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) {
65 for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
66 if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { // remove from middle
67 unsigned RegMatch = PhysRegsUseOrder[i-1];
68 PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
69 PhysRegsUseOrder.push_back(RegMatch); // Add it to the end of the list
71 return; // Found an exact match, exit early
79 : TM(tm), RegInfo(*tm.getRegisterInfo()), MIInfo(tm.getInstrInfo()) {
80 cleanupAfterFunction();
83 bool runOnFunction(Function &Fn) {
84 return runOnMachineFunction(MachineFunction::get(&Fn));
87 virtual const char *getPassName() const {
88 return "Local Register Allocator";
92 /// runOnMachineFunction - Register allocate the whole function
93 bool runOnMachineFunction(MachineFunction &Fn);
95 /// AllocateBasicBlock - Register allocate the specified basic block.
96 void AllocateBasicBlock(MachineBasicBlock &MBB);
98 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
99 /// in predecessor basic blocks.
100 void EliminatePHINodes(MachineBasicBlock &MBB);
102 /// CalculateLastUseOfVReg - Calculate an approximation of the killing
103 /// uses for the virtual registers in the function. Here we try to capture
104 /// registers that are defined and only used within the same basic block.
105 /// Because we don't have use-def chains yet, we have to do this the hard
108 void CalculateLastUseOfVReg(MachineBasicBlock &MBB,
109 std::map<unsigned, MachineInstr*> &LastUseOfVReg) const;
112 /// EmitPrologue/EmitEpilogue - Use the register info object to add a
113 /// prologue/epilogue to the function and save/restore any callee saved
114 /// registers we are responsible for.
117 void EmitEpilogue(MachineBasicBlock &MBB);
119 /// areRegsEqual - This method returns true if the specified registers are
120 /// related to each other. To do this, it checks to see if they are equal
121 /// or if the first register is in the alias set of the second register.
123 bool areRegsEqual(unsigned R1, unsigned R2) const {
124 if (R1 == R2) return true;
125 if (const unsigned *AliasSet = RegInfo.getAliasSet(R2))
126 for (unsigned i = 0; AliasSet[i]; ++i)
127 if (AliasSet[i] == R1) return true;
131 /// isAllocatableRegister - A register may be used by the program if it's
132 /// not the stack or frame pointer.
133 bool isAllocatableRegister(unsigned R) const {
134 unsigned FP = RegInfo.getFramePointer(), SP = RegInfo.getStackPointer();
135 return !areRegsEqual(FP, R) && !areRegsEqual(SP, R);
138 /// getStackSpaceFor - This returns the offset of the specified virtual
139 /// register on the stack, allocating space if neccesary.
140 unsigned getStackSpaceFor(unsigned VirtReg,
141 const TargetRegisterClass *regClass);
143 void cleanupAfterFunction() {
144 VirtReg2OffsetMap.clear();
145 NumBytesAllocated = 4; // FIXME: This is X86 specific
148 void removePhysReg(unsigned PhysReg);
150 /// spillVirtReg - This method spills the value specified by PhysReg into
151 /// the virtual register slot specified by VirtReg. It then updates the RA
152 /// data structures to indicate the fact that PhysReg is now available.
154 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
155 unsigned VirtReg, unsigned PhysReg);
157 /// spillPhysReg - This method spills the specified physical register into
158 /// the virtual register slot associated with it.
160 void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
162 std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
163 if (PI != PhysRegsUsed.end()) { // Only spill it if it's used!
164 spillVirtReg(MBB, I, PI->second, PhysReg);
165 } else if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg)) {
166 // If the selected register aliases any other registers, we must make sure
167 // that one of the aliases isn't alive...
168 for (unsigned i = 0; AliasSet[i]; ++i) {
169 PI = PhysRegsUsed.find(AliasSet[i]);
170 if (PI != PhysRegsUsed.end()) // Spill aliased register...
171 spillVirtReg(MBB, I, PI->second, AliasSet[i]);
176 void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
178 /// isPhysRegAvailable - Return true if the specified physical register is
179 /// free and available for use. This also includes checking to see if
180 /// aliased registers are all free...
182 bool isPhysRegAvailable(unsigned PhysReg) const;
184 /// getFreeReg - Find a physical register to hold the specified virtual
185 /// register. If all compatible physical registers are used, this method
186 /// spills the last used virtual register to the stack, and uses that
189 unsigned getFreeReg(MachineBasicBlock &MBB,
190 MachineBasicBlock::iterator &I,
191 unsigned virtualReg);
193 /// reloadVirtReg - This method loads the specified virtual register into a
194 /// physical register, returning the physical register chosen. This updates
195 /// the regalloc data structures to reflect the fact that the virtual reg is
196 /// now alive in a physical register, and the previous one isn't.
198 unsigned reloadVirtReg(MachineBasicBlock &MBB,
199 MachineBasicBlock::iterator &I, unsigned VirtReg);
204 /// getStackSpaceFor - This allocates space for the specified virtual
205 /// register to be held on the stack.
206 unsigned RA::getStackSpaceFor(unsigned VirtReg,
207 const TargetRegisterClass *RegClass) {
208 // Find the location VirtReg would belong...
209 std::map<unsigned, unsigned>::iterator I =
210 VirtReg2OffsetMap.lower_bound(VirtReg);
212 if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
213 return I->second; // Already has space allocated?
215 unsigned RegSize = RegClass->getDataSize();
217 // Align NumBytesAllocated. We should be using TargetData alignment stuff
218 // to determine this, but we don't know the LLVM type associated with the
219 // virtual register. Instead, just align to a multiple of the size for now.
220 NumBytesAllocated += RegSize-1;
221 NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
223 // Assign the slot...
224 VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
226 // Reserve the space!
227 NumBytesAllocated += RegSize;
228 return NumBytesAllocated-RegSize;
232 /// removePhysReg - This method marks the specified physical register as no
233 /// longer being in use.
235 void RA::removePhysReg(unsigned PhysReg) {
236 PhysRegsUsed.erase(PhysReg); // PhyReg no longer used
238 std::vector<unsigned>::iterator It =
239 std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
240 assert(It != PhysRegsUseOrder.end() &&
241 "Spilled a physical register, but it was not in use list!");
242 PhysRegsUseOrder.erase(It);
245 /// spillVirtReg - This method spills the value specified by PhysReg into the
246 /// virtual register slot specified by VirtReg. It then updates the RA data
247 /// structures to indicate the fact that PhysReg is now available.
249 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
250 unsigned VirtReg, unsigned PhysReg) {
251 // If this is just a marker register, we don't need to spill it.
253 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
254 unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
256 // Add move instruction(s)
257 I = RegInfo.storeReg2RegOffset(MBB, I, PhysReg, RegInfo.getFramePointer(),
258 -stackOffset, RegClass->getDataSize());
259 ++NumSpilled; // Update statistics
260 Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available
263 removePhysReg(PhysReg);
267 /// isPhysRegAvailable - Return true if the specified physical register is free
268 /// and available for use. This also includes checking to see if aliased
269 /// registers are all free...
271 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
272 if (PhysRegsUsed.count(PhysReg)) return false;
274 // If the selected register aliases any other allocated registers, it is
276 if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
277 for (unsigned i = 0; AliasSet[i]; ++i)
278 if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use?
279 return false; // Can't use this reg then.
285 /// getFreeReg - Find a physical register to hold the specified virtual
286 /// register. If all compatible physical registers are used, this method spills
287 /// the last used virtual register to the stack, and uses that register.
289 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
291 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
292 unsigned PhysReg = 0;
294 // First check to see if we have a free register of the requested type...
295 for (TargetRegisterClass::iterator It = RegClass->begin(),E = RegClass->end();
298 if (isPhysRegAvailable(R)) { // Is reg unused?
299 if (isAllocatableRegister(R)) { // And is not a frame register?
300 // Found an unused register!
307 // If we didn't find an unused register, scavenge one now!
309 assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
311 // Loop over all of the preallocated registers from the least recently used
312 // to the most recently used. When we find one that is capable of holding
313 // our register, use it.
314 for (unsigned i = 0; PhysReg == 0; ++i) {
315 assert(i != PhysRegsUseOrder.size() &&
316 "Couldn't find a register of the appropriate class!");
318 unsigned R = PhysRegsUseOrder[i];
319 // If the current register is compatible, use it.
320 if (isAllocatableRegister(R)) {
321 if (RegInfo.getRegClass(R) == RegClass) {
325 // If one of the registers aliased to the current register is
326 // compatible, use it.
327 if (const unsigned *AliasSet = RegInfo.getAliasSet(R))
328 for (unsigned a = 0; AliasSet[a]; ++a)
329 if (RegInfo.getRegClass(AliasSet[a]) == RegClass) {
330 PhysReg = AliasSet[a]; // Take an aliased register
337 assert(isAllocatableRegister(PhysReg) && "Register is not allocatable!");
339 assert(PhysReg && "Physical register not assigned!?!?");
341 // At this point PhysRegsUseOrder[i] is the least recently used register of
342 // compatible register class. Spill it to memory and reap its remains.
343 spillPhysReg(MBB, I, PhysReg);
346 // Now that we know which register we need to assign this to, do it now!
347 AssignVirtToPhysReg(VirtReg, PhysReg);
352 void RA::AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
353 assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
354 "Phys reg already assigned!");
355 // Update information to note the fact that this register was just used, and
357 PhysRegsUsed[PhysReg] = VirtReg;
358 Virt2PhysRegMap[VirtReg] = PhysReg;
359 PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg
363 /// reloadVirtReg - This method loads the specified virtual register into a
364 /// physical register, returning the physical register chosen. This updates the
365 /// regalloc data structures to reflect the fact that the virtual reg is now
366 /// alive in a physical register, and the previous one isn't.
368 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
369 MachineBasicBlock::iterator &I,
371 std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
372 if (It != Virt2PhysRegMap.end()) {
373 MarkPhysRegRecentlyUsed(It->second);
374 return It->second; // Already have this value available!
377 unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
379 const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
380 unsigned StackOffset = getStackSpaceFor(VirtReg, RegClass);
382 // Add move instruction(s)
383 I = RegInfo.loadRegOffset2Reg(MBB, I, PhysReg, RegInfo.getFramePointer(),
384 -StackOffset, RegClass->getDataSize());
385 ++NumReloaded; // Update statistics
389 /// CalculateLastUseOfVReg - Calculate an approximation of the killing uses for
390 /// the virtual registers in the function. Here we try to capture registers
391 /// that are defined and only used within the same basic block. Because we
392 /// don't have use-def chains yet, we have to do this the hard way.
394 void RA::CalculateLastUseOfVReg(MachineBasicBlock &MBB,
395 std::map<unsigned, MachineInstr*> &LastUseOfVReg) const {
396 // Calculate the last machine instruction in this basic block that uses the
397 // specified virtual register defined in this basic block.
398 std::map<unsigned, MachineInstr*> LastLocalUses;
400 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;++I){
401 MachineInstr *MI = *I;
402 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
403 MachineOperand &Op = MI->getOperand(i);
404 if (Op.isVirtualRegister()) {
405 if (Op.opIsDef()) { // Definition of a new virtual reg?
406 LastLocalUses[Op.getAllocatedRegNum()] = 0; // Record it
407 } else { // Use of a virtual reg.
408 std::map<unsigned, MachineInstr*>::iterator It =
409 LastLocalUses.find(Op.getAllocatedRegNum());
410 if (It != LastLocalUses.end()) // Local use?
411 It->second = MI; // Update last use
413 LastUseOfVReg[Op.getAllocatedRegNum()] = 0;
419 // Move local uses over... if there are any uses of a local already in the
420 // lastuse map, the newly inserted entry is ignored.
421 LastUseOfVReg.insert(LastLocalUses.begin(), LastLocalUses.end());
425 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
426 /// predecessor basic blocks.
428 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
429 const MachineInstrInfo &MII = TM.getInstrInfo();
431 while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
432 MachineInstr *MI = MBB.front();
433 // Unlink the PHI node from the basic block... but don't delete the PHI yet
434 MBB.erase(MBB.begin());
436 assert(MI->getOperand(0).isVirtualRegister() &&
437 "PHI node doesn't write virt reg?");
439 unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
441 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
442 MachineOperand &opVal = MI->getOperand(i-1);
444 // Get the MachineBasicBlock equivalent of the BasicBlock that is the
445 // source path the phi
446 MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
448 // Check to make sure we haven't already emitted the copy for this block.
449 // This can happen because PHI nodes may have multiple entries for the
450 // same basic block. It doesn't matter which entry we use though, because
451 // all incoming values are guaranteed to be the same for a particular bb.
453 // Note that this is N^2 in the number of phi node entries, but since the
454 // # of entries is tiny, this is not a problem.
456 bool HaveNotEmitted = true;
457 for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
458 if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
459 HaveNotEmitted = false;
463 if (HaveNotEmitted) {
464 MachineBasicBlock::iterator opI = opBlock.end();
465 MachineInstr *opMI = *--opI;
467 // must backtrack over ALL the branches in the previous block
468 while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
471 // move back to the first branch instruction so new instructions
472 // are inserted right in front of it and not in front of a non-branch
473 if (!MII.isBranch(opMI->getOpcode()))
476 unsigned dataSize = MF->getRegClass(virtualReg)->getDataSize();
478 // Retrieve the constant value from this op, move it to target
479 // register of the phi
480 if (opVal.isImmediate()) {
481 opI = RegInfo.moveImm2Reg(opBlock, opI, virtualReg,
482 (unsigned) opVal.getImmedValue(),
485 opI = RegInfo.moveReg2Reg(opBlock, opI, virtualReg,
486 opVal.getAllocatedRegNum(), dataSize);
491 // really delete the PHI instruction now!
497 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
498 // loop over each instruction
499 MachineBasicBlock::iterator I = MBB.begin();
500 for (; I != MBB.end(); ++I) {
501 MachineInstr *MI = *I;
502 const MachineInstrDescriptor &MID = MIInfo.get(MI->getOpcode());
504 // Loop over all of the operands of the instruction, spilling registers that
505 // are defined, and marking explicit destinations in the PhysRegsUsed map.
506 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
507 if (MI->getOperand(i).opIsDef() &&
508 MI->getOperand(i).isPhysicalRegister()) {
509 unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
510 spillPhysReg(MBB, I, Reg);
511 PhysRegsUsed[Reg] = 0; // It's free now, and it's reserved
512 PhysRegsUseOrder.push_back(Reg);
515 // Loop over the implicit defs, spilling them, as above.
516 if (const unsigned *ImplicitDefs = MID.ImplicitDefs)
517 for (unsigned i = 0; ImplicitDefs[i]; ++i) {
518 unsigned Reg = ImplicitDefs[i];
520 // We don't want to spill implicit definitions if they were explicitly
521 // chosen. For this reason, check to see now if the register we are
522 // to spill has a vreg of 0.
523 if (PhysRegsUsed.count(Reg) && PhysRegsUsed[Reg] != 0) {
524 spillPhysReg(MBB, I, Reg);
525 PhysRegsUsed[Reg] = 0; // It's free now, and it's reserved
526 PhysRegsUseOrder.push_back(Reg);
530 // Loop over the implicit uses, making sure that they are at the head of the
531 // use order list, so they don't get reallocated.
532 if (const unsigned *ImplicitUses = MID.ImplicitUses)
533 for (unsigned i = 0; ImplicitUses[i]; ++i)
534 MarkPhysRegRecentlyUsed(ImplicitUses[i]);
536 // Loop over all of the operands again, getting the used operands into
537 // registers. This has the potiential to spill incoming values because we
538 // are out of registers.
540 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
541 if (MI->getOperand(i).opIsUse() &&
542 MI->getOperand(i).isVirtualRegister()) {
543 unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
544 unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
545 MI->SetMachineOperandReg(i, PhysSrcReg); // Assign the input register
548 // Okay, we have allocated all of the source operands and spilled any values
549 // that would be destroyed by defs of this instruction. Loop over the
550 // implicit defs and assign them to a register, spilling the incoming value
551 // if we need to scavange a register.
553 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
554 if (MI->getOperand(i).opIsDef() &&
555 !MI->getOperand(i).isPhysicalRegister()) {
556 unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
557 unsigned DestPhysReg;
559 if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
560 // must be same register number as the first operand
561 // This maps a = b + c into b += c, and saves b into a's spot
562 assert(MI->getOperand(1).isRegister() &&
563 MI->getOperand(1).getAllocatedRegNum() &&
564 MI->getOperand(1).opIsUse() &&
565 "Two address instruction invalid!");
566 DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
568 // Spill the incoming value, because we are about to change the
569 // register contents.
570 spillPhysReg(MBB, I, DestPhysReg);
571 AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
573 DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
575 MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register
579 // If this instruction is the last user of anything in registers, kill the
580 // value, freeing the register being used, so it doesn't need to be spilled
581 // to memory at the end of the block.
582 std::multimap<MachineInstr*, unsigned>::iterator LUOI =
583 LastUserOf.lower_bound(MI);
584 for (; LUOI != LastUserOf.end() && LUOI->first == MI; ++MI) {// entry found?
585 unsigned VirtReg = LUOI->second;
586 unsigned PhysReg = Virt2PhysRegMap[VirtReg];
588 DEBUG(std::cout << "V: " << VirtReg << " P: " << PhysReg << " Last use of: " << *MI);
589 removePhysReg(PhysReg);
591 Virt2PhysRegMap.erase(VirtReg);
596 // Rewind the iterator to point to the first flow control instruction...
597 const MachineInstrInfo &MII = TM.getInstrInfo();
601 } while ((MII.isReturn((*I)->getOpcode()) ||
602 MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
604 if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
607 // Spill all physical registers holding virtual registers now.
608 while (!PhysRegsUsed.empty())
609 spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
610 PhysRegsUsed.begin()->first);
612 assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
613 assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
617 /// EmitPrologue - Use the register info object to add a prologue to the
618 /// function and save any callee saved registers we are responsible for.
620 void RA::EmitPrologue() {
621 // Get a list of the callee saved registers, so that we can save them on entry
625 MachineBasicBlock &MBB = MF->front(); // Prolog goes in entry BB
626 MachineBasicBlock::iterator I = MBB.begin();
628 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
629 for (unsigned i = 0; CSRegs[i]; ++i) {
630 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
631 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
633 // Insert the spill to the stack frame...
635 I = RegInfo.storeReg2RegOffset(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
636 -Offset, RegClass->getDataSize());
639 // Add prologue to the function...
640 RegInfo.emitPrologue(*MF, NumBytesAllocated);
644 /// EmitEpilogue - Use the register info object to add a epilogue to the
645 /// function and restore any callee saved registers we are responsible for.
647 void RA::EmitEpilogue(MachineBasicBlock &MBB) {
648 // Insert instructions before the return.
649 MachineBasicBlock::iterator I = --MBB.end();
651 const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
652 for (unsigned i = 0; CSRegs[i]; ++i) {
653 const TargetRegisterClass *RegClass = RegInfo.getRegClass(CSRegs[i]);
654 unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
656 I = RegInfo.loadRegOffset2Reg(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
657 -Offset, RegClass->getDataSize());
658 --I; // Insert in reverse order
661 RegInfo.emitEpilogue(MBB, NumBytesAllocated);
665 /// runOnMachineFunction - Register allocate the whole function
667 bool RA::runOnMachineFunction(MachineFunction &Fn) {
668 DEBUG(std::cerr << "Machine Function " << "\n");
671 // First pass: eliminate PHI instructions by inserting copies into predecessor
672 // blocks, and calculate a simple approximation of killing uses for virtual
675 std::map<unsigned, MachineInstr*> LastUseOfVReg;
676 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
677 MBB != MBBe; ++MBB) {
679 CalculateLastUseOfVReg(*MBB, LastUseOfVReg);
680 EliminatePHINodes(*MBB);
683 // At this point LastUseOfVReg has been filled in to contain the last
684 // MachineInstr user of the specified virtual register, if that user is
685 // within the same basic block as the definition (otherwise it contains
686 // null). Invert this mapping now:
688 for (std::map<unsigned, MachineInstr*>::iterator I = LastUseOfVReg.begin(),
689 E = LastUseOfVReg.end(); I != E; ++I)
691 LastUserOf.insert(std::make_pair(I->second, I->first));
693 // We're done with the temporary list now.
694 LastUseOfVReg.clear();
696 // Loop over all of the basic blocks, eliminating virtual register references
697 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
699 AllocateBasicBlock(*MBB);
702 // Emit a prologue for the function...
705 const MachineInstrInfo &MII = TM.getInstrInfo();
707 // Add epilogue to restore the callee-save registers in each exiting block
708 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
709 MBB != MBBe; ++MBB) {
710 // If last instruction is a return instruction, add an epilogue
711 if (MII.isReturn(MBB->back()->getOpcode()))
716 cleanupAfterFunction();
720 Pass *createLocalRegisterAllocator(TargetMachine &TM) {