Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Instrumentation/CFGMST.h
Line
Count
Source (jump to first uncovered line)
1
//===-- CFGMST.h - Minimum Spanning Tree for CFG ----------------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements a Union-find algorithm to compute Minimum Spanning Tree
10
// for a given CFG.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
15
#define LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/STLExtras.h"
19
#include "llvm/Analysis/BlockFrequencyInfo.h"
20
#include "llvm/Analysis/BranchProbabilityInfo.h"
21
#include "llvm/Analysis/CFG.h"
22
#include "llvm/Support/BranchProbability.h"
23
#include "llvm/Support/Debug.h"
24
#include "llvm/Support/raw_ostream.h"
25
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
26
#include <utility>
27
#include <vector>
28
29
#define DEBUG_TYPE "cfgmst"
30
31
namespace llvm {
32
33
/// An union-find based Minimum Spanning Tree for CFG
34
///
35
/// Implements a Union-find algorithm to compute Minimum Spanning Tree
36
/// for a given CFG.
37
template <class Edge, class BBInfo> class CFGMST {
38
public:
39
  Function &F;
40
41
  // Store all the edges in CFG. It may contain some stale edges
42
  // when Removed is set.
43
  std::vector<std::unique_ptr<Edge>> AllEdges;
44
45
  // This map records the auxiliary information for each BB.
46
  DenseMap<const BasicBlock *, std::unique_ptr<BBInfo>> BBInfos;
47
48
  // Whehter the function has an exit block with no successors.
49
  // (For function with an infinite loop, this block may be absent)
50
  bool ExitBlockFound = false;
51
52
  // Find the root group of the G and compress the path from G to the root.
53
3.21k
  BBInfo *findAndCompressGroup(BBInfo *G) {
54
3.21k
    if (G->Group != G)
55
987
      G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));
56
3.21k
    return static_cast<BBInfo *>(G->Group);
57
3.21k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::findAndCompressGroup((anonymous namespace)::BBInfo*)
Line
Count
Source
53
1.50k
  BBInfo *findAndCompressGroup(BBInfo *G) {
54
1.50k
    if (G->Group != G)
55
447
      G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));
56
1.50k
    return static_cast<BBInfo *>(G->Group);
57
1.50k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::findAndCompressGroup((anonymous namespace)::UseBBInfo*)
Line
Count
Source
53
1.71k
  BBInfo *findAndCompressGroup(BBInfo *G) {
54
1.71k
    if (G->Group != G)
55
540
      G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));
56
1.71k
    return static_cast<BBInfo *>(G->Group);
57
1.71k
  }
58
59
  // Union BB1 and BB2 into the same group and return true.
60
  // Returns false if BB1 and BB2 are already in the same group.
61
1.11k
  bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2) {
62
1.11k
    BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));
63
1.11k
    BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));
64
1.11k
65
1.11k
    if (BB1G == BB2G)
66
344
      return false;
67
770
68
770
    // Make the smaller rank tree a direct child or the root of high rank tree.
69
770
    if (BB1G->Rank < BB2G->Rank)
70
104
      BB1G->Group = BB2G;
71
666
    else {
72
666
      BB2G->Group = BB1G;
73
666
      // If the ranks are the same, increment root of one tree by one.
74
666
      if (BB1G->Rank == BB2G->Rank)
75
287
        BB1G->Rank++;
76
666
    }
77
770
    return true;
78
770
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::unionGroups(llvm::BasicBlock const*, llvm::BasicBlock const*)
Line
Count
Source
61
529
  bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2) {
62
529
    BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));
63
529
    BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));
64
529
65
529
    if (BB1G == BB2G)
66
163
      return false;
67
366
68
366
    // Make the smaller rank tree a direct child or the root of high rank tree.
69
366
    if (BB1G->Rank < BB2G->Rank)
70
46
      BB1G->Group = BB2G;
71
320
    else {
72
320
      BB2G->Group = BB1G;
73
320
      // If the ranks are the same, increment root of one tree by one.
74
320
      if (BB1G->Rank == BB2G->Rank)
75
141
        BB1G->Rank++;
76
320
    }
77
366
    return true;
78
366
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::unionGroups(llvm::BasicBlock const*, llvm::BasicBlock const*)
Line
Count
Source
61
585
  bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2) {
62
585
    BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));
