LLVM API Documentation

LiveIntervalAnalysis.cpp

Go to the documentation of this file.
00001 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the LiveInterval analysis pass which is used
00011 // by the Linear Scan Register allocator. This pass linearizes the
00012 // basic blocks of the function in DFS order and uses the
00013 // LiveVariables pass to conservatively compute live intervals for
00014 // each virtual and physical register.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #define DEBUG_TYPE "liveintervals"
00019 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00020 #include "VirtRegMap.h"
00021 #include "llvm/Value.h"
00022 #include "llvm/Analysis/AliasAnalysis.h"
00023 #include "llvm/CodeGen/LiveVariables.h"
00024 #include "llvm/CodeGen/MachineFrameInfo.h"
00025 #include "llvm/CodeGen/MachineInstr.h"
00026 #include "llvm/CodeGen/MachineInstrBuilder.h"
00027 #include "llvm/CodeGen/MachineLoopInfo.h"
00028 #include "llvm/CodeGen/MachineRegisterInfo.h"
00029 #include "llvm/CodeGen/Passes.h"
00030 #include "llvm/CodeGen/PseudoSourceValue.h"
00031 #include "llvm/Target/TargetRegisterInfo.h"
00032 #include "llvm/Target/TargetInstrInfo.h"
00033 #include "llvm/Target/TargetMachine.h"
00034 #include "llvm/Target/TargetOptions.h"
00035 #include "llvm/Support/CommandLine.h"
00036 #include "llvm/Support/Debug.h"
00037 #include "llvm/Support/ErrorHandling.h"
00038 #include "llvm/Support/raw_ostream.h"
00039 #include "llvm/ADT/DepthFirstIterator.h"
00040 #include "llvm/ADT/SmallSet.h"
00041 #include "llvm/ADT/Statistic.h"
00042 #include "llvm/ADT/STLExtras.h"
00043 #include <algorithm>
00044 #include <limits>
00045 #include <cmath>
00046 using namespace llvm;
00047 
00048 // Hidden options for help debugging.
00049 static cl::opt<bool> DisableReMat("disable-rematerialization", 
00050                                   cl::init(false), cl::Hidden);
00051 
00052 static cl::opt<bool> SplitAtBB("split-intervals-at-bb", 
00053                                cl::init(true), cl::Hidden);
00054 static cl::opt<int> SplitLimit("split-limit",
00055                                cl::init(-1), cl::Hidden);
00056 
00057 static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
00058 
00059 static cl::opt<bool> EnableFastSpilling("fast-spill",
00060                                         cl::init(false), cl::Hidden);
00061 
00062 STATISTIC(numIntervals, "Number of original intervals");
00063 STATISTIC(numFolds    , "Number of loads/stores folded into instructions");
00064 STATISTIC(numSplits   , "Number of intervals split");
00065 
00066 char LiveIntervals::ID = 0;
00067 static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
00068 
00069 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
00070   AU.setPreservesCFG();
00071   AU.addRequired<AliasAnalysis>();
00072   AU.addPreserved<AliasAnalysis>();
00073   AU.addPreserved<LiveVariables>();
00074   AU.addRequired<LiveVariables>();
00075   AU.addPreservedID(MachineLoopInfoID);
00076   AU.addPreservedID(MachineDominatorsID);
00077   
00078   if (!StrongPHIElim) {
00079     AU.addPreservedID(PHIEliminationID);
00080     AU.addRequiredID(PHIEliminationID);
00081   }
00082   
00083   AU.addRequiredID(TwoAddressInstructionPassID);
00084   MachineFunctionPass::getAnalysisUsage(AU);
00085 }
00086 
00087 void LiveIntervals::releaseMemory() {
00088   // Free the live intervals themselves.
00089   for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
00090        E = r2iMap_.end(); I != E; ++I)
00091     delete I->second;
00092   
00093   MBB2IdxMap.clear();
00094   Idx2MBBMap.clear();
00095   mi2iMap_.clear();
00096   i2miMap_.clear();
00097   r2iMap_.clear();
00098   terminatorGaps.clear();
00099 
00100   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
00101   VNInfoAllocator.Reset();
00102   while (!ClonedMIs.empty()) {
00103     MachineInstr *MI = ClonedMIs.back();
00104     ClonedMIs.pop_back();
00105     mf_->DeleteMachineInstr(MI);
00106   }
00107 }
00108 
00109 static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
00110                                    const TargetInstrInfo *tii_) {
00111   unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
00112   if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
00113       Reg == SrcReg)
00114     return true;
00115 
00116   if ((MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
00117        MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) &&
00118       MI->getOperand(2).getReg() == Reg)
00119     return true;
00120   if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG &&
00121       MI->getOperand(1).getReg() == Reg)
00122     return true;
00123   return false;
00124 }
00125 
00126 /// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
00127 /// there is one implicit_def for each use. Add isUndef marker to
00128 /// implicit_def defs and their uses.
00129 void LiveIntervals::processImplicitDefs() {
00130   SmallSet<unsigned, 8> ImpDefRegs;
00131   SmallVector<MachineInstr*, 8> ImpDefMIs;
00132   MachineBasicBlock *Entry = mf_->begin();
00133   SmallPtrSet<MachineBasicBlock*,16> Visited;
00134   for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
00135          DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
00136        DFI != E; ++DFI) {
00137     MachineBasicBlock *MBB = *DFI;
00138     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
00139          I != E; ) {
00140       MachineInstr *MI = &*I;
00141       ++I;
00142       if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
00143         unsigned Reg = MI->getOperand(0).getReg();
00144         ImpDefRegs.insert(Reg);
00145         ImpDefMIs.push_back(MI);
00146         continue;
00147       }
00148 
00149       bool ChangedToImpDef = false;
00150       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00151         MachineOperand& MO = MI->getOperand(i);
00152         if (!MO.isReg() || !MO.isUse() || MO.isUndef())
00153           continue;
00154         unsigned Reg = MO.getReg();
00155         if (!Reg)
00156           continue;
00157         if (!ImpDefRegs.count(Reg))
00158           continue;
00159         // Use is a copy, just turn it into an implicit_def.
00160         if (CanTurnIntoImplicitDef(MI, Reg, tii_)) {
00161           bool isKill = MO.isKill();
00162           MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
00163           for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
00164             MI->RemoveOperand(j);
00165           if (isKill)
00166             ImpDefRegs.erase(Reg);
00167           ChangedToImpDef = true;
00168           break;
00169         }
00170 
00171         MO.setIsUndef();
00172         if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
00173           // Make sure other uses of 
00174           for (unsigned j = i+1; j != e; ++j) {
00175             MachineOperand &MOJ = MI->getOperand(j);
00176             if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
00177               MOJ.setIsUndef();
00178           }
00179           ImpDefRegs.erase(Reg);
00180         }
00181       }
00182 
00183       if (ChangedToImpDef) {
00184         // Backtrack to process this new implicit_def.
00185         --I;
00186       } else {
00187         for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
00188           MachineOperand& MO = MI->getOperand(i);
00189           if (!MO.isReg() || !MO.isDef())
00190             continue;
00191           ImpDefRegs.erase(MO.getReg());
00192         }
00193       }
00194     }
00195 
00196     // Any outstanding liveout implicit_def's?
00197     for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
00198       MachineInstr *MI = ImpDefMIs[i];
00199       unsigned Reg = MI->getOperand(0).getReg();
00200       if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
00201           !ImpDefRegs.count(Reg)) {
00202         // Delete all "local" implicit_def's. That include those which define
00203         // physical registers since they cannot be liveout.
00204         MI->eraseFromParent();
00205         continue;
00206       }
00207 
00208       // If there are multiple defs of the same register and at least one
00209       // is not an implicit_def, do not insert implicit_def's before the
00210       // uses.
00211       bool Skip = false;
00212       for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
00213              DE = mri_->def_end(); DI != DE; ++DI) {
00214         if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
00215           Skip = true;
00216           break;
00217         }
00218       }
00219       if (Skip)
00220         continue;
00221 
00222       // The only implicit_def which we want to keep are those that are live
00223       // out of its block.
00224       MI->eraseFromParent();
00225 
00226       for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
00227              UE = mri_->use_end(); UI != UE; ) {
00228         MachineOperand &RMO = UI.getOperand();
00229         MachineInstr *RMI = &*UI;
00230         ++UI;
00231         MachineBasicBlock *RMBB = RMI->getParent();
00232         if (RMBB == MBB)
00233           continue;
00234 
00235         // Turn a copy use into an implicit_def.
00236         unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
00237         if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
00238             Reg == SrcReg) {
00239           RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
00240           for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
00241             RMI->RemoveOperand(j);
00242           continue;
00243         }
00244 
00245         const TargetRegisterClass* RC = mri_->getRegClass(Reg);
00246         unsigned NewVReg = mri_->createVirtualRegister(RC);
00247         RMO.setReg(NewVReg);
00248         RMO.setIsUndef();
00249         RMO.setIsKill();
00250       }
00251     }
00252     ImpDefRegs.clear();
00253     ImpDefMIs.clear();
00254   }
00255 }
00256 
00257 void LiveIntervals::computeNumbering() {
00258   Index2MiMap OldI2MI = i2miMap_;
00259   std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
00260   
00261   Idx2MBBMap.clear();
00262   MBB2IdxMap.clear();
00263   mi2iMap_.clear();
00264   i2miMap_.clear();
00265   terminatorGaps.clear();
00266   
00267   FunctionSize = 0;
00268   
00269   // Number MachineInstrs and MachineBasicBlocks.
00270   // Initialize MBB indexes to a sentinal.
00271   MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
00272   
00273   unsigned MIIndex = 0;
00274   for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
00275        MBB != E; ++MBB) {
00276     unsigned StartIdx = MIIndex;
00277 
00278     // Insert an empty slot at the beginning of each block.
00279     MIIndex += InstrSlots::NUM;
00280     i2miMap_.push_back(0);
00281 
00282     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
00283          I != E; ++I) {
00284       
00285       if (I == MBB->getFirstTerminator()) {
00286         // Leave a gap for before terminators, this is where we will point
00287         // PHI kills.
00288         bool inserted =
00289           terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
00290         assert(inserted && 
00291                "Multiple 'first' terminators encountered during numbering.");
00292         inserted = inserted; // Avoid compiler warning if assertions turned off.
00293         i2miMap_.push_back(0);
00294 
00295         MIIndex += InstrSlots::NUM;
00296       }
00297 
00298       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
00299       assert(inserted && "multiple MachineInstr -> index mappings");
00300       inserted = true;
00301       i2miMap_.push_back(I);
00302       MIIndex += InstrSlots::NUM;
00303       FunctionSize++;
00304       
00305       // Insert max(1, numdefs) empty slots after every instruction.
00306       unsigned Slots = I->getDesc().getNumDefs();
00307       if (Slots == 0)
00308         Slots = 1;
00309       MIIndex += InstrSlots::NUM * Slots;
00310       while (Slots--)
00311         i2miMap_.push_back(0);
00312     }
00313   
00314     if (MBB->getFirstTerminator() == MBB->end()) {
00315       // Leave a gap for before terminators, this is where we will point
00316       // PHI kills.
00317       bool inserted =
00318         terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
00319       assert(inserted && 
00320              "Multiple 'first' terminators encountered during numbering.");
00321       inserted = inserted; // Avoid compiler warning if assertions turned off.
00322       i2miMap_.push_back(0);
00323  
00324       MIIndex += InstrSlots::NUM;
00325     }
00326     
00327     // Set the MBB2IdxMap entry for this MBB.
00328     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
00329     Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
00330   }
00331 
00332   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
00333   
00334   if (!OldI2MI.empty())
00335     for (iterator OI = begin(), OE = end(); OI != OE; ++OI) {
00336       for (LiveInterval::iterator LI = OI->second->begin(),
00337            LE = OI->second->end(); LI != LE; ++LI) {
00338         
00339         // Remap the start index of the live range to the corresponding new
00340         // number, or our best guess at what it _should_ correspond to if the
00341         // original instruction has been erased.  This is either the following
00342         // instruction or its predecessor.
00343         unsigned index = LI->start / InstrSlots::NUM;
00344         unsigned offset = LI->start % InstrSlots::NUM;
00345         if (offset == InstrSlots::LOAD) {
00346           std::vector<IdxMBBPair>::const_iterator I =
00347                   std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start);
00348           // Take the pair containing the index
00349           std::vector<IdxMBBPair>::const_iterator J =
00350                     (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
00351           
00352           LI->start = getMBBStartIdx(J->second);
00353         } else {
00354           LI->start = mi2iMap_[OldI2MI[index]] + offset;
00355         }
00356         
00357         // Remap the ending index in the same way that we remapped the start,
00358         // except for the final step where we always map to the immediately
00359         // following instruction.
00360         index = (LI->end - 1) / InstrSlots::NUM;
00361         offset  = LI->end % InstrSlots::NUM;
00362         if (offset == InstrSlots::LOAD) {
00363           // VReg dies at end of block.
00364           std::vector<IdxMBBPair>::const_iterator I =
00365                   std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
00366           --I;
00367           
00368           LI->end = getMBBEndIdx(I->second) + 1;
00369         } else {
00370           unsigned idx = index;
00371           while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
00372           
00373           if (index != OldI2MI.size())
00374             LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0);
00375           else
00376             LI->end = InstrSlots::NUM * i2miMap_.size();
00377         }
00378       }
00379       
00380       for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(),
00381            VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 
00382         VNInfo* vni = *VNI;
00383         
00384         // Remap the VNInfo def index, which works the same as the
00385         // start indices above. VN's with special sentinel defs
00386         // don't need to be remapped.
00387         if (vni->isDefAccurate() && !vni->isUnused()) {
00388           unsigned index = vni->def / InstrSlots::NUM;
00389           unsigned offset = vni->def % InstrSlots::NUM;
00390           if (offset == InstrSlots::LOAD) {
00391             std::vector<IdxMBBPair>::const_iterator I =
00392                   std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def);
00393             // Take the pair containing the index
00394             std::vector<IdxMBBPair>::const_iterator J =
00395                     (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
00396           
00397             vni->def = getMBBStartIdx(J->second);
00398           } else {
00399             vni->def = mi2iMap_[OldI2MI[index]] + offset;
00400           }
00401         }
00402         
00403         // Remap the VNInfo kill indices, which works the same as
00404         // the end indices above.
00405         for (size_t i = 0; i < vni->kills.size(); ++i) {
00406           unsigned killIdx = vni->kills[i].killIdx;
00407 
00408           unsigned index = (killIdx - 1) / InstrSlots::NUM;
00409           unsigned offset = killIdx % InstrSlots::NUM;
00410 
00411           if (offset == InstrSlots::LOAD) {
00412             assert("Value killed at a load slot.");
00413             /*std::vector<IdxMBBPair>::const_iterator I =
00414              std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
00415             --I;
00416 
00417             vni->kills[i] = getMBBEndIdx(I->second);*/
00418           } else {
00419             if (vni->kills[i].isPHIKill) {
00420               std::vector<IdxMBBPair>::const_iterator I =
00421                 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index);
00422               --I;
00423               vni->kills[i].killIdx = terminatorGaps[I->second];  
00424             } else {
00425               assert(OldI2MI[index] != 0 &&
00426                      "Kill refers to instruction not present in index maps.");
00427               vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset;
00428             }
00429            
00430             /*
00431             unsigned idx = index;
00432             while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
00433             
00434             if (index != OldI2MI.size())
00435               vni->kills[i] = mi2iMap_[OldI2MI[index]] + 
00436                               (idx == index ? offset : 0);
00437             else
00438               vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
00439             */
00440           }
00441         }
00442       }
00443     }
00444 }
00445 
00446 void LiveIntervals::scaleNumbering(int factor) {
00447   // Need to
00448   //  * scale MBB begin and end points
00449   //  * scale all ranges.
00450   //  * Update VNI structures.
00451   //  * Scale instruction numberings 
00452 
00453   // Scale the MBB indices.
00454   Idx2MBBMap.clear();
00455   for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end();
00456        MBB != MBBE; ++MBB) {
00457     std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()];
00458     mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor);
00459     mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor);
00460     Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); 
00461   }
00462   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
00463 
00464   // Scale terminator gaps.
00465   for (DenseMap<MachineBasicBlock*, unsigned>::iterator
00466        TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
00467        TGI != TGE; ++TGI) {
00468     terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor);
00469   }
00470 
00471   // Scale the intervals.
00472   for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
00473     LI->second->scaleNumbering(factor);
00474   }
00475 
00476   // Scale MachineInstrs.
00477   Mi2IndexMap oldmi2iMap = mi2iMap_;
00478   unsigned highestSlot = 0;
00479   for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end();
00480        MI != ME; ++MI) {
00481     unsigned newSlot = InstrSlots::scale(MI->second, factor);
00482     mi2iMap_[MI->first] = newSlot;
00483     highestSlot = std::max(highestSlot, newSlot); 
00484   }
00485 
00486   i2miMap_.clear();
00487   i2miMap_.resize(highestSlot + 1);
00488   for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end();
00489        MI != ME; ++MI) {
00490     i2miMap_[MI->second] = const_cast<MachineInstr *>(MI->first);
00491   }
00492 
00493 }
00494 
00495 
00496 /// runOnMachineFunction - Register allocate the whole function
00497 ///
00498 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
00499   mf_ = &fn;
00500   mri_ = &mf_->getRegInfo();
00501   tm_ = &fn.getTarget();
00502   tri_ = tm_->getRegisterInfo();
00503   tii_ = tm_->getInstrInfo();
00504   aa_ = &getAnalysis<AliasAnalysis>();
00505   lv_ = &getAnalysis<LiveVariables>();
00506   allocatableRegs_ = tri_->getAllocatableSet(fn);
00507 
00508   processImplicitDefs();
00509   computeNumbering();
00510   computeIntervals();
00511 
00512   numIntervals += getNumIntervals();
00513 
00514   DEBUG(dump());
00515   return true;
00516 }
00517 
00518 /// print - Implement the dump method.
00519 void LiveIntervals::print(std::ostream &O, const Module* ) const {
00520   O << "********** INTERVALS **********\n";
00521   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00522     I->second->print(O, tri_);
00523     O << "\n";
00524   }
00525 
00526   O << "********** MACHINEINSTRS **********\n";
00527   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
00528        mbbi != mbbe; ++mbbi) {
00529     O << ((Value*)mbbi->getBasicBlock())->getNameStr() << ":\n";
00530     for (MachineBasicBlock::iterator mii = mbbi->begin(),
00531            mie = mbbi->end(); mii != mie; ++mii) {
00532       O << getInstructionIndex(mii) << '\t' << *mii;
00533     }
00534   }
00535 }
00536 
00537 /// conflictsWithPhysRegDef - Returns true if the specified register
00538 /// is defined during the duration of the specified interval.
00539 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
00540                                             VirtRegMap &vrm, unsigned reg) {
00541   for (LiveInterval::Ranges::const_iterator
00542          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
00543     for (unsigned index = getBaseIndex(I->start),
00544            end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
00545          index += InstrSlots::NUM) {
00546       // skip deleted instructions
00547       while (index != end && !getInstructionFromIndex(index))
00548         index += InstrSlots::NUM;
00549       if (index == end) break;
00550 
00551       MachineInstr *MI = getInstructionFromIndex(index);
00552       unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
00553       if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
00554         if (SrcReg == li.reg || DstReg == li.reg)
00555           continue;
00556       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
00557         MachineOperand& mop = MI->getOperand(i);
00558         if (!mop.isReg())
00559           continue;
00560         unsigned PhysReg = mop.getReg();
00561         if (PhysReg == 0 || PhysReg == li.reg)
00562           continue;
00563         if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
00564           if (!vrm.hasPhys(PhysReg))
00565             continue;
00566           PhysReg = vrm.getPhys(PhysReg);
00567         }
00568         if (PhysReg && tri_->regsOverlap(PhysReg, reg))
00569           return true;
00570       }
00571     }
00572   }
00573 
00574   return false;
00575 }
00576 
00577 /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
00578 /// it can check use as well.
00579 bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li,
00580                                             unsigned Reg, bool CheckUse,
00581                                   SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
00582   for (LiveInterval::Ranges::const_iterator
00583          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
00584     for (unsigned index = getBaseIndex(I->start),
00585            end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
00586          index += InstrSlots::NUM) {
00587       // Skip deleted instructions.
00588       MachineInstr *MI = 0;
00589       while (index != end) {
00590         MI = getInstructionFromIndex(index);
00591         if (MI)
00592           break;
00593         index += InstrSlots::NUM;
00594       }
00595       if (index == end) break;
00596 
00597       if (JoinedCopies.count(MI))
00598         continue;
00599       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00600         MachineOperand& MO = MI->getOperand(i);
00601         if (!MO.isReg())
00602           continue;
00603         if (MO.isUse() && !CheckUse)
00604           continue;
00605         unsigned PhysReg = MO.getReg();
00606         if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg))
00607           continue;
00608         if (tri_->isSubRegister(Reg, PhysReg))
00609           return true;
00610       }
00611     }
00612   }
00613 
00614   return false;
00615 }
00616 
00617 
00618 void LiveIntervals::printRegName(unsigned reg) const {
00619   if (TargetRegisterInfo::isPhysicalRegister(reg))
00620     errs() << tri_->getName(reg);
00621   else
00622     errs() << "%reg" << reg;
00623 }
00624 
00625 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
00626                                              MachineBasicBlock::iterator mi,
00627                                              unsigned MIIdx, MachineOperand& MO,
00628                                              unsigned MOIdx,
00629                                              LiveInterval &interval) {
00630   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
00631 
00632   // Virtual registers may be defined multiple times (due to phi
00633   // elimination and 2-addr elimination).  Much of what we do only has to be
00634   // done once for the vreg.  We use an empty interval to detect the first
00635   // time we see a vreg.
00636   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
00637   if (interval.empty()) {
00638     // Get the Idx of the defining instructions.
00639     unsigned defIndex = getDefIndex(MIIdx);
00640     // Earlyclobbers move back one.
00641     if (MO.isEarlyClobber())
00642       defIndex = getUseIndex(MIIdx);
00643     VNInfo *ValNo;
00644     MachineInstr *CopyMI = NULL;
00645     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
00646     if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
00647         mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
00648         mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
00649         tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
00650       CopyMI = mi;
00651     // Earlyclobbers move back one.
00652     ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
00653 
00654     assert(ValNo->id == 0 && "First value in interval is not 0?");
00655 
00656     // Loop over all of the blocks that the vreg is defined in.  There are
00657     // two cases we have to handle here.  The most common case is a vreg
00658     // whose lifetime is contained within a basic block.  In this case there
00659     // will be a single kill, in MBB, which comes after the definition.
00660     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
00661       // FIXME: what about dead vars?
00662       unsigned killIdx;
00663       if (vi.Kills[0] != mi)
00664         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
00665       else
00666         killIdx = defIndex+1;
00667 
00668       // If the kill happens after the definition, we have an intra-block
00669       // live range.
00670       if (killIdx > defIndex) {
00671         assert(vi.AliveBlocks.empty() &&
00672                "Shouldn't be alive across any blocks!");
00673         LiveRange LR(defIndex, killIdx, ValNo);
00674         interval.addRange(LR);
00675         DOUT << " +" << LR << "\n";
00676         interval.addKill(ValNo, killIdx, false);
00677         return;
00678       }
00679     }
00680 
00681     // The other case we handle is when a virtual register lives to the end
00682     // of the defining block, potentially live across some blocks, then is
00683     // live into some number of blocks, but gets killed.  Start by adding a
00684     // range that goes from this definition to the end of the defining block.
00685     LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo);
00686     DOUT << " +" << NewLR;
00687     interval.addRange(NewLR);
00688 
00689     // Iterate over all of the blocks that the variable is completely
00690     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
00691     // live interval.
00692     for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 
00693              E = vi.AliveBlocks.end(); I != E; ++I) {
00694       LiveRange LR(getMBBStartIdx(*I),
00695                    getMBBEndIdx(*I)+1,  // MBB ends at -1.
00696                    ValNo);
00697       interval.addRange(LR);
00698       DOUT << " +" << LR;
00699     }
00700 
00701     // Finally, this virtual register is live from the start of any killing
00702     // block to the 'use' slot of the killing instruction.
00703     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
00704       MachineInstr *Kill = vi.Kills[i];
00705       unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
00706       LiveRange LR(getMBBStartIdx(Kill->getParent()),
00707                    killIdx, ValNo);
00708       interval.addRange(LR);
00709       interval.addKill(ValNo, killIdx, false);
00710       DOUT << " +" << LR;
00711     }
00712 
00713   } else {
00714     // If this is the second time we see a virtual register definition, it
00715     // must be due to phi elimination or two addr elimination.  If this is
00716     // the result of two address elimination, then the vreg is one of the
00717     // def-and-use register operand.
00718     if (mi->isRegTiedToUseOperand(MOIdx)) {
00719       // If this is a two-address definition, then we have already processed
00720       // the live range.  The only problem is that we didn't realize there
00721       // are actually two values in the live interval.  Because of this we
00722       // need to take the LiveRegion that defines this register and split it
00723       // into two values.
00724       assert(interval.containsOneValue());
00725       unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
00726       unsigned RedefIndex = getDefIndex(MIIdx);
00727       if (MO.isEarlyClobber())
00728         RedefIndex = getUseIndex(MIIdx);
00729 
00730       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
00731       VNInfo *OldValNo = OldLR->valno;
00732 
00733       // Delete the initial value, which should be short and continuous,
00734       // because the 2-addr copy must be in the same MBB as the redef.
00735       interval.removeRange(DefIndex, RedefIndex);
00736 
00737       // Two-address vregs should always only be redefined once.  This means
00738       // that at this point, there should be exactly one value number in it.
00739       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
00740 
00741       // The new value number (#1) is defined by the instruction we claimed
00742       // defined value #0.
00743       VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(),
00744                                             false, // update at *
00745                                             VNInfoAllocator);
00746       ValNo->setFlags(OldValNo->getFlags()); // * <- updating here
00747 
00748       // Value#0 is now defined by the 2-addr instruction.
00749       OldValNo->def  = RedefIndex;
00750       OldValNo->setCopy(0);
00751       if (MO.isEarlyClobber())
00752         OldValNo->setHasRedefByEC(true);
00753       
00754       // Add the new live interval which replaces the range for the input copy.
00755       LiveRange LR(DefIndex, RedefIndex, ValNo);
00756       DOUT << " replace range with " << LR;
00757       interval.addRange(LR);
00758       interval.addKill(ValNo, RedefIndex, false);
00759 
00760       // If this redefinition is dead, we need to add a dummy unit live
00761       // range covering the def slot.
00762       if (MO.isDead())
00763         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
00764 
00765       DOUT << " RESULT: ";
00766       interval.print(DOUT, tri_);
00767 
00768     } else {
00769       // Otherwise, this must be because of phi elimination.  If this is the
00770       // first redefinition of the vreg that we have seen, go back and change
00771       // the live range in the PHI block to be a different value number.
00772       if (interval.containsOneValue()) {
00773         assert(vi.Kills.size() == 1 &&
00774                "PHI elimination vreg should have one kill, the PHI itself!");
00775 
00776         // Remove the old range that we now know has an incorrect number.
00777         VNInfo *VNI = interval.getValNumInfo(0);
00778         MachineInstr *Killer = vi.Kills[0];
00779         unsigned Start = getMBBStartIdx(Killer->getParent());
00780         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
00781         DOUT << " Removing [" << Start << "," << End << "] from: ";
00782         interval.print(DOUT, tri_); DOUT << "\n";
00783         interval.removeRange(Start, End);        
00784         assert(interval.ranges.size() == 1 &&
00785                "newly discovered PHI interval has >1 ranges.");
00786         MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber());
00787         interval.addKill(VNI, terminatorGaps[killMBB], true);        
00788         VNI->setHasPHIKill(true);
00789         DOUT << " RESULT: "; interval.print(DOUT, tri_);
00790 
00791         // Replace the interval with one of a NEW value number.  Note that this
00792         // value number isn't actually defined by an instruction, weird huh? :)
00793         LiveRange LR(Start, End,
00794           interval.getNextValue(mbb->getNumber(), 0, false, VNInfoAllocator));
00795         LR.valno->setIsPHIDef(true);
00796         DOUT << " replace range with " << LR;
00797         interval.addRange(LR);
00798         interval.addKill(LR.valno, End, false);
00799         DOUT << " RESULT: "; interval.print(DOUT, tri_);
00800       }
00801 
00802       // In the case of PHI elimination, each variable definition is only
00803       // live until the end of the block.  We've already taken care of the
00804       // rest of the live range.
00805       unsigned defIndex = getDefIndex(MIIdx);
00806       if (MO.isEarlyClobber())
00807         defIndex = getUseIndex(MIIdx);
00808       
00809       VNInfo *ValNo;
00810       MachineInstr *CopyMI = NULL;
00811       unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
00812       if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
00813           mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
00814           mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
00815           tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
00816         CopyMI = mi;
00817       ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
00818       
00819       unsigned killIndex = getMBBEndIdx(mbb) + 1;
00820       LiveRange LR(defIndex, killIndex, ValNo);
00821       interval.addRange(LR);
00822       interval.addKill(ValNo, terminatorGaps[mbb], true);
00823       ValNo->setHasPHIKill(true);
00824       DOUT << " +" << LR;
00825     }
00826   }
00827 
00828   DOUT << '\n';
00829 }
00830 
00831 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
00832                                               MachineBasicBlock::iterator mi,
00833                                               unsigned MIIdx,
00834                                               MachineOperand& MO,
00835                                               LiveInterval &interval,
00836                                               MachineInstr *CopyMI) {
00837   // A physical register cannot be live across basic block, so its
00838   // lifetime must end somewhere in its defining basic block.
00839   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
00840 
00841   unsigned baseIndex = MIIdx;
00842   unsigned start = getDefIndex(baseIndex);
00843   // Earlyclobbers move back one.
00844   if (MO.isEarlyClobber())
00845     start = getUseIndex(MIIdx);
00846   unsigned end = start;
00847 
00848   // If it is not used after definition, it is considered dead at
00849   // the instruction defining it. Hence its interval is:
00850   // [defSlot(def), defSlot(def)+1)
00851   if (MO.isDead()) {
00852     DOUT << " dead";
00853     end = start + 1;
00854     goto exit;
00855   }
00856 
00857   // If it is not dead on definition, it must be killed by a
00858   // subsequent instruction. Hence its interval is:
00859   // [defSlot(def), useSlot(kill)+1)
00860   baseIndex += InstrSlots::NUM;
00861   while (++mi != MBB->end()) {
00862     while (baseIndex / InstrSlots::NUM < i2miMap_.size() &&
00863            getInstructionFromIndex(baseIndex) == 0)
00864       baseIndex += InstrSlots::NUM;
00865     if (mi->killsRegister(interval.reg, tri_)) {
00866       DOUT << " killed";
00867       end = getUseIndex(baseIndex) + 1;
00868       goto exit;
00869     } else {
00870       int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_);
00871       if (DefIdx != -1) {
00872         if (mi->isRegTiedToUseOperand(DefIdx)) {
00873           // Two-address instruction.
00874           end = getDefIndex(baseIndex);
00875           if (mi->getOperand(DefIdx).isEarlyClobber())
00876             end = getUseIndex(baseIndex);
00877         } else {
00878           // Another instruction redefines the register before it is ever read.
00879           // Then the register is essentially dead at the instruction that defines
00880           // it. Hence its interval is:
00881           // [defSlot(def), defSlot(def)+1)
00882           DOUT << " dead";
00883           end = start + 1;
00884         }
00885         goto exit;
00886       }
00887     }
00888     
00889     baseIndex += InstrSlots::NUM;
00890   }
00891   
00892   // The only case we should have a dead physreg here without a killing or
00893   // instruction where we know it's dead is if it is live-in to the function
00894   // and never used. Another possible case is the implicit use of the
00895   // physical register has been deleted by two-address pass.
00896   end = start + 1;
00897 
00898 exit:
00899   assert(start < end && "did not find end of interval?");
00900 
00901   // Already exists? Extend old live interval.
00902   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
00903   bool Extend = OldLR != interval.end();
00904   VNInfo *ValNo = Extend
00905     ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator);
00906   if (MO.isEarlyClobber() && Extend)
00907     ValNo->setHasRedefByEC(true);
00908   LiveRange LR(start, end, ValNo);
00909   interval.addRange(LR);
00910   interval.addKill(LR.valno, end, false);
00911   DOUT << " +" << LR << '\n';
00912 }
00913 
00914 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
00915                                       MachineBasicBlock::iterator MI,
00916                                       unsigned MIIdx,
00917                                       MachineOperand& MO,
00918                                       unsigned MOIdx) {
00919   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
00920     handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
00921                              getOrCreateInterval(MO.getReg()));
00922   else if (allocatableRegs_[MO.getReg()]) {
00923     MachineInstr *CopyMI = NULL;
00924     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
00925     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
00926         MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
00927         MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
00928         tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
00929       CopyMI = MI;
00930     handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
00931                               getOrCreateInterval(MO.getReg()), CopyMI);
00932     // Def of a register also defines its sub-registers.
00933     for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
00934       // If MI also modifies the sub-register explicitly, avoid processing it
00935       // more than once. Do not pass in TRI here so it checks for exact match.
00936       if (!MI->modifiesRegister(*AS))
00937         handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
00938                                   getOrCreateInterval(*AS), 0);
00939   }
00940 }
00941 
00942 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
00943                                          unsigned MIIdx,
00944                                          LiveInterval &interval, bool isAlias) {
00945   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
00946 
00947   // Look for kills, if it reaches a def before it's killed, then it shouldn't
00948   // be considered a livein.
00949   MachineBasicBlock::iterator mi = MBB->begin();
00950   unsigned baseIndex = MIIdx;
00951   unsigned start = baseIndex;
00952   while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 
00953          getInstructionFromIndex(baseIndex) == 0)
00954     baseIndex += InstrSlots::NUM;
00955   unsigned end = baseIndex;
00956   bool SeenDefUse = false;
00957   
00958   while (mi != MBB->end()) {
00959     if (mi->killsRegister(interval.reg, tri_)) {
00960       DOUT << " killed";
00961       end = getUseIndex(baseIndex) + 1;
00962       SeenDefUse = true;
00963       break;
00964     } else if (mi->modifiesRegister(interval.reg, tri_)) {
00965       // Another instruction redefines the register before it is ever read.
00966       // Then the register is essentially dead at the instruction that defines
00967       // it. Hence its interval is:
00968       // [defSlot(def), defSlot(def)+1)
00969       DOUT << " dead";
00970       end = getDefIndex(start) + 1;
00971       SeenDefUse = true;
00972       break;
00973     }
00974 
00975     baseIndex += InstrSlots::NUM;
00976     ++mi;
00977     if (mi != MBB->end()) {
00978       while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 
00979              getInstructionFromIndex(baseIndex) == 0)
00980         baseIndex += InstrSlots::NUM;
00981     }
00982   }
00983 
00984   // Live-in register might not be used at all.
00985   if (!SeenDefUse) {
00986     if (isAlias) {
00987       DOUT << " dead";
00988       end = getDefIndex(MIIdx) + 1;
00989     } else {
00990       DOUT << " live through";
00991       end = baseIndex;
00992     }
00993   }
00994 
00995   VNInfo *vni =
00996     interval.getNextValue(MBB->getNumber(), 0, false, VNInfoAllocator);
00997   vni->setIsPHIDef(true);
00998   LiveRange LR(start, end, vni);
00999   
01000   interval.addRange(LR);
01001   interval.addKill(LR.valno, end, false);
01002   DOUT << " +" << LR << '\n';
01003 }
01004 
01005 /// computeIntervals - computes the live intervals for virtual
01006 /// registers. for some ordering of the machine instructions [1,N] a
01007 /// live interval is an interval [i, j) where 1 <= i <= j < N for
01008 /// which a variable is live
01009 void LiveIntervals::computeIntervals() { 
01010 
01011   DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n"
01012         << "********** Function: "
01013         << ((Value*)mf_->getFunction())->getName() << '\n');
01014 
01015   SmallVector<unsigned, 8> UndefUses;
01016   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
01017        MBBI != E; ++MBBI) {
01018     MachineBasicBlock *MBB = MBBI;
01019     // Track the index of the current machine instr.
01020     unsigned MIIndex = getMBBStartIdx(MBB);
01021     DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
01022 
01023     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
01024 
01025     // Create intervals for live-ins to this BB first.
01026     for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
01027            LE = MBB->livein_end(); LI != LE; ++LI) {
01028       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
01029       // Multiple live-ins can alias the same register.
01030       for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
01031         if (!hasInterval(*AS))
01032           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
01033                                true);
01034     }
01035     
01036     // Skip over empty initial indices.
01037     while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
01038            getInstructionFromIndex(MIIndex) == 0)
01039       MIIndex += InstrSlots::NUM;
01040     
01041     for (; MI != miEnd; ++MI) {
01042       DOUT << MIIndex << "\t" << *MI;
01043 
01044       // Handle defs.
01045       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
01046         MachineOperand &MO = MI->getOperand(i);
01047         if (!MO.isReg() || !MO.getReg())
01048           continue;
01049 
01050         // handle register defs - build intervals
01051         if (MO.isDef())
01052           handleRegisterDef(MBB, MI, MIIndex, MO, i);
01053         else if (MO.isUndef())
01054           UndefUses.push_back(MO.getReg());
01055       }
01056 
01057       // Skip over the empty slots after each instruction.
01058       unsigned Slots = MI->getDesc().getNumDefs();
01059       if (Slots == 0)
01060         Slots = 1;
01061       MIIndex += InstrSlots::NUM * Slots;
01062       
01063       // Skip over empty indices.
01064       while (MIIndex / InstrSlots::NUM < i2miMap_.size() &&
01065              getInstructionFromIndex(MIIndex) == 0)
01066         MIIndex += InstrSlots::NUM;
01067     }
01068   }
01069 
01070   // Create empty intervals for registers defined by implicit_def's (except
01071   // for those implicit_def that define values which are liveout of their
01072   // blocks.
01073   for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
01074     unsigned UndefReg = UndefUses[i];
01075     (void)getOrCreateInterval(UndefReg);
01076   }
01077 }
01078 
01079 bool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End,
01080                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
01081   std::vector<IdxMBBPair>::const_iterator I =
01082     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
01083 
01084   bool ResVal = false;
01085   while (I != Idx2MBBMap.end()) {
01086     if (I->first >= End)
01087       break;
01088     MBBs.push_back(I->second);
01089     ResVal = true;
01090     ++I;
01091   }
01092   return ResVal;
01093 }
01094 
01095 bool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End,
01096                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
01097   std::vector<IdxMBBPair>::const_iterator I =
01098     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
01099 
01100   bool ResVal = false;
01101   while (I != Idx2MBBMap.end()) {
01102     if (I->first > End)
01103       break;
01104     MachineBasicBlock *MBB = I->second;
01105     if (getMBBEndIdx(MBB) > End)
01106       break;
01107     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
01108            SE = MBB->succ_end(); SI != SE; ++SI)
01109       MBBs.push_back(*SI);
01110     ResVal = true;
01111     ++I;
01112   }
01113   return ResVal;
01114 }
01115 
01116 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
01117   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
01118   return new LiveInterval(reg, Weight);
01119 }
01120 
01121 /// dupInterval - Duplicate a live interval. The caller is responsible for
01122 /// managing the allocated memory.
01123 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
01124   LiveInterval *NewLI = createInterval(li->reg);
01125   NewLI->Copy(*li, mri_, getVNInfoAllocator());
01126   return NewLI;
01127 }
01128 
01129 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
01130 /// copy field and returns the source register that defines it.
01131 unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
01132   if (!VNI->getCopy())
01133     return 0;
01134 
01135   if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
01136     // If it's extracting out of a physical register, return the sub-register.
01137     unsigned Reg = VNI->getCopy()->getOperand(1).getReg();
01138     if (TargetRegisterInfo::isPhysicalRegister(Reg))
01139       Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm());
01140     return Reg;
01141   } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
01142              VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
01143     return VNI->getCopy()->getOperand(2).getReg();
01144 
01145   unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
01146   if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg))
01147     return SrcReg;
01148   llvm_unreachable("Unrecognized copy instruction!");
01149   return 0;
01150 }
01151 
01152 //===----------------------------------------------------------------------===//
01153 // Register allocator hooks.
01154 //
01155 
01156 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
01157 /// allow one) virtual register operand, then its uses are implicitly using
01158 /// the register. Returns the virtual register.
01159 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
01160                                             MachineInstr *MI) const {
01161   unsigned RegOp = 0;
01162   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
01163     MachineOperand &MO = MI->getOperand(i);
01164     if (!MO.isReg() || !MO.isUse())
01165       continue;
01166     unsigned Reg = MO.getReg();
01167     if (Reg == 0 || Reg == li.reg)
01168       continue;
01169     
01170     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
01171         !allocatableRegs_[Reg])
01172       continue;
01173     // FIXME: For now, only remat MI with at most one register operand.
01174     assert(!RegOp &&
01175            "Can't rematerialize instruction with multiple register operand!");
01176     RegOp = MO.getReg();
01177 #ifndef NDEBUG
01178     break;
01179 #endif
01180   }
01181   return RegOp;
01182 }
01183 
01184 /// isValNoAvailableAt - Return true if the val# of the specified interval
01185 /// which reaches the given instruction also reaches the specified use index.
01186 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
01187                                        unsigned UseIdx) const {
01188   unsigned Index = getInstructionIndex(MI);  
01189   VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
01190   LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
01191   return UI != li.end() && UI->valno == ValNo;
01192 }
01193 
01194 /// isReMaterializable - Returns true if the definition MI of the specified
01195 /// val# of the specified interval is re-materializable.
01196 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
01197                                        const VNInfo *ValNo, MachineInstr *MI,
01198                                        SmallVectorImpl<LiveInterval*> &SpillIs,
01199                                        bool &isLoad) {
01200   if (DisableReMat)
01201     return false;
01202 
01203   if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
01204     return true;
01205 
01206   int FrameIdx = 0;
01207   if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
01208       mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
01209     // FIXME: Let target specific isReallyTriviallyReMaterializable determines
01210     // this but remember this is not safe to fold into a two-address
01211     // instruction.
01212     // This is a load from fixed stack slot. It can be rematerialized.
01213     return true;
01214 
01215   // If the target-specific rules don't identify an instruction as
01216   // being trivially rematerializable, use some target-independent
01217   // rules.
01218   if (!MI->getDesc().isRematerializable() ||
01219       !tii_->isTriviallyReMaterializable(MI)) {
01220     if (!EnableAggressiveRemat)
01221       return false;
01222 
01223     // If the instruction accesses memory but the memoperands have been lost,
01224     // we can't analyze it.
01225     const TargetInstrDesc &TID = MI->getDesc();
01226     if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty())
01227       return false;
01228 
01229     // Avoid instructions obviously unsafe for remat.
01230     if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable())
01231       return false;
01232 
01233     // If the instruction accesses memory and the memory could be non-constant,
01234     // assume the instruction is not rematerializable.
01235     for (std::list<MachineMemOperand>::const_iterator
01236            I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){
01237       const MachineMemOperand &MMO = *I;
01238       if (MMO.isVolatile() || MMO.isStore())
01239         return false;
01240       const Value *V = MMO.getValue();
01241       if (!V)
01242         return false;
01243       if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
01244         if (!PSV->isConstant(mf_->getFrameInfo()))
01245           return false;
01246       } else if (!aa_->pointsToConstantMemory(V))
01247         return false;
01248     }
01249 
01250     // If any of the registers accessed are non-constant, conservatively assume
01251     // the instruction is not rematerializable.
01252     unsigned ImpUse = 0;
01253     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
01254       const MachineOperand &MO = MI->getOperand(i);
01255       if (MO.isReg()) {
01256         unsigned Reg = MO.getReg();
01257         if (Reg == 0)
01258           continue;
01259         if (TargetRegisterInfo::isPhysicalRegister(Reg))
01260           return false;
01261 
01262         // Only allow one def, and that in the first operand.
01263         if (MO.isDef() != (i == 0))
01264           return false;
01265 
01266         // Only allow constant-valued registers.
01267         bool IsLiveIn = mri_->isLiveIn(Reg);
01268         MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg),
01269                                           E = mri_->def_end();
01270 
01271         // For the def, it should be the only def of that register.
01272         if (MO.isDef() && (next(I) != E || IsLiveIn))
01273           return false;
01274 
01275         if (MO.isUse()) {
01276           // Only allow one use other register use, as that's all the
01277           // remat mechanisms support currently.
01278           if (Reg != li.reg) {
01279             if (ImpUse == 0)
01280               ImpUse = Reg;
01281             else if (Reg != ImpUse)
01282               return false;
01283           }
01284           // For the use, there should be only one associated def.
01285           if (I != E && (next(I) != E || IsLiveIn))
01286             return false;
01287         }
01288       }
01289     }
01290   }
01291 
01292   unsigned ImpUse = getReMatImplicitUse(li, MI);
01293   if (ImpUse) {
01294     const LiveInterval &ImpLi = getInterval(ImpUse);
01295     for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
01296            re = mri_->use_end(); ri != re; ++ri) {
01297       MachineInstr *UseMI = &*ri;
01298       unsigned UseIdx = getInstructionIndex(UseMI);
01299       if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
01300         continue;
01301       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
01302         return false;
01303     }
01304 
01305     // If a register operand of the re-materialized instruction is going to
01306     // be spilled next, then it's not legal to re-materialize this instruction.
01307     for (unsigned i = 0, e = SpillIs.size(); i != e; ++i)
01308       if (ImpUse == SpillIs[i]->reg)
01309         return false;
01310   }
01311   return true;
01312 }
01313 
01314 /// isReMaterializable - Returns true if the definition MI of the specified
01315 /// val# of the specified interval is re-materializable.
01316 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
01317                                        const VNInfo *ValNo, MachineInstr *MI) {
01318   SmallVector<LiveInterval*, 4> Dummy1;
01319   bool Dummy2;
01320   return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2);
01321 }
01322 
01323 /// isReMaterializable - Returns true if every definition of MI of every
01324 /// val# of the specified interval is re-materializable.
01325 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
01326                                        SmallVectorImpl<LiveInterval*> &SpillIs,
01327                                        bool &isLoad) {
01328   isLoad = false;
01329   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
01330        i != e; ++i) {
01331     const VNInfo *VNI = *i;
01332     if (VNI->isUnused())
01333       continue; // Dead val#.
01334     // Is the def for the val# rematerializable?
01335     if (!VNI->isDefAccurate())
01336       return false;
01337     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
01338     bool DefIsLoad = false;
01339     if (!ReMatDefMI ||
01340         !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
01341       return false;
01342     isLoad |= DefIsLoad;
01343   }
01344   return true;
01345 }
01346 
01347 /// FilterFoldedOps - Filter out two-address use operands. Return
01348 /// true if it finds any issue with the operands that ought to prevent
01349 /// folding.
01350 static bool FilterFoldedOps(MachineInstr *MI,
01351                             SmallVector<unsigned, 2> &Ops,
01352                             unsigned &MRInfo,
01353                             SmallVector<unsigned, 2> &FoldOps) {
01354   MRInfo = 0;
01355   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
01356     unsigned OpIdx = Ops[i];
01357     MachineOperand &MO = MI->getOperand(OpIdx);
01358     // FIXME: fold subreg use.
01359     if (MO.getSubReg())
01360       return true;
01361     if (MO.isDef())
01362       MRInfo |= (unsigned)VirtRegMap::isMod;
01363     else {
01364       // Filter out two-address use operand(s).
01365       if (MI->isRegTiedToDefOperand(OpIdx)) {
01366         MRInfo = VirtRegMap::isModRef;
01367         continue;
01368       }
01369       MRInfo |= (unsigned)VirtRegMap::isRef;
01370     }
01371     FoldOps.push_back(OpIdx);
01372   }
01373   return false;
01374 }
01375                            
01376 
01377 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
01378 /// slot / to reg or any rematerialized load into ith operand of specified
01379 /// MI. If it is successul, MI is updated with the newly created MI and
01380 /// returns true.
01381 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
01382                                          VirtRegMap &vrm, MachineInstr *DefMI,
01383                                          unsigned InstrIdx,
01384                                          SmallVector<unsigned, 2> &Ops,
01385                                          bool isSS, int Slot, unsigned Reg) {
01386   // If it is an implicit def instruction, just delete it.
01387   if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
01388     RemoveMachineInstrFromMaps(MI);
01389     vrm.RemoveMachineInstrFromMaps(MI);
01390     MI->eraseFromParent();
01391     ++numFolds;
01392     return true;
01393   }
01394 
01395   // Filter the list of operand indexes that are to be folded. Abort if
01396   // any operand will prevent folding.
01397   unsigned MRInfo = 0;
01398   SmallVector<unsigned, 2> FoldOps;
01399   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
01400     return false;
01401 
01402   // The only time it's safe to fold into a two address instruction is when
01403   // it's folding reload and spill from / into a spill stack slot.
01404   if (DefMI && (MRInfo & VirtRegMap::isMod))
01405     return false;
01406 
01407   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
01408                            : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
01409   if (fmi) {
01410     // Remember this instruction uses the spill slot.
01411     if (isSS) vrm.addSpillSlotUse(Slot, fmi);
01412 
01413     // Attempt to fold the memory reference into the instruction. If
01414     // we can do this, we don't need to insert spill code.
01415     MachineBasicBlock &MBB = *MI->getParent();
01416     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
01417       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
01418     vrm.transferSpillPts(MI, fmi);
01419     vrm.transferRestorePts(MI, fmi);
01420     vrm.transferEmergencySpills(MI, fmi);
01421     mi2iMap_.erase(MI);
01422     i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
01423     mi2iMap_[fmi] = InstrIdx;
01424     MI = MBB.insert(MBB.erase(MI), fmi);
01425     ++numFolds;
01426     return true;
01427   }
01428   return false;
01429 }
01430 
01431 /// canFoldMemoryOperand - Returns true if the specified load / store
01432 /// folding is possible.
01433 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
01434                                          SmallVector<unsigned, 2> &Ops,
01435                                          bool ReMat) const {
01436   // Filter the list of operand indexes that are to be folded. Abort if
01437   // any operand will prevent folding.
01438   unsigned MRInfo = 0;
01439   SmallVector<unsigned, 2> FoldOps;
01440   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
01441     return false;
01442 
01443   // It's only legal to remat for a use, not a def.
01444   if (ReMat && (MRInfo & VirtRegMap::isMod))
01445     return false;
01446 
01447   return tii_->canFoldMemoryOperand(MI, FoldOps);
01448 }
01449 
01450 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
01451   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
01452   for (LiveInterval::Ranges::const_iterator
01453          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
01454     std::vector<IdxMBBPair>::const_iterator II =
01455       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
01456     if (II == Idx2MBBMap.end())
01457       continue;
01458     if (I->end > II->first)  // crossing a MBB.
01459       return false;
01460     MBBs.insert(II->second);
01461     if (MBBs.size() > 1)
01462       return false;
01463   }
01464   return true;
01465 }
01466 
01467 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
01468 /// interval on to-be re-materialized operands of MI) with new register.
01469 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
01470                                        MachineInstr *MI, unsigned NewVReg,
01471                                        VirtRegMap &vrm) {
01472   // There is an implicit use. That means one of the other operand is
01473   // being remat'ed and the remat'ed instruction has li.reg as an
01474   // use operand. Make sure we rewrite that as well.
01475   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
01476     MachineOperand &MO = MI->getOperand(i);
01477     if (!MO.isReg())
01478       continue;
01479     unsigned Reg = MO.getReg();
01480     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
01481       continue;
01482     if (!vrm.isReMaterialized(Reg))
01483       continue;
01484     MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
01485     MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
01486     if (UseMO)
01487       UseMO->setReg(NewVReg);
01488   }
01489 }
01490 
01491 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
01492 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
01493 bool LiveIntervals::
01494 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
01495                  bool TrySplit, unsigned index, unsigned end,  MachineInstr *MI,
01496                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
01497                  unsigned Slot, int LdSlot,
01498                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
01499                  VirtRegMap &vrm,
01500                  const TargetRegisterClass* rc,
01501                  SmallVector<int, 4> &ReMatIds,
01502                  const MachineLoopInfo *loopInfo,
01503                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
01504                  DenseMap<unsigned,unsigned> &MBBVRegsMap,
01505                  std::vector<LiveInterval*> &NewLIs) {
01506   bool CanFold = false;
01507  RestartInstruction:
01508   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
01509     MachineOperand& mop = MI->getOperand(i);
01510     if (!mop.isReg())
01511       continue;
01512     unsigned Reg = mop.getReg();
01513     unsigned RegI = Reg;
01514     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
01515       continue;
01516     if (Reg != li.reg)
01517       continue;
01518 
01519     bool TryFold = !DefIsReMat;
01520     bool FoldSS = true; // Default behavior unless it's a remat.
01521     int FoldSlot = Slot;
01522     if (DefIsReMat) {
01523       // If this is the rematerializable definition MI itself and
01524       // all of its uses are rematerialized, simply delete it.
01525       if (MI == ReMatOrigDefMI && CanDelete) {
01526         DOUT << "\t\t\t\tErasing re-materlizable def: ";
01527         DOUT << MI << '\n';
01528         RemoveMachineInstrFromMaps(MI);
01529         vrm.RemoveMachineInstrFromMaps(MI);
01530         MI->eraseFromParent();
01531         break;
01532       }
01533 
01534       // If def for this use can't be rematerialized, then try folding.
01535       // If def is rematerializable and it's a load, also try folding.
01536       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
01537       if (isLoad) {
01538         // Try fold loads (from stack slot, constant pool, etc.) into uses.
01539         FoldSS = isLoadSS;
01540         FoldSlot = LdSlot;
01541       }
01542     }
01543 
01544     // Scan all of the operands of this instruction rewriting operands
01545     // to use NewVReg instead of li.reg as appropriate.  We do this for
01546     // two reasons:
01547     //
01548     //   1. If the instr reads the same spilled vreg multiple times, we
01549     //      want to reuse the NewVReg.
01550     //   2. If the instr is a two-addr instruction, we are required to
01551     //      keep the src/dst regs pinned.
01552     //
01553     // Keep track of whether we replace a use and/or def so that we can
01554     // create the spill interval with the appropriate range. 
01555 
01556     HasUse = mop.isUse();
01557     HasDef = mop.isDef();
01558     SmallVector<unsigned, 2> Ops;
01559     Ops.push_back(i);
01560     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
01561       const MachineOperand &MOj = MI->getOperand(j);
01562       if (!MOj.isReg())
01563         continue;
01564       unsigned RegJ = MOj.getReg();
01565       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
01566         continue;
01567       if (RegJ == RegI) {
01568         Ops.push_back(j);
01569         if (!MOj.isUndef()) {
01570           HasUse |= MOj.isUse();
01571           HasDef |= MOj.isDef();
01572         }
01573       }
01574     }
01575 
01576     // Create a new virtual register for the spill interval.
01577     // Create the new register now so we can map the fold instruction
01578     // to the new register so when it is unfolded we get the correct
01579     // answer.
01580     bool CreatedNewVReg = false;
01581     if (NewVReg == 0) {
01582       NewVReg = mri_->createVirtualRegister(rc);
01583       vrm.grow();
01584       CreatedNewVReg = true;
01585     }
01586 
01587     if (!TryFold)
01588       CanFold = false;
01589     else {
01590       // Do not fold load / store here if we are splitting. We'll find an
01591       // optimal point to insert a load / store later.
01592       if (!TrySplit) {
01593         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
01594                                  Ops, FoldSS, FoldSlot, NewVReg)) {
01595           // Folding the load/store can completely change the instruction in
01596           // unpredictable ways, rescan it from the beginning.
01597 
01598           if (FoldSS) {
01599             // We need to give the new vreg the same stack slot as the
01600             // spilled interval.
01601             vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
01602           }
01603 
01604           HasUse = false;
01605           HasDef = false;
01606           CanFold = false;
01607           if (isNotInMIMap(MI))
01608             break;
01609           goto RestartInstruction;
01610         }
01611       } else {
01612         // We'll try to fold it later if it's profitable.
01613         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
01614       }
01615     }
01616 
01617     mop.setReg(NewVReg);
01618     if (mop.isImplicit())
01619       rewriteImplicitOps(li, MI, NewVReg, vrm);
01620 
01621     // Reuse NewVReg for other reads.
01622     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
01623       MachineOperand &mopj = MI->getOperand(Ops[j]);
01624       mopj.setReg(NewVReg);
01625       if (mopj.isImplicit())
01626         rewriteImplicitOps(li, MI, NewVReg, vrm);
01627     }
01628             
01629     if (CreatedNewVReg) {
01630       if (DefIsReMat) {
01631         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
01632         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
01633           // Each valnum may have its own remat id.
01634           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
01635         } else {
01636           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
01637         }
01638         if (!CanDelete || (HasUse && HasDef)) {
01639           // If this is a two-addr instruction then its use operands are
01640           // rematerializable but its def is not. It should be assigned a
01641           // stack slot.
01642           vrm.assignVirt2StackSlot(NewVReg, Slot);
01643         }
01644       } else {
01645         vrm.assignVirt2StackSlot(NewVReg, Slot);
01646       }
01647     } else if (HasUse && HasDef &&
01648                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
01649       // If this interval hasn't been assigned a stack slot (because earlier
01650       // def is a deleted remat def), do it now.
01651       assert(Slot != VirtRegMap::NO_STACK_SLOT);
01652       vrm.assignVirt2StackSlot(NewVReg, Slot);
01653     }
01654 
01655     // Re-matting an instruction with virtual register use. Add the
01656     // register as an implicit use on the use MI.
01657     if (DefIsReMat && ImpUse)
01658       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
01659 
01660     // Create a new register interval for this spill / remat.
01661     LiveInterval &nI = getOrCreateInterval(NewVReg);
01662     if (CreatedNewVReg) {
01663       NewLIs.push_back(&nI);
01664       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
01665       if (TrySplit)
01666         vrm.setIsSplitFromReg(NewVReg, li.reg);
01667     }
01668 
01669     if (HasUse) {
01670       if (CreatedNewVReg) {
01671         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
01672                      nI.getNextValue(0, 0, false, VNInfoAllocator));
01673         DOUT << " +" << LR;
01674         nI.addRange(LR);
01675       } else {
01676         // Extend the split live interval to this def / use.
01677         unsigned End = getUseIndex(index)+1;
01678         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
01679                      nI.getValNumInfo(nI.getNumValNums()-1));
01680         DOUT << " +" << LR;
01681         nI.addRange(LR);
01682       }
01683     }
01684     if (HasDef) {
01685       LiveRange LR(getDefIndex(index), getStoreIndex(index),
01686                    nI.getNextValue(0, 0, false, VNInfoAllocator));
01687       DOUT << " +" << LR;
01688       nI.addRange(LR);
01689     }
01690 
01691     DOUT << "\t\t\t\tAdded new interval: ";
01692     nI.print(DOUT, tri_);
01693     DOUT << '\n';
01694   }
01695   return CanFold;
01696 }
01697 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
01698                                    const VNInfo *VNI,
01699                                    MachineBasicBlock *MBB, unsigned Idx) const {
01700   unsigned End = getMBBEndIdx(MBB);
01701   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
01702     if (VNI->kills[j].isPHIKill)
01703       continue;
01704 
01705     unsigned KillIdx = VNI->kills[j].killIdx;
01706     if (KillIdx > Idx && KillIdx < End)
01707       return true;
01708   }
01709   return false;
01710 }
01711 
01712 /// RewriteInfo - Keep track of machine instrs that will be rewritten
01713 /// during spilling.
01714 namespace {
01715   struct RewriteInfo {
01716     unsigned Index;
01717     MachineInstr *MI;
01718     bool HasUse;
01719     bool HasDef;
01720     RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
01721       : Index(i), MI(mi), HasUse(u), HasDef(d) {}
01722   };
01723 
01724   struct RewriteInfoCompare {
01725     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
01726       return LHS.Index < RHS.Index;
01727     }
01728   };
01729 }
01730 
01731 void LiveIntervals::
01732 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
01733                     LiveInterval::Ranges::const_iterator &I,
01734                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
01735                     unsigned Slot, int LdSlot,
01736                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
01737                     VirtRegMap &vrm,
01738                     const TargetRegisterClass* rc,
01739                     SmallVector<int, 4> &ReMatIds,
01740                     const MachineLoopInfo *loopInfo,
01741                     BitVector &SpillMBBs,
01742                     DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
01743                     BitVector &RestoreMBBs,
01744                     DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
01745                     DenseMap<unsigned,unsigned> &MBBVRegsMap,
01746                     std::vector<LiveInterval*> &NewLIs) {
01747   bool AllCanFold = true;
01748   unsigned NewVReg = 0;
01749   unsigned start = getBaseIndex(I->start);
01750   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
01751 
01752   // First collect all the def / use in this live range that will be rewritten.
01753   // Make sure they are sorted according to instruction index.
01754   std::vector<RewriteInfo> RewriteMIs;
01755   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
01756          re = mri_->reg_end(); ri != re; ) {
01757     MachineInstr *MI = &*ri;
01758     MachineOperand &O = ri.getOperand();
01759     ++ri;
01760     assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
01761     unsigned index = getInstructionIndex(MI);
01762     if (index < start || index >= end)
01763       continue;
01764 
01765     if (O.isUndef())
01766       // Must be defined by an implicit def. It should not be spilled. Note,
01767       // this is for correctness reason. e.g.
01768       // 8   %reg1024<def> = IMPLICIT_DEF
01769       // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
01770       // The live range [12, 14) are not part of the r1024 live interval since
01771       // it's defined by an implicit def. It will not conflicts with live
01772       // interval of r1025. Now suppose both registers are spilled, you can
01773       // easily see a situation where both registers are reloaded before
01774       // the INSERT_SUBREG and both target registers that would overlap.
01775       continue;
01776     RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
01777   }
01778   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
01779 
01780   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
01781   // Now rewrite the defs and uses.
01782   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
01783     RewriteInfo &rwi = RewriteMIs[i];
01784     ++i;
01785     unsigned index = rwi.Index;
01786     bool MIHasUse = rwi.HasUse;
01787     bool MIHasDef = rwi.HasDef;
01788     MachineInstr *MI = rwi.MI;
01789     // If MI def and/or use the same register multiple times, then there
01790     // are multiple entries.
01791     unsigned NumUses = MIHasUse;
01792     while (i != e && RewriteMIs[i].MI == MI) {
01793       assert(RewriteMIs[i].Index == index);
01794       bool isUse = RewriteMIs[i].HasUse;
01795       if (isUse) ++NumUses;
01796       MIHasUse |= isUse;
01797       MIHasDef |= RewriteMIs[i].HasDef;
01798       ++i;
01799     }
01800     MachineBasicBlock *MBB = MI->getParent();
01801 
01802     if (ImpUse && MI != ReMatDefMI) {
01803       // Re-matting an instruction with virtual register use. Update the
01804       // register interval's spill weight to HUGE_VALF to prevent it from
01805       // being spilled.
01806       LiveInterval &ImpLi = getInterval(ImpUse);
01807       ImpLi.weight = HUGE_VALF;
01808     }
01809 
01810     unsigned MBBId = MBB->getNumber();
01811     unsigned ThisVReg = 0;
01812     if (TrySplit) {
01813       DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
01814       if (NVI != MBBVRegsMap.end()) {
01815         ThisVReg = NVI->second;
01816         // One common case:
01817         // x = use
01818         // ...
01819         // ...
01820         // def = ...
01821         //     = use
01822         // It's better to start a new interval to avoid artifically
01823         // extend the new interval.
01824         if (MIHasDef && !MIHasUse) {
01825           MBBVRegsMap.erase(MBB->getNumber());
01826           ThisVReg = 0;
01827         }
01828       }
01829     }
01830 
01831     bool IsNew = ThisVReg == 0;
01832     if (IsNew) {
01833       // This ends the previous live interval. If all of its def / use
01834       // can be folded, give it a low spill weight.
01835       if (NewVReg && TrySplit && AllCanFold) {
01836         LiveInterval &nI = getOrCreateInterval(NewVReg);
01837         nI.weight /= 10.0F;
01838       }
01839       AllCanFold = true;
01840     }
01841     NewVReg = ThisVReg;
01842 
01843     bool HasDef = false;
01844     bool HasUse = false;
01845     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
01846                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
01847                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
01848                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
01849                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
01850     if (!HasDef && !HasUse)
01851       continue;
01852 
01853     AllCanFold &= CanFold;
01854 
01855     // Update weight of spill interval.
01856     LiveInterval &nI = getOrCreateInterval(NewVReg);
01857     if (!TrySplit) {
01858       // The spill weight is now infinity as it cannot be spilled again.
01859       nI.weight = HUGE_VALF;
01860       continue;
01861     }
01862 
01863     // Keep track of the last def and first use in each MBB.
01864     if (HasDef) {
01865       if (MI != ReMatOrigDefMI || !CanDelete) {
01866         bool HasKill = false;
01867         if (!HasUse)
01868           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
01869         else {
01870           // If this is a two-address code, then this index starts a new VNInfo.
01871           const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
01872           if (VNI)
01873             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
01874         }
01875         DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
01876           SpillIdxes.find(MBBId);
01877         if (!HasKill) {
01878           if (SII == SpillIdxes.end()) {
01879             std::vector<SRInfo> S;
01880             S.push_back(SRInfo(index, NewVReg, true));
01881             SpillIdxes.insert(std::make_pair(MBBId, S));
01882           } else if (SII->second.back().vreg != NewVReg) {
01883             SII->second.push_back(SRInfo(index, NewVReg, true));
01884           } else if ((int)index > SII->second.back().index) {
01885             // If there is an earlier def and this is a two-address
01886             // instruction, then it's not possible to fold the store (which
01887             // would also fold the load).
01888             SRInfo &Info = SII->second.back();
01889             Info.index = index;
01890             Info.canFold = !HasUse;
01891           }
01892           SpillMBBs.set(MBBId);
01893         } else if (SII != SpillIdxes.end() &&
01894                    SII->second.back().vreg == NewVReg &&
01895                    (int)index > SII->second.back().index) {
01896           // There is an earlier def that's not killed (must be two-address).
01897           // The spill is no longer needed.
01898           SII->second.pop_back();
01899           if (SII->second.empty()) {
01900             SpillIdxes.erase(MBBId);
01901             SpillMBBs.reset(MBBId);
01902           }
01903         }
01904       }
01905     }
01906 
01907     if (HasUse) {
01908       DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
01909         SpillIdxes.find(MBBId);
01910       if (SII != SpillIdxes.end() &&
01911           SII->second.back().vreg == NewVReg &&
01912           (int)index > SII->second.back().index)
01913         // Use(s) following the last def, it's not safe to fold the spill.
01914         SII->second.back().canFold = false;
01915       DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
01916         RestoreIdxes.find(MBBId);
01917       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
01918         // If we are splitting live intervals, only fold if it's the first
01919         // use and there isn't another use later in the MBB.
01920         RII->second.back().canFold = false;
01921       else if (IsNew) {
01922         // Only need a reload if there isn't an earlier def / use.
01923         if (RII == RestoreIdxes.end()) {
01924           std::vector<SRInfo> Infos;
01925           Infos.push_back(SRInfo(index, NewVReg, true));
01926           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
01927         } else {
01928           RII->second.push_back(SRInfo(index, NewVReg, true));
01929         }
01930         RestoreMBBs.set(MBBId);
01931       }
01932     }
01933 
01934     // Update spill weight.
01935     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
01936     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
01937   }
01938 
01939   if (NewVReg && TrySplit && AllCanFold) {
01940     // If all of its def / use can be folded, give it a low spill weight.
01941     LiveInterval &nI = getOrCreateInterval(NewVReg);
01942     nI.weight /= 10.0F;
01943   }
01944 }
01945 
01946 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
01947                         BitVector &RestoreMBBs,
01948                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
01949   if (!RestoreMBBs[Id])
01950     return false;
01951   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
01952   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
01953     if (Restores[i].index == index &&
01954         Restores[i].vreg == vr &&
01955         Restores[i].canFold)
01956       return true;
01957   return false;
01958 }
01959 
01960 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
01961                         BitVector &RestoreMBBs,
01962                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
01963   if (!RestoreMBBs[Id])
01964     return;
01965   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
01966   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
01967     if (Restores[i].index == index && Restores[i].vreg)
01968       Restores[i].index = -1;
01969 }
01970 
01971 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
01972 /// spilled and create empty intervals for their uses.
01973 void
01974 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
01975                                     const TargetRegisterClass* rc,
01976                                     std::vector<LiveInterval*> &NewLIs) {
01977   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
01978          re = mri_->reg_end(); ri != re; ) {
01979     MachineOperand &O = ri.getOperand();
01980     MachineInstr *MI = &*ri;
01981     ++ri;
01982     if (O.isDef()) {
01983       assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
01984              "Register def was not rewritten?");
01985       RemoveMachineInstrFromMaps(MI);
01986       vrm.RemoveMachineInstrFromMaps(MI);
01987       MI->eraseFromParent();
01988     } else {
01989       // This must be an use of an implicit_def so it's not part of the live
01990       // interval. Create a new empty live interval for it.
01991       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
01992       unsigned NewVReg = mri_->createVirtualRegister(rc);
01993       vrm.grow();
01994       vrm.setIsImplicitlyDefined(NewVReg);
01995       NewLIs.push_back(&getOrCreateInterval(NewVReg));
01996       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
01997         MachineOperand &MO = MI->getOperand(i);
01998         if (MO.isReg() && MO.getReg() == li.reg) {
01999           MO.setReg(NewVReg);
02000           MO.setIsUndef();
02001         }
02002       }
02003     }
02004   }
02005 }
02006 
02007 std::vector<LiveInterval*> LiveIntervals::
02008 addIntervalsForSpillsFast(const LiveInterval &li,
02009                           const MachineLoopInfo *loopInfo,
02010                           VirtRegMap &vrm) {
02011   unsigned slot = vrm.assignVirt2StackSlot(li.reg);
02012 
02013   std::vector<LiveInterval*> added;
02014 
02015   assert(li.weight != HUGE_VALF &&
02016          "attempt to spill already spilled interval!");
02017 
02018   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
02019   DEBUG(li.dump());
02020   DOUT << '\n';
02021 
02022   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
02023 
02024   MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg);
02025   while (RI != mri_->reg_end()) {
02026     MachineInstr* MI = &*RI;
02027     
02028     SmallVector<unsigned, 2> Indices;
02029     bool HasUse = false;
02030     bool HasDef = false;
02031     
02032     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
02033       MachineOperand& mop = MI->getOperand(i);
02034       if (!mop.isReg() || mop.getReg() != li.reg) continue;
02035       
02036       HasUse |= MI->getOperand(i).isUse();
02037       HasDef |= MI->getOperand(i).isDef();
02038       
02039       Indices.push_back(i);
02040     }
02041     
02042     if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI),
02043                               Indices, true, slot, li.reg)) {
02044       unsigned NewVReg = mri_->createVirtualRegister(rc);
02045       vrm.grow();
02046       vrm.assignVirt2StackSlot(NewVReg, slot);
02047       
02048       // create a new register for this spill
02049       LiveInterval &nI = getOrCreateInterval(NewVReg);
02050 
02051       // the spill weight is now infinity as it
02052       // cannot be spilled again
02053       nI.weight = HUGE_VALF;
02054       
02055       // Rewrite register operands to use the new vreg.
02056       for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(),
02057            E = Indices.end(); I != E; ++I) {
02058         MI->getOperand(*I).setReg(NewVReg);
02059         
02060         if (MI->getOperand(*I).isUse())
02061           MI->getOperand(*I).setIsKill(true);
02062       }
02063       
02064       // Fill in  the new live interval.
02065       unsigned index = getInstructionIndex(MI);
02066       if (HasUse) {
02067         LiveRange LR(getLoadIndex(index), getUseIndex(index),
02068                      nI.getNextValue(0, 0, false, getVNInfoAllocator()));
02069         DOUT << " +" << LR;
02070         nI.addRange(LR);
02071         vrm.addRestorePoint(NewVReg, MI);
02072       }
02073       if (HasDef) {
02074         LiveRange LR(getDefIndex(index), getStoreIndex(index),
02075                      nI.getNextValue(0, 0, false, getVNInfoAllocator()));
02076         DOUT << " +" << LR;
02077         nI.addRange(LR);
02078         vrm.addSpillPoint(NewVReg, true, MI);
02079       }
02080       
02081       added.push_back(&nI);
02082         
02083       DOUT << "\t\t\t\tadded new interval: ";
02084       DEBUG(nI.dump());
02085       DOUT << '\n';
02086     }
02087     
02088     
02089     RI = mri_->reg_begin(li.reg);
02090   }
02091 
02092   return added;
02093 }
02094 
02095 std::vector<LiveInterval*> LiveIntervals::
02096 addIntervalsForSpills(const LiveInterval &li,
02097                       SmallVectorImpl<LiveInterval*> &SpillIs,
02098                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
02099   
02100   if (EnableFastSpilling)
02101     return addIntervalsForSpillsFast(li, loopInfo, vrm);
02102   
02103   assert(li.weight != HUGE_VALF &&
02104          "attempt to spill already spilled interval!");
02105 
02106   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
02107   li.print(DOUT, tri_);
02108   DOUT << '\n';
02109 
02110   // Each bit specify whether a spill is required in the MBB.
02111   BitVector SpillMBBs(mf_->getNumBlockIDs());
02112   DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
02113   BitVector RestoreMBBs(mf_->getNumBlockIDs());
02114   DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
02115   DenseMap<unsigned,unsigned> MBBVRegsMap;
02116   std::vector<LiveInterval*> NewLIs;
02117   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
02118 
02119   unsigned NumValNums = li.getNumValNums();
02120   SmallVector<MachineInstr*, 4> ReMatDefs;
02121   ReMatDefs.resize(NumValNums, NULL);
02122   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
02123   ReMatOrigDefs.resize(NumValNums, NULL);
02124   SmallVector<int, 4> ReMatIds;
02125   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
02126   BitVector ReMatDelete(NumValNums);
02127   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
02128 
02129   // Spilling a split live interval. It cannot be split any further. Also,
02130   // it's also guaranteed to be a single val# / range interval.
02131   if (vrm.getPreSplitReg(li.reg)) {
02132     vrm.setIsSplitFromReg(li.reg, 0);
02133     // Unset the split kill marker on the last use.
02134     unsigned KillIdx = vrm.getKillPoint(li.reg);
02135     if (KillIdx) {
02136       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
02137       assert(KillMI && "Last use disappeared?");
02138       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
02139       assert(KillOp != -1 && "Last use disappeared?");
02140       KillMI->getOperand(KillOp).setIsKill(false);
02141     }
02142     vrm.removeKillPoint(li.reg);
02143     bool DefIsReMat = vrm.isReMaterialized(li.reg);
02144     Slot = vrm.getStackSlot(li.reg);
02145     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
02146     MachineInstr *ReMatDefMI = DefIsReMat ?
02147       vrm.getReMaterializedMI(li.reg) : NULL;
02148     int LdSlot = 0;
02149     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
02150     bool isLoad = isLoadSS ||
02151       (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
02152     bool IsFirstRange = true;
02153     for (LiveInterval::Ranges::const_iterator
02154            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
02155       // If this is a split live interval with multiple ranges, it means there
02156       // are two-address instructions that re-defined the value. Only the
02157       // first def can be rematerialized!
02158       if (IsFirstRange) {
02159         // Note ReMatOrigDefMI has already been deleted.
02160         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
02161                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
02162                              false, vrm, rc, ReMatIds, loopInfo,
02163                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
02164                              MBBVRegsMap, NewLIs);
02165       } else {
02166         rewriteInstructionsForSpills(li, false, I, NULL, 0,
02167                              Slot, 0, false, false, false,
02168                              false, vrm, rc, ReMatIds, loopInfo,
02169                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
02170                              MBBVRegsMap, NewLIs);
02171       }
02172       IsFirstRange = false;
02173     }
02174 
02175     handleSpilledImpDefs(li, vrm, rc, NewLIs);
02176     return NewLIs;
02177   }
02178 
02179   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
02180   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
02181     TrySplit = false;
02182   if (TrySplit)
02183     ++numSplits;
02184   bool NeedStackSlot = false;
02185   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
02186        i != e; ++i) {
02187     const VNInfo *VNI = *i;
02188     unsigned VN = VNI->id;
02189     if (VNI->isUnused())
02190       continue; // Dead val#.
02191     // Is the def for the val# rematerializable?
02192     MachineInstr *ReMatDefMI = VNI->isDefAccurate()
02193       ? getInstructionFromIndex(VNI->def) : 0;
02194     bool dummy;
02195     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
02196       // Remember how to remat the def of this val#.
02197       ReMatOrigDefs[VN] = ReMatDefMI;
02198       // Original def may be modified so we have to make a copy here.
02199       MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
02200       ClonedMIs.push_back(Clone);
02201       ReMatDefs[VN] = Clone;
02202 
02203       bool CanDelete = true;
02204       if (VNI->hasPHIKill()) {
02205         // A kill is a phi node, not all of its uses can be rematerialized.
02206         // It must not be deleted.
02207         CanDelete = false;
02208         // Need a stack slot if there is any live range where uses cannot be
02209         // rematerialized.
02210         NeedStackSlot = true;
02211       }
02212       if (CanDelete)
02213         ReMatDelete.set(VN);
02214     } else {
02215       // Need a stack slot if there is any live range where uses cannot be
02216       // rematerialized.
02217       NeedStackSlot = true;
02218     }
02219   }
02220 
02221   // One stack slot per live interval.
02222   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
02223     if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
02224       Slot = vrm.assignVirt2StackSlot(li.reg);
02225     
02226     // This case only occurs when the prealloc splitter has already assigned
02227     // a stack slot to this vreg.
02228     else
02229       Slot = vrm.getStackSlot(li.reg);
02230   }
02231 
02232   // Create new intervals and rewrite defs and uses.
02233   for (LiveInterval::Ranges::const_iterator
02234          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
02235     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
02236     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
02237     bool DefIsReMat = ReMatDefMI != NULL;
02238     bool CanDelete = ReMatDelete[I->valno->id];
02239     int LdSlot = 0;
02240     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
02241     bool isLoad = isLoadSS ||
02242       (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
02243     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
02244                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
02245                                CanDelete, vrm, rc, ReMatIds, loopInfo,
02246                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
02247                                MBBVRegsMap, NewLIs);
02248   }
02249 
02250   // Insert spills / restores if we are splitting.
02251   if (!TrySplit) {
02252     handleSpilledImpDefs(li, vrm, rc, NewLIs);
02253     return NewLIs;
02254   }
02255 
02256   SmallPtrSet<LiveInterval*, 4> AddedKill;
02257   SmallVector<unsigned, 2> Ops;
02258   if (NeedStackSlot) {
02259     int Id = SpillMBBs.find_first();
02260     while (Id != -1) {
02261       std::vector<SRInfo> &spills = SpillIdxes[Id];
02262       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
02263         int index = spills[i].index;
02264         unsigned VReg = spills[i].vreg;
02265         LiveInterval &nI = getOrCreateInterval(VReg);
02266         bool isReMat = vrm.isReMaterialized(VReg);
02267         MachineInstr *MI = getInstructionFromIndex(index);
02268         bool CanFold = false;
02269         bool FoundUse = false;
02270         Ops.clear();
02271         if (spills[i].canFold) {
02272           CanFold = true;
02273           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
02274             MachineOperand &MO = MI->getOperand(j);
02275             if (!MO.isReg() || MO.getReg() != VReg)
02276               continue;
02277 
02278             Ops.push_back(j);
02279             if (MO.isDef())
02280               continue;
02281             if (isReMat || 
02282                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
02283                                                 RestoreMBBs, RestoreIdxes))) {
02284               // MI has two-address uses of the same register. If the use
02285               // isn't the first and only use in the BB, then we can't fold
02286               // it. FIXME: Move this to rewriteInstructionsForSpills.
02287               CanFold = false;
02288               break;
02289             }
02290             FoundUse = true;
02291           }
02292         }
02293         // Fold the store into the def if possible.
02294         bool Folded = false;
02295         if (CanFold && !Ops.empty()) {
02296           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
02297             Folded = true;
02298             if (FoundUse) {
02299               // Also folded uses, do not issue a load.
02300               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
02301               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
02302             }
02303             nI.removeRange(getDefIndex(index), getStoreIndex(index));
02304           }
02305         }
02306 
02307         // Otherwise tell the spiller to issue a spill.
02308         if (!Folded) {
02309           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
02310           bool isKill = LR->end == getStoreIndex(index);
02311           if (!MI->registerDefIsDead(nI.reg))
02312             // No need to spill a dead def.
02313             vrm.addSpillPoint(VReg, isKill, MI);
02314           if (isKill)
02315             AddedKill.insert(&nI);
02316         }
02317       }
02318       Id = SpillMBBs.find_next(Id);
02319     }
02320   }
02321 
02322   int Id = RestoreMBBs.find_first();
02323   while (Id != -1) {
02324     std::vector<SRInfo> &restores = RestoreIdxes[Id];
02325     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
02326       int index = restores[i].index;
02327       if (index == -1)
02328         continue;
02329       unsigned VReg = restores[i].vreg;
02330       LiveInterval &nI = getOrCreateInterval(VReg);
02331       bool isReMat = vrm.isReMaterialized(VReg);
02332       MachineInstr *MI = getInstructionFromIndex(index);
02333       bool CanFold = false;
02334       Ops.clear();
02335       if (restores[i].canFold) {
02336         CanFold = true;
02337         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
02338           MachineOperand &MO = MI->getOperand(j);
02339           if (!MO.isReg() || MO.getReg() != VReg)
02340             continue;
02341 
02342           if (MO.isDef()) {
02343             // If this restore were to be folded, it would have been folded
02344             // already.
02345             CanFold = false;
02346             break;
02347           }
02348           Ops.push_back(j);
02349         }
02350       }
02351 
02352       // Fold the load into the use if possible.
02353       bool Folded = false;
02354       if (CanFold && !Ops.empty()) {
02355         if (!isReMat)
02356           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
02357         else {
02358           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
02359           int LdSlot = 0;
02360           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
02361           // If the rematerializable def is a load, also try to fold it.
02362           if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
02363             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
02364                                           Ops, isLoadSS, LdSlot, VReg);
02365           if (!Folded) {
02366             unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
02367             if (ImpUse) {
02368               // Re-matting an instruction with virtual register use. Add the
02369               // register as an implicit use on the use MI and update the register
02370               // interval's spill weight to HUGE_VALF to prevent it from being
02371               // spilled.
02372               LiveInterval &ImpLi = getInterval(ImpUse);
02373               ImpLi.weight = HUGE_VALF;
02374               MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
02375             }
02376           }
02377         }
02378       }
02379       // If folding is not possible / failed, then tell the spiller to issue a
02380       // load / rematerialization for us.
02381       if (Folded)
02382         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
02383       else
02384         vrm.addRestorePoint(VReg, MI);
02385     }
02386     Id = RestoreMBBs.find_next(Id);
02387   }
02388 
02389   // Finalize intervals: add kills, finalize spill weights, and filter out
02390   // dead intervals.
02391   std::vector<LiveInterval*> RetNewLIs;
02392   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
02393     LiveInterval *LI = NewLIs[i];
02394     if (!LI->empty()) {
02395       LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI);
02396       if (!AddedKill.count(LI)) {
02397         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
02398         unsigned LastUseIdx = getBaseIndex(LR->end);
02399         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
02400         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
02401         assert(UseIdx != -1);
02402         if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
02403           LastUse->getOperand(UseIdx).setIsKill();
02404           vrm.addKillPoint(LI->reg, LastUseIdx);
02405         }
02406       }
02407       RetNewLIs.push_back(LI);
02408     }
02409   }
02410 
02411   handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
02412   return RetNewLIs;
02413 }
02414 
02415 /// hasAllocatableSuperReg - Return true if the specified physical register has
02416 /// any super register that's allocatable.
02417 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
02418   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
02419     if (allocatableRegs_[*AS] && hasInterval(*AS))
02420       return true;
02421   return false;
02422 }
02423 
02424 /// getRepresentativeReg - Find the largest super register of the specified
02425 /// physical register.
02426 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
02427   // Find the largest super-register that is allocatable. 
02428   unsigned BestReg = Reg;
02429   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
02430     unsigned SuperReg = *AS;
02431     if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
02432       BestReg = SuperReg;
02433       break;
02434     }
02435   }
02436   return BestReg;
02437 }
02438 
02439 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
02440 /// specified interval that conflicts with the specified physical register.
02441 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
02442                                                    unsigned PhysReg) const {
02443   unsigned NumConflicts = 0;
02444   const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
02445   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
02446          E = mri_->reg_end(); I != E; ++I) {
02447     MachineOperand &O = I.getOperand();
02448     MachineInstr *MI = O.getParent();
02449     unsigned Index = getInstructionIndex(MI);
02450     if (pli.liveAt(Index))
02451       ++NumConflicts;
02452   }
02453   return NumConflicts;
02454 }
02455 
02456 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
02457 /// around all defs and uses of the specified interval. Return true if it
02458 /// was able to cut its interval.
02459 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
02460                                             unsigned PhysReg, VirtRegMap &vrm) {
02461   unsigned SpillReg = getRepresentativeReg(PhysReg);
02462 
02463   for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
02464     // If there are registers which alias PhysReg, but which are not a
02465     // sub-register of the chosen representative super register. Assert
02466     // since we can't handle it yet.
02467     assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
02468            tri_->isSuperRegister(*AS, SpillReg));
02469 
02470   bool Cut = false;
02471   LiveInterval &pli = getInterval(SpillReg);
02472   SmallPtrSet<MachineInstr*, 8> SeenMIs;
02473   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
02474          E = mri_->reg_end(); I != E; ++I) {
02475     MachineOperand &O = I.getOperand();
02476     MachineInstr *MI = O.getParent();
02477     if (SeenMIs.count(MI))
02478       continue;
02479     SeenMIs.insert(MI);
02480     unsigned Index = getInstructionIndex(MI);
02481     if (pli.liveAt(Index)) {
02482       vrm.addEmergencySpill(SpillReg, MI);
02483       unsigned StartIdx = getLoadIndex(Index);
02484       unsigned EndIdx = getStoreIndex(Index)+1;
02485       if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
02486         pli.removeRange(StartIdx, EndIdx);
02487         Cut = true;
02488       } else {
02489         std::string msg;
02490         raw_string_ostream Msg(msg);
02491         Msg << "Ran out of registers during register allocation!";
02492         if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
02493           Msg << "\nPlease check your inline asm statement for invalid "
02494                << "constraints:\n";
02495           MI->print(Msg, tm_);
02496         }
02497         llvm_report_error(Msg.str());
02498       }
02499       for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
02500         if (!hasInterval(*AS))
02501           continue;
02502         LiveInterval &spli = getInterval(*AS);
02503         if (spli.liveAt(Index))
02504           spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
02505       }
02506     }
02507   }
02508   return Cut;
02509 }
02510 
02511 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
02512                                                   MachineInstr* startInst) {
02513   LiveInterval& Interval = getOrCreateInterval(reg);
02514   VNInfo* VN = Interval.getNextValue(
02515             getInstructionIndex(startInst) + InstrSlots::DEF,
02516             startInst, true, getVNInfoAllocator());
02517   VN->setHasPHIKill(true);
02518   VN->kills.push_back(
02519     VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true));
02520   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
02521                getMBBEndIdx(startInst->getParent()) + 1, VN);
02522   Interval.addRange(LR);
02523   
02524   return LR;
02525 }
02526 
02527 raw_ostream &
02528 IntervalPrefixPrinter::operator()(raw_ostream &out,
02529                                   const MachineInstr &instr) const {
02530       return out << liinfo.getInstructionIndex(&instr);
02531 }