lib/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 "RegisterClassInfo.h"
  16 #include "llvm/Support/IncludeFile.h"
  17 #include "llvm/CodeGen/LiveInterval.h"
  18 #include "llvm/ADT/SmallPtrSet.h"
  19
  20 #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H
  21 #define LLVM_CODEGEN_REGISTER_COALESCER_H
  22
  23 namespace llvm {
  24
  25   class MachineFunction;
  26   class RegallocQuery;
  27   class AnalysisUsage;
  28   class MachineInstr;
  29   class TargetRegisterInfo;
  30   class TargetRegisterClass;
  31   class TargetInstrInfo;
  32   class SimpleRegisterCoalescing;
  33   class LiveDebugVariables;
  34   class VirtRegMap;
  35   class MachineLoopInfo;
  36
  37   /// An abstract interface for register coalescers.  Coalescers must
  38   /// implement this interface to be part of the coalescer analysis
  39   /// group.
  40   class RegisterCoalescer {
  41   public:
  42     static char ID; // Class identification, replacement for typeinfo
  43     RegisterCoalescer() {}
  44     virtual ~RegisterCoalescer();  // We want to be subclassed
  45
  46     /// Run the coalescer on this function, providing interference
  47     /// data to query.  Return whether we removed any copies.
  48     virtual bool coalesceFunction(MachineFunction &mf,
  49                                   RegallocQuery &ifd) = 0;
  50
  51     /// Reset state.  Can be used to allow a coalescer run by
  52     /// PassManager to be run again by the register allocator.
  53     virtual void reset(MachineFunction &mf) {}
  54
  55     /// Register allocators must call this from their own
  56     /// getAnalysisUsage to cover the case where the coalescer is not
  57     /// a Pass in the proper sense and isn't managed by PassManager.
  58     /// PassManager needs to know which analyses to make available and
  59     /// which to invalidate when running the register allocator or any
  60     /// pass that might call coalescing.  The long-term solution is to
  61     /// allow hierarchies of PassManagers.
  62     virtual void getAnalysisUsage(AnalysisUsage &AU) const {}
  63   };
  64
  65   /// An abstract interface for register allocators to interact with
  66   /// coalescers
  67   ///
  68   /// Example:
  69   ///
  70   /// This is simply an example of how to use the RegallocQuery
  71   /// interface.  It is not meant to be used in production.
  72   ///
  73   ///   class LinearScanRegallocQuery : public RegallocQuery {
  74   ///   private:
  75   ///     const LiveIntervals \&li;
  76   ///
  77   ///   public:
  78   ///     LinearScanRegallocQuery(LiveIntervals &intervals)
  79   ///         : li(intervals) {}
  80   ///
  81   ///     /// This is pretty slow and conservative, but since linear scan
  82   ///     /// allocation doesn't pre-compute interference information it's
  83   ///     /// the best we can do.  Coalescers are always free to ignore this
  84   ///     /// and implement their own discovery strategy.  See
  85   ///     /// SimpleRegisterCoalescing for an example.
  86   ///     void getInterferences(IntervalSet &interferences,
  87   ///                           const LiveInterval &a) const {
  88   ///       for(LiveIntervals::const_iterator iv = li.begin(),
  89   ///             ivend = li.end();
  90   ///           iv != ivend;
  91   ///           ++iv) {
  92   ///         if (interfere(a, iv->second)) {
  93   ///           interferences.insert(&iv->second);
  94   ///         }
  95   ///       }
  96   ///     }
  97   ///
  98   ///     /// This is *really* slow and stupid.  See above.
  99   ///     int getNumberOfInterferences(const LiveInterval &a) const {
 100   ///       IntervalSet intervals;
 101   ///       getInterferences(intervals, a);
 102   ///       return intervals.size();
 103   ///     }
 104   ///   };
 105   ///
 106   ///   In the allocator:
 107   ///
 108   ///   RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>();
 109   ///
 110   ///   // We don't reset the coalescer so if it's already been run this
 111   ///   // takes almost no time.
 112   ///   LinearScanRegallocQuery ifd(*li_);
 113   ///   coalescer.coalesceFunction(fn, ifd);
 114   ///
 115   class RegallocQuery {
 116   public:
 117     typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet;
 118
 119     virtual ~RegallocQuery() {}
 120
 121     /// Return whether two live ranges interfere.
 122     virtual bool interfere(const LiveInterval &a,
 123                            const LiveInterval &b) const {
 124       // A naive test
 125       return a.overlaps(b);
 126     }
 127
 128     /// Return the set of intervals that interfere with this one.
 129     virtual void getInterferences(IntervalSet &interferences,
 130                                   const LiveInterval &a) const = 0;
 131
 132     /// This can often be cheaper than actually returning the
 133     /// interferences.
 134     virtual int getNumberOfInterferences(const LiveInterval &a) const = 0;
 135
 136     /// Make any data structure updates necessary to reflect
 137     /// coalescing or other modifications.
 138     virtual void updateDataForMerge(const LiveInterval &a,
 139                                     const LiveInterval &b,
 140                                     const MachineInstr &copy) {}
 141
 142     /// Allow the register allocator to communicate when it doesn't
 143     /// want a copy coalesced.  This may be due to assumptions made by
 144     /// the allocator about various invariants and so this question is
 145     /// a matter of legality, not performance.  Performance decisions
 146     /// about which copies to coalesce should be made by the
 147     /// coalescer.
 148     virtual bool isLegalToCoalesce(const MachineInstr &inst) const {
 149       return true;
 150     }
 151   };
 152
 153
 154   /// CoalescerPair - A helper class for register coalescers. When deciding if
 155   /// two registers can be coalesced, CoalescerPair can determine if a copy
 156   /// instruction would become an identity copy after coalescing.
 157   class CoalescerPair {
 158     const TargetInstrInfo &tii_;
 159     const TargetRegisterInfo &tri_;
 160
 161     /// dstReg_ - The register that will be left after coalescing. It can be a
 162     /// virtual or physical register.
 163     unsigned dstReg_;
 164
 165     /// srcReg_ - the virtual register that will be coalesced into dstReg.
 166     unsigned srcReg_;
 167
 168     /// subReg_ - The subregister index of srcReg in dstReg_. It is possible the
 169     /// coalesce srcReg_ into a subreg of the larger dstReg_ when dstReg_ is a
 170     /// virtual register.
 171     unsigned subIdx_;
 172
 173     /// partial_ - True when the original copy was a partial subregister copy.
 174     bool partial_;
 175
 176     /// crossClass_ - True when both regs are virtual, and newRC is constrained.
 177     bool crossClass_;
 178
 179     /// flipped_ - True when DstReg and SrcReg are reversed from the oriignal copy
 180     /// instruction.
 181     bool flipped_;
 182
 183     /// newRC_ - The register class of the coalesced register, or NULL if dstReg_
 184     /// is a physreg.
 185     const TargetRegisterClass *newRC_;
 186
 187     /// compose - Compose subreg indices a and b, either may be 0.
 188     unsigned compose(unsigned, unsigned) const;
 189
 190     /// isMoveInstr - Return true if MI is a move or subreg instruction.
 191     bool isMoveInstr(const MachineInstr *MI, unsigned &Src, unsigned &Dst,
 192                      unsigned &SrcSub, unsigned &DstSub) const;
 193
 194   public:
 195     CoalescerPair(const TargetInstrInfo &tii, const TargetRegisterInfo &tri)
 196       : tii_(tii), tri_(tri), dstReg_(0), srcReg_(0), subIdx_(0),
 197         partial_(false), crossClass_(false), flipped_(false), newRC_(0) {}
 198
 199     /// setRegisters - set registers to match the copy instruction MI. Return
 200     /// false if MI is not a coalescable copy instruction.
 201     bool setRegisters(const MachineInstr*);
 202
 203     /// flip - Swap srcReg_ and dstReg_. Return false if swapping is impossible
 204     /// because dstReg_ is a physical register, or subIdx_ is set.
 205     bool flip();
 206
 207     /// isCoalescable - Return true if MI is a copy instruction that will become
 208     /// an identity copy after coalescing.
 209     bool isCoalescable(const MachineInstr*) const;
 210
 211     /// isPhys - Return true if DstReg is a physical register.
 212     bool isPhys() const { return !newRC_; }
 213
 214     /// isPartial - Return true if the original copy instruction did not copy the
 215     /// full register, but was a subreg operation.
 216     bool isPartial() const { return partial_; }
 217
 218     /// isCrossClass - Return true if DstReg is virtual and NewRC is a smaller register class than DstReg's.
 219     bool isCrossClass() const { return crossClass_; }
 220
 221     /// isFlipped - Return true when getSrcReg is the register being defined by
 222     /// the original copy instruction.
 223     bool isFlipped() const { return flipped_; }
 224
 225     /// getDstReg - Return the register (virtual or physical) that will remain
 226     /// after coalescing.
 227     unsigned getDstReg() const { return dstReg_; }
 228
 229     /// getSrcReg - Return the virtual register that will be coalesced away.
 230     unsigned getSrcReg() const { return srcReg_; }
 231
 232     /// getSubIdx - Return the subregister index in DstReg that SrcReg will be
 233     /// coalesced into, or 0.
 234     unsigned getSubIdx() const { return subIdx_; }
 235
 236     /// getNewRC - Return the register class of the coalesced register.
 237     const TargetRegisterClass *getNewRC() const { return newRC_; }
 238   };
 239
 240   class SimpleRegisterCoalescing : public MachineFunctionPass,
 241                                    public RegisterCoalescer {
 242     MachineFunction* mf_;
 243     MachineRegisterInfo* mri_;
 244     const TargetMachine* tm_;
 245     const TargetRegisterInfo* tri_;
 246     const TargetInstrInfo* tii_;
 247     LiveIntervals *li_;
 248     LiveDebugVariables *ldv_;
 249     const MachineLoopInfo* loopInfo;
 250     AliasAnalysis *AA;
 251     RegisterClassInfo RegClassInfo;
 252
 253     /// JoinedCopies - Keep track of copies eliminated due to coalescing.
 254     ///
 255     SmallPtrSet<MachineInstr*, 32> JoinedCopies;
 256
 257     /// ReMatCopies - Keep track of copies eliminated due to remat.
 258     ///
 259     SmallPtrSet<MachineInstr*, 32> ReMatCopies;
 260
 261     /// ReMatDefs - Keep track of definition instructions which have
 262     /// been remat'ed.
 263     SmallPtrSet<MachineInstr*, 8> ReMatDefs;
 264
 265   public:
 266     static char ID; // Pass identifcation, replacement for typeid
 267     SimpleRegisterCoalescing() : MachineFunctionPass(ID) {
 268       initializeSimpleRegisterCoalescingPass(*PassRegistry::getPassRegistry());
 269     }
 270
 271     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 272     virtual void releaseMemory();
 273
 274     /// runOnMachineFunction - pass entry point
 275     virtual bool runOnMachineFunction(MachineFunction&);
 276
 277     bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
 278       // This runs as an independent pass, so don't do anything.
 279       return false;
 280     }
 281
 282     /// print - Implement the dump method.
 283     virtual void print(raw_ostream &O, const Module* = 0) const;
 284
 285   private:
 286     /// joinIntervals - join compatible live intervals
 287     void joinIntervals();
 288
 289     /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting
 290     /// copies that cannot yet be coalesced into the "TryAgain" list.
 291     void CopyCoalesceInMBB(MachineBasicBlock *MBB,
 292                            std::vector<MachineInstr*> &TryAgain);
 293
 294     /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 295     /// which are the src/dst of the copy instruction CopyMI.  This returns true
 296     /// if the copy was successfully coalesced away. If it is not currently
 297     /// possible to coalesce this interval, but it may be possible if other
 298     /// things get coalesced, then it returns true by reference in 'Again'.
 299     bool JoinCopy(MachineInstr *TheCopy, bool &Again);
 300
 301     /// JoinIntervals - Attempt to join these two intervals.  On failure, this
 302     /// returns false.  The output "SrcInt" will not have been modified, so we can
 303     /// use this information below to update aliases.
 304     bool JoinIntervals(CoalescerPair &CP);
 305
 306     /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy. If
 307     /// the source value number is defined by a copy from the destination reg
 308     /// see if we can merge these two destination reg valno# into a single
 309     /// value number, eliminating a copy.
 310     bool AdjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
 311
 312     /// HasOtherReachingDefs - Return true if there are definitions of IntB
 313     /// other than BValNo val# that can reach uses of AValno val# of IntA.
 314     bool HasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
 315                               VNInfo *AValNo, VNInfo *BValNo);
 316
 317     /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy.
 318     /// If the source value number is defined by a commutable instruction and
 319     /// its other operand is coalesced to the copy dest register, see if we
 320     /// can transform the copy into a noop by commuting the definition.
 321     bool RemoveCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI);
 322
 323     /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
 324     /// computation, replace the copy by rematerialize the definition.
 325     /// If PreserveSrcInt is true, make sure SrcInt is valid after the call.
 326     bool ReMaterializeTrivialDef(LiveInterval &SrcInt, bool PreserveSrcInt,
 327                                  unsigned DstReg, unsigned DstSubIdx,
 328                                  MachineInstr *CopyMI);
 329
 330     /// shouldJoinPhys - Return true if a physreg copy should be joined.
 331     bool shouldJoinPhys(CoalescerPair &CP);
 332
 333     /// isWinToJoinCrossClass - Return true if it's profitable to coalesce
 334     /// two virtual registers from different register classes.
 335     bool isWinToJoinCrossClass(unsigned SrcReg,
 336                                unsigned DstReg,
 337                                const TargetRegisterClass *SrcRC,
 338                                const TargetRegisterClass *DstRC,
 339                                const TargetRegisterClass *NewRC);
 340
 341     /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 342     /// update the subregister number if it is not zero. If DstReg is a
 343     /// physical register and the existing subregister number of the def / use
 344     /// being updated is not zero, make sure to set it to the correct physical
 345     /// subregister.
 346     void UpdateRegDefsUses(const CoalescerPair &CP);
 347
 348     /// RemoveDeadDef - If a def of a live interval is now determined dead,
 349     /// remove the val# it defines. If the live interval becomes empty, remove
 350     /// it as well.
 351     bool RemoveDeadDef(LiveInterval &li, MachineInstr *DefMI);
 352
 353     /// RemoveCopyFlag - If DstReg is no longer defined by CopyMI, clear the
 354     /// VNInfo copy flag for DstReg and all aliases.
 355     void RemoveCopyFlag(unsigned DstReg, const MachineInstr *CopyMI);
 356
 357     /// markAsJoined - Remember that CopyMI has already been joined.
 358     void markAsJoined(MachineInstr *CopyMI);
 359   };
 360 } // End llvm namespace
 361
 362 // Because of the way .a files work, we must force the SimpleRC
 363 // implementation to be pulled in if the RegisterCoalescing header is
 364 // included.  Otherwise we run the risk of RegisterCoalescing being
 365 // used, but the default implementation not being linked into the tool
 366 // that uses it.
 367 FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer)
 368 FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing)
 369
 370 #endif