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