Expose CFG Update struct. Define GraphTraits to get children given a snapshot CFG.

[asbirlea]

Summary

Certain passes or analysis need to view a CFG snapshot rather than the actual CFG. This patch provides GraphTraits to offer such a view.

The patch defines GraphTraits for BasicBlock* and Inverse<BasicBlock*> to provide CFG successors and predecessors based on a list of CFG updates.

An Update is defined as a triple {InsertOrDeleteKind, BlockStartOfEdge, BlockEndOfEdge}.
A GraphDiff is defined as a list of Updates that has been preprocessed to treat the CFG as a graph rather than a multi-graph. As such, there can only exist a single Update given two nodes. All duplicates will be filtered and Insert/Delete edges that cancel out will be ignored.
The methods GraphDiff exposes are:

• Determine if an existing child needs to be ignored, i.e. an Update exists in the correct direction to assume the removal of that edge.
• Return a list of new children to be considered, i.e. an Update exists in the correct direction for each child in the list to assume the insertion of that edge.

[asbirlea]

Looking for feedback on this before moving forward. Some questions:

1. Namespace naming (cfg) and placement of Update struct.
2. Move WrappedPairNodeDataIterator somewhere in ADT, to reuse in LoopIterator.h?
3. The part to pre-process the Updates is not part of this patch. I would like to move GenericDomTreeConstruction::LegalizeUpdates somewhere in Support outside DomTreeBuilder namespace, in order to reuse the functionality. Where is a good place to have this, or are there objections to moving it?

Should these follow-up patches be part of this one?

1. Reference cfg::Update in DomTree, remove Update from DomTreeBuilder namespace.
2. Teach IDF to use children based on a GraphDiff, given the new GraphTraits in this patch.

[asbirlea]

Format.

[kuhar]

One thing that is not clear to me is how you decide whether to apply the updates on top of the current CFG or to reverse-apply them. DomTreeConstruction needs the latter, but I don't know what makes sense in your use-case.

I think that this should eventually replace the diffing functionality in the dominator tree construction. This should be also perhaps useful if we decide to go with CFG snapshots for easier incremental updates, like in @NutshellySima 's prototypes.

In D50479#1193105, @asbirlea wrote:

Looking for feedback on this before moving forward. Some questions:

1. Namespace naming (cfg) and placement of Update struct.

Fine with me.

2. Move WrappedPairNodeDataIterator somewhere in ADT, to reuse in LoopIterator.h?

Not familiar enough to suggest anything :/.

3. The part to pre-process the Updates is not part of this patch. I would like to move GenericDomTreeConstruction::LegalizeUpdates somewhere in Support outside DomTreeBuilder namespace, in order to reuse the functionality. Where is a good place to have this, or are there objections to moving it?

Fine with migrating it somewhere. I would keep it close to the update struct.

Should these follow-up patches be part of this one?

1. Reference cfg::Update in DomTree, remove Update from DomTreeBuilder namespace.

Fine with either now or a separate patch.

2. Teach IDF to use children based on a GraphDiff, given the new GraphTraits in this patch.

Where does IDF calculation need the diffing functionality?

include/llvm/IR/CFGDiff.h

42

It wan't obvious for me what this is for until I grepped for the field name and saw how it's used -- I'd add a comment saying why you need it.

72

Why is returning a pointer better than reference? Can this ever return nullptr?

80

I think it would be *extremely* useful to add a dump method here.

[asbirlea]

Right, I'm defining Inverse but not IsPostDom (from ChildrenGetter).
Adding a second bool is an easy option, and defining 2 more traits with:
std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>>
and
std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>>
These would set the second bool for the GraphDiff calls to reflect IsPostDom. NodeRef would remain the same.

The children call site in DomTree would look something like:
children<GraphDiffBBPair>({GD, BB})), with
using GraphDiffBBPair = std::pair<const GraphDiff<BasicBlock*> *, Inverse<BasicBlock*>; for predecessors in DomTree (and so on for all combos)

I agree that long term this can and should be reused in DomTree, so I'm trying to make it have the right functionality.
Another possibly related issue, is that I'm not reversing the children, as in DomTree, not sure the reason behind that one.

Another issue with the above traits: is there a way to avoid some of the code duplication, since the only differences are the bool arguments to GraphDiff and succ/pred iterators?

include/llvm/IR/CFGDiff.h

72

I really wanted to define the GraphTraits in the other header as a pair of a *const* GraphDiff* and BasicBlock*. This meant that I needed to have the methods const as well and they cannot return a reference. No, this can never return null.

