lib/CodeGen/RegAllocLinearScan.cpp

   1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
   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 file implements a linear scan register allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #define DEBUG_TYPE "regalloc"
  14 #include "llvm/Function.h"
  15 #include "llvm/CodeGen/LiveIntervals.h"
  16 #include "llvm/CodeGen/LiveVariables.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/CodeGen/Passes.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/Target/MRegisterInfo.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Support/CFG.h"
  26 #include "Support/Debug.h"
  27 #include "Support/DepthFirstIterator.h"
  28 #include "Support/Statistic.h"
  29 #include "Support/STLExtras.h"
  30 using namespace llvm;
  31
  32 namespace {
  33     Statistic<> numSpilled ("ra-linearscan", "Number of registers spilled");
  34     Statistic<> numReloaded("ra-linearscan", "Number of registers reloaded");
  35     Statistic<> numPeep    ("ra-linearscan",
  36                             "Number of identity moves eliminated");
  37
  38     class RA : public MachineFunctionPass {
  39     private:
  40         MachineFunction* mf_;
  41         const TargetMachine* tm_;
  42         const MRegisterInfo* mri_;
  43         LiveIntervals* li_;
  44         MachineFunction::iterator currentMbb_;
  45         MachineBasicBlock::iterator currentInstr_;
  46         typedef std::vector<const LiveIntervals::Interval*> IntervalPtrs;
  47         IntervalPtrs unhandled_, fixed_, active_, inactive_;
  48
  49         typedef std::vector<unsigned> Regs;
  50         Regs tempUseOperands_;
  51         Regs tempDefOperands_;
  52
  53         typedef std::vector<bool> RegMask;
  54         RegMask reserved_;
  55
  56         unsigned regUse_[MRegisterInfo::FirstVirtualRegister];
  57         unsigned regUseBackup_[MRegisterInfo::FirstVirtualRegister];
  58
  59         typedef std::map<unsigned, unsigned> Virt2PhysMap;
  60         Virt2PhysMap v2pMap_;
  61
  62         typedef std::map<unsigned, int> Virt2StackSlotMap;
  63         Virt2StackSlotMap v2ssMap_;
  64
  65         int instrAdded_;
  66
  67     public:
  68         virtual const char* getPassName() const {
  69             return "Linear Scan Register Allocator";
  70         }
  71
  72         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  73             AU.addRequired<LiveVariables>();
  74             AU.addRequired<LiveIntervals>();
  75             MachineFunctionPass::getAnalysisUsage(AU);
  76         }
  77
  78     private:
  79         /// runOnMachineFunction - register allocate the whole function
  80         bool runOnMachineFunction(MachineFunction&);
  81
  82         /// initIntervalSets - initializa the four interval sets:
  83         /// unhandled, fixed, active and inactive
  84         void initIntervalSets(const LiveIntervals::Intervals& li);
  85
  86         /// processActiveIntervals - expire old intervals and move
  87         /// non-overlapping ones to the incative list
  88         void processActiveIntervals(IntervalPtrs::value_type cur);
  89
  90         /// processInactiveIntervals - expire old intervals and move
  91         /// overlapping ones to the active list
  92         void processInactiveIntervals(IntervalPtrs::value_type cur);
  93
  94         /// assignStackSlotAtInterval - choose and spill
  95         /// interval. Currently we spill the interval with the last
  96         /// end point in the active and inactive lists and the current
  97         /// interval
  98         void assignStackSlotAtInterval(IntervalPtrs::value_type cur);
  99
 100         ///
 101         /// register handling helpers
 102         ///
 103
 104         /// getFreePhysReg - return a free physical register for this
 105         /// virtual register interval if we have one, otherwise return
 106         /// 0
 107         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 108
 109         /// physRegAvailable - returns true if the specifed physical
 110         /// register is available
 111         bool physRegAvailable(unsigned physReg);
 112
 113         /// tempPhysRegAvailable - returns true if the specifed
 114         /// temporary physical register is available
 115         bool tempPhysRegAvailable(unsigned physReg);
 116
 117         /// getFreeTempPhysReg - return a free temprorary physical
 118         /// register for this virtual register if we have one (should
 119         /// never return 0)
 120         unsigned getFreeTempPhysReg(unsigned virtReg);
 121
 122         /// assignVirt2PhysReg - assigns the free physical register to
 123         /// the virtual register passed as arguments
 124         void assignVirt2PhysReg(unsigned virtReg, unsigned physReg);
 125
 126         /// clearVirtReg - free the physical register associated with this
 127         /// virtual register and disassociate virtual->physical and
 128         /// physical->virtual mappings
 129         void clearVirtReg(unsigned virtReg);
 130
 131         /// assignVirt2StackSlot - assigns this virtual register to a
 132         /// stack slot
 133         void assignVirt2StackSlot(unsigned virtReg);
 134
 135         /// getStackSlot - returns the offset of the specified
 136         /// register on the stack
 137         int getStackSlot(unsigned virtReg);
 138
 139         /// spillVirtReg - spills the virtual register
 140         void spillVirtReg(unsigned virtReg);
 141
 142         /// loadPhysReg - loads to the physical register the value of
 143         /// the virtual register specifed. Virtual register must have
 144         /// an assigned stack slot
 145         void loadVirt2PhysReg(unsigned virtReg, unsigned physReg);
 146
 147         void markPhysRegFree(unsigned physReg);
 148         void markPhysRegNotFree(unsigned physReg);
 149
 150         void backupRegUse() {
 151             memcpy(regUseBackup_, regUse_, sizeof(regUseBackup_));
 152         }
 153
 154         void restoreRegUse() {
 155             memcpy(regUse_, regUseBackup_, sizeof(regUseBackup_));
 156         }
 157
 158         void printVirtRegAssignment() const {
 159             std::cerr << "register assignment:\n";
 160             for (Virt2PhysMap::const_iterator
 161                      i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) {
 162                 assert(i->second != 0);
 163                 std::cerr << '[' << i->first << ','
 164                           << mri_->getName(i->second) << "]\n";
 165             }
 166             for (Virt2StackSlotMap::const_iterator
 167                      i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) {
 168                 std::cerr << '[' << i->first << ",ss#" << i->second << "]\n";
 169             }
 170             std::cerr << '\n';
 171         }
 172
 173         void printIntervals(const char* const str,
 174                             RA::IntervalPtrs::const_iterator i,
 175                             RA::IntervalPtrs::const_iterator e) const {
 176             if (str) std::cerr << str << " intervals:\n";
 177             for (; i != e; ++i) {
 178                 std::cerr << "\t\t" << **i << " -> ";
 179                 unsigned reg = (*i)->reg;
 180                 if (reg >= MRegisterInfo::FirstVirtualRegister) {
 181                     Virt2PhysMap::const_iterator it = v2pMap_.find(reg);
 182                     reg = (it == v2pMap_.end() ? 0 : it->second);
 183                 }
 184                 std::cerr << mri_->getName(reg) << '\n';
 185             }
 186         }
 187
 188         void printFreeRegs(const char* const str,
 189                            const TargetRegisterClass* rc) const {
 190             if (str) std::cerr << str << ':';
 191             for (TargetRegisterClass::iterator i =
 192                      rc->allocation_order_begin(*mf_);
 193                  i != rc->allocation_order_end(*mf_); ++i) {
 194                 unsigned reg = *i;
 195                 if (!regUse_[reg]) {
 196                     std::cerr << ' ' << mri_->getName(reg);
 197                     if (reserved_[reg]) std::cerr << "*";
 198                 }
 199             }
 200             std::cerr << '\n';
 201         }
 202     };
 203 }
 204
 205 bool RA::runOnMachineFunction(MachineFunction &fn) {
 206     mf_ = &fn;
 207     tm_ = &fn.getTarget();
 208     mri_ = tm_->getRegisterInfo();
 209     li_ = &getAnalysis<LiveIntervals>();
 210     initIntervalSets(li_->getIntervals());
 211
 212     v2pMap_.clear();
 213     v2ssMap_.clear();
 214     memset(regUse_, 0, sizeof(regUse_));
 215     memset(regUseBackup_, 0, sizeof(regUseBackup_));
 216
 217     // FIXME: this will work only for the X86 backend. I need to
 218     // device an algorthm to select the minimal (considering register
 219     // aliasing) number of temp registers to reserve so that we have 2
 220     // registers for each register class available.
 221
 222     // reserve R8:   CH,  CL
 223     //         R16:  CX,  DI,
 224     //         R32: ECX, EDI,
 225     //         RFP: FP5, FP6
 226     reserved_.assign(MRegisterInfo::FirstVirtualRegister, false);
 227     reserved_[ 8] = true; /*  CH */
 228     reserved_[ 9] = true; /*  CL */
 229     reserved_[10] = true; /*  CX */
 230     reserved_[12] = true; /*  DI */
 231     reserved_[18] = true; /* ECX */
 232     reserved_[19] = true; /* EDI */
 233     reserved_[28] = true; /* FP5 */
 234     reserved_[29] = true; /* FP6 */
 235
 236     // linear scan algorithm
 237     DEBUG(std::cerr << "Machine Function\n");
 238
 239     DEBUG(printIntervals("\tunhandled", unhandled_.begin(), unhandled_.end()));
 240     DEBUG(printIntervals("\tfixed", fixed_.begin(), fixed_.end()));
 241     DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 242     DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));
 243
 244     while (!unhandled_.empty() || !fixed_.empty()) {
 245         // pick the interval with the earliest start point
 246         IntervalPtrs::value_type cur;
 247         if (fixed_.empty()) {
 248             cur = unhandled_.front();
 249             unhandled_.erase(unhandled_.begin());
 250         }
 251         else if (unhandled_.empty()) {
 252             cur = fixed_.front();
 253             fixed_.erase(fixed_.begin());
 254         }
 255         else if (unhandled_.front()->start() < fixed_.front()->start()) {
 256             cur = unhandled_.front();
 257             unhandled_.erase(unhandled_.begin());
 258         }
 259         else {
 260             cur = fixed_.front();
 261             fixed_.erase(fixed_.begin());
 262         }
 263
 264         DEBUG(std::cerr << *cur << '\n');
 265
 266         processActiveIntervals(cur);
 267         processInactiveIntervals(cur);
 268
 269         // if this register is fixed we are done
 270         if (cur->reg < MRegisterInfo::FirstVirtualRegister) {
 271             markPhysRegNotFree(cur->reg);
 272             active_.push_back(cur);
 273         }
 274         // otherwise we are allocating a virtual register. try to find
 275         // a free physical register or spill an interval in order to
 276         // assign it one (we could spill the current though).
 277         else {
 278             backupRegUse();
 279
 280             // for every interval in inactive we overlap with, mark the
 281             // register as not free
 282             for (IntervalPtrs::const_iterator i = inactive_.begin(),
 283                      e = inactive_.end(); i != e; ++i) {
 284                 unsigned reg = (*i)->reg;
 285                 if (reg >= MRegisterInfo::FirstVirtualRegister)
 286                     reg = v2pMap_[reg];
 287
 288                 if (cur->overlaps(**i)) {
 289                     markPhysRegNotFree(reg);
 290                 }
 291             }
 292
 293             // for every interval in fixed we overlap with,
 294             // mark the register as not free
 295             for (IntervalPtrs::const_iterator i = fixed_.begin(),
 296                      e = fixed_.end(); i != e; ++i) {
 297                 assert((*i)->reg < MRegisterInfo::FirstVirtualRegister &&
 298                        "virtual register interval in fixed set?");
 299                 if (cur->overlaps(**i))
 300                     markPhysRegNotFree((*i)->reg);
 301             }
 302
 303             DEBUG(std::cerr << "\tallocating current interval:\n");
 304
 305             unsigned physReg = getFreePhysReg(cur);
 306             if (!physReg) {
 307                 assignStackSlotAtInterval(cur);
 308             }
 309             else {
 310                 restoreRegUse();
 311                 assignVirt2PhysReg(cur->reg, physReg);
 312                 active_.push_back(cur);
 313             }
 314         }
 315
 316         DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 317         DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));    }
 318
 319     // expire any remaining active intervals
 320     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 321         unsigned reg = (*i)->reg;
 322         DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 323         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 324             reg = v2pMap_[reg];
 325         }
 326         markPhysRegFree(reg);
 327     }
 328     active_.clear();
 329     inactive_.clear();
 330
 331     typedef LiveIntervals::Reg2RegMap Reg2RegMap;
 332     const Reg2RegMap& r2rMap = li_->getJoinedRegMap();
 333
 334     DEBUG(printVirtRegAssignment());
 335     DEBUG(std::cerr << "Performing coalescing on joined intervals\n");
 336     // perform coalescing if we were passed joined intervals
 337     for(Reg2RegMap::const_iterator i = r2rMap.begin(), e = r2rMap.end();
 338         i != e; ++i) {
 339         unsigned reg = i->first;
 340         unsigned rep = li_->rep(reg);
 341
 342         assert((rep < MRegisterInfo::FirstVirtualRegister ||
 343                 v2pMap_.find(rep) != v2pMap_.end() ||
 344                 v2ssMap_.find(rep) != v2ssMap_.end()) &&
 345                "representative register is not allocated!");
 346
 347         assert(reg >= MRegisterInfo::FirstVirtualRegister &&
 348                v2pMap_.find(reg) == v2pMap_.end() &&
 349                v2ssMap_.find(reg) == v2ssMap_.end() &&
 350                "coalesced register is already allocated!");
 351
 352         if (rep < MRegisterInfo::FirstVirtualRegister) {
 353             v2pMap_.insert(std::make_pair(reg, rep));
 354         }
 355         else {
 356             Virt2PhysMap::const_iterator pr = v2pMap_.find(rep);
 357             if (pr != v2pMap_.end()) {
 358                 v2pMap_.insert(std::make_pair(reg, pr->second));
 359             }
 360             else {
 361                 Virt2StackSlotMap::const_iterator ss = v2ssMap_.find(rep);
 362                 assert(ss != v2ssMap_.end());
 363                 v2ssMap_.insert(std::make_pair(reg, ss->second));
 364             }
 365         }
 366     }
 367
 368     DEBUG(printVirtRegAssignment());
 369     DEBUG(std::cerr << "finished register allocation\n");
 370
 371     const TargetInstrInfo& tii = tm_->getInstrInfo();
 372
 373     DEBUG(std::cerr << "Rewrite machine code:\n");
 374     for (currentMbb_ = mf_->begin(); currentMbb_ != mf_->end(); ++currentMbb_) {
 375         instrAdded_ = 0;
 376
 377         for (currentInstr_ = currentMbb_->begin();
 378              currentInstr_ != currentMbb_->end(); ) {
 379
 380             DEBUG(std::cerr << "\tinstruction: ";
 381                   (*currentInstr_)->print(std::cerr, *tm_););
 382
 383             // use our current mapping and actually replace and
 384             // virtual register with its allocated physical registers
 385             DEBUG(std::cerr << "\t\treplacing virtual registers with mapped "
 386                   "physical registers:\n");
 387             for (unsigned i = 0, e = (*currentInstr_)->getNumOperands();
 388                  i != e; ++i) {
 389                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 390                 if (op.isVirtualRegister()) {
 391                     unsigned virtReg = op.getAllocatedRegNum();
 392                     Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg);
 393                     if (it != v2pMap_.end()) {
 394                         DEBUG(std::cerr << "\t\t\t%reg" << it->second
 395                               << " -> " << mri_->getName(it->second) << '\n');
 396                         (*currentInstr_)->SetMachineOperandReg(i, it->second);
 397                     }
 398                 }
 399             }
 400
 401             unsigned srcReg, dstReg;
 402             if (tii.isMoveInstr(**currentInstr_, srcReg, dstReg) &&
 403                 ((srcReg < MRegisterInfo::FirstVirtualRegister &&
 404                   dstReg < MRegisterInfo::FirstVirtualRegister &&
 405                   srcReg == dstReg) ||
 406                  (srcReg >= MRegisterInfo::FirstVirtualRegister &&
 407                   dstReg >= MRegisterInfo::FirstVirtualRegister &&
 408                   v2ssMap_[srcReg] == v2ssMap_[dstReg]))) {
 409                 delete *currentInstr_;
 410                 currentInstr_ = currentMbb_->erase(currentInstr_);
 411                 ++numPeep;
 412                 DEBUG(std::cerr << "\t\tdeleting instruction\n");
 413                 continue;
 414             }
 415
 416             DEBUG(std::cerr << "\t\tloading temporarily used operands to "
 417                   "registers:\n");
 418             for (unsigned i = 0, e = (*currentInstr_)->getNumOperands();
 419                  i != e; ++i) {
 420                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 421                 if (op.isVirtualRegister() && op.isUse() && !op.isDef()) {
 422                     unsigned virtReg = op.getAllocatedRegNum();
 423                     unsigned physReg = 0;
 424                     Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg);
 425                     if (it != v2pMap_.end()) {
 426                         physReg = it->second;
 427                     }
 428                     else {
 429                         physReg = getFreeTempPhysReg(virtReg);
 430                         loadVirt2PhysReg(virtReg, physReg);
 431                         tempUseOperands_.push_back(virtReg);
 432                     }
 433                     (*currentInstr_)->SetMachineOperandReg(i, physReg);
 434                 }
 435             }
 436
 437             DEBUG(std::cerr << "\t\tclearing temporarily used operands:\n");
 438             for (unsigned i = 0, e = tempUseOperands_.size(); i != e; ++i) {
 439                 clearVirtReg(tempUseOperands_[i]);
 440             }
 441             tempUseOperands_.clear();
 442
 443             DEBUG(std::cerr << "\t\tassigning temporarily defined operands to "
 444                   "registers:\n");
 445             for (unsigned i = 0, e = (*currentInstr_)->getNumOperands();
 446                  i != e; ++i) {
 447                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 448                 if (op.isVirtualRegister() && op.isDef()) {
 449                     unsigned virtReg = op.getAllocatedRegNum();
 450                     unsigned physReg = 0;
 451                     Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg);
 452                     if (it != v2pMap_.end()) {
 453                         physReg = it->second;
 454                     }
 455                     else {
 456                         physReg = getFreeTempPhysReg(virtReg);
 457                     }
 458                     if (op.isUse()) { // def and use
 459                         loadVirt2PhysReg(virtReg, physReg);
 460                     }
 461                     else {
 462                         assignVirt2PhysReg(virtReg, physReg);
 463                     }
 464                     tempDefOperands_.push_back(virtReg);
 465                     (*currentInstr_)->SetMachineOperandReg(i, physReg);
 466                 }
 467             }
 468
 469             DEBUG(std::cerr << "\t\tspilling temporarily defined operands "
 470                   "of this instruction:\n");
 471             ++currentInstr_; // we want to insert after this instruction
 472             for (unsigned i = 0, e = tempDefOperands_.size(); i != e; ++i) {
 473                 spillVirtReg(tempDefOperands_[i]);
 474             }
 475             --currentInstr_; // restore currentInstr_ iterator
 476             tempDefOperands_.clear();
 477             ++currentInstr_;
 478         }
 479     }
 480
 481     return true;
 482 }
 483
 484 void RA::initIntervalSets(const LiveIntervals::Intervals& li)
 485 {
 486     assert(unhandled_.empty() && fixed_.empty() &&
 487            active_.empty() && inactive_.empty() &&
 488            "interval sets should be empty on initialization");
 489
 490     for (LiveIntervals::Intervals::const_iterator i = li.begin(), e = li.end();
 491          i != e; ++i) {
 492         if (i->reg < MRegisterInfo::FirstVirtualRegister)
 493             fixed_.push_back(&*i);
 494         else
 495             unhandled_.push_back(&*i);
 496     }
 497 }
 498
 499 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 500 {
 501     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 502     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 503         unsigned reg = (*i)->reg;
 504         // remove expired intervals
 505         if ((*i)->expiredAt(cur->start())) {
 506             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 507             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 508                 reg = v2pMap_[reg];
 509             }
 510             markPhysRegFree(reg);
 511             // remove from active
 512             i = active_.erase(i);
 513         }
 514         // move inactive intervals to inactive list
 515         else if (!(*i)->liveAt(cur->start())) {
 516             DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n");
 517             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 518                 reg = v2pMap_[reg];
 519             }
 520             markPhysRegFree(reg);
 521             // add to inactive
 522             inactive_.push_back(*i);
 523             // remove from active
 524             i = active_.erase(i);
 525         }
 526         else {
 527             ++i;
 528         }
 529     }
 530 }
 531
 532 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 533 {
 534     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 535     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 536         unsigned reg = (*i)->reg;
 537
 538         // remove expired intervals
 539         if ((*i)->expiredAt(cur->start())) {
 540             DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n");
 541             // remove from inactive
 542             i = inactive_.erase(i);
 543         }
 544         // move re-activated intervals in active list
 545         else if ((*i)->liveAt(cur->start())) {
 546             DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n");
 547             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 548                 reg = v2pMap_[reg];
 549             }
 550             markPhysRegNotFree(reg);
 551             // add to active
 552             active_.push_back(*i);
 553             // remove from inactive
 554             i = inactive_.erase(i);
 555         }
 556         else {
 557             ++i;
 558         }
 559     }
 560 }
 561
 562 namespace {
 563     template <typename T>
 564     void updateWeight(T rw[], int reg, T w)
 565     {
 566         if (rw[reg] == std::numeric_limits<T>::max() ||
 567             w == std::numeric_limits<T>::max())
 568             rw[reg] = std::numeric_limits<T>::max();
 569         else
 570             rw[reg] += w;
 571     }
 572 }
 573
 574 void RA::assignStackSlotAtInterval(IntervalPtrs::value_type cur)
 575 {
 576     DEBUG(std::cerr << "\t\tassigning stack slot at interval "
 577           << *cur << ":\n");
 578
 579     // set all weights to zero
 580     float regWeight[MRegisterInfo::FirstVirtualRegister];
 581     for (unsigned i = 0; i < MRegisterInfo::FirstVirtualRegister; ++i)
 582         regWeight[i] = 0.0F;
 583
 584     // for each interval in active
 585     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 586          i != e; ++i) {
 587         unsigned reg = (*i)->reg;
 588         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 589             reg = v2pMap_[reg];
 590         }
 591         updateWeight(regWeight, reg, (*i)->weight);
 592         for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 593             updateWeight(regWeight, *as, (*i)->weight);
 594     }
 595
 596     // for each interval in inactive that overlaps
 597     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 598              e = inactive_.end(); i != e; ++i) {
 599         if (!cur->overlaps(**i))
 600             continue;
 601
 602         unsigned reg = (*i)->reg;
 603         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 604             reg = v2pMap_[reg];
 605         }
 606         updateWeight(regWeight, reg, (*i)->weight);
 607         for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 608             updateWeight(regWeight, *as, (*i)->weight);
 609     }
 610
 611     // for each fixed interval that overlaps
 612     for (IntervalPtrs::const_iterator i = fixed_.begin(), e = fixed_.end();
 613          i != e; ++i) {
 614         if (!cur->overlaps(**i))
 615             continue;
 616
 617         assert((*i)->reg < MRegisterInfo::FirstVirtualRegister &&
 618                "virtual register interval in fixed set?");
 619         updateWeight(regWeight, (*i)->reg, (*i)->weight);
 620         for (const unsigned* as = mri_->getAliasSet((*i)->reg); *as; ++as)
 621             updateWeight(regWeight, *as, (*i)->weight);
 622     }
 623
 624     float minWeight = std::numeric_limits<float>::max();
 625     unsigned minReg = 0;
 626     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 627     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 628          i != rc->allocation_order_end(*mf_); ++i) {
 629         unsigned reg = *i;
 630         if (!reserved_[reg] && minWeight > regWeight[reg]) {
 631             minWeight = regWeight[reg];
 632             minReg = reg;
 633         }
 634     }
 635     DEBUG(std::cerr << "\t\t\tregister with min weight: "
 636           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 637
 638     if (cur->weight < minWeight) {
 639         restoreRegUse();
 640         DEBUG(std::cerr << "\t\t\t\tspilling: " << *cur << '\n');
 641         assignVirt2StackSlot(cur->reg);
 642     }
 643     else {
 644         std::set<unsigned> toSpill;
 645         toSpill.insert(minReg);
 646         for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 647             toSpill.insert(*as);
 648
 649         std::vector<unsigned> spilled;
 650         for (IntervalPtrs::iterator i = active_.begin();
 651              i != active_.end(); ) {
 652             unsigned reg = (*i)->reg;
 653             if (reg >= MRegisterInfo::FirstVirtualRegister &&
 654                 toSpill.find(v2pMap_[reg]) != toSpill.end() &&
 655                 cur->overlaps(**i)) {
 656                 spilled.push_back(v2pMap_[reg]);
 657                 DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 658                 assignVirt2StackSlot(reg);
 659                 i = active_.erase(i);
 660             }
 661             else {
 662                 ++i;
 663             }
 664         }
 665         for (IntervalPtrs::iterator i = inactive_.begin();
 666              i != inactive_.end(); ) {
 667             unsigned reg = (*i)->reg;
 668             if (reg >= MRegisterInfo::FirstVirtualRegister &&
 669                 toSpill.find(v2pMap_[reg]) != toSpill.end() &&
 670                 cur->overlaps(**i)) {
 671                 DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 672                 assignVirt2StackSlot(reg);
 673                 i = inactive_.erase(i);
 674             }
 675             else {
 676                 ++i;
 677             }
 678         }
 679
 680         unsigned physReg = getFreePhysReg(cur);
 681         assert(physReg && "no free physical register after spill?");
 682
 683         restoreRegUse();
 684         for (unsigned i = 0; i < spilled.size(); ++i)
 685             markPhysRegFree(spilled[i]);
 686
 687         assignVirt2PhysReg(cur->reg, physReg);
 688         active_.push_back(cur);
 689     }
 690 }
 691
 692 bool RA::physRegAvailable(unsigned physReg)
 693 {
 694     assert(!reserved_[physReg] &&
 695            "cannot call this method with a reserved register");
 696
 697     return !regUse_[physReg];
 698 }
 699
 700 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 701 {
 702     DEBUG(std::cerr << "\t\tgetting free physical register: ");
 703     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 704
 705     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 706          i != rc->allocation_order_end(*mf_); ++i) {
 707         unsigned reg = *i;
 708         if (!reserved_[reg] && !regUse_[reg]) {
 709             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 710             return reg;
 711         }
 712     }
 713
 714     DEBUG(std::cerr << "no free register\n");
 715     return 0;
 716 }
 717
 718 bool RA::tempPhysRegAvailable(unsigned physReg)
 719 {
 720     assert(reserved_[physReg] &&
 721            "cannot call this method with a not reserved temp register");
 722
 723     return !regUse_[physReg];
 724 }
 725
 726 unsigned RA::getFreeTempPhysReg(unsigned virtReg)
 727 {
 728     DEBUG(std::cerr << "\t\tgetting free temporary physical register: ");
 729
 730     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 731     // go in reverse allocation order for the temp registers
 732     for (TargetRegisterClass::iterator i = rc->allocation_order_end(*mf_) - 1;
 733          i != rc->allocation_order_begin(*mf_) - 1; --i) {
 734         unsigned reg = *i;
 735         if (reserved_[reg] && !regUse_[reg]) {
 736             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 737             return reg;
 738         }
 739     }
 740
 741     assert(0 && "no free temporary physical register?");
 742     return 0;
 743 }
 744
 745 void RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 746 {
 747     bool inserted = v2pMap_.insert(std::make_pair(virtReg, physReg)).second;
 748     assert(inserted && "attempting to assign a virt->phys mapping to an "
 749            "already mapped register");
 750     markPhysRegNotFree(physReg);
 751 }
 752
 753 void RA::clearVirtReg(unsigned virtReg)
 754 {
 755     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 756     assert(it != v2pMap_.end() &&
 757            "attempting to clear a not allocated virtual register");
 758     unsigned physReg = it->second;
 759     markPhysRegFree(physReg);
 760     v2pMap_.erase(it);
 761     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 762           << "\n");
 763 }
 764
 765 void RA::assignVirt2StackSlot(unsigned virtReg)
 766 {
 767     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 768     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 769
 770     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 771     assert(inserted &&
 772            "attempt to assign stack slot to already assigned register?");
 773     // if the virtual register was previously assigned clear the mapping
 774     // and free the virtual register
 775     if (v2pMap_.find(virtReg) != v2pMap_.end()) {
 776         clearVirtReg(virtReg);
 777     }
 778 }
 779
 780 int RA::getStackSlot(unsigned virtReg)
 781 {
 782     // use lower_bound so that we can do a possibly O(1) insert later
 783     // if necessary
 784     Virt2StackSlotMap::iterator it = v2ssMap_.find(virtReg);
 785     assert(it != v2ssMap_.end() &&
 786            "attempt to get stack slot on register that does not live on the stack");
 787     return it->second;
 788 }
 789
 790 void RA::spillVirtReg(unsigned virtReg)
 791 {
 792     DEBUG(std::cerr << "\t\t\tspilling register: " << virtReg);
 793     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 794     int frameIndex = getStackSlot(virtReg);
 795     DEBUG(std::cerr << " to stack slot #" << frameIndex << '\n');
 796     ++numSpilled;
 797     instrAdded_ += mri_->storeRegToStackSlot(*currentMbb_, currentInstr_,
 798                                              v2pMap_[virtReg], frameIndex, rc);
 799     clearVirtReg(virtReg);
 800 }
 801
 802 void RA::loadVirt2PhysReg(unsigned virtReg, unsigned physReg)
 803 {
 804     DEBUG(std::cerr << "\t\t\tloading register: " << virtReg);
 805     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 806     int frameIndex = getStackSlot(virtReg);
 807     DEBUG(std::cerr << " from stack slot #" << frameIndex << '\n');
 808     ++numReloaded;
 809     instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_,
 810                                               physReg, frameIndex, rc);
 811     assignVirt2PhysReg(virtReg, physReg);
 812 }
 813
 814 void RA::markPhysRegFree(unsigned physReg)
 815 {
 816     assert(regUse_[physReg] != 0);
 817     --regUse_[physReg];
 818     for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
 819         physReg = *as;
 820         assert(regUse_[physReg] != 0);
 821         --regUse_[physReg];
 822     }
 823 }
 824
 825 void RA::markPhysRegNotFree(unsigned physReg)
 826 {
 827     ++regUse_[physReg];
 828     for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
 829         physReg = *as;
 830         ++regUse_[physReg];
 831     }
 832 }
 833
 834 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 835     return new RA();
 836 }