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 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &MBB : *MF) { 458dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen unsigned OutE = 2 * MBB.getNumber() + 1; 468dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen // Join the outgoing bundle with the ingoing bundles of all successors. 478dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 488dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen SE = MBB.succ_end(); SI != SE; ++SI) 498dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen EC.join(OutE, 2 * (*SI)->getNumber()); 508dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen } 518dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen EC.compress(); 526b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen if (ViewEdgeBundles) 536b705d482511e432a543d04f6f5e27f5881b6441Jakob Stoklund Olesen view(); 54f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 55f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // Compute the reverse mapping. 56f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks.clear(); 57f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks.resize(getNumBundles()); 58f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 59f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) { 60f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned b0 = getBundle(i, 0); 61f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned b1 = getBundle(i, 1); 62f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks[b0].push_back(i); 63f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (b1 != b0) 64f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Blocks[b1].push_back(i); 65f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 66f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 678dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen return false; 688dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen} 698dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 708dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen/// Specialize WriteGraph, the standard implementation won't work. 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesnamespace llvm { 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate<> 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesraw_ostream &WriteGraph<>(raw_ostream &O, const EdgeBundles &G, 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool ShortNames, 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const Twine &Title) { 768dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen const MachineFunction *MF = G.getMachineFunction(); 778dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen 788dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "digraph {\n"; 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &MBB : *MF) { 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned BB = MBB.getNumber(); 818dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "\t\"BB#" << BB << "\" [ shape=box ]\n" 828dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n" 838dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n'; 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SE = MBB.succ_end(); SI != SE; ++SI) 868dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber() 878dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen << "\" [ color=lightgray ]\n"; 888dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen } 898dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen O << "}\n"; 908dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen return O; 918dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen} 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 94dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// view - Visualize the annotated bipartite CFG with Graphviz. 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid EdgeBundles::view() const { 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ViewGraph(*this, "EdgeBundles"); 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 98