lib/CodeGen/LiveIntervalAnalysis.cpp

   1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements 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/LoopInfo.h"
  23 #include "llvm/CodeGen/LiveVariables.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/Passes.h"
  27 #include "llvm/CodeGen/SSARegMap.h"
  28 #include "llvm/Target/MRegisterInfo.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include <algorithm>
  36 #include <cmath>
  37 using namespace llvm;
  38
  39 namespace {
  40   // Hidden options for help debugging.
  41   cl::opt<bool> DisableReMat("disable-rematerialization",
  42                               cl::init(false), cl::Hidden);
  43 }
  44
  45 STATISTIC(numIntervals, "Number of original intervals");
  46 STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
  47 STATISTIC(numFolded   , "Number of loads/stores folded into instructions");
  48
  49 char LiveIntervals::ID = 0;
  50 namespace {
  51   RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
  52 }
  53
  54 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  55   AU.addPreserved<LiveVariables>();
  56   AU.addRequired<LiveVariables>();
  57   AU.addPreservedID(PHIEliminationID);
  58   AU.addRequiredID(PHIEliminationID);
  59   AU.addRequiredID(TwoAddressInstructionPassID);
  60   AU.addRequired<LoopInfo>();
  61   MachineFunctionPass::getAnalysisUsage(AU);
  62 }
  63
  64 void LiveIntervals::releaseMemory() {
  65   mi2iMap_.clear();
  66   i2miMap_.clear();
  67   r2iMap_.clear();
  68   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
  69   VNInfoAllocator.Reset();
  70   for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
  71     delete ClonedMIs[i];
  72 }
  73
  74 /// runOnMachineFunction - Register allocate the whole function
  75 ///
  76 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
  77   mf_ = &fn;
  78   tm_ = &fn.getTarget();
  79   mri_ = tm_->getRegisterInfo();
  80   tii_ = tm_->getInstrInfo();
  81   lv_ = &getAnalysis<LiveVariables>();
  82   allocatableRegs_ = mri_->getAllocatableSet(fn);
  83
  84   // Number MachineInstrs and MachineBasicBlocks.
  85   // Initialize MBB indexes to a sentinal.
  86   MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
  87
  88   unsigned MIIndex = 0;
  89   for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
  90        MBB != E; ++MBB) {
  91     unsigned StartIdx = MIIndex;
  92
  93     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
  94          I != E; ++I) {
  95       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
  96       assert(inserted && "multiple MachineInstr -> index mappings");
  97       i2miMap_.push_back(I);
  98       MIIndex += InstrSlots::NUM;
  99     }
 100
 101     // Set the MBB2IdxMap entry for this MBB.
 102     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
 103   }
 104
 105   computeIntervals();
 106
 107   numIntervals += getNumIntervals();
 108
 109   DOUT << "********** INTERVALS **********\n";
 110   for (iterator I = begin(), E = end(); I != E; ++I) {
 111     I->second.print(DOUT, mri_);
 112     DOUT << "\n";
 113   }
 114
 115   numIntervalsAfter += getNumIntervals();
 116   DEBUG(dump());
 117   return true;
 118 }
 119
 120 /// print - Implement the dump method.
 121 void LiveIntervals::print(std::ostream &O, const Module* ) const {
 122   O << "********** INTERVALS **********\n";
 123   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 124     I->second.print(DOUT, mri_);
 125     DOUT << "\n";
 126   }
 127
 128   O << "********** MACHINEINSTRS **********\n";
 129   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 130        mbbi != mbbe; ++mbbi) {
 131     O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
 132     for (MachineBasicBlock::iterator mii = mbbi->begin(),
 133            mie = mbbi->end(); mii != mie; ++mii) {
 134       O << getInstructionIndex(mii) << '\t' << *mii;
 135     }
 136   }
 137 }
 138
 139 /// isReMaterializable - Returns true if the definition MI of the specified
 140 /// val# of the specified interval is re-materializable.
 141 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
 142                                        const VNInfo *ValNo, MachineInstr *MI) {
 143   if (DisableReMat)
 144     return false;
 145
 146   if (tii_->isTriviallyReMaterializable(MI))
 147     return true;
 148
 149   int FrameIdx = 0;
 150   if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
 151       !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
 152     return false;
 153
 154   // This is a load from fixed stack slot. It can be rematerialized unless it's
 155   // re-defined by a two-address instruction.
 156   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 157        i != e; ++i) {
 158     const VNInfo *VNI = *i;
 159     if (VNI == ValNo)
 160       continue;
 161     unsigned DefIdx = VNI->def;
 162     if (DefIdx == ~1U)
 163       continue; // Dead val#.
 164     MachineInstr *DefMI = (DefIdx == ~0u)
 165       ? NULL : getInstructionFromIndex(DefIdx);
 166     if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg))
 167       return false;
 168   }
 169   return true;
 170 }
 171
 172 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
 173 /// slot / to reg or any rematerialized load into ith operand of specified
 174 /// MI. If it is successul, MI is updated with the newly created MI and
 175 /// returns true.
 176 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
 177                                          MachineInstr *DefMI,
 178                                          unsigned index, unsigned i,
 179                                          bool isSS, int slot, unsigned reg) {
 180   MachineInstr *fmi = isSS
 181     ? mri_->foldMemoryOperand(MI, i, slot)
 182     : mri_->foldMemoryOperand(MI, i, DefMI);
 183   if (fmi) {
 184     // Attempt to fold the memory reference into the instruction. If
 185     // we can do this, we don't need to insert spill code.
 186     if (lv_)
 187       lv_->instructionChanged(MI, fmi);
 188     MachineBasicBlock &MBB = *MI->getParent();
 189     vrm.virtFolded(reg, MI, i, fmi);
 190     mi2iMap_.erase(MI);
 191     i2miMap_[index/InstrSlots::NUM] = fmi;
 192     mi2iMap_[fmi] = index;
 193     MI = MBB.insert(MBB.erase(MI), fmi);
 194     ++numFolded;
 195     return true;
 196   }
 197   return false;
 198 }
 199
 200 std::vector<LiveInterval*> LiveIntervals::
 201 addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
 202   // since this is called after the analysis is done we don't know if
 203   // LiveVariables is available
 204   lv_ = getAnalysisToUpdate<LiveVariables>();
 205
 206   std::vector<LiveInterval*> added;
 207
 208   assert(li.weight != HUGE_VALF &&
 209          "attempt to spill already spilled interval!");
 210
 211   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
 212   li.print(DOUT, mri_);
 213   DOUT << '\n';
 214
 215   SSARegMap *RegMap = mf_->getSSARegMap();
 216   const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
 217
 218   unsigned NumValNums = li.getNumValNums();
 219   SmallVector<MachineInstr*, 4> ReMatDefs;
 220   ReMatDefs.resize(NumValNums, NULL);
 221   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
 222   ReMatOrigDefs.resize(NumValNums, NULL);
 223   SmallVector<int, 4> ReMatIds;
 224   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
 225   BitVector ReMatDelete(NumValNums);
 226   unsigned slot = VirtRegMap::MAX_STACK_SLOT;
 227
 228   bool NeedStackSlot = false;
 229   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 230        i != e; ++i) {
 231     const VNInfo *VNI = *i;
 232     unsigned VN = VNI->id;
 233     unsigned DefIdx = VNI->def;
 234     if (DefIdx == ~1U)
 235       continue; // Dead val#.
 236     // Is the def for the val# rematerializable?
 237     MachineInstr *DefMI = (DefIdx == ~0u)
 238       ? NULL : getInstructionFromIndex(DefIdx);
 239     if (DefMI && isReMaterializable(li, VNI, DefMI)) {
 240       // Remember how to remat the def of this val#.
 241       ReMatOrigDefs[VN] = DefMI;
 242       // Original def may be modified so we have to make a copy here. vrm must
 243       // delete these!
 244       ReMatDefs[VN] = DefMI = DefMI->clone();
 245       vrm.setVirtIsReMaterialized(reg, DefMI);
 246
 247       bool CanDelete = true;
 248       for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
 249         unsigned KillIdx = VNI->kills[j];
 250         MachineInstr *KillMI = (KillIdx & 1)
 251           ? NULL : getInstructionFromIndex(KillIdx);
 252         // Kill is a phi node, not all of its uses can be rematerialized.
 253         // It must not be deleted.
 254         if (!KillMI) {
 255           CanDelete = false;
 256           // Need a stack slot if there is any live range where uses cannot be
 257           // rematerialized.
 258           NeedStackSlot = true;
 259           break;
 260         }
 261       }
 262
 263       if (CanDelete)
 264         ReMatDelete.set(VN);
 265     } else {
 266       // Need a stack slot if there is any live range where uses cannot be
 267       // rematerialized.
 268       NeedStackSlot = true;
 269     }
 270   }
 271
 272   // One stack slot per live interval.
 273   if (NeedStackSlot)
 274     slot = vrm.assignVirt2StackSlot(reg);
 275
 276   for (LiveInterval::Ranges::const_iterator
 277          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 278     MachineInstr *DefMI = ReMatDefs[I->valno->id];
 279     MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id];
 280     bool DefIsReMat = DefMI != NULL;
 281     bool CanDelete = ReMatDelete[I->valno->id];
 282     int LdSlot = 0;
 283     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot);
 284     bool isLoad = isLoadSS ||
 285       (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
 286     unsigned index = getBaseIndex(I->start);
 287     unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
 288     for (; index != end; index += InstrSlots::NUM) {
 289       // skip deleted instructions
 290       while (index != end && !getInstructionFromIndex(index))
 291         index += InstrSlots::NUM;
 292       if (index == end) break;
 293
 294       MachineInstr *MI = getInstructionFromIndex(index);
 295
 296     RestartInstruction:
 297       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 298         MachineOperand& mop = MI->getOperand(i);
 299         if (!mop.isRegister())
 300           continue;
 301         unsigned Reg = mop.getReg();
 302         if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
 303           continue;
 304         bool isSubReg = RegMap->isSubRegister(Reg);
 305         unsigned SubIdx = 0;
 306         if (isSubReg) {
 307           SubIdx = RegMap->getSubRegisterIndex(Reg);
 308           Reg = RegMap->getSuperRegister(Reg);
 309         }
 310         if (Reg != li.reg)
 311           continue;
 312
 313         bool TryFold = !DefIsReMat;
 314         bool FoldSS = true;
 315         int FoldSlot = slot;
 316         if (DefIsReMat) {
 317           // If this is the rematerializable definition MI itself and
 318           // all of its uses are rematerialized, simply delete it.
 319           if (MI == OrigDefMI && CanDelete) {
 320             RemoveMachineInstrFromMaps(MI);
 321             MI->eraseFromParent();
 322             break;
 323           }
 324
 325           // If def for this use can't be rematerialized, then try folding.
 326           TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad));
 327           if (isLoad) {
 328             // Try fold loads (from stack slot, constant pool, etc.) into uses.
 329             FoldSS = isLoadSS;
 330             FoldSlot = LdSlot;
 331           }
 332         }
 333
 334         // FIXME: fold subreg use
 335         if (!isSubReg && TryFold &&
 336             tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg))
 337           // Folding the load/store can completely change the instruction in
 338           // unpredictable ways, rescan it from the beginning.
 339           goto RestartInstruction;
 340
 341         // Create a new virtual register for the spill interval.
 342         unsigned NewVReg = RegMap->createVirtualRegister(rc);
 343         if (isSubReg)
 344           RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx);
 345
 346         // Scan all of the operands of this instruction rewriting operands
 347         // to use NewVReg instead of li.reg as appropriate.  We do this for
 348         // two reasons:
 349         //
 350         //   1. If the instr reads the same spilled vreg multiple times, we
 351         //      want to reuse the NewVReg.
 352         //   2. If the instr is a two-addr instruction, we are required to
 353         //      keep the src/dst regs pinned.
 354         //
 355         // Keep track of whether we replace a use and/or def so that we can
 356         // create the spill interval with the appropriate range.
 357         mop.setReg(NewVReg);
 358
 359         bool HasUse = mop.isUse();
 360         bool HasDef = mop.isDef();
 361         for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
 362           if (MI->getOperand(j).isRegister() &&
 363               MI->getOperand(j).getReg() == li.reg) {
 364             MI->getOperand(j).setReg(NewVReg);
 365             HasUse |= MI->getOperand(j).isUse();
 366             HasDef |= MI->getOperand(j).isDef();
 367           }
 368         }
 369
 370         vrm.grow();
 371         if (DefIsReMat) {
 372           vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
 373           if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) {
 374             // Each valnum may have its own remat id.
 375             ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg);
 376           } else {
 377             vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]);
 378           }
 379           if (!CanDelete || (HasUse && HasDef)) {
 380             // If this is a two-addr instruction then its use operands are
 381             // rematerializable but its def is not. It should be assigned a
 382             // stack slot.
 383             vrm.assignVirt2StackSlot(NewVReg, slot);
 384           }
 385         } else {
 386           vrm.assignVirt2StackSlot(NewVReg, slot);
 387         }
 388
 389         // create a new register interval for this spill / remat.
 390         LiveInterval &nI = getOrCreateInterval(NewVReg);
 391         assert(nI.empty());
 392
 393         // the spill weight is now infinity as it
 394         // cannot be spilled again
 395         nI.weight = HUGE_VALF;
 396
 397         if (HasUse) {
 398           LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
 399                        nI.getNextValue(~0U, 0, VNInfoAllocator));
 400           DOUT << " +" << LR;
 401           nI.addRange(LR);
 402         }
 403         if (HasDef) {
 404           LiveRange LR(getDefIndex(index), getStoreIndex(index),
 405                        nI.getNextValue(~0U, 0, VNInfoAllocator));
 406           DOUT << " +" << LR;
 407           nI.addRange(LR);
 408         }
 409
 410         added.push_back(&nI);
 411
 412         // update live variables if it is available
 413         if (lv_)
 414           lv_->addVirtualRegisterKilled(NewVReg, MI);
 415
 416         DOUT << "\t\t\t\tadded new interval: ";
 417         nI.print(DOUT, mri_);
 418         DOUT << '\n';
 419       }
 420     }
 421   }
 422
 423   return added;
 424 }
 425
 426 void LiveIntervals::printRegName(unsigned reg) const {
 427   if (MRegisterInfo::isPhysicalRegister(reg))
 428     cerr << mri_->getName(reg);
 429   else
 430     cerr << "%reg" << reg;
 431 }
 432
 433 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 434                                              MachineBasicBlock::iterator mi,
 435                                              unsigned MIIdx,
 436                                              LiveInterval &interval) {
 437   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 438   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
 439
 440   // Virtual registers may be defined multiple times (due to phi
 441   // elimination and 2-addr elimination).  Much of what we do only has to be
 442   // done once for the vreg.  We use an empty interval to detect the first
 443   // time we see a vreg.
 444   if (interval.empty()) {
 445     // Get the Idx of the defining instructions.
 446     unsigned defIndex = getDefIndex(MIIdx);
 447     VNInfo *ValNo;
 448     unsigned SrcReg, DstReg;
 449     if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
 450       ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
 451     else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 452       ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
 453                                     VNInfoAllocator);
 454     else
 455       ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
 456
 457     assert(ValNo->id == 0 && "First value in interval is not 0?");
 458
 459     // Loop over all of the blocks that the vreg is defined in.  There are
 460     // two cases we have to handle here.  The most common case is a vreg
 461     // whose lifetime is contained within a basic block.  In this case there
 462     // will be a single kill, in MBB, which comes after the definition.
 463     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 464       // FIXME: what about dead vars?
 465       unsigned killIdx;
 466       if (vi.Kills[0] != mi)
 467         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
 468       else
 469         killIdx = defIndex+1;
 470
 471       // If the kill happens after the definition, we have an intra-block
 472       // live range.
 473       if (killIdx > defIndex) {
 474         assert(vi.AliveBlocks.none() &&
 475                "Shouldn't be alive across any blocks!");
 476         LiveRange LR(defIndex, killIdx, ValNo);
 477         interval.addRange(LR);
 478         DOUT << " +" << LR << "\n";
 479         interval.addKill(ValNo, killIdx);
 480         return;
 481       }
 482     }
 483
 484     // The other case we handle is when a virtual register lives to the end
 485     // of the defining block, potentially live across some blocks, then is
 486     // live into some number of blocks, but gets killed.  Start by adding a
 487     // range that goes from this definition to the end of the defining block.
 488     LiveRange NewLR(defIndex,
 489                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
 490                     ValNo);
 491     DOUT << " +" << NewLR;
 492     interval.addRange(NewLR);
 493
 494     // Iterate over all of the blocks that the variable is completely
 495     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 496     // live interval.
 497     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
 498       if (vi.AliveBlocks[i]) {
 499         MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
 500         if (!MBB->empty()) {
 501           LiveRange LR(getMBBStartIdx(i),
 502                        getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
 503                        ValNo);
 504           interval.addRange(LR);
 505           DOUT << " +" << LR;
 506         }
 507       }
 508     }
 509
 510     // Finally, this virtual register is live from the start of any killing
 511     // block to the 'use' slot of the killing instruction.
 512     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 513       MachineInstr *Kill = vi.Kills[i];
 514       unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
 515       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 516                    killIdx, ValNo);
 517       interval.addRange(LR);
 518       interval.addKill(ValNo, killIdx);
 519       DOUT << " +" << LR;
 520     }
 521
 522   } else {
 523     // If this is the second time we see a virtual register definition, it
 524     // must be due to phi elimination or two addr elimination.  If this is
 525     // the result of two address elimination, then the vreg is one of the
 526     // def-and-use register operand.
 527     if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
 528       // If this is a two-address definition, then we have already processed
 529       // the live range.  The only problem is that we didn't realize there
 530       // are actually two values in the live interval.  Because of this we
 531       // need to take the LiveRegion that defines this register and split it
 532       // into two values.
 533       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
 534       unsigned RedefIndex = getDefIndex(MIIdx);
 535
 536       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
 537       VNInfo *OldValNo = OldLR->valno;
 538       unsigned OldEnd = OldLR->end;
 539
 540       // Delete the initial value, which should be short and continuous,
 541       // because the 2-addr copy must be in the same MBB as the redef.
 542       interval.removeRange(DefIndex, RedefIndex);
 543
 544       // Two-address vregs should always only be redefined once.  This means
 545       // that at this point, there should be exactly one value number in it.
 546       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
 547
 548       // The new value number (#1) is defined by the instruction we claimed
 549       // defined value #0.
 550       VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
 551       interval.copyValNumInfo(ValNo, OldValNo);
 552
 553       // Value#0 is now defined by the 2-addr instruction.
 554       OldValNo->def = RedefIndex;
 555       OldValNo->reg = 0;
 556
 557       // Add the new live interval which replaces the range for the input copy.
 558       LiveRange LR(DefIndex, RedefIndex, ValNo);
 559       DOUT << " replace range with " << LR;
 560       interval.addRange(LR);
 561       interval.addKill(ValNo, RedefIndex);
 562       interval.removeKills(ValNo, RedefIndex, OldEnd);
 563
 564       // If this redefinition is dead, we need to add a dummy unit live
 565       // range covering the def slot.
 566       if (lv_->RegisterDefIsDead(mi, interval.reg))
 567         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
 568
 569       DOUT << " RESULT: ";
 570       interval.print(DOUT, mri_);
 571
 572     } else {
 573       // Otherwise, this must be because of phi elimination.  If this is the
 574       // first redefinition of the vreg that we have seen, go back and change
 575       // the live range in the PHI block to be a different value number.
 576       if (interval.containsOneValue()) {
 577         assert(vi.Kills.size() == 1 &&
 578                "PHI elimination vreg should have one kill, the PHI itself!");
 579
 580         // Remove the old range that we now know has an incorrect number.
 581         VNInfo *VNI = interval.getValNumInfo(0);
 582         MachineInstr *Killer = vi.Kills[0];
 583         unsigned Start = getMBBStartIdx(Killer->getParent());
 584         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 585         DOUT << " Removing [" << Start << "," << End << "] from: ";
 586         interval.print(DOUT, mri_); DOUT << "\n";
 587         interval.removeRange(Start, End);
 588         interval.addKill(VNI, Start+1); // odd # means phi node
 589         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 590
 591         // Replace the interval with one of a NEW value number.  Note that this
 592         // value number isn't actually defined by an instruction, weird huh? :)
 593         LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
 594         DOUT << " replace range with " << LR;
 595         interval.addRange(LR);
 596         interval.addKill(LR.valno, End);
 597         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 598       }
 599
 600       // In the case of PHI elimination, each variable definition is only
 601       // live until the end of the block.  We've already taken care of the
 602       // rest of the live range.
 603       unsigned defIndex = getDefIndex(MIIdx);
 604
 605       VNInfo *ValNo;
 606       unsigned SrcReg, DstReg;
 607       if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
 608         ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
 609       else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 610         ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
 611                                       VNInfoAllocator);
 612       else
 613         ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
 614
 615       unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
 616       LiveRange LR(defIndex, killIndex, ValNo);
 617       interval.addRange(LR);
 618       interval.addKill(ValNo, killIndex-1); // odd # means phi node
 619       DOUT << " +" << LR;
 620     }
 621   }
 622
 623   DOUT << '\n';
 624 }
 625
 626 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 627                                               MachineBasicBlock::iterator mi,
 628                                               unsigned MIIdx,
 629                                               LiveInterval &interval,
 630                                               unsigned SrcReg) {
 631   // A physical register cannot be live across basic block, so its
 632   // lifetime must end somewhere in its defining basic block.
 633   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 634
 635   unsigned baseIndex = MIIdx;
 636   unsigned start = getDefIndex(baseIndex);
 637   unsigned end = start;
 638
 639   // If it is not used after definition, it is considered dead at
 640   // the instruction defining it. Hence its interval is:
 641   // [defSlot(def), defSlot(def)+1)
 642   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
 643     DOUT << " dead";
 644     end = getDefIndex(start) + 1;
 645     goto exit;
 646   }
 647
 648   // If it is not dead on definition, it must be killed by a
 649   // subsequent instruction. Hence its interval is:
 650   // [defSlot(def), useSlot(kill)+1)
 651   while (++mi != MBB->end()) {
 652     baseIndex += InstrSlots::NUM;
 653     if (lv_->KillsRegister(mi, interval.reg)) {
 654       DOUT << " killed";
 655       end = getUseIndex(baseIndex) + 1;
 656       goto exit;
 657     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 658       // Another instruction redefines the register before it is ever read.
 659       // Then the register is essentially dead at the instruction that defines
 660       // it. Hence its interval is:
 661       // [defSlot(def), defSlot(def)+1)
 662       DOUT << " dead";
 663       end = getDefIndex(start) + 1;
 664       goto exit;
 665     }
 666   }
 667
 668   // The only case we should have a dead physreg here without a killing or
 669   // instruction where we know it's dead is if it is live-in to the function
 670   // and never used.
 671   assert(!SrcReg && "physreg was not killed in defining block!");
 672   end = getDefIndex(start) + 1;  // It's dead.
 673
 674 exit:
 675   assert(start < end && "did not find end of interval?");
 676
 677   // Already exists? Extend old live interval.
 678   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 679   VNInfo *ValNo = (OldLR != interval.end())
 680     ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
 681   LiveRange LR(start, end, ValNo);
 682   interval.addRange(LR);
 683   interval.addKill(LR.valno, end);
 684   DOUT << " +" << LR << '\n';
 685 }
 686
 687 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 688                                       MachineBasicBlock::iterator MI,
 689                                       unsigned MIIdx,
 690                                       unsigned reg) {
 691   if (MRegisterInfo::isVirtualRegister(reg))
 692     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 693   else if (allocatableRegs_[reg]) {
 694     unsigned SrcReg, DstReg;
 695     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 696       SrcReg = MI->getOperand(1).getReg();
 697     else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
 698       SrcReg = 0;
 699     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
 700     // Def of a register also defines its sub-registers.
 701     for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
 702       // Avoid processing some defs more than once.
 703       if (!MI->findRegisterDefOperand(*AS))
 704         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 705   }
 706 }
 707
 708 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 709                                          unsigned MIIdx,
 710                                          LiveInterval &interval, bool isAlias) {
 711   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 712
 713   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 714   // be considered a livein.
 715   MachineBasicBlock::iterator mi = MBB->begin();
 716   unsigned baseIndex = MIIdx;
 717   unsigned start = baseIndex;
 718   unsigned end = start;
 719   while (mi != MBB->end()) {
 720     if (lv_->KillsRegister(mi, interval.reg)) {
 721       DOUT << " killed";
 722       end = getUseIndex(baseIndex) + 1;
 723       goto exit;
 724     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 725       // Another instruction redefines the register before it is ever read.
 726       // Then the register is essentially dead at the instruction that defines
 727       // it. Hence its interval is:
 728       // [defSlot(def), defSlot(def)+1)
 729       DOUT << " dead";
 730       end = getDefIndex(start) + 1;
 731       goto exit;
 732     }
 733
 734     baseIndex += InstrSlots::NUM;
 735     ++mi;
 736   }
 737
 738 exit:
 739   // Live-in register might not be used at all.
 740   if (end == MIIdx) {
 741     if (isAlias) {
 742       DOUT << " dead";
 743       end = getDefIndex(MIIdx) + 1;
 744     } else {
 745       DOUT << " live through";
 746       end = baseIndex;
 747     }
 748   }
 749
 750   LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
 751   interval.addRange(LR);
 752   interval.addKill(LR.valno, end);
 753   DOUT << " +" << LR << '\n';
 754 }
 755
 756 /// computeIntervals - computes the live intervals for virtual
 757 /// registers. for some ordering of the machine instructions [1,N] a
 758 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 759 /// which a variable is live
 760 void LiveIntervals::computeIntervals() {
 761   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 762        << "********** Function: "
 763        << ((Value*)mf_->getFunction())->getName() << '\n';
 764   // Track the index of the current machine instr.
 765   unsigned MIIndex = 0;
 766   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 767        MBBI != E; ++MBBI) {
 768     MachineBasicBlock *MBB = MBBI;
 769     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 770
 771     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 772
 773     // Create intervals for live-ins to this BB first.
 774     for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 775            LE = MBB->livein_end(); LI != LE; ++LI) {
 776       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 777       // Multiple live-ins can alias the same register.
 778       for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
 779         if (!hasInterval(*AS))
 780           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
 781                                true);
 782     }
 783
 784     for (; MI != miEnd; ++MI) {
 785       DOUT << MIIndex << "\t" << *MI;
 786
 787       // Handle defs.
 788       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 789         MachineOperand &MO = MI->getOperand(i);
 790         // handle register defs - build intervals
 791         if (MO.isRegister() && MO.getReg() && MO.isDef())
 792           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 793       }
 794
 795       MIIndex += InstrSlots::NUM;
 796     }
 797   }
 798 }
 799
 800 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 801   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
 802                        HUGE_VALF : 0.0F;
 803   return LiveInterval(reg, Weight);
 804 }