summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms')
-rw-r--r--llvm/lib/Transforms/Scalar/LoopRerollPass.cpp173
1 files changed, 50 insertions, 123 deletions
diff --git a/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp b/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp
index 014bc43363f..27c2d8824df 100644
--- a/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp
@@ -396,7 +396,6 @@ namespace {
bool instrDependsOn(Instruction *I,
UsesTy::iterator Start,
UsesTy::iterator End);
- void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount);
LoopReroll *Parent;
@@ -461,48 +460,6 @@ 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;
-}
-
// Collect the list of loop induction variables with respect to which it might
// be possible to reroll the loop.
void LoopReroll::collectPossibleIVs(Loop *L,
@@ -512,7 +469,7 @@ void LoopReroll::collectPossibleIVs(Loop *L,
IE = Header->getFirstInsertionPt(); I != IE; ++I) {
if (!isa<PHINode>(I))
continue;
- if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())
+ if (!I->getType()->isIntegerTy())
continue;
if (const SCEVAddRecExpr *PHISCEV =
@@ -521,14 +478,9 @@ void LoopReroll::collectPossibleIVs(Loop *L,
continue;
if (!PHISCEV->isAffine())
continue;
- 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 (const SCEVConstant *IncSCEV =
+ dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE))) {
+ const APInt &AInt = IncSCEV->getAPInt().abs();
if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
continue;
IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
@@ -699,12 +651,10 @@ static bool isSimpleArithmeticOp(User *IVU) {
static bool isLoopIncrement(User *U, Instruction *IV) {
BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
-
- if ((BO && BO->getOpcode() != Instruction::Add) ||
- (!BO && !isa<GetElementPtrInst>(U)))
+ if (!BO || BO->getOpcode() != Instruction::Add)
return false;
- for (auto *UU : U->users()) {
+ for (auto *UU : BO->users()) {
PHINode *PN = dyn_cast<PHINode>(UU);
if (PN && PN == IV)
return true;
@@ -1322,84 +1272,61 @@ 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)
+ for (auto &DRS : RootSets) {
// Insert the new induction variable.
- replaceIV(DRS.BaseInst, IV, IterCount);
+ 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);
+ }
- SimplifyInstructionsInBlock(Header, TLI);
- DeleteDeadPHIs(Header, TLI);
-}
+ 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);
-void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst,
- Instruction *InstIV,
- const SCEV *IterCount) {
- BasicBlock *Header = L->getHeader();
- int64_t Inc = IVToIncMap[InstIV];
- bool Negative = Inc < 0;
-
- const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Inst));
- const SCEV *Start = RealIVSCEV->getStart();
-
- 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);
-
- // 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);
- }
+ // Iteration count SCEV minus 1
+ const SCEV *ICMinus1SCEV = SE->getMinusSCEV(
+ ICSCEV, SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1));
- const SCEV *ICMinusPlus1SCEV = SE->getMinusSCEV(ICSCEV, MinusPlus1SCEV);
- // Iteration count minus 1
- Value *ICMinusPlus1 = nullptr;
- if (isa<SCEVConstant>(ICMinusPlus1SCEV)) {
- ICMinusPlus1 =
- Expander.expandCodeFor(ICMinusPlus1SCEV, NewIV->getType(), BI);
- } else {
- BasicBlock *Preheader = L->getLoopPreheader();
- if (!Preheader)
- Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
- ICMinusPlus1 = Expander.expandCodeFor(
- ICMinusPlus1SCEV, NewIV->getType(), Preheader->getTerminator());
- }
+ 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);
- Value *Cond =
- new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinusPlus1, "exitcond");
- BI->setCondition(Cond);
+ ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(),
+ Preheader->getTerminator());
+ }
+
+ Value *Cond =
+ new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinus1, "exitcond");
+ BI->setCondition(Cond);
- if (BI->getSuccessor(1) != Header)
- BI->swapSuccessors();
+ if (BI->getSuccessor(1) != Header)
+ BI->swapSuccessors();
+ }
}
}
}
+
+ SimplifyInstructionsInBlock(Header, TLI);
+ DeleteDeadPHIs(Header, TLI);
}
// Validate the selected reductions. All iterations must have an isomorphic
OpenPOWER on IntegriCloud