diff options
Diffstat (limited to 'llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp | 62 |
1 files changed, 45 insertions, 17 deletions
diff --git a/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp index b6b996d..ea3a291 100644 --- a/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp +++ b/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp @@ -14,14 +14,11 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "insert-optimal-edge-profiling" #include "ProfilingUtils.h" -#include "llvm/Constants.h" -#include "llvm/Function.h" -#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ProfileInfo.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Instrumentation.h" @@ -75,8 +72,19 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { return false; // No main, no instrumentation! } + // BlocksToInstrument stores all blocks that are in the function prior to + // instrumenting, since the spliting of critical edges adds new blocks (which + // have not to be instrumented), we have to remember them for later. std::set<BasicBlock*> BlocksToInstrument; + + // NumEdges counts all the edges that may be instrumented. Later on its + // decided which edges to actually instrument, to achieve optimal profiling. + // For the entry block a virtual edge (0,entry) is reserved, for each block + // with no successors an edge (BB,0) is reserved. These edges are necessary + // to calculate a truly optimal maximum spanning tree and thus an optimal + // instrumentation. unsigned NumEdges = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { if (F->isDeclaration()) continue; // Reserve space for (0,entry) edge. @@ -95,6 +103,13 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { } } + // In the profiling output a counter for each edge is reserved, but only few + // are used. This is done to be able to read back in the profile without + // calulating the maximum spanning tree again, instead each edge counter that + // is not used is initialised with -1 to signal that this edge counter has to + // be calculated from other edge counters on reading the profile info back + // in. + const Type *Int32 = Type::getInt32Ty(M.getContext()); const ArrayType *ATy = ArrayType::get(Int32, NumEdges); GlobalVariable *Counters = @@ -112,13 +127,23 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { if (F->isDeclaration()) continue; DEBUG(errs()<<"Working on "<<F->getNameStr()<<"\n"); - PI = &getAnalysisID<ProfileInfo>(ProfileEstimatorPassID,*F); - MaximumSpanningTree MST = MaximumSpanningTree(&(*F),PI,true); + // Calculate a Maximum Spanning Tree with the edge weights determined by + // ProfileEstimator. ProfileEstimator also assign weights to the virtual + // edges (0,entry) and (BB,0) (for blocks with no successors) and this + // edges also participate in the maximum spanning tree calculation. + // The third parameter of MaximumSpanningTree() has the effect that not the + // actual MST is returned but the edges _not_ in the MST. + + PI = &getAnalysisID<ProfileInfo>(ProfileEstimatorPassID, *F); + MaximumSpanningTree MST = MaximumSpanningTree(&(*F), PI, true); + + // Check if (0,entry) not in the MST. If not, instrument edge + // (IncrementCounterInBlock()) and set the counter initially to zero, if + // the edge is in the MST the counter is initialised to -1. - // Create counter for (0,entry) edge. BasicBlock *entry = &(F->getEntryBlock()); ProfileInfo::Edge edge = ProfileInfo::getEdge(0,entry); - if (std::binary_search(MST.begin(),MST.end(),edge)) { + if (std::binary_search(MST.begin(), MST.end(), edge)) { printEdgeCounter(edge,entry,i); IncrementCounterInBlock(entry, i, Counters); NumEdgesInserted++; Initializer[i++] = (zeroc); @@ -127,15 +152,17 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { } for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - if (!BlocksToInstrument.count(BB)) continue; // Don't count new blocks + // Do not count blocks that where introduced by spliting critical edges. + if (!BlocksToInstrument.count(BB)) continue; + // Okay, we have to add a counter of each outgoing edge not in MST. If // the outgoing edge is not critical don't split it, just insert the - // counter in the source or destination of the edge. + // counter in the source or destination of the edge. Also, if the block + // has no successors, the virtual edge (BB,0) is processed. TerminatorInst *TI = BB->getTerminator(); if (TI->getNumSuccessors() == 0) { - // Create counter for (BB,0), edge. ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,0); - if (std::binary_search(MST.begin(),MST.end(),edge)) { + if (std::binary_search(MST.begin(), MST.end(), edge)) { printEdgeCounter(edge,BB,i); IncrementCounterInBlock(BB, i, Counters); NumEdgesInserted++; Initializer[i++] = (zeroc); @@ -146,14 +173,14 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { BasicBlock *Succ = TI->getSuccessor(s); ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,Succ); - if (std::binary_search(MST.begin(),MST.end(),edge)) { + if (std::binary_search(MST.begin(), MST.end(), edge)) { // If the edge is critical, split it. SplitCriticalEdge(TI,s,this); Succ = TI->getSuccessor(s); - // Okay, we are guaranteed that the edge is no longer critical. If we - // only have a single successor, insert the counter in this block, + // Okay, we are guaranteed that the edge is no longer critical. If + // we only have a single successor, insert the counter in this block, // otherwise insert it in the successor block. if (TI->getNumSuccessors() == 1) { // Insert counter at the start of the block @@ -172,10 +199,11 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { } } - // check if indeed all counters have been used + // Check if the number of edges counted at first was the number of edges we + // considered for instrumentation. assert(i==NumEdges && "the number of edges in counting array is wrong"); - // assign initialiser to array + // Assing the now completely defined initialiser to the array. Constant *init = ConstantArray::get(ATy, Initializer); Counters->setInitializer(init); |