summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Reapply the new LoopStrengthReduction code, with compile time andDan Gohman2010-02-121-2/+18
| | | | | | | | | | bug fixes, and with improved heuristics for analyzing foreign-loop addrecs. This change also flattens IVUsers, eliminating the stride-oriented groupings, which makes it easier to work with. llvm-svn: 95975
* Generalize target-independent folding rules for sizeof to handle moreDan Gohman2010-02-011-3/+3
| | | | | | | | | | | | | | | | | | | cases, and implement target-independent folding rules for alignof and offsetof. Also, reassociate reassociative operators when it leads to more folding. Generalize ScalarEvolution's isOffsetOf to recognize offsetof on arrays. Rename getAllocSizeExpr to getSizeOfExpr, and getFieldOffsetExpr to getOffsetOfExpr, for consistency with analagous ConstantExpr routines. Make the target-dependent folder promote GEP array indices to pointer-sized integers, to make implicit casting explicit and exposed to subsequent folding. And add a bunch of testcases for this new functionality, and a bunch of related existing functionality. llvm-svn: 94987
* Check Type::isSized before calling ScalarEvolution::getAllocSizeExpr,Dan Gohman2010-01-281-21/+23
| | | | | | rather than after. llvm-svn: 94742
* Remove SCEVAllocSizeExpr and SCEVFieldOffsetExpr, and in their placeDan Gohman2010-01-281-17/+9
| | | | | | | | | | | | | | | | use plain SCEVUnknowns with ConstantExpr::getSizeOf and ConstantExpr::getOffsetOf constants. This eliminates a bunch of special-case code. Also add code for pattern-matching these expressions, for clients that want to recognize them. Move ScalarEvolution's logic for expanding array and vector sizeof expressions into an element count times the element size, to expose the multiplication to subsequent folding, into the regular constant folder. llvm-svn: 94737
* When re-using an existing cast for a user, it's still necessary to callDan Gohman2010-01-211-1/+3
| | | | | | | rememberInstruction so that future users of that user will be inserted in the correct position. This fixes the Darwin selfhost. llvm-svn: 94070
* Re-implement the main strength-reduction portion of LoopStrengthReduction.Dan Gohman2010-01-211-18/+210
| | | | | | | | | | | | | | This new version is much more aggressive about doing "full" reduction in cases where it reduces register pressure, and also more aggressive about rewriting induction variables to count down (or up) to zero when doing so reduces register pressure. It currently uses fairly simplistic algorithms for finding reuse opportunities, but it introduces a new framework allows it to combine multiple strategies at once to form hybrid solutions, instead of doing all full-reduction or all base+index. llvm-svn: 94061
* Fix a typo and an 80-column violation in comments.Dan Gohman2010-01-191-3/+3
| | | | llvm-svn: 93931
* Fix a comment typo.Bob Wilson2009-12-041-1/+1
| | | | llvm-svn: 90511
* improve portability to avoid conflicting with std::next in c++'0x.Chris Lattner2009-12-031-2/+2
| | | | | | Patch by Howard Hinnant! llvm-svn: 90365
* Introduce and use convenience methods for getting pointer typesDuncan Sands2009-10-061-1/+1
| | | | | | | where the element is of a basic builtin type. For example, to get an i8* use getInt8PtrTy. llvm-svn: 83379
* When extending the operands of an addrec, iterate through allDan Gohman2009-09-281-5/+5
| | | | | | | the operands, rather than trying to partition them into a start and a step. This handles non-affine add recurrences correctly. llvm-svn: 83011
* Fix SCEVExpander's canonical addrec expansion code to work on loops thatDan Gohman2009-09-271-19/+12
| | | | | | | | aren't in canonical loop-simplify form, since it doesn't itself depend on LoopSimplify. This means handling loops without preheaders and loops with multiple backedges. llvm-svn: 82905
* Fix a case where ScalarEvolution was expanding pointer arithmeticDan Gohman2009-09-261-3/+20
| | | | | | to inttoptr/ptrtoint unnecessarily. llvm-svn: 82864
* Various comment and whitespace cleanups.Dan Gohman2009-08-201-8/+11
| | | | llvm-svn: 79533
* Generalize ScalarEvolution to be able to analyze GEPs whenDan Gohman2009-08-181-83/+230
| | | | | | | | 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. llvm-svn: 79344
* Push LLVMContexts through the IntegerType APIs.Owen Anderson2009-08-131-2/+3
| | | | llvm-svn: 78948
* Move a few more APIs back to 2.5 forms. The only remaining ones left to ↵Owen Anderson2009-07-311-3/+3
| | | | | | | | change back are metadata related, which I'm waiting on to avoid conflicting with Devang. llvm-svn: 77721
* Move ConstantExpr to 2.5 API.Owen Anderson2009-07-291-3/+3
| | | | llvm-svn: 77494
* Teach instcombine to respect and preserve inbounds. Add inboundsDan Gohman2009-07-281-1/+3
| | | | | | to a few tests where it is required for the expected transformation. llvm-svn: 77290
* Revert the ConstantInt constructors back to their 2.5 forms where possible, ↵Owen Anderson2009-07-241-5/+4
| | | | | | thanks to contexts-on-types. More to come. llvm-svn: 77011
* Get rid of the Pass+Context magic.Owen Anderson2009-07-221-10/+10
| | | | llvm-svn: 76702
* Update this comment.Dan Gohman2009-07-201-7/+5
| | | | llvm-svn: 76438
* Fix the expansion of umax and smax in the case where one or more ofDan Gohman2009-07-141-6/+26
| | | | | | | | 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. llvm-svn: 75680
* Change all SCEV* to SCEV *.Dan Gohman2009-07-071-29/+29
| | | | llvm-svn: 74918
* Finish LLVMContext-ing lib/Analysis. This required pushing LLVMContext's ↵Owen Anderson2009-07-061-10/+12
| | | | | | through the ValueTracking API. llvm-svn: 74873
* Minor formatting, whitespace, and 80-column fixes.Dan Gohman2009-06-301-7/+7
| | | | llvm-svn: 74492
* Change SCEVExpander to use an IRBuilder to emit instructions.Dan Gohman2009-06-271-72/+70
| | | | llvm-svn: 74391
* Incorporate the insertion point into the key of SCEVExpander's CSE map.Dan Gohman2009-06-261-14/+19
| | | | | | | | | | | | | | 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. llvm-svn: 74352
* Extend ScalarEvolution's multiple-exit support to compute exactDan Gohman2009-06-241-46/+58
| | | | | | | | | | | | | | | 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. llvm-svn: 74048
* Fix a few minor issues that were exposed by the removal of SCEVHandle.Dan Gohman2009-06-221-1/+1
| | | | llvm-svn: 73910
* SCEVHandle is no more!Owen Anderson2009-06-221-34/+34
| | | | llvm-svn: 73906
* Support vector casts in more places, fixing a variety of assertionDan Gohman2009-06-151-3/+1
| | | | | | | | | | | | | | | 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. llvm-svn: 73431
* Convert several parts of the ScalarEvolution framework to useDan Gohman2009-06-141-7/+9
| | | | | | SmallVector instead of std::vector. llvm-svn: 73357
* 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
OpenPOWER on IntegriCloud