LLVM: lib/Transforms/Scalar/JumpThreading.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
71#include
72#include
73#include
74#include
75#include
76
77using namespace llvm;
78using namespace jumpthreading;
79
80#define DEBUG_TYPE "jump-threading"
81
82STATISTIC(NumThreads, "Number of jumps threaded");
83STATISTIC(NumFolds, "Number of terminators folded");
84STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi");
85
88 cl::desc("Max block size to duplicate for jump threading"),
90
93 "jump-threading-implication-search-threshold",
94 cl::desc("The number of predecessors to search for a stronger "
95 "condition to use to thread over a weaker condition"),
97
99 "jump-threading-phi-threshold",
100 cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76),
102
104 "jump-threading-across-loop-headers",
105 cl::desc("Allow JumpThreading to thread across loop headers, for testing"),
107
110}
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
149 if (!CondBr)
150 return;
151
152 uint64_t TrueWeight, FalseWeight;
154 return;
155
156 if (TrueWeight + FalseWeight == 0)
157
158
159
160 return;
161
162
163
164 auto GetPredOutEdge =
166 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
167 auto *PredBB = IncomingBB;
168 auto *SuccBB = PhiBB;
170 while (true) {
171 BranchInst *PredBr = dyn_cast(PredBB->getTerminator());
173 return {PredBB, SuccBB};
174 Visited.insert(PredBB);
175 auto *SinglePredBB = PredBB->getSinglePredecessor();
176 if (!SinglePredBB)
177 return {nullptr, nullptr};
178
179
180
181 if (Visited.count(SinglePredBB))
182 return {nullptr, nullptr};
183
184 SuccBB = PredBB;
185 PredBB = SinglePredBB;
186 }
187 };
188
191 ConstantInt *CI = dyn_cast(PhiOpnd);
192
194 continue;
195
198 TrueWeight, TrueWeight + FalseWeight)
200 FalseWeight, TrueWeight + FalseWeight));
201
202 auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB);
203 if (!PredOutEdge.first)
204 return;
205
206 BasicBlock *PredBB = PredOutEdge.first;
208 if (!PredBr)
209 return;
210
211 uint64_t PredTrueWeight, PredFalseWeight;
212
213
214
215
217 continue;
218
219
220
222 continue;
223
225 if (PredBr->getSuccessor(0) == PredOutEdge.second) {
228 } else {
231 }
233 }
234}
235
239
246
247 bool Changed =
249 std::make_unique(
250 &DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy),
251 std::nullopt, std::nullopt);
252
253 if (!Changed)
255
256
258
259#if defined(EXPENSIVE_CHECKS)
261 DominatorTree::VerificationLevel::Full) &&
262 "DT broken after JumpThreading");
266 "PDT broken after JumpThreading");
267#else
269 DominatorTree::VerificationLevel::Fast) &&
270 "DT broken after JumpThreading");
274 "PDT broken after JumpThreading");
275#endif
276
277 return getPreservedAnalysis();
278}
279
284 std::unique_ptr DTU_,
285 std::optional<BlockFrequencyInfo *> BFI_,
286 std::optional<BranchProbabilityInfo *> BPI_) {
288 F = &F_;
289 FAM = FAM_;
290 TLI = TLI_;
291 TTI = TTI_;
292 LVI = LVI_;
293 AA = AA_;
294 DTU = std::move(DTU_);
295 BFI = BFI_;
296 BPI = BPI_;
298 F->getParent(), Intrinsic::experimental_guard);
299 HasGuards = GuardDecl && !GuardDecl->use_empty();
300
301
302
306 BBDupThreshold = 3;
307 else
308 BBDupThreshold = DefaultBBDupThreshold;
309
310
311
313 assert(DTU && "DTU isn't passed into JumpThreading before using it.");
314 assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
316 for (auto &BB : *F)
318 Unreachable.insert(&BB);
319
322
323 bool EverChanged = false;
324 bool Changed;
325 do {
326 Changed = false;
327 for (auto &BB : *F) {
328 if (Unreachable.count(&BB))
329 continue;
330 while (processBlock(&BB))
331 Changed = ChangedSinceLastAnalysisUpdate = true;
332
333
334
335 if (Changed)
337
338
339
340
341 if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
342 continue;
343
345
346
347 LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName()
348 << "' with terminator: " << *BB.getTerminator()
349 << '\n');
350 LoopHeaders.erase(&BB);
353 Changed = ChangedSinceLastAnalysisUpdate = true;
354 continue;
355 }
356
357
358
359 auto *BI = dyn_cast(BB.getTerminator());
360 if (BI && BI->isUnconditional()) {
361 BasicBlock *Succ = BI->getSuccessor(0);
362 if (
363
364 BB.getFirstNonPHIOrDbg(true)->isTerminator() &&
365
366
367 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
370
371
373 Changed = ChangedSinceLastAnalysisUpdate = true;
374 }
375 }
376 }
377 EverChanged |= Changed;
378 } while (Changed);
379
380 LoopHeaders.clear();
381 return EverChanged;
382}
383
384
385
386
387
388
389
390
393 bool Changed = false;
395
396
397
398 if (Cond->getParent() == KnownAtEndOfBB)
401
403 DVR.replaceVariableLocationOp(Cond, ToVal, true);
404
405
406
408 break;
409
410
412 break;
413 Changed |= I.replaceUsesOfWith(Cond, ToVal);
414 }
415 if (Cond->use_empty() && ->mayHaveSideEffects()) {
416 Cond->eraseFromParent();
417 Changed = true;
418 }
419 return Changed;
420}
421
422
423
424
428 unsigned Threshold) {
429 assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
430
431
432
433
434 unsigned PhiCount = 0;
437 if (!isa(&I)) {
438 FirstNonPHI = &I;
439 break;
440 }
442 return ~0U;
443 }
444
445
447
448
449
450
451 unsigned Bonus = 0;
453
454
455
456 if (isa(StopAt))
457 Bonus = 6;
458
459
460 if (isa(StopAt))
461 Bonus = 8;
462 }
463
464
465
466 Threshold += Bonus;
467
468
469
470 unsigned Size = 0;
471 for (; &*I != StopAt; ++I) {
472
473
474 if (Size > Threshold)
476
477
478
479 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
480 return ~0U;
481
482
483
484 if (const CallInst *CI = dyn_cast(I))
485 if (CI->cannotDuplicate() || CI->isConvergent())
486 return ~0U;
487
490 continue;
491
492
494
495
496
497
498
499 if (const CallInst *CI = dyn_cast(I)) {
500 if (!isa(CI))
502 else if (!CI->getType()->isVectorTy())
504 }
505 }
506
507 return Size > Bonus ? Size - Bonus : 0;
508}
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
527
528 for (const auto &Edge : Edges)
529 LoopHeaders.insert(Edge.second);
530}
531
532
533
534
535
536
538 if (!Val)
539 return nullptr;
540
541
542 if (UndefValue *U = dyn_cast(Val))
543 return U;
544
547
548 return dyn_cast(Val);
549}
550
551
552
553
554
555
556
562
563
564
565
566
567 if (!RecursionSet.insert(V).second)
568 return false;
569
570
573 Result.emplace_back(KC, Pred);
574
575 return !Result.empty();
576 }
577
578
579
581 if ( || I->getParent() != BB) {
582
583
584
586 using namespace PatternMatch;
587
588
590
591
592
593
600 Result.emplace_back(KC, P);
601 }
602
603 return !Result.empty();
604 }
605
606
607 if (PHINode *PN = dyn_cast(I)) {
608 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
609 Value *InVal = PN->getIncomingValue(i);
611 Result.emplace_back(KC, PN->getIncomingBlock(i));
612 } else {
614 PN->getIncomingBlock(i),
615 BB, CxtI);
617 Result.emplace_back(KC, PN->getIncomingBlock(i));
618 }
619 }
620
621 return !Result.empty();
622 }
623
624
625 if (CastInst *CI = dyn_cast(I)) {
626 Value *Source = CI->getOperand(0);
629 RecursionSet, CxtI);
630 if (Vals.empty())
631 return false;
632
633
634 for (auto &Val : Vals)
636 CI->getType(), DL))
637 Result.emplace_back(Folded, Val.second);
638
639 return !Result.empty();
640 }
641
642 if (FreezeInst *FI = dyn_cast(I)) {
643 Value *Source = FI->getOperand(0);
645 RecursionSet, CxtI);
646
647 erase_if(Result, [](auto &Pair) {
649 });
650
651 return !Result.empty();
652 }
653
654
655 if (I->getType()->getPrimitiveSizeInBits() == 1) {
656 using namespace PatternMatch;
658 return false;
659
660
661 Value *Op0, *Op1;
665
667 RecursionSet, CxtI);
669 RecursionSet, CxtI);
670
671 if (LHSVals.empty() && RHSVals.empty())
672 return false;
673
677 else
679
681
682
683
684 for (const auto &LHSVal : LHSVals)
685 if (LHSVal.first == InterestingVal || isa(LHSVal.first)) {
686 Result.emplace_back(InterestingVal, LHSVal.second);
687 LHSKnownBBs.insert(LHSVal.second);
688 }
689 for (const auto &RHSVal : RHSVals)
690 if (RHSVal.first == InterestingVal || isa(RHSVal.first)) {
691
692
693 if (!LHSKnownBBs.count(RHSVal.second))
694 Result.emplace_back(InterestingVal, RHSVal.second);
695 }
696
697 return !Result.empty();
698 }
699
700
701 if (I->getOpcode() == Instruction::Xor &&
702 isa(I->getOperand(1)) &&
703 cast(I->getOperand(1))->isOne()) {
706 if (Result.empty())
707 return false;
708
709
710 for (auto &R : Result)
712
713 return true;
714 }
715
716
717 } else if (BinaryOperator *BO = dyn_cast(I)) {
719 return false;
720 if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) {
724
725
726 for (const auto &LHSVal : LHSVals) {
730
732 Result.emplace_back(KC, LHSVal.second);
733 }
734 }
735
736 return !Result.empty();
737 }
738
739
740 if (CmpInst *Cmp = dyn_cast(I)) {
742 return false;
743 Type *CmpType = Cmp->getType();
744 Value *CmpLHS = Cmp->getOperand(0);
745 Value *CmpRHS = Cmp->getOperand(1);
747
748 PHINode *PN = dyn_cast(CmpLHS);
749 if (!PN)
750 PN = dyn_cast(CmpRHS);
751
752
753
754 if (PN && PN->getParent() == BB && !LoopHeaders.contains(BB)) {
756
757
761 if (PN == CmpLHS) {
764 } else {
767 }
769 if (!Res) {
770 if (!isa(RHS))
771 continue;
772
773
774 auto LHSInst = dyn_cast(LHS);
775 if (LHSInst && LHSInst->getParent() == BB)
776 continue;
777
779 BB, CxtI ? CxtI : Cmp);
780 }
781
783 Result.emplace_back(KC, PredBB);
784 }
785
786 return !Result.empty();
787 }
788
789
790
791 if (isa(CmpRHS) && !CmpType->isVectorTy()) {
792 Constant *CmpConst = cast(CmpRHS);
793
794 if (!isa(CmpLHS) ||
795 cast(CmpLHS)->getParent() != BB) {
797
798
800 CxtI ? CxtI : Cmp);
802 Result.emplace_back(KC, P);
803 }
804
805 return !Result.empty();
806 }
807
808
809
810
811 {
812 using namespace PatternMatch;
813
816 if (isa(CmpConst) &&
818 if (!isa(AddLHS) ||
819 cast(AddLHS)->getParent() != BB) {
821
822
823
825 AddLHS, P, BB, CxtI ? CxtI : cast(CmpLHS));
826
828
829
831 Pred, cast(CmpConst)->getValue());
832
838 else
839 continue;
840
841 Result.emplace_back(ResC, P);
842 }
843
844 return !Result.empty();
845 }
846 }
847 }
848
849
850
854
855 for (const auto &LHSVal : LHSVals) {
860 Result.emplace_back(KC, LHSVal.second);
861 }
862
863 return !Result.empty();
864 }
865 }
866
867 if (SelectInst *SI = dyn_cast(I)) {
868
869
873 if ((TrueVal || FalseVal) &&
876 for (auto &C : Conds) {
878
879
880 bool KnownCond;
882
883 KnownCond = CI->isOne();
884 } else {
885 assert(isa(Cond) && "Unexpected condition value");
886
887
888
889 KnownCond = (TrueVal != nullptr);
890 }
891
892
893 if (Constant *Val = KnownCond ? TrueVal : FalseVal)
894 Result.emplace_back(Val, C.second);
895 }
896
897 return !Result.empty();
898 }
899 }
900
901
902 assert(CxtI->getParent() == BB && "CxtI should be in BB");
906 Result.emplace_back(KC, Pred);
907 }
908
909 return !Result.empty();
910}
911
912
913
914
915
916
919 unsigned MinSucc = 0;
921
922 unsigned MinNumPreds = pred_size(TestBB);
923 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
925 unsigned NumPreds = pred_size(TestBB);
926 if (NumPreds < MinNumPreds) {
927 MinSucc = i;
928 MinNumPreds = NumPreds;
929 }
930 }
931
932 return MinSucc;
933}
934
937
938
939
943}
944
945
946
948
949
950 if (DTU->isBBPendingDeletion(BB) ||
952 return false;
953
954
955
956
957
959 return true;
960
962 return true;
963
964
966 return true;
967
968
970
971
972
973 Value *Condition;
975 if (BranchInst *BI = dyn_cast(Terminator)) {
976
977 if (BI->isUnconditional()) return false;
978 Condition = BI->getCondition();
979 } else if (SwitchInst *SI = dyn_cast(Terminator)) {
980 Condition = SI->getCondition();
981 } else if (IndirectBrInst *IB = dyn_cast(Terminator)) {
982
983 if (IB->getNumSuccessors() == 0) return false;
984 Condition = IB->getAddress()->stripPointerCasts();
986 } else {
987 return false;
988 }
989
990
991 bool ConstantFolded = false;
992
993
994
995 if (Instruction *I = dyn_cast(Condition)) {
996 Value *SimpleVal =
998 if (SimpleVal) {
999 I->replaceAllUsesWith(SimpleVal);
1001 I->eraseFromParent();
1002 Condition = SimpleVal;
1003 ConstantFolded = true;
1004 }
1005 }
1006
1007
1008
1009 auto *FI = dyn_cast(Condition);
1010 if (isa(Condition) ||
1011 (FI && isa(FI->getOperand(0)) && FI->hasOneUse())) {
1013 std::vectorDominatorTree::UpdateType Updates;
1014
1015
1018 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
1019 if (i == BestSucc) continue;
1023 }
1024
1026 << "' folding undef terminator: " << *BBTerm << '\n');
1029 ++NumFolds;
1031 DTU->applyUpdatesPermissive(Updates);
1032 if (FI)
1033 FI->eraseFromParent();
1034 return true;
1035 }
1036
1037
1038
1039
1042 << "' folding terminator: " << *BB->getTerminator()
1043 << '\n');
1044 ++NumFolds;
1046 if (auto *BPI = getBPI())
1047 BPI->eraseBlock(BB);
1048 return true;
1049 }
1050
1051 Instruction *CondInst = dyn_cast(Condition);
1052
1053
1054 if (!CondInst) {
1055
1057 return true;
1058 return ConstantFolded;
1059 }
1060
1061
1062 Value *CondWithoutFreeze = CondInst;
1063 if (auto *FI = dyn_cast(CondInst))
1064 CondWithoutFreeze = FI->getOperand(0);
1065
1066 if (CmpInst *CondCmp = dyn_cast(CondWithoutFreeze)) {
1067
1068
1069
1070 if (Constant *CondConst = dyn_cast(CondCmp->getOperand(1))) {
1072 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1074 false);
1075 if (Res) {
1076
1077
1078
1079
1080
1081
1082
1084 return true;
1085 }
1086
1087
1088
1090 return true;
1091 }
1092 }
1093
1096 return true;
1097
1098
1099
1100
1101
1102 Value *SimplifyValue = CondWithoutFreeze;
1103
1104 if (CmpInst *CondCmp = dyn_cast(SimplifyValue))
1105 if (isa(CondCmp->getOperand(1)))
1106 SimplifyValue = CondCmp->getOperand(0);
1107
1108
1109
1110 if (LoadInst *LoadI = dyn_cast(SimplifyValue))
1112 return true;
1113
1114
1115 if (PHINode *PN = dyn_cast(CondInst))
1116 if (PN->getParent() == BB && isa(BB->getTerminator()))
1118
1119
1120
1121
1123 return true;
1124
1125
1126
1127 PHINode *PN = dyn_cast(CondWithoutFreeze);
1130
1131
1132 if (CondInst->getOpcode() == Instruction::Xor &&
1135
1136
1137
1139 return true;
1140
1141 return false;
1142}
1143
1145 auto *BI = dyn_cast(BB->getTerminator());
1146 if (!BI || !BI->isConditional())
1147 return false;
1148
1149 Value *Cond = BI->getCondition();
1150
1151
1152
1153
1154
1155 auto *FICond = dyn_cast(Cond);
1156 if (FICond && FICond->hasOneUse())
1157 Cond = FICond->getOperand(0);
1158 else
1159 FICond = nullptr;
1160
1163 unsigned Iter = 0;
1164
1166
1168 auto *PBI = dyn_cast(CurrentPred->getTerminator());
1169 if (!PBI || !PBI->isConditional())
1170 return false;
1171 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1172 return false;
1173
1174 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1175 std::optional Implication =
1177
1178
1179
1180 if (!Implication && FICond && isa(PBI->getCondition())) {
1181 if (cast(PBI->getCondition())->getOperand(0) ==
1182 FICond->getOperand(0))
1183 Implication = CondIsTrue;
1184 }
1185
1186 if (Implication) {
1187 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1188 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1191 UncondBI->setDebugLoc(BI->getDebugLoc());
1192 ++NumFolds;
1193 BI->eraseFromParent();
1194 if (FICond)
1195 FICond->eraseFromParent();
1196
1198 if (auto *BPI = getBPI())
1199 BPI->eraseBlock(BB);
1200 return true;
1201 }
1202 CurrentBB = CurrentPred;
1204 }
1205
1206 return false;
1207}
1208
1209
1211 if (Instruction *OpInst = dyn_cast(Op))
1212 if (OpInst->getParent() == BB)
1213 return true;
1214 return false;
1215}
1216
1217
1218
1219
1220
1222
1223 if (!LoadI->isUnordered()) return false;
1224
1225
1226
1229 return false;
1230
1231
1232
1233
1235 return false;
1236
1238
1239
1240
1241 if (isOpDefinedInBlock(LoadedPtr, LoadBB) && !isa(LoadedPtr))
1242 return false;
1243
1244
1245
1247 bool IsLoadCSE;
1249
1252 LoadI, LoadBB, BBIt, DefMaxInstsToScan, &BatchAA, &IsLoadCSE)) {
1253
1254
1255
1256 if (IsLoadCSE) {
1257 LoadInst *NLoadI = cast(AvailableVal);
1260 };
1261
1262
1263
1264 if (AvailableVal == LoadI)
1266 if (AvailableVal->getType() != LoadI->getType()) {
1269 cast(AvailableVal)->setDebugLoc(LoadI->getDebugLoc());
1270 }
1273 return true;
1274 }
1275
1276
1277
1278
1279 if (BBIt != LoadBB->begin())
1280 return false;
1281
1282
1283
1285
1287
1289
1290 AvailablePredsTy AvailablePreds;
1291 BasicBlock *OneUnavailablePred = nullptr;
1293
1294
1295
1297
1298 if (!PredsScanned.insert(PredBB).second)
1299 continue;
1300
1301 BBIt = PredBB->end();
1302 unsigned NumScanedInst = 0;
1303 Value *PredAvailable = nullptr;
1304
1305
1307 "Attempting to CSE volatile or atomic loads");
1308
1309
1314 AATags);
1317 &BatchAA, &IsLoadCSE, &NumScanedInst);
1318
1319
1320
1322 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
1325 if (SinglePredBB) {
1326 BBIt = SinglePredBB->end();
1328 Loc, AccessTy, LoadI->isAtomic(), SinglePredBB, BBIt,
1330 &NumScanedInst);
1331 }
1332 }
1333
1334 if (!PredAvailable) {
1335 OneUnavailablePred = PredBB;
1336 continue;
1337 }
1338
1339 if (IsLoadCSE)
1340 CSELoads.push_back(cast(PredAvailable));
1341
1342
1343
1344 AvailablePreds.emplace_back(PredBB, PredAvailable);
1345 }
1346
1347
1348
1349 if (AvailablePreds.empty()) return false;
1350
1351
1352
1353
1354
1355
1356 BasicBlock *UnavailablePred = nullptr;
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366 if (PredsScanned.size() != AvailablePreds.size() &&
1368 for (auto I = LoadBB->begin(); &*I != LoadI; ++I)
1370 return false;
1371
1372
1373
1374
1375 if (PredsScanned.size() == AvailablePreds.size()+1 &&
1377 UnavailablePred = OneUnavailablePred;
1378 } else if (PredsScanned.size() != AvailablePreds.size()) {
1379
1380
1383
1384 for (const auto &AvailablePred : AvailablePreds)
1385 AvailablePredSet.insert(AvailablePred.first);
1386
1387
1389
1390 if (isa(P->getTerminator()))
1391 return false;
1392
1393 if (!AvailablePredSet.count(P))
1395 }
1396
1397
1398 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split");
1399 }
1400
1401
1402
1403
1404 if (UnavailablePred) {
1406 "Can't handle critical edge here!");
1413 if (AATags)
1415
1416 AvailablePreds.emplace_back(UnavailablePred, NewVal);
1417 }
1418
1419
1420
1421 array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
1422
1423
1428
1429
1430
1432 AvailablePredsTy::iterator I =
1434
1435 assert(I != AvailablePreds.end() && I->first == P &&
1436 "Didn't find entry for predecessor!");
1437
1438
1439
1440
1441
1442 Value *&PredV = I->second;
1445 PredV, LoadI->getType(), "", P->getTerminator()->getIterator());
1446
1448 }
1449
1450 for (LoadInst *PredLoadI : CSELoads) {
1453 }
1454
1457
1458 return true;
1459}
1460
1461
1462
1463
1468 assert(!PredToDestList.empty());
1469
1470
1471
1472
1473
1475
1476
1477
1478
1479
1480 DestPopularity[nullptr] = 0;
1482 DestPopularity[SuccBB] = 0;
1483
1484 for (const auto &PredToDest : PredToDestList)
1485 if (PredToDest.second)
1486 DestPopularity[PredToDest.second]++;
1487
1488
1490
1491
1492 return MostPopular->first;
1493}
1494
1495
1496
1502 assert(PredBB && "Expected a single predecessor");
1503
1504 if (Constant *Cst = dyn_cast(V)) {
1505 return Cst;
1506 }
1507
1508
1510 if ( || (I->getParent() != BB && I->getParent() != PredBB)) {
1512 }
1513
1514
1515 if (PHINode *PHI = dyn_cast(V)) {
1516 if (PHI->getParent() == PredBB)
1517 return dyn_cast(PHI->getIncomingValueForBlock(PredPredBB));
1518 return nullptr;
1519 }
1520
1521
1522 if (CmpInst *CondCmp = dyn_cast(V)) {
1523 if (CondCmp->getParent() == BB) {
1528 if (Op0 && Op1) {
1530 Op1, DL);
1531 }
1532 }
1533 return nullptr;
1534 }
1535
1536 return nullptr;
1537}
1538
1542
1543
1544 if (LoopHeaders.count(BB))
1545 return false;
1546
1549 CxtI)) {
1550
1551
1553 }
1554
1556 "computeValueKnownInPredecessors returned true with no values");
1557
1559 for (const auto &PredValue : PredValues) {
1561 << "': FOUND condition = " << *PredValue.first
1562 << " for pred '" << PredValue.second->getName() << "'.\n";
1563 });
1564
1565
1566
1567
1568
1571
1574 Constant *OnlyVal = nullptr;
1576
1577 for (const auto &PredValue : PredValues) {
1578 BasicBlock *Pred = PredValue.second;
1579 if (!SeenPreds.insert(Pred).second)
1580 continue;
1581
1582 Constant *Val = PredValue.first;
1583
1585 if (isa(Val))
1586 DestBB = nullptr;
1588 assert(isa(Val) && "Expecting a constant integer");
1589 DestBB = BI->getSuccessor(cast(Val)->isZero());
1591 assert(isa(Val) && "Expecting a constant integer");
1592 DestBB = SI->findCaseValue(cast(Val))->getCaseSuccessor();
1593 } else {
1595 && "Unexpected terminator");
1596 assert(isa(Val) && "Expecting a constant blockaddress");
1597 DestBB = cast(Val)->getBasicBlock();
1598 }
1599
1600
1601 if (PredToDestList.empty()) {
1602 OnlyDest = DestBB;
1603 OnlyVal = Val;
1604 } else {
1605 if (OnlyDest != DestBB)
1606 OnlyDest = MultipleDestSentinel;
1607
1608
1609 if (Val != OnlyVal)
1610 OnlyVal = MultipleVal;
1611 }
1612
1613
1614
1616 continue;
1617
1619 }
1620
1621
1622 if (PredToDestList.empty())
1623 return false;
1624
1625
1626
1627
1628 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1630 bool SeenFirstBranchToOnlyDest = false;
1631 std::vector DominatorTree::UpdateType Updates;
1634 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1635 SeenFirstBranchToOnlyDest = true;
1636 } else {
1637 SuccBB->removePredecessor(BB, true);
1639 }
1640 }
1641
1642
1645 NewBI->setDebugLoc(Term->getDebugLoc());
1646 ++NumFolds;
1647 Term->eraseFromParent();
1648 DTU->applyUpdatesPermissive(Updates);
1649 if (auto *BPI = getBPI())
1650 BPI->eraseBlock(BB);
1651
1652
1653
1654 if (auto *CondInst = dyn_cast(Cond)) {
1655 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1656 CondInst->eraseFromParent();
1657
1658
1659
1660
1661
1662
1663
1664 else if (OnlyVal && OnlyVal != MultipleVal)
1666 }
1667 return true;
1668 }
1669 }
1670
1671
1672
1673
1674
1675 BasicBlock *MostPopularDest = OnlyDest;
1676
1677 if (MostPopularDest == MultipleDestSentinel) {
1678
1679
1680
1682 [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1683 return LoopHeaders.contains(PredToDest.second);
1684 });
1685
1686 if (PredToDestList.empty())
1687 return false;
1688
1690 }
1691
1692
1693
1695 for (const auto &PredToDest : PredToDestList)
1696 if (PredToDest.second == MostPopularDest) {
1697 BasicBlock *Pred = PredToDest.first;
1698
1699
1700
1701
1703 if (Succ == BB)
1705 }
1706
1707
1708
1709 if (!MostPopularDest)
1712
1713
1714 return tryThreadEdge(BB, PredsToFactor, MostPopularDest);
1715}
1716
1717
1718
1719
1722
1723
1724
1727
1728
1729
1730
1731
1732
1733
1734
1738 if (PredBr->isUnconditional()) {
1739 PredBBs[0] = PredBB;
1740
1742 return true;
1743 }
1744 }
1745
1746 return false;
1747}
1748
1749
1750
1751
1754
1755
1756
1757 if (isa(BO->getOperand(0)) ||
1758 isa(BO->getOperand(1)))
1759 return false;
1760
1761
1762
1763 if (!isa(BB->front()))
1764 return false;
1765
1766
1768 return false;
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1789 bool isLHS = true;
1795 return false;
1796 isLHS = false;
1797 }
1798
1800 "computeValueKnownInPredecessors returned true with no values");
1801
1802
1803
1804 unsigned NumTrue = 0, NumFalse = 0;
1805 for (const auto &XorOpValue : XorOpValues) {
1806 if (isa(XorOpValue.first))
1807
1808 continue;
1809 if (cast(XorOpValue.first)->isZero())
1810 ++NumFalse;
1811 else
1812 ++NumTrue;
1813 }
1814
1815
1817 if (NumTrue > NumFalse)
1819 else if (NumTrue != 0 || NumFalse != 0)
1821
1822
1823
1825 for (const auto &XorOpValue : XorOpValues) {
1826 if (XorOpValue.first != SplitVal && !isa(XorOpValue.first))
1827 continue;
1828
1829 BlocksToFoldInto.push_back(XorOpValue.second);
1830 }
1831
1832
1833
1834 if (BlocksToFoldInto.size() ==
1835 cast(BB->front()).getNumIncomingValues()) {
1836 if (!SplitVal) {
1837
1840 } else if (SplitVal->isZero() && BO != BO->getOperand(isLHS)) {
1841
1844 } else {
1845
1847 }
1848
1849 return true;
1850 }
1851
1852
1853
1855 return isa(Pred->getTerminator());
1856 }))
1857 return false;
1858
1859
1861}
1862
1863
1864
1865
1871
1872
1873 Value *IV = PN.getIncomingValueForBlock(OldPred);
1874
1875
1876 if (Instruction *Inst = dyn_cast(IV)) {
1880 }
1881
1882 PN.addIncoming(IV, NewPred);
1883 }
1884}
1885
1886
1889 if (!SinglePred)
1890 return false;
1891
1895 return false;
1896
1897
1898 if (LoopHeaders.erase(SinglePred))
1899 LoopHeaders.insert(BB);
1900
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1933 return true;
1934}
1935
1936
1937
1940
1941
1942
1943
1948
1950
1951
1952 for (Use &U : I.uses()) {
1954 if (PHINode *UserPN = dyn_cast(User)) {
1955 if (UserPN->getIncomingBlock(U) == BB)
1956 continue;
1957 } else if (User->getParent() == BB)
1958 continue;
1959
1961 }
1962
1963
1966 return DbgVal->getParent() == BB;
1967 });
1969 return DbgVarRec->getParent() == BB;
1970 });
1971
1972
1973 if (UsesToRename.empty() && DbgValues.empty() && DbgVariableRecords.empty())
1974 continue;
1975 LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
1976
1977
1978
1979
1980 SSAUpdate.Initialize(I.getType(), I.getName());
1983
1984 while (!UsesToRename.empty())
1986 if (!DbgValues.empty() || !DbgVariableRecords.empty()) {
1989 DbgValues.clear();
1990 DbgVariableRecords.clear();
1991 }
1992
1994 }
1995}
1996
1997
1998
1999
2000
2006
2007
2008
2009
2010
2011 auto RetargetDbgValueIfPossible = [&](Instruction *NewInst) -> bool {
2012 auto DbgInstruction = dyn_cast(NewInst);
2013 if (!DbgInstruction)
2014 return false;
2015
2017 for (auto DbgOperand : DbgInstruction->location_ops()) {
2018 auto DbgOperandInstruction = dyn_cast(DbgOperand);
2019 if (!DbgOperandInstruction)
2020 continue;
2021
2022 auto I = ValueMapping.find(DbgOperandInstruction);
2023 if (I != ValueMapping.end()) {
2024 OperandsToRemap.insert(
2025 std::pair<Value *, Value *>(DbgOperand, I->second));
2026 }
2027 }
2028
2029 for (auto &[OldOp, MappedOp] : OperandsToRemap)
2030 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2031 return true;
2032 };
2033
2034
2035
2036 auto RetargetDbgVariableRecordIfPossible = [&](DbgVariableRecord *DVR) {
2038 for (auto *Op : DVR->location_ops()) {
2039 Instruction *OpInst = dyn_cast(Op);
2040 if (!OpInst)
2041 continue;
2042
2043 auto I = ValueMapping.find(OpInst);
2044 if (I != ValueMapping.end())
2045 OperandsToRemap.insert({OpInst, I->second});
2046 }
2047
2048 for (auto &[OldOp, MappedOp] : OperandsToRemap)
2049 DVR->replaceVariableLocationOp(OldOp, MappedOp);
2050 };
2051
2053
2054
2055
2056
2057 for (; PHINode *PN = dyn_cast(BI); ++BI) {
2060 ValueMapping[PN] = NewPN;
2061 }
2062
2063
2064
2065
2071
2075 RetargetDbgVariableRecordIfPossible(&DVR);
2076 };
2077
2078
2079
2080
2081 for (; BI != BE; ++BI) {
2083 New->setName(BI->getName());
2084 New->insertInto(NewBB, NewBB->end());
2085 ValueMapping[&*BI] = New;
2087
2088 CloneAndRemapDbgInfo(New, &*BI);
2089
2090 if (RetargetDbgValueIfPossible(New))
2091 continue;
2092
2093
2094 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2095 if (Instruction *Inst = dyn_cast(New->getOperand(i))) {
2097 if (I != ValueMapping.end())
2098 New->setOperand(i, I->second);
2099 }
2100 }
2101
2102
2103
2104 if (BE != RangeBB->end() && BE->hasDbgRecords()) {
2105
2108 auto DVRRange = EndMarker->cloneDebugInfoFrom(Marker, std::nullopt);
2110 RetargetDbgVariableRecordIfPossible(&DVR);
2111 }
2112}
2113
2114
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2135 if (!CondBr)
2136 return false;
2137
2138
2140 if (!PredBB)
2141 return false;
2142
2143
2144
2145
2148 return false;
2149
2150
2151
2153 return false;
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2165 return false;
2166
2167
2168 if (LoopHeaders.count(PredBB))
2169 return false;
2170
2171
2173 return false;
2174
2175
2176
2177
2178 unsigned ZeroCount = 0;
2179 unsigned OneCount = 0;
2184
2185 if (isa(P->getTerminator()))
2186 continue;
2187 if (ConstantInt *CI = dyn_cast_or_null(
2189 if (CI->isZero()) {
2190 ZeroCount++;
2191 ZeroPred = P;
2192 } else if (CI->isOne()) {
2193 OneCount++;
2194 OnePred = P;
2195 }
2196 }
2197 }
2198
2199
2201 if (ZeroCount == 1) {
2202 PredPredBB = ZeroPred;
2203 } else if (OneCount == 1) {
2204 PredPredBB = OnePred;
2205 } else {
2206 return false;
2207 }
2208
2210
2211
2212 if (SuccBB == BB) {
2214 << "' - would thread to self!\n");
2215 return false;
2216 }
2217
2218
2219
2220 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2222 bool BBIsHeader = LoopHeaders.count(BB);
2223 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2224 dbgs() << " Not threading across "
2225 << (BBIsHeader ? "loop header BB '" : "block BB '")
2226 << BB->getName() << "' to dest "
2227 << (SuccIsHeader ? "loop header BB '" : "block BB '")
2229 << "' - it might create an irreducible loop!\n";
2230 });
2231 return false;
2232 }
2233
2234
2239
2240
2241
2242
2243 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2244 BBCost + PredBBCost > BBDupThreshold) {
2246 << "' - Cost is too high: " << PredBBCost
2247 << " for PredBB, " << BBCost << "for BB\n");
2248 return false;
2249 }
2250
2251
2253 return true;
2254}
2255
2261 << BB->getName() << "'\n");
2262
2263
2264 bool HasProfile = doesBlockHaveProfileData(BB);
2265 auto *BFI = getOrCreateBFI(HasProfile);
2266 auto *BPI = getOrCreateBPI(BFI != nullptr);
2267
2270
2275
2276
2277 if (BFI) {
2278 assert(BPI && "It's expected BPI to exist along with BFI");
2279 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2280 BPI->getEdgeProbability(PredPredBB, PredBB);
2281 BFI->setBlockFreq(NewBB, NewBBFreq);
2282 }
2283
2284
2285
2286
2289 PredPredBB);
2290
2291
2292 if (BPI)
2293 BPI->copyEdgeProbabilities(PredBB, NewBB);
2294
2295
2296
2297
2299 for (unsigned i = 0, e = PredPredTerm->getNumSuccessors(); i != e; ++i)
2300 if (PredPredTerm->getSuccessor(i) == PredBB) {
2303 }
2304
2306 ValueMapping);
2308 ValueMapping);
2309
2310 DTU->applyUpdatesPermissive(
2315
2316 updateSSA(PredBB, NewBB, ValueMapping);
2317
2318
2319
2322
2325 threadEdge(BB, PredsToFactor, SuccBB);
2326}
2327
2328
2332
2333 if (SuccBB == BB) {
2335 << "' - would thread to self!\n");
2336 return false;
2337 }
2338
2339
2340
2341 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2343 bool BBIsHeader = LoopHeaders.count(BB);
2344 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2345 dbgs() << " Not threading across "
2346 << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
2347 << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")
2348 << SuccBB->getName() << "' - it might create an irreducible loop!\n";
2349 });
2350 return false;
2351 }
2352
2355 if (JumpThreadCost > BBDupThreshold) {
2357 << "' - Cost is too high: " << JumpThreadCost << "\n");
2358 return false;
2359 }
2360
2362 return true;
2363}
2364
2365
2366
2367
2371 assert(SuccBB != BB && "Don't create an infinite loop");
2372
2373 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2374 "Don't thread across loop headers");
2375
2376
2377 bool HasProfile = doesBlockHaveProfileData(BB);
2378 auto *BFI = getOrCreateBFI(HasProfile);
2379 auto *BPI = getOrCreateBPI(BFI != nullptr);
2380
2381
2383 if (PredBBs.size() == 1)
2384 PredBB = PredBBs[0];
2385 else {
2387 << " common predecessors.\n");
2388 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");
2389 }
2390
2391
2393 << "' to '" << SuccBB->getName()
2394 << ", across block:\n " << *BB << "\n");
2395
2396 LVI->threadEdge(PredBB, BB, SuccBB);
2397
2399 BB->getName()+".thread",
2402
2403
2404 if (BFI) {
2405 assert(BPI && "It's expected BPI to exist along with BFI");
2406 auto NewBBFreq =
2407 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2408 BFI->setBlockFreq(NewBB, NewBBFreq);
2409 }
2410
2411
2414 PredBB);
2415
2416
2417
2420
2421
2422
2424
2425
2426
2427
2429 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
2433 }
2434
2435
2439
2440 updateSSA(BB, NewBB, ValueMapping);
2441
2442
2443
2444
2446
2447
2448 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
2449
2450
2451 ++NumThreads;
2452}
2453
2454
2455
2456
2459 const char *Suffix) {
2461
2462
2463
2465 auto *BFI = getBFI();
2466 if (BFI) {
2467 auto *BPI = getOrCreateBPI(true);
2468 for (auto *Pred : Preds)
2469 FreqMap.insert(std::make_pair(
2470 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2471 }
2472
2473
2474
2476 std::string NewName = std::string(Suffix) + ".split-lp";
2478 } else {
2480 }
2481
2482 std::vectorDominatorTree::UpdateType Updates;
2483 Updates.reserve((2 * Preds.size()) + NewBBs.size());
2484 for (auto *NewBB : NewBBs) {
2490 if (BFI)
2491 NewBBFreq += FreqMap.lookup(Pred);
2492 }
2493 if (BFI)
2494 BFI->setBlockFreq(NewBB, NewBBFreq);
2495 }
2496
2497 DTU->applyUpdatesPermissive(Updates);
2498 return NewBBs[0];
2499}
2500
2501bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
2504 return false;
2505
2507}
2508
2509
2510
2511
2512void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
2518 bool HasProfile) {
2519 assert(((BFI && BPI) || (!BFI && !BFI)) &&
2520 "Both BFI & BPI should either be set or unset");
2521
2522 if (!BFI) {
2523 assert(!HasProfile &&
2524 "It's expected to have BFI/BPI when profile info exists");
2525 return;
2526 }
2527
2528
2529
2530 auto BBOrigFreq = BFI->getBlockFreq(BB);
2531 auto NewBBFreq = BFI->getBlockFreq(NewBB);
2532 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);
2533 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2534 BFI->setBlockFreq(BB, BBNewFreq);
2535
2536
2537
2540 auto SuccFreq = (Succ == SuccBB)
2541 ? BB2SuccBBFreq - NewBBFreq
2543 BBSuccFreq.push_back(SuccFreq.getFrequency());
2544 }
2545
2547
2549 if (MaxBBSuccFreq == 0)
2550 BBSuccProbs.assign(BBSuccFreq.size(),
2551 {1, static_cast(BBSuccFreq.size())});
2552 else {
2553 for (uint64_t Freq : BBSuccFreq)
2556
2558 BBSuccProbs.end());
2559 }
2560
2561
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598 if (BBSuccProbs.size() >= 2 && HasProfile) {
2600 for (auto Prob : BBSuccProbs)
2601 Weights.push_back(Prob.getNumerator());
2602
2605 }
2606}
2607
2608
2609
2610
2611
2612
2615 assert(!PredBBs.empty() && "Can't handle an empty set");
2616
2617
2618
2619
2620 if (LoopHeaders.count(BB)) {
2622 << "' into predecessor block '" << PredBBs[0]->getName()
2623 << "' - it might create an irreducible loop!\n");
2624 return false;
2625 }
2626
2629 if (DuplicationCost > BBDupThreshold) {
2631 << "' - Cost is too high: " << DuplicationCost << "\n");
2632 return false;
2633 }
2634
2635
2636 std::vectorDominatorTree::UpdateType Updates;
2638 if (PredBBs.size() == 1)
2639 PredBB = PredBBs[0];
2640 else {
2642 << " common predecessors.\n");
2643 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");
2644 }
2646
2647
2648
2650 << "' into end of '" << PredBB->getName()
2651 << "' to eliminate branch on phi. Cost: "
2652 << DuplicationCost << " block is:" << *BB << "\n");
2653
2654
2655
2657
2658 if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
2660 PredBB = SplitEdge(OldPredBB, BB);
2664 OldPredBranch = cast(PredBB->getTerminator());
2665 }
2666
2667
2668
2670
2672 for (; PHINode *PN = dyn_cast(BI); ++BI)
2674
2675
2676 for (; BI != BB->end(); ++BI) {
2678 New->insertInto(PredBB, OldPredBranch->getIterator());
2679
2680
2681 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2682 if (Instruction *Inst = dyn_cast(New->getOperand(i))) {
2684 if (I != ValueMapping.end())
2685 New->setOperand(i, I->second);
2686 }
2687
2688
2690
2691
2692
2693
2695 New,
2696 {BB->getDataLayout(), TLI, nullptr, nullptr, New})) {
2697 ValueMapping[&*BI] = IV;
2698 if (!New->mayHaveSideEffects()) {
2699 New->eraseFromParent();
2700 New = nullptr;
2701
2702
2704 }
2705 } else {
2706 ValueMapping[&*BI] = New;
2707 }
2708 if (New) {
2709
2710 New->setName(BI->getName());
2711
2712 New->cloneDebugInfoFrom(&*BI);
2713
2714 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2715 if (BasicBlock *SuccBB = dyn_cast(New->getOperand(i)))
2717 }
2718 }
2719
2720
2721
2724 ValueMapping);
2726 ValueMapping);
2727
2728 updateSSA(BB, PredBB, ValueMapping);
2729
2730
2731
2733
2734
2736 if (auto *BPI = getBPI())
2738 DTU->applyUpdatesPermissive(Updates);
2739
2740 ++NumDupes;
2741 return true;
2742}
2743
2744
2745
2746
2747
2748
2751 unsigned Idx) {
2752
2753
2754
2755
2756
2757
2758
2759
2760
2764
2767
2769 BI->applyMergedLocation(PredTerm->getDebugLoc(), SI->getDebugLoc());
2770 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2772 SIUse->addIncoming(SI->getTrueValue(), NewBB);
2773
2776
2778 (TrueWeight + FalseWeight) != 0) {
2781 TrueWeight, TrueWeight + FalseWeight));
2783 FalseWeight, TrueWeight + FalseWeight));
2784
2785 if (auto *BPI = getBPI())
2787 }
2788
2789 if (auto *BFI = getBFI()) {
2790 if ((TrueWeight + FalseWeight) == 0) {
2791 TrueWeight = 1;
2792 FalseWeight = 1;
2793 }
2795 TrueWeight, TrueWeight + FalseWeight);
2796 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2797 BFI->setBlockFreq(NewBB, NewBBFreq);
2798 }
2799
2800
2801 SI->eraseFromParent();
2804
2805
2807 PHINode *Phi = dyn_cast(BI); ++BI)
2808 if (Phi != SIUse)
2809 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2810}
2811
2813 PHINode *CondPHI = dyn_cast(SI->getCondition());
2814
2815 if (!CondPHI || CondPHI->getParent() != BB)
2816 return false;
2817
2821
2822
2823
2824
2826 continue;
2827
2830 continue;
2831
2833 return true;
2834 }
2835 return false;
2836}
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2854
2855 if (!CondBr || !CondBr->isConditional() || !CondLHS ||
2857 return false;
2858
2862
2863
2864
2865 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2866 continue;
2867
2870 continue;
2871
2872
2873
2874
2877 CondRHS, Pred, BB, CondCmp);
2880 CondRHS, Pred, BB, CondCmp);
2881 if ((LHSRes || RHSRes) && LHSRes != RHSRes) {
2883 return true;
2884 }
2885 }
2886 return false;
2887}
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2910
2911
2913 return false;
2914
2915
2916
2917 if (LoopHeaders.count(BB))
2918 return false;
2919
2921 PHINode *PN = dyn_cast(BI); ++BI) {
2922
2924 [](Value *V) { return !isa(V); }))
2925 continue;
2926
2927 auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) {
2928 using namespace PatternMatch;
2929
2930
2931 if (SI->getParent() != BB)
2932 return false;
2933 Value *Cond = SI->getCondition();
2935 return Cond && Cond == V && Cond->getType()->isIntegerTy(1) && !IsAndOr;
2936 };
2937
2939 for (Use &U : PN->uses()) {
2940 if (ICmpInst *Cmp = dyn_cast(U.getUser())) {
2941
2942
2943 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2944 isa(Cmp->getOperand(1 - U.getOperandNo())))
2945 if (SelectInst *SelectI = dyn_cast(Cmp->user_back()))
2946 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2947 SI = SelectI;
2948 break;
2949 }
2950 } else if (SelectInst *SelectI = dyn_cast(U.getUser())) {
2951
2952 if (isUnfoldCandidate(SelectI, U.get())) {
2953 SI = SelectI;
2954 break;
2955 }
2956 }
2957 }
2958
2959 if (!SI)
2960 continue;
2961
2962 Value *Cond = SI->getCondition();
2968 BasicBlock *SplitBB = SI->getParent();
2969 BasicBlock *NewBB = Term->getParent();
2971 NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
2972 NewPN->addIncoming(SI->getFalseValue(), BB);
2974 SI->replaceAllUsesWith(NewPN);
2975 SI->eraseFromParent();
2976
2977 std::vectorDominatorTree::UpdateType Updates;
2982
2983 for (auto *Succ : successors(SplitBB)) {
2986 }
2987 DTU->applyUpdatesPermissive(Updates);
2988 return true;
2989 }
2990 return false;
2991}
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3013 using namespace PatternMatch;
3014
3015
3018 if (PI == PE)
3019 return false;
3020 Pred1 = *PI++;
3021 if (PI == PE)
3022 return false;
3023 Pred2 = *PI++;
3024 if (PI != PE)
3025 return false;
3026 if (Pred1 == Pred2)
3027 return false;
3028
3029
3030
3033 return false;
3034
3035 if (auto *BI = dyn_cast(Parent->getTerminator()))
3036 for (auto &I : *BB)
3038 return true;
3039
3040 return false;
3041}
3042
3043
3044
3045
3049 assert(BI->isConditional() && "Unconditional branch has 2 successors?");
3054
3056 bool TrueDestIsSafe = false;
3057 bool FalseDestIsSafe = false;
3058
3059
3061 if (Impl && *Impl)
3062 TrueDestIsSafe = true;
3063 else {
3064
3065 Impl = isImpliedCondition(BranchCond, GuardCond, DL, false);
3066 if (Impl && *Impl)
3067 FalseDestIsSafe = true;
3068 }
3069
3070 if (!TrueDestIsSafe && !FalseDestIsSafe)
3071 return false;
3072
3073 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3074 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3075
3078 unsigned Cost =
3080 if (Cost > BBDupThreshold)
3081 return false;
3082
3083
3085 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3086 assert(GuardedBlock && "Could not create the guarded block?");
3087
3088
3089
3091 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3092 assert(UnguardedBlock && "Could not create the unguarded block?");
3093 LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
3094 << GuardedBlock->getName() << "\n");
3095
3096
3097
3099 for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
3100 if (!isa(&*BI))
3102
3105
3107 if (!Inst->use_empty()) {
3109 NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3110 NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
3111 NewPN->setDebugLoc(Inst->getDebugLoc());
3113 Inst->replaceAllUsesWith(NewPN);
3114 }
3115 Inst->dropDbgRecords();
3116 Inst->eraseFromParent();
3117 }
3118 return true;
3119}
3120
3121PreservedAnalyses JumpThreadingPass::getPreservedAnalysis() const {
3125
3126
3127
3128 return PA;
3129}
3130
3131template
3132typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
3133 assert(FAM && "Can't run external analysis without FunctionAnalysisManager");
3134
3135
3136
3137
3138 if (!ChangedSinceLastAnalysisUpdate) {
3139 assert(!DTU->hasPendingUpdates() &&
3140 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
3141
3142 return &FAM->getResult(*F);
3143 }
3144 ChangedSinceLastAnalysisUpdate = false;
3145
3146 auto PA = getPreservedAnalysis();
3147
3148
3151
3153
3154 DTU->flush();
3155
3156 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3157 assert((!DTU->hasPostDomTree() ||
3158 DTU->getPostDomTree().verify(
3160
3162
3166
3168}
3169
3171 if (!BPI) {
3172 assert(FAM && "Can't create BPI without FunctionAnalysisManager");
3174 }
3175 return *BPI;
3176}
3177
3179 if (!BFI) {
3180 assert(FAM && "Can't create BFI without FunctionAnalysisManager");
3182 }
3183 return *BFI;
3184}
3185
3186
3187
3188
3190 auto *Res = getBPI();
3191 if (Res)
3192 return Res;
3193
3194 if (Force)
3195 BPI = runExternalAnalysis();
3196
3197 return *BPI;
3198}
3199
3201 auto *Res = getBFI();
3202 if (Res)
3203 return Res;
3204
3205 if (Force)
3206 BFI = runExternalAnalysis();
3207
3208 return *BFI;
3209}
ReachingDefAnalysis InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
static unsigned getBestDestForJumpOnUndef(BasicBlock *BB)
GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump,...
static cl::opt< unsigned > PhiDuplicateThreshold("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden)
static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)
static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
static cl::opt< bool > ThreadAcrossLoopHeaders("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden)
static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI, BasicBlock *BB, Instruction *StopAt, unsigned Threshold)
Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction...
static void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, ValueToValueMapTy &ValueMap)
addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.
static BasicBlock * findMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)
findMostPopularDest - The specified list contains multiple possible threadable destinations.
static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)
getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...
static cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)
static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
Return true if Op is an instruction defined in the given block.
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)
static bool hasAddressTakenAndUsed(BasicBlock *BB)
See the comments on JumpThreadingPass.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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 const uint32_t IV[8]
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
DbgMarker * createMarker(Instruction *I)
Attach a DbgMarker to the given instruction.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
InstListType::const_iterator const_iterator
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
DbgMarker * getMarker(InstListType::iterator It)
Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isLandingPad() const
Return true if this basic block is a landing pad.
bool isEHPad() const
Return true if this basic block is an exception handling block.
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...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
void disableDominatorTree()
Disable the use of the dominator tree during alias analysis queries.
The address of a basic block.
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
uint32_t getNumerator() const
BranchProbability getCompl() const
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
Value * getArgOperand(unsigned i) const
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static Constant * getNot(Constant *C)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This is an important base class in LLVM.
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Per-instruction record of debug-info.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(DbgMarker *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere, bool InsertAtHead=false)
Clone all DbgMarkers from From into this marker.
const BasicBlock * getParent() const
This represents the llvm.dbg.value instruction.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
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...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
This class represents a freeze function that returns random concrete value if an operand is either a ...
const BasicBlock & getEntryBlock() const
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Indirect Branch Instruction.
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
bool isSpecialTerminator() const
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.
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)
Update the SSA form.
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
JumpThreadingPass(int T=-1)
void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, std::optional< BlockFrequencyInfo * > BFI, std::optional< BranchProbabilityInfo * > BPI)
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value *, 4 > &RecursionSet, Instruction *CxtI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
bool processImpliedCondition(BasicBlock *BB)
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
void threadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...
bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...
This is an important class for using LLVM in a threaded context.
Analysis to compute lazy value information.
This pass computes, caches, and vends lazy value constraint information.
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
Constant * getPredicateOnEdge(CmpInst::Predicate Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
void forgetValue(Value *V)
Remove information related to this value from the cache.
Constant * getPredicateAt(CmpInst::Predicate Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
An instruction for reading from memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Align getAlign() const
Return the alignment of the access that is being performed.
static LocationSize precise(uint64_t Value)
This class implements a map that also provides access to all stored values in a deterministic order.
Representation for a specific memory location.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static 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.
void preserve()
Mark an analysis as preserved.
Helper class for SSA formation on a set of values defined in multiple blocks.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
void UpdateDebugValues(Instruction *I)
Rewrite debug value intrinsics to conform to a new SSA form.
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
This class represents the LLVM 'select' instruction.
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.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool hasBranchDivergence(const Function *F=nullptr) const
Return true if branch divergence exists.
@ TCK_SizeAndLatency
The weighted sum of size and latency.
@ TCC_Free
Expected to fold away in lowering.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
bool isIntegerTy() const
True if this is an instance of IntegerType.
'undef' values are things that do not have specified contents.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
iterator find(const KeyT &Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclarationIfExists(Module *M, ID id, ArrayRef< Type * > Tys, FunctionType *FT=nullptr)
This version supports overloaded intrinsics.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
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)
This is an optimization pass for GlobalISel generic memory operations.
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
auto pred_end(const MachineBasicBlock *BB)
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
auto successors(const MachineBasicBlock *BB)
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
void remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst)
Remap the operands of the debug records attached to Inst, and the operands of Inst itself if it's a d...
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto pred_size(const MachineBasicBlock *BB)
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, BatchAAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
bool hasValidBranchWeightMD(const Instruction &I)
Checks if an instructions has valid Branch Weight Metadata.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
void cloneNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, DenseMap< MDNode *, MDNode * > &ClonedScopes, StringRef Ext, LLVMContext &Context)
Duplicate the specified list of noalias decl scopes.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
void adaptNoAliasScopes(llvm::Instruction *I, const DenseMap< MDNode *, MDNode * > &ClonedScopes, LLVMContext &Context)
Adapt the metadata for the specified instruction according to the provided mapping.
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
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.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto pred_begin(const MachineBasicBlock *BB)
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)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
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 ...
Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
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 auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Function object to check whether the second component of a container supported by std::get (like std:...