summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/SimplifyCFG
Commit message (Collapse)AuthorAgeFilesLines
...
* [SimplifyCFG] Properly CSE metadata in SinkThenElseCodeToEndJames Molloy2016-08-301-0/+37
| | | | | | 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-0/+31
| | | | | | | | | We forgot to remove optimization metadata when performing hosting during FoldTwoEntryPHINode. This fixes PR29163. llvm-svn: 279980
* [Constant] remove fdiv and frem from canTrap()Sanjay Patel2016-08-291-6/+3
| | | | | | | | | | | Assuming the default FP env, we should not treat fdiv and frem any differently in terms of trapping behavior than any other FP op. Ie, FP ops do not trap with the default FP env. This matches how we treat the fdiv/frem in IR with isSafeToSpeculativelyExecute() and in the backend after: https://reviews.llvm.org/rL279970 llvm-svn: 279973
* [SimplifyCFG] rename test file, regenerate checks, and add testSanjay Patel2016-08-292-41/+70
| | | | | | | The fdiv test shows a problem similar to: https://reviews.llvm.org/rL279970 llvm-svn: 279972
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-222-1/+231
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | [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-222-231/+1
| | | | | | This reverts commit r279443. It caused buildbot failures. llvm-svn: 279447
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-222-1/+231
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-192-203/+1
| | | | | | | This reverts commit r279229. It breaks intrinsic function calls in diamonds. llvm-svn: 279313
* [SimplifyCFG] Rewrite SinkThenElseCodeToEndJames Molloy2016-08-192-1/+203
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert "[SimplifyCFG] Rewrite SinkThenElseCodeToEnd"Reid Kleckner2016-08-152-179/+1
| | | | | | | | | 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-152-1/+179
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Actually, r277337 was fine. Just kill the DAGs that made the test allow ↵Benjamin Kramer2016-08-051-20/+20
| | | | | | nondeterminism. llvm-svn: 277821
* [SimplifyCFG] Make range reduction code deterministic.Benjamin Kramer2016-08-051-20/+20
| | | | | | | | | | | 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
* Fixed test check ordering issue on windows buildbotsSimon Pilgrim2016-08-011-20/+20
| | | | llvm-svn: 277337
* [SimplifyCFG] Fix nasty RAUW bug from r277325James Molloy2016-08-011-1/+27
| | | | | | | | | | | | | | | 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] Try and pacify buildbots after r277325James Molloy2016-08-011-8/+8
| | | | | | It looks like the two independent parts of the rotate operation (a lshr and shl) are being reordered on some bots. Add CHECK-DAGs to account for this. llvm-svn: 277329
* [SimplifyCFG] Range reduce switchesJames Molloy2016-08-011-0/+195
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert "[SimplifyCFG] Stop inserting calls to llvm.trap for UB"David Majnemer2016-06-253-0/+25
| | | | | | This reverts commit r273778, it seems to break UBSan :/ llvm-svn: 273779
* [SimplifyCFG] Stop inserting calls to llvm.trap for UBDavid Majnemer2016-06-253-25/+0
| | | | | | | | | | | | | | | | | SimplifyCFG had logic to insert calls to llvm.trap for two very particular IR patterns: stores and invokes of undef/null. While InstCombine canonicalizes certain undefined behavior IR patterns to stores of undef, phase ordering means that this cannot be relied upon in general. There are much better tools than llvm.trap: UBSan and ASan. N.B. I could be argued into reverting this change if a clear argument as to why it is important that we synthesize llvm.trap for stores, I'd be hard pressed to see why it'd be useful for invokes... llvm-svn: 273778
* [SimplifyCFG] Replace calls to null/undef with unreachableDavid Majnemer2016-06-251-0/+31
| | | | | | | Calling null is undefined behavior, a call to undef can be trivially treated as a call to null. llvm-svn: 273776
* Teaching SimplifyCFG to recognize the Or-Mask trick that InstCombine uses toChuang-Yu Cheng2016-06-241-0/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* SimplifyCFG is able to detect the pattern:Chuang-Yu Cheng2016-06-161-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (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
* [SimplifyCFG] Don't kill empty cleanuppads with multiple usesDavid Majnemer2016-06-041-0/+24
| | | | | | | | | | | | | | | | | 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-0/+31
| | | | | | | | | | | | | 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/+0
| | | | | | | | | | | | 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-37/+38
| | | | | | | | | | | | | | 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
* add test to show missing optimizationSanjay Patel2016-05-151-0/+37
| | | | llvm-svn: 269601
* regenerate checksSanjay Patel2016-05-151-10/+16
| | | | llvm-svn: 269596
* Propagate branch metadata when some branch probability is missing.Dehao Chen2016-05-101-1/+25
| | | | | | | | | | | | 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-8/+39
| | | | | | | | | | | | | | | | / 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-39/+8
| | | | llvm-svn: 268765
* [SimplifyCFG] propagate branch metadata when creating select (retry r268550 ↵Sanjay Patel2016-05-061-8/+39
| | | | | | | | | | | | | | | | 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-0/+48
| | | | | | | Rather than merge two branches with a common destination. Differential Revision: http://reviews.llvm.org/D19743 llvm-svn: 268735
* [ValueTracking] Improve isImpliedCondition for matching LHS and Imm RHSs.Chad Rosier2016-05-051-0/+123
| | | | llvm-svn: 268636
* Revert "[SimplifyCFG] propagate branch metadata when creating select"Vitaly Buka2016-05-041-39/+8
| | | | | | | | | | | | 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-8/+39
| | | | | | | | | 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-0/+68
| | | | | | | | | | | | | | | 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-232/+0
| | | | | | | | | | | 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-0/+232
| | | | | | | | | | | | | | | | | | 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
* add minimal test to show dropped metadataSanjay Patel2016-04-301-0/+28
| | | | llvm-svn: 268141
* remove the metadata added with r267827Sanjay Patel2016-04-301-14/+6
| | | | | | | We can demonstrate the 'select' bug and fix with a simpler test case. The merged weight values are already tested in another test. llvm-svn: 268139
* Update test to use FileCheckSanjay Patel2016-04-281-14/+41
| | | | | | Also, add some metadata to show what that currently looks like. llvm-svn: 267827
* [SimplifyCFG] propagate branch metadata when creating selectSanjay Patel2016-04-261-1/+28
| | | | llvm-svn: 267624
* [SimplifyCFG] Preserve !llvm.mem.parallel_loop_access when mergingHal Finkel2016-04-261-0/+55
| | | | | | | | When SimplifyCFG merges identical instructions from both sides of a diamond, it can preserve !llvm.mem.parallel_loop_access (as it does with most of the other metadata). There's no real data or control dependency change in this case. llvm-svn: 267515
* Add check for "branch_weights" with prof metadataSanjay Patel2016-04-251-0/+24
| | | | | | | While we're here, fix the comment and variable names to make it clear that these are raw weights, not percentages. llvm-svn: 267491
* Fix typo from r267432.Chad Rosier2016-04-251-2/+2
| | | | llvm-svn: 267436
* [ValueTracking] Add an additional test case for r266767 where one operand is ↵Chad Rosier2016-04-251-0/+24
| | | | | | a const. llvm-svn: 267432
* [ValueTracking] Improve isImpliedCondition when the dominating cond is false.Chad Rosier2016-04-251-0/+339
| | | | llvm-svn: 267430
* [SimplifyCFG] Add final missing implications to isImpliedTrueByMatchingCmp.Chad Rosier2016-04-221-8/+8
| | | | | | | | | Summary: eq imply [u|s]ge and [u|s]le are true. Remove redundant logic by implementing isImpliedFalseByMatchingCmp(Pred1, Pred2) as isImpliedTrueByMatchingCmp(Pred1, getInversePredicate(Pred2)). llvm-svn: 267177
* [SimplifyCFG] Add missing implications to isImpliedTrueByMatchingCmp.Chad Rosier2016-04-221-0/+1005
| | | | | | | | | Summary: [u|s]gt and [u|s]lt imply [u|s]ge and [u|s]le are true, respectively. I've simplified the existing tests and added additional tests to cover the new cases mentioned above. I've also added tests for all the cases where the first compare doesn't imply anything about the second compare. llvm-svn: 267171
OpenPOWER on IntegriCloud