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 EdgeBundlesWrapperLegacy::ID = 0; 30 31 INITIALIZE_PASS(EdgeBundlesWrapperLegacy, "edge-bundles", 32 "Bundle Machine CFG Edges", 33 /* cfg = */ true, /* is_analysis = */ true) 34 35 char &llvm::EdgeBundlesWrapperLegacyID = EdgeBundlesWrapperLegacy::ID; 36 37 void EdgeBundlesWrapperLegacy::getAnalysisUsage(AnalysisUsage &AU) const { 38 AU.setPreservesAll(); 39 MachineFunctionPass::getAnalysisUsage(AU); 40 } 41 42 AnalysisKey EdgeBundlesAnalysis::Key; 43 44 EdgeBundles EdgeBundlesAnalysis::run(MachineFunction &MF, 45 MachineFunctionAnalysisManager &MFAM) { 46 EdgeBundles Impl(MF); 47 return Impl; 48 } 49 50 bool EdgeBundlesWrapperLegacy::runOnMachineFunction(MachineFunction &MF) { 51 Impl.reset(new EdgeBundles(MF)); 52 return false; 53 } 54 55 EdgeBundles::EdgeBundles(MachineFunction &MF) : MF(&MF) { init(); } 56 57 void EdgeBundles::init() { 58 EC.clear(); 59 EC.grow(2 * MF->getNumBlockIDs()); 60 61 for (const auto &MBB : *MF) { 62 unsigned OutE = 2 * MBB.getNumber() + 1; 63 // Join the outgoing bundle with the ingoing bundles of all successors. 64 for (const MachineBasicBlock *Succ : MBB.successors()) 65 EC.join(OutE, 2 * Succ->getNumber()); 66 } 67 EC.compress(); 68 if (ViewEdgeBundles) 69 view(); 70 71 // Compute the reverse mapping. 72 Blocks.clear(); 73 Blocks.resize(getNumBundles()); 74 75 for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) { 76 unsigned b0 = getBundle(i, false); 77 unsigned b1 = getBundle(i, true); 78 Blocks[b0].push_back(i); 79 if (b1 != b0) 80 Blocks[b1].push_back(i); 81 } 82 } 83 84 namespace llvm { 85 86 /// Specialize WriteGraph, the standard implementation won't work. 87 template<> 88 raw_ostream &WriteGraph<>(raw_ostream &O, const EdgeBundles &G, 89 bool ShortNames, 90 const Twine &Title) { 91 const MachineFunction *MF = G.getMachineFunction(); 92 93 O << "digraph {\n"; 94 for (const auto &MBB : *MF) { 95 unsigned BB = MBB.getNumber(); 96 O << "\t\"" << printMBBReference(MBB) << "\" [ shape=box, label=\"" 97 << printMBBReference(MBB) << "\" ]\n" 98 << '\t' << G.getBundle(BB, false) << " -> \"" << printMBBReference(MBB) 99 << "\"\n" 100 << "\t\"" << printMBBReference(MBB) << "\" -> " << G.getBundle(BB, true) 101 << '\n'; 102 for (const MachineBasicBlock *Succ : MBB.successors()) 103 O << "\t\"" << printMBBReference(MBB) << "\" -> \"" 104 << printMBBReference(*Succ) << "\" [ color=lightgray ]\n"; 105 } 106 O << "}\n"; 107 return O; 108 } 109 110 } // end namespace llvm 111 112 /// view - Visualize the annotated bipartite CFG with Graphviz. 113 void EdgeBundles::view() const { 114 ViewGraph(*this, "EdgeBundles"); 115 } 116 117 bool EdgeBundles::invalidate(MachineFunction &MF, const PreservedAnalyses &PA, 118 MachineFunctionAnalysisManager::Invalidator &Inv) { 119 // Invalidated when CFG is not preserved 120 auto PAC = PA.getChecker<EdgeBundlesAnalysis>(); 121 return !PAC.preserved() && !PAC.preservedSet<CFGAnalyses>() && 122 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>(); 123 } 124