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