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/Support/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   class TargetRegisterInfo;
  29   class TargetRegisterClass;
  30   class TargetInstrInfo;
  31
  32   /// An abstract interface for register coalescers.  Coalescers must
  33   /// implement this interface to be part of the coalescer analysis
  34   /// group.
  35   class RegisterCoalescer {
  36   public:
  37     static char ID; // Class identification, replacement for typeinfo
  38     RegisterCoalescer() {}
  39     virtual ~RegisterCoalescer();  // We want to be subclassed
  40
  41     /// Run the coalescer on this function, providing interference
  42     /// data to query.  Return whether we removed any copies.
  43     virtual bool coalesceFunction(MachineFunction &mf,
  44                                   RegallocQuery &ifd) = 0;
  45
  46     /// Reset state.  Can be used to allow a coalescer run by
  47     /// PassManager to be run again by the register allocator.
  48     virtual void reset(MachineFunction &mf) {}
  49
  50     /// Register allocators must call this from their own
  51     /// getAnalysisUsage to cover the case where the coalescer is not
  52     /// a Pass in the proper sense and isn't managed by PassManager.
  53     /// PassManager needs to know which analyses to make available and
  54     /// which to invalidate when running the register allocator or any
  55     /// pass that might call coalescing.  The long-term solution is to
  56     /// allow hierarchies of PassManagers.
  57     virtual void getAnalysisUsage(AnalysisUsage &AU) const {}
  58   };
  59
  60   /// An abstract interface for register allocators to interact with
  61   /// coalescers
  62   ///
  63   /// Example:
  64   ///
  65   /// This is simply an example of how to use the RegallocQuery
  66   /// interface.  It is not meant to be used in production.
  67   ///
  68   ///   class LinearScanRegallocQuery : public RegallocQuery {
  69   ///   private:
  70   ///     const LiveIntervals \&li;
  71   ///
  72   ///   public:
  73   ///     LinearScanRegallocQuery(LiveIntervals &intervals)
  74   ///         : li(intervals) {}
  75   ///
  76   ///     /// This is pretty slow and conservative, but since linear scan
  77   ///     /// allocation doesn't pre-compute interference information it's
  78   ///     /// the best we can do.  Coalescers are always free to ignore this
  79   ///     /// and implement their own discovery strategy.  See
  80   ///     /// SimpleRegisterCoalescing for an example.
  81   ///     void getInterferences(IntervalSet &interferences,
  82   ///                           const LiveInterval &a) const {
  83   ///       for(LiveIntervals::const_iterator iv = li.begin(),
  84   ///             ivend = li.end();
  85   ///           iv != ivend;
  86   ///           ++iv) {
  87   ///         if (interfere(a, iv->second)) {
  88   ///           interferences.insert(&iv->second);
  89   ///         }
  90   ///       }
  91   ///     }
  92   ///
  93   ///     /// This is *really* slow and stupid.  See above.
  94   ///     int getNumberOfInterferences(const LiveInterval &a) const {
  95   ///       IntervalSet intervals;
  96   ///       getInterferences(intervals, a);
  97   ///       return intervals.size();
  98   ///     }
  99   ///   };
 100   ///
 101   ///   In the allocator:
 102   ///
 103   ///   RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
 104   ///
 105   ///   // We don't reset the coalescer so if it's already been run this
 106   ///   // takes almost no time.
 107   ///   LinearScanRegallocQuery ifd(*li_);
 108   ///   coalescer.coalesceFunction(fn, ifd);
 109   ///
 110   class RegallocQuery {
 111   public:
 112     typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
 113
 114     virtual ~RegallocQuery() {}
 115
 116     /// Return whether two live ranges interfere.
 117     virtual bool interfere(const LiveInterval &a,
 118                            const LiveInterval &b) const {
 119       // A naive test
 120       return a.overlaps(b);
 121     }
 122
 123     /// Return the set of intervals that interfere with this one.
 124     virtual void getInterferences(IntervalSet &interferences,
 125                                   const LiveInterval &a) const = 0;
 126
 127     /// This can often be cheaper than actually returning the
 128     /// interferences.
 129     virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
 130
 131     /// Make any data structure updates necessary to reflect
 132     /// coalescing or other modifications.
 133     virtual void updateDataForMerge(const LiveInterval &a,
 134                                     const LiveInterval &b,
 135                                     const MachineInstr &copy) {}
 136
 137     /// Allow the register allocator to communicate when it doesn't
 138     /// want a copy coalesced.  This may be due to assumptions made by
 139     /// the allocator about various invariants and so this question is
 140     /// a matter of legality, not performance.  Performance decisions
 141     /// about which copies to coalesce should be made by the
 142     /// coalescer.
 143     virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
 144       return true;
 145     }
 146   };
 147
 148
 149   /// CoalescerPair - A helper class for register coalescers. When deciding if
 150   /// two registers can be coalesced, CoalescerPair can determine if a copy
 151   /// instruction would become an identity copy after coalescing.
 152   class CoalescerPair {
 153     const TargetInstrInfo &tii_;
 154     const TargetRegisterInfo &tri_;
 155
 156     /// dstReg_ - The register that will be left after coalescing. It can be a
 157     /// virtual or physical register.
 158     unsigned dstReg_;
 159
 160     /// srcReg_ - the virtual register that will be coalesced into dstReg.
 161     unsigned srcReg_;
 162
 163     /// subReg_ - The subregister index of srcReg in dstReg_. It is possible the
 164     /// coalesce srcReg_ into a subreg of the larger dstReg_ when dstReg_ is a
 165     /// virtual register.
 166     unsigned subIdx_;
 167
 168     /// partial_ - True when the original copy was a partial subregister copy.
 169     bool partial_;
 170
 171     /// crossClass_ - True when both regs are virtual, and newRC is constrained.
 172     bool crossClass_;
 173
 174     /// flipped_ - True when DstReg and SrcReg are reversed from the oriignal copy
 175     /// instruction.
 176     bool flipped_;
 177
 178     /// newRC_ - The register class of the coalesced register, or NULL if dstReg_
 179     /// is a physreg.
 180     const TargetRegisterClass *newRC_;
 181
 182     /// compose - Compose subreg indices a and b, either may be 0.
 183     unsigned compose(unsigned, unsigned) const;
 184
 185     /// isMoveInstr - Return true if MI is a move or subreg instruction.
 186     bool isMoveInstr(const MachineInstr *MI, unsigned &Src, unsigned &Dst,
 187                      unsigned &SrcSub, unsigned &DstSub) const;
 188
 189   public:
 190     CoalescerPair(const TargetInstrInfo &tii, const TargetRegisterInfo &tri)
 191       : tii_(tii), tri_(tri), dstReg_(0), srcReg_(0), subIdx_(0),
 192         partial_(false), crossClass_(false), flipped_(false), newRC_(0) {}
 193
 194     /// setRegisters - set registers to match the copy instruction MI. Return
 195     /// false if MI is not a coalescable copy instruction.
 196     bool setRegisters(const MachineInstr*);
 197
 198     /// flip - Swap srcReg_ and dstReg_. Return false if swapping is impossible
 199     /// because dstReg_ is a physical register, or subIdx_ is set.
 200     bool flip();
 201
 202     /// isCoalescable - Return true if MI is a copy instruction that will become
 203     /// an identity copy after coalescing.
 204     bool isCoalescable(const MachineInstr*) const;
 205
 206     /// isPhys - Return true if DstReg is a physical register.
 207     bool isPhys() const { return !newRC_; }
 208
 209     /// isPartial - Return true if the original copy instruction did not copy the
 210     /// full register, but was a subreg operation.
 211     bool isPartial() const { return partial_; }
 212
 213     /// isCrossClass - Return true if DstReg is virtual and NewRC is a smaller register class than DstReg's.
 214     bool isCrossClass() const { return crossClass_; }
 215
 216     /// isFlipped - Return true when getSrcReg is the register being defined by
 217     /// the original copy instruction.
 218     bool isFlipped() const { return flipped_; }
 219
 220     /// getDstReg - Return the register (virtual or physical) that will remain
 221     /// after coalescing.
 222     unsigned getDstReg() const { return dstReg_; }
 223
 224     /// getSrcReg - Return the virtual register that will be coalesced away.
 225     unsigned getSrcReg() const { return srcReg_; }
 226
 227     /// getSubIdx - Return the subregister index in DstReg that SrcReg will be
 228     /// coalesced into, or 0.
 229     unsigned getSubIdx() const { return subIdx_; }
 230
 231     /// getNewRC - Return the register class of the coalesced register.
 232     const TargetRegisterClass *getNewRC() const { return newRC_; }
 233   };
 234 }
 235
 236 // Because of the way .a files work, we must force the SimpleRC
 237 // implementation to be pulled in if the RegisterCoalescing header is
 238 // included.  Otherwise we run the risk of RegisterCoalescing being
 239 // used, but the default implementation not being linked into the tool
 240 // that uses it.
 241 FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
 242 FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)
 243
 244 #endif