Skip to content

Commit 86652f2

Browse files
timshen91timshen91
committedApr 19, 2017
Cleanup some GraphTraits iteration code
Use children<> and nodes<> in appropriate places to cleanup the code. Also, as part of the cleanup, change the signature of DominatorTreeBase's Split. It is a protected non-virtual member function called only twice, both from within the class, and the removed passed argument in both cases is '*this'. The reason for the existence of that argument seems to be that back before r43115 Split was a free function, so an argument to get '*this' was needed - but now that is no longer the case. Patch by Yoav Ben-Shalom! Differential Revision: https://reviews.llvm.org/D32118 llvm-svn: 300656
1 parent 5943a96 commit 86652f2

File tree

6 files changed

+65
-114
lines changed

6 files changed

+65
-114
lines changed
 

Diff for: ‎llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

+5-7
Original file line numberDiff line numberDiff line change
@@ -1164,9 +1164,8 @@ template <class BT> struct BlockEdgesAdder {
11641164
void operator()(IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr,
11651165
const LoopData *OuterLoop) {
11661166
const BlockT *BB = BFI.RPOT[Irr.Node.Index];
1167-
for (auto I = Successor::child_begin(BB), E = Successor::child_end(BB);
1168-
I != E; ++I)
1169-
G.addEdge(Irr, BFI.getNode(*I), OuterLoop);
1167+
for (const auto Succ : children<const BlockT *>(BB))
1168+
G.addEdge(Irr, BFI.getNode(Succ), OuterLoop);
11701169
}
11711170
};
11721171
}
@@ -1210,10 +1209,9 @@ BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
12101209
return false;
12111210
} else {
12121211
const BlockT *BB = getBlock(Node);
1213-
for (auto SI = Successor::child_begin(BB), SE = Successor::child_end(BB);
1214-
SI != SE; ++SI)
1215-
if (!addToDist(Dist, OuterLoop, Node, getNode(*SI),
1216-
getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI))))
1212+
for (const auto Succ : children<const BlockT *>(BB))
1213+
if (!addToDist(Dist, OuterLoop, Node, getNode(Succ),
1214+
getWeightFromBranchProb(BPI->getEdgeProbability(BB, Succ))))
12171215
// Irreducible backedge.
12181216
return false;
12191217
}

Diff for: ‎llvm/include/llvm/Analysis/DominanceFrontierImpl.h