63
585
    BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));
64
585
65
585
    if (BB1G == BB2G)
66
181
      return false;
67
404
68
404
    // Make the smaller rank tree a direct child or the root of high rank tree.
69
404
    if (BB1G->Rank < BB2G->Rank)
70
58
      BB1G->Group = BB2G;
71
346
    else {
72
346
      BB2G->Group = BB1G;
73
346
      // If the ranks are the same, increment root of one tree by one.
74
346
      if (BB1G->Rank == BB2G->Rank)
75
146
        BB1G->Rank++;
76
346
    }
77
404
    return true;
78
404
  }
79
80
  // Give BB, return the auxiliary information.
81
6.76k
  BBInfo &getBBInfo(const BasicBlock *BB) const {
82
6.76k
    auto It = BBInfos.find(BB);
83
6.76k
    assert(It->second.get() != nullptr);
84
6.76k
    return *It->second.get();
85
6.76k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::getBBInfo(llvm::BasicBlock const*) const
Line
Count
Source
81
2.26k
  BBInfo &getBBInfo(const BasicBlock *BB) const {
82
2.26k
    auto It = BBInfos.find(BB);
83
2.26k
    assert(It->second.get() != nullptr);
84
2.26k
    return *It->second.get();
85
2.26k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::getBBInfo(llvm::BasicBlock const*) const
Line
Count
Source
81
4.49k
  BBInfo &getBBInfo(const BasicBlock *BB) const {
82
4.49k
    auto It = BBInfos.find(BB);
83
4.49k
    assert(It->second.get() != nullptr);
84
4.49k
    return *It->second.get();
85
4.49k
  }
86
87
  // Give BB, return the auxiliary information if it's available.
88
2.49k
  BBInfo *findBBInfo(const BasicBlock *BB) const {
89
2.49k
    auto It = BBInfos.find(BB);
90
2.49k
    if (It == BBInfos.end())
91
0
      return nullptr;
92
2.49k
    return It->second.get();
93
2.49k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::findBBInfo(llvm::BasicBlock const*) const
Line
Count
Source
88
2.11k
  BBInfo *findBBInfo(const BasicBlock *BB) const {
89
2.11k
    auto It = BBInfos.find(BB);
90
2.11k
    if (It == BBInfos.end())
91
0
      return nullptr;
92
2.11k
    return It->second.get();
93
2.11k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::findBBInfo(llvm::BasicBlock const*) const
Line
Count
Source
88
378
  BBInfo *findBBInfo(const BasicBlock *BB) const {
89
378
    auto It = BBInfos.find(BB);
90
378
    if (It == BBInfos.end())
91
0
      return nullptr;
92
378
    return It->second.get();
93
378
  }
94
95
  // Traverse the CFG using a stack. Find all the edges and assign the weight.
96
  // Edges with large weight will be put into MST first so they are less likely
97
  // to be instrumented.
98
198
  void buildEdges() {
99
198
    LLVM_DEBUG(dbgs() << "Build Edge on " << F.getName() << "\n");
100
198
101
198
    const BasicBlock *Entry = &(F.getEntryBlock());
102
198
    uint64_t EntryWeight = (BFI != nullptr ? BFI->getEntryFreq() : 
20
);
103
198
    Edge *EntryIncoming = nullptr, *EntryOutgoing = nullptr,
104
198
        *ExitOutgoing = nullptr, *ExitIncoming = nullptr;
105
198
    uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;
106
198
107
198
    // Add a fake edge to the entry.
108
198
    EntryIncoming = &addEdge(nullptr, Entry, EntryWeight);
109
198
    LLVM_DEBUG(dbgs() << "  Edge: from fake node to " << Entry->getName()
110
198
                      << " w = " << EntryWeight << "\n");
111
198
112
198
    // Special handling for single BB functions.
113
198
    if (succ_empty(Entry)) {
114
102
      addEdge(Entry, nullptr, EntryWeight);
115
102
      return;
116
102
    }
117
96
118
96
    static const uint32_t CriticalEdgeMultiplier = 1000;
119
96
120
766
    for (Function::iterator BB = F.begin(), E = F.end(); BB != E; 
++BB670
) {
121
670
      Instruction *TI = BB->getTerminator();
122
670
      uint64_t BBWeight =
123
670
          (BFI != nullptr ? BFI->getBlockFreq(&*BB).getFrequency() : 
20
);
124
670
      uint64_t Weight = 2;
125
670
      if (int successors = TI->getNumSuccessors()) {
126
1.37k
        for (int i = 0; i != successors; 
++i809
) {
127
809
          BasicBlock *TargetBB = TI->getSuccessor(i);
128
809
          bool Critical = isCriticalEdge(TI, i);
129
809
          uint64_t scaleFactor = BBWeight;
130
809
          if (Critical) {
131
134
            if (scaleFactor < UINT64_MAX / CriticalEdgeMultiplier)
132
134
              scaleFactor *= CriticalEdgeMultiplier;
133
0
            else
134
0
              scaleFactor = UINT64_MAX;
135
134
          }
136
809
          if (BPI != nullptr)
137
809
            Weight = BPI->getEdgeProbability(&*BB, TargetBB).scale(scaleFactor);
138
809
          auto *E = &addEdge(&*BB, TargetBB, Weight);
139
809
          E->IsCritical = Critical;
140
809
          LLVM_DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to "
141
809
                            << TargetBB->getName() << "  w=" << Weight << "\n");
142
809
143
809
          // Keep track of entry/exit edges:
144
809
          if (&*BB == Entry) {
145
183
            if (Weight > MaxEntryOutWeight) {
146
128
              MaxEntryOutWeight = Weight;
147
128
              EntryOutgoing = E;
148
128
            }
149
183
          }
150
809
151
809
          auto *TargetTI = TargetBB->getTerminator();
152
809
          if (TargetTI && !TargetTI->getNumSuccessors()) {
153
190
            if (Weight > MaxExitInWeight) {
154
125
              MaxExitInWeight = Weight;
155
125
              ExitIncoming = E;
156
125
            }
157
190
          }
158
809
        }
159
561
      } else {
160
109
        ExitBlockFound = true;
161
109
        Edge *ExitO = &addEdge(&*BB, nullptr, BBWeight);
162
109
        if (BBWeight > MaxExitOutWeight) {
163
102
          MaxExitOutWeight = BBWeight;
164
102
          ExitOutgoing = ExitO;
165
102
        }
166
109
        LLVM_DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to fake exit"
167
109
                          << " w = " << BBWeight << "\n");
168
109
      }
169
670
    }
170
96
171
96
    // Entry/exit edge adjustment heurisitic:
172
96
    // prefer instrumenting entry edge over exit edge
173
96
    // if possible. Those exit edges may never have a chance to be
174
96
    // executed (for instance the program is an event handling loop)
175
96
    // before the profile is asynchronously dumped.
176
96
    //
177
96
    // If EntryIncoming and ExitOutgoing has similar weight, make sure
178
96
    // ExitOutging is selected as the min-edge. Similarly, if EntryOutgoing
179
96
    // and ExitIncoming has similar weight, make sure ExitIncoming becomes
180
96
    // the min-edge.
181
96
    uint64_t EntryInWeight = EntryWeight;
182
96
183
96
    if (EntryInWeight >= MaxExitOutWeight &&
184
96
        EntryInWeight * 2 < MaxExitOutWeight * 3) {
185
94
      EntryIncoming->Weight = MaxExitOutWeight;
186
94
      ExitOutgoing->Weight = EntryInWeight + 1;
187
94
    }
188
96
189
96
    if (MaxEntryOutWeight >= MaxExitInWeight &&
190
96
        
MaxEntryOutWeight * 2 < MaxExitInWeight * 389
) {
191
74
      EntryOutgoing->Weight = MaxExitInWeight;
192
74
      ExitIncoming->Weight = MaxEntryOutWeight + 1;
193
74
    }
194
96
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::buildEdges()
Line
Count
Source
98
101
  void buildEdges() {
99
101
    LLVM_DEBUG(dbgs() << "Build Edge on " << F.getName() << "\n");
100
101
101
101
    const BasicBlock *Entry = &(F.getEntryBlock());
102
101
    uint64_t EntryWeight = (BFI != nullptr ? BFI->getEntryFreq() : 
20
);
103
101
    Edge *EntryIncoming = nullptr, *EntryOutgoing = nullptr,
104
101
        *ExitOutgoing = nullptr, *ExitIncoming = nullptr;
105
101
    uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;
106
101
107
101
    // Add a fake edge to the entry.
108
101
    EntryIncoming = &addEdge(nullptr, Entry, EntryWeight);
109
101
    LLVM_DEBUG(dbgs() << "  Edge: from fake node to " << Entry->getName()
110
101
                      << " w = " << EntryWeight << "\n");
111
101
112
101
    // Special handling for single BB functions.
113
101
    if (succ_empty(Entry)) {
114
56
      addEdge(Entry, nullptr, EntryWeight);
115
56
      return;
116
56
    }
117
45
118
45
    static const uint32_t CriticalEdgeMultiplier = 1000;
119
45
120
357
    for (Function::iterator BB = F.begin(), E = F.end(); BB != E; 
++BB312
) {
121
312
      Instruction *TI = BB->getTerminator();
122
312
      uint64_t BBWeight =
123
312
          (BFI != nullptr ? BFI->getBlockFreq(&*BB).getFrequency() : 
20
);
124
312
      uint64_t Weight = 2;
125
312
      if (int successors = TI->getNumSuccessors()) {
126
638
        for (int i = 0; i != successors; 
++i378
) {
127
378
          BasicBlock *TargetBB = TI->getSuccessor(i);
128
378
          bool Critical = isCriticalEdge(TI, i);
129
378
          uint64_t scaleFactor = BBWeight;
130
378
          if (Critical) {
131
67
            if (scaleFactor < UINT64_MAX / CriticalEdgeMultiplier)
132
67
              scaleFactor *= CriticalEdgeMultiplier;
133
0
            else
134
0
              scaleFactor = UINT64_MAX;
135
67
          }
136
378
          if (BPI != nullptr)
137
378
            Weight = BPI->getEdgeProbability(&*BB, TargetBB).scale(scaleFactor);
138
378
          auto *E = &addEdge(&*BB, TargetBB, Weight);
139
378
          E->IsCritical = Critical;
140
378
          LLVM_DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to "
141
378
                            << TargetBB->getName() << "  w=" << Weight << "\n");
142
378
143
378
          // Keep track of entry/exit edges:
144
378
          if (&*BB == Entry) {
145
85
            if (Weight > MaxEntryOutWeight) {
146
57
              MaxEntryOutWeight = Weight;
147
57
              EntryOutgoing = E;
148
57
            }
149
85
          }
150
378
151
378
          auto *TargetTI = TargetBB->getTerminator();
152
378
          if (TargetTI && !TargetTI->getNumSuccessors()) {
153
92
            if (Weight > MaxExitInWeight) {
154
55
              MaxExitInWeight = Weight;
155
55
              ExitIncoming = E;
156
55
            }
157
92
          }
158
378
        }
159
260
      } else {
160
52
        ExitBlockFound = true;
161
52
        Edge *ExitO = &addEdge(&*BB, nullptr, BBWeight);
162
52
        if (BBWeight > MaxExitOutWeight) {
163
47
          MaxExitOutWeight = BBWeight;
164
47
          ExitOutgoing = ExitO;
165
47
        }
166
52
        LLVM_DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to fake exit"
167
52
                          << " w = " << BBWeight << "\n");
168
52
      }
169
312
    }
170
45
171
45
    // Entry/exit edge adjustment heurisitic:
172
45
    // prefer instrumenting entry edge over exit edge
173
45
    // if possible. Those exit edges may never have a chance to be
174
45
    // executed (for instance the program is an event handling loop)
175
45
    // before the profile is asynchronously dumped.
176
45
    //
177
45
    // If EntryIncoming and ExitOutgoing has similar weight, make sure
178
45
    // ExitOutging is selected as the min-edge. Similarly, if EntryOutgoing
179
45
    // and ExitIncoming has similar weight, make sure ExitIncoming becomes
180
45
    // the min-edge.
181
45
    uint64_t EntryInWeight = EntryWeight;
182
45
183
45
    if (EntryInWeight >= MaxExitOutWeight &&
184
45
        EntryInWeight * 2 < MaxExitOutWeight * 3) {
185
43
      EntryIncoming->Weight = MaxExitOutWeight;
186
43
      ExitOutgoing->Weight = EntryInWeight + 1;
187
43
    }
188
45
189
45
    if (MaxEntryOutWeight >= MaxExitInWeight &&
190
45
        MaxEntryOutWeight * 2 < MaxExitInWeight * 3) {
191
37
      EntryOutgoing->Weight = MaxExitInWeight;
192
37
      ExitIncoming->Weight = MaxEntryOutWeight + 1;
193
37
    }
194
45
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::buildEdges()
Line
Count
Source
98
97
  void buildEdges() {
99
97
    LLVM_DEBUG(dbgs() << "Build Edge on " << F.getName() << "\n");
100
97
101
97
    const BasicBlock *Entry = &(F.getEntryBlock());
102
97
    uint64_t EntryWeight = (BFI != nullptr ? BFI->getEntryFreq() : 
20
);
103
97
    Edge *EntryIncoming = nullptr, *EntryOutgoing = nullptr,
104
97
        *ExitOutgoing = nullptr, *ExitIncoming = nullptr;
105
97
    uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;
106
97
107
97
    // Add a fake edge to the entry.
108
97
    EntryIncoming = &addEdge(nullptr, Entry, EntryWeight);
109
97
    LLVM_DEBUG(dbgs() << "  Edge: from fake node to " << Entry->getName()
110
97
                      << " w = " << EntryWeight << "\n");
111
97
112
97
    // Special handling for single BB functions.
113
97
    if (succ_empty(Entry)) {
114
46
      addEdge(Entry, nullptr, EntryWeight);
115
46
      return;
116
46
    }
117
51
118
51
    static const uint32_t CriticalEdgeMultiplier = 1000;
119
51
120
409
    for (Function::iterator BB = F.begin(), E = F.end(); BB != E; 
++BB358
) {
121
358
      Instruction *TI = BB->getTerminator();
122
358
      uint64_t BBWeight =
123
358
          (BFI != nullptr ? BFI->getBlockFreq(&*BB).getFrequency() : 
20
);
124
358
      uint64_t Weight = 2;
125
358
      if (int successors = TI->getNumSuccessors()) {
126
732
        for (int i = 0; i != successors; 
++i431
) {
127
431
          BasicBlock *TargetBB = TI->getSuccessor(i);
128
431
          bool Critical = isCriticalEdge(TI, i);
129
431
          uint64_t scaleFactor = BBWeight;
130
431
          if (Critical) {
131
67
            if (scaleFactor < UINT64_MAX / CriticalEdgeMultiplier)
132
67
              scaleFactor *= CriticalEdgeMultiplier;
133
0
            else
134
0
              scaleFactor = UINT64_MAX;
135
67
          }
136
431
          if (BPI != nullptr)
137
431
            Weight = BPI->getEdgeProbability(&*BB, TargetBB).scale(scaleFactor);
138
431
          auto *E = &addEdge(&*BB, TargetBB, Weight);
139
431
          E->IsCritical = Critical;
140
431
          LLVM_DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to "
141
431
                            << TargetBB->getName() << "  w=" << Weight << "\n");
142
431
143
431
          // Keep track of entry/exit edges:
144
431
          if (&*BB == Entry) {
145
98
            if (Weight > MaxEntryOutWeight) {
146
71
              MaxEntryOutWeight = Weight;
147
71
              EntryOutgoing = E;
148
71
            }
149
98
          }
150
431
151
431
          auto *TargetTI = TargetBB->getTerminator();
152
431
          if (TargetTI && !TargetTI->getNumSuccessors()) {
153
98
            if (Weight > MaxExitInWeight) {
154
70
              MaxExitInWeight = Weight;
155
70
              ExitIncoming = E;
156
70
            }
157
98
          }
158
431
        }
159
301
      } else {
160
57
        ExitBlockFound = true;
161
57
        Edge *ExitO = &addEdge(&*BB, nullptr, BBWeight);
162
57
        if (BBWeight > MaxExitOutWeight) {
163
55
          MaxExitOutWeight = BBWeight;
164
55
          ExitOutgoing = ExitO;
165
55
        }
166
57
        LLVM_DEBUG(dbgs() << "  Edge: from " << BB->getName() << " to fake exit"
167
57
                          << " w = " << BBWeight << "\n");
168
57
      }
169
358
    }
170
51
171
51
    // Entry/exit edge adjustment heurisitic:
172
51
    // prefer instrumenting entry edge over exit edge
173
51
    // if possible. Those exit edges may never have a chance to be
174
51
    // executed (for instance the program is an event handling loop)
175
51
    // before the profile is asynchronously dumped.
176
51
    //
177
51
    // If EntryIncoming and ExitOutgoing has similar weight, make sure
178
51
    // ExitOutging is selected as the min-edge. Similarly, if EntryOutgoing
179
51
    // and ExitIncoming has similar weight, make sure ExitIncoming becomes
180
51
    // the min-edge.
181
51
    uint64_t EntryInWeight = EntryWeight;
182
51
183
51
    if (EntryInWeight >= MaxExitOutWeight &&
184
51
        EntryInWeight * 2 < MaxExitOutWeight * 3) {
185
51
      EntryIncoming->Weight = MaxExitOutWeight;
186
51
      ExitOutgoing->Weight = EntryInWeight + 1;
187
51
    }
188
51
189
51
    if (MaxEntryOutWeight >= MaxExitInWeight &&
190
51
        
MaxEntryOutWeight * 2 < MaxExitInWeight * 344
) {
191
37
      EntryOutgoing->Weight = MaxExitInWeight;
192
37
      ExitIncoming->Weight = MaxEntryOutWeight + 1;
193
37
    }
194
51
  }
195
196
  // Sort CFG edges based on its weight.
197
198
  void sortEdgesByWeight() {
198
198
    llvm::stable_sort(AllEdges, [](const std::unique_ptr<Edge> &Edge1,
199
2.57k
                                   const std::unique_ptr<Edge> &Edge2) {
200
2.57k
      return Edge1->Weight > Edge2->Weight;
201
2.57k
    });
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::sortEdgesByWeight()::'lambda'(std::__1::unique_ptr<(anonymous namespace)::PGOEdge, std::__1::default_delete<(anonymous namespace)::PGOEdge> > const&, std::__1::unique_ptr<(anonymous namespace)::PGOEdge, std::__1::default_delete<(anonymous namespace)::PGOEdge> > const&)::operator()(std::__1::unique_ptr<(anonymous namespace)::PGOEdge, std::__1::default_delete<(anonymous namespace)::PGOEdge> > const&, std::__1::unique_ptr<(anonymous namespace)::PGOEdge, std::__1::default_delete<(anonymous namespace)::PGOEdge> > const&) const
Line
Count
Source
199
1.19k
                                   const std::unique_ptr<Edge> &Edge2) {
200
1.19k
      return Edge1->Weight > Edge2->Weight;
201
1.19k
    });
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::sortEdgesByWeight()::'lambda'(std::__1::unique_ptr<(anonymous namespace)::PGOUseEdge, std::__1::default_delete<(anonymous namespace)::PGOUseEdge> > const&, std::__1::unique_ptr<(anonymous namespace)::PGOUseEdge, std::__1::default_delete<(anonymous namespace)::PGOUseEdge> > const&)::operator()(std::__1::unique_ptr<(anonymous namespace)::PGOUseEdge, std::__1::default_delete<(anonymous namespace)::PGOUseEdge> > const&, std::__1::unique_ptr<(anonymous namespace)::PGOUseEdge, std::__1::default_delete<(anonymous namespace)::PGOUseEdge> > const&) const
Line
Count
Source
199
1.37k
                                   const std::unique_ptr<Edge> &Edge2) {
200
1.37k
      return Edge1->Weight > Edge2->Weight;
201
1.37k
    });
