DomTree: Remove getRoots() accessor

[nhaehnle]

Summary

Avoid exposing details about how roots are stored. This enables subsequent
type-erasure changes.

Change-Id: I532b774cc71f2224e543bc7d79131d97f63f093d

[arsenm]

This is more consistent with other iteratables

llvm/unittests/IR/DominatorTreeTest.cpp

808

This should really be EXPECT_EQ(2, PDT.root_size())

llvm/include/llvm/Analysis/DominanceFrontier.h

private:
   using BlockTraits = GraphTraits<BlockT *>;
 
 public:
   using DomTreeT = DomTreeBase<BlockT>;
   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
   using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;
 
   void analyze(DomTreeT &DT) {
-    assert(DT.getRoots().size() == 1 &&
+    assert(DT.root_size() == 1 &&
            "Only one entry block for forward domfronts!");
     this->Roots = {DT.getRoot()};
     calculate(DT, DT[this->Roots[0]]);
   }
 
   const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
 };
 

llvm/include/llvm/CodeGen/MachineDominators.h

public:
   DomTreeT &getBase() {
     if (!DT) DT.reset(new DomTreeT());
     applySplitCriticalEdges();
     return *DT;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
-  /// getRoots -  Return the root blocks of the current CFG.  This may include
-  /// multiple blocks if we are computing post dominators.  For forward
-  /// dominators, this will always be a single block (the entry node).
-  ///
-  const SmallVectorImpl<MachineBasicBlock*> &getRoots() const {
-    applySplitCriticalEdges();
-    return DT->getRoots();
-  }
-
   MachineBasicBlock *getRoot() const {
     applySplitCriticalEdges();
     return DT->getRoot();
   }
 
   MachineDomTreeNode *getRootNode() const {
     applySplitCriticalEdges();
     return DT->getRootNode();

llvm/include/llvm/CodeGen/MachinePostDominators.h

public:
   PostDomTreeT &getBase() {
     if (!PDT)
       PDT.reset(new PostDomTreeT());
     return *PDT;
   }
 
   FunctionPass *createMachinePostDominatorTreePass();
 
-  const SmallVectorImpl<MachineBasicBlock *> &getRoots() const {
-    return PDT->getRoots();
-  }
-
   MachineDomTreeNode *getRootNode() const { return PDT->getRootNode(); }
 
   MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
     return PDT->getNode(BB);
   }
 
   MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
     return PDT->getNode(BB);

llvm/include/llvm/Support/GenericDomTree.h

DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
     SlowQueries = RHS.SlowQueries;
     RHS.wipe();
     return *this;
   }
 
   DominatorTreeBase(const DominatorTreeBase &) = delete;
   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
 
-  /// getRoots - Return the root blocks of the current CFG.  This may include
-  /// multiple blocks if we are computing post dominators.  For forward
-  /// dominators, this will always be a single block (the entry node).
+  /// Iteration over roots.
   ///
