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