summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Teach SCEVExpander's visitAddRecExpr to reuse an existing canonicalDan Gohman2009-06-131-8/+51
| | | | | | | | | | | | | | | | | 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. llvm-svn: 73294
* Use expandCodeFor instead of expand when the result will beDan Gohman2009-06-091-29/+18
| | | | | | | | | 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. llvm-svn: 73137
* Move SCEVExpander::getOrInsertCanonicalInductionVariable out of line.Dan Gohman2009-06-051-0/+13
| | | | llvm-svn: 72949
* Add braces around an array initializer.Dan Gohman2009-05-271-1/+1
| | | | llvm-svn: 72453
* Teach SCEVExpander to avoid creating over-indexed GEP indices whenDan Gohman2009-05-271-10/+25
| | | | | | | | | | | | 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 llvm-svn: 72452
* In cases where a pointer value is an operand of a multiplication orDan Gohman2009-05-261-3/+8
| | | | | | | division operation, don't attempt to use the operation's value as the base of a getelementptr. This fixes PR4271. llvm-svn: 72422
* Instead of clearing the rewriter, don't attempt to rewrite dead phi nodes.Torok Edwin2009-05-241-1/+2
| | | | | | Also fix 80 column violation. llvm-svn: 72371
* Fix this code for hosts where std::vector doesn't have .data().Dan Gohman2009-05-241-1/+1
| | | | | | Use &Ops[0] instead, which is safe since Ops will never be empty here. llvm-svn: 72368
* Generalize SCEVExpander::visitAddRecExpr's GEP persuit, and avoidDan Gohman2009-05-241-51/+140
| | | | | | | | | | | | | | | 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. llvm-svn: 72366
* The rewriter may hold references to instructions that are deleted because ↵Torok Edwin2009-05-241-1/+1
| | | | | | | | | | | 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. llvm-svn: 72364
* Fix a thinko in the code that adapted SCEVMulExpr operands forDan Gohman2009-05-221-3/+13
| | | | | | | use in expanding SCEVAddExprs with GEPs. The operands of a SCEVMulExpr need to be multiplied together, not added. llvm-svn: 72250
* Create ConstantExpr GEPs the correct way. This fixesDan Gohman2009-05-191-1/+1
| | | | | | | MultiSource/Benchmarks/Prolangs-C/football and a variety of other failures. llvm-svn: 72120
* Teach SCEVExpander to expand arithmetic involving pointers into GEPDan Gohman2009-05-191-16/+161
| | | | | | | | | | | | | | | | 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. llvm-svn: 72093
* Actually insert inserted instructions into the InsertedValues map.Dan Gohman2009-05-011-11/+33
| | | | llvm-svn: 70557
* Short-circuit inttoptr-ptrtoint constant expressions; these aren'tDan Gohman2009-05-011-1/+8
| | | | | | | always folded by the regular constant folder because it doesn't have TargetData information. llvm-svn: 70553
* Change SCEVExpander's expandCodeFor to provide more flexibilityDan Gohman2009-04-231-3/+1
| | | | | | | | | | | 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. llvm-svn: 69892
* Fix cut-n-pasto.Devang Patel2009-04-221-2/+2
| | | | llvm-svn: 69816
* SCEVExpander's InsertCastOfTo knows how to move existing castDan Gohman2009-04-221-0/+5
| | | | | | | | | | | 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. llvm-svn: 69808
* Use BasicBlock::iterator instead of Instruction* for insert points,Dan Gohman2009-04-221-7/+7
| | | | | | to better handle inserting instructions at the end of a block. llvm-svn: 69807
* Introduce encapsulation for ScalarEvolution's TargetData object, and refactorDan Gohman2009-04-211-50/+49
| | | | | | the code to minimize dependencies on TargetData. llvm-svn: 69644
* Use more const qualifiers with SCEV interfaces.Dan Gohman2009-04-181-12/+12
| | | | llvm-svn: 69450
* Handle a pointer type correctly in SCEVExpander::visitAddRecExpr.Dan Gohman2009-04-161-0/+2
| | | | llvm-svn: 69310
* Fix a bug with inttoptr/ptrtoint casts where the pointer has a differentDan Gohman2009-04-161-2/+6
| | | | | | | | size from the integer, requiring zero extension or truncation. Don't create ZExtInsts with pointer types. This fixes a regression in consumer-jpeg. llvm-svn: 69307
* Fix SCEVExpander::visitSMaxExpr and SCEVExpander::visitUMaxExpr toDan Gohman2009-04-161-0/+8
| | | | | | | not create ICmpInsts with operands of different types. This fixes a regression in Applications/d/make_dparser. llvm-svn: 69294
* Teach SCEVExpander::InsertCastOfTo to avoid creating inttoptr-of-ptrtointDan Gohman2009-04-161-0/+8
| | | | | | and ptrtoint-of-inttoptr expressions. This fixes a regression in 300.twolf. llvm-svn: 69293
* Expand GEPs in ScalarEvolution expressions. SCEV expressions can nowDan Gohman2009-04-161-12/+47
| | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 69258
* Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky2009-01-131-9/+0
| | | | | | PR3296 and PR3302. llvm-svn: 62160
* Add a new SCEV representing signed division.Nick Lewycky2008-12-021-0/+9
| | | | llvm-svn: 60407
* do not use deprecated interfacesGabor Greif2008-10-131-3/+3
| | | | llvm-svn: 57433
* Expand SCEVUDiv of power of 2 to a lshr instruction.Nick Lewycky2008-07-081-0/+14
| | | | llvm-svn: 53217
* Use SCEVAddRecExpr::isAffine.Dan Gohman2008-06-221-2/+2
| | | | llvm-svn: 52614
* Move a few more SCEVExpander methods out-of-line.Dan Gohman2008-06-221-0/+21
| | | | llvm-svn: 52612
* Move SCEVExpander::visitAddExpr out-of-line.Dan Gohman2008-06-181-0/+10
| | | | llvm-svn: 52464
* Move LSR's private isZero function to a public SCEV memberDan Gohman2008-06-181-2/+1
| | | | | | function, and make use of it in several places. llvm-svn: 52463
* Fix PR2434. When scanning for exising binary operator to reuse don't Wojciech Matyjewicz2008-06-151-15/+15
| | | | | | | | | | | 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. llvm-svn: 52291
* Change 'while' loop to 'do' loop.Wojciech Matyjewicz2008-06-141-4/+11
| | | | | | | | | 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 llvm-svn: 52275
* API change for {BinaryOperator|CmpInst|CastInst}::create*() --> Create. ↵Gabor Greif2008-05-161-4/+4
| | | | | | Legacy interfaces will be in place for some time. (Merge from use-diet branch.) llvm-svn: 51200
* API changes for class Use size reduction, wave 1.Gabor Greif2008-04-061-3/+3
| | | | | | | | Specifically, introduction of XXX::Create methods for Users that have a potentially variable number of Uses. llvm-svn: 49277
* Add 'umax' similar to 'smax' SCEV. Closes PR2003.Nick Lewycky2008-02-201-1/+10
| | | | | | | | | | | | | | | 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(). llvm-svn: 47360
* We should check that existing cast operation has the appropriate opcode ↵Wojciech Matyjewicz2008-02-091-19/+21
| | | | | | before we reuse it. llvm-svn: 46908
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | llvm-svn: 45418
* Add new SCEV, SCEVSMax. This allows LLVM to analyze do-while loops.Nick Lewycky2007-11-251-0/+10
| | | | llvm-svn: 44319
* Move the SCEV object factors from being static members of the individualDan Gohman2007-10-221-5/+5
| | | | | | | SCEV subclasses to being non-static member functions of the ScalarEvolution class. llvm-svn: 43224
* Change "tmp." to "tmp" for temporaries created by ScalarEvolutionExpanderDan Gohman2007-09-141-1/+1
| | | | | | for consistency with many other transforms. llvm-svn: 41957
* - Use correct header for SCEV inside LoopPass.cppAnton Korobeynikov2007-08-201-0/+12
| | | | | | - Move SCEVExpander::expand() out-of-line workarounding possible toolchain bug llvm-svn: 41197
* Fold a binary operator with constant operands when expanding code for a SCEV.Dan Gohman2007-06-151-0/+5
| | | | llvm-svn: 37602
* Add a SCEV class and supporting code for sign-extend expressions.Dan Gohman2007-06-151-7/+6
| | | | | | | | | | This created an ambiguity for expandInTy to decide when to use sign-extension or zero-extension, but it turns out that most of its callers don't actually need a type conversion, now that LLVM types don't have explicit signedness. Drop expandInTy in favor of plain expand, and change the few places that actually need a type conversion to do it themselves. llvm-svn: 37591
* Be more careful when inserting reused instructions. This fixes ↵Chris Lattner2007-04-171-2/+7
| | | | | | CodeGen/Generic/2007-04-17-lsr-crash.ll llvm-svn: 36231
* CSE simple binary expressions when they are inserted. This makes LSR produceChris Lattner2007-04-131-5/+25
| | | | | | less huge code that needs to be cleaned up by sdisel. llvm-svn: 35959
* Prefer non-virtual calls to ConstantInt::isZero over virtual calls toReid Spencer2007-03-021-1/+1
| | | | | | Constant::isNullValue() in situations where it is possible. llvm-svn: 34821
OpenPOWER on IntegriCloud