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 #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"
  14 #include <iostream>
  15
  16 namespace {
  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"));
  21
  22   class RA : public FunctionPass {
  23     TargetMachine &TM;
  24     MachineFunction *MF;
  25     const MRegisterInfo &RegInfo;
  26     const MachineInstrInfo &MIInfo;
  27     unsigned NumBytesAllocated;
  28
  29     // Maps SSA Regs => offsets on the stack where these values are stored
  30     std::map<unsigned, unsigned> VirtReg2OffsetMap;
  31
  32     // Virt2PhysRegMap - This map contains entries for each virtual register
  33     // that is currently available in a physical register.
  34     //
  35     std::map<unsigned, unsigned> Virt2PhysRegMap;
  36
  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.
  42     //
  43     std::map<unsigned, unsigned> PhysRegsUsed;
  44
  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.
  52     //
  53     std::vector<unsigned> PhysRegsUseOrder;
  54
  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
  59     //
  60     std::multimap<MachineInstr*, unsigned> LastUserOf;
  61
  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
  70             if (RegMatch == Reg)
  71               return;    // Found an exact match, exit early
  72           }
  73       }
  74     }
  75
  76   public:
  77
  78     RA(TargetMachine &tm)
  79       : TM(tm), RegInfo(*tm.getRegisterInfo()), MIInfo(tm.getInstrInfo()) {
  80       cleanupAfterFunction();
  81     }
  82
  83     bool runOnFunction(Function &Fn) {
  84       return runOnMachineFunction(MachineFunction::get(&Fn));
  85     }
  86
  87     virtual const char *getPassName() const {
  88       return "Local Register Allocator";
  89     }
  90
  91   private:
  92     /// runOnMachineFunction - Register allocate the whole function
  93     bool runOnMachineFunction(MachineFunction &Fn);
  94
  95     /// AllocateBasicBlock - Register allocate the specified basic block.
  96     void AllocateBasicBlock(MachineBasicBlock &MBB);
  97
  98     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
  99     /// in predecessor basic blocks.
 100     void EliminatePHINodes(MachineBasicBlock &MBB);
 101
 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
 106     /// way.
 107     ///
 108     void CalculateLastUseOfVReg(MachineBasicBlock &MBB,
 109                         std::map<unsigned, MachineInstr*> &LastUseOfVReg) const;
 110
 111
 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.
 115     ///
 116     void EmitPrologue();
 117     void EmitEpilogue(MachineBasicBlock &MBB);
 118
 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.
 122     ///
 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;
 128       return false;
 129     }
 130
 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);
 136     }
 137
 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);
 142
 143     void cleanupAfterFunction() {
 144       VirtReg2OffsetMap.clear();
 145       NumBytesAllocated = 4;   // FIXME: This is X86 specific
 146     }
 147
 148     void removePhysReg(unsigned PhysReg);
 149
 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.
 153     ///
 154     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 155                       unsigned VirtReg, unsigned PhysReg);
 156
 157     /// spillPhysReg - This method spills the specified physical register into
 158     /// the virtual register slot associated with it.
 159     //
 160     void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 161                       unsigned PhysReg) {
 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]);
 172         }
 173       }
 174     }
 175
 176     void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 177
 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...
 181     ///
 182     bool isPhysRegAvailable(unsigned PhysReg) const;
 183
 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
 187     /// register.
 188     ///
 189     unsigned getFreeReg(MachineBasicBlock &MBB,
 190                         MachineBasicBlock::iterator &I,
 191                         unsigned virtualReg);
 192
 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.
 197     ///
 198     unsigned reloadVirtReg(MachineBasicBlock &MBB,
 199                            MachineBasicBlock::iterator &I, unsigned VirtReg);
 200   };
 201 }
 202
 203
 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);
 211
 212   if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
 213     return I->second;          // Already has space allocated?
 214
 215   unsigned RegSize = RegClass->getDataSize();
 216
 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;
 222
 223   // Assign the slot...
 224   VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
 225
 226   // Reserve the space!
 227   NumBytesAllocated += RegSize;
 228   return NumBytesAllocated-RegSize;
 229 }
 230
 231
 232 /// removePhysReg - This method marks the specified physical register as no
 233 /// longer being in use.
 234 ///
 235 void RA::removePhysReg(unsigned PhysReg) {
 236   PhysRegsUsed.erase(PhysReg);      // PhyReg no longer used
 237
 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);
 243 }
 244
 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.
 248 ///
 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.
 252   if (VirtReg != 0) {
 253     const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 254     unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
 255
 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
 261   }
 262
 263   removePhysReg(PhysReg);
 264 }
 265
 266
 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...
 270 ///
 271 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
 272   if (PhysRegsUsed.count(PhysReg)) return false;
 273
 274   // If the selected register aliases any other allocated registers, it is
 275   // not free!
 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.
 280   return true;
 281 }
 282
 283
 284
 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.
 288 ///
 289 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 290                         unsigned VirtReg) {
 291   const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 292   unsigned PhysReg = 0;
 293
 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();
 296        It != E; ++It) {
 297     unsigned R = *It;
 298     if (isPhysRegAvailable(R)) {       // Is reg unused?
 299       if (isAllocatableRegister(R)) {  // And is not a frame register?
 300         // Found an unused register!
 301         PhysReg = R;
 302         break;
 303       }
 304     }
 305   }
 306
 307   // If we didn't find an unused register, scavenge one now!
 308   if (PhysReg == 0) {
 309     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 310
 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!");
 317
 318       unsigned R = PhysRegsUseOrder[i];
 319       // If the current register is compatible, use it.
 320       if (isAllocatableRegister(R)) {
 321         if (RegInfo.getRegClass(R) == RegClass) {
 322           PhysReg = R;
 323           break;
 324         } else {
 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
 331                 break;
 332               }
 333         }
 334       }
 335     }
 336
 337     assert(isAllocatableRegister(PhysReg) && "Register is not allocatable!");
 338
 339     assert(PhysReg && "Physical register not assigned!?!?");
 340
 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);
 344   }
 345
 346   // Now that we know which register we need to assign this to, do it now!
 347   AssignVirtToPhysReg(VirtReg, PhysReg);
 348   return PhysReg;
 349 }
 350
 351
 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
 356   // it holds VirtReg.
 357   PhysRegsUsed[PhysReg] = VirtReg;
 358   Virt2PhysRegMap[VirtReg] = PhysReg;
 359   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
 360 }
 361
 362
 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.
 367 ///
 368 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
 369                            MachineBasicBlock::iterator &I,
 370                            unsigned VirtReg) {
 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!
 375   }
 376
 377   unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
 378
 379   const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 380   unsigned StackOffset = getStackSpaceFor(VirtReg, RegClass);
 381
 382   // Add move instruction(s)
 383   I = RegInfo.loadRegOffset2Reg(MBB, I, PhysReg, RegInfo.getFramePointer(),
 384                                 -StackOffset, RegClass->getDataSize());
 385   ++NumReloaded;    // Update statistics
 386   return PhysReg;
 387 }
 388
 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.
 393 ///
 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;
 399
 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
 412           else
 413             LastUseOfVReg[Op.getAllocatedRegNum()] = 0;
 414         }
 415       }
 416     }
 417   }
 418
 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());
 422 }
 423
 424
 425 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 426 /// predecessor basic blocks.
 427 ///
 428 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
 429   const MachineInstrInfo &MII = TM.getInstrInfo();
 430
 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());
 435
 436     assert(MI->getOperand(0).isVirtualRegister() &&
 437            "PHI node doesn't write virt reg?");
 438
 439     unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
 440
 441     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 442       MachineOperand &opVal = MI->getOperand(i-1);
 443
 444       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 445       // source path the phi
 446       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
 447
 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.
 452       //
 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.
 455       //
 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;
 460           break;
 461         }
 462
 463       if (HaveNotEmitted) {
 464         MachineBasicBlock::iterator opI = opBlock.end();
 465         MachineInstr *opMI = *--opI;
 466
 467         // must backtrack over ALL the branches in the previous block
 468         while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
 469           opMI = *--opI;
 470
 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()))
 474           ++opI;
 475
 476         unsigned dataSize = MF->getRegClass(virtualReg)->getDataSize();
 477
 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(),
 483                                     dataSize);
 484         } else {
 485           opI = RegInfo.moveReg2Reg(opBlock, opI, virtualReg,
 486                                     opVal.getAllocatedRegNum(), dataSize);
 487         }
 488       }
 489     }
 490
 491     // really delete the PHI instruction now!
 492     delete MI;
 493   }
 494 }
 495
 496
 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());
 503
 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);
 513       }
 514
 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];
 519
 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);
 527         }
 528       }
 529
 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]);
 535
 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.
 539     //
 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
 546       }
 547
 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.
 552     //
 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;
 558
 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();
 567
 568           // Spill the incoming value, because we are about to change the
 569           // register contents.
 570           spillPhysReg(MBB, I, DestPhysReg);
 571           AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
 572         } else {
 573           DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
 574         }
 575         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
 576       }
 577
 578     if (!DisableKill) {
 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];
 587         if (PhysReg) {
 588           DEBUG(std::cout << "V: " << VirtReg << " P: " << PhysReg << " Last use of: " << *MI);
 589           removePhysReg(PhysReg);
 590         }
 591         Virt2PhysRegMap.erase(VirtReg);
 592       }
 593     }
 594   }
 595
 596   // Rewind the iterator to point to the first flow control instruction...
 597   const MachineInstrInfo &MII = TM.getInstrInfo();
 598   I = MBB.end();
 599   do {
 600     --I;
 601   } while ((MII.isReturn((*I)->getOpcode()) ||
 602             MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
 603
 604   if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
 605     ++I;
 606
 607   // Spill all physical registers holding virtual registers now.
 608   while (!PhysRegsUsed.empty())
 609     spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
 610                  PhysRegsUsed.begin()->first);
 611
 612   assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
 613   assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
 614 }
 615
 616
 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.
 619 ///
 620 void RA::EmitPrologue() {
 621   // Get a list of the callee saved registers, so that we can save them on entry
 622   // to the function.
 623   //
 624
 625   MachineBasicBlock &MBB = MF->front();   // Prolog goes in entry BB
 626   MachineBasicBlock::iterator I = MBB.begin();
 627
 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);
 632
 633     // Insert the spill to the stack frame...
 634     ++NumSpilled;
 635     I = RegInfo.storeReg2RegOffset(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
 636                                    -Offset, RegClass->getDataSize());
 637   }
 638
 639   // Add prologue to the function...
 640   RegInfo.emitPrologue(*MF, NumBytesAllocated);
 641 }
 642
 643
 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.
 646 ///
 647 void RA::EmitEpilogue(MachineBasicBlock &MBB) {
 648   // Insert instructions before the return.
 649   MachineBasicBlock::iterator I = --MBB.end();
 650
 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);
 655     ++NumReloaded;
 656     I = RegInfo.loadRegOffset2Reg(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
 657                                   -Offset, RegClass->getDataSize());
 658     --I;  // Insert in reverse order
 659   }
 660
 661   RegInfo.emitEpilogue(MBB, NumBytesAllocated);
 662 }
 663
 664
 665 /// runOnMachineFunction - Register allocate the whole function
 666 ///
 667 bool RA::runOnMachineFunction(MachineFunction &Fn) {
 668   DEBUG(std::cerr << "Machine Function " << "\n");
 669   MF = &Fn;
 670
 671   // First pass: eliminate PHI instructions by inserting copies into predecessor
 672   // blocks, and calculate a simple approximation of killing uses for virtual
 673   // registers.
 674   //
 675   std::map<unsigned, MachineInstr*> LastUseOfVReg;
 676   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 677        MBB != MBBe; ++MBB) {
 678     if (!DisableKill)
 679       CalculateLastUseOfVReg(*MBB, LastUseOfVReg);
 680     EliminatePHINodes(*MBB);
 681   }
 682
 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:
 687   if (!DisableKill)
 688     for (std::map<unsigned, MachineInstr*>::iterator I = LastUseOfVReg.begin(),
 689          E = LastUseOfVReg.end(); I != E; ++I)
 690       if (I->second)
 691         LastUserOf.insert(std::make_pair(I->second, I->first));
 692
 693   // We're done with the temporary list now.
 694   LastUseOfVReg.clear();
 695
 696   // Loop over all of the basic blocks, eliminating virtual register references
 697   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 698        MBB != MBBe; ++MBB)
 699     AllocateBasicBlock(*MBB);
 700
 701
 702   // Emit a prologue for the function...
 703   EmitPrologue();
 704
 705   const MachineInstrInfo &MII = TM.getInstrInfo();
 706
 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()))
 712       EmitEpilogue(*MBB);
 713   }
 714
 715   LastUserOf.clear();
 716   cleanupAfterFunction();
 717   return true;
 718 }
 719
 720 Pass *createLocalRegisterAllocator(TargetMachine &TM) {
 721   return new RA(TM);
 722 }