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 <iostream>
  14
  15 /// PhysRegClassMap - Construct a mapping of physical register numbers to their
  16 /// register classes.
  17 ///
  18 /// NOTE: This class will eventually be pulled out to somewhere shared.
  19 ///
  20 class PhysRegClassMap {
  21   std::map<unsigned, const TargetRegisterClass*> PhysReg2RegClassMap;
  22 public:
  23   PhysRegClassMap(const MRegisterInfo *RI) {
  24     for (MRegisterInfo::const_iterator I = RI->regclass_begin(),
  25            E = RI->regclass_end(); I != E; ++I)
  26       for (unsigned i=0; i < (*I)->getNumRegs(); ++i)
  27         PhysReg2RegClassMap[(*I)->getRegister(i)] = *I;
  28   }
  29
  30   const TargetRegisterClass *operator[](unsigned Reg) {
  31     assert(PhysReg2RegClassMap[Reg] && "Register is not a known physreg!");
  32     return PhysReg2RegClassMap[Reg];
  33   }
  34
  35   const TargetRegisterClass *get(unsigned Reg) { return operator[](Reg); }
  36 };
  37
  38 namespace {
  39   Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
  40   Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
  41
  42   class RA : public FunctionPass {
  43     TargetMachine &TM;
  44     MachineFunction *MF;
  45     const MRegisterInfo *RegInfo;
  46     unsigned NumBytesAllocated;
  47     PhysRegClassMap PhysRegClasses;
  48
  49     // Maps SSA Regs => offsets on the stack where these values are stored
  50     std::map<unsigned, unsigned> VirtReg2OffsetMap;
  51
  52     // Virt2PhysRegMap - This map contains entries for each virtual register
  53     // that is currently available in a physical register.
  54     //
  55     std::map<unsigned, unsigned> Virt2PhysRegMap;
  56
  57     // PhysRegsUsed - This map contains entries for each physical register that
  58     // currently has a value (ie, it is in Virt2PhysRegMap).  The value mapped
  59     // to is the virtual register corresponding to the physical register (the
  60     // inverse of the Virt2PhysRegMap), or 0.  The value is set to 0 if this
  61     // register is pinned because it is used by a future instruction.
  62     //
  63     std::map<unsigned, unsigned> PhysRegsUsed;
  64
  65     // PhysRegsUseOrder - This contains a list of the physical registers that
  66     // currently have a virtual register value in them.  This list provides an
  67     // ordering of registers, imposing a reallocation order.  This list is only
  68     // used if all registers are allocated and we have to spill one, in which
  69     // case we spill the least recently used register.  Entries at the front of
  70     // the list are the least recently used registers, entries at the back are
  71     // the most recently used.
  72     //
  73     std::vector<unsigned> PhysRegsUseOrder;
  74
  75     void MarkPhysRegRecentlyUsed(unsigned Reg) {
  76       assert(std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg) !=
  77              PhysRegsUseOrder.end() && "Register isn't used yet!");
  78       if (PhysRegsUseOrder.back() != Reg) {
  79         for (unsigned i = PhysRegsUseOrder.size(); ; --i)
  80           if (PhysRegsUseOrder[i-1] == Reg) {  // remove from middle
  81             PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
  82             PhysRegsUseOrder.push_back(Reg);  // Add it to the end of the list
  83             return;
  84           }
  85       }
  86     }
  87
  88   public:
  89
  90     RA(TargetMachine &tm)
  91       : TM(tm), RegInfo(tm.getRegisterInfo()), PhysRegClasses(RegInfo) {
  92       cleanupAfterFunction();
  93     }
  94
  95     bool runOnFunction(Function &Fn) {
  96       return runOnMachineFunction(MachineFunction::get(&Fn));
  97     }
  98
  99     virtual const char *getPassName() const {
 100       return "Local Register Allocator";
 101     }
 102
 103   private:
 104     /// runOnMachineFunction - Register allocate the whole function
 105     bool runOnMachineFunction(MachineFunction &Fn);
 106
 107     /// AllocateBasicBlock - Register allocate the specified basic block.
 108     void AllocateBasicBlock(MachineBasicBlock &MBB);
 109
 110     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
 111     /// in predecessor basic blocks.
 112     void EliminatePHINodes(MachineBasicBlock &MBB);
 113
 114     /// isAllocatableRegister - A register may be used by the program if it's
 115     /// not the stack or frame pointer.
 116     bool isAllocatableRegister(unsigned R) const {
 117       unsigned FP = RegInfo->getFramePointer(), SP = RegInfo->getStackPointer();
 118       // Don't allocate the Frame or Stack pointers
 119       if (R == FP || R == SP)
 120         return false;
 121
 122       // Check to see if this register aliases the stack or frame pointer...
 123       if (const unsigned *AliasSet = RegInfo->getAliasSet(R)) {
 124         for (unsigned i = 0; AliasSet[i]; ++i)
 125           if (AliasSet[i] == FP || AliasSet[i] == SP)
 126             return false;
 127       }
 128       return true;
 129     }
 130
 131     /// getStackSpaceFor - This returns the offset of the specified virtual
 132     /// register on the stack, allocating space if neccesary.
 133     unsigned getStackSpaceFor(unsigned VirtReg,
 134                               const TargetRegisterClass *regClass);
 135
 136     void cleanupAfterFunction() {
 137       VirtReg2OffsetMap.clear();
 138       NumBytesAllocated = 4;   // FIXME: This is X86 specific
 139     }
 140
 141
 142     /// spillVirtReg - This method spills the value specified by PhysReg into
 143     /// the virtual register slot specified by VirtReg.  It then updates the RA
 144     /// data structures to indicate the fact that PhysReg is now available.
 145     ///
 146     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 147                       unsigned VirtReg, unsigned PhysReg);
 148
 149     /// spillPhysReg - This method spills the specified physical register into
 150     /// the virtual register slot associated with it.
 151     //
 152     void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 153                       unsigned PhysReg) {
 154       assert(PhysRegsUsed.find(PhysReg) != PhysRegsUsed.end() &&
 155              "Physical register is not used: cannot spill it!");
 156       spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg);
 157     }
 158
 159     void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 160
 161
 162     /// getFreeReg - Find a physical register to hold the specified virtual
 163     /// register.  If all compatible physical registers are used, this method
 164     /// spills the last used virtual register to the stack, and uses that
 165     /// register.
 166     ///
 167     unsigned getFreeReg(MachineBasicBlock &MBB,
 168                         MachineBasicBlock::iterator &I,
 169                         unsigned virtualReg);
 170
 171     /// reloadVirtReg - This method loads the specified virtual register into a
 172     /// physical register, returning the physical register chosen.  This updates
 173     /// the regalloc data structures to reflect the fact that the virtual reg is
 174     /// now alive in a physical register, and the previous one isn't.
 175     ///
 176     unsigned reloadVirtReg(MachineBasicBlock &MBB,
 177                            MachineBasicBlock::iterator &I, unsigned VirtReg);
 178   };
 179
 180 }
 181
 182 /// getStackSpaceFor - This allocates space for the specified virtual
 183 /// register to be held on the stack.
 184 unsigned RA::getStackSpaceFor(unsigned VirtReg,
 185                               const TargetRegisterClass *RegClass) {
 186   // Find the location VirtReg would belong...
 187   std::map<unsigned, unsigned>::iterator I =
 188     VirtReg2OffsetMap.lower_bound(VirtReg);
 189
 190   if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
 191     return I->second;          // Already has space allocated?
 192
 193   unsigned RegSize = RegClass->getDataSize();
 194
 195   // Align NumBytesAllocated.  We should be using TargetData alignment stuff
 196   // to determine this, but we don't know the LLVM type associated with the
 197   // virtual register.  Instead, just align to a multiple of the size for now.
 198   NumBytesAllocated += RegSize-1;
 199   NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
 200
 201   // Assign the slot...
 202   VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
 203
 204   // Reserve the space!
 205   NumBytesAllocated += RegSize;
 206   return NumBytesAllocated-RegSize;
 207 }
 208
 209 /// spillVirtReg - This method spills the value specified by PhysReg into the
 210 /// virtual register slot specified by VirtReg.  It then updates the RA data
 211 /// structures to indicate the fact that PhysReg is now available.
 212 ///
 213 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 214                       unsigned VirtReg, unsigned PhysReg) {
 215   // If this is just a marker register, we don't need to spill it.
 216   if (VirtReg != 0) {
 217     const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 218     unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
 219
 220     // Add move instruction(s)
 221     I = RegInfo->storeReg2RegOffset(MBB, I, PhysReg, RegInfo->getFramePointer(),
 222                                     -stackOffset, RegClass->getDataSize());
 223     ++NumSpilled;   // Update statistics
 224     Virt2PhysRegMap.erase(VirtReg);   // VirtReg no longer available
 225   }
 226   PhysRegsUsed.erase(PhysReg);      // PhyReg no longer used
 227
 228   std::vector<unsigned>::iterator It =
 229     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 230   assert(It != PhysRegsUseOrder.end() &&
 231          "Spilled a physical register, but it was not in use list!");
 232   PhysRegsUseOrder.erase(It);
 233 }
 234
 235 /// getFreeReg - Find a physical register to hold the specified virtual
 236 /// register.  If all compatible physical registers are used, this method spills
 237 /// the last used virtual register to the stack, and uses that register.
 238 ///
 239 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 240                         unsigned VirtReg) {
 241   const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 242   unsigned PhysReg = 0;
 243
 244   for (TargetRegisterClass::iterator It = RegClass->begin(),E = RegClass->end();
 245        It != E; ++It) {
 246     unsigned R = *It;
 247     if (PhysRegsUsed.find(R) == PhysRegsUsed.end())   // Is reg unused?
 248       if (isAllocatableRegister(R)) {
 249         // Found an unused register!
 250         PhysReg = R;
 251         break;
 252       }
 253   }
 254
 255   // If we didn't find an unused register, scavange one now!
 256   if (PhysReg == 0) {
 257     unsigned i = 0;
 258     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 259     while (PhysRegClasses[PhysRegsUseOrder[i]] != RegClass) {
 260       ++i;
 261       assert(i != PhysRegsUseOrder.size() &&
 262              "Couldn't find a register of the appropriate class!");
 263     }
 264
 265     // At this point PhysRegsUseOrder[i] is the least recently used register of
 266     // compatible register class.  Spill it to memory and reap its remains.
 267     PhysReg = PhysRegsUseOrder[i];
 268     spillPhysReg(MBB, I, PhysReg);
 269   }
 270
 271   // If the selected register aliases any other registers, we must make sure to
 272   // spill them as well...
 273   if (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg))
 274     for (unsigned i = 0; AliasSet[i]; ++i)
 275       if (PhysRegsUsed.count(AliasSet[i]))     // Spill aliased register...
 276         spillPhysReg(MBB, I, AliasSet[i]);
 277
 278
 279   // Now that we know which register we need to assign this to, do it now!
 280   AssignVirtToPhysReg(VirtReg, PhysReg);
 281   return PhysReg;
 282 }
 283
 284 void RA::AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 285   assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
 286          "Phys reg already assigned!");
 287   // Update information to note the fact that this register was just used, and
 288   // it holds VirtReg.
 289   PhysRegsUsed[PhysReg] = VirtReg;
 290   Virt2PhysRegMap[VirtReg] = PhysReg;
 291   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
 292 }
 293
 294
 295 /// reloadVirtReg - This method loads the specified virtual register into a
 296 /// physical register, returning the physical register chosen.  This updates the
 297 /// regalloc data structures to reflect the fact that the virtual reg is now
 298 /// alive in a physical register, and the previous one isn't.
 299 ///
 300 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
 301                            MachineBasicBlock::iterator &I,
 302                            unsigned VirtReg) {
 303   std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
 304   if (It != Virt2PhysRegMap.end()) {
 305     MarkPhysRegRecentlyUsed(It->second);
 306     return It->second;               // Already have this value available!
 307   }
 308
 309   unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
 310
 311   const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 312   unsigned StackOffset = getStackSpaceFor(VirtReg, RegClass);
 313
 314   // Add move instruction(s)
 315   I = RegInfo->loadRegOffset2Reg(MBB, I, PhysReg, RegInfo->getFramePointer(),
 316                                  -StackOffset, RegClass->getDataSize());
 317   ++NumReloaded;    // Update statistics
 318   return PhysReg;
 319 }
 320
 321 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 322 /// predecessor basic blocks.
 323 ///
 324 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
 325   const MachineInstrInfo &MII = TM.getInstrInfo();
 326
 327   while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
 328     MachineInstr *MI = MBB.front();
 329     // Unlink the PHI node from the basic block... but don't delete the PHI yet
 330     MBB.erase(MBB.begin());
 331
 332     DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
 333     assert(MI->getOperand(0).isVirtualRegister() &&
 334            "PHI node doesn't write virt reg?");
 335
 336     unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
 337
 338     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 339       MachineOperand &opVal = MI->getOperand(i-1);
 340
 341       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 342       // source path the phi
 343       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
 344
 345       // Check to make sure we haven't already emitted the copy for this block.
 346       // This can happen because PHI nodes may have multiple entries for the
 347       // same basic block.  It doesn't matter which entry we use though, because
 348       // all incoming values are guaranteed to be the same for a particular bb.
 349       //
 350       // Note that this is N^2 in the number of phi node entries, but since the
 351       // # of entries is tiny, this is not a problem.
 352       //
 353       bool HaveNotEmitted = true;
 354       for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
 355         if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
 356           HaveNotEmitted = false;
 357           break;
 358         }
 359
 360       if (HaveNotEmitted) {
 361         MachineBasicBlock::iterator opI = opBlock.end();
 362         MachineInstr *opMI = *--opI;
 363
 364         // must backtrack over ALL the branches in the previous block
 365         while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
 366           opMI = *--opI;
 367
 368         // move back to the first branch instruction so new instructions
 369         // are inserted right in front of it and not in front of a non-branch
 370         if (!MII.isBranch(opMI->getOpcode()))
 371           ++opI;
 372
 373         unsigned dataSize = MF->getRegClass(virtualReg)->getDataSize();
 374
 375         // Retrieve the constant value from this op, move it to target
 376         // register of the phi
 377         if (opVal.isImmediate()) {
 378           opI = RegInfo->moveImm2Reg(opBlock, opI, virtualReg,
 379                                      (unsigned) opVal.getImmedValue(),
 380                                      dataSize);
 381         } else {
 382           opI = RegInfo->moveReg2Reg(opBlock, opI, virtualReg,
 383                                      opVal.getAllocatedRegNum(), dataSize);
 384         }
 385       }
 386     }
 387
 388     // really delete the PHI instruction now!
 389     delete MI;
 390   }
 391 }
 392
 393 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 394   // loop over each instruction
 395   MachineBasicBlock::iterator I = MBB.begin();
 396   for (; I != MBB.end(); ++I) {
 397     MachineInstr *MI = *I;
 398
 399     // Loop over all of the operands of the instruction, spilling registers that
 400     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 401     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 402       if (MI->getOperand(i).opIsDef() &&
 403           MI->getOperand(i).isPhysicalRegister()) {
 404         unsigned Reg  = MI->getOperand(i).getAllocatedRegNum();
 405         unsigned VMap = PhysRegsUsed[Reg];
 406         if (VMap) {  // Spill the value in this register...
 407           spillVirtReg(MBB, I, VMap, Reg);
 408           PhysRegsUsed[Reg] = 0;  // It's free now, and it's reserved
 409         }
 410         PhysRegsUseOrder.push_back(Reg);
 411       }
 412
 413     // FIXME: Loop over the implicit defs, spilling them, as above.
 414
 415
 416     // FIXME: Loop over the implicit uses, making sure that they are at the head
 417     // of the use order list, so they don't get reallocated.
 418
 419     // Loop over all of the operands again, getting the used operands into
 420     // registers.  This has the potiential to spill incoming values because we
 421     // are out of registers.
 422     //
 423     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 424       if (MI->getOperand(i).opIsUse() &&
 425           MI->getOperand(i).isVirtualRegister()) {
 426         unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
 427         unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
 428         MI->SetMachineOperandReg(i, PhysSrcReg);  // Assign the input register
 429       }
 430
 431     // Okay, we have allocated all of the source operands and spilled any values
 432     // that would be destroyed by defs of this instruction.  Loop over the
 433     // implicit defs and assign them to a register, spilling the incoming value
 434     // if we need to scavange a register.
 435
 436     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 437       if (MI->getOperand(i).opIsDef() &&
 438           !MI->getOperand(i).isPhysicalRegister()) {
 439         unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
 440         unsigned DestPhysReg;
 441
 442         if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 443           // must be same register number as the first operand
 444           // This maps a = b + c into b += c, and saves b into a's spot
 445           assert(MI->getOperand(1).isRegister()  &&
 446                  MI->getOperand(1).getAllocatedRegNum() &&
 447                  MI->getOperand(1).opIsUse() &&
 448                  "Two address instruction invalid!");
 449           DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
 450
 451           // Spill the incoming value, because we are about to change the
 452           // register contents.
 453           spillPhysReg(MBB, I, DestPhysReg);
 454           AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
 455         } else {
 456           DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
 457         }
 458         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
 459       }
 460   }
 461
 462   // Rewind the iterator to point to the first flow control instruction...
 463   const MachineInstrInfo &MII = TM.getInstrInfo();
 464   I = MBB.end();
 465   do {
 466     --I;
 467   } while ((MII.isReturn((*I)->getOpcode()) ||
 468             MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
 469
 470   if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
 471     ++I;
 472
 473   // Spill all physical registers holding virtual registers now.
 474   while (!PhysRegsUsed.empty())
 475     spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
 476                  PhysRegsUsed.begin()->first);
 477
 478   assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
 479   assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
 480 }
 481
 482 /// runOnMachineFunction - Register allocate the whole function
 483 ///
 484 bool RA::runOnMachineFunction(MachineFunction &Fn) {
 485   DEBUG(std::cerr << "Machine Function " << "\n");
 486   MF = &Fn;
 487
 488   // First pass: eliminate PHI instructions by inserting copies into predecessor
 489   // blocks.
 490   // FIXME: In this pass, count how many uses of each VReg exist!
 491   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 492        MBB != MBBe; ++MBB)
 493     EliminatePHINodes(*MBB);
 494
 495   // Loop over all of the basic blocks, eliminating virtual register references
 496   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 497        MBB != MBBe; ++MBB)
 498     AllocateBasicBlock(*MBB);
 499
 500   // Round stack allocation up to a nice alignment to keep the stack aligned
 501   // FIXME: This is X86 specific!  Move to frame manager
 502   NumBytesAllocated = (NumBytesAllocated + 3) & ~3;
 503
 504   // Add prologue to the function...
 505   RegInfo->emitPrologue(Fn, NumBytesAllocated);
 506
 507   const MachineInstrInfo &MII = TM.getInstrInfo();
 508
 509   // Add epilogue to restore the callee-save registers in each exiting block
 510   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 511        MBB != MBBe; ++MBB) {
 512     // If last instruction is a return instruction, add an epilogue
 513     if (MII.isReturn(MBB->back()->getOpcode()))
 514       RegInfo->emitEpilogue(*MBB, NumBytesAllocated);
 515   }
 516
 517   cleanupAfterFunction();
 518   return true;
 519 }
 520
 521 Pass *createLocalRegisterAllocator(TargetMachine &TM) {
 522   return new RA(TM);
 523 }