31#define DEBUG_TYPE "predicateinfo"
33using namespace PatternMatch;
37 cl::desc(
"Verify PredicateInfo in legacy printer pass."));
39 "Controls which variables are renamed with predicateinfo");
50 "Only branches and switches should have PHIOnly defs that "
51 "require branch blocks.");
52 return cast<PredicateWithEdge>(
PB)->From;
59 "Not a predicate info type we know how to get a terminator from.");
60 return cast<PredicateWithEdge>(
PB)->From->getTerminator();
65std::pair<BasicBlock *, BasicBlock *> getBlockEdge(
const PredicateBase *
PB) {
67 "Not a predicate info type we know how to get an edge from.");
68 const auto *PEdge = cast<PredicateWithEdge>(
PB);
69 return std::make_pair(PEdge->From, PEdge->To);
100 auto *ArgA = dyn_cast_or_null<Argument>(
A);
101 auto *ArgB = dyn_cast_or_null<Argument>(
B);
107 return ArgA->getArgNo() < ArgB->getArgNo();
108 return cast<Instruction>(
A)->comesBefore(cast<Instruction>(
B));
125 assert((
A.DFSIn !=
B.DFSIn ||
A.DFSOut ==
B.DFSOut) &&
126 "Equal DFS-in numbers imply equal out numbers");
127 bool SameBlock =
A.DFSIn ==
B.DFSIn;
139 return std::tie(
A.DFSIn,
A.LocalNum, isADef) <
140 std::tie(
B.DFSIn,
B.LocalNum, isBDef);
146 if (!VD.
Def && VD.
U) {
147 auto *
PHI = cast<PHINode>(VD.
U->getUser());
148 return std::make_pair(
PHI->getIncomingBlock(*VD.
U),
PHI->getParent());
151 return ::getBlockEdge(VD.
PInfo);
165 "DFS numbers for A should match the ones of the source block");
167 "DFS numbers for B should match the ones of the source block");
168 assert(
A.DFSIn ==
B.DFSIn &&
"Values must be in the same block");
181 assert((!
A.Def || !
A.U) && (!
B.Def || !
B.U) &&
182 "Def and U cannot be set at the same time");
184 return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
199 "No def, no use, and no predicateinfo should not occur");
201 "Middle of block should only occur for assumes");
202 return cast<PredicateAssume>(VD.
PInfo)->AssumeInst->getNextNode();
211 return cast<Instruction>(Def);
212 return cast<Instruction>(U->getUser());
224 auto *ArgA = dyn_cast_or_null<Argument>(ADef);
225 auto *ArgB = dyn_cast_or_null<Argument>(BDef);
283 : PI(PI),
F(
F), DT(DT), AC(AC) {
291bool PredicateInfoBuilder::stackIsInScope(
const ValueDFSStack &Stack,
300 if (Stack.back().EdgeOnly) {
303 auto *
PHI = dyn_cast<PHINode>(VDUse.
U->getUser());
308 if (EdgePred != getBranchBlock(Stack.back().PInfo))
312 return DT.
dominates(getBlockEdge(Stack.back().PInfo), *VDUse.
U);
319void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,
321 while (!
Stack.empty() && !stackIsInScope(Stack, VD))
327void PredicateInfoBuilder::convertUsesToDFSOrdered(
329 for (
auto &U :
Op->uses()) {
330 if (
auto *
I = dyn_cast<Instruction>(
U.getUser())) {
334 if (
auto *PN = dyn_cast<PHINode>(
I)) {
335 IBlock = PN->getIncomingBlock(U);
342 IBlock =
I->getParent();
361 return (isa<Instruction>(V) || isa<Argument>(V)) && !V->hasOneUse();
367 auto *Op0 = Comparison->getOperand(0);
368 auto *Op1 = Comparison->getOperand(1);
379 auto &OperandInfo = getOrCreateValueInfo(
Op);
380 if (OperandInfo.Infos.empty())
382 PI.AllInfos.push_back(
PB);
383 OperandInfo.Infos.push_back(
PB);
388void PredicateInfoBuilder::processAssume(
394 while (!Worklist.
empty()) {
409 if (
auto *Cmp = dyn_cast<CmpInst>(
Cond))
412 for (
Value *V : Values) {
415 addInfoFor(OpsToRename, V, PA);
423void PredicateInfoBuilder::processBranch(
429 for (
BasicBlock *Succ : {FirstBB, SecondBB}) {
430 bool TakenEdge = Succ == FirstBB;
433 if (Succ == BranchBB)
439 while (!Worklist.
empty()) {
455 if (
auto *Cmp = dyn_cast<CmpInst>(
Cond))
458 for (
Value *V : Values) {
462 addInfoFor(OpsToRename, V,
PB);
463 if (!Succ->getSinglePredecessor())
464 EdgeUsesOnly.insert({BranchBB, Succ});
472void PredicateInfoBuilder::processSwitch(
476 if ((!isa<Instruction>(
Op) && !isa<Argument>(
Op)) ||
Op->hasOneUse())
482 ++SwitchEdges[TargetBlock];
485 for (
auto C :
SI->cases()) {
487 if (SwitchEdges.
lookup(TargetBlock) == 1) {
489 Op,
SI->getParent(), TargetBlock,
C.getCaseValue(), SI);
490 addInfoFor(OpsToRename,
Op, PS);
492 EdgeUsesOnly.insert({BranchBB, TargetBlock});
505 if (
auto *BI = dyn_cast<BranchInst>(BranchBB->
getTerminator())) {
511 processBranch(BI, BranchBB, OpsToRename);
512 }
else if (
auto *SI = dyn_cast<SwitchInst>(BranchBB->
getTerminator())) {
513 processSwitch(SI, BranchBB, OpsToRename);
517 if (
auto *
II = dyn_cast_or_null<IntrinsicInst>(Assume))
519 processAssume(
II,
II->getParent(), OpsToRename);
522 renameUses(OpsToRename);
527Value *PredicateInfoBuilder::materializeStack(
unsigned int &Counter,
528 ValueDFSStack &RenameStack,
531 auto RevIter = RenameStack.rbegin();
532 for (; RevIter != RenameStack.rend(); ++RevIter)
536 size_t Start = RevIter - RenameStack.rbegin();
540 for (
auto RenameIter = RenameStack.end() - Start;
541 RenameIter != RenameStack.end(); ++RenameIter) {
543 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
545 auto *ValInfo = Result.PInfo;
546 ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
548 : (RenameStack.end() - Start - 1)->Def;
559 if (isa<PredicateWithEdge>(ValInfo)) {
563 F.
getParent(), Intrinsic::ssa_copy,
Op->getType());
565 PI.CreatedDeclarations.insert(IF);
567 B.CreateCall(IF,
Op,
Op->getName() +
"." +
Twine(Counter++));
568 PI.PredicateMap.insert({
PIC, ValInfo});
571 auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
573 "Should not have gotten here without it being an assume");
579 F.
getParent(), Intrinsic::ssa_copy,
Op->getType());
581 PI.CreatedDeclarations.insert(IF);
583 PI.PredicateMap.insert({
PIC, ValInfo});
587 return RenameStack.back().Def;
612 for (
auto *
Op : OpsToRename) {
614 unsigned Counter = 0;
620 for (
const auto &PossibleCopy :
ValueInfo.Infos) {
627 if (
const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
634 VD.
PInfo = PossibleCopy;
636 }
else if (isa<PredicateWithEdge>(PossibleCopy)) {
640 auto BlockEdge = getBlockEdge(PossibleCopy);
641 if (EdgeUsesOnly.count(BlockEdge)) {
643 auto *DomNode = DT.
getNode(BlockEdge.first);
647 VD.
PInfo = PossibleCopy;
656 auto *DomNode = DT.
getNode(BlockEdge.second);
660 VD.
PInfo = PossibleCopy;
667 convertUsesToDFSOrdered(
Op, OrderedUses);
677 for (
auto &VD : OrderedUses) {
680 bool PossibleCopy = VD.
PInfo !=
nullptr;
681 if (RenameStack.
empty()) {
685 << RenameStack.
back().DFSIn <<
","
686 << RenameStack.
back().DFSOut <<
")\n");
692 bool ShouldPush = (VD.
Def || PossibleCopy);
693 bool OutOfScope = !stackIsInScope(RenameStack, VD);
694 if (OutOfScope || ShouldPush) {
696 popStackUntilDFSScope(RenameStack, VD);
703 if (RenameStack.
empty())
706 if (VD.
Def || PossibleCopy)
709 LLVM_DEBUG(
dbgs() <<
"Skipping execution due to debug counter\n");
718 Result.Def = materializeStack(Counter, RenameStack,
Op);
721 << *VD.
U->get() <<
" in " << *(VD.
U->getUser())
724 "Predicateinfo def should have dominated this use");
730PredicateInfoBuilder::ValueInfo &
731PredicateInfoBuilder::getOrCreateValueInfo(
Value *Operand) {
732 auto OIN = ValueInfoNums.find(Operand);
733 if (OIN == ValueInfoNums.end()) {
737 auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.
size() - 1});
738 assert(InsertResult.second &&
"Value info number already existed?");
739 return ValueInfos[InsertResult.first->second];
741 return ValueInfos[OIN->second];
744const PredicateInfoBuilder::ValueInfo &
745PredicateInfoBuilder::getValueInfo(
Value *Operand)
const {
746 auto OINI = ValueInfoNums.lookup(Operand);
747 assert(OINI != 0 &&
"Operand was not really in the Value Info Numbers");
749 "Value Info Number greater than size of Value Info Table");
750 return ValueInfos[OINI];
766 for (
const auto &F : CreatedDeclarations)
768 CreatedDeclarations.clear();
772 "PredicateInfo consumer did not remove all SSA copies.");
781 bool TrueEdge =
true;
782 if (
auto *PBranch = dyn_cast<PredicateBranch>(
this))
783 TrueEdge = PBranch->TrueEdge;
800 Pred = Cmp->getPredicate();
801 OtherOp = Cmp->getOperand(1);
802 }
else if (Cmp->getOperand(1) ==
RenamedOp) {
803 Pred = Cmp->getSwappedPredicate();
804 OtherOp = Cmp->getOperand(0);
814 return {{Pred, OtherOp}};
833 auto *
II = dyn_cast<IntrinsicInst>(&Inst);
834 if (!PI || !
II ||
II->getIntrinsicID() != Intrinsic::ssa_copy)
837 Inst.replaceAllUsesWith(
II->getOperand(0));
838 Inst.eraseFromParent();
846 OS <<
"PredicateInfo for function: " <<
F.getName() <<
"\n";
847 auto PredInfo = std::make_unique<PredicateInfo>(
F, DT, AC);
869 OS <<
"; Has predicate info\n";
870 if (
const auto *
PB = dyn_cast<PredicateBranch>(PI)) {
871 OS <<
"; branch predicate info { TrueEdge: " <<
PB->TrueEdge
872 <<
" Comparison:" << *
PB->Condition <<
" Edge: [";
873 PB->From->printAsOperand(
OS);
875 PB->To->printAsOperand(
OS);
877 }
else if (
const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
878 OS <<
"; switch predicate info { CaseValue: " << *PS->CaseValue
879 <<
" Switch:" << *PS->Switch <<
" Edge: [";
880 PS->From->printAsOperand(
OS);
882 PS->To->printAsOperand(
OS);
884 }
else if (
const auto *PA = dyn_cast<PredicateAssume>(PI)) {
885 OS <<
"; assume predicate info {"
886 <<
" Comparison:" << *PA->Condition;
888 OS <<
", RenamedOp: ";
889 PI->RenamedOp->printAsOperand(
OS,
false);
897 F.print(
OS, &Writer);
902 F.print(
dbgs(), &Writer);
909 std::make_unique<PredicateInfo>(
F, DT, AC)->verifyPredicateInfo();
Expand Atomic instructions
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
PassInstrumentationCallbacks PIC
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
static cl::opt< bool > VerifyPredicateInfo("verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass."))
static const unsigned MaxCondsPerBranch
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
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.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
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...
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
This class represents an Operation in the Expression.
static bool shouldExecute(unsigned CounterName)
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Implements a dense probed hash-table based set.
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Module * getParent()
Get the module that this global value is contained inside of...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
A wrapper class for inspecting calls to intrinsic functions.
unsigned getNumNamedValues() const
Return the number of global values in the module.
std::optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
An assembly annotator class to print PredicateInfo information in comments.
PredicateInfoAnnotatedWriter(const PredicateInfo *M)
void emitInstructionAnnot(const Instruction *I, formatted_raw_ostream &OS) override
emitInstructionAnnot - This may be implemented to emit a string right before an instruction is emitte...
void emitBasicBlockStartAnnot(const BasicBlock *BB, formatted_raw_ostream &OS) override
emitBasicBlockStartAnnot - This may be implemented to emit a string right after the basic block label...
void buildPredicateInfo()
PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT, AssumptionCache &AC)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Encapsulates PredicateInfo, including all data associated with memory accesses.
void verifyPredicateInfo() const
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
void print(raw_ostream &) const
const PredicateBase * getPredicateInfoFor(const Value *V) const
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.
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.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
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.
user_iterator user_begin()
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
bool match(Val *V, const Pattern &P)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
static bool valueComesBefore(const Value *A, const Value *B)
void stable_sort(R &&Range)
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl< Value * > &CmpOperands)
auto successors(const MachineBasicBlock *BB)
static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool shouldRename(Value *V)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< df_iterator< T > > depth_first(const T &G)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
std::pair< BasicBlock *, BasicBlock * > getBlockEdge(const ValueDFS &VD) const
bool operator()(const ValueDFS &A, const ValueDFS &B) const
bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const
ValueDFS_Compare(DominatorTree &DT)
const Instruction * getDefOrUser(const Value *Def, const Use *U) const
bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const
Value * getMiddleDef(const ValueDFS &VD) const
Struct that holds a reference to a particular GUID in a global value summary.