+3-5
Original file line numberDiff line numberDiff line change
@@ -174,12 +174,10 @@ ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
174174
// Visit each block only once.
175175
if (visited.insert(currentBB).second) {
176176
// Loop over CFG successors to calculate DFlocal[currentNode]
177-
for (auto SI = BlockTraits::child_begin(currentBB),
178-
SE = BlockTraits::child_end(currentBB);
179-
SI != SE; ++SI) {
177+
for (const auto Succ : children<BlockT *>(currentBB)) {
180178
// Does Node immediately dominate this successor?
181-
if (DT[*SI]->getIDom() != currentNode)
182-
S.insert(*SI);
179+
if (DT[Succ]->getIDom() != currentNode)
180+
S.insert(Succ);
183181
}
184182
}
185183

Diff for: ‎llvm/include/llvm/Analysis/LoopInfo.h

+7-16
Original file line numberDiff line numberDiff line change
@@ -158,11 +158,8 @@ class LoopBase {
158158
/// True if terminator in the block can branch to another block that is
159159
/// outside of the current loop.
160160
bool isLoopExiting(const BlockT *BB) const {
161-
typedef GraphTraits<const BlockT*> BlockTraits;
162-
for (typename BlockTraits::ChildIteratorType SI =
163-
BlockTraits::child_begin(BB),
164-
SE = BlockTraits::child_end(BB); SI != SE; ++SI) {
165-
if (!contains(*SI))
161+
for (const auto Succ : children<const BlockT*>(BB)) {
162+
if (!contains(Succ))
166163
return true;
167164
}
168165
return false;
@@ -186,11 +183,8 @@ class LoopBase {
186183
unsigned NumBackEdges = 0;
187184
BlockT *H = getHeader();
188185

189-
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
190-
for (typename InvBlockTraits::ChildIteratorType I =
191-
InvBlockTraits::child_begin(H),
192-
E = InvBlockTraits::child_end(H); I != E; ++I)
193-
if (contains(*I))
186+
for (const auto Pred : children<Inverse<BlockT*> >(H))
187+
if (contains(Pred))
194188
++NumBackEdges;
195189

196190
return NumBackEdges;
@@ -249,12 +243,9 @@ class LoopBase {
249243
/// contains a branch back to the header.
250244
void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
251245
BlockT *H = getHeader();
252-
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
253-
for (typename InvBlockTraits::ChildIteratorType I =
254-
InvBlockTraits::child_begin(H),
255-
E = InvBlockTraits::child_end(H); I != E; ++I)
256-
if (contains(*I))
257-
LoopLatches.push_back(*I);
246+
for (const auto Pred : children<Inverse<BlockT*>>(H))
247+
if (contains(Pred))
248+
LoopLatches.push_back(Pred);
258249
}
259250

260251
//===--------------------------------------------------------------------===//

Diff for: ‎llvm/include/llvm/Analysis/LoopInfoImpl.h

+23-50
Original file line numberDiff line numberDiff line change
@@ -34,14 +34,11 @@ namespace llvm {
3434
template<class BlockT, class LoopT>
3535
void LoopBase<BlockT, LoopT>::
3636
getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
37-
typedef GraphTraits<BlockT*> BlockTraits;
38-
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
39-
for (typename BlockTraits::ChildIteratorType I =
40-
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
41-
I != E; ++I)
42-
if (!contains(*I)) {
37+
for (const auto BB : blocks())
38+
for (const auto Succ : children<BlockT*>(BB))
39+
if (!contains(Succ)) {
4340
// Not in current loop? It must be an exit block.
44-
ExitingBlocks.push_back(*BI);
41+
ExitingBlocks.push_back(BB);
4542
break;
4643
}
4744
}
@@ -63,14 +60,11 @@ BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
6360
template<class BlockT, class LoopT>
6461
void LoopBase<BlockT, LoopT>::
6562
getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
66-
typedef GraphTraits<BlockT*> BlockTraits;
67-
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
68-
for (typename BlockTraits::ChildIteratorType I =
69-
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
70-
I != E; ++I)
71-
if (!contains(*I))
63+
for (const auto BB : blocks())
64+
for (const auto Succ : children<BlockT*>(BB))
65+
if (!contains(Succ))
7266
// Not in current loop? It must be an exit block.
73-
ExitBlocks.push_back(*I);
67+
ExitBlocks.push_back(Succ);
7468
}
7569

7670
/// getExitBlock - If getExitBlocks would return exactly one block,
@@ -88,14 +82,11 @@ BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
8882
template<class BlockT, class LoopT>
8983
void LoopBase<BlockT, LoopT>::
9084
getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
91-
typedef GraphTraits<BlockT*> BlockTraits;
92-
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
93-
for (typename BlockTraits::ChildIteratorType I =
94-
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
95-
I != E; ++I)
96-
if (!contains(*I))
85+
for (const auto BB : blocks())
86+
for (const auto Succ : children<BlockT*>(BB))
87+
if (!contains(Succ))
9788
// Not in current loop? It must be an exit block.
98-
ExitEdges.push_back(Edge(*BI, *I));
89+
ExitEdges.emplace_back(BB, Succ);
9990
}
10091

10192
/// getLoopPreheader - If there is a preheader for this loop, return it. A
@@ -134,15 +125,11 @@ BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
134125

135126
// Loop over the predecessors of the header node...
136127
BlockT *Header = getHeader();
137-
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
138-
for (typename InvBlockTraits::ChildIteratorType PI =
139-
InvBlockTraits::child_begin(Header),
140-
PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
141-
typename InvBlockTraits::NodeRef N = *PI;
142-
if (!contains(N)) { // If the block is not in the loop...
143-
if (Out && Out != N)
128+
for (const auto Pred : children<Inverse<BlockT*>>(Header)) {
129+
if (!contains(Pred)) { // If the block is not in the loop...
130+
if (Out && Out != Pred)
144131
return nullptr; // Multiple predecessors outside the loop
145-
Out = N;
132+
Out = Pred;
146133
}
147134
}
148135

@@ -156,17 +143,11 @@ BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
156143
template<class BlockT, class LoopT>
157144
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
158145
BlockT *Header = getHeader();
159-
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
160-
typename InvBlockTraits::ChildIteratorType PI =
161-
InvBlockTraits::child_begin(Header);
162-
typename InvBlockTraits::ChildIteratorType PE =
163-
InvBlockTraits::child_end(Header);
164146
BlockT *Latch = nullptr;
165-
for (; PI != PE; ++PI) {
166-
typename InvBlockTraits::NodeRef N = *PI;
167-
if (contains(N)) {
147+
for (const auto Pred : children<Inverse<BlockT*>>(Header)) {
148+
if (contains(Pred)) {
168149
if (Latch) return nullptr;
169-
Latch = N;
150+
Latch = Pred;
170151
}
171152
}
172153

@@ -394,11 +375,9 @@ static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges,
394375
// within this subloop tree itself. Note that a predecessor may directly
395376
// reach another subloop that is not yet discovered to be a subloop of
396377
// this loop, which we must traverse.
397-
for (typename InvBlockTraits::ChildIteratorType PI =
398-
InvBlockTraits::child_begin(PredBB),
399-
PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
400-
if (LI->getLoopFor(*PI) != Subloop)
401-
ReverseCFGWorklist.push_back(*PI);
378+
for (const auto Pred : children<Inverse<BlockT*>>(PredBB)) {
379+
if (LI->getLoopFor(Pred) != Subloop)
380+
ReverseCFGWorklist.push_back(Pred);
402381
}
403382
}
404383
}
@@ -482,13 +461,7 @@ analyze(const DominatorTreeBase<BlockT> &DomTree) {
482461
SmallVector<BlockT *, 4> Backedges;
483462

484463
// Check each predecessor of the potential loop header.
485-
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
486-
for (typename InvBlockTraits::ChildIteratorType PI =
487-
InvBlockTraits::child_begin(Header),
488-
PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
489-
490-
BlockT *Backedge = *PI;
491-
464+
for (const auto Backedge : children<Inverse<BlockT*>>(Header)) {
492465
// If Header dominates predBB, this is a new loop. Collect the backedges.
493466
if (DomTree.dominates(Header, Backedge)
494467
&& DomTree.isReachableFromEntry(Backedge)) {

Diff for: ‎llvm/include/llvm/Support/GenericDomTree.h

+24-32
Original file line numberDiff line numberDiff line change
@@ -276,32 +276,25 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
276276

277277
// NewBB is split and now it has one successor. Update dominator tree to
278278
// reflect this change.
279-
template <class N, class GraphT>
280-
void Split(DominatorTreeBaseByGraphTraits<GraphT> &DT,
281-
typename GraphT::NodeRef NewBB) {
279+
template <class N>
280+
void Split(typename GraphTraits<N>::NodeRef NewBB) {
281+
using GraphT = GraphTraits<N>;
282+
using NodeRef = typename GraphT::NodeRef;
282283
assert(std::distance(GraphT::child_begin(NewBB),
283284
GraphT::child_end(NewBB)) == 1 &&
284285
"NewBB should have a single successor!");
285-
typename GraphT::NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
286+
NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
286287

287-
std::vector<typename GraphT::NodeRef> PredBlocks;
288-
typedef GraphTraits<Inverse<N>> InvTraits;
289-
for (typename InvTraits::ChildIteratorType
290-
PI = InvTraits::child_begin(NewBB),
291-
PE = InvTraits::child_end(NewBB);
292-
PI != PE; ++PI)
293-
PredBlocks.push_back(*PI);
288+
std::vector<NodeRef> PredBlocks;
289+
for (const auto Pred : children<Inverse<N>>(NewBB))
290+
PredBlocks.push_back(Pred);
294291

295292
assert(!PredBlocks.empty() && "No predblocks?");
296293

297294
bool NewBBDominatesNewBBSucc = true;
298-
for (typename InvTraits::ChildIteratorType
299-
PI = InvTraits::child_begin(NewBBSucc),
300-
E = InvTraits::child_end(NewBBSucc);
301-
PI != E; ++PI) {
302-
typename InvTraits::NodeRef ND = *PI;
303-
if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
304-
DT.isReachableFromEntry(ND)) {
295+
for (const auto Pred : children<Inverse<N>>(NewBBSucc)) {
296+
if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
297+
isReachableFromEntry(Pred)) {
305298
NewBBDominatesNewBBSucc = false;
306299
break;
307300
}
@@ -312,7 +305,7 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
312305
NodeT *NewBBIDom = nullptr;
313306
unsigned i = 0;
314307
for (i = 0; i < PredBlocks.size(); ++i)
315-
if (DT.isReachableFromEntry(PredBlocks[i])) {
308+
if (isReachableFromEntry(PredBlocks[i])) {
316309
NewBBIDom = PredBlocks[i];
317310
break;
318311
}
@@ -324,18 +317,18 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
324317
return;
325318

326319
for (i = i + 1; i < PredBlocks.size(); ++i) {
327-
if (DT.isReachableFromEntry(PredBlocks[i]))
328-
NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
320+
if (isReachableFromEntry(PredBlocks[i]))
321+
NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
329322
}
330323

331324
// Create the new dominator tree node... and set the idom of NewBB.
332-
DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
325+
DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
333326

334327
// If NewBB strictly dominates other blocks, then it is now the immediate
335328
// dominator of NewBBSucc. Update the dominator tree as appropriate.
336329
if (NewBBDominatesNewBBSucc) {
337-
DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
338-
DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
330+
DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
331+
changeImmediateDominator(NewBBSuccNode, NewBBNode);
339332
}
340333
}
341334

@@ -379,7 +372,7 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
379372
if (DomTreeNodes.size() != OtherDomTreeNodes.size())
380373
return true;
381374

382-
for (const auto &DomTreeNode : this->DomTreeNodes) {
375+
for (const auto &DomTreeNode : DomTreeNodes) {
383376
NodeT *BB = DomTreeNode.first;
384377
typename DomTreeNodeMapType::const_iterator OI =
385378
OtherDomTreeNodes.find(BB);
@@ -663,10 +656,9 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
663656
/// tree to reflect this change.
664657
void splitBlock(NodeT *NewBB) {
665658
if (this->IsPostDominators)
666-
this->Split<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this,
667-
NewBB);
659+
Split<Inverse<NodeT *>>(NewBB);
668660
else
669-
this->Split<NodeT *, GraphTraits<NodeT *>>(*this, NewBB);
661+
Split<NodeT *>(NewBB);
670662
}
671663

672664
/// print - Convert to human readable form
@@ -677,7 +669,7 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
677669
o << "Inorder PostDominator Tree: ";
678670
else
679671
o << "Inorder Dominator Tree: ";
680-
if (!this->DFSInfoValid)
672+
if (!DFSInfoValid)
681673
o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
682674
o << "\n";
683675

@@ -712,12 +704,12 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
712704
// immediate dominator.
713705
NodeT *IDom = getIDom(BB);
714706

715-
assert(IDom || this->DomTreeNodes[nullptr]);
707+
assert(IDom || DomTreeNodes[nullptr]);
716708
DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
717709

718710
// Add a new tree node for this NodeT, and link it as a child of
719711
// IDomNode
720-
return (this->DomTreeNodes[BB] = IDomNode->addChild(
712+
return (DomTreeNodes[BB] = IDomNode->addChild(
721713
llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
722714
}
723715

@@ -780,7 +772,7 @@ template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
780772
template <class FT> void recalculate(FT &F) {
781773
typedef GraphTraits<FT *> TraitsTy;
782774
reset();
783-
this->Vertex.push_back(nullptr);
775+
Vertex.push_back(nullptr);
784776

785777
if (!this->IsPostDominators) {
786778
// Initialize root

Diff for: ‎llvm/include/llvm/Support/GraphWriter.h

+3-4
Original file line numberDiff line numberDiff line change
@@ -143,10 +143,9 @@ class GraphWriter {
143143

144144
void writeNodes() {
145145
// Loop over the graph, printing it out...
146-
for (node_iterator I = GTraits::nodes_begin(G), E = GTraits::nodes_end(G);
147-
I != E; ++I)
148-
if (!isNodeHidden(*I))
149-
writeNode(*I);
146+
for (const auto Node : nodes<GraphType>(G))
147+
if (!isNodeHidden(Node))
148+
writeNode(Node);
150149
}
151150

152151
bool isNodeHidden(NodeRef Node) {

0 commit comments

Comments
 (0)
Please sign in to comment.