[Dominators] Teach IDF to use level information

[kuhar]

Summary

This patch teaches IteratedDominanceFrontier to use the level information stored in DomTreeNodes instead of calculating it manually.

[davide]

LGTM

llvm/trunk/include/llvm/Analysis/IteratedDominanceFrontier.h

public:
   /// the file-level comment.  It performs DF->IDF pruning using the live-in
   /// set, to avoid computing the IDF for blocks where an inserted PHI node
   /// would be dead.
   void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks);
 
 private:
   DominatorTreeBase<BasicBlock> &DT;
   bool useLiveIn;
-  DenseMap<DomTreeNode *, unsigned> DomLevels;
   const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
   const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
 };
 typedef IDFCalculator<BasicBlock *> ForwardIDFCalculator;
 typedef IDFCalculator<Inverse<BasicBlock *>> ReverseIDFCalculator;
 }
 #endif

llvm/trunk/lib/Analysis/IteratedDominanceFrontier.cpp

 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include <queue>
 
 namespace llvm {
 template <class NodeTy>
 void IDFCalculator<NodeTy>::calculate(
     SmallVectorImpl<BasicBlock *> &PHIBlocks) {
-  // If we haven't computed dominator tree levels, do so now.
-  if (DomLevels.empty()) {
-    for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
-         DFI != DFE; ++DFI) {
-      DomLevels[*DFI] = DFI.getPathLength() - 1;
-    }
-  }
-
   // 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)));
+      PQ.push({Node, Node->getLevel()});
   }
 
   SmallVector<DomTreeNode *, 32> Worklist;
   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
 
   while (!PQ.empty()) {
     DomTreeNodePair RootPair = PQ.top();
while (!Worklist.empty()) {
       for (auto *Succ : children<NodeTy>(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);
+        const unsigned SuccLevel = SuccNode->getLevel();
         if (SuccLevel > RootLevel)
           continue;
 
         if (!VisitedPQ.insert(SuccNode).second)
           continue;
 
         BasicBlock *SuccBB = SuccNode->getBlock();
         if (useLiveIn && !LiveInBlocks->count(SuccBB))