1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
3 // This register allocator allocates registers to a basic block at a time,
4 // attempting to keep values in registers and reusing registers as appropriate.
6 //===----------------------------------------------------------------------===//
8 #include "llvm/CodeGen/MachineFunction.h"
9 #include "llvm/CodeGen/MachineInstr.h"
10 #include "llvm/Target/MachineInstrInfo.h"
11 #include "llvm/Target/TargetMachine.h"
12 #include "Support/Statistic.h"
16 Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
17 Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
19 class RA : public FunctionPass {
22 const MRegisterInfo &RegInfo;
23 const MachineInstrInfo &MIInfo;
24 unsigned NumBytesAllocated;
26 // Maps SSA Regs => offsets on the stack where these values are stored
27 std::map<unsigned, unsigned> VirtReg2OffsetMap;
29 // Virt2PhysRegMap - This map contains entries for each virtual register
30 // that is currently available in a physical register.
32 std::map<unsigned, unsigned> Virt2PhysRegMap;
34 // PhysRegsUsed - This map contains entries for each physical register that
35 // currently has a value (ie, it is in Virt2PhysRegMap). The value mapped
36 // to is the virtual register corresponding to the physical register (the
37 // inverse of the Virt2PhysRegMap), or 0. The value is set to 0 if this
38 // register is pinned because it is used by a future instruction.
40 std::map<unsigned, unsigned> PhysRegsUsed;
42 // PhysRegsUseOrder - This contains a list of the physical registers that
43 // currently have a virtual register value in them. This list provides an
44 // ordering of registers, imposing a reallocation order. This list is only
45 // used if all registers are allocated and we have to spill one, in which
46 // case we spill the least recently used register. Entries at the front of
47 // the list are the least recently used registers, entries at the back are
48 // the most recently used.
50 std::vector<unsigned> PhysRegsUseOrder;
52 void MarkPhysRegRecentlyUsed(unsigned Reg) {
53 assert(std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg) !=
54 PhysRegsUseOrder.end() && "Register isn't used yet!");
55 if (PhysRegsUseOrder.back() != Reg) {
56 for (unsigned i = PhysRegsUseOrder.size(); ; --i)
57 if (PhysRegsUseOrder[i-1] == Reg) { // remove from middle
58 PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
59 PhysRegsUseOrder.push_back(Reg); // Add it to the end of the list
68 : TM(tm), RegInfo(*tm.getRegisterInfo()), MIInfo(tm.getInstrInfo()) {
69 cleanupAfterFunction();
72 bool runOnFunction(Function &Fn) {
73 return runOnMachineFunction(MachineFunction::get(&Fn));
76 virtual const char *getPassName() const {
77 return "Local Register Allocator";
81 /// runOnMachineFunction - Register allocate the whole function
82 bool runOnMachineFunction(MachineFunction &Fn);
84 /// AllocateBasicBlock - Register allocate the specified basic block.
85 void AllocateBasicBlock(MachineBasicBlock &MBB);
87 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
88 /// in predecessor basic blocks.
89 void EliminatePHINodes(MachineBasicBlock &MBB);
91 /// EmitPrologue/EmitEpilogue - Use the register info object to add a
92 /// prologue/epilogue to the function and save/restore any callee saved
93 /// registers we are responsible for.
96 void EmitEpilogue(MachineBasicBlock &MBB);
98 /// isAllocatableRegister - A register may be used by the program if it's
99 /// not the stack or frame pointer.
100 bool isAllocatableRegister(unsigned R) const {
101 unsigned FP = RegInfo.getFramePointer(), SP = RegInfo.getStackPointer();
102 // Don't allocate the Frame or Stack pointers
103 if (R == FP || R == SP)
106 // Check to see if this register aliases the stack or frame pointer...
107 if (const unsigned *AliasSet = RegInfo.getAliasSet(R)) {
108 for (unsigned i = 0; AliasSet[i]; ++i)
109 if (AliasSet[i] == FP || AliasSet[i] == SP)
115 /// getStackSpaceFor - This returns the offset of the specified virtual
116 /// register on the stack, allocating space if neccesary.
117 unsigned getStackSpaceFor(unsigned VirtReg,
118 const TargetRegisterClass *regClass);
120 void cleanupAfterFunction() {
121 VirtReg2OffsetMap.clear();
122 NumBytesAllocated = 4; // FIXME: This is X86 specific
126 /// spillVirtReg - This method spills the value specified by PhysReg into
127 /// the virtual register slot specified by VirtReg. It then updates the RA
128 /// data structures to indicate the fact that PhysReg is now available.
130 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
131 unsigned VirtReg, unsigned PhysReg);
133 /// spillPhysReg - This method spills the specified physical register into
134 /// the virtual register slot associated with it.
136 void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
138 std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
139 if (PI != PhysRegsUsed.end()) // Only spill it if it's used!
140 spillVirtReg(MBB, I, PI->second, PhysReg);
143 void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
145 /// isPhysRegAvailable - Return true if the specified physical register is
146 /// free and available for use. This also includes checking to see if
147 /// aliased registers are all free...
149 bool RA::isPhysRegAvailable(unsigned PhysReg) const;
151 /// getFreeReg - Find a physical register to hold the specified virtual
152 /// register. If all compatible physical registers are used, this method
153 /// spills the last used virtual register to the stack, and uses that
156 unsigned getFreeReg(MachineBasicBlock &MBB,
157 MachineBasicBlock::iterator &I,
158 unsigned virtualReg);
160 /// reloadVirtReg - This method loads the specified virtual register into a
161 /// physical register, returning the physical register chosen. This updates
162 /// the regalloc data structures to reflect the fact that the virtual reg is
163 /// now alive in a physical register, and the previous one isn't.
165 unsigned reloadVirtReg(MachineBasicBlock &MBB,
166 MachineBasicBlock::iterator &I, unsigned VirtReg);
171 /// getStackSpaceFor - This allocates space for the specified virtual
172 /// register to be held on the stack.
173 unsigned RA::getStackSpaceFor(unsigned VirtReg,
174 const TargetRegisterClass *RegClass) {
175 // Find the location VirtReg would belong...
176 std::map<unsigned, unsigned>::iterator I =
177 VirtReg2OffsetMap.lower_bound(VirtReg);
179 if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
180 return I->second; // Already has space allocated?
182 unsigned RegSize = RegClass->getDataSize();
184 // Align NumBytesAllocated. We should be using TargetData alignment stuff
185 // to determine this, but we don't know the LLVM type associated with the
186 // virtual register. Instead, just align to a multiple of the size for now.
187 NumBytesAllocated += RegSize-1;
188 NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
190 // Assign the slot...
191 VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
193 // Reserve the space!
194 NumBytesAllocated += RegSize;
195 return NumBytesAllocated-RegSize;
199 /// spillVirtReg - This method spills the value specified by PhysReg into the
200 /// virtual register slot specified by VirtReg. It then updates the RA data
201 /// structures to indicate the fact that PhysReg is now available.
203 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
204 unsigned VirtReg, unsigned PhysReg) {
205 // If this is just a marker register, we don't need to spill it.
207 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
208 unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
210 // Add move instruction(s)
211 I = RegInfo.storeReg2RegOffset(MBB, I, PhysReg, RegInfo.getFramePointer(),
212 -stackOffset, RegClass->getDataSize());
213 ++NumSpilled; // Update statistics
214 Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available
216 PhysRegsUsed.erase(PhysReg); // PhyReg no longer used
218 std::vector<unsigned>::iterator It =
219 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
220 assert(It != PhysRegsUseOrder.end() &&
221 "Spilled a physical register, but it was not in use list!");
222 PhysRegsUseOrder.erase(It);
226 /// isPhysRegAvailable - Return true if the specified physical register is free
227 /// and available for use. This also includes checking to see if aliased
228 /// registers are all free...
230 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
231 if (PhysRegsUsed.count(PhysReg)) return false;
233 // If the selected register aliases any other allocated registers, it is
235 if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
236 for (unsigned i = 0; AliasSet[i]; ++i)
237 if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use?
238 return false; // Can't use this reg then.
244 /// getFreeReg - Find a physical register to hold the specified virtual
245 /// register. If all compatible physical registers are used, this method spills
246 /// the last used virtual register to the stack, and uses that register.
248 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
250 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
251 unsigned PhysReg = 0;
253 // First check to see if we have a free register of the requested type...
254 for (TargetRegisterClass::iterator It = RegClass->begin(),E = RegClass->end();
257 if (isPhysRegAvailable(R)) { // Is reg unused?
258 if (isAllocatableRegister(R)) { // And is not a frame register?
259 // Found an unused register!
266 // If we didn't find an unused register, scavenge one now!
268 assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
270 // Loop over all of the preallocated registers from the least recently used
271 // to the most recently used. When we find one that is capable of holding
272 // our register, use it.
273 for (unsigned i = 0; PhysReg == 0; ++i) {
274 assert(i != PhysRegsUseOrder.size() &&
275 "Couldn't find a register of the appropriate class!");
277 unsigned R = PhysRegsUseOrder[i];
278 // If the current register is compatible, use it.
279 if (isAllocatableRegister(R)) {
280 if (RegInfo.getRegClass(R) == RegClass) {
284 // If one of the registers aliased to the current register is
285 // compatible, use it.
286 if (const unsigned *AliasSet = RegInfo.getAliasSet(R))
287 for (unsigned a = 0; AliasSet[a]; ++a)
288 if (RegInfo.getRegClass(AliasSet[a]) == RegClass) {
289 PhysReg = AliasSet[a]; // Take an aliased register
296 assert(isAllocatableRegister(PhysReg) && "Register is not allocatable!");
298 assert(PhysReg && "Physical register not assigned!?!?");
300 // At this point PhysRegsUseOrder[i] is the least recently used register of
301 // compatible register class. Spill it to memory and reap its remains.
302 spillPhysReg(MBB, I, PhysReg);
304 // If the selected register aliases any other registers, we must make sure
305 // to spill them as well...
306 if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
307 for (unsigned i = 0; AliasSet[i]; ++i)
308 if (PhysRegsUsed.count(AliasSet[i])) // Spill aliased register...
309 spillPhysReg(MBB, I, AliasSet[i]);
312 // Now that we know which register we need to assign this to, do it now!
313 AssignVirtToPhysReg(VirtReg, PhysReg);
318 void RA::AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
319 assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
320 "Phys reg already assigned!");
321 // Update information to note the fact that this register was just used, and
323 PhysRegsUsed[PhysReg] = VirtReg;
324 Virt2PhysRegMap[VirtReg] = PhysReg;
325 PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg
329 /// reloadVirtReg - This method loads the specified virtual register into a
330 /// physical register, returning the physical register chosen. This updates the
331 /// regalloc data structures to reflect the fact that the virtual reg is now
332 /// alive in a physical register, and the previous one isn't.
334 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
335 MachineBasicBlock::iterator &I,
337 std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
338 if (It != Virt2PhysRegMap.end()) {
339 MarkPhysRegRecentlyUsed(It->second);
340 return It->second; // Already have this value available!
343 unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
345 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
346 unsigned StackOffset = getStackSpaceFor(VirtReg, RegClass);
348 // Add move instruction(s)
349 I = RegInfo.loadRegOffset2Reg(MBB, I, PhysReg, RegInfo.getFramePointer(),
350 -StackOffset, RegClass->getDataSize());
351 ++NumReloaded; // Update statistics
356 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
357 /// predecessor basic blocks.
359 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
360 const MachineInstrInfo &MII = TM.getInstrInfo();
362 while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
363 MachineInstr *MI = MBB.front();
364 // Unlink the PHI node from the basic block... but don't delete the PHI yet
365 MBB.erase(MBB.begin());
367 DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
368 assert(MI->getOperand(0).isVirtualRegister() &&
369 "PHI node doesn't write virt reg?");
371 unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
373 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
374 MachineOperand &opVal = MI->getOperand(i-1);
376 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
377 // source path the phi
378 MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
380 // Check to make sure we haven't already emitted the copy for this block.
381 // This can happen because PHI nodes may have multiple entries for the
382 // same basic block. It doesn't matter which entry we use though, because
383 // all incoming values are guaranteed to be the same for a particular bb.
385 // Note that this is N^2 in the number of phi node entries, but since the
386 // # of entries is tiny, this is not a problem.
388 bool HaveNotEmitted = true;
389 for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
390 if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
391 HaveNotEmitted = false;
395 if (HaveNotEmitted) {
396 MachineBasicBlock::iterator opI = opBlock.end();
397 MachineInstr *opMI = *--opI;
399 // must backtrack over ALL the branches in the previous block
400 while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
403 // move back to the first branch instruction so new instructions
404 // are inserted right in front of it and not in front of a non-branch
405 if (!MII.isBranch(opMI->getOpcode()))
408 unsigned dataSize = MF->getRegClass(virtualReg)->getDataSize();
410 // Retrieve the constant value from this op, move it to target
411 // register of the phi
412 if (opVal.isImmediate()) {
413 opI = RegInfo.moveImm2Reg(opBlock, opI, virtualReg,
414 (unsigned) opVal.getImmedValue(),
417 opI = RegInfo.moveReg2Reg(opBlock, opI, virtualReg,
418 opVal.getAllocatedRegNum(), dataSize);
423 // really delete the PHI instruction now!
429 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
430 // loop over each instruction
431 MachineBasicBlock::iterator I = MBB.begin();
432 for (; I != MBB.end(); ++I) {
433 MachineInstr *MI = *I;
434 const MachineInstrDescriptor &MID = MIInfo.get(MI->getOpcode());
436 // Loop over all of the operands of the instruction, spilling registers that
437 // are defined, and marking explicit destinations in the PhysRegsUsed map.
438 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
439 if (MI->getOperand(i).opIsDef() &&
440 MI->getOperand(i).isPhysicalRegister()) {
441 unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
442 spillPhysReg(MBB, I, Reg);
443 PhysRegsUsed[Reg] = 0; // It's free now, and it's reserved
444 PhysRegsUseOrder.push_back(Reg);
447 // Loop over the implicit defs, spilling them, as above.
448 if (const unsigned *ImplicitDefs = MID.ImplicitDefs)
449 for (unsigned i = 0; ImplicitDefs[i]; ++i) {
450 unsigned Reg = ImplicitDefs[i];
451 spillPhysReg(MBB, I, Reg);
452 PhysRegsUsed[Reg] = 0; // It's free now, and it's reserved
453 PhysRegsUseOrder.push_back(Reg);
456 // Loop over the implicit uses, making sure that they are at the head of the
457 // use order list, so they don't get reallocated.
458 if (const unsigned *ImplicitUses = MID.ImplicitUses)
459 for (unsigned i = 0; ImplicitUses[i]; ++i)
460 MarkPhysRegRecentlyUsed(ImplicitUses[i]);
462 // Loop over all of the operands again, getting the used operands into
463 // registers. This has the potiential to spill incoming values because we
464 // are out of registers.
466 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
467 if (MI->getOperand(i).opIsUse() &&
468 MI->getOperand(i).isVirtualRegister()) {
469 unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
470 unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
471 MI->SetMachineOperandReg(i, PhysSrcReg); // Assign the input register
474 // Okay, we have allocated all of the source operands and spilled any values
475 // that would be destroyed by defs of this instruction. Loop over the
476 // implicit defs and assign them to a register, spilling the incoming value
477 // if we need to scavange a register.
479 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
480 if (MI->getOperand(i).opIsDef() &&
481 !MI->getOperand(i).isPhysicalRegister()) {
482 unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
483 unsigned DestPhysReg;
485 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
486 // must be same register number as the first operand
487 // This maps a = b + c into b += c, and saves b into a's spot
488 assert(MI->getOperand(1).isRegister() &&
489 MI->getOperand(1).getAllocatedRegNum() &&
490 MI->getOperand(1).opIsUse() &&
491 "Two address instruction invalid!");
492 DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
494 // Spill the incoming value, because we are about to change the
495 // register contents.
496 spillPhysReg(MBB, I, DestPhysReg);
497 AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
499 DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
501 MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register
505 // Rewind the iterator to point to the first flow control instruction...
506 const MachineInstrInfo &MII = TM.getInstrInfo();
510 } while ((MII.isReturn((*I)->getOpcode()) ||
511 MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
513 if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
516 // Spill all physical registers holding virtual registers now.
517 while (!PhysRegsUsed.empty())
518 spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
519 PhysRegsUsed.begin()->first);
521 assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
522 assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
526 /// EmitPrologue - Use the register info object to add a prologue to the
527 /// function and save any callee saved registers we are responsible for.
529 void RA::EmitPrologue() {
530 // Get a list of the callee saved registers, so that we can save them on entry
534 MachineBasicBlock &MBB = MF->front(); // Prolog goes in entry BB
535 MachineBasicBlock::iterator I = MBB.begin();
537 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
538 for (unsigned i = 0; CSRegs[i]; ++i) {
539 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
540 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
542 // Insert the spill to the stack frame...
544 I = RegInfo.storeReg2RegOffset(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
545 -Offset, RegClass->getDataSize());
548 // Add prologue to the function...
549 RegInfo.emitPrologue(*MF, NumBytesAllocated);
553 /// EmitEpilogue - Use the register info object to add a epilogue to the
554 /// function and restore any callee saved registers we are responsible for.
556 void RA::EmitEpilogue(MachineBasicBlock &MBB) {
557 // Insert instructions before the return.
558 MachineBasicBlock::iterator I = --MBB.end();
560 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
561 for (unsigned i = 0; CSRegs[i]; ++i) {
562 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
563 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
565 I = RegInfo.loadRegOffset2Reg(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
566 -Offset, RegClass->getDataSize());
567 --I; // Insert in reverse order
570 RegInfo.emitEpilogue(MBB, NumBytesAllocated);
574 /// runOnMachineFunction - Register allocate the whole function
576 bool RA::runOnMachineFunction(MachineFunction &Fn) {
577 DEBUG(std::cerr << "Machine Function " << "\n");
580 // First pass: eliminate PHI instructions by inserting copies into predecessor
582 // FIXME: In this pass, count how many uses of each VReg exist!
583 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
584 MBB != MBBe; ++MBB) {
585 EliminatePHINodes(*MBB);
588 // Loop over all of the basic blocks, eliminating virtual register references
589 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
591 AllocateBasicBlock(*MBB);
594 // Emit a prologue for the function...
597 const MachineInstrInfo &MII = TM.getInstrInfo();
599 // Add epilogue to restore the callee-save registers in each exiting block
600 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
601 MBB != MBBe; ++MBB) {
602 // If last instruction is a return instruction, add an epilogue
603 if (MII.isReturn(MBB->back()->getOpcode()))
607 cleanupAfterFunction();
611 Pass *createLocalRegisterAllocator(TargetMachine &TM) {