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