Rename determineInsertionPoints to determinePHINodes, expose it so it can be reused

[• dberlin]

Summary

MemorySSA uses this algorithm. This moves the code around and changes the arguments so it can be reused in both places.
We don't have an SSAUtils.h or anything, but happy to put this wherever.

There are no actual algorithm or datastructure changes in here, just code movement.

[• dberlin]

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

1008

Sorry, accidentally carried this comment from the invocation, being rewritten now. :)

[• dberlin]

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

1014

Note that i have deliberately not changed the algorithm handling numbering here. Post-this-patch, i will move the block number lookups and sorting into the caller, and make this a simple SmallVector<BasicBlock *>, and remove the BBNumbers argument)

[• dberlin]

• Update comments

[qcolombet]

Hi Daniel

include/llvm/Transforms/Utils/PromoteMemToReg.h

70

From the user stand point I think we should not have to provide the DomLevels and the LiveInBlocks.

The BBNumbers are already on your “to-remove” list, so it is fine for now.

[• dberlin]

• Update to move IDF calculation

[qcolombet]

Hi Daniel,

Thanks for the refactoring!

LGTM with a couple of nitpicks.

Cheers,
-Quentin

include/llvm/Analysis/IteratedDominanceFrontier.h

45 ↗

(On Diff #24136)

Add a comment that says that Blocks must be valid for the whole lifetime of the IDFCalculator (or the next call to setDefiningBlocks).

49 ↗

(On Diff #24136)

Ditto.

58 ↗

(On Diff #24136)

Add a comment on what will IDFBlocks contain.

Edit: I see that the comment is in the cpp file. I believe it would be more convenient to have it here. Also, does doxygen pick up the comments from the .cpp?

include/llvm/Transforms/Utils/PromoteMemToReg.h

 // registers, by using the SSA construction algorithm.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H
 #define LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H
 
 #include "llvm/ADT/ArrayRef.h"
-
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 namespace llvm {
 
+class BasicBlock;
+template <class T> class DomTreeNodeBase;
+typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
 class AllocaInst;
 class DominatorTree;
 class AliasSetTracker;
 class AssumptionCache;
 
 /// \brief Return true if this alloca is legal for promotion.
 ///
 /// This is true if there are only loads, stores, and lifetime markers

 /// the same function.
 ///
 /// If AST is specified, the specified tracker is updated to reflect changes
 /// made to the IR.
 void PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
                      AliasSetTracker *AST = nullptr,
                      AssumptionCache *AC = nullptr);
 
+
+/// \brief Determine where a set of PHI nodes should be placed, given a set of
+/// defining blocks and a set of live-in blocks.
+///
+/// \p BBNumbers is expected to be a mapping from a unique number to a basic
+/// block, and is used to order the resulting PHIBlocks.
+///
+/// \p DomLevels is expected to be a mapping from Dominator tree node to depth
+/// in the dominator tree.
+void determinePHINodes(DominatorTree &DT,
+                       const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
+                       const SmallPtrSetImpl<BasicBlock *> &LiveInBlocks,
+                       const DenseMap<BasicBlock *, unsigned > &BBNumbers,
+                       const DenseMap<DomTreeNode *, unsigned> &DomLevels,
+                       SmallVectorImpl<std::pair<unsigned, BasicBlock *>> &PHIBlocks);
+
 } // End llvm namespace
 
 #endif

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/PromoteMemToReg.h"
 #include <algorithm>
 #include <queue>
 using namespace llvm;
 
 #define DEBUG_TYPE "mem2reg"
 
 STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
 STATISTIC(NumSingleStore,   "Number of alloca's promoted with a single store");
private:
 
   unsigned getNumPreds(const BasicBlock *BB) {
     unsigned &NP = BBNumPreds[BB];
     if (NP == 0)
       NP = std::distance(pred_begin(BB), pred_end(BB)) + 1;
     return NP - 1;
   }
 
-  void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
-                               AllocaInfo &Info);
   void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
                            const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
                            SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
   void RenamePass(BasicBlock *BB, BasicBlock *Pred,
                   RenamePassData::ValVector &IncVals,
                   std::vector<RenamePassData> &Worklist);
   bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
 };
