30 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
31 #define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X)
33 #define SCEV_DEBUG_WITH_TYPE(TYPE, X)
40 cl::desc(
"When performing SCEV expansion only if it is cheap to do, this "
41 "controls the budget that is considered cheap (default = 4)"));
43 using namespace PatternMatch;
66 if (U->getType() != Ty)
68 CastInst *CI = dyn_cast<CastInst>(U);
74 if (
IP->getParent() == CI->
getParent() && &*BIP != CI &&
83 SCEVInsertPointGuard Guard(
Builder,
this);
92 SE.DT.dominates(cast<Instruction>(
Ret), &*BIP));
101 if (
auto *II = dyn_cast<InvokeInst>(
I))
102 IP = II->getNormalDest()->begin();
104 while (isa<PHINode>(
IP))
107 if (isa<FuncletPadInst>(
IP) || isa<LandingPadInst>(
IP)) {
109 }
else if (isa<CatchSwitchInst>(
IP)) {
112 assert(!
IP->isEHPad() &&
"unexpected eh pad!");
118 while (isInsertedInstruction(&*
IP) && &*
IP != MustDominate)
125 SCEVExpander::GetOptimalInsertionPointForCastOf(
Value *V)
const {
128 if (
Argument *A = dyn_cast<Argument>(V)) {
130 while ((isa<BitCastInst>(
IP) &&
131 isa<Argument>(cast<BitCastInst>(
IP)->getOperand(0)) &&
132 cast<BitCastInst>(
IP)->getOperand(0) != A) ||
133 isa<DbgInfoIntrinsic>(
IP))
140 return findInsertPointAfter(
I, &*
Builder.GetInsertPoint());
144 assert(isa<Constant>(V) &&
145 "Expected the cast argument to be a global/constant");
146 return Builder.GetInsertBlock()
149 .getFirstInsertionPt();
157 assert((
Op == Instruction::BitCast ||
158 Op == Instruction::PtrToInt ||
159 Op == Instruction::IntToPtr) &&
160 "InsertNoopCastOfTo cannot perform non-noop casts!");
161 assert(SE.getTypeSizeInBits(V->
getType()) == SE.getTypeSizeInBits(Ty) &&
162 "InsertNoopCastOfTo cannot change sizes!");
169 if (
Op == Instruction::IntToPtr) {
170 auto *PtrTy = cast<PointerType>(Ty);
171 if (
DL.isNonIntegralPointerType(PtrTy)) {
172 auto *Int8PtrTy =
Builder.getInt8PtrTy(PtrTy->getAddressSpace());
174 "alloc size of i8 must by 1 byte for the GEP to be correct");
181 if (
Op == Instruction::BitCast) {
184 if (
CastInst *CI = dyn_cast<CastInst>(V)) {
190 if ((
Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) &&
191 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->
getType())) {
192 if (
CastInst *CI = dyn_cast<CastInst>(V))
193 if ((CI->
getOpcode() == Instruction::PtrToInt ||
194 CI->
getOpcode() == Instruction::IntToPtr) &&
195 SE.getTypeSizeInBits(CI->
getType()) ==
199 if ((
CE->getOpcode() == Instruction::PtrToInt ||
200 CE->getOpcode() == Instruction::IntToPtr) &&
201 SE.getTypeSizeInBits(
CE->getType()) ==
202 SE.getTypeSizeInBits(
CE->getOperand(0)->getType()))
203 return CE->getOperand(0);
211 return ReuseOrCreateCast(V, Ty,
Op, GetOptimalInsertionPointForCastOf(V));
226 unsigned ScanLimit = 6;
230 if (
IP != BlockBegin) {
232 for (; ScanLimit; --
IP, --ScanLimit) {
235 if (isa<DbgInfoIntrinsic>(
IP))
238 auto canGenerateIncompatiblePoison = [&Flags](
Instruction *
I) {
240 if (isa<OverflowingBinaryOperator>(
I)) {
248 if (isa<PossiblyExactOperator>(
I) &&
I->isExact())
252 if (
IP->getOpcode() == (unsigned)Opcode &&
IP->getOperand(0) ==
LHS &&
253 IP->getOperand(1) ==
RHS && !canGenerateIncompatiblePoison(&*
IP))
255 if (
IP == BlockBegin)
break;
261 SCEVInsertPointGuard Guard(
Builder,
this);
265 while (
const Loop *L = SE.LI.getLoopFor(
Builder.GetInsertBlock())) {
266 if (!L->isLoopInvariant(
LHS) || !L->isLoopInvariant(
RHS))
break;
267 BasicBlock *Preheader = L->getLoopPreheader();
268 if (!Preheader)
break;
331 if (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(
M->getOperand(0)))
332 if (!
C->getAPInt().srem(
FC->getAPInt())) {
334 NewMulOps[0] = SE.
getConstant(
C->getAPInt().sdiv(
FC->getAPInt()));
342 const SCEV *Step = A->getStepRecurrence(SE);
348 const SCEV *Start = A->getStart();
366 unsigned NumAddRecs = 0;
367 for (
unsigned i = Ops.size();
i > 0 && isa<SCEVAddRecExpr>(Ops[
i-1]); --
i)
373 const SCEV *Sum = NoAddRecs.empty() ?
379 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
380 Ops.
append(Add->op_begin(), Add->op_end());
384 Ops.
append(AddRecs.begin(), AddRecs.end());
397 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
399 const SCEV *Start = A->getStart();
400 if (Start->isZero())
break;
403 A->getStepRecurrence(SE),
406 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
408 Ops.
append(Add->op_begin(), Add->op_end());
409 e += Add->getNumOperands();
414 if (!AddRecs.empty()) {
416 Ops.
append(AddRecs.begin(), AddRecs.end());
449 Value *SCEVExpander::expandAddToGEP(
const SCEV *
const *op_begin,
450 const SCEV *
const *op_end,
456 bool AnyNonZeroIndices =
false;
462 Type *IntIdxTy =
DL.getIndexType(PTy);
477 const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy);
480 for (
const SCEV *
Op : Ops) {
481 const SCEV *Remainder = SE.getConstant(Ty, 0);
484 ScaledOps.push_back(
Op);
486 NewOps.push_back(Remainder);
487 AnyNonZeroIndices =
true;
491 NewOps.push_back(
Op);
495 if (!ScaledOps.empty()) {
509 : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty,
false);
510 GepIndices.push_back(
Scaled);
513 while (
StructType *STy = dyn_cast<StructType>(ElTy)) {
514 bool FoundFieldNo =
false;
516 if (STy->getNumElements() == 0)
break;
522 if (SE.getTypeSizeInBits(
C->getType()) <= 64) {
524 uint64_t FullOffset =
C->getValue()->getZExtValue();
527 GepIndices.push_back(
529 ElTy = STy->getTypeAtIndex(ElIdx);
532 AnyNonZeroIndices =
true;
540 ElTy = STy->getTypeAtIndex(0u);
541 GepIndices.push_back(
546 if (
ArrayType *ATy = dyn_cast<ArrayType>(ElTy))
547 ElTy = ATy->getElementType();
560 if (!AnyNonZeroIndices) {
563 V = InsertNoopCastOfTo(V,
566 assert(!isa<Instruction>(V) ||
567 SE.DT.dominates(cast<Instruction>(V), &*
Builder.GetInsertPoint()));
570 Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty,
false);
573 if (
Constant *CLHS = dyn_cast<Constant>(V))
574 if (
Constant *CRHS = dyn_cast<Constant>(Idx))
579 unsigned ScanLimit = 6;
583 if (
IP != BlockBegin) {
585 for (; ScanLimit; --
IP, --ScanLimit) {
588 if (isa<DbgInfoIntrinsic>(
IP))
590 if (
IP->getOpcode() == Instruction::GetElementPtr &&
591 IP->getOperand(0) == V &&
IP->getOperand(1) == Idx &&
592 cast<GEPOperator>(&*
IP)->getSourceElementType() ==
595 if (
IP == BlockBegin)
break;
600 SCEVInsertPointGuard Guard(
Builder,
this);
603 while (
const Loop *L = SE.LI.getLoopFor(
Builder.GetInsertBlock())) {
604 if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx))
break;
605 BasicBlock *Preheader = L->getLoopPreheader();
606 if (!Preheader)
break;
617 SCEVInsertPointGuard Guard(
Builder,
this);
620 while (
const Loop *L = SE.LI.getLoopFor(
Builder.GetInsertBlock())) {
621 if (!L->isLoopInvariant(V))
break;
623 bool AnyIndexNotLoopInvariant =
any_of(
624 GepIndices, [L](
Value *
Op) {
return !L->isLoopInvariant(
Op); });
626 if (AnyIndexNotLoopInvariant)
629 BasicBlock *Preheader = L->getLoopPreheader();
630 if (!Preheader)
break;
641 Casted = InsertNoopCastOfTo(Casted, PTy);
643 Casted, GepIndices,
"scevgep");
644 Ops.push_back(SE.getUnknown(
GEP));
647 return expand(SE.getAddExpr(Ops));
652 const SCEV *
const Ops[1] = {
Op};
653 return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
663 if (A->contains(
B))
return B;
664 if (
B->contains(A))
return A;
665 if (DT.
dominates(A->getHeader(),
B->getHeader()))
return B;
666 if (DT.
dominates(
B->getHeader(), A->getHeader()))
return A;
672 const Loop *SCEVExpander::getRelevantLoop(
const SCEV *
S) {
674 auto Pair = RelevantLoops.insert(std::make_pair(
S,
nullptr));
676 return Pair.first->second;
678 if (isa<SCEVConstant>(
S))
682 if (
const Instruction *
I = dyn_cast<Instruction>(U->getValue()))
683 return Pair.first->second = SE.LI.getLoopFor(
I->getParent());
688 const Loop *L =
nullptr;
691 for (
const SCEV *
Op :
N->operands())
693 return RelevantLoops[
N] = L;
696 const Loop *
Result = getRelevantLoop(
C->getOperand());
697 return RelevantLoops[
C] =
Result;
701 getRelevantLoop(
D->getLHS()), getRelevantLoop(
D->getRHS()), SE.DT);
702 return RelevantLoops[
D] =
Result;
715 bool operator()(std::pair<const Loop *, const SCEV *>
LHS,
716 std::pair<const Loop *, const SCEV *>
RHS)
const {
723 if (
LHS.first !=
RHS.first)
729 if (
LHS.second->isNonConstantNegative()) {
730 if (!
RHS.second->isNonConstantNegative())
732 }
else if (
RHS.second->isNonConstantNegative())
743 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
751 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(
Op),
Op));
759 Value *Sum =
nullptr;
760 for (
auto I = OpsAndLoops.begin(),
E = OpsAndLoops.end();
I !=
E;) {
761 const Loop *CurLoop =
I->first;
770 assert(!
Op->getType()->isPointerTy() &&
"Only first op can be pointer");
775 for (;
I !=
E &&
I->first == CurLoop; ++
I) {
778 const SCEV *
X =
I->second;
780 if (!isa<Instruction>(U->getValue()))
781 X = SE.getSCEV(U->getValue());
784 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
785 }
else if (
Op->isNonConstantNegative()) {
787 Value *
W = expandCodeForImpl(SE.getNegativeSCEV(
Op), Ty,
false);
788 Sum = InsertNoopCastOfTo(Sum, Ty);
794 Value *
W = expandCodeForImpl(
Op, Ty,
false);
795 Sum = InsertNoopCastOfTo(Sum, Ty);
808 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
814 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(
Op),
Op));
821 Value *Prod =
nullptr;
822 auto I = OpsAndLoops.begin();
827 const auto ExpandOpBinPowN = [
this, &
I, &OpsAndLoops, &Ty]() {
837 while (
E != OpsAndLoops.end() && *
I == *
E &&
Exponent != MaxExponent) {
841 assert(Exponent > 0 &&
"Trying to calculate a zeroth exponent of operand?");
845 Value *
P = expandCodeForImpl(
I->second, Ty,
false);
852 if (Exponent & BinExp)
860 assert(Result &&
"Nothing was expanded?");
864 while (
I != OpsAndLoops.end()) {
867 Prod = ExpandOpBinPowN();
868 }
else if (
I->second->isAllOnesValue()) {
870 Prod = InsertNoopCastOfTo(Prod, Ty);
876 Value *
W = ExpandOpBinPowN();
877 Prod = InsertNoopCastOfTo(Prod, Ty);
884 auto NWFlags =
S->getNoWrapFlags();
886 if (
RHS->logBase2() ==
RHS->getBitWidth() - 1)
888 Prod = InsertBinop(Instruction::Shl, Prod,
902 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
904 Value *
LHS = expandCodeForImpl(
S->getLHS(), Ty,
false);
907 if (
RHS.isPowerOf2())
908 return InsertBinop(Instruction::LShr,
LHS,
913 Value *
RHS = expandCodeForImpl(
S->getRHS(), Ty,
false);
915 SE.isKnownNonZero(
S->getRHS()));
923 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
928 if (L == IVIncInsertLoop) {
931 if (!SE.DT.dominates(OInst, IVIncInsertPos))
935 IncV = dyn_cast<Instruction>(IncV->
getOperand(0));
945 return isNormalAddRecExprPHI(PN, IncV, L);
960 if (IncV == InsertPos)
968 case Instruction::Sub: {
970 if (!OInst || SE.DT.dominates(OInst, InsertPos))
971 return dyn_cast<Instruction>(IncV->
getOperand(0));
974 case Instruction::BitCast:
975 return dyn_cast<Instruction>(IncV->
getOperand(0));
976 case Instruction::GetElementPtr:
978 if (isa<Constant>(U))
980 if (
Instruction *OInst = dyn_cast<Instruction>(U)) {
981 if (!SE.DT.dominates(OInst, InsertPos))
994 unsigned AS = cast<PointerType>(IncV->
getType())->getAddressSpace();
1000 return dyn_cast<Instruction>(IncV->
getOperand(0));
1014 if (
Builder.GetInsertPoint() == It)
1015 Builder.SetInsertPoint(&*NewInsertPt);
1016 for (
auto *InsertPtGuard : InsertPointGuards)
1017 if (InsertPtGuard->GetInsertPoint() == It)
1018 InsertPtGuard->SetInsertPoint(NewInsertPt);
1025 if (SE.DT.dominates(IncV, InsertPos))
1030 if (isa<PHINode>(InsertPos) ||
1034 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1040 Instruction *Oper = getIVIncOperand(IncV, InsertPos,
true);
1044 IVIncs.push_back(IncV);
1046 if (SE.DT.dominates(IncV, InsertPos))
1050 fixupInsertPoints(
I);
1051 I->moveBefore(InsertPos);
1081 PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1084 if (!isa<ConstantInt>(StepV))
1087 IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1091 IncV = useSubtract ?
1092 Builder.CreateSub(PN, StepV,
Twine(IVName) +
".iv.next") :
1093 Builder.CreateAdd(PN, StepV,
Twine(IVName) +
".iv.next");
1120 if (Phi == Requested) {
1135 if (!isa<IntegerType>(AR->
getType()))
1143 const SCEV *ExtendAfterOp =
1145 return ExtendAfterOp == OpAfterExtend;
1149 if (!isa<IntegerType>(AR->
getType()))
1157 const SCEV *ExtendAfterOp =
1159 return ExtendAfterOp == OpAfterExtend;
1166 SCEVExpander::getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
1172 assert((!IVIncInsertLoop||IVIncInsertPos) &&
"Uninitialized insert position");
1177 PHINode *AddRecPhiMatch =
nullptr;
1184 bool TryNonMatchingSCEV =
1186 SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1189 if (!SE.isSCEVable(PN.
getType()))
1196 DebugType,
dbgs() <<
"One incomplete PHI is found: " << PN <<
"\n");
1200 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1204 bool IsMatchingSCEV = PhiSCEV == Normalized;
1208 if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1219 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1222 if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1227 if (IsMatchingSCEV) {
1231 AddRecPhiMatch = &PN;
1237 if ((!TruncTy || InvertStep) &&
1241 AddRecPhiMatch = &PN;
1243 TruncTy = SE.getEffectiveSCEVType(Normalized->
getType());
1247 if (AddRecPhiMatch) {
1250 InsertedValues.insert(AddRecPhiMatch);
1252 rememberInstruction(IncV);
1254 ReusedValues.insert(AddRecPhiMatch);
1255 ReusedValues.insert(IncV);
1256 return AddRecPhiMatch;
1261 SCEVInsertPointGuard Guard(
Builder,
this);
1271 PostIncLoops.
clear();
1275 "Can't expand add recurrences without a loop preheader!");
1277 expandCodeForImpl(Normalized->
getStart(), ExpandTy,
1282 assert(!isa<Instruction>(StartV) ||
1283 SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
1294 Step = SE.getNegativeSCEV(Step);
1296 Value *StepV = expandCodeForImpl(
1302 bool IncrementIsNUW = !useSubtract &&
IsIncrementNUW(SE, Normalized);
1303 bool IncrementIsNSW = !useSubtract &&
IsIncrementNSW(SE, Normalized);
1309 PHINode *PN =
Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1310 Twine(IVName) +
".iv");
1327 Builder.SetInsertPoint(InsertPos);
1328 Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1330 if (isa<OverflowingBinaryOperator>(IncV)) {
1332 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1334 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1341 PostIncLoops = SavedPostIncLoops;
1345 InsertedValues.
insert(PN);
1346 InsertedIVs.push_back(PN);
1351 Type *STy =
S->getType();
1352 Type *IntTy = SE.getEffectiveSCEVType(STy);
1353 const Loop *L =
S->getLoop();
1358 if (PostIncLoops.count(L)) {
1366 const SCEV *PostLoopOffset =
nullptr;
1367 if (!SE.properlyDominates(Start, L->
getHeader())) {
1368 PostLoopOffset = Start;
1369 Start = SE.getConstant(Normalized->
getType(), 0);
1370 Normalized = cast<SCEVAddRecExpr>(
1378 const SCEV *PostLoopScale =
nullptr;
1379 if (!SE.dominates(Step, L->
getHeader())) {
1380 PostLoopScale = Step;
1381 Step = SE.getConstant(Normalized->
getType(), 1);
1382 if (!Start->isZero()) {
1385 assert(!PostLoopOffset &&
"Start not-null but PostLoopOffset set?");
1386 PostLoopOffset = Start;
1387 Start = SE.getConstant(Normalized->
getType(), 0);
1390 cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1391 Start, Step, Normalized->
getLoop(),
1397 Type *ExpandTy = PostLoopScale ? IntTy : STy;
1400 Type *AddRecPHIExpandTy =
1401 DL.isNonIntegralPointerType(STy) ? Normalized->
getType() : ExpandTy;
1405 Type *TruncTy =
nullptr;
1406 bool InvertStep =
false;
1407 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1408 IntTy, TruncTy, InvertStep);
1412 if (!PostIncLoops.count(L))
1417 assert(LatchBlock &&
"PostInc mode requires a unique loop latch!");
1423 if (isa<OverflowingBinaryOperator>(Result)) {
1424 auto *
I = cast<Instruction>(Result);
1425 if (!
S->hasNoUnsignedWrap())
1426 I->setHasNoUnsignedWrap(
false);
1427 if (!
S->hasNoSignedWrap())
1428 I->setHasNoSignedWrap(
false);
1434 if (isa<Instruction>(Result) &&
1435 !SE.DT.dominates(cast<Instruction>(Result),
1436 &*
Builder.GetInsertPoint())) {
1449 Step = SE.getNegativeSCEV(Step);
1453 SCEVInsertPointGuard Guard(
Builder,
this);
1454 StepV = expandCodeForImpl(
1457 Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1466 if (ResTy != SE.getEffectiveSCEVType(ResTy))
1467 Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1469 if (TruncTy !=
Result->getType())
1475 expandCodeForImpl(Normalized->
getStart(), TruncTy,
false), Result);
1479 if (PostLoopScale) {
1480 assert(
S->isAffine() &&
"Can't linearly scale non-affine recurrences.");
1481 Result = InsertNoopCastOfTo(Result, IntTy);
1483 expandCodeForImpl(PostLoopScale, IntTy,
false));
1487 if (PostLoopOffset) {
1488 if (
PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1489 if (
Result->getType()->isIntegerTy()) {
1490 Value *
Base = expandCodeForImpl(PostLoopOffset, ExpandTy,
false);
1491 Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy,
Base);
1493 Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1496 Result = InsertNoopCastOfTo(Result, IntTy);
1498 Result, expandCodeForImpl(PostLoopOffset, IntTy,
false));
1516 if (!CanonicalMode || (
S->getNumOperands() > 2))
1517 return expandAddRecExprLiterally(
S);
1519 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
1520 const Loop *L =
S->getLoop();
1523 PHINode *CanonicalIV =
nullptr;
1525 if (SE.getTypeSizeInBits(PN->
getType()) >= SE.getTypeSizeInBits(Ty))
1531 SE.getTypeSizeInBits(CanonicalIV->
getType()) > SE.getTypeSizeInBits(Ty) &&
1532 !
S->getType()->isPointerTy()) {
1534 for (
unsigned i = 0,
e =
S->getNumOperands();
i !=
e; ++
i)
1535 NewOps[
i] = SE.getAnyExtendExpr(
S->op_begin()[
i], CanonicalIV->
getType());
1536 Value *V =
expand(SE.getAddRecExpr(NewOps,
S->getLoop(),
1539 findInsertPointAfter(cast<Instruction>(V), &*
Builder.GetInsertPoint());
1540 V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty),
nullptr,
1541 &*NewInsertPt,
false);
1546 if (!
S->getStart()->isZero()) {
1547 if (
PointerType *PTy = dyn_cast<PointerType>(
S->getType())) {
1549 assert(StartV->
getType() == PTy &&
"Pointer type mismatch for GEP!");
1550 return expandAddToGEP(SE.removePointerBase(
S), PTy, Ty, StartV);
1554 NewOps[0] = SE.getConstant(Ty, 0);
1555 const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1562 const SCEV *AddExprLHS = SE.getUnknown(
expand(
S->getStart()));
1563 const SCEV *AddExprRHS = SE.getUnknown(
expand(Rest));
1564 return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1575 rememberInstruction(CanonicalIV);
1581 if (!PredSeen.
insert(HP).second) {
1595 rememberInstruction(Add);
1604 if (
S->isAffine() &&
S->getOperand(1)->isOne()) {
1605 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->
getType()) &&
1606 "IVs with types different from the canonical IV should "
1607 "already have been handled!");
1616 expand(SE.getTruncateOrNoop(
1617 SE.getMulExpr(SE.getUnknown(CanonicalIV),
1618 SE.getNoopOrAnyExtend(
S->getOperand(1),
1626 const SCEV *IH = SE.getUnknown(CanonicalIV);
1629 const SCEV *NewS =
S;
1631 if (isa<SCEVAddRecExpr>(
Ext))
1634 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1638 const SCEV *
T = SE.getTruncateOrNoop(V, Ty);
1644 expandCodeForImpl(
S->getOperand(),
S->getOperand()->getType(),
false);
1645 return ReuseOrCreateCast(V,
S->getType(), CastInst::PtrToInt,
1646 GetOptimalInsertionPointForCastOf(V));
1650 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
1651 Value *V = expandCodeForImpl(
1652 S->getOperand(), SE.getEffectiveSCEVType(
S->getOperand()->getType()),
1654 return Builder.CreateTrunc(V, Ty);
1658 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
1659 Value *V = expandCodeForImpl(
1660 S->getOperand(), SE.getEffectiveSCEVType(
S->getOperand()->getType()),
1662 return Builder.CreateZExt(V, Ty);
1666 Type *Ty = SE.getEffectiveSCEVType(
S->getType());
1667 Value *V = expandCodeForImpl(
1668 S->getOperand(), SE.getEffectiveSCEVType(
S->getOperand()->getType()),
1670 return Builder.CreateSExt(V, Ty);
1675 bool IsSequential) {
1680 for (
int i =
S->getNumOperands() - 2;
i >= 0; --
i) {
1681 Value *
RHS = expandCodeForImpl(
S->getOperand(
i), Ty,
false);
1682 if (IsSequential &&
i != 0)
1718 Value *SCEVExpander::expandCodeForImpl(
const SCEV *SH,
Type *Ty,
1721 Value *V = expandCodeForImpl(SH, Ty, Root);
1725 Value *SCEVExpander::expandCodeForImpl(
const SCEV *SH,
Type *Ty,
bool Root) {
1729 if (PreserveLCSSA) {
1730 if (
auto *Inst = dyn_cast<Instruction>(V)) {
1739 if (Inst->getType()->isIntegerTy())
1740 Tmp = cast<Instruction>(
Builder.CreateIntToPtr(
1741 Inst, Inst->getType()->getPointerTo(),
"tmp.lcssa.user"));
1743 assert(Inst->getType()->isPointerTy());
1744 Tmp = cast<Instruction>(
Builder.CreatePtrToInt(
1747 V = fixupLCSSAFormFor(Tmp, 0);
1750 InsertedValues.erase(Tmp);
1751 InsertedPostIncValues.erase(Tmp);
1756 InsertedExpressions[std::make_pair(SH, &*
Builder.GetInsertPoint())] = V;
1758 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->
getType()) &&
1759 "non-trivial casts should be done with the SCEVs directly!");
1760 V = InsertNoopCastOfTo(V, Ty);
1765 Value *SCEVExpander::FindValueInExprValueMap(
const SCEV *
S,
1769 if (!CanonicalMode && SE.containsAddRecurrence(
S))
1773 if (isa<SCEVConstant>(
S))
1779 for (
Value *V : SE.getSCEVValues(
S)) {
1785 if (
S->getType() == V->
getType() &&
1786 SE.DT.dominates(EntInst, InsertPt) &&
1787 (SE.LI.getLoopFor(EntInst->
getParent()) ==
nullptr ||
1788 SE.LI.getLoopFor(EntInst->
getParent())->contains(InsertPt)))
1807 auto SafeToHoist = [](
const SCEV *
S) {
1809 if (
const auto *
D = dyn_cast<SCEVUDivExpr>(
S)) {
1810 if (
const auto *
SC = dyn_cast<SCEVConstant>(
D->getRHS()))
1812 return SC->getValue()->isZero();
1822 if (SafeToHoist(
S)) {
1823 for (
Loop *L = SE.LI.getLoopFor(
Builder.GetInsertBlock());;
1825 if (SE.isLoopInvariant(
S, L)) {
1838 if (L && SE.hasComputableLoopEvolution(
S, L) && !PostIncLoops.count(L))
1842 (isInsertedInstruction(InsertPt) ||
1843 isa<DbgInfoIntrinsic>(InsertPt))) {
1852 auto I = InsertedExpressions.find(std::make_pair(
S, InsertPt));
1853 if (
I != InsertedExpressions.end())
1856 SCEVInsertPointGuard Guard(
Builder,
this);
1857 Builder.SetInsertPoint(InsertPt);
1860 Value *V = FindValueInExprValueMap(
S, InsertPt);
1868 if (
auto *
I = dyn_cast<Instruction>(V))
1870 I->dropPoisonGeneratingFlags();
1878 InsertedExpressions[std::make_pair(
S, InsertPt)] = V;
1882 void SCEVExpander::rememberInstruction(
Value *
I) {
1883 auto DoInsert = [
this](
Value *V) {
1884 if (!PostIncLoops.empty())
1885 InsertedPostIncValues.insert(V);
1887 InsertedValues.insert(V);
1894 if (
auto *Inst = dyn_cast<Instruction>(
I)) {
1898 for (
unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd;
1900 fixupLCSSAFormFor(Inst, OpIdx);
1917 Phis.push_back(&PN);
1930 unsigned NumElim = 0;
1938 if (!SE.isSCEVable(PN->
getType()))
1940 auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
1943 return Const->getValue();
1949 if (V->
getType() != Phi->getType())
1951 Phi->replaceAllUsesWith(V);
1955 dbgs() <<
"INDVARS: Eliminated constant iv: " << *Phi
1960 if (!SE.isSCEVable(Phi->getType()))
1963 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
1966 if (Phi->getType()->isIntegerTy() &&
TTI &&
1970 const SCEV *TruncExpr =
1971 SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
1972 ExprToIVMap[TruncExpr] = Phi;
1986 dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
1988 if (OrigInc && IsomorphicInc) {
1992 if (OrigPhiRef->
getType() == Phi->getType() &&
1993 !(ChainedPhis.count(Phi) ||
1994 isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
1995 (ChainedPhis.count(Phi) ||
1996 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
2007 const SCEV *TruncExpr =
2008 SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->
getType());
2009 if (OrigInc != IsomorphicInc &&
2010 TruncExpr == SE.getSCEV(IsomorphicInc) &&
2011 SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2012 hoistIVInc(OrigInc, IsomorphicInc)) {
2014 DebugType,
dbgs() <<
"INDVARS: Eliminated congruent iv.inc: "
2015 << *IsomorphicInc <<
'\n');
2016 Value *NewInc = OrigInc;
2019 if (
PHINode *PN = dyn_cast<PHINode>(OrigInc))
2026 NewInc =
Builder.CreateTruncOrBitCast(
2027 OrigInc, IsomorphicInc->
getType(), IVName);
2035 dbgs() <<
"INDVARS: Eliminated congruent iv: " << *Phi
2038 DebugType,
dbgs() <<
"INDVARS: Original iv: " << *OrigPhiRef <<
'\n');
2040 Value *NewIV = OrigPhiRef;
2041 if (OrigPhiRef->
getType() != Phi->getType()) {
2043 Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2044 NewIV =
Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->
getType(), IVName);
2046 Phi->replaceAllUsesWith(NewIV);
2065 if (!
match(
BB->getTerminator(),
2070 if (SE.getSCEV(
LHS) ==
S && SE.DT.dominates(
LHS, At))
2073 if (SE.getSCEV(
RHS) ==
S && SE.DT.dominates(
RHS, At))
2081 return FindValueInExprValueMap(
S, At);
2089 const T *
S = cast<T>(WorkItem.
S);
2092 struct OperationIndices {
2093 OperationIndices(
unsigned Opc,
size_t min,
size_t max) :
2094 Opcode(Opc), MinIdx(
min), MaxIdx(
max) { }
2108 S->getOperand(0)->getType(),
2112 auto ArithCost = [&](
unsigned Opcode,
unsigned NumRequired,
2113 unsigned MinIdx = 0,
2116 return NumRequired *
2120 auto CmpSelCost = [&](
unsigned Opcode,
unsigned NumRequired,
unsigned MinIdx,
2123 Type *OpType =
S->getOperand(0)->getType();
2129 switch (
S->getSCEVType()) {
2136 Cost = CastCost(Instruction::PtrToInt);
2139 Cost = CastCost(Instruction::Trunc);
2142 Cost = CastCost(Instruction::ZExt);
2145 Cost = CastCost(Instruction::SExt);
2148 unsigned Opcode = Instruction::UDiv;
2149 if (
auto *
SC = dyn_cast<SCEVConstant>(
S->getOperand(1)))
2150 if (
SC->getAPInt().isPowerOf2())
2151 Opcode = Instruction::LShr;
2152 Cost = ArithCost(Opcode, 1);
2171 Cost += CmpSelCost(Instruction::ICmp,
S->getNumOperands() - 1, 0, 1);
2173 switch (
S->getSCEVType()) {
2177 Cost += CmpSelCost(Instruction::ICmp,
S->getNumOperands() - 1, 0, 0);
2178 Cost += ArithCost(Instruction::Or,
2179 S->getNumOperands() > 2 ?
S->getNumOperands() - 2 : 0);
2184 assert(!isa<SCEVSequentialMinMaxExpr>(
S) &&
2185 "Unhandled SCEV expression type?");
2194 return !Op->isZero();
2197 assert(NumTerms >= 1 &&
"Polynominal should have at least one term.");
2198 assert(!(*std::prev(
S->operands().end()))->isZero() &&
2199 "Last operand should not be zero");
2202 int NumNonZeroDegreeNonOneTerms =
2204 auto *SConst = dyn_cast<SCEVConstant>(Op);
2205 return !SConst || SConst->getAPInt().ugt(1);
2215 Cost = AddCost + MulCost;
2218 int PolyDegree =
S->getNumOperands() - 1;
2219 assert(PolyDegree >= 1 &&
"Should be at least affine.");
2227 Cost += MulCost * (PolyDegree - 1);
2232 for (
auto &CostOp : Operations) {
2233 for (
auto SCEVOp :
enumerate(
S->operands())) {
2235 size_t MinIdx =
std::max(SCEVOp.index(), CostOp.MinIdx);
2236 size_t OpIdx =
std::min(MinIdx, CostOp.MaxIdx);
2237 Worklist.
emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2243 bool SCEVExpander::isHighCostExpansionHelper(
2251 const SCEV *
S = WorkItem.
S;
2253 if (!isa<SCEVConstant>(
S) && !Processed.
insert(
S).second)
2258 if (getRelatedExistingExpansion(
S, &At, L))
2266 switch (
S->getSCEVType()) {
2276 const APInt &Imm = cast<SCEVConstant>(
S)->getAPInt();
2277 Type *Ty =
S->getType();
2280 return Cost > Budget;
2287 costAndCollectOperands<SCEVCastExpr>(WorkItem,
TTI,
CostKind, Worklist);
2299 if (getRelatedExistingExpansion(
2300 SE.getAddExpr(
S, SE.getConstant(
S->getType(), 1)), &At, L))
2304 costAndCollectOperands<SCEVUDivExpr>(WorkItem,
TTI,
CostKind, Worklist);
2314 assert(cast<SCEVNAryExpr>(
S)->getNumOperands() > 1 &&
2315 "Nary expr should have more than 1 operand.");
2319 costAndCollectOperands<SCEVNAryExpr>(WorkItem,
TTI,
CostKind, Worklist);
2320 return Cost > Budget;
2323 assert(cast<SCEVAddRecExpr>(
S)->getNumOperands() >= 2 &&
2324 "Polynomial should be at least linear");
2325 Cost += costAndCollectOperands<SCEVAddRecExpr>(
2327 return Cost > Budget;
2338 return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred),
IP);
2340 return expandComparePredicate(cast<SCEVComparePredicate>(Pred),
IP);
2342 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2343 return expandWrapPredicate(AddRecPred,
IP);
2358 auto *
I =
Builder.CreateICmp(InvPred, Expr0, Expr1,
"ident.check");
2365 "non-affine expression");
2369 const SCEV *ExitCount =
2370 SE.getPredicatedBackedgeTakenCount(AR->
getLoop(), Pred);
2372 assert(!isa<SCEVCouldNotCompute>(ExitCount) &&
"Invalid loop count");
2378 unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->
getType());
2379 unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2388 Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc,
false);
2393 Value *StepValue = expandCodeForImpl(Step, Ty, Loc,
false);
2394 Value *NegStepValue =
2395 expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc,
false);
2396 Value *StartValue = expandCodeForImpl(Start, ARTy, Loc,
false);
2404 Value *AbsStep =
Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2414 auto ComputeEndCheck = [&]() ->
Value * {
2416 if (!
Signed && Start->isZero() && SE.isKnownPositive(Step))
2420 Value *TruncTripCount =
Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2422 Value *MulV, *OfMul;
2423 if (Step->
isOne()) {
2427 MulV = TruncTripCount;
2431 Intrinsic::umul_with_overflow, Ty);
2433 Builder.CreateCall(MulF, {AbsStep, TruncTripCount},
"mul");
2434 MulV =
Builder.CreateExtractValue(
Mul, 0,
"mul.result");
2435 OfMul =
Builder.CreateExtractValue(
Mul, 1,
"mul.overflow");
2438 Value *Add =
nullptr, *Sub =
nullptr;
2439 bool NeedPosCheck = !SE.isKnownNegative(Step);
2440 bool NeedNegCheck = !SE.isKnownPositive(Step);
2442 if (
PointerType *ARPtrTy = dyn_cast<PointerType>(ARTy)) {
2443 StartValue = InsertNoopCastOfTo(
2444 StartValue,
Builder.getInt8PtrTy(ARPtrTy->getAddressSpace()));
2449 Sub =
Builder.CreateGEP(
Builder.getInt8Ty(), StartValue, NegMulV);
2452 Add =
Builder.CreateAdd(StartValue, MulV);
2454 Sub =
Builder.CreateSub(StartValue, MulV);
2457 Value *EndCompareLT =
nullptr;
2458 Value *EndCompareGT =
nullptr;
2459 Value *EndCheck =
nullptr;
2461 EndCheck = EndCompareLT =
Builder.CreateICmp(
2464 EndCheck = EndCompareGT =
Builder.CreateICmp(
2466 if (NeedPosCheck && NeedNegCheck) {
2468 EndCheck =
Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2470 return Builder.CreateOr(EndCheck, OfMul);
2472 Value *EndCheck = ComputeEndCheck();
2477 if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2479 auto *BackedgeCheck =
2482 BackedgeCheck =
Builder.CreateAnd(
2485 EndCheck =
Builder.CreateOr(EndCheck, BackedgeCheck);
2493 const auto *A = cast<SCEVAddRecExpr>(Pred->
getExpr());
2494 Value *NSSWCheck =
nullptr, *NUSWCheck =
nullptr;
2498 NUSWCheck = generateOverflowCheck(A,
IP,
false);
2502 NSSWCheck = generateOverflowCheck(A,
IP,
true);
2504 if (NUSWCheck && NSSWCheck)
2505 return Builder.CreateOr(NUSWCheck, NSSWCheck);
2520 for (
auto Pred : Union->getPredicates()) {
2521 Checks.push_back(expandCodeForPredicate(Pred,
IP));
2527 return Builder.CreateOr(Checks);
2535 auto *OpI = dyn_cast<Instruction>(OpV);
2539 Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent());
2540 Loop *UseLoop = SE.LI.getLoopFor(
User->getParent());
2541 if (!DefLoop || UseLoop == DefLoop || DefLoop->
contains(UseLoop))
2544 ToUpdate.push_back(OpI);
2547 for (
PHINode *PN : PHIsToRemove) {
2550 InsertedValues.erase(PN);
2551 InsertedPostIncValues.erase(PN);
2579 struct SCEVFindUnsafe {
2582 bool IsUnsafe =
false;
2585 : SE(SE), CanonicalMode(CanonicalMode) {}
2587 bool follow(
const SCEV *
S) {
2590 if (!
SC ||
SC->getValue()->isZero()) {
2596 const SCEV *Step = AR->getStepRecurrence(SE);
2597 if (!AR->isAffine() && !SE.
dominates(Step, AR->getLoop()->getHeader())) {
2604 if (!AR->getLoop()->getLoopPreheader() &&
2605 (!CanonicalMode || !AR->isAffine())) {
2612 bool isDone()
const {
return IsUnsafe; }
2618 SCEVFindUnsafe Search(SE, CanonicalMode);
2620 return !Search.IsUnsafe;
2650 auto InsertedInstructions = Expander.getAllInsertedInstructions();
2653 InsertedInstructions.end());
2663 [&InsertedSet](
Value *U) {
2664 return InsertedSet.contains(cast<Instruction>(U));
2666 "removed instruction should only be used by instructions inserted "
2667 "during expansion");
2669 assert(!
I->getType()->isVoidTy() &&
2670 "inserted instruction should have non-void types");
2672 I->eraseFromParent();