[Analysis] Change several Analysis pieces to use NodeRef. NFC.

[dblaikie]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1274

I'm confused by this '&'.

If GraphTraits is meant to be node handle agnostic, why is it producing a dereferenced node handle type here? (such that the address needs to be taken again)

include/llvm/Analysis/RegionIterator.h

59

This would still be restricted to pointers - so it doesn't actually generalize over the new node handles you are introducing.

Does this need deeper changes?

283–312

Might be worth reformatting this in a separate preliminary commit (no review required, jsut mash clang-format on that, commit, then resolve the changes against this commit/code review)

[timshen]

Added static_assert.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1274

This is more or less embarrassing:

Some implementors decide to let *I return NodeType& (e.g. I as Function::iterator), while others decide to let *I return NodeType*.

GraphWriter has the same problem. The solution of GraphWriter (even before the NodeType -> NodeRef change) is to pass *I into Foo, where Foo is overloaded on NodeType&, NodeType* and NodeType **.

include/llvm/Analysis/RegionIterator.h

59

As discussed offline, put a static_assert here.

[timshen]

Rebase onto the formatted code.

[dblaikie]

include/llvm/Analysis/RegionIterator.h

35

If it has to be a pointer type anyway - would it be simpler to preserve that behavior of value_type being a pointer rather than a value? Or is there something else going on here as well that makes this change necessary/useful?

[timshen]

include/llvm/Analysis/RegionIterator.h

35

Actually by looking at the code, I can tell that NodeType is always GraphTraits<BlockT*>::NodeType. After the migration I prefer to keep the consistency, that is the template parameter NodeRef is always GraphTraits<BlockT*>::NodeRef. The fact that NodeRef is required to be a pointer seems not worthy to be mentioned too frequently.

The code also assumes that BlockT* is NodeRef/NodeType*. And the code also uses getParent(). I'm sad that people stick on GraphTraits just because it exists, when TreeTraits could be a better fit.

[grosser]

Hi Tim,

thank you for looking through this. The general direction and the changes look fine for RegionInfo. I let David finish his detailed comments (thank you David!) for him to give the final OK.

include/llvm/Analysis/RegionIterator.h

59

This seems a good solution for now. This PointerIntPair should just be replaced with two separate fields, but can be done later on. However, this will not be sufficient to allow pointer types, as there seem to be other uses of PtrSet, which would need to be changed. I assume we leave this for when there is an actual need for a non-pointer type.

[timshen]

Changed the static_assert error message accordingly.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

 enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count };
 
 template <class BlockFrequencyInfoT, class BranchProbabilityInfoT>
 struct BFIDOTGraphTraitsBase : public DefaultDOTGraphTraits {
   explicit BFIDOTGraphTraitsBase(bool isSimple = false)
       : DefaultDOTGraphTraits(isSimple) {}
 
   typedef GraphTraits<BlockFrequencyInfoT *> GTraits;
-  typedef typename GTraits::NodeType NodeType;
+  typedef typename GTraits::NodeRef NodeRef;
   typedef typename GTraits::ChildIteratorType EdgeIter;
   typedef typename GTraits::nodes_iterator NodeIter;
 
   uint64_t MaxFrequency = 0;
   static std::string getGraphName(const BlockFrequencyInfoT *G) {
     return G->getFunction()->getName();
   }
 
-  std::string getNodeAttributes(const NodeType *Node,
-                                const BlockFrequencyInfoT *Graph,
+  std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph,
                                 unsigned HotPercentThreshold = 0) {
     std::string Result;
     if (!HotPercentThreshold)
       return Result;
 
     // Compute MaxFrequency on the fly:
     if (!MaxFrequency) {
       for (NodeIter I = GTraits::nodes_begin(Graph),
                     E = GTraits::nodes_end(Graph);
            I != E; ++I) {
-        NodeType &N = *I;
+        NodeRef N = &*I;
         MaxFrequency =
-            std::max(MaxFrequency, Graph->getBlockFreq(&N).getFrequency());
+            std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency());
       }
     }
     BlockFrequency Freq = Graph->getBlockFreq(Node);
     BlockFrequency HotFreq =
         (BlockFrequency(MaxFrequency) *
          BranchProbability::getBranchProbability(HotPercentThreshold, 100));
 
     if (Freq < HotFreq)
       return Result;
 
     raw_string_ostream OS(Result);
     OS << "color=\"red\"";
     OS.flush();
     return Result;
   }
 