202
198
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::sortEdgesByWeight()
Line
Count
Source
197
101
  void sortEdgesByWeight() {
198
101
    llvm::stable_sort(AllEdges, [](const std::unique_ptr<Edge> &Edge1,
199
101
                                   const std::unique_ptr<Edge> &Edge2) {
200
101
      return Edge1->Weight > Edge2->Weight;
201
101
    });
202
101
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::sortEdgesByWeight()
Line
Count
Source
197
97
  void sortEdgesByWeight() {
198
97
    llvm::stable_sort(AllEdges, [](const std::unique_ptr<Edge> &Edge1,
199
97
                                   const std::unique_ptr<Edge> &Edge2) {
200
97
      return Edge1->Weight > Edge2->Weight;
201
97
    });
202
97
  }
203
204
  // Traverse all the edges and compute the Minimum Weight Spanning Tree
205
  // using union-find algorithm.
206
198
  void computeMinimumSpanningTree() {
207
198
    // First, put all the critical edge with landing-pad as the Dest to MST.
208
198
    // This works around the insufficient support of critical edges split
209
198
    // when destination BB is a landing pad.
210
1.21k
    for (auto &Ei : AllEdges) {
211
1.21k
      if (Ei->Removed)
212
0
        continue;
213
1.21k
      if (Ei->IsCritical) {
214
134
        if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
215
0
          if (unionGroups(Ei->SrcBB, Ei->DestBB))
216
0
            Ei->InMST = true;
217
0
        }
218
134
      }
219
1.21k
    }
220
198
221
1.21k
    for (auto &Ei : AllEdges) {
222
1.21k
      if (Ei->Removed)
223
0
        continue;
224
1.21k
      // If we detect infinite loops, force
225
1.21k
      // instrumenting the entry edge:
226
1.21k
      if (!ExitBlockFound && 
Ei->SrcBB == nullptr218
)
227
104
        continue;
228
1.11k
      if (unionGroups(Ei->SrcBB, Ei->DestBB))
229
770
        Ei->InMST = true;
230
1.11k
    }
231
198
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::computeMinimumSpanningTree()
Line
Count
Source
206
101
  void computeMinimumSpanningTree() {
207
101
    // First, put all the critical edge with landing-pad as the Dest to MST.
208
101
    // This works around the insufficient support of critical edges split
209
101
    // when destination BB is a landing pad.
210
587
    for (auto &Ei : AllEdges) {
211
587
      if (Ei->Removed)
212
0
        continue;
213
587
      if (Ei->IsCritical) {
214
67
        if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
215
0
          if (unionGroups(Ei->SrcBB, Ei->DestBB))
216
0
            Ei->InMST = true;
217
0
        }
218
67
      }
219
587
    }
220
101
221
587
    for (auto &Ei : AllEdges) {
222
587
      if (Ei->Removed)
223
0
        continue;
224
587
      // If we detect infinite loops, force
225
587
      // instrumenting the entry edge:
226
587
      if (!ExitBlockFound && 
Ei->SrcBB == nullptr126
)
227
58
        continue;
228
529
      if (unionGroups(Ei->SrcBB, Ei->DestBB))
229
366
        Ei->InMST = true;
230
529
    }
231
101
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::computeMinimumSpanningTree()
Line
Count
Source
206
97
  void computeMinimumSpanningTree() {
207
97
    // First, put all the critical edge with landing-pad as the Dest to MST.
208
97
    // This works around the insufficient support of critical edges split
209
97
    // when destination BB is a landing pad.
210
631
    for (auto &Ei : AllEdges) {
211
631
      if (Ei->Removed)
212
0
        continue;
213
631
      if (Ei->IsCritical) {
214
67
        if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
215
0
          if (unionGroups(Ei->SrcBB, Ei->DestBB))
216
0
            Ei->InMST = true;
217
0
        }
218
67
      }
219
631
    }
220
97
221
631
    for (auto &Ei : AllEdges) {
222
631
      if (Ei->Removed)
223
0
        continue;
224
631
      // If we detect infinite loops, force
225
631
      // instrumenting the entry edge:
226
631
      if (!ExitBlockFound && 
Ei->SrcBB == nullptr92
)
227
46
        continue;
228
585
      if (unionGroups(Ei->SrcBB, Ei->DestBB))
229
404
        Ei->InMST = true;
230
585
    }
231
97
  }
