[IDF] Generalize IDFCalculator to be used with Clang's CFG

I'm currently working on a GSoC project that aims to improve the the bug reports
of the analyzer. The main heuristic I plan to use is to explain values that are
a control dependency of the bug location better.

01 bool b = messyComputation();
02 int i = 0;
03 if (b) // control dependency of the bug site, let's explain why we assume val
04        // to be true
05   10 / i; // warn: division by zero

Because of this, I'd like to generalize IDFCalculator so that I could use it for
Clang's CFG: D62883.

In detail:

* Rename IDFCalculator to IDFCalculatorBase, make it take a general CFG node
  type as a template argument rather then strictly BasicBlock (but preserve
  ForwardIDFCalculator and ReverseIDFCalculator)
* Move IDFCalculatorBase from llvm/include/llvm/Analysis to
  llvm/include/llvm/Support (but leave the BasicBlock variants in
  llvm/include/llvm/Analysis)
* clang-format the file since this patch messes up git blame anyways
* Change typedef to using
* Add the new type ChildrenGetterTy, and store an instance of it in
  IDFCalculatorBase. This is important because I'll have to specialize it for
  Clang's CFG to filter out nullpointer successors, similarly to D62507.

Differential Revision: https://reviews.llvm.org/D63389

llvm-svn: 364911

1 files changed, 0 insertions, 104 deletions

diff --git a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp
deleted file mode 100644
index 89257121c6a..00000000000
--- a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp
+++ /dev/null
@@ -1,104 +0,0 @@
-//===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// Compute iterated dominance frontiers using a linear time algorithm.
-//
-//===----------------------------------------------------------------------===//
-
-#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>>
-      DomTreeNodePair;
-  typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
-                              less_second> IDFPriorityQueue;
-  IDFPriorityQueue PQ;
-
-  DT.updateDFSNumbers();
-
-  for (BasicBlock *BB : *DefBlocks) {
-    if (DomTreeNode *Node = DT.getNode(BB))
-      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
-  }
-
-  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.first;
-
-    // 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();
-      // Succ is the successor in the direction we are calculating IDF, so it is
-      // successor for IDF, and predecessor for Reverse IDF.
-      auto DoWork = [&](BasicBlock *Succ) {
-        DomTreeNode *SuccNode = DT.getNode(Succ);
-
-        const unsigned SuccLevel = SuccNode->getLevel();
-        if (SuccLevel > RootLevel)
-          return;
-
-        if (!VisitedPQ.insert(SuccNode).second)
-          return;
-
-        BasicBlock *SuccBB = SuccNode->getBlock();
-        if (useLiveIn && !LiveInBlocks->count(SuccBB))
-          return;
-
-        PHIBlocks.emplace_back(SuccBB);
-        if (!DefBlocks->count(SuccBB))
-          PQ.push(std::make_pair(
-              SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
-      };
-
-      if (GD) {
-        for (auto Pair : children<
-                 std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, 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>;
-}