Go to the documentation of this file.
32 #define DEBUG_TYPE "predicateinfo"
34 using namespace PatternMatch;
37 "PredicateInfo Printer",
false,
false)
57 "Only branches and switches should have PHIOnly defs that "
58 "require branch blocks.");
59 return cast<PredicateWithEdge>(
PB)->From;
66 "Not a predicate info type we know how to get a terminator from.");
67 return cast<PredicateWithEdge>(
PB)->From->getTerminator();
72 std::pair<BasicBlock *, BasicBlock *> getBlockEdge(
const PredicateBase *
PB) {
74 "Not a predicate info type we know how to get an edge from.");
75 const auto *PEdge = cast<PredicateWithEdge>(
PB);
76 return std::make_pair(PEdge->From, PEdge->To);
102 bool EdgeOnly =
false;
107 auto *ArgA = dyn_cast_or_null<Argument>(A);
108 auto *ArgB = dyn_cast_or_null<Argument>(
B);
114 return ArgA->getArgNo() < ArgB->getArgNo();
115 return cast<Instruction>(A)->comesBefore(cast<Instruction>(
B));
132 assert((A.DFSIn !=
B.DFSIn || A.DFSOut ==
B.DFSOut) &&
133 "Equal DFS-in numbers imply equal out numbers");
134 bool SameBlock = A.DFSIn ==
B.DFSIn;
141 return comparePHIRelated(A,
B);
146 return std::tie(A.DFSIn, A.LocalNum, isADef) <
147 std::tie(
B.DFSIn,
B.LocalNum, isBDef);
148 return localComesBefore(A,
B);
153 if (!VD.
Def && VD.
U) {
154 auto *PHI = cast<PHINode>(VD.
U->getUser());
155 return std::make_pair(PHI->getIncomingBlock(*VD.
U), PHI->getParent());
158 return ::getBlockEdge(VD.
PInfo);
164 std::tie(ASrc, ADest) = getBlockEdge(A);
165 std::tie(BSrc, BDest) = getBlockEdge(
B);
172 "DFS numbers for A should match the ones of the source block");
174 "DFS numbers for B should match the ones of the source block");
175 assert(A.DFSIn ==
B.DFSIn &&
"Values must be in the same block");
188 assert((!A.Def || !A.U) && (!
B.Def || !
B.U) &&
189 "Def and U cannot be set at the same time");
191 return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
206 "No def, no use, and no predicateinfo should not occur");
208 "Middle of block should only occur for assumes");
209 return cast<PredicateAssume>(VD.
PInfo)->AssumeInst->getNextNode();
218 return cast<Instruction>(
Def);
219 return cast<Instruction>(U->getUser());
225 auto *ADef = getMiddleDef(A);
226 auto *BDef = getMiddleDef(
B);
231 auto *ArgA = dyn_cast_or_null<Argument>(ADef);
232 auto *ArgB = dyn_cast_or_null<Argument>(BDef);
237 auto *AInst = getDefOrUser(ADef, A.U);
238 auto *BInst = getDefOrUser(BDef,
B.U);
268 ValueInfo &getOrCreateValueInfo(
Value *);
269 const ValueInfo &getValueInfo(
Value *)
const;
290 : PI(PI),
F(
F), DT(DT), AC(AC) {
295 void buildPredicateInfo();
298 bool PredicateInfoBuilder::stackIsInScope(
const ValueDFSStack &Stack,
307 if (Stack.back().EdgeOnly) {
310 auto *PHI = dyn_cast<PHINode>(VDUse.
U->getUser());
314 BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.
U);
315 if (EdgePred != getBranchBlock(Stack.back().PInfo))
319 return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.
U);
326 void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,
328 while (!
Stack.empty() && !stackIsInScope(Stack, VD))
334 void PredicateInfoBuilder::convertUsesToDFSOrdered(
336 for (
auto &U :
Op->uses()) {
337 if (
auto *
I = dyn_cast<Instruction>(U.getUser())) {
341 if (
auto *PN = dyn_cast<PHINode>(
I)) {
342 IBlock = PN->getIncomingBlock(U);
349 IBlock =
I->getParent();
359 DFSOrderedSet.push_back(VD);
368 return (isa<Instruction>(V) || isa<Argument>(V)) && !V->
hasOneUse();
379 CmpOperands.push_back(Op0);
380 CmpOperands.push_back(Op1);
386 auto &OperandInfo = getOrCreateValueInfo(
Op);
387 if (OperandInfo.Infos.empty())
388 OpsToRename.push_back(
Op);
389 PI.AllInfos.push_back(
PB);
390 OperandInfo.Infos.push_back(
PB);
395 void PredicateInfoBuilder::processAssume(
401 while (!Worklist.empty()) {
410 Worklist.push_back(Op1);
411 Worklist.push_back(Op0);
415 Values.push_back(
Cond);
416 if (
auto *Cmp = dyn_cast<CmpInst>(
Cond))
419 for (
Value *V : Values) {
422 addInfoFor(OpsToRename, V, PA);
430 void PredicateInfoBuilder::processBranch(
436 for (
BasicBlock *Succ : {FirstBB, SecondBB}) {
437 bool TakenEdge = Succ == FirstBB;
440 if (Succ == BranchBB)
446 while (!Worklist.empty()) {
456 Worklist.push_back(Op1);
457 Worklist.push_back(Op0);
461 Values.push_back(
Cond);
462 if (
auto *Cmp = dyn_cast<CmpInst>(
Cond))
465 for (
Value *V : Values) {
469 addInfoFor(OpsToRename, V,
PB);
470 if (!Succ->getSinglePredecessor())
471 EdgeUsesOnly.insert({BranchBB, Succ});
479 void PredicateInfoBuilder::processSwitch(
483 if ((!isa<Instruction>(
Op) && !isa<Argument>(
Op)) ||
Op->hasOneUse())
488 for (
unsigned i = 0,
e =
SI->getNumSuccessors();
i !=
e; ++
i) {
490 ++SwitchEdges[TargetBlock];
494 for (
auto C :
SI->cases()) {
496 if (SwitchEdges.
lookup(TargetBlock) == 1) {
498 Op,
SI->getParent(), TargetBlock,
C.getCaseValue(),
SI);
499 addInfoFor(OpsToRename,
Op, PS);
501 EdgeUsesOnly.insert({BranchBB, TargetBlock});
508 DT.updateDFSNumbers();
514 if (
auto *BI = dyn_cast<BranchInst>(BranchBB->
getTerminator())) {
520 processBranch(BI, BranchBB, OpsToRename);
521 }
else if (
auto *
SI = dyn_cast<SwitchInst>(BranchBB->
getTerminator())) {
525 for (
auto &Assume : AC.assumptions()) {
526 if (
auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
527 if (DT.isReachableFromEntry(II->
getParent()))
528 processAssume(II, II->
getParent(), OpsToRename);
531 renameUses(OpsToRename);
536 Value *PredicateInfoBuilder::materializeStack(
unsigned int &Counter,
537 ValueDFSStack &RenameStack,
540 auto RevIter = RenameStack.rbegin();
541 for (; RevIter != RenameStack.rend(); ++RevIter)
545 size_t Start = RevIter - RenameStack.rbegin();
549 for (
auto RenameIter = RenameStack.end() - Start;
550 RenameIter != RenameStack.end(); ++RenameIter) {
552 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->
Def;
554 auto *ValInfo = Result.PInfo;
555 ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
557 : (RenameStack.end() - Start - 1)->
Def;
568 if (isa<PredicateWithEdge>(ValInfo)) {
570 auto NumDecls =
F.getParent()->getNumNamedValues();
572 F.getParent(), Intrinsic::ssa_copy,
Op->getType());
573 if (NumDecls !=
F.getParent()->getNumNamedValues())
574 PI.CreatedDeclarations.insert(
IF);
576 B.CreateCall(
IF,
Op,
Op->getName() +
"." +
Twine(Counter++));
577 PI.PredicateMap.insert({
PIC, ValInfo});
580 auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
582 "Should not have gotten here without it being an assume");
586 auto NumDecls =
F.getParent()->getNumNamedValues();
588 F.getParent(), Intrinsic::ssa_copy,
Op->getType());
589 if (NumDecls !=
F.getParent()->getNumNamedValues())
590 PI.CreatedDeclarations.insert(
IF);
592 PI.PredicateMap.insert({
PIC, ValInfo});
596 return RenameStack.back().Def;
621 for (
auto *
Op : OpsToRename) {
623 unsigned Counter = 0;
629 for (
auto &PossibleCopy :
ValueInfo.Infos) {
636 if (
const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
638 DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
643 VD.
PInfo = PossibleCopy;
644 OrderedUses.push_back(VD);
645 }
else if (isa<PredicateWithEdge>(PossibleCopy)) {
649 auto BlockEdge = getBlockEdge(PossibleCopy);
650 if (EdgeUsesOnly.count(BlockEdge)) {
652 auto *DomNode = DT.getNode(BlockEdge.first);
656 VD.
PInfo = PossibleCopy;
658 OrderedUses.push_back(VD);
665 auto *DomNode = DT.getNode(BlockEdge.second);
669 VD.
PInfo = PossibleCopy;
670 OrderedUses.push_back(VD);
676 convertUsesToDFSOrdered(
Op, OrderedUses);
686 for (
auto &VD : OrderedUses) {
689 bool PossibleCopy = VD.
PInfo !=
nullptr;
690 if (RenameStack.empty()) {
694 << RenameStack.back().DFSIn <<
","
695 << RenameStack.back().DFSOut <<
")\n");
701 bool ShouldPush = (VD.
Def || PossibleCopy);
702 bool OutOfScope = !stackIsInScope(RenameStack, VD);
703 if (OutOfScope || ShouldPush) {
705 popStackUntilDFSScope(RenameStack, VD);
707 RenameStack.push_back(VD);
712 if (RenameStack.empty())
715 if (VD.
Def || PossibleCopy)
718 LLVM_DEBUG(
dbgs() <<
"Skipping execution due to debug counter\n");
727 Result.Def = materializeStack(Counter, RenameStack,
Op);
730 << *VD.
U->get() <<
" in " << *(VD.
U->getUser())
733 "Predicateinfo def should have dominated this use");
739 PredicateInfoBuilder::ValueInfo &
740 PredicateInfoBuilder::getOrCreateValueInfo(
Value *Operand) {
741 auto OIN = ValueInfoNums.find(Operand);
742 if (OIN == ValueInfoNums.end()) {
744 ValueInfos.resize(ValueInfos.size() + 1);
746 auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
747 assert(InsertResult.second &&
"Value info number already existed?");
748 return ValueInfos[InsertResult.first->second];
750 return ValueInfos[OIN->second];
753 const PredicateInfoBuilder::ValueInfo &
754 PredicateInfoBuilder::getValueInfo(
Value *Operand)
const {
755 auto OINI = ValueInfoNums.lookup(Operand);
756 assert(OINI != 0 &&
"Operand was not really in the Value Info Numbers");
757 assert(OINI < ValueInfos.size() &&
758 "Value Info Number greater than size of Value Info Table");
759 return ValueInfos[OINI];
775 for (
auto &F : CreatedDeclarations)
777 CreatedDeclarations.clear();
781 "PredicateInfo consumer did not remove all SSA copies.");
790 bool TrueEdge =
true;
791 if (
auto *PBranch = dyn_cast<PredicateBranch>(
this))
792 TrueEdge = PBranch->TrueEdge;
809 Pred = Cmp->getPredicate();
810 OtherOp = Cmp->getOperand(1);
811 }
else if (Cmp->getOperand(1) ==
RenamedOp) {
812 Pred = Cmp->getSwappedPredicate();
813 OtherOp = Cmp->getOperand(0);
823 return {{Pred, OtherOp}};
856 auto *II = dyn_cast<IntrinsicInst>(&Inst);
861 Inst.eraseFromParent();
866 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
867 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
868 auto PredInfo = std::make_unique<PredicateInfo>(
F, DT, AC);
869 PredInfo->print(
dbgs());
871 PredInfo->verifyPredicateInfo();
881 OS <<
"PredicateInfo for function: " <<
F.getName() <<
"\n";
882 auto PredInfo = std::make_unique<PredicateInfo>(
F, DT, AC);
904 OS <<
"; Has predicate info\n";
905 if (
const auto *
PB = dyn_cast<PredicateBranch>(PI)) {
906 OS <<
"; branch predicate info { TrueEdge: " <<
PB->TrueEdge
907 <<
" Comparison:" << *
PB->Condition <<
" Edge: [";
908 PB->From->printAsOperand(OS);
910 PB->To->printAsOperand(OS);
912 }
else if (
const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
913 OS <<
"; switch predicate info { CaseValue: " << *PS->CaseValue
914 <<
" Switch:" << *PS->Switch <<
" Edge: [";
915 PS->From->printAsOperand(OS);
917 PS->To->printAsOperand(OS);
919 }
else if (
const auto *PA = dyn_cast<PredicateAssume>(PI)) {
920 OS <<
"; assume predicate info {"
921 <<
" Comparison:" << *PA->Condition;
923 OS <<
", RenamedOp: ";
924 PI->RenamedOp->printAsOperand(OS,
false);
932 F.print(OS, &Writer);
937 F.print(
dbgs(), &Writer);
944 std::make_unique<PredicateInfo>(
F, DT, AC)->verifyPredicateInfo();
A set of analyses that are preserved following a run of a transformation pass.
static bool valueComesBefore(const Value *A, const Value *B)
This is an optimization pass for GlobalISel generic memory operations.
PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT, AssumptionCache &AC)
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool hasOneUse() const
Return true if there is exactly one use of this value.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup 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...
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
print PredicateInfo Printer
PredicateInfoAnnotatedWriter(const PredicateInfo *M)
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
print PredicateInfo static false cl::opt< bool > VerifyPredicateInfo("verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass."))
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool shouldRename(Value *V)
void verifyPredicateInfo() const
The instances of the Type class are immutable: once they are created, they are never changed.
PassInstrumentationCallbacks PIC
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
user_iterator user_begin()
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_NODISCARD T pop_back_val()
LLVM Basic Block Representation.
ppc ctr loops PowerPC CTR Loops Verify
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
(vector float) vec_cmpeq(*A, *B) C
Represent the analysis usage information of a pass.
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F)
Value * getMiddleDef(const ValueDFS &VD) const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
modulo schedule Modulo Schedule test pass
The object format emitted by the WebAssembly backed is documented in
static bool shouldExecute(unsigned CounterName)
Legacy analysis pass which computes a DominatorTree.
This class implements an extremely fast bulk output stream that can only output to a stream.
static const unsigned MaxCondsPerBranch
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
DEBUG_COUNTER(RenameCounter, "predicateinfo-rename", "Controls which variables are renamed with predicateinfo")
Encapsulates PredicateInfo, including all data associated with memory accesses.
Struct that holds a reference to a particular GUID in a global value summary.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Value * getCondition() const
void buildPredicateInfo()
PredicateInfoPrinterLegacyPass()
This class is the base class for the comparison instructions.
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
Implements a dense probed hash-table based set.
const Instruction * getDefOrUser(const Value *Def, const Use *U) const
inst_range instructions(Function *F)
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...
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
bool operator()(const ValueDFS &A, const ValueDFS &B) const
bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const
A function analysis which provides an AssumptionCache.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
initializer< Ty > init(const Ty &Val)
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...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
const PredicateBase * getPredicateInfoFor(const Value *V) const
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
An immutable pass that tracks lazily created AssumptionCache objects.
An assembly annotator class to print PredicateInfo information in comments.
SmallVector< MachineOperand, 4 > Cond
void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &)
A cache of @llvm.assume calls within a function.
http eax xorl edx cl sete al setne dl sall cl
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl< Value * > &CmpOperands)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo", "PredicateInfo Printer", false, false) INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass
static ConstantInt * getFalse(LLVMContext &Context)
iterator_range< df_iterator< T > > depth_first(const T &G)
bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
void stable_sort(R &&Range)
static ConstantInt * getTrue(LLVMContext &Context)
std::pair< BasicBlock *, BasicBlock * > getBlockEdge(const ValueDFS &VD) const
void setPreservesAll()
Set by analyses that do not transform their input at all.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void print(raw_ostream &) const
A wrapper class for inspecting calls to intrinsic functions.
ValueDFS_Compare(DominatorTree &DT)
Analysis pass which computes a DominatorTree.
static void rename(GlobalValue *GV)
const BasicBlock * getParent() const
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...
AnalysisUsage & addRequiredTransitive()
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
This class represents a function call, abstracting a target machine's calling convention.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
Value * getOperand(unsigned i) const
Conditional or Unconditional Branch instruction.
LLVM Value Representation.
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...
bool isConditional() const
Optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
BasicBlock * getSuccessor(unsigned i) const
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.