71#define DEBUG_TYPE "loop-fusion"
74STATISTIC(NumFusionCandidates,
"Number of candidates for loop fusion");
75STATISTIC(InvalidPreheader,
"Loop has invalid preheader");
77STATISTIC(InvalidExitingBlock,
"Loop has invalid exiting blocks");
78STATISTIC(InvalidExitBlock,
"Loop has invalid exit block");
81STATISTIC(AddressTakenBB,
"Basic block has address taken");
82STATISTIC(MayThrowException,
"Loop may throw an exception");
83STATISTIC(ContainsVolatileAccess,
"Loop contains a volatile access");
84STATISTIC(NotSimplifiedForm,
"Loop is not in simplified form");
85STATISTIC(InvalidDependencies,
"Dependencies prevent fusion");
86STATISTIC(UnknownTripCount,
"Loop has unknown trip count");
87STATISTIC(UncomputableTripCount,
"SCEV cannot compute trip count of loop");
88STATISTIC(NonEqualTripCount,
"Loop trip counts are not the same");
92 "Loop has a non-empty preheader with instructions that cannot be moved");
93STATISTIC(FusionNotBeneficial,
"Fusion is not beneficial");
94STATISTIC(NonIdenticalGuards,
"Candidates have different guards");
95STATISTIC(NonEmptyExitBlock,
"Candidate has a non-empty exit block with "
96 "instructions that cannot be moved");
97STATISTIC(NonEmptyGuardBlock,
"Candidate has a non-empty guard block with "
98 "instructions that cannot be moved");
101 "The second candidate is guarded while the first one is not");
102STATISTIC(NumHoistedInsts,
"Number of hoisted preheader instructions.");
103STATISTIC(NumSunkInsts,
"Number of hoisted preheader instructions.");
112 "loop-fusion-dependence-analysis",
113 cl::desc(
"Which dependence analysis should loop fusion use?"),
115 "Use the scalar evolution interface"),
117 "Use the dependence analysis interface"),
119 "Use all available analyses")),
124 cl::desc(
"Max number of iterations to be peeled from a loop, such that "
125 "fusion can take place"));
130 cl::desc(
"Enable verbose debugging for Loop Fusion"),
145struct FusionCandidate {
188 : Preheader(L->getLoopPreheader()), Header(L->getHeader()),
189 ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()),
190 Latch(L->getLoopLatch()), L(L), Valid(
true),
191 GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(
canPeel(L)),
192 Peeled(
false), DT(DT), PDT(PDT), ORE(ORE) {
199 if (BB->hasAddressTaken()) {
211 if (
StoreInst *SI = dyn_cast<StoreInst>(&
I)) {
212 if (
SI->isVolatile()) {
218 if (
LoadInst *LI = dyn_cast<LoadInst>(&
I)) {
219 if (LI->isVolatile()) {
225 if (
I.mayWriteToMemory())
227 if (
I.mayReadFromMemory())
235 return Preheader && Header && ExitingBlock && ExitBlock && Latch &&
L &&
236 !
L->isInvalid() && Valid;
242 assert(!
L->isInvalid() &&
"Loop is invalid!");
243 assert(Preheader ==
L->getLoopPreheader() &&
"Preheader is out of sync");
244 assert(Header ==
L->getHeader() &&
"Header is out of sync");
245 assert(ExitingBlock ==
L->getExitingBlock() &&
246 "Exiting Blocks is out of sync");
247 assert(ExitBlock ==
L->getExitBlock() &&
"Exit block is out of sync");
248 assert(Latch ==
L->getLoopLatch() &&
"Latch is out of sync");
265 void updateAfterPeeling() {
266 Preheader =
L->getLoopPreheader();
267 Header =
L->getHeader();
268 ExitingBlock =
L->getExitingBlock();
269 ExitBlock =
L->getExitBlock();
270 Latch =
L->getLoopLatch();
282 assert(GuardBranch &&
"Only valid on guarded loops.");
284 "Expecting guard to be a conditional branch.");
292#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
294 dbgs() <<
"\tGuardBranch: ";
296 dbgs() << *GuardBranch;
300 << (GuardBranch ? GuardBranch->
getName() :
"nullptr") <<
"\n"
301 <<
"\tPreheader: " << (Preheader ? Preheader->
getName() :
"nullptr")
303 <<
"\tHeader: " << (Header ? Header->getName() :
"nullptr") <<
"\n"
305 << (ExitingBlock ? ExitingBlock->
getName() :
"nullptr") <<
"\n"
306 <<
"\tExitBB: " << (ExitBlock ? ExitBlock->
getName() :
"nullptr")
308 <<
"\tLatch: " << (Latch ? Latch->
getName() :
"nullptr") <<
"\n"
310 << (getEntryBlock() ? getEntryBlock()->getName() :
"nullptr")
326 ++InvalidExitingBlock;
340 <<
" trip count not computable!\n");
344 if (!
L->isLoopSimplifyForm()) {
346 <<
" is not in simplified form!\n");
350 if (!
L->isRotatedForm()) {
373 assert(L && Preheader &&
"Fusion candidate not initialized properly!");
377 L->getStartLoc(), Preheader)
379 <<
"Loop is not a candidate for fusion: " << Stat.getDesc());
385struct FusionCandidateCompare {
396 bool operator()(
const FusionCandidate &LHS,
397 const FusionCandidate &RHS)
const {
405 assert(DT &&
LHS.PDT &&
"Expecting valid dominator tree");
408 if (DT->
dominates(RHSEntryBlock, LHSEntryBlock)) {
411 assert(
LHS.PDT->dominates(LHSEntryBlock, RHSEntryBlock));
415 if (DT->
dominates(LHSEntryBlock, RHSEntryBlock)) {
417 assert(
LHS.PDT->dominates(RHSEntryBlock, LHSEntryBlock));
429 if (WrongOrder && RightOrder) {
436 }
else if (WrongOrder)
445 "No dominance relationship between these fusion candidates!");
461using FusionCandidateSet = std::set<FusionCandidate, FusionCandidateCompare>;
466 const FusionCandidate &FC) {
468 OS <<
FC.Preheader->getName();
476 const FusionCandidateSet &CandSet) {
477 for (
const FusionCandidate &FC : CandSet)
484printFusionCandidates(
const FusionCandidateCollection &FusionCandidates) {
485 dbgs() <<
"Fusion Candidates: \n";
486 for (
const auto &CandidateSet : FusionCandidates) {
487 dbgs() <<
"*** Fusion Candidate Set ***\n";
488 dbgs() << CandidateSet;
489 dbgs() <<
"****************************\n";
500struct LoopDepthTree {
507 LoopsOnLevel.emplace_back(LoopVector(LI.
rbegin(), LI.
rend()));
512 bool isRemovedLoop(
const Loop *L)
const {
return RemovedLoops.count(L); }
516 void removeLoop(
const Loop *L) { RemovedLoops.insert(L); }
520 LoopsOnLevelTy LoopsOnNextLevel;
522 for (
const LoopVector &LV : *
this)
524 if (!isRemovedLoop(L) &&
L->begin() !=
L->end())
525 LoopsOnNextLevel.emplace_back(LoopVector(
L->begin(),
L->end()));
527 LoopsOnLevel = LoopsOnNextLevel;
528 RemovedLoops.clear();
532 bool empty()
const {
return size() == 0; }
533 size_t size()
const {
return LoopsOnLevel.size() - RemovedLoops.size(); }
534 unsigned getDepth()
const {
return Depth; }
536 iterator
begin() {
return LoopsOnLevel.begin(); }
537 iterator
end() {
return LoopsOnLevel.end(); }
550 LoopsOnLevelTy LoopsOnLevel;
554static void printLoopVector(
const LoopVector &LV) {
555 dbgs() <<
"****************************\n";
558 dbgs() <<
"****************************\n";
565 FusionCandidateCollection FusionCandidates;
584 : LDT(LI), DTU(DT, PDT,
DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
585 DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE), AC(AC),
TTI(
TTI) {}
597 LLVM_DEBUG(
dbgs() <<
"Performing Loop Fusion on function " <<
F.getName()
599 bool Changed =
false;
601 while (!LDT.empty()) {
602 LLVM_DEBUG(
dbgs() <<
"Got " << LDT.size() <<
" loop sets for depth "
603 << LDT.getDepth() <<
"\n";);
605 for (
const LoopVector &LV : LDT) {
606 assert(LV.size() > 0 &&
"Empty loop set was build!");
615 dbgs() <<
" Visit loop set (#" << LV.size() <<
"):\n";
621 collectFusionCandidates(LV);
622 Changed |= fuseCandidates();
633 FusionCandidates.clear();
658 const FusionCandidate &FC1)
const {
659 assert(FC0.Preheader && FC1.Preheader &&
"Expecting valid preheaders");
661 return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
668 void collectFusionCandidates(
const LoopVector &LV) {
672 FusionCandidate CurrCand(L, DT, &PDT, ORE, PP);
673 if (!CurrCand.isEligibleForFusion(SE))
681 bool FoundSet =
false;
683 for (
auto &CurrCandSet : FusionCandidates) {
685 CurrCandSet.insert(CurrCand);
690 <<
" to existing candidate set\n");
701 FusionCandidateSet NewCandSet;
702 NewCandSet.insert(CurrCand);
703 FusionCandidates.push_back(NewCandSet);
705 NumFusionCandidates++;
714 bool isBeneficialFusion(
const FusionCandidate &FC0,
715 const FusionCandidate &FC1) {
727 std::pair<bool, std::optional<unsigned>>
728 haveIdenticalTripCounts(
const FusionCandidate &FC0,
729 const FusionCandidate &FC1)
const {
731 if (isa<SCEVCouldNotCompute>(TripCount0)) {
732 UncomputableTripCount++;
733 LLVM_DEBUG(
dbgs() <<
"Trip count of first loop could not be computed!");
734 return {
false, std::nullopt};
738 if (isa<SCEVCouldNotCompute>(TripCount1)) {
739 UncomputableTripCount++;
740 LLVM_DEBUG(
dbgs() <<
"Trip count of second loop could not be computed!");
741 return {
false, std::nullopt};
745 << *TripCount1 <<
" are "
746 << (TripCount0 == TripCount1 ?
"identical" :
"different")
749 if (TripCount0 == TripCount1)
753 "determining the difference between trip counts\n");
762 if (TC0 == 0 || TC1 == 0) {
763 LLVM_DEBUG(
dbgs() <<
"Loop(s) do not have a single exit point or do not "
764 "have a constant number of iterations. Peeling "
765 "is not benefical\n");
766 return {
false, std::nullopt};
769 std::optional<unsigned> Difference;
770 int Diff = TC0 - TC1;
776 dbgs() <<
"Difference is less than 0. FC1 (second loop) has more "
777 "iterations than the first one. Currently not supported\n");
780 LLVM_DEBUG(
dbgs() <<
"Difference in loop trip count is: " << Difference
783 return {
false, Difference};
786 void peelFusionCandidate(FusionCandidate &FC0,
const FusionCandidate &FC1,
787 unsigned PeelCount) {
788 assert(FC0.AbleToPeel &&
"Should be able to peel loop");
791 <<
" iterations of the first loop. \n");
794 FC0.Peeled =
peelLoop(FC0.L, PeelCount, &LI, &SE, DT, &AC,
true, VMap);
799 auto IdenticalTripCount = haveIdenticalTripCounts(FC0, FC1);
801 assert(IdenticalTripCount.first && *IdenticalTripCount.second == 0 &&
802 "Loops should have identical trip counts after peeling");
805 FC0.PP.PeelCount += PeelCount;
810 FC0.updateAfterPeeling();
826 if (Pred != FC0.ExitBlock) {
835 BasicBlock *Succ = CurrentBranch->getSuccessor(0);
837 Succ = CurrentBranch->getSuccessor(1);
845 dbgs() <<
"Sucessfully peeled " << FC0.PP.PeelCount
846 <<
" iterations from the first loop.\n"
847 "Both Loops have the same number of iterations now.\n");
858 bool fuseCandidates() {
860 LLVM_DEBUG(printFusionCandidates(FusionCandidates));
861 for (
auto &CandidateSet : FusionCandidates) {
862 if (CandidateSet.size() < 2)
866 << CandidateSet <<
"\n");
868 for (
auto FC0 = CandidateSet.begin(); FC0 != CandidateSet.end(); ++FC0) {
869 assert(!LDT.isRemovedLoop(FC0->L) &&
870 "Should not have removed loops in CandidateSet!");
872 for (++FC1; FC1 != CandidateSet.end(); ++FC1) {
873 assert(!LDT.isRemovedLoop(FC1->L) &&
874 "Should not have removed loops in CandidateSet!");
876 LLVM_DEBUG(
dbgs() <<
"Attempting to fuse candidate \n"; FC0->dump();
877 dbgs() <<
" with\n"; FC1->dump();
dbgs() <<
"\n");
887 std::pair<bool, std::optional<unsigned>> IdenticalTripCountRes =
888 haveIdenticalTripCounts(*FC0, *FC1);
889 bool SameTripCount = IdenticalTripCountRes.first;
890 std::optional<unsigned> TCDifference = IdenticalTripCountRes.second;
894 if (FC0->AbleToPeel && !SameTripCount && TCDifference) {
897 <<
"Difference in loop trip counts: " << *TCDifference
898 <<
" is greater than maximum peel count specificed: "
903 SameTripCount =
true;
907 if (!SameTripCount) {
908 LLVM_DEBUG(
dbgs() <<
"Fusion candidates do not have identical trip "
909 "counts. Not fusing.\n");
910 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
915 if (!isAdjacent(*FC0, *FC1)) {
917 <<
"Fusion candidates are not adjacent. Not fusing.\n");
918 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);
922 if ((!FC0->GuardBranch && FC1->GuardBranch) ||
923 (FC0->GuardBranch && !FC1->GuardBranch)) {
925 "another one is not. Not fusing.\n");
926 reportLoopFusion<OptimizationRemarkMissed>(
927 *FC0, *FC1, OnlySecondCandidateIsGuarded);
933 if (FC0->GuardBranch && FC1->GuardBranch &&
934 !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) {
936 "guards. Not Fusing.\n");
937 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
942 if (FC0->GuardBranch) {
943 assert(FC1->GuardBranch &&
"Expecting valid FC1 guard branch");
946 *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
949 "instructions in exit block. Not fusing.\n");
950 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
956 *FC1->GuardBranch->getParent(),
957 *FC0->GuardBranch->getParent()->getTerminator(), DT, &PDT,
960 <<
"Fusion candidate contains unsafe "
961 "instructions in guard block. Not fusing.\n");
962 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
970 if (!dependencesAllowFusion(*FC0, *FC1)) {
971 LLVM_DEBUG(
dbgs() <<
"Memory dependencies do not allow fusion!\n");
972 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
973 InvalidDependencies);
985 if (!isEmptyPreheader(*FC1)) {
991 if (!collectMovablePreheaderInsts(*FC0, *FC1, SafeToHoist,
994 "Fusion Candidate Pre-header.\n"
996 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
1002 bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);
1004 <<
"\tFusion appears to be "
1005 << (BeneficialToFuse ?
"" :
"un") <<
"profitable!\n");
1006 if (!BeneficialToFuse) {
1007 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
1008 FusionNotBeneficial);
1016 movePreheaderInsts(*FC0, *FC1, SafeToHoist, SafeToSink);
1018 LLVM_DEBUG(
dbgs() <<
"\tFusion is performed: " << *FC0 <<
" and "
1021 FusionCandidate FC0Copy = *FC0;
1024 bool Peel = TCDifference && *TCDifference > 0;
1026 peelFusionCandidate(FC0Copy, *FC1, *TCDifference);
1032 reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : *FC0), *FC1,
1035 FusionCandidate FusedCand(
1036 performFusion((Peel ? FC0Copy : *FC0), *FC1), DT, &PDT, ORE,
1039 assert(FusedCand.isEligibleForFusion(SE) &&
1040 "Fused candidate should be eligible for fusion!");
1043 LDT.removeLoop(FC1->L);
1045 CandidateSet.erase(FC0);
1046 CandidateSet.erase(FC1);
1048 auto InsertPos = CandidateSet.insert(FusedCand);
1050 assert(InsertPos.second &&
1051 "Unable to insert TargetCandidate in CandidateSet!");
1056 FC0 = FC1 = InsertPos.first;
1058 LLVM_DEBUG(
dbgs() <<
"Candidate Set (after fusion): " << CandidateSet
1076 const FusionCandidate &FC0)
const {
1078 assert(FC0PreheaderTarget &&
1079 "Expected single successor for loop preheader.");
1081 for (
Use &
Op :
I.operands()) {
1082 if (
auto *OpInst = dyn_cast<Instruction>(
Op)) {
1086 if (!(OpHoisted || DT.
dominates(OpInst, FC0PreheaderTarget))) {
1094 if (isa<PHINode>(
I))
1098 if (!
I.mayReadOrWriteMemory())
1101 LLVM_DEBUG(
dbgs() <<
"Checking if this mem inst can be hoisted.\n");
1103 if (
auto D = DI.
depends(&
I, NotHoistedInst,
true)) {
1106 if (
D->isFlow() ||
D->isAnti() ||
D->isOutput()) {
1108 "preheader that is not being hoisted.\n");
1115 if (
auto D = DI.
depends(ReadInst, &
I,
true)) {
1118 LLVM_DEBUG(
dbgs() <<
"Inst depends on a read instruction in FC0.\n");
1125 if (
auto D = DI.
depends(WriteInst, &
I,
true)) {
1127 if (
D->isFlow() ||
D->isOutput()) {
1128 LLVM_DEBUG(
dbgs() <<
"Inst depends on a write instruction in FC0.\n");
1139 bool canSinkInst(
Instruction &
I,
const FusionCandidate &FC1)
const {
1140 for (
User *U :
I.users()) {
1141 if (
auto *UI{dyn_cast<Instruction>(U)}) {
1144 if (FC1.L->contains(UI)) {
1153 if (!
I.mayReadOrWriteMemory())
1157 if (
auto D = DI.
depends(&
I, ReadInst,
true)) {
1160 LLVM_DEBUG(
dbgs() <<
"Inst depends on a read instruction in FC1.\n");
1167 if (
auto D = DI.
depends(&
I, WriteInst,
true)) {
1169 if (
D->isOutput() ||
D->isAnti()) {
1170 LLVM_DEBUG(
dbgs() <<
"Inst depends on a write instruction in FC1.\n");
1181 bool collectMovablePreheaderInsts(
1182 const FusionCandidate &FC0,
const FusionCandidate &FC1,
1192 if (&
I == FC1Preheader->getTerminator())
1198 if (
I.mayThrow() || !
I.willReturn()) {
1199 LLVM_DEBUG(
dbgs() <<
"Inst: " <<
I <<
" may throw or won't return.\n");
1205 if (
I.isAtomic() ||
I.isVolatile()) {
1207 dbgs() <<
"\tInstruction is volatile or atomic. Cannot move it.\n");
1211 if (canHoistInst(
I, SafeToHoist, NotHoisting, FC0)) {
1218 if (canSinkInst(
I, FC1)) {
1228 dbgs() <<
"All preheader instructions could be sunk or hoisted!\n");
1243 if (ExprL == &OldL) {
1248 if (OldL.contains(ExprL)) {
1250 if (!UseMax || !Pos || !Expr->
isAffine()) {
1262 bool wasValidSCEV()
const {
return Valid; }
1266 const Loop &OldL, &NewL;
1282 LLVM_DEBUG(
dbgs() <<
" Access function check: " << *SCEVPtr0 <<
" vs "
1283 << *SCEVPtr1 <<
"\n");
1285 AddRecLoopReplacer
Rewriter(SE, L0, L1);
1286 SCEVPtr0 =
Rewriter.visit(SCEVPtr0);
1289 LLVM_DEBUG(
dbgs() <<
" Access function after rewrite: " << *SCEVPtr0
1290 <<
" [Valid: " <<
Rewriter.wasValidSCEV() <<
"]\n");
1300 auto HasNonLinearDominanceRelation = [&](
const SCEV *S) {
1311 EqualIsInvalid ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_SGE;
1316 << (IsAlwaysGE ?
" >= " :
" may < ") << *SCEVPtr1
1325 bool dependencesAllowFusion(
const FusionCandidate &FC0,
1331 LLVM_DEBUG(
dbgs() <<
"Check dep: " << I0 <<
" vs " << I1 <<
" : "
1332 << DepChoice <<
"\n");
1335 switch (DepChoice) {
1337 return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);
1339 auto DepResult = DI.
depends(&I0, &I1,
true);
1345 dbgs() <<
" [#l: " << DepResult->getLevels() <<
"][Ordered: "
1346 << (DepResult->isOrdered() ?
"true" :
"false")
1348 LLVM_DEBUG(
dbgs() <<
"DepResult Levels: " << DepResult->getLevels()
1353 if (DepResult->getNextPredecessor() || DepResult->getNextSuccessor())
1355 dbgs() <<
"TODO: Implement pred/succ dependence handling!\n");
1362 return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
1364 dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
1372 bool dependencesAllowFusion(
const FusionCandidate &FC0,
1373 const FusionCandidate &FC1) {
1374 LLVM_DEBUG(
dbgs() <<
"Check if " << FC0 <<
" can be fused with " << FC1
1376 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
1381 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1384 InvalidDependencies++;
1388 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,
1391 InvalidDependencies++;
1398 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
1401 InvalidDependencies++;
1405 if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1,
1408 InvalidDependencies++;
1417 for (
auto &
Op :
I.operands())
1419 if (FC0.L->contains(
Def->getParent())) {
1420 InvalidDependencies++;
1436 bool isAdjacent(
const FusionCandidate &FC0,
1437 const FusionCandidate &FC1)
const {
1439 if (FC0.GuardBranch)
1440 return FC0.getNonLoopBlock() == FC1.getEntryBlock();
1442 return FC0.ExitBlock == FC1.getEntryBlock();
1445 bool isEmptyPreheader(
const FusionCandidate &FC)
const {
1446 return FC.Preheader->size() == 1;
1451 void movePreheaderInsts(
const FusionCandidate &FC0,
1452 const FusionCandidate &FC1,
1456 assert(HoistInsts.
size() + SinkInsts.
size() == FC1.Preheader->size() - 1 &&
1457 "Attempting to sink and hoist preheader instructions, but not all "
1458 "the preheader instructions are accounted for.");
1460 NumHoistedInsts += HoistInsts.
size();
1461 NumSunkInsts += SinkInsts.
size();
1464 if (!HoistInsts.
empty())
1465 dbgs() <<
"Hoisting: \n";
1467 dbgs() << *
I <<
"\n";
1468 if (!SinkInsts.
empty())
1469 dbgs() <<
"Sinking: \n";
1471 dbgs() << *
I <<
"\n";
1475 assert(
I->getParent() == FC1.Preheader);
1476 I->moveBefore(*FC0.Preheader,
1477 FC0.Preheader->getTerminator()->getIterator());
1481 assert(
I->getParent() == FC1.Preheader);
1482 I->moveBefore(*FC1.ExitBlock, FC1.ExitBlock->getFirstInsertionPt());
1498 bool haveIdenticalGuards(
const FusionCandidate &FC0,
1499 const FusionCandidate &FC1)
const {
1500 assert(FC0.GuardBranch && FC1.GuardBranch &&
1501 "Expecting FC0 and FC1 to be guarded loops.");
1503 if (
auto FC0CmpInst =
1504 dyn_cast<Instruction>(FC0.GuardBranch->getCondition()))
1505 if (
auto FC1CmpInst =
1506 dyn_cast<Instruction>(FC1.GuardBranch->getCondition()))
1507 if (!FC0CmpInst->isIdenticalTo(FC1CmpInst))
1513 if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader)
1514 return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);
1516 return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);
1521 void simplifyLatchBranch(
const FusionCandidate &FC)
const {
1522 BranchInst *FCLatchBranch = dyn_cast<BranchInst>(
FC.Latch->getTerminator());
1523 if (FCLatchBranch) {
1526 "Expecting the two successors of FCLatchBranch to be the same");
1535 void mergeLatch(
const FusionCandidate &FC0,
const FusionCandidate &FC1) {
1572 Loop *performFusion(
const FusionCandidate &FC0,
const FusionCandidate &FC1) {
1573 assert(FC0.isValid() && FC1.isValid() &&
1574 "Expecting valid fusion candidates");
1577 dbgs() <<
"Fusion Candidate 1: \n"; FC1.dump(););
1586 if (FC0.GuardBranch)
1587 return fuseGuardedLoops(FC0, FC1);
1590 (FC0.Peeled ? FC0.ExitBlock->getUniqueSuccessor() : FC0.ExitBlock));
1591 assert(FC1.Preheader->size() == 1 &&
1592 FC1.Preheader->getSingleSuccessor() == FC1.Header);
1604 if (FC0.ExitingBlock != FC0.Latch)
1609 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1610 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1633 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
1636 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
1638 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1641 DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));
1644 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,
1647 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
1648 FC0.ExitBlock->getTerminator()->eraseFromParent();
1650 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1656 FC1.Preheader->getTerminator()->eraseFromParent();
1659 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1662 while (
PHINode *
PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1665 if (
PHI->hasNUsesOrMore(1))
1666 PHI->moveBefore(&*FC0.Header->getFirstInsertionPt());
1668 PHI->eraseFromParent();
1676 for (
PHINode *LCPHI : OriginalFC0PHIs) {
1677 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1678 assert(L1LatchBBIdx >= 0 &&
1679 "Expected loop carried value to be rewired at this point!");
1681 Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx);
1690 LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);
1694 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1695 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1699 simplifyLatchBranch(FC0);
1703 if (FC0.Latch != FC0.ExitingBlock)
1705 DominatorTree::Insert, FC0.Latch, FC1.Header));
1708 FC0.Latch, FC0.Header));
1710 FC1.Latch, FC0.Header));
1712 FC1.Latch, FC1.Header));
1738 mergeLatch(FC0, FC1);
1743 FC0.L->addBlockEntry(BB);
1744 FC1.L->removeBlockFromLoop(BB);
1749 while (!FC1.L->isInnermost()) {
1750 const auto &ChildLoopIt = FC1.L->begin();
1751 Loop *ChildLoop = *ChildLoopIt;
1761 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
1784 template <
typename RemarkKind>
1785 void reportLoopFusion(
const FusionCandidate &FC0,
const FusionCandidate &FC1,
1787 assert(FC0.Preheader && FC1.Preheader &&
1788 "Expecting valid fusion candidates");
1789 using namespace ore;
1790#if LLVM_ENABLE_STATS
1792 ORE.
emit(RemarkKind(
DEBUG_TYPE, Stat.getName(), FC0.L->getStartLoc(),
1794 <<
"[" << FC0.Preheader->getParent()->getName()
1795 <<
"]: " <<
NV(
"Cand1",
StringRef(FC0.Preheader->getName()))
1796 <<
" and " <<
NV(
"Cand2",
StringRef(FC1.Preheader->getName()))
1797 <<
": " << Stat.getDesc());
1816 Loop *fuseGuardedLoops(
const FusionCandidate &FC0,
1817 const FusionCandidate &FC1) {
1818 assert(FC0.GuardBranch && FC1.GuardBranch &&
"Expecting guarded loops");
1822 BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
1823 BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
1831 (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock,
1838 assert(FC0NonLoopBlock == FC1GuardBlock &&
"Loops are not adjacent");
1851 FC0.GuardBranch->replaceUsesOfWith(FC0NonLoopBlock, FC1NonLoopBlock);
1853 BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock;
1857 FC1.GuardBranch->eraseFromParent();
1861 DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));
1863 DominatorTree::Delete, FC1GuardBlock, FC1NonLoopBlock));
1865 DominatorTree::Delete, FC0GuardBlock, FC1GuardBlock));
1867 DominatorTree::Insert, FC0GuardBlock, FC1NonLoopBlock));
1872 DominatorTree::Delete, FC0ExitBlockSuccessor, FC1GuardBlock));
1875 FC0ExitBlockSuccessor);
1879 "Expecting guard block to have no predecessors");
1881 "Expecting guard block to have no successors");
1896 if (FC0.ExitingBlock != FC0.Latch)
1900 assert(OriginalFC0PHIs.
empty() &&
"Expecting OriginalFC0PHIs to be empty!");
1903 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1904 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1919 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,
1923 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
1925 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1935 FC0.ExitBlock->getTerminator()->eraseFromParent();
1941 FC1.Preheader->getTerminator()->eraseFromParent();
1944 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1947 while (
PHINode *
PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1950 if (
PHI->hasNUsesOrMore(1))
1951 PHI->moveBefore(&*FC0.Header->getFirstInsertionPt());
1953 PHI->eraseFromParent();
1961 for (
PHINode *LCPHI : OriginalFC0PHIs) {
1962 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1963 assert(L1LatchBBIdx >= 0 &&
1964 "Expected loop carried value to be rewired at this point!");
1966 Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx);
1975 LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);
1981 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1982 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1986 simplifyLatchBranch(FC0);
1990 if (FC0.Latch != FC0.ExitingBlock)
1992 DominatorTree::Insert, FC0.Latch, FC1.Header));
1995 FC0.Latch, FC0.Header));
1997 FC1.Latch, FC0.Header));
1999 FC1.Latch, FC1.Header));
2015 DTU.
deleteBB(FC0ExitBlockSuccessor);
2034 mergeLatch(FC0, FC1);
2039 FC0.L->addBlockEntry(BB);
2040 FC1.L->removeBlockFromLoop(BB);
2045 while (!FC1.L->isInnermost()) {
2046 const auto &ChildLoopIt = FC1.L->begin();
2047 Loop *ChildLoop = *ChildLoopIt;
2057 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
2084 bool Changed =
false;
2085 for (
auto &L : LI) {
2092 LoopFuser LF(LI, DT, DI, SE, PDT, ORE,
DL, AC,
TTI);
2093 Changed |= LF.fuseLoops(
F);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static bool reportInvalidCandidate(const Instruction &I, llvm::Statistic &Stat)
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
DenseMap< Block *, BlockRelaxAux > Blocks
static cl::opt< FusionDependenceAnalysisChoice > FusionDependenceAnalysis("loop-fusion-dependence-analysis", cl::desc("Which dependence analysis should loop fusion use?"), cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev", "Use the scalar evolution interface"), clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da", "Use the dependence analysis interface"), clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all", "Use all available analyses")), cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL))
FusionDependenceAnalysisChoice
@ FUSION_DEPENDENCE_ANALYSIS_DA
@ FUSION_DEPENDENCE_ANALYSIS_ALL
@ FUSION_DEPENDENCE_ANALYSIS_SCEV
static cl::opt< bool > VerboseFusionDebugging("loop-fusion-verbose-debug", cl::desc("Enable verbose debugging for Loop Fusion"), cl::Hidden, cl::init(false))
static cl::opt< unsigned > FusionPeelMaxCount("loop-fusion-peel-max-count", cl::init(0), cl::Hidden, cl::desc("Max number of iterations to be peeled from a loop, such that " "fusion can take place"))
This file implements the Loop Fusion pass.
mir Rename Register Operands
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Virtual Register Rewriter
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Conditional or Unconditional Branch instruction.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
AnalysisPass to compute dependence information in a function.
DependenceInfo - This class is the main dependence-analysis driver.
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
unsigned getLevel() const
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Analysis pass which computes a DominatorTree.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
BlockT * getHeader() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void print(raw_ostream &OS) const
reverse_iterator rend() const
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
reverse_iterator rbegin() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Represents a single loop in the control flow graph.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
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 PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
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.
void preserve()
Mark an analysis as preserved.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
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
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
ArrayRef< const SCEV * > operands() const
This visitor recursively visits a SCEV expression and re-writes it.
This class represents an analyzed expression in the program.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
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...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< DefNode * > Def
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
bool succ_empty(const Instruction *I)
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
bool canPeel(const Loop *L)
void moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)
Move instructions, in an order-preserving manner, from FromBB to the end of ToBB when proven safe.
auto reverse(ContainerTy &&C)
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT)
Return true if I0 and I1 are control flow equivalent.
bool nonStrictlyPostDominate(const BasicBlock *ThisBlock, const BasicBlock *OtherBlock, const DominatorTree *DT, const PostDominatorTree *PDT)
In case that two BBs ThisBlock and OtherBlock are control flow equivalent but they do not strictly do...
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)
Move instructions, in an order-preserving manner, from FromBB to the beginning of ToBB when proven sa...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT=nullptr, DependenceInfo *DI=nullptr, bool CheckForEntireBlock=false)
Return true if I can be safely moved before InsertPoint.
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)
VMap is the value-map that maps instructions from the original loop to instructions in the last peele...
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.