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"
13 #include "Support/CommandLine.h"
17 Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
18 Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
19 cl::opt<bool> DisableKill("no-kill", cl::Hidden,
20 cl::desc("Disable register kill in local-ra"));
22 class RA : public FunctionPass {
25 const MRegisterInfo &RegInfo;
26 const MachineInstrInfo &MIInfo;
27 unsigned NumBytesAllocated;
29 // Maps SSA Regs => offsets on the stack where these values are stored
30 std::map<unsigned, unsigned> VirtReg2OffsetMap;
32 // Virt2PhysRegMap - This map contains entries for each virtual register
33 // that is currently available in a physical register.
35 std::map<unsigned, unsigned> Virt2PhysRegMap;
37 // PhysRegsUsed - This map contains entries for each physical register that
38 // currently has a value (ie, it is in Virt2PhysRegMap). The value mapped
39 // to is the virtual register corresponding to the physical register (the
40 // inverse of the Virt2PhysRegMap), or 0. The value is set to 0 if this
41 // register is pinned because it is used by a future instruction.
43 std::map<unsigned, unsigned> PhysRegsUsed;
45 // PhysRegsUseOrder - This contains a list of the physical registers that
46 // currently have a virtual register value in them. This list provides an
47 // ordering of registers, imposing a reallocation order. This list is only
48 // used if all registers are allocated and we have to spill one, in which
49 // case we spill the least recently used register. Entries at the front of
50 // the list are the least recently used registers, entries at the back are
51 // the most recently used.
53 std::vector<unsigned> PhysRegsUseOrder;
55 // LastUserOf map - This multimap contains the set of registers that each
56 // key instruction is the last user of. If an instruction has an entry in
57 // this map, that means that the specified operands are killed after the
58 // instruction is executed, thus they don't need to be spilled into memory
60 std::multimap<MachineInstr*, unsigned> LastUserOf;
62 void MarkPhysRegRecentlyUsed(unsigned Reg) {
63 assert(!PhysRegsUseOrder.empty() && "No registers used!");
64 if (PhysRegsUseOrder.back() == Reg) return; // Already most recently used
66 for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
67 if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
68 unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle
69 PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
70 // Add it to the end of the list
71 PhysRegsUseOrder.push_back(RegMatch);
73 return; // Found an exact match, exit early
80 : TM(tm), RegInfo(*tm.getRegisterInfo()), MIInfo(tm.getInstrInfo()) {
81 cleanupAfterFunction();
84 bool runOnFunction(Function &Fn) {
85 return runOnMachineFunction(MachineFunction::get(&Fn));
88 virtual const char *getPassName() const {
89 return "Local Register Allocator";
93 /// runOnMachineFunction - Register allocate the whole function
94 bool runOnMachineFunction(MachineFunction &Fn);
96 /// AllocateBasicBlock - Register allocate the specified basic block.
97 void AllocateBasicBlock(MachineBasicBlock &MBB);
99 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
100 /// in predecessor basic blocks.
101 void EliminatePHINodes(MachineBasicBlock &MBB);
103 /// CalculateLastUseOfVReg - Calculate an approximation of the killing
104 /// uses for the virtual registers in the function. Here we try to capture
105 /// registers that are defined and only used within the same basic block.
106 /// Because we don't have use-def chains yet, we have to do this the hard
109 void CalculateLastUseOfVReg(MachineBasicBlock &MBB,
110 std::map<unsigned, MachineInstr*> &LastUseOfVReg) const;
113 /// EmitPrologue/EmitEpilogue - Use the register info object to add a
114 /// prologue/epilogue to the function and save/restore any callee saved
115 /// registers we are responsible for.
118 void EmitEpilogue(MachineBasicBlock &MBB);
120 /// areRegsEqual - This method returns true if the specified registers are
121 /// related to each other. To do this, it checks to see if they are equal
122 /// or if the first register is in the alias set of the second register.
124 bool areRegsEqual(unsigned R1, unsigned R2) const {
125 if (R1 == R2) return true;
126 if (const unsigned *AliasSet = RegInfo.getAliasSet(R2))
127 for (unsigned i = 0; AliasSet[i]; ++i)
128 if (AliasSet[i] == R1) return true;
132 /// isAllocatableRegister - A register may be used by the program if it's
133 /// not the stack or frame pointer.
134 bool isAllocatableRegister(unsigned R) const {
135 unsigned FP = RegInfo.getFramePointer(), SP = RegInfo.getStackPointer();
136 return !areRegsEqual(FP, R) && !areRegsEqual(SP, R);
139 /// getStackSpaceFor - This returns the offset of the specified virtual
140 /// register on the stack, allocating space if neccesary.
141 unsigned getStackSpaceFor(unsigned VirtReg,
142 const TargetRegisterClass *regClass);
144 void cleanupAfterFunction() {
145 VirtReg2OffsetMap.clear();
146 NumBytesAllocated = 4; // FIXME: This is X86 specific
149 void removePhysReg(unsigned PhysReg);
151 /// spillVirtReg - This method spills the value specified by PhysReg into
152 /// the virtual register slot specified by VirtReg. It then updates the RA
153 /// data structures to indicate the fact that PhysReg is now available.
155 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
156 unsigned VirtReg, unsigned PhysReg);
158 /// spillPhysReg - This method spills the specified physical register into
159 /// the virtual register slot associated with it.
161 void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
163 std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
164 if (PI != PhysRegsUsed.end()) { // Only spill it if it's used!
165 spillVirtReg(MBB, I, PI->second, PhysReg);
166 } else if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg)) {
167 // If the selected register aliases any other registers, we must make
168 // sure that one of the aliases isn't alive...
169 for (unsigned i = 0; AliasSet[i]; ++i) {
170 PI = PhysRegsUsed.find(AliasSet[i]);
171 if (PI != PhysRegsUsed.end()) // Spill aliased register...
172 spillVirtReg(MBB, I, PI->second, AliasSet[i]);
177 void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
179 /// isPhysRegAvailable - Return true if the specified physical register is
180 /// free and available for use. This also includes checking to see if
181 /// aliased registers are all free...
183 bool isPhysRegAvailable(unsigned PhysReg) const;
185 /// getFreeReg - Find a physical register to hold the specified virtual
186 /// register. If all compatible physical registers are used, this method
187 /// spills the last used virtual register to the stack, and uses that
190 unsigned getFreeReg(MachineBasicBlock &MBB,
191 MachineBasicBlock::iterator &I,
192 unsigned virtualReg);
194 /// reloadVirtReg - This method loads the specified virtual register into a
195 /// physical register, returning the physical register chosen. This updates
196 /// the regalloc data structures to reflect the fact that the virtual reg is
197 /// now alive in a physical register, and the previous one isn't.
199 unsigned reloadVirtReg(MachineBasicBlock &MBB,
200 MachineBasicBlock::iterator &I, unsigned VirtReg);
205 /// getStackSpaceFor - This allocates space for the specified virtual
206 /// register to be held on the stack.
207 unsigned RA::getStackSpaceFor(unsigned VirtReg,
208 const TargetRegisterClass *RegClass) {
209 // Find the location VirtReg would belong...
210 std::map<unsigned, unsigned>::iterator I =
211 VirtReg2OffsetMap.lower_bound(VirtReg);
213 if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
214 return I->second; // Already has space allocated?
216 unsigned RegSize = RegClass->getDataSize();
218 // Align NumBytesAllocated. We should be using TargetData alignment stuff
219 // to determine this, but we don't know the LLVM type associated with the
220 // virtual register. Instead, just align to a multiple of the size for now.
221 NumBytesAllocated += RegSize-1;
222 NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
224 // Assign the slot...
225 VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
227 // Reserve the space!
228 NumBytesAllocated += RegSize;
229 return NumBytesAllocated-RegSize;
233 /// removePhysReg - This method marks the specified physical register as no
234 /// longer being in use.
236 void RA::removePhysReg(unsigned PhysReg) {
237 PhysRegsUsed.erase(PhysReg); // PhyReg no longer used
239 std::vector<unsigned>::iterator It =
240 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
241 assert(It != PhysRegsUseOrder.end() &&
242 "Spilled a physical register, but it was not in use list!");
243 PhysRegsUseOrder.erase(It);
246 /// spillVirtReg - This method spills the value specified by PhysReg into the
247 /// virtual register slot specified by VirtReg. It then updates the RA data
248 /// structures to indicate the fact that PhysReg is now available.
250 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
251 unsigned VirtReg, unsigned PhysReg) {
252 // If this is just a marker register, we don't need to spill it.
254 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
255 unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
257 // Add move instruction(s)
258 I = RegInfo.storeReg2RegOffset(MBB, I, PhysReg, RegInfo.getFramePointer(),
259 -stackOffset, RegClass->getDataSize());
260 ++NumSpilled; // Update statistics
261 Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available
264 removePhysReg(PhysReg);
268 /// isPhysRegAvailable - Return true if the specified physical register is free
269 /// and available for use. This also includes checking to see if aliased
270 /// registers are all free...
272 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
273 if (PhysRegsUsed.count(PhysReg)) return false;
275 // If the selected register aliases any other allocated registers, it is
277 if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
278 for (unsigned i = 0; AliasSet[i]; ++i)
279 if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use?
280 return false; // Can't use this reg then.
286 /// getFreeReg - Find a physical register to hold the specified virtual
287 /// register. If all compatible physical registers are used, this method spills
288 /// the last used virtual register to the stack, and uses that register.
290 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
292 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
293 unsigned PhysReg = 0;
295 // First check to see if we have a free register of the requested type...
296 for (TargetRegisterClass::iterator It = RegClass->begin(),E = RegClass->end();
299 if (isPhysRegAvailable(R)) { // Is reg unused?
300 if (isAllocatableRegister(R)) { // And is not a frame register?
301 // Found an unused register!
308 // If we didn't find an unused register, scavenge one now!
310 assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
312 // Loop over all of the preallocated registers from the least recently used
313 // to the most recently used. When we find one that is capable of holding
314 // our register, use it.
315 for (unsigned i = 0; PhysReg == 0; ++i) {
316 assert(i != PhysRegsUseOrder.size() &&
317 "Couldn't find a register of the appropriate class!");
319 unsigned R = PhysRegsUseOrder[i];
320 // If the current register is compatible, use it.
321 if (isAllocatableRegister(R)) {
322 if (RegInfo.getRegClass(R) == RegClass) {
326 // If one of the registers aliased to the current register is
327 // compatible, use it.
328 if (const unsigned *AliasSet = RegInfo.getAliasSet(R))
329 for (unsigned a = 0; AliasSet[a]; ++a)
330 if (RegInfo.getRegClass(AliasSet[a]) == RegClass) {
331 PhysReg = AliasSet[a]; // Take an aliased register
338 assert(isAllocatableRegister(PhysReg) && "Register is not allocatable!");
340 assert(PhysReg && "Physical register not assigned!?!?");
342 // At this point PhysRegsUseOrder[i] is the least recently used register of
343 // compatible register class. Spill it to memory and reap its remains.
344 spillPhysReg(MBB, I, PhysReg);
347 // Now that we know which register we need to assign this to, do it now!
348 AssignVirtToPhysReg(VirtReg, PhysReg);
353 void RA::AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
354 assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
355 "Phys reg already assigned!");
356 // Update information to note the fact that this register was just used, and
358 PhysRegsUsed[PhysReg] = VirtReg;
359 Virt2PhysRegMap[VirtReg] = PhysReg;
360 PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg
364 /// reloadVirtReg - This method loads the specified virtual register into a
365 /// physical register, returning the physical register chosen. This updates the
366 /// regalloc data structures to reflect the fact that the virtual reg is now
367 /// alive in a physical register, and the previous one isn't.
369 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
370 MachineBasicBlock::iterator &I,
372 std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
373 if (It != Virt2PhysRegMap.end()) {
374 MarkPhysRegRecentlyUsed(It->second);
375 return It->second; // Already have this value available!
378 unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
380 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
381 unsigned StackOffset = getStackSpaceFor(VirtReg, RegClass);
383 // Add move instruction(s)
384 I = RegInfo.loadRegOffset2Reg(MBB, I, PhysReg, RegInfo.getFramePointer(),
385 -StackOffset, RegClass->getDataSize());
386 ++NumReloaded; // Update statistics
390 /// CalculateLastUseOfVReg - Calculate an approximation of the killing uses for
391 /// the virtual registers in the function. Here we try to capture registers
392 /// that are defined and only used within the same basic block. Because we
393 /// don't have use-def chains yet, we have to do this the hard way.
395 void RA::CalculateLastUseOfVReg(MachineBasicBlock &MBB,
396 std::map<unsigned, MachineInstr*> &LastUseOfVReg) const {
397 // Calculate the last machine instruction in this basic block that uses the
398 // specified virtual register defined in this basic block.
399 std::map<unsigned, MachineInstr*> LastLocalUses;
401 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;++I){
402 MachineInstr *MI = *I;
403 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
404 MachineOperand &Op = MI->getOperand(i);
405 if (Op.isVirtualRegister()) {
406 if (Op.opIsDef()) { // Definition of a new virtual reg?
407 LastLocalUses[Op.getAllocatedRegNum()] = 0; // Record it
408 } else { // Use of a virtual reg.
409 std::map<unsigned, MachineInstr*>::iterator It =
410 LastLocalUses.find(Op.getAllocatedRegNum());
411 if (It != LastLocalUses.end()) // Local use?
412 It->second = MI; // Update last use
414 LastUseOfVReg[Op.getAllocatedRegNum()] = 0;
420 // Move local uses over... if there are any uses of a local already in the
421 // lastuse map, the newly inserted entry is ignored.
422 LastUseOfVReg.insert(LastLocalUses.begin(), LastLocalUses.end());
426 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
427 /// predecessor basic blocks.
429 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
430 const MachineInstrInfo &MII = TM.getInstrInfo();
432 while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
433 MachineInstr *MI = MBB.front();
434 // Unlink the PHI node from the basic block... but don't delete the PHI yet
435 MBB.erase(MBB.begin());
437 assert(MI->getOperand(0).isVirtualRegister() &&
438 "PHI node doesn't write virt reg?");
440 unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
442 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
443 MachineOperand &opVal = MI->getOperand(i-1);
445 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
446 // source path the phi
447 MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
449 // Check to make sure we haven't already emitted the copy for this block.
450 // This can happen because PHI nodes may have multiple entries for the
451 // same basic block. It doesn't matter which entry we use though, because
452 // all incoming values are guaranteed to be the same for a particular bb.
454 // Note that this is N^2 in the number of phi node entries, but since the
455 // # of entries is tiny, this is not a problem.
457 bool HaveNotEmitted = true;
458 for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
459 if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
460 HaveNotEmitted = false;
464 if (HaveNotEmitted) {
465 MachineBasicBlock::iterator opI = opBlock.end();
466 MachineInstr *opMI = *--opI;
468 // must backtrack over ALL the branches in the previous block
469 while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
472 // move back to the first branch instruction so new instructions
473 // are inserted right in front of it and not in front of a non-branch
474 if (!MII.isBranch(opMI->getOpcode()))
477 unsigned dataSize = MF->getRegClass(virtualReg)->getDataSize();
479 // Retrieve the constant value from this op, move it to target
480 // register of the phi
481 if (opVal.isImmediate()) {
482 opI = RegInfo.moveImm2Reg(opBlock, opI, virtualReg,
483 (unsigned) opVal.getImmedValue(),
486 opI = RegInfo.moveReg2Reg(opBlock, opI, virtualReg,
487 opVal.getAllocatedRegNum(), dataSize);
492 // really delete the PHI instruction now!
498 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
499 // loop over each instruction
500 MachineBasicBlock::iterator I = MBB.begin();
501 for (; I != MBB.end(); ++I) {
502 MachineInstr *MI = *I;
503 const MachineInstrDescriptor &MID = MIInfo.get(MI->getOpcode());
505 // Loop over all of the operands of the instruction, spilling registers that
506 // are defined, and marking explicit destinations in the PhysRegsUsed map.
508 // FIXME: We don't need to spill a register if this is the last use of the
510 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
511 if (MI->getOperand(i).opIsDef() &&
512 MI->getOperand(i).isPhysicalRegister()) {
513 unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
514 spillPhysReg(MBB, I, Reg);
515 PhysRegsUsed[Reg] = 0; // It is free and reserved now
516 PhysRegsUseOrder.push_back(Reg);
519 // Loop over the implicit defs, spilling them, as above.
520 if (const unsigned *ImplicitDefs = MID.ImplicitDefs)
521 for (unsigned i = 0; ImplicitDefs[i]; ++i) {
522 unsigned Reg = ImplicitDefs[i];
524 // We don't want to spill implicit definitions if they were explicitly
525 // chosen. For this reason, check to see now if the register we are
526 // to spill has a vreg of 0.
527 if (PhysRegsUsed.count(Reg) && PhysRegsUsed[Reg] != 0)
528 spillPhysReg(MBB, I, Reg);
529 else if (PhysRegsUsed.count(Reg)) {
530 // Remove the entry from PhysRegsUseOrder to avoid having two entries!
533 PhysRegsUseOrder.push_back(Reg);
534 PhysRegsUsed[Reg] = 0; // It is free and reserved now
537 // Loop over the implicit uses, making sure that they are at the head of the
538 // use order list, so they don't get reallocated.
539 if (const unsigned *ImplicitUses = MID.ImplicitUses)
540 for (unsigned i = 0; ImplicitUses[i]; ++i)
541 MarkPhysRegRecentlyUsed(ImplicitUses[i]);
543 // Loop over all of the operands again, getting the used operands into
544 // registers. This has the potiential to spill incoming values if we are
547 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
548 if (MI->getOperand(i).opIsUse() &&
549 MI->getOperand(i).isVirtualRegister()) {
550 unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
551 unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
552 MI->SetMachineOperandReg(i, PhysSrcReg); // Assign the input register
555 // Okay, we have allocated all of the source operands and spilled any values
556 // that would be destroyed by defs of this instruction. Loop over the
557 // implicit defs and assign them to a register, spilling the incoming value
558 // if we need to scavange a register.
560 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
561 if (MI->getOperand(i).opIsDef() &&
562 !MI->getOperand(i).isPhysicalRegister()) {
563 unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
564 unsigned DestPhysReg;
566 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
567 // must be same register number as the first operand
568 // This maps a = b + c into b += c, and saves b into a's spot
569 assert(MI->getOperand(1).isRegister() &&
570 MI->getOperand(1).getAllocatedRegNum() &&
571 MI->getOperand(1).opIsUse() &&
572 "Two address instruction invalid!");
573 DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
575 // Spill the incoming value, because we are about to change the
576 // register contents.
577 spillPhysReg(MBB, I, DestPhysReg);
578 AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
580 DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
582 MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register
586 // If this instruction is the last user of anything in registers, kill the
587 // value, freeing the register being used, so it doesn't need to be
588 // spilled to memory at the end of the block.
589 std::multimap<MachineInstr*, unsigned>::iterator LUOI =
590 LastUserOf.lower_bound(MI);
591 for (; LUOI != LastUserOf.end() && LUOI->first == MI; ++MI) {
592 unsigned VirtReg = LUOI->second; // entry found?
593 unsigned PhysReg = Virt2PhysRegMap[VirtReg];
595 DEBUG(std::cout << "V: " << VirtReg << " P: " << PhysReg
596 << " Last use of: " << *MI);
597 removePhysReg(PhysReg);
599 Virt2PhysRegMap.erase(VirtReg);
604 // Rewind the iterator to point to the first flow control instruction...
605 const MachineInstrInfo &MII = TM.getInstrInfo();
609 } while ((MII.isReturn((*I)->getOpcode()) ||
610 MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
612 if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
615 // Spill all physical registers holding virtual registers now.
616 while (!PhysRegsUsed.empty())
617 spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
618 PhysRegsUsed.begin()->first);
620 assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
621 assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
625 /// EmitPrologue - Use the register info object to add a prologue to the
626 /// function and save any callee saved registers we are responsible for.
628 void RA::EmitPrologue() {
629 // Get a list of the callee saved registers, so that we can save them on entry
633 MachineBasicBlock &MBB = MF->front(); // Prolog goes in entry BB
634 MachineBasicBlock::iterator I = MBB.begin();
636 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
637 for (unsigned i = 0; CSRegs[i]; ++i) {
638 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
639 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
641 // Insert the spill to the stack frame...
643 I = RegInfo.storeReg2RegOffset(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
644 -Offset, RegClass->getDataSize());
647 // Add prologue to the function...
648 RegInfo.emitPrologue(*MF, NumBytesAllocated);
652 /// EmitEpilogue - Use the register info object to add a epilogue to the
653 /// function and restore any callee saved registers we are responsible for.
655 void RA::EmitEpilogue(MachineBasicBlock &MBB) {
656 // Insert instructions before the return.
657 MachineBasicBlock::iterator I = MBB.end()-1;
659 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
660 for (unsigned i = 0; CSRegs[i]; ++i) {
661 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
662 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
664 I = RegInfo.loadRegOffset2Reg(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
665 -Offset, RegClass->getDataSize());
666 --I; // Insert in reverse order
669 RegInfo.emitEpilogue(MBB, NumBytesAllocated);
673 /// runOnMachineFunction - Register allocate the whole function
675 bool RA::runOnMachineFunction(MachineFunction &Fn) {
676 DEBUG(std::cerr << "Machine Function " << "\n");
679 // First pass: eliminate PHI instructions by inserting copies into predecessor
680 // blocks, and calculate a simple approximation of killing uses for virtual
683 std::map<unsigned, MachineInstr*> LastUseOfVReg;
684 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
685 MBB != MBBe; ++MBB) {
687 CalculateLastUseOfVReg(*MBB, LastUseOfVReg);
688 EliminatePHINodes(*MBB);
691 // At this point LastUseOfVReg has been filled in to contain the last
692 // MachineInstr user of the specified virtual register, if that user is
693 // within the same basic block as the definition (otherwise it contains
694 // null). Invert this mapping now:
696 for (std::map<unsigned, MachineInstr*>::iterator I = LastUseOfVReg.begin(),
697 E = LastUseOfVReg.end(); I != E; ++I)
699 LastUserOf.insert(std::make_pair(I->second, I->first));
701 // We're done with the temporary list now.
702 LastUseOfVReg.clear();
704 // Loop over all of the basic blocks, eliminating virtual register references
705 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
707 AllocateBasicBlock(*MBB);
710 // Emit a prologue for the function...
713 const MachineInstrInfo &MII = TM.getInstrInfo();
715 // Add epilogue to restore the callee-save registers in each exiting block
716 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
717 MBB != MBBe; ++MBB) {
718 // If last instruction is a return instruction, add an epilogue
719 if (MII.isReturn(MBB->back()->getOpcode()))
724 cleanupAfterFunction();
728 Pass *createLocalRegisterAllocator(TargetMachine &TM) {