[LLVMdev] [PATCH] Re: Pluggable Register Coalescers
David A. Greene
greened at obbligato.org
Fri Jul 13 11:32:36 PDT 2007
On Wednesday 11 July 2007 15:07, Christopher Lamb wrote:
> Could it be possible for there to be a harness type interface that
> would allow coalescers that support both modes to be hooked into the
> pass registration, and those that depend on the allocator not be
> registered as passes?
I have a patch for this kind of thing attached. Please take a look and let
me know if it looks reasonable. It's not complete yet. I'm about to embark
on implementing a new coalescer that will not be managed by PassManager
and as I do that I'll figure out any additional interfaces that are needed.
If this looks good, I'll commit it and later on I'll commit any additions I
make to this basic interface.
-Dave
-------------- next part --------------
Index: llvm/include/llvm/CodeGen/RegisterAllocator.h
===================================================================
--- llvm/include/llvm/CodeGen/RegisterAllocator.h (revision 0)
+++ llvm/include/llvm/CodeGen/RegisterAllocator.h (revision 0)
@@ -0,0 +1,41 @@
+//===-- RegisterAllocator.h - Register Coalescing Interface ------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the abstract interface for register allocators,
+// allowing them to provide information to coalescers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_REGISTER_ALLOCATOR_H
+#define LLVM_CODEGEN_REGISTER_ALLOCATOR_H
+
+#include <llvm/CodeGen/LiveInterval.h>
+
+namespace llvm
+{
+ class MachineInstruction;
+
+ class RegisterAllocator {
+ public:
+ /// Return whether this copy should be considered for coalescing.
+ virtual bool coalesceThisCopy(const MachineInstruction &) {
+ // Be aggressive, but possibly bad
+ return(true);
+ };
+
+ /// Return whether two live ranges interfere.
+ virtual bool interfere(const LiveInterval &a,
+ const LiveInterval &b) {
+ // A naive test
+ return(a.overlaps(b));
+ };
+ };
+}
+
+#endif
Property changes on: llvm/include/llvm/CodeGen/RegisterAllocator.h
___________________________________________________________________
Name: svn:eol-style
+ LF
Index: llvm/include/llvm/CodeGen/RegisterCoalescer.h
===================================================================
--- llvm/include/llvm/CodeGen/RegisterCoalescer.h (revision 0)
+++ llvm/include/llvm/CodeGen/RegisterCoalescer.h (revision 0)
@@ -0,0 +1,58 @@
+//===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the abstract interface for register coalescers,
+// allowing them to interact with and query register allocators.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/System/IncludeFile.h"
+
+#ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
+#define LLVM_CODEGEN_REGISTER_COALESCER_H
+
+namespace llvm
+{
+ class MachineFunction;
+ class RegisterAllocator;
+ class AnalysisUsage;
+
+ class RegisterCoalescer {
+ public:
+ static char ID; // Class identification, replacement for typeinfo
+ RegisterCoalescer() {}
+ virtual ~RegisterCoalescer(); // We want to be subclassed
+
+ /// Run the coalescer on this function, providing the register
+ /// allocator for queries.
+ virtual void invoke(MachineFunction &mf, RegisterAllocator &ra) = 0;
+
+ /// Reset state. Can be used to allow a coalescer run by
+ /// PassManager to be run again by the register allocator.
+ virtual void reset(MachineFunction &mf) {};
+
+ /// Register allocators must call this from their own
+ /// getAnalysisUsage to cover the case where the coalescer is not
+ /// a Pass in the proper sense and isn't managed by PassManager.
+ /// PassManager needs to know which analyses to make available and
+ /// which to invalidate when running the register allocator or any
+ /// pass that might call coalescing.
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {};
+ };
+}
+
+// Because of the way .a files work, we must force the SimpleRC
+// implementation to be pulled in if the RegisterCoalescing header is
+// included. Otherwise we run the risk of RegisterCoalescing being
+// used, but the default implementation not being linked into the tool
+// that uses it.
+FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
+FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)
+
+#endif
Property changes on: llvm/include/llvm/CodeGen/RegisterCoalescer.h
___________________________________________________________________
Name: svn:eol-style
+ LF
Index: llvm/include/llvm/CodeGen/SimpleRegisterCoalescing.h
===================================================================
--- llvm/include/llvm/CodeGen/SimpleRegisterCoalescing.h (revision 58818)
+++ llvm/include/llvm/CodeGen/SimpleRegisterCoalescing.h (working copy)
@@ -17,17 +17,22 @@
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/IndexedMap.h"
+#include <map>
+
namespace llvm {
class LiveVariables;
class MRegisterInfo;
class TargetInstrInfo;
class VirtRegMap;
-
- class SimpleRegisterCoalescing : public MachineFunctionPass {
+ class RegisterAllocator;
+
+ class SimpleRegisterCoalescing : public MachineFunctionPass,
+ public RegisterCoalescer {
MachineFunction* mf_;
const TargetMachine* tm_;
const MRegisterInfo* mri_;
@@ -45,10 +50,35 @@
/// with other intervals.
BitVector JoinedLIs;
+ /// didWork - Tell whether we have run on this function already.
+ /// This allows the coalescer to either run independently or from
+ /// within a register allocator.
+ typedef std::map<const MachineFunction *, bool> WorkMap;
+ WorkMap didWork;
+ void doWork(MachineFunction &mf);
+
public:
static char ID; // Pass identifcation, replacement for typeid
SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {};
+ const char *getPassName() const{
+ return "Simple Register Coalescing";
+ };
+
+ /// Allow a register allocator to re-run this on a function
+ void reset(const MachineFunction &mf) {
+ didWork[&mf] = false;
+ };
+
+ // TODO: Because PassManager didn't invoke this, how does it know
+ // if analyses were invalidated? This works for this
+ // implementation because it derives from PassManager and will be
+ // run before register allocation if the allocator specifies
+ // addRequiredTransitive of it.
+ void invoke(MachineFunction &mf, RegisterAllocator &) {
+ doWork(mf);
+ };
+
struct CopyRec {
MachineInstr *MI;
unsigned SrcReg, DstReg;
@@ -74,7 +104,9 @@
virtual void releaseMemory();
/// runOnMachineFunction - pass entry point
- virtual bool runOnMachineFunction(MachineFunction&);
+ virtual bool runOnMachineFunction(MachineFunction&mf) {
+ doWork(mf);
+ }
/// print - Implement the dump method.
virtual void print(std::ostream &O, const Module* = 0) const;
Index: llvm/lib/CodeGen/RegAllocBigBlock.cpp
===================================================================
--- llvm/lib/CodeGen/RegAllocBigBlock.cpp (revision 58818)
+++ llvm/lib/CodeGen/RegAllocBigBlock.cpp (working copy)
@@ -36,6 +36,7 @@
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/RegisterAllocator.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
@@ -79,7 +80,8 @@
/// - break ties when picking regs? (probably not worth it in a
/// JIT context)
///
- class VISIBILITY_HIDDEN RABigBlock : public MachineFunctionPass {
+ class VISIBILITY_HIDDEN RABigBlock : public MachineFunctionPass,
+ public RegisterAllocator {
public:
static char ID;
RABigBlock() : MachineFunctionPass((intptr_t)&ID) {}
Index: llvm/lib/CodeGen/RegAllocLinearScan.cpp
===================================================================
--- llvm/lib/CodeGen/RegAllocLinearScan.cpp (revision 58818)
+++ llvm/lib/CodeGen/RegAllocLinearScan.cpp (working copy)
@@ -21,6 +21,8 @@
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/RegisterAllocator.h"
+#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
@@ -47,7 +49,8 @@
static unsigned numIterations = 0;
static unsigned numIntervals = 0;
- struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
+ struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass,
+ public RegisterAllocator {
static char ID;
RALinScan() : MachineFunctionPass((intptr_t)&ID) {}
@@ -96,7 +99,10 @@
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LiveIntervals>();
- AU.addRequiredID(SimpleRegisterCoalescingID);
+ AU.addRequiredTransitive<RegisterCoalescer>();
+ // Make sure PassManager knows which analyses to make available
+ // to coalescing and which analyses coalescing invalidates.
+ getAnalysis<RegisterCoalescer>().getAnalysisUsage(AU);
MachineFunctionPass::getAnalysisUsage(AU);
}
@@ -194,6 +200,10 @@
mri_ = tm_->getRegisterInfo();
li_ = &getAnalysis<LiveIntervals>();
+ RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
+
+ coalescer.invoke(fn, *this);
+
// If this is the first function compiled, compute the related reg classes.
if (RelatedRegClasses.empty())
ComputeRelatedRegClasses();
Index: llvm/lib/CodeGen/RegAllocLocal.cpp
===================================================================
--- llvm/lib/CodeGen/RegAllocLocal.cpp (revision 58818)
+++ llvm/lib/CodeGen/RegAllocLocal.cpp (working copy)
@@ -21,6 +21,7 @@
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/RegisterAllocator.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
@@ -42,7 +43,8 @@
createLocalRegisterAllocator);
- class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
+ class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass,
+ public RegisterAllocator {
public:
static char ID;
RALocal() : MachineFunctionPass((intptr_t)&ID) {}
@@ -129,7 +131,7 @@
}
}
- public:
+ public:
virtual const char *getPassName() const {
return "Local Register Allocator";
}
Index: llvm/lib/CodeGen/RegAllocSimple.cpp
===================================================================
--- llvm/lib/CodeGen/RegAllocSimple.cpp (revision 58818)
+++ llvm/lib/CodeGen/RegAllocSimple.cpp (working copy)
@@ -21,6 +21,7 @@
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/RegisterAllocator.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/Debug.h"
@@ -37,7 +38,8 @@
simpleRegAlloc("simple", " simple register allocator",
createSimpleRegisterAllocator);
- class VISIBILITY_HIDDEN RegAllocSimple : public MachineFunctionPass {
+ class VISIBILITY_HIDDEN RegAllocSimple : public MachineFunctionPass,
+ public RegisterAllocator {
public:
static char ID;
RegAllocSimple() : MachineFunctionPass((intptr_t)&ID) {}
Index: llvm/lib/CodeGen/RegisterCoalescer.cpp
===================================================================
--- llvm/lib/CodeGen/RegisterCoalescer.cpp (revision 0)
+++ llvm/lib/CodeGen/RegisterCoalescer.cpp (revision 0)
@@ -0,0 +1,40 @@
+//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the generic RegisterCoalescer interface which
+// is used as the common interface used by all clients and
+// implementations of register coalescing.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/RegisterCoalescer.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+// Register the RegisterCoalescer interface, providing a nice name to refer to.
+namespace {
+ RegisterAnalysisGroup<RegisterCoalescer> Z("Register Coalescer");
+}
+char RegisterCoalescer::ID = 0;
+
+// RegisterCoalescer destructor: DO NOT move this to the header file
+// for RegisterCoalescer or else clients of the RegisterCoalescer
+// class may not depend on the RegisterCoalescer.o file in the current
+// .a file, causing alias analysis support to not be included in the
+// tool correctly!
+//
+RegisterCoalescer::~RegisterCoalescer() {}
+
+// Because of the way .a files work, we must force the SimpleRC
+// implementation to be pulled in if the RegisterCoalescer classes are
+// pulled in. Otherwise we run the risk of RegisterCoalescer being
+// used, but the default implementation not being linked into the tool
+// that uses it.
+DEFINING_FILE_FOR(RegisterCoalescer)
Property changes on: llvm/lib/CodeGen/RegisterCoalescer.cpp
___________________________________________________________________
Name: svn:eol-style
+ LF
Index: llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp
===================================================================
--- llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp (revision 58818)
+++ llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp (working copy)
@@ -46,13 +46,15 @@
cl::desc("Coallesce copies (default=true)"),
cl::init(true));
+ // Need to register with PassManager so getAnalysis works
RegisterPass<SimpleRegisterCoalescing>
X("simple-register-coalescing",
- "Simple register coalescing to eliminate all possible register copies");
+ "Simple register coalescing to eliminate all possible register copies (default RC impl)");
+
+ // Declare that we implement the RegisterCoalescer interface
+ RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
}
-const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo();
-
void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
//AU.addPreserved<LiveVariables>();
AU.addPreserved<LiveIntervals>();
@@ -1020,7 +1022,16 @@
return true;
}
-bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
+void SimpleRegisterCoalescing::doWork(MachineFunction &fn) {
+ std::pair<WorkMap::iterator, bool> w =
+ didWork.insert(std::make_pair(&fn, false));
+
+ assert(w.first != didWork.end() && "Insert failed");
+
+ if (w.first->second) {
+ return;
+ }
+
mf_ = &fn;
tm_ = &fn.getTarget();
mri_ = tm_->getRegisterInfo();
@@ -1133,10 +1144,13 @@
}
DEBUG(dump());
- return true;
+ w.first->second = true;
}
/// print - Implement the dump method.
void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const {
li_->print(O, m);
}
+
+// Make sure that anything that uses RegisterCoalescer pulls in this file...
+DEFINING_FILE_FOR(SimpleRegisterCoalescing)
More information about the llvm-dev
mailing list