indvars: Prototyping Sign/ZeroExtend elimination without canonical IVs.
No functionality enabled by default. Use -disable-iv-rewrite.
Extended IVUsers to keep track of the phi that represents the users' IV.
Added the WidenIV transform to replace a narrow IV with a wide IV
by doing a one-for-one replacement of IV users instead of expanding the
SCEV expressions. [sz]exts are removed and truncs are inserted.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131744 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index ea38027..bc3bc30 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -109,13 +109,13 @@
private:
bool isValidRewrite(Value *FromVal, Value *ToVal);
- void SimplifyIVUsers();
+ void SimplifyIVUsers(SCEVExpander &Rewriter);
void EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
void EliminateIVRemainder(BinaryOperator *Rem,
Value *IVOperand,
- bool IsSigned);
+ bool IsSigned,
+ PHINode *IVPhi);
void RewriteNonIntegerIVs(Loop *L);
- const Type *WidenIVs(Loop *L, SCEVExpander &Rewriter);
bool canExpandBackedgeTakenCount(Loop *L,
const SCEV *BackedgeTakenCount);
@@ -454,29 +454,357 @@
SE->forgetLoop(L);
}
+namespace {
+ // Collect information about induction variables that are used by sign/zero
+ // extend operations. This information is recorded by CollectExtend and
+ // provides the input to WidenIV.
+ struct WideIVInfo {
+ const Type *WidestNativeType; // Widest integer type created [sz]ext
+ bool IsSigned; // Was an sext user seen before a zext?
+
+ WideIVInfo() : WidestNativeType(0), IsSigned(false) {}
+ };
+ typedef std::map<PHINode *, WideIVInfo> WideIVMap;
+}
+
+/// CollectExtend - Update information about the induction variable that is
+/// extended by this sign or zero extend operation. This is used to determine
+/// the final width of the IV before actually widening it.
+static void CollectExtend(CastInst *Cast, PHINode *Phi, bool IsSigned,
+ WideIVMap &IVMap, ScalarEvolution *SE,
+ const TargetData *TD) {
+ const Type *Ty = Cast->getType();
+ uint64_t Width = SE->getTypeSizeInBits(Ty);
+ if (TD && !TD->isLegalInteger(Width))
+ return;
+
+ WideIVInfo &IVInfo = IVMap[Phi];
+ if (!IVInfo.WidestNativeType) {
+ IVInfo.WidestNativeType = SE->getEffectiveSCEVType(Ty);
+ IVInfo.IsSigned = IsSigned;
+ return;
+ }
+
+ // We extend the IV to satisfy the sign of its first user, arbitrarily.
+ if (IVInfo.IsSigned != IsSigned)
+ return;
+
+ if (Width > SE->getTypeSizeInBits(IVInfo.WidestNativeType))
+ IVInfo.WidestNativeType = SE->getEffectiveSCEVType(Ty);
+}
+
+namespace {
+/// WidenIV - The goal of this transform is to remove sign and zero extends
+/// without creating any new induction variables. To do this, it creates a new
+/// phi of the wider type and redirects all users, either removing extends or
+/// inserting truncs whenever we stop propagating the type.
+///
+class WidenIV {
+ PHINode *OrigPhi;
+ const Type *WideType;
+ bool IsSigned;
+
+ IVUsers *IU;
+ LoopInfo *LI;
+ Loop *L;
+ ScalarEvolution *SE;
+ SmallVectorImpl<WeakVH> &DeadInsts;
+
+ PHINode *WidePhi;
+ Instruction *WideInc;
+ const SCEV *WideIncExpr;
+
+ SmallPtrSet<Instruction*,16> Processed;
+
+public:
+ WidenIV(PHINode *PN, const WideIVInfo &IVInfo, IVUsers *IUsers,
+ LoopInfo *LInfo, ScalarEvolution *SEv, SmallVectorImpl<WeakVH> &DI) :
+ OrigPhi(PN),
+ WideType(IVInfo.WidestNativeType),
+ IsSigned(IVInfo.IsSigned),
+ IU(IUsers),
+ LI(LInfo),
+ L(LI->getLoopFor(OrigPhi->getParent())),
+ SE(SEv),
+ DeadInsts(DI),
+ WidePhi(0),
+ WideInc(0),
+ WideIncExpr(0) {
+ assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
+ }
+
+ bool CreateWideIV(SCEVExpander &Rewriter);
+
+protected:
+ const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse);
+
+ Instruction *CloneIVUser(Instruction *NarrowUse,
+ Instruction *NarrowDef,
+ Instruction *WideDef);
+
+ Instruction *WidenIVUse(Instruction *NarrowUse,
+ Instruction *NarrowDef,
+ Instruction *WideDef);
+};
+} // anonymous namespace
+
/// SimplifyIVUsers - Iteratively perform simplification on IVUsers within this
/// loop. IVUsers is treated as a worklist. Each successive simplification may
/// push more users which may themselves be candidates for simplification.
-void IndVarSimplify::SimplifyIVUsers() {
- for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) {
- Instruction *UseInst = I->getUser();
- Value *IVOperand = I->getOperandValToReplace();
+///
+void IndVarSimplify::SimplifyIVUsers(SCEVExpander &Rewriter) {
+ WideIVMap IVMap;
- if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
- EliminateIVComparison(ICmp, IVOperand);
- continue;
- }
+ // Each round of simplification involves a round of eliminating operations
+ // followed by a round of widening IVs. A single IVUsers worklist is used
+ // across all rounds. The inner loop advances the user. If widening exposes
+ // more uses, then another pass through the outer loop is triggered.
+ for (IVUsers::iterator I = IU->begin(), E = IU->end(); I != E;) {
+ for(; I != E; ++I) {
+ Instruction *UseInst = I->getUser();
+ Value *IVOperand = I->getOperandValToReplace();
- if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
- bool IsSigned = Rem->getOpcode() == Instruction::SRem;
- if (IsSigned || Rem->getOpcode() == Instruction::URem) {
- EliminateIVRemainder(Rem, IVOperand, IsSigned);
+ if (DisableIVRewrite) {
+ if (CastInst *Cast = dyn_cast<CastInst>(UseInst)) {
+ bool IsSigned = Cast->getOpcode() == Instruction::SExt;
+ if (IsSigned || Cast->getOpcode() == Instruction::ZExt) {
+ CollectExtend(Cast, I->getPhi(), IsSigned, IVMap, SE, TD);
+ continue;
+ }
+ }
+ }
+ if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
+ EliminateIVComparison(ICmp, IVOperand);
continue;
}
+ if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
+ bool IsSigned = Rem->getOpcode() == Instruction::SRem;
+ if (IsSigned || Rem->getOpcode() == Instruction::URem) {
+ EliminateIVRemainder(Rem, IVOperand, IsSigned, I->getPhi());
+ continue;
+ }
+ }
+ }
+ for (WideIVMap::const_iterator I = IVMap.begin(), E = IVMap.end();
+ I != E; ++I) {
+ WidenIV Widener(I->first, I->second, IU, LI, SE, DeadInsts);
+ if (Widener.CreateWideIV(Rewriter))
+ Changed = true;
}
}
}
+// GetWideRecurrence - Is this instruction potentially interesting from IVUsers'
+// perspective after widening it's type? In other words, can the extend be
+// safely hoisted out of the loop with SCEV reducing the value to a recurrence
+// on the same loop. If so, return the sign or zero extended
+// recurrence. Otherwise return NULL.
+const SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) {
+ if (!SE->isSCEVable(NarrowUse->getType()))
+ return 0;
+
+ const SCEV *NarrowExpr = SE->getSCEV(NarrowUse);
+ const SCEV *WideExpr = IsSigned ?
+ SE->getSignExtendExpr(NarrowExpr, WideType) :
+ SE->getZeroExtendExpr(NarrowExpr, WideType);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
+ if (!AddRec || AddRec->getLoop() != L)
+ return 0;
+
+ return AddRec;
+}
+
+/// CloneIVUser - Instantiate a wide operation to replace a narrow
+/// operation. This only needs to handle operations that can evaluation to
+/// SCEVAddRec. It can safely return 0 for any operation we decide not to clone.
+Instruction *WidenIV::CloneIVUser(Instruction *NarrowUse,
+ Instruction *NarrowDef,
+ Instruction *WideDef) {
+ unsigned Opcode = NarrowUse->getOpcode();
+ switch (Opcode) {
+ default:
+ return 0;
+ case Instruction::Add:
+ case Instruction::Mul:
+ case Instruction::UDiv:
+ case Instruction::Sub:
+ case Instruction::And:
+ case Instruction::Or:
+ case Instruction::Xor:
+ case Instruction::Shl:
+ case Instruction::LShr:
+ case Instruction::AShr:
+ DEBUG(dbgs() << "Cloning IVUser: " << *NarrowUse << "\n");
+
+ BinaryOperator *NarrowBO = cast<BinaryOperator>(NarrowUse);
+ BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(),
+ NarrowBO->getOperand(0),
+ NarrowBO->getOperand(1),
+ NarrowBO->getName());
+ IRBuilder<> Builder(NarrowUse);
+ Builder.Insert(WideBO);
+ if (NarrowBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap();
+ if (NarrowBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap();
+
+ for (unsigned i = 0; i < NarrowBO->getNumOperands(); ++i) {
+ Value *NarrowOper = NarrowBO->getOperand(i);
+ if (NarrowOper == NarrowDef) {
+ WideBO->setOperand(i, WideDef);
+ continue;
+ }
+ // We don't know anything about the other operand here so must insert a
+ // [sz]ext. It is probably loop invariant and will be folded or
+ // hoisted. If it actually comes from a widened IV, it should be removed
+ // during a future call to WidenIVUse.
+ IRBuilder<> Builder(NarrowUse);
+ Value *Extend = IsSigned ?
+ Builder.CreateSExt(NarrowOper, WideType) :
+ Builder.CreateZExt(NarrowOper, WideType);
+ WideBO->setOperand(i, Extend);
+ }
+ }
+ llvm_unreachable(0);
+}
+
+/// WidenIVUse - Determine whether an individual user of the narrow IV can be
+/// widened. If so, return the wide clone of the user.
+Instruction *WidenIV::WidenIVUse(Instruction *NarrowUse,
+ Instruction *NarrowDef,
+ Instruction *WideDef) {
+ // To be consistent with IVUsers, stop traversing the def-use chain at
+ // inner-loop phis or post-loop phis.
+ if (isa<PHINode>(NarrowUse) && LI->getLoopFor(NarrowUse->getParent()) != L)
+ return 0;
+
+ // Handle data flow merges and bizarre phi cycles.
+ if (!Processed.insert(NarrowUse))
+ return 0;
+
+ // Our raison d'etre! Eliminate sign and zero extension.
+ if (IsSigned ? isa<SExtInst>(NarrowUse) : isa<ZExtInst>(NarrowUse)) {
+ NarrowUse->replaceAllUsesWith(WideDef);
+ DeadInsts.push_back(NarrowUse);
+
+ // Now that the extend is gone, expose it's uses to IVUsers for potential
+ // further simplification within SimplifyIVUsers.
+ IU->AddUsersIfInteresting(WideDef, WidePhi);
+
+ // No further widening is needed. The deceased [sz]ext had done it for us.
+ return 0;
+ }
+ const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(NarrowUse);
+ if (!WideAddRec) {
+ // This user does not evaluate to a recurence after widening, so don't
+ // follow it. Instead insert a Trunc to kill off the original use,
+ // eventually isolating the original narrow IV so it can be removed.
+ IRBuilder<> Builder(NarrowUse);
+ Value *Trunc = Builder.CreateTrunc(WideDef, NarrowUse->getType());
+ NarrowUse->replaceUsesOfWith(NarrowDef, Trunc);
+ return 0;
+ }
+ Instruction *WideUse = 0;
+ if (WideAddRec == WideIncExpr) {
+ // Reuse the IV increment that SCEVExpander created.
+ WideUse = WideInc;
+ }
+ else {
+ WideUse = CloneIVUser(NarrowUse, NarrowDef, WideDef);
+ if (!WideUse)
+ return 0;
+ }
+ // GetWideRecurrence ensured that the narrow expression could be extended
+ // outside the loop without overflow. This suggests that the wide use
+ // evaluates to the same expression as the extended narrow use, but doesn't
+ // absolutely guarantee it. Hence the following failsafe check. In rare cases
+ // where it fails, we simple throw away the newly created wide use.
+ if (WideAddRec != SE->getSCEV(WideUse)) {
+ DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse
+ << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n");
+ DeadInsts.push_back(WideUse);
+ return 0;
+ }
+
+ // Returning WideUse pushes it on the worklist.
+ return WideUse;
+}
+
+/// CreateWideIV - Process a single induction variable. First use the
+/// SCEVExpander to create a wide induction variable that evaluates to the same
+/// recurrence as the original narrow IV. Then use a worklist to forward
+/// traverse the narrow IV's def-use chain. After WidenIVUse as processed all
+/// interesting IV users, the narrow IV will be isolated for removal by
+/// DeleteDeadPHIs.
+///
+/// It would be simpler to delete uses as they are processed, but we must avoid
+/// invalidating SCEV expressions.
+///
+bool WidenIV::CreateWideIV(SCEVExpander &Rewriter) {
+ // Is this phi an induction variable?
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
+ if (!AddRec)
+ return false;
+
+ // Widen the induction variable expression.
+ const SCEV *WideIVExpr = IsSigned ?
+ SE->getSignExtendExpr(AddRec, WideType) :
+ SE->getZeroExtendExpr(AddRec, WideType);
+
+ assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
+ "Expect the new IV expression to preserve its type");
+
+ // Can the IV be extended outside the loop without overflow?
+ AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
+ if (!AddRec || AddRec->getLoop() != L)
+ return false;
+
+ // An AddRec must have loop-invariant operands. Since this AddRec it
+ // materialized by a loop header phi, the expression cannot have any post-loop
+ // operands, so they must dominate the loop header.
+ assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
+ SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader())
+ && "Loop header phi recurrence inputs do not dominate the loop");
+
+ // The rewriter provides a value for the desired IV expression. This may
+ // either find an existing phi or materialize a new one. Either way, we
+ // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
+ // of the phi-SCC dominates the loop entry.
+ Instruction *InsertPt = L->getHeader()->begin();
+ WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));
+
+ // Remembering the WideIV increment generated by SCEVExpander allows
+ // WidenIVUse to reuse it when widening the narrow IV's increment. We don't
+ // employ a general reuse mechanism because the call above is the only call to
+ // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
+ assert(WidePhi->hasOneUse() && "New IV has multiple users");
+ WideInc = WidePhi->use_back();
+ WideIncExpr = SE->getSCEV(WideInc);
+
+ DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
+ ++NumWidened;
+
+ // Traverse the def-use chain using a worklist starting at the original IV.
+ assert(Processed.empty() && "expect initial state" );
+ SmallVector<std::pair<Instruction *, Instruction *>, 8> NarrowIVUsers;
+
+ NarrowIVUsers.push_back(std::make_pair(OrigPhi, WidePhi));
+ while (!NarrowIVUsers.empty()) {
+ Instruction *NarrowInst, *WideInst;
+ tie(NarrowInst, WideInst) = NarrowIVUsers.pop_back_val();
+
+ for (Value::use_iterator UI = NarrowInst->use_begin(),
+ UE = NarrowInst->use_end(); UI != UE; ++UI) {
+ Instruction *NarrowUse = cast<Instruction>(*UI);
+ Instruction *WideUse = WidenIVUse(NarrowUse, NarrowInst, WideInst);
+ if (WideUse)
+ NarrowIVUsers.push_back(std::make_pair(NarrowUse, WideUse));
+
+ if (NarrowInst->use_empty())
+ DeadInsts.push_back(NarrowInst);
+ }
+ }
+ return true;
+}
+
void IndVarSimplify::EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
unsigned IVOperIdx = 0;
ICmpInst::Predicate Pred = ICmp->getPredicate();
@@ -512,7 +840,8 @@
void IndVarSimplify::EliminateIVRemainder(BinaryOperator *Rem,
Value *IVOperand,
- bool IsSigned) {
+ bool IsSigned,
+ PHINode *IVPhi) {
// We're only interested in the case where we know something about
// the numerator.
if (IVOperand != Rem->getOperand(0))
@@ -556,7 +885,7 @@
// Inform IVUsers about the new users.
if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0)))
- IU->AddUsersIfInteresting(I);
+ IU->AddUsersIfInteresting(I, IVPhi);
DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
Changed = true;
@@ -595,11 +924,6 @@
if (DisableIVRewrite)
Rewriter.disableCanonicalMode();
- const Type *LargestType = 0;
- if (DisableIVRewrite) {
- LargestType = WidenIVs(L, Rewriter);
- }
-
// Check to see if this loop has a computable loop-invariant execution count.
// If so, this means that we can compute the final value of any expressions
// that are recurrent in the loop, and substitute the exit values from the
@@ -609,10 +933,12 @@
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
RewriteLoopExitValues(L, Rewriter);
- SimplifyIVUsers();
+ // Eliminate redundant IV users.
+ SimplifyIVUsers(Rewriter);
// Compute the type of the largest recurrence expression, and decide whether
// a canonical induction variable should be inserted.
+ const Type *LargestType = 0;
bool NeedCannIV = false;
bool ExpandBECount = canExpandBackedgeTakenCount(L, BackedgeTakenCount);
if (ExpandBECount) {
@@ -708,7 +1034,8 @@
// For completeness, inform IVUsers of the IV use in the newly-created
// loop exit test instruction.
if (NewICmp)
- IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
+ IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)),
+ IndVar);
// Clean up dead instructions.
Changed |= DeleteDeadPHIs(L->getHeader());
@@ -757,83 +1084,6 @@
return false;
}
-/// Widen the type of any induction variables that are sign/zero extended and
-/// remove the [sz]ext uses.
-///
-/// FIXME: This may currently create extra IVs which could increase regpressure
-/// (without LSR to cleanup).
-///
-/// FIXME: may factor this with RewriteIVExpressions once it stabilizes.
-const Type *IndVarSimplify::WidenIVs(Loop *L, SCEVExpander &Rewriter) {
- const Type *LargestType = 0;
- for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) {
- Instruction *ExtInst = UI->getUser();
- if (!isa<SExtInst>(ExtInst) && !isa<ZExtInst>(ExtInst))
- continue;
- const SCEV *AR = SE->getSCEV(ExtInst);
- // Only widen this IV is SCEV tells us it's safe.
- if (!isa<SCEVAddRecExpr>(AR) && !isa<SCEVAddExpr>(AR))
- continue;
-
- if (!L->contains(UI->getUser())) {
- const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop());
- if (SE->isLoopInvariant(ExitVal, L))
- AR = ExitVal;
- }
-
- // Only expand affine recurences.
- if (!isSafe(AR, L, SE))
- continue;
-
- const Type *Ty =
- SE->getEffectiveSCEVType(ExtInst->getType());
-
- // Only remove [sz]ext if the wide IV is still a native type.
- //
- // FIXME: We may be able to remove the copy of this logic in
- // IVUsers::AddUsersIfInteresting.
- uint64_t Width = SE->getTypeSizeInBits(Ty);
- if (Width > 64 || (TD && !TD->isLegalInteger(Width)))
- continue;
-
- // Now expand it into actual Instructions and patch it into place.
- //
- // FIXME: avoid creating a new IV.
- Value *NewVal = Rewriter.expandCodeFor(AR, Ty, ExtInst);
-
- DEBUG(dbgs() << "INDVARS: Widened IV '" << *AR << "' " << *ExtInst << '\n'
- << " into = " << *NewVal << "\n");
-
- if (!isValidRewrite(ExtInst, NewVal)) {
- DeadInsts.push_back(NewVal);
- continue;
- }
-
- ++NumWidened;
- Changed = true;
-
- if (!LargestType ||
- SE->getTypeSizeInBits(Ty) >
- SE->getTypeSizeInBits(LargestType))
- LargestType = Ty;
-
- SE->forgetValue(ExtInst);
-
- // Patch the new value into place.
- if (ExtInst->hasName())
- NewVal->takeName(ExtInst);
- ExtInst->replaceAllUsesWith(NewVal);
-
- // The old value may be dead now.
- DeadInsts.push_back(ExtInst);
-
- // UI is a linked list iterator, so AddUsersIfInteresting effectively pushes
- // nodes on the worklist.
- IU->AddUsersIfInteresting(ExtInst);
- }
- return LargestType;
-}
-
void IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) {
// Rewrite all induction variable expressions in terms of the canonical
// induction variable.
@@ -1216,5 +1466,5 @@
}
// Add a new IVUsers entry for the newly-created integer PHI.
- IU->AddUsersIfInteresting(NewPHI);
+ IU->AddUsersIfInteresting(NewPHI, NewPHI);
}