The alternative to all this is to drop the const in the GraphTraits std::pair below and all the related const attributes. Personal preference is to keep them, but if folks have strong preferences otherwise, I'm open to changing it.

[kuhar]

In D50479#1194111, @asbirlea wrote:

Another issue with the above traits: is there a way to avoid some of the code duplication, since the only differences are the bool arguments to GraphDiff and succ/pred iterators?

I think you can create a base class with extra template parameters and then inherit from it, specializing the parameters you want. There's something similar in BlockFrequencyInfoImpl.h.

[kuhar]

In D50479#1194111, @asbirlea wrote:

I agree that long term this can and should be reused in DomTree, so I'm trying to make it have the right functionality.
Another possibly related issue, is that I'm not reversing the children, as in DomTree, not sure the reason behind that one.

Sure. The children are being reversed to preserve the successor order in DFS, which uses stack and reverses them (again) internally. But this reverse can be moved somewhere else and you don't have to worry about it.

[timshen]

include/llvm/IR/CFGDiff.h

60

Can we have a void verify() const that verifies the class invariants? e.g. whether duplicated edges are allowed, can one edge exist in both delete and insert, etc. We can call it with the guards of #ifdef EXPENSIVE_CHECKS.

72

Would it be better to return iterator_range(SmallVectorImpl<NodePtr>::const_iterator)?

111

Optional: The two GraphTraits specializations are highly duplicated. Maybe find a way to de-duplicate them?

The only differences between the two specializations are (1) succ_iterator vs succ_iterator, (2) succ_begin/succ_end vs pred_begin/pred_end, and (3) false vs true gets passed to getAddedChildren.

Both (1) and (2) can be abstracted in a common place. Maybe add some "inverse utility"?

include/llvm/Support/CFGUpdate.h

23

Due to the use of PointerIntPair, it's better be a class and hides the data members.

39

Can this be a print() and/or dump() function, consistent with other types?

[asbirlea]

Address most comments.
Partially resolved GraphTraits duplication, working out if I can fully parametrize on succ/pred.

[asbirlea]

include/llvm/IR/CFGDiff.h

60

I added the LegalizeUpdates call that should guarantee the specified behavior. Let me know if this is a good solution.

72

Works for me, updated.

[kuhar]

include/llvm/IR/CFGDiff.h

61

It's not clear to me what InverseGraph means here.

83

return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();

102

missing )? :P

114

please guard this with the macro for dump methods

include/llvm/Support/CFGUpdate.h

48

Same as above - please guard this with the macro.

[timshen]

include/llvm/IR/CFGDiff.h

61

I imagine that if InverseGraph, then To is a predecessor of From. If not InverseGraph, To is a successor of From. Maybe you want to document that?

88

"const" is not necessary here. It doesn't prevent the caller from removing the const anyway.

include/llvm/Support/CFGUpdate.h

73

There is no need to swap?

96

If the previous swap is removed, I guess this will always be Operations[{U.getFrom(), U.getTo()}] = int(i);.

[kuhar]

include/llvm/IR/CFGDiff.h

61

What confuses me is it's already possible to Pass Inverse<BB*> as the template arguments, so it's not clear if InverseGraph is for the graph, the updates, or if it means to swap insertions and deletions of edges.

It would be really helpful to add a comment about it above.

include/llvm/Support/CFGUpdate.h

73

DomTree and PostDomTree allow you to pass the same update vector to both, but since PostDomTree operates on inverse CFG, you have to swap somewhere to make it work.

I believe this was just copied from the domtree code.

[timshen]

Unintentional LGTM. But it's close. :)

[asbirlea]

include/llvm/IR/CFGDiff.h

61

Let me try to clarify what I had in mind and please let me know if this makes sense in terms of generality. There is also a comment about this below which I'd be happy to move around and expand to give clarity.

There are 2 boolean values used consistently throughout this file: InverseGraph and InverseEdge. InverseGraph refers to having a normal graph, or viewing the graph in reverse, which is analogous with reverse-applying updates.
InverseEdge refers to the direction of the edges you're looking for. For a non-inversed graph, that's naturally successors when InverseEdge is false and predecessors when InverseEdge is true.

Below there are two classes that call into GraphDiff:
CFGViewSuccessors and CFGViewPredecessors, both can be parametrized to consider the graph inverted or not (i.e. InverseGraph). Successors implicitly has InverseEdge = false and Predecessors implicitly has InverseEdge = true (see calls to GraphDiff methods in there).

