Rename LoopInfo::Analyze() to LoopInfo::analyze() and turn its parameter type to const&.

[congh]

Summary

The benefit of turning the parameter of LoopInfo::analyze() to const& is that it now can accept a rvalue.

[hfinkel]

include/llvm/CodeGen/MachineDominators.h

267

The fact that this requires copy-and-paste from above is somewhat sad, could we do better (have them both inherit from a templated base class perhaps)?

include/llvm/IR/Dominators.h

151

Same comment here.

[congh]

include/llvm/CodeGen/MachineDominators.h

267

Thanks you for your suggestion! I tried creating a base class and it works well. However, we have many places with two template struct defined for T and const T in copy-and-paste style. Do you think if it is a good idea to do this for all of them?

[congh]

Use class inheritance to avoid code duplication when specializing GraphTraits for T and const T.

[congh]

Bug fix.

[hfinkel]

LGTM.

include/llvm/Analysis/LoopInfo.h

public:
   static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
                                       const LoopT *ParentLoop) {
     if (!SubLoop) return true;
     if (SubLoop == ParentLoop) return false;
     return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
   }
 
   /// Create the loop forest using a stable algorithm.
-  void Analyze(DominatorTreeBase<BlockT> &DomTree);
+  void analyze(const DominatorTreeBase<BlockT> &DomTree);
 
   // Debugging
   void print(raw_ostream &OS) const;
 
   void verify() const;
 };
 
 // Implementation in LoopInfoImpl.h

include/llvm/Analysis/LoopInfoImpl.h

 ///
 
 /// Discover a subloop with the specified backedges such that: All blocks within
 /// this loop are mapped to this loop or a subloop. And all subloops within this
 /// loop have their parent loop set to this loop or a subloop.
 template<class BlockT, class LoopT>
 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges,
                                   LoopInfoBase<BlockT, LoopT> *LI,
-                                  DominatorTreeBase<BlockT> &DomTree) {
+                                  const DominatorTreeBase<BlockT> &DomTree) {
   typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
 
   unsigned NumBlocks = 0;
   unsigned NumSubloops = 0;
 
   // Perform a backward CFG traversal using a worklist.
   std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
   while (!ReverseCFGWorklist.empty()) {

 /// 1) Discovered and mapped by a reverse CFG traversal.
 /// 2) Visited during a forward DFS CFG traversal.
 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
 ///
 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
 /// insertions per block.
 template<class BlockT, class LoopT>
 void LoopInfoBase<BlockT, LoopT>::
-Analyze(DominatorTreeBase<BlockT> &DomTree) {
+analyze(const DominatorTreeBase<BlockT> &DomTree) {
 
   // Postorder traversal of the dominator tree.
-  DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode();
+  const DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode();
   for (auto DomNode : post_order(DomRoot)) {
 
     BlockT *Header = DomNode->getBlock();
     SmallVector<BlockT *, 4> Backedges;
 
     // Check each predecessor of the potential loop header.
     typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
     for (typename InvBlockTraits::ChildIteratorType PI =

include/llvm/CodeGen/MachineDominators.h

template <> struct GraphTraits<MachineDomTreeNode *> {
   static inline ChildIteratorType child_begin(NodeType* N) {
     return N->begin();
   }
   static inline ChildIteratorType child_end(NodeType* N) {
     return N->end();
   }
 };
 
+template <> struct GraphTraits<const MachineDomTreeNode *> {
+  typedef const MachineDomTreeNode NodeType;
+  typedef NodeType::const_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(NodeType *N) {
+    return N;
+  }
+  static inline ChildIteratorType child_begin(NodeType* N) {
+    return N->begin();
+  }
+  static inline ChildIteratorType child_end(NodeType* N) {
+    return N->end();
+  }
+};
+
 template <> struct GraphTraits<MachineDominatorTree*>
   : public GraphTraits<MachineDomTreeNode *> {
   static NodeType *getEntryNode(MachineDominatorTree *DT) {
     return DT->getRootNode();
   }
 };
 
 }
 
 #endif

include/llvm/IR/Dominators.h

static nodes_iterator nodes_begin(DomTreeNode *N) {
     return df_begin(getEntryNode(N));
   }
 
   static nodes_iterator nodes_end(DomTreeNode *N) {
     return df_end(getEntryNode(N));
   }
 };
 
+template <> struct GraphTraits<const DomTreeNode *> {
+  typedef const DomTreeNode NodeType;
+  typedef NodeType::const_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(NodeType *N) {
+    return N;
+  }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->end();
+  }
+
+  typedef df_iterator<const DomTreeNode *> nodes_iterator;
+
+  static nodes_iterator nodes_begin(const DomTreeNode *N) {
+    return df_begin(getEntryNode(N));
+  }
+
+  static nodes_iterator nodes_end(const DomTreeNode *N) {
+    return df_end(getEntryNode(N));
+  }
+};
+
 template <> struct GraphTraits<DominatorTree*>
   : public GraphTraits<DomTreeNode*> {
   static NodeType *getEntryNode(DominatorTree *DT) {
     return DT->getRootNode();
   }
 
   static nodes_iterator nodes_begin(DominatorTree *N) {
     return df_begin(getEntryNode(N));

lib/Analysis/LoopInfo.cpp

 LoopInfo LoopAnalysis::run(Function &F, AnalysisManager<Function> *AM) {
   // FIXME: Currently we create a LoopInfo from scratch for every function.
   // This may prove to be too wasteful due to deallocating and re-allocating
   // memory each time for the underlying map and vector datastructures. At some
   // point it may prove worthwhile to use a freelist and recycle LoopInfo
   // objects. I don't want to add that kind of complexity until the scope of
   // the problem is better understood.
   LoopInfo LI;
-  LI.Analyze(AM->getResult<DominatorTreeAnalysis>(F));
+  LI.analyze(AM->getResult<DominatorTreeAnalysis>(F));
   return LI;
 }
 
 PreservedAnalyses LoopPrinterPass::run(Function &F,
                                        AnalysisManager<Function> *AM) {
   AM->getResult<LoopAnalysis>(F).print(OS);
   return PreservedAnalyses::all();
 }
 
 //===----------------------------------------------------------------------===//
 // LoopInfo implementation
 //
 
 char LoopInfoWrapperPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
                       true, true)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
                     true, true)
 
 bool LoopInfoWrapperPass::runOnFunction(Function &) {
   releaseMemory();
-  LI.Analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
+  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
   return false;
 }
 
 void LoopInfoWrapperPass::verifyAnalysis() const {
   // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
   // function each time verifyAnalysis is called is very expensive. The
   // -verify-loop-info option can enable this. In order to perform some
   // checking by default, LoopPass has been taught to call verifyLoop manually

lib/CodeGen/MachineLoopInfo.cpp

 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
                 "Machine Natural Loop Construction", true, true)
 
 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
 
 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
   releaseMemory();
-  LI.Analyze(getAnalysis<MachineDominatorTree>().getBase());
+  LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
   return false;
 }
 
 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<MachineDominatorTree>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }