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   public:
  51     static char ID; // Pass identifcation, replacement for typeid
  52     SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {}
  53
  54     struct CopyRec {
  55       MachineInstr *MI;
  56       unsigned SrcReg, DstReg;
  57     };
  58     CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) {
  59       CopyRec R;
  60       R.MI = MI;
  61       R.SrcReg = SrcReg;
  62       R.DstReg = DstReg;
  63       return R;
  64     }
  65     struct InstrSlots {
  66       enum {
  67         LOAD  = 0,
  68         USE   = 1,
  69         DEF   = 2,
  70         STORE = 3,
  71         NUM   = 4
  72       };
  73     };
  74
  75     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  76     virtual void releaseMemory();
  77
  78     /// runOnMachineFunction - pass entry point
  79     virtual bool runOnMachineFunction(MachineFunction&);
  80
  81     bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
  82       // This runs as an independent pass, so don't do anything.
  83       return(false);
  84     };
  85
  86     /// print - Implement the dump method.
  87     virtual void print(std::ostream &O, const Module* = 0) const;
  88     void print(std::ostream *O, const Module* M = 0) const {
  89       if (O) print(*O, M);
  90     }
  91
  92   private:
  93     /// joinIntervals - join compatible live intervals
  94     void joinIntervals();
  95
  96     /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting
  97     /// copies that cannot yet be coalesced into the "TryAgain" list.
  98     void CopyCoalesceInMBB(MachineBasicBlock *MBB,
  99                          std::vector<CopyRec> *TryAgain, bool PhysOnly = false);
 100
 101     /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 102     /// which are the src/dst of the copy instruction CopyMI.  This returns true
 103     /// if the copy was successfully coalesced away, or if it is never possible
 104     /// to coalesce these this copy, due to register constraints.  It returns
 105     /// false if it is not currently possible to coalesce this interval, but
 106     /// it may be possible if other things get coalesced.
 107     bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg,
 108                   bool PhysOnly = false);
 109
 110     /// JoinIntervals - Attempt to join these two intervals.  On failure, this
 111     /// returns false.  Otherwise, if one of the intervals being joined is a
 112     /// physreg, this method always canonicalizes DestInt to be it.  The output
 113     /// "SrcInt" will not have been modified, so we can use this information
 114     /// below to update aliases.
 115     bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped);
 116
 117     /// SimpleJoin - Attempt to join the specified interval into this one. The
 118     /// caller of this method must guarantee that the RHS only contains a single
 119     /// value number and that the RHS is not defined by a copy from this
 120     /// interval.  This returns false if the intervals are not joinable, or it
 121     /// joins them and returns true.
 122     bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
 123
 124     /// Return true if the two specified registers belong to different
 125     /// register classes.  The registers may be either phys or virt regs.
 126     bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
 127
 128
 129     bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
 130                               MachineInstr *CopyMI);
 131
 132     /// lastRegisterUse - Returns the last use of the specific register between
 133     /// cycles Start and End. It also returns the use operand by reference. It
 134     /// returns NULL if there are no uses.
 135      MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
 136                                   MachineOperand *&MOU);
 137
 138     /// findDefOperand - Returns the MachineOperand that is a def of the specific
 139     /// register. It returns NULL if the def is not found.
 140     MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg);
 141
 142     /// unsetRegisterKill - Unset IsKill property of all uses of the specific
 143     /// register of the specific instruction.
 144     void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
 145
 146     /// unsetRegisterKills - Unset IsKill property of all uses of specific register
 147     /// between cycles Start and End.
 148     void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg);
 149
 150     /// hasRegisterDef - True if the instruction defines the specific register.
 151     ///
 152     bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
 153
 154     /// rep - returns the representative of this register
 155     unsigned rep(unsigned Reg) {
 156       unsigned Rep = r2rMap_[Reg];
 157       if (Rep)
 158         return r2rMap_[Reg] = rep(Rep);
 159       return Reg;
 160     }
 161
 162     void printRegName(unsigned reg) const;
 163   };
 164
 165 } // End llvm namespace
 166
 167 #endif