aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/Analysis/Dominators.h
AgeCommit message (Collapse)Author
2013-03-05Add some constantness.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176518 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-05std::distance() == 0 means that iterators are equal. No functionality change.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176516 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02Move all of the header files which are involved in modelling the LLVM IRChandler Carruth
into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Sort the #include lines for the include/... tree with the script.Chandler Carruth
AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-04Fix doxygen comment to match parameters' names.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165239 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-27Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru
See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164768 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-27Fix a typo 'iff' => 'if'Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164767 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-16Teach GVN to reason about edges dominating uses. This allows it to handle casesRafael Espindola
where some fact lake a=b dominates a use in a phi, but doesn't dominate the basic block itself. This feature could also be implemented by splitting critical edges, but at least with the current algorithm reasoning about the dominance directly is faster. The time for running "opt -O2" in the testcase in pr10584 is 1.003 times slower and on gcc as a single file it is 1.0007 times faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162023 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-10Move BasicBlockEdge to the cpp file. No functionality change.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161663 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-07The dominance computation already has logic for computing if an edge dominatesRafael Espindola
a use or a BB, but it is inline in the handling of the invoke instruction. This patch refactors it so that it can be used in other cases. For example, in define i32 @f(i32 %x) { bb0: %cmp = icmp eq i32 %x, 0 br i1 %cmp, label %bb2, label %bb1 bb1: br label %bb2 bb2: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] %foo = add i32 %cond, %x ret i32 %foo } GVN should be able to replace %x with 0 in any use that is dominated by the true edge out of bb0. In the above example the only such use is the one in the phi. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161429 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Remove 'static' from inline functions defined in header files.Chandler Carruth
There is a pretty staggering amount of this in LLVM's header files, this is not all of the instances I'm afraid. These include all of the functions that (in my build) are used by a non-static inline (or external) function. Specifically, these issues were caught by the new '-Winternal-linkage-in-inline' warning. I'll try to just clean up the remainder of the clearly redundant "static inline" cases on functions (not methods!) defined within headers if I can do so in a reliable way. There were even several cases of a missing 'inline' altogether, or my personal favorite "static bool inline". Go figure. ;] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158800 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-12Add forms of dominates and isReachableFromEntry that accept a UseDan Gohman
directly instead of a user Instruction. This allows them to test whether a def dominates a particular operand if the user instruction is a PHI. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154631 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-02Make dominatedBySlowTreeWalk private and assert cases handled by the caller.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153905 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-02Add missing 'd'.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153872 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-31Add a workaround for building with old versions of clang.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153820 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-30Handle unreachable code in the dominates functions. This changes users whenRafael Espindola
needed for correctness, but still doesn't clean up code that now unnecessary checks for reachability. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153755 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-24Avoid using dominatedBySlowTreeWalk.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153398 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-26Change the implementation of dominates(inst, inst) to one based on what theRafael Espindola
verifier does. This correctly handles invoke. Thanks to Duncan, Andrew and Chris for the comments. Thanks to Joerg for the early testing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151469 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-26Don't call dominates on unreachable instructions.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151466 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-20SCEVExpander fixes. Affects LSR and indvars.Andrew Trick
LSR has gradually been improved to more aggressively reuse existing code, particularly existing phi cycles. This exposed problems with the SCEVExpander's sloppy treatment of its insertion point. I applied some rigor to the insertion point problem that will hopefully avoid an endless bug cycle in this area. Changes: - Always used properlyDominates to check safe code hoisting. - The insertion point provided to SCEV is now considered a lower bound. This is usually a block terminator or the use itself. Under no cirumstance may SCEVExpander insert below this point. - LSR is reponsible for finding a "canonical" insertion point across expansion of different expressions. - Robust logic to determine whether IV increments are in "expanded" form and/or can be safely hoisted above some insertion point. Fixes PR11783: SCEVExpander assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148535 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-04Simplify code. No functionality change.Benjamin Kramer
Using DenseMap iterators isn't free as they have to check for empty buckets. Dominator queries are common so this gives a minor speedup. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147544 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-05Change the Dominators recalculate() function to only rely on GraphTraitsAnna Zaks
This is a patch by Guoping Long! As part of utilizing LLVM Dominator computation in Clang, made two changes to LLVM dominators tree implementation: - (1) Change the recalculate() template function to only rely on GraphTraits. - (2) Add a size() method to GraphTraits template class to query the number of nodes in the graph. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145837 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23In the simpler version of the link-eval data structure that we use in dominatorCameron Zwarich
computation, the Ancestor field is always set to the Parent, so we can remove the explicit link entirely and merge the Parent and Ancestor fields. Instead of checking for whether an ancestor exists for a node or not, we simply check whether the node has already been processed. This is simpler if Compress is inlined into Eval, so I did that as well. This is about a 3% speedup running -domtree on test-suite + SPEC2000 & SPEC2006, but it also opens up some opportunities for further improvement. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124061 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Remove useless struct fields.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124058 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Remove friend declaration for removed function.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124057 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Put the Dominator improvements back in. They were not the cause of bootstrap ↵Jakob Stoklund Olesen
miscomparisons. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123273 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Speculatively revert the recent improvements to Dominators.h in an attempt ↵Jakob Stoklund Olesen
to track down the gcc bootstrap miscompare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123254 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09DominatorTree->print() now prints the status of the DFSNumbers correctlyTobias Grosser
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123120 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner
so that Dominators.h is *just* domtree. Also prune #includes a bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122714 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Remove an unused member function.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122693 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02Speed up dominator computation some more by optimizing bucket processing. WhenCameron Zwarich
naively implemented, the Lengauer-Tarjan algorithm requires a separate bucket for each vertex. However, this is unnecessary, because each vertex is only placed into a single bucket (that of its semidominator), and each vertex's bucket is processed before it is added to any bucket itself. Instead of using a bucket per vertex, we use a single array Buckets that has two purposes. Before the vertex V with DFS number i is processed, Buckets[i] stores the index of the first element in V's bucket. After V's bucket is processed, Buckets[i] stores the index of the next element in the bucket to which V now belongs, if any. Reading from the buckets can also be optimized. Instead of processing the bucket of V's parent at the end of processing V, we process the bucket of V itself at the beginning of processing V. This means that the case of the root vertex can be simplified somewhat. It also means that we don't need to look up the DFS number of the semidominator of every node in the bucket we are processing, since we know it is the current index being processed. This is a 6.5% speedup running -domtree on test-suite + SPEC2000/2006, with larger speedups of around 12% on the larger benchmarks like GCC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122680 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-22Constify.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122447 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-19Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson
exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116820 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-06Constify isReachableFromEntry.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115788 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-27Constify properlyDominates in the same manner as dominates.Dan Gohman
Add constified overloads for findNearestCommonDominator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114834 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-10typoesGabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113647 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110460 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Revert r110396 to fix buildbots.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110410 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-05Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson
address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110396 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-16Add dump() to DominanceFrontierTobias Grosser
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108512 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-09fix clang selfhost issue (shadowing)Gabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107970 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-09refactor type expressions and cache operator*'s resultGabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107964 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-18Don't bother calling releaseMemory before destroying the DominatorTreeBase.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106287 91177308-0d34-0410-b5e6-96231b3b80d8
2010-03-24Fix coding style.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99362 91177308-0d34-0410-b5e6-96231b3b80d8
2010-03-24Generalize findNearestCommonDominator to work on post-dominators,Dan Gohman
based on a suggestion by Jochen Wilhelmy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99361 91177308-0d34-0410-b5e6-96231b3b80d8
2010-03-01Whitespace cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97452 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-07Add assert to check dominance dfs numbers.Tobias Grosser
Compare the dominance information calculated using a dominance tree walk to the information calculated based on DFS numbers, if XDEBUG is enabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92969 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-07Remove workaround in PostDominatorsTobias Grosser
Remove a FIXME and unify code that was necessary to work around broken updateDFSNumbers(). Before updateDFSNumbers() did not work correctly for post dominators. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92968 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-07Fix DFS number calculation for postdominatorsTobias Grosser
The DFS number calculation for postdominators was broken. In the case of multiple exits that form the post dominator root nodes, do not iterate over all exits, but start from the virtual root node. Otherwise bbs, that are not post dominated by any exit but by the virtual root node, will never be assigned a DFS number. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92967 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-14Remove dead variable found by clang++.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@88803 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-27 16:13:40 +0000