third_party/LLVM/lib/Analysis/ProfileInfo.cpp

//===- ProfileInfo.cpp - Profile Info Interface ---------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the abstract ProfileInfo interface, and the default
// "no profile" implementation.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "profile-info"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/ProfileInfo.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/Pass.h"
#include "llvm/Support/CFG.h"
#include "llvm/ADT/SmallSet.h"
#include <set>
#include <queue>
#include <limits>
using namespace llvm;

namespace llvm {
  template<> char ProfileInfoT<Function,BasicBlock>::ID = 0;
}

// Register the ProfileInfo interface, providing a nice name to refer to.
INITIALIZE_ANALYSIS_GROUP(ProfileInfo, "Profile Information", NoProfileInfo)

namespace llvm {

template <>
ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {}
template <>
ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {}

template <>
ProfileInfoT<Function, BasicBlock>::ProfileInfoT() {
  MachineProfile = 0;
}
template <>
ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() {
  if (MachineProfile) delete MachineProfile;
}

template<>
char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0;

template<>
const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1;

template<> const
double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1;

template<> double
ProfileInfoT<Function,BasicBlock>::getExecutionCount(const BasicBlock *BB) {
  std::map<const Function*, BlockCounts>::iterator J =
    BlockInformation.find(BB->getParent());
  if (J != BlockInformation.end()) {
    BlockCounts::iterator I = J->second.find(BB);
    if (I != J->second.end())
      return I->second;
  }

  double Count = MissingValue;

  const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);

  // Are there zero predecessors of this block?
  if (PI == PE) {
    Edge e = getEdge(0, BB);
    Count = getEdgeWeight(e);
  } else {
    // Otherwise, if there are predecessors, the execution count of this block is
    // the sum of the edge frequencies from the incoming edges.
    std::set<const BasicBlock*> ProcessedPreds;
    Count = 0;
    for (; PI != PE; ++PI) {
      const BasicBlock *P = *PI;
      if (ProcessedPreds.insert(P).second) {
        double w = getEdgeWeight(getEdge(P, BB));
        if (w == MissingValue) {
          Count = MissingValue;
          break;
        }
        Count += w;
      }
    }
  }

  // If the predecessors did not suffice to get block weight, try successors.
  if (Count == MissingValue) {

    succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);

    // Are there zero successors of this block?
    if (SI == SE) {
      Edge e = getEdge(BB,0);
      Count = getEdgeWeight(e);
    } else {
      std::set<const BasicBlock*> ProcessedSuccs;
      Count = 0;
      for (; SI != SE; ++SI)
        if (ProcessedSuccs.insert(*SI).second) {
          double w = getEdgeWeight(getEdge(BB, *SI));
          if (w == MissingValue) {
            Count = MissingValue;
            break;
          }
          Count += w;
        }
    }
  }

  if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count;
  return Count;
}

template<>
double ProfileInfoT<MachineFunction, MachineBasicBlock>::
        getExecutionCount(const MachineBasicBlock *MBB) {
  std::map<const MachineFunction*, BlockCounts>::iterator J =
    BlockInformation.find(MBB->getParent());
  if (J != BlockInformation.end()) {
    BlockCounts::iterator I = J->second.find(MBB);
    if (I != J->second.end())
      return I->second;
  }

  return MissingValue;
}

template<>
double ProfileInfoT<Function,BasicBlock>::getExecutionCount(const Function *F) {
  std::map<const Function*, double>::iterator J =
    FunctionInformation.find(F);
  if (J != FunctionInformation.end())
    return J->second;

  // isDeclaration() is checked here and not at start of function to allow
  // functions without a body still to have a execution count.
  if (F->isDeclaration()) return MissingValue;

  double Count = getExecutionCount(&F->getEntryBlock());
  if (Count != MissingValue) FunctionInformation[F] = Count;
  return Count;
}

