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

7 files changed, 489 insertions, 8 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