Index: include/llvm/Transforms/Utils/PredicateInfo.h =================================================================== --- include/llvm/Transforms/Utils/PredicateInfo.h +++ include/llvm/Transforms/Utils/PredicateInfo.h @@ -51,42 +51,22 @@ #define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" -#include "llvm/ADT/iterator.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/OrderedInstructions.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/OperandTraits.h" -#include "llvm/IR/Type.h" -#include "llvm/IR/Use.h" -#include "llvm/IR/User.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" #include "llvm/PassAnalysisSupport.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/ErrorHandling.h" -#include -#include -#include -#include -#include -#include namespace llvm { +class AssumptionCache; class DominatorTree; class Function; +class IntrinsicInst; class raw_ostream; enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; @@ -186,23 +166,9 @@ } }; -// This name is used in a few places, so kick it into their own namespace -namespace PredicateInfoClasses { -struct ValueDFS; -} - /// Encapsulates PredicateInfo, including all data associated with memory /// accesses. class PredicateInfo { -private: - // Used to store information about each value we might rename. - struct ValueInfo { - // Information about each possible copy. - SmallVector Infos; - }; - // This owns the all the predicate infos in the function, placed or not. - iplist AllInfos; - public: PredicateInfo(Function &, DominatorTree &, AssumptionCache &); ~PredicateInfo(); @@ -220,42 +186,18 @@ // Used by PredicateInfo annotater, dumpers, and wrapper pass. friend class PredicateInfoAnnotatedWriter; friend class PredicateInfoPrinterLegacyPass; + friend class PredicateInfoBuilder; private: - void buildPredicateInfo(); - void processAssume(IntrinsicInst *, BasicBlock *, SmallVectorImpl &); - void processBranch(BranchInst *, BasicBlock *, SmallVectorImpl &); - void processSwitch(SwitchInst *, BasicBlock *, SmallVectorImpl &); - void renameUses(SmallVectorImpl &); - using ValueDFS = PredicateInfoClasses::ValueDFS; - typedef SmallVectorImpl ValueDFSStack; - void convertUsesToDFSOrdered(Value *, SmallVectorImpl &); - Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); - bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; - void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); - ValueInfo &getOrCreateValueInfo(Value *); - void addInfoFor(SmallVectorImpl &OpsToRename, Value *Op, - PredicateBase *PB); - const ValueInfo &getValueInfo(Value *) const; Function &F; - DominatorTree &DT; - AssumptionCache &AC; - OrderedInstructions OI; + + // This owns the all the predicate infos in the function, placed or not. + iplist AllInfos; + // This maps from copy operands to Predicate Info. Note that it does not own // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos // vector. DenseMap PredicateMap; - // This stores info about each operand or comparison result we make copies - // of. The real ValueInfos start at index 1, index 0 is unused so that we can - // more easily detect invalid indexing. - SmallVector ValueInfos; - // This gives the index into the ValueInfos array for a given Value. Because - // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell - // whether it returned a valid result. - DenseMap ValueInfoNums; - // The set of edges along which we can only handle phi uses, due to critical - // edges. - DenseSet> EdgeUsesOnly; // The set of ssa_copy declarations we created with our custom mangling. SmallSet, 20> CreatedDeclarations; }; Index: lib/Transforms/Utils/PredicateInfo.cpp =================================================================== --- lib/Transforms/Utils/PredicateInfo.cpp +++ lib/Transforms/Utils/PredicateInfo.cpp @@ -19,6 +19,7 @@ #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/OrderedInstructions.h" #include "llvm/IR/AssemblyAnnotationWriter.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" @@ -39,7 +40,6 @@ #define DEBUG_TYPE "predicateinfo" using namespace llvm; using namespace PatternMatch; -using namespace llvm::PredicateInfoClasses; INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo", "PredicateInfo Printer", false, false) @@ -80,10 +80,10 @@ const auto *PEdge = cast(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, @@ -251,10 +251,62 @@ } }; -} // namespace PredicateInfoClasses +class PredicateInfoBuilder { + // Used to store information about each value we might rename. + struct ValueInfo { + SmallVector Infos; + }; + + PredicateInfo &PI; + Function &F; + DominatorTree &DT; + AssumptionCache &AC; + OrderedInstructions OI; + + SmallVector OpsToRename; + + // This stores info about each operand or comparison result we make copies + // of. The real ValueInfos start at index 1, index 0 is unused so that we + // can more easily detect invalid indexing. + SmallVector ValueInfos; + + // This gives the index into the ValueInfos array for a given Value. Because + // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell + // whether it returned a valid result. + DenseMap ValueInfoNums; + + // The set of edges along which we can only handle phi uses, due to critical + // edges. + DenseSet> EdgeUsesOnly; -bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, - const ValueDFS &VDUse) const { + ValueInfo &getOrCreateValueInfo(Value *); + const ValueInfo &getValueInfo(Value *) const; + + void processAssume(IntrinsicInst *, BasicBlock *); + void processBranch(BranchInst *, BasicBlock *); + void processSwitch(SwitchInst *, BasicBlock *); + void renameUses(); + void addInfoFor(Value *Op, PredicateBase *PB); + + typedef SmallVectorImpl ValueDFSStack; + void convertUsesToDFSOrdered(Value *, SmallVectorImpl &); + Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); + bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; + void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); + +public: + PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT, + AssumptionCache &AC) + : PI(PI), 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); + } + + void buildPredicateInfo(); +}; + +bool PredicateInfoBuilder::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 @@ -281,15 +333,15 @@ VDUse.DFSOut <= Stack.back().DFSOut); } -void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack, - const ValueDFS &VD) { +void PredicateInfoBuilder::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( +void PredicateInfoBuilder::convertUsesToDFSOrdered( Value *Op, SmallVectorImpl &DFSOrderedSet) { for (auto &U : Op->uses()) { if (auto *I = dyn_cast(U.getUser())) { @@ -338,19 +390,18 @@ } // Add Op, PB to the list of value infos for Op, and mark Op to be renamed. -void PredicateInfo::addInfoFor(SmallVectorImpl &OpsToRename, Value *Op, - PredicateBase *PB) { +void PredicateInfoBuilder::addInfoFor(Value *Op, PredicateBase *PB) { auto &OperandInfo = getOrCreateValueInfo(Op); if (OperandInfo.Infos.empty()) OpsToRename.push_back(Op); - AllInfos.push_back(PB); + PI.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 &OpsToRename) { +void PredicateInfoBuilder::processAssume(IntrinsicInst *II, + BasicBlock *AssumeBB) { // See if we have a comparison we support SmallVector CmpOperands; SmallVector ConditionsToProcess; @@ -372,7 +423,7 @@ // Now add our copy infos for our operands for (auto *Op : CmpOperands) { auto *PA = new PredicateAssume(Op, II, Cmp); - addInfoFor(OpsToRename, Op, PA); + addInfoFor(Op, PA); } CmpOperands.clear(); } else if (auto *BinOp = dyn_cast(Cond)) { @@ -380,7 +431,7 @@ assert(BinOp->getOpcode() == Instruction::And && "Should have been an AND"); auto *PA = new PredicateAssume(BinOp, II, BinOp); - addInfoFor(OpsToRename, BinOp, PA); + addInfoFor(BinOp, PA); } else { llvm_unreachable("Unknown type of condition"); } @@ -389,8 +440,7 @@ // Process a block terminating branch, and place relevant operations to be // renamed into OpsToRename. -void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB, - SmallVectorImpl &OpsToRename) { +void PredicateInfoBuilder::processBranch(BranchInst *BI, BasicBlock *BranchBB) { BasicBlock *FirstBB = BI->getSuccessor(0); BasicBlock *SecondBB = BI->getSuccessor(1); SmallVector SuccsToProcess; @@ -411,7 +461,7 @@ continue; PredicateBase *PB = new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge); - addInfoFor(OpsToRename, Op, PB); + addInfoFor(Op, PB); if (!Succ->getSinglePredecessor()) EdgeUsesOnly.insert({BranchBB, Succ}); } @@ -459,8 +509,7 @@ } // Process a block terminating switch, and place relevant operations to be // renamed into OpsToRename. -void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB, - SmallVectorImpl &OpsToRename) { +void PredicateInfoBuilder::processSwitch(SwitchInst *SI, BasicBlock *BranchBB) { Value *Op = SI->getCondition(); if ((!isa(Op) && !isa(Op)) || Op->hasOneUse()) return; @@ -478,7 +527,7 @@ if (SwitchEdges.lookup(TargetBlock) == 1) { PredicateSwitch *PS = new PredicateSwitch( Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI); - addInfoFor(OpsToRename, Op, PS); + addInfoFor(Op, PS); if (!TargetBlock->getSinglePredecessor()) EdgeUsesOnly.insert({BranchBB, TargetBlock}); } @@ -486,11 +535,10 @@ } // Build predicate info for our function -void PredicateInfo::buildPredicateInfo() { +void PredicateInfoBuilder::buildPredicateInfo() { DT.updateDFSNumbers(); // Collect operands to rename from all conditional branch terminators, as well // as assume statements. - SmallVector OpsToRename; for (auto DTN : depth_first(DT.getRootNode())) { BasicBlock *BranchBB = DTN->getBlock(); if (auto *BI = dyn_cast(BranchBB->getTerminator())) { @@ -499,18 +547,18 @@ // 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); + processBranch(BI, BranchBB); } else if (auto *SI = dyn_cast(BranchBB->getTerminator())) { - processSwitch(SI, BranchBB, OpsToRename); + processSwitch(SI, BranchBB); } } for (auto &Assume : AC.assumptions()) { if (auto *II = dyn_cast_or_null(Assume)) if (DT.isReachableFromEntry(II->getParent())) - processAssume(II, II->getParent(), OpsToRename); + processAssume(II, II->getParent()); } // Now rename all our operations. - renameUses(OpsToRename); + renameUses(); } // Create a ssa_copy declaration with custom mangling, because @@ -530,9 +578,9 @@ // 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) { +Value *PredicateInfoBuilder::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) @@ -558,10 +606,10 @@ IRBuilder<> B(getBranchTerminator(ValInfo)); Function *IF = getCopyDeclaration(F.getParent(), Op->getType()); if (IF->users().empty()) - CreatedDeclarations.insert(IF); + PI.CreatedDeclarations.insert(IF); CallInst *PIC = B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++)); - PredicateMap.insert({PIC, ValInfo}); + PI.PredicateMap.insert({PIC, ValInfo}); Result.Def = PIC; } else { auto *PAssume = dyn_cast(ValInfo); @@ -570,9 +618,9 @@ IRBuilder<> B(PAssume->AssumeInst); Function *IF = getCopyDeclaration(F.getParent(), Op->getType()); if (IF->users().empty()) - CreatedDeclarations.insert(IF); + PI.CreatedDeclarations.insert(IF); CallInst *PIC = B.CreateCall(IF, Op); - PredicateMap.insert({PIC, ValInfo}); + PI.PredicateMap.insert({PIC, ValInfo}); Result.Def = PIC; } } @@ -598,7 +646,7 @@ // // TODO: Use this algorithm to perform fast single-variable renaming in // promotememtoreg and memoryssa. -void PredicateInfo::renameUses(SmallVectorImpl &OpsToRename) { +void PredicateInfoBuilder::renameUses() { ValueDFS_Compare Compare(DT, OI); // Compute liveness, and rename in O(uses) per Op. for (auto *Op : OpsToRename) { @@ -719,7 +767,8 @@ } } -PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) { +PredicateInfoBuilder::ValueInfo & +PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) { auto OIN = ValueInfoNums.find(Operand); if (OIN == ValueInfoNums.end()) { // This will grow it @@ -732,8 +781,8 @@ return ValueInfos[OIN->second]; } -const PredicateInfo::ValueInfo & -PredicateInfo::getValueInfo(Value *Operand) const { +const PredicateInfoBuilder::ValueInfo & +PredicateInfoBuilder::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() && @@ -743,10 +792,9 @@ 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(); + : F(F) { + PredicateInfoBuilder Builder(*this, F, DT, AC); + Builder.buildPredicateInfo(); } // Remove all declarations we created . The PredicateInfo consumers are