lib/CodeGen/RegisterScavenging.cpp

   1 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Evan Cheng and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the machine register scavenger. It can provide
  11 // information such as unused register at any point in a machine basic block.
  12 // It also provides a mechanism to make registers availbale by evicting them
  13 // to spill slots.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "reg-scavenging"
  18 #include "llvm/CodeGen/RegisterScavenging.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineBasicBlock.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/Target/MRegisterInfo.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 using namespace llvm;
  27
  28 void RegScavenger::init(MachineBasicBlock *mbb) {
  29   if (mbb)
  30     MBB = mbb;
  31
  32   const MachineFunction &MF = *MBB->getParent();
  33   const TargetMachine &TM = MF.getTarget();
  34   const MRegisterInfo *RegInfo = TM.getRegisterInfo();
  35
  36   MBBI = MBB->begin();
  37   NumPhysRegs = RegInfo->getNumRegs();
  38   RegStates.resize(NumPhysRegs, true);
  39
  40   // Create reserved registers bitvector.
  41   ReservedRegs = RegInfo->getReservedRegs(MF);
  42   RegStates ^= ReservedRegs;
  43
  44   // Create callee-saved registers bitvector.
  45   CalleeSavedRegs.resize(NumPhysRegs);
  46   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
  47   if (CSRegs != NULL)
  48     for (unsigned i = 0; CSRegs[i]; ++i)
  49       CalleeSavedRegs.set(CSRegs[i]);
  50
  51   // Live-in registers are in use.
  52   if (!MBB->livein_empty())
  53     for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
  54            E = MBB->livein_end(); I != E; ++I)
  55       setUsed(*I);
  56
  57   Initialized = true;
  58 }
  59
  60 void RegScavenger::forward() {
  61   assert(MBBI != MBB->end() && "Already at the end of the basic block!");
  62   // Move ptr forward.
  63   if (!Initialized)
  64     init();
  65   else
  66     MBBI = next(MBBI);
  67
  68   MachineInstr *MI = MBBI;
  69   // Process uses first.
  70   BitVector ChangedRegs(NumPhysRegs);
  71   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  72     const MachineOperand &MO = MI->getOperand(i);
  73     if (!MO.isReg() || !MO.isUse())
  74       continue;
  75     unsigned Reg = MO.getReg();
  76     if (Reg == 0)
  77       continue;
  78     assert(isUsed(Reg));
  79     if (MO.isKill() && !isReserved(Reg))
  80       ChangedRegs.set(Reg);
  81   }
  82   // Change states of all registers after all the uses are processed to guard
  83   // against multiple uses.
  84   setUnused(ChangedRegs);
  85
  86   // Process defs.
  87   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
  88   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  89     const MachineOperand &MO = MI->getOperand(i);
  90     if (!MO.isReg() || !MO.isDef())
  91       continue;
  92     unsigned Reg = MO.getReg();
  93     // Skip two-address destination operand.
  94     if (TID->findTiedToSrcOperand(i) != -1) {
  95       assert(isUsed(Reg));
  96       continue;
  97     }
  98     assert(isUnused(Reg) || isReserved(Reg));
  99     if (!MO.isDead())
 100       setUsed(Reg);
 101   }
 102 }
 103
 104 void RegScavenger::backward() {
 105   assert(MBBI != MBB->begin() && "Already at start of basic block!");
 106   // Move ptr backward.
 107   MBBI = prior(MBBI);
 108
 109   MachineInstr *MI = MBBI;
 110   // Process defs first.
 111   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 112   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 113     const MachineOperand &MO = MI->getOperand(i);
 114     if (!MO.isReg() || !MO.isDef())
 115       continue;
 116     // Skip two-address destination operand.
 117     if (TID->findTiedToSrcOperand(i) != -1)
 118       continue;
 119     unsigned Reg = MO.getReg();
 120     assert(isUsed(Reg));
 121     if (!isReserved(Reg))
 122       setUnused(Reg);
 123   }
 124
 125   // Process uses.
 126   BitVector ChangedRegs(NumPhysRegs);
 127   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 128     const MachineOperand &MO = MI->getOperand(i);
 129     if (!MO.isReg() || !MO.isUse())
 130       continue;
 131     unsigned Reg = MO.getReg();
 132     if (Reg == 0)
 133       continue;
 134     assert(isUnused(Reg) || isReserved(Reg));
 135     ChangedRegs.set(Reg);
 136   }
 137   setUsed(ChangedRegs);
 138 }
 139
 140 /// CreateRegClassMask - Set the bits that represent the registers in the
 141 /// TargetRegisterClass.
 142 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 143   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 144        ++I)
 145     Mask.set(*I);
 146 }
 147
 148 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 149                                      bool ExCalleeSaved) const {
 150   // Mask off the registers which are not in the TargetRegisterClass.
 151   BitVector RegStatesCopy(NumPhysRegs, false);
 152   CreateRegClassMask(RegClass, RegStatesCopy);
 153   RegStatesCopy &= RegStates;
 154
 155   // If looking for a non-callee-saved register, mask off all the callee-saved
 156   // registers.
 157   if (ExCalleeSaved)
 158     RegStatesCopy &= ~CalleeSavedRegs;
 159
 160   // Returns the first unused (bit is set) register, or 0 is none is found.
 161   int Reg = RegStatesCopy.find_first();
 162   return (Reg == -1) ? 0 : Reg;
 163 }
 164
 165 void RegScavenger::clear() {
 166   if (MBB) {
 167     MBBI = MBB->end();
 168     MBB = NULL;
 169   }
 170
 171   NumPhysRegs = 0;
 172   Initialized = false;
 173   RegStates.clear();
 174 }