81#ifdef EXPENSIVE_CHECKS
87#define DEBUG_TYPE "dfa-jump-threading"
89STATISTIC(NumTransforms,
"Number of transformations done");
91STATISTIC(NumPaths,
"Number of individual paths threaded");
96 cl::desc(
"View the CFG before DFA Jump Threading"),
100 "dfa-early-exit-heuristic",
101 cl::desc(
"Exit early if an unpredictable value come from the same loop"),
105 "dfa-max-path-length",
106 cl::desc(
"Max number of blocks searched to find a threading path"),
110 "dfa-max-num-visited-paths",
112 "Max number of blocks visited while enumerating paths around a switch"),
117 cl::desc(
"Max number of paths enumerated around a switch"),
122 cl::desc(
"Maximum cost accepted for the transformation"),
126 "dfa-max-cloned-rate",
128 "Maximum cloned instructions rate accepted for the transformation"),
133 cl::desc(
"Maximum unduplicated blocks with outer uses "
134 "accepted for the transformation"),
142class SelectInstToUnfold {
149 SelectInst *getInst() {
return SI; }
150 PHINode *getUse() {
return SIUse; }
152 explicit operator bool()
const {
return SI && SIUse; }
155class DFAJumpThreading {
157 DFAJumpThreading(AssumptionCache *AC, DomTreeUpdater *DTU, LoopInfo *LI,
158 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE)
159 : AC(AC), DTU(DTU), LI(LI), TTI(TTI), ORE(ORE) {}
161 bool run(Function &
F);
169 while (!
Stack.empty()) {
170 SelectInstToUnfold SIToUnfold =
Stack.pop_back_val();
172 std::vector<SelectInstToUnfold> NewSIsToUnfold;
173 std::vector<BasicBlock *> NewBBs;
174 unfold(DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);
181 static void unfold(DomTreeUpdater *DTU, LoopInfo *LI,
182 SelectInstToUnfold SIToUnfold,
183 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
184 std::vector<BasicBlock *> *NewBBs);
189 TargetTransformInfo *TTI;
190 OptimizationRemarkEmitter *ORE;
202 SelectInstToUnfold SIToUnfold,
203 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
204 std::vector<BasicBlock *> *NewBBs) {
205 SelectInst *
SI = SIToUnfold.getInst();
206 PHINode *SIUse = SIToUnfold.getUse();
210 BranchInst *StartBlockTerm =
218 SI->getContext(), Twine(
SI->getName(),
".si.unfold.false"),
220 NewBBs->push_back(NewBlock);
222 DTU->
applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});
229 Value *SIOp1 =
SI->getTrueValue();
230 Value *SIOp2 =
SI->getFalseValue();
233 Twine(SIOp2->
getName(),
".si.unfold.phi"),
238 for (PHINode &Phi : EndBlock->
phis()) {
241 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlock);
250 Twine(
SI->getName(),
".si.unfold.phi"),
253 if (Pred != StartBlock && Pred != NewBlock)
264 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));
266 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));
273 BI->setMetadata(LLVMContext::MD_prof,
274 SI->getMetadata(LLVMContext::MD_prof));
275 DTU->
applyUpdates({{DominatorTree::Insert, StartBlock, NewBlock}});
279 SI->getContext(), Twine(
SI->getName(),
".si.unfold.true"),
282 SI->getContext(), Twine(
SI->getName(),
".si.unfold.false"),
285 NewBBs->push_back(NewBlockT);
286 NewBBs->push_back(NewBlockF);
311 BI->setMetadata(LLVMContext::MD_prof,
312 SI->getMetadata(LLVMContext::MD_prof));
313 DTU->
applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},
314 {DominatorTree::Insert, NewBlockT, EndBlock},
315 {DominatorTree::Insert, NewBlockF, EndBlock}});
330 NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));
332 NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));
339 for (PHINode &Phi : EndBlock->
phis()) {
342 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlockT);
343 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlockF);
344 Phi.removeIncomingValue(StartBlock);
349 unsigned SuccNum = StartBlockTerm->
getSuccessor(1) == EndBlock ? 1 : 0;
351 DTU->
applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},
352 {DominatorTree::Insert, StartBlock, NewBlockT}});
357 for (BasicBlock *NewBB : *NewBBs)
358 L->addBasicBlockToLoop(NewBB, *LI);
362 assert(
SI->use_empty() &&
"Select must be dead now");
363 SI->eraseFromParent();
390 OS <<
"< " <<
llvm::join(BBNames,
", ") <<
" >";
399struct ThreadingPath {
401 APInt getExitValue()
const {
return ExitVal; }
402 void setExitValue(
const ConstantInt *V) {
403 ExitVal =
V->getValue();
406 void setExitValue(
const APInt &V) {
410 bool isExitValueSet()
const {
return IsExitValSet; }
413 const BasicBlock *getDeterminatorBB()
const {
return DBB; }
414 void setDeterminator(
const BasicBlock *BB) { DBB = BB; }
417 const PathType &getPath()
const {
return Path; }
418 void setPath(
const PathType &NewPath) { Path = NewPath; }
419 void push_back(BasicBlock *BB) { Path.push_back(BB); }
420 void push_front(BasicBlock *BB) { Path.push_front(BB); }
421 void appendExcludingFirst(
const PathType &OtherPath) {
425 void print(raw_ostream &OS)
const {
433 bool IsExitValSet =
false;
437inline raw_ostream &
operator<<(raw_ostream &OS,
const ThreadingPath &TPath) {
444 MainSwitch(SwitchInst *SI, LoopInfo *LI, OptimizationRemarkEmitter *ORE)
450 return OptimizationRemarkMissed(
DEBUG_TYPE,
"SwitchNotPredictable", SI)
451 <<
"Switch instruction is not predictable.";
456 virtual ~MainSwitch() =
default;
458 SwitchInst *getInstr()
const {
return Instr; }
469 std::deque<std::pair<Value *, BasicBlock *>> Q;
470 SmallPtrSet<Value *, 16> SeenValues;
473 Value *SICond =
SI->getCondition();
483 addToQueue(SICond,
nullptr, Q, SeenValues);
486 Value *Current = Q.front().first;
487 BasicBlock *CurrentIncomingBB = Q.front().second;
491 for (BasicBlock *IncomingBB :
Phi->blocks()) {
492 Value *Incoming =
Phi->getIncomingValueForBlock(IncomingBB);
493 addToQueue(Incoming, IncomingBB, Q, SeenValues);
497 if (!isValidSelectInst(SelI))
499 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);
500 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);
503 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
521 <<
"\tExiting early due to unpredictability heuristic.\n");
532 void addToQueue(
Value *Val, BasicBlock *BB,
533 std::deque<std::pair<Value *, BasicBlock *>> &Q,
534 SmallPtrSet<Value *, 16> &SeenValues) {
535 if (SeenValues.
insert(Val).second)
536 Q.push_back({Val, BB});
539 bool isValidSelectInst(SelectInst *SI) {
540 if (!
SI->hasOneUse())
565 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
566 SelectInst *PrevSI = SIToUnfold.getInst();
576 SwitchInst *Instr =
nullptr;
580struct AllSwitchPaths {
581 AllSwitchPaths(
const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE,
582 LoopInfo *LI, Loop *L)
583 : Switch(MSwitch->getInstr()), SwitchBlock(Switch->
getParent()), ORE(ORE),
584 LI(LI), SwitchOuterLoop(
L) {}
586 std::vector<ThreadingPath> &getThreadingPaths() {
return TPaths; }
587 unsigned getNumThreadingPaths() {
return TPaths.size(); }
588 SwitchInst *getSwitchInst() {
return Switch; }
589 BasicBlock *getSwitchBlock() {
return SwitchBlock; }
599 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
600 std::vector<ThreadingPath> getPathsFromStateDefMap(StateDefMap &StateDef,
603 unsigned PathsLimit) {
604 std::vector<ThreadingPath> Res;
605 auto *PhiBB =
Phi->getParent();
609 for (
auto *IncomingBB :
Phi->blocks()) {
610 if (Res.size() >= PathsLimit)
612 if (!UniqueBlocks.
insert(IncomingBB).second)
614 if (!SwitchOuterLoop->
contains(IncomingBB))
617 Value *IncomingValue =
Phi->getIncomingValueForBlock(IncomingBB);
621 if (PhiBB == SwitchBlock &&
624 ThreadingPath NewPath;
625 NewPath.setDeterminator(PhiBB);
626 NewPath.setExitValue(
C);
628 if (IncomingBB != SwitchBlock)
629 NewPath.push_back(IncomingBB);
630 NewPath.push_back(PhiBB);
631 Res.push_back(NewPath);
635 if (VB.
contains(IncomingBB) || IncomingBB == SwitchBlock)
641 auto *IncomingPhiDefBB = IncomingPhi->getParent();
642 if (!StateDef.contains(IncomingPhiDefBB))
646 if (IncomingPhiDefBB == IncomingBB) {
647 assert(PathsLimit > Res.size());
648 std::vector<ThreadingPath> PredPaths = getPathsFromStateDefMap(
649 StateDef, IncomingPhi, VB, PathsLimit - Res.size());
650 for (ThreadingPath &Path : PredPaths) {
651 Path.push_back(PhiBB);
652 Res.push_back(std::move(Path));
662 assert(PathsLimit > Res.size());
663 auto InterPathLimit = PathsLimit - Res.size();
664 IntermediatePaths = paths(IncomingPhiDefBB, IncomingBB, VB,
666 if (IntermediatePaths.empty())
669 assert(InterPathLimit >= IntermediatePaths.size());
670 auto PredPathLimit = InterPathLimit / IntermediatePaths.size();
671 std::vector<ThreadingPath> PredPaths =
672 getPathsFromStateDefMap(StateDef, IncomingPhi, VB, PredPathLimit);
673 for (
const ThreadingPath &Path : PredPaths) {
674 for (
const PathType &IPath : IntermediatePaths) {
675 ThreadingPath NewPath(Path);
676 NewPath.appendExcludingFirst(IPath);
677 NewPath.push_back(PhiBB);
678 Res.push_back(NewPath);
687 unsigned PathDepth,
unsigned PathsLimit) {
693 return OptimizationRemarkAnalysis(
DEBUG_TYPE,
"MaxPathLengthReached",
695 <<
"Exploration stopped after visiting MaxPathLength="
712 SmallPtrSet<BasicBlock *, 4> Successors;
714 if (Res.size() >= PathsLimit)
716 if (!Successors.
insert(Succ).second)
721 Res.push_back({BB, ToBB});
731 if (Succ == CurrLoop->getHeader())
737 assert(PathsLimit > Res.size());
739 paths(Succ, ToBB, Visited, PathDepth + 1, PathsLimit - Res.size());
754 StateDefMap getStateDefMap()
const {
757 assert(FirstDef &&
"The first definition must be a phi.");
760 Stack.push_back(FirstDef);
761 SmallPtrSet<Value *, 16> SeenValues;
763 while (!
Stack.empty()) {
764 PHINode *CurPhi =
Stack.pop_back_val();
767 SeenValues.
insert(CurPhi);
769 for (BasicBlock *IncomingBB : CurPhi->
blocks()) {
770 PHINode *IncomingPhi =
774 bool IsOutsideLoops = !SwitchOuterLoop->
contains(IncomingBB);
775 if (SeenValues.
contains(IncomingPhi) || IsOutsideLoops)
778 Stack.push_back(IncomingPhi);
787 StateDefMap StateDef = getStateDefMap();
788 if (StateDef.empty()) {
790 return OptimizationRemarkMissed(
DEBUG_TYPE,
"SwitchNotPredictable",
792 <<
"Switch instruction is not predictable.";
798 auto *SwitchPhiDefBB = SwitchPhi->getParent();
801 std::vector<ThreadingPath> PathsToPhiDef =
802 getPathsFromStateDefMap(StateDef, SwitchPhi, VB,
MaxNumPaths);
803 if (SwitchPhiDefBB == SwitchBlock || PathsToPhiDef.empty()) {
804 TPaths = std::move(PathsToPhiDef);
809 auto PathsLimit =
MaxNumPaths / PathsToPhiDef.size();
812 paths(SwitchPhiDefBB, SwitchBlock, VB, 1, PathsLimit);
813 if (PathsToSwitchBB.empty())
816 std::vector<ThreadingPath> TempList;
817 for (
const ThreadingPath &Path : PathsToPhiDef) {
818 for (
const PathType &PathToSw : PathsToSwitchBB) {
819 ThreadingPath PathCopy(Path);
820 PathCopy.appendExcludingFirst(PathToSw);
821 TempList.push_back(PathCopy);
824 TPaths = std::move(TempList);
829 BasicBlock *getNextCaseSuccessor(
const APInt &NextState) {
831 if (CaseValToDest.empty()) {
832 for (
auto Case : Switch->
cases()) {
833 APInt CaseVal = Case.getCaseValue()->getValue();
834 CaseValToDest[CaseVal] = Case.getCaseSuccessor();
838 auto SuccIt = CaseValToDest.find(NextState);
846 SmallDenseMap<BasicBlock *, APInt> DestToState;
847 for (ThreadingPath &Path : TPaths) {
848 APInt NextState =
Path.getExitValue();
849 BasicBlock *Dest = getNextCaseSuccessor(NextState);
853 if (NextState != StateIt->second) {
854 LLVM_DEBUG(
dbgs() <<
"Next state in " << Path <<
" is equivalent to "
855 << StateIt->second <<
"\n");
856 Path.setExitValue(StateIt->second);
861 unsigned NumVisited = 0;
864 OptimizationRemarkEmitter *ORE;
865 std::vector<ThreadingPath> TPaths;
866 DenseMap<APInt, BasicBlock *> CaseValToDest;
868 Loop *SwitchOuterLoop;
872 TransformDFA(AllSwitchPaths *SwitchPaths, DomTreeUpdater *DTU,
873 AssumptionCache *AC, TargetTransformInfo *
TTI,
874 OptimizationRemarkEmitter *ORE,
875 SmallPtrSet<const Value *, 32> EphValues)
876 : SwitchPaths(SwitchPaths), DTU(DTU), AC(AC),
TTI(
TTI), ORE(ORE),
877 EphValues(EphValues) {}
880 if (isLegalAndProfitableToTransform()) {
881 createAllExitPaths();
893 bool isLegalAndProfitableToTransform() {
895 uint64_t NumClonedInst = 0;
896 SwitchInst *
Switch = SwitchPaths->getSwitchInst();
899 if (
Switch->getNumSuccessors() <= 1)
905 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
907 APInt NextState = TPath.getExitValue();
908 const BasicBlock *Determinator = TPath.getDeterminatorBB();
911 BasicBlock *BB = SwitchPaths->getSwitchBlock();
912 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
914 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
916 DuplicateMap[BB].push_back({BB, NextState});
921 if (PathBBs.front() == Determinator)
926 auto DetIt =
llvm::find(PathBBs, Determinator);
927 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
929 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
932 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
934 DuplicateMap[BB].push_back({BB, NextState});
938 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
939 <<
"non-duplicatable instructions.\n");
941 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NonDuplicatableInst",
943 <<
"Contains non-duplicatable instructions.";
949 if (
Metrics.Convergence != ConvergenceKind::None) {
950 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
951 <<
"convergent instructions.\n");
953 return OptimizationRemarkMissed(
DEBUG_TYPE,
"ConvergentInst", Switch)
954 <<
"Contains convergent instructions.";
959 if (!
Metrics.NumInsts.isValid()) {
960 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
961 <<
"instructions with invalid cost.\n");
963 return OptimizationRemarkMissed(
DEBUG_TYPE,
"ConvergentInst", Switch)
964 <<
"Contains instructions with invalid cost.";
973 uint64_t NumOrigInst = 0;
974 uint64_t NumOuterUseBlock = 0;
975 for (
auto *BB : DuplicateMap.
keys()) {
980 if (!DuplicateMap.
count(Succ) && Succ->getSinglePredecessor())
984 if (
double(NumClonedInst) /
double(NumOrigInst) >
MaxClonedRate) {
985 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, too much "
986 "instructions wll be cloned\n");
988 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NotProfitable", Switch)
989 <<
"Too much instructions will be cloned.";
999 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, too much "
1000 "blocks with outer uses\n");
1002 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NotProfitable", Switch)
1003 <<
"Too much blocks with outer uses.";
1010 unsigned JumpTableSize = 0;
1013 if (JumpTableSize == 0) {
1017 unsigned CondBranches =
1018 APInt(32,
Switch->getNumSuccessors()).ceilLogBase2();
1019 assert(CondBranches > 0 &&
1020 "The threaded switch must have multiple branches");
1021 DuplicationCost =
Metrics.NumInsts / CondBranches;
1029 DuplicationCost =
Metrics.NumInsts / JumpTableSize;
1032 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump Threading: Cost to jump thread block "
1033 << SwitchPaths->getSwitchBlock()->getName()
1034 <<
" is: " << DuplicationCost <<
"\n\n");
1037 LLVM_DEBUG(
dbgs() <<
"Not jump threading, duplication cost exceeds the "
1038 <<
"cost threshold.\n");
1040 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NotProfitable", Switch)
1041 <<
"Duplication cost exceeds the cost threshold (cost="
1042 <<
ore::NV(
"Cost", DuplicationCost)
1049 return OptimizationRemark(
DEBUG_TYPE,
"JumpThreaded", Switch)
1050 <<
"Switch statement jump-threaded.";
1057 void createAllExitPaths() {
1059 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
1060 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1064 TPath.push_front(SwitchBlock);
1071 SmallPtrSet<BasicBlock *, 16> BlocksToClean;
1074 for (
const ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1075 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, DTU);
1081 for (
const ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
1082 updateLastSuccessor(TPath, DuplicateMap, DTU);
1088 for (BasicBlock *BB : BlocksToClean)
1098 void createExitPath(
DefMap &NewDefs,
const ThreadingPath &Path,
1100 SmallPtrSet<BasicBlock *, 16> &BlocksToClean,
1101 DomTreeUpdater *DTU) {
1102 APInt NextState =
Path.getExitValue();
1107 if (PathBBs.front() == Determinator)
1108 PathBBs.pop_front();
1110 auto DetIt =
llvm::find(PathBBs, Determinator);
1113 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt);
1114 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
1116 BlocksToClean.
insert(BB);
1120 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
1122 updatePredecessor(PrevBB, BB, NextBB, DTU);
1128 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
1129 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
1130 DuplicateMap[BB].push_back({NewBB, NextState});
1131 BlocksToClean.
insert(NewBB);
1142 void updateSSA(
DefMap &NewDefs) {
1143 SSAUpdaterBulk SSAUpdate;
1144 SmallVector<Use *, 16> UsesToRename;
1146 for (
const auto &KV : NewDefs) {
1149 std::vector<Instruction *> Cloned = KV.second;
1153 for (Use &U :
I->uses()) {
1156 if (UserPN->getIncomingBlock(U) == BB)
1158 }
else if (
User->getParent() == BB) {
1167 if (UsesToRename.
empty())
1175 unsigned VarNum = SSAUpdate.
AddVariable(
I->getName(),
I->getType());
1177 for (Instruction *New : Cloned)
1180 while (!UsesToRename.
empty())
1194 static BasicBlock *getNextCaseSuccessor(SwitchInst *Switch,
1195 const APInt &NextState) {
1197 for (
auto Case :
Switch->cases()) {
1198 if (Case.getCaseValue()->getValue() == NextState) {
1199 NextCase = Case.getCaseSuccessor();
1204 NextCase =
Switch->getDefaultDest();
1212 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
1213 const APInt &NextState,
1216 DomTreeUpdater *DTU) {
1224 for (Instruction &
I : *NewBB) {
1236 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1237 updatePredecessor(PrevBB, BB, NewBB, DTU);
1238 updateDefMap(NewDefs, VMap);
1241 SmallPtrSet<BasicBlock *, 4> SuccSet;
1243 if (SuccSet.
insert(SuccBB).second)
1244 DTU->
applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1254 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
1257 std::vector<BasicBlock *> BlocksToUpdate;
1261 if (BB == SwitchPaths->getSwitchBlock()) {
1262 SwitchInst *
Switch = SwitchPaths->getSwitchInst();
1263 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1264 BlocksToUpdate.push_back(NextCase);
1265 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1267 BlocksToUpdate.push_back(ClonedSucc);
1272 BlocksToUpdate.push_back(Succ);
1277 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1279 BlocksToUpdate.push_back(ClonedSucc);
1286 for (BasicBlock *Succ : BlocksToUpdate) {
1287 for (PHINode &Phi : Succ->phis()) {
1288 Value *Incoming =
Phi.getIncomingValueForBlock(BB);
1291 Phi.addIncoming(Incoming, ClonedBB);
1294 Value *ClonedVal = VMap[Incoming];
1296 Phi.addIncoming(ClonedVal, ClonedBB);
1298 Phi.addIncoming(Incoming, ClonedBB);
1306 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
1307 BasicBlock *NewBB, DomTreeUpdater *DTU) {
1310 if (!isPredecessor(OldBB, PrevBB))
1320 DTU->
applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1321 {DominatorTree::Insert, PrevBB, NewBB}});
1330 for (
auto Entry : VMap) {
1342 NewDefsVector.
push_back({Inst, Cloned});
1346 sort(NewDefsVector, [](
const auto &
LHS,
const auto &
RHS) {
1347 if (
LHS.first ==
RHS.first)
1348 return LHS.second->comesBefore(
RHS.second);
1349 return LHS.first->comesBefore(
RHS.first);
1352 for (
const auto &KV : NewDefsVector)
1353 NewDefs[KV.first].push_back(KV.second);
1361 void updateLastSuccessor(
const ThreadingPath &TPath,
1363 DomTreeUpdater *DTU) {
1364 APInt NextState = TPath.getExitValue();
1366 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1373 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1375 std::vector<DominatorTree::UpdateType> DTUpdates;
1376 SmallPtrSet<BasicBlock *, 4> SuccSet;
1377 for (BasicBlock *Succ :
successors(LastBlock)) {
1378 if (Succ != NextCase && SuccSet.
insert(Succ).second)
1379 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1382 Switch->eraseFromParent();
1390 void cleanPhiNodes(BasicBlock *BB) {
1395 PN.eraseFromParent();
1401 for (PHINode &Phi : BB->
phis())
1402 Phi.removeIncomingValueIf([&](
unsigned Index) {
1404 return !isPredecessor(BB, IncomingBB);
1410 BasicBlock *getClonedBB(BasicBlock *BB,
const APInt &NextState,
1416 auto It =
llvm::find_if(ClonedBBs, [NextState](
const ClonedBlock &
C) {
1417 return C.State == NextState;
1419 return It != ClonedBBs.end() ? (*It).BB :
nullptr;
1423 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
1427 AllSwitchPaths *SwitchPaths;
1428 DomTreeUpdater *DTU;
1429 AssumptionCache *AC;
1430 TargetTransformInfo *
TTI;
1431 OptimizationRemarkEmitter *ORE;
1432 SmallPtrSet<const Value *, 32> EphValues;
1433 std::vector<ThreadingPath> TPaths;
1437bool DFAJumpThreading::run(Function &
F) {
1438 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump threading: " <<
F.getName() <<
"\n");
1440 if (
F.hasOptSize()) {
1441 LLVM_DEBUG(
dbgs() <<
"Skipping due to the 'minsize' attribute\n");
1449 bool MadeChanges =
false;
1450 LoopInfoBroken =
false;
1452 for (BasicBlock &BB :
F) {
1458 <<
" is a candidate\n");
1459 MainSwitch
Switch(SI, LI, ORE);
1461 if (!
Switch.getInstr()) {
1463 <<
"candidate for jump threading\n");
1468 <<
"candidate for jump threading\n");
1471 unfoldSelectInstrs(
Switch.getSelectInsts());
1472 if (!
Switch.getSelectInsts().empty())
1475 AllSwitchPaths SwitchPaths(&Switch, ORE, LI,
1479 if (SwitchPaths.getNumThreadingPaths() > 0) {
1496 SmallPtrSet<const Value *, 32> EphValues;
1497 if (ThreadableLoops.
size() > 0)
1500 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1501 TransformDFA Transform(&SwitchPaths, DTU, AC,
TTI, ORE, EphValues);
1502 if (Transform.run())
1503 MadeChanges = LoopInfoBroken =
true;
1508#ifdef EXPENSIVE_CHECKS
1514 "Failed to maintain validity of domtree!");
1529 DFAJumpThreading ThreadImpl(&AC, &DTU, &LI, &
TTI, &ORE);
1530 if (!ThreadImpl.run(
F))
1535 if (!ThreadImpl.LoopInfoBroken)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
std::deque< BasicBlock * > PathType
std::vector< PathType > PathsType
MapVector< Instruction *, std::vector< Instruction * > > DefMap
std::vector< ClonedBlock > CloneList
DenseMap< BasicBlock *, CloneList > DuplicateBlockMap
This file defines the DenseMap class.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
uint64_t IntrinsicInst * II
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
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.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
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.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI filter_iterator< BasicBlock::const_iterator, std::function< bool(constInstruction &)> >::difference_type sizeWithoutDebug() const
Return the size of the basic block ignoring debug instructions.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Analysis pass which computes a DominatorTree.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class implements a map that also provides access to all stored values in a deterministic order.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
LLVM_ABI unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
LLVM_ABI void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
LLVM_ABI void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.
LLVM_ABI void AddUse(unsigned Var, Use *U)
Record a use of the symbolic value.
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getTrueValue() const
bool erase(PtrType Ptr)
Remove pointer from the set.
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.
void reserve(size_type N)
void push_back(const T &Elt)
BasicBlock * getDefaultDest() const
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
Analysis pass providing the TargetTransformInfo.
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI std::string getNameOrAsOperand() const
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
initializer< Ty > init(const Ty &Val)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > MaxNumPaths("dfa-max-num-paths", cl::desc("Max number of paths enumerated around a switch"), cl::Hidden, cl::init(200))
LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
auto pred_size(const MachineBasicBlock *BB)
static cl::opt< bool > ClViewCfgBefore("dfa-jump-view-cfg-before", cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden, cl::init(false))
auto map_range(ContainerTy &&C, FuncTy F)
static cl::opt< double > MaxClonedRate("dfa-max-cloned-rate", cl::desc("Maximum cloned instructions rate accepted for the transformation"), cl::Hidden, cl::init(7.5))
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxNumVisitiedPaths("dfa-max-num-visited-paths", cl::desc("Max number of blocks visited while enumerating paths around a switch"), cl::Hidden, cl::init(2500))
std::string join(IteratorT Begin, IteratorT End, StringRef Separator)
Joins the strings in the range [Begin, End), adding Separator between the elements.
static cl::opt< bool > EarlyExitHeuristic("dfa-early-exit-heuristic", cl::desc("Exit early if an unpredictable value come from the same loop"), cl::Hidden, cl::init(true))
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.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
LLVM_ABI bool VerifyDomInfo
Enables verification of dominator trees.
static cl::opt< unsigned > MaxOuterUseBlocks("dfa-max-out-use-blocks", cl::desc("Maximum unduplicated blocks with outer uses " "accepted for the transformation"), cl::Hidden, cl::init(40))
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > MaxPathLength("dfa-max-path-length", cl::desc("Max number of blocks searched to find a threading path"), cl::Hidden, cl::init(20))
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
bool pred_empty(const BasicBlock *BB)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
static cl::opt< unsigned > CostThreshold("dfa-cost-threshold", cl::desc("Maximum cost accepted for the transformation"), cl::Hidden, cl::init(50))
static LLVM_ABI void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Integrate with the new Pass Manager.