From 77cf856e56dc568ebe760e7de820323fdcf825a4 Mon Sep 17 00:00:00 2001 From: David Blaikie Date: Fri, 11 Apr 2014 01:50:01 +0000 Subject: [PATCH] Implement depth_first and inverse_depth_first range factory functions. Also updated as many loops as I could find using df_begin/idf_begin - strangely I found no uses of idf_begin. Is that just used out of tree? Also a few places couldn't use df_begin because either they used the member functions of the depth first iterators or had specific ordering constraints (I added a comment in the latter case). Based on a patch by Jim Grosbach. (Jim - you just had iterator_range where you needed iterator_range>) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206016 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/DepthFirstIterator.h | 13 ++++++++++++ include/llvm/Analysis/LoopInfoImpl.h | 9 ++++----- lib/CodeGen/StackColoring.cpp | 20 +++++++++---------- lib/Target/ARM64/ARM64ConditionalCompares.cpp | 2 +- lib/Target/R600/AMDILCFGStructurizer.cpp | 12 +++++------ .../Instrumentation/AddressSanitizer.cpp | 6 ++---- .../Instrumentation/DataFlowSanitizer.cpp | 5 ++--- .../Instrumentation/MemorySanitizer.cpp | 6 ++---- lib/Transforms/Scalar/GVN.cpp | 10 +++------- lib/Transforms/Utils/SimplifyInstructions.cpp | 7 ++++--- 10 files changed, 45 insertions(+), 45 deletions(-) diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index 644544253ab..dfba43f3ac8 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -33,6 +33,7 @@ #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H #define LLVM_ADT_DEPTHFIRSTITERATOR_H +#include "llvm/ADT/iterator_range.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" @@ -207,6 +208,12 @@ df_iterator df_end(const T& G) { return df_iterator::end(G); } +// Provide an accessor method to use them in range-based patterns. +template +iterator_range> depth_first(const T& G) { + return iterator_range>(df_begin(G), df_end(G)); +} + // Provide global definitions of external depth first iterators... template ::NodeType*> > struct df_ext_iterator : public df_iterator { @@ -244,6 +251,12 @@ idf_iterator idf_end(const T& G){ return idf_iterator::end(Inverse(G)); } +// Provide an accessor method to use them in range-based patterns. +template +iterator_range> inverse_depth_first(const T& G) { + return iterator_range>(idf_begin(G), idf_end(G)); +} + // Provide global definitions of external inverse depth first iterators... template ::NodeType*> > struct idf_ext_iterator : public idf_iterator { diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index dd2dc28bb06..0c0d5c44fb5 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -270,11 +270,10 @@ void LoopBase::verifyLoop() const { // though it is permitted if the predecessor is not itself actually // reachable. BlockT *EntryBB = BB->getParent()->begin(); - for (df_iterator NI = df_begin(EntryBB), - NE = df_end(EntryBB); NI != NE; ++NI) - for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) - assert(*NI != OutsideLoopPreds[i] && - "Loop has multiple entry points!"); + for (BlockT *CB : depth_first(EntryBB)) + for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) + assert(CB != OutsideLoopPreds[i] && + "Loop has multiple entry points!"); } assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!"); assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!"); diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index 7b1de85baa7..ac1f320b8b2 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -193,12 +193,11 @@ void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { } void StackColoring::dump() const { - for (df_iterator FI = df_begin(MF), FE = df_end(MF); - FI != FE; ++FI) { - DEBUG(dbgs()<<"Inspecting block #"<getName()<<"]\n"); + for (MachineBasicBlock *MBB : depth_first(MF)) { + DEBUG(dbgs() << "Inspecting block #" << BasicBlocks.lookup(MBB) << " [" + << MBB->getName() << "]\n"); - LivenessMap::const_iterator BI = BlockLiveness.find(*FI); + LivenessMap::const_iterator BI = BlockLiveness.find(MBB); assert(BI != BlockLiveness.end() && "Block not found"); const BlockLifetimeInfo &BlockInfo = BI->second; @@ -231,20 +230,19 @@ unsigned StackColoring::collectMarkers(unsigned NumSlot) { // NOTE: We use the a reverse-post-order iteration to ensure that we obtain a // deterministic numbering, and because we'll need a post-order iteration // later for solving the liveness dataflow problem. - for (df_iterator FI = df_begin(MF), FE = df_end(MF); - FI != FE; ++FI) { + for (MachineBasicBlock *MBB : depth_first(MF)) { // Assign a serial number to this basic block. - BasicBlocks[*FI] = BasicBlockNumbering.size(); - BasicBlockNumbering.push_back(*FI); + BasicBlocks[MBB] = BasicBlockNumbering.size(); + BasicBlockNumbering.push_back(MBB); // Keep a reference to avoid repeated lookups. - BlockLifetimeInfo &BlockInfo = BlockLiveness[*FI]; + BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB]; BlockInfo.Begin.resize(NumSlot); BlockInfo.End.resize(NumSlot); - for (MachineInstr &MI : **FI) { + for (MachineInstr &MI : *MBB) { if (MI.getOpcode() != TargetOpcode::LIFETIME_START && MI.getOpcode() != TargetOpcode::LIFETIME_END) continue; diff --git a/lib/Target/ARM64/ARM64ConditionalCompares.cpp b/lib/Target/ARM64/ARM64ConditionalCompares.cpp index cefa44ad96a..759e8b7df4f 100644 --- a/lib/Target/ARM64/ARM64ConditionalCompares.cpp +++ b/lib/Target/ARM64/ARM64ConditionalCompares.cpp @@ -908,7 +908,7 @@ bool ARM64ConditionalCompares::runOnMachineFunction(MachineFunction &MF) { // Note that updateDomTree() modifies the children of the DomTree node // currently being visited. The df_iterator supports that; it doesn't look at // child_begin() / child_end() until after a node has been visited. - for (auto *I : make_range(df_begin(DomTree), df_end(DomTree))) + for (auto *I : depth_first(DomTree)) if (tryConvert(I->getBlock())) Changed = true; diff --git a/lib/Target/R600/AMDILCFGStructurizer.cpp b/lib/Target/R600/AMDILCFGStructurizer.cpp index 21ca560dba0..1b458df294e 100644 --- a/lib/Target/R600/AMDILCFGStructurizer.cpp +++ b/lib/Target/R600/AMDILCFGStructurizer.cpp @@ -1075,13 +1075,11 @@ int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) { int AMDGPUCFGStructurizer::loopendPatternMatch() { std::vector NestedLoops; - for (MachineLoopInfo::iterator It = MLI->begin(), E = MLI->end(); - It != E; ++It) { - df_iterator LpIt = df_begin(*It), - LpE = df_end(*It); - for (; LpIt != LpE; ++LpIt) - NestedLoops.push_back(*LpIt); - } + for (MachineLoopInfo::iterator It = MLI->begin(), E = MLI->end(); It != E; + ++It) + for (MachineLoop *ML : depth_first(*It)) + NestedLoops.push_back(ML); + if (NestedLoops.size() == 0) return 0; diff --git a/lib/Transforms/Instrumentation/AddressSanitizer.cpp b/lib/Transforms/Instrumentation/AddressSanitizer.cpp index bbfa4c57146..d2ed8748fe8 100644 --- a/lib/Transforms/Instrumentation/AddressSanitizer.cpp +++ b/lib/Transforms/Instrumentation/AddressSanitizer.cpp @@ -443,11 +443,9 @@ struct FunctionStackPoisoner : public InstVisitor { bool runOnFunction() { if (!ClStack) return false; // Collect alloca, ret, lifetime instructions etc. - for (df_iterator DI = df_begin(&F.getEntryBlock()), - DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { - BasicBlock *BB = *DI; + for (BasicBlock *BB : depth_first(&F.getEntryBlock())) visit(*BB); - } + if (AllocaVec.empty()) return false; initializeCallbacks(*F.getParent()); diff --git a/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp b/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp index df1549d405c..61edb7b0544 100644 --- a/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp +++ b/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp @@ -680,9 +680,8 @@ bool DataFlowSanitizer::runOnModule(Module &M) { // DFSanVisitor may create new basic blocks, which confuses df_iterator. // Build a copy of the list before iterating over it. - llvm::SmallVector BBList; - std::copy(df_begin(&(*i)->getEntryBlock()), df_end(&(*i)->getEntryBlock()), - std::back_inserter(BBList)); + llvm::SmallVector BBList( + depth_first(&(*i)->getEntryBlock())); for (llvm::SmallVector::iterator i = BBList.begin(), e = BBList.end(); diff --git a/lib/Transforms/Instrumentation/MemorySanitizer.cpp b/lib/Transforms/Instrumentation/MemorySanitizer.cpp index ec1a195c950..fd846829a59 100644 --- a/lib/Transforms/Instrumentation/MemorySanitizer.cpp +++ b/lib/Transforms/Instrumentation/MemorySanitizer.cpp @@ -662,11 +662,9 @@ struct MemorySanitizerVisitor : public InstVisitor { // Iterate all BBs in depth-first order and create shadow instructions // for all instructions (where applicable). // For PHI nodes we create dummy shadow PHIs which will be finalized later. - for (df_iterator DI = df_begin(&F.getEntryBlock()), - DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { - BasicBlock *BB = *DI; + for (BasicBlock *BB : depth_first(&F.getEntryBlock())) visit(*BB); - } + // Finalize PHI nodes. for (size_t i = 0, n = ShadowPHINodes.size(); i < n; i++) { diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 33c387cb71c..0188b6e3f5d 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -2421,10 +2421,7 @@ bool GVN::processBlock(BasicBlock *BB) { bool GVN::performPRE(Function &F) { bool Changed = false; SmallVector, 8> predMap; - for (df_iterator DI = df_begin(&F.getEntryBlock()), - DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { - BasicBlock *CurrentBlock = *DI; - + for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) { // Nothing to PRE in the entry block. if (CurrentBlock == &F.getEntryBlock()) continue; @@ -2637,9 +2634,8 @@ bool GVN::iterateOnFunction(Function &F) { // std::vector BBVect; BBVect.reserve(256); - for (df_iterator DI = df_begin(DT->getRootNode()), - DE = df_end(DT->getRootNode()); DI != DE; ++DI) - BBVect.push_back(DI->getBlock()); + for (DomTreeNode *x : depth_first(DT->getRootNode())) + BBVect.push_back(x->getBlock()); for (std::vector::iterator I = BBVect.begin(), E = BBVect.end(); I != E; I++) diff --git a/lib/Transforms/Utils/SimplifyInstructions.cpp b/lib/Transforms/Utils/SimplifyInstructions.cpp index bbd65f17528..6762527cf76 100644 --- a/lib/Transforms/Utils/SimplifyInstructions.cpp +++ b/lib/Transforms/Utils/SimplifyInstructions.cpp @@ -55,9 +55,10 @@ namespace { bool Changed = false; do { - for (df_iterator DI = df_begin(&F.getEntryBlock()), - DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) - for (BasicBlock::iterator BI = DI->begin(), BE = DI->end(); BI != BE;) { + for (BasicBlock *BB : depth_first(&F.getEntryBlock())) + // Here be subtlety: the iterator must be incremented before the loop + // body (not sure why), so a range-for loop won't work here. + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { Instruction *I = BI++; // The first time through the loop ToSimplify is empty and we try to // simplify all instructions. On later iterations ToSimplify is not -- 2.34.1