[IDF] Teach Iterated Dominance Frontier to use a snapshot CFG based on a GraphDiff.

[asbirlea]

Summary

Create the ability to compute IDF using a CFG View.
For this, we'll need a new DT created using a list of Updates (to be refactored later to a GraphDiff), and the GraphTraits based on the same GraphDiff.

[kuhar]

lib/Analysis/IteratedDominanceFrontier.cpp

93

Is it possible to instead create a helper function in GraffDiff that returns a node of appropriate type (like the pair here)?
Something like children(GraphDiff::make_node(GD, BB))

101

I'd prefer braces around the for

[george.burgess.iv]

Never touched this code, so all I can offer is a style nit. Thanks for the patch!

lib/Analysis/IteratedDominanceFrontier.cpp

65

nit: Unless this is consistent with the rest of the file, please spell this DoWork (there was a llvm-dev thread about this recently. My interpretation is that upper-camel is winning, but I'm also slightly biased.)

[asbirlea]

lib/Analysis/IteratedDominanceFrontier.cpp

93

I don't think that's how GraphTraits is intended to work, but your comment helped me understand that the InverseGraph bool is actually a property of the GraphDiff (just like doms), so it should be a template argument, not an argument to all methods.

I'll send a follow-up patch to the one adding GraphDiff to make that change and rebase this patch.
With that change, I can drop the if and this becomes:
children<std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>({GD, BB})
which I think is pretty clean.

[asbirlea]

Address style comments.
Rebase on top of patch making GraphDiff templated on IsPostDom/InverseGraph.

[asbirlea]

Format.

[kuhar]

Seems fine

include/llvm/Analysis/IteratedDominanceFrontier.h

 
 #ifndef LLVM_ANALYSIS_IDF_H
 #define LLVM_ANALYSIS_IDF_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
 
 /// Determine the iterated dominance frontier, given a set of defining
 /// blocks, and optionally, a set of live-in blocks.
 ///
 /// In turn, the results can be used to place phi nodes.
 ///
 /// This algorithm is a linear time computation of Iterated Dominance Frontiers,
 /// pruned using the live-in set.
 /// By default, liveness is not used to prune the IDF computation.
 /// The template parameters should be either BasicBlock* or Inverse<BasicBlock
 /// *>, depending on if you want the forward or reverse IDF.
 template <class NodeTy, bool IsPostDom>
 class IDFCalculator {
  public:
    IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
-      : DT(DT), useLiveIn(false) {}
+       : DT(DT), GD(nullptr), useLiveIn(false) {}
+
+   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
+                 GraphDiff<BasicBlock *> *GD)
+       : DT(DT), GD(GD), useLiveIn(false) {}
 
    /// Give the IDF calculator the set of blocks in which the value is
    /// defined.  This is equivalent to the set of starting blocks it should be
    /// calculating the IDF for (though later gets pruned based on liveness).
    ///
    /// Note: This set *must* live for the entire lifetime of the IDF calculator.
    void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
      DefBlocks = &Blocks;
    }
 
   /// Give the IDF calculator the set of blocks in which the value is
   /// live on entry to the block.   This is used to prune the IDF calculation to
   /// not include blocks where any phi insertion would be dead.
   ///
   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
 
   void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
public:
   /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
   /// 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, IsPostDom> &DT;
+ GraphDiff<BasicBlock *> *GD;
  bool useLiveIn;
  const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
  const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
 };
 typedef IDFCalculator<BasicBlock *, false> ForwardIDFCalculator;
 typedef IDFCalculator<Inverse<BasicBlock *>, true> ReverseIDFCalculator;
 }
 #endif

lib/Analysis/IteratedDominanceFrontier.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include <queue>
 
 namespace llvm {
+
 template <class NodeTy, bool IsPostDom>
 void IDFCalculator<NodeTy, IsPostDom>::calculate(
     SmallVectorImpl<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. We also augment
   // the level with a DFS number to ensure that the blocks are ordered in a
   // deterministic way.
   typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>>
while (!PQ.empty()) {
     Worklist.push_back(Root);
     VisitedWorklist.insert(Root);
 
     while (!Worklist.empty()) {
       DomTreeNode *Node = Worklist.pop_back_val();
       BasicBlock *BB = Node->getBlock();
       // Succ is the successor in the direction we are calculating IDF, so it is
       // successor for IDF, and predecessor for Reverse IDF.
-      for (auto *Succ : children<NodeTy>(BB)) {
+      auto doWork = [&](BasicBlock *Succ) {
         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;
+          return;
 
         const unsigned SuccLevel = SuccNode->getLevel();
         if (SuccLevel > RootLevel)
-          continue;
+          return;
 
         if (!VisitedPQ.insert(SuccNode).second)
-          continue;
+          return;
 
         BasicBlock *SuccBB = SuccNode->getBlock();
         if (useLiveIn && !LiveInBlocks->count(SuccBB))
-          continue;
+          return;
 
         PHIBlocks.emplace_back(SuccBB);
         if (!DefBlocks->count(SuccBB))
           PQ.push(std::make_pair(
               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
-      }
+      };
+
+      if (GD) {
+        if (!IsPostDom)
+          for (auto Pair :
+               children<std::pair<const GraphDiff<BasicBlock *> *, NodeTy>>(
+                   {GD, BB}))
+            doWork(Pair.second);
+        else
+          for (auto Pair : children<
+                   std::pair<const GraphDiff<Inverse<BasicBlock *>> *, NodeTy>>(
+                   {GD, BB}))
+            doWork(Pair.second);
+      } else
+        for (auto *Succ : children<NodeTy>(BB))
+          doWork(Succ);
 
       for (auto DomChild : *Node) {
         if (VisitedWorklist.insert(DomChild).second)
           Worklist.push_back(DomChild);
       }
     }
   }
 }
 
 template class IDFCalculator<BasicBlock *, false>;
 template class IDFCalculator<Inverse<BasicBlock *>, true>;
 }