1218885Sdim//===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file provides the implementation of the EdgeBundles analysis. 11218885Sdim// 12218885Sdim//===----------------------------------------------------------------------===// 13218885Sdim 14218885Sdim#include "llvm/CodeGen/EdgeBundles.h" 15218885Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 16218885Sdim#include "llvm/CodeGen/MachineFunction.h" 17218885Sdim#include "llvm/CodeGen/Passes.h" 18218885Sdim#include "llvm/Support/CommandLine.h" 19218885Sdim#include "llvm/Support/GraphWriter.h" 20218885Sdim 21218885Sdimusing namespace llvm; 22218885Sdim 23218885Sdimstatic cl::opt<bool> 24218885SdimViewEdgeBundles("view-edge-bundles", cl::Hidden, 25218885Sdim cl::desc("Pop up a window to show edge bundle graphs")); 26218885Sdim 27218885Sdimchar EdgeBundles::ID = 0; 28218885Sdim 29218885SdimINITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges", 30218885Sdim /* cfg = */true, /* analysis = */ true) 31218885Sdim 32218885Sdimchar &llvm::EdgeBundlesID = EdgeBundles::ID; 33218885Sdim 34218885Sdimvoid EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const { 35218885Sdim AU.setPreservesAll(); 36218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 37218885Sdim} 38218885Sdim 39218885Sdimbool EdgeBundles::runOnMachineFunction(MachineFunction &mf) { 40218885Sdim MF = &mf; 41218885Sdim EC.clear(); 42224145Sdim EC.grow(2 * MF->getNumBlockIDs()); 43218885Sdim 44218885Sdim for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E; 45218885Sdim ++I) { 46218885Sdim const MachineBasicBlock &MBB = *I; 47218885Sdim unsigned OutE = 2 * MBB.getNumber() + 1; 48218885Sdim // Join the outgoing bundle with the ingoing bundles of all successors. 49218885Sdim for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 50218885Sdim SE = MBB.succ_end(); SI != SE; ++SI) 51218885Sdim EC.join(OutE, 2 * (*SI)->getNumber()); 52218885Sdim } 53218885Sdim EC.compress(); 54218885Sdim if (ViewEdgeBundles) 55218885Sdim view(); 56221345Sdim 57221345Sdim // Compute the reverse mapping. 58221345Sdim Blocks.clear(); 59221345Sdim Blocks.resize(getNumBundles()); 60221345Sdim 61221345Sdim for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) { 62221345Sdim unsigned b0 = getBundle(i, 0); 63221345Sdim unsigned b1 = getBundle(i, 1); 64221345Sdim Blocks[b0].push_back(i); 65221345Sdim if (b1 != b0) 66221345Sdim Blocks[b1].push_back(i); 67221345Sdim } 68221345Sdim 69218885Sdim return false; 70218885Sdim} 71218885Sdim 72218885Sdim/// view - Visualize the annotated bipartite CFG with Graphviz. 73218885Sdimvoid EdgeBundles::view() const { 74218885Sdim ViewGraph(*this, "EdgeBundles"); 75218885Sdim} 76218885Sdim 77218885Sdim/// Specialize WriteGraph, the standard implementation won't work. 78218885Sdimraw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G, 79218885Sdim bool ShortNames, 80234353Sdim const Twine &Title) { 81218885Sdim const MachineFunction *MF = G.getMachineFunction(); 82218885Sdim 83218885Sdim O << "digraph {\n"; 84218885Sdim for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); 85218885Sdim I != E; ++I) { 86218885Sdim unsigned BB = I->getNumber(); 87218885Sdim O << "\t\"BB#" << BB << "\" [ shape=box ]\n" 88218885Sdim << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n" 89218885Sdim << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n'; 90218885Sdim for (MachineBasicBlock::const_succ_iterator SI = I->succ_begin(), 91218885Sdim SE = I->succ_end(); SI != SE; ++SI) 92218885Sdim O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber() 93218885Sdim << "\" [ color=lightgray ]\n"; 94218885Sdim } 95218885Sdim O << "}\n"; 96218885Sdim return O; 97218885Sdim} 98