summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine
Commit message (Collapse)AuthorAgeFilesLines
* InstCombine: Combine (add (and %a, %b) (or %a, %b)) to (add %a, %b)David Majnemer2014-08-111-1/+23
| | | | | | | | | | | | | | What follows bellow is a correctness proof of the transform using CVC3. $ < t.cvc A, B : BITVECTOR(32); QUERY BVPLUS(32, A & B, A | B) = BVPLUS(32, A, B); $ cvc3 < t.cvc Valid. llvm-svn: 215400
* This patch implements transform for pattern "(A & ~B) ^ (~A) -> ~(A & B)".Suyog Sarda2014-08-011-0/+5
| | | | | | Differential Revision: http://reviews.llvm.org/D4653 llvm-svn: 214479
* This patch implements transform for pattern "(A | B) & ((~A) ^ B) -> (A & B)".Suyog Sarda2014-08-011-0/+10
| | | | | | Differential Revision: http://reviews.llvm.org/D4628 llvm-svn: 214478
* This patch implements transform for pattern "( A & (~B)) | (A ^ B) -> (A ^ B)"Suyog Sarda2014-08-011-0/+10
| | | | | | Differential Revision: http://reviews.llvm.org/D4652 llvm-svn: 214477
* This patch implements transform for pattern "(A & B) | ((~A) ^ B) -> (~A ^ B)".Suyog Sarda2014-08-011-0/+10
| | | | | | | | Patch Credit to Ankit Jain ! Differential Revision: http://reviews.llvm.org/D4655 llvm-svn: 214476
* InstCombine: Correctly propagate NSW/NUW for x-(-A) -> x+ADavid Majnemer2014-07-311-3/+9
| | | | | | | | | | | | We can only propagate the nsw bits if both subtraction instructions are marked with the appropriate bit. N.B. We only propagate the nsw bit in InstCombine because the nuw case is already handled in InstSimplify. This fixes PR20189. llvm-svn: 214385
* InstCombine: Simplify (A ^ B) or/and (A ^ B ^ C)David Majnemer2014-07-301-0/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | While we can already transform A | (A ^ B) into A | B, things get bad once we have (A ^ B) | (A ^ B ^ Cst) because reassociation will morph this into (A ^ B) | ((A ^ Cst) ^ B). Our existing patterns fail once this happens. To fix this, we add a new pattern which looks through the tree of xor binary operators to see that, in fact, there exists a redundant xor operation. What follows bellow is a correctness proof of the transform using CVC3. $ cat t.cvc A, B, C : BITVECTOR(64); QUERY BVXOR(A, B) | BVXOR(BVXOR(B, C), A) = BVXOR(A, B) | C; QUERY BVXOR(BVXOR(A, C), B) | BVXOR(A, B) = BVXOR(A, B) | C; QUERY BVXOR(A, B) & BVXOR(BVXOR(B, C), A) = BVXOR(A, B) & ~C; QUERY BVXOR(BVXOR(A, C), B) & BVXOR(A, B) = BVXOR(A, B) & ~C; $ cvc3 < t.cvc Valid. Valid. Valid. Valid. llvm-svn: 214342
* Canonicalization for @llvm.assumeHal Finkel2014-07-251-0/+17
| | | | | | | | | Adds simple logical canonicalization of assumption intrinsics to instcombine, currently: - invariant(a && b) -> invariant(a); invariant(b) - invariant(!(a || b)) -> invariant(!a); invariant(!b) llvm-svn: 213977
* AA metadata refactoring (introduce AAMDNodes)Hal Finkel2014-07-241-6/+7
| | | | | | | | | | | | | | | | | | | | In order to enable the preservation of noalias function parameter information after inlining, and the representation of block-level __restrict__ pointer information (etc.), additional kinds of aliasing metadata will be introduced. This metadata needs to be carried around in AliasAnalysis::Location objects (and MMOs at the SDAG level), and so we need to generalize the current scheme (which is hard-coded to just one TBAA MDNode*). This commit introduces only the necessary refactoring to allow for the introduction of other aliasing metadata types, but does not actually introduce any (that will come in a follow-up commit). What it does introduce is a new AAMDNodes structure to hold all of the aliasing metadata nodes associated with a particular memory-accessing instruction, and uses that structure instead of the raw MDNode* in AliasAnalysis::Location, etc. No functionality change intended. llvm-svn: 213859
* This patch implements optimization as mentioned in PR19753: Optimize ↵Suyog Sarda2014-07-222-0/+95
| | | | | | | | | | | | | | | | | comparisons with "ashr/lshr exact" of a constanst. It handles the errors which were seen in PR19958 where wrong code was being emitted due to earlier patch. Added code for lshr as well as non-exact right shifts. It implements : (icmp eq/ne (ashr/lshr const2, A), const1)" -> (icmp eq/ne A, Log2(const2/const1)) -> (icmp eq/ne A, Log2(const2) - Log2(const1)) Differential Revision: http://reviews.llvm.org/D4068 llvm-svn: 213678
* Added InstCombine transform for pattern "(A & B) ^ (A ^ B) -> (A | B)"Suyog Sarda2014-07-221-0/+8
| | | | | | | | Patch idea by Ankit Jain ! Differential Revision: http://reviews.llvm.org/D4618 llvm-svn: 213677
* Added InstCombine Transform for patterns: Suyog Sarda2014-07-221-0/+10
| | | | | | | | | | "((~A & B) | A) -> (A | B)" and "((A & B) | ~A) -> (~A | B)" Original Patch credit to Ankit Jain !! Differential Revision: http://reviews.llvm.org/D4591 llvm-svn: 213676
* This patch implements transform for pattern "(A | B) ^ (~A) -> (A | ~B)".Suyog Sarda2014-07-221-0/+6
| | | | | | | | Patch Credit to Ankit Jain !! Differential Revision: http://reviews.llvm.org/D4588 llvm-svn: 213662
* fixed typo in commentSanjay Patel2014-07-221-1/+1
| | | | llvm-svn: 213614
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-2/+2
| | | | | | | | | 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-2/+2
| | | | | | | | | | | | | | | | | | 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
* Move ashr optimization from InstCombineShift to InstSimplify.Suyog Sarda2014-07-171-5/+0
| | | | | | | | | Refactor code, no functionality change, test case moved from instcombine to instsimplify. Differential Revision: http://reviews.llvm.org/D4102 llvm-svn: 213231
* Fix Typo (first commit to test commit access)Suyog Sarda2014-07-171-1/+1
| | | | llvm-svn: 213228
* Utilize CastInst::CreatePointerBitCastOrAddrSpaceCast here.Manuel Jacob2014-07-161-9/+6
| | | | llvm-svn: 213189
* Fix comment in InstCombiner::visitAddrSpaceCast.Manuel Jacob2014-07-161-3/+3
| | | | | | | | In the original version of the patch the behaviour was like described in the comment. This behaviour was changed before committing it without updating the comment. llvm-svn: 213117
* Use pointer type cast helpers.Matt Arsenault2014-07-141-3/+2
| | | | llvm-svn: 212963
* When we sink an instruction, this can open up opportunity for the operands ↵Aditya Nandakumar2014-07-111-2/+11
| | | | | | to be sunk - add them to the worklist llvm-svn: 212847
* InstCombine: Fix a crash in Descale for multiply-by-zeroDuncan P. N. Exon Smith2014-07-101-0/+6
| | | | | | | | | | Fix a crash in `InstCombiner::Descale()` when a multiply-by-zero gets created as an argument to a GEP partway through an iteration, causing -instcombine to optimize the GEP before the multiply. rdar://problem/17615671 llvm-svn: 212742
* Feeding isSafeToSpeculativelyExecute its DataLayout pointerHal Finkel2014-07-101-1/+1
| | | | | | | | | | | | | | isSafeToSpeculativelyExecute can optionally take a DataLayout pointer. In the past, this was mainly used to make better decisions regarding divisions known not to trap, and so was not all that important for users concerned with "cheap" instructions. However, now it also helps look through bitcasts for dereferencable loads, and will also be important if/when we add a dereferencable pointer attribute. This is some initial work to feed a DataLayout pointer through to callers of isSafeToSpeculativelyExecute, generally where one was already available. llvm-svn: 212720
* Fix for PR20059 (instcombine reorders shufflevector after instruction that ↵Sanjay Patel2014-07-091-0/+6
| | | | | | | | | | | | may trap) In PR20059 ( http://llvm.org/pr20059 ), instcombine eliminates shuffles that are necessary before performing an operation that can trap (srem). This patch calls isSafeToSpeculativelyExecute() and bails out of the optimization in SimplifyVectorOp() if needed. Differential Revision: http://reviews.llvm.org/D4424 llvm-svn: 212629
* fixed some typosSanjay Patel2014-07-071-4/+4
| | | | llvm-svn: 212495
* Make helper functions static.Benjamin Kramer2014-07-072-4/+4
| | | | llvm-svn: 212460
* InstCombine: Simplify code, no functionality change.Benjamin Kramer2014-07-071-16/+2
| | | | llvm-svn: 212449
* InstCombine: Strength reduce sadd.with.overflow into a regular nsw add if we ↵Benjamin Kramer2014-07-041-0/+15
| | | | | | | | can prove that it cannot overflow. PR20194 llvm-svn: 212331
* InstCombine: Optimize x/INT_MIN to x==INT_MINDavid Majnemer2014-07-021-0/+4
| | | | | | | The result of x/INT_MIN is either 0 or 1, we can just use an icmp instead. llvm-svn: 212167
* InstCombine: Don't turn -(x/INT_MIN) -> x/INT_MINDavid Majnemer2014-07-021-3/+3
| | | | | | | | | It is not safe to negate the smallest signed integer, doing so yields the same number back. This fixes PR20186. llvm-svn: 212164
* Optimize InstCombine stack memory consumptionReid Kleckner2014-07-011-75/+78
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch reduces the stack memory consumption of the InstCombine function "isOnlyCopiedFromConstantGlobal() ", that in certain conditions could overflow the stack because of excessive recursiveness. For example, in a case like this: %0 = alloca [50025 x i32], align 4 %1 = getelementptr inbounds [50025 x i32]* %0, i64 0, i64 0 store i32 0, i32* %1 %2 = getelementptr inbounds i32* %1, i64 1 store i32 1, i32* %2 %3 = getelementptr inbounds i32* %2, i64 1 store i32 2, i32* %3 %4 = getelementptr inbounds i32* %3, i64 1 store i32 3, i32* %4 %5 = getelementptr inbounds i32* %4, i64 1 store i32 4, i32* %5 %6 = getelementptr inbounds i32* %5, i64 1 store i32 5, i32* %6 ... This piece of code crashes llvm when trying to apply instcombine on desktop. On embedded devices this could happen with a much lower limit of recursiveness. Some instructions (getelementptr and bitcasts) make the function recursively call itself on their uses, which is what makes the example above consume so much stack (it becomes a recursive depth-first tree visit with a very big depth). The patch changes the algorithm to be semantically equivalent, but iterative instead of recursive and the visiting order to be from a depth-first visit to a breadth-first visit (visit all the instructions of the current level before the ones of the next one). Now if a lot of memory is required a heap allocation is done instead of the the stack allocation, avoiding the possible crash. Reviewed By: rnk Differential Revision: http://reviews.llvm.org/D4355 Patch by Marcello Maggioni! We don't generally commit large stress test that look for out of memory conditions, so I didn't request that one be added to the patch. llvm-svn: 212133
* Added instruction combine to transform few more negative values addition to ↵Dinesh Dwivedi2014-06-271-48/+62
| | | | | | | | | | | | subtraction (Part 3) This patch enables transforms for (x + (~(y | c) + 1) --> x - (y | c) if c is odd Differential Revision: http://reviews.llvm.org/D4210 llvm-svn: 211881
* This patch removed duplicate code for matching patterns Dinesh Dwivedi2014-06-261-36/+0
| | | | | | | | | which are now handled in SimplifyUsingDistributiveLaws() (after r211261) Differential Revision: http://reviews.llvm.org/D4253 llvm-svn: 211768
* Added instruction combine to transform few more negative values addition to ↵Dinesh Dwivedi2014-06-261-49/+54
| | | | | | | | | | | | subtraction (Part 2) This patch enables transforms for (x + (~(y | c) + 1) --> x - (y | c) if c is even Differential Revision: http://reviews.llvm.org/D4209 llvm-svn: 211765
* InstCombine: Disable umul.with.overflow recognition for vectors.Benjamin Kramer2014-06-241-1/+5
| | | | | | It doesn't make a lot on most targets and the code isn't ready for it. PR20113. llvm-svn: 211583
* InstCombine: Don't try to reorder shuffles where the mask is a ConstantExpr.Benjamin Kramer2014-06-241-1/+3
| | | | | | We can't analyze the individual values of a vector expression. PR20114. llvm-svn: 211581
* Added instruction combine to transform few more negative values addition to ↵Dinesh Dwivedi2014-06-191-0/+45
| | | | | | | | | | | | subtraction (Part 1) This patch enables transforms for following patterns. (x + (~(y & c) + 1) --> x - (y & c) (x + (~((y >> z) & c) + 1) --> x - ((y>>z) & c) Differential Revision: http://reviews.llvm.org/D3733 llvm-svn: 211266
* Refactored and updated SimplifyUsingDistributiveLaws() to Dinesh Dwivedi2014-06-192-105/+142
| | | | | | | | | | | | * Find factorization opportunities using identity values. * Find factorization opportunities by treating shl(X, C) as mul (X, shl(C)) * Keep NSW flag while simplifying instruction using factorization. This fixes PR19263. Differential Revision: http://reviews.llvm.org/D3799 llvm-svn: 211261
* InstCombine: Stop two transforms duelingDavid Majnemer2014-06-191-2/+5
| | | | | | | | | | | | | | | | | | | | | | InstCombineMulDivRem has: // Canonicalize (X+C1)*CI -> X*CI+C1*CI. InstCombineAddSub has: // W*X + Y*Z --> W * (X+Z) iff W == Y These two transforms could fight with each other if C1*CI would not fold away to something simpler than a ConstantExpr mul. The InstCombineMulDivRem transform only acted on ConstantInts until r199602 when it was changed to operate on all Constants in order to let it fire on ConstantVectors. To fix this, make this transform more careful by checking to see if we actually folded away C1*CI. This fixes PR20079. llvm-svn: 211258
* Move optimization of some cases of (A & C1)|(B & C2) from instcombine to ↵Nick Lewycky2014-06-191-23/+0
| | | | | | instsimplify. Patch by Rahul Jain, plus some last minute changes by me -- you can blame me for any bugs. llvm-svn: 211252
* Remove redundant code in InstCombineShift, no functionality change because ↵Nick Lewycky2014-06-191-5/+0
| | | | | | instsimplify already does this and instcombine calls instsimplify a few lines above. Patch by Suyog Sarda! llvm-svn: 211250
* R600/SI: Add intrinsics for various math instructions.Matt Arsenault2014-06-191-0/+14
| | | | | | | | These will be used for custom lowering and for library implementations of various math functions, so it's useful to expose these as builtins. llvm-svn: 211247
* [InstCombine] mark ADD with nuw if no unsigned overflowJingyue Wu2014-06-172-0/+23
| | | | | | | | | | | | | | | | | | | | | | Summary: As a starting step, we only use one simple heuristic: if the sign bits of both a and b are zero, we can prove "add a, b" do not unsigned overflow, and thus convert it to "add nuw a, b". Updated all affected tests and added two new tests (@zero_sign_bit and @zero_sign_bit2) in AddOverflow.ll Test Plan: make check-all Reviewers: eliben, rafael, meheff, chandlerc Reviewed By: chandlerc Subscribers: chandlerc, llvm-commits Differential Revision: http://reviews.llvm.org/D4144 llvm-svn: 211084
* Canonicalize addrspacecast ConstExpr between different pointer typesJingyue Wu2014-06-151-2/+4
| | | | | | | | | | | | | | | | | | As a follow-up to r210375 which canonicalizes addrspacecast instructions, this patch canonicalizes addrspacecast constant expressions. Given clang uses ConstantExpr::getAddrSpaceCast to emit addrspacecast cosntant expressions, this patch is also a step towards having the frontend emit canonicalized addrspacecasts. Piggyback a minor refactor in InstCombineCasts.cpp Update three affected tests in addrspacecast-alias.ll, access-non-generic.ll and constant-fold-gep.ll and added one new test in constant-fold-address-space-pointer.ll llvm-svn: 211004
* This removes TODO added in http://reviews.llvm.org/D3658Dinesh Dwivedi2014-06-121-2/+9
| | | | | | | | | | | The patch transforms ABS(NABS(X)) -> ABS(X) NABS(ABS(X)) -> NABS(X) Differential Revision: http://reviews.llvm.org/D4040 llvm-svn: 210782
* Look through addrspacecasts when turning ptr comparisons intoMatt Arsenault2014-06-091-5/+21
| | | | | | index comparisons. llvm-svn: 210488
* Revert 209903 and 210040.Rafael Espindola2014-06-071-40/+0
| | | | | | | | | | | | The messages were "PR19753: Optimize comparisons with "ashr exact" of a constanst." "Added support to optimize comparisons with "lshr exact" of a constant." They were not correctly handling signed/unsigned operation differences, causing pr19958. llvm-svn: 210393
* InstCombine: Canonicalize addrspacecast between different element typesJingyue Wu2014-06-061-1/+23
| | | | | | | | | | | | | | | | addrspacecast X addrspace(M)* to Y addrspace(N)* --> bitcast X addrspace(M)* to Y addrspace(M)* addrspacecast Y addrspace(M)* to Y addrspace(N)* Updat all affected tests and add several new tests in addrspacecast.ll. This patch is based on http://reviews.llvm.org/D2186 (authored by Matt Arsenault) with fixes and more tests. llvm-svn: 210375
* Added select flavour for ABS and NEG(ABS)Dinesh Dwivedi2014-06-062-20/+51
| | | | | | | | | | | | | | | | This patch can identify ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X and can transform ABS(ABS(X)) -> ABS(X) NABS(NABS(X)) -> NABS(X) Differential Revision: http://reviews.llvm.org/D3658 llvm-svn: 210312
OpenPOWER on IntegriCloud