[GraphTraits] Make nodes_iterator dereference to NodeType*

[timshen]

Summary

Currently nodes_iterator may dereference to a NodeType* or a NodeType&. Make them all dereference to NodeType*, which is NodeRef later.

[dblaikie]

include/llvm/Analysis/CallGraph.h

463–500

Same sort of feedback I gave on the equivalent code in Clang (why does the code in Clang look /so/ much the same & could we make some of it common?): A follow up commit to drop the "DerefFun" noise now that we can use decltype, etc.

[timshen]

Landed as r279326.

[• dberlin]

lib/Transforms/Scalar/NaryReassociate.cpp

212

This is actually not preorder :)
It's depth first.

and could be replaced with the depth first iterator

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

1155

Ditto, this is just depth_first, and should use that.

lib/Transforms/Scalar/StraightLineStrengthReduce.cpp

680

This whole glop is just a fancy way of saying:

for (const auto *Node : depth_first(DT)) { allocateCandidatesAndFindBasis(I->getBlock()); }

I'll fix it if you don't :)

include/llvm/ADT/GraphTraits.h

struct GraphTraits {
 
   // NOTICE: We are in a transition from migration interfaces that require
   // NodeType *, to NodeRef. NodeRef is required to be cheap to copy, but does
   // not have to be a raw pointer. In the transition, user should define
   // NodeType, and NodeRef = NodeType *.
   //
   // typedef NodeType          - Type of Node in the graph
   // typedef NodeRef           - NodeType *
-  // typedef ChildIteratorType - Type used to iterate over children in graph
+  // typedef ChildIteratorType - Type used to iterate over children in graph,
+  //                             dereference to a NodeRef
 
   // static NodeRef getEntryNode(const GraphType &)
   //    Return the entry node of the graph
 
   // static ChildIteratorType child_begin(NodeRef)
   // static ChildIteratorType child_end  (NodeRef)
   //    Return iterators that point to the beginning and ending of the child
   //    node list for the specified node.
   //
 
-  // typedef  ...iterator nodes_iterator;
+  // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
   // static nodes_iterator nodes_begin(GraphType *G)
   // static nodes_iterator nodes_end  (GraphType *G)
   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 
   // static unsigned       size       (GraphType *G)
   //    Return total number of nodes in the graph
   //
 

include/llvm/Analysis/BlockFrequencyInfoImpl.h

std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph,
     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) {
-        NodeRef N = &*I;
+        NodeRef N = *I;
         MaxFrequency =
             std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency());
       }
     }
     BlockFrequency Freq = Graph->getBlockFreq(Node);
     BlockFrequency HotFreq =
         (BlockFrequency(MaxFrequency) *
          BranchProbability::getBranchProbability(HotPercentThreshold, 100));

