Pluggable coalescers inplementation.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41743 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 175 insertions, 1 deletions

diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h
index 15021c1..c3cc906 100644
--- a/include/llvm/CodeGen/LinkAllCodegenComponents.h
+++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h
@@ -32,6 +32,8 @@ namespace {
       (void) llvm::createLocalRegisterAllocator();
       (void) llvm::createBigBlockRegisterAllocator();
       (void) llvm::createLinearScanRegisterAllocator();
+
+      (void) llvm::createSimpleRegisterCoalescer();
       
       (void) llvm::createBFS_DAGScheduler(NULL, NULL, NULL);
       (void) llvm::createSimpleDAGScheduler(NULL, NULL, NULL);
diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h
index 4512982..ed96b40 100644
--- a/include/llvm/CodeGen/Passes.h
+++ b/include/llvm/CodeGen/Passes.h
@@ -23,6 +23,7 @@ namespace llvm {
   class FunctionPass;
   class PassInfo;
   class TargetMachine;
+  class RegisterCoalescer;
 
   /// createUnreachableBlockEliminationPass - The LLVM code generator does not
   /// work well with unreachable basic blocks (what live ranges make sense for a
@@ -84,6 +85,11 @@ namespace llvm {
   ///
   FunctionPass *createLinearScanRegisterAllocator();
 
+  /// SimpleRegisterCoalescing Pass - Coalesce all copies possible.  Can run
+  /// independently of the register allocator.
+  ///
+  RegisterCoalescer *createSimpleRegisterCoalescer();
+
   /// PrologEpilogCodeInserter Pass - This pass inserts prolog and epilog code,
   /// and eliminates abstract frame references.
   ///
diff --git a/include/llvm/CodeGen/RegisterCoalescer.h b/include/llvm/CodeGen/RegisterCoalescer.h
new file mode 100644
index 0000000..e7727d5
--- /dev/null
+++ b/include/llvm/CodeGen/RegisterCoalescer.h
@@ -0,0 +1,159 @@
+//===-- 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"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+
+#ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
+#define LLVM_CODEGEN_REGISTER_COALESCER_H
+
+namespace llvm 
+{
+  class MachineFunction;
+  class RegallocQuery;
+  class AnalysisUsage;
+  class LiveIntervals;
+  class MachineInstr;
+  class MRegisterInfo;
+
+  /// An abstract interface for register coalescers.  Coalescers must
+  /// implement this interface to be part of the coalescer analysis
+  /// group.
+  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 interference
+    /// data to query.  Return whether we removed any copies.
+    virtual bool coalesceFunction(MachineFunction &mf,
+                                  RegallocQuery &ifd) = 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.  The long-term solution is to
+    /// allow hierarchies of PassManagers.
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {};
+  }; 
+
+  /// An abstract interface for register allocators to interact with
+  /// coalescers
+  ///
+  /// Example:
+  ///
+  /// This is simply an example of how to use the RegallocQuery
+  /// interface.  It is not meant to be used in production.
+  ///
+  ///   class LinearScanRegallocQuery : public RegallocQuery {
+  ///   private:
+  ///     const LiveIntervals &li;
+  ///
+  ///   public:
+  ///     LinearScanRegallocQuery(LiveIntervals &intervals) 
+  ///         : li(intervals) {};
+  ///
+  ///     /// This is pretty slow and conservative, but since linear scan
+  ///     /// allocation doesn't pre-compute interference information it's
+  ///     /// the best we can do.  Coalescers are always free to ignore this
+  ///     /// and implement their own discovery strategy.  See
+  ///     /// SimpleRegisterCoalescing for an example.
+  ///     void getInterferences(IntervalSet &interferences,
+  ///                           const LiveInterval &a) const {
+  ///       for(LiveIntervals::const_iterator iv = li.begin(),
+  ///             ivend = li.end();
+  ///           iv != ivend;
+  ///           ++iv) {
+  ///         if (interfere(a, iv->second)) {
+  ///           interferences.insert(&iv->second);
+  ///         }
+  ///       }
+  ///     };
+  ///
+  ///     /// This is *really* slow and stupid.  See above.
+  ///     int getNumberOfInterferences(const LiveInterval &a) const {
+  ///       IntervalSet intervals;
+  ///       getInterferences(intervals, a);
+  ///       return(intervals.size());
+  ///     };
+  ///   };  
+  ///
+  ///   In the allocator:
+  ///
+  ///   RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
+  ///
+  ///   // We don't reset the coalescer so if it's already been run this
+  ///   // takes almost no time.
+  ///   LinearScanRegallocQuery ifd(*li_);
+  ///   coalescer.coalesceFunction(fn, ifd);
+  ///
+  class RegallocQuery {
+  public:
+    typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
+
+    virtual ~RegallocQuery() {};
+    
+    /// Return whether two live ranges interfere.
+    virtual bool interfere(const LiveInterval &a,
+                           const LiveInterval &b) const {
+      // A naive test
+      return(a.overlaps(b));
+    };
+
+    /// Return the set of intervals that interfere with this one.
+    virtual void getInterferences(IntervalSet &interferences,
+                                  const LiveInterval &a) const = 0;
+
+    /// This can often be cheaper than actually returning the
+    /// interferences.
+    virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
+
+    /// Make any data structure updates necessary to reflect
+    /// coalescing or other modifications.
+    virtual void updateDataForMerge(const LiveInterval &a,
+                                    const LiveInterval &b,
+                                    const MachineInstr &copy) {};
+
+    /// Allow the register allocator to communicate when it doesn't
+    /// want a copy coalesced.  This may be due to assumptions made by
+    /// the allocator about various invariants and so this question is
+    /// a matter of legality, not performance.  Performance decisions
+    /// about which copies to coalesce should be made by the
+    /// coalescer.
+    virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
+      return(true);
+    }
+  };
+}
+
+// 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
diff --git a/include/llvm/CodeGen/SimpleRegisterCoalescing.h b/include/llvm/CodeGen/SimpleRegisterCoalescing.h
index 2f363d5..4e76081 100644
--- a/include/llvm/CodeGen/SimpleRegisterCoalescing.h
+++ b/include/llvm/CodeGen/SimpleRegisterCoalescing.h
@@ -17,6 +17,7 @@
 #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"
 
@@ -27,7 +28,8 @@ namespace llvm {
   class TargetInstrInfo;
   class VirtRegMap;
 
-  class SimpleRegisterCoalescing : public MachineFunctionPass {
+  class SimpleRegisterCoalescing : public MachineFunctionPass,
+                                   public RegisterCoalescer {
     MachineFunction* mf_;
     const TargetMachine* tm_;
     const MRegisterInfo* mri_;
@@ -76,6 +78,11 @@ namespace llvm {
     /// runOnMachineFunction - pass entry point
     virtual bool runOnMachineFunction(MachineFunction&);
 
+    bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
+      // This runs as an independent pass, so don't do anything.
+      return(false);
+    };
+
     /// print - Implement the dump method.
     virtual void print(std::ostream &O, const Module* = 0) const;
     void print(std::ostream *O, const Module* M = 0) const {