template<>
double ProfileInfoT<MachineFunction, MachineBasicBlock>::
        getExecutionCount(const MachineFunction *MF) {
  std::map<const MachineFunction*, double>::iterator J =
    FunctionInformation.find(MF);
  if (J != FunctionInformation.end())
    return J->second;

  double Count = getExecutionCount(&MF->front());
  if (Count != MissingValue) FunctionInformation[MF] = Count;
  return Count;
}

template<>
void ProfileInfoT<Function,BasicBlock>::
        setExecutionCount(const BasicBlock *BB, double w) {
  DEBUG(dbgs() << "Creating Block " << BB->getName() 
               << " (weight: " << format("%.20g",w) << ")\n");
  BlockInformation[BB->getParent()][BB] = w;
}

template<>
void ProfileInfoT<MachineFunction, MachineBasicBlock>::
        setExecutionCount(const MachineBasicBlock *MBB, double w) {
  DEBUG(dbgs() << "Creating Block " << MBB->getBasicBlock()->getName()
               << " (weight: " << format("%.20g",w) << ")\n");
  BlockInformation[MBB->getParent()][MBB] = w;
}

template<>
void ProfileInfoT<Function,BasicBlock>::addEdgeWeight(Edge e, double w) {
  double oldw = getEdgeWeight(e);
  assert (oldw != MissingValue && "Adding weight to Edge with no previous weight");
  DEBUG(dbgs() << "Adding to Edge " << e
               << " (new weight: " << format("%.20g",oldw + w) << ")\n");
  EdgeInformation[getFunction(e)][e] = oldw + w;
}

template<>
void ProfileInfoT<Function,BasicBlock>::
        addExecutionCount(const BasicBlock *BB, double w) {
  double oldw = getExecutionCount(BB);
  assert (oldw != MissingValue && "Adding weight to Block with no previous weight");
  DEBUG(dbgs() << "Adding to Block " << BB->getName()
               << " (new weight: " << format("%.20g",oldw + w) << ")\n");
  BlockInformation[BB->getParent()][BB] = oldw + w;
}

template<>
void ProfileInfoT<Function,BasicBlock>::removeBlock(const BasicBlock *BB) {
  std::map<const Function*, BlockCounts>::iterator J =
    BlockInformation.find(BB->getParent());
  if (J == BlockInformation.end()) return;

  DEBUG(dbgs() << "Deleting " << BB->getName() << "\n");
  J->second.erase(BB);
}

template<>
void ProfileInfoT<Function,BasicBlock>::removeEdge(Edge e) {
  std::map<const Function*, EdgeWeights>::iterator J =
    EdgeInformation.find(getFunction(e));
  if (J == EdgeInformation.end()) return;

  DEBUG(dbgs() << "Deleting" << e << "\n");
  J->second.erase(e);
}

template<>
void ProfileInfoT<Function,BasicBlock>::
        replaceEdge(const Edge &oldedge, const Edge &newedge) {
  double w;
  if ((w = getEdgeWeight(newedge)) == MissingValue) {
    w = getEdgeWeight(oldedge);
    DEBUG(dbgs() << "Replacing " << oldedge << " with " << newedge  << "\n");
  } else {
    w += getEdgeWeight(oldedge);
    DEBUG(dbgs() << "Adding " << oldedge << " to " << newedge  << "\n");
  }
  setEdgeWeight(newedge,w);
  removeEdge(oldedge);
}

template<>
const BasicBlock *ProfileInfoT<Function,BasicBlock>::
        GetPath(const BasicBlock *Src, const BasicBlock *Dest,
                Path &P, unsigned Mode) {
  const BasicBlock *BB = 0;
  bool hasFoundPath = false;

  std::queue<const BasicBlock *> BFS;
  BFS.push(Src);

  while(BFS.size() && !hasFoundPath) {
    BB = BFS.front();
    BFS.pop();

    succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
    if (Succ == End) {
      P[0] = BB;
      if (Mode & GetPathToExit) {
        hasFoundPath = true;
        BB = 0;
      }
    }
    for(;Succ != End; ++Succ) {
      if (P.find(*Succ) != P.end()) continue;
      Edge e = getEdge(BB,*Succ);
      if ((Mode & GetPathWithNewEdges) && (getEdgeWeight(e) != MissingValue)) continue;
      P[*Succ] = BB;
      BFS.push(*Succ);
      if ((Mode & GetPathToDest) && *Succ == Dest) {
        hasFoundPath = true;
        BB = *Succ;
        break;
      }
      if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) {
        hasFoundPath = true;
        BB = *Succ;
        break;
      }
    }
  }

  return BB;
}

