diff options
23 files changed, 3423 insertions, 51 deletions
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 64bd290..5b0c5b1 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -116,6 +116,28 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createPathProfileLoaderPass - This pass loads information from a path + // profile dump file. + // + ModulePass *createPathProfileLoaderPass(); + extern char &PathProfileLoaderPassID; + + //===--------------------------------------------------------------------===// + // + // createNoPathProfileInfoPass - This pass implements the default + // "no path profile". + // + ImmutablePass *createNoPathProfileInfoPass(); + + //===--------------------------------------------------------------------===// + // + // createPathProfileVerifierPass - This pass verifies path profiling + // information. + // + ModulePass *createPathProfileVerifierPass(); + + //===--------------------------------------------------------------------===// + // // createDSAAPass - This pass implements simple context sensitive alias // analysis. // @@ -140,7 +162,7 @@ namespace llvm { // createLiveValuesPass - This creates an instance of the LiveValues pass. // FunctionPass *createLiveValuesPass(); - + //===--------------------------------------------------------------------===// // /// createLazyValueInfoPass - This creates an instance of the LazyValueInfo @@ -153,7 +175,7 @@ namespace llvm { // LoopDependenceAnalysis pass. // LoopPass *createLoopDependenceAnalysisPass(); - + // Minor pass prototypes, allowing us to expose them through bugpoint and // analyze. FunctionPass *createInstCountPass(); diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h new file mode 100644 index 0000000..7025e28 --- /dev/null +++ b/include/llvm/Analysis/PathNumbering.h @@ -0,0 +1,304 @@ +//===- PathNumbering.h ----------------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Ball-Larus path numbers uniquely identify paths through a directed acyclic +// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony +// edges to obtain a DAG, and thus the unique path numbers [Ball96]. +// +// The purpose of this analysis is to enumerate the edges in a CFG in order +// to obtain paths from path numbers in a convenient manner. As described in +// [Ball96] edges can be enumerated such that given a path number by following +// the CFG and updating the path number, the path is obtained. +// +// [Ball96] +// T. Ball and J. R. Larus. "Efficient Path Profiling." +// International Symposium on Microarchitecture, pages 46-57, 1996. +// http://portal.acm.org/citation.cfm?id=243857 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_PATH_NUMBERING_H +#define LLVM_PATH_NUMBERING_H + +#include "llvm/BasicBlock.h" +#include "llvm/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Support/CFG.h" +#include "llvm/Analysis/ProfileInfoTypes.h" +#include <map> +#include <stack> +#include <vector> + +namespace llvm { +class BallLarusNode; +class BallLarusEdge; +class BallLarusDag; + +// typedefs for storage/ interators of various DAG components +typedef std::vector<BallLarusNode*> BLNodeVector; +typedef std::vector<BallLarusNode*>::iterator BLNodeIterator; +typedef std::vector<BallLarusEdge*> BLEdgeVector; +typedef std::vector<BallLarusEdge*>::iterator BLEdgeIterator; +typedef std::map<BasicBlock*, BallLarusNode*> BLBlockNodeMap; +typedef std::stack<BallLarusNode*> BLNodeStack; + +// Represents a basic block with information necessary for the BallLarus +// algorithms. +class BallLarusNode { +public: + enum NodeColor { WHITE, GRAY, BLACK }; + + // Constructor: Initializes a new Node for the given BasicBlock + BallLarusNode(BasicBlock* BB) : + _basicBlock(BB), _numberPaths(0), _color(WHITE) { + static unsigned nextUID = 0; + _uid = nextUID++; + } + + // Returns the basic block for the BallLarusNode + BasicBlock* getBlock(); + + // Get/set the number of paths to the exit starting at the node. + unsigned getNumberPaths(); + void setNumberPaths(unsigned numberPaths); + + // Get/set the NodeColor used in graph algorithms. + NodeColor getColor(); + void setColor(NodeColor color); + + // Iterator information for predecessor edges. Includes phony and + // backedges. + BLEdgeIterator predBegin(); + BLEdgeIterator predEnd(); + unsigned getNumberPredEdges(); + + // Iterator information for successor edges. Includes phony and + // backedges. + BLEdgeIterator succBegin(); + BLEdgeIterator succEnd(); + unsigned getNumberSuccEdges(); + + // Add an edge to the predecessor list. + void addPredEdge(BallLarusEdge* edge); + + // Remove an edge from the predecessor list. + void removePredEdge(BallLarusEdge* edge); + + // Add an edge to the successor list. + void addSuccEdge(BallLarusEdge* edge); + + // Remove an edge from the successor list. + void removeSuccEdge(BallLarusEdge* edge); + + // Returns the name of the BasicBlock being represented. If BasicBlock + // is null then returns "<null>". If BasicBlock has no name, then + // "<unnamed>" is returned. Intended for use with debug output. + std::string getName(); + +private: + // The corresponding underlying BB. + BasicBlock* _basicBlock; + + // Holds the predecessor edges of this node. + BLEdgeVector _predEdges; + + // Holds the successor edges of this node. + BLEdgeVector _succEdges; + + // The number of paths from the node to the exit. + unsigned _numberPaths; + + // 'Color' used by graph algorithms to mark the node. + NodeColor _color; + + // Unique ID to ensure naming difference with dotgraphs + unsigned _uid; + + // Removes an edge from an edgeVector. Used by removePredEdge and + // removeSuccEdge. + void removeEdge(BLEdgeVector& v, BallLarusEdge* e); +}; + +// Represents an edge in the Dag. For an edge, v -> w, v is the source, and +// w is the target. +class BallLarusEdge { +public: + enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE, + BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY }; + + // Constructor: Initializes an BallLarusEdge with a source and target. + BallLarusEdge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateNumber) + : _source(source), _target(target), _weight(0), _edgeType(NORMAL), + _realEdge(NULL), _duplicateNumber(duplicateNumber) {} + + // Returns the source/ target node of this edge. + BallLarusNode* getSource() const; + BallLarusNode* getTarget() const; + + // Sets the type of the edge. + EdgeType getType() const; + + // Gets the type of the edge. + void setType(EdgeType type); + + // Returns the weight of this edge. Used to decode path numbers to + // sequences of basic blocks. + unsigned getWeight(); + + // Sets the weight of the edge. Used during path numbering. + void setWeight(unsigned weight); + + // Gets/sets the phony edge originating at the root. + BallLarusEdge* getPhonyRoot(); + void setPhonyRoot(BallLarusEdge* phonyRoot); + + // Gets/sets the phony edge terminating at the exit. + BallLarusEdge* getPhonyExit(); + void setPhonyExit(BallLarusEdge* phonyExit); + + // Gets/sets the associated real edge if this is a phony edge. + BallLarusEdge* getRealEdge(); + void setRealEdge(BallLarusEdge* realEdge); + + // Returns the duplicate number of the edge. + unsigned getDuplicateNumber(); + +protected: + // Source node for this edge. + BallLarusNode* _source; + + // Target node for this edge. + BallLarusNode* _target; + +private: + // Edge weight cooresponding to path number increments before removing + // increments along a spanning tree. The sum over the edge weights gives + // the path number. + unsigned _weight; + + // Type to represent for what this edge is intended + EdgeType _edgeType; + + // For backedges and split-edges, the phony edge which is linked to the + // root node of the DAG. This contains a path number initialization. + BallLarusEdge* _phonyRoot; + + // For backedges and split-edges, the phony edge which is linked to the + // exit node of the DAG. This contains a path counter increment, and + // potentially a path number increment. + BallLarusEdge* _phonyExit; + + // If this is a phony edge, _realEdge is a link to the back or split + // edge. Otherwise, this is null. + BallLarusEdge* _realEdge; + + // An ID to differentiate between those edges which have the same source + // and destination blocks. + unsigned _duplicateNumber; +}; + +// Represents the Ball Larus DAG for a given Function. Can calculate +// various properties required for instrumentation or analysis. E.g. the +// edge weights that determine the path number. +class BallLarusDag { +public: + // Initializes a BallLarusDag from the CFG of a given function. Must + // call init() after creation, since some initialization requires + // virtual functions. + BallLarusDag(Function &F) + : _root(NULL), _exit(NULL), _function(F) {} + + // Initialization that requires virtual functions which are not fully + // functional in the constructor. + void init(); + + // Frees all memory associated with the DAG. + virtual ~BallLarusDag(); + + // Calculate the path numbers by assigning edge increments as prescribed + // in Ball-Larus path profiling. + void calculatePathNumbers(); + + // Returns the number of paths for the DAG. + unsigned getNumberOfPaths(); + + // Returns the root (i.e. entry) node for the DAG. + BallLarusNode* getRoot(); + + // Returns the exit node for the DAG. + BallLarusNode* getExit(); + + // Returns the function for the DAG. + Function& getFunction(); + + // Clears the node colors. + void clearColors(BallLarusNode::NodeColor color); + +protected: + // All nodes in the DAG. + BLNodeVector _nodes; + + // All edges in the DAG. + BLEdgeVector _edges; + + // All backedges in the DAG. + BLEdgeVector _backEdges; + + // Allows subclasses to determine which type of Node is created. + // Override this method to produce subclasses of BallLarusNode if + // necessary. The destructor of BallLarusDag will call free on each pointer + // created. + virtual BallLarusNode* createNode(BasicBlock* BB); + + // Allows subclasses to determine which type of Edge is created. + // Override this method to produce subclasses of BallLarusEdge if + // necessary. Parameters source and target will have been created by + // createNode and can be cast to the subclass of BallLarusNode* + // returned by createNode. The destructor of BallLarusDag will call free + // on each pointer created. + virtual BallLarusEdge* createEdge(BallLarusNode* source, BallLarusNode* + target, unsigned duplicateNumber); + + // Proxy to node's constructor. Updates the DAG state. + BallLarusNode* addNode(BasicBlock* BB); + + // Proxy to edge's constructor. Updates the DAG state. + BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateNumber); + +private: + // The root (i.e. entry) node for this DAG. + BallLarusNode* _root; + + // The exit node for this DAG. + BallLarusNode* _exit; + + // The function represented by this DAG. + Function& _function; + + // Processes one node and its imediate edges for building the DAG. + void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack); + + // Process an edge in the CFG for DAG building. + void buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack, + BallLarusNode* currentNode, BasicBlock* succBB, + unsigned duplicateNumber); + + // The weight on each edge is the increment required along any path that + // contains that edge. + void calculatePathNumbersFrom(BallLarusNode* node); + + // Adds a backedge with its phony edges. Updates the DAG state. + void addBackedge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateCount); +}; +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/PathProfileInfo.h b/include/llvm/Analysis/PathProfileInfo.h new file mode 100644 index 0000000..263763f --- /dev/null +++ b/include/llvm/Analysis/PathProfileInfo.h @@ -0,0 +1,113 @@ +//===- PathProfileInfo.h --------------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file outlines the interface used by optimizers to load path profiles. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_PATHPROFILEINFO_H +#define LLVM_PATHPROFILEINFO_H + +#include "llvm/BasicBlock.h" +#include "llvm/Analysis/PathNumbering.h" +#include <stack> + +namespace llvm { + +class ProfilePath; +class ProfilePathEdge; +class PathProfileInfo; + +typedef std::vector<ProfilePathEdge> ProfilePathEdgeVector; +typedef std::vector<ProfilePathEdge>::iterator ProfilePathEdgeIterator; + +typedef std::vector<BasicBlock*> ProfilePathBlockVector; +typedef std::vector<BasicBlock*>::iterator ProfilePathBlockIterator; + +typedef std::map<unsigned int,ProfilePath*> ProfilePathMap; +typedef std::map<unsigned int,ProfilePath*>::iterator ProfilePathIterator; + +typedef std::map<Function*,unsigned int> FunctionPathCountMap; +typedef std::map<Function*,ProfilePathMap> FunctionPathMap; +typedef std::map<Function*,ProfilePathMap>::iterator FunctionPathIterator; + +class ProfilePathEdge { +public: + ProfilePathEdge(BasicBlock* source, BasicBlock* target, + unsigned duplicateNumber); + + inline unsigned getDuplicateNumber() { return _duplicateNumber; } + inline BasicBlock* getSource() { return _source; } + inline BasicBlock* getTarget() { return _target; } + +protected: + BasicBlock* _source; + BasicBlock* _target; + unsigned _duplicateNumber; +}; + +class ProfilePath { +public: + ProfilePath(unsigned int number, unsigned int count, + double countStdDev, PathProfileInfo* ppi); + + double getFrequency() const; + + inline unsigned int getNumber() const { return _number; } + inline unsigned int getCount() const { return _count; } + inline double getCountStdDev() const { return _countStdDev; } + + ProfilePathEdgeVector* getPathEdges() const; + ProfilePathBlockVector* getPathBlocks() const; + + BasicBlock* getFirstBlockInPath() const; + +private: + unsigned int _number; + unsigned int _count; + double _countStdDev; + + // double pointer back to the profiling info + PathProfileInfo* _ppi; +}; + +// TODO: overload [] operator for getting path +// Add: getFunctionCallCount() +class PathProfileInfo { + public: + PathProfileInfo(); + ~PathProfileInfo(); + + void setCurrentFunction(Function* F); + Function* getCurrentFunction() const; + BasicBlock* getCurrentFunctionEntry(); + + ProfilePath* getPath(unsigned int number); + unsigned int getPotentialPathCount(); + + ProfilePathIterator pathBegin(); + ProfilePathIterator pathEnd(); + unsigned int pathsRun(); + + static char ID; // Pass identification + std::string argList; + +protected: + FunctionPathMap _functionPaths; + FunctionPathCountMap _functionPathCounts; + +private: + BallLarusDag* _currentDag; + Function* _currentFunction; + + friend class ProfilePath; +}; +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h index 0d531d5..f344af6 100644 --- a/include/llvm/Analysis/ProfileInfoTypes.h +++ b/include/llvm/Analysis/ProfileInfoTypes.h @@ -1,4 +1,4 @@ -/*===-- ProfileInfoTypes.h - Profiling info shared constants ------*- C -*-===*\ +/*===-- ProfileInfoTypes.h - Profiling info shared constants --------------===*\ |* |* The LLVM Compiler Infrastructure |* @@ -16,6 +16,17 @@ #ifndef LLVM_ANALYSIS_PROFILEINFOTYPES_H #define LLVM_ANALYSIS_PROFILEINFOTYPES_H +// Included by libprofile. +#if defined(__cplusplus) +extern "C" { +#endif + +/* IDs to distinguish between those path counters stored in hashses vs arrays */ +enum ProfilingStorageType { + ProfilingArray = 1, + ProfilingHash = 2 +}; + enum ProfilingType { ArgumentInfo = 1, /* The command line argument block */ FunctionInfo = 2, /* Function profiling information */ @@ -26,4 +37,24 @@ enum ProfilingType { OptEdgeInfo = 7 /* Edge profiling information, optimal version */ }; +/* + * The header for tables that map path numbers to path counters. + */ +typedef struct { + unsigned fnNumber; /* function number for these counters */ + unsigned numEntries; /* number of entries stored */ +} PathProfileHeader; + +/* + * Describes an entry in a tagged table for path counters. + */ +typedef struct { + unsigned pathNumber; + unsigned pathCounter; +} PathProfileTableEntry; + +#if defined(__cplusplus) +} +#endif + #endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */ diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 8aeb1c2..2a17c38 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -19,19 +19,19 @@ namespace llvm { class PassRegistry; -/// initializeCore - Initialize all passes linked into the +/// initializeCore - Initialize all passes linked into the /// TransformUtils library. void initializeCore(PassRegistry&); -/// initializeTransformUtils - Initialize all passes linked into the +/// initializeTransformUtils - Initialize all passes linked into the /// TransformUtils library. void initializeTransformUtils(PassRegistry&); -/// initializeScalarOpts - Initialize all passes linked into the +/// initializeScalarOpts - Initialize all passes linked into the /// ScalarOpts library. void initializeScalarOpts(PassRegistry&); -/// initializeInstCombine - Initialize all passes linked into the +/// initializeInstCombine - Initialize all passes linked into the /// ScalarOpts library. void initializeInstCombine(PassRegistry&); @@ -93,6 +93,7 @@ void initializeDominanceFrontierPass(PassRegistry&); void initializeDominatorTreePass(PassRegistry&); void initializeEdgeBundlesPass(PassRegistry&); void initializeEdgeProfilerPass(PassRegistry&); +void initializePathProfilerPass(PassRegistry&); void initializeEarlyCSEPass(PassRegistry&); void initializeExpandISelPseudosPass(PassRegistry&); void initializeFindUsedTypesPass(PassRegistry&); @@ -125,6 +126,7 @@ void initializeLiveStacksPass(PassRegistry&); void initializeLiveValuesPass(PassRegistry&); void initializeLiveVariablesPass(PassRegistry&); void initializeLoaderPassPass(PassRegistry&); +void initializePathProfileLoaderPassPass(PassRegistry&); void initializeLoopDeletionPass(PassRegistry&); void initializeLoopDependenceAnalysisPass(PassRegistry&); void initializeLoopExtractorPass(PassRegistry&); @@ -157,6 +159,7 @@ void initializeMergeFunctionsPass(PassRegistry&); void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeNoAAPass(PassRegistry&); void initializeNoProfileInfoPass(PassRegistry&); +void initializeNoPathProfileInfoPass(PassRegistry&); void initializeOptimalEdgeProfilerPass(PassRegistry&); void initializeOptimizePHIsPass(PassRegistry&); void initializePEIPass(PassRegistry&); @@ -177,6 +180,8 @@ void initializePrintModulePassPass(PassRegistry&); void initializeProcessImplicitDefsPass(PassRegistry&); void initializeProfileEstimatorPassPass(PassRegistry&); void initializeProfileInfoAnalysisGroup(PassRegistry&); +void initializePathProfileInfoAnalysisGroup(PassRegistry&); +void initializePathProfileVerifierPass(PassRegistry&); void initializeProfileVerifierPassPass(PassRegistry&); void initializePromotePassPass(PassRegistry&); void initializePruneEHPass(PassRegistry&); diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index a6f89c5..69e1bd9 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This header file pulls in all transformation and analysis passes for tools +// This header file pulls in all transformation and analysis passes for tools // like opt and bugpoint that need this functionality. // //===----------------------------------------------------------------------===// @@ -70,6 +70,7 @@ namespace { (void) llvm::createDomViewerPass(); (void) llvm::createEdgeProfilerPass(); (void) llvm::createOptimalEdgeProfilerPass(); + (void) llvm::createPathProfilerPass(); (void) llvm::createFunctionInliningPass(); (void) llvm::createAlwaysInlinerPass(); (void) llvm::createGlobalDCEPass(); @@ -99,7 +100,9 @@ namespace { (void) llvm::createNoProfileInfoPass(); (void) llvm::createProfileEstimatorPass(); (void) llvm::createProfileVerifierPass(); + (void) llvm::createPathProfileVerifierPass(); (void) llvm::createProfileLoaderPass(); + (void) llvm::createPathProfileLoaderPass(); (void) llvm::createPromoteMemoryToRegisterPass(); (void) llvm::createDemoteRegisterToMemoryPass(); (void) llvm::createPruneEHPass(); diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index 9c579ac..aa9873f 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -25,6 +25,9 @@ ModulePass *createEdgeProfilerPass(); // Insert optimal edge profiling instrumentation ModulePass *createOptimalEdgeProfilerPass(); +// Insert path profiling instrumentation +ModulePass *createPathProfilerPass(); + } // End llvm namespace #endif diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp index c948214..1af1c35 100644 --- a/lib/Analysis/Analysis.cpp +++ b/lib/Analysis/Analysis.cpp @@ -53,9 +53,13 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializePostDominanceFrontierPass(Registry); initializeProfileEstimatorPassPass(Registry); initializeNoProfileInfoPass(Registry); + initializeNoPathProfileInfoPass(Registry); initializeProfileInfoAnalysisGroup(Registry); + initializePathProfileInfoAnalysisGroup(Registry); initializeLoaderPassPass(Registry); + initializePathProfileLoaderPassPass(Registry); initializeProfileVerifierPassPass(Registry); + initializePathProfileVerifierPass(Registry); initializeRegionInfoPass(Registry); initializeRegionViewerPass(Registry); initializeRegionPrinterPass(Registry); @@ -73,14 +77,14 @@ void LLVMInitializeAnalysis(LLVMPassRegistryRef R) { LLVMBool LLVMVerifyModule(LLVMModuleRef M, LLVMVerifierFailureAction Action, char **OutMessages) { std::string Messages; - + LLVMBool Result = verifyModule(*unwrap(M), static_cast<VerifierFailureAction>(Action), OutMessages? &Messages : 0); - + if (OutMessages) *OutMessages = strdup(Messages.c_str()); - + return Result; } diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index a43cd37..1f43b44 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -33,6 +33,9 @@ add_llvm_library(LLVMAnalysis MemoryBuiltins.cpp MemoryDependenceAnalysis.cpp ModuleDebugInfoPrinter.cpp + PathNumbering.cpp + PathProfileInfo.cpp + PathProfileVerifier.cpp NoAliasAnalysis.cpp PHITransAddr.cpp PostDominators.cpp diff --git a/lib/Analysis/PathNumbering.cpp b/lib/Analysis/PathNumbering.cpp new file mode 100644 index 0000000..5d3f6bb --- /dev/null +++ b/lib/Analysis/PathNumbering.cpp @@ -0,0 +1,525 @@ +//===- PathNumbering.cpp --------------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Ball-Larus path numbers uniquely identify paths through a directed acyclic +// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony +// edges to obtain a DAG, and thus the unique path numbers [Ball96]. +// +// The purpose of this analysis is to enumerate the edges in a CFG in order +// to obtain paths from path numbers in a convenient manner. As described in +// [Ball96] edges can be enumerated such that given a path number by following +// the CFG and updating the path number, the path is obtained. +// +// [Ball96] +// T. Ball and J. R. Larus. "Efficient Path Profiling." +// International Symposium on Microarchitecture, pages 46-57, 1996. +// http://portal.acm.org/citation.cfm?id=243857 +// +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "ball-larus-numbering" + +#include "llvm/Analysis/PathNumbering.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/InstrTypes.h" +#include "llvm/Instructions.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/TypeBuilder.h" +#include "llvm/Support/raw_ostream.h" + +#include <map> +#include <queue> +#include <set> +#include <stack> +#include <string> +#include <utility> +#include <vector> +#include <sstream> + +using namespace llvm; + +// Are we enabling early termination +static cl::opt<bool> ProcessEarlyTermination( + "path-profile-early-termination", cl::Hidden, + cl::desc("In path profiling, insert extra instrumentation to account for " + "unexpected function termination.")); + +// Returns the basic block for the BallLarusNode +BasicBlock* BallLarusNode::getBlock() { + return(_basicBlock); +} + +// Returns the number of paths to the exit starting at the node. +unsigned BallLarusNode::getNumberPaths() { + return(_numberPaths); +} + +// Sets the number of paths to the exit starting at the node. +void BallLarusNode::setNumberPaths(unsigned numberPaths) { + _numberPaths = numberPaths; +} + +// Gets the NodeColor used in graph algorithms. +BallLarusNode::NodeColor BallLarusNode::getColor() { + return(_color); +} + +// Sets the NodeColor used in graph algorithms. +void BallLarusNode::setColor(BallLarusNode::NodeColor color) { + _color = color; +} + +// Returns an iterator over predecessor edges. Includes phony and +// backedges. +BLEdgeIterator BallLarusNode::predBegin() { + return(_predEdges.begin()); +} + +// Returns the end sentinel for the predecessor iterator. +BLEdgeIterator BallLarusNode::predEnd() { + return(_predEdges.end()); +} + +// Returns the number of predecessor edges. Includes phony and +// backedges. +unsigned BallLarusNode::getNumberPredEdges() { + return(_predEdges.size()); +} + +// Returns an iterator over successor edges. Includes phony and +// backedges. +BLEdgeIterator BallLarusNode::succBegin() { + return(_succEdges.begin()); +} + +// Returns the end sentinel for the successor iterator. +BLEdgeIterator BallLarusNode::succEnd() { + return(_succEdges.end()); +} + +// Returns the number of successor edges. Includes phony and +// backedges. +unsigned BallLarusNode::getNumberSuccEdges() { + return(_succEdges.size()); +} + +// Add an edge to the predecessor list. +void BallLarusNode::addPredEdge(BallLarusEdge* edge) { + _predEdges.push_back(edge); +} + +// Remove an edge from the predecessor list. +void BallLarusNode::removePredEdge(BallLarusEdge* edge) { + removeEdge(_predEdges, edge); +} + +// Add an edge to the successor list. +void BallLarusNode::addSuccEdge(BallLarusEdge* edge) { + _succEdges.push_back(edge); +} + +// Remove an edge from the successor list. +void BallLarusNode::removeSuccEdge(BallLarusEdge* edge) { + removeEdge(_succEdges, edge); +} + +// Returns the name of the BasicBlock being represented. If BasicBlock +// is null then returns "<null>". If BasicBlock has no name, then +// "<unnamed>" is returned. Intended for use with debug output. +std::string BallLarusNode::getName() { + std::stringstream name; + + if(getBlock() != NULL) { + if(getBlock()->hasName()) { + std::string tempName(getBlock()->getName()); + name << tempName.c_str() << " (" << _uid << ")"; + } else + name << "<unnamed> (" << _uid << ")"; + } else + name << "<null> (" << _uid << ")"; + + return name.str(); +} + +// Removes an edge from an edgeVector. Used by removePredEdge and +// removeSuccEdge. +void BallLarusNode::removeEdge(BLEdgeVector& v, BallLarusEdge* e) { + // TODO: Avoid linear scan by using a set instead + for(BLEdgeIterator i = v.begin(), + end = v.end(); + i != end; + ++i) { + if((*i) == e) { + v.erase(i); + break; + } + } +} + +// Returns the source node of this edge. +BallLarusNode* BallLarusEdge::getSource() const { + return(_source); +} + +// Returns the target node of this edge. +BallLarusNode* BallLarusEdge::getTarget() const { + return(_target); +} + +// Sets the type of the edge. +BallLarusEdge::EdgeType BallLarusEdge::getType() const { + return _edgeType; +} + +// Gets the type of the edge. +void BallLarusEdge::setType(EdgeType type) { + _edgeType = type; +} + +// Returns the weight of this edge. Used to decode path numbers to sequences +// of basic blocks. +unsigned BallLarusEdge::getWeight() { + return(_weight); +} + +// Sets the weight of the edge. Used during path numbering. +void BallLarusEdge::setWeight(unsigned weight) { + _weight = weight; +} + +// Gets the phony edge originating at the root. +BallLarusEdge* BallLarusEdge::getPhonyRoot() { + return _phonyRoot; +} + +// Sets the phony edge originating at the root. +void BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) { + _phonyRoot = phonyRoot; +} + +// Gets the phony edge terminating at the exit. +BallLarusEdge* BallLarusEdge::getPhonyExit() { + return _phonyExit; +} + +// Sets the phony edge terminating at the exit. +void BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) { + _phonyExit = phonyExit; +} + +// Gets the associated real edge if this is a phony edge. +BallLarusEdge* BallLarusEdge::getRealEdge() { + return _realEdge; +} + +// Sets the associated real edge if this is a phony edge. +void BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) { + _realEdge = realEdge; +} + +// Returns the duplicate number of the edge. +unsigned BallLarusEdge::getDuplicateNumber() { + return(_duplicateNumber); +} + +// Initialization that requires virtual functions which are not fully +// functional in the constructor. +void BallLarusDag::init() { + BLBlockNodeMap inDag; + std::stack<BallLarusNode*> dfsStack; + + _root = addNode(&(_function.getEntryBlock())); + _exit = addNode(NULL); + + // start search from root + dfsStack.push(getRoot()); + + // dfs to add each bb into the dag + while(dfsStack.size()) + buildNode(inDag, dfsStack); + + // put in the final edge + addEdge(getExit(),getRoot(),0); +} + +// Frees all memory associated with the DAG. +BallLarusDag::~BallLarusDag() { + for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); edge != end; + ++edge) + delete (*edge); + + for(BLNodeIterator node = _nodes.begin(), end = _nodes.end(); node != end; + ++node) + delete (*node); +} + +// Calculate the path numbers by assigning edge increments as prescribed +// in Ball-Larus path profiling. +void BallLarusDag::calculatePathNumbers() { + BallLarusNode* node; + std::queue<BallLarusNode*> bfsQueue; + bfsQueue.push(getExit()); + + while(bfsQueue.size() > 0) { + node = bfsQueue.front(); + + DEBUG(dbgs() << "calculatePathNumbers on " << node->getName() << "\n"); + + bfsQueue.pop(); + unsigned prevPathNumber = node->getNumberPaths(); + calculatePathNumbersFrom(node); + + // Check for DAG splitting + if( node->getNumberPaths() > 100000000 && node != getRoot() ) { + // Add new phony edge from the split-node to the DAG's exit + BallLarusEdge* exitEdge = addEdge(node, getExit(), 0); + exitEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); + + // Counters to handle the possibilty of a multi-graph + BasicBlock* oldTarget = 0; + unsigned duplicateNumber = 0; + + // Iterate through each successor edge, adding phony edges + for( BLEdgeIterator succ = node->succBegin(), end = node->succEnd(); + succ != end; oldTarget = (*succ)->getTarget()->getBlock(), succ++ ) { + + if( (*succ)->getType() == BallLarusEdge::NORMAL ) { + // is this edge a duplicate? + if( oldTarget != (*succ)->getTarget()->getBlock() ) + duplicateNumber = 0; + + // create the new phony edge: root -> succ + BallLarusEdge* rootEdge = + addEdge(getRoot(), (*succ)->getTarget(), duplicateNumber++); + rootEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); + rootEdge->setRealEdge(*succ); + + // split on this edge and reference it's exit/root phony edges + (*succ)->setType(BallLarusEdge::SPLITEDGE); + (*succ)->setPhonyRoot(rootEdge); + (*succ)->setPhonyExit(exitEdge); + (*succ)->setWeight(0); + } + } + + calculatePathNumbersFrom(node); + } + + DEBUG(dbgs() << "prev, new number paths " << prevPathNumber << ", " + << node->getNumberPaths() << ".\n"); + + if(prevPathNumber == 0 && node->getNumberPaths() != 0) { + DEBUG(dbgs() << "node ready : " << node->getName() << "\n"); + for(BLEdgeIterator pred = node->predBegin(), end = node->predEnd(); + pred != end; pred++) { + if( (*pred)->getType() == BallLarusEdge::BACKEDGE || + (*pred)->getType() == BallLarusEdge::SPLITEDGE ) + continue; + + BallLarusNode* nextNode = (*pred)->getSource(); + // not yet visited? + if(nextNode->getNumberPaths() == 0) + bfsQueue.push(nextNode); + } + } + } + + DEBUG(dbgs() << "\tNumber of paths: " << getRoot()->getNumberPaths() << "\n"); +} + +// Returns the number of paths for the Dag. +unsigned BallLarusDag::getNumberOfPaths() { + return(getRoot()->getNumberPaths()); +} + +// Returns the root (i.e. entry) node for the DAG. +BallLarusNode* BallLarusDag::getRoot() { + return _root; +} + +// Returns the exit node for the DAG. +BallLarusNode* BallLarusDag::getExit() { + return _exit; +} + +// Returns the function for the DAG. +Function& BallLarusDag::getFunction() { + return(_function); +} + +// Clears the node colors. +void BallLarusDag::clearColors(BallLarusNode::NodeColor color) { + for (BLNodeIterator nodeIt = _nodes.begin(); nodeIt != _nodes.end(); nodeIt++) + (*nodeIt)->setColor(color); +} + +// Processes one node and its imediate edges for building the DAG. +void BallLarusDag::buildNode(BLBlockNodeMap& inDag, BLNodeStack& dfsStack) { + BallLarusNode* currentNode = dfsStack.top(); + BasicBlock* currentBlock = currentNode->getBlock(); + + if(currentNode->getColor() != BallLarusNode::WHITE) { + // we have already visited this node + dfsStack.pop(); + currentNode->setColor(BallLarusNode::BLACK); + } else { + // are there any external procedure calls? + if( ProcessEarlyTermination ) { + for( BasicBlock::iterator bbCurrent = currentNode->getBlock()->begin(), + bbEnd = currentNode->getBlock()->end(); bbCurrent != bbEnd; + bbCurrent++ ) { + Instruction& instr = *bbCurrent; + if( instr.getOpcode() == Instruction::Call ) { + BallLarusEdge* callEdge = addEdge(currentNode, getExit(), 0); + callEdge->setType(BallLarusEdge::CALLEDGE_PHONY); + break; + } + } + } + + TerminatorInst* terminator = currentNode->getBlock()->getTerminator(); + if(isa<ReturnInst>(terminator) || isa<UnreachableInst>(terminator) + || isa<UnwindInst>(terminator)) + addEdge(currentNode, getExit(),0); + + currentNode->setColor(BallLarusNode::GRAY); + inDag[currentBlock] = currentNode; + + BasicBlock* oldSuccessor = 0; + unsigned duplicateNumber = 0; + + // iterate through this node's successors + for(succ_iterator successor = succ_begin(currentBlock), + succEnd = succ_end(currentBlock); successor != succEnd; + oldSuccessor = *successor, ++successor ) { + BasicBlock* succBB = *successor; + + // is this edge a duplicate? + if (oldSuccessor == succBB) + duplicateNumber++; + else + duplicateNumber = 0; + + buildEdge(inDag, dfsStack, currentNode, succBB, duplicateNumber); + } + } +} + +// Process an edge in the CFG for DAG building. +void BallLarusDag::buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& + dfsStack, BallLarusNode* currentNode, + BasicBlock* succBB, unsigned duplicateCount) { + BallLarusNode* succNode = inDag[succBB]; + + if(succNode && succNode->getColor() == BallLarusNode::BLACK) { + // visited node and forward edge + addEdge(currentNode, succNode, duplicateCount); + } else if(succNode && succNode->getColor() == BallLarusNode::GRAY) { + // visited node and back edge + DEBUG(dbgs() << "Backedge detected.\n"); + addBackedge(currentNode, succNode, duplicateCount); + } else { + BallLarusNode* childNode; + // not visited node and forward edge + if(succNode) // an unvisited node that is child of a gray node + childNode = succNode; + else { // an unvisited node that is a child of a an unvisted node + childNode = addNode(succBB); + inDag[succBB] = childNode; + } + addEdge(currentNode, childNode, duplicateCount); + dfsStack.push(childNode); + } +} + +// The weight on each edge is the increment required along any path that +// contains that edge. +void BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) { + if(node == getExit()) + // The Exit node must be base case + node->setNumberPaths(1); + else { + unsigned sumPaths = 0; + BallLarusNode* succNode; + + for(BLEdgeIterator succ = node->succBegin(), end = node->succEnd(); + succ != end; succ++) { + if( (*succ)->getType() == BallLarusEdge::BACKEDGE || + (*succ)->getType() == BallLarusEdge::SPLITEDGE ) + continue; + + (*succ)->setWeight(sumPaths); + succNode = (*succ)->getTarget(); + + if( !succNode->getNumberPaths() ) + return; + sumPaths += succNode->getNumberPaths(); + } + + node->setNumberPaths(sumPaths); + } +} + +// Allows subclasses to determine which type of Node is created. +// Override this method to produce subclasses of BallLarusNode if +// necessary. The destructor of BallLarusDag will call free on each +// pointer created. +BallLarusNode* BallLarusDag::createNode(BasicBlock* BB) { + return( new BallLarusNode(BB) ); +} + +// Allows subclasses to determine which type of Edge is created. +// Override this method to produce subclasses of BallLarusEdge if +// necessary. The destructor of BallLarusDag will call free on each +// pointer created. +BallLarusEdge* BallLarusDag::createEdge(BallLarusNode* source, + BallLarusNode* target, + unsigned duplicateCount) { + return( new BallLarusEdge(source, target, duplicateCount) ); +} + +// Proxy to node's constructor. Updates the DAG state. +BallLarusNode* BallLarusDag::addNode(BasicBlock* BB) { + BallLarusNode* newNode = createNode(BB); + _nodes.push_back(newNode); + return( newNode ); +} + +// Proxy to edge's constructor. Updates the DAG state. +BallLarusEdge* BallLarusDag::addEdge(BallLarusNode* source, + BallLarusNode* target, + unsigned duplicateCount) { + BallLarusEdge* newEdge = createEdge(source, target, duplicateCount); + _edges.push_back(newEdge); + source->addSuccEdge(newEdge); + target->addPredEdge(newEdge); + return(newEdge); +} + +// Adds a backedge with its phony edges. Updates the DAG state. +void BallLarusDag::addBackedge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateCount) { + BallLarusEdge* childEdge = addEdge(source, target, duplicateCount); + childEdge->setType(BallLarusEdge::BACKEDGE); + + childEdge->setPhonyRoot(addEdge(getRoot(), target,0)); + childEdge->setPhonyExit(addEdge(source, getExit(),0)); + + childEdge->getPhonyRoot()->setRealEdge(childEdge); + childEdge->getPhonyRoot()->setType(BallLarusEdge::BACKEDGE_PHONY); + + childEdge->getPhonyExit()->setRealEdge(childEdge); + childEdge->getPhonyExit()->setType(BallLarusEdge::BACKEDGE_PHONY); + _backEdges.push_back(childEdge); +} diff --git a/lib/Analysis/PathProfileInfo.cpp b/lib/Analysis/PathProfileInfo.cpp new file mode 100644 index 0000000..b361d3f --- /dev/null +++ b/lib/Analysis/PathProfileInfo.cpp @@ -0,0 +1,434 @@ +//===- PathProfileInfo.cpp ------------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the interface used by optimizers to load path profiles, +// and provides a loader pass which reads a path profile file. +// +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "path-profile-info" + +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/ProfileInfoTypes.h" +#include "llvm/Analysis/PathProfileInfo.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +#include <cstdio> + +using namespace llvm; + +// command line option for loading path profiles +static cl::opt<std::string> +PathProfileInfoFilename("path-profile-loader-file", cl::init("llvmprof.out"), + cl::value_desc("filename"), + cl::desc("Path profile file loaded by -path-profile-loader"), cl::Hidden); + +namespace { + class PathProfileLoaderPass : public ModulePass, public PathProfileInfo { + public: + PathProfileLoaderPass() : ModulePass(ID) { } + ~PathProfileLoaderPass(); + + // this pass doesn't change anything (only loads information) + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } + + // the full name of the loader pass + virtual const char* getPassName() const { + return "Path Profiling Information Loader"; + } + + // required since this pass implements multiple inheritance + virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { + if (PI == &PathProfileInfo::ID) + return (PathProfileInfo*)this; + return this; + } + + // entry point to run the pass + bool runOnModule(Module &M); + + // pass identification + static char ID; + + private: + // make a reference table to refer to function by number + void buildFunctionRefs(Module &M); + + // process argument info of a program from the input file + void handleArgumentInfo(); + + // process path number information from the input file + void handlePathInfo(); + + // array of references to the functions in the module + std::vector<Function*> _functions; + + // path profile file handle + FILE* _file; + + // path profile file name + std::string _filename; + }; +} + +// register PathLoader +char PathProfileLoaderPass::ID = 0; + +INITIALIZE_ANALYSIS_GROUP(PathProfileInfo, "Path Profile Information", + NoPathProfileInfo) +INITIALIZE_AG_PASS(PathProfileLoaderPass, PathProfileInfo, + "path-profile-loader", + "Load path profile information from file", + false, true, false) + +char &llvm::PathProfileLoaderPassID = PathProfileLoaderPass::ID; + +// link PathLoader as a pass, and make it available as an optimisation +ModulePass *llvm::createPathProfileLoaderPass() { + return new PathProfileLoaderPass; +} + +// ---------------------------------------------------------------------------- +// PathEdge implementation +// +ProfilePathEdge::ProfilePathEdge (BasicBlock* source, BasicBlock* target, + unsigned duplicateNumber) + : _source(source), _target(target), _duplicateNumber(duplicateNumber) {} + +// ---------------------------------------------------------------------------- +// Path implementation +// + +ProfilePath::ProfilePath (unsigned int number, unsigned int count, + double countStdDev, PathProfileInfo* ppi) + : _number(number) , _count(count), _countStdDev(countStdDev), _ppi(ppi) {} + +double ProfilePath::getFrequency() const { + return 100 * double(_count) / + double(_ppi->_functionPathCounts[_ppi->_currentFunction]); +} + +static BallLarusEdge* getNextEdge (BallLarusNode* node, + unsigned int pathNumber) { + BallLarusEdge* best = 0; + + for( BLEdgeIterator next = node->succBegin(), + end = node->succEnd(); next != end; next++ ) { + if( (*next)->getType() != BallLarusEdge::BACKEDGE && // no backedges + (*next)->getType() != BallLarusEdge::SPLITEDGE && // no split edges + (*next)->getWeight() <= pathNumber && // weight must be <= pathNumber + (!best || (best->getWeight() < (*next)->getWeight())) ) // best one? + best = *next; + } + + return best; +} + +ProfilePathEdgeVector* ProfilePath::getPathEdges() const { + BallLarusNode* currentNode = _ppi->_currentDag->getRoot (); + unsigned int increment = _number; + ProfilePathEdgeVector* pev = new ProfilePathEdgeVector; + + while (currentNode != _ppi->_currentDag->getExit()) { + BallLarusEdge* next = getNextEdge(currentNode, increment); + + increment -= next->getWeight(); + + if( next->getType() != BallLarusEdge::BACKEDGE_PHONY && + next->getType() != BallLarusEdge::SPLITEDGE_PHONY && + next->getTarget() != _ppi->_currentDag->getExit() ) + pev->push_back(ProfilePathEdge( + next->getSource()->getBlock(), + next->getTarget()->getBlock(), + next->getDuplicateNumber())); + + if( next->getType() == BallLarusEdge::BACKEDGE_PHONY && + next->getTarget() == _ppi->_currentDag->getExit() ) + pev->push_back(ProfilePathEdge( + next->getRealEdge()->getSource()->getBlock(), + next->getRealEdge()->getTarget()->getBlock(), + next->getDuplicateNumber())); + + if( next->getType() == BallLarusEdge::SPLITEDGE_PHONY && + next->getSource() == _ppi->_currentDag->getRoot() ) + pev->push_back(ProfilePathEdge( + next->getRealEdge()->getSource()->getBlock(), + next->getRealEdge()->getTarget()->getBlock(), + next->getDuplicateNumber())); + + // set the new node + currentNode = next->getTarget(); + } + + return pev; +} + +ProfilePathBlockVector* ProfilePath::getPathBlocks() const { + BallLarusNode* currentNode = _ppi->_currentDag->getRoot (); + unsigned int increment = _number; + ProfilePathBlockVector* pbv = new ProfilePathBlockVector; + + while (currentNode != _ppi->_currentDag->getExit()) { + BallLarusEdge* next = getNextEdge(currentNode, increment); + increment -= next->getWeight(); + + // add block to the block list if it is a real edge + if( next->getType() == BallLarusEdge::NORMAL) + pbv->push_back (currentNode->getBlock()); + // make the back edge the last edge since we are at the end + else if( next->getTarget() == _ppi->_currentDag->getExit() ) { + pbv->push_back (currentNode->getBlock()); + pbv->push_back (next->getRealEdge()->getTarget()->getBlock()); + } + + // set the new node + currentNode = next->getTarget(); + } + + return pbv; +} + +BasicBlock* ProfilePath::getFirstBlockInPath() const { + BallLarusNode* root = _ppi->_currentDag->getRoot(); + BallLarusEdge* edge = getNextEdge(root, _number); + + if( edge && (edge->getType() == BallLarusEdge::BACKEDGE_PHONY || + edge->getType() == BallLarusEdge::SPLITEDGE_PHONY) ) + return edge->getTarget()->getBlock(); + + return root->getBlock(); +} + +// ---------------------------------------------------------------------------- +// PathProfileInfo implementation +// + +// Pass identification +char llvm::PathProfileInfo::ID = 0; + +PathProfileInfo::PathProfileInfo () : _currentDag(0) , _currentFunction(0) { +} + +PathProfileInfo::~PathProfileInfo() { + if (_currentDag) + delete _currentDag; +} + +// set the function for which paths are currently begin processed +void PathProfileInfo::setCurrentFunction(Function* F) { + // Make sure it exists + if (!F) return; + + if (_currentDag) + delete _currentDag; + + _currentFunction = F; + _currentDag = new BallLarusDag(*F); + _currentDag->init(); + _currentDag->calculatePathNumbers(); +} + +// get the function for which paths are currently being processed +Function* PathProfileInfo::getCurrentFunction() const { + return _currentFunction; +} + +// get the entry block of the function +BasicBlock* PathProfileInfo::getCurrentFunctionEntry() { + return _currentDag->getRoot()->getBlock(); +} + +// return the path based on its number +ProfilePath* PathProfileInfo::getPath(unsigned int number) { + return _functionPaths[_currentFunction][number]; +} + +// return the number of paths which a function may potentially execute +unsigned int PathProfileInfo::getPotentialPathCount() { + return _currentDag ? _currentDag->getNumberOfPaths() : 0; +} + +// return an iterator for the beginning of a functions executed paths +ProfilePathIterator PathProfileInfo::pathBegin() { + return _functionPaths[_currentFunction].begin(); +} + +// return an iterator for the end of a functions executed paths +ProfilePathIterator PathProfileInfo::pathEnd() { + return _functionPaths[_currentFunction].end(); +} + +// returns the total number of paths run in the function +unsigned int PathProfileInfo::pathsRun() { + return _currentFunction ? _functionPaths[_currentFunction].size() : 0; +} + +// ---------------------------------------------------------------------------- +// PathLoader implementation +// + +// remove all generated paths +PathProfileLoaderPass::~PathProfileLoaderPass() { + for( FunctionPathIterator funcNext = _functionPaths.begin(), + funcEnd = _functionPaths.end(); funcNext != funcEnd; funcNext++) + for( ProfilePathIterator pathNext = funcNext->second.begin(), + pathEnd = funcNext->second.end(); pathNext != pathEnd; pathNext++) + delete pathNext->second; +} + +// entry point of the pass; this loads and parses a file +bool PathProfileLoaderPass::runOnModule(Module &M) { + // get the filename and setup the module's function references + _filename = PathProfileInfoFilename; + buildFunctionRefs (M); + + if (!(_file = fopen(_filename.c_str(), "rb"))) { + errs () << "error: input '" << _filename << "' file does not exist.\n"; + return false; + } + + ProfilingType profType; + + while( fread(&profType, sizeof(ProfilingType), 1, _file) ) { + switch (profType) { + case ArgumentInfo: + handleArgumentInfo (); + break; + case PathInfo: + handlePathInfo (); + break; + default: + errs () << "error: bad path profiling file syntax, " << profType << "\n"; + fclose (_file); + return false; + } + } + + fclose (_file); + + return true; +} + +// create a reference table for functions defined in the path profile file +void PathProfileLoaderPass::buildFunctionRefs (Module &M) { + _functions.push_back(0); // make the 0 index a null pointer + + for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) { + if (F->isDeclaration()) + continue; + _functions.push_back(F); + } +} + +// handle command like argument infor in the output file +void PathProfileLoaderPass::handleArgumentInfo() { + // get the argument list's length + unsigned savedArgsLength; + if( fread(&savedArgsLength, sizeof(unsigned), 1, _file) != 1 ) { + errs() << "warning: argument info header/data mismatch\n"; + return; + } + + // allocate a buffer, and get the arguments + char* args = new char[savedArgsLength+1]; + if( fread(args, 1, savedArgsLength, _file) != savedArgsLength ) + errs() << "warning: argument info header/data mismatch\n"; + + args[savedArgsLength] = '\0'; + argList = std::string(args); + delete [] args; // cleanup dynamic string + + // byte alignment + if (savedArgsLength & 3) + fseek(_file, 4-(savedArgsLength&3), SEEK_CUR); +} + +// Handle path profile information in the output file +void PathProfileLoaderPass::handlePathInfo () { + // get the number of functions in this profile + unsigned functionCount; + if( fread(&functionCount, sizeof(functionCount), 1, _file) != 1 ) { + errs() << "warning: path info header/data mismatch\n"; + return; + } + + // gather path information for each function + for (unsigned i = 0; i < functionCount; i++) { + PathProfileHeader pathHeader; + if( fread(&pathHeader, sizeof(pathHeader), 1, _file) != 1 ) { + errs() << "warning: bad header for path function info\n"; + break; + } + + Function* f = _functions[pathHeader.fnNumber]; + + // dynamically allocate a table to store path numbers + PathProfileTableEntry* pathTable = + new PathProfileTableEntry[pathHeader.numEntries]; + + if( fread(pathTable, sizeof(PathProfileTableEntry), + pathHeader.numEntries, _file) != pathHeader.numEntries) { + delete [] pathTable; + errs() << "warning: path function info header/data mismatch\n"; + return; + } + + // Build a new path for the current function + unsigned int totalPaths = 0; + for (unsigned int j = 0; j < pathHeader.numEntries; j++) { + totalPaths += pathTable[j].pathCounter; + _functionPaths[f][pathTable[j].pathNumber] + = new ProfilePath(pathTable[j].pathNumber, pathTable[j].pathCounter, + 0, this); + } + + _functionPathCounts[f] = totalPaths; + + delete [] pathTable; + } +} + +//===----------------------------------------------------------------------===// +// NoProfile PathProfileInfo implementation +// + +namespace { + struct NoPathProfileInfo : public ImmutablePass, public PathProfileInfo { + static char ID; // Class identification, replacement for typeinfo + NoPathProfileInfo() : ImmutablePass(ID) { + initializeNoPathProfileInfoPass(*PassRegistry::getPassRegistry()); + } + + /// getAdjustedAnalysisPointer - This method is used when a pass implements + /// an analysis interface through multiple inheritance. If needed, it + /// should override this to adjust the this pointer as needed for the + /// specified pass info. + virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { + if (PI == &PathProfileInfo::ID) + return (PathProfileInfo*)this; + return this; + } + + virtual const char *getPassName() const { + return "NoPathProfileInfo"; + } + }; +} // End of anonymous namespace + +char NoPathProfileInfo::ID = 0; +// Register this pass... +INITIALIZE_AG_PASS(NoPathProfileInfo, PathProfileInfo, "no-path-profile", + "No Path Profile Information", false, true, true) + +ImmutablePass *llvm::createNoPathProfileInfoPass() { return new NoPathProfileInfo(); } diff --git a/lib/Analysis/PathProfileVerifier.cpp b/lib/Analysis/PathProfileVerifier.cpp new file mode 100644 index 0000000..c549773 --- /dev/null +++ b/lib/Analysis/PathProfileVerifier.cpp @@ -0,0 +1,207 @@ +//===- PathProfileVerifier.cpp --------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This verifier derives an edge profile file from current path profile +// information +// +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "path-profile-verifier" + +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/ProfileInfoTypes.h" +#include "llvm/Analysis/PathProfileInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/raw_ostream.h" + +#include <stdio.h> + +using namespace llvm; + +namespace { + class PathProfileVerifier : public ModulePass { + private: + bool runOnModule(Module &M); + + public: + static char ID; // Pass identification, replacement for typeid + PathProfileVerifier() : ModulePass(ID) { + initializePathProfileVerifierPass(*PassRegistry::getPassRegistry()); + } + + + virtual const char *getPassName() const { + return "Path Profiler Verifier"; + } + + // The verifier requires the path profile and edge profile. + virtual void getAnalysisUsage(AnalysisUsage& AU) const; + }; +} + +static cl::opt<std::string> +EdgeProfileFilename("path-profile-verifier-file", + cl::init("edgefrompath.llvmprof.out"), + cl::value_desc("filename"), + cl::desc("Edge profile file generated by -path-profile-verifier"), + cl::Hidden); + +char PathProfileVerifier::ID = 0; +INITIALIZE_PASS(PathProfileVerifier, "path-profile-verifier", + "Compare the path profile derived edge profile against the " + "edge profile.", true, true) + +ModulePass *llvm::createPathProfileVerifierPass() { + return new PathProfileVerifier(); +} + +// The verifier requires the path profile and edge profile. +void PathProfileVerifier::getAnalysisUsage(AnalysisUsage& AU) const { + AU.addRequired<PathProfileInfo>(); + AU.addPreserved<PathProfileInfo>(); +} + +typedef std::map<unsigned, unsigned> DuplicateToIndexMap; +typedef std::map<BasicBlock*,DuplicateToIndexMap> BlockToDuplicateMap; +typedef std::map<BasicBlock*,BlockToDuplicateMap> NestedBlockToIndexMap; + +// the verifier iterates through each path to gather the total +// number of edge frequencies +bool PathProfileVerifier::runOnModule (Module &M) { + PathProfileInfo& pathProfileInfo = getAnalysis<PathProfileInfo>(); + + // setup a data structure to map path edges which index an + // array of edge counters + NestedBlockToIndexMap arrayMap; + unsigned i = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + + arrayMap[0][F->begin()][0] = i++; + + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + TerminatorInst *TI = BB->getTerminator(); + + unsigned duplicate = 0; + BasicBlock* prev = 0; + for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; + prev = TI->getSuccessor(s), ++s) { + if (prev == TI->getSuccessor(s)) + duplicate++; + else duplicate = 0; + + arrayMap[BB][TI->getSuccessor(s)][duplicate] = i++; + } + } + } + + std::vector<unsigned> edgeArray(i); + + // iterate through each path and increment the edge counters as needed + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + + pathProfileInfo.setCurrentFunction(F); + + DEBUG(dbgs() << "function '" << F->getName() << "' ran " + << pathProfileInfo.pathsRun() + << "/" << pathProfileInfo.getPotentialPathCount() + << " potential paths\n"); + + for( ProfilePathIterator nextPath = pathProfileInfo.pathBegin(), + endPath = pathProfileInfo.pathEnd(); + nextPath != endPath; nextPath++ ) { + ProfilePath* currentPath = nextPath->second; + + ProfilePathEdgeVector* pev = currentPath->getPathEdges(); + DEBUG(dbgs () << "path #" << currentPath->getNumber() << ": " + << currentPath->getCount() << "\n"); + // setup the entry edge (normally path profiling doens't care about this) + if (currentPath->getFirstBlockInPath() == &F->getEntryBlock()) + edgeArray[arrayMap[0][currentPath->getFirstBlockInPath()][0]] + += currentPath->getCount(); + + for( ProfilePathEdgeIterator nextEdge = pev->begin(), + endEdge = pev->end(); nextEdge != endEdge; nextEdge++ ) { + if (nextEdge != pev->begin()) + DEBUG(dbgs() << " :: "); + + BasicBlock* source = nextEdge->getSource(); + BasicBlock* target = nextEdge->getTarget(); + unsigned duplicateNumber = nextEdge->getDuplicateNumber(); + DEBUG(dbgs () << source->getNameStr() << " --{" << duplicateNumber + << "}--> " << target->getNameStr()); + + // Ensure all the referenced edges exist + // TODO: make this a separate function + if( !arrayMap.count(source) ) { + errs() << " error [" << F->getNameStr() << "()]: source '" + << source->getNameStr() + << "' does not exist in the array map.\n"; + } else if( !arrayMap[source].count(target) ) { + errs() << " error [" << F->getNameStr() << "()]: target '" + << target->getNameStr() + << "' does not exist in the array map.\n"; + } else if( !arrayMap[source][target].count(duplicateNumber) ) { + errs() << " error [" << F->getNameStr() << "()]: edge " + << source->getNameStr() << " -> " << target->getNameStr() + << " duplicate number " << duplicateNumber + << " does not exist in the array map.\n"; + } else { + edgeArray[arrayMap[source][target][duplicateNumber]] + += currentPath->getCount(); + } + } + + DEBUG(errs() << "\n"); + + delete pev; + } + } + + std::string errorInfo; + std::string filename = EdgeProfileFilename; + + // Open a handle to the file + FILE* edgeFile = fopen(filename.c_str(),"wb"); + + if (!edgeFile) { + errs() << "error: unable to open file '" << filename << "' for output.\n"; + return false; + } + + errs() << "Generating edge profile '" << filename << "' ...\n"; + + // write argument info + unsigned type = ArgumentInfo; + unsigned num = pathProfileInfo.argList.size(); + int zeros = 0; + + fwrite(&type,sizeof(unsigned),1,edgeFile); + fwrite(&num,sizeof(unsigned),1,edgeFile); + fwrite(pathProfileInfo.argList.c_str(),1,num,edgeFile); + if (num&3) + fwrite(&zeros, 1, 4-(num&3), edgeFile); + + type = EdgeInfo; + num = edgeArray.size(); + fwrite(&type,sizeof(unsigned),1,edgeFile); + fwrite(&num,sizeof(unsigned),1,edgeFile); + + // write each edge to the file + for( std::vector<unsigned>::iterator s = edgeArray.begin(), + e = edgeArray.end(); s != e; s++) + fwrite(&*s, sizeof (unsigned), 1, edgeFile); + + fclose (edgeFile); + + return true; +} diff --git a/lib/Transforms/Instrumentation/CMakeLists.txt b/lib/Transforms/Instrumentation/CMakeLists.txt index 80bb48c..0ac1cb0 100644 --- a/lib/Transforms/Instrumentation/CMakeLists.txt +++ b/lib/Transforms/Instrumentation/CMakeLists.txt @@ -2,5 +2,6 @@ add_llvm_library(LLVMInstrumentation EdgeProfiling.cpp Instrumentation.cpp OptimalEdgeProfiling.cpp + PathProfiling.cpp ProfilingUtils.cpp ) diff --git a/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/lib/Transforms/Instrumentation/EdgeProfiling.cpp index fe99b21..1d31fcc 100644 --- a/lib/Transforms/Instrumentation/EdgeProfiling.cpp +++ b/lib/Transforms/Instrumentation/EdgeProfiling.cpp @@ -17,6 +17,7 @@ // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "insert-edge-profiling" + #include "ProfilingUtils.h" #include "llvm/Module.h" #include "llvm/Pass.h" @@ -100,7 +101,7 @@ bool EdgeProfiler::runOnModule(Module &M) { // otherwise insert it in the successor block. if (TI->getNumSuccessors() == 1) { // Insert counter at the start of the block - IncrementCounterInBlock(BB, i++, Counters); + IncrementCounterInBlock(BB, i++, Counters, false); } else { // Insert counter at the start of the block IncrementCounterInBlock(TI->getSuccessor(s), i++, Counters); diff --git a/lib/Transforms/Instrumentation/Instrumentation.cpp b/lib/Transforms/Instrumentation/Instrumentation.cpp index 21dc7b9..96ed4fa 100644 --- a/lib/Transforms/Instrumentation/Instrumentation.cpp +++ b/lib/Transforms/Instrumentation/Instrumentation.cpp @@ -22,6 +22,7 @@ using namespace llvm; void llvm::initializeInstrumentation(PassRegistry &Registry) { initializeEdgeProfilerPass(Registry); initializeOptimalEdgeProfilerPass(Registry); + initializePathProfilerPass(Registry); } /// LLVMInitializeInstrumentation - C binding for diff --git a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp index 96a5417..c85a1a9 100644 --- a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp +++ b/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp @@ -52,12 +52,12 @@ namespace { } char OptimalEdgeProfiler::ID = 0; -INITIALIZE_PASS_BEGIN(OptimalEdgeProfiler, "insert-optimal-edge-profiling", +INITIALIZE_PASS_BEGIN(OptimalEdgeProfiler, "insert-optimal-edge-profiling", "Insert optimal instrumentation for edge profiling", false, false) INITIALIZE_PASS_DEPENDENCY(ProfileEstimatorPass) INITIALIZE_AG_DEPENDENCY(ProfileInfo) -INITIALIZE_PASS_END(OptimalEdgeProfiler, "insert-optimal-edge-profiling", +INITIALIZE_PASS_END(OptimalEdgeProfiler, "insert-optimal-edge-profiling", "Insert optimal instrumentation for edge profiling", false, false) @@ -132,11 +132,11 @@ bool OptimalEdgeProfiler::runOnModule(Module &M) { // Calculate a Maximum Spanning Tree with the edge weights determined by // ProfileEstimator. ProfileEstimator also assign weights to the virtual // edges (0,entry) and (BB,0) (for blocks with no successors) and this - // edges also participate in the maximum spanning tree calculation. + // edges also participate in the maximum spanning tree calculation. // The third parameter of MaximumSpanningTree() has the effect that not the // actual MST is returned but the edges _not_ in the MST. - ProfileInfo::EdgeWeights ECs = + ProfileInfo::EdgeWeights ECs = getAnalysis<ProfileInfo>(*F).getEdgeWeights(F); std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end()); MaximumSpanningTree<BasicBlock> MST (EdgeVector); diff --git a/lib/Transforms/Instrumentation/PathProfiling.cpp b/lib/Transforms/Instrumentation/PathProfiling.cpp new file mode 100644 index 0000000..6449b39 --- /dev/null +++ b/lib/Transforms/Instrumentation/PathProfiling.cpp @@ -0,0 +1,1423 @@ +//===- PathProfiling.cpp - Inserts counters for path profiling ------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass instruments functions for Ball-Larus path profiling. Ball-Larus +// profiling converts the CFG into a DAG by replacing backedges with edges +// from entry to the start block and from the end block to exit. The paths +// along the new DAG are enumrated, i.e. each path is given a path number. +// Edges are instrumented to increment the path number register, such that the +// path number register will equal the path number of the path taken at the +// exit. +// +// This file defines classes for building a CFG for use with different stages +// in the Ball-Larus path profiling instrumentation [Ball96]. The +// requirements are formatting the llvm CFG into the Ball-Larus DAG, path +// numbering, finding a spanning tree, moving increments from the spanning +// tree to chords. +// +// Terms: +// DAG - Directed Acyclic Graph. +// Ball-Larus DAG - A CFG with an entry node, an exit node, and backedges +// removed in the following manner. For every backedge +// v->w, insert edge ENTRY->w and edge v->EXIT. +// Path Number - The number corresponding to a specific path through a +// Ball-Larus DAG. +// Spanning Tree - A subgraph, S, is a spanning tree if S covers all +// vertices and is a tree. +// Chord - An edge not in the spanning tree. +// +// [Ball96] +// T. Ball and J. R. Larus. "Efficient Path Profiling." +// International Symposium on Microarchitecture, pages 46-57, 1996. +// http://portal.acm.org/citation.cfm?id=243857 +// +// [Ball94] +// Thomas Ball. "Efficiently Counting Program Events with Support for +// On-line queries." +// ACM Transactions on Programmmg Languages and Systems, Vol 16, No 5, +// September 1994, Pages 1399-1410. +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "insert-path-profiling" + +#include "llvm/DerivedTypes.h" +#include "ProfilingUtils.h" +#include "llvm/Analysis/PathNumbering.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/InstrTypes.h" +#include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/TypeBuilder.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Instrumentation.h" +#include <map> +#include <vector> + +#define HASH_THRESHHOLD 100000 + +using namespace llvm; + +namespace { +class BLInstrumentationNode; +class BLInstrumentationEdge; +class BLInstrumentationDag; + +// --------------------------------------------------------------------------- +// BLInstrumentationNode extends BallLarusNode with member used by the +// instrumentation algortihms. +// --------------------------------------------------------------------------- +class BLInstrumentationNode : public BallLarusNode { +public: + // Creates a new BLInstrumentationNode from a BasicBlock. + BLInstrumentationNode(BasicBlock* BB); + + // Get/sets the Value corresponding to the pathNumber register, + // constant or phinode. Used by the instrumentation code to remember + // path number Values. + Value* getStartingPathNumber(); + void setStartingPathNumber(Value* pathNumber); + + Value* getEndingPathNumber(); + void setEndingPathNumber(Value* pathNumber); + + // Get/set the PHINode Instruction for this node. + PHINode* getPathPHI(); + void setPathPHI(PHINode* pathPHI); + +private: + + Value* _startingPathNumber; // The Value for the current pathNumber. + Value* _endingPathNumber; // The Value for the current pathNumber. + PHINode* _pathPHI; // The PHINode for current pathNumber. +}; + +// -------------------------------------------------------------------------- +// BLInstrumentationEdge extends BallLarusEdge with data about the +// instrumentation that will end up on each edge. +// -------------------------------------------------------------------------- +class BLInstrumentationEdge : public BallLarusEdge { +public: + BLInstrumentationEdge(BLInstrumentationNode* source, + BLInstrumentationNode* target); + + // Sets the target node of this edge. Required to split edges. + void setTarget(BallLarusNode* node); + + // Get/set whether edge is in the spanning tree. + bool isInSpanningTree() const; + void setIsInSpanningTree(bool isInSpanningTree); + + // Get/ set whether this edge will be instrumented with a path number + // initialization. + bool isInitialization() const; + void setIsInitialization(bool isInitialization); + + // Get/set whether this edge will be instrumented with a path counter + // increment. Notice this is incrementing the path counter + // corresponding to the path number register. The path number + // increment is determined by getIncrement(). + bool isCounterIncrement() const; + void setIsCounterIncrement(bool isCounterIncrement); + + // Get/set the path number increment that this edge will be instrumented + // with. This is distinct from the path counter increment and the + // weight. The counter increment counts the number of executions of + // some path, whereas the path number keeps track of which path number + // the program is on. + long getIncrement() const; + void setIncrement(long increment); + + // Get/set whether the edge has been instrumented. + bool hasInstrumentation(); + void setHasInstrumentation(bool hasInstrumentation); + + // Returns the successor number of this edge in the source. + unsigned getSuccessorNumber(); + +private: + // The increment that the code will be instrumented with. + long long _increment; + + // Whether this edge is in the spanning tree. + bool _isInSpanningTree; + + // Whether this edge is an initialiation of the path number. + bool _isInitialization; + + // Whether this edge is a path counter increment. + bool _isCounterIncrement; + + // Whether this edge has been instrumented. + bool _hasInstrumentation; +}; + +// --------------------------------------------------------------------------- +// BLInstrumentationDag extends BallLarusDag with algorithms that +// determine where instrumentation should be placed. +// --------------------------------------------------------------------------- +class BLInstrumentationDag : public BallLarusDag { +public: + BLInstrumentationDag(Function &F); + + // Returns the Exit->Root edge. This edge is required for creating + // directed cycles in the algorithm for moving instrumentation off of + // the spanning tree + BallLarusEdge* getExitRootEdge(); + + // Returns an array of phony edges which mark those nodes + // with function calls + BLEdgeVector getCallPhonyEdges(); + + // Gets/sets the path counter array + GlobalVariable* getCounterArray(); + void setCounterArray(GlobalVariable* c); + + // Calculates the increments for the chords, thereby removing + // instrumentation from the spanning tree edges. Implementation is based + // on the algorithm in Figure 4 of [Ball94] + void calculateChordIncrements(); + + // Updates the state when an edge has been split + void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock); + + // Calculates a spanning tree of the DAG ignoring cycles. Whichever + // edges are in the spanning tree will not be instrumented, but this + // implementation does not try to minimize the instrumentation overhead + // by trying to find hot edges. + void calculateSpanningTree(); + + // Pushes initialization further down in order to group the first + // increment and initialization. + void pushInitialization(); + + // Pushes the path counter increments up in order to group the last path + // number increment. + void pushCounters(); + + // Removes phony edges from the successor list of the source, and the + // predecessor list of the target. + void unlinkPhony(); + + // Generate dot graph for the function + void generateDotGraph(); + +protected: + // BLInstrumentationDag creates BLInstrumentationNode objects in this + // method overriding the creation of BallLarusNode objects. + // + // Allows subclasses to determine which type of Node is created. + // Override this method to produce subclasses of BallLarusNode if + // necessary. + virtual BallLarusNode* createNode(BasicBlock* BB); + + // BLInstrumentationDag create BLInstrumentationEdges. + // + // Allows subclasses to determine which type of Edge is created. + // Override this method to produce subclasses of BallLarusEdge if + // necessary. Parameters source and target will have been created by + // createNode and can be cast to the subclass of BallLarusNode* + // returned by createNode. + virtual BallLarusEdge* createEdge( + BallLarusNode* source, BallLarusNode* target, unsigned edgeNumber); + +private: + BLEdgeVector _treeEdges; // All edges in the spanning tree. + BLEdgeVector _chordEdges; // All edges not in the spanning tree. + GlobalVariable* _counterArray; // Array to store path counters + + // Removes the edge from the appropriate predecessor and successor lists. + void unlinkEdge(BallLarusEdge* edge); + + // Makes an edge part of the spanning tree. + void makeEdgeSpanning(BLInstrumentationEdge* edge); + + // Pushes initialization and calls itself recursively. + void pushInitializationFromEdge(BLInstrumentationEdge* edge); + + // Pushes path counter increments up recursively. + void pushCountersFromEdge(BLInstrumentationEdge* edge); + + // Depth first algorithm for determining the chord increments.f + void calculateChordIncrementsDfs( + long weight, BallLarusNode* v, BallLarusEdge* e); + + // Determines the relative direction of two edges. + int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f); +}; + +// --------------------------------------------------------------------------- +// PathProfiler is a module pass which intruments path profiling instructions +// --------------------------------------------------------------------------- +class PathProfiler : public ModulePass { +private: + // Current context for multi threading support. + LLVMContext* Context; + + // Which function are we currently instrumenting + unsigned currentFunctionNumber; + + // The function prototype in the profiling runtime for incrementing a + // single path counter in a hash table. + Constant* llvmIncrementHashFunction; + Constant* llvmDecrementHashFunction; + + // Instruments each function with path profiling. 'main' is instrumented + // with code to save the profile to disk. + bool runOnModule(Module &M); + + // Analyzes the function for Ball-Larus path profiling, and inserts code. + void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M); + + // Creates an increment constant representing incr. + ConstantInt* createIncrementConstant(long incr, int bitsize); + + // Creates an increment constant representing the value in + // edge->getIncrement(). + ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge); + + // Finds the insertion point after pathNumber in block. PathNumber may + // be NULL. + BasicBlock::iterator getInsertionPoint( + BasicBlock* block, Value* pathNumber); + + // Inserts source's pathNumber Value* into target. Target may or may not + // have multiple predecessors, and may or may not have its phiNode + // initalized. + void pushValueIntoNode( + BLInstrumentationNode* source, BLInstrumentationNode* target); + + // Inserts source's pathNumber Value* into the appropriate slot of + // target's phiNode. + void pushValueIntoPHI( + BLInstrumentationNode* target, BLInstrumentationNode* source); + + // The Value* in node, oldVal, is updated with a Value* correspodning to + // oldVal + addition. + void insertNumberIncrement(BLInstrumentationNode* node, Value* addition, + bool atBeginning); + + // Creates a counter increment in the given node. The Value* in node is + // taken as the index into a hash table. + void insertCounterIncrement( + Value* incValue, + BasicBlock::iterator insertPoint, + BLInstrumentationDag* dag, + bool increment = true); + + // A PHINode is created in the node, and its values initialized to -1U. + void preparePHI(BLInstrumentationNode* node); + + // Inserts instrumentation for the given edge + // + // Pre: The edge's source node has pathNumber set if edge is non zero + // path number increment. + // + // Post: Edge's target node has a pathNumber set to the path number Value + // corresponding to the value of the path register after edge's + // execution. + void insertInstrumentationStartingAt( + BLInstrumentationEdge* edge, + BLInstrumentationDag* dag); + + // If this edge is a critical edge, then inserts a node at this edge. + // This edge becomes the first edge, and a new BallLarusEdge is created. + bool splitCritical(BLInstrumentationEdge* edge, BLInstrumentationDag* dag); + + // Inserts instrumentation according to the marked edges in dag. Phony + // edges must be unlinked from the DAG, but accessible from the + // backedges. Dag must have initializations, path number increments, and + // counter increments present. + // + // Counter storage is created here. + void insertInstrumentation( BLInstrumentationDag& dag, Module &M); + +public: + static char ID; // Pass identification, replacement for typeid + PathProfiler() : ModulePass(ID) { + initializePathProfilerPass(*PassRegistry::getPassRegistry()); + } + + virtual const char *getPassName() const { + return "Path Profiler"; + } +}; +} // end anonymous namespace + +// Should we print the dot-graphs +static cl::opt<bool> DotPathDag("path-profile-pathdag", cl::Hidden, + cl::desc("Output the path profiling DAG for each function.")); + +// Register the path profiler as a pass +char PathProfiler::ID = 0; +INITIALIZE_PASS(PathProfiler, "insert-path-profiling", + "Insert instrumentation for Ball-Larus path profiling", + false, false) + +ModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); } + +namespace llvm { + class PathProfilingFunctionTable {}; + + // Type for global array storing references to hashes or arrays + template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable, + xcompile> { + public: + static const StructType *get(LLVMContext& C) { + return( StructType::get( + C, TypeBuilder<types::i<32>, xcompile>::get(C), // type + TypeBuilder<types::i<32>, xcompile>::get(C), // array size + TypeBuilder<types::i<8>*, xcompile>::get(C), // array/hash ptr + NULL)); + } + }; + + typedef TypeBuilder<PathProfilingFunctionTable, true> + ftEntryTypeBuilder; + + // BallLarusEdge << operator overloading + raw_ostream& operator<<(raw_ostream& os, + const BLInstrumentationEdge& edge) { + os << "[" << edge.getSource()->getName() << " -> " + << edge.getTarget()->getName() << "] init: " + << (edge.isInitialization() ? "yes" : "no") + << " incr:" << edge.getIncrement() << " cinc: " + << (edge.isCounterIncrement() ? "yes" : "no"); + return(os); + } +} + +// Creates a new BLInstrumentationNode from a BasicBlock. +BLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) : + BallLarusNode(BB), + _startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {} + +// Constructor for BLInstrumentationEdge. +BLInstrumentationEdge::BLInstrumentationEdge(BLInstrumentationNode* source, + BLInstrumentationNode* target) + : BallLarusEdge(source, target, 0), + _increment(0), _isInSpanningTree(false), _isInitialization(false), + _isCounterIncrement(false), _hasInstrumentation(false) {} + +// Sets the target node of this edge. Required to split edges. +void BLInstrumentationEdge::setTarget(BallLarusNode* node) { + _target = node; +} + +// Returns whether this edge is in the spanning tree. +bool BLInstrumentationEdge::isInSpanningTree() const { + return(_isInSpanningTree); +} + +// Sets whether this edge is in the spanning tree. +void BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) { + _isInSpanningTree = isInSpanningTree; +} + +// Returns whether this edge will be instrumented with a path number +// initialization. +bool BLInstrumentationEdge::isInitialization() const { + return(_isInitialization); +} + +// Sets whether this edge will be instrumented with a path number +// initialization. +void BLInstrumentationEdge::setIsInitialization(bool isInitialization) { + _isInitialization = isInitialization; +} + +// Returns whether this edge will be instrumented with a path counter +// increment. Notice this is incrementing the path counter +// corresponding to the path number register. The path number +// increment is determined by getIncrement(). +bool BLInstrumentationEdge::isCounterIncrement() const { + return(_isCounterIncrement); +} + +// Sets whether this edge will be instrumented with a path counter +// increment. +void BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) { + _isCounterIncrement = isCounterIncrement; +} + +// Gets the path number increment that this edge will be instrumented +// with. This is distinct from the path counter increment and the +// weight. The counter increment is counts the number of executions of +// some path, whereas the path number keeps track of which path number +// the program is on. +long BLInstrumentationEdge::getIncrement() const { + return(_increment); +} + +// Set whether this edge will be instrumented with a path number +// increment. +void BLInstrumentationEdge::setIncrement(long increment) { + _increment = increment; +} + +// True iff the edge has already been instrumented. +bool BLInstrumentationEdge::hasInstrumentation() { + return(_hasInstrumentation); +} + +// Set whether this edge has been instrumented. +void BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) { + _hasInstrumentation = hasInstrumentation; +} + +// Returns the successor number of this edge in the source. +unsigned BLInstrumentationEdge::getSuccessorNumber() { + BallLarusNode* sourceNode = getSource(); + BallLarusNode* targetNode = getTarget(); + BasicBlock* source = sourceNode->getBlock(); + BasicBlock* target = targetNode->getBlock(); + + if(source == NULL || target == NULL) + return(0); + + TerminatorInst* terminator = source->getTerminator(); + + unsigned i; + for(i=0; i < terminator->getNumSuccessors(); i++) { + if(terminator->getSuccessor(i) == target) + break; + } + + return(i); +} + +// BLInstrumentationDag constructor initializes a DAG for the given Function. +BLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F), + _counterArray(0) { +} + +// Returns the Exit->Root edge. This edge is required for creating +// directed cycles in the algorithm for moving instrumentation off of +// the spanning tree +BallLarusEdge* BLInstrumentationDag::getExitRootEdge() { + BLEdgeIterator erEdge = getExit()->succBegin(); + return(*erEdge); +} + +BLEdgeVector BLInstrumentationDag::getCallPhonyEdges () { + BLEdgeVector callEdges; + + for( BLEdgeIterator edge = _edges.begin(), end = _edges.end(); + edge != end; edge++ ) { + if( (*edge)->getType() == BallLarusEdge::CALLEDGE_PHONY ) + callEdges.push_back(*edge); + } + + return callEdges; +} + +// Gets the path counter array +GlobalVariable* BLInstrumentationDag::getCounterArray() { + return _counterArray; +} + +void BLInstrumentationDag::setCounterArray(GlobalVariable* c) { + _counterArray = c; +} + +// Calculates the increment for the chords, thereby removing +// instrumentation from the spanning tree edges. Implementation is based on +// the algorithm in Figure 4 of [Ball94] +void BLInstrumentationDag::calculateChordIncrements() { + calculateChordIncrementsDfs(0, getRoot(), NULL); + + BLInstrumentationEdge* chord; + for(BLEdgeIterator chordEdge = _chordEdges.begin(), + end = _chordEdges.end(); chordEdge != end; chordEdge++) { + chord = (BLInstrumentationEdge*) *chordEdge; + chord->setIncrement(chord->getIncrement() + chord->getWeight()); + } +} + +// Updates the state when an edge has been split +void BLInstrumentationDag::splitUpdate(BLInstrumentationEdge* formerEdge, + BasicBlock* newBlock) { + BallLarusNode* oldTarget = formerEdge->getTarget(); + BallLarusNode* newNode = addNode(newBlock); + formerEdge->setTarget(newNode); + newNode->addPredEdge(formerEdge); + + DEBUG(dbgs() << " Edge split: " << *formerEdge << "\n"); + + oldTarget->removePredEdge(formerEdge); + BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0); + + if( formerEdge->getType() == BallLarusEdge::BACKEDGE || + formerEdge->getType() == BallLarusEdge::SPLITEDGE) { + newEdge->setType(formerEdge->getType()); + newEdge->setPhonyRoot(formerEdge->getPhonyRoot()); + newEdge->setPhonyExit(formerEdge->getPhonyExit()); + formerEdge->setType(BallLarusEdge::NORMAL); + formerEdge->setPhonyRoot(NULL); + formerEdge->setPhonyExit(NULL); + } +} + +// Calculates a spanning tree of the DAG ignoring cycles. Whichever +// edges are in the spanning tree will not be instrumented, but this +// implementation does not try to minimize the instrumentation overhead +// by trying to find hot edges. +void BLInstrumentationDag::calculateSpanningTree() { + std::stack<BallLarusNode*> dfsStack; + + for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end(); + nodeIt != end; nodeIt++) { + (*nodeIt)->setColor(BallLarusNode::WHITE); + } + + dfsStack.push(getRoot()); + while(dfsStack.size() > 0) { + BallLarusNode* node = dfsStack.top(); + dfsStack.pop(); + + if(node->getColor() == BallLarusNode::WHITE) + continue; + + BallLarusNode* nextNode; + bool forward = true; + BLEdgeIterator succEnd = node->succEnd(); + + node->setColor(BallLarusNode::WHITE); + // first iterate over successors then predecessors + for(BLEdgeIterator edge = node->succBegin(), predEnd = node->predEnd(); + edge != predEnd; edge++) { + if(edge == succEnd) { + edge = node->predBegin(); + forward = false; + } + + // Ignore split edges + if ((*edge)->getType() == BallLarusEdge::SPLITEDGE) + continue; + + nextNode = forward? (*edge)->getTarget(): (*edge)->getSource(); + if(nextNode->getColor() != BallLarusNode::WHITE) { + nextNode->setColor(BallLarusNode::WHITE); + makeEdgeSpanning((BLInstrumentationEdge*)(*edge)); + } + } + } + + for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); + edge != end; edge++) { + BLInstrumentationEdge* instEdge = (BLInstrumentationEdge*) (*edge); + // safe since createEdge is overriden + if(!instEdge->isInSpanningTree() && (*edge)->getType() + != BallLarusEdge::SPLITEDGE) + _chordEdges.push_back(instEdge); + } +} + +// Pushes initialization further down in order to group the first +// increment and initialization. +void BLInstrumentationDag::pushInitialization() { + BLInstrumentationEdge* exitRootEdge = + (BLInstrumentationEdge*) getExitRootEdge(); + exitRootEdge->setIsInitialization(true); + pushInitializationFromEdge(exitRootEdge); +} + +// Pushes the path counter increments up in order to group the last path +// number increment. +void BLInstrumentationDag::pushCounters() { + BLInstrumentationEdge* exitRootEdge = + (BLInstrumentationEdge*) getExitRootEdge(); + exitRootEdge->setIsCounterIncrement(true); + pushCountersFromEdge(exitRootEdge); +} + +// Removes phony edges from the successor list of the source, and the +// predecessor list of the target. +void BLInstrumentationDag::unlinkPhony() { + BallLarusEdge* edge; + + for(BLEdgeIterator next = _edges.begin(), + end = _edges.end(); next != end; next++) { + edge = (*next); + + if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY || + edge->getType() == BallLarusEdge::SPLITEDGE_PHONY || + edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) { + unlinkEdge(edge); + } + } +} + +// Generate a .dot graph to represent the DAG and pathNumbers +void BLInstrumentationDag::generateDotGraph() { + std::string errorInfo; + std::string functionName = getFunction().getNameStr(); + std::string filename = "pathdag." + functionName + ".dot"; + + DEBUG (dbgs() << "Writing '" << filename << "'...\n"); + raw_fd_ostream dotFile(filename.c_str(), errorInfo); + + if (!errorInfo.empty()) { + errs() << "Error opening '" << filename.c_str() <<"' for writing!"; + errs() << "\n"; + return; + } + + dotFile << "digraph " << functionName << " {\n"; + + for( BLEdgeIterator edge = _edges.begin(), end = _edges.end(); + edge != end; edge++) { + std::string sourceName = (*edge)->getSource()->getName(); + std::string targetName = (*edge)->getTarget()->getName(); + + dotFile << "\t\"" << sourceName.c_str() << "\" -> \"" + << targetName.c_str() << "\" "; + + long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement(); + + switch( (*edge)->getType() ) { + case BallLarusEdge::NORMAL: + dotFile << "[label=" << inc << "] [color=black];\n"; + break; + + case BallLarusEdge::BACKEDGE: + dotFile << "[color=cyan];\n"; + break; + + case BallLarusEdge::BACKEDGE_PHONY: + dotFile << "[label=" << inc + << "] [color=blue];\n"; + break; + + case BallLarusEdge::SPLITEDGE: + dotFile << "[color=violet];\n"; + break; + + case BallLarusEdge::SPLITEDGE_PHONY: + dotFile << "[label=" << inc << "] [color=red];\n"; + break; + + case BallLarusEdge::CALLEDGE_PHONY: + dotFile << "[label=" << inc << "] [color=green];\n"; + break; + } + } + + dotFile << "}\n"; +} + +// Allows subclasses to determine which type of Node is created. +// Override this method to produce subclasses of BallLarusNode if +// necessary. The destructor of BallLarusDag will call free on each pointer +// created. +BallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) { + return( new BLInstrumentationNode(BB) ); +} + +// Allows subclasses to determine which type of Edge is created. +// Override this method to produce subclasses of BallLarusEdge if +// necessary. The destructor of BallLarusDag will call free on each pointer +// created. +BallLarusEdge* BLInstrumentationDag::createEdge(BallLarusNode* source, + BallLarusNode* target, unsigned edgeNumber) { + // One can cast from BallLarusNode to BLInstrumentationNode since createNode + // is overriden to produce BLInstrumentationNode. + return( new BLInstrumentationEdge((BLInstrumentationNode*)source, + (BLInstrumentationNode*)target) ); +} + +// Sets the Value corresponding to the pathNumber register, constant, +// or phinode. Used by the instrumentation code to remember path +// number Values. +Value* BLInstrumentationNode::getStartingPathNumber(){ + return(_startingPathNumber); +} + +// Sets the Value of the pathNumber. Used by the instrumentation code. +void BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) { + DEBUG(dbgs() << " SPN-" << getName() << " <-- " << (pathNumber ? + pathNumber->getNameStr() : "unused") << "\n"); + _startingPathNumber = pathNumber; +} + +Value* BLInstrumentationNode::getEndingPathNumber(){ + return(_endingPathNumber); +} + +void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) { + DEBUG(dbgs() << " EPN-" << getName() << " <-- " + << (pathNumber ? pathNumber->getNameStr() : "unused") << "\n"); + _endingPathNumber = pathNumber; +} + +// Get the PHINode Instruction for this node. Used by instrumentation +// code. +PHINode* BLInstrumentationNode::getPathPHI() { + return(_pathPHI); +} + +// Set the PHINode Instruction for this node. Used by instrumentation +// code. +void BLInstrumentationNode::setPathPHI(PHINode* pathPHI) { + _pathPHI = pathPHI; +} + +// Removes the edge from the appropriate predecessor and successor +// lists. +void BLInstrumentationDag::unlinkEdge(BallLarusEdge* edge) { + if(edge == getExitRootEdge()) + DEBUG(dbgs() << " Removing exit->root edge\n"); + + edge->getSource()->removeSuccEdge(edge); + edge->getTarget()->removePredEdge(edge); +} + +// Makes an edge part of the spanning tree. +void BLInstrumentationDag::makeEdgeSpanning(BLInstrumentationEdge* edge) { + edge->setIsInSpanningTree(true); + _treeEdges.push_back(edge); +} + +// Pushes initialization and calls itself recursively. +void BLInstrumentationDag::pushInitializationFromEdge( + BLInstrumentationEdge* edge) { + BallLarusNode* target; + + target = edge->getTarget(); + if( target->getNumberPredEdges() > 1 || target == getExit() ) { + return; + } else { + for(BLEdgeIterator next = target->succBegin(), + end = target->succEnd(); next != end; next++) { + BLInstrumentationEdge* intoEdge = (BLInstrumentationEdge*) *next; + + // Skip split edges + if (intoEdge->getType() == BallLarusEdge::SPLITEDGE) + continue; + + intoEdge->setIncrement(intoEdge->getIncrement() + + edge->getIncrement()); + intoEdge->setIsInitialization(true); + pushInitializationFromEdge(intoEdge); + } + + edge->setIncrement(0); + edge->setIsInitialization(false); + } +} + +// Pushes path counter increments up recursively. +void BLInstrumentationDag::pushCountersFromEdge(BLInstrumentationEdge* edge) { + BallLarusNode* source; + + source = edge->getSource(); + if(source->getNumberSuccEdges() > 1 || source == getRoot() + || edge->isInitialization()) { + return; + } else { + for(BLEdgeIterator previous = source->predBegin(), + end = source->predEnd(); previous != end; previous++) { + BLInstrumentationEdge* fromEdge = (BLInstrumentationEdge*) *previous; + + // Skip split edges + if (fromEdge->getType() == BallLarusEdge::SPLITEDGE) + continue; + + fromEdge->setIncrement(fromEdge->getIncrement() + + edge->getIncrement()); + fromEdge->setIsCounterIncrement(true); + pushCountersFromEdge(fromEdge); + } + + edge->setIncrement(0); + edge->setIsCounterIncrement(false); + } +} + +// Depth first algorithm for determining the chord increments. +void BLInstrumentationDag::calculateChordIncrementsDfs(long weight, + BallLarusNode* v, BallLarusEdge* e) { + BLInstrumentationEdge* f; + + for(BLEdgeIterator treeEdge = _treeEdges.begin(), + end = _treeEdges.end(); treeEdge != end; treeEdge++) { + f = (BLInstrumentationEdge*) *treeEdge; + if(e != f && v == f->getTarget()) { + calculateChordIncrementsDfs( + calculateChordIncrementsDir(e,f)*(weight) + + f->getWeight(), f->getSource(), f); + } + if(e != f && v == f->getSource()) { + calculateChordIncrementsDfs( + calculateChordIncrementsDir(e,f)*(weight) + + f->getWeight(), f->getTarget(), f); + } + } + + for(BLEdgeIterator chordEdge = _chordEdges.begin(), + end = _chordEdges.end(); chordEdge != end; chordEdge++) { + f = (BLInstrumentationEdge*) *chordEdge; + if(v == f->getSource() || v == f->getTarget()) { + f->setIncrement(f->getIncrement() + + calculateChordIncrementsDir(e,f)*weight); + } + } +} + +// Determines the relative direction of two edges. +int BLInstrumentationDag::calculateChordIncrementsDir(BallLarusEdge* e, + BallLarusEdge* f) { + if( e == NULL) + return(1); + else if(e->getSource() == f->getTarget() + || e->getTarget() == f->getSource()) + return(1); + + return(-1); +} + +// Creates an increment constant representing incr. +ConstantInt* PathProfiler::createIncrementConstant(long incr, + int bitsize) { + return(ConstantInt::get(IntegerType::get(*Context, 32), incr)); +} + +// Creates an increment constant representing the value in +// edge->getIncrement(). +ConstantInt* PathProfiler::createIncrementConstant( + BLInstrumentationEdge* edge) { + return(createIncrementConstant(edge->getIncrement(), 32)); +} + +// Finds the insertion point after pathNumber in block. PathNumber may +// be NULL. +BasicBlock::iterator PathProfiler::getInsertionPoint(BasicBlock* block, Value* + pathNumber) { + if(pathNumber == NULL || isa<ConstantInt>(pathNumber) + || (((Instruction*)(pathNumber))->getParent()) != block) { + return(block->getFirstNonPHI()); + } else { + Instruction* pathNumberInst = (Instruction*) (pathNumber); + BasicBlock::iterator insertPoint; + BasicBlock::iterator end = block->end(); + + for(insertPoint = block->begin(); + insertPoint != end; insertPoint++) { + Instruction* insertInst = &(*insertPoint); + + if(insertInst == pathNumberInst) + return(++insertPoint); + } + + return(insertPoint); + } +} + +// A PHINode is created in the node, and its values initialized to -1U. +void PathProfiler::preparePHI(BLInstrumentationNode* node) { + BasicBlock* block = node->getBlock(); + BasicBlock::iterator insertPoint = block->getFirstNonPHI(); + PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context), "pathNumber", + insertPoint ); + node->setPathPHI(phi); + node->setStartingPathNumber(phi); + node->setEndingPathNumber(phi); + + for(pred_iterator predIt = pred_begin(node->getBlock()), + end = pred_end(node->getBlock()); predIt != end; predIt++) { + BasicBlock* pred = (*predIt); + + if(pred != NULL) + phi->addIncoming(createIncrementConstant((long)-1, 32), pred); + } +} + +// Inserts source's pathNumber Value* into target. Target may or may not +// have multiple predecessors, and may or may not have its phiNode +// initalized. +void PathProfiler::pushValueIntoNode(BLInstrumentationNode* source, + BLInstrumentationNode* target) { + if(target->getBlock() == NULL) + return; + + + if(target->getNumberPredEdges() <= 1) { + assert(target->getStartingPathNumber() == NULL && + "Target already has path number"); + target->setStartingPathNumber(source->getEndingPathNumber()); + target->setEndingPathNumber(source->getEndingPathNumber()); + DEBUG(dbgs() << " Passing path number" + << (source->getEndingPathNumber() ? "" : " (null)") + << " value through.\n"); + } else { + if(target->getPathPHI() == NULL) { + DEBUG(dbgs() << " Initializing PHI node for block '" + << target->getName() << "'\n"); + preparePHI(target); + } + pushValueIntoPHI(target, source); + DEBUG(dbgs() << " Passing number value into PHI for block '" + << target->getName() << "'\n"); + } +} + +// Inserts source's pathNumber Value* into the appropriate slot of +// target's phiNode. +void PathProfiler::pushValueIntoPHI(BLInstrumentationNode* target, + BLInstrumentationNode* source) { + PHINode* phi = target->getPathPHI(); + assert(phi != NULL && " Tried to push value into node with PHI, but node" + " actually had no PHI."); + phi->removeIncomingValue(source->getBlock(), false); + phi->addIncoming(source->getEndingPathNumber(), source->getBlock()); +} + +// The Value* in node, oldVal, is updated with a Value* correspodning to +// oldVal + addition. +void PathProfiler::insertNumberIncrement(BLInstrumentationNode* node, + Value* addition, bool atBeginning) { + BasicBlock* block = node->getBlock(); + assert(node->getStartingPathNumber() != NULL); + assert(node->getEndingPathNumber() != NULL); + + BasicBlock::iterator insertPoint; + + if( atBeginning ) + insertPoint = block->getFirstNonPHI(); + else + insertPoint = block->getTerminator(); + + DEBUG(errs() << " Creating addition instruction.\n"); + Value* newpn = BinaryOperator::Create(Instruction::Add, + node->getStartingPathNumber(), + addition, "pathNumber", insertPoint); + + node->setEndingPathNumber(newpn); + + if( atBeginning ) + node->setStartingPathNumber(newpn); +} + +// Creates a counter increment in the given node. The Value* in node is +// taken as the index into an array or hash table. The hash table access +// is a call to the runtime. +void PathProfiler::insertCounterIncrement(Value* incValue, + BasicBlock::iterator insertPoint, + BLInstrumentationDag* dag, + bool increment) { + // Counter increment for array + if( dag->getNumberOfPaths() <= HASH_THRESHHOLD ) { + // Get pointer to the array location + std::vector<Value*> gepIndices(2); + gepIndices[0] = Constant::getNullValue(Type::getInt32Ty(*Context)); + gepIndices[1] = incValue; + + GetElementPtrInst* pcPointer = + GetElementPtrInst::Create(dag->getCounterArray(), + gepIndices.begin(), gepIndices.end(), + "counterInc", insertPoint); + + // Load from the array - call it oldPC + LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint); + + // Test to see whether adding 1 will overflow the counter + ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc, + createIncrementConstant(0xffffffff, 32), + "isMax"); + + // Select increment for the path counter based on overflow + SelectInst* inc = + SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32), + createIncrementConstant(0,32), + "pathInc", insertPoint); + + // newPc = oldPc + inc + BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add, + oldPc, inc, "newPC", + insertPoint); + + // Store back in to the array + new StoreInst(newPc, pcPointer, insertPoint); + } else { // Counter increment for hash + std::vector<Value*> args(2); + args[0] = ConstantInt::get(Type::getInt32Ty(*Context), + currentFunctionNumber); + args[1] = incValue; + + CallInst::Create( + increment ? llvmIncrementHashFunction : llvmDecrementHashFunction, + args.begin(), args.end(), "", insertPoint); + } +} + +// Inserts instrumentation for the given edge +// +// Pre: The edge's source node has pathNumber set if edge is non zero +// path number increment. +// +// Post: Edge's target node has a pathNumber set to the path number Value +// corresponding to the value of the path register after edge's +// execution. +// +// FIXME: This should be reworked so it's not recursive. +void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge, + BLInstrumentationDag* dag) { + // Mark the edge as instrumented + edge->setHasInstrumentation(true); + DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n"); + + // create a new node for this edge's instrumentation + splitCritical(edge, dag); + + BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource(); + BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget(); + BLInstrumentationNode* instrumentNode; + BLInstrumentationNode* nextSourceNode; + + bool atBeginning = false; + + // Source node has only 1 successor so any information can be simply + // inserted in to it without splitting + if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) { + DEBUG(dbgs() << " Potential instructions to be placed in: " + << sourceNode->getName() << " (at end)\n"); + instrumentNode = sourceNode; + nextSourceNode = targetNode; // ... since we never made any new nodes + } + + // The target node only has one predecessor, so we can safely insert edge + // instrumentation into it. If there was splitting, it must have been + // successful. + else if( targetNode->getNumberPredEdges() == 1 ) { + DEBUG(dbgs() << " Potential instructions to be placed in: " + << targetNode->getName() << " (at beginning)\n"); + pushValueIntoNode(sourceNode, targetNode); + instrumentNode = targetNode; + nextSourceNode = NULL; // ... otherwise we'll just keep splitting + atBeginning = true; + } + + // Somehow, splitting must have failed. + else { + errs() << "Instrumenting could not split a critical edge.\n"; + DEBUG(dbgs() << " Couldn't split edge " << (*edge) << ".\n"); + return; + } + + // Insert instrumentation if this is a back or split edge + if( edge->getType() == BallLarusEdge::BACKEDGE || + edge->getType() == BallLarusEdge::SPLITEDGE ) { + BLInstrumentationEdge* top = + (BLInstrumentationEdge*) edge->getPhonyRoot(); + BLInstrumentationEdge* bottom = + (BLInstrumentationEdge*) edge->getPhonyExit(); + + assert( top->isInitialization() && " Top phony edge did not" + " contain a path number initialization."); + assert( bottom->isCounterIncrement() && " Bottom phony edge" + " did not contain a path counter increment."); + + // split edge has yet to be initialized + if( !instrumentNode->getEndingPathNumber() ) { + instrumentNode->setStartingPathNumber(createIncrementConstant(0,32)); + instrumentNode->setEndingPathNumber(createIncrementConstant(0,32)); + } + + BasicBlock::iterator insertPoint = atBeginning ? + instrumentNode->getBlock()->getFirstNonPHI() : + instrumentNode->getBlock()->getTerminator(); + + // add information from the bottom edge, if it exists + if( bottom->getIncrement() ) { + Value* newpn = + BinaryOperator::Create(Instruction::Add, + instrumentNode->getStartingPathNumber(), + createIncrementConstant(bottom), + "pathNumber", insertPoint); + instrumentNode->setEndingPathNumber(newpn); + } + + insertCounterIncrement(instrumentNode->getEndingPathNumber(), + insertPoint, dag); + + if( atBeginning ) + instrumentNode->setStartingPathNumber(createIncrementConstant(top)); + + instrumentNode->setEndingPathNumber(createIncrementConstant(top)); + + // Check for path counter increments + if( top->isCounterIncrement() ) { + insertCounterIncrement(instrumentNode->getEndingPathNumber(), + instrumentNode->getBlock()->getTerminator(),dag); + instrumentNode->setEndingPathNumber(0); + } + } + + // Insert instrumentation if this is a normal edge + else { + BasicBlock::iterator insertPoint = atBeginning ? + instrumentNode->getBlock()->getFirstNonPHI() : + instrumentNode->getBlock()->getTerminator(); + + if( edge->isInitialization() ) { // initialize path number + instrumentNode->setEndingPathNumber(createIncrementConstant(edge)); + } else if( edge->getIncrement() ) {// increment path number + Value* newpn = + BinaryOperator::Create(Instruction::Add, + instrumentNode->getStartingPathNumber(), + createIncrementConstant(edge), + "pathNumber", insertPoint); + instrumentNode->setEndingPathNumber(newpn); + + if( atBeginning ) + instrumentNode->setStartingPathNumber(newpn); + } + + // Check for path counter increments + if( edge->isCounterIncrement() ) { + insertCounterIncrement(instrumentNode->getEndingPathNumber(), + insertPoint, dag); + instrumentNode->setEndingPathNumber(0); + } + } + + // Push it along + if (nextSourceNode && instrumentNode->getEndingPathNumber()) + pushValueIntoNode(instrumentNode, nextSourceNode); + + // Add all the successors + for( BLEdgeIterator next = targetNode->succBegin(), + end = targetNode->succEnd(); next != end; next++ ) { + // So long as it is un-instrumented, add it to the list + if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() ) + insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag); + else + DEBUG(dbgs() << " Edge " << *(BLInstrumentationEdge*)(*next) + << " already instrumented.\n"); + } +} + +// Inserts instrumentation according to the marked edges in dag. Phony edges +// must be unlinked from the DAG, but accessible from the backedges. Dag +// must have initializations, path number increments, and counter increments +// present. +// +// Counter storage is created here. +void PathProfiler::insertInstrumentation( + BLInstrumentationDag& dag, Module &M) { + + BLInstrumentationEdge* exitRootEdge = + (BLInstrumentationEdge*) dag.getExitRootEdge(); + insertInstrumentationStartingAt(exitRootEdge, &dag); + + // Iterate through each call edge and apply the appropriate hash increment + // and decrement functions + BLEdgeVector callEdges = dag.getCallPhonyEdges(); + for( BLEdgeIterator edge = callEdges.begin(), + end = callEdges.end(); edge != end; edge++ ) { + BLInstrumentationNode* node = + (BLInstrumentationNode*)(*edge)->getSource(); + BasicBlock::iterator insertPoint = node->getBlock()->getFirstNonPHI(); + + // Find the first function call + while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call ) + insertPoint++; + + DEBUG(dbgs() << "\nInstrumenting method call block '" + << node->getBlock()->getNameStr() << "'\n"); + DEBUG(dbgs() << " Path number initialized: " + << ((node->getStartingPathNumber()) ? "yes" : "no") << "\n"); + + Value* newpn; + if( node->getStartingPathNumber() ) { + long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement(); + if ( inc ) + newpn = BinaryOperator::Create(Instruction::Add, + node->getStartingPathNumber(), + createIncrementConstant(inc,32), + "pathNumber", insertPoint); + else + newpn = node->getStartingPathNumber(); + } else { + newpn = (Value*)createIncrementConstant( + ((BLInstrumentationEdge*)(*edge))->getIncrement(), 32); + } + + insertCounterIncrement(newpn, insertPoint, &dag); + insertCounterIncrement(newpn, node->getBlock()->getTerminator(), + &dag, false); + } +} + +// Entry point of the module +void PathProfiler::runOnFunction(std::vector<Constant*> &ftInit, + Function &F, Module &M) { + // Build DAG from CFG + BLInstrumentationDag dag = BLInstrumentationDag(F); + dag.init(); + + // give each path a unique integer value + dag.calculatePathNumbers(); + + // modify path increments to increase the efficiency + // of instrumentation + dag.calculateSpanningTree(); + dag.calculateChordIncrements(); + dag.pushInitialization(); + dag.pushCounters(); + dag.unlinkPhony(); + + // potentially generate .dot graph for the dag + if (DotPathDag) + dag.generateDotGraph (); + + // Should we store the information in an array or hash + if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) { + const Type* t = ArrayType::get(Type::getInt32Ty(*Context), + dag.getNumberOfPaths()); + + dag.setCounterArray(new GlobalVariable(M, t, false, + GlobalValue::InternalLinkage, + Constant::getNullValue(t), "")); + } + + insertInstrumentation(dag, M); + + // Add to global function reference table + unsigned type; + const Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context); + + if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) + type = ProfilingArray; + else + type = ProfilingHash; + + std::vector<Constant*> entryArray(3); + entryArray[0] = createIncrementConstant(type,32); + entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32); + entryArray[2] = dag.getCounterArray() ? + ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) : + Constant::getNullValue(voidPtr); + + const StructType* at = ftEntryTypeBuilder::get(*Context); + ConstantStruct* functionEntry = + (ConstantStruct*)ConstantStruct::get(at, entryArray); + ftInit.push_back(functionEntry); +} + +// Output the bitcode if we want to observe instrumentation changess +#define PRINT_MODULE dbgs() << \ + "\n\n============= MODULE BEGIN ===============\n" << M << \ + "\n============== MODULE END ================\n" + +bool PathProfiler::runOnModule(Module &M) { + Context = &M.getContext(); + + DEBUG(dbgs() + << "****************************************\n" + << "****************************************\n" + << "** **\n" + << "** PATH PROFILING INSTRUMENTATION **\n" + << "** **\n" + << "****************************************\n" + << "****************************************\n"); + + // No main, no instrumentation! + Function *Main = M.getFunction("main"); + + // Using fortran? ... this kind of works + if (!Main) + Main = M.getFunction("MAIN__"); + + if (!Main) { + errs() << "WARNING: cannot insert path profiling into a module" + << " with no main function!\n"; + return false; + } + + BasicBlock::iterator insertPoint = Main->getEntryBlock().getFirstNonPHI(); + + llvmIncrementHashFunction = M.getOrInsertFunction( + "llvm_increment_path_count", + Type::getVoidTy(*Context), // return type + Type::getInt32Ty(*Context), // function number + Type::getInt32Ty(*Context), // path number + NULL ); + + llvmDecrementHashFunction = M.getOrInsertFunction( + "llvm_decrement_path_count", + Type::getVoidTy(*Context), // return type + Type::getInt32Ty(*Context), // function number + Type::getInt32Ty(*Context), // path number + NULL ); + + std::vector<Constant*> ftInit; + unsigned functionNumber = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) { + if (F->isDeclaration()) + continue; + + DEBUG(dbgs() << "Function: " << F->getNameStr() << "\n"); + functionNumber++; + + // set function number + currentFunctionNumber = functionNumber; + runOnFunction(ftInit, *F, M); + } + + const Type *t = ftEntryTypeBuilder::get(*Context); + const ArrayType* ftArrayType = ArrayType::get(t, ftInit.size()); + Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit); + + DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n"); + + GlobalVariable* functionTable = + new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage, + ftInitConstant, "functionPathTable"); + const Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0); + InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable, + PointerType::getUnqual(eltType)); + + DEBUG(PRINT_MODULE); + + return true; +} + +// If this edge is a critical edge, then inserts a node at this edge. +// This edge becomes the first edge, and a new BallLarusEdge is created. +// Returns true if the edge was split +bool PathProfiler::splitCritical(BLInstrumentationEdge* edge, + BLInstrumentationDag* dag) { + unsigned succNum = edge->getSuccessorNumber(); + BallLarusNode* sourceNode = edge->getSource(); + BallLarusNode* targetNode = edge->getTarget(); + BasicBlock* sourceBlock = sourceNode->getBlock(); + BasicBlock* targetBlock = targetNode->getBlock(); + + if(sourceBlock == NULL || targetBlock == NULL + || sourceNode->getNumberSuccEdges() <= 1 + || targetNode->getNumberPredEdges() == 1 ) { + return(false); + } + + TerminatorInst* terminator = sourceBlock->getTerminator(); + + if( SplitCriticalEdge(terminator, succNum, this, false)) { + BasicBlock* newBlock = terminator->getSuccessor(succNum); + dag->splitUpdate(edge, newBlock); + return(true); + } else + return(false); +} diff --git a/lib/Transforms/Instrumentation/ProfilingUtils.cpp b/lib/Transforms/Instrumentation/ProfilingUtils.cpp index 1a30e9b..b57bbf6 100644 --- a/lib/Transforms/Instrumentation/ProfilingUtils.cpp +++ b/lib/Transforms/Instrumentation/ProfilingUtils.cpp @@ -22,12 +22,13 @@ #include "llvm/Module.h" void llvm::InsertProfilingInitCall(Function *MainFn, const char *FnName, - GlobalValue *Array) { + GlobalValue *Array, + PointerType *arrayType) { LLVMContext &Context = MainFn->getContext(); - const Type *ArgVTy = + const Type *ArgVTy = PointerType::getUnqual(Type::getInt8PtrTy(Context)); - const PointerType *UIntPtr = - Type::getInt32PtrTy(Context); + const PointerType *UIntPtr = arrayType ? arrayType : + Type::getInt32PtrTy(Context); Module &M = *MainFn->getParent(); Constant *InitFn = M.getOrInsertFunction(FnName, Type::getInt32Ty(Context), Type::getInt32Ty(Context), @@ -71,9 +72,9 @@ void llvm::InsertProfilingInitCall(Function *MainFn, const char *FnName, case 2: AI = MainFn->arg_begin(); ++AI; if (AI->getType() != ArgVTy) { - Instruction::CastOps opcode = CastInst::getCastOpcode(AI, false, ArgVTy, + Instruction::CastOps opcode = CastInst::getCastOpcode(AI, false, ArgVTy, false); - InitCall->setArgOperand(1, + InitCall->setArgOperand(1, CastInst::Create(opcode, AI, ArgVTy, "argv.cast", InitCall)); } else { InitCall->setArgOperand(1, AI); @@ -93,7 +94,7 @@ void llvm::InsertProfilingInitCall(Function *MainFn, const char *FnName, } opcode = CastInst::getCastOpcode(AI, true, Type::getInt32Ty(Context), true); - InitCall->setArgOperand(0, + InitCall->setArgOperand(0, CastInst::Create(opcode, AI, Type::getInt32Ty(Context), "argc.cast", InitCall)); } else { @@ -106,9 +107,10 @@ void llvm::InsertProfilingInitCall(Function *MainFn, const char *FnName, } void llvm::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum, - GlobalValue *CounterArray) { + GlobalValue *CounterArray, bool beginning) { // Insert the increment after any alloca or PHI instructions... - BasicBlock::iterator InsertPos = BB->getFirstNonPHI(); + BasicBlock::iterator InsertPos = beginning ? BB->getFirstNonPHI() : + BB->getTerminator(); while (isa<AllocaInst>(InsertPos)) ++InsertPos; @@ -118,7 +120,7 @@ void llvm::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum, std::vector<Constant*> Indices(2); Indices[0] = Constant::getNullValue(Type::getInt32Ty(Context)); Indices[1] = ConstantInt::get(Type::getInt32Ty(Context), CounterNum); - Constant *ElementPtr = + Constant *ElementPtr = ConstantExpr::getGetElementPtr(CounterArray, &Indices[0], Indices.size()); diff --git a/lib/Transforms/Instrumentation/ProfilingUtils.h b/lib/Transforms/Instrumentation/ProfilingUtils.h index 94efffe..a76e357 100644 --- a/lib/Transforms/Instrumentation/ProfilingUtils.h +++ b/lib/Transforms/Instrumentation/ProfilingUtils.h @@ -21,11 +21,14 @@ namespace llvm { class Function; class GlobalValue; class BasicBlock; + class PointerType; void InsertProfilingInitCall(Function *MainFn, const char *FnName, - GlobalValue *Arr = 0); + GlobalValue *Arr = 0, + PointerType *arrayType = 0); void IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum, - GlobalValue *CounterArray); + GlobalValue *CounterArray, + bool beginning = true); } #endif diff --git a/runtime/libprofile/CommonProfiling.c b/runtime/libprofile/CommonProfiling.c index 8b27a25..1c1771c 100644 --- a/runtime/libprofile/CommonProfiling.c +++ b/runtime/libprofile/CommonProfiling.c @@ -2,17 +2,18 @@ |* |* The LLVM Compiler Infrastructure |* -|* This file is distributed under the University of Illinois Open Source -|* License. See LICENSE.TXT for details. -|* +|* This file is distributed under the University of Illinois Open Source +|* License. See LICENSE.TXT for details. +|* |*===----------------------------------------------------------------------===*| -|* +|* |* This file implements functions used by the various different types of |* profiling implementations. |* \*===----------------------------------------------------------------------===*/ #include "Profiling.h" +#include <assert.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> @@ -74,26 +75,23 @@ int save_arguments(int argc, const char **argv) { } -/* write_profiling_data - Write a raw block of profiling counters out to the - * llvmprof.out file. Note that we allow programs to be instrumented with - * multiple different kinds of instrumentation. For this reason, this function - * may be called more than once. +/* + * Retrieves the file descriptor for the profile file. */ -void write_profiling_data(enum ProfilingType PT, unsigned *Start, - unsigned NumElements) { +int getOutFile() { static int OutFile = -1; - int PTy; - - /* If this is the first time this function is called, open the output file for - * appending, creating it if it does not already exist. + + /* If this is the first time this function is called, open the output file + * for appending, creating it if it does not already exist. */ if (OutFile == -1) { - OutFile = open(OutputFilename, O_CREAT | O_WRONLY | O_APPEND, 0666); + OutFile = open(OutputFilename, O_CREAT | O_WRONLY, 0666); + lseek(OutFile, 0, SEEK_END); /* O_APPEND prevents seeking */ if (OutFile == -1) { fprintf(stderr, "LLVM profiling runtime: while opening '%s': ", OutputFilename); perror(""); - return; + return(OutFile); } /* Output the command line arguments to the file. */ @@ -108,10 +106,25 @@ void write_profiling_data(enum ProfilingType PT, unsigned *Start, write(OutFile, &Zeros, 4-(SavedArgsLength&3)); } } - + return(OutFile); +} + +/* write_profiling_data - Write a raw block of profiling counters out to the + * llvmprof.out file. Note that we allow programs to be instrumented with + * multiple different kinds of instrumentation. For this reason, this function + * may be called more than once. + */ +void write_profiling_data(enum ProfilingType PT, unsigned *Start, + unsigned NumElements) { + int PTy; + int outFile = getOutFile(); + /* Write out this record! */ PTy = PT; - write(OutFile, &PTy, sizeof(int)); - write(OutFile, &NumElements, sizeof(unsigned)); - write(OutFile, Start, NumElements*sizeof(unsigned)); + if( write(outFile, &PTy, sizeof(int)) < 0 || + write(outFile, &NumElements, sizeof(unsigned)) < 0 || + write(outFile, Start, NumElements*sizeof(unsigned)) < 0 ) { + fprintf(stderr,"error: unable to write to output file."); + exit(0); + } } diff --git a/runtime/libprofile/PathProfiling.c b/runtime/libprofile/PathProfiling.c new file mode 100644 index 0000000..651e63c --- /dev/null +++ b/runtime/libprofile/PathProfiling.c @@ -0,0 +1,266 @@ +/*===-- PathProfiling.c - Support library for path profiling --------------===*\ +|* +|* The LLVM Compiler Infrastructure +|* +|* This file is distributed under the University of Illinois Open Source +|* License. See LICENSE.TXT for details. +|* +|*===----------------------------------------------------------------------===*| +|* +|* This file implements the call back routines for the path profiling +|* instrumentation pass. This should be used with the -insert-path-profiling +|* LLVM pass. +|* +\*===----------------------------------------------------------------------===*/ + +#include "Profiling.h" +#include "llvm/Analysis/ProfileInfoTypes.h" +#include <sys/types.h> +#include <unistd.h> +#include <string.h> +#include <stdlib.h> +#include <unistd.h> +#include <stdint.h> +#include <stdio.h> + +/* note that this is used for functions with large path counts, + but it is unlikely those paths will ALL be executed */ +#define ARBITRARY_HASH_BIN_COUNT 100 + +typedef struct pathHashEntry_s { + uint32_t pathNumber; + uint32_t pathCount; + struct pathHashEntry_s* next; +} pathHashEntry_t; + +typedef struct pathHashTable_s { + pathHashEntry_t* hashBins[ARBITRARY_HASH_BIN_COUNT]; + uint32_t pathCounts; +} pathHashTable_t; + +typedef struct { + enum ProfilingStorageType type; + uint32_t size; + void* array; +} ftEntry_t; + +/* pointer to the function table allocated in the instrumented program */ +ftEntry_t* ft; +uint32_t ftSize; + +/* write an array table to file */ +void writeArrayTable(uint32_t fNumber, ftEntry_t* ft, uint32_t* funcCount) { + int outFile = getOutFile(); + uint32_t arrayHeaderLocation = 0; + uint32_t arrayCurrentLocation = 0; + uint32_t arrayIterator = 0; + uint32_t functionUsed = 0; + uint32_t pathCounts = 0; + + /* look through each entry in the array to determine whether the function + was executed at all */ + for( arrayIterator = 0; arrayIterator < ft->size; arrayIterator++ ) { + uint32_t pc = ((uint32_t*)ft->array)[arrayIterator]; + + /* was this path executed? */ + if( pc ) { + PathProfileTableEntry pte; + pte.pathNumber = arrayIterator; + pte.pathCounter = pc; + pathCounts++; + + /* one-time initialization stuff */ + if(!functionUsed) { + arrayHeaderLocation = lseek(outFile, 0, SEEK_CUR); + lseek(outFile, sizeof(PathProfileHeader), SEEK_CUR); + functionUsed = 1; + (*funcCount)++; + } + + /* write path data */ + if (write(outFile, &pte, sizeof(PathProfileTableEntry)) < 0) { + fprintf(stderr, "error: unable to write path entry to output file.\n"); + return; + } + } + } + + /* If this function was executed, write the header */ + if( functionUsed ) { + PathProfileHeader fHeader; + fHeader.fnNumber = fNumber; + fHeader.numEntries = pathCounts; + + arrayCurrentLocation = lseek(outFile, 0, SEEK_CUR); + lseek(outFile, arrayHeaderLocation, SEEK_SET); + + if (write(outFile, &fHeader, sizeof(PathProfileHeader)) < 0) { + fprintf(stderr, + "error: unable to write function header to output file.\n"); + return; + } + + lseek(outFile, arrayCurrentLocation, SEEK_SET); + } +} + +inline uint32_t hash (uint32_t key) { + /* this may benifit from a proper hash function */ + return key%ARBITRARY_HASH_BIN_COUNT; +} + +/* output a specific function's hash table to the profile file */ +void writeHashTable(uint32_t functionNumber, pathHashTable_t* hashTable) { + int outFile = getOutFile(); + PathProfileHeader header; + uint32_t i; + + header.fnNumber = functionNumber; + header.numEntries = hashTable->pathCounts; + + if (write(outFile, &header, sizeof(PathProfileHeader)) < 0) { + fprintf(stderr, "error: unable to write function header to output file.\n"); + return; + } + + for (i = 0; i < ARBITRARY_HASH_BIN_COUNT; i++) { + pathHashEntry_t* hashEntry = hashTable->hashBins[i]; + + while (hashEntry) { + pathHashEntry_t* temp; + + PathProfileTableEntry pte; + pte.pathNumber = hashEntry->pathNumber; + pte.pathCounter = hashEntry->pathCount; + + if (write(outFile, &pte, sizeof(PathProfileTableEntry)) < 0) { + fprintf(stderr, "error: unable to write path entry to output file.\n"); + return; + } + + temp = hashEntry; + hashEntry = hashEntry->next; + free (temp); + + } + } +} + +/* Return a pointer to this path's specific path counter */ +inline uint32_t* getPathCounter(uint32_t functionNumber, uint32_t pathNumber) { + pathHashTable_t* hashTable; + pathHashEntry_t* hashEntry; + uint32_t index = hash(pathNumber); + + if( ft[functionNumber-1].array == 0) + ft[functionNumber-1].array = calloc(sizeof(pathHashTable_t), 1); + + hashTable = (pathHashTable_t*)((ftEntry_t*)ft)[functionNumber-1].array; + hashEntry = hashTable->hashBins[index]; + + while (hashEntry) { + if (hashEntry->pathNumber == pathNumber) { + return &hashEntry->pathCount; + } + + hashEntry = hashEntry->next; + } + + hashEntry = malloc(sizeof(pathHashEntry_t)); + hashEntry->pathNumber = pathNumber; + hashEntry->pathCount = 0; + hashEntry->next = hashTable->hashBins[index]; + hashTable->hashBins[index] = hashEntry; + hashTable->pathCounts++; + return &hashEntry->pathCount; +} + +/* Increment a specific path's count */ +void llvm_increment_path_count (uint32_t functionNumber, uint32_t pathNumber) { + uint32_t* pathCounter = getPathCounter(functionNumber, pathNumber); + if( *pathCounter < 0xffffffff ) + (*pathCounter)++; +} + +/* Increment a specific path's count */ +void llvm_decrement_path_count (uint32_t functionNumber, uint32_t pathNumber) { + uint32_t* pathCounter = getPathCounter(functionNumber, pathNumber); + (*pathCounter)--; +} + +/* + * Writes out a path profile given a function table, in the following format. + * + * + * | <-- 32 bits --> | + * +-----------------+-----------------+ + * 0x00 | profileType | functionCount | + * +-----------------+-----------------+ + * 0x08 | functionNum | profileEntries | // function 1 + * +-----------------+-----------------+ + * 0x10 | pathNumber | pathCounter | // entry 1.1 + * +-----------------+-----------------+ + * 0x18 | pathNumber | pathCounter | // entry 1.2 + * +-----------------+-----------------+ + * ... | ... | ... | // entry 1.n + * +-----------------+-----------------+ + * ... | functionNum | profileEntries | // function 2 + * +-----------------+-----------------+ + * ... | pathNumber | pathCounter | // entry 2.1 + * +-----------------+-----------------+ + * ... | pathNumber | pathCounter | // entry 2.2 + * +-----------------+-----------------+ + * ... | ... | ... | // entry 2.n + * +-----------------+-----------------+ + * + */ +static void pathProfAtExitHandler() { + int outFile = getOutFile(); + uint32_t i; + uint32_t header[2] = { PathInfo, 0 }; + uint32_t headerLocation; + uint32_t currentLocation; + + /* skip over the header for now */ + headerLocation = lseek(outFile, 0, SEEK_CUR); + lseek(outFile, 2*sizeof(uint32_t), SEEK_CUR); + + /* Iterate through each function */ + for( i = 0; i < ftSize; i++ ) { + if( ft[i].type == ProfilingArray ) { + writeArrayTable(i+1,&ft[i],header + 1); + + } else if( ft[i].type == ProfilingHash ) { + /* If the hash exists, write it to file */ + if( ft[i].array ) { + writeHashTable(i+1,ft[i].array); + header[1]++; + free(ft[i].array); + } + } + } + + /* Setup and write the path profile header */ + currentLocation = lseek(outFile, 0, SEEK_CUR); + lseek(outFile, headerLocation, SEEK_SET); + + if (write(outFile, header, sizeof(header)) < 0) { + fprintf(stderr, + "error: unable to write path profile header to output file.\n"); + return; + } + + lseek(outFile, currentLocation, SEEK_SET); +} +/* llvm_start_path_profiling - This is the main entry point of the path + * profiling library. It is responsible for setting up the atexit handler. + */ +int llvm_start_path_profiling(int argc, const char** argv, + void* functionTable, uint32_t numElements) { + int Ret = save_arguments(argc, argv); + ft = functionTable; + ftSize = numElements; + atexit(pathProfAtExitHandler); + + return Ret; +} diff --git a/runtime/libprofile/Profiling.h b/runtime/libprofile/Profiling.h index a7e3ccc..c6b9a4d 100644 --- a/runtime/libprofile/Profiling.h +++ b/runtime/libprofile/Profiling.h @@ -1,9 +1,9 @@ -/*===-- Profiling.h - Profiling support library support routines --*- C -*-===*\ +/*===-- Profiling.h - Profiling support library support routines ----------===*\ |* |* The LLVM Compiler Infrastructure |* -|* This file is distributed under the University of Illinois Open Source -|* License. See LICENSE.TXT for details. +|* This file is distributed under the University of Illinois Open Source +|* License. See LICENSE.TXT for details. |* |*===----------------------------------------------------------------------===*| |* @@ -22,6 +22,11 @@ */ int save_arguments(int argc, const char **argv); +/* + * Retrieves the file descriptor for the profile file. + */ +int getOutFile(); + /* write_profiling_data - Write out a typed packet of profiling data to the * current output file. */ diff --git a/runtime/libprofile/libprofile.exports b/runtime/libprofile/libprofile.exports index f45ff47..b8057c7 100644 --- a/runtime/libprofile/libprofile.exports +++ b/runtime/libprofile/libprofile.exports @@ -1,4 +1,7 @@ llvm_start_edge_profiling llvm_start_opt_edge_profiling +llvm_start_path_profiling llvm_start_basic_block_tracing llvm_trace_basic_block +llvm_increment_path_count +llvm_decrement_path_count |