EdgeProfiling.cpp revision 081c34b725980f995be9080eaec24cd3dfaaf065
1//===- EdgeProfiling.cpp - Insert counters for 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// Note that this implementation is very naive. We insert a counter for *every* 15// edge in the program, instead of using control flow information to prune the 16// number of counters inserted. 17// 18//===----------------------------------------------------------------------===// 19#define DEBUG_TYPE "insert-edge-profiling" 20#include "ProfilingUtils.h" 21#include "llvm/Module.h" 22#include "llvm/Pass.h" 23#include "llvm/Support/raw_ostream.h" 24#include "llvm/Transforms/Utils/BasicBlockUtils.h" 25#include "llvm/Transforms/Instrumentation.h" 26#include "llvm/ADT/Statistic.h" 27#include <set> 28using namespace llvm; 29 30STATISTIC(NumEdgesInserted, "The # of edges inserted."); 31 32namespace { 33 class EdgeProfiler : public ModulePass { 34 bool runOnModule(Module &M); 35 public: 36 static char ID; // Pass identification, replacement for typeid 37 EdgeProfiler() : ModulePass(ID) { 38 initializeEdgeProfilerPass(*PassRegistry::getPassRegistry()); 39 } 40 41 virtual const char *getPassName() const { 42 return "Edge Profiler"; 43 } 44 }; 45} 46 47char EdgeProfiler::ID = 0; 48INITIALIZE_PASS(EdgeProfiler, "insert-edge-profiling", 49 "Insert instrumentation for edge profiling", false, false) 50 51ModulePass *llvm::createEdgeProfilerPass() { return new EdgeProfiler(); } 52 53bool EdgeProfiler::runOnModule(Module &M) { 54 Function *Main = M.getFunction("main"); 55 if (Main == 0) { 56 errs() << "WARNING: cannot insert edge profiling into a module" 57 << " with no main function!\n"; 58 return false; // No main, no instrumentation! 59 } 60 61 std::set<BasicBlock*> BlocksToInstrument; 62 unsigned NumEdges = 0; 63 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 64 if (F->isDeclaration()) continue; 65 // Reserve space for (0,entry) edge. 66 ++NumEdges; 67 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 68 // Keep track of which blocks need to be instrumented. We don't want to 69 // instrument blocks that are added as the result of breaking critical 70 // edges! 71 BlocksToInstrument.insert(BB); 72 NumEdges += BB->getTerminator()->getNumSuccessors(); 73 } 74 } 75 76 const Type *ATy = ArrayType::get(Type::getInt32Ty(M.getContext()), NumEdges); 77 GlobalVariable *Counters = 78 new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, 79 Constant::getNullValue(ATy), "EdgeProfCounters"); 80 NumEdgesInserted = NumEdges; 81 82 // Instrument all of the edges... 83 unsigned i = 0; 84 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 85 if (F->isDeclaration()) continue; 86 // Create counter for (0,entry) edge. 87 IncrementCounterInBlock(&F->getEntryBlock(), i++, Counters); 88 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 89 if (BlocksToInstrument.count(BB)) { // Don't instrument inserted blocks 90 // Okay, we have to add a counter of each outgoing edge. If the 91 // outgoing edge is not critical don't split it, just insert the counter 92 // in the source or destination of the edge. 93 TerminatorInst *TI = BB->getTerminator(); 94 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { 95 // If the edge is critical, split it. 96 SplitCriticalEdge(TI, s, this); 97 98 // Okay, we are guaranteed that the edge is no longer critical. If we 99 // only have a single successor, insert the counter in this block, 100 // otherwise insert it in the successor block. 101 if (TI->getNumSuccessors() == 1) { 102 // Insert counter at the start of the block 103 IncrementCounterInBlock(BB, i++, Counters); 104 } else { 105 // Insert counter at the start of the block 106 IncrementCounterInBlock(TI->getSuccessor(s), i++, Counters); 107 } 108 } 109 } 110 } 111 112 // Add the initialization call to main. 113 InsertProfilingInitCall(Main, "llvm_start_edge_profiling", Counters); 114 return true; 115} 116 117