1218885Sdim//===- PathNumbering.cpp --------------------------------------*- C++ -*---===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// Ball-Larus path numbers uniquely identify paths through a directed acyclic 11218885Sdim// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony 12218885Sdim// edges to obtain a DAG, and thus the unique path numbers [Ball96]. 13218885Sdim// 14218885Sdim// The purpose of this analysis is to enumerate the edges in a CFG in order 15218885Sdim// to obtain paths from path numbers in a convenient manner. As described in 16218885Sdim// [Ball96] edges can be enumerated such that given a path number by following 17218885Sdim// the CFG and updating the path number, the path is obtained. 18218885Sdim// 19218885Sdim// [Ball96] 20218885Sdim// T. Ball and J. R. Larus. "Efficient Path Profiling." 21218885Sdim// International Symposium on Microarchitecture, pages 46-57, 1996. 22218885Sdim// http://portal.acm.org/citation.cfm?id=243857 23218885Sdim// 24218885Sdim//===----------------------------------------------------------------------===// 25218885Sdim#define DEBUG_TYPE "ball-larus-numbering" 26218885Sdim 27218885Sdim#include "llvm/Analysis/PathNumbering.h" 28249423Sdim#include "llvm/IR/Constants.h" 29249423Sdim#include "llvm/IR/DerivedTypes.h" 30249423Sdim#include "llvm/IR/InstrTypes.h" 31249423Sdim#include "llvm/IR/Instructions.h" 32249423Sdim#include "llvm/IR/Module.h" 33249423Sdim#include "llvm/IR/TypeBuilder.h" 34218885Sdim#include "llvm/Pass.h" 35218885Sdim#include "llvm/Support/CFG.h" 36218885Sdim#include "llvm/Support/CommandLine.h" 37218885Sdim#include "llvm/Support/Compiler.h" 38218885Sdim#include "llvm/Support/Debug.h" 39218885Sdim#include "llvm/Support/raw_ostream.h" 40218885Sdim#include <queue> 41249423Sdim#include <sstream> 42218885Sdim#include <stack> 43218885Sdim#include <string> 44218885Sdim#include <utility> 45218885Sdim 46218885Sdimusing namespace llvm; 47218885Sdim 48218885Sdim// Are we enabling early termination 49218885Sdimstatic cl::opt<bool> ProcessEarlyTermination( 50218885Sdim "path-profile-early-termination", cl::Hidden, 51218885Sdim cl::desc("In path profiling, insert extra instrumentation to account for " 52218885Sdim "unexpected function termination.")); 53218885Sdim 54218885Sdim// Returns the basic block for the BallLarusNode 55218885SdimBasicBlock* BallLarusNode::getBlock() { 56218885Sdim return(_basicBlock); 57218885Sdim} 58218885Sdim 59218885Sdim// Returns the number of paths to the exit starting at the node. 60218885Sdimunsigned BallLarusNode::getNumberPaths() { 61218885Sdim return(_numberPaths); 62218885Sdim} 63218885Sdim 64218885Sdim// Sets the number of paths to the exit starting at the node. 65218885Sdimvoid BallLarusNode::setNumberPaths(unsigned numberPaths) { 66218885Sdim _numberPaths = numberPaths; 67218885Sdim} 68218885Sdim 69218885Sdim// Gets the NodeColor used in graph algorithms. 70218885SdimBallLarusNode::NodeColor BallLarusNode::getColor() { 71218885Sdim return(_color); 72218885Sdim} 73218885Sdim 74218885Sdim// Sets the NodeColor used in graph algorithms. 75218885Sdimvoid BallLarusNode::setColor(BallLarusNode::NodeColor color) { 76218885Sdim _color = color; 77218885Sdim} 78218885Sdim 79218885Sdim// Returns an iterator over predecessor edges. Includes phony and 80218885Sdim// backedges. 81218885SdimBLEdgeIterator BallLarusNode::predBegin() { 82218885Sdim return(_predEdges.begin()); 83218885Sdim} 84218885Sdim 85218885Sdim// Returns the end sentinel for the predecessor iterator. 86218885SdimBLEdgeIterator BallLarusNode::predEnd() { 87218885Sdim return(_predEdges.end()); 88218885Sdim} 89218885Sdim 90218885Sdim// Returns the number of predecessor edges. Includes phony and 91218885Sdim// backedges. 92218885Sdimunsigned BallLarusNode::getNumberPredEdges() { 93218885Sdim return(_predEdges.size()); 94218885Sdim} 95218885Sdim 96218885Sdim// Returns an iterator over successor edges. Includes phony and 97218885Sdim// backedges. 98218885SdimBLEdgeIterator BallLarusNode::succBegin() { 99218885Sdim return(_succEdges.begin()); 100218885Sdim} 101218885Sdim 102218885Sdim// Returns the end sentinel for the successor iterator. 103218885SdimBLEdgeIterator BallLarusNode::succEnd() { 104218885Sdim return(_succEdges.end()); 105218885Sdim} 106218885Sdim 107218885Sdim// Returns the number of successor edges. Includes phony and 108218885Sdim// backedges. 109218885Sdimunsigned BallLarusNode::getNumberSuccEdges() { 110218885Sdim return(_succEdges.size()); 111218885Sdim} 112218885Sdim 113218885Sdim// Add an edge to the predecessor list. 114218885Sdimvoid BallLarusNode::addPredEdge(BallLarusEdge* edge) { 115218885Sdim _predEdges.push_back(edge); 116218885Sdim} 117218885Sdim 118218885Sdim// Remove an edge from the predecessor list. 119218885Sdimvoid BallLarusNode::removePredEdge(BallLarusEdge* edge) { 120218885Sdim removeEdge(_predEdges, edge); 121218885Sdim} 122218885Sdim 123218885Sdim// Add an edge to the successor list. 124218885Sdimvoid BallLarusNode::addSuccEdge(BallLarusEdge* edge) { 125218885Sdim _succEdges.push_back(edge); 126218885Sdim} 127218885Sdim 128218885Sdim// Remove an edge from the successor list. 129218885Sdimvoid BallLarusNode::removeSuccEdge(BallLarusEdge* edge) { 130218885Sdim removeEdge(_succEdges, edge); 131218885Sdim} 132218885Sdim 133218885Sdim// Returns the name of the BasicBlock being represented. If BasicBlock 134218885Sdim// is null then returns "<null>". If BasicBlock has no name, then 135218885Sdim// "<unnamed>" is returned. Intended for use with debug output. 136218885Sdimstd::string BallLarusNode::getName() { 137218885Sdim std::stringstream name; 138218885Sdim 139218885Sdim if(getBlock() != NULL) { 140218885Sdim if(getBlock()->hasName()) { 141218885Sdim std::string tempName(getBlock()->getName()); 142218885Sdim name << tempName.c_str() << " (" << _uid << ")"; 143218885Sdim } else 144218885Sdim name << "<unnamed> (" << _uid << ")"; 145218885Sdim } else 146218885Sdim name << "<null> (" << _uid << ")"; 147218885Sdim 148218885Sdim return name.str(); 149218885Sdim} 150218885Sdim 151218885Sdim// Removes an edge from an edgeVector. Used by removePredEdge and 152218885Sdim// removeSuccEdge. 153218885Sdimvoid BallLarusNode::removeEdge(BLEdgeVector& v, BallLarusEdge* e) { 154218885Sdim // TODO: Avoid linear scan by using a set instead 155218885Sdim for(BLEdgeIterator i = v.begin(), 156218885Sdim end = v.end(); 157218885Sdim i != end; 158218885Sdim ++i) { 159218885Sdim if((*i) == e) { 160218885Sdim v.erase(i); 161218885Sdim break; 162218885Sdim } 163218885Sdim } 164218885Sdim} 165218885Sdim 166218885Sdim// Returns the source node of this edge. 167218885SdimBallLarusNode* BallLarusEdge::getSource() const { 168218885Sdim return(_source); 169218885Sdim} 170218885Sdim 171218885Sdim// Returns the target node of this edge. 172218885SdimBallLarusNode* BallLarusEdge::getTarget() const { 173218885Sdim return(_target); 174218885Sdim} 175218885Sdim 176218885Sdim// Sets the type of the edge. 177218885SdimBallLarusEdge::EdgeType BallLarusEdge::getType() const { 178218885Sdim return _edgeType; 179218885Sdim} 180218885Sdim 181218885Sdim// Gets the type of the edge. 182218885Sdimvoid BallLarusEdge::setType(EdgeType type) { 183218885Sdim _edgeType = type; 184218885Sdim} 185218885Sdim 186218885Sdim// Returns the weight of this edge. Used to decode path numbers to sequences 187218885Sdim// of basic blocks. 188218885Sdimunsigned BallLarusEdge::getWeight() { 189218885Sdim return(_weight); 190218885Sdim} 191218885Sdim 192218885Sdim// Sets the weight of the edge. Used during path numbering. 193218885Sdimvoid BallLarusEdge::setWeight(unsigned weight) { 194218885Sdim _weight = weight; 195218885Sdim} 196218885Sdim 197218885Sdim// Gets the phony edge originating at the root. 198218885SdimBallLarusEdge* BallLarusEdge::getPhonyRoot() { 199218885Sdim return _phonyRoot; 200218885Sdim} 201218885Sdim 202218885Sdim// Sets the phony edge originating at the root. 203218885Sdimvoid BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) { 204218885Sdim _phonyRoot = phonyRoot; 205218885Sdim} 206218885Sdim 207218885Sdim// Gets the phony edge terminating at the exit. 208218885SdimBallLarusEdge* BallLarusEdge::getPhonyExit() { 209218885Sdim return _phonyExit; 210218885Sdim} 211218885Sdim 212218885Sdim// Sets the phony edge terminating at the exit. 213218885Sdimvoid BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) { 214218885Sdim _phonyExit = phonyExit; 215218885Sdim} 216218885Sdim 217218885Sdim// Gets the associated real edge if this is a phony edge. 218218885SdimBallLarusEdge* BallLarusEdge::getRealEdge() { 219218885Sdim return _realEdge; 220218885Sdim} 221218885Sdim 222218885Sdim// Sets the associated real edge if this is a phony edge. 223218885Sdimvoid BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) { 224218885Sdim _realEdge = realEdge; 225218885Sdim} 226218885Sdim 227218885Sdim// Returns the duplicate number of the edge. 228218885Sdimunsigned BallLarusEdge::getDuplicateNumber() { 229218885Sdim return(_duplicateNumber); 230218885Sdim} 231218885Sdim 232218885Sdim// Initialization that requires virtual functions which are not fully 233218885Sdim// functional in the constructor. 234218885Sdimvoid BallLarusDag::init() { 235218885Sdim BLBlockNodeMap inDag; 236218885Sdim std::stack<BallLarusNode*> dfsStack; 237218885Sdim 238218885Sdim _root = addNode(&(_function.getEntryBlock())); 239218885Sdim _exit = addNode(NULL); 240218885Sdim 241218885Sdim // start search from root 242218885Sdim dfsStack.push(getRoot()); 243218885Sdim 244218885Sdim // dfs to add each bb into the dag 245218885Sdim while(dfsStack.size()) 246218885Sdim buildNode(inDag, dfsStack); 247218885Sdim 248218885Sdim // put in the final edge 249218885Sdim addEdge(getExit(),getRoot(),0); 250218885Sdim} 251218885Sdim 252218885Sdim// Frees all memory associated with the DAG. 253218885SdimBallLarusDag::~BallLarusDag() { 254218885Sdim for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); edge != end; 255218885Sdim ++edge) 256218885Sdim delete (*edge); 257218885Sdim 258218885Sdim for(BLNodeIterator node = _nodes.begin(), end = _nodes.end(); node != end; 259218885Sdim ++node) 260218885Sdim delete (*node); 261218885Sdim} 262218885Sdim 263218885Sdim// Calculate the path numbers by assigning edge increments as prescribed 264218885Sdim// in Ball-Larus path profiling. 265218885Sdimvoid BallLarusDag::calculatePathNumbers() { 266218885Sdim BallLarusNode* node; 267218885Sdim std::queue<BallLarusNode*> bfsQueue; 268218885Sdim bfsQueue.push(getExit()); 269218885Sdim 270218885Sdim while(bfsQueue.size() > 0) { 271218885Sdim node = bfsQueue.front(); 272218885Sdim 273218885Sdim DEBUG(dbgs() << "calculatePathNumbers on " << node->getName() << "\n"); 274218885Sdim 275218885Sdim bfsQueue.pop(); 276218885Sdim unsigned prevPathNumber = node->getNumberPaths(); 277218885Sdim calculatePathNumbersFrom(node); 278218885Sdim 279218885Sdim // Check for DAG splitting 280218885Sdim if( node->getNumberPaths() > 100000000 && node != getRoot() ) { 281218885Sdim // Add new phony edge from the split-node to the DAG's exit 282218885Sdim BallLarusEdge* exitEdge = addEdge(node, getExit(), 0); 283218885Sdim exitEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); 284218885Sdim 285221345Sdim // Counters to handle the possibility of a multi-graph 286218885Sdim BasicBlock* oldTarget = 0; 287218885Sdim unsigned duplicateNumber = 0; 288218885Sdim 289218885Sdim // Iterate through each successor edge, adding phony edges 290218885Sdim for( BLEdgeIterator succ = node->succBegin(), end = node->succEnd(); 291218885Sdim succ != end; oldTarget = (*succ)->getTarget()->getBlock(), succ++ ) { 292218885Sdim 293218885Sdim if( (*succ)->getType() == BallLarusEdge::NORMAL ) { 294218885Sdim // is this edge a duplicate? 295218885Sdim if( oldTarget != (*succ)->getTarget()->getBlock() ) 296218885Sdim duplicateNumber = 0; 297218885Sdim 298218885Sdim // create the new phony edge: root -> succ 299218885Sdim BallLarusEdge* rootEdge = 300218885Sdim addEdge(getRoot(), (*succ)->getTarget(), duplicateNumber++); 301218885Sdim rootEdge->setType(BallLarusEdge::SPLITEDGE_PHONY); 302218885Sdim rootEdge->setRealEdge(*succ); 303218885Sdim 304218885Sdim // split on this edge and reference it's exit/root phony edges 305218885Sdim (*succ)->setType(BallLarusEdge::SPLITEDGE); 306218885Sdim (*succ)->setPhonyRoot(rootEdge); 307218885Sdim (*succ)->setPhonyExit(exitEdge); 308218885Sdim (*succ)->setWeight(0); 309218885Sdim } 310218885Sdim } 311218885Sdim 312218885Sdim calculatePathNumbersFrom(node); 313218885Sdim } 314218885Sdim 315218885Sdim DEBUG(dbgs() << "prev, new number paths " << prevPathNumber << ", " 316218885Sdim << node->getNumberPaths() << ".\n"); 317218885Sdim 318218885Sdim if(prevPathNumber == 0 && node->getNumberPaths() != 0) { 319218885Sdim DEBUG(dbgs() << "node ready : " << node->getName() << "\n"); 320218885Sdim for(BLEdgeIterator pred = node->predBegin(), end = node->predEnd(); 321218885Sdim pred != end; pred++) { 322218885Sdim if( (*pred)->getType() == BallLarusEdge::BACKEDGE || 323218885Sdim (*pred)->getType() == BallLarusEdge::SPLITEDGE ) 324218885Sdim continue; 325218885Sdim 326218885Sdim BallLarusNode* nextNode = (*pred)->getSource(); 327218885Sdim // not yet visited? 328218885Sdim if(nextNode->getNumberPaths() == 0) 329218885Sdim bfsQueue.push(nextNode); 330218885Sdim } 331218885Sdim } 332218885Sdim } 333218885Sdim 334218885Sdim DEBUG(dbgs() << "\tNumber of paths: " << getRoot()->getNumberPaths() << "\n"); 335218885Sdim} 336218885Sdim 337218885Sdim// Returns the number of paths for the Dag. 338218885Sdimunsigned BallLarusDag::getNumberOfPaths() { 339218885Sdim return(getRoot()->getNumberPaths()); 340218885Sdim} 341218885Sdim 342218885Sdim// Returns the root (i.e. entry) node for the DAG. 343218885SdimBallLarusNode* BallLarusDag::getRoot() { 344218885Sdim return _root; 345218885Sdim} 346218885Sdim 347218885Sdim// Returns the exit node for the DAG. 348218885SdimBallLarusNode* BallLarusDag::getExit() { 349218885Sdim return _exit; 350218885Sdim} 351218885Sdim 352218885Sdim// Returns the function for the DAG. 353218885SdimFunction& BallLarusDag::getFunction() { 354218885Sdim return(_function); 355218885Sdim} 356218885Sdim 357218885Sdim// Clears the node colors. 358218885Sdimvoid BallLarusDag::clearColors(BallLarusNode::NodeColor color) { 359218885Sdim for (BLNodeIterator nodeIt = _nodes.begin(); nodeIt != _nodes.end(); nodeIt++) 360218885Sdim (*nodeIt)->setColor(color); 361218885Sdim} 362218885Sdim 363218885Sdim// Processes one node and its imediate edges for building the DAG. 364218885Sdimvoid BallLarusDag::buildNode(BLBlockNodeMap& inDag, BLNodeStack& dfsStack) { 365218885Sdim BallLarusNode* currentNode = dfsStack.top(); 366218885Sdim BasicBlock* currentBlock = currentNode->getBlock(); 367218885Sdim 368218885Sdim if(currentNode->getColor() != BallLarusNode::WHITE) { 369218885Sdim // we have already visited this node 370218885Sdim dfsStack.pop(); 371218885Sdim currentNode->setColor(BallLarusNode::BLACK); 372218885Sdim } else { 373218885Sdim // are there any external procedure calls? 374218885Sdim if( ProcessEarlyTermination ) { 375218885Sdim for( BasicBlock::iterator bbCurrent = currentNode->getBlock()->begin(), 376218885Sdim bbEnd = currentNode->getBlock()->end(); bbCurrent != bbEnd; 377218885Sdim bbCurrent++ ) { 378218885Sdim Instruction& instr = *bbCurrent; 379218885Sdim if( instr.getOpcode() == Instruction::Call ) { 380218885Sdim BallLarusEdge* callEdge = addEdge(currentNode, getExit(), 0); 381218885Sdim callEdge->setType(BallLarusEdge::CALLEDGE_PHONY); 382218885Sdim break; 383218885Sdim } 384218885Sdim } 385218885Sdim } 386218885Sdim 387218885Sdim TerminatorInst* terminator = currentNode->getBlock()->getTerminator(); 388234353Sdim if(isa<ReturnInst>(terminator) || isa<UnreachableInst>(terminator) || 389234353Sdim isa<ResumeInst>(terminator)) 390218885Sdim addEdge(currentNode, getExit(),0); 391218885Sdim 392218885Sdim currentNode->setColor(BallLarusNode::GRAY); 393218885Sdim inDag[currentBlock] = currentNode; 394218885Sdim 395218885Sdim BasicBlock* oldSuccessor = 0; 396218885Sdim unsigned duplicateNumber = 0; 397218885Sdim 398218885Sdim // iterate through this node's successors 399218885Sdim for(succ_iterator successor = succ_begin(currentBlock), 400218885Sdim succEnd = succ_end(currentBlock); successor != succEnd; 401218885Sdim oldSuccessor = *successor, ++successor ) { 402218885Sdim BasicBlock* succBB = *successor; 403218885Sdim 404218885Sdim // is this edge a duplicate? 405218885Sdim if (oldSuccessor == succBB) 406218885Sdim duplicateNumber++; 407218885Sdim else 408218885Sdim duplicateNumber = 0; 409218885Sdim 410218885Sdim buildEdge(inDag, dfsStack, currentNode, succBB, duplicateNumber); 411218885Sdim } 412218885Sdim } 413218885Sdim} 414218885Sdim 415218885Sdim// Process an edge in the CFG for DAG building. 416218885Sdimvoid BallLarusDag::buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& 417218885Sdim dfsStack, BallLarusNode* currentNode, 418218885Sdim BasicBlock* succBB, unsigned duplicateCount) { 419218885Sdim BallLarusNode* succNode = inDag[succBB]; 420218885Sdim 421218885Sdim if(succNode && succNode->getColor() == BallLarusNode::BLACK) { 422218885Sdim // visited node and forward edge 423218885Sdim addEdge(currentNode, succNode, duplicateCount); 424218885Sdim } else if(succNode && succNode->getColor() == BallLarusNode::GRAY) { 425218885Sdim // visited node and back edge 426218885Sdim DEBUG(dbgs() << "Backedge detected.\n"); 427218885Sdim addBackedge(currentNode, succNode, duplicateCount); 428218885Sdim } else { 429218885Sdim BallLarusNode* childNode; 430218885Sdim // not visited node and forward edge 431218885Sdim if(succNode) // an unvisited node that is child of a gray node 432218885Sdim childNode = succNode; 433218885Sdim else { // an unvisited node that is a child of a an unvisted node 434218885Sdim childNode = addNode(succBB); 435218885Sdim inDag[succBB] = childNode; 436218885Sdim } 437218885Sdim addEdge(currentNode, childNode, duplicateCount); 438218885Sdim dfsStack.push(childNode); 439218885Sdim } 440218885Sdim} 441218885Sdim 442218885Sdim// The weight on each edge is the increment required along any path that 443218885Sdim// contains that edge. 444218885Sdimvoid BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) { 445218885Sdim if(node == getExit()) 446218885Sdim // The Exit node must be base case 447218885Sdim node->setNumberPaths(1); 448218885Sdim else { 449218885Sdim unsigned sumPaths = 0; 450218885Sdim BallLarusNode* succNode; 451218885Sdim 452218885Sdim for(BLEdgeIterator succ = node->succBegin(), end = node->succEnd(); 453218885Sdim succ != end; succ++) { 454218885Sdim if( (*succ)->getType() == BallLarusEdge::BACKEDGE || 455218885Sdim (*succ)->getType() == BallLarusEdge::SPLITEDGE ) 456218885Sdim continue; 457218885Sdim 458218885Sdim (*succ)->setWeight(sumPaths); 459218885Sdim succNode = (*succ)->getTarget(); 460218885Sdim 461218885Sdim if( !succNode->getNumberPaths() ) 462218885Sdim return; 463218885Sdim sumPaths += succNode->getNumberPaths(); 464218885Sdim } 465218885Sdim 466218885Sdim node->setNumberPaths(sumPaths); 467218885Sdim } 468218885Sdim} 469218885Sdim 470218885Sdim// Allows subclasses to determine which type of Node is created. 471218885Sdim// Override this method to produce subclasses of BallLarusNode if 472218885Sdim// necessary. The destructor of BallLarusDag will call free on each 473218885Sdim// pointer created. 474218885SdimBallLarusNode* BallLarusDag::createNode(BasicBlock* BB) { 475218885Sdim return( new BallLarusNode(BB) ); 476218885Sdim} 477218885Sdim 478218885Sdim// Allows subclasses to determine which type of Edge is created. 479218885Sdim// Override this method to produce subclasses of BallLarusEdge if 480218885Sdim// necessary. The destructor of BallLarusDag will call free on each 481218885Sdim// pointer created. 482218885SdimBallLarusEdge* BallLarusDag::createEdge(BallLarusNode* source, 483218885Sdim BallLarusNode* target, 484218885Sdim unsigned duplicateCount) { 485218885Sdim return( new BallLarusEdge(source, target, duplicateCount) ); 486218885Sdim} 487218885Sdim 488218885Sdim// Proxy to node's constructor. Updates the DAG state. 489218885SdimBallLarusNode* BallLarusDag::addNode(BasicBlock* BB) { 490218885Sdim BallLarusNode* newNode = createNode(BB); 491218885Sdim _nodes.push_back(newNode); 492218885Sdim return( newNode ); 493218885Sdim} 494218885Sdim 495218885Sdim// Proxy to edge's constructor. Updates the DAG state. 496218885SdimBallLarusEdge* BallLarusDag::addEdge(BallLarusNode* source, 497218885Sdim BallLarusNode* target, 498218885Sdim unsigned duplicateCount) { 499218885Sdim BallLarusEdge* newEdge = createEdge(source, target, duplicateCount); 500218885Sdim _edges.push_back(newEdge); 501218885Sdim source->addSuccEdge(newEdge); 502218885Sdim target->addPredEdge(newEdge); 503218885Sdim return(newEdge); 504218885Sdim} 505218885Sdim 506218885Sdim// Adds a backedge with its phony edges. Updates the DAG state. 507218885Sdimvoid BallLarusDag::addBackedge(BallLarusNode* source, BallLarusNode* target, 508218885Sdim unsigned duplicateCount) { 509218885Sdim BallLarusEdge* childEdge = addEdge(source, target, duplicateCount); 510218885Sdim childEdge->setType(BallLarusEdge::BACKEDGE); 511218885Sdim 512218885Sdim childEdge->setPhonyRoot(addEdge(getRoot(), target,0)); 513218885Sdim childEdge->setPhonyExit(addEdge(source, getExit(),0)); 514218885Sdim 515218885Sdim childEdge->getPhonyRoot()->setRealEdge(childEdge); 516218885Sdim childEdge->getPhonyRoot()->setType(BallLarusEdge::BACKEDGE_PHONY); 517218885Sdim 518218885Sdim childEdge->getPhonyExit()->setRealEdge(childEdge); 519218885Sdim childEdge->getPhonyExit()->setType(BallLarusEdge::BACKEDGE_PHONY); 520218885Sdim _backEdges.push_back(childEdge); 521218885Sdim} 522