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