132#define DEBUG_TYPE "loop-reduce"
148 return Opts.stress_ivchain;
158 static const unsigned UnknownAddressSpace =
159 std::numeric_limits<unsigned>::max();
161 Type *MemTy =
nullptr;
162 unsigned AddrSpace = UnknownAddressSpace;
164 MemAccessTy() =
default;
165 MemAccessTy(
Type *Ty,
unsigned AS) : MemTy(Ty), AddrSpace(AS) {}
168 return MemTy ==
Other.MemTy && AddrSpace ==
Other.AddrSpace;
173 static MemAccessTy getUnknown(LLVMContext &Ctx,
174 unsigned AS = UnknownAddressSpace) {
175 return MemAccessTy(Type::getVoidTy(Ctx), AS);
186 SmallBitVector UsedByIndices;
188 void print(raw_ostream &OS)
const;
195 constexpr Immediate(ScalarTy MinVal,
bool Scalable)
196 : FixedOrScalableQuantity(MinVal, Scalable) {}
198 constexpr Immediate(
const FixedOrScalableQuantity<Immediate, int64_t> &
V)
199 : FixedOrScalableQuantity(
V) {}
202 constexpr Immediate() =
delete;
204 static constexpr Immediate getFixed(ScalarTy MinVal) {
205 return {MinVal,
false};
207 static constexpr Immediate getScalable(ScalarTy MinVal) {
208 return {MinVal,
true};
210 static constexpr Immediate
get(ScalarTy MinVal,
bool Scalable) {
211 return {MinVal, Scalable};
213 static constexpr Immediate getZero() {
return {0,
false}; }
214 static constexpr Immediate getFixedMin() {
215 return {std::numeric_limits<int64_t>::min(),
false};
217 static constexpr Immediate getFixedMax() {
218 return {std::numeric_limits<int64_t>::max(),
false};
220 static constexpr Immediate getScalableMin() {
221 return {std::numeric_limits<int64_t>::min(),
true};
223 static constexpr Immediate getScalableMax() {
224 return {std::numeric_limits<int64_t>::max(),
true};
227 constexpr bool isLessThanZero()
const {
return Quantity < 0; }
229 constexpr bool isGreaterThanZero()
const {
return Quantity > 0; }
231 constexpr bool isCompatibleImmediate(
const Immediate &
Imm)
const {
232 return isZero() ||
Imm.isZero() ||
Imm.Scalable == Scalable;
235 constexpr bool isMin()
const {
236 return Quantity == std::numeric_limits<ScalarTy>::min();
239 constexpr bool isMax()
const {
240 return Quantity == std::numeric_limits<ScalarTy>::max();
244 constexpr Immediate addUnsigned(
const Immediate &
RHS)
const {
245 assert(isCompatibleImmediate(
RHS) &&
"Incompatible Immediates");
247 return {
Value, Scalable ||
RHS.isScalable()};
250 constexpr Immediate subUnsigned(
const Immediate &
RHS)
const {
251 assert(isCompatibleImmediate(
RHS) &&
"Incompatible Immediates");
253 return {
Value, Scalable ||
RHS.isScalable()};
257 constexpr Immediate mulUnsigned(
const ScalarTy
RHS)
const {
259 return {
Value, Scalable};
263 const SCEV *getSCEV(ScalarEvolution &SE,
Type *Ty)
const {
270 const SCEV *getNegativeSCEV(ScalarEvolution &SE,
Type *Ty)
const {
277 const SCEV *getUnknownSCEV(ScalarEvolution &SE,
Type *Ty)
const {
292struct KeyOrderTargetImmediate {
293 bool operator()(
const Immediate &
LHS,
const Immediate &
RHS)
const {
294 if (
LHS.isScalable() && !
RHS.isScalable())
296 if (!
LHS.isScalable() &&
RHS.isScalable())
298 return LHS.getKnownMinValue() <
RHS.getKnownMinValue();
305struct KeyOrderSizeTAndImmediate {
306 bool operator()(
const std::pair<size_t, Immediate> &
LHS,
307 const std::pair<size_t, Immediate> &
RHS)
const {
308 size_t LSize =
LHS.first;
309 size_t RSize =
RHS.first;
311 return LSize < RSize;
312 return KeyOrderTargetImmediate()(
LHS.second,
RHS.second);
317#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
319 OS <<
"[NumUses=" << UsedByIndices.
count() <<
']';
331 using RegUsesTy = DenseMap<const SCEV *, RegSortData>;
333 RegUsesTy RegUsesMap;
337 void countRegister(
const SCEV *
Reg,
size_t LUIdx);
338 void dropRegister(
const SCEV *
Reg,
size_t LUIdx);
339 void swapAndDropUse(
size_t LUIdx,
size_t LastLUIdx);
341 bool isRegUsedByUsesOtherThan(
const SCEV *
Reg,
size_t LUIdx)
const;
343 const SmallBitVector &getUsedByIndices(
const SCEV *
Reg)
const;
359RegUseTracker::countRegister(
const SCEV *
Reg,
size_t LUIdx) {
360 std::pair<RegUsesTy::iterator, bool> Pair = RegUsesMap.try_emplace(
Reg);
361 RegSortData &RSD = Pair.first->second;
364 RSD.UsedByIndices.
resize(std::max(RSD.UsedByIndices.
size(), LUIdx + 1));
365 RSD.UsedByIndices.
set(LUIdx);
369RegUseTracker::dropRegister(
const SCEV *
Reg,
size_t LUIdx) {
370 RegUsesTy::iterator It = RegUsesMap.find(
Reg);
371 assert(It != RegUsesMap.end());
372 RegSortData &RSD = It->second;
374 RSD.UsedByIndices.
reset(LUIdx);
378RegUseTracker::swapAndDropUse(
size_t LUIdx,
size_t LastLUIdx) {
379 assert(LUIdx <= LastLUIdx);
383 for (
auto &Pair : RegUsesMap) {
384 SmallBitVector &UsedByIndices = Pair.second.UsedByIndices;
385 if (LUIdx < UsedByIndices.
size())
386 UsedByIndices[LUIdx] =
387 LastLUIdx < UsedByIndices.
size() ? UsedByIndices[LastLUIdx] :
false;
388 UsedByIndices.
resize(std::min(UsedByIndices.
size(), LastLUIdx));
393RegUseTracker::isRegUsedByUsesOtherThan(
const SCEV *
Reg,
size_t LUIdx)
const {
394 RegUsesTy::const_iterator
I = RegUsesMap.find(
Reg);
395 if (
I == RegUsesMap.end())
397 const SmallBitVector &UsedByIndices =
I->second.UsedByIndices;
399 if (i == -1)
return false;
400 if ((
size_t)i != LUIdx)
return true;
404const SmallBitVector &RegUseTracker::getUsedByIndices(
const SCEV *
Reg)
const {
405 RegUsesTy::const_iterator
I = RegUsesMap.find(
Reg);
406 assert(
I != RegUsesMap.end() &&
"Unknown register!");
407 return I->second.UsedByIndices;
410void RegUseTracker::clear() {
421 GlobalValue *BaseGV =
nullptr;
424 Immediate BaseOffset = Immediate::getZero();
427 bool HasBaseReg =
false;
450 const SCEV *ScaledReg =
nullptr;
455 Immediate UnfoldedOffset = Immediate::getZero();
459 void initialMatch(
const SCEV *S,
Loop *L, ScalarEvolution &SE);
463 void canonicalize(
const Loop &L);
467 bool hasZeroEnd()
const;
469 bool countsDownToZero()
const;
471 size_t getNumRegs()
const;
474 void deleteBaseReg(
const SCEV *&S);
476 bool referencesReg(
const SCEV *S)
const;
477 bool hasRegsUsedByUsesOtherThan(
size_t LUIdx,
478 const RegUseTracker &RegUses)
const;
480 void print(raw_ostream &OS)
const;
498 for (
const SCEV *S :
Add->operands())
504 const SCEV *Start, *Step;
519 if (
Mul->getOperand(0)->isAllOnesValue()) {
528 for (
const SCEV *S : MyGood)
530 for (
const SCEV *S : MyBad)
542void Formula::initialMatch(
const SCEV *S,
Loop *L, ScalarEvolution &SE) {
549 BaseRegs.push_back(Sum);
555 BaseRegs.push_back(Sum);
570bool Formula::isCanonical(
const Loop &L)
const {
571 assert((Scale == 0 || ScaledReg) &&
572 "ScaledReg must be non-null if Scale is non-zero");
575 return BaseRegs.size() <= 1;
580 if (Scale == 1 && BaseRegs.empty())
589 return none_of(BaseRegs, [&L](
const SCEV *S) {
600void Formula::canonicalize(
const Loop &L) {
604 if (BaseRegs.empty()) {
606 assert(ScaledReg &&
"Expected 1*reg => reg");
607 assert(Scale == 1 &&
"Expected 1*reg => reg");
608 BaseRegs.push_back(ScaledReg);
616 ScaledReg = BaseRegs.pop_back_val();
624 auto I =
find_if(BaseRegs, [&L](
const SCEV *S) {
627 if (
I != BaseRegs.end())
637bool Formula::unscale() {
641 BaseRegs.push_back(ScaledReg);
646bool Formula::hasZeroEnd()
const {
647 if (UnfoldedOffset || BaseOffset)
649 if (BaseRegs.size() != 1 || ScaledReg)
654bool Formula::countsDownToZero()
const {
657 assert(BaseRegs.size() == 1 &&
"hasZeroEnd should mean one BaseReg");
658 const APInt *StepInt;
666size_t Formula::getNumRegs()
const {
667 return !!ScaledReg + BaseRegs.size();
672Type *Formula::getType()
const {
673 return !BaseRegs.empty() ? BaseRegs.front()->getType() :
674 ScaledReg ? ScaledReg->
getType() :
680void Formula::deleteBaseReg(
const SCEV *&S) {
681 if (&S != &BaseRegs.back())
687bool Formula::referencesReg(
const SCEV *S)
const {
693bool Formula::hasRegsUsedByUsesOtherThan(
size_t LUIdx,
694 const RegUseTracker &RegUses)
const {
696 if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx))
698 for (
const SCEV *BaseReg : BaseRegs)
699 if (RegUses.isRegUsedByUsesOtherThan(BaseReg, LUIdx))
704#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
705void Formula::print(raw_ostream &OS)
const {
706 ListSeparator
Plus(
" + ");
711 if (BaseOffset.isNonZero())
712 OS <<
Plus << BaseOffset;
714 for (
const SCEV *BaseReg : BaseRegs)
717 if (HasBaseReg && BaseRegs.empty())
718 OS <<
Plus <<
"**error: HasBaseReg**";
719 else if (!HasBaseReg && !BaseRegs.empty())
720 OS <<
Plus <<
"**error: !HasBaseReg**";
723 OS <<
Plus << Scale <<
"*reg(";
730 if (UnfoldedOffset.isNonZero())
731 OS <<
Plus <<
"imm(" << UnfoldedOffset <<
')';
771 bool IgnoreSignificantBits =
false) {
786 if (
RA.isAllOnes()) {
787 if (
LHS->getType()->isPointerTy())
800 const APInt &LA =
C->getAPInt();
809 if ((IgnoreSignificantBits ||
isAddRecSExtable(AR, SE)) && AR->isAffine()) {
811 IgnoreSignificantBits);
812 if (!Step)
return nullptr;
814 IgnoreSignificantBits);
815 if (!Start)
return nullptr;
828 for (
const SCEV *S :
Add->operands()) {
830 if (!
Op)
return nullptr;
858 for (
const SCEV *S :
Mul->operands()) {
861 IgnoreSignificantBits)) {
882 bool PreferScalable) {
885 Immediate Result = Immediate::getZero();
894 C->getSignificantBits() <= 64) {
896 Result = Immediate::getFixed(
C->getSExtValue());
901 if (Opts.lsr_enable_vscale_immediates &&
902 (Result.isZero() || PreferScalable)) {
909 Result = Immediate::getScalable(
C->getSExtValue());
915 if (Result.isNonZero()) {
927 bool PreferScalable =
false) {
934 if (Result.isNonZero())
941 if (Result.isNonZero())
982 if (
SI->getPointerOperand() == OperandVal)
987 switch (
II->getIntrinsicID()) {
988 case Intrinsic::memset:
989 case Intrinsic::prefetch:
990 case Intrinsic::masked_load:
991 if (
II->getArgOperand(0) == OperandVal)
994 case Intrinsic::masked_store:
995 if (
II->getArgOperand(1) == OperandVal)
998 case Intrinsic::memmove:
999 case Intrinsic::memcpy:
1000 if (
II->getArgOperand(0) == OperandVal ||
1001 II->getArgOperand(1) == OperandVal)
1006 if (
TTI.getTgtMemIntrinsic(
II, IntrInfo)) {
1007 if (IntrInfo.
PtrVal == OperandVal)
1013 if (RMW->getPointerOperand() == OperandVal)
1016 if (CmpX->getPointerOperand() == OperandVal)
1025 MemAccessTy AccessTy = MemAccessTy::getUnknown(Inst->
getContext());
1029 AccessTy.MemTy = Ty;
1033 AccessTy.AddrSpace =
SI->getPointerAddressSpace();
1035 AccessTy.AddrSpace = LI->getPointerAddressSpace();
1037 AccessTy.AddrSpace = RMW->getPointerAddressSpace();
1039 AccessTy.AddrSpace = CmpX->getPointerAddressSpace();
1041 switch (
II->getIntrinsicID()) {
1042 case Intrinsic::prefetch:
1043 case Intrinsic::memset:
1044 AccessTy.AddrSpace =
II->getArgOperand(0)->getType()->getPointerAddressSpace();
1045 AccessTy.MemTy = OperandVal->
getType();
1047 case Intrinsic::memmove:
1048 case Intrinsic::memcpy:
1050 AccessTy.MemTy = OperandVal->
getType();
1052 case Intrinsic::masked_load:
1053 AccessTy.AddrSpace =
1054 II->getArgOperand(0)->getType()->getPointerAddressSpace();
1056 case Intrinsic::masked_store:
1057 AccessTy.AddrSpace =
1058 II->getArgOperand(1)->getType()->getPointerAddressSpace();
1062 if (
TTI.getTgtMemIntrinsic(
II, IntrInfo) && IntrInfo.
PtrVal) {
1118 if (!Processed.
insert(S).second)
1122 for (
const SCEV *S :
Add->operands()) {
1129 const SCEV *Op0, *Op1;
1138 Value *UVal = U->getValue();
1142 if (UI && UI->
getOpcode() == Instruction::Mul &&
1175 const LSRUse &LU,
const Formula &
F);
1179 const LSRUse &LU,
const Formula &
F,
1186 const ScalarOptions *Opts =
nullptr;
1187 const Loop *
L =
nullptr;
1188 ScalarEvolution *SE =
nullptr;
1189 const TargetTransformInfo *
TTI =
nullptr;
1190 TargetTransformInfo::LSRCost
C;
1195 Cost(
const ScalarOptions &Opts,
const Loop *L, ScalarEvolution &SE,
1197 : Opts(&Opts),
L(
L), SE(&SE),
TTI(&
TTI), AMK(AMK) {
1206 C.NumPrePostIndex = 0;
1216 return ((
C.Insns |
C.NumRegs |
C.AddRecCost |
C.NumIVMuls |
C.NumBaseAdds |
1217 C.ImmCost |
C.SetupCost |
C.ScaleCost |
C.NumPrePostIndex) !=
1219 ((
C.Insns &
C.NumRegs &
C.AddRecCost &
C.NumIVMuls &
C.NumBaseAdds &
1220 C.ImmCost &
C.SetupCost &
C.ScaleCost &
C.NumPrePostIndex) == ~0
u);
1226 return C.NumRegs == ~0
u;
1229 void RateFormula(
const Formula &
F, SmallPtrSetImpl<const SCEV *> &Regs,
1230 const DenseSet<const SCEV *> &VisitedRegs,
const LSRUse &LU,
1231 bool HardwareLoopProfitable,
1232 SmallPtrSetImpl<const SCEV *> *LoserRegs =
nullptr);
1234 void print(raw_ostream &OS)
const;
1238 void RateRegister(
const Formula &
F,
const SCEV *
Reg,
1239 SmallPtrSetImpl<const SCEV *> &Regs,
const LSRUse &LU,
1240 bool HardwareLoopProfitable);
1241 void RatePrimaryRegister(
const Formula &
F,
const SCEV *
Reg,
1242 SmallPtrSetImpl<const SCEV *> &Regs,
1243 const LSRUse &LU,
bool HardwareLoopProfitable,
1244 SmallPtrSetImpl<const SCEV *> *LoserRegs);
1255 Value *OperandValToReplace =
nullptr;
1265 Immediate
Offset = Immediate::getZero();
1267 LSRFixup() =
default;
1269 bool isUseFullyOutsideLoop(
const Loop *L)
const;
1271 void print(raw_ostream &OS)
const;
1281 DenseSet<SmallVector<const SCEV *, 4>> Uniquifier;
1294 using SCEVUseKindPair = PointerIntPair<const SCEV *, 2, KindType>;
1297 MemAccessTy AccessTy;
1303 Immediate MinOffset = Immediate::getFixedMax();
1304 Immediate MaxOffset = Immediate::getFixedMin();
1308 bool AllFixupsOutsideLoop =
true;
1313 bool AllFixupsUnconditional =
true;
1320 bool RigidFormula =
false;
1328 SmallPtrSet<const SCEV *, 4> Regs;
1330 LSRUse(KindType K, MemAccessTy AT) :
Kind(
K), AccessTy(AT) {}
1332 LSRFixup &getNewFixup() {
1333 Fixups.push_back(LSRFixup());
1337 void pushFixup(LSRFixup &f) {
1339 if (Immediate::isKnownGT(
f.Offset, MaxOffset))
1340 MaxOffset =
f.Offset;
1341 if (Immediate::isKnownLT(
f.Offset, MinOffset))
1342 MinOffset =
f.Offset;
1345 bool HasFormulaWithSameRegs(
const Formula &
F)
const;
1346 float getNotSelectedProbability(
const SCEV *
Reg)
const;
1347 bool InsertFormula(
const Formula &
F,
const Loop &L);
1348 void DeleteFormula(Formula &
F);
1349 void RecomputeRegs(
size_t LUIdx, RegUseTracker &Reguses);
1351 void print(raw_ostream &OS)
const;
1358 LSRUse::KindType Kind, MemAccessTy AccessTy,
1359 GlobalValue *BaseGV, Immediate BaseOffset,
1360 bool HasBaseReg, int64_t Scale,
1361 Instruction *Fixup =
nullptr);
1368 if (
TTI.getIntImmCost(
C->getAPInt(),
C->getType(),
1382 [&](
unsigned i,
const SCEV *
Reg) {
1383 return i + getSetupCost(Reg, Depth - 1, TTI);
1392void Cost::RateRegister(
const Formula &
F,
const SCEV *
Reg,
1393 SmallPtrSetImpl<const SCEV *> &Regs,
const LSRUse &LU,
1394 bool HardwareLoopProfitable) {
1399 if (AR->getLoop() != L) {
1406 if (!AR->getLoop()->contains(L)) {
1416 unsigned LoopCost = 1;
1417 if (LU.Kind == LSRUse::Address &&
1426 F.BaseOffset.isFixed() &&
1427 *Step ==
F.BaseOffset.getFixedValue();
1432 if ((CanPreIndex || CanPostIndex) && LU.AllFixupsUnconditional) {
1433 ++
C.NumPrePostIndex;
1441 if (LU.Kind == LSRUse::ICmpZero &&
F.countsDownToZero() &&
1442 HardwareLoopProfitable)
1444 C.AddRecCost += LoopCost;
1448 const SCEV *StepReg = AR->getOperand(1);
1453 auto IsVScaleStep = [](
const SCEV *
Reg,
const TargetTransformInfo *
TTI) {
1459 if (!Regs.
count(StepReg) && !IsVScaleStep(StepReg,
TTI)) {
1460 RateRegister(
F, StepReg, Regs, LU, HardwareLoopProfitable);
1472 C.SetupCost = std::min<unsigned>(
C.SetupCost, 1 << 16);
1481void Cost::RatePrimaryRegister(
const Formula &
F,
const SCEV *
Reg,
1482 SmallPtrSetImpl<const SCEV *> &Regs,
1483 const LSRUse &LU,
bool HardwareLoopProfitable,
1484 SmallPtrSetImpl<const SCEV *> *LoserRegs) {
1485 if (LoserRegs && LoserRegs->
count(
Reg)) {
1490 RateRegister(
F,
Reg, Regs, LU, HardwareLoopProfitable);
1491 if (LoserRegs && isLoser())
1496void Cost::RateFormula(
const Formula &
F, SmallPtrSetImpl<const SCEV *> &Regs,
1497 const DenseSet<const SCEV *> &VisitedRegs,
1498 const LSRUse &LU,
bool HardwareLoopProfitable,
1499 SmallPtrSetImpl<const SCEV *> *LoserRegs) {
1502 assert(
F.isCanonical(*L) &&
"Cost is accurate only for canonical formula");
1504 unsigned PrevAddRecCost =
C.AddRecCost;
1505 unsigned PrevNumRegs =
C.NumRegs;
1506 unsigned PrevNumBaseAdds =
C.NumBaseAdds;
1507 if (
const SCEV *ScaledReg =
F.ScaledReg) {
1508 if (VisitedRegs.
count(ScaledReg)) {
1512 RatePrimaryRegister(
F, ScaledReg, Regs, LU, HardwareLoopProfitable,
1517 for (
const SCEV *BaseReg :
F.BaseRegs) {
1518 if (VisitedRegs.
count(BaseReg)) {
1522 RatePrimaryRegister(
F, BaseReg, Regs, LU, HardwareLoopProfitable,
1529 size_t NumBaseParts =
F.getNumRegs();
1530 if (NumBaseParts > 1)
1535 C.NumBaseAdds += (
F.UnfoldedOffset.isNonZero());
1541 for (
const LSRFixup &Fixup : LU.Fixups) {
1542 if (
Fixup.Offset.isCompatibleImmediate(
F.BaseOffset)) {
1543 Immediate
Offset =
Fixup.Offset.addUnsigned(
F.BaseOffset);
1547 else if (
Offset.isNonZero())
1549 APInt(64,
Offset.getKnownMinValue(),
true).getSignificantBits();
1553 if (LU.Kind == LSRUse::Address &&
Offset.isNonZero() &&
1564 if (!
valueOr(Opts->lsr_insns_cost,
true)) {
1574 if (
C.NumRegs > TTIRegNum) {
1577 if (PrevNumRegs > TTIRegNum)
1578 C.Insns += (
C.NumRegs - PrevNumRegs);
1580 C.Insns += (
C.NumRegs - TTIRegNum);
1593 if (LU.Kind == LSRUse::ICmpZero && !
F.hasZeroEnd() &&
1597 C.Insns += (
C.AddRecCost - PrevAddRecCost);
1600 if (LU.Kind != LSRUse::ICmpZero)
1601 C.Insns +=
C.NumBaseAdds - PrevNumBaseAdds;
1607 C.Insns = std::numeric_limits<unsigned>::max();
1608 C.NumRegs = std::numeric_limits<unsigned>::max();
1609 C.AddRecCost = std::numeric_limits<unsigned>::max();
1610 C.NumIVMuls = std::numeric_limits<unsigned>::max();
1611 C.NumBaseAdds = std::numeric_limits<unsigned>::max();
1612 C.ImmCost = std::numeric_limits<unsigned>::max();
1613 C.SetupCost = std::numeric_limits<unsigned>::max();
1614 C.ScaleCost = std::numeric_limits<unsigned>::max();
1615 C.NumPrePostIndex = std::numeric_limits<unsigned>::max();
1619bool Cost::isLess(
const Cost &
Other)
const {
1620 if (Opts->lsr_insns_cost == BoolOrDefault::True &&
C.Insns !=
Other.C.Insns)
1621 return C.Insns <
Other.C.Insns;
1625#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1627 if (
valueOr(Opts->lsr_insns_cost,
true))
1628 OS <<
C.Insns <<
" instruction" << (
C.Insns == 1 ?
" " :
"s ");
1629 OS <<
C.NumRegs <<
" reg" << (
C.NumRegs == 1 ?
"" :
"s");
1630 if (
C.AddRecCost != 0)
1631 OS <<
", with addrec cost " <<
C.AddRecCost;
1632 if (
C.NumIVMuls != 0)
1633 OS <<
", plus " <<
C.NumIVMuls <<
" IV mul"
1634 << (
C.NumIVMuls == 1 ?
"" :
"s");
1635 if (
C.NumBaseAdds != 0)
1636 OS <<
", plus " <<
C.NumBaseAdds <<
" base add"
1637 << (
C.NumBaseAdds == 1 ?
"" :
"s");
1638 if (
C.ScaleCost != 0)
1639 OS <<
", plus " <<
C.ScaleCost <<
" scale cost";
1641 OS <<
", plus " <<
C.ImmCost <<
" imm cost";
1642 if (
C.SetupCost != 0)
1643 OS <<
", plus " <<
C.SetupCost <<
" setup cost";
1644 if (
C.NumPrePostIndex != 0)
1645 OS <<
", plus " <<
C.NumPrePostIndex <<
" pre/post-index";
1654bool LSRFixup::isUseFullyOutsideLoop(
const Loop *L)
const {
1657 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1658 if (PN->getIncomingValue(i) == OperandValToReplace &&
1659 L->contains(PN->getIncomingBlock(i)))
1664 return !
L->contains(UserInst);
1667#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1668void LSRFixup::print(raw_ostream &OS)
const {
1673 Store->getOperand(0)->printAsOperand(OS,
false);
1679 OS <<
", OperandValToReplace=";
1682 for (
const Loop *PIL : PostIncLoops) {
1683 OS <<
", PostIncLoop=";
1684 PIL->getHeader()->printAsOperand(OS,
false);
1688 OS <<
", Offset=" <<
Offset;
1698bool LSRUse::HasFormulaWithSameRegs(
const Formula &
F)
const {
1700 if (
F.ScaledReg)
Key.push_back(
F.ScaledReg);
1707float LSRUse::getNotSelectedProbability(
const SCEV *
Reg)
const {
1709 for (
const Formula &
F : Formulae)
1710 if (
F.referencesReg(
Reg))
1712 return ((
float)(Formulae.size() - FNum)) / Formulae.size();
1717bool LSRUse::InsertFormula(
const Formula &
F,
const Loop &L) {
1718 assert(
F.isCanonical(L) &&
"Invalid canonical representation");
1720 if (!Formulae.empty() && RigidFormula)
1724 if (
F.ScaledReg)
Key.push_back(
F.ScaledReg);
1732 assert((!
F.ScaledReg || !
F.ScaledReg->isZero()) &&
1733 "Zero allocated in a scaled register!");
1735 for (
const SCEV *BaseReg :
F.BaseRegs)
1736 assert(!
BaseReg->isZero() &&
"Zero allocated in a base register!");
1740 Formulae.push_back(
F);
1751void LSRUse::DeleteFormula(Formula &
F) {
1752 if (&
F != &Formulae.back())
1754 Formulae.pop_back();
1758void LSRUse::RecomputeRegs(
size_t LUIdx, RegUseTracker &RegUses) {
1760 SmallPtrSet<const SCEV *, 4> OldRegs = std::move(Regs);
1762 for (
const Formula &
F : Formulae) {
1763 if (
F.ScaledReg) Regs.
insert(
F.ScaledReg);
1768 for (
const SCEV *S : OldRegs)
1770 RegUses.dropRegister(S, LUIdx);
1773#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1774void LSRUse::print(raw_ostream &OS)
const {
1775 OS <<
"LSR Use: Kind=";
1777 case Basic: OS <<
"Basic";
break;
1778 case Special: OS <<
"Special";
break;
1779 case ICmpZero: OS <<
"ICmpZero";
break;
1781 OS <<
"Address of ";
1785 OS << *AccessTy.MemTy;
1788 OS <<
" in addrspace(" << AccessTy.AddrSpace <<
')';
1791 OS <<
", Offsets={";
1792 bool NeedComma =
false;
1793 for (
const LSRFixup &Fixup : Fixups) {
1794 if (NeedComma) OS <<
',';
1800 if (AllFixupsOutsideLoop)
1801 OS <<
", all-fixups-outside-loop";
1803 if (AllFixupsUnconditional)
1804 OS <<
", all-fixups-unconditional";
1813 LSRUse::KindType Kind, MemAccessTy AccessTy,
1815 bool HasBaseReg, int64_t Scale,
1818 case LSRUse::Address: {
1819 int64_t FixedOffset =
1820 BaseOffset.isScalable() ? 0 : BaseOffset.getFixedValue();
1821 int64_t ScalableOffset =
1822 BaseOffset.isScalable() ? BaseOffset.getKnownMinValue() : 0;
1823 return TTI.isLegalAddressingMode(AccessTy.MemTy, BaseGV, FixedOffset,
1824 HasBaseReg, Scale, AccessTy.AddrSpace,
1825 Fixup, ScalableOffset);
1827 case LSRUse::ICmpZero:
1834 if (Scale != 0 && HasBaseReg && BaseOffset.isNonZero())
1839 if (Scale != 0 && Scale != -1)
1844 if (BaseOffset.isNonZero()) {
1847 if (BaseOffset.isScalable())
1857 BaseOffset = BaseOffset.getFixed(-(
uint64_t)BaseOffset.getFixedValue());
1858 return TTI.isLegalICmpImmediate(BaseOffset.getFixedValue());
1866 return !BaseGV && Scale == 0 && BaseOffset.isZero();
1868 case LSRUse::Special:
1870 return !BaseGV && (Scale == 0 || Scale == -1) && BaseOffset.isZero();
1877 Immediate MinOffset, Immediate MaxOffset,
1878 LSRUse::KindType Kind, MemAccessTy AccessTy,
1880 bool HasBaseReg, int64_t Scale) {
1881 if (BaseOffset.isNonZero() &&
1882 (BaseOffset.isScalable() != MinOffset.isScalable() ||
1883 BaseOffset.isScalable() != MaxOffset.isScalable()))
1886 int64_t
Base = BaseOffset.getKnownMinValue();
1887 int64_t Min = MinOffset.getKnownMinValue();
1888 int64_t Max = MaxOffset.getKnownMinValue();
1891 MinOffset = Immediate::get((
uint64_t)
Base + Min, MinOffset.isScalable());
1894 MaxOffset = Immediate::get((
uint64_t)
Base + Max, MaxOffset.isScalable());
1897 HasBaseReg, Scale) &&
1903 Immediate MinOffset, Immediate MaxOffset,
1904 LSRUse::KindType Kind, MemAccessTy AccessTy,
1905 const Formula &
F,
const Loop &L) {
1913 assert((
F.isCanonical(L) ||
F.Scale != 0));
1915 F.BaseGV,
F.BaseOffset,
F.HasBaseReg,
F.Scale);
1920 Immediate MaxOffset, LSRUse::KindType Kind,
1922 Immediate BaseOffset,
bool HasBaseReg, int64_t Scale) {
1925 BaseOffset, HasBaseReg, Scale) ||
1930 BaseGV, BaseOffset,
true, 0));
1934 Immediate MaxOffset, LSRUse::KindType Kind,
1935 MemAccessTy AccessTy,
const Formula &
F) {
1936 return isLegalUse(
TTI, MinOffset, MaxOffset, Kind, AccessTy,
F.BaseGV,
1937 F.BaseOffset,
F.HasBaseReg,
F.Scale);
1943 return TTI.isLegalAddScalableImmediate(
Offset.getKnownMinValue());
1945 return TTI.isLegalAddImmediate(
Offset.getFixedValue());
1949 const LSRUse &LU,
const Formula &
F) {
1951 if (LU.Kind == LSRUse::Address &&
TTI.LSRWithInstrQueries()) {
1952 for (
const LSRFixup &Fixup : LU.Fixups)
1954 (
F.BaseOffset + Fixup.Offset),
F.HasBaseReg,
1955 F.Scale, Fixup.UserInst))
1961 LU.AccessTy,
F.BaseGV,
F.BaseOffset,
F.HasBaseReg,
1966 const LSRUse &LU,
const Formula &
F,
1975 return F.Scale != 1;
1978 case LSRUse::Address: {
1980 int64_t ScalableMin = 0, ScalableMax = 0, FixedMin = 0, FixedMax = 0;
1981 if (
F.BaseOffset.isScalable()) {
1982 ScalableMin = (
F.BaseOffset + LU.MinOffset).getKnownMinValue();
1983 ScalableMax = (
F.BaseOffset + LU.MaxOffset).getKnownMinValue();
1985 FixedMin = (
F.BaseOffset + LU.MinOffset).getFixedValue();
1986 FixedMax = (
F.BaseOffset + LU.MaxOffset).getFixedValue();
1990 F.HasBaseReg,
F.Scale, LU.AccessTy.AddrSpace);
1993 F.HasBaseReg,
F.Scale, LU.AccessTy.AddrSpace);
1996 "Legal addressing mode has an illegal cost!");
1997 return std::max(ScaleCostMinOffset, ScaleCostMaxOffset);
1999 case LSRUse::ICmpZero:
2001 case LSRUse::Special:
2012 LSRUse::KindType Kind, MemAccessTy AccessTy,
2016 if (BaseOffset.isZero() && !BaseGV)
2021 int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1;
2025 if (!HasBaseReg && Scale == 1) {
2035 if (HasBaseReg && BaseOffset.isNonZero() && Kind != LSRUse::ICmpZero &&
2037 Opts.lsr_drop_scaled_reg_for_vscale)
2047 Immediate MaxOffset, LSRUse::KindType Kind,
2048 MemAccessTy AccessTy,
const SCEV *S,
2051 if (S->
isZero())
return true;
2064 if (BaseOffset.isZero() && !BaseGV)
2067 if (BaseOffset.isScalable())
2072 int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1;
2075 BaseOffset, HasBaseReg, Scale);
2092 const SCEV *IncExpr;
2094 IVInc(Instruction *U,
Value *O,
const SCEV *
E)
2095 : UserInst(
U), IVOperand(
O), IncExpr(
E) {}
2102 const SCEV *ExprBase =
nullptr;
2104 IVChain() =
default;
2105 IVChain(
const IVInc &Head,
const SCEV *
Base)
2106 : Incs(1, Head), ExprBase(
Base) {}
2111 const_iterator
begin()
const {
2113 return std::next(Incs.
begin());
2115 const_iterator
end()
const {
2120 bool hasIncs()
const {
return Incs.
size() >= 2; }
2129 bool isProfitableIncrement(
const SCEV *OperExpr,
2130 const SCEV *IncExpr,
2138 SmallPtrSet<Instruction*, 4> FarUsers;
2139 SmallPtrSet<Instruction*, 4> NearUsers;
2144 const ScalarOptions &Opts;
2146 ScalarEvolution &SE;
2149 AssumptionCache &AC;
2150 TargetLibraryInfo &
TLI;
2151 const TargetTransformInfo &
TTI;
2153 MemorySSAUpdater *MSSAU;
2157 bool HardwareLoopProfitable =
false;
2158 bool ShouldPreserveLCSSA =
false;
2172 SetVector<int64_t, SmallVector<int64_t, 8>, SmallSet<int64_t, 8>> Factors;
2179 SmallSetVector<Type *, 4> Types;
2185 RegUseTracker RegUses;
2190 static const unsigned MaxChains = 8;
2196 SmallPtrSet<Use*, MaxChains> IVIncSet;
2199 SmallVector<llvm::WeakVH, 2> ScalarEvolutionIVs;
2205 SmallSetVector<Instruction *, 4> InsertedNonLCSSAInsts;
2207 void OptimizeShadowIV();
2208 bool FindIVUserForCond(Instruction *
Cond, IVStrideUse *&CondUse);
2210 ICmpInst *OptimizeLoopTermCondToEquality(ICmpInst *
Cond,
2211 IVStrideUse *&CondUse,
2212 BasicBlock *ExitingBlock);
2213 void OptimizeLoopTermCond();
2215 void ChainInstruction(Instruction *UserInst, Instruction *IVOper,
2216 SmallVectorImpl<ChainUsers> &ChainUsersVec);
2217 void FinalizeChain(IVChain &Chain);
2218 void CollectChains();
2219 void GenerateIVChain(
const IVChain &Chain,
2220 SmallVectorImpl<WeakTrackingVH> &DeadInsts);
2222 void CollectInterestingTypesAndFactors();
2223 void CollectFixupsAndInitialFormulae();
2226 using UseMapTy = DenseMap<LSRUse::SCEVUseKindPair, size_t>;
2229 bool reconcileNewOffset(LSRUse &LU, Immediate NewOffset,
bool HasBaseReg,
2230 LSRUse::KindType Kind, MemAccessTy AccessTy);
2232 std::pair<size_t, Immediate> getUse(
const SCEV *&Expr, LSRUse::KindType Kind,
2233 MemAccessTy AccessTy);
2235 void DeleteUse(LSRUse &LU,
size_t LUIdx);
2237 LSRUse *FindUseWithSimilarFormula(
const Formula &
F,
const LSRUse &OrigLU);
2239 void InsertInitialFormula(
const SCEV *S, LSRUse &LU,
size_t LUIdx);
2240 void InsertSupplementalFormula(
const SCEV *S, LSRUse &LU,
size_t LUIdx);
2241 void CountRegisters(
const Formula &
F,
size_t LUIdx);
2242 bool InsertFormula(LSRUse &LU,
unsigned LUIdx,
const Formula &
F);
2243 bool IsFixupExecutedEachIncrement(
const LSRFixup &LF)
const;
2245 void CollectLoopInvariantFixupsAndFormulae();
2247 void GenerateReassociations(LSRUse &LU,
unsigned LUIdx, Formula
Base,
2248 unsigned Depth = 0);
2250 void GenerateReassociationsImpl(LSRUse &LU,
unsigned LUIdx,
2252 size_t Idx,
bool IsScaledReg =
false);
2253 void GenerateCombinations(LSRUse &LU,
unsigned LUIdx, Formula
Base);
2254 void GenerateSymbolicOffsetsImpl(LSRUse &LU,
unsigned LUIdx,
2255 const Formula &
Base,
size_t Idx,
2256 bool IsScaledReg =
false);
2257 void GenerateSymbolicOffsets(LSRUse &LU,
unsigned LUIdx, Formula
Base);
2258 void GenerateConstantOffsetsImpl(LSRUse &LU,
unsigned LUIdx,
2259 const Formula &
Base,
2260 const SmallVectorImpl<Immediate> &Worklist,
2261 size_t Idx,
bool IsScaledReg =
false);
2262 void GenerateConstantOffsets(LSRUse &LU,
unsigned LUIdx, Formula
Base);
2263 void GenerateICmpZeroScales(LSRUse &LU,
unsigned LUIdx, Formula
Base);
2264 void GenerateScales(LSRUse &LU,
unsigned LUIdx, Formula
Base);
2265 void GenerateTruncates(LSRUse &LU,
unsigned LUIdx, Formula
Base);
2266 void GenerateCrossUseConstantOffsets();
2267 void GenerateAllReuseFormulae();
2269 void FilterOutUndesirableDedicatedRegisters();
2271 size_t EstimateSearchSpaceComplexity()
const;
2272 void NarrowSearchSpaceByDetectingSupersets();
2273 void NarrowSearchSpaceByCollapsingUnrolledCode();
2274 void NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
2275 void NarrowSearchSpaceByFilterFormulaWithSameScaledReg();
2276 void NarrowSearchSpaceByFilterPostInc();
2277 void NarrowSearchSpaceByMergingUsesOutsideLoop();
2278 void NarrowSearchSpaceByDeletingCostlyFormulas();
2279 void NarrowSearchSpaceByPickingWinnerRegs();
2280 void NarrowSearchSpaceUsingHeuristics();
2282 void SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
2284 SmallVectorImpl<const Formula *> &Workspace,
2285 const Cost &CurCost,
2286 const SmallPtrSet<const SCEV *, 16> &CurRegs,
2287 DenseSet<const SCEV *> &VisitedRegs)
const;
2288 void Solve(SmallVectorImpl<const Formula *> &Solution)
const;
2292 const SmallVectorImpl<Instruction *> &Inputs)
const;
2295 const LSRUse &LU)
const;
2297 Value *Expand(
const LSRUse &LU,
const LSRFixup &LF,
const Formula &
F,
2299 SmallVectorImpl<WeakTrackingVH> &DeadInsts)
const;
2300 void RewriteForPHI(PHINode *PN,
const LSRUse &LU,
const LSRFixup &LF,
2302 SmallVectorImpl<WeakTrackingVH> &DeadInsts);
2303 void Rewrite(
const LSRUse &LU,
const LSRFixup &LF,
const Formula &
F,
2304 SmallVectorImpl<WeakTrackingVH> &DeadInsts);
2305 void ImplementSolution(
const SmallVectorImpl<const Formula *> &Solution);
2312 LSRInstance(
const ScalarOptions &Opts,
Loop *L, IVUsers &IU,
2313 ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI,
2314 const TargetTransformInfo &
TTI, AssumptionCache &AC,
2315 TargetLibraryInfo &
TLI, MemorySSAUpdater *MSSAU,
2316 bool PreserveLCSSA);
2318 bool getChanged()
const {
return Changed; }
2319 const SmallVectorImpl<WeakVH> &getScalarEvolutionIVs()
const {
2320 return ScalarEvolutionIVs;
2323 void print_factors_and_types(raw_ostream &OS)
const;
2324 void print_fixups(raw_ostream &OS)
const;
2325 void print_uses(raw_ostream &OS)
const;
2326 void print(raw_ostream &OS)
const;
2334void LSRInstance::OptimizeShadowIV() {
2344 Type *DestTy =
nullptr;
2345 bool IsSigned =
false;
2361 DestTy = UCast->getDestTy();
2365 DestTy = SCast->getDestTy();
2367 if (!DestTy)
continue;
2387 if (Mantissa == -1)
continue;
2391 unsigned Entry, Latch;
2401 if (!Init)
continue;
2402 Constant *NewInit = ConstantFP::get(DestTy, IsSigned ?
2406 BinaryOperator *Incr =
2408 if (!Incr)
continue;
2409 if (Incr->
getOpcode() != Instruction::Add
2410 && Incr->
getOpcode() != Instruction::Sub)
2414 ConstantInt *
C =
nullptr;
2426 if (!
C->getValue().isStrictlyPositive())
2434 Constant *CFP = ConstantFP::get(DestTy,
C->getZExtValue());
2436 Incr->
getOpcode() == Instruction::Add ? Instruction::FAdd
2437 : Instruction::FSub,
2454bool LSRInstance::FindIVUserForCond(Instruction *
Cond, IVStrideUse *&CondUse) {
2455 for (IVStrideUse &U : IU)
2456 if (
U.getUser() ==
Cond) {
2468ICmpInst *LSRInstance::OptimizeLoopTermCondToEquality(
2469 ICmpInst *
Cond, IVStrideUse *&CondUse, BasicBlock *ExitingBlock) {
2470 if (
Cond->isEquality() || ExitingBlock !=
L->getLoopLatch())
2474 if (!
IV || !
IV->getType()->isIntegerTy() ||
IV->getParent() !=
L->getHeader())
2482 if (!Step || Step->
isZero())
2485 const SCEV *ExitCount = SE.
getExitCount(L, ExitingBlock);
2493 const APInt &StepValue = Step->getAPInt();
2494 unsigned RecurrencePeriodLog2 =
2499 const auto *ExitValue =
2502 *
Cond, ExitValue->getAPInt() + StepValue))
2505 LLVM_DEBUG(
dbgs() <<
" Rewriting loop exit to compare " << *
IV <<
" against "
2506 << *ExitValue <<
'\n');
2509 bool TrueContinues =
L->contains(TermBr->getSuccessor(0));
2510 assert(TrueContinues !=
L->contains(TermBr->getSuccessor(1)) &&
2511 "Expected exactly one in-loop successor");
2513 auto Pred = TrueContinues ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
2514 auto *NewCond =
new ICmpInst(TermBr->getIterator(),
Pred,
IV,
2515 ExitValue->getValue(),
"lsr.exitcond");
2516 NewCond->setDebugLoc(
Cond->getDebugLoc());
2517 TermBr->setCondition(NewCond);
2519 if (
Cond->use_empty()) {
2521 Cond->eraseFromParent();
2523 CondUse = &IU.AddUser(NewCond,
IV);
2578Instruction *LSRInstance::OptimizeMax(ICmpInst *
Cond, IVStrideUse *&CondUse) {
2593 const SCEV *IterationCount = SE.
getAddExpr(One, BackedgeTakenCount);
2594 if (IterationCount != SE.
getSCEV(Sel))
return Cond;
2600 const SCEVNAryExpr *
Max =
nullptr;
2602 Pred = ICmpInst::ICMP_SLE;
2605 Pred = ICmpInst::ICMP_SLT;
2608 Pred = ICmpInst::ICMP_ULT;
2617 if (
Max->getNumOperands() != 2)
2620 const SCEV *MaxLHS =
Max->getOperand(0);
2621 const SCEV *MaxRHS =
Max->getOperand(1);
2626 (ICmpInst::isTrueWhenEqual(
Pred) ? !MaxLHS->
isZero() : (MaxLHS != One)))
2637 "Loop condition operand is an addrec in a different loop!");
2641 Value *NewRHS =
nullptr;
2642 if (ICmpInst::isTrueWhenEqual(
Pred)) {
2646 if (BO1->isOne() && SE.
getSCEV(BO->getOperand(0)) == MaxRHS)
2647 NewRHS = BO->getOperand(0);
2650 if (BO1->isOne() && SE.
getSCEV(BO->getOperand(0)) == MaxRHS)
2651 NewRHS = BO->getOperand(0);
2659 NewRHS = SU->getValue();
2671 ICmpInst *NewCond =
new ICmpInst(
Cond->getIterator(),
Pred,
2672 Cond->getOperand(0), NewRHS,
"scmp");
2676 Cond->replaceAllUsesWith(NewCond);
2679 Cond->eraseFromParent();
2681 if (
Cmp->use_empty()) {
2683 Cmp->eraseFromParent();
2690LSRInstance::OptimizeLoopTermCond() {
2691 SmallPtrSet<Instruction *, 4> PostIncs;
2706 SmallVector<BasicBlock*, 8> ExitingBlocks;
2707 L->getExitingBlocks(ExitingBlocks);
2715 for (BasicBlock *ExitingBlock : ExitingBlocks) {
2737 IVStrideUse *CondUse =
nullptr;
2738 if (!FindIVUserForCond(
Cond, CondUse))
2748 Cond = OptimizeMax(Cmp, CondUse);
2753 if (!DT.
dominates(ExitingBlock, LatchBlock))
2757 Cond = OptimizeLoopTermCondToEquality(Cmp, CondUse, ExitingBlock);
2761 if (LatchBlock != ExitingBlock)
2762 for (
const IVStrideUse &UI : IU)
2765 if (&UI != CondUse &&
2769 const SCEV *
A = IU.getStride(*CondUse, L);
2770 const SCEV *
B = IU.getStride(UI, L);
2771 if (!
A || !
B)
continue;
2780 if (
const SCEVConstant *
D =
2782 const ConstantInt *
C =
D->getValue();
2784 if (
C->isOne() ||
C->isMinusOne())
2785 goto decline_post_inc;
2787 if (
C->getValue().getSignificantBits() >= 64 ||
2788 C->getValue().isMinSignedValue())
2789 goto decline_post_inc;
2792 MemAccessTy AccessTy =
2794 int64_t Scale =
C->getSExtValue();
2798 AccessTy.AddrSpace))
2799 goto decline_post_inc;
2804 AccessTy.AddrSpace))
2805 goto decline_post_inc;
2810 LLVM_DEBUG(
dbgs() <<
" Change loop exiting icmp to use postinc iv: "
2818 if (
Cond->hasOneUse()) {
2824 Cond->setName(
L->getHeader()->getName() +
".termcond");
2846 IVIncInsertPos =
L->getLoopLatch()->getTerminator();
2847 for (Instruction *Inst : PostIncs)
2853bool LSRInstance::reconcileNewOffset(LSRUse &LU, Immediate NewOffset,
2854 bool HasBaseReg, LSRUse::KindType Kind,
2855 MemAccessTy AccessTy) {
2856 Immediate NewMinOffset = LU.MinOffset;
2857 Immediate NewMaxOffset = LU.MaxOffset;
2858 MemAccessTy NewAccessTy = AccessTy;
2863 if (LU.Kind != Kind)
2869 if (Kind == LSRUse::Address) {
2870 if (AccessTy.MemTy != LU.AccessTy.MemTy) {
2871 NewAccessTy = MemAccessTy::getUnknown(AccessTy.MemTy->
getContext(),
2872 AccessTy.AddrSpace);
2877 if (Immediate::isKnownLT(NewOffset, LU.MinOffset)) {
2879 LU.MaxOffset - NewOffset, HasBaseReg))
2881 NewMinOffset = NewOffset;
2882 }
else if (Immediate::isKnownGT(NewOffset, LU.MaxOffset)) {
2884 NewOffset - LU.MinOffset, HasBaseReg))
2886 NewMaxOffset = NewOffset;
2892 if (NewAccessTy.MemTy && NewAccessTy.MemTy->
isVoidTy() &&
2893 (NewMinOffset.isScalable() || NewMaxOffset.isScalable()))
2897 LU.MinOffset = NewMinOffset;
2898 LU.MaxOffset = NewMaxOffset;
2899 LU.AccessTy = NewAccessTy;
2906std::pair<size_t, Immediate> LSRInstance::getUse(
const SCEV *&Expr,
2907 LSRUse::KindType Kind,
2908 MemAccessTy AccessTy) {
2909 const SCEV *
Copy = Expr;
2912 Opts, ExprUse, SE, AccessTy.MemTy && AccessTy.MemTy->
isScalableTy());
2919 Offset = Immediate::getFixed(0);
2922 std::pair<UseMapTy::iterator, bool>
P =
2923 UseMap.
try_emplace(LSRUse::SCEVUseKindPair(Expr, Kind));
2926 size_t LUIdx =
P.first->second;
2927 LSRUse &LU =
Uses[LUIdx];
2928 if (reconcileNewOffset(LU,
Offset,
true, Kind, AccessTy))
2930 return std::make_pair(LUIdx,
Offset);
2934 size_t LUIdx =
Uses.size();
2935 P.first->second = LUIdx;
2936 Uses.push_back(LSRUse(Kind, AccessTy));
2937 LSRUse &LU =
Uses[LUIdx];
2941 return std::make_pair(LUIdx,
Offset);
2945void LSRInstance::DeleteUse(LSRUse &LU,
size_t LUIdx) {
2946 if (&LU != &
Uses.back())
2951 RegUses.swapAndDropUse(LUIdx,
Uses.size());
2957LSRInstance::FindUseWithSimilarFormula(
const Formula &OrigF,
2958 const LSRUse &OrigLU) {
2960 for (LSRUse &LU :
Uses) {
2966 if (&LU != &OrigLU && LU.Kind != LSRUse::ICmpZero &&
2967 LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy &&
2968 LU.HasFormulaWithSameRegs(OrigF)) {
2970 for (
const Formula &
F : LU.Formulae) {
2973 if (
F.BaseRegs == OrigF.BaseRegs &&
2974 F.ScaledReg == OrigF.ScaledReg &&
2975 F.BaseGV == OrigF.BaseGV &&
2976 F.Scale == OrigF.Scale &&
2977 F.UnfoldedOffset == OrigF.UnfoldedOffset) {
2978 if (
F.BaseOffset.isZero())
2993void LSRInstance::CollectInterestingTypesAndFactors() {
2994 SmallSetVector<const SCEV *, 4> Strides;
2998 for (
const IVStrideUse &U : IU) {
2999 const SCEV *Expr = IU.getExpr(U);
3017 }
while (!Worklist.
empty());
3021 for (SmallSetVector<const SCEV *, 4>::const_iterator
3023 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
3024 std::next(
I); NewStrideIter !=
E; ++NewStrideIter) {
3025 const SCEV *OldStride = *
I;
3026 const SCEV *NewStride = *NewStrideIter;
3036 if (
const SCEVConstant *Factor =
3039 if (Factor->getAPInt().getSignificantBits() <= 64 && !Factor->isZero())
3040 Factors.insert(Factor->getAPInt().getSExtValue());
3041 }
else if (
const SCEVConstant *Factor =
3045 if (Factor->getAPInt().getSignificantBits() <= 64 && !Factor->isZero())
3046 Factors.insert(Factor->getAPInt().getSExtValue());
3052 if (Types.size() == 1)
3064 for(; OI != OE; ++OI) {
3083 return Trunc->getOperand(0);
3116 if (SubExpr->getSCEVType() ==
scAddExpr)
3119 if (SubExpr->getSCEVType() !=
scMulExpr)
3135bool IVChain::isProfitableIncrement(
const SCEV *OperExpr,
3136 const SCEV *IncExpr,
3137 ScalarEvolution &SE) {
3146 SmallPtrSet<const SCEV*, 8> Processed;
3164 if (!Chain.hasIncs())
3167 if (!
Users.empty()) {
3168 LLVM_DEBUG(
dbgs() <<
"Chain: " << *Chain.Incs[0].UserInst <<
" users:\n";
3170 :
Users) {
dbgs() <<
" " << *Inst <<
"\n"; });
3173 assert(!Chain.Incs.empty() &&
"empty IV chains are not allowed");
3182 && SE.
getSCEV(Chain.tailUserInst()) == Chain.Incs[0].IncExpr) {
3185 const SCEV *LastIncExpr =
nullptr;
3186 unsigned NumConstIncrements = 0;
3187 unsigned NumVarIncrements = 0;
3188 unsigned NumReusedIncrements = 0;
3190 if (
TTI.isProfitableLSRChainElement(Chain.Incs[0].UserInst))
3193 for (
const IVInc &Inc : Chain) {
3194 if (
TTI.isProfitableLSRChainElement(Inc.UserInst))
3196 if (Inc.IncExpr->isZero())
3202 ++NumConstIncrements;
3206 if (Inc.IncExpr == LastIncExpr)
3207 ++NumReusedIncrements;
3211 LastIncExpr = Inc.IncExpr;
3216 if (NumConstIncrements > 1)
3223 cost += NumVarIncrements;
3227 cost -= NumReusedIncrements;
3229 LLVM_DEBUG(
dbgs() <<
"Chain: " << *Chain.Incs[0].UserInst <<
" Cost: " << cost
3236void LSRInstance::ChainInstruction(Instruction *UserInst, Instruction *IVOper,
3237 SmallVectorImpl<ChainUsers> &ChainUsersVec) {
3241 const SCEV *
const OperExpr = SE.
getSCEV(NextIV);
3242 const SCEV *
const OperExprBase =
getExprBase(OperExpr);
3246 unsigned ChainIdx = 0, NChains = IVChainVec.size();
3247 const SCEV *LastIncExpr =
nullptr;
3248 for (; ChainIdx < NChains; ++ChainIdx) {
3249 IVChain &Chain = IVChainVec[ChainIdx];
3267 const SCEV *PrevExpr = SE.
getSCEV(PrevIV);
3268 const SCEV *IncExpr = SE.
getMinusSCEV(OperExpr, PrevExpr);
3274 Chain.isProfitableIncrement(OperExpr, IncExpr, SE)) {
3275 LastIncExpr = IncExpr;
3281 if (ChainIdx == NChains) {
3288 LastIncExpr = OperExpr;
3295 IVChainVec.push_back(IVChain(IVInc(UserInst, IVOper, LastIncExpr),
3297 ChainUsersVec.
resize(NChains);
3298 LLVM_DEBUG(
dbgs() <<
"IV Chain#" << ChainIdx <<
" Head: (" << *UserInst
3299 <<
") IV=" << *LastIncExpr <<
"\n");
3301 LLVM_DEBUG(
dbgs() <<
"IV Chain#" << ChainIdx <<
" Inc: (" << *UserInst
3302 <<
") IV+" << *LastIncExpr <<
"\n");
3304 IVChainVec[ChainIdx].add(IVInc(UserInst, IVOper, LastIncExpr));
3306 IVChain &Chain = IVChainVec[ChainIdx];
3308 SmallPtrSet<Instruction*,4> &NearUsers = ChainUsersVec[ChainIdx].NearUsers;
3310 if (!LastIncExpr->
isZero()) {
3311 ChainUsersVec[ChainIdx].FarUsers.insert_range(NearUsers);
3320 for (User *U : IVOper->
users()) {
3326 IVChain::const_iterator IncIter = Chain.Incs.begin();
3327 IVChain::const_iterator IncEnd = Chain.Incs.end();
3328 for( ; IncIter != IncEnd; ++IncIter) {
3329 if (IncIter->UserInst == OtherUse)
3332 if (IncIter != IncEnd)
3337 && IU.isIVUserOrOperand(OtherUse)) {
3340 NearUsers.
insert(OtherUse);
3345 ChainUsersVec[ChainIdx].FarUsers.
erase(UserInst);
3370void LSRInstance::CollectChains() {
3374 SmallVector<BasicBlock *,8> LatchPath;
3377 Rung->
getBlock() != LoopHeader; Rung = Rung->getIDom()) {
3383 for (BasicBlock *BB :
reverse(LatchPath)) {
3384 for (Instruction &
I : *BB) {
3390 if (IU.isEphemeral(&
I))
3400 for (
unsigned ChainIdx = 0, NChains = IVChainVec.size();
3401 ChainIdx < NChains; ++ChainIdx) {
3402 ChainUsersVec[ChainIdx].NearUsers.
erase(&
I);
3405 SmallPtrSet<Instruction*, 4> UniqueOperands;
3408 while (IVOpIter != IVOpEnd) {
3410 if (UniqueOperands.
insert(IVOpInst).second)
3411 ChainInstruction(&
I, IVOpInst, ChainUsersVec);
3412 IVOpIter =
findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE);
3417 for (PHINode &PN :
L->getHeader()->phis()) {
3424 ChainInstruction(&PN, IncV, ChainUsersVec);
3427 unsigned ChainIdx = 0;
3428 for (
unsigned UsersIdx = 0, NChains = IVChainVec.size();
3429 UsersIdx < NChains; ++UsersIdx) {
3432 ChainUsersVec[UsersIdx].FarUsers, SE,
TTI))
3435 if (ChainIdx != UsersIdx)
3436 IVChainVec[ChainIdx] = IVChainVec[UsersIdx];
3437 FinalizeChain(IVChainVec[ChainIdx]);
3440 IVChainVec.resize(ChainIdx);
3443void LSRInstance::FinalizeChain(IVChain &Chain) {
3444 assert(!Chain.Incs.empty() &&
"empty IV chains are not allowed");
3445 LLVM_DEBUG(
dbgs() <<
"Final Chain: " << *Chain.Incs[0].UserInst <<
"\n");
3447 for (
const IVInc &Inc : Chain) {
3449 auto UseI =
find(Inc.UserInst->operands(), Inc.IVOperand);
3450 assert(UseI != Inc.UserInst->op_end() &&
"cannot find IV operand");
3451 IVIncSet.insert(UseI);
3460 Immediate IncOffset = Immediate::getZero();
3469 C->getSignificantBits() > 64)
3471 IncOffset = Immediate::getScalable(
C->getSExtValue());
3479 nullptr, IncOffset,
false))
3487void LSRInstance::GenerateIVChain(
const IVChain &Chain,
3488 SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
3491 const IVInc &Head = Chain.Incs[0];
3496 Value *IVSrc =
nullptr;
3497 while (IVOpIter != IVOpEnd) {
3508 if (SE.
getSCEV(*IVOpIter) == Head.IncExpr
3509 || SE.
getSCEV(IVSrc) == Head.IncExpr) {
3512 IVOpIter =
findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE);
3514 if (IVOpIter == IVOpEnd) {
3516 LLVM_DEBUG(
dbgs() <<
"Concealed chain head: " << *Head.UserInst <<
"\n");
3519 assert(IVSrc &&
"Failed to find IV chain source");
3524 const SCEV *LeftOverExpr =
nullptr;
3525 const SCEV *Accum = SE.
getZero(IntTy);
3529 for (
const IVInc &Inc : Chain) {
3532 InsertPt =
L->getLoopLatch()->getTerminator();
3536 Value *IVOper = IVSrc;
3537 if (!Inc.IncExpr->isZero()) {
3542 LeftOverExpr = LeftOverExpr
3548 bool FoundBase =
false;
3549 for (
auto [MapScev, MapIVOper] :
reverse(Bases)) {
3550 const SCEV *Remainder = SE.
getMinusSCEV(Accum, MapScev);
3552 if (!Remainder->
isZero()) {
3555 const SCEV *IVOperExpr =
3566 if (!FoundBase && LeftOverExpr && !LeftOverExpr->
isZero()) {
3577 assert(IVTy == IVOper->
getType() &&
"inconsistent IV increment type");
3580 LeftOverExpr =
nullptr;
3584 if (IVTy != OperTy) {
3586 "cannot extend a chained IV");
3588 IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy,
"lsr.chain");
3590 Inc.UserInst->replaceUsesOfWith(Inc.IVOperand, IVOper);
3597 for (PHINode &Phi :
L->getHeader()->phis()) {
3601 Phi.getIncomingValueForBlock(
L->getLoopLatch()));
3604 Value *IVOper = IVSrc;
3606 if (IVTy != PostIncTy) {
3608 IRBuilder<> Builder(
L->getLoopLatch()->getTerminator());
3609 Builder.SetCurrentDebugLocation(PostIncV->
getDebugLoc());
3610 IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy,
"lsr.chain");
3612 Phi.replaceUsesOfWith(PostIncV, IVOper);
3618void LSRInstance::CollectFixupsAndInitialFormulae() {
3619 CondBrInst *ExitBranch =
nullptr;
3623 SmallPtrSet<const SCEV *, 16> Regs;
3624 DenseSet<const SCEV *> VisitedRegs;
3625 DenseSet<size_t> VisitedLSRUse;
3627 for (
const IVStrideUse &U : IU) {
3632 assert(UseI != UserInst->
op_end() &&
"cannot find IV operand");
3633 if (IVIncSet.count(UseI)) {
3634 LLVM_DEBUG(
dbgs() <<
"Use is in profitable chain: " << **UseI <<
'\n');
3638 LSRUse::KindType
Kind = LSRUse::Basic;
3639 MemAccessTy AccessTy;
3641 Kind = LSRUse::Address;
3645 const SCEV *S = IU.getExpr(U);
3661 if (CI->isEquality()) {
3664 Value *
NV = CI->getOperand(1);
3665 if (NV ==
U.getOperandValToReplace()) {
3666 CI->setOperand(1, CI->getOperand(0));
3667 CI->setOperand(0, NV);
3668 NV = CI->getOperand(1);
3675 (!
NV->getType()->isPointerTy() ||
3682 Kind = LSRUse::ICmpZero;
3684 }
else if (
L->isLoopInvariant(NV) &&
3687 !
NV->getType()->isPointerTy()) {
3698 Kind = LSRUse::ICmpZero;
3705 for (
size_t i = 0, e = Factors.size(); i != e; ++i)
3706 if (Factors[i] != -1)
3707 Factors.insert(-(
uint64_t)Factors[i]);
3713 std::pair<size_t, Immediate>
P = getUse(S, Kind, AccessTy);
3714 size_t LUIdx =
P.first;
3716 LSRUse &LU =
Uses[LUIdx];
3719 LSRFixup &LF = LU.getNewFixup();
3720 LF.UserInst = UserInst;
3721 LF.OperandValToReplace =
U.getOperandValToReplace();
3722 LF.PostIncLoops = TmpPostIncLoops;
3724 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
3725 LU.AllFixupsUnconditional &= IsFixupExecutedEachIncrement(LF);
3728 if (!VisitedLSRUse.
count(LUIdx) && !LF.isUseFullyOutsideLoop(L)) {
3730 F.initialMatch(S, L, SE);
3731 BaselineCost.RateFormula(
F, Regs, VisitedRegs, LU,
3732 HardwareLoopProfitable);
3733 VisitedLSRUse.
insert(LUIdx);
3737 if (LU.Formulae.empty()) {
3738 InsertInitialFormula(S, LU, LUIdx);
3739 CountRegisters(LU.Formulae.back(), LUIdx);
3748void LSRInstance::InsertInitialFormula(
const SCEV *S, LSRUse &LU,
3752 LU.RigidFormula =
true;
3755 F.initialMatch(S, L, SE);
3756 bool Inserted = InsertFormula(LU, LUIdx,
F);
3757 assert(Inserted &&
"Initial formula already exists!"); (void)Inserted;
3763LSRInstance::InsertSupplementalFormula(
const SCEV *S,
3764 LSRUse &LU,
size_t LUIdx) {
3766 F.BaseRegs.push_back(S);
3767 F.HasBaseReg =
true;
3768 bool Inserted = InsertFormula(LU, LUIdx,
F);
3769 assert(Inserted &&
"Supplemental formula already exists!"); (void)Inserted;
3773void LSRInstance::CountRegisters(
const Formula &
F,
size_t LUIdx) {
3775 RegUses.countRegister(
F.ScaledReg, LUIdx);
3776 for (
const SCEV *BaseReg :
F.BaseRegs)
3777 RegUses.countRegister(BaseReg, LUIdx);
3782bool LSRInstance::InsertFormula(LSRUse &LU,
unsigned LUIdx,
const Formula &
F) {
3785 "Formula is illegal");
3787 if (!LU.InsertFormula(
F, *L))
3790 CountRegisters(
F, LUIdx);
3796bool LSRInstance::IsFixupExecutedEachIncrement(
const LSRFixup &LF)
const {
3808LSRInstance::CollectLoopInvariantFixupsAndFormulae() {
3810 SmallPtrSet<const SCEV *, 32> Visited;
3817 while (!Worklist.
empty()) {
3821 if (!Visited.
insert(S).second)
3832 const Value *
V = US->getValue();
3835 if (
L->contains(Inst))
continue;
3839 for (
const Use &U :
V->uses()) {
3849 if (UserInst->
getParent()->getParent() !=
L->getHeader()->getParent())
3871 bool HasIncompatibleEHPTerminatedBlock =
false;
3873 for (
unsigned int I = 0;
I < PhiNode->getNumIncomingValues();
I++) {
3874 if (PhiNode->getIncomingValue(
I) == ExpectedValue) {
3875 if (PhiNode->getIncomingBlock(
I)->getTerminator()->isEHPad()) {
3876 HasIncompatibleEHPTerminatedBlock =
true;
3881 if (HasIncompatibleEHPTerminatedBlock) {
3904 unsigned OtherIdx = !
U.getOperandNo();
3905 Value *OtherOp = ICI->getOperand(OtherIdx);
3915 std::pair<size_t, Immediate>
P =
3916 getUse(S, LSRUse::Basic, MemAccessTy());
3917 size_t LUIdx =
P.first;
3919 LSRUse &LU =
Uses[LUIdx];
3920 LSRFixup &LF = LU.getNewFixup();
3921 LF.UserInst =
const_cast<Instruction *
>(UserInst);
3922 LF.OperandValToReplace =
U;
3924 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
3925 LU.AllFixupsUnconditional &= IsFixupExecutedEachIncrement(LF);
3926 InsertSupplementalFormula(US, LU, LUIdx);
3927 CountRegisters(LU.Formulae.back(),
Uses.size() - 1);
3943 unsigned Depth = 0) {
3950 for (
const SCEV *S :
Add->operands()) {
3957 const SCEV *Start, *Step;
3962 if (Start->isZero())
3971 Remainder =
nullptr;
3973 if (Remainder != Start) {
3995 LSRUse &LU,
const SCEV *S,
const Loop *L,
3997 if (LU.Kind != LSRUse::Address ||
3998 !LU.AccessTy.getType()->isIntOrIntVectorTy())
4004 if (
TTI.isIndexedLoadLegal(
TTI.MIM_PostInc, S->
getType()) ||
4013void LSRInstance::GenerateReassociationsImpl(LSRUse &LU,
unsigned LUIdx,
4014 const Formula &
Base,
4015 unsigned Depth,
size_t Idx,
4025 const SCEV *Remainder =
CollectSubexprs(BaseReg,
nullptr, AddOps, L, SE);
4029 if (AddOps.
size() == 1)
4043 LU.AccessTy, *J,
Base.getNumRegs() > 1))
4048 InnerAddOps.append(std::next(J), std::as_const(AddOps).
end());
4052 if (InnerAddOps.size() == 1 &&
4054 LU.AccessTy, InnerAddOps[0],
Base.getNumRegs() > 1))
4057 const SCEV *InnerSum = SE.
getAddExpr(InnerAddOps);
4062 if (
F.UnfoldedOffset.isNonZero() &&
F.UnfoldedOffset.isScalable())
4071 Immediate::getFixed((
uint64_t)
F.UnfoldedOffset.getFixedValue() +
4074 F.ScaledReg =
nullptr;
4077 F.BaseRegs.erase(
F.BaseRegs.begin() + Idx);
4078 }
else if (IsScaledReg)
4079 F.ScaledReg = InnerSum;
4081 F.BaseRegs[
Idx] = InnerSum;
4089 Immediate::getFixed((
uint64_t)
F.UnfoldedOffset.getFixedValue() +
4092 F.BaseRegs.push_back(*J);
4097 if (InsertFormula(LU, LUIdx,
F))
4104 GenerateReassociations(LU, LUIdx, LU.Formulae.back(),
4110void LSRInstance::GenerateReassociations(LSRUse &LU,
unsigned LUIdx,
4112 assert(
Base.isCanonical(*L) &&
"Input must be in the canonical form");
4117 for (
size_t i = 0, e =
Base.BaseRegs.size(); i != e; ++i)
4118 GenerateReassociationsImpl(LU, LUIdx,
Base,
Depth, i);
4120 if (
Base.Scale == 1)
4121 GenerateReassociationsImpl(LU, LUIdx,
Base,
Depth,
4127void LSRInstance::GenerateCombinations(LSRUse &LU,
unsigned LUIdx,
4130 if (
Base.BaseRegs.size() + (
Base.Scale == 1) +
4131 (
Base.UnfoldedOffset.isNonZero()) <=
4139 Formula NewBase =
Base;
4140 NewBase.BaseRegs.clear();
4141 Type *CombinedIntegerType =
nullptr;
4142 for (
const SCEV *BaseReg :
Base.BaseRegs) {
4145 if (!CombinedIntegerType)
4147 Ops.push_back(BaseReg);
4150 NewBase.BaseRegs.push_back(BaseReg);
4154 if (
Ops.size() == 0)
4159 auto GenerateFormula = [&](
const SCEV *Sum) {
4160 Formula
F = NewBase;
4168 F.BaseRegs.push_back(Sum);
4170 (void)InsertFormula(LU, LUIdx,
F);
4174 if (
Ops.size() > 1) {
4181 if (NewBase.UnfoldedOffset.isNonZero() && NewBase.UnfoldedOffset.isFixed()) {
4182 assert(CombinedIntegerType &&
"Missing a type for the unfolded offset");
4184 NewBase.UnfoldedOffset.getFixedValue(),
true));
4185 NewBase.UnfoldedOffset = Immediate::getFixed(0);
4191void LSRInstance::GenerateSymbolicOffsetsImpl(LSRUse &LU,
unsigned LUIdx,
4192 const Formula &
Base,
size_t Idx,
4196 if (
G->isZero() || !GV)
4200 if (!
isLegalUse(
TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy,
F))
4205 F.BaseRegs[
Idx] =
G;
4206 (void)InsertFormula(LU, LUIdx,
F);
4210void LSRInstance::GenerateSymbolicOffsets(LSRUse &LU,
unsigned LUIdx,
4213 if (
Base.BaseGV)
return;
4215 for (
size_t i = 0, e =
Base.BaseRegs.size(); i != e; ++i)
4216 GenerateSymbolicOffsetsImpl(LU, LUIdx,
Base, i);
4217 if (
Base.Scale == 1)
4218 GenerateSymbolicOffsetsImpl(LU, LUIdx,
Base, -1,
4223void LSRInstance::GenerateConstantOffsetsImpl(
4224 LSRUse &LU,
unsigned LUIdx,
const Formula &
Base,
4225 const SmallVectorImpl<Immediate> &Worklist,
size_t Idx,
bool IsScaledReg) {
4227 auto GenerateOffset = [&](
const SCEV *
G, Immediate
Offset) {
4229 if (!
Base.BaseOffset.isCompatibleImmediate(
Offset))
4231 F.BaseOffset =
Base.BaseOffset.subUnsigned(
Offset);
4233 if (
isLegalUse(
TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy,
F)) {
4235 const SCEV *NewOffset =
Offset.getSCEV(SE,
G->getType());
4241 F.ScaledReg =
nullptr;
4243 F.deleteBaseReg(
F.BaseRegs[Idx]);
4245 }
else if (IsScaledReg)
4248 F.BaseRegs[
Idx] = NewG;
4250 (void)InsertFormula(LU, LUIdx,
F);
4265 const APInt *StepInt;
4270 for (Immediate
Offset : Worklist) {
4272 Offset = Immediate::getFixed(
Offset.getFixedValue() - Step);
4278 for (Immediate
Offset : Worklist)
4285 if (
G->isZero() ||
Imm.isZero() ||
4286 !
Base.BaseOffset.isCompatibleImmediate(
Imm))
4289 F.BaseOffset =
F.BaseOffset.addUnsigned(
Imm);
4290 if (!
isLegalUse(
TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy,
F))
4295 F.BaseRegs[
Idx] =
G;
4300 (void)InsertFormula(LU, LUIdx,
F);
4304void LSRInstance::GenerateConstantOffsets(LSRUse &LU,
unsigned LUIdx,
4310 if (LU.MaxOffset != LU.MinOffset)
4313 for (
size_t i = 0, e =
Base.BaseRegs.size(); i != e; ++i)
4314 GenerateConstantOffsetsImpl(LU, LUIdx,
Base, Worklist, i);
4315 if (
Base.Scale == 1)
4316 GenerateConstantOffsetsImpl(LU, LUIdx,
Base, Worklist, -1,
4322void LSRInstance::GenerateICmpZeroScales(LSRUse &LU,
unsigned LUIdx,
4324 if (LU.Kind != LSRUse::ICmpZero)
return;
4332 if (LU.MinOffset != LU.MaxOffset)
return;
4335 if (
Base.ScaledReg &&
Base.ScaledReg->getType()->isPointerTy())
4337 for (
const SCEV *BaseReg :
Base.BaseRegs)
4338 if (
BaseReg->getType()->isPointerTy())
4340 assert(!
Base.BaseGV &&
"ICmpZero use is not legal!");
4343 for (int64_t Factor : Factors) {
4348 if (
Base.BaseOffset.isMin() && Factor == -1)
4351 if (
Base.BaseOffset.isNonZero() &&
Base.BaseOffset.isScalable())
4353 Immediate NewBaseOffset =
Base.BaseOffset.mulUnsigned(Factor);
4354 assert(Factor != 0 &&
"Zero factor not expected!");
4355 if (NewBaseOffset.getFixedValue() / Factor !=
4356 Base.BaseOffset.getFixedValue())
4364 Immediate
Offset = LU.MinOffset;
4365 if (
Offset.isMin() && Factor == -1)
4368 if (
Offset.getFixedValue() / Factor != LU.MinOffset.getFixedValue())
4376 F.BaseOffset = NewBaseOffset;
4383 F.BaseOffset =
F.BaseOffset.addUnsigned(
Offset).subUnsigned(LU.MinOffset);
4385 const SCEV *FactorS = SE.
getConstant(IntTy, Factor);
4388 for (
size_t i = 0, e =
F.BaseRegs.size(); i != e; ++i) {
4402 if (
F.UnfoldedOffset.isNonZero()) {
4403 if (
F.UnfoldedOffset.isMin() && Factor == -1)
4405 F.UnfoldedOffset =
F.UnfoldedOffset.mulUnsigned(Factor);
4406 if (
F.UnfoldedOffset.getFixedValue() / Factor !=
4407 Base.UnfoldedOffset.getFixedValue())
4411 IntTy,
F.UnfoldedOffset.getFixedValue()))
4416 (void)InsertFormula(LU, LUIdx,
F);
4423void LSRInstance::GenerateScales(LSRUse &LU,
unsigned LUIdx, Formula
Base) {
4430 if (
Base.Scale != 0 && !
Base.unscale())
4433 assert(
Base.Scale == 0 &&
"unscale did not did its job!");
4436 for (int64_t Factor : Factors) {
4437 Base.Scale = Factor;
4438 Base.HasBaseReg =
Base.BaseRegs.size() > 1;
4440 if (!
isLegalUse(
TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy,
4444 if (LU.Kind == LSRUse::Basic &&
4445 isLegalUse(
TTI, LU.MinOffset, LU.MaxOffset, LSRUse::Special,
4446 LU.AccessTy,
Base) &&
4447 LU.AllFixupsOutsideLoop)
4448 LU.Kind = LSRUse::Special;
4454 if (LU.Kind == LSRUse::ICmpZero && !
Base.HasBaseReg &&
4455 Base.BaseOffset.isZero() && !
Base.BaseGV)
4458 for (
size_t i = 0, e =
Base.BaseRegs.size(); i != e; ++i) {
4460 if (AR && (AR->
getLoop() == L || LU.AllFixupsOutsideLoop)) {
4461 const SCEV *FactorS = SE.
getConstant(IntTy, Factor);
4466 if (
const SCEV *Quotient =
getExactSDiv(AR, FactorS, SE,
true))
4467 if (!Quotient->isZero()) {
4470 F.ScaledReg = Quotient;
4471 F.deleteBaseReg(
F.BaseRegs[i]);
4475 if (
F.Scale == 1 && (
F.BaseRegs.empty() ||
4476 (AR->
getLoop() != L && LU.AllFixupsOutsideLoop)))
4480 if (
F.Scale == 1 && LU.AllFixupsOutsideLoop)
4482 (void)InsertFormula(LU, LUIdx,
F);
4498 const SCEV *Result =
nullptr;
4499 for (
auto &L :
Loops) {
4503 if (!New || (Result && New != Result))
4508 assert(Result &&
"failed to create expression");
4513void LSRInstance::GenerateTruncates(LSRUse &LU,
unsigned LUIdx, Formula
Base) {
4515 if (
Base.BaseGV)
return;
4525 if (
Base.ScaledReg &&
Base.ScaledReg->getType()->isPointerTy())
4528 [](
const SCEV *S) { return S->getType()->isPointerTy(); }))
4532 for (
auto &LF : LU.Fixups)
4533 Loops.push_back(LF.PostIncLoops);
4535 for (
Type *SrcTy : Types) {
4544 const SCEV *NewScaledReg =
4546 if (!NewScaledReg || NewScaledReg->
isZero())
4548 F.ScaledReg = NewScaledReg;
4550 bool HasZeroBaseReg =
false;
4551 for (
const SCEV *&BaseReg :
F.BaseRegs) {
4552 const SCEV *NewBaseReg =
4554 if (!NewBaseReg || NewBaseReg->
isZero()) {
4555 HasZeroBaseReg =
true;
4565 if (!
F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses))
4569 (void)InsertFormula(LU, LUIdx,
F);
4582 const SCEV *OrigReg;
4584 WorkItem(
size_t LI, Immediate
I,
const SCEV *R)
4585 : LUIdx(LI),
Imm(
I), OrigReg(
R) {}
4587 void print(raw_ostream &OS)
const;
4593#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4594void WorkItem::print(raw_ostream &OS)
const {
4595 OS <<
"in formulae referencing " << *OrigReg <<
" in use " << LUIdx
4596 <<
" , add offset " <<
Imm;
4606void LSRInstance::GenerateCrossUseConstantOffsets() {
4608 using ImmMapTy = std::map<Immediate, const SCEV *, KeyOrderTargetImmediate>;
4610 DenseMap<const SCEV *, ImmMapTy>
Map;
4611 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap;
4613 for (
const SCEV *Use : RegUses) {
4617 auto Pair =
Map.try_emplace(
Reg);
4620 Pair.first->second.insert(std::make_pair(
Imm, Use));
4621 UsedByIndicesMap[
Reg] |= RegUses.getUsedByIndices(Use);
4628 SmallSet<std::pair<size_t, Immediate>, 32, KeyOrderSizeTAndImmediate>
4630 for (
const SCEV *
Reg : Sequence) {
4631 const ImmMapTy &Imms =
Map.find(
Reg)->second;
4634 if (Imms.size() == 1)
4638 for (
const auto &Entry
4640 <<
' ' <<
Entry.first;
4644 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end();
4646 const SCEV *OrigReg = J->second;
4648 Immediate JImm = J->first;
4649 const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(OrigReg);
4652 UsedByIndicesMap[
Reg].
count() == 1) {
4660 Immediate
First = Imms.begin()->first;
4661 Immediate
Last = std::prev(Imms.end())->first;
4662 if (!
First.isCompatibleImmediate(
Last)) {
4669 bool Scalable =
First.isScalable() ||
Last.isScalable();
4670 int64_t FI =
First.getKnownMinValue();
4671 int64_t LI =
Last.getKnownMinValue();
4674 int64_t Avg = (FI & LI) + ((FI ^ LI) >> 1);
4677 Avg = Avg + ((FI ^ LI) & ((
uint64_t)Avg >> 63));
4678 ImmMapTy::const_iterator OtherImms[] = {
4679 Imms.begin(), std::prev(Imms.end()),
4680 Imms.lower_bound(Immediate::get(Avg, Scalable))};
4681 for (
const auto &M : OtherImms) {
4682 if (M == J || M == JE)
continue;
4683 if (!JImm.isCompatibleImmediate(
M->first))
4687 Immediate
Imm = JImm.subUnsigned(
M->first);
4688 for (
unsigned LUIdx : UsedByIndices.
set_bits())
4690 if (UniqueItems.
insert(std::make_pair(LUIdx,
Imm)).second)
4698 UsedByIndicesMap.
clear();
4699 UniqueItems.
clear();
4702 for (
const WorkItem &WI : WorkItems) {
4703 size_t LUIdx = WI.LUIdx;
4704 LSRUse &LU =
Uses[LUIdx];
4705 Immediate
Imm = WI.Imm;
4706 const SCEV *OrigReg = WI.OrigReg;
4709 const SCEV *NegImmS =
Imm.getNegativeSCEV(SE, IntTy);
4713 for (
size_t L = 0, LE = LU.Formulae.size(); L != LE; ++L) {
4714 Formula
F = LU.Formulae[
L];
4721 if (
F.ScaledReg == OrigReg) {
4722 if (!
F.BaseOffset.isCompatibleImmediate(
Imm))
4724 Immediate
Offset =
F.BaseOffset.addUnsigned(
Imm.mulUnsigned(
F.Scale));
4726 const SCEV *S =
Offset.getNegativeSCEV(SE, IntTy);
4727 if (
F.referencesReg(S))
4730 NewF.BaseOffset =
Offset;
4731 if (!
isLegalUse(
TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy,
4734 NewF.ScaledReg = SE.
getAddExpr(NegImmS, NewF.ScaledReg);
4743 if (NewF.BaseOffset.isNonZero() && NewF.BaseOffset.isScalable())
4745 if (
C->getValue()->isNegative() !=
4746 (NewF.BaseOffset.isLessThanZero()) &&
4747 (
C->getAPInt().abs() * APInt(
BitWidth,
F.Scale))
4748 .ule(std::abs(NewF.BaseOffset.getFixedValue())))
4753 NewF.canonicalize(*this->L);
4754 (void)InsertFormula(LU, LUIdx, NewF);
4757 for (
size_t N = 0, NE =
F.BaseRegs.size();
N != NE; ++
N) {
4759 if (BaseReg != OrigReg)
4762 if (!NewF.BaseOffset.isCompatibleImmediate(
Imm) ||
4763 !NewF.UnfoldedOffset.isCompatibleImmediate(
Imm) ||
4764 !NewF.BaseOffset.isCompatibleImmediate(NewF.UnfoldedOffset))
4766 NewF.BaseOffset = NewF.BaseOffset.addUnsigned(
Imm);
4768 LU.Kind, LU.AccessTy, NewF)) {
4772 Immediate NewUnfoldedOffset = NewF.UnfoldedOffset.addUnsigned(
Imm);
4776 NewF.UnfoldedOffset = NewUnfoldedOffset;
4778 NewF.BaseRegs[
N] = SE.
getAddExpr(NegImmS, BaseReg);
4783 for (
const SCEV *NewReg : NewF.BaseRegs)
4785 if (NewF.BaseOffset.isNonZero() && NewF.BaseOffset.isScalable())
4787 if ((
C->getAPInt() + NewF.BaseOffset.getFixedValue())
4789 .slt(std::abs(NewF.BaseOffset.getFixedValue())) &&
4790 (
C->getAPInt() + NewF.BaseOffset.getFixedValue())
4793 NewF.BaseOffset.getFixedValue()))
4798 NewF.canonicalize(*this->L);
4799 (void)InsertFormula(LU, LUIdx, NewF);
4810LSRInstance::GenerateAllReuseFormulae() {
4813 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
4814 LSRUse &LU =
Uses[LUIdx];
4815 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4816 GenerateReassociations(LU, LUIdx, LU.Formulae[i]);
4817 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4818 GenerateCombinations(LU, LUIdx, LU.Formulae[i]);
4820 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
4821 LSRUse &LU =
Uses[LUIdx];
4822 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4823 GenerateSymbolicOffsets(LU, LUIdx, LU.Formulae[i]);
4824 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4825 GenerateConstantOffsets(LU, LUIdx, LU.Formulae[i]);
4826 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4827 GenerateICmpZeroScales(LU, LUIdx, LU.Formulae[i]);
4828 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4829 GenerateScales(LU, LUIdx, LU.Formulae[i]);
4831 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
4832 LSRUse &LU =
Uses[LUIdx];
4833 for (
size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
4834 GenerateTruncates(LU, LUIdx, LU.Formulae[i]);
4837 GenerateCrossUseConstantOffsets();
4840 "After generating reuse formulae:\n";
4841 print_uses(
dbgs()));
4846void LSRInstance::FilterOutUndesirableDedicatedRegisters() {
4847 DenseSet<const SCEV *> VisitedRegs;
4848 SmallPtrSet<const SCEV *, 16> Regs;
4849 SmallPtrSet<const SCEV *, 16> LoserRegs;
4851 bool ChangedFormulae =
false;
4856 using BestFormulaeTy = DenseMap<SmallVector<const SCEV *, 4>,
size_t>;
4858 BestFormulaeTy BestFormulae;
4860 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
4861 LSRUse &LU =
Uses[LUIdx];
4866 for (
size_t FIdx = 0, NumForms = LU.Formulae.size();
4867 FIdx != NumForms; ++FIdx) {
4868 Formula &
F = LU.Formulae[FIdx];
4877 Cost CostF(Opts, L, SE,
TTI, AMK);
4879 CostF.RateFormula(
F, Regs, VisitedRegs, LU, HardwareLoopProfitable,
4881 if (CostF.isLoser()) {
4893 for (
const SCEV *
Reg :
F.BaseRegs) {
4894 if (RegUses.isRegUsedByUsesOtherThan(
Reg, LUIdx))
4898 RegUses.isRegUsedByUsesOtherThan(
F.ScaledReg, LUIdx))
4899 Key.push_back(
F.ScaledReg);
4904 std::pair<BestFormulaeTy::const_iterator, bool>
P =
4905 BestFormulae.insert(std::make_pair(
Key, FIdx));
4909 Formula &Best = LU.Formulae[
P.first->second];
4911 Cost CostBest(Opts, L, SE,
TTI, AMK);
4913 CostBest.RateFormula(Best, Regs, VisitedRegs, LU,
4914 HardwareLoopProfitable);
4915 if (CostF.isLess(CostBest))
4919 " in favor of formula ";
4920 Best.print(
dbgs());
dbgs() <<
'\n');
4923 ChangedFormulae =
true;
4925 LU.DeleteFormula(
F);
4933 LU.RecomputeRegs(LUIdx, RegUses);
4936 BestFormulae.clear();
4941 "After filtering out undesirable candidates:\n";
4949size_t LSRInstance::EstimateSearchSpaceComplexity()
const {
4951 for (
const LSRUse &LU :
Uses) {
4952 size_t FSize = LU.Formulae.size();
4953 if (FSize >= Opts.lsr_complexity_limit) {
4954 Power = Opts.lsr_complexity_limit;
4958 if (Power >= Opts.lsr_complexity_limit)
4967void LSRInstance::NarrowSearchSpaceByDetectingSupersets() {
4968 if (EstimateSearchSpaceComplexity() >= Opts.lsr_complexity_limit) {
4971 LLVM_DEBUG(
dbgs() <<
"Narrowing the search space by eliminating formulae "
4972 "which use a superset of registers used by other "
4975 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
4976 LSRUse &LU =
Uses[LUIdx];
4978 for (
size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
4979 Formula &
F = LU.Formulae[i];
4980 if (
F.BaseOffset.isNonZero() &&
F.BaseOffset.isScalable())
4986 I =
F.BaseRegs.begin(),
E =
F.BaseRegs.end();
I !=
E; ++
I) {
4992 Immediate::getFixed(NewF.BaseOffset.getFixedValue() +
4993 (
uint64_t)
C->getValue()->getSExtValue());
4994 NewF.BaseRegs.erase(NewF.BaseRegs.begin() +
4995 (
I -
F.BaseRegs.begin()));
4996 if (LU.HasFormulaWithSameRegs(NewF)) {
4999 LU.DeleteFormula(
F);
5010 NewF.BaseRegs.erase(NewF.BaseRegs.begin() +
5011 (
I -
F.BaseRegs.begin()));
5012 if (LU.HasFormulaWithSameRegs(NewF)) {
5015 LU.DeleteFormula(
F);
5026 LU.RecomputeRegs(LUIdx, RegUses);
5035void LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode() {
5036 if (EstimateSearchSpaceComplexity() < Opts.lsr_complexity_limit)
5040 dbgs() <<
"The search space is too complex.\n"
5041 "Narrowing the search space by assuming that uses separated "
5042 "by a constant offset will use the same registers.\n");
5046 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
5047 LSRUse &LU =
Uses[LUIdx];
5048 for (
const Formula &
F : LU.Formulae) {
5049 if (
F.BaseOffset.isZero() || (
F.Scale != 0 &&
F.Scale != 1))
5051 assert((LU.Kind == LSRUse::Address || LU.Kind == LSRUse::ICmpZero) &&
5052 "Only address and cmp uses expected to have nonzero BaseOffset");
5054 LSRUse *LUThatHas = FindUseWithSimilarFormula(
F, LU);
5058 if (!reconcileNewOffset(*LUThatHas,
F.BaseOffset,
false,
5059 LU.Kind, LU.AccessTy))
5064 LUThatHas->AllFixupsOutsideLoop &= LU.AllFixupsOutsideLoop;
5065 LUThatHas->AllFixupsUnconditional &= LU.AllFixupsUnconditional;
5068 for (LSRFixup &Fixup : LU.Fixups) {
5069 Fixup.Offset +=
F.BaseOffset;
5070 LUThatHas->pushFixup(Fixup);
5075 Type *FixupType = LUThatHas->Fixups[0].OperandValToReplace->getType();
5076 for (LSRFixup &Fixup : LUThatHas->Fixups)
5077 assert(
Fixup.OperandValToReplace->getType() == FixupType &&
5078 "Expected all fixups to have the same type");
5083 for (
size_t i = 0, e = LUThatHas->Formulae.size(); i != e; ++i) {
5084 Formula &
F = LUThatHas->Formulae[i];
5085 if (!
isLegalUse(
TTI, LUThatHas->MinOffset, LUThatHas->MaxOffset,
5086 LUThatHas->Kind, LUThatHas->AccessTy,
F)) {
5088 LUThatHas->DeleteFormula(
F);
5096 LUThatHas->RecomputeRegs(LUThatHas - &
Uses.front(), RegUses);
5099 DeleteUse(LU, LUIdx);
5112void LSRInstance::NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters(){
5113 if (EstimateSearchSpaceComplexity() >= Opts.lsr_complexity_limit) {
5116 LLVM_DEBUG(
dbgs() <<
"Narrowing the search space by re-filtering out "
5117 "undesirable dedicated registers.\n");
5119 FilterOutUndesirableDedicatedRegisters();
5134void LSRInstance::NarrowSearchSpaceByFilterFormulaWithSameScaledReg() {
5135 if (EstimateSearchSpaceComplexity() < Opts.lsr_complexity_limit)
5139 dbgs() <<
"The search space is too complex.\n"
5140 "Narrowing the search space by choosing the best Formula "
5141 "from the Formulae with the same Scale and ScaledReg.\n");
5144 using BestFormulaeTy = DenseMap<std::pair<const SCEV *, int64_t>,
size_t>;
5146 BestFormulaeTy BestFormulae;
5148 bool ChangedFormulae =
false;
5150 DenseSet<const SCEV *> VisitedRegs;
5151 SmallPtrSet<const SCEV *, 16> Regs;
5153 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
5154 LSRUse &LU =
Uses[LUIdx];
5159 auto IsBetterThan = [&](Formula &FA, Formula &FB) {
5164 size_t FARegNum = 0;
5165 for (
const SCEV *
Reg : FA.BaseRegs) {
5166 const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(
Reg);
5167 FARegNum += (NumUses - UsedByIndices.
count() + 1);
5169 size_t FBRegNum = 0;
5170 for (
const SCEV *
Reg : FB.BaseRegs) {
5171 const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(
Reg);
5172 FBRegNum += (NumUses - UsedByIndices.
count() + 1);
5174 if (FARegNum != FBRegNum)
5175 return FARegNum < FBRegNum;
5179 Cost CostFA(Opts, L, SE,
TTI, AMK);
5180 Cost CostFB(Opts, L, SE,
TTI, AMK);
5182 CostFA.RateFormula(FA, Regs, VisitedRegs, LU, HardwareLoopProfitable);
5184 CostFB.RateFormula(FB, Regs, VisitedRegs, LU, HardwareLoopProfitable);
5185 return CostFA.isLess(CostFB);
5189 for (
size_t FIdx = 0, NumForms = LU.Formulae.size(); FIdx != NumForms;
5191 Formula &
F = LU.Formulae[FIdx];
5194 auto P = BestFormulae.insert({{
F.ScaledReg,
F.Scale}, FIdx});
5198 Formula &Best = LU.Formulae[
P.first->second];
5199 if (IsBetterThan(
F, Best))
5203 " in favor of formula ";
5204 Best.print(
dbgs());
dbgs() <<
'\n');
5206 ChangedFormulae =
true;
5208 LU.DeleteFormula(
F);
5214 LU.RecomputeRegs(LUIdx, RegUses);
5217 BestFormulae.clear();
5222 "After filtering out undesirable candidates:\n";
5229void LSRInstance::NarrowSearchSpaceByFilterPostInc() {
5232 if (EstimateSearchSpaceComplexity() < Opts.lsr_complexity_limit)
5236 "Narrowing the search space by choosing the lowest "
5237 "register Formula for PostInc Uses.\n");
5239 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
5240 LSRUse &LU =
Uses[LUIdx];
5242 if (LU.Kind != LSRUse::Address)
5248 size_t MinRegs = std::numeric_limits<size_t>::max();
5249 for (
const Formula &
F : LU.Formulae)
5250 MinRegs = std::min(
F.getNumRegs(), MinRegs);
5253 for (
size_t FIdx = 0, NumForms = LU.Formulae.size(); FIdx != NumForms;
5255 Formula &
F = LU.Formulae[FIdx];
5256 if (
F.getNumRegs() > MinRegs) {
5259 LU.DeleteFormula(
F);
5266 LU.RecomputeRegs(LUIdx, RegUses);
5268 if (EstimateSearchSpaceComplexity() < Opts.lsr_complexity_limit)
5275void LSRInstance::NarrowSearchSpaceByMergingUsesOutsideLoop() {
5276 if (EstimateSearchSpaceComplexity() < Opts.lsr_complexity_limit)
5280 dbgs() <<
"The search space is too complex.\n"
5281 "Narrowing the search space by merging uses with fixups "
5282 "entirely outside the loop with uses inside the loop.\n");
5284 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
5285 LSRUse &LU =
Uses[LUIdx];
5288 if (!LU.AllFixupsOutsideLoop || LU.Formulae.empty() ||
5289 LU.Kind == LSRUse::ICmpZero)
5296 LSRUse *LUToMergeWith =
nullptr;
5297 const Formula &ThisF = LU.Formulae[0];
5298 for (LSRUse &OtherLU :
Uses) {
5300 if (OtherLU.AllFixupsOutsideLoop)
5304 if (OtherLU.Kind == LSRUse::ICmpZero)
5307 if (OtherLU.Formulae.empty())
5310 if (
any_of(OtherLU.Formulae, [&](
const Formula &
F) {
5311 return !isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, OtherLU.Kind,
5312 OtherLU.AccessTy, F);
5319 const Formula &OtherF = OtherLU.Formulae[0];
5320 if (ThisF.BaseRegs == OtherF.BaseRegs &&
5321 ThisF.ScaledReg == OtherF.ScaledReg &&
5322 ThisF.BaseGV == OtherF.BaseGV && ThisF.Scale == OtherF.Scale &&
5323 ThisF.UnfoldedOffset == OtherF.UnfoldedOffset &&
5324 ThisF.BaseOffset == OtherF.BaseOffset) {
5325 LUToMergeWith = &OtherLU;
5336 for (LSRFixup &Fixup : LU.Fixups) {
5337 LUToMergeWith->pushFixup(Fixup);
5341 DeleteUse(LU, LUIdx);
5391void LSRInstance::NarrowSearchSpaceByDeletingCostlyFormulas() {
5392 if (EstimateSearchSpaceComplexity() < Opts.lsr_complexity_limit)
5400 SmallPtrSet<const SCEV *, 4> UniqRegs;
5404 DenseMap <const SCEV *, float> RegNumMap;
5405 for (
const SCEV *
Reg : RegUses) {
5409 for (
const LSRUse &LU :
Uses) {
5410 if (!LU.Regs.count(
Reg))
5412 float P = LU.getNotSelectedProbability(
Reg);
5418 RegNumMap.
insert(std::make_pair(
Reg, PNotSel));
5422 dbgs() <<
"Narrowing the search space by deleting costly formulas\n");
5425 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
5426 LSRUse &LU =
Uses[LUIdx];
5428 if (LU.Formulae.size() < 2)
5433 float FMinRegNum = LU.Formulae[0].getNumRegs();
5434 float FMinARegNum = LU.Formulae[0].getNumRegs();
5436 for (
size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
5437 Formula &
F = LU.Formulae[i];
5440 for (
const SCEV *BaseReg :
F.BaseRegs) {
5441 if (UniqRegs.
count(BaseReg))
5443 FRegNum += RegNumMap[
BaseReg] / LU.getNotSelectedProbability(BaseReg);
5446 RegNumMap[
BaseReg] / LU.getNotSelectedProbability(BaseReg);
5448 if (
const SCEV *ScaledReg =
F.ScaledReg) {
5449 if (!UniqRegs.
count(ScaledReg)) {
5451 RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
5454 RegNumMap[ScaledReg] / LU.getNotSelectedProbability(ScaledReg);
5457 if (FMinRegNum > FRegNum ||
5458 (FMinRegNum == FRegNum && FMinARegNum > FARegNum)) {
5459 FMinRegNum = FRegNum;
5460 FMinARegNum = FARegNum;
5465 dbgs() <<
" with min reg num " << FMinRegNum <<
'\n');
5467 std::swap(LU.Formulae[MinIdx], LU.Formulae[0]);
5468 while (LU.Formulae.size() != 1) {
5471 LU.Formulae.pop_back();
5473 LU.RecomputeRegs(LUIdx, RegUses);
5474 assert(LU.Formulae.size() == 1 &&
"Should be exactly 1 min regs formula");
5475 Formula &
F = LU.Formulae[0];
5491 MemAccessTy AccessType) {
5501 return TTI.isLegalAddressingMode(
5502 AccessType.MemTy,
nullptr,
5503 Diff->getSExtValue(),
5504 true, 0, AccessType.AddrSpace) &&
5505 !
TTI.isLegalAddressingMode(
5506 AccessType.MemTy,
nullptr,
5507 -Diff->getSExtValue(),
5508 true, 0, AccessType.AddrSpace);
5514void LSRInstance::NarrowSearchSpaceByPickingWinnerRegs() {
5517 SmallPtrSet<const SCEV *, 4> Taken;
5518 while (EstimateSearchSpaceComplexity() >= Opts.lsr_complexity_limit) {
5525 const SCEV *Best =
nullptr;
5526 unsigned BestNum = 0;
5527 for (
const SCEV *
Reg : RegUses) {
5532 BestNum = RegUses.getUsedByIndices(
Reg).count();
5534 unsigned Count = RegUses.getUsedByIndices(
Reg).count();
5535 if (
Count > BestNum) {
5543 if (
Count == BestNum) {
5544 int LUIdx = RegUses.getUsedByIndices(
Reg).find_first();
5545 if (LUIdx >= 0 &&
Uses[LUIdx].Kind == LSRUse::Address &&
5547 Uses[LUIdx].AccessTy)) {
5554 assert(Best &&
"Failed to find best LSRUse candidate");
5556 LLVM_DEBUG(
dbgs() <<
"Narrowing the search space by assuming " << *Best
5557 <<
" will yield profitable reuse.\n");
5562 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx) {
5563 LSRUse &LU =
Uses[LUIdx];
5564 if (!LU.Regs.count(Best))
continue;
5567 for (
size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
5568 Formula &
F = LU.Formulae[i];
5569 if (!
F.referencesReg(Best)) {
5571 LU.DeleteFormula(
F);
5575 assert(e != 0 &&
"Use has no formulae left! Is Regs inconsistent?");
5581 LU.RecomputeRegs(LUIdx, RegUses);
5592void LSRInstance::NarrowSearchSpaceUsingHeuristics() {
5593 NarrowSearchSpaceByDetectingSupersets();
5594 NarrowSearchSpaceByCollapsingUnrolledCode();
5595 NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
5596 if (Opts.lsr_filter_same_scaled_reg)
5597 NarrowSearchSpaceByFilterFormulaWithSameScaledReg();
5598 NarrowSearchSpaceByFilterPostInc();
5599 NarrowSearchSpaceByMergingUsesOutsideLoop();
5600 if (Opts.lsr_exp_narrow)
5601 NarrowSearchSpaceByDeletingCostlyFormulas();
5603 NarrowSearchSpaceByPickingWinnerRegs();
5607void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
5609 SmallVectorImpl<const Formula *> &Workspace,
5610 const Cost &CurCost,
5611 const SmallPtrSet<const SCEV *, 16> &CurRegs,
5612 DenseSet<const SCEV *> &VisitedRegs)
const {
5623 const LSRUse &LU =
Uses[Workspace.
size()];
5629 SmallSetVector<const SCEV *, 4> ReqRegs;
5630 for (
const SCEV *S : CurRegs)
5631 if (LU.Regs.count(S))
5634 SmallPtrSet<const SCEV *, 16> NewRegs;
5635 Cost NewCost(Opts, L, SE,
TTI, AMK);
5636 for (
const Formula &
F : LU.Formulae) {
5644 int NumReqRegsToFind = std::min(
F.getNumRegs(), ReqRegs.
size());
5645 for (
const SCEV *
Reg : ReqRegs) {
5646 if ((
F.ScaledReg &&
F.ScaledReg ==
Reg) ||
5649 if (NumReqRegsToFind == 0)
5653 if (NumReqRegsToFind != 0) {
5664 NewCost.RateFormula(
F, NewRegs, VisitedRegs, LU, HardwareLoopProfitable);
5665 if (NewCost.isLess(SolutionCost)) {
5667 if (Workspace.
size() !=
Uses.size()) {
5668 SolveRecurse(Solution, SolutionCost, Workspace, NewCost,
5669 NewRegs, VisitedRegs);
5670 if (
F.getNumRegs() == 1 && Workspace.
size() == 1)
5671 VisitedRegs.
insert(
F.ScaledReg ?
F.ScaledReg :
F.BaseRegs[0]);
5674 dbgs() <<
".\nRegs:\n";
5675 for (
const SCEV *S : NewRegs)
dbgs()
5676 <<
"- " << *S <<
"\n";
5679 SolutionCost = NewCost;
5680 Solution = Workspace;
5689void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution)
const {
5691 Cost SolutionCost(Opts, L, SE,
TTI, AMK);
5692 SolutionCost.Lose();
5693 Cost CurCost(Opts, L, SE,
TTI, AMK);
5694 SmallPtrSet<const SCEV *, 16> CurRegs;
5695 DenseSet<const SCEV *> VisitedRegs;
5699 SolveRecurse(Solution, SolutionCost, Workspace, CurCost,
5700 CurRegs, VisitedRegs);
5701 if (Solution.
empty()) {
5708 "The chosen solution requires ";
5709 SolutionCost.print(
dbgs());
dbgs() <<
":\n";
5710 for (
size_t i = 0, e =
Uses.size(); i != e; ++i) {
5715 Solution[i]->print(
dbgs());
5721 const bool EnableDropUnprofitableSolution =
valueOr(
5724 if (BaselineCost.isLess(SolutionCost)) {
5725 if (!EnableDropUnprofitableSolution)
5727 dbgs() <<
"Baseline is more profitable than chosen solution, "
5728 "add option 'lsr-drop-solution' to drop LSR solution.\n");
5731 "solution, dropping LSR solution.\n";);
5742 const SmallVectorImpl<Instruction *> &Inputs)
5746 bool AllDominate =
true;
5753 for (Instruction *Inst : Inputs) {
5754 if (Inst == Tentative || !DT.
dominates(Inst, Tentative)) {
5755 AllDominate =
false;
5760 if (Tentative->
getParent() == Inst->getParent() &&
5761 (!BetterPos || !DT.
dominates(Inst, BetterPos)))
5771 const Loop *IPLoop = LI.getLoopFor(IP->getParent());
5772 unsigned IPLoopDepth = IPLoop ? IPLoop->
getLoopDepth() : 0;
5776 if (!Rung)
return IP;
5777 Rung = Rung->getIDom();
5778 if (!Rung)
return IP;
5779 IDom = Rung->getBlock();
5782 const Loop *IDomLoop = LI.getLoopFor(IDom);
5783 unsigned IDomDepth = IDomLoop ? IDomLoop->
getLoopDepth() : 0;
5784 if (IDomDepth <= IPLoopDepth &&
5785 (IDomDepth != IPLoopDepth || IDomLoop == IPLoop))
5802 SmallVector<Instruction *, 4> Inputs;
5805 if (LU.Kind == LSRUse::ICmpZero)
5806 if (Instruction *
I =
5809 if (LF.PostIncLoops.
count(L)) {
5810 if (LF.isUseFullyOutsideLoop(L))
5811 Inputs.
push_back(
L->getLoopLatch()->getTerminator());
5817 for (
const Loop *PIL : LF.PostIncLoops) {
5818 if (PIL == L)
continue;
5823 if (!ExitingBlocks.
empty()) {
5825 for (
unsigned i = 1, e = ExitingBlocks.
size(); i != e; ++i)
5832 "Insertion point must be a normal instruction");
5842 while (IP->isEHPad()) ++IP;
5847 while (
Rewriter.isInsertedInstruction(&*IP) && IP != LowestIP)
5855Value *LSRInstance::Expand(
const LSRUse &LU,
const LSRFixup &LF,
5857 SmallVectorImpl<WeakTrackingVH> &DeadInsts)
const {
5858 if (LU.RigidFormula)
5859 return LF.OperandValToReplace;
5863 IP = AdjustInsertPositionForExpand(IP, LF, LU);
5868 Rewriter.setPostInc(LF.PostIncLoops);
5873 Type *Ty =
F.getType();
5886 if (LU.Kind == LSRUse::ICmpZero && OpTy->
isPointerTy()) {
5895 for (
const SCEV *
Reg :
F.BaseRegs) {
5896 assert(!
Reg->isZero() &&
"Zero allocated in a base register!");
5904 Value *ICmpScaledV =
nullptr;
5906 const SCEV *ScaledS =
F.ScaledReg;
5912 if (LU.Kind == LSRUse::ICmpZero) {
5922 "The only scale supported by ICmpZero uses is -1!");
5923 ICmpScaledV =
Rewriter.expandCodeFor(ScaledS,
nullptr);
5931 if (!
Ops.empty() && LU.Kind == LSRUse::Address &&
5941 Ops.push_back(ScaledS);
5967 assert(
F.BaseOffset.isCompatibleImmediate(LF.Offset) &&
5968 "Expanding mismatched offsets\n");
5970 Immediate
Offset =
F.BaseOffset.addUnsigned(LF.Offset);
5971 if (
Offset.isNonZero()) {
5972 if (LU.Kind == LSRUse::ICmpZero) {
5988 Ops.push_back(
Offset.getUnknownSCEV(SE, IntTy));
5993 Immediate UnfoldedOffset =
F.UnfoldedOffset;
5994 if (UnfoldedOffset.isNonZero()) {
5996 Ops.push_back(UnfoldedOffset.getUnknownSCEV(SE, IntTy));
6010 if (LU.Kind == LSRUse::ICmpZero) {
6014 assert(!
F.BaseGV &&
"ICmp does not support folding a global value and "
6015 "a scale at the same time!");
6016 if (
F.Scale == -1) {
6017 if (ICmpScaledV->
getType() != OpTy) {
6027 assert((
F.Scale == 0 ||
F.Scale == 1) &&
6028 "ICmp does not support folding a global value and "
6029 "a scale at the same time!");
6035 if (
C->getType() != OpTy) {
6039 assert(
C &&
"Cast of ConstantInt should have folded");
6052void LSRInstance::RewriteForPHI(PHINode *PN,
const LSRUse &LU,
6053 const LSRFixup &LF,
const Formula &
F,
6054 SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
6055 DenseMap<BasicBlock *, Value *>
Inserted;
6059 bool needUpdateFixups =
false;
6070 Loop *PNLoop = LI.getLoopFor(Parent);
6071 if (!PNLoop || Parent != PNLoop->
getHeader()) {
6075 CriticalEdgeSplittingOptions SplitOptions(&DT, &LI, MSSAU);
6077 SplitOptions.setMergeIdenticalEdges().setKeepOneInputPHIs();
6078 if (ShouldPreserveLCSSA)
6079 SplitOptions = SplitOptions.setPreserveLCSSA();
6083 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
6085 MSSAU, ShouldPreserveLCSSA);
6095 if (
L->contains(BB) && !
L->contains(PN))
6103 needUpdateFixups =
true;
6105 if (
auto *OldIncomingInst =
6112 std::pair<DenseMap<BasicBlock *, Value *>::iterator,
bool> Pair =
6125 LF.OperandValToReplace->
getType(),
"tmp",
6132 if (
L->contains(
I) && !
L->contains(BB))
6133 InsertedNonLCSSAInsts.insert(
I);
6136 Pair.first->second = FullV;
6143 if (needUpdateFixups) {
6144 for (LSRUse &LU :
Uses)
6145 for (LSRFixup &Fixup : LU.Fixups)
6149 if (
Fixup.UserInst == PN) {
6152 bool foundInOriginalPHI =
false;
6154 if (val ==
Fixup.OperandValToReplace) {
6155 foundInOriginalPHI =
true;
6160 if (foundInOriginalPHI)
6171 if (val ==
Fixup.OperandValToReplace)
6172 Fixup.UserInst = NewPN;
6182void LSRInstance::Rewrite(
const LSRUse &LU,
const LSRFixup &LF,
6184 SmallVectorImpl<WeakTrackingVH> &DeadInsts) {
6188 RewriteForPHI(PN, LU, LF,
F, DeadInsts);
6196 if (FullV->
getType() != OpTy &&
6197 !(LU.Kind == LSRUse::ICmpZero && OpTy->
isPointerTy())) {
6209 if (LU.Kind == LSRUse::ICmpZero)
6225 const LSRFixup &Fixup,
const LSRUse &LU,
6229 if (LU.Kind != LSRUse::Address)
6230 return IVIncInsertPos;
6234 Type *Ty =
I->getType();
6237 return IVIncInsertPos;
6244 return IVIncInsertPos;
6251void LSRInstance::ImplementSolution(
6252 const SmallVectorImpl<const Formula *> &Solution) {
6258 for (
const IVChain &Chain : IVChainVec) {
6264 for (
size_t LUIdx = 0, NumUses =
Uses.size(); LUIdx != NumUses; ++LUIdx)
6265 for (
const LSRFixup &Fixup :
Uses[LUIdx].Fixups) {
6268 Rewriter.setIVIncInsertPos(L, InsertPos);
6269 Rewrite(
Uses[LUIdx], Fixup, *Solution[LUIdx], DeadInsts);
6273 auto InsertedInsts = InsertedNonLCSSAInsts.takeVector();
6276 for (
const IVChain &Chain : IVChainVec) {
6277 GenerateIVChain(Chain, DeadInsts);
6281 for (
const WeakVH &
IV :
Rewriter.getInsertedIVs())
6299 for (PHINode &PN :
L->getHeader()->phis()) {
6300 BinaryOperator *BO =
nullptr;
6306 case Instruction::Sub:
6311 case Instruction::Add:
6328 [&](Use &U) {return DT.dominates(IVIncInsertPos, U);}))
6337LSRInstance::LSRInstance(
const ScalarOptions &Opts,
Loop *L, IVUsers &IU,
6338 ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI,
6339 const TargetTransformInfo &
TTI, AssumptionCache &AC,
6340 TargetLibraryInfo &
TLI, MemorySSAUpdater *MSSAU,
6342 : Opts(Opts), IU(IU), SE(SE), DT(DT), LI(LI), AC(AC),
TLI(
TLI),
TTI(
TTI),
6343 L(
L), MSSAU(MSSAU), AMK(Opts.lsr_preferred_addressing_mode.value_or(
6344 TTI.getPreferredAddressingMode(
L, &SE))),
6345 Rewriter(SE,
"lsr", PreserveLCSSA), ShouldPreserveLCSSA(PreserveLCSSA),
6346 BaselineCost(Opts,
L, SE,
TTI, AMK) {
6348 if (!
L->isLoopSimplifyForm())
6356 unsigned NumUsers = 0;
6360 LLVM_DEBUG(
dbgs() <<
"LSR skipping loop, too many IV Users in " << U
6368 auto FirstNonPHI = PN->
getParent()->getFirstNonPHIIt();
6378 L->getHeader()->printAsOperand(
dbgs(),
false);
6384 HardwareLoopProfitable =
6385 TTI.isHardwareLoopProfitable(L, SE, AC, &
TLI, HWLoopInfo);
6389#if LLVM_ENABLE_ABI_BREAKING_CHECKS
6392 Rewriter.disableCanonicalMode();
6393 Rewriter.enableLSRMode();
6397 OptimizeLoopTermCond();
6400 if (IU.empty())
return;
6403 if (!
L->isInnermost()) {
6416 CollectInterestingTypesAndFactors();
6417 CollectFixupsAndInitialFormulae();
6418 CollectLoopInvariantFixupsAndFormulae();
6424 print_uses(
dbgs()));
6426 BaselineCost.print(
dbgs());
dbgs() <<
"\n");
6430 GenerateAllReuseFormulae();
6432 FilterOutUndesirableDedicatedRegisters();
6433 NarrowSearchSpaceUsingHeuristics();
6443 if (Solution.
empty())
6448 for (
const LSRUse &LU :
Uses) {
6449 for (
const Formula &
F : LU.Formulae)
6451 F) &&
"Illegal formula generated!");
6456 ImplementSolution(Solution);
6459#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
6460void LSRInstance::print_factors_and_types(
raw_ostream &OS)
const {
6461 if (Factors.empty() &&
Types.empty())
return;
6463 OS <<
"LSR has identified the following interesting factors and types: ";
6466 for (int64_t Factor : Factors)
6467 OS <<
LS <<
'*' << Factor;
6469 for (
Type *Ty : Types)
6470 OS <<
LS <<
'(' << *Ty <<
')';
6474void LSRInstance::print_fixups(raw_ostream &OS)
const {
6475 OS <<
"LSR is examining the following fixup sites:\n";
6476 for (
const LSRUse &LU :
Uses)
6477 for (
const LSRFixup &LF : LU.Fixups) {
6484void LSRInstance::print_uses(raw_ostream &OS)
const {
6485 OS <<
"LSR is examining the following uses:\n";
6486 for (
const LSRUse &LU :
Uses) {
6490 for (
const Formula &
F : LU.Formulae) {
6498void LSRInstance::print(raw_ostream &OS)
const {
6499 print_factors_and_types(OS);
6511class LoopStrengthReduce :
public LoopPass {
6515 LoopStrengthReduce();
6518 bool runOnLoop(
Loop *L, LPPassManager &LPM)
override;
6519 void getAnalysisUsage(AnalysisUsage &AU)
const override;
6524LoopStrengthReduce::LoopStrengthReduce() : LoopPass(
ID) {
6528void LoopStrengthReduce::getAnalysisUsage(
AnalysisUsage &AU)
const {
6555ToDwarfOpIter(SmallVectorImpl<uint64_t> &Expr) {
6556 llvm::DIExpression::expr_op_iterator Begin =
6557 llvm::DIExpression::expr_op_iterator(Expr.
begin());
6558 llvm::DIExpression::expr_op_iterator
End =
6559 llvm::DIExpression::expr_op_iterator(Expr.
end());
6560 return {Begin,
End};
6563struct SCEVDbgValueBuilder {
6564 SCEVDbgValueBuilder() =
default;
6565 SCEVDbgValueBuilder(
const SCEVDbgValueBuilder &
Base) { clone(
Base); }
6567 void clone(
const SCEVDbgValueBuilder &
Base) {
6568 LocationOps =
Base.LocationOps;
6573 LocationOps.
clear();
6580 SmallVector<Value *, 2> LocationOps;
6590 unsigned ArgIndex = 0;
6591 if (It != LocationOps.
end()) {
6592 ArgIndex = std::distance(LocationOps.
begin(), It);
6594 ArgIndex = LocationOps.
size();
6600 void pushValue(
const SCEVUnknown *U) {
6605 bool pushConst(
const SCEVConstant *
C) {
6606 if (
C->getAPInt().getSignificantBits() > 64)
6608 Expr.
push_back(llvm::dwarf::DW_OP_consts);
6609 Expr.
push_back(
C->getAPInt().getSExtValue());
6616 return ToDwarfOpIter(Expr);
6621 bool pushArithmeticExpr(
const llvm::SCEVCommutativeExpr *CommExpr,
6624 "Expected arithmetic SCEV type");
6626 unsigned EmitOperator = 0;
6627 for (
const auto &
Op : CommExpr->
operands()) {
6630 if (EmitOperator >= 1)
6631 pushOperator(DwarfOp);
6638 bool pushCast(
const llvm::SCEVCastExpr *
C,
bool IsSigned) {
6639 const llvm::SCEV *Inner =
C->getOperand(0);
6640 const llvm::Type *
Type =
C->getType();
6642 bool Success = pushSCEV(Inner);
6644 IsSigned ? llvm::dwarf::DW_ATE_signed
6645 : llvm::dwarf::DW_ATE_unsigned};
6646 for (
const auto &
Op : CastOps)
6652 bool pushSCEV(
const llvm::SCEV *S) {
6655 Success &= pushConst(StartInt);
6660 pushLocation(
U->getValue());
6663 Success &= pushArithmeticExpr(MulRec, llvm::dwarf::DW_OP_mul);
6666 Success &= pushSCEV(UDiv->getLHS());
6667 Success &= pushSCEV(UDiv->getRHS());
6668 pushOperator(llvm::dwarf::DW_OP_div);
6674 "Unexpected cast type in SCEV.");
6678 Success &= pushArithmeticExpr(AddExpr, llvm::dwarf::DW_OP_plus);
6693 bool isIdentityFunction(
uint64_t Op,
const SCEV *S) {
6695 if (
C->getAPInt().getSignificantBits() > 64)
6697 int64_t
I =
C->getAPInt().getSExtValue();
6699 case llvm::dwarf::DW_OP_plus:
6700 case llvm::dwarf::DW_OP_minus:
6702 case llvm::dwarf::DW_OP_mul:
6703 case llvm::dwarf::DW_OP_div:
6716 bool SCEVToValueExpr(
const llvm::SCEVAddRecExpr &SAR, ScalarEvolution &SE) {
6722 if (!isIdentityFunction(llvm::dwarf::DW_OP_mul, Stride)) {
6723 if (!pushSCEV(Stride))
6725 pushOperator(llvm::dwarf::DW_OP_mul);
6727 if (!isIdentityFunction(llvm::dwarf::DW_OP_plus, Start)) {
6728 if (!pushSCEV(Start))
6730 pushOperator(llvm::dwarf::DW_OP_plus);
6736 void createOffsetExpr(int64_t
Offset,
Value *OffsetValue) {
6737 pushLocation(OffsetValue);
6740 dbgs() <<
"scev-salvage: Generated IV offset expression. Offset: "
6741 << std::to_string(
Offset) <<
"\n");
6747 bool createIterCountExpr(
const SCEV *S,
6748 const SCEVDbgValueBuilder &IterationCount,
6749 ScalarEvolution &SE) {
6758 LLVM_DEBUG(
dbgs() <<
"scev-salvage: Location to salvage SCEV: " << *S
6762 if (!Rec->isAffine())
6770 clone(IterationCount);
6771 if (!SCEVToValueExpr(*Rec, SE))
6782 bool SCEVToIterCountExpr(
const llvm::SCEVAddRecExpr &SAR,
6783 ScalarEvolution &SE) {
6789 if (!isIdentityFunction(llvm::dwarf::DW_OP_minus, Start)) {
6790 if (!pushSCEV(Start))
6792 pushOperator(llvm::dwarf::DW_OP_minus);
6794 if (!isIdentityFunction(llvm::dwarf::DW_OP_div, Stride)) {
6795 if (!pushSCEV(Stride))
6797 pushOperator(llvm::dwarf::DW_OP_div);
6805 void appendToVectors(SmallVectorImpl<uint64_t> &DestExpr,
6806 SmallVectorImpl<Value *> &DestLocations) {
6808 "Expected the locations vector to contain the IV");
6813 "Expected the location ops to contain the IV.");
6817 for (
const auto &
Op : LocationOps) {
6818 auto It =
find(DestLocations,
Op);
6819 if (It != DestLocations.
end()) {
6821 DestIndexMap.
push_back(std::distance(DestLocations.
begin(), It));
6829 for (
const auto &
Op : expr_ops()) {
6832 Op.appendToVector(DestExpr);
6839 uint64_t NewIndex = DestIndexMap[Arg.getIndex()];
6847struct DVIRecoveryRec {
6848 DVIRecoveryRec(DbgVariableRecord *DVR)
6849 : DbgRef(DVR), Expr(DVR->getExpression()), HadLocationArgList(
false) {}
6851 DbgVariableRecord *DbgRef;
6853 bool HadLocationArgList;
6859 for (
auto &RE : RecoveryExprs)
6861 RecoveryExprs.clear();
6864 ~DVIRecoveryRec() { clear(); }
6872 auto expr_ops = ToDwarfOpIter(Expr);
6874 for (
auto Op : expr_ops)
6883template <
typename T>
6887 "contain any DW_OP_llvm_arg operands.");
6893template <
typename T>
6898 "Expected expression that references DIArglist locations using "
6899 "DW_OP_llvm_arg operands.");
6901 for (
Value *
V : Locations)
6918 if (NumLLVMArgs == 0) {
6925 "Lone LLVM_arg in a DIExpression should refer to location-op 0.");
6955 LLVM_DEBUG(
dbgs() <<
"scev-salvage: restore dbg.value to pre-LSR state\n"
6956 <<
"scev-salvage: post-LSR: " << *DbgVal <<
'\n');
6957 assert(DVIRec.Expr &&
"Expected an expression");
6962 if (!DVIRec.HadLocationArgList) {
6963 assert(DVIRec.LocationOps.size() == 1 &&
6964 "Unexpected number of location ops.");
6968 Value *CachedValue =
6973 for (
WeakVH VH : DVIRec.LocationOps) {
6981 LLVM_DEBUG(
dbgs() <<
"scev-salvage: pre-LSR: " << *DbgVal <<
'\n');
6986 const SCEV *SCEVInductionVar,
6987 SCEVDbgValueBuilder IterCountExpr) {
7001 LocationOpIndexMap.
assign(DVIRec.LocationOps.size(), -1);
7003 NewLocationOps.
push_back(LSRInductionVar);
7005 for (
unsigned i = 0; i < DVIRec.LocationOps.size(); i++) {
7006 WeakVH VH = DVIRec.LocationOps[i];
7012 LocationOpIndexMap[i] = NewLocationOps.
size() - 1;
7014 <<
" now at index " << LocationOpIndexMap[i] <<
"\n");
7022 LLVM_DEBUG(
dbgs() <<
"scev-salvage: SCEV for location at index: " << i
7023 <<
" refers to a location that is now undef or erased. "
7024 "Salvage abandoned.\n");
7028 LLVM_DEBUG(
dbgs() <<
"scev-salvage: salvaging location at index " << i
7029 <<
" with SCEV: " << *DVIRec.SCEVs[i] <<
"\n");
7031 DVIRec.RecoveryExprs[i] = std::make_unique<SCEVDbgValueBuilder>();
7032 SCEVDbgValueBuilder *SalvageExpr = DVIRec.RecoveryExprs[i].get();
7036 if (std::optional<APInt>
Offset =
7038 if (
Offset->getSignificantBits() <= 64)
7039 SalvageExpr->createOffsetExpr(
Offset->getSExtValue(), LSRInductionVar);
7042 }
else if (!SalvageExpr->createIterCountExpr(DVIRec.SCEVs[i], IterCountExpr,
7051 assert(DVIRec.RecoveryExprs.size() == 1 &&
7052 "Expected only a single recovery expression for an empty "
7054 assert(DVIRec.RecoveryExprs[0] &&
7055 "Expected a SCEVDbgSalvageBuilder for location 0");
7056 SCEVDbgValueBuilder *
B = DVIRec.RecoveryExprs[0].get();
7057 B->appendToVectors(
NewExpr, NewLocationOps);
7059 for (
const auto &
Op : DVIRec.Expr->
expr_ops()) {
7067 uint64_t LocationArgIndex = Arg.getIndex();
7068 SCEVDbgValueBuilder *DbgBuilder =
7069 DVIRec.RecoveryExprs[LocationArgIndex].get();
7075 assert(LocationOpIndexMap[LocationArgIndex] != -1 &&
7076 "Expected a positive index for the location-op position.");
7077 NewExpr.push_back(LocationOpIndexMap[LocationArgIndex]);
7081 DbgBuilder->appendToVectors(
NewExpr, NewLocationOps);
7085 LLVM_DEBUG(
dbgs() <<
"scev-salvage: Updated DVI: " << *DVIRec.DbgRef <<
"\n");
7093 SmallVector<std::unique_ptr<DVIRecoveryRec>, 2> &DVIToUpdate) {
7094 if (DVIToUpdate.empty())
7098 assert(SCEVInductionVar &&
7099 "Anticipated a SCEV for the post-LSR induction variable");
7103 if (!IVAddRec->isAffine())
7111 SCEVDbgValueBuilder IterCountExpr;
7112 IterCountExpr.pushLocation(LSRInductionVar);
7113 if (!IterCountExpr.SCEVToIterCountExpr(*IVAddRec, SE))
7116 LLVM_DEBUG(
dbgs() <<
"scev-salvage: IV SCEV: " << *SCEVInductionVar
7119 for (
auto &DVIRec : DVIToUpdate) {
7120 SalvageDVI(L, SE, LSRInductionVar, *DVIRec, SCEVInductionVar,
7131 SmallVector<std::unique_ptr<DVIRecoveryRec>, 2> &SalvageableDVISCEVs) {
7132 for (
const auto &
B : L->getBlocks()) {
7133 for (
auto &
I : *
B) {
7135 if (!DbgVal.isDbgValue() && !DbgVal.isDbgAssign())
7140 if (DbgVal.isKillLocation())
7145 const auto &HasTranslatableLocationOps =
7147 for (
const auto LocOp : DbgValToTranslate.location_ops()) {
7161 if (!HasTranslatableLocationOps(DbgVal))
7164 std::unique_ptr<DVIRecoveryRec> NewRec =
7165 std::make_unique<DVIRecoveryRec>(&DbgVal);
7169 NewRec->RecoveryExprs.resize(DbgVal.getNumVariableLocationOps());
7170 for (
const auto LocOp : DbgVal.location_ops()) {
7171 NewRec->SCEVs.push_back(SE.
getSCEV(LocOp));
7172 NewRec->LocationOps.push_back(LocOp);
7173 NewRec->HadLocationArgList = DbgVal.hasArgList();
7175 SalvageableDVISCEVs.push_back(std::move(NewRec));
7185 const LSRInstance &LSR) {
7187 auto IsSuitableIV = [&](
PHINode *
P) {
7198 for (
const WeakVH &
IV : LSR.getScalarEvolutionIVs()) {
7205 if (IsSuitableIV(
P))
7209 for (
PHINode &
P : L.getHeader()->phis()) {
7210 if (IsSuitableIV(&
P))
7229 std::unique_ptr<MemorySSAUpdater> MSSAU;
7231 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
7234 const LSRInstance &Reducer = LSRInstance(Opts, L, IU, SE, DT, LI,
TTI, AC,
7235 TLI, MSSAU.get(), PreserveLCSSA);
7236 Changed |= Reducer.getChanged();
7240 if (Opts.enable_lsr_phielim && L->isLoopSimplifyForm()) {
7243#if LLVM_ENABLE_ABI_BREAKING_CHECKS
7246 unsigned numFolded = Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, &
TTI);
7260 L->getUniqueExitBlocks(ExitBlocks);
7269 if (L->isRecursivelyLCSSAForm(DT, LI) && L->getExitBlock()) {
7283 if (SalvageableDVIRecords.
empty())
7289 for (
const auto &L : LI) {
7293 LLVM_DEBUG(
dbgs() <<
"scev-salvage: SCEV salvaging not possible. An IV "
7294 "could not be identified.\n");
7298 for (
auto &Rec : SalvageableDVIRecords)
7300 SalvageableDVIRecords.
clear();
7304bool LoopStrengthReduce::runOnLoop(
Loop *L, LPPassManager & ) {
7308 auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();
7309 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
7310 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
7311 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
7312 const auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
7313 *
L->getHeader()->getParent());
7314 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
7315 *
L->getHeader()->getParent());
7316 auto &
TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
7317 *
L->getHeader()->getParent());
7318 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
7321 MSSA = &MSSAAnalysis->getMSSA();
7340char LoopStrengthReduce::ID = 0;
7343 "Loop Strength Reduction",
false,
false)
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AArch64 Predicate As Counter Loop Rewrites
const AArch64InstrInfo MachineBasicBlock::iterator InsertPt
This file implements a class to represent arbitrary precision integral constant values and operations...
Function Alias Analysis false
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static bool isAddressUse(const Use &U)
The use is the address of the function as a value.
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file contains constants used for implementing Dwarf debug support.
early cse Early CSE w MemorySSA
Module.h This file contains the declarations for the Module class.
This defines the Use class.
iv Induction Variable Users
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
This header provides classes for managing per-loop analyses.
static bool SalvageDVI(llvm::Loop *L, ScalarEvolution &SE, llvm::PHINode *LSRInductionVar, DVIRecoveryRec &DVIRec, const SCEV *SCEVInductionVar, SCEVDbgValueBuilder IterCountExpr)
static Value * getWideOperand(Value *Oper)
IVChain logic must consistently peek base TruncInst operands, so wrap it in a convenient helper.
static bool isAddSExtable(const SCEVAddExpr *A, ScalarEvolution &SE)
Return true if the given add can be sign-extended without changing its value.
static bool stressIVChain(const ScalarOptions &Opts)
static bool mayUsePostIncMode(const TargetTransformInfo &TTI, LSRUse &LU, const SCEV *S, const Loop *L, ScalarEvolution &SE)
Return true if the SCEV represents a value that may end up as a post-increment operation.
static void restorePreTransformState(DVIRecoveryRec &DVIRec)
Restore the DVI's pre-LSR arguments. Substitute undef for any erased values.
static bool containsAddRecDependentOnLoop(const SCEV *S, const Loop &L)
static User::op_iterator findIVOperand(User::op_iterator OI, User::op_iterator OE, Loop *L, ScalarEvolution &SE)
Helper for CollectChains that finds an IV operand (computed by an AddRec in this loop) within [OI,...
static bool isLegalUse(const TargetTransformInfo &TTI, Immediate MinOffset, Immediate MaxOffset, LSRUse::KindType Kind, MemAccessTy AccessTy, GlobalValue *BaseGV, Immediate BaseOffset, bool HasBaseReg, int64_t Scale)
Test whether we know how to expand the current formula.
static void DbgGatherSalvagableDVI(Loop *L, ScalarEvolution &SE, SmallVector< std::unique_ptr< DVIRecoveryRec >, 2 > &SalvageableDVISCEVs)
Identify and cache salvageable DVI locations and expressions along with the corresponding SCEV(s).
static bool isMulSExtable(const SCEVMulExpr *M, ScalarEvolution &SE)
Return true if the given mul can be sign-extended without changing its value.
static const unsigned MaxSCEVSalvageExpressionSize
Limit the size of expression that SCEV-based salvaging will attempt to translate into a DIExpression.
static bool isExistingPhi(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Return true if this AddRec is already a phi in its loop.
static InstructionCost getScalingFactorCost(const TargetTransformInfo &TTI, const LSRUse &LU, const Formula &F, const Loop &L)
static void DoInitialMatch(const SCEV *S, Loop *L, SmallVectorImpl< SCEVUse > &Good, SmallVectorImpl< SCEVUse > &Bad, ScalarEvolution &SE)
Recursion helper for initialMatch.
static void updateDVIWithLocation(T &DbgVal, Value *Location, SmallVectorImpl< uint64_t > &Ops)
Overwrites DVI with the location and Ops as the DIExpression.
static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI, const TargetTransformInfo &TTI, AssumptionCache &AC, TargetLibraryInfo &TLI, MemorySSA *MSSA, bool PreserveLCSSA)
static bool isLegalAddImmediate(const TargetTransformInfo &TTI, Immediate Offset)
static Instruction * getFixupInsertPos(const TargetTransformInfo &TTI, const LSRFixup &Fixup, const LSRUse &LU, Instruction *IVIncInsertPos, DominatorTree &DT)
static const SCEV * getExprBase(const SCEV *S)
Return an approximation of this SCEV expression's "base", or NULL for any constant.
static llvm::PHINode * GetInductionVariable(const Loop &L, ScalarEvolution &SE, const LSRInstance &LSR)
Ideally pick the PHI IV inserted by ScalarEvolutionExpander.
static bool IsSimplerBaseSCEVForTarget(const TargetTransformInfo &TTI, ScalarEvolution &SE, const SCEV *Best, const SCEV *Reg, MemAccessTy AccessType)
static const unsigned MaxIVUsers
MaxIVUsers is an arbitrary threshold that provides an early opportunity for bail out.
static Immediate extractImmediate(const ScalarOptions &Opts, SCEVUse &S, ScalarEvolution &SE, bool PreferScalable=false)
If S involves the addition of a constant integer value, return that integer value,...
static bool isHighCostExpansion(const SCEV *S, SmallPtrSetImpl< const SCEV * > &Processed, ScalarEvolution &SE)
Check if expanding this expression is likely to incur significant cost.
static Value * getValueOrPoison(WeakVH &VH, LLVMContext &C)
Cached location ops may be erased during LSR, in which case a poison is required when restoring from ...
static MemAccessTy getAccessType(const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
Return the type of the memory being accessed.
static unsigned numLLVMArgOps(SmallVectorImpl< uint64_t > &Expr)
Returns the total number of DW_OP_llvm_arg operands in the expression.
static bool isAlwaysFoldable(const ScalarOptions &Opts, const TargetTransformInfo &TTI, LSRUse::KindType Kind, MemAccessTy AccessTy, GlobalValue *BaseGV, Immediate BaseOffset, bool HasBaseReg)
static void DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE, llvm::PHINode *LSRInductionVar, SmallVector< std::unique_ptr< DVIRecoveryRec >, 2 > &DVIToUpdate)
Obtain an expression for the iteration count, then attempt to salvage the dbg.value intrinsics.
static void UpdateDbgValue(DVIRecoveryRec &DVIRec, SmallVectorImpl< Value * > &NewLocationOps, SmallVectorImpl< uint64_t > &NewExpr)
Write the new expression and new location ops for the dbg.value.
static bool isAddRecSExtable(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Return true if the given addrec can be sign-extended without changing its value.
static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, const LSRUse &LU, const Formula &F)
Check if the addressing mode defined by F is completely folded in LU at isel time.
static Immediate extractImmediateOperand(const ScalarOptions &Opts, MutableArrayRef< SCEVUse > Ops, ScalarEvolution &SE, bool PreferScalable)
Extracts an immediate operand from Ops and replaces the operand with zero.
static void updateDVIWithLocations(T &DbgVal, SmallVectorImpl< Value * > &Locations, SmallVectorImpl< uint64_t > &Ops)
Overwrite DVI with locations placed into a DIArglist.
static bool canFoldIVIncExpr(const ScalarOptions &Opts, const SCEV *IncExpr, Instruction *UserInst, Value *Operand, const TargetTransformInfo &TTI)
Return true if the IVInc can be folded into an addressing mode.
static GlobalValue * ExtractSymbol(SCEVUse &S, ScalarEvolution &SE)
If S involves the addition of a GlobalValue address, return that symbol, and mutate S to point to a n...
static bool isProfitableChain(IVChain &Chain, SmallPtrSetImpl< Instruction * > &Users, ScalarEvolution &SE, const TargetTransformInfo &TTI)
Return true if the number of registers needed for the chain is estimated to be less than the number r...
static const SCEV * CollectSubexprs(const SCEV *S, const SCEVConstant *C, SmallVectorImpl< const SCEV * > &Ops, const Loop *L, ScalarEvolution &SE, unsigned Depth=0)
Split S into subexpressions which can be pulled out into separate registers.
static const SCEV * getExactSDiv(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE, bool IgnoreSignificantBits=false)
Return an expression for LHS /s RHS, if it can be determined and if the remainder is known to be zero...
static const SCEV * getAnyExtendConsideringPostIncUses(ArrayRef< PostIncLoopSet > Loops, const SCEV *Expr, Type *ToTy, ScalarEvolution &SE)
Extend/Truncate Expr to ToTy considering post-inc uses in Loops.
static unsigned getSetupCost(const SCEV *Reg, unsigned Depth, const TargetTransformInfo &TTI)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the PointerIntPair class.
SmallVector< MachineOperand, 4 > Cond
Remove Loads Into Fake Uses
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
This file implements a set that has insertion order iteration characteristics.
This file implements the SmallBitVector class.
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
static SymbolRef::Type getType(const Symbol *Sym)
virt reg Virtual Register Rewriter
static const uint32_t IV[8]
Class for arbitrary precision integers.
uint64_t getZExtValue() const
Get zero extended value.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isNegative() const
Determine sign of this APInt.
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
unsigned countr_zero() const
Count the number of trailing zero bits.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
LLVM_ABI APInt srem(const APInt &RHS) const
Function for signed remainder operation.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
int64_t getSExtValue() const
Get sign extended value.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
An instruction that atomically checks whether a specified value is in a memory location,...
an instruction that atomically reads a memory location, combines it with another value,...
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
InstListType::iterator iterator
Instruction iterators...
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
BinaryOps getOpcode() const
static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
static LLVM_ABI Instruction::CastOps getCastOpcode(const Value *Val, bool SrcIsSigned, Type *Ty, bool DstIsSigned)
Returns the opcode necessary to cast Val into Ty using usual casting rules.
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Value * getCondition() const
static LLVM_ABI bool isValueValidForType(Type *Ty, uint64_t V)
This static method returns true if the type Ty is big enough to represent the value V.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
static LLVM_ABI DIArgList * get(LLVMContext &Context, ArrayRef< ValueAsMetadata * > Args)
iterator_range< expr_op_iterator > expr_ops() const
static LLVM_ABI DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)
Append the opcodes Ops to DIExpr.
unsigned getNumElements() const
static LLVM_ABI void appendOffset(SmallVectorImpl< uint64_t > &Ops, int64_t Offset)
Append Ops with operations to apply the Offset.
LLVM_ABI bool isComplex() const
Return whether the location is computed on the expression stack, meaning it cannot be a simple regist...
LLVM_ABI LLVMContext & getContext()
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LLVM_ABI bool isKillLocation() const
void setRawLocation(Metadata *NewLocation)
Use of this should generally be avoided; instead, replaceVariableLocationOp and addVariableLocationOp...
void setExpression(DIExpression *NewExpr)
DIExpression * getExpression() const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
PointerType * getType() const
Global values are always pointers.
IVStrideUse - Keep track of one use of a strided induction variable.
void transformToPostInc(const Loop *L)
transformToPostInc - Transform the expression to post-inc form for the given loop.
Value * getOperandValToReplace() const
getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...
void setUser(Instruction *NewUser)
setUser - Assign a new user instruction for this use.
Analysis pass that exposes the IVUsers for a loop.
ilist< IVStrideUse >::const_iterator const_iterator
LLVM_ABI void print(raw_ostream &OS) const
CostType getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
LLVM_ABI bool isLifetimeStartOrEnd() const LLVM_READONLY
Return true if the instruction is a llvm.lifetime.start or llvm.lifetime.end marker.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI Type * getAccessType() const LLVM_READONLY
Return the type this instruction accesses in memory, if any.
iterator_range< user_iterator > users()
const char * getOpcodeName() const
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
An instruction for reading from memory.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
The legacy pass manager's analysis pass to compute loop information.
LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
An analysis that produces MemorySSA for a function.
Encapsulates MemorySSA, including all data associated with memory accesses.
Represent a mutable reference to an array (0 or more elements consecutively in memory),...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
static unsigned getIncomingValueNumForOperand(unsigned i)
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This class uses information about analyze scalars to rewrite expressions in canonical form.
This node represents multiplication of some number of SCEVs.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
bool hasNoSignedWrap() const
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
unsigned short getExpressionSize() const
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Type * getType() const
Return the LLVM type of this SCEV expression.
static constexpr auto FlagNone
SCEVTypes getSCEVType() const
The main scalar evolution driver.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlagsPair Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEV * getAnyExtendExpr(SCEVUse Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI const SCEV * getSignExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
LLVMContext & getContext() const
size_type size() const
Determine the number of elements in the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
iterator_range< const_set_bits_iterator > set_bits() const
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
size_type size() const
Returns the number of bits in this bitvector.
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
size_type count() const
Returns the number of bits which are set.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
typename SuperClass::const_iterator const_iterator
typename SuperClass::iterator iterator
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static StackOffset get(int64_t Fixed, int64_t Scalable)
An instruction for storing to memory.
Provides information about what library functions are available for the current target.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
LLVM_ABI bool isScalableTy() const
Return true if this is a type whose size is a known multiple of vscale.
LLVM_ABI int getFPMantissaWidth() const
Return the width of the mantissa of this type.
bool isVoidTy() const
Return true if this is 'void'.
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
iterator_range< use_iterator > uses()
A nullable Value handle that is nullable.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
const ParentTy * getParent() const
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ BasicBlock
Various leaf nodes.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
bool match(const SCEV *S, const Pattern &P)
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
cst_pred_ty< is_specific_cst > m_scev_SpecificInt(uint64_t V)
Match an SCEV constant with a plain unsigned integer.
@ DW_OP_LLVM_arg
Only used in LLVM metadata.
@ DW_OP_LLVM_convert
Only used in LLVM metadata.
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
friend class Instruction
Iterator for Instructions in a `BasicBlock.
LLVM_ABI iterator begin() const
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
unsigned KindType
For isa, dyn_cast, etc operations on TelemetryInfo.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
@ Store
The extracted value is stored (ExtractElement only).
bool operator!=(uint64_t V1, const APInt &V2)
LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, SmallPtrSetImpl< PHINode * > *KnownNonDeadPHIs=nullptr)
Examine each PHI in the given block and delete it if it is dead.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
const ScalarOptions & getScalarOptions(const LLVMContext &C)
LLVM_ABI char & LoopSimplifyID
bool isa_and_nonnull(const Y &Val)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
DomTreeNodeBase< BasicBlock > DomTreeNode
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI void initializeLoopStrengthReducePass(PassRegistry &)
auto reverse(ContainerTy &&C)
LLVM_ABI const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE, bool CheckInvertible=true)
Normalize S to be post-increment for all loops present in Loops.
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
LLVM_ABI Pass * createLoopStrengthReducePass()
LLVM_ABI BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructionsPermissive(SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow instructions that are not...
constexpr unsigned BitWidth
LLVM_ABI bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
SmallPtrSet< const Loop *, 2 > PostIncLoopSet
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
constexpr bool valueOr(BoolOrDefault X, bool Default)
@ End
Run the machine verifier once, at the end of the pipeline.
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Attributes of a target dependent hardware loop.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
Information about a load/store intrinsic defined by the target.
Value * PtrVal
This is the pointer that the intrinsic is loading from or storing to.
SCEVPtrT getPointer() const