EdgeBundles.cpp revision f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0c
1//===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file provides the implementation of the EdgeBundles analysis. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/EdgeBundles.h" 15#include "llvm/CodeGen/MachineBasicBlock.h" 16#include "llvm/CodeGen/MachineFunction.h" 17#include "llvm/CodeGen/Passes.h" 18#include "llvm/Support/CommandLine.h" 19#include "llvm/Support/GraphWriter.h" 20 21using namespace llvm; 22 23static cl::opt<bool> 24ViewEdgeBundles("view-edge-bundles", cl::Hidden, 25 cl::desc("Pop up a window to show edge bundle graphs")); 26 27char EdgeBundles::ID = 0; 28 29INITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges", 30 /* cfg = */true, /* analysis = */ true) 31 32char &llvm::EdgeBundlesID = EdgeBundles::ID; 33 34void EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const { 35 AU.setPreservesAll(); 36 MachineFunctionPass::getAnalysisUsage(AU); 37} 38 39bool EdgeBundles::runOnMachineFunction(MachineFunction &mf) { 40 MF = &mf; 41 EC.clear(); 42 EC.grow(2 * MF->size()); 43 44 for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E; 45 ++I) { 46 const MachineBasicBlock &MBB = *I; 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, 0); 63 unsigned b1 = getBundle(i, 1); 64 Blocks[b0].push_back(i); 65 if (b1 != b0) 66 Blocks[b1].push_back(i); 67 } 68 69 return false; 70} 71 72/// view - Visualize the annotated bipartite CFG with Graphviz. 73void EdgeBundles::view() const { 74 ViewGraph(*this, "EdgeBundles"); 75} 76 77/// Specialize WriteGraph, the standard implementation won't work. 78raw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G, 79 bool ShortNames, 80 const std::string &Title) { 81 const MachineFunction *MF = G.getMachineFunction(); 82 83 O << "digraph {\n"; 84 for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); 85 I != E; ++I) { 86 unsigned BB = I->getNumber(); 87 O << "\t\"BB#" << BB << "\" [ shape=box ]\n" 88 << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n" 89 << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n'; 90 for (MachineBasicBlock::const_succ_iterator SI = I->succ_begin(), 91 SE = I->succ_end(); SI != SE; ++SI) 92 O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber() 93 << "\" [ color=lightgray ]\n"; 94 } 95 O << "}\n"; 96 return O; 97} 98