CFGMST.h Source File (original) (raw)

40template <class Edge, class BBInfo> class CFGMST {

45 std::vector<std::unique_ptr> AllEdges;

52 bool ExitBlockFound = false;

59 const bool InstrumentFuncEntry;

62 const bool InstrumentLoopEntries;

65 BBInfo *findAndCompressGroup(BBInfo *G) {

66 if (G->Group != G)

67 G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));

68 return static_cast<BBInfo *>(G->Group);

69 }

74 BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));

75 BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));

77 if (BB1G == BB2G)

78 return false;

81 if (BB1G->Rank < BB2G->Rank)

82 BB1G->Group = BB2G;

83 else {

84 BB2G->Group = BB1G;

86 if (BB1G->Rank == BB2G->Rank)

87 BB1G->Rank++;

88 }

89 return true;

90 }

92 void handleCoroSuspendEdge(Edge *E) {

100

101

102

103

104

105

106

107

108 if (->DestBB)

109 return;

112 E->Removed = true;

113 }

114

115

116

117

118 void buildEdges() {

119 LLVM_DEBUG(dbgs() << "Build Edge on " << F.getName() << "\n");

120

121 BasicBlock *Entry = &(F.getEntryBlock());

123 (BFI != nullptr ? BFI->getEntryFreq().getFrequency() : 2);

124

125 if (InstrumentFuncEntry)

126 EntryWeight = 0;

127 Edge *EntryIncoming = nullptr, *EntryOutgoing = nullptr,

128 *ExitOutgoing = nullptr, *ExitIncoming = nullptr;

129 uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;

130

131

132 EntryIncoming = &addEdge(nullptr, Entry, EntryWeight);

133 LLVM_DEBUG(dbgs() << " Edge: from fake node to " << Entry->getName()

134 << " w = " << EntryWeight << "\n");

135

136

138 addEdge(Entry, nullptr, EntryWeight);

139 return;

140 }

141

142 static const uint32_t CriticalEdgeMultiplier = 1000;

143

147 (BFI != nullptr ? BFI->getBlockFreq(&BB).getFrequency() : 2);

150 for (int i = 0; i != successors; ++i) {

153 uint64_t scaleFactor = BBWeight;

154 if (Critical) {

155 if (scaleFactor < UINT64_MAX / CriticalEdgeMultiplier)

156 scaleFactor *= CriticalEdgeMultiplier;

157 else

159 }

160 if (BPI != nullptr)

161 Weight = BPI->getEdgeProbability(&BB, TargetBB).scale(scaleFactor);

162

163

164

165

166 if (InstrumentLoopEntries && LI->isLoopHeader(TargetBB)) {

167 Loop *TargetLoop = LI->getLoopFor(TargetBB);

169 if (!TargetLoop->contains(&BB))

170 Weight = 0;

171 }

172 if (Weight == 0)

173 Weight++;

174 auto *E = &addEdge(&BB, TargetBB, Weight);

175 E->IsCritical = Critical;

176 handleCoroSuspendEdge(E);

177 LLVM_DEBUG(dbgs() << " Edge: from " << BB.getName() << " to "

178 << TargetBB->getName() << " w=" << Weight << "\n");

179

180

181 if (&BB == Entry) {

182 if (Weight > MaxEntryOutWeight) {

183 MaxEntryOutWeight = Weight;

184 EntryOutgoing = E;

185 }

186 }

187

189 if (TargetTI && !TargetTI->getNumSuccessors()) {

190 if (Weight > MaxExitInWeight) {

191 MaxExitInWeight = Weight;

192 ExitIncoming = E;

193 }

194 }

195 }

196 } else {

197 ExitBlockFound = true;

198 Edge *ExitO = &addEdge(&BB, nullptr, BBWeight);

199 if (BBWeight > MaxExitOutWeight) {

200 MaxExitOutWeight = BBWeight;

201 ExitOutgoing = ExitO;

202 }

203 LLVM_DEBUG(dbgs() << " Edge: from " << BB.getName() << " to fake exit"

204 << " w = " << BBWeight << "\n");

205 }

206 }

207

208

209

210

211

212

213

214

215

216

217

218 uint64_t EntryInWeight = EntryWeight;

219

220 if (EntryInWeight >= MaxExitOutWeight &&

221 EntryInWeight * 2 < MaxExitOutWeight * 3) {

222 EntryIncoming->Weight = MaxExitOutWeight;

223 ExitOutgoing->Weight = EntryInWeight + 1;

224 }

225