In the GraphTraits instantiations:

• GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
• GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
• second pair item is BasicBlock *, then InverseEdge = false
• second pair item is Inverse<BasicBlock *>, then InverseEdge = true

The 4 GraphTraits are as follows:

1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> : CFGViewSuccessors<false>

Regular CFG, children means successors, InverseGraph = false, InverseEdge = false.

2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> : CFGViewSuccessors<true>

Reverse the graph, get successors but reverse-apply updates, InverseGraph = true, InverseEdge = false.

3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> : CFGViewPredecessors<false>

Regular CFG, reverse edges, so children mean predecessors, InverseGraph = false, InverseEdge = true.

4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>> : CFGViewPredecessors<true>

Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.

If this makes sense, I'll make this explanation into a comment before GraphDiff, rather than before CFGViewSuccessors.

include/llvm/Support/CFGUpdate.h

73

The swap is intentional, for reverse-applying updates. It refers to the first bool: InverseGraph and should be used for PostDomTree.
Yes, the method is copied from the domtree code. I have a dependent patch to clean that up (remove Update struct and legalizeUpdates).

[asbirlea]

Updated documentation in CFGDiff to describe InverseEdge adn InverseGraph.
Moved wrapper iterator to ADT/iterator.h

Thanks a lot for the comments so far!

[kuhar]

Thanks for the changes. LGTM.

[asbirlea]

Thank you for the review, Kuba! I'll wait for Tim's input as well in case he has more comments.

[timshen]

include/llvm/Support/CFGUpdate.h

106

Just want to make sure that this sorts to descending order.

[asbirlea]

include/llvm/Support/CFGUpdate.h

106

Yes, that's right. The reason is that DomTree then applies updates from the end of the vector, so they will be applied in the original order.

My use case of GraphDiff does not care about update order and I don't want to change the order for DomTree, so I'll leave it like this in this patch.
I'm planning to refactor DomTree to use GraphDiff instead of its inner data structure (BatchUpdaterInfo), so then I can tell DT to use the Updates in order, and also reverse the sort here.

include/llvm/IR/CFGDiff.h

