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