Page MenuHomePhabricator

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

Authored by Szelethus on Jun 16 2019, 3:12 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

Szelethus created this revision.Jun 16 2019, 3:12 PM
Szelethus edited the summary of this revision. (Show Details)Jun 16 2019, 3:15 PM
Szelethus edited the summary of this revision. (Show Details)Jun 17 2019, 3:04 AM
kuhar added a comment.Jun 17 2019, 8:17 AM

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?

Thanks!

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 added a comment.Jun 17 2019, 8:23 AM

Thanks!

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.

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 added a comment.EditedJun 17 2019, 10:18 AM

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 updated this revision to Diff 205480.EditedJun 18 2019, 5:37 PM
Szelethus edited the summary of this revision. (Show Details)

Reimplement D50675.

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 added a comment.Jun 19 2019, 8:25 AM

@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 updated this revision to Diff 205889.Jun 20 2019, 1:23 PM
Szelethus edited the summary of this revision. (Show Details)
Szelethus set the repository for this revision to rG LLVM Github Monorepo.

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 :^)

A polite ping :^)

kuhar accepted this revision.Jun 26 2019, 11:11 AM

Looks good now. I added a few nits inline.

llvm/include/llvm/Analysis/IteratedDominanceFrontier.h
84 ↗(On Diff #205889)

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

85 ↗(On Diff #205889)

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

This revision is now accepted and ready to land.Jun 26 2019, 11:11 AM
This revision was automatically updated to reflect the committed changes.