-  std::string getNodeLabel(const NodeType *Node,
-                           const BlockFrequencyInfoT *Graph, GVDAGType GType) {
+  std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph,
+                           GVDAGType GType) {
     std::string Result;
     raw_string_ostream OS(Result);
 
     OS << Node->getName().str() << " : ";
     switch (GType) {
     case GVDT_Fraction:
       Graph->printBlockFreq(OS, Node);
       break;
std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph,
     }
     case GVDT_None:
       llvm_unreachable("If we are not supposed to render a graph we should "
                        "never reach this point.");
     }
     return Result;
   }
 
-  std::string getEdgeAttributes(const NodeType *Node, EdgeIter EI,
+  std::string getEdgeAttributes(NodeRef Node, EdgeIter EI,
                                 const BlockFrequencyInfoT *BFI,
                                 const BranchProbabilityInfoT *BPI,
                                 unsigned HotPercentThreshold = 0) {
     std::string Str;
     if (!BPI)
       return Str;
 
     BranchProbability BP = BPI->getEdgeProbability(Node, EI);

include/llvm/Analysis/LoopInfoImpl.h

BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
   BlockT *Out = nullptr;
 
   // Loop over the predecessors of the header node...
   BlockT *Header = getHeader();
   typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
   for (typename InvBlockTraits::ChildIteratorType PI =
          InvBlockTraits::child_begin(Header),
          PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
-    typename InvBlockTraits::NodeType *N = *PI;
+    typename InvBlockTraits::NodeRef N = *PI;
     if (!contains(N)) {     // If the block is not in the loop...
       if (Out && Out != N)
         return nullptr;     // Multiple predecessors outside the loop
       Out = N;
     }
   }
 
   // Make sure there is only one exit out of the preheader.
   assert(Out && "Header of loop has no predecessors from outside loop?");
   return Out;
 }
 
 /// getLoopLatch - If there is a single latch block for this loop, return it.
 /// A latch block is a block that contains a branch back to the header.
 template<class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
   BlockT *Header = getHeader();
   typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
   typename InvBlockTraits::ChildIteratorType PI =
     InvBlockTraits::child_begin(Header);
   typename InvBlockTraits::ChildIteratorType PE =
     InvBlockTraits::child_end(Header);
   BlockT *Latch = nullptr;
   for (; PI != PE; ++PI) {
-    typename InvBlockTraits::NodeType *N = *PI;
+    typename InvBlockTraits::NodeRef N = *PI;
     if (contains(N)) {
       if (Latch) return nullptr;
       Latch = N;
     }
   }
 
   return Latch;
 }

include/llvm/Analysis/RegionIterator.h

 /// This iterator iterates over all successors of a RegionNode.
 ///
 /// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
 /// the parent Region.  Furthermore for BasicBlocks that start a subregion, a
 /// RegionNode representing the subregion is returned.
 ///
 /// For a subregion RegionNode there is just one successor. The RegionNode
 /// representing the exit of the subregion.
-template<class NodeType, class BlockT, class RegionT>
-class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
-                                           NodeType, ptrdiff_t> {
-  typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
+template <class NodeRef, class BlockT, class RegionT>
+class RNSuccIterator
+    : public std::iterator<std::forward_iterator_tag, NodeRef> {
+  typedef std::iterator<std::forward_iterator_tag, NodeRef> super;
 
   typedef GraphTraits<BlockT*> BlockTraits;
   typedef typename BlockTraits::ChildIteratorType SuccIterTy;
 
   // The iterator works in two modes, bb mode or region mode.
   enum ItMode {
     // In BB mode it returns all successors of this BasicBlock as its
     // successors.
     ItBB,
     // In region mode there is only one successor, thats the regionnode mapping
     // to the exit block of the regionnode
     ItRgBegin, // At the beginning of the regionnode successor.
     ItRgEnd    // At the end of the regionnode successor.
   };
 
+  static_assert(std::is_pointer<NodeRef>::value,
+                "FIXME: Currently RNSuccIterator only supports NodeRef as "
+                "pointers due to the use of pointer-specific data structures "
+                "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
+                "it to support non-pointer types");
+
   // Use two bit to represent the mode iterator.
-  PointerIntPair<NodeType*, 2, ItMode> Node;
+  PointerIntPair<NodeRef, 2, ItMode> Node;
 
   // The block successor iterator.
   SuccIterTy BItor;
 
   // advanceRegionSucc - A region node has only one successor. It reaches end
   // once we advance it.
   void advanceRegionSucc() {
     assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
     Node.setInt(ItRgEnd);
   }
 
-  NodeType* getNode() const{ return Node.getPointer(); }
+  NodeRef getNode() const { return Node.getPointer(); }
 
   // isRegionMode - Is the current iterator in region mode?
   bool isRegionMode() const { return Node.getInt() != ItBB; }
 
   // Get the immediate successor. This function may return a Basic Block
   // RegionNode or a subregion RegionNode.
-  NodeType* getISucc(BlockT* BB) const {
-    NodeType *succ;
+  NodeRef getISucc(BlockT *BB) const {
+    NodeRef succ;
     succ = getNode()->getParent()->getNode(BB);
     assert(succ && "BB not in Region or entered subregion!");
     return succ;
   }
 
   // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
   inline BlockT* getRegionSucc() const {
     assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
     return getNode()->template getNodeAs<RegionT>()->getExit();
   }
 
   // isExit - Is this the exit BB of the Region?
   inline bool isExit(BlockT* BB) const {
     return getNode()->getParent()->getExit() == BB;
   }
 public:
-  typedef RNSuccIterator<NodeType, BlockT, RegionT> Self;
+  typedef RNSuccIterator<NodeRef, BlockT, RegionT> Self;
 
-  typedef typename super::pointer pointer;
+  typedef typename super::value_type value_type;
 
   /// @brief Create begin iterator of a RegionNode.
-  inline RNSuccIterator(NodeType* node)
+  inline RNSuccIterator(NodeRef node)
       : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
         BItor(BlockTraits::child_begin(node->getEntry())) {
 
     // Skip the exit block
     if (!isRegionMode())
       while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
         ++BItor;
 
     if (isRegionMode() && isExit(getRegionSucc()))
       advanceRegionSucc();
   }
 
   /// @brief Create an end iterator.
-  inline RNSuccIterator(NodeType* node, bool)
+  inline RNSuccIterator(NodeRef node, bool)
       : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
         BItor(BlockTraits::child_end(node->getEntry())) {}
 
   inline bool operator==(const Self& x) const {
     assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
     if (isRegionMode())
       return Node.getInt() == x.Node.getInt();
     else
       return BItor == x.BItor;
   }
 
   inline bool operator!=(const Self& x) const { return !operator==(x); }
 
-  inline pointer operator*() const {
+  inline value_type operator*() const {
     BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
     assert(!isExit(BB) && "Iterator out of range!");
     return getISucc(BB);
   }
 
   inline Self& operator++() {
     if(isRegionMode()) {
       // The Region only has 1 successor.

 
 
 //===----------------------------------------------------------------------===//
 /// @brief Flat RegionNode iterator.
 ///
 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
 /// are contained in the Region and its subregions. This is close to a virtual
 /// control flow graph of the Region.
-template<class NodeType, class BlockT, class RegionT>
-class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>
-  : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> {
-  typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
+template <class NodeRef, class BlockT, class RegionT>
+class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
+    : public std::iterator<std::forward_iterator_tag, NodeRef> {
+  typedef std::iterator<std::forward_iterator_tag, NodeRef> super;
   typedef GraphTraits<BlockT*> BlockTraits;
   typedef typename BlockTraits::ChildIteratorType SuccIterTy;
 
-  NodeType* Node;
+  NodeRef Node;
   SuccIterTy Itor;
 
 public:
-  typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self;
-  typedef typename super::pointer pointer;
+  typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> Self;
+  typedef typename super::value_type value_type;
 
   /// @brief Create the iterator from a RegionNode.
   ///
   /// Note that the incoming node must be a bb node, otherwise it will trigger
   /// an assertion when we try to get a BasicBlock.
-  inline RNSuccIterator(NodeType *node)
+  inline RNSuccIterator(NodeRef node)
       : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
     assert(!Node->isSubRegion() &&
            "Subregion node not allowed in flat iterating mode!");
     assert(Node->getParent() && "A BB node must have a parent!");
 
     // Skip the exit block of the iterating region.
     while (BlockTraits::child_end(Node->getEntry()) != Itor &&
            Node->getParent()->getExit() == *Itor)
       ++Itor;
   }
 
   /// @brief Create an end iterator
-  inline RNSuccIterator(NodeType *node, bool)
+  inline RNSuccIterator(NodeRef node, bool)
       : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
     assert(!Node->isSubRegion() &&
            "Subregion node not allowed in flat iterating mode!");
   }
 
   inline bool operator==(const Self& x) const {
     assert(Node->getParent() == x.Node->getParent()
            && "Cannot compare iterators of different regions!");
 
     return Itor == x.Itor && Node == x.Node;
   }
 
   inline bool operator!=(const Self& x) const { return !operator==(x); }
 
-  inline pointer operator*() const {
+  inline value_type operator*() const {
     BlockT *BB = *Itor;
 
     // Get the iterating region.
     RegionT *Parent = Node->getParent();
 
     // The only case that the successor reaches out of the region is it reaches
     // the exit of the region.
     assert(Parent->getExit() != BB && "iterator out of range!");
public:
 
   inline Self operator++(int) {
     Self tmp = *this;
     ++*this;
     return tmp;
   }
 };
 
-template<class NodeType, class BlockT, class RegionT>
-inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) {
-  return RNSuccIterator<NodeType, BlockT, RegionT>(Node);
+template <class NodeRef, class BlockT, class RegionT>
+inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
+  return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
 }
 
-template<class NodeType, class BlockT, class RegionT>
-inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) {
-  return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true);
+template <class NodeRef, class BlockT, class RegionT>
+inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
+  return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true);
 }
 
 //===--------------------------------------------------------------------===//
 // RegionNode GraphTraits specialization so the bbs in the region can be
 // iterate by generic graph iterators.
 //
 // NodeT can either be region node or const region node, otherwise child_begin
 // and child_end fail.
 
 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT)                          \
   template <> struct GraphTraits<NodeT *> {                                    \
     typedef NodeT NodeType;                                                    \
     typedef NodeT *NodeRef;                                                    \
-    typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType;       \
-    static NodeType *getEntryNode(NodeType *N) { return N; }                   \
-    static inline ChildIteratorType child_begin(NodeType *N) {                 \
-      return RNSuccIterator<NodeType, BlockT, RegionT>(N);                     \
+    typedef RNSuccIterator<NodeRef, BlockT, RegionT> ChildIteratorType;        \
+    static NodeRef getEntryNode(NodeRef N) { return N; }                       \
+    static inline ChildIteratorType child_begin(NodeRef N) {                   \
+      return RNSuccIterator<NodeRef, BlockT, RegionT>(N);                      \
     }                                                                          \
-    static inline ChildIteratorType child_end(NodeType *N) {                   \
-      return RNSuccIterator<NodeType, BlockT, RegionT>(N, true);               \
+    static inline ChildIteratorType child_end(NodeRef N) {                     \
+      return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true);                \
     }                                                                          \
   };                                                                           \
   template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
     typedef NodeT NodeType;                                                    \
     typedef NodeT *NodeRef;                                                    \
-    typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT> ChildIteratorType;  \
-    static NodeType *getEntryNode(NodeType *N) { return N; }                   \
-    static inline ChildIteratorType child_begin(NodeType *N) {                 \
-      return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N);             \
+    typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>                   \
+        ChildIteratorType;                                                     \
+    static NodeRef getEntryNode(NodeRef N) { return N; }                       \
+    static inline ChildIteratorType child_begin(NodeRef N) {                   \
+      return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N);              \
     }                                                                          \
-    static inline ChildIteratorType child_end(NodeType *N) {                   \
-      return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true);       \
+    static inline ChildIteratorType child_end(NodeRef N) {                     \
+      return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true);        \
     }                                                                          \
   }
 
 #define RegionGraphTraits(RegionT, NodeT)                                      \
   template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> {    \
-    typedef df_iterator<NodeType *> nodes_iterator;                            \
-    static NodeType *getEntryNode(RegionT *R) {                                \
+    typedef df_iterator<NodeRef> nodes_iterator;                               \
+    static NodeRef getEntryNode(RegionT *R) {                                  \
       return R->getNode(R->getEntry());                                        \
     }                                                                          \
     static nodes_iterator nodes_begin(RegionT *R) {                            \
       return nodes_iterator::begin(getEntryNode(R));                           \
     }                                                                          \
     static nodes_iterator nodes_end(RegionT *R) {                              \
       return nodes_iterator::end(getEntryNode(R));                             \
     }                                                                          \
   };                                                                           \
   template <>                                                                  \
   struct GraphTraits<FlatIt<RegionT *>>                                        \
       : public GraphTraits<FlatIt<NodeT *>> {                                  \
-    typedef df_iterator<NodeType *, SmallPtrSet<NodeType *, 8>, false,         \
-                        GraphTraits<FlatIt<NodeType *>>>                       \
+    typedef df_iterator<NodeRef, SmallPtrSet<NodeRef, 8>, false,               \
+                        GraphTraits<FlatIt<NodeRef>>>                          \
         nodes_iterator;                                                        \
-    static NodeType *getEntryNode(RegionT *R) {                                \
+    static NodeRef getEntryNode(RegionT *R) {                                  \
       return R->getBBNode(R->getEntry());                                      \
     }                                                                          \
     static nodes_iterator nodes_begin(RegionT *R) {                            \
       return nodes_iterator::begin(getEntryNode(R));                           \
     }                                                                          \
     static nodes_iterator nodes_end(RegionT *R) {                              \
       return nodes_iterator::end(getEntryNode(R));                             \
     }                                                                          \
   }
 
 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
 
 RegionGraphTraits(Region, RegionNode);
 RegionGraphTraits(const Region, const RegionNode);
 
 template <> struct GraphTraits<RegionInfo*>
   : public GraphTraits<FlatIt<RegionNode*> > {
-  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
-                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
+  typedef df_iterator<NodeRef, SmallPtrSet<NodeRef, 8>, false,
+                      GraphTraits<FlatIt<NodeRef>>>
+      nodes_iterator;
 
-  static NodeType *getEntryNode(RegionInfo *RI) {
+  static NodeRef getEntryNode(RegionInfo *RI) {
     return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
   }
   static nodes_iterator nodes_begin(RegionInfo* RI) {
     return nodes_iterator::begin(getEntryNode(RI));
   }
   static nodes_iterator nodes_end(RegionInfo *RI) {
     return nodes_iterator::end(getEntryNode(RI));
   }
 };
 
 template <> struct GraphTraits<RegionInfoPass*>
   : public GraphTraits<RegionInfo *> {
-  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
-                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
+  typedef df_iterator<NodeRef, SmallPtrSet<NodeRef, 8>, false,
+                      GraphTraits<FlatIt<NodeRef>>>
+      nodes_iterator;
 
-  static NodeType *getEntryNode(RegionInfoPass *RI) {
+  static NodeRef getEntryNode(RegionInfoPass *RI) {
     return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
   }
   static nodes_iterator nodes_begin(RegionInfoPass* RI) {
     return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
   }
   static nodes_iterator nodes_end(RegionInfoPass *RI) {
     return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
   }
 };
 
 } // End namespace llvm
 
 #endif