From 7871b8666029eb5183e02b389bd93f36d6dca8e3 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Wed, 15 Apr 2015 17:41:42 +0000 Subject: [PATCH] Add range iterators for post order and inverse post order. Use them git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@235026 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/PostOrderIterator.h | 23 +++++++++++++++++++ include/llvm/Analysis/LoopInfoImpl.h | 5 ++-- include/llvm/Analysis/RegionInfoImpl.h | 6 ++--- lib/Analysis/BranchProbabilityInfo.cpp | 22 ++++++++---------- lib/CodeGen/EarlyIfConversion.cpp | 5 ++-- lib/CodeGen/MachineTraceMetrics.cpp | 16 +++++-------- .../SelectionDAG/FunctionLoweringInfo.cpp | 3 +-- lib/Transforms/Vectorize/SLPVectorizer.cpp | 4 +--- 8 files changed, 47 insertions(+), 37 deletions(-) diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index fa337e9efb8..e7214e30495 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -18,6 +18,7 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" #include #include @@ -178,6 +179,10 @@ po_iterator po_begin(T G) { return po_iterator::begin(G); } template po_iterator po_end (T G) { return po_iterator::end(G); } +template iterator_range> post_order(T G) { + return iterator_range>(po_begin(G), po_end(G)); +} + // Provide global definitions of external postorder iterators... template::NodeType*> > struct po_ext_iterator : public po_iterator { @@ -195,6 +200,12 @@ po_ext_iterator po_ext_end(T G, SetType &S) { return po_ext_iterator::end(G, S); } +template +iterator_range> post_order_ext(T G, SetType &S) { + return iterator_range>(po_ext_begin(G, S), + po_ext_end(G, S)); +} + // Provide global definitions of inverse post order iterators... template ::NodeType*>, @@ -214,6 +225,11 @@ ipo_iterator ipo_end(T G){ return ipo_iterator::end(G); } +template +iterator_range> inverse_post_order(T G, bool Reverse = false) { + return iterator_range>(ipo_begin(G, Reverse), ipo_end(G)); +} + // Provide global definitions of external inverse postorder iterators... template ::NodeType*> > @@ -234,6 +250,13 @@ ipo_ext_iterator ipo_ext_end(T G, SetType &S) { return ipo_ext_iterator::end(G, S); } +template +iterator_range> +inverse_post_order_ext(T G, SetType &S) { + return iterator_range>(ipo_ext_begin(G, S), + ipo_ext_end(G, S)); +} + //===--------------------------------------------------------------------===// // Reverse Post Order CFG iterator code //===--------------------------------------------------------------------===// diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index 7cc4a77c690..ded6e9292a7 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -498,10 +498,9 @@ Analyze(DominatorTreeBase &DomTree) { // Postorder traversal of the dominator tree. DomTreeNodeBase* DomRoot = DomTree.getRootNode(); - for (po_iterator*> DomIter = po_begin(DomRoot), - DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) { + for (auto DomNode : post_order(DomRoot)) { - BlockT *Header = DomIter->getBlock(); + BlockT *Header = DomNode->getBlock(); SmallVector Backedges; // Check each predecessor of the potential loop header. diff --git a/include/llvm/Analysis/RegionInfoImpl.h b/include/llvm/Analysis/RegionInfoImpl.h index b0dc26312aa..1f48d046720 100644 --- a/include/llvm/Analysis/RegionInfoImpl.h +++ b/include/llvm/Analysis/RegionInfoImpl.h @@ -714,10 +714,8 @@ void RegionInfoBase::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) { // regions from the bottom of the dominance tree. If the small regions are // detected first, detection of bigger regions is faster, as we can jump // over the small regions. - for (po_iterator FI = po_begin(N), FE = po_end(N); FI != FE; - ++FI) { - findRegionsWithEntry(FI->getBlock(), ShortCut); - } + for (auto DomNode : post_order(N)) + findRegionsWithEntry(DomNode->getBlock(), ShortCut); } template diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index d7cee3afaf5..8799a710af0 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -507,25 +507,23 @@ bool BranchProbabilityInfo::runOnFunction(Function &F) { // Walk the basic blocks in post-order so that we can build up state about // the successors of a block iteratively. - for (po_iterator I = po_begin(&F.getEntryBlock()), - E = po_end(&F.getEntryBlock()); - I != E; ++I) { - DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n"); - if (calcUnreachableHeuristics(*I)) + for (auto BB : post_order(&F.getEntryBlock())) { + DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); + if (calcUnreachableHeuristics(BB)) continue; - if (calcMetadataWeights(*I)) + if (calcMetadataWeights(BB)) continue; - if (calcColdCallHeuristics(*I)) + if (calcColdCallHeuristics(BB)) continue; - if (calcLoopBranchHeuristics(*I)) + if (calcLoopBranchHeuristics(BB)) continue; - if (calcPointerHeuristics(*I)) + if (calcPointerHeuristics(BB)) continue; - if (calcZeroHeuristics(*I)) + if (calcZeroHeuristics(BB)) continue; - if (calcFloatingPointHeuristics(*I)) + if (calcFloatingPointHeuristics(BB)) continue; - calcInvokeHeuristics(*I); + calcInvokeHeuristics(BB); } PostDominatedByUnreachable.clear(); diff --git a/lib/CodeGen/EarlyIfConversion.cpp b/lib/CodeGen/EarlyIfConversion.cpp index 8f742713ccf..6cde4c24915 100644 --- a/lib/CodeGen/EarlyIfConversion.cpp +++ b/lib/CodeGen/EarlyIfConversion.cpp @@ -797,9 +797,8 @@ bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { // if-conversion in a single pass. The tryConvertIf() function may erase // blocks, but only blocks dominated by the head block. This makes it safe to // update the dominator tree while the post-order iterator is still active. - for (po_iterator - I = po_begin(DomTree), E = po_end(DomTree); I != E; ++I) - if (tryConvertIf(I->getBlock())) + for (auto DomNode : post_order(DomTree)) + if (tryConvertIf(DomNode->getBlock())) Changed = true; return Changed; diff --git a/lib/CodeGen/MachineTraceMetrics.cpp b/lib/CodeGen/MachineTraceMetrics.cpp index 8aacd1f31bb..5dc7c216994 100644 --- a/lib/CodeGen/MachineTraceMetrics.cpp +++ b/lib/CodeGen/MachineTraceMetrics.cpp @@ -463,13 +463,11 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { // Run an upwards post-order search for the trace start. Bounds.Downward = false; Bounds.Visited.clear(); - typedef ipo_ext_iterator UpwardPO; - for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds); - I != E; ++I) { + for (auto I : inverse_post_order_ext(MBB, Bounds)) { DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; // All the predecessors have been visited, pick the preferred one. - TBI.Pred = pickTracePred(*I); + TBI.Pred = pickTracePred(I); DEBUG({ if (TBI.Pred) dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; @@ -477,19 +475,17 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { dbgs() << "null\n"; }); // The trace leading to I is now known, compute the depth resources. - computeDepthResources(*I); + computeDepthResources(I); } // Run a downwards post-order search for the trace end. Bounds.Downward = true; Bounds.Visited.clear(); - typedef po_ext_iterator DownwardPO; - for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds); - I != E; ++I) { + for (auto I : post_order_ext(MBB, Bounds)) { DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; // All the successors have been visited, pick the preferred one. - TBI.Succ = pickTraceSucc(*I); + TBI.Succ = pickTraceSucc(I); DEBUG({ if (TBI.Succ) dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; @@ -497,7 +493,7 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { dbgs() << "null\n"; }); // The trace leaving I is now known, compute the height resources. - computeHeightResources(*I); + computeHeightResources(I); } } diff --git a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp index 65a67265d79..4b8ae32e9a5 100644 --- a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp +++ b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp @@ -652,8 +652,7 @@ void llvm::ComputeUsesVAFloatArgument(const CallInst &I, if (FT->isVarArg() && !MMI->usesVAFloatArgument()) { for (unsigned i = 0, e = I.getNumArgOperands(); i != e; ++i) { Type* T = I.getArgOperand(i)->getType(); - for (po_iterator i = po_begin(T), e = po_end(T); - i != e; ++i) { + for (auto i : post_order(T)) { if (i->isFloatingPointTy()) { MMI->setUsesVAFloatArgument(true); return; diff --git a/lib/Transforms/Vectorize/SLPVectorizer.cpp b/lib/Transforms/Vectorize/SLPVectorizer.cpp index 5eae4e278c5..7267f58d1c9 100644 --- a/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -3101,9 +3101,7 @@ struct SLPVectorizer : public FunctionPass { // delete instructions. // Scan the blocks in the function in post order. - for (po_iterator it = po_begin(&F.getEntryBlock()), - e = po_end(&F.getEntryBlock()); it != e; ++it) { - BasicBlock *BB = *it; + for (auto BB : post_order(&F.getEntryBlock())) { // Vectorize trees that end at stores. if (unsigned count = collectStores(BB, R)) { (void)count; -- 2.34.1