38 #define DEBUG_TYPE "predicateinfo"
40 using namespace PatternMatch;
43 "PredicateInfo Printer",
false,
false)
62 assert(isa<PredicateWithEdge>(PB) &&
63 "Only branches and switches should have PHIOnly defs that "
64 "require branch blocks.");
65 return cast<PredicateWithEdge>(PB)->From;
71 assert(isa<PredicateWithEdge>(PB) &&
72 "Not a predicate info type we know how to get a terminator from.");
73 return cast<PredicateWithEdge>(PB)->From->getTerminator();
78 std::pair<BasicBlock *, BasicBlock *> getBlockEdge(
const PredicateBase *PB) {
79 assert(isa<PredicateWithEdge>(PB) &&
80 "Not a predicate info type we know how to get an edge from.");
81 const auto *PEdge = cast<PredicateWithEdge>(PB);
82 return std::make_pair(PEdge->From, PEdge->To);
108 bool EdgeOnly =
false;
113 auto *ArgA = dyn_cast_or_null<Argument>(A);
114 auto *ArgB = dyn_cast_or_null<Argument>(
B);
120 return ArgA->getArgNo() < ArgB->getArgNo();
121 return cast<Instruction>(A)->comesBefore(cast<Instruction>(
B));
138 assert((A.DFSIn !=
B.DFSIn || A.DFSOut ==
B.DFSOut) &&
139 "Equal DFS-in numbers imply equal out numbers");
140 bool SameBlock = A.DFSIn ==
B.DFSIn;
147 return comparePHIRelated(A,
B);
152 return std::tie(A.DFSIn, A.LocalNum, isADef) <
153 std::tie(
B.DFSIn,
B.LocalNum, isBDef);
154 return localComesBefore(A,
B);
159 if (!VD.
Def && VD.
U) {
160 auto *PHI = cast<PHINode>(VD.
U->getUser());
161 return std::make_pair(PHI->getIncomingBlock(*VD.
U), PHI->getParent());
164 return ::getBlockEdge(VD.
PInfo);
170 std::tie(ASrc, ADest) = getBlockEdge(A);
171 std::tie(BSrc, BDest) = getBlockEdge(
B);
178 "DFS numbers for A should match the ones of the source block");
180 "DFS numbers for B should match the ones of the source block");
181 assert(A.DFSIn ==
B.DFSIn &&
"Values must be in the same block");
194 assert((!A.Def || !A.U) && (!
B.Def || !
B.U) &&
195 "Def and U cannot be set at the same time");
197 return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
212 "No def, no use, and no predicateinfo should not occur");
214 "Middle of block should only occur for assumes");
215 return cast<PredicateAssume>(VD.
PInfo)->AssumeInst->getNextNode();
224 return cast<Instruction>(
Def);
225 return cast<Instruction>(U->getUser());
231 auto *ADef = getMiddleDef(A);
232 auto *BDef = getMiddleDef(
B);
237 auto *ArgA = dyn_cast_or_null<Argument>(ADef);
238 auto *ArgB = dyn_cast_or_null<Argument>(BDef);
243 auto *AInst = getDefOrUser(ADef, A.U);
244 auto *BInst = getDefOrUser(BDef,
B.U);
274 ValueInfo &getOrCreateValueInfo(
Value *);
275 const ValueInfo &getValueInfo(
Value *)
const;
296 : PI(PI),
F(
F), DT(DT), AC(AC) {
301 void buildPredicateInfo();
304 bool PredicateInfoBuilder::stackIsInScope(
const ValueDFSStack &Stack,
313 if (Stack.back().EdgeOnly) {
316 auto *PHI = dyn_cast<PHINode>(VDUse.
U->getUser());
320 BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.
U);
321 if (EdgePred != getBranchBlock(Stack.back().PInfo))
325 return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.
U);
332 void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,
334 while (!
Stack.empty() && !stackIsInScope(Stack, VD))
340 void PredicateInfoBuilder::convertUsesToDFSOrdered(
342 for (
auto &U :
Op->uses()) {
343 if (
auto *
I = dyn_cast<Instruction>(U.getUser())) {
347 if (
auto *PN = dyn_cast<PHINode>(
I)) {
348 IBlock = PN->getIncomingBlock(U);
355 IBlock =
I->getParent();
365 DFSOrderedSet.push_back(VD);
374 return (isa<Instruction>(V) || isa<Argument>(V)) && !V->
hasOneUse();
385 CmpOperands.push_back(Op0);
386 CmpOperands.push_back(Op1);
392 auto &OperandInfo = getOrCreateValueInfo(
Op);
393 if (OperandInfo.Infos.empty())
394 OpsToRename.push_back(
Op);
395 PI.AllInfos.push_back(PB);
396 OperandInfo.Infos.push_back(PB);
401 void PredicateInfoBuilder::processAssume(
407 while (!Worklist.empty()) {
416 Worklist.push_back(Op1);
417 Worklist.push_back(Op0);
421 Values.push_back(
Cond);
422 if (
auto *Cmp = dyn_cast<CmpInst>(
Cond))
425 for (
Value *V : Values) {
428 addInfoFor(OpsToRename, V, PA);
436 void PredicateInfoBuilder::processBranch(
442 for (
BasicBlock *Succ : {FirstBB, SecondBB}) {
443 bool TakenEdge = Succ == FirstBB;
446 if (Succ == BranchBB)
452 while (!Worklist.empty()) {
462 Worklist.push_back(Op1);
463 Worklist.push_back(Op0);
467 Values.push_back(
Cond);
468 if (
auto *Cmp = dyn_cast<CmpInst>(
Cond))
471 for (
Value *V : Values) {
475 addInfoFor(OpsToRename, V, PB);
476 if (!Succ->getSinglePredecessor())
477 EdgeUsesOnly.insert({BranchBB, Succ});
485 void PredicateInfoBuilder::processSwitch(
489 if ((!isa<Instruction>(
Op) && !isa<Argument>(
Op)) ||
Op->hasOneUse())
494 for (
unsigned i = 0,
e =
SI->getNumSuccessors();
i !=
e; ++
i) {
496 ++SwitchEdges[TargetBlock];
500 for (
auto C :
SI->cases()) {
502 if (SwitchEdges.
lookup(TargetBlock) == 1) {
504 Op,
SI->getParent(), TargetBlock,
C.getCaseValue(),
SI);
505 addInfoFor(OpsToRename,
Op, PS);
507 EdgeUsesOnly.insert({BranchBB, TargetBlock});
514 DT.updateDFSNumbers();
520 if (
auto *BI = dyn_cast<BranchInst>(BranchBB->
getTerminator())) {
526 processBranch(BI, BranchBB, OpsToRename);
527 }
else if (
auto *
SI = dyn_cast<SwitchInst>(BranchBB->
getTerminator())) {
531 for (
auto &Assume : AC.assumptions()) {
532 if (
auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
533 if (DT.isReachableFromEntry(II->
getParent()))
534 processAssume(II, II->
getParent(), OpsToRename);
537 renameUses(OpsToRename);
542 Value *PredicateInfoBuilder::materializeStack(
unsigned int &Counter,
543 ValueDFSStack &RenameStack,
546 auto RevIter = RenameStack.rbegin();
547 for (; RevIter != RenameStack.rend(); ++RevIter)
551 size_t Start = RevIter - RenameStack.rbegin();
555 for (
auto RenameIter = RenameStack.end() - Start;
556 RenameIter != RenameStack.end(); ++RenameIter) {
558 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->
Def;
560 auto *ValInfo = Result.PInfo;
561 ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
563 : (RenameStack.end() - Start - 1)->
Def;
569 if (isa<PredicateWithEdge>(ValInfo)) {
572 F.getParent(), Intrinsic::ssa_copy,
Op->getType());
574 B.CreateCall(
IF,
Op,
Op->getName() +
"." +
Twine(Counter++));
575 PI.PredicateMap.insert({PIC, ValInfo});
578 auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
580 "Should not have gotten here without it being an assume");
585 F.getParent(), Intrinsic::ssa_copy,
Op->getType());
587 PI.PredicateMap.insert({PIC, ValInfo});
591 return RenameStack.back().Def;
616 for (
auto *
Op : OpsToRename) {
618 unsigned Counter = 0;
624 for (
auto &PossibleCopy :
ValueInfo.Infos) {
631 if (
const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
633 DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
638 VD.
PInfo = PossibleCopy;
639 OrderedUses.push_back(VD);
640 }
else if (isa<PredicateWithEdge>(PossibleCopy)) {
644 auto BlockEdge = getBlockEdge(PossibleCopy);
645 if (EdgeUsesOnly.count(BlockEdge)) {
647 auto *DomNode = DT.getNode(BlockEdge.first);
651 VD.
PInfo = PossibleCopy;
653 OrderedUses.push_back(VD);
660 auto *DomNode = DT.getNode(BlockEdge.second);
664 VD.
PInfo = PossibleCopy;
665 OrderedUses.push_back(VD);
671 convertUsesToDFSOrdered(
Op, OrderedUses);
681 for (
auto &VD : OrderedUses) {
684 bool PossibleCopy = VD.
PInfo !=
nullptr;
685 if (RenameStack.empty()) {
689 << RenameStack.back().DFSIn <<
","
690 << RenameStack.back().DFSOut <<
")\n");
696 bool ShouldPush = (VD.
Def || PossibleCopy);
697 bool OutOfScope = !stackIsInScope(RenameStack, VD);
698 if (OutOfScope || ShouldPush) {
700 popStackUntilDFSScope(RenameStack, VD);
702 RenameStack.push_back(VD);
707 if (RenameStack.empty())
710 if (VD.
Def || PossibleCopy)
713 LLVM_DEBUG(
dbgs() <<
"Skipping execution due to debug counter\n");
722 Result.Def = materializeStack(Counter, RenameStack,
Op);
725 << *VD.
U->get() <<
" in " << *(VD.
U->getUser())
728 "Predicateinfo def should have dominated this use");
734 PredicateInfoBuilder::ValueInfo &
735 PredicateInfoBuilder::getOrCreateValueInfo(
Value *Operand) {
736 auto OIN = ValueInfoNums.find(Operand);
737 if (OIN == ValueInfoNums.end()) {
739 ValueInfos.resize(ValueInfos.size() + 1);
741 auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
742 assert(InsertResult.second &&
"Value info number already existed?");
743 return ValueInfos[InsertResult.first->second];
745 return ValueInfos[OIN->second];
748 const PredicateInfoBuilder::ValueInfo &
749 PredicateInfoBuilder::getValueInfo(
Value *Operand)
const {
750 auto OINI = ValueInfoNums.lookup(Operand);
751 assert(OINI != 0 &&
"Operand was not really in the Value Info Numbers");
752 assert(OINI < ValueInfos.size() &&
753 "Value Info Number greater than size of Value Info Table");
754 return ValueInfos[OINI];
768 bool TrueEdge =
true;
769 if (
auto *PBranch = dyn_cast<PredicateBranch>(
this))
770 TrueEdge = PBranch->TrueEdge;
787 Pred = Cmp->getPredicate();
788 OtherOp = Cmp->getOperand(1);
789 }
else if (Cmp->getOperand(1) ==
RenamedOp) {
790 Pred = Cmp->getSwappedPredicate();
791 OtherOp = Cmp->getOperand(0);
801 return {{Pred, OtherOp}};
831 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
832 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
833 auto PredInfo = std::make_unique<PredicateInfo>(
F, DT, AC);
834 PredInfo->print(
dbgs());
836 PredInfo->verifyPredicateInfo();
844 OS <<
"PredicateInfo for function: " <<
F.getName() <<
"\n";
845 auto PredInfo = std::make_unique<PredicateInfo>(
F, DT, AC);
866 OS <<
"; Has predicate info\n";
867 if (
const auto *PB = dyn_cast<PredicateBranch>(PI)) {
868 OS <<
"; branch predicate info { TrueEdge: " << PB->TrueEdge
869 <<
" Comparison:" << *PB->
Condition <<
" Edge: [";
870 PB->From->printAsOperand(OS);
872 PB->To->printAsOperand(OS);
874 }
else if (
const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
875 OS <<
"; switch predicate info { CaseValue: " << *PS->CaseValue
876 <<
" Switch:" << *PS->Switch <<
" Edge: [";
877 PS->From->printAsOperand(OS);
879 PS->To->printAsOperand(OS);
881 }
else if (
const auto *PA = dyn_cast<PredicateAssume>(PI)) {
882 OS <<
"; assume predicate info {"
883 <<
" Comparison:" << *PA->Condition;
885 OS <<
", RenamedOp: ";
886 PI->RenamedOp->printAsOperand(OS,
false);
894 F.print(OS, &Writer);
899 F.print(
dbgs(), &Writer);
906 std::make_unique<PredicateInfo>(
F, DT, AC)->verifyPredicateInfo();