226 if (MaxEntryOutWeight >= MaxExitInWeight &&

227 MaxEntryOutWeight * 2 < MaxExitInWeight * 3) {

228 EntryOutgoing->Weight = MaxExitInWeight;

229 ExitIncoming->Weight = MaxEntryOutWeight + 1;

230 }

231 }

232

233

234 void sortEdgesByWeight() {

235 llvm::stable_sort(AllEdges, [](const std::unique_ptr &Edge1,

236 const std::unique_ptr &Edge2) {

237 return Edge1->Weight > Edge2->Weight;

238 });

239 }

240

241

242

243 void computeMinimumSpanningTree() {

244

245

246

247 for (auto &Ei : AllEdges) {

248 if (Ei->Removed)

249 continue;

250 if (Ei->IsCritical) {

251 if (Ei->DestBB && Ei->DestBB->isLandingPad()) {

252 if (unionGroups(Ei->SrcBB, Ei->DestBB))

253 Ei->InMST = true;

254 }

255 }

256 }

257

258 for (auto &Ei : AllEdges) {

259 if (Ei->Removed)

260 continue;

261

262

263 if (!ExitBlockFound && Ei->SrcBB == nullptr)

264 continue;

265 if (unionGroups(Ei->SrcBB, Ei->DestBB))

266 Ei->InMST = true;

267 }

268 }

269

270 [[maybe_unused]] bool validateLoopEntryInstrumentation() {

271 if (!InstrumentLoopEntries)

272 return true;

273 for (auto &Ei : AllEdges) {

274 if (Ei->Removed)

275 continue;

276 if (Ei->DestBB && LI->isLoopHeader(Ei->DestBB) &&

277 !LI->getLoopFor(Ei->DestBB)->contains(Ei->SrcBB) && Ei->InMST)

278 return false;

279 }

280 return true;

281 }

282

283public:

284

286 if (!Message.str().empty())

287 OS << Message << "\n";

288 OS << " Number of Basic Blocks: " << BBInfos.size() << "\n";

289 for (auto &BI : BBInfos) {

291 OS << " BB: " << (BB == nullptr ? "FakeNode" : BB->getName()) << " "

292 << BI.second->infoString() << "\n";

293 }

294

295 OS << " Number of Edges: " << AllEdges.size()

296 << " (*: Instrument, C: CriticalEdge, -: Removed)\n";

298 for (auto &EI : AllEdges)

299 OS << " Edge " << Count++ << ": " << getBBInfo(EI->SrcBB).Index << "-->"

300 << getBBInfo(EI->DestBB).Index << EI->infoString() << "\n";

301 }

302

303

305 uint32_t Index = BBInfos.size();

306 auto Iter = BBInfos.end();

307 bool Inserted;

308 std::tie(Iter, Inserted) = BBInfos.try_emplace(Src);

309 if (Inserted) {

310

311 Iter->second = std::make_unique(Index);

312 Index++;

313 }

314 std::tie(Iter, Inserted) = BBInfos.try_emplace(Dest);

315 if (Inserted)

316

317 Iter->second = std::make_unique(Index);

318 AllEdges.emplace_back(new Edge(Src, Dest, W));

319 return *AllEdges.back();

320 }

321

322 CFGMST(Function &Func, bool InstrumentFuncEntry, bool InstrumentLoopEntries,

325 : F(Func), BPI(BPI), BFI(BFI), LI(LI),

326 InstrumentFuncEntry(InstrumentFuncEntry),

327 InstrumentLoopEntries(InstrumentLoopEntries) {

328 assert(!(InstrumentLoopEntries && !LI) &&

329 "expected a LoopInfo to instrumenting loop entries");

330 buildEdges();

331 sortEdgesByWeight();

332 computeMinimumSpanningTree();

333 assert(validateLoopEntryInstrumentation() &&

334 "Loop entries should not be in MST when "

335 "InstrumentLoopEntries is on");

336 if (AllEdges.size() > 1 && InstrumentFuncEntry)

337 std::iter_swap(std::move(AllEdges.begin()),

338 std::move(AllEdges.begin() + AllEdges.size() - 1));

339 }

340

341 const std::vector<std::unique_ptr> &allEdges() const {

342 return AllEdges;

343 }

344

345 std::vector<std::unique_ptr> &allEdges() { return AllEdges; }

346

347 size_t numEdges() const { return AllEdges.size(); }

348

349 size_t bbInfoSize() const { return BBInfos.size(); }

350

351

353 auto It = BBInfos.find(BB);

354 assert(It->second.get() != nullptr);

355 return *It->second.get();

356 }

357

358

360 auto It = BBInfos.find(BB);

361 if (It == BBInfos.end())

362 return nullptr;

363 return It->second.get();

364 }

365};