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              mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
 453       ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
 454                                     VNInfoAllocator);
 455     else
 456       ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
 457
 458     assert(ValNo->id == 0 && "First value in interval is not 0?");
 459
 460     // Loop over all of the blocks that the vreg is defined in.  There are
 461     // two cases we have to handle here.  The most common case is a vreg
 462     // whose lifetime is contained within a basic block.  In this case there
 463     // will be a single kill, in MBB, which comes after the definition.
 464     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 465       // FIXME: what about dead vars?
 466       unsigned killIdx;
 467       if (vi.Kills[0] != mi)
 468         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
 469       else
 470         killIdx = defIndex+1;
 471
 472       // If the kill happens after the definition, we have an intra-block
 473       // live range.
 474       if (killIdx > defIndex) {
 475         assert(vi.AliveBlocks.none() &&
 476                "Shouldn't be alive across any blocks!");
 477         LiveRange LR(defIndex, killIdx, ValNo);
 478         interval.addRange(LR);
 479         DOUT << " +" << LR << "\n";
 480         interval.addKill(ValNo, killIdx);
 481         return;
 482       }
 483     }
 484
 485     // The other case we handle is when a virtual register lives to the end
 486     // of the defining block, potentially live across some blocks, then is
 487     // live into some number of blocks, but gets killed.  Start by adding a
 488     // range that goes from this definition to the end of the defining block.
 489     LiveRange NewLR(defIndex,
 490                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
 491                     ValNo);
 492     DOUT << " +" << NewLR;
 493     interval.addRange(NewLR);
 494
 495     // Iterate over all of the blocks that the variable is completely
 496     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 497     // live interval.
 498     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
 499       if (vi.AliveBlocks[i]) {
 500         MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
 501         if (!MBB->empty()) {
 502           LiveRange LR(getMBBStartIdx(i),
 503                        getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
 504                        ValNo);
 505           interval.addRange(LR);
 506           DOUT << " +" << LR;
 507         }
 508       }
 509     }
 510
 511     // Finally, this virtual register is live from the start of any killing
 512     // block to the 'use' slot of the killing instruction.
 513     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 514       MachineInstr *Kill = vi.Kills[i];
 515       unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
 516       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 517                    killIdx, ValNo);
 518       interval.addRange(LR);
 519       interval.addKill(ValNo, killIdx);
 520       DOUT << " +" << LR;
 521     }
 522
 523   } else {
 524     // If this is the second time we see a virtual register definition, it
 525     // must be due to phi elimination or two addr elimination.  If this is
 526     // the result of two address elimination, then the vreg is one of the
 527     // def-and-use register operand.
 528     if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
 529       // If this is a two-address definition, then we have already processed
 530       // the live range.  The only problem is that we didn't realize there
 531       // are actually two values in the live interval.  Because of this we
 532       // need to take the LiveRegion that defines this register and split it
 533       // into two values.
 534       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
 535       unsigned RedefIndex = getDefIndex(MIIdx);
 536
 537       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
 538       VNInfo *OldValNo = OldLR->valno;
 539       unsigned OldEnd = OldLR->end;
 540
 541       // Delete the initial value, which should be short and continuous,
 542       // because the 2-addr copy must be in the same MBB as the redef.
 543       interval.removeRange(DefIndex, RedefIndex);
 544
 545       // Two-address vregs should always only be redefined once.  This means
 546       // that at this point, there should be exactly one value number in it.
 547       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
 548
 549       // The new value number (#1) is defined by the instruction we claimed
 550       // defined value #0.
 551       VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
 552       interval.copyValNumInfo(ValNo, OldValNo);
 553
 554       // Value#0 is now defined by the 2-addr instruction.
 555       OldValNo->def = RedefIndex;
 556       OldValNo->reg = 0;
 557
 558       // Add the new live interval which replaces the range for the input copy.
 559       LiveRange LR(DefIndex, RedefIndex, ValNo);
 560       DOUT << " replace range with " << LR;
 561       interval.addRange(LR);
 562       interval.addKill(ValNo, RedefIndex);
 563       interval.removeKills(ValNo, RedefIndex, OldEnd);
 564
 565       // If this redefinition is dead, we need to add a dummy unit live
 566       // range covering the def slot.
 567       if (lv_->RegisterDefIsDead(mi, interval.reg))
 568         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
 569
 570       DOUT << " RESULT: ";
 571       interval.print(DOUT, mri_);
 572
 573     } else {
 574       // Otherwise, this must be because of phi elimination.  If this is the
 575       // first redefinition of the vreg that we have seen, go back and change
 576       // the live range in the PHI block to be a different value number.
 577       if (interval.containsOneValue()) {
 578         assert(vi.Kills.size() == 1 &&
 579                "PHI elimination vreg should have one kill, the PHI itself!");
 580
 581         // Remove the old range that we now know has an incorrect number.
 582         VNInfo *VNI = interval.getValNumInfo(0);
 583         MachineInstr *Killer = vi.Kills[0];
 584         unsigned Start = getMBBStartIdx(Killer->getParent());
 585         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 586         DOUT << " Removing [" << Start << "," << End << "] from: ";
 587         interval.print(DOUT, mri_); DOUT << "\n";
 588         interval.removeRange(Start, End);
 589         interval.addKill(VNI, Start+1); // odd # means phi node
 590         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 591
 592         // Replace the interval with one of a NEW value number.  Note that this
 593         // value number isn't actually defined by an instruction, weird huh? :)
 594         LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
 595         DOUT << " replace range with " << LR;
 596         interval.addRange(LR);
 597         interval.addKill(LR.valno, End);
 598         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 599       }
 600
 601       // In the case of PHI elimination, each variable definition is only
 602       // live until the end of the block.  We've already taken care of the
 603       // rest of the live range.
 604       unsigned defIndex = getDefIndex(MIIdx);
 605
 606       VNInfo *ValNo;
 607       unsigned SrcReg, DstReg;
 608       if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
 609         ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
 610       else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 611         ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
 612                                       VNInfoAllocator);
 613       else
 614         ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
 615
 616       unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
 617       LiveRange LR(defIndex, killIndex, ValNo);
 618       interval.addRange(LR);
 619       interval.addKill(ValNo, killIndex-1); // odd # means phi node
 620       DOUT << " +" << LR;
 621     }
 622   }
 623
 624   DOUT << '\n';
 625 }
 626
 627 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 628                                               MachineBasicBlock::iterator mi,
 629                                               unsigned MIIdx,
 630                                               LiveInterval &interval,
 631                                               unsigned SrcReg) {
 632   // A physical register cannot be live across basic block, so its
 633   // lifetime must end somewhere in its defining basic block.
 634   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 635
 636   unsigned baseIndex = MIIdx;
 637   unsigned start = getDefIndex(baseIndex);
 638   unsigned end = start;
 639
 640   // If it is not used after definition, it is considered dead at
 641   // the instruction defining it. Hence its interval is:
 642   // [defSlot(def), defSlot(def)+1)
 643   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
 644     DOUT << " dead";
 645     end = getDefIndex(start) + 1;
 646     goto exit;
 647   }
 648
 649   // If it is not dead on definition, it must be killed by a
 650   // subsequent instruction. Hence its interval is:
 651   // [defSlot(def), useSlot(kill)+1)
 652   while (++mi != MBB->end()) {
 653     baseIndex += InstrSlots::NUM;
 654     if (lv_->KillsRegister(mi, interval.reg)) {
 655       DOUT << " killed";
 656       end = getUseIndex(baseIndex) + 1;
 657       goto exit;
 658     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 659       // Another instruction redefines the register before it is ever read.
 660       // Then the register is essentially dead at the instruction that defines
 661       // it. Hence its interval is:
 662       // [defSlot(def), defSlot(def)+1)
 663       DOUT << " dead";
 664       end = getDefIndex(start) + 1;
 665       goto exit;
 666     }
 667   }
 668
 669   // The only case we should have a dead physreg here without a killing or
 670   // instruction where we know it's dead is if it is live-in to the function
 671   // and never used.
 672   assert(!SrcReg && "physreg was not killed in defining block!");
 673   end = getDefIndex(start) + 1;  // It's dead.
 674
 675 exit:
 676   assert(start < end && "did not find end of interval?");
 677
 678   // Already exists? Extend old live interval.
 679   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 680   VNInfo *ValNo = (OldLR != interval.end())
 681     ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
 682   LiveRange LR(start, end, ValNo);
 683   interval.addRange(LR);
 684   interval.addKill(LR.valno, end);
 685   DOUT << " +" << LR << '\n';
 686 }
 687
 688 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 689                                       MachineBasicBlock::iterator MI,
 690                                       unsigned MIIdx,
 691                                       unsigned reg) {
 692   if (MRegisterInfo::isVirtualRegister(reg))
 693     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 694   else if (allocatableRegs_[reg]) {
 695     unsigned SrcReg, DstReg;
 696     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 697       SrcReg = MI->getOperand(1).getReg();
 698     else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
 699       SrcReg = 0;
 700     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
 701     // Def of a register also defines its sub-registers.
 702     for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
 703       // Avoid processing some defs more than once.
 704       if (!MI->findRegisterDefOperand(*AS))
 705         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 706   }
 707 }
 708
 709 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 710                                          unsigned MIIdx,
 711                                          LiveInterval &interval, bool isAlias) {
 712   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 713
 714   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 715   // be considered a livein.
 716   MachineBasicBlock::iterator mi = MBB->begin();
 717   unsigned baseIndex = MIIdx;
 718   unsigned start = baseIndex;
 719   unsigned end = start;
 720   while (mi != MBB->end()) {
 721     if (lv_->KillsRegister(mi, interval.reg)) {
 722       DOUT << " killed";
 723       end = getUseIndex(baseIndex) + 1;
 724       goto exit;
 725     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 726       // Another instruction redefines the register before it is ever read.
 727       // Then the register is essentially dead at the instruction that defines
 728       // it. Hence its interval is:
 729       // [defSlot(def), defSlot(def)+1)
 730       DOUT << " dead";
 731       end = getDefIndex(start) + 1;
 732       goto exit;
 733     }
 734
 735     baseIndex += InstrSlots::NUM;
 736     ++mi;
 737   }
 738
 739 exit:
 740   // Live-in register might not be used at all.
 741   if (end == MIIdx) {
 742     if (isAlias) {
 743       DOUT << " dead";
 744       end = getDefIndex(MIIdx) + 1;
 745     } else {
 746       DOUT << " live through";
 747       end = baseIndex;
 748     }
 749   }
 750
 751   LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
 752   interval.addRange(LR);
 753   interval.addKill(LR.valno, end);
 754   DOUT << " +" << LR << '\n';
 755 }
 756
 757 /// computeIntervals - computes the live intervals for virtual
 758 /// registers. for some ordering of the machine instructions [1,N] a
 759 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 760 /// which a variable is live
 761 void LiveIntervals::computeIntervals() {
 762   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 763        << "********** Function: "
 764        << ((Value*)mf_->getFunction())->getName() << '\n';
 765   // Track the index of the current machine instr.
 766   unsigned MIIndex = 0;
 767   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 768        MBBI != E; ++MBBI) {
 769     MachineBasicBlock *MBB = MBBI;
 770     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 771
 772     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 773
 774     // Create intervals for live-ins to this BB first.
 775     for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 776            LE = MBB->livein_end(); LI != LE; ++LI) {
 777       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 778       // Multiple live-ins can alias the same register.
 779       for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
 780         if (!hasInterval(*AS))
 781           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
 782                                true);
 783     }
 784
 785     for (; MI != miEnd; ++MI) {
 786       DOUT << MIIndex << "\t" << *MI;
 787
 788       // Handle defs.
 789       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 790         MachineOperand &MO = MI->getOperand(i);
 791         // handle register defs - build intervals
 792         if (MO.isRegister() && MO.getReg() && MO.isDef())
 793           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 794       }
 795
 796       MIIndex += InstrSlots::NUM;
 797     }
 798   }
 799 }
 800
 801 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 802   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
 803                        HUGE_VALF : 0.0F;
 804   return LiveInterval(reg, Weight);
 805 }