-  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
+  /// This may include multiple blocks if we are computing post dominators.
+  /// For forward dominators, this will always be a single block (the entry
+  /// block).
+  using root_iterator = typename SmallVectorImpl<NodeT *>::iterator;
+  using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator;
+
+  root_iterator root_begin() { return Roots.begin(); }
+  const_root_iterator root_begin() const { return Roots.begin(); }
+  root_iterator root_end() { return Roots.end(); }
+  const_root_iterator root_end() const { return Roots.end(); }
+
+  size_t root_size() const { return Roots.size(); }
+
+  iterator_range<root_iterator> roots() {
+    return make_range(root_begin(), root_end());
+  }
+  iterator_range<const_root_iterator> roots() const {
+    return make_range(root_begin(), root_end());
+  }
 
   /// isPostDominator - Returns true if analysis based of postdoms
   ///
   bool isPostDominator() const { return IsPostDominator; }
 
   /// compare - Return false if the other dominator tree base matches this
   /// dominator tree base. Otherwise return true.
   bool compare(const DominatorTreeBase &Other) const {

llvm/include/llvm/Support/GenericDomTreeConstruction.h

#endif
 
   // Check if the computed DFS numbers are correct. Note that DFS info may not
   // be valid, and when that is the case, we don't verify the numbers.
   // Running time: O(N log(N)).
   static bool VerifyDFSNumbers(const DomTreeT &DT) {
     if (!DT.DFSInfoValid || !DT.Parent)
       return true;
 
-    const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
+    const NodePtr RootBB = IsPostDom ? nullptr : *DT.root_begin();
     const TreeNodePtr Root = DT.getNode(RootBB);
 
     auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
       errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
              << TN->getDFSNumOut() << '}';
     };
 
     // Verify the root's DFS In number. Although DFS numbering would also work

llvm/lib/Target/AMDGPU/AMDGPUUnifyDivergentExitNodes.cpp

 }
 
 bool AMDGPUUnifyDivergentExitNodes::runOnFunction(Function &F) {
   auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 
   // If there's only one exit, we don't need to do anything, unless this is a
   // pixel shader and that exit is an infinite loop, since we still have to
   // insert an export in that case.
-  if (PDT.getRoots().size() <= 1 &&
-      F.getCallingConv() != CallingConv::AMDGPU_PS)
+  if (PDT.root_size() <= 1 && F.getCallingConv() != CallingConv::AMDGPU_PS)
     return false;
 
   LegacyDivergenceAnalysis &DA = getAnalysis<LegacyDivergenceAnalysis>();
 
   // Loop over all of the blocks in a function, tracking all of the blocks that
   // return.
   SmallVector<BasicBlock *, 4> ReturningBlocks;
   SmallVector<BasicBlock *, 4> UniformlyReachedRetBlocks;
   SmallVector<BasicBlock *, 4> UnreachableBlocks;
 
   // Dummy return block for infinite loop.
   BasicBlock *DummyReturnBB = nullptr;
 
   bool InsertExport = false;
 
   bool Changed = false;
-  for (BasicBlock *BB : PDT.getRoots()) {
+  for (BasicBlock *BB : PDT.roots()) {
     if (isa<ReturnInst>(BB->getTerminator())) {
       if (!isUniformlyReached(DA, *BB))
         ReturningBlocks.push_back(BB);
       else
         UniformlyReachedRetBlocks.push_back(BB);
     } else if (isa<UnreachableInst>(BB->getTerminator())) {
       if (!isUniformlyReached(DA, *BB))
         UnreachableBlocks.push_back(BB);

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (DefVisibleToCallerAfterRet) {
         unsigned UpperBound =
             PostOrderNumbers.find(DomAccess->getBlock())->second;
 
         // If CommonPred is null, there are multiple exits from the function.
         // They all have to be added to the worklist.
         if (CommonPred)
           WorkList.insert(CommonPred);
         else
-          for (BasicBlock *R : PDT.getRoots())
+          for (BasicBlock *R : PDT.roots())
             WorkList.insert(R);
 
         NumCFGTries++;
         // Check if all paths starting from an exit node go through one of the
         // killing blocks before reaching DomAccess.
         for (unsigned I = 0; I < WorkList.size(); I++) {
           NumCFGChecks++;
           BasicBlock *Current = WorkList[I];

llvm/unittests/IR/DominatorTreeTest.cpp

TEST(DominatorTree, InsertFromUnreachable) {
   Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
   EXPECT_TRUE(LastUpdate);
 
   EXPECT_EQ(LastUpdate->Action, Insert);
   BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
   BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
   PDT.insertEdge(From, To);
   EXPECT_TRUE(PDT.verify());
-  EXPECT_TRUE(PDT.getRoots().size() == 2);
+  EXPECT_EQ(PDT.root_size(), 2);
   // Make sure we can use a const pointer with getNode.
   const BasicBlock *BB5 = B.getOrAddBlock("5");
   EXPECT_NE(PDT.getNode(BB5), nullptr);
 }
 
 TEST(DominatorTree, InsertMixed) {
   CFGHolder Holder;
   std::vector<CFGBuilder::Arc> Arcs = {