1b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner//===- EdgeProfiling.cpp - Insert counters for edge profiling -------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// The LLVM Compiler Infrastructure 4b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner//===----------------------------------------------------------------------===// 9b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// 10b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// This pass instruments the specified program with counters for edge profiling. 11b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// Edge profiling can give a reasonable approximation of the hot paths through a 12b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// program, and is used for a wide variety of program transformations. 13b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// 14b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// Note that this implementation is very naive. We insert a counter for *every* 15b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// edge in the program, instead of using control flow information to prune the 16b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// number of counters inserted. 17b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner// 18b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner//===----------------------------------------------------------------------===// 1962353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter#define DEBUG_TYPE "insert-edge-profiling" 2004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 21e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling#include "ProfilingUtils.h" 22b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner#include "llvm/Module.h" 23b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner#include "llvm/Pass.h" 24cfa6ec92e61a1ab040c2b79db5de3a39df732ff6Benjamin Kramer#include "llvm/Support/raw_ostream.h" 25b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 26d9ed8c888016d15eded298c25bc8bdeffcb8d155Jeff Cohen#include "llvm/Transforms/Instrumentation.h" 2762353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter#include "llvm/ADT/Statistic.h" 28b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner#include <set> 29b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattnerusing namespace llvm; 30b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 3162353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas NeustifterSTATISTIC(NumEdgesInserted, "The # of edges inserted."); 3262353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter 33b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattnernamespace { 346726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class EdgeProfiler : public ModulePass { 35b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattner bool runOnModule(Module &M); 36794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel public: 37ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson EdgeProfiler() : ModulePass(ID) { 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeEdgeProfilerPass(*PassRegistry::getPassRegistry()); 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 4162353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter 4262353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter virtual const char *getPassName() const { 4362353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter return "Edge Profiler"; 4462353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter } 45b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner }; 46b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner} 47b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 48844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar EdgeProfiler::ID = 0; 49d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(EdgeProfiler, "insert-edge-profiling", 50ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Insert instrumentation for edge profiling", false, false) 51844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 52d9ed8c888016d15eded298c25bc8bdeffcb8d155Jeff CohenModulePass *llvm::createEdgeProfilerPass() { return new EdgeProfiler(); } 53d9ed8c888016d15eded298c25bc8bdeffcb8d155Jeff Cohen 54b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattnerbool EdgeProfiler::runOnModule(Module &M) { 55688b0490e22eb67623f5aaa24406209be74efcb2Reid Spencer Function *Main = M.getFunction("main"); 56b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner if (Main == 0) { 57cfa6ec92e61a1ab040c2b79db5de3a39df732ff6Benjamin Kramer errs() << "WARNING: cannot insert edge profiling into a module" 58cfa6ec92e61a1ab040c2b79db5de3a39df732ff6Benjamin Kramer << " with no main function!\n"; 59b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner return false; // No main, no instrumentation! 60b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner } 61b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 62b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner std::set<BasicBlock*> BlocksToInstrument; 63b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner unsigned NumEdges = 0; 64caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 65caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar if (F->isDeclaration()) continue; 66caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar // Reserve space for (0,entry) edge. 67caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar ++NumEdges; 68b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 69b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Keep track of which blocks need to be instrumented. We don't want to 70b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // instrument blocks that are added as the result of breaking critical 71b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // edges! 72b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner BlocksToInstrument.insert(BB); 73b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner NumEdges += BB->getTerminator()->getNumSuccessors(); 74b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner } 75caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar } 76b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 77db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ATy = ArrayType::get(Type::getInt32Ty(M.getContext()), NumEdges); 78b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner GlobalVariable *Counters = 79e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, 80a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant::getNullValue(ATy), "EdgeProfCounters"); 8162353a8d1323b42e4c28ea3a6f5cca39acac3195Andreas Neustifter NumEdgesInserted = NumEdges; 82b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 83b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Instrument all of the edges... 84b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner unsigned i = 0; 85caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 86caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar if (F->isDeclaration()) continue; 87caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar // Create counter for (0,entry) edge. 88caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar IncrementCounterInBlock(&F->getEntryBlock(), i++, Counters); 89b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 90b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner if (BlocksToInstrument.count(BB)) { // Don't instrument inserted blocks 91b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Okay, we have to add a counter of each outgoing edge. If the 92b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // outgoing edge is not critical don't split it, just insert the counter 93b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // in the source or destination of the edge. 94b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner TerminatorInst *TI = BB->getTerminator(); 95b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { 96b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // If the edge is critical, split it. 97b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner SplitCriticalEdge(TI, s, this); 98b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 99b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Okay, we are guaranteed that the edge is no longer critical. If we 100b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // only have a single successor, insert the counter in this block, 101b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // otherwise insert it in the successor block. 102915c656a745ea9a580ebb6a23cfe404d27e08d32Chris Lattner if (TI->getNumSuccessors() == 1) { 103b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Insert counter at the start of the block 10404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick IncrementCounterInBlock(BB, i++, Counters, false); 105b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner } else { 106b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Insert counter at the start of the block 107518310cb0d136906ff0a99d7a24cb460794de5bfReid Spencer IncrementCounterInBlock(TI->getSuccessor(s), i++, Counters); 108b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner } 109b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner } 110b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner } 111caaa49336b47b542d7255a8455fbab2e14a20ec5Daniel Dunbar } 112b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 113b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner // Add the initialization call to main. 114b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner InsertProfilingInitCall(Main, "llvm_start_edge_profiling", Counters); 115b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner return true; 116b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner} 117b2f12a2c38faaa1d0919b4ebb0b2bf3666fb672dChris Lattner 118