diff options
61 files changed, 12 insertions, 8640 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 3218e844b6..f4ec094f1b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -246,18 +246,13 @@ if( WIN32 AND NOT CYGWIN ) endif() # Define options to control the inclusion and default build behavior for -# components which may not strictly be necessary (tools, runtime, examples, and -# tests). +# components which may not strictly be necessary (tools, examples, and tests). # # This is primarily to support building smaller or faster project files. option(LLVM_INCLUDE_TOOLS "Generate build targets for the LLVM tools." ON) option(LLVM_BUILD_TOOLS "Build the LLVM tools. If OFF, just generate build targets." ON) -option(LLVM_INCLUDE_RUNTIME "Generate build targets for the LLVM runtimes" ON) -option(LLVM_BUILD_RUNTIME - "Build the LLVM runtime libraries. If OFF, just generate build targets." ON) - option(LLVM_BUILD_EXAMPLES "Build the LLVM example programs. If OFF, just generate build targets." OFF) option(LLVM_INCLUDE_EXAMPLES "Generate build targets for the LLVM examples" ON) @@ -471,10 +466,6 @@ if( LLVM_INCLUDE_TOOLS ) add_subdirectory(tools) endif() -if( LLVM_INCLUDE_RUNTIME ) - add_subdirectory(runtime) -endif() - if( LLVM_INCLUDE_EXAMPLES ) add_subdirectory(examples) endif() diff --git a/LLVMBuild.txt b/LLVMBuild.txt index e763fd2afe..9cee3030a9 100644 --- a/LLVMBuild.txt +++ b/LLVMBuild.txt @@ -16,7 +16,7 @@ ;===------------------------------------------------------------------------===; [common] -subdirectories = bindings docs examples lib projects runtime tools utils +subdirectories = bindings docs examples lib projects tools utils [component_0] type = Group @@ -15,7 +15,7 @@ LEVEL := . # 3. Build IR, which builds the Intrinsics.inc file used by libs. # 4. Build libs, which are needed by llvm-config. # 5. Build llvm-config, which determines inter-lib dependencies for tools. -# 6. Build tools, runtime, docs. +# 6. Build tools and docs. # # When cross-compiling, there are some things (tablegen) that need to # be build for the build system first. @@ -31,7 +31,7 @@ ifeq ($(BUILD_DIRS_ONLY),1) OPTIONAL_DIRS := tools/clang/utils/TableGen else DIRS := lib/Support lib/TableGen utils lib/IR lib tools/llvm-shlib \ - tools/llvm-config tools runtime docs unittests + tools/llvm-config tools docs unittests OPTIONAL_DIRS := projects bindings endif @@ -52,17 +52,17 @@ ifneq ($(ENABLE_DOCS),1) endif ifeq ($(MAKECMDGOALS),libs-only) - DIRS := $(filter-out tools runtime docs, $(DIRS)) + DIRS := $(filter-out tools docs, $(DIRS)) OPTIONAL_DIRS := endif ifeq ($(MAKECMDGOALS),install-libs) - DIRS := $(filter-out tools runtime docs, $(DIRS)) + DIRS := $(filter-out tools docs, $(DIRS)) OPTIONAL_DIRS := $(filter bindings, $(OPTIONAL_DIRS)) endif ifeq ($(MAKECMDGOALS),tools-only) - DIRS := $(filter-out runtime docs, $(DIRS)) + DIRS := $(filter-out docs, $(DIRS)) OPTIONAL_DIRS := endif @@ -72,7 +72,7 @@ ifeq ($(MAKECMDGOALS),install-clang) tools/clang/tools/c-index-test \ tools/clang/include/clang-c \ tools/clang/runtime tools/clang/docs \ - tools/lto runtime + tools/lto OPTIONAL_DIRS := NO_INSTALL = 1 endif @@ -84,7 +84,7 @@ ifeq ($(MAKECMDGOALS),clang-only) endif ifeq ($(MAKECMDGOALS),unittests) - DIRS := $(filter-out tools runtime docs, $(DIRS)) utils unittests + DIRS := $(filter-out tools docs, $(DIRS)) utils unittests OPTIONAL_DIRS := endif diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index ae117135db..0b4e96f1e8 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -95,64 +95,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createProfileLoaderPass - This pass loads information from a profile dump - // file. - // - ModulePass *createProfileLoaderPass(); - extern char &ProfileLoaderPassID; - - //===--------------------------------------------------------------------===// - // - // createProfileMetadataLoaderPass - This pass loads information from a - // profile dump file and sets branch weight metadata. - // - ModulePass *createProfileMetadataLoaderPass(); - extern char &ProfileMetadataLoaderPassID; - - //===--------------------------------------------------------------------===// - // - // createNoProfileInfoPass - This pass implements the default "no profile". - // - ImmutablePass *createNoProfileInfoPass(); - - //===--------------------------------------------------------------------===// - // - // createProfileEstimatorPass - This pass estimates profiling information - // instead of loading it from a previous run. - // - FunctionPass *createProfileEstimatorPass(); - extern char &ProfileEstimatorPassID; - - //===--------------------------------------------------------------------===// - // - // createProfileVerifierPass - This pass verifies profiling information. - // - FunctionPass *createProfileVerifierPass(); - - //===--------------------------------------------------------------------===// - // - // 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. // diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h deleted file mode 100644 index 400a37d829..0000000000 --- a/include/llvm/Analysis/PathNumbering.h +++ /dev/null @@ -1,304 +0,0 @@ -//===- 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_ANALYSIS_PATHNUMBERING_H -#define LLVM_ANALYSIS_PATHNUMBERING_H - -#include "llvm/Analysis/ProfileInfoTypes.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.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 deleted file mode 100644 index 4fce16ef0d..0000000000 --- a/include/llvm/Analysis/PathProfileInfo.h +++ /dev/null @@ -1,112 +0,0 @@ -//===- 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_ANALYSIS_PATHPROFILEINFO_H -#define LLVM_ANALYSIS_PATHPROFILEINFO_H - -#include "llvm/Analysis/PathNumbering.h" -#include "llvm/IR/BasicBlock.h" - -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/ProfileDataLoader.h b/include/llvm/Analysis/ProfileDataLoader.h deleted file mode 100644 index 90097f7995..0000000000 --- a/include/llvm/Analysis/ProfileDataLoader.h +++ /dev/null @@ -1,140 +0,0 @@ -//===- ProfileDataLoader.h - Load & convert profile info ----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// The ProfileDataLoader class is used to load profiling data from a dump file. -// The ProfileDataT<FType, BType> class is used to store the mapping of this -// data to control flow edges. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PROFILEDATALOADER_H -#define LLVM_ANALYSIS_PROFILEDATALOADER_H - -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include <string> - -namespace llvm { - -class ModulePass; -class Function; -class BasicBlock; - -// Helper for dumping edges to dbgs(). -raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, - const BasicBlock *> E); - -/// \brief The ProfileDataT<FType, BType> class is used to store the mapping of -/// profiling data to control flow edges. -/// -/// An edge is defined by its source and sink basic blocks. -template<class FType, class BType> -class ProfileDataT { -public: - // The profiling information defines an Edge by its source and sink basic - // blocks. - typedef std::pair<const BType*, const BType*> Edge; - -private: - typedef DenseMap<Edge, unsigned> EdgeWeights; - - /// \brief Count the number of times a transition between two blocks is - /// executed. - /// - /// As a special case, we also hold an edge from the null BasicBlock to the - /// entry block to indicate how many times the function was entered. - DenseMap<const FType*, EdgeWeights> EdgeInformation; - -public: - /// getFunction() - Returns the Function for an Edge. - static const FType *getFunction(Edge e) { - // e.first may be NULL - assert(((!e.first) || (e.first->getParent() == e.second->getParent())) - && "A ProfileData::Edge can not be between two functions"); - assert(e.second && "A ProfileData::Edge must have a real sink"); - return e.second->getParent(); - } - - /// getEdge() - Creates an Edge between two BasicBlocks. - static Edge getEdge(const BType *Src, const BType *Dest) { - return Edge(Src, Dest); - } - - /// getEdgeWeight - Return the number of times that a given edge was - /// executed. - unsigned getEdgeWeight(Edge e) const { - const FType *f = getFunction(e); - assert((EdgeInformation.find(f) != EdgeInformation.end()) - && "No profiling information for function"); - EdgeWeights weights = EdgeInformation.find(f)->second; - - assert((weights.find(e) != weights.end()) - && "No profiling information for edge"); - return weights.find(e)->second; - } - - /// addEdgeWeight - Add 'weight' to the already stored execution count for - /// this edge. - void addEdgeWeight(Edge e, unsigned weight) { - EdgeInformation[getFunction(e)][e] += weight; - } -}; - -typedef ProfileDataT<Function, BasicBlock> ProfileData; -//typedef ProfileDataT<MachineFunction, MachineBasicBlock> MachineProfileData; - -/// The ProfileDataLoader class is used to load raw profiling data from the -/// dump file. -class ProfileDataLoader { -private: - /// The name of the file where the raw profiling data is stored. - const std::string &Filename; - - /// A vector of the command line arguments used when the target program was - /// run to generate profiling data. One entry per program run. - SmallVector<std::string, 1> CommandLines; - - /// The raw values for how many times each edge was traversed, values from - /// multiple program runs are accumulated. - SmallVector<unsigned, 32> EdgeCounts; - -public: - /// ProfileDataLoader ctor - Read the specified profiling data file, exiting - /// the program if the file is invalid or broken. - ProfileDataLoader(const char *ToolName, const std::string &Filename); - - /// A special value used to represent the weight of an edge which has not - /// been counted yet. - static const unsigned Uncounted; - - /// getNumExecutions - Return the number of times the target program was run - /// to generate this profiling data. - unsigned getNumExecutions() const { return CommandLines.size(); } - - /// getExecution - Return the command line parameters used to generate the - /// i'th set of profiling data. - const std::string &getExecution(unsigned i) const { return CommandLines[i]; } - - const std::string &getFileName() const { return Filename; } - - /// getRawEdgeCounts - Return the raw profiling data, this is just a list of - /// numbers with no mappings to edges. - ArrayRef<unsigned> getRawEdgeCounts() const { return EdgeCounts; } -}; - -/// createProfileMetadataLoaderPass - This function returns a Pass that loads -/// the profiling information for the module from the specified filename. -ModulePass *createProfileMetadataLoaderPass(const std::string &Filename); - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/ProfileDataTypes.h b/include/llvm/Analysis/ProfileDataTypes.h deleted file mode 100644 index 1be15e025d..0000000000 --- a/include/llvm/Analysis/ProfileDataTypes.h +++ /dev/null @@ -1,39 +0,0 @@ -/*===-- ProfileDataTypes.h - Profiling info shared constants --------------===*\ -|* -|* The LLVM Compiler Infrastructure -|* -|* This file is distributed under the University of Illinois Open Source -|* License. See LICENSE.TXT for details. -|* -|*===----------------------------------------------------------------------===*| -|* -|* This file defines constants shared by the various different profiling -|* runtime libraries and the LLVM C++ profile metadata loader. It must be a -|* C header because, at present, the profiling runtimes are written in C. -|* -\*===----------------------------------------------------------------------===*/ - -#ifndef LLVM_ANALYSIS_PROFILEDATATYPES_H -#define LLVM_ANALYSIS_PROFILEDATATYPES_H - -/* Included by libprofile. */ -#if defined(__cplusplus) -extern "C" { -#endif - -/* TODO: Strip out unused entries once ProfileInfo etc has been removed. */ -enum ProfilingType { - ArgumentInfo = 1, /* The command line argument block */ - FunctionInfo = 2, /* Function profiling information */ - BlockInfo = 3, /* Block profiling information */ - EdgeInfo = 4, /* Edge profiling information */ - PathInfo = 5, /* Path profiling information */ - BBTraceInfo = 6, /* Basic block trace information */ - OptEdgeInfo = 7 /* Edge profiling information, optimal version */ -}; - -#if defined(__cplusplus) -} -#endif - -#endif /* LLVM_ANALYSIS_PROFILEDATATYPES_H */ diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h deleted file mode 100644 index 5d17fa1220..0000000000 --- a/include/llvm/Analysis/ProfileInfo.h +++ /dev/null @@ -1,247 +0,0 @@ -//===- llvm/Analysis/ProfileInfo.h - Profile Info Interface -----*- 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 generic ProfileInfo interface, which is used as the -// common interface used by all clients of profiling information, and -// implemented either by making static guestimations, or by actually reading in -// profiling information gathered by running the program. -// -// Note that to be useful, all profile-based optimizations should preserve -// ProfileInfo, which requires that they notify it when changes to the CFG are -// made. (This is not implemented yet.) -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PROFILEINFO_H -#define LLVM_ANALYSIS_PROFILEINFO_H - -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -#include <cassert> -#include <map> -#include <set> -#include <string> - -namespace llvm { - class Pass; - class raw_ostream; - - class BasicBlock; - class Function; - class MachineBasicBlock; - class MachineFunction; - - // Helper for dumping edges to dbgs(). - raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E); - raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E); - - raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB); - raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB); - - raw_ostream& operator<<(raw_ostream &O, const Function *F); - raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF); - - /// ProfileInfo Class - This class holds and maintains profiling - /// information for some unit of code. - template<class FType, class BType> - class ProfileInfoT { - public: - // Types for handling profiling information. - typedef std::pair<const BType*, const BType*> Edge; - typedef std::pair<Edge, double> EdgeWeight; - typedef std::map<Edge, double> EdgeWeights; - typedef std::map<const BType*, double> BlockCounts; - typedef std::map<const BType*, const BType*> Path; - - protected: - // EdgeInformation - Count the number of times a transition between two - // blocks is executed. As a special case, we also hold an edge from the - // null BasicBlock to the entry block to indicate how many times the - // function was entered. - std::map<const FType*, EdgeWeights> EdgeInformation; - - // BlockInformation - Count the number of times a block is executed. - std::map<const FType*, BlockCounts> BlockInformation; - - // FunctionInformation - Count the number of times a function is executed. - std::map<const FType*, double> FunctionInformation; - - ProfileInfoT<MachineFunction, MachineBasicBlock> *MachineProfile; - public: - static char ID; // Class identification, replacement for typeinfo - ProfileInfoT(); - ~ProfileInfoT(); // We want to be subclassed - - // MissingValue - The value that is returned for execution counts in case - // no value is available. - static const double MissingValue; - - // getFunction() - Returns the Function for an Edge, checking for validity. - static const FType* getFunction(Edge e) { - if (e.first) - return e.first->getParent(); - if (e.second) - return e.second->getParent(); - llvm_unreachable("Invalid ProfileInfo::Edge"); - } - - // getEdge() - Creates an Edge from two BasicBlocks. - static Edge getEdge(const BType *Src, const BType *Dest) { - return std::make_pair(Src, Dest); - } - - //===------------------------------------------------------------------===// - /// Profile Information Queries - /// - double getExecutionCount(const FType *F); - - double getExecutionCount(const BType *BB); - - void setExecutionCount(const BType *BB, double w); - - void addExecutionCount(const BType *BB, double w); - - double getEdgeWeight(Edge e) const { - typename std::map<const FType*, EdgeWeights>::const_iterator J = - EdgeInformation.find(getFunction(e)); - if (J == EdgeInformation.end()) return MissingValue; - - typename EdgeWeights::const_iterator I = J->second.find(e); - if (I == J->second.end()) return MissingValue; - - return I->second; - } - - void setEdgeWeight(Edge e, double w) { - DEBUG_WITH_TYPE("profile-info", - dbgs() << "Creating Edge " << e - << " (weight: " << format("%.20g",w) << ")\n"); - EdgeInformation[getFunction(e)][e] = w; - } - - void addEdgeWeight(Edge e, double w); - - EdgeWeights &getEdgeWeights (const FType *F) { - return EdgeInformation[F]; - } - - //===------------------------------------------------------------------===// - /// Analysis Update Methods - /// - void removeBlock(const BType *BB); - - void removeEdge(Edge e); - - void replaceEdge(const Edge &, const Edge &); - - enum GetPathMode { - GetPathToExit = 1, - GetPathToValue = 2, - GetPathToDest = 4, - GetPathWithNewEdges = 8 - }; - - const BType *GetPath(const BType *Src, const BType *Dest, - Path &P, unsigned Mode); - - void divertFlow(const Edge &, const Edge &); - - void splitEdge(const BType *FirstBB, const BType *SecondBB, - const BType *NewBB, bool MergeIdenticalEdges = false); - - void splitBlock(const BType *Old, const BType* New); - - void splitBlock(const BType *BB, const BType* NewBB, - BType *const *Preds, unsigned NumPreds); - - void replaceAllUses(const BType *RmBB, const BType *DestBB); - - void transfer(const FType *Old, const FType *New); - - void repair(const FType *F); - - void dump(FType *F = 0, bool real = true) { - dbgs() << "**** This is ProfileInfo " << this << " speaking:\n"; - if (!real) { - typename std::set<const FType*> Functions; - - dbgs() << "Functions: \n"; - if (F) { - dbgs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n"; - Functions.insert(F); - } else { - for (typename std::map<const FType*, double>::iterator fi = FunctionInformation.begin(), - fe = FunctionInformation.end(); fi != fe; ++fi) { - dbgs() << fi->first << "@" << format("%p",fi->first) << ": " << format("%.20g",fi->second) << "\n"; - Functions.insert(fi->first); - } - } - - for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end(); - FI != FE; ++FI) { - const FType *F = *FI; - typename std::map<const FType*, BlockCounts>::iterator bwi = BlockInformation.find(F); - dbgs() << "BasicBlocks for Function " << F << ":\n"; - for (typename BlockCounts::const_iterator bi = bwi->second.begin(), be = bwi->second.end(); bi != be; ++bi) { - dbgs() << bi->first << "@" << format("%p", bi->first) << ": " << format("%.20g",bi->second) << "\n"; - } - } - - for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end(); - FI != FE; ++FI) { - typename std::map<const FType*, EdgeWeights>::iterator ei = EdgeInformation.find(*FI); - dbgs() << "Edges for Function " << ei->first << ":\n"; - for (typename EdgeWeights::iterator ewi = ei->second.begin(), ewe = ei->second.end(); - ewi != ewe; ++ewi) { - dbgs() << ewi->first << ": " << format("%.20g",ewi->second) << "\n"; - } - } - } else { - assert(F && "No function given, this is not supported!"); - dbgs() << "Functions: \n"; - dbgs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n"; - - dbgs() << "BasicBlocks for Function " << F << ":\n"; - for (typename FType::const_iterator BI = F->begin(), BE = F->end(); - BI != BE; ++BI) { - const BType *BB = &(*BI); - dbgs() << BB << "@" << format("%p", BB) << ": " << format("%.20g",getExecutionCount(BB)) << "\n"; - } - } - dbgs() << "**** ProfileInfo " << this << ", over and out.\n"; - } - - bool CalculateMissingEdge(const BType *BB, Edge &removed, bool assumeEmptyExit = false); - - bool EstimateMissingEdges(const BType *BB); - - ProfileInfoT<MachineFunction, MachineBasicBlock> *MI() { - if (MachineProfile == 0) - MachineProfile = new ProfileInfoT<MachineFunction, MachineBasicBlock>(); - return MachineProfile; - } - - bool hasMI() const { - return (MachineProfile != 0); - } - }; - - typedef ProfileInfoT<Function, BasicBlock> ProfileInfo; - typedef ProfileInfoT<MachineFunction, MachineBasicBlock> MachineProfileInfo; - - /// createProfileLoaderPass - This function returns a Pass that loads the - /// profiling information for the module from the specified filename, making - /// it available to the optimizers. - Pass *createProfileLoaderPass(const std::string &Filename); - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h deleted file mode 100644 index e0f49f3179..0000000000 --- a/include/llvm/Analysis/ProfileInfoLoader.h +++ /dev/null @@ -1,81 +0,0 @@ -//===- ProfileInfoLoader.h - Load & convert profile information -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// The ProfileInfoLoader class is used to load and represent profiling -// information read in from the dump file. If conversions between formats are -// needed, it can also do this. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PROFILEINFOLOADER_H -#define LLVM_ANALYSIS_PROFILEINFOLOADER_H - -#include <string> -#include <utility> -#include <vector> - -namespace llvm { - -class Module; -class Function; -class BasicBlock; - -class ProfileInfoLoader { - const std::string &Filename; - std::vector<std::string> CommandLines; - std::vector<unsigned> FunctionCounts; - std::vector<unsigned> BlockCounts; - std::vector<unsigned> EdgeCounts; - std::vector<unsigned> OptimalEdgeCounts; - std::vector<unsigned> BBTrace; -public: - // ProfileInfoLoader ctor - Read the specified profiling data file, exiting - // the program if the file is invalid or broken. - ProfileInfoLoader(const char *ToolName, const std::string &Filename); - - static const unsigned Uncounted; - - unsigned getNumExecutions() const { return CommandLines.size(); } - const std::string &getExecution(unsigned i) const { return CommandLines[i]; } - - const std::string &getFileName() const { return Filename; } - - // getRawFunctionCounts - This method is used by consumers of function - // counting information. - // - const std::vector<unsigned> &getRawFunctionCounts() const { - return FunctionCounts; - } - - // getRawBlockCounts - This method is used by consumers of block counting - // information. - // - const std::vector<unsigned> &getRawBlockCounts() const { - return BlockCounts; - } - - // getEdgeCounts - This method is used by consumers of edge counting - // information. - // - const std::vector<unsigned> &getRawEdgeCounts() const { - return EdgeCounts; - } - - // getEdgeOptimalCounts - This method is used by consumers of optimal edge - // counting information. - // - const std::vector<unsigned> &getRawOptimalEdgeCounts() const { - return OptimalEdgeCounts; - } - -}; - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h deleted file mode 100644 index 45aab5b70d..0000000000 --- a/include/llvm/Analysis/ProfileInfoTypes.h +++ /dev/null @@ -1,52 +0,0 @@ -/*===-- ProfileInfoTypes.h - Profiling info shared constants --------------===*\ -|* -|* The LLVM Compiler Infrastructure -|* -|* This file is distributed under the University of Illinois Open Source -|* License. See LICENSE.TXT for details. -|* -|*===----------------------------------------------------------------------===*| -|* -|* This file defines constants shared by the various different profiling -|* runtime libraries and the LLVM C++ profile info loader. It must be a -|* C header because, at present, the profiling runtimes are written in C. -|* -\*===----------------------------------------------------------------------===*/ - -#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 -}; - -#include "llvm/Analysis/ProfileDataTypes.h" - -/* - * 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 1b50bb2265..bb82d94290 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -113,9 +113,7 @@ void initializeDominanceFrontierPass(PassRegistry&); void initializeDominatorTreePass(PassRegistry&); void initializeEarlyIfConverterPass(PassRegistry&); void initializeEdgeBundlesPass(PassRegistry&); -void initializeEdgeProfilerPass(PassRegistry&); void initializeExpandPostRAPass(PassRegistry&); -void initializePathProfilerPass(PassRegistry&); void initializeGCOVProfilerPass(PassRegistry&); void initializeAddressSanitizerPass(PassRegistry&); void initializeAddressSanitizerModulePass(PassRegistry&); @@ -155,8 +153,6 @@ void initializeLiveRegMatrixPass(PassRegistry&); void initializeLiveStacksPass(PassRegistry&); void initializeLiveVariablesPass(PassRegistry&); void initializeLoaderPassPass(PassRegistry&); -void initializeProfileMetadataLoaderPassPass(PassRegistry&); -void initializePathProfileLoaderPassPass(PassRegistry&); void initializeLocalStackSlotPassPass(PassRegistry&); void initializeLoopDeletionPass(PassRegistry&); void initializeLoopExtractorPass(PassRegistry&); @@ -195,14 +191,11 @@ void initializeMetaRenamerPass(PassRegistry&); void initializeMergeFunctionsPass(PassRegistry&); void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeNoAAPass(PassRegistry&); -void initializeNoProfileInfoPass(PassRegistry&); -void initializeNoPathProfileInfoPass(PassRegistry&); void initializeObjCARCAliasAnalysisPass(PassRegistry&); void initializeObjCARCAPElimPass(PassRegistry&); void initializeObjCARCExpandPass(PassRegistry&); void initializeObjCARCContractPass(PassRegistry&); void initializeObjCARCOptPass(PassRegistry&); -void initializeOptimalEdgeProfilerPass(PassRegistry&); void initializeOptimizePHIsPass(PassRegistry&); void initializePartiallyInlineLibCallsPass(PassRegistry&); void initializePEIPass(PassRegistry&); @@ -220,11 +213,6 @@ void initializePrintFunctionPassPass(PassRegistry&); void initializePrintModulePassPass(PassRegistry&); void initializePrintBasicBlockPassPass(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&); void initializeReassociatePass(PassRegistry&); diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 0639ed1dad..d97e54c205 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -74,9 +74,6 @@ namespace { (void) llvm::createDomPrinterPass(); (void) llvm::createDomOnlyViewerPass(); (void) llvm::createDomViewerPass(); - (void) llvm::createEdgeProfilerPass(); - (void) llvm::createOptimalEdgeProfilerPass(); - (void) llvm::createPathProfilerPass(); (void) llvm::createGCOVProfilerPass(); (void) llvm::createFunctionInliningPass(); (void) llvm::createAlwaysInlinerPass(); @@ -102,18 +99,11 @@ namespace { (void) llvm::createLowerInvokePass(); (void) llvm::createLowerSwitchPass(); (void) llvm::createNoAAPass(); - (void) llvm::createNoProfileInfoPass(); (void) llvm::createObjCARCAliasAnalysisPass(); (void) llvm::createObjCARCAPElimPass(); (void) llvm::createObjCARCExpandPass(); (void) llvm::createObjCARCContractPass(); (void) llvm::createObjCARCOptPass(); - (void) llvm::createProfileEstimatorPass(); - (void) llvm::createProfileVerifierPass(); - (void) llvm::createPathProfileVerifierPass(); - (void) llvm::createProfileLoaderPass(); - (void) llvm::createProfileMetadataLoaderPass(); - (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 a5cac00e3e..8a1b34e488 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -35,15 +35,6 @@ namespace llvm { class ModulePass; class FunctionPass; -// Insert edge profiling instrumentation -ModulePass *createEdgeProfilerPass(); - -// Insert optimal edge profiling instrumentation -ModulePass *createOptimalEdgeProfilerPass(); - -// Insert path profiling instrumentation -ModulePass *createPathProfilerPass(); - // Insert GCOV profiling instrumentation struct GCOVOptions { static GCOVOptions getDefault(); diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp index 349c4178c2..806239306a 100644 --- a/lib/Analysis/Analysis.cpp +++ b/lib/Analysis/Analysis.cpp @@ -54,16 +54,6 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeMemoryDependenceAnalysisPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); initializePostDominatorTreePass(Registry); - initializeProfileEstimatorPassPass(Registry); - initializeNoProfileInfoPass(Registry); - initializeNoPathProfileInfoPass(Registry); - initializeProfileInfoAnalysisGroup(Registry); - initializePathProfileInfoAnalysisGroup(Registry); - initializeLoaderPassPass(Registry); - initializePathProfileLoaderPassPass(Registry); - initializeProfileVerifierPassPass(Registry); - initializePathProfileVerifierPass(Registry); - initializeProfileMetadataLoaderPassPass(Registry); initializeRegionInfoPass(Registry); initializeRegionViewerPass(Registry); initializeRegionPrinterPass(Registry); diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 94ded342a9..3d7c0ed7c2 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -35,17 +35,7 @@ add_llvm_library(LLVMAnalysis ModuleDebugInfoPrinter.cpp NoAliasAnalysis.cpp PHITransAddr.cpp - PathNumbering.cpp - PathProfileInfo.cpp - PathProfileVerifier.cpp PostDominators.cpp - ProfileEstimatorPass.cpp - ProfileInfo.cpp - ProfileInfoLoader.cpp - ProfileInfoLoaderPass.cpp - ProfileVerifierPass.cpp - ProfileDataLoader.cpp - ProfileDataLoaderPass.cpp PtrUseVisitor.cpp RegionInfo.cpp RegionPass.cpp diff --git a/lib/Analysis/PathNumbering.cpp b/lib/Analysis/PathNumbering.cpp deleted file mode 100644 index 30d213b775..0000000000 --- a/lib/Analysis/PathNumbering.cpp +++ /dev/null @@ -1,521 +0,0 @@ -//===- 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/IR/Constants.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/TypeBuilder.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/raw_ostream.h" -#include <queue> -#include <sstream> -#include <stack> -#include <string> -#include <utility> - -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 possibility 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<ResumeInst>(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 deleted file mode 100644 index bc53221d31..0000000000 --- a/lib/Analysis/PathProfileInfo.cpp +++ /dev/null @@ -1,433 +0,0 @@ -//===- 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/Analysis/PathProfileInfo.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ProfileInfoTypes.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.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 deleted file mode 100644 index dabd347501..0000000000 --- a/lib/Analysis/PathProfileVerifier.cpp +++ /dev/null @@ -1,205 +0,0 @@ -//===- 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/Analysis/Passes.h" -#include "llvm/Analysis/PathProfileInfo.h" -#include "llvm/Analysis/ProfileInfoTypes.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.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[(BasicBlock*)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 doesn't care about this) - if (currentPath->getFirstBlockInPath() == &F->getEntryBlock()) - edgeArray[arrayMap[(BasicBlock*)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->getName() << " --{" << duplicateNumber - << "}--> " << target->getName()); - - // Ensure all the referenced edges exist - // TODO: make this a separate function - if( !arrayMap.count(source) ) { - errs() << " error [" << F->getName() << "()]: source '" - << source->getName() - << "' does not exist in the array map.\n"; - } else if( !arrayMap[source].count(target) ) { - errs() << " error [" << F->getName() << "()]: target '" - << target->getName() - << "' does not exist in the array map.\n"; - } else if( !arrayMap[source][target].count(duplicateNumber) ) { - errs() << " error [" << F->getName() << "()]: edge " - << source->getName() << " -> " << target->getName() - << " 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 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/Analysis/ProfileDataLoader.cpp b/lib/Analysis/ProfileDataLoader.cpp deleted file mode 100644 index 3d0a1e2eac..0000000000 --- a/lib/Analysis/ProfileDataLoader.cpp +++ /dev/null @@ -1,155 +0,0 @@ -//===- ProfileDataLoader.cpp - Load profile information from disk ---------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// The ProfileDataLoader class is used to load raw profiling data from the dump -// file. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/ProfileDataLoader.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/OwningPtr.h" -#include "llvm/Analysis/ProfileDataTypes.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/system_error.h" -#include <cstdio> -#include <cstdlib> -using namespace llvm; - -raw_ostream &llvm::operator<<(raw_ostream &O, std::pair<const BasicBlock *, - const BasicBlock *> E) { - O << "("; - - if (E.first) - O << E.first->getName(); - else - O << "0"; - - O << ","; - - if (E.second) - O << E.second->getName(); - else - O << "0"; - - return O << ")"; -} - -/// AddCounts - Add 'A' and 'B', accounting for the fact that the value of one -/// (or both) may not be defined. -static unsigned AddCounts(unsigned A, unsigned B) { - // If either value is undefined, use the other. - // Undefined + undefined = undefined. - if (A == ProfileDataLoader::Uncounted) return B; - if (B == ProfileDataLoader::Uncounted) return A; - - return A + B; -} - -/// ReadProfilingData - Load 'NumEntries' items of type 'T' from file 'F' -template <typename T> -static void ReadProfilingData(const char *ToolName, FILE *F, - T *Data, size_t NumEntries) { - // Read in the block of data... - if (fread(Data, sizeof(T), NumEntries, F) != NumEntries) - report_fatal_error(Twine(ToolName) + ": Profiling data truncated"); -} - -/// ReadProfilingNumEntries - Read how many entries are in this profiling data -/// packet. -static unsigned ReadProfilingNumEntries(const char *ToolName, FILE *F, - bool ShouldByteSwap) { - unsigned Entry; - ReadProfilingData<unsigned>(ToolName, F, &Entry, 1); - return ShouldByteSwap ? ByteSwap_32(Entry) : Entry; -} - -/// ReadProfilingBlock - Read the number of entries in the next profiling data -/// packet and then accumulate the entries into 'Data'. -static void ReadProfilingBlock(const char *ToolName, FILE *F, - bool ShouldByteSwap, - SmallVectorImpl<unsigned> &Data) { - // Read the number of entries... - unsigned NumEntries = ReadProfilingNumEntries(ToolName, F, ShouldByteSwap); - - // Read in the data. - SmallVector<unsigned, 8> TempSpace(NumEntries); - ReadProfilingData<unsigned>(ToolName, F, TempSpace.data(), NumEntries); - - // Make sure we have enough space ... - if (Data.size() < NumEntries) - Data.resize(NumEntries, ProfileDataLoader::Uncounted); - - // Accumulate the data we just read into the existing data. - for (unsigned i = 0; i < NumEntries; ++i) { - unsigned Entry = ShouldByteSwap ? ByteSwap_32(TempSpace[i]) : TempSpace[i]; - Data[i] = AddCounts(Entry, Data[i]); - } -} - -/// ReadProfilingArgBlock - Read the command line arguments that the progam was -/// run with when the current profiling data packet(s) were generated. -static void ReadProfilingArgBlock(const char *ToolName, FILE *F, - bool ShouldByteSwap, - SmallVectorImpl<std::string> &CommandLines) { - // Read the number of bytes ... - unsigned ArgLength = ReadProfilingNumEntries(ToolName, F, ShouldByteSwap); - - // Read in the arguments (if there are any to read). Round up the length to - // the nearest 4-byte multiple. - SmallVector<char, 8> Args(ArgLength+4); - if (ArgLength) - ReadProfilingData<char>(ToolName, F, Args.data(), (ArgLength+3) & ~3); - - // Store the arguments. - CommandLines.push_back(std::string(&Args[0], &Args[ArgLength])); -} - -const unsigned ProfileDataLoader::Uncounted = ~0U; - -/// ProfileDataLoader ctor - Read the specified profiling data file, reporting -/// a fatal error if the file is invalid or broken. -ProfileDataLoader::ProfileDataLoader(const char *ToolName, - const std::string &Filename) - : Filename(Filename) { - FILE *F = fopen(Filename.c_str(), "rb"); - if (F == 0) - report_fatal_error(Twine(ToolName) + ": Error opening '" + - Filename + "': "); - - // Keep reading packets until we run out of them. - unsigned PacketType; - while (fread(&PacketType, sizeof(unsigned), 1, F) == 1) { - // If the low eight bits of the packet are zero, we must be dealing with an - // endianness mismatch. Byteswap all words read from the profiling - // information. This can happen when the compiler host and target have - // different endianness. - bool ShouldByteSwap = (char)PacketType == 0; - PacketType = ShouldByteSwap ? ByteSwap_32(PacketType) : PacketType; - - switch (PacketType) { - case ArgumentInfo: - ReadProfilingArgBlock(ToolName, F, ShouldByteSwap, CommandLines); - break; - - case EdgeInfo: - ReadProfilingBlock(ToolName, F, ShouldByteSwap, EdgeCounts); - break; - - default: - report_fatal_error(std::string(ToolName) - + ": Unknown profiling packet type"); - break; - } - } - - fclose(F); -} diff --git a/lib/Analysis/ProfileDataLoaderPass.cpp b/lib/Analysis/ProfileDataLoaderPass.cpp deleted file mode 100644 index 2ee0093a8f..0000000000 --- a/lib/Analysis/ProfileDataLoaderPass.cpp +++ /dev/null @@ -1,188 +0,0 @@ -//===- ProfileDataLoaderPass.cpp - Set branch weight metadata from prof ---===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass loads profiling data from a dump file and sets branch weight -// metadata. -// -// TODO: Replace all "profile-metadata-loader" strings with "profile-loader" -// once ProfileInfo etc. has been removed. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "profile-metadata-loader" -#include "llvm/Analysis/Passes.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/ProfileDataLoader.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/MDBuilder.h" -#include "llvm/IR/Metadata.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -using namespace llvm; - -STATISTIC(NumEdgesRead, "The # of edges read."); -STATISTIC(NumTermsAnnotated, "The # of terminator instructions annotated."); - -static cl::opt<std::string> -ProfileMetadataFilename("profile-file", cl::init("llvmprof.out"), - cl::value_desc("filename"), - cl::desc("Profile file loaded by -profile-metadata-loader")); - -namespace { - /// This pass loads profiling data from a dump file and sets branch weight - /// metadata. - class ProfileMetadataLoaderPass : public ModulePass { - std::string Filename; - public: - static char ID; // Class identification, replacement for typeinfo - explicit ProfileMetadataLoaderPass(const std::string &filename = "") - : ModulePass(ID), Filename(filename) { - initializeProfileMetadataLoaderPassPass(*PassRegistry::getPassRegistry()); - if (filename.empty()) Filename = ProfileMetadataFilename; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - - virtual const char *getPassName() const { - return "Profile loader"; - } - - virtual void readEdge(unsigned, ProfileData&, ProfileData::Edge, - ArrayRef<unsigned>); - virtual unsigned matchEdges(Module&, ProfileData&, ArrayRef<unsigned>); - virtual void setBranchWeightMetadata(Module&, ProfileData&); - - virtual bool runOnModule(Module &M); - }; -} // End of anonymous namespace - -char ProfileMetadataLoaderPass::ID = 0; -INITIALIZE_PASS_BEGIN(ProfileMetadataLoaderPass, "profile-metadata-loader", - "Load profile information from llvmprof.out", false, true) -INITIALIZE_PASS_END(ProfileMetadataLoaderPass, "profile-metadata-loader", - "Load profile information from llvmprof.out", false, true) - -char &llvm::ProfileMetadataLoaderPassID = ProfileMetadataLoaderPass::ID; - -/// createProfileMetadataLoaderPass - This function returns a Pass that loads -/// the profiling information for the module from the specified filename, -/// making it available to the optimizers. -ModulePass *llvm::createProfileMetadataLoaderPass() { - return new ProfileMetadataLoaderPass(); -} -ModulePass *llvm::createProfileMetadataLoaderPass(const std::string &Filename) { - return new ProfileMetadataLoaderPass(Filename); -} - -/// readEdge - Take the value from a profile counter and assign it to an edge. -void ProfileMetadataLoaderPass::readEdge(unsigned ReadCount, - ProfileData &PB, ProfileData::Edge e, - ArrayRef<unsigned> Counters) { - if (ReadCount >= Counters.size()) return; - - unsigned weight = Counters[ReadCount]; - assert(weight != ProfileDataLoader::Uncounted); - PB.addEdgeWeight(e, weight); - - DEBUG(dbgs() << "-- Read Edge Counter for " << e - << " (# "<< (ReadCount) << "): " - << PB.getEdgeWeight(e) << "\n"); -} - -/// matchEdges - Link every profile counter with an edge. -unsigned ProfileMetadataLoaderPass::matchEdges(Module &M, ProfileData &PB, - ArrayRef<unsigned> Counters) { - if (Counters.size() == 0) return 0; - - unsigned ReadCount = 0; - - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - DEBUG(dbgs() << "Loading edges in '" << F->getName() << "'\n"); - readEdge(ReadCount++, PB, PB.getEdge(0, &F->getEntryBlock()), Counters); - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - TerminatorInst *TI = BB->getTerminator(); - for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { - readEdge(ReadCount++, PB, PB.getEdge(BB,TI->getSuccessor(s)), - Counters); - } - } - } - - return ReadCount; -} - -/// setBranchWeightMetadata - Translate the counter values associated with each -/// edge into branch weights for each conditional branch (a branch with 2 or -/// more desinations). -void ProfileMetadataLoaderPass::setBranchWeightMetadata(Module &M, - ProfileData &PB) { - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - DEBUG(dbgs() << "Setting branch metadata in '" << F->getName() << "'\n"); - - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - TerminatorInst *TI = BB->getTerminator(); - unsigned NumSuccessors = TI->getNumSuccessors(); - - // If there is only one successor then we can not set a branch - // probability as the target is certain. - if (NumSuccessors < 2) continue; - - // Load the weights of all edges leading from this terminator. - DEBUG(dbgs() << "-- Terminator with " << NumSuccessors - << " successors:\n"); - SmallVector<uint32_t, 4> Weights(NumSuccessors); - for (unsigned s = 0 ; s < NumSuccessors ; ++s) { - ProfileData::Edge edge = PB.getEdge(BB, TI->getSuccessor(s)); - Weights[s] = (uint32_t)PB.getEdgeWeight(edge); - DEBUG(dbgs() << "---- Edge '" << edge << "' has weight " - << Weights[s] << "\n"); - } - - // Set branch weight metadata. This will set branch probabilities of - // 100%/0% if that is true of the dynamic execution. - // BranchProbabilityInfo can account for this when it loads this metadata - // (it gives the unexectuted branch a weight of 1 for the purposes of - // probability calculations). - MDBuilder MDB(TI->getContext()); - MDNode *Node = MDB.createBranchWeights(Weights); - TI->setMetadata(LLVMContext::MD_prof, Node); - NumTermsAnnotated++; - } - } -} - -bool ProfileMetadataLoaderPass::runOnModule(Module &M) { - ProfileDataLoader PDL("profile-data-loader", Filename); - ProfileData PB; - - ArrayRef<unsigned> Counters = PDL.getRawEdgeCounts(); - - unsigned ReadCount = matchEdges(M, PB, Counters); - - if (ReadCount != Counters.size()) { - errs() << "WARNING: profile information is inconsistent with " - << "the current program!\n"; - } - NumEdgesRead = ReadCount; - - setBranchWeightMetadata(M, PB); - - return ReadCount > 0; -} diff --git a/lib/Analysis/ProfileEstimatorPass.cpp b/lib/Analysis/ProfileEstimatorPass.cpp deleted file mode 100644 index 365b64c0ae..0000000000 --- a/lib/Analysis/ProfileEstimatorPass.cpp +++ /dev/null @@ -1,426 +0,0 @@ -//===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements a concrete implementation of profiling information that -// estimates the profiling information in a very crude and unimaginative way. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "profile-estimator" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/Pass.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -using namespace llvm; - -static cl::opt<double> -LoopWeight( - "profile-estimator-loop-weight", cl::init(10), - cl::value_desc("loop-weight"), - cl::desc("Number of loop executions used for profile-estimator") -); - -namespace { - class ProfileEstimatorPass : public FunctionPass, public ProfileInfo { - double ExecCount; - LoopInfo *LI; - std::set<BasicBlock*> BBToVisit; - std::map<Loop*,double> LoopExitWeights; - std::map<Edge,double> MinimalWeight; - public: - static char ID; // Class identification, replacement for typeinfo - explicit ProfileEstimatorPass(const double execcount = 0) - : FunctionPass(ID), ExecCount(execcount) { - initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry()); - if (execcount == 0) ExecCount = LoopWeight; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired<LoopInfo>(); - } - - virtual const char *getPassName() const { - return "Profiling information estimator"; - } - - /// run - Estimate the profile information from the specified file. - virtual bool runOnFunction(Function &F); - - /// 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 == &ProfileInfo::ID) - return (ProfileInfo*)this; - return this; - } - - virtual void recurseBasicBlock(BasicBlock *BB); - - void inline printEdgeWeight(Edge); - }; -} // End of anonymous namespace - -char ProfileEstimatorPass::ID = 0; -INITIALIZE_AG_PASS_BEGIN(ProfileEstimatorPass, ProfileInfo, "profile-estimator", - "Estimate profiling information", false, true, false) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_AG_PASS_END(ProfileEstimatorPass, ProfileInfo, "profile-estimator", - "Estimate profiling information", false, true, false) - -namespace llvm { - char &ProfileEstimatorPassID = ProfileEstimatorPass::ID; - - FunctionPass *createProfileEstimatorPass() { - return new ProfileEstimatorPass(); - } - - /// createProfileEstimatorPass - This function returns a Pass that estimates - /// profiling information using the given loop execution count. - Pass *createProfileEstimatorPass(const unsigned execcount) { - return new ProfileEstimatorPass(execcount); - } -} - -static double ignoreMissing(double w) { - if (w == ProfileInfo::MissingValue) return 0; - return w; -} - -static void inline printEdgeError(ProfileInfo::Edge e, const char *M) { - DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n"); -} - -void inline ProfileEstimatorPass::printEdgeWeight(Edge E) { - DEBUG(dbgs() << "-- Weight of Edge " << E << ":" - << format("%20.20g", getEdgeWeight(E)) << "\n"); -} - -// recurseBasicBlock() - This calculates the ProfileInfo estimation for a -// single block and then recurses into the successors. -// The algorithm preserves the flow condition, meaning that the sum of the -// weight of the incoming edges must be equal the block weight which must in -// turn be equal to the sume of the weights of the outgoing edges. -// Since the flow of an block is deterimined from the current state of the -// flow, once an edge has a flow assigned this flow is never changed again, -// otherwise it would be possible to violate the flow condition in another -// block. -void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { - - // Break the recursion if this BasicBlock was already visited. - if (BBToVisit.find(BB) == BBToVisit.end()) return; - - // Read the LoopInfo for this block. - bool BBisHeader = LI->isLoopHeader(BB); - Loop* BBLoop = LI->getLoopFor(BB); - - // To get the block weight, read all incoming edges. - double BBWeight = 0; - std::set<BasicBlock*> ProcessedPreds; - for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); - bbi != bbe; ++bbi ) { - // If this block was not considered already, add weight. - Edge edge = getEdge(*bbi,BB); - double w = getEdgeWeight(edge); - if (ProcessedPreds.insert(*bbi).second) { - BBWeight += ignoreMissing(w); - } - // If this block is a loop header and the predecessor is contained in this - // loop, thus the edge is a backedge, continue and do not check if the - // value is valid. - if (BBisHeader && BBLoop->contains(*bbi)) { - printEdgeError(edge, "but is backedge, continuing"); - continue; - } - // If the edges value is missing (and this is no loop header, and this is - // no backedge) return, this block is currently non estimatable. - if (w == MissingValue) { - printEdgeError(edge, "returning"); - return; - } - } - if (getExecutionCount(BB) != MissingValue) { - BBWeight = getExecutionCount(BB); - } - - // Fetch all necessary information for current block. - SmallVector<Edge, 8> ExitEdges; - SmallVector<Edge, 8> Edges; - if (BBLoop) { - BBLoop->getExitEdges(ExitEdges); - } - - // If this is a loop header, consider the following: - // Exactly the flow that is entering this block, must exit this block too. So - // do the following: - // *) get all the exit edges, read the flow that is already leaving this - // loop, remember the edges that do not have any flow on them right now. - // (The edges that have already flow on them are most likely exiting edges of - // other loops, do not touch those flows because the previously caclulated - // loopheaders would not be exact anymore.) - // *) In case there is not a single exiting edge left, create one at the loop - // latch to prevent the flow from building up in the loop. - // *) Take the flow that is not leaving the loop already and distribute it on - // the remaining exiting edges. - // (This ensures that all flow that enters the loop also leaves it.) - // *) Increase the flow into the loop by increasing the weight of this block. - // There is at least one incoming backedge that will bring us this flow later - // on. (So that the flow condition in this node is valid again.) - if (BBisHeader) { - double incoming = BBWeight; - // Subtract the flow leaving the loop. - std::set<Edge> ProcessedExits; - for (SmallVectorImpl<Edge>::iterator ei = ExitEdges.begin(), - ee = ExitEdges.end(); ei != ee; ++ei) { - if (ProcessedExits.insert(*ei).second) { - double w = getEdgeWeight(*ei); - if (w == MissingValue) { - Edges.push_back(*ei); - // Check if there is a necessary minimal weight, if yes, subtract it - // from weight. - if (MinimalWeight.find(*ei) != MinimalWeight.end()) { - incoming -= MinimalWeight[*ei]; - DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n"); - } - } else { - incoming -= w; - } - } - } - // If no exit edges, create one: - if (Edges.size() == 0) { - BasicBlock *Latch = BBLoop->getLoopLatch(); - if (Latch) { - Edge edge = getEdge(Latch,0); - EdgeInformation[BB->getParent()][edge] = BBWeight; - printEdgeWeight(edge); - edge = getEdge(Latch, BB); - EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount; - printEdgeWeight(edge); - } - } - - // Distribute remaining weight to the exting edges. To prevent fractions - // from building up and provoking precision problems the weight which is to - // be distributed is split and the rounded, the last edge gets a somewhat - // bigger value, but we are close enough for an estimation. - double fraction = floor(incoming/Edges.size()); - for (SmallVectorImpl<Edge>::iterator ei = Edges.begin(), ee = Edges.end(); - ei != ee; ++ei) { - double w = 0; - if (ei != (ee-1)) { - w = fraction; - incoming -= fraction; - } else { - w = incoming; - } - EdgeInformation[BB->getParent()][*ei] += w; - // Read necessary minimal weight. - if (MinimalWeight.find(*ei) != MinimalWeight.end()) { - EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei]; - DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n"); - } - printEdgeWeight(*ei); - - // Add minimal weight to paths to all exit edges, this is used to ensure - // that enough flow is reaching this edges. - Path p; - const BasicBlock *Dest = GetPath(BB, (*ei).first, p, GetPathToDest); - while (Dest != BB) { - const BasicBlock *Parent = p.find(Dest)->second; - Edge e = getEdge(Parent, Dest); - if (MinimalWeight.find(e) == MinimalWeight.end()) { - MinimalWeight[e] = 0; - } - MinimalWeight[e] += w; - DEBUG(dbgs() << "Minimal Weight for " << e << ": " << format("%.20g",MinimalWeight[e]) << "\n"); - Dest = Parent; - } - } - // Increase flow into the loop. - BBWeight *= (ExecCount+1); - } - - BlockInformation[BB->getParent()][BB] = BBWeight; - // Up until now we considered only the loop exiting edges, now we have a - // definite block weight and must distribute this onto the outgoing edges. - // Since there may be already flow attached to some of the edges, read this - // flow first and remember the edges that have still now flow attached. - Edges.clear(); - std::set<BasicBlock*> ProcessedSuccs; - - succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - // Also check for (BB,0) edges that may already contain some flow. (But only - // in case there are no successors.) - if (bbi == bbe) { - Edge edge = getEdge(BB,0); - EdgeInformation[BB->getParent()][edge] = BBWeight; - printEdgeWeight(edge); - } - for ( ; bbi != bbe; ++bbi ) { - if (ProcessedSuccs.insert(*bbi).second) { - Edge edge = getEdge(BB,*bbi); - double w = getEdgeWeight(edge); - if (w != MissingValue) { - BBWeight -= getEdgeWeight(edge); - } else { - Edges.push_back(edge); - // If minimal weight is necessary, reserve weight by subtracting weight - // from block weight, this is readded later on. - if (MinimalWeight.find(edge) != MinimalWeight.end()) { - BBWeight -= MinimalWeight[edge]; - DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n"); - } - } - } - } - - double fraction = Edges.size() ? floor(BBWeight/Edges.size()) : 0.0; - // Finally we know what flow is still not leaving the block, distribute this - // flow onto the empty edges. - for (SmallVectorImpl<Edge>::iterator ei = Edges.begin(), ee = Edges.end(); - ei != ee; ++ei) { - if (ei != (ee-1)) { - EdgeInformation[BB->getParent()][*ei] += fraction; - BBWeight -= fraction; - } else { - EdgeInformation[BB->getParent()][*ei] += BBWeight; - } - // Readd minial necessary weight. - if (MinimalWeight.find(*ei) != MinimalWeight.end()) { - EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei]; - DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n"); - } - printEdgeWeight(*ei); - } - - // This block is visited, mark this before the recursion. - BBToVisit.erase(BB); - - // Recurse into successors. - for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - bbi != bbe; ++bbi) { - recurseBasicBlock(*bbi); - } -} - -bool ProfileEstimatorPass::runOnFunction(Function &F) { - if (F.isDeclaration()) return false; - - // Fetch LoopInfo and clear ProfileInfo for this function. - LI = &getAnalysis<LoopInfo>(); - FunctionInformation.erase(&F); - BlockInformation[&F].clear(); - EdgeInformation[&F].clear(); - BBToVisit.clear(); - - // Mark all blocks as to visit. - for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi) - BBToVisit.insert(bi); - - // Clear Minimal Edges. - MinimalWeight.clear(); - - DEBUG(dbgs() << "Working on function " << F.getName() << "\n"); - - // Since the entry block is the first one and has no predecessors, the edge - // (0,entry) is inserted with the starting weight of 1. - BasicBlock *entry = &F.getEntryBlock(); - BlockInformation[&F][entry] = pow(2.0, 32.0); - Edge edge = getEdge(0,entry); - EdgeInformation[&F][edge] = BlockInformation[&F][entry]; - printEdgeWeight(edge); - - // Since recurseBasicBlock() maybe returns with a block which was not fully - // estimated, use recurseBasicBlock() until everything is calculated. - bool cleanup = false; - recurseBasicBlock(entry); - while (BBToVisit.size() > 0 && !cleanup) { - // Remember number of open blocks, this is later used to check if progress - // was made. - unsigned size = BBToVisit.size(); - - // Try to calculate all blocks in turn. - for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(), - be = BBToVisit.end(); bi != be; ++bi) { - recurseBasicBlock(*bi); - // If at least one block was finished, break because iterator may be - // invalid. - if (BBToVisit.size() < size) break; - } - - // If there was not a single block resolved, make some assumptions. - if (BBToVisit.size() == size) { - bool found = false; - for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end(); - (BBI != BBE) && (!found); ++BBI) { - BasicBlock *BB = *BBI; - // Try each predecessor if it can be assumend. - for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); - (bbi != bbe) && (!found); ++bbi) { - Edge e = getEdge(*bbi,BB); - double w = getEdgeWeight(e); - // Check that edge from predecessor is still free. - if (w == MissingValue) { - // Check if there is a circle from this block to predecessor. - Path P; - const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest); - if (Dest != *bbi) { - // If there is no circle, just set edge weight to 0 - EdgeInformation[&F][e] = 0; - DEBUG(dbgs() << "Assuming edge weight: "); - printEdgeWeight(e); - found = true; - } - } - } - } - if (!found) { - cleanup = true; - DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n"); - } - } - } - // In case there was no safe way to assume edges, set as a last measure, - // set _everything_ to zero. - if (cleanup) { - FunctionInformation[&F] = 0; - BlockInformation[&F].clear(); - EdgeInformation[&F].clear(); - for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { - const BasicBlock *BB = &(*FI); - BlockInformation[&F][BB] = 0; - const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB); - if (predi == prede) { - Edge e = getEdge(0,BB); - setEdgeWeight(e,0); - } - for (;predi != prede; ++predi) { - Edge e = getEdge(*predi,BB); - setEdgeWeight(e,0); - } - succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB); - if (succi == succe) { - Edge e = getEdge(BB,0); - setEdgeWeight(e,0); - } - for (;succi != succe; ++succi) { - Edge e = getEdge(*succi,BB); - setEdgeWeight(e,0); - } - } - } - - return false; -} diff --git a/lib/Analysis/ProfileInfo.cpp b/lib/Analysis/ProfileInfo.cpp deleted file mode 100644 index 9626a48b9d..0000000000 --- a/lib/Analysis/ProfileInfo.cpp +++ /dev/null @@ -1,1079 +0,0 @@ -//===- ProfileInfo.cpp - Profile Info Interface ---------------------------===// -// -// 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 abstract ProfileInfo interface, and the default -// "no profile" implementation. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "profile-info" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include <limits> -#include <queue> -#include <set> -using namespace llvm; - -namespace llvm { - template<> char ProfileInfoT<Function,BasicBlock>::ID = 0; -} - -// Register the ProfileInfo interface, providing a nice name to refer to. -INITIALIZE_ANALYSIS_GROUP(ProfileInfo, "Profile Information", NoProfileInfo) - -namespace llvm { - -template <> -ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {} -template <> -ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {} - -template <> -ProfileInfoT<Function, BasicBlock>::ProfileInfoT() { - MachineProfile = 0; -} -template <> -ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() { - if (MachineProfile) delete MachineProfile; -} - -template<> -char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0; - -template<> -const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1; - -template<> const -double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1; - -template<> double -ProfileInfoT<Function,BasicBlock>::getExecutionCount(const BasicBlock *BB) { - std::map<const Function*, BlockCounts>::iterator J = - BlockInformation.find(BB->getParent()); - if (J != BlockInformation.end()) { - BlockCounts::iterator I = J->second.find(BB); - if (I != J->second.end()) - return I->second; - } - - double Count = MissingValue; - - const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB); - - // Are there zero predecessors of this block? - if (PI == PE) { - Edge e = getEdge(0, BB); - Count = getEdgeWeight(e); - } else { - // Otherwise, if there are predecessors, the execution count of this block is - // the sum of the edge frequencies from the incoming edges. - std::set<const BasicBlock*> ProcessedPreds; - Count = 0; - for (; PI != PE; ++PI) { - const BasicBlock *P = *PI; - if (ProcessedPreds.insert(P).second) { - double w = getEdgeWeight(getEdge(P, BB)); - if (w == MissingValue) { - Count = MissingValue; - break; - } - Count += w; - } - } - } - - // If the predecessors did not suffice to get block weight, try successors. - if (Count == MissingValue) { - - succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB); - - // Are there zero successors of this block? - if (SI == SE) { - Edge e = getEdge(BB,0); - Count = getEdgeWeight(e); - } else { - std::set<const BasicBlock*> ProcessedSuccs; - Count = 0; - for (; SI != SE; ++SI) - if (ProcessedSuccs.insert(*SI).second) { - double w = getEdgeWeight(getEdge(BB, *SI)); - if (w == MissingValue) { - Count = MissingValue; - break; - } - Count += w; - } - } - } - - if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count; - return Count; -} - -template<> -double ProfileInfoT<MachineFunction, MachineBasicBlock>:: - getExecutionCount(const MachineBasicBlock *MBB) { - std::map<const MachineFunction*, BlockCounts>::iterator J = - BlockInformation.find(MBB->getParent()); - if (J != BlockInformation.end()) { - BlockCounts::iterator I = J->second.find(MBB); - if (I != J->second.end()) - return I->second; - } - - return MissingValue; -} - -template<> -double ProfileInfoT<Function,BasicBlock>::getExecutionCount(const Function *F) { - std::map<const Function*, double>::iterator J = - FunctionInformation.find(F); - if (J != FunctionInformation.end()) - return J->second; - - // isDeclaration() is checked here and not at start of function to allow - // functions without a body still to have a execution count. - if (F->isDeclaration()) return MissingValue; - - double Count = getExecutionCount(&F->getEntryBlock()); - if (Count != MissingValue) FunctionInformation[F] = Count; - return Count; -} - -template<> -double ProfileInfoT<MachineFunction, MachineBasicBlock>:: - getExecutionCount(const MachineFunction *MF) { - std::map<const MachineFunction*, double>::iterator J = - FunctionInformation.find(MF); - if (J != FunctionInformation.end()) - return J->second; - - double Count = getExecutionCount(&MF->front()); - if (Count != MissingValue) FunctionInformation[MF] = Count; - return Count; -} - -template<> -void ProfileInfoT<Function,BasicBlock>:: - setExecutionCount(const BasicBlock *BB, double w) { - DEBUG(dbgs() << "Creating Block " << BB->getName() - << " (weight: " << format("%.20g",w) << ")\n"); - BlockInformation[BB->getParent()][BB] = w; -} - -template<> -void ProfileInfoT<MachineFunction, MachineBasicBlock>:: - setExecutionCount(const MachineBasicBlock *MBB, double w) { - DEBUG(dbgs() << "Creating Block " << MBB->getBasicBlock()->getName() - << " (weight: " << format("%.20g",w) << ")\n"); - BlockInformation[MBB->getParent()][MBB] = w; -} - -template<> -void ProfileInfoT<Function,BasicBlock>::addEdgeWeight(Edge e, double w) { - double oldw = getEdgeWeight(e); - assert (oldw != MissingValue && "Adding weight to Edge with no previous weight"); - DEBUG(dbgs() << "Adding to Edge " << e - << " (new weight: " << format("%.20g",oldw + w) << ")\n"); - EdgeInformation[getFunction(e)][e] = oldw + w; -} - -template<> -void ProfileInfoT<Function,BasicBlock>:: - addExecutionCount(const BasicBlock *BB, double w) { - double oldw = getExecutionCount(BB); - assert (oldw != MissingValue && "Adding weight to Block with no previous weight"); - DEBUG(dbgs() << "Adding to Block " << BB->getName() - << " (new weight: " << format("%.20g",oldw + w) << ")\n"); - BlockInformation[BB->getParent()][BB] = oldw + w; -} - -template<> -void ProfileInfoT<Function,BasicBlock>::removeBlock(const BasicBlock *BB) { - std::map<const Function*, BlockCounts>::iterator J = - BlockInformation.find(BB->getParent()); - if (J == BlockInformation.end()) return; - - DEBUG(dbgs() << "Deleting " << BB->getName() << "\n"); - J->second.erase(BB); -} - -template<> -void ProfileInfoT<Function,BasicBlock>::removeEdge(Edge e) { - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(getFunction(e)); - if (J == EdgeInformation.end()) return; - - DEBUG(dbgs() << "Deleting" << e << "\n"); - J->second.erase(e); -} - -template<> -void ProfileInfoT<Function,BasicBlock>:: - replaceEdge(const Edge &oldedge, const Edge &newedge) { - double w; - if ((w = getEdgeWeight(newedge)) == MissingValue) { - w = getEdgeWeight(oldedge); - DEBUG(dbgs() << "Replacing " << oldedge << " with " << newedge << "\n"); - } else { - w += getEdgeWeight(oldedge); - DEBUG(dbgs() << "Adding " << oldedge << " to " << newedge << "\n"); - } - setEdgeWeight(newedge,w); - removeEdge(oldedge); -} - -template<> -const BasicBlock *ProfileInfoT<Function,BasicBlock>:: - GetPath(const BasicBlock *Src, const BasicBlock *Dest, - Path &P, unsigned Mode) { - const BasicBlock *BB = 0; - bool hasFoundPath = false; - - std::queue<const BasicBlock *> BFS; - BFS.push(Src); - - while(BFS.size() && !hasFoundPath) { - BB = BFS.front(); - BFS.pop(); - - succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB); - if (Succ == End) { - P[(const BasicBlock*)0] = BB; - if (Mode & GetPathToExit) { - hasFoundPath = true; - BB = 0; - } - } - for(;Succ != End; ++Succ) { - if (P.find(*Succ) != P.end()) continue; - Edge e = getEdge(BB,*Succ); - if ((Mode & GetPathWithNewEdges) && (getEdgeWeight(e) != MissingValue)) continue; - P[*Succ] = BB; - BFS.push(*Succ); - if ((Mode & GetPathToDest) && *Succ == Dest) { - hasFoundPath = true; - BB = *Succ; - break; - } - if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) { - hasFoundPath = true; - BB = *Succ; - break; - } - } - } - - return BB; -} - -template<> -void ProfileInfoT<Function,BasicBlock>:: - divertFlow(const Edge &oldedge, const Edge &newedge) { - DEBUG(dbgs() << "Diverting " << oldedge << " via " << newedge ); - - // First check if the old edge was taken, if not, just delete it... - if (getEdgeWeight(oldedge) == 0) { - removeEdge(oldedge); - return; - } - - Path P; - P[newedge.first] = 0; - P[newedge.second] = newedge.first; - const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest); - - double w = getEdgeWeight (oldedge); - DEBUG(dbgs() << ", Weight: " << format("%.20g",w) << "\n"); - do { - const BasicBlock *Parent = P.find(BB)->second; - Edge e = getEdge(Parent,BB); - double oldw = getEdgeWeight(e); - double oldc = getExecutionCount(e.first); - setEdgeWeight(e, w+oldw); - if (Parent != oldedge.first) { - setExecutionCount(e.first, w+oldc); - } - BB = Parent; - } while (BB != newedge.first); - removeEdge(oldedge); -} - -/// Replaces all occurrences of RmBB in the ProfilingInfo with DestBB. -/// This checks all edges of the function the blocks reside in and replaces the -/// occurrences of RmBB with DestBB. -template<> -void ProfileInfoT<Function,BasicBlock>:: - replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB) { - DEBUG(dbgs() << "Replacing " << RmBB->getName() - << " with " << DestBB->getName() << "\n"); - const Function *F = DestBB->getParent(); - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(F); - if (J == EdgeInformation.end()) return; - - Edge e, newedge; - bool erasededge = false; - EdgeWeights::iterator I = J->second.begin(), E = J->second.end(); - while(I != E) { - e = (I++)->first; - bool foundedge = false; bool eraseedge = false; - if (e.first == RmBB) { - if (e.second == DestBB) { - eraseedge = true; - } else { - newedge = getEdge(DestBB, e.second); - foundedge = true; - } - } - if (e.second == RmBB) { - if (e.first == DestBB) { - eraseedge = true; - } else { - newedge = getEdge(e.first, DestBB); - foundedge = true; - } - } - if (foundedge) { - replaceEdge(e, newedge); - } - if (eraseedge) { - if (erasededge) { - Edge newedge = getEdge(DestBB, DestBB); - replaceEdge(e, newedge); - } else { - removeEdge(e); - erasededge = true; - } - } - } -} - -/// Splits an edge in the ProfileInfo and redirects flow over NewBB. -/// Since its possible that there is more than one edge in the CFG from FristBB -/// to SecondBB its necessary to redirect the flow proporionally. -template<> -void ProfileInfoT<Function,BasicBlock>::splitEdge(const BasicBlock *FirstBB, - const BasicBlock *SecondBB, - const BasicBlock *NewBB, - bool MergeIdenticalEdges) { - const Function *F = FirstBB->getParent(); - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(F); - if (J == EdgeInformation.end()) return; - - // Generate edges and read current weight. - Edge e = getEdge(FirstBB, SecondBB); - Edge n1 = getEdge(FirstBB, NewBB); - Edge n2 = getEdge(NewBB, SecondBB); - EdgeWeights &ECs = J->second; - double w = ECs[e]; - - int succ_count = 0; - if (!MergeIdenticalEdges) { - // First count the edges from FristBB to SecondBB, if there is more than - // one, only slice out a proporional part for NewBB. - for(succ_const_iterator BBI = succ_begin(FirstBB), BBE = succ_end(FirstBB); - BBI != BBE; ++BBI) { - if (*BBI == SecondBB) succ_count++; - } - // When the NewBB is completely new, increment the count by one so that - // the counts are properly distributed. - if (getExecutionCount(NewBB) == ProfileInfo::MissingValue) succ_count++; - } else { - // When the edges are merged anyway, then redirect all flow. - succ_count = 1; - } - - // We know now how many edges there are from FirstBB to SecondBB, reroute a - // proportional part of the edge weight over NewBB. - double neww = floor(w / succ_count); - ECs[n1] += neww; - ECs[n2] += neww; - BlockInformation[F][NewBB] += neww; - if (succ_count == 1) { - ECs.erase(e); - } else { - ECs[e] -= neww; - } -} - -template<> -void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *Old, - const BasicBlock* New) { - const Function *F = Old->getParent(); - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(F); - if (J == EdgeInformation.end()) return; - - DEBUG(dbgs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n"); - - std::set<Edge> Edges; - for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end(); - ewi != ewe; ++ewi) { - Edge old = ewi->first; - if (old.first == Old) { - Edges.insert(old); - } - } - for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end(); - EI != EE; ++EI) { - Edge newedge = getEdge(New, EI->second); - replaceEdge(*EI, newedge); - } - - double w = getExecutionCount(Old); - setEdgeWeight(getEdge(Old, New), w); - setExecutionCount(New, w); -} - -template<> -void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *BB, - const BasicBlock* NewBB, - BasicBlock *const *Preds, - unsigned NumPreds) { - const Function *F = BB->getParent(); - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(F); - if (J == EdgeInformation.end()) return; - - DEBUG(dbgs() << "Splitting " << NumPreds << " Edges from " << BB->getName() - << " to " << NewBB->getName() << "\n"); - - // Collect weight that was redirected over NewBB. - double newweight = 0; - - std::set<const BasicBlock *> ProcessedPreds; - // For all requestes Predecessors. - for (unsigned pred = 0; pred < NumPreds; ++pred) { - const BasicBlock * Pred = Preds[pred]; - if (ProcessedPreds.insert(Pred).second) { - // Create edges and read old weight. - Edge oldedge = getEdge(Pred, BB); - Edge newedge = getEdge(Pred, NewBB); - - // Remember how much weight was redirected. - newweight += getEdgeWeight(oldedge); - - replaceEdge(oldedge,newedge); - } - } - - Edge newedge = getEdge(NewBB,BB); - setEdgeWeight(newedge, newweight); - setExecutionCount(NewBB, newweight); -} - -template<> -void ProfileInfoT<Function,BasicBlock>::transfer(const Function *Old, - const Function *New) { - DEBUG(dbgs() << "Replacing Function " << Old->getName() << " with " - << New->getName() << "\n"); - std::map<const Function*, EdgeWeights>::iterator J = - EdgeInformation.find(Old); - if(J != EdgeInformation.end()) { - EdgeInformation[New] = J->second; - } - EdgeInformation.erase(Old); - BlockInformation.erase(Old); - FunctionInformation.erase(Old); -} - -static double readEdgeOrRemember(ProfileInfo::Edge edge, double w, - ProfileInfo::Edge &tocalc, unsigned &uncalc) { - if (w == ProfileInfo::MissingValue) { - tocalc = edge; - uncalc++; - return 0; - } else { - return w; - } -} - -template<> -bool ProfileInfoT<Function,BasicBlock>:: - CalculateMissingEdge(const BasicBlock *BB, Edge &removed, - bool assumeEmptySelf) { - Edge edgetocalc; - unsigned uncalculated = 0; - - // collect weights of all incoming and outgoing edges, rememer edges that - // have no value - double incount = 0; - SmallSet<const BasicBlock*,8> pred_visited; - const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); - if (bbi==bbe) { - Edge e = getEdge(0,BB); - incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated); - } - for (;bbi != bbe; ++bbi) { - if (pred_visited.insert(*bbi)) { - Edge e = getEdge(*bbi,BB); - incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated); - } - } - - double outcount = 0; - SmallSet<const BasicBlock*,8> succ_visited; - succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB); - if (sbbi==sbbe) { - Edge e = getEdge(BB,0); - if (getEdgeWeight(e) == MissingValue) { - double w = getExecutionCount(BB); - if (w != MissingValue) { - setEdgeWeight(e,w); - removed = e; - } - } - outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated); - } - for (;sbbi != sbbe; ++sbbi) { - if (succ_visited.insert(*sbbi)) { - Edge e = getEdge(BB,*sbbi); - outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated); - } - } - - // if exactly one edge weight was missing, calculate it and remove it from - // spanning tree - if (uncalculated == 0 ) { - return true; - } else - if (uncalculated == 1) { - if (incount < outcount) { - EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount; - } else { - EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount; - } - DEBUG(dbgs() << "--Calc Edge Counter for " << edgetocalc << ": " - << format("%.20g", getEdgeWeight(edgetocalc)) << "\n"); - removed = edgetocalc; - return true; - } else - if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) { - setEdgeWeight(edgetocalc, incount * 10); - removed = edgetocalc; - return true; - } else { - return false; - } -} - -static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::set<ProfileInfo::Edge> &misscount) { - double w = PI->getEdgeWeight(e); - if (w != ProfileInfo::MissingValue) { - calcw += w; - } else { - misscount.insert(e); - } -} - -template<> -bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) { - double inWeight = 0; - std::set<Edge> inMissing; - std::set<const BasicBlock*> ProcessedPreds; - const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); - if (bbi == bbe) { - readEdge(this,getEdge(0,BB),inWeight,inMissing); - } - for( ; bbi != bbe; ++bbi ) { - if (ProcessedPreds.insert(*bbi).second) { - readEdge(this,getEdge(*bbi,BB),inWeight,inMissing); - } - } - - double outWeight = 0; - std::set<Edge> outMissing; - std::set<const BasicBlock*> ProcessedSuccs; - succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB); - if (sbbi == sbbe) - readEdge(this,getEdge(BB,0),outWeight,outMissing); - for ( ; sbbi != sbbe; ++sbbi ) { - if (ProcessedSuccs.insert(*sbbi).second) { - readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing); - } - } - - double share; - std::set<Edge>::iterator ei,ee; - if (inMissing.size() == 0 && outMissing.size() > 0) { - ei = outMissing.begin(); - ee = outMissing.end(); - share = inWeight/outMissing.size(); - setExecutionCount(BB,inWeight); - } else - if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) { - ei = inMissing.begin(); - ee = inMissing.end(); - share = 0; - setExecutionCount(BB,0); - } else - if (inMissing.size() == 0 && outMissing.size() == 0) { - setExecutionCount(BB,outWeight); - return true; - } else { - return false; - } - for ( ; ei != ee; ++ei ) { - setEdgeWeight(*ei,share); - } - return true; -} - -template<> -void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) { -// if (getExecutionCount(&(F->getEntryBlock())) == 0) { -// for (Function::const_iterator FI = F->begin(), FE = F->end(); -// FI != FE; ++FI) { -// const BasicBlock* BB = &(*FI); -// { -// const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB); -// if (NBB == End) { -// setEdgeWeight(getEdge(0,BB),0); -// } -// for(;NBB != End; ++NBB) { -// setEdgeWeight(getEdge(*NBB,BB),0); -// } -// } -// { -// succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); -// if (NBB == End) { -// setEdgeWeight(getEdge(0,BB),0); -// } -// for(;NBB != End; ++NBB) { -// setEdgeWeight(getEdge(*NBB,BB),0); -// } -// } -// } -// return; -// } - // The set of BasicBlocks that are still unvisited. - std::set<const BasicBlock*> Unvisited; - - // The set of return edges (Edges with no successors). - std::set<Edge> ReturnEdges; - double ReturnWeight = 0; - - // First iterate over the whole function and collect: - // 1) The blocks in this function in the Unvisited set. - // 2) The return edges in the ReturnEdges set. - // 3) The flow that is leaving the function already via return edges. - - // Data structure for searching the function. - std::queue<const BasicBlock *> BFS; - const BasicBlock *BB = &(F->getEntryBlock()); - BFS.push(BB); - Unvisited.insert(BB); - - while (BFS.size()) { - BB = BFS.front(); BFS.pop(); - succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); - if (NBB == End) { - Edge e = getEdge(BB,0); - double w = getEdgeWeight(e); - if (w == MissingValue) { - // If the return edge has no value, try to read value from block. - double bw = getExecutionCount(BB); - if (bw != MissingValue) { - setEdgeWeight(e,bw); - ReturnWeight += bw; - } else { - // If both return edge and block provide no value, collect edge. - ReturnEdges.insert(e); - } - } else { - // If the return edge has a proper value, collect it. - ReturnWeight += w; - } - } - for (;NBB != End; ++NBB) { - if (Unvisited.insert(*NBB).second) { - BFS.push(*NBB); - } - } - } - - while (Unvisited.size() > 0) { - unsigned oldUnvisitedCount = Unvisited.size(); - bool FoundPath = false; - - // If there is only one edge left, calculate it. - if (ReturnEdges.size() == 1) { - ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight; - - Edge e = *ReturnEdges.begin(); - setEdgeWeight(e,ReturnWeight); - setExecutionCount(e.first,ReturnWeight); - - Unvisited.erase(e.first); - ReturnEdges.erase(e); - continue; - } - - // Calculate all blocks where only one edge is missing, this may also - // resolve furhter return edges. - std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE) { - const BasicBlock *BB = *FI; ++FI; - Edge e; - if(CalculateMissingEdge(BB,e,true)) { - if (BlockInformation[F].find(BB) == BlockInformation[F].end()) { - setExecutionCount(BB,getExecutionCount(BB)); - } - Unvisited.erase(BB); - if (e.first != 0 && e.second == 0) { - ReturnEdges.erase(e); - ReturnWeight += getEdgeWeight(e); - } - } - } - if (oldUnvisitedCount > Unvisited.size()) continue; - - // Estimate edge weights by dividing the flow proportionally. - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE) { - const BasicBlock *BB = *FI; ++FI; - const BasicBlock *Dest = 0; - bool AllEdgesHaveSameReturn = true; - // Check each Successor, these must all end up in the same or an empty - // return block otherwise its dangerous to do an estimation on them. - for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB); - Succ != End; ++Succ) { - Path P; - GetPath(*Succ, 0, P, GetPathToExit); - if (Dest && Dest != P[(const BasicBlock*)0]) { - AllEdgesHaveSameReturn = false; - } - Dest = P[(const BasicBlock*)0]; - } - if (AllEdgesHaveSameReturn) { - if(EstimateMissingEdges(BB)) { - Unvisited.erase(BB); - break; - } - } - } - if (oldUnvisitedCount > Unvisited.size()) continue; - - // Check if there is a path to an block that has a known value and redirect - // flow accordingly. - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE && !FoundPath) { - // Fetch path. - const BasicBlock *BB = *FI; ++FI; - Path P; - const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue); - - // Calculate incoming flow. - double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0; - std::set<const BasicBlock *> Processed; - for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB); - NBB != End; ++NBB) { - if (Processed.insert(*NBB).second) { - Edge e = getEdge(*NBB, BB); - double ew = getEdgeWeight(e); - if (ew != MissingValue) { - iw += ew; - invalid++; - } else { - // If the path contains the successor, this means its a backedge, - // do not count as missing. - if (P.find(*NBB) == P.end()) - inmissing++; - } - incount++; - } - } - if (inmissing == incount) continue; - if (invalid == 0) continue; - - // Subtract (already) outgoing flow. - Processed.clear(); - for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); - NBB != End; ++NBB) { - if (Processed.insert(*NBB).second) { - Edge e = getEdge(BB, *NBB); - double ew = getEdgeWeight(e); - if (ew != MissingValue) { - iw -= ew; - } - } - } - if (iw < 0) continue; - - // Check the receiving end of the path if it can handle the flow. - double ow = getExecutionCount(Dest); - Processed.clear(); - for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); - NBB != End; ++NBB) { - if (Processed.insert(*NBB).second) { - Edge e = getEdge(BB, *NBB); - double ew = getEdgeWeight(e); - if (ew != MissingValue) { - ow -= ew; - } - } - } - if (ow < 0) continue; - - // Determine how much flow shall be used. - double ew = getEdgeWeight(getEdge(P[Dest],Dest)); - if (ew != MissingValue) { - ew = ew<ow?ew:ow; - ew = ew<iw?ew:iw; - } else { - if (inmissing == 0) - ew = iw; - } - - // Create flow. - if (ew != MissingValue) { - do { - Edge e = getEdge(P[Dest],Dest); - if (getEdgeWeight(e) == MissingValue) { - setEdgeWeight(e,ew); - FoundPath = true; - } - Dest = P[Dest]; - } while (Dest != BB); - } - } - if (FoundPath) continue; - - // Calculate a block with self loop. - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE && !FoundPath) { - const BasicBlock *BB = *FI; ++FI; - bool SelfEdgeFound = false; - for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB); - NBB != End; ++NBB) { - if (*NBB == BB) { - SelfEdgeFound = true; - break; - } - } - if (SelfEdgeFound) { - Edge e = getEdge(BB,BB); - if (getEdgeWeight(e) == MissingValue) { - double iw = 0; - std::set<const BasicBlock *> Processed; - for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB); - NBB != End; ++NBB) { - if (Processed.insert(*NBB).second) { - Edge e = getEdge(*NBB, BB); - double ew = getEdgeWeight(e); - if (ew != MissingValue) { - iw += ew; - } - } - } - setEdgeWeight(e,iw * 10); - FoundPath = true; - } - } - } - if (FoundPath) continue; - - // Determine backedges, set them to zero. - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE && !FoundPath) { - const BasicBlock *BB = *FI; ++FI; - const BasicBlock *Dest = 0; - Path P; - bool BackEdgeFound = false; - for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB); - NBB != End; ++NBB) { - Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges); - if (Dest == *NBB) { - BackEdgeFound = true; - break; - } - } - if (BackEdgeFound) { - Edge e = getEdge(Dest,BB); - double w = getEdgeWeight(e); - if (w == MissingValue) { - setEdgeWeight(e,0); - FoundPath = true; - } - do { - Edge e = getEdge(P[Dest], Dest); - double w = getEdgeWeight(e); - if (w == MissingValue) { - setEdgeWeight(e,0); - FoundPath = true; - } - Dest = P[Dest]; - } while (Dest != BB); - } - } - if (FoundPath) continue; - - // Channel flow to return block. - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE && !FoundPath) { - const BasicBlock *BB = *FI; ++FI; - - Path P; - const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges); - Dest = P[(const BasicBlock*)0]; - if (!Dest) continue; - - if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) { - // Calculate incoming flow. - double iw = 0; - std::set<const BasicBlock *> Processed; - for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB); - NBB != End; ++NBB) { - if (Processed.insert(*NBB).second) { - Edge e = getEdge(*NBB, BB); - double ew = getEdgeWeight(e); - if (ew != MissingValue) { - iw += ew; - } - } - } - do { - Edge e = getEdge(P[Dest], Dest); - double w = getEdgeWeight(e); - if (w == MissingValue) { - setEdgeWeight(e,iw); - FoundPath = true; - } else { - assert(0 && "Edge should not have value already!"); - } - Dest = P[Dest]; - } while (Dest != BB); - } - } - if (FoundPath) continue; - - // Speculatively set edges to zero. - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE && !FoundPath) { - const BasicBlock *BB = *FI; ++FI; - - for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB); - NBB != End; ++NBB) { - Edge e = getEdge(*NBB,BB); - double w = getEdgeWeight(e); - if (w == MissingValue) { - setEdgeWeight(e,0); - FoundPath = true; - break; - } - } - } - if (FoundPath) continue; - - errs() << "{"; - FI = Unvisited.begin(), FE = Unvisited.end(); - while(FI != FE) { - const BasicBlock *BB = *FI; ++FI; - dbgs() << BB->getName(); - if (FI != FE) - dbgs() << ","; - } - errs() << "}"; - - errs() << "ASSERT: could not repair function"; - assert(0 && "could not repair function"); - } - - EdgeWeights J = EdgeInformation[F]; - for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) { - Edge e = EI->first; - - bool SuccFound = false; - if (e.first != 0) { - succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first); - if (NBB == End) { - if (0 == e.second) { - SuccFound = true; - } - } - for (;NBB != End; ++NBB) { - if (*NBB == e.second) { - SuccFound = true; - break; - } - } - if (!SuccFound) { - removeEdge(e); - } - } - } -} - -raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) { - return O << MF->getFunction()->getName() << "(MF)"; -} - -raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) { - return O << MBB->getBasicBlock()->getName() << "(MB)"; -} - -raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) { - O << "("; - - if (E.first) - O << E.first; - else - O << "0"; - - O << ","; - - if (E.second) - O << E.second; - else - O << "0"; - - return O << ")"; -} - -} // namespace llvm - -//===----------------------------------------------------------------------===// -// NoProfile ProfileInfo implementation -// - -namespace { - struct NoProfileInfo : public ImmutablePass, public ProfileInfo { - static char ID; // Class identification, replacement for typeinfo - NoProfileInfo() : ImmutablePass(ID) { - initializeNoProfileInfoPass(*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 == &ProfileInfo::ID) - return (ProfileInfo*)this; - return this; - } - - virtual const char *getPassName() const { - return "NoProfileInfo"; - } - }; -} // End of anonymous namespace - -char NoProfileInfo::ID = 0; -// Register this pass... -INITIALIZE_AG_PASS(NoProfileInfo, ProfileInfo, "no-profile", - "No Profile Information", false, true, true) - -ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); } diff --git a/lib/Analysis/ProfileInfoLoader.cpp b/lib/Analysis/ProfileInfoLoader.cpp deleted file mode 100644 index f1f3e940c9..0000000000 --- a/lib/Analysis/ProfileInfoLoader.cpp +++ /dev/null @@ -1,155 +0,0 @@ -//===- ProfileInfoLoad.cpp - Load profile information from disk -----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// The ProfileInfoLoader class is used to load and represent profiling -// information read in from the dump file. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/ProfileInfoLoader.h" -#include "llvm/Analysis/ProfileInfoTypes.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/raw_ostream.h" -#include <cstdio> -#include <cstdlib> -using namespace llvm; - -// ByteSwap - Byteswap 'Var' if 'Really' is true. -// -static inline unsigned ByteSwap(unsigned Var, bool Really) { - if (!Really) return Var; - return ((Var & (255U<< 0U)) << 24U) | - ((Var & (255U<< 8U)) << 8U) | - ((Var & (255U<<16U)) >> 8U) | - ((Var & (255U<<24U)) >> 24U); -} - -static unsigned AddCounts(unsigned A, unsigned B) { - // If either value is undefined, use the other. - if (A == ProfileInfoLoader::Uncounted) return B; - if (B == ProfileInfoLoader::Uncounted) return A; - return A + B; -} - -static void ReadProfilingBlock(const char *ToolName, FILE *F, - bool ShouldByteSwap, - std::vector<unsigned> &Data) { - // Read the number of entries... - unsigned NumEntries; - if (fread(&NumEntries, sizeof(unsigned), 1, F) != 1) { - errs() << ToolName << ": data packet truncated!\n"; - perror(0); - exit(1); - } - NumEntries = ByteSwap(NumEntries, ShouldByteSwap); - - // Read the counts... - std::vector<unsigned> TempSpace(NumEntries); - - // Read in the block of data... - if (fread(&TempSpace[0], sizeof(unsigned)*NumEntries, 1, F) != 1) { - errs() << ToolName << ": data packet truncated!\n"; - perror(0); - exit(1); - } - - // Make sure we have enough space... The space is initialised to -1 to - // facitiltate the loading of missing values for OptimalEdgeProfiling. - if (Data.size() < NumEntries) - Data.resize(NumEntries, ProfileInfoLoader::Uncounted); - - // Accumulate the data we just read into the data. - if (!ShouldByteSwap) { - for (unsigned i = 0; i != NumEntries; ++i) { - Data[i] = AddCounts(TempSpace[i], Data[i]); - } - } else { - for (unsigned i = 0; i != NumEntries; ++i) { - Data[i] = AddCounts(ByteSwap(TempSpace[i], true), Data[i]); - } - } -} - -const unsigned ProfileInfoLoader::Uncounted = ~0U; - -// ProfileInfoLoader ctor - Read the specified profiling data file, exiting the -// program if the file is invalid or broken. -// -ProfileInfoLoader::ProfileInfoLoader(const char *ToolName, - const std::string &Filename) - : Filename(Filename) { - FILE *F = fopen(Filename.c_str(), "rb"); - if (F == 0) { - errs() << ToolName << ": Error opening '" << Filename << "': "; - perror(0); - exit(1); - } - - // Keep reading packets until we run out of them. - unsigned PacketType; - while (fread(&PacketType, sizeof(unsigned), 1, F) == 1) { - // If the low eight bits of the packet are zero, we must be dealing with an - // endianness mismatch. Byteswap all words read from the profiling - // information. - bool ShouldByteSwap = (char)PacketType == 0; - PacketType = ByteSwap(PacketType, ShouldByteSwap); - - switch (PacketType) { - case ArgumentInfo: { - unsigned ArgLength; - if (fread(&ArgLength, sizeof(unsigned), 1, F) != 1) { - errs() << ToolName << ": arguments packet truncated!\n"; - perror(0); - exit(1); - } - ArgLength = ByteSwap(ArgLength, ShouldByteSwap); - - // Read in the arguments... - std::vector<char> Chars(ArgLength+4); - - if (ArgLength) - if (fread(&Chars[0], (ArgLength+3) & ~3, 1, F) != 1) { - errs() << ToolName << ": arguments packet truncated!\n"; - perror(0); - exit(1); - } - CommandLines.push_back(std::string(&Chars[0], &Chars[ArgLength])); - break; - } - - case FunctionInfo: - ReadProfilingBlock(ToolName, F, ShouldByteSwap, FunctionCounts); - break; - - case BlockInfo: - ReadProfilingBlock(ToolName, F, ShouldByteSwap, BlockCounts); - break; - - case EdgeInfo: - ReadProfilingBlock(ToolName, F, ShouldByteSwap, EdgeCounts); - break; - - case OptEdgeInfo: - ReadProfilingBlock(ToolName, F, ShouldByteSwap, OptimalEdgeCounts); - break; - - case BBTraceInfo: - ReadProfilingBlock(ToolName, F, ShouldByteSwap, BBTrace); - break; - - default: - errs() << ToolName << ": Unknown packet type #" << PacketType << "!\n"; - exit(1); - } - } - - fclose(F); -} - diff --git a/lib/Analysis/ProfileInfoLoaderPass.cpp b/lib/Analysis/ProfileInfoLoaderPass.cpp deleted file mode 100644 index 346f8d6d62..0000000000 --- a/lib/Analysis/ProfileInfoLoaderPass.cpp +++ /dev/null @@ -1,267 +0,0 @@ -//===- ProfileInfoLoaderPass.cpp - LLVM Pass to load profile info ---------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements a concrete implementation of profiling information that -// loads the information from a profile dump file. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "profile-loader" -#include "llvm/Analysis/Passes.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/Analysis/ProfileInfoLoader.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -#include <set> -using namespace llvm; - -STATISTIC(NumEdgesRead, "The # of edges read."); - -static cl::opt<std::string> -ProfileInfoFilename("profile-info-file", cl::init("llvmprof.out"), - cl::value_desc("filename"), - cl::desc("Profile file loaded by -profile-loader")); - -namespace { - class LoaderPass : public ModulePass, public ProfileInfo { - std::string Filename; - std::set<Edge> SpanningTree; - std::set<const BasicBlock*> BBisUnvisited; - unsigned ReadCount; - public: - static char ID; // Class identification, replacement for typeinfo - explicit LoaderPass(const std::string &filename = "") - : ModulePass(ID), Filename(filename) { - initializeLoaderPassPass(*PassRegistry::getPassRegistry()); - if (filename.empty()) Filename = ProfileInfoFilename; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - - virtual const char *getPassName() const { - return "Profiling information loader"; - } - - // recurseBasicBlock() - Calculates the edge weights for as much basic - // blocks as possbile. - virtual void recurseBasicBlock(const BasicBlock *BB); - virtual void readEdgeOrRemember(Edge, Edge&, unsigned &, double &); - virtual void readEdge(ProfileInfo::Edge, std::vector<unsigned>&); - - /// 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 == &ProfileInfo::ID) - return (ProfileInfo*)this; - return this; - } - - /// run - Load the profile information from the specified file. - virtual bool runOnModule(Module &M); - }; -} // End of anonymous namespace - -char LoaderPass::ID = 0; -INITIALIZE_AG_PASS(LoaderPass, ProfileInfo, "profile-loader", - "Load profile information from llvmprof.out", false, true, false) - -char &llvm::ProfileLoaderPassID = LoaderPass::ID; - -ModulePass *llvm::createProfileLoaderPass() { return new LoaderPass(); } - -/// createProfileLoaderPass - This function returns a Pass that loads the -/// profiling information for the module from the specified filename, making it -/// available to the optimizers. -Pass *llvm::createProfileLoaderPass(const std::string &Filename) { - return new LoaderPass(Filename); -} - -void LoaderPass::readEdgeOrRemember(Edge edge, Edge &tocalc, - unsigned &uncalc, double &count) { - double w; - if ((w = getEdgeWeight(edge)) == MissingValue) { - tocalc = edge; - uncalc++; - } else { - count+=w; - } -} - -// recurseBasicBlock - Visits all neighbours of a block and then tries to -// calculate the missing edge values. -void LoaderPass::recurseBasicBlock(const BasicBlock *BB) { - - // break recursion if already visited - if (BBisUnvisited.find(BB) == BBisUnvisited.end()) return; - BBisUnvisited.erase(BB); - if (!BB) return; - - for (succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - bbi != bbe; ++bbi) { - recurseBasicBlock(*bbi); - } - for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); - bbi != bbe; ++bbi) { - recurseBasicBlock(*bbi); - } - - Edge tocalc; - if (CalculateMissingEdge(BB, tocalc)) { - SpanningTree.erase(tocalc); - } -} - -void LoaderPass::readEdge(ProfileInfo::Edge e, - std::vector<unsigned> &ECs) { - if (ReadCount < ECs.size()) { - double weight = ECs[ReadCount++]; - if (weight != ProfileInfoLoader::Uncounted) { - // Here the data realm changes from the unsigned of the file to the - // double of the ProfileInfo. This conversion is save because we know - // that everything thats representable in unsinged is also representable - // in double. - EdgeInformation[getFunction(e)][e] += (double)weight; - - DEBUG(dbgs() << "--Read Edge Counter for " << e - << " (# "<< (ReadCount-1) << "): " - << (unsigned)getEdgeWeight(e) << "\n"); - } else { - // This happens only if reading optimal profiling information, not when - // reading regular profiling information. - SpanningTree.insert(e); - } - } -} - -bool LoaderPass::runOnModule(Module &M) { - ProfileInfoLoader PIL("profile-loader", Filename); - - EdgeInformation.clear(); - std::vector<unsigned> Counters = PIL.getRawEdgeCounts(); - if (Counters.size() > 0) { - ReadCount = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - DEBUG(dbgs() << "Working on " << F->getName() << "\n"); - readEdge(getEdge(0,&F->getEntryBlock()), Counters); - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - TerminatorInst *TI = BB->getTerminator(); - for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { - readEdge(getEdge(BB,TI->getSuccessor(s)), Counters); - } - } - } - if (ReadCount != Counters.size()) { - errs() << "WARNING: profile information is inconsistent with " - << "the current program!\n"; - } - NumEdgesRead = ReadCount; - } - - Counters = PIL.getRawOptimalEdgeCounts(); - if (Counters.size() > 0) { - ReadCount = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - DEBUG(dbgs() << "Working on " << F->getName() << "\n"); - readEdge(getEdge(0,&F->getEntryBlock()), Counters); - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - TerminatorInst *TI = BB->getTerminator(); - if (TI->getNumSuccessors() == 0) { - readEdge(getEdge(BB,0), Counters); - } - for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { - readEdge(getEdge(BB,TI->getSuccessor(s)), Counters); - } - } - while (SpanningTree.size() > 0) { - - unsigned size = SpanningTree.size(); - - BBisUnvisited.clear(); - for (std::set<Edge>::iterator ei = SpanningTree.begin(), - ee = SpanningTree.end(); ei != ee; ++ei) { - BBisUnvisited.insert(ei->first); - BBisUnvisited.insert(ei->second); - } - while (BBisUnvisited.size() > 0) { - recurseBasicBlock(*BBisUnvisited.begin()); - } - - if (SpanningTree.size() == size) { - DEBUG(dbgs()<<"{"); - for (std::set<Edge>::iterator ei = SpanningTree.begin(), - ee = SpanningTree.end(); ei != ee; ++ei) { - DEBUG(dbgs()<< *ei <<","); - } - assert(0 && "No edge calculated!"); - } - - } - } - if (ReadCount != Counters.size()) { - errs() << "WARNING: profile information is inconsistent with " - << "the current program!\n"; - } - NumEdgesRead = ReadCount; - } - - BlockInformation.clear(); - Counters = PIL.getRawBlockCounts(); - if (Counters.size() > 0) { - ReadCount = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - if (ReadCount < Counters.size()) - // Here the data realm changes from the unsigned of the file to the - // double of the ProfileInfo. This conversion is save because we know - // that everything thats representable in unsinged is also - // representable in double. - BlockInformation[F][BB] = (double)Counters[ReadCount++]; - } - if (ReadCount != Counters.size()) { - errs() << "WARNING: profile information is inconsistent with " - << "the current program!\n"; - } - } - - FunctionInformation.clear(); - Counters = PIL.getRawFunctionCounts(); - if (Counters.size() > 0) { - ReadCount = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - if (ReadCount < Counters.size()) - // Here the data realm changes from the unsigned of the file to the - // double of the ProfileInfo. This conversion is save because we know - // that everything thats representable in unsinged is also - // representable in double. - FunctionInformation[F] = (double)Counters[ReadCount++]; - } - if (ReadCount != Counters.size()) { - errs() << "WARNING: profile information is inconsistent with " - << "the current program!\n"; - } - } - - return false; -} diff --git a/lib/Analysis/ProfileVerifierPass.cpp b/lib/Analysis/ProfileVerifierPass.cpp deleted file mode 100644 index c8896de893..0000000000 --- a/lib/Analysis/ProfileVerifierPass.cpp +++ /dev/null @@ -1,383 +0,0 @@ -//===- ProfileVerifierPass.cpp - LLVM Pass to estimate profile info -------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements a pass that checks profiling information for -// plausibility. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "profile-verifier" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/CallSite.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/InstIterator.h" -#include "llvm/Support/raw_ostream.h" -#include <set> -using namespace llvm; - -static cl::opt<bool,false> -ProfileVerifierDisableAssertions("profile-verifier-noassert", - cl::desc("Disable assertions")); - -namespace { - template<class FType, class BType> - class ProfileVerifierPassT : public FunctionPass { - - struct DetailedBlockInfo { - const BType *BB; - double BBWeight; - double inWeight; - int inCount; - double outWeight; - int outCount; - }; - - ProfileInfoT<FType, BType> *PI; - std::set<const BType*> BBisVisited; - std::set<const FType*> FisVisited; - bool DisableAssertions; - - // When debugging is enabled, the verifier prints a whole slew of debug - // information, otherwise its just the assert. These are all the helper - // functions. - bool PrintedDebugTree; - std::set<const BType*> BBisPrinted; - void debugEntry(DetailedBlockInfo*); - void printDebugInfo(const BType *BB); - - public: - static char ID; // Class identification, replacement for typeinfo - - explicit ProfileVerifierPassT () : FunctionPass(ID) { - initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry()); - DisableAssertions = ProfileVerifierDisableAssertions; - } - explicit ProfileVerifierPassT (bool da) : FunctionPass(ID), - DisableAssertions(da) { - initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry()); - } - - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired<ProfileInfoT<FType, BType> >(); - } - - const char *getPassName() const { - return "Profiling information verifier"; - } - - /// run - Verify the profile information. - bool runOnFunction(FType &F); - void recurseBasicBlock(const BType*); - - bool exitReachable(const FType*); - double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge); - void CheckValue(bool, const char*, DetailedBlockInfo*); - }; - - typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass; - - template<class FType, class BType> - void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) { - - if (BBisPrinted.find(BB) != BBisPrinted.end()) return; - - double BBWeight = PI->getExecutionCount(BB); - if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; } - double inWeight = 0; - int inCount = 0; - std::set<const BType*> ProcessedPreds; - for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); - bbi != bbe; ++bbi ) { - if (ProcessedPreds.insert(*bbi).second) { - typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB); - double EdgeWeight = PI->getEdgeWeight(E); - if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; } - dbgs() << "calculated in-edge " << E << ": " - << format("%20.20g",EdgeWeight) << "\n"; - inWeight += EdgeWeight; - inCount++; - } - } - double outWeight = 0; - int outCount = 0; - std::set<const BType*> ProcessedSuccs; - for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - bbi != bbe; ++bbi ) { - if (ProcessedSuccs.insert(*bbi).second) { - typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi); - double EdgeWeight = PI->getEdgeWeight(E); - if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; } - dbgs() << "calculated out-edge " << E << ": " - << format("%20.20g",EdgeWeight) << "\n"; - outWeight += EdgeWeight; - outCount++; - } - } - dbgs() << "Block " << BB->getName() << " in " - << BB->getParent()->getName() << ":" - << "BBWeight=" << format("%20.20g",BBWeight) << "," - << "inWeight=" << format("%20.20g",inWeight) << "," - << "inCount=" << inCount << "," - << "outWeight=" << format("%20.20g",outWeight) << "," - << "outCount" << outCount << "\n"; - - // mark as visited and recurse into subnodes - BBisPrinted.insert(BB); - for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - bbi != bbe; ++bbi ) { - printDebugInfo(*bbi); - } - } - - template<class FType, class BType> - void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) { - dbgs() << "TROUBLE: Block " << DI->BB->getName() << " in " - << DI->BB->getParent()->getName() << ":" - << "BBWeight=" << format("%20.20g",DI->BBWeight) << "," - << "inWeight=" << format("%20.20g",DI->inWeight) << "," - << "inCount=" << DI->inCount << "," - << "outWeight=" << format("%20.20g",DI->outWeight) << "," - << "outCount=" << DI->outCount << "\n"; - if (!PrintedDebugTree) { - PrintedDebugTree = true; - printDebugInfo(&(DI->BB->getParent()->getEntryBlock())); - } - } - - // This compares A and B for equality. - static bool Equals(double A, double B) { - return A == B; - } - - // This checks if the function "exit" is reachable from an given function - // via calls, this is necessary to check if a profile is valid despite the - // counts not fitting exactly. - template<class FType, class BType> - bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) { - if (!F) return false; - - if (FisVisited.count(F)) return false; - - FType *Exit = F->getParent()->getFunction("exit"); - if (Exit == F) { - return true; - } - - FisVisited.insert(F); - bool exits = false; - for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { - if (const CallInst *CI = dyn_cast<CallInst>(&*I)) { - FType *F = CI->getCalledFunction(); - if (F) { - exits |= exitReachable(F); - } else { - // This is a call to a pointer, all bets are off... - exits = true; - } - if (exits) break; - } - } - return exits; - } - - #define ASSERTMESSAGE(M) \ - { dbgs() << "ASSERT:" << (M) << "\n"; \ - if (!DisableAssertions) assert(0 && (M)); } - - template<class FType, class BType> - double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) { - double EdgeWeight = PI->getEdgeWeight(E); - if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { - dbgs() << "Edge " << E << " in Function " - << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": "; - ASSERTMESSAGE("Edge has missing value"); - return 0; - } else { - if (EdgeWeight < 0) { - dbgs() << "Edge " << E << " in Function " - << ProfileInfoT<FType, BType>::getFunction(E)->getName() << ": "; - ASSERTMESSAGE("Edge has negative value"); - } - return EdgeWeight; - } - } - - template<class FType, class BType> - void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error, - const char *Message, - DetailedBlockInfo *DI) { - if (Error) { - DEBUG(debugEntry(DI)); - dbgs() << "Block " << DI->BB->getName() << " in Function " - << DI->BB->getParent()->getName() << ": "; - ASSERTMESSAGE(Message); - } - return; - } - - // This calculates the Information for a block and then recurses into the - // successors. - template<class FType, class BType> - void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) { - - // Break the recursion by remembering all visited blocks. - if (BBisVisited.find(BB) != BBisVisited.end()) return; - - // Use a data structure to store all the information, this can then be handed - // to debug printers. - DetailedBlockInfo DI; - DI.BB = BB; - DI.outCount = DI.inCount = 0; - DI.inWeight = DI.outWeight = 0; - - // Read predecessors. - std::set<const BType*> ProcessedPreds; - const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB); - // If there are none, check for (0,BB) edge. - if (bpi == bpe) { - DI.inWeight += ReadOrAssert(PI->getEdge(0,BB)); - DI.inCount++; - } - for (;bpi != bpe; ++bpi) { - if (ProcessedPreds.insert(*bpi).second) { - DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB)); - DI.inCount++; - } - } - - // Read successors. - std::set<const BType*> ProcessedSuccs; - succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - // If there is an (0,BB) edge, consider it too. (This is done not only when - // there are no successors, but every time; not every function contains - // return blocks with no successors (think loop latch as return block)). - double w = PI->getEdgeWeight(PI->getEdge(BB,0)); - if (w != ProfileInfoT<FType, BType>::MissingValue) { - DI.outWeight += w; - DI.outCount++; - } - for (;bbi != bbe; ++bbi) { - if (ProcessedSuccs.insert(*bbi).second) { - DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi)); - DI.outCount++; - } - } - - // Read block weight. - DI.BBWeight = PI->getExecutionCount(BB); - CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue, - "BasicBlock has missing value", &DI); - CheckValue(DI.BBWeight < 0, - "BasicBlock has negative value", &DI); - - // Check if this block is a setjmp target. - bool isSetJmpTarget = false; - if (DI.outWeight > DI.inWeight) { - for (typename BType::const_iterator i = BB->begin(), ie = BB->end(); - i != ie; ++i) { - if (const CallInst *CI = dyn_cast<CallInst>(&*i)) { - FType *F = CI->getCalledFunction(); - if (F && (F->getName() == "_setjmp")) { - isSetJmpTarget = true; break; - } - } - } - } - // Check if this block is eventually reaching exit. - bool isExitReachable = false; - if (DI.inWeight > DI.outWeight) { - for (typename BType::const_iterator i = BB->begin(), ie = BB->end(); - i != ie; ++i) { - if (const CallInst *CI = dyn_cast<CallInst>(&*i)) { - FType *F = CI->getCalledFunction(); - if (F) { - FisVisited.clear(); - isExitReachable |= exitReachable(F); - } else { - // This is a call to a pointer, all bets are off... - isExitReachable = true; - } - if (isExitReachable) break; - } - } - } - - if (DI.inCount > 0 && DI.outCount == 0) { - // If this is a block with no successors. - if (!isSetJmpTarget) { - CheckValue(!Equals(DI.inWeight,DI.BBWeight), - "inWeight and BBWeight do not match", &DI); - } - } else if (DI.inCount == 0 && DI.outCount > 0) { - // If this is a block with no predecessors. - if (!isExitReachable) - CheckValue(!Equals(DI.BBWeight,DI.outWeight), - "BBWeight and outWeight do not match", &DI); - } else { - // If this block has successors and predecessors. - if (DI.inWeight > DI.outWeight && !isExitReachable) - CheckValue(!Equals(DI.inWeight,DI.outWeight), - "inWeight and outWeight do not match", &DI); - if (DI.inWeight < DI.outWeight && !isSetJmpTarget) - CheckValue(!Equals(DI.inWeight,DI.outWeight), - "inWeight and outWeight do not match", &DI); - } - - - // Mark this block as visited, rescurse into successors. - BBisVisited.insert(BB); - for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); - bbi != bbe; ++bbi ) { - recurseBasicBlock(*bbi); - } - } - - template<class FType, class BType> - bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) { - PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >(); - if (!PI) - ASSERTMESSAGE("No ProfileInfo available"); - - // Prepare global variables. - PrintedDebugTree = false; - BBisVisited.clear(); - - // Fetch entry block and recurse into it. - const BType *entry = &F.getEntryBlock(); - recurseBasicBlock(entry); - - if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry)) - ASSERTMESSAGE("Function count and entry block count do not match"); - - return false; - } - - template<class FType, class BType> - char ProfileVerifierPassT<FType, BType>::ID = 0; -} - -INITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier", - "Verify profiling information", false, true) -INITIALIZE_AG_DEPENDENCY(ProfileInfo) -INITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier", - "Verify profiling information", false, true) - -namespace llvm { - FunctionPass *createProfileVerifierPass() { - return new ProfileVerifierPass(ProfileVerifierDisableAssertions); - } -} - diff --git a/lib/CodeGen/UnreachableBlockElim.cpp b/lib/CodeGen/UnreachableBlockElim.cpp index a95ebcd16d..f735ef200d 100644 --- a/lib/CodeGen/UnreachableBlockElim.cpp +++ b/lib/CodeGen/UnreachableBlockElim.cpp @@ -24,7 +24,6 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/ProfileInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" @@ -50,7 +49,6 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved<DominatorTree>(); - AU.addPreserved<ProfileInfo>(); } }; } @@ -87,9 +85,7 @@ bool UnreachableBlockElim::runOnFunction(Function &F) { } // Actually remove the blocks now. - ProfileInfo *PI = getAnalysisIfAvailable<ProfileInfo>(); for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { - if (PI) PI->removeBlock(DeadBlocks[i]); DeadBlocks[i]->eraseFromParent(); } diff --git a/lib/Transforms/Instrumentation/CMakeLists.txt b/lib/Transforms/Instrumentation/CMakeLists.txt index 65d41f51fe..71a0ecd0f1 100644 --- a/lib/Transforms/Instrumentation/CMakeLists.txt +++ b/lib/Transforms/Instrumentation/CMakeLists.txt @@ -3,12 +3,9 @@ add_llvm_library(LLVMInstrumentation BoundsChecking.cpp DataFlowSanitizer.cpp DebugIR.cpp - EdgeProfiling.cpp GCOVProfiling.cpp MemorySanitizer.cpp Instrumentation.cpp - OptimalEdgeProfiling.cpp - PathProfiling.cpp ProfilingUtils.cpp ThreadSanitizer.cpp ) diff --git a/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/lib/Transforms/Instrumentation/EdgeProfiling.cpp deleted file mode 100644 index a2459fbafe..0000000000 --- a/lib/Transforms/Instrumentation/EdgeProfiling.cpp +++ /dev/null @@ -1,117 +0,0 @@ -//===- EdgeProfiling.cpp - Insert counters for edge 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 the specified program with counters for edge profiling. -// Edge profiling can give a reasonable approximation of the hot paths through a -// program, and is used for a wide variety of program transformations. -// -// Note that this implementation is very naive. We insert a counter for *every* -// edge in the program, instead of using control flow information to prune the -// number of counters inserted. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "insert-edge-profiling" - -#include "llvm/Transforms/Instrumentation.h" -#include "ProfilingUtils.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include <set> -using namespace llvm; - -STATISTIC(NumEdgesInserted, "The # of edges inserted."); - -namespace { - class EdgeProfiler : public ModulePass { - bool runOnModule(Module &M); - public: - static char ID; // Pass identification, replacement for typeid - EdgeProfiler() : ModulePass(ID) { - initializeEdgeProfilerPass(*PassRegistry::getPassRegistry()); - } - - virtual const char *getPassName() const { - return "Edge Profiler"; - } - }; -} - -char EdgeProfiler::ID = 0; -INITIALIZE_PASS(EdgeProfiler, "insert-edge-profiling", - "Insert instrumentation for edge profiling", false, false) - -ModulePass *llvm::createEdgeProfilerPass() { return new EdgeProfiler(); } - -bool EdgeProfiler::runOnModule(Module &M) { - Function *Main = M.getFunction("main"); - if (Main == 0) { - errs() << "WARNING: cannot insert edge profiling into a module" - << " with no main function!\n"; - return false; // No main, no instrumentation! - } - - std::set<BasicBlock*> BlocksToInstrument; - unsigned NumEdges = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - // Reserve space for (0,entry) edge. - ++NumEdges; - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - // Keep track of which blocks need to be instrumented. We don't want to - // instrument blocks that are added as the result of breaking critical - // edges! - BlocksToInstrument.insert(BB); - NumEdges += BB->getTerminator()->getNumSuccessors(); - } - } - - Type *ATy = ArrayType::get(Type::getInt32Ty(M.getContext()), NumEdges); - GlobalVariable *Counters = - new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, - Constant::getNullValue(ATy), "EdgeProfCounters"); - NumEdgesInserted = NumEdges; - - // Instrument all of the edges... - unsigned i = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - // Create counter for (0,entry) edge. - IncrementCounterInBlock(&F->getEntryBlock(), i++, Counters); - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - if (BlocksToInstrument.count(BB)) { // Don't instrument inserted blocks - // Okay, we have to add a counter of each outgoing edge. If the - // outgoing edge is not critical don't split it, just insert the counter - // in the source or destination of the edge. - TerminatorInst *TI = BB->getTerminator(); - for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { - // If the edge is critical, split it. - SplitCriticalEdge(TI, s, this); - - // Okay, we are guaranteed that the edge is no longer critical. If we - // only have a single successor, insert the counter in this block, - // otherwise insert it in the successor block. - if (TI->getNumSuccessors() == 1) { - // Insert counter at the start of the block - IncrementCounterInBlock(BB, i++, Counters, false); - } else { - // Insert counter at the start of the block - IncrementCounterInBlock(TI->getSuccessor(s), i++, Counters); - } - } - } - } - - // Add the initialization call to main. - InsertProfilingInitCall(Main, "llvm_start_edge_profiling", Counters); - return true; -} - diff --git a/lib/Transforms/Instrumentation/Instrumentation.cpp b/lib/Transforms/Instrumentation/Instrumentation.cpp index 94f7901fb9..b1bea389bb 100644 --- a/lib/Transforms/Instrumentation/Instrumentation.cpp +++ b/lib/Transforms/Instrumentation/Instrumentation.cpp @@ -24,10 +24,7 @@ void llvm::initializeInstrumentation(PassRegistry &Registry) { initializeAddressSanitizerPass(Registry); initializeAddressSanitizerModulePass(Registry); initializeBoundsCheckingPass(Registry); - initializeEdgeProfilerPass(Registry); initializeGCOVProfilerPass(Registry); - initializeOptimalEdgeProfilerPass(Registry); - initializePathProfilerPass(Registry); initializeMemorySanitizerPass(Registry); initializeThreadSanitizerPass(Registry); initializeDataFlowSanitizerPass(Registry); diff --git a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp deleted file mode 100644 index b45aef65bc..0000000000 --- a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp +++ /dev/null @@ -1,225 +0,0 @@ -//===- OptimalEdgeProfiling.cpp - Insert counters for opt. edge 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 the specified program with counters for edge profiling. -// Edge profiling can give a reasonable approximation of the hot paths through a -// program, and is used for a wide variety of program transformations. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "insert-optimal-edge-profiling" -#include "llvm/Transforms/Instrumentation.h" -#include "MaximumSpanningTree.h" -#include "ProfilingUtils.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/Analysis/ProfileInfoLoader.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -using namespace llvm; - -STATISTIC(NumEdgesInserted, "The # of edges inserted."); - -namespace { - class OptimalEdgeProfiler : public ModulePass { - bool runOnModule(Module &M); - public: - static char ID; // Pass identification, replacement for typeid - OptimalEdgeProfiler() : ModulePass(ID) { - initializeOptimalEdgeProfilerPass(*PassRegistry::getPassRegistry()); - } - - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredID(ProfileEstimatorPassID); - AU.addRequired<ProfileInfo>(); - } - - virtual const char *getPassName() const { - return "Optimal Edge Profiler"; - } - }; -} - -char OptimalEdgeProfiler::ID = 0; -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", - "Insert optimal instrumentation for edge profiling", - false, false) - -ModulePass *llvm::createOptimalEdgeProfilerPass() { - return new OptimalEdgeProfiler(); -} - -inline static void printEdgeCounter(ProfileInfo::Edge e, - BasicBlock* b, - unsigned i) { - DEBUG(dbgs() << "--Edge Counter for " << (e) << " in " \ - << ((b)?(b)->getName():"0") << " (# " << (i) << ")\n"); -} - -bool OptimalEdgeProfiler::runOnModule(Module &M) { - Function *Main = M.getFunction("main"); - if (Main == 0) { - errs() << "WARNING: cannot insert edge profiling into a module" - << " with no main function!\n"; - return false; // No main, no instrumentation! - } - - // NumEdges counts all the edges that may be instrumented. Later on its - // decided which edges to actually instrument, to achieve optimal profiling. - // For the entry block a virtual edge (0,entry) is reserved, for each block - // with no successors an edge (BB,0) is reserved. These edges are necessary - // to calculate a truly optimal maximum spanning tree and thus an optimal - // instrumentation. - unsigned NumEdges = 0; - - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - // Reserve space for (0,entry) edge. - ++NumEdges; - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - // Keep track of which blocks need to be instrumented. We don't want to - // instrument blocks that are added as the result of breaking critical - // edges! - if (BB->getTerminator()->getNumSuccessors() == 0) { - // Reserve space for (BB,0) edge. - ++NumEdges; - } else { - NumEdges += BB->getTerminator()->getNumSuccessors(); - } - } - } - - // In the profiling output a counter for each edge is reserved, but only few - // are used. This is done to be able to read back in the profile without - // calulating the maximum spanning tree again, instead each edge counter that - // is not used is initialised with -1 to signal that this edge counter has to - // be calculated from other edge counters on reading the profile info back - // in. - - Type *Int32 = Type::getInt32Ty(M.getContext()); - ArrayType *ATy = ArrayType::get(Int32, NumEdges); - GlobalVariable *Counters = - new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, - Constant::getNullValue(ATy), "OptEdgeProfCounters"); - NumEdgesInserted = 0; - - std::vector<Constant*> Initializer(NumEdges); - Constant *Zero = ConstantInt::get(Int32, 0); - Constant *Uncounted = ConstantInt::get(Int32, ProfileInfoLoader::Uncounted); - - // Instrument all of the edges not in MST... - unsigned i = 0; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) continue; - DEBUG(dbgs() << "Working on " << F->getName() << "\n"); - - // 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. - // 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 = - getAnalysis<ProfileInfo>(*F).getEdgeWeights(F); - std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end()); - MaximumSpanningTree<BasicBlock> MST(EdgeVector); - std::stable_sort(MST.begin(), MST.end()); - - // Check if (0,entry) not in the MST. If not, instrument edge - // (IncrementCounterInBlock()) and set the counter initially to zero, if - // the edge is in the MST the counter is initialised to -1. - - BasicBlock *entry = &(F->getEntryBlock()); - ProfileInfo::Edge edge = ProfileInfo::getEdge(0, entry); - if (!std::binary_search(MST.begin(), MST.end(), edge)) { - printEdgeCounter(edge, entry, i); - IncrementCounterInBlock(entry, i, Counters); ++NumEdgesInserted; - Initializer[i++] = (Zero); - } else{ - Initializer[i++] = (Uncounted); - } - - // InsertedBlocks contains all blocks that were inserted for splitting an - // edge, this blocks do not have to be instrumented. - DenseSet<BasicBlock*> InsertedBlocks; - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { - // Check if block was not inserted and thus does not have to be - // instrumented. - if (InsertedBlocks.count(BB)) continue; - - // Okay, we have to add a counter of each outgoing edge not in MST. If - // the outgoing edge is not critical don't split it, just insert the - // counter in the source or destination of the edge. Also, if the block - // has no successors, the virtual edge (BB,0) is processed. - TerminatorInst *TI = BB->getTerminator(); - if (TI->getNumSuccessors() == 0) { - ProfileInfo::Edge edge = ProfileInfo::getEdge(BB, 0); - if (!std::binary_search(MST.begin(), MST.end(), edge)) { - printEdgeCounter(edge, BB, i); - IncrementCounterInBlock(BB, i, Counters); ++NumEdgesInserted; - Initializer[i++] = (Zero); - } else{ - Initializer[i++] = (Uncounted); - } - } - for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { - BasicBlock *Succ = TI->getSuccessor(s); - ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,Succ); - if (!std::binary_search(MST.begin(), MST.end(), edge)) { - - // If the edge is critical, split it. - bool wasInserted = SplitCriticalEdge(TI, s, this); - Succ = TI->getSuccessor(s); - if (wasInserted) - InsertedBlocks.insert(Succ); - - // Okay, we are guaranteed that the edge is no longer critical. If - // we only have a single successor, insert the counter in this block, - // otherwise insert it in the successor block. - if (TI->getNumSuccessors() == 1) { - // Insert counter at the start of the block - printEdgeCounter(edge, BB, i); - IncrementCounterInBlock(BB, i, Counters); ++NumEdgesInserted; - } else { - // Insert counter at the start of the block - printEdgeCounter(edge, Succ, i); - IncrementCounterInBlock(Succ, i, Counters); ++NumEdgesInserted; - } - Initializer[i++] = (Zero); - } else { - Initializer[i++] = (Uncounted); - } - } - } - } - - // Check if the number of edges counted at first was the number of edges we - // considered for instrumentation. - assert(i == NumEdges && "the number of edges in counting array is wrong"); - - // Assign the now completely defined initialiser to the array. - Constant *init = ConstantArray::get(ATy, Initializer); - Counters->setInitializer(init); - - // Add the initialization call to main. - InsertProfilingInitCall(Main, "llvm_start_opt_edge_profiling", Counters); - return true; -} - diff --git a/lib/Transforms/Instrumentation/PathProfiling.cpp b/lib/Transforms/Instrumentation/PathProfiling.cpp deleted file mode 100644 index 7de73269cf..0000000000 --- a/lib/Transforms/Instrumentation/PathProfiling.cpp +++ /dev/null @@ -1,1424 +0,0 @@ -//===- 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/Transforms/Instrumentation.h" -#include "ProfilingUtils.h" -#include "llvm/Analysis/PathNumbering.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/TypeBuilder.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/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#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 instruments 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 StructType *get(LLVMContext& C) { - return( StructType::get( - 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) - LLVM_ATTRIBUTE_USED; - 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().getName().str(); - 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->getName() : - "unused") << "\n"); - _startingPathNumber = pathNumber; -} - -Value* BLInstrumentationNode::getEndingPathNumber(){ - return(_endingPathNumber); -} - -void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) { - DEBUG(dbgs() << " EPN-" << getName() << " <-- " - << (pathNumber ? pathNumber->getName() : "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->getFirstInsertionPt()); - } 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->getFirstInsertionPt(); - pred_iterator PB = pred_begin(node->getBlock()), - PE = pred_end(node->getBlock()); - PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context), - std::distance(PB, PE), "pathNumber", - insertPoint ); - node->setPathPHI(phi); - node->setStartingPathNumber(phi); - node->setEndingPathNumber(phi); - - for(pred_iterator predIt = PB; predIt != PE; 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->getFirstInsertionPt(); - 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, - "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, "", 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()->getFirstInsertionPt() : - 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()->getFirstInsertionPt() : - 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()->getFirstInsertionPt(); - - // Find the first function call - while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call ) - insertPoint++; - - DEBUG(dbgs() << "\nInstrumenting method call block '" - << node->getBlock()->getName() << "'\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 ) { - 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; - 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); - - 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; - } - - 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->getName() << "\n"); - functionNumber++; - - // set function number - currentFunctionNumber = functionNumber; - runOnFunction(ftInit, *F, M); - } - - Type *t = ftEntryTypeBuilder::get(*Context); - 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"); - 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/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp index 9b56a76962..007e9b79e2 100644 --- a/lib/Transforms/Scalar/CodeGenPrepare.cpp +++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp @@ -22,7 +22,6 @@ #include "llvm/Analysis/DominatorInternals.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" -#include "llvm/Analysis/ProfileInfo.h" #include "llvm/Assembly/Writer.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -80,7 +79,6 @@ namespace { const TargetLowering *TLI; const TargetLibraryInfo *TLInfo; DominatorTree *DT; - ProfileInfo *PFI; /// CurInstIterator - As we scan instructions optimizing them, this is the /// next instruction to optimize. Xforms that can invalidate this should @@ -111,7 +109,6 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved<DominatorTree>(); - AU.addPreserved<ProfileInfo>(); AU.addRequired<TargetLibraryInfo>(); } @@ -151,7 +148,6 @@ bool CodeGenPrepare::runOnFunction(Function &F) { if (TM) TLI = TM->getTargetLowering(); TLInfo = &getAnalysis<TargetLibraryInfo>(); DT = getAnalysisIfAvailable<DominatorTree>(); - PFI = getAnalysisIfAvailable<ProfileInfo>(); OptSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize); @@ -442,10 +438,6 @@ void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { DT->changeImmediateDominator(DestBB, NewIDom); DT->eraseNode(BB); } - if (PFI) { - PFI->replaceAllUses(BB, DestBB); - PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); - } BB->eraseFromParent(); ++NumBlocksElim; diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 8f3ff96d7e..0e7f7f7844 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -22,7 +22,6 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/ProfileInfo.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Type.h" @@ -45,7 +44,6 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved<DominatorTree>(); AU.addPreserved<LoopInfo>(); - AU.addPreserved<ProfileInfo>(); // No loop canonicalization guarantees are broken by this pass. AU.addPreservedID(LoopSimplifyID); @@ -213,10 +211,9 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>(); - ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); // If we have nothing to update, just return. - if (DT == 0 && LI == 0 && PI == 0) + if (DT == 0 && LI == 0) return NewBB; // Now update analysis information. Since the only predecessor of NewBB is @@ -369,9 +366,5 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, } } - // Update ProfileInfo if it is around. - if (PI) - PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges); - return NewBB; } diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 56a2d92d47..82b8da3a10 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -20,7 +20,6 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Analysis/ProfileInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/DIBuilder.h" #include "llvm/DebugInfo.h" @@ -513,11 +512,6 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { DT->changeImmediateDominator(DestBB, PredBBIDom); DT->eraseNode(PredBB); } - ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); - if (PI) { - PI->replaceAllUses(PredBB, DestBB); - PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); - } } // Nuke BB. PredBB->eraseFromParent(); diff --git a/runtime/CMakeLists.txt b/runtime/CMakeLists.txt deleted file mode 100644 index 502b91dc58..0000000000 --- a/runtime/CMakeLists.txt +++ /dev/null @@ -1,5 +0,0 @@ -if( NOT LLVM_BUILD_RUNTIME ) - set(EXCLUDE_FROM_ALL ON) -endif() - -add_subdirectory(libprofile) diff --git a/runtime/LLVMBuild.txt b/runtime/LLVMBuild.txt deleted file mode 100644 index 05334fda50..0000000000 --- a/runtime/LLVMBuild.txt +++ /dev/null @@ -1,21 +0,0 @@ -;===- ./runtime/LLVMBuild.txt ----------------------------------*- Conf -*--===; -; -; The LLVM Compiler Infrastructure -; -; This file is distributed under the University of Illinois Open Source -; License. See LICENSE.TXT for details. -; -;===------------------------------------------------------------------------===; -; -; This is an LLVMBuild description file for the components in this subdirectory. -; -; For more information on the LLVMBuild system, please see: -; -; http://llvm.org/docs/LLVMBuild.html -; -;===------------------------------------------------------------------------===; - -[component_0] -type = Group -name = Runtime -parent = $ROOT diff --git a/runtime/Makefile b/runtime/Makefile deleted file mode 100644 index 6a6c6610a7..0000000000 --- a/runtime/Makefile +++ /dev/null @@ -1,25 +0,0 @@ -##===- runtime/Makefile ------------------------------------*- Makefile -*-===## -# -# The LLVM Compiler Infrastructure -# -# This file is distributed under the University of Illinois Open Source -# License. See LICENSE.TXT for details. -# -##===----------------------------------------------------------------------===## - -LEVEL = .. -include $(LEVEL)/Makefile.config - -ifndef NO_RUNTIME_LIBS - -PARALLEL_DIRS := libprofile - -ifeq ($(TARGET_OS), $(filter $(TARGET_OS), Cygwin MingW Minix)) -PARALLEL_DIRS := $(filter-out libprofile, $(PARALLEL_DIRS)) -endif - -endif - -include $(LEVEL)/Makefile.common - -install:: diff --git a/runtime/README.txt b/runtime/README.txt deleted file mode 100644 index 2e2e547de3..0000000000 --- a/runtime/README.txt +++ /dev/null @@ -1,4 +0,0 @@ -This directory contains the various runtime libraries used by components of -the LLVM compiler. For example, the automatic pool allocation transformation -inserts calls to an external pool allocator library. This runtime library is -an example of the type of library that lives in these directories. diff --git a/runtime/libprofile/BasicBlockTracing.c b/runtime/libprofile/BasicBlockTracing.c deleted file mode 100644 index 0815e2e516..0000000000 --- a/runtime/libprofile/BasicBlockTracing.c +++ /dev/null @@ -1,67 +0,0 @@ -/*===-- BasicBlockTracing.c - Support library for basic block tracing -----===*\ -|* -|* 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 basic block tracing -|* instrumentation pass. This should be used with the -trace-basic-blocks -|* LLVM pass. -|* -\*===----------------------------------------------------------------------===*/ - -#include "Profiling.h" -#include <stdlib.h> -#include <stdio.h> - -static unsigned *ArrayStart, *ArrayEnd, *ArrayCursor; - -/* WriteAndFlushBBTraceData - write out the currently accumulated trace data - * and reset the cursor to point to the beginning of the buffer. - */ -static void WriteAndFlushBBTraceData () { - write_profiling_data(BBTraceInfo, ArrayStart, (ArrayCursor - ArrayStart)); - ArrayCursor = ArrayStart; -} - -/* BBTraceAtExitHandler - When the program exits, just write out any remaining - * data and free the trace buffer. - */ -static void BBTraceAtExitHandler(void) { - WriteAndFlushBBTraceData (); - free (ArrayStart); -} - -/* llvm_trace_basic_block - called upon hitting a new basic block. */ -void llvm_trace_basic_block (unsigned BBNum) { - *ArrayCursor++ = BBNum; - if (ArrayCursor == ArrayEnd) - WriteAndFlushBBTraceData (); -} - -/* llvm_start_basic_block_tracing - This is the main entry point of the basic - * block tracing library. It is responsible for setting up the atexit - * handler and allocating the trace buffer. - */ -int llvm_start_basic_block_tracing(int argc, const char **argv, - unsigned *arrayStart, unsigned numElements) { - int Ret; - const unsigned BufferSize = 128 * 1024; - unsigned ArraySize; - - Ret = save_arguments(argc, argv); - - /* Allocate a buffer to contain BB tracing data */ - ArraySize = BufferSize / sizeof (unsigned); - ArrayStart = malloc (ArraySize * sizeof (unsigned)); - ArrayEnd = ArrayStart + ArraySize; - ArrayCursor = ArrayStart; - - /* Set up the atexit handler. */ - atexit (BBTraceAtExitHandler); - - return Ret; -} diff --git a/runtime/libprofile/CMakeLists.txt b/runtime/libprofile/CMakeLists.txt deleted file mode 100644 index 9044f768e1..0000000000 --- a/runtime/libprofile/CMakeLists.txt +++ /dev/null @@ -1,19 +0,0 @@ -set(SOURCES - BasicBlockTracing.c - CommonProfiling.c - PathProfiling.c - EdgeProfiling.c - OptimalEdgeProfiling.c - Profiling.h - ) - -add_llvm_library( profile_rt-static ${SOURCES} ) -set_target_properties( profile_rt-static - PROPERTIES - OUTPUT_NAME "profile_rt" ) - -set(BUILD_SHARED_LIBS ON) -add_llvm_library( profile_rt-shared ${SOURCES} ) -set_target_properties( profile_rt-shared - PROPERTIES - OUTPUT_NAME "profile_rt" ) diff --git a/runtime/libprofile/CommonProfiling.c b/runtime/libprofile/CommonProfiling.c deleted file mode 100644 index 8f4119c2c6..0000000000 --- a/runtime/libprofile/CommonProfiling.c +++ /dev/null @@ -1,173 +0,0 @@ -/*===-- CommonProfiling.c - Profiling support library support -------------===*\ -|* -|* The LLVM Compiler Infrastructure -|* -|* 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> -#include <stdio.h> -#include <string.h> -#if !defined(_MSC_VER) && !defined(__MINGW32__) -#include <unistd.h> -#else -#include <io.h> -#endif -#include <stdlib.h> - -static char *SavedArgs = 0; -static unsigned SavedArgsLength = 0; -static const char *SavedEnvVar = 0; - -static const char *OutputFilename = "llvmprof.out"; - -/* check_environment_variable - Check to see if the LLVMPROF_OUTPUT environment - * variable is set. If it is then save it and set OutputFilename. - */ -static void check_environment_variable(void) { - const char *EnvVar; - if (SavedEnvVar) return; /* Guarantee that we can't leak memory. */ - - if ((EnvVar = getenv("LLVMPROF_OUTPUT")) != NULL) { - /* The string that getenv returns is allowed to be statically allocated, - * which means it may be changed by future calls to getenv, so copy it. - */ - SavedEnvVar = strdup(EnvVar); - OutputFilename = SavedEnvVar; - } -} - -/* save_arguments - Save argc and argv as passed into the program for the file - * we output. - * If either the LLVMPROF_OUTPUT environment variable or the -llvmprof-output - * command line argument are set then change OutputFilename to the provided - * value. The command line argument value overrides the environment variable. - */ -int save_arguments(int argc, const char **argv) { - unsigned Length, i; - if (!SavedEnvVar && !SavedArgs) check_environment_variable(); - if (SavedArgs || !argv) return argc; /* This can be called multiple times */ - - /* Check to see if there are any arguments passed into the program for the - * profiler. If there are, strip them off and remember their settings. - */ - while (argc > 1 && !strncmp(argv[1], "-llvmprof-", 10)) { - /* Ok, we have an llvmprof argument. Remove it from the arg list and decide - * what to do with it. - */ - const char *Arg = argv[1]; - memmove((char**)&argv[1], &argv[2], (argc-1)*sizeof(char*)); - --argc; - - if (!strcmp(Arg, "-llvmprof-output")) { - if (argc == 1) - puts("-llvmprof-output requires a filename argument!"); - else { - OutputFilename = strdup(argv[1]); - if (SavedEnvVar) { free((void *)SavedEnvVar); SavedEnvVar = 0; } - memmove((char**)&argv[1], &argv[2], (argc-1)*sizeof(char*)); - --argc; - } - } else { - printf("Unknown option to the profiler runtime: '%s' - ignored.\n", Arg); - } - } - - for (Length = 0, i = 0; i != (unsigned)argc; ++i) - Length += strlen(argv[i])+1; - - /* Defensively check for a zero length, even though this is unlikely - * to happen in practice. This avoids calling malloc() below with a - * size of 0. - */ - if (Length == 0) { - SavedArgs = 0; - SavedArgsLength = 0; - return argc; - } - - SavedArgs = (char*)malloc(Length); - for (Length = 0, i = 0; i != (unsigned)argc; ++i) { - unsigned Len = strlen(argv[i]); - memcpy(SavedArgs+Length, argv[i], Len); - Length += Len; - SavedArgs[Length++] = ' '; - } - - SavedArgsLength = Length; - - return argc; -} - - -/* - * Retrieves the file descriptor for the profile file. - */ -int getOutFile() { - static int OutFile = -1; - - /* 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, 0666); - lseek(OutFile, 0, SEEK_END); /* O_APPEND prevents seeking */ - if (OutFile == -1) { - fprintf(stderr, "LLVM profiling runtime: while opening '%s': ", - OutputFilename); - perror(""); - return(OutFile); - } - - /* Output the command line arguments to the file. */ - { - int PTy = ArgumentInfo; - int Zeros = 0; - if (write(OutFile, &PTy, sizeof(int)) < 0 || - write(OutFile, &SavedArgsLength, sizeof(unsigned)) < 0 || - write(OutFile, SavedArgs, SavedArgsLength) < 0 ) { - fprintf(stderr,"error: unable to write to output file."); - exit(0); - } - /* Pad out to a multiple of four bytes */ - if (SavedArgsLength & 3) { - if (write(OutFile, &Zeros, 4-(SavedArgsLength&3)) < 0) { - fprintf(stderr,"error: unable to write to output file."); - exit(0); - } - } - } - } - 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; - 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/EdgeProfiling.c b/runtime/libprofile/EdgeProfiling.c deleted file mode 100644 index f19e188f0d..0000000000 --- a/runtime/libprofile/EdgeProfiling.c +++ /dev/null @@ -1,45 +0,0 @@ -/*===-- EdgeProfiling.c - Support library for edge 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 edge profiling -|* instrumentation pass. This should be used with the -insert-edge-profiling -|* LLVM pass. -|* -\*===----------------------------------------------------------------------===*/ - -#include "Profiling.h" -#include <stdlib.h> - -static unsigned *ArrayStart; -static unsigned NumElements; - -/* EdgeProfAtExitHandler - When the program exits, just write out the profiling - * data. - */ -static void EdgeProfAtExitHandler(void) { - /* Note that if this were doing something more intelligent with the - * instrumentation, we could do some computation here to expand what we - * collected into simple edge profiles. Since we directly count each edge, we - * just write out all of the counters directly. - */ - write_profiling_data(EdgeInfo, ArrayStart, NumElements); -} - - -/* llvm_start_edge_profiling - This is the main entry point of the edge - * profiling library. It is responsible for setting up the atexit handler. - */ -int llvm_start_edge_profiling(int argc, const char **argv, - unsigned *arrayStart, unsigned numElements) { - int Ret = save_arguments(argc, argv); - ArrayStart = arrayStart; - NumElements = numElements; - atexit(EdgeProfAtExitHandler); - return Ret; -} diff --git a/runtime/libprofile/Makefile b/runtime/libprofile/Makefile deleted file mode 100644 index 2f061adcd5..0000000000 --- a/runtime/libprofile/Makefile +++ /dev/null @@ -1,52 +0,0 @@ -##===- runtime/libprofile/Makefile -------------------------*- Makefile -*-===## -# -# The LLVM Compiler Infrastructure -# -# This file is distributed under the University of Illinois Open Source -# License. See LICENSE.TXT for details. -# -##===----------------------------------------------------------------------===## - -LEVEL = ../.. -include $(LEVEL)/Makefile.config - -LIBRARYNAME = profile_rt -LINK_LIBS_IN_SHARED = 1 -SHARED_LIBRARY = 1 - -# Build and install this archive. -BUILD_ARCHIVE = 1 -override NO_INSTALL_ARCHIVES = - -include $(LEVEL)/Makefile.common - -ifeq ($(HOST_OS),Darwin) - # Special hack to allow libprofile_rt to have an offset version number. - PROFILE_RT_LIBRARY_VERSION := $(LLVM_SUBMIT_VERSION) - - # Set dylib internal version number to llvmCore submission number. - ifdef LLVM_SUBMIT_VERSION - LLVMLibsOptions := $(LLVMLibsOptions) -Wl,-current_version \ - -Wl,$(PROFILE_RT_LIBRARY_VERSION).$(LLVM_SUBMIT_SUBVERSION) \ - -Wl,-compatibility_version -Wl,1 - endif - # Extra options to override libtool defaults. - LLVMLibsOptions := $(LLVMLibsOptions) \ - -Wl,-dead_strip - - # Mac OS X 10.4 and earlier tools do not allow a second -install_name on - # command line. - DARWIN_VERS := $(shell echo $(TARGET_TRIPLE) | sed 's/.*darwin\([0-9]*\).*/\1/') - ifneq ($(DARWIN_VERS),8) - LLVMLibsOptions := $(LLVMLibsOptions) \ - -Wl,-install_name \ - -Wl,"@rpath/lib$(LIBRARYNAME)$(SHLIBEXT)" - endif - - # If we're doing an Apple-style build, add the LTO object path. - ifeq ($(RC_XBS),YES) - TempFile := $(shell mkdir -p ${OBJROOT}/dSYMs ; mktemp ${OBJROOT}/dSYMs/profile_rt-lto.XXXXXX) - LLVMLibsOptions := $(LLVMLibsOptions) \ - -Wl,-object_path_lto -Wl,$(TempFile) - endif -endif diff --git a/runtime/libprofile/OptimalEdgeProfiling.c b/runtime/libprofile/OptimalEdgeProfiling.c deleted file mode 100644 index 3a7631b6e8..0000000000 --- a/runtime/libprofile/OptimalEdgeProfiling.c +++ /dev/null @@ -1,45 +0,0 @@ -/*===-- OptimalEdgeProfiling.c - Support library for opt. edge 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 edge profiling -|* instrumentation pass. This should be used with the -|* -insert-opt-edge-profiling LLVM pass. -|* -\*===----------------------------------------------------------------------===*/ - -#include "Profiling.h" -#include <stdlib.h> - -static unsigned *ArrayStart; -static unsigned NumElements; - -/* OptEdgeProfAtExitHandler - When the program exits, just write out the - * profiling data. - */ -static void OptEdgeProfAtExitHandler(void) { - /* Note that, although the array has a counter for each edge, not all - * counters are updated, the ones that are not used are initialised with -1. - * When loading this information the counters with value -1 have to be - * recalculated, it is guaranteed that this is possible. - */ - write_profiling_data(OptEdgeInfo, ArrayStart, NumElements); -} - - -/* llvm_start_opt_edge_profiling - This is the main entry point of the edge - * profiling library. It is responsible for setting up the atexit handler. - */ -int llvm_start_opt_edge_profiling(int argc, const char **argv, - unsigned *arrayStart, unsigned numElements) { - int Ret = save_arguments(argc, argv); - ArrayStart = arrayStart; - NumElements = numElements; - atexit(OptEdgeProfAtExitHandler); - return Ret; -} diff --git a/runtime/libprofile/PathProfiling.c b/runtime/libprofile/PathProfiling.c deleted file mode 100644 index 71ee944fc5..0000000000 --- a/runtime/libprofile/PathProfiling.c +++ /dev/null @@ -1,270 +0,0 @@ -/*===-- 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 "llvm/Support/DataTypes.h" -#include <sys/types.h> -#if !defined(_MSC_VER) && !defined(__MINGW32__) -#include <unistd.h> -#else -#include <io.h> -#endif -#include <string.h> -#include <stdlib.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); - } -} - -static uint32_t hash (uint32_t key) { - /* this may benefit 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 */ -static 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(void) { - 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 deleted file mode 100644 index acc6399a18..0000000000 --- a/runtime/libprofile/Profiling.h +++ /dev/null @@ -1,36 +0,0 @@ -/*===-- 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 defines functions shared by the various different profiling -|* implementations. -|* -\*===----------------------------------------------------------------------===*/ - -#ifndef PROFILING_H -#define PROFILING_H - -#include "llvm/Analysis/ProfileDataTypes.h" /* for enum ProfilingType */ - -/* save_arguments - Save argc and argv as passed into the program for the file - * we output. - */ -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. - */ -void write_profiling_data(enum ProfilingType PT, unsigned *Start, - unsigned NumElements); - -#endif diff --git a/test/Analysis/Profiling/edge-profiling.ll b/test/Analysis/Profiling/edge-profiling.ll deleted file mode 100644 index cbaf47617f..0000000000 --- a/test/Analysis/Profiling/edge-profiling.ll +++ /dev/null @@ -1,139 +0,0 @@ -; Test the edge profiling instrumentation. -; RUN: opt < %s -insert-edge-profiling -S | FileCheck %s - -; ModuleID = '<stdin>' - -@.str = private constant [12 x i8] c"hello world\00", align 1 ; <[12 x i8]*> [#uses=1] -@.str1 = private constant [6 x i8] c"franz\00", align 1 ; <[6 x i8]*> [#uses=1] -@.str2 = private constant [9 x i8] c"argc > 2\00", align 1 ; <[9 x i8]*> [#uses=1] -@.str3 = private constant [9 x i8] c"argc = 1\00", align 1 ; <[9 x i8]*> [#uses=1] -@.str4 = private constant [6 x i8] c"fritz\00", align 1 ; <[6 x i8]*> [#uses=1] -@.str5 = private constant [10 x i8] c"argc <= 1\00", align 1 ; <[10 x i8]*> [#uses=1] -; CHECK:@EdgeProfCounters -; CHECK:[19 x i32] -; CHECK:zeroinitializer - -define void @oneblock() nounwind { -entry: -; CHECK:entry: -; CHECK:%OldFuncCounter -; CHECK:load -; CHECK:getelementptr -; CHECK:@EdgeProfCounters -; CHECK:i32 0 -; CHECK:i32 0 -; CHECK:%NewFuncCounter -; CHECK:add -; CHECK:%OldFuncCounter -; CHECK:store -; CHECK:%NewFuncCounter -; CHECK:getelementptr -; CHECK:@EdgeProfCounters - %0 = call i32 @puts(i8* getelementptr inbounds ([12 x i8]* @.str, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - ret void -} - -declare i32 @puts(i8*) - -define i32 @main(i32 %argc, i8** %argv) nounwind { -entry: -; CHECK:entry: - %argc_addr = alloca i32 ; <i32*> [#uses=4] - %argv_addr = alloca i8** ; <i8***> [#uses=1] - %retval = alloca i32 ; <i32*> [#uses=2] - %j = alloca i32 ; <i32*> [#uses=4] - %i = alloca i32 ; <i32*> [#uses=4] - %0 = alloca i32 ; <i32*> [#uses=2] -; CHECK:call -; CHECK:@llvm_start_edge_profiling -; CHECK:@EdgeProfCounters - %"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0] - store i32 %argc, i32* %argc_addr - store i8** %argv, i8*** %argv_addr - store i32 0, i32* %i, align 4 - br label %bb10 - -bb: ; preds = %bb10 -; CHECK:bb: - %1 = load i32* %argc_addr, align 4 ; <i32> [#uses=1] - %2 = icmp sgt i32 %1, 1 ; <i1> [#uses=1] - br i1 %2, label %bb1, label %bb8 - -bb1: ; preds = %bb -; CHECK:bb1: - store i32 0, i32* %j, align 4 - br label %bb6 - -bb2: ; preds = %bb6 -; CHECK:bb2: - %3 = call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @.str1, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - %4 = load i32* %argc_addr, align 4 ; <i32> [#uses=1] - %5 = icmp sgt i32 %4, 2 ; <i1> [#uses=1] - br i1 %5, label %bb3, label %bb4 - -bb3: ; preds = %bb2 -; CHECK:bb3: - %6 = call i32 @puts(i8* getelementptr inbounds ([9 x i8]* @.str2, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - br label %bb5 - -bb4: ; preds = %bb2 -; CHECK:bb4: - %7 = call i32 @puts(i8* getelementptr inbounds ([9 x i8]* @.str3, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - br label %bb11 - -bb5: ; preds = %bb3 -; CHECK:bb5: - %8 = call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @.str4, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - %9 = load i32* %j, align 4 ; <i32> [#uses=1] - %10 = add nsw i32 %9, 1 ; <i32> [#uses=1] - store i32 %10, i32* %j, align 4 - br label %bb6 - -bb6: ; preds = %bb5, %bb1 -; CHECK:bb6: - %11 = load i32* %j, align 4 ; <i32> [#uses=1] - %12 = load i32* %argc_addr, align 4 ; <i32> [#uses=1] - %13 = icmp slt i32 %11, %12 ; <i1> [#uses=1] - br i1 %13, label %bb2, label %bb7 - -bb7: ; preds = %bb6 -; CHECK:bb7: - br label %bb9 - -bb8: ; preds = %bb -; CHECK:bb8: - %14 = call i32 @puts(i8* getelementptr inbounds ([10 x i8]* @.str5, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - br label %bb9 - -bb9: ; preds = %bb8, %bb7 -; CHECK:bb9: - %15 = load i32* %i, align 4 ; <i32> [#uses=1] - %16 = add nsw i32 %15, 1 ; <i32> [#uses=1] - store i32 %16, i32* %i, align 4 - br label %bb10 - -bb10: ; preds = %bb9, %entry -; CHECK:bb10: - %17 = load i32* %i, align 4 ; <i32> [#uses=1] - %18 = icmp ne i32 %17, 3 ; <i1> [#uses=1] - br i1 %18, label %bb, label %bb11 -; CHECK:br -; CHECK:label %bb10.bb11_crit_edge - -; CHECK:bb10.bb11_crit_edge: -; CHECK:br -; CHECK:label %bb11 - -bb11: ; preds = %bb10, %bb4 -; CHECK:bb11: - call void @oneblock() nounwind - store i32 0, i32* %0, align 4 - %19 = load i32* %0, align 4 ; <i32> [#uses=1] - store i32 %19, i32* %retval, align 4 - br label %return - -return: ; preds = %bb11 -; CHECK:return: - %retval12 = load i32* %retval ; <i32> [#uses=1] - ret i32 %retval12 -} diff --git a/test/Analysis/Profiling/lit.local.cfg b/test/Analysis/Profiling/lit.local.cfg deleted file mode 100644 index 5481b13ce0..0000000000 --- a/test/Analysis/Profiling/lit.local.cfg +++ /dev/null @@ -1,2 +0,0 @@ -if 'hexagon' in config.root.target_triple: - config.unsupported = True diff --git a/test/Analysis/Profiling/load-branch-weights-ifs.ll b/test/Analysis/Profiling/load-branch-weights-ifs.ll deleted file mode 100644 index 7ed090b7c3..0000000000 --- a/test/Analysis/Profiling/load-branch-weights-ifs.ll +++ /dev/null @@ -1,122 +0,0 @@ -; RUN: opt -insert-edge-profiling -o %t1 < %s -; RUN: rm -f %t1.prof_data -; RUN: lli %defaultjit -load %llvmshlibdir/libprofile_rt%shlibext %t1 \ -; RUN: -llvmprof-output %t1.prof_data -; RUN: opt -profile-file %t1.prof_data -profile-metadata-loader -S -o - < %s \ -; RUN: | FileCheck %s -; RUN: rm -f %t1.prof_data - -; FIXME: profile_rt.dll could be built on win32. -; REQUIRES: loadable_module - -;; func_mod - Branch taken 6 times in 7. -define i32 @func_mod(i32 %N) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %N.addr = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - %0 = load i32* %N.addr, align 4 - %rem = srem i32 %0, 7 - %tobool = icmp ne i32 %rem, 0 - br i1 %tobool, label %if.then, label %if.else -; CHECK: br i1 %tobool, label %if.then, label %if.else, !prof !0 - -if.then: - store i32 1, i32* %retval - br label %return - -if.else: - store i32 0, i32* %retval - br label %return - -return: - %1 = load i32* %retval - ret i32 %1 -} - -;; func_const_true - conditional branch which 100% taken probability. -define i32 @func_const_true(i32 %N) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %N.addr = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - %0 = load i32* %N.addr, align 4 - %cmp = icmp eq i32 %0, 1 - br i1 %cmp, label %if.then, label %if.end -; CHECK: br i1 %cmp, label %if.then, label %if.end, !prof !1 - -if.then: - store i32 1, i32* %retval - br label %return - -if.end: - store i32 0, i32* %retval - br label %return - -return: - %1 = load i32* %retval - ret i32 %1 -} - -;; func_const_true - conditional branch which 100% not-taken probability. -define i32 @func_const_false(i32 %N) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %N.addr = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - %0 = load i32* %N.addr, align 4 - %cmp = icmp eq i32 %0, 1 - br i1 %cmp, label %if.then, label %if.end -; CHECK: br i1 %cmp, label %if.then, label %if.end, !prof !2 - -if.then: - store i32 1, i32* %retval - br label %return - -if.end: - store i32 0, i32* %retval - br label %return - -return: - %1 = load i32* %retval - ret i32 %1 -} - -define i32 @main(i32 %argc, i8** %argv) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %argc.addr = alloca i32, align 4 - %argv.addr = alloca i8**, align 8 - %loop = alloca i32, align 4 - store i32 0, i32* %retval - store i32 0, i32* %loop, align 4 - br label %for.cond - -for.cond: - %0 = load i32* %loop, align 4 - %cmp = icmp slt i32 %0, 7000 - br i1 %cmp, label %for.body, label %for.end -; CHECK: br i1 %cmp, label %for.body, label %for.end, !prof !3 - -for.body: - %1 = load i32* %loop, align 4 - %call = call i32 @func_mod(i32 %1) - br label %for.inc - -for.inc: - %2 = load i32* %loop, align 4 - %inc = add nsw i32 %2, 1 - store i32 %inc, i32* %loop, align 4 - br label %for.cond - -for.end: - %call1 = call i32 @func_const_true(i32 1) - %call2 = call i32 @func_const_false(i32 0) - ret i32 0 -} - -; CHECK: !0 = metadata !{metadata !"branch_weights", i32 6000, i32 1000} -; CHECK: !1 = metadata !{metadata !"branch_weights", i32 1, i32 0} -; CHECK: !2 = metadata !{metadata !"branch_weights", i32 0, i32 1} -; CHECK: !3 = metadata !{metadata !"branch_weights", i32 7000, i32 1} -; CHECK-NOT: !4 diff --git a/test/Analysis/Profiling/load-branch-weights-loops.ll b/test/Analysis/Profiling/load-branch-weights-loops.ll deleted file mode 100644 index 9d1925a2d7..0000000000 --- a/test/Analysis/Profiling/load-branch-weights-loops.ll +++ /dev/null @@ -1,188 +0,0 @@ -; RUN: opt -insert-edge-profiling -o %t1 < %s -; RUN: rm -f %t1.prof_data -; RUN: lli %defaultjit -load %llvmshlibdir/libprofile_rt%shlibext %t1 \ -; RUN: -llvmprof-output %t1.prof_data -; RUN: opt -profile-file %t1.prof_data -profile-metadata-loader -S -o - < %s \ -; RUN: | FileCheck %s -; RUN: rm -f %t1.prof_data - -; FIXME: profile_rt.dll could be built on win32. -; REQUIRES: loadable_module - -;; func_for - Test branch probabilities for a vanilla for loop. -define i32 @func_for(i32 %N) nounwind uwtable { -entry: - %N.addr = alloca i32, align 4 - %ret = alloca i32, align 4 - %loop = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - store i32 0, i32* %ret, align 4 - store i32 0, i32* %loop, align 4 - br label %for.cond - -for.cond: - %0 = load i32* %loop, align 4 - %1 = load i32* %N.addr, align 4 - %cmp = icmp slt i32 %0, %1 - br i1 %cmp, label %for.body, label %for.end -; CHECK: br i1 %cmp, label %for.body, label %for.end, !prof !0 - -for.body: - %2 = load i32* %N.addr, align 4 - %3 = load i32* %ret, align 4 - %add = add nsw i32 %3, %2 - store i32 %add, i32* %ret, align 4 - br label %for.inc - -for.inc: - %4 = load i32* %loop, align 4 - %inc = add nsw i32 %4, 1 - store i32 %inc, i32* %loop, align 4 - br label %for.cond - -for.end: - %5 = load i32* %ret, align 4 - ret i32 %5 -} - -;; func_for_odd - Test branch probabilities for a for loop with a continue and -;; a break. -define i32 @func_for_odd(i32 %N) nounwind uwtable { -entry: - %N.addr = alloca i32, align 4 - %ret = alloca i32, align 4 - %loop = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - store i32 0, i32* %ret, align 4 - store i32 0, i32* %loop, align 4 - br label %for.cond - -for.cond: - %0 = load i32* %loop, align 4 - %1 = load i32* %N.addr, align 4 - %cmp = icmp slt i32 %0, %1 - br i1 %cmp, label %for.body, label %for.end -; CHECK: br i1 %cmp, label %for.body, label %for.end, !prof !1 - -for.body: - %2 = load i32* %loop, align 4 - %rem = srem i32 %2, 10 - %tobool = icmp ne i32 %rem, 0 - br i1 %tobool, label %if.then, label %if.end -; CHECK: br i1 %tobool, label %if.then, label %if.end, !prof !2 - -if.then: - br label %for.inc - -if.end: - %3 = load i32* %loop, align 4 - %cmp1 = icmp eq i32 %3, 500 - br i1 %cmp1, label %if.then2, label %if.end3 -; CHECK: br i1 %cmp1, label %if.then2, label %if.end3, !prof !3 - -if.then2: - br label %for.end - -if.end3: - %4 = load i32* %N.addr, align 4 - %5 = load i32* %ret, align 4 - %add = add nsw i32 %5, %4 - store i32 %add, i32* %ret, align 4 - br label %for.inc - -for.inc: - %6 = load i32* %loop, align 4 - %inc = add nsw i32 %6, 1 - store i32 %inc, i32* %loop, align 4 - br label %for.cond - -for.end: - %7 = load i32* %ret, align 4 - ret i32 %7 -} - -;; func_while - Test branch probability in a vanilla while loop. -define i32 @func_while(i32 %N) nounwind uwtable { -entry: - %N.addr = alloca i32, align 4 - %ret = alloca i32, align 4 - %loop = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - store i32 0, i32* %ret, align 4 - store i32 0, i32* %loop, align 4 - br label %while.cond - -while.cond: - %0 = load i32* %loop, align 4 - %1 = load i32* %N.addr, align 4 - %cmp = icmp slt i32 %0, %1 - br i1 %cmp, label %while.body, label %while.end -; CHECK: br i1 %cmp, label %while.body, label %while.end, !prof !0 - -while.body: - %2 = load i32* %N.addr, align 4 - %3 = load i32* %ret, align 4 - %add = add nsw i32 %3, %2 - store i32 %add, i32* %ret, align 4 - %4 = load i32* %loop, align 4 - %inc = add nsw i32 %4, 1 - store i32 %inc, i32* %loop, align 4 - br label %while.cond - -while.end: - %5 = load i32* %ret, align 4 - ret i32 %5 -} - -;; func_while - Test branch probability in a vanilla do-while loop. -define i32 @func_do_while(i32 %N) nounwind uwtable { -entry: - %N.addr = alloca i32, align 4 - %ret = alloca i32, align 4 - %loop = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - store i32 0, i32* %ret, align 4 - store i32 0, i32* %loop, align 4 - br label %do.body - -do.body: - %0 = load i32* %N.addr, align 4 - %1 = load i32* %ret, align 4 - %add = add nsw i32 %1, %0 - store i32 %add, i32* %ret, align 4 - %2 = load i32* %loop, align 4 - %inc = add nsw i32 %2, 1 - store i32 %inc, i32* %loop, align 4 - br label %do.cond - -do.cond: - %3 = load i32* %loop, align 4 - %4 = load i32* %N.addr, align 4 - %cmp = icmp slt i32 %3, %4 - br i1 %cmp, label %do.body, label %do.end -; CHECK: br i1 %cmp, label %do.body, label %do.end, !prof !4 - -do.end: - %5 = load i32* %ret, align 4 - ret i32 %5 -} - -define i32 @main(i32 %argc, i8** %argv) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %argc.addr = alloca i32, align 4 - %argv.addr = alloca i8**, align 8 - store i32 0, i32* %retval - %call = call i32 @func_for(i32 1000) - %call1 = call i32 @func_for_odd(i32 1000) - %call2 = call i32 @func_while(i32 1000) - %call3 = call i32 @func_do_while(i32 1000) - ret i32 0 -} - -!0 = metadata !{metadata !"branch_weights", i32 1000, i32 1} -!1 = metadata !{metadata !"branch_weights", i32 501, i32 0} -!2 = metadata !{metadata !"branch_weights", i32 450, i32 51} -!3 = metadata !{metadata !"branch_weights", i32 1, i32 50} -!4 = metadata !{metadata !"branch_weights", i32 999, i32 1} -; CHECK-NOT: !5 diff --git a/test/Analysis/Profiling/load-branch-weights-switches.ll b/test/Analysis/Profiling/load-branch-weights-switches.ll deleted file mode 100644 index 5587c7172b..0000000000 --- a/test/Analysis/Profiling/load-branch-weights-switches.ll +++ /dev/null @@ -1,165 +0,0 @@ -; RUN: opt -insert-edge-profiling -o %t1 < %s -; RUN: rm -f %t1.prof_data -; RUN: lli %defaultjit -load %llvmshlibdir/libprofile_rt%shlibext %t1 \ -; RUN: -llvmprof-output %t1.prof_data -; RUN: opt -profile-file %t1.prof_data -profile-metadata-loader -S -o - < %s \ -; RUN: | FileCheck %s -; RUN: rm -f %t1.prof_data - -; FIXME: profile_rt.dll could be built on win32. -; REQUIRES: loadable_module - -;; func_switch - Test branch probabilities for a switch instruction with an -;; even chance of taking each case (or no case). -define i32 @func_switch(i32 %N) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %N.addr = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - %0 = load i32* %N.addr, align 4 - %rem = srem i32 %0, 4 - switch i32 %rem, label %sw.epilog [ - i32 0, label %sw.bb - i32 1, label %sw.bb1 - i32 2, label %sw.bb2 - ] -; CHECK: ], !prof !0 - -sw.bb: - store i32 5, i32* %retval - br label %return - -sw.bb1: - store i32 6, i32* %retval - br label %return - -sw.bb2: - store i32 7, i32* %retval - br label %return - -sw.epilog: - store i32 8, i32* %retval - br label %return - -return: - %1 = load i32* %retval - ret i32 %1 -} - -;; func_switch_switch - Test branch probabilities in a switch-instruction that -;; leads to further switch instructions. The first-tier switch occludes some -;; possibilities in the second-tier switches, leading to some branches having a -;; 0 probability. -define i32 @func_switch_switch(i32 %N) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %N.addr = alloca i32, align 4 - store i32 %N, i32* %N.addr, align 4 - %0 = load i32* %N.addr, align 4 - %rem = srem i32 %0, 2 - switch i32 %rem, label %sw.default11 [ - i32 0, label %sw.bb - i32 1, label %sw.bb5 - ] -; CHECK: ], !prof !1 - -sw.bb: - %1 = load i32* %N.addr, align 4 - %rem1 = srem i32 %1, 4 - switch i32 %rem1, label %sw.default [ - i32 0, label %sw.bb2 - i32 1, label %sw.bb3 - i32 2, label %sw.bb4 - ] -; CHECK: ], !prof !2 - -sw.bb2: - store i32 5, i32* %retval - br label %return - -sw.bb3: - store i32 6, i32* %retval - br label %return - -sw.bb4: - store i32 7, i32* %retval - br label %return - -sw.default: - store i32 8, i32* %retval - br label %return - -sw.bb5: - %2 = load i32* %N.addr, align 4 - %rem6 = srem i32 %2, 4 - switch i32 %rem6, label %sw.default10 [ - i32 0, label %sw.bb7 - i32 1, label %sw.bb8 - i32 2, label %sw.bb9 - ] -; CHECK: ], !prof !3 - -sw.bb7: - store i32 9, i32* %retval - br label %return - -sw.bb8: - store i32 10, i32* %retval - br label %return - -sw.bb9: - store i32 11, i32* %retval - br label %return - -sw.default10: - store i32 12, i32* %retval - br label %return - -sw.default11: - store i32 13, i32* %retval - br label %return - -return: - %3 = load i32* %retval - ret i32 %3 -} - -define i32 @main(i32 %argc, i8** %argv) nounwind uwtable { -entry: - %retval = alloca i32, align 4 - %argc.addr = alloca i32, align 4 - %argv.addr = alloca i8**, align 8 - %loop = alloca i32, align 4 - store i32 0, i32* %retval - store i32 0, i32* %loop, align 4 - br label %for.cond - -for.cond: - %0 = load i32* %loop, align 4 - %cmp = icmp slt i32 %0, 4000 - br i1 %cmp, label %for.body, label %for.end -; CHECK: br i1 %cmp, label %for.body, label %for.end, !prof !4 - -for.body: - %1 = load i32* %loop, align 4 - %call = call i32 @func_switch(i32 %1) - %2 = load i32* %loop, align 4 - %call1 = call i32 @func_switch_switch(i32 %2) - br label %for.inc - -for.inc: - %3 = load i32* %loop, align 4 - %inc = add nsw i32 %3, 1 - store i32 %inc, i32* %loop, align 4 - br label %for.cond - -for.end: - ret i32 0 -} - -; CHECK: !0 = metadata !{metadata !"branch_weights", i32 1000, i32 1000, i32 1000, i32 1000} -; CHECK: !1 = metadata !{metadata !"branch_weights", i32 0, i32 2000, i32 2000} -; CHECK: !2 = metadata !{metadata !"branch_weights", i32 0, i32 1000, i32 0, i32 1000} -; CHECK: !3 = metadata !{metadata !"branch_weights", i32 1000, i32 0, i32 1000, i32 0} -; CHECK: !4 = metadata !{metadata !"branch_weights", i32 4000, i32 1} -; CHECK-NOT: !5 diff --git a/test/Analysis/Profiling/profiling-tool-chain.ll b/test/Analysis/Profiling/profiling-tool-chain.ll deleted file mode 100644 index 9135a85dc3..0000000000 --- a/test/Analysis/Profiling/profiling-tool-chain.ll +++ /dev/null @@ -1,212 +0,0 @@ -; RUN: llvm-as %s -o %t1 - -; FIXME: The RUX parts of the test are disabled for now, they aren't working on -; llvm-gcc-x86_64-darwin10-selfhost. - -; Test the edge optimal profiling instrumentation. -; RUN: opt %t1 -insert-optimal-edge-profiling -o %t2 -; RUX: llvm-dis < %t2 | FileCheck --check-prefix=INST %s - -; Test the creation, reading and displaying of profile -; RUX: rm -f llvmprof.out -; RUX: lli -load %llvmshlibdir/profile_rt%shlibext %t2 -; RUX: lli -load %llvmshlibdir/profile_rt%shlibext %t2 1 2 -; RUX: llvm-prof -print-all-code %t1 | FileCheck --check-prefix=PROF %s - -; Test the loaded profile also with verifier. -; RUX opt %t1 -profile-loader -profile-verifier -o %t3 - -; Test profile estimator. -; RUN: opt %t1 -profile-estimator -profile-verifier -o %t3 - -; PROF: 1. 2/4 oneblock -; PROF: 2. 2/4 main -; PROF: 1. 15.7895% 12/76 main() - bb6 -; PROF: 2. 11.8421% 9/76 main() - bb2 -; PROF: 3. 11.8421% 9/76 main() - bb3 -; PROF: 4. 11.8421% 9/76 main() - bb5 -; PROF: 5. 10.5263% 8/76 main() - bb10 -; PROF: 6. 7.89474% 6/76 main() - bb -; PROF: 7. 7.89474% 6/76 main() - bb9 -; PROF: 8. 3.94737% 3/76 main() - bb1 -; PROF: 9. 3.94737% 3/76 main() - bb7 -; PROF: 10. 3.94737% 3/76 main() - bb8 -; PROF: 11. 2.63158% 2/76 oneblock() - entry -; PROF: 12. 2.63158% 2/76 main() - entry -; PROF: 13. 2.63158% 2/76 main() - bb11 -; PROF: 14. 2.63158% 2/76 main() - return - -; ModuleID = '<stdin>' - -@.str = private constant [12 x i8] c"hello world\00", align 1 ; <[12 x i8]*> [#uses=1] -@.str1 = private constant [6 x i8] c"franz\00", align 1 ; <[6 x i8]*> [#uses=1] -@.str2 = private constant [9 x i8] c"argc > 2\00", align 1 ; <[9 x i8]*> [#uses=1] -@.str3 = private constant [9 x i8] c"argc = 1\00", align 1 ; <[9 x i8]*> [#uses=1] -@.str4 = private constant [6 x i8] c"fritz\00", align 1 ; <[6 x i8]*> [#uses=1] -@.str5 = private constant [10 x i8] c"argc <= 1\00", align 1 ; <[10 x i8]*> [#uses=1] -; INST:@OptEdgeProfCounters -; INST:[21 x i32] -; INST:[i32 0, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 0, -; INST:i32 0, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 0, -; INST:i32 0, -; INST:i32 -1, -; INST:i32 -1, -; INST:i32 0, -; INST:i32 -1, -; INST:i32 -1] - -; PROF:;;; %oneblock called 2 times. -; PROF:;;; -define void @oneblock() nounwind { -entry: -; PROF:entry: -; PROF: ;;; Basic block executed 2 times. - %0 = call i32 @puts(i8* getelementptr inbounds ([12 x i8]* @.str, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - ret void -} - -declare i32 @puts(i8*) - -; PROF:;;; %main called 2 times. -; PROF:;;; -define i32 @main(i32 %argc, i8** %argv) nounwind { -entry: -; PROF:entry: -; PROF: ;;; Basic block executed 2 times. - %argc_addr = alloca i32 ; <i32*> [#uses=4] - %argv_addr = alloca i8** ; <i8***> [#uses=1] - %retval = alloca i32 ; <i32*> [#uses=2] - %j = alloca i32 ; <i32*> [#uses=4] - %i = alloca i32 ; <i32*> [#uses=4] - %0 = alloca i32 ; <i32*> [#uses=2] -; INST:call -; INST:@llvm_start_opt_edge_profiling -; INST:@OptEdgeProfCounters - %"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0] - store i32 %argc, i32* %argc_addr - store i8** %argv, i8*** %argv_addr - store i32 0, i32* %i, align 4 - br label %bb10 -; PROF: ;;; Out-edge counts: [2.000000e+00 -> bb10] - -bb: ; preds = %bb10 -; PROF:bb: -; PROF: ;;; Basic block executed 6 times. - %1 = load i32* %argc_addr, align 4 ; <i32> [#uses=1] - %2 = icmp sgt i32 %1, 1 ; <i1> [#uses=1] - br i1 %2, label %bb1, label %bb8 -; PROF: ;;; Out-edge counts: [3.000000e+00 -> bb1] [3.000000e+00 -> bb8] - -bb1: ; preds = %bb -; PROF:bb1: -; PROF: ;;; Basic block executed 3 times. - store i32 0, i32* %j, align 4 - br label %bb6 -; PROF: ;;; Out-edge counts: [3.000000e+00 -> bb6] - -bb2: ; preds = %bb6 -; PROF:bb2: -; PROF: ;;; Basic block executed 9 times. - %3 = call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @.str1, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - %4 = load i32* %argc_addr, align 4 ; <i32> [#uses=1] - %5 = icmp sgt i32 %4, 2 ; <i1> [#uses=1] - br i1 %5, label %bb3, label %bb4 -; PROF: ;;; Out-edge counts: [9.000000e+00 -> bb3] - -bb3: ; preds = %bb2 -; PROF:bb3: -; PROF: ;;; Basic block executed 9 times. - %6 = call i32 @puts(i8* getelementptr inbounds ([9 x i8]* @.str2, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - br label %bb5 -; PROF: ;;; Out-edge counts: [9.000000e+00 -> bb5] - -bb4: ; preds = %bb2 -; PROF:bb4: -; PROF: ;;; Never executed! - %7 = call i32 @puts(i8* getelementptr inbounds ([9 x i8]* @.str3, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - br label %bb11 - -bb5: ; preds = %bb3 -; PROF:bb5: -; PROF: ;;; Basic block executed 9 times. - %8 = call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @.str4, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - %9 = load i32* %j, align 4 ; <i32> [#uses=1] - %10 = add nsw i32 %9, 1 ; <i32> [#uses=1] - store i32 %10, i32* %j, align 4 - br label %bb6 -; PROF: ;;; Out-edge counts: [9.000000e+00 -> bb6] - -bb6: ; preds = %bb5, %bb1 -; PROF:bb6: -; PROF: ;;; Basic block executed 12 times. - %11 = load i32* %j, align 4 ; <i32> [#uses=1] - %12 = load i32* %argc_addr, align 4 ; <i32> [#uses=1] - %13 = icmp slt i32 %11, %12 ; <i1> [#uses=1] - br i1 %13, label %bb2, label %bb7 -; PROF: ;;; Out-edge counts: [9.000000e+00 -> bb2] [3.000000e+00 -> bb7] - -bb7: ; preds = %bb6 -; PROF:bb7: -; PROF: ;;; Basic block executed 3 times. - br label %bb9 -; PROF: ;;; Out-edge counts: [3.000000e+00 -> bb9] - -bb8: ; preds = %bb -; PROF:bb8: -; PROF: ;;; Basic block executed 3 times. - %14 = call i32 @puts(i8* getelementptr inbounds ([10 x i8]* @.str5, i64 0, i64 0)) nounwind ; <i32> [#uses=0] - br label %bb9 -; PROF: ;;; Out-edge counts: [3.000000e+00 -> bb9] - -bb9: ; preds = %bb8, %bb7 -; PROF:bb9: -; PROF: ;;; Basic block executed 6 times. - %15 = load i32* %i, align 4 ; <i32> [#uses=1] - %16 = add nsw i32 %15, 1 ; <i32> [#uses=1] - store i32 %16, i32* %i, align 4 - br label %bb10 -; PROF: ;;; Out-edge counts: [6.000000e+00 -> bb10] - -bb10: ; preds = %bb9, %entry -; PROF:bb10: -; PROF: ;;; Basic block executed 8 times. - %17 = load i32* %i, align 4 ; <i32> [#uses=1] - %18 = icmp ne i32 %17, 3 ; <i1> [#uses=1] - br i1 %18, label %bb, label %bb11 -; INST:br -; INST:label %bb10.bb11_crit_edge -; PROF: ;;; Out-edge counts: [6.000000e+00 -> bb] [2.000000e+00 -> bb11] - -; INST:bb10.bb11_crit_edge: -; INST:br -; INST:label %bb11 - -bb11: ; preds = %bb10, %bb4 -; PROF:bb11: -; PROF: ;;; Basic block executed 2 times. - call void @oneblock() nounwind - store i32 0, i32* %0, align 4 - %19 = load i32* %0, align 4 ; <i32> [#uses=1] - store i32 %19, i32* %retval, align 4 - br label %return -; PROF: ;;; Out-edge counts: [2.000000e+00 -> return] - -return: ; preds = %bb11 -; PROF:return: -; PROF: ;;; Basic block executed 2 times. - %retval12 = load i32* %retval ; <i32> [#uses=1] - ret i32 %retval12 -} diff --git a/test/lit.cfg b/test/lit.cfg index 171186ea50..9e590a80a9 100644 --- a/test/lit.cfg +++ b/test/lit.cfg @@ -226,7 +226,6 @@ for pattern in [r"\bbugpoint\b(?!-)", r"\bllvm-mc\b", r"\bllvm-nm\b", r"\bllvm-objdump\b", - r"\bllvm-prof\b", r"\bllvm-ranlib\b", r"\bllvm-readobj\b", r"\bllvm-rtdyld\b", diff --git a/tools/CMakeLists.txt b/tools/CMakeLists.txt index d8001e75a7..69c4050c91 100644 --- a/tools/CMakeLists.txt +++ b/tools/CMakeLists.txt @@ -15,7 +15,6 @@ add_llvm_tool_subdirectory(llvm-nm) add_llvm_tool_subdirectory(llvm-size) add_llvm_tool_subdirectory(llvm-cov) -add_llvm_tool_subdirectory(llvm-prof) add_llvm_tool_subdirectory(llvm-link) add_llvm_tool_subdirectory(lli) diff --git a/tools/LLVMBuild.txt b/tools/LLVMBuild.txt index fa10b997a2..93b8d98dcb 100644 --- a/tools/LLVMBuild.txt +++ b/tools/LLVMBuild.txt @@ -16,7 +16,7 @@ ;===------------------------------------------------------------------------===; [common] -subdirectories = bugpoint llc lli llvm-ar llvm-as llvm-bcanalyzer llvm-cov llvm-diff llvm-dis llvm-dwarfdump llvm-extract llvm-jitlistener llvm-link llvm-lto llvm-mc llvm-nm llvm-objdump llvm-prof llvm-rtdyld llvm-size macho-dump opt llvm-mcmarkup +subdirectories = bugpoint llc lli llvm-ar llvm-as llvm-bcanalyzer llvm-cov llvm-diff llvm-dis llvm-dwarfdump llvm-extract llvm-jitlistener llvm-link llvm-lto llvm-mc llvm-nm llvm-objdump llvm-rtdyld llvm-size macho-dump opt llvm-mcmarkup [component_0] type = Group diff --git a/tools/Makefile b/tools/Makefile index bacca717f3..11e417a307 100644 --- a/tools/Makefile +++ b/tools/Makefile @@ -27,7 +27,7 @@ OPTIONAL_DIRS := lldb # large and three small executables. This is done to minimize memory load # in parallel builds. Please retain this ordering. DIRS := llvm-config -PARALLEL_DIRS := opt llvm-as llvm-dis llc llvm-ar llvm-nm llvm-prof llvm-link \ +PARALLEL_DIRS := opt llvm-as llvm-dis llc llvm-ar llvm-nm llvm-link \ lli llvm-extract llvm-mc bugpoint llvm-bcanalyzer llvm-diff \ macho-dump llvm-objdump llvm-readobj llvm-rtdyld \ llvm-dwarfdump llvm-cov llvm-size llvm-stress llvm-mcmarkup \ diff --git a/tools/llvm-prof/CMakeLists.txt b/tools/llvm-prof/CMakeLists.txt deleted file mode 100644 index 442112bc88..0000000000 --- a/tools/llvm-prof/CMakeLists.txt +++ /dev/null @@ -1,5 +0,0 @@ -set(LLVM_LINK_COMPONENTS bitreader analysis) - -add_llvm_tool(llvm-prof - llvm-prof.cpp - ) diff --git a/tools/llvm-prof/LLVMBuild.txt b/tools/llvm-prof/LLVMBuild.txt deleted file mode 100644 index d59127cc26..0000000000 --- a/tools/llvm-prof/LLVMBuild.txt +++ /dev/null @@ -1,22 +0,0 @@ -;===- ./tools/llvm-prof/LLVMBuild.txt --------------------------*- Conf -*--===; -; -; The LLVM Compiler Infrastructure -; -; This file is distributed under the University of Illinois Open Source -; License. See LICENSE.TXT for details. -; -;===------------------------------------------------------------------------===; -; -; This is an LLVMBuild description file for the components in this subdirectory. -; -; For more information on the LLVMBuild system, please see: -; -; http://llvm.org/docs/LLVMBuild.html -; -;===------------------------------------------------------------------------===; - -[component_0] -type = Tool -name = llvm-prof -parent = Tools -required_libraries = Analysis BitReader diff --git a/tools/llvm-prof/Makefile b/tools/llvm-prof/Makefile deleted file mode 100644 index f829786765..0000000000 --- a/tools/llvm-prof/Makefile +++ /dev/null @@ -1,17 +0,0 @@ -##===- tools/llvm-prof/Makefile ----------------------------*- Makefile -*-===## -# -# The LLVM Compiler Infrastructure -# -# This file is distributed under the University of Illinois Open Source -# License. See LICENSE.TXT for details. -# -##===----------------------------------------------------------------------===## - -LEVEL := ../.. -TOOLNAME := llvm-prof -LINK_COMPONENTS := bitreader analysis - -# This tool has no plugins, optimize startup time. -TOOL_NO_EXPORTS = 1 - -include $(LEVEL)/Makefile.common diff --git a/tools/llvm-prof/llvm-prof.cpp b/tools/llvm-prof/llvm-prof.cpp deleted file mode 100644 index 6c340b89c6..0000000000 --- a/tools/llvm-prof/llvm-prof.cpp +++ /dev/null @@ -1,290 +0,0 @@ -//===- llvm-prof.cpp - Read in and process llvmprof.out data files --------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This tools is meant for use with the various LLVM profiling instrumentation -// passes. It reads in the data file produced by executing an instrumented -// program, and outputs a nice report. -// -//===----------------------------------------------------------------------===// - -#include "llvm/IR/LLVMContext.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/Analysis/ProfileInfoLoader.h" -#include "llvm/Assembly/AssemblyAnnotationWriter.h" -#include "llvm/Bitcode/ReaderWriter.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Module.h" -#include "llvm/PassManager.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/FormattedStream.h" -#include "llvm/Support/ManagedStatic.h" -#include "llvm/Support/MemoryBuffer.h" -#include "llvm/Support/PrettyStackTrace.h" -#include "llvm/Support/Signals.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/system_error.h" -#include <algorithm> -#include <iomanip> -#include <map> -#include <set> - -using namespace llvm; - -namespace { - cl::opt<std::string> - BitcodeFile(cl::Positional, cl::desc("<program bitcode file>"), - cl::Required); - - cl::opt<std::string> - ProfileDataFile(cl::Positional, cl::desc("<llvmprof.out file>"), - cl::Optional, cl::init("llvmprof.out")); - - cl::opt<bool> - PrintAnnotatedLLVM("annotated-llvm", - cl::desc("Print LLVM code with frequency annotations")); - cl::alias PrintAnnotated2("A", cl::desc("Alias for --annotated-llvm"), - cl::aliasopt(PrintAnnotatedLLVM)); - cl::opt<bool> - PrintAllCode("print-all-code", - cl::desc("Print annotated code for the entire program")); -} - -// PairSecondSort - A sorting predicate to sort by the second element of a pair. -template<class T> -struct PairSecondSortReverse - : public std::binary_function<std::pair<T, double>, - std::pair<T, double>, bool> { - bool operator()(const std::pair<T, double> &LHS, - const std::pair<T, double> &RHS) const { - return LHS.second > RHS.second; - } -}; - -static double ignoreMissing(double w) { - if (w == ProfileInfo::MissingValue) return 0; - return w; -} - -namespace { - class ProfileAnnotator : public AssemblyAnnotationWriter { - ProfileInfo &PI; - public: - ProfileAnnotator(ProfileInfo &pi) : PI(pi) {} - - virtual void emitFunctionAnnot(const Function *F, - formatted_raw_ostream &OS) { - double w = PI.getExecutionCount(F); - if (w != ProfileInfo::MissingValue) { - OS << ";;; %" << F->getName() << " called "<<(unsigned)w - <<" times.\n;;;\n"; - } - } - virtual void emitBasicBlockStartAnnot(const BasicBlock *BB, - formatted_raw_ostream &OS) { - double w = PI.getExecutionCount(BB); - if (w != ProfileInfo::MissingValue) { - if (w != 0) { - OS << "\t;;; Basic block executed " << (unsigned)w << " times.\n"; - } else { - OS << "\t;;; Never executed!\n"; - } - } - } - - virtual void emitBasicBlockEndAnnot(const BasicBlock *BB, - formatted_raw_ostream &OS) { - // Figure out how many times each successor executed. - std::vector<std::pair<ProfileInfo::Edge, double> > SuccCounts; - - const TerminatorInst *TI = BB->getTerminator(); - for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { - BasicBlock* Succ = TI->getSuccessor(s); - double w = ignoreMissing(PI.getEdgeWeight(std::make_pair(BB, Succ))); - if (w != 0) - SuccCounts.push_back(std::make_pair(std::make_pair(BB, Succ), w)); - } - if (!SuccCounts.empty()) { - OS << "\t;;; Out-edge counts:"; - for (unsigned i = 0, e = SuccCounts.size(); i != e; ++i) - OS << " [" << (SuccCounts[i]).second << " -> " - << (SuccCounts[i]).first.second->getName() << "]"; - OS << "\n"; - } - } - }; -} - -namespace { - /// ProfileInfoPrinterPass - Helper pass to dump the profile information for - /// a module. - // - // FIXME: This should move elsewhere. - class ProfileInfoPrinterPass : public ModulePass { - ProfileInfoLoader &PIL; - public: - static char ID; // Class identification, replacement for typeinfo. - explicit ProfileInfoPrinterPass(ProfileInfoLoader &_PIL) - : ModulePass(ID), PIL(_PIL) {} - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired<ProfileInfo>(); - } - - bool runOnModule(Module &M); - }; -} - -char ProfileInfoPrinterPass::ID = 0; - -bool ProfileInfoPrinterPass::runOnModule(Module &M) { - ProfileInfo &PI = getAnalysis<ProfileInfo>(); - - // Output a report. Eventually, there will be multiple reports selectable on - // the command line, for now, just keep things simple. - - // Emit the most frequent function table... - std::vector<std::pair<Function*, double> > FunctionCounts; - std::vector<std::pair<BasicBlock*, double> > Counts; - for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) { - if (FI->isDeclaration()) continue; - double w = ignoreMissing(PI.getExecutionCount(FI)); - FunctionCounts.push_back(std::make_pair(FI, w)); - for (Function::iterator BB = FI->begin(), BBE = FI->end(); - BB != BBE; ++BB) { - double w = ignoreMissing(PI.getExecutionCount(BB)); - Counts.push_back(std::make_pair(BB, w)); - } - } - - // Sort by the frequency, backwards. - sort(FunctionCounts.begin(), FunctionCounts.end(), - PairSecondSortReverse<Function*>()); - - double TotalExecutions = 0; - for (unsigned i = 0, e = FunctionCounts.size(); i != e; ++i) - TotalExecutions += FunctionCounts[i].second; - - outs() << "===" << std::string(73, '-') << "===\n" - << "LLVM profiling output for execution"; - if (PIL.getNumExecutions() != 1) outs() << "s"; - outs() << ":\n"; - - for (unsigned i = 0, e = PIL.getNumExecutions(); i != e; ++i) { - outs() << " "; - if (e != 1) outs() << i+1 << ". "; - outs() << PIL.getExecution(i) << "\n"; - } - - outs() << "\n===" << std::string(73, '-') << "===\n"; - outs() << "Function execution frequencies:\n\n"; - - // Print out the function frequencies... - outs() << " ## Frequency\n"; - for (unsigned i = 0, e = FunctionCounts.size(); i != e; ++i) { - if (FunctionCounts[i].second == 0) { - outs() << "\n NOTE: " << e-i << " function" - << (e-i-1 ? "s were" : " was") << " never executed!\n"; - break; - } - - outs() << format("%3d", i+1) << ". " - << format("%5.2g", FunctionCounts[i].second) << "/" - << format("%g", TotalExecutions) << " " - << FunctionCounts[i].first->getName() << "\n"; - } - - std::set<Function*> FunctionsToPrint; - - TotalExecutions = 0; - for (unsigned i = 0, e = Counts.size(); i != e; ++i) - TotalExecutions += Counts[i].second; - - // Sort by the frequency, backwards. - sort(Counts.begin(), Counts.end(), - PairSecondSortReverse<BasicBlock*>()); - - outs() << "\n===" << std::string(73, '-') << "===\n"; - outs() << "Top 20 most frequently executed basic blocks:\n\n"; - - // Print out the function frequencies... - outs() <<" ## %% \tFrequency\n"; - unsigned BlocksToPrint = Counts.size(); - if (BlocksToPrint > 20) BlocksToPrint = 20; - for (unsigned i = 0; i != BlocksToPrint; ++i) { - if (Counts[i].second == 0) break; - Function *F = Counts[i].first->getParent(); - outs() << format("%3d", i+1) << ". " - << format("%5g", Counts[i].second/(double)TotalExecutions*100)<<"% " - << format("%5.0f", Counts[i].second) << "/" - << format("%g", TotalExecutions) << "\t" - << F->getName() << "() - " - << Counts[i].first->getName() << "\n"; - FunctionsToPrint.insert(F); - } - - if (PrintAnnotatedLLVM || PrintAllCode) { - outs() << "\n===" << std::string(73, '-') << "===\n"; - outs() << "Annotated LLVM code for the module:\n\n"; - - ProfileAnnotator PA(PI); - - if (FunctionsToPrint.empty() || PrintAllCode) - M.print(outs(), &PA); - else - // Print just a subset of the functions. - for (std::set<Function*>::iterator I = FunctionsToPrint.begin(), - E = FunctionsToPrint.end(); I != E; ++I) - (*I)->print(outs(), &PA); - } - - return false; -} - -int main(int argc, char **argv) { - // Print a stack trace if we signal out. - sys::PrintStackTraceOnErrorSignal(); - PrettyStackTraceProgram X(argc, argv); - - LLVMContext &Context = getGlobalContext(); - llvm_shutdown_obj Y; // Call llvm_shutdown() on exit. - - cl::ParseCommandLineOptions(argc, argv, "llvm profile dump decoder\n"); - - // Read in the bitcode file... - std::string ErrorMessage; - OwningPtr<MemoryBuffer> Buffer; - error_code ec; - Module *M = 0; - if (!(ec = MemoryBuffer::getFileOrSTDIN(BitcodeFile, Buffer))) { - M = ParseBitcodeFile(Buffer.get(), Context, &ErrorMessage); - } else - ErrorMessage = ec.message(); - if (M == 0) { - errs() << argv[0] << ": " << BitcodeFile << ": " - << ErrorMessage << "\n"; - return 1; - } - - // Read the profiling information. This is redundant since we load it again - // using the standard profile info provider pass, but for now this gives us - // access to additional information not exposed via the ProfileInfo - // interface. - ProfileInfoLoader PIL(argv[0], ProfileDataFile); - - // Run the printer pass. - PassManager PassMgr; - PassMgr.add(createProfileLoaderPass(ProfileDataFile)); - PassMgr.add(new ProfileInfoPrinterPass(PIL)); - PassMgr.run(*M); - - return 0; -} |