summaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolutionExpander.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/ScalarEvolutionExpander.cpp')
-rw-r--r--lib/Analysis/ScalarEvolutionExpander.cpp88
1 files changed, 48 insertions, 40 deletions
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 3ceda677ba61..8f89389c4b5d 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -589,6 +589,12 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
return expand(SE.getAddExpr(Ops));
}
+Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty,
+ Value *V) {
+ const SCEV *const Ops[1] = {Op};
+ return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
+}
+
/// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
/// SCEV expansion. If they are nested, this is the most nested. If they are
/// neighboring, pick the later.
@@ -1036,8 +1042,7 @@ Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
if (!isa<ConstantInt>(StepV))
GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
GEPPtrTy->getAddressSpace());
- const SCEV *const StepArray[1] = { SE.getSCEV(StepV) };
- IncV = expandAddToGEP(StepArray, StepArray+1, GEPPtrTy, IntTy, PN);
+ IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
if (IncV->getType() != PN->getType()) {
IncV = Builder.CreateBitCast(IncV, PN->getType());
rememberInstruction(IncV);
@@ -1051,7 +1056,7 @@ Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
return IncV;
}
-/// \brief Hoist the addrec instruction chain rooted in the loop phi above the
+/// Hoist the addrec instruction chain rooted in the loop phi above the
/// position. This routine assumes that this is possible (has been checked).
void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
Instruction *Pos, PHINode *LoopPhi) {
@@ -1067,7 +1072,7 @@ void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
} while (InstToHoist != LoopPhi);
}
-/// \brief Check whether we can cheaply express the requested SCEV in terms of
+/// Check whether we can cheaply express the requested SCEV in terms of
/// the available PHI SCEV by truncation and/or inversion of the step.
static bool canBeCheaplyTransformed(ScalarEvolution &SE,
const SCEVAddRecExpr *Phi,
@@ -1154,16 +1159,11 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
IVIncInsertLoop &&
SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
- for (auto &I : *L->getHeader()) {
- auto *PN = dyn_cast<PHINode>(&I);
- // Found first non-phi, the rest of instructions are also not Phis.
- if (!PN)
- break;
-
- if (!SE.isSCEVable(PN->getType()))
+ for (PHINode &PN : L->getHeader()->phis()) {
+ if (!SE.isSCEVable(PN.getType()))
continue;
- const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(PN));
+ const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
if (!PhiSCEV)
continue;
@@ -1174,17 +1174,20 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
if (!IsMatchingSCEV && !TryNonMatchingSCEV)
continue;
+ // TODO: this possibly can be reworked to avoid this cast at all.
Instruction *TempIncV =
- cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock));
+ dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
+ if (!TempIncV)
+ continue;
// Check whether we can reuse this PHI node.
if (LSRMode) {
- if (!isExpandedAddRecExprPHI(PN, TempIncV, L))
+ if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
continue;
if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
continue;
} else {
- if (!isNormalAddRecExprPHI(PN, TempIncV, L))
+ if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
continue;
}
@@ -1193,7 +1196,7 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
IncV = TempIncV;
TruncTy = nullptr;
InvertStep = false;
- AddRecPhiMatch = PN;
+ AddRecPhiMatch = &PN;
break;
}
@@ -1203,7 +1206,7 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
// Record the phi node. But don't stop we might find an exact match
// later.
- AddRecPhiMatch = PN;
+ AddRecPhiMatch = &PN;
IncV = TempIncV;
TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
}
@@ -1392,7 +1395,7 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
// IVUsers tries to prevent this case, so it is rare. However, it can
// happen when an IVUser outside the loop is not dominated by the latch
// block. Adjusting IVIncInsertPos before expansion begins cannot handle
- // all cases. Consider a phi outide whose operand is replaced during
+ // all cases. Consider a phi outside whose operand is replaced during
// expansion with the value of the postinc user. Without fundamentally
// changing the way postinc users are tracked, the only remedy is
// inserting an extra IV increment. StepV might fold into PostLoopOffset,
@@ -1412,7 +1415,7 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
}
// We have decided to reuse an induction variable of a dominating loop. Apply
- // truncation and/or invertion of the step.
+ // truncation and/or inversion of the step.
if (TruncTy) {
Type *ResTy = Result->getType();
// Normalize the result type.
@@ -1445,12 +1448,9 @@ Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
if (Result->getType()->isIntegerTy()) {
Value *Base = expandCodeFor(PostLoopOffset, ExpandTy);
- const SCEV *const OffsetArray[1] = {SE.getUnknown(Result)};
- Result = expandAddToGEP(OffsetArray, OffsetArray + 1, PTy, IntTy, Base);
+ Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
} else {
- const SCEV *const OffsetArray[1] = {PostLoopOffset};
- Result =
- expandAddToGEP(OffsetArray, OffsetArray + 1, PTy, IntTy, Result);
+ Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
}
} else {
Result = InsertNoopCastOfTo(Result, IntTy);
@@ -1502,9 +1502,9 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
// Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
// comments on expandAddToGEP for details.
const SCEV *Base = S->getStart();
- const SCEV *RestArray[1] = { Rest };
// Dig into the expression to find the pointer base for a GEP.
- ExposePointerBase(Base, RestArray[0], SE);
+ const SCEV *ExposedRest = Rest;
+ ExposePointerBase(Base, ExposedRest, SE);
// If we found a pointer, expand the AddRec with a GEP.
if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
// Make sure the Base isn't something exotic, such as a multiplied
@@ -1513,7 +1513,7 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
Value *StartV = expand(Base);
assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
- return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV);
+ return expandAddToGEP(ExposedRest, PTy, Ty, StartV);
}
}
@@ -1863,15 +1863,11 @@ SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
const TargetTransformInfo *TTI) {
// Find integer phis in order of increasing width.
SmallVector<PHINode*, 8> Phis;
- for (auto &I : *L->getHeader()) {
- if (auto *PN = dyn_cast<PHINode>(&I))
- Phis.push_back(PN);
- else
- break;
- }
+ for (PHINode &PN : L->getHeader()->phis())
+ Phis.push_back(&PN);
if (TTI)
- std::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
+ llvm::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
// Put pointers at the back and make sure pointer < pointer = false.
if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
@@ -2163,8 +2159,9 @@ Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
const SCEV *Step = AR->getStepRecurrence(SE);
const SCEV *Start = AR->getStart();
+ Type *ARTy = AR->getType();
unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
- unsigned DstBits = SE.getTypeSizeInBits(AR->getType());
+ unsigned DstBits = SE.getTypeSizeInBits(ARTy);
// The expression {Start,+,Step} has nusw/nssw if
// Step < 0, Start - |Step| * Backedge <= Start
@@ -2176,11 +2173,12 @@ Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
Value *TripCountVal = expandCodeFor(ExitCount, CountTy, Loc);
IntegerType *Ty =
- IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(AR->getType()));
+ IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
+ Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty;
Value *StepValue = expandCodeFor(Step, Ty, Loc);
Value *NegStepValue = expandCodeFor(SE.getNegativeSCEV(Step), Ty, Loc);
- Value *StartValue = expandCodeFor(Start, Ty, Loc);
+ Value *StartValue = expandCodeFor(Start, ARExpandTy, Loc);
ConstantInt *Zero =
ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits));
@@ -2203,8 +2201,18 @@ Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
// Compute:
// Start + |Step| * Backedge < Start
// Start - |Step| * Backedge > Start
- Value *Add = Builder.CreateAdd(StartValue, MulV);
- Value *Sub = Builder.CreateSub(StartValue, MulV);
+ Value *Add = nullptr, *Sub = nullptr;
+ if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) {
+ const SCEV *MulS = SE.getSCEV(MulV);
+ const SCEV *NegMulS = SE.getNegativeSCEV(MulS);
+ Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue),
+ ARPtrTy);
+ Sub = Builder.CreateBitCast(
+ expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy);
+ } else {
+ Add = Builder.CreateAdd(StartValue, MulV);
+ Sub = Builder.CreateSub(StartValue, MulV);
+ }
Value *EndCompareGT = Builder.CreateICmp(
Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
@@ -2218,7 +2226,7 @@ Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
// If the backedge taken count type is larger than the AR type,
// check that we don't drop any bits by truncating it. If we are
- // droping bits, then we have overflow (unless the step is zero).
+ // dropping bits, then we have overflow (unless the step is zero).
if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
auto *BackedgeCheck =
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-06 09:58:19 +0000