GraphTraits: Add range versions of graph traits functions (graph_nodes, graph_children, inverse_graph_nodes, inverse_graph_children).

[• dberlin]

Summary

Convert all obvious node_begin/node_end and child_begin/child_end
pairs to range based for.

Sending for review in case someone has a good idea how to make
graph_children able to be inferred. It looks like it would require
changing GraphTraits to be two argument or something. I presume
inference does not happen because it would have to check every
GraphTraits in the world to see if the noderef types matched.

Note: This change was 3-staged with clang as well, which uses
Dominators/etc from LLVM.

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

203 ↗

(On Diff #87813)

Note that this use of const auto & is required to make clang build, as the iterator type it for CFG blocks ends up returning blocks directly otherwise here.

I'm not sure this is a legal definition of graphtraits, and the definition of CFG inverse graph traits is also definitely broken:

 template <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > {
   typedef ::clang::CFGBlock *NodeRef;
-  typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
+  typedef ::clang::CFGBlock::pred_iterator ChildIteratorType;

(the constant iterator is being used for the non-constant version of inverse graphtraits, which looks like a paste error)

I don't usually work in clang world, so i added someone who does :)

[dblaikie]

Looks good - sounds like you answered your own main question: no way to find the graph from the node type, so the children ops do need an explicit template param.

& I'd probably drop the "graph_" prefix - up to you though if you think that's better or worse, etc.

lib/Target/Hexagon/HexagonBitSimplify.cpp

264 ↗

(On Diff #87813)

I probably wouldn't bother with the extra parens there:

*DTN->getBlock()

rather than:

*(DTN->getBlock())

[• dberlin]

• Drop graph_ prefix

llvm/trunk/include/llvm/ADT/GraphTraits.h

 // This file also defines the marker class Inverse that is used to iterate over
 // graphs in a graph defined, inverse ordering...
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_GRAPHTRAITS_H
 #define LLVM_ADT_GRAPHTRAITS_H
 
+#include "llvm/ADT/iterator_range.h"
+
 namespace llvm {
 
 // GraphTraits - This class should be specialized by different graph types...
 // which is why the default version is empty.
 //
 template<class GraphType>
 struct GraphTraits {
   // Elements to provide:
struct Inverse {
 
   inline Inverse(const GraphType &G) : Graph(G) {}
 };
 
 // Provide a partial specialization of GraphTraits so that the inverse of an
 // inverse falls back to the original graph.
 template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
 
+// Provide iterator ranges for the graph traits nodes and children
+template <class GraphType>
+iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
+graph_nodes(const GraphType &G) {
+  return make_range(GraphTraits<GraphType>::nodes_begin(G),
+                    GraphTraits<GraphType>::nodes_end(G));
+}
+template <class GraphType>
+iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
+inverse_graph_nodes(const GraphType &G) {
+  return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
+                    GraphTraits<Inverse<GraphType>>::nodes_end(G));
+}
+
+template <class GraphType>
+iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
+graph_children(const typename GraphTraits<GraphType>::NodeRef &G) {
+  return make_range(GraphTraits<GraphType>::child_begin(G),
+                    GraphTraits<GraphType>::child_end(G));
+}
+
+template <class GraphType>
+iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
+inverse_graph_children(const typename GraphTraits<GraphType>::NodeRef &G) {
+  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
+                    GraphTraits<Inverse<GraphType>>::child_end(G));
+}
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/Support/GenericDomTree.h

template <class FT> void recalculate(FT &F) {
     if (!this->IsPostDominators) {
       // Initialize root
       NodeT *entry = TraitsTy::getEntryNode(&F);
       addRoot(entry);
 
       Calculate<FT, NodeT *>(*this, F);
     } else {
       // Initialize the roots list
-      for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
-                                             E = TraitsTy::nodes_end(&F);
-           I != E; ++I)
-        if (TraitsTy::child_begin(*I) == TraitsTy::child_end(*I))
-          addRoot(*I);
+      for (auto *Node : graph_nodes(&F))
+        if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
+          addRoot(Node);
 
       Calculate<FT, Inverse<NodeT *>>(*this, F);
     }
   }
 };
 
 // These two functions are declared out of line as a workaround for building
 // with old (< r147295) versions of clang because of pr11642.

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
       typename GraphT::NodeRef U = Eval<GraphT>(DT, V, i + 1);
       DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
     }
 
     // Step #3: Calculate the semidominators of all vertices
 
     // initialize the semi dominator to point to the parent node
     WInfo.Semi = WInfo.Parent;
-    typedef GraphTraits<Inverse<NodeT> > InvTraits;
-    for (typename InvTraits::ChildIteratorType CI =
-         InvTraits::child_begin(W),
-         E = InvTraits::child_end(W); CI != E; ++CI) {
-      typename InvTraits::NodeRef N = *CI;
-      if (DT.Info.count(N)) {  // Only if this predecessor is reachable!
+    for (const auto &N : inverse_graph_children<NodeT>(W))
+      if (DT.Info.count(N)) { // Only if this predecessor is reachable!
         unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
-    }
 
     // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is
     // necessarily parent(V). In this case, set idom(V) here and avoid placing
     // V into a bucket.
     if (WInfo.Semi == WInfo.Parent) {
       DT.IDoms[W] = DT.Vertex[WInfo.Parent];
     } else {
       Buckets[i] = Buckets[WInfo.Semi];

llvm/trunk/lib/Analysis/IteratedDominanceFrontier.cpp

while (!PQ.empty()) {
     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.
-      for (auto SuccIter = GraphTraits<NodeTy>::child_begin(BB),
-                End = GraphTraits<NodeTy>::child_end(BB);
-           SuccIter != End; ++SuccIter) {
-        BasicBlock *Succ = *SuccIter;
+      for (auto *Succ : graph_children<NodeTy>(BB)) {
         DomTreeNode *SuccNode = DT.getNode(Succ);
 
         // Quickly skip all CFG edges that are also dominator tree edges instead
         // of catching them below.
         if (SuccNode->getIDom() == Node)
           continue;
 
         unsigned SuccLevel = DomLevels.lookup(SuccNode);

llvm/trunk/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp

for (std::vector<MachineBasicBlock *>::const_iterator
          blockIter = SccNext.begin(), blockEnd = SccNext.end();
          blockIter != blockEnd; ++blockIter) {
       MBB = *blockIter;
       OrderedBlks.push_back(MBB);
       recordSccnum(MBB, SccNum);
     }
   }
 
-  //walk through all the block in func to check for unreachable
-  typedef GraphTraits<MachineFunction *> GTM;
-  auto It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF);
-  for (; It != E; ++It) {
-    MachineBasicBlock *MBB = *It;
+  // walk through all the block in func to check for unreachable
+  for (auto *MBB : graph_nodes(MF)) {
     SccNum = getSCCNum(MBB);
     if (SccNum == INVALIDSCCNUM)
       dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";
   }
 }
 
 int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
   int NumMatch = 0;
int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
   LoopRep->getExitBlocks(ExitBlks);
   SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet;
   for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
     ExitBlkSet.insert(ExitBlks[i]);
   assert(ExitBlkSet.size() == 1);
   MachineBasicBlock *ExitBlk = *ExitBlks.begin();
   assert(ExitBlk && "Loop has several exit block");
   MBBVector LatchBlks;
-  typedef GraphTraits<Inverse<MachineBasicBlock*>> InvMBBTraits;
-  InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader),
-      PE = InvMBBTraits::child_end(LoopHeader);
-  for (; PI != PE; PI++) {
-    if (LoopRep->contains(*PI))
-      LatchBlks.push_back(*PI);
-  }
+  for (auto *LB : inverse_graph_children<MachineBasicBlock*>(LoopHeader))
+    if (LoopRep->contains(LB))
+      LatchBlks.push_back(LB);
 
   for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
     mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
   for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
     settleLoopcontBlock(LatchBlks[i], LoopHeader);
   int Match = 0;
   do {
     Match = 0;

llvm/trunk/lib/Target/Hexagon/HexagonBitSimplify.cpp

 INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexbit",
       "Hexagon bit simplification", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_END(HexagonBitSimplify, "hexbit",
       "Hexagon bit simplification", false, false)
 
 bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T,
       RegisterSet &AVs) {
-  MachineDomTreeNode *N = MDT->getNode(&B);
-  typedef GraphTraits<MachineDomTreeNode*> GTN;
   bool Changed = false;
 
   if (T.TopDown)
     Changed = T.processBlock(B, AVs);
 
   RegisterSet Defs;
   for (auto &I : B)
     getInstrDefs(I, Defs);
   RegisterSet NewAVs = AVs;
   NewAVs.insert(Defs);
 
-  for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) {
-    MachineBasicBlock *SB = (*I)->getBlock();
-    Changed |= visitBlock(*SB, T, NewAVs);
-  }
+  for (auto *DTN : graph_children<MachineDomTreeNode*>(MDT->getNode(&B)))
+    Changed |= visitBlock(*(DTN->getBlock()), T, NewAVs);
+
   if (!T.TopDown)
     Changed |= T.processBlock(B, AVs);
 
   return Changed;
 }
 
 //
 // Utility functions:
for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) {
     }
     return false;
   }
   return true;
 }
 
 bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) {
   bool Changed = false;
-  typedef GraphTraits<MachineDomTreeNode*> GTN;
-  for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
-    Changed |= runOnNode(*I);
+
+  for (auto *DTN : graph_children<MachineDomTreeNode*>(N))
+    Changed |= runOnNode(DTN);
 
   MachineBasicBlock *B = N->getBlock();
   std::vector<MachineInstr*> Instrs;
   for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
     Instrs.push_back(&*I);
 
   for (auto MI : Instrs) {
     unsigned Opc = MI->getOpcode();

llvm/trunk/lib/Target/Hexagon/HexagonCommonGEP.cpp

 
 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
       ValueVect &Order) {
   // Compute block ordering for a typical DT-based traversal of the flow
   // graph: "before visiting a block, all of its dominators must have been
   // visited".
 
   Order.push_back(Root);
-  DomTreeNode *DTN = DT->getNode(Root);
-  typedef GraphTraits<DomTreeNode*> GTN;
-  typedef GTN::ChildIteratorType Iter;
-  for (Iter I = GTN::child_begin(DTN), E = GTN::child_end(DTN); I != E; ++I)
-    getBlockTraversalOrder((*I)->getBlock(), Order);
+  for (auto *DTN : graph_children<DomTreeNode*>(DT->getNode(Root)))
+    getBlockTraversalOrder(DTN->getBlock(), Order);
 }
 
 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
   // No vector GEPs.
   if (!GepI->getType()->isPointerTy())
     return false;
   // No GEPs without any indices.  (Is this possible?)
   if (GepI->idx_begin() == GepI->idx_end())

 }
 
 void HexagonCommonGEP::removeDeadCode() {
   ValueVect BO;
   BO.push_back(&Fn->front());
 
   for (unsigned i = 0; i < BO.size(); ++i) {
     BasicBlock *B = cast<BasicBlock>(BO[i]);
-    DomTreeNode *N = DT->getNode(B);
-    typedef GraphTraits<DomTreeNode*> GTN;
-    typedef GTN::ChildIteratorType Iter;
-    for (Iter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
-      BO.push_back((*I)->getBlock());
+    for (auto DTN : graph_children<DomTreeNode*>(DT->getNode(B)))
+      BO.push_back(DTN->getBlock());
   }
 
   for (unsigned i = BO.size(); i > 0; --i) {
     BasicBlock *B = cast<BasicBlock>(BO[i-1]);
     BasicBlock::InstListType &IL = B->getInstList();
     typedef BasicBlock::InstListType::reverse_iterator reverse_iterator;
     ValueVect Ins;
     for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I)

llvm/trunk/lib/Target/Hexagon/HexagonGenExtract.cpp

bool HexagonGenExtract::convert(Instruction *In) {
   if (SL != 0)
     NewIn = IRB.CreateShl(NewIn, SL, CSL->getName());
   In->replaceAllUsesWith(NewIn);
   return true;
 }
 
 bool HexagonGenExtract::visitBlock(BasicBlock *B) {
   // Depth-first, bottom-up traversal.
-  DomTreeNode *DTN = DT->getNode(B);
-  typedef GraphTraits<DomTreeNode*> GTN;
-  typedef GTN::ChildIteratorType Iter;
-  for (Iter I = GTN::child_begin(DTN), E = GTN::child_end(DTN); I != E; ++I)
-    visitBlock((*I)->getBlock());
+  for (auto *DTN : graph_children<DomTreeNode*>(DT->getNode(B)))
+    visitBlock(DTN->getBlock());
 
   // Allow limiting the number of generated extracts for debugging purposes.
   bool HasCutoff = ExtractCutoff.getPosition();
   unsigned Cutoff = ExtractCutoff;
 
   bool Changed = false;
   BasicBlock::iterator I = std::prev(B->end()), NextI, Begin = B->begin();
   while (true) {

llvm/trunk/lib/Target/Hexagon/HexagonGenInsert.cpp

for (MachineBasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
 
     // Insert the defined registers into the list of available registers
     // after they have been processed.
     for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR))
       AVs.insert(VR);
     BlockDefs.insert(InsDefs);
   }
 
-  MachineDomTreeNode *N = MDT->getNode(B);
-  typedef GraphTraits<MachineDomTreeNode*> GTN;
-  typedef GTN::ChildIteratorType ChildIter;
-  for (ChildIter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) {
-    MachineBasicBlock *SB = (*I)->getBlock();
+  for (auto *DTN : graph_children<MachineDomTreeNode*>(MDT->getNode(B))) {
+    MachineBasicBlock *SB = DTN->getBlock();
     collectInBlock(SB, AVs);
   }
 
   for (unsigned VR = BlockDefs.find_first(); VR; VR = BlockDefs.find_next(VR))
     AVs.remove(VR);
 }
 
 void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
     DefI->eraseFromParent();
   }
 
   return true;
 }
 
 bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
   bool Changed = false;
-  typedef GraphTraits<MachineDomTreeNode*> GTN;
-  for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
-    Changed |= removeDeadCode(*I);
+
+  for (auto *DTN : graph_children<MachineDomTreeNode*>(N))
+    Changed |= removeDeadCode(DTN);
 
   MachineBasicBlock *B = N->getBlock();
   std::vector<MachineInstr*> Instrs;
   for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
     Instrs.push_back(&*I);
 
   for (auto I = Instrs.begin(), E = Instrs.end(); I != E; ++I) {
     MachineInstr *MI = *I;