lib/CodeGen/SimpleRegisterCoalescing.cpp

   1 //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a simple register coalescing pass that attempts to
  11 // aggressively coalesce every register copy that it can.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "regcoalescing"
  16 #include "SimpleRegisterCoalescing.h"
  17 #include "VirtRegMap.h"
  18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  19 #include "llvm/Value.h"
  20 #include "llvm/CodeGen/LiveVariables.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/MachineInstr.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/Passes.h"
  26 #include "llvm/CodeGen/RegisterCoalescer.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/ADT/SmallSet.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include <algorithm>
  35 #include <cmath>
  36 using namespace llvm;
  37
  38 STATISTIC(numJoins    , "Number of interval joins performed");
  39 STATISTIC(numCommutes , "Number of instruction commuting performed");
  40 STATISTIC(numExtends  , "Number of copies extended");
  41 STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
  42 STATISTIC(numAborts   , "Number of times interval joining aborted");
  43
  44 char SimpleRegisterCoalescing::ID = 0;
  45 namespace {
  46   static cl::opt<bool>
  47   EnableJoining("join-liveintervals",
  48                 cl::desc("Coalesce copies (default=true)"),
  49                 cl::init(true));
  50
  51   static cl::opt<bool>
  52   NewHeuristic("new-coalescer-heuristic",
  53                 cl::desc("Use new coalescer heuristic"),
  54                 cl::init(false));
  55
  56   static cl::opt<bool>
  57   CommuteDef("coalescer-commute-instrs",
  58              cl::init(true), cl::Hidden);
  59
  60   static cl::opt<int>
  61   CommuteLimit("commute-limit",
  62                cl::init(-1), cl::Hidden);
  63
  64   RegisterPass<SimpleRegisterCoalescing>
  65   X("simple-register-coalescing", "Simple Register Coalescing");
  66
  67   // Declare that we implement the RegisterCoalescer interface
  68   RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
  69 }
  70
  71 const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo();
  72
  73 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
  74   AU.addPreserved<LiveIntervals>();
  75   AU.addPreserved<MachineLoopInfo>();
  76   AU.addPreservedID(MachineDominatorsID);
  77   AU.addPreservedID(PHIEliminationID);
  78   AU.addPreservedID(TwoAddressInstructionPassID);
  79   AU.addRequired<LiveVariables>();
  80   AU.addRequired<LiveIntervals>();
  81   AU.addRequired<MachineLoopInfo>();
  82   MachineFunctionPass::getAnalysisUsage(AU);
  83 }
  84
  85 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
  86 /// being the source and IntB being the dest, thus this defines a value number
  87 /// in IntB.  If the source value number (in IntA) is defined by a copy from B,
  88 /// see if we can merge these two pieces of B into a single value number,
  89 /// eliminating a copy.  For example:
  90 ///
  91 ///  A3 = B0
  92 ///    ...
  93 ///  B1 = A3      <- this copy
  94 ///
  95 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
  96 /// value number to be replaced with B0 (which simplifies the B liveinterval).
  97 ///
  98 /// This returns true if an interval was modified.
  99 ///
 100 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
 101                                                     LiveInterval &IntB,
 102                                                     MachineInstr *CopyMI) {
 103   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
 104
 105   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
 106   // the example above.
 107   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 108   VNInfo *BValNo = BLR->valno;
 109
 110   // Get the location that B is defined at.  Two options: either this value has
 111   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 112   // can't process it.
 113   if (!BValNo->copy) return false;
 114   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 115
 116   // AValNo is the value number in A that defines the copy, A3 in the example.
 117   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
 118   VNInfo *AValNo = ALR->valno;
 119
 120   // If AValNo is defined as a copy from IntB, we can potentially process this.
 121   // Get the instruction that defines this value number.
 122   unsigned SrcReg = li_->getVNInfoSourceReg(AValNo);
 123   if (!SrcReg) return false;  // Not defined by a copy.
 124
 125   // If the value number is not defined by a copy instruction, ignore it.
 126
 127   // If the source register comes from an interval other than IntB, we can't
 128   // handle this.
 129   if (SrcReg != IntB.reg) return false;
 130
 131   // Get the LiveRange in IntB that this value number starts with.
 132   LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1);
 133
 134   // Make sure that the end of the live range is inside the same block as
 135   // CopyMI.
 136   MachineInstr *ValLREndInst = li_->getInstructionFromIndex(ValLR->end-1);
 137   if (!ValLREndInst ||
 138       ValLREndInst->getParent() != CopyMI->getParent()) return false;
 139
 140   // Okay, we now know that ValLR ends in the same block that the CopyMI
 141   // live-range starts.  If there are no intervening live ranges between them in
 142   // IntB, we can merge them.
 143   if (ValLR+1 != BLR) return false;
 144
 145   // If a live interval is a physical register, conservatively check if any
 146   // of its sub-registers is overlapping the live interval of the virtual
 147   // register. If so, do not coalesce.
 148   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) &&
 149       *tri_->getSubRegisters(IntB.reg)) {
 150     for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
 151       if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) {
 152         DOUT << "Interfere with sub-register ";
 153         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
 154         return false;
 155       }
 156   }
 157
 158   DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
 159
 160   unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
 161   // We are about to delete CopyMI, so need to remove it as the 'instruction
 162   // that defines this value #'. Update the the valnum with the new defining
 163   // instruction #.
 164   BValNo->def  = FillerStart;
 165   BValNo->copy = NULL;
 166
 167   // Okay, we can merge them.  We need to insert a new liverange:
 168   // [ValLR.end, BLR.begin) of either value number, then we merge the
 169   // two value numbers.
 170   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
 171
 172   // If the IntB live range is assigned to a physical register, and if that
 173   // physreg has aliases,
 174   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
 175     // Update the liveintervals of sub-registers.
 176     for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) {
 177       LiveInterval &AliasLI = li_->getInterval(*AS);
 178       AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
 179               AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator())));
 180     }
 181   }
 182
 183   // Okay, merge "B1" into the same value number as "B0".
 184   if (BValNo != ValLR->valno)
 185     IntB.MergeValueNumberInto(BValNo, ValLR->valno);
 186   DOUT << "   result = "; IntB.print(DOUT, tri_);
 187   DOUT << "\n";
 188
 189   // If the source instruction was killing the source register before the
 190   // merge, unset the isKill marker given the live range has been extended.
 191   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
 192   if (UIdx != -1)
 193     ValLREndInst->getOperand(UIdx).setIsKill(false);
 194
 195   ++numExtends;
 196   return true;
 197 }
 198
 199 /// HasOtherReachingDefs - Return true if there are definitions of IntB
 200 /// other than BValNo val# that can reach uses of AValno val# of IntA.
 201 bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA,
 202                                                     LiveInterval &IntB,
 203                                                     VNInfo *AValNo,
 204                                                     VNInfo *BValNo) {
 205   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 206        AI != AE; ++AI) {
 207     if (AI->valno != AValNo) continue;
 208     LiveInterval::Ranges::iterator BI =
 209       std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
 210     if (BI != IntB.ranges.begin())
 211       --BI;
 212     for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
 213       if (BI->valno == BValNo)
 214         continue;
 215       if (BI->start <= AI->start && BI->end > AI->start)
 216         return true;
 217       if (BI->start > AI->start && BI->start < AI->end)
 218         return true;
 219     }
 220   }
 221   return false;
 222 }
 223
 224 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA
 225 /// being the source and IntB being the dest, thus this defines a value number
 226 /// in IntB.  If the source value number (in IntA) is defined by a commutable
 227 /// instruction and its other operand is coalesced to the copy dest register,
 228 /// see if we can transform the copy into a noop by commuting the definition. For
 229 /// example,
 230 ///
 231 ///  A3 = op A2 B0<kill>
 232 ///    ...
 233 ///  B1 = A3      <- this copy
 234 ///    ...
 235 ///     = op A3   <- more uses
 236 ///
 237 /// ==>
 238 ///
 239 ///  B2 = op B0 A2<kill>
 240 ///    ...
 241 ///  B1 = B2      <- now an identify copy
 242 ///    ...
 243 ///     = op B2   <- more uses
 244 ///
 245 /// This returns true if an interval was modified.
 246 ///
 247 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
 248                                                         LiveInterval &IntB,
 249                                                         MachineInstr *CopyMI) {
 250   if (!CommuteDef) return false;
 251
 252   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
 253
 254   // FIXME: For now, only eliminate the copy by commuting its def when the
 255   // source register is a virtual register. We want to guard against cases
 256   // where the copy is a back edge copy and commuting the def lengthen the
 257   // live interval of the source register to the entire loop.
 258   if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
 259     return false;
 260
 261   // BValNo is a value number in B that is defined by a copy from A. 'B3' in
 262   // the example above.
 263   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 264   VNInfo *BValNo = BLR->valno;
 265
 266   // Get the location that B is defined at.  Two options: either this value has
 267   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 268   // can't process it.
 269   if (!BValNo->copy) return false;
 270   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 271
 272   // AValNo is the value number in A that defines the copy, A3 in the example.
 273   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
 274   VNInfo *AValNo = ALR->valno;
 275   // If other defs can reach uses of this def, then it's not safe to perform
 276   // the optimization.
 277   if (AValNo->def == ~0U || AValNo->def == ~1U || AValNo->hasPHIKill)
 278     return false;
 279   MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def);
 280   const TargetInstrDesc &TID = DefMI->getDesc();
 281   unsigned NewDstIdx;
 282   if (!TID.isCommutable() ||
 283       !tii_->CommuteChangesDestination(DefMI, NewDstIdx))
 284     return false;
 285
 286   MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
 287   unsigned NewReg = NewDstMO.getReg();
 288   if (NewReg != IntB.reg || !NewDstMO.isKill())
 289     return false;
 290
 291   // Make sure there are no other definitions of IntB that would reach the
 292   // uses which the new definition can reach.
 293   if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
 294     return false;
 295
 296   if (CommuteLimit >= 0 && numCommutes >= (unsigned)CommuteLimit)
 297     return false;
 298
 299   // At this point we have decided that it is legal to do this
 300   // transformation.  Start by commuting the instruction.
 301   MachineBasicBlock *MBB = DefMI->getParent();
 302   MachineInstr *NewMI = tii_->commuteInstruction(DefMI);
 303   if (!NewMI)
 304     return false;
 305   if (NewMI != DefMI) {
 306     li_->ReplaceMachineInstrInMaps(DefMI, NewMI);
 307     MBB->insert(DefMI, NewMI);
 308     MBB->erase(DefMI);
 309   }
 310   unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
 311   NewMI->getOperand(OpIdx).setIsKill();
 312
 313   bool BHasPHIKill = BValNo->hasPHIKill;
 314   SmallVector<VNInfo*, 4> BDeadValNos;
 315   SmallVector<unsigned, 4> BKills;
 316   std::map<unsigned, unsigned> BExtend;
 317
 318   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
 319   // A = or A, B
 320   // ...
 321   // B = A
 322   // ...
 323   // C = A<kill>
 324   // ...
 325   //   = B
 326   //
 327   // then do not add kills of A to the newly created B interval.
 328   bool Extended = BLR->end > ALR->end && ALR->end != ALR->start;
 329   if (Extended)
 330     BExtend[ALR->end] = BLR->end;
 331
 332   // Update uses of IntA of the specific Val# with IntB.
 333   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
 334          UE = mri_->use_end(); UI != UE;) {
 335     MachineOperand &UseMO = UI.getOperand();
 336     MachineInstr *UseMI = &*UI;
 337     ++UI;
 338     if (JoinedCopies.count(UseMI))
 339       continue;
 340     unsigned UseIdx = li_->getInstructionIndex(UseMI);
 341     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 342     if (ULR->valno != AValNo)
 343       continue;
 344     UseMO.setReg(NewReg);
 345     if (UseMI == CopyMI)
 346       continue;
 347     if (UseMO.isKill()) {
 348       if (Extended)
 349         UseMO.setIsKill(false);
 350       else
 351         BKills.push_back(li_->getUseIndex(UseIdx)+1);
 352     }
 353     unsigned SrcReg, DstReg;
 354     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg))
 355       continue;
 356     if (DstReg == IntB.reg) {
 357       // This copy will become a noop. If it's defining a new val#,
 358       // remove that val# as well. However this live range is being
 359       // extended to the end of the existing live range defined by the copy.
 360       unsigned DefIdx = li_->getDefIndex(UseIdx);
 361       LiveInterval::iterator DLR = IntB.FindLiveRangeContaining(DefIdx);
 362       BHasPHIKill |= DLR->valno->hasPHIKill;
 363       assert(DLR->valno->def == DefIdx);
 364       BDeadValNos.push_back(DLR->valno);
 365       BExtend[DLR->start] = DLR->end;
 366       JoinedCopies.insert(UseMI);
 367       // If this is a kill but it's going to be removed, the last use
 368       // of the same val# is the new kill.
 369       if (UseMO.isKill())
 370         BKills.pop_back();
 371     }
 372   }
 373
 374   // We need to insert a new liverange: [ALR.start, LastUse). It may be we can
 375   // simply extend BLR if CopyMI doesn't end the range.
 376   DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
 377
 378   IntB.removeValNo(BValNo);
 379   for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i)
 380     IntB.removeValNo(BDeadValNos[i]);
 381   VNInfo *ValNo = IntB.getNextValue(ALR->start, 0, li_->getVNInfoAllocator());
 382   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 383        AI != AE; ++AI) {
 384     if (AI->valno != AValNo) continue;
 385     unsigned End = AI->end;
 386     std::map<unsigned, unsigned>::iterator EI = BExtend.find(End);
 387     if (EI != BExtend.end())
 388       End = EI->second;
 389     IntB.addRange(LiveRange(AI->start, End, ValNo));
 390   }
 391   IntB.addKills(ValNo, BKills);
 392   ValNo->hasPHIKill = BHasPHIKill;
 393
 394   DOUT << "   result = "; IntB.print(DOUT, tri_);
 395   DOUT << "\n";
 396
 397   DOUT << "\nShortening: "; IntA.print(DOUT, tri_);
 398   IntA.removeValNo(AValNo);
 399   DOUT << "   result = "; IntA.print(DOUT, tri_);
 400   DOUT << "\n";
 401
 402   ++numCommutes;
 403   return true;
 404 }
 405
 406 /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy.
 407 ///
 408 bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI,
 409                                               unsigned DstReg) {
 410   MachineBasicBlock *MBB = CopyMI->getParent();
 411   const MachineLoop *L = loopInfo->getLoopFor(MBB);
 412   if (!L)
 413     return false;
 414   if (MBB != L->getLoopLatch())
 415     return false;
 416
 417   LiveInterval &LI = li_->getInterval(DstReg);
 418   unsigned DefIdx = li_->getInstructionIndex(CopyMI);
 419   LiveInterval::const_iterator DstLR =
 420     LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx));
 421   if (DstLR == LI.end())
 422     return false;
 423   unsigned KillIdx = li_->getInstructionIndex(&MBB->back()) + InstrSlots::NUM;
 424   if (DstLR->valno->kills.size() == 1 &&
 425       DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill)
 426     return true;
 427   return false;
 428 }
 429
 430 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 431 /// update the subregister number if it is not zero. If DstReg is a
 432 /// physical register and the existing subregister number of the def / use
 433 /// being updated is not zero, make sure to set it to the correct physical
 434 /// subregister.
 435 void
 436 SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
 437                                             unsigned SubIdx) {
 438   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 439   if (DstIsPhys && SubIdx) {
 440     // Figure out the real physical register we are updating with.
 441     DstReg = tri_->getSubReg(DstReg, SubIdx);
 442     SubIdx = 0;
 443   }
 444
 445   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
 446          E = mri_->reg_end(); I != E; ) {
 447     MachineOperand &O = I.getOperand();
 448     ++I;
 449     if (DstIsPhys) {
 450       unsigned UseSubIdx = O.getSubReg();
 451       unsigned UseDstReg = DstReg;
 452       if (UseSubIdx)
 453         UseDstReg = tri_->getSubReg(DstReg, UseSubIdx);
 454       O.setReg(UseDstReg);
 455       O.setSubReg(0);
 456     } else {
 457       unsigned OldSubIdx = O.getSubReg();
 458       // Sub-register indexes goes from small to large. e.g.
 459       // RAX: 0 -> AL, 1 -> AH, 2 -> AX, 3 -> EAX
 460       // EAX: 0 -> AL, 1 -> AH, 2 -> AX
 461       // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose
 462       // sub-register 2 is also AX.
 463       if (SubIdx && OldSubIdx && SubIdx != OldSubIdx)
 464         assert(OldSubIdx < SubIdx && "Conflicting sub-register index!");
 465       else if (SubIdx)
 466         O.setSubReg(SubIdx);
 467       O.setReg(DstReg);
 468     }
 469   }
 470 }
 471
 472 /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate
 473 /// due to live range lengthening as the result of coalescing.
 474 void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg,
 475                                                       LiveInterval &LI) {
 476   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
 477          UE = mri_->use_end(); UI != UE; ++UI) {
 478     MachineOperand &UseMO = UI.getOperand();
 479     if (UseMO.isKill()) {
 480       MachineInstr *UseMI = UseMO.getParent();
 481       unsigned SReg, DReg;
 482       if (!tii_->isMoveInstr(*UseMI, SReg, DReg))
 483         continue;
 484       unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
 485       if (JoinedCopies.count(UseMI))
 486         continue;
 487       LiveInterval::const_iterator UI = LI.FindLiveRangeContaining(UseIdx);
 488       assert(UI != LI.end());
 489       if (!LI.isKill(UI->valno, UseIdx+1))
 490         UseMO.setIsKill(false);
 491     }
 492   }
 493 }
 494
 495 /// ShortenDeadCopyLiveRange - Shorten a live range as it's artificially
 496 /// extended by a dead copy. Mark the last use (if any) of the val# as kill
 497 /// as ends the live range there. If there isn't another use, then this
 498 /// live range is dead.
 499 void SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
 500                                                         MachineInstr *CopyMI) {
 501   unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
 502   LiveInterval::iterator MLR =
 503     li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
 504   unsigned RemoveStart = MLR->start;
 505   unsigned RemoveEnd = MLR->end;
 506   unsigned LastUseIdx;
 507   MachineOperand *LastUse = lastRegisterUse(RemoveStart, CopyIdx, li.reg,
 508                                             LastUseIdx);
 509   if (LastUse) {
 510     // Shorten the liveinterval to the end of last use.
 511     LastUse->setIsKill();
 512     RemoveStart = li_->getDefIndex(LastUseIdx);
 513   }
 514   li.removeRange(RemoveStart, RemoveEnd, true);
 515   if (li.empty())
 516     li_->removeInterval(li.reg);
 517 }
 518
 519 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 520 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 521 /// if the copy was successfully coalesced away. If it is not currently
 522 /// possible to coalesce this interval, but it may be possible if other
 523 /// things get coalesced, then it returns true by reference in 'Again'.
 524 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
 525   MachineInstr *CopyMI = TheCopy.MI;
 526
 527   Again = false;
 528   if (JoinedCopies.count(CopyMI))
 529     return false; // Already done.
 530
 531   DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI;
 532
 533   unsigned SrcReg;
 534   unsigned DstReg;
 535   bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG;
 536   unsigned SubIdx = 0;
 537   if (isExtSubReg) {
 538     DstReg = CopyMI->getOperand(0).getReg();
 539     SrcReg = CopyMI->getOperand(1).getReg();
 540   } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
 541     assert(0 && "Unrecognized copy instruction!");
 542     return false;
 543   }
 544
 545   // If they are already joined we continue.
 546   if (SrcReg == DstReg) {
 547     DOUT << "\tCopy already coalesced.\n";
 548     return false;  // Not coalescable.
 549   }
 550
 551   bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
 552   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 553
 554   // If they are both physical registers, we cannot join them.
 555   if (SrcIsPhys && DstIsPhys) {
 556     DOUT << "\tCan not coalesce physregs.\n";
 557     return false;  // Not coalescable.
 558   }
 559
 560   // We only join virtual registers with allocatable physical registers.
 561   if (SrcIsPhys && !allocatableRegs_[SrcReg]) {
 562     DOUT << "\tSrc reg is unallocatable physreg.\n";
 563     return false;  // Not coalescable.
 564   }
 565   if (DstIsPhys && !allocatableRegs_[DstReg]) {
 566     DOUT << "\tDst reg is unallocatable physreg.\n";
 567     return false;  // Not coalescable.
 568   }
 569
 570   unsigned RealDstReg = 0;
 571   if (isExtSubReg) {
 572     SubIdx = CopyMI->getOperand(2).getImm();
 573     if (SrcIsPhys) {
 574       // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be
 575       // coalesced with AX.
 576       SrcReg = tri_->getSubReg(SrcReg, SubIdx);
 577       SubIdx = 0;
 578     } else if (DstIsPhys) {
 579       // If this is a extract_subreg where dst is a physical register, e.g.
 580       // cl = EXTRACT_SUBREG reg1024, 1
 581       // then create and update the actual physical register allocated to RHS.
 582       const TargetRegisterClass *RC = mri_->getRegClass(SrcReg);
 583       for (const unsigned *SRs = tri_->getSuperRegisters(DstReg);
 584            unsigned SR = *SRs; ++SRs) {
 585         if (DstReg == tri_->getSubReg(SR, SubIdx) &&
 586             RC->contains(SR)) {
 587           RealDstReg = SR;
 588           break;
 589         }
 590       }
 591       assert(RealDstReg && "Invalid extra_subreg instruction!");
 592
 593       // For this type of EXTRACT_SUBREG, conservatively
 594       // check if the live interval of the source register interfere with the
 595       // actual super physical register we are trying to coalesce with.
 596       LiveInterval &RHS = li_->getInterval(SrcReg);
 597       if (li_->hasInterval(RealDstReg) &&
 598           RHS.overlaps(li_->getInterval(RealDstReg))) {
 599         DOUT << "Interfere with register ";
 600         DEBUG(li_->getInterval(RealDstReg).print(DOUT, tri_));
 601         return false; // Not coalescable
 602       }
 603       for (const unsigned* SR = tri_->getSubRegisters(RealDstReg); *SR; ++SR)
 604         if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
 605           DOUT << "Interfere with sub-register ";
 606           DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
 607           return false; // Not coalescable
 608         }
 609       SubIdx = 0;
 610     } else {
 611       unsigned SrcSize= li_->getInterval(SrcReg).getSize() / InstrSlots::NUM;
 612       unsigned DstSize= li_->getInterval(DstReg).getSize() / InstrSlots::NUM;
 613       const TargetRegisterClass *RC = mri_->getRegClass(DstReg);
 614       unsigned Threshold = allocatableRCRegs_[RC].count();
 615       // Be conservative. If both sides are virtual registers, do not coalesce
 616       // if this will cause a high use density interval to target a smaller set
 617       // of registers.
 618       if (DstSize > Threshold || SrcSize > Threshold) {
 619         LiveVariables::VarInfo &svi = lv_->getVarInfo(SrcReg);
 620         LiveVariables::VarInfo &dvi = lv_->getVarInfo(DstReg);
 621         if ((float)dvi.NumUses / DstSize < (float)svi.NumUses / SrcSize) {
 622           Again = true;  // May be possible to coalesce later.
 623           return false;
 624         }
 625       }
 626     }
 627   } else if (differingRegisterClasses(SrcReg, DstReg)) {
 628     // FIXME: What if the resul of a EXTRACT_SUBREG is then coalesced
 629     // with another? If it's the resulting destination register, then
 630     // the subidx must be propagated to uses (but only those defined
 631     // by the EXTRACT_SUBREG). If it's being coalesced into another
 632     // register, it should be safe because register is assumed to have
 633     // the register class of the super-register.
 634
 635     // If they are not of the same register class, we cannot join them.
 636     DOUT << "\tSrc/Dest are different register classes.\n";
 637     // Allow the coalescer to try again in case either side gets coalesced to
 638     // a physical register that's compatible with the other side. e.g.
 639     // r1024 = MOV32to32_ r1025
 640     // but later r1024 is assigned EAX then r1025 may be coalesced with EAX.
 641     Again = true;  // May be possible to coalesce later.
 642     return false;
 643   }
 644
 645   LiveInterval &SrcInt = li_->getInterval(SrcReg);
 646   LiveInterval &DstInt = li_->getInterval(DstReg);
 647   assert(SrcInt.reg == SrcReg && DstInt.reg == DstReg &&
 648          "Register mapping is horribly broken!");
 649
 650   DOUT << "\t\tInspecting "; SrcInt.print(DOUT, tri_);
 651   DOUT << " and "; DstInt.print(DOUT, tri_);
 652   DOUT << ": ";
 653
 654   // Check if it is necessary to propagate "isDead" property before intervals
 655   // are joined.
 656   MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false);
 657   bool isDead = mopd->isDead();
 658   bool isShorten = false;
 659   unsigned SrcStart = 0, RemoveStart = 0;
 660   unsigned SrcEnd = 0, RemoveEnd = 0;
 661   if (isDead) {
 662     unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
 663     LiveInterval::iterator SrcLR =
 664       SrcInt.FindLiveRangeContaining(li_->getUseIndex(CopyIdx));
 665     RemoveStart = SrcStart = SrcLR->start;
 666     RemoveEnd   = SrcEnd   = SrcLR->end;
 667     if (SrcEnd > li_->getDefIndex(CopyIdx)) {
 668       // If there are other uses of SrcReg beyond the copy, there is nothing to do.
 669       isDead = false;
 670     } else {
 671       unsigned LastUseIdx;
 672       MachineOperand *LastUse =
 673         lastRegisterUse(SrcStart, CopyIdx, SrcReg, LastUseIdx);
 674       if (LastUse) {
 675         // There are uses before the copy, just shorten the live range to the end
 676         // of last use.
 677         LastUse->setIsKill();
 678         isDead = false;
 679         isShorten = true;
 680         RemoveStart = li_->getDefIndex(LastUseIdx);
 681       } else {
 682         // This live range is truly dead. Remove it.
 683         MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart);
 684         if (SrcMI && SrcMI->modifiesRegister(SrcReg, tri_))
 685           // A dead def should have a single cycle interval.
 686           ++RemoveStart;
 687       }
 688     }
 689   }
 690
 691   // We need to be careful about coalescing a source physical register with a
 692   // virtual register. Once the coalescing is done, it cannot be broken and
 693   // these are not spillable! If the destination interval uses are far away,
 694   // think twice about coalescing them!
 695   if (!mopd->isDead() && (SrcIsPhys || DstIsPhys) && !isExtSubReg) {
 696     LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
 697     unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg;
 698     unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg;
 699     const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg);
 700     unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
 701     if (TheCopy.isBackEdge)
 702       Threshold *= 2; // Favors back edge copies.
 703
 704     // If the virtual register live interval is long but it has low use desity,
 705     // do not join them, instead mark the physical register as its allocation
 706     // preference.
 707     unsigned Length = JoinVInt.getSize() / InstrSlots::NUM;
 708     LiveVariables::VarInfo &vi = lv_->getVarInfo(JoinVReg);
 709     if (Length > Threshold &&
 710         (((float)vi.NumUses / Length) < (1.0 / Threshold))) {
 711       JoinVInt.preference = JoinPReg;
 712       ++numAborts;
 713       DOUT << "\tMay tie down a physical register, abort!\n";
 714       Again = true;  // May be possible to coalesce later.
 715       return false;
 716     }
 717   }
 718
 719   // Okay, attempt to join these two intervals.  On failure, this returns false.
 720   // Otherwise, if one of the intervals being joined is a physreg, this method
 721   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
 722   // been modified, so we can use this information below to update aliases.
 723   bool Swapped = false;
 724   if (JoinIntervals(DstInt, SrcInt, Swapped)) {
 725     if (isDead) {
 726       // Result of the copy is dead. Propagate this property.
 727       if (SrcStart == 0) {
 728         assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
 729                "Live-in must be a physical register!");
 730         // Live-in to the function but dead. Remove it from entry live-in set.
 731         // JoinIntervals may end up swapping the two intervals.
 732         mf_->begin()->removeLiveIn(SrcReg);
 733       } else {
 734         MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart);
 735         if (SrcMI) {
 736           int DeadIdx = SrcMI->findRegisterDefOperandIdx(SrcReg, false, tri_);
 737           if (DeadIdx != -1)
 738             SrcMI->getOperand(DeadIdx).setIsDead();
 739         }
 740       }
 741     }
 742
 743     if (isShorten || isDead) {
 744       // Shorten the destination live interval.
 745       if (Swapped)
 746         SrcInt.removeRange(RemoveStart, RemoveEnd, true);
 747     }
 748   } else {
 749     // Coalescing failed.
 750
 751     // If we can eliminate the copy without merging the live ranges, do so now.
 752     if (!isExtSubReg &&
 753         (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) ||
 754          RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) {
 755       JoinedCopies.insert(CopyMI);
 756       return true;
 757     }
 758
 759     // Otherwise, we are unable to join the intervals.
 760     DOUT << "Interference!\n";
 761     Again = true;  // May be possible to coalesce later.
 762     return false;
 763   }
 764
 765   LiveInterval *ResSrcInt = &SrcInt;
 766   LiveInterval *ResDstInt = &DstInt;
 767   if (Swapped) {
 768     std::swap(SrcReg, DstReg);
 769     std::swap(ResSrcInt, ResDstInt);
 770   }
 771   assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 772          "LiveInterval::join didn't work right!");
 773
 774   // If we're about to merge live ranges into a physical register live range,
 775   // we have to update any aliased register's live ranges to indicate that they
 776   // have clobbered values for this range.
 777   if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
 778     // If this is a extract_subreg where dst is a physical register, e.g.
 779     // cl = EXTRACT_SUBREG reg1024, 1
 780     // then create and update the actual physical register allocated to RHS.
 781     if (RealDstReg) {
 782       LiveInterval &RealDstInt = li_->getOrCreateInterval(RealDstReg);
 783       SmallSet<const VNInfo*, 4> CopiedValNos;
 784       for (LiveInterval::Ranges::const_iterator I = ResSrcInt->ranges.begin(),
 785              E = ResSrcInt->ranges.end(); I != E; ++I) {
 786         LiveInterval::const_iterator DstLR =
 787           ResDstInt->FindLiveRangeContaining(I->start);
 788         assert(DstLR != ResDstInt->end() && "Invalid joined interval!");
 789         const VNInfo *DstValNo = DstLR->valno;
 790         if (CopiedValNos.insert(DstValNo)) {
 791           VNInfo *ValNo = RealDstInt.getNextValue(DstValNo->def, DstValNo->copy,
 792                                                   li_->getVNInfoAllocator());
 793           ValNo->hasPHIKill = DstValNo->hasPHIKill;
 794           RealDstInt.addKills(ValNo, DstValNo->kills);
 795           RealDstInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo);
 796         }
 797       }
 798       DstReg = RealDstReg;
 799     }
 800
 801     // Update the liveintervals of sub-registers.
 802     for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
 803       li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
 804                                                  li_->getVNInfoAllocator());
 805   } else {
 806     // Merge use info if the destination is a virtual register.
 807     LiveVariables::VarInfo& dVI = lv_->getVarInfo(DstReg);
 808     LiveVariables::VarInfo& sVI = lv_->getVarInfo(SrcReg);
 809     dVI.NumUses += sVI.NumUses;
 810   }
 811
 812   // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the
 813   // larger super-register.
 814   if (isExtSubReg && !SrcIsPhys && !DstIsPhys) {
 815     if (!Swapped) {
 816       ResSrcInt->Copy(*ResDstInt, li_->getVNInfoAllocator());
 817       std::swap(SrcReg, DstReg);
 818       std::swap(ResSrcInt, ResDstInt);
 819     }
 820   }
 821
 822   if (NewHeuristic) {
 823     // Add all copies that define val# in the source interval into the queue.
 824     for (LiveInterval::const_vni_iterator i = ResSrcInt->vni_begin(),
 825            e = ResSrcInt->vni_end(); i != e; ++i) {
 826       const VNInfo *vni = *i;
 827       if (!vni->def || vni->def == ~1U || vni->def == ~0U)
 828         continue;
 829       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
 830       unsigned NewSrcReg, NewDstReg;
 831       if (CopyMI &&
 832           JoinedCopies.count(CopyMI) == 0 &&
 833           tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg)) {
 834         unsigned LoopDepth = loopInfo->getLoopDepth(CopyMI->getParent());
 835         JoinQueue->push(CopyRec(CopyMI, LoopDepth,
 836                                 isBackEdgeCopy(CopyMI, DstReg)));
 837       }
 838     }
 839   }
 840
 841   DOUT << "\n\t\tJoined.  Result = "; ResDstInt->print(DOUT, tri_);
 842   DOUT << "\n";
 843
 844   // Remember to delete the copy instruction.
 845   JoinedCopies.insert(CopyMI);
 846
 847   // Some live range has been lengthened due to colaescing, eliminate the
 848   // unnecessary kills.
 849   RemoveUnnecessaryKills(SrcReg, *ResDstInt);
 850   if (TargetRegisterInfo::isVirtualRegister(DstReg))
 851     RemoveUnnecessaryKills(DstReg, *ResDstInt);
 852
 853   // SrcReg is guarateed to be the register whose live interval that is
 854   // being merged.
 855   li_->removeInterval(SrcReg);
 856   UpdateRegDefsUses(SrcReg, DstReg, SubIdx);
 857
 858   ++numJoins;
 859   return true;
 860 }
 861
 862 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
 863 /// compute what the resultant value numbers for each value in the input two
 864 /// ranges will be.  This is complicated by copies between the two which can
 865 /// and will commonly cause multiple value numbers to be merged into one.
 866 ///
 867 /// VN is the value number that we're trying to resolve.  InstDefiningValue
 868 /// keeps track of the new InstDefiningValue assignment for the result
 869 /// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
 870 /// whether a value in this or other is a copy from the opposite set.
 871 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
 872 /// already been assigned.
 873 ///
 874 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
 875 /// contains the value number the copy is from.
 876 ///
 877 static unsigned ComputeUltimateVN(VNInfo *VNI,
 878                                   SmallVector<VNInfo*, 16> &NewVNInfo,
 879                                   DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
 880                                   DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
 881                                   SmallVector<int, 16> &ThisValNoAssignments,
 882                                   SmallVector<int, 16> &OtherValNoAssignments) {
 883   unsigned VN = VNI->id;
 884
 885   // If the VN has already been computed, just return it.
 886   if (ThisValNoAssignments[VN] >= 0)
 887     return ThisValNoAssignments[VN];
 888 //  assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?");
 889
 890   // If this val is not a copy from the other val, then it must be a new value
 891   // number in the destination.
 892   DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
 893   if (I == ThisFromOther.end()) {
 894     NewVNInfo.push_back(VNI);
 895     return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
 896   }
 897   VNInfo *OtherValNo = I->second;
 898
 899   // Otherwise, this *is* a copy from the RHS.  If the other side has already
 900   // been computed, return it.
 901   if (OtherValNoAssignments[OtherValNo->id] >= 0)
 902     return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
 903
 904   // Mark this value number as currently being computed, then ask what the
 905   // ultimate value # of the other value is.
 906   ThisValNoAssignments[VN] = -2;
 907   unsigned UltimateVN =
 908     ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
 909                       OtherValNoAssignments, ThisValNoAssignments);
 910   return ThisValNoAssignments[VN] = UltimateVN;
 911 }
 912
 913 static bool InVector(VNInfo *Val, const SmallVector<VNInfo*, 8> &V) {
 914   return std::find(V.begin(), V.end(), Val) != V.end();
 915 }
 916
 917 /// SimpleJoin - Attempt to joint the specified interval into this one. The
 918 /// caller of this method must guarantee that the RHS only contains a single
 919 /// value number and that the RHS is not defined by a copy from this
 920 /// interval.  This returns false if the intervals are not joinable, or it
 921 /// joins them and returns true.
 922 bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){
 923   assert(RHS.containsOneValue());
 924
 925   // Some number (potentially more than one) value numbers in the current
 926   // interval may be defined as copies from the RHS.  Scan the overlapping
 927   // portions of the LHS and RHS, keeping track of this and looking for
 928   // overlapping live ranges that are NOT defined as copies.  If these exist, we
 929   // cannot coalesce.
 930
 931   LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end();
 932   LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end();
 933
 934   if (LHSIt->start < RHSIt->start) {
 935     LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start);
 936     if (LHSIt != LHS.begin()) --LHSIt;
 937   } else if (RHSIt->start < LHSIt->start) {
 938     RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start);
 939     if (RHSIt != RHS.begin()) --RHSIt;
 940   }
 941
 942   SmallVector<VNInfo*, 8> EliminatedLHSVals;
 943
 944   while (1) {
 945     // Determine if these live intervals overlap.
 946     bool Overlaps = false;
 947     if (LHSIt->start <= RHSIt->start)
 948       Overlaps = LHSIt->end > RHSIt->start;
 949     else
 950       Overlaps = RHSIt->end > LHSIt->start;
 951
 952     // If the live intervals overlap, there are two interesting cases: if the
 953     // LHS interval is defined by a copy from the RHS, it's ok and we record
 954     // that the LHS value # is the same as the RHS.  If it's not, then we cannot
 955     // coalesce these live ranges and we bail out.
 956     if (Overlaps) {
 957       // If we haven't already recorded that this value # is safe, check it.
 958       if (!InVector(LHSIt->valno, EliminatedLHSVals)) {
 959         // Copy from the RHS?
 960         unsigned SrcReg = li_->getVNInfoSourceReg(LHSIt->valno);
 961         if (SrcReg != RHS.reg)
 962           return false;    // Nope, bail out.
 963
 964         EliminatedLHSVals.push_back(LHSIt->valno);
 965       }
 966
 967       // We know this entire LHS live range is okay, so skip it now.
 968       if (++LHSIt == LHSEnd) break;
 969       continue;
 970     }
 971
 972     if (LHSIt->end < RHSIt->end) {
 973       if (++LHSIt == LHSEnd) break;
 974     } else {
 975       // One interesting case to check here.  It's possible that we have
 976       // something like "X3 = Y" which defines a new value number in the LHS,
 977       // and is the last use of this liverange of the RHS.  In this case, we
 978       // want to notice this copy (so that it gets coalesced away) even though
 979       // the live ranges don't actually overlap.
 980       if (LHSIt->start == RHSIt->end) {
 981         if (InVector(LHSIt->valno, EliminatedLHSVals)) {
 982           // We already know that this value number is going to be merged in
 983           // if coalescing succeeds.  Just skip the liverange.
 984           if (++LHSIt == LHSEnd) break;
 985         } else {
 986           // Otherwise, if this is a copy from the RHS, mark it as being merged
 987           // in.
 988           if (li_->getVNInfoSourceReg(LHSIt->valno) == RHS.reg) {
 989             EliminatedLHSVals.push_back(LHSIt->valno);
 990
 991             // We know this entire LHS live range is okay, so skip it now.
 992             if (++LHSIt == LHSEnd) break;
 993           }
 994         }
 995       }
 996
 997       if (++RHSIt == RHSEnd) break;
 998     }
 999   }
