summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/EdgeBundles.h58
-rw-r--r--include/llvm/CodeGen/Passes.h4
-rw-r--r--include/llvm/InitializePasses.h1
-rw-r--r--lib/CodeGen/CMakeLists.txt1
-rw-r--r--lib/CodeGen/EdgeBundles.cpp79
-rw-r--r--lib/CodeGen/SplitKit.cpp51
-rw-r--r--lib/CodeGen/SplitKit.h38
-rw-r--r--lib/Target/X86/X86FloatingPoint.cpp3
8 files changed, 147 insertions, 88 deletions
diff --git a/include/llvm/CodeGen/EdgeBundles.h b/include/llvm/CodeGen/EdgeBundles.h
new file mode 100644
index 0000000000..0929d935ec
--- /dev/null
+++ b/include/llvm/CodeGen/EdgeBundles.h
@@ -0,0 +1,58 @@
+//===-------- EdgeBundles.h - Bundles of CFG edges --------------*- c++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The EdgeBundles analysis forms equivalence classes of CFG edges such that all
+// edges leaving a machine basic block are in the same bundle, and all edges
+// leaving a basic block are in the same bundle.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_EDGEBUNDLES_H
+#define LLVM_CODEGEN_EDGEBUNDLES_H
+
+#include "llvm/ADT/IntEqClasses.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+
+class EdgeBundles : public MachineFunctionPass {
+ const MachineFunction *MF;
+
+ /// EC - Each edge bundle is an equivalence class. The keys are:
+ /// 2*BB->getNumber() -> Ingoing bundle.
+ /// 2*BB->getNumber()+1 -> Outgoing bundle.
+ IntEqClasses EC;
+
+public:
+ static char ID;
+ EdgeBundles() : MachineFunctionPass(ID) {}
+
+ /// getBundle - Return the ingoing (Out = false) or outgoing (Out = true)
+ /// bundle number for basic block #N
+ unsigned getBundle(unsigned N, bool Out) const { return EC[2 * N + Out]; }
+
+ /// getMachineFunction - Return the last machine function computed.
+ const MachineFunction *getMachineFunction() const { return MF; }
+
+ /// view - Visualize the annotated bipartite CFG with Graphviz.
+ void view() const;
+
+private:
+ virtual bool runOnMachineFunction(MachineFunction&);
+ virtual void getAnalysisUsage(AnalysisUsage&) const;
+};
+
+/// Specialize WriteGraph, the standard implementation won't work.
+raw_ostream &WriteGraph(raw_ostream &O, const EdgeBundles &G,
+ bool ShortNames = false,
+ const std::string &Title = "");
+
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h
index d4ed9949ea..6f53d344e7 100644
--- a/include/llvm/CodeGen/Passes.h
+++ b/include/llvm/CodeGen/Passes.h
@@ -54,6 +54,10 @@ namespace llvm {
///
extern char &MachineDominatorsID;
+ /// EdgeBundles analysis - Bundle machine CFG edges.
+ ///
+ extern char &EdgeBundlesID;
+
/// PHIElimination pass - This pass eliminates machine instruction PHI nodes
/// by inserting copy instructions. This destroys SSA information, but is the
/// desired input for some register allocators. This pass is "required" by
diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index c89d4fefa8..dc45716328 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -91,6 +91,7 @@ void initializeDomPrinterPass(PassRegistry&);
void initializeDomViewerPass(PassRegistry&);
void initializeDominanceFrontierPass(PassRegistry&);
void initializeDominatorTreePass(PassRegistry&);
+void initializeEdgeBundlesPass(PassRegistry&);
void initializeEdgeProfilerPass(PassRegistry&);
void initializeEarlyCSEPass(PassRegistry&);
void initializeExpandISelPseudosPass(PassRegistry&);
diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt
index a43a0c5d53..b4da151a3a 100644
--- a/lib/CodeGen/CMakeLists.txt
+++ b/lib/CodeGen/CMakeLists.txt
@@ -10,6 +10,7 @@ add_llvm_library(LLVMCodeGen
CriticalAntiDepBreaker.cpp
DeadMachineInstructionElim.cpp
DwarfEHPrepare.cpp
+ EdgeBundles.cpp
ELFCodeEmitter.cpp
ELFWriter.cpp
ExpandISelPseudos.cpp
diff --git a/lib/CodeGen/EdgeBundles.cpp b/lib/CodeGen/EdgeBundles.cpp
new file mode 100644
index 0000000000..d7e73d160e
--- /dev/null
+++ b/lib/CodeGen/EdgeBundles.cpp
@@ -0,0 +1,79 @@
+//===-------- EdgeBundles.cpp - Bundles of CFG edges ----------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides the implementation of the EdgeBundles analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/EdgeBundles.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/GraphWriter.h"
+
+using namespace llvm;
+
+char EdgeBundles::ID = 0;
+
+INITIALIZE_PASS(EdgeBundles, "edge-bundles", "Bundle Machine CFG Edges",
+ /* cfg = */true, /* analysis = */ true)
+
+char &llvm::EdgeBundlesID = EdgeBundles::ID;
+
+void EdgeBundles::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool EdgeBundles::runOnMachineFunction(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();
+ return false;
+}
+
+/// 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';
+ for (MachineBasicBlock::const_succ_iterator SI = I->succ_begin(),
+ SE = I->succ_end(); SI != SE; ++SI)
+ O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber()
+ << "\" [ color=lightgray ]\n";
+ }
+ O << "}\n";
+ return O;
+}
+
+
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index d0971fea48..4bb13e44b8 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -24,7 +24,6 @@
#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"
@@ -36,56 +35,6 @@ 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';
- for (MachineBasicBlock::const_succ_iterator SI = I->succ_begin(),
- SE = I->succ_end(); SI != SE; ++SI)
- O << "\t\"BB#" << BB << "\" -> \"BB#" << (*SI)->getNumber()
- << "\" [ color=lightgray ]\n";
- }
- O << "}\n";
- return O;
-}
-
-
-//===----------------------------------------------------------------------===//
// Split Analysis
//===----------------------------------------------------------------------===//
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index a6ba37610a..236986e4af 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -1,4 +1,4 @@
-//===-------- SplitKit.cpp - Toolkit for splitting live ranges --*- C++ -*-===//
+//===-------- SplitKit.h - Toolkit for splitting live ranges ----*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
@@ -13,12 +13,9 @@
//===----------------------------------------------------------------------===//
#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/IntEqClasses.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/CodeGen/SlotIndexes.h"
-#include <string>
-
namespace llvm {
class LiveInterval;
@@ -40,39 +37,6 @@ template <class NodeT> class DomTreeNodeBase;
typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
-/// EdgeBundles - Group CFG edges into equivalence classes where registers must
-/// be allocated identically. This annotates the CFG to form a bipartite graph
-/// where each block is connected to an ingoing and an outgoing bundle.
-/// Edge bundles are simply numbered, there is no object representation.
-class EdgeBundles {
- const MachineFunction *MF;
-
- /// EC - Each edge bundle is an equivalence class. The keys are:
- /// 2*BB->getNumber() -> Ingoing bundle.
- /// 2*BB->getNumber()+1 -> Outgoing bundle.
- IntEqClasses EC;
-
-public:
- /// compute - Compute the edge bundles for MF. Bundles depend only on the CFG.
- void compute(const MachineFunction *MF);
-
- /// getBundle - Return the ingoing (Out = false) or outgoing (Out = true)
- /// bundle number for basic block #N
- unsigned getBundle(unsigned N, bool Out) const { return EC[2 * N + Out]; }
-
- /// getMachineFunction - Return the last machine function computed.
- const MachineFunction *getMachineFunction() const { return MF; }
-
- /// view - Visualize the annotated bipartite CFG with Graphviz.
- void view() const;
-};
-
-/// Specialize WriteGraph, the standard implementation won't work.
-raw_ostream &WriteGraph(raw_ostream &O, const EdgeBundles &G,
- bool ShortNames = false,
- const std::string &Title = "");
-
-
/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
/// opportunities.
class SplitAnalysis {
diff --git a/lib/Target/X86/X86FloatingPoint.cpp b/lib/Target/X86/X86FloatingPoint.cpp
index 5da6d3ae5c..873a4d9dc6 100644
--- a/lib/Target/X86/X86FloatingPoint.cpp
+++ b/lib/Target/X86/X86FloatingPoint.cpp
@@ -32,6 +32,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/CodeGen/EdgeBundles.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
@@ -51,6 +52,7 @@ namespace {
struct FPS : public MachineFunctionPass {
static char ID;
FPS() : MachineFunctionPass(ID) {
+ initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
// This is really only to keep valgrind quiet.
// The logic in isLive() is too much for it.
memset(Stack, 0, sizeof(Stack));
@@ -59,6 +61,7 @@ namespace {
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
+ AU.addRequired<EdgeBundles>();
AU.addPreservedID(MachineLoopInfoID);
AU.addPreservedID(MachineDominatorsID);
MachineFunctionPass::getAnalysisUsage(AU);
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-28 19:38:51 +0000