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/CodeGen/SSARegMap.h"
11 #include "llvm/Target/MachineInstrInfo.h"
12 #include "llvm/Target/TargetMachine.h"
13 #include "Support/Statistic.h"
14 #include "Support/CommandLine.h"
19 Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
20 Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
21 cl::opt<bool> DisableKill("no-kill", cl::Hidden,
22 cl::desc("Disable register kill in local-ra"));
24 class RA : public FunctionPass {
27 const MRegisterInfo &RegInfo;
28 const MachineInstrInfo &MIInfo;
29 unsigned NumBytesAllocated;
31 // PhysRegsModified - Keep track of which physical registers are actually
32 // modified by the function we are code generating. This set allows us to
33 // only spill caller-saved registers that we actually change.
35 // FIXME: this would be much nicer & faster as a bitset.
37 std::set<unsigned> PhysRegsModified;
39 // Maps SSA Regs => offsets on the stack where these values are stored
40 std::map<unsigned, unsigned> VirtReg2OffsetMap;
42 // Virt2PhysRegMap - This map contains entries for each virtual register
43 // that is currently available in a physical register.
45 std::map<unsigned, unsigned> Virt2PhysRegMap;
47 // PhysRegsUsed - This map contains entries for each physical register that
48 // currently has a value (ie, it is in Virt2PhysRegMap). The value mapped
49 // to is the virtual register corresponding to the physical register (the
50 // inverse of the Virt2PhysRegMap), or 0. The value is set to 0 if this
51 // register is pinned because it is used by a future instruction.
53 std::map<unsigned, unsigned> PhysRegsUsed;
55 // PhysRegsUseOrder - This contains a list of the physical registers that
56 // currently have a virtual register value in them. This list provides an
57 // ordering of registers, imposing a reallocation order. This list is only
58 // used if all registers are allocated and we have to spill one, in which
59 // case we spill the least recently used register. Entries at the front of
60 // the list are the least recently used registers, entries at the back are
61 // the most recently used.
63 std::vector<unsigned> PhysRegsUseOrder;
65 // LastUserOf map - This multimap contains the set of registers that each
66 // key instruction is the last user of. If an instruction has an entry in
67 // this map, that means that the specified operands are killed after the
68 // instruction is executed, thus they don't need to be spilled into memory
70 std::multimap<MachineInstr*, unsigned> LastUserOf;
72 void MarkPhysRegRecentlyUsed(unsigned Reg) {
73 assert(!PhysRegsUseOrder.empty() && "No registers used!");
74 if (PhysRegsUseOrder.back() == Reg) return; // Already most recently used
76 for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
77 if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
78 unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle
79 PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
80 // Add it to the end of the list
81 PhysRegsUseOrder.push_back(RegMatch);
83 return; // Found an exact match, exit early
90 : TM(tm), RegInfo(*tm.getRegisterInfo()), MIInfo(tm.getInstrInfo()) {
91 cleanupAfterFunction();
94 bool runOnFunction(Function &Fn) {
95 return runOnMachineFunction(MachineFunction::get(&Fn));
98 virtual const char *getPassName() const {
99 return "Local Register Allocator";
103 /// runOnMachineFunction - Register allocate the whole function
104 bool runOnMachineFunction(MachineFunction &Fn);
106 /// AllocateBasicBlock - Register allocate the specified basic block.
107 void AllocateBasicBlock(MachineBasicBlock &MBB);
109 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
110 /// in predecessor basic blocks.
111 void EliminatePHINodes(MachineBasicBlock &MBB);
113 /// CalculateLastUseOfVReg - Calculate an approximation of the killing
114 /// uses for the virtual registers in the function. Here we try to capture
115 /// registers that are defined and only used within the same basic block.
116 /// Because we don't have use-def chains yet, we have to do this the hard
119 void CalculateLastUseOfVReg(MachineBasicBlock &MBB,
120 std::map<unsigned, MachineInstr*> &LastUseOfVReg) const;
123 /// EmitPrologue/EmitEpilogue - Use the register info object to add a
124 /// prologue/epilogue to the function and save/restore the callee saved
125 /// registers specified by the CSRegs list.
127 void EmitPrologue(const std::vector<unsigned> &CSRegs);
128 void EmitEpilogue(MachineBasicBlock &MBB,
129 const std::vector<unsigned> &CSRegs);
131 /// areRegsEqual - This method returns true if the specified registers are
132 /// related to each other. To do this, it checks to see if they are equal
133 /// or if the first register is in the alias set of the second register.
135 bool areRegsEqual(unsigned R1, unsigned R2) const {
136 if (R1 == R2) return true;
137 if (const unsigned *AliasSet = RegInfo.getAliasSet(R2))
138 for (unsigned i = 0; AliasSet[i]; ++i)
139 if (AliasSet[i] == R1) return true;
143 /// isAllocatableRegister - A register may be used by the program if it's
144 /// not the stack or frame pointer.
145 bool isAllocatableRegister(unsigned R) const {
146 unsigned FP = RegInfo.getFramePointer(), SP = RegInfo.getStackPointer();
147 return !areRegsEqual(FP, R) && !areRegsEqual(SP, R);
150 /// getStackSpaceFor - This returns the offset of the specified virtual
151 /// register on the stack, allocating space if neccesary.
152 unsigned getStackSpaceFor(unsigned VirtReg,
153 const TargetRegisterClass *regClass);
155 void cleanupAfterFunction() {
156 VirtReg2OffsetMap.clear();
157 NumBytesAllocated = 4; // FIXME: This is X86 specific
160 void removePhysReg(unsigned PhysReg);
162 /// spillVirtReg - This method spills the value specified by PhysReg into
163 /// the virtual register slot specified by VirtReg. It then updates the RA
164 /// data structures to indicate the fact that PhysReg is now available.
166 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
167 unsigned VirtReg, unsigned PhysReg);
169 /// spillPhysReg - This method spills the specified physical register into
170 /// the virtual register slot associated with it.
172 void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
174 std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
175 if (PI != PhysRegsUsed.end()) { // Only spill it if it's used!
176 spillVirtReg(MBB, I, PI->second, PhysReg);
177 } else if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg)) {
178 // If the selected register aliases any other registers, we must make
179 // sure that one of the aliases isn't alive...
180 for (unsigned i = 0; AliasSet[i]; ++i) {
181 PI = PhysRegsUsed.find(AliasSet[i]);
182 if (PI != PhysRegsUsed.end()) // Spill aliased register...
183 spillVirtReg(MBB, I, PI->second, AliasSet[i]);
188 void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
190 /// isPhysRegAvailable - Return true if the specified physical register is
191 /// free and available for use. This also includes checking to see if
192 /// aliased registers are all free...
194 bool isPhysRegAvailable(unsigned PhysReg) const;
196 /// getFreeReg - Find a physical register to hold the specified virtual
197 /// register. If all compatible physical registers are used, this method
198 /// spills the last used virtual register to the stack, and uses that
201 unsigned getFreeReg(MachineBasicBlock &MBB,
202 MachineBasicBlock::iterator &I,
203 unsigned virtualReg);
205 /// reloadVirtReg - This method loads the specified virtual register into a
206 /// physical register, returning the physical register chosen. This updates
207 /// the regalloc data structures to reflect the fact that the virtual reg is
208 /// now alive in a physical register, and the previous one isn't.
210 unsigned reloadVirtReg(MachineBasicBlock &MBB,
211 MachineBasicBlock::iterator &I, unsigned VirtReg);
216 /// getStackSpaceFor - This allocates space for the specified virtual
217 /// register to be held on the stack.
218 unsigned RA::getStackSpaceFor(unsigned VirtReg,
219 const TargetRegisterClass *RegClass) {
220 // Find the location VirtReg would belong...
221 std::map<unsigned, unsigned>::iterator I =
222 VirtReg2OffsetMap.lower_bound(VirtReg);
224 if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
225 return I->second; // Already has space allocated?
227 unsigned RegSize = RegClass->getDataSize();
229 // Align NumBytesAllocated. We should be using TargetData alignment stuff
230 // to determine this, but we don't know the LLVM type associated with the
231 // virtual register. Instead, just align to a multiple of the size for now.
232 NumBytesAllocated += RegSize-1;
233 NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
235 // Assign the slot...
236 VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
238 // Reserve the space!
239 NumBytesAllocated += RegSize;
240 return NumBytesAllocated-RegSize;
244 /// removePhysReg - This method marks the specified physical register as no
245 /// longer being in use.
247 void RA::removePhysReg(unsigned PhysReg) {
248 PhysRegsUsed.erase(PhysReg); // PhyReg no longer used
250 std::vector<unsigned>::iterator It =
251 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
252 assert(It != PhysRegsUseOrder.end() &&
253 "Spilled a physical register, but it was not in use list!");
254 PhysRegsUseOrder.erase(It);
257 /// spillVirtReg - This method spills the value specified by PhysReg into the
258 /// virtual register slot specified by VirtReg. It then updates the RA data
259 /// structures to indicate the fact that PhysReg is now available.
261 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
262 unsigned VirtReg, unsigned PhysReg) {
263 // If this is just a marker register, we don't need to spill it.
265 const TargetRegisterClass *RegClass =
266 MF->getSSARegMap()->getRegClass(VirtReg);
267 unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
269 // Add move instruction(s)
270 RegInfo.storeReg2RegOffset(MBB, I, PhysReg, RegInfo.getFramePointer(),
271 -stackOffset, RegClass);
272 ++NumSpilled; // Update statistics
273 Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available
276 removePhysReg(PhysReg);
280 /// isPhysRegAvailable - Return true if the specified physical register is free
281 /// and available for use. This also includes checking to see if aliased
282 /// registers are all free...
284 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
285 if (PhysRegsUsed.count(PhysReg)) return false;
287 // If the selected register aliases any other allocated registers, it is
289 if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
290 for (unsigned i = 0; AliasSet[i]; ++i)
291 if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use?
292 return false; // Can't use this reg then.
298 /// getFreeReg - Find a physical register to hold the specified virtual
299 /// register. If all compatible physical registers are used, this method spills
300 /// the last used virtual register to the stack, and uses that register.
302 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
304 const TargetRegisterClass *RegClass =
305 MF->getSSARegMap()->getRegClass(VirtReg);
306 unsigned PhysReg = 0;
308 // First check to see if we have a free register of the requested type...
309 for (TargetRegisterClass::iterator It = RegClass->begin(),E = RegClass->end();
312 if (isPhysRegAvailable(R)) { // Is reg unused?
313 if (isAllocatableRegister(R)) { // And is not a frame register?
314 // Found an unused register!
321 // If we didn't find an unused register, scavenge one now!
323 assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
325 // Loop over all of the preallocated registers from the least recently used
326 // to the most recently used. When we find one that is capable of holding
327 // our register, use it.
328 for (unsigned i = 0; PhysReg == 0; ++i) {
329 assert(i != PhysRegsUseOrder.size() &&
330 "Couldn't find a register of the appropriate class!");
332 unsigned R = PhysRegsUseOrder[i];
333 // If the current register is compatible, use it.
334 if (isAllocatableRegister(R)) {
335 if (RegInfo.getRegClass(R) == RegClass) {
339 // If one of the registers aliased to the current register is
340 // compatible, use it.
341 if (const unsigned *AliasSet = RegInfo.getAliasSet(R))
342 for (unsigned a = 0; AliasSet[a]; ++a)
343 if (RegInfo.getRegClass(AliasSet[a]) == RegClass) {
344 PhysReg = AliasSet[a]; // Take an aliased register
351 assert(isAllocatableRegister(PhysReg) && "Register is not allocatable!");
353 assert(PhysReg && "Physical register not assigned!?!?");
355 // At this point PhysRegsUseOrder[i] is the least recently used register of
356 // compatible register class. Spill it to memory and reap its remains.
357 spillPhysReg(MBB, I, PhysReg);
360 // Now that we know which register we need to assign this to, do it now!
361 AssignVirtToPhysReg(VirtReg, PhysReg);
366 void RA::AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
367 assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
368 "Phys reg already assigned!");
369 // Update information to note the fact that this register was just used, and
371 PhysRegsUsed[PhysReg] = VirtReg;
372 Virt2PhysRegMap[VirtReg] = PhysReg;
373 PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg
377 /// reloadVirtReg - This method loads the specified virtual register into a
378 /// physical register, returning the physical register chosen. This updates the
379 /// regalloc data structures to reflect the fact that the virtual reg is now
380 /// alive in a physical register, and the previous one isn't.
382 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
383 MachineBasicBlock::iterator &I,
385 std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
386 if (It != Virt2PhysRegMap.end()) {
387 MarkPhysRegRecentlyUsed(It->second);
388 return It->second; // Already have this value available!
391 unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
393 const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
394 unsigned StackOffset = getStackSpaceFor(VirtReg, RC);
396 // Add move instruction(s)
397 RegInfo.loadRegOffset2Reg(MBB, I, PhysReg, RegInfo.getFramePointer(),
399 ++NumReloaded; // Update statistics
403 /// CalculateLastUseOfVReg - Calculate an approximation of the killing uses for
404 /// the virtual registers in the function. Here we try to capture registers
405 /// that are defined and only used within the same basic block. Because we
406 /// don't have use-def chains yet, we have to do this the hard way.
408 void RA::CalculateLastUseOfVReg(MachineBasicBlock &MBB,
409 std::map<unsigned, MachineInstr*> &LastUseOfVReg) const {
410 // Calculate the last machine instruction in this basic block that uses the
411 // specified virtual register defined in this basic block.
412 std::map<unsigned, MachineInstr*> LastLocalUses;
414 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;++I){
415 MachineInstr *MI = *I;
416 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
417 MachineOperand &Op = MI->getOperand(i);
418 if (Op.isVirtualRegister()) {
419 if (Op.opIsDef()) { // Definition of a new virtual reg?
420 LastLocalUses[Op.getAllocatedRegNum()] = 0; // Record it
421 } else { // Use of a virtual reg.
422 std::map<unsigned, MachineInstr*>::iterator It =
423 LastLocalUses.find(Op.getAllocatedRegNum());
424 if (It != LastLocalUses.end()) // Local use?
425 It->second = MI; // Update last use
427 LastUseOfVReg[Op.getAllocatedRegNum()] = 0;
433 // Move local uses over... if there are any uses of a local already in the
434 // lastuse map, the newly inserted entry is ignored.
435 LastUseOfVReg.insert(LastLocalUses.begin(), LastLocalUses.end());
439 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
440 /// predecessor basic blocks.
442 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
443 const MachineInstrInfo &MII = TM.getInstrInfo();
445 while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
446 MachineInstr *MI = MBB.front();
447 // Unlink the PHI node from the basic block... but don't delete the PHI yet
448 MBB.erase(MBB.begin());
450 assert(MI->getOperand(0).isVirtualRegister() &&
451 "PHI node doesn't write virt reg?");
453 unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
455 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
456 MachineOperand &opVal = MI->getOperand(i-1);
458 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
459 // source path the phi
460 MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
462 // Check to make sure we haven't already emitted the copy for this block.
463 // This can happen because PHI nodes may have multiple entries for the
464 // same basic block. It doesn't matter which entry we use though, because
465 // all incoming values are guaranteed to be the same for a particular bb.
467 // Note that this is N^2 in the number of phi node entries, but since the
468 // # of entries is tiny, this is not a problem.
470 bool HaveNotEmitted = true;
471 for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
472 if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
473 HaveNotEmitted = false;
477 if (HaveNotEmitted) {
478 MachineBasicBlock::iterator opI = opBlock.end();
479 MachineInstr *opMI = *--opI;
481 // must backtrack over ALL the branches in the previous block
482 while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
485 // move back to the first branch instruction so new instructions
486 // are inserted right in front of it and not in front of a non-branch
487 if (!MII.isBranch(opMI->getOpcode()))
490 const TargetRegisterClass *RC =
491 MF->getSSARegMap()->getRegClass(virtualReg);
493 // Retrieve the constant value from this op, move it to target
494 // register of the phi
495 if (opVal.isImmediate()) {
496 RegInfo.moveImm2Reg(opBlock, opI, virtualReg,
497 (unsigned) opVal.getImmedValue(), RC);
499 RegInfo.moveReg2Reg(opBlock, opI, virtualReg,
500 opVal.getAllocatedRegNum(), RC);
505 // really delete the PHI instruction now!
511 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
512 // loop over each instruction
513 MachineBasicBlock::iterator I = MBB.begin();
514 for (; I != MBB.end(); ++I) {
515 MachineInstr *MI = *I;
516 const MachineInstrDescriptor &MID = MIInfo.get(MI->getOpcode());
518 // Loop over all of the operands of the instruction, spilling registers that
519 // are defined, and marking explicit destinations in the PhysRegsUsed map.
521 // FIXME: We don't need to spill a register if this is the last use of the
523 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
524 if (MI->getOperand(i).opIsDef() &&
525 MI->getOperand(i).isPhysicalRegister()) {
526 unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
527 spillPhysReg(MBB, I, Reg);
528 PhysRegsUsed[Reg] = 0; // It is free and reserved now
529 PhysRegsUseOrder.push_back(Reg);
530 PhysRegsModified.insert(Reg); // Register is modified by current Fn
533 // Loop over the implicit defs, spilling them, as above.
534 if (const unsigned *ImplicitDefs = MID.ImplicitDefs)
535 for (unsigned i = 0; ImplicitDefs[i]; ++i) {
536 unsigned Reg = ImplicitDefs[i];
538 // We don't want to spill implicit definitions if they were explicitly
539 // chosen. For this reason, check to see now if the register we are
540 // to spill has a vreg of 0.
541 if (PhysRegsUsed.count(Reg) && PhysRegsUsed[Reg] != 0)
542 spillPhysReg(MBB, I, Reg);
543 else if (PhysRegsUsed.count(Reg)) {
544 // Remove the entry from PhysRegsUseOrder to avoid having two entries!
547 PhysRegsUseOrder.push_back(Reg);
548 PhysRegsUsed[Reg] = 0; // It is free and reserved now
549 PhysRegsModified.insert(Reg); // Register is modified by current Fn
552 // Loop over the implicit uses, making sure that they are at the head of the
553 // use order list, so they don't get reallocated.
554 if (const unsigned *ImplicitUses = MID.ImplicitUses)
555 for (unsigned i = 0; ImplicitUses[i]; ++i)
556 MarkPhysRegRecentlyUsed(ImplicitUses[i]);
558 // Loop over all of the operands again, getting the used operands into
559 // registers. This has the potiential to spill incoming values if we are
562 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
563 if (MI->getOperand(i).opIsUse() &&
564 MI->getOperand(i).isVirtualRegister()) {
565 unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
566 unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
567 MI->SetMachineOperandReg(i, PhysSrcReg); // Assign the input register
568 PhysRegsModified.insert(PhysSrcReg); // Register is modified
571 // Okay, we have allocated all of the source operands and spilled any values
572 // that would be destroyed by defs of this instruction. Loop over the
573 // implicit defs and assign them to a register, spilling the incoming value
574 // if we need to scavange a register.
576 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
577 if (MI->getOperand(i).opIsDef() &&
578 !MI->getOperand(i).isPhysicalRegister()) {
579 unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
580 unsigned DestPhysReg;
582 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
583 // must be same register number as the first operand
584 // This maps a = b + c into b += c, and saves b into a's spot
585 assert(MI->getOperand(1).isRegister() &&
586 MI->getOperand(1).getAllocatedRegNum() &&
587 MI->getOperand(1).opIsUse() &&
588 "Two address instruction invalid!");
589 DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
591 // Spill the incoming value, because we are about to change the
592 // register contents.
593 spillPhysReg(MBB, I, DestPhysReg);
594 AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
596 DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
598 PhysRegsModified.insert(DestPhysReg); // Register is modified
599 MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register
603 // If this instruction is the last user of anything in registers, kill the
604 // value, freeing the register being used, so it doesn't need to be
605 // spilled to memory at the end of the block.
606 std::multimap<MachineInstr*, unsigned>::iterator LUOI =
607 LastUserOf.lower_bound(MI);
608 for (; LUOI != LastUserOf.end() && LUOI->first == MI; ++MI) {
609 unsigned VirtReg = LUOI->second; // entry found?
610 unsigned PhysReg = Virt2PhysRegMap[VirtReg];
612 DEBUG(std::cout << "V: " << VirtReg << " P: " << PhysReg
613 << " Last use of: " << *MI);
614 removePhysReg(PhysReg);
616 Virt2PhysRegMap.erase(VirtReg);
621 // Rewind the iterator to point to the first flow control instruction...
622 const MachineInstrInfo &MII = TM.getInstrInfo();
626 } while ((MII.isReturn((*I)->getOpcode()) ||
627 MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
629 if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
632 // Spill all physical registers holding virtual registers now.
633 while (!PhysRegsUsed.empty())
634 spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
635 PhysRegsUsed.begin()->first);
637 assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
638 assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
642 /// EmitPrologue - Use the register info object to add a prologue to the
643 /// function and save any callee saved registers we are responsible for.
645 void RA::EmitPrologue(const std::vector<unsigned> &CSRegs) {
646 MachineBasicBlock &MBB = MF->front(); // Prolog goes in entry BB
647 MachineBasicBlock::iterator I = MBB.begin();
649 for (unsigned i = 0, e = CSRegs.size(); i != e; ++i) {
650 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
651 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
653 // Insert the spill to the stack frame...
655 RegInfo.storeReg2RegOffset(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
659 // Add prologue to the function...
660 RegInfo.emitPrologue(*MF, NumBytesAllocated);
664 /// EmitEpilogue - Use the register info object to add a epilogue to the
665 /// function and restore any callee saved registers we are responsible for.
667 void RA::EmitEpilogue(MachineBasicBlock &MBB,
668 const std::vector<unsigned> &CSRegs) {
669 // Insert instructions before the return.
670 MachineBasicBlock::iterator I = MBB.end()-1;
672 for (unsigned i = 0, e = CSRegs.size(); i != e; ++i) {
673 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
674 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
676 RegInfo.loadRegOffset2Reg(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
678 --I; // Insert in reverse order
681 RegInfo.emitEpilogue(MBB, NumBytesAllocated);
685 /// runOnMachineFunction - Register allocate the whole function
687 bool RA::runOnMachineFunction(MachineFunction &Fn) {
688 DEBUG(std::cerr << "Machine Function " << "\n");
691 // First pass: eliminate PHI instructions by inserting copies into predecessor
692 // blocks, and calculate a simple approximation of killing uses for virtual
695 std::map<unsigned, MachineInstr*> LastUseOfVReg;
696 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
697 MBB != MBBe; ++MBB) {
699 CalculateLastUseOfVReg(*MBB, LastUseOfVReg);
700 EliminatePHINodes(*MBB);
703 // At this point LastUseOfVReg has been filled in to contain the last
704 // MachineInstr user of the specified virtual register, if that user is
705 // within the same basic block as the definition (otherwise it contains
706 // null). Invert this mapping now:
708 for (std::map<unsigned, MachineInstr*>::iterator I = LastUseOfVReg.begin(),
709 E = LastUseOfVReg.end(); I != E; ++I)
711 LastUserOf.insert(std::make_pair(I->second, I->first));
713 // We're done with the temporary list now.
714 LastUseOfVReg.clear();
716 // Loop over all of the basic blocks, eliminating virtual register references
717 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
719 AllocateBasicBlock(*MBB);
721 // Figure out which callee saved registers are modified by the current
722 // function, thus needing to be saved and restored in the prolog/epilog.
724 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
725 std::vector<unsigned> RegsToSave;
726 for (unsigned i = 0; CSRegs[i]; ++i) {
727 unsigned Reg = CSRegs[i];
728 if (PhysRegsModified.count(Reg)) // If modified register...
729 RegsToSave.push_back(Reg);
730 else if (const unsigned *AliasSet = RegInfo.getAliasSet(Reg))
731 for (unsigned j = 0; AliasSet[j]; ++j) // Check alias registers too...
732 if (PhysRegsModified.count(AliasSet[j])) {
733 RegsToSave.push_back(Reg);
738 // Emit a prologue for the function...
739 EmitPrologue(RegsToSave);
741 const MachineInstrInfo &MII = TM.getInstrInfo();
743 // Add epilogue to restore the callee-save registers in each exiting block
744 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
745 MBB != MBBe; ++MBB) {
746 // If last instruction is a return instruction, add an epilogue
747 if (MII.isReturn(MBB->back()->getOpcode()))
748 EmitEpilogue(*MBB, RegsToSave);
751 PhysRegsModified.clear();
753 cleanupAfterFunction();
757 Pass *createLocalRegisterAllocator(TargetMachine &TM) {