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;
97 void cleanupAfterFunction() {
99 SSA2PhysRegMap.clear();
100 NumBytesAllocated = ByteAlignment;
103 /// Moves value from memory into that register
104 MachineBasicBlock::iterator
105 moveUseToReg (MachineBasicBlock *MBB,
106 MachineBasicBlock::iterator I, unsigned VirtReg,
109 /// Saves reg value on the stack (maps virtual register to stack value)
110 MachineBasicBlock::iterator
111 saveVirtRegToStack (MachineBasicBlock *MBB,
112 MachineBasicBlock::iterator I, unsigned VirtReg,
115 MachineBasicBlock::iterator
116 savePhysRegToStack (MachineBasicBlock *MBB,
117 MachineBasicBlock::iterator I, unsigned PhysReg);
119 /// runOnFunction - Top level implementation of instruction selection for
120 /// the entire function.
122 bool runOnMachineFunction(MachineFunction &Fn);
124 bool runOnFunction(Function &Fn) {
125 return runOnMachineFunction(MachineFunction::get(&Fn));
131 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
132 const TargetRegisterClass *regClass)
134 if (RegMap.find(VirtReg) == RegMap.end()) {
136 unsigned size = regClass->getDataSize();
137 unsigned over = NumBytesAllocated - (NumBytesAllocated % ByteAlignment);
138 if (size >= ByteAlignment - over) {
139 // need to pad by (ByteAlignment - over)
140 NumBytesAllocated += ByteAlignment - over;
142 RegMap[VirtReg] = NumBytesAllocated;
143 NumBytesAllocated += size;
145 // FIXME: forcing each arg to take 4 bytes on the stack
146 RegMap[VirtReg] = NumBytesAllocated;
147 NumBytesAllocated += ByteAlignment;
149 return RegMap[VirtReg];
152 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
153 const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
156 if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
157 unsigned regIdx = RegClassIdx[regClass]++;
158 assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
159 physReg = regClass->getRegister(regIdx);
161 physReg = regClass->getRegister(0);
162 // assert(physReg < regClass->getNumRegs() && "No registers in class!");
163 RegClassIdx[regClass] = 1;
166 if (isAvailableReg(physReg))
169 return getFreeReg(virtualReg);
173 MachineBasicBlock::iterator
174 RegAllocSimple::moveUseToReg (MachineBasicBlock *MBB,
175 MachineBasicBlock::iterator I,
176 unsigned VirtReg, unsigned &PhysReg)
178 const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
181 unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
182 PhysReg = getFreeReg(VirtReg);
184 // Add move instruction(s)
185 return RegInfo->loadRegOffset2Reg(MBB, I, PhysReg,
186 RegInfo->getFramePointer(),
187 -stackOffset, regClass->getDataSize());
190 MachineBasicBlock::iterator
191 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock *MBB,
192 MachineBasicBlock::iterator I,
193 unsigned VirtReg, unsigned PhysReg)
195 const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
198 unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
200 // Add move instruction(s)
201 return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
202 RegInfo->getFramePointer(),
203 -stackOffset, regClass->getDataSize());
206 MachineBasicBlock::iterator
207 RegAllocSimple::savePhysRegToStack (MachineBasicBlock *MBB,
208 MachineBasicBlock::iterator I,
211 const TargetRegisterClass* regClass = MF->getRegClass(PhysReg);
214 unsigned offset = allocateStackSpaceFor(PhysReg, regClass);
216 // Add move instruction(s)
217 return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
218 RegInfo->getFramePointer(),
219 offset, regClass->getDataSize());
222 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
223 cleanupAfterFunction();
225 unsigned virtualReg, physReg;
226 DEBUG(std::cerr << "Machine Function " << "\n");
229 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
234 // Handle PHI instructions specially: add moves to each pred block
235 while (MBB->front()->getOpcode() == 0) {
236 MachineInstr *MI = MBB->front();
237 // get rid of the phi
238 MBB->erase(MBB->begin());
240 // a preliminary pass that will invalidate any registers that
241 // are used by the instruction (including implicit uses)
242 invalidatePhysRegs(MI);
244 DEBUG(std::cerr << "num invalid regs: " << RegsUsed.size() << "\n");
246 DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
247 MachineOperand &targetReg = MI->getOperand(0);
249 // If it's a virtual register, allocate a physical one
250 // otherwise, just use whatever register is there now
251 // note: it MUST be a register -- we're assigning to it
252 virtualReg = (unsigned) targetReg.getAllocatedRegNum();
253 if (targetReg.isVirtualRegister()) {
254 physReg = getFreeReg(virtualReg);
256 physReg = targetReg.getAllocatedRegNum();
259 // Find the register class of the target register: should be the
260 // same as the values we're trying to store there
261 const TargetRegisterClass* regClass = PhysReg2RegClassMap[physReg];
262 assert(regClass && "Target register class not found!");
263 unsigned dataSize = regClass->getDataSize();
265 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
266 MachineOperand &opVal = MI->getOperand(i-1);
268 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
269 // source path the phi
271 cast<BasicBlock>(MI->getOperand(i).getVRegValue());
272 MachineBasicBlock *opBlock = NULL;
273 for (MachineFunction::iterator opFi = Fn.begin(), opFe = Fn.end();
274 opFi != opFe; ++opFi)
276 if (opFi->getBasicBlock() == opBB) {
277 opBlock = opFi; break;
280 assert(opBlock && "MachineBasicBlock object not found for specified block!");
282 MachineBasicBlock::iterator opI = opBlock->end();
283 MachineInstr *opMI = *(--opI);
284 const MachineInstrInfo &MII = TM.getInstrInfo();
285 // must backtrack over ALL the branches in the previous block, until no more
286 while ((MII.isBranch(opMI->getOpcode()) || MII.isReturn(opMI->getOpcode()))
287 && opI != opBlock->begin())
291 // move back to the first branch instruction so new instructions
292 // are inserted right in front of it and not in front of a non-branch
296 // insert the move just before the return/branch
297 if (MII.isReturn(opMI->getOpcode()) || MII.isBranch(opMI->getOpcode()))
299 // Retrieve the constant value from this op, move it to target
300 // register of the phi
301 if (opVal.getType() == MachineOperand::MO_SignExtendedImmed ||
302 opVal.getType() == MachineOperand::MO_UnextendedImmed)
304 opI = RegInfo->moveImm2Reg(opBlock, opI, physReg,
305 (unsigned) opVal.getImmedValue(),
307 saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
309 // Allocate a physical register and add a move in the BB
310 unsigned opVirtualReg = (unsigned) opVal.getAllocatedRegNum();
311 unsigned opPhysReg; // = getFreeReg(opVirtualReg);
312 opI = moveUseToReg(opBlock, opI, opVirtualReg, opPhysReg);
313 opI = RegInfo->moveReg2Reg(opBlock, opI, physReg, opPhysReg,
315 // Save that register value to the stack of the TARGET REG
316 saveVirtRegToStack(opBlock, opI, virtualReg, opPhysReg);
320 // make regs available to other instructions
324 // really delete the instruction
328 //loop over each basic block
329 for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I)
331 MachineInstr *MI = *I;
333 // a preliminary pass that will invalidate any registers that
334 // are used by the instruction (including implicit uses)
335 invalidatePhysRegs(MI);
337 // Loop over uses, move from memory into registers
338 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
339 MachineOperand &op = MI->getOperand(i);
341 if (op.getType() == MachineOperand::MO_SignExtendedImmed ||
342 op.getType() == MachineOperand::MO_UnextendedImmed)
344 DEBUG(std::cerr << "const\n");
345 } else if (op.isVirtualRegister()) {
346 virtualReg = (unsigned) op.getAllocatedRegNum();
347 DEBUG(std::cerr << "op: " << op << "\n");
348 DEBUG(std::cerr << "\t inst[" << i << "]: ";
349 MI->print(std::cerr, TM));
351 // make sure the same virtual register maps to the same physical
352 // register in any given instruction
353 if (VirtReg2PhysRegMap.find(virtualReg) != VirtReg2PhysRegMap.end()) {
354 physReg = VirtReg2PhysRegMap[virtualReg];
357 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
358 // must be same register number as the first operand
359 // This maps a = b + c into b += c, and saves b into a's spot
360 physReg = (unsigned) MI->getOperand(1).getAllocatedRegNum();
362 physReg = getFreeReg(virtualReg);
364 MachineBasicBlock::iterator J = I;
365 J = saveVirtRegToStack(CurrMBB, ++J, virtualReg, physReg);
368 I = moveUseToReg(CurrMBB, I, virtualReg, physReg);
370 VirtReg2PhysRegMap[virtualReg] = physReg;
372 MI->SetMachineOperandReg(i, physReg);
373 DEBUG(std::cerr << "virt: " << virtualReg <<
374 ", phys: " << op.getAllocatedRegNum() << "\n");
379 VirtReg2PhysRegMap.clear();
384 // add prologue we should preserve callee-save registers...
385 MachineFunction::iterator Fi = Fn.begin();
386 MachineBasicBlock *MBB = Fi;
387 MachineBasicBlock::iterator MBBi = MBB->begin();
388 RegInfo->emitPrologue(MBB, MBBi, NumBytesAllocated);
390 // add epilogue to restore the callee-save registers
391 // loop over the basic block
392 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
395 // check if last instruction is a RET
396 MachineBasicBlock::iterator I = (*MBB).end();
397 MachineInstr *MI = *(--I);
398 const MachineInstrInfo &MII = TM.getInstrInfo();
399 if (MII.isReturn(MI->getOpcode())) {
400 // this block has a return instruction, add epilogue
401 RegInfo->emitEpilogue(MBB, I, NumBytesAllocated);
405 return false; // We never modify the LLVM itself.
408 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
409 return new RegAllocSimple(TM);