* Fix spelling of 'necessary'
[oota-llvm.git] / lib / CodeGen / RegAllocLocal.cpp
1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
2 //
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.
5 //
6 //===----------------------------------------------------------------------===//
7
8 #define DEBUG_TYPE "regalloc"
9 #include "llvm/CodeGen/Passes.h"
10 #include "llvm/CodeGen/MachineFunctionPass.h"
11 #include "llvm/CodeGen/MachineInstr.h"
12 #include "llvm/CodeGen/SSARegMap.h"
13 #include "llvm/CodeGen/MachineFrameInfo.h"
14 #include "llvm/CodeGen/LiveVariables.h"
15 #include "llvm/Target/TargetInstrInfo.h"
16 #include "llvm/Target/TargetMachine.h"
17 #include "Support/CommandLine.h"
18 #include "Support/Debug.h"
19 #include "Support/Statistic.h"
20 #include <iostream>
21
22 namespace {
23   Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
24   Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
25   cl::opt<bool> DisableKill("no-kill", cl::Hidden, 
26                             cl::desc("Disable register kill in local-ra"));
27
28   class RA : public MachineFunctionPass {
29     const TargetMachine *TM;
30     MachineFunction *MF;
31     const MRegisterInfo *RegInfo;
32     LiveVariables *LV;
33
34     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
35     // values are spilled.
36     std::map<unsigned, int> StackSlotForVirtReg;
37
38     // Virt2PhysRegMap - This map contains entries for each virtual register
39     // that is currently available in a physical register.
40     //
41     std::map<unsigned, unsigned> Virt2PhysRegMap;
42     
43     // PhysRegsUsed - This map contains entries for each physical register that
44     // currently has a value (ie, it is in Virt2PhysRegMap).  The value mapped
45     // to is the virtual register corresponding to the physical register (the
46     // inverse of the Virt2PhysRegMap), or 0.  The value is set to 0 if this
47     // register is pinned because it is used by a future instruction.
48     //
49     std::map<unsigned, unsigned> PhysRegsUsed;
50
51     // PhysRegsUseOrder - This contains a list of the physical registers that
52     // currently have a virtual register value in them.  This list provides an
53     // ordering of registers, imposing a reallocation order.  This list is only
54     // used if all registers are allocated and we have to spill one, in which
55     // case we spill the least recently used register.  Entries at the front of
56     // the list are the least recently used registers, entries at the back are
57     // the most recently used.
58     //
59     std::vector<unsigned> PhysRegsUseOrder;
60
61     // VirtRegModified - This bitset contains information about which virtual
62     // registers need to be spilled back to memory when their registers are
63     // scavenged.  If a virtual register has simply been rematerialized, there
64     // is no reason to spill it to memory when we need the register back.
65     //
66     std::vector<bool> VirtRegModified;
67
68     void markVirtRegModified(unsigned Reg, bool Val = true) {
69       assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!");
70       Reg -= MRegisterInfo::FirstVirtualRegister;
71       if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1);
72       VirtRegModified[Reg] = Val;
73     }
74
75     bool isVirtRegModified(unsigned Reg) const {
76       assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!");
77       assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
78              && "Illegal virtual register!");
79       return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister];
80     }
81
82     void MarkPhysRegRecentlyUsed(unsigned Reg) {
83       assert(!PhysRegsUseOrder.empty() && "No registers used!");
84       if (PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
85
86       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
87         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
88           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
89           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
90           // Add it to the end of the list
91           PhysRegsUseOrder.push_back(RegMatch);
92           if (RegMatch == Reg) 
93             return;    // Found an exact match, exit early
94         }
95     }
96
97   public:
98     virtual const char *getPassName() const {
99       return "Local Register Allocator";
100     }
101
102     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
103       if (!DisableKill)
104         AU.addRequired<LiveVariables>();
105       AU.addRequiredID(PHIEliminationID);
106       MachineFunctionPass::getAnalysisUsage(AU);
107     }
108
109   private:
110     /// runOnMachineFunction - Register allocate the whole function
111     bool runOnMachineFunction(MachineFunction &Fn);
112
113     /// AllocateBasicBlock - Register allocate the specified basic block.
114     void AllocateBasicBlock(MachineBasicBlock &MBB);
115
116
117     /// areRegsEqual - This method returns true if the specified registers are
118     /// related to each other.  To do this, it checks to see if they are equal
119     /// or if the first register is in the alias set of the second register.
120     ///
121     bool areRegsEqual(unsigned R1, unsigned R2) const {
122       if (R1 == R2) return true;
123       if (const unsigned *AliasSet = RegInfo->getAliasSet(R2))
124         for (unsigned i = 0; AliasSet[i]; ++i)
125           if (AliasSet[i] == R1) return true;
126       return false;
127     }
128
129     /// getStackSpaceFor - This returns the frame index of the specified virtual
130     /// register on the stack, allocating space if necessary.
131     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
132
133     /// removePhysReg - This method marks the specified physical register as no
134     /// longer being in use.
135     ///
136     void removePhysReg(unsigned PhysReg);
137
138     /// spillVirtReg - This method spills the value specified by PhysReg into
139     /// the virtual register slot specified by VirtReg.  It then updates the RA
140     /// data structures to indicate the fact that PhysReg is now available.
141     ///
142     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
143                       unsigned VirtReg, unsigned PhysReg);
144
145     /// spillPhysReg - This method spills the specified physical register into
146     /// the virtual register slot associated with it.
147     ///
148     void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
149                       unsigned PhysReg);
150
151     /// assignVirtToPhysReg - This method updates local state so that we know
152     /// that PhysReg is the proper container for VirtReg now.  The physical
153     /// register must not be used for anything else when this is called.
154     ///
155     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
156
157     /// liberatePhysReg - Make sure the specified physical register is available
158     /// for use.  If there is currently a value in it, it is either moved out of
159     /// the way or spilled to memory.
160     ///
161     void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
162                          unsigned PhysReg);
163
164     /// isPhysRegAvailable - Return true if the specified physical register is
165     /// free and available for use.  This also includes checking to see if
166     /// aliased registers are all free...
167     ///
168     bool isPhysRegAvailable(unsigned PhysReg) const;
169
170     /// getFreeReg - Look to see if there is a free register available in the
171     /// specified register class.  If not, return 0.
172     ///
173     unsigned getFreeReg(const TargetRegisterClass *RC);
174     
175     /// getReg - Find a physical register to hold the specified virtual
176     /// register.  If all compatible physical registers are used, this method
177     /// spills the last used virtual register to the stack, and uses that
178     /// register.
179     ///
180     unsigned getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
181                     unsigned VirtReg);
182
183     /// reloadVirtReg - This method loads the specified virtual register into a
184     /// physical register, returning the physical register chosen.  This updates
185     /// the regalloc data structures to reflect the fact that the virtual reg is
186     /// now alive in a physical register, and the previous one isn't.
187     ///
188     unsigned reloadVirtReg(MachineBasicBlock &MBB,
189                            MachineBasicBlock::iterator &I, unsigned VirtReg);
190
191     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
192                        unsigned PhysReg);
193   };
194 }
195
196
197 /// getStackSpaceFor - This allocates space for the specified virtual register
198 /// to be held on the stack.
199 int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
200   // Find the location Reg would belong...
201   std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg);
202
203   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
204     return I->second;          // Already has space allocated?
205
206   // Allocate a new stack object for this spill location...
207   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC);
208
209   // Assign the slot...
210   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
211   return FrameIdx;
212 }
213
214
215 /// removePhysReg - This method marks the specified physical register as no 
216 /// longer being in use.
217 ///
218 void RA::removePhysReg(unsigned PhysReg) {
219   PhysRegsUsed.erase(PhysReg);      // PhyReg no longer used
220
221   std::vector<unsigned>::iterator It =
222     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
223   assert(It != PhysRegsUseOrder.end() &&
224          "Spilled a physical register, but it was not in use list!");
225   PhysRegsUseOrder.erase(It);
226 }
227
228
229 /// spillVirtReg - This method spills the value specified by PhysReg into the
230 /// virtual register slot specified by VirtReg.  It then updates the RA data
231 /// structures to indicate the fact that PhysReg is now available.
232 ///
233 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
234                       unsigned VirtReg, unsigned PhysReg) {
235
236   DEBUG(std::cerr << "  Spilling register " << RegInfo->getName(PhysReg));
237   if (VirtReg == 0) {
238     DEBUG(std::cerr << " which corresponds to no vreg, "
239                     << "must be spurious physreg: ignoring (WARNING)\n");
240   } else {
241     // FIXME: move this into the conditional??
242     const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
243     int FrameIndex = getStackSpaceFor(VirtReg, RC);
244
245     DEBUG(std::cerr << " containing %reg" << VirtReg;
246           if (!isVirtRegModified(VirtReg))
247            std::cerr << " which has not been modified, so no store necessary!");
248
249     // Otherwise, there is a virtual register corresponding to this physical
250     // register.  We only need to spill it into its stack slot if it has been
251     // modified.
252     if (isVirtRegModified(VirtReg)) {
253       DEBUG(std::cerr << " to stack slot #" << FrameIndex);
254       RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC);
255       ++NumSpilled;   // Update statistics
256     }
257     Virt2PhysRegMap.erase(VirtReg);   // VirtReg no longer available
258   }
259
260   DEBUG(std::cerr << "\n");
261   removePhysReg(PhysReg);
262 }
263
264
265 /// spillPhysReg - This method spills the specified physical register into the
266 /// virtual register slot associated with it.
267 ///
268 void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
269                       unsigned PhysReg) {
270   std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
271   if (PI != PhysRegsUsed.end()) {             // Only spill it if it's used!
272     spillVirtReg(MBB, I, PI->second, PhysReg);
273   } else if (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg)) {
274     // If the selected register aliases any other registers, we must make
275     // sure that one of the aliases isn't alive...
276     for (unsigned i = 0; AliasSet[i]; ++i) {
277       PI = PhysRegsUsed.find(AliasSet[i]);
278       if (PI != PhysRegsUsed.end())     // Spill aliased register...
279         spillVirtReg(MBB, I, PI->second, AliasSet[i]);
280     }
281   }
282 }
283
284
285 /// assignVirtToPhysReg - This method updates local state so that we know
286 /// that PhysReg is the proper container for VirtReg now.  The physical
287 /// register must not be used for anything else when this is called.
288 ///
289 void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
290   assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
291          "Phys reg already assigned!");
292   // Update information to note the fact that this register was just used, and
293   // it holds VirtReg.
294   PhysRegsUsed[PhysReg] = VirtReg;
295   Virt2PhysRegMap[VirtReg] = PhysReg;
296   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
297 }
298
299
300 /// isPhysRegAvailable - Return true if the specified physical register is free
301 /// and available for use.  This also includes checking to see if aliased
302 /// registers are all free...
303 ///
304 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
305   if (PhysRegsUsed.count(PhysReg)) return false;
306
307   // If the selected register aliases any other allocated registers, it is
308   // not free!
309   if (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg))
310     for (unsigned i = 0; AliasSet[i]; ++i)
311       if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use?
312         return false;                      // Can't use this reg then.
313   return true;
314 }
315
316
317 /// getFreeReg - Look to see if there is a free register available in the
318 /// specified register class.  If not, return 0.
319 ///
320 unsigned RA::getFreeReg(const TargetRegisterClass *RC) {
321   // Get iterators defining the range of registers that are valid to allocate in
322   // this class, which also specifies the preferred allocation order.
323   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
324   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
325
326   for (; RI != RE; ++RI)
327     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
328       assert(*RI != 0 && "Cannot use register!");
329       return *RI; // Found an unused register!
330     }
331   return 0;
332 }
333
334
335 /// liberatePhysReg - Make sure the specified physical register is available for
336 /// use.  If there is currently a value in it, it is either moved out of the way
337 /// or spilled to memory.
338 ///
339 void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
340                          unsigned PhysReg) {
341   // FIXME: This code checks to see if a register is available, but it really
342   // wants to know if a reg is available BEFORE the instruction executes.  If
343   // called after killed operands are freed, it runs the risk of reallocating a
344   // used operand...
345 #if 0
346   if (isPhysRegAvailable(PhysReg)) return;  // Already available...
347
348   // Check to see if the register is directly used, not indirectly used through
349   // aliases.  If aliased registers are the ones actually used, we cannot be
350   // sure that we will be able to save the whole thing if we do a reg-reg copy.
351   std::map<unsigned, unsigned>::iterator PRUI = PhysRegsUsed.find(PhysReg);
352   if (PRUI != PhysRegsUsed.end()) {
353     unsigned VirtReg = PRUI->second;   // The virtual register held...
354
355     // Check to see if there is a compatible register available.  If so, we can
356     // move the value into the new register...
357     //
358     const TargetRegisterClass *RC = RegInfo->getRegClass(PhysReg);
359     if (unsigned NewReg = getFreeReg(RC)) {
360       // Emit the code to copy the value...
361       RegInfo->copyRegToReg(MBB, I, NewReg, PhysReg, RC);
362       
363       // Update our internal state to indicate that PhysReg is available and Reg
364       // isn't.
365       Virt2PhysRegMap.erase(VirtReg);
366       removePhysReg(PhysReg);  // Free the physreg
367       
368       // Move reference over to new register...
369       assignVirtToPhysReg(VirtReg, NewReg);
370       return;
371     }
372   }
373 #endif
374   spillPhysReg(MBB, I, PhysReg);
375 }
376
377
378 /// getReg - Find a physical register to hold the specified virtual
379 /// register.  If all compatible physical registers are used, this method spills
380 /// the last used virtual register to the stack, and uses that register.
381 ///
382 unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
383                     unsigned VirtReg) {
384   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
385
386   // First check to see if we have a free register of the requested type...
387   unsigned PhysReg = getFreeReg(RC);
388
389   // If we didn't find an unused register, scavenge one now!
390   if (PhysReg == 0) {
391     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
392
393     // Loop over all of the preallocated registers from the least recently used
394     // to the most recently used.  When we find one that is capable of holding
395     // our register, use it.
396     for (unsigned i = 0; PhysReg == 0; ++i) {
397       assert(i != PhysRegsUseOrder.size() &&
398              "Couldn't find a register of the appropriate class!");
399       
400       unsigned R = PhysRegsUseOrder[i];
401       // If the current register is compatible, use it.
402       if (RegInfo->getRegClass(R) == RC) {
403         PhysReg = R;
404         break;
405       } else {
406         // If one of the registers aliased to the current register is
407         // compatible, use it.
408         if (const unsigned *AliasSet = RegInfo->getAliasSet(R))
409           for (unsigned a = 0; AliasSet[a]; ++a)
410             if (RegInfo->getRegClass(AliasSet[a]) == RC) {
411               PhysReg = AliasSet[a];    // Take an aliased register
412               break;
413             }
414       }
415     }
416
417     assert(PhysReg && "Physical register not assigned!?!?");
418
419     // At this point PhysRegsUseOrder[i] is the least recently used register of
420     // compatible register class.  Spill it to memory and reap its remains.
421     spillPhysReg(MBB, I, PhysReg);
422   }
423
424   // Now that we know which register we need to assign this to, do it now!
425   assignVirtToPhysReg(VirtReg, PhysReg);
426   return PhysReg;
427 }
428
429
430 /// reloadVirtReg - This method loads the specified virtual register into a
431 /// physical register, returning the physical register chosen.  This updates the
432 /// regalloc data structures to reflect the fact that the virtual reg is now
433 /// alive in a physical register, and the previous one isn't.
434 ///
435 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
436                            MachineBasicBlock::iterator &I,
437                            unsigned VirtReg) {
438   std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
439   if (It != Virt2PhysRegMap.end()) {
440     MarkPhysRegRecentlyUsed(It->second);
441     return It->second;               // Already have this value available!
442   }
443
444   unsigned PhysReg = getReg(MBB, I, VirtReg);
445
446   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
447   int FrameIndex = getStackSpaceFor(VirtReg, RC);
448
449   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
450
451   DEBUG(std::cerr << "  Reloading %reg" << VirtReg << " into "
452                   << RegInfo->getName(PhysReg) << "\n");
453
454   // Add move instruction(s)
455   RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIndex, RC);
456   ++NumReloaded;    // Update statistics
457   return PhysReg;
458 }
459
460
461
462 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
463   // loop over each instruction
464   MachineBasicBlock::iterator I = MBB.begin();
465   for (; I != MBB.end(); ++I) {
466     MachineInstr *MI = *I;
467     const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode());
468     DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI;
469           std::cerr << "  Regs have values: ";
470           for (std::map<unsigned, unsigned>::const_iterator
471                  I = PhysRegsUsed.begin(), E = PhysRegsUsed.end(); I != E; ++I)
472              std::cerr << "[" << RegInfo->getName(I->first)
473                        << ",%reg" << I->second << "] ";
474           std::cerr << "\n");
475
476     // Loop over the implicit uses, making sure that they are at the head of the
477     // use order list, so they don't get reallocated.
478     if (const unsigned *ImplicitUses = TID.ImplicitUses)
479       for (unsigned i = 0; ImplicitUses[i]; ++i)
480         MarkPhysRegRecentlyUsed(ImplicitUses[i]);
481
482     // Get the used operands into registers.  This has the potiential to spill
483     // incoming values if we are out of registers.  Note that we completely
484     // ignore physical register uses here.  We assume that if an explicit
485     // physical register is referenced by the instruction, that it is guaranteed
486     // to be live-in, or the input is badly hosed.
487     //
488     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
489       if (MI->getOperand(i).opIsUse() && MI->getOperand(i).isVirtualRegister()){
490         unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
491         unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
492         MI->SetMachineOperandReg(i, PhysSrcReg);  // Assign the input register
493       }
494     
495     if (!DisableKill) {
496       // If this instruction is the last user of anything in registers, kill the
497       // value, freeing the register being used, so it doesn't need to be
498       // spilled to memory.
499       //
500       for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
501              KE = LV->killed_end(MI); KI != KE; ++KI) {
502         unsigned VirtReg = KI->second;
503         unsigned PhysReg = VirtReg;
504         if (VirtReg >= MRegisterInfo::FirstVirtualRegister) {
505           std::map<unsigned, unsigned>::iterator I =
506             Virt2PhysRegMap.find(VirtReg);
507           assert(I != Virt2PhysRegMap.end());
508           PhysReg = I->second;
509           Virt2PhysRegMap.erase(I);
510         }
511
512         if (PhysReg) {
513           DEBUG(std::cerr << "  Last use of " << RegInfo->getName(PhysReg)
514                       << "[%reg" << VirtReg <<"], removing it from live set\n");
515           // If the physical register was used, but there was no definition of
516           // the physical register (we are reading garbage), Live Variables will
517           // tell us that this is the last use of the register even though we
518           // don't know of anything in the register.  No need to remove it.
519           if (VirtReg != PhysReg || PhysRegsUsed.count(PhysReg))
520             removePhysReg(PhysReg);
521         }
522       }
523     }
524
525     // Loop over all of the operands of the instruction, spilling registers that
526     // are defined, and marking explicit destinations in the PhysRegsUsed map.
527     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
528       if ((MI->getOperand(i).opIsDefOnly() ||
529            MI->getOperand(i).opIsDefAndUse()) &&
530           MI->getOperand(i).isPhysicalRegister()) {
531         unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
532         spillPhysReg(MBB, I, Reg);        // Spill any existing value in the reg
533         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
534         PhysRegsUseOrder.push_back(Reg);
535       }
536
537     // Loop over the implicit defs, spilling them as well.
538     if (const unsigned *ImplicitDefs = TID.ImplicitDefs)
539       for (unsigned i = 0; ImplicitDefs[i]; ++i) {
540         unsigned Reg = ImplicitDefs[i];
541         spillPhysReg(MBB, I, Reg);
542         PhysRegsUseOrder.push_back(Reg);
543         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
544       }
545
546     // Okay, we have allocated all of the source operands and spilled any values
547     // that would be destroyed by defs of this instruction.  Loop over the
548     // implicit defs and assign them to a register, spilling incoming values if
549     // we need to scavenge a register.
550     //
551     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
552       if ((MI->getOperand(i).opIsDefOnly() || MI->getOperand(i).opIsDefAndUse())
553           && MI->getOperand(i).isVirtualRegister()) {
554         unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
555         unsigned DestPhysReg;
556
557         // If DestVirtReg already has a value, forget about it.  Why doesn't
558         // getReg do this right?
559         std::map<unsigned, unsigned>::iterator DestI =
560           Virt2PhysRegMap.find(DestVirtReg);
561         if (DestI != Virt2PhysRegMap.end()) {
562           unsigned PhysReg = DestI->second;
563           Virt2PhysRegMap.erase(DestI);
564           removePhysReg(PhysReg);
565         }
566
567         if (TM->getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
568           // must be same register number as the first operand
569           // This maps a = b + c into b += c, and saves b into a's spot
570           assert(MI->getOperand(1).isRegister()  &&
571                  MI->getOperand(1).getAllocatedRegNum() &&
572                  MI->getOperand(1).opIsUse() &&
573                  "Two address instruction invalid!");
574           DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
575
576           liberatePhysReg(MBB, I, DestPhysReg);
577           assignVirtToPhysReg(DestVirtReg, DestPhysReg);
578         } else {
579           DestPhysReg = getReg(MBB, I, DestVirtReg);
580         }
581         markVirtRegModified(DestVirtReg);
582         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
583       }
584
585     if (!DisableKill) {
586       // If this instruction defines any registers that are immediately dead,
587       // kill them now.
588       //
589       for (LiveVariables::killed_iterator KI = LV->dead_begin(MI),
590              KE = LV->dead_end(MI); KI != KE; ++KI) {
591         unsigned VirtReg = KI->second;
592         unsigned PhysReg = VirtReg;
593         if (VirtReg >= MRegisterInfo::FirstVirtualRegister) {
594           std::map<unsigned, unsigned>::iterator I =
595             Virt2PhysRegMap.find(VirtReg);
596           assert(I != Virt2PhysRegMap.end());
597           PhysReg = I->second;
598           Virt2PhysRegMap.erase(I);
599         }
600
601         if (PhysReg) {
602           DEBUG(std::cerr << "  Register " << RegInfo->getName(PhysReg)
603                           << " [%reg" << VirtReg
604                           << "] is never used, removing it frame live list\n");
605           removePhysReg(PhysReg);
606         }
607       }
608     }
609   }
610
611   // Rewind the iterator to point to the first flow control instruction...
612   const TargetInstrInfo &TII = TM->getInstrInfo();
613   I = MBB.end();
614   while (I != MBB.begin() && TII.isTerminatorInstr((*(I-1))->getOpcode()))
615     --I;
616
617   // Spill all physical registers holding virtual registers now.
618   while (!PhysRegsUsed.empty())
619     spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
620                  PhysRegsUsed.begin()->first);
621
622   for (std::map<unsigned, unsigned>::iterator I = Virt2PhysRegMap.begin(),
623          E = Virt2PhysRegMap.end(); I != E; ++I)
624     std::cerr << "Register still mapped: " << I->first << " -> "
625               << I->second << "\n";
626
627   assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
628   assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
629 }
630
631
632 /// runOnMachineFunction - Register allocate the whole function
633 ///
634 bool RA::runOnMachineFunction(MachineFunction &Fn) {
635   DEBUG(std::cerr << "Machine Function " << "\n");
636   MF = &Fn;
637   TM = &Fn.getTarget();
638   RegInfo = TM->getRegisterInfo();
639
640   if (!DisableKill)
641     LV = &getAnalysis<LiveVariables>();
642
643   // Loop over all of the basic blocks, eliminating virtual register references
644   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
645        MBB != MBBe; ++MBB)
646     AllocateBasicBlock(*MBB);
647
648   StackSlotForVirtReg.clear();
649   VirtRegModified.clear();
650   return true;
651 }
652
653 Pass *createLocalRegisterAllocator() {
654   return new RA();
655 }