LLVM API Documentation

SimpleRegisterCoalescing.cpp

Go to the documentation of this file.
00001 //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===//
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 a simple register coalescing pass that attempts to
00011 // aggressively coalesce every register copy that it can.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "regcoalescing"
00016 #include "SimpleRegisterCoalescing.h"
00017 #include "VirtRegMap.h"
00018 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00019 #include "llvm/Value.h"
00020 #include "llvm/CodeGen/MachineFrameInfo.h"
00021 #include "llvm/CodeGen/MachineInstr.h"
00022 #include "llvm/CodeGen/MachineLoopInfo.h"
00023 #include "llvm/CodeGen/MachineRegisterInfo.h"
00024 #include "llvm/CodeGen/Passes.h"
00025 #include "llvm/CodeGen/RegisterCoalescer.h"
00026 #include "llvm/Target/TargetInstrInfo.h"
00027 #include "llvm/Target/TargetMachine.h"
00028 #include "llvm/Target/TargetOptions.h"
00029 #include "llvm/Support/CommandLine.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/ErrorHandling.h"
00032 #include "llvm/Support/raw_ostream.h"
00033 #include "llvm/ADT/SmallSet.h"
00034 #include "llvm/ADT/Statistic.h"
00035 #include "llvm/ADT/STLExtras.h"
00036 #include <algorithm>
00037 #include <cmath>
00038 using namespace llvm;
00039 
00040 STATISTIC(numJoins    , "Number of interval joins performed");
00041 STATISTIC(numCrossRCs , "Number of cross class joins performed");
00042 STATISTIC(numCommutes , "Number of instruction commuting performed");
00043 STATISTIC(numExtends  , "Number of copies extended");
00044 STATISTIC(NumReMats   , "Number of instructions re-materialized");
00045 STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
00046 STATISTIC(numAborts   , "Number of times interval joining aborted");
00047 STATISTIC(numDeadValNo, "Number of valno def marked dead");
00048 
00049 char SimpleRegisterCoalescing::ID = 0;
00050 static cl::opt<bool>
00051 EnableJoining("join-liveintervals",
00052               cl::desc("Coalesce copies (default=true)"),
00053               cl::init(true));
00054 
00055 static cl::opt<bool>
00056 NewHeuristic("new-coalescer-heuristic",
00057              cl::desc("Use new coalescer heuristic"),
00058              cl::init(false), cl::Hidden);
00059 
00060 static cl::opt<bool>
00061 DisableCrossClassJoin("disable-cross-class-join",
00062                cl::desc("Avoid coalescing cross register class copies"),
00063                cl::init(false), cl::Hidden);
00064 
00065 static cl::opt<bool>
00066 PhysJoinTweak("tweak-phys-join-heuristics",
00067                cl::desc("Tweak heuristics for joining phys reg with vr"),
00068                cl::init(false), cl::Hidden);
00069 
00070 static RegisterPass<SimpleRegisterCoalescing> 
00071 X("simple-register-coalescing", "Simple Register Coalescing");
00072 
00073 // Declare that we implement the RegisterCoalescer interface
00074 static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
00075 
00076 const PassInfo *const llvm::SimpleRegisterCoalescingID = &X;
00077 
00078 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
00079   AU.setPreservesCFG();
00080   AU.addRequired<LiveIntervals>();
00081   AU.addPreserved<LiveIntervals>();
00082   AU.addRequired<MachineLoopInfo>();
00083   AU.addPreserved<MachineLoopInfo>();
00084   AU.addPreservedID(MachineDominatorsID);
00085   if (StrongPHIElim)
00086     AU.addPreservedID(StrongPHIEliminationID);
00087   else
00088     AU.addPreservedID(PHIEliminationID);
00089   AU.addPreservedID(TwoAddressInstructionPassID);
00090   MachineFunctionPass::getAnalysisUsage(AU);
00091 }
00092 
00093 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
00094 /// being the source and IntB being the dest, thus this defines a value number
00095 /// in IntB.  If the source value number (in IntA) is defined by a copy from B,
00096 /// see if we can merge these two pieces of B into a single value number,
00097 /// eliminating a copy.  For example:
00098 ///
00099 ///  A3 = B0
00100 ///    ...
00101 ///  B1 = A3      <- this copy
00102 ///
00103 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
00104 /// value number to be replaced with B0 (which simplifies the B liveinterval).
00105 ///
00106 /// This returns true if an interval was modified.
00107 ///
00108 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
00109                                                     LiveInterval &IntB,
00110                                                     MachineInstr *CopyMI) {
00111   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
00112 
00113   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
00114   // the example above.
00115   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
00116   assert(BLR != IntB.end() && "Live range not found!");
00117   VNInfo *BValNo = BLR->valno;
00118   
00119   // Get the location that B is defined at.  Two options: either this value has
00120   // an unknown definition point or it is defined at CopyIdx.  If unknown, we 
00121   // can't process it.
00122   if (!BValNo->getCopy()) return false;
00123   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
00124   
00125   // AValNo is the value number in A that defines the copy, A3 in the example.
00126   unsigned CopyUseIdx = li_->getUseIndex(CopyIdx);
00127   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
00128   assert(ALR != IntA.end() && "Live range not found!");
00129   VNInfo *AValNo = ALR->valno;
00130   // If it's re-defined by an early clobber somewhere in the live range, then
00131   // it's not safe to eliminate the copy. FIXME: This is a temporary workaround.
00132   // See PR3149:
00133   // 172     %ECX<def> = MOV32rr %reg1039<kill>
00134   // 180     INLINEASM <es:subl $5,$1
00135   //         sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, %EAX<kill>,
00136   // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0
00137   // 188     %EAX<def> = MOV32rr %EAX<kill>
00138   // 196     %ECX<def> = MOV32rr %ECX<kill>
00139   // 204     %ECX<def> = MOV32rr %ECX<kill>
00140   // 212     %EAX<def> = MOV32rr %EAX<kill>
00141   // 220     %EAX<def> = MOV32rr %EAX
00142   // 228     %reg1039<def> = MOV32rr %ECX<kill>
00143   // The early clobber operand ties ECX input to the ECX def.
00144   //
00145   // The live interval of ECX is represented as this:
00146   // %reg20,inf = [46,47:1)[174,230:0)  0@174-(230) 1@46-(47)
00147   // The coalescer has no idea there was a def in the middle of [174,230].
00148   if (AValNo->hasRedefByEC())
00149     return false;
00150   
00151   // If AValNo is defined as a copy from IntB, we can potentially process this.  
00152   // Get the instruction that defines this value number.
00153   unsigned SrcReg = li_->getVNInfoSourceReg(AValNo);
00154   if (!SrcReg) return false;  // Not defined by a copy.
00155     
00156   // If the value number is not defined by a copy instruction, ignore it.
00157 
00158   // If the source register comes from an interval other than IntB, we can't
00159   // handle this.
00160   if (SrcReg != IntB.reg) return false;
00161   
00162   // Get the LiveRange in IntB that this value number starts with.
00163   LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1);
00164   assert(ValLR != IntB.end() && "Live range not found!");
00165   
00166   // Make sure that the end of the live range is inside the same block as
00167   // CopyMI.
00168   MachineInstr *ValLREndInst = li_->getInstructionFromIndex(ValLR->end-1);
00169   if (!ValLREndInst || 
00170       ValLREndInst->getParent() != CopyMI->getParent()) return false;
00171 
00172   // Okay, we now know that ValLR ends in the same block that the CopyMI
00173   // live-range starts.  If there are no intervening live ranges between them in
00174   // IntB, we can merge them.
00175   if (ValLR+1 != BLR) return false;
00176 
00177   // If a live interval is a physical register, conservatively check if any
00178   // of its sub-registers is overlapping the live interval of the virtual
00179   // register. If so, do not coalesce.
00180   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) &&
00181       *tri_->getSubRegisters(IntB.reg)) {
00182     for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
00183       if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) {
00184         DOUT << "Interfere with sub-register ";
00185         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
00186         return false;
00187       }
00188   }
00189   
00190   DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
00191   
00192   unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
00193   // We are about to delete CopyMI, so need to remove it as the 'instruction
00194   // that defines this value #'. Update the the valnum with the new defining
00195   // instruction #.
00196   BValNo->def  = FillerStart;
00197   BValNo->setCopy(0);
00198   
00199   // Okay, we can merge them.  We need to insert a new liverange:
00200   // [ValLR.end, BLR.begin) of either value number, then we merge the
00201   // two value numbers.
00202   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
00203 
00204   // If the IntB live range is assigned to a physical register, and if that
00205   // physreg has sub-registers, update their live intervals as well. 
00206   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
00207     for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
00208       LiveInterval &SRLI = li_->getInterval(*SR);
00209       SRLI.addRange(LiveRange(FillerStart, FillerEnd,
00210                               SRLI.getNextValue(FillerStart, 0, true,
00211                                                 li_->getVNInfoAllocator())));
00212     }
00213   }
00214 
00215   // Okay, merge "B1" into the same value number as "B0".
00216   if (BValNo != ValLR->valno) {
00217     IntB.addKills(ValLR->valno, BValNo->kills);
00218     IntB.MergeValueNumberInto(BValNo, ValLR->valno);
00219   }
00220   DOUT << "   result = "; IntB.print(DOUT, tri_);
00221   DOUT << "\n";
00222 
00223   // If the source instruction was killing the source register before the
00224   // merge, unset the isKill marker given the live range has been extended.
00225   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
00226   if (UIdx != -1) {
00227     ValLREndInst->getOperand(UIdx).setIsKill(false);
00228     IntB.removeKill(ValLR->valno, FillerStart);
00229   }
00230 
00231   // If the copy instruction was killing the destination register before the
00232   // merge, find the last use and trim the live range. That will also add the
00233   // isKill marker.
00234   if (CopyMI->killsRegister(IntA.reg))
00235     TrimLiveIntervalToLastUse(CopyUseIdx, CopyMI->getParent(), IntA, ALR);
00236 
00237   ++numExtends;
00238   return true;
00239 }
00240 
00241 /// HasOtherReachingDefs - Return true if there are definitions of IntB
00242 /// other than BValNo val# that can reach uses of AValno val# of IntA.
00243 bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA,
00244                                                     LiveInterval &IntB,
00245                                                     VNInfo *AValNo,
00246                                                     VNInfo *BValNo) {
00247   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
00248        AI != AE; ++AI) {
00249     if (AI->valno != AValNo) continue;
00250     LiveInterval::Ranges::iterator BI =
00251       std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
00252     if (BI != IntB.ranges.begin())
00253       --BI;
00254     for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
00255       if (BI->valno == BValNo)
00256         continue;
00257       if (BI->start <= AI->start && BI->end > AI->start)
00258         return true;
00259       if (BI->start > AI->start && BI->start < AI->end)
00260         return true;
00261     }
00262   }
00263   return false;
00264 }
00265 
00266 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA
00267 /// being the source and IntB being the dest, thus this defines a value number
00268 /// in IntB.  If the source value number (in IntA) is defined by a commutable
00269 /// instruction and its other operand is coalesced to the copy dest register,
00270 /// see if we can transform the copy into a noop by commuting the definition. For
00271 /// example,
00272 ///
00273 ///  A3 = op A2 B0<kill>
00274 ///    ...
00275 ///  B1 = A3      <- this copy
00276 ///    ...
00277 ///     = op A3   <- more uses
00278 ///
00279 /// ==>
00280 ///
00281 ///  B2 = op B0 A2<kill>
00282 ///    ...
00283 ///  B1 = B2      <- now an identify copy
00284 ///    ...
00285 ///     = op B2   <- more uses
00286 ///
00287 /// This returns true if an interval was modified.
00288 ///
00289 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
00290                                                         LiveInterval &IntB,
00291                                                         MachineInstr *CopyMI) {
00292   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
00293 
00294   // FIXME: For now, only eliminate the copy by commuting its def when the
00295   // source register is a virtual register. We want to guard against cases
00296   // where the copy is a back edge copy and commuting the def lengthen the
00297   // live interval of the source register to the entire loop.
00298   if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
00299     return false;
00300 
00301   // BValNo is a value number in B that is defined by a copy from A. 'B3' in
00302   // the example above.
00303   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
00304   assert(BLR != IntB.end() && "Live range not found!");
00305   VNInfo *BValNo = BLR->valno;
00306   
00307   // Get the location that B is defined at.  Two options: either this value has
00308   // an unknown definition point or it is defined at CopyIdx.  If unknown, we 
00309   // can't process it.
00310   if (!BValNo->getCopy()) return false;
00311   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
00312   
00313   // AValNo is the value number in A that defines the copy, A3 in the example.
00314   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
00315   assert(ALR != IntA.end() && "Live range not found!");
00316   VNInfo *AValNo = ALR->valno;
00317   // If other defs can reach uses of this def, then it's not safe to perform
00318   // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be
00319   // tested?
00320   if (AValNo->isPHIDef() || !AValNo->isDefAccurate() ||
00321       AValNo->isUnused() || AValNo->hasPHIKill())
00322     return false;
00323   MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def);
00324   const TargetInstrDesc &TID = DefMI->getDesc();
00325   if (!TID.isCommutable())
00326     return false;
00327   // If DefMI is a two-address instruction then commuting it will change the
00328   // destination register.
00329   int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg);
00330   assert(DefIdx != -1);
00331   unsigned UseOpIdx;
00332   if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
00333     return false;
00334   unsigned Op1, Op2, NewDstIdx;
00335   if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2))
00336     return false;
00337   if (Op1 == UseOpIdx)
00338     NewDstIdx = Op2;
00339   else if (Op2 == UseOpIdx)
00340     NewDstIdx = Op1;
00341   else
00342     return false;
00343 
00344   MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
00345   unsigned NewReg = NewDstMO.getReg();
00346   if (NewReg != IntB.reg || !NewDstMO.isKill())
00347     return false;
00348 
00349   // Make sure there are no other definitions of IntB that would reach the
00350   // uses which the new definition can reach.
00351   if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
00352     return false;
00353 
00354   // If some of the uses of IntA.reg is already coalesced away, return false.
00355   // It's not possible to determine whether it's safe to perform the coalescing.
00356   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
00357          UE = mri_->use_end(); UI != UE; ++UI) {
00358     MachineInstr *UseMI = &*UI;
00359     unsigned UseIdx = li_->getInstructionIndex(UseMI);
00360     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
00361     if (ULR == IntA.end())
00362       continue;
00363     if (ULR->valno == AValNo && JoinedCopies.count(UseMI))
00364       return false;
00365   }
00366 
00367   // At this point we have decided that it is legal to do this
00368   // transformation.  Start by commuting the instruction.
00369   MachineBasicBlock *MBB = DefMI->getParent();
00370   MachineInstr *NewMI = tii_->commuteInstruction(DefMI);
00371   if (!NewMI)
00372     return false;
00373   if (NewMI != DefMI) {
00374     li_->ReplaceMachineInstrInMaps(DefMI, NewMI);
00375     MBB->insert(DefMI, NewMI);
00376     MBB->erase(DefMI);
00377   }
00378   unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
00379   NewMI->getOperand(OpIdx).setIsKill();
00380 
00381   bool BHasPHIKill = BValNo->hasPHIKill();
00382   SmallVector<VNInfo*, 4> BDeadValNos;
00383   VNInfo::KillSet BKills;
00384   std::map<unsigned, unsigned> BExtend;
00385 
00386   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
00387   // A = or A, B
00388   // ...
00389   // B = A
00390   // ...
00391   // C = A<kill>
00392   // ...
00393   //   = B
00394   //
00395   // then do not add kills of A to the newly created B interval.
00396   bool Extended = BLR->end > ALR->end && ALR->end != ALR->start;
00397   if (Extended)
00398     BExtend[ALR->end] = BLR->end;
00399 
00400   // Update uses of IntA of the specific Val# with IntB.
00401   bool BHasSubRegs = false;
00402   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg))
00403     BHasSubRegs = *tri_->getSubRegisters(IntB.reg);
00404   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
00405          UE = mri_->use_end(); UI != UE;) {
00406     MachineOperand &UseMO = UI.getOperand();
00407     MachineInstr *UseMI = &*UI;
00408     ++UI;
00409     if (JoinedCopies.count(UseMI))
00410       continue;
00411     unsigned UseIdx = li_->getInstructionIndex(UseMI);
00412     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
00413     if (ULR == IntA.end() || ULR->valno != AValNo)
00414       continue;
00415     UseMO.setReg(NewReg);
00416     if (UseMI == CopyMI)
00417       continue;
00418     if (UseMO.isKill()) {
00419       if (Extended)
00420         UseMO.setIsKill(false);
00421       else
00422         BKills.push_back(VNInfo::KillInfo(false, li_->getUseIndex(UseIdx)+1));
00423     }
00424     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
00425     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
00426       continue;
00427     if (DstReg == IntB.reg) {
00428       // This copy will become a noop. If it's defining a new val#,
00429       // remove that val# as well. However this live range is being
00430       // extended to the end of the existing live range defined by the copy.
00431       unsigned DefIdx = li_->getDefIndex(UseIdx);
00432       const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
00433       BHasPHIKill |= DLR->valno->hasPHIKill();
00434       assert(DLR->valno->def == DefIdx);
00435       BDeadValNos.push_back(DLR->valno);
00436       BExtend[DLR->start] = DLR->end;
00437       JoinedCopies.insert(UseMI);
00438       // If this is a kill but it's going to be removed, the last use
00439       // of the same val# is the new kill.
00440       if (UseMO.isKill())
00441         BKills.pop_back();
00442     }
00443   }
00444 
00445   // We need to insert a new liverange: [ALR.start, LastUse). It may be we can
00446   // simply extend BLR if CopyMI doesn't end the range.
00447   DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
00448 
00449   // Remove val#'s defined by copies that will be coalesced away.
00450   for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) {
00451     VNInfo *DeadVNI = BDeadValNos[i];
00452     if (BHasSubRegs) {
00453       for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
00454         LiveInterval &SRLI = li_->getInterval(*SR);
00455         const LiveRange *SRLR = SRLI.getLiveRangeContaining(DeadVNI->def);
00456         SRLI.removeValNo(SRLR->valno);
00457       }
00458     }
00459     IntB.removeValNo(BDeadValNos[i]);
00460   }
00461 
00462   // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
00463   // is updated. Kills are also updated.
00464   VNInfo *ValNo = BValNo;
00465   ValNo->def = AValNo->def;
00466   ValNo->setCopy(0);
00467   for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) {
00468     unsigned Kill = ValNo->kills[j].killIdx;
00469     if (Kill != BLR->end)
00470       BKills.push_back(VNInfo::KillInfo(ValNo->kills[j].isPHIKill, Kill));
00471   }
00472   ValNo->kills.clear();
00473   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
00474        AI != AE; ++AI) {
00475     if (AI->valno != AValNo) continue;
00476     unsigned End = AI->end;
00477     std::map<unsigned, unsigned>::iterator EI = BExtend.find(End);
00478     if (EI != BExtend.end())
00479       End = EI->second;
00480     IntB.addRange(LiveRange(AI->start, End, ValNo));
00481 
00482     // If the IntB live range is assigned to a physical register, and if that
00483     // physreg has sub-registers, update their live intervals as well. 
00484     if (BHasSubRegs) {
00485       for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
00486         LiveInterval &SRLI = li_->getInterval(*SR);
00487         SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator());
00488       }
00489     }
00490   }
00491   IntB.addKills(ValNo, BKills);
00492   ValNo->setHasPHIKill(BHasPHIKill);
00493 
00494   DOUT << "   result = "; IntB.print(DOUT, tri_);
00495   DOUT << "\n";
00496 
00497   DOUT << "\nShortening: "; IntA.print(DOUT, tri_);
00498   IntA.removeValNo(AValNo);
00499   DOUT << "   result = "; IntA.print(DOUT, tri_);
00500   DOUT << "\n";
00501 
00502   ++numCommutes;
00503   return true;
00504 }
00505 
00506 /// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
00507 /// fallthoughs to SuccMBB.
00508 static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
00509                                   MachineBasicBlock *SuccMBB,
00510                                   const TargetInstrInfo *tii_) {
00511   if (MBB == SuccMBB)
00512     return true;
00513   MachineBasicBlock *TBB = 0, *FBB = 0;
00514   SmallVector<MachineOperand, 4> Cond;
00515   return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
00516     MBB->isSuccessor(SuccMBB);
00517 }
00518 
00519 /// removeRange - Wrapper for LiveInterval::removeRange. This removes a range
00520 /// from a physical register live interval as well as from the live intervals
00521 /// of its sub-registers.
00522 static void removeRange(LiveInterval &li, unsigned Start, unsigned End,
00523                         LiveIntervals *li_, const TargetRegisterInfo *tri_) {
00524   li.removeRange(Start, End, true);
00525   if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
00526     for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
00527       if (!li_->hasInterval(*SR))
00528         continue;
00529       LiveInterval &sli = li_->getInterval(*SR);
00530       unsigned RemoveStart = Start;
00531       unsigned RemoveEnd = Start;
00532       while (RemoveEnd != End) {
00533         LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart);
00534         if (LR == sli.end())
00535           break;
00536         RemoveEnd = (LR->end < End) ? LR->end : End;
00537         sli.removeRange(RemoveStart, RemoveEnd, true);
00538         RemoveStart = RemoveEnd;
00539       }
00540     }
00541   }
00542 }
00543 
00544 /// TrimLiveIntervalToLastUse - If there is a last use in the same basic block
00545 /// as the copy instruction, trim the live interval to the last use and return
00546 /// true.
00547 bool
00548 SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx,
00549                                                     MachineBasicBlock *CopyMBB,
00550                                                     LiveInterval &li,
00551                                                     const LiveRange *LR) {
00552   unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
00553   unsigned LastUseIdx;
00554   MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg,
00555                                             LastUseIdx);
00556   if (LastUse) {
00557     MachineInstr *LastUseMI = LastUse->getParent();
00558     if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
00559       // r1024 = op
00560       // ...
00561       // BB1:
00562       //       = r1024
00563       //
00564       // BB2:
00565       // r1025<dead> = r1024<kill>
00566       if (MBBStart < LR->end)
00567         removeRange(li, MBBStart, LR->end, li_, tri_);
00568       return true;
00569     }
00570 
00571     // There are uses before the copy, just shorten the live range to the end
00572     // of last use.
00573     LastUse->setIsKill();
00574     removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
00575     li.addKill(LR->valno, LastUseIdx+1, false);
00576     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
00577     if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
00578         DstReg == li.reg) {
00579       // Last use is itself an identity code.
00580       int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_);
00581       LastUseMI->getOperand(DeadIdx).setIsDead();
00582     }
00583     return true;
00584   }
00585 
00586   // Is it livein?
00587   if (LR->start <= MBBStart && LR->end > MBBStart) {
00588     if (LR->start == 0) {
00589       assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
00590       // Live-in to the function but dead. Remove it from entry live-in set.
00591       mf_->begin()->removeLiveIn(li.reg);
00592     }
00593     // FIXME: Shorten intervals in BBs that reaches this BB.
00594   }
00595 
00596   return false;
00597 }
00598 
00599 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
00600 /// computation, replace the copy by rematerialize the definition.
00601 bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
00602                                                        unsigned DstReg,
00603                                                        unsigned DstSubIdx,
00604                                                        MachineInstr *CopyMI) {
00605   unsigned CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI));
00606   LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
00607   assert(SrcLR != SrcInt.end() && "Live range not found!");
00608   VNInfo *ValNo = SrcLR->valno;
00609   // If other defs can reach uses of this def, then it's not safe to perform
00610   // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be
00611   // tested?
00612   if (ValNo->isPHIDef() || !ValNo->isDefAccurate() ||
00613       ValNo->isUnused() || ValNo->hasPHIKill())
00614     return false;
00615   MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def);
00616   const TargetInstrDesc &TID = DefMI->getDesc();
00617   if (!TID.isAsCheapAsAMove())
00618     return false;
00619   if (!DefMI->getDesc().isRematerializable() ||
00620       !tii_->isTriviallyReMaterializable(DefMI))
00621     return false;
00622   bool SawStore = false;
00623   if (!DefMI->isSafeToMove(tii_, SawStore))
00624     return false;
00625   if (TID.getNumDefs() != 1)
00626     return false;
00627   if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
00628     // Make sure the copy destination register class fits the instruction
00629     // definition register class. The mismatch can happen as a result of earlier
00630     // extract_subreg, insert_subreg, subreg_to_reg coalescing.
00631     const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_);
00632     if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
00633       if (mri_->getRegClass(DstReg) != RC)
00634         return false;
00635     } else if (!RC->contains(DstReg))
00636       return false;
00637   }
00638 
00639   // If destination register has a sub-register index on it, make sure it mtches
00640   // the instruction register class.
00641   if (DstSubIdx) {
00642     const TargetInstrDesc &TID = DefMI->getDesc();
00643     if (TID.getNumDefs() != 1)
00644       return false;
00645     const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg);
00646     const TargetRegisterClass *DstSubRC =
00647       DstRC->getSubRegisterRegClass(DstSubIdx);
00648     const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_);
00649     if (DefRC == DstRC)
00650       DstSubIdx = 0;
00651     else if (DefRC != DstSubRC)
00652       return false;
00653   }
00654 
00655   unsigned DefIdx = li_->getDefIndex(CopyIdx);
00656   const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx);
00657   DLR->valno->setCopy(0);
00658   // Don't forget to update sub-register intervals.
00659   if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
00660     for (const unsigned* SR = tri_->getSubRegisters(DstReg); *SR; ++SR) {
00661       if (!li_->hasInterval(*SR))
00662         continue;
00663       DLR = li_->getInterval(*SR).getLiveRangeContaining(DefIdx);
00664       if (DLR && DLR->valno->getCopy() == CopyMI)
00665         DLR->valno->setCopy(0);
00666     }
00667   }
00668 
00669   // If copy kills the source register, find the last use and propagate
00670   // kill.
00671   bool checkForDeadDef = false;
00672   MachineBasicBlock *MBB = CopyMI->getParent();
00673   if (CopyMI->killsRegister(SrcInt.reg))
00674     if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) {
00675       checkForDeadDef = true;
00676     }
00677 
00678   MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI));
00679   tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI);
00680   MachineInstr *NewMI = prior(MII);
00681 
00682   if (checkForDeadDef) {
00683     // PR4090 fix: Trim interval failed because there was no use of the
00684     // source interval in this MBB. If the def is in this MBB too then we
00685     // should mark it dead:
00686     if (DefMI->getParent() == MBB) {
00687       DefMI->addRegisterDead(SrcInt.reg, tri_);
00688       SrcLR->end = SrcLR->start + 1;
00689     }
00690   }
00691 
00692   // CopyMI may have implicit operands, transfer them over to the newly
00693   // rematerialized instruction. And update implicit def interval valnos.
00694   for (unsigned i = CopyMI->getDesc().getNumOperands(),
00695          e = CopyMI->getNumOperands(); i != e; ++i) {
00696     MachineOperand &MO = CopyMI->getOperand(i);
00697     if (MO.isReg() && MO.isImplicit())
00698       NewMI->addOperand(MO);
00699     if (MO.isDef() && li_->hasInterval(MO.getReg())) {
00700       unsigned Reg = MO.getReg();
00701       DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
00702       if (DLR && DLR->valno->getCopy() == CopyMI)
00703         DLR->valno->setCopy(0);
00704     }
00705   }
00706 
00707   li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
00708   CopyMI->eraseFromParent();
00709   ReMatCopies.insert(CopyMI);
00710   ReMatDefs.insert(DefMI);
00711   ++NumReMats;
00712   return true;
00713 }
00714 
00715 /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy.
00716 ///
00717 bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI,
00718                                               unsigned DstReg) const {
00719   MachineBasicBlock *MBB = CopyMI->getParent();
00720   const MachineLoop *L = loopInfo->getLoopFor(MBB);
00721   if (!L)
00722     return false;
00723   if (MBB != L->getLoopLatch())
00724     return false;
00725 
00726   LiveInterval &LI = li_->getInterval(DstReg);
00727   unsigned DefIdx = li_->getInstructionIndex(CopyMI);
00728   LiveInterval::const_iterator DstLR =
00729     LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx));
00730   if (DstLR == LI.end())
00731     return false;
00732   if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0].isPHIKill)
00733     return true;
00734   return false;
00735 }
00736 
00737 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
00738 /// update the subregister number if it is not zero. If DstReg is a
00739 /// physical register and the existing subregister number of the def / use
00740 /// being updated is not zero, make sure to set it to the correct physical
00741 /// subregister.
00742 void
00743 SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
00744                                             unsigned SubIdx) {
00745   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
00746   if (DstIsPhys && SubIdx) {
00747     // Figure out the real physical register we are updating with.
00748     DstReg = tri_->getSubReg(DstReg, SubIdx);
00749     SubIdx = 0;
00750   }
00751 
00752   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
00753          E = mri_->reg_end(); I != E; ) {
00754     MachineOperand &O = I.getOperand();
00755     MachineInstr *UseMI = &*I;
00756     ++I;
00757     unsigned OldSubIdx = O.getSubReg();
00758     if (DstIsPhys) {
00759       unsigned UseDstReg = DstReg;
00760       if (OldSubIdx)
00761           UseDstReg = tri_->getSubReg(DstReg, OldSubIdx);
00762 
00763       unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
00764       if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
00765                             CopySrcSubIdx, CopyDstSubIdx) &&
00766           CopySrcReg != CopyDstReg &&
00767           CopySrcReg == SrcReg && CopyDstReg != UseDstReg) {
00768         // If the use is a copy and it won't be coalesced away, and its source
00769         // is defined by a trivial computation, try to rematerialize it instead.
00770         if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg,
00771                                     CopyDstSubIdx, UseMI))
00772           continue;
00773       }
00774 
00775       O.setReg(UseDstReg);
00776       O.setSubReg(0);
00777       continue;
00778     }
00779 
00780     // Sub-register indexes goes from small to large. e.g.
00781     // RAX: 1 -> AL, 2 -> AX, 3 -> EAX
00782     // EAX: 1 -> AL, 2 -> AX
00783     // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose
00784     // sub-register 2 is also AX.
00785     if (SubIdx && OldSubIdx && SubIdx != OldSubIdx)
00786       assert(OldSubIdx < SubIdx && "Conflicting sub-register index!");
00787     else if (SubIdx)
00788       O.setSubReg(SubIdx);
00789     // Remove would-be duplicated kill marker.
00790     if (O.isKill() && UseMI->killsRegister(DstReg))
00791       O.setIsKill(false);
00792     O.setReg(DstReg);
00793 
00794     // After updating the operand, check if the machine instruction has
00795     // become a copy. If so, update its val# information.
00796     if (JoinedCopies.count(UseMI))
00797       continue;
00798 
00799     const TargetInstrDesc &TID = UseMI->getDesc();
00800     unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
00801     if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 &&
00802         tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
00803                           CopySrcSubIdx, CopyDstSubIdx) &&
00804         CopySrcReg != CopyDstReg &&
00805         (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
00806          allocatableRegs_[CopyDstReg])) {
00807       LiveInterval &LI = li_->getInterval(CopyDstReg);
00808       unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(UseMI));
00809       if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) {
00810         if (DLR->valno->def == DefIdx)
00811           DLR->valno->setCopy(UseMI);
00812       }
00813     }
00814   }
00815 }
00816 
00817 /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate
00818 /// due to live range lengthening as the result of coalescing.
00819 void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg,
00820                                                       LiveInterval &LI) {
00821   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
00822          UE = mri_->use_end(); UI != UE; ++UI) {
00823     MachineOperand &UseMO = UI.getOperand();
00824     if (!UseMO.isKill())
00825       continue;
00826     MachineInstr *UseMI = UseMO.getParent();
00827     unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
00828     const LiveRange *LR = LI.getLiveRangeContaining(UseIdx);
00829     if (!LR || !LI.isKill(LR->valno, UseIdx+1)) {
00830       if (LR->valno->def != UseIdx+1) {
00831         // Interesting problem. After coalescing reg1027's def and kill are both
00832         // at the same point:  %reg1027,0.000000e+00 = [56,814:0)  0@70-(814)
00833         //
00834         // bb5:
00835         // 60 %reg1027<def> = t2MOVr %reg1027, 14, %reg0, %reg0
00836         // 68 %reg1027<def> = t2LDRi12 %reg1027<kill>, 8, 14, %reg0
00837         // 76 t2CMPzri %reg1038<kill,undef>, 0, 14, %reg0, %CPSR<imp-def>
00838         // 84 %reg1027<def> = t2MOVr %reg1027, 14, %reg0, %reg0
00839         // 96 t2Bcc mbb<bb5,0x2030910>, 1, %CPSR<kill>
00840         //
00841         // Do not remove the kill marker on t2LDRi12.
00842         UseMO.setIsKill(false);
00843       }
00844     }
00845   }
00846 }
00847 
00848 /// removeIntervalIfEmpty - Check if the live interval of a physical register
00849 /// is empty, if so remove it and also remove the empty intervals of its
00850 /// sub-registers. Return true if live interval is removed.
00851 static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
00852                                   const TargetRegisterInfo *tri_) {
00853   if (li.empty()) {
00854     if (TargetRegisterInfo::isPhysicalRegister(li.reg))
00855       for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
00856         if (!li_->hasInterval(*SR))
00857           continue;
00858         LiveInterval &sli = li_->getInterval(*SR);
00859         if (sli.empty())
00860           li_->removeInterval(*SR);
00861       }
00862     li_->removeInterval(li.reg);
00863     return true;
00864   }
00865   return false;
00866 }
00867 
00868 /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
00869 /// Return true if live interval is removed.
00870 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
00871                                                         MachineInstr *CopyMI) {
00872   unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
00873   LiveInterval::iterator MLR =
00874     li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
00875   if (MLR == li.end())
00876     return false;  // Already removed by ShortenDeadCopySrcLiveRange.
00877   unsigned RemoveStart = MLR->start;
00878   unsigned RemoveEnd = MLR->end;
00879   unsigned DefIdx = li_->getDefIndex(CopyIdx);
00880   // Remove the liverange that's defined by this.
00881   if (RemoveStart == DefIdx && RemoveEnd == DefIdx+1) {
00882     removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
00883     return removeIntervalIfEmpty(li, li_, tri_);
00884   }
00885   return false;
00886 }
00887 
00888 /// RemoveDeadDef - If a def of a live interval is now determined dead, remove
00889 /// the val# it defines. If the live interval becomes empty, remove it as well.
00890 bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
00891                                              MachineInstr *DefMI) {
00892   unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI));
00893   LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
00894   if (DefIdx != MLR->valno->def)
00895     return false;
00896   li.removeValNo(MLR->valno);
00897   return removeIntervalIfEmpty(li, li_, tri_);
00898 }
00899 
00900 /// PropagateDeadness - Propagate the dead marker to the instruction which
00901 /// defines the val#.
00902 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
00903                               unsigned &LRStart, LiveIntervals *li_,
00904                               const TargetRegisterInfo* tri_) {
00905   MachineInstr *DefMI =
00906     li_->getInstructionFromIndex(li_->getDefIndex(LRStart));
00907   if (DefMI && DefMI != CopyMI) {
00908     int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false);
00909     if (DeadIdx != -1)
00910       DefMI->getOperand(DeadIdx).setIsDead();
00911     else
00912       DefMI->addOperand(MachineOperand::CreateReg(li.reg,
00913                                                   true, true, false, true));
00914     ++LRStart;
00915   }
00916 }
00917 
00918 /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
00919 /// extended by a dead copy. Mark the last use (if any) of the val# as kill as
00920 /// ends the live range there. If there isn't another use, then this live range
00921 /// is dead. Return true if live interval is removed.
00922 bool
00923 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
00924                                                       MachineInstr *CopyMI) {
00925   unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
00926   if (CopyIdx == 0) {
00927     // FIXME: special case: function live in. It can be a general case if the
00928     // first instruction index starts at > 0 value.
00929     assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
00930     // Live-in to the function but dead. Remove it from entry live-in set.
00931     if (mf_->begin()->isLiveIn(li.reg))
00932       mf_->begin()->removeLiveIn(li.reg);
00933     const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
00934     removeRange(li, LR->start, LR->end, li_, tri_);
00935     return removeIntervalIfEmpty(li, li_, tri_);
00936   }
00937 
00938   LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx-1);
00939   if (LR == li.end())
00940     // Livein but defined by a phi.
00941     return false;
00942 
00943   unsigned RemoveStart = LR->start;
00944   unsigned RemoveEnd = li_->getDefIndex(CopyIdx)+1;
00945   if (LR->end > RemoveEnd)
00946     // More uses past this copy? Nothing to do.
00947     return false;
00948 
00949   // If there is a last use in the same bb, we can't remove the live range.
00950   // Shorten the live interval and return.
00951   MachineBasicBlock *CopyMBB = CopyMI->getParent();
00952   if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR))
00953     return false;
00954 
00955   // There are other kills of the val#. Nothing to do.
00956   if (!li.isOnlyLROfValNo(LR))
00957     return false;
00958 
00959   MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart);
00960   if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_))
00961     // If the live range starts in another mbb and the copy mbb is not a fall
00962     // through mbb, then we can only cut the range from the beginning of the
00963     // copy mbb.
00964     RemoveStart = li_->getMBBStartIdx(CopyMBB) + 1;
00965 
00966   if (LR->valno->def == RemoveStart) {
00967     // If the def MI defines the val# and this copy is the only kill of the
00968     // val#, then propagate the dead marker.
00969     PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
00970     ++numDeadValNo;
00971 
00972     if (li.isKill(LR->valno, RemoveEnd))
00973       li.removeKill(LR->valno, RemoveEnd);
00974   }
00975 
00976   removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
00977   return removeIntervalIfEmpty(li, li_, tri_);
00978 }
00979 
00980 /// CanCoalesceWithImpDef - Returns true if the specified copy instruction
00981 /// from an implicit def to another register can be coalesced away.
00982 bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI,
00983                                                      LiveInterval &li,
00984                                                      LiveInterval &ImpLi) const{
00985   if (!CopyMI->killsRegister(ImpLi.reg))
00986     return false;
00987   // Make sure this is the only use.
00988   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(ImpLi.reg),
00989          UE = mri_->use_end(); UI != UE;) {
00990     MachineInstr *UseMI = &*UI;
00991     ++UI;
00992     if (CopyMI == UseMI || JoinedCopies.count(UseMI))
00993       continue;
00994     return false;
00995   }
00996   return true;
00997 }
00998 
00999 
01000 /// isWinToJoinVRWithSrcPhysReg - Return true if it's worth while to join a
01001 /// a virtual destination register with physical source register.
01002 bool
01003 SimpleRegisterCoalescing::isWinToJoinVRWithSrcPhysReg(MachineInstr *CopyMI,
01004                                                      MachineBasicBlock *CopyMBB,
01005                                                      LiveInterval &DstInt,
01006                                                      LiveInterval &SrcInt) {
01007   // If the virtual register live interval is long but it has low use desity,
01008   // do not join them, instead mark the physical register as its allocation
01009   // preference.
01010   const TargetRegisterClass *RC = mri_->getRegClass(DstInt.reg);
01011   unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
01012   unsigned Length = li_->getApproximateInstructionCount(DstInt);
01013   if (Length > Threshold &&
01014       (((float)std::distance(mri_->use_begin(DstInt.reg),
01015                              mri_->use_end()) / Length) < (1.0 / Threshold)))
01016     return false;
01017 
01018   // If the virtual register live interval extends into a loop, turn down
01019   // aggressiveness.
01020   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
01021   const MachineLoop *L = loopInfo->getLoopFor(CopyMBB);
01022   if (!L) {
01023     // Let's see if the virtual register live interval extends into the loop.
01024     LiveInterval::iterator DLR = DstInt.FindLiveRangeContaining(CopyIdx);
01025     assert(DLR != DstInt.end() && "Live range not found!");
01026     DLR = DstInt.FindLiveRangeContaining(DLR->end+1);
01027     if (DLR != DstInt.end()) {
01028       CopyMBB = li_->getMBBFromIndex(DLR->start);
01029       L = loopInfo->getLoopFor(CopyMBB);
01030     }
01031   }
01032 
01033   if (!L || Length <= Threshold)
01034     return true;
01035 
01036   unsigned UseIdx = li_->getUseIndex(CopyIdx);
01037   LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx);
01038   MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start);
01039   if (loopInfo->getLoopFor(SMBB) != L) {
01040     if (!loopInfo->isLoopHeader(CopyMBB))
01041       return false;
01042     // If vr's live interval extends pass the loop header, do not join.
01043     for (MachineBasicBlock::succ_iterator SI = CopyMBB->succ_begin(),
01044            SE = CopyMBB->succ_end(); SI != SE; ++SI) {
01045       MachineBasicBlock *SuccMBB = *SI;
01046       if (SuccMBB == CopyMBB)
01047         continue;
01048       if (DstInt.overlaps(li_->getMBBStartIdx(SuccMBB),
01049                           li_->getMBBEndIdx(SuccMBB)+1))
01050         return false;
01051     }
01052   }
01053   return true;
01054 }
01055 
01056 /// isWinToJoinVRWithDstPhysReg - Return true if it's worth while to join a
01057 /// copy from a virtual source register to a physical destination register.
01058 bool
01059 SimpleRegisterCoalescing::isWinToJoinVRWithDstPhysReg(MachineInstr *CopyMI,
01060                                                      MachineBasicBlock *CopyMBB,
01061                                                      LiveInterval &DstInt,
01062                                                      LiveInterval &SrcInt) {
01063   // If the virtual register live interval is long but it has low use desity,
01064   // do not join them, instead mark the physical register as its allocation
01065   // preference.
01066   const TargetRegisterClass *RC = mri_->getRegClass(SrcInt.reg);
01067   unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
01068   unsigned Length = li_->getApproximateInstructionCount(SrcInt);
01069   if (Length > Threshold &&
01070       (((float)std::distance(mri_->use_begin(SrcInt.reg),
01071                              mri_->use_end()) / Length) < (1.0 / Threshold)))
01072     return false;
01073 
01074   if (SrcInt.empty())
01075     // Must be implicit_def.
01076     return false;
01077 
01078   // If the virtual register live interval is defined or cross a loop, turn
01079   // down aggressiveness.
01080   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
01081   unsigned UseIdx = li_->getUseIndex(CopyIdx);
01082   LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx);
01083   assert(SLR != SrcInt.end() && "Live range not found!");
01084   SLR = SrcInt.FindLiveRangeContaining(SLR->start-1);
01085   if (SLR == SrcInt.end())
01086     return true;
01087   MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start);
01088   const MachineLoop *L = loopInfo->getLoopFor(SMBB);
01089 
01090   if (!L || Length <= Threshold)
01091     return true;
01092 
01093   if (loopInfo->getLoopFor(CopyMBB) != L) {
01094     if (SMBB != L->getLoopLatch())
01095       return false;
01096     // If vr's live interval is extended from before the loop latch, do not
01097     // join.
01098     for (MachineBasicBlock::pred_iterator PI = SMBB->pred_begin(),
01099            PE = SMBB->pred_end(); PI != PE; ++PI) {
01100       MachineBasicBlock *PredMBB = *PI;
01101       if (PredMBB == SMBB)
01102         continue;
01103       if (SrcInt.overlaps(li_->getMBBStartIdx(PredMBB),
01104                           li_->getMBBEndIdx(PredMBB)+1))
01105         return false;
01106     }
01107   }
01108   return true;
01109 }
01110 
01111 /// isWinToJoinCrossClass - Return true if it's profitable to coalesce
01112 /// two virtual registers from different register classes.
01113 bool
01114 SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned LargeReg,
01115                                                 unsigned SmallReg,
01116                                                 unsigned Threshold) {
01117   // Then make sure the intervals are *short*.
01118   LiveInterval &LargeInt = li_->getInterval(LargeReg);
01119   LiveInterval &SmallInt = li_->getInterval(SmallReg);
01120   unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt);
01121   unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt);
01122   if (SmallSize > Threshold || LargeSize > Threshold)
01123     if ((float)std::distance(mri_->use_begin(SmallReg),
01124                              mri_->use_end()) / SmallSize <
01125         (float)std::distance(mri_->use_begin(LargeReg),
01126                              mri_->use_end()) / LargeSize)
01127       return false;
01128   return true;
01129 }
01130 
01131 /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual
01132 /// register with a physical register, check if any of the virtual register
01133 /// operand is a sub-register use or def. If so, make sure it won't result
01134 /// in an illegal extract_subreg or insert_subreg instruction. e.g.
01135 /// vr1024 = extract_subreg vr1025, 1
01136 /// ...
01137 /// vr1024 = mov8rr AH
01138 /// If vr1024 is coalesced with AH, the extract_subreg is now illegal since
01139 /// AH does not have a super-reg whose sub-register 1 is AH.
01140 bool
01141 SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI,
01142                                                       unsigned VirtReg,
01143                                                       unsigned PhysReg) {
01144   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(VirtReg),
01145          E = mri_->reg_end(); I != E; ++I) {
01146     MachineOperand &O = I.getOperand();
01147     MachineInstr *MI = &*I;
01148     if (MI == CopyMI || JoinedCopies.count(MI))
01149       continue;
01150     unsigned SubIdx = O.getSubReg();
01151     if (SubIdx && !tri_->getSubReg(PhysReg, SubIdx))
01152       return true;
01153     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
01154       SubIdx = MI->getOperand(2).getImm();
01155       if (O.isUse() && !tri_->getSubReg(PhysReg, SubIdx))
01156         return true;
01157       if (O.isDef()) {
01158         unsigned SrcReg = MI->getOperand(1).getReg();
01159         const TargetRegisterClass *RC =
01160           TargetRegisterInfo::isPhysicalRegister(SrcReg)
01161           ? tri_->getPhysicalRegisterRegClass(SrcReg)
01162           : mri_->getRegClass(SrcReg);
01163         if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC))
01164           return true;
01165       }
01166     }
01167     if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
01168         MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) {
01169       SubIdx = MI->getOperand(3).getImm();
01170       if (VirtReg == MI->getOperand(0).getReg()) {
01171         if (!tri_->getSubReg(PhysReg, SubIdx))
01172           return true;
01173       } else {
01174         unsigned DstReg = MI->getOperand(0).getReg();
01175         const TargetRegisterClass *RC =
01176           TargetRegisterInfo::isPhysicalRegister(DstReg)
01177           ? tri_->getPhysicalRegisterRegClass(DstReg)
01178           : mri_->getRegClass(DstReg);
01179         if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC))
01180           return true;
01181       }
01182     }
01183   }
01184   return false;
01185 }
01186 
01187 
01188 /// CanJoinExtractSubRegToPhysReg - Return true if it's possible to coalesce
01189 /// an extract_subreg where dst is a physical register, e.g.
01190 /// cl = EXTRACT_SUBREG reg1024, 1
01191 bool
01192 SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(unsigned DstReg,
01193                                                unsigned SrcReg, unsigned SubIdx,
01194                                                unsigned &RealDstReg) {
01195   const TargetRegisterClass *RC = mri_->getRegClass(SrcReg);
01196   RealDstReg = tri_->getMatchingSuperReg(DstReg, SubIdx, RC);
01197   assert(RealDstReg && "Invalid extract_subreg instruction!");
01198 
01199   // For this type of EXTRACT_SUBREG, conservatively
01200   // check if the live interval of the source register interfere with the
01201   // actual super physical register we are trying to coalesce with.
01202   LiveInterval &RHS = li_->getInterval(SrcReg);
01203   if (li_->hasInterval(RealDstReg) &&
01204       RHS.overlaps(li_->getInterval(RealDstReg))) {
01205     DOUT << "Interfere with register ";
01206     DEBUG(li_->getInterval(RealDstReg).print(DOUT, tri_));
01207     return false; // Not coalescable
01208   }
01209   for (const unsigned* SR = tri_->getSubRegisters(RealDstReg); *SR; ++SR)
01210     if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
01211       DOUT << "Interfere with sub-register ";
01212       DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
01213       return false; // Not coalescable
01214     }
01215   return true;
01216 }
01217 
01218 /// CanJoinInsertSubRegToPhysReg - Return true if it's possible to coalesce
01219 /// an insert_subreg where src is a physical register, e.g.
01220 /// reg1024 = INSERT_SUBREG reg1024, c1, 0
01221 bool
01222 SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(unsigned DstReg,
01223                                                unsigned SrcReg, unsigned SubIdx,
01224                                                unsigned &RealSrcReg) {
01225   const TargetRegisterClass *RC = mri_->getRegClass(DstReg);
01226   RealSrcReg = tri_->getMatchingSuperReg(SrcReg, SubIdx, RC);
01227   assert(RealSrcReg && "Invalid extract_subreg instruction!");
01228 
01229   LiveInterval &RHS = li_->getInterval(DstReg);
01230   if (li_->hasInterval(RealSrcReg) &&
01231       RHS.overlaps(li_->getInterval(RealSrcReg))) {
01232     DOUT << "Interfere with register ";
01233     DEBUG(li_->getInterval(RealSrcReg).print(DOUT, tri_));
01234     return false; // Not coalescable
01235   }
01236   for (const unsigned* SR = tri_->getSubRegisters(RealSrcReg); *SR; ++SR)
01237     if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
01238       DOUT << "Interfere with sub-register ";
01239       DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
01240       return false; // Not coalescable
01241     }
01242   return true;
01243 }
01244 
01245 /// getRegAllocPreference - Return register allocation preference register.
01246 ///
01247 static unsigned getRegAllocPreference(unsigned Reg, MachineFunction &MF,
01248                                       MachineRegisterInfo *MRI,
01249                                       const TargetRegisterInfo *TRI) {
01250   if (TargetRegisterInfo::isPhysicalRegister(Reg))
01251     return 0;
01252   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(Reg);
01253   return TRI->ResolveRegAllocHint(Hint.first, Hint.second, MF);
01254 }
01255 
01256 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
01257 /// which are the src/dst of the copy instruction CopyMI.  This returns true
01258 /// if the copy was successfully coalesced away. If it is not currently
01259 /// possible to coalesce this interval, but it may be possible if other
01260 /// things get coalesced, then it returns true by reference in 'Again'.
01261 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
01262   MachineInstr *CopyMI = TheCopy.MI;
01263 
01264   Again = false;
01265   if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI))
01266     return false; // Already done.
01267 
01268   DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI;
01269 
01270   unsigned SrcReg, DstReg, SrcSubIdx = 0, DstSubIdx = 0;
01271   bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG;
01272   bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG;
01273   bool isSubRegToReg = CopyMI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG;
01274   unsigned SubIdx = 0;
01275   if (isExtSubReg) {
01276     DstReg    = CopyMI->getOperand(0).getReg();
01277     DstSubIdx = CopyMI->getOperand(0).getSubReg();
01278     SrcReg    = CopyMI->getOperand(1).getReg();
01279     SrcSubIdx = CopyMI->getOperand(2).getImm();
01280   } else if (isInsSubReg || isSubRegToReg) {
01281     DstReg    = CopyMI->getOperand(0).getReg();
01282     DstSubIdx = CopyMI->getOperand(3).getImm();
01283     SrcReg    = CopyMI->getOperand(2).getReg();
01284     SrcSubIdx = CopyMI->getOperand(2).getSubReg();
01285     if (SrcSubIdx && SrcSubIdx != DstSubIdx) {
01286       // r1025 = INSERT_SUBREG r1025, r1024<2>, 2 Then r1024 has already been
01287       // coalesced to a larger register so the subreg indices cancel out.
01288       DOUT << "\tSource of insert_subreg is already coalesced "
01289            << "to another register.\n";
01290       return false;  // Not coalescable.
01291     }
01292   } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)){
01293     llvm_unreachable("Unrecognized copy instruction!");
01294   }
01295 
01296   // If they are already joined we continue.
01297   if (SrcReg == DstReg) {
01298     DOUT << "\tCopy already coalesced.\n";
01299     return false;  // Not coalescable.
01300   }
01301   
01302   bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
01303   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
01304 
01305   // If they are both physical registers, we cannot join them.
01306   if (SrcIsPhys && DstIsPhys) {
01307     DOUT << "\tCan not coalesce physregs.\n";
01308     return false;  // Not coalescable.
01309   }
01310   
01311   // We only join virtual registers with allocatable physical registers.
01312   if (SrcIsPhys && !allocatableRegs_[SrcReg]) {
01313     DOUT << "\tSrc reg is unallocatable physreg.\n";
01314     return false;  // Not coalescable.
01315   }
01316   if (DstIsPhys && !allocatableRegs_[DstReg]) {
01317     DOUT << "\tDst reg is unallocatable physreg.\n";
01318     return false;  // Not coalescable.
01319   }
01320 
01321   // Check that a physical source register is compatible with dst regclass
01322   if (SrcIsPhys) {
01323     unsigned SrcSubReg = SrcSubIdx ?
01324       tri_->getSubReg(SrcReg, SrcSubIdx) : SrcReg;
01325     const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg);
01326     const TargetRegisterClass *DstSubRC = DstRC;
01327     if (DstSubIdx)
01328       DstSubRC = DstRC->getSubRegisterRegClass(DstSubIdx);
01329     assert(DstSubRC && "Illegal subregister index");
01330     if (!DstSubRC->contains(SrcSubReg)) {
01331       DEBUG(errs() << "\tIncompatible destination regclass: "
01332             << tri_->getName(SrcSubReg) << " not in " << DstSubRC->getName()
01333             << ".\n");
01334       return false;             // Not coalescable.
01335     }
01336   }
01337 
01338   // Check that a physical dst register is compatible with source regclass
01339   if (DstIsPhys) {
01340     unsigned DstSubReg = DstSubIdx ?
01341       tri_->getSubReg(DstReg, DstSubIdx) : DstReg;
01342     const TargetRegisterClass *SrcRC = mri_->getRegClass(SrcReg);
01343     const TargetRegisterClass *SrcSubRC = SrcRC;
01344     if (SrcSubIdx)
01345       SrcSubRC = SrcRC->getSubRegisterRegClass(SrcSubIdx);
01346     assert(SrcSubRC && "Illegal subregister index");
01347     if (!SrcSubRC->contains(DstReg)) {
01348       DEBUG(errs() << "\tIncompatible source regclass: "
01349             << tri_->getName(DstSubReg) << " not in " << SrcSubRC->getName()
01350             << ".\n");
01351       (void)DstSubReg;
01352       return false;             // Not coalescable.
01353     }
01354   }
01355 
01356   // Should be non-null only when coalescing to a sub-register class.
01357   bool CrossRC = false;
01358   const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg);
01359   const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg);
01360   const TargetRegisterClass *NewRC = NULL;
01361   MachineBasicBlock *CopyMBB = CopyMI->getParent();
01362   unsigned RealDstReg = 0;
01363   unsigned RealSrcReg = 0;
01364   if (isExtSubReg || isInsSubReg || isSubRegToReg) {
01365     SubIdx = CopyMI->getOperand(isExtSubReg ? 2 : 3).getImm();
01366     if (SrcIsPhys && isExtSubReg) {
01367       // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be
01368       // coalesced with AX.
01369       unsigned DstSubIdx = CopyMI->getOperand(0).getSubReg();
01370       if (DstSubIdx) {
01371         // r1024<2> = EXTRACT_SUBREG EAX, 2. Then r1024 has already been
01372         // coalesced to a larger register so the subreg indices cancel out.
01373         if (DstSubIdx != SubIdx) {
01374           DOUT << "\t Sub-register indices mismatch.\n";
01375           return false; // Not coalescable.
01376         }
01377       } else
01378         SrcReg = tri_->getSubReg(SrcReg, SubIdx);
01379       SubIdx = 0;
01380     } else if (DstIsPhys && (isInsSubReg || isSubRegToReg)) {
01381       // EAX = INSERT_SUBREG EAX, r1024, 0
01382       unsigned SrcSubIdx = CopyMI->getOperand(2).getSubReg();
01383       if (SrcSubIdx) {
01384         // EAX = INSERT_SUBREG EAX, r1024<2>, 2 Then r1024 has already been
01385         // coalesced to a larger register so the subreg indices cancel out.
01386         if (SrcSubIdx != SubIdx) {
01387           DOUT << "\t Sub-register indices mismatch.\n";
01388           return false; // Not coalescable.
01389         }
01390       } else
01391         DstReg = tri_->getSubReg(DstReg, SubIdx);
01392       SubIdx = 0;
01393     } else if ((DstIsPhys && isExtSubReg) ||
01394                (SrcIsPhys && (isInsSubReg || isSubRegToReg))) {
01395       if (!isSubRegToReg && CopyMI->getOperand(1).getSubReg()) {
01396         DOUT << "\tSrc of extract_subreg already coalesced with reg"
01397              << " of a super-class.\n";
01398         return false; // Not coalescable.
01399       }
01400 
01401       if (isExtSubReg) {
01402         if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg))
01403           return false; // Not coalescable
01404       } else {
01405         if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg))
01406           return false; // Not coalescable
01407       }
01408       SubIdx = 0;
01409     } else {
01410       unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg()
01411         : CopyMI->getOperand(2).getSubReg();
01412       if (OldSubIdx) {
01413         if (OldSubIdx == SubIdx && !differingRegisterClasses(SrcReg, DstReg))
01414           // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been
01415           // coalesced to a larger register so the subreg indices cancel out.
01416           // Also check if the other larger register is of the same register
01417           // class as the would be resulting register.
01418           SubIdx = 0;
01419         else {
01420           DOUT << "\t Sub-register indices mismatch.\n";
01421           return false; // Not coalescable.
01422         }
01423       }
01424       if (SubIdx) {
01425         if (!DstIsPhys && !SrcIsPhys) {
01426           if (isInsSubReg || isSubRegToReg) {
01427             NewRC = tri_->getMatchingSuperRegClass(DstRC, SrcRC, SubIdx);
01428           } else // extract_subreg {
01429             NewRC = tri_->getMatchingSuperRegClass(SrcRC, DstRC, SubIdx);
01430           }
01431         if (!NewRC) {
01432           DOUT << "\t Conflicting sub-register indices.\n";
01433           return false;  // Not coalescable
01434         }
01435 
01436         unsigned LargeReg = isExtSubReg ? SrcReg : DstReg;
01437         unsigned SmallReg = isExtSubReg ? DstReg : SrcReg;
01438         unsigned Limit= allocatableRCRegs_[mri_->getRegClass(SmallReg)].count();
01439         if (!isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) {
01440           Again = true;  // May be possible to coalesce later.
01441           return false;
01442         }
01443       }
01444     }
01445   } else if (differingRegisterClasses(SrcReg, DstReg)) {
01446     if (DisableCrossClassJoin)
01447       return false;
01448     CrossRC = true;
01449 
01450     // FIXME: What if the result of a EXTRACT_SUBREG is then coalesced
01451     // with another? If it's the resulting destination register, then
01452     // the subidx must be propagated to uses (but only those defined
01453     // by the EXTRACT_SUBREG). If it's being coalesced into another
01454     // register, it should be safe because register is assumed to have
01455     // the register class of the super-register.
01456 
01457     // Process moves where one of the registers have a sub-register index.
01458     MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg);
01459     MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg);
01460     SubIdx = DstMO->getSubReg();
01461     if (SubIdx) {
01462       if (SrcMO->getSubReg())
01463         // FIXME: can we handle this?
01464         return false;
01465       // This is not an insert_subreg but it looks like one.
01466       // e.g. %reg1024:4 = MOV32rr %EAX
01467       isInsSubReg = true;
01468       if (SrcIsPhys) {
01469         if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg))
01470           return false; // Not coalescable
01471         SubIdx = 0;
01472       }
01473     } else {
01474       SubIdx = SrcMO->getSubReg();
01475       if (SubIdx) {
01476         // This is not a extract_subreg but it looks like one.
01477         // e.g. %cl = MOV16rr %reg1024:1
01478         isExtSubReg = true;
01479         if (DstIsPhys) {
01480           if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg))
01481             return false; // Not coalescable
01482           SubIdx = 0;
01483         }
01484       }
01485     }
01486 
01487     unsigned LargeReg = SrcReg;
01488     unsigned SmallReg = DstReg;
01489 
01490     // Now determine the register class of the joined register.
01491     if (isExtSubReg) {
01492       if (SubIdx && DstRC && DstRC->isASubClass()) {
01493         // This is a move to a sub-register class. However, the source is a
01494         // sub-register of a larger register class. We don't know what should
01495         // the register class be. FIXME.
01496         Again = true;
01497         return false;
01498       }
01499       if (!DstIsPhys && !SrcIsPhys)
01500         NewRC = SrcRC;
01501     } else if (!SrcIsPhys && !DstIsPhys) {
01502       NewRC = getCommonSubClass(SrcRC, DstRC);
01503       if (!NewRC) {
01504         DEBUG(errs() << "\tDisjoint regclasses: "
01505               << SrcRC->getName() << ", "
01506               << DstRC->getName() << ".\n");
01507         return false;           // Not coalescable.
01508       }
01509       if (DstRC->getSize() > SrcRC->getSize())
01510         std::swap(LargeReg, SmallReg);
01511     }
01512 
01513     // If we are joining two virtual registers and the resulting register
01514     // class is more restrictive (fewer register, smaller size). Check if it's
01515     // worth doing the merge.
01516     if (!SrcIsPhys && !DstIsPhys &&
01517         (isExtSubReg || DstRC->isASubClass()) &&
01518         !isWinToJoinCrossClass(LargeReg, SmallReg,
01519                                allocatableRCRegs_[NewRC].count())) {
01520       DOUT << "\tSrc/Dest are different register classes.\n";
01521       // Allow the coalescer to try again in case either side gets coalesced to
01522       // a physical register that's compatible with the other side. e.g.
01523       // r1024 = MOV32to32_ r1025
01524       // But later r1024 is assigned EAX then r1025 may be coalesced with EAX.
01525       Again = true;  // May be possible to coalesce later.
01526       return false;
01527     }
01528   }
01529 
01530   // Will it create illegal extract_subreg / insert_subreg?
01531   if (SrcIsPhys && HasIncompatibleSubRegDefUse(CopyMI, DstReg, SrcReg))
01532     return false;
01533   if (DstIsPhys && HasIncompatibleSubRegDefUse(CopyMI, SrcReg, DstReg))
01534     return false;
01535   
01536   LiveInterval &SrcInt = li_->getInterval(SrcReg);
01537   LiveInterval &DstInt = li_->getInterval(DstReg);
01538   assert(SrcInt.reg == SrcReg && DstInt.reg == DstReg &&
01539          "Register mapping is horribly broken!");
01540 
01541   DOUT << "\t\tInspecting "; SrcInt.print(DOUT, tri_);
01542   DOUT << " and "; DstInt.print(DOUT, tri_);
01543   DOUT << ": ";
01544 
01545   // Save a copy of the virtual register live interval. We'll manually
01546   // merge this into the "real" physical register live interval this is
01547   // coalesced with.
01548   LiveInterval *SavedLI = 0;
01549   if (RealDstReg)
01550     SavedLI = li_->dupInterval(&SrcInt);
01551   else if (RealSrcReg)
01552     SavedLI = li_->dupInterval(&DstInt);
01553 
01554   // Check if it is necessary to propagate "isDead" property.
01555   if (!isExtSubReg && !isInsSubReg && !isSubRegToReg) {
01556     MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false);
01557     bool isDead = mopd->isDead();
01558 
01559     // We need to be careful about coalescing a source physical register with a
01560     // virtual register. Once the coalescing is done, it cannot be broken and
01561     // these are not spillable! If the destination interval uses are far away,
01562     // think twice about coalescing them!
01563     if (!isDead && (SrcIsPhys || DstIsPhys)) {
01564       // If the copy is in a loop, take care not to coalesce aggressively if the
01565       // src is coming in from outside the loop (or the dst is out of the loop).
01566       // If it's not in a loop, then determine whether to join them base purely
01567       // by the length of the interval.
01568       if (PhysJoinTweak) {
01569         if (SrcIsPhys) {
01570           if (!isWinToJoinVRWithSrcPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) {
01571             mri_->setRegAllocationHint(DstInt.reg, 0, SrcReg);
01572             ++numAborts;
01573             DOUT << "\tMay tie down a physical register, abort!\n";
01574             Again = true;  // May be possible to coalesce later.
01575             return false;
01576           }
01577         } else {
01578           if (!isWinToJoinVRWithDstPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) {
01579             mri_->setRegAllocationHint(SrcInt.reg, 0, DstReg);
01580             ++numAborts;
01581             DOUT << "\tMay tie down a physical register, abort!\n";
01582             Again = true;  // May be possible to coalesce later.
01583             return false;
01584           }
01585         }
01586       } else {
01587         // If the virtual register live interval is long but it has low use desity,
01588         // do not join them, instead mark the physical register as its allocation
01589         // preference.
01590         LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
01591         unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg;
01592         unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg;
01593         const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg);
01594         unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
01595         if (TheCopy.isBackEdge)
01596           Threshold *= 2; // Favors back edge copies.
01597 
01598         unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
01599         float Ratio = 1.0 / Threshold;
01600         if (Length > Threshold &&
01601             (((float)std::distance(mri_->use_begin(JoinVReg),
01602                                    mri_->use_end()) / Length) < Ratio)) {
01603           mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg);
01604           ++numAborts;
01605           DOUT << "\tMay tie down a physical register, abort!\n";
01606           Again = true;  // May be possible to coalesce later.
01607           return false;
01608         }
01609       }
01610     }
01611   }
01612 
01613   // Okay, attempt to join these two intervals.  On failure, this returns false.
01614   // Otherwise, if one of the intervals being joined is a physreg, this method
01615   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
01616   // been modified, so we can use this information below to update aliases.
01617   bool Swapped = false;
01618   // If SrcInt is implicitly defined, it's safe to coalesce.
01619   bool isEmpty = SrcInt.empty();
01620   if (isEmpty && !CanCoalesceWithImpDef(CopyMI, DstInt, SrcInt)) {
01621     // Only coalesce an empty interval (defined by implicit_def) with
01622     // another interval which has a valno defined by the CopyMI and the CopyMI
01623     // is a kill of the implicit def.
01624     DOUT << "Not profitable!\n";
01625     return false;
01626   }
01627 
01628   if (!isEmpty && !JoinIntervals(DstInt, SrcInt, Swapped)) {
01629     // Coalescing failed.
01630 
01631     // If definition of source is defined by trivial computation, try
01632     // rematerializing it.
01633     if (!isExtSubReg && !isInsSubReg && !isSubRegToReg &&
01634         ReMaterializeTrivialDef(SrcInt, DstReg, DstSubIdx, CopyMI))
01635       return true;
01636     
01637     // If we can eliminate the copy without merging the live ranges, do so now.
01638     if (!isExtSubReg && !isInsSubReg && !isSubRegToReg &&
01639         (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) ||
01640          RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) {
01641       JoinedCopies.insert(CopyMI);
01642       return true;
01643     }
01644     
01645     // Otherwise, we are unable to join the intervals.
01646     DOUT << "Interference!\n";
01647     Again = true;  // May be possible to coalesce later.
01648     return false;
01649   }
01650 
01651   LiveInterval *ResSrcInt = &SrcInt;
01652   LiveInterval *ResDstInt = &DstInt;
01653   if (Swapped) {
01654     std::swap(SrcReg, DstReg);
01655     std::swap(ResSrcInt, ResDstInt);
01656   }
01657   assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
01658          "LiveInterval::join didn't work right!");
01659                                
01660   // If we're about to merge live ranges into a physical register live interval,
01661   // we have to update any aliased register's live ranges to indicate that they
01662   // have clobbered values for this range.
01663   if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
01664     // If this is a extract_subreg where dst is a physical register, e.g.
01665     // cl = EXTRACT_SUBREG reg1024, 1
01666     // then create and update the actual physical register allocated to RHS.
01667     if (RealDstReg || RealSrcReg) {
01668       LiveInterval &RealInt =
01669         li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg);
01670       for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(),
01671              E = SavedLI->vni_end(); I != E; ++I) {
01672         const VNInfo *ValNo = *I;
01673         VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(),
01674                                                 false, // updated at *
01675                                                 li_->getVNInfoAllocator());
01676         NewValNo->setFlags(ValNo->getFlags()); // * updated here.
01677         RealInt.addKills(NewValNo, ValNo->kills);
01678         RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo);
01679       }
01680       RealInt.weight += SavedLI->weight;      
01681       DstReg = RealDstReg ? RealDstReg : RealSrcReg;
01682     }
01683 
01684     // Update the liveintervals of sub-registers.
01685     for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
01686       li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
01687                                                  li_->getVNInfoAllocator());
01688   }
01689 
01690   // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the
01691   // larger super-register.
01692   if ((isExtSubReg || isInsSubReg || isSubRegToReg) &&
01693       !SrcIsPhys && !DstIsPhys) {
01694     if ((isExtSubReg && !Swapped) ||
01695         ((isInsSubReg || isSubRegToReg) && Swapped)) {
01696       ResSrcInt->Copy(*ResDstInt, mri_, li_->getVNInfoAllocator());
01697       std::swap(SrcReg, DstReg);
01698       std::swap(ResSrcInt, ResDstInt);
01699     }
01700   }
01701 
01702   // Coalescing to a virtual register that is of a sub-register class of the
01703   // other. Make sure the resulting register is set to the right register class.
01704   if (CrossRC)
01705     ++numCrossRCs;
01706 
01707   // This may happen even if it's cross-rc coalescing. e.g.
01708   // %reg1026<def> = SUBREG_TO_REG 0, %reg1037<kill>, 4
01709   // reg1026 -> GR64, reg1037 -> GR32_ABCD. The resulting register will have to
01710   // be allocate a register from GR64_ABCD.
01711   if (NewRC)
01712     mri_->setRegClass(DstReg, NewRC);
01713 
01714   if (NewHeuristic) {
01715     // Add all copies that define val# in the source interval into the queue.
01716     for (LiveInterval::const_vni_iterator i = ResSrcInt->vni_begin(),
01717            e = ResSrcInt->vni_end(); i != e; ++i) {
01718       const VNInfo *vni = *i;
01719       // FIXME: Do isPHIDef and isDefAccurate both need to be tested?
01720       if (!vni->def || vni->isUnused() || vni->isPHIDef() || !vni->isDefAccurate())
01721         continue;
01722       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
01723       unsigned NewSrcReg, NewDstReg, NewSrcSubIdx, NewDstSubIdx;
01724       if (CopyMI &&
01725           JoinedCopies.count(CopyMI) == 0 &&
01726           tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg,
01727                             NewSrcSubIdx, NewDstSubIdx)) {
01728         unsigned LoopDepth = loopInfo->getLoopDepth(CopyMBB);
01729         JoinQueue->push(CopyRec(CopyMI, LoopDepth,
01730                                 isBackEdgeCopy(CopyMI, DstReg)));
01731       }
01732     }
01733   }
01734 
01735   // Remember to delete the copy instruction.
01736   JoinedCopies.insert(CopyMI);
01737 
01738   // Some live range has been lengthened due to colaescing, eliminate the
01739   // unnecessary kills.
01740   RemoveUnnecessaryKills(SrcReg, *ResDstInt);
01741   if (TargetRegisterInfo::isVirtualRegister(DstReg))
01742     RemoveUnnecessaryKills(DstReg, *ResDstInt);
01743 
01744   UpdateRegDefsUses(SrcReg, DstReg, SubIdx);
01745 
01746   // SrcReg is guarateed to be the register whose live interval that is
01747   // being merged.
01748   li_->removeInterval(SrcReg);
01749 
01750   // Update regalloc hint.
01751   tri_->UpdateRegAllocHint(SrcReg, DstReg, *mf_);
01752 
01753   // Manually deleted the live interval copy.
01754   if (SavedLI) {
01755     SavedLI->clear();
01756     delete SavedLI;
01757   }
01758 
01759   // If resulting interval has a preference that no longer fits because of subreg
01760   // coalescing, just clear the preference.
01761   unsigned Preference = getRegAllocPreference(ResDstInt->reg, *mf_, mri_, tri_);
01762   if (Preference && (isExtSubReg || isInsSubReg || isSubRegToReg) &&
01763       TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) {
01764     const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg);
01765     if (!RC->contains(Preference))
01766       mri_->setRegAllocationHint(ResDstInt->reg, 0, 0);
01767   }
01768 
01769   DOUT << "\n\t\tJoined.  Result = "; ResDstInt->print(DOUT, tri_);
01770   DOUT << "\n";
01771 
01772   ++numJoins;
01773   return true;
01774 }
01775 
01776 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
01777 /// compute what the resultant value numbers for each value in the input two
01778 /// ranges will be.  This is complicated by copies between the two which can
01779 /// and will commonly cause multiple value numbers to be merged into one.
01780 ///
01781 /// VN is the value number that we're trying to resolve.  InstDefiningValue
01782 /// keeps track of the new InstDefiningValue assignment for the result
01783 /// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
01784 /// whether a value in this or other is a copy from the opposite set.
01785 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
01786 /// already been assigned.
01787 ///
01788 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
01789 /// contains the value number the copy is from.
01790 ///
01791 static unsigned ComputeUltimateVN(VNInfo *VNI,
01792                                   SmallVector<VNInfo*, 16> &NewVNInfo,
01793                                   DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
01794                                   DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
01795                                   SmallVector<int, 16> &ThisValNoAssignments,
01796                                   SmallVector<int, 16> &OtherValNoAssignments) {
01797   unsigned VN = VNI->id;
01798 
01799   // If the VN has already been computed, just return it.
01800   if (ThisValNoAssignments[VN] >= 0)
01801     return ThisValNoAssignments[VN];
01802 //  assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?");
01803 
01804   // If this val is not a copy from the other val, then it must be a new value
01805   // number in the destination.
01806   DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
01807   if (I == ThisFromOther.end()) {
01808     NewVNInfo.push_back(VNI);
01809     return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
01810   }
01811   VNInfo *OtherValNo = I->second;
01812 
01813   // Otherwise, this *is* a copy from the RHS.  If the other side has already
01814   // been computed, return it.
01815   if (OtherValNoAssignments[OtherValNo->id] >= 0)
01816     return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
01817   
01818   // Mark this value number as currently being computed, then ask what the
01819   // ultimate value # of the other value is.
01820   ThisValNoAssignments[VN] = -2;
01821   unsigned UltimateVN =
01822     ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
01823                       OtherValNoAssignments, ThisValNoAssignments);
01824   return ThisValNoAssignments[VN] = UltimateVN;
01825 }
01826 
01827 static bool InVector(VNInfo *Val, const SmallVector<VNInfo*, 8> &V) {
01828   return std::find(V.begin(), V.end(), Val) != V.end();
01829 }
01830 
01831 /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of
01832 /// the specified live interval is defined by a copy from the specified
01833 /// register.
01834 bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li,
01835                                                            LiveRange *LR,
01836                                                            unsigned Reg) {
01837   unsigned SrcReg = li_->getVNInfoSourceReg(LR->valno);
01838   if (SrcReg == Reg)
01839     return true;
01840   // FIXME: Do isPHIDef and isDefAccurate both need to be tested?
01841   if ((LR->valno->isPHIDef() || !LR->valno->isDefAccurate()) &&
01842       TargetRegisterInfo::isPhysicalRegister(li.reg) &&
01843       *tri_->getSuperRegisters(li.reg)) {
01844     // It's a sub-register live interval, we may not have precise information.
01845     // Re-compute it.
01846     MachineInstr *DefMI = li_->getInstructionFromIndex(LR->start);
01847     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
01848     if (DefMI &&
01849         tii_->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
01850         DstReg == li.reg && SrcReg == Reg) {
01851       // Cache computed info.
01852       LR->valno->def  = LR->start;
01853       LR->valno->setCopy(DefMI);
01854       return true;
01855     }
01856   }
01857   return false;
01858 }
01859 
01860 /// SimpleJoin - Attempt to joint the specified interval into this one. The
01861 /// caller of this method must guarantee that the RHS only contains a single
01862 /// value number and that the RHS is not defined by a copy from this
01863 /// interval.  This returns false if the intervals are not joinable, or it
01864 /// joins them and returns true.
01865 bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){
01866   assert(RHS.containsOneValue());
01867   
01868   // Some number (potentially more than one) value numbers in the current
01869   // interval may be defined as copies from the RHS.  Scan the overlapping
01870   // portions of the LHS and RHS, keeping track of this and looking for
01871   // overlapping live ranges that are NOT defined as copies.  If these exist, we
01872   // cannot coalesce.
01873   
01874   LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end();
01875   LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end();
01876   
01877   if (LHSIt->start < RHSIt->start) {
01878     LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start);
01879     if (LHSIt != LHS.begin()) --LHSIt;
01880   } else if (RHSIt->start < LHSIt->start) {
01881     RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start);
01882     if (RHSIt != RHS.begin()) --RHSIt;
01883   }
01884   
01885   SmallVector<VNInfo*, 8> EliminatedLHSVals;
01886   
01887   while (1) {
01888     // Determine if these live intervals overlap.
01889     bool Overlaps = false;
01890     if (LHSIt->start <= RHSIt->start)
01891       Overlaps = LHSIt->end > RHSIt->start;
01892     else
01893       Overlaps = RHSIt->end > LHSIt->start;
01894     
01895     // If the live intervals overlap, there are two interesting cases: if the
01896     // LHS interval is defined by a copy from the RHS, it's ok and we record
01897     // that the LHS value # is the same as the RHS.  If it's not, then we cannot
01898     // coalesce these live ranges and we bail out.
01899     if (Overlaps) {
01900       // If we haven't already recorded that this value # is safe, check it.
01901       if (!InVector(LHSIt->valno, EliminatedLHSVals)) {
01902         // Copy from the RHS?
01903         if (!RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg))
01904           return false;    // Nope, bail out.
01905 
01906         if (LHSIt->contains(RHSIt->valno->def))
01907           // Here is an interesting situation:
01908           // BB1:
01909           //   vr1025 = copy vr1024
01910           //   ..
01911           // BB2:
01912           //   vr1024 = op 
01913           //          = vr1025
01914           // Even though vr1025 is copied from vr1024, it's not safe to
01915           // coalesce them since the live range of vr1025 intersects the
01916           // def of vr1024. This happens because vr1025 is assigned the
01917           // value of the previous iteration of vr1024.
01918           return false;
01919         EliminatedLHSVals.push_back(LHSIt->valno);
01920       }
01921       
01922       // We know this entire LHS live range is okay, so skip it now.
01923       if (++LHSIt == LHSEnd) break;
01924       continue;
01925     }
01926     
01927     if (LHSIt->end < RHSIt->end) {
01928       if (++LHSIt == LHSEnd) break;
01929     } else {
01930       // One interesting case to check here.  It's possible that we have
01931       // something like "X3 = Y" which defines a new value number in the LHS,
01932       // and is the last use of this liverange of the RHS.  In this case, we
01933       // want to notice this copy (so that it gets coalesced away) even though
01934       // the live ranges don't actually overlap.
01935       if (LHSIt->start == RHSIt->end) {
01936         if (InVector(LHSIt->valno, EliminatedLHSVals)) {
01937           // We already know that this value number is going to be merged in
01938           // if coalescing succeeds.  Just skip the liverange.
01939           if (++LHSIt == LHSEnd) break;
01940         } else {
01941           // Otherwise, if this is a copy from the RHS, mark it as being merged
01942           // in.
01943           if (RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg)) {
01944             if (LHSIt->contains(RHSIt->valno->def))
01945               // Here is an interesting situation:
01946               // BB1:
01947               //   vr1025 = copy vr1024
01948               //   ..
01949               // BB2:
01950               //   vr1024 = op 
01951               //          = vr1025
01952               // Even though vr1025 is copied from vr1024, it's not safe to
01953               // coalesced them since live range of vr1025 intersects the
01954               // def of vr1024. This happens because vr1025 is assigned the
01955               // value of the previous iteration of vr1024.
01956               return false;
01957             EliminatedLHSVals.push_back(LHSIt->valno);
01958 
01959             // We know this entire LHS live range is okay, so skip it now.
01960             if (++LHSIt == LHSEnd) break;
01961           }
01962         }
01963       }
01964       
01965       if (++RHSIt == RHSEnd) break;
01966     }
01967   }
01968   
01969   // If we got here, we know that the coalescing will be successful and that
01970   // the value numbers in EliminatedLHSVals will all be merged together.  Since
01971   // the most common case is that EliminatedLHSVals has a single number, we
01972   // optimize for it: if there is more than one value, we merge them all into
01973   // the lowest numbered one, then handle the interval as if we were merging
01974   // with one value number.
01975   VNInfo *LHSValNo = NULL;
01976   if (EliminatedLHSVals.size() > 1) {
01977     // Loop through all the equal value numbers merging them into the smallest
01978     // one.
01979     VNInfo *Smallest = EliminatedLHSVals[0];
01980     for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) {
01981       if (EliminatedLHSVals[i]->id < Smallest->id) {
01982         // Merge the current notion of the smallest into the smaller one.
01983         LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]);
01984         Smallest = EliminatedLHSVals[i];
01985       } else {
01986         // Merge into the smallest.
01987         LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest);
01988       }
01989     }
01990     LHSValNo = Smallest;
01991   } else if (EliminatedLHSVals.empty()) {
01992     if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) &&
01993         *tri_->getSuperRegisters(LHS.reg))
01994       // Imprecise sub-register information. Can't handle it.
01995       return false;
01996     llvm_unreachable("No copies from the RHS?");
01997   } else {
01998     LHSValNo = EliminatedLHSVals[0];
01999   }
02000   
02001   // Okay, now that there is a single LHS value number that we're merging the
02002   // RHS into, update the value number info for the LHS to indicate that the
02003   // value number is defined where the RHS value number was.
02004   const VNInfo *VNI = RHS.getValNumInfo(0);
02005   LHSValNo->def  = VNI->def;
02006   LHSValNo->setCopy(VNI->getCopy());
02007   
02008   // Okay, the final step is to loop over the RHS live intervals, adding them to
02009   // the LHS.
02010   if (VNI->hasPHIKill())
02011     LHSValNo->setHasPHIKill(true);
02012   LHS.addKills(LHSValNo, VNI->kills);
02013   LHS.MergeRangesInAsValue(RHS, LHSValNo);
02014 
02015   LHS.ComputeJoinedWeight(RHS);
02016 
02017   // Update regalloc hint if both are virtual registers.
02018   if (TargetRegisterInfo::isVirtualRegister(LHS.reg) && 
02019       TargetRegisterInfo::isVirtualRegister(RHS.reg)) {
02020     std::pair<unsigned, unsigned> RHSPref = mri_->getRegAllocationHint(RHS.reg);
02021     std::pair<unsigned, unsigned> LHSPref = mri_->getRegAllocationHint(LHS.reg);
02022     if (RHSPref != LHSPref)
02023       mri_->setRegAllocationHint(LHS.reg, RHSPref.first, RHSPref.second);
02024   }
02025 
02026   // Update the liveintervals of sub-registers.
02027   if (TargetRegisterInfo::isPhysicalRegister(LHS.reg))
02028     for (const unsigned *AS = tri_->getSubRegisters(LHS.reg); *AS; ++AS)
02029       li_->getOrCreateInterval(*AS).MergeInClobberRanges(LHS,
02030                                                     li_->getVNInfoAllocator());
02031 
02032   return true;
02033 }
02034 
02035 /// JoinIntervals - Attempt to join these two intervals.  On failure, this
02036 /// returns false.  Otherwise, if one of the intervals being joined is a
02037 /// physreg, this method always canonicalizes LHS to be it.  The output
02038 /// "RHS" will not have been modified, so we can use this information
02039 /// below to update aliases.
02040 bool
02041 SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS,
02042                                         bool &Swapped) {
02043   // Compute the final value assignment, assuming that the live ranges can be
02044   // coalesced.
02045   SmallVector<int, 16> LHSValNoAssignments;
02046   SmallVector<int, 16> RHSValNoAssignments;
02047   DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
02048   DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
02049   SmallVector<VNInfo*, 16> NewVNInfo;
02050 
02051   // If a live interval is a physical register, conservatively check if any
02052   // of its sub-registers is overlapping the live interval of the virtual
02053   // register. If so, do not coalesce.
02054   if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) &&
02055       *tri_->getSubRegisters(LHS.reg)) {
02056     // If it's coalescing a virtual register to a physical register, estimate
02057     // its live interval length. This is the *cost* of scanning an entire live
02058     // interval. If the cost is low, we'll do an exhaustive check instead.
02059 
02060     // If this is something like this:
02061     // BB1:
02062     // v1024 = op
02063     // ...
02064     // BB2:
02065     // ...
02066     // RAX   = v1024
02067     //
02068     // That is, the live interval of v1024 crosses a bb. Then we can't rely on
02069     // less conservative check. It's possible a sub-register is defined before
02070     // v1024 (or live in) and live out of BB1.
02071     if (RHS.containsOneValue() &&
02072         li_->intervalIsInOneMBB(RHS) &&
02073         li_->getApproximateInstructionCount(RHS) <= 10) {
02074       // Perform a more exhaustive check for some common cases.
02075       if (li_->conflictsWithPhysRegRef(RHS, LHS.reg, true, JoinedCopies))
02076         return false;
02077     } else {
02078       for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR)
02079         if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
02080           DOUT << "Interfere with sub-register ";
02081           DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
02082           return false;
02083         }
02084     }
02085   } else if (TargetRegisterInfo::isPhysicalRegister(RHS.reg) &&
02086              *tri_->getSubRegisters(RHS.reg)) {
02087     if (LHS.containsOneValue() &&
02088         li_->getApproximateInstructionCount(LHS) <= 10) {
02089       // Perform a more exhaustive check for some common cases.
02090       if (li_->conflictsWithPhysRegRef(LHS, RHS.reg, false, JoinedCopies))
02091         return false;
02092     } else {
02093       for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR)
02094         if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) {
02095           DOUT << "Interfere with sub-register ";
02096           DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
02097           return false;
02098         }
02099     }
02100   }
02101                           
02102   // Compute ultimate value numbers for the LHS and RHS values.
02103   if (RHS.containsOneValue()) {
02104     // Copies from a liveinterval with a single value are simple to handle and
02105     // very common, handle the special case here.  This is important, because
02106     // often RHS is small and LHS is large (e.g. a physreg).
02107     
02108     // Find out if the RHS is defined as a copy from some value in the LHS.
02109     int RHSVal0DefinedFromLHS = -1;
02110     int RHSValID = -1;
02111     VNInfo *RHSValNoInfo = NULL;
02112     VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0);
02113     unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0);
02114     if (RHSSrcReg == 0 || RHSSrcReg != LHS.reg) {
02115       // If RHS is not defined as a copy from the LHS, we can use simpler and
02116       // faster checks to see if the live ranges are coalescable.  This joiner
02117       // can't swap the LHS/RHS intervals though.
02118       if (!TargetRegisterInfo::isPhysicalRegister(RHS.reg)) {
02119         return SimpleJoin(LHS, RHS);
02120       } else {
02121         RHSValNoInfo = RHSValNoInfo0;
02122       }
02123     } else {
02124       // It was defined as a copy from the LHS, find out what value # it is.
02125       RHSValNoInfo = LHS.getLiveRangeContaining(RHSValNoInfo0->def-1)->valno;
02126       RHSValID = RHSValNoInfo->id;
02127       RHSVal0DefinedFromLHS = RHSValID;
02128     }
02129     
02130     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
02131     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
02132     NewVNInfo.resize(LHS.getNumValNums(), NULL);
02133     
02134     // Okay, *all* of the values in LHS that are defined as a copy from RHS
02135     // should now get updated.
02136     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
02137          i != e; ++i) {
02138       VNInfo *VNI = *i;
02139       unsigned VN = VNI->id;
02140       if (unsigned LHSSrcReg = li_->getVNInfoSourceReg(VNI)) {
02141         if (LHSSrcReg != RHS.reg) {
02142           // If this is not a copy from the RHS, its value number will be
02143           // unmodified by the coalescing.
02144           NewVNInfo[VN] = VNI;
02145           LHSValNoAssignments[VN] = VN;
02146         } else if (RHSValID == -1) {
02147           // Otherwise, it is a copy from the RHS, and we don't already have a
02148           // value# for it.  Keep the current value number, but remember it.
02149           LHSValNoAssignments[VN] = RHSValID = VN;
02150           NewVNInfo[VN] = RHSValNoInfo;
02151           LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0;
02152         } else {
02153           // Otherwise, use the specified value #.
02154           LHSValNoAssignments[VN] = RHSValID;
02155           if (VN == (unsigned)RHSValID) {  // Else this val# is dead.
02156             NewVNInfo[VN] = RHSValNoInfo;
02157             LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0;
02158           }
02159         }
02160       } else {
02161         NewVNInfo[VN] = VNI;
02162         LHSValNoAssignments[VN] = VN;
02163       }
02164     }
02165     
02166     assert(RHSValID != -1 && "Didn't find value #?");
02167     RHSValNoAssignments[0] = RHSValID;
02168     if (RHSVal0DefinedFromLHS != -1) {
02169       // This path doesn't go through ComputeUltimateVN so just set
02170       // it to anything.
02171       RHSValsDefinedFromLHS[RHSValNoInfo0] = (VNInfo*)1;
02172     }
02173   } else {
02174     // Loop over the value numbers of the LHS, seeing if any are defined from
02175     // the RHS.
02176     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
02177          i != e; ++i) {
02178       VNInfo *VNI = *i;
02179       if (VNI->isUnused() || VNI->getCopy() == 0)  // Src not defined by a copy?
02180         continue;
02181       
02182       // DstReg is known to be a register in the LHS interval.  If the src is
02183       // from the RHS interval, we can use its value #.
02184       if (li_->getVNInfoSourceReg(VNI) != RHS.reg)
02185         continue;
02186       
02187       // Figure out the value # from the RHS.
02188       LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno;
02189     }
02190     
02191     // Loop over the value numbers of the RHS, seeing if any are defined from
02192     // the LHS.
02193     for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
02194          i != e; ++i) {
02195       VNInfo *VNI = *i;
02196       if (VNI->isUnused() || VNI->getCopy() == 0)  // Src not defined by a copy?
02197         continue;
02198       
02199       // DstReg is known to be a register in the RHS interval.  If the src is
02200       // from the LHS interval, we can use its value #.
02201       if (li_->getVNInfoSourceReg(VNI) != LHS.reg)
02202         continue;
02203       
02204       // Figure out the value # from the LHS.
02205       RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno;
02206     }
02207     
02208     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
02209     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
02210     NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
02211     
02212     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
02213          i != e; ++i) {
02214       VNInfo *VNI = *i;
02215       unsigned VN = VNI->id;
02216       if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 
02217         continue;
02218       ComputeUltimateVN(VNI, NewVNInfo,
02219                         LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
02220                         LHSValNoAssignments, RHSValNoAssignments);
02221     }
02222     for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
02223          i != e; ++i) {
02224       VNInfo *VNI = *i;
02225       unsigned VN = VNI->id;
02226       if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused())
02227         continue;
02228       // If this value number isn't a copy from the LHS, it's a new number.
02229       if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
02230         NewVNInfo.push_back(VNI);
02231         RHSValNoAssignments[VN] = NewVNInfo.size()-1;
02232         continue;
02233       }
02234       
02235       ComputeUltimateVN(VNI, NewVNInfo,
02236                         RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
02237                         RHSValNoAssignments, LHSValNoAssignments);
02238     }
02239   }
02240   
02241   // Armed with the mappings of LHS/RHS values to ultimate values, walk the
02242   // interval lists to see if these intervals are coalescable.
02243   LiveInterval::const_iterator I = LHS.begin();
02244   LiveInterval::const_iterator IE = LHS.end();
02245   LiveInterval::const_iterator J = RHS.begin();
02246   LiveInterval::const_iterator JE = RHS.end();
02247   
02248   // Skip ahead until the first place of potential sharing.
02249   if (I->start < J->start) {
02250     I = std::upper_bound(I, IE, J->start);
02251     if (I != LHS.begin()) --I;
02252   } else if (J->start < I->start) {
02253     J = std::upper_bound(J, JE, I->start);
02254     if (J != RHS.begin()) --J;
02255   }
02256   
02257   while (1) {
02258     // Determine if these two live ranges overlap.
02259     bool Overlaps;
02260     if (I->start < J->start) {
02261       Overlaps = I->end > J->start;
02262     } else {
02263       Overlaps = J->end > I->start;
02264     }
02265 
02266     // If so, check value # info to determine if they are really different.
02267     if (Overlaps) {
02268       // If the live range overlap will map to the same value number in the
02269       // result liverange, we can still coalesce them.  If not, we can't.
02270       if (LHSValNoAssignments[I->valno->id] !=
02271           RHSValNoAssignments[J->valno->id])
02272         return false;
02273     }
02274     
02275     if (I->end < J->end) {
02276       ++I;
02277       if (I == IE) break;
02278     } else {
02279       ++J;
02280       if (J == JE) break;
02281     }
02282   }
02283 
02284   // Update kill info. Some live ranges are extended due to copy coalescing.
02285   for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(),
02286          E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
02287     VNInfo *VNI = I->first;
02288     unsigned LHSValID = LHSValNoAssignments[VNI->id];
02289     LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def);
02290     if (VNI->hasPHIKill())
02291       NewVNInfo[LHSValID]->setHasPHIKill(true);
02292     RHS.addKills(NewVNInfo[LHSValID], VNI->kills);
02293   }
02294 
02295   // Update kill info. Some live ranges are extended due to copy coalescing.
02296   for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(),
02297          E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
02298     VNInfo *VNI = I->first;
02299     unsigned RHSValID = RHSValNoAssignments[VNI->id];
02300     LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def);
02301     if (VNI->hasPHIKill())
02302       NewVNInfo[RHSValID]->setHasPHIKill(true);
02303     LHS.addKills(NewVNInfo[RHSValID], VNI->kills);
02304   }
02305 
02306   // If we get here, we know that we can coalesce the live ranges.  Ask the
02307   // intervals to coalesce themselves now.
02308   if ((RHS.ranges.size() > LHS.ranges.size() &&
02309       TargetRegisterInfo::isVirtualRegister(LHS.reg)) ||
02310       TargetRegisterInfo::isPhysicalRegister(RHS.reg)) {
02311     RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo,
02312              mri_);
02313     Swapped = true;
02314   } else {
02315     LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo,
02316              mri_);
02317     Swapped = false;
02318   }
02319   return true;
02320 }
02321 
02322 namespace {
02323   // DepthMBBCompare - Comparison predicate that sort first based on the loop
02324   // depth of the basic block (the unsigned), and then on the MBB number.
02325   struct DepthMBBCompare {
02326     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
02327     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
02328       if (LHS.first > RHS.first) return true;   // Deeper loops first
02329       return LHS.first == RHS.first &&
02330         LHS.second->getNumber() < RHS.second->getNumber();
02331     }
02332   };
02333 }
02334 
02335 /// getRepIntervalSize - Returns the size of the interval that represents the
02336 /// specified register.
02337 template<class SF>
02338 unsigned JoinPriorityQueue<SF>::getRepIntervalSize(unsigned Reg) {
02339   return Rc->getRepIntervalSize(Reg);
02340 }
02341 
02342 /// CopyRecSort::operator - Join priority queue sorting function.
02343 ///
02344 bool CopyRecSort::operator()(CopyRec left, CopyRec right) const {
02345   // Inner loops first.
02346   if (left.LoopDepth > right.LoopDepth)
02347     return false;
02348   else if (left.LoopDepth == right.LoopDepth)
02349     if (left.isBackEdge && !right.isBackEdge)
02350       return false;
02351   return true;
02352 }
02353 
02354 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
02355                                                std::vector<CopyRec> &TryAgain) {
02356   DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
02357 
02358   std::vector<CopyRec> VirtCopies;
02359   std::vector<CopyRec> PhysCopies;
02360   std::vector<CopyRec> ImpDefCopies;
02361   unsigned LoopDepth = loopInfo->getLoopDepth(MBB);
02362   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
02363        MII != E;) {
02364     MachineInstr *Inst = MII++;
02365     
02366     // If this isn't a copy nor a extract_subreg, we can't join intervals.
02367     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
02368     if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
02369       DstReg = Inst->getOperand(0).getReg();
02370       SrcReg = Inst->getOperand(1).getReg();
02371     } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
02372                Inst->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) {
02373       DstReg = Inst->getOperand(0).getReg();
02374       SrcReg = Inst->getOperand(2).getReg();
02375     } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
02376       continue;
02377 
02378     bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
02379     bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
02380     if (NewHeuristic) {
02381       JoinQueue->push(CopyRec(Inst, LoopDepth, isBackEdgeCopy(Inst, DstReg)));
02382     } else {
02383       if (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty())
02384         ImpDefCopies.push_back(CopyRec(Inst, 0, false));
02385       else if (SrcIsPhys || DstIsPhys)
02386         PhysCopies.push_back(CopyRec(Inst, 0, false));
02387       else
02388         VirtCopies.push_back(CopyRec(Inst, 0, false));
02389     }
02390   }
02391 
02392   if (NewHeuristic)
02393     return;
02394 
02395   // Try coalescing implicit copies first, followed by copies to / from
02396   // physical registers, then finally copies from virtual registers to
02397   // virtual registers.
02398   for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) {
02399     CopyRec &TheCopy = ImpDefCopies[i];
02400     bool Again = false;
02401     if (!JoinCopy(TheCopy, Again))
02402       if (Again)
02403         TryAgain.push_back(TheCopy);
02404   }
02405   for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) {
02406     CopyRec &TheCopy = PhysCopies[i];
02407     bool Again = false;
02408     if (!JoinCopy(TheCopy, Again))
02409       if (Again)
02410         TryAgain.push_back(TheCopy);
02411   }
02412   for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) {
02413     CopyRec &TheCopy = VirtCopies[i];
02414     bool Again = false;
02415     if (!JoinCopy(TheCopy, Again))
02416       if (Again)
02417         TryAgain.push_back(TheCopy);
02418   }
02419 }
02420 
02421 void SimpleRegisterCoalescing::joinIntervals() {
02422   DOUT << "********** JOINING INTERVALS ***********\n";
02423 
02424   if (NewHeuristic)
02425     JoinQueue = new JoinPriorityQueue<CopyRecSort>(this);
02426 
02427   std::vector<CopyRec> TryAgainList;
02428   if (loopInfo->empty()) {
02429     // If there are no loops in the function, join intervals in function order.
02430     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
02431          I != E; ++I)
02432       CopyCoalesceInMBB(I, TryAgainList);
02433   } else {
02434     // Otherwise, join intervals in inner loops before other intervals.
02435     // Unfortunately we can't just iterate over loop hierarchy here because
02436     // there may be more MBB's than BB's.  Collect MBB's for sorting.
02437 
02438     // Join intervals in the function prolog first. We want to join physical
02439     // registers with virtual registers before the intervals got too long.
02440     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
02441     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){
02442       MachineBasicBlock *MBB = I;
02443       MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I));
02444     }
02445 
02446     // Sort by loop depth.
02447     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
02448 
02449     // Finally, join intervals in loop nest order.
02450     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
02451       CopyCoalesceInMBB(MBBs[i].second, TryAgainList);
02452   }
02453   
02454   // Joining intervals can allow other intervals to be joined.  Iteratively join
02455   // until we make no progress.
02456   if (NewHeuristic) {
02457     SmallVector<CopyRec, 16> TryAgain;
02458     bool ProgressMade = true;
02459     while (ProgressMade) {
02460       ProgressMade = false;
02461       while (!JoinQueue->empty()) {
02462         CopyRec R = JoinQueue->pop();
02463         bool Again = false;
02464         bool Success = JoinCopy(R, Again);
02465         if (Success)
02466           ProgressMade = true;
02467         else if (Again)
02468           TryAgain.push_back(R);
02469       }
02470 
02471       if (ProgressMade) {
02472         while (!TryAgain.empty()) {
02473           JoinQueue->push(TryAgain.back());
02474           TryAgain.pop_back();
02475         }
02476       }
02477     }
02478   } else {
02479     bool ProgressMade = true;
02480     while (ProgressMade) {
02481       ProgressMade = false;
02482 
02483       for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
02484         CopyRec &TheCopy = TryAgainList[i];
02485         if (TheCopy.MI) {
02486           bool Again = false;
02487           bool Success = JoinCopy(TheCopy, Again);
02488           if (Success || !Again) {
02489             TheCopy.MI = 0;   // Mark this one as done.
02490             ProgressMade = true;
02491           }
02492         }
02493       }
02494     }
02495   }
02496 
02497   if (NewHeuristic)
02498     delete JoinQueue;  
02499 }
02500 
02501 /// Return true if the two specified registers belong to different register
02502 /// classes.  The registers may be either phys or virt regs.
02503 bool
02504 SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
02505                                                    unsigned RegB) const {
02506   // Get the register classes for the first reg.
02507   if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
02508     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
02509            "Shouldn't consider two physregs!");
02510     return !mri_->getRegClass(RegB)->contains(RegA);
02511   }
02512 
02513   // Compare against the regclass for the second reg.
02514   const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA);
02515   if (TargetRegisterInfo::isVirtualRegister(RegB)) {
02516     const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB);
02517     return RegClassA != RegClassB;
02518   }
02519   return !RegClassA->contains(RegB);
02520 }
02521 
02522 /// lastRegisterUse - Returns the last use of the specific register between
02523 /// cycles Start and End or NULL if there are no uses.
02524 MachineOperand *
02525 SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
02526                                           unsigned Reg, unsigned &UseIdx) const{
02527   UseIdx = 0;
02528   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
02529     MachineOperand *LastUse = NULL;
02530     for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg),
02531            E = mri_->use_end(); I != E; ++I) {
02532       MachineOperand &Use = I.getOperand();
02533       MachineInstr *UseMI = Use.getParent();
02534       unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
02535       if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
02536           SrcReg == DstReg)
02537         // Ignore identity copies.
02538         continue;
02539       unsigned Idx = li_->getInstructionIndex(UseMI);
02540       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
02541         LastUse = &Use;
02542         UseIdx = li_->getUseIndex(Idx);
02543       }
02544     }
02545     return LastUse;
02546   }
02547 
02548   int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM;
02549   int s = Start;
02550   while (e >= s) {
02551     // Skip deleted instructions
02552     MachineInstr *MI = li_->getInstructionFromIndex(e);
02553     while ((e - InstrSlots::NUM) >= s && !MI) {
02554       e -= InstrSlots::NUM;
02555       MI = li_->getInstructionFromIndex(e);
02556     }
02557     if (e < s || MI == NULL)
02558       return NULL;
02559 
02560     // Ignore identity copies.
02561     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
02562     if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
02563           SrcReg == DstReg))
02564       for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
02565         MachineOperand &Use = MI->getOperand(i);
02566         if (Use.isReg() && Use.isUse() && Use.getReg() &&
02567             tri_->regsOverlap(Use.getReg(), Reg)) {
02568           UseIdx = li_->getUseIndex(e);
02569           return &Use;
02570         }
02571       }
02572 
02573     e -= InstrSlots::NUM;
02574   }
02575 
02576   return NULL;
02577 }
02578 
02579 
02580 void SimpleRegisterCoalescing::printRegName(unsigned reg) const {
02581   if (TargetRegisterInfo::isPhysicalRegister(reg))
02582     cerr << tri_->getName(reg);
02583   else
02584     cerr << "%reg" << reg;
02585 }
02586 
02587 void SimpleRegisterCoalescing::releaseMemory() {
02588   JoinedCopies.clear();
02589   ReMatCopies.clear();
02590   ReMatDefs.clear();
02591 }
02592 
02593 static bool isZeroLengthInterval(LiveInterval *li) {
02594   for (LiveInterval::Ranges::const_iterator
02595          i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
02596     if (i->end - i->start > LiveInterval::InstrSlots::NUM)
02597       return false;
02598   return true;
02599 }
02600 
02601 
02602 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
02603   mf_ = &fn;
02604   mri_ = &fn.getRegInfo();
02605   tm_ = &fn.getTarget();
02606   tri_ = tm_->getRegisterInfo();
02607   tii_ = tm_->getInstrInfo();
02608   li_ = &getAnalysis<LiveIntervals>();
02609   loopInfo = &getAnalysis<MachineLoopInfo>();
02610 
02611   DEBUG(errs() << "********** SIMPLE REGISTER COALESCING **********\n"
02612         << "********** Function: "
02613         << ((Value*)mf_->getFunction())->getName() << '\n');
02614 
02615   allocatableRegs_ = tri_->getAllocatableSet(fn);
02616   for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(),
02617          E = tri_->regclass_end(); I != E; ++I)
02618     allocatableRCRegs_.insert(std::make_pair(*I,
02619                                              tri_->getAllocatableSet(fn, *I)));
02620 
02621   // Join (coalesce) intervals if requested.
02622   if (EnableJoining) {
02623     joinIntervals();
02624     DEBUG({
02625         DOUT << "********** INTERVALS POST JOINING **********\n";
02626         for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){
02627           I->second->print(DOUT, tri_);
02628           DOUT << "\n";
02629         }
02630       });
02631   }
02632 
02633   // Perform a final pass over the instructions and compute spill weights
02634   // and remove identity moves.
02635   SmallVector<unsigned, 4> DeadDefs;
02636   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
02637        mbbi != mbbe; ++mbbi) {
02638     MachineBasicBlock* mbb = mbbi;
02639     unsigned loopDepth = loopInfo->getLoopDepth(mbb);
02640 
02641     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
02642          mii != mie; ) {
02643       MachineInstr *MI = mii;
02644       unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
02645       if (JoinedCopies.count(MI)) {
02646         // Delete all coalesced copies.
02647         if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
02648           assert((MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
02649                   MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
02650                   MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) &&
02651                  "Unrecognized copy instruction");
02652           DstReg = MI->getOperand(0).getReg();
02653         }
02654         if (MI->registerDefIsDead(DstReg)) {
02655           LiveInterval &li = li_->getInterval(DstReg);
02656           if (!ShortenDeadCopySrcLiveRange(li, MI))
02657             ShortenDeadCopyLiveRange(li, MI);
02658         }
02659         li_->RemoveMachineInstrFromMaps(MI);
02660         mii = mbbi->erase(mii);
02661         ++numPeep;
02662         continue;
02663       }
02664 
02665       // Now check if this is a remat'ed def instruction which is now dead.
02666       if (ReMatDefs.count(MI)) {
02667         bool isDead = true;
02668         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
02669           const MachineOperand &MO = MI->getOperand(i);
02670           if (!MO.isReg())
02671             continue;
02672           unsigned Reg = MO.getReg();
02673           if (!Reg)
02674             continue;
02675           if (TargetRegisterInfo::isVirtualRegister(Reg))
02676             DeadDefs.push_back(Reg);
02677           if (MO.isDead())
02678             continue;
02679           if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
02680               !mri_->use_empty(Reg)) {
02681             isDead = false;
02682             break;
02683           }
02684         }
02685         if (isDead) {
02686           while (!DeadDefs.empty()) {
02687             unsigned DeadDef = DeadDefs.back();
02688             DeadDefs.pop_back();
02689             RemoveDeadDef(li_->getInterval(DeadDef), MI);
02690           }
02691           li_->RemoveMachineInstrFromMaps(mii);
02692           mii = mbbi->erase(mii);
02693           continue;
02694         } else
02695           DeadDefs.clear();
02696       }
02697 
02698       // If the move will be an identity move delete it
02699       bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
02700       if (isMove && SrcReg == DstReg) {
02701         if (li_->hasInterval(SrcReg)) {
02702           LiveInterval &RegInt = li_->getInterval(SrcReg);
02703           // If def of this move instruction is dead, remove its live range
02704           // from the dstination register's live interval.
02705           if (MI->registerDefIsDead(DstReg)) {
02706             if (!ShortenDeadCopySrcLiveRange(RegInt, MI))
02707               ShortenDeadCopyLiveRange(RegInt, MI);
02708           }
02709         }
02710         li_->RemoveMachineInstrFromMaps(MI);
02711         mii = mbbi->erase(mii);
02712         ++numPeep;
02713       } else {
02714         SmallSet<unsigned, 4> UniqueUses;
02715         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
02716           const MachineOperand &mop = MI->getOperand(i);
02717           if (mop.isReg() && mop.getReg() &&
02718               TargetRegisterInfo::isVirtualRegister(mop.getReg())) {
02719             unsigned reg = mop.getReg();
02720             // Multiple uses of reg by the same instruction. It should not
02721             // contribute to spill weight again.
02722             if (UniqueUses.count(reg) != 0)
02723               continue;
02724             LiveInterval &RegInt = li_->getInterval(reg);
02725             RegInt.weight +=
02726               li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth);
02727             UniqueUses.insert(reg);
02728           }
02729         }
02730         ++mii;
02731       }
02732     }
02733   }
02734 
02735   for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) {
02736     LiveInterval &LI = *I->second;
02737     if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
02738       // If the live interval length is essentially zero, i.e. in every live
02739       // range the use follows def immediately, it doesn't make sense to spill
02740       // it and hope it will be easier to allocate for this li.
02741       if (isZeroLengthInterval(&LI))
02742         LI.weight = HUGE_VALF;
02743       else {
02744         bool isLoad = false;
02745         SmallVector<LiveInterval*, 4> SpillIs;
02746         if (li_->isReMaterializable(LI, SpillIs, isLoad)) {
02747           // If all of the definitions of the interval are re-materializable,
02748           // it is a preferred candidate for spilling. If non of the defs are
02749           // loads, then it's potentially very cheap to re-materialize.
02750           // FIXME: this gets much more complicated once we support non-trivial
02751           // re-materialization.
02752           if (isLoad)
02753             LI.weight *= 0.9F;
02754           else
02755             LI.weight *= 0.5F;
02756         }
02757       }
02758 
02759       // Slightly prefer live interval that has been assigned a preferred reg.
02760       std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(LI.reg);
02761       if (Hint.first || Hint.second)
02762         LI.weight *= 1.01F;
02763 
02764       // Divide the weight of the interval by its size.  This encourages 
02765       // spilling of intervals that are large and have few uses, and
02766       // discourages spilling of small intervals with many uses.
02767       LI.weight /= li_->getApproximateInstructionCount(LI) * InstrSlots::NUM;
02768     }
02769   }
02770 
02771   DEBUG(dump());
02772   return true;
02773 }
02774 
02775 /// print - Implement the dump method.
02776 void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const {
02777    li_->print(O, m);
02778 }
02779 
02780 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() {
02781   return new SimpleRegisterCoalescing();
02782 }
02783 
02784 // Make sure that anything that uses RegisterCoalescer pulls in this file...
02785 DEFINING_FILE_FOR(SimpleRegisterCoalescing)