aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Trick <atrick@apple.com>2011-01-29 01:09:53 +0000
committerAndrew Trick <atrick@apple.com>2011-01-29 01:09:53 +0000
commit04317cc618aeae28910916469e074d8ce0fcaa03 (patch)
tree5ea1ef8b97500d011b703e296c66a2056782b0a3
parentdb9cd76635220ebc6451069667e9aaaacb4fc455 (diff)
Implementation of path profiling.
Modified patch by Adam Preuss. This builds on the existing framework for block tracing, edge profiling and optimal edge profiling. See -help-hidden for new flags. For documentation, see the technical report "Implementation of Path Profiling..." in llvm.org/pubs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124515 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--include/llvm/Analysis/Passes.h26
-rw-r--r--include/llvm/Analysis/PathNumbering.h304
-rw-r--r--include/llvm/Analysis/PathProfileInfo.h113
-rw-r--r--include/llvm/Analysis/ProfileInfoTypes.h33
-rw-r--r--include/llvm/InitializePasses.h13
-rw-r--r--include/llvm/LinkAllPasses.h5
-rw-r--r--include/llvm/Transforms/Instrumentation.h3
-rw-r--r--lib/Analysis/Analysis.cpp10
-rw-r--r--lib/Analysis/CMakeLists.txt3
-rw-r--r--lib/Analysis/PathNumbering.cpp525
-rw-r--r--lib/Analysis/PathProfileInfo.cpp434
-rw-r--r--lib/Analysis/PathProfileVerifier.cpp207
-rw-r--r--lib/Transforms/Instrumentation/CMakeLists.txt1
-rw-r--r--lib/Transforms/Instrumentation/EdgeProfiling.cpp3
-rw-r--r--lib/Transforms/Instrumentation/Instrumentation.cpp1
-rw-r--r--lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp8
-rw-r--r--lib/Transforms/Instrumentation/PathProfiling.cpp1423
-rw-r--r--lib/Transforms/Instrumentation/ProfilingUtils.cpp22
-rw-r--r--lib/Transforms/Instrumentation/ProfilingUtils.h7
-rw-r--r--runtime/libprofile/CommonProfiling.c53
-rw-r--r--runtime/libprofile/PathProfiling.c266
-rw-r--r--runtime/libprofile/Profiling.h11
-rw-r--r--runtime/libprofile/libprofile.exports3
23 files changed, 3423 insertions, 51 deletions
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index 64bd290dd6..5b0c5b1e6b 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -116,6 +116,28 @@ namespace llvm {
//===--------------------------------------------------------------------===//
//
+ // createPathProfileLoaderPass - This pass loads information from a path
+ // profile dump file.
+ //
+ ModulePass *createPathProfileLoaderPass();
+ extern char &PathProfileLoaderPassID;
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createNoPathProfileInfoPass - This pass implements the default
+ // "no path profile".
+ //
+ ImmutablePass *createNoPathProfileInfoPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createPathProfileVerifierPass - This pass verifies path profiling
+ // information.
+ //
+ ModulePass *createPathProfileVerifierPass();
+
+ //===--------------------------------------------------------------------===//
+ //
// createDSAAPass - This pass implements simple context sensitive alias
// analysis.
//
@@ -140,7 +162,7 @@ namespace llvm {
// createLiveValuesPass - This creates an instance of the LiveValues pass.
//
FunctionPass *createLiveValuesPass();
-
+
//===--------------------------------------------------------------------===//
//
/// createLazyValueInfoPass - This creates an instance of the LazyValueInfo
@@ -153,7 +175,7 @@ namespace llvm {
// LoopDependenceAnalysis pass.
//
LoopPass *createLoopDependenceAnalysisPass();
-
+
// Minor pass prototypes, allowing us to expose them through bugpoint and
// analyze.
FunctionPass *createInstCountPass();
diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h
new file mode 100644
index 0000000000..7025e28484
--- /dev/null
+++ b/include/llvm/Analysis/PathNumbering.h
@@ -0,0 +1,304 @@
+//===- PathNumbering.h ----------------------------------------*- C++ -*---===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Ball-Larus path numbers uniquely identify paths through a directed acyclic
+// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony
+// edges to obtain a DAG, and thus the unique path numbers [Ball96].
+//
+// The purpose of this analysis is to enumerate the edges in a CFG in order
+// to obtain paths from path numbers in a convenient manner. As described in
+// [Ball96] edges can be enumerated such that given a path number by following
+// the CFG and updating the path number, the path is obtained.
+//
+// [Ball96]
+// T. Ball and J. R. Larus. "Efficient Path Profiling."
+// International Symposium on Microarchitecture, pages 46-57, 1996.
+// http://portal.acm.org/citation.cfm?id=243857
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_PATH_NUMBERING_H
+#define LLVM_PATH_NUMBERING_H
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Analysis/ProfileInfoTypes.h"
+#include <map>
+#include <stack>
+#include <vector>
+
+namespace llvm {
+class BallLarusNode;
+class BallLarusEdge;
+class BallLarusDag;
+
+// typedefs for storage/ interators of various DAG components
+typedef std::vector<BallLarusNode*> BLNodeVector;
+typedef std::vector<BallLarusNode*>::iterator BLNodeIterator;
+typedef std::vector<BallLarusEdge*> BLEdgeVector;
+typedef std::vector<BallLarusEdge*>::iterator BLEdgeIterator;
+typedef std::map<BasicBlock*, BallLarusNode*> BLBlockNodeMap;
+typedef std::stack<BallLarusNode*> BLNodeStack;
+
+// Represents a basic block with information necessary for the BallLarus
+// algorithms.
+class BallLarusNode {
+public:
+ enum NodeColor { WHITE, GRAY, BLACK };
+
+ // Constructor: Initializes a new Node for the given BasicBlock
+ BallLarusNode(BasicBlock* BB) :
+ _basicBlock(BB), _numberPaths(0), _color(WHITE) {
+ static unsigned nextUID = 0;
+ _uid = nextUID++;
+ }
+
+ // Returns the basic block for the BallLarusNode
+ BasicBlock* getBlock();
+
+ // Get/set the number of paths to the exit starting at the node.
+ unsigned getNumberPaths();
+ void setNumberPaths(unsigned numberPaths);
+
+ // Get/set the NodeColor used in graph algorithms.
+ NodeColor getColor();
+ void setColor(NodeColor color);
+
+ // Iterator information for predecessor edges. Includes phony and
+ // backedges.
+ BLEdgeIterator predBegin();
+ BLEdgeIterator predEnd();
+ unsigned getNumberPredEdges();
+
+ // Iterator information for successor edges. Includes phony and
+ // backedges.
+ BLEdgeIterator succBegin();
+ BLEdgeIterator succEnd();
+ unsigned getNumberSuccEdges();
+
+ // Add an edge to the predecessor list.
+ void addPredEdge(BallLarusEdge* edge);
+
+ // Remove an edge from the predecessor list.
+ void removePredEdge(BallLarusEdge* edge);
+
+ // Add an edge to the successor list.
+ void addSuccEdge(BallLarusEdge* edge);
+
+ // Remove an edge from the successor list.
+ void removeSuccEdge(BallLarusEdge* edge);
+
+ // Returns the name of the BasicBlock being represented. If BasicBlock
+ // is null then returns "<null>". If BasicBlock has no name, then
+ // "<unnamed>" is returned. Intended for use with debug output.
+ std::string getName();
+
+private:
+ // The corresponding underlying BB.
+ BasicBlock* _basicBlock;
+
+ // Holds the predecessor edges of this node.
+ BLEdgeVector _predEdges;
+
+ // Holds the successor edges of this node.
+ BLEdgeVector _succEdges;
+
+ // The number of paths from the node to the exit.
+ unsigned _numberPaths;
+
+ // 'Color' used by graph algorithms to mark the node.
+ NodeColor _color;
+
+ // Unique ID to ensure naming difference with dotgraphs
+ unsigned _uid;
+
+ // Removes an edge from an edgeVector. Used by removePredEdge and
+ // removeSuccEdge.
+ void removeEdge(BLEdgeVector& v, BallLarusEdge* e);
+};
+
+// Represents an edge in the Dag. For an edge, v -> w, v is the source, and
+// w is the target.
+class BallLarusEdge {
+public:
+ enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE,
+ BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY };
+
+ // Constructor: Initializes an BallLarusEdge with a source and target.
+ BallLarusEdge(BallLarusNode* source, BallLarusNode* target,
+ unsigned duplicateNumber)
+ : _source(source), _target(target), _weight(0), _edgeType(NORMAL),
+ _realEdge(NULL), _duplicateNumber(duplicateNumber) {}
+
+ // Returns the source/ target node of this edge.
+ BallLarusNode* getSource() const;
+ BallLarusNode* getTarget() const;
+
+ // Sets the type of the edge.
+ EdgeType getType() const;
+
+ // Gets the type of the edge.
+ void setType(EdgeType type);
+
+ // Returns the weight of this edge. Used to decode path numbers to
+ // sequences of basic blocks.
+ unsigned getWeight();
+
+ // Sets the weight of the edge. Used during path numbering.
+ void setWeight(unsigned weight);
+
+ // Gets/sets the phony edge originating at the root.
+ BallLarusEdge* getPhonyRoot();
+ void setPhonyRoot(BallLarusEdge* phonyRoot);
+
+ // Gets/sets the phony edge terminating at the exit.
+ BallLarusEdge* getPhonyExit();
+ void setPhonyExit(BallLarusEdge* phonyExit);
+
+ // Gets/sets the associated real edge if this is a phony edge.
+ BallLarusEdge* getRealEdge();
+ void setRealEdge(BallLarusEdge* realEdge);
+
+ // Returns the duplicate number of the edge.
+ unsigned getDuplicateNumber();
+
+protected:
+ // Source node for this edge.
+ BallLarusNode* _source;
+
+ // Target node for this edge.
+ BallLarusNode* _target;
+
+private:
+ // Edge weight cooresponding to path number increments before removing
+ // increments along a spanning tree. The sum over the edge weights gives
+ // the path number.
+ unsigned _weight;
+
+ // Type to represent for what this edge is intended
+ EdgeType _edgeType;
+
+ // For backedges and split-edges, the phony edge which is linked to the
+ // root node of the DAG. This contains a path number initialization.
+ BallLarusEdge* _phonyRoot;
+
+ // For backedges and split-edges, the phony edge which is linked to the
+ // exit node of the DAG. This contains a path counter increment, and
+ // potentially a path number increment.
+ BallLarusEdge* _phonyExit;
+
+ // If this is a phony edge, _realEdge is a link to the back or split
+ // edge. Otherwise, this is null.
+ BallLarusEdge* _realEdge;
+
+ // An ID to differentiate between those edges which have the same source
+ // and destination blocks.
+ unsigned _duplicateNumber;
+};
+
+// Represents the Ball Larus DAG for a given Function. Can calculate
+// various properties required for instrumentation or analysis. E.g. the
+// edge weights that determine the path number.
+class BallLarusDag {
+public:
+ // Initializes a BallLarusDag from the CFG of a given function. Must
+ // call init() after creation, since some initialization requires
+ // virtual functions.
+ BallLarusDag(Function &F)
+ : _root(NULL), _exit(NULL), _function(F) {}
+
+ // Initialization that requires virtual functions which are not fully
+ // functional in the constructor.
+ void init();
+
+ // Frees all memory associated with the DAG.
+ virtual ~BallLarusDag();
+
+ // Calculate the path numbers by assigning edge increments as prescribed
+ // in Ball-Larus path profiling.
+ void calculatePathNumbers();
+
+ // Returns the number of paths for the DAG.
+ unsigned getNumberOfPaths();
+
+ // Returns the root (i.e. entry) node for the DAG.
+ BallLarusNode* getRoot();
+
+ // Returns the exit node for the DAG.
+ BallLarusNode* getExit();
+
+ // Returns the function for the DAG.
+ Function& getFunction();
+
+ // Clears the node colors.
+ void clearColors(BallLarusNode::NodeColor color);
+
+protected:
+ // All nodes in the DAG.
+ BLNodeVector _nodes;
+
+ // All edges in the DAG.
+ BLEdgeVector _edges;
+
+ // All backedges in the DAG.
+ BLEdgeVector _backEdges;
+
+ // Allows subclasses to determine which type of Node is created.
+ // Override this method to produce subclasses of BallLarusNode if
+ // necessary. The destructor of BallLarusDag will call free on each pointer
+ // created.
+ virtual BallLarusNode* createNode(BasicBlock* BB);
+
+ // Allows subclasses to determine which type of Edge is created.
+ // Override this method to produce subclasses of BallLarusEdge if
+ // necessary. Parameters source and target will have been created by
+ // createNode and can be cast to the subclass of BallLarusNode*
+ // returned by createNode. The destructor of BallLarusDag will call free
+ // on each pointer created.
+ virtual BallLarusEdge* createEdge(BallLarusNode* source, BallLarusNode*
+ target, unsigned duplicateNumber);
+
+ // Proxy to node's constructor. Updates the DAG state.
+ BallLarusNode* addNode(BasicBlock* BB);
+
+ // Proxy to edge's constructor. Updates the DAG state.
+ BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target,
+ unsigned duplicateNumber);
+
+private:
+ // The root (i.e. entry) node for this DAG.
+ BallLarusNode* _root;
+
+ // The exit node for this DAG.
+ BallLarusNode* _exit;
+
+ // The function represented by this DAG.
+ Function& _function;
+
+ // Processes one node and its imediate edges for building the DAG.
+ void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack);
+
+ // Process an edge in the CFG for DAG building.
+ void buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack,
+ BallLarusNode* currentNode, BasicBlock* succBB,
+ unsigned duplicateNumber);
+
+ // The weight on each edge is the increment required along any path that
+ // contains that edge.
+ void calculatePathNumbersFrom(BallLarusNode* node);
+
+ // Adds a backedge with its phony edges. Updates the DAG state.
+ void addBackedge(BallLarusNode* source, BallLarusNode* target,
+ unsigned duplicateCount);
+};
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/PathProfileInfo.h b/include/llvm/Analysis/PathProfileInfo.h
new file mode 100644
index 0000000000..263763f7a8
--- /dev/null
+++ b/include/llvm/Analysis/PathProfileInfo.h
@@ -0,0 +1,113 @@
+//===- PathProfileInfo.h --------------------------------------*- C++ -*---===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file outlines the interface used by optimizers to load path profiles.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_PATHPROFILEINFO_H
+#define LLVM_PATHPROFILEINFO_H
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Analysis/PathNumbering.h"
+#include <stack>
+
+namespace llvm {
+
+class ProfilePath;
+class ProfilePathEdge;
+class PathProfileInfo;
+
+typedef std::vector<ProfilePathEdge> ProfilePathEdgeVector;
+typedef std::vector<ProfilePathEdge>::iterator ProfilePathEdgeIterator;
+
+typedef std::vector<BasicBlock*> ProfilePathBlockVector;
+typedef std::vector<BasicBlock*>::iterator ProfilePathBlockIterator;
+
+typedef std::map<unsigned int,ProfilePath*> ProfilePathMap;
+typedef std::map<unsigned int,ProfilePath*>::iterator ProfilePathIterator;
+
+typedef std::map<Function*,unsigned int> FunctionPathCountMap;
+typedef std::map<Function*,ProfilePathMap> FunctionPathMap;
+typedef std::map<Function*,ProfilePathMap>::iterator FunctionPathIterator;
+
+class ProfilePathEdge {
+public:
+ ProfilePathEdge(BasicBlock* source, BasicBlock* target,
+ unsigned duplicateNumber);
+
+ inline unsigned getDuplicateNumber() { return _duplicateNumber; }
+ inline BasicBlock* getSource() { return _source; }
+ inline BasicBlock* getTarget() { return _target; }
+
+protected:
+ BasicBlock* _source;
+ BasicBlock* _target;
+ unsigned _duplicateNumber;
+};
+
+class ProfilePath {
+public:
+ ProfilePath(unsigned int number, unsigned int count,
+ double countStdDev, PathProfileInfo* ppi);
+
+ double getFrequency() const;
+
+ inline unsigned int getNumber() const { return _number; }
+ inline unsigned int getCount() const { return _count; }
+ inline double getCountStdDev() const { return _countStdDev; }
+
+ ProfilePathEdgeVector* getPathEdges() const;
+ ProfilePathBlockVector* getPathBlocks() const;
+
+ BasicBlock* getFirstBlockInPath() const;
+
+private:
+ unsigned int _number;
+ unsigned int _count;
+ double _countStdDev;
+
+ // double pointer back to the profiling info
+ PathProfileInfo* _ppi;
+};
+
+// TODO: overload [] operator for getting path
+// Add: getFunctionCallCount()
+class PathProfileInfo {
+ public:
+ PathProfileInfo();
+ ~PathProfileInfo();
+
+ void setCurrentFunction(Function* F);
+ Function* getCurrentFunction() const;
+ BasicBlock* getCurrentFunctionEntry();
+
+ ProfilePath* getPath(unsigned int number);
+ unsigned int getPotentialPathCount();
+
+ ProfilePathIterator pathBegin();
+ ProfilePathIterator pathEnd();
+ unsigned int pathsRun();
+
+ static char ID; // Pass identification
+ std::string argList;
+
+protected:
+ FunctionPathMap _functionPaths;
+ FunctionPathCountMap _functionPathCounts;
+
+private:
+ BallLarusDag* _currentDag;
+ Function* _currentFunction;
+
+ friend class ProfilePath;
+};
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h
index 0d531d5c5f..f344af6925 100644
--- a/include/llvm/Analysis/ProfileInfoTypes.h
+++ b/include/llvm/Analysis/ProfileInfoTypes.h
@@ -1,4 +1,4 @@
-/*===-- ProfileInfoTypes.h - Profiling info shared constants ------*- C -*-===*\
+/*===-- ProfileInfoTypes.h - Profiling info shared constants --------------===*\
|*
|* The LLVM Compiler Infrastructure
|*
@@ -16,6 +16,17 @@
#ifndef LLVM_ANALYSIS_PROFILEINFOTYPES_H
#define LLVM_ANALYSIS_PROFILEINFOTYPES_H
+// Included by libprofile.
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+/* IDs to distinguish between those path counters stored in hashses vs arrays */
+enum ProfilingStorageType {
+ ProfilingArray = 1,
+ ProfilingHash = 2
+};
+
enum ProfilingType {
ArgumentInfo = 1, /* The command line argument block */
FunctionInfo = 2, /* Function profiling information */
@@ -26,4 +37,24 @@ enum ProfilingType {
OptEdgeInfo = 7 /* Edge profiling information, optimal version */
};
+/*
+ * The header for tables that map path numbers to path counters.
+ */
+typedef struct {
+ unsigned fnNumber; /* function number for these counters */
+ unsigned numEntries; /* number of entries stored */
+} PathProfileHeader;
+
+/*
+ * Describes an entry in a tagged table for path counters.
+ */
+typedef struct {
+ unsigned pathNumber;
+ unsigned pathCounter;
+} PathProfileTableEntry;
+
+#if defined(__cplusplus)
+}
+#endif
+
#endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */
diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 8aeb1c2b98..2a17c383f8 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -19,19 +19,19 @@ namespace llvm {
class PassRegistry;
-/// initializeCore - Initialize all passes linked into the
+/// initializeCore - Initialize all passes linked into the
/// TransformUtils library.
void initializeCore(PassRegistry&);
-/// initializeTransformUtils - Initialize all passes linked into the
+/// initializeTransformUtils - Initialize all passes linked into the
/// TransformUtils library.
void initializeTransformUtils(PassRegistry&);
-/// initializeScalarOpts - Initialize all passes linked into the
+/// initializeScalarOpts - Initialize all passes linked into the
/// ScalarOpts library.
void initializeScalarOpts(PassRegistry&);
-/// initializeInstCombine - Initialize all passes linked into the
+/// initializeInstCombine - Initialize all passes linked into the
/// ScalarOpts library.
void initializeInstCombine(PassRegistry&);
@@ -93,6 +93,7 @@ void initializeDominanceFrontierPass(PassRegistry&);
void initializeDominatorTreePass(PassRegistry&);
void initializeEdgeBundlesPass(PassRegistry&);
void initializeEdgeProfilerPass(PassRegistry&);
+void initializePathProfilerPass(PassRegistry&);
void initializeEarlyCSEPass(PassRegistry&);
void initializeExpandISelPseudosPass(PassRegistry&);
void initializeFindUsedTypesPass(PassRegistry&);
@@ -125,6 +126,7 @@ void initializeLiveStacksPass(PassRegistry&);
void initializeLiveValuesPass(PassRegistry&);
void initializeLiveVariablesPass(PassRegistry&);
void initializeLoaderPassPass(PassRegistry&);
+void initializePathProfileLoaderPassPass(PassRegistry&);
void initializeLoopDeletionPass(PassRegistry&);
void initializeLoopDependenceAnalysisPass(PassRegistry&);
void initializeLoopExtractorPass(PassRegistry&);
@@ -157,6 +159,7 @@ void initializeMergeFunctionsPass(PassRegistry&);
void initializeModuleDebugInfoPrinterPass(PassRegistry&);
void initializeNoAAPass(PassRegistry&);
void initializeNoProfileInfoPass(PassRegistry&);
+void initializeNoPathProfileInfoPass(PassRegistry&);
void initializeOptimalEdgeProfilerPass(PassRegistry&);
void initializeOptimizePHIsPass(PassRegistry&);
void initializePEIPass(PassRegistry&);
@@ -177,6 +180,8 @@ void initializePrintModulePassPass(PassRegistry&);
void initializeProcessImplicitDefsPass(PassRegistry&);
void initializeProfileEstimatorPassPass(PassRegistry&);
void initializeProfileInfoAnalysisGroup(PassRegistry&);
+void initializePathProfileInfoAnalysisGroup(PassRegistry&);
+void initializePathProfileVerifierPass(PassRegistry&);
void initializeProfileVerifierPassPass(PassRegistry&);
void initializePromotePassPass(PassRegistry&);
void initializePruneEHPass(PassRegistry&);
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index a6f89c5938..69e1bd919f 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -7,7 +7,7 @@
//
//===----------------------------------------------------------------------===//
//
-// This header file pulls in all transformation and analysis passes for tools
+// This header file pulls in all transformation and analysis passes for tools
// like opt and bugpoint that need this functionality.
//
//===----------------------------------------------------------------------===//
@@ -70,6 +70,7 @@ namespace {
(void) llvm::createDomViewerPass();
(void) llvm::createEdgeProfilerPass();
(void) llvm::createOptimalEdgeProfilerPass();
+ (void) llvm::createPathProfilerPass();
(void) llvm::createFunctionInliningPass();
(void) llvm::createAlwaysInlinerPass();
(void) llvm::createGlobalDCEPass();
@@ -99,7 +100,9 @@ namespace {
(void) llvm::createNoProfileInfoPass();
(void) llvm::createProfileEstimatorPass();
(void) llvm::createProfileVerifierPass();
+ (void) llvm::createPathProfileVerifierPass();
(void) llvm::createProfileLoaderPass();
+ (void) llvm::createPathProfileLoaderPass();
(void) llvm::createPromoteMemoryToRegisterPass();
(void) llvm::createDemoteRegisterToMemoryPass();
(void) llvm::createPruneEHPass();
diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h
index 9c579ac761..aa9873fb8a 100644
--- a/include/llvm/Transforms/Instrumentation.h
+++ b/include/llvm/Transforms/Instrumentation.h
@@ -25,6 +25,9 @@ ModulePass *createEdgeProfilerPass();
// Insert optimal edge profiling instrumentation
ModulePass *createOptimalEdgeProfilerPass();
+// Insert path profiling instrumentation
+ModulePass *createPathProfilerPass();
+
} // End llvm namespace
#endif
diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp
index c948214042..1af1c35f53 100644
--- a/lib/Analysis/Analysis.cpp
+++ b/lib/Analysis/Analysis.cpp
@@ -53,9 +53,13 @@ void llvm::initializeAnalysis(PassRegistry &Registry) {
initializePostDominanceFrontierPass(Registry);
initializeProfileEstimatorPassPass(Registry);
initializeNoProfileInfoPass(Registry);
+ initializeNoPathProfileInfoPass(Registry);
initializeProfileInfoAnalysisGroup(Registry);
+ initializePathProfileInfoAnalysisGroup(Registry);
initializeLoaderPassPass(Registry);
+ initializePathProfileLoaderPassPass(Registry);
initializeProfileVerifierPassPass(Registry);
+ initializePathProfileVerifierPass(Registry);
initializeRegionInfoPass(Registry);
initializeRegionViewerPass(Registry);
initializeRegionPrinterPass(Registry);
@@ -73,14 +77,14 @@ void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
LLVMBool LLVMVerifyModule(LLVMModuleRef M, LLVMVerifierFailureAction Action,
char **OutMessages) {
std::string Messages;
-
+
LLVMBool Result = verifyModule(*unwrap(M),
static_cast<VerifierFailureAction>(Action),
OutMessages? &Messages : 0);
-
+
if (OutMessages)
*OutMessages = strdup(Messages.c_str());
-
+
return Result;
}
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index a43cd377dd..1f43b4481d 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -33,6 +33,9 @@ add_llvm_library(LLVMAnalysis
MemoryBuiltins.cpp
MemoryDependenceAnalysis.cpp
ModuleDebugInfoPrinter.cpp
+ PathNumbering.cpp
+ PathProfileInfo.cpp
+ PathProfileVerifier.cpp
NoAliasAnalysis.cpp
PHITransAddr.cpp
PostDominators.cpp
diff --git a/lib/Analysis/PathNumbering.cpp b/lib/Analysis/PathNumbering.cpp
new file mode 100644
index 0000000000..5d3f6bbc7b
--- /dev/null
+++ b/lib/Analysis/PathNumbering.cpp
@@ -0,0 +1,525 @@
+//===- PathNumbering.cpp --------------------------------------*- C++ -*---===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Ball-Larus path numbers uniquely identify paths through a directed acyclic
+// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony
+// edges to obtain a DAG, and thus the unique path numbers [Ball96].
+//
+// The purpose of this analysis is to enumerate the edges in a CFG in order
+// to obtain paths from path numbers in a convenient manner. As described in
+// [Ball96] edges can be enumerated such that given a path number by following
+// the CFG and updating the path number, the path is obtained.
+//
+// [Ball96]
+// T. Ball and J. R. Larus. "Efficient Path Profiling."
+// International Symposium on Microarchitecture, pages 46-57, 1996.
+// http://portal.acm.org/citation.cfm?id=243857
+//
+//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "ball-larus-numbering"
+
+#include "llvm/Analysis/PathNumbering.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/InstrTypes.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/TypeBuilder.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <map>
+#include <queue>
+#include <set>
+#include <stack>
+#include <string>
+#include <utility>
+#include <vector>
+#include <sstream>
+
+using namespace llvm;
+
+// Are we enabling early termination
+static cl::opt<bool> ProcessEarlyTermination(
+ "path-profile-early-termination", cl::Hidden,
+ cl::desc("In path profiling, insert extra instrumentation to account for "
+ "unexpected function termination."));
+
+// Returns the basic block for the BallLarusNode
+BasicBlock* BallLarusNode::getBlock() {
+ return(_basicBlock);
+}
+
+// Returns the number of paths to the exit starting at the node.
+unsigned BallLarusNode::getNumberPaths() {
+ return(_numberPaths);
+}
+
+// Sets the number of paths to the exit starting at the node.
+void BallLarusNode::setNumberPaths(unsigned numberPaths) {
+ _numberPaths = numberPaths;
+}
+
+// Gets the NodeColor used in graph algorithms.
+BallLarusNode::NodeColor BallLarusNode::getColor() {
+ return(_color);
+}
+
+// Sets the NodeColor used in graph algorithms.
+void BallLarusNode::setColor(BallLarusNode::NodeColor color) {
+ _color = color;
+}
+
+// Returns an iterator over predecessor edges. Includes phony and
+// backedges.
+BLEdgeIterator BallLarusNode::predBegin() {
+ return(_predEdges.begin());
+}
+
+// Returns the end sentinel for the predecessor iterator.
+BLEdgeIterator BallLarusNode::predEnd() {
+ return(_predEdges.end());
+}
+
+// Returns the number of predecessor edges. Includes phony and
+// backedges.
+unsigned BallLarusNode::getNumberPredEdges() {
+ return(_predEdges.size());
+}
+
+// Returns an iterator over successor edges. Includes phony and
+// backedges.
+BLEdgeIterator BallLarusNode::succBegin() {
+ return(_succEdges.begin());
+}
+
+// Returns the end sentinel for the successor iterator.
+BLEdgeIterator BallLarusNode::succEnd() {
+ return(_succEdges.end());
+}
+
+// Returns the number of successor edges. Includes phony and
+// backedges.
+unsigned BallLarusNode::getNumberSuccEdges() {
+ return(_succEdges.size());
+}
+
+// Add an edge to the predecessor list.
+void BallLarusNode::addPredEdge(BallLarusEdge* edge) {
+ _predEdges.push_back(edge);
+}
+
+// Remove an edge from the predecessor list.
+void BallLarusNode::removePredEdge(BallLarusEdge* edge) {
+ removeEdge(_predEdges, edge);
+}
+
+// Add an edge to the successor list.
+void BallLarusNode::addSuccEdge(BallLarusEdge* edge) {
+ _succEdges.push_back(edge);
+}
+
+// Remove an edge from the successor list.
+void BallLarusNode::removeSuccEdge(BallLarusEdge* edge) {
+ removeEdge(_succEdges, edge);
+}
+
+// Returns the name of the BasicBlock being represented. If BasicBlock
+// is null then returns "<null>". If BasicBlock has no name, then
+// "<unnamed>" is returned. Intended for use with debug outp