155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar//===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===// 255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// 355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// The LLVM Compiler Infrastructure 455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// 555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// This file is distributed under the University of Illinois Open Source 655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// License. See LICENSE.TXT for details. 755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// 855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar//===----------------------------------------------------------------------===// 955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// 1055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// This file implements a concrete implementation of profiling information that 1155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// estimates the profiling information in a very crude and unimaginative way. 1255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// 1355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar//===----------------------------------------------------------------------===// 1455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#define DEBUG_TYPE "profile-estimator" 1555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Pass.h" 1655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Analysis/Passes.h" 1755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Analysis/ProfileInfo.h" 1855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Analysis/LoopInfo.h" 1955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Support/CommandLine.h" 2055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Support/Debug.h" 2155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar#include "llvm/Support/raw_ostream.h" 22ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter#include "llvm/Support/Format.h" 2355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarusing namespace llvm; 2455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 2555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarstatic cl::opt<double> 26ff271e13539a43e804cab4457821a46a8bddc2ecAndreas NeustifterLoopWeight( 2755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar "profile-estimator-loop-weight", cl::init(10), 2855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar cl::value_desc("loop-weight"), 2955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar cl::desc("Number of loop executions used for profile-estimator") 3055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar); 3155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 3255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarnamespace { 336726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class ProfileEstimatorPass : public FunctionPass, public ProfileInfo { 3455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar double ExecCount; 3555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar LoopInfo *LI; 368a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter std::set<BasicBlock*> BBToVisit; 3755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar std::map<Loop*,double> LoopExitWeights; 381640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter std::map<Edge,double> MinimalWeight; 3955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar public: 4055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar static char ID; // Class identification, replacement for typeinfo 4155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar explicit ProfileEstimatorPass(const double execcount = 0) 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : FunctionPass(ID), ExecCount(execcount) { 43081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeProfileEstimatorPassPass(*PassRegistry::getPassRegistry()); 44ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter if (execcount == 0) ExecCount = LoopWeight; 4555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 4655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 4755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar virtual void getAnalysisUsage(AnalysisUsage &AU) const { 4855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar AU.setPreservesAll(); 4955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar AU.addRequired<LoopInfo>(); 5055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 5155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 5255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar virtual const char *getPassName() const { 5355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar return "Profiling information estimator"; 5455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 5555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 5655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar /// run - Estimate the profile information from the specified file. 5755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar virtual bool runOnFunction(Function &F); 5855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 591bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 601bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// an analysis interface through multiple inheritance. If needed, it 611bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// should override this to adjust the this pointer as needed for the 621bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner /// specified pass info. 6390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 6490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &ProfileInfo::ID) 651bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return (ProfileInfo*)this; 661bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner return this; 671bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner } 681bc76d48d476446f226f06f0aced7efb268f2536Chris Lattner 698a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter virtual void recurseBasicBlock(BasicBlock *BB); 70ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter 71ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter void inline printEdgeWeight(Edge); 7255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar }; 7355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar} // End of anonymous namespace 7455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 7555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarchar ProfileEstimatorPass::ID = 0; 762ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_PASS_BEGIN(ProfileEstimatorPass, ProfileInfo, "profile-estimator", 772ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Estimate profiling information", false, true, false) 782ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 792ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_PASS_END(ProfileEstimatorPass, ProfileInfo, "profile-estimator", 80ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Estimate profiling information", false, true, false) 8155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 8255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarnamespace llvm { 8390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson char &ProfileEstimatorPassID = ProfileEstimatorPass::ID; 8455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 8555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar FunctionPass *createProfileEstimatorPass() { 8655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar return new ProfileEstimatorPass(); 8755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 8855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 89ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter /// createProfileEstimatorPass - This function returns a Pass that estimates 90ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter /// profiling information using the given loop execution count. 9155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar Pass *createProfileEstimatorPass(const unsigned execcount) { 9255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar return new ProfileEstimatorPass(execcount); 9355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 9455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar} 9555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 9655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarstatic double ignoreMissing(double w) { 9755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (w == ProfileInfo::MissingValue) return 0; 9855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar return w; 9955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar} 10055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 1018a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifterstatic void inline printEdgeError(ProfileInfo::Edge e, const char *M) { 102244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n"); 103ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter} 10455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 105ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustiftervoid inline ProfileEstimatorPass::printEdgeWeight(Edge E) { 106244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "-- Weight of Edge " << E << ":" 1071640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter << format("%20.20g", getEdgeWeight(E)) << "\n"); 108ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter} 10955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 11055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// recurseBasicBlock() - This calculates the ProfileInfo estimation for a 11155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar// single block and then recurses into the successors. 1128a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// The algorithm preserves the flow condition, meaning that the sum of the 1138a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// weight of the incoming edges must be equal the block weight which must in 1148a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// turn be equal to the sume of the weights of the outgoing edges. 1158a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// Since the flow of an block is deterimined from the current state of the 1168a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// flow, once an edge has a flow assigned this flow is never changed again, 1178a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// otherwise it would be possible to violate the flow condition in another 1188a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter// block. 1198a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustiftervoid ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) { 12055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 121ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter // Break the recursion if this BasicBlock was already visited. 1228a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter if (BBToVisit.find(BB) == BBToVisit.end()) return; 12355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 1248a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Read the LoopInfo for this block. 12555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar bool BBisHeader = LI->isLoopHeader(BB); 12655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar Loop* BBLoop = LI->getLoopFor(BB); 12755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 1288a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // To get the block weight, read all incoming edges. 12955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar double BBWeight = 0; 13055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar std::set<BasicBlock*> ProcessedPreds; 13155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); 13255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar bbi != bbe; ++bbi ) { 1338a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // If this block was not considered already, add weight. 1340c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter Edge edge = getEdge(*bbi,BB); 1350c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter double w = getEdgeWeight(edge); 13655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (ProcessedPreds.insert(*bbi).second) { 1370c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter BBWeight += ignoreMissing(w); 13855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 1398a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // If this block is a loop header and the predecessor is contained in this 1408a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // loop, thus the edge is a backedge, continue and do not check if the 1418a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // value is valid. 1420c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter if (BBisHeader && BBLoop->contains(*bbi)) { 1437a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner printEdgeError(edge, "but is backedge, continuing"); 14455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar continue; 14555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 1468a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // If the edges value is missing (and this is no loop header, and this is 1478a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // no backedge) return, this block is currently non estimatable. 1480c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter if (w == MissingValue) { 1498a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter printEdgeError(edge, "returning"); 1508a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter return; 15155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 15255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 15355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (getExecutionCount(BB) != MissingValue) { 15455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar BBWeight = getExecutionCount(BB); 15555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 15655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 157ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter // Fetch all necessary information for current block. 15855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar SmallVector<Edge, 8> ExitEdges; 15955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar SmallVector<Edge, 8> Edges; 16055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (BBLoop) { 16155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar BBLoop->getExitEdges(ExitEdges); 16255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 16355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 1648a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // If this is a loop header, consider the following: 1658a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Exactly the flow that is entering this block, must exit this block too. So 1668a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // do the following: 1678a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // *) get all the exit edges, read the flow that is already leaving this 1688a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // loop, remember the edges that do not have any flow on them right now. 1698a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // (The edges that have already flow on them are most likely exiting edges of 1708a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // other loops, do not touch those flows because the previously caclulated 1718a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // loopheaders would not be exact anymore.) 1728a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // *) In case there is not a single exiting edge left, create one at the loop 1738a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // latch to prevent the flow from building up in the loop. 1748a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // *) Take the flow that is not leaving the loop already and distribute it on 1758a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // the remaining exiting edges. 1768a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // (This ensures that all flow that enters the loop also leaves it.) 1778a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // *) Increase the flow into the loop by increasing the weight of this block. 1788a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // There is at least one incoming backedge that will bring us this flow later 1798a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // on. (So that the flow condition in this node is valid again.) 18055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (BBisHeader) { 18155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar double incoming = BBWeight; 182ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter // Subtract the flow leaving the loop. 1830c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter std::set<Edge> ProcessedExits; 18455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(), 18555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar ee = ExitEdges.end(); ei != ee; ++ei) { 1860c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter if (ProcessedExits.insert(*ei).second) { 1870c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter double w = getEdgeWeight(*ei); 1880c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter if (w == MissingValue) { 1890c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter Edges.push_back(*ei); 1901640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Check if there is a necessary minimal weight, if yes, subtract it 1911640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // from weight. 1921640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (MinimalWeight.find(*ei) != MinimalWeight.end()) { 1931640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter incoming -= MinimalWeight[*ei]; 194244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n"); 1951640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 1960c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter } else { 1970c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter incoming -= w; 1980c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter } 1990c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter } 2000c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter } 2010c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter // If no exit edges, create one: 2020c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter if (Edges.size() == 0) { 2030c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter BasicBlock *Latch = BBLoop->getLoopLatch(); 2040c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter if (Latch) { 2050c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter Edge edge = getEdge(Latch,0); 2060c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter EdgeInformation[BB->getParent()][edge] = BBWeight; 2070c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter printEdgeWeight(edge); 2080c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter edge = getEdge(Latch, BB); 2090c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount; 2100c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter printEdgeWeight(edge); 21155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 21255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 2131640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter 2141640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Distribute remaining weight to the exting edges. To prevent fractions 2151640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // from building up and provoking precision problems the weight which is to 2161640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // be distributed is split and the rounded, the last edge gets a somewhat 2171640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // bigger value, but we are close enough for an estimation. 2181640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter double fraction = floor(incoming/Edges.size()); 21955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end(); 22055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar ei != ee; ++ei) { 2211640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter double w = 0; 2221640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (ei != (ee-1)) { 2231640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter w = fraction; 2241640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter incoming -= fraction; 2251640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } else { 2261640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter w = incoming; 2271640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 2281640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[BB->getParent()][*ei] += w; 2291640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Read necessary minimal weight. 2301640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (MinimalWeight.find(*ei) != MinimalWeight.end()) { 2311640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei]; 232244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n"); 2331640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 234ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter printEdgeWeight(*ei); 2351640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter 2361640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Add minimal weight to paths to all exit edges, this is used to ensure 2371640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // that enough flow is reaching this edges. 2381640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Path p; 2391640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter const BasicBlock *Dest = GetPath(BB, (*ei).first, p, GetPathToDest); 2401640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter while (Dest != BB) { 2411640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter const BasicBlock *Parent = p.find(Dest)->second; 2421640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Edge e = getEdge(Parent, Dest); 2431640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (MinimalWeight.find(e) == MinimalWeight.end()) { 2441640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter MinimalWeight[e] = 0; 2451640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 2461640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter MinimalWeight[e] += w; 247244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "Minimal Weight for " << e << ": " << format("%.20g",MinimalWeight[e]) << "\n"); 2481640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Dest = Parent; 2491640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 25055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 251ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter // Increase flow into the loop. 25255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar BBWeight *= (ExecCount+1); 25355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 25455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 2558a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter BlockInformation[BB->getParent()][BB] = BBWeight; 2568a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Up until now we considered only the loop exiting edges, now we have a 2571640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // definite block weight and must distribute this onto the outgoing edges. 2588a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Since there may be already flow attached to some of the edges, read this 2598a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // flow first and remember the edges that have still now flow attached. 26055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar Edges.clear(); 26155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar std::set<BasicBlock*> ProcessedSuccs; 262ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter 263e885af9fb773f5a01a5b31fa0a0b7fd0489bde56Andreas Neustifter succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 2648a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Also check for (BB,0) edges that may already contain some flow. (But only 2658a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // in case there are no successors.) 266e885af9fb773f5a01a5b31fa0a0b7fd0489bde56Andreas Neustifter if (bbi == bbe) { 267e885af9fb773f5a01a5b31fa0a0b7fd0489bde56Andreas Neustifter Edge edge = getEdge(BB,0); 268e885af9fb773f5a01a5b31fa0a0b7fd0489bde56Andreas Neustifter EdgeInformation[BB->getParent()][edge] = BBWeight; 269e885af9fb773f5a01a5b31fa0a0b7fd0489bde56Andreas Neustifter printEdgeWeight(edge); 270e885af9fb773f5a01a5b31fa0a0b7fd0489bde56Andreas Neustifter } 27119531d113c74d734a6e4128653ad694089e8981bAndreas Neustifter for ( ; bbi != bbe; ++bbi ) { 27255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (ProcessedSuccs.insert(*bbi).second) { 27355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar Edge edge = getEdge(BB,*bbi); 27455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar double w = getEdgeWeight(edge); 27555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (w != MissingValue) { 27655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar BBWeight -= getEdgeWeight(edge); 27755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } else { 27855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar Edges.push_back(edge); 2791640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // If minimal weight is necessary, reserve weight by subtracting weight 2801640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // from block weight, this is readded later on. 2811640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (MinimalWeight.find(edge) != MinimalWeight.end()) { 2821640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter BBWeight -= MinimalWeight[edge]; 283244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n"); 2841640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 28555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 28655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 28755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 28855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 2899e085a86376179cd471c3e6a59987339110ff92eRichard Smith double fraction = Edges.size() ? floor(BBWeight/Edges.size()) : 0.0; 2908a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Finally we know what flow is still not leaving the block, distribute this 2918a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // flow onto the empty edges. 29255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end(); 29355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar ei != ee; ++ei) { 2941640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (ei != (ee-1)) { 2951640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[BB->getParent()][*ei] += fraction; 2961640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter BBWeight -= fraction; 2971640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } else { 2981640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[BB->getParent()][*ei] += BBWeight; 2991640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 3001640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Readd minial necessary weight. 3011640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (MinimalWeight.find(*ei) != MinimalWeight.end()) { 3021640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei]; 303244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n"); 3041640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 305ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter printEdgeWeight(*ei); 30655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 30755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 3088a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // This block is visited, mark this before the recursion. 3098a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter BBToVisit.erase(BB); 3108a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter 3118a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Recurse into successors. 3128a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 3138a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter bbi != bbe; ++bbi) { 3148a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter recurseBasicBlock(*bbi); 31555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 31655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar} 31755e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 31855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbarbool ProfileEstimatorPass::runOnFunction(Function &F) { 31955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar if (F.isDeclaration()) return false; 32055e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 3218a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Fetch LoopInfo and clear ProfileInfo for this function. 32255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar LI = &getAnalysis<LoopInfo>(); 32355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar FunctionInformation.erase(&F); 32455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar BlockInformation[&F].clear(); 32555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar EdgeInformation[&F].clear(); 3260e3fae27a1634f51943d06588e32a550dae6a4b9Chris Lattner BBToVisit.clear(); 3278a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter 3288a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Mark all blocks as to visit. 3298a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi) 3308a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter BBToVisit.insert(bi); 33155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 3321640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Clear Minimal Edges. 3331640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter MinimalWeight.clear(); 3341640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter 335a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer DEBUG(dbgs() << "Working on function " << F.getName() << "\n"); 33655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 337ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter // Since the entry block is the first one and has no predecessors, the edge 338ff271e13539a43e804cab4457821a46a8bddc2ecAndreas Neustifter // (0,entry) is inserted with the starting weight of 1. 33955e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar BasicBlock *entry = &F.getEntryBlock(); 34088a91b579bb300f700a4acc5917f9e3a048dd05cBenjamin Kramer BlockInformation[&F][entry] = pow(2.0, 32.0); 34155e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar Edge edge = getEdge(0,entry); 3421640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[&F][edge] = BlockInformation[&F][entry]; 3438a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter printEdgeWeight(edge); 3448a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter 3458a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Since recurseBasicBlock() maybe returns with a block which was not fully 3461640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // estimated, use recurseBasicBlock() until everything is calculated. 3471640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter bool cleanup = false; 3488a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter recurseBasicBlock(entry); 3491640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter while (BBToVisit.size() > 0 && !cleanup) { 3508a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Remember number of open blocks, this is later used to check if progress 3518a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // was made. 3528a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter unsigned size = BBToVisit.size(); 3538a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter 3548a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // Try to calculate all blocks in turn. 3558a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(), 3568a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter be = BBToVisit.end(); bi != be; ++bi) { 3578a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter recurseBasicBlock(*bi); 3588a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // If at least one block was finished, break because iterator may be 3598a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter // invalid. 3608a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter if (BBToVisit.size() < size) break; 3618a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter } 3628a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter 3631640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // If there was not a single block resolved, make some assumptions. 3648a58c180c288accc74d37ca94045a90efda3ae5cAndreas Neustifter if (BBToVisit.size() == size) { 3651640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter bool found = false; 3661640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end(); 3671640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter (BBI != BBE) && (!found); ++BBI) { 3681640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter BasicBlock *BB = *BBI; 3691640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Try each predecessor if it can be assumend. 3701640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB); 3711640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter (bbi != bbe) && (!found); ++bbi) { 3721640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Edge e = getEdge(*bbi,BB); 3731640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter double w = getEdgeWeight(e); 3741640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Check that edge from predecessor is still free. 3751640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (w == MissingValue) { 3761640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // Check if there is a circle from this block to predecessor. 3771640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Path P; 3781640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest); 3791640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (Dest != *bbi) { 3801640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // If there is no circle, just set edge weight to 0 3811640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[&F][e] = 0; 382244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "Assuming edge weight: "); 3831640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter printEdgeWeight(e); 3841640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter found = true; 3851640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 3861640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 3870c0de66ea40df4c7ef64d7d5259507b72e8c4d1fAndreas Neustifter } 38855e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 3891640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (!found) { 3901640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter cleanup = true; 391244d7571f723f4e438c17f06decaf7afcd5bbf2cDavid Greene DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n"); 3921640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 3931640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 3941640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 3951640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // In case there was no safe way to assume edges, set as a last measure, 3961640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter // set _everything_ to zero. 3971640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (cleanup) { 3981640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter FunctionInformation[&F] = 0; 3991640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter BlockInformation[&F].clear(); 4001640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter EdgeInformation[&F].clear(); 4011640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 4021640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter const BasicBlock *BB = &(*FI); 4031640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter BlockInformation[&F][BB] = 0; 40444424646ac9db5c4d3919462bd0831ec22783085Gabor Greif const_pred_iterator predi = pred_begin(BB), prede = pred_end(BB); 4051640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (predi == prede) { 4061640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Edge e = getEdge(0,BB); 4071640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter setEdgeWeight(e,0); 4081640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 4091640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter for (;predi != prede; ++predi) { 4101640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Edge e = getEdge(*predi,BB); 4111640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter setEdgeWeight(e,0); 4121640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 4131640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB); 4141640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter if (succi == succe) { 4151640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Edge e = getEdge(BB,0); 4161640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter setEdgeWeight(e,0); 4171640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 4181640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter for (;succi != succe; ++succi) { 4191640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter Edge e = getEdge(*succi,BB); 4201640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter setEdgeWeight(e,0); 4211640f7e033116256813a301dd8f581e7f9272a3fAndreas Neustifter } 42255e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 42355e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar } 42455e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar 42555e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar return false; 42655e354ac0e294bde258420f80a2cc11ea19db482Daniel Dunbar} 427