OSDN Git Service

Some improvements related to the computation of isReachable.
authorRoman Levenstein <romix.llvm@googlemail.com>
Wed, 26 Mar 2008 09:18:09 +0000 (09:18 +0000)
committerRoman Levenstein <romix.llvm@googlemail.com>
Wed, 26 Mar 2008 09:18:09 +0000 (09:18 +0000)
commite513ba49589bcf8fdf7dad658e20db21d6ef4758
treee68a4aeb11437cb678150c59824a6a355911bfa6
parent7aae876db13b76a10d690777d93e11093a15c826
Some improvements related to the computation of isReachable.
This fixes Bugzilla #1835 (http://llvm.org/bugs/show_bug.cgi?id=1835).
This patched is reviewed by Tanya and Dan. Dan tested and approved it.

The reason for the bad performance of the old algorithm is that it is very naive and scans every
time all nodes of the DAG in the worst case.

This patch introduces  a new algorithm based on the paper "Online algorithms
for maintaining the topological order of a directed acyclic graph" by
David J.Pearce and Paul H.J.Kelly. This is the MNR algorithm. It has a
linear time worst-case and performs much better in most situations.

The paper can be found here:
http://fano.ics.uci.edu/cites/Document/Online-algorithms-for-maintaining-the-topological-order-of-a-directed-acyclic-graph.html

The main idea of the new algorithm is to compute the topological ordering of the SNodes in the
DAG and to maintain it even after DAG modifications. The topological ordering allows for very fast
node reachability checks.

Tests on very big  input files with tens of thousands of instructions in a BB indicate huge
speed-ups (up to 10x compilation time improvement) compared to the old version.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48817 91177308-0d34-0410-b5e6-96231b3b80d8
lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp