857 lines · cpp
1//===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------===//8//9// This file implements the PredicateInfo class.10//11//===----------------------------------------------------------------===//12 13#include "llvm/Transforms/Utils/PredicateInfo.h"14#include "llvm/ADT/DenseMap.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/SmallPtrSet.h"17#include "llvm/Analysis/AssumptionCache.h"18#include "llvm/IR/AssemblyAnnotationWriter.h"19#include "llvm/IR/Dominators.h"20#include "llvm/IR/IRBuilder.h"21#include "llvm/IR/InstIterator.h"22#include "llvm/IR/IntrinsicInst.h"23#include "llvm/IR/PatternMatch.h"24#include "llvm/Support/CommandLine.h"25#include "llvm/Support/Debug.h"26#include "llvm/Support/DebugCounter.h"27#include "llvm/Support/FormattedStream.h"28#define DEBUG_TYPE "predicateinfo"29using namespace llvm;30using namespace PatternMatch;31 32static cl::opt<bool> VerifyPredicateInfo(33 "verify-predicateinfo", cl::init(false), cl::Hidden,34 cl::desc("Verify PredicateInfo in legacy printer pass."));35DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",36 "Controls which variables are renamed with predicateinfo");37 38// Maximum number of conditions considered for renaming for each branch/assume.39// This limits renaming of deep and/or chains.40static const unsigned MaxCondsPerBranch = 8;41 42namespace {43// Given a predicate info that is a type of branching terminator, get the44// branching block.45const BasicBlock *getBranchBlock(const PredicateBase *PB) {46 assert(isa<PredicateWithEdge>(PB) &&47 "Only branches and switches should have PHIOnly defs that "48 "require branch blocks.");49 return cast<PredicateWithEdge>(PB)->From;50}51 52// Given a predicate info that is a type of branching terminator, get the53// branching terminator.54static Instruction *getBranchTerminator(const PredicateBase *PB) {55 assert(isa<PredicateWithEdge>(PB) &&56 "Not a predicate info type we know how to get a terminator from.");57 return cast<PredicateWithEdge>(PB)->From->getTerminator();58}59 60// Given a predicate info that is a type of branching terminator, get the61// edge this predicate info represents62std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const PredicateBase *PB) {63 assert(isa<PredicateWithEdge>(PB) &&64 "Not a predicate info type we know how to get an edge from.");65 const auto *PEdge = cast<PredicateWithEdge>(PB);66 return std::make_pair(PEdge->From, PEdge->To);67}68}69 70namespace llvm {71enum LocalNum {72 // Operations that must appear first in the block.73 LN_First,74 // Operations that are somewhere in the middle of the block, and are sorted on75 // demand.76 LN_Middle,77 // Operations that must appear last in a block, like successor phi node uses.78 LN_Last79};80 81// Associate global and local DFS info with defs (PInfo set) and uses (U set),82// so we can sort them into a global domination ordering.83struct ValueDFS {84 int DFSIn = 0;85 int DFSOut = 0;86 unsigned int LocalNum = LN_Middle;87 // Only one of U or PInfo will be set.88 Use *U = nullptr;89 PredicateBase *PInfo = nullptr;90};91 92// This compares ValueDFS structures. Doing so allows us to walk the minimum93// number of instructions necessary to compute our def/use ordering.94struct ValueDFS_Compare {95 DominatorTree &DT;96 ValueDFS_Compare(DominatorTree &DT) : DT(DT) {}97 98 bool operator()(const ValueDFS &A, const ValueDFS &B) const {99 if (&A == &B)100 return false;101 102 // Order by block first.103 if (A.DFSIn != B.DFSIn)104 return A.DFSIn < B.DFSIn;105 assert(A.DFSOut == B.DFSOut &&106 "Equal DFS-in numbers imply equal out numbers");107 108 // Then order by first/middle/last.109 if (A.LocalNum != B.LocalNum)110 return A.LocalNum < B.LocalNum;111 112 // We want to put the def that will get used for a given set of phi uses,113 // before those phi uses.114 // So we sort by edge, then by def.115 // Note that only phi nodes uses and defs can come last.116 if (A.LocalNum == LN_Last)117 return comparePHIRelated(A, B);118 119 // Use block-local ordering for instructions in the middle.120 if (A.LocalNum == LN_Middle)121 return localComesBefore(A, B);122 123 // The order of PredicateInfo definitions at the start of the block does not124 // matter.125 assert(A.LocalNum == LN_First);126 assert(A.PInfo && B.PInfo && "Must be predicate info def");127 return false;128 }129 130 // For a phi use, or a non-materialized def, return the edge it represents.131 std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const ValueDFS &VD) const {132 if (VD.U) {133 auto *PHI = cast<PHINode>(VD.U->getUser());134 return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());135 }136 // This is really a non-materialized def.137 return ::getBlockEdge(VD.PInfo);138 }139 140 // For two phi related values, return the ordering.141 bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {142 BasicBlock *ASrc, *ADest, *BSrc, *BDest;143 std::tie(ASrc, ADest) = getBlockEdge(A);144 std::tie(BSrc, BDest) = getBlockEdge(B);145 146#ifndef NDEBUG147 // This function should only be used for values in the same BB, check that.148 DomTreeNode *DomASrc = DT.getNode(ASrc);149 DomTreeNode *DomBSrc = DT.getNode(BSrc);150 assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn &&151 "DFS numbers for A should match the ones of the source block");152 assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn &&153 "DFS numbers for B should match the ones of the source block");154 assert(A.DFSIn == B.DFSIn && "Values must be in the same block");155#endif156 (void)ASrc;157 (void)BSrc;158 159 // Use DFS numbers to compare destination blocks, to guarantee a160 // deterministic order.161 DomTreeNode *DomADest = DT.getNode(ADest);162 DomTreeNode *DomBDest = DT.getNode(BDest);163 unsigned AIn = DomADest->getDFSNumIn();164 unsigned BIn = DomBDest->getDFSNumIn();165 bool isAUse = A.U;166 bool isBUse = B.U;167 assert((!A.PInfo || !A.U) && (!B.PInfo || !B.U) &&168 "Def and U cannot be set at the same time");169 // Now sort by edge destination and then defs before uses.170 return std::tie(AIn, isAUse) < std::tie(BIn, isBUse);171 }172 173 const Instruction *getDefOrUser(const ValueDFS &VD) const {174 if (VD.U)175 return cast<Instruction>(VD.U->getUser());176 177 // For the purpose of ordering, we pretend the def is right after the178 // assume, because that is where we will insert the info.179 assert(VD.PInfo && "No use, and no predicateinfo should not occur");180 assert(isa<PredicateAssume>(VD.PInfo) &&181 "Middle of block should only occur for assumes");182 return cast<PredicateAssume>(VD.PInfo)->AssumeInst->getNextNode();183 }184 185 // This performs the necessary local basic block ordering checks to tell186 // whether A comes before B, where both are in the same basic block.187 bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {188 const Instruction *AInst = getDefOrUser(A);189 const Instruction *BInst = getDefOrUser(B);190 return AInst->comesBefore(BInst);191 }192};193 194class PredicateInfoBuilder {195 // Used to store information about each value we might rename.196 struct ValueInfo {197 SmallVector<PredicateBase *, 4> Infos;198 };199 200 PredicateInfo &PI;201 Function &F;202 DominatorTree &DT;203 AssumptionCache &AC;204 205 // This stores info about each operand or comparison result we make copies206 // of. The real ValueInfos start at index 1, index 0 is unused so that we207 // can more easily detect invalid indexing.208 SmallVector<ValueInfo, 32> ValueInfos;209 210 // This gives the index into the ValueInfos array for a given Value. Because211 // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell212 // whether it returned a valid result.213 DenseMap<Value *, unsigned int> ValueInfoNums;214 215 BumpPtrAllocator &Allocator;216 217 ValueInfo &getOrCreateValueInfo(Value *);218 const ValueInfo &getValueInfo(Value *) const;219 220 void processAssume(IntrinsicInst *, BasicBlock *,221 SmallVectorImpl<Value *> &OpsToRename);222 void processBranch(BranchInst *, BasicBlock *,223 SmallVectorImpl<Value *> &OpsToRename);224 void processSwitch(SwitchInst *, BasicBlock *,225 SmallVectorImpl<Value *> &OpsToRename);226 void renameUses(SmallVectorImpl<Value *> &OpsToRename);227 void addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op,228 PredicateBase *PB);229 230 struct StackEntry {231 const ValueDFS *V;232 Value *Def = nullptr;233 234 StackEntry(const ValueDFS *V) : V(V) {}235 };236 237 using ValueDFSStack = SmallVectorImpl<StackEntry>;238 void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);239 Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);240 bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;241 void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);242 243public:244 PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT,245 AssumptionCache &AC, BumpPtrAllocator &Allocator)246 : PI(PI), F(F), DT(DT), AC(AC), Allocator(Allocator) {247 // Push an empty operand info so that we can detect 0 as not finding one248 ValueInfos.resize(1);249 }250 251 void buildPredicateInfo();252};253 254bool PredicateInfoBuilder::stackIsInScope(const ValueDFSStack &Stack,255 const ValueDFS &VDUse) const {256 assert(!Stack.empty() && "Should not be called with empty stack");257 // If it's a phi only use, make sure it's for this phi node edge, and that the258 // use is in a phi node. If it's anything else, and the top of the stack is259 // a LN_Last def, we need to pop the stack. We deliberately sort phi uses260 // next to the defs they must go with so that we can know it's time to pop261 // the stack when we hit the end of the phi uses for a given def.262 const ValueDFS &Top = *Stack.back().V;263 assert(Top.PInfo && "RenameStack should only contain predicate infos (defs)");264 if (Top.LocalNum == LN_Last) {265 if (!VDUse.U) {266 assert(VDUse.PInfo && "A non-use VDUse should have a predicate info");267 // We should reserve adjacent LN_Last defs for the same phi use.268 return VDUse.LocalNum == LN_Last &&269 // If the two phi defs have the same edge, they must be designated270 // for the same succ BB.271 getBlockEdge(Top.PInfo) == getBlockEdge(VDUse.PInfo);272 }273 auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());274 if (!PHI)275 return false;276 // Check edge277 BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);278 if (EdgePred != getBranchBlock(Top.PInfo))279 return false;280 281 // Use dominates, which knows how to handle edge dominance.282 return DT.dominates(getBlockEdge(Top.PInfo), *VDUse.U);283 }284 285 return VDUse.DFSIn >= Top.DFSIn && VDUse.DFSOut <= Top.DFSOut;286}287 288void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,289 const ValueDFS &VD) {290 while (!Stack.empty() && !stackIsInScope(Stack, VD))291 Stack.pop_back();292}293 294// Convert the uses of Op into a vector of uses, associating global and local295// DFS info with each one.296void PredicateInfoBuilder::convertUsesToDFSOrdered(297 Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {298 for (auto &U : Op->uses()) {299 if (auto *I = dyn_cast<Instruction>(U.getUser())) {300 // Lifetime intrinsics must work directly on alloca, do not replace them301 // with a predicated copy.302 if (I->isLifetimeStartOrEnd())303 continue;304 305 ValueDFS VD;306 // Put the phi node uses in the incoming block.307 BasicBlock *IBlock;308 if (auto *PN = dyn_cast<PHINode>(I)) {309 IBlock = PN->getIncomingBlock(U);310 // Make phi node users appear last in the incoming block311 // they are from.312 VD.LocalNum = LN_Last;313 } else {314 // If it's not a phi node use, it is somewhere in the middle of the315 // block.316 IBlock = I->getParent();317 VD.LocalNum = LN_Middle;318 }319 DomTreeNode *DomNode = DT.getNode(IBlock);320 // It's possible our use is in an unreachable block. Skip it if so.321 if (!DomNode)322 continue;323 VD.DFSIn = DomNode->getDFSNumIn();324 VD.DFSOut = DomNode->getDFSNumOut();325 VD.U = &U;326 DFSOrderedSet.push_back(VD);327 }328 }329}330 331bool shouldRename(Value *V) {332 // Only want real values, not constants. Additionally, operands with one use333 // are only being used in the comparison, which means they will not be useful334 // for us to consider for predicateinfo.335 return (isa<Instruction>(V) || isa<Argument>(V)) && !V->hasOneUse();336}337 338// Collect relevant operations from Comparison that we may want to insert copies339// for.340void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {341 auto *Op0 = Comparison->getOperand(0);342 auto *Op1 = Comparison->getOperand(1);343 if (Op0 == Op1)344 return;345 346 CmpOperands.push_back(Op0);347 CmpOperands.push_back(Op1);348}349 350// Add Op, PB to the list of value infos for Op, and mark Op to be renamed.351void PredicateInfoBuilder::addInfoFor(SmallVectorImpl<Value *> &OpsToRename,352 Value *Op, PredicateBase *PB) {353 auto &OperandInfo = getOrCreateValueInfo(Op);354 if (OperandInfo.Infos.empty())355 OpsToRename.push_back(Op);356 OperandInfo.Infos.push_back(PB);357}358 359// Process an assume instruction and place relevant operations we want to rename360// into OpsToRename.361void PredicateInfoBuilder::processAssume(362 IntrinsicInst *II, BasicBlock *AssumeBB,363 SmallVectorImpl<Value *> &OpsToRename) {364 SmallVector<Value *, 4> Worklist;365 SmallPtrSet<Value *, 4> Visited;366 Worklist.push_back(II->getOperand(0));367 while (!Worklist.empty()) {368 Value *Cond = Worklist.pop_back_val();369 if (!Visited.insert(Cond).second)370 continue;371 if (Visited.size() > MaxCondsPerBranch)372 break;373 374 Value *Op0, *Op1;375 if (match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {376 Worklist.push_back(Op1);377 Worklist.push_back(Op0);378 }379 380 SmallVector<Value *, 4> Values;381 Values.push_back(Cond);382 if (auto *Cmp = dyn_cast<CmpInst>(Cond))383 collectCmpOps(Cmp, Values);384 else if (match(Cond, m_NUWTrunc(m_Value(Op0))))385 Values.push_back(Op0);386 387 for (Value *V : Values) {388 if (shouldRename(V)) {389 auto *PA = new (Allocator) PredicateAssume(V, II, Cond);390 addInfoFor(OpsToRename, V, PA);391 }392 }393 }394}395 396// Process a block terminating branch, and place relevant operations to be397// renamed into OpsToRename.398void PredicateInfoBuilder::processBranch(399 BranchInst *BI, BasicBlock *BranchBB,400 SmallVectorImpl<Value *> &OpsToRename) {401 BasicBlock *FirstBB = BI->getSuccessor(0);402 BasicBlock *SecondBB = BI->getSuccessor(1);403 404 for (BasicBlock *Succ : {FirstBB, SecondBB}) {405 bool TakenEdge = Succ == FirstBB;406 // Don't try to insert on a self-edge. This is mainly because we will407 // eliminate during renaming anyway.408 if (Succ == BranchBB)409 continue;410 411 SmallVector<Value *, 4> Worklist;412 SmallPtrSet<Value *, 4> Visited;413 Worklist.push_back(BI->getCondition());414 while (!Worklist.empty()) {415 Value *Cond = Worklist.pop_back_val();416 if (!Visited.insert(Cond).second)417 continue;418 if (Visited.size() > MaxCondsPerBranch)419 break;420 421 Value *Op0, *Op1;422 if (TakenEdge ? match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))423 : match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {424 Worklist.push_back(Op1);425 Worklist.push_back(Op0);426 }427 428 SmallVector<Value *, 4> Values;429 Values.push_back(Cond);430 if (auto *Cmp = dyn_cast<CmpInst>(Cond))431 collectCmpOps(Cmp, Values);432 else if (match(Cond, m_NUWTrunc(m_Value(Op0))))433 Values.push_back(Op0);434 435 for (Value *V : Values) {436 if (shouldRename(V)) {437 PredicateBase *PB = new (Allocator)438 PredicateBranch(V, BranchBB, Succ, Cond, TakenEdge);439 addInfoFor(OpsToRename, V, PB);440 }441 }442 }443 }444}445// Process a block terminating switch, and place relevant operations to be446// renamed into OpsToRename.447void PredicateInfoBuilder::processSwitch(448 SwitchInst *SI, BasicBlock *BranchBB,449 SmallVectorImpl<Value *> &OpsToRename) {450 Value *Op = SI->getCondition();451 if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())452 return;453 454 // Remember how many outgoing edges there are to every successor.455 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;456 for (BasicBlock *TargetBlock : successors(BranchBB))457 ++SwitchEdges[TargetBlock];458 459 // Now propagate info for each case value460 for (auto C : SI->cases()) {461 BasicBlock *TargetBlock = C.getCaseSuccessor();462 if (SwitchEdges.lookup(TargetBlock) == 1) {463 PredicateSwitch *PS = new (Allocator) PredicateSwitch(464 Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);465 addInfoFor(OpsToRename, Op, PS);466 }467 }468}469 470// Build predicate info for our function471void PredicateInfoBuilder::buildPredicateInfo() {472 DT.updateDFSNumbers();473 // Collect operands to rename from all conditional branch terminators, as well474 // as assume statements.475 SmallVector<Value *, 8> OpsToRename;476 for (BasicBlock &BB : F) {477 if (!DT.isReachableFromEntry(&BB))478 continue;479 480 if (auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {481 if (!BI->isConditional())482 continue;483 // Can't insert conditional information if they all go to the same place.484 if (BI->getSuccessor(0) == BI->getSuccessor(1))485 continue;486 processBranch(BI, &BB, OpsToRename);487 } else if (auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {488 processSwitch(SI, &BB, OpsToRename);489 }490 }491 for (auto &Assume : AC.assumptions()) {492 if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))493 if (DT.isReachableFromEntry(II->getParent()))494 processAssume(II, II->getParent(), OpsToRename);495 }496 // Now rename all our operations.497 renameUses(OpsToRename);498}499 500// Given the renaming stack, make all the operands currently on the stack real501// by inserting them into the IR. Return the last operation's value.502Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,503 ValueDFSStack &RenameStack,504 Value *OrigOp) {505 // Find the first thing we have to materialize506 auto RevIter = RenameStack.rbegin();507 for (; RevIter != RenameStack.rend(); ++RevIter)508 if (RevIter->Def)509 break;510 511 size_t Start = RevIter - RenameStack.rbegin();512 // The maximum number of things we should be trying to materialize at once513 // right now is 4, depending on if we had an assume, a branch, and both used514 // and of conditions.515 for (auto RenameIter = RenameStack.end() - Start;516 RenameIter != RenameStack.end(); ++RenameIter) {517 auto *Op =518 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;519 StackEntry &Result = *RenameIter;520 auto *ValInfo = Result.V->PInfo;521 ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()522 ? OrigOp523 : (RenameStack.end() - Start - 1)->Def;524 auto CreateSSACopy = [](Instruction *InsertPt, Value *Op,525 const Twine &Name = "") {526 // Use a no-op bitcast to represent ssa copy.527 return new BitCastInst(Op, Op->getType(), Name, InsertPt->getIterator());528 };529 // For edge predicates, we can just place the operand in the block before530 // the terminator. For assume, we have to place it right after the assume531 // to ensure we dominate all uses except assume itself. Always insert532 // right before the terminator or after the assume, so that we insert in533 // proper order in the case of multiple predicateinfo in the same block.534 if (isa<PredicateWithEdge>(ValInfo)) {535 BitCastInst *PIC = CreateSSACopy(getBranchTerminator(ValInfo), Op,536 Op->getName() + "." + Twine(Counter++));537 PI.PredicateMap.insert({PIC, ValInfo});538 Result.Def = PIC;539 } else {540 auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);541 assert(PAssume &&542 "Should not have gotten here without it being an assume");543 // Insert the predicate directly after the assume. While it also holds544 // directly before it, assume(i1 true) is not a useful fact.545 BitCastInst *PIC = CreateSSACopy(PAssume->AssumeInst->getNextNode(), Op);546 PI.PredicateMap.insert({PIC, ValInfo});547 Result.Def = PIC;548 }549 }550 return RenameStack.back().Def;551}552 553// Instead of the standard SSA renaming algorithm, which is O(Number of554// instructions), and walks the entire dominator tree, we walk only the defs +555// uses. The standard SSA renaming algorithm does not really rely on the556// dominator tree except to order the stack push/pops of the renaming stacks, so557// that defs end up getting pushed before hitting the correct uses. This does558// not require the dominator tree, only the *order* of the dominator tree. The559// complete and correct ordering of the defs and uses, in dominator tree is560// contained in the DFS numbering of the dominator tree. So we sort the defs and561// uses into the DFS ordering, and then just use the renaming stack as per562// normal, pushing when we hit a def (which is a predicateinfo instruction),563// popping when we are out of the dfs scope for that def, and replacing any uses564// with top of stack if it exists. In order to handle liveness without565// propagating liveness info, we don't actually insert the predicateinfo566// instruction def until we see a use that it would dominate. Once we see such567// a use, we materialize the predicateinfo instruction in the right place and568// use it.569//570// TODO: Use this algorithm to perform fast single-variable renaming in571// promotememtoreg and memoryssa.572void PredicateInfoBuilder::renameUses(SmallVectorImpl<Value *> &OpsToRename) {573 ValueDFS_Compare Compare(DT);574 // Compute liveness, and rename in O(uses) per Op.575 for (auto *Op : OpsToRename) {576 LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");577 unsigned Counter = 0;578 SmallVector<ValueDFS, 16> OrderedUses;579 const auto &ValueInfo = getValueInfo(Op);580 // Insert the possible copies into the def/use list.581 // They will become real copies if we find a real use for them, and never582 // created otherwise.583 for (const auto &PossibleCopy : ValueInfo.Infos) {584 ValueDFS VD;585 // Determine where we are going to place the copy by the copy type.586 // The predicate info for branches always come first, they will get587 // materialized in the split block at the top of the block.588 // The predicate info for assumes will be somewhere in the middle,589 // it will get materialized right after the assume.590 if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {591 VD.LocalNum = LN_Middle;592 DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());593 if (!DomNode)594 continue;595 VD.DFSIn = DomNode->getDFSNumIn();596 VD.DFSOut = DomNode->getDFSNumOut();597 VD.PInfo = PossibleCopy;598 OrderedUses.push_back(VD);599 } else if (isa<PredicateWithEdge>(PossibleCopy)) {600 // If we can only do phi uses, we treat it like it's in the branch601 // block, and handle it specially. We know that it goes last, and only602 // dominate phi uses.603 auto BlockEdge = getBlockEdge(PossibleCopy);604 if (!BlockEdge.second->getSinglePredecessor()) {605 VD.LocalNum = LN_Last;606 auto *DomNode = DT.getNode(BlockEdge.first);607 if (DomNode) {608 VD.DFSIn = DomNode->getDFSNumIn();609 VD.DFSOut = DomNode->getDFSNumOut();610 VD.PInfo = PossibleCopy;611 OrderedUses.push_back(VD);612 }613 } else {614 // Otherwise, we are in the split block (even though we perform615 // insertion in the branch block).616 // Insert a possible copy at the split block and before the branch.617 VD.LocalNum = LN_First;618 auto *DomNode = DT.getNode(BlockEdge.second);619 if (DomNode) {620 VD.DFSIn = DomNode->getDFSNumIn();621 VD.DFSOut = DomNode->getDFSNumOut();622 VD.PInfo = PossibleCopy;623 OrderedUses.push_back(VD);624 }625 }626 }627 }628 629 convertUsesToDFSOrdered(Op, OrderedUses);630 // Here we require a stable sort because we do not bother to try to631 // assign an order to the operands the uses represent. Thus, two632 // uses in the same instruction do not have a strict sort order633 // currently and will be considered equal. We could get rid of the634 // stable sort by creating one if we wanted.635 llvm::stable_sort(OrderedUses, Compare);636 SmallVector<StackEntry, 8> RenameStack;637 // For each use, sorted into dfs order, push values and replaces uses with638 // top of stack, which will represent the reaching def.639 for (const ValueDFS &VD : OrderedUses) {640 // We currently do not materialize copy over copy, but we should decide if641 // we want to.642 if (RenameStack.empty()) {643 LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");644 } else {645 LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("646 << RenameStack.back().V->DFSIn << ","647 << RenameStack.back().V->DFSOut << ")\n");648 }649 650 LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","651 << VD.DFSOut << ")\n");652 653 // Sync to our current scope.654 popStackUntilDFSScope(RenameStack, VD);655 656 if (VD.PInfo) {657 RenameStack.push_back(&VD);658 continue;659 }660 661 // If we get to this point, and the stack is empty we must have a use662 // with no renaming needed, just skip it.663 if (RenameStack.empty())664 continue;665 if (!DebugCounter::shouldExecute(RenameCounter)) {666 LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");667 continue;668 }669 StackEntry &Result = RenameStack.back();670 671 // If the possible copy dominates something, materialize our stack up to672 // this point. This ensures every comparison that affects our operation673 // ends up with predicateinfo.674 if (!Result.Def)675 Result.Def = materializeStack(Counter, RenameStack, Op);676 677 LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "678 << *VD.U->get() << " in " << *(VD.U->getUser())679 << "\n");680 assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&681 "Predicateinfo def should have dominated this use");682 VD.U->set(Result.Def);683 }684 }685}686 687PredicateInfoBuilder::ValueInfo &688PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) {689 auto Res = ValueInfoNums.try_emplace(Operand, ValueInfos.size());690 if (Res.second) {691 // Allocate space for new ValueInfo.692 ValueInfos.resize(ValueInfos.size() + 1);693 }694 return ValueInfos[Res.first->second];695}696 697const PredicateInfoBuilder::ValueInfo &698PredicateInfoBuilder::getValueInfo(Value *Operand) const {699 auto OINI = ValueInfoNums.lookup(Operand);700 assert(OINI != 0 && "Operand was not really in the Value Info Numbers");701 assert(OINI < ValueInfos.size() &&702 "Value Info Number greater than size of Value Info Table");703 return ValueInfos[OINI];704}705 706PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,707 AssumptionCache &AC, BumpPtrAllocator &Allocator)708 : F(F) {709 PredicateInfoBuilder Builder(*this, F, DT, AC, Allocator);710 Builder.buildPredicateInfo();711}712 713std::optional<PredicateConstraint> PredicateBase::getConstraint() const {714 switch (Type) {715 case PT_Assume:716 case PT_Branch: {717 bool TrueEdge = true;718 if (auto *PBranch = dyn_cast<PredicateBranch>(this))719 TrueEdge = PBranch->TrueEdge;720 721 if (Condition == RenamedOp) {722 return {{CmpInst::ICMP_EQ,723 TrueEdge ? ConstantInt::getTrue(Condition->getType())724 : ConstantInt::getFalse(Condition->getType())}};725 }726 727 if (match(Condition, m_NUWTrunc(m_Specific(RenamedOp)))) {728 return {{TrueEdge ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ,729 ConstantInt::getNullValue(RenamedOp->getType())}};730 }731 732 CmpInst *Cmp = dyn_cast<CmpInst>(Condition);733 if (!Cmp) {734 // TODO: Make this an assertion once RenamedOp is fully accurate.735 return std::nullopt;736 }737 738 CmpInst::Predicate Pred;739 Value *OtherOp;740 if (Cmp->getOperand(0) == RenamedOp) {741 Pred = Cmp->getPredicate();742 OtherOp = Cmp->getOperand(1);743 } else if (Cmp->getOperand(1) == RenamedOp) {744 Pred = Cmp->getSwappedPredicate();745 OtherOp = Cmp->getOperand(0);746 } else {747 // TODO: Make this an assertion once RenamedOp is fully accurate.748 return std::nullopt;749 }750 751 // Invert predicate along false edge.752 if (!TrueEdge)753 Pred = CmpInst::getInversePredicate(Pred);754 755 return {{Pred, OtherOp}};756 }757 case PT_Switch:758 if (Condition != RenamedOp) {759 // TODO: Make this an assertion once RenamedOp is fully accurate.760 return std::nullopt;761 }762 763 return {{CmpInst::ICMP_EQ, cast<PredicateSwitch>(this)->CaseValue}};764 }765 llvm_unreachable("Unknown predicate type");766}767 768void PredicateInfo::verifyPredicateInfo() const {}769 770// Replace bitcasts created by PredicateInfo with their operand.771static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {772 for (Instruction &Inst : llvm::make_early_inc_range(instructions(F))) {773 const auto *PI = PredInfo.getPredicateInfoFor(&Inst);774 if (!PI)775 continue;776 777 assert(isa<BitCastInst>(Inst) &&778 Inst.getType() == Inst.getOperand(0)->getType());779 Inst.replaceAllUsesWith(Inst.getOperand(0));780 Inst.eraseFromParent();781 }782}783 784PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,785 FunctionAnalysisManager &AM) {786 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);787 auto &AC = AM.getResult<AssumptionAnalysis>(F);788 OS << "PredicateInfo for function: " << F.getName() << "\n";789 BumpPtrAllocator Allocator;790 auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC, Allocator);791 PredInfo->print(OS);792 793 replaceCreatedSSACopys(*PredInfo, F);794 return PreservedAnalyses::all();795}796 797/// An assembly annotator class to print PredicateInfo information in798/// comments.799class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {800 friend class PredicateInfo;801 const PredicateInfo *PredInfo;802 803public:804 PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}805 806 void emitBasicBlockStartAnnot(const BasicBlock *BB,807 formatted_raw_ostream &OS) override {}808 809 void emitInstructionAnnot(const Instruction *I,810 formatted_raw_ostream &OS) override {811 if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {812 if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {813 OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge814 << " Comparison:" << *PB->Condition << " Edge: [";815 PB->From->printAsOperand(OS);816 OS << ",";817 PB->To->printAsOperand(OS);818 OS << "]";819 } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {820 OS << "; switch predicate info { CaseValue: " << *PS->CaseValue821 << " Edge: [";822 PS->From->printAsOperand(OS);823 OS << ",";824 PS->To->printAsOperand(OS);825 OS << "]";826 } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {827 OS << "; assume predicate info {"828 << " Comparison:" << *PA->Condition;829 }830 OS << ", RenamedOp: ";831 PI->RenamedOp->printAsOperand(OS, false);832 OS << " }\n";833 }834 }835};836 837void PredicateInfo::print(raw_ostream &OS) const {838 PredicateInfoAnnotatedWriter Writer(this);839 F.print(OS, &Writer);840}841 842void PredicateInfo::dump() const {843 PredicateInfoAnnotatedWriter Writer(this);844 F.print(dbgs(), &Writer);845}846 847PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,848 FunctionAnalysisManager &AM) {849 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);850 auto &AC = AM.getResult<AssumptionAnalysis>(F);851 BumpPtrAllocator Allocator;852 std::make_unique<PredicateInfo>(F, DT, AC, Allocator)->verifyPredicateInfo();853 854 return PreservedAnalyses::all();855}856}857