RegisterScavenging.cpp revision 403c45dfcc74585b02339b5f55f739672e3d141a 
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"
25using namespace llvm;
26
27RegScavenger::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  // Live-in registers are in use.
48  if (!MBB->livein_empty())
49    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
50           E = MBB->livein_end(); I != E; ++I)
51      setUsed(*I);
52}
53
54void RegScavenger::forward() {
55  MachineInstr *MI = MBBI;
56  // Process uses first.
57  BitVector ChangedRegs(NumPhysRegs);
58  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
59    const MachineOperand &MO = MI->getOperand(i);
60    if (!MO.isReg() || !MO.isUse())
61      continue;
62    unsigned Reg = MO.getReg();
63    if (Reg == 0)
64      continue;
65    assert(isUsed(Reg));
66    if (MO.isKill() && !isReserved(Reg))
67      ChangedRegs.set(Reg);
68  }
69  // Change states of all registers after all the uses are processed to guard
70  // against multiple uses.
71  setUnused(ChangedRegs);
72
73  // Process defs.
74  const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
75  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
76    const MachineOperand &MO = MI->getOperand(i);
77    if (!MO.isReg() || !MO.isDef())
78      continue;
79    // Skip two-address destination operand.
80    if (TID->findTiedToSrcOperand(i) != -1)
81      continue;
82    unsigned Reg = MO.getReg();
83    assert(isUnused(Reg) || isReserved(Reg));
84    if (!MO.isDead())
85      setUsed(Reg);
86  }
87
88  ++MBBI;
89}
90
91void RegScavenger::backward() {
92  MachineInstr *MI = --MBBI;
93  // Process defs first.
94  const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
95  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
96    const MachineOperand &MO = MI->getOperand(i);
97    if (!MO.isReg() || !MO.isDef())
98      continue;
99    // Skip two-address destination operand.
100    if (TID->findTiedToSrcOperand(i) != -1)
101      continue;
102    unsigned Reg = MO.getReg();
103    assert(isUsed(Reg));
104    if (!isReserved(Reg))
105      setUnused(Reg);
106  }
107
108  // Process uses.
109  BitVector ChangedRegs(NumPhysRegs);
110  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
111    const MachineOperand &MO = MI->getOperand(i);
112    if (!MO.isReg() || !MO.isUse())
113      continue;
114    unsigned Reg = MO.getReg();
115    if (Reg == 0)
116      continue;
117    assert(isUnused(Reg) || isReserved(Reg));
118    ChangedRegs.set(Reg);
119  }
120  setUsed(ChangedRegs);
121}
122
123/// CreateRegClassMask - Set the bits that represent the registers in the
124/// TargetRegisterClass.
125static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
126  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
127       ++I)
128    Mask.set(*I);
129}
130
131unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
132                                     bool ExCalleeSaved) const {
133  // Mask off the registers which are not in the TargetRegisterClass.
134  BitVector RegStatesCopy(NumPhysRegs, false);
135  CreateRegClassMask(RegClass, RegStatesCopy);
136  RegStatesCopy &= RegStates;
137
138  // If looking for a non-callee-saved register, mask off all the callee-saved
139  // registers.
140  if (ExCalleeSaved)
141    RegStatesCopy &= ~CalleeSavedRegs;
142
143  // Returns the first unused (bit is set) register, or 0 is none is found.
144  int Reg = RegStatesCopy.find_first();
145  return (Reg == -1) ? 0 : Reg;
146}
147