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"),
111 cl::desc(
"Max number of paths enumerated around a switch"),
116 cl::desc(
"Maximum cost accepted for the transformation"),
121class SelectInstToUnfold {
129 PHINode *getUse() {
return SIUse; }
131 explicit operator bool()
const {
return SI && SIUse; }
135 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
136 std::vector<BasicBlock *> *NewBBs);
138class DFAJumpThreading {
142 : AC(AC), DT(DT), LI(LI),
TTI(
TTI), ORE(ORE) {}
152 for (SelectInstToUnfold SIToUnfold : SelectInsts)
153 Stack.push_back(SIToUnfold);
155 while (!
Stack.empty()) {
156 SelectInstToUnfold SIToUnfold =
Stack.pop_back_val();
158 std::vector<SelectInstToUnfold> NewSIsToUnfold;
159 std::vector<BasicBlock *> NewBBs;
160 unfold(&DTU, SIToUnfold, &NewSIsToUnfold, &NewBBs);
163 for (
const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold)
164 Stack.push_back(NewSIToUnfold);
180void createBasicBlockAndSinkSelectInst(
183 BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold,
184 std::vector<BasicBlock *> *NewBBs) {
190 NewBBs->push_back(*NewBlock);
193 NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse));
194 DTU->
applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}});
205 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
206 std::vector<BasicBlock *> *NewBBs) {
208 PHINode *SIUse = SIToUnfold.getUse();
225 if (
SelectInst *SIOp = dyn_cast<SelectInst>(
SI->getTrueValue())) {
226 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
227 "si.unfold.true", &TrueBlock, &TrueBranch,
228 NewSIsToUnfold, NewBBs);
230 if (
SelectInst *SIOp = dyn_cast<SelectInst>(
SI->getFalseValue())) {
231 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
232 "si.unfold.false", &FalseBlock,
233 &FalseBranch, NewSIsToUnfold, NewBBs);
238 if (!TrueBlock && !FalseBlock) {
241 NewBBs->push_back(FalseBlock);
243 DTU->
applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
253 if (TrueBlock && FalseBlock) {
265 Value *OrigValue =
Phi.getIncomingValueForBlock(StartBlock);
266 Phi.addIncoming(OrigValue, TrueBlock);
267 Phi.addIncoming(OrigValue, FalseBlock);
272 Phi.removeIncomingValue(StartBlock,
false);
276 Value *SIOp1 =
SI->getTrueValue();
277 Value *SIOp2 =
SI->getFalseValue();
281 NewBlock = FalseBlock;
286 NewBlock = TrueBlock;
299 for (
auto II = EndBlock->
begin();
PHINode *Phi = dyn_cast<PHINode>(II);
302 Phi->addIncoming(
Phi->getIncomingValueForBlock(StartBlock), NewBlock);
308 {DominatorTree::Insert, StartBlock, FT}});
311 assert(
SI->use_empty() &&
"Select must be dead now");
312 SI->eraseFromParent();
320typedef std::deque<BasicBlock *> PathType;
321typedef std::vector<PathType> PathsType;
323typedef std::vector<ClonedBlock> CloneList;
352struct ThreadingPath {
354 APInt getExitValue()
const {
return ExitVal; }
356 ExitVal =
V->getValue();
359 bool isExitValueSet()
const {
return IsExitValSet; }
362 const BasicBlock *getDeterminatorBB()
const {
return DBB; }
363 void setDeterminator(
const BasicBlock *BB) { DBB = BB; }
366 const PathType &getPath()
const {
return Path; }
367 void setPath(
const PathType &NewPath) {
Path = NewPath; }
370 OS <<
Path <<
" [ " << ExitVal <<
", " << DBB->getName() <<
" ]";
377 bool IsExitValSet =
false;
395 <<
"Switch instruction is not predictable.";
400 virtual ~MainSwitch() =
default;
413 std::deque<std::pair<Value *, BasicBlock *>> Q;
417 Value *SICond =
SI->getCondition();
419 if (!isa<PHINode>(SICond))
427 addToQueue(SICond,
nullptr, Q, SeenValues);
430 Value *Current = Q.front().first;
434 if (
auto *Phi = dyn_cast<PHINode>(Current)) {
437 addToQueue(
Incoming, IncomingBB, Q, SeenValues);
440 }
else if (
SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
441 if (!isValidSelectInst(SelI))
443 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);
444 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);
446 if (
auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
447 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
448 }
else if (isa<Constant>(Current)) {
465 <<
"\tExiting early due to unpredictability heuristic.\n");
477 std::deque<std::pair<Value *, BasicBlock *>> &Q,
481 Q.push_back({Val, BB});
486 if (!
SI->hasOneUse())
491 if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
503 PHINode *PHIUser = dyn_cast<PHINode>(SIUse);
509 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
524struct AllSwitchPaths {
529 std::vector<ThreadingPath> &getThreadingPaths() {
return TPaths; }
530 unsigned getNumThreadingPaths() {
return TPaths.size(); }
532 BasicBlock *getSwitchBlock() {
return SwitchBlock; }
535 VisitedBlocks Visited;
536 PathsType LoopPaths = paths(SwitchBlock, Visited, 1);
537 StateDefMap StateDef = getStateDefMap(LoopPaths);
539 if (StateDef.empty()) {
543 <<
"Switch instruction is not predictable.";
548 for (PathType Path : LoopPaths) {
553 if (StateDef.contains(BB)) {
554 const PHINode *
Phi = dyn_cast<PHINode>(StateDef[BB]);
555 assert(Phi &&
"Expected a state-defining instr to be a phi node.");
557 const Value *
V =
Phi->getIncomingValueForBlock(PrevBB);
558 if (
const ConstantInt *
C = dyn_cast<const ConstantInt>(V)) {
559 TPath.setExitValue(
C);
560 TPath.setDeterminator(BB);
566 if (TPath.isExitValueSet() && BB ==
Path.front())
572 if (TPath.isExitValueSet() && isSupported(TPath))
573 TPaths.push_back(TPath);
582 PathsType paths(
BasicBlock *BB, VisitedBlocks &Visited,
583 unsigned PathDepth)
const {
591 <<
"Exploration stopped after visiting MaxPathLength="
603 if (!Successors.
insert(Succ).second)
607 if (Succ == SwitchBlock) {
613 if (Visited.contains(Succ))
616 PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
617 for (
const PathType &Path : SuccPaths) {
618 PathType NewPath(Path);
619 NewPath.push_front(BB);
620 Res.push_back(NewPath);
637 StateDefMap getStateDefMap(
const PathsType &LoopPaths)
const {
642 for (
const PathType &Path : LoopPaths) {
649 assert(isa<PHINode>(FirstDef) &&
"The first definition must be a phi.");
652 Stack.push_back(dyn_cast<PHINode>(FirstDef));
655 while (!
Stack.empty()) {
659 SeenValues.
insert(CurPhi);
663 bool IsOutsideLoops = LoopBBs.
count(IncomingBB) == 0;
671 return StateDefMap();
698 bool isSupported(
const ThreadingPath &TPath) {
706 const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
709 SwitchCondUseBB == TPath.getPath().front() &&
710 "The first BB in a threading path should have the switch instruction");
711 if (SwitchCondUseBB != TPath.getPath().front())
715 PathType
Path = TPath.getPath();
716 auto ItDet =
llvm::find(Path, DeterminatorBB);
717 std::rotate(
Path.begin(), ItDet,
Path.end());
719 bool IsDetBBSeen =
false;
720 bool IsDefBBSeen =
false;
721 bool IsUseBBSeen =
false;
723 if (BB == DeterminatorBB)
725 if (BB == SwitchCondDefBB)
727 if (BB == SwitchCondUseBB)
729 if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
739 std::vector<ThreadingPath> TPaths;
747 : SwitchPaths(SwitchPaths), DT(DT), AC(AC),
TTI(
TTI), ORE(ORE),
748 EphValues(EphValues) {}
751 if (isLegalAndProfitableToTransform()) {
752 createAllExitPaths();
762 bool isLegalAndProfitableToTransform() {
767 if (
Switch->getNumSuccessors() <= 1)
772 DuplicateBlockMap DuplicateMap;
774 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
775 PathType PathBBs = TPath.getPath();
776 APInt NextState = TPath.getExitValue();
777 const BasicBlock *Determinator = TPath.getDeterminatorBB();
780 BasicBlock *BB = SwitchPaths->getSwitchBlock();
781 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
783 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
784 DuplicateMap[BB].push_back({BB, NextState});
789 if (PathBBs.front() == Determinator)
794 auto DetIt =
llvm::find(PathBBs, Determinator);
795 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
797 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
800 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
801 DuplicateMap[BB].push_back({BB, NextState});
805 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
806 <<
"non-duplicatable instructions.\n");
810 <<
"Contains non-duplicatable instructions.";
816 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
817 <<
"convergent instructions.\n");
820 <<
"Contains convergent instructions.";
825 if (!
Metrics.NumInsts.isValid()) {
826 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
827 <<
"instructions with invalid cost.\n");
830 <<
"Contains instructions with invalid cost.";
838 unsigned JumpTableSize = 0;
841 if (JumpTableSize == 0) {
845 unsigned CondBranches =
847 assert(CondBranches > 0 &&
848 "The threaded switch must have multiple branches");
849 DuplicationCost =
Metrics.NumInsts / CondBranches;
857 DuplicationCost =
Metrics.NumInsts / JumpTableSize;
860 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump Threading: Cost to jump thread block "
861 << SwitchPaths->getSwitchBlock()->getName()
862 <<
" is: " << DuplicationCost <<
"\n\n");
865 LLVM_DEBUG(
dbgs() <<
"Not jump threading, duplication cost exceeds the "
866 <<
"cost threshold.\n");
869 <<
"Duplication cost exceeds the cost threshold (cost="
870 <<
ore::NV(
"Cost", DuplicationCost)
878 <<
"Switch statement jump-threaded.";
885 void createAllExitPaths() {
889 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
890 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
892 PathType NewPath(TPath.getPath());
893 NewPath.push_back(SwitchBlock);
894 TPath.setPath(NewPath);
898 DuplicateBlockMap DuplicateMap;
905 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
906 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
912 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
913 updateLastSuccessor(TPath, DuplicateMap, &DTU);
929 void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
930 DuplicateBlockMap &DuplicateMap,
935 PathType PathBBs =
Path.getPath();
938 if (PathBBs.front() == Determinator)
941 auto DetIt =
llvm::find(PathBBs, Determinator);
944 BasicBlock *PrevBB = PathBBs.
size() == 1 ? *DetIt : *std::prev(DetIt);
945 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
951 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
953 updatePredecessor(PrevBB, BB, NextBB, DTU);
959 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
960 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
961 DuplicateMap[BB].push_back({NewBB, NextState});
962 BlocksToClean.
insert(NewBB);
973 void updateSSA(DefMap &NewDefs) {
977 for (
const auto &KV : NewDefs) {
980 std::vector<Instruction *> Cloned = KV.second;
984 for (
Use &U :
I->uses()) {
987 if (UserPN->getIncomingBlock(U) == BB)
989 }
else if (
User->getParent() == BB) {
998 if (UsesToRename.
empty())
1006 unsigned VarNum = SSAUpdate.
AddVariable(
I->getName(),
I->getType());
1011 while (!UsesToRename.
empty())
1026 const APInt &NextState,
1027 DuplicateBlockMap &DuplicateMap,
1041 if (isa<PHINode>(&
I))
1046 AC->registerAssumption(II);
1049 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1050 updatePredecessor(PrevBB, BB, NewBB, DTU);
1051 updateDefMap(NewDefs, VMap);
1056 if (SuccSet.
insert(SuccBB).second)
1057 DTU->
applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1069 DuplicateBlockMap &DuplicateMap) {
1070 std::vector<BasicBlock *> BlocksToUpdate;
1074 if (BB == SwitchPaths->getSwitchBlock()) {
1076 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1077 BlocksToUpdate.push_back(NextCase);
1078 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1080 BlocksToUpdate.push_back(ClonedSucc);
1085 BlocksToUpdate.push_back(Succ);
1090 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1092 BlocksToUpdate.push_back(ClonedSucc);
1100 for (
auto II = Succ->begin();
PHINode *Phi = dyn_cast<PHINode>(II);
1110 Phi->addIncoming(ClonedVal, ClonedBB);
1124 if (!isPredecessor(OldBB, PrevBB))
1134 DTU->
applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1135 {DominatorTree::Insert, PrevBB, NewBB}});
1144 for (
auto Entry : VMap) {
1146 dyn_cast<Instruction>(
const_cast<Value *
>(Entry.first));
1147 if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1148 isa<SwitchInst>(Inst)) {
1152 Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1156 NewDefsVector.
push_back({Inst, Cloned});
1160 sort(NewDefsVector, [](
const auto &LHS,
const auto &RHS) {
1161 if (
LHS.first ==
RHS.first)
1162 return LHS.second->comesBefore(
RHS.second);
1163 return LHS.first->comesBefore(
RHS.first);
1166 for (
const auto &KV : NewDefsVector)
1167 NewDefs[KV.first].push_back(KV.second);
1175 void updateLastSuccessor(ThreadingPath &TPath,
1176 DuplicateBlockMap &DuplicateMap,
1178 APInt NextState = TPath.getExitValue();
1180 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1187 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1189 std::vector<DominatorTree::UpdateType> DTUpdates;
1192 if (Succ != NextCase && SuccSet.
insert(Succ).second)
1193 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1196 Switch->eraseFromParent();
1207 std::vector<PHINode *> PhiToRemove;
1208 for (
auto II = BB->
begin();
PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1209 PhiToRemove.push_back(Phi);
1211 for (
PHINode *PN : PhiToRemove) {
1213 PN->eraseFromParent();
1219 for (
auto II = BB->
begin();
PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1220 std::vector<BasicBlock *> BlocksToRemove;
1222 if (!isPredecessor(BB, IncomingBB))
1223 BlocksToRemove.push_back(IncomingBB);
1226 Phi->removeIncomingValue(BB);
1233 DuplicateBlockMap &DuplicateMap) {
1234 CloneList ClonedBBs = DuplicateMap[BB];
1238 auto It =
llvm::find_if(ClonedBBs, [NextState](
const ClonedBlock &
C) {
1239 return C.State == NextState;
1241 return It != ClonedBBs.end() ? (*It).BB :
nullptr;
1248 for (
auto Case :
Switch->cases()) {
1249 if (Case.getCaseValue()->getValue() == NextState) {
1250 NextCase = Case.getCaseSuccessor();
1255 NextCase =
Switch->getDefaultDest();
1264 AllSwitchPaths *SwitchPaths;
1270 std::vector<ThreadingPath> TPaths;
1273bool DFAJumpThreading::run(
Function &
F) {
1274 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump threading: " <<
F.getName() <<
"\n");
1276 if (
F.hasOptSize()) {
1277 LLVM_DEBUG(
dbgs() <<
"Skipping due to the 'minsize' attribute\n");
1285 bool MadeChanges =
false;
1293 <<
" is a candidate\n");
1294 MainSwitch
Switch(SI, LI, ORE);
1300 <<
"candidate for jump threading\n");
1303 unfoldSelectInstrs(DT,
Switch.getSelectInsts());
1304 if (!
Switch.getSelectInsts().empty())
1307 AllSwitchPaths SwitchPaths(&Switch, ORE);
1310 if (SwitchPaths.getNumThreadingPaths() > 0) {
1323 if (ThreadableLoops.
size() > 0)
1326 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1327 TransformDFA Transform(&SwitchPaths, DT, AC,
TTI, ORE, EphValues);
1332#ifdef EXPENSIVE_CHECKS
1333 assert(DT->
verify(DominatorTree::VerificationLevel::Full));
1351 if (!DFAJumpThreading(&AC, &DT, &LI, &
TTI, &ORE).
run(
F))
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< 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)
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 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, BasicBlock::iterator InsertBefore)
bool isUnconditional() const
This is the shared class of boolean and integer constants.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
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.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const BasicBlock * getParent() const
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.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Analysis pass that exposes the LoopInfo for a function.
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
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 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
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
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.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
bool hasOneUse() const
Return true if there is exactly one use of this value.
StringRef getName() const
Return a constant reference to the value's name.
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)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
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...