summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* StructurizeCFG: Test for branch divergence correctlyNicolai Haehnle2018-04-041-13/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes cases like the new test @nonuniform. In that test, %cc itself is a uniform value; however, when reading it after the end of the loop in basic block %if, its value is effectively non-uniform, so the branch is non-uniform. This problem was encountered in https://bugs.freedesktop.org/show_bug.cgi?id=103743; however, this change in itself is not sufficient to fix that bug, as there is another issue in the AMDGPU backend. As discovered after committing an earlier version of this change, this exposes a subtle interaction between this pass and DivergenceAnalysis: since we remove and re-create branch instructions, we can no longer rely on DivergenceAnalysis for branches in subregions that were already processed by the pass. Explicitly remove branch instructions from DivergenceAnalysis to avoid dangling pointers as a matter of defensive programming, and change how we detect non-uniform subregions. Change-Id: I32bbffece4a32f686fab54964dae1a5dd72949d4 Differential Revision: https://reviews.llvm.org/D43743 llvm-svn: 329165
* Transforms: Introduce Transforms/Utils.h rather than spreading the ↵David Blaikie2018-03-281-0/+1
| | | | | | | | | declarations amongst Scalar.h and IPO.h Fixes layering - Transforms/Utils shouldn't depend on including a Scalar or IPO header, because Scalar and IPO depend on Utils. llvm-svn: 328717
* Revert "StructurizeCFG: Test for branch divergence correctly"Adam Nemet2018-02-241-12/+3
| | | | | | | | This reverts commit r325881. Breaks many bots llvm-svn: 326037
* StructurizeCFG: Test for branch divergence correctlyNicolai Haehnle2018-02-231-3/+12
| | | | | | | | | | | | | | | | | | | | | | Summary: This fixes cases like the new test @nonuniform. In that test, %cc itself is a uniform value; however, when reading it after the end of the loop in basic block %if, its value is effectively non-uniform. This problem was encountered in https://bugs.freedesktop.org/show_bug.cgi?id=103743; however, this change in itself is not sufficient to fix that bug, as there is another issue in the AMDGPU backend. Change-Id: I32bbffece4a32f686fab54964dae1a5dd72949d4 Reviewers: arsenm, rampitec, jlebar Subscribers: wdng, tpr, llvm-commits Differential Revision: https://reviews.llvm.org/D40546 llvm-svn: 325881
* Revert r321751, "StructurizeCFG: Fix broken backedge detection"Nicolai Haehnle2018-01-241-28/+82
| | | | | | | | | | | It causes regressions in various OpenGL test suites. Keep the test cases introduced by r321751 as XFAIL, and add a test case for the regression. Change-Id: I90b4cc354f68cebe5fcef1f2422dc8fe1c6d3514 Bugzilla: https://bugs.llvm.org/show_bug.cgi?id=36015 llvm-svn: 323355
* StructurizeCFG: Fix broken backedge detectionMatt Arsenault2018-01-031-82/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The work order was changed in r228186 from SCC order to RPO with an arbitrary sorting function. The sorting function attempted to move inner loop nodes earlier. This was was apparently relying on an assumption that every block in a given loop / the same loop depth would be seen before visiting another loop. In the broken testcase, a block outside of the loop was encountered before moving onto another block in the same loop. The testcase would then structurize such that one blocks unconditional successor could never be reached. Revert to plain RPO for the analysis phase. This fixes detecting edges as backedges that aren't really. The processing phase does use another visited set, and I'm unclear on whether the order there is as important. An arbitrary order doesn't work, and triggers some infinite loops. The reversed RPO list seems to work and is closer to the order that was used before, minus the arbitary custom sorting. A few of the changed tests now produce smaller code, and a few are slightly worse looking. llvm-svn: 321751
* StructurizeCFG: Use phi iterator rangeMatt Arsenault2017-12-291-8/+2
| | | | llvm-svn: 321568
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-201-19/+41
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 316241
* fix trivial typos; NFCHiroshi Inoue2017-07-091-1/+1
| | | | | | sucessor -> successor llvm-svn: 307488
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* Revert "StructurizeCFG: Directly invert cmp instructions"Matt Arsenault2017-04-241-12/+2
| | | | | | | | This reverts commit r300732. This breaks a few tests. I think the problem is related to adding more uses of the condition that don't yet exist at this point. llvm-svn: 301242
* StructurizeCFG: Directly invert cmp instructionsMatt Arsenault2017-04-191-2/+12
| | | | | | | | | | | | | | | | The most common case for a branch condition is a single use compare. Directly invert the branch predicate rather than adding a lot of xor i1 true which the DAG will have to fold later. This produces nicer to read structurizer output. This produces some random changes in codegen due to the DAG swapping branch conditions itself, and then does a poor job of dealing with those inverts. llvm-svn: 300732
* [StructurizeCfg] Update dominator info.Serge Pavlov2017-01-101-0/+1
| | | | | | | | | | | | | | 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
* [StructurizeCFG] Fix infinite loop in rebuildSSA.Justin Lebar2016-11-291-1/+4
| | | | | | | | | Michel Dänzer reported that r288051, "[StructurizeCFG] Use range-based for loops", introduced a bug into rebuildSSA, wherein we were iterating over an instruction's use list while modifying it, without taking care to do this correctly. llvm-svn: 288200
* [StructurizeCFG] Use range-based for loops.Justin Lebar2016-11-281-72/+51
| | | | | | | | | | Reviewers: arsenm Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D27000 llvm-svn: 288051
* [StructurizeCFG] Refactor NearestCommonDominator.Justin Lebar2016-11-281-56/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: As far as I can tell, doing our own computations in NearestCommonDominator is a false optimization -- DomTree will build up what appears to be exactly this data when it decides it's worthwhile. Moreover, by building the cache ourselves, we cannot take advantage of the cache that the domtree might have available. In addition, I am not convinced of the correctness of the original code. In particular, setting ResultIndex = 1 on the first addBlock instead of setting it to 0 is quite fishy. Similarly, it's not clear to me that setting IndexMap[Node] = 0 for every node as we walk up the tree finding a common parent is correct. But rather than ponder over these questions, I'd rather just make the code do the obviously-correct thing. This patch also changes the NearestCommonDominator API a bit, improving the names and getting rid of the boolean parameter in addBlock -- see http://jlebar.com/2011/12/16/Boolean_parameters_to_API_functions_considered_harmful..html Reviewers: arsenm Subscribers: aemerson, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26998 llvm-svn: 288050
* [StructurizeCFG] Refactor OrderNodes.Justin Lebar2016-11-221-12/+6
| | | | | | | | | | | Summary: No need to copy the RPOT vector before using it. Switch from std::map to SmallDenseMap. Get rid of an unused variable (TempVisited). Get rid of a typedef, RNVector, which is now used only once. Differential Revision: https://reviews.llvm.org/D26997 llvm-svn: 287721
* [StructurizeCFG] Add whitespace in getAnalysisUsage.Justin Lebar2016-11-221-0/+1
| | | | | | | | | | | | | | | Summary: "addRequired" and "addPreserved" look very similar when squished up next to each other -- without the newline this code looked to me like it was addRequired'ing DominatorTreeWrapperPass twice. Reviewers: arsenm Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26996 llvm-svn: 287720
* [StructurizeCFG] Remove unnecessary "using" in class.Justin Lebar2016-11-221-1/+0
| | | | | | | | | | Reviewers: arsenm Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26995 llvm-svn: 287719
* [StructurizeCFG] Merge the two constructors into one.Justin Lebar2016-11-221-7/+2
| | | | | | | | | | Reviewers: arsenm Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26994 llvm-svn: 287718
* [StructurizeCFG] Use a for-each loop instead of iterators in runOnRegion.Justin Lebar2016-11-221-4/+3
| | | | | | | | | | | | Summary: Reviewers: arsenm Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26993 llvm-svn: 287717
* [StructurizeCFG] Make hasOnlyUniformBranches a non-member function.Justin Lebar2016-11-221-7/+5
| | | | | | | | | | | | Summary: Lets us get rid of one member variable too. Reviewers: arsenm Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26992 llvm-svn: 287716
* Fix spelling mistakes in Transforms comments. NFC.Simon Pilgrim2016-11-201-1/+1
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287488
* Use StringRef in Pass/PassManager APIs (NFC)Mehdi Amini2016-10-011-3/+1
| | | | llvm-svn: 283004
* Use the range variant of find instead of unpacking begin/endDavid Majnemer2016-08-111-1/+1
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278433
* StructurizeCFG: Fix inverting constantexpr conditionsMatt Arsenault2016-07-151-8/+2
| | | | llvm-svn: 275626
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-15/+11
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* Switch more loops to be range-basedDavid Majnemer2016-06-241-8/+8
| | | | | | | This makes the code a little more concise, no functional change is intended. llvm-svn: 273644
* Avoid duplicated map lookups. No functionality change intended.Benjamin Kramer2016-06-171-7/+3
| | | | llvm-svn: 273030
* [StructurizeCFG] Annotate branches that were treated as uniformNicolai Haehnle2016-04-141-0/+15
| | | | | | | | | | | | | | | | | | | Summary: This fully solves the problem where the StructurizeCFG pass does not consider the same branches as uniform as the SIAnnotateControlFlow pass. The patch in D19013 helps with this problem, but is not sufficient (and, interestingly, causes a "regression" with one of the existing test cases). No tests included here, because tests in D19013 already cover this. Reviewers: arsenm, tstellarAMD Subscribers: arsenm, llvm-commits Differential Revision: http://reviews.llvm.org/D19018 llvm-svn: 266346
* StructurizeCFG: Initialize SkipUniformRegions in the default constructorTom Stellard2016-02-101-1/+1
| | | | | | This should fix some random bot failures caused by r260336. llvm-svn: 260342
* StructurizeCFG: Add an option for skipping regions with only uniform branchesTom Stellard2016-02-101-3/+38
| | | | | | | | | | | | | | Summary: Tests for this will be added once the AMDGPU backend enables this option. Reviewers: arsenm Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16602 llvm-svn: 260336
* Scalar: Remove remaining ilist iterator implicit conversionsDuncan P. N. Exon Smith2015-10-131-2/+2
| | | | | | | | | | | | | | | | | | | Remove remaining `ilist_iterator` implicit conversions from LLVMScalarOpts. This change exposed some scary behaviour in lib/Transforms/Scalar/SCCP.cpp around line 1770. This patch changes a call from `Function::begin()` to `&Function::front()`, since the return was immediately being passed into another function that takes a `Function*`. `Function::front()` started to assert, since the function was empty. Note that `Function::end()` does not point at a legal `Function*` -- it points at an `ilist_half_node` -- so the other function was getting garbage before. (I added the missing check for `Function::isDeclaration()`.) Otherwise, no functionality change intended. llvm-svn: 250211
* Convert a bunch of loops to foreach. NFC.Pete Cooper2015-08-061-6/+2
| | | | | | | | After r244074, we now have a successors() method to iterate over all the successors of a TerminatorInst. This commit changes a bunch of eligible loops to use it. llvm-svn: 244260
* Change range-based for-loops to be -Wrange-loop-analysis clean.Richard Trieu2015-04-151-1/+1
| | | | | | No functionality change. llvm-svn: 234963
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-1/+2
| | | | llvm-svn: 232998
* StructurizeCFG: Remove obsolete fix for loop backedge detectionTom Stellard2015-02-041-1/+1
| | | | | | | This is no longer needed now that we are using a reverse post-order traversal. llvm-svn: 228187
* StructurizeCFG: Use a reverse post-order traversalTom Stellard2015-02-041-4/+64
| | | | | | | | | | | | | | We were previously doing a post-order traversal and operating on the list in reverse, however this would occasionaly cause backedges for loops to be visited before some of the other blocks in the loop. We know use a reverse post-order traversal, which avoids this issue. The reverse post-order traversal is not completely ideal, so we need to manually fixup the list to ensure that inner loop backedges are visited before outer loop backedges. llvm-svn: 228186
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-2/+2
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* StructurizeCFG: Use LoopInfo analysis for better loop detectionTom Stellard2014-12-031-1/+6
| | | | | | | | We were assuming that each back-edge in a region represented a unique loop, which is not always the case. We need to use LoopInfo to correctly determine which back-edges are loops. llvm-svn: 223199
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-12/+20
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-20/+12
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* Templatify RegionInfo so it works on MachineBasicBlocksMatt Arsenault2014-07-191-3/+3
| | | | llvm-svn: 213456
* Use range forMatt Arsenault2014-05-191-4/+1
| | | | llvm-svn: 209147
* SCC: Change clients to use const, NFCDuncan P. N. Exon Smith2014-04-251-1/+1
| | | | | | | | | | It's fishy to be changing the `std::vector<>` owned by the iterator, and no one actual does it, so I'm going to remove the ability in a subsequent commit. First, update the users. <rdar://problem/14292693> llvm-svn: 207252
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-8/+9
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-17/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-4/+4
| | | | | | class. llvm-svn: 202953
* [Modules] Move the LLVM IR pattern match header into the IR library, itChandler Carruth2014-03-041-1/+1
| | | | | | obviously is coupled to the IR. llvm-svn: 202818
OpenPOWER on IntegriCloud