82#ifdef EXPENSIVE_CHECKS
88#define DEBUG_TYPE "dfa-jump-threading"
90STATISTIC(NumTransforms,
"Number of transformations done");
92STATISTIC(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"),
127class SelectInstToUnfold {
135 PHINode *getUse() {
return SIUse; }
137 explicit operator bool()
const {
return SI && SIUse; }
141 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
142 std::vector<BasicBlock *> *NewBBs);
144class DFAJumpThreading {
148 : AC(AC), DT(DT), LI(LI),
TTI(
TTI), ORE(ORE) {}
160 while (!
Stack.empty()) {
161 SelectInstToUnfold SIToUnfold =
Stack.pop_back_val();
163 std::vector<SelectInstToUnfold> NewSIsToUnfold;
164 std::vector<BasicBlock *> NewBBs;
165 unfold(&DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);
168 for (
const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold)
169 Stack.push_back(NewSIToUnfold);
192 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
193 std::vector<BasicBlock *> *NewBBs) {
195 PHINode *SIUse = SIToUnfold.getUse();
207 SI->getContext(),
Twine(
SI->getName(),
".si.unfold.false"),
209 NewBBs->push_back(NewBlock);
211 DTU->
applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});
218 Value *SIOp1 =
SI->getTrueValue();
219 Value *SIOp2 =
SI->getFalseValue();
226 if (
auto *OpSi = dyn_cast<SelectInst>(SIOp1))
227 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));
228 if (
auto *OpSi = dyn_cast<SelectInst>(SIOp2))
229 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));
242 Phi->addIncoming(
Phi->getIncomingValueForBlock(StartBlock), NewBlock);
249 DTU->
applyUpdates({{DominatorTree::Insert, StartBlock, EndBlock},
250 {DominatorTree::Insert, StartBlock, NewBlock}});
253 SI->getContext(),
Twine(
SI->getName(),
".si.unfold.true"),
256 SI->getContext(),
Twine(
SI->getName(),
".si.unfold.false"),
259 NewBBs->push_back(NewBlockT);
260 NewBBs->push_back(NewBlockF);
283 DTU->
applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},
284 {DominatorTree::Insert, NewBlockT, EndBlock},
285 {DominatorTree::Insert, NewBlockF, EndBlock}});
299 if (
auto *TrueSI = dyn_cast<SelectInst>(TrueVal))
300 NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));
301 if (
auto *FalseSi = dyn_cast<SelectInst>(FalseVal))
302 NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));
312 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlockT);
313 Phi.addIncoming(
Phi.getIncomingValueForBlock(StartBlock), NewBlockF);
314 Phi.removeIncomingValue(StartBlock);
319 unsigned SuccNum = StartBlockTerm->
getSuccessor(1) == EndBlock ? 1 : 0;
321 DTU->
applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},
322 {DominatorTree::Insert, StartBlock, NewBlockT}});
328 L->addBasicBlockToLoop(NewBB, *LI);
332 assert(
SI->use_empty() &&
"Select must be dead now");
333 SI->eraseFromParent();
341typedef std::deque<BasicBlock *> PathType;
342typedef std::vector<PathType> PathsType;
344typedef std::vector<ClonedBlock> CloneList;
373struct ThreadingPath {
375 APInt getExitValue()
const {
return ExitVal; }
377 ExitVal =
V->getValue();
380 bool isExitValueSet()
const {
return IsExitValSet; }
383 const BasicBlock *getDeterminatorBB()
const {
return DBB; }
384 void setDeterminator(
const BasicBlock *BB) { DBB = BB; }
387 const PathType &getPath()
const {
return Path; }
388 void setPath(
const PathType &NewPath) {
Path = NewPath; }
391 void appendExcludingFirst(
const PathType &OtherPath) {
392 Path.insert(
Path.end(), OtherPath.begin() + 1, OtherPath.end());
396 OS <<
Path <<
" [ " << ExitVal <<
", " << DBB->getName() <<
" ]";
403 bool IsExitValSet =
false;
421 <<
"Switch instruction is not predictable.";
426 virtual ~MainSwitch() =
default;
439 std::deque<std::pair<Value *, BasicBlock *>> Q;
443 Value *SICond =
SI->getCondition();
445 if (!isa<PHINode>(SICond))
453 addToQueue(SICond,
nullptr, Q, SeenValues);
456 Value *Current = Q.front().first;
460 if (
auto *Phi = dyn_cast<PHINode>(Current)) {
463 addToQueue(
Incoming, IncomingBB, Q, SeenValues);
466 }
else if (
SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
467 if (!isValidSelectInst(SelI))
469 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);
470 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);
472 if (
auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
473 SelectInsts.
push_back(SelectInstToUnfold(SelI, SelIUse));
474 }
else if (isa<Constant>(Current)) {
491 <<
"\tExiting early due to unpredictability heuristic.\n");
503 std::deque<std::pair<Value *, BasicBlock *>> &Q,
507 Q.push_back({Val, BB});
512 if (!
SI->hasOneUse())
517 if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
529 PHINode *PHIUser = dyn_cast<PHINode>(SIUse);
535 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
550struct AllSwitchPaths {
554 LI(LI), SwitchOuterLoop(
L) {}
556 std::vector<ThreadingPath> &getThreadingPaths() {
return TPaths; }
557 unsigned getNumThreadingPaths() {
return TPaths.size(); }
559 BasicBlock *getSwitchBlock() {
return SwitchBlock; }
562 StateDefMap StateDef = getStateDefMap();
563 if (StateDef.empty()) {
567 <<
"Switch instruction is not predictable.";
572 auto *SwitchPhi = cast<PHINode>(
Switch->getOperand(0));
573 auto *SwitchPhiDefBB = SwitchPhi->getParent();
576 std::vector<ThreadingPath> PathsToPhiDef =
577 getPathsFromStateDefMap(StateDef, SwitchPhi, VB);
578 if (SwitchPhiDefBB == SwitchBlock) {
579 TPaths = std::move(PathsToPhiDef);
584 PathsType PathsToSwitchBB =
585 paths(SwitchPhiDefBB, SwitchBlock, VB, 1);
586 if (PathsToSwitchBB.empty())
589 std::vector<ThreadingPath> TempList;
590 for (
const ThreadingPath &Path : PathsToPhiDef) {
591 for (
const PathType &PathToSw : PathsToSwitchBB) {
592 ThreadingPath PathCopy(Path);
593 PathCopy.appendExcludingFirst(PathToSw);
594 TempList.push_back(PathCopy);
597 TPaths = std::move(TempList);
604 std::vector<ThreadingPath> getPathsFromStateDefMap(StateDefMap &StateDef,
607 std::vector<ThreadingPath> Res;
608 auto *PhiBB =
Phi->getParent();
611 VisitedBlocks UniqueBlocks;
612 for (
auto *IncomingBB :
Phi->blocks()) {
613 if (!UniqueBlocks.insert(IncomingBB).second)
615 if (!SwitchOuterLoop->contains(IncomingBB))
618 Value *IncomingValue =
Phi->getIncomingValueForBlock(IncomingBB);
620 if (
auto *
C = dyn_cast<ConstantInt>(IncomingValue)) {
622 if (PhiBB == SwitchBlock &&
623 SwitchBlock != cast<PHINode>(
Switch->getOperand(0))->getParent())
625 ThreadingPath NewPath;
626 NewPath.setDeterminator(PhiBB);
627 NewPath.setExitValue(
C);
629 if (IncomingBB != SwitchBlock)
630 NewPath.push_back(IncomingBB);
631 NewPath.push_back(PhiBB);
632 Res.push_back(NewPath);
636 if (
VB.contains(IncomingBB) || IncomingBB == SwitchBlock)
639 auto *IncomingPhi = dyn_cast<PHINode>(IncomingValue);
642 auto *IncomingPhiDefBB = IncomingPhi->getParent();
643 if (!StateDef.contains(IncomingPhiDefBB))
647 if (IncomingPhiDefBB == IncomingBB) {
648 std::vector<ThreadingPath> PredPaths =
649 getPathsFromStateDefMap(StateDef, IncomingPhi, VB);
650 for (ThreadingPath &Path : PredPaths) {
651 Path.push_back(PhiBB);
652 Res.push_back(std::move(Path));
658 if (
VB.contains(IncomingPhiDefBB))
661 PathsType IntermediatePaths;
663 paths(IncomingPhiDefBB, IncomingBB, VB, 1);
664 if (IntermediatePaths.empty())
667 std::vector<ThreadingPath> PredPaths =
668 getPathsFromStateDefMap(StateDef, IncomingPhi, VB);
669 for (
const ThreadingPath &Path : PredPaths) {
670 for (
const PathType &IPath : IntermediatePaths) {
671 ThreadingPath NewPath(Path);
672 NewPath.appendExcludingFirst(IPath);
673 NewPath.push_back(PhiBB);
674 Res.push_back(NewPath);
683 unsigned PathDepth) {
691 <<
"Exploration stopped after visiting MaxPathLength="
703 if (!SwitchOuterLoop->contains(BB))
710 if (!Successors.
insert(Succ).second)
715 Res.push_back({BB, ToBB});
720 if (Visited.contains(Succ))
725 if (Succ == CurrLoop->getHeader())
732 PathsType SuccPaths = paths(Succ, ToBB, Visited, PathDepth + 1);
733 for (PathType &Path : SuccPaths) {
752 StateDefMap getStateDefMap()
const {
755 assert(isa<PHINode>(FirstDef) &&
"The first definition must be a phi.");
758 Stack.push_back(dyn_cast<PHINode>(FirstDef));
761 while (!
Stack.empty()) {
765 SeenValues.
insert(CurPhi);
769 bool IsOutsideLoops = !SwitchOuterLoop->contains(IncomingBB);
777 return StateDefMap();
786 unsigned NumVisited = 0;
790 std::vector<ThreadingPath> TPaths;
792 Loop *SwitchOuterLoop;
800 : SwitchPaths(SwitchPaths), DT(DT), AC(AC),
TTI(
TTI), ORE(ORE),
801 EphValues(EphValues) {}
804 if (isLegalAndProfitableToTransform()) {
805 createAllExitPaths();
815 bool isLegalAndProfitableToTransform() {
820 if (
Switch->getNumSuccessors() <= 1)
825 DuplicateBlockMap DuplicateMap;
827 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
828 PathType PathBBs = TPath.getPath();
829 APInt NextState = TPath.getExitValue();
830 const BasicBlock *Determinator = TPath.getDeterminatorBB();
833 BasicBlock *BB = SwitchPaths->getSwitchBlock();
834 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
836 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
837 DuplicateMap[BB].push_back({BB, NextState});
842 if (PathBBs.front() == Determinator)
847 auto DetIt =
llvm::find(PathBBs, Determinator);
848 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
850 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
853 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
854 DuplicateMap[BB].push_back({BB, NextState});
858 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
859 <<
"non-duplicatable instructions.\n");
863 <<
"Contains non-duplicatable instructions.";
869 if (
Metrics.Convergence != ConvergenceKind::None) {
870 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
871 <<
"convergent instructions.\n");
874 <<
"Contains convergent instructions.";
879 if (!
Metrics.NumInsts.isValid()) {
880 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
881 <<
"instructions with invalid cost.\n");
884 <<
"Contains instructions with invalid cost.";
892 unsigned JumpTableSize = 0;
895 if (JumpTableSize == 0) {
899 unsigned CondBranches =
901 assert(CondBranches > 0 &&
902 "The threaded switch must have multiple branches");
903 DuplicationCost =
Metrics.NumInsts / CondBranches;
911 DuplicationCost =
Metrics.NumInsts / JumpTableSize;
914 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump Threading: Cost to jump thread block "
915 << SwitchPaths->getSwitchBlock()->getName()
916 <<
" is: " << DuplicationCost <<
"\n\n");
919 LLVM_DEBUG(
dbgs() <<
"Not jump threading, duplication cost exceeds the "
920 <<
"cost threshold.\n");
923 <<
"Duplication cost exceeds the cost threshold (cost="
924 <<
ore::NV(
"Cost", DuplicationCost)
932 <<
"Switch statement jump-threaded.";
939 void createAllExitPaths() {
943 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
944 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
948 TPath.push_front(SwitchBlock);
952 DuplicateBlockMap DuplicateMap;
959 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
960 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
966 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
967 updateLastSuccessor(TPath, DuplicateMap, &DTU);
983 void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
984 DuplicateBlockMap &DuplicateMap,
989 PathType PathBBs =
Path.getPath();
992 if (PathBBs.front() == Determinator)
995 auto DetIt =
llvm::find(PathBBs, Determinator);
998 BasicBlock *PrevBB = PathBBs.
size() == 1 ? *DetIt : *std::prev(DetIt);
999 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
1001 BlocksToClean.
insert(BB);
1005 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
1007 updatePredecessor(PrevBB, BB, NextBB, DTU);
1013 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
1014 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
1015 DuplicateMap[BB].push_back({NewBB, NextState});
1016 BlocksToClean.
insert(NewBB);
1027 void updateSSA(DefMap &NewDefs) {
1031 for (
const auto &KV : NewDefs) {
1034 std::vector<Instruction *> Cloned = KV.second;
1038 for (
Use &U :
I->uses()) {
1041 if (UserPN->getIncomingBlock(U) == BB)
1043 }
else if (
User->getParent() == BB) {
1052 if (UsesToRename.
empty())
1060 unsigned VarNum = SSAUpdate.
AddVariable(
I->getName(),
I->getType());
1065 while (!UsesToRename.
empty())
1080 const APInt &NextState,
1081 DuplicateBlockMap &DuplicateMap,
1095 if (isa<PHINode>(&
I))
1100 AC->registerAssumption(
II);
1103 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1104 updatePredecessor(PrevBB, BB, NewBB, DTU);
1105 updateDefMap(NewDefs, VMap);
1110 if (SuccSet.
insert(SuccBB).second)
1111 DTU->
applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1123 DuplicateBlockMap &DuplicateMap) {
1124 std::vector<BasicBlock *> BlocksToUpdate;
1128 if (BB == SwitchPaths->getSwitchBlock()) {
1130 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1131 BlocksToUpdate.push_back(NextCase);
1132 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1134 BlocksToUpdate.push_back(ClonedSucc);
1139 BlocksToUpdate.push_back(Succ);
1144 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1146 BlocksToUpdate.push_back(ClonedSucc);
1154 for (
auto II = Succ->begin();
PHINode *Phi = dyn_cast<PHINode>(
II);
1164 Phi->addIncoming(ClonedVal, ClonedBB);
1178 if (!isPredecessor(OldBB, PrevBB))
1188 DTU->
applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1189 {DominatorTree::Insert, PrevBB, NewBB}});
1198 for (
auto Entry : VMap) {
1200 dyn_cast<Instruction>(
const_cast<Value *
>(
Entry.first));
1201 if (!Inst || !
Entry.second || isa<BranchInst>(Inst) ||
1202 isa<SwitchInst>(Inst)) {
1210 NewDefsVector.
push_back({Inst, Cloned});
1214 sort(NewDefsVector, [](
const auto &LHS,
const auto &RHS) {
1215 if (
LHS.first ==
RHS.first)
1216 return LHS.second->comesBefore(
RHS.second);
1217 return LHS.first->comesBefore(
RHS.first);
1220 for (
const auto &KV : NewDefsVector)
1221 NewDefs[KV.first].push_back(KV.second);
1229 void updateLastSuccessor(ThreadingPath &TPath,
1230 DuplicateBlockMap &DuplicateMap,
1232 APInt NextState = TPath.getExitValue();
1234 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1241 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1243 std::vector<DominatorTree::UpdateType> DTUpdates;
1246 if (Succ != NextCase && SuccSet.
insert(Succ).second)
1247 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1250 Switch->eraseFromParent();
1261 std::vector<PHINode *> PhiToRemove;
1263 PhiToRemove.push_back(Phi);
1265 for (
PHINode *PN : PhiToRemove) {
1267 PN->eraseFromParent();
1274 std::vector<BasicBlock *> BlocksToRemove;
1276 if (!isPredecessor(BB, IncomingBB))
1277 BlocksToRemove.push_back(IncomingBB);
1280 Phi->removeIncomingValue(BB);
1287 DuplicateBlockMap &DuplicateMap) {
1288 CloneList ClonedBBs = DuplicateMap[BB];
1292 auto It =
llvm::find_if(ClonedBBs, [NextState](
const ClonedBlock &
C) {
1293 return C.State == NextState;
1295 return It != ClonedBBs.end() ? (*It).BB :
nullptr;
1302 for (
auto Case :
Switch->cases()) {
1303 if (Case.getCaseValue()->getValue() == NextState) {
1304 NextCase = Case.getCaseSuccessor();
1309 NextCase =
Switch->getDefaultDest();
1318 AllSwitchPaths *SwitchPaths;
1324 std::vector<ThreadingPath> TPaths;
1327bool DFAJumpThreading::run(
Function &
F) {
1328 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump threading: " <<
F.getName() <<
"\n");
1330 if (
F.hasOptSize()) {
1331 LLVM_DEBUG(
dbgs() <<
"Skipping due to the 'minsize' attribute\n");
1339 bool MadeChanges =
false;
1340 LoopInfoBroken =
false;
1348 <<
" is a candidate\n");
1349 MainSwitch
Switch(SI, LI, ORE);
1351 if (!
Switch.getInstr()) {
1353 <<
"candidate for jump threading\n");
1358 <<
"candidate for jump threading\n");
1361 unfoldSelectInstrs(DT,
Switch.getSelectInsts());
1362 if (!
Switch.getSelectInsts().empty())
1365 AllSwitchPaths SwitchPaths(&Switch, ORE, LI,
1369 if (SwitchPaths.getNumThreadingPaths() > 0) {
1387 if (ThreadableLoops.
size() > 0)
1390 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1391 TransformDFA Transform(&SwitchPaths, DT, AC,
TTI, ORE, EphValues);
1394 LoopInfoBroken =
true;
1397#ifdef EXPENSIVE_CHECKS
1398 assert(DT->
verify(DominatorTree::VerificationLevel::Full));
1415 DFAJumpThreading ThreadImpl(&AC, &DT, &LI, &
TTI, &ORE);
1416 if (!ThreadImpl.run(
F))
1421 if (!ThreadImpl.LoopInfoBroken)
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...
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))
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(2000))
static cl::opt< bool > ClViewCfgBefore("dfa-jump-view-cfg-before", cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden, cl::init(false))
static cl::opt< unsigned > CostThreshold("dfa-cost-threshold", cl::desc("Maximum cost accepted for the transformation"), cl::Hidden, cl::init(50))
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))
static cl::opt< unsigned > MaxNumPaths("dfa-max-num-paths", cl::desc("Max number of paths enumerated around a switch"), cl::Hidden, cl::init(200))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This 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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
unsigned ceilLogBase2() const
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.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
const Function * getParent() const
Return the enclosing method, or null if none.
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...
const Instruction & back() const
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
This is the shared class of boolean and integer constants.
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< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
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.
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.
Represents a single loop in the control flow graph.
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
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
Helper class for SSA formation on a set of values defined in multiple blocks.
unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.
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
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
bool contains(const T &V) const
Check if the SmallSet contains the given element.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
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.
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.
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< InstrNode * > Instr
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
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)
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
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...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Utility to calculate the size and a few similar metrics for a set of basic blocks.
static 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.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...