diff options
Diffstat (limited to 'contrib/llvm/include/llvm/Analysis/PathNumbering.h')
| -rw-r--r-- | contrib/llvm/include/llvm/Analysis/PathNumbering.h | 304 |
1 files changed, 304 insertions, 0 deletions
diff --git a/contrib/llvm/include/llvm/Analysis/PathNumbering.h b/contrib/llvm/include/llvm/Analysis/PathNumbering.h new file mode 100644 index 0000000..7025e28 --- /dev/null +++ b/contrib/llvm/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 |