if (Info.OnlyUsedInOneBlock) {
 
       // The alloca has been processed, move on.
       RemoveFromAllocasList(AllocaNum);
       continue;
     }
 
     // If we haven't computed dominator tree levels, do so now.
     if (DomLevels.empty()) {
-      SmallVector<DomTreeNode *, 32> Worklist;
-
-      DomTreeNode *Root = DT.getRootNode();
-      DomLevels[Root] = 0;
-      Worklist.push_back(Root);
-
-      while (!Worklist.empty()) {
-        DomTreeNode *Node = Worklist.pop_back_val();
-        unsigned ChildLevel = DomLevels[Node] + 1;
-        for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end();
-             CI != CE; ++CI) {
-          DomLevels[*CI] = ChildLevel;
-          Worklist.push_back(*CI);
-        }
-      }
+      for (auto DFI = df_begin(DT.getRootNode()),
+                DFE = df_end(DT.getRootNode());
+           DFI != DFE; ++DFI)
+        DomLevels[*DFI] = DFI.getPathLength() - 1;
     }
 
     // If we haven't computed a numbering for the BB's in the function, do so
     // now.
     if (BBNumbers.empty()) {
       unsigned ID = 0;
       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
         BBNumbers[I] = ID++;
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
 
     // Keep the reverse mapping of the 'Allocas' array for the rename pass.
     AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
 
     // At this point, we're committed to promoting the alloca using IDF's, and
     // the standard SSA construction algorithm.  Determine which blocks need PHI
     // nodes and see if we can optimize out some work by avoiding insertion of
     // dead phi nodes.
-    DetermineInsertionPoint(AI, AllocaNum, Info);
+
+    SmallVector<std::pair<unsigned, BasicBlock *>, 32> PHIBlocks;
+
+    // Unique the set of defining blocks for efficient lookup.
+    SmallPtrSet<BasicBlock *, 32> DefBlocks;
+    DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
+
+    // Determine which blocks the value is live in.  These are blocks which lead
+    // to uses.
+    SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
+    ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
+
+
+    llvm::determinePHINodes(DT, DefBlocks, LiveInBlocks, BBNumbers, DomLevels,
+                      PHIBlocks);
+    if (PHIBlocks.size() > 1)
+      std::sort(PHIBlocks.begin(), PHIBlocks.end());
+
+    unsigned CurrentVersion = 0;
+    for (unsigned i = 0, e = PHIBlocks.size(); i != e; ++i)
+      QueuePhiNode(PHIBlocks[i].second, AllocaNum, CurrentVersion);
   }
 
   if (Allocas.empty())
     return; // All of the allocas must have been trivial!
 
   LBI.clear();
 
   // Set the incoming values for the basic block to be null values for all of
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
         continue;
 
       // Otherwise it is, add to the worklist.
       LiveInBlockWorklist.push_back(P);
     }
   }
 }
 
-/// At this point, we're committed to promoting the alloca using IDF's, and the
-/// standard SSA construction algorithm.  Determine which blocks need phi nodes
-/// and see if we can optimize out some work by avoiding insertion of dead phi
-/// nodes.
-void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
-                                             AllocaInfo &Info) {
-  // Unique the set of defining blocks for efficient lookup.
-  SmallPtrSet<BasicBlock *, 32> DefBlocks;
-  DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
-
-  // Determine which blocks the value is live in.  These are blocks which lead
-  // to uses.
-  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
-  ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
-
-  // Use a priority queue keyed on dominator tree level so that inserted nodes
-  // are handled from the bottom of the dominator tree upwards.
-  typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
-  typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
-                              less_second> IDFPriorityQueue;
-  IDFPriorityQueue PQ;
-
-  for (BasicBlock *BB : DefBlocks) {
-    if (DomTreeNode *Node = DT.getNode(BB))
-      PQ.push(std::make_pair(Node, DomLevels[Node]));
-  }
-
-  SmallVector<std::pair<unsigned, BasicBlock *>, 32> DFBlocks;
-  SmallVector<DomTreeNode *, 32> Worklist;
-  SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
-  SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
-
-  while (!PQ.empty()) {
-    DomTreeNodePair RootPair = PQ.top();
-    PQ.pop();
-    DomTreeNode *Root = RootPair.first;
-    unsigned RootLevel = RootPair.second;
-
-    // Walk all dominator tree children of Root, inspecting their CFG edges with
-    // targets elsewhere on the dominator tree. Only targets whose level is at
-    // most Root's level are added to the iterated dominance frontier of the
-    // definition set.
-
-    Worklist.clear();
-    Worklist.push_back(Root);
-    VisitedWorklist.insert(Root);
-
-    while (!Worklist.empty()) {
-      DomTreeNode *Node = Worklist.pop_back_val();
-      BasicBlock *BB = Node->getBlock();
-
-      for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
-           ++SI) {
-        DomTreeNode *SuccNode = DT.getNode(*SI);
-
-        // Quickly skip all CFG edges that are also dominator tree edges instead
-        // of catching them below.
-        if (SuccNode->getIDom() == Node)
-          continue;
-
-        unsigned SuccLevel = DomLevels[SuccNode];
-        if (SuccLevel > RootLevel)
-          continue;
-
-        if (!VisitedPQ.insert(SuccNode).second)
-          continue;
-
-        BasicBlock *SuccBB = SuccNode->getBlock();
-        if (!LiveInBlocks.count(SuccBB))
-          continue;
-
-        DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB));
-        if (!DefBlocks.count(SuccBB))
-          PQ.push(std::make_pair(SuccNode, SuccLevel));
-      }
-
-      for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE;
-           ++CI) {
-        if (VisitedWorklist.insert(*CI).second)
-          Worklist.push_back(*CI);
-      }
-    }
-  }
-
-  if (DFBlocks.size() > 1)
-    std::sort(DFBlocks.begin(), DFBlocks.end());
-
-  unsigned CurrentVersion = 0;
-  for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i)
-    QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion);
-}
 
 /// \brief Queue a phi-node to be added to a basic-block for a specific Alloca.
 ///
 /// Returns true if there wasn't already a phi-node for that variable
 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
                                   unsigned &Version) {
   // Look up the basic-block in question.
   PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)];

 void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
                            AliasSetTracker *AST, AssumptionCache *AC) {
   // If there is nothing to do, bail out...
   if (Allocas.empty())
     return;
 
   PromoteMem2Reg(Allocas, DT, AST, AC).run();
 }