232
233
  // Dump the Debug information about the instrumentation.
234
0
  void dumpEdges(raw_ostream &OS, const Twine &Message) const {
235
0
    if (!Message.str().empty())
236
0
      OS << Message << "\n";
237
0
    OS << "  Number of Basic Blocks: " << BBInfos.size() << "\n";
238
0
    for (auto &BI : BBInfos) {
239
0
      const BasicBlock *BB = BI.first;
240
0
      OS << "  BB: " << (BB == nullptr ? "FakeNode" : BB->getName()) << "  "
241
0
         << BI.second->infoString() << "\n";
242
0
    }
243
0
244
0
    OS << "  Number of Edges: " << AllEdges.size()
245
0
       << " (*: Instrument, C: CriticalEdge, -: Removed)\n";
246
0
    uint32_t Count = 0;
247
0
    for (auto &EI : AllEdges)
248
0
      OS << "  Edge " << Count++ << ": " << getBBInfo(EI->SrcBB).Index << "-->"
249
0
         << getBBInfo(EI->DestBB).Index << EI->infoString() << "\n";
250
0
  }
251
252
  // Add an edge to AllEdges with weight W.
253
1.26k
  Edge &addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W) {
254
1.26k
    uint32_t Index = BBInfos.size();
255
1.26k
    auto Iter = BBInfos.end();
256
1.26k
    bool Inserted;
257
1.26k
    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Src, nullptr));