+//===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines specializations of GraphTraits that allows generic
+// algorithms to see a different snapshot of a CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_CFGDIFF_H
+#define LLVM_IR_CFGDIFF_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/Support/CFGUpdate.h"
+#include "llvm/Support/type_traits.h"
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+
+namespace llvm {
+
+// GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
+// utilities to skip edges marked as deleted and return a set of edges marked as
+// newly inserted. The current diff treats the CFG as a graph rather than a
+// multigraph. Added edges are pruned to be unique, and deleted edges will
+// remove all existing edges between two blocks.
+template <typename NodePtr>
+class GraphDiff {
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> SuccInsert;
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> SuccDelete;
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> PredInsert;
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> PredDelete;
+  SmallVector<NodePtr, 1> Empty;
+
+  public:
+  GraphDiff () {}
+  GraphDiff (ArrayRef<cfg::Update<NodePtr>> Updates) {
+    for (auto U : Updates) {
+      //TODO: preprocessing to remove duplicates and edges that cancel out.
+      // see: LegalizeUpdates in DomTreeConstruction.
+
+      if (U.getKind() == cfg::UpdateKind::Insert) {
+        SuccInsert[U.getFrom()].push_back(U.getTo());
+        PredInsert[U.getTo()].push_back(U.getFrom());
+      }
+      else {
+        SuccDelete[U.getFrom()].push_back(U.getTo());
+        PredDelete[U.getTo()].push_back(U.getFrom());
+      }
+    }
+  }
+
+  bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool Inverse) const {
+    auto &DeleteChildren = Inverse ? PredDelete : SuccDelete;
+    auto It = DeleteChildren.find(BB);
+    if (It == DeleteChildren.end())
+      return false;
+    auto &EdgesForBB = It->second;
+    if (llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end())
+      return true;
+    return false;
+  }
+
+  const SmallVectorImpl<NodePtr>* getAddedChildren(const NodePtr BB, bool Inverse) const {
+    auto &InsertChildren = Inverse ? PredInsert : SuccInsert;
+    auto It = InsertChildren.find(BB);
+    if (It == InsertChildren.end())
+      return &Empty;
+    return &It->second;
+  }
+};
+
+// Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
+// to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
+template <typename ItType, typename NodeRef, typename DataRef>
+class WrappedPairNodeDataIterator
+    : public iterator_adaptor_base<
+          WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
+          typename std::iterator_traits<ItType>::iterator_category,
+          NodeRef, std::ptrdiff_t, NodeRef *, NodeRef &> {
+  using BaseT = iterator_adaptor_base<
+      WrappedPairNodeDataIterator, ItType,
+      typename std::iterator_traits<ItType>::iterator_category,
+      NodeRef, std::ptrdiff_t, NodeRef *, NodeRef &>;
+
+  const DataRef DR;
+  mutable NodeRef NR;
+
+public:
+  WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
+      : BaseT(Begin), DR(DR) { NR.first = DR; }
+
+  NodeRef& operator*() const {
+    NR.second = *this->I;
+    return NR;
+  }
+};
+
+template <> struct GraphTraits<std::pair<const GraphDiff<BasicBlock*> *, BasicBlock*>> {
+  using DataRef = const GraphDiff<BasicBlock*> *;
+  using NodeRef = std::pair<DataRef, BasicBlock *>;
+
+  using SuccIterator = WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
+  struct DeletedEdgesFilter {
+    BasicBlock *BB;
+    DeletedEdgesFilter (BasicBlock *BB) : BB(BB) {};
+    bool operator()(NodeRef N) const {
+      return !N.first->ignoreChild(BB, N.second, false);
+    }
+  };
+  using FilterSuccessorsIterator =
+      filter_iterator<SuccIterator, DeletedEdgesFilter>;
+
+  using vec_iterator = SmallVectorImpl<BasicBlock*>::const_iterator;
+  using AddNewSuccessorsIterator = WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
+  using ChildIteratorType =
+      concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator>;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, false);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<SuccIterator>(
+              {succ_begin(N.second), N.first},
+              {succ_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->begin(), N.first},
+              {InsertVec->end(), N.first});
+
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, false);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<SuccIterator>(
+              {succ_end(N.second), N.first},
+              {succ_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->end(), N.first},
+              {InsertVec->end(), N.first});
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+};
+
+template <> struct GraphTraits<std::pair<const GraphDiff<BasicBlock*> *, Inverse<BasicBlock*>>> {
+  using DataRef = const GraphDiff<BasicBlock*> *;
+  using NodeRef = std::pair<DataRef, BasicBlock *>;
+
+  using PredIterator = WrappedPairNodeDataIterator<pred_iterator, NodeRef, DataRef>;
+  struct DeletedEdgesFilter {
+    BasicBlock *BB;
+    DeletedEdgesFilter (BasicBlock *BB) : BB(BB) {};
+    bool operator()(NodeRef N) const {
+      return !N.first->ignoreChild(BB, N.second, true);
+    }
+  };
+  using FilterSuccessorsIterator =
+      filter_iterator<PredIterator, DeletedEdgesFilter>;
+
+  using vec_iterator = SmallVectorImpl<BasicBlock*>::const_iterator;
+  using AddNewSuccessorsIterator = WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
+  using ChildIteratorType =
+      concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator>;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, true);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<PredIterator>(
+              {pred_begin(N.second), N.first},
+              {pred_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->begin(), N.first},
+              {InsertVec->end(), N.first});
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, true);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<PredIterator>(
+              {pred_end(N.second), N.first},
+              {pred_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->end(), N.first},
+              {InsertVec->end(), N.first});
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+};
+} // end namespace llvm
+
+#endif // LLVM_IR_CFGDIFF_H

include/llvm/Support/CFGUpdate.h

+//===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the
+// Edge ends.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CFGUPDATE_H
+#define LLVM_SUPPORT_CFGUPDATE_H
+
+namespace llvm {
+namespace cfg {
+enum class UpdateKind : unsigned char { Insert, Delete };
+
+template <typename NodePtr>
+struct Update {
+  using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
+
+  NodePtr From;
+  NodeKindPair ToAndKind;
+
+  Update(UpdateKind Kind, NodePtr From, NodePtr To)
+      : From(From), ToAndKind(To, Kind) {}
+
+  UpdateKind getKind() const { return ToAndKind.getInt(); }
+  NodePtr getFrom() const { return From; }
+  NodePtr getTo() const { return ToAndKind.getPointer(); }
+  bool operator==(const Update &RHS) const {
+    return From == RHS.From && ToAndKind == RHS.ToAndKind;
+  }
+
+  friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
+    OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
+    U.getFrom()->printAsOperand(OS, false);
+    OS << " -> ";
+    U.getTo()->printAsOperand(OS, false);
+    return OS;
+  }
+};
+} // end namespace cfg
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_CFGUPDATE_H