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