summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/IR/DominatorTreeTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [Dominators] Reapply r306892, r306893, r306893.Jakub Kuderski2017-07-011-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
* Revert "[Dominators] Teach IDF to use level information"Jakub Kuderski2017-06-301-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
* [Dominators] Keep tree level in DomTreeNode and use it to find NCD and ↵Jakub Kuderski2017-06-301-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
* [Dominators] Don't compute DFS InOut numbers eagerly.Jakub Kuderski2017-06-301-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
* Handle non-unique edges in edge-dominanceAdam Nemet2017-06-051-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
* Rearrange Dom unittest to accommodate multiple testsAdam Nemet2017-05-271-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
* clang-format DomTree unittestAdam Nemet2017-05-271-242/+241
| | | | llvm-svn: 304060
* Fix test typo. NFCXin Tong2017-05-201-2/+2
| | | | llvm-svn: 303489
* [StructurizeCfg] Update dominator info.Serge Pavlov2017-01-101-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
* Remove every uses of getGlobalContext() in LLVM (but the C API)Mehdi Amini2016-04-141-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
* Introduce analysis pass to compute PostDominators in the new pass manager. NFCHongbin Zheng2016-02-251-3/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D17537 llvm-svn: 261902
* Revert "Introduce analysis pass to compute PostDominators in the new pass ↵Hongbin Zheng2016-02-251-4/+3
| | | | | | | | manager. NFC" This reverts commit a3e5cc6a51ab5ad88d1760c63284294a4e34c018. llvm-svn: 261891
* Introduce analysis pass to compute PostDominators in the new pass manager. NFCHongbin Zheng2016-02-251-3/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D17537 llvm-svn: 261882
* unittests: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-201-14/+14
| | | | llvm-svn: 250843
* Move the personality function from LandingPadInst to FunctionDavid Majnemer2015-06-171-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
* Only recalculate DFS Numbers if invalid. Invalidate DFS numbers on reset. ↵Daniel Berlin2015-04-141-0/+28
| | | | | | Add unit test to verify recalculation llvm-svn: 234933
* Use 'override/final' instead of 'virtual' for overridden methodsAlexander Kornienko2015-04-111-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
* [PM] Remove the old 'PassManager.h' header file at the top level ofChandler Carruth2015-02-131-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
* Modernize the .ll parsing interface.Rafael Espindola2014-08-191-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
* [C++11] Use 'nullptr'.Craig Topper2014-06-081-1/+1
| | | | llvm-svn: 210442
* Replace OwningPtr<T> with std::unique_ptr<T>.Ahmed Charles2014-03-061-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
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-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
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-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
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-071-1/+1
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* Fix dominator descendants for unreachable blocks.Diego Novillo2013-12-021-0/+27
| | | | | | | | | | | | | When a block is unreachable, asking its dom tree descendants should return the empty set. However, the computation of the descendants was causing a segmentation fault because the dom tree node we get from the basic block is initially NULL. Fixed by adding a test for a valid dom tree node before we iterate. The patch also adds some unit tests to the existing dom tree tests. llvm-svn: 196099
* llvm/unittests: Use OwningPtr to fix --vg-leak.NAKAMURA Takumi2013-01-231-1/+1
| | | | llvm-svn: 173240
* DominatorTreeTest.cpp: Add the file header.NAKAMURA Takumi2013-01-231-0/+9
| | | | llvm-svn: 173233
* Rename the VMCore unittest tree to IR. Somehow was missed when doing theChandler Carruth2013-01-071-0/+195
library rename. llvm-svn: 171747
OpenPOWER on IntegriCloud