lib/CodeGen/LiveIntervalAnalysis.cpp

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