include/llvm/CodeGen/RegisterCoalescer.h

   1 //===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the abstract interface for register coalescers,
  11 // allowing them to interact with and query register allocators.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/System/IncludeFile.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  18 #include "llvm/CodeGen/LiveVariables.h"
  19 #include "llvm/Target/TargetRegisterInfo.h"
  20
  21 #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
  22 #define LLVM_CODEGEN_REGISTER_COALESCER_H
  23
  24 namespace llvm
  25 {
  26   class MachineFunction;
  27   class RegallocQuery;
  28   class AnalysisUsage;
  29   class LiveIntervals;
  30   class MachineInstr;
  31   class TargetRegisterInfo;
  32
  33   /// An abstract interface for register coalescers.  Coalescers must
  34   /// implement this interface to be part of the coalescer analysis
  35   /// group.
  36   class RegisterCoalescer {
  37   public:
  38     static char ID; // Class identification, replacement for typeinfo
  39     RegisterCoalescer() {}
  40     virtual ~RegisterCoalescer();  // We want to be subclassed
  41
  42     /// Run the coalescer on this function, providing interference
  43     /// data to query.  Return whether we removed any copies.
  44     virtual bool coalesceFunction(MachineFunction &mf,
  45                                   RegallocQuery &ifd) = 0;
  46
  47     /// Reset state.  Can be used to allow a coalescer run by
  48     /// PassManager to be run again by the register allocator.
  49     virtual void reset(MachineFunction &mf) {};
  50
  51     /// Register allocators must call this from their own
  52     /// getAnalysisUsage to cover the case where the coalescer is not
  53     /// a Pass in the proper sense and isn't managed by PassManager.
  54     /// PassManager needs to know which analyses to make available and
  55     /// which to invalidate when running the register allocator or any
  56     /// pass that might call coalescing.  The long-term solution is to
  57     /// allow hierarchies of PassManagers.
  58     virtual void getAnalysisUsage(AnalysisUsage &AU) const {};
  59   };
  60
  61   /// An abstract interface for register allocators to interact with
  62   /// coalescers
  63   ///
  64   /// Example:
  65   ///
  66   /// This is simply an example of how to use the RegallocQuery
  67   /// interface.  It is not meant to be used in production.
  68   ///
  69   ///   class LinearScanRegallocQuery : public RegallocQuery {
  70   ///   private:
  71   ///     const LiveIntervals &li;
  72   ///
  73   ///   public:
  74   ///     LinearScanRegallocQuery(LiveIntervals &intervals)
  75   ///         : li(intervals) {};
  76   ///
  77   ///     /// This is pretty slow and conservative, but since linear scan
  78   ///     /// allocation doesn't pre-compute interference information it's
  79   ///     /// the best we can do.  Coalescers are always free to ignore this
  80   ///     /// and implement their own discovery strategy.  See
  81   ///     /// SimpleRegisterCoalescing for an example.
  82   ///     void getInterferences(IntervalSet &interferences,
  83   ///                           const LiveInterval &a) const {
  84   ///       for(LiveIntervals::const_iterator iv = li.begin(),
  85   ///             ivend = li.end();
  86   ///           iv != ivend;
  87   ///           ++iv) {
  88   ///         if (interfere(a, iv->second)) {
  89   ///           interferences.insert(&iv->second);
  90   ///         }
  91   ///       }
  92   ///     };
  93   ///
  94   ///     /// This is *really* slow and stupid.  See above.
  95   ///     int getNumberOfInterferences(const LiveInterval &a) const {
  96   ///       IntervalSet intervals;
  97   ///       getInterferences(intervals, a);
  98   ///       return(intervals.size());
  99   ///     };
 100   ///   };
 101   ///
 102   ///   In the allocator:
 103   ///
 104   ///   RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
 105   ///
 106   ///   // We don't reset the coalescer so if it's already been run this
 107   ///   // takes almost no time.
 108   ///   LinearScanRegallocQuery ifd(*li_);
 109   ///   coalescer.coalesceFunction(fn, ifd);
 110   ///
 111   class RegallocQuery {
 112   public:
 113     typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
 114
 115     virtual ~RegallocQuery() {};
 116
 117     /// Return whether two live ranges interfere.
 118     virtual bool interfere(const LiveInterval &a,
 119                            const LiveInterval &b) const {
 120       // A naive test
 121       return(a.overlaps(b));
 122     };
 123
 124     /// Return the set of intervals that interfere with this one.
 125     virtual void getInterferences(IntervalSet &interferences,
 126                                   const LiveInterval &a) const = 0;
 127
 128     /// This can often be cheaper than actually returning the
 129     /// interferences.
 130     virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
 131
 132     /// Make any data structure updates necessary to reflect
 133     /// coalescing or other modifications.
 134     virtual void updateDataForMerge(const LiveInterval &a,
 135                                     const LiveInterval &b,
 136                                     const MachineInstr &copy) {};
 137
 138     /// Allow the register allocator to communicate when it doesn't
 139     /// want a copy coalesced.  This may be due to assumptions made by
 140     /// the allocator about various invariants and so this question is
 141     /// a matter of legality, not performance.  Performance decisions
 142     /// about which copies to coalesce should be made by the
 143     /// coalescer.
 144     virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
 145       return true;
 146     }
 147   };
 148 }
 149
 150 // Because of the way .a files work, we must force the SimpleRC
 151 // implementation to be pulled in if the RegisterCoalescing header is
 152 // included.  Otherwise we run the risk of RegisterCoalescing being
 153 // used, but the default implementation not being linked into the tool
 154 // that uses it.
 155 FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
 156 FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)
 157
 158 #endif