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