104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===- PathNumbering.h ----------------------------------------*- C++ -*---===// 204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// The LLVM Compiler Infrastructure 404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// This file is distributed under the University of Illinois Open Source 604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// License. See LICENSE.TXT for details. 704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===----------------------------------------------------------------------===// 904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 1004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Ball-Larus path numbers uniquely identify paths through a directed acyclic 1104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony 1204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// edges to obtain a DAG, and thus the unique path numbers [Ball96]. 1304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 1404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// The purpose of this analysis is to enumerate the edges in a CFG in order 1504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// to obtain paths from path numbers in a convenient manner. As described in 1604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// [Ball96] edges can be enumerated such that given a path number by following 1704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// the CFG and updating the path number, the path is obtained. 1804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 1904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// [Ball96] 2004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// T. Ball and J. R. Larus. "Efficient Path Profiling." 2104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// International Symposium on Microarchitecture, pages 46-57, 1996. 2204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// http://portal.acm.org/citation.cfm?id=243857 2304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// 2404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===----------------------------------------------------------------------===// 2504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 26674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_PATHNUMBERING_H 27674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_PATHNUMBERING_H 2804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 29255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Analysis/ProfileInfoTypes.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 3204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Pass.h" 3304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/CFG.h" 3404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <map> 3504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <stack> 3604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <vector> 3704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 3804317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricknamespace llvm { 3904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickclass BallLarusNode; 4004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickclass BallLarusEdge; 4104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickclass BallLarusDag; 4204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// typedefs for storage/ interators of various DAG components 4404317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::vector<BallLarusNode*> BLNodeVector; 4504317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::vector<BallLarusNode*>::iterator BLNodeIterator; 4604317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::vector<BallLarusEdge*> BLEdgeVector; 4704317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::vector<BallLarusEdge*>::iterator BLEdgeIterator; 4804317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::map<BasicBlock*, BallLarusNode*> BLBlockNodeMap; 4904317cc618aeae28910916469e074d8ce0fcaa03Andrew Tricktypedef std::stack<BallLarusNode*> BLNodeStack; 5004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 5104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Represents a basic block with information necessary for the BallLarus 5204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// algorithms. 5304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickclass BallLarusNode { 5404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickpublic: 5504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick enum NodeColor { WHITE, GRAY, BLACK }; 5604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 5704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Constructor: Initializes a new Node for the given BasicBlock 5804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode(BasicBlock* BB) : 5904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _basicBlock(BB), _numberPaths(0), _color(WHITE) { 6004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick static unsigned nextUID = 0; 6104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _uid = nextUID++; 6204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 6304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 6404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the basic block for the BallLarusNode 6504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* getBlock(); 6604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 6704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Get/set the number of paths to the exit starting at the node. 6804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned getNumberPaths(); 6904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setNumberPaths(unsigned numberPaths); 7004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 7104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Get/set the NodeColor used in graph algorithms. 7204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick NodeColor getColor(); 7304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setColor(NodeColor color); 7404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 7504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Iterator information for predecessor edges. Includes phony and 7604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // backedges. 7704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeIterator predBegin(); 7804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeIterator predEnd(); 7904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned getNumberPredEdges(); 8004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Iterator information for successor edges. Includes phony and 8204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // backedges. 8304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeIterator succBegin(); 8404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeIterator succEnd(); 8504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned getNumberSuccEdges(); 8604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Add an edge to the predecessor list. 8804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void addPredEdge(BallLarusEdge* edge); 8904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Remove an edge from the predecessor list. 9104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void removePredEdge(BallLarusEdge* edge); 9204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Add an edge to the successor list. 9404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void addSuccEdge(BallLarusEdge* edge); 9504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Remove an edge from the successor list. 9704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void removeSuccEdge(BallLarusEdge* edge); 9804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the name of the BasicBlock being represented. If BasicBlock 10004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // is null then returns "<null>". If BasicBlock has no name, then 10104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // "<unnamed>" is returned. Intended for use with debug output. 10204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::string getName(); 10304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickprivate: 10504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The corresponding underlying BB. 10604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* _basicBlock; 10704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Holds the predecessor edges of this node. 10904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeVector _predEdges; 11004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Holds the successor edges of this node. 11204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeVector _succEdges; 11304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The number of paths from the node to the exit. 11504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned _numberPaths; 11604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // 'Color' used by graph algorithms to mark the node. 11804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick NodeColor _color; 11904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 12004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Unique ID to ensure naming difference with dotgraphs 12104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned _uid; 12204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 12304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Removes an edge from an edgeVector. Used by removePredEdge and 12404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // removeSuccEdge. 12504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void removeEdge(BLEdgeVector& v, BallLarusEdge* e); 12604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick}; 12704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 12804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Represents an edge in the Dag. For an edge, v -> w, v is the source, and 12904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// w is the target. 13004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickclass BallLarusEdge { 13104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickpublic: 13204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE, 13304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY }; 13404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 13504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Constructor: Initializes an BallLarusEdge with a source and target. 13604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge(BallLarusNode* source, BallLarusNode* target, 13704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateNumber) 13804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick : _source(source), _target(target), _weight(0), _edgeType(NORMAL), 13904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _realEdge(NULL), _duplicateNumber(duplicateNumber) {} 14004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 14104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the source/ target node of this edge. 14204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* getSource() const; 14304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* getTarget() const; 14404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 14504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Sets the type of the edge. 14604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick EdgeType getType() const; 14704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 14804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Gets the type of the edge. 14904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setType(EdgeType type); 15004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 15104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the weight of this edge. Used to decode path numbers to 15204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // sequences of basic blocks. 15304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned getWeight(); 15404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 15504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Sets the weight of the edge. Used during path numbering. 15604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setWeight(unsigned weight); 15704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 15804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Gets/sets the phony edge originating at the root. 15904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* getPhonyRoot(); 16004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setPhonyRoot(BallLarusEdge* phonyRoot); 16104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 16204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Gets/sets the phony edge terminating at the exit. 16304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* getPhonyExit(); 16404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setPhonyExit(BallLarusEdge* phonyExit); 16504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 16604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Gets/sets the associated real edge if this is a phony edge. 16704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* getRealEdge(); 16804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void setRealEdge(BallLarusEdge* realEdge); 16904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the duplicate number of the edge. 17104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned getDuplicateNumber(); 17204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickprotected: 17404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Source node for this edge. 17504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* _source; 17604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Target node for this edge. 17804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* _target; 17904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickprivate: 18104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Edge weight cooresponding to path number increments before removing 18204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // increments along a spanning tree. The sum over the edge weights gives 18304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // the path number. 18404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned _weight; 18504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Type to represent for what this edge is intended 18704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick EdgeType _edgeType; 18804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // For backedges and split-edges, the phony edge which is linked to the 19004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // root node of the DAG. This contains a path number initialization. 19104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* _phonyRoot; 19204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 19304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // For backedges and split-edges, the phony edge which is linked to the 19404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // exit node of the DAG. This contains a path counter increment, and 19504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // potentially a path number increment. 19604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* _phonyExit; 19704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 19804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // If this is a phony edge, _realEdge is a link to the back or split 19904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // edge. Otherwise, this is null. 20004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* _realEdge; 20104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 20204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // An ID to differentiate between those edges which have the same source 20304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // and destination blocks. 20404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned _duplicateNumber; 20504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick}; 20604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 20704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Represents the Ball Larus DAG for a given Function. Can calculate 20804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// various properties required for instrumentation or analysis. E.g. the 20904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// edge weights that determine the path number. 21004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickclass BallLarusDag { 21104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickpublic: 21204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Initializes a BallLarusDag from the CFG of a given function. Must 21304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // call init() after creation, since some initialization requires 21404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // virtual functions. 21504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusDag(Function &F) 21604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick : _root(NULL), _exit(NULL), _function(F) {} 21704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 21804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Initialization that requires virtual functions which are not fully 21904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // functional in the constructor. 22004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void init(); 22104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 22204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Frees all memory associated with the DAG. 22304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick virtual ~BallLarusDag(); 22404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 22504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Calculate the path numbers by assigning edge increments as prescribed 22604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // in Ball-Larus path profiling. 22704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void calculatePathNumbers(); 22804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 22904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the number of paths for the DAG. 23004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned getNumberOfPaths(); 23104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 23204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the root (i.e. entry) node for the DAG. 23304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* getRoot(); 23404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 23504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the exit node for the DAG. 23604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* getExit(); 23704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 23804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Returns the function for the DAG. 23904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick Function& getFunction(); 24004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 24104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Clears the node colors. 24204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void clearColors(BallLarusNode::NodeColor color); 24304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 24404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickprotected: 24504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // All nodes in the DAG. 24604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLNodeVector _nodes; 24704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 24804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // All edges in the DAG. 24904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeVector _edges; 25004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 25104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // All backedges in the DAG. 25204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLEdgeVector _backEdges; 25304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 25404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Allows subclasses to determine which type of Node is created. 25504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Override this method to produce subclasses of BallLarusNode if 25604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // necessary. The destructor of BallLarusDag will call free on each pointer 25704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // created. 25804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick virtual BallLarusNode* createNode(BasicBlock* BB); 25904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 26004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Allows subclasses to determine which type of Edge is created. 26104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Override this method to produce subclasses of BallLarusEdge if 26204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // necessary. Parameters source and target will have been created by 26304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // createNode and can be cast to the subclass of BallLarusNode* 26404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // returned by createNode. The destructor of BallLarusDag will call free 26504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // on each pointer created. 26604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick virtual BallLarusEdge* createEdge(BallLarusNode* source, BallLarusNode* 26704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick target, unsigned duplicateNumber); 26804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 26904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Proxy to node's constructor. Updates the DAG state. 27004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* addNode(BasicBlock* BB); 27104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 27204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Proxy to edge's constructor. Updates the DAG state. 27304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target, 27404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateNumber); 27504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 27604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickprivate: 27704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The root (i.e. entry) node for this DAG. 27804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* _root; 27904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 28004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The exit node for this DAG. 28104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* _exit; 28204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 28304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The function represented by this DAG. 28404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick Function& _function; 28504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 28604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Processes one node and its imediate edges for building the DAG. 28704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack); 28804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 28904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Process an edge in the CFG for DAG building. 29004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack, 29104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* currentNode, BasicBlock* succBB, 29204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateNumber); 29304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 29404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The weight on each edge is the increment required along any path that 29504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // contains that edge. 29604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void calculatePathNumbersFrom(BallLarusNode* node); 29704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 29804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Adds a backedge with its phony edges. Updates the DAG state. 29904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick void addBackedge(BallLarusNode* source, BallLarusNode* target, 30004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateCount); 30104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick}; 30204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} // end namespace llvm 30304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 30404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#endif 305