diff --git a/llvm/include/llvm/Transforms/Utils/PredicateInfo.h b/llvm/include/llvm/Transforms/Utils/PredicateInfo.h --- a/llvm/include/llvm/Transforms/Utils/PredicateInfo.h +++ b/llvm/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; }; diff --git a/llvm/lib/Transforms/Utils/PredicateInfo.cpp b/llvm/lib/Transforms/Utils/PredicateInfo.cpp --- a/llvm/lib/Transforms/Utils/PredicateInfo.cpp +++ b/llvm/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) @@ -83,7 +83,6 @@ } namespace llvm { -namespace PredicateInfoClasses { enum LocalNum { // Operations that must appear first in the block. LN_First, @@ -251,10 +250,64 @@ } }; -} // 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; + + // 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; + + ValueInfo &getOrCreateValueInfo(Value *); + const ValueInfo &getValueInfo(Value *) const; + + void processAssume(IntrinsicInst *, BasicBlock *, + SmallVectorImpl &OpsToRename); + void processBranch(BranchInst *, BasicBlock *, + SmallVectorImpl &OpsToRename); + void processSwitch(SwitchInst *, BasicBlock *, + SmallVectorImpl &OpsToRename); + void renameUses(SmallVectorImpl &OpsToRename); + void addInfoFor(SmallVectorImpl &OpsToRename, 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 PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, - const ValueDFS &VDUse) const { +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 +334,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 +391,20 @@ } // 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(SmallVectorImpl &OpsToRename, + 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, + SmallVectorImpl &OpsToRename) { // See if we have a comparison we support SmallVector CmpOperands; SmallVector ConditionsToProcess; @@ -389,8 +443,9 @@ // 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, + SmallVectorImpl &OpsToRename) { BasicBlock *FirstBB = BI->getSuccessor(0); BasicBlock *SecondBB = BI->getSuccessor(1); SmallVector SuccsToProcess; @@ -459,8 +514,9 @@ } // 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, + SmallVectorImpl &OpsToRename) { Value *Op = SI->getCondition(); if ((!isa(Op) && !isa(Op)) || Op->hasOneUse()) return; @@ -486,7 +542,7 @@ } // 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. @@ -530,9 +586,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 +614,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 +626,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 +654,7 @@ // // TODO: Use this algorithm to perform fast single-variable renaming in // promotememtoreg and memoryssa. -void PredicateInfo::renameUses(SmallVectorImpl &OpsToRename) { +void PredicateInfoBuilder::renameUses(SmallVectorImpl &OpsToRename) { ValueDFS_Compare Compare(DT, OI); // Compute liveness, and rename in O(uses) per Op. for (auto *Op : OpsToRename) { @@ -719,7 +775,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 +789,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 +800,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