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/MachineFunction.h"
13 #include "llvm/CodeGen/MachineInstrBuilder.h"
14 #include "llvm/Target/MachineInstrInfo.h"
15 #include "llvm/Target/MRegisterInfo.h"
16 #include "llvm/Target/TargetMachine.h"
17 #include "llvm/Support/InstVisitor.h"
18 #include "Support/Statistic.h"
21 struct RegAllocSimple : public FunctionPass {
23 MachineBasicBlock *CurrMBB;
26 const MRegisterInfo *RegInfo;
27 unsigned NumBytesAllocated, ByteAlignment;
29 // Maps SSA Regs => offsets on the stack where these values are stored
30 std::map<unsigned, unsigned> VirtReg2OffsetMap;
32 // Maps SSA Regs => physical regs
33 std::map<unsigned, unsigned> SSA2PhysRegMap;
35 // Maps physical register to their register classes
36 std::map<unsigned, const TargetRegisterClass*> PhysReg2RegClassMap;
38 // Made to combat the incorrect allocation of r2 = add r1, r1
39 std::map<unsigned, unsigned> VirtReg2PhysRegMap;
41 // Maps RegClass => which index we can take a register from. Since this is a
42 // simple register allocator, when we need a register of a certain class, we
43 // just take the next available one.
44 std::map<unsigned, unsigned> RegsUsed;
45 std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
47 RegAllocSimple(TargetMachine &tm) : TM(tm), CurrMBB(0), maxOffset(0),
48 RegInfo(tm.getRegisterInfo()),
51 // build reverse mapping for physReg -> register class
52 RegInfo->buildReg2RegClassMap(PhysReg2RegClassMap);
54 RegsUsed[RegInfo->getFramePointer()] = 1;
55 RegsUsed[RegInfo->getStackPointer()] = 1;
57 cleanupAfterFunction();
60 bool isAvailableReg(unsigned Reg) {
61 // assert(Reg < MRegisterInfo::FirstVirtualReg && "...");
62 return RegsUsed.find(Reg) == RegsUsed.end();
66 unsigned allocateStackSpaceFor(unsigned VirtReg,
67 const TargetRegisterClass *regClass);
69 /// Given size (in bytes), returns a register that is currently unused
70 /// Side effect: marks that register as being used until manually cleared
71 unsigned getFreeReg(unsigned virtualReg);
73 /// Returns all `borrowed' registers back to the free pool
78 /// Invalidates any references, real or implicit, to physical registers
80 void invalidatePhysRegs(const MachineInstr *MI) {
81 unsigned Opcode = MI->getOpcode();
82 const MachineInstrInfo &MII = TM.getInstrInfo();
83 const MachineInstrDescriptor &Desc = MII.get(Opcode);
84 const unsigned *regs = Desc.ImplicitUses;
86 RegsUsed[*regs++] = 1;
88 regs = Desc.ImplicitDefs;
90 RegsUsed[*regs++] = 1;
93 void cleanupAfterFunction() {
94 VirtReg2OffsetMap.clear();
95 SSA2PhysRegMap.clear();
96 NumBytesAllocated = ByteAlignment;
99 /// Moves value from memory into that register
100 MachineBasicBlock::iterator
101 moveUseToReg (MachineBasicBlock *MBB,
102 MachineBasicBlock::iterator I, unsigned VirtReg,
105 /// Saves reg value on the stack (maps virtual register to stack value)
106 MachineBasicBlock::iterator
107 saveVirtRegToStack (MachineBasicBlock *MBB,
108 MachineBasicBlock::iterator I, unsigned VirtReg,
111 MachineBasicBlock::iterator
112 savePhysRegToStack (MachineBasicBlock *MBB,
113 MachineBasicBlock::iterator I, unsigned PhysReg);
115 /// runOnFunction - Top level implementation of instruction selection for
116 /// the entire function.
118 bool runOnMachineFunction(MachineFunction &Fn);
120 bool runOnFunction(Function &Fn) {
121 return runOnMachineFunction(MachineFunction::get(&Fn));
127 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
128 const TargetRegisterClass *regClass)
130 if (VirtReg2OffsetMap.find(VirtReg) == VirtReg2OffsetMap.end()) {
132 unsigned size = regClass->getDataSize();
133 unsigned over = NumBytesAllocated - (NumBytesAllocated % ByteAlignment);
134 if (size >= ByteAlignment - over) {
135 // need to pad by (ByteAlignment - over)
136 NumBytesAllocated += ByteAlignment - over;
138 VirtReg2OffsetMap[VirtReg] = NumBytesAllocated;
139 NumBytesAllocated += size;
141 // FIXME: forcing each arg to take 4 bytes on the stack
142 VirtReg2OffsetMap[VirtReg] = NumBytesAllocated;
143 NumBytesAllocated += ByteAlignment;
145 return VirtReg2OffsetMap[VirtReg];
148 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
149 const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
152 if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
153 unsigned regIdx = RegClassIdx[regClass]++;
154 assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
155 physReg = regClass->getRegister(regIdx);
157 physReg = regClass->getRegister(0);
158 // assert(physReg < regClass->getNumRegs() && "No registers in class!");
159 RegClassIdx[regClass] = 1;
162 if (isAvailableReg(physReg))
165 return getFreeReg(virtualReg);
169 MachineBasicBlock::iterator
170 RegAllocSimple::moveUseToReg (MachineBasicBlock *MBB,
171 MachineBasicBlock::iterator I,
172 unsigned VirtReg, unsigned &PhysReg)
174 const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
177 unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
178 PhysReg = getFreeReg(VirtReg);
180 // Add move instruction(s)
181 return RegInfo->loadRegOffset2Reg(MBB, I, PhysReg,
182 RegInfo->getFramePointer(),
183 -stackOffset, regClass->getDataSize());
186 MachineBasicBlock::iterator
187 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock *MBB,
188 MachineBasicBlock::iterator I,
189 unsigned VirtReg, unsigned PhysReg)
191 const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
194 unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
196 // Add move instruction(s)
197 return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
198 RegInfo->getFramePointer(),
199 -stackOffset, regClass->getDataSize());
202 MachineBasicBlock::iterator
203 RegAllocSimple::savePhysRegToStack (MachineBasicBlock *MBB,
204 MachineBasicBlock::iterator I,
207 const TargetRegisterClass* regClass = MF->getRegClass(PhysReg);
210 unsigned offset = allocateStackSpaceFor(PhysReg, regClass);
212 // Add move instruction(s)
213 return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
214 RegInfo->getFramePointer(),
215 offset, regClass->getDataSize());
218 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
219 cleanupAfterFunction();
221 unsigned virtualReg, physReg;
222 DEBUG(std::cerr << "Machine Function " << "\n");
225 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
230 // Handle PHI instructions specially: add moves to each pred block
231 while (MBB->front()->getOpcode() == 0) {
232 MachineInstr *MI = MBB->front();
233 // get rid of the phi
234 MBB->erase(MBB->begin());
236 // a preliminary pass that will invalidate any registers that
237 // are used by the instruction (including implicit uses)
238 invalidatePhysRegs(MI);
240 DEBUG(std::cerr << "num invalid regs: " << RegsUsed.size() << "\n");
242 DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
243 MachineOperand &targetReg = MI->getOperand(0);
245 // If it's a virtual register, allocate a physical one
246 // otherwise, just use whatever register is there now
247 // note: it MUST be a register -- we're assigning to it
248 virtualReg = (unsigned) targetReg.getAllocatedRegNum();
249 if (targetReg.isVirtualRegister()) {
250 physReg = getFreeReg(virtualReg);
252 physReg = virtualReg;
255 // Find the register class of the target register: should be the
256 // same as the values we're trying to store there
257 const TargetRegisterClass* regClass = PhysReg2RegClassMap[physReg];
258 assert(regClass && "Target register class not found!");
259 unsigned dataSize = regClass->getDataSize();
261 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
262 MachineOperand &opVal = MI->getOperand(i-1);
264 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
265 // source path the phi
266 MachineBasicBlock *opBlock = MI->getOperand(i).getMachineBasicBlock();
267 MachineBasicBlock::iterator opI = opBlock->end();
268 MachineInstr *opMI = *(--opI);
269 const MachineInstrInfo &MII = TM.getInstrInfo();
270 // must backtrack over ALL the branches in the previous block, until no more
271 while ((MII.isBranch(opMI->getOpcode()) || MII.isReturn(opMI->getOpcode()))
272 && opI != opBlock->begin())
276 // move back to the first branch instruction so new instructions
277 // are inserted right in front of it and not in front of a non-branch
281 // Retrieve the constant value from this op, move it to target
282 // register of the phi
283 if (opVal.getType() == MachineOperand::MO_SignExtendedImmed ||
284 opVal.getType() == MachineOperand::MO_UnextendedImmed)
286 opI = RegInfo->moveImm2Reg(opBlock, opI, physReg,
287 (unsigned) opVal.getImmedValue(),
289 saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
291 // Allocate a physical register and add a move in the BB
292 unsigned opVirtualReg = (unsigned) opVal.getAllocatedRegNum();
293 unsigned opPhysReg; // = getFreeReg(opVirtualReg);
294 opI = moveUseToReg(opBlock, opI, opVirtualReg, physReg);
295 //opI = RegInfo->moveReg2Reg(opBlock, opI, physReg, opPhysReg,
297 // Save that register value to the stack of the TARGET REG
298 saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
301 // make regs available to other instructions
305 // really delete the instruction
309 //loop over each basic block
310 for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I)
312 MachineInstr *MI = *I;
314 // a preliminary pass that will invalidate any registers that
315 // are used by the instruction (including implicit uses)
316 invalidatePhysRegs(MI);
318 // Loop over uses, move from memory into registers
319 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
320 MachineOperand &op = MI->getOperand(i);
322 if (op.getType() == MachineOperand::MO_SignExtendedImmed ||
323 op.getType() == MachineOperand::MO_UnextendedImmed)
325 DEBUG(std::cerr << "const\n");
326 } else if (op.isVirtualRegister()) {
327 virtualReg = (unsigned) op.getAllocatedRegNum();
328 DEBUG(std::cerr << "op: " << op << "\n");
329 DEBUG(std::cerr << "\t inst[" << i << "]: ";
330 MI->print(std::cerr, TM));
332 // make sure the same virtual register maps to the same physical
333 // register in any given instruction
334 if (VirtReg2PhysRegMap.find(virtualReg) != VirtReg2PhysRegMap.end()) {
335 physReg = VirtReg2PhysRegMap[virtualReg];
338 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
339 // must be same register number as the first operand
340 // This maps a = b + c into b += c, and saves b into a's spot
341 physReg = (unsigned) MI->getOperand(1).getAllocatedRegNum();
343 physReg = getFreeReg(virtualReg);
345 MachineBasicBlock::iterator J = I;
346 J = saveVirtRegToStack(CurrMBB, ++J, virtualReg, physReg);
349 I = moveUseToReg(CurrMBB, I, virtualReg, physReg);
351 VirtReg2PhysRegMap[virtualReg] = physReg;
353 MI->SetMachineOperandReg(i, physReg);
354 DEBUG(std::cerr << "virt: " << virtualReg <<
355 ", phys: " << op.getAllocatedRegNum() << "\n");
360 VirtReg2PhysRegMap.clear();
365 // add prologue we should preserve callee-save registers...
366 MachineFunction::iterator Fi = Fn.begin();
367 MachineBasicBlock *MBB = Fi;
368 MachineBasicBlock::iterator MBBi = MBB->begin();
369 RegInfo->emitPrologue(MBB, MBBi, NumBytesAllocated);
371 // add epilogue to restore the callee-save registers
372 // loop over the basic block
373 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
376 // check if last instruction is a RET
377 MachineBasicBlock::iterator I = (*MBB).end();
378 MachineInstr *MI = *(--I);
379 const MachineInstrInfo &MII = TM.getInstrInfo();
380 if (MII.isReturn(MI->getOpcode())) {
381 // this block has a return instruction, add epilogue
382 RegInfo->emitEpilogue(MBB, I, NumBytesAllocated);
386 return false; // We never modify the LLVM itself.
389 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
390 return new RegAllocSimple(TM);