aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolutionExpander.cpp
AgeCommit message (Collapse)Author
2010-02-17Fix SCEVExpander's existing PHI reuse checking to recognize theDan Gohman
case where there are loop-invariant instructions somehow left inside the loop, and in a position where they won't dominate the IV increment position. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96448 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-16There are two ways of checking for a given type, for example isa<PointerType>(T)Duncan Sands
and T->isPointerTy(). Convert most instances of the first form to the second form. Requested by Chris. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96344 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-16When reusing an existing PHI node in a loop, be even moreDan Gohman
strict about the requirements. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96301 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-15Uniformize the names of type predicates: rather than having isFloatTy andDuncan Sands
isInteger, we now have isFloatTy and isIntegerTy. Requested by Chris! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96223 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-15When restoring a saved insert location, check to see if the savedDan Gohman
insert location has become an "inserted" instruction since the time it was saved. If so, advance to the first non-"inserted" instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96203 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-14In rememberInstruction, if the value being remembered is theDan Gohman
current insertion point, advance the current insertion point. This avoids a use-before-def situation in a testcase extracted from clang which is difficult to reduce to a reasonable-sized regression test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96151 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Fix a case of mismatched types in an Add that turned up in 447.dealII.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96007 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-12Reapply the new LoopStrengthReduction code, with compile time andDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95975 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-01Generalize target-independent folding rules for sizeof to handle moreDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94987 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-28Check Type::isSized before calling ScalarEvolution::getAllocSizeExpr,Dan Gohman
rather than after. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94742 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-28Remove SCEVAllocSizeExpr and SCEVFieldOffsetExpr, and in their placeDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94737 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21When re-using an existing cast for a user, it's still necessary to callDan Gohman
rememberInstruction so that future users of that user will be inserted in the correct position. This fixes the Darwin selfhost. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94070 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-21Re-implement the main strength-reduction portion of LoopStrengthReduction.Dan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94061 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-19Fix a typo and an 80-column violation in comments.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93931 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-04Fix a comment typo.Bob Wilson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90511 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-03improve portability to avoid conflicting with std::next in c++'0x.Chris Lattner
Patch by Howard Hinnant! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90365 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-06Introduce and use convenience methods for getting pointer typesDuncan Sands
where the element is of a basic builtin type. For example, to get an i8* use getInt8PtrTy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83379 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-28When extending the operands of an addrec, iterate through allDan Gohman
the operands, rather than trying to partition them into a start and a step. This handles non-affine add recurrences correctly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83011 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-27Fix SCEVExpander's canonical addrec expansion code to work on loops thatDan Gohman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82905 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-26Fix a case where ScalarEvolution was expanding pointer arithmeticDan Gohman
to inttoptr/ptrtoint unnecessarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82864 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-20Various comment and whitespace cleanups.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79533 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-08-13Push LLVMContexts through the IntegerType APIs.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78948 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-31Move a few more APIs back to 2.5 forms. The only remaining ones left to ↵Owen Anderson
change back are metadata related, which I'm waiting on to avoid conflicting with Devang. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77721 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-29Move ConstantExpr to 2.5 API.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77494 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-28Teach instcombine to respect and preserve inbounds. Add inboundsDan Gohman
to a few tests where it is required for the expected transformation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77290 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-24Revert the ConstantInt constructors back to their 2.5 forms where possible, ↵Owen Anderson
thanks to contexts-on-types. More to come. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77011 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-22Get rid of the Pass+Context magic.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76702 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-20Update this comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76438 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-07Change all SCEV* to SCEV *.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74918 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-06Finish LLVMContext-ing lib/Analysis. This required pushing LLVMContext's ↵Owen Anderson
through the ValueTracking API. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74873 91177308-0d34-0410-b5e6-96231b3b80d8
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 21:19:42 +0000