template<>
void ProfileInfoT<Function,BasicBlock>::
        divertFlow(const Edge &oldedge, const Edge &newedge) {
  DEBUG(dbgs() << "Diverting " << oldedge << " via " << newedge );

  // First check if the old edge was taken, if not, just delete it...
  if (getEdgeWeight(oldedge) == 0) {
    removeEdge(oldedge);
    return;
  }

  Path P;
  P[newedge.first] = 0;
  P[newedge.second] = newedge.first;
  const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest);

  double w = getEdgeWeight (oldedge);
  DEBUG(dbgs() << ", Weight: " << format("%.20g",w) << "\n");
  do {
    const BasicBlock *Parent = P.find(BB)->second;
    Edge e = getEdge(Parent,BB);
    double oldw = getEdgeWeight(e);
    double oldc = getExecutionCount(e.first);
    setEdgeWeight(e, w+oldw);
    if (Parent != oldedge.first) {
      setExecutionCount(e.first, w+oldc);
    }
    BB = Parent;
  } while (BB != newedge.first);
  removeEdge(oldedge);
}

/// Replaces all occurrences of RmBB in the ProfilingInfo with DestBB.
/// This checks all edges of the function the blocks reside in and replaces the
/// occurrences of RmBB with DestBB.
template<>
void ProfileInfoT<Function,BasicBlock>::
        replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB) {
  DEBUG(dbgs() << "Replacing " << RmBB->getName()
               << " with " << DestBB->getName() << "\n");
  const Function *F = DestBB->getParent();
  std::map<const Function*, EdgeWeights>::iterator J =
    EdgeInformation.find(F);
  if (J == EdgeInformation.end()) return;

  Edge e, newedge;
  bool erasededge = false;
  EdgeWeights::iterator I = J->second.begin(), E = J->second.end();
  while(I != E) {
    e = (I++)->first;
    bool foundedge = false; bool eraseedge = false;
    if (e.first == RmBB) {
      if (e.second == DestBB) {
        eraseedge = true;
      } else {
        newedge = getEdge(DestBB, e.second);
        foundedge = true;
      }
    }
    if (e.second == RmBB) {
      if (e.first == DestBB) {
        eraseedge = true;
      } else {
        newedge = getEdge(e.first, DestBB);
        foundedge = true;
      }
    }
    if (foundedge) {
      replaceEdge(e, newedge);
    }
    if (eraseedge) {
      if (erasededge) {
        Edge newedge = getEdge(DestBB, DestBB);
        replaceEdge(e, newedge);
      } else {
        removeEdge(e);
        erasededge = true;
      }
    }
  }
}

