OptimalEdgeProfiling.cpp revision 39859438715fc8f9ff16d7cec6cf2a9cb2ac0803
1//===- OptimalEdgeProfiling.cpp - Insert counters for opt. edge profiling -===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass instruments the specified program with counters for edge profiling. 11// Edge profiling can give a reasonable approximation of the hot paths through a 12// program, and is used for a wide variety of program transformations. 13// 14//===----------------------------------------------------------------------===// 15#define DEBUG_TYPE "insert-optimal-edge-profiling" 16#include "ProfilingUtils.h" 17#include "llvm/Module.h" 18#include "llvm/Pass.h" 19#include "llvm/Analysis/Passes.h" 20#include "llvm/Support/Compiler.h" 21#include "llvm/Support/raw_ostream.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Transforms/Utils/BasicBlockUtils.h" 24#include "llvm/Transforms/Instrumentation.h" 25#include "llvm/ADT/DenseSet.h" 26#include "llvm/ADT/Statistic.h" 27#include "MaximumSpanningTree.h" 28#include <set> 29using namespace llvm; 30 31STATISTIC(NumEdgesInserted, "The # of edges inserted."); 32 33namespace { 34 class VISIBILITY_HIDDEN OptimalEdgeProfiler : public ModulePass { 35 bool runOnModule(Module &M); 36 public: 37 static char ID; // Pass identification, replacement for typeid 38 OptimalEdgeProfiler() : ModulePass(&ID) {} 39 40 void getAnalysisUsage(AnalysisUsage &AU) const { 41 AU.addRequiredID(ProfileEstimatorPassID); 42 AU.addRequired<ProfileInfo>(); 43 } 44 45 virtual const char *getPassName() const { 46 return "Optimal Edge Profiler"; 47 } 48 }; 49} 50 51char OptimalEdgeProfiler::ID = 0; 52static RegisterPass<OptimalEdgeProfiler> 53X("insert-optimal-edge-profiling", 54 "Insert optimal instrumentation for edge profiling"); 55 56ModulePass *llvm::createOptimalEdgeProfilerPass() { 57 return new OptimalEdgeProfiler(); 58} 59 60inline static void printEdgeCounter(ProfileInfo::Edge e, 61 BasicBlock* b, 62 unsigned i) { 63 DEBUG(errs() << "--Edge Counter for " << (e) << " in " \ 64 << ((b)?(b)->getNameStr():"0") << " (# " << (i) << ")\n"); 65} 66 67bool OptimalEdgeProfiler::runOnModule(Module &M) { 68 Function *Main = M.getFunction("main"); 69 if (Main == 0) { 70 errs() << "WARNING: cannot insert edge profiling into a module" 71 << " with no main function!\n"; 72 return false; // No main, no instrumentation! 73 } 74 75 // NumEdges counts all the edges that may be instrumented. Later on its 76 // decided which edges to actually instrument, to achieve optimal profiling. 77 // For the entry block a virtual edge (0,entry) is reserved, for each block 78 // with no successors an edge (BB,0) is reserved. These edges are necessary 79 // to calculate a truly optimal maximum spanning tree and thus an optimal 80 // instrumentation. 81 unsigned NumEdges = 0; 82 83 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 84 if (F->isDeclaration()) continue; 85 // Reserve space for (0,entry) edge. 86 ++NumEdges; 87 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 88 // Keep track of which blocks need to be instrumented. We don't want to 89 // instrument blocks that are added as the result of breaking critical 90 // edges! 91 if (BB->getTerminator()->getNumSuccessors() == 0) { 92 // Reserve space for (BB,0) edge. 93 ++NumEdges; 94 } else { 95 NumEdges += BB->getTerminator()->getNumSuccessors(); 96 } 97 } 98 } 99 100 // In the profiling output a counter for each edge is reserved, but only few 101 // are used. This is done to be able to read back in the profile without 102 // calulating the maximum spanning tree again, instead each edge counter that 103 // is not used is initialised with -1 to signal that this edge counter has to 104 // be calculated from other edge counters on reading the profile info back 105 // in. 106 107 const Type *Int32 = Type::getInt32Ty(M.getContext()); 108 const ArrayType *ATy = ArrayType::get(Int32, NumEdges); 109 GlobalVariable *Counters = 110 new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, 111 Constant::getNullValue(ATy), "OptEdgeProfCounters"); 112 NumEdgesInserted = 0; 113 114 std::vector<Constant*> Initializer(NumEdges); 115 Constant* zeroc = ConstantInt::get(Int32, 0); 116 Constant* minusonec = ConstantInt::get(Int32, ProfileInfo::MissingValue); 117 118 // Instrument all of the edges not in MST... 119 unsigned i = 0; 120 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 121 if (F->isDeclaration()) continue; 122 DEBUG(errs()<<"Working on "<<F->getNameStr()<<"\n"); 123 124 // Calculate a Maximum Spanning Tree with the edge weights determined by 125 // ProfileEstimator. ProfileEstimator also assign weights to the virtual 126 // edges (0,entry) and (BB,0) (for blocks with no successors) and this 127 // edges also participate in the maximum spanning tree calculation. 128 // The third parameter of MaximumSpanningTree() has the effect that not the 129 // actual MST is returned but the edges _not_ in the MST. 130 131 ProfileInfo::EdgeWeights ECs = 132 getAnalysisID<ProfileInfo>(ProfileEstimatorPassID, *F).getEdgeWeights(F); 133 std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end()); 134 MaximumSpanningTree MST = MaximumSpanningTree(EdgeVector); 135 136 // Check if (0,entry) not in the MST. If not, instrument edge 137 // (IncrementCounterInBlock()) and set the counter initially to zero, if 138 // the edge is in the MST the counter is initialised to -1. 139 140 BasicBlock *entry = &(F->getEntryBlock()); 141 ProfileInfo::Edge edge = ProfileInfo::getEdge(0,entry); 142 if (!std::binary_search(MST.begin(), MST.end(), edge)) { 143 printEdgeCounter(edge,entry,i); 144 IncrementCounterInBlock(entry, i, Counters); NumEdgesInserted++; 145 Initializer[i++] = (zeroc); 146 } else{ 147 Initializer[i++] = (minusonec); 148 } 149 150 // InsertedBlocks contains all blocks that were inserted for splitting an 151 // edge, this blocks do not have to be instrumented. 152 DenseSet<BasicBlock*> InsertedBlocks; 153 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 154 // Check if block was not inserted and thus does not have to be 155 // instrumented. 156 if (InsertedBlocks.count(BB)) continue; 157 158 // Okay, we have to add a counter of each outgoing edge not in MST. If 159 // the outgoing edge is not critical don't split it, just insert the 160 // counter in the source or destination of the edge. Also, if the block 161 // has no successors, the virtual edge (BB,0) is processed. 162 TerminatorInst *TI = BB->getTerminator(); 163 if (TI->getNumSuccessors() == 0) { 164 ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,0); 165 if (!std::binary_search(MST.begin(), MST.end(), edge)) { 166 printEdgeCounter(edge,BB,i); 167 IncrementCounterInBlock(BB, i, Counters); NumEdgesInserted++; 168 Initializer[i++] = (zeroc); 169 } else{ 170 Initializer[i++] = (minusonec); 171 } 172 } 173 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { 174 BasicBlock *Succ = TI->getSuccessor(s); 175 ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,Succ); 176 if (!std::binary_search(MST.begin(), MST.end(), edge)) { 177 178 // If the edge is critical, split it. 179 bool wasInserted = SplitCriticalEdge(TI, s, this); 180 Succ = TI->getSuccessor(s); 181 if (wasInserted) 182 InsertedBlocks.insert(Succ); 183 184 // Okay, we are guaranteed that the edge is no longer critical. If 185 // we only have a single successor, insert the counter in this block, 186 // otherwise insert it in the successor block. 187 if (TI->getNumSuccessors() == 1) { 188 // Insert counter at the start of the block 189 printEdgeCounter(edge,BB,i); 190 IncrementCounterInBlock(BB, i, Counters); NumEdgesInserted++; 191 } else { 192 // Insert counter at the start of the block 193 printEdgeCounter(edge,Succ,i); 194 IncrementCounterInBlock(Succ, i, Counters); NumEdgesInserted++; 195 } 196 Initializer[i++] = (zeroc); 197 } else { 198 Initializer[i++] = (minusonec); 199 } 200 } 201 } 202 } 203 204 // Check if the number of edges counted at first was the number of edges we 205 // considered for instrumentation. 206 assert(i==NumEdges && "the number of edges in counting array is wrong"); 207 208 // Assing the now completely defined initialiser to the array. 209 Constant *init = ConstantArray::get(ATy, Initializer); 210 Counters->setInitializer(init); 211 212 // Add the initialization call to main. 213 InsertProfilingInitCall(Main, "llvm_start_opt_edge_profiling", Counters); 214 return true; 215} 216 217