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