| //===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------===// |
| // |
| // This file implements the PredicateInfo class. |
| // |
| //===----------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Utils/PredicateInfo.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/DepthFirstIterator.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/ADT/StringExtras.h" |
| #include "llvm/Analysis/AssumptionCache.h" |
| #include "llvm/Analysis/CFG.h" |
| #include "llvm/IR/AssemblyAnnotationWriter.h" |
| #include "llvm/IR/DataLayout.h" |
| #include "llvm/IR/Dominators.h" |
| #include "llvm/IR/GlobalVariable.h" |
| #include "llvm/IR/IRBuilder.h" |
| #include "llvm/IR/InstIterator.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/LLVMContext.h" |
| #include "llvm/IR/Metadata.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/IR/PatternMatch.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/DebugCounter.h" |
| #include "llvm/Support/FormattedStream.h" |
| #include "llvm/Transforms/Utils.h" |
| #include <algorithm> |
| #define DEBUG_TYPE "predicateinfo" |
| using namespace llvm; |
| using namespace PatternMatch; |
| using namespace llvm::PredicateInfoClasses; |
| |
| INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo", |
| "PredicateInfo Printer", false, false) |
| INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
| INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) |
| INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo", |
| "PredicateInfo Printer", false, false) |
| static cl::opt<bool> VerifyPredicateInfo( |
| "verify-predicateinfo", cl::init(false), cl::Hidden, |
| cl::desc("Verify PredicateInfo in legacy printer pass.")); |
| DEBUG_COUNTER(RenameCounter, "predicateinfo-rename", |
| "Controls which variables are renamed with predicateinfo"); |
| |
| namespace { |
| // Given a predicate info that is a type of branching terminator, get the |
| // branching block. |
| const BasicBlock *getBranchBlock(const PredicateBase *PB) { |
| assert(isa<PredicateWithEdge>(PB) && |
| "Only branches and switches should have PHIOnly defs that " |
| "require branch blocks."); |
| return cast<PredicateWithEdge>(PB)->From; |
| } |
| |
| // Given a predicate info that is a type of branching terminator, get the |
| // branching terminator. |
| static Instruction *getBranchTerminator(const PredicateBase *PB) { |
| assert(isa<PredicateWithEdge>(PB) && |
| "Not a predicate info type we know how to get a terminator from."); |
| return cast<PredicateWithEdge>(PB)->From->getTerminator(); |
| } |
| |
| // Given a predicate info that is a type of branching terminator, get the |
| // edge this predicate info represents |
| const std::pair<BasicBlock *, BasicBlock *> |
| getBlockEdge(const PredicateBase *PB) { |
| assert(isa<PredicateWithEdge>(PB) && |
| "Not a predicate info type we know how to get an edge from."); |
| const auto *PEdge = cast<PredicateWithEdge>(PB); |
| return std::make_pair(PEdge->From, PEdge->To); |
| } |
| } |
| |
| namespace llvm { |
| namespace PredicateInfoClasses { |
| enum LocalNum { |
| // Operations that must appear first in the block. |
| LN_First, |
| // Operations that are somewhere in the middle of the block, and are sorted on |
| // demand. |
| LN_Middle, |
| // Operations that must appear last in a block, like successor phi node uses. |
| LN_Last |
| }; |
| |
| // Associate global and local DFS info with defs and uses, so we can sort them |
| // into a global domination ordering. |
| struct ValueDFS { |
| int DFSIn = 0; |
| int DFSOut = 0; |
| unsigned int LocalNum = LN_Middle; |
| // Only one of Def or Use will be set. |
| Value *Def = nullptr; |
| Use *U = nullptr; |
| // Neither PInfo nor EdgeOnly participate in the ordering |
| PredicateBase *PInfo = nullptr; |
| bool EdgeOnly = false; |
| }; |
| |
| // Perform a strict weak ordering on instructions and arguments. |
| static bool valueComesBefore(OrderedInstructions &OI, const Value *A, |
| const Value *B) { |
| auto *ArgA = dyn_cast_or_null<Argument>(A); |
| auto *ArgB = dyn_cast_or_null<Argument>(B); |
| if (ArgA && !ArgB) |
| return true; |
| if (ArgB && !ArgA) |
| return false; |
| if (ArgA && ArgB) |
| return ArgA->getArgNo() < ArgB->getArgNo(); |
| return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B)); |
| } |
| |
| // This compares ValueDFS structures, creating OrderedBasicBlocks where |
| // necessary to compare uses/defs in the same block. Doing so allows us to walk |
| // the minimum number of instructions necessary to compute our def/use ordering. |
| struct ValueDFS_Compare { |
| DominatorTree &DT; |
| OrderedInstructions &OI; |
| ValueDFS_Compare(DominatorTree &DT, OrderedInstructions &OI) |
| : DT(DT), OI(OI) {} |
| |
| bool operator()(const ValueDFS &A, const ValueDFS &B) const { |
| if (&A == &B) |
| return false; |
| // The only case we can't directly compare them is when they in the same |
| // block, and both have localnum == middle. In that case, we have to use |
| // comesbefore to see what the real ordering is, because they are in the |
| // same basic block. |
| |
| assert((A.DFSIn != B.DFSIn || A.DFSOut == B.DFSOut) && |
| "Equal DFS-in numbers imply equal out numbers"); |
| bool SameBlock = A.DFSIn == B.DFSIn; |
| |
| // We want to put the def that will get used for a given set of phi uses, |
| // before those phi uses. |
| // So we sort by edge, then by def. |
| // Note that only phi nodes uses and defs can come last. |
| if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last) |
| return comparePHIRelated(A, B); |
| |
| bool isADef = A.Def; |
| bool isBDef = B.Def; |
| if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle) |
| return std::tie(A.DFSIn, A.LocalNum, isADef) < |
| std::tie(B.DFSIn, B.LocalNum, isBDef); |
| return localComesBefore(A, B); |
| } |
| |
| // For a phi use, or a non-materialized def, return the edge it represents. |
| const std::pair<BasicBlock *, BasicBlock *> |
| getBlockEdge(const ValueDFS &VD) const { |
| if (!VD.Def && VD.U) { |
| auto *PHI = cast<PHINode>(VD.U->getUser()); |
| return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent()); |
| } |
| // This is really a non-materialized def. |
| return ::getBlockEdge(VD.PInfo); |
| } |
| |
| // For two phi related values, return the ordering. |
| bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const { |
| BasicBlock *ASrc, *ADest, *BSrc, *BDest; |
| std::tie(ASrc, ADest) = getBlockEdge(A); |
| std::tie(BSrc, BDest) = getBlockEdge(B); |
| |
| #ifndef NDEBUG |
| // This function should only be used for values in the same BB, check that. |
| DomTreeNode *DomASrc = DT.getNode(ASrc); |
| DomTreeNode *DomBSrc = DT.getNode(BSrc); |
| assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn && |
| "DFS numbers for A should match the ones of the source block"); |
| assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn && |
| "DFS numbers for B should match the ones of the source block"); |
| assert(A.DFSIn == B.DFSIn && "Values must be in the same block"); |
| #endif |
| (void)ASrc; |
| (void)BSrc; |
| |
| // Use DFS numbers to compare destination blocks, to guarantee a |
| // deterministic order. |
| DomTreeNode *DomADest = DT.getNode(ADest); |
| DomTreeNode *DomBDest = DT.getNode(BDest); |
| unsigned AIn = DomADest->getDFSNumIn(); |
| unsigned BIn = DomBDest->getDFSNumIn(); |
| bool isADef = A.Def; |
| bool isBDef = B.Def; |
| assert((!A.Def || !A.U) && (!B.Def || !B.U) && |
| "Def and U cannot be set at the same time"); |
| // Now sort by edge destination and then defs before uses. |
| return std::tie(AIn, isADef) < std::tie(BIn, isBDef); |
| } |
| |
| // Get the definition of an instruction that occurs in the middle of a block. |
| Value *getMiddleDef(const ValueDFS &VD) const { |
| if (VD.Def) |
| return VD.Def; |
| // It's possible for the defs and uses to be null. For branches, the local |
| // numbering will say the placed predicaeinfos should go first (IE |
| // LN_beginning), so we won't be in this function. For assumes, we will end |
| // up here, beause we need to order the def we will place relative to the |
| // assume. So for the purpose of ordering, we pretend the def is the assume |
| // because that is where we will insert the info. |
| if (!VD.U) { |
| assert(VD.PInfo && |
| "No def, no use, and no predicateinfo should not occur"); |
| assert(isa<PredicateAssume>(VD.PInfo) && |
| "Middle of block should only occur for assumes"); |
| return cast<PredicateAssume>(VD.PInfo)->AssumeInst; |
| } |
| return nullptr; |
| } |
| |
| // Return either the Def, if it's not null, or the user of the Use, if the def |
| // is null. |
| const Instruction *getDefOrUser(const Value *Def, const Use *U) const { |
| if (Def) |
| return cast<Instruction>(Def); |
| return cast<Instruction>(U->getUser()); |
| } |
| |
| // This performs the necessary local basic block ordering checks to tell |
| // whether A comes before B, where both are in the same basic block. |
| bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const { |
| auto *ADef = getMiddleDef(A); |
| auto *BDef = getMiddleDef(B); |
| |
| // See if we have real values or uses. If we have real values, we are |
| // guaranteed they are instructions or arguments. No matter what, we are |
| // guaranteed they are in the same block if they are instructions. |
| auto *ArgA = dyn_cast_or_null<Argument>(ADef); |
| auto *ArgB = dyn_cast_or_null<Argument>(BDef); |
| |
| if (ArgA || ArgB) |
| return valueComesBefore(OI, ArgA, ArgB); |
| |
| auto *AInst = getDefOrUser(ADef, A.U); |
| auto *BInst = getDefOrUser(BDef, B.U); |
| return valueComesBefore(OI, AInst, BInst); |
| } |
| }; |
| |
| } // namespace PredicateInfoClasses |
| |
| bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, |
| const ValueDFS &VDUse) const { |
| if (Stack.empty()) |
| return false; |
| // If it's a phi only use, make sure it's for this phi node edge, and that the |
| // use is in a phi node. If it's anything else, and the top of the stack is |
| // EdgeOnly, we need to pop the stack. We deliberately sort phi uses next to |
| // the defs they must go with so that we can know it's time to pop the stack |
| // when we hit the end of the phi uses for a given def. |
| if (Stack.back().EdgeOnly) { |
| if (!VDUse.U) |
| return false; |
| auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser()); |
| if (!PHI) |
| return false; |
| // Check edge |
| BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U); |
| if (EdgePred != getBranchBlock(Stack.back().PInfo)) |
| return false; |
| |
| // Use dominates, which knows how to handle edge dominance. |
| return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U); |
| } |
| |
| return (VDUse.DFSIn >= Stack.back().DFSIn && |
| VDUse.DFSOut <= Stack.back().DFSOut); |
| } |
| |
| void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack, |
| const ValueDFS &VD) { |
| while (!Stack.empty() && !stackIsInScope(Stack, VD)) |
| Stack.pop_back(); |
| } |
| |
| // Convert the uses of Op into a vector of uses, associating global and local |
| // DFS info with each one. |
| void PredicateInfo::convertUsesToDFSOrdered( |
| Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) { |
| for (auto &U : Op->uses()) { |
| if (auto *I = dyn_cast<Instruction>(U.getUser())) { |
| ValueDFS VD; |
| // Put the phi node uses in the incoming block. |
| BasicBlock *IBlock; |
| if (auto *PN = dyn_cast<PHINode>(I)) { |
| IBlock = PN->getIncomingBlock(U); |
| // Make phi node users appear last in the incoming block |
| // they are from. |
| VD.LocalNum = LN_Last; |
| } else { |
| // If it's not a phi node use, it is somewhere in the middle of the |
| // block. |
| IBlock = I->getParent(); |
| VD.LocalNum = LN_Middle; |
| } |
| DomTreeNode *DomNode = DT.getNode(IBlock); |
| // It's possible our use is in an unreachable block. Skip it if so. |
| if (!DomNode) |
| continue; |
| VD.DFSIn = DomNode->getDFSNumIn(); |
| VD.DFSOut = DomNode->getDFSNumOut(); |
| VD.U = &U; |
| DFSOrderedSet.push_back(VD); |
| } |
| } |
| } |
| |
| // Collect relevant operations from Comparison that we may want to insert copies |
| // for. |
| void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) { |
| auto *Op0 = Comparison->getOperand(0); |
| auto *Op1 = Comparison->getOperand(1); |
| if (Op0 == Op1) |
| return; |
| CmpOperands.push_back(Comparison); |
| // Only want real values, not constants. Additionally, operands with one use |
| // are only being used in the comparison, which means they will not be useful |
| // for us to consider for predicateinfo. |
| // |
| if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse()) |
| CmpOperands.push_back(Op0); |
| if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse()) |
| CmpOperands.push_back(Op1); |
| } |
| |
| // Add Op, PB to the list of value infos for Op, and mark Op to be renamed. |
| void PredicateInfo::addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op, |
| PredicateBase *PB) { |
| auto &OperandInfo = getOrCreateValueInfo(Op); |
| if (OperandInfo.Infos.empty()) |
| OpsToRename.push_back(Op); |
| AllInfos.push_back(PB); |
| OperandInfo.Infos.push_back(PB); |
| } |
| |
| // Process an assume instruction and place relevant operations we want to rename |
| // into OpsToRename. |
| void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB, |
| SmallVectorImpl<Value *> &OpsToRename) { |
| // See if we have a comparison we support |
| SmallVector<Value *, 8> CmpOperands; |
| SmallVector<Value *, 2> ConditionsToProcess; |
| CmpInst::Predicate Pred; |
| Value *Operand = II->getOperand(0); |
| if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), |
| m_Cmp(Pred, m_Value(), m_Value())) |
| .match(II->getOperand(0))) { |
| ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0)); |
| ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1)); |
| ConditionsToProcess.push_back(Operand); |
| } else if (isa<CmpInst>(Operand)) { |
| |
| ConditionsToProcess.push_back(Operand); |
| } |
| for (auto Cond : ConditionsToProcess) { |
| if (auto *Cmp = dyn_cast<CmpInst>(Cond)) { |
| collectCmpOps(Cmp, CmpOperands); |
| // Now add our copy infos for our operands |
| for (auto *Op : CmpOperands) { |
| auto *PA = new PredicateAssume(Op, II, Cmp); |
| addInfoFor(OpsToRename, Op, PA); |
| } |
| CmpOperands.clear(); |
| } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) { |
| // Otherwise, it should be an AND. |
| assert(BinOp->getOpcode() == Instruction::And && |
| "Should have been an AND"); |
| auto *PA = new PredicateAssume(BinOp, II, BinOp); |
| addInfoFor(OpsToRename, BinOp, PA); |
| } else { |
| llvm_unreachable("Unknown type of condition"); |
| } |
| } |
| } |
| |
| // Process a block terminating branch, and place relevant operations to be |
| // renamed into OpsToRename. |
| void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB, |
| SmallVectorImpl<Value *> &OpsToRename) { |
| BasicBlock *FirstBB = BI->getSuccessor(0); |
| BasicBlock *SecondBB = BI->getSuccessor(1); |
| SmallVector<BasicBlock *, 2> SuccsToProcess; |
| SuccsToProcess.push_back(FirstBB); |
| SuccsToProcess.push_back(SecondBB); |
| SmallVector<Value *, 2> ConditionsToProcess; |
| |
| auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) { |
| for (auto *Succ : SuccsToProcess) { |
| // Don't try to insert on a self-edge. This is mainly because we will |
| // eliminate during renaming anyway. |
| if (Succ == BranchBB) |
| continue; |
| bool TakenEdge = (Succ == FirstBB); |
| // For and, only insert on the true edge |
| // For or, only insert on the false edge |
| if ((isAnd && !TakenEdge) || (isOr && TakenEdge)) |
| continue; |
| PredicateBase *PB = |
| new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge); |
| addInfoFor(OpsToRename, Op, PB); |
| if (!Succ->getSinglePredecessor()) |
| EdgeUsesOnly.insert({BranchBB, Succ}); |
| } |
| }; |
| |
| // Match combinations of conditions. |
| CmpInst::Predicate Pred; |
| bool isAnd = false; |
| bool isOr = false; |
| SmallVector<Value *, 8> CmpOperands; |
| if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()), |
| m_Cmp(Pred, m_Value(), m_Value()))) || |
| match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()), |
| m_Cmp(Pred, m_Value(), m_Value())))) { |
| auto *BinOp = cast<BinaryOperator>(BI->getCondition()); |
| if (BinOp->getOpcode() == Instruction::And) |
| isAnd = true; |
| else if (BinOp->getOpcode() == Instruction::Or) |
| isOr = true; |
| ConditionsToProcess.push_back(BinOp->getOperand(0)); |
| ConditionsToProcess.push_back(BinOp->getOperand(1)); |
| ConditionsToProcess.push_back(BI->getCondition()); |
| } else if (isa<CmpInst>(BI->getCondition())) { |
| ConditionsToProcess.push_back(BI->getCondition()); |
| } |
| for (auto Cond : ConditionsToProcess) { |
| if (auto *Cmp = dyn_cast<CmpInst>(Cond)) { |
| collectCmpOps(Cmp, CmpOperands); |
| // Now add our copy infos for our operands |
| for (auto *Op : CmpOperands) |
| InsertHelper(Op, isAnd, isOr, Cmp); |
| } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) { |
| // This must be an AND or an OR. |
| assert((BinOp->getOpcode() == Instruction::And || |
| BinOp->getOpcode() == Instruction::Or) && |
| "Should have been an AND or an OR"); |
| // The actual value of the binop is not subject to the same restrictions |
| // as the comparison. It's either true or false on the true/false branch. |
| InsertHelper(BinOp, false, false, BinOp); |
| } else { |
| llvm_unreachable("Unknown type of condition"); |
| } |
| CmpOperands.clear(); |
| } |
| } |
| // Process a block terminating switch, and place relevant operations to be |
| // renamed into OpsToRename. |
| void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB, |
| SmallVectorImpl<Value *> &OpsToRename) { |
| Value *Op = SI->getCondition(); |
| if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse()) |
| return; |
| |
| // Remember how many outgoing edges there are to every successor. |
| SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges; |
| for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { |
| BasicBlock *TargetBlock = SI->getSuccessor(i); |
| ++SwitchEdges[TargetBlock]; |
| } |
| |
| // Now propagate info for each case value |
| for (auto C : SI->cases()) { |
| BasicBlock *TargetBlock = C.getCaseSuccessor(); |
| if (SwitchEdges.lookup(TargetBlock) == 1) { |
| PredicateSwitch *PS = new PredicateSwitch( |
| Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI); |
| addInfoFor(OpsToRename, Op, PS); |
| if (!TargetBlock->getSinglePredecessor()) |
| EdgeUsesOnly.insert({BranchBB, TargetBlock}); |
| } |
| } |
| } |
| |
| // Build predicate info for our function |
| void PredicateInfo::buildPredicateInfo() { |
| DT.updateDFSNumbers(); |
| // Collect operands to rename from all conditional branch terminators, as well |
| // as assume statements. |
| SmallVector<Value *, 8> OpsToRename; |
| for (auto DTN : depth_first(DT.getRootNode())) { |
| BasicBlock *BranchBB = DTN->getBlock(); |
| if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) { |
| if (!BI->isConditional()) |
| continue; |
| // Can't insert conditional information if they all go to the same place. |
| if (BI->getSuccessor(0) == BI->getSuccessor(1)) |
| continue; |
| processBranch(BI, BranchBB, OpsToRename); |
| } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) { |
| processSwitch(SI, BranchBB, OpsToRename); |
| } |
| } |
| for (auto &Assume : AC.assumptions()) { |
| if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume)) |
| if (DT.isReachableFromEntry(II->getParent())) |
| processAssume(II, II->getParent(), OpsToRename); |
| } |
| // Now rename all our operations. |
| renameUses(OpsToRename); |
| } |
| |
| // Create a ssa_copy declaration with custom mangling, because |
| // Intrinsic::getDeclaration does not handle overloaded unnamed types properly: |
| // all unnamed types get mangled to the same string. We use the pointer |
| // to the type as name here, as it guarantees unique names for different |
| // types and we remove the declarations when destroying PredicateInfo. |
| // It is a workaround for PR38117, because solving it in a fully general way is |
| // tricky (FIXME). |
| static Function *getCopyDeclaration(Module *M, Type *Ty) { |
| std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty); |
| return cast<Function>( |
| M->getOrInsertFunction(Name, |
| getType(M->getContext(), Intrinsic::ssa_copy, Ty)) |
| .getCallee()); |
| } |
| |
| // Given the renaming stack, make all the operands currently on the stack real |
| // by inserting them into the IR. Return the last operation's value. |
| Value *PredicateInfo::materializeStack(unsigned int &Counter, |
| ValueDFSStack &RenameStack, |
| Value *OrigOp) { |
| // Find the first thing we have to materialize |
| auto RevIter = RenameStack.rbegin(); |
| for (; RevIter != RenameStack.rend(); ++RevIter) |
| if (RevIter->Def) |
| break; |
| |
| size_t Start = RevIter - RenameStack.rbegin(); |
| // The maximum number of things we should be trying to materialize at once |
| // right now is 4, depending on if we had an assume, a branch, and both used |
| // and of conditions. |
| for (auto RenameIter = RenameStack.end() - Start; |
| RenameIter != RenameStack.end(); ++RenameIter) { |
| auto *Op = |
| RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def; |
| ValueDFS &Result = *RenameIter; |
| auto *ValInfo = Result.PInfo; |
| // For edge predicates, we can just place the operand in the block before |
| // the terminator. For assume, we have to place it right before the assume |
| // to ensure we dominate all of our uses. Always insert right before the |
| // relevant instruction (terminator, assume), so that we insert in proper |
| // order in the case of multiple predicateinfo in the same block. |
| if (isa<PredicateWithEdge>(ValInfo)) { |
| IRBuilder<> B(getBranchTerminator(ValInfo)); |
| Function *IF = getCopyDeclaration(F.getParent(), Op->getType()); |
| if (IF->users().empty()) |
| CreatedDeclarations.insert(IF); |
| CallInst *PIC = |
| B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++)); |
| PredicateMap.insert({PIC, ValInfo}); |
| Result.Def = PIC; |
| } else { |
| auto *PAssume = dyn_cast<PredicateAssume>(ValInfo); |
| assert(PAssume && |
| "Should not have gotten here without it being an assume"); |
| IRBuilder<> B(PAssume->AssumeInst); |
| Function *IF = getCopyDeclaration(F.getParent(), Op->getType()); |
| if (IF->users().empty()) |
| CreatedDeclarations.insert(IF); |
| CallInst *PIC = B.CreateCall(IF, Op); |
| PredicateMap.insert({PIC, ValInfo}); |
| Result.Def = PIC; |
| } |
| } |
| return RenameStack.back().Def; |
| } |
| |
| // Instead of the standard SSA renaming algorithm, which is O(Number of |
| // instructions), and walks the entire dominator tree, we walk only the defs + |
| // uses. The standard SSA renaming algorithm does not really rely on the |
| // dominator tree except to order the stack push/pops of the renaming stacks, so |
| // that defs end up getting pushed before hitting the correct uses. This does |
| // not require the dominator tree, only the *order* of the dominator tree. The |
| // complete and correct ordering of the defs and uses, in dominator tree is |
| // contained in the DFS numbering of the dominator tree. So we sort the defs and |
| // uses into the DFS ordering, and then just use the renaming stack as per |
| // normal, pushing when we hit a def (which is a predicateinfo instruction), |
| // popping when we are out of the dfs scope for that def, and replacing any uses |
| // with top of stack if it exists. In order to handle liveness without |
| // propagating liveness info, we don't actually insert the predicateinfo |
| // instruction def until we see a use that it would dominate. Once we see such |
| // a use, we materialize the predicateinfo instruction in the right place and |
| // use it. |
| // |
| // TODO: Use this algorithm to perform fast single-variable renaming in |
| // promotememtoreg and memoryssa. |
| void PredicateInfo::renameUses(SmallVectorImpl<Value *> &OpsToRename) { |
| ValueDFS_Compare Compare(DT, OI); |
| // Compute liveness, and rename in O(uses) per Op. |
| for (auto *Op : OpsToRename) { |
| LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n"); |
| unsigned Counter = 0; |
| SmallVector<ValueDFS, 16> OrderedUses; |
| const auto &ValueInfo = getValueInfo(Op); |
| // Insert the possible copies into the def/use list. |
| // They will become real copies if we find a real use for them, and never |
| // created otherwise. |
| for (auto &PossibleCopy : ValueInfo.Infos) { |
| ValueDFS VD; |
| // Determine where we are going to place the copy by the copy type. |
| // The predicate info for branches always come first, they will get |
| // materialized in the split block at the top of the block. |
| // The predicate info for assumes will be somewhere in the middle, |
| // it will get materialized in front of the assume. |
| if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) { |
| VD.LocalNum = LN_Middle; |
| DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent()); |
| if (!DomNode) |
| continue; |
| VD.DFSIn = DomNode->getDFSNumIn(); |
| VD.DFSOut = DomNode->getDFSNumOut(); |
| VD.PInfo = PossibleCopy; |
| OrderedUses.push_back(VD); |
| } else if (isa<PredicateWithEdge>(PossibleCopy)) { |
| // If we can only do phi uses, we treat it like it's in the branch |
| // block, and handle it specially. We know that it goes last, and only |
| // dominate phi uses. |
| auto BlockEdge = getBlockEdge(PossibleCopy); |
| if (EdgeUsesOnly.count(BlockEdge)) { |
| VD.LocalNum = LN_Last; |
| auto *DomNode = DT.getNode(BlockEdge.first); |
| if (DomNode) { |
| VD.DFSIn = DomNode->getDFSNumIn(); |
| VD.DFSOut = DomNode->getDFSNumOut(); |
| VD.PInfo = PossibleCopy; |
| VD.EdgeOnly = true; |
| OrderedUses.push_back(VD); |
| } |
| } else { |
| // Otherwise, we are in the split block (even though we perform |
| // insertion in the branch block). |
| // Insert a possible copy at the split block and before the branch. |
| VD.LocalNum = LN_First; |
| auto *DomNode = DT.getNode(BlockEdge.second); |
| if (DomNode) { |
| VD.DFSIn = DomNode->getDFSNumIn(); |
| VD.DFSOut = DomNode->getDFSNumOut(); |
| VD.PInfo = PossibleCopy; |
| OrderedUses.push_back(VD); |
| } |
| } |
| } |
| } |
| |
| convertUsesToDFSOrdered(Op, OrderedUses); |
| // Here we require a stable sort because we do not bother to try to |
| // assign an order to the operands the uses represent. Thus, two |
| // uses in the same instruction do not have a strict sort order |
| // currently and will be considered equal. We could get rid of the |
| // stable sort by creating one if we wanted. |
| llvm::stable_sort(OrderedUses, Compare); |
| SmallVector<ValueDFS, 8> RenameStack; |
| // For each use, sorted into dfs order, push values and replaces uses with |
| // top of stack, which will represent the reaching def. |
| for (auto &VD : OrderedUses) { |
| // We currently do not materialize copy over copy, but we should decide if |
| // we want to. |
| bool PossibleCopy = VD.PInfo != nullptr; |
| if (RenameStack.empty()) { |
| LLVM_DEBUG(dbgs() << "Rename Stack is empty\n"); |
| } else { |
| LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are (" |
| << RenameStack.back().DFSIn << "," |
| << RenameStack.back().DFSOut << ")\n"); |
| } |
| |
| LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << "," |
| << VD.DFSOut << ")\n"); |
| |
| bool ShouldPush = (VD.Def || PossibleCopy); |
| bool OutOfScope = !stackIsInScope(RenameStack, VD); |
| if (OutOfScope || ShouldPush) { |
| // Sync to our current scope. |
| popStackUntilDFSScope(RenameStack, VD); |
| if (ShouldPush) { |
| RenameStack.push_back(VD); |
| } |
| } |
| // If we get to this point, and the stack is empty we must have a use |
| // with no renaming needed, just skip it. |
| if (RenameStack.empty()) |
| continue; |
| // Skip values, only want to rename the uses |
| if (VD.Def || PossibleCopy) |
| continue; |
| if (!DebugCounter::shouldExecute(RenameCounter)) { |
| LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n"); |
| continue; |
| } |
| ValueDFS &Result = RenameStack.back(); |
| |
| // If the possible copy dominates something, materialize our stack up to |
| // this point. This ensures every comparison that affects our operation |
| // ends up with predicateinfo. |
| if (!Result.Def) |
| Result.Def = materializeStack(Counter, RenameStack, Op); |
| |
| LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for " |
| << *VD.U->get() << " in " << *(VD.U->getUser()) |
| << "\n"); |
| assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) && |
| "Predicateinfo def should have dominated this use"); |
| VD.U->set(Result.Def); |
| } |
| } |
| } |
| |
| PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) { |
| auto OIN = ValueInfoNums.find(Operand); |
| if (OIN == ValueInfoNums.end()) { |
| // This will grow it |
| ValueInfos.resize(ValueInfos.size() + 1); |
| // This will use the new size and give us a 0 based number of the info |
| auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1}); |
| assert(InsertResult.second && "Value info number already existed?"); |
| return ValueInfos[InsertResult.first->second]; |
| } |
| return ValueInfos[OIN->second]; |
| } |
| |
| const PredicateInfo::ValueInfo & |
| PredicateInfo::getValueInfo(Value *Operand) const { |
| auto OINI = ValueInfoNums.lookup(Operand); |
| assert(OINI != 0 && "Operand was not really in the Value Info Numbers"); |
| assert(OINI < ValueInfos.size() && |
| "Value Info Number greater than size of Value Info Table"); |
| return ValueInfos[OINI]; |
| } |
| |
| PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT, |
| AssumptionCache &AC) |
| : F(F), DT(DT), AC(AC), OI(&DT) { |
| // Push an empty operand info so that we can detect 0 as not finding one |
| ValueInfos.resize(1); |
| buildPredicateInfo(); |
| } |
| |
| // Remove all declarations we created . The PredicateInfo consumers are |
| // responsible for remove the ssa_copy calls created. |
| PredicateInfo::~PredicateInfo() { |
| // Collect function pointers in set first, as SmallSet uses a SmallVector |
| // internally and we have to remove the asserting value handles first. |
| SmallPtrSet<Function *, 20> FunctionPtrs; |
| for (auto &F : CreatedDeclarations) |
| FunctionPtrs.insert(&*F); |
| CreatedDeclarations.clear(); |
| |
| for (Function *F : FunctionPtrs) { |
| assert(F->user_begin() == F->user_end() && |
| "PredicateInfo consumer did not remove all SSA copies."); |
| F->eraseFromParent(); |
| } |
| } |
| |
| void PredicateInfo::verifyPredicateInfo() const {} |
| |
| char PredicateInfoPrinterLegacyPass::ID = 0; |
| |
| PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass() |
| : FunctionPass(ID) { |
| initializePredicateInfoPrinterLegacyPassPass( |
| *PassRegistry::getPassRegistry()); |
| } |
| |
| void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.setPreservesAll(); |
| AU.addRequiredTransitive<DominatorTreeWrapperPass>(); |
| AU.addRequired<AssumptionCacheTracker>(); |
| } |
| |
| // Replace ssa_copy calls created by PredicateInfo with their operand. |
| static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) { |
| for (auto I = inst_begin(F), E = inst_end(F); I != E;) { |
| Instruction *Inst = &*I++; |
| const auto *PI = PredInfo.getPredicateInfoFor(Inst); |
| auto *II = dyn_cast<IntrinsicInst>(Inst); |
| if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy) |
| continue; |
| |
| Inst->replaceAllUsesWith(II->getOperand(0)); |
| Inst->eraseFromParent(); |
| } |
| } |
| |
| bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) { |
| auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
| auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); |
| auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC); |
| PredInfo->print(dbgs()); |
| if (VerifyPredicateInfo) |
| PredInfo->verifyPredicateInfo(); |
| |
| replaceCreatedSSACopys(*PredInfo, F); |
| return false; |
| } |
| |
| PreservedAnalyses PredicateInfoPrinterPass::run(Function &F, |
| FunctionAnalysisManager &AM) { |
| auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
| auto &AC = AM.getResult<AssumptionAnalysis>(F); |
| OS << "PredicateInfo for function: " << F.getName() << "\n"; |
| auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC); |
| PredInfo->print(OS); |
| |
| replaceCreatedSSACopys(*PredInfo, F); |
| return PreservedAnalyses::all(); |
| } |
| |
| /// An assembly annotator class to print PredicateInfo information in |
| /// comments. |
| class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter { |
| friend class PredicateInfo; |
| const PredicateInfo *PredInfo; |
| |
| public: |
| PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {} |
| |
| virtual void emitBasicBlockStartAnnot(const BasicBlock *BB, |
| formatted_raw_ostream &OS) {} |
| |
| virtual void emitInstructionAnnot(const Instruction *I, |
| formatted_raw_ostream &OS) { |
| if (const auto *PI = PredInfo->getPredicateInfoFor(I)) { |
| OS << "; Has predicate info\n"; |
| if (const auto *PB = dyn_cast<PredicateBranch>(PI)) { |
| OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge |
| << " Comparison:" << *PB->Condition << " Edge: ["; |
| PB->From->printAsOperand(OS); |
| OS << ","; |
| PB->To->printAsOperand(OS); |
| OS << "] }\n"; |
| } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) { |
| OS << "; switch predicate info { CaseValue: " << *PS->CaseValue |
| << " Switch:" << *PS->Switch << " Edge: ["; |
| PS->From->printAsOperand(OS); |
| OS << ","; |
| PS->To->printAsOperand(OS); |
| OS << "] }\n"; |
| } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) { |
| OS << "; assume predicate info {" |
| << " Comparison:" << *PA->Condition << " }\n"; |
| } |
| } |
| } |
| }; |
| |
| void PredicateInfo::print(raw_ostream &OS) const { |
| PredicateInfoAnnotatedWriter Writer(this); |
| F.print(OS, &Writer); |
| } |
| |
| void PredicateInfo::dump() const { |
| PredicateInfoAnnotatedWriter Writer(this); |
| F.print(dbgs(), &Writer); |
| } |
| |
| PreservedAnalyses PredicateInfoVerifierPass::run(Function &F, |
| FunctionAnalysisManager &AM) { |
| auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
| auto &AC = AM.getResult<AssumptionAnalysis>(F); |
| std::make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo(); |
| |
| return PreservedAnalyses::all(); |
| } |
| } |
