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