/// Splits an edge in the ProfileInfo and redirects flow over NewBB.
/// Since its possible that there is more than one edge in the CFG from FristBB
/// to SecondBB its necessary to redirect the flow proporionally.
template<>
void ProfileInfoT<Function,BasicBlock>::splitEdge(const BasicBlock *FirstBB,
                                                  const BasicBlock *SecondBB,
                                                  const BasicBlock *NewBB,
                                                  bool MergeIdenticalEdges) {
  const Function *F = FirstBB->getParent();
  std::map<const Function*, EdgeWeights>::iterator J =
    EdgeInformation.find(F);
  if (J == EdgeInformation.end()) return;

  // Generate edges and read current weight.
  Edge e  = getEdge(FirstBB, SecondBB);
  Edge n1 = getEdge(FirstBB, NewBB);
  Edge n2 = getEdge(NewBB, SecondBB);
  EdgeWeights &ECs = J->second;
  double w = ECs[e];

  int succ_count = 0;
  if (!MergeIdenticalEdges) {
    // First count the edges from FristBB to SecondBB, if there is more than
    // one, only slice out a proporional part for NewBB.
    for(succ_const_iterator BBI = succ_begin(FirstBB), BBE = succ_end(FirstBB);
        BBI != BBE; ++BBI) {
      if (*BBI == SecondBB) succ_count++;  
    }
    // When the NewBB is completely new, increment the count by one so that
    // the counts are properly distributed.
    if (getExecutionCount(NewBB) == ProfileInfo::MissingValue) succ_count++;
  } else {
    // When the edges are merged anyway, then redirect all flow.
    succ_count = 1;
  }

  // We know now how many edges there are from FirstBB to SecondBB, reroute a
  // proportional part of the edge weight over NewBB.
  double neww = floor(w / succ_count);
  ECs[n1] += neww;
  ECs[n2] += neww;
  BlockInformation[F][NewBB] += neww;
  if (succ_count == 1) {
    ECs.erase(e);
  } else {
    ECs[e] -= neww;
  }
}

template<>
void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *Old,
                                                   const BasicBlock* New) {
  const Function *F = Old->getParent();
  std::map<const Function*, EdgeWeights>::iterator J =
    EdgeInformation.find(F);
  if (J == EdgeInformation.end()) return;

  DEBUG(dbgs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n");

  std::set<Edge> Edges;
  for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end(); 
       ewi != ewe; ++ewi) {
    Edge old = ewi->first;
    if (old.first == Old) {
      Edges.insert(old);
    }
  }
  for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end(); 
       EI != EE; ++EI) {
    Edge newedge = getEdge(New, EI->second);
    replaceEdge(*EI, newedge);
  }

  double w = getExecutionCount(Old);
  setEdgeWeight(getEdge(Old, New), w);
  setExecutionCount(New, w);
}

template<>
void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *BB,
                                                   const BasicBlock* NewBB,
                                                   BasicBlock *const *Preds,
                                                   unsigned NumPreds) {
  const Function *F = BB->getParent();
  std::map<const Function*, EdgeWeights>::iterator J =
    EdgeInformation.find(F);
  if (J == EdgeInformation.end()) return;

  DEBUG(dbgs() << "Splitting " << NumPreds << " Edges from " << BB->getName() 
               << " to " << NewBB->getName() << "\n");

  // Collect weight that was redirected over NewBB.
  double newweight = 0;
  
  std::set<const BasicBlock *> ProcessedPreds;
  // For all requestes Predecessors.
  for (unsigned pred = 0; pred < NumPreds; ++pred) {
    const BasicBlock * Pred = Preds[pred];
    if (ProcessedPreds.insert(Pred).second) {
      // Create edges and read old weight.
      Edge oldedge = getEdge(Pred, BB);
      Edge newedge = getEdge(Pred, NewBB);

      // Remember how much weight was redirected.
      newweight += getEdgeWeight(oldedge);
    
      replaceEdge(oldedge,newedge);
    }
  }

  Edge newedge = getEdge(NewBB,BB);
  setEdgeWeight(newedge, newweight);
  setExecutionCount(NewBB, newweight);
}

template<>
void ProfileInfoT<Function,BasicBlock>::transfer(const Function *Old,
                                                 const Function *New) {
  DEBUG(dbgs() << "Replacing Function " << Old->getName() << " with "
               << New->getName() << "\n");
  std::map<const Function*, EdgeWeights>::iterator J =
    EdgeInformation.find(Old);
  if(J != EdgeInformation.end()) {
    EdgeInformation[New] = J->second;
  }
  EdgeInformation.erase(Old);
  BlockInformation.erase(Old);
  FunctionInformation.erase(Old);
}

static double readEdgeOrRemember(ProfileInfo::Edge edge, double w,
                                 ProfileInfo::Edge &tocalc, unsigned &uncalc) {
  if (w == ProfileInfo::MissingValue) {
    tocalc = edge;
    uncalc++;
    return 0;
  } else {
    return w;
  }
}

