From 8d0963f72c8922bafffb36ff49b18064098a3cab Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 21 Dec 2010 01:50:21 +0000 Subject: Add EdgeBundles to SplitKit. Edge bundles is an annotation on the CFG that turns it into a bipartite directed graph where each basic block is connected to an outgoing and an ingoing bundle. These bundles are useful for identifying regions of the CFG for live range splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122301 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SplitKit.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) (limited to 'lib/CodeGen/SplitKit.cpp') diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index 4bb13e44b8..38c9469879 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -24,6 +24,7 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/GraphWriter.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" @@ -34,6 +35,52 @@ static cl::opt AllowSplit("spiller-splits-edges", cl::desc("Allow critical edge splitting during spilling")); +//===----------------------------------------------------------------------===// +// Edge Bundles +//===----------------------------------------------------------------------===// + +/// compute - Compute the edge bundles for MF. Bundles depend only on the CFG. +void EdgeBundles::compute(const MachineFunction *mf) { + MF = mf; + EC.clear(); + EC.grow(2 * MF->size()); + + for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E; + ++I) { + const MachineBasicBlock &MBB = *I; + unsigned OutE = 2 * MBB.getNumber() + 1; + // Join the outgoing bundle with the ingoing bundles of all successors. + for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), + SE = MBB.succ_end(); SI != SE; ++SI) + EC.join(OutE, 2 * (*SI)->getNumber()); + } + EC.compress(); +} + +/// view - Visualize the annotated bipartite CFG with Graphviz. +void EdgeBundles::view() const { + ViewGraph(*this, "EdgeBundles"); +} + +/// Specialize WriteGraph, the standard implementation won't work. +raw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G, + bool ShortNames, + const std::string &Title) { + const MachineFunction *MF = G.getMachineFunction(); + + O << "digraph {\n"; + for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); + I != E; ++I) { + unsigned BB = I->getNumber(); + O << "\t\"BB#" << BB << "\" [ shape=box ]\n" + << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n" + << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n'; + } + O << "}\n"; + return O; +} + + //===----------------------------------------------------------------------===// // Split Analysis //===----------------------------------------------------------------------===// -- cgit v1.2.3-18-g5258