lib/CodeGen/LiveIntervalAnalysis.cpp

   1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LiveInterval analysis pass which is used
  11 // by the Linear Scan Register allocator. This pass linearizes the
  12 // basic blocks of the function in DFS order and uses the
  13 // LiveVariables pass to conservatively compute live intervals for
  14 // each virtual and physical register.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "liveintervals"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "VirtRegMap.h"
  21 #include "llvm/Value.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/CodeGen/LiveVariables.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/MachineInstrBuilder.h"
  27 #include "llvm/CodeGen/MachineLoopInfo.h"
  28 #include "llvm/CodeGen/MachineRegisterInfo.h"
  29 #include "llvm/CodeGen/Passes.h"
  30 #include "llvm/CodeGen/PseudoSourceValue.h"
  31 #include "llvm/Target/TargetRegisterInfo.h"
  32 #include "llvm/Target/TargetInstrInfo.h"
  33 #include "llvm/Target/TargetMachine.h"
  34 #include "llvm/Target/TargetOptions.h"
  35 #include "llvm/Support/CommandLine.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/ErrorHandling.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include "llvm/ADT/DepthFirstIterator.h"
  40 #include "llvm/ADT/SmallSet.h"
  41 #include "llvm/ADT/Statistic.h"
  42 #include "llvm/ADT/STLExtras.h"
  43 #include <algorithm>
  44 #include <limits>
  45 #include <cmath>
  46 using namespace llvm;
  47
  48 // Hidden options for help debugging.
  49 static cl::opt<bool> DisableReMat("disable-rematerialization",
  50                                   cl::init(false), cl::Hidden);
  51
  52 static cl::opt<bool> SplitAtBB("split-intervals-at-bb",
  53                                cl::init(true), cl::Hidden);
  54 static cl::opt<int> SplitLimit("split-limit",
  55                                cl::init(-1), cl::Hidden);
  56
  57 static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
  58
  59 static cl::opt<bool> EnableFastSpilling("fast-spill",
  60                                         cl::init(false), cl::Hidden);
  61
  62 STATISTIC(numIntervals, "Number of original intervals");
  63 STATISTIC(numFolds    , "Number of loads/stores folded into instructions");
  64 STATISTIC(numSplits   , "Number of intervals split");
  65
  66 char LiveIntervals::ID = 0;
  67 static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
  68
  69 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  70   AU.setPreservesCFG();
  71   AU.addRequired<AliasAnalysis>();
  72   AU.addPreserved<AliasAnalysis>();
  73   AU.addPreserved<LiveVariables>();
  74   AU.addRequired<LiveVariables>();
  75   AU.addPreservedID(MachineLoopInfoID);
  76   AU.addPreservedID(MachineDominatorsID);
  77
  78   if (!StrongPHIElim) {
  79     AU.addPreservedID(PHIEliminationID);
  80     AU.addRequiredID(PHIEliminationID);
  81   }
  82
  83   AU.addRequiredID(TwoAddressInstructionPassID);
  84   MachineFunctionPass::getAnalysisUsage(AU);
  85 }
  86
  87 void LiveIntervals::releaseMemory() {
  88   // Free the live intervals themselves.
  89   for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
  90        E = r2iMap_.end(); I != E; ++I)
  91     delete I->second;
  92
  93   MBB2IdxMap.clear();
  94   Idx2MBBMap.clear();
  95   mi2iMap_.clear();
  96   i2miMap_.clear();
  97   r2iMap_.clear();
  98   terminatorGaps.clear();
  99
 100   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
 101   VNInfoAllocator.Reset();
 102   while (!ClonedMIs.empty()) {
 103     MachineInstr *MI = ClonedMIs.back();
 104     ClonedMIs.pop_back();
 105     mf_->DeleteMachineInstr(MI);
 106   }
 107 }
 108
 109 static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
 110                                    const TargetInstrInfo *tii_) {
 111   unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 112   if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
 113       Reg == SrcReg)
 114     return true;
 115
 116   if ((MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
 117        MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) &&
 118       MI->getOperand(2).getReg() == Reg)
 119     return true;
 120   if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG &&
 121       MI->getOperand(1).getReg() == Reg)
 122     return true;
 123   return false;
 124 }
 125
 126 /// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
 127 /// there is one implicit_def for each use. Add isUndef marker to
 128 /// implicit_def defs and their uses.
 129 void LiveIntervals::processImplicitDefs() {
 130   SmallSet<unsigned, 8> ImpDefRegs;
 131   SmallVector<MachineInstr*, 8> ImpDefMIs;
 132   MachineBasicBlock *Entry = mf_->begin();
 133   SmallPtrSet<MachineBasicBlock*,16> Visited;
 134   for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
 135          DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
 136        DFI != E; ++DFI) {
 137     MachineBasicBlock *MBB = *DFI;
 138     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 139          I != E; ) {
 140       MachineInstr *MI = &*I;
 141       ++I;
 142       if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
 143         unsigned Reg = MI->getOperand(0).getReg();
 144         ImpDefRegs.insert(Reg);
 145         ImpDefMIs.push_back(MI);
 146         continue;
 147       }
 148
 149       bool ChangedToImpDef = false;
 150       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 151         MachineOperand& MO = MI->getOperand(i);
 152         if (!MO.isReg() || !MO.isUse() || MO.isUndef())
 153           continue;
 154         unsigned Reg = MO.getReg();
 155         if (!Reg)
 156           continue;
 157         if (!ImpDefRegs.count(Reg))
 158           continue;
 159         // Use is a copy, just turn it into an implicit_def.
 160         if (CanTurnIntoImplicitDef(MI, Reg, tii_)) {
 161           bool isKill = MO.isKill();
 162           MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
 163           for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
 164             MI->RemoveOperand(j);
 165           if (isKill)
 166             ImpDefRegs.erase(Reg);
 167           ChangedToImpDef = true;
 168           break;
 169         }
 170
 171         MO.setIsUndef();
 172         if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
 173           // Make sure other uses of
 174           for (unsigned j = i+1; j != e; ++j) {
 175             MachineOperand &MOJ = MI->getOperand(j);
 176             if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
 177               MOJ.setIsUndef();
 178           }
 179           ImpDefRegs.erase(Reg);
 180         }
 181       }
 182
 183       if (ChangedToImpDef) {
 184         // Backtrack to process this new implicit_def.
 185         --I;
 186       } else {
 187         for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 188           MachineOperand& MO = MI->getOperand(i);
 189           if (!MO.isReg() || !MO.isDef())
 190             continue;
 191           ImpDefRegs.erase(MO.getReg());
 192         }
 193       }
 194     }
 195
 196     // Any outstanding liveout implicit_def's?
 197     for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
 198       MachineInstr *MI = ImpDefMIs[i];
 199       unsigned Reg = MI->getOperand(0).getReg();
 200       if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
 201           !ImpDefRegs.count(Reg)) {
 202         // Delete all "local" implicit_def's. That include those which define
 203         // physical registers since they cannot be liveout.
 204         MI->eraseFromParent();
 205         continue;
 206       }
 207
 208       // If there are multiple defs of the same register and at least one
 209       // is not an implicit_def, do not insert implicit_def's before the
 210       // uses.
 211       bool Skip = false;
 212       for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
 213              DE = mri_->def_end(); DI != DE; ++DI) {
 214         if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
 215           Skip = true;
 216           break;
 217         }
 218       }
 219       if (Skip)
 220         continue;
 221
 222       // The only implicit_def which we want to keep are those that are live
 223       // out of its block.
 224       MI->eraseFromParent();
 225
 226       for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
 227              UE = mri_->use_end(); UI != UE; ) {
 228         MachineOperand &RMO = UI.getOperand();
 229         MachineInstr *RMI = &*UI;
 230         ++UI;
 231         MachineBasicBlock *RMBB = RMI->getParent();
 232         if (RMBB == MBB)
 233           continue;
 234
 235         // Turn a copy use into an implicit_def.
 236         unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 237         if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
 238             Reg == SrcReg) {
 239           RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
 240           for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
 241             RMI->RemoveOperand(j);
 242           continue;
 243         }
 244
 245         const TargetRegisterClass* RC = mri_->getRegClass(Reg);
 246         unsigned NewVReg = mri_->createVirtualRegister(RC);
 247         RMO.setReg(NewVReg);
 248         RMO.setIsUndef();
 249         RMO.setIsKill();
 250       }
 251     }
 252     ImpDefRegs.clear();
 253     ImpDefMIs.clear();
 254   }
 255 }
 256
 257 void LiveIntervals::computeNumbering() {
 258   Index2MiMap OldI2MI = i2miMap_;
 259   std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
 260
 261   Idx2MBBMap.clear();
 262   MBB2IdxMap.clear();
 263   mi2iMap_.clear();
 264   i2miMap_.clear();
 265   terminatorGaps.clear();
 266
 267   FunctionSize = 0;
 268
 269   // Number MachineInstrs and MachineBasicBlocks.
 270   // Initialize MBB indexes to a sentinal.
 271   MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
 272
 273   unsigned MIIndex = 0;
 274   for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
 275        MBB != E; ++MBB) {
 276     unsigned StartIdx = MIIndex;
 277
 278     // Insert an empty slot at the beginning of each block.
 279     MIIndex += InstrSlots::NUM;
 280     i2miMap_.push_back(0);
 281
 282     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 283          I != E; ++I) {
 284
 285       if (I == MBB->getFirstTerminator()) {
 286         // Leave a gap for before terminators, this is where we will point
 287         // PHI kills.
 288         bool inserted =
 289           terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
 290         assert(inserted &&
 291                "Multiple 'first' terminators encountered during numbering.");
 292         inserted = inserted; // Avoid compiler warning if assertions turned off.
 293         i2miMap_.push_back(0);
 294
 295         MIIndex += InstrSlots::NUM;
 296       }
 297
 298       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
 299       assert(inserted && "multiple MachineInstr -> index mappings");
 300       inserted = true;
 301       i2miMap_.push_back(I);
 302       MIIndex += InstrSlots::NUM;
 303       FunctionSize++;
 304
 305       // Insert max(1, numdefs) empty slots after every instruction.
 306       unsigned Slots = I->getDesc().getNumDefs();
 307       if (Slots == 0)
 308         Slots = 1;
 309       MIIndex += InstrSlots::NUM * Slots;
 310       while (Slots--)
 311         i2miMap_.push_back(0);
 312     }
 313
 314     if (MBB->getFirstTerminator() == MBB->end()) {
 315       // Leave a gap for before terminators, this is where we will point
 316       // PHI kills.
 317       bool inserted =
 318         terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
 319       assert(inserted &&
 320              "Multiple 'first' terminators encountered during numbering.");
 321       inserted = inserted; // Avoid compiler warning if assertions turned off.
 322       i2miMap_.push_back(0);
 323
 324       MIIndex += InstrSlots::NUM;
 325     }
 326
 327     // Set the MBB2IdxMap entry for this MBB.
 328     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
 329     Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
 330   }
 331
 332   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
 333
 334   if (!OldI2MI.empty())
 335     for (iterator OI = begin(), OE = end(); OI != OE; ++OI) {
 336       for (LiveInterval::iterator LI = OI->second->begin(),
 337            LE = OI->second->end(); LI != LE; ++LI) {
 338
 339         // Remap the start index of the live range to the corresponding new
 340         // number, or our best guess at what it _should_ correspond to if the
 341         // original instruction has been erased.  This is either the following
 342         // instruction or its predecessor.
 343         unsigned index = LI->start / InstrSlots::NUM;
 344         unsigned offset = LI->start % InstrSlots::NUM;
 345         if (offset == InstrSlots::LOAD) {
 346           std::vector<IdxMBBPair>::const_iterator I =
 347                   std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start);
 348           // Take the pair containing the index
 349           std::vector<IdxMBBPair>::const_iterator J =
 350                     (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
 351
 352           LI->start = getMBBStartIdx(J->second);
 353         } else {
 354           LI->start = mi2iMap_[OldI2MI[index]] + offset;
 355         }
 356
 357         // Remap the ending index in the same way that we remapped the start,
 358         // except for the final step where we always map to the immediately
 359         // following instruction.
 360         index = (LI->end - 1) / InstrSlots::NUM;
 361         offset  = LI->end % InstrSlots::NUM;
 362         if (offset == InstrSlots::LOAD) {
 363           // VReg dies at end of block.
 364           std::vector<IdxMBBPair>::const_iterator I =
 365                   std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
 366           --I;
 367
 368           LI->end = getMBBEndIdx(I->second) + 1;
 369         } else {
 370           unsigned idx = index;
 371           while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
 372
 373           if (index != OldI2MI.size())
 374             LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0);
 375           else
 376             LI->end = InstrSlots::NUM * i2miMap_.size();
 377         }
 378       }
 379
 380       for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(),
 381            VNE = OI->second->vni_end(); VNI != VNE; ++VNI) {
 382         VNInfo* vni = *VNI;
 383
 384         // Remap the VNInfo def index, which works the same as the
 385         // start indices above. VN's with special sentinel defs
 386         // don't need to be remapped.
 387         if (vni->isDefAccurate() && !vni->isUnused()) {
 388           unsigned index = vni->def / InstrSlots::NUM;
 389           unsigned offset = vni->def % InstrSlots::NUM;
 390           if (offset == InstrSlots::LOAD) {
 391             std::vector<IdxMBBPair>::const_iterator I =
 392                   std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def);
 393             // Take the pair containing the index
 394             std::vector<IdxMBBPair>::const_iterator J =
 395                     (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
 396
 397             vni->def = getMBBStartIdx(J->second);
 398           } else {
 399             vni->def = mi2iMap_[OldI2MI[index]] + offset;
 400           }
 401         }
 402
 403         // Remap the VNInfo kill indices, which works the same as
 404         // the end indices above.
 405         for (size_t i = 0; i < vni->kills.size(); ++i) {
 406           unsigned killIdx = vni->kills[i].killIdx;
 407
 408           unsigned index = (killIdx - 1) / InstrSlots::NUM;
 409           unsigned offset = killIdx % InstrSlots::NUM;
 410
 411           if (offset == InstrSlots::LOAD) {
 412             assert("Value killed at a load slot.");
 413             /*std::vector<IdxMBBPair>::const_iterator I =
 414              std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
 415             --I;
 416
 417             vni->kills[i] = getMBBEndIdx(I->second);*/
 418           } else {
 419             if (vni->kills[i].isPHIKill) {
 420               std::vector<IdxMBBPair>::const_iterator I =
 421                 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index);
 422               --I;
 423               vni->kills[i].killIdx = terminatorGaps[I->second];
 424             } else {
 425               assert(OldI2MI[index] != 0 &&
 426                      "Kill refers to instruction not present in index maps.");
 427               vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset;
 428             }
 429
 430             /*
 431             unsigned idx = index;
 432             while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
 433
 434             if (index != OldI2MI.size())
 435               vni->kills[i] = mi2iMap_[OldI2MI[index]] +
 436                               (idx == index ? offset : 0);
 437             else
 438               vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
 439             */
 440           }
 441         }
 442       }
 443     }
 444 }
 445
 446 void LiveIntervals::scaleNumbering(int factor) {
 447   // Need to
 448   //  * scale MBB begin and end points
 449   //  * scale all ranges.
 450   //  * Update VNI structures.
 451   //  * Scale instruction numberings
 452
 453   // Scale the MBB indices.
 454   Idx2MBBMap.clear();
 455   for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end();
 456        MBB != MBBE; ++MBB) {
 457     std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()];
 458     mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor);
 459     mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor);
 460     Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB));
 461   }
 462   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
 463
 464   // Scale terminator gaps.
 465   for (DenseMap<MachineBasicBlock*, unsigned>::iterator
 466        TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
 467        TGI != TGE; ++TGI) {
 468     terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor);
 469   }
 470
 471   // Scale the intervals.
 472   for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
 473     LI->second->scaleNumbering(factor);
 474   }
 475
 476   // Scale MachineInstrs.
 477   Mi2IndexMap oldmi2iMap = mi2iMap_;
 478   unsigned highestSlot = 0;
 479   for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end();
 480        MI != ME; ++MI) {
 481     unsigned newSlot = InstrSlots::scale(MI->second, factor);
 482     mi2iMap_[MI->first] = newSlot;
 483     highestSlot = std::max(highestSlot, newSlot);
 484   }
 485
 486   i2miMap_.clear();
 487   i2miMap_.resize(highestSlot + 1);
 488   for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end();
 489        MI != ME; ++MI) {
 490     i2miMap_[MI->second] = const_cast<MachineInstr *>(MI->first);
 491   }
 492
 493 }
 494
 495
 496 /// runOnMachineFunction - Register allocate the whole function
 497 ///
 498 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 499   mf_ = &fn;
 500   mri_ = &mf_->getRegInfo();
 501   tm_ = &fn.getTarget();
 502   tri_ = tm_->getRegisterInfo();
 503   tii_ = tm_->getInstrInfo();
 504   aa_ = &getAnalysis<AliasAnalysis>();
 505   lv_ = &getAnalysis<LiveVariables>();
 506   allocatableRegs_ = tri_->getAllocatableSet(fn);
 507
 508   processImplicitDefs();
 509   computeNumbering();
 510   computeIntervals();
 511
 512   numIntervals += getNumIntervals();
 513
 514   DEBUG(dump());
 515   return true;
 516 }
 517
 518 /// print - Implement the dump method.
 519 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
 520   OS << "********** INTERVALS **********\n";
 521   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 522     I->second->print(OS, tri_);
 523     OS << "\n";
 524   }
 525
 526   OS << "********** MACHINEINSTRS **********\n";
 527
 528   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 529        mbbi != mbbe; ++mbbi) {
 530     OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
 531     for (MachineBasicBlock::iterator mii = mbbi->begin(),
 532            mie = mbbi->end(); mii != mie; ++mii) {
 533       OS << getInstructionIndex(mii) << '\t' << *mii;
 534     }
 535   }
 536 }
 537
 538 /// conflictsWithPhysRegDef - Returns true if the specified register
 539 /// is defined during the duration of the specified interval.
 540 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
 541                                             VirtRegMap &vrm, unsigned reg) {
 542   for (LiveInterval::Ranges::const_iterator
 543          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 544     for (unsigned index = getBaseIndex(I->start),
 545            end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
 546          index += InstrSlots::NUM) {
 547       // skip deleted instructions
 548       while (index != end && !getInstructionFromIndex(index))
 549         index += InstrSlots::NUM;
 550       if (index == end) break;
 551
 552       MachineInstr *MI = getInstructionFromIndex(index);
 553       unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 554       if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
 555         if (SrcReg == li.reg || DstReg == li.reg)
 556           continue;
 557       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 558         MachineOperand& mop = MI->getOperand(i);
 559         if (!mop.isReg())
 560           continue;
 561         unsigned PhysReg = mop.getReg();
 562         if (PhysReg == 0 || PhysReg == li.reg)
 563           continue;
 564         if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
 565           if (!vrm.hasPhys(PhysReg))
 566             continue;
 567           PhysReg = vrm.getPhys(PhysReg);
 568         }
 569         if (PhysReg && tri_->regsOverlap(PhysReg, reg))
 570           return true;
 571       }
 572     }
 573   }
 574
 575   return false;
 576 }
 577
 578 /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
 579 /// it can check use as well.
 580 bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li,
 581                                             unsigned Reg, bool CheckUse,
 582                                   SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
 583   for (LiveInterval::Ranges::const_iterator
 584          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 585     for (unsigned index = getBaseIndex(I->start),
 586            end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
 587          index += InstrSlots::NUM) {
 588       // Skip deleted instructions.
 589       MachineInstr *MI = 0;
 590       while (index != end) {
 591         MI = getInstructionFromIndex(index);
 592         if (MI)
 593           break;
 594         index += InstrSlots::NUM;
 595       }
 596       if (index == end) break;
 597
 598       if (JoinedCopies.count(MI))
 599         continue;
 600       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 601         MachineOperand& MO = MI->getOperand(i);
 602         if (!MO.isReg())
 603           continue;
 604         if (MO.isUse() && !CheckUse)
 605           continue;
 606         unsigned PhysReg = MO.getReg();
 607         if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg))
 608           continue;
 609         if (tri_->isSubRegister(Reg, PhysReg))
 610           return true;
 611       }
 612     }
 613   }
 614
 615   return false;
 616 }
 617
 618
 619 void LiveIntervals::printRegName(unsigned reg) const {
 620   if (TargetRegisterInfo::isPhysicalRegister(reg))
 621     errs() << tri_->getName(reg);
 622   else
 623     errs() << "%reg" << reg;
 624 }
 625
 626 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 627                                              MachineBasicBlock::iterator mi,
 628                                              unsigned MIIdx, MachineOperand& MO,
 629                                              unsigned MOIdx,
 630                                              LiveInterval &interval) {
 631   DEBUG({
 632       errs() << "\t\tregister: ";
 633       printRegName(interval.reg);
 634     });
 635
 636   // Virtual registers may be defined multiple times (due to phi
 637   // elimination and 2-addr elimination).  Much of what we do only has to be
 638   // done once for the vreg.  We use an empty interval to detect the first
 639   // time we see a vreg.
 640   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
 641   if (interval.empty()) {
 642     // Get the Idx of the defining instructions.
 643     unsigned defIndex = getDefIndex(MIIdx);
 644     // Earlyclobbers move back one.
 645     if (MO.isEarlyClobber())
 646       defIndex = getUseIndex(MIIdx);
 647     VNInfo *ValNo;
 648     MachineInstr *CopyMI = NULL;
 649     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 650     if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
 651         mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
 652         mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
 653         tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
 654       CopyMI = mi;
 655     // Earlyclobbers move back one.
 656     ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
 657
 658     assert(ValNo->id == 0 && "First value in interval is not 0?");
 659
 660     // Loop over all of the blocks that the vreg is defined in.  There are
 661     // two cases we have to handle here.  The most common case is a vreg
 662     // whose lifetime is contained within a basic block.  In this case there
 663     // will be a single kill, in MBB, which comes after the definition.
 664     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 665       // FIXME: what about dead vars?
 666       unsigned killIdx;
 667       if (vi.Kills[0] != mi)
 668         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
 669       else
 670         killIdx = defIndex+1;
 671
 672       // If the kill happens after the definition, we have an intra-block
 673       // live range.
 674       if (killIdx > defIndex) {
 675         assert(vi.AliveBlocks.empty() &&
 676                "Shouldn't be alive across any blocks!");
 677         LiveRange LR(defIndex, killIdx, ValNo);
 678         interval.addRange(LR);
 679         DEBUG(errs() << " +" << LR << "\n");
 680         interval.addKill(ValNo, killIdx, false);
 681         return;
 682       }
 683     }
 684
 685     // The other case we handle is when a virtual register lives to the end
 686     // of the defining block, potentially live across some blocks, then is
 687     // live into some number of blocks, but gets killed.  Start by adding a
 688     // range that goes from this definition to the end of the defining block.
 689     LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo);
 690     DEBUG(errs() << " +" << NewLR);
 691     interval.addRange(NewLR);
 692
 693     // Iterate over all of the blocks that the variable is completely
 694     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 695     // live interval.
 696     for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
 697              E = vi.AliveBlocks.end(); I != E; ++I) {
 698       LiveRange LR(getMBBStartIdx(*I),
 699                    getMBBEndIdx(*I)+1,  // MBB ends at -1.
 700                    ValNo);
 701       interval.addRange(LR);
 702       DEBUG(errs() << " +" << LR);
 703     }
 704
 705     // Finally, this virtual register is live from the start of any killing
 706     // block to the 'use' slot of the killing instruction.
 707     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 708       MachineInstr *Kill = vi.Kills[i];
 709       unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
 710       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 711                    killIdx, ValNo);
 712       interval.addRange(LR);
 713       interval.addKill(ValNo, killIdx, false);
 714       DEBUG(errs() << " +" << LR);
 715     }
 716
 717   } else {
 718     // If this is the second time we see a virtual register definition, it
 719     // must be due to phi elimination or two addr elimination.  If this is
 720     // the result of two address elimination, then the vreg is one of the
 721     // def-and-use register operand.
 722     if (mi->isRegTiedToUseOperand(MOIdx)) {
 723       // If this is a two-address definition, then we have already processed
 724       // the live range.  The only problem is that we didn't realize there
 725       // are actually two values in the live interval.  Because of this we
 726       // need to take the LiveRegion that defines this register and split it
 727       // into two values.
 728       assert(interval.containsOneValue());
 729       unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
 730       unsigned RedefIndex = getDefIndex(MIIdx);
 731       if (MO.isEarlyClobber())
 732         RedefIndex = getUseIndex(MIIdx);
 733
 734       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
 735       VNInfo *OldValNo = OldLR->valno;
 736
 737       // Delete the initial value, which should be short and continuous,
 738       // because the 2-addr copy must be in the same MBB as the redef.
 739       interval.removeRange(DefIndex, RedefIndex);
 740
 741       // Two-address vregs should always only be redefined once.  This means
 742       // that at this point, there should be exactly one value number in it.
 743       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
 744
 745       // The new value number (#1) is defined by the instruction we claimed
 746       // defined value #0.
 747       VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(),
 748                                             false, // update at *
 749                                             VNInfoAllocator);
 750       ValNo->setFlags(OldValNo->getFlags()); // * <- updating here
 751
 752       // Value#0 is now defined by the 2-addr instruction.
 753       OldValNo->def  = RedefIndex;
 754       OldValNo->setCopy(0);
 755       if (MO.isEarlyClobber())
 756         OldValNo->setHasRedefByEC(true);
 757
 758       // Add the new live interval which replaces the range for the input copy.
 759       LiveRange LR(DefIndex, RedefIndex, ValNo);
 760       DEBUG(errs() << " replace range with " << LR);
 761       interval.addRange(LR);
 762       interval.addKill(ValNo, RedefIndex, false);
 763
 764       // If this redefinition is dead, we need to add a dummy unit live
 765       // range covering the def slot.
 766       if (MO.isDead())
 767         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
 768
 769       DEBUG({
 770           errs() << " RESULT: ";
 771           interval.print(errs(), tri_);
 772         });
 773     } else {
 774       // Otherwise, this must be because of phi elimination.  If this is the
 775       // first redefinition of the vreg that we have seen, go back and change
 776       // the live range in the PHI block to be a different value number.
 777       if (interval.containsOneValue()) {
 778         assert(vi.Kills.size() == 1 &&
 779                "PHI elimination vreg should have one kill, the PHI itself!");
 780
 781         // Remove the old range that we now know has an incorrect number.
 782         VNInfo *VNI = interval.getValNumInfo(0);
 783         MachineInstr *Killer = vi.Kills[0];
 784         unsigned Start = getMBBStartIdx(Killer->getParent());
 785         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 786         DEBUG({
 787             errs() << " Removing [" << Start << "," << End << "] from: ";
 788             interval.print(errs(), tri_);
 789             errs() << "\n";
 790           });
 791         interval.removeRange(Start, End);
 792         assert(interval.ranges.size() == 1 &&
 793                "newly discovered PHI interval has >1 ranges.");
 794         MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber());
 795         interval.addKill(VNI, terminatorGaps[killMBB], true);
 796         VNI->setHasPHIKill(true);
 797         DEBUG({
 798             errs() << " RESULT: ";
 799             interval.print(errs(), tri_);
 800           });
 801
 802         // Replace the interval with one of a NEW value number.  Note that this
 803         // value number isn't actually defined by an instruction, weird huh? :)
 804         LiveRange LR(Start, End,
 805           interval.getNextValue(mbb->getNumber(), 0, false, VNInfoAllocator));
 806         LR.valno->setIsPHIDef(true);
 807         DEBUG(errs() << " replace range with " << LR);
 808         interval.addRange(LR);
 809         interval.addKill(LR.valno, End, false);
 810         DEBUG({
 811             errs() << " RESULT: ";
 812             interval.print(errs(), tri_);
 813           });
 814       }
 815
 816       // In the case of PHI elimination, each variable definition is only
 817       // live until the end of the block.  We've already taken care of the
 818       // rest of the live range.
 819       unsigned defIndex = getDefIndex(MIIdx);
 820       if (MO.isEarlyClobber())
 821         defIndex = getUseIndex(MIIdx);
 822
 823       VNInfo *ValNo;
 824       MachineInstr *CopyMI = NULL;
 825       unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 826       if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
 827           mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
 828           mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
 829           tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
 830         CopyMI = mi;
 831       ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
 832
 833       unsigned killIndex = getMBBEndIdx(mbb) + 1;
 834       LiveRange LR(defIndex, killIndex, ValNo);
 835       interval.addRange(LR);
 836       interval.addKill(ValNo, terminatorGaps[mbb], true);
 837       ValNo->setHasPHIKill(true);
 838       DEBUG(errs() << " +" << LR);
 839     }
 840   }
 841
 842   DEBUG(errs() << '\n');
 843 }
 844
 845 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 846                                               MachineBasicBlock::iterator mi,
 847                                               unsigned MIIdx,
 848                                               MachineOperand& MO,
 849                                               LiveInterval &interval,
 850                                               MachineInstr *CopyMI) {
 851   // A physical register cannot be live across basic block, so its
 852   // lifetime must end somewhere in its defining basic block.
 853   DEBUG({
 854       errs() << "\t\tregister: ";
 855       printRegName(interval.reg);
 856     });
 857
 858   unsigned baseIndex = MIIdx;
 859   unsigned start = getDefIndex(baseIndex);
 860   // Earlyclobbers move back one.
 861   if (MO.isEarlyClobber())
 862     start = getUseIndex(MIIdx);
 863   unsigned end = start;
 864
 865   // If it is not used after definition, it is considered dead at
 866   // the instruction defining it. Hence its interval is:
 867   // [defSlot(def), defSlot(def)+1)
 868   if (MO.isDead()) {
 869     DEBUG(errs() << " dead");
 870     end = start + 1;
 871     goto exit;
 872   }
 873
 874   // If it is not dead on definition, it must be killed by a
 875   // subsequent instruction. Hence its interval is:
 876   // [defSlot(def), useSlot(kill)+1)
 877   baseIndex += InstrSlots::NUM;
 878   while (++mi != MBB->end()) {
 879     while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
 880            getInstructionFromIndex(baseIndex) == 0)
 881       baseIndex += InstrSlots::NUM;
 882     if (mi->killsRegister(interval.reg, tri_)) {
 883       DEBUG(errs() << " killed");
 884       end = getUseIndex(baseIndex) + 1;
 885       goto exit;
 886     } else {
 887       int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_);
 888       if (DefIdx != -1) {
 889         if (mi->isRegTiedToUseOperand(DefIdx)) {
 890           // Two-address instruction.
 891           end = getDefIndex(baseIndex);
 892           if (mi->getOperand(DefIdx).isEarlyClobber())
 893             end = getUseIndex(baseIndex);
 894         } else {
 895           // Another instruction redefines the register before it is ever read.
 896           // Then the register is essentially dead at the instruction that defines
 897           // it. Hence its interval is:
 898           // [defSlot(def), defSlot(def)+1)
 899           DEBUG(errs() << " dead");
 900           end = start + 1;
 901         }
 902         goto exit;
 903       }
 904     }
 905
 906     baseIndex += InstrSlots::NUM;
 907   }
 908
 909   // The only case we should have a dead physreg here without a killing or
 910   // instruction where we know it's dead is if it is live-in to the function
 911   // and never used. Another possible case is the implicit use of the
 912   // physical register has been deleted by two-address pass.
 913   end = start + 1;
 914
 915 exit:
 916   assert(start < end && "did not find end of interval?");
 917
 918   // Already exists? Extend old live interval.
 919   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 920   bool Extend = OldLR != interval.end();
 921   VNInfo *ValNo = Extend
 922     ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator);
 923   if (MO.isEarlyClobber() && Extend)
 924     ValNo->setHasRedefByEC(true);
 925   LiveRange LR(start, end, ValNo);
 926   interval.addRange(LR);
 927   interval.addKill(LR.valno, end, false);
 928   DEBUG(errs() << " +" << LR << '\n');
 929 }
 930
 931 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 932                                       MachineBasicBlock::iterator MI,
 933                                       unsigned MIIdx,
 934                                       MachineOperand& MO,
 935                                       unsigned MOIdx) {
 936   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 937     handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
 938                              getOrCreateInterval(MO.getReg()));
 939   else if (allocatableRegs_[MO.getReg()]) {
 940     MachineInstr *CopyMI = NULL;
 941     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 942     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
 943         MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
 944         MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
 945         tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
 946       CopyMI = MI;
 947     handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
 948                               getOrCreateInterval(MO.getReg()), CopyMI);
 949     // Def of a register also defines its sub-registers.
 950     for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
 951       // If MI also modifies the sub-register explicitly, avoid processing it
 952       // more than once. Do not pass in TRI here so it checks for exact match.
 953       if (!MI->modifiesRegister(*AS))
 954         handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
 955                                   getOrCreateInterval(*AS), 0);
 956   }
 957 }
 958
 959 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 960                                          unsigned MIIdx,
 961                                          LiveInterval &interval, bool isAlias) {
 962   DEBUG({
 963       errs() << "\t\tlivein register: ";
 964       printRegName(interval.reg);
 965     });
 966
 967   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 968   // be considered a livein.
 969   MachineBasicBlock::iterator mi = MBB->begin();
 970   unsigned baseIndex = MIIdx;
 971   unsigned start = baseIndex;
 972   while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
 973          getInstructionFromIndex(baseIndex) == 0)
 974     baseIndex += InstrSlots::NUM;
 975   unsigned end = baseIndex;
 976   bool SeenDefUse = false;
 977
 978   while (mi != MBB->end()) {
 979     if (mi->killsRegister(interval.reg, tri_)) {
 980       DEBUG(errs() << " killed");
 981       end = getUseIndex(baseIndex) + 1;
 982       SeenDefUse = true;
 983       break;
 984     } else if (mi->modifiesRegister(interval.reg, tri_)) {
 985       // Another instruction redefines the register before it is ever read.
 986       // Then the register is essentially dead at the instruction that defines
 987       // it. Hence its interval is:
 988       // [defSlot(def), defSlot(def)+1)
 989       DEBUG(errs() << " dead");
 990       end = getDefIndex(start) + 1;
 991       SeenDefUse = true;
 992       break;
 993     }
 994
 995     baseIndex += InstrSlots::NUM;
 996     ++mi;
 997     if (mi != MBB->end()) {
 998       while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
 999              getInstructionFromIndex(baseIndex) == 0)
1000         baseIndex += InstrSlots::NUM;
1001     }
1002   }
1003
1004   // Live-in register might not be used at all.
1005   if (!SeenDefUse) {
1006     if (isAlias) {
1007       DEBUG(errs() << " dead");
1008       end = getDefIndex(MIIdx) + 1;
1009     } else {
1010       DEBUG(errs() << " live through");
1011       end = baseIndex;
1012     }
1013   }
1014
1015   VNInfo *vni =
1016     interval.getNextValue(MBB->getNumber(), 0, false, VNInfoAllocator);
1017   vni->setIsPHIDef(true);
1018   LiveRange LR(start, end, vni);
1019
1020   interval.addRange(LR);
1021   interval.addKill(LR.valno, end, false);
1022   DEBUG(errs() << " +" << LR << '\n');
1023 }
1024
1025 /// computeIntervals - computes the live intervals for virtual
1026 /// registers. for some ordering of the machine instructions [1,N] a
1027 /// live interval is an interval [i, j) where 1 <= i <= j < N for
1028 /// which a variable is live
1029 void LiveIntervals::computeIntervals() {
1030   DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n"
1031                << "********** Function: "
1032                << ((Value*)mf_->getFunction())->getName() << '\n');
1033
1034   SmallVector<unsigned, 8> UndefUses;
1035   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
1036        MBBI != E; ++MBBI) {
1037     MachineBasicBlock *MBB = MBBI;
1038     // Track the index of the current machine instr.
1039     unsigned MIIndex = getMBBStartIdx(MBB);
1040     DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
1041
1042     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
1043
1044     // Create intervals for live-ins to this BB first.
1045     for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
1046            LE = MBB->livein_end(); LI != LE; ++LI) {
1047       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
1048       // Multiple live-ins can alias the same register.
1049       for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
1050         if (!hasInterval(*AS))
1051           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
1052                                true);
1053     }
1054
1055     // Skip over empty initial indices.
1056     while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
1057            getInstructionFromIndex(MIIndex) == 0)
1058       MIIndex += InstrSlots::NUM;
1059
1060     for (; MI != miEnd; ++MI) {
1061       DEBUG(errs() << MIIndex << "\t" << *MI);
1062
1063       // Handle defs.
1064       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
1065         MachineOperand &MO = MI->getOperand(i);
1066         if (!MO.isReg() || !MO.getReg())
1067           continue;
1068
1069         // handle register defs - build intervals
1070         if (MO.isDef())
1071           handleRegisterDef(MBB, MI, MIIndex, MO, i);
1072         else if (MO.isUndef())
1073           UndefUses.push_back(MO.getReg());
1074       }
1075
1076       // Skip over the empty slots after each instruction.
1077       unsigned Slots = MI->getDesc().getNumDefs();
1078       if (Slots == 0)
1079         Slots = 1;
1080       MIIndex += InstrSlots::NUM * Slots;
1081
1082       // Skip over empty indices.
1083       while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
1084              getInstructionFromIndex(MIIndex) == 0)
1085         MIIndex += InstrSlots::NUM;
1086     }
1087   }
1088
1089   // Create empty intervals for registers defined by implicit_def's (except
1090   // for those implicit_def that define values which are liveout of their
1091   // blocks.
1092   for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
1093     unsigned UndefReg = UndefUses[i];
1094     (void)getOrCreateInterval(UndefReg);
1095   }
1096 }
1097
1098 bool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End,
1099                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
1100   std::vector<IdxMBBPair>::const_iterator I =
1101     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
1102
1103   bool ResVal = false;
1104   while (I != Idx2MBBMap.end()) {
1105     if (I->first >= End)
1106       break;
1107     MBBs.push_back(I->second);
1108     ResVal = true;
1109     ++I;
1110   }
1111   return ResVal;
1112 }
1113
1114 bool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End,
1115                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
1116   std::vector<IdxMBBPair>::const_iterator I =
1117     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
1118
1119   bool ResVal = false;
1120   while (I != Idx2MBBMap.end()) {
1121     if (I->first > End)
1122       break;
1123     MachineBasicBlock *MBB = I->second;
1124     if (getMBBEndIdx(MBB) > End)
1125       break;
1126     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
1127            SE = MBB->succ_end(); SI != SE; ++SI)
1128       MBBs.push_back(*SI);
1129     ResVal = true;
1130     ++I;
1131   }
1132   return ResVal;
1133 }
1134
1135 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
1136   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
1137   return new LiveInterval(reg, Weight);
1138 }
1139
1140 /// dupInterval - Duplicate a live interval. The caller is responsible for
1141 /// managing the allocated memory.
1142 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
1143   LiveInterval *NewLI = createInterval(li->reg);
1144   NewLI->Copy(*li, mri_, getVNInfoAllocator());
1145   return NewLI;
1146 }
1147
1148 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
1149 /// copy field and returns the source register that defines it.
1150 unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
1151   if (!VNI->getCopy())
1152     return 0;
1153
1154   if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
1155     // If it's extracting out of a physical register, return the sub-register.
1156     unsigned Reg = VNI->getCopy()->getOperand(1).getReg();
1157     if (TargetRegisterInfo::isPhysicalRegister(Reg))
1158       Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm());
1159     return Reg;
1160   } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
1161              VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
1162     return VNI->getCopy()->getOperand(2).getReg();
1163
1164   unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
1165   if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg))
1166     return SrcReg;
1167   llvm_unreachable("Unrecognized copy instruction!");
1168   return 0;
1169 }
1170
1171 //===----------------------------------------------------------------------===//
1172 // Register allocator hooks.
1173 //
1174
1175 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
1176 /// allow one) virtual register operand, then its uses are implicitly using
1177 /// the register. Returns the virtual register.
1178 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
1179                                             MachineInstr *MI) const {
1180   unsigned RegOp = 0;
1181   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1182     MachineOperand &MO = MI->getOperand(i);
1183     if (!MO.isReg() || !MO.isUse())
1184       continue;
1185     unsigned Reg = MO.getReg();
1186     if (Reg == 0 || Reg == li.reg)
1187       continue;
1188
1189     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
1190         !allocatableRegs_[Reg])
1191       continue;
1192     // FIXME: For now, only remat MI with at most one register operand.
1193     assert(!RegOp &&
1194            "Can't rematerialize instruction with multiple register operand!");
1195     RegOp = MO.getReg();
1196 #ifndef NDEBUG
1197     break;
1198 #endif
1199   }
1200   return RegOp;
1201 }
1202
1203 /// isValNoAvailableAt - Return true if the val# of the specified interval
1204 /// which reaches the given instruction also reaches the specified use index.
1205 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
1206                                        unsigned UseIdx) const {
1207   unsigned Index = getInstructionIndex(MI);
1208   VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
1209   LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
1210   return UI != li.end() && UI->valno == ValNo;
1211 }
1212
1213 /// isReMaterializable - Returns true if the definition MI of the specified
1214 /// val# of the specified interval is re-materializable.
1215 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1216                                        const VNInfo *ValNo, MachineInstr *MI,
1217                                        SmallVectorImpl<LiveInterval*> &SpillIs,
1218                                        bool &isLoad) {
1219   if (DisableReMat)
1220     return false;
1221
1222   if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
1223     return true;
1224
1225   int FrameIdx = 0;
1226   if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
1227       mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
1228     // FIXME: Let target specific isReallyTriviallyReMaterializable determines
1229     // this but remember this is not safe to fold into a two-address
1230     // instruction.
1231     // This is a load from fixed stack slot. It can be rematerialized.
1232     return true;
1233
1234   // If the target-specific rules don't identify an instruction as
1235   // being trivially rematerializable, use some target-independent
1236   // rules.
1237   if (!MI->getDesc().isRematerializable() ||
1238       !tii_->isTriviallyReMaterializable(MI)) {
1239     if (!EnableAggressiveRemat)
1240       return false;
1241
1242     // If the instruction accesses memory but the memoperands have been lost,
1243     // we can't analyze it.
1244     const TargetInstrDesc &TID = MI->getDesc();
1245     if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty())
1246       return false;
1247
1248     // Avoid instructions obviously unsafe for remat.
1249     if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable())
1250       return false;
1251
1252     // If the instruction accesses memory and the memory could be non-constant,
1253     // assume the instruction is not rematerializable.
1254     for (std::list<MachineMemOperand>::const_iterator
1255            I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){
1256       const MachineMemOperand &MMO = *I;
1257       if (MMO.isVolatile() || MMO.isStore())
1258         return false;
1259       const Value *V = MMO.getValue();
1260       if (!V)
1261         return false;
1262       if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
1263         if (!PSV->isConstant(mf_->getFrameInfo()))
1264           return false;
1265       } else if (!aa_->pointsToConstantMemory(V))
1266         return false;
1267     }
1268
1269     // If any of the registers accessed are non-constant, conservatively assume
1270     // the instruction is not rematerializable.
1271     unsigned ImpUse = 0;
1272     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1273       const MachineOperand &MO = MI->getOperand(i);
1274       if (MO.isReg()) {
1275         unsigned Reg = MO.getReg();
1276         if (Reg == 0)
1277           continue;
1278         if (TargetRegisterInfo::isPhysicalRegister(Reg))
1279           return false;
1280
1281         // Only allow one def, and that in the first operand.
1282         if (MO.isDef() != (i == 0))
1283           return false;
1284
1285         // Only allow constant-valued registers.
1286         bool IsLiveIn = mri_->isLiveIn(Reg);
1287         MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg),
1288                                           E = mri_->def_end();
1289
1290         // For the def, it should be the only def of that register.
1291         if (MO.isDef() && (next(I) != E || IsLiveIn))
1292           return false;
1293
1294         if (MO.isUse()) {
1295           // Only allow one use other register use, as that's all the
1296           // remat mechanisms support currently.
1297           if (Reg != li.reg) {
1298             if (ImpUse == 0)
1299               ImpUse = Reg;
1300             else if (Reg != ImpUse)
1301               return false;
1302           }
1303           // For the use, there should be only one associated def.
1304           if (I != E && (next(I) != E || IsLiveIn))
1305             return false;
1306         }
1307       }
1308     }
1309   }
1310
1311   unsigned ImpUse = getReMatImplicitUse(li, MI);
1312   if (ImpUse) {
1313     const LiveInterval &ImpLi = getInterval(ImpUse);
1314     for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
1315            re = mri_->use_end(); ri != re; ++ri) {
1316       MachineInstr *UseMI = &*ri;
1317       unsigned UseIdx = getInstructionIndex(UseMI);
1318       if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
1319         continue;
1320       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
1321         return false;
1322     }
1323
1324     // If a register operand of the re-materialized instruction is going to
1325     // be spilled next, then it's not legal to re-materialize this instruction.
1326     for (unsigned i = 0, e = SpillIs.size(); i != e; ++i)
1327       if (ImpUse == SpillIs[i]->reg)
1328         return false;
1329   }
1330   return true;
1331 }
1332
1333 /// isReMaterializable - Returns true if the definition MI of the specified
1334 /// val# of the specified interval is re-materializable.
1335 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1336                                        const VNInfo *ValNo, MachineInstr *MI) {
1337   SmallVector<LiveInterval*, 4> Dummy1;
1338   bool Dummy2;
1339   return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2);
1340 }
1341
1342 /// isReMaterializable - Returns true if every definition of MI of every
1343 /// val# of the specified interval is re-materializable.
1344 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1345                                        SmallVectorImpl<LiveInterval*> &SpillIs,
1346                                        bool &isLoad) {
1347   isLoad = false;
1348   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1349        i != e; ++i) {
1350     const VNInfo *VNI = *i;
1351     if (VNI->isUnused())
1352       continue; // Dead val#.
1353     // Is the def for the val# rematerializable?
1354     if (!VNI->isDefAccurate())
1355       return false;
1356     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1357     bool DefIsLoad = false;
1358     if (!ReMatDefMI ||
1359         !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1360       return false;
1361     isLoad |= DefIsLoad;
1362   }
1363   return true;
1364 }
1365
1366 /// FilterFoldedOps - Filter out two-address use operands. Return
1367 /// true if it finds any issue with the operands that ought to prevent
1368 /// folding.
1369 static bool FilterFoldedOps(MachineInstr *MI,
1370                             SmallVector<unsigned, 2> &Ops,
1371                             unsigned &MRInfo,
1372                             SmallVector<unsigned, 2> &FoldOps) {
1373   MRInfo = 0;
1374   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1375     unsigned OpIdx = Ops[i];
1376     MachineOperand &MO = MI->getOperand(OpIdx);
1377     // FIXME: fold subreg use.
1378     if (MO.getSubReg())
1379       return true;
1380     if (MO.isDef())
1381       MRInfo |= (unsigned)VirtRegMap::isMod;
1382     else {
1383       // Filter out two-address use operand(s).
1384       if (MI->isRegTiedToDefOperand(OpIdx)) {
1385         MRInfo = VirtRegMap::isModRef;
1386         continue;
1387       }
1388       MRInfo |= (unsigned)VirtRegMap::isRef;
1389     }
1390     FoldOps.push_back(OpIdx);
1391   }
1392   return false;
1393 }
1394
1395
1396 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1397 /// slot / to reg or any rematerialized load into ith operand of specified
1398 /// MI. If it is successul, MI is updated with the newly created MI and
1399 /// returns true.
1400 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1401                                          VirtRegMap &vrm, MachineInstr *DefMI,
1402                                          unsigned InstrIdx,
1403                                          SmallVector<unsigned, 2> &Ops,
1404                                          bool isSS, int Slot, unsigned Reg) {
1405   // If it is an implicit def instruction, just delete it.
1406   if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
1407     RemoveMachineInstrFromMaps(MI);
1408     vrm.RemoveMachineInstrFromMaps(MI);
1409     MI->eraseFromParent();
1410     ++numFolds;
1411     return true;
1412   }
1413
1414   // Filter the list of operand indexes that are to be folded. Abort if
1415   // any operand will prevent folding.
1416   unsigned MRInfo = 0;
1417   SmallVector<unsigned, 2> FoldOps;
1418   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1419     return false;
1420
1421   // The only time it's safe to fold into a two address instruction is when
1422   // it's folding reload and spill from / into a spill stack slot.
1423   if (DefMI && (MRInfo & VirtRegMap::isMod))
1424     return false;
1425
1426   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
1427                            : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
1428   if (fmi) {
1429     // Remember this instruction uses the spill slot.
1430     if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1431
1432     // Attempt to fold the memory reference into the instruction. If
1433     // we can do this, we don't need to insert spill code.
1434     MachineBasicBlock &MBB = *MI->getParent();
1435     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
1436       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
1437     vrm.transferSpillPts(MI, fmi);
1438     vrm.transferRestorePts(MI, fmi);
1439     vrm.transferEmergencySpills(MI, fmi);
1440     mi2iMap_.erase(MI);
1441     i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
1442     mi2iMap_[fmi] = InstrIdx;
1443     MI = MBB.insert(MBB.erase(MI), fmi);
1444     ++numFolds;
1445     return true;
1446   }
1447   return false;
1448 }
1449
1450 /// canFoldMemoryOperand - Returns true if the specified load / store
1451 /// folding is possible.
1452 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
1453                                          SmallVector<unsigned, 2> &Ops,
1454                                          bool ReMat) const {
1455   // Filter the list of operand indexes that are to be folded. Abort if
1456   // any operand will prevent folding.
1457   unsigned MRInfo = 0;
1458   SmallVector<unsigned, 2> FoldOps;
1459   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1460     return false;
1461
1462   // It's only legal to remat for a use, not a def.
1463   if (ReMat && (MRInfo & VirtRegMap::isMod))
1464     return false;
1465
1466   return tii_->canFoldMemoryOperand(MI, FoldOps);
1467 }
1468
1469 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
1470   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
1471   for (LiveInterval::Ranges::const_iterator
1472          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1473     std::vector<IdxMBBPair>::const_iterator II =
1474       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
1475     if (II == Idx2MBBMap.end())
1476       continue;
1477     if (I->end > II->first)  // crossing a MBB.
1478       return false;
1479     MBBs.insert(II->second);
1480     if (MBBs.size() > 1)
1481       return false;
1482   }
1483   return true;
1484 }
1485
1486 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1487 /// interval on to-be re-materialized operands of MI) with new register.
1488 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1489                                        MachineInstr *MI, unsigned NewVReg,
1490                                        VirtRegMap &vrm) {
1491   // There is an implicit use. That means one of the other operand is
1492   // being remat'ed and the remat'ed instruction has li.reg as an
1493   // use operand. Make sure we rewrite that as well.
1494   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1495     MachineOperand &MO = MI->getOperand(i);
1496     if (!MO.isReg())
1497       continue;
1498     unsigned Reg = MO.getReg();
1499     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
1500       continue;
1501     if (!vrm.isReMaterialized(Reg))
1502       continue;
1503     MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
1504     MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1505     if (UseMO)
1506       UseMO->setReg(NewVReg);
1507   }
1508 }
1509
1510 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1511 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
1512 bool LiveIntervals::
1513 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
1514                  bool TrySplit, unsigned index, unsigned end,  MachineInstr *MI,
1515                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1516                  unsigned Slot, int LdSlot,
1517                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1518                  VirtRegMap &vrm,
1519                  const TargetRegisterClass* rc,
1520                  SmallVector<int, 4> &ReMatIds,
1521                  const MachineLoopInfo *loopInfo,
1522                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
1523                  DenseMap<unsigned,unsigned> &MBBVRegsMap,
1524                  std::vector<LiveInterval*> &NewLIs) {
1525   bool CanFold = false;
1526  RestartInstruction:
1527   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1528     MachineOperand& mop = MI->getOperand(i);
1529     if (!mop.isReg())
1530       continue;
1531     unsigned Reg = mop.getReg();
1532     unsigned RegI = Reg;
1533     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
1534       continue;
1535     if (Reg != li.reg)
1536       continue;
1537
1538     bool TryFold = !DefIsReMat;
1539     bool FoldSS = true; // Default behavior unless it's a remat.
1540     int FoldSlot = Slot;
1541     if (DefIsReMat) {
1542       // If this is the rematerializable definition MI itself and
1543       // all of its uses are rematerialized, simply delete it.
1544       if (MI == ReMatOrigDefMI && CanDelete) {
1545         DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: "
1546                      << MI << '\n');
1547         RemoveMachineInstrFromMaps(MI);
1548         vrm.RemoveMachineInstrFromMaps(MI);
1549         MI->eraseFromParent();
1550         break;
1551       }
1552
1553       // If def for this use can't be rematerialized, then try folding.
1554       // If def is rematerializable and it's a load, also try folding.
1555       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1556       if (isLoad) {
1557         // Try fold loads (from stack slot, constant pool, etc.) into uses.
1558         FoldSS = isLoadSS;
1559         FoldSlot = LdSlot;
1560       }
1561     }
1562
1563     // Scan all of the operands of this instruction rewriting operands
1564     // to use NewVReg instead of li.reg as appropriate.  We do this for
1565     // two reasons:
1566     //
1567     //   1. If the instr reads the same spilled vreg multiple times, we
1568     //      want to reuse the NewVReg.
1569     //   2. If the instr is a two-addr instruction, we are required to
1570     //      keep the src/dst regs pinned.
1571     //
1572     // Keep track of whether we replace a use and/or def so that we can
1573     // create the spill interval with the appropriate range.
1574
1575     HasUse = mop.isUse();
1576     HasDef = mop.isDef();
1577     SmallVector<unsigned, 2> Ops;
1578     Ops.push_back(i);
1579     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
1580       const MachineOperand &MOj = MI->getOperand(j);
1581       if (!MOj.isReg())
1582         continue;
1583       unsigned RegJ = MOj.getReg();
1584       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
1585         continue;
1586       if (RegJ == RegI) {
1587         Ops.push_back(j);
1588         if (!MOj.isUndef()) {
1589           HasUse |= MOj.isUse();
1590           HasDef |= MOj.isDef();
1591         }
1592       }
1593     }
1594
1595     // Create a new virtual register for the spill interval.
1596     // Create the new register now so we can map the fold instruction
1597     // to the new register so when it is unfolded we get the correct
1598     // answer.
1599     bool CreatedNewVReg = false;
1600     if (NewVReg == 0) {
1601       NewVReg = mri_->createVirtualRegister(rc);
1602       vrm.grow();
1603       CreatedNewVReg = true;
1604     }
1605
1606     if (!TryFold)
1607       CanFold = false;
1608     else {
1609       // Do not fold load / store here if we are splitting. We'll find an
1610       // optimal point to insert a load / store later.
1611       if (!TrySplit) {
1612         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1613                                  Ops, FoldSS, FoldSlot, NewVReg)) {
1614           // Folding the load/store can completely change the instruction in
1615           // unpredictable ways, rescan it from the beginning.
1616
1617           if (FoldSS) {
1618             // We need to give the new vreg the same stack slot as the
1619             // spilled interval.
1620             vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1621           }
1622
1623           HasUse = false;
1624           HasDef = false;
1625           CanFold = false;
1626           if (isNotInMIMap(MI))
1627             break;
1628           goto RestartInstruction;
1629         }
1630       } else {
1631         // We'll try to fold it later if it's profitable.
1632         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1633       }
1634     }
1635
1636     mop.setReg(NewVReg);
1637     if (mop.isImplicit())
1638       rewriteImplicitOps(li, MI, NewVReg, vrm);
1639
1640     // Reuse NewVReg for other reads.
1641     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1642       MachineOperand &mopj = MI->getOperand(Ops[j]);
1643       mopj.setReg(NewVReg);
1644       if (mopj.isImplicit())
1645         rewriteImplicitOps(li, MI, NewVReg, vrm);
1646     }
1647
1648     if (CreatedNewVReg) {
1649       if (DefIsReMat) {
1650         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
1651         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1652           // Each valnum may have its own remat id.
1653           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1654         } else {
1655           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1656         }
1657         if (!CanDelete || (HasUse && HasDef)) {
1658           // If this is a two-addr instruction then its use operands are
1659           // rematerializable but its def is not. It should be assigned a
1660           // stack slot.
1661           vrm.assignVirt2StackSlot(NewVReg, Slot);
1662         }
1663       } else {
1664         vrm.assignVirt2StackSlot(NewVReg, Slot);
1665       }
1666     } else if (HasUse && HasDef &&
1667                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1668       // If this interval hasn't been assigned a stack slot (because earlier
1669       // def is a deleted remat def), do it now.
1670       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1671       vrm.assignVirt2StackSlot(NewVReg, Slot);
1672     }
1673
1674     // Re-matting an instruction with virtual register use. Add the
1675     // register as an implicit use on the use MI.
1676     if (DefIsReMat && ImpUse)
1677       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1678
1679     // Create a new register interval for this spill / remat.
1680     LiveInterval &nI = getOrCreateInterval(NewVReg);
1681     if (CreatedNewVReg) {
1682       NewLIs.push_back(&nI);
1683       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1684       if (TrySplit)
1685         vrm.setIsSplitFromReg(NewVReg, li.reg);
1686     }
1687
1688     if (HasUse) {
1689       if (CreatedNewVReg) {
1690         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1691                      nI.getNextValue(0, 0, false, VNInfoAllocator));
1692         DEBUG(errs() << " +" << LR);
1693         nI.addRange(LR);
1694       } else {
1695         // Extend the split live interval to this def / use.
1696         unsigned End = getUseIndex(index)+1;
1697         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1698                      nI.getValNumInfo(nI.getNumValNums()-1));
1699         DEBUG(errs() << " +" << LR);
1700         nI.addRange(LR);
1701       }
1702     }
1703     if (HasDef) {
1704       LiveRange LR(getDefIndex(index), getStoreIndex(index),
1705                    nI.getNextValue(0, 0, false, VNInfoAllocator));
1706       DEBUG(errs() << " +" << LR);
1707       nI.addRange(LR);
1708     }
1709
1710     DEBUG({
1711         errs() << "\t\t\t\tAdded new interval: ";
1712         nI.print(errs(), tri_);
1713         errs() << '\n';
1714       });
1715   }
1716   return CanFold;
1717 }
1718 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1719                                    const VNInfo *VNI,
1720                                    MachineBasicBlock *MBB, unsigned Idx) const {
1721   unsigned End = getMBBEndIdx(MBB);
1722   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1723     if (VNI->kills[j].isPHIKill)
1724       continue;
1725
1726     unsigned KillIdx = VNI->kills[j].killIdx;
1727     if (KillIdx > Idx && KillIdx < End)
1728       return true;
1729   }
1730   return false;
1731 }
1732
1733 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1734 /// during spilling.
1735 namespace {
1736   struct RewriteInfo {
1737     unsigned Index;
1738     MachineInstr *MI;
1739     bool HasUse;
1740     bool HasDef;
1741     RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1742       : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1743   };
1744
1745   struct RewriteInfoCompare {
1746     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1747       return LHS.Index < RHS.Index;
1748     }
1749   };
1750 }
1751
1752 void LiveIntervals::
1753 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1754                     LiveInterval::Ranges::const_iterator &I,
1755                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1756                     unsigned Slot, int LdSlot,
1757                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1758                     VirtRegMap &vrm,
1759                     const TargetRegisterClass* rc,
1760                     SmallVector<int, 4> &ReMatIds,
1761                     const MachineLoopInfo *loopInfo,
1762                     BitVector &SpillMBBs,
1763                     DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
1764                     BitVector &RestoreMBBs,
1765                     DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1766                     DenseMap<unsigned,unsigned> &MBBVRegsMap,
1767                     std::vector<LiveInterval*> &NewLIs) {
1768   bool AllCanFold = true;
1769   unsigned NewVReg = 0;
1770   unsigned start = getBaseIndex(I->start);
1771   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1772
1773   // First collect all the def / use in this live range that will be rewritten.
1774   // Make sure they are sorted according to instruction index.
1775   std::vector<RewriteInfo> RewriteMIs;
1776   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1777          re = mri_->reg_end(); ri != re; ) {
1778     MachineInstr *MI = &*ri;
1779     MachineOperand &O = ri.getOperand();
1780     ++ri;
1781     assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
1782     unsigned index = getInstructionIndex(MI);
1783     if (index < start || index >= end)
1784       continue;
1785
1786     if (O.isUndef())
1787       // Must be defined by an implicit def. It should not be spilled. Note,
1788       // this is for correctness reason. e.g.
1789       // 8   %reg1024<def> = IMPLICIT_DEF
1790       // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1791       // The live range [12, 14) are not part of the r1024 live interval since
1792       // it's defined by an implicit def. It will not conflicts with live
1793       // interval of r1025. Now suppose both registers are spilled, you can
1794       // easily see a situation where both registers are reloaded before
1795       // the INSERT_SUBREG and both target registers that would overlap.
1796       continue;
1797     RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1798   }
1799   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1800
1801   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1802   // Now rewrite the defs and uses.
1803   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1804     RewriteInfo &rwi = RewriteMIs[i];
1805     ++i;
1806     unsigned index = rwi.Index;
1807     bool MIHasUse = rwi.HasUse;
1808     bool MIHasDef = rwi.HasDef;
1809     MachineInstr *MI = rwi.MI;
1810     // If MI def and/or use the same register multiple times, then there
1811     // are multiple entries.
1812     unsigned NumUses = MIHasUse;
1813     while (i != e && RewriteMIs[i].MI == MI) {
1814       assert(RewriteMIs[i].Index == index);
1815       bool isUse = RewriteMIs[i].HasUse;
1816       if (isUse) ++NumUses;
1817       MIHasUse |= isUse;
1818       MIHasDef |= RewriteMIs[i].HasDef;
1819       ++i;
1820     }
1821     MachineBasicBlock *MBB = MI->getParent();
1822
1823     if (ImpUse && MI != ReMatDefMI) {
1824       // Re-matting an instruction with virtual register use. Update the
1825       // register interval's spill weight to HUGE_VALF to prevent it from
1826       // being spilled.
1827       LiveInterval &ImpLi = getInterval(ImpUse);
1828       ImpLi.weight = HUGE_VALF;
1829     }
1830
1831     unsigned MBBId = MBB->getNumber();
1832     unsigned ThisVReg = 0;
1833     if (TrySplit) {
1834       DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
1835       if (NVI != MBBVRegsMap.end()) {
1836         ThisVReg = NVI->second;
1837         // One common case:
1838         // x = use
1839         // ...
1840         // ...
1841         // def = ...
1842         //     = use
1843         // It's better to start a new interval to avoid artifically
1844         // extend the new interval.
1845         if (MIHasDef && !MIHasUse) {
1846           MBBVRegsMap.erase(MBB->getNumber());
1847           ThisVReg = 0;
1848         }
1849       }
1850     }
1851
1852     bool IsNew = ThisVReg == 0;
1853     if (IsNew) {
1854       // This ends the previous live interval. If all of its def / use
1855       // can be folded, give it a low spill weight.
1856       if (NewVReg && TrySplit && AllCanFold) {
1857         LiveInterval &nI = getOrCreateInterval(NewVReg);
1858         nI.weight /= 10.0F;
1859       }
1860       AllCanFold = true;
1861     }
1862     NewVReg = ThisVReg;
1863
1864     bool HasDef = false;
1865     bool HasUse = false;
1866     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1867                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1868                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1869                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1870                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1871     if (!HasDef && !HasUse)
1872       continue;
1873
1874     AllCanFold &= CanFold;
1875
1876     // Update weight of spill interval.
1877     LiveInterval &nI = getOrCreateInterval(NewVReg);
1878     if (!TrySplit) {
1879       // The spill weight is now infinity as it cannot be spilled again.
1880       nI.weight = HUGE_VALF;
1881       continue;
1882     }
1883
1884     // Keep track of the last def and first use in each MBB.
1885     if (HasDef) {
1886       if (MI != ReMatOrigDefMI || !CanDelete) {
1887         bool HasKill = false;
1888         if (!HasUse)
1889           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1890         else {
1891           // If this is a two-address code, then this index starts a new VNInfo.
1892           const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
1893           if (VNI)
1894             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1895         }
1896         DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1897           SpillIdxes.find(MBBId);
1898         if (!HasKill) {
1899           if (SII == SpillIdxes.end()) {
1900             std::vector<SRInfo> S;
1901             S.push_back(SRInfo(index, NewVReg, true));
1902             SpillIdxes.insert(std::make_pair(MBBId, S));
1903           } else if (SII->second.back().vreg != NewVReg) {
1904             SII->second.push_back(SRInfo(index, NewVReg, true));
1905           } else if ((int)index > SII->second.back().index) {
1906             // If there is an earlier def and this is a two-address
1907             // instruction, then it's not possible to fold the store (which
1908             // would also fold the load).
1909             SRInfo &Info = SII->second.back();
1910             Info.index = index;
1911             Info.canFold = !HasUse;
1912           }
1913           SpillMBBs.set(MBBId);
1914         } else if (SII != SpillIdxes.end() &&
1915                    SII->second.back().vreg == NewVReg &&
1916                    (int)index > SII->second.back().index) {
1917           // There is an earlier def that's not killed (must be two-address).
1918           // The spill is no longer needed.
1919           SII->second.pop_back();
1920           if (SII->second.empty()) {
1921             SpillIdxes.erase(MBBId);
1922             SpillMBBs.reset(MBBId);
1923           }
1924         }
1925       }
1926     }
1927
1928     if (HasUse) {
1929       DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1930         SpillIdxes.find(MBBId);
1931       if (SII != SpillIdxes.end() &&
1932           SII->second.back().vreg == NewVReg &&
1933           (int)index > SII->second.back().index)
1934         // Use(s) following the last def, it's not safe to fold the spill.
1935         SII->second.back().canFold = false;
1936       DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
1937         RestoreIdxes.find(MBBId);
1938       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1939         // If we are splitting live intervals, only fold if it's the first
1940         // use and there isn't another use later in the MBB.
1941         RII->second.back().canFold = false;
1942       else if (IsNew) {
1943         // Only need a reload if there isn't an earlier def / use.
1944         if (RII == RestoreIdxes.end()) {
1945           std::vector<SRInfo> Infos;
1946           Infos.push_back(SRInfo(index, NewVReg, true));
1947           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1948         } else {
1949           RII->second.push_back(SRInfo(index, NewVReg, true));
1950         }
1951         RestoreMBBs.set(MBBId);
1952       }
1953     }
1954
1955     // Update spill weight.
1956     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1957     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1958   }
1959
1960   if (NewVReg && TrySplit && AllCanFold) {
1961     // If all of its def / use can be folded, give it a low spill weight.
1962     LiveInterval &nI = getOrCreateInterval(NewVReg);
1963     nI.weight /= 10.0F;
1964   }
1965 }
1966
1967 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1968                         BitVector &RestoreMBBs,
1969                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1970   if (!RestoreMBBs[Id])
1971     return false;
1972   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1973   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1974     if (Restores[i].index == index &&
1975         Restores[i].vreg == vr &&
1976         Restores[i].canFold)
1977       return true;
1978   return false;
1979 }
1980
1981 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1982                         BitVector &RestoreMBBs,
1983                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1984   if (!RestoreMBBs[Id])
1985     return;
1986   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1987   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1988     if (Restores[i].index == index && Restores[i].vreg)
1989       Restores[i].index = -1;
1990 }
1991
1992 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1993 /// spilled and create empty intervals for their uses.
1994 void
1995 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1996                                     const TargetRegisterClass* rc,
1997                                     std::vector<LiveInterval*> &NewLIs) {
1998   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1999          re = mri_->reg_end(); ri != re; ) {
2000     MachineOperand &O = ri.getOperand();
2001     MachineInstr *MI = &*ri;
2002     ++ri;
2003     if (O.isDef()) {
2004       assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
2005              "Register def was not rewritten?");
2006       RemoveMachineInstrFromMaps(MI);
2007       vrm.RemoveMachineInstrFromMaps(MI);
2008       MI->eraseFromParent();
2009     } else {
2010       // This must be an use of an implicit_def so it's not part of the live
2011       // interval. Create a new empty live interval for it.
2012       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
2013       unsigned NewVReg = mri_->createVirtualRegister(rc);
2014       vrm.grow();
2015       vrm.setIsImplicitlyDefined(NewVReg);
2016       NewLIs.push_back(&getOrCreateInterval(NewVReg));
2017       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2018         MachineOperand &MO = MI->getOperand(i);
2019         if (MO.isReg() && MO.getReg() == li.reg) {
2020           MO.setReg(NewVReg);
2021           MO.setIsUndef();
2022         }
2023       }
2024     }
2025   }
2026 }
2027
2028 std::vector<LiveInterval*> LiveIntervals::
2029 addIntervalsForSpillsFast(const LiveInterval &li,
2030                           const MachineLoopInfo *loopInfo,
2031                           VirtRegMap &vrm) {
2032   unsigned slot = vrm.assignVirt2StackSlot(li.reg);
2033
2034   std::vector<LiveInterval*> added;
2035
2036   assert(li.weight != HUGE_VALF &&
2037          "attempt to spill already spilled interval!");
2038
2039   DEBUG({
2040       errs() << "\t\t\t\tadding intervals for spills for interval: ";
2041       li.dump();
2042       errs() << '\n';
2043     });
2044
2045   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
2046
2047   MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg);
2048   while (RI != mri_->reg_end()) {
2049     MachineInstr* MI = &*RI;
2050
2051     SmallVector<unsigned, 2> Indices;
2052     bool HasUse = false;
2053     bool HasDef = false;
2054
2055     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
2056       MachineOperand& mop = MI->getOperand(i);
2057       if (!mop.isReg() || mop.getReg() != li.reg) continue;
2058
2059       HasUse |= MI->getOperand(i).isUse();
2060       HasDef |= MI->getOperand(i).isDef();
2061
2062       Indices.push_back(i);
2063     }
2064
2065     if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI),
2066                               Indices, true, slot, li.reg)) {
2067       unsigned NewVReg = mri_->createVirtualRegister(rc);
2068       vrm.grow();
2069       vrm.assignVirt2StackSlot(NewVReg, slot);
2070
2071       // create a new register for this spill
2072       LiveInterval &nI = getOrCreateInterval(NewVReg);
2073
2074       // the spill weight is now infinity as it
2075       // cannot be spilled again
2076       nI.weight = HUGE_VALF;
2077
2078       // Rewrite register operands to use the new vreg.
2079       for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(),
2080            E = Indices.end(); I != E; ++I) {
2081         MI->getOperand(*I).setReg(NewVReg);
2082
2083         if (MI->getOperand(*I).isUse())
2084           MI->getOperand(*I).setIsKill(true);
2085       }
2086
2087       // Fill in  the new live interval.
2088       unsigned index = getInstructionIndex(MI);
2089       if (HasUse) {
2090         LiveRange LR(getLoadIndex(index), getUseIndex(index),
2091                      nI.getNextValue(0, 0, false, getVNInfoAllocator()));
2092         DEBUG(errs() << " +" << LR);
2093         nI.addRange(LR);
2094         vrm.addRestorePoint(NewVReg, MI);
2095       }
2096       if (HasDef) {
2097         LiveRange LR(getDefIndex(index), getStoreIndex(index),
2098                      nI.getNextValue(0, 0, false, getVNInfoAllocator()));
2099         DEBUG(errs() << " +" << LR);
2100         nI.addRange(LR);
2101         vrm.addSpillPoint(NewVReg, true, MI);
2102       }
2103
2104       added.push_back(&nI);
2105
2106       DEBUG({
2107           errs() << "\t\t\t\tadded new interval: ";
2108           nI.dump();
2109           errs() << '\n';
2110         });
2111     }
2112
2113
2114     RI = mri_->reg_begin(li.reg);
2115   }
2116
2117   return added;
2118 }
2119
2120 std::vector<LiveInterval*> LiveIntervals::
2121 addIntervalsForSpills(const LiveInterval &li,
2122                       SmallVectorImpl<LiveInterval*> &SpillIs,
2123                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
2124
2125   if (EnableFastSpilling)
2126     return addIntervalsForSpillsFast(li, loopInfo, vrm);
2127
2128   assert(li.weight != HUGE_VALF &&
2129          "attempt to spill already spilled interval!");
2130
2131   DEBUG({
2132       errs() << "\t\t\t\tadding intervals for spills for interval: ";
2133       li.print(errs(), tri_);
2134       errs() << '\n';
2135     });
2136
2137   // Each bit specify whether a spill is required in the MBB.
2138   BitVector SpillMBBs(mf_->getNumBlockIDs());
2139   DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
2140   BitVector RestoreMBBs(mf_->getNumBlockIDs());
2141   DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
2142   DenseMap<unsigned,unsigned> MBBVRegsMap;
2143   std::vector<LiveInterval*> NewLIs;
2144   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
2145
2146   unsigned NumValNums = li.getNumValNums();
2147   SmallVector<MachineInstr*, 4> ReMatDefs;
2148   ReMatDefs.resize(NumValNums, NULL);
2149   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
2150   ReMatOrigDefs.resize(NumValNums, NULL);
2151   SmallVector<int, 4> ReMatIds;
2152   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
2153   BitVector ReMatDelete(NumValNums);
2154   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
2155
2156   // Spilling a split live interval. It cannot be split any further. Also,
2157   // it's also guaranteed to be a single val# / range interval.
2158   if (vrm.getPreSplitReg(li.reg)) {
2159     vrm.setIsSplitFromReg(li.reg, 0);
2160     // Unset the split kill marker on the last use.
2161     unsigned KillIdx = vrm.getKillPoint(li.reg);
2162     if (KillIdx) {
2163       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
2164       assert(KillMI && "Last use disappeared?");
2165       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
2166       assert(KillOp != -1 && "Last use disappeared?");
2167       KillMI->getOperand(KillOp).setIsKill(false);
2168     }
2169     vrm.removeKillPoint(li.reg);
2170     bool DefIsReMat = vrm.isReMaterialized(li.reg);
2171     Slot = vrm.getStackSlot(li.reg);
2172     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
2173     MachineInstr *ReMatDefMI = DefIsReMat ?
2174       vrm.getReMaterializedMI(li.reg) : NULL;
2175     int LdSlot = 0;
2176     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2177     bool isLoad = isLoadSS ||
2178       (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
2179     bool IsFirstRange = true;
2180     for (LiveInterval::Ranges::const_iterator
2181            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
2182       // If this is a split live interval with multiple ranges, it means there
2183       // are two-address instructions that re-defined the value. Only the
2184       // first def can be rematerialized!
2185       if (IsFirstRange) {
2186         // Note ReMatOrigDefMI has already been deleted.
2187         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
2188                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
2189                              false, vrm, rc, ReMatIds, loopInfo,
2190                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
2191                              MBBVRegsMap, NewLIs);
2192       } else {
2193         rewriteInstructionsForSpills(li, false, I, NULL, 0,
2194                              Slot, 0, false, false, false,
2195                              false, vrm, rc, ReMatIds, loopInfo,
2196                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
2197                              MBBVRegsMap, NewLIs);
2198       }
2199       IsFirstRange = false;
2200     }
2201
2202     handleSpilledImpDefs(li, vrm, rc, NewLIs);
2203     return NewLIs;
2204   }
2205
2206   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
2207   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
2208     TrySplit = false;
2209   if (TrySplit)
2210     ++numSplits;
2211   bool NeedStackSlot = false;
2212   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
2213        i != e; ++i) {
2214     const VNInfo *VNI = *i;
2215     unsigned VN = VNI->id;
2216     if (VNI->isUnused())
2217       continue; // Dead val#.
2218     // Is the def for the val# rematerializable?
2219     MachineInstr *ReMatDefMI = VNI->isDefAccurate()
2220       ? getInstructionFromIndex(VNI->def) : 0;
2221     bool dummy;
2222     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
2223       // Remember how to remat the def of this val#.
2224       ReMatOrigDefs[VN] = ReMatDefMI;
2225       // Original def may be modified so we have to make a copy here.
2226       MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
2227       ClonedMIs.push_back(Clone);
2228       ReMatDefs[VN] = Clone;
2229
2230       bool CanDelete = true;
2231       if (VNI->hasPHIKill()) {
2232         // A kill is a phi node, not all of its uses can be rematerialized.
2233         // It must not be deleted.
2234         CanDelete = false;
2235         // Need a stack slot if there is any live range where uses cannot be
2236         // rematerialized.
2237         NeedStackSlot = true;
2238       }
2239       if (CanDelete)
2240         ReMatDelete.set(VN);
2241     } else {
2242       // Need a stack slot if there is any live range where uses cannot be
2243       // rematerialized.
2244       NeedStackSlot = true;
2245     }
2246   }
2247
2248   // One stack slot per live interval.
2249   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
2250     if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
2251       Slot = vrm.assignVirt2StackSlot(li.reg);
2252
2253     // This case only occurs when the prealloc splitter has already assigned
2254     // a stack slot to this vreg.
2255     else
2256       Slot = vrm.getStackSlot(li.reg);
2257   }
2258
2259   // Create new intervals and rewrite defs and uses.
2260   for (LiveInterval::Ranges::const_iterator
2261          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
2262     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
2263     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
2264     bool DefIsReMat = ReMatDefMI != NULL;
2265     bool CanDelete = ReMatDelete[I->valno->id];
2266     int LdSlot = 0;
2267     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2268     bool isLoad = isLoadSS ||
2269       (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
2270     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
2271                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
2272                                CanDelete, vrm, rc, ReMatIds, loopInfo,
2273                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
2274                                MBBVRegsMap, NewLIs);
2275   }
2276
2277   // Insert spills / restores if we are splitting.
2278   if (!TrySplit) {
2279     handleSpilledImpDefs(li, vrm, rc, NewLIs);
2280     return NewLIs;
2281   }
2282
2283   SmallPtrSet<LiveInterval*, 4> AddedKill;
2284   SmallVector<unsigned, 2> Ops;
2285   if (NeedStackSlot) {
2286     int Id = SpillMBBs.find_first();
2287     while (Id != -1) {
2288       std::vector<SRInfo> &spills = SpillIdxes[Id];
2289       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
2290         int index = spills[i].index;
2291         unsigned VReg = spills[i].vreg;
2292         LiveInterval &nI = getOrCreateInterval(VReg);
2293         bool isReMat = vrm.isReMaterialized(VReg);
2294         MachineInstr *MI = getInstructionFromIndex(index);
2295         bool CanFold = false;
2296         bool FoundUse = false;
2297         Ops.clear();
2298         if (spills[i].canFold) {
2299           CanFold = true;
2300           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
2301             MachineOperand &MO = MI->getOperand(j);
2302             if (!MO.isReg() || MO.getReg() != VReg)
2303               continue;
2304
2305             Ops.push_back(j);
2306             if (MO.isDef())
2307               continue;
2308             if (isReMat ||
2309                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
2310                                                 RestoreMBBs, RestoreIdxes))) {
2311               // MI has two-address uses of the same register. If the use
2312               // isn't the first and only use in the BB, then we can't fold
2313               // it. FIXME: Move this to rewriteInstructionsForSpills.
2314               CanFold = false;
2315               break;
2316             }
2317             FoundUse = true;
2318           }
2319         }
2320         // Fold the store into the def if possible.
2321         bool Folded = false;
2322         if (CanFold && !Ops.empty()) {
2323           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
2324             Folded = true;
2325             if (FoundUse) {
2326               // Also folded uses, do not issue a load.
2327               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
2328               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
2329             }
2330             nI.removeRange(getDefIndex(index), getStoreIndex(index));
2331           }
2332         }
2333
2334         // Otherwise tell the spiller to issue a spill.
2335         if (!Folded) {
2336           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
2337           bool isKill = LR->end == getStoreIndex(index);
2338           if (!MI->registerDefIsDead(nI.reg))
2339             // No need to spill a dead def.
2340             vrm.addSpillPoint(VReg, isKill, MI);
2341           if (isKill)
2342             AddedKill.insert(&nI);
2343         }
2344       }
2345       Id = SpillMBBs.find_next(Id);
2346     }
2347   }
2348
2349   int Id = RestoreMBBs.find_first();
2350   while (Id != -1) {
2351     std::vector<SRInfo> &restores = RestoreIdxes[Id];
2352     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
2353       int index = restores[i].index;
2354       if (index == -1)
2355         continue;
2356       unsigned VReg = restores[i].vreg;
2357       LiveInterval &nI = getOrCreateInterval(VReg);
2358       bool isReMat = vrm.isReMaterialized(VReg);
2359       MachineInstr *MI = getInstructionFromIndex(index);
2360       bool CanFold = false;
2361       Ops.clear();
2362       if (restores[i].canFold) {
2363         CanFold = true;
2364         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
2365           MachineOperand &MO = MI->getOperand(j);
2366           if (!MO.isReg() || MO.getReg() != VReg)
2367             continue;
2368
2369           if (MO.isDef()) {
2370             // If this restore were to be folded, it would have been folded
2371             // already.
2372             CanFold = false;
2373             break;
2374           }
2375           Ops.push_back(j);
2376         }
2377       }
2378
2379       // Fold the load into the use if possible.
2380       bool Folded = false;
2381       if (CanFold && !Ops.empty()) {
2382         if (!isReMat)
2383           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
2384         else {
2385           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
2386           int LdSlot = 0;
2387           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
2388           // If the rematerializable def is a load, also try to fold it.
2389           if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
2390             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
2391                                           Ops, isLoadSS, LdSlot, VReg);
2392           if (!Folded) {
2393             unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
2394             if (ImpUse) {
2395               // Re-matting an instruction with virtual register use. Add the
2396               // register as an implicit use on the use MI and update the register
2397               // interval's spill weight to HUGE_VALF to prevent it from being
2398               // spilled.
2399               LiveInterval &ImpLi = getInterval(ImpUse);
2400               ImpLi.weight = HUGE_VALF;
2401               MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
2402             }
2403           }
2404         }
2405       }
2406       // If folding is not possible / failed, then tell the spiller to issue a
2407       // load / rematerialization for us.
2408       if (Folded)
2409         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
2410       else
2411         vrm.addRestorePoint(VReg, MI);
2412     }
2413     Id = RestoreMBBs.find_next(Id);
2414   }
2415
2416   // Finalize intervals: add kills, finalize spill weights, and filter out
2417   // dead intervals.
2418   std::vector<LiveInterval*> RetNewLIs;
2419   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2420     LiveInterval *LI = NewLIs[i];
2421     if (!LI->empty()) {
2422       LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI);
2423       if (!AddedKill.count(LI)) {
2424         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
2425         unsigned LastUseIdx = getBaseIndex(LR->end);
2426         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
2427         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
2428         assert(UseIdx != -1);
2429         if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
2430           LastUse->getOperand(UseIdx).setIsKill();
2431           vrm.addKillPoint(LI->reg, LastUseIdx);
2432         }
2433       }
2434       RetNewLIs.push_back(LI);
2435     }
2436   }
2437
2438   handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
2439   return RetNewLIs;
2440 }
2441
2442 /// hasAllocatableSuperReg - Return true if the specified physical register has
2443 /// any super register that's allocatable.
2444 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2445   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2446     if (allocatableRegs_[*AS] && hasInterval(*AS))
2447       return true;
2448   return false;
2449 }
2450
2451 /// getRepresentativeReg - Find the largest super register of the specified
2452 /// physical register.
2453 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
2454   // Find the largest super-register that is allocatable.
2455   unsigned BestReg = Reg;
2456   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2457     unsigned SuperReg = *AS;
2458     if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2459       BestReg = SuperReg;
2460       break;
2461     }
2462   }
2463   return BestReg;
2464 }
2465
2466 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2467 /// specified interval that conflicts with the specified physical register.
2468 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2469                                                    unsigned PhysReg) const {
2470   unsigned NumConflicts = 0;
2471   const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2472   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2473          E = mri_->reg_end(); I != E; ++I) {
2474     MachineOperand &O = I.getOperand();
2475     MachineInstr *MI = O.getParent();
2476     unsigned Index = getInstructionIndex(MI);
2477     if (pli.liveAt(Index))
2478       ++NumConflicts;
2479   }
2480   return NumConflicts;
2481 }
2482
2483 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
2484 /// around all defs and uses of the specified interval. Return true if it
2485 /// was able to cut its interval.
2486 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
2487                                             unsigned PhysReg, VirtRegMap &vrm) {
2488   unsigned SpillReg = getRepresentativeReg(PhysReg);
2489
2490   for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2491     // If there are registers which alias PhysReg, but which are not a
2492     // sub-register of the chosen representative super register. Assert
2493     // since we can't handle it yet.
2494     assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
2495            tri_->isSuperRegister(*AS, SpillReg));
2496
2497   bool Cut = false;
2498   LiveInterval &pli = getInterval(SpillReg);
2499   SmallPtrSet<MachineInstr*, 8> SeenMIs;
2500   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2501          E = mri_->reg_end(); I != E; ++I) {
2502     MachineOperand &O = I.getOperand();
2503     MachineInstr *MI = O.getParent();
2504     if (SeenMIs.count(MI))
2505       continue;
2506     SeenMIs.insert(MI);
2507     unsigned Index = getInstructionIndex(MI);
2508     if (pli.liveAt(Index)) {
2509       vrm.addEmergencySpill(SpillReg, MI);
2510       unsigned StartIdx = getLoadIndex(Index);
2511       unsigned EndIdx = getStoreIndex(Index)+1;
2512       if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
2513         pli.removeRange(StartIdx, EndIdx);
2514         Cut = true;
2515       } else {
2516         std::string msg;
2517         raw_string_ostream Msg(msg);
2518         Msg << "Ran out of registers during register allocation!";
2519         if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
2520           Msg << "\nPlease check your inline asm statement for invalid "
2521                << "constraints:\n";
2522           MI->print(Msg, tm_);
2523         }
2524         llvm_report_error(Msg.str());
2525       }
2526       for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
2527         if (!hasInterval(*AS))
2528           continue;
2529         LiveInterval &spli = getInterval(*AS);
2530         if (spli.liveAt(Index))
2531           spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
2532       }
2533     }
2534   }
2535   return Cut;
2536 }
2537
2538 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
2539                                                   MachineInstr* startInst) {
2540   LiveInterval& Interval = getOrCreateInterval(reg);
2541   VNInfo* VN = Interval.getNextValue(
2542             getInstructionIndex(startInst) + InstrSlots::DEF,
2543             startInst, true, getVNInfoAllocator());
2544   VN->setHasPHIKill(true);
2545   VN->kills.push_back(
2546     VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true));
2547   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
2548                getMBBEndIdx(startInst->getParent()) + 1, VN);
2549   Interval.addRange(LR);
2550
2551   return LR;
2552 }
2553