/// 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());
// 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,
ScalarEvolution *SE);
- Value *InsertCodeForBaseAtPosition(const SCEV *const &NewBase,
+ Value *InsertCodeForBaseAtPosition(const SCEV *NewBase,
const Type *Ty,
SCEVExpander &Rewriter,
Instruction *IP,
}
void BasedUser::dump() const {
- errs() << " Base=" << *Base;
- errs() << " Imm=" << *Imm;
- errs() << " Inst: " << *Inst;
+ dbgs() << " Base=" << *Base;
+ dbgs() << " Imm=" << *Imm;
+ dbgs() << " Inst: " << *Inst;
}
-Value *BasedUser::InsertCodeForBaseAtPosition(const SCEV *const &NewBase,
+Value *BasedUser::InsertCodeForBaseAtPosition(const SCEV *NewBase,
const Type *Ty,
SCEVExpander &Rewriter,
Instruction *IP,
// 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,
// 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;
// Replace the use of the operand Value with the new Phi we just created.
Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
- DEBUG(errs() << " Replacing with ");
- DEBUG(WriteAsOperand(errs(), NewVal, /*PrintType=*/false));
- DEBUG(errs() << ", which has value " << *NewBase << " plus IMM "
+ DEBUG(dbgs() << " Replacing with ");
+ DEBUG(WriteAsOperand(dbgs(), NewVal, /*PrintType=*/false));
+ DEBUG(dbgs() << ", which has value " << *NewBase << " plus IMM "
<< *Imm << "\n");
return;
}
// 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, SE);
- DEBUG(errs() << " Changing PHI use to ");
- DEBUG(WriteAsOperand(errs(), Code, /*PrintType=*/false));
- DEBUG(errs() << ", which has value " << *NewBase << " plus IMM "
+ DEBUG(dbgs() << " Changing PHI use to ");
+ DEBUG(WriteAsOperand(dbgs(), Code, /*PrintType=*/false));
+ DEBUG(dbgs() << ", which has value " << *NewBase << " plus IMM "
<< *Imm << "\n");
}
/// 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 (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) {
/// 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 SCEV *CommonExprs,
const Loop *L,
SCEVExpander &PreheaderRewriter) {
- DEBUG(errs() << " Fully reducing all users\n");
+ DEBUG(dbgs() << " Fully reducing all users\n");
// Rewrite the UsersToProcess records, creating a separate PHI for each
// unique Base value.
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();
}
Instruction *IVIncInsertPt,
const Loop *L,
SCEVExpander &PreheaderRewriter) {
- DEBUG(errs() << " Inserting new PHI:\n");
+ DEBUG(dbgs() << " Inserting new PHI:\n");
PHINode *Phi = InsertAffinePhi(SE->getUnknown(CommonBaseV),
Stride, IVIncInsertPt, L,
for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i)
UsersToProcess[i].Phi = Phi;
- DEBUG(errs() << " IV=");
- DEBUG(WriteAsOperand(errs(), Phi, /*PrintType=*/false));
- DEBUG(errs() << "\n");
+ DEBUG(dbgs() << " IV=");
+ DEBUG(WriteAsOperand(dbgs(), Phi, /*PrintType=*/false));
+ DEBUG(dbgs() << "\n");
}
/// PrepareToStrengthReduceFromSmallerStride - Prepare for the given users to
Value *CommonBaseV,
const IVExpr &ReuseIV,
Instruction *PreInsertPt) {
- DEBUG(errs() << " Rewriting in terms of existing IV of STRIDE "
+ DEBUG(dbgs() << " Rewriting in terms of existing IV of STRIDE "
<< *ReuseIV.Stride << " and BASE " << *ReuseIV.Base << "\n");
// All the users will share the reused IV.
/// 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.
UsersToProcess, TLI);
if (DoSink) {
- DEBUG(errs() << " Sinking " << *Imm << " back down into uses\n");
+ DEBUG(dbgs() << " Sinking " << *Imm << " back down into uses\n");
for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i)
UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm, Imm);
CommonExprs = NewCommon;
// Now that we know what we need to do, insert the PHI node itself.
//
- DEBUG(errs() << "LSR: Examining IVs of TYPE " << *ReplacedTy << " of STRIDE "
+ DEBUG(dbgs() << "LSR: Examining IVs of TYPE " << *ReplacedTy << " of STRIDE "
<< *Stride << ":\n"
<< " Common base: " << *CommonExprs << "\n");
if (!Base->isZero()) {
BaseV = PreheaderRewriter.expandCodeFor(Base, 0, PreInsertPt);
- DEBUG(errs() << " INSERTING code for BASE = " << *Base << ":");
+ DEBUG(dbgs() << " INSERTING code for BASE = " << *Base << ":");
if (BaseV->hasName())
- DEBUG(errs() << " Result value name = %" << BaseV->getName());
- DEBUG(errs() << "\n");
+ DEBUG(dbgs() << " Result value name = %" << BaseV->getName());
+ DEBUG(dbgs() << "\n");
// If BaseV is a non-zero constant, make sure that it gets inserted into
// the preheader, instead of being forward substituted into the uses. We
// FIXME: Use emitted users to emit other users.
BasedUser &User = UsersToProcess.back();
- DEBUG(errs() << " Examining ");
+ DEBUG(dbgs() << " Examining ");
if (User.isUseOfPostIncrementedValue)
- DEBUG(errs() << "postinc");
+ DEBUG(dbgs() << "postinc");
else
- DEBUG(errs() << "preinc");
- DEBUG(errs() << " use ");
- DEBUG(WriteAsOperand(errs(), UsersToProcess.back().OperandValToReplace,
+ DEBUG(dbgs() << "preinc");
+ DEBUG(dbgs() << " use ");
+ DEBUG(WriteAsOperand(dbgs(), UsersToProcess.back().OperandValToReplace,
/*PrintType=*/false));
- DEBUG(errs() << " in Inst: " << *User.Inst);
+ DEBUG(dbgs() << " in Inst: " << *User.Inst);
// If this instruction wants to use the post-incremented value, move it
// after the post-inc and use its value instead of the PHI.
// 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
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) {
Cond = new ICmpInst(OldCond, Predicate, NewCmpLHS, NewCmpRHS,
L->getHeader()->getName() + ".termcond");
- DEBUG(errs() << " Change compare stride in Inst " << *OldCond);
- DEBUG(errs() << " to " << *Cond << '\n');
+ DEBUG(dbgs() << " Change compare stride in Inst " << *OldCond);
+ DEBUG(dbgs() << " to " << *Cond << '\n');
// Remove the old compare instruction. The old indvar is probably dead too.
DeadInsts.push_back(CondUse->getOperandValToReplace());
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()))
if (!UsePostInc)
continue;
- DEBUG(errs() << " Change loop exiting icmp to use postinc iv: "
+ DEBUG(dbgs() << " Change loop exiting icmp to use postinc iv: "
<< *Cond << '\n');
// It's possible for the setcc instruction to be anywhere in the loop, and
}
// Replace the increment with a decrement.
- DEBUG(errs() << "LSR: Examining use ");
- DEBUG(WriteAsOperand(errs(), CondOp0, /*PrintType=*/false));
- DEBUG(errs() << " in Inst: " << *Cond << '\n');
+ DEBUG(dbgs() << "LSR: Examining use ");
+ DEBUG(WriteAsOperand(dbgs(), CondOp0, /*PrintType=*/false));
+ DEBUG(dbgs() << " in Inst: " << *Cond << '\n');
BinaryOperator *Decr = BinaryOperator::Create(Instruction::Sub,
Incr->getOperand(0), Incr->getOperand(1), "tmp", Incr);
Incr->replaceAllUsesWith(Decr);
unsigned InBlock = L->contains(PHIExpr->getIncomingBlock(0)) ? 1 : 0;
Value *StartVal = PHIExpr->getIncomingValue(InBlock);
Value *EndVal = Cond->getOperand(1);
- DEBUG(errs() << " Optimize loop counting iv to count down ["
+ DEBUG(dbgs() << " Optimize loop counting iv to count down ["
<< *EndVal << " .. " << *StartVal << "]\n");
// FIXME: check for case where both are constant.
EndVal, StartVal, "tmp", PreInsertPt);
PHIExpr->setIncomingValue(InBlock, NewStartVal);
Cond->setOperand(1, Zero);
- DEBUG(errs() << " New icmp: " << *Cond << "\n");
+ DEBUG(dbgs() << " New icmp: " << *Cond << "\n");
int64_t SInt = cast<SCEVConstant>(Stride)->getValue()->getSExtValue();
const SCEV *NewStride = 0;
return false;
if (!IU->IVUsesByStride.empty()) {
- DEBUG(errs() << "\nLSR on \"" << L->getHeader()->getParent()->getName()
+ DEBUG(dbgs() << "\nLSR on \"" << L->getHeader()->getParent()->getName()
<< "\" ";
- L->dump());
+ L->print(dbgs()));
// Sort the StrideOrder so we process larger strides first.
std::stable_sort(IU->StrideOrder.begin(), IU->StrideOrder.end(),
IVsByStride.clear();
// Clean up after ourselves
- if (!DeadInsts.empty())
- DeleteTriviallyDeadInstructions();
+ 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.
- DeleteDeadPHIs(L->getHeader());
+ Changed |= DeleteDeadPHIs(L->getHeader());
return Changed;
}