aboutsummaryrefslogtreecommitdiff
path: root/llvm/unittests/IR/DominatorTreeTest.cpp
AgeCommit message (Collapse)AuthorFilesLines
2025-05-04[llvm] Remove unused local variables (NFC) (#138454)Kazu Hirata1-1/+0
2024-07-31[Support] Erase blocks after DomTree::eraseNode (#101195)Alexis Engelke1-2/+1
Change eraseNode to require that the basic block is still contained inside the function. This is a preparation for using numbers of basic blocks inside the dominator tree, which are invalid for blocks that are not inside a function.
2023-02-16[Dominators] check indirect branches of callbrNick Desaulniers1-0/+43
This will be necessary to support outputs from asm goto along indirect edges. Test via: $ pushd llvm/build; ninja IRTests; popd $ ./llvm/build/unittests/IR/IRTests \ --gtest_filter=DominatorTree.CallBrDomination Also, return nullptr in Instruction::getInsertionPointAfterDef for CallBrInst as was recommened in https://reviews.llvm.org/D135997#3991427. The following phab review was folded into this commit: https://reviews.llvm.org/D140166 Link: Link: https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8 Reviewed By: void, efriedma, ChuanqiXu, MaskRay Differential Revision: https://reviews.llvm.org/D135997
2022-12-20[llvm] Use std::optional instead of OptionalKazu Hirata1-10/+10
This is part of an effort to migrate from llvm::Optional to std::optional: https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
2020-10-22[DomTree] Accept Value as Def (NFC)Nikita Popov1-0/+29
Non-instruction defs like arguments, constants or global values always dominate all instructions/uses inside the function. This case currently needs to be treated separately by the caller, see https://reviews.llvm.org/D89623#inline-832818 for an example. This patch makes the dominator tree APIs accept a Value instead of an Instruction and always returns true for the non-Instruction case. A complication here is that BasicBlocks are also Values. For that reason we can't support the dominates(Value *, BasicBlock *) variant, as it would conflict with dominates(BasicBlock *, BasicBlock *), which has different semantics. For the other two APIs we assert that the passed value is not a BasicBlock. Differential Revision: https://reviews.llvm.org/D89632
2020-07-06Fix [-Werror,-Wsign-compare] in dominator unit test.Eric Christopher1-1/+1
2020-07-06DomTree: Remove getRoots() accessorNicolai Hähnle1-1/+1
Summary: Avoid exposing details about how roots are stored. This enables subsequent type-erasure changes. v5: - cleanup a unit test by using EXPECT_EQ instead of EXPECT_TRUE Change-Id: I532b774cc71f2224e543bc7d79131d97f63f093d Reviewers: arsenm, RKSimon, mehdi_amini, courbet Subscribers: jvesely, wdng, hiraditya, kuhar, kerbowa, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D83085
2020-06-17[NFC] Add API for edge domination check in dom treeMax Kazantsev1-0/+51
2020-02-20[Dominators] Use Instruction::comesBefore for block-local queries, NFCVedant Kumar1-0/+31
Use the lazy instruction ordering facility for block-local dominance queries. Differential Revision: https://reviews.llvm.org/D74931
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2018-10-15[TI removal] Make `getTerminator()` return a generic `Instruction`.Chandler Carruth1-1/+1
This removes the primary remaining API producing `TerminatorInst` which will reduce the rate at which code is introduced trying to use it and generally make it much easier to remove the remaining APIs across the codebase. Also clean up some of the stragglers that the previous mechanical update of variables missed. Users of LLVM and out-of-tree code generally will need to update any explicit variable types to handle this. Replacing `TerminatorInst` with `Instruction` (or `auto`) almost always works. Most of these edits were made in prior commits using the perl one-liner: ``` perl -i -ple 's/TerminatorInst(\b.* = .*getTerminator\(\))/Instruction\1/g' ``` This also my break some rare use cases where people overload for both `Instruction` and `TerminatorInst`, but these should be easily fixed by removing the `TerminatorInst` overload. llvm-svn: 344504
2018-06-16[Dominators] Change getNode parameter type to const NodeT * (NFC).Florian Hahn1-1/+3
DominatorTreeBase::getNode does not modify its parameter and this change allows callers that only have access to const pointers to use it without casting. Reviewers: kuhar, dblaikie, chandlerc Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D48231 llvm-svn: 334892
2018-05-23[Dominators] Add PDT constructor from FunctionJakub Kuderski1-25/+23
Summary: This patch adds a PDT constructor from Function and lets codes previously using a local class to do this use PostDominatorTree class directly. Reviewers: davide, kuhar, grosser, dberlin Reviewed By: kuhar Author: NutshellySima Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46709 llvm-svn: 333102
2018-05-12[IDF] Enforce the returned blocks to be sorted.Michael Zolotukhin1-0/+70
Summary: Currently the order of blocks returned by `IDF::calculate` can be non-deterministic. This was discovered in several attempts to enable SSAUpdaterBulk for JumpThreading (which led to miscompare in bootstrap between stage 3 and stage4). Originally, the blocks were put into a priority queue with a depth level as their key, and this patch adds a DFSIn number as a second key to specify a deterministic order across blocks from one level. The solution was suggested by Daniel Berlin. Reviewers: dberlin, davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46646 llvm-svn: 332167
2018-02-28[Dominators] Remove verifyDomTree and add some verifying for Post Dom TreesDavid Green1-2/+2
Removes verifyDomTree, using assert(verify()) everywhere instead, and changes verify a little to always run IsSameAsFreshTree first in order to print good output when we find errors. Also adds verifyAnalysis for PostDomTrees, which will allow checking of PostDomTrees it the same way we check DomTrees and MachineDomTrees. Differential Revision: https://reviews.llvm.org/D41298 llvm-svn: 326315
2018-01-21[Dominators] Remove misleading double-deletion testJakub Kuderski1-30/+0
Summary: It's generally not safe to perform multiple DomTree updates without using the incremental API. Although it is supposed to work in this particular case, the testcase is misleading/confusing, and it's better to remove it. Reviewers: dberlin, brzycki, davide, grosser Reviewed By: davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42333 llvm-svn: 323058
2018-01-19[Dominators] Visit affected node candidates found at different root levelsJakub Kuderski1-0/+25
Summary: This patch attempts to fix the DomTree incremental insertion bug found here [[ https://bugs.llvm.org/show_bug.cgi?id=35969 | PR35969 ]] . When performing an insertion into a piece of unreachable CFG, we may find the same not at different levels. When this happens, the node can turn out to be affected when we find it starting from a node with a lower level in the tree. The level at which we start visitation affects if we consider a node affected or not. This patch tracks the lowest level at which each node was visited during insertion and allows it to be visited multiple times, if it can cause it to be considered affected. Reviewers: brzycki, davide, dberlin, grosser Reviewed By: brzycki Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42231 llvm-svn: 322993
2017-08-15[Dominators] Include infinite loops in PostDominatorTreeJakub Kuderski1-67/+92
Summary: This patch teaches PostDominatorTree about infinite loops. It is built on top of D29705 by @dberlin which includes a very detailed motivation for this change. What's new is that the patch also teaches the incremental updater how to deal with reverse-unreachable regions and how to properly maintain and verify tree roots. Before that, the incremental algorithm sometimes ended up preserving reverse-unreachable regions after updates that wouldn't appear in the tree if it was constructed from scratch on the same CFG. This patch makes the following assumptions: - A sequence of updates should produce the same tree as a recalculating it. - Any sequence of the same updates should lead to the same tree. - Siblings and roots are unordered. The last two properties are essential to efficiently perform batch updates in the future. When it comes to the first one, we can decide later that the consistency between freshly built tree and an updated one doesn't matter match, as there are many correct ways to pick roots in infinite loops, and to relax this assumption. That should enable us to recalculate postdominators less frequently. This patch is pretty conservative when it comes to incremental updates on reverse-unreachable regions and ends up recalculating the whole tree in many cases. It should be possible to improve the performance in many cases, if we decide that it's important enough. That being said, my experiments showed that reverse-unreachable are very rare in the IR emitted by clang when bootstrapping clang. Here are the statistics I collected by analyzing IR between passes and after each removePredecessor call: ``` # functions: 52283 # samples: 337609 # reverse unreachable BBs: 216022 # BBs: 247840796 Percent reverse-unreachable: 0.08716159869015269 % Max(PercRevUnreachable) in a function: 87.58620689655172 % # > 25 % samples: 471 ( 0.1395104988314885 % samples ) ... in 145 ( 0.27733680163724345 % functions ) ``` Most of the reverse-unreachable regions come from invalid IR where it wouldn't be possible to construct a PostDomTree anyway. I would like to commit this patch in the next week in order to be able to complete the work that depends on it before the end of my internship, so please don't wait long to voice your concerns :). Reviewers: dberlin, sanjoy, grosser, brzycki, davide, chandlerc, hfinkel Reviewed By: dberlin Subscribers: nhaehnle, javed.absar, kparzysz, uabelho, jlebar, hiraditya, llvm-commits, dberlin, david2050 Differential Revision: https://reviews.llvm.org/D35851 llvm-svn: 310940
2017-08-03[unittest] Remove TODO comment which caused concernTobias Grosser1-1/+1
Remove the second part of the TODO comment that highlighted an issue with possibly connecting all nodes to the exit of the CFG. This caused concerns with Jakub Kuderski regarding its feasability, hence we remove it. Such points are better discussed outside of CFG. If connecting all nodes makes sense and what the impact is is currently part of an active review discussion. llvm-svn: 309919
2017-08-02[Dominators] Teach LoopDeletion to use the new incremental APIJakub Kuderski1-0/+30
Summary: This patch makes LoopDeletion use the incremental DominatorTree API. We modify LoopDeletion to perform the deletion in 5 steps: 1. Create a new dummy edge from the preheader to the exit, by adding a conditional branch. 2. Inform the DomTree about the new edge. 3. Remove the conditional branch and replace it with an unconditional edge to the exit. This removes the edge to the loop header, making it unreachable. 4. Inform the DomTree about the deleted edge. 5. Remove the unreachable block from the function. Creating the dummy conditional branch is necessary to perform incremental DomTree update. We should consider using the batch updater when it's ready. Reviewers: dberlin, davide, grosser, sanjoy Reviewed By: dberlin, grosser Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35391 llvm-svn: 309850
2017-08-01[PostDom] document the current handling of infinite loops and unreachablesTobias Grosser1-0/+268
Summary: As we are in the process of changing the behavior of how the post-dominator tree is computed, make sure we have some more test coverage in this area. Current inconsistencies: - Newly unreachable nodes are not added as new roots, in case the PDT is updated but not rebuilt. - Newly unreachable loops are not added to the CFG at all (neither when building from scratch nor when updating the CFG). This is inconsistent with the fact that unreachables are added to the PDT, but unreachable loops not. On the other side, PDT relationships are not loosened at the moment in cases where new unreachable loops are built. This commit is providing additional test coverage for https://reviews.llvm.org/D35851 Reviewers: dberlin, kuhar Reviewed By: kuhar Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D36107 llvm-svn: 309684
2017-07-15[Dominators] Fix reachable visitation and reenable a unit testJakub Kuderski1-1/+27
This fixes a minor bug in insertion to a reachable node that caused DominatorTree.InsertDeleteExhaustive flakiness. The patch also adds a new testcase for this exact failure. llvm-svn: 308074
2017-07-14[Dominators] Temporarily disable a flaky unit testJakub Kuderski1-1/+1
The DominatorTree.InsertDeleteExhaustive uses a RNG with a constant seed to generate different sequences of updates. The test fails on some buildbots and this patch disables it for now. llvm-svn: 308070
2017-07-14[Dominators] Remove an extra semicolon and add a missing include.Jakub Kuderski1-1/+2
llvm-svn: 308065
2017-07-14[Dominators] Implement incremental deletionsJakub Kuderski1-0/+127
Summary: This patch implements incremental edge deletions. It also makes DominatorTreeBase store a pointer to the parent function. The parent function is needed to perform full rebuilts during some deletions, but it is also used to verify that inserted and deleted edges come from the same function. Reviewers: dberlin, davide, grosser, sanjoy, brzycki Reviewed By: dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D35342 llvm-svn: 308062
2017-07-14[Dominators] Implement incremental insertionsJakub Kuderski1-0/+125
Summary: This patch introduces incremental edge insertions based on the Depth Based Search algorithm. Insertions should work for both dominators and postdominators. Reviewers: dberlin, grosser, davide, sanjoy, brzycki Reviewed By: dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D35341 llvm-svn: 308054
2017-07-14[Dominators] Make IsPostDominator a template parameterJakub Kuderski1-11/+10
Summary: DominatorTreeBase used to have IsPostDominators (bool) member to indicate if the tree is a dominator or a postdominator tree. This made it possible to switch between the two 'modes' at runtime, but it isn't used in practice anywhere. This patch makes IsPostDominator a template argument. This way, it is easier to switch between different algorithms at compile-time based on this argument and design external utilities around it. It also makes it impossible to incidentally assign a postdominator tree to a dominator tree (and vice versa), and to further simplify template code in GenericDominatorTreeConstruction. Reviewers: dberlin, sanjoy, davide, grosser Reviewed By: dberlin Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35315 llvm-svn: 308040
2017-07-01[Dominators] Reapply r306892, r306893, r306893.Jakub Kuderski1-0/+13
This reverts commit r306907 and reapplies the patches in the title. The patches used to make one of the CodeGen/ARM/2011-02-07-AntidepClobber.ll test to fail because of a missing null check. llvm-svn: 306919
2017-06-30Revert "[Dominators] Teach IDF to use level information"Jakub Kuderski1-13/+0
This reverts commit r306894. Revert "[Dominators] Add NearestCommonDominator verification" This reverts commit r306893. Revert "[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries" This reverts commit r306892. llvm-svn: 306907
2017-06-30[Dominators] Keep tree level in DomTreeNode and use it to find NCD and ↵Jakub Kuderski1-0/+13
answer dominance queries Summary: This patch makes DomTreeNodes keep their level (depth) in the DomTree. By having this information always available, it is possible to speedup and simplify findNearestCommonDominator and certain dominance queries. In the future, level information will be also needed to perform incremental updates. My testing doesn't show any noticeable performance differences after applying this patch. There may be some improvements when other passes are thought to use the level information. Reviewers: dberlin, sanjoy, chandlerc, grosser Reviewed By: dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34548 llvm-svn: 306892
2017-06-30[Dominators] Don't compute DFS InOut numbers eagerly.Jakub Kuderski1-0/+2
Summary: DFS InOut numbers currently get eagerly computer upon DomTree construction. They are only needed to answer dome dominance queries and they get invalidated by updates and recalculations. Because of that, it is faster in practice to compute them lazily when they are actually needed. Clang built without this patch takes 6m 45s to boostrap on my machine, and with the patch applied 6m 38s. Reviewers: sanjoy, dberlin, chandlerc Reviewed By: dberlin Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34296 llvm-svn: 306778
2017-06-05Handle non-unique edges in edge-dominanceAdam Nemet1-0/+52
This removes a quadratic behavior in assert-enabled builds. GVN propagates the equivalence from a condition into the blocks guarded by the condition. E.g. for 'if (a == 7) { ... }', 'a' will be replaced in the block with 7. It does this by replacing all the uses of 'a' that are dominated by the true edge. For a switch with N cases and U uses of the value, this will mean N * U calls to 'dominates'. Asserting isSingleEdge in 'dominates' make this N^2 * U because this function checks for the uniqueness of the edge. I.e. traverses each edge between the SwitchInst's block and the cases. The change removes the assert and makes 'dominates' works correctly in the presence of non-unique edges. This brings build time down by an order of magnitude for an input that has ~10k cases in a switch statement. Differential Revision: https://reviews.llvm.org/D33584 llvm-svn: 304721
2017-05-27Rearrange Dom unittest to accommodate multiple testsAdam Nemet1-223/+213
I've taken the approach from the LoopInfo test: * Rather than running in the pass manager just build the analyses manually * Split out the common parts (makeLLVMModule, runWithDomTree) into helpers Differential Revision: https://reviews.llvm.org/D33617 llvm-svn: 304061
2017-05-27clang-format DomTree unittestAdam Nemet1-242/+241
llvm-svn: 304060
2017-05-20Fix test typo. NFCXin Tong1-2/+2
llvm-svn: 303489
2017-01-10[StructurizeCfg] Update dominator info.Serge Pavlov1-0/+10
In some cases StructurizeCfg updates root node, but dominator info remains unchanges, it causes crash when expensive checks are enabled. To cope with this problem a new method was added to DominatorTreeBase that allows adding new root nodes, it is called in StructurizeCfg to put dominator tree in sync. This change fixes PR27488. Differential Revision: https://reviews.llvm.org/D28114 llvm-svn: 291530
2016-04-14Remove every uses of getGlobalContext() in LLVM (but the C API)Mehdi Amini1-4/+4
At the same time, fixes InstructionsTest::CastInst unittest: yes you can leave the IR in an invalid state and exit when you don't destroy the context (like the global one), no longer now. This is the first part of http://reviews.llvm.org/D19094 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266379
2016-02-25Introduce analysis pass to compute PostDominators in the new pass manager. NFCHongbin Zheng1-3/+4
Differential Revision: http://reviews.llvm.org/D17537 llvm-svn: 261902
2016-02-25Revert "Introduce analysis pass to compute PostDominators in the new pass ↵Hongbin Zheng1-4/+3
manager. NFC" This reverts commit a3e5cc6a51ab5ad88d1760c63284294a4e34c018. llvm-svn: 261891
2016-02-25Introduce analysis pass to compute PostDominators in the new pass manager. NFCHongbin Zheng1-3/+4
Differential Revision: http://reviews.llvm.org/D17537 llvm-svn: 261882
2015-10-20unittests: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith1-14/+14
llvm-svn: 250843
2015-06-17Move the personality function from LandingPadInst to FunctionDavid Majnemer1-2/+2
The personality routine currently lives in the LandingPadInst. This isn't desirable because: - All LandingPadInsts in the same function must have the same personality routine. This means that each LandingPadInst beyond the first has an operand which produces no additional information. - There is ongoing work to introduce EH IR constructs other than LandingPadInst. Moving the personality routine off of any one particular Instruction and onto the parent function seems a lot better than have N different places a personality function can sneak onto an exceptional function. Differential Revision: http://reviews.llvm.org/D10429 llvm-svn: 239940
2015-04-14Only recalculate DFS Numbers if invalid. Invalidate DFS numbers on reset. ↵Daniel Berlin1-0/+28
Add unit test to verify recalculation llvm-svn: 234933
2015-04-11Use 'override/final' instead of 'virtual' for overridden methodsAlexander Kornienko1-2/+2
The patch is generated using clang-tidy misc-use-override check. This command was used: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py \ -checks='-*,misc-use-override' -header-filter='llvm|clang' \ -j=32 -fix -format http://reviews.llvm.org/D8925 llvm-svn: 234679
2015-02-13[PM] Remove the old 'PassManager.h' header file at the top level ofChandler Carruth1-2/+2
LLVM's include tree and the use of using declarations to hide the 'legacy' namespace for the old pass manager. This undoes the primary modules-hostile change I made to keep out-of-tree targets building. I sent an email inquiring about whether this would be reasonable to do at this phase and people seemed fine with it, so making it a reality. This should allow us to start bootstrapping with modules to a certain extent along with making it easier to mix and match headers in general. The updates to any code for users of LLVM are very mechanical. Switch from including "llvm/PassManager.h" to "llvm/IR/LegacyPassManager.h". Qualify the types which now produce compile errors with "legacy::". The most common ones are "PassManager", "PassManagerBase", and "FunctionPassManager". llvm-svn: 229094
2014-08-19Modernize the .ll parsing interface.Rafael Espindola1-4/+3
* Use StringRef instead of std::string& * Return a std::unique_ptr<Module> instead of taking an optional module to write to (was not really used). * Use current comment style. * Use current naming convention. llvm-svn: 215989
2014-06-08[C++11] Use 'nullptr'.Craig Topper1-1/+1
llvm-svn: 210442
2014-03-06Replace OwningPtr<T> with std::unique_ptr<T>.Ahmed Charles1-1/+1
This compiles with no changes to clang/lld/lldb with MSVC and includes overloads to various functions which are used by those projects and llvm which have OwningPtr's as parameters. This should allow out of tree projects some time to move. There are also no changes to libs/Target, which should help out of tree targets have time to move, if necessary. llvm-svn: 203083
2014-01-13[PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth1-3/+4
can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
2014-01-13[cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth1-1/+1
directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
generated by cgit v1.1 at 2025-09-29 04:50:50 +0000