lib/CodeGen/RegAllocBigBlock.cpp

   1 //===- RegAllocBigBlock.cpp - A register allocator for large basic blocks -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This register allocator is derived from RegAllocLocal.cpp. Like it, this
  11 // allocator works on one basic block at a time, oblivious to others.
  12 // However, the algorithm used here is suited for long blocks of
  13 // instructions - registers are spilled by greedily choosing those holding
  14 // values that will not be needed for the longest amount of time. This works
  15 // particularly well for blocks with 10 or more times as many instructions
  16 // as machine registers, but can be used for general code.
  17 //
  18 //===----------------------------------------------------------------------===//
  19 //
  20 // TODO: - automagically invoke linearscan for (groups of) small BBs?
  21 //       - break ties when picking regs? (probably not worth it in a
  22 //         JIT context)
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #define DEBUG_TYPE "regalloc"
  27 #include "llvm/BasicBlock.h"
  28 #include "llvm/CodeGen/Passes.h"
  29 #include "llvm/CodeGen/MachineFunctionPass.h"
  30 #include "llvm/CodeGen/MachineInstr.h"
  31 #include "llvm/CodeGen/SSARegMap.h"
  32 #include "llvm/CodeGen/MachineFrameInfo.h"
  33 #include "llvm/CodeGen/LiveVariables.h"
  34 #include "llvm/CodeGen/RegAllocRegistry.h"
  35 #include "llvm/Target/TargetInstrInfo.h"
  36 #include "llvm/Target/TargetMachine.h"
  37 #include "llvm/Support/CommandLine.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/Compiler.h"
  40 #include "llvm/ADT/IndexedMap.h"
  41 #include "llvm/ADT/DenseMap.h"
  42 #include "llvm/ADT/SmallVector.h"
  43 #include "llvm/ADT/Statistic.h"
  44 #include <algorithm>
  45 using namespace llvm;
  46
  47 STATISTIC(NumStores, "Number of stores added");
  48 STATISTIC(NumLoads , "Number of loads added");
  49 STATISTIC(NumFolded, "Number of loads/stores folded into instructions");
  50
  51 namespace {
  52   static RegisterRegAlloc
  53     bigBlockRegAlloc("bigblock", "  Big-block register allocator",
  54                   createBigBlockRegisterAllocator);
  55
  56   struct VRegKeyInfo {
  57     static inline unsigned getEmptyKey() { return -1U; }
  58     static inline unsigned getTombstoneKey() { return -2U; }
  59     static unsigned getHashValue(const unsigned &Key) { return Key; }
  60   };
  61
  62   class VISIBILITY_HIDDEN RABigBlock : public MachineFunctionPass {
  63   public:
  64     static char ID;
  65     RABigBlock() : MachineFunctionPass((intptr_t)&ID) {}
  66   private:
  67     const TargetMachine *TM;
  68     MachineFunction *MF;
  69     const MRegisterInfo *RegInfo;
  70     LiveVariables *LV;
  71
  72     // InsnTimes - maps machine instructions to their "execute times"
  73     std::map<MachineInstr *, unsigned> InsnTimes;
  74
  75     // VRegReadTable - maps VRegs in a BB to the set of times they are read
  76     DenseMap<unsigned, SmallVector<unsigned, 2>*, VRegKeyInfo> VRegReadTable;
  77
  78     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  79     // values are spilled.
  80     std::map<unsigned, int> StackSlotForVirtReg;
  81
  82     // Virt2PhysRegMap - This map contains entries for each virtual register
  83     // that is currently available in a physical register.
  84     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
  85
  86     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
  87       return Virt2PhysRegMap[VirtReg];
  88     }
  89
  90     // PhysRegsUsed - This array is effectively a map, containing entries for
  91     // each physical register that currently has a value (ie, it is in
  92     // Virt2PhysRegMap).  The value mapped to is the virtual register
  93     // corresponding to the physical register (the inverse of the
  94     // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
  95     // because it is used by a future instruction, and to -2 if it is not
  96     // allocatable.  If the entry for a physical register is -1, then the
  97     // physical register is "not in the map".
  98     //
  99     std::vector<int> PhysRegsUsed;
 100
 101     // PhysRegsUseOrder - This contains a list of the physical registers that
 102     // currently have a virtual register value in them.  This list provides an
 103     // ordering of registers, imposing a reallocation order.  This list is only
 104     // used if all registers are allocated and we have to spill one, in which
 105     // case we spill the least recently used register.  Entries at the front of
 106     // the list are the least recently used registers, entries at the back are
 107     // the most recently used.
 108     //
 109     std::vector<unsigned> PhysRegsUseOrder;
 110
 111     // VirtRegModified - This bitset contains information about which virtual
 112     // registers need to be spilled back to memory when their registers are
 113     // scavenged.  If a virtual register has simply been rematerialized, there
 114     // is no reason to spill it to memory when we need the register back.
 115     //
 116     std::vector<bool> VirtRegModified;
 117
 118     void markVirtRegModified(unsigned Reg, bool Val = true) {
 119       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 120       Reg -= MRegisterInfo::FirstVirtualRegister;
 121       if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1);
 122       VirtRegModified[Reg] = Val;
 123     }
 124
 125     bool isVirtRegModified(unsigned Reg) const {
 126       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 127       assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
 128              && "Illegal virtual register!");
 129       return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister];
 130     }
 131
 132     void MarkPhysRegRecentlyUsed(unsigned Reg) {
 133       if (PhysRegsUseOrder.empty() ||
 134           PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
 135
 136       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
 137         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
 138           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
 139           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
 140           // Add it to the end of the list
 141           PhysRegsUseOrder.push_back(RegMatch);
 142           if (RegMatch == Reg)
 143             return;    // Found an exact match, exit early
 144         }
 145     }
 146
 147   public:
 148     virtual const char *getPassName() const {
 149       return "BigBlock Register Allocator";
 150     }
 151
 152     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 153       AU.addRequired<LiveVariables>();
 154       AU.addRequiredID(PHIEliminationID);
 155       AU.addRequiredID(TwoAddressInstructionPassID);
 156       MachineFunctionPass::getAnalysisUsage(AU);
 157     }
 158
 159   private:
 160     /// runOnMachineFunction - Register allocate the whole function
 161     bool runOnMachineFunction(MachineFunction &Fn);
 162
 163     /// AllocateBasicBlock - Register allocate the specified basic block.
 164     void AllocateBasicBlock(MachineBasicBlock &MBB);
 165
 166     /// FillVRegReadTable - Fill out the table of vreg read times given a BB
 167     void FillVRegReadTable(MachineBasicBlock &MBB);
 168
 169     /// areRegsEqual - This method returns true if the specified registers are
 170     /// related to each other.  To do this, it checks to see if they are equal
 171     /// or if the first register is in the alias set of the second register.
 172     ///
 173     bool areRegsEqual(unsigned R1, unsigned R2) const {
 174       if (R1 == R2) return true;
 175       for (const unsigned *AliasSet = RegInfo->getAliasSet(R2);
 176            *AliasSet; ++AliasSet) {
 177         if (*AliasSet == R1) return true;
 178       }
 179       return false;
 180     }
 181
 182     /// getStackSpaceFor - This returns the frame index of the specified virtual
 183     /// register on the stack, allocating space if necessary.
 184     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 185
 186     /// removePhysReg - This method marks the specified physical register as no
 187     /// longer being in use.
 188     ///
 189     void removePhysReg(unsigned PhysReg);
 190
 191     /// spillVirtReg - This method spills the value specified by PhysReg into
 192     /// the virtual register slot specified by VirtReg.  It then updates the RA
 193     /// data structures to indicate the fact that PhysReg is now available.
 194     ///
 195     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 196                       unsigned VirtReg, unsigned PhysReg);
 197
 198     /// spillPhysReg - This method spills the specified physical register into
 199     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 200     /// true, then the request is ignored if the physical register does not
 201     /// contain a virtual register.
 202     ///
 203     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 204                       unsigned PhysReg, bool OnlyVirtRegs = false);
 205
 206     /// assignVirtToPhysReg - This method updates local state so that we know
 207     /// that PhysReg is the proper container for VirtReg now.  The physical
 208     /// register must not be used for anything else when this is called.
 209     ///
 210     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 211
 212     /// liberatePhysReg - Make sure the specified physical register is available
 213     /// for use.  If there is currently a value in it, it is either moved out of
 214     /// the way or spilled to memory.
 215     ///
 216     void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 217                          unsigned PhysReg);
 218
 219     /// isPhysRegAvailable - Return true if the specified physical register is
 220     /// free and available for use.  This also includes checking to see if
 221     /// aliased registers are all free...
 222     ///
 223     bool isPhysRegAvailable(unsigned PhysReg) const;
 224
 225     /// getFreeReg - Look to see if there is a free register available in the
 226     /// specified register class.  If not, return 0.
 227     ///
 228     unsigned getFreeReg(const TargetRegisterClass *RC);
 229
 230     /// chooseReg - Pick a physical register to hold the specified
 231     /// virtual register by choosing the one which will be read furthest
 232     /// in the future.
 233     ///
 234     unsigned chooseReg(MachineBasicBlock &MBB, MachineInstr *MI,
 235                     unsigned VirtReg);
 236
 237     /// reloadVirtReg - This method transforms the specified specified virtual
 238     /// register use to refer to a physical register.  This method may do this
 239     /// in one of several ways: if the register is available in a physical
 240     /// register already, it uses that physical register.  If the value is not
 241     /// in a physical register, and if there are physical registers available,
 242     /// it loads it into a register.  If register pressure is high, and it is
 243     /// possible, it tries to fold the load of the virtual register into the
 244     /// instruction itself.  It avoids doing this if register pressure is low to
 245     /// improve the chance that subsequent instructions can use the reloaded
 246     /// value.  This method returns the modified instruction.
 247     ///
 248     MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 249                                 unsigned OpNum);
 250
 251   };
 252   char RABigBlock::ID = 0;
 253 }
 254
 255 /// getStackSpaceFor - This allocates space for the specified virtual register
 256 /// to be held on the stack.
 257 int RABigBlock::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 258   // Find the location Reg would belong...
 259   std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg);
 260
 261   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
 262     return I->second;          // Already has space allocated?
 263
 264   // Allocate a new stack object for this spill location...
 265   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
 266                                                        RC->getAlignment());
 267
 268   // Assign the slot...
 269   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
 270   return FrameIdx;
 271 }
 272
 273
 274 /// removePhysReg - This method marks the specified physical register as no
 275 /// longer being in use.
 276 ///
 277 void RABigBlock::removePhysReg(unsigned PhysReg) {
 278   PhysRegsUsed[PhysReg] = -1;      // PhyReg no longer used
 279
 280   std::vector<unsigned>::iterator It =
 281     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 282   if (It != PhysRegsUseOrder.end())
 283     PhysRegsUseOrder.erase(It);
 284 }
 285
 286
 287 /// spillVirtReg - This method spills the value specified by PhysReg into the
 288 /// virtual register slot specified by VirtReg.  It then updates the RA data
 289 /// structures to indicate the fact that PhysReg is now available.
 290 ///
 291 void RABigBlock::spillVirtReg(MachineBasicBlock &MBB,
 292                            MachineBasicBlock::iterator I,
 293                            unsigned VirtReg, unsigned PhysReg) {
 294   assert(VirtReg && "Spilling a physical register is illegal!"
 295          " Must not have appropriate kill for the register or use exists beyond"
 296          " the intended one.");
 297   DOUT << "  Spilling register " << RegInfo->getName(PhysReg)
 298        << " containing %reg" << VirtReg;
 299   if (!isVirtRegModified(VirtReg))
 300     DOUT << " which has not been modified, so no store necessary!";
 301
 302   // Otherwise, there is a virtual register corresponding to this physical
 303   // register.  We only need to spill it into its stack slot if it has been
 304   // modified.
 305   if (isVirtRegModified(VirtReg)) {
 306     const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 307     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 308     DOUT << " to stack slot #" << FrameIndex;
 309     RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC);
 310     ++NumStores;   // Update statistics
 311   }
 312
 313   getVirt2PhysRegMapSlot(VirtReg) = 0;   // VirtReg no longer available
 314
 315   DOUT << "\n";
 316   removePhysReg(PhysReg);
 317 }
 318
 319
 320 /// spillPhysReg - This method spills the specified physical register into the
 321 /// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
 322 /// then the request is ignored if the physical register does not contain a
 323 /// virtual register.
 324 ///
 325 void RABigBlock::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 326                            unsigned PhysReg, bool OnlyVirtRegs) {
 327   if (PhysRegsUsed[PhysReg] != -1) {            // Only spill it if it's used!
 328     assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!");
 329     if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs)
 330       spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg);
 331   } else {
 332     // If the selected register aliases any other registers, we must make
 333     // sure that one of the aliases isn't alive.
 334     for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 335          *AliasSet; ++AliasSet)
 336       if (PhysRegsUsed[*AliasSet] != -1 &&     // Spill aliased register.
 337           PhysRegsUsed[*AliasSet] != -2)       // If allocatable.
 338         if (PhysRegsUsed[*AliasSet] == 0) {
 339           // This must have been a dead def due to something like this:
 340           // %EAX :=
 341           //      := op %AL
 342           // No more use of %EAX, %AH, etc.
 343           // %EAX isn't dead upon definition, but %AH is. However %AH isn't
 344           // an operand of definition MI so it's not marked as such.
 345           DOUT << "  Register " << RegInfo->getName(*AliasSet)
 346                << " [%reg" << *AliasSet
 347                << "] is never used, removing it frame live list\n";
 348           removePhysReg(*AliasSet);
 349         } else
 350           spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet);
 351   }
 352 }
 353
 354
 355 /// assignVirtToPhysReg - This method updates local state so that we know
 356 /// that PhysReg is the proper container for VirtReg now.  The physical
 357 /// register must not be used for anything else when this is called.
 358 ///
 359 void RABigBlock::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 360   assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!");
 361   // Update information to note the fact that this register was just used, and
 362   // it holds VirtReg.
 363   PhysRegsUsed[PhysReg] = VirtReg;
 364   getVirt2PhysRegMapSlot(VirtReg) = PhysReg;
 365   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
 366 }
 367
 368
 369 /// isPhysRegAvailable - Return true if the specified physical register is free
 370 /// and available for use.  This also includes checking to see if aliased
 371 /// registers are all free...
 372 ///
 373 bool RABigBlock::isPhysRegAvailable(unsigned PhysReg) const {
 374   if (PhysRegsUsed[PhysReg] != -1) return false;
 375
 376   // If the selected register aliases any other allocated registers, it is
 377   // not free!
 378   for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 379        *AliasSet; ++AliasSet)
 380     if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use?
 381       return false;                    // Can't use this reg then.
 382   return true;
 383 }
 384
 385
 386 //////// FIX THIS:
 387 /// getFreeReg - Look to see if there is a free register available in the
 388 /// specified register class.  If not, return 0.
 389 ///
 390 unsigned RABigBlock::getFreeReg(const TargetRegisterClass *RC) {
 391   // Get iterators defining the range of registers that are valid to allocate in
 392   // this class, which also specifies the preferred allocation order.
 393   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 394   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 395
 396   for (; RI != RE; ++RI)
 397     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
 398       assert(*RI != 0 && "Cannot use register!");
 399       return *RI; // Found an unused register!
 400     }
 401   return 0;
 402 }
 403
 404
 405 /// liberatePhysReg - Make sure the specified physical register is available for
 406 /// use.  If there is currently a value in it, it is either moved out of the way
 407 /// or spilled to memory.
 408 ///
 409 void RABigBlock::liberatePhysReg(MachineBasicBlock &MBB,
 410                               MachineBasicBlock::iterator &I,
 411                               unsigned PhysReg) {
 412   spillPhysReg(MBB, I, PhysReg);
 413 }
 414
 415 /// chooseReg - Pick a physical register to hold the specified
 416 /// virtual register by choosing the one whose value will be read
 417 /// furthest in the future.
 418 ///
 419 unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I,
 420                          unsigned VirtReg) {
 421   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 422   // First check to see if we have a free register of the requested type...
 423   unsigned PhysReg = getFreeReg(RC);
 424
 425   // If we didn't find an unused register, find the one which will be
 426   // read at the most distant point in time.
 427   if (PhysReg == 0) {
 428     unsigned delay=0, longest_delay=0;
 429     SmallVector<unsigned, 2> *ReadTimes;
 430
 431     unsigned curTime = InsnTimes[I];
 432
 433     // for all physical regs in the RC,
 434     for(TargetRegisterClass::iterator pReg = RC->begin();
 435                                       pReg != RC->end();  ++pReg) {
 436       // how long until they're read?
 437       if(PhysRegsUsed[*pReg]>0) { // ignore non-allocatable regs
 438         ReadTimes = VRegReadTable[PhysRegsUsed[*pReg]];
 439         SmallVector<unsigned, 2>::iterator pt =
 440                                          std::lower_bound(ReadTimes->begin(),
 441                                                           ReadTimes->end(),
 442                                                           curTime);
 443         delay = *pt - curTime;
 444
 445         if(delay > longest_delay) {
 446           longest_delay = delay;
 447           PhysReg = *pReg;
 448         }
 449       }
 450     }
 451
 452     assert(PhysReg && "couldn't grab a register from the table?");
 453     // TODO: assert that RC->contains(PhysReg) / handle aliased registers
 454
 455     // since we needed to look in the table we need to spill this register.
 456     spillPhysReg(MBB, I, PhysReg);
 457   }
 458
 459   // assign the vreg to our chosen physical register
 460   assignVirtToPhysReg(VirtReg, PhysReg);
 461   return PhysReg; // and return it
 462 }
 463
 464
 465 /// reloadVirtReg - This method transforms an instruction with a virtual
 466 /// register use to one that references a physical register. It does this as
 467 /// follows:
 468 ///
 469 ///   1) If the register is already in a physical register, it uses it.
 470 ///   2) Otherwise, if there is a free physical register, it uses that.
 471 ///   3) Otherwise, it calls chooseReg() to get the physical register
 472 ///      holding the most distantly needed value, generating a spill in
 473 ///      the process.
 474 ///
 475 /// This method returns the modified instruction.
 476 MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 477                                      unsigned OpNum) {
 478   unsigned VirtReg = MI->getOperand(OpNum).getReg();
 479
 480   // If the virtual register is already available in a physical register,
 481   // just update the instruction and return.
 482   if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) {
 483     MI->getOperand(OpNum).setReg(PR);
 484     return MI;
 485   }
 486
 487   // Otherwise, if we have free physical registers available to hold the
 488   // value, use them.
 489   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 490   unsigned PhysReg = getFreeReg(RC);
 491   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 492
 493   if (PhysReg) {   // we have a free register, so use it.
 494     assignVirtToPhysReg(VirtReg, PhysReg);
 495   } else {  // no free registers available.
 496     // try to fold the spill into the instruction
 497     if(MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)) {
 498       ++NumFolded;
 499       // Since we changed the address of MI, make sure to update live variables
 500       // to know that the new instruction has the properties of the old one.
 501       LV->instructionChanged(MI, FMI);
 502       return MBB.insert(MBB.erase(MI), FMI);
 503     }
 504
 505     // determine which of the physical registers we'll kill off, since we
 506     // couldn't fold.
 507     PhysReg = chooseReg(MBB, MI, VirtReg);
 508   }
 509
 510   // this virtual register is now unmodified (since we just reloaded it)
 511   markVirtRegModified(VirtReg, false);
 512
 513   DOUT << "  Reloading %reg" << VirtReg << " into "
 514        << RegInfo->getName(PhysReg) << "\n";
 515
 516   // Add move instruction(s)
 517   RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC);
 518   ++NumLoads;    // Update statistics
 519
 520   MF->setPhysRegUsed(PhysReg);
 521   MI->getOperand(OpNum).setReg(PhysReg);  // Assign the input register
 522   return MI;
 523 }
 524
 525 /// Fill out the vreg read timetable. Since ReadTime increases
 526 /// monotonically, the individual readtime sets will be sorted
 527 /// in ascending order.
 528 void RABigBlock::FillVRegReadTable(MachineBasicBlock &MBB) {
 529   // loop over each instruction
 530   MachineBasicBlock::iterator MII;
 531   unsigned ReadTime;
 532
 533   for(ReadTime=0, MII = MBB.begin(); MII != MBB.end(); ++ReadTime, ++MII) {
 534     MachineInstr *MI = MII;
 535
 536     InsnTimes[MI] = ReadTime;
 537
 538     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 539       MachineOperand& MO = MI->getOperand(i);
 540       // look for vreg reads..
 541       if (MO.isRegister() && !MO.isDef() && MO.getReg() &&
 542           MRegisterInfo::isVirtualRegister(MO.getReg())) {
 543         // ..and add them to the read table.
 544         if(!VRegReadTable[MO.getReg()])
 545           VRegReadTable[MO.getReg()] = new SmallVector<unsigned, 2>;
 546
 547         VRegReadTable[MO.getReg()]->push_back(ReadTime);
 548       }
 549     }
 550
 551   }
 552
 553 }
 554
 555 void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) {
 556   // loop over each instruction
 557   MachineBasicBlock::iterator MII = MBB.begin();
 558   const TargetInstrInfo &TII = *TM->getInstrInfo();
 559
 560   DEBUG(const BasicBlock *LBB = MBB.getBasicBlock();
 561         if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName());
 562
 563   // If this is the first basic block in the machine function, add live-in
 564   // registers as active.
 565   if (&MBB == &*MF->begin()) {
 566     for (MachineFunction::livein_iterator I = MF->livein_begin(),
 567          E = MF->livein_end(); I != E; ++I) {
 568       unsigned Reg = I->first;
 569       MF->setPhysRegUsed(Reg);
 570       PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 571       PhysRegsUseOrder.push_back(Reg);
 572       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 573            *AliasSet; ++AliasSet) {
 574         if (PhysRegsUsed[*AliasSet] != -2) {
 575           PhysRegsUseOrder.push_back(*AliasSet);
 576           PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 577           MF->setPhysRegUsed(*AliasSet);
 578         }
 579       }
 580     }
 581   }
 582
 583   // Otherwise, sequentially allocate each instruction in the MBB.
 584   while (MII != MBB.end()) {
 585     MachineInstr *MI = MII++;
 586     const TargetInstrDescriptor &TID = TII.get(MI->getOpcode());
 587     DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI;
 588           DOUT << "  Regs have values: ";
 589           for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i)
 590             if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
 591                DOUT << "[" << RegInfo->getName(i)
 592                     << ",%reg" << PhysRegsUsed[i] << "] ";
 593           DOUT << "\n");
 594
 595     // Loop over the implicit uses, making sure that they are at the head of the
 596     // use order list, so they don't get reallocated.
 597     if (TID.ImplicitUses) {
 598       for (const unsigned *ImplicitUses = TID.ImplicitUses;
 599            *ImplicitUses; ++ImplicitUses)
 600         MarkPhysRegRecentlyUsed(*ImplicitUses);
 601     }
 602
 603     SmallVector<unsigned, 8> Kills;
 604     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 605       MachineOperand& MO = MI->getOperand(i);
 606       if (MO.isRegister() && MO.isKill())
 607         Kills.push_back(MO.getReg());
 608     }
 609
 610     // Get the used operands into registers.  This has the potential to spill
 611     // incoming values if we are out of registers.  Note that we completely
 612     // ignore physical register uses here.  We assume that if an explicit
 613     // physical register is referenced by the instruction, that it is guaranteed
 614     // to be live-in, or the input is badly hosed.
 615     //
 616     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 617       MachineOperand& MO = MI->getOperand(i);
 618       // here we are looking for only used operands (never def&use)
 619       if (MO.isRegister() && !MO.isDef() && MO.getReg() && !MO.isImplicit() &&
 620           MRegisterInfo::isVirtualRegister(MO.getReg()))
 621         MI = reloadVirtReg(MBB, MI, i);
 622     }
 623
 624     // If this instruction is the last user of this register, kill the
 625     // value, freeing the register being used, so it doesn't need to be
 626     // spilled to memory.
 627     //
 628     for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 629       unsigned VirtReg = Kills[i];
 630       unsigned PhysReg = VirtReg;
 631       if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 632         // If the virtual register was never materialized into a register, it
 633         // might not be in the map, but it won't hurt to zero it out anyway.
 634         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 635         PhysReg = PhysRegSlot;
 636         PhysRegSlot = 0;
 637       } else if (PhysRegsUsed[PhysReg] == -2) {
 638         // Unallocatable register dead, ignore.
 639         continue;
 640       }
 641
 642       if (PhysReg) {
 643         DOUT << "  Last use of " << RegInfo->getName(PhysReg)
 644              << "[%reg" << VirtReg <<"], removing it from live set\n";
 645         removePhysReg(PhysReg);
 646         for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 647              *AliasSet; ++AliasSet) {
 648           if (PhysRegsUsed[*AliasSet] != -2) {
 649             DOUT  << "  Last use of "
 650                   << RegInfo->getName(*AliasSet)
 651                   << "[%reg" << VirtReg <<"], removing it from live set\n";
 652             removePhysReg(*AliasSet);
 653           }
 654         }
 655       }
 656     }
 657
 658     // Loop over all of the operands of the instruction, spilling registers that
 659     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 660     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 661       MachineOperand& MO = MI->getOperand(i);
 662       if (MO.isRegister() && MO.isDef() && !MO.isImplicit() && MO.getReg() &&
 663           MRegisterInfo::isPhysicalRegister(MO.getReg())) {
 664         unsigned Reg = MO.getReg();
 665         if (PhysRegsUsed[Reg] == -2) continue;  // Something like ESP.
 666
 667         MF->setPhysRegUsed(Reg);
 668         spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg
 669         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 670         PhysRegsUseOrder.push_back(Reg);
 671         for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 672              *AliasSet; ++AliasSet) {
 673           if (PhysRegsUsed[*AliasSet] != -2) {
 674             PhysRegsUseOrder.push_back(*AliasSet);
 675             PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 676             MF->setPhysRegUsed(*AliasSet);
 677           }
 678         }
 679       }
 680     }
 681
 682     // Loop over the implicit defs, spilling them as well.
 683     if (TID.ImplicitDefs) {
 684       for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
 685            *ImplicitDefs; ++ImplicitDefs) {
 686         unsigned Reg = *ImplicitDefs;
 687         bool IsNonAllocatable = PhysRegsUsed[Reg] == -2;
 688         if (!IsNonAllocatable) {
 689           spillPhysReg(MBB, MI, Reg, true);
 690           PhysRegsUseOrder.push_back(Reg);
 691           PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 692         }
 693         MF->setPhysRegUsed(Reg);
 694
 695         for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 696              *AliasSet; ++AliasSet) {
 697           if (PhysRegsUsed[*AliasSet] != -2) {
 698             if (!IsNonAllocatable) {
 699               PhysRegsUseOrder.push_back(*AliasSet);
 700               PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 701             }
 702             MF->setPhysRegUsed(*AliasSet);
 703           }
 704         }
 705       }
 706     }
 707
 708     SmallVector<unsigned, 8> DeadDefs;
 709     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 710       MachineOperand& MO = MI->getOperand(i);
 711       if (MO.isRegister() && MO.isDead())
 712         DeadDefs.push_back(MO.getReg());
 713     }
 714
 715     // Okay, we have allocated all of the source operands and spilled any values
 716     // that would be destroyed by defs of this instruction.  Loop over the
 717     // explicit defs and assign them to a register, spilling incoming values if
 718     // we need to scavenge a register.
 719     //
 720     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 721       MachineOperand& MO = MI->getOperand(i);
 722       if (MO.isRegister() && MO.isDef() && MO.getReg() &&
 723           MRegisterInfo::isVirtualRegister(MO.getReg())) {
 724         unsigned DestVirtReg = MO.getReg();
 725         unsigned DestPhysReg;
 726
 727         // If DestVirtReg already has a value, use it.
 728         if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg)))
 729           DestPhysReg = chooseReg(MBB, MI, DestVirtReg);
 730         MF->setPhysRegUsed(DestPhysReg);
 731         markVirtRegModified(DestVirtReg);
 732         MI->getOperand(i).setReg(DestPhysReg);  // Assign the output register
 733       }
 734     }
 735
 736     // If this instruction defines any registers that are immediately dead,
 737     // kill them now.
 738     //
 739     for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) {
 740       unsigned VirtReg = DeadDefs[i];
 741       unsigned PhysReg = VirtReg;
 742       if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 743         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 744         PhysReg = PhysRegSlot;
 745         assert(PhysReg != 0);
 746         PhysRegSlot = 0;
 747       } else if (PhysRegsUsed[PhysReg] == -2) {
 748         // Unallocatable register dead, ignore.
 749         continue;
 750       }
 751
 752       if (PhysReg) {
 753         DOUT  << "  Register " << RegInfo->getName(PhysReg)
 754               << " [%reg" << VirtReg
 755               << "] is never used, removing it frame live list\n";
 756         removePhysReg(PhysReg);
 757         for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 758              *AliasSet; ++AliasSet) {
 759           if (PhysRegsUsed[*AliasSet] != -2) {
 760             DOUT  << "  Register " << RegInfo->getName(*AliasSet)
 761                   << " [%reg" << *AliasSet
 762                   << "] is never used, removing it frame live list\n";
 763             removePhysReg(*AliasSet);
 764           }
 765         }
 766       }
 767     }
 768
 769     // Finally, if this is a noop copy instruction, zap it.
 770     unsigned SrcReg, DstReg;
 771     if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) {
 772       LV->removeVirtualRegistersKilled(MI);
 773       LV->removeVirtualRegistersDead(MI);
 774       MBB.erase(MI);
 775     }
 776   }
 777
 778   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
 779
 780   // Spill all physical registers holding virtual registers now.
 781   for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i)
 782     if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
 783       if (unsigned VirtReg = PhysRegsUsed[i])
 784         spillVirtReg(MBB, MI, VirtReg, i);
 785       else
 786         removePhysReg(i);
 787
 788 #if 0
 789   // This checking code is very expensive.
 790   bool AllOk = true;
 791   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 792            e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i)
 793     if (unsigned PR = Virt2PhysRegMap[i]) {
 794       cerr << "Register still mapped: " << i << " -> " << PR << "\n";
 795       AllOk = false;
 796     }
 797   assert(AllOk && "Virtual registers still in phys regs?");
 798 #endif
 799
 800   // Clear any physical register which appear live at the end of the basic
 801   // block, but which do not hold any virtual registers.  e.g., the stack
 802   // pointer.
 803   PhysRegsUseOrder.clear();
 804 }
 805
 806 /// runOnMachineFunction - Register allocate the whole function
 807 ///
 808 bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) {
 809   DOUT << "Machine Function " << "\n";
 810   MF = &Fn;
 811   TM = &Fn.getTarget();
 812   RegInfo = TM->getRegisterInfo();
 813   LV = &getAnalysis<LiveVariables>();
 814
 815   PhysRegsUsed.assign(RegInfo->getNumRegs(), -1);
 816
 817   // At various places we want to efficiently check to see whether a register
 818   // is allocatable.  To handle this, we mark all unallocatable registers as
 819   // being pinned down, permanently.
 820   {
 821     BitVector Allocable = RegInfo->getAllocatableSet(Fn);
 822     for (unsigned i = 0, e = Allocable.size(); i != e; ++i)
 823       if (!Allocable[i])
 824         PhysRegsUsed[i] = -2;  // Mark the reg unallocable.
 825   }
 826
 827   // initialize the virtual->physical register map to have a 'null'
 828   // mapping for all virtual registers
 829   Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg());
 830
 831   // Loop over all of the basic blocks, eliminating virtual register references
 832   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 833        MBB != MBBe; ++MBB) {
 834     // fill out the read timetable
 835     FillVRegReadTable(*MBB);
 836     // use it to allocate the BB
 837     AllocateBasicBlock(*MBB);
 838     // clear it
 839     VRegReadTable.clear();
 840   }
 841
 842   StackSlotForVirtReg.clear();
 843   PhysRegsUsed.clear();
 844   VirtRegModified.clear();
 845   Virt2PhysRegMap.clear();
 846   return true;
 847 }
 848
 849 FunctionPass *llvm::createBigBlockRegisterAllocator() {
 850   return new RABigBlock();
 851 }
 852