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 using namespace llvm;
  26
  27 RegScavenger::RegScavenger(MachineBasicBlock *mbb)
  28   : MBB(mbb), MBBI(mbb->begin()) {
  29   const MachineFunction &MF = *MBB->getParent();
  30   const TargetMachine &TM = MF.getTarget();
  31   const MRegisterInfo *RegInfo = TM.getRegisterInfo();
  32
  33   NumPhysRegs = RegInfo->getNumRegs();
  34   RegStates.resize(NumPhysRegs, true);
  35
  36   // Create reserved registers bitvector.
  37   ReservedRegs = RegInfo->getReservedRegs(MF);
  38   RegStates ^= ReservedRegs;
  39
  40   // Create callee-saved registers bitvector.
  41   CalleeSavedRegs.resize(NumPhysRegs);
  42   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
  43   if (CSRegs != NULL)
  44     for (unsigned i = 0; CSRegs[i]; ++i)
  45       CalleeSavedRegs.set(CSRegs[i]);
  46 }
  47
  48 void RegScavenger::forward() {
  49   MachineInstr *MI = MBBI;
  50   // Process uses first.
  51   BitVector ChangedRegs(NumPhysRegs);
  52   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  53     const MachineOperand &MO = MI->getOperand(i);
  54     if (!MO.isReg() || !MO.isUse())
  55       continue;
  56     unsigned Reg = MO.getReg();
  57     if (Reg == 0)
  58       continue;
  59     assert(isUsed(Reg));
  60     if (MO.isKill() && !isReserved(Reg))
  61       ChangedRegs.set(Reg);
  62   }
  63   // Change states of all registers after all the uses are processed to guard
  64   // against multiple uses.
  65   setUnused(ChangedRegs);
  66
  67   // Process defs.
  68   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
  69   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  70     const MachineOperand &MO = MI->getOperand(i);
  71     if (!MO.isReg() || !MO.isDef())
  72       continue;
  73     // Skip two-address destination operand.
  74     if (TID->findTiedToSrcOperand(i) != -1)
  75       continue;
  76     unsigned Reg = MO.getReg();
  77     assert(isUnused(Reg) || isReserved(Reg));
  78     if (!MO.isDead())
  79       setUsed(Reg);
  80   }
  81
  82   ++MBBI;
  83 }
  84
  85 void RegScavenger::backward() {
  86   MachineInstr *MI = --MBBI;
  87   // Process defs first.
  88   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
  89   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  90     const MachineOperand &MO = MI->getOperand(i);
  91     if (!MO.isReg() || !MO.isDef())
  92       continue;
  93     // Skip two-address destination operand.
  94     if (TID->findTiedToSrcOperand(i) != -1)
  95       continue;
  96     unsigned Reg = MO.getReg();
  97     assert(isUsed(Reg));
  98     if (!isReserved(Reg))
  99       setUnused(Reg);
 100   }
 101
 102   // Process uses.
 103   BitVector ChangedRegs(NumPhysRegs);
 104   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 105     const MachineOperand &MO = MI->getOperand(i);
 106     if (!MO.isReg() || !MO.isUse())
 107       continue;
 108     unsigned Reg = MO.getReg();
 109     if (Reg == 0)
 110       continue;
 111     assert(isUnused(Reg) || isReserved(Reg));
 112     ChangedRegs.set(Reg);
 113   }
 114   setUsed(ChangedRegs);
 115 }
 116
 117 /// CreateRegClassMask - Set the bits that represent the registers in the
 118 /// TargetRegisterClass.
 119 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
 120   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
 121        ++I)
 122     Mask.set(*I);
 123 }
 124
 125 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
 126                                      bool ExCalleeSaved) const {
 127   // Mask off the registers which are not in the TargetRegisterClass.
 128   BitVector RegStatesCopy(NumPhysRegs, false);
 129   CreateRegClassMask(RegClass, RegStatesCopy);
 130   RegStatesCopy &= RegStates;
 131
 132   // If looking for a non-callee-saved register, mask off all the callee-saved
 133   // registers.
 134   if (ExCalleeSaved)
 135     RegStatesCopy &= ~CalleeSavedRegs;
 136
 137   // Returns the first unused (bit is set) register, or 0 is none is found.
 138   int Reg = RegStatesCopy.find_first();
 139   return (Reg == -1) ? 0 : Reg;
 140 }