LLVM: lib/Transforms/Scalar/SimpleLoopUnswitch.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
62#include
63#include
64#include
65#include
66#include
67#include
68
69#define DEBUG_TYPE "simple-loop-unswitch"
70
71using namespace llvm;
73
74STATISTIC(NumBranches, "Number of branches unswitched");
75STATISTIC(NumSwitches, "Number of switches unswitched");
76STATISTIC(NumSelects, "Number of selects turned into branches for unswitching");
77STATISTIC(NumGuards, "Number of guards turned into branches for unswitching");
78STATISTIC(NumTrivial, "Number of unswitches that are trivial");
80 NumCostMultiplierSkipped,
81 "Number of unswitch candidates that had their cost multiplier skipped");
83 "Number of invariant conditions injected and unswitched");
84
85namespace llvm {
88 cl::desc("Forcibly enables non-trivial loop unswitching rather than "
89 "following the configuration passed into the pass."));
90
93 cl::desc("The cost threshold for unswitching a loop."));
94
97 cl::desc("Enable unswitch cost multiplier that prohibits exponential "
98 "explosion in nontrivial unswitch."));
101 cl::desc("Toplevel siblings divisor for cost multiplier."));
104 cl::desc("Outer loop size divisor for cost multiplier."));
107 cl::desc("Number of unswitch candidates that are ignored when calculating "
108 "cost multiplier."));
111 cl::desc("If enabled, simple loop unswitching will also consider "
112 "llvm.experimental.guard intrinsics as unswitch candidates."));
114 "simple-loop-unswitch-drop-non-trivial-implicit-null-checks",
116 cl::desc("If enabled, drop make.implicit metadata in unswitched implicit "
117 "null checks to save time analyzing if we can keep it."));
120 cl::desc("Max number of memory uses to explore during "
121 "partial unswitching analysis"),
125 cl::desc("If enabled, the freeze instruction will be added to condition "
126 "of loop unswitch to prevent miscompilation."));
127
129 "simple-loop-unswitch-inject-invariant-conditions", cl::Hidden,
130 cl::desc("Whether we should inject new invariants and unswitch them to "
131 "eliminate some existing (non-invariant) conditions."),
133
135 "simple-loop-unswitch-inject-invariant-condition-hotness-threshold",
137 cl::desc("Only try to inject loop invariant conditions and "
138 "unswitch on them to eliminate branches that are "
139 "not-taken 1/ times or less."),
141
145}
146
148namespace {
149struct CompareDesc {
151 Value *Invariant;
153
155 : Term(Term), Invariant(Invariant), InLoopSucc(InLoopSucc) {}
156};
157
158struct InjectedInvariant {
159 ICmpInst::Predicate Pred;
163
164 InjectedInvariant(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
165 BasicBlock *InLoopSucc)
166 : Pred(Pred), LHS(LHS), RHS(RHS), InLoopSucc(InLoopSucc) {}
167};
168
169struct NonTrivialUnswitchCandidate {
171 TinyPtrVector<Value *> Invariants;
172 std::optional Cost;
173 std::optional PendingInjection;
174 NonTrivialUnswitchCandidate(
176 std::optional Cost = std::nullopt,
177 std::optional PendingInjection = std::nullopt)
178 : TI(TI), Invariants(Invariants), Cost(Cost),
179 PendingInjection(PendingInjection) {};
180
181 bool hasPendingInjection() const { return PendingInjection.has_value(); }
182};
183}
184
185
186
187
191 Cond = CondNext;
193}
194
195
196
197
198
199
200
201
205 assert(!L.isLoopInvariant(&Root) &&
206 "Only need to walk the graph if root itself is not invariant.");
208
211
212
216 Visited.insert(&Root);
217 do {
219 for (Value *OpV : I.operand_values()) {
220
222 continue;
223
224
225 if (L.isLoopInvariant(OpV)) {
227 continue;
228 }
229
230
232
235
236 if (Visited.insert(OpI).second)
238 }
239 }
240 } while (!Worklist.empty());
241
242 return Invariants;
243}
244
247 assert((Invariant) && "Why are we unswitching on a constant?");
248
249
250
253
254
255 if (UserI && L.contains(UserI))
256 U.set(&Replacement);
257 }
258}
259
260
261
267 if (!PN)
268
269 return true;
270
271
272
273 if (!L.isLoopInvariant(PN->getIncomingValueForBlock(&ExitingBB)))
274 return false;
275 }
277}
278
279
280
281
282
283
284
285
286
287
288
294
298
299
300
301
302
303
304
305
306
307
308
309 if (HasBranchWeights &&
310 static_cast<double>(BranchWeights[Direction ? 0 : 1]) /
311 static_cast<double>(sum_of(BranchWeights)) >
312 0.5)
313 HasBranchWeights = false;
314
317
319 for (Value *Inv : Invariants) {
321 Inv = IRB.CreateFreeze(Inv, Inv->getName() + ".fr");
323 }
324
326 : IRB.CreateAnd(FrozenInvariants);
329 Direction ? &NormalSucc : &UnswitchedSucc,
330 HasBranchWeights ? ComputeProfFrom.getMetadata(LLVMContext::MD_prof)
331 : nullptr);
332 if (!HasBranchWeights)
334}
335
336
342 for (auto *Val : reverse(ToDuplicate)) {
345
348
352 VMap[Val] = NewInst;
353
354 if (!MSSAU)
355 continue;
356
358 if (auto *MemUse =
360 auto *DefiningAccess = MemUse->getDefiningAccess();
361
362 while (L.contains(DefiningAccess->getBlock())) {
363
364
366 DefiningAccess =
367 MemPhi->getIncomingValueForBlock(L.getLoopPreheader());
368 else
369 DefiningAccess = cast(DefiningAccess)->getDefiningAccess();
370 }
374 }
375 }
376
379 Value *Cond = VMap[ToDuplicate[0]];
380
381
382 auto *ProfData =
385 ? OriginalBranch.getMetadata(LLVMContext::MD_prof)
386 : nullptr;
387 auto *BR =
389 Direction ? &NormalSucc : &UnswitchedSucc, ProfData);
390 if (!ProfData)
392}
393
394
395
396
397
398
399
400
404 for (PHINode &PN : UnswitchedBB.phis()) {
405
406
407
408 for (auto i : seq(0, PN.getNumOperands())) {
409 assert(PN.getIncomingBlock(i) == &OldExitingBB &&
410 "Found incoming block different from unique predecessor!");
411 PN.setIncomingBlock(i, &OldPH);
412 }
413 }
414}
415
416
417
418
419
420
421
422
427 bool FullUnswitch) {
428 assert(&ExitBB != &UnswitchedBB &&
429 "Must have different loop exit and unswitched blocks!");
432 auto *NewPN = PHINode::Create(PN.getType(), 2,
433 PN.getName() + ".split");
434 NewPN->insertBefore(InsertPt);
435
436
437
438
439
440
441
442
443
444
445 for (int i = PN.getNumIncomingValues() - 1; i >= 0; --i) {
446 if (PN.getIncomingBlock(i) != &OldExitingBB)
447 continue;
448
450 if (FullUnswitch)
451
452 PN.removeIncomingValue(i);
453
454 NewPN->addIncoming(Incoming, &OldPH);
455 }
456
457
458
459 PN.replaceAllUsesWith(NewPN);
460 NewPN->addIncoming(&PN, &ExitBB);
461 }
462}
463
464
465
466
467
468
472
473 Loop *OldParentL = L.getParentLoop();
474 if (!OldParentL)
475 return;
476
478 L.getExitBlocks(Exits);
479 Loop *NewParentL = nullptr;
480 for (auto *ExitBB : Exits)
482 if (!NewParentL || NewParentL->contains(ExitL))
483 NewParentL = ExitL;
484
485 if (NewParentL == OldParentL)
486 return;
487
488
489 if (NewParentL)
491 "Can only hoist this loop up the nest!");
492
493
494
496 "Parent loop of this loop should contain this loop's preheader!");
498
499
501
502
503 if (NewParentL)
505 else
507
508
509
510
511 for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL;
512 OldContainingL = OldContainingL->getParentLoop()) {
515 return BB == &Preheader || L.contains(BB);
516 });
517
518 OldContainingL->getBlocksSet().erase(&Preheader);
520 OldContainingL->getBlocksSet().erase(BB);
521
522
523
524
525 formLCSSA(*OldContainingL, DT, &LI, SE);
526
527
528
529
530
531
533 true);
534 }
535}
536
537
538
539
543 Loop *Current = TopMost;
544 while (Current) {
546 TopMost = Current;
548 }
549 return TopMost;
550}
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
573 LLVM_DEBUG(dbgs() << " Trying to unswitch branch: " << BI << "\n");
574
575
577
578
579
580 bool FullUnswitch = false;
581
583 if (L.isLoopInvariant(Cond)) {
585 FullUnswitch = true;
586 } else {
589 if (Invariants.empty()) {
590 LLVM_DEBUG(dbgs() << " Couldn't find invariant inputs!\n");
591 return false;
592 }
593 }
594
595
596 bool ExitDirection = true;
597 int LoopExitSuccIdx = 0;
599 if (L.contains(LoopExitBB)) {
600 ExitDirection = false;
601 LoopExitSuccIdx = 1;
603 if (L.contains(LoopExitBB)) {
604 LLVM_DEBUG(dbgs() << " Branch doesn't exit the loop!\n");
605 return false;
606 }
607 }
608 auto *ContinueBB = BI.getSuccessor(1 - LoopExitSuccIdx);
611 LLVM_DEBUG(dbgs() << " Loop exit PHI's aren't loop-invariant!\n");
612 return false;
613 }
614
615
616
617
618
619
620 if (!FullUnswitch) {
623 LLVM_DEBUG(dbgs() << " Branch condition is in improper form for "
624 "non-full unswitch!\n");
625 return false;
626 }
627 }
628
630 dbgs() << " unswitching trivial invariant conditions for: " << BI
631 << "\n";
632 for (Value *Invariant : Invariants) {
633 dbgs() << " " << *Invariant << " == true";
634 if (Invariant != Invariants.back())
635 dbgs() << " ||";
636 dbgs() << "\n";
637 }
638 });
639
640
641
642
643 if (SE) {
646 else
647
650 }
651
654
655
656
657
658 BasicBlock *OldPH = L.getLoopPreheader();
660
661
662
663
664
666 if (FullUnswitch && LoopExitBB->getUniquePredecessor()) {
667 assert(LoopExitBB->getUniquePredecessor() == BI.getParent() &&
668 "A branch's parent isn't a predecessor!");
669 UnswitchedBB = LoopExitBB;
670 } else {
671 UnswitchedBB =
672 SplitBlock(LoopExitBB, LoopExitBB->begin(), &DT, &LI, MSSAU, "", false);
673 }
674
677
678
679
680
682 if (FullUnswitch) {
683
684
685
688 if (MSSAU) {
689
690
692 } else {
693
694
697 }
698 BI.setSuccessor(LoopExitSuccIdx, UnswitchedBB);
700 } else {
701
702
703 if (ExitDirection)
705 "Must have an `or` of `i1`s or `select i1 X, true, Y`s for the "
706 "condition!");
707 else
709 "Must have an `and` of `i1`s or `select i1 X, Y, false`s for the"
710 " condition!");
712 *OldPH, Invariants, ExitDirection, *UnswitchedBB, *NewPH,
714 }
715
716
718
719
720
721 if (MSSAU) {
725 }
726
727
728 if (FullUnswitch) {
729 if (MSSAU) {
730 Instruction *Term = ParentBB->getTerminator();
731
732
735 Term->eraseFromParent();
736 MSSAU->removeEdge(ParentBB, LoopExitBB);
737 }
739 }
740
743
744
745 if (UnswitchedBB == LoopExitBB)
747 else
749 *ParentBB, *OldPH, FullUnswitch);
750
751
752
753
757
758
759
760 for (Value *Invariant : Invariants)
762
763
764
765 if (FullUnswitch)
767
770
771 LLVM_DEBUG(dbgs() << " done: unswitching trivial branch...\n");
772 ++NumTrivial;
773 ++NumBranches;
774 return true;
775}
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
806 LLVM_DEBUG(dbgs() << " Trying to unswitch switch: " << SI << "\n");
807 Value *LoopCond = SI.getCondition();
808
809
810 if (!L.isLoopInvariant(LoopCond))
811 return false;
812
813 auto *ParentBB = SI.getParent();
814
815
816
817
818
819
820 auto IsTriviallyUnswitchableExitBlock = [&](BasicBlock &BBToCheck) {
821
822 if (L.contains(&BBToCheck))
823 return false;
824
826 return false;
827
828
829
830
831 auto *TI = BBToCheck.getTerminator();
833 return !isUnreachable || &*BBToCheck.getFirstNonPHIOrDbg() != TI;
834 };
835
837 for (auto Case : SI.cases())
838 if (IsTriviallyUnswitchableExitBlock(*Case.getCaseSuccessor()))
839 ExitCaseIndices.push_back(Case.getCaseIndex());
843 if (IsTriviallyUnswitchableExitBlock(*SI.getDefaultDest())) {
844 DefaultExitBB = SI.getDefaultDest();
845 } else if (ExitCaseIndices.empty())
846 return false;
847
848 LLVM_DEBUG(dbgs() << " unswitching trivial switch...\n");
849
852
853
854
855 Loop *OuterL = &L;
856
857 if (DefaultExitBB) {
858
860 if (!ExitL || ExitL->contains(OuterL))
861 OuterL = ExitL;
862 }
863 for (unsigned Index : ExitCaseIndices) {
864 auto CaseI = SI.case_begin() + Index;
865
867 if (!ExitL || ExitL->contains(OuterL))
868 OuterL = ExitL;
869 }
870
871 if (SE) {
872 if (OuterL)
874 else
876 }
877
878 if (DefaultExitBB) {
879
880
881 SI.setDefaultDest(nullptr);
882 }
883
884
885
888 4> ExitCases;
889 ExitCases.reserve(ExitCaseIndices.size());
891
892
893 for (unsigned Index : reverse(ExitCaseIndices)) {
894 auto CaseI = SI.case_begin() + Index;
895
897 ExitCases.emplace_back(CaseI->getCaseValue(), CaseI->getCaseSuccessor(), W);
898
900 }
901
902
903
905 if (SI.getNumCases() > 0 &&
907 return Case.getCaseSuccessor() == SI.case_begin()->getCaseSuccessor();
908 }))
909 CommonSuccBB = SI.case_begin()->getCaseSuccessor();
910 if (!DefaultExitBB) {
911
912
913
914 if (SI.getNumCases() == 0)
915 CommonSuccBB = SI.getDefaultDest();
916 else if (SI.getDefaultDest() != CommonSuccBB)
917 CommonSuccBB = nullptr;
918 }
919
920
921
922 BasicBlock *OldPH = L.getLoopPreheader();
925
926
927
928
932
933
934
935
936
937
938
941
942
943
944 if (DefaultExitBB) {
946 UnswitchedExitBBs.insert(DefaultExitBB);
948 } else {
949 auto *SplitBB =
950 SplitBlock(DefaultExitBB, DefaultExitBB->begin(), &DT, &LI, MSSAU);
952 *ParentBB, *OldPH,
953 true);
954 DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB;
955 }
956 }
957
958
959 for (auto &ExitCase : reverse(ExitCases)) {
960
961 BasicBlock *ExitBB = std::get<1>(ExitCase);
962
963
964
966
967 if (UnswitchedExitBBs.insert(ExitBB).second)
969 continue;
970 }
971
972
973
974 BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB];
975 if (!SplitExitBB) {
976
977 SplitExitBB = SplitBlock(ExitBB, ExitBB->begin(), &DT, &LI, MSSAU);
979 *ParentBB, *OldPH,
980 true);
981 }
982
983 std::get<1>(ExitCase) = SplitExitBB;
984 }
985
986
987
988 for (auto &ExitCase : reverse(ExitCases)) {
989 ConstantInt *CaseVal = std::get<0>(ExitCase);
990 BasicBlock *UnswitchedBB = std::get<1>(ExitCase);
991
992 NewSIW.addCase(CaseVal, UnswitchedBB, std::get<2>(ExitCase));
993 }
994
995
996
997 if (DefaultExitBB) {
1000
1001
1002
1003 for (const auto &Case : SI.cases())
1006 } else if (DefaultCaseWeight) {
1007
1008 uint64_t SW = *DefaultCaseWeight;
1009 for (const auto &Case : SI.cases()) {
1012 "case weight must be defined as default case weight is defined");
1013 SW += *W;
1014 }
1016 }
1017
1018
1019
1020
1021
1022 if (CommonSuccBB) {
1024
1025
1026
1027 bool SkippedFirst = DefaultExitBB == nullptr;
1028 for (auto Case : SI.cases()) {
1030 "Non-common successor!");
1031 (void)Case;
1032 if (!SkippedFirst) {
1033 SkippedFirst = true;
1034 continue;
1035 }
1037 true);
1038 }
1039
1043 } else if (DefaultExitBB) {
1044 assert(SI.getNumCases() > 0 &&
1045 "If we had no cases we'd have a common successor!");
1046
1047
1048
1049
1050 auto LastCaseI = std::prev(SI.case_end());
1051
1052 SI.setDefaultDest(LastCaseI->getCaseSuccessor());
1056 }
1057
1058
1059
1060
1061
1063 for (auto *UnswitchedExitBB : UnswitchedExitBBs) {
1064 DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedExitBB});
1065 DTUpdates.push_back({DT.Insert, OldPH, UnswitchedExitBB});
1066 }
1067 for (auto SplitUnswitchedPair : SplitExitBBMap) {
1068 DTUpdates.push_back({DT.Delete, ParentBB, SplitUnswitchedPair.first});
1069 DTUpdates.push_back({DT.Insert, OldPH, SplitUnswitchedPair.second});
1070 }
1071
1072 if (MSSAU) {
1073 MSSAU->applyUpdates(DTUpdates, DT, true);
1076 } else {
1078 }
1079
1080 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1081
1082
1083
1085
1088
1089 ++NumTrivial;
1090 ++NumSwitches;
1091 LLVM_DEBUG(dbgs() << " done: unswitching trivial switch...\n");
1092 return true;
1093}
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123 BasicBlock *CurrentBB = L.getHeader();
1125 Visited.insert(CurrentBB);
1126 do {
1127
1128
1129
1130 if (MSSAU)
1132 if ((*Defs->begin()) || (++Defs->begin() != Defs->end()))
1135 [](Instruction &I) { return I.mayHaveSideEffects(); }))
1137
1139
1141
1142
1143
1146
1148
1150
1151
1153
1154
1155
1156
1157
1159 if (!BI || BI->isConditional())
1161
1162 CurrentBB = BI->getSuccessor(0);
1163 continue;
1164 }
1165
1167 if (!BI)
1168
1170
1171
1172
1173
1174 if (!BI->isConditional() ||
1177
1178
1179
1182
1183
1185
1186
1187
1189 if (BI->isConditional())
1191
1192
1193 CurrentBB = BI->getSuccessor(0);
1194
1195
1196
1197
1198 } while (L.contains(CurrentBB) && Visited.insert(CurrentBB).second);
1199
1201}
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1236 NewBlocks.reserve(L.getNumBlocks() + ExitBlocks.size());
1237
1238
1239
1240 auto CloneBlock = [&](BasicBlock *OldBB) {
1241
1244
1245
1247 VMap[OldBB] = NewBB;
1248
1249 return NewBB;
1250 };
1251
1252
1253
1254 auto SkipBlock = [&](BasicBlock *BB) {
1255 auto It = DominatingSucc.find(BB);
1256 return It != DominatingSucc.end() && It->second != UnswitchedSuccBB;
1257 };
1258
1259
1260 auto *ClonedPH = CloneBlock(LoopPH);
1261
1262
1263 for (auto *LoopBB : L.blocks())
1264 if (!SkipBlock(LoopBB))
1265 CloneBlock(LoopBB);
1266
1267
1268
1269
1270 for (auto *ExitBB : ExitBlocks) {
1271 if (SkipBlock(ExitBB))
1272 continue;
1273
1274
1275
1276
1277
1278
1279 auto *MergeBB = SplitBlock(ExitBB, ExitBB->begin(), &DT, &LI, MSSAU);
1280
1281
1282
1283
1284 MergeBB->takeName(ExitBB);
1285 ExitBB->setName(Twine(MergeBB->getName()) + ".split");
1286
1287
1288 auto *ClonedExitBB = CloneBlock(ExitBB);
1289 assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 &&
1290 "Exit block should have been split to have one successor!");
1291 assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB &&
1292 "Cloned exit block has the wrong successor!");
1293
1294
1296 llvm::make_range(ExitBB->begin(), std::prev(ExitBB->end())),
1298 std::prev(ClonedExitBB->end())))) {
1300 Instruction &ClonedI = std::get<1>(ZippedInsts);
1301
1302
1303
1306 "Bad instruction in exit block!");
1307
1308 assert(VMap.lookup(&I) == &ClonedI && "Mismatch in the value map!");
1309
1310
1311 if (SE)
1314
1316
1317 auto *MergePN =
1318 PHINode::Create(I.getType(), 2, ".us-phi");
1319 MergePN->insertBefore(InsertPt);
1320 MergePN->setDebugLoc(InsertPt->getDebugLoc());
1321 I.replaceAllUsesWith(MergePN);
1322 MergePN->addIncoming(&I, ExitBB);
1323 MergePN->addIncoming(&ClonedI, ClonedExitBB);
1324 }
1325 }
1326
1327
1328
1329
1330
1331
1332 Module *M = ClonedPH->getParent()->getParent();
1333 for (auto *ClonedBB : NewBlocks)
1341 }
1342
1343
1344
1345 for (auto *LoopBB : L.blocks())
1346 if (SkipBlock(LoopBB))
1347 for (auto *SuccBB : successors(LoopBB))
1349 for (PHINode &PN : ClonedSuccBB->phis())
1350 PN.removeIncomingValue(LoopBB, false);
1351
1352
1353
1355 for (auto *SuccBB : successors(ParentBB)) {
1356 if (SuccBB == UnswitchedSuccBB)
1357 continue;
1358
1360 if (!ClonedSuccBB)
1361 continue;
1362
1363 ClonedSuccBB->removePredecessor(ClonedParentBB,
1364 true);
1365 }
1366
1367
1368
1370 Instruction *ClonedTerminator = ClonedParentBB->getTerminator();
1371
1372
1373 Value *ClonedConditionToErase = nullptr;
1375 ClonedConditionToErase = BI->getCondition();
1377 ClonedConditionToErase = SI->getCondition();
1378
1382
1383 if (ClonedConditionToErase)
1385 MSSAU);
1386
1387
1388
1389
1390 for (PHINode &PN : ClonedSuccBB->phis()) {
1391 bool Found = false;
1392
1393
1394 for (int i = PN.getNumOperands() - 1; i >= 0; --i) {
1395 if (PN.getIncomingBlock(i) != ClonedParentBB)
1396 continue;
1397 if (!Found) {
1398 Found = true;
1399 continue;
1400 }
1401 PN.removeIncomingValue(i, false);
1402 }
1403 }
1404
1405
1407 for (auto *ClonedBB : NewBlocks) {
1408 for (auto *SuccBB : successors(ClonedBB))
1409 if (SuccSet.insert(SuccBB).second)
1411 SuccSet.clear();
1412 }
1413
1414 return ClonedPH;
1415}
1416
1417
1418
1419
1420
1421
1422
1425 auto AddClonedBlocksToLoop = [&](Loop &OrigL, Loop &ClonedL) {
1426 assert(ClonedL.getBlocks().empty() && "Must start with an empty loop!");
1427 ClonedL.reserveBlocks(OrigL.getNumBlocks());
1428 for (auto *BB : OrigL.blocks()) {
1430 ClonedL.addBlockEntry(ClonedBB);
1433 }
1434 };
1435
1436
1437
1439 if (RootParentL)
1441 else
1443 AddClonedBlocksToLoop(OrigRootL, *ClonedRootL);
1444
1446 return ClonedRootL;
1447
1448
1449
1450
1452
1453
1455 LoopsToClone.push_back({ClonedRootL, ChildL});
1456 do {
1457 Loop *ClonedParentL, *L;
1458 std::tie(ClonedParentL, L) = LoopsToClone.pop_back_val();
1461 AddClonedBlocksToLoop(*L, *ClonedL);
1463 LoopsToClone.push_back({ClonedL, ChildL});
1464 } while (!LoopsToClone.empty());
1465
1466 return ClonedRootL;
1467}
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1485 Loop *ClonedL = nullptr;
1486
1488 auto *OrigHeader = OrigL.getHeader();
1489
1492
1493
1494
1495
1496
1497 Loop *ParentL = nullptr;
1500 ClonedExitsInLoops.reserve(ExitBlocks.size());
1501 for (auto *ExitBB : ExitBlocks)
1504 ExitLoopMap[ClonedExitBB] = ExitL;
1505 ClonedExitsInLoops.push_back(ClonedExitBB);
1506 if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL)))
1507 ParentL = ExitL;
1508 }
1511 "The computed parent loop should always contain (or be) the parent of "
1512 "the original loop.");
1513
1514
1515
1516
1517
1519 for (auto *BB : OrigL.blocks())
1521 ClonedLoopBlocks.insert(ClonedBB);
1522
1523
1524
1525
1526
1529 for (auto *Pred : predecessors(ClonedHeader)) {
1530
1531
1532 if (Pred == ClonedPH)
1533 continue;
1534
1535
1536
1537 assert(ClonedLoopBlocks.count(Pred) && "Found a predecessor of the loop "
1538 "header other than the preheader "
1539 "that is not part of the loop!");
1540
1541
1542
1543
1544 if (BlocksInClonedLoop.insert(Pred).second && Pred != ClonedHeader)
1546 }
1547
1548
1549
1550
1551 if (!BlocksInClonedLoop.empty()) {
1552 BlocksInClonedLoop.insert(ClonedHeader);
1553
1554 while (!Worklist.empty()) {
1557 "Didn't put block into the loop set!");
1558
1559
1560
1561
1562
1563
1565 if (ClonedLoopBlocks.count(Pred) &&
1566 BlocksInClonedLoop.insert(Pred).second)
1568 }
1569
1571 if (ParentL) {
1574 } else {
1576 }
1577 NonChildClonedLoops.push_back(ClonedL);
1578
1580
1581
1582
1583
1584
1585 for (auto *BB : OrigL.blocks()) {
1587 if (!ClonedBB || !BlocksInClonedLoop.count(ClonedBB))
1588 continue;
1589
1590
1593 continue;
1594 }
1595
1596
1597
1598
1599 for (Loop *PL = ClonedL; PL; PL = PL->getParentLoop())
1600 PL->addBlockEntry(ClonedBB);
1601 }
1602
1603
1604
1605
1606
1607 for (Loop *ChildL : OrigL) {
1608 auto *ClonedChildHeader =
1610 if (!ClonedChildHeader || !BlocksInClonedLoop.count(ClonedChildHeader))
1611 continue;
1612
1613#ifndef NDEBUG
1614
1615
1616 for (auto *ChildLoopBB : ChildL->blocks())
1619 "Child cloned loop has a header within the cloned outer "
1620 "loop but not all of its blocks!");
1621#endif
1622
1624 }
1625 }
1626
1627
1628
1629
1630
1631
1632
1633
1635 if (BlocksInClonedLoop.empty())
1636 UnloopedBlockSet.insert(ClonedPH);
1637 for (auto *ClonedBB : ClonedLoopBlocks)
1638 if (!BlocksInClonedLoop.count(ClonedBB))
1639 UnloopedBlockSet.insert(ClonedBB);
1640
1641
1642
1643
1644
1645 auto OrderedClonedExitsInLoops = ClonedExitsInLoops;
1647 return ExitLoopMap.lookup(LHS)->getLoopDepth() <
1648 ExitLoopMap.lookup(RHS)->getLoopDepth();
1649 });
1650
1651
1652
1653 while (!UnloopedBlockSet.empty() && !OrderedClonedExitsInLoops.empty()) {
1654 assert(Worklist.empty() && "Didn't clear worklist!");
1655
1656 BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val();
1657 Loop *ExitL = ExitLoopMap.lookup(ExitBB);
1658
1659
1660
1662 do {
1664
1665 if (BB == ClonedPH)
1666 continue;
1667
1669
1670
1671 if (!UnloopedBlockSet.erase(PredBB)) {
1673 (BlocksInClonedLoop.count(PredBB) || ExitLoopMap.count(PredBB)) &&
1674 "Predecessor not mapped to a loop!");
1675 continue;
1676 }
1677
1678
1679
1680
1681 bool Inserted = ExitLoopMap.insert({PredBB, ExitL}).second;
1682 (void)Inserted;
1683 assert(Inserted && "Should only visit an unlooped block once!");
1684
1685
1687 }
1688 } while (!Worklist.empty());
1689 }
1690
1691
1692
1693
1694
1695
1696
1698 ArrayRef(ClonedPH), ClonedLoopBlocks, ClonedExitsInLoops))
1699 if (Loop *OuterL = ExitLoopMap.lookup(BB))
1700 OuterL->addBasicBlockToLoop(BB, LI);
1701
1702#ifndef NDEBUG
1703 for (auto &BBAndL : ExitLoopMap) {
1704 auto *BB = BBAndL.first;
1705 auto *OuterL = BBAndL.second;
1707 "Failed to put all blocks into outer loops!");
1708 }
1709#endif
1710
1711
1712
1713
1714 for (Loop *ChildL : OrigL) {
1715 auto *ClonedChildHeader =
1717 if (!ClonedChildHeader || BlocksInClonedLoop.count(ClonedChildHeader))
1718 continue;
1719
1720#ifndef NDEBUG
1721 for (auto *ChildLoopBB : ChildL->blocks())
1723 "Cloned a child loop header but not all of that loops blocks!");
1724#endif
1725
1727 *ChildL, ExitLoopMap.lookup(ClonedChildHeader), VMap, LI));
1728 }
1729}
1730
1731static void
1733 ArrayRef<std::unique_ptr> VMaps,
1735
1738 for (const auto &VMap : VMaps)
1742 SuccBB->removePredecessor(ClonedBB);
1744 }
1745
1746
1747 if (MSSAU) {
1749 DeadBlocks.end());
1751 }
1752
1753
1755 BB->dropAllReferences();
1756
1758 BB->eraseFromParent();
1759}
1760
1767
1768
1770
1771
1772
1774 ExitBlocks.end());
1775 DeathCandidates.append(L.blocks().begin(), L.blocks().end());
1776 while (!DeathCandidates.empty()) {
1780 SuccBB->removePredecessor(BB);
1781 DeathCandidates.push_back(SuccBB);
1782 }
1783 DeadBlockSet.insert(BB);
1784 }
1785 }
1786
1787
1788 if (MSSAU)
1790
1791
1792
1794 [&](BasicBlock *BB) { return DeadBlockSet.count(BB); });
1795
1796
1797 for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) {
1798 for (auto *BB : DeadBlockSet)
1799 ParentL->getBlocksSet().erase(BB);
1801 [&](BasicBlock *BB) { return DeadBlockSet.count(BB); });
1802 }
1803
1804
1805
1807 if (!DeadBlockSet.count(ChildL->getHeader()))
1808 return false;
1809
1810 assert(llvm::all_of(ChildL->blocks(),
1811 [&](BasicBlock *ChildBB) {
1812 return DeadBlockSet.count(ChildBB);
1813 }) &&
1814 "If the child loop header is dead all blocks in the child loop must "
1815 "be dead as well!");
1817 if (SE)
1820 return true;
1821 });
1822
1823
1824
1825
1826 for (auto *BB : DeadBlockSet) {
1827
1828 assert(!DT.getNode(BB) && "Should already have cleared domtree!");
1829 LI.changeLoopFor(BB, nullptr);
1830
1831
1832 for (auto &I : *BB)
1833 if (.use_empty())
1835 BB->dropAllReferences();
1836 }
1837
1838
1839
1840 for (auto *BB : DeadBlockSet)
1841 BB->eraseFromParent();
1842}
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1858
1859 auto *PH = L.getLoopPreheader();
1860 auto *Header = L.getHeader();
1861
1862
1864
1865
1866
1868
1869 if (Pred == PH)
1870 continue;
1871
1872
1873
1874 assert(L.contains(Pred) && "Found a predecessor of the loop header other "
1875 "than the preheader that is not part of the "
1876 "loop!");
1877
1878
1879
1880
1881 if (LoopBlockSet.insert(Pred).second && Pred != Header)
1883 }
1884
1885
1886 if (LoopBlockSet.empty())
1887 return LoopBlockSet;
1888
1889
1890 while (!Worklist.empty()) {
1892 assert(LoopBlockSet.count(BB) && "Didn't put block into the loop set!");
1893
1894
1895 if (BB == Header)
1896 continue;
1897
1898
1899
1900
1901
1903 if (InnerL != &L) {
1904 assert(L.contains(InnerL) &&
1905 "Should not reach a loop *outside* this loop!");
1906
1907
1908 auto *InnerPH = InnerL->getLoopPreheader();
1909 assert(L.contains(InnerPH) && "Cannot contain an inner loop block "
1910 "but not contain the inner loop "
1911 "preheader!");
1912 if (!LoopBlockSet.insert(InnerPH).second)
1913
1914
1915 continue;
1916
1917
1918
1919
1920
1921
1922 for (auto *InnerBB : InnerL->blocks()) {
1923 if (InnerBB == BB) {
1925 "Block should already be in the set!");
1926 continue;
1927 }
1928
1929 LoopBlockSet.insert(InnerBB);
1930 }
1931
1932
1933
1935 continue;
1936 }
1937
1938
1939
1941 if (L.contains(Pred) && LoopBlockSet.insert(Pred).second)
1943 }
1944
1945 assert(LoopBlockSet.count(Header) && "Cannot fail to add the header!");
1946
1947
1948
1949 return LoopBlockSet;
1950}
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1970 auto *PH = L.getLoopPreheader();
1971
1972
1973
1974 Loop *ParentL = nullptr;
1977 ExitsInLoops.reserve(ExitBlocks.size());
1978 for (auto *ExitBB : ExitBlocks)
1982 if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL)))
1983 ParentL = ExitL;
1984 }
1985
1986
1987
1989
1990
1991
1992
1993
1994 if (!LoopBlockSet.empty() && L.getParentLoop() != ParentL) {
1995
1996 for (Loop *IL = L.getParentLoop(); IL != ParentL;
1998 IL->getBlocksSet().erase(PH);
1999 for (auto *BB : L.blocks())
2000 IL->getBlocksSet().erase(BB);
2002 return BB == PH || L.contains(BB);
2003 });
2004 }
2005
2007 L.getParentLoop()->removeChildLoop(&L);
2008 if (ParentL)
2010 else
2012 }
2013
2014
2015 auto &Blocks = L.getBlocksVector();
2016 auto BlocksSplitI =
2017 LoopBlockSet.empty()
2018 ? Blocks.begin()
2019 : std::stable_partition(
2020 Blocks.begin(), Blocks.end(),
2021 [&](BasicBlock *BB) { return LoopBlockSet.count(BB); });
2022
2023
2025 if (LoopBlockSet.empty())
2026 UnloopedBlocks.insert(PH);
2027
2028
2029 for (auto *BB : make_range(BlocksSplitI, Blocks.end()))
2030 L.getBlocksSet().erase(BB);
2031 Blocks.erase(BlocksSplitI, Blocks.end());
2032
2033
2034
2037 });
2038
2039
2041 Loop *PrevExitL = L.getParentLoop();
2042
2043 auto RemoveUnloopedBlocksFromLoop =
2045 for (auto *BB : UnloopedBlocks)
2046 L.getBlocksSet().erase(BB);
2048 return UnloopedBlocks.count(BB);
2049 });
2050 };
2051
2053 while (!UnloopedBlocks.empty() && !ExitsInLoops.empty()) {
2054 assert(Worklist.empty() && "Didn't clear worklist!");
2055 assert(NewExitLoopBlocks.empty() && "Didn't clear loop set!");
2056
2057
2060 assert(ExitL.contains(&L) && "Exit loop must contain the inner loop!");
2061
2062
2063
2064
2065
2066 for (; PrevExitL != &ExitL; PrevExitL = PrevExitL->getParentLoop())
2067 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
2068
2069
2070
2072 do {
2074
2075 if (BB == PH)
2076 continue;
2077
2079
2080
2081 if (!UnloopedBlocks.erase(PredBB)) {
2082 assert((NewExitLoopBlocks.count(PredBB) ||
2084 "Predecessor not in a nested loop (or already visited)!");
2085 continue;
2086 }
2087
2088
2089
2090
2091 bool Inserted = NewExitLoopBlocks.insert(PredBB).second;
2092 (void)Inserted;
2093 assert(Inserted && "Should only visit an unlooped block once!");
2094
2095
2097 }
2098 } while (!Worklist.empty());
2099
2100
2101
2102
2103 for (auto *BB : NewExitLoopBlocks)
2105 if (BBL == &L || !L.contains(BBL))
2107
2108
2109
2110 NewExitLoopBlocks.clear();
2111 }
2112
2113
2114
2115 for (; PrevExitL; PrevExitL = PrevExitL->getParentLoop())
2116 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
2117 for (auto *BB : UnloopedBlocks)
2119 if (BBL == &L || !L.contains(BBL))
2121
2122
2123
2124
2125 auto &SubLoops = L.getSubLoopsVector();
2126 auto SubLoopsSplitI =
2127 LoopBlockSet.empty()
2128 ? SubLoops.begin()
2129 : std::stable_partition(
2130 SubLoops.begin(), SubLoops.end(), [&](Loop *SubL) {
2131 return LoopBlockSet.count(SubL->getHeader());
2132 });
2133 for (auto *HoistedL : make_range(SubLoopsSplitI, SubLoops.end())) {
2134 HoistedLoops.push_back(HoistedL);
2135 HoistedL->setParentLoop(nullptr);
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145 if (auto *NewParentL = LI.getLoopFor(HoistedL->getLoopPreheader()))
2146 NewParentL->addChildLoop(HoistedL);
2147 else
2149 }
2150 SubLoops.erase(SubLoopsSplitI, SubLoops.end());
2151
2152
2153 if (Blocks.empty()) {
2154 assert(SubLoops.empty() &&
2155 "Failed to remove all subloops from the original loop!");
2156 if (Loop *ParentL = L.getParentLoop())
2158 else
2160
2161
2162 if (SE)
2165 return false;
2166 }
2167
2168 return true;
2169}
2170
2171
2172
2173
2174template
2178#ifndef NDEBUG
2180 Visited.insert(DT[BB]);
2181#endif
2182 do {
2184
2185
2186 if (!Callable(N->getBlock()))
2187 continue;
2188
2189
2192 "Cannot visit a node twice when walking a tree!");
2194 }
2195 } while (!DomWorklist.empty());
2196}
2197
2199 bool CurrentLoopValid, bool PartiallyInvariant,
2201
2202 if (!NewLoops.empty())
2203 U.addSiblingLoops(NewLoops);
2204
2205
2206
2207 if (CurrentLoopValid) {
2208 if (PartiallyInvariant) {
2209
2210
2211 auto &Context = L.getHeader()->getContext();
2213 Context,
2214 MDString::get(Context, "llvm.loop.unswitch.partial.disable"));
2216 Context, L.getLoopID(), {"llvm.loop.unswitch.partial"},
2217 {DisableUnswitchMD});
2218 L.setLoopID(NewLoopID);
2219 } else if (InjectedCondition) {
2220
2221 auto &Context = L.getHeader()->getContext();
2223 Context,
2224 MDString::get(Context, "llvm.loop.unswitch.injection.disable"));
2226 Context, L.getLoopID(), {"llvm.loop.unswitch.injection"},
2227 {DisableUnswitchMD});
2228 L.setLoopID(NewLoopID);
2229 } else
2230 U.revisitCurrentLoop();
2231 } else
2232 U.markLoopAsDeleted(L, LoopName);
2233}
2234
2239 LPMUpdater &LoopUpdater, bool InsertFreeze, bool InjectedCondition) {
2240 auto *ParentBB = TI.getParent();
2243
2244
2245
2246 std::string LoopName(L.getName());
2247
2248
2249
2250
2252 "Can only unswitch switches and conditional branch!");
2253 bool PartiallyInvariant = !PartialIVInfo.InstToDuplicate.empty();
2254 bool FullUnswitch =
2256 !PartiallyInvariant);
2257 if (FullUnswitch)
2259 "Cannot have other invariants with full unswitching!");
2260 else
2262 "Partial unswitching requires an instruction as the condition!");
2263
2266
2267
2268
2269
2270
2271
2272
2274 int ClonedSucc = 0;
2275 if (!FullUnswitch) {
2279 PartiallyInvariant) &&
2280 "Only `or`, `and`, an `select`, partially invariant instructions "
2281 "can combine invariants being unswitched.");
2286 ClonedSucc = 1;
2287 }
2288 }
2289 }
2290
2292 BI ? BI->getSuccessor(1 - ClonedSucc) : SI->getDefaultDest();
2294 if (BI)
2296 else
2297 for (auto Case : SI->cases())
2298 if (Case.getCaseSuccessor() != RetainedSuccBB)
2299 UnswitchedSuccBBs.insert(Case.getCaseSuccessor());
2300
2301 assert(!UnswitchedSuccBBs.count(RetainedSuccBB) &&
2302 "Should not unswitch the same successor we are retaining!");
2303
2304
2305
2306
2307
2308 assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!");
2309
2310
2311 Loop *ParentL = L.getParentLoop();
2312
2314 if (MSSAU)
2316
2317
2318
2319
2320 Loop *OuterExitL = &L;
2322 L.getUniqueExitBlocks(ExitBlocks);
2323 for (auto *ExitBB : ExitBlocks) {
2324
2325
2327 if (!NewOuterExitL) {
2328
2329 OuterExitL = nullptr;
2330 break;
2331 }
2332 if (NewOuterExitL != OuterExitL && NewOuterExitL->contains(OuterExitL))
2333 OuterExitL = NewOuterExitL;
2334 }
2335
2336
2337
2338
2339 if (SE) {
2340 if (OuterExitL)
2342 else
2345 }
2346
2347
2348
2349
2350
2351
2354 UnswitchedSuccBBs))
2355 if (SuccBB->getUniquePredecessor() ||
2357 return PredBB == ParentBB || DT.dominates(SuccBB, PredBB);
2358 }))
2360 DominatingSucc[BB] = SuccBB;
2361 return true;
2362 });
2363
2364
2365
2366
2367
2368
2369 BasicBlock *SplitBB = L.getLoopPreheader();
2370 BasicBlock *LoopPH = SplitEdge(SplitBB, L.getHeader(), &DT, &LI, MSSAU);
2371
2372
2374
2375
2377 VMaps.reserve(UnswitchedSuccBBs.size());
2379 for (auto *SuccBB : UnswitchedSuccBBs) {
2382 L, LoopPH, SplitBB, ExitBlocks, ParentBB, SuccBB, RetainedSuccBB,
2383 DominatingSucc, *VMaps.back(), DTUpdates, AC, DT, LI, MSSAU, SE);
2384 }
2385
2386
2387
2388 if (TI.getMetadata(LLVMContext::MD_make_implicit)) {
2390
2391
2392 TI.setMetadata(LLVMContext::MD_make_implicit, nullptr);
2393 else {
2394
2395
2399 TI.setMetadata(LLVMContext::MD_make_implicit, nullptr);
2400 }
2401 }
2402
2403
2404
2405
2407 if (FullUnswitch) {
2408
2410 NewTI->insertInto(ParentBB, ParentBB->end());
2411
2412
2413
2416
2417
2418 if (BI) {
2423 if (InsertFreeze) {
2424
2425
2426
2429 }
2432 } else {
2433 assert(SI && "Must either be a branch or switch!");
2434
2435
2436 assert(SI->getDefaultDest() == RetainedSuccBB &&
2437 "Not retaining default successor!");
2438 SI->setDefaultDest(LoopPH);
2439 for (const auto &Case : SI->cases())
2440 if (Case.getCaseSuccessor() == RetainedSuccBB)
2441 Case.setSuccessor(LoopPH);
2442 else
2443 Case.setSuccessor(ClonedPHs.find(Case.getCaseSuccessor())->second);
2444
2445 if (InsertFreeze)
2447 SI->getCondition()->getName() + ".fr",
2448 SI->getIterator()));
2449
2450
2451
2452
2453 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2456 }
2457
2458 if (MSSAU) {
2460 DTUpdates.clear();
2461
2462
2463
2464
2466 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2468
2469 for (auto &VMap : VMaps)
2471 true);
2473
2474
2475 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2476 MSSAU->removeEdge(ParentBB, SuccBB);
2477 }
2478
2479
2480
2481
2482 if (BI) {
2483
2484 assert(UnswitchedSuccBBs.size() == 1 &&
2485 "Only one possible unswitched block for a branch!");
2486 BasicBlock *UnswitchedSuccBB = *UnswitchedSuccBBs.begin();
2488 true);
2490 } else {
2491
2492
2493
2494
2495
2496
2499 "Not retaining default successor!");
2500 for (const auto &Case : NewSI->cases())
2501 Case.getCaseSuccessor()->removePredecessor(
2502 ParentBB,
2503 true);
2504
2505
2506
2507
2508 for (BasicBlock *SuccBB : UnswitchedSuccBBs)
2510 }
2511
2512
2513
2516
2517
2519 } else {
2520 assert(BI && "Only branches have partial unswitching.");
2521 assert(UnswitchedSuccBBs.size() == 1 &&
2522 "Only one possible unswitched block for a branch!");
2524
2525
2526 if (PartiallyInvariant)
2528 *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH, L, MSSAU, *BI);
2529 else {
2531 *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH,
2533 }
2535
2536 if (MSSAU) {
2538 DTUpdates.clear();
2539
2540
2541 for (auto &VMap : VMaps)
2543 true);
2545 }
2546 }
2547
2548
2550
2551
2552
2553
2554
2556
2557
2558
2559
2561 for (std::unique_ptr &VMap : VMaps)
2562 buildClonedLoops(L, ExitBlocks, *VMap, LI, NonChildClonedLoops);
2563
2564
2565
2566
2568
2571
2573 bool IsStillLoop =
2575
2578
2579
2580
2581
2582
2583
2584 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
2585
2586 if (BI && !PartiallyInvariant) {
2587
2588
2589
2590
2591 assert(UnswitchedSuccBBs.size() == 1 &&
2592 "Only one possible unswitched block for a branch!");
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604 bool ReplaceUnswitched =
2605 FullUnswitch || (Invariants.size() == 1) || PartiallyInvariant;
2606
2613 for (Value *Invariant : Invariants) {
2615 "Should not be replacing constant values!");
2616
2619 if (!UserI)
2620 continue;
2621
2622
2623
2625 U.set(ContinueReplacement);
2626 else if (ReplaceUnswitched &&
2628 U.set(UnswitchedReplacement);
2629 }
2630 }
2631 }
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645 auto UpdateLoop = [&](Loop &UpdateL) {
2646#ifndef NDEBUG
2647 UpdateL.verifyLoop();
2648 for (Loop *ChildL : UpdateL) {
2649 ChildL->verifyLoop();
2650 assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
2651 "Perturbed a child loop's LCSSA form!");
2652 }
2653#endif
2654
2655
2656
2657 formLCSSA(UpdateL, DT, &LI, SE);
2658
2659
2660
2661
2662
2664 };
2665
2666
2667
2668
2669
2670
2671 for (Loop *UpdatedL :
2673 UpdateLoop(*UpdatedL);
2674 if (UpdatedL->isOutermost())
2675 OuterExitL = nullptr;
2676 }
2677 if (IsStillLoop) {
2678 UpdateLoop(L);
2679 if (L.isOutermost())
2680 OuterExitL = nullptr;
2681 }
2682
2683
2684
2685 if (OuterExitL != &L)
2686 for (Loop *OuterL = ParentL; OuterL != OuterExitL;
2688 UpdateLoop(*OuterL);
2689
2690#ifndef NDEBUG
2691
2692
2694#endif
2695
2696
2697
2698
2701 if (UpdatedL->getParentLoop() == ParentL)
2703 postUnswitch(L, LoopUpdater, LoopName, IsStillLoop, PartiallyInvariant,
2704 InjectedCondition, SibLoops);
2705
2708
2709 if (BI)
2710 ++NumBranches;
2711 else
2712 ++NumSwitches;
2713}
2714
2715
2716
2717
2718
2719
2720
2725
2726
2727 auto BBCostIt = BBCostMap.find(N.getBlock());
2728 if (BBCostIt == BBCostMap.end())
2729 return 0;
2730
2731
2732 auto DTCostIt = DTCostMap.find(&N);
2733 if (DTCostIt != DTCostMap.end())
2734 return DTCostIt->second;
2735
2736
2737
2739 N.begin(), N.end(), BBCostIt->second,
2741 return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap);
2742 });
2743 bool Inserted = DTCostMap.insert({&N, Cost}).second;
2744 (void)Inserted;
2745 assert(Inserted && "Should not insert a node while visiting children!");
2746 return Cost;
2747}
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2775 LLVM_DEBUG(dbgs() << "Turning " << *SI << " into a branch.\n");
2777
2778 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
2780 SI->getMetadata(LLVMContext::MD_prof), &DTU, &LI);
2782 BasicBlock *ThenBB = CondBr->getSuccessor(0),
2783 *TailBB = CondBr->getSuccessor(1);
2784 if (MSSAU)
2786
2788 PHINode::Create(SI->getType(), 2, "unswitched.select", SI->getIterator());
2789 Phi->addIncoming(SI->getTrueValue(), ThenBB);
2790 Phi->addIncoming(SI->getFalseValue(), HeadBB);
2791 Phi->setDebugLoc(SI->getDebugLoc());
2792 SI->replaceAllUsesWith(Phi);
2793 SI->eraseFromParent();
2794
2797
2798 ++NumSelects;
2799 return CondBr;
2800}
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2826 LLVM_DEBUG(dbgs() << "Turning " << *GI << " into a branch.\n");
2828
2831
2832 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
2833
2834
2839 : nullptr,
2840 &DTU, &LI);
2842
2843
2845
2847 GuardedBlock->setName("guarded");
2850
2851 if (MSSAU)
2853
2856
2857 if (MSSAU) {
2862 }
2863
2866 ++NumGuards;
2867 return CheckBI;
2868}
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2887
2888
2889
2890
2891
2892 const BasicBlock *Latch = L.getLoopLatch();
2894 if (DT.dominates(CondBlock, Latch) &&
2898 return L.contains(SuccBB);
2899 }) <= 1))) {
2900 NumCostMultiplierSkipped++;
2901 return 1;
2902 }
2903
2904
2905
2906
2907
2908
2909
2910
2911 auto *ParentL = L.getParentLoop();
2912 int ParentLoopSizeMultiplier = 1;
2913 if (ParentL)
2914 ParentLoopSizeMultiplier =
2916
2917 int SiblingsCount =
2918 (ParentL ? ParentL->getSubLoopsVector().size() : llvm::size(LI));
2919
2920
2921
2922 int UnswitchedClones = 0;
2923 for (const auto &Candidate : UnswitchCandidates) {
2926 bool SkipExitingSuccessors = DT.dominates(CondBlock, Latch);
2928 UnswitchedClones++;
2929 continue;
2930 }
2932 if (!SkipExitingSuccessors)
2933 UnswitchedClones++;
2934 continue;
2935 }
2936 int NonExitingSuccessors =
2938 [SkipExitingSuccessors, &L](const BasicBlock *SuccBB) {
2939 return !SkipExitingSuccessors || L.contains(SuccBB);
2940 });
2941 UnswitchedClones += Log2_32(NonExitingSuccessors);
2942 }
2943
2944
2945
2946
2947
2948
2949 unsigned ClonesPower =
2951
2952
2953 int SiblingsMultiplier =
2954 std::max((ParentL ? SiblingsCount
2956 1);
2957
2958
2959 int CostMultiplier;
2964 else
2965 CostMultiplier = std::min(SiblingsMultiplier * (1 << ClonesPower),
2967
2968 LLVM_DEBUG(dbgs() << " Computed multiplier " << CostMultiplier
2969 << " (siblings " << SiblingsMultiplier << " * parent size "
2970 << ParentLoopSizeMultiplier << " * clones "
2971 << (1 << ClonesPower) << ")"
2972 << " for unswitch candidate: " << TI << "\n");
2973 return CostMultiplier;
2974}
2975
2981 assert(UnswitchCandidates.empty() && "Should be!");
2982
2986 return;
2987 if (L.isLoopInvariant(Cond)) {
2989 return;
2990 }
2995 if (!Invariants.empty())
2996 UnswitchCandidates.push_back({I, std::move(Invariants)});
2997 }
2998 };
2999
3000
3001 bool CollectGuards = false;
3004 L.getHeader()->getParent()->getParent(), Intrinsic::experimental_guard);
3005 if (GuardDecl && !GuardDecl->use_empty())
3006 CollectGuards = true;
3007 }
3008
3009 for (auto *BB : L.blocks()) {
3011 continue;
3012
3013 for (auto &I : *BB) {
3015 auto *Cond = SI->getCondition();
3016
3017 if (Cond->getType()->isIntegerTy(1) && ->getType()->isIntegerTy(1))
3018 AddUnswitchCandidatesForInst(SI, Cond);
3019 } else if (CollectGuards && isGuard(&I)) {
3020 auto *Cond =
3022
3025 }
3026 }
3027
3029
3030
3032 L.isLoopInvariant(SI->getCondition()) && !BB->getUniqueSuccessor())
3033 UnswitchCandidates.push_back({SI, {SI->getCondition()}});
3034 continue;
3035 }
3036
3038 if (!BI || !BI->isConditional() ||
3039 BI->getSuccessor(0) == BI->getSuccessor(1))
3040 continue;
3041
3042 AddUnswitchCandidatesForInst(BI, BI->getCondition());
3043 }
3044
3045 if (MSSAU && (&L, "llvm.loop.unswitch.partial.disable") &&
3046 (UnswitchCandidates, [&L](auto &TerminatorAndInvariants) {
3047 return TerminatorAndInvariants.TI == L.getHeader()->getTerminator();
3048 })) {
3052 dbgs() << "simple-loop-unswitch: Found partially invariant condition "
3053 << *Info->InstToDuplicate[0] << "\n");
3054 PartialIVInfo = *Info;
3055 PartialIVCondBranch = L.getHeader()->getTerminator();
3059 {L.getHeader()->getTerminator(), std::move(ValsToDuplicate)});
3060 }
3061 }
3062 return !UnswitchCandidates.empty();
3063}
3064
3065
3066
3067
3068
3069
3070
3071
3076 const Loop &L) {
3077 if (!L.contains(IfTrue)) {
3080 }
3081
3082
3083 if (L.isLoopInvariant(LHS)) {
3086 }
3087
3089
3091 RHS = ConstantInt::get(
3092 RHS->getContext(),
3094 }
3095}
3096
3097
3098
3099
3103 if (L.isLoopInvariant(LHS) || !L.isLoopInvariant(RHS))
3104 return false;
3105
3107 return false;
3108
3109 if (!L.contains(IfTrue) || L.contains(IfFalse))
3110 return false;
3111
3112
3113 if (L.getHeader() == IfTrue)
3114 return false;
3115 return true;
3116}
3117
3118
3119
3120
3121
3126 return false;
3129
3130 assert(Weights.size() == 2 && "Unexpected profile data!");
3131 size_t Idx = BI->getSuccessor(0) == TakenSucc ? 0 : 1;
3132 auto Num = Weights[Idx];
3133 auto Denom = Weights[0] + Weights[1];
3134
3135 if (Denom == 0 || Num > Denom)
3136 return false;
3138 if (LikelyTaken > ActualTaken)
3139 return false;
3140 return true;
3141}
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161static NonTrivialUnswitchCandidate
3165 assert(Candidate.hasPendingInjection() && "Nothing to inject!");
3166 BasicBlock *Preheader = L.getLoopPreheader();
3167 assert(Preheader && "Loop is not in simplified form?");
3169 "Unswitching branch of inner loop!");
3170
3171 auto Pred = Candidate.PendingInjection->Pred;
3172 auto *LHS = Candidate.PendingInjection->LHS;
3173 auto *RHS = Candidate.PendingInjection->RHS;
3174 auto *InLoopSucc = Candidate.PendingInjection->InLoopSucc;
3176 auto *BB = Candidate.TI->getParent();
3177 auto *OutOfLoopSucc = InLoopSucc == TI->getSuccessor(0) ? TI->getSuccessor(1)
3178 : TI->getSuccessor(0);
3179
3180 assert(L.contains(InLoopSucc) && "Not supported yet!");
3181 assert(!L.contains(OutOfLoopSucc) && "Not supported yet!");
3182 auto &Ctx = BB->getContext();
3183
3186 if (LHS->getType() != RHS->getType()) {
3187 if (LHS->getType()->getIntegerBitWidth() <
3188 RHS->getType()->getIntegerBitWidth())
3189 LHS = Builder.CreateZExt(LHS, RHS->getType(), LHS->getName() + ".wide");
3190 else
3191 RHS = Builder.CreateZExt(RHS, LHS->getType(), RHS->getName() + ".wide");
3192 }
3193
3194
3195 auto *InjectedCond =
3198
3200 BB->getParent(), InLoopSucc);
3201 Builder.SetInsertPoint(TI);
3202 auto *InvariantBr =
3203 Builder.CreateCondBr(InjectedCond, InLoopSucc, CheckBlock);
3204
3206
3207 Builder.SetInsertPoint(CheckBlock);
3208 Builder.CreateCondBr(
3209 TI->getCondition(), TI->getSuccessor(0), TI->getSuccessor(1),
3211 : nullptr);
3212 TI->eraseFromParent();
3213
3214
3215 for (auto &I : *InLoopSucc) {
3217 if (!PN)
3218 break;
3219 auto *Inc = PN->getIncomingValueForBlock(BB);
3220 PN->addIncoming(Inc, CheckBlock);
3221 }
3222 OutOfLoopSucc->replacePhiUsesWith(BB, CheckBlock);
3223
3229 };
3230
3232 if (MSSAU)
3234 L.addBasicBlockToLoop(CheckBlock, LI);
3235
3236#ifndef NDEBUG
3241#endif
3242
3243
3244
3245
3246 LLVM_DEBUG(dbgs() << "Injected a new loop-invariant branch " << *InvariantBr
3247 << " and considering it for unswitching.");
3248 ++NumInvariantConditionsInjected;
3249 return NonTrivialUnswitchCandidate(InvariantBr, { InjectedCond },
3250 Candidate.Cost);
3251}
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3268
3271 if (Compares.size() < 2)
3272 return false;
3274 for (auto Prev = Compares.begin(), Next = Compares.begin() + 1;
3275 Next != Compares.end(); ++Prev, ++Next) {
3277 Value *RHS = Prev->Invariant;
3278 BasicBlock *InLoopSucc = Prev->InLoopSucc;
3279 InjectedInvariant ToInject(NonStrictPred, LHS, RHS, InLoopSucc);
3280 NonTrivialUnswitchCandidate Candidate(Prev->Term, { LHS, RHS },
3281 std::nullopt, std::move(ToInject));
3282 UnswitchCandidates.push_back(std::move(Candidate));
3283 }
3284 return true;
3285}
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3308 return false;
3309
3311 return false;
3312 auto *Latch = L.getLoopLatch();
3313
3314 if (!Latch)
3315 return false;
3316 assert(L.getLoopPreheader() && "Must have a preheader!");
3317
3319
3320
3321 for (auto *DTN = DT.getNode(Latch); L.contains(DTN->getBlock());
3322 DTN = DTN->getIDom()) {
3325 BasicBlock *IfTrue = nullptr, *IfFalse = nullptr;
3326 auto *BB = DTN->getBlock();
3327
3329 continue;
3330 auto *Term = BB->getTerminator();
3333 continue;
3334 if (->getType()->isIntegerTy())
3335 continue;
3337 L);
3339 continue;
3341 continue;
3342
3343
3346 LHS = Zext->getOperand(0);
3347 CandidatesULT[LHS].push_back(Desc);
3348 }
3349
3350 bool Found = false;
3351 for (auto &It : CandidatesULT)
3354 return Found;
3355}
3356
3358 if (!L.isSafeToClone())
3359 return false;
3360 for (auto *BB : L.blocks())
3361 for (auto &I : *BB) {
3362 if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
3363 return false;
3365 assert(!CB->cannotDuplicate() && "Checked by L.isSafeToClone().");
3366 if (CB->isConvergent())
3367 return false;
3368 }
3369 }
3370
3371
3372
3373
3374
3375
3376
3380 return false;
3381
3383 L.getUniqueExitBlocks(ExitBlocks);
3384
3385
3386
3387
3388 for (auto *ExitBB : ExitBlocks) {
3389 auto It = ExitBB->getFirstNonPHIIt();
3391 LLVM_DEBUG(dbgs() << "Cannot unswitch because of cleanuppad/catchswitch "
3392 "in exit block\n");
3393 return false;
3394 }
3395 }
3396
3397 return true;
3398}
3399
3404
3405
3406
3407
3408
3412
3413
3414
3415
3416
3417
3419 L.getHeader()->getParent()->hasMinSize()
3423 for (auto *BB : L.blocks()) {
3425 for (auto &I : *BB) {
3427 continue;
3428 Cost += TTI.getInstructionCost(&I, CostKind);
3429 }
3430 assert(Cost >= 0 && "Must not have negative costs!");
3431 LoopCost += Cost;
3432 assert(LoopCost >= 0 && "Must not have negative loop costs!");
3433 BBCostMap[BB] = Cost;
3434 }
3435 LLVM_DEBUG(dbgs() << " Total loop cost: " << LoopCost << "\n");
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3452
3453
3454 auto ComputeUnswitchedCost = [&](Instruction &TI,
3456
3458 return LoopCost;
3459
3462
3465
3466 if (!Visited.insert(SuccBB).second)
3467 continue;
3468
3469
3470
3471
3472
3473
3474 if (!FullUnswitch) {
3478 if (SuccBB == BI.getSuccessor(1))
3479 continue;
3481 if (SuccBB == BI.getSuccessor(0))
3482 continue;
3484 SuccBB == BI.getSuccessor(0)) ||
3486 SuccBB == BI.getSuccessor(1)))
3487 continue;
3488 }
3489
3490
3491
3492
3493
3494 if (SuccBB->getUniquePredecessor() ||
3496 return PredBB == &BB || DT.dominates(SuccBB, PredBB);
3497 })) {
3499 assert(Cost <= LoopCost &&
3500 "Non-duplicated cost should never exceed total loop cost!");
3501 }
3502 }
3503
3504
3505
3506
3507
3508
3509 int SuccessorsCount = isGuard(&TI) ? 2 : Visited.size();
3510 assert(SuccessorsCount > 1 &&
3511 "Cannot unswitch a condition without multiple distinct successors!");
3512 return (LoopCost - Cost) * (SuccessorsCount - 1);
3513 };
3514
3515 std::optional Best;
3516 for (auto &Candidate : UnswitchCandidates) {
3520 bool FullUnswitch =
3521 !BI || Candidate.hasPendingInjection() ||
3522 (Invariants.size() == 1 &&
3524 InstructionCost CandidateCost = ComputeUnswitchedCost(TI, FullUnswitch);
3525
3526
3528 int CostMultiplier =
3532 "cost multiplier needs to be in the range of 1..UnswitchThreshold");
3533 CandidateCost *= CostMultiplier;
3534 LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost
3535 << " (multiplier: " << CostMultiplier << ")"
3536 << " for unswitch candidate: " << TI << "\n");
3537 } else {
3538 LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost
3539 << " for unswitch candidate: " << TI << "\n");
3540 }
3541
3542 if (!Best || CandidateCost < Best->Cost) {
3543 Best = Candidate;
3544 Best->Cost = CandidateCost;
3545 }
3546 }
3547 assert(Best && "Must be!");
3548 return *Best;
3549}
3550
3551
3552
3553
3554
3555
3556
3561 return false;
3562
3566 return false;
3567
3571 else
3574 Cond, &AC, L.getLoopPreheader()->getTerminator(), &DT);
3575}
3576
3582
3583
3586 Instruction *PartialIVCondBranch = nullptr;
3588 PartialIVCondBranch, L, LI, AA, MSSAU);
3591 PartialIVCondBranch, L, DT, LI, AA,
3592 MSSAU);
3593
3594 if (UnswitchCandidates.empty())
3595 return false;
3596
3598 dbgs() << "Considering " << UnswitchCandidates.size()
3599 << " non-trivial loop invariant conditions for unswitching.\n");
3600
3602 UnswitchCandidates, L, DT, LI, AC, TTI, PartialIVInfo);
3603
3604 assert(Best.TI && "Failed to find loop unswitch candidate");
3605 assert(Best.Cost && "Failed to compute cost");
3606
3608 LLVM_DEBUG(dbgs() << "Cannot unswitch, lowest cost found: " << *Best.Cost
3609 << "\n");
3610 return false;
3611 }
3612
3613 bool InjectedCondition = false;
3614 if (Best.hasPendingInjection()) {
3616 InjectedCondition = true;
3617 }
3618 assert(!Best.hasPendingInjection() &&
3619 "All injections should have been done by now!");
3620
3621 if (Best.TI != PartialIVCondBranch)
3623
3624 bool InsertFreeze;
3626
3627
3628
3629
3631 SI->getCondition(), &AC, L.getLoopPreheader()->getTerminator(), &DT);
3633 } else {
3634
3636 Best.TI =
3639 }
3640
3641 LLVM_DEBUG(dbgs() << " Unswitching non-trivial (cost = " << Best.Cost
3642 << ") terminator: " << *Best.TI << "\n");
3644 LI, AC, SE, MSSAU, LoopUpdater, InsertFreeze,
3645 InjectedCondition);
3646 return true;
3647}
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3675 assert(L.isRecursivelyLCSSAForm(DT, LI) &&
3676 "Loops must be in LCSSA form before unswitching.");
3677
3678
3679 if (!L.isLoopSimplifyForm())
3680 return false;
3681
3682
3684
3685
3687 true, false,
3688 false, {});
3689 return true;
3690 }
3691
3692 const Function *F = L.getHeader()->getParent();
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705 bool ContinueWithNonTrivial =
3707 if (!ContinueWithNonTrivial)
3708 return false;
3709
3710
3711 if (F->hasOptSize())
3712 return false;
3713
3714
3716 return false;
3717
3718
3719
3720
3721
3722
3723
3724
3725
3727 return true;
3728
3729
3730 return false;
3731}
3732
3736 Function &F = *L.getHeader()->getParent();
3737 (void)F;
3738 LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L
3739 << "\n");
3740
3741 std::optional MSSAU;
3742 if (AR.MSSA) {
3746 }
3748 &AR.SE, MSSAU ? &*MSSAU : nullptr, U))
3750
3753
3754
3755
3756 assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
3757
3759 if (AR.MSSA)
3761 return PA;
3762}
3763
3767 OS, MapClassName2PassName);
3768
3769 OS << '<';
3770 OS << (NonTrivial ? "" : "no-") << "nontrivial;";
3771 OS << (Trivial ? "" : "no-") << "trivial";
3772 OS << '>';
3773}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Analysis containing CSE Info
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
static Value * getCondition(Instruction *I)
Module.h This file contains the declarations for the Module class.
This defines the Use class.
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
This header provides classes for managing per-loop analyses.
Loop::LoopBounds::Direction Direction
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
uint64_t IntrinsicInst * II
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
Provides some synthesis utilities to produce sequences of values.
This file implements a set that has insertion order iteration characteristics.
static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH)
Rewrite the PHI nodes in an unswitched loop exit basic block.
Definition SimpleLoopUnswitch.cpp:401
static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
This routine scans the loop to find a branch or switch which occurs before any side effects occur.
Definition SimpleLoopUnswitch.cpp:1107
static SmallPtrSet< const BasicBlock *, 16 > recomputeLoopBlockSet(Loop &L, LoopInfo &LI)
Recompute the set of blocks in a loop after unswitching.
Definition SimpleLoopUnswitch.cpp:1855
static int CalculateUnswitchCostMultiplier(const Instruction &TI, const Loop &L, const LoopInfo &LI, const DominatorTree &DT, ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates)
Cost multiplier is a way to limit potentially exponential behavior of loop-unswitch.
Definition SimpleLoopUnswitch.cpp:2883
static TinyPtrVector< Value * > collectHomogenousInstGraphLoopInvariants(const Loop &L, Instruction &Root, const LoopInfo &LI)
Collect all of the loop invariant input values transitively used by the homogeneous instruction graph...
Definition SimpleLoopUnswitch.cpp:203
static void deleteDeadClonedBlocks(Loop &L, ArrayRef< BasicBlock * > ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy > > VMaps, DominatorTree &DT, MemorySSAUpdater *MSSAU)
Definition SimpleLoopUnswitch.cpp:1732
void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable)
Helper to visit a dominator subtree, invoking a callable on each node.
Definition SimpleLoopUnswitch.cpp:2175
static BranchInst * turnSelectIntoBranch(SelectInst *SI, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, AssumptionCache *AC)
Turns a select instruction into implicit control flow branch, making the following replacement:
Definition SimpleLoopUnswitch.cpp:2772
static bool isSafeForNoNTrivialUnswitching(Loop &L, LoopInfo &LI)
Definition SimpleLoopUnswitch.cpp:3357
void postUnswitch(Loop &L, LPMUpdater &U, StringRef LoopName, bool CurrentLoopValid, bool PartiallyInvariant, bool InjectedCondition, ArrayRef< Loop * > NewLoops)
Definition SimpleLoopUnswitch.cpp:2198
static bool shouldTryInjectInvariantCondition(const ICmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const BasicBlock *IfTrue, const BasicBlock *IfFalse, const Loop &L)
Returns true, if predicate described by ( Pred, LHS, RHS ) succeeding into blocks ( IfTrue,...
Definition SimpleLoopUnswitch.cpp:3100
static NonTrivialUnswitchCandidate findBestNonTrivialUnswitchCandidate(ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates, const Loop &L, const DominatorTree &DT, const LoopInfo &LI, AssumptionCache &AC, const TargetTransformInfo &TTI, const IVConditionInfo &PartialIVInfo)
Definition SimpleLoopUnswitch.cpp:3400
static Value * skipTrivialSelect(Value *Cond)
Definition SimpleLoopUnswitch.cpp:188
static Loop * getTopMostExitingLoop(const BasicBlock *ExitBB, const LoopInfo &LI)
Definition SimpleLoopUnswitch.cpp:540
static bool collectUnswitchCandidatesWithInjections(SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, Loop &L, const DominatorTree &DT, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU)
Collect unswitch candidates by invariant conditions that are not immediately present in the loop.
Definition SimpleLoopUnswitch.cpp:3302
static void replaceLoopInvariantUses(const Loop &L, Value *Invariant, Constant &Replacement)
Definition SimpleLoopUnswitch.cpp:245
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
Unswitch a trivial branch if the condition is loop invariant.
Definition SimpleLoopUnswitch.cpp:569
static bool collectUnswitchCandidates(SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, const Loop &L, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU)
Definition SimpleLoopUnswitch.cpp:2976
static InstructionCost computeDomSubtreeCost(DomTreeNode &N, const SmallDenseMap< BasicBlock *, InstructionCost, 4 > &BBCostMap, SmallDenseMap< DomTreeNode *, InstructionCost, 4 > &DTCostMap)
Recursively compute the cost of a dominator subtree based on the per-block cost map provided.
Definition SimpleLoopUnswitch.cpp:2721
static bool shouldInsertFreeze(Loop &L, Instruction &TI, DominatorTree &DT, AssumptionCache &AC)
Definition SimpleLoopUnswitch.cpp:3557
static void canonicalizeForInvariantConditionInjection(CmpPredicate &Pred, Value *&LHS, Value *&RHS, BasicBlock *&IfTrue, BasicBlock *&IfFalse, const Loop &L)
Tries to canonicalize condition described by:
Definition SimpleLoopUnswitch.cpp:3072
static bool areLoopExitPHIsLoopInvariant(const Loop &L, const BasicBlock &ExitingBB, const BasicBlock &ExitBB)
Check that all the LCSSA PHI nodes in the loop exit block have trivial incoming values along this edg...
Definition SimpleLoopUnswitch.cpp:262
static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB, BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH, bool FullUnswitch)
Rewrite the PHI nodes in the loop exit basic block and the split off unswitched block.
Definition SimpleLoopUnswitch.cpp:423
static bool insertCandidatesWithPendingInjections(SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, Loop &L, ICmpInst::Predicate Pred, ArrayRef< CompareDesc > Compares, const DominatorTree &DT)
Given chain of loop branch conditions looking like: br (Variant < Invariant1) br (Variant < Invariant...
Definition SimpleLoopUnswitch.cpp:3264
static NonTrivialUnswitchCandidate injectPendingInvariantConditions(NonTrivialUnswitchCandidate Candidate, Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, MemorySSAUpdater *MSSAU)
Materialize pending invariant condition of the given candidate into IR.
Definition SimpleLoopUnswitch.cpp:3162
static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
Unswitch a trivial switch if the condition is loop invariant.
Definition SimpleLoopUnswitch.cpp:803
static void unswitchNontrivialInvariants(Loop &L, Instruction &TI, ArrayRef< Value * > Invariants, IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater, bool InsertFreeze, bool InjectedCondition)
Definition SimpleLoopUnswitch.cpp:2235
static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef< BasicBlock * > ExitBlocks, LoopInfo &LI, SmallVectorImpl< Loop * > &HoistedLoops, ScalarEvolution *SE)
Rebuild a loop after unswitching removes some subset of blocks and edges.
Definition SimpleLoopUnswitch.cpp:1966
static bool unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater)
Definition SimpleLoopUnswitch.cpp:3577
static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, bool Trivial, bool NonTrivial, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater)
Unswitch control flow predicated on loop invariant conditions.
Definition SimpleLoopUnswitch.cpp:3670
static void buildPartialInvariantUnswitchConditionalBranch(BasicBlock &BB, ArrayRef< Value * > ToDuplicate, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L, MemorySSAUpdater *MSSAU, const BranchInst &OriginalBranch)
Copy a set of loop invariant values, and conditionally branch on them.
Definition SimpleLoopUnswitch.cpp:337
static BasicBlock * buildClonedLoopBlocks(Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, ArrayRef< BasicBlock * > ExitBlocks, BasicBlock *ParentBB, BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, const SmallDenseMap< BasicBlock *, BasicBlock *, 16 > &DominatingSucc, ValueToValueMapTy &VMap, SmallVectorImpl< DominatorTree::UpdateType > &DTUpdates, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE)
Build the cloned blocks for an unswitched copy of the given loop.
Definition SimpleLoopUnswitch.cpp:1226
static void deleteDeadBlocksFromLoop(Loop &L, SmallVectorImpl< BasicBlock * > &ExitBlocks, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE, LPMUpdater &LoopUpdater)
Definition SimpleLoopUnswitch.cpp:1761
bool shouldTryInjectBasingOnMetadata(const BranchInst *BI, const BasicBlock *TakenSucc)
Returns true, if metadata on BI allows us to optimize branching into TakenSucc via injection of invar...
Definition SimpleLoopUnswitch.cpp:3122
static BranchInst * turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
Turns a llvm.experimental.guard intrinsic into implicit control flow branch, making the following rep...
Definition SimpleLoopUnswitch.cpp:2823
static Loop * cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, const ValueToValueMapTy &VMap, LoopInfo &LI)
Recursively clone the specified loop and all of its children.
Definition SimpleLoopUnswitch.cpp:1423
static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE)
Hoist the current loop up to the innermost loop containing a remaining exit.
Definition SimpleLoopUnswitch.cpp:469
static void buildClonedLoops(Loop &OrigL, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, LoopInfo &LI, SmallVectorImpl< Loop * > &NonChildClonedLoops)
Build the cloned loops of an original loop from unswitching.
Definition SimpleLoopUnswitch.cpp:1482
static void buildPartialUnswitchConditionalBranch(BasicBlock &BB, ArrayRef< Value * > Invariants, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze, const Instruction *I, AssumptionCache *AC, const DominatorTree &DT, const BranchInst &ComputeProfFrom)
Copy a set of loop invariant values Invariants and insert them at the end of BB and conditionally bra...
Definition SimpleLoopUnswitch.cpp:289
This file defines the SmallPtrSet 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...
#define STATISTIC(VARNAME, DESC)
This pass exposes codegen information to IR-level passes.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
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 ...
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...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
LLVM_ABI void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static LLVM_ABI CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static LLVM_ABI bool isStrictPredicate(Predicate predicate)
This is a static version that you can use without an instruction available.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static DebugLoc getCompilerGenerated()
static DebugLoc getDropped()
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
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.
This class represents a freeze function that returns random concrete value if an operand is either a ...
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI void dropLocation()
Drop the instruction's debug location.
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 ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
bool isTerminator() const
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
A wrapper class for inspecting calls to intrinsic functions.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
BlockT * getHeader() const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
void reserveBlocks(unsigned size)
interface to do reserve() for Blocks
iterator_range< block_iterator > blocks() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
void perform(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
Represents a single loop in the control flow graph.
StringRef getName() const
LLVM_ABI MDNode * createUnlikelyBranchWeights()
Return metadata containing two branch weights, with significant bias towards false destination.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
static LLVM_ABI MDString * get(LLVMContext &Context, StringRef Str)
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
An analysis that produces MemorySSA for a function.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
LLVM_ABI void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
LLVM_ABI void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones=false)
Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 ma...
LLVM_ABI void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
LLVM_ABI void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
LLVM_ABI void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
LLVM_ABI MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point, bool CreationMustSucceed=true)
Create a MemoryAccess in MemorySSA at a specified point in a block.
LLVM_ABI void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
LLVM_ABI void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
LLVM_ABI void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
LLVM_ABI void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
Encapsulates MemorySSA, including all data associated with memory accesses.
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
A Module instance is used to store all the information related to an LLVM module.
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 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.
The main scalar evolution driver.
LLVM_ABI 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...
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
size_type count(const_arg_type key) const
Count the number of elements of a given key in 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.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition SimpleLoopUnswitch.cpp:3764
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition SimpleLoopUnswitch.cpp:3733
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI Instruction::InstListType::iterator eraseFromParent()
Delegate the call to the underlying SwitchInst::eraseFromParent() and mark this object to not touch t...
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
unsigned getSuccessorIndex() const
Returns successor index for current case successor.
BasicBlockT * getCaseSuccessor() const
Resolves successor for current case.
ConstantIntT * getCaseValue() const
Resolves case value for current case.
BasicBlock * getDefaultDest() const
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, InsertPosition InsertBefore=nullptr)
void setDefaultDest(BasicBlock *DefaultCase)
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
TargetCostKind
The kind of cost model.
@ TCK_CodeSize
Instruction code size.
@ TCK_SizeAndLatency
The weighted sum of size and latency.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
void push_back(EltTy NewVal)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
A Use represents the edge between a Value definition and its users.
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
LLVM Value Representation.
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
self_iterator getIterator()
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.
Abstract Attribute helper functions.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ?
bool match(Val *V, const Pattern &P)
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ?
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
initializer< Ty > init(const Ty &Val)
friend class Instruction
Iterator for Instructions in a `BasicBlock.
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.
FunctionAddr VTableAddr Value
void stable_sort(R &&Range)
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.
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.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
static cl::opt< int > UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop."))
auto successors(const MachineBasicBlock *BB)
static cl::opt< bool > EnableNonTrivialUnswitch("enable-nontrivial-unswitch", cl::init(false), cl::Hidden, cl::desc("Forcibly enables non-trivial loop unswitching rather than " "following the configuration passed into the pass."))
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
auto cast_or_null(const Y &Val)
LLVM_ABI MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)
Returns a concatenated range across two or more ranges.
DomTreeNodeBase< BasicBlock > DomTreeNode
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
static cl::opt< bool > EnableUnswitchCostMultiplier("enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, cl::desc("Enable unswitch cost multiplier that prohibits exponential " "explosion in nontrivial unswitch."))
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.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
auto reverse(ContainerTy &&C)
static cl::opt< bool > DropNonTrivialImplicitNullChecks("simple-loop-unswitch-drop-non-trivial-implicit-null-checks", cl::init(false), cl::Hidden, cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " "null checks to save time analyzing if we can keep it."))
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
static cl::opt< unsigned > InjectInvariantConditionHotnesThreshold("simple-loop-unswitch-inject-invariant-condition-hotness-threshold", cl::Hidden, cl::desc("Only try to inject loop invariant conditions and " "unswitch on them to eliminate branches that are " "not-taken 1/ times or less."), cl::init(16))
static cl::opt< int > UnswitchSiblingsToplevelDiv("unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, cl::desc("Toplevel siblings divisor for cost multiplier."))
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&...args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static cl::opt< bool > InjectInvariantConditions("simple-loop-unswitch-inject-invariant-conditions", cl::Hidden, cl::desc("Whether we should inject new invariants and unswitch them to " "eliminate some existing (non-invariant) conditions."), cl::init(true))
LLVM_ABI bool VerifyLoopInfo
Enable verification of loop info.
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
FunctionAddr VTableAddr Next
LLVM_ABI bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
ArrayRef(const T &OneElt) -> ArrayRef< T >
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
static cl::opt< int > UnswitchNumInitialUnscaledCandidates("unswitch-num-initial-unscaled-candidates", cl::init(8), cl::Hidden, cl::desc("Number of unswitch candidates that are ignored when calculating " "cost multiplier."))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
static cl::opt< bool > EstimateProfile("simple-loop-unswitch-estimate-profile", cl::Hidden, cl::init(true))
LLVM_ABI llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)
Create a new LoopID after the loop has been transformed.
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
static cl::opt< bool > FreezeLoopUnswitchCond("freeze-loop-unswitch-cond", cl::init(true), cl::Hidden, cl::desc("If enabled, the freeze instruction will be added to condition " "of loop unswitch to prevent miscompilation."))
LLVM_ABI std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
LLVM_ABI bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
static cl::opt< bool > UnswitchGuards("simple-loop-unswitch-guards", cl::init(true), cl::Hidden, cl::desc("If enabled, simple loop unswitching will also consider " "llvm.experimental.guard intrinsics as unswitch candidates."))
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
static cl::opt< int > UnswitchParentBlocksDiv("unswitch-parent-blocks-div", cl::init(8), cl::Hidden, cl::desc("Outer loop size divisor for cost multiplier."))
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static LLVM_ABI void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Struct to hold information about a partially invariant condition.
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
A CRTP mix-in to automatically provide informational APIs needed for passes.