#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
-#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/IVUsers.h"
-#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/AddrModeMatcher.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ValueHandle.h"
class LoopStrengthReduce : public LoopPass {
IVUsers *IU;
- LoopInfo *LI;
ScalarEvolution *SE;
bool Changed;
/// particular stride.
std::map<const SCEV *, IVsOfOneStride> IVsByStride;
- /// StrideNoReuse - Keep track of all the strides whose ivs cannot be
- /// reused (nor should they be rewritten to reuse other strides).
- SmallSet<const SCEV *, 4> StrideNoReuse;
-
/// DeadInsts - Keep track of instructions we may have made dead, so that
/// we can remove them after we are done working.
SmallVector<WeakVH, 16> DeadInsts;
// We split critical edges, so we change the CFG. However, we do update
// many analyses if they are around.
AU.addPreservedID(LoopSimplifyID);
- AU.addPreserved<LoopInfo>();
+ AU.addPreserved("loops");
AU.addPreserved("domfrontier");
AU.addPreserved("domtree");
AU.addRequiredID(LoopSimplifyID);
- AU.addRequired<LoopInfo>();
AU.addRequired<ScalarEvolution>();
AU.addPreserved<ScalarEvolution>();
AU.addRequired<IVUsers>();
/// StrengthReduceIVUsersOfStride - Strength reduce all of the users of a
/// single stride of IV. All of the users may have different starting
/// values, and this may not be the only stride.
- void StrengthReduceIVUsersOfStride(const SCEV *const &Stride,
+ void StrengthReduceIVUsersOfStride(const SCEV *Stride,
IVUsersOfOneStride &Uses,
Loop *L);
void StrengthReduceIVUsers(Loop *L);
bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
const SCEV* &CondStride);
bool RequiresTypeConversion(const Type *Ty, const Type *NewTy);
- const SCEV *CheckForIVReuse(bool, bool, bool, const SCEV *const&,
+ const SCEV *CheckForIVReuse(bool, bool, bool, const SCEV *,
IVExpr&, const Type*,
const std::vector<BasedUser>& UsersToProcess);
bool ValidScale(bool, int64_t,
const std::vector<BasedUser>& UsersToProcess);
bool ValidOffset(bool, int64_t, int64_t,
const std::vector<BasedUser>& UsersToProcess);
- const SCEV *CollectIVUsers(const SCEV *const &Stride,
+ const SCEV *CollectIVUsers(const SCEV *Stride,
IVUsersOfOneStride &Uses,
Loop *L,
bool &AllUsesAreAddresses,
/// specified set are trivially dead, delete them and see if this makes any of
/// their operands subsequently dead.
void LoopStrengthReduce::DeleteTriviallyDeadInstructions() {
- if (DeadInsts.empty()) return;
-
while (!DeadInsts.empty()) {
Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
}
}
-/// containsAddRecFromDifferentLoop - Determine whether expression S involves a
-/// subexpression that is an AddRec from a loop other than L. An outer loop
-/// of L is OK, but not an inner loop nor a disjoint loop.
-static bool containsAddRecFromDifferentLoop(const SCEV *S, Loop *L) {
- // This is very common, put it first.
- if (isa<SCEVConstant>(S))
- return false;
- if (const SCEVCommutativeExpr *AE = dyn_cast<SCEVCommutativeExpr>(S)) {
- for (unsigned int i=0; i< AE->getNumOperands(); i++)
- if (containsAddRecFromDifferentLoop(AE->getOperand(i), L))
- return true;
- return false;
- }
- if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) {
- if (const Loop *newLoop = AE->getLoop()) {
- if (newLoop == L)
- return false;
- // if newLoop is an outer loop of L, this is OK.
- if (!LoopInfo::isNotAlreadyContainedIn(L, newLoop))
- return false;
- }
- return true;
- }
- if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S))
- return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
- containsAddRecFromDifferentLoop(DE->getRHS(), L);
-#if 0
- // SCEVSDivExpr has been backed out temporarily, but will be back; we'll
- // need this when it is.
- if (const SCEVSDivExpr *DE = dyn_cast<SCEVSDivExpr>(S))
- return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
- containsAddRecFromDifferentLoop(DE->getRHS(), L);
-#endif
- if (const SCEVCastExpr *CE = dyn_cast<SCEVCastExpr>(S))
- return containsAddRecFromDifferentLoop(CE->getOperand(), L);
- return false;
-}
-
/// isAddressUse - Returns true if the specified instruction is using the
/// specified value as an address.
static bool isAddressUse(Instruction *Inst, Value *OperandVal) {
/// BasedUser - For a particular base value, keep information about how we've
/// partitioned the expression so far.
struct BasedUser {
- /// SE - The current ScalarEvolution object.
- ScalarEvolution *SE;
-
/// Base - The Base value for the PHI node that needs to be inserted for
/// this use. As the use is processed, information gets moved from this
/// field to the Imm field (below). BasedUser values are sorted by this
bool isUseOfPostIncrementedValue;
BasedUser(IVStrideUse &IVSU, ScalarEvolution *se)
- : SE(se), Base(IVSU.getOffset()), Inst(IVSU.getUser()),
+ : Base(IVSU.getOffset()), Inst(IVSU.getUser()),
OperandValToReplace(IVSU.getOperandValToReplace()),
- Imm(SE->getIntegerSCEV(0, Base->getType())),
+ Imm(se->getIntegerSCEV(0, Base->getType())),
isUseOfPostIncrementedValue(IVSU.isUseOfPostIncrementedValue()) {}
// Once we rewrite the code to insert the new IVs we want, update the
// operands of Inst to use the new expression 'NewBase', with 'Imm' added
// to it.
- void RewriteInstructionToUseNewBase(const SCEV *const &NewBase,
+ void RewriteInstructionToUseNewBase(const SCEV *NewBase,
Instruction *InsertPt,
SCEVExpander &Rewriter, Loop *L, Pass *P,
- SmallVectorImpl<WeakVH> &DeadInsts);
+ SmallVectorImpl<WeakVH> &DeadInsts,
+ ScalarEvolution *SE);
- Value *InsertCodeForBaseAtPosition(const SCEV *const &NewBase,
+ Value *InsertCodeForBaseAtPosition(const SCEV *NewBase,
const Type *Ty,
SCEVExpander &Rewriter,
- Instruction *IP);
+ Instruction *IP,
+ ScalarEvolution *SE);
void dump() const;
};
}
errs() << " Inst: " << *Inst;
}
-Value *BasedUser::InsertCodeForBaseAtPosition(const SCEV *const &NewBase,
+Value *BasedUser::InsertCodeForBaseAtPosition(const SCEV *NewBase,
const Type *Ty,
SCEVExpander &Rewriter,
- Instruction *IP) {
+ Instruction *IP,
+ ScalarEvolution *SE) {
Value *Base = Rewriter.expandCodeFor(NewBase, 0, IP);
// Wrap the base in a SCEVUnknown so that ScalarEvolution doesn't try to
// value of NewBase in the case that it's a diffferent instruction from
// the PHI that NewBase is computed from, or null otherwise.
//
-void BasedUser::RewriteInstructionToUseNewBase(const SCEV *const &NewBase,
+void BasedUser::RewriteInstructionToUseNewBase(const SCEV *NewBase,
Instruction *NewBasePt,
SCEVExpander &Rewriter, Loop *L, Pass *P,
- SmallVectorImpl<WeakVH> &DeadInsts) {
+ SmallVectorImpl<WeakVH> &DeadInsts,
+ ScalarEvolution *SE) {
if (!isa<PHINode>(Inst)) {
// By default, insert code at the user instruction.
BasicBlock::iterator InsertPt = Inst;
// If this is a use outside the loop (which means after, since it is based
// on a loop indvar) we use the post-incremented value, so that we don't
// artificially make the preinc value live out the bottom of the loop.
- if (!isUseOfPostIncrementedValue && L->contains(Inst->getParent())) {
+ if (!isUseOfPostIncrementedValue && L->contains(Inst)) {
if (NewBasePt && isa<PHINode>(OperandValToReplace)) {
InsertPt = NewBasePt;
++InsertPt;
}
Value *NewVal = InsertCodeForBaseAtPosition(NewBase,
OperandValToReplace->getType(),
- Rewriter, InsertPt);
+ Rewriter, InsertPt, SE);
// Replace the use of the operand Value with the new Phi we just created.
Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
// that case(?).
Instruction *OldLoc = dyn_cast<Instruction>(OperandValToReplace);
BasicBlock *PHIPred = PN->getIncomingBlock(i);
- if (L->contains(OldLoc->getParent())) {
+ if (L->contains(OldLoc)) {
// If this is a critical edge, split the edge so that we do not insert
// the code on all predecessor/successor paths. We do this unless this
// is the canonical backedge for this loop, as this can make some
// is outside of the loop, and PredTI is in the loop, we want to
// move the block to be immediately before the PHI block, not
// immediately after PredTI.
- if (L->contains(PHIPred) && !L->contains(PN->getParent()))
+ if (L->contains(PHIPred) && !L->contains(PN))
NewBB->moveBefore(PN->getParent());
// Splitting the edge can reduce the number of PHI entries we have.
Value *&Code = InsertedCode[PHIPred];
if (!Code) {
// Insert the code into the end of the predecessor block.
- Instruction *InsertPt = (L->contains(OldLoc->getParent())) ?
+ Instruction *InsertPt = (L->contains(OldLoc)) ?
PHIPred->getTerminator() :
OldLoc->getParent()->getTerminator();
Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(),
- Rewriter, InsertPt);
+ Rewriter, InsertPt, SE);
DEBUG(errs() << " Changing PHI use to ");
DEBUG(WriteAsOperand(errs(), Code, /*PrintType=*/false));
/// fitsInAddressMode - Return true if V can be subsumed within an addressing
/// mode, and does not need to be put in a register first.
-static bool fitsInAddressMode(const SCEV *const &V, const Type *AccessTy,
+static bool fitsInAddressMode(const SCEV *V, const Type *AccessTy,
const TargetLowering *TLI, bool HasBaseReg) {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
int64_t VC = SC->getValue()->getSExtValue();
// it is clearly shared across all the IV's. If the use is outside the loop
// (which means after it) we don't want to factor anything *into* the loop,
// so just use 0 as the base.
- if (L->contains(Uses[0].Inst->getParent()))
+ if (L->contains(Uses[0].Inst))
std::swap(Result, Uses[0].Base);
return Result;
}
// after the loop to affect base computation of values *inside* the loop,
// because we can always add their offsets to the result IV after the loop
// is done, ensuring we get good code inside the loop.
- if (!L->contains(Uses[i].Inst->getParent()))
+ if (!L->contains(Uses[i].Inst))
continue;
NumUsesInsideLoop++;
// and a Result in the same instruction (for example because it would
// require too many registers). Check this.
for (unsigned i=0; i<NumUses; ++i) {
- if (!L->contains(Uses[i].Inst->getParent()))
+ if (!L->contains(Uses[i].Inst))
continue;
// We know this is an addressing mode use; if there are any uses that
// are not, FreeResult would be Zero.
// the final IV value coming into those uses does. Instead of trying to
// remove the pieces of the common base, which might not be there,
// subtract off the base to compensate for this.
- if (!L->contains(Uses[i].Inst->getParent())) {
+ if (!L->contains(Uses[i].Inst)) {
Uses[i].Base = SE->getMinusSCEV(Uses[i].Base, Result);
continue;
}
const SCEV *LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg,
bool AllUsesAreAddresses,
bool AllUsesAreOutsideLoop,
- const SCEV *const &Stride,
+ const SCEV *Stride,
IVExpr &IV, const Type *Ty,
const std::vector<BasedUser>& UsersToProcess) {
- if (StrideNoReuse.count(Stride))
- return SE->getIntegerSCEV(0, Stride->getType());
-
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) {
int64_t SInt = SC->getValue()->getSExtValue();
for (unsigned NewStride = 0, e = IU->StrideOrder.size();
NewStride != e; ++NewStride) {
std::map<const SCEV *, IVsOfOneStride>::iterator SI =
IVsByStride.find(IU->StrideOrder[NewStride]);
- if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first) ||
- StrideNoReuse.count(SI->first))
+ if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first))
continue;
// The other stride has no uses, don't reuse it.
std::map<const SCEV *, IVUsersOfOneStride *>::iterator UI =
/// isNonConstantNegative - Return true if the specified scev is negated, but
/// not a constant.
-static bool isNonConstantNegative(const SCEV *const &Expr) {
+static bool isNonConstantNegative(const SCEV *Expr) {
const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Expr);
if (!Mul) return false;
/// base of the strided accesses, as well as the old information from Uses. We
/// progressively move information from the Base field to the Imm field, until
/// we eventually have the full access expression to rewrite the use.
-const SCEV *LoopStrengthReduce::CollectIVUsers(const SCEV *const &Stride,
+const SCEV *LoopStrengthReduce::CollectIVUsers(const SCEV *Stride,
IVUsersOfOneStride &Uses,
Loop *L,
bool &AllUsesAreAddresses,
// If the user is not in the current loop, this means it is using the exit
// value of the IV. Do not put anything in the base, make sure it's all in
// the immediate field to allow as much factoring as possible.
- if (!L->contains(UsersToProcess[i].Inst->getParent())) {
+ if (!L->contains(UsersToProcess[i].Inst)) {
UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm,
UsersToProcess[i].Base);
UsersToProcess[i].Base =
const Loop *L) {
if (UsersToProcess.size() == 1 &&
UsersToProcess[0].isUseOfPostIncrementedValue &&
- L->contains(UsersToProcess[0].Inst->getParent()))
+ L->contains(UsersToProcess[0].Inst))
return UsersToProcess[0].Inst;
return L->getLoopLatch()->getTerminator();
}
/// stride of IV. All of the users may have different starting values, and this
/// may not be the only stride.
void
-LoopStrengthReduce::StrengthReduceIVUsersOfStride(const SCEV *const &Stride,
+LoopStrengthReduce::StrengthReduceIVUsersOfStride(const SCEV *Stride,
IVUsersOfOneStride &Uses,
Loop *L) {
// If all the users are moved to another stride, then there is nothing to do.
// loop to ensure it is dominated by the increment. In case it's the
// only use of the iv, the increment instruction is already before the
// use.
- if (L->contains(User.Inst->getParent()) && User.Inst != IVIncInsertPt)
+ if (L->contains(User.Inst) && User.Inst != IVIncInsertPt)
User.Inst->moveBefore(IVIncInsertPt);
}
// common base, and are adding it back here. Use the same expression
// as before, rather than CommonBaseV, so DAGCombiner will zap it.
if (!CommonExprs->isZero()) {
- if (L->contains(User.Inst->getParent()))
+ if (L->contains(User.Inst))
RewriteExpr = SE->getAddExpr(RewriteExpr,
SE->getUnknown(CommonBaseV));
else
User.RewriteInstructionToUseNewBase(RewriteExpr, NewBasePt,
Rewriter, L, this,
- DeadInsts);
+ DeadInsts, SE);
// Mark old value we replaced as possibly dead, so that it is eliminated
// if we just replaced the last use of that value.
const ScalarEvolution *SE;
explicit StrideCompare(const ScalarEvolution *se) : SE(se) {}
- bool operator()(const SCEV *const &LHS, const SCEV *const &RHS) {
+ bool operator()(const SCEV *LHS, const SCEV *RHS) {
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS);
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS);
if (LHSC && RHSC) {
static bool ShouldCountToZero(ICmpInst *Cond, IVStrideUse* &CondUse,
ScalarEvolution *SE, Loop *L,
const TargetLowering *TLI = 0) {
- if (!L->contains(Cond->getParent()))
+ if (!L->contains(Cond))
return false;
if (!isa<SCEVConstant>(CondUse->getOffset()))
bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) {
IU = &getAnalysis<IVUsers>();
- LI = &getAnalysis<LoopInfo>();
SE = &getAnalysis<ScalarEvolution>();
Changed = false;
// After all sharing is done, see if we can adjust the loop to test against
// zero instead of counting up to a maximum. This is usually faster.
OptimizeLoopCountIV(L);
- }
- // We're done analyzing this loop; release all the state we built up for it.
- IVsByStride.clear();
- StrideNoReuse.clear();
+ // We're done analyzing this loop; release all the state we built up for it.
+ IVsByStride.clear();
- // Clean up after ourselves
- if (!DeadInsts.empty())
+ // Clean up after ourselves
DeleteTriviallyDeadInstructions();
+ }
// At this point, it is worth checking to see if any recurrence PHIs are also
// dead, so that we can remove them as well.
projects / oota-llvm.git / blobdiff