summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopRerollPass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/LoopRerollPass.cpp')
-rw-r--r--lib/Transforms/Scalar/LoopRerollPass.cpp407
1 files changed, 317 insertions, 90 deletions
diff --git a/lib/Transforms/Scalar/LoopRerollPass.cpp b/lib/Transforms/Scalar/LoopRerollPass.cpp
index 27c2d8824df06..d2f1b66076a6c 100644
--- a/lib/Transforms/Scalar/LoopRerollPass.cpp
+++ b/lib/Transforms/Scalar/LoopRerollPass.cpp
@@ -14,7 +14,7 @@
#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
@@ -128,9 +128,8 @@ NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400),
namespace {
enum IterationLimits {
- /// The maximum number of iterations that we'll try and reroll. This
- /// has to be less than 25 in order to fit into a SmallBitVector.
- IL_MaxRerollIterations = 16,
+ /// The maximum number of iterations that we'll try and reroll.
+ IL_MaxRerollIterations = 32,
/// The bitvector index used by loop induction variables and other
/// instructions that belong to all iterations.
IL_All,
@@ -147,13 +146,8 @@ namespace {
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<AAResultsWrapperPass>();
- AU.addRequired<LoopInfoWrapperPass>();
- AU.addPreserved<LoopInfoWrapperPass>();
- AU.addRequired<DominatorTreeWrapperPass>();
- AU.addPreserved<DominatorTreeWrapperPass>();
- AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
+ getLoopAnalysisUsage(AU);
}
protected:
@@ -169,6 +163,9 @@ namespace {
// Map between induction variable and its increment
DenseMap<Instruction *, int64_t> IVToIncMap;
+ // For loop with multiple induction variable, remember the one used only to
+ // control the loop.
+ Instruction *LoopControlIV;
// A chain of isomorphic instructions, identified by a single-use PHI
// representing a reduction. Only the last value may be used outside the
@@ -356,9 +353,11 @@ namespace {
ScalarEvolution *SE, AliasAnalysis *AA,
TargetLibraryInfo *TLI, DominatorTree *DT, LoopInfo *LI,
bool PreserveLCSSA,
- DenseMap<Instruction *, int64_t> &IncrMap)
+ DenseMap<Instruction *, int64_t> &IncrMap,
+ Instruction *LoopCtrlIV)
: Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), DT(DT), LI(LI),
- PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap) {}
+ PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap),
+ LoopControlIV(LoopCtrlIV) {}
/// Stage 1: Find all the DAG roots for the induction variable.
bool findRoots();
@@ -370,7 +369,7 @@ namespace {
void replace(const SCEV *IterCount);
protected:
- typedef MapVector<Instruction*, SmallBitVector> UsesTy;
+ typedef MapVector<Instruction*, BitVector> UsesTy;
bool findRootsRecursive(Instruction *IVU,
SmallInstructionSet SubsumedInsts);
@@ -396,6 +395,8 @@ namespace {
bool instrDependsOn(Instruction *I,
UsesTy::iterator Start,
UsesTy::iterator End);
+ void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount);
+ void updateNonLoopCtrlIncr();
LoopReroll *Parent;
@@ -426,8 +427,18 @@ namespace {
UsesTy Uses;
// Map between induction variable and its increment
DenseMap<Instruction *, int64_t> &IVToIncMap;
+ Instruction *LoopControlIV;
};
+ // Check if it is a compare-like instruction whose user is a branch
+ bool isCompareUsedByBranch(Instruction *I) {
+ auto *TI = I->getParent()->getTerminator();
+ if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
+ return false;
+ return I->hasOneUse() && TI->getOperand(0) == I;
+ };
+
+ bool isLoopControlIV(Loop *L, Instruction *IV);
void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
void collectPossibleReductions(Loop *L,
ReductionTracker &Reductions);
@@ -438,10 +449,7 @@ namespace {
char LoopReroll::ID = 0;
INITIALIZE_PASS_BEGIN(LoopReroll, "loop-reroll", "Reroll loops", false, false)
-INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(LoopReroll, "loop-reroll", "Reroll loops", false, false)
@@ -460,6 +468,110 @@ static bool hasUsesOutsideLoop(Instruction *I, Loop *L) {
return false;
}
+static const SCEVConstant *getIncrmentFactorSCEV(ScalarEvolution *SE,
+ const SCEV *SCEVExpr,
+ Instruction &IV) {
+ const SCEVMulExpr *MulSCEV = dyn_cast<SCEVMulExpr>(SCEVExpr);
+
+ // If StepRecurrence of a SCEVExpr is a constant (c1 * c2, c2 = sizeof(ptr)),
+ // Return c1.
+ if (!MulSCEV && IV.getType()->isPointerTy())
+ if (const SCEVConstant *IncSCEV = dyn_cast<SCEVConstant>(SCEVExpr)) {
+ const PointerType *PTy = cast<PointerType>(IV.getType());
+ Type *ElTy = PTy->getElementType();
+ const SCEV *SizeOfExpr =
+ SE->getSizeOfExpr(SE->getEffectiveSCEVType(IV.getType()), ElTy);
+ if (IncSCEV->getValue()->getValue().isNegative()) {
+ const SCEV *NewSCEV =
+ SE->getUDivExpr(SE->getNegativeSCEV(SCEVExpr), SizeOfExpr);
+ return dyn_cast<SCEVConstant>(SE->getNegativeSCEV(NewSCEV));
+ } else {
+ return dyn_cast<SCEVConstant>(SE->getUDivExpr(SCEVExpr, SizeOfExpr));
+ }
+ }
+
+ if (!MulSCEV)
+ return nullptr;
+
+ // If StepRecurrence of a SCEVExpr is a c * sizeof(x), where c is constant,
+ // Return c.
+ const SCEVConstant *CIncSCEV = nullptr;
+ for (const SCEV *Operand : MulSCEV->operands()) {
+ if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Operand)) {
+ CIncSCEV = Constant;
+ } else if (const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Operand)) {
+ Type *AllocTy;
+ if (!Unknown->isSizeOf(AllocTy))
+ break;
+ } else {
+ return nullptr;
+ }
+ }
+ return CIncSCEV;
+}
+
+// Check if an IV is only used to control the loop. There are two cases:
+// 1. It only has one use which is loop increment, and the increment is only
+// used by comparison and the PHI (could has sext with nsw in between), and the
+// comparison is only used by branch.
+// 2. It is used by loop increment and the comparison, the loop increment is
+// only used by the PHI, and the comparison is used only by the branch.
+bool LoopReroll::isLoopControlIV(Loop *L, Instruction *IV) {
+ unsigned IVUses = IV->getNumUses();
+ if (IVUses != 2 && IVUses != 1)
+ return false;
+
+ for (auto *User : IV->users()) {
+ int32_t IncOrCmpUses = User->getNumUses();
+ bool IsCompInst = isCompareUsedByBranch(cast<Instruction>(User));
+
+ // User can only have one or two uses.
+ if (IncOrCmpUses != 2 && IncOrCmpUses != 1)
+ return false;
+
+ // Case 1
+ if (IVUses == 1) {
+ // The only user must be the loop increment.
+ // The loop increment must have two uses.
+ if (IsCompInst || IncOrCmpUses != 2)
+ return false;
+ }
+
+ // Case 2
+ if (IVUses == 2 && IncOrCmpUses != 1)
+ return false;
+
+ // The users of the IV must be a binary operation or a comparison
+ if (auto *BO = dyn_cast<BinaryOperator>(User)) {
+ if (BO->getOpcode() == Instruction::Add) {
+ // Loop Increment
+ // User of Loop Increment should be either PHI or CMP
+ for (auto *UU : User->users()) {
+ if (PHINode *PN = dyn_cast<PHINode>(UU)) {
+ if (PN != IV)
+ return false;
+ }
+ // Must be a CMP or an ext (of a value with nsw) then CMP
+ else {
+ Instruction *UUser = dyn_cast<Instruction>(UU);
+ // Skip SExt if we are extending an nsw value
+ // TODO: Allow ZExt too
+ if (BO->hasNoSignedWrap() && UUser && UUser->getNumUses() == 1 &&
+ isa<SExtInst>(UUser))
+ UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
+ if (!isCompareUsedByBranch(UUser))
+ return false;
+ }
+ }
+ } else
+ return false;
+ // Compare : can only have one use, and must be branch
+ } else if (!IsCompInst)
+ return false;
+ }
+ return true;
+}
+
// Collect the list of loop induction variables with respect to which it might
// be possible to reroll the loop.
void LoopReroll::collectPossibleIVs(Loop *L,
@@ -469,7 +581,7 @@ void LoopReroll::collectPossibleIVs(Loop *L,
IE = Header->getFirstInsertionPt(); I != IE; ++I) {
if (!isa<PHINode>(I))
continue;
- if (!I->getType()->isIntegerTy())
+ if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())
continue;
if (const SCEVAddRecExpr *PHISCEV =
@@ -478,15 +590,27 @@ void LoopReroll::collectPossibleIVs(Loop *L,
continue;
if (!PHISCEV->isAffine())
continue;
- if (const SCEVConstant *IncSCEV =
- dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE))) {
- const APInt &AInt = IncSCEV->getAPInt().abs();
+ const SCEVConstant *IncSCEV = nullptr;
+ if (I->getType()->isPointerTy())
+ IncSCEV =
+ getIncrmentFactorSCEV(SE, PHISCEV->getStepRecurrence(*SE), *I);
+ else
+ IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
+ if (IncSCEV) {
+ const APInt &AInt = IncSCEV->getValue()->getValue().abs();
if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
continue;
IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
<< "\n");
- PossibleIVs.push_back(&*I);
+
+ if (isLoopControlIV(L, &*I)) {
+ assert(!LoopControlIV && "Found two loop control only IV");
+ LoopControlIV = &(*I);
+ DEBUG(dbgs() << "LRR: Possible loop control only IV: " << *I << " = "
+ << *PHISCEV << "\n");
+ } else
+ PossibleIVs.push_back(&*I);
}
}
}
@@ -611,9 +735,8 @@ void LoopReroll::DAGRootTracker::collectInLoopUserSet(
const SmallInstructionSet &Exclude,
const SmallInstructionSet &Final,
DenseSet<Instruction *> &Users) {
- for (SmallInstructionVector::const_iterator I = Roots.begin(),
- IE = Roots.end(); I != IE; ++I)
- collectInLoopUserSet(*I, Exclude, Final, Users);
+ for (Instruction *Root : Roots)
+ collectInLoopUserSet(Root, Exclude, Final, Users);
}
static bool isSimpleLoadStore(Instruction *I) {
@@ -651,10 +774,12 @@ static bool isSimpleArithmeticOp(User *IVU) {
static bool isLoopIncrement(User *U, Instruction *IV) {
BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
- if (!BO || BO->getOpcode() != Instruction::Add)
+
+ if ((BO && BO->getOpcode() != Instruction::Add) ||
+ (!BO && !isa<GetElementPtrInst>(U)))
return false;
- for (auto *UU : BO->users()) {
+ for (auto *UU : U->users()) {
PHINode *PN = dyn_cast<PHINode>(UU);
if (PN && PN == IV)
return true;
@@ -1031,6 +1156,33 @@ bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
Uses[I].set(IL_All);
}
+ // Make sure we mark loop-control-only PHIs as used in all iterations. See
+ // comment above LoopReroll::isLoopControlIV for more information.
+ BasicBlock *Header = L->getHeader();
+ if (LoopControlIV && LoopControlIV != IV) {
+ for (auto *U : LoopControlIV->users()) {
+ Instruction *IVUser = dyn_cast<Instruction>(U);
+ // IVUser could be loop increment or compare
+ Uses[IVUser].set(IL_All);
+ for (auto *UU : IVUser->users()) {
+ Instruction *UUser = dyn_cast<Instruction>(UU);
+ // UUser could be compare, PHI or branch
+ Uses[UUser].set(IL_All);
+ // Skip SExt
+ if (isa<SExtInst>(UUser)) {
+ UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
+ Uses[UUser].set(IL_All);
+ }
+ // Is UUser a compare instruction?
+ if (UU->hasOneUse()) {
+ Instruction *BI = dyn_cast<BranchInst>(*UUser->user_begin());
+ if (BI == cast<BranchInst>(Header->getTerminator()))
+ Uses[BI].set(IL_All);
+ }
+ }
+ }
+ }
+
// Make sure all instructions in the loop are in one and only one
// set.
for (auto &KV : Uses) {
@@ -1272,61 +1424,136 @@ void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) {
++J;
}
- bool Negative = IVToIncMap[IV] < 0;
- const DataLayout &DL = Header->getModule()->getDataLayout();
- // We need to create a new induction variable for each different BaseInst.
- for (auto &DRS : RootSets) {
- // Insert the new induction variable.
- const SCEVAddRecExpr *RealIVSCEV =
- cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
- const SCEV *Start = RealIVSCEV->getStart();
- const SCEVAddRecExpr *H = cast<SCEVAddRecExpr>(SE->getAddRecExpr(
- Start, SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1), L,
- SCEV::FlagAnyWrap));
- { // Limit the lifetime of SCEVExpander.
- SCEVExpander Expander(*SE, DL, "reroll");
- Value *NewIV = Expander.expandCodeFor(H, IV->getType(), &Header->front());
-
- for (auto &KV : Uses) {
- if (KV.second.find_first() == 0)
- KV.first->replaceUsesOfWith(DRS.BaseInst, NewIV);
- }
+ bool HasTwoIVs = LoopControlIV && LoopControlIV != IV;
+
+ if (HasTwoIVs) {
+ updateNonLoopCtrlIncr();
+ replaceIV(LoopControlIV, LoopControlIV, IterCount);
+ } else
+ // We need to create a new induction variable for each different BaseInst.
+ for (auto &DRS : RootSets)
+ // Insert the new induction variable.
+ replaceIV(DRS.BaseInst, IV, IterCount);
- if (BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator())) {
- // FIXME: Why do we need this check?
- if (Uses[BI].find_first() == IL_All) {
- const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
+ SimplifyInstructionsInBlock(Header, TLI);
+ DeleteDeadPHIs(Header, TLI);
+}
- // Iteration count SCEV minus 1
- const SCEV *ICMinus1SCEV = SE->getMinusSCEV(
- ICSCEV, SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1));
+// For non-loop-control IVs, we only need to update the last increment
+// with right amount, then we are done.
+void LoopReroll::DAGRootTracker::updateNonLoopCtrlIncr() {
+ const SCEV *NewInc = nullptr;
+ for (auto *LoopInc : LoopIncs) {
+ GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LoopInc);
+ const SCEVConstant *COp = nullptr;
+ if (GEP && LoopInc->getOperand(0)->getType()->isPointerTy()) {
+ COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(1)));
+ } else {
+ COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(0)));
+ if (!COp)
+ COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(1)));
+ }
- Value *ICMinus1; // Iteration count minus 1
- if (isa<SCEVConstant>(ICMinus1SCEV)) {
- ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), BI);
- } else {
- BasicBlock *Preheader = L->getLoopPreheader();
- if (!Preheader)
- Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
+ assert(COp && "Didn't find constant operand of LoopInc!\n");
- ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(),
- Preheader->getTerminator());
- }
+ const APInt &AInt = COp->getValue()->getValue();
+ const SCEV *ScaleSCEV = SE->getConstant(COp->getType(), Scale);
+ if (AInt.isNegative()) {
+ NewInc = SE->getNegativeSCEV(COp);
+ NewInc = SE->getUDivExpr(NewInc, ScaleSCEV);
+ NewInc = SE->getNegativeSCEV(NewInc);
+ } else
+ NewInc = SE->getUDivExpr(COp, ScaleSCEV);
+
+ LoopInc->setOperand(1, dyn_cast<SCEVConstant>(NewInc)->getValue());
+ }
+}
- Value *Cond =
- new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinus1, "exitcond");
- BI->setCondition(Cond);
+void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst,
+ Instruction *InstIV,
+ const SCEV *IterCount) {
+ BasicBlock *Header = L->getHeader();
+ int64_t Inc = IVToIncMap[InstIV];
+ bool NeedNewIV = InstIV == LoopControlIV;
+ bool Negative = !NeedNewIV && Inc < 0;
+
+ const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Inst));
+ const SCEV *Start = RealIVSCEV->getStart();
+
+ if (NeedNewIV)
+ Start = SE->getConstant(Start->getType(), 0);
+
+ const SCEV *SizeOfExpr = nullptr;
+ const SCEV *IncrExpr =
+ SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1);
+ if (auto *PTy = dyn_cast<PointerType>(Inst->getType())) {
+ Type *ElTy = PTy->getElementType();
+ SizeOfExpr =
+ SE->getSizeOfExpr(SE->getEffectiveSCEVType(Inst->getType()), ElTy);
+ IncrExpr = SE->getMulExpr(IncrExpr, SizeOfExpr);
+ }
+ const SCEV *NewIVSCEV =
+ SE->getAddRecExpr(Start, IncrExpr, L, SCEV::FlagAnyWrap);
+
+ { // Limit the lifetime of SCEVExpander.
+ const DataLayout &DL = Header->getModule()->getDataLayout();
+ SCEVExpander Expander(*SE, DL, "reroll");
+ Value *NewIV =
+ Expander.expandCodeFor(NewIVSCEV, InstIV->getType(), &Header->front());
+
+ for (auto &KV : Uses)
+ if (KV.second.find_first() == 0)
+ KV.first->replaceUsesOfWith(Inst, NewIV);
+
+ if (BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator())) {
+ // FIXME: Why do we need this check?
+ if (Uses[BI].find_first() == IL_All) {
+ const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
+
+ if (NeedNewIV)
+ ICSCEV = SE->getMulExpr(IterCount,
+ SE->getConstant(IterCount->getType(), Scale));
+
+ // Iteration count SCEV minus or plus 1
+ const SCEV *MinusPlus1SCEV =
+ SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1);
+ if (Inst->getType()->isPointerTy()) {
+ assert(SizeOfExpr && "SizeOfExpr is not initialized");
+ MinusPlus1SCEV = SE->getMulExpr(MinusPlus1SCEV, SizeOfExpr);
+ }
- if (BI->getSuccessor(1) != Header)
- BI->swapSuccessors();
+ const SCEV *ICMinusPlus1SCEV = SE->getMinusSCEV(ICSCEV, MinusPlus1SCEV);
+ // Iteration count minus 1
+ Instruction *InsertPtr = nullptr;
+ if (isa<SCEVConstant>(ICMinusPlus1SCEV)) {
+ InsertPtr = BI;
+ } else {
+ BasicBlock *Preheader = L->getLoopPreheader();
+ if (!Preheader)
+ Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
+ InsertPtr = Preheader->getTerminator();
}
+
+ if (!isa<PointerType>(NewIV->getType()) && NeedNewIV &&
+ (SE->getTypeSizeInBits(NewIV->getType()) <
+ SE->getTypeSizeInBits(ICMinusPlus1SCEV->getType()))) {
+ IRBuilder<> Builder(BI);
+ Builder.SetCurrentDebugLocation(BI->getDebugLoc());
+ NewIV = Builder.CreateSExt(NewIV, ICMinusPlus1SCEV->getType());
+ }
+ Value *ICMinusPlus1 = Expander.expandCodeFor(
+ ICMinusPlus1SCEV, NewIV->getType(), InsertPtr);
+
+ Value *Cond =
+ new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinusPlus1, "exitcond");
+ BI->setCondition(Cond);
+
+ if (BI->getSuccessor(1) != Header)
+ BI->swapSuccessors();
}
}
}
-
- SimplifyInstructionsInBlock(Header, TLI);
- DeleteDeadPHIs(Header, TLI);
}
// Validate the selected reductions. All iterations must have an isomorphic
@@ -1334,9 +1561,7 @@ void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) {
// entries must appear in order.
bool LoopReroll::ReductionTracker::validateSelected() {
// For a non-associative reduction, the chain entries must appear in order.
- for (DenseSet<int>::iterator RI = Reds.begin(), RIE = Reds.end();
- RI != RIE; ++RI) {
- int i = *RI;
+ for (int i : Reds) {
int PrevIter = 0, BaseCount = 0, Count = 0;
for (Instruction *J : PossibleReds[i]) {
// Note that all instructions in the chain must have been found because
@@ -1380,9 +1605,7 @@ bool LoopReroll::ReductionTracker::validateSelected() {
void LoopReroll::ReductionTracker::replaceSelected() {
// Fixup reductions to refer to the last instruction associated with the
// first iteration (not the last).
- for (DenseSet<int>::iterator RI = Reds.begin(), RIE = Reds.end();
- RI != RIE; ++RI) {
- int i = *RI;
+ for (int i : Reds) {
int j = 0;
for (int e = PossibleReds[i].size(); j != e; ++j)
if (PossibleRedIter[PossibleReds[i][j]] != 0) {
@@ -1396,9 +1619,8 @@ void LoopReroll::ReductionTracker::replaceSelected() {
Users.push_back(cast<Instruction>(U));
}
- for (SmallInstructionVector::iterator J = Users.begin(),
- JE = Users.end(); J != JE; ++J)
- (*J)->replaceUsesOfWith(PossibleReds[i].getReducedValue(),
+ for (Instruction *User : Users)
+ User->replaceUsesOfWith(PossibleReds[i].getReducedValue(),
PossibleReds[i][j]);
}
}
@@ -1450,7 +1672,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
const SCEV *IterCount,
ReductionTracker &Reductions) {
DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
- IVToIncMap);
+ IVToIncMap, LoopControlIV);
if (!DAGRoots.findRoots())
return false;
@@ -1472,7 +1694,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
}
bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
- if (skipOptnoneFunction(L))
+ if (skipLoop(L))
return false;
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
@@ -1487,41 +1709,46 @@ bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
"] Loop %" << Header->getName() << " (" <<
L->getNumBlocks() << " block(s))\n");
- bool Changed = false;
-
// For now, we'll handle only single BB loops.
if (L->getNumBlocks() > 1)
- return Changed;
+ return false;
if (!SE->hasLoopInvariantBackedgeTakenCount(L))
- return Changed;
+ return false;
const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
const SCEV *IterCount = SE->getAddExpr(LIBETC, SE->getOne(LIBETC->getType()));
+ DEBUG(dbgs() << "\n Before Reroll:\n" << *(L->getHeader()) << "\n");
DEBUG(dbgs() << "LRR: iteration count = " << *IterCount << "\n");
// First, we need to find the induction variable with respect to which we can
// reroll (there may be several possible options).
SmallInstructionVector PossibleIVs;
IVToIncMap.clear();
+ LoopControlIV = nullptr;
collectPossibleIVs(L, PossibleIVs);
if (PossibleIVs.empty()) {
DEBUG(dbgs() << "LRR: No possible IVs found\n");
- return Changed;
+ return false;
}
ReductionTracker Reductions;
collectPossibleReductions(L, Reductions);
+ bool Changed = false;
// For each possible IV, collect the associated possible set of 'root' nodes
// (i+1, i+2, etc.).
- for (SmallInstructionVector::iterator I = PossibleIVs.begin(),
- IE = PossibleIVs.end(); I != IE; ++I)
- if (reroll(*I, L, Header, IterCount, Reductions)) {
+ for (Instruction *PossibleIV : PossibleIVs)
+ if (reroll(PossibleIV, L, Header, IterCount, Reductions)) {
Changed = true;
break;
}
+ DEBUG(dbgs() << "\n After Reroll:\n" << *(L->getHeader()) << "\n");
+
+ // Trip count of L has changed so SE must be re-evaluated.
+ if (Changed)
+ SE->forgetLoop(L);
return Changed;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-16 05:55:22 +0000