1000
1001   // If we got here, we know that the coalescing will be successful and that
1002   // the value numbers in EliminatedLHSVals will all be merged together.  Since
1003   // the most common case is that EliminatedLHSVals has a single number, we
1004   // optimize for it: if there is more than one value, we merge them all into
1005   // the lowest numbered one, then handle the interval as if we were merging
1006   // with one value number.
1007   VNInfo *LHSValNo;
1008   if (EliminatedLHSVals.size() > 1) {
1009     // Loop through all the equal value numbers merging them into the smallest
1010     // one.
1011     VNInfo *Smallest = EliminatedLHSVals[0];
1012     for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) {
1013       if (EliminatedLHSVals[i]->id < Smallest->id) {
1014         // Merge the current notion of the smallest into the smaller one.
1015         LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]);
1016         Smallest = EliminatedLHSVals[i];
1017       } else {
1018         // Merge into the smallest.
1019         LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest);
1020       }
1021     }
1022     LHSValNo = Smallest;
1023   } else {
1024     assert(!EliminatedLHSVals.empty() && "No copies from the RHS?");
1025     LHSValNo = EliminatedLHSVals[0];
1026   }
1027
1028   // Okay, now that there is a single LHS value number that we're merging the
1029   // RHS into, update the value number info for the LHS to indicate that the
1030   // value number is defined where the RHS value number was.
1031   const VNInfo *VNI = RHS.getValNumInfo(0);
1032   LHSValNo->def  = VNI->def;
1033   LHSValNo->copy = VNI->copy;
1034
1035   // Okay, the final step is to loop over the RHS live intervals, adding them to
1036   // the LHS.
1037   LHSValNo->hasPHIKill |= VNI->hasPHIKill;
1038   LHS.addKills(LHSValNo, VNI->kills);
1039   LHS.MergeRangesInAsValue(RHS, LHSValNo);
1040   LHS.weight += RHS.weight;
1041   if (RHS.preference && !LHS.preference)
1042     LHS.preference = RHS.preference;
1043
1044   return true;
1045 }
1046
1047 /// JoinIntervals - Attempt to join these two intervals.  On failure, this
1048 /// returns false.  Otherwise, if one of the intervals being joined is a
1049 /// physreg, this method always canonicalizes LHS to be it.  The output
1050 /// "RHS" will not have been modified, so we can use this information
1051 /// below to update aliases.
1052 bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS,
1053                                              LiveInterval &RHS, bool &Swapped) {
1054   // Compute the final value assignment, assuming that the live ranges can be
1055   // coalesced.
1056   SmallVector<int, 16> LHSValNoAssignments;
1057   SmallVector<int, 16> RHSValNoAssignments;
1058   DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
1059   DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
1060   SmallVector<VNInfo*, 16> NewVNInfo;
1061
1062   // If a live interval is a physical register, conservatively check if any
1063   // of its sub-registers is overlapping the live interval of the virtual
1064   // register. If so, do not coalesce.
1065   if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) &&
1066       *tri_->getSubRegisters(LHS.reg)) {
1067     for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR)
1068       if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
1069         DOUT << "Interfere with sub-register ";
1070         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
1071         return false;
1072       }
1073   } else if (TargetRegisterInfo::isPhysicalRegister(RHS.reg) &&
1074              *tri_->getSubRegisters(RHS.reg)) {
1075     for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR)
1076       if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) {
1077         DOUT << "Interfere with sub-register ";
1078         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
1079         return false;
1080       }
1081   }
1082
1083   // Compute ultimate value numbers for the LHS and RHS values.
1084   if (RHS.containsOneValue()) {
1085     // Copies from a liveinterval with a single value are simple to handle and
1086     // very common, handle the special case here.  This is important, because
1087     // often RHS is small and LHS is large (e.g. a physreg).
1088
1089     // Find out if the RHS is defined as a copy from some value in the LHS.
1090     int RHSVal0DefinedFromLHS = -1;
1091     int RHSValID = -1;
1092     VNInfo *RHSValNoInfo = NULL;
1093     VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0);
1094     unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0);
1095     if ((RHSSrcReg == 0 || RHSSrcReg != LHS.reg)) {
1096       // If RHS is not defined as a copy from the LHS, we can use simpler and
1097       // faster checks to see if the live ranges are coalescable.  This joiner
1098       // can't swap the LHS/RHS intervals though.
1099       if (!TargetRegisterInfo::isPhysicalRegister(RHS.reg)) {
1100         return SimpleJoin(LHS, RHS);
1101       } else {
1102         RHSValNoInfo = RHSValNoInfo0;
1103       }
1104     } else {
1105       // It was defined as a copy from the LHS, find out what value # it is.
1106       RHSValNoInfo = LHS.getLiveRangeContaining(RHSValNoInfo0->def-1)->valno;
1107       RHSValID = RHSValNoInfo->id;
1108       RHSVal0DefinedFromLHS = RHSValID;
1109     }
1110
1111     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1112     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1113     NewVNInfo.resize(LHS.getNumValNums(), NULL);
1114
1115     // Okay, *all* of the values in LHS that are defined as a copy from RHS
1116     // should now get updated.
1117     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1118          i != e; ++i) {
1119       VNInfo *VNI = *i;
1120       unsigned VN = VNI->id;
1121       if (unsigned LHSSrcReg = li_->getVNInfoSourceReg(VNI)) {
1122         if (LHSSrcReg != RHS.reg) {
1123           // If this is not a copy from the RHS, its value number will be
1124           // unmodified by the coalescing.
1125           NewVNInfo[VN] = VNI;
1126           LHSValNoAssignments[VN] = VN;
1127         } else if (RHSValID == -1) {
1128           // Otherwise, it is a copy from the RHS, and we don't already have a
1129           // value# for it.  Keep the current value number, but remember it.
1130           LHSValNoAssignments[VN] = RHSValID = VN;
1131           NewVNInfo[VN] = RHSValNoInfo;
1132           LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0;
1133         } else {
1134           // Otherwise, use the specified value #.
1135           LHSValNoAssignments[VN] = RHSValID;
1136           if (VN == (unsigned)RHSValID) {  // Else this val# is dead.
1137             NewVNInfo[VN] = RHSValNoInfo;
1138             LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0;
1139           }
1140         }
1141       } else {
1142         NewVNInfo[VN] = VNI;
1143         LHSValNoAssignments[VN] = VN;
1144       }
1145     }
1146
1147     assert(RHSValID != -1 && "Didn't find value #?");
1148     RHSValNoAssignments[0] = RHSValID;
1149     if (RHSVal0DefinedFromLHS != -1) {
1150       // This path doesn't go through ComputeUltimateVN so just set
1151       // it to anything.
1152       RHSValsDefinedFromLHS[RHSValNoInfo0] = (VNInfo*)1;
1153     }
1154   } else {
1155     // Loop over the value numbers of the LHS, seeing if any are defined from
1156     // the RHS.
1157     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1158          i != e; ++i) {
1159       VNInfo *VNI = *i;
1160       if (VNI->def == ~1U || VNI->copy == 0)  // Src not defined by a copy?
1161         continue;
1162
1163       // DstReg is known to be a register in the LHS interval.  If the src is
1164       // from the RHS interval, we can use its value #.
1165       if (li_->getVNInfoSourceReg(VNI) != RHS.reg)
1166         continue;
1167
1168       // Figure out the value # from the RHS.
1169       LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno;
1170     }
1171
1172     // Loop over the value numbers of the RHS, seeing if any are defined from
1173     // the LHS.
1174     for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1175          i != e; ++i) {
1176       VNInfo *VNI = *i;
1177       if (VNI->def == ~1U || VNI->copy == 0)  // Src not defined by a copy?
1178         continue;
1179
1180       // DstReg is known to be a register in the RHS interval.  If the src is
1181       // from the LHS interval, we can use its value #.
1182       if (li_->getVNInfoSourceReg(VNI) != LHS.reg)
1183         continue;
1184
1185       // Figure out the value # from the LHS.
1186       RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno;
1187     }
1188
1189     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1190     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1191     NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
1192
1193     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1194          i != e; ++i) {
1195       VNInfo *VNI = *i;
1196       unsigned VN = VNI->id;
1197       if (LHSValNoAssignments[VN] >= 0 || VNI->def == ~1U)
1198         continue;
1199       ComputeUltimateVN(VNI, NewVNInfo,
1200                         LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
1201                         LHSValNoAssignments, RHSValNoAssignments);
1202     }
1203     for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1204          i != e; ++i) {
1205       VNInfo *VNI = *i;
1206       unsigned VN = VNI->id;
1207       if (RHSValNoAssignments[VN] >= 0 || VNI->def == ~1U)
1208         continue;
1209       // If this value number isn't a copy from the LHS, it's a new number.
1210       if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
1211         NewVNInfo.push_back(VNI);
1212         RHSValNoAssignments[VN] = NewVNInfo.size()-1;
1213         continue;
1214       }
1215
1216       ComputeUltimateVN(VNI, NewVNInfo,
1217                         RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
1218                         RHSValNoAssignments, LHSValNoAssignments);
1219     }
1220   }
1221
1222   // Armed with the mappings of LHS/RHS values to ultimate values, walk the
1223   // interval lists to see if these intervals are coalescable.
1224   LiveInterval::const_iterator I = LHS.begin();
1225   LiveInterval::const_iterator IE = LHS.end();
1226   LiveInterval::const_iterator J = RHS.begin();
1227   LiveInterval::const_iterator JE = RHS.end();
1228
1229   // Skip ahead until the first place of potential sharing.
1230   if (I->start < J->start) {
1231     I = std::upper_bound(I, IE, J->start);
1232     if (I != LHS.begin()) --I;
1233   } else if (J->start < I->start) {
1234     J = std::upper_bound(J, JE, I->start);
1235     if (J != RHS.begin()) --J;
1236   }
1237
1238   while (1) {
1239     // Determine if these two live ranges overlap.
1240     bool Overlaps;
1241     if (I->start < J->start) {
1242       Overlaps = I->end > J->start;
1243     } else {
1244       Overlaps = J->end > I->start;
1245     }
1246
1247     // If so, check value # info to determine if they are really different.
1248     if (Overlaps) {
1249       // If the live range overlap will map to the same value number in the
1250       // result liverange, we can still coalesce them.  If not, we can't.
1251       if (LHSValNoAssignments[I->valno->id] !=
1252           RHSValNoAssignments[J->valno->id])
1253         return false;
1254     }
1255
1256     if (I->end < J->end) {
1257       ++I;
1258       if (I == IE) break;
1259     } else {
1260       ++J;
1261       if (J == JE) break;
1262     }
1263   }
1264
1265   // Update kill info. Some live ranges are extended due to copy coalescing.
1266   for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(),
1267          E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
1268     VNInfo *VNI = I->first;
1269     unsigned LHSValID = LHSValNoAssignments[VNI->id];
1270     LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def);
1271     NewVNInfo[LHSValID]->hasPHIKill |= VNI->hasPHIKill;
1272     RHS.addKills(NewVNInfo[LHSValID], VNI->kills);
1273   }
1274
1275   // Update kill info. Some live ranges are extended due to copy coalescing.
1276   for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(),
1277          E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
1278     VNInfo *VNI = I->first;
1279     unsigned RHSValID = RHSValNoAssignments[VNI->id];
1280     LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def);
1281     NewVNInfo[RHSValID]->hasPHIKill |= VNI->hasPHIKill;
1282     LHS.addKills(NewVNInfo[RHSValID], VNI->kills);
1283   }
1284
1285   // If we get here, we know that we can coalesce the live ranges.  Ask the
1286   // intervals to coalesce themselves now.
1287   if ((RHS.ranges.size() > LHS.ranges.size() &&
1288       TargetRegisterInfo::isVirtualRegister(LHS.reg)) ||
1289       TargetRegisterInfo::isPhysicalRegister(RHS.reg)) {
1290     RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo);
1291     Swapped = true;
1292   } else {
1293     LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo);
1294     Swapped = false;
1295   }
1296   return true;
1297 }
1298
1299 namespace {
1300   // DepthMBBCompare - Comparison predicate that sort first based on the loop
1301   // depth of the basic block (the unsigned), and then on the MBB number.
1302   struct DepthMBBCompare {
1303     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
1304     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
1305       if (LHS.first > RHS.first) return true;   // Deeper loops first
1306       return LHS.first == RHS.first &&
1307         LHS.second->getNumber() < RHS.second->getNumber();
1308     }
1309   };
1310 }
1311
1312 /// getRepIntervalSize - Returns the size of the interval that represents the
1313 /// specified register.
1314 template<class SF>
1315 unsigned JoinPriorityQueue<SF>::getRepIntervalSize(unsigned Reg) {
1316   return Rc->getRepIntervalSize(Reg);
1317 }
1318
1319 /// CopyRecSort::operator - Join priority queue sorting function.
1320 ///
1321 bool CopyRecSort::operator()(CopyRec left, CopyRec right) const {
1322   // Inner loops first.
1323   if (left.LoopDepth > right.LoopDepth)
1324     return false;
1325   else if (left.LoopDepth == right.LoopDepth)
1326     if (left.isBackEdge && !right.isBackEdge)
1327       return false;
1328   return true;
1329 }
1330
1331 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
1332                                                std::vector<CopyRec> &TryAgain) {
1333   DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
1334
1335   std::vector<CopyRec> VirtCopies;
1336   std::vector<CopyRec> PhysCopies;
1337   unsigned LoopDepth = loopInfo->getLoopDepth(MBB);
1338   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
1339        MII != E;) {
1340     MachineInstr *Inst = MII++;
1341
1342     // If this isn't a copy nor a extract_subreg, we can't join intervals.
1343     unsigned SrcReg, DstReg;
1344     if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
1345       DstReg = Inst->getOperand(0).getReg();
1346       SrcReg = Inst->getOperand(1).getReg();
1347     } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg))
1348       continue;
1349
1350     bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
1351     bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1352     if (NewHeuristic) {
1353       JoinQueue->push(CopyRec(Inst, LoopDepth, isBackEdgeCopy(Inst, DstReg)));
1354     } else {
1355       if (SrcIsPhys || DstIsPhys)
1356         PhysCopies.push_back(CopyRec(Inst, 0, false));
1357       else
1358         VirtCopies.push_back(CopyRec(Inst, 0, false));
1359     }
1360   }
1361
1362   if (NewHeuristic)
1363     return;
1364
1365   // Try coalescing physical register + virtual register first.
1366   for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) {
1367     CopyRec &TheCopy = PhysCopies[i];
1368     bool Again = false;
1369     if (!JoinCopy(TheCopy, Again))
1370       if (Again)
1371         TryAgain.push_back(TheCopy);
1372   }
1373   for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) {
1374     CopyRec &TheCopy = VirtCopies[i];
1375     bool Again = false;
1376     if (!JoinCopy(TheCopy, Again))
1377       if (Again)
1378         TryAgain.push_back(TheCopy);
1379   }
1380 }
1381
1382 void SimpleRegisterCoalescing::joinIntervals() {
1383   DOUT << "********** JOINING INTERVALS ***********\n";
1384
1385   if (NewHeuristic)
1386     JoinQueue = new JoinPriorityQueue<CopyRecSort>(this);
1387
1388   std::vector<CopyRec> TryAgainList;
1389   if (loopInfo->begin() == loopInfo->end()) {
1390     // If there are no loops in the function, join intervals in function order.
1391     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
1392          I != E; ++I)
1393       CopyCoalesceInMBB(I, TryAgainList);
1394   } else {
1395     // Otherwise, join intervals in inner loops before other intervals.
1396     // Unfortunately we can't just iterate over loop hierarchy here because
1397     // there may be more MBB's than BB's.  Collect MBB's for sorting.
1398
1399     // Join intervals in the function prolog first. We want to join physical
1400     // registers with virtual registers before the intervals got too long.
1401     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
1402     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){
1403       MachineBasicBlock *MBB = I;
1404       MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I));
1405     }
1406
1407     // Sort by loop depth.
1408     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
1409
1410     // Finally, join intervals in loop nest order.
1411     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
1412       CopyCoalesceInMBB(MBBs[i].second, TryAgainList);
1413   }
1414
1415   // Joining intervals can allow other intervals to be joined.  Iteratively join
1416   // until we make no progress.
1417   if (NewHeuristic) {
1418     SmallVector<CopyRec, 16> TryAgain;
1419     bool ProgressMade = true;
1420     while (ProgressMade) {
1421       ProgressMade = false;
1422       while (!JoinQueue->empty()) {
1423         CopyRec R = JoinQueue->pop();
1424         bool Again = false;
1425         bool Success = JoinCopy(R, Again);
1426         if (Success)
1427           ProgressMade = true;
1428         else if (Again)
1429           TryAgain.push_back(R);
1430       }
1431
1432       if (ProgressMade) {
1433         while (!TryAgain.empty()) {
1434           JoinQueue->push(TryAgain.back());
1435           TryAgain.pop_back();
1436         }
1437       }
1438     }
1439   } else {
1440     bool ProgressMade = true;
1441     while (ProgressMade) {
1442       ProgressMade = false;
1443
1444       for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
1445         CopyRec &TheCopy = TryAgainList[i];
1446         if (TheCopy.MI) {
1447           bool Again = false;
1448           bool Success = JoinCopy(TheCopy, Again);
1449           if (Success || !Again) {
1450             TheCopy.MI = 0;   // Mark this one as done.
1451             ProgressMade = true;
1452           }
1453         }
1454       }
1455     }
1456   }
1457
1458   if (NewHeuristic)
1459     delete JoinQueue;
1460 }
1461
1462 /// Return true if the two specified registers belong to different register
1463 /// classes.  The registers may be either phys or virt regs.
1464 bool SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
1465                                                         unsigned RegB) const {
1466
1467   // Get the register classes for the first reg.
1468   if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
1469     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1470            "Shouldn't consider two physregs!");
1471     return !mri_->getRegClass(RegB)->contains(RegA);
1472   }
1473
1474   // Compare against the regclass for the second reg.
1475   const TargetRegisterClass *RegClass = mri_->getRegClass(RegA);
1476   if (TargetRegisterInfo::isVirtualRegister(RegB))
1477     return RegClass != mri_->getRegClass(RegB);
1478   else
1479     return !RegClass->contains(RegB);
1480 }
1481
1482 /// lastRegisterUse - Returns the last use of the specific register between
1483 /// cycles Start and End or NULL if there are no uses.
1484 MachineOperand *
1485 SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
1486                                           unsigned Reg, unsigned &UseIdx) const{
1487   UseIdx = 0;
1488   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1489     MachineOperand *LastUse = NULL;
1490     for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg),
1491            E = mri_->use_end(); I != E; ++I) {
1492       MachineOperand &Use = I.getOperand();
1493       MachineInstr *UseMI = Use.getParent();
1494       unsigned Idx = li_->getInstructionIndex(UseMI);
1495       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
1496         LastUse = &Use;
1497         UseIdx = Idx;
1498       }
1499     }
1500     return LastUse;
1501   }
1502
1503   int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM;
1504   int s = Start;
1505   while (e >= s) {
1506     // Skip deleted instructions
1507     MachineInstr *MI = li_->getInstructionFromIndex(e);
1508     while ((e - InstrSlots::NUM) >= s && !MI) {
1509       e -= InstrSlots::NUM;
1510       MI = li_->getInstructionFromIndex(e);
1511     }
1512     if (e < s || MI == NULL)
1513       return NULL;
1514
1515     for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
1516       MachineOperand &Use = MI->getOperand(i);
1517       if (Use.isRegister() && Use.isUse() && Use.getReg() &&
1518           tri_->regsOverlap(Use.getReg(), Reg)) {
1519         UseIdx = e;
1520         return &Use;
1521       }
1522     }
1523
1524     e -= InstrSlots::NUM;
1525   }
1526
1527   return NULL;
1528 }
1529
1530
1531 void SimpleRegisterCoalescing::printRegName(unsigned reg) const {
1532   if (TargetRegisterInfo::isPhysicalRegister(reg))
1533     cerr << tri_->getName(reg);
1534   else
1535     cerr << "%reg" << reg;
1536 }
1537
1538 void SimpleRegisterCoalescing::releaseMemory() {
1539   JoinedCopies.clear();
1540 }
1541
1542 static bool isZeroLengthInterval(LiveInterval *li) {
1543   for (LiveInterval::Ranges::const_iterator
1544          i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
1545     if (i->end - i->start > LiveIntervals::InstrSlots::NUM)
1546       return false;
1547   return true;
1548 }
1549
1550 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
1551   mf_ = &fn;
1552   mri_ = &fn.getRegInfo();
1553   tm_ = &fn.getTarget();
1554   tri_ = tm_->getRegisterInfo();
1555   tii_ = tm_->getInstrInfo();
1556   li_ = &getAnalysis<LiveIntervals>();
1557   lv_ = &getAnalysis<LiveVariables>();
1558   loopInfo = &getAnalysis<MachineLoopInfo>();
1559
1560   DOUT << "********** SIMPLE REGISTER COALESCING **********\n"
1561        << "********** Function: "
1562        << ((Value*)mf_->getFunction())->getName() << '\n';
1563
1564   allocatableRegs_ = tri_->getAllocatableSet(fn);
1565   for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(),
1566          E = tri_->regclass_end(); I != E; ++I)
1567     allocatableRCRegs_.insert(std::make_pair(*I,
1568                                              tri_->getAllocatableSet(fn, *I)));
1569
1570   // Join (coalesce) intervals if requested.
1571   if (EnableJoining) {
1572     joinIntervals();
1573     DOUT << "********** INTERVALS POST JOINING **********\n";
1574     for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){
1575       I->second.print(DOUT, tri_);
1576       DOUT << "\n";
1577     }
1578
1579     // Delete all coalesced copies.
1580     for (SmallPtrSet<MachineInstr*,32>::iterator I = JoinedCopies.begin(),
1581            E = JoinedCopies.end(); I != E; ++I) {
1582       li_->RemoveMachineInstrFromMaps(*I);
1583       (*I)->eraseFromParent();
1584       ++numPeep;
1585     }
1586   }
1587
1588   // Perform a final pass over the instructions and compute spill weights
1589   // and remove identity moves.
1590   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
1591        mbbi != mbbe; ++mbbi) {
1592     MachineBasicBlock* mbb = mbbi;
1593     unsigned loopDepth = loopInfo->getLoopDepth(mbb);
1594
1595     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
1596          mii != mie; ) {
1597       // if the move will be an identity move delete it
1598       unsigned srcReg, dstReg;
1599       if (tii_->isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) {
1600         // remove from def list
1601         LiveInterval &RegInt = li_->getOrCreateInterval(srcReg);
1602         // If def of this move instruction is dead, remove its live range from
1603         // the dstination register's live interval.
1604         if (mii->registerDefIsDead(dstReg))
1605           ShortenDeadCopyLiveRange(RegInt, mii);
1606         li_->RemoveMachineInstrFromMaps(mii);
1607         mii = mbbi->erase(mii);
1608         ++numPeep;
1609       } else {
1610         SmallSet<unsigned, 4> UniqueUses;
1611         for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
1612           const MachineOperand &mop = mii->getOperand(i);
1613           if (mop.isRegister() && mop.getReg() &&
1614               TargetRegisterInfo::isVirtualRegister(mop.getReg())) {
1615             unsigned reg = mop.getReg();
1616             // Multiple uses of reg by the same instruction. It should not
1617             // contribute to spill weight again.
1618             if (UniqueUses.count(reg) != 0)
1619               continue;
1620             LiveInterval &RegInt = li_->getInterval(reg);
1621             RegInt.weight +=
1622               li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth);
1623             UniqueUses.insert(reg);
1624           }
1625         }
1626         ++mii;
1627       }
1628     }
1629   }
1630
1631   for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) {
1632     LiveInterval &LI = I->second;
1633     if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1634       // If the live interval length is essentially zero, i.e. in every live
1635       // range the use follows def immediately, it doesn't make sense to spill
1636       // it and hope it will be easier to allocate for this li.
1637       if (isZeroLengthInterval(&LI))
1638         LI.weight = HUGE_VALF;
1639       else {
1640         bool isLoad = false;
1641         if (li_->isReMaterializable(LI, isLoad)) {
1642           // If all of the definitions of the interval are re-materializable,
1643           // it is a preferred candidate for spilling. If non of the defs are
1644           // loads, then it's potentially very cheap to re-materialize.
1645           // FIXME: this gets much more complicated once we support non-trivial
1646           // re-materialization.
1647           if (isLoad)
1648             LI.weight *= 0.9F;
1649           else
1650             LI.weight *= 0.5F;
1651         }
1652       }
1653
1654       // Slightly prefer live interval that has been assigned a preferred reg.
1655       if (LI.preference)
1656         LI.weight *= 1.01F;
1657
1658       // Divide the weight of the interval by its size.  This encourages
1659       // spilling of intervals that are large and have few uses, and
1660       // discourages spilling of small intervals with many uses.
1661       LI.weight /= LI.getSize();
1662     }
1663   }
1664
1665   DEBUG(dump());
1666   return true;
1667 }
1668
1669 /// print - Implement the dump method.
1670 void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const {
1671    li_->print(O, m);
1672 }
1673
1674 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() {
1675   return new SimpleRegisterCoalescing();
1676 }
1677
1678 // Make sure that anything that uses RegisterCoalescer pulls in this file...
1679 DEFINING_FILE_FOR(SimpleRegisterCoalescing)