template<>
bool ProfileInfoT<Function,BasicBlock>::
        CalculateMissingEdge(const BasicBlock *BB, Edge &removed,
                             bool assumeEmptySelf) {
  Edge edgetocalc;
  unsigned uncalculated = 0;

  // collect weights of all incoming and outgoing edges, rememer edges that
  // have no value
  double incount = 0;
  SmallSet<const BasicBlock*,8> pred_visited;
  const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
  if (bbi==bbe) {
    Edge e = getEdge(0,BB);
    incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
  }
  for (;bbi != bbe; ++bbi) {
    if (pred_visited.insert(*bbi)) {
      Edge e = getEdge(*bbi,BB);
      incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
    }
  }

  double outcount = 0;
  SmallSet<const BasicBlock*,8> succ_visited;
  succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
  if (sbbi==sbbe) {
    Edge e = getEdge(BB,0);
    if (getEdgeWeight(e) == MissingValue) {
      double w = getExecutionCount(BB);
      if (w != MissingValue) {
        setEdgeWeight(e,w);
        removed = e;
      }
    }
    outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
  }
  for (;sbbi != sbbe; ++sbbi) {
    if (succ_visited.insert(*sbbi)) {
      Edge e = getEdge(BB,*sbbi);
      outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
    }
  }

  // if exactly one edge weight was missing, calculate it and remove it from
  // spanning tree
  if (uncalculated == 0 ) {
    return true;
  } else
  if (uncalculated == 1) {
    if (incount < outcount) {
      EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
    } else {
      EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
    }
    DEBUG(dbgs() << "--Calc Edge Counter for " << edgetocalc << ": "
                 << format("%.20g", getEdgeWeight(edgetocalc)) << "\n");
    removed = edgetocalc;
    return true;
  } else 
  if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) {
    setEdgeWeight(edgetocalc, incount * 10);
    removed = edgetocalc;
    return true;
  } else {
    return false;
  }
}

static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::set<ProfileInfo::Edge> &misscount) {
  double w = PI->getEdgeWeight(e);
  if (w != ProfileInfo::MissingValue) {
    calcw += w;
  } else {
    misscount.insert(e);
  }
}

template<>
bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) {
  double inWeight = 0;
  std::set<Edge> inMissing;
  std::set<const BasicBlock*> ProcessedPreds;
  const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
  if (bbi == bbe) {
    readEdge(this,getEdge(0,BB),inWeight,inMissing);
  }
  for( ; bbi != bbe; ++bbi ) {
    if (ProcessedPreds.insert(*bbi).second) {
      readEdge(this,getEdge(*bbi,BB),inWeight,inMissing);
    }
  }

  double outWeight = 0;
  std::set<Edge> outMissing;
  std::set<const BasicBlock*> ProcessedSuccs;
  succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
  if (sbbi == sbbe)
    readEdge(this,getEdge(BB,0),outWeight,outMissing);
  for ( ; sbbi != sbbe; ++sbbi ) {
    if (ProcessedSuccs.insert(*sbbi).second) {
      readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
    }
  }

  double share;
  std::set<Edge>::iterator ei,ee;
  if (inMissing.size() == 0 && outMissing.size() > 0) {
    ei = outMissing.begin();
    ee = outMissing.end();
    share = inWeight/outMissing.size();
    setExecutionCount(BB,inWeight);
  } else
  if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
    ei = inMissing.begin();
    ee = inMissing.end();
    share = 0;
    setExecutionCount(BB,0);
  } else
  if (inMissing.size() == 0 && outMissing.size() == 0) {
    setExecutionCount(BB,outWeight);
    return true;
  } else {
    return false;
  }
  for ( ; ei != ee; ++ei ) {
    setEdgeWeight(*ei,share);
  }
  return true;
}