+
+/// At this point, we're committed to promoting the alloca using IDF's, and the
+/// standard SSA construction algorithm.  Determine which blocks need phi nodes
+/// and see if we can optimize out some work by avoiding insertion of dead phi
+/// nodes.
+void llvm::determinePHINodes(DominatorTree &DT,
+    const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
+    const SmallPtrSetImpl<BasicBlock *> &LiveInBlocks,
+    const DenseMap<BasicBlock *, unsigned> &BBNumbers,
+    const DenseMap<DomTreeNode *, unsigned> &DomLevels,
+    SmallVectorImpl<std::pair<unsigned, BasicBlock *>> &PHIBlocks) {
+
+  // Use a priority queue keyed on dominator tree level so that inserted nodes
+  // are handled from the bottom of the dominator tree upwards.
+  typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
+  typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
+                              less_second> IDFPriorityQueue;
+  IDFPriorityQueue PQ;
+
+  for (BasicBlock *BB : DefBlocks) {
+    if (DomTreeNode *Node = DT.getNode(BB))
+      PQ.push(std::make_pair(Node, DomLevels.lookup(Node)));
+  }
+
+  SmallVector<DomTreeNode *, 32> Worklist;
+  SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
+  SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
+
+  while (!PQ.empty()) {
+    DomTreeNodePair RootPair = PQ.top();
+    PQ.pop();
+    DomTreeNode *Root = RootPair.first;
+    unsigned RootLevel = RootPair.second;
+
+    // Walk all dominator tree children of Root, inspecting their CFG edges with
+    // targets elsewhere on the dominator tree. Only targets whose level is at
+    // most Root's level are added to the iterated dominance frontier of the
+    // definition set.
+
+    Worklist.clear();
+    Worklist.push_back(Root);
+    VisitedWorklist.insert(Root);
+
+    while (!Worklist.empty()) {
+      DomTreeNode *Node = Worklist.pop_back_val();
+      BasicBlock *BB = Node->getBlock();
+
+      for (auto Succ : successors(BB)) {
+        DomTreeNode *SuccNode = DT.getNode(Succ);
+
+        // Quickly skip all CFG edges that are also dominator tree edges instead
+        // of catching them below.
+        if (SuccNode->getIDom() == Node)
+          continue;
+
+        unsigned SuccLevel = DomLevels.lookup(SuccNode);
+        if (SuccLevel > RootLevel)
+          continue;
+
+        if (!VisitedPQ.insert(SuccNode).second)
+          continue;
+
+        BasicBlock *SuccBB = SuccNode->getBlock();
+        if (!LiveInBlocks.count(SuccBB))
+          continue;
+
+        PHIBlocks.push_back(std::make_pair(BBNumbers.lookup(SuccBB), SuccBB));
+        if (!DefBlocks.count(SuccBB))
+          PQ.push(std::make_pair(SuccNode, SuccLevel));
+      }
+
+      for (auto DomChild : *Node){
+        if (VisitedWorklist.insert(DomChild).second)
+          Worklist.push_back(DomChild);
+      }
+    }
+  }
+}