104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick//===- PathNumbering.cpp --------------------------------------*- 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#define DEBUG_TYPE "ball-larus-numbering" 2604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 2704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Analysis/PathNumbering.h" 2804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Constants.h" 2904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/DerivedTypes.h" 3004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/InstrTypes.h" 3104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Instructions.h" 3204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Module.h" 3304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Pass.h" 3404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/CFG.h" 3504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/CommandLine.h" 3604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/Compiler.h" 3704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/Debug.h" 3804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/TypeBuilder.h" 3904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include "llvm/Support/raw_ostream.h" 4004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <queue> 4204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <stack> 4304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <string> 4404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <utility> 4504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick#include <sstream> 4604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickusing namespace llvm; 4804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 4904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Are we enabling early termination 5004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickstatic cl::opt<bool> ProcessEarlyTermination( 5104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick "path-profile-early-termination", cl::Hidden, 5204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick cl::desc("In path profiling, insert extra instrumentation to account for " 5304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick "unexpected function termination.")); 5404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 5504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the basic block for the BallLarusNode 5604317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBasicBlock* BallLarusNode::getBlock() { 5704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_basicBlock); 5804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 5904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 6004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the number of paths to the exit starting at the node. 6104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickunsigned BallLarusNode::getNumberPaths() { 6204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_numberPaths); 6304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 6404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 6504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the number of paths to the exit starting at the node. 6604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::setNumberPaths(unsigned numberPaths) { 6704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _numberPaths = numberPaths; 6804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 6904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 7004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Gets the NodeColor used in graph algorithms. 7104317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode::NodeColor BallLarusNode::getColor() { 7204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_color); 7304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 7404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 7504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the NodeColor used in graph algorithms. 7604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::setColor(BallLarusNode::NodeColor color) { 7704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _color = color; 7804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 7904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns an iterator over predecessor edges. Includes phony and 8104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// backedges. 8204317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBLEdgeIterator BallLarusNode::predBegin() { 8304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_predEdges.begin()); 8404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 8504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 8604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the end sentinel for the predecessor iterator. 8704317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBLEdgeIterator BallLarusNode::predEnd() { 8804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_predEdges.end()); 8904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 9004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the number of predecessor edges. Includes phony and 9204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// backedges. 9304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickunsigned BallLarusNode::getNumberPredEdges() { 9404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_predEdges.size()); 9504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 9604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 9704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns an iterator over successor edges. Includes phony and 9804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// backedges. 9904317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBLEdgeIterator BallLarusNode::succBegin() { 10004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_succEdges.begin()); 10104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 10204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the end sentinel for the successor iterator. 10404317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBLEdgeIterator BallLarusNode::succEnd() { 10504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_succEdges.end()); 10604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 10704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 10804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the number of successor edges. Includes phony and 10904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// backedges. 11004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickunsigned BallLarusNode::getNumberSuccEdges() { 11104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_succEdges.size()); 11204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 11304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Add an edge to the predecessor list. 11504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::addPredEdge(BallLarusEdge* edge) { 11604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _predEdges.push_back(edge); 11704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 11804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 11904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Remove an edge from the predecessor list. 12004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::removePredEdge(BallLarusEdge* edge) { 12104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick removeEdge(_predEdges, edge); 12204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 12304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 12404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Add an edge to the successor list. 12504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::addSuccEdge(BallLarusEdge* edge) { 12604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _succEdges.push_back(edge); 12704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 12804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 12904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Remove an edge from the successor list. 13004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::removeSuccEdge(BallLarusEdge* edge) { 13104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick removeEdge(_succEdges, edge); 13204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 13304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 13404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the name of the BasicBlock being represented. If BasicBlock 13504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// is null then returns "<null>". If BasicBlock has no name, then 13604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// "<unnamed>" is returned. Intended for use with debug output. 13704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickstd::string BallLarusNode::getName() { 13804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::stringstream name; 13904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 14004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(getBlock() != NULL) { 14104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(getBlock()->hasName()) { 14204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::string tempName(getBlock()->getName()); 14304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick name << tempName.c_str() << " (" << _uid << ")"; 14404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else 14504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick name << "<unnamed> (" << _uid << ")"; 14604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else 14704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick name << "<null> (" << _uid << ")"; 14804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 14904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return name.str(); 15004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 15104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 15204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Removes an edge from an edgeVector. Used by removePredEdge and 15304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// removeSuccEdge. 15404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusNode::removeEdge(BLEdgeVector& v, BallLarusEdge* e) { 15504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // TODO: Avoid linear scan by using a set instead 15604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for(BLEdgeIterator i = v.begin(), 15704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick end = v.end(); 15804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick i != end; 15904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick ++i) { 16004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if((*i) == e) { 16104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick v.erase(i); 16204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick break; 16304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 16404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 16504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 16604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 16704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the source node of this edge. 16804317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode* BallLarusEdge::getSource() const { 16904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_source); 17004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 17104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the target node of this edge. 17304317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode* BallLarusEdge::getTarget() const { 17404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_target); 17504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 17604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 17704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the type of the edge. 17804317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusEdge::EdgeType BallLarusEdge::getType() const { 17904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return _edgeType; 18004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 18104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Gets the type of the edge. 18304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusEdge::setType(EdgeType type) { 18404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _edgeType = type; 18504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 18604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 18704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the weight of this edge. Used to decode path numbers to sequences 18804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// of basic blocks. 18904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickunsigned BallLarusEdge::getWeight() { 19004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_weight); 19104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 19204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 19304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the weight of the edge. Used during path numbering. 19404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusEdge::setWeight(unsigned weight) { 19504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _weight = weight; 19604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 19704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 19804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Gets the phony edge originating at the root. 19904317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusEdge* BallLarusEdge::getPhonyRoot() { 20004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return _phonyRoot; 20104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 20204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 20304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the phony edge originating at the root. 20404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) { 20504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _phonyRoot = phonyRoot; 20604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 20704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 20804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Gets the phony edge terminating at the exit. 20904317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusEdge* BallLarusEdge::getPhonyExit() { 21004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return _phonyExit; 21104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 21204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 21304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the phony edge terminating at the exit. 21404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) { 21504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _phonyExit = phonyExit; 21604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 21704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 21804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Gets the associated real edge if this is a phony edge. 21904317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusEdge* BallLarusEdge::getRealEdge() { 22004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return _realEdge; 22104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 22204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 22304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Sets the associated real edge if this is a phony edge. 22404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) { 22504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _realEdge = realEdge; 22604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 22704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 22804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the duplicate number of the edge. 22904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickunsigned BallLarusEdge::getDuplicateNumber() { 23004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_duplicateNumber); 23104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 23204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 23304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Initialization that requires virtual functions which are not fully 23404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// functional in the constructor. 23504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::init() { 23604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BLBlockNodeMap inDag; 23704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::stack<BallLarusNode*> dfsStack; 23804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 23904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _root = addNode(&(_function.getEntryBlock())); 24004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _exit = addNode(NULL); 24104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 24204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // start search from root 24304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick dfsStack.push(getRoot()); 24404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 24504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // dfs to add each bb into the dag 24604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick while(dfsStack.size()) 24704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick buildNode(inDag, dfsStack); 24804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 24904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // put in the final edge 25004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick addEdge(getExit(),getRoot(),0); 25104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 25204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 25304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Frees all memory associated with the DAG. 25404317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusDag::~BallLarusDag() { 25504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); edge != end; 25604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick ++edge) 25704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick delete (*edge); 25804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 25904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for(BLNodeIterator node = _nodes.begin(), end = _nodes.end(); node != end; 26004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick ++node) 26104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick delete (*node); 26204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 26304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 26404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Calculate the path numbers by assigning edge increments as prescribed 26504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// in Ball-Larus path profiling. 26604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::calculatePathNumbers() { 26704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* node; 26804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick std::queue<BallLarusNode*> bfsQueue; 26904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick bfsQueue.push(getExit()); 27004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 27104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick while(bfsQueue.size() > 0) { 27204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick node = bfsQueue.front(); 27304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 27404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << "calculatePathNumbers on " << node->getName() << "\n"); 27504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 27604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick bfsQueue.pop(); 27704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned prevPathNumber = node->getNumberPaths(); 27804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick calculatePathNumbersFrom(node); 27904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 28004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Check for DAG splitting 28104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( node->getNumberPaths() > 100000000 && node != getRoot() ) { 28204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Add new phony edge from the split-node to the DAG's exit 28304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* exitEdge = addEdge(node, getExit(), 0); 28404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick exitEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); 28504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 2867a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Counters to handle the possibility of a multi-graph 28704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* oldTarget = 0; 28804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateNumber = 0; 28904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 29004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // Iterate through each successor edge, adding phony edges 29104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for( BLEdgeIterator succ = node->succBegin(), end = node->succEnd(); 29204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick succ != end; oldTarget = (*succ)->getTarget()->getBlock(), succ++ ) { 29304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 29404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( (*succ)->getType() == BallLarusEdge::NORMAL ) { 29504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // is this edge a duplicate? 29604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( oldTarget != (*succ)->getTarget()->getBlock() ) 29704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick duplicateNumber = 0; 29804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 29904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // create the new phony edge: root -> succ 30004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* rootEdge = 30104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick addEdge(getRoot(), (*succ)->getTarget(), duplicateNumber++); 30204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick rootEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); 30304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick rootEdge->setRealEdge(*succ); 30404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 30504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // split on this edge and reference it's exit/root phony edges 30604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*succ)->setType(BallLarusEdge::SPLITEDGE); 30704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*succ)->setPhonyRoot(rootEdge); 30804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*succ)->setPhonyExit(exitEdge); 30904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*succ)->setWeight(0); 31004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 31104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 31204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 31304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick calculatePathNumbersFrom(node); 31404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 31504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 31604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << "prev, new number paths " << prevPathNumber << ", " 31704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick << node->getNumberPaths() << ".\n"); 31804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 31904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(prevPathNumber == 0 && node->getNumberPaths() != 0) { 32004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << "node ready : " << node->getName() << "\n"); 32104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for(BLEdgeIterator pred = node->predBegin(), end = node->predEnd(); 32204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick pred != end; pred++) { 32304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( (*pred)->getType() == BallLarusEdge::BACKEDGE || 32404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*pred)->getType() == BallLarusEdge::SPLITEDGE ) 32504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick continue; 32604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 32704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* nextNode = (*pred)->getSource(); 32804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // not yet visited? 32904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(nextNode->getNumberPaths() == 0) 33004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick bfsQueue.push(nextNode); 33104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 33204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 33304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 33404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 33504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << "\tNumber of paths: " << getRoot()->getNumberPaths() << "\n"); 33604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 33704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 33804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the number of paths for the Dag. 33904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickunsigned BallLarusDag::getNumberOfPaths() { 34004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(getRoot()->getNumberPaths()); 34104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 34204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 34304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the root (i.e. entry) node for the DAG. 34404317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode* BallLarusDag::getRoot() { 34504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return _root; 34604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 34704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 34804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the exit node for the DAG. 34904317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode* BallLarusDag::getExit() { 35004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return _exit; 35104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 35204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 35304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Returns the function for the DAG. 35404317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickFunction& BallLarusDag::getFunction() { 35504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(_function); 35604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 35704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 35804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Clears the node colors. 35904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::clearColors(BallLarusNode::NodeColor color) { 36004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for (BLNodeIterator nodeIt = _nodes.begin(); nodeIt != _nodes.end(); nodeIt++) 36104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*nodeIt)->setColor(color); 36204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 36304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 36404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Processes one node and its imediate edges for building the DAG. 36504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::buildNode(BLBlockNodeMap& inDag, BLNodeStack& dfsStack) { 36604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* currentNode = dfsStack.top(); 36704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* currentBlock = currentNode->getBlock(); 36804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 36904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(currentNode->getColor() != BallLarusNode::WHITE) { 37004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // we have already visited this node 37104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick dfsStack.pop(); 37204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick currentNode->setColor(BallLarusNode::BLACK); 37304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else { 37404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // are there any external procedure calls? 37504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( ProcessEarlyTermination ) { 37604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for( BasicBlock::iterator bbCurrent = currentNode->getBlock()->begin(), 37704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick bbEnd = currentNode->getBlock()->end(); bbCurrent != bbEnd; 37804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick bbCurrent++ ) { 37904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick Instruction& instr = *bbCurrent; 38004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( instr.getOpcode() == Instruction::Call ) { 38104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* callEdge = addEdge(currentNode, getExit(), 0); 38204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick callEdge->setType(BallLarusEdge::CALLEDGE_PHONY); 38304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick break; 38404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 38504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 38604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 38704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 38804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick TerminatorInst* terminator = currentNode->getBlock()->getTerminator(); 38904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(isa<ReturnInst>(terminator) || isa<UnreachableInst>(terminator) 390d0c0d444592a0fea209ea99ebcd1be274eee6692Bill Wendling || isa<ResumeInst>(terminator) || isa<UnwindInst>(terminator)) 39104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick addEdge(currentNode, getExit(),0); 39204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 39304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick currentNode->setColor(BallLarusNode::GRAY); 39404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick inDag[currentBlock] = currentNode; 39504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 39604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* oldSuccessor = 0; 39704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateNumber = 0; 39804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 39904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // iterate through this node's successors 40004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for(succ_iterator successor = succ_begin(currentBlock), 40104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick succEnd = succ_end(currentBlock); successor != succEnd; 40204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick oldSuccessor = *successor, ++successor ) { 40304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* succBB = *successor; 40404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 40504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // is this edge a duplicate? 40604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if (oldSuccessor == succBB) 40704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick duplicateNumber++; 40804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick else 40904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick duplicateNumber = 0; 41004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 41104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick buildEdge(inDag, dfsStack, currentNode, succBB, duplicateNumber); 41204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 41304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 41404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 41504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 41604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Process an edge in the CFG for DAG building. 41704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& 41804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick dfsStack, BallLarusNode* currentNode, 41904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BasicBlock* succBB, unsigned duplicateCount) { 42004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* succNode = inDag[succBB]; 42104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 42204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(succNode && succNode->getColor() == BallLarusNode::BLACK) { 42304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // visited node and forward edge 42404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick addEdge(currentNode, succNode, duplicateCount); 42504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else if(succNode && succNode->getColor() == BallLarusNode::GRAY) { 42604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // visited node and back edge 42704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick DEBUG(dbgs() << "Backedge detected.\n"); 42804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick addBackedge(currentNode, succNode, duplicateCount); 42904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } else { 43004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* childNode; 43104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // not visited node and forward edge 43204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(succNode) // an unvisited node that is child of a gray node 43304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childNode = succNode; 43404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick else { // an unvisited node that is a child of a an unvisted node 43504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childNode = addNode(succBB); 43604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick inDag[succBB] = childNode; 43704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 43804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick addEdge(currentNode, childNode, duplicateCount); 43904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick dfsStack.push(childNode); 44004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 44104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 44204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 44304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// The weight on each edge is the increment required along any path that 44404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// contains that edge. 44504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) { 44604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if(node == getExit()) 44704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick // The Exit node must be base case 44804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick node->setNumberPaths(1); 44904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick else { 45004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned sumPaths = 0; 45104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* succNode; 45204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 45304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick for(BLEdgeIterator succ = node->succBegin(), end = node->succEnd(); 45404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick succ != end; succ++) { 45504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( (*succ)->getType() == BallLarusEdge::BACKEDGE || 45604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*succ)->getType() == BallLarusEdge::SPLITEDGE ) 45704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick continue; 45804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 45904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick (*succ)->setWeight(sumPaths); 46004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick succNode = (*succ)->getTarget(); 46104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 46204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick if( !succNode->getNumberPaths() ) 46304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return; 46404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick sumPaths += succNode->getNumberPaths(); 46504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 46604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 46704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick node->setNumberPaths(sumPaths); 46804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick } 46904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 47004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 47104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Allows subclasses to determine which type of Node is created. 47204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Override this method to produce subclasses of BallLarusNode if 47304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// necessary. The destructor of BallLarusDag will call free on each 47404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// pointer created. 47504317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode* BallLarusDag::createNode(BasicBlock* BB) { 47604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return( new BallLarusNode(BB) ); 47704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 47804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 47904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Allows subclasses to determine which type of Edge is created. 48004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Override this method to produce subclasses of BallLarusEdge if 48104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// necessary. The destructor of BallLarusDag will call free on each 48204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// pointer created. 48304317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusEdge* BallLarusDag::createEdge(BallLarusNode* source, 48404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* target, 48504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateCount) { 48604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return( new BallLarusEdge(source, target, duplicateCount) ); 48704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 48804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 48904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Proxy to node's constructor. Updates the DAG state. 49004317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusNode* BallLarusDag::addNode(BasicBlock* BB) { 49104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* newNode = createNode(BB); 49204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _nodes.push_back(newNode); 49304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return( newNode ); 49404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 49504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 49604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Proxy to edge's constructor. Updates the DAG state. 49704317cc618aeae28910916469e074d8ce0fcaa03Andrew TrickBallLarusEdge* BallLarusDag::addEdge(BallLarusNode* source, 49804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusNode* target, 49904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateCount) { 50004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* newEdge = createEdge(source, target, duplicateCount); 50104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _edges.push_back(newEdge); 50204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick source->addSuccEdge(newEdge); 50304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick target->addPredEdge(newEdge); 50404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick return(newEdge); 50504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 50604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 50704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick// Adds a backedge with its phony edges. Updates the DAG state. 50804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trickvoid BallLarusDag::addBackedge(BallLarusNode* source, BallLarusNode* target, 50904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick unsigned duplicateCount) { 51004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick BallLarusEdge* childEdge = addEdge(source, target, duplicateCount); 51104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->setType(BallLarusEdge::BACKEDGE); 51204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 51304317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->setPhonyRoot(addEdge(getRoot(), target,0)); 51404317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->setPhonyExit(addEdge(source, getExit(),0)); 51504317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 51604317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->getPhonyRoot()->setRealEdge(childEdge); 51704317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->getPhonyRoot()->setType(BallLarusEdge::BACKEDGE_PHONY); 51804317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick 51904317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->getPhonyExit()->setRealEdge(childEdge); 52004317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick childEdge->getPhonyExit()->setType(BallLarusEdge::BACKEDGE_PHONY); 52104317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick _backEdges.push_back(childEdge); 52204317cc618aeae28910916469e074d8ce0fcaa03Andrew Trick} 523