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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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/LoopInfo.h"
00023 #include "llvm/CodeGen/LiveVariables.h"
00024 #include "llvm/CodeGen/MachineFrameInfo.h"
00025 #include "llvm/CodeGen/MachineInstr.h"
00026 #include "llvm/CodeGen/Passes.h"
00027 #include "llvm/CodeGen/SSARegMap.h"
00028 #include "llvm/Target/MRegisterInfo.h"
00029 #include "llvm/Target/TargetInstrInfo.h"
00030 #include "llvm/Target/TargetMachine.h"
00031 #include "llvm/Support/CommandLine.h"
00032 #include "llvm/Support/Debug.h"
00033 #include "llvm/ADT/Statistic.h"
00034 #include "llvm/ADT/STLExtras.h"
00035 #include <algorithm>
00036 #include <cmath>
00037 #include <iostream>
00038 using namespace llvm;
00039 
00040 namespace {
00041   RegisterAnalysis<LiveIntervals> X("liveintervals", "Live Interval Analysis");
00042 
00043   static Statistic<> numIntervals
00044   ("liveintervals", "Number of original intervals");
00045 
00046   static Statistic<> numIntervalsAfter
00047   ("liveintervals", "Number of intervals after coalescing");
00048 
00049   static Statistic<> numJoins
00050   ("liveintervals", "Number of interval joins performed");
00051 
00052   static Statistic<> numPeep
00053   ("liveintervals", "Number of identity moves eliminated after coalescing");
00054 
00055   static Statistic<> numFolded
00056   ("liveintervals", "Number of loads/stores folded into instructions");
00057 
00058   static cl::opt<bool>
00059   EnableJoining("join-liveintervals",
00060                 cl::desc("Join compatible live intervals"),
00061                 cl::init(true));
00062 }
00063 
00064 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
00065 {
00066   AU.addRequired<LiveVariables>();
00067   AU.addPreservedID(PHIEliminationID);
00068   AU.addRequiredID(PHIEliminationID);
00069   AU.addRequiredID(TwoAddressInstructionPassID);
00070   AU.addRequired<LoopInfo>();
00071   MachineFunctionPass::getAnalysisUsage(AU);
00072 }
00073 
00074 void LiveIntervals::releaseMemory()
00075 {
00076   mi2iMap_.clear();
00077   i2miMap_.clear();
00078   r2iMap_.clear();
00079   r2rMap_.clear();
00080 }
00081 
00082 
00083 static bool isZeroLengthInterval(LiveInterval *li) {
00084   for (LiveInterval::Ranges::const_iterator
00085          i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
00086     if (i->end - i->start > LiveIntervals::InstrSlots::NUM)
00087       return false;
00088   return true;
00089 }
00090 
00091 
00092 /// runOnMachineFunction - Register allocate the whole function
00093 ///
00094 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
00095   mf_ = &fn;
00096   tm_ = &fn.getTarget();
00097   mri_ = tm_->getRegisterInfo();
00098   tii_ = tm_->getInstrInfo();
00099   lv_ = &getAnalysis<LiveVariables>();
00100   allocatableRegs_ = mri_->getAllocatableSet(fn);
00101   r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg());
00102 
00103   // If this function has any live ins, insert a dummy instruction at the
00104   // beginning of the function that we will pretend "defines" the values.  This
00105   // is to make the interval analysis simpler by providing a number.
00106   if (fn.livein_begin() != fn.livein_end()) {
00107     unsigned FirstLiveIn = fn.livein_begin()->first;
00108 
00109     // Find a reg class that contains this live in.
00110     const TargetRegisterClass *RC = 0;
00111     for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(),
00112            E = mri_->regclass_end(); RCI != E; ++RCI)
00113       if ((*RCI)->contains(FirstLiveIn)) {
00114         RC = *RCI;
00115         break;
00116       }
00117 
00118     MachineInstr *OldFirstMI = fn.begin()->begin();
00119     mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(),
00120                        FirstLiveIn, FirstLiveIn, RC);
00121     assert(OldFirstMI != fn.begin()->begin() &&
00122            "copyRetToReg didn't insert anything!");
00123   }
00124 
00125   // number MachineInstrs
00126   unsigned miIndex = 0;
00127   for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end();
00128        mbb != mbbEnd; ++mbb)
00129     for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
00130          mi != miEnd; ++mi) {
00131       bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second;
00132       assert(inserted && "multiple MachineInstr -> index mappings");
00133       i2miMap_.push_back(mi);
00134       miIndex += InstrSlots::NUM;
00135     }
00136 
00137   // Note intervals due to live-in values.
00138   if (fn.livein_begin() != fn.livein_end()) {
00139     MachineBasicBlock *Entry = fn.begin();
00140     for (MachineFunction::livein_iterator I = fn.livein_begin(),
00141            E = fn.livein_end(); I != E; ++I) {
00142       handlePhysicalRegisterDef(Entry, Entry->begin(),
00143                                 getOrCreateInterval(I->first), 0, 0, true);
00144       for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS)
00145         handlePhysicalRegisterDef(Entry, Entry->begin(),
00146                                   getOrCreateInterval(*AS), 0, 0, true);
00147     }
00148   }
00149 
00150   computeIntervals();
00151 
00152   numIntervals += getNumIntervals();
00153 
00154   DEBUG(std::cerr << "********** INTERVALS **********\n";
00155         for (iterator I = begin(), E = end(); I != E; ++I) {
00156           I->second.print(std::cerr, mri_);
00157           std::cerr << "\n";
00158         });
00159 
00160   // join intervals if requested
00161   if (EnableJoining) joinIntervals();
00162 
00163   numIntervalsAfter += getNumIntervals();
00164 
00165   // perform a final pass over the instructions and compute spill
00166   // weights, coalesce virtual registers and remove identity moves
00167   const LoopInfo& loopInfo = getAnalysis<LoopInfo>();
00168 
00169   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
00170        mbbi != mbbe; ++mbbi) {
00171     MachineBasicBlock* mbb = mbbi;
00172     unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());
00173 
00174     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
00175          mii != mie; ) {
00176       // if the move will be an identity move delete it
00177       unsigned srcReg, dstReg, RegRep;
00178       if (tii_->isMoveInstr(*mii, srcReg, dstReg) &&
00179           (RegRep = rep(srcReg)) == rep(dstReg)) {
00180         // remove from def list
00181         LiveInterval &interval = getOrCreateInterval(RegRep);
00182         // remove index -> MachineInstr and
00183         // MachineInstr -> index mappings
00184         Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii);
00185         if (mi2i != mi2iMap_.end()) {
00186           i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
00187           mi2iMap_.erase(mi2i);
00188         }
00189         mii = mbbi->erase(mii);
00190         ++numPeep;
00191       }
00192       else {
00193         for (unsigned i = 0; i < mii->getNumOperands(); ++i) {
00194           const MachineOperand& mop = mii->getOperand(i);
00195           if (mop.isRegister() && mop.getReg() &&
00196               MRegisterInfo::isVirtualRegister(mop.getReg())) {
00197             // replace register with representative register
00198             unsigned reg = rep(mop.getReg());
00199             mii->getOperand(i).setReg(reg);
00200 
00201             LiveInterval &RegInt = getInterval(reg);
00202             RegInt.weight +=
00203               (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth);
00204           }
00205         }
00206         ++mii;
00207       }
00208     }
00209   }
00210 
00211   for (iterator I = begin(), E = end(); I != E; ++I) {
00212     LiveInterval &li = I->second;
00213     if (MRegisterInfo::isVirtualRegister(li.reg))
00214       // If the live interval legnth is essentially zero, i.e. in every live
00215       // range the use follows def immediately, it doesn't make sense to spill
00216       // it and hope it will be easier to allocate for this li.
00217       if (isZeroLengthInterval(&li))
00218         li.weight = float(HUGE_VAL);
00219   }
00220 
00221   DEBUG(dump());
00222   return true;
00223 }
00224 
00225 /// print - Implement the dump method.
00226 void LiveIntervals::print(std::ostream &O, const Module* ) const {
00227   O << "********** INTERVALS **********\n";
00228   for (const_iterator I = begin(), E = end(); I != E; ++I) {
00229     I->second.print(std::cerr, mri_);
00230     std::cerr << "\n";
00231   }
00232 
00233   O << "********** MACHINEINSTRS **********\n";
00234   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
00235        mbbi != mbbe; ++mbbi) {
00236     O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
00237     for (MachineBasicBlock::iterator mii = mbbi->begin(),
00238            mie = mbbi->end(); mii != mie; ++mii) {
00239       O << getInstructionIndex(mii) << '\t' << *mii;
00240     }
00241   }
00242 }
00243 
00244 std::vector<LiveInterval*> LiveIntervals::
00245 addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
00246   // since this is called after the analysis is done we don't know if
00247   // LiveVariables is available
00248   lv_ = getAnalysisToUpdate<LiveVariables>();
00249 
00250   std::vector<LiveInterval*> added;
00251 
00252   assert(li.weight != HUGE_VAL &&
00253          "attempt to spill already spilled interval!");
00254 
00255   DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: "
00256         << li << '\n');
00257 
00258   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
00259 
00260   for (LiveInterval::Ranges::const_iterator
00261          i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
00262     unsigned index = getBaseIndex(i->start);
00263     unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM;
00264     for (; index != end; index += InstrSlots::NUM) {
00265       // skip deleted instructions
00266       while (index != end && !getInstructionFromIndex(index))
00267         index += InstrSlots::NUM;
00268       if (index == end) break;
00269 
00270       MachineInstr *MI = getInstructionFromIndex(index);
00271 
00272       // NewRegLiveIn - This instruction might have multiple uses of the spilled
00273       // register.  In this case, for the first use, keep track of the new vreg
00274       // that we reload it into.  If we see a second use, reuse this vreg
00275       // instead of creating live ranges for two reloads.
00276       unsigned NewRegLiveIn = 0;
00277 
00278     for_operand:
00279       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
00280         MachineOperand& mop = MI->getOperand(i);
00281         if (mop.isRegister() && mop.getReg() == li.reg) {
00282           if (NewRegLiveIn && mop.isUse()) {
00283             // We already emitted a reload of this value, reuse it for
00284             // subsequent operands.
00285             MI->getOperand(i).setReg(NewRegLiveIn);
00286             DEBUG(std::cerr << "\t\t\t\treused reload into reg" << NewRegLiveIn
00287                             << " for operand #" << i << '\n');
00288           } else if (MachineInstr* fmi = mri_->foldMemoryOperand(MI, i, slot)) {
00289             // Attempt to fold the memory reference into the instruction.  If we
00290             // can do this, we don't need to insert spill code.
00291             if (lv_)
00292               lv_->instructionChanged(MI, fmi);
00293             MachineBasicBlock &MBB = *MI->getParent();
00294             vrm.virtFolded(li.reg, MI, i, fmi);
00295             mi2iMap_.erase(MI);
00296             i2miMap_[index/InstrSlots::NUM] = fmi;
00297             mi2iMap_[fmi] = index;
00298             MI = MBB.insert(MBB.erase(MI), fmi);
00299             ++numFolded;
00300             // Folding the load/store can completely change the instruction in
00301             // unpredictable ways, rescan it from the beginning.
00302             goto for_operand;
00303           } else {
00304             // This is tricky. We need to add information in the interval about
00305             // the spill code so we have to use our extra load/store slots.
00306             //
00307             // If we have a use we are going to have a load so we start the
00308             // interval from the load slot onwards. Otherwise we start from the
00309             // def slot.
00310             unsigned start = (mop.isUse() ?
00311                               getLoadIndex(index) :
00312                               getDefIndex(index));
00313             // If we have a def we are going to have a store right after it so
00314             // we end the interval after the use of the next
00315             // instruction. Otherwise we end after the use of this instruction.
00316             unsigned end = 1 + (mop.isDef() ?
00317                                 getStoreIndex(index) :
00318                                 getUseIndex(index));
00319 
00320             // create a new register for this spill
00321             NewRegLiveIn = mf_->getSSARegMap()->createVirtualRegister(rc);
00322             MI->getOperand(i).setReg(NewRegLiveIn);
00323             vrm.grow();
00324             vrm.assignVirt2StackSlot(NewRegLiveIn, slot);
00325             LiveInterval& nI = getOrCreateInterval(NewRegLiveIn);
00326             assert(nI.empty());
00327 
00328             // the spill weight is now infinity as it
00329             // cannot be spilled again
00330             nI.weight = float(HUGE_VAL);
00331             LiveRange LR(start, end, nI.getNextValue());
00332             DEBUG(std::cerr << " +" << LR);
00333             nI.addRange(LR);
00334             added.push_back(&nI);
00335 
00336             // update live variables if it is available
00337             if (lv_)
00338               lv_->addVirtualRegisterKilled(NewRegLiveIn, MI);
00339             
00340             // If this is a live in, reuse it for subsequent live-ins.  If it's
00341             // a def, we can't do this.
00342             if (!mop.isUse()) NewRegLiveIn = 0;
00343             
00344             DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n');
00345           }
00346         }
00347       }
00348     }
00349   }
00350 
00351   return added;
00352 }
00353 
00354 void LiveIntervals::printRegName(unsigned reg) const
00355 {
00356   if (MRegisterInfo::isPhysicalRegister(reg))
00357     std::cerr << mri_->getName(reg);
00358   else
00359     std::cerr << "%reg" << reg;
00360 }
00361 
00362 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
00363                                              MachineBasicBlock::iterator mi,
00364                                              LiveInterval& interval)
00365 {
00366   DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg));
00367   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
00368 
00369   // Virtual registers may be defined multiple times (due to phi
00370   // elimination and 2-addr elimination).  Much of what we do only has to be
00371   // done once for the vreg.  We use an empty interval to detect the first
00372   // time we see a vreg.
00373   if (interval.empty()) {
00374     // Get the Idx of the defining instructions.
00375     unsigned defIndex = getDefIndex(getInstructionIndex(mi));
00376 
00377     unsigned ValNum = interval.getNextValue();
00378     assert(ValNum == 0 && "First value in interval is not 0?");
00379     ValNum = 0;  // Clue in the optimizer.
00380 
00381     // Loop over all of the blocks that the vreg is defined in.  There are
00382     // two cases we have to handle here.  The most common case is a vreg
00383     // whose lifetime is contained within a basic block.  In this case there
00384     // will be a single kill, in MBB, which comes after the definition.
00385     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
00386       // FIXME: what about dead vars?
00387       unsigned killIdx;
00388       if (vi.Kills[0] != mi)
00389         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
00390       else
00391         killIdx = defIndex+1;
00392 
00393       // If the kill happens after the definition, we have an intra-block
00394       // live range.
00395       if (killIdx > defIndex) {
00396         assert(vi.AliveBlocks.empty() &&
00397                "Shouldn't be alive across any blocks!");
00398         LiveRange LR(defIndex, killIdx, ValNum);
00399         interval.addRange(LR);
00400         DEBUG(std::cerr << " +" << LR << "\n");
00401         return;
00402       }
00403     }
00404 
00405     // The other case we handle is when a virtual register lives to the end
00406     // of the defining block, potentially live across some blocks, then is
00407     // live into some number of blocks, but gets killed.  Start by adding a
00408     // range that goes from this definition to the end of the defining block.
00409     LiveRange NewLR(defIndex,
00410                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
00411                     ValNum);
00412     DEBUG(std::cerr << " +" << NewLR);
00413     interval.addRange(NewLR);
00414 
00415     // Iterate over all of the blocks that the variable is completely
00416     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
00417     // live interval.
00418     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
00419       if (vi.AliveBlocks[i]) {
00420         MachineBasicBlock* mbb = mf_->getBlockNumbered(i);
00421         if (!mbb->empty()) {
00422           LiveRange LR(getInstructionIndex(&mbb->front()),
00423                        getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
00424                        ValNum);
00425           interval.addRange(LR);
00426           DEBUG(std::cerr << " +" << LR);
00427         }
00428       }
00429     }
00430 
00431     // Finally, this virtual register is live from the start of any killing
00432     // block to the 'use' slot of the killing instruction.
00433     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
00434       MachineInstr *Kill = vi.Kills[i];
00435       LiveRange LR(getInstructionIndex(Kill->getParent()->begin()),
00436                    getUseIndex(getInstructionIndex(Kill))+1,
00437                    ValNum);
00438       interval.addRange(LR);
00439       DEBUG(std::cerr << " +" << LR);
00440     }
00441 
00442   } else {
00443     // If this is the second time we see a virtual register definition, it
00444     // must be due to phi elimination or two addr elimination.  If this is
00445     // the result of two address elimination, then the vreg is the first
00446     // operand, and is a def-and-use.
00447     if (mi->getOperand(0).isRegister() &&
00448         mi->getOperand(0).getReg() == interval.reg &&
00449         mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) {
00450       // If this is a two-address definition, then we have already processed
00451       // the live range.  The only problem is that we didn't realize there
00452       // are actually two values in the live interval.  Because of this we
00453       // need to take the LiveRegion that defines this register and split it
00454       // into two values.
00455       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
00456       unsigned RedefIndex = getDefIndex(getInstructionIndex(mi));
00457 
00458       // Delete the initial value, which should be short and continuous,
00459       // becuase the 2-addr copy must be in the same MBB as the redef.
00460       interval.removeRange(DefIndex, RedefIndex);
00461 
00462       LiveRange LR(DefIndex, RedefIndex, interval.getNextValue());
00463       DEBUG(std::cerr << " replace range with " << LR);
00464       interval.addRange(LR);
00465 
00466       // If this redefinition is dead, we need to add a dummy unit live
00467       // range covering the def slot.
00468       if (lv_->RegisterDefIsDead(mi, interval.reg))
00469         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
00470 
00471       DEBUG(std::cerr << "RESULT: " << interval);
00472 
00473     } else {
00474       // Otherwise, this must be because of phi elimination.  If this is the
00475       // first redefinition of the vreg that we have seen, go back and change
00476       // the live range in the PHI block to be a different value number.
00477       if (interval.containsOneValue()) {
00478         assert(vi.Kills.size() == 1 &&
00479                "PHI elimination vreg should have one kill, the PHI itself!");
00480 
00481         // Remove the old range that we now know has an incorrect number.
00482         MachineInstr *Killer = vi.Kills[0];
00483         unsigned Start = getInstructionIndex(Killer->getParent()->begin());
00484         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
00485         DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: "
00486               << interval << "\n");
00487         interval.removeRange(Start, End);
00488         DEBUG(std::cerr << "RESULT: " << interval);
00489 
00490         // Replace the interval with one of a NEW value number.
00491         LiveRange LR(Start, End, interval.getNextValue());
00492         DEBUG(std::cerr << " replace range with " << LR);
00493         interval.addRange(LR);
00494         DEBUG(std::cerr << "RESULT: " << interval);
00495       }
00496 
00497       // In the case of PHI elimination, each variable definition is only
00498       // live until the end of the block.  We've already taken care of the
00499       // rest of the live range.
00500       unsigned defIndex = getDefIndex(getInstructionIndex(mi));
00501       LiveRange LR(defIndex,
00502                    getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
00503                    interval.getNextValue());
00504       interval.addRange(LR);
00505       DEBUG(std::cerr << " +" << LR);
00506     }
00507   }
00508 
00509   DEBUG(std::cerr << '\n');
00510 }
00511 
00512 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
00513                                               MachineBasicBlock::iterator mi,
00514                                               LiveInterval& interval,
00515                                               unsigned SrcReg, unsigned DestReg,
00516                                               bool isLiveIn)
00517 {
00518   // A physical register cannot be live across basic block, so its
00519   // lifetime must end somewhere in its defining basic block.
00520   DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg));
00521   typedef LiveVariables::killed_iterator KillIter;
00522 
00523   unsigned baseIndex = getInstructionIndex(mi);
00524   unsigned start = getDefIndex(baseIndex);
00525   unsigned end = start;
00526 
00527   // If it is not used after definition, it is considered dead at
00528   // the instruction defining it. Hence its interval is:
00529   // [defSlot(def), defSlot(def)+1)
00530   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
00531     DEBUG(std::cerr << " dead");
00532     end = getDefIndex(start) + 1;
00533     goto exit;
00534   }
00535 
00536   // If it is not dead on definition, it must be killed by a
00537   // subsequent instruction. Hence its interval is:
00538   // [defSlot(def), useSlot(kill)+1)
00539   while (++mi != MBB->end()) {
00540     baseIndex += InstrSlots::NUM;
00541     if (lv_->KillsRegister(mi, interval.reg)) {
00542       DEBUG(std::cerr << " killed");
00543       end = getUseIndex(baseIndex) + 1;
00544       goto exit;
00545     }
00546   }
00547   
00548   // The only case we should have a dead physreg here without a killing or
00549   // instruction where we know it's dead is if it is live-in to the function
00550   // and never used.
00551   assert(isLiveIn && "physreg was not killed in defining block!");
00552   end = getDefIndex(start) + 1;  // It's dead.
00553 
00554 exit:
00555   assert(start < end && "did not find end of interval?");
00556 
00557   // Finally, if this is defining a new range for the physical register, and if
00558   // that physreg is just a copy from a vreg, and if THAT vreg was a copy from
00559   // the physreg, then the new fragment has the same value as the one copied
00560   // into the vreg.
00561   if (interval.reg == DestReg && !interval.empty() &&
00562       MRegisterInfo::isVirtualRegister(SrcReg)) {
00563 
00564     // Get the live interval for the vreg, see if it is defined by a copy.
00565     LiveInterval &SrcInterval = getOrCreateInterval(SrcReg);
00566 
00567     if (SrcInterval.containsOneValue()) {
00568       assert(!SrcInterval.empty() && "Can't contain a value and be empty!");
00569 
00570       // Get the first index of the first range.  Though the interval may have
00571       // multiple liveranges in it, we only check the first.
00572       unsigned StartIdx = SrcInterval.begin()->start;
00573       MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx);
00574 
00575       // Check to see if the vreg was defined by a copy instruction, and that
00576       // the source was this physreg.
00577       unsigned VRegSrcSrc, VRegSrcDest;
00578       if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) &&
00579           SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) {
00580         // Okay, now we know that the vreg was defined by a copy from this
00581         // physreg.  Find the value number being copied and use it as the value
00582         // for this range.
00583         const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1);
00584         if (DefRange) {
00585           LiveRange LR(start, end, DefRange->ValId);
00586           interval.addRange(LR);
00587           DEBUG(std::cerr << " +" << LR << '\n');
00588           return;
00589         }
00590       }
00591     }
00592   }
00593 
00594 
00595   LiveRange LR(start, end, interval.getNextValue());
00596   interval.addRange(LR);
00597   DEBUG(std::cerr << " +" << LR << '\n');
00598 }
00599 
00600 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
00601                                       MachineBasicBlock::iterator MI,
00602                                       unsigned reg) {
00603   if (MRegisterInfo::isVirtualRegister(reg))
00604     handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg));
00605   else if (allocatableRegs_[reg]) {
00606     unsigned SrcReg = 0, DestReg = 0;
00607     if (!tii_->isMoveInstr(*MI, SrcReg, DestReg))
00608       SrcReg = DestReg = 0;
00609 
00610     handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg),
00611                               SrcReg, DestReg);
00612     for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS)
00613       handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS),
00614                                 SrcReg, DestReg);
00615   }
00616 }
00617 
00618 /// computeIntervals - computes the live intervals for virtual
00619 /// registers. for some ordering of the machine instructions [1,N] a
00620 /// live interval is an interval [i, j) where 1 <= i <= j < N for
00621 /// which a variable is live
00622 void LiveIntervals::computeIntervals()
00623 {
00624   DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n");
00625   DEBUG(std::cerr << "********** Function: "
00626         << ((Value*)mf_->getFunction())->getName() << '\n');
00627   bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end();
00628 
00629   for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
00630        I != E; ++I) {
00631     MachineBasicBlock* mbb = I;
00632     DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n");
00633 
00634     MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
00635     if (IgnoreFirstInstr) { ++mi; IgnoreFirstInstr = false; }
00636     for (; mi != miEnd; ++mi) {
00637       const TargetInstrDescriptor& tid =
00638         tm_->getInstrInfo()->get(mi->getOpcode());
00639       DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi);
00640 
00641       // handle implicit defs
00642       if (tid.ImplicitDefs) {
00643         for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
00644           handleRegisterDef(mbb, mi, *id);
00645       }
00646 
00647       // handle explicit defs
00648       for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
00649         MachineOperand& mop = mi->getOperand(i);
00650         // handle register defs - build intervals
00651         if (mop.isRegister() && mop.getReg() && mop.isDef())
00652           handleRegisterDef(mbb, mi, mop.getReg());
00653       }
00654     }
00655   }
00656 }
00657 
00658 /// IntA is defined as a copy from IntB and we know it only has one value
00659 /// number.  If all of the places that IntA and IntB overlap are defined by
00660 /// copies from IntA to IntB, we know that these two ranges can really be
00661 /// merged if we adjust the value numbers.  If it is safe, adjust the value
00662 /// numbers and return true, allowing coalescing to occur.
00663 bool LiveIntervals::
00664 AdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA,
00665                                           LiveInterval &IntB,
00666                                           unsigned CopyIdx) {
00667   std::vector<LiveRange*> Ranges;
00668   IntA.getOverlapingRanges(IntB, CopyIdx, Ranges);
00669   
00670   assert(!Ranges.empty() && "Why didn't we do a simple join of this?");
00671   
00672   unsigned IntBRep = rep(IntB.reg);
00673   
00674   // Check to see if all of the overlaps (entries in Ranges) are defined by a
00675   // copy from IntA.  If not, exit.
00676   for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
00677     unsigned Idx = Ranges[i]->start;
00678     MachineInstr *MI = getInstructionFromIndex(Idx);
00679     unsigned SrcReg, DestReg;
00680     if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) return false;
00681     
00682     // If this copy isn't actually defining this range, it must be a live
00683     // range spanning basic blocks or something.
00684     if (rep(DestReg) != rep(IntA.reg)) return false;
00685     
00686     // Check to see if this is coming from IntB.  If not, bail out.
00687     if (rep(SrcReg) != IntBRep) return false;
00688   }
00689 
00690   // Okay, we can change this one.  Get the IntB value number that IntA is
00691   // copied from.
00692   unsigned ActualValNo = IntA.getLiveRangeContaining(CopyIdx-1)->ValId;
00693   
00694   // Change all of the value numbers to the same as what we IntA is copied from.
00695   for (unsigned i = 0, e = Ranges.size(); i != e; ++i)
00696     Ranges[i]->ValId = ActualValNo;
00697   
00698   return true;
00699 }
00700 
00701 void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) {
00702   DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
00703 
00704   for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end();
00705        mi != mie; ++mi) {
00706     DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi);
00707 
00708     // we only join virtual registers with allocatable
00709     // physical registers since we do not have liveness information
00710     // on not allocatable physical registers
00711     unsigned SrcReg, DestReg;
00712     if (tii_->isMoveInstr(*mi, SrcReg, DestReg) &&
00713         (MRegisterInfo::isVirtualRegister(SrcReg) || allocatableRegs_[SrcReg])&&
00714         (MRegisterInfo::isVirtualRegister(DestReg)||allocatableRegs_[DestReg])){
00715 
00716       // Get representative registers.
00717       SrcReg = rep(SrcReg);
00718       DestReg = rep(DestReg);
00719 
00720       // If they are already joined we continue.
00721       if (SrcReg == DestReg)
00722         continue;
00723 
00724       // If they are both physical registers, we cannot join them.
00725       if (MRegisterInfo::isPhysicalRegister(SrcReg) &&
00726           MRegisterInfo::isPhysicalRegister(DestReg))
00727         continue;
00728 
00729       // If they are not of the same register class, we cannot join them.
00730       if (differingRegisterClasses(SrcReg, DestReg))
00731         continue;
00732 
00733       LiveInterval &SrcInt = getInterval(SrcReg);
00734       LiveInterval &DestInt = getInterval(DestReg);
00735       assert(SrcInt.reg == SrcReg && DestInt.reg == DestReg &&
00736              "Register mapping is horribly broken!");
00737 
00738       DEBUG(std::cerr << "\t\tInspecting " << SrcInt << " and " << DestInt
00739                       << ": ");
00740 
00741       // If two intervals contain a single value and are joined by a copy, it
00742       // does not matter if the intervals overlap, they can always be joined.
00743       bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue();
00744 
00745       unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi));
00746       
00747       // If the intervals think that this is joinable, do so now.
00748       if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx))
00749         Joinable = true;
00750 
00751       // If DestInt is actually a copy from SrcInt (which we know) that is used
00752       // to define another value of SrcInt, we can change the other range of
00753       // SrcInt to be the value of the range that defines DestInt, allowing a
00754       // coalesce.
00755       if (!Joinable && DestInt.containsOneValue() &&
00756           AdjustIfAllOverlappingRangesAreCopiesFrom(SrcInt, DestInt, MIDefIdx))
00757         Joinable = true;
00758       
00759       if (!Joinable || overlapsAliases(&SrcInt, &DestInt)) {
00760         DEBUG(std::cerr << "Interference!\n");
00761       } else {
00762         DestInt.join(SrcInt, MIDefIdx);
00763         DEBUG(std::cerr << "Joined.  Result = " << DestInt << "\n");
00764 
00765         if (!MRegisterInfo::isPhysicalRegister(SrcReg)) {
00766           r2iMap_.erase(SrcReg);
00767           r2rMap_[SrcReg] = DestReg;
00768         } else {
00769           // Otherwise merge the data structures the other way so we don't lose
00770           // the physreg information.
00771           r2rMap_[DestReg] = SrcReg;
00772           DestInt.reg = SrcReg;
00773           SrcInt.swap(DestInt);
00774           r2iMap_.erase(DestReg);
00775         }
00776         ++numJoins;
00777       }
00778     }
00779   }
00780 }
00781 
00782 namespace {
00783   // DepthMBBCompare - Comparison predicate that sort first based on the loop
00784   // depth of the basic block (the unsigned), and then on the MBB number.
00785   struct DepthMBBCompare {
00786     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
00787     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
00788       if (LHS.first > RHS.first) return true;   // Deeper loops first
00789       return LHS.first == RHS.first &&
00790         LHS.second->getNumber() < RHS.second->getNumber();
00791     }
00792   };
00793 }
00794 
00795 void LiveIntervals::joinIntervals() {
00796   DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n");
00797 
00798   const LoopInfo &LI = getAnalysis<LoopInfo>();
00799   if (LI.begin() == LI.end()) {
00800     // If there are no loops in the function, join intervals in function order.
00801     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
00802          I != E; ++I)
00803       joinIntervalsInMachineBB(I);
00804   } else {
00805     // Otherwise, join intervals in inner loops before other intervals.
00806     // Unfortunately we can't just iterate over loop hierarchy here because
00807     // there may be more MBB's than BB's.  Collect MBB's for sorting.
00808     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
00809     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
00810          I != E; ++I)
00811       MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I));
00812 
00813     // Sort by loop depth.
00814     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
00815 
00816     // Finally, join intervals in loop nest order.
00817     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
00818       joinIntervalsInMachineBB(MBBs[i].second);
00819   }
00820 
00821   DEBUG(std::cerr << "*** Register mapping ***\n");
00822   DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i)
00823           if (r2rMap_[i])
00824              std::cerr << "  reg " << i << " -> reg " << r2rMap_[i] << "\n");
00825 }
00826 
00827 /// Return true if the two specified registers belong to different register
00828 /// classes.  The registers may be either phys or virt regs.
00829 bool LiveIntervals::differingRegisterClasses(unsigned RegA,
00830                                              unsigned RegB) const {
00831 
00832   // Get the register classes for the first reg.
00833   if (MRegisterInfo::isPhysicalRegister(RegA)) {
00834     assert(MRegisterInfo::isVirtualRegister(RegB) &&
00835            "Shouldn't consider two physregs!");
00836     return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA);
00837   }
00838 
00839   // Compare against the regclass for the second reg.
00840   const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA);
00841   if (MRegisterInfo::isVirtualRegister(RegB))
00842     return RegClass != mf_->getSSARegMap()->getRegClass(RegB);
00843   else
00844     return !RegClass->contains(RegB);
00845 }
00846 
00847 bool LiveIntervals::overlapsAliases(const LiveInterval *LHS,
00848                                     const LiveInterval *RHS) const {
00849   if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) {
00850     if (!MRegisterInfo::isPhysicalRegister(RHS->reg))
00851       return false;   // vreg-vreg merge has no aliases!
00852     std::swap(LHS, RHS);
00853   }
00854 
00855   assert(MRegisterInfo::isPhysicalRegister(LHS->reg) &&
00856          MRegisterInfo::isVirtualRegister(RHS->reg) &&
00857          "first interval must describe a physical register");
00858 
00859   for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS)
00860     if (RHS->overlaps(getInterval(*AS)))
00861       return true;
00862 
00863   return false;
00864 }
00865 
00866 LiveInterval LiveIntervals::createInterval(unsigned reg) {
00867   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
00868                        (float)HUGE_VAL :0.0F;
00869   return LiveInterval(reg, Weight);
00870 }