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

[Szelethus]

Summary

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 to be true
04   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
• Practically revert D50675. This was done because GraphDiff is only specialized for BasicBlock, and wouldn't be used for clang::CFGBlcok. Interestingly, it wasn't even used at all: In D45299, it was used at a certain point (https://reviews.llvm.org/D45299?id=160698) but was ultimately removed. Is this okay?
• 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.

[kuhar]

Looks great, I'm only not sure about the GraphDiff removal.

Practically revert D50675. This was done because GraphDiff is only specialized for BasicBlock, and wouldn't be used for clang::CFGBlcok. Interestingly, it wasn't even used at all: In D45299, it was used at a certain point (https://reviews.llvm.org/D45299?id=160698) but was ultimately removed. Is this okay?

@asbirlea?

[Szelethus]

Thanks!

In D63389#1546185, @kuhar wrote:

Looks great, I'm only not sure about the GraphDiff removal.

Practically revert D50675. This was done because GraphDiff is only specialized for BasicBlock, and wouldn't be used for clang::CFGBlcok. Interestingly, it wasn't even used at all: In D45299, it was used at a certain point (https://reviews.llvm.org/D45299?id=160698) but was ultimately removed. Is this okay?

@asbirlea?

If having a virtual function isn't too painful, it'd be easy to reimplement it.

[kuhar]

In D63389#1546196, @Szelethus wrote:

Thanks!

In D63389#1546185, @kuhar wrote:

Looks great, I'm only not sure about the GraphDiff removal.

Practically revert D50675. This was done because GraphDiff is only specialized for BasicBlock, and wouldn't be used for clang::CFGBlcok. Interestingly, it wasn't even used at all: In D45299, it was used at a certain point (https://reviews.llvm.org/D45299?id=160698) but was ultimately removed. Is this okay?

@asbirlea?

If having a virtual function isn't too painful, it'd be easy to reimplement it.

Given that the original change was just a few lines of code, we can reimplement it directly later, when it's actually needed.

[asbirlea]

We do very much need GraphDiff in the IDFCalculator when doing updates in MemorySSA. I don't know how I missed this, since it was the very reason it was added, but thanks a lot for catching it.
I'll send a patch with the fix shortly.

[Szelethus]

In D63389#1546470, @asbirlea wrote:

We do very much need GraphDiff in the IDFCalculator when doing updates in MemorySSA. I don't know how I missed this, since it was the very reason it was added, but thanks a lot for catching it.
I'll send a patch with the fix shortly.

Glad its back! How does yet another class (IDFGraphDiffCalculator) sound like? With that, I could use template specializations instead of virtual functions.

[Szelethus]

Reimplement D50675.

In D63389#1546512, @Szelethus wrote:

In D63389#1546470, @asbirlea wrote:

We do very much need GraphDiff in the IDFCalculator when doing updates in MemorySSA. I don't know how I missed this, since it was the very reason it was added, but thanks a lot for catching it.
I'll send a patch with the fix shortly.

Glad its back! How does yet another class (IDFGraphDiffCalculator) sound like? With that, I could use template specializations instead of virtual functions.

That wasn't going to happen, since the GraphDiff object has to be used in the getChildren function. I made llvm::IDFCalculator::getChildren virtual, is this okay?

I also have a local branch on which I used std::function (had to be used in order to pass a lambda with a non-empty capture list) and kept everything non-virtual, but I read somewhere that std::function is heavy-weight. Which solution is better, if any?

(diffed to this revision)

diff --git a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h
index d3563f409fa..2ef6c9460bb 100644
--- a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h
+++ b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h
@@ -27,7 +27,19 @@ public:
 
   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
                 const GraphDiff<BasicBlock *, IsPostDom> *GD)
-      : IDFCalculatorBase(DT), GD(GD) {
+      : IDFCalculatorBase(
+            DT,
+            [GD](const NodeRef &BB) {
+              using SnapShotBBPair =
+                  std::pair<const GraphDiff<BasicBlock *, IsPostDom> *,
+                            OrderedNodeTy>;
+
+              ChildrenTy Ret;
+              for (auto Pair : children<SnapShotBBPair>({GD, BB}))
+                Ret.emplace_back(Pair.second);
+              return Ret;
+            }),
+        GD(GD) {
     assert(GD);
   }
 
@@ -35,21 +47,6 @@ public:
   using ChildrenTy = typename IDFCalculatorBase::ChildrenTy;
   using OrderedNodeTy = typename IDFCalculatorBase::OrderedNodeTy;
 
-  virtual ChildrenTy getChildren(const NodeRef &BB) override {
-    if (!GD) {
-      auto Children = children<OrderedNodeTy>(BB);
-      return {Children.begin(), Children.end()};
-    }
-
-    using SnapShotBBPair =
-        std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, OrderedNodeTy>;
-
-    ChildrenTy Ret;
-    for (auto Pair : children<SnapShotBBPair>({GD, BB}))
-      Ret.emplace_back(Pair.second);
-    return Ret;
-  }
-
 private:
   const GraphDiff<BasicBlock *, IsPostDom> *GD = nullptr;
 };
diff --git a/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h b/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h
index 15326a24955..e9dddb8c6d1 100644
--- a/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h
+++ b/llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h
@@ -28,6 +28,7 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/CFGDiff.h"
 #include "llvm/Support/GenericDomTree.h"
+#include <functional>
 #include <queue>
 
 namespace llvm {
@@ -46,9 +47,17 @@ public:
   using OrderedNodeTy =
       typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type;
 
-  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
+  using NodeRef = typename GraphTraits<OrderedNodeTy>::NodeRef;
+  using ChildrenTy = SmallVector<NodeRef, 8>;
+  using ChildrenGetterFn = ChildrenTy(const NodeRef &);
 
-  virtual ~IDFCalculatorBase() = default;
+  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT,
+                    std::function<ChildrenGetterFn> Fn =
+                        [](const NodeRef &N) -> ChildrenTy {
+                      auto Children = children<OrderedNodeTy>(N);
+                      return {Children.begin(), Children.end()};
+                    })
+      : DT(DT), GetChildren(Fn) {}
 
   /// 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
@@ -85,19 +94,12 @@ public:
   /// would be dead.
   void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks);
 
-  using NodeRef = typename GraphTraits<OrderedNodeTy>::NodeRef;
-  using ChildrenTy = SmallVector<NodeRef, 8>;
-
-  virtual ChildrenTy getChildren(const NodeRef &N) {
-    auto Children = children<OrderedNodeTy>(N);
-    return {Children.begin(), Children.end()};
-  }
-
 private:
   DominatorTreeBase<NodeTy, IsPostDom> &DT;
   bool useLiveIn = false;
   const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
   const SmallPtrSetImpl<NodeTy *> *DefBlocks;
+  std::function<ChildrenGetterFn> GetChildren;
 };
 
 //===----------------------------------------------------------------------===//
@@ -170,7 +172,7 @@ void IDFCalculatorBase<NodeTy, IsPostDom>::calculate(
               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
       };
 
-      for (auto Succ : getChildren(BB))
+      for (auto Succ : GetChildren(BB))
         DoWork(Succ);
 
       for (auto DomChild : *Node) {

[kuhar]

@Szelethus

That wasn't going to happen, since the GraphDiff object has to be used in the getChildren function. I made llvm::IDFCalculator::getChildren virtual, is this okay?

I also have a local branch on which I used std::function (had to be used in order to pass a lambda with a non-empty capture list) and kept everything non-virtual, but I read somewhere that std::function is heavy-weight. Which solution is better, if any?

I'd expect the getChildren to be potentially performance-sensitive and am worried about switching it into a virtual call or another indirection through std::function. Do you have some evidence that this does not affect performance?

Why not have the generic base that used typical way of getting children with children (for clang) and a specialization for BasicBlock using GraphDiff?

[Szelethus]

Added a new type called ChildrenGetterTy, and added an instance of it as a field to IDFCalculatorBase (since we need to store a pointer to GraphDiff in it when specializing for BasicBlock).

Using template instantiations instead of runtime indirection.

Why not have the generic base that used typical way of getting children with children (for clang) and a specialization for BasicBlock using GraphDiff?

That is what I was going for, it just took far too long to realize I didn't need to have that method be static :^)

[Szelethus]

A polite ping :^)

[kuhar]

Looks good now. I added a few nits inline.

llvm/include/llvm/Analysis/IteratedDominanceFrontier.h

85

Since there's no move, I'd rather make it const &.

86

Is it possible to rename Pair such that it's clear what (type) .second is?

llvm/include/llvm/Analysis/IteratedDominanceFrontier.h

 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
-/// \file
-/// Compute iterated dominance frontiers using a linear time algorithm.
-///
-/// The algorithm used here is based on:
-///
-///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
-///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
-///   Programming Languages
-///   POPL '95. ACM, New York, NY, 62-73.
-///
-/// It has been modified to not explicitly use the DJ graph data structure and
-/// to directly compute pruned SSA using per-variable liveness information.
-//
-//===----------------------------------------------------------------------===//
 
 #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"
+#include "llvm/Support/GenericIteratedDominanceFrontier.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), GD(nullptr), useLiveIn(false) {}
+class BasicBlock;
+
+template <bool IsPostDom>
+class IDFCalculator final : public IDFCalculatorBase<BasicBlock, IsPostDom> {
+  using IDFCalculatorBase =
+      typename llvm::IDFCalculatorBase<BasicBlock, IsPostDom>;
+
+      : IDFCalculatorBase(DT) {}
 
-   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
-                 const GraphDiff<BasicBlock *, IsPostDom> *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;
-   }
+      : IDFCalculatorBase(DT), GD(GD) {
+    assert(GD);
 
-  /// 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) {
-    LiveInBlocks = &Blocks;
-    useLiveIn = true;
+  using NodeRef = BasicBlock *;
+  using ChildrenTy = typename IDFCalculatorBase::ChildrenTy;
+  using OrderedNodeTy = typename IDFCalculatorBase::OrderedNodeTy;
+
+  virtual ChildrenTy getChildren(const NodeRef &BB) override {
+    if (!GD) {
+      auto Children = children<OrderedNodeTy>(BB);
+      return {Children.begin(), Children.end()};
     }
 
-  /// Reset the live-in block set to be empty, and tell the IDF
-  /// calculator to not use liveness anymore.
-  void resetLiveInBlocks() {
-    LiveInBlocks = nullptr;
-    useLiveIn = false;
-  }
+    using SnapShotBBPair =
+        std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, OrderedNodeTy>;
 
-  /// Calculate iterated dominance frontiers
-  ///
-  /// 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);
+    ChildrenTy Ret;
+    for (auto Pair : children<SnapShotBBPair>({GD, BB}))
+      Ret.emplace_back(Pair.second);
+    return Ret;
+  }
 
 private:
- DominatorTreeBase<BasicBlock, IsPostDom> &DT;
- const GraphDiff<BasicBlock *, IsPostDom> *GD;
- bool useLiveIn;
- const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
- const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
+  const GraphDiff<BasicBlock *, IsPostDom> *GD = nullptr;
 };
-typedef IDFCalculator<BasicBlock *, false> ForwardIDFCalculator;
-typedef IDFCalculator<Inverse<BasicBlock *>, true> ReverseIDFCalculator;
-}
+
+using ForwardIDFCalculator = IDFCalculator<false>;
+using ReverseIDFCalculator = IDFCalculator<true>;
+
+} // end of namespace llvm
+
 #endif

llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h

+//===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// Compute iterated dominance frontiers using a linear time algorithm.
+///
+/// The algorithm used here is based on:
+///
+///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
+///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
+///   Programming Languages
+///   POPL '95. ACM, New York, NY, 62-73.
+///
+/// It has been modified to not explicitly use the DJ graph data structure and
+/// to directly compute pruned SSA using per-variable liveness information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_GENERIC_IDF_H
+#define LLVM_SUPPORT_GENERIC_IDF_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFGDiff.h"
+#include "llvm/Support/GenericDomTree.h"
+#include <queue>
+
+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 of a CFG block type.
+template <class NodeTy, bool IsPostDom> class IDFCalculatorBase {
+public:
+  using OrderedNodeTy =
+      typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type;
+
+  IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
+
+  virtual ~IDFCalculatorBase() = default;
+
+  /// 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<NodeTy *> &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<NodeTy *> &Blocks) {
+    LiveInBlocks = &Blocks;
+    useLiveIn = true;
+  }
+
+  /// Reset the live-in block set to be empty, and tell the IDF
+  /// calculator to not use liveness anymore.
+  void resetLiveInBlocks() {
+    LiveInBlocks = nullptr;
+    useLiveIn = false;
+  }
+
+  /// Calculate iterated dominance frontiers
+  ///
+  /// 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<NodeTy *> &IDFBlocks);
+
+  using NodeRef = typename GraphTraits<OrderedNodeTy>::NodeRef;
+  using ChildrenTy = SmallVector<NodeRef, 8>;
+
+  virtual ChildrenTy getChildren(const NodeRef &N) {
+    auto Children = children<OrderedNodeTy>(N);
+    return {Children.begin(), Children.end()};
+  }
+
+private:
+  DominatorTreeBase<NodeTy, IsPostDom> &DT;
+  bool useLiveIn = false;
+  const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
+  const SmallPtrSetImpl<NodeTy *> *DefBlocks;
+};
+
+//===----------------------------------------------------------------------===//
+// Implementation.
+//===----------------------------------------------------------------------===//
+
+template <class NodeTy, bool IsPostDom>
+void IDFCalculatorBase<NodeTy, IsPostDom>::calculate(
+    SmallVectorImpl<NodeTy *> &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.
+  using DomTreeNodePair =
+      std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
+  using IDFPriorityQueue =
+      std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
+                          less_second>;
+
+  IDFPriorityQueue PQ;
+
+  DT.updateDFSNumbers();
+
+  for (NodeTy *BB : *DefBlocks) {
+    if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
+      PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
+  }
+
+  SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
+  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
+  SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
+
+  while (!PQ.empty()) {
+    DomTreeNodePair RootPair = PQ.top();
+    PQ.pop();
+    DomTreeNodeBase<NodeTy> *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()) {
+      DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
+      NodeTy *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 = [&](NodeTy *Succ) {
+        DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
+
+        const unsigned SuccLevel = SuccNode->getLevel();
+        if (SuccLevel > RootLevel)
+          return;
+
+        if (!VisitedPQ.insert(SuccNode).second)
+          return;
+
+        NodeTy *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())));
+      };
+
+      for (auto Succ : getChildren(BB))
+        DoWork(Succ);
+
+      for (auto DomChild : *Node) {
+        if (VisitedWorklist.insert(DomChild).second)
+          Worklist.push_back(DomChild);
+      }
+    }
+  }
+}
+
+} // end of namespace llvm
+
+#endif

llvm/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   IVUsers.cpp
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionPrecedenceTracking.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
-  IteratedDominanceFrontier.cpp
   LazyBranchProbabilityInfo.cpp
   LazyBlockFrequencyInfo.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp
   LegacyDivergenceAnalysis.cpp
   Lint.cpp
   Loads.cpp
   LoopAccessAnalysis.cpp

llvm/lib/Analysis/IteratedDominanceFrontier.cpp

-//===- 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>;
-}