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) {}
153 for (SelectInstToUnfold SIToUnfold : SelectInsts)
154 Stack.push_back(SIToUnfold);
156 while (!
Stack.empty()) {
157 SelectInstToUnfold SIToUnfold =
Stack.pop_back_val();
159 std::vector<SelectInstToUnfold> NewSIsToUnfold;
160 std::vector<BasicBlock *> NewBBs;
161 unfold(&DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);
164 for (
const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold)
165 Stack.push_back(NewSIToUnfold);
181void createBasicBlockAndSinkSelectInst(
184 BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold,
185 std::vector<BasicBlock *> *NewBBs) {
191 NewBBs->push_back(*NewBlock);
194 NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse));
195 DTU->
applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}});
206 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
207 std::vector<BasicBlock *> *NewBBs) {
209 PHINode *SIUse = SIToUnfold.getUse();
226 if (
SelectInst *SIOp = dyn_cast<SelectInst>(
SI->getTrueValue())) {
227 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
228 "si.unfold.true", &TrueBlock, &TrueBranch,
229 NewSIsToUnfold, NewBBs);
231 if (
SelectInst *SIOp = dyn_cast<SelectInst>(
SI->getFalseValue())) {
232 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
233 "si.unfold.false", &FalseBlock,
234 &FalseBranch, NewSIsToUnfold, NewBBs);
239 if (!TrueBlock && !FalseBlock) {
242 NewBBs->push_back(FalseBlock);
244 DTU->
applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
254 if (TrueBlock && FalseBlock) {
266 Value *OrigValue =
Phi.getIncomingValueForBlock(StartBlock);
267 Phi.addIncoming(OrigValue, TrueBlock);
268 Phi.addIncoming(OrigValue, FalseBlock);
273 Phi.removeIncomingValue(StartBlock,
false);
277 Value *SIOp1 =
SI->getTrueValue();
278 Value *SIOp2 =
SI->getFalseValue();
282 NewBlock = FalseBlock;
287 NewBlock = TrueBlock;
300 for (
auto II = EndBlock->
begin();
PHINode *Phi = dyn_cast<PHINode>(II);
303 Phi->addIncoming(
Phi->getIncomingValueForBlock(StartBlock), NewBlock);
309 {DominatorTree::Insert, StartBlock, FT}});
314 L->addBasicBlockToLoop(NewBB, *LI);
318 assert(
SI->use_empty() &&
"Select must be dead now");
319 SI->eraseFromParent();
327typedef std::deque<BasicBlock *> PathType;
328typedef std::vector<PathType> PathsType;
330typedef std::vector<ClonedBlock> CloneList;
359struct ThreadingPath {
361 APInt getExitValue()
const {
return ExitVal; }
363 ExitVal =
V->getValue();
366 bool isExitValueSet()
const {
return IsExitValSet; }
369 const BasicBlock *getDeterminatorBB()
const {
return DBB; }
370 void setDeterminator(
const BasicBlock *BB) { DBB = BB; }
373 const PathType &getPath()
const {
return Path; }
374 void setPath(
const PathType &NewPath) {
Path = NewPath; }
377 OS <<
Path <<
" [ " << ExitVal <<
", " << DBB->getName() <<
" ]";
384 bool IsExitValSet =
false;
402 <<
"Switch instruction is not predictable.";
407 virtual ~MainSwitch() =
default;
420 std::deque<std::pair<Value *, BasicBlock *>> Q;
424 Value *SICond =
SI->getCondition();
426 if (!isa<PHINode>(SICond))
434 addToQueue(SICond,
nullptr, Q, SeenValues);
437 Value *Current = Q.front().first;
441 if (
auto *Phi = dyn_cast<PHINode>(Current)) {
444 addToQueue(
Incoming, IncomingBB, Q, SeenValues);
447 }
else if (
SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
448 if (!isValidSelectInst(SelI))
450 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);
451 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);
453 if (
auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
454 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
455 }
else if (isa<Constant>(Current)) {
472 <<
"\tExiting early due to unpredictability heuristic.\n");
484 std::deque<std::pair<Value *, BasicBlock *>> &Q,
488 Q.push_back({Val, BB});
493 if (!
SI->hasOneUse())
498 if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
510 PHINode *PHIUser = dyn_cast<PHINode>(SIUse);
516 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
531struct AllSwitchPaths {
537 std::vector<ThreadingPath> &getThreadingPaths() {
return TPaths; }
538 unsigned getNumThreadingPaths() {
return TPaths.size(); }
540 BasicBlock *getSwitchBlock() {
return SwitchBlock; }
543 VisitedBlocks Visited;
544 PathsType LoopPaths = paths(SwitchBlock, Visited, 1);
545 StateDefMap StateDef = getStateDefMap(LoopPaths);
547 if (StateDef.empty()) {
551 <<
"Switch instruction is not predictable.";
556 for (
const PathType &Path : LoopPaths) {
561 if (StateDef.contains(BB)) {
562 const PHINode *
Phi = dyn_cast<PHINode>(StateDef[BB]);
563 assert(Phi &&
"Expected a state-defining instr to be a phi node.");
565 const Value *
V =
Phi->getIncomingValueForBlock(PrevBB);
566 if (
const ConstantInt *
C = dyn_cast<const ConstantInt>(V)) {
567 TPath.setExitValue(
C);
568 TPath.setDeterminator(BB);
574 if (TPath.isExitValueSet() && BB ==
Path.front())
580 if (TPath.isExitValueSet() && isSupported(TPath))
581 TPaths.push_back(TPath);
590 PathsType paths(
BasicBlock *BB, VisitedBlocks &Visited,
591 unsigned PathDepth)
const {
599 <<
"Exploration stopped after visiting MaxPathLength="
617 if (!Successors.
insert(Succ).second)
621 if (Succ == SwitchBlock) {
627 if (Visited.contains(Succ))
630 PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
631 for (
const PathType &Path : SuccPaths) {
632 PathType NewPath(Path);
633 NewPath.push_front(BB);
634 Res.push_back(NewPath);
651 StateDefMap getStateDefMap(
const PathsType &LoopPaths)
const {
656 for (
const PathType &Path : LoopPaths) {
663 assert(isa<PHINode>(FirstDef) &&
"The first definition must be a phi.");
666 Stack.push_back(dyn_cast<PHINode>(FirstDef));
669 while (!
Stack.empty()) {
673 SeenValues.
insert(CurPhi);
677 bool IsOutsideLoops = LoopBBs.
count(IncomingBB) == 0;
685 return StateDefMap();
712 bool isSupported(
const ThreadingPath &TPath) {
720 const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
723 SwitchCondUseBB == TPath.getPath().front() &&
724 "The first BB in a threading path should have the switch instruction");
725 if (SwitchCondUseBB != TPath.getPath().front())
729 PathType
Path = TPath.getPath();
730 auto ItDet =
llvm::find(Path, DeterminatorBB);
731 std::rotate(
Path.begin(), ItDet,
Path.end());
733 bool IsDetBBSeen =
false;
734 bool IsDefBBSeen =
false;
735 bool IsUseBBSeen =
false;
737 if (BB == DeterminatorBB)
739 if (BB == SwitchCondDefBB)
741 if (BB == SwitchCondUseBB)
743 if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
753 std::vector<ThreadingPath> TPaths;
762 : SwitchPaths(SwitchPaths), DT(DT), AC(AC),
TTI(
TTI), ORE(ORE),
763 EphValues(EphValues) {}
766 if (isLegalAndProfitableToTransform()) {
767 createAllExitPaths();
777 bool isLegalAndProfitableToTransform() {
782 if (
Switch->getNumSuccessors() <= 1)
787 DuplicateBlockMap DuplicateMap;
789 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
790 PathType PathBBs = TPath.getPath();
791 APInt NextState = TPath.getExitValue();
792 const BasicBlock *Determinator = TPath.getDeterminatorBB();
795 BasicBlock *BB = SwitchPaths->getSwitchBlock();
796 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
798 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
799 DuplicateMap[BB].push_back({BB, NextState});
804 if (PathBBs.front() == Determinator)
809 auto DetIt =
llvm::find(PathBBs, Determinator);
810 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
812 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
815 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
816 DuplicateMap[BB].push_back({BB, NextState});
820 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
821 <<
"non-duplicatable instructions.\n");
825 <<
"Contains non-duplicatable instructions.";
831 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
832 <<
"convergent instructions.\n");
835 <<
"Contains convergent instructions.";
840 if (!
Metrics.NumInsts.isValid()) {
841 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
842 <<
"instructions with invalid cost.\n");
845 <<
"Contains instructions with invalid cost.";
853 unsigned JumpTableSize = 0;
856 if (JumpTableSize == 0) {
860 unsigned CondBranches =
862 assert(CondBranches > 0 &&
863 "The threaded switch must have multiple branches");
864 DuplicationCost =
Metrics.NumInsts / CondBranches;
872 DuplicationCost =
Metrics.NumInsts / JumpTableSize;
875 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump Threading: Cost to jump thread block "
876 << SwitchPaths->getSwitchBlock()->getName()
877 <<
" is: " << DuplicationCost <<
"\n\n");
880 LLVM_DEBUG(
dbgs() <<
"Not jump threading, duplication cost exceeds the "
881 <<
"cost threshold.\n");
884 <<
"Duplication cost exceeds the cost threshold (cost="
885 <<
ore::NV(
"Cost", DuplicationCost)
893 <<
"Switch statement jump-threaded.";
900 void createAllExitPaths() {
904 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
905 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
907 PathType NewPath(TPath.getPath());
908 NewPath.push_back(SwitchBlock);
909 TPath.setPath(NewPath);
913 DuplicateBlockMap DuplicateMap;
920 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
921 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
927 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
928 updateLastSuccessor(TPath, DuplicateMap, &DTU);
944 void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
945 DuplicateBlockMap &DuplicateMap,
950 PathType PathBBs =
Path.getPath();
953 if (PathBBs.front() == Determinator)
956 auto DetIt =
llvm::find(PathBBs, Determinator);
959 BasicBlock *PrevBB = PathBBs.
size() == 1 ? *DetIt : *std::prev(DetIt);
960 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
966 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
968 updatePredecessor(PrevBB, BB, NextBB, DTU);
974 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
975 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
976 DuplicateMap[BB].push_back({NewBB, NextState});
977 BlocksToClean.
insert(NewBB);
988 void updateSSA(DefMap &NewDefs) {
992 for (
const auto &KV : NewDefs) {
995 std::vector<Instruction *> Cloned = KV.second;
999 for (
Use &U :
I->uses()) {
1002 if (UserPN->getIncomingBlock(U) == BB)
1004 }
else if (
User->getParent() == BB) {
1013 if (UsesToRename.
empty())
1021 unsigned VarNum = SSAUpdate.
AddVariable(
I->getName(),
I->getType());
1026 while (!UsesToRename.
empty())
1041 const APInt &NextState,
1042 DuplicateBlockMap &DuplicateMap,
1056 if (isa<PHINode>(&
I))
1061 AC->registerAssumption(II);
1064 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1065 updatePredecessor(PrevBB, BB, NewBB, DTU);
1066 updateDefMap(NewDefs, VMap);
1071 if (SuccSet.
insert(SuccBB).second)
1072 DTU->
applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1084 DuplicateBlockMap &DuplicateMap) {
1085 std::vector<BasicBlock *> BlocksToUpdate;
1089 if (BB == SwitchPaths->getSwitchBlock()) {
1091 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1092 BlocksToUpdate.push_back(NextCase);
1093 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1095 BlocksToUpdate.push_back(ClonedSucc);
1100 BlocksToUpdate.push_back(Succ);
1105 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1107 BlocksToUpdate.push_back(ClonedSucc);
1115 for (
auto II = Succ->begin();
PHINode *Phi = dyn_cast<PHINode>(II);
1125 Phi->addIncoming(ClonedVal, ClonedBB);
1139 if (!isPredecessor(OldBB, PrevBB))
1149 DTU->
applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1150 {DominatorTree::Insert, PrevBB, NewBB}});
1159 for (
auto Entry : VMap) {
1161 dyn_cast<Instruction>(
const_cast<Value *
>(Entry.first));
1162 if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1163 isa<SwitchInst>(Inst)) {
1167 Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1171 NewDefsVector.
push_back({Inst, Cloned});
1175 sort(NewDefsVector, [](
const auto &LHS,
const auto &RHS) {
1176 if (
LHS.first ==
RHS.first)
1177 return LHS.second->comesBefore(
RHS.second);
1178 return LHS.first->comesBefore(
RHS.first);
1181 for (
const auto &KV : NewDefsVector)
1182 NewDefs[KV.first].push_back(KV.second);
1190 void updateLastSuccessor(ThreadingPath &TPath,
1191 DuplicateBlockMap &DuplicateMap,
1193 APInt NextState = TPath.getExitValue();
1195 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1202 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1204 std::vector<DominatorTree::UpdateType> DTUpdates;
1207 if (Succ != NextCase && SuccSet.
insert(Succ).second)
1208 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1211 Switch->eraseFromParent();
1222 std::vector<PHINode *> PhiToRemove;
1223 for (
auto II = BB->
begin();
PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1224 PhiToRemove.push_back(Phi);
1226 for (
PHINode *PN : PhiToRemove) {
1228 PN->eraseFromParent();
1234 for (
auto II = BB->
begin();
PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1235 std::vector<BasicBlock *> BlocksToRemove;
1237 if (!isPredecessor(BB, IncomingBB))
1238 BlocksToRemove.push_back(IncomingBB);
1241 Phi->removeIncomingValue(BB);
1248 DuplicateBlockMap &DuplicateMap) {
1249 CloneList ClonedBBs = DuplicateMap[BB];
1253 auto It =
llvm::find_if(ClonedBBs, [NextState](
const ClonedBlock &
C) {
1254 return C.State == NextState;
1256 return It != ClonedBBs.end() ? (*It).BB :
nullptr;
1263 for (
auto Case :
Switch->cases()) {
1264 if (Case.getCaseValue()->getValue() == NextState) {
1265 NextCase = Case.getCaseSuccessor();
1270 NextCase =
Switch->getDefaultDest();
1279 AllSwitchPaths *SwitchPaths;
1285 std::vector<ThreadingPath> TPaths;
1288bool DFAJumpThreading::run(
Function &
F) {
1289 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump threading: " <<
F.getName() <<
"\n");
1291 if (
F.hasOptSize()) {
1292 LLVM_DEBUG(
dbgs() <<
"Skipping due to the 'minsize' attribute\n");
1300 bool MadeChanges =
false;
1301 LoopInfoBroken =
false;
1309 <<
" is a candidate\n");
1310 MainSwitch
Switch(SI, LI, ORE);
1316 <<
"candidate for jump threading\n");
1319 unfoldSelectInstrs(DT,
Switch.getSelectInsts());
1320 if (!
Switch.getSelectInsts().empty())
1323 AllSwitchPaths SwitchPaths(&Switch, ORE, LI);
1326 if (SwitchPaths.getNumThreadingPaths() > 0) {
1344 if (ThreadableLoops.
size() > 0)
1347 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1348 TransformDFA Transform(&SwitchPaths, DT, AC,
TTI, ORE, EphValues);
1351 LoopInfoBroken =
true;
1354#ifdef EXPENSIVE_CHECKS
1355 assert(DT->
verify(DominatorTree::VerificationLevel::Full));
1372 DFAJumpThreading ThreadImpl(&AC, &DT, &LI, &
TTI, &ORE);
1373 if (!ThreadImpl.run(
F))
1378 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< 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.
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
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...