diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h --- a/llvm/include/llvm/Support/GenericDomTree.h +++ b/llvm/include/llvm/Support/GenericDomTree.h @@ -77,18 +77,25 @@ const_iterator begin() const { return Children.begin(); } const_iterator end() const { return Children.end(); } + DomTreeNodeBase *const &back() const { return Children.back(); } + DomTreeNodeBase *&back() { return Children.back(); } + + iterator_range children() { return make_range(begin(), end()); } + iterator_range children() const { + return make_range(begin(), end()); + } + NodeT *getBlock() const { return TheBB; } DomTreeNodeBase *getIDom() const { return IDom; } unsigned getLevel() const { return Level; } - const std::vector &getChildren() const { return Children; } - std::unique_ptr addChild( std::unique_ptr C) { Children.push_back(C.get()); return C; } + bool isLeaf() const { return Children.empty(); } size_t getNumChildren() const { return Children.size(); } void clearAllChildren() { Children.clear(); } @@ -619,7 +626,7 @@ void eraseNode(NodeT *BB) { DomTreeNodeBase *Node = getNode(BB); assert(Node && "Removing node that isn't in dominator tree."); - assert(Node->getChildren().empty() && "Node is not a leaf node."); + assert(Node->isLeaf() && "Node is not a leaf node."); DFSInfoValid = false; diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -1396,7 +1396,7 @@ const TreeNodePtr Node = NodeToTN.second.get(); // Handle tree leaves. - if (Node->getChildren().empty()) { + if (Node->isLeaf()) { if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) { errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t"; PrintNodeAndDFSNums(Node); @@ -1508,7 +1508,8 @@ for (auto &NodeToTN : DT.DomTreeNodes) { const TreeNodePtr TN = NodeToTN.second.get(); const NodePtr BB = TN->getBlock(); - if (!BB || TN->getChildren().empty()) continue; + if (!BB || TN->isLeaf()) + continue; LLVM_DEBUG(dbgs() << "Verifying parent property of node " << BlockNamePrinter(TN) << "\n"); @@ -1517,7 +1518,7 @@ return From != BB && To != BB; }); - for (TreeNodePtr Child : TN->getChildren()) + for (TreeNodePtr Child : TN->children()) if (NodeToInfo.count(Child->getBlock()) != 0) { errs() << "Child " << BlockNamePrinter(Child) << " reachable after its parent " << BlockNamePrinter(BB) @@ -1541,17 +1542,17 @@ for (auto &NodeToTN : DT.DomTreeNodes) { const TreeNodePtr TN = NodeToTN.second.get(); const NodePtr BB = TN->getBlock(); - if (!BB || TN->getChildren().empty()) continue; + if (!BB || TN->isLeaf()) + continue; - const auto &Siblings = TN->getChildren(); - for (const TreeNodePtr N : Siblings) { + for (const TreeNodePtr N : TN->children()) { clear(); NodePtr BBN = N->getBlock(); doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) { return From != BBN && To != BBN; }); - for (const TreeNodePtr S : Siblings) { + for (const TreeNodePtr S : TN->children()) { if (S == N) continue; if (NodeToInfo.count(S->getBlock()) == 0) { diff --git a/llvm/lib/CodeGen/EarlyIfConversion.cpp b/llvm/lib/CodeGen/EarlyIfConversion.cpp --- a/llvm/lib/CodeGen/EarlyIfConversion.cpp +++ b/llvm/lib/CodeGen/EarlyIfConversion.cpp @@ -759,7 +759,7 @@ assert(Node != HeadNode && "Cannot erase the head node"); while (Node->getNumChildren()) { assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); - DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); + DomTree->changeImmediateDominator(Node->back(), HeadNode); } DomTree->eraseNode(B); } diff --git a/llvm/lib/CodeGen/InlineSpiller.cpp b/llvm/lib/CodeGen/InlineSpiller.cpp --- a/llvm/lib/CodeGen/InlineSpiller.cpp +++ b/llvm/lib/CodeGen/InlineSpiller.cpp @@ -1306,10 +1306,7 @@ Orders.push_back(MDT.getBase().getNode(Root)); do { MachineDomTreeNode *Node = Orders[idx++]; - const std::vector &Children = Node->getChildren(); - unsigned NumChildren = Children.size(); - for (unsigned i = 0; i != NumChildren; ++i) { - MachineDomTreeNode *Child = Children[i]; + for (MachineDomTreeNode *Child : Node->children()) { if (WorkSet.count(Child)) Orders.push_back(Child); } @@ -1377,10 +1374,7 @@ // Collect spills in subtree of current node (*RIt) to // SpillsInSubTreeMap[*RIt].first. - const std::vector &Children = (*RIt)->getChildren(); - unsigned NumChildren = Children.size(); - for (unsigned i = 0; i != NumChildren; ++i) { - MachineDomTreeNode *Child = Children[i]; + for (MachineDomTreeNode *Child : (*RIt)->children()) { if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end()) continue; // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below diff --git a/llvm/lib/CodeGen/MachineCSE.cpp b/llvm/lib/CodeGen/MachineCSE.cpp --- a/llvm/lib/CodeGen/MachineCSE.cpp +++ b/llvm/lib/CodeGen/MachineCSE.cpp @@ -747,9 +747,8 @@ do { Node = WorkList.pop_back_val(); Scopes.push_back(Node); - const std::vector &Children = Node->getChildren(); - OpenChildren[Node] = Children.size(); - for (MachineDomTreeNode *Child : Children) + OpenChildren[Node] = Node->getNumChildren(); + for (MachineDomTreeNode *Child : Node->children()) WorkList.push_back(Child); } while (!WorkList.empty()); @@ -862,8 +861,7 @@ BBs.push_back(DT->getRootNode()); do { auto Node = BBs.pop_back_val(); - const std::vector &Children = Node->getChildren(); - for (MachineDomTreeNode *Child : Children) + for (MachineDomTreeNode *Child : Node->children()) BBs.push_back(Child); MachineBasicBlock *MBB = Node->getBlock(); diff --git a/llvm/lib/CodeGen/MachineLICM.cpp b/llvm/lib/CodeGen/MachineLICM.cpp --- a/llvm/lib/CodeGen/MachineLICM.cpp +++ b/llvm/lib/CodeGen/MachineLICM.cpp @@ -737,8 +737,7 @@ continue; Scopes.push_back(Node); - const std::vector &Children = Node->getChildren(); - unsigned NumChildren = Children.size(); + unsigned NumChildren = Node->getNumChildren(); // Don't hoist things out of a large switch statement. This often causes // code to be hoisted that wasn't going to be executed, and increases @@ -747,13 +746,14 @@ NumChildren = 0; OpenChildren[Node] = NumChildren; - // Add children in reverse order as then the next popped worklist node is - // the first child of this node. This means we ultimately traverse the - // DOM tree in exactly the same order as if we'd recursed. - for (int i = (int)NumChildren-1; i >= 0; --i) { - MachineDomTreeNode *Child = Children[i]; - ParentMap[Child] = Node; - WorkList.push_back(Child); + if (NumChildren) { + // Add children in reverse order as then the next popped worklist node is + // the first child of this node. This means we ultimately traverse the + // DOM tree in exactly the same order as if we'd recursed. + for (MachineDomTreeNode *Child : reverse(Node->children())) { + ParentMap[Child] = Node; + WorkList.push_back(Child); + } } } diff --git a/llvm/lib/CodeGen/MachineSink.cpp b/llvm/lib/CodeGen/MachineSink.cpp --- a/llvm/lib/CodeGen/MachineSink.cpp +++ b/llvm/lib/CodeGen/MachineSink.cpp @@ -623,14 +623,13 @@ // if () {} else {} // use x // - const std::vector &Children = - DT->getNode(MBB)->getChildren(); - for (const auto &DTChild : Children) + for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) { // DomTree children of MBB that have MBB as immediate dominator are added. if (DTChild->getIDom()->getBlock() == MI.getParent() && // Skip MBBs already added to the AllSuccs vector above. !MBB->isSuccessor(DTChild->getBlock())) AllSuccs.push_back(DTChild->getBlock()); + } // Sort Successors according to their loop depth or block frequency info. llvm::stable_sort( diff --git a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp --- a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp +++ b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp @@ -828,7 +828,7 @@ assert(Node != HeadNode && "Cannot erase the head node"); assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head"); while (Node->getNumChildren()) - DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); + DomTree->changeImmediateDominator(Node->back(), HeadNode); DomTree->eraseNode(RemovedMBB); } } diff --git a/llvm/lib/Target/Mips/MipsOptimizePICCall.cpp b/llvm/lib/Target/Mips/MipsOptimizePICCall.cpp --- a/llvm/lib/Target/Mips/MipsOptimizePICCall.cpp +++ b/llvm/lib/Target/Mips/MipsOptimizePICCall.cpp @@ -218,8 +218,7 @@ MBBI.preVisit(ScopedHT); Changed |= visitNode(MBBI); const MachineDomTreeNode *Node = MBBI.getNode(); - const std::vector &Children = Node->getChildren(); - WorkList.append(Children.begin(), Children.end()); + WorkList.append(Node->begin(), Node->end()); } return Changed; diff --git a/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp b/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp --- a/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp +++ b/llvm/lib/Transforms/Scalar/ConstantHoisting.cpp @@ -250,7 +250,7 @@ Orders.push_back(Entry); while (Idx != Orders.size()) { BasicBlock *Node = Orders[Idx++]; - for (auto ChildDomNode : DT.getNode(Node)->getChildren()) { + for (auto ChildDomNode : DT.getNode(Node)->children()) { if (Candidates.count(ChildDomNode->getBlock())) Orders.push_back(ChildDomNode->getBlock()); } diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp --- a/llvm/lib/Transforms/Scalar/NewGVN.cpp +++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp @@ -3436,7 +3436,7 @@ // Sort dominator tree children arrays into RPO. for (auto &B : RPOT) { auto *Node = DT->getNode(B); - if (Node->getChildren().size() > 1) + if (Node->getNumChildren() > 1) llvm::sort(Node->begin(), Node->end(), [&](const DomTreeNode *A, const DomTreeNode *B) { return RPOOrdering[A] < RPOOrdering[B]; diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -696,10 +696,8 @@ LI->removeBlock(ExitingBlock); DomTreeNode *Node = DT->getNode(ExitingBlock); - const std::vector *> &Children = - Node->getChildren(); - while (!Children.empty()) { - DomTreeNode *Child = Children.front(); + while (!Node->isLeaf()) { + DomTreeNode *Child = Node->back(); DT->changeImmediateDominator(Child, Node->getIDom()); } DT->eraseNode(ExitingBlock); diff --git a/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/llvm/lib/Transforms/Utils/LoopUnroll.cpp --- a/llvm/lib/Transforms/Utils/LoopUnroll.cpp +++ b/llvm/lib/Transforms/Utils/LoopUnroll.cpp @@ -809,7 +809,7 @@ for (auto *BB : OriginalLoopBlocks) { auto *BBDomNode = DT->getNode(BB); SmallVector ChildrenToUpdate; - for (auto *ChildDomNode : BBDomNode->getChildren()) { + for (auto *ChildDomNode : BBDomNode->children()) { auto *ChildBB = ChildDomNode->getBlock(); if (!L->contains(ChildBB)) ChildrenToUpdate.push_back(ChildBB); diff --git a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp --- a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -848,7 +848,7 @@ // dominator of the exit blocks. for (auto *BB : L->blocks()) { auto *DomNodeBB = DT->getNode(BB); - for (auto *DomChild : DomNodeBB->getChildren()) { + for (auto *DomChild : DomNodeBB->children()) { auto *DomChildBB = DomChild->getBlock(); if (!L->contains(LI->getLoopFor(DomChildBB))) ChildrenToUpdate.push_back(DomChildBB); diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -512,9 +512,10 @@ AddRegionToWorklist(N); - for (size_t I = 0; I < Worklist.size(); I++) - for (DomTreeNode *Child : Worklist[I]->getChildren()) + for (size_t I = 0; I < Worklist.size(); I++) { + for (DomTreeNode *Child : Worklist[I]->children()) AddRegionToWorklist(Child); + } return Worklist; }