include/llvm/Analysis/CallGraph.h

 
 template <>
 struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> {
   static NodeType *getEntryNode(CallGraph *CGN) {
     return CGN->getExternalCallingNode(); // Start at the external node!
   }
   typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
       PairTy;
-  typedef std::pointer_to_unary_function<const PairTy &, CallGraphNode &>
+  typedef std::pointer_to_unary_function<const PairTy &, CallGraphNode *>
       DerefFun;
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator;
   static nodes_iterator nodes_begin(CallGraph *CG) {
     return map_iterator(CG->begin(), DerefFun(CGdereference));
   }
   static nodes_iterator nodes_end(CallGraph *CG) {
     return map_iterator(CG->end(), DerefFun(CGdereference));
   }
 
-  static CallGraphNode &CGdereference(const PairTy &P) { return *P.second; }
+  static CallGraphNode *CGdereference(const PairTy &P) { return P.second.get(); }
 };
 
 template <>
 struct GraphTraits<const CallGraph *> : public GraphTraits<
                                             const CallGraphNode *> {
   static NodeType *getEntryNode(const CallGraph *CGN) {
     return CGN->getExternalCallingNode(); // Start at the external node!
   }
   typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
       PairTy;
-  typedef std::pointer_to_unary_function<const PairTy &, const CallGraphNode &>
+  typedef std::pointer_to_unary_function<const PairTy &, const CallGraphNode *>
       DerefFun;
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef mapped_iterator<CallGraph::const_iterator, DerefFun> nodes_iterator;
   static nodes_iterator nodes_begin(const CallGraph *CG) {
     return map_iterator(CG->begin(), DerefFun(CGdereference));
   }
   static nodes_iterator nodes_end(const CallGraph *CG) {
     return map_iterator(CG->end(), DerefFun(CGdereference));
   }
 
-  static const CallGraphNode &CGdereference(const PairTy &P) {
-    return *P.second;
+  static const CallGraphNode *CGdereference(const PairTy &P) {
+    return P.second.get();
   }
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/CodeGen/MachineFunction.h

 //
 template <> struct GraphTraits<MachineFunction*> :
   public GraphTraits<MachineBasicBlock*> {
   static NodeType *getEntryNode(MachineFunction *F) {
     return &F->front();
   }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef MachineFunction::iterator nodes_iterator;
-  static nodes_iterator nodes_begin(MachineFunction *F) { return F->begin(); }
-  static nodes_iterator nodes_end  (MachineFunction *F) { return F->end(); }
+  typedef pointer_iterator<MachineFunction::iterator> nodes_iterator;
+  static nodes_iterator nodes_begin(MachineFunction *F) {
+    return nodes_iterator(F->begin());
+  }
+  static nodes_iterator nodes_end(MachineFunction *F) {
+    return nodes_iterator(F->end());
+  }
   static unsigned       size       (MachineFunction *F) { return F->size(); }
 };
 template <> struct GraphTraits<const MachineFunction*> :
   public GraphTraits<const MachineBasicBlock*> {
   static NodeType *getEntryNode(const MachineFunction *F) {
     return &F->front();
   }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef MachineFunction::const_iterator nodes_iterator;
+  typedef pointer_iterator<MachineFunction::const_iterator> nodes_iterator;
   static nodes_iterator nodes_begin(const MachineFunction *F) {
-    return F->begin();
+    return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end  (const MachineFunction *F) {
-    return F->end();
+    return nodes_iterator(F->end());
   }
   static unsigned       size       (const MachineFunction *F)  {
     return F->size();
   }
 };
 
 
 // Provide specializations of GraphTraits to be able to treat a function as a

include/llvm/CodeGen/ScheduleDAG.h

static inline ChildIteratorType child_begin(NodeType *N) {
       return SUnitIterator::begin(N);
     }
     static inline ChildIteratorType child_end(NodeType *N) {
       return SUnitIterator::end(N);
     }
   };
 
   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
-    typedef std::vector<SUnit>::iterator nodes_iterator;
+    typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
     static nodes_iterator nodes_begin(ScheduleDAG *G) {
-      return G->SUnits.begin();
+      return nodes_iterator(G->SUnits.begin());
     }
     static nodes_iterator nodes_end(ScheduleDAG *G) {
-      return G->SUnits.end();
+      return nodes_iterator(G->SUnits.end());
     }
   };
 
   /// ScheduleDAGTopologicalSort is a class that computes a topological
   /// ordering for SUnits and provides methods for dynamically updating
   /// the ordering as new edges are added.
   ///
   /// This allows a very fast implementation of IsReachable, for example.

include/llvm/CodeGen/SelectionDAG.h

private:
   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
   StringMap<SDNode*> ExternalSymbols;
 
   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
   DenseMap<MCSymbol *, SDNode *> MCSymbols;
 };
 
 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