258
1.26k
    if (Inserted) {
259
218
      // Newly inserted, update the real info.
260
218
      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
261
218
      Index++;
262
218
    }
263
1.26k
    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Dest, nullptr));
264
1.26k
    if (Inserted)
265
774
      // Newly inserted, update the real info.
266
774
      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
267
1.26k
    AllEdges.emplace_back(new Edge(Src, Dest, W));
268
1.26k
    return *AllEdges.back();
269
1.26k
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::addEdge(llvm::BasicBlock const*, llvm::BasicBlock const*, unsigned long long)
Line
Count
Source
253
623
  Edge &addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W) {
254
623
    uint32_t Index = BBInfos.size();
255
623
    auto Iter = BBInfos.end();
256
623
    bool Inserted;
257
623
    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Src, nullptr));
258
623
    if (Inserted) {
259
111
      // Newly inserted, update the real info.
260
111
      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
261
111
      Index++;
262
111
    }
263
623
    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Dest, nullptr));
264
623
    if (Inserted)
265
376
      // Newly inserted, update the real info.
266
376
      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
267
623
    AllEdges.emplace_back(new Edge(Src, Dest, W));
268
623
    return *AllEdges.back();
269
623
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::addEdge(llvm::BasicBlock const*, llvm::BasicBlock const*, unsigned long long)
Line
Count
Source
253
639
  Edge &addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W) {
254
639
    uint32_t Index = BBInfos.size();
255
639
    auto Iter = BBInfos.end();
256
639
    bool Inserted;
257
639
    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Src, nullptr));