template<>
void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
//  if (getExecutionCount(&(F->getEntryBlock())) == 0) {
//    for (Function::const_iterator FI = F->begin(), FE = F->end();
//         FI != FE; ++FI) {
//      const BasicBlock* BB = &(*FI);
//      {
//        const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
//        if (NBB == End) {
//          setEdgeWeight(getEdge(0,BB),0);
//        }
//        for(;NBB != End; ++NBB) {
//          setEdgeWeight(getEdge(*NBB,BB),0);
//        }
//      }
//      {
//        succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
//        if (NBB == End) {
//          setEdgeWeight(getEdge(0,BB),0);
//        }
//        for(;NBB != End; ++NBB) {
//          setEdgeWeight(getEdge(*NBB,BB),0);
//        }
//      }
//    }
//    return;
//  }
  // The set of BasicBlocks that are still unvisited.
  std::set<const BasicBlock*> Unvisited;

  // The set of return edges (Edges with no successors).
  std::set<Edge> ReturnEdges;
  double ReturnWeight = 0;
  
  // First iterate over the whole function and collect:
  // 1) The blocks in this function in the Unvisited set.
  // 2) The return edges in the ReturnEdges set.
  // 3) The flow that is leaving the function already via return edges.

  // Data structure for searching the function.
  std::queue<const BasicBlock *> BFS;
  const BasicBlock *BB = &(F->getEntryBlock());
  BFS.push(BB);
  Unvisited.insert(BB);

  while (BFS.size()) {
    BB = BFS.front(); BFS.pop();
    succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
    if (NBB == End) {
      Edge e = getEdge(BB,0);
      double w = getEdgeWeight(e);
      if (w == MissingValue) {
        // If the return edge has no value, try to read value from block.
        double bw = getExecutionCount(BB);
        if (bw != MissingValue) {
          setEdgeWeight(e,bw);
          ReturnWeight += bw;
        } else {
          // If both return edge and block provide no value, collect edge.
          ReturnEdges.insert(e);
        }
      } else {
        // If the return edge has a proper value, collect it.
        ReturnWeight += w;
      }
    }
    for (;NBB != End; ++NBB) {
      if (Unvisited.insert(*NBB).second) {
        BFS.push(*NBB);
      }
    }
  }

  while (Unvisited.size() > 0) {
    unsigned oldUnvisitedCount = Unvisited.size();
    bool FoundPath = false;

    // If there is only one edge left, calculate it.
    if (ReturnEdges.size() == 1) {
      ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;

      Edge e = *ReturnEdges.begin();
      setEdgeWeight(e,ReturnWeight);
      setExecutionCount(e.first,ReturnWeight);

      Unvisited.erase(e.first);
      ReturnEdges.erase(e);
      continue;
    }

    // Calculate all blocks where only one edge is missing, this may also
    // resolve furhter return edges.
    std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE) {
      const BasicBlock *BB = *FI; ++FI;
      Edge e;
      if(CalculateMissingEdge(BB,e,true)) {
        if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
          setExecutionCount(BB,getExecutionCount(BB));
        }
        Unvisited.erase(BB);
        if (e.first != 0 && e.second == 0) {
          ReturnEdges.erase(e);
          ReturnWeight += getEdgeWeight(e);
        }
      }
    }
    if (oldUnvisitedCount > Unvisited.size()) continue;

    // Estimate edge weights by dividing the flow proportionally.
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE) {
      const BasicBlock *BB = *FI; ++FI;
      const BasicBlock *Dest = 0;
      bool AllEdgesHaveSameReturn = true;
      // Check each Successor, these must all end up in the same or an empty
      // return block otherwise its dangerous to do an estimation on them.
      for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
           Succ != End; ++Succ) {
        Path P;
        GetPath(*Succ, 0, P, GetPathToExit);
        if (Dest && Dest != P[0]) {
          AllEdgesHaveSameReturn = false;
        }
        Dest = P[0];
      }
      if (AllEdgesHaveSameReturn) {
        if(EstimateMissingEdges(BB)) {
          Unvisited.erase(BB);
          break;
        }
      }
    }
    if (oldUnvisitedCount > Unvisited.size()) continue;

    // Check if there is a path to an block that has a known value and redirect
    // flow accordingly.
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE && !FoundPath) {
      // Fetch path.
      const BasicBlock *BB = *FI; ++FI;
      Path P;
      const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);

      // Calculate incoming flow.
      double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0;
      std::set<const BasicBlock *> Processed;
      for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
           NBB != End; ++NBB) {
        if (Processed.insert(*NBB).second) {
          Edge e = getEdge(*NBB, BB);
          double ew = getEdgeWeight(e);
          if (ew != MissingValue) {
            iw += ew;
            invalid++;
          } else {
            // If the path contains the successor, this means its a backedge,
            // do not count as missing.
            if (P.find(*NBB) == P.end())
              inmissing++;
          }
          incount++;
        }
      }
      if (inmissing == incount) continue;
      if (invalid == 0) continue;

      // Subtract (already) outgoing flow.
      Processed.clear();
      for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
           NBB != End; ++NBB) {
        if (Processed.insert(*NBB).second) {
          Edge e = getEdge(BB, *NBB);
          double ew = getEdgeWeight(e);
          if (ew != MissingValue) {
            iw -= ew;
          }
        }
      }
      if (iw < 0) continue;

      // Check the receiving end of the path if it can handle the flow.
      double ow = getExecutionCount(Dest);
      Processed.clear();
      for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
           NBB != End; ++NBB) {
        if (Processed.insert(*NBB).second) {
          Edge e = getEdge(BB, *NBB);
          double ew = getEdgeWeight(e);
          if (ew != MissingValue) {
            ow -= ew;
          }
        }
      }
      if (ow < 0) continue;

      // Determine how much flow shall be used.
      double ew = getEdgeWeight(getEdge(P[Dest],Dest));
      if (ew != MissingValue) {
        ew = ew<ow?ew:ow;
        ew = ew<iw?ew:iw;
      } else {
        if (inmissing == 0)
          ew = iw;
      }

      // Create flow.
      if (ew != MissingValue) {
        do {
          Edge e = getEdge(P[Dest],Dest);
          if (getEdgeWeight(e) == MissingValue) {
            setEdgeWeight(e,ew);
            FoundPath = true;
          }
          Dest = P[Dest];
        } while (Dest != BB);
      }
    }
    if (FoundPath) continue;

    // Calculate a block with self loop.
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE && !FoundPath) {
      const BasicBlock *BB = *FI; ++FI;
      bool SelfEdgeFound = false;
      for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
           NBB != End; ++NBB) {
        if (*NBB == BB) {
          SelfEdgeFound = true;
          break;
        }
      }
      if (SelfEdgeFound) {
        Edge e = getEdge(BB,BB);
        if (getEdgeWeight(e) == MissingValue) {
          double iw = 0;
          std::set<const BasicBlock *> Processed;
          for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
               NBB != End; ++NBB) {
            if (Processed.insert(*NBB).second) {
              Edge e = getEdge(*NBB, BB);
              double ew = getEdgeWeight(e);
              if (ew != MissingValue) {
                iw += ew;
              }
            }
          }
          setEdgeWeight(e,iw * 10);
          FoundPath = true;
        }
      }
    }
    if (FoundPath) continue;

    // Determine backedges, set them to zero.
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE && !FoundPath) {
      const BasicBlock *BB = *FI; ++FI;
      const BasicBlock *Dest = 0;
      Path P;
      bool BackEdgeFound = false;
      for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
           NBB != End; ++NBB) {
        Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
        if (Dest == *NBB) {
          BackEdgeFound = true;
          break;
        }
      }
      if (BackEdgeFound) {
        Edge e = getEdge(Dest,BB);
        double w = getEdgeWeight(e);
        if (w == MissingValue) {
          setEdgeWeight(e,0);
          FoundPath = true;
        }
        do {
          Edge e = getEdge(P[Dest], Dest);
          double w = getEdgeWeight(e);
          if (w == MissingValue) {
            setEdgeWeight(e,0);
            FoundPath = true;
          }
          Dest = P[Dest];
        } while (Dest != BB);
      }
    }
    if (FoundPath) continue;

    // Channel flow to return block.
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE && !FoundPath) {
      const BasicBlock *BB = *FI; ++FI;

      Path P;
      const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
      Dest = P[0];
      if (!Dest) continue;

      if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
        // Calculate incoming flow.
        double iw = 0;
        std::set<const BasicBlock *> Processed;
        for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
             NBB != End; ++NBB) {
          if (Processed.insert(*NBB).second) {
            Edge e = getEdge(*NBB, BB);
            double ew = getEdgeWeight(e);
            if (ew != MissingValue) {
              iw += ew;
            }
          }
        }
        do {
          Edge e = getEdge(P[Dest], Dest);
          double w = getEdgeWeight(e);
          if (w == MissingValue) {
            setEdgeWeight(e,iw);
            FoundPath = true;
          } else {
            assert(0 && "Edge should not have value already!");
          }
          Dest = P[Dest];
        } while (Dest != BB);
      }
    }
    if (FoundPath) continue;

    // Speculatively set edges to zero.
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE && !FoundPath) {
      const BasicBlock *BB = *FI; ++FI;

      for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
           NBB != End; ++NBB) {
        Edge e = getEdge(*NBB,BB);
        double w = getEdgeWeight(e);
        if (w == MissingValue) {
          setEdgeWeight(e,0);
          FoundPath = true;
          break;
        }
      }
    }
    if (FoundPath) continue;

    errs() << "{";
    FI = Unvisited.begin(), FE = Unvisited.end();
    while(FI != FE) {
      const BasicBlock *BB = *FI; ++FI;
      dbgs() << BB->getName();
      if (FI != FE)
        dbgs() << ",";
    }
    errs() << "}";

    errs() << "ASSERT: could not repair function";
    assert(0 && "could not repair function");
  }

  EdgeWeights J = EdgeInformation[F];
  for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
    Edge e = EI->first;

    bool SuccFound = false;
    if (e.first != 0) {
      succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
      if (NBB == End) {
        if (0 == e.second) {
          SuccFound = true;
        }
      }
      for (;NBB != End; ++NBB) {
        if (*NBB == e.second) {
          SuccFound = true;
          break;
        }
      }
      if (!SuccFound) {
        removeEdge(e);
      }
    }
  }
}

