summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [SimplifyCFG] Fix bootstrap failure after r280220James Molloy2016-08-311-5/+21
| | | | | | We check that a sinking candidate is used by only one PHI node during our legality checks. However for instructions that are used by other sinking candidates our heuristic is less conservative. This can result in a candidate actually being illegal when we come to sink it because of how we sunk a predecessor. Do the used-by-only-one-PHI checks again during sinking to ensure we don't crash. llvm-svn: 280228
* [SimplifyCFG] Add a workaround to fix PR30188James Molloy2016-08-311-0/+10
| | | | | | | | We're sinking stores, which is a good thing, but in the process creating selects for the store address operand, which SROA/Mem2Reg can't look through, which caused serious regressions. The real fix is in SROA, which I'll be looking into. llvm-svn: 280219
* [SimplifyCFG] Improve FoldValueComparisonIntoPredecessors to handle more casesJames Molloy2016-08-311-6/+20
| | | | | | | | | | | | | | | | | | | A very important case is not handled here: multiple arcs to a single block with a PHI. Consider: a: %1 = icmp %b, 1 br %1, label %c, label %e c: %2 = icmp %b, 2 br %2, label %d, label %e d: br %e e: phi [0, %a], [1, %c], [2, %d] FoldValueComparisonIntoPredecessors will refuse to fold this, as it doesn't know how to deal with two arcs to a common destination with different PHI values. The answer is obvious - just split all conflicting arcs. llvm-svn: 280218
* [SimplifyCFG] Handle tail-sinking of more than 2 incoming branchesJames Molloy2016-08-311-27/+89
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This was a real restriction in the original version of SinkIfThenCodeToEnd. Now it's been rewritten, the restriction can be lifted. As part of this, we handle a very common and useful case where one of the incoming branches is actually conditional. Consider: if (a) x(1); else if (b) x(2); This produces the following CFG: [if] / \ [x(1)] [if] | | \ | | \ | [x(2)] | \ | / [ end ] [end] has two unconditional predecessor arcs and one conditional. The conditional refers to the implicit empty 'else' arc. This same pattern can also be caused by an empty default block in a switch. We can't sink the call to x() down to end because no call to x() happens on the third incoming arc (assume that x() has sideeffects for the sake of argument; if something is safe to speculate we could indeed sink nevertheless but this cannot happen in the general case and causes many extra selects). We are now able to detect this case and split off the unconditional arcs to a common successor: [if] / \ [x(1)] [if] | | \ | | \ | [x(2)] | \ / | [sink.split] | \ / [ end ] Now we can sink the call to x() into %sink.split. This can cause significant code simplification in many testcases. llvm-svn: 280217
* [SimplifyCFG] Change the algorithm in SinkThenElseCodeToEndJames Molloy2016-08-311-86/+127
| | | | | | | | | | | | | | | | | | | | | | | | | r279460 rewrote this function to be able to handle more than two incoming edges and took pains to ensure this didn't regress anything. This time we change the logic for determining if an instruction should be sunk. Previously we used a single pass greedy algorithm - sink instructions until one requires more than one PHI node or we run out of instructions to sink. This had the problem that sinking instructions that had non-identical but trivially the same operands needed extra logic so we sunk them aggressively. For example: %a = load i32* %b %d = load i32* %b %c = gep i32* %a, i32 0 %e = gep i32* %d, i32 1 Sinking %c and %e would naively require two PHI merges as %a != %d. But the loads are obviously equivalent (and maybe can't be hoisted because there is no common predecessor). This is why we implemented the fairly complex function areValuesTriviallySame(), to look through trivial differences like this. However it's just not clever enough. Instead, throw areValuesTriviallySame away, use pointer equality to check equivalence of operands and switch to a two-stage algorithm. In the "scan" stage, we look at every sinkable instruction in isolation from end of block to front. If it's sinkable, we keep track of all operands that required PHI merging. In the "sink" stage, we iteratively sink the last non-terminator in the source blocks. But when calculating how many PHIs are actually required to be inserted (to work out if we should stop or not) we remove any values that have already been sunk from the set of PHI-merges required, which allows us to be more aggressive. This turns an algorithm with potentially recursive lookahead (looking through GEPs, casts, loads and any other instruction potentially not CSE'd) to two linear scans. llvm-svn: 280216
* [SimplifyCFG] Tail-merge calls with sideeffectsJames Molloy2016-08-311-7/+3
| | | | | | | | | | | | | This was deliberately disabled during my rewrite of SinkIfThenToEnd to keep behaviour at least vaguely consistent with the previous version and keep it as close to NFC as I could. There's no real reason not to merge sideeffect calls though, so let's do it! Small fixup along the way to ensure we don't create indirect calls. Should fix PR28964. llvm-svn: 280215
* [SimplifyCFG] Properly CSE metadata in SinkThenElseCodeToEndJames Molloy2016-08-301-0/+5
| | | | | | This was missing, meaning the metadata in sunk instructions was potentially bogus and could cause miscompiles. llvm-svn: 280072
* [SimplifyCFG] Hoisting invalidates metadataDavid Majnemer2016-08-291-2/+8
| | | | | | | | | We forgot to remove optimization metadata when performing hosting during FoldTwoEntryPHINode. This fixes PR29163. llvm-svn: 279980
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-221-150/+236
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | [Recommitting now an unrelated assertion in SROA is sorted out] The new version has several advantages: 1) IMSHO it's more readable and neater 2) It handles loads and stores properly 3) It can handle any number of incoming blocks rather than just two. I'll be taking advantage of this in a followup patch. With this change we can now finally sink load-modify-store idioms such as: if (a) return *b += 3; else return *b += 4; => %z = load i32, i32* %y %.sink = select i1 %a, i32 5, i32 7 %b = add i32 %z, %.sink store i32 %b, i32* %y ret i32 %b When this works for switches it'll be even more powerful. Round 4. This time we should handle all instructions correctly, and not replace any operands that need to be constant with variables. This was really hard to determine safely, so the helper function should be put into the Instruction API. I'll do that as a followup. llvm-svn: 279460
* Revert "[SimplifyCFG] Rewrite SinkThenElseCodeToEnd"James Molloy2016-08-221-236/+150
| | | | | | This reverts commit r279443. It caused buildbot failures. llvm-svn: 279447
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-221-150/+236
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The new version has several advantages: 1) IMSHO it's more readable and neater 2) It handles loads and stores properly 3) It can handle any number of incoming blocks rather than just two. I'll be taking advantage of this in a followup patch. With this change we can now finally sink load-modify-store idioms such as: if (a) return *b += 3; else return *b += 4; => %z = load i32, i32* %y %.sink = select i1 %a, i32 5, i32 7 %b = add i32 %z, %.sink store i32 %b, i32* %y ret i32 %b When this works for switches it'll be even more powerful. Round 4. This time we should handle all instructions correctly, and not replace any operands that need to be constant with variables. This was really hard to determine safely, so the helper function should be put into the Instruction API. I'll do that as a followup. llvm-svn: 279443
* Revert "[SimplifyCFG] Rewrite SinkThenElseCodeToEnd"Reid Kleckner2016-08-191-210/+150
| | | | | | | This reverts commit r279229. It breaks intrinsic function calls in diamonds. llvm-svn: 279313
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-191-150/+210
| | | | | | | | | | | | | | | | | | | | | | | | | | The new version has several advantages: 1) IMSHO it's more readable and neater 2) It handles loads and stores properly 3) It can handle any number of incoming blocks rather than just two. I'll be taking advantage of this in a followup patch. With this change we can now finally sink load-modify-store idioms such as: if (a) return *b += 3; else return *b += 4; => %z = load i32, i32* %y %.sink = select i1 %a, i32 5, i32 7 %b = add i32 %z, %.sink store i32 %b, i32* %y ret i32 %b When this works for switches it'll be even more powerful. llvm-svn: 279229
* SimplifyCFG: Avoid dereferencing end()Duncan P. N. Exon Smith2016-08-161-1/+4
| | | | | | | | When comparing a User* to a BasicBlock::iterator in passingValueIsAlwaysUndefined, don't dereference the iterator in case it is end(). llvm-svn: 278872
* Revert "[SimplifyCFG] Rewrite SinkThenElseCodeToEnd"Reid Kleckner2016-08-151-207/+150
| | | | | | | | | This reverts commit r278660. It causes downstream assertion failure in InstCombine on shuffle instructions. Comes up in __mm_swizzle_epi32. llvm-svn: 278672
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-151-150/+207
| | | | | | | | | | | | | | | | | | | | | | | | | | The new version has several advantages: 1) IMSHO it's more readable and neater 2) It handles loads and stores properly 3) It can handle any number of incoming blocks rather than just two. I'll be taking advantage of this in a followup patch. With this change we can now finally sink load-modify-store idioms such as: if (a) return *b += 3; else return *b += 4; => %z = load i32, i32* %y %.sink = select i1 %a, i32 5, i32 7 %b = add i32 %z, %.sink store i32 %b, i32* %y ret i32 %b When this works for switches it'll be even more powerful. llvm-svn: 278660
* Fixed typo.David L Kreitzer2016-08-121-1/+1
| | | | llvm-svn: 278565
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-1/+1
| | | | | | No functionality change is intended. llvm-svn: 278417
* [SimplifyCFG] Make range reduction code deterministic.Benjamin Kramer2016-08-051-2/+3
| | | | | | | | | | | This generated IR based on the order of evaluation, which is different between GCC and Clang. With that in mind you get bootstrap miscompares if you compare a Clang built with GCC-built Clang vs. Clang built with Clang-built Clang. Diagnosing that made my head hurt. This also reverts commit r277337, which "fixed" the test case. llvm-svn: 277820
* Minor code cleanups. NFC.Junmo Park2016-08-021-2/+2
| | | | llvm-svn: 277415
* [SimplifyCFG] Fix nasty RAUW bug from r277325James Molloy2016-08-011-3/+4
| | | | | | | | | | | | | | | Using RAUW was wrong here; if we have a switch transform such as: 18 -> 6 then 6 -> 0 If we use RAUW, while performing the second transform the *transformed* 6 from the first will be also replaced, so we end up with: 18 -> 0 6 -> 0 Found by clang stage2 bootstrap; testcase added. llvm-svn: 277332
* [SimplifyCFG] Range reduce switchesJames Molloy2016-08-011-0/+106
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If a switch is sparse and all the cases (once sorted) are in arithmetic progression, we can extract the common factor out of the switch and create a dense switch. For example: switch (i) { case 5: ... case 9: ... case 13: ... case 17: ... } can become: if ( (i - 5) % 4 ) goto default; switch ((i - 5) / 4) { case 0: ... case 1: ... case 2: ... case 3: ... } or even better: switch ( ROTR(i - 5, 2) { case 0: ... case 1: ... case 2: ... case 3: ... } The division and remainder operations could be costly so we only do this if the factor is a power of two, and emit a right-rotate instead of a divide/remainder sequence. Dense switches can be lowered significantly better than sparse switches and can even be transformed into lookup tables. llvm-svn: 277325
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-11/+8
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* [SimplifyCFG] Replace calls to null/undef with unreachableDavid Majnemer2016-06-251-1/+5
| | | | | | | Calling null is undefined behavior, a call to undef can be trivially treated as a call to null. llvm-svn: 273776
* Reinstate r273711David Majnemer2016-06-251-4/+9
| | | | | | | | | | r273711 was reverted by r273743. The inliner needs to know about any call sites in the inlined function. These were obscured if we replaced a call to undef with an undef but kept the call around. This fixes PR28298. llvm-svn: 273753
* Revert r273711, it caused PR28298.Nico Weber2016-06-241-9/+4
| | | | llvm-svn: 273743
* SimplifyInstruction does not imply DCEDavid Majnemer2016-06-241-4/+9
| | | | | | | We cannot remove an instruction with no uses just because SimplifyInstruction succeeds. It may have side effects. llvm-svn: 273711
* Switch more loops to be range-basedDavid Majnemer2016-06-241-10/+10
| | | | | | | This makes the code a little more concise, no functional change is intended. llvm-svn: 273644
* Teaching SimplifyCFG to recognize the Or-Mask trick that InstCombine uses toChuang-Yu Cheng2016-06-241-0/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | reduce the number of comparisons. Specifically, InstCombine can turn: (i == 5334 || i == 5335) into: ((i | 1) == 5335) SimplifyCFG was already able to detect the pattern: (i == 5334 || i == 5335) to: ((i & -2) == 5334) This patch supersedes D21315 and resolves PR27555 (https://llvm.org/bugs/show_bug.cgi?id=27555). Thanks to David and Chandler for the suggestions! Author: Thomas Jablin (tjablin) Reviewers: majnemer chandlerc halfdan cycheng http://reviews.llvm.org/D21397 llvm-svn: 273639
* Use m_APInt in SimplifyCFGChuang-Yu Cheng2016-06-171-5/+5
| | | | | | | | | | | Switch from m_Constant to m_APInt per David's request. NFC. Author: Thomas Jablin (tjablin) Reviewers: majnemer cycheng http://reviews.llvm.org/D21440 llvm-svn: 272977
* SimplifyCFG is able to detect the pattern:Chuang-Yu Cheng2016-06-161-4/+42
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (i == 5334 || i == 5335) to: ((i & -2) == 5334) This transformation has some incorrect side conditions. Specifically, the transformation is only applied when the right-hand side constant (5334 in the example) is a power of two not equal and not equal to the negated mask. These side conditions were added in r258904 to fix PR26323. The correct side condition is that: ((Constant & Mask) == Constant)[(5334 & -2) == 5334]. It's a little bit hard to see why these transformations are correct and what the side conditions ought to be. Here is a CVC3 program to verify them for 64-bit values: ONE : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63); x : BITVECTOR(64); y : BITVECTOR(64); z : BITVECTOR(64); mask : BITVECTOR(64) = BVSHL(ONE, z); QUERY( (y & ~mask = y) => ((x & ~mask = y) <=> (x = y OR x = (y | mask))) ); Please note that each pattern must be a dual implication (<--> or iff). One directional implication can create spurious matches. If the implication is only one-way, an unsatisfiable condition on the left side can imply a satisfiable condition on the right side. Dual implication ensures that satisfiable conditions are transformed to other satisfiable conditions and unsatisfiable conditions are transformed to other unsatisfiable conditions. Here is a concrete example of a unsatisfiable condition on the left implying a satisfiable condition on the right: mask = (1 << z) (x & ~mask) == y --> (x == y || x == (y | mask)) Substituting y = 3, z = 0 yields: (x & -2) == 3 --> (x == 3 || x == 2) The version of this code before r258904 had no side-conditions and incorrectly justified itself in comments through one-directional implication. Thanks to Chandler for the suggestion! Author: Thomas Jablin (tjablin) Reviewers: chandlerc majnemer hfinkel cycheng http://reviews.llvm.org/D21417 llvm-svn: 272873
* IR: Introduce local_unnamed_addr attribute.Peter Collingbourne2016-06-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If a local_unnamed_addr attribute is attached to a global, the address is known to be insignificant within the module. It is distinct from the existing unnamed_addr attribute in that it only describes a local property of the module rather than a global property of the symbol. This attribute is intended to be used by the code generator and LTO to allow the linker to decide whether the global needs to be in the symbol table. It is possible to exclude a global from the symbol table if three things are true: - This attribute is present on every instance of the global (which means that the normal rule that the global must have a unique address can be broken without being observable by the program by performing comparisons against the global's address) - The global has linkonce_odr linkage (which means that each linkage unit must have its own copy of the global if it requires one, and the copy in each linkage unit must be the same) - It is a constant or a function (which means that the program cannot observe that the unique-address rule has been broken by writing to the global) Although this attribute could in principle be computed from the module contents, LTO clients (i.e. linkers) will normally need to be able to compute this property as part of symbol resolution, and it would be inefficient to materialize every module just to compute it. See: http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160509/356401.html http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160516/356738.html for earlier discussion. Part of the fix for PR27553. Differential Revision: http://reviews.llvm.org/D20348 llvm-svn: 272709
* [SimplifyCFG] Don't kill empty cleanuppads with multiple usesDavid Majnemer2016-06-041-0/+5
| | | | | | | | | | | | | | | | | A basic block could contain: %cp = cleanuppad [] cleanupret from %cp unwind to caller This basic block is empty and is thus a candidate for removal. However, there can be other uses of %cp outside of this basic block. This is only possible in unreachable blocks. Make our transform more correct by checking that the pad has a single user before removing the BB. This fixes PR28005. llvm-svn: 271816
* [SimplifyCFG] Remove cleanuppads which are empty except for calls to ↵David Majnemer2016-05-211-5/+17
| | | | | | | | | | | | | lifetime.end A cleanuppad is not cheap, they turn into many instructions and result in additional spills and fills. It is not worth keeping a cleanuppad around if all it does is hold a lifetime.end instruction. N.B. We first try to merge the cleanuppad with another cleanuppad to avoid dropping the lifetime and debug info markers. llvm-svn: 270314
* [SimplifyCFG] eliminate switch cases based on known range of switch conditionSanjay Patel2016-05-201-4/+10
| | | | | | | | | | | | This was noted in PR24766: https://llvm.org/bugs/show_bug.cgi?id=24766#c2 We may not know whether the sign bit(s) are zero or one, but we can still optimize based on knowing that the sign bit is repeated. Differential Revision: http://reviews.llvm.org/D20275 llvm-svn: 270222
* Follow-up patch of http://reviews.llvm.org/D19948 to handle missing profiles ↵Dehao Chen2016-05-181-18/+32
| | | | | | | | | | | | | | when simplifying CFG. Summary: Set default branch weight to 1:1 if one of the branch has profile missing when simplifying CFG. Reviewers: spatel, davidxl Subscribers: danielcdh, llvm-commits Differential Revision: http://reviews.llvm.org/D20307 llvm-svn: 269995
* clang-format SimplifyCFG.cpp.Dehao Chen2016-05-181-581/+625
| | | | llvm-svn: 269974
* use range-loops; NFCISanjay Patel2016-05-131-7/+7
| | | | llvm-svn: 269471
* Propagate branch metadata when some branch probability is missing.Dehao Chen2016-05-101-5/+13
| | | | | | | | | | | | Summary: In sample profile, some branches may have profile missing due to profile inaccuracy. We want existing branch probability still valid after propagation. Reviewers: hfinkel, davidxl, spatel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D19948 llvm-svn: 269137
* [SimplifyCFG] propagate branch metadata when creating select (retry r268550 ↵Sanjay Patel2016-05-061-1/+21
| | | | | | | | | | | | | | | | / r268751 with possible fix) Retrying r268550/r268751 which were reverted at r268577/r268765 due a memory sanitizer failure. I have not been able to reproduce that failure, but I've taken another guess at fixing the problem in this version of the patch and will watch for another failure. Original commit message: Unlike earlier similar fixes, we need to recalculate the branch weights in this case. Differential Revision: http://reviews.llvm.org/D19674 llvm-svn: 268767
* revert r268751 - caused same failures on msan botSanjay Patel2016-05-061-24/+9
| | | | llvm-svn: 268765
* [SimplifyCFG] propagate branch metadata when creating select (retry r268550 ↵Sanjay Patel2016-05-061-9/+24
| | | | | | | | | | | | | | | | with possible fix) Retrying r268550 which was reverted at r268577 due a memory sanitizer failure. I have not been able to reproduce that failure, but I've taken a guess at fixing the problem in this version of the patch and will watch for another failure. Original commit message: Unlike earlier similar fixes, we need to recalculate the branch weights in this case. Differential Revision: http://reviews.llvm.org/D19674 llvm-svn: 268751
* [SimplifyCFG] Prefer a simplification based on a dominating condition.Chad Rosier2016-05-061-20/+24
| | | | | | | Rather than merge two branches with a common destination. Differential Revision: http://reviews.llvm.org/D19743 llvm-svn: 268735
* Revert "[SimplifyCFG] propagate branch metadata when creating select"Vitaly Buka2016-05-041-28/+14
| | | | | | | | | | | | MemorySanitizer: use-of-uninitialized-value 0x4910e47 in count /mnt/b/sanitizer-buildbot2/sanitizer-x86_64-linux-bootstrap/build/llvm/include/llvm/Support/MathExtras.h:159:12 0x4910e47 in countLeadingZeros<unsigned long> /mnt/b/sanitizer-buildbot2/sanitizer-x86_64-linux-bootstrap/build/llvm/include/llvm/Support/MathExtras.h:183 0x4910e47 in FitWeights /mnt/b/sanitizer-buildbot2/sanitizer-x86_64-linux-bootstrap/build/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:855 0x4910e47 in SimplifyCondBranchToCondBranch /mnt/b/sanitizer-buildbot2/sanitizer-x86_64-linux-bootstrap/build/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:2895 This reverts commit 609f4dd4bf3bc735c8c047a4d4b0a8e9e4d202e2. llvm-svn: 268577
* [SimplifyCFG] propagate branch metadata when creating selectSanjay Patel2016-05-041-14/+28
| | | | | | | | | Unlike earlier similar fixes, we need to recalculate the branch weights in this case. Differential Revision: http://reviews.llvm.org/D19674 llvm-svn: 268550
* [SimplifyCFG] isSafeToSpeculateStore now ignores debug infoHans Wennborg2016-05-041-2/+6
| | | | | | | | | | | | | | | This patch fixes PR27615. @llvm.dbg.value instructions no longer count towards the maximum number of instructions to look back at in the instruction list when searching for a store instruction. This should make the output consistent between debug and non-debug build. Patch by Henric Karlsson <henric.karlsson@ericsson.com>! Differential Revision: http://reviews.llvm.org/D19912 llvm-svn: 268512
* Revert "[SimplifyCFG] Extend TryToSimplifyUncondBranchFromEmptyBlock for ↵Reid Kleckner2016-05-021-5/+4
| | | | | | | | | | | empty block including lifetime intrinsics" This reverts commit r268254. This change causes assertion failures while building Chromium. Reduced test case coming soon. llvm-svn: 268288
* [SimplifyCFG] Extend TryToSimplifyUncondBranchFromEmptyBlock for empty block ↵Hans Wennborg2016-05-021-4/+5
| | | | | | | | | | | | | | | | | | including lifetime intrinsics Make it possible that TryToSimplifyUncondBranchFromEmptyBlock merges empty basic block including lifetime intrinsics as well as phi nodes and unconditional branch into its successor or predecessor(s). If successor of empty block has single predecessor, all contents including lifetime intrinsics are sinked into the successor. Otherwise, they are hoisted into its predecessor(s) and then merged into the predecessor(s). Patch by Josh Yoon <josh.yoon@samsung.com>! Differential Revision: http://reviews.llvm.org/D19257 llvm-svn: 268254
* [SimplifyCFG] propagate branch metadata when creating selectSanjay Patel2016-04-271-2/+2
| | | | | | | | There's no existing test for this path, and I don't know how to expose it in a regression test, but I'm assuming there's some reason this path exists. llvm-svn: 267813
* [SimplifyCFG] propagate branch metadata when creating selectSanjay Patel2016-04-261-1/+1
| | | | llvm-svn: 267624
OpenPOWER on IntegriCloud