119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file provides the implementation of the EdgeBundles analysis. 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/EdgeBundles.h" 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineBasicBlock.h" 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFunction.h" 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/Passes.h" 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/CommandLine.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/GraphWriter.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<bool> 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanViewEdgeBundles("view-edge-bundles", cl::Hidden, 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Pop up a window to show edge bundle graphs")); 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar EdgeBundles::ID = 0; 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges", 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /* cfg = */true, /* analysis = */ true) 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar &llvm::EdgeBundlesID = EdgeBundles::ID; 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const { 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.setPreservesAll(); 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunctionPass::getAnalysisUsage(AU); 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool EdgeBundles::runOnMachineFunction(MachineFunction &mf) { 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MF = &mf; 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EC.clear(); 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EC.grow(2 * MF->getNumBlockIDs()); 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++I) { 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineBasicBlock &MBB = *I; 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned OutE = 2 * MBB.getNumber() + 1; 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Join the outgoing bundle with the ingoing bundles of all successors. 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE = MBB.succ_end(); SI != SE; ++SI) 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EC.join(OutE, 2 * (*SI)->getNumber()); 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EC.compress(); 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ViewEdgeBundles) 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman view(); 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute the reverse mapping. 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Blocks.clear(); 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Blocks.resize(getNumBundles()); 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) { 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned b0 = getBundle(i, 0); 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned b1 = getBundle(i, 1); 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Blocks[b0].push_back(i); 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (b1 != b0) 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Blocks[b1].push_back(i); 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// view - Visualize the annotated bipartite CFG with Graphviz. 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid EdgeBundles::view() const { 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ViewGraph(*this, "EdgeBundles"); 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Specialize WriteGraph, the standard implementation won't work. 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanraw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G, 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool ShortNames, 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const std::string &Title) { 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineFunction *MF = G.getMachineFunction(); 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman O << "digraph {\n"; 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I) { 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned BB = I->getNumber(); 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman O << "\t\"BB#" << BB << "\" [ shape=box ]\n" 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n" 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n'; 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::const_succ_iterator SI = I->succ_begin(), 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SE = I->succ_end(); SI != SE; ++SI) 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber() 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << "\" [ color=lightgray ]\n"; 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman O << "}\n"; 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return O; 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 98