1 //===-- RegAllocSimple.cpp - A simple generic register allocator ----------===//
3 // This file implements a simple register allocator. *Very* simple: It immediate
4 // spills every value right after it is computed, and it reloads all used
5 // operands from the spill area to temporary registers before each instruction.
6 // It does not keep values in registers across instructions.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/CodeGen/Passes.h"
11 #include "llvm/CodeGen/MachineFunctionPass.h"
12 #include "llvm/CodeGen/MachineInstr.h"
13 #include "llvm/CodeGen/SSARegMap.h"
14 #include "llvm/CodeGen/MachineFrameInfo.h"
15 #include "llvm/Target/TargetInstrInfo.h"
16 #include "llvm/Target/TargetMachine.h"
17 #include "Support/Debug.h"
18 #include "Support/Statistic.h"
22 Statistic<> NumSpilled ("ra-simple", "Number of registers spilled");
23 Statistic<> NumReloaded("ra-simple", "Number of registers reloaded");
25 class RegAllocSimple : public MachineFunctionPass {
27 const TargetMachine *TM;
28 const MRegisterInfo *RegInfo;
30 // StackSlotForVirtReg - Maps SSA Regs => frame index on the stack where
31 // these values are spilled
32 std::map<unsigned, int> StackSlotForVirtReg;
34 // RegsUsed - Keep track of what registers are currently in use. This is a
36 std::vector<bool> RegsUsed;
38 // RegClassIdx - Maps RegClass => which index we can take a register
39 // from. Since this is a simple register allocator, when we need a register
40 // of a certain class, we just take the next available one.
41 std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
44 virtual const char *getPassName() const {
45 return "Simple Register Allocator";
48 /// runOnMachineFunction - Register allocate the whole function
49 bool runOnMachineFunction(MachineFunction &Fn);
51 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
52 AU.addRequiredID(PHIEliminationID); // Eliminate PHI nodes
53 MachineFunctionPass::getAnalysisUsage(AU);
56 /// AllocateBasicBlock - Register allocate the specified basic block.
57 void AllocateBasicBlock(MachineBasicBlock &MBB);
59 /// getStackSpaceFor - This returns the offset of the specified virtual
60 /// register on the stack, allocating space if neccesary.
61 int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
63 /// Given a virtual register, return a compatible physical register that is
66 /// Side effect: marks that register as being used until manually cleared
68 unsigned getFreeReg(unsigned virtualReg);
70 /// Moves value from memory into that register
71 unsigned reloadVirtReg(MachineBasicBlock &MBB,
72 MachineBasicBlock::iterator &I, unsigned VirtReg);
74 /// Saves reg value on the stack (maps virtual register to stack value)
75 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
76 unsigned VirtReg, unsigned PhysReg);
81 /// getStackSpaceFor - This allocates space for the specified virtual
82 /// register to be held on the stack.
83 int RegAllocSimple::getStackSpaceFor(unsigned VirtReg,
84 const TargetRegisterClass *RC) {
85 // Find the location VirtReg would belong...
86 std::map<unsigned, int>::iterator I =
87 StackSlotForVirtReg.lower_bound(VirtReg);
89 if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
90 return I->second; // Already has space allocated?
92 // Allocate a new stack object for this spill location...
93 int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC);
96 StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
101 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
102 const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(virtualReg);
103 TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
104 TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
107 unsigned regIdx = RegClassIdx[RC]++;
108 assert(RI+regIdx != RE && "Not enough registers!");
109 unsigned PhysReg = *(RI+regIdx);
111 if (!RegsUsed[PhysReg])
116 unsigned RegAllocSimple::reloadVirtReg(MachineBasicBlock &MBB,
117 MachineBasicBlock::iterator &I,
119 const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
120 int FrameIdx = getStackSpaceFor(VirtReg, RC);
121 unsigned PhysReg = getFreeReg(VirtReg);
123 // Add move instruction(s)
125 RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIdx, RC);
129 void RegAllocSimple::spillVirtReg(MachineBasicBlock &MBB,
130 MachineBasicBlock::iterator &I,
131 unsigned VirtReg, unsigned PhysReg) {
132 const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VirtReg);
133 int FrameIdx = getStackSpaceFor(VirtReg, RC);
135 // Add move instruction(s)
137 RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIdx, RC);
141 void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
142 // loop over each instruction
143 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
144 // Made to combat the incorrect allocation of r2 = add r1, r1
145 std::map<unsigned, unsigned> Virt2PhysRegMap;
147 MachineInstr *MI = *I;
149 RegsUsed.resize(MRegisterInfo::FirstVirtualRegister);
151 // a preliminary pass that will invalidate any registers that
152 // are used by the instruction (including implicit uses)
153 unsigned Opcode = MI->getOpcode();
154 const TargetInstrDescriptor &Desc = TM->getInstrInfo().get(Opcode);
155 if (const unsigned *Regs = Desc.ImplicitUses)
157 RegsUsed[*Regs++] = true;
159 if (const unsigned *Regs = Desc.ImplicitDefs)
161 RegsUsed[*Regs++] = true;
163 // Loop over uses, move from memory into registers
164 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
165 MachineOperand &op = MI->getOperand(i);
167 if (op.isVirtualRegister()) {
168 unsigned virtualReg = (unsigned) op.getAllocatedRegNum();
169 DEBUG(std::cerr << "op: " << op << "\n");
170 DEBUG(std::cerr << "\t inst[" << i << "]: ";
171 MI->print(std::cerr, *TM));
173 // make sure the same virtual register maps to the same physical
174 // register in any given instruction
175 unsigned physReg = Virt2PhysRegMap[virtualReg];
177 if (op.opIsDefOnly() || op.opIsDefAndUse()) {
178 if (TM->getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
179 // must be same register number as the first operand
180 // This maps a = b + c into b += c, and saves b into a's spot
181 assert(MI->getOperand(1).isRegister() &&
182 MI->getOperand(1).getAllocatedRegNum() &&
183 MI->getOperand(1).opIsUse() &&
184 "Two address instruction invalid!");
186 physReg = MI->getOperand(1).getAllocatedRegNum();
188 physReg = getFreeReg(virtualReg);
191 spillVirtReg(MBB, I, virtualReg, physReg);
194 physReg = reloadVirtReg(MBB, I, virtualReg);
195 Virt2PhysRegMap[virtualReg] = physReg;
198 MI->SetMachineOperandReg(i, physReg);
199 DEBUG(std::cerr << "virt: " << virtualReg <<
200 ", phys: " << op.getAllocatedRegNum() << "\n");
209 /// runOnMachineFunction - Register allocate the whole function
211 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
212 DEBUG(std::cerr << "Machine Function " << "\n");
214 TM = &MF->getTarget();
215 RegInfo = TM->getRegisterInfo();
217 // Loop over all of the basic blocks, eliminating virtual register references
218 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
220 AllocateBasicBlock(*MBB);
222 StackSlotForVirtReg.clear();
226 Pass *createSimpleRegisterAllocator() {
227 return new RegAllocSimple();