Fix PR681 by using the standard Lengauer and Tarjan algorithm for dominator
authorNate Begeman <natebegeman@mac.com>
Sat, 11 Mar 2006 02:20:46 +0000 (02:20 +0000)
committerNate Begeman <natebegeman@mac.com>
Sat, 11 Mar 2006 02:20:46 +0000 (02:20 +0000)
commit442b32b5c5f690bc9b49d67b3ec76008879bc4d9
treefe3e71fffa0ec5fb7290b29d95eb510178c63579
parent78167faa18e66e95be3d73028b2db99bf3fbdcb3
Fix PR681 by using the standard Lengauer and Tarjan algorithm for dominator
set construction, rather than intersecting various std::sets.  This reduces
the memory usage for the testcase in PR681 from 496 to 26MB of ram on my
darwin system, and reduces the runtime from 32.8 to 0.8 seconds on a
2.5GHz G5.  This also enables future code sharing between Dom and PostDom
now that they share near-identical implementations.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@26707 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/Analysis/PostDominators.h
lib/Analysis/PostDominators.cpp