lib/CodeGen/LiveIntervalAnalysis.cpp

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