raw_ostream& operator<<(raw_ostream &O, const Function *F) {
  return O << F->getName();
}

raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
  return O << MF->getFunction()->getName() << "(MF)";
}

raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
  return O << BB->getName();
}

raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
  return O << MBB->getBasicBlock()->getName() << "(MB)";
}

raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
  O << "(";

  if (E.first)
    O << E.first;
  else
    O << "0";

  O << ",";

  if (E.second)
    O << E.second;
  else
    O << "0";

  return O << ")";
}

raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
  O << "(";

  if (E.first)
    O << E.first;
  else
    O << "0";

  O << ",";

  if (E.second)
    O << E.second;
  else
    O << "0";

  return O << ")";
}

} // namespace llvm

//===----------------------------------------------------------------------===//
//  NoProfile ProfileInfo implementation
//

namespace {
  struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
    static char ID; // Class identification, replacement for typeinfo
    NoProfileInfo() : ImmutablePass(ID) {
      initializeNoProfileInfoPass(*PassRegistry::getPassRegistry());
    }
    
    /// getAdjustedAnalysisPointer - This method is used when a pass implements
    /// an analysis interface through multiple inheritance.  If needed, it
    /// should override this to adjust the this pointer as needed for the
    /// specified pass info.
    virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
      if (PI == &ProfileInfo::ID)
        return (ProfileInfo*)this;
      return this;
    }
    
    virtual const char *getPassName() const {
      return "NoProfileInfo";
    }
  };
}  // End of anonymous namespace

char NoProfileInfo::ID = 0;
// Register this pass...
INITIALIZE_AG_PASS(NoProfileInfo, ProfileInfo, "no-profile",
                   "No Profile Information", false, true, true)

ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }