1 //===-- RegAllocSimple.cpp - A simple generic register allocator --- ------===//
3 // This file implements a simple register allocator. *Very* simple.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/Function.h"
8 #include "llvm/iTerminators.h"
10 #include "llvm/Constants.h"
11 #include "llvm/Pass.h"
12 #include "llvm/CodeGen/MachineInstr.h"
13 #include "llvm/CodeGen/MachineFunction.h"
14 #include "llvm/CodeGen/MachineInstrBuilder.h"
15 #include "llvm/Target/MachineInstrInfo.h"
16 #include "llvm/Target/MRegisterInfo.h"
17 #include "llvm/Target/MachineRegInfo.h"
18 #include "llvm/Target/TargetMachine.h"
19 #include "llvm/Support/InstVisitor.h"
20 #include "Support/Statistic.h"
24 struct RegAllocSimple : public FunctionPass {
26 MachineBasicBlock *CurrMBB;
29 const MRegisterInfo *RegInfo;
30 unsigned NumBytesAllocated, ByteAlignment;
32 // Maps SSA Regs => offsets on the stack where these values are stored
33 // FIXME: change name to VirtReg2OffsetMap
34 std::map<unsigned, unsigned> RegMap;
36 // Maps SSA Regs => physical regs
37 std::map<unsigned, unsigned> SSA2PhysRegMap;
39 // Maps physical register to their register classes
40 std::map<unsigned, const TargetRegisterClass*> PhysReg2RegClassMap;
42 // Made to combat the incorrect allocation of r2 = add r1, r1
43 std::map<unsigned, unsigned> VirtReg2PhysRegMap;
45 // Maps RegClass => which index we can take a register from. Since this is a
46 // simple register allocator, when we need a register of a certain class, we
47 // just take the next available one.
48 std::map<unsigned, unsigned> RegsUsed;
49 std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
51 RegAllocSimple(TargetMachine &tm) : TM(tm), CurrMBB(0), maxOffset(0),
52 RegInfo(tm.getRegisterInfo()),
55 // build reverse mapping for physReg -> register class
56 RegInfo->buildReg2RegClassMap(PhysReg2RegClassMap);
58 RegsUsed[RegInfo->getFramePointer()] = 1;
59 RegsUsed[RegInfo->getStackPointer()] = 1;
61 cleanupAfterFunction();
64 bool isAvailableReg(unsigned Reg) {
65 // assert(Reg < MRegisterInfo::FirstVirtualReg && "...");
66 return RegsUsed.find(Reg) == RegsUsed.end();
70 unsigned allocateStackSpaceFor(unsigned VirtReg,
71 const TargetRegisterClass *regClass);
73 /// Given size (in bytes), returns a register that is currently unused
74 /// Side effect: marks that register as being used until manually cleared
75 unsigned getFreeReg(unsigned virtualReg);
77 /// Returns all `borrowed' registers back to the free pool
82 /// Invalidates any references, real or implicit, to physical registers
84 void invalidatePhysRegs(const MachineInstr *MI) {
85 unsigned Opcode = MI->getOpcode();
86 const MachineInstrInfo &MII = TM.getInstrInfo();
87 const MachineInstrDescriptor &Desc = MII.get(Opcode);
88 const unsigned *regs = Desc.ImplicitUses;
90 RegsUsed[*regs++] = 1;
92 regs = Desc.ImplicitDefs;
94 RegsUsed[*regs++] = 1;
98 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
99 const MachineOperand &op = MI->getOperand(i);
100 if (op.isMachineRegister())
101 RegsUsed[op.getAllocatedRegNum()] = 1;
104 for (int i = MI->getNumImplicitRefs() - 1; i >= 0; --i) {
105 const MachineOperand &op = MI->getImplicitOp(i);
106 if (op.isMachineRegister())
107 RegsUsed[op.getAllocatedRegNum()] = 1;
112 void cleanupAfterFunction() {
114 SSA2PhysRegMap.clear();
115 NumBytesAllocated = ByteAlignment;
118 /// Moves value from memory into that register
119 MachineBasicBlock::iterator
120 moveUseToReg (MachineBasicBlock *MBB,
121 MachineBasicBlock::iterator I, unsigned VirtReg,
124 /// Saves reg value on the stack (maps virtual register to stack value)
125 MachineBasicBlock::iterator
126 saveVirtRegToStack (MachineBasicBlock *MBB,
127 MachineBasicBlock::iterator I, unsigned VirtReg,
130 MachineBasicBlock::iterator
131 savePhysRegToStack (MachineBasicBlock *MBB,
132 MachineBasicBlock::iterator I, unsigned PhysReg);
134 /// runOnFunction - Top level implementation of instruction selection for
135 /// the entire function.
137 bool runOnMachineFunction(MachineFunction &Fn);
139 bool runOnFunction(Function &Fn) {
140 return runOnMachineFunction(MachineFunction::get(&Fn));
146 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
147 const TargetRegisterClass *regClass)
149 if (RegMap.find(VirtReg) == RegMap.end()) {
151 unsigned size = regClass->getDataSize();
152 unsigned over = NumBytesAllocated - (NumBytesAllocated % ByteAlignment);
153 if (size >= ByteAlignment - over) {
154 // need to pad by (ByteAlignment - over)
155 NumBytesAllocated += ByteAlignment - over;
157 RegMap[VirtReg] = NumBytesAllocated;
158 NumBytesAllocated += size;
160 // FIXME: forcing each arg to take 4 bytes on the stack
161 RegMap[VirtReg] = NumBytesAllocated;
162 NumBytesAllocated += ByteAlignment;
164 return RegMap[VirtReg];
167 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
168 const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
171 if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
172 unsigned regIdx = RegClassIdx[regClass]++;
173 assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
174 physReg = regClass->getRegister(regIdx);
176 physReg = regClass->getRegister(0);
177 // assert(physReg < regClass->getNumRegs() && "No registers in class!");
178 RegClassIdx[regClass] = 1;
181 if (isAvailableReg(physReg))
184 return getFreeReg(virtualReg);
188 MachineBasicBlock::iterator
189 RegAllocSimple::moveUseToReg (MachineBasicBlock *MBB,
190 MachineBasicBlock::iterator I,
191 unsigned VirtReg, unsigned &PhysReg)
193 const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
196 unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
197 PhysReg = getFreeReg(VirtReg);
199 // Add move instruction(s)
200 return RegInfo->loadRegOffset2Reg(MBB, I, PhysReg,
201 RegInfo->getFramePointer(),
202 -stackOffset, regClass->getDataSize());
205 MachineBasicBlock::iterator
206 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock *MBB,
207 MachineBasicBlock::iterator I,
208 unsigned VirtReg, unsigned PhysReg)
210 const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
213 unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
215 // Add move instruction(s)
216 return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
217 RegInfo->getFramePointer(),
218 -stackOffset, regClass->getDataSize());
221 MachineBasicBlock::iterator
222 RegAllocSimple::savePhysRegToStack (MachineBasicBlock *MBB,
223 MachineBasicBlock::iterator I,
226 const TargetRegisterClass* regClass = MF->getRegClass(PhysReg);
229 unsigned offset = allocateStackSpaceFor(PhysReg, regClass);
231 // Add move instruction(s)
232 return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
233 RegInfo->getFramePointer(),
234 offset, regClass->getDataSize());
237 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
238 cleanupAfterFunction();
240 unsigned virtualReg, physReg;
241 DEBUG(std::cerr << "Machine Function " << "\n");
244 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
249 // Handle PHI instructions specially: add moves to each pred block
250 while (MBB->front()->getOpcode() == 0) {
251 MachineInstr *MI = MBB->front();
252 // get rid of the phi
253 MBB->erase(MBB->begin());
255 // a preliminary pass that will invalidate any registers that
256 // are used by the instruction (including implicit uses)
257 invalidatePhysRegs(MI);
259 DEBUG(std::cerr << "num invalid regs: " << RegsUsed.size() << "\n");
261 DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
262 MachineOperand &targetReg = MI->getOperand(0);
264 // If it's a virtual register, allocate a physical one
265 // otherwise, just use whatever register is there now
266 // note: it MUST be a register -- we're assigning to it
267 virtualReg = (unsigned) targetReg.getAllocatedRegNum();
268 if (targetReg.isVirtualRegister()) {
269 physReg = getFreeReg(virtualReg);
271 physReg = targetReg.getAllocatedRegNum();
274 // Find the register class of the target register: should be the
275 // same as the values we're trying to store there
276 const TargetRegisterClass* regClass = PhysReg2RegClassMap[physReg];
277 assert(regClass && "Target register class not found!");
278 unsigned dataSize = regClass->getDataSize();
280 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
281 MachineOperand &opVal = MI->getOperand(i-1);
283 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
284 // source path the phi
286 cast<BasicBlock>(MI->getOperand(i).getVRegValue());
287 MachineBasicBlock *opBlock = NULL;
288 for (MachineFunction::iterator opFi = Fn.begin(), opFe = Fn.end();
289 opFi != opFe; ++opFi)
291 if (opFi->getBasicBlock() == opBB) {
292 opBlock = opFi; break;
295 assert(opBlock && "MachineBasicBlock object not found for specified block!");
297 MachineBasicBlock::iterator opI = opBlock->end();
298 MachineInstr *opMI = *(--opI);
299 const MachineInstrInfo &MII = TM.getInstrInfo();
301 // insert the move just before the return/branch
302 if (MII.isReturn(opMI->getOpcode()) || MII.isBranch(opMI->getOpcode()))
304 // Retrieve the constant value from this op, move it to target
305 // register of the phi
306 if (opVal.getType() == MachineOperand::MO_SignExtendedImmed ||
307 opVal.getType() == MachineOperand::MO_UnextendedImmed)
309 opI = RegInfo->moveImm2Reg(opBlock, opI, physReg,
310 (unsigned) opVal.getImmedValue(),
312 saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
314 // Allocate a physical register and add a move in the BB
315 unsigned opVirtualReg = (unsigned) opVal.getAllocatedRegNum();
316 unsigned opPhysReg; // = getFreeReg(opVirtualReg);
317 opI = moveUseToReg(opBlock, opI, opVirtualReg, opPhysReg);
318 opI = RegInfo->moveReg2Reg(opBlock, opI, physReg, opPhysReg,
320 // Save that register value to the stack of the TARGET REG
321 saveVirtRegToStack(opBlock, opI, virtualReg, opPhysReg);
325 // make regs available to other instructions
329 // really delete the instruction
333 //loop over each basic block
334 for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I)
336 MachineInstr *MI = *I;
338 // a preliminary pass that will invalidate any registers that
339 // are used by the instruction (including implicit uses)
340 invalidatePhysRegs(MI);
342 // Loop over uses, move from memory into registers
343 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
344 MachineOperand &op = MI->getOperand(i);
346 if (op.getType() == MachineOperand::MO_SignExtendedImmed ||
347 op.getType() == MachineOperand::MO_UnextendedImmed)
349 DEBUG(std::cerr << "const\n");
350 } else if (op.isVirtualRegister()) {
351 virtualReg = (unsigned) op.getAllocatedRegNum();
352 DEBUG(std::cerr << "op: " << op << "\n");
353 DEBUG(std::cerr << "\t inst[" << i << "]: ";
354 MI->print(std::cerr, TM));
356 // make sure the same virtual register maps to the same physical
357 // register in any given instruction
358 if (VirtReg2PhysRegMap.find(virtualReg) != VirtReg2PhysRegMap.end()) {
359 physReg = VirtReg2PhysRegMap[virtualReg];
362 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
363 // must be same register number as the first operand
364 // This maps a = b + c into b += c, and saves b into a's spot
365 physReg = (unsigned) MI->getOperand(1).getAllocatedRegNum();
367 physReg = getFreeReg(virtualReg);
369 MachineBasicBlock::iterator J = I;
370 J = saveVirtRegToStack(CurrMBB, ++J, virtualReg, physReg);
373 I = moveUseToReg(CurrMBB, I, virtualReg, physReg);
375 VirtReg2PhysRegMap[virtualReg] = physReg;
377 MI->SetMachineOperandReg(i, physReg);
378 DEBUG(std::cerr << "virt: " << virtualReg <<
379 ", phys: " << op.getAllocatedRegNum() << "\n");
384 VirtReg2PhysRegMap.clear();
389 // add prologue we should preserve callee-save registers...
390 MachineFunction::iterator Fi = Fn.begin();
391 MachineBasicBlock *MBB = Fi;
392 MachineBasicBlock::iterator MBBi = MBB->begin();
393 RegInfo->emitPrologue(MBB, MBBi, NumBytesAllocated);
395 // add epilogue to restore the callee-save registers
396 // loop over the basic block
397 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
400 // check if last instruction is a RET
401 MachineBasicBlock::iterator I = (*MBB).end();
402 MachineInstr *MI = *(--I);
403 const MachineInstrInfo &MII = TM.getInstrInfo();
404 if (MII.isReturn(MI->getOpcode())) {
405 // this block has a return instruction, add epilogue
406 RegInfo->emitEpilogue(MBB, I, NumBytesAllocated);
410 return false; // We never modify the LLVM itself.
413 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
414 return new RegAllocSimple(TM);