258
639
    if (Inserted) {
259
107
      // Newly inserted, update the real info.
260
107
      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
261
107
      Index++;
262
107
    }
263
639
    std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Dest, nullptr));
264
639
    if (Inserted)
265
398
      // Newly inserted, update the real info.
266
398
      Iter->second = std::move(llvm::make_unique<BBInfo>(Index));
267
639
    AllEdges.emplace_back(new Edge(Src, Dest, W));
268
639
    return *AllEdges.back();
269
639
  }
270
271
  BranchProbabilityInfo *BPI;
272
  BlockFrequencyInfo *BFI;
273
274
public:
275
  CFGMST(Function &Func, BranchProbabilityInfo *BPI_ = nullptr,
276
         BlockFrequencyInfo *BFI_ = nullptr)
277
198
      : F(Func), BPI(BPI_), BFI(BFI_) {
278
198
    buildEdges();
279
198
    sortEdgesByWeight();
280
198
    computeMinimumSpanningTree();
281
198
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOEdge, (anonymous namespace)::BBInfo>::CFGMST(llvm::Function&, llvm::BranchProbabilityInfo*, llvm::BlockFrequencyInfo*)
Line
Count
Source
277
101
      : F(Func), BPI(BPI_), BFI(BFI_) {
278
101
    buildEdges();
279
101
    sortEdgesByWeight();
280
101
    computeMinimumSpanningTree();
281
101
  }
PGOInstrumentation.cpp:llvm::CFGMST<(anonymous namespace)::PGOUseEdge, (anonymous namespace)::UseBBInfo>::CFGMST(llvm::Function&, llvm::BranchProbabilityInfo*, llvm::BlockFrequencyInfo*)
Line
Count
Source
277
97
      : F(Func), BPI(BPI_), BFI(BFI_) {
278
97
    buildEdges();
279
97
    sortEdgesByWeight();
280
97
    computeMinimumSpanningTree();
281
97
  }
282
};
283
284
} // end namespace llvm
285
286
#undef DEBUG_TYPE // "cfgmst"
287
288
#endif // LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H