[ADT] Change PostOrderIterator to use NodeRef. NFC.

[dblaikie]

include/llvm/ADT/PostOrderIterator.h

93–95 ↗

(On Diff #68069)

Having T == Pointer == Reference seems wrong. Could you explain how that works?

126 ↗

(On Diff #68069)

Optional<T>() => None

(& in a few other places)

[timshen]

include/llvm/ADT/PostOrderIterator.h

93–95 ↗

(On Diff #68069)

This is because po_iterator has "non-standard" operator*() and operator->().

Ideally, value_type should be NodeRef, reference type is NodeRef& and pointer_type is NodeRef*, but that way the current operator*() and operator->()'s returned types don't suffice.

I think it's an orthogonal issue apart from this patch.

126 ↗

(On Diff #68069)

The conversion doesn't work here, because po_iterator_storage has insertEdge as a template function on NodeRef.

We can move the "template <typename NodeRef>" from insertEdge up to po_iterator_storage, but that involves other po_iterator_storage template changes as well.

[dblaikie]

include/llvm/ADT/PostOrderIterator.h

126 ↗

(On Diff #68069)

Alternatively you could take the first argument to insertEdge as an opaque parameter (another template parameter T) and then convert it in the implementation:

Optional<NodeRef> From = FromValue;

But that might be too weird/complicated with all the different implementations.

[timshen]

Make std::iterator<...> look normal again.

[timshen]

include/llvm/ADT/PostOrderIterator.h

93–95 ↗

(On Diff #68081)

Hey somehow I realized that it's only operator->() that is non-standard. I make std::iterator<...> normal, leaving operator->() returning NodeRef. If NodeRef isn't a pointer and the user never calls PoIterator->..., the user code still builds.

122 ↗

(On Diff #68081)

Yeah, the main reason I don't want that is it aggressively generalize the insertEdge's interface.

[dblaikie]

include/llvm/ADT/PostOrderIterator.h

122 ↗

(On Diff #68081)

Not sure I follow - it doesn't really make the interface more permissive (if there were overloads then you'd need some SFINAE to promote the internal template errors out onto the interface to ensure overload resolution did the right thing is the only big wrinkle) - so far as I can see.

Anything that can be implicitly converted to Optional<NodeRef> seems to be what the function is trying to accept.

[timshen]

include/llvm/ADT/PostOrderIterator.h

122 ↗

(On Diff #68081)

Assuming that the user relies on template argument deduction, then the user has to pass in an Optional<...> object, right? This limits the interface to take Optional objects, not any T that is convertible to an Optional object.

If the user doesn't rely on template argument deduction, they are the same.

llvm/trunk/include/llvm/ADT/PostOrderIterator.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_POSTORDERITERATOR_H
 #define LLVM_ADT_POSTORDERITERATOR_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/iterator_range.h"
+#include "llvm/ADT/Optional.h"
 #include <set>
 #include <vector>
 
 namespace llvm {
 
 // The po_iterator_storage template provides access to the set of already
 // visited nodes during the po_iterator's depth-first traversal.
 //

 // on to the next node.
 
 /// Default po_iterator_storage implementation with an internal set object.
 template<class SetType, bool External>
 class po_iterator_storage {
   SetType Visited;
 public:
   // Return true if edge destination should be visited.
-  template<typename NodeType>
-  bool insertEdge(NodeType *From, NodeType *To) {
+  template <typename NodeRef>
+  bool insertEdge(Optional<NodeRef> From, NodeRef To) {
     return Visited.insert(To).second;
   }
 
   // Called after all children of BB have been visited.
-  template<typename NodeType>
-  void finishPostorder(NodeType *BB) {}
+  template <typename NodeRef> void finishPostorder(NodeRef BB) {}
 };
 
 /// Specialization of po_iterator_storage that references an external set.
 template<class SetType>
 class po_iterator_storage<SetType, true> {
   SetType &Visited;
 public:
   po_iterator_storage(SetType &VSet) : Visited(VSet) {}
   po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {}
 
   // Return true if edge destination should be visited, called with From = 0 for
   // the root node.
   // Graph edges can be pruned by specializing this function.
-  template <class NodeType> bool insertEdge(NodeType *From, NodeType *To) {
+  template <class NodeRef> bool insertEdge(Optional<NodeRef> From, NodeRef To) {
     return Visited.insert(To).second;
   }
 
   // Called after all children of BB have been visited.
-  template<class NodeType>
-  void finishPostorder(NodeType *BB) {}
+  template <class NodeRef> void finishPostorder(NodeRef BB) {}
 };
 
-template<class GraphT,
-  class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
-  bool ExtStorage = false,
-  class GT = GraphTraits<GraphT> >
-class po_iterator : public std::iterator<std::forward_iterator_tag,
-                                         typename GT::NodeType, ptrdiff_t>,
-                    public po_iterator_storage<SetType, ExtStorage> {
-  typedef std::iterator<std::forward_iterator_tag,
-                        typename GT::NodeType, ptrdiff_t> super;
-  typedef typename GT::NodeType          NodeType;
+template <class GraphT,
+          class SetType =
+              llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeRef, 8>,
+          bool ExtStorage = false, class GT = GraphTraits<GraphT>>
+class po_iterator
+    : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
+  typedef std::iterator<std::forward_iterator_tag, typename GT::NodeRef> super;
+  typedef typename GT::NodeRef NodeRef;
   typedef typename GT::ChildIteratorType ChildItTy;
 
   // VisitStack - Used to maintain the ordering.  Top = current block
   // First element is basic block pointer, second is the 'next child' to visit
-  std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
+  std::vector<std::pair<NodeRef, ChildItTy>> VisitStack;
 
   void traverseChild() {
     while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
-      NodeType *BB = *VisitStack.back().second++;
-      if (this->insertEdge(VisitStack.back().first, BB)) {
+      NodeRef BB = *VisitStack.back().second++;
+      if (this->insertEdge(Optional<NodeRef>(VisitStack.back().first), BB)) {
         // If the block is not visited...
         VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
       }
     }
   }
 
-  po_iterator(NodeType *BB) {
-    this->insertEdge((NodeType*)nullptr, BB);
+  po_iterator(NodeRef BB) {
+    this->insertEdge(Optional<NodeRef>(), BB);
     VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     traverseChild();
   }
   po_iterator() {} // End is when stack is empty.
 
-  po_iterator(NodeType *BB, SetType &S)
+  po_iterator(NodeRef BB, SetType &S)
       : po_iterator_storage<SetType, ExtStorage>(S) {
-    if (this->insertEdge((NodeType*)nullptr, BB)) {
+    if (this->insertEdge(Optional<NodeRef>(), BB)) {
       VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
       traverseChild();
     }
   }
 
   po_iterator(SetType &S)
       : po_iterator_storage<SetType, ExtStorage>(S) {
   } // End is when stack is empty.
public:
   }
   static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); }
 
   bool operator==(const po_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   bool operator!=(const po_iterator &x) const { return !(*this == x); }
 
-  pointer operator*() const { return VisitStack.back().first; }
+  const NodeRef &operator*() const { return VisitStack.back().first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the BasicBlock, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
-  NodeType *operator->() const { return **this; }
+  NodeRef operator->() const { return **this; }
 
   po_iterator &operator++() { // Preincrement
     this->finishPostorder(VisitStack.back().first);
     VisitStack.pop_back();
     if (!VisitStack.empty())
       traverseChild();
     return *this;
   }

 template <class T>
 po_iterator<T> po_end  (const T &G) { return po_iterator<T>::end(G); }
 
 template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
   return make_range(po_begin(G), po_end(G));
 }
 
 // Provide global definitions of external postorder iterators...
-template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> >
+template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
 struct po_ext_iterator : public po_iterator<T, SetType, true> {
   po_ext_iterator(const po_iterator<T, SetType, true> &V) :
   po_iterator<T, SetType, true>(V) {}
 };
 
 template<class T, class SetType>
 po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
   return po_ext_iterator<T, SetType>::begin(G, S);
 }
 
 template<class T, class SetType>
 po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
   return po_ext_iterator<T, SetType>::end(G, S);
 }
 
 template <class T, class SetType>
 iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) {
   return make_range(po_ext_begin(G, S), po_ext_end(G, S));
 }
 
 // Provide global definitions of inverse post order iterators...
-template <class T,
-          class SetType = std::set<typename GraphTraits<T>::NodeType*>,
+template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>,
           bool External = false>
-struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > {
+struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External> {
   ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
      po_iterator<Inverse<T>, SetType, External> (V) {}
 };
 
 template <class T>
 ipo_iterator<T> ipo_begin(const T &G) {
   return ipo_iterator<T>::begin(G);
 }
 
 template <class T>
 ipo_iterator<T> ipo_end(const T &G){
   return ipo_iterator<T>::end(G);
 }
 
 template <class T>
 iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) {
   return make_range(ipo_begin(G), ipo_end(G));
 }
 
 // Provide global definitions of external inverse postorder iterators...
-template <class T,
-          class SetType = std::set<typename GraphTraits<T>::NodeType*> >
+template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
 struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
   ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
     ipo_iterator<T, SetType, true>(V) {}
   ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
     ipo_iterator<T, SetType, true>(V) {}
 };
 
 template <class T, class SetType>

 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
 //      ...
 //   }
 // }
 //
 
 template<class GraphT, class GT = GraphTraits<GraphT> >
 class ReversePostOrderTraversal {
-  typedef typename GT::NodeType NodeType;
-  std::vector<NodeType*> Blocks;       // Block list in normal PO order
-  void Initialize(NodeType *BB) {
+  typedef typename GT::NodeRef NodeRef;
+  std::vector<NodeRef> Blocks; // Block list in normal PO order
+  void Initialize(NodeRef BB) {
     std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
   }
 public:
-  typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator;
+  typedef typename std::vector<NodeRef>::reverse_iterator rpo_iterator;
 
   ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); }
 
   // Because we want a reverse post order, use reverse iterators from the vector
   rpo_iterator begin() { return Blocks.rbegin(); }
   rpo_iterator end() { return Blocks.rend(); }
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/Analysis/LoopIterator.h

 };
 
 /// Specialize po_iterator_storage to record postorder numbers.
 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
   LoopBlocksTraversal &LBT;
 public:
   po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
   // These functions are defined below.
-  bool insertEdge(BasicBlock *From, BasicBlock *To);
+  bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
   void finishPostorder(BasicBlock *BB);
 };
 
 /// Traverse the blocks in a loop using a depth-first search.
 class LoopBlocksTraversal {
 public:
   /// Graph traversal iterator.
   typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
public:
   /// postorder.
   void finishPostorder(BasicBlock *BB) {
     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
     DFS.PostBlocks.push_back(BB);
     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
   }
 };
 
-inline bool po_iterator_storage<LoopBlocksTraversal, true>::
-insertEdge(BasicBlock *From, BasicBlock *To) {
+inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
+    Optional<BasicBlock *> From, BasicBlock *To) {
   return LBT.visitPreorder(To);
 }
 
 inline void po_iterator_storage<LoopBlocksTraversal, true>::
 finishPostorder(BasicBlock *BB) {
   LBT.finishPostorder(BB);
 }
 
 } // End namespace llvm
 
 #endif

llvm/trunk/include/llvm/IR/Type.h

 };
 
 //===----------------------------------------------------------------------===//
 // Provide specializations of GraphTraits to be able to treat a type as a
 // graph of sub types.
 
 template <> struct GraphTraits<Type *> {
   typedef Type NodeType;
+  typedef Type *NodeRef;
   typedef Type::subtype_iterator ChildIteratorType;
 
   static inline NodeType *getEntryNode(Type *T) { return T; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->subtype_begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->subtype_end();
   }
 };
 
 template <> struct GraphTraits<const Type*> {
   typedef const Type NodeType;
+  typedef const Type *NodeRef;
   typedef Type::subtype_iterator ChildIteratorType;
 
   static inline NodeType *getEntryNode(NodeType *T) { return T; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->subtype_begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->subtype_end();

llvm/trunk/lib/CodeGen/MachineTraceMetrics.cpp

 namespace llvm {
 template<>
 class po_iterator_storage<LoopBounds, true> {
   LoopBounds &LB;
 public:
   po_iterator_storage(LoopBounds &lb) : LB(lb) {}
   void finishPostorder(const MachineBasicBlock*) {}
 
-  bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) {
+  bool insertEdge(Optional<const MachineBasicBlock *> From,
+                  const MachineBasicBlock *To) {
     // Skip already visited To blocks.
     MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()];
     if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
       return false;
     // From is null once when To is the trace center block.
     if (From) {
-      if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(From)) {
+      if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(*From)) {
         // Don't follow backedges, don't leave FromLoop when going upwards.
-        if ((LB.Downward ? To : From) == FromLoop->getHeader())
+        if ((LB.Downward ? To : *From) == FromLoop->getHeader())
           return false;
         // Don't leave FromLoop.
         if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))
           return false;
       }
     }
     // To is a new block. Mark the block as visited in case the CFG has cycles
     // that MachineLoopInfo didn't recognize as a natural loop.

llvm/trunk/unittests/ADT/PostOrderIteratorTest.cpp

 
 // Whether we're able to compile
 TEST(PostOrderIteratorTest, Compiles) {
   typedef SmallPtrSet<void *, 4> ExtSetTy;
 
   // Tests that template specializations are kept up to date
   void *Null = nullptr;
   po_iterator_storage<std::set<void *>, false> PIS;
-  PIS.insertEdge(Null, Null);
+  PIS.insertEdge(Optional<void *>(), Null);
   ExtSetTy Ext;
   po_iterator_storage<ExtSetTy, true> PISExt(Ext);
-  PIS.insertEdge(Null, Null);
+  PIS.insertEdge(Optional<void *>(), Null);
 
   // Test above, but going through po_iterator (which inherits from template
   // base)
   BasicBlock *NullBB = nullptr;
   auto PI = po_end(NullBB);
-  PI.insertEdge(NullBB, NullBB);
+  PI.insertEdge(Optional<BasicBlock *>(), NullBB);
   auto PIExt = po_ext_end(NullBB, Ext);
-  PIExt.insertEdge(NullBB, NullBB);
+  PIExt.insertEdge(Optional<BasicBlock *>(), NullBB);
 }
 }