1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
//===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the Evan Cheng and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the machine register scavenger. It can provide
// information such as unused register at any point in a machine basic block.
// It also provides a mechanism to make registers availbale by evicting them
// to spill slots.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "reg-scavenging"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
using namespace llvm;
RegScavenger::RegScavenger(MachineBasicBlock *mbb)
: MBB(mbb), MBBI(mbb->begin()) {
const MachineFunction &MF = *MBB->getParent();
const TargetMachine &TM = MF.getTarget();
const MRegisterInfo *RegInfo = TM.getRegisterInfo();
NumPhysRegs = RegInfo->getNumRegs();
RegStates.resize(NumPhysRegs, true);
// Create reserved registers bitvector.
ReservedRegs = RegInfo->getReservedRegs(MF);
RegStates ^= ReservedRegs;
// Create callee-saved registers bitvector.
CalleeSavedRegs.resize(NumPhysRegs);
const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
if (CSRegs != NULL)
for (unsigned i = 0; CSRegs[i]; ++i)
CalleeSavedRegs.set(CSRegs[i]);
// Live-in registers are in use.
if (!MBB->livein_empty())
for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
E = MBB->livein_end(); I != E; ++I)
setUsed(*I);
}
void RegScavenger::forward() {
MachineInstr *MI = MBBI;
// Process uses first.
BitVector ChangedRegs(NumPhysRegs);
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isUse())
continue;
unsigned Reg = MO.getReg();
if (Reg == 0)
continue;
assert(isUsed(Reg));
if (MO.isKill() && !isReserved(Reg))
ChangedRegs.set(Reg);
}
// Change states of all registers after all the uses are processed to guard
// against multiple uses.
setUnused(ChangedRegs);
// Process defs.
const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isDef())
continue;
// Skip two-address destination operand.
if (TID->findTiedToSrcOperand(i) != -1)
continue;
unsigned Reg = MO.getReg();
assert(isUnused(Reg) || isReserved(Reg));
if (!MO.isDead())
setUsed(Reg);
}
++MBBI;
}
void RegScavenger::backward() {
MachineInstr *MI = --MBBI;
// Process defs first.
const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isDef())
continue;
// Skip two-address destination operand.
if (TID->findTiedToSrcOperand(i) != -1)
continue;
unsigned Reg = MO.getReg();
assert(isUsed(Reg));
if (!isReserved(Reg))
setUnused(Reg);
}
// Process uses.
BitVector ChangedRegs(NumPhysRegs);
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isUse())
continue;
unsigned Reg = MO.getReg();
if (Reg == 0)
continue;
assert(isUnused(Reg) || isReserved(Reg));
ChangedRegs.set(Reg);
}
setUsed(ChangedRegs);
}
/// CreateRegClassMask - Set the bits that represent the registers in the
/// TargetRegisterClass.
static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
++I)
Mask.set(*I);
}
unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
bool ExCalleeSaved) const {
// Mask off the registers which are not in the TargetRegisterClass.
BitVector RegStatesCopy(NumPhysRegs, false);
CreateRegClassMask(RegClass, RegStatesCopy);
RegStatesCopy &= RegStates;
// If looking for a non-callee-saved register, mask off all the callee-saved
// registers.
if (ExCalleeSaved)
RegStatesCopy &= ~CalleeSavedRegs;
// Returns the first unused (bit is set) register, or 0 is none is found.
int Reg = RegStatesCopy.find_first();
return (Reg == -1) ? 0 : Reg;
}
|
