1 //===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===// 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 provides the implementation of the EdgeBundles analysis. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/EdgeBundles.h" 14 #include "llvm/ADT/Twine.h" 15 #include "llvm/CodeGen/MachineBasicBlock.h" 16 #include "llvm/CodeGen/MachineFunction.h" 17 #include "llvm/CodeGen/Passes.h" 18 #include "llvm/InitializePasses.h" 19 #include "llvm/Support/CommandLine.h" 20 #include "llvm/Support/GraphWriter.h" 21 #include "llvm/Support/raw_ostream.h" 22 23 using namespace llvm; 24 25 static cl::opt<bool> 26 ViewEdgeBundles("view-edge-bundles", cl::Hidden, 27 cl::desc("Pop up a window to show edge bundle graphs")); 28 29 char EdgeBundles::ID = 0; 30 31 INITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges", 32 /* cfg = */true, /* is_analysis = */ true) 33 34 char &llvm::EdgeBundlesID = EdgeBundles::ID; 35 36 void EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const { 37 AU.setPreservesAll(); 38 MachineFunctionPass::getAnalysisUsage(AU); 39 } 40 41 bool EdgeBundles::runOnMachineFunction(MachineFunction &mf) { 42 MF = &mf; 43 EC.clear(); 44 EC.grow(2 * MF->getNumBlockIDs()); 45 46 for (const auto &MBB : *MF) { 47 unsigned OutE = 2 * MBB.getNumber() + 1; 48 // Join the outgoing bundle with the ingoing bundles of all successors. 49 for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 50 SE = MBB.succ_end(); SI != SE; ++SI) 51 EC.join(OutE, 2 * (*SI)->getNumber()); 52 } 53 EC.compress(); 54 if (ViewEdgeBundles) 55 view(); 56 57 // Compute the reverse mapping. 58 Blocks.clear(); 59 Blocks.resize(getNumBundles()); 60 61 for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) { 62 unsigned b0 = getBundle(i, false); 63 unsigned b1 = getBundle(i, true); 64 Blocks[b0].push_back(i); 65 if (b1 != b0) 66 Blocks[b1].push_back(i); 67 } 68 69 return false; 70 } 71 72 /// Specialize WriteGraph, the standard implementation won't work. 73 namespace llvm { 74 75 template<> 76 raw_ostream &WriteGraph<>(raw_ostream &O, const EdgeBundles &G, 77 bool ShortNames, 78 const Twine &Title) { 79 const MachineFunction *MF = G.getMachineFunction(); 80 81 O << "digraph {\n"; 82 for (const auto &MBB : *MF) { 83 unsigned BB = MBB.getNumber(); 84 O << "\t\"" << printMBBReference(MBB) << "\" [ shape=box ]\n" 85 << '\t' << G.getBundle(BB, false) << " -> \"" << printMBBReference(MBB) 86 << "\"\n" 87 << "\t\"" << printMBBReference(MBB) << "\" -> " << G.getBundle(BB, true) 88 << '\n'; 89 for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 90 SE = MBB.succ_end(); SI != SE; ++SI) 91 O << "\t\"" << printMBBReference(MBB) << "\" -> \"" 92 << printMBBReference(**SI) << "\" [ color=lightgray ]\n"; 93 } 94 O << "}\n"; 95 return O; 96 } 97 98 } // end namespace llvm 99 100 /// view - Visualize the annotated bipartite CFG with Graphviz. 101 void EdgeBundles::view() const { 102 ViewGraph(*this, "EdgeBundles"); 103 } 104