aboutsummaryrefslogtreecommitdiff
path: root/test/Transforms/IndVarSimplify
AgeCommit message (Collapse)Author
2009-08-31Merge from mainline.Tanya Lattner
Special-case static allocas in IndVarSimplify's loop invariant sinking code, since they are special. If the loop preheader happens to be the entry block of a function, don't sink static allocas out of it. This fixes PR4775. git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_26@80551 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-18Generalize ScalarEvolution to be able to analyze GEPs whenDan Gohman
TargetData is not present. It still uses TargetData when available. This generalization also fixed some limitations in the TargetData case; the attached testcase covers this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79344 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-20The upper argument of ConstantRange is exclusive, not inclusive.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76492 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-20Revert the addition of hasNoPointerOverflow to GEPOperator.Dan Gohman
Getelementptrs that are defined to wrap are virtually useless to optimization, and getelementptrs that are undefined on any kind of overflow are too restrictive -- it's difficult to ensure that all intermediate addresses are within bounds. I'm going to take a different approach. Remove a few optimizations that depended on this flag. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76437 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-16Fill in some holes in ScalarEvolution's loop iteration conditionDan Gohman
analysis. This allows indvars to emit a simpler loop trip count expression. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76085 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-15Switch invars away from using isTrapping when it really shouldn't be Eli Friedman
using it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75852 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-14Fix the expansion of umax and smax in the case where one or more ofDan Gohman
the operands have pointer type, so that the resulting type matches the original SCEV type, and so that unnecessary ptrtoints are avoided in common cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75680 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-14Add a testcase for a bug fixed by r75634.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75644 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-14Update LoopSimplify and LoopUnswitch to use the new makeLoopInvariantDan Gohman
function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75584 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-14Fix indvars to not assume that a loop with a single unique exitDan Gohman
block has a single unique exiting block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75579 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-13Reapply 75252, with a fix to avoid the infinite recursion case. TheDan Gohman
check for avoiding re-analyzing a widening cast needed to happen earlier, as getSCEV itself may result in a isLoopGuardedByCond query. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75511 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-11Revert r75252 which was causing some crashes at compile time.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75384 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-10Generalize ScalarEvolution's cast-folding code to support more kindsDan Gohman
of loops. Add several new functions to for working with ScalarEvolution's add-hoc value-range analysis functionality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75252 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-29Don't cache PHI exit values from exhaustive evaluations, becauseDan Gohman
an individual exhaustive evaluation reflects only the exit value implied by an individual exit, which may differ from the actual exit value of the loop if there are other exits. This fixes PR4477. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74447 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-27When a value is used multiple times within a single PHI, instructionsDan Gohman
inserted to replace that value must dominate all of of the basic blocks associated with the uses of the value in the PHI, not just one of them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74376 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-26Add some testcases for some of the recent ScalarEvolution bug fixes.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74353 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Simplify [su]max(MAX, n) to MAX. This comes up in loop tripcountDan Gohman
computations in loops with multiple exits. Adjust the testcase for PR4436 so that the relevant portion isn't optimized away. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74073 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24When inserting code into a loop preheader, insert it before theDan Gohman
terminator, instead of after the last phi. This fixes a bug exposed by ScalarEvolution analyzing more kinds of loops. This fixes PR4436. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74072 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-21Fix ScalarEvolution's backedge-taken count computations to check forDan Gohman
overflow when computing a integer division to round up. Thanks to Nick Lewycky for noticing this! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73862 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-20Generalize isLoopGuardedByCond's checking to consider twoDan Gohman
SCEVUnknowns with identical Instructions to be equal. This allows it to analze cases such as the attached testcase, where the front-end has cloned the loop controlling expression. Along with r73805, this lets IndVarSimplify eliminate all the sign-extend casts in the loop in the attached testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73807 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Remove the code from IVUsers that attempted to handleDan Gohman
casted induction variables in cases where the cast isn't foldable. It ended up being a pessimization in many cases. This could be fixed, but it would require a bunch of complicated code in IVUsers' clients. The advantages of this approach aren't visible enough to justify it at this time. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73706 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-17Add -disable-output to a bunch of tests that don't care about the output.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73633 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-16Instcombine's ShrinkDemandedConstant may strip bits out of constants,Dan Gohman
obscuring what would otherwise be a low-bits mask. Use ComputeMaskedBits to compute what ShrinkDemandedConstant knew about to reconstruct a low-bits mask value. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73540 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Implement more aggressive folding of add operand lists whenDan Gohman
they contain multiplications of constants with add operations. This helps simplify several kinds of things; in particular it helps simplify expressions like ((-1 * (%a + %b)) + %a) to %b, as expressions like this often come up in loop trip count computations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73361 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-13Teach SCEVExpander's visitAddRecExpr to reuse an existing canonicalDan Gohman
induction variable when the addrec to be expanded does not require a wider type. This eliminates the need for IndVarSimplify to micro-manage SCEV expansions, because SCEVExpander now automatically expands them in the form that IndVarSimplify considers to be canonical. (LSR still micro-manages its SCEV expansions, because it's optimizing for the target, rather than for other optimizations.) Also, this uses the new getAnyExtendExpr, which has more clever expression simplification logic than the IndVarSimplify code it replaces, and this cleans up some ugly expansions in code such as the included masked-iv.ll testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73294 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-04Split the Add, Sub, and Mul instruction opcodes into separateDan Gohman
integer and floating-point opcodes, introducing FAdd, FSub, and FMul. For now, the AsmParser, BitcodeReader, and IRBuilder all preserve backwards compatability, and the Core LLVM APIs preserve backwards compatibility for IR producers. Most front-ends won't need to change immediately. This implements the first step of the plan outlined here: http://nondot.org/sabre/LLVMNotes/IntegerOverflow.txt git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72897 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-03Don't attempt to simplify an non-affine IV expression if it can'tDan Gohman
be simplified to a loop-invariant value. This fixes PR4315. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72798 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-27Teach SCEVExpander to avoid creating over-indexed GEP indices whenDan Gohman
possible. For example, it now emits %p.2.ip.1 = getelementptr [3 x [3 x double]]* %p, i64 2, i64 %tmp, i64 1 instead of the equivalent but less obvious %p.2.ip.1 = getelementptr [3 x [3 x double]]* %p, i64 0, i64 %tmp, i64 19 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72452 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-26In cases where a pointer value is an operand of a multiplication orDan Gohman
division operation, don't attempt to use the operation's value as the base of a getelementptr. This fixes PR4271. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72422 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-24When rewriting the loop exit test with the canonical induction variable,Dan Gohman
leave the original comparison in place if it has other uses, since the other uses won't be dominated by the new comparison instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72369 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-24Generalize SCEVExpander::visitAddRecExpr's GEP persuit, and avoidDan Gohman
sending SCEVUnknowns to expandAddToGEP. This avoids the need for expandAddToGEP to bend the rules and peek into SCEVUnknown expressions. Factor out the code for testing whether a SCEV can be factored by a constant for use in a GEP index. This allows it to handle SCEVAddRecExprs, by recursing. As a result, SCEVExpander can now put more things in GEP indices, so it emits fewer explicit mul instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72366 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-24The rewriter may hold references to instructions that are deleted because ↵Torok Edwin
they are trivially dead. Fix by clearing the rewriter cache before deleting the trivially dead instructions. Also make InsertedExpressions use an AssertingVH to catch these bugs easier. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72364 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-22Teach IndVarSimplify's FixUsesBeforeDefs to handle InvokeInsts byDan Gohman
assuming that the use of the value is in a block dominated by the "normal" destination. LangRef.html and other documentation sources don't explicitly guarantee this, but it seems to be assumed in other places in LLVM at least. This fixes an assertion failure on the included testcase, which is derived from the Ada testsuite. FixUsesBeforeDefs is a temporary measure which I'm looking to replace with a more capable solution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72266 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-22Fix a thinko in the code that adapted SCEVMulExpr operands forDan Gohman
use in expanding SCEVAddExprs with GEPs. The operands of a SCEVMulExpr need to be multiplied together, not added. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72250 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-19Teach SCEVExpander to expand arithmetic involving pointers into GEPDan Gohman
instructions. It attempts to create high-level multi-operand GEPs, though in cases where this isn't possible it falls back to casting the pointer to i8* and emitting a GEP with that. Using GEP instructions instead of ptrtoint+arithmetic+inttoptr helps pointer analyses that don't use ScalarEvolution, such as BasicAliasAnalysis. Also, make the AddrModeMatcher more aggressive in handling GEPs. Previously it assumed that operand 0 of a GEP would require a register in almost all cases. It now does extra checking and can do more matching if operand 0 of the GEP is foldable. This fixes a problem that was exposed by SCEVExpander using GEPs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72093 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-18Add nounwind to a few tests.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72002 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-12Factor the code for collecting IV users out of LSR into an IVUsers class,Dan Gohman
and generalize it so that it can be used by IndVarSimplify. Implement the base IndVarSimplify transformation code using IVUsers. This removes TestOrigIVForWrap and associated code, as ScalarEvolution now has enough builtin overflow detection and folding logic to handle all the same cases, and more. Run "opt -iv-users -analyze -disable-output" on your favorite loop for an example of what IVUsers does. This lets IndVarSimplify eliminate IV casts and compute trip counts in more cases. Also, this happens to finally fix the remaining testcases in PR1301. Now that IndVarSimplify is being more aggressive, it occasionally runs into the problem where ScalarEvolutionExpander's code for avoiding duplicate expansions makes it difficult to ensure that all expanded instructions dominate all the instructions that will use them. As a temporary measure, IndVarSimplify now uses a FixUsesBeforeDefs function to fix up instructions inserted by SCEVExpander. Fortunately, this code is contained, and can be easily removed once a more comprehensive solution is available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71535 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-12When forgetting SCEVs for loop PHIs, don't forget SCEVUnknown values.Dan Gohman
These values aren't analyzable, so they don't care if more information about the loop trip count can be had. Also, SCEVUnknown is used for a PHI while the PHI itself is being analyzed, so it needs to be left in the Scalars map. This fixes a variety of subtle issues. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@71533 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-28Make this testcase slightly less trivial, so that it doesn't failDan Gohman
if indvars happens to optimize away the unused primary induction variable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70333 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-27Fix PR 4086, a bug in FP IV elimination.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70247 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-27Handle ands with ~0 correctly too. This fixes PR4052.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70176 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-25Handle ands with 0 and shifts by 0 correctly. These aren'tDan Gohman
common, but indvars shouldn't crash on them. This fixes PR4054. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70051 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-23Fix an error in this test.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69893 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-23Change SCEVExpander's expandCodeFor to provide more flexibilityDan Gohman
with the persistent insertion point, and change IndVars to make use of it. This fixes a bug where IndVars was holding on to a stale insertion point and forcing the SCEVExpander to continue to use it. This fixes PR4038. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69892 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-22Make sure both operands have binary instructions have the same type.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69844 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-22Avoid deferencing use_begin() if value does not have a use.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69836 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-22SCEVExpander's InsertCastOfTo knows how to move existing castDan Gohman
instructions in order to avoid inserting new ones. However, if the cast instruction is the SCEVExpander's InsertPt, this causes subsequently emitted instructions to be inserted near the cast, and not at the location of the original insert point. Fix this by adjusting the insert point in such cases. This fixes PR4009. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69808 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Another testcase for IV shortening.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69247 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-15Enhance induction variable code to remove theDale Johannesen
sext around sext(shorter IV + constant), using a longer IV instead, when it can figure out the add can't overflow. This comes up a lot in subscripting; mainly affects 64 bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69123 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-23Back out the change in 64918 that used sign-extensions when promotingDan Gohman
trip counts that use signed comparisons. It's not obviously the best approach for preserving trip count information, and at any rate there isn't anything in the tree right now that makes use of that, so for now always using zero-extensions is preferable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65347 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-12-29 12:46:28 +0000