summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner2019-11-141-0/+1
| | | | | These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [StructurizeCFG] Enable -structurizecfg-relaxed-uniform-regions by defaultTim Renouf2019-08-061-1/+1
| | | | | | | | | | | D62198 introduced an option to relax the checks for hasOnlyUniformBranches. This commit turns the option on by default, for better code generation in some cases in AMDGPU. Differential Revision: https://reviews.llvm.org/D63198 Change-Id: I9cbff002a1e74d3b7eb96b4192dc8129936d537d llvm-svn: 368042
* PHINode: introduce setIncomingValueForBlock() function, and use it.Whitney Tsang2019-06-171-5/+2
| | | | | | | | | | | | | | | | Summary: There is PHINode::getBasicBlockIndex() and PHINode::setIncomingValue() but no function to replace incoming value for a specified BasicBlock* predecessor. Clearly, there are a lot of places that could use that functionality. Reviewer: craig.topper, lebedev.ri, Meinersbur, kbarton, fhahn Reviewed By: Meinersbur, fhahn Subscribers: fhahn, hiraditya, zzheng, jsji, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D63338 llvm-svn: 363566
* StructurizeCFG: Relax uniformity checks.Neil Henning2019-05-241-3/+30
| | | | | | | | | | | | | | | This change relaxes the checks for hasOnlyUniformBranches such that our region is uniform if: 1. All conditional branches that are direct children are uniform. 2. And either: a. All sub-regions are uniform. b. There is one or less conditional branches among the direct children. Differential Revision: https://reviews.llvm.org/D62198 llvm-svn: 361610
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-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
* StructurizeCFG: Simplify inserted PHI nodesNicolai Haehnle2018-10-171-1/+23
| | | | | | | | | | | | | | | Summary: This improves subsequent divergence analysis in some cases. Change-Id: I5e95e7ec7fd3fa80d414d1a53a02fea23e3d67d3 Reviewers: arsenm, rampitec Subscribers: jvesely, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D53316 llvm-svn: 344697
* [TI removal] Make variables declared as `TerminatorInst` and initializedChandler Carruth2018-10-151-1/+1
| | | | | | | | | | | | | by `getTerminator()` calls instead be declared as `Instruction`. This is the biggest remaining chunk of the usage of `getTerminator()` that insists on the narrow type and so is an easy batch of updates. Several files saw more extensive updates where this would cascade to requiring API updates within the file to use `Instruction` instead of `TerminatorInst`. All of these were trivial in nature (pervasively using `Instruction` instead just worked). llvm-svn: 344502
* revert changes from r342722Sameer Sahasrabuddhe2018-09-211-1/+0
| | | | | | | | | "[AMDGPU] lower-switch in preISel as a workaround for legacy DA" This broke regression tests. The first breakage was noticed here: http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/23549 llvm-svn: 342743
* [AMDGPU] lower-switch in preISel as a workaround for legacy DASameer Sahasrabuddhe2018-09-211-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: The default target of the switch instruction may sometimes be an "unreachable" block, when it is guaranteed that one of the cases is always taken. The dominator tree concludes that such a switch instruction does not have an immediate post dominator. This confuses divergence analysis, which is unable to propagate sync dependence to the targets of the switch instruction. As a workaround, the AMDGPU target now invokes lower-switch as a preISel pass. LowerSwitch is designed to handle the unreachable default target correctly, allowing the divergence analysis to locate the correct immediate dominator of the now-lowered switch. Reviewers: arsenm, nhaehnle Reviewed By: nhaehnle Subscribers: kzhuravl, jvesely, wdng, nhaehnle, yaxunl, dstuttard, tpr, t-tye, llvm-commits, simoll Differential Revision: https://reviews.llvm.org/D52221 llvm-svn: 342722
* [NFC] Rename the DivergenceAnalysis to LegacyDivergenceAnalysisNicolai Haehnle2018-08-301-6/+6
| | | | | | | | | | | | | | | | | | | | Summary: This is patch 1 of the new DivergenceAnalysis (https://reviews.llvm.org/D50433). The purpose of this patch is to free up the name DivergenceAnalysis for the new generic implementation. The generic implementation class will be shared by specialized divergence analysis classes. Patch by: Simon Moll Reviewed By: nhaehnle Subscribers: jvesely, jholewinski, arsenm, nhaehnle, mgorny, jfb, llvm-commits Differential Revision: https://reviews.llvm.org/D50434 Change-Id: Ie8146b11be2c50d5312f30e11c7a3036a15b48cb llvm-svn: 341071
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-06-141-1/+1
| | | | llvm-svn: 334687
* StructurizeCFG: Adjust the loop depth for a subregion to order the nodes ↵Changpeng Fang2018-05-231-7/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | correctly Summary: StructurizeCFG::orderNodes basically uses a reverse post-order (RPO) traversal of the region list to get the order. The only problem with it is that sometimes backedges for outer loops will be visited before backedges for inner loops. To solve this problem, a loop depth based approach has been used to make sure all blocks in this loop has been visited before moving on to outer loop. However, we found a problem for a SubRegion which is a loop itself: --> BB1 --> BB2 --> BB3 --> In this case, BB2 is a SubRegion (loop), and thus its loopdepth is different than that of BB1 and BB3. This fact will lead BB2 to be placed in the wrong order. In this work, we treat the SubRegion as a special case and use its exit block to determine the loop and its depth to guard the sorting. Reviewers: arsenm, jlebar Differential Revision: https://reviews.llvm.org/D46912 llvm-svn: 333111
* StructurizeCFG: fix inverting conditionsMarek Olsak2018-05-151-2/+3
| | | | | | | | | | | | | | | | Author: Samuel Pitoiset Without this patch, it appears to me that we are selecting the wrong operand when inverting conditions. In the attached test, it will select %tmp3 instead of %tmp4. To fix it, just use 'A' as everywhere. This fixes a regression introduced by "[PatternMatch] define m_Not using m_Xor and cst_pred_ty" https://reviews.llvm.org/D46351 llvm-svn: 332403
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-7/+8
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Remove @brief commands from doxygen comments, too.Adrian Prantl2018-05-011-1/+1
| | | | | | | | | | | | | | | | | This is a follow-up to r331272. We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\@brief'); do perl -pi -e 's/\@brief //g' $i & done https://reviews.llvm.org/D46290 llvm-svn: 331275
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-20/+20
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* 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
OpenPOWER on IntegriCloud