aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolutionExpander.cpp
AgeCommit message (Collapse)Author
2009-06-30Minor formatting, whitespace, and 80-column fixes.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74492 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-27Change SCEVExpander to use an IRBuilder to emit instructions.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74391 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-26Incorporate the insertion point into the key of SCEVExpander's CSE map.Dan Gohman
This helps it avoid reusing an instruction that doesn't dominate all of the users, in cases where the original instruction was inserted before all of the users were known. This may result in redundant expansions of sub-expressions that depend on loop-unpredictable values in some cases, however this isn't very common, and it primarily impacts IndVarSimplify, so GVN can be expected to clean these up. This eliminates the need for IndVarSimplify's FixUsesBeforeDefs, which fixes several bugs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74352 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Extend ScalarEvolution's multiple-exit support to compute exactDan Gohman
trip counts in more cases. Generalize ScalarEvolution's isLoopGuardedByCond code to recognize And and Or conditions, splitting the code out into an isNecessaryCond helper function so that it can evaluate Ands and Ors recursively, and make SCEVExpander be much more aggressive about hoisting instructions out of loops. test/CodeGen/X86/pr3495.ll has an additional instruction now, but it appears to be due to an arbitrary register allocation difference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74048 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22Fix a few minor issues that were exposed by the removal of SCEVHandle.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73910 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-22SCEVHandle is no more!Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73906 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-15Support vector casts in more places, fixing a variety of assertionDan Gohman
failures. To support this, add some utility functions to Type to help support vector/scalar-independent code. Change ConstantInt::get and ConstantFP::get to support vector types, and add an overload to ConstantInt::get that uses a static IntegerType type, for convenience. Introduce a new getConstant method for ScalarEvolution, to simplify common use cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73431 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Convert several parts of the ScalarEvolution framework to useDan Gohman
SmallVector instead of std::vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73357 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-09Use expandCodeFor instead of expand when the result will beDan Gohman
immediately casted. At present, this is just a minor code simplification. In the future, the expansion code may be able to make better choices if it knows what the desired result type will be. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73137 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-05Move SCEVExpander::getOrInsertCanonicalInductionVariable out of line.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72949 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-27Add braces around an array initializer.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72453 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-24Instead of clearing the rewriter, don't attempt to rewrite dead phi nodes.Torok Edwin
Also fix 80 column violation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72371 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-24Fix this code for hosts where std::vector doesn't have .data().Dan Gohman
Use &Ops[0] instead, which is safe since Ops will never be empty here. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72368 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-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-19Create ConstantExpr GEPs the correct way. This fixesDan Gohman
MultiSource/Benchmarks/Prolangs-C/football and a variety of other failures. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72120 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-01Actually insert inserted instructions into the InsertedValues map.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70557 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-01Short-circuit inttoptr-ptrtoint constant expressions; these aren'tDan Gohman
always folded by the regular constant folder because it doesn't have TargetData information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70553 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-22Fix cut-n-pasto.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69816 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-22Use BasicBlock::iterator instead of Instruction* for insert points,Dan Gohman
to better handle inserting instructions at the end of a block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69807 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21Introduce encapsulation for ScalarEvolution's TargetData object, and refactorDan Gohman
the code to minimize dependencies on TargetData. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69644 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-18Use more const qualifiers with SCEV interfaces.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69450 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Handle a pointer type correctly in SCEVExpander::visitAddRecExpr.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69310 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Fix a bug with inttoptr/ptrtoint casts where the pointer has a differentDan Gohman
size from the integer, requiring zero extension or truncation. Don't create ZExtInsts with pointer types. This fixes a regression in consumer-jpeg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69307 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Fix SCEVExpander::visitSMaxExpr and SCEVExpander::visitUMaxExpr toDan Gohman
not create ICmpInsts with operands of different types. This fixes a regression in Applications/d/make_dparser. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69294 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Teach SCEVExpander::InsertCastOfTo to avoid creating inttoptr-of-ptrtointDan Gohman
and ptrtoint-of-inttoptr expressions. This fixes a regression in 300.twolf. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69293 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Expand GEPs in ScalarEvolution expressions. SCEV expressions can nowDan Gohman
have pointer types, though in contrast to C pointer types, SCEV addition is never implicitly scaled. This not only eliminates the need for special code like IndVars' EliminatePointerRecurrence and LSR's own GEP expansion code, it also does a better job because it lets the normal optimizations handle pointer expressions just like integer expressions. Also, since LLVM IR GEPs can't directly index into multi-dimensional VLAs, moving the GEP analysis out of client code and into the SCEV framework makes it easier for clients to handle multi-dimensional VLAs the same way as other arrays. Some existing regression tests show improved optimization. test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to the point where if-conversion started kicking in; I turned it off for this test to preserve the intent of the test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69258 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-13Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky
PR3296 and PR3302. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62160 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-02Add a new SCEV representing signed division.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60407 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-13do not use deprecated interfacesGabor Greif
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57433 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-08Expand SCEVUDiv of power of 2 to a lshr instruction.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53217 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-22Use SCEVAddRecExpr::isAffine.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52614 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-22Move a few more SCEVExpander methods out-of-line.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52612 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-18Move SCEVExpander::visitAddExpr out-of-line.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52464 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-18Move LSR's private isZero function to a public SCEV memberDan Gohman
function, and make use of it in several places. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52463 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-15Fix PR2434. When scanning for exising binary operator to reuse don't Wojciech Matyjewicz
take into account the instrucion pointed by InsertPt. Thanks to it, returning the new value of InsertPt to the InsertBinop() caller can be avoided. The bug was, actually, in visitAddRecExpr() method which wasn't correctly handling changes of InsertPt. There shouldn't be any performance regression, as -gvn pass (run after -indvars) removes any redundant binops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52291 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-14Change 'while' loop to 'do' loop.Wojciech Matyjewicz
Add a safety measure. It isn't safe to assume in ScalarEvolutionExpander that all loops are in canonical form (but it should be safe for loops that have AddRecs). xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52275 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-16API change for {BinaryOperator|CmpInst|CastInst}::create*() --> Create. ↵Gabor Greif
Legacy interfaces will be in place for some time. (Merge from use-diet branch.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51200 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-06API changes for class Use size reduction, wave 1.Gabor Greif
Specifically, introduction of XXX::Create methods for Users that have a potentially variable number of Uses. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49277 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-20Add 'umax' similar to 'smax' SCEV. Closes PR2003.Nick Lewycky
Parse reversed smax and umax as smin and umin and express them with negative or binary-not SCEVs (which are really just subtract under the hood). Parse 'xor %x, -1' as (-1 - %x). Remove dead code (ConstantInt::get always returns a ConstantInt). Don't use getIntegerSCEV(-1, Ty). The first value is an int, then it gets passed into a uint64_t. Instead, create the -1 directly from ConstantInt::getAllOnesValue(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47360 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-09We should check that existing cast operation has the appropriate opcode ↵Wojciech Matyjewicz
before we reuse it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46908 91177308-0d34-0410-b5e6-96231b3b80d8
2007-12-29Remove attribution from file headers, per discussion on llvmdev.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45418 91177308-0d34-0410-b5e6-96231b3b80d8
2007-11-25Add new SCEV, SCEVSMax. This allows LLVM to analyze do-while loops.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44319 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-02 20:34:21 +0000