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