summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/IteratedDominanceFrontier.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [IDF] Enforce the returned blocks to be sorted.Michael Zolotukhin2018-05-121-5/+11
| | | | | | | | | | | | | | | | | | | | 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
* [Dominators] Make IsPostDominator a template parameterJakub Kuderski2017-07-141-4/+4
| | | | | | | | | | | | | | | | | 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
* [Dominators] Reapply r306892, r306893, r306893.Jakub Kuderski2017-07-011-10/+2
| | | | | | | | | 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-2/+10
| | | | | | | | | | | | | | 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] Teach IDF to use level informationJakub Kuderski2017-06-301-10/+2
| | | | | | | | | | | | | | Summary: This patch teaches IteratedDominanceFrontier to use the level information stored in DomTreeNodes instead of calculating it manually. Reviewers: dberlin, sanjoy, davide Reviewed By: davide Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34703 llvm-svn: 306894
* Drop graph_ prefixDaniel Berlin2017-02-091-1/+1
| | | | llvm-svn: 294621
* GraphTraits: Add range versions of graph traits functions (graph_nodes, ↵Daniel Berlin2017-02-091-4/+1
| | | | | | | | | | | | | | | | | | | | | | | | | graph_children, inverse_graph_nodes, inverse_graph_children). Summary: Convert all obvious node_begin/node_end and child_begin/child_end pairs to range based for. Sending for review in case someone has a good idea how to make graph_children able to be inferred. It looks like it would require changing GraphTraits to be two argument or something. I presume inference does not happen because it would have to check every GraphTraits in the world to see if the noderef types matched. Note: This change was 3-staged with clang as well, which uses Dominators/etc from LLVM. Reviewers: chandlerc, tstellarAMD, dblaikie, rsmith Subscribers: arsenm, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D29767 llvm-svn: 294620
* Normalize file docs. NFC.George Burgess IV2016-07-211-1/+1
| | | | | | | | Having the added `\brief` made doxygen interpret it as the summary for the `llvm` namespace (visible at: http://llvm.org/doxygen/namespaces.html). llvm-svn: 276331
* Correct IDF calculator for ReverseIDFDaniel Berlin2016-04-191-5/+14
| | | | | | | | | | | | | | Summary: Need to use predecessors for reverse graph, successors for forward graph. succ_iterator/pred_iterator are not compatible, this patch is all the work necessary to work around that (which is what everywhere else does). Not sure if there is a better way, so cc'ing some random folks to take a gander :) Reviewers: dblaikie, qcolombet, echristo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18796 llvm-svn: 266718
* Move IDF Calculation to a separate file, expose an interface to it.Daniel Berlin2015-04-211-0/+95
Summary: MemorySSA uses this algorithm as well, and this enables us to reuse the code in both places. There are no actual algorithm or datastructure changes in here, just code movement. Reviewers: qcolombet, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9118 llvm-svn: 235406
OpenPOWER on IntegriCloud