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