include/llvm/CodeGen/SimpleRegisterCoalescing.h

   1 //===-- SimpleRegisterCoalescing.h - Register Coalescing --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a simple register copy coalescing phase.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
  15 #define LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
  16
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/LiveInterval.h"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "llvm/CodeGen/RegisterCoalescer.h"
  21 #include "llvm/ADT/BitVector.h"
  22 #include "llvm/ADT/IndexedMap.h"
  23
  24 namespace llvm {
  25
  26   class LiveVariables;
  27   class MRegisterInfo;
  28   class TargetInstrInfo;
  29   class VirtRegMap;
  30
  31   class SimpleRegisterCoalescing : public MachineFunctionPass,
  32                                    public RegisterCoalescer {
  33     MachineFunction* mf_;
  34     const TargetMachine* tm_;
  35     const MRegisterInfo* mri_;
  36     const TargetInstrInfo* tii_;
  37     LiveIntervals *li_;
  38     LiveVariables *lv_;
  39
  40     typedef IndexedMap<unsigned> Reg2RegMap;
  41     Reg2RegMap r2rMap_;
  42
  43     BitVector allocatableRegs_;
  44     DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_;
  45
  46     /// JoinedLIs - Keep track which register intervals have been coalesced
  47     /// with other intervals.
  48     BitVector JoinedLIs;
  49
  50     /// SubRegIdxes - Keep track of sub-register and sub-indexes.
  51     ///
  52     std::vector<std::pair<unsigned, unsigned> > SubRegIdxes;
  53
  54   public:
  55     static char ID; // Pass identifcation, replacement for typeid
  56     SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {}
  57
  58     struct CopyRec {
  59       MachineInstr *MI;
  60       unsigned SrcReg, DstReg;
  61     };
  62     CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) {
  63       CopyRec R;
  64       R.MI = MI;
  65       R.SrcReg = SrcReg;
  66       R.DstReg = DstReg;
  67       return R;
  68     }
  69     struct InstrSlots {
  70       enum {
  71         LOAD  = 0,
  72         USE   = 1,
  73         DEF   = 2,
  74         STORE = 3,
  75         NUM   = 4
  76       };
  77     };
  78
  79     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  80     virtual void releaseMemory();
  81
  82     /// runOnMachineFunction - pass entry point
  83     virtual bool runOnMachineFunction(MachineFunction&);
  84
  85     bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
  86       // This runs as an independent pass, so don't do anything.
  87       return(false);
  88     };
  89
  90     /// print - Implement the dump method.
  91     virtual void print(std::ostream &O, const Module* = 0) const;
  92     void print(std::ostream *O, const Module* M = 0) const {
  93       if (O) print(*O, M);
  94     }
  95
  96   private:
  97     /// joinIntervals - join compatible live intervals
  98     void joinIntervals();
  99
 100     /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting
 101     /// copies that cannot yet be coalesced into the "TryAgain" list.
 102     void CopyCoalesceInMBB(MachineBasicBlock *MBB,
 103                          std::vector<CopyRec> *TryAgain, bool PhysOnly = false);
 104
 105     /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 106     /// which are the src/dst of the copy instruction CopyMI.  This returns true
 107     /// if the copy was successfully coalesced away, or if it is never possible
 108     /// to coalesce these this copy, due to register constraints.  It returns
 109     /// false if it is not currently possible to coalesce this interval, but
 110     /// it may be possible if other things get coalesced.
 111     bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg,
 112                   bool PhysOnly = false);
 113
 114     /// JoinIntervals - Attempt to join these two intervals.  On failure, this
 115     /// returns false.  Otherwise, if one of the intervals being joined is a
 116     /// physreg, this method always canonicalizes DestInt to be it.  The output
 117     /// "SrcInt" will not have been modified, so we can use this information
 118     /// below to update aliases.
 119     bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped);
 120
 121     /// SimpleJoin - Attempt to join the specified interval into this one. The
 122     /// caller of this method must guarantee that the RHS only contains a single
 123     /// value number and that the RHS is not defined by a copy from this
 124     /// interval.  This returns false if the intervals are not joinable, or it
 125     /// joins them and returns true.
 126     bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
 127
 128     /// Return true if the two specified registers belong to different
 129     /// register classes.  The registers may be either phys or virt regs.
 130     bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
 131
 132
 133     bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
 134                               MachineInstr *CopyMI);
 135
 136     /// lastRegisterUse - Returns the last use of the specific register between
 137     /// cycles Start and End. It also returns the use operand by reference. It
 138     /// returns NULL if there are no uses.
 139      MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
 140                                   MachineOperand *&MOU);
 141
 142     /// findDefOperand - Returns the MachineOperand that is a def of the specific
 143     /// register. It returns NULL if the def is not found.
 144     MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg);
 145
 146     /// unsetRegisterKill - Unset IsKill property of all uses of the specific
 147     /// register of the specific instruction.
 148     void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
 149
 150     /// unsetRegisterKills - Unset IsKill property of all uses of specific register
 151     /// between cycles Start and End.
 152     void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg);
 153
 154     /// hasRegisterDef - True if the instruction defines the specific register.
 155     ///
 156     bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
 157
 158     /// rep - returns the representative of this register
 159     unsigned rep(unsigned Reg) {
 160       unsigned Rep = r2rMap_[Reg];
 161       if (Rep)
 162         return r2rMap_[Reg] = rep(Rep);
 163       return Reg;
 164     }
 165
 166     void printRegName(unsigned reg) const;
 167   };
 168
 169 } // End llvm namespace
 170
 171 #endif