18dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen//===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===// 28dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// 38dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 48dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// 58dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 78dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// 88dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 98dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// 108dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// This file provides the implementation of the EdgeBundles analysis. 118dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen// 128dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 138dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 148dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen#include "llvm/CodeGen/EdgeBundles.h" 158dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen#include "llvm/CodeGen/MachineBasicBlock.h" 168dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunction.h" 178dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 186b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 198dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen#include "llvm/Support/GraphWriter.h" 208dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 218dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenusing namespace llvm; 228dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 236b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesenstatic cl::opt<bool> 246b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund OlesenViewEdgeBundles("view-edge-bundles", cl::Hidden, 256b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen cl::desc("Pop up a window to show edge bundle graphs")); 266b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen 278dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenchar EdgeBundles::ID = 0; 288dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 298dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund OlesenINITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges", 308dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen /* cfg = */true, /* analysis = */ true) 318dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 328dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenchar &llvm::EdgeBundlesID = EdgeBundles::ID; 338dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 348dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenvoid EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const { 358dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen AU.setPreservesAll(); 368dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 378dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen} 388dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 398dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenbool EdgeBundles::runOnMachineFunction(MachineFunction &mf) { 408dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen MF = &mf; 418dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen EC.clear(); 423c397eb741d1b6c5ecf2aa5c3632b7ce3abf55d4Anna Zaks EC.grow(2 * MF->getNumBlockIDs()); 438dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 448dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E; 458dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen ++I) { 468dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen const MachineBasicBlock &MBB = *I; 478dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen unsigned OutE = 2 * MBB.getNumber() + 1; 488dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen // Join the outgoing bundle with the ingoing bundles of all successors. 498dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 508dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen SE = MBB.succ_end(); SI != SE; ++SI) 518dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen EC.join(OutE, 2 * (*SI)->getNumber()); 528dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen } 538dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen EC.compress(); 546b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen if (ViewEdgeBundles) 556b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen view(); 56f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 57f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Compute the reverse mapping. 58f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks.clear(); 59f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks.resize(getNumBundles()); 60f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 61f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) { 62f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned b0 = getBundle(i, 0); 63f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned b1 = getBundle(i, 1); 64f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks[b0].push_back(i); 65f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (b1 != b0) 66f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks[b1].push_back(i); 67f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 68f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 698dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen return false; 708dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen} 718dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 728dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen/// view - Visualize the annotated bipartite CFG with Graphviz. 738dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenvoid EdgeBundles::view() const { 748dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen ViewGraph(*this, "EdgeBundles"); 758dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen} 768dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 778dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen/// Specialize WriteGraph, the standard implementation won't work. 788dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesenraw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G, 798dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen bool ShortNames, 808dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen const std::string &Title) { 818dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen const MachineFunction *MF = G.getMachineFunction(); 828dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 838dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "digraph {\n"; 848dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); 858dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen I != E; ++I) { 868dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen unsigned BB = I->getNumber(); 878dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "\t\"BB#" << BB << "\" [ shape=box ]\n" 888dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n" 898dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n'; 908dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen for (MachineBasicBlock::const_succ_iterator SI = I->succ_begin(), 918dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen SE = I->succ_end(); SI != SE; ++SI) 928dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber() 938dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen << "\" [ color=lightgray ]\n"; 948dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen } 958dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "}\n"; 968dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen return O; 978dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen} 98