summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
Commit message (Collapse)AuthorAgeFilesLines
* simplify; NFCSanjay Patel2016-01-311-8/+5
| | | | llvm-svn: 259323
* Avoid overly large SmallPtrSet/SmallSetMatthias Braun2016-01-301-1/+1
| | | | | | | These sets perform linear searching in small mode so it is never a good idea to use SmallSize/N bigger than 32. llvm-svn: 259283
* [InstCombine, SCCP] Consolidate code used to remove instructionsDavid Majnemer2016-01-241-18/+3
| | | | | | | | | InstCombine and SCCP both want to remove dead code in a very particular way but using identical means to do so. Share the code between the two. No functionality change is intended. llvm-svn: 258653
* [opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with ↵Eduard Burtescu2016-01-191-12/+11
| | | | | | | | | | | | | | | | | | get{Source,Result}ElementType. Summary: GEPOperator: provide getResultElementType alongside getSourceElementType. This is made possible by adding a result element type field to GetElementPtrConstantExpr, which GetElementPtrInst already has. GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16275 llvm-svn: 258145
* [opaque pointer types] [breaking-change] [NFC] SimplifyGEPInst: take the ↵Manuel Jacob2016-01-171-1/+1
| | | | | | | | | | | | | | source element type of the GEP as an argument. Patch by Eduard Burtescu. Reviewers: dblaikie, mjacob Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16281 llvm-svn: 258024
* [InstructionCombining] prepareICWorklistFromFunction halts in infinite loop ↵Chen Li2016-01-041-3/+2
| | | | | | | | | | | | | | with instructions of token type Summary: This patch fixes a bug in prepareICWorklistFromFunction, where the loop becomes infinite with instructions of token type. The patch checks if the instruction is token type, and if so it updates EndInst with the current instruction. Reviewers: reames, majnemer Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D15859 llvm-svn: 256792
* Instcombine: destructor loads of structs that do not contains paddingMehdi Amini2015-12-151-3/+4
| | | | | | | | | | | | | | | | | | | | For non padded structs, we can just proceed and deaggregate them. We don't want ot do this when there is padding in the struct as to not lose information about this padding (the subsequents passes would then try hard to preserve the padding, which is undesirable). Also update extractvalue.ll and cast.ll so that they use structs with padding. Remove the FIXME in the extractvalue of laod case as the non padded case is handled when processing the load, and we don't want to do it on the padded case. Patch by: Amaury SECHET <deadalnix@gmail.com> Differential Revision: http://reviews.llvm.org/D14483 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 255600
* getParent() ^ 3 == getModule() ; NFCISanjay Patel2015-12-141-1/+1
| | | | llvm-svn: 255511
* Move EH-specific helper functions to a more appropriate placeDavid Majnemer2015-12-021-1/+1
| | | | | | No functionality change is intended. llvm-svn: 254562
* [InstCombine] fix propagation of fast-math-flagsSanjay Patel2015-11-241-10/+5
| | | | | | | Noticed while working on D4583: http://reviews.llvm.org/D4583 llvm-svn: 253997
* use ternary ops; NFCSanjay Patel2015-11-211-8/+2
| | | | llvm-svn: 253787
* remove unnecessary temp variables; NFCSanjay Patel2015-11-211-4/+2
| | | | llvm-svn: 253786
* [EH] Keep filter clauses for types that have been caught.Andrew Kaylor2015-11-171-4/+18
| | | | | | | | The instruction combiner previously removed types from filter clauses in Landing Pad instructions if the type had previously been seen in a catch clause. This is incorrect and prevents unexpected exception handlers from rethrowing the caught type. Differential Revision: http://reviews.llvm.org/D14669 llvm-svn: 253370
* Fixed GEP visitor in the InstCombine pass.Elena Demikhovsky2015-11-151-5/+10
| | | | | | | | | | | | | The current implementation of GEP visitor in InstCombine fails with assertion on Vector GEP with mix of scalar and vector types, like this: getelementptr double, double* %a, <8 x i32> %i (It fails to create a "sext" from <8 x i32> to <8 x i64>) I fixed it and added some tests. Differential Revision: http://reviews.llvm.org/D14485 llvm-svn: 253162
* [InstCombine] Don't RAUW tokens with undefDavid Majnemer2015-11-061-2/+3
| | | | | | Let SimplifyCFG remove unreachable BBs which define token instructions. llvm-svn: 252343
* InstCombine: fix sinking of convergent callsFiona Glaser2015-11-031-0/+6
| | | | llvm-svn: 251991
* [InstCombine] Teach instcombine not to create extra PHI nodes when folding GEPsSilviu Baranga2015-10-261-1/+6
| | | | | | | | | | | | | | | | | | Summary: InstCombine tries to transform GEP(PHI(GEP1, GEP2, ..)) into GEP(GEP(PHI(...)) when possible. However, this may leave the old PHI node around. Even if we do end up folding the GEPs, having an extra PHI node might not be beneficial. This change makes the transformation more conservative. We now only do this if the PHI has only one use, and can therefore be removed after the transformation. Reviewers: jmolloy, majnemer Subscribers: mcrosier, mssimpso, llvm-commits Differential Revision: http://reviews.llvm.org/D13887 llvm-svn: 251281
* Handle non-constant shifts in computeKnownBits, and use computeKnownBits for ↵Hal Finkel2015-10-231-0/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | constant folding in InstCombine/Simplify First, the motivation: LLVM currently does not realize that: ((2072 >> (L == 0)) >> 7) & 1 == 0 where L is some arbitrary value. Whether you right-shift 2072 by 7 or by 8, the lowest-order bit is always zero. There are obviously several ways to go about fixing this, but the generic solution pursued in this patch is to teach computeKnownBits something about shifts by a non-constant amount. Previously, we would give up completely on these. Instead, in cases where we know something about the low-order bits of the shift-amount operand, we can combine (and together) the associated restrictions for all shift amounts consistent with that knowledge. As a further generalization, I refactored all of the logic for all three kinds of shifts to have this capability. This works well in the above case, for example, because the dynamic shift amount can only be 0 or 1, and thus we can say a lot about the known bits of the result. This brings us to the second part of this change: Even when we know all of the bits of a value via computeKnownBits, nothing used to constant-fold the result. This introduces the necessary code into InstCombine and InstSimplify. I've added it into both because: 1. InstCombine won't automatically pick up the associated logic in InstSimplify (InstCombine uses InstSimplify, but not via the API that passes in the original instruction). 2. Putting the logic in InstCombine allows the resulting simplifications to become part of the iterative worklist 3. Putting the logic in InstSimplify allows the resulting simplifications to be used by everywhere else that calls SimplifyInstruction (inlining, unrolling, and many others). And this requires a small change to our definition of an ephemeral value so that we don't break the rest case from r246696 (where the icmp feeding the @llvm.assume, is also feeding a br). Under the old definition, the icmp would not be considered ephemeral (because it is used by the br), but this causes the assume to remove itself (in addition to simplifying the branch structure), and it seems more-useful to prevent that from happening. llvm-svn: 251146
* Use ArrayRef instead of pointer and size. NFCCraig Topper2015-10-221-2/+1
| | | | llvm-svn: 251029
* InstCombine: Remove ilist iterator implicit conversions, NFCDuncan P. N. Exon Smith2015-10-131-16/+18
| | | | | | | Stop relying on implicit conversions of ilist iterators in LLVMInstCombine. No functionality change intended. llvm-svn: 250183
* [WinEH] Recognize CoreCLR personality functionJoseph Tremoulet2015-10-061-0/+1
| | | | | | | | | | | | | | | Summary: - Add CoreCLR to if/else ladders and switches as appropriate. - Rename isMSVCEHPersonality to isFuncletEHPersonality to better reflect what it captures. Reviewers: majnemer, andrew.w.kaylor, rnk Subscribers: pgavlin, AndyAyers, llvm-commits Differential Revision: http://reviews.llvm.org/D13449 llvm-svn: 249455
* add ShouldChangeType() variant that takes bitwidthsSanjay Patel2015-09-211-6/+15
| | | | | | This is more efficient for cases like D12965 where we already have widths. llvm-svn: 248170
* don't repeat function names in comments; NFCSanjay Patel2015-09-211-62/+57
| | | | llvm-svn: 248166
* typo; NFCSanjay Patel2015-09-111-1/+1
| | | | llvm-svn: 247454
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-3/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* use minSize wrapper; NFCISanjay Patel2015-08-181-3/+1
| | | | | | | These were missed when other uses were switched over: http://llvm.org/viewvc/llvm-project?view=revision&revision=243994 llvm-svn: 245311
* Fix some comment typos.Benjamin Kramer2015-08-081-1/+1
| | | | llvm-svn: 244402
* [InstCombine] Don't try to sink EH pad instructionsDavid Majnemer2015-08-081-2/+2
| | | | | | | Found by inspection, this change should not effect the existing landingpad behavior. llvm-svn: 244391
* Convert a bunch of loops to foreach. NFC.Pete Cooper2015-08-061-2/+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
* [InstCombine] Generalize sub of selects optimization to all BinaryOperatorsDavid Majnemer2015-07-141-0/+27
| | | | | | | This exposes further optimization opportunities if the selects are correlated. llvm-svn: 242235
* [InstSimplify] Teach InstSimplify how to simplify extractvalueDavid Majnemer2015-07-131-10/+3
| | | | llvm-svn: 242007
* [InstCombine] Employ AliasAnalysis in FindAvailableLoadedValueBjorn Steinbrink2015-07-101-5/+11
| | | | llvm-svn: 241887
* fix typo; NFCSanjay Patel2015-06-231-1/+1
| | | | llvm-svn: 240480
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Move the personality function from LandingPadInst to FunctionDavid Majnemer2015-06-171-4/+6
| | | | | | | | | | | | | | | | | | | The personality routine currently lives in the LandingPadInst. This isn't desirable because: - All LandingPadInsts in the same function must have the same personality routine. This means that each LandingPadInst beyond the first has an operand which produces no additional information. - There is ongoing work to introduce EH IR constructs other than LandingPadInst. Moving the personality routine off of any one particular Instruction and onto the parent function seems a lot better than have N different places a personality function can sneak onto an exceptional function. Differential Revision: http://reviews.llvm.org/D10429 llvm-svn: 239940
* Replace push_back(Constructor(foo)) with emplace_back(foo) for non-trivial typesBenjamin Kramer2015-05-291-5/+5
| | | | | | | | | | | | | | | | | | | | If the type isn't trivially moveable emplace can skip a potentially expensive move. It also saves a couple of characters. Call sites were found with the ASTMatcher + some semi-automated cleanup. memberCallExpr( argumentCountIs(1), callee(methodDecl(hasName("push_back"))), on(hasType(recordDecl(has(namedDecl(hasName("emplace_back")))))), hasArgument(0, bindTemporaryExpr( hasType(recordDecl(hasNonTrivialDestructor())), has(constructExpr()))), unless(isInTemplateInstantiation())) No functional change intended. llvm-svn: 238602
* [InstCombine] Don't eagerly propagate nsw for A*B+A*C => A*(B+C)David Majnemer2015-05-221-3/+16
| | | | | | | | | | | | | | | | InstCombine transforms A *nsw B +nsw A *nsw C to A *nsw (B + C). This is incorrect -- e.g. if A = -1, B = 1, C = INT_SMAX. Then nothing in the LHS overflows, but the multiplication in RHS overflows. We need to first make sure that we won't multiple by INT_SMAX + 1. Test case `add_of_mul` contributed by Sanjoy Das. This fixes PR23635. Differential Revision: http://reviews.llvm.org/D9629 llvm-svn: 238066
* Reapply r237539 with a fix for the Chromium build.James Molloy2015-05-201-1/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Make sure if we're truncating a constant that would then be sign extended that the sign extension of the truncated constant is the same as the original constant. > Canonicalize min/max expressions correctly. > > This patch introduces a canonical form for min/max idioms where one operand > is extended or truncated. This often happens when the other operand is a > constant. For example: > > %1 = icmp slt i32 %a, i32 0 > %2 = sext i32 %a to i64 > %3 = select i1 %1, i64 %2, i64 0 > > Would now be canonicalized into: > > %1 = icmp slt i32 %a, i32 0 > %2 = select i1 %1, i32 %a, i32 0 > %3 = sext i32 %2 to i64 > > This builds upon a patch posted by David Majenemer > (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass > passively stopped instcombine from ruining canonical patterns. This > patch additionally actively makes instcombine canonicalize too. > > Canonicalization of expressions involving a change in type from int->fp > or fp->int are not yet implemented. llvm-svn: 237821
* Revert r237539: "Reapply r237520 with another fix for infinite looping"Hans Wennborg2015-05-191-16/+1
| | | | | | This caused PR23583. llvm-svn: 237739
* Reapply r237520 with another fix for infinite loopingJames Molloy2015-05-171-1/+16
| | | | | | | | | SimplifyDemandedBits was "simplifying" a constant by removing just sign bits. This caused a canonicalization race between different parts of instcombine. Fix and regression test added - third time lucky? llvm-svn: 237539
* Revert commits r237521 and r237520.James Molloy2015-05-161-16/+1
| | | | | | | | The AArch64 LNT bot is unhappy - I've found that the problem is in SimpliftDemandedBits, but that's going to require another code review so reverting in the meantime. llvm-svn: 237528
* Reapply r237453 with a fix for the test timeouts.James Molloy2015-05-161-1/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The test timeouts were due to instcombine fighting itself. Regression test added. Original log message: Canonicalize min/max expressions correctly. This patch introduces a canonical form for min/max idioms where one operand is extended or truncated. This often happens when the other operand is a constant. For example: %1 = icmp slt i32 %a, i32 0 %2 = sext i32 %a to i64 %3 = select i1 %1, i64 %2, i64 0 Would now be canonicalized into: %1 = icmp slt i32 %a, i32 0 %2 = select i1 %1, i32 %a, i32 0 %3 = sext i32 %2 to i64 This builds upon a patch posted by David Majenemer (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass passively stopped instcombine from ruining canonical patterns. This patch additionally actively makes instcombine canonicalize too. Canonicalization of expressions involving a change in type from int->fp or fp->int are not yet implemented. llvm-svn: 237520
* Revert "Canonicalize min/max expressions correctly."James Molloy2015-05-151-16/+1
| | | | | | | This reverts r237453 - it was causing timeouts on some bots. Reverting while I investigate (it's probably InstCombine fighting itself...) llvm-svn: 237458
* Canonicalize min/max expressions correctly.James Molloy2015-05-151-1/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch introduces a canonical form for min/max idioms where one operand is extended or truncated. This often happens when the other operand is a constant. For example: %1 = icmp slt i32 %a, i32 0 %2 = sext i32 %a to i64 %3 = select i1 %1, i64 %2, i64 0 Would now be canonicalized into: %1 = icmp slt i32 %a, i32 0 %2 = select i1 %1, i32 %a, i32 0 %3 = sext i32 %2 to i64 This builds upon a patch posted by David Majenemer (https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass passively stopped instcombine from ruining canonical patterns. This patch additionally actively makes instcombine canonicalize too. Canonicalization of expressions involving a change in type from int->fp or fp->int are not yet implemented. llvm-svn: 237453
* [opaque pointer type] Track explicit GEP pointee type through in-memory IRDavid Blaikie2015-05-051-0/+1
| | | | llvm-svn: 236510
* Limiting gep merging to fix the performance problem described inWei Mi2015-04-211-0/+5
| | | | | | | | | | | | | | | | | | https://llvm.org/bugs/show_bug.cgi?id=23163. Gep merging sometimes behaves like a reverse CSE/LICM optimization, which has negative impact on performance. In this patch we restrict gep merging to happen only when the indexes to be merged are both consts, which ensures such merge is always beneficial. The patch makes gep merging only happen in very restrictive cases. It is possible that some analysis/optimization passes rely on the merged geps to get better result, and we havn't notice them yet. We will be ready to further improve it once we see the cases. Differential Revision: http://reviews.llvm.org/D8911 llvm-svn: 235455
* Revert r235451 since it is attached to a wrong Differential Revision. Sorry.Wei Mi2015-04-211-5/+0
| | | | llvm-svn: 235453
* Limiting gep merging to fix the performance problem described inWei Mi2015-04-211-0/+5
| | | | | | | | | | | | | | | | | | https://llvm.org/bugs/show_bug.cgi?id=23163. Gep merging sometimes behaves like a reverse CSE/LICM optimizations, which has negative impact on performance. In this patch we restrict gep merging to happen only when the indexes to be merged are both consts, which ensures such merge is always beneficial. The patch makes gep merging only happen in very restrictive cases. It is possible that some analysis/optimization passes rely on the merged geps to get better result, and we havn't notice them yet. We will be ready to further improve it once we see the cases. Differential Revision: http://reviews.llvm.org/D9007 llvm-svn: 235451
* [opaque pointer type] More GEP IRBuilder API migrations...David Blaikie2015-04-031-19/+22
| | | | llvm-svn: 234058
OpenPOWER on IntegriCloud