Index: include/llvm/Transforms/Utils/PredicateInfo.h =================================================================== --- include/llvm/Transforms/Utils/PredicateInfo.h +++ include/llvm/Transforms/Utils/PredicateInfo.h @@ -195,11 +195,34 @@ /// accesses. class PredicateInfo { private: - // Used to store information about each value we might rename. - struct ValueInfo { - // Information about each possible copy. - SmallVector Infos; + /// State used only temporarily during PredicateInfo construction. + struct State { + // Used to store information about each value we might rename. + struct ValueInfo { + SmallVector Infos; + }; + + 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; + + State(); + ValueInfo &getOrCreateValueInfo(Value *); + const ValueInfo &getValueInfo(Value *) const; }; + // This owns the all the predicate infos in the function, placed or not. iplist AllInfos; @@ -223,20 +246,17 @@ private: void buildPredicateInfo(); - void processAssume(IntrinsicInst *, BasicBlock *, SmallVectorImpl &); - void processBranch(BranchInst *, BasicBlock *, SmallVectorImpl &); - void processSwitch(SwitchInst *, BasicBlock *, SmallVectorImpl &); - void renameUses(SmallVectorImpl &); + void processAssume(IntrinsicInst *, BasicBlock *, State &); + void processBranch(BranchInst *, BasicBlock *, State &); + void processSwitch(SwitchInst *, BasicBlock *, State &); + void renameUses(State &); 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; + void addInfoFor(State &State, Value *Op, PredicateBase *PB); Function &F; DominatorTree &DT; AssumptionCache &AC; @@ -245,17 +265,6 @@ // 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 @@ -338,11 +338,10 @@ } // 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) { - auto &OperandInfo = getOrCreateValueInfo(Op); +void PredicateInfo::addInfoFor(State &State, Value *Op, PredicateBase *PB) { + auto &OperandInfo = State.getOrCreateValueInfo(Op); if (OperandInfo.Infos.empty()) - OpsToRename.push_back(Op); + State.OpsToRename.push_back(Op); AllInfos.push_back(PB); OperandInfo.Infos.push_back(PB); } @@ -350,7 +349,7 @@ // Process an assume instruction and place relevant operations we want to rename // into OpsToRename. void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB, - SmallVectorImpl &OpsToRename) { + State &State) { // See if we have a comparison we support SmallVector CmpOperands; SmallVector ConditionsToProcess; @@ -372,7 +371,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(State, Op, PA); } CmpOperands.clear(); } else if (auto *BinOp = dyn_cast(Cond)) { @@ -380,7 +379,7 @@ assert(BinOp->getOpcode() == Instruction::And && "Should have been an AND"); auto *PA = new PredicateAssume(BinOp, II, BinOp); - addInfoFor(OpsToRename, BinOp, PA); + addInfoFor(State, BinOp, PA); } else { llvm_unreachable("Unknown type of condition"); } @@ -390,7 +389,7 @@ // Process a block terminating branch, and place relevant operations to be // renamed into OpsToRename. void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB, - SmallVectorImpl &OpsToRename) { + State &State) { BasicBlock *FirstBB = BI->getSuccessor(0); BasicBlock *SecondBB = BI->getSuccessor(1); SmallVector SuccsToProcess; @@ -411,9 +410,9 @@ continue; PredicateBase *PB = new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge); - addInfoFor(OpsToRename, Op, PB); + addInfoFor(State, Op, PB); if (!Succ->getSinglePredecessor()) - EdgeUsesOnly.insert({BranchBB, Succ}); + State.EdgeUsesOnly.insert({BranchBB, Succ}); } }; @@ -460,7 +459,7 @@ // Process a block terminating switch, and place relevant operations to be // renamed into OpsToRename. void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB, - SmallVectorImpl &OpsToRename) { + State &State) { Value *Op = SI->getCondition(); if ((!isa(Op) && !isa(Op)) || Op->hasOneUse()) return; @@ -478,9 +477,9 @@ if (SwitchEdges.lookup(TargetBlock) == 1) { PredicateSwitch *PS = new PredicateSwitch( Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI); - addInfoFor(OpsToRename, Op, PS); + addInfoFor(State, Op, PS); if (!TargetBlock->getSinglePredecessor()) - EdgeUsesOnly.insert({BranchBB, TargetBlock}); + State.EdgeUsesOnly.insert({BranchBB, TargetBlock}); } } } @@ -490,7 +489,7 @@ DT.updateDFSNumbers(); // Collect operands to rename from all conditional branch terminators, as well // as assume statements. - SmallVector OpsToRename; + State State; for (auto DTN : depth_first(DT.getRootNode())) { BasicBlock *BranchBB = DTN->getBlock(); if (auto *BI = dyn_cast(BranchBB->getTerminator())) { @@ -499,18 +498,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, State); } else if (auto *SI = dyn_cast(BranchBB->getTerminator())) { - processSwitch(SI, BranchBB, OpsToRename); + processSwitch(SI, BranchBB, State); } } 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(), State); } // Now rename all our operations. - renameUses(OpsToRename); + renameUses(State); } // Create a ssa_copy declaration with custom mangling, because @@ -598,14 +597,14 @@ // // TODO: Use this algorithm to perform fast single-variable renaming in // promotememtoreg and memoryssa. -void PredicateInfo::renameUses(SmallVectorImpl &OpsToRename) { +void PredicateInfo::renameUses(State &State) { ValueDFS_Compare Compare(DT, OI); // Compute liveness, and rename in O(uses) per Op. - for (auto *Op : OpsToRename) { + for (auto *Op : State.OpsToRename) { LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n"); unsigned Counter = 0; SmallVector OrderedUses; - const auto &ValueInfo = getValueInfo(Op); + const auto &ValueInfo = State.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. @@ -630,7 +629,7 @@ // block, and handle it specially. We know that it goes last, and only // dominate phi uses. auto BlockEdge = getBlockEdge(PossibleCopy); - if (EdgeUsesOnly.count(BlockEdge)) { + if (State.EdgeUsesOnly.count(BlockEdge)) { VD.LocalNum = LN_Last; auto *DomNode = DT.getNode(BlockEdge.first); if (DomNode) { @@ -719,7 +718,13 @@ } } -PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) { +PredicateInfo::State::State() { + // Push an empty operand info so that we can detect 0 as not finding one + ValueInfos.resize(1); +} + +PredicateInfo::State::ValueInfo & +PredicateInfo::State::getOrCreateValueInfo(Value *Operand) { auto OIN = ValueInfoNums.find(Operand); if (OIN == ValueInfoNums.end()) { // This will grow it @@ -732,8 +737,8 @@ return ValueInfos[OIN->second]; } -const PredicateInfo::ValueInfo & -PredicateInfo::getValueInfo(Value *Operand) const { +const PredicateInfo::State::ValueInfo & +PredicateInfo::State::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() && @@ -744,8 +749,6 @@ 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(); }