用最大生成树减少 PGO 边计数插桩

9// This file implements PGO instrumentation using a minimum spanning tree based10// on the following paper:11//   [1] Donald E. Knuth, Francis R. Stevenson. Optimal measurement of points12//   for program frequency counts. BIT Numerical Mathematics 1973, Volume 13,13//   Issue 3, pp 313-32214// The idea of the algorithm based on the fact that for each node (except for15// the entry and exit), the sum of incoming edge counts equals the sum of16// outgoing edge counts. The count of edge on spanning tree can be derived from17// those edges not on the spanning tree. Knuth proves this method instruments18// the minimum number of edges.19//20// The minimal spanning tree here is actually a maximum weight tree -- on-tree21// edges have higher frequencies (more likely to execute). The idea is to22// instrument those less frequently executed edges to reduce the runtime23// overhead of instrumented binaries.

59  // Find the root group of the G and compress the path from G to the root.60  BBInfo *findAndCompressGroup(BBInfo *G) {61    if (G->Group != G)62      G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));63    return static_cast<BBInfo *>(G->Group);64  }6566  // Union BB1 and BB2 into the same group and return true.67  // Returns false if BB1 and BB2 are already in the same group.68  bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2) {69    BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));70    BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));7172    if (BB1G == BB2G)73      return false;

75    // Make the smaller rank tree a direct child or the root of high rank tree.76    if (BB1G->Rank < BB2G->Rank)77      BB1G->Group = BB2G;78    else {79      BB2G->Group = BB1G;80      // If the ranks are the same, increment root of one tree by one.81      if (BB1G->Rank == BB2G->Rank)82        BB1G->Rank++;83    }84    return true;85  }

218  // Sort CFG edges based on its weight.219  void sortEdgesByWeight() {220    llvm::stable_sort(AllEdges, [](const std::unique_ptr<Edge> &Edge1,221                                   const std::unique_ptr<Edge> &Edge2) {222      return Edge1->Weight > Edge2->Weight;223    });224  }225226  // Traverse all the edges and compute the Minimum Weight Spanning Tree227  // using union-find algorithm.228  void computeMinimumSpanningTree() {229    // First, put all the critical edge with landing-pad as the Dest to MST.230    // This works around the insufficient support of critical edges split231    // when destination BB is a landing pad.232    for (auto &Ei : AllEdges) {233      if (Ei->Removed)234        continue;235      if (Ei->IsCritical) {236        if (Ei->DestBB && Ei->DestBB->isLandingPad()) {237          if (unionGroups(Ei->SrcBB, Ei->DestBB))238            Ei->InMST = true;

243    for (auto &Ei : AllEdges) {244      if (Ei->Removed)245        continue;246      // If we detect infinite loops, force247      // instrumenting the entry edge:248      if (!ExitBlockFound && Ei->SrcBB == nullptr)249        continue;250      if (unionGroups(Ei->SrcBB, Ei->DestBB))251        Ei->InMST = true;252    }

779// Given a CFG E to be instrumented, find which BB to place the instrumented780// code. The function will split the critical edge if necessary.781template <class Edge, class BBInfo>782BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {783  if (E->InMST || E->Removed)784    return nullptr;785786  BasicBlock *SrcBB = E->SrcBB;787  BasicBlock *DestBB = E->DestBB;788  // For a fake edge, instrument the real BB.789  if (SrcBB == nullptr)790    return DestBB;791  if (DestBB == nullptr)792    return SrcBB;793794  auto canInstrument = [](BasicBlock *BB) -> BasicBlock * {795    // There are basic blocks (such as catchswitch) cannot be instrumented.796    // If the returned first insertion point is the end of BB, skip this BB.797    if (BB->getFirstInsertionPt() == BB->end())798      return nullptr;799    return BB;