-  typedef SelectionDAG::allnodes_iterator nodes_iterator;
+  typedef pointer_iterator<SelectionDAG::allnodes_iterator> nodes_iterator;
   static nodes_iterator nodes_begin(SelectionDAG *G) {
-    return G->allnodes_begin();
+    return nodes_iterator(G->allnodes_begin());
   }
   static nodes_iterator nodes_end(SelectionDAG *G) {
-    return G->allnodes_end();
+    return nodes_iterator(G->allnodes_end());
   }
 };
 
 }  // end namespace llvm
 
 #endif

include/llvm/IR/CFG.h

 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks... these are the same as the basic block iterators,
 // except that the root node is implicitly the first node of the function.
 //
 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
   static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef Function::iterator nodes_iterator;
-  static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
-  static nodes_iterator nodes_end  (Function *F) { return F->end(); }
+  typedef pointer_iterator<Function::iterator> nodes_iterator;
+  static nodes_iterator nodes_begin(Function *F) {
+    return nodes_iterator(F->begin());
+  }
+  static nodes_iterator nodes_end(Function *F) {
+    return nodes_iterator(F->end());
+  }
   static size_t         size       (Function *F) { return F->size(); }
 };
 template <> struct GraphTraits<const Function*> :
   public GraphTraits<const BasicBlock*> {
   static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef Function::const_iterator nodes_iterator;
-  static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
-  static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
+  typedef pointer_iterator<Function::const_iterator> nodes_iterator;
+  static nodes_iterator nodes_begin(const Function *F) {
+    return nodes_iterator(F->begin());
+  }
+  static nodes_iterator nodes_end(const Function *F) {
+    return nodes_iterator(F->end());
+  }
   static size_t         size       (const Function *F) { return F->size(); }
 };
 
 
 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 // a function is considered to be when traversing the predecessor edges of a BB
 // instead of the successor edges.

include/llvm/Support/GenericDomTree.h

if (!this->IsPostDominators) {
       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);
+        if (TraitsTy::child_begin(*I) == TraitsTy::child_end(*I))
+          addRoot(*I);
 
       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.

include/llvm/Support/GraphWriter.h

void writeFooter() {
     // Finish off the graph
     O << "}\n";
   }
 
   void writeNodes() {
     // Loop over the graph, printing it out...
     for (node_iterator I = GTraits::nodes_begin(G), E = GTraits::nodes_end(G);
          I != E; ++I)
-      if (!isNodeHidden(&*I))
-        writeNode(&*I);
-  }
-
-  bool isNodeHidden(NodeRef const *Node) {
-    return isNodeHidden(*Node);
+      if (!isNodeHidden(*I))
+        writeNode(*I);
   }
 
   bool isNodeHidden(NodeRef Node) {
     return DTraits.isNodeHidden(Node);
   }
 
-  void writeNode(NodeRef const *Node) {
-    writeNode(*Node);
-  }
-
   void writeNode(NodeRef Node) {
     std::string NodeAttributes = DTraits.getNodeAttributes(Node, G);
 
     O << "\tNode" << static_cast<const void*>(Node) << " [shape=record,";
     if (!NodeAttributes.empty()) O << NodeAttributes << ",";
     O << "label=\"{";
 
     if (!DTraits.renderGraphFromBottomUp()) {

lib/Analysis/BlockFrequencyInfo.cpp

 
 namespace llvm {
 
 template <>
 struct GraphTraits<BlockFrequencyInfo *> {
   typedef const BasicBlock NodeType;
   typedef const BasicBlock *NodeRef;
   typedef succ_const_iterator ChildIteratorType;
-  typedef Function::const_iterator nodes_iterator;
+  typedef pointer_iterator<Function::const_iterator> nodes_iterator;
 
   static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
     return &G->getFunction()->front();
   }
   static ChildIteratorType child_begin(const NodeType *N) {
     return succ_begin(N);
   }
   static ChildIteratorType child_end(const NodeType *N) {
     return succ_end(N);
   }
   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
-    return G->getFunction()->begin();
+    return nodes_iterator(G->getFunction()->begin());
   }
   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
-    return G->getFunction()->end();
+    return nodes_iterator(G->getFunction()->end());
   }
 };
 
 typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
     BFIDOTGTraitsBase;
 
 template <>
 struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {

lib/CodeGen/MachineBlockFrequencyInfo.cpp

 extern cl::opt<unsigned> ViewHotFreqPercent;
 
 namespace llvm {
 
 template <> struct GraphTraits<MachineBlockFrequencyInfo *> {
   typedef const MachineBasicBlock NodeType;
   typedef const MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
-  typedef MachineFunction::const_iterator nodes_iterator;
+  typedef pointer_iterator<MachineFunction::const_iterator> nodes_iterator;
 
   static inline const NodeType *
   getEntryNode(const MachineBlockFrequencyInfo *G) {
     return &G->getFunction()->front();
   }
 
   static ChildIteratorType child_begin(const NodeType *N) {
     return N->succ_begin();
   }
 
   static ChildIteratorType child_end(const NodeType *N) {
     return N->succ_end();
   }
 
   static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) {
-    return G->getFunction()->begin();
+    return nodes_iterator(G->getFunction()->begin());
   }
 
   static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) {
-    return G->getFunction()->end();
+    return nodes_iterator(G->getFunction()->end());
   }
 };
 
 typedef BFIDOTGraphTraitsBase<MachineBlockFrequencyInfo,
                               MachineBranchProbabilityInfo>
     MBFIDOTGraphTraitsBase;
 template <>
 struct DOTGraphTraits<MachineBlockFrequencyInfo *>

lib/Target/AMDGPU/AMDILCFGStructurizer.cpp

while (It != E) {
         ContNextScc = false;
       }
 
       if (ContNextScc)
         SccBeginMBB = nullptr;
     } //while, "one iteration" over the function.
 
     MachineBasicBlock *EntryMBB =
-        &*GraphTraits<MachineFunction *>::nodes_begin(FuncRep);
+        *GraphTraits<MachineFunction *>::nodes_begin(FuncRep);
     if (EntryMBB->succ_size() == 0) {
       Finish = true;
       DEBUG(
         dbgs() << "Reduce to one block\n";
       );
     } else {
       int NewnumRemainedBlk
         = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());
       // consider cloned blocks ??
       if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {
         MakeProgress = true;
         NumRemainedBlk = NewnumRemainedBlk;
       } else {
         MakeProgress = false;
         DEBUG(
           dbgs() << "No progress\n";
         );
       }
     }
   } while (!Finish && MakeProgress);
 
   // Misc wrap up to maintain the consistency of the Function representation.
-  wrapup(&*GraphTraits<MachineFunction *>::nodes_begin(FuncRep));
+  wrapup(*GraphTraits<MachineFunction *>::nodes_begin(FuncRep));
 
   // Detach retired Block, release memory.
   for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end();
       It != E; ++It) {
     if ((*It).second && (*It).second->IsRetired) {
       assert(((*It).first)->getNumber() != -1);
       DEBUG(
         dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";
for (std::vector<MachineBasicBlock *>::const_iterator
       MBB = *blockIter;
       OrderedBlks.push_back(MBB);
       recordSccnum(MBB, SccNum);
     }
   }
 
   //walk through all the block in func to check for unreachable
   typedef GraphTraits<MachineFunction *> GTM;
-  MachineFunction::iterator It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF);
+  auto It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF);
   for (; It != E; ++It) {
-    MachineBasicBlock *MBB = &(*It);
+    MachineBasicBlock *MBB = *It;
     SccNum = getSCCNum(MBB);
     if (SccNum == INVALIDSCCNUM)
       dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";
   }
 }
 
 int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
   int NumMatch = 0;

lib/Transforms/Scalar/NaryReassociate.cpp

