80#ifdef EXPENSIVE_CHECKS
86#define DEBUG_TYPE "dfa-jump-threading"
88STATISTIC(NumTransforms,
"Number of transformations done");
90STATISTIC(NumPaths,
"Number of individual paths threaded");
95 cl::desc(
"View the CFG before DFA Jump Threading"),
99 "dfa-early-exit-heuristic",
100 cl::desc(
"Exit early if an unpredictable value come from the same loop"),
104 "dfa-max-path-length",
105 cl::desc(
"Max number of blocks searched to find a threading path"),
109 "dfa-max-num-visited-paths",
111 "Max number of blocks visited while enumerating paths around a switch"),
116 cl::desc(
"Max number of paths enumerated around a switch"),
121 cl::desc(
"Maximum cost accepted for the transformation"),
129 "dfa-max-cloned-rate",
131 "Maximum cloned instructions rate accepted for the transformation"),
135class SelectInstToUnfold {
142 SelectInst *getInst() {
return SI; }
143 PHINode *getUse() {
return SIUse; }
145 explicit operator bool()
const {
return SI && SIUse; }
148class DFAJumpThreading {
150 DFAJumpThreading(AssumptionCache *AC, DominatorTree *DT, LoopInfo *LI,
151 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE)
152 : AC(AC), DT(DT), LI(LI), TTI(TTI), ORE(ORE) {}
154 bool run(Function &
F);
159 unfoldSelectInstrs(DominatorTree *DT,
162 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
165 while (!
Stack.empty()) {
166 SelectInstToUnfold SIToUnfold =
Stack.pop_back_val();
168 std::vector<SelectInstToUnfold> NewSIsToUnfold;
169 std::vector<BasicBlock *> NewBBs;
170 unfold(&DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);
177 static void unfold(DomTreeUpdater *DTU, LoopInfo *LI,
178 SelectInstToUnfold SIToUnfold,
179 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
180 std::vector<BasicBlock *> *NewBBs);
185 TargetTransformInfo *TTI;
186 OptimizationRemarkEmitter *ORE;
198 SelectInstToUnfold SIToUnfold,
199 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
200 std::vector<BasicBlock *> *NewBBs) {
201 SelectInst *
SI = SIToUnfold.getInst();
202 PHINode *SIUse = SIToUnfold.getUse();
206 BranchInst *StartBlockTerm =
214 SI->getContext(), Twine(
SI->getName(),
".si.unfold.false"),
216 NewBBs->push_back(NewBlock);
218 DTU->
applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});
225 Value *SIOp1 =
SI->getTrueValue();
226 Value *SIOp2 =
SI->getFalseValue();
229 Twine(SIOp2->
getName(),
".si.unfold.phi"),
234 for (PHINode &Phi : EndBlock->
phis()) {
237 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlock);
246 Twine(
SI->getName(),
".si.unfold.phi"),
249 if (Pred != StartBlock && Pred != NewBlock)
260 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));
262 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));
269 BI->setMetadata(LLVMContext::MD_prof,
270 SI->getMetadata(LLVMContext::MD_prof));
271 DTU->
applyUpdates({{DominatorTree::Insert, StartBlock, EndBlock},
272 {DominatorTree::Insert, StartBlock, NewBlock}});
276 SI->getContext(), Twine(
SI->getName(),
".si.unfold.true"),
279 SI->getContext(), Twine(
SI->getName(),
".si.unfold.false"),
282 NewBBs->push_back(NewBlockT);
283 NewBBs->push_back(NewBlockF);
308 BI->setMetadata(LLVMContext::MD_prof,
309 SI->getMetadata(LLVMContext::MD_prof));
310 DTU->
applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},
311 {DominatorTree::Insert, NewBlockT, EndBlock},
312 {DominatorTree::Insert, NewBlockF, EndBlock}});
327 NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));
329 NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));
336 for (PHINode &Phi : EndBlock->
phis()) {
339 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlockT);
340 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlockF);
341 Phi.removeIncomingValue(StartBlock);
346 unsigned SuccNum = StartBlockTerm->
getSuccessor(1) == EndBlock ? 1 : 0;
348 DTU->
applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},
349 {DominatorTree::Insert, StartBlock, NewBlockT}});
354 for (BasicBlock *NewBB : *NewBBs)
355 L->addBasicBlockToLoop(NewBB, *LI);
359 assert(
SI->use_empty() &&
"Select must be dead now");
360 SI->eraseFromParent();
403struct ThreadingPath {
405 APInt getExitValue()
const {
return ExitVal; }
406 void setExitValue(
const ConstantInt *V) {
407 ExitVal =
V->getValue();
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 {
426 OS << Path <<
" [ " << ExitVal <<
", " << DBB->
getName() <<
" ]";
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; }
592 StateDefMap StateDef = getStateDefMap();
593 if (StateDef.empty()) {
595 return OptimizationRemarkMissed(
DEBUG_TYPE,
"SwitchNotPredictable",
597 <<
"Switch instruction is not predictable.";
603 auto *SwitchPhiDefBB = SwitchPhi->getParent();
606 std::vector<ThreadingPath> PathsToPhiDef =
607 getPathsFromStateDefMap(StateDef, SwitchPhi, VB,
MaxNumPaths);
608 if (SwitchPhiDefBB == SwitchBlock || PathsToPhiDef.empty()) {
609 TPaths = std::move(PathsToPhiDef);
614 auto PathsLimit =
MaxNumPaths / PathsToPhiDef.size();
617 paths(SwitchPhiDefBB, SwitchBlock, VB, 1, PathsLimit);
618 if (PathsToSwitchBB.empty())
621 std::vector<ThreadingPath> TempList;
622 for (
const ThreadingPath &Path : PathsToPhiDef) {
623 for (
const PathType &PathToSw : PathsToSwitchBB) {
624 ThreadingPath PathCopy(Path);
625 PathCopy.appendExcludingFirst(PathToSw);
626 TempList.push_back(PathCopy);
629 TPaths = std::move(TempList);
635 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
636 std::vector<ThreadingPath> getPathsFromStateDefMap(StateDefMap &StateDef,
639 unsigned PathsLimit) {
640 std::vector<ThreadingPath> Res;
641 auto *PhiBB =
Phi->getParent();
645 for (
auto *IncomingBB :
Phi->blocks()) {
646 if (Res.size() >= PathsLimit)
648 if (!UniqueBlocks.
insert(IncomingBB).second)
650 if (!SwitchOuterLoop->
contains(IncomingBB))
653 Value *IncomingValue =
Phi->getIncomingValueForBlock(IncomingBB);
657 if (PhiBB == SwitchBlock &&
660 ThreadingPath NewPath;
661 NewPath.setDeterminator(PhiBB);
662 NewPath.setExitValue(
C);
664 if (IncomingBB != SwitchBlock)
665 NewPath.push_back(IncomingBB);
666 NewPath.push_back(PhiBB);
667 Res.push_back(NewPath);
671 if (VB.
contains(IncomingBB) || IncomingBB == SwitchBlock)
677 auto *IncomingPhiDefBB = IncomingPhi->getParent();
678 if (!StateDef.contains(IncomingPhiDefBB))
682 if (IncomingPhiDefBB == IncomingBB) {
683 assert(PathsLimit > Res.size());
684 std::vector<ThreadingPath> PredPaths = getPathsFromStateDefMap(
685 StateDef, IncomingPhi, VB, PathsLimit - Res.size());
686 for (ThreadingPath &Path : PredPaths) {
687 Path.push_back(PhiBB);
688 Res.push_back(std::move(Path));
698 assert(PathsLimit > Res.size());
699 auto InterPathLimit = PathsLimit - Res.size();
700 IntermediatePaths = paths(IncomingPhiDefBB, IncomingBB, VB,
702 if (IntermediatePaths.empty())
705 assert(InterPathLimit >= IntermediatePaths.size());
706 auto PredPathLimit = InterPathLimit / IntermediatePaths.size();
707 std::vector<ThreadingPath> PredPaths =
708 getPathsFromStateDefMap(StateDef, IncomingPhi, VB, PredPathLimit);
709 for (
const ThreadingPath &Path : PredPaths) {
710 for (
const PathType &IPath : IntermediatePaths) {
711 ThreadingPath NewPath(Path);
712 NewPath.appendExcludingFirst(IPath);
713 NewPath.push_back(PhiBB);
714 Res.push_back(NewPath);
723 unsigned PathDepth,
unsigned PathsLimit) {
729 return OptimizationRemarkAnalysis(
DEBUG_TYPE,
"MaxPathLengthReached",
731 <<
"Exploration stopped after visiting MaxPathLength="
748 SmallPtrSet<BasicBlock *, 4> Successors;
750 if (Res.size() >= PathsLimit)
752 if (!Successors.
insert(Succ).second)
757 Res.push_back({BB, ToBB});
767 if (Succ == CurrLoop->getHeader())
773 assert(PathsLimit > Res.size());
775 paths(Succ, ToBB, Visited, PathDepth + 1, PathsLimit - Res.size());
790 StateDefMap getStateDefMap()
const {
793 assert(FirstDef &&
"The first definition must be a phi.");
796 Stack.push_back(FirstDef);
797 SmallPtrSet<Value *, 16> SeenValues;
799 while (!
Stack.empty()) {
800 PHINode *CurPhi =
Stack.pop_back_val();
803 SeenValues.
insert(CurPhi);
805 for (BasicBlock *IncomingBB : CurPhi->
blocks()) {
806 PHINode *IncomingPhi =
810 bool IsOutsideLoops = !SwitchOuterLoop->
contains(IncomingBB);
811 if (SeenValues.
contains(IncomingPhi) || IsOutsideLoops)
814 Stack.push_back(IncomingPhi);
821 unsigned NumVisited = 0;
824 OptimizationRemarkEmitter *ORE;
825 std::vector<ThreadingPath> TPaths;
827 Loop *SwitchOuterLoop;
831 TransformDFA(AllSwitchPaths *SwitchPaths, DominatorTree *DT,
832 AssumptionCache *AC, TargetTransformInfo *
TTI,
833 OptimizationRemarkEmitter *ORE,
834 SmallPtrSet<const Value *, 32> EphValues)
835 : SwitchPaths(SwitchPaths), DT(DT), AC(AC),
TTI(
TTI), ORE(ORE),
836 EphValues(EphValues) {}
839 if (isLegalAndProfitableToTransform()) {
840 createAllExitPaths();
852 bool isLegalAndProfitableToTransform() {
854 uint64_t NumClonedInst = 0;
855 SwitchInst *
Switch = SwitchPaths->getSwitchInst();
858 if (
Switch->getNumSuccessors() <= 1)
864 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
866 APInt NextState = TPath.getExitValue();
867 const BasicBlock *Determinator = TPath.getDeterminatorBB();
870 BasicBlock *BB = SwitchPaths->getSwitchBlock();
871 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
873 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
875 DuplicateMap[BB].push_back({BB, NextState});
880 if (PathBBs.front() == Determinator)
885 auto DetIt =
llvm::find(PathBBs, Determinator);
886 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
888 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
891 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
893 DuplicateMap[BB].push_back({BB, NextState});
897 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
898 <<
"non-duplicatable instructions.\n");
900 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NonDuplicatableInst",
902 <<
"Contains non-duplicatable instructions.";
908 if (
Metrics.Convergence != ConvergenceKind::None) {
909 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
910 <<
"convergent instructions.\n");
912 return OptimizationRemarkMissed(
DEBUG_TYPE,
"ConvergentInst", Switch)
913 <<
"Contains convergent instructions.";
918 if (!
Metrics.NumInsts.isValid()) {
919 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
920 <<
"instructions with invalid cost.\n");
922 return OptimizationRemarkMissed(
DEBUG_TYPE,
"ConvergentInst", Switch)
923 <<
"Contains instructions with invalid cost.";
932 uint64_t NumOrigInst = 0;
933 for (
auto *BB : DuplicateMap.
keys())
935 if (
double(NumClonedInst) /
double(NumOrigInst) >
MaxClonedRate) {
936 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, too much "
937 "instructions wll be cloned\n");
939 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NotProfitable", Switch)
940 <<
"Too much instructions will be cloned.";
947 unsigned JumpTableSize = 0;
950 if (JumpTableSize == 0) {
954 unsigned CondBranches =
955 APInt(32,
Switch->getNumSuccessors()).ceilLogBase2();
956 assert(CondBranches > 0 &&
957 "The threaded switch must have multiple branches");
958 DuplicationCost =
Metrics.NumInsts / CondBranches;
966 DuplicationCost =
Metrics.NumInsts / JumpTableSize;
969 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump Threading: Cost to jump thread block "
970 << SwitchPaths->getSwitchBlock()->getName()
971 <<
" is: " << DuplicationCost <<
"\n\n");
974 LLVM_DEBUG(
dbgs() <<
"Not jump threading, duplication cost exceeds the "
975 <<
"cost threshold.\n");
977 return OptimizationRemarkMissed(
DEBUG_TYPE,
"NotProfitable", Switch)
978 <<
"Duplication cost exceeds the cost threshold (cost="
979 <<
ore::NV(
"Cost", DuplicationCost)
986 return OptimizationRemark(
DEBUG_TYPE,
"JumpThreaded", Switch)
987 <<
"Switch statement jump-threaded.";
994 void createAllExitPaths() {
996 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
997 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1001 TPath.push_front(SwitchBlock);
1008 SmallPtrSet<BasicBlock *, 16> BlocksToClean;
1012 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
1013 for (
const ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1014 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
1020 for (
const ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
1021 updateLastSuccessor(TPath, DuplicateMap, &DTU);
1028 for (BasicBlock *BB : BlocksToClean)
1038 void createExitPath(
DefMap &NewDefs,
const ThreadingPath &Path,
1040 SmallPtrSet<BasicBlock *, 16> &BlocksToClean,
1041 DomTreeUpdater *DTU) {
1042 APInt NextState =
Path.getExitValue();
1047 if (PathBBs.front() == Determinator)
1048 PathBBs.pop_front();
1050 auto DetIt =
llvm::find(PathBBs, Determinator);
1053 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt);
1054 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
1056 BlocksToClean.
insert(BB);
1060 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
1062 updatePredecessor(PrevBB, BB, NextBB, DTU);
1068 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
1069 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
1070 DuplicateMap[BB].push_back({NewBB, NextState});
1071 BlocksToClean.
insert(NewBB);
1082 void updateSSA(
DefMap &NewDefs) {
1083 SSAUpdaterBulk SSAUpdate;
1084 SmallVector<Use *, 16> UsesToRename;
1086 for (
const auto &KV : NewDefs) {
1089 std::vector<Instruction *> Cloned = KV.second;
1093 for (Use &U :
I->uses()) {
1096 if (UserPN->getIncomingBlock(U) == BB)
1098 }
else if (
User->getParent() == BB) {
1107 if (UsesToRename.
empty())
1115 unsigned VarNum = SSAUpdate.
AddVariable(
I->getName(),
I->getType());
1117 for (Instruction *New : Cloned)
1120 while (!UsesToRename.
empty())
1134 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
1135 const APInt &NextState,
1138 DomTreeUpdater *DTU) {
1146 for (Instruction &
I : *NewBB) {
1158 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1159 updatePredecessor(PrevBB, BB, NewBB, DTU);
1160 updateDefMap(NewDefs, VMap);
1163 SmallPtrSet<BasicBlock *, 4> SuccSet;
1165 if (SuccSet.
insert(SuccBB).second)
1166 DTU->
applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1176 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
1179 std::vector<BasicBlock *> BlocksToUpdate;
1183 if (BB == SwitchPaths->getSwitchBlock()) {
1184 SwitchInst *
Switch = SwitchPaths->getSwitchInst();
1185 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1186 BlocksToUpdate.push_back(NextCase);
1187 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1189 BlocksToUpdate.push_back(ClonedSucc);
1194 BlocksToUpdate.push_back(Succ);
1199 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1201 BlocksToUpdate.push_back(ClonedSucc);
1208 for (BasicBlock *Succ : BlocksToUpdate) {
1209 for (PHINode &Phi : Succ->phis()) {
1210 Value *Incoming =
Phi.getIncomingValueForBlock(BB);
1213 Phi.addIncoming(Incoming, ClonedBB);
1216 Value *ClonedVal = VMap[Incoming];
1218 Phi.addIncoming(ClonedVal, ClonedBB);
1220 Phi.addIncoming(Incoming, ClonedBB);
1228 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
1229 BasicBlock *NewBB, DomTreeUpdater *DTU) {
1232 if (!isPredecessor(OldBB, PrevBB))
1242 DTU->
applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1243 {DominatorTree::Insert, PrevBB, NewBB}});
1252 for (
auto Entry : VMap) {
1264 NewDefsVector.
push_back({Inst, Cloned});
1268 sort(NewDefsVector, [](
const auto &
LHS,
const auto &
RHS) {
1269 if (
LHS.first ==
RHS.first)
1270 return LHS.second->comesBefore(
RHS.second);
1271 return LHS.first->comesBefore(
RHS.first);
1274 for (
const auto &KV : NewDefsVector)
1275 NewDefs[KV.first].push_back(KV.second);
1283 void updateLastSuccessor(
const ThreadingPath &TPath,
1285 DomTreeUpdater *DTU) {
1286 APInt NextState = TPath.getExitValue();
1288 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1295 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1297 std::vector<DominatorTree::UpdateType> DTUpdates;
1298 SmallPtrSet<BasicBlock *, 4> SuccSet;
1299 for (BasicBlock *Succ :
successors(LastBlock)) {
1300 if (Succ != NextCase && SuccSet.
insert(Succ).second)
1301 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1304 Switch->eraseFromParent();
1312 void cleanPhiNodes(BasicBlock *BB) {
1317 PN.eraseFromParent();
1323 for (PHINode &Phi : BB->
phis())
1324 Phi.removeIncomingValueIf([&](
unsigned Index) {
1326 return !isPredecessor(BB, IncomingBB);
1332 BasicBlock *getClonedBB(BasicBlock *BB,
const APInt &NextState,
1338 auto It =
llvm::find_if(ClonedBBs, [NextState](
const ClonedBlock &
C) {
1339 return C.State == NextState;
1341 return It != ClonedBBs.end() ? (*It).BB :
nullptr;
1346 BasicBlock *getNextCaseSuccessor(SwitchInst *Switch,
const APInt &NextState) {
1348 for (
auto Case :
Switch->cases()) {
1349 if (Case.getCaseValue()->getValue() == NextState) {
1350 NextCase = Case.getCaseSuccessor();
1355 NextCase =
Switch->getDefaultDest();
1360 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
1364 AllSwitchPaths *SwitchPaths;
1366 AssumptionCache *AC;
1367 TargetTransformInfo *
TTI;
1368 OptimizationRemarkEmitter *ORE;
1369 SmallPtrSet<const Value *, 32> EphValues;
1370 std::vector<ThreadingPath> TPaths;
1374bool DFAJumpThreading::run(Function &
F) {
1375 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump threading: " <<
F.getName() <<
"\n");
1377 if (
F.hasOptSize()) {
1378 LLVM_DEBUG(
dbgs() <<
"Skipping due to the 'minsize' attribute\n");
1386 bool MadeChanges =
false;
1387 LoopInfoBroken =
false;
1389 for (BasicBlock &BB :
F) {
1395 <<
" is a candidate\n");
1396 MainSwitch
Switch(SI, LI, ORE);
1398 if (!
Switch.getInstr()) {
1400 <<
"candidate for jump threading\n");
1405 <<
"candidate for jump threading\n");
1408 unfoldSelectInstrs(DT,
Switch.getSelectInsts());
1409 if (!
Switch.getSelectInsts().empty())
1412 AllSwitchPaths SwitchPaths(&Switch, ORE, LI,
1416 if (SwitchPaths.getNumThreadingPaths() > 0) {
1433 SmallPtrSet<const Value *, 32> EphValues;
1434 if (ThreadableLoops.
size() > 0)
1437 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1438 TransformDFA Transform(&SwitchPaths, DT, AC,
TTI, ORE, EphValues);
1439 if (Transform.run())
1440 MadeChanges = LoopInfoBroken =
true;
1443#ifdef EXPENSIVE_CHECKS
1444 assert(DT->
verify(DominatorTree::VerificationLevel::Full));
1459 DFAJumpThreading ThreadImpl(&AC, &DT, &LI, &
TTI, &ORE);
1460 if (!ThreadImpl.run(
F))
1465 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
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))
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)
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.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
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)
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 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.
A raw_ostream that writes to an std::string.
@ 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))
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))
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)
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.