84#ifdef EXPENSIVE_CHECKS
90#define DEBUG_TYPE "dfa-jump-threading"
92STATISTIC(NumTransforms,
"Number of transformations done");
94STATISTIC(NumPaths,
"Number of individual paths threaded");
98 cl::desc(
"View the CFG before DFA Jump Threading"),
102 "dfa-max-path-length",
103 cl::desc(
"Max number of blocks searched to find a threading path"),
108 cl::desc(
"Max number of paths enumerated around a switch"),
113 cl::desc(
"Maximum cost accepted for the transformation"),
118class SelectInstToUnfold {
126 PHINode *getUse() {
return SIUse; }
128 explicit operator bool()
const {
return SI && SIUse; }
132 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
133 std::vector<BasicBlock *> *NewBBs);
135class DFAJumpThreading {
139 : AC(AC), DT(DT),
TTI(
TTI), ORE(ORE) {}
149 for (SelectInstToUnfold SIToUnfold : SelectInsts)
150 Stack.push_back(SIToUnfold);
152 while (!
Stack.empty()) {
153 SelectInstToUnfold SIToUnfold =
Stack.pop_back_val();
155 std::vector<SelectInstToUnfold> NewSIsToUnfold;
156 std::vector<BasicBlock *> NewBBs;
157 unfold(&DTU, SIToUnfold, &NewSIsToUnfold, &NewBBs);
160 for (
const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold)
161 Stack.push_back(NewSIToUnfold);
176void createBasicBlockAndSinkSelectInst(
179 BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold,
180 std::vector<BasicBlock *> *NewBBs) {
186 NewBBs->push_back(*NewBlock);
189 NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse));
190 DTU->
applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}});
201 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
202 std::vector<BasicBlock *> *NewBBs) {
204 PHINode *SIUse = SIToUnfold.getUse();
221 if (
SelectInst *SIOp = dyn_cast<SelectInst>(
SI->getTrueValue())) {
222 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
223 "si.unfold.true", &TrueBlock, &TrueBranch,
224 NewSIsToUnfold, NewBBs);
226 if (
SelectInst *SIOp = dyn_cast<SelectInst>(
SI->getFalseValue())) {
227 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
228 "si.unfold.false", &FalseBlock,
229 &FalseBranch, NewSIsToUnfold, NewBBs);
234 if (!TrueBlock && !FalseBlock) {
237 NewBBs->push_back(FalseBlock);
239 DTU->
applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
249 if (TrueBlock && FalseBlock) {
262 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), TrueBlock);
263 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), FalseBlock);
268 Value *SIOp1 =
SI->getTrueValue();
269 Value *SIOp2 =
SI->getFalseValue();
273 NewBlock = FalseBlock;
278 NewBlock = TrueBlock;
291 for (
auto II = EndBlock->
begin();
PHINode *Phi = dyn_cast<PHINode>(II);
294 Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), NewBlock);
300 {DominatorTree::Insert, StartBlock, FT}});
303 SI->eraseFromParent();
311typedef std::deque<BasicBlock *> PathType;
312typedef std::vector<PathType> PathsType;
314typedef std::vector<ClonedBlock> CloneList;
343struct ThreadingPath {
345 uint64_t getExitValue()
const {
return ExitVal; }
347 ExitVal =
V->getZExtValue();
350 bool isExitValueSet()
const {
return IsExitValSet; }
353 const BasicBlock *getDeterminatorBB()
const {
return DBB; }
354 void setDeterminator(
const BasicBlock *BB) { DBB = BB; }
357 const PathType &getPath()
const {
return Path; }
358 void setPath(
const PathType &NewPath) {
Path = NewPath; }
361 OS <<
Path <<
" [ " << ExitVal <<
", " << DBB->getName() <<
" ]";
368 bool IsExitValSet =
false;
385 <<
"Switch instruction is not predictable.";
390 virtual ~MainSwitch() =
default;
392 SwitchInst *getInstr()
const {
return Instr; }
403 std::deque<Value *> Q;
407 Value *SICond =
SI->getCondition();
409 if (!isa<PHINode>(SICond))
412 addToQueue(SICond, Q, SeenValues);
415 Value *Current = Q.front();
418 if (
auto *Phi = dyn_cast<PHINode>(Current)) {
419 for (
Value *Incoming : Phi->incoming_values()) {
420 addToQueue(Incoming, Q, SeenValues);
423 }
else if (
SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
424 if (!isValidSelectInst(SelI))
426 addToQueue(SelI->getTrueValue(), Q, SeenValues);
427 addToQueue(SelI->getFalseValue(), Q, SeenValues);
429 if (
auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
430 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
431 }
else if (isa<Constant>(Current)) {
447 void addToQueue(
Value *Val, std::deque<Value *> &Q,
456 if (!
SI->hasOneUse())
461 if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
472 if (isa<PHINode>(SIUse) &&
478 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
492struct AllSwitchPaths {
497 std::vector<ThreadingPath> &getThreadingPaths() {
return TPaths; }
498 unsigned getNumThreadingPaths() {
return TPaths.size(); }
500 BasicBlock *getSwitchBlock() {
return SwitchBlock; }
503 VisitedBlocks Visited;
504 PathsType LoopPaths = paths(SwitchBlock, Visited, 1);
505 StateDefMap StateDef = getStateDefMap(LoopPaths);
507 if (StateDef.empty()) {
511 <<
"Switch instruction is not predictable.";
516 for (PathType Path : LoopPaths) {
521 if (StateDef.count(BB) != 0) {
522 const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]);
523 assert(Phi &&
"Expected a state-defining instr to be a phi node.");
526 if (
const ConstantInt *
C = dyn_cast<const ConstantInt>(V)) {
527 TPath.setExitValue(
C);
528 TPath.setDeterminator(BB);
534 if (TPath.isExitValueSet() && BB ==
Path.front())
540 if (TPath.isExitValueSet() && isSupported(TPath))
541 TPaths.push_back(TPath);
550 PathsType paths(
BasicBlock *BB, VisitedBlocks &Visited,
551 unsigned PathDepth)
const {
559 <<
"Exploration stopped after visiting MaxPathLength="
571 if (!Successors.
insert(Succ).second)
575 if (Succ == SwitchBlock) {
581 if (Visited.contains(Succ))
584 PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
585 for (PathType Path : SuccPaths) {
586 PathType NewPath(Path);
587 NewPath.push_front(BB);
588 Res.push_back(NewPath);
605 StateDefMap getStateDefMap(
const PathsType &LoopPaths)
const {
610 for (
const PathType &Path : LoopPaths) {
617 assert(isa<PHINode>(FirstDef) &&
"The first definition must be a phi.");
620 Stack.push_back(dyn_cast<PHINode>(FirstDef));
623 while (!
Stack.empty()) {
627 SeenValues.
insert(CurPhi);
631 bool IsOutsideLoops = LoopBBs.
count(IncomingBB) == 0;
632 if (Incoming == FirstDef || isa<ConstantInt>(Incoming) ||
633 SeenValues.
contains(Incoming) || IsOutsideLoops) {
638 if (!isa<PHINode>(Incoming))
639 return StateDefMap();
641 Stack.push_back(cast<PHINode>(Incoming));
666 bool isSupported(
const ThreadingPath &TPath) {
674 const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
677 SwitchCondUseBB == TPath.getPath().front() &&
678 "The first BB in a threading path should have the switch instruction");
679 if (SwitchCondUseBB != TPath.getPath().front())
683 PathType
Path = TPath.getPath();
684 auto ItDet =
llvm::find(Path, DeterminatorBB);
685 std::rotate(
Path.begin(), ItDet,
Path.end());
687 bool IsDetBBSeen =
false;
688 bool IsDefBBSeen =
false;
689 bool IsUseBBSeen =
false;
691 if (BB == DeterminatorBB)
693 if (BB == SwitchCondDefBB)
695 if (BB == SwitchCondUseBB)
697 if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
707 std::vector<ThreadingPath> TPaths;
715 : SwitchPaths(SwitchPaths), DT(DT), AC(AC),
TTI(
TTI), ORE(ORE),
716 EphValues(EphValues) {}
719 if (isLegalAndProfitableToTransform()) {
720 createAllExitPaths();
730 bool isLegalAndProfitableToTransform() {
736 DuplicateBlockMap DuplicateMap;
738 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
739 PathType PathBBs = TPath.getPath();
740 uint64_t NextState = TPath.getExitValue();
741 const BasicBlock *Determinator = TPath.getDeterminatorBB();
744 BasicBlock *BB = SwitchPaths->getSwitchBlock();
745 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
747 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
748 DuplicateMap[BB].push_back({BB, NextState});
753 if (PathBBs.front() == Determinator)
758 auto DetIt =
llvm::find(PathBBs, Determinator);
759 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
761 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
764 Metrics.analyzeBasicBlock(BB, *
TTI, EphValues);
765 DuplicateMap[BB].push_back({BB, NextState});
769 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
770 <<
"non-duplicatable instructions.\n");
774 <<
"Contains non-duplicatable instructions.";
780 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
781 <<
"convergent instructions.\n");
784 <<
"Contains convergent instructions.";
789 if (!
Metrics.NumInsts.isValid()) {
790 LLVM_DEBUG(
dbgs() <<
"DFA Jump Threading: Not jump threading, contains "
791 <<
"instructions with invalid cost.\n");
794 <<
"Contains instructions with invalid cost.";
802 unsigned JumpTableSize = 0;
805 if (JumpTableSize == 0) {
809 unsigned CondBranches =
811 DuplicationCost =
Metrics.NumInsts / CondBranches;
819 DuplicationCost =
Metrics.NumInsts / JumpTableSize;
822 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump Threading: Cost to jump thread block "
823 << SwitchPaths->getSwitchBlock()->getName()
824 <<
" is: " << DuplicationCost <<
"\n\n");
827 LLVM_DEBUG(
dbgs() <<
"Not jump threading, duplication cost exceeds the "
828 <<
"cost threshold.\n");
831 <<
"Duplication cost exceeds the cost threshold (cost="
832 <<
ore::NV(
"Cost", DuplicationCost)
840 <<
"Switch statement jump-threaded.";
847 void createAllExitPaths() {
851 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
852 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
854 PathType NewPath(TPath.getPath());
855 NewPath.push_back(SwitchBlock);
856 TPath.setPath(NewPath);
860 DuplicateBlockMap DuplicateMap;
867 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
868 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
874 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
875 updateLastSuccessor(TPath, DuplicateMap, &DTU);
891 void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
892 DuplicateBlockMap &DuplicateMap,
897 PathType PathBBs =
Path.getPath();
900 if (PathBBs.front() == Determinator)
903 auto DetIt =
llvm::find(PathBBs, Determinator);
904 auto Prev = std::prev(DetIt);
906 for (
auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
912 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
914 updatePredecessor(PrevBB, BB, NextBB, DTU);
920 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
921 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
922 DuplicateMap[BB].push_back({NewBB, NextState});
923 BlocksToClean.
insert(NewBB);
934 void updateSSA(DefMap &NewDefs) {
938 for (
auto KV : NewDefs) {
941 std::vector<Instruction *> Cloned = KV.second;
945 for (
Use &U :
I->uses()) {
948 if (UserPN->getIncomingBlock(U) == BB)
950 }
else if (
User->getParent() == BB) {
959 if (UsesToRename.
empty())
967 unsigned VarNum = SSAUpdate.
AddVariable(
I->getName(),
I->getType());
972 while (!UsesToRename.
empty())
988 DuplicateBlockMap &DuplicateMap,
993 BB, VMap,
".jt" + std::to_string(NextState), BB->
getParent());
1001 if (isa<PHINode>(&
I))
1006 AC->registerAssumption(II);
1009 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1010 updatePredecessor(PrevBB, BB, NewBB, DTU);
1011 updateDefMap(NewDefs, VMap);
1016 if (SuccSet.
insert(SuccBB).second)
1017 DTU->
applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1029 DuplicateBlockMap &DuplicateMap) {
1030 std::vector<BasicBlock *> BlocksToUpdate;
1034 if (BB == SwitchPaths->getSwitchBlock()) {
1036 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1037 BlocksToUpdate.push_back(NextCase);
1038 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1040 BlocksToUpdate.push_back(ClonedSucc);
1045 BlocksToUpdate.push_back(Succ);
1050 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1052 BlocksToUpdate.push_back(ClonedSucc);
1060 for (
auto II = Succ->begin();
PHINode *Phi = dyn_cast<PHINode>(II);
1064 if (isa<Constant>(Incoming)) {
1068 Value *ClonedVal = VMap[Incoming];
1084 if (!isPredecessor(OldBB, PrevBB))
1094 DTU->
applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1095 {DominatorTree::Insert, PrevBB, NewBB}});
1104 for (
auto Entry : VMap) {
1106 dyn_cast<Instruction>(
const_cast<Value *
>(Entry.first));
1107 if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1108 isa<SwitchInst>(Inst)) {
1112 Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1116 NewDefsVector.
push_back({Inst, Cloned});
1120 sort(NewDefsVector, [](
const auto &LHS,
const auto &RHS) {
1121 if (
LHS.first ==
RHS.first)
1122 return LHS.second->comesBefore(
RHS.second);
1123 return LHS.first->comesBefore(
RHS.first);
1126 for (
const auto &KV : NewDefsVector)
1127 NewDefs[KV.first].push_back(KV.second);
1135 void updateLastSuccessor(ThreadingPath &TPath,
1136 DuplicateBlockMap &DuplicateMap,
1138 uint64_t NextState = TPath.getExitValue();
1140 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1147 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1149 std::vector<DominatorTree::UpdateType> DTUpdates;
1152 if (Succ != NextCase && SuccSet.
insert(Succ).second)
1153 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1156 Switch->eraseFromParent();
1167 std::vector<PHINode *> PhiToRemove;
1168 for (
auto II = BB->
begin();
PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1169 PhiToRemove.push_back(Phi);
1171 for (
PHINode *PN : PhiToRemove) {
1173 PN->eraseFromParent();
1179 for (
auto II = BB->
begin();
PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1180 std::vector<BasicBlock *> BlocksToRemove;
1182 if (!isPredecessor(BB, IncomingBB))
1183 BlocksToRemove.push_back(IncomingBB);
1193 DuplicateBlockMap &DuplicateMap) {
1194 CloneList ClonedBBs = DuplicateMap[BB];
1198 auto It =
llvm::find_if(ClonedBBs, [NextState](
const ClonedBlock &
C) {
1199 return C.State == NextState;
1201 return It != ClonedBBs.end() ? (*It).BB :
nullptr;
1208 for (
auto Case :
Switch->cases()) {
1209 if (Case.getCaseValue()->getZExtValue() == NextState) {
1210 NextCase = Case.getCaseSuccessor();
1215 NextCase =
Switch->getDefaultDest();
1224 AllSwitchPaths *SwitchPaths;
1230 std::vector<ThreadingPath> TPaths;
1233bool DFAJumpThreading::run(
Function &
F) {
1234 LLVM_DEBUG(
dbgs() <<
"\nDFA Jump threading: " <<
F.getName() <<
"\n");
1236 if (
F.hasOptSize()) {
1237 LLVM_DEBUG(
dbgs() <<
"Skipping due to the 'minsize' attribute\n");
1245 bool MadeChanges =
false;
1253 <<
" is a candidate\n");
1254 MainSwitch
Switch(SI, ORE);
1260 <<
"candidate for jump threading\n");
1263 unfoldSelectInstrs(DT,
Switch.getSelectInsts());
1264 if (!
Switch.getSelectInsts().empty())
1267 AllSwitchPaths SwitchPaths(&Switch, ORE);
1270 if (SwitchPaths.getNumThreadingPaths() > 0) {
1283 if (ThreadableLoops.
size() > 0)
1286 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1287 TransformDFA Transform(&SwitchPaths, DT, AC,
TTI, ORE, EphValues);
1292#ifdef EXPENSIVE_CHECKS
1293 assert(DT->
verify(DominatorTree::VerificationLevel::Full));
1310 if (!DFAJumpThreading(&AC, &DT, &
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< 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
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.
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 BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
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, Instruction *InsertBefore=nullptr)
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
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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 ...
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 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
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.