static bool isPotentiallyNaryReassociable(Instruction *I) {
   }
 }
 
 bool NaryReassociatePass::doOneIteration(Function &F) {
   bool Changed = false;
   SeenExprs.clear();
   // Process the basic blocks in pre-order of the dominator tree. This order
   // ensures that all bases of a candidate are in Candidates when we process it.
   for (auto Node = GraphTraits<DominatorTree *>::nodes_begin(DT);
        Node != GraphTraits<DominatorTree *>::nodes_end(DT); ++Node) {
-    BasicBlock *BB = Node->getBlock();
+    BasicBlock *BB = (*Node)->getBlock();
     for (auto I = BB->begin(); I != BB->end(); ++I) {
       if (SE->isSCEVable(I->getType()) && isPotentiallyNaryReassociable(&*I)) {
         const SCEV *OldSCEV = SE->getSCEV(&*I);
         if (Instruction *NewI = tryReassociate(&*I)) {
           Changed = true;
           SE->forgetValue(&*I);
           I->replaceAllUsesWith(NewI);
           // If SeenExprs constains I's WeakVH, that entry will be replaced with

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

bool SeparateConstOffsetFromGEP::reuniteExts(Instruction *I) {
   return false;
 }
 
 bool SeparateConstOffsetFromGEP::reuniteExts(Function &F) {
   bool Changed = false;
   DominatingExprs.clear();
   for (auto Node = GraphTraits<DominatorTree *>::nodes_begin(DT);
        Node != GraphTraits<DominatorTree *>::nodes_end(DT); ++Node) {
-    BasicBlock *BB = Node->getBlock();
+    BasicBlock *BB = (*Node)->getBlock();
     for (auto I = BB->begin(); I != BB->end(); ) {
       Instruction *Cur = &*I++;
       Changed |= reuniteExts(Cur);
     }
   }
   return Changed;
 }
 

lib/Transforms/Scalar/StraightLineStrengthReduce.cpp

bool StraightLineStrengthReduce::runOnFunction(Function &F) {
 
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   // Traverse the dominator tree in the depth-first order. This order makes sure
   // all bases of a candidate are in Candidates when we process it.
   for (auto node = GraphTraits<DominatorTree *>::nodes_begin(DT);
        node != GraphTraits<DominatorTree *>::nodes_end(DT); ++node) {
-    for (auto &I : *node->getBlock())
+    for (auto &I : *(*node)->getBlock())
       allocateCandidatesAndFindBasis(&I);
   }
 
   // Rewrite candidates in the reverse depth-first order. This order makes sure
   // a candidate being rewritten is not a basis for any other candidate.
   while (!Candidates.empty()) {
     const Candidate &C = Candidates.back();
     if (C.Basis != nullptr) {
       rewriteCandidateWithBasis(C, *C.Basis);

unittests/Analysis/CallGraphTest.cpp

 template <typename Ty> void canSpecializeGraphTraitsIterators(Ty *G) {
   typedef typename GraphTraits<Ty *>::NodeType NodeTy;
 
   auto I = GraphTraits<Ty *>::nodes_begin(G);
   auto E = GraphTraits<Ty *>::nodes_end(G);
   auto X = ++I;
 
   // Should be able to iterate over all nodes of the graph.
-  static_assert(std::is_same<decltype(*I), NodeTy &>::value,
+  static_assert(std::is_same<decltype(*I), NodeTy *>::value,
                 "Node type does not match");
-  static_assert(std::is_same<decltype(*X), NodeTy &>::value,
+  static_assert(std::is_same<decltype(*X), NodeTy *>::value,
                 "Node type does not match");
-  static_assert(std::is_same<decltype(*E), NodeTy &>::value,
+  static_assert(std::is_same<decltype(*E), NodeTy *>::value,
                 "Node type does not match");
 
   NodeTy *N = GraphTraits<Ty *>::getEntryNode(G);
 
   auto S = GraphTraits<NodeTy *>::child_begin(N);
   auto F = GraphTraits<NodeTy *>::child_end(N);
 
   // Should be able to iterate over immediate successors of a node.