LLVM: lib/Transforms/Utils/SimplifyCFG.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
80#include
81#include
82#include
83#include
84#include
85#include
86#include
87#include
88#include
89#include
90#include
91#include
92#include
93
94using namespace llvm;
96
97#define DEBUG_TYPE "simplifycfg"
98
99namespace llvm {
100
102 "simplifycfg-require-and-preserve-domtree", cl::Hidden,
103
105 "Temporary development switch used to gradually uplift SimplifyCFG "
106 "into preserving DomTree,"));
107
108
109
110
111
115 "Control the amount of phi node folding to perform (default = 2)"));
116
119 cl::desc("Control the maximal total instruction cost that we are willing "
120 "to speculatively execute to fold a 2-entry PHI node into a "
121 "select (default = 4)"));
122
125 cl::desc("Hoist common instructions up to the parent block"));
126
128 "simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true),
129 cl::desc("Hoist loads if the target supports conditional faulting"));
130
132 "simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true),
133 cl::desc("Hoist stores if the target supports conditional faulting"));
134
136 "hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6),
137 cl::desc("Control the maximal conditional load/store that we are willing "
138 "to speculatively execute to eliminate conditional branch "
139 "(default = 6)"));
140
144 cl::desc("Allow reordering across at most this many "
145 "instructions when hoisting"));
146
149 cl::desc("Sink common instructions down to the end block"));
150
153 cl::desc("Hoist conditional stores if an unconditional store precedes"));
154
157 cl::desc("Hoist conditional stores even if an unconditional store does not "
158 "precede - hoist multiple conditional stores into a single "
159 "predicated store"));
160
162 "simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false),
163 cl::desc("When merging conditional stores, do so even if the resultant "
164 "basic blocks are unlikely to be if-converted as a result"));
165
168 cl::desc("Allow exactly one expensive instruction to be speculatively "
169 "executed"));
170
173 cl::desc("Limit maximum recursion depth when calculating costs of "
174 "speculatively executed instructions"));
175
179 cl::desc("Max size of a block which is still considered "
180 "small enough to thread through"));
181
182
186 cl::desc("Maximum cost of combining conditions when "
187 "folding branches"));
188
190 "simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden,
192 cl::desc("Multiplier to apply to threshold when determining whether or not "
193 "to fold branch to common destination when vector operations are "
194 "present"));
195
198 cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"));
199
202 cl::desc("Limit cases to analyze when converting a switch to select"));
203
206 cl::desc("Limit number of blocks a define in a threaded block is allowed "
207 "to be live in"));
208
210
211}
212
213STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
215 "Number of switch instructions turned into linear mapping");
217 "Number of switch instructions turned into lookup tables");
219 NumLookupTablesHoles,
220 "Number of switch instructions turned into lookup tables (holes checked)");
221STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
222STATISTIC(NumFoldValueComparisonIntoPredecessors,
223 "Number of value comparisons folded into predecessor basic blocks");
225 "Number of branches folded into predecessor basic block");
227 NumHoistCommonCode,
228 "Number of common instruction 'blocks' hoisted up to the begin block");
230 "Number of common instructions hoisted up to the begin block");
232 "Number of common instruction 'blocks' sunk down to the end block");
234 "Number of common instructions sunk down to the end block");
235STATISTIC(NumSpeculations, "Number of speculative executed instructions");
237 "Number of invokes with empty resume blocks simplified into calls");
238STATISTIC(NumInvokesMerged, "Number of invokes that were merged together");
239STATISTIC(NumInvokeSetsFormed, "Number of invoke sets that were formed");
240
241namespace {
242
243
244
245
246using SwitchCaseResultVectorTy =
248
249
250
251
253
254
255struct ValueEqualityComparisonCase {
258
261
262 bool operator<(ValueEqualityComparisonCase RHS) const {
263
265 }
266
267 bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
268};
269
270class SimplifyCFGOpt {
271 const TargetTransformInfo &TTI;
272 DomTreeUpdater *DTU;
273 const DataLayout &DL;
275 const SimplifyCFGOptions &Options;
276 bool Resimplify;
277
278 Value *isValueEqualityComparison(Instruction *TI);
279 BasicBlock *getValueEqualityComparisonCases(
280 Instruction *TI, std::vector &Cases);
281 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
282 BasicBlock *Pred,
284 bool performValueComparisonIntoPredecessorFolding(Instruction *TI, Value *&CV,
285 Instruction *PTI,
287 bool foldValueComparisonIntoPredecessors(Instruction *TI,
289
290 bool simplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
291 bool simplifySingleResume(ResumeInst *RI);
292 bool simplifyCommonResume(ResumeInst *RI);
293 bool simplifyCleanupReturn(CleanupReturnInst *RI);
294 bool simplifyUnreachable(UnreachableInst *UI);
295 bool simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
296 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
297 bool simplifyIndirectBr(IndirectBrInst *IBI);
298 bool simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder);
299 bool simplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
300 bool simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
301 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
302
303 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
305 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
308 bool hoistCommonCodeFromSuccessors(Instruction *TI, bool AllInstsEqOnly);
309 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
310 Instruction *TI, Instruction *I1,
311 SmallVectorImpl<Instruction *> &OtherSuccTIs,
313 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
314 bool simplifyTerminatorOnSelect(Instruction *OldTerm, Value *Cond,
315 BasicBlock *TrueBB, BasicBlock *FalseBB,
316 uint32_t TrueWeight, uint32_t FalseWeight);
317 bool simplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
318 const DataLayout &DL);
319 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select);
320 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
321 bool turnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder);
322
323public:
324 SimplifyCFGOpt(const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
326 const SimplifyCFGOptions &Opts)
327 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
328 assert((!DTU || !DTU->hasPostDomTree()) &&
329 "SimplifyCFG is not yet capable of maintaining validity of a "
330 "PostDomTree, so don't ask for it.");
331 }
332
333 bool simplifyOnce(BasicBlock *BB);
334 bool run(BasicBlock *BB);
335
336
337 bool requestResimplify() {
338 Resimplify = true;
339 return true;
340 }
341};
342
343
344
345
346[[maybe_unused]] bool
347isSelectInRoleOfConjunctionOrDisjunction(const SelectInst *SI) {
352}
353
354}
355
356
357
358
359
360
361
362
367 "Only for a pair of incoming blocks at the time!");
368
369
370
371
372 return all_of(BB->phis(), [IncomingBlocks, EquivalenceSet](PHINode &PN) {
373 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
374 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
375 if (IV0 == IV1)
376 return true;
377 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
378 EquivalenceSet->contains(IV1))
379 return true;
380 return false;
381 });
382}
383
384
385
386static bool
389 if (SI1 == SI2)
390 return false;
391
392
393
394
397
399 bool Fail = false;
401 if (!SI1Succs.count(Succ))
402 continue;
404 continue;
406 if (FailBlocks)
407 FailBlocks->insert(Succ);
408 else
409 break;
410 }
411
412 return ;
413}
414
415
416
417
418
423 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
424 if (MSSAU)
425 if (auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
426 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
427}
428
429
430
431
432
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
460
461
462
463
465 return false;
466
468 if () {
469
470
471 return true;
472 }
474
475
476
477 if (PBB == BB)
478 return false;
479
480
481
482
485 return true;
486
487
488 if (AggressiveInsts.count(I))
489 return true;
490
491
492
493
495 return false;
496
497
498
499
500
501
504 ZeroCostInstructions.insert(OverflowInst);
505 Cost += 1;
506 } else if (!ZeroCostInstructions.contains(I))
508
509
510
511
512
513
514
515 if (Cost > Budget &&
517 !Cost.isValid()))
518 return false;
519
520
521
522 for (Use &Op : I->operands())
524 TTI, AC, ZeroCostInstructions, Depth + 1))
525 return false;
526
527 AggressiveInsts.insert(I);
528 return true;
529}
530
531
532
534
536 if (CI || (V) || !V->getType()->isPointerTy())
537 return CI;
538
539
540
541 if (DL.hasUnstableRepresentation(V->getType()))
542 return nullptr;
543
544
545
547
548
550 return ConstantInt::get(IntPtrTy, 0);
551
552
553
555 if (CE->getOpcode() == Instruction::IntToPtr)
557
558 if (CI->getType() == IntPtrTy)
559 return CI;
560 else
563 }
564 return nullptr;
565}
566
567namespace {
568
569
570
571
572
573
574
575
576
577
578
579struct ConstantComparesGatherer {
580 const DataLayout &DL;
581
582
583 Value *CompValue = nullptr;
584
585
586 Value *Extra = nullptr;
587
588
590
591
592 unsigned UsedICmps = 0;
593
594
595 bool IsEq = false;
596
597
598 bool IgnoreFirstMatch = false;
599 bool MultipleMatches = false;
600
601
602 ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL) : DL(DL) {
603 gather(Cond);
604 if (CompValue || !MultipleMatches)
605 return;
606 Extra = nullptr;
607 Vals.clear();
608 UsedICmps = 0;
609 IgnoreFirstMatch = true;
610 gather(Cond);
611 }
612
613 ConstantComparesGatherer(const ConstantComparesGatherer &) = delete;
614 ConstantComparesGatherer &
615 operator=(const ConstantComparesGatherer &) = delete;
616
617private:
618
619
620 bool setValueOnce(Value *NewVal) {
621 if (IgnoreFirstMatch) {
622 IgnoreFirstMatch = false;
623 return false;
624 }
625 if (CompValue && CompValue != NewVal) {
626 MultipleMatches = true;
627 return false;
628 }
629 CompValue = NewVal;
630 return true;
631 }
632
633
634
635
636
637
638
639
640 bool matchInstruction(Instruction *I, bool isEQ) {
642 isEQ = !isEQ;
643
646
647 if (!setValueOnce(Val))
648 return false;
649 UsedICmps++;
651 return true;
652 }
653
654 ICmpInst *ICI;
655 ConstantInt *C;
658 return false;
659 }
660
662 const APInt *RHSC;
663
664
665
666
667 if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
710 APInt Mask = ~*RHSC;
711 if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) {
712
713 if (!setValueOnce(RHSVal))
714 return false;
715
716 Vals.push_back(C);
717 Vals.push_back(
718 ConstantInt::get(C->getContext(),
719 C->getValue() | Mask));
720 UsedICmps++;
721 return true;
722 }
723 }
724
725
726
727
728
729
730
733 APInt Mask = *RHSC;
734 if (Mask.isPowerOf2() && (C->getValue() | Mask) == C->getValue()) {
735
736 if (!setValueOnce(RHSVal))
737 return false;
738
739 Vals.push_back(C);
740 Vals.push_back(ConstantInt::get(C->getContext(),
741 C->getValue() & ~Mask));
742 UsedICmps++;
743 return true;
744 }
745 }
746
747
748 if (!setValueOnce(ICI->getOperand(0)))
749 return false;
750
751 UsedICmps++;
752 Vals.push_back(C);
753 return true;
754 }
755
756
757 ConstantRange Span =
759
760
761
762 Value *CandidateVal = I->getOperand(0);
765 CandidateVal = RHSVal;
766 }
767
768
769
770
771 if (!isEQ)
773
774
776 return false;
777 }
778
779
780 if (!setValueOnce(CandidateVal))
781 return false;
782
783
785 do
786 Vals.push_back(ConstantInt::get(I->getContext(), Tmp));
787 while (++Tmp != Span.getUpper());
788
789 UsedICmps++;
790 return true;
791 }
792
793
794
795
796
797
798 void gather(Value *V) {
799 Value *Op0, *Op1;
801 IsEq = true;
803 IsEq = false;
804 else
805 return;
806
807 SmallVector<Value *, 8> DFT{Op0, Op1};
808 SmallPtrSet<Value *, 8> Visited{V, Op0, Op1};
809
810 while (!DFT.empty()) {
812
814
817 if (Visited.insert(Op1).second)
819 if (Visited.insert(Op0).second)
821
822 continue;
823 }
824
825
826 if (matchInstruction(I, IsEq))
827
828 continue;
829 }
830
831
832
833
834 if (!Extra) {
835 Extra = V;
836 continue;
837 }
838
839 CompValue = nullptr;
840 break;
841 }
842 }
843};
844
845}
846
853 if (BI->isConditional())
857 }
858
862}
863
864
865
866Value *SimplifyCFGOpt::isValueEqualityComparison(Instruction *TI) {
867 Value *CV = nullptr;
869
870
871 if (->getParent()->hasNPredecessorsOrMore(128 / SI->getNumSuccessors()))
872 CV = SI->getCondition();
874 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
879 if (Trunc->hasNoUnsignedWrap())
880 CV = Trunc->getOperand(0);
881 }
882 }
883
884
885 if (CV) {
887 Value *Ptr = PTII->getPointerOperand();
888 if (DL.hasUnstableRepresentation(Ptr->getType()))
889 return CV;
890 if (PTII->getType() == DL.getIntPtrType(Ptr->getType()))
891 CV = Ptr;
892 }
893 }
894 return CV;
895}
896
897
898
899BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
900 Instruction *TI, std::vector &Cases) {
902 Cases.reserve(SI->getNumCases());
903 for (auto Case : SI->cases())
904 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
905 Case.getCaseSuccessor()));
906 return SI->getDefaultDest();
907 }
908
911 ICmpInst::Predicate Pred;
912 ConstantInt *C;
916 } else {
917 Pred = ICmpInst::ICMP_NE;
919 C = ConstantInt::get(cast(Trunc->getOperand(0)->getType()), 0);
920 }
922 Cases.push_back(ValueEqualityComparisonCase(C, Succ));
923 return BI->getSuccessor(Pred == ICmpInst::ICMP_EQ);
924}
925
926
927
928static void
930 std::vector &Cases) {
932}
933
934
935static bool valuesOverlap(std::vector &C1,
936 std::vector &C2) {
937 std::vector *V1 = &C1, *V2 = &C2;
938
939
940 if (V1->size() > V2->size())
942
943 if (V1->empty())
944 return false;
945 if (V1->size() == 1) {
946
948 for (const ValueEqualityComparisonCase &VECC : *V2)
949 if (TheVal == VECC.Value)
950 return true;
951 }
952
953
956 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
957 while (i1 != e1 && i2 != e2) {
958 if ((*V1)[i1].Value == (*V2)[i2].Value)
959 return true;
960 if ((*V1)[i1].Value < (*V2)[i2].Value)
961 ++i1;
962 else
963 ++i2;
964 }
965 return false;
966}
967
968
969
970
971
972
973bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
974 Instruction *TI, BasicBlock *Pred, IRBuilder<> &Builder) {
976 if (!PredVal)
977 return false;
978
979 Value *ThisVal = isValueEqualityComparison(TI);
980 assert(ThisVal && "This isn't a value comparison!!");
981 if (ThisVal != PredVal)
982 return false;
983
984
985
986
987
988 std::vector PredCases;
990 getValueEqualityComparisonCases(Pred->getTerminator(), PredCases);
992
993
994 std::vector ThisCases;
995 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
997
998
999
1000 if (PredDef == TI->getParent()) {
1001
1002
1003
1005 return false;
1006
1008
1009
1010 assert(ThisCases.size() == 1 && "Branch can only have one case!");
1011
1013 (void)NI;
1014
1015
1016 ThisCases[0].Dest->removePredecessor(PredDef);
1017
1019 << "Through successor TI: " << *TI << "Leaving: " << *NI
1020 << "\n");
1021
1023
1024 if (DTU)
1026 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1027
1028 return true;
1029 }
1030
1032
1033 SmallPtrSet<Constant *, 16> DeadCases;
1034 for (const ValueEqualityComparisonCase &Case : PredCases)
1035 DeadCases.insert(Case.Value);
1036
1038 << "Through successor TI: " << *TI);
1039
1040 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1042 --i;
1043 auto *Successor = i->getCaseSuccessor();
1044 if (DTU)
1045 ++NumPerSuccessorCases[Successor];
1046 if (DeadCases.count(i->getCaseValue())) {
1047 Successor->removePredecessor(PredDef);
1048 SI.removeCase(i);
1049 if (DTU)
1050 --NumPerSuccessorCases[Successor];
1051 }
1052 }
1053
1054 if (DTU) {
1055 std::vectorDominatorTree::UpdateType Updates;
1056 for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
1057 if (I.second == 0)
1058 Updates.push_back({DominatorTree::Delete, PredDef, I.first});
1060 }
1061
1063 return true;
1064 }
1065
1066
1067
1068 ConstantInt *TIV = nullptr;
1070 for (const auto &[Value, Dest] : PredCases)
1071 if (Dest == TIBB) {
1072 if (TIV)
1073 return false;
1075 }
1076 assert(TIV && "No edge from pred to succ?");
1077
1078
1079
1081 for (const auto &[Value, Dest] : ThisCases)
1082 if (Value == TIV) {
1083 TheRealDest = Dest;
1084 break;
1085 }
1086
1087
1088 if (!TheRealDest)
1089 TheRealDest = ThisDef;
1090
1091 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1092
1093
1094 BasicBlock *CheckEdge = TheRealDest;
1095 for (BasicBlock *Succ : successors(TIBB))
1096 if (Succ != CheckEdge) {
1097 if (Succ != TheRealDest)
1098 RemovedSuccs.insert(Succ);
1100 } else
1101 CheckEdge = nullptr;
1102
1103
1105 (void)NI;
1106
1108 << "Through successor TI: " << *TI << "Leaving: " << *NI
1109 << "\n");
1110
1112 if (DTU) {
1113 SmallVector<DominatorTree::UpdateType, 2> Updates;
1115 for (auto *RemovedSucc : RemovedSuccs)
1116 Updates.push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1118 }
1119 return true;
1120}
1121
1122namespace {
1123
1124
1125
1126
1127struct ConstantIntOrdering {
1128 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
1129 return LHS->getValue().ult(RHS->getValue());
1130 }
1131};
1132
1133}
1134
1140 return 0;
1141 return LHS->getValue().ult(RHS->getValue()) ? 1 : -1;
1142}
1143
1144
1145
1146
1150 assert(MD && "Invalid branch-weight metadata");
1152
1153
1154
1155
1159 if (!ICI)
1160 return;
1161
1164 }
1165}
1166
1170
1171
1172
1173
1175 if (BonusInst.isTerminator())
1176 continue;
1177
1179
1181
1182
1183
1184
1188 }
1189
1192
1193
1194
1195
1196
1197
1199
1204
1205 NewBonusInst->takeName(&BonusInst);
1206 BonusInst.setName(NewBonusInst->getName() + ".old");
1207 VMap[&BonusInst] = NewBonusInst;
1208
1209
1210
1211
1215 if (!PN) {
1216 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1217 "If the user is not a PHI node, then it should be in the same "
1218 "block as, and come after, the original bonus instruction.");
1219 continue;
1220 }
1221
1222 if (PN->getIncomingBlock(U) == BB)
1223 continue;
1224
1225
1226 assert(PN->getIncomingBlock(U) == PredBlock &&
1227 "Not in block-closed SSA form?");
1228 U.set(NewBonusInst);
1229 }
1230 }
1231
1232
1233
1234
1235
1236 if (auto &PredDL = PTI->getDebugLoc()) {
1238 if (!PredDL->getAtomGroup() && DL && DL->getAtomGroup() &&
1239 PredDL.isSameSourceLocation(DL)) {
1242 }
1243 }
1244}
1245
1246bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1247 Instruction *TI, Value *&CV, Instruction *PTI, IRBuilder<> &Builder) {
1250
1252
1253
1254 std::vector BBCases;
1255 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1256
1257 std::vector PredCases;
1258 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1259
1260
1261
1262
1263 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1264
1265
1266 SmallVector<uint64_t, 8> Weights;
1269
1270 if (PredHasWeights) {
1272
1273 if (Weights.size() != 1 + PredCases.size())
1274 PredHasWeights = SuccHasWeights = false;
1275 } else if (SuccHasWeights)
1276
1277
1278
1279 Weights.assign(1 + PredCases.size(), 1);
1280
1281 SmallVector<uint64_t, 8> SuccWeights;
1282 if (SuccHasWeights) {
1284
1285 if (SuccWeights.size() != 1 + BBCases.size())
1286 PredHasWeights = SuccHasWeights = false;
1287 } else if (PredHasWeights)
1288 SuccWeights.assign(1 + BBCases.size(), 1);
1289
1290 if (PredDefault == BB) {
1291
1292
1293 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1294 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
1295 if (PredCases[i].Dest != BB)
1296 PTIHandled.insert(PredCases[i].Value);
1297 else {
1298
1299 std::swap(PredCases[i], PredCases.back());
1300
1301 if (PredHasWeights || SuccHasWeights) {
1302
1303 Weights[0] += Weights[i + 1];
1306 }
1307
1308 PredCases.pop_back();
1309 --i;
1310 --e;
1311 }
1312
1313
1314 if (PredDefault != BBDefault) {
1316 if (DTU && PredDefault != BB)
1317 Updates.push_back({DominatorTree::Delete, Pred, PredDefault});
1318 PredDefault = BBDefault;
1319 ++NewSuccessors[BBDefault];
1320 }
1321
1322 unsigned CasesFromPred = Weights.size();
1323 uint64_t ValidTotalSuccWeight = 0;
1324 for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
1325 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1326 PredCases.push_back(BBCases[i]);
1327 ++NewSuccessors[BBCases[i].Dest];
1328 if (SuccHasWeights || PredHasWeights) {
1329
1330
1331
1332 Weights.push_back(Weights[0] * SuccWeights[i + 1]);
1333 ValidTotalSuccWeight += SuccWeights[i + 1];
1334 }
1335 }
1336
1337 if (SuccHasWeights || PredHasWeights) {
1338 ValidTotalSuccWeight += SuccWeights[0];
1339
1340 for (unsigned i = 1; i < CasesFromPred; ++i)
1341 Weights[i] *= ValidTotalSuccWeight;
1342
1343 Weights[0] *= SuccWeights[0];
1344 }
1345 } else {
1346
1347
1348
1349 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1350 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1351 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
1352 if (PredCases[i].Dest == BB) {
1353 PTIHandled.insert(PredCases[i].Value);
1354
1355 if (PredHasWeights || SuccHasWeights) {
1356 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1359 }
1360
1361 std::swap(PredCases[i], PredCases.back());
1362 PredCases.pop_back();
1363 --i;
1364 --e;
1365 }
1366
1367
1368
1369 for (const ValueEqualityComparisonCase &Case : BBCases)
1370 if (PTIHandled.count(Case.Value)) {
1371
1372 if (PredHasWeights || SuccHasWeights)
1373 Weights.push_back(WeightsForHandled[Case.Value]);
1374 PredCases.push_back(Case);
1375 ++NewSuccessors[Case.Dest];
1376 PTIHandled.erase(Case.Value);
1377 }
1378
1379
1380
1381 for (ConstantInt *I : PTIHandled) {
1382 if (PredHasWeights || SuccHasWeights)
1383 Weights.push_back(WeightsForHandled[I]);
1384 PredCases.push_back(ValueEqualityComparisonCase(I, BBDefault));
1385 ++NewSuccessors[BBDefault];
1386 }
1387 }
1388
1389
1390
1391
1392 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1393 if (DTU) {
1396 }
1397 for (const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1398 NewSuccessors) {
1399 for (auto I : seq(NewSuccessor.second)) {
1400 (void)I;
1402 }
1403 if (DTU && !SuccsOfPred.contains(NewSuccessor.first))
1404 Updates.push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1405 }
1406
1408
1411 "Should not end up here with unstable pointers");
1412 CV =
1414 }
1415
1416
1417 SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault, PredCases.size());
1419 for (ValueEqualityComparisonCase &V : PredCases)
1420 NewSI->addCase(V.Value, V.Dest);
1421
1422 if (PredHasWeights || SuccHasWeights)
1424 true);
1425
1427
1428
1429
1430
1432 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
1434 if (!InfLoopBlock) {
1435
1436
1437 InfLoopBlock =
1440 if (DTU)
1442 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1443 }
1445 }
1446
1447 if (DTU) {
1448 if (InfLoopBlock)
1449 Updates.push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1450
1451 Updates.push_back({DominatorTree::Delete, Pred, BB});
1452
1454 }
1455
1456 ++NumFoldValueComparisonIntoPredecessors;
1457 return true;
1458}
1459
1460
1461
1462
1463
1464bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1467 Value *CV = isValueEqualityComparison(TI);
1468 assert(CV && "Not a comparison?");
1469
1471
1472 SmallSetVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
1473 while (!Preds.empty()) {
1474 BasicBlock *Pred = Preds.pop_back_val();
1476
1477
1478 if (Pred == BB)
1479 continue;
1480
1481
1482 Value *PCV = isValueEqualityComparison(PTI);
1483 if (PCV != CV)
1484 continue;
1485
1486 SmallSetVector<BasicBlock *, 4> FailBlocks;
1488 for (auto *Succ : FailBlocks) {
1490 return false;
1491 }
1492 }
1493
1494 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1496 }
1498}
1499
1500
1501
1502
1503
1507 for (const PHINode &PN : Succ->phis()) {
1508 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1509 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1510 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1511 return false;
1512 }
1513 }
1514 }
1515 return true;
1516}
1517
1518
1519
1520
1526
1528 unsigned Flags = 0;
1529 if (I->mayReadFromMemory())
1531
1532
1537 return Flags;
1538}
1539
1540
1541
1543
1544 if ((Flags & SkipReadMem) && I->mayWriteToMemory())
1545 return false;
1546
1547
1548
1550 (I->mayReadFromMemory() || I->mayHaveSideEffects() || isa(I)))
1551 return false;
1552
1553
1554
1556 return false;
1557
1558
1559
1561 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1562 return false;
1563
1564
1565
1567 for (Value *Op : I->operands()) {
1569 if (J->getParent() == BB)
1570 return false;
1571 }
1572
1573 return true;
1574}
1575
1577
1578
1579
1582
1583
1584
1585
1586
1587
1590 if (C1 && C2)
1591 if (C1->isMustTailCall() != C2->isMustTailCall())
1592 return false;
1593
1594 if (.isProfitableToHoist(I1) ||
.isProfitableToHoist(I2))
1595 return false;
1596
1597
1598
1600 if (CB1->cannotMerge() || CB1->isConvergent())
1601 return false;
1603 if (CB2->cannotMerge() || CB2->isConvergent())
1604 return false;
1605
1606 return true;
1607}
1608
1609
1610
1611
1612
1613
1614
1618 if (!I1->hasDbgRecords())
1619 return;
1620 using CurrentAndEndIt =
1621 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1622
1625
1626
1627 auto atEnd = [](const CurrentAndEndIt &Pair) {
1628 return Pair.first == Pair.second;
1629 };
1630
1634 return Itrs[0].first->isIdenticalToWhenDefined(*I);
1635 });
1636 };
1637
1638
1640 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1642 if (->hasDbgRecords())
1643 return;
1645 {Other->getDbgRecordRange().begin(), Other->getDbgRecordRange().end()});
1646 }
1647
1648
1649
1650
1651
1652 while (none_of(Itrs, atEnd)) {
1653 bool HoistDVRs = allIdentical(Itrs);
1654 for (CurrentAndEndIt &Pair : Itrs) {
1655
1656
1658 if (HoistDVRs) {
1661 }
1662 }
1663 }
1664}
1665
1668 if (I1->isIdenticalToWhenDefined(I2, true))
1669 return true;
1670
1673 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1674 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1675 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1676
1677 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1678 return I1->getOperand(0) == I2->getOperand(1) &&
1679 I1->getOperand(1) == I2->getOperand(0) &&
1681 }
1682
1683 return false;
1684}
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1743 std::optional Invert, Instruction *Sel) {
1744 auto &Context = BI->getParent()->getContext();
1747
1749 Value *Mask = nullptr;
1750 Value *MaskFalse = nullptr;
1751 Value *MaskTrue = nullptr;
1752 if (Invert.has_value()) {
1753 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.back());
1754 Mask = Builder.CreateBitCast(
1756 VCondTy);
1757 } else {
1759 MaskFalse = Builder.CreateBitCast(
1761 MaskTrue = Builder.CreateBitCast(Cond, VCondTy);
1762 }
1763 auto PeekThroughBitcasts = [](Value *V) {
1765 V = BitCast->getOperand(0);
1766 return V;
1767 };
1768 for (auto *I : SpeculatedConditionalLoadsStores) {
1769 IRBuilder<> Builder(Invert.has_value() ? I : BI);
1770 if (!Invert.has_value())
1771 Mask = I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1772
1773
1774
1776 auto *Op0 = I->getOperand(0);
1777 CallInst *MaskedLoadStore = nullptr;
1779
1780 auto *Ty = I->getType();
1782 Value *PassThru = nullptr;
1783 if (Invert.has_value())
1784 for (User *U : I->users()) {
1786 PassThru = Builder.CreateBitCast(
1790 Sel && Ins->getParent() == BB) {
1791
1792
1793
1794
1795 Builder.SetInsertPoint(Ins);
1796 }
1797 }
1798 MaskedLoadStore = Builder.CreateMaskedLoad(
1800 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1801 if (PN)
1803 I->replaceAllUsesWith(NewLoadStore);
1804 } else {
1805
1806 auto *StoredVal = Builder.CreateBitCast(
1808 MaskedLoadStore = Builder.CreateMaskedStore(
1809 StoredVal, I->getOperand(1), cast(I)->getAlign(), Mask);
1810 }
1811
1812
1813
1814
1815
1816
1817
1818
1819 if (const MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1821 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1822
1823
1825 I->eraseMetadataIf([](unsigned MDKind, MDNode *Node) {
1826 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1827 });
1829 I->eraseFromParent();
1830 }
1831}
1832
1835
1836 bool IsStore = false;
1839 return false;
1842 return false;
1843 IsStore = true;
1844 } else
1845 return false;
1846
1847
1848
1849
1852}
1853
1854
1855
1856
1857
1858
1859bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1860 bool AllInstsEqOnly) {
1861
1862
1863
1864
1865
1866
1868 unsigned int SuccSize = succ_size(BB);
1869 if (SuccSize < 2)
1870 return false;
1871
1872
1873
1874
1875 SmallSetVector<BasicBlock *, 4> UniqueSuccessors(from_range, successors(BB));
1876 for (auto *Succ : UniqueSuccessors) {
1878 return false;
1879
1880
1882 continue;
1883
1884
1885
1886
1888 continue;
1889 return false;
1890 }
1891
1892 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1894 for (auto *Succ : UniqueSuccessors) {
1897 return false;
1898 SuccIterPairs.push_back(SuccIterPair(SuccItr, 0));
1899 }
1900
1901 if (AllInstsEqOnly) {
1902
1903
1904
1905
1906
1907 unsigned Size0 = UniqueSuccessors[0]->size();
1908 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1909 bool AllSame =
1910 all_of(drop_begin(UniqueSuccessors), [Term0, Size0](BasicBlock *Succ) {
1912 Succ->size() == Size0;
1913 });
1914 if (!AllSame)
1915 return false;
1916 if (AllSame) {
1917 LockstepReverseIterator LRI(UniqueSuccessors.getArrayRef());
1918 while (LRI.isValid()) {
1920 if (any_of(*LRI, [I0](Instruction *I) {
1922 })) {
1923 return false;
1924 }
1925 --LRI;
1926 }
1927 }
1928
1929
1930 }
1931
1932
1933
1934
1935 unsigned NumSkipped = 0;
1936
1937
1938 if (SuccIterPairs.size() > 2) {
1941 if (SuccIterPairs.size() < 2)
1942 return false;
1943 }
1944
1946
1947 for (;;) {
1948 auto *SuccIterPairBegin = SuccIterPairs.begin();
1949 auto &BB1ItrPair = *SuccIterPairBegin++;
1950 auto OtherSuccIterPairRange =
1952 auto OtherSuccIterRange = make_first_range(OtherSuccIterPairRange);
1953
1955
1956 bool AllInstsAreIdentical = true;
1957 bool HasTerminator = I1->isTerminator();
1958 for (auto &SuccIter : OtherSuccIterRange) {
1962 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1963 AllInstsAreIdentical = false;
1964 }
1965
1966 SmallVector<Instruction *, 8> OtherInsts;
1967 for (auto &SuccIter : OtherSuccIterRange)
1968 OtherInsts.push_back(&*SuccIter);
1969
1970
1971
1972 if (HasTerminator) {
1973
1974
1975
1976 if (NumSkipped || !AllInstsAreIdentical) {
1979 }
1980
1981 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1982 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1984 }
1985
1986 if (AllInstsAreIdentical) {
1987 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1988 AllInstsAreIdentical =
1990 all_of(OtherSuccIterPairRange, [=](const auto &Pair) {
1992 unsigned SkipFlagsBB2 = Pair.second;
1993
1994
1995
1996
1999 });
2000 }
2001
2002 if (AllInstsAreIdentical) {
2003 BB1ItrPair.first++;
2004
2005
2006
2008
2009
2010
2012 for (auto &SuccIter : OtherSuccIterRange) {
2017 I1->andIRFlags(I2);
2020 assert(Success && "We should not be trying to hoist callbases "
2021 "with non-intersectable attributes");
2022
2024 }
2025
2027
2028
2029 I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
2031 }
2033 NumHoistCommonCode += SuccIterPairs.size();
2035 NumHoistCommonInstrs += SuccIterPairs.size();
2036 } else {
2040 }
2041
2042
2043
2044 for (auto &SuccIterPair : SuccIterPairs) {
2047 }
2048 ++NumSkipped;
2049 }
2050 }
2051}
2052
2053bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2054 Instruction *TI, Instruction *I1,
2055 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2057
2059
2063
2064
2065 auto *I2 = *OtherSuccTIs.begin();
2067 if (BI) {
2071 }
2072
2073
2074
2075
2076
2078 return false;
2079
2080
2082 return false;
2083
2084 for (BasicBlock *Succ : successors(BB1)) {
2085 for (PHINode &PN : Succ->phis()) {
2086 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2087 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2088 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2089 if (BB1V == BB2V)
2090 continue;
2091
2092
2093
2094
2097 return false;
2098 }
2099 }
2100 }
2101
2102
2103
2105
2108 if (->getType()->isVoidTy()) {
2109 I1->replaceAllUsesWith(NT);
2110 for (Instruction *OtherSuccTI : OtherSuccTIs)
2111 OtherSuccTI->replaceAllUsesWith(NT);
2112 NT->takeName(I1);
2113 }
2115 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2116
2117
2118
2121 for (auto *OtherSuccTI : OtherSuccTIs)
2122 Locs.push_back(OtherSuccTI->getDebugLoc());
2124
2125
2127
2128
2129
2130
2131
2132
2133 if (BI) {
2134 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2135 for (BasicBlock *Succ : successors(BB1)) {
2136 for (PHINode &PN : Succ->phis()) {
2137 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2138 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2139 if (BB1V == BB2V)
2140 continue;
2141
2142
2143
2144 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2145 if (!SI) {
2146
2151 }
2152
2153
2154 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2155 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2156 PN.setIncomingValue(i, SI);
2157 }
2158 }
2159 }
2160
2162
2163
2164 for (BasicBlock *Succ : successors(BB1)) {
2166 if (DTU)
2167 Updates.push_back({DominatorTree::Insert, TIParent, Succ});
2168 }
2169
2170 if (DTU) {
2171
2172
2173 for (BasicBlock *Succ : UniqueSuccessors)
2174 Updates.push_back({DominatorTree::Delete, TIParent, Succ});
2175 }
2176
2178 if (DTU)
2181}
2182
2183
2184
2187
2188 if (I->isIntDivRem())
2189 return OpIdx != 1;
2191}
2192
2193
2194
2195
2196
2197
2201
2202
2203 std::optional NumUses;
2204 for (auto *I : Insts) {
2205
2207 I->getType()->isTokenTy())
2208 return false;
2209
2210
2211
2212 if (I->getParent()->getSingleSuccessor() == I->getParent())
2213 return false;
2214
2215
2216
2217
2218
2220 if (C->isInlineAsm() || C->cannotMerge() || C->isConvergent())
2221 return false;
2222
2223 if (!NumUses)
2224 NumUses = I->getNumUses();
2225 else if (NumUses != I->getNumUses())
2226 return false;
2227 }
2228
2231 for (auto *I : Insts) {
2233 return false;
2234
2235
2236
2238 return false;
2239 }
2240
2241
2242
2243
2244
2245 for (const Use &U : I0->uses()) {
2246 auto It = PHIOperands.find(&U);
2247 if (It == PHIOperands.end())
2248
2249 return false;
2250 if ((Insts, It->second))
2251 return false;
2252 }
2253
2254
2255
2256
2257
2259 auto IsIndirectCall = [](const Instruction *I) {
2261 };
2262 bool HaveIndirectCalls = any_of(Insts, IsIndirectCall);
2263 bool AllCallsAreIndirect = all_of(Insts, IsIndirectCall);
2264 if (HaveIndirectCalls) {
2265 if (!AllCallsAreIndirect)
2266 return false;
2267 } else {
2268
2269 Value *Callee = nullptr;
2272 if (!Callee)
2273 Callee = CurrCallee;
2274 else if (Callee != CurrCallee)
2275 return false;
2276 }
2277 }
2278 }
2279
2280 for (unsigned OI = 0, OE = I0->getNumOperands(); OI != OE; ++OI) {
2282 auto SameAsI0 = [&I0, OI](const Instruction *I) {
2284 return I->getOperand(OI) == I0->getOperand(OI);
2285 };
2286 if ((Insts, SameAsI0)) {
2289
2290 return false;
2292 for (auto *I : Insts)
2293 Ops.push_back(I->getOperand(OI));
2294 }
2295 }
2296 return true;
2297}
2298
2299
2300
2301
2303 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2304
2305
2306
2308 for (auto *BB : Blocks) {
2312 }
2313
2314
2315
2318 for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
2319
2320
2321
2322
2323
2324
2326 return I->getOperand(O) != I0->getOperand(O);
2327 });
2328 if (!NeedPHI) {
2330 continue;
2331 }
2332
2333
2335 assert(->getType()->isTokenTy() && "Can't PHI tokens!");
2336 auto *PN =
2338 PN->insertBefore(BBEnd->begin());
2339 for (auto *I : Insts)
2340 PN->addIncoming(I->getOperand(O), I->getParent());
2342 }
2343
2344
2345
2348
2349 I0->moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2350
2351
2352 for (auto *I : Insts)
2353 if (I != I0) {
2354
2355
2356
2357
2358
2359
2360
2366 assert(Success && "We should not be trying to sink callbases "
2367 "with non-intersectable attributes");
2368
2370 }
2371 }
2372
2374
2375
2376
2378 PN->replaceAllUsesWith(I0);
2379 PN->eraseFromParent();
2380 }
2381
2382
2383 for (auto *I : Insts) {
2384 if (I == I0)
2385 continue;
2386
2387
2388 assert(I->user_empty() && "Inst unexpectedly still has non-dbg users");
2389 I->replaceAllUsesWith(I0);
2390 I->eraseFromParent();
2391 }
2392}
2393
2394
2395
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2440 bool HaveNonUnconditionalPredecessors = false;
2443 if (PredBr && PredBr->isUnconditional())
2444 UnconditionalPreds.push_back(PredBB);
2445 else
2446 HaveNonUnconditionalPredecessors = true;
2447 }
2448 if (UnconditionalPreds.size() < 2)
2449 return false;
2450
2451
2452
2453
2454
2455
2456
2457
2461 for (const Use &U : PN.incoming_values())
2462 IncomingVals.insert({PN.getIncomingBlock(U), &U});
2463 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2464 for (BasicBlock *Pred : UnconditionalPreds)
2465 Ops.push_back(*IncomingVals[Pred]);
2466 }
2467
2468 int ScanIdx = 0;
2473 LLVM_DEBUG(dbgs() << "SINK: instruction can be sunk: " << *(*LRI)[0]
2474 << "\n");
2476 ++ScanIdx;
2477 --LRI;
2478 }
2479
2480
2481 if (ScanIdx == 0)
2482 return false;
2483
2485
2486 if (!followedByDeoptOrUnreachable) {
2487
2488 auto IsMemOperand = [](Use &U) {
2494 return false;
2495 };
2496
2497
2498
2499
2501 unsigned NumPHIInsts = 0;
2502 for (Use &U : (*LRI)[0]->operands()) {
2503 auto It = PHIOperands.find(&U);
2504 if (It != PHIOperands.end() && (It->second, [&](Value *V) {
2505 return InstructionsToSink.contains(V);
2506 })) {
2507 ++NumPHIInsts;
2508
2509
2510
2511
2512 if (IsMemOperand(U) &&
2513 any_of(It->second, [](Value *V) { return isa(V); }))
2514 return false;
2515
2516
2517
2518 }
2519 }
2520 LLVM_DEBUG(dbgs() << "SINK: #phi insts: " << NumPHIInsts << "\n");
2521 return NumPHIInsts <= 1;
2522 };
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2536 int Idx = 0;
2538 while (Idx < ScanIdx) {
2539 if (!ProfitableToSinkInstruction(LRI)) {
2540
2542 dbgs() << "SINK: stopping here, too many PHIs would be created!\n");
2543 break;
2544 }
2545 InstructionsProfitableToSink.insert_range(*LRI);
2546 --LRI;
2547 ++Idx;
2548 }
2549
2550
2551 if (Idx == 0)
2552 return false;
2553
2554
2555 if (Idx < ScanIdx) {
2556
2557 ScanIdx = Idx;
2558 InstructionsToSink = InstructionsProfitableToSink;
2559
2560
2561
2562
2564 !ProfitableToSinkInstruction(LRI) &&
2565 "We already know that the last instruction is unprofitable to sink");
2566 ++LRI;
2567 --Idx;
2568 while (Idx >= 0) {
2569
2570
2571
2572
2573 for (auto *I : *LRI)
2574 InstructionsProfitableToSink.erase(I);
2575 if (!ProfitableToSinkInstruction(LRI)) {
2576
2577 ScanIdx = Idx;
2578 InstructionsToSink = InstructionsProfitableToSink;
2579 }
2580 ++LRI;
2581 --Idx;
2582 }
2583 }
2584
2585
2586 if (ScanIdx == 0)
2587 return false;
2588 }
2589
2591
2592 if (HaveNonUnconditionalPredecessors) {
2593 if (!followedByDeoptOrUnreachable) {
2594
2595
2596
2597
2598
2600 int Idx = 0;
2601 bool Profitable = false;
2602 while (Idx < ScanIdx) {
2604 Profitable = true;
2605 break;
2606 }
2607 --LRI;
2608 ++Idx;
2609 }
2610 if (!Profitable)
2611 return false;
2612 }
2613
2615
2616
2618
2619 return false;
2621 }
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635 int SinkIdx = 0;
2636 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2638 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2639 << "\n");
2640
2641
2642
2644
2646 NumSinkCommonInstrs++;
2648 }
2649 if (SinkIdx != 0)
2650 ++NumSinkCommonCode;
2652}
2653
2654namespace {
2655
2656struct CompatibleSets {
2657 using SetTy = SmallVector<InvokeInst *, 2>;
2658
2660
2662
2663 SetTy &getCompatibleSet(InvokeInst *II);
2664
2665 void insert(InvokeInst *II);
2666};
2667
2668CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *II) {
2669
2670
2671
2672
2673 for (CompatibleSets::SetTy &Set : Sets) {
2674 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2675 return Set;
2676 }
2677
2678
2679 return Sets.emplace_back();
2680}
2681
2682void CompatibleSets::insert(InvokeInst *II) {
2683 getCompatibleSet(II).emplace_back(II);
2684}
2685
2687 assert(Invokes.size() == 2 && "Always called with exactly two candidates.");
2688
2689
2690 auto IsIllegalToMerge = [](InvokeInst *II) {
2691 return II->cannotMerge() || II->isInlineAsm();
2692 };
2693 if (any_of(Invokes, IsIllegalToMerge))
2694 return false;
2695
2696
2697
2698 auto IsIndirectCall = [](InvokeInst *II) { return II->isIndirectCall(); };
2699 bool HaveIndirectCalls = any_of(Invokes, IsIndirectCall);
2700 bool AllCallsAreIndirect = all_of(Invokes, IsIndirectCall);
2701 if (HaveIndirectCalls) {
2702 if (!AllCallsAreIndirect)
2703 return false;
2704 } else {
2705
2707 for (InvokeInst *II : Invokes) {
2708 Value *CurrCallee = II->getCalledOperand();
2709 assert(CurrCallee && "There is always a called operand.");
2710 if (!Callee)
2711 Callee = CurrCallee;
2712 else if (Callee != CurrCallee)
2713 return false;
2714 }
2715 }
2716
2717
2718
2719 auto HasNormalDest = [](InvokeInst *II) {
2721 };
2722 if (any_of(Invokes, HasNormalDest)) {
2723
2724
2725 if ((Invokes, HasNormalDest))
2726 return false;
2727
2728
2730 for (InvokeInst *II : Invokes) {
2731 BasicBlock *CurrNormalBB = II->getNormalDest();
2732 assert(CurrNormalBB && "There is always a 'continue to' basic block.");
2733 if (!NormalBB)
2734 NormalBB = CurrNormalBB;
2735 else if (NormalBB != CurrNormalBB)
2736 return false;
2737 }
2738
2739
2740
2741 SmallPtrSet<Value *, 16> EquivalenceSet(llvm::from_range, Invokes);
2743 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2744 &EquivalenceSet))
2745 return false;
2746 }
2747
2748#ifndef NDEBUG
2749
2750
2752 for (InvokeInst *II : Invokes) {
2753 BasicBlock *CurrUnwindBB = II->getUnwindDest();
2754 assert(CurrUnwindBB && "There is always an 'unwind to' basic block.");
2755 if (!UnwindBB)
2756 UnwindBB = CurrUnwindBB;
2757 else
2758 assert(UnwindBB == CurrUnwindBB && "Unexpected unwind destination.");
2759 }
2760#endif
2761
2762
2763
2765 Invokes.front()->getUnwindDest(),
2766 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2767 return false;
2768
2769
2770
2771 const InvokeInst *II0 = Invokes.front();
2772 for (auto *II : Invokes.drop_front())
2774 return false;
2775
2776
2777 auto IsIllegalToMergeArguments = [](auto Ops) {
2778 Use &U0 = std::get<0>(Ops);
2779 Use &U1 = std::get<1>(Ops);
2780 if (U0 == U1)
2781 return false;
2784 };
2785 assert(Invokes.size() == 2 && "Always called with exactly two candidates.");
2786 if (any_of(zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2787 IsIllegalToMergeArguments))
2788 return false;
2789
2790 return true;
2791}
2792
2793}
2794
2795
2796
2799 assert(Invokes.size() >= 2 && "Must have at least two invokes to merge.");
2800
2802 if (DTU)
2803 Updates.reserve(2 + 3 * Invokes.size());
2804
2805 bool HasNormalDest =
2807
2808
2809
2810 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2814 II0->getParent()->getIterator()->getNextNode();
2817
2819 Ctx, II0BB->getName() + ".invoke", Func, InsertBeforeBlock);
2820
2822
2823 MergedInvoke->insertInto(MergedInvokeBB, MergedInvokeBB->end());
2824
2825 if (!HasNormalDest) {
2826
2827
2829 Ctx, II0BB->getName() + ".cont", Func, InsertBeforeBlock);
2833 }
2834
2835
2836
2837 return MergedInvoke;
2838 }();
2839
2840 if (DTU) {
2841
2842
2846
2847
2848
2851 SuccBBOfMergedInvoke});
2852
2853
2854
2859 }
2860
2861 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2862
2863
2864 for (Use &U : MergedInvoke->operands()) {
2865
2866 if (MergedInvoke->isCallee(&U)) {
2867 if (!IsIndirectCall)
2868 continue;
2870 continue;
2871
2872
2874 return II->getOperand(U.getOperandNo()) != U.get();
2875 });
2876 if (!NeedPHI)
2877 continue;
2878
2879
2881 U->getType(), Invokes.size(), "", MergedInvoke->getIterator());
2883 PN->addIncoming(II->getOperand(U.getOperandNo()), II->getParent());
2884
2885 U.set(PN);
2886 }
2887
2888
2889
2890
2893 Invokes.front()->getParent());
2894
2895
2896
2897
2898 DILocation *MergedDebugLoc = nullptr;
2900
2901 if (!MergedDebugLoc)
2902 MergedDebugLoc = II->getDebugLoc();
2903 else
2904 MergedDebugLoc =
2906
2907
2908
2910 OrigSuccBB->removePredecessor(II->getParent());
2912
2913
2916 assert(Success && "Merged invokes with incompatible attributes");
2917
2919 II->replaceAllUsesWith(MergedInvoke);
2920 II->eraseFromParent();
2921 ++NumInvokesMerged;
2922 }
2923 MergedInvoke->setDebugLoc(MergedDebugLoc);
2924 ++NumInvokeSetsFormed;
2925
2926 if (DTU)
2928}
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2952 return false;
2953
2955
2956
2959
2960 CompatibleSets Grouper;
2961
2962
2963
2964
2967
2968
2970 if (Invokes.size() < 2)
2971 continue;
2974 }
2975
2977}
2978
2979namespace {
2980
2981
2982class EphemeralValueTracker {
2983 SmallPtrSet<const Instruction *, 32> EphValues;
2984
2985 bool isEphemeral(const Instruction *I) {
2987 return true;
2988 return ->mayHaveSideEffects() &&
->isTerminator() &&
2989 all_of(I->users(), [&](const User *U) {
2990 return EphValues.count(cast(U));
2991 });
2992 }
2993
2994public:
2995 bool track(const Instruction *I) {
2996 if (isEphemeral(I)) {
2998 return true;
2999 }
3000 return false;
3001 }
3002
3003 bool contains(const Instruction *I) const { return EphValues.contains(I); }
3004};
3005}
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3036 if (!StoreToHoist)
3037 return nullptr;
3038
3039
3040 if (!StoreToHoist->isSimple())
3041 return nullptr;
3042
3045
3046
3047 unsigned MaxNumInstToLookAt = 9;
3048
3049
3051 if (!MaxNumInstToLookAt)
3052 break;
3053 --MaxNumInstToLookAt;
3054
3055
3056 if (CurI.mayWriteToMemory() && (CurI))
3057 return nullptr;
3058
3060
3061
3062
3063 if (SI->getPointerOperand() == StorePtr &&
3064 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3065 SI->getAlign() >= StoreToHoist->getAlign())
3066
3067 return SI->getValueOperand();
3068 return nullptr;
3069 }
3070
3072 if (LI->getPointerOperand() == StorePtr && LI->getType() == StoreTy &&
3073 LI->isSimple() && LI->getAlign() >= StoreToHoist->getAlign()) {
3075 bool ExplicitlyDereferenceableOnly;
3080 (!ExplicitlyDereferenceableOnly ||
3082 LI->getDataLayout()))) {
3083
3084 return LI;
3085 }
3086 }
3087
3088 }
3089 }
3090
3091 return nullptr;
3092}
3093
3094
3095
3098 unsigned &SpeculatedInstructions,
3105
3106 bool HaveRewritablePHIs = false;
3108 Value *OrigV = PN.getIncomingValueForBlock(BB);
3109 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3110
3111
3112
3113 if (ThenV == OrigV)
3114 continue;
3115
3116 Cost += TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3119
3120
3123 return false;
3124
3125 HaveRewritablePHIs = true;
3128 if (!OrigCE && !ThenCE)
3129 continue;
3130
3135 if (OrigCost + ThenCost > MaxCost)
3136 return false;
3137
3138
3139
3140
3141
3142 ++SpeculatedInstructions;
3143 if (SpeculatedInstructions > 1)
3144 return false;
3145 }
3146
3147 return HaveRewritablePHIs;
3148}
3149
3151 std::optional Invert,
3153
3154
3155 if (BI->getMetadata(LLVMContext::MD_unpredictable))
3156 return true;
3157
3159 if ((*BI, TWeight, FWeight) || (TWeight + FWeight) == 0)
3160 return true;
3161
3162 if (!Invert.has_value())
3163 return false;
3164
3165 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3169 return BIEndProb < Likely;
3170}
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3210 BasicBlock *ThenBB) {
3211 if (.SpeculateBlocks)
3212 return false;
3213
3214
3217 return false;
3218
3223
3224
3225
3226 bool Invert = false;
3228 assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
3229 Invert = true;
3230 }
3231 assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
3232
3234 return false;
3235
3236
3237
3238
3239
3240
3241 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3242
3243 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3244
3245 unsigned SpeculatedInstructions = 0;
3246 bool HoistLoadsStores = Options.HoistLoadsStoresWithCondFaulting;
3247 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3248 Value *SpeculatedStoreValue = nullptr;
3249 StoreInst *SpeculatedStore = nullptr;
3250 EphemeralValueTracker EphTracker;
3252
3253
3254
3256
3257
3258
3259
3260 SpeculatedPseudoProbes.push_back(&I);
3261 continue;
3262 }
3263
3264
3265 if (EphTracker.track(&I))
3266 continue;
3267
3268
3269
3270 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3272 SpeculatedConditionalLoadsStores.size() <
3274
3275
3276 if (IsSafeCheapLoadStore)
3277 SpeculatedConditionalLoadsStores.push_back(&I);
3278 else
3279 ++SpeculatedInstructions;
3280
3281 if (SpeculatedInstructions > 1)
3282 return false;
3283
3284
3285 if (!IsSafeCheapLoadStore &&
3288 (SpeculatedStoreValue =
3290 return false;
3291 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3294 return false;
3295
3296
3297 if (!SpeculatedStore && SpeculatedStoreValue)
3299
3300
3301
3302
3303 for (Use &Op : I.operands()) {
3306 continue;
3307
3308 ++SinkCandidateUseCounts[OpI];
3309 }
3310 }
3311
3312
3313
3314
3315 for (const auto &[Inst, Count] : SinkCandidateUseCounts)
3316 if (Inst->hasNUses(Count)) {
3317 ++SpeculatedInstructions;
3318 if (SpeculatedInstructions > 1)
3319 return false;
3320 }
3321
3322
3323
3324 bool Convert =
3325 SpeculatedStore != nullptr || !SpeculatedConditionalLoadsStores.empty();
3328 SpeculatedInstructions, Cost, TTI);
3329 if (!Convert || Cost > Budget)
3330 return false;
3331
3332
3333 LLVM_DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";);
3334
3336
3337 if (SpeculatedStoreValue) {
3341 Value *FalseV = SpeculatedStoreValue;
3342 if (Invert)
3345 BrCond, TrueV, FalseV, "spec.store.select", BI);
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375 for (DbgVariableRecord *DbgAssign :
3378 DbgAssign->replaceVariableLocationOp(OrigV, S);
3379 }
3380
3381
3382
3383
3384
3385
3386
3388 if (!SpeculatedStoreValue || &I != SpeculatedStore) {
3389 I.dropLocation();
3390 }
3391 I.dropUBImplyingAttrsAndMetadata();
3392
3393
3394 if (EphTracker.contains(&I)) {
3396 I.eraseFromParent();
3397 }
3398 }
3399
3400
3401
3402 for (auto &It : *ThenBB)
3404
3405
3407 !DVR || !DVR->isDbgAssign())
3408 It.dropOneDbgRecord(&DR);
3410 std::prev(ThenBB->end()));
3411
3412 if (!SpeculatedConditionalLoadsStores.empty())
3414 Sel);
3415
3416
3418 for (PHINode &PN : EndBB->phis()) {
3419 unsigned OrigI = PN.getBasicBlockIndex(BB);
3420 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3421 Value *OrigV = PN.getIncomingValue(OrigI);
3422 Value *ThenV = PN.getIncomingValue(ThenI);
3423
3424
3425 if (OrigV == ThenV)
3426 continue;
3427
3428
3429
3430
3431 Value *TrueV = ThenV, *FalseV = OrigV;
3432 if (Invert)
3434 Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV, "spec.select", BI);
3435 PN.setIncomingValue(OrigI, V);
3436 PN.setIncomingValue(ThenI, V);
3437 }
3438
3439
3440 for (Instruction *I : SpeculatedPseudoProbes)
3441 I->eraseFromParent();
3442
3443 ++NumSpeculations;
3444 return true;
3445}
3446
3448
3449
3451 BlocksSet &ReachesNonLocalUses) {
3452 if (BB == DefBB)
3453 return true;
3454 if (!ReachesNonLocalUses.insert(BB).second)
3455 return true;
3456
3458 return false;
3460 if ((Pred, DefBB, ReachesNonLocalUses))
3461 return false;
3462 return true;
3463}
3464
3465
3468 int Size = 0;
3469 EphemeralValueTracker EphTracker;
3470
3471
3472
3474
3476 if (CI->cannotDuplicate() || CI->isConvergent())
3477 return false;
3478
3479
3480
3481
3484 return false;
3485 }
3486
3487
3488
3489 for (User *U : I.users()) {
3492 if (UsedInBB == BB) {
3494 return false;
3495 } else
3496 NonLocalUseBlocks.insert(UsedInBB);
3497 }
3498
3499
3500 }
3501
3502 return true;
3503}
3504
3507
3508
3510 if (I && I->getParent() == To)
3511 return nullptr;
3512
3513
3519
3520 return nullptr;
3521}
3522
3523
3524
3525
3526static std::optional
3534 if (PN && PN->getParent() == BB) {
3535
3538 return true;
3539 }
3540
3544 } else {
3547 KnownValues[CB].insert(Pred);
3548 }
3549 }
3550
3551 if (KnownValues.empty())
3552 return false;
3553
3554
3555
3556
3557
3559 BlocksSet ReachesNonLocalUseBlocks;
3561 return false;
3562
3563
3564
3565
3566
3567
3570 return false;
3571
3572
3573
3574 for (BasicBlock *UseBB : NonLocalUseBlocks)
3575
3576 if ((UseBB, BB, ReachesNonLocalUseBlocks))
3577 return false;
3578
3579 for (const auto &Pair : KnownValues) {
3583
3584
3585
3586 if (RealDest == BB)
3587 continue;
3588
3589
3592 }))
3593 continue;
3594
3595
3596 if (ReachesNonLocalUseBlocks.contains(RealDest))
3597 continue;
3598
3600 dbgs() << "Condition " << *Cond << " in " << BB->getName()
3601 << " has value " << *Pair.first << " in predecessors:\n";
3602 for (const BasicBlock *PredBB : Pair.second)
3603 dbgs() << " " << PredBB->getName() << "\n";
3604 dbgs() << "Threading to destination " << RealDest->getName() << ".\n";
3605 });
3606
3607
3608
3610
3611
3612 EdgeBB->setName(RealDest->getName() + ".critedge");
3613 EdgeBB->moveBefore(RealDest);
3614
3615
3617
3618
3619
3620
3623 TranslateMap[Cond] = CB;
3624
3625
3626
3631 continue;
3632 }
3633
3635
3636 N->insertInto(EdgeBB, InsertPt);
3637
3638 if (BBI->hasName())
3639 N->setName(BBI->getName() + ".c");
3640
3641
3642
3643 if (const DebugLoc &DL = BBI->getDebugLoc())
3647
3648
3650 if (!BBI->use_empty())
3651 TranslateMap[&*BBI] = V;
3652 if (->mayHaveSideEffects()) {
3653 N->eraseFromParent();
3654
3655 N = nullptr;
3656 }
3657 } else {
3658 if (!BBI->use_empty())
3659 TranslateMap[&*BBI] = N;
3660 }
3661 if (N) {
3662
3663
3664
3665 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3666 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3667 SrcDbgCursor = std::next(BBI);
3668
3669 N->cloneDebugInfoFrom(&*BBI);
3670
3671
3673 if (AC)
3675 }
3676 }
3677
3678 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3679 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3680 InsertPt->cloneDebugInfoFrom(BI);
3681
3686
3687 if (DTU) {
3692 }
3693
3694
3695
3696
3697
3699
3700
3701 return std::nullopt;
3702 }
3703
3704 return false;
3705}
3706
3707bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3708
3709
3710
3712 return false;
3713
3714 std::optional Result;
3715 bool EverChanged = false;
3716 do {
3717
3720 EverChanged |= Result == std::nullopt || *Result;
3721 } while (Result == std::nullopt);
3722 return EverChanged;
3723}
3724
3725
3726
3730 bool SpeculateUnpredictables) {
3731
3732
3733
3734
3735
3736
3738
3741 if (!DomBI)
3742 return false;
3744
3746 return false;
3747
3751 PN->blocks(), std::back_inserter(IfBlocks), [](BasicBlock *IfBlock) {
3752 return cast(IfBlock->getTerminator())->isUnconditional();
3753 });
3754 assert((IfBlocks.size() == 1 || IfBlocks.size() == 2) &&
3755 "Will have either one or two blocks to speculate.");
3756
3757
3758
3759
3760
3761
3762 bool IsUnpredictable = DomBI->getMetadata(LLVMContext::MD_unpredictable);
3763 if (!IsUnpredictable) {
3766 (TWeight + FWeight) != 0) {
3771 if (IfBlocks.size() == 1) {
3773 DomBI->getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3774 if (BIBBProb >= Likely)
3775 return false;
3776 } else {
3777 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3778 return false;
3779 }
3780 }
3781 }
3782
3783
3784
3786 if (IfCondPhiInst->getParent() == BB)
3787 return false;
3788
3789
3790
3791
3792
3793
3794 unsigned NumPhis = 0;
3796 if (NumPhis > 2)
3797 return false;
3798
3799
3800
3801
3807 if (SpeculateUnpredictables && IsUnpredictable)
3808 Budget += TTI.getBranchMispredictPenalty();
3809
3817 continue;
3818 }
3819
3821 AggressiveInsts, Cost, Budget, TTI, AC,
3822 ZeroCostInstructions) ||
3824 AggressiveInsts, Cost, Budget, TTI, AC,
3825 ZeroCostInstructions))
3827 }
3828
3829
3830
3832 if (!PN)
3833 return true;
3834
3835
3836
3837 auto CanHoistNotFromBothValues = [](Value *V0, Value *V1) {
3842 };
3843
3844
3845
3846
3847
3848 auto IsBinOpOrAnd = [](Value *V) {
3851 };
3854 IsBinOpOrAnd(PN->getIncomingValue(1)) || IsBinOpOrAnd(IfCond)) &&
3858
3859
3860
3861
3862
3863 for (BasicBlock *IfBlock : IfBlocks)
3865 if (!AggressiveInsts.count(&*I) && ->isDebugOrPseudoInst()) {
3866
3867
3868
3870 }
3871
3872
3873 if (any_of(IfBlocks,
3876
3877 LLVM_DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond;
3878 if (IsUnpredictable) dbgs() << " (unpredictable)";
3880 << " F: " << IfFalse->getName() << "\n");
3881
3882
3883
3884
3885
3886
3887 for (BasicBlock *IfBlock : IfBlocks)
3889
3891
3893
3896
3897 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3899 "", DomBI);
3902 PN->eraseFromParent();
3903 }
3904
3905
3906
3907
3908 Builder.CreateBr(BB);
3909
3911 if (DTU) {
3915 }
3916
3918 if (DTU)
3920
3921 return true;
3922}
3923
3927
3929 return Builder.CreateBinOp(Opc, LHS, RHS, Name);
3930 if (Opc == Instruction::And)
3931 return Builder.CreateLogicalAnd(LHS, RHS, Name);
3932 if (Opc == Instruction::Or)
3933 return Builder.CreateLogicalOr(LHS, RHS, Name);
3935}
3936
3937
3938
3939
3944 uint64_t &SuccFalseWeight) {
3945 bool PredHasWeights =
3947 bool SuccHasWeights =
3949 if (PredHasWeights || SuccHasWeights) {
3950 if (!PredHasWeights)
3951 PredTrueWeight = PredFalseWeight = 1;
3952 if (!SuccHasWeights)
3953 SuccTrueWeight = SuccFalseWeight = 1;
3954 return true;
3955 } else {
3956 return false;
3957 }
3958}
3959
3960
3961
3962
3963static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3967 "Both blocks must end with a conditional branches.");
3969 "PredBB must be a predecessor of BB.");
3970
3971
3972
3973 uint64_t PTWeight, PFWeight;
3975 if (TTI && !PBI->getMetadata(LLVMContext::MD_unpredictable) &&
3977 (PTWeight + PFWeight) != 0) {
3978 PBITrueProb =
3980 Likely = TTI->getPredictableBranchThreshold();
3981 }
3982
3984
3985 if (PBITrueProb.isUnknown() || PBITrueProb < Likely)
3986 return {{BI->getSuccessor(0), Instruction::Or, false}};
3988
3990 return {{BI->getSuccessor(1), Instruction::And, false}};
3992
3993 if (PBITrueProb.isUnknown() || PBITrueProb < Likely)
3994 return {{BI->getSuccessor(1), Instruction::And, true}};
3996
3998 return {{BI->getSuccessor(0), Instruction::Or, true}};
3999 }
4000 return std::nullopt;
4001}
4002
4009
4010
4013 bool InvertPredCond;
4014 std::tie(CommonSucc, Opc, InvertPredCond) =
4016
4017 LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4018
4020
4021
4022
4023 Builder.CollectMetadataToCopy(BB->getTerminator(),
4024 {LLVMContext::MD_annotation});
4025
4026
4027 if (InvertPredCond) {
4029 }
4030
4033
4034
4035
4036
4038
4039
4040 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4043 SuccTrueWeight, SuccFalseWeight)) {
4044
4046
4047
4048
4049 MDWeights.push_back(PredTrueWeight * SuccTrueWeight);
4050
4051
4052
4053
4054 MDWeights.push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4055 PredTrueWeight * SuccFalseWeight);
4056 } else {
4057
4058
4059
4060
4061 MDWeights.push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4062 PredFalseWeight * SuccTrueWeight);
4063
4064 MDWeights.push_back(PredFalseWeight * SuccFalseWeight);
4065 }
4066
4068 true);
4069
4070
4071
4072 } else
4073 PBI->setMetadata(LLVMContext::MD_prof, nullptr);
4074
4075
4077
4078 if (DTU)
4081
4082
4083
4085 PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
4086
4087 ValueToValueMapTy VMap;
4089
4091
4097 }
4098
4099
4100
4106 if (!MDWeights.empty()) {
4107 assert(isSelectInRoleOfConjunctionOrDisjunction(SI));
4109 false, true);
4110 }
4111
4112 ++NumFoldBranchToCommonDest;
4113 return true;
4114}
4115
4116
4117
4119 return I.getType()->isVectorTy() || any_of(I.operands(), [](Use &U) {
4120 return U->getType()->isVectorTy();
4121 });
4122}
4123
4124
4125
4126
4130 unsigned BonusInstThreshold) {
4131
4132
4134 return false;
4135
4140
4142
4144 Cond->getParent() != BB || ->hasOneUse())
4145 return false;
4146
4147
4149 return false;
4150
4151
4155
4156
4157
4158
4160 continue;
4161
4162
4165 bool InvertPredCond;
4167 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
4168 else
4169 continue;
4170
4171
4172
4173 if (TTI) {
4178 Cost += TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
4179
4181 continue;
4182 }
4183
4184
4186 }
4187
4188
4189
4190 if (Preds.empty())
4191 return false;
4192
4193
4194
4195
4196
4197
4198
4199 unsigned NumBonusInsts = 0;
4200 bool SawVectorOp = false;
4201 const unsigned PredCount = Preds.size();
4203
4205 continue;
4206
4208 continue;
4209
4211 return false;
4213
4214
4215
4218 NumBonusInsts += PredCount;
4219
4220
4221 if (NumBonusInsts >
4223 return false;
4224 }
4225
4226 auto IsBCSSAUse = [BB, &I](Use &U) {
4229 return PN->getIncomingBlock(U) == BB;
4230 return UI->getParent() == BB && I.comesBefore(UI);
4231 };
4232
4233
4234 if ((I.uses(), IsBCSSAUse))
4235 return false;
4236 }
4237 if (NumBonusInsts >
4238 BonusInstThreshold *
4240 return false;
4241
4242
4243 for (BasicBlock *PredBlock : Preds) {
4246 }
4247 return false;
4248}
4249
4250
4251
4254 for (auto *BB : {BB1, BB2}) {
4255 if (!BB)
4256 continue;
4257 for (auto &I : *BB)
4259 if (S)
4260
4261 return nullptr;
4262 else
4263 S = SI;
4264 }
4265 }
4266 return S;
4267}
4268
4270 Value *AlternativeV = nullptr) {
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4287
4289 if (cast(I)->getIncomingValueForBlock(BB) == V) {
4291 if (!AlternativeV)
4292 break;
4293
4296 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4297 if (PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4298 break;
4299 PHI = nullptr;
4300 }
4301 if (PHI)
4302 return PHI;
4303
4304
4305 if (!AlternativeV &&
4307 return V;
4308
4310 PHI->insertBefore(Succ->begin());
4311 PHI->addIncoming(V, BB);
4313 if (PredBB != BB)
4314 PHI->addIncoming(
4315 AlternativeV ? AlternativeV : PoisonValue::get(V->getType()), PredBB);
4316 return PHI;
4317}
4318
4321 BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond,
4323
4324
4325
4326
4327
4330 if (!PStore || !QStore)
4331 return false;
4332
4333
4337 return false;
4338
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4351 if (I.mayReadOrWriteMemory())
4352 return false;
4353 for (auto &I : *QFB)
4354 if (&I != QStore && I.mayReadOrWriteMemory())
4355 return false;
4356 if (QTB)
4357 for (auto &I : *QTB)
4358 if (&I != QStore && I.mayReadOrWriteMemory())
4359 return false;
4362 if (&*I != PStore && I->mayReadOrWriteMemory())
4363 return false;
4364
4365
4366
4368 if (!BB)
4369 return true;
4370
4371
4372
4377
4378 if (I.isTerminator())
4379 continue;
4380
4381
4384 continue;
4385
4387 return false;
4388
4389
4390 Cost +=
4392 if (Cost > Budget)
4393 return false;
4394 }
4395 assert(Cost <= Budget &&
4396 "When we run out of budget we will eagerly return from within the "
4397 "per-instruction loop.");
4398 return true;
4399 };
4400
4401 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4403 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4404 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4405 return false;
4406
4407
4408
4410
4411
4412
4413
4417 if (!NewBB)
4418 return false;
4419 PostBB = NewBB;
4420 }
4421
4422
4423
4430
4435
4439
4440 InvertPCond ^= (PStore->getParent() != PTB);
4441 InvertQCond ^= (QStore->getParent() != QTB);
4442 Value *PPred = InvertPCond ? QB.CreateNot(PCond) : PCond;
4443 Value *QPred = InvertQCond ? QB.CreateNot(QCond) : QCond;
4444
4445 Value *CombinedPred = QB.CreateOr(PPred, QPred);
4446
4449 false,
4450 nullptr, DTU);
4456 if (InvertPCond)
4457 std::swap(PWeights[0], PWeights[1]);
4458 if (InvertQCond)
4459 std::swap(QWeights[0], QWeights[1]);
4462 {CombinedWeights[0], CombinedWeights[1]},
4463 false, true);
4464 }
4465
4469
4470
4471
4472
4474
4477
4478 return true;
4479}
4480
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4516
4517
4518
4520 PostBB = QFB;
4521
4522
4523 if (!PostBB)
4524 return false;
4525
4526 bool InvertPCond = false, InvertQCond = false;
4527
4530 InvertPCond = true;
4531 }
4532 if (QFB == PostBB) {
4534 InvertQCond = true;
4535 }
4536
4537
4538
4540 PTB = nullptr;
4541 if (QTB == PostBB)
4542 QTB = nullptr;
4543
4544
4545
4546
4549 };
4550 if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
4551 !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB))
4552 return false;
4553 if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) ||
4554 (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB)))
4555 return false;
4556 if (!QBI->getParent()->hasNUses(2))
4557 return false;
4558
4559
4560
4562 for (auto *BB : {PTB, PFB}) {
4563 if (!BB)
4564 continue;
4565 for (auto &I : *BB)
4567 PStoreAddresses.insert(SI->getPointerOperand());
4568 }
4569 for (auto *BB : {QTB, QFB}) {
4570 if (!BB)
4571 continue;
4572 for (auto &I : *BB)
4574 QStoreAddresses.insert(SI->getPointerOperand());
4575 }
4576
4577 set_intersect(PStoreAddresses, QStoreAddresses);
4578
4579
4580 auto &CommonAddresses = PStoreAddresses;
4581
4583 for (auto *Address : CommonAddresses)
4586 InvertPCond, InvertQCond, DTU, DL, TTI);
4588}
4589
4590
4591
4592
4595
4596
4597
4598
4599
4600
4604 !BI->getParent()->getSinglePredecessor())
4605 return false;
4606 if (!IfFalseBB->phis().empty())
4607 return false;
4608
4609
4610
4612 return false;
4613
4614 auto NoSideEffects = [](BasicBlock &BB) {
4616 return I.mayWriteToMemory() || I.mayHaveSideEffects();
4617 });
4618 };
4619 if (BI->getSuccessor(1) != IfFalseBB &&
4621 NoSideEffects(*BI->getParent())) {
4625 if (DTU)
4629 return true;
4630 }
4631 if (BI->getSuccessor(0) != IfFalseBB &&
4633 NoSideEffects(*BI->getParent())) {
4637 if (DTU)
4641 return true;
4642 }
4643 return false;
4644}
4645
4646
4647
4648
4649
4656
4657
4658
4659
4662
4663
4664
4666
4667 bool CondIsTrue = PBI->getSuccessor(0) == BB;
4670 return true;
4671 }
4672 }
4673
4674
4675
4676
4678 return true;
4679
4680
4681
4682
4684 return true;
4685
4686
4687
4688
4689
4690
4692 return false;
4693
4694 int PBIOp, BIOp;
4696 PBIOp = 0;
4697 BIOp = 0;
4699 PBIOp = 0;
4700 BIOp = 1;
4702 PBIOp = 1;
4703 BIOp = 0;
4705 PBIOp = 1;
4706 BIOp = 1;
4707 } else {
4708 return false;
4709 }
4710
4711
4712
4713
4715 return false;
4716
4717
4719 if (!PBI->getMetadata(LLVMContext::MD_unpredictable) &&
4721 (static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4722
4724 PredWeights[PBIOp],
4725 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4726
4728 if (CommonDestProb >= Likely)
4729 return false;
4730 }
4731
4732
4733
4734
4735
4738 unsigned NumPhis = 0;
4740 ++II, ++NumPhis) {
4741 if (NumPhis > 2)
4742 return false;
4743 }
4744
4745
4747
4749 << "AND: " << *BI->getParent());
4750
4752
4753
4754
4755
4756
4757
4758
4759
4760 if (OtherDest == BB) {
4761
4762
4766 if (DTU)
4768 OtherDest = InfLoopBlock;
4769 }
4770
4772
4773
4774
4775
4776
4779 if (PBIOp)
4780 PBICond = Builder.CreateNot(PBICond, PBICond->getName() + ".not");
4781
4783 if (BIOp)
4784 BICond = Builder.CreateNot(BICond, BICond->getName() + ".not");
4785
4786
4788 createLogicalOp(Builder, Instruction::Or, PBICond, BICond, "brmerge");
4789
4790
4794
4795 if (DTU) {
4798
4800 }
4801
4802
4803 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4804 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4805 bool HasWeights =
4807 SuccTrueWeight, SuccFalseWeight);
4808 if (HasWeights) {
4809 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4810 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4811 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4812 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4813
4814
4815
4816 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4817 PredOther * SuccCommon,
4818 PredOther * SuccOther};
4819
4821 true);
4822
4823
4826 assert(isSelectInRoleOfConjunctionOrDisjunction(SI));
4827
4829
4830
4832 false, true);
4833 }
4834 }
4835
4836
4837
4839
4840
4841
4842
4843
4844 for (PHINode &PN : CommonDest->phis()) {
4845 Value *BIV = PN.getIncomingValueForBlock(BB);
4846 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent());
4847 Value *PBIV = PN.getIncomingValue(PBBIdx);
4848 if (BIV != PBIV) {
4849
4851 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux"));
4852 PN.setIncomingValue(PBBIdx, NV);
4853
4854
4855 if (HasWeights) {
4856 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4857 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4859 false, true);
4860 }
4861 }
4862 }
4863
4866
4867
4868
4869 return true;
4870}
4871
4872
4873
4874
4875
4876
4877bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4878 Value *Cond, BasicBlock *TrueBB,
4879 BasicBlock *FalseBB,
4880 uint32_t TrueWeight,
4881 uint32_t FalseWeight) {
4882 auto *BB = OldTerm->getParent();
4883
4884
4885
4886
4888 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
4889
4890 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4891
4892
4893 for (BasicBlock *Succ : successors(OldTerm)) {
4894
4895 if (Succ == KeepEdge1)
4896 KeepEdge1 = nullptr;
4897 else if (Succ == KeepEdge2)
4898 KeepEdge2 = nullptr;
4899 else {
4901 true);
4902
4903 if (Succ != TrueBB && Succ != FalseBB)
4904 RemovedSuccessors.insert(Succ);
4905 }
4906 }
4907
4910
4911
4912 if (!KeepEdge1 && !KeepEdge2) {
4913 if (TrueBB == FalseBB) {
4914
4915
4917 } else {
4918
4919
4920 BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB);
4922 false, true);
4923 }
4924 } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4925
4926
4928 } else {
4929
4930
4931
4932 if (!KeepEdge1) {
4933
4935 } else {
4936
4938 }
4939 }
4940
4942
4943 if (DTU) {
4944 SmallVector<DominatorTree::UpdateType, 2> Updates;
4945 Updates.reserve(RemovedSuccessors.size());
4946 for (auto *RemovedSuccessor : RemovedSuccessors)
4947 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4949 }
4950
4951 return true;
4952}
4953
4954
4955
4956
4957
4958bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4959 SelectInst *Select) {
4960
4963 if (!TrueVal || !FalseVal)
4964 return false;
4965
4966
4967 Value *Condition = Select->getCondition();
4968 BasicBlock *TrueBB = SI->findCaseValue(TrueVal)->getCaseSuccessor();
4969 BasicBlock *FalseBB = SI->findCaseValue(FalseVal)->getCaseSuccessor();
4970
4971
4972 uint32_t TrueWeight = 0, FalseWeight = 0;
4973 SmallVector<uint64_t, 8> Weights;
4975 if (HasWeights) {
4977 if (Weights.size() == 1 + SI->getNumCases()) {
4978 TrueWeight =
4979 (uint32_t)Weights[SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4980 FalseWeight =
4981 (uint32_t)Weights[SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4982 }
4983 }
4984
4985
4986 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4987 FalseWeight);
4988}
4989
4990
4991
4992
4993
4994
4995bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
4996 SelectInst *SI) {
4997
5000 if (!TBA || !FBA)
5001 return false;
5002
5003
5006
5007
5008
5009 SmallVector<uint32_t> SelectBranchWeights(2);
5012
5013 return simplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB,
5014 SelectBranchWeights[0],
5015 SelectBranchWeights[1]);
5016}
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5037
5038
5039 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI, nullptr, Builder);
5040}
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5088
5089
5090
5091
5094 return false;
5095
5096
5097
5098
5101 return false;
5102
5103 Value *IcmpCond;
5104 ConstantInt *NewCaseVal;
5106
5107
5110 return false;
5111
5112 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5115
5116
5117 SelectCond = ICI;
5118 SelectTrueVal = Builder.getTrue();
5119 SelectFalseVal = Builder.getFalse();
5121 } else {
5122 SelectCond = Select->getCondition();
5123
5124 if (SelectCond != ICI)
5125 return false;
5126 SelectTrueVal = Select->getTrueValue();
5127 SelectFalseVal = Select->getFalseValue();
5129 }
5130
5132 if (SI->getCondition() != IcmpCond)
5133 return false;
5134
5135
5136
5137
5138 if (SI->getDefaultDest() != BB) {
5139 ConstantInt *VVal = SI->findCaseDest(BB);
5140 assert(VVal && "Should have a unique destination value");
5142
5146 }
5147
5148 return requestResimplify();
5149 }
5150
5151
5152
5153
5154 if (SI->findCaseValue(NewCaseVal) != SI->case_default()) {
5156 if (Predicate == ICmpInst::ICMP_EQ)
5158 else
5160
5163
5164 return requestResimplify();
5165 }
5166
5167
5168
5171 if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
5173 return false;
5174
5175
5176
5177 Value *DefaultCst = SelectFalseVal;
5178 Value *NewCst = SelectTrueVal;
5179
5180 if (ICI->getPredicate() == ICmpInst::ICMP_NE)
5182
5183
5184
5186 Select->replaceAllUsesWith(DefaultCst);
5187 Select->eraseFromParent();
5188 } else {
5190 }
5192
5193 SmallVector<DominatorTree::UpdateType, 2> Updates;
5194
5195
5196
5199 {
5200 SwitchInstProfUpdateWrapper SIW(*SI);
5201 auto W0 = SIW.getSuccessorWeight(0);
5203 if (W0) {
5204 NewW = ((uint64_t(*W0) + 1) >> 1);
5205 SIW.setSuccessorWeight(0, *NewW);
5206 }
5207 SIW.addCase(NewCaseVal, NewBB, NewW);
5208 if (DTU)
5209 Updates.push_back({DominatorTree::Insert, Pred, NewBB});
5210 }
5211
5212
5215 Builder.CreateBr(SuccBlock);
5217 if (DTU) {
5218 Updates.push_back({DominatorTree::Insert, NewBB, SuccBlock});
5220 }
5221 return true;
5222}
5223
5224
5225
5226
5227bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5229 const DataLayout &DL) {
5232 return false;
5233
5234
5235
5236
5237
5238
5239 ConstantComparesGatherer ConstantCompare(Cond, DL);
5240
5241 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5242 Value *CompVal = ConstantCompare.CompValue;
5243 unsigned UsedICmps = ConstantCompare.UsedICmps;
5244 Value *ExtraCase = ConstantCompare.Extra;
5245 bool TrueWhenEqual = ConstantCompare.IsEq;
5246
5247
5248 if (!CompVal)
5249 return false;
5250
5251
5252 if (UsedICmps <= 1)
5253 return false;
5254
5255
5256
5259
5260
5261
5262 if (ExtraCase && Values.size() < 2)
5263 return false;
5264
5265 SmallVector<uint32_t> BranchWeights;
5268
5269
5272 if (!TrueWhenEqual) {
5274 if (HasProfile)
5275 std::swap(BranchWeights[0], BranchWeights[1]);
5276 }
5277
5279
5280 LLVM_DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
5281 << " cases into SWITCH. BB is:\n"
5282 << *BB);
5283
5284 SmallVector<DominatorTree::UpdateType, 2> Updates;
5285
5286
5287
5288
5289 if (ExtraCase) {
5291 nullptr, "switch.early.test");
5292
5293
5296
5297
5298
5299
5300
5301
5302 AssumptionCache *AC = Options.AC;
5303
5305 ExtraCase = Builder.CreateFreeze(ExtraCase);
5306
5307
5308 auto *Br = TrueWhenEqual ? Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB)
5309 : Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
5311
5313
5314 if (DTU)
5315 Updates.push_back({DominatorTree::Insert, BB, EdgeBB});
5316
5317
5318
5320
5321 LLVM_DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase
5322 << "\nEXTRABB = " << *BB);
5323 BB = NewBB;
5324 }
5325
5327
5329 assert(.hasUnstableRepresentation(CompVal->getType()) &&
5330 "Should not end up here with unstable pointers");
5332 CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr");
5333 }
5334
5335
5336
5337 if (Values.front()->getValue() - Values.back()->getValue() ==
5338 Values.size() - 1) {
5340 Values.back()->getValue(), Values.front()->getValue() + 1);
5342 ICmpInst::Predicate Pred;
5345 if (.isZero())
5349 BranchInst *NewBI = Builder.CreateCondBr(Cond, EdgeBB, DefaultBB);
5350 if (HasProfile)
5351 setBranchWeights(*NewBI, BranchWeights, false);
5352
5353 } else {
5354
5355 SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size());
5356 if (HasProfile) {
5357
5358
5359
5360 SmallVector<uint32_t> NewWeights(Values.size() + 1);
5361 NewWeights[0] = BranchWeights[1];
5362
5363 for (auto &V : drop_begin(NewWeights))
5364 V = BranchWeights[0] / Values.size();
5366 }
5367
5368
5369 for (ConstantInt *Val : Values)
5370 New->addCase(Val, EdgeBB);
5371
5372
5373
5374
5378 for (unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5380 }
5381 }
5382
5383
5385 if (DTU)
5387
5388 LLVM_DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n');
5389 return true;
5390}
5391
5392bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
5394 return simplifyCommonResume(RI);
5397
5398 return simplifySingleResume(RI);
5399
5400 return false;
5401}
5402
5403
5407 if ()
5408 return false;
5409
5411 switch (IntrinsicID) {
5412 case Intrinsic::dbg_declare:
5413 case Intrinsic::dbg_value:
5414 case Intrinsic::dbg_label:
5415 case Intrinsic::lifetime_end:
5416 break;
5417 default:
5418 return false;
5419 }
5420 }
5421 return true;
5422}
5423
5424
5425bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5427
5428
5429
5432 return false;
5433
5434 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5436
5437
5438 for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5439 Idx++) {
5440 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5441 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5442
5443
5444
5445 if (IncomingBB->getUniqueSuccessor() != BB)
5446 continue;
5447
5449
5450 if (IncomingValue != LandingPad)
5451 continue;
5452
5454 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5455 TrivialUnwindBlocks.insert(IncomingBB);
5456 }
5457
5458
5459 if (TrivialUnwindBlocks.empty())
5460 return false;
5461
5462
5463 for (auto *TrivialBB : TrivialUnwindBlocks) {
5464
5465
5466
5467 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5469
5470 for (BasicBlock *Pred :
5473 ++NumInvokes;
5474 }
5475
5476
5477
5478
5479
5480
5481 TrivialBB->getTerminator()->eraseFromParent();
5482 new UnreachableInst(RI->getContext(), TrivialBB);
5483 if (DTU)
5484 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5485 }
5486
5487
5490
5491 return !TrivialUnwindBlocks.empty();
5492}
5493
5494
5495bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5499 "Resume must unwind the exception that caused control to here");
5500
5501
5504 return false;
5505
5506
5509 ++NumInvokes;
5510 }
5511
5512
5514 return true;
5515}
5516
5518
5519
5520
5521
5522
5523
5524
5525
5529
5530 return false;
5531
5532
5533
5535 return false;
5536
5537
5540 return false;
5541
5542
5543
5545
5546
5547
5548
5549
5550
5551 if (UnwindDest) {
5552
5553
5554 for (PHINode &DestPN : UnwindDest->phis()) {
5555 int Idx = DestPN.getBasicBlockIndex(BB);
5556
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569 Value *SrcVal = DestPN.getIncomingValue(Idx);
5571
5572 bool NeedPHITranslation = SrcPN && SrcPN->getParent() == BB;
5576 DestPN.addIncoming(Incoming, Pred);
5577 }
5578 }
5579
5580
5584
5585
5586
5587 continue;
5588
5589
5590
5591
5592
5594 if (pred != BB)
5597
5598
5600 }
5601 }
5602
5603 std::vectorDominatorTree::UpdateType Updates;
5604
5605
5607 if (UnwindDest == nullptr) {
5608 if (DTU) {
5610 Updates.clear();
5611 }
5613 ++NumInvokes;
5614 } else {
5616 Instruction *TI = PredBB->getTerminator();
5618 if (DTU) {
5621 }
5622 }
5623 }
5624
5625 if (DTU)
5627
5629
5630 return true;
5631}
5632
5633
5635
5636
5638 if (!UnwindDest)
5639 return false;
5640
5641
5642
5644 return false;
5645
5646
5648 if (!SuccessorCleanupPad)
5649 return false;
5650
5652
5653
5654
5656
5657 SuccessorCleanupPad->eraseFromParent();
5658
5659
5662
5663 return true;
5664}
5665
5666bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5667
5668
5669
5671 return false;
5672
5674 return true;
5675
5677 return true;
5678
5679 return false;
5680}
5681
5682
5683bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5685
5687
5688
5689
5690
5692
5693
5694
5696
5697
5698
5701 --BBI;
5702
5704 break;
5705
5706
5707
5708
5709
5710
5711
5712
5713
5714
5715 BBI->dropDbgRecords();
5716
5717
5719 BBI->eraseFromParent();
5721 }
5722
5723
5724
5725 if (&BB->front() != UI)
5727
5728 std::vectorDominatorTree::UpdateType Updates;
5729
5730 SmallSetVector<BasicBlock *, 8> Preds(pred_begin(BB), pred_end(BB));
5731 for (BasicBlock *Predecessor : Preds) {
5732 Instruction *TI = Predecessor->getTerminator();
5735
5736
5738 [BB](auto *Successor) { return Successor == BB; })) {
5742 } else {
5746 "The destinations are guaranteed to be different here.");
5747 CallInst *Assumption;
5751 } else {
5755 }
5758
5761 }
5762 if (DTU)
5763 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5765 SwitchInstProfUpdateWrapper SU(*SI);
5766 for (auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5767 if (i->getCaseSuccessor() != BB) {
5768 ++i;
5769 continue;
5770 }
5772 i = SU.removeCase(i);
5773 e = SU->case_end();
5775 }
5776
5777 if (DTU && SI->getDefaultDest() != BB)
5778 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5780 if (II->getUnwindDest() == BB) {
5781 if (DTU) {
5783 Updates.clear();
5784 }
5786 if (!CI->doesNotThrow())
5787 CI->setDoesNotThrow();
5789 }
5791 if (CSI->getUnwindDest() == BB) {
5792 if (DTU) {
5794 Updates.clear();
5795 }
5798 continue;
5799 }
5800
5802 E = CSI->handler_end();
5804 if (*I == BB) {
5805 CSI->removeHandler(I);
5806 --I;
5807 --E;
5809 }
5810 }
5811 if (DTU)
5812 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5813 if (CSI->getNumHandlers() == 0) {
5814 if (CSI->hasUnwindDest()) {
5815
5816
5817 if (DTU) {
5818 for (auto *PredecessorOfPredecessor : predecessors(Predecessor)) {
5819 Updates.push_back({DominatorTree::Insert,
5820 PredecessorOfPredecessor,
5821 CSI->getUnwindDest()});
5822 Updates.push_back({DominatorTree::Delete,
5823 PredecessorOfPredecessor, Predecessor});
5824 }
5825 }
5826 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5827 } else {
5828
5829 if (DTU) {
5831 Updates.clear();
5832 }
5833 SmallVector<BasicBlock *, 8> EHPreds(predecessors(Predecessor));
5834 for (BasicBlock *EHPred : EHPreds)
5836 }
5837
5838 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5839 CSI->eraseFromParent();
5841 }
5843 (void)CRI;
5844 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5845 "Expected to always have an unwind to BB.");
5846 if (DTU)
5847 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5851 }
5852 }
5853
5854 if (DTU)
5856
5857
5860 return true;
5861 }
5862
5864}
5865
5874
5875static std::optional
5880
5882 const APInt &Min = Cases.back()->getValue();
5883 const APInt &Max = Cases.front()->getValue();
5885 size_t ContiguousOffset = Cases.size() - 1;
5886 if (Offset == ContiguousOffset) {
5888 Cases.back(),
5889 Cases.front(),
5890 Dest,
5891 OtherDest,
5892 &Cases,
5893 &OtherCases,
5894 };
5895 }
5897
5898
5899
5900
5903 auto *It =
5904 std::adjacent_find(Cases.begin(), Cases.end(), [](auto L, auto R) {
5905 return L->getValue() != R->getValue() + 1;
5906 });
5907 if (It == Cases.end())
5908 return std::nullopt;
5909 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5910 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5911 Cases.size() - 2) {
5914 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5915
5917 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5918 OtherDest,
5919 Dest,
5920 &OtherCases,
5921 &Cases,
5922 };
5923 }
5924 }
5925 return std::nullopt;
5926}
5927
5930 bool RemoveOrigDefaultBlock = true) {
5931 LLVM_DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n");
5932 auto *BB = Switch->getParent();
5933 auto *OrigDefaultBlock = Switch->getDefaultDest();
5934 if (RemoveOrigDefaultBlock)
5935 OrigDefaultBlock->removePredecessor(BB);
5938 OrigDefaultBlock);
5939 auto *UI = new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5941 Switch->setDefaultDest(&*NewDefaultBlock);
5942 if (DTU) {
5945 if (RemoveOrigDefaultBlock &&
5949 }
5950}
5951
5952
5953
5954
5955bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5957 assert(SI->getNumCases() > 1 && "Degenerate switch?");
5958
5959 bool HasDefault = ->defaultDestUnreachable();
5960
5961 auto *BB = SI->getParent();
5962
5963 BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr;
5967
5968 for (auto Case : SI->cases()) {
5969 BasicBlock *Dest = Case.getCaseSuccessor();
5970 if (!DestA)
5971 DestA = Dest;
5972 if (Dest == DestA) {
5973 CasesA.push_back(Case.getCaseValue());
5974 continue;
5975 }
5976 if (!DestB)
5977 DestB = Dest;
5978 if (Dest == DestB) {
5979 CasesB.push_back(Case.getCaseValue());
5980 continue;
5981 }
5982 return false;
5983 }
5984 if (!DestB)
5985 return false;
5986
5987 assert(DestA && DestB &&
5988 "Single-destination switch should have been folded.");
5989 assert(DestA != DestB);
5990 assert(DestB != SI->getDefaultDest());
5991 assert(!CasesB.empty() && "There must be non-default cases.");
5993
5994
5995 std::optional ContiguousCases;
5996
5997
5998 if (!HasDefault && CasesA.size() == 1)
5999 ContiguousCases = ContiguousCasesResult{
6000 CasesA[0],
6001 CasesA[0],
6002 DestA,
6003 DestB,
6004 &CasesA,
6005 &CasesB,
6006 };
6007 else if (CasesB.size() == 1)
6008 ContiguousCases = ContiguousCasesResult{
6009 CasesB[0],
6010 CasesB[0],
6011 DestB,
6012 DestA,
6013 &CasesB,
6014 &CasesA,
6015 };
6016
6017 else if (!HasDefault)
6018 ContiguousCases =
6020
6021 if (!ContiguousCases)
6022 ContiguousCases =
6024
6025 if (!ContiguousCases)
6026 return false;
6027
6028 auto [Min, Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6029
6030
6031
6033 Constant *NumCases = ConstantInt::get(Offset->getType(),
6034 Max->getValue() - Min->getValue() + 1);
6035 BranchInst *NewBI;
6037 assert(Max->getValue() == Min->getValue());
6039 NewBI = Builder.CreateCondBr(Cmp, Dest, OtherDest);
6040 }
6041
6042 else if (NumCases->isNullValue() && !Cases->empty()) {
6043 NewBI = Builder.CreateBr(Dest);
6044 } else {
6046 if (->isNullValue())
6049 NewBI = Builder.CreateCondBr(Cmp, Dest, OtherDest);
6050 }
6051
6052
6054 SmallVector<uint64_t, 8> Weights;
6056 if (Weights.size() == 1 + SI->getNumCases()) {
6057 uint64_t TrueWeight = 0;
6058 uint64_t FalseWeight = 0;
6059 for (size_t I = 0, E = Weights.size(); I != E; ++I) {
6060 if (SI->getSuccessor(I) == Dest)
6061 TrueWeight += Weights[I];
6062 else
6063 FalseWeight += Weights[I];
6064 }
6065 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6066 TrueWeight /= 2;
6067 FalseWeight /= 2;
6068 }
6070 false, true);
6071 }
6072 }
6073
6074
6076 unsigned PreviousEdges = Cases->size();
6077 if (Dest == SI->getDefaultDest())
6078 ++PreviousEdges;
6079 for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
6080 PHI.removeIncomingValue(SI->getParent());
6081 }
6083 unsigned PreviousEdges = OtherCases->size();
6084 if (OtherDest == SI->getDefaultDest())
6085 ++PreviousEdges;
6086 unsigned E = PreviousEdges - 1;
6087
6089 ++E;
6090 for (unsigned I = 0; I != E; ++I)
6091 PHI.removeIncomingValue(SI->getParent());
6092 }
6093
6094
6095
6096 if (!HasDefault)
6098
6099 auto *UnreachableDefault = SI->getDefaultDest();
6100
6101
6102 SI->eraseFromParent();
6103
6104 if (!HasDefault && DTU)
6105 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6106
6107 return true;
6108}
6109
6110
6111
6119
6120
6121
6122
6123 unsigned MaxSignificantBitsInCond =
6125
6126
6130 for (const auto &Case : SI->cases()) {
6131 auto *Successor = Case.getCaseSuccessor();
6132 if (DTU) {
6134 if (Inserted)
6136 ++It->second;
6137 }
6138 ConstantInt *CaseC = Case.getCaseValue();
6142 (IsKnownValuesValid && !KnownValues.contains(CaseC))) {
6144 if (DTU)
6145 --NumPerSuccessorCases[Successor];
6146 LLVM_DEBUG(dbgs() << "SimplifyCFG: switch case " << CaseVal
6147 << " is dead.\n");
6148 } else if (IsKnownValuesValid)
6149 KnownValues.erase(CaseC);
6150 }
6151
6152
6153
6154
6155
6156 bool HasDefault = ->defaultDestUnreachable();
6157 const unsigned NumUnknownBits =
6160 if (HasDefault && DeadCases.empty()) {
6163 return true;
6164 }
6165
6166 if (NumUnknownBits < 64 ) {
6167 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6168 if (SI->getNumCases() == AllNumCases) {
6170 return true;
6171 }
6172
6173
6174
6175 if (SI->getNumCases() == AllNumCases - 1) {
6176 assert(NumUnknownBits > 1 && "Should be canonicalized to a branch");
6180 return false;
6181
6182 uint64_t MissingCaseVal = 0;
6183 for (const auto &Case : SI->cases())
6184 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6186 ConstantInt::get(Cond->getType(), MissingCaseVal));
6188 SIW.addCase(MissingCase, SI->getDefaultDest(),
6191 false);
6193 return true;
6194 }
6195 }
6196 }
6197
6198 if (DeadCases.empty())
6199 return false;
6200
6202 for (ConstantInt *DeadCase : DeadCases) {
6204 assert(CaseI != SI->case_default() &&
6205 "Case was not found. Probably mistake in DeadCases forming.");
6206
6207 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
6209 }
6210
6211 if (DTU) {
6212 std::vectorDominatorTree::UpdateType Updates;
6213 for (auto *Successor : UniqueSuccessors)
6214 if (NumPerSuccessorCases[Successor] == 0)
6217 }
6218
6219 return true;
6220}
6221
6222
6223
6224
6225
6226
6230 return nullptr;
6232 return nullptr;
6233
6235 if (!Branch || !Branch->isUnconditional())
6236 return nullptr;
6237
6238 BasicBlock *Succ = Branch->getSuccessor(0);
6239
6241 int Idx = PHI.getBasicBlockIndex(BB);
6242 assert(Idx >= 0 && "PHI has no entry for predecessor?");
6243
6244 Value *InValue = PHI.getIncomingValue(Idx);
6245 if (InValue != CaseValue)
6246 continue;
6247
6248 *PhiIndex = Idx;
6249 return &PHI;
6250 }
6251
6252 return nullptr;
6253}
6254
6255
6256
6257
6260
6261 ForwardingNodesMap ForwardingNodes;
6264 for (const auto &Case : SI->cases()) {
6265 ConstantInt *CaseValue = Case.getCaseValue();
6266 BasicBlock *CaseDest = Case.getCaseSuccessor();
6267
6268
6269
6270
6271
6272
6273
6274
6275
6276
6277
6278
6280
6281
6282
6283
6284
6285 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6286 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6287 count(Phi.blocks(), SwitchBlock) == 1) {
6288 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6290 }
6291 }
6292
6293
6294 int PhiIdx;
6296 ForwardingNodes[Phi].push_back(PhiIdx);
6297 }
6298
6299 for (auto &ForwardingNode : ForwardingNodes) {
6300 PHINode *Phi = ForwardingNode.first;
6302
6304 continue;
6305
6306 for (int Index : Indexes)
6307 Phi->setIncomingValue(Index, SI->getCondition());
6309 }
6310
6312}
6313
6314
6315
6317 if (C->isThreadDependent())
6318 return false;
6319 if (C->isDLLImportDependent())
6320 return false;
6321
6325 return false;
6326
6328
6329
6332 return false;
6333 }
6334
6335 if (.shouldBuildLookupTablesForConstant(C))
6336 return false;
6337
6338 return true;
6339}
6340
6341
6342
6350
6351
6352
6353
6354
6360 if ()
6361 return nullptr;
6362 if (A->isAllOnesValue())
6364 if (A->isNullValue())
6366 return nullptr;
6367 }
6368
6370 for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) {
6373 else
6374 return nullptr;
6375 }
6376
6378}
6379
6380
6381
6382
6383
6384static bool
6389
6391
6392
6393
6395 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6397 if (I.isTerminator()) {
6398
6399 if (I.getNumSuccessors() != 1 || I.isSpecialTerminator())
6400 return false;
6401 Pred = CaseDest;
6402 CaseDest = I.getSuccessor(0);
6404
6405
6406
6407
6408
6409 for (auto &Use : I.uses()) {
6412 if (I->getParent() == CaseDest)
6413 continue;
6415 if (Phi->getIncomingBlock(Use) == CaseDest)
6416 continue;
6417 return false;
6418 }
6419
6421 } else {
6422 break;
6423 }
6424 }
6425
6426
6427 if (!*CommonDest)
6428 *CommonDest = CaseDest;
6429
6430 if (CaseDest != *CommonDest)
6431 return false;
6432
6433
6434 for (PHINode &PHI : (*CommonDest)->phis()) {
6435 int Idx = PHI.getBasicBlockIndex(Pred);
6436 if (Idx == -1)
6437 continue;
6438
6441 if (!ConstVal)
6442 return false;
6443
6444
6446 return false;
6447
6448 Res.push_back(std::make_pair(&PHI, ConstVal));
6449 }
6450
6451 return Res.size() > 0;
6452}
6453
6454
6455
6457 SwitchCaseResultVectorTy &UniqueResults,
6459 for (auto &I : UniqueResults) {
6460 if (I.first == Result) {
6461 I.second.push_back(CaseVal);
6462 return I.second.size();
6463 }
6464 }
6465 UniqueResults.push_back(
6467 return 1;
6468}
6469
6470
6471
6472
6473
6476 SwitchCaseResultVectorTy &UniqueResults,
6480 uintptr_t MaxUniqueResults) {
6481 for (const auto &I : SI->cases()) {
6483
6484
6485 SwitchCaseResultsTy Results;
6488 return false;
6489
6490
6492 return false;
6493
6494
6495 const size_t NumCasesForResult =
6497
6498
6500 return false;
6501
6502
6503 if (UniqueResults.size() > MaxUniqueResults)
6504 return false;
6505
6506
6507 if ()
6510 return false;
6511 }
6512
6514 getCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6516
6517
6518 DefaultResult =
6519 DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
6520
6521 return DefaultResult || SI->defaultDestUnreachable();
6522}
6523
6524
6525
6526
6527
6528
6533
6534
6535
6536
6537
6538
6539
6540
6541
6542 const bool HasBranchWeights =
6544
6545 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6546 ResultVector[1].second.size() == 1) {
6547 ConstantInt *FirstCase = ResultVector[0].second[0];
6548 ConstantInt *SecondCase = ResultVector[1].second[0];
6549 Value *SelectValue = ResultVector[1].first;
6550 if (DefaultResult) {
6551 Value *ValueCompare =
6552 Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp");
6553 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6554 DefaultResult, "switch.select");
6556 SI && HasBranchWeights) {
6557
6558
6559
6560
6563 *SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6564 false, true);
6565 }
6566 }
6567 Value *ValueCompare =
6568 Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp");
6569 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6570 SelectValue, "switch.select");
6572
6573
6574
6576 size_t FirstCasePos = (Condition != nullptr);
6577 size_t SecondCasePos = FirstCasePos + 1;
6578 uint32_t DefaultCase = (Condition != nullptr) ? BranchWeights[0] : 0;
6580 {BranchWeights[FirstCasePos],
6581 DefaultCase + BranchWeights[SecondCasePos]},
6582 false, true);
6583 }
6584 return Ret;
6585 }
6586
6587
6588 if (ResultVector.size() == 1 && DefaultResult) {
6590 unsigned CaseCount = CaseValues.size();
6591
6592
6593
6594
6596 ConstantInt *MinCaseVal = CaseValues[0];
6597
6598
6599
6601
6602
6603 for (auto *Case : CaseValues) {
6604 if (Case->getValue().slt(MinCaseVal->getValue()))
6605 MinCaseVal = Case;
6606 AndMask &= Case->getValue();
6607 }
6609
6611
6613
6614
6615
6616 if (FreeBits == Log2_32(CaseCount)) {
6617 Value *And = Builder.CreateAnd(Condition, AndMask);
6618 Value *Cmp = Builder.CreateICmpEQ(
6621 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6623
6624
6627 *SI,
6629 false, true);
6630 }
6631 return Ret;
6632 }
6633 }
6634
6635
6637 for (auto *Case : CaseValues)
6638 BitMask |= (Case->getValue() - MinCaseVal->getValue());
6639
6640
6641
6644 Condition = Builder.CreateSub(Condition, MinCaseVal);
6645 Value *And = Builder.CreateAnd(Condition, ~BitMask, "switch.and");
6646 Value *Cmp = Builder.CreateICmpEQ(
6649 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6653 *SI,
6655 false, true);
6656 }
6657 return Ret;
6658 }
6659 }
6660
6661
6662 if (CaseValues.size() == 2) {
6663 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6664 "switch.selectcmp.case1");
6665 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6666 "switch.selectcmp.case2");
6667 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2, "switch.selectcmp");
6669 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6674 false, true);
6675 }
6676 return Ret;
6677 }
6678 }
6679
6680 return nullptr;
6681}
6682
6683
6684
6686 Value *SelectValue,
6689 std::vectorDominatorTree::UpdateType Updates;
6690
6693
6696 Builder.CreateBr(DestBB);
6697
6698
6699
6700 PHI->removeIncomingValueIf(
6701 [&](unsigned Idx) { return PHI->getIncomingBlock(Idx) == SelectBB; });
6702 PHI->addIncoming(SelectValue, SelectBB);
6703
6705 for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6707
6708 if (Succ == DestBB)
6709 continue;
6711 if (DTU && RemovedSuccessors.insert(Succ).second)
6713 }
6714 SI->eraseFromParent();
6715 if (DTU)
6717}
6718
6719
6720
6721
6729 SwitchCaseResultVectorTy UniqueResults;
6730
6733 return false;
6734
6735 assert(PHI != nullptr && "PHI for value select not found");
6736 Builder.SetInsertPoint(SI);
6739 [[maybe_unused]] auto HasWeights =
6741 assert(!HasWeights == (BranchWeights.empty()));
6742 }
6744 (BranchWeights.size() >=
6745 UniqueResults.size() + (DefaultResult != nullptr)));
6746
6748 Builder, DL, BranchWeights);
6749 if (!SelectValue)
6750 return false;
6751
6753 return true;
6754}
6755
6756namespace {
6757
6758
6759
6760class SwitchReplacement {
6761public:
6762
6763
6764
6765 SwitchReplacement(
6766 Module &M, uint64_t TableSize, ConstantInt *Offset,
6767 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6768 Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName);
6769
6770
6771
6773 Function *Func);
6774
6775
6776
6777 static bool wouldFitInRegister(const DataLayout &DL, uint64_t TableSize,
6778 Type *ElementType);
6779
6780
6781 Constant *getDefaultValue();
6782
6783
6784 bool isLookupTable();
6785
6786
6787 bool isBitMap();
6788
6789private:
6790
6791 enum {
6792
6793
6794 SingleValueKind,
6795
6796
6797
6798
6799 LinearMapKind,
6800
6801
6802
6803
6804 BitMapKind,
6805
6806
6807
6808 LookupTableKind
6809 } Kind;
6810
6811
6813
6814
6816
6817
6818 Constant *SingleValue = nullptr;
6819
6820
6821 ConstantInt *BitMap = nullptr;
6822 IntegerType *BitMapElementTy = nullptr;
6823
6824
6825 ConstantInt *LinearOffset = nullptr;
6826 ConstantInt *LinearMultiplier = nullptr;
6827 bool LinearMapValWrapped = false;
6828
6829
6830 Constant *Initializer = nullptr;
6831};
6832
6833}
6834
6835SwitchReplacement::SwitchReplacement(
6836 Module &M, uint64_t TableSize, ConstantInt *Offset,
6837 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6838 Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName)
6839 : DefaultValue(DefaultValue) {
6840 assert(Values.size() && "Can't build lookup table without values!");
6841 assert(TableSize >= Values.size() && "Can't fit values in table!");
6842
6843
6844 SingleValue = Values.begin()->second;
6845
6846 ValueType = Values.begin()->second->getType();
6847
6848
6850 for (const auto &[CaseVal, CaseRes] : Values) {
6852
6853 uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue();
6854 TableContents[Idx] = CaseRes;
6855
6856 if (SingleValue && (CaseRes) && CaseRes != SingleValue)
6857 SingleValue = isa(SingleValue) ? CaseRes : nullptr;
6858 }
6859
6860
6861 if (Values.size() < TableSize) {
6862 assert(DefaultValue &&
6863 "Need a default value to fill the lookup table holes.");
6865 for (uint64_t I = 0; I < TableSize; ++I) {
6866 if (!TableContents[I])
6867 TableContents[I] = DefaultValue;
6868 }
6869
6870
6872
6873 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6874 SingleValue = nullptr;
6875 }
6876
6877
6878
6879 if (SingleValue) {
6880 Kind = SingleValueKind;
6881 return;
6882 }
6883
6884
6885
6887 bool LinearMappingPossible = true;
6889 APInt DistToPrev;
6890
6891
6892 bool NonMonotonic = false;
6893 assert(TableSize >= 2 && "Should be a SingleValue table.");
6894
6895 for (uint64_t I = 0; I < TableSize; ++I) {
6897
6899
6900
6901
6902
6903
6905 }
6906
6907 if (!ConstVal) {
6908
6909
6910 LinearMappingPossible = false;
6911 break;
6912 }
6914 if (I != 0) {
6915 APInt Dist = Val - PrevVal;
6916 if (I == 1) {
6917 DistToPrev = Dist;
6918 } else if (Dist != DistToPrev) {
6919 LinearMappingPossible = false;
6920 break;
6921 }
6922 NonMonotonic |=
6924 }
6925 PrevVal = Val;
6926 }
6927 if (LinearMappingPossible) {
6929 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6930 APInt M = LinearMultiplier->getValue();
6931 bool MayWrap = true;
6932 if (isIntN(M.getBitWidth(), TableSize - 1))
6933 (void)M.smul_ov(APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6934 LinearMapValWrapped = NonMonotonic || MayWrap;
6935 Kind = LinearMapKind;
6936 return;
6937 }
6938 }
6939
6940
6941 if (wouldFitInRegister(DL, TableSize, ValueType)) {
6943 APInt TableInt(TableSize * IT->getBitWidth(), 0);
6944 for (uint64_t I = TableSize; I > 0; --I) {
6945 TableInt <<= IT->getBitWidth();
6946
6949 TableInt |= Val->getValue().zext(TableInt.getBitWidth());
6950 }
6951 }
6952 BitMap = ConstantInt::get(M.getContext(), TableInt);
6953 BitMapElementTy = IT;
6954 Kind = BitMapKind;
6955 return;
6956 }
6957
6958
6961
6962 Kind = LookupTableKind;
6963}
6964
6967 switch (Kind) {
6968 case SingleValueKind:
6969 return SingleValue;
6970 case LinearMapKind: {
6971 ++NumLinearMaps;
6972
6974 false, "switch.idx.cast");
6975 if (!LinearMultiplier->isOne())
6976 Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult",
6977 false,
6978 !LinearMapValWrapped);
6979
6980 if (!LinearOffset->isZero())
6981 Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset",
6982 false,
6983 !LinearMapValWrapped);
6985 }
6986 case BitMapKind: {
6987 ++NumBitMaps;
6988
6990
6991
6992
6993
6995
6996
6997
6998
7000 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
7001 "switch.shiftamt",true,true);
7002
7003
7004 Value *DownShifted =
7005 Builder.CreateLShr(BitMap, ShiftAmt, "switch.downshift");
7006
7007 return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked");
7008 }
7009 case LookupTableKind: {
7010 ++NumLookupTables;
7011 auto *Table =
7012 new GlobalVariable(*Func->getParent(), Initializer->getType(),
7013 true, GlobalVariable::PrivateLinkage,
7014 Initializer, "switch.table." + Func->getName());
7015 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7016
7017
7018 Table->setAlignment(DL.getPrefTypeAlign(ValueType));
7019 Type *IndexTy = DL.getIndexType(Table->getType());
7021
7022 if (Index->getType() != IndexTy) {
7023 unsigned OldBitWidth = Index->getType()->getIntegerBitWidth();
7026 Zext->setNonNeg(
7027 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7028 }
7029
7030 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0), Index};
7032 Builder.CreateInBoundsGEP(ArrayTy, Table, GEPIndices, "switch.gep");
7033 return Builder.CreateLoad(ArrayTy->getElementType(), GEP, "switch.load");
7034 }
7035 }
7037}
7038
7039bool SwitchReplacement::wouldFitInRegister(const DataLayout &DL,
7040 uint64_t TableSize,
7041 Type *ElementType) {
7043 if ()
7044 return false;
7045
7046
7047
7048
7049 if (TableSize >= UINT_MAX / IT->getBitWidth())
7050 return false;
7051 return DL.fitsInLegalInteger(TableSize * IT->getBitWidth());
7052}
7053
7056
7057 if (TTI.isTypeLegal(Ty))
7058 return true;
7059
7061 if ()
7062 return false;
7063
7064
7065
7066
7067
7068
7069
7070 unsigned BitWidth = IT->getBitWidth();
7072 DL.fitsInLegalInteger(IT->getBitWidth());
7073}
7074
7075Constant *SwitchReplacement::getDefaultValue() { return DefaultValue; }
7076
7077bool SwitchReplacement::isLookupTable() { return Kind == LookupTableKind; }
7078
7079bool SwitchReplacement::isBitMap() { return Kind == BitMapKind; }
7080
7082
7083
7084
7085 const uint64_t MinDensity = 40;
7086
7088 return false;
7089
7090 return NumCases * 100 >= CaseRange * MinDensity;
7091}
7092
7096 if (Range < Diff)
7097 return false;
7098
7100}
7101
7102
7103
7104
7105
7106
7111 if (SI->getNumCases() > TableSize)
7112 return false;
7113
7114 bool AllTablesFitInRegister = true;
7115 bool HasIllegalType = false;
7116 for (const auto &Ty : ResultTypes) {
7117
7119
7120
7121 AllTablesFitInRegister =
7122 AllTablesFitInRegister &&
7123 SwitchReplacement::wouldFitInRegister(DL, TableSize, Ty);
7124
7125
7126
7127
7128 if (HasIllegalType && !AllTablesFitInRegister)
7129 break;
7130 }
7131
7132
7133 if (AllTablesFitInRegister)
7134 return true;
7135
7136
7137 if (HasIllegalType)
7138 return false;
7139
7141}
7142
7148 return true;
7150 MaxCaseVal.getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7151 !HasDefaultResults)
7152 return false;
7153 return all_of(ResultTypes, [&](const auto &ResultType) {
7154 return SwitchReplacement::wouldFitInRegister(
7155 DL, MaxCaseVal.getLimitedValue() + 1 , ResultType);
7156 });
7157}
7158
7159
7160
7161
7162
7163
7164
7165
7166
7167
7168
7169
7170
7171
7172
7173
7174
7175
7176
7177
7178
7182 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7185 return;
7186
7187
7188
7190 return;
7191
7193 if (!CmpOp1)
7194 return;
7195
7199
7200
7204 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7205 return;
7206
7207
7208
7209 for (auto ValuePair : Values) {
7212 if (!CaseConst || CaseConst == DefaultConst ||
7213 (CaseConst != TrueConst && CaseConst != FalseConst))
7214 return;
7215 }
7216
7217
7218
7219
7220
7224 return;
7225 }
7226
7227 if (DefaultConst == FalseConst) {
7228
7230 ++NumTableCmpReuses;
7231 } else {
7232
7233 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7234 RangeCmp, ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp",
7237 ++NumTableCmpReuses;
7238 }
7239}
7240
7241
7242
7243
7247 bool ConvertSwitchToLookupTable) {
7248 assert(SI->getNumCases() > 1 && "Degenerate switch?");
7249
7252
7253
7254
7255
7256
7257
7258
7259
7260
7261
7262 if (SI->getNumCases() < 3)
7263 return false;
7264
7265
7266
7267 assert(->cases().empty());
7269 ConstantInt *MinCaseVal = CI->getCaseValue();
7270 ConstantInt *MaxCaseVal = CI->getCaseValue();
7271
7273
7276
7280
7282 ConstantInt *CaseVal = CI->getCaseValue();
7284 MinCaseVal = CaseVal;
7286 MaxCaseVal = CaseVal;
7287
7288
7291 if ((SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
7293 return false;
7294
7295
7296
7297 for (const auto &I : Results) {
7301 if (Inserted)
7303 It->second.push_back(std::make_pair(CaseVal, Value));
7305 }
7306 }
7307
7308
7309
7311 bool HasDefaultResults =
7313 DefaultResultsList, DL, TTI);
7314 for (const auto &I : DefaultResultsList) {
7317 DefaultResults[PHI] = Result;
7318 }
7319
7321 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes, DL, TTI);
7324 if (UseSwitchConditionAsTableIndex) {
7326 TableIndexOffset = ConstantInt::get(MaxCaseVal->getIntegerType(), 0);
7327 } else {
7328 TableSize =
7329 (MaxCaseVal->getValue() - MinCaseVal->getValue()).getLimitedValue() + 1;
7330
7331 TableIndexOffset = MinCaseVal;
7332 }
7333
7334
7335
7336
7337 uint64_t NumResults = ResultLists[PHIs[0]].size();
7338 bool DefaultIsReachable = ->defaultDestUnreachable();
7339
7340 bool TableHasHoles = (NumResults < TableSize);
7341
7342
7343
7344
7345 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7346
7347
7348
7349
7350
7351
7352
7353 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7354 if (NeedMask) {
7355
7356 if (SI->getNumCases() < 4)
7357 return false;
7358 if (.fitsInLegalInteger(TableSize))
7359 return false;
7360 }
7361
7363 return false;
7364
7365
7366 Value *TableIndex;
7367 if (UseSwitchConditionAsTableIndex) {
7368 TableIndex = SI->getCondition();
7369 if (HasDefaultResults) {
7370
7371
7372
7375
7376
7377
7378
7381 all_of(ResultTypes, [&](const auto &ResultType) {
7382 return SwitchReplacement::wouldFitInRegister(DL, UpperBound,
7383 ResultType);
7384 })) {
7385
7386
7387 TableSize = std::max(UpperBound, TableSize);
7388
7389
7390 DefaultIsReachable = false;
7391 }
7392 }
7393 }
7394
7395
7398 const auto &ResultList = ResultLists[PHI];
7399
7400 Type *ResultType = ResultList.begin()->second->getType();
7401
7405 SwitchReplacement Replacement(*Fn->getParent(), TableSize, TableIndexOffset,
7407 PhiToReplacementMap.insert({PHI, Replacement});
7408 }
7409
7410 bool AnyLookupTables = any_of(
7411 PhiToReplacementMap, [](auto &KV) { return KV.second.isLookupTable(); });
7412 bool AnyBitMaps = any_of(PhiToReplacementMap,
7413 [](auto &KV) { return KV.second.isBitMap(); });
7414
7415
7416
7417
7418
7419
7420
7421 if (AnyLookupTables &&
7422 (.shouldBuildLookupTables() ||
7424 return false;
7425
7426
7427
7428 if (!ConvertSwitchToLookupTable &&
7429 (AnyLookupTables || AnyBitMaps || NeedMask))
7430 return false;
7431
7432 Builder.SetInsertPoint(SI);
7433
7434
7435 if (!UseSwitchConditionAsTableIndex) {
7436
7437
7438 bool MayWrap = true;
7439 if (!DefaultIsReachable) {
7442 (void)Res;
7443 }
7444 TableIndex = Builder.CreateSub(SI->getCondition(), TableIndexOffset,
7445 "switch.tableidx", false,
7446 !MayWrap);
7447 }
7448
7449 std::vectorDominatorTree::UpdateType Updates;
7450
7451
7452
7454 uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
7455 assert(MaxTableSize >= TableSize &&
7456 "It is impossible for a switch to have more entries than the max "
7457 "representable value of its input integer type's size.");
7458
7459
7462 Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest);
7463
7464 BranchInst *RangeCheckBranch = nullptr;
7466
7467 Builder.SetInsertPoint(SI);
7468 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7469 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7470 Builder.CreateBr(LookupBB);
7471 if (DTU)
7473
7474
7475 } else {
7476 Value *Cmp = Builder.CreateICmpULT(
7477 TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize));
7478 RangeCheckBranch =
7479 Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7480 CondBranch = RangeCheckBranch;
7481 if (DTU)
7483 }
7484
7485
7486 Builder.SetInsertPoint(LookupBB);
7487
7488 if (NeedMask) {
7489
7490
7492 MaskBB->setName("switch.hole_check");
7494 CommonDest->getParent(), CommonDest);
7495
7496
7497
7499 APInt MaskInt(TableSizePowOf2, 0);
7500 APInt One(TableSizePowOf2, 1);
7501
7502 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7503 for (const auto &Result : ResultList) {
7504 uint64_t Idx = (Result.first->getValue() - TableIndexOffset->getValue())
7505 .getLimitedValue();
7506 MaskInt |= One << Idx;
7507 }
7508 ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt);
7509
7510
7511
7512
7514 Value *MaskIndex =
7515 Builder.CreateZExtOrTrunc(TableIndex, MapTy, "switch.maskindex");
7516 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex, "switch.shifted");
7517 Value *LoBit = Builder.CreateTrunc(
7519 CondBranch = Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7520 if (DTU) {
7523 }
7524 Builder.SetInsertPoint(LookupBB);
7526 }
7527
7528 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7529
7530
7531 SI->getDefaultDest()->removePredecessor(BB,
7532 true);
7533 if (DTU)
7535 }
7536
7538 const ResultListTy &ResultList = ResultLists[PHI];
7539 auto Replacement = PhiToReplacementMap.at(PHI);
7540 auto *Result = Replacement.replaceSwitch(TableIndex, Builder, DL, Fn);
7541
7542
7543 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7545
7546 for (auto *User : PHI->users()) {
7548 Replacement.getDefaultValue(), ResultList);
7549 }
7550 }
7551
7552 PHI->addIncoming(Result, LookupBB);
7553 }
7554
7555 Builder.CreateBr(CommonDest);
7556 if (DTU)
7558
7562 uint64_t ToLookupWeight = 0;
7563 uint64_t ToDefaultWeight = 0;
7564
7565
7567 for (unsigned I = 0, E = SI->getNumSuccessors(); I < E; ++I) {
7569
7570 if (Succ == SI->getDefaultDest()) {
7571 if (HasBranchWeights)
7572 ToDefaultWeight += BranchWeights[I];
7573 continue;
7574 }
7576 if (DTU && RemovedSuccessors.insert(Succ).second)
7578 if (HasBranchWeights)
7579 ToLookupWeight += BranchWeights[I];
7580 }
7581 SI->eraseFromParent();
7582 if (HasBranchWeights)
7584 false);
7585 if (DTU)
7587
7588 if (NeedMask)
7589 ++NumLookupTablesHoles;
7590 return true;
7591}
7592
7593
7594
7595
7596
7597
7598
7599
7600
7605 if (CondTy->getIntegerBitWidth() > 64 ||
7606 .fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7607 return false;
7608
7609
7610 if (SI->getNumCases() < 4)
7611 return false;
7612
7613
7614
7615
7616
7618 for (const auto &C : SI->cases())
7619 Values.push_back(C.getCaseValue()->getValue().getSExtValue());
7621
7622
7624 return false;
7625
7626
7627 int64_t Base = Values[0];
7628 for (auto &V : Values)
7630
7631
7632
7633
7634
7635
7636
7637
7638
7639
7640
7641 unsigned Shift = 64;
7642 for (auto &V : Values)
7645 if (Shift > 0)
7646 for (auto &V : Values)
7647 V = (int64_t)((uint64_t)V >> Shift);
7648
7650
7651 return false;
7652
7653
7654
7655
7656
7657
7658
7659
7660
7661
7662
7664 Builder.SetInsertPoint(SI);
7666 Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
7667 Value *Rot = Builder.CreateIntrinsic(
7668 Ty, Intrinsic::fshl,
7669 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7670 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7671
7672 for (auto Case : SI->cases()) {
7673 auto *Orig = Case.getCaseValue();
7674 auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base, true);
7676 }
7677 return true;
7678}
7679
7680
7681
7682
7683
7684
7685
7686
7687
7688
7689
7690
7691
7692
7693
7694
7695
7696
7697
7698
7699
7700
7701
7702
7703
7704
7705
7709
7711 return false;
7712
7716
7717
7718
7719 for (auto I = SI->case_begin(), E = SI->case_end(); I != E;) {
7720 if (->getCaseValue()->getValue().ugt(Constant->getValue())) {
7721 ++I;
7722 continue;
7723 }
7724 BasicBlock *DeadCaseBB = I->getCaseSuccessor();
7729 }
7730
7731 auto Case = SI->findCaseValue(Constant);
7732
7733
7734
7735
7736 if (->defaultDestUnreachable() || Case == SI->case_default()) {
7737 if (DTU)
7739 return !Updates.empty();
7740 }
7741
7742 BasicBlock *Unreachable = SI->getDefaultDest();
7746
7748
7749 if (DTU)
7751
7752 return true;
7753}
7754
7755
7756
7757
7758
7759
7760
7761
7762
7763
7764
7769 Value *Condition = SI->getCondition();
7772
7773 if (CondTy->getIntegerBitWidth() > 64 ||
7774 .fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7775 return false;
7776
7777
7782 return false;
7783
7784
7785
7786 if (SI->getNumCases() < 4)
7787 return false;
7788
7789
7791 for (const auto &Case : SI->cases()) {
7792 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7795 else
7796 return false;
7797 }
7798
7799
7803
7804 return false;
7805
7806 Builder.SetInsertPoint(SI);
7807
7808 if (->defaultDestUnreachable()) {
7809
7810
7811 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7812 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7813
7814 auto *OrigBB = SI->getParent();
7815 auto *DefaultCaseBB = SI->getDefaultDest();
7817 auto It = OrigBB->getTerminator()->getIterator();
7819 auto HasWeights =
7822 if (HasWeights && any_of(Weights, [](const auto &V) { return V != 0; })) {
7823
7824
7825
7826
7830 NewWeights[1] = Weights[0] / 2;
7831 NewWeights[0] = OrigDenominator - NewWeights[1];
7833
7834
7835
7836
7837
7838
7839
7840
7841
7842
7843 Weights[0] = NewWeights[1];
7844 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7846 W = NewWeights[0] * static_cast<double>(W) / CasesDenominator;
7847
7849 }
7850
7852 It->eraseFromParent();
7853
7855 if (DTU)
7857 }
7858
7859
7860 for (auto &Case : SI->cases()) {
7861 auto *OrigValue = Case.getCaseValue();
7862 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7863 OrigValue->getValue().countr_zero()));
7864 }
7865
7866
7867 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7869
7870 SI->setCondition(ConditionTrailingZeros);
7871
7872 return true;
7873}
7874
7875
7876
7880 if (!Cmp || !Cmp->hasOneUse())
7881 return false;
7882
7885 if (!HasWeights)
7886 Weights.resize(4);
7887
7888
7889 int64_t Res;
7891 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7893
7894 if (SI->getNumCases() == 2) {
7895
7898 Missing.insert(0);
7899 Missing.insert(-1);
7900
7901 Succ = SI->getDefaultDest();
7902 SuccWeight = Weights[0];
7904 for (auto &Case : SI->cases()) {
7905 std::optional<int64_t> Val =
7906 Case.getCaseValue()->getValue().trySExtValue();
7907 if (!Val)
7908 return false;
7909 if (!Missing.erase(*Val))
7910 return false;
7912 return false;
7913 OtherSucc = Case.getCaseSuccessor();
7914 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7915 }
7916
7917 assert(Missing.size() == 1 && "Should have one case left");
7918 Res = *Missing.begin();
7919 } else if (SI->getNumCases() == 3 && SI->defaultDestUnreachable()) {
7920
7921 Unreachable = SI->getDefaultDest();
7923 for (auto &Case : SI->cases()) {
7924 BasicBlock *NewSucc = Case.getCaseSuccessor();
7925 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7928 OtherSuccWeight += Weight;
7929 } else if (!Succ) {
7930 Succ = NewSucc;
7931 SuccWeight = Weight;
7932 } else if (Succ == NewSucc) {
7934 std::swap(SuccWeight, OtherSuccWeight);
7935 } else
7936 return false;
7937 }
7938 for (auto &Case : SI->cases()) {
7939 std::optional<int64_t> Val =
7940 Case.getCaseValue()->getValue().trySExtValue();
7941 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7942 return false;
7943 if (Case.getCaseSuccessor() == Succ) {
7944 Res = *Val;
7945 break;
7946 }
7947 }
7948 } else {
7949 return false;
7950 }
7951
7952
7954 switch (Res) {
7955 case 1:
7957 break;
7958 case 0:
7960 break;
7961 case -1:
7963 break;
7964 }
7965 if (Cmp->isSigned())
7967
7968 MDNode *NewWeights = nullptr;
7969 if (HasWeights)
7970 NewWeights = MDBuilder(SI->getContext())
7972
7974 Builder.SetInsertPoint(SI->getIterator());
7975 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7976 Builder.CreateCondBr(ICmp, Succ, OtherSucc, NewWeights,
7977 SI->getMetadata(LLVMContext::MD_unpredictable));
7978 OtherSucc->removePredecessor(BB);
7979 if (Unreachable)
7981 SI->eraseFromParent();
7982 Cmp->eraseFromParent();
7983 if (DTU && Unreachable)
7985 return true;
7986}
7987
7988
7989
7990
7991
7992
7993
7994
7995
8000
8014 "Only supporting unconditional branches for now");
8016 "Expected unconditional branches to have one successor");
8017 assert(Succ->size() == 1 && "Expected just a single branch in the BB");
8018
8019
8020
8021
8022
8023
8024
8025
8026
8031
8033 }
8038 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
8039 return LHS == RHS;
8040
8043
8044
8045
8046
8047
8048
8049
8050
8054 "Only supporting unconditional branches for now");
8055 if (ABI->getSuccessor(0) != BBI->getSuccessor(0))
8056 return false;
8057
8058
8059 BasicBlock *Succ = ABI->getSuccessor(0);
8061 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8062 if (PredIVs[A] != PredIVs[B])
8063 return false;
8064 }
8065
8066 return true;
8067 }
8068};
8069
8070bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8072
8073
8074
8075
8076
8082 Cases.reserve(SI->getNumSuccessors());
8083
8084 for (unsigned I = 0; I < SI->getNumSuccessors(); ++I) {
8086
8087
8088
8089 if (BB->size() != 1)
8090 continue;
8091
8092
8093
8094
8097 continue;
8098
8099 if (!Seen.insert(BB).second) {
8100 auto It = BBToSuccessorIndexes.find(BB);
8101 if (It != BBToSuccessorIndexes.end())
8102 It->second.emplace_back(I);
8103 continue;
8104 }
8105
8106
8107
8109 continue;
8110
8111
8112 for (BasicBlock *Succ : BI->successors())
8114
8115
8116 Cases.emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
8117 BBToSuccessorIndexes[BB].emplace_back(I);
8118 }
8119
8120
8121
8123 for (PHINode *Phi : Phis) {
8124 auto &IVs =
8125 PhiPredIVs.try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8126 for (auto &IV : Phi->incoming_values())
8127 IVs.insert({Phi->getIncomingBlock(IV), IV.get()});
8128 }
8129
8130
8131
8132
8133
8134
8135
8136
8137
8138 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
8140
8143 bool MadeChange = false;
8144 for (auto &SSW : Cases) {
8145
8146
8147 const auto [It, Inserted] = ReplaceWith.insert(&SSW);
8148 if (!Inserted) {
8149
8150
8151 Updates.push_back({DominatorTree::Delete, SI->getParent(), SSW.Dest});
8152 const auto &Successors = BBToSuccessorIndexes.at(SSW.Dest);
8153 for (unsigned Idx : Successors)
8154 SI->setSuccessor(Idx, (*It)->Dest);
8155 MadeChange = true;
8156 }
8157 }
8158
8159 if (DTU)
8161
8162 return MadeChange;
8163}
8164
8165bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
8167
8168 if (isValueEqualityComparison(SI)) {
8169
8170
8172 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8173 return requestResimplify();
8174
8177 if (simplifySwitchOnSelect(SI, Select))
8178 return requestResimplify();
8179
8180
8181
8183 if (foldValueComparisonIntoPredecessors(SI, Builder))
8184 return requestResimplify();
8185 }
8186
8187
8188
8189
8190 if (Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8191 return requestResimplify();
8192
8193
8195 return requestResimplify();
8196
8198 return requestResimplify();
8199
8201 return requestResimplify();
8202
8204 return requestResimplify();
8205
8206
8207
8208
8209 if (Options.ConvertSwitchToArithmetic || Options.ConvertSwitchToLookupTable)
8211 Options.ConvertSwitchToLookupTable))
8212 return requestResimplify();
8213
8215 return requestResimplify();
8216
8218 return requestResimplify();
8219
8221 hoistCommonCodeFromSuccessors(SI, .HoistCommonInsts))
8222 return requestResimplify();
8223
8224 if (simplifyDuplicateSwitchArms(SI, DTU))
8225 return requestResimplify();
8226
8228 return requestResimplify();
8229
8230 return false;
8231}
8232
8233bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8236 SmallVector<uint32_t> BranchWeights;
8239
8240 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8241 if (HasBranchWeights)
8244
8245
8246 SmallPtrSet<Value *, 8> Succs;
8247 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8252 RemovedSuccs.insert(Dest);
8255 --I;
8256 --E;
8258 }
8259 }
8260
8261 if (DTU) {
8262 std::vectorDominatorTree::UpdateType Updates;
8263 Updates.reserve(RemovedSuccs.size());
8264 for (auto *RemovedSucc : RemovedSuccs)
8265 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8267 }
8268
8270
8273 return true;
8274 }
8275
8277
8280 return true;
8281 }
8282 if (HasBranchWeights) {
8287 }
8289 if (simplifyIndirectBrOnSelect(IBI, SI))
8290 return requestResimplify();
8291 }
8293}
8294
8295
8296
8297
8298
8299
8300
8301
8302
8303
8304
8305
8306
8307
8308
8309
8310
8311
8312
8313
8314
8315
8320
8321
8323 return false;
8324
8326 if (BB == OtherPred)
8327 continue;
8331 continue;
8332 ++I;
8335 continue;
8336
8337 std::vectorDominatorTree::UpdateType Updates;
8338
8339
8340
8342 for (BasicBlock *Pred : UniquePreds) {
8344 assert(II->getNormalDest() != BB && II->getUnwindDest() == BB &&
8345 "unexpected successor");
8346 II->setUnwindDest(OtherPred);
8347 if (DTU) {
8350 }
8351 }
8352
8354 for (BasicBlock *Succ : UniqueSuccs) {
8356 if (DTU)
8358 }
8359
8361 Builder.CreateUnreachable();
8363 if (DTU)
8365 return true;
8366 }
8367 return false;
8368}
8369
8370bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder) {
8371 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
8372 : simplifyCondBranch(Branch, Builder);
8373}
8374
8375bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
8379
8380
8381
8382
8383
8384
8385
8386
8387 bool NeedCanonicalLoop =
8388 Options.NeedCanonicalLoop &&
8394 return true;
8395
8396
8397
8400 ++I;
8401 if (I->isTerminator() &&
8402 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8403 return true;
8405 tryToSimplifyUncondBranchWithICmpSelectInIt(ICI, cast(I),
8406 Builder))
8407 return true;
8408 }
8409 }
8410
8411
8412
8414 ++I;
8416 return true;
8417 }
8418
8419
8420
8421
8422
8423 if (Options.SpeculateBlocks &&
8425 Options.BonusInstThreshold))
8426 return requestResimplify();
8427 return false;
8428}
8429
8433 BasicBlock *PPred = P->getSinglePredecessor();
8434 if (!PPred || (PredPred && PredPred != PPred))
8435 return nullptr;
8436 PredPred = PPred;
8437 }
8438 return PredPred;
8439}
8440
8441
8442
8443
8444
8445
8446
8447
8448
8449
8450
8451
8452
8453
8454
8455
8456
8457
8458
8459
8460
8466 if (Succ == BB)
8467 return false;
8469 return false;
8471 if (!SuccBI || !SuccBI->isConditional())
8472 return false;
8473 BasicBlock *Succ1 = SuccBI->getSuccessor(0);
8474 BasicBlock *Succ2 = SuccBI->getSuccessor(1);
8475 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8477 };
8479 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8480 return false;
8481
8485 return false;
8486
8496 if (DTU) {
8502
8504 }
8505 bool HasWeight = false;
8506 uint64_t BBTWeight, BBFWeight;
8508 HasWeight = true;
8509 else
8510 BBTWeight = BBFWeight = 1;
8511 uint64_t BB1TWeight, BB1FWeight;
8513 HasWeight = true;
8514 else
8515 BB1TWeight = BB1FWeight = 1;
8516 uint64_t BB2TWeight, BB2FWeight;
8518 HasWeight = true;
8519 else
8520 BB2TWeight = BB2FWeight = 1;
8521 if (HasWeight) {
8522 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8523 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8525 true);
8526 }
8527 return true;
8528}
8529
8530bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
8534 "Tautological conditional branch should have been eliminated already.");
8535
8537 if (.SimplifyCondBranch ||
8539 return false;
8540
8541
8542 if (isValueEqualityComparison(BI)) {
8543
8544
8545
8547 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8548 return requestResimplify();
8549
8550
8551
8553 if (&*I == BI) {
8554 if (foldValueComparisonIntoPredecessors(BI, Builder))
8555 return requestResimplify();
8557 ++I;
8558 if (&*I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8559 return requestResimplify();
8560 }
8561 }
8562
8563
8564 if (simplifyBranchOnICmpChain(BI, Builder, DL))
8565 return true;
8566
8567
8568
8570 if (Imp) {
8571
8577 return requestResimplify();
8578 }
8579
8580
8581
8582
8583 if (Options.SpeculateBlocks &&
8585 Options.BonusInstThreshold))
8586 return requestResimplify();
8587
8588
8589
8590
8591
8595 hoistCommonCodeFromSuccessors(BI, .HoistCommonInsts))
8596 return requestResimplify();
8597
8598 if (BI && Options.HoistLoadsStoresWithCondFaulting &&
8600 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8601 auto CanSpeculateConditionalLoadsStores = [&]() {
8603 for (Instruction &I : *Succ) {
8604 if (I.isTerminator()) {
8605 if (I.getNumSuccessors() > 1)
8606 return false;
8607 continue;
8609 SpeculatedConditionalLoadsStores.size() ==
8611 return false;
8612 }
8613 SpeculatedConditionalLoadsStores.push_back(&I);
8614 }
8615 }
8616 return !SpeculatedConditionalLoadsStores.empty();
8617 };
8618
8619 if (CanSpeculateConditionalLoadsStores()) {
8621 std::nullopt, nullptr);
8622 return requestResimplify();
8623 }
8624 }
8625 } else {
8626
8627
8631 if (speculativelyExecuteBB(BI, BI->getSuccessor(0)))
8632 return requestResimplify();
8633 }
8635
8636
8640 if (speculativelyExecuteBB(BI, BI->getSuccessor(1)))
8641 return requestResimplify();
8642 }
8643
8644
8645
8646
8647 if (foldCondBranchOnValueKnownInPredecessor(BI))
8648 return requestResimplify();
8649
8650
8653 if (PBI != BI && PBI->isConditional())
8655 return requestResimplify();
8656
8657
8661 if (PBI != BI && PBI->isConditional())
8663 return requestResimplify();
8664
8665
8667 return requestResimplify();
8668
8669 return false;
8670}
8671
8672
8674 assert(V->getType() == I->getType() && "Mismatched types");
8676 if ()
8677 return false;
8678
8679 if (I->use_empty())
8680 return false;
8681
8683
8684
8685 auto FindUse = llvm::find_if(I->uses(), [](auto &U) {
8686 auto *Use = cast(U.getUser());
8687
8688 switch (Use->getOpcode()) {
8689 default:
8690 return false;
8691 case Instruction::GetElementPtr:
8692 case Instruction::Ret:
8693 case Instruction::BitCast:
8694 case Instruction::Load:
8695 case Instruction::Store:
8696 case Instruction::Call:
8697 case Instruction::CallBr:
8698 case Instruction::Invoke:
8699 case Instruction::UDiv:
8700 case Instruction::URem:
8701
8702
8703
8704 case Instruction::SDiv:
8705 case Instruction::SRem:
8706 return true;
8707 }
8708 });
8709 if (FindUse == I->use_end())
8710 return false;
8711 auto &Use = *FindUse;
8713
8714
8715
8716 if (User->getParent() != I->getParent() || User == I ||
8718 return false;
8719
8720
8721
8722 auto InstrRange =
8723 make_range(std::next(I->getIterator()), User->getIterator());
8726 }))
8727 return false;
8728
8729
8731 if (GEP->getPointerOperand() == I) {
8732
8733
8734 if (GEP->getType()->isVectorTy())
8735 return false;
8736
8737
8738
8739
8740
8741
8742 if (->hasAllZeroIndices() &&
8743 (->isInBounds() ||
8745 GEP->getPointerAddressSpace())))
8746 PtrValueMayBeModified = true;
8748 }
8749
8750
8752 bool HasNoUndefAttr =
8753 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8754
8756 return true;
8757
8758 if (C->isNullValue() && HasNoUndefAttr &&
8759 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8760 return !PtrValueMayBeModified;
8761 }
8762 }
8763
8764
8766 if (!LI->isVolatile())
8768 LI->getPointerAddressSpace());
8769
8770
8772 if (->isVolatile())
8774 SI->getPointerAddressSpace())) &&
8775 SI->getPointerOperand() == I;
8776
8777
8779
8780 if (I == Assume->getArgOperand(0))
8781 return true;
8782 }
8783
8786 return false;
8787
8788 if (CB->getCalledOperand() == I)
8789 return true;
8790
8791 if (CB->isArgOperand(&Use)) {
8792 unsigned ArgIdx = CB->getArgOperandNo(&Use);
8793
8795 CB->paramHasNonNullAttr(ArgIdx, false))
8796 return !PtrValueMayBeModified;
8797
8799 return true;
8800 }
8801 }
8802
8804 return true;
8805 }
8806 return false;
8807}
8808
8809
8810
8815 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i)
8817 BasicBlock *Predecessor = PHI.getIncomingBlock(i);
8822
8823
8825 Builder.CreateUnreachable();
8826 else {
8827
8828
8832 Assumption = Builder.CreateAssumption(Builder.CreateNot(Cond));
8833 else
8834 Assumption = Builder.CreateAssumption(Cond);
8835 if (AC)
8839 }
8841 if (DTU)
8843 return true;
8845
8846
8849 Builder.SetInsertPoint(Unreachable);
8850
8851 Builder.CreateUnreachable();
8852 for (const auto &Case : SI->cases())
8853 if (Case.getCaseSuccessor() == BB) {
8855 Case.setSuccessor(Unreachable);
8856 }
8857 if (SI->getDefaultDest() == BB) {
8859 SI->setDefaultDest(Unreachable);
8860 }
8861
8862 if (DTU)
8866 return true;
8867 }
8868 }
8869
8870 return false;
8871}
8872
8873bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8875
8876 assert(BB && BB->getParent() && "Block not embedded in function!");
8878
8879
8880
8885 return true;
8886 }
8887
8888
8889
8891 nullptr, DTU);
8892
8893
8895
8896
8898 return requestResimplify();
8899
8900
8901
8902
8904 return true;
8905
8909
8910
8911
8912
8913
8914 return true;
8915 }
8916
8918
8919 if (Options.SpeculateBlocks &&
8921
8922
8926 Options.SpeculateUnpredictables))
8927 return true;
8928 }
8929
8933 case Instruction::Br:
8935 break;
8936 case Instruction::Resume:
8938 break;
8939 case Instruction::CleanupRet:
8941 break;
8942 case Instruction::Switch:
8944 break;
8945 case Instruction::Unreachable:
8947 break;
8948 case Instruction::IndirectBr:
8950 break;
8951 }
8952
8954}
8955
8956bool SimplifyCFGOpt::run(BasicBlock *BB) {
8958
8959
8960 do {
8961 Resimplify = false;
8962
8963
8964
8965 Changed |= simplifyOnce(BB);
8966 } while (Resimplify);
8967
8969}
8970
8974 return SimplifyCFGOpt(TTI, DTU, BB->getDataLayout(), LoopHeaders,
8976 .run(BB);
8977}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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.
static Value * getCondition(Instruction *I)
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 defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
Definition SimplifyCFG.cpp:5876
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
Definition SimplifyCFG.cpp:419
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
Definition SimplifyCFG.cpp:6316
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
Definition SimplifyCFG.cpp:4252
static bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
Definition SimplifyCFG.cpp:3150
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
Definition SimplifyCFG.cpp:3096
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
Definition SimplifyCFG.cpp:7244
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
Definition SimplifyCFG.cpp:6685
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
Definition SimplifyCFG.cpp:935
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Definition SimplifyCFG.cpp:4319
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
Definition SimplifyCFG.cpp:3964
static bool mergeCleanupPad(CleanupReturnInst *RI)
Definition SimplifyCFG.cpp:5634
static void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
Definition SimplifyCFG.cpp:1740
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
Definition SimplifyCFG.cpp:4118
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
Definition SimplifyCFG.cpp:8430
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
Definition SimplifyCFG.cpp:1167
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
Definition SimplifyCFG.cpp:1135
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
Definition SimplifyCFG.cpp:6385
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
Definition SimplifyCFG.cpp:4003
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
Definition SimplifyCFG.cpp:8673
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
Definition SimplifyCFG.cpp:1542
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
Definition SimplifyCFG.cpp:1504
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
Definition SimplifyCFG.cpp:533
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
Definition SimplifyCFG.cpp:7877
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
Definition SimplifyCFG.cpp:7107
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
Definition SimplifyCFG.cpp:3940
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
Definition SimplifyCFG.cpp:6356
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
Definition SimplifyCFG.cpp:4650
static bool tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
Definition SimplifyCFG.cpp:8316
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
Definition SimplifyCFG.cpp:1666
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
Definition SimplifyCFG.cpp:6258
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
Definition SimplifyCFG.cpp:6227
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
Definition SimplifyCFG.cpp:7765
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
Definition SimplifyCFG.cpp:5404
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
Definition SimplifyCFG.cpp:4269
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
Definition SimplifyCFG.cpp:3924
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
Definition SimplifyCFG.cpp:1580
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
Definition SimplifyCFG.cpp:7601
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Definition SimplifyCFG.cpp:4481
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
Definition SimplifyCFG.cpp:387
SkipFlags
Definition SimplifyCFG.cpp:1521
@ SkipReadMem
Definition SimplifyCFG.cpp:1522
@ SkipSideEffect
Definition SimplifyCFG.cpp:1523
@ SkipImplicitControlFlow
Definition SimplifyCFG.cpp:1524
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
Definition SimplifyCFG.cpp:363
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
Definition SimplifyCFG.cpp:6722
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
Definition SimplifyCFG.cpp:5928
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
Definition SimplifyCFG.cpp:6529
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
Definition SimplifyCFG.cpp:7081
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
Definition SimplifyCFG.cpp:2396
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
Definition SimplifyCFG.cpp:7054
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
Definition SimplifyCFG.cpp:6112
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
Definition SimplifyCFG.cpp:3466
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
Definition SimplifyCFG.cpp:3033
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
Definition SimplifyCFG.cpp:3727
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
Definition SimplifyCFG.cpp:3450
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
Definition SimplifyCFG.cpp:6474
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
Definition SimplifyCFG.cpp:7143
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
Definition SimplifyCFG.cpp:433
SmallPtrSet< BasicBlock *, 8 > BlocksSet
Definition SimplifyCFG.cpp:3447
static unsigned skippedInstrFlags(Instruction *I)
Definition SimplifyCFG.cpp:1527
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
Definition SimplifyCFG.cpp:2950
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
Definition SimplifyCFG.cpp:2185
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
Definition SimplifyCFG.cpp:847
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
Definition SimplifyCFG.cpp:929
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
Definition SimplifyCFG.cpp:2302
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
Definition SimplifyCFG.cpp:3527
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
Definition SimplifyCFG.cpp:6456
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
Definition SimplifyCFG.cpp:2797
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
Definition SimplifyCFG.cpp:1147
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
Definition SimplifyCFG.cpp:7179
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
Definition SimplifyCFG.cpp:4593
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
Definition SimplifyCFG.cpp:8461
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
Definition SimplifyCFG.cpp:6344
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
Definition SimplifyCFG.cpp:2198
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
Definition SimplifyCFG.cpp:1615
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
Definition SimplifyCFG.cpp:5517
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
Definition SimplifyCFG.cpp:8811
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
Definition SimplifyCFG.cpp:7706
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
Definition SimplifyCFG.cpp:1833
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
Definition SimplifyCFG.cpp:3505
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
Definition SimplifyCFG.cpp:455
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)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
This pass exposes codegen information to IR-level passes.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
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_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
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.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
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 splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
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.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI 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...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
ValueT & at(const_arg_type_t< KeyT > Val)
at - Return the entry for the specified key, or abort if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
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.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI 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.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
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.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to 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...
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
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.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
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.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
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.
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 reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
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 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)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
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.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
LLVM_ABI CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
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.
@ TCC_Free
Expected to fold away in lowering.
@ TCC_Basic
The cost of a typical 'add' instruction.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
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.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
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.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
FunctionAddr VTableAddr Value
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.
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.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI 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...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
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.
auto successors(const MachineBasicBlock *BB)
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI 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.
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...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
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)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ 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 void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI 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...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
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 canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
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.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
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
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
Definition SimplifyCFG.cpp:8971
auto pred_begin(const MachineBasicBlock *BB)
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.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
LLVM_ABI bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
Definition SimplifyCFG.cpp:4127
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 ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
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.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition SimplifyCFG.cpp:5866
BasicBlock * OtherDest
Definition SimplifyCFG.cpp:5870
ConstantInt * Min
Definition SimplifyCFG.cpp:5867
BasicBlock * Dest
Definition SimplifyCFG.cpp:5869
SmallVectorImpl< ConstantInt * > * Cases
Definition SimplifyCFG.cpp:5871
ConstantInt * Max
Definition SimplifyCFG.cpp:5868
SmallVectorImpl< ConstantInt * > * OtherCases
Definition SimplifyCFG.cpp:5872
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
Definition SimplifyCFG.cpp:7996
BasicBlock * Dest
Definition SimplifyCFG.cpp:7997
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
Definition SimplifyCFG.cpp:7998
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
Definition SimplifyCFG.cpp:8002
static const SwitchSuccWrapper * getTombstoneKey()
Definition SimplifyCFG.cpp:8006
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
Definition SimplifyCFG.cpp:8010
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
Definition SimplifyCFG.cpp:8034
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.