[PredicateInfo] Factor out PredicateInfoBuilder (NFC)

[nikic]

Summary

When running IPSCCP on a module with many small functions, memory usage is currently dominated by PredicateInfo, which is a huge structure (partially due to some unfortunate nested SmallVector use). However, most of it is actually only temporary analysis state, and does not need to be retained after initial construction.

This patch factors the temporary state out into a separate structure that is only live during the analysis.

[fhahn]

include/llvm/Transforms/Utils/PredicateInfo.h

191–192

Could all those helpers be moved into State?

That way, we would not need to thread the parameter through the code and we would even more cleanly separate the build phase. If it is possible to move the construction parts into State, it might make sense to rename it to something like PredicateInfoBuilder and PredicateInfo itself would only contain PredicateMap, CreatedDeclarations, AllInfos. The builder could hold references to those.

[nikic]

include/llvm/Transforms/Utils/PredicateInfo.h

191–192

That should be possible, if we pass a PredicateInfo reference into State (and make it a friend class), so that we have access to AllInfos etc. I'll give it a try.

[nikic]

Move most state & logic into PredicateInfoBuilder

[fhahn]

LGTM, thanks! As noted I think it would be slightly better to keep passing the OpsToRename explicitly, but I don't feel too strongly about that

lib/Transforms/Utils/PredicateInfo.cpp

493

I think it would be slightly better to keep passing OpsToRename to various places, as it makes things a bit more explicit; that's the main list op operations to rename.

[nikic]

lib/Transforms/Utils/PredicateInfo.cpp

493

Hm, why do you think that OpsToRename should be handled differently than other state like ValueInfo?

In fact, now that I look a bit more closely at this, I think there's some duplication going on here, in that the values stored in OpsToRename should be the same as the keys of ValueInfoNums. I guess this is stored separate to preserve order?

[fhahn]

lib/Transforms/Utils/PredicateInfo.cpp

493

Hm, why do you think that OpsToRename should be handled differently than other state like ValueInfo?

I think passing it to renameUses makes it clearer at the call site & function signature *what* uses are renamed, although it's true that it currently queries some other information as well. I have a few patches somewhere, which expose renameUses for general SSA renaming and there it would be convenient to just pass in the list of uses to rename.

In fact, now that I look a bit more closely at this, I think there's some duplication going on here, in that the values stored in OpsToRename should be the same as the keys of ValueInfoNums. I guess this is stored separate to preserve order?

ValueInfoNums maps values to their ValueInfo entry and I think it is used to ensure that there's a single ValueInfo per value. I guess alternatively we could just use a map Value* -> ValueInfo, but then we would have to iterate over the keys of the map. That would safe sizeof(unsigned) per value to rename, but iterating over the keys in the map should be more expensive in terms of runtime.

[nikic]

Keep OpsToRename as explicit argument.

[nikic]

lib/Transforms/Utils/PredicateInfo.cpp

493

I think passing it to renameUses makes it clearer at the call site & function signature *what* uses are renamed, although it's true that it currently queries some other information as well. I have a few patches somewhere, which expose renameUses for general SSA renaming and there it would be convenient to just pass in the list of uses to rename.

Fair enough, I've changed the code back to pass OpsToRename explicitly.

ValueInfoNums maps values to their ValueInfo entry and I think it is used to ensure that there's a single ValueInfo per value. I guess alternatively we could just use a map Value* -> ValueInfo, but then we would have to iterate over the keys of the map. That would safe sizeof(unsigned) per value to rename, but iterating over the keys in the map should be more expensive in terms of runtime.

I think the split into ValueInfoNums and ValueInfos here is because ValueInfo is large, so storing it in a DenseMap is inefficient. Using a DenseMap of integers that index into a separate vector avoids that.

include/llvm/Transforms/Utils/PredicateInfo.h

 ///
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
 #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 <algorithm>
-#include <cassert>
-#include <cstddef>
-#include <iterator>
-#include <memory>
-#include <utility>
 
 namespace llvm {
 
+class AssumptionCache;
 class DominatorTree;
 class Function;
+class IntrinsicInst;
 class raw_ostream;
 
 enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
 
 // Base class for all predicate information we provide.
 // All of our predicate information has at least a comparison.
 class PredicateBase : public ilist_node<PredicateBase> {
 public:
PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
                           SI->getCondition()),
         CaseValue(CaseValue), Switch(SI) {}
   PredicateSwitch() = delete;
   static bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Switch;
   }
 };
 
-// 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<PredicateBase *, 4> Infos;
-  };
-  // This owns the all the predicate infos in the function, placed or not.
-  iplist<PredicateBase> AllInfos;
-
 public:
   PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
   ~PredicateInfo();
 
   void verifyPredicateInfo() const;
 
   void dump() const;
   void print(raw_ostream &) const;
 
   const PredicateBase *getPredicateInfoFor(const Value *V) const {
     return PredicateMap.lookup(V);
   }
 
 protected:
   // 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<Value *> &);
-  void processBranch(BranchInst *, BasicBlock *, SmallVectorImpl<Value *> &);
-  void processSwitch(SwitchInst *, BasicBlock *, SmallVectorImpl<Value *> &);
-  void renameUses(SmallVectorImpl<Value *> &);
-  using ValueDFS = PredicateInfoClasses::ValueDFS;
-  typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
-  void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
-  Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
-  bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
-  void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
-  ValueInfo &getOrCreateValueInfo(Value *);
-  void addInfoFor(SmallVectorImpl<Value *> &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<PredicateBase> 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<const Value *, const PredicateBase *> 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<ValueInfo, 32> 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<Value *, unsigned int> ValueInfoNums;
-  // The set of edges along which we can only handle phi uses, due to critical
-  // edges.
-  DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
   // The set of ssa_copy declarations we created with our custom mangling.
   SmallSet<AssertingVH<Function>, 20> CreatedDeclarations;
 };
 
 // This pass does eager building and then printing of PredicateInfo. It is used
 // by
 // the tests to be able to build, dump, and verify PredicateInfo.
 class PredicateInfoPrinterLegacyPass : public FunctionPass {

lib/Transforms/Utils/PredicateInfo.cpp

 #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/Analysis/OrderedInstructions.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(

 // 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
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
+class PredicateInfoBuilder {
+  // Used to store information about each value we might rename.
+  struct ValueInfo {
+    SmallVector<PredicateBase *, 4> Infos;
+  };
+
+  PredicateInfo &PI;
+  Function &F;
+  DominatorTree &DT;
+  AssumptionCache &AC;
+  OrderedInstructions OI;
+
+  SmallVector<Value *, 8> 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<ValueInfo, 32> 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<Value *, unsigned int> ValueInfoNums;
+
+  // The set of edges along which we can only handle phi uses, due to critical
+  // edges.
+  DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
+
+  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<ValueDFS> ValueDFSStack;
+  void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
+  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,
+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
   // 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 (Stack.back().EdgeOnly) {
     // 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,
+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<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);
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
   //
   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) {
+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<Value *> &OpsToRename) {
+void PredicateInfoBuilder::processAssume(IntrinsicInst *II,
+                                         BasicBlock *AssumeBB) {
   // 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);
+        addInfoFor(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);
+      addInfoFor(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) {
+void PredicateInfoBuilder::processBranch(BranchInst *BI, BasicBlock *BranchBB) {
   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);
+      addInfoFor(Op, PB);
       if (!Succ->getSinglePredecessor())
         EdgeUsesOnly.insert({BranchBB, Succ});
     }
   };
 
   // Match combinations of conditions.
   CmpInst::Predicate Pred;
   bool isAnd = false;
for (auto Cond : ConditionsToProcess) {
     } 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) {
+void PredicateInfoBuilder::processSwitch(SwitchInst *SI, BasicBlock *BranchBB) {
   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);
+      addInfoFor(Op, PS);
       if (!TargetBlock->getSinglePredecessor())
         EdgeUsesOnly.insert({BranchBB, TargetBlock});
     }
   }
 }
 
 // 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<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);
+      processBranch(BI, BranchBB);
     } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
-      processSwitch(SI, BranchBB, OpsToRename);
+      processSwitch(SI, BranchBB);
     }
   }
   for (auto &Assume : AC.assumptions()) {
     if (auto *II = dyn_cast_or_null<IntrinsicInst>(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
 // 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,
+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)
     if (RevIter->Def)
       break;
 
   size_t Start = RevIter - RenameStack.rbegin();
   // The maximum number of things we should be trying to materialize at once
for (auto RenameIter = RenameStack.end() - Start;
     // 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);
+        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<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);
+        PI.CreatedDeclarations.insert(IF);
       CallInst *PIC = B.CreateCall(IF, Op);
-      PredicateMap.insert({PIC, ValInfo});
+      PI.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 +

 // 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) {
+void PredicateInfoBuilder::renameUses() {
   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.
for (auto &VD : OrderedUses) {
                         << "\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) {
+PredicateInfoBuilder::ValueInfo &
+PredicateInfoBuilder::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 {
+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() &&
          "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();
+    : F(F) {
+  PredicateInfoBuilder Builder(*this, F, DT, AC);
+  Builder.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;