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/Analysis/AliasAnalysis.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/Target/TargetOptions.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/ADT/OwningPtr.h"
  35 #include "llvm/ADT/SmallSet.h"
  36 #include "llvm/ADT/Statistic.h"
  37 #include "llvm/ADT/STLExtras.h"
  38 #include <algorithm>
  39 #include <cmath>
  40 using namespace llvm;
  41
  42 STATISTIC(numJoins    , "Number of interval joins performed");
  43 STATISTIC(numCrossRCs , "Number of cross class joins performed");
  44 STATISTIC(numCommutes , "Number of instruction commuting performed");
  45 STATISTIC(numExtends  , "Number of copies extended");
  46 STATISTIC(NumReMats   , "Number of instructions re-materialized");
  47 STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
  48 STATISTIC(numAborts   , "Number of times interval joining aborted");
  49 STATISTIC(numDeadValNo, "Number of valno def marked dead");
  50
  51 char SimpleRegisterCoalescing::ID = 0;
  52 static cl::opt<bool>
  53 EnableJoining("join-liveintervals",
  54               cl::desc("Coalesce copies (default=true)"),
  55               cl::init(true));
  56
  57 static cl::opt<bool>
  58 DisableCrossClassJoin("disable-cross-class-join",
  59                cl::desc("Avoid coalescing cross register class copies"),
  60                cl::init(false), cl::Hidden);
  61
  62 static RegisterPass<SimpleRegisterCoalescing>
  63 X("simple-register-coalescing", "Simple Register Coalescing");
  64
  65 // Declare that we implement the RegisterCoalescer interface
  66 static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
  67
  68 const PassInfo *const llvm::SimpleRegisterCoalescingID = &X;
  69
  70 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
  71   AU.setPreservesCFG();
  72   AU.addRequired<AliasAnalysis>();
  73   AU.addRequired<LiveIntervals>();
  74   AU.addPreserved<LiveIntervals>();
  75   AU.addPreserved<SlotIndexes>();
  76   AU.addRequired<MachineLoopInfo>();
  77   AU.addPreserved<MachineLoopInfo>();
  78   AU.addPreservedID(MachineDominatorsID);
  79   if (StrongPHIElim)
  80     AU.addPreservedID(StrongPHIEliminationID);
  81   else
  82     AU.addPreservedID(PHIEliminationID);
  83   AU.addPreservedID(TwoAddressInstructionPassID);
  84   MachineFunctionPass::getAnalysisUsage(AU);
  85 }
  86
  87 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
  88 /// being the source and IntB being the dest, thus this defines a value number
  89 /// in IntB.  If the source value number (in IntA) is defined by a copy from B,
  90 /// see if we can merge these two pieces of B into a single value number,
  91 /// eliminating a copy.  For example:
  92 ///
  93 ///  A3 = B0
  94 ///    ...
  95 ///  B1 = A3      <- this copy
  96 ///
  97 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
  98 /// value number to be replaced with B0 (which simplifies the B liveinterval).
  99 ///
 100 /// This returns true if an interval was modified.
 101 ///
 102 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(const CoalescerPair &CP,
 103                                                     MachineInstr *CopyMI) {
 104   LiveInterval &IntA =
 105     li_->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
 106   LiveInterval &IntB =
 107     li_->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
 108   SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
 109
 110   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
 111   // the example above.
 112   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 113   assert(BLR != IntB.end() && "Live range not found!");
 114   VNInfo *BValNo = BLR->valno;
 115
 116   // Get the location that B is defined at.  Two options: either this value has
 117   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 118   // can't process it.
 119   if (!BValNo->getCopy()) return false;
 120   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 121
 122   // AValNo is the value number in A that defines the copy, A3 in the example.
 123   SlotIndex CopyUseIdx = CopyIdx.getUseIndex();
 124   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
 125   // The live range might not exist after fun with physreg coalescing.
 126   if (ALR == IntA.end()) return false;
 127   VNInfo *AValNo = ALR->valno;
 128   // If it's re-defined by an early clobber somewhere in the live range, then
 129   // it's not safe to eliminate the copy. FIXME: This is a temporary workaround.
 130   // See PR3149:
 131   // 172     %ECX<def> = MOV32rr %reg1039<kill>
 132   // 180     INLINEASM <es:subl $5,$1
 133   //         sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9,
 134   //         %EAX<kill>,
 135   // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0
 136   // 188     %EAX<def> = MOV32rr %EAX<kill>
 137   // 196     %ECX<def> = MOV32rr %ECX<kill>
 138   // 204     %ECX<def> = MOV32rr %ECX<kill>
 139   // 212     %EAX<def> = MOV32rr %EAX<kill>
 140   // 220     %EAX<def> = MOV32rr %EAX
 141   // 228     %reg1039<def> = MOV32rr %ECX<kill>
 142   // The early clobber operand ties ECX input to the ECX def.
 143   //
 144   // The live interval of ECX is represented as this:
 145   // %reg20,inf = [46,47:1)[174,230:0)  0@174-(230) 1@46-(47)
 146   // The coalescer has no idea there was a def in the middle of [174,230].
 147   if (AValNo->hasRedefByEC())
 148     return false;
 149
 150   // If AValNo is defined as a copy from IntB, we can potentially process this.
 151   // Get the instruction that defines this value number.
 152   if (!CP.isCoalescable(AValNo->getCopy()))
 153     return false;
 154
 155   // Get the LiveRange in IntB that this value number starts with.
 156   LiveInterval::iterator ValLR =
 157     IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot());
 158   if (ValLR == IntB.end())
 159     return false;
 160
 161   // Make sure that the end of the live range is inside the same block as
 162   // CopyMI.
 163   MachineInstr *ValLREndInst =
 164     li_->getInstructionFromIndex(ValLR->end.getPrevSlot());
 165   if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent())
 166     return false;
 167
 168   // Okay, we now know that ValLR ends in the same block that the CopyMI
 169   // live-range starts.  If there are no intervening live ranges between them in
 170   // IntB, we can merge them.
 171   if (ValLR+1 != BLR) return false;
 172
 173   // If a live interval is a physical register, conservatively check if any
 174   // of its sub-registers is overlapping the live interval of the virtual
 175   // register. If so, do not coalesce.
 176   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) &&
 177       *tri_->getSubRegisters(IntB.reg)) {
 178     for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
 179       if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) {
 180         DEBUG({
 181             dbgs() << "\t\tInterfere with sub-register ";
 182             li_->getInterval(*SR).print(dbgs(), tri_);
 183           });
 184         return false;
 185       }
 186   }
 187
 188   DEBUG({
 189       dbgs() << "Extending: ";
 190       IntB.print(dbgs(), tri_);
 191     });
 192
 193   SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
 194   // We are about to delete CopyMI, so need to remove it as the 'instruction
 195   // that defines this value #'. Update the valnum with the new defining
 196   // instruction #.
 197   BValNo->def  = FillerStart;
 198   BValNo->setCopy(0);
 199
 200   // Okay, we can merge them.  We need to insert a new liverange:
 201   // [ValLR.end, BLR.begin) of either value number, then we merge the
 202   // two value numbers.
 203   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
 204
 205   // If the IntB live range is assigned to a physical register, and if that
 206   // physreg has sub-registers, update their live intervals as well.
 207   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
 208     for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
 209       LiveInterval &SRLI = li_->getInterval(*SR);
 210       SRLI.addRange(LiveRange(FillerStart, FillerEnd,
 211                               SRLI.getNextValue(FillerStart, 0, true,
 212                                                 li_->getVNInfoAllocator())));
 213     }
 214   }
 215
 216   // Okay, merge "B1" into the same value number as "B0".
 217   if (BValNo != ValLR->valno) {
 218     IntB.MergeValueNumberInto(BValNo, ValLR->valno);
 219   }
 220   DEBUG({
 221       dbgs() << "   result = ";
 222       IntB.print(dbgs(), tri_);
 223       dbgs() << "\n";
 224     });
 225
 226   // If the source instruction was killing the source register before the
 227   // merge, unset the isKill marker given the live range has been extended.
 228   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
 229   if (UIdx != -1) {
 230     ValLREndInst->getOperand(UIdx).setIsKill(false);
 231   }
 232
 233   // If the copy instruction was killing the destination register before the
 234   // merge, find the last use and trim the live range. That will also add the
 235   // isKill marker.
 236   if (ALR->end == CopyIdx)
 237     TrimLiveIntervalToLastUse(CopyUseIdx, CopyMI->getParent(), IntA, ALR);
 238
 239   ++numExtends;
 240   return true;
 241 }
 242
 243 /// HasOtherReachingDefs - Return true if there are definitions of IntB
 244 /// other than BValNo val# that can reach uses of AValno val# of IntA.
 245 bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA,
 246                                                     LiveInterval &IntB,
 247                                                     VNInfo *AValNo,
 248                                                     VNInfo *BValNo) {
 249   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 250        AI != AE; ++AI) {
 251     if (AI->valno != AValNo) continue;
 252     LiveInterval::Ranges::iterator BI =
 253       std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
 254     if (BI != IntB.ranges.begin())
 255       --BI;
 256     for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
 257       if (BI->valno == BValNo)
 258         continue;
 259       // When BValNo is null, we're looking for a dummy clobber-value for a subreg.
 260       if (!BValNo && !BI->valno->isDefAccurate() && !BI->valno->getCopy())
 261         continue;
 262       if (BI->start <= AI->start && BI->end > AI->start)
 263         return true;
 264       if (BI->start > AI->start && BI->start < AI->end)
 265         return true;
 266     }
 267   }
 268   return false;
 269 }
 270
 271 static void
 272 TransferImplicitOps(MachineInstr *MI, MachineInstr *NewMI) {
 273   for (unsigned i = MI->getDesc().getNumOperands(), e = MI->getNumOperands();
 274        i != e; ++i) {
 275     MachineOperand &MO = MI->getOperand(i);
 276     if (MO.isReg() && MO.isImplicit())
 277       NewMI->addOperand(MO);
 278   }
 279 }
 280
 281 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with
 282 /// IntA being the source and IntB being the dest, thus this defines a value
 283 /// number in IntB.  If the source value number (in IntA) is defined by a
 284 /// commutable instruction and its other operand is coalesced to the copy dest
 285 /// register, see if we can transform the copy into a noop by commuting the
 286 /// definition. For example,
 287 ///
 288 ///  A3 = op A2 B0<kill>
 289 ///    ...
 290 ///  B1 = A3      <- this copy
 291 ///    ...
 292 ///     = op A3   <- more uses
 293 ///
 294 /// ==>
 295 ///
 296 ///  B2 = op B0 A2<kill>
 297 ///    ...
 298 ///  B1 = B2      <- now an identify copy
 299 ///    ...
 300 ///     = op B2   <- more uses
 301 ///
 302 /// This returns true if an interval was modified.
 303 ///
 304 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
 305                                                         LiveInterval &IntB,
 306                                                         MachineInstr *CopyMI) {
 307   SlotIndex CopyIdx =
 308     li_->getInstructionIndex(CopyMI).getDefIndex();
 309
 310   // FIXME: For now, only eliminate the copy by commuting its def when the
 311   // source register is a virtual register. We want to guard against cases
 312   // where the copy is a back edge copy and commuting the def lengthen the
 313   // live interval of the source register to the entire loop.
 314   if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
 315     return false;
 316
 317   // BValNo is a value number in B that is defined by a copy from A. 'B3' in
 318   // the example above.
 319   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 320   assert(BLR != IntB.end() && "Live range not found!");
 321   VNInfo *BValNo = BLR->valno;
 322
 323   // Get the location that B is defined at.  Two options: either this value has
 324   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 325   // can't process it.
 326   if (!BValNo->getCopy()) return false;
 327   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 328
 329   // AValNo is the value number in A that defines the copy, A3 in the example.
 330   LiveInterval::iterator ALR =
 331     IntA.FindLiveRangeContaining(CopyIdx.getUseIndex()); //
 332
 333   assert(ALR != IntA.end() && "Live range not found!");
 334   VNInfo *AValNo = ALR->valno;
 335   // If other defs can reach uses of this def, then it's not safe to perform
 336   // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be
 337   // tested?
 338   if (AValNo->isPHIDef() || !AValNo->isDefAccurate() ||
 339       AValNo->isUnused() || AValNo->hasPHIKill())
 340     return false;
 341   MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def);
 342   const TargetInstrDesc &TID = DefMI->getDesc();
 343   if (!TID.isCommutable())
 344     return false;
 345   // If DefMI is a two-address instruction then commuting it will change the
 346   // destination register.
 347   int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg);
 348   assert(DefIdx != -1);
 349   unsigned UseOpIdx;
 350   if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
 351     return false;
 352   unsigned Op1, Op2, NewDstIdx;
 353   if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2))
 354     return false;
 355   if (Op1 == UseOpIdx)
 356     NewDstIdx = Op2;
 357   else if (Op2 == UseOpIdx)
 358     NewDstIdx = Op1;
 359   else
 360     return false;
 361
 362   MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
 363   unsigned NewReg = NewDstMO.getReg();
 364   if (NewReg != IntB.reg || !NewDstMO.isKill())
 365     return false;
 366
 367   // Make sure there are no other definitions of IntB that would reach the
 368   // uses which the new definition can reach.
 369   if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
 370     return false;
 371
 372   bool BHasSubRegs = false;
 373   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg))
 374     BHasSubRegs = *tri_->getSubRegisters(IntB.reg);
 375
 376   // Abort if the subregisters of IntB.reg have values that are not simply the
 377   // clobbers from the superreg.
 378   if (BHasSubRegs)
 379     for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
 380       if (HasOtherReachingDefs(IntA, li_->getInterval(*SR), AValNo, 0))
 381         return false;
 382
 383   // If some of the uses of IntA.reg is already coalesced away, return false.
 384   // It's not possible to determine whether it's safe to perform the coalescing.
 385   for (MachineRegisterInfo::use_nodbg_iterator UI =
 386          mri_->use_nodbg_begin(IntA.reg),
 387        UE = mri_->use_nodbg_end(); UI != UE; ++UI) {
 388     MachineInstr *UseMI = &*UI;
 389     SlotIndex UseIdx = li_->getInstructionIndex(UseMI);
 390     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 391     if (ULR == IntA.end())
 392       continue;
 393     if (ULR->valno == AValNo && JoinedCopies.count(UseMI))
 394       return false;
 395   }
 396
 397   // At this point we have decided that it is legal to do this
 398   // transformation.  Start by commuting the instruction.
 399   MachineBasicBlock *MBB = DefMI->getParent();
 400   MachineInstr *NewMI = tii_->commuteInstruction(DefMI);
 401   if (!NewMI)
 402     return false;
 403   if (NewMI != DefMI) {
 404     li_->ReplaceMachineInstrInMaps(DefMI, NewMI);
 405     MBB->insert(DefMI, NewMI);
 406     MBB->erase(DefMI);
 407   }
 408   unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
 409   NewMI->getOperand(OpIdx).setIsKill();
 410
 411   bool BHasPHIKill = BValNo->hasPHIKill();
 412   SmallVector<VNInfo*, 4> BDeadValNos;
 413   std::map<SlotIndex, SlotIndex> BExtend;
 414
 415   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
 416   // A = or A, B
 417   // ...
 418   // B = A
 419   // ...
 420   // C = A<kill>
 421   // ...
 422   //   = B
 423   bool Extended = BLR->end > ALR->end && ALR->end != ALR->start;
 424   if (Extended)
 425     BExtend[ALR->end] = BLR->end;
 426
 427   // Update uses of IntA of the specific Val# with IntB.
 428   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
 429          UE = mri_->use_end(); UI != UE;) {
 430     MachineOperand &UseMO = UI.getOperand();
 431     MachineInstr *UseMI = &*UI;
 432     ++UI;
 433     if (JoinedCopies.count(UseMI))
 434       continue;
 435     if (UseMI->isDebugValue()) {
 436       // FIXME These don't have an instruction index.  Not clear we have enough
 437       // info to decide whether to do this replacement or not.  For now do it.
 438       UseMO.setReg(NewReg);
 439       continue;
 440     }
 441     SlotIndex UseIdx = li_->getInstructionIndex(UseMI).getUseIndex();
 442     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 443     if (ULR == IntA.end() || ULR->valno != AValNo)
 444       continue;
 445     UseMO.setReg(NewReg);
 446     if (UseMI == CopyMI)
 447       continue;
 448     if (UseMO.isKill()) {
 449       if (Extended)
 450         UseMO.setIsKill(false);
 451     }
 452     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 453     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
 454       continue;
 455     if (DstReg == IntB.reg && DstSubIdx == 0) {
 456       // This copy will become a noop. If it's defining a new val#,
 457       // remove that val# as well. However this live range is being
 458       // extended to the end of the existing live range defined by the copy.
 459       SlotIndex DefIdx = UseIdx.getDefIndex();
 460       const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
 461       BHasPHIKill |= DLR->valno->hasPHIKill();
 462       assert(DLR->valno->def == DefIdx);
 463       BDeadValNos.push_back(DLR->valno);
 464       BExtend[DLR->start] = DLR->end;
 465       JoinedCopies.insert(UseMI);
 466     }
 467   }
 468
 469   // We need to insert a new liverange: [ALR.start, LastUse). It may be we can
 470   // simply extend BLR if CopyMI doesn't end the range.
 471   DEBUG({
 472       dbgs() << "Extending: ";
 473       IntB.print(dbgs(), tri_);
 474     });
 475
 476   // Remove val#'s defined by copies that will be coalesced away.
 477   for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) {
 478     VNInfo *DeadVNI = BDeadValNos[i];
 479     if (BHasSubRegs) {
 480       for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
 481         LiveInterval &SRLI = li_->getInterval(*SR);
 482         const LiveRange *SRLR = SRLI.getLiveRangeContaining(DeadVNI->def);
 483         SRLI.removeValNo(SRLR->valno);
 484       }
 485     }
 486     IntB.removeValNo(BDeadValNos[i]);
 487   }
 488
 489   // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
 490   // is updated.
 491   VNInfo *ValNo = BValNo;
 492   ValNo->def = AValNo->def;
 493   ValNo->setCopy(0);
 494   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 495        AI != AE; ++AI) {
 496     if (AI->valno != AValNo) continue;
 497     SlotIndex End = AI->end;
 498     std::map<SlotIndex, SlotIndex>::iterator
 499       EI = BExtend.find(End);
 500     if (EI != BExtend.end())
 501       End = EI->second;
 502     IntB.addRange(LiveRange(AI->start, End, ValNo));
 503
 504     // If the IntB live range is assigned to a physical register, and if that
 505     // physreg has sub-registers, update their live intervals as well.
 506     if (BHasSubRegs) {
 507       for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
 508         LiveInterval &SRLI = li_->getInterval(*SR);
 509         SRLI.MergeInClobberRange(*li_, AI->start, End,
 510                                  li_->getVNInfoAllocator());
 511       }
 512     }
 513   }
 514   ValNo->setHasPHIKill(BHasPHIKill);
 515
 516   DEBUG({
 517       dbgs() << "   result = ";
 518       IntB.print(dbgs(), tri_);
 519       dbgs() << "\nShortening: ";
 520       IntA.print(dbgs(), tri_);
 521     });
 522
 523   IntA.removeValNo(AValNo);
 524
 525   DEBUG({
 526       dbgs() << "   result = ";
 527       IntA.print(dbgs(), tri_);
 528       dbgs() << '\n';
 529     });
 530
 531   ++numCommutes;
 532   return true;
 533 }
 534
 535 /// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
 536 /// fallthoughs to SuccMBB.
 537 static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
 538                                   MachineBasicBlock *SuccMBB,
 539                                   const TargetInstrInfo *tii_) {
 540   if (MBB == SuccMBB)
 541     return true;
 542   MachineBasicBlock *TBB = 0, *FBB = 0;
 543   SmallVector<MachineOperand, 4> Cond;
 544   return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
 545     MBB->isSuccessor(SuccMBB);
 546 }
 547
 548 /// removeRange - Wrapper for LiveInterval::removeRange. This removes a range
 549 /// from a physical register live interval as well as from the live intervals
 550 /// of its sub-registers.
 551 static void removeRange(LiveInterval &li,
 552                         SlotIndex Start, SlotIndex End,
 553                         LiveIntervals *li_, const TargetRegisterInfo *tri_) {
 554   li.removeRange(Start, End, true);
 555   if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
 556     for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
 557       if (!li_->hasInterval(*SR))
 558         continue;
 559       LiveInterval &sli = li_->getInterval(*SR);
 560       SlotIndex RemoveStart = Start;
 561       SlotIndex RemoveEnd = Start;
 562
 563       while (RemoveEnd != End) {
 564         LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart);
 565         if (LR == sli.end())
 566           break;
 567         RemoveEnd = (LR->end < End) ? LR->end : End;
 568         sli.removeRange(RemoveStart, RemoveEnd, true);
 569         RemoveStart = RemoveEnd;
 570       }
 571     }
 572   }
 573 }
 574
 575 /// TrimLiveIntervalToLastUse - If there is a last use in the same basic block
 576 /// as the copy instruction, trim the live interval to the last use and return
 577 /// true.
 578 bool
 579 SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(SlotIndex CopyIdx,
 580                                                     MachineBasicBlock *CopyMBB,
 581                                                     LiveInterval &li,
 582                                                     const LiveRange *LR) {
 583   SlotIndex MBBStart = li_->getMBBStartIdx(CopyMBB);
 584   SlotIndex LastUseIdx;
 585   MachineOperand *LastUse =
 586     lastRegisterUse(LR->start, CopyIdx.getPrevSlot(), li.reg, LastUseIdx);
 587   if (LastUse) {
 588     MachineInstr *LastUseMI = LastUse->getParent();
 589     if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
 590       // r1024 = op
 591       // ...
 592       // BB1:
 593       //       = r1024
 594       //
 595       // BB2:
 596       // r1025<dead> = r1024<kill>
 597       if (MBBStart < LR->end)
 598         removeRange(li, MBBStart, LR->end, li_, tri_);
 599       return true;
 600     }
 601
 602     // There are uses before the copy, just shorten the live range to the end
 603     // of last use.
 604     LastUse->setIsKill();
 605     removeRange(li, LastUseIdx.getDefIndex(), LR->end, li_, tri_);
 606     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 607     if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
 608         DstReg == li.reg && DstSubIdx == 0) {
 609       // Last use is itself an identity code.
 610       int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg,
 611                                                          false, false, tri_);
 612       LastUseMI->getOperand(DeadIdx).setIsDead();
 613     }
 614     return true;
 615   }
 616
 617   // Is it livein?
 618   if (LR->start <= MBBStart && LR->end > MBBStart) {
 619     if (LR->start == li_->getZeroIndex()) {
 620       assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
 621       // Live-in to the function but dead. Remove it from entry live-in set.
 622       mf_->begin()->removeLiveIn(li.reg);
 623     }
 624     // FIXME: Shorten intervals in BBs that reaches this BB.
 625   }
 626
 627   return false;
 628 }
 629
 630 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
 631 /// computation, replace the copy by rematerialize the definition.
 632 bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
 633                                                        unsigned DstReg,
 634                                                        unsigned DstSubIdx,
 635                                                        MachineInstr *CopyMI) {
 636   SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getUseIndex();
 637   LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
 638   assert(SrcLR != SrcInt.end() && "Live range not found!");
 639   VNInfo *ValNo = SrcLR->valno;
 640   // If other defs can reach uses of this def, then it's not safe to perform
 641   // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be
 642   // tested?
 643   if (ValNo->isPHIDef() || !ValNo->isDefAccurate() ||
 644       ValNo->isUnused() || ValNo->hasPHIKill())
 645     return false;
 646   MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def);
 647   assert(DefMI && "Defining instruction disappeared");
 648   const TargetInstrDesc &TID = DefMI->getDesc();
 649   if (!TID.isAsCheapAsAMove())
 650     return false;
 651   if (!tii_->isTriviallyReMaterializable(DefMI, AA))
 652     return false;
 653   bool SawStore = false;
 654   if (!DefMI->isSafeToMove(tii_, AA, SawStore))
 655     return false;
 656   if (TID.getNumDefs() != 1)
 657     return false;
 658   if (!DefMI->isImplicitDef()) {
 659     // Make sure the copy destination register class fits the instruction
 660     // definition register class. The mismatch can happen as a result of earlier
 661     // extract_subreg, insert_subreg, subreg_to_reg coalescing.
 662     const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_);
 663     if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
 664       if (mri_->getRegClass(DstReg) != RC)
 665         return false;
 666     } else if (!RC->contains(DstReg))
 667       return false;
 668   }
 669
 670   // If destination register has a sub-register index on it, make sure it mtches
 671   // the instruction register class.
 672   if (DstSubIdx) {
 673     const TargetInstrDesc &TID = DefMI->getDesc();
 674     if (TID.getNumDefs() != 1)
 675       return false;
 676     const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg);
 677     const TargetRegisterClass *DstSubRC =
 678       DstRC->getSubRegisterRegClass(DstSubIdx);
 679     const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_);
 680     if (DefRC == DstRC)
 681       DstSubIdx = 0;
 682     else if (DefRC != DstSubRC)
 683       return false;
 684   }
 685
 686   RemoveCopyFlag(DstReg, CopyMI);
 687
 688   // If copy kills the source register, find the last use and propagate
 689   // kill.
 690   bool checkForDeadDef = false;
 691   MachineBasicBlock *MBB = CopyMI->getParent();
 692   if (SrcLR->end == CopyIdx.getDefIndex())
 693     if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) {
 694       checkForDeadDef = true;
 695     }
 696
 697   MachineBasicBlock::iterator MII =
 698     llvm::next(MachineBasicBlock::iterator(CopyMI));
 699   tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI, *tri_);
 700   MachineInstr *NewMI = prior(MII);
 701
 702   if (checkForDeadDef) {
 703     // PR4090 fix: Trim interval failed because there was no use of the
 704     // source interval in this MBB. If the def is in this MBB too then we
 705     // should mark it dead:
 706     if (DefMI->getParent() == MBB) {
 707       DefMI->addRegisterDead(SrcInt.reg, tri_);
 708       SrcLR->end = SrcLR->start.getNextSlot();
 709     }
 710   }
 711
 712   // CopyMI may have implicit operands, transfer them over to the newly
 713   // rematerialized instruction. And update implicit def interval valnos.
 714   for (unsigned i = CopyMI->getDesc().getNumOperands(),
 715          e = CopyMI->getNumOperands(); i != e; ++i) {
 716     MachineOperand &MO = CopyMI->getOperand(i);
 717     if (MO.isReg() && MO.isImplicit())
 718       NewMI->addOperand(MO);
 719     if (MO.isDef())
 720       RemoveCopyFlag(MO.getReg(), CopyMI);
 721   }
 722
 723   TransferImplicitOps(CopyMI, NewMI);
 724   li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
 725   CopyMI->eraseFromParent();
 726   ReMatCopies.insert(CopyMI);
 727   ReMatDefs.insert(DefMI);
 728   DEBUG(dbgs() << "Remat: " << *NewMI);
 729   ++NumReMats;
 730   return true;
 731 }
 732
 733 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 734 /// update the subregister number if it is not zero. If DstReg is a
 735 /// physical register and the existing subregister number of the def / use
 736 /// being updated is not zero, make sure to set it to the correct physical
 737 /// subregister.
 738 void
 739 SimpleRegisterCoalescing::UpdateRegDefsUses(const CoalescerPair &CP) {
 740   bool DstIsPhys = CP.isPhys();
 741   unsigned SrcReg = CP.getSrcReg();
 742   unsigned DstReg = CP.getDstReg();
 743   unsigned SubIdx = CP.getSubIdx();
 744
 745   // Collect all the instructions using SrcReg.
 746   SmallPtrSet<MachineInstr*, 32> Instrs;
 747   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
 748          E = mri_->reg_end(); I != E; ++I)
 749     Instrs.insert(&*I);
 750
 751   for (SmallPtrSet<MachineInstr*, 32>::const_iterator I = Instrs.begin(),
 752        E = Instrs.end(); I != E; ++I) {
 753     MachineInstr *UseMI = *I;
 754
 755     // A PhysReg copy that won't be coalesced can perhaps be rematerialized
 756     // instead.
 757     if (DstIsPhys) {
 758       unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
 759       if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
 760                             CopySrcSubIdx, CopyDstSubIdx) &&
 761           CopySrcSubIdx == 0 && CopyDstSubIdx == 0 &&
 762           CopySrcReg != CopyDstReg && CopySrcReg == SrcReg &&
 763           CopyDstReg != DstReg && !JoinedCopies.count(UseMI) &&
 764           ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg, 0,
 765                                   UseMI))
 766         continue;
 767     }
 768
 769     SmallVector<unsigned,8> Ops;
 770     bool Reads, Writes;
 771     tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
 772     bool Kills = false, Deads = false;
 773
 774     // Replace SrcReg with DstReg in all UseMI operands.
 775     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 776       MachineOperand &MO = UseMI->getOperand(Ops[i]);
 777       Kills |= MO.isKill();
 778       Deads |= MO.isDead();
 779
 780       if (DstIsPhys)
 781         MO.substPhysReg(DstReg, *tri_);
 782       else
 783         MO.substVirtReg(DstReg, SubIdx, *tri_);
 784     }
 785
 786     // This instruction is a copy that will be removed.
 787     if (JoinedCopies.count(UseMI))
 788       continue;
 789
 790     if (SubIdx) {
 791       // If UseMI was a simple SrcReg def, make sure we didn't turn it into a
 792       // read-modify-write of DstReg.
 793       if (Deads)
 794         UseMI->addRegisterDead(DstReg, tri_);
 795       else if (!Reads && Writes)
 796         UseMI->addRegisterDefined(DstReg, tri_);
 797
 798       // Kill flags apply to the whole physical register.
 799       if (DstIsPhys && Kills)
 800         UseMI->addRegisterKilled(DstReg, tri_);
 801     }
 802
 803     DEBUG({
 804         dbgs() << "\t\tupdated: ";
 805         if (!UseMI->isDebugValue())
 806           dbgs() << li_->getInstructionIndex(UseMI) << "\t";
 807         dbgs() << *UseMI;
 808       });
 809
 810
 811     // After updating the operand, check if the machine instruction has
 812     // become a copy. If so, update its val# information.
 813     const TargetInstrDesc &TID = UseMI->getDesc();
 814     if (DstIsPhys || TID.getNumDefs() != 1 || TID.getNumOperands() <= 2)
 815       continue;
 816
 817     unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
 818     if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
 819                           CopySrcSubIdx, CopyDstSubIdx) &&
 820         CopySrcReg != CopyDstReg &&
 821         (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
 822          allocatableRegs_[CopyDstReg])) {
 823       LiveInterval &LI = li_->getInterval(CopyDstReg);
 824       SlotIndex DefIdx =
 825         li_->getInstructionIndex(UseMI).getDefIndex();
 826       if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) {
 827         if (DLR->valno->def == DefIdx)
 828           DLR->valno->setCopy(UseMI);
 829       }
 830     }
 831   }
 832 }
 833
 834 /// removeIntervalIfEmpty - Check if the live interval of a physical register
 835 /// is empty, if so remove it and also remove the empty intervals of its
 836 /// sub-registers. Return true if live interval is removed.
 837 static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
 838                                   const TargetRegisterInfo *tri_) {
 839   if (li.empty()) {
 840     if (TargetRegisterInfo::isPhysicalRegister(li.reg))
 841       for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
 842         if (!li_->hasInterval(*SR))
 843           continue;
 844         LiveInterval &sli = li_->getInterval(*SR);
 845         if (sli.empty())
 846           li_->removeInterval(*SR);
 847       }
 848     li_->removeInterval(li.reg);
 849     return true;
 850   }
 851   return false;
 852 }
 853
 854 /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
 855 /// Return true if live interval is removed.
 856 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
 857                                                         MachineInstr *CopyMI) {
 858   SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
 859   LiveInterval::iterator MLR =
 860     li.FindLiveRangeContaining(CopyIdx.getDefIndex());
 861   if (MLR == li.end())
 862     return false;  // Already removed by ShortenDeadCopySrcLiveRange.
 863   SlotIndex RemoveStart = MLR->start;
 864   SlotIndex RemoveEnd = MLR->end;
 865   SlotIndex DefIdx = CopyIdx.getDefIndex();
 866   // Remove the liverange that's defined by this.
 867   if (RemoveStart == DefIdx && RemoveEnd == DefIdx.getStoreIndex()) {
 868     removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
 869     return removeIntervalIfEmpty(li, li_, tri_);
 870   }
 871   return false;
 872 }
 873
 874 /// RemoveDeadDef - If a def of a live interval is now determined dead, remove
 875 /// the val# it defines. If the live interval becomes empty, remove it as well.
 876 bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
 877                                              MachineInstr *DefMI) {
 878   SlotIndex DefIdx = li_->getInstructionIndex(DefMI).getDefIndex();
 879   LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
 880   if (DefIdx != MLR->valno->def)
 881     return false;
 882   li.removeValNo(MLR->valno);
 883   return removeIntervalIfEmpty(li, li_, tri_);
 884 }
 885
 886 void SimpleRegisterCoalescing::RemoveCopyFlag(unsigned DstReg,
 887                                               const MachineInstr *CopyMI) {
 888   SlotIndex DefIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
 889   if (li_->hasInterval(DstReg)) {
 890     LiveInterval &LI = li_->getInterval(DstReg);
 891     if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx))
 892       if (LR->valno->getCopy() == CopyMI)
 893         LR->valno->setCopy(0);
 894   }
 895   if (!TargetRegisterInfo::isPhysicalRegister(DstReg))
 896     return;
 897   for (const unsigned* AS = tri_->getAliasSet(DstReg); *AS; ++AS) {
 898     if (!li_->hasInterval(*AS))
 899       continue;
 900     LiveInterval &LI = li_->getInterval(*AS);
 901     if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx))
 902       if (LR->valno->getCopy() == CopyMI)
 903         LR->valno->setCopy(0);
 904   }
 905 }
 906
 907 /// PropagateDeadness - Propagate the dead marker to the instruction which
 908 /// defines the val#.
 909 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
 910                               SlotIndex &LRStart, LiveIntervals *li_,
 911                               const TargetRegisterInfo* tri_) {
 912   MachineInstr *DefMI =
 913     li_->getInstructionFromIndex(LRStart.getDefIndex());
 914   if (DefMI && DefMI != CopyMI) {
 915     int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg);
 916     if (DeadIdx != -1)
 917       DefMI->getOperand(DeadIdx).setIsDead();
 918     else
 919       DefMI->addOperand(MachineOperand::CreateReg(li.reg,
 920                    /*def*/true, /*implicit*/true, /*kill*/false, /*dead*/true));
 921     LRStart = LRStart.getNextSlot();
 922   }
 923 }
 924
 925 /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
 926 /// extended by a dead copy. Mark the last use (if any) of the val# as kill as
 927 /// ends the live range there. If there isn't another use, then this live range
 928 /// is dead. Return true if live interval is removed.
 929 bool
 930 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
 931                                                       MachineInstr *CopyMI) {
 932   SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
 933   if (CopyIdx == SlotIndex()) {
 934     // FIXME: special case: function live in. It can be a general case if the
 935     // first instruction index starts at > 0 value.
 936     assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
 937     // Live-in to the function but dead. Remove it from entry live-in set.
 938     if (mf_->begin()->isLiveIn(li.reg))
 939       mf_->begin()->removeLiveIn(li.reg);
 940     const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
 941     removeRange(li, LR->start, LR->end, li_, tri_);
 942     return removeIntervalIfEmpty(li, li_, tri_);
 943   }
 944
 945   LiveInterval::iterator LR =
 946     li.FindLiveRangeContaining(CopyIdx.getPrevIndex().getStoreIndex());
 947   if (LR == li.end())
 948     // Livein but defined by a phi.
 949     return false;
 950
 951   SlotIndex RemoveStart = LR->start;
 952   SlotIndex RemoveEnd = CopyIdx.getStoreIndex();
 953   if (LR->end > RemoveEnd)
 954     // More uses past this copy? Nothing to do.
 955     return false;
 956
 957   // If there is a last use in the same bb, we can't remove the live range.
 958   // Shorten the live interval and return.
 959   MachineBasicBlock *CopyMBB = CopyMI->getParent();
 960   if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR))
 961     return false;
 962
 963   // There are other kills of the val#. Nothing to do.
 964   if (!li.isOnlyLROfValNo(LR))
 965     return false;
 966
 967   MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart);
 968   if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_))
 969     // If the live range starts in another mbb and the copy mbb is not a fall
 970     // through mbb, then we can only cut the range from the beginning of the
 971     // copy mbb.
 972     RemoveStart = li_->getMBBStartIdx(CopyMBB).getNextIndex().getBaseIndex();
 973
 974   if (LR->valno->def == RemoveStart) {
 975     // If the def MI defines the val# and this copy is the only kill of the
 976     // val#, then propagate the dead marker.
 977     PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
 978     ++numDeadValNo;
 979   }
 980
 981   removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
 982   return removeIntervalIfEmpty(li, li_, tri_);
 983 }
 984
 985
 986 /// isWinToJoinCrossClass - Return true if it's profitable to coalesce
 987 /// two virtual registers from different register classes.
 988 bool
 989 SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned SrcReg,
 990                                                 unsigned DstReg,
 991                                              const TargetRegisterClass *SrcRC,
 992                                              const TargetRegisterClass *DstRC,
 993                                              const TargetRegisterClass *NewRC) {
 994   unsigned NewRCCount = allocatableRCRegs_[NewRC].count();
 995   // This heuristics is good enough in practice, but it's obviously not *right*.
 996   // 4 is a magic number that works well enough for x86, ARM, etc. It filter
 997   // out all but the most restrictive register classes.
 998   if (NewRCCount > 4 ||
 999       // Early exit if the function is fairly small, coalesce aggressively if
1000       // that's the case. For really special register classes with 3 or
1001       // fewer registers, be a bit more careful.
1002       (li_->getFuncInstructionCount() / NewRCCount) < 8)
1003     return true;
1004   LiveInterval &SrcInt = li_->getInterval(SrcReg);
1005   LiveInterval &DstInt = li_->getInterval(DstReg);
1006   unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt);
1007   unsigned DstSize = li_->getApproximateInstructionCount(DstInt);
1008   if (SrcSize <= NewRCCount && DstSize <= NewRCCount)
1009     return true;
1010   // Estimate *register use density*. If it doubles or more, abort.
1011   unsigned SrcUses = std::distance(mri_->use_nodbg_begin(SrcReg),
1012                                    mri_->use_nodbg_end());
1013   unsigned DstUses = std::distance(mri_->use_nodbg_begin(DstReg),
1014                                    mri_->use_nodbg_end());
1015   unsigned NewUses = SrcUses + DstUses;
1016   unsigned NewSize = SrcSize + DstSize;
1017   if (SrcRC != NewRC && SrcSize > NewRCCount) {
1018     unsigned SrcRCCount = allocatableRCRegs_[SrcRC].count();
1019     if (NewUses*SrcSize*SrcRCCount > 2*SrcUses*NewSize*NewRCCount)
1020       return false;
1021   }
1022   if (DstRC != NewRC && DstSize > NewRCCount) {
1023     unsigned DstRCCount = allocatableRCRegs_[DstRC].count();
1024     if (NewUses*DstSize*DstRCCount > 2*DstUses*NewSize*NewRCCount)
1025       return false;
1026   }
1027   return true;
1028 }
1029
1030
1031 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
1032 /// which are the src/dst of the copy instruction CopyMI.  This returns true
1033 /// if the copy was successfully coalesced away. If it is not currently
1034 /// possible to coalesce this interval, but it may be possible if other
1035 /// things get coalesced, then it returns true by reference in 'Again'.
1036 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
1037   MachineInstr *CopyMI = TheCopy.MI;
1038
1039   Again = false;
1040   if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI))
1041     return false; // Already done.
1042
1043   DEBUG(dbgs() << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI);
1044
1045   CoalescerPair CP(*tii_, *tri_);
1046   if (!CP.setRegisters(CopyMI)) {
1047     DEBUG(dbgs() << "\tNot coalescable.\n");
1048     return false;
1049   }
1050
1051   // If they are already joined we continue.
1052   if (CP.getSrcReg() == CP.getDstReg()) {
1053     DEBUG(dbgs() << "\tCopy already coalesced.\n");
1054     return false;  // Not coalescable.
1055   }
1056
1057   DEBUG(dbgs() << "\tConsidering merging %reg" << CP.getSrcReg());
1058
1059   // Enforce policies.
1060   if (CP.isPhys()) {
1061     DEBUG(dbgs() <<" with physreg %" << tri_->getName(CP.getDstReg()) << "\n");
1062     // Only coalesce to allocatable physreg.
1063     if (!allocatableRegs_[CP.getDstReg()]) {
1064       DEBUG(dbgs() << "\tRegister is an unallocatable physreg.\n");
1065       return false;  // Not coalescable.
1066     }
1067   } else {
1068     DEBUG({
1069       dbgs() << " with reg%" << CP.getDstReg();
1070       if (CP.getSubIdx())
1071         dbgs() << ":" << tri_->getSubRegIndexName(CP.getSubIdx());
1072       dbgs() << " to " << CP.getNewRC()->getName() << "\n";
1073     });
1074
1075     // Avoid constraining virtual register regclass too much.
1076     if (CP.isCrossClass()) {
1077       if (DisableCrossClassJoin) {
1078         DEBUG(dbgs() << "\tCross-class joins disabled.\n");
1079         return false;
1080       }
1081       if (!isWinToJoinCrossClass(CP.getSrcReg(), CP.getDstReg(),
1082                                  mri_->getRegClass(CP.getSrcReg()),
1083                                  mri_->getRegClass(CP.getDstReg()),
1084                                  CP.getNewRC())) {
1085         DEBUG(dbgs() << "\tAvoid coalescing to constrained register class: "
1086                      << CP.getNewRC()->getName() << ".\n");
1087         Again = true;  // May be possible to coalesce later.
1088         return false;
1089       }
1090     }
1091
1092     // When possible, let DstReg be the larger interval.
1093     if (!CP.getSubIdx() && li_->getInterval(CP.getSrcReg()).ranges.size() >
1094                            li_->getInterval(CP.getDstReg()).ranges.size())
1095       CP.flip();
1096   }
1097
1098   // We need to be careful about coalescing a source physical register with a
1099   // virtual register. Once the coalescing is done, it cannot be broken and
1100   // these are not spillable! If the destination interval uses are far away,
1101   // think twice about coalescing them!
1102   // FIXME: Why are we skipping this test for partial copies?
1103   //        CodeGen/X86/phys_subreg_coalesce-3.ll needs it.
1104   if (!CP.isPartial() && CP.isPhys()) {
1105     LiveInterval &JoinVInt = li_->getInterval(CP.getSrcReg());
1106
1107     // Don't join with physregs that have a ridiculous number of live
1108     // ranges. The data structure performance is really bad when that
1109     // happens.
1110     if (li_->hasInterval(CP.getDstReg()) &&
1111         li_->getInterval(CP.getDstReg()).ranges.size() > 1000) {
1112       mri_->setRegAllocationHint(CP.getSrcReg(), 0, CP.getDstReg());
1113       ++numAborts;
1114       DEBUG(dbgs()
1115            << "\tPhysical register live interval too complicated, abort!\n");
1116       return false;
1117     }
1118
1119     const TargetRegisterClass *RC = mri_->getRegClass(CP.getSrcReg());
1120     unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
1121     unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
1122     if (Length > Threshold &&
1123         std::distance(mri_->use_nodbg_begin(CP.getSrcReg()),
1124                       mri_->use_nodbg_end()) * Threshold < Length) {
1125       // Before giving up coalescing, if definition of source is defined by
1126       // trivial computation, try rematerializing it.
1127       if (!CP.isFlipped() &&
1128           ReMaterializeTrivialDef(JoinVInt, CP.getDstReg(), 0, CopyMI))
1129         return true;
1130
1131       mri_->setRegAllocationHint(CP.getSrcReg(), 0, CP.getDstReg());
1132       ++numAborts;
1133       DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
1134       Again = true;  // May be possible to coalesce later.
1135       return false;
1136     }
1137   }
1138
1139   // We may need the source interval after JoinIntervals has destroyed it.
1140   OwningPtr<LiveInterval> SavedLI;
1141   if (CP.getOrigDstReg() != CP.getDstReg())
1142     SavedLI.reset(li_->dupInterval(&li_->getInterval(CP.getSrcReg())));
1143
1144   // Okay, attempt to join these two intervals.  On failure, this returns false.
1145   // Otherwise, if one of the intervals being joined is a physreg, this method
1146   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
1147   // been modified, so we can use this information below to update aliases.
1148   if (!JoinIntervals(CP)) {
1149     // Coalescing failed.
1150
1151     // If definition of source is defined by trivial computation, try
1152     // rematerializing it.
1153     if (!CP.isFlipped() &&
1154         ReMaterializeTrivialDef(li_->getInterval(CP.getSrcReg()),
1155                                 CP.getDstReg(), 0, CopyMI))
1156       return true;
1157
1158     // If we can eliminate the copy without merging the live ranges, do so now.
1159     if (!CP.isPartial()) {
1160       LiveInterval *UseInt = &li_->getInterval(CP.getSrcReg());
1161       LiveInterval *DefInt = &li_->getInterval(CP.getDstReg());
1162       if (CP.isFlipped())
1163         std::swap(UseInt, DefInt);
1164       if (AdjustCopiesBackFrom(CP, CopyMI) ||
1165           RemoveCopyByCommutingDef(*UseInt, *DefInt, CopyMI)) {
1166         JoinedCopies.insert(CopyMI);
1167         DEBUG(dbgs() << "\tTrivial!\n");
1168         return true;
1169       }
1170     }
1171
1172     // Otherwise, we are unable to join the intervals.
1173     DEBUG(dbgs() << "\tInterference!\n");
1174     Again = true;  // May be possible to coalesce later.
1175     return false;
1176   }
1177
1178   if (CP.isPhys()) {
1179     // If this is a extract_subreg where dst is a physical register, e.g.
1180     // cl = EXTRACT_SUBREG reg1024, 1
1181     // then create and update the actual physical register allocated to RHS.
1182     unsigned LargerDstReg = CP.getDstReg();
1183     if (CP.getOrigDstReg() != CP.getDstReg()) {
1184       if (tri_->isSubRegister(CP.getOrigDstReg(), LargerDstReg))
1185         LargerDstReg = CP.getOrigDstReg();
1186       LiveInterval &RealInt = li_->getOrCreateInterval(CP.getDstReg());
1187       for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(),
1188              E = SavedLI->vni_end(); I != E; ++I) {
1189         const VNInfo *ValNo = *I;
1190         VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(),
1191                                                 false, // updated at *
1192                                                 li_->getVNInfoAllocator());
1193         NewValNo->setFlags(ValNo->getFlags()); // * updated here.
1194         RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo);
1195       }
1196       RealInt.weight += SavedLI->weight;
1197     }
1198
1199     // Update the liveintervals of sub-registers.
1200     LiveInterval &LargerInt = li_->getInterval(LargerDstReg);
1201     for (const unsigned *AS = tri_->getSubRegisters(LargerDstReg); *AS; ++AS) {
1202       LiveInterval &SRI = li_->getOrCreateInterval(*AS);
1203       SRI.MergeInClobberRanges(*li_, LargerInt, li_->getVNInfoAllocator());
1204       DEBUG({
1205         dbgs() << "\t\tsubreg: "; SRI.print(dbgs(), tri_); dbgs() << "\n";
1206       });
1207     }
1208   }
1209
1210   // Coalescing to a virtual register that is of a sub-register class of the
1211   // other. Make sure the resulting register is set to the right register class.
1212   if (CP.isCrossClass()) {
1213     ++numCrossRCs;
1214     mri_->setRegClass(CP.getDstReg(), CP.getNewRC());
1215   }
1216
1217   // Remember to delete the copy instruction.
1218   JoinedCopies.insert(CopyMI);
1219
1220   UpdateRegDefsUses(CP);
1221
1222   // If we have extended the live range of a physical register, make sure we
1223   // update live-in lists as well.
1224   if (CP.isPhys()) {
1225     SmallVector<MachineBasicBlock*, 16> BlockSeq;
1226     // JoinIntervals invalidates the VNInfos in SrcInt, but we only need the
1227     // ranges for this, and they are preserved.
1228     LiveInterval &SrcInt = li_->getInterval(CP.getSrcReg());
1229     for (LiveInterval::const_iterator I = SrcInt.begin(), E = SrcInt.end();
1230          I != E; ++I ) {
1231       li_->findLiveInMBBs(I->start, I->end, BlockSeq);
1232       for (unsigned idx = 0, size = BlockSeq.size(); idx != size; ++idx) {
1233         MachineBasicBlock &block = *BlockSeq[idx];
1234         if (!block.isLiveIn(CP.getDstReg()))
1235           block.addLiveIn(CP.getDstReg());
1236       }
1237       BlockSeq.clear();
1238     }
1239   }
1240
1241   // SrcReg is guarateed to be the register whose live interval that is
1242   // being merged.
1243   li_->removeInterval(CP.getSrcReg());
1244
1245   // Update regalloc hint.
1246   tri_->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *mf_);
1247
1248   DEBUG({
1249     LiveInterval &DstInt = li_->getInterval(CP.getDstReg());
1250     dbgs() << "\tJoined. Result = ";
1251     DstInt.print(dbgs(), tri_);
1252     dbgs() << "\n";
1253   });
1254
1255   ++numJoins;
1256   return true;
1257 }
1258
1259 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
1260 /// compute what the resultant value numbers for each value in the input two
1261 /// ranges will be.  This is complicated by copies between the two which can
1262 /// and will commonly cause multiple value numbers to be merged into one.
1263 ///
1264 /// VN is the value number that we're trying to resolve.  InstDefiningValue
1265 /// keeps track of the new InstDefiningValue assignment for the result
1266 /// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
1267 /// whether a value in this or other is a copy from the opposite set.
1268 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
1269 /// already been assigned.
1270 ///
1271 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
1272 /// contains the value number the copy is from.
1273 ///
1274 static unsigned ComputeUltimateVN(VNInfo *VNI,
1275                                   SmallVector<VNInfo*, 16> &NewVNInfo,
1276                                   DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
1277                                   DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
1278                                   SmallVector<int, 16> &ThisValNoAssignments,
1279                                   SmallVector<int, 16> &OtherValNoAssignments) {
1280   unsigned VN = VNI->id;
1281
1282   // If the VN has already been computed, just return it.
1283   if (ThisValNoAssignments[VN] >= 0)
1284     return ThisValNoAssignments[VN];
1285   assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers");
1286
1287   // If this val is not a copy from the other val, then it must be a new value
1288   // number in the destination.
1289   DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
1290   if (I == ThisFromOther.end()) {
1291     NewVNInfo.push_back(VNI);
1292     return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
1293   }
1294   VNInfo *OtherValNo = I->second;
1295
1296   // Otherwise, this *is* a copy from the RHS.  If the other side has already
1297   // been computed, return it.
1298   if (OtherValNoAssignments[OtherValNo->id] >= 0)
1299     return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
1300
1301   // Mark this value number as currently being computed, then ask what the
1302   // ultimate value # of the other value is.
1303   ThisValNoAssignments[VN] = -2;
1304   unsigned UltimateVN =
1305     ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
1306                       OtherValNoAssignments, ThisValNoAssignments);
1307   return ThisValNoAssignments[VN] = UltimateVN;
1308 }
1309
1310 /// JoinIntervals - Attempt to join these two intervals.  On failure, this
1311 /// returns false.
1312 bool SimpleRegisterCoalescing::JoinIntervals(CoalescerPair &CP) {
1313   LiveInterval &RHS = li_->getInterval(CP.getSrcReg());
1314   DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), tri_); dbgs() << "\n"; });
1315
1316   // FIXME: Join into CP.getDstReg instead of CP.getOrigDstReg.
1317   // When looking at
1318   //   %reg2000 = EXTRACT_SUBREG %EAX, sub_16bit
1319   // we really want to join %reg2000 with %AX ( = CP.getDstReg). We are actually
1320   // joining into %EAX ( = CP.getOrigDstReg) because it is guaranteed to have an
1321   // existing live interval, and we are better equipped to handle interference.
1322   // JoinCopy cleans up the mess by taking a copy of RHS before calling here,
1323   // and merging that copy into CP.getDstReg after.
1324
1325   // If a live interval is a physical register, conservatively check if any
1326   // of its sub-registers is overlapping the live interval of the virtual
1327   // register. If so, do not coalesce.
1328   if (CP.isPhys() && *tri_->getSubRegisters(CP.getOrigDstReg())) {
1329     // If it's coalescing a virtual register to a physical register, estimate
1330     // its live interval length. This is the *cost* of scanning an entire live
1331     // interval. If the cost is low, we'll do an exhaustive check instead.
1332
1333     // If this is something like this:
1334     // BB1:
1335     // v1024 = op
1336     // ...
1337     // BB2:
1338     // ...
1339     // RAX   = v1024
1340     //
1341     // That is, the live interval of v1024 crosses a bb. Then we can't rely on
1342     // less conservative check. It's possible a sub-register is defined before
1343     // v1024 (or live in) and live out of BB1.
1344     if (RHS.containsOneValue() &&
1345         li_->intervalIsInOneMBB(RHS) &&
1346         li_->getApproximateInstructionCount(RHS) <= 10) {
1347       // Perform a more exhaustive check for some common cases.
1348       if (li_->conflictsWithAliasRef(RHS, CP.getOrigDstReg(), JoinedCopies))
1349         return false;
1350     } else {
1351       for (const unsigned* SR = tri_->getAliasSet(CP.getOrigDstReg()); *SR;
1352            ++SR)
1353         if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
1354           DEBUG({
1355               dbgs() << "\tInterfere with sub-register ";
1356               li_->getInterval(*SR).print(dbgs(), tri_);
1357             });
1358           return false;
1359         }
1360     }
1361   }
1362
1363   // Compute the final value assignment, assuming that the live ranges can be
1364   // coalesced.
1365   SmallVector<int, 16> LHSValNoAssignments;
1366   SmallVector<int, 16> RHSValNoAssignments;
1367   DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
1368   DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
1369   SmallVector<VNInfo*, 16> NewVNInfo;
1370
1371   LiveInterval &LHS = li_->getInterval(CP.getOrigDstReg());
1372   DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), tri_); dbgs() << "\n"; });
1373
1374   // Loop over the value numbers of the LHS, seeing if any are defined from
1375   // the RHS.
1376   for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1377        i != e; ++i) {
1378     VNInfo *VNI = *i;
1379     if (VNI->isUnused() || VNI->getCopy() == 0)  // Src not defined by a copy?
1380       continue;
1381
1382     // Never join with a register that has EarlyClobber redefs.
1383     if (VNI->hasRedefByEC())
1384       return false;
1385
1386     // DstReg is known to be a register in the LHS interval.  If the src is
1387     // from the RHS interval, we can use its value #.
1388     if (!CP.isCoalescable(VNI->getCopy()))
1389       continue;
1390
1391     // Figure out the value # from the RHS.
1392     LiveRange *lr = RHS.getLiveRangeContaining(VNI->def.getPrevSlot());
1393     // The copy could be to an aliased physreg.
1394     if (!lr) continue;
1395     LHSValsDefinedFromRHS[VNI] = lr->valno;
1396   }
1397
1398   // Loop over the value numbers of the RHS, seeing if any are defined from
1399   // the LHS.
1400   for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1401        i != e; ++i) {
1402     VNInfo *VNI = *i;
1403     if (VNI->isUnused() || VNI->getCopy() == 0)  // Src not defined by a copy?
1404       continue;
1405
1406     // Never join with a register that has EarlyClobber redefs.
1407     if (VNI->hasRedefByEC())
1408       return false;
1409
1410     // DstReg is known to be a register in the RHS interval.  If the src is
1411     // from the LHS interval, we can use its value #.
1412     if (!CP.isCoalescable(VNI->getCopy()))
1413       continue;
1414
1415     // Figure out the value # from the LHS.
1416     LiveRange *lr = LHS.getLiveRangeContaining(VNI->def.getPrevSlot());
1417     // The copy could be to an aliased physreg.
1418     if (!lr) continue;
1419     RHSValsDefinedFromLHS[VNI] = lr->valno;
1420   }
1421
1422   LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1423   RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1424   NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
1425
1426   for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1427        i != e; ++i) {
1428     VNInfo *VNI = *i;
1429     unsigned VN = VNI->id;
1430     if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused())
1431       continue;
1432     ComputeUltimateVN(VNI, NewVNInfo,
1433                       LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
1434                       LHSValNoAssignments, RHSValNoAssignments);
1435   }
1436   for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1437        i != e; ++i) {
1438     VNInfo *VNI = *i;
1439     unsigned VN = VNI->id;
1440     if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused())
1441       continue;
1442     // If this value number isn't a copy from the LHS, it's a new number.
1443     if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
1444       NewVNInfo.push_back(VNI);
1445       RHSValNoAssignments[VN] = NewVNInfo.size()-1;
1446       continue;
1447     }
1448
1449     ComputeUltimateVN(VNI, NewVNInfo,
1450                       RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
1451                       RHSValNoAssignments, LHSValNoAssignments);
1452   }
1453
1454   // Armed with the mappings of LHS/RHS values to ultimate values, walk the
1455   // interval lists to see if these intervals are coalescable.
1456   LiveInterval::const_iterator I = LHS.begin();
1457   LiveInterval::const_iterator IE = LHS.end();
1458   LiveInterval::const_iterator J = RHS.begin();
1459   LiveInterval::const_iterator JE = RHS.end();
1460
1461   // Skip ahead until the first place of potential sharing.
1462   if (I != IE && J != JE) {
1463     if (I->start < J->start) {
1464       I = std::upper_bound(I, IE, J->start);
1465       if (I != LHS.begin()) --I;
1466     } else if (J->start < I->start) {
1467       J = std::upper_bound(J, JE, I->start);
1468       if (J != RHS.begin()) --J;
1469     }
1470   }
1471
1472   while (I != IE && J != JE) {
1473     // Determine if these two live ranges overlap.
1474     bool Overlaps;
1475     if (I->start < J->start) {
1476       Overlaps = I->end > J->start;
1477     } else {
1478       Overlaps = J->end > I->start;
1479     }
1480
1481     // If so, check value # info to determine if they are really different.
1482     if (Overlaps) {
1483       // If the live range overlap will map to the same value number in the
1484       // result liverange, we can still coalesce them.  If not, we can't.
1485       if (LHSValNoAssignments[I->valno->id] !=
1486           RHSValNoAssignments[J->valno->id])
1487         return false;
1488       // If it's re-defined by an early clobber somewhere in the live range,
1489       // then conservatively abort coalescing.
1490       if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC())
1491         return false;
1492     }
1493
1494     if (I->end < J->end)
1495       ++I;
1496     else
1497       ++J;
1498   }
1499
1500   // Update kill info. Some live ranges are extended due to copy coalescing.
1501   for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(),
1502          E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
1503     VNInfo *VNI = I->first;
1504     unsigned LHSValID = LHSValNoAssignments[VNI->id];
1505     if (VNI->hasPHIKill())
1506       NewVNInfo[LHSValID]->setHasPHIKill(true);
1507   }
1508
1509   // Update kill info. Some live ranges are extended due to copy coalescing.
1510   for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(),
1511          E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
1512     VNInfo *VNI = I->first;
1513     unsigned RHSValID = RHSValNoAssignments[VNI->id];
1514     if (VNI->hasPHIKill())
1515       NewVNInfo[RHSValID]->setHasPHIKill(true);
1516   }
1517
1518   if (LHSValNoAssignments.empty())
1519     LHSValNoAssignments.push_back(-1);
1520   if (RHSValNoAssignments.empty())
1521     RHSValNoAssignments.push_back(-1);
1522
1523   // If we get here, we know that we can coalesce the live ranges.  Ask the
1524   // intervals to coalesce themselves now.
1525   LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo,
1526            mri_);
1527   return true;
1528 }
1529
1530 namespace {
1531   // DepthMBBCompare - Comparison predicate that sort first based on the loop
1532   // depth of the basic block (the unsigned), and then on the MBB number.
1533   struct DepthMBBCompare {
1534     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
1535     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
1536       // Deeper loops first
1537       if (LHS.first != RHS.first)
1538         return LHS.first > RHS.first;
1539
1540       // Prefer blocks that are more connected in the CFG. This takes care of
1541       // the most difficult copies first while intervals are short.
1542       unsigned cl = LHS.second->pred_size() + LHS.second->succ_size();
1543       unsigned cr = RHS.second->pred_size() + RHS.second->succ_size();
1544       if (cl != cr)
1545         return cl > cr;
1546
1547       // As a last resort, sort by block number.
1548       return LHS.second->getNumber() < RHS.second->getNumber();
1549     }
1550   };
1551 }
1552
1553 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
1554                                                std::vector<CopyRec> &TryAgain) {
1555   DEBUG(dbgs() << MBB->getName() << ":\n");
1556
1557   std::vector<CopyRec> VirtCopies;
1558   std::vector<CopyRec> PhysCopies;
1559   std::vector<CopyRec> ImpDefCopies;
1560   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
1561        MII != E;) {
1562     MachineInstr *Inst = MII++;
1563
1564     // If this isn't a copy nor a extract_subreg, we can't join intervals.
1565     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1566     bool isInsUndef = false;
1567     if (Inst->isExtractSubreg()) {
1568       DstReg = Inst->getOperand(0).getReg();
1569       SrcReg = Inst->getOperand(1).getReg();
1570     } else if (Inst->isInsertSubreg()) {
1571       DstReg = Inst->getOperand(0).getReg();
1572       SrcReg = Inst->getOperand(2).getReg();
1573       if (Inst->getOperand(1).isUndef())
1574         isInsUndef = true;
1575     } else if (Inst->isInsertSubreg() || Inst->isSubregToReg()) {
1576       DstReg = Inst->getOperand(0).getReg();
1577       SrcReg = Inst->getOperand(2).getReg();
1578     } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1579       continue;
1580
1581     bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
1582     bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1583     if (isInsUndef ||
1584         (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()))
1585       ImpDefCopies.push_back(CopyRec(Inst, 0));
1586     else if (SrcIsPhys || DstIsPhys)
1587       PhysCopies.push_back(CopyRec(Inst, 0));
1588     else
1589       VirtCopies.push_back(CopyRec(Inst, 0));
1590   }
1591
1592   // Try coalescing implicit copies and insert_subreg <undef> first,
1593   // followed by copies to / from physical registers, then finally copies
1594   // from virtual registers to virtual registers.
1595   for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) {
1596     CopyRec &TheCopy = ImpDefCopies[i];
1597     bool Again = false;
1598     if (!JoinCopy(TheCopy, Again))
1599       if (Again)
1600         TryAgain.push_back(TheCopy);
1601   }
1602   for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) {
1603     CopyRec &TheCopy = PhysCopies[i];
1604     bool Again = false;
1605     if (!JoinCopy(TheCopy, Again))
1606       if (Again)
1607         TryAgain.push_back(TheCopy);
1608   }
1609   for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) {
1610     CopyRec &TheCopy = VirtCopies[i];
1611     bool Again = false;
1612     if (!JoinCopy(TheCopy, Again))
1613       if (Again)
1614         TryAgain.push_back(TheCopy);
1615   }
1616 }
1617
1618 void SimpleRegisterCoalescing::joinIntervals() {
1619   DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
1620
1621   std::vector<CopyRec> TryAgainList;
1622   if (loopInfo->empty()) {
1623     // If there are no loops in the function, join intervals in function order.
1624     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
1625          I != E; ++I)
1626       CopyCoalesceInMBB(I, TryAgainList);
1627   } else {
1628     // Otherwise, join intervals in inner loops before other intervals.
1629     // Unfortunately we can't just iterate over loop hierarchy here because
1630     // there may be more MBB's than BB's.  Collect MBB's for sorting.
1631
1632     // Join intervals in the function prolog first. We want to join physical
1633     // registers with virtual registers before the intervals got too long.
1634     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
1635     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){
1636       MachineBasicBlock *MBB = I;
1637       MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I));
1638     }
1639
1640     // Sort by loop depth.
1641     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
1642
1643     // Finally, join intervals in loop nest order.
1644     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
1645       CopyCoalesceInMBB(MBBs[i].second, TryAgainList);
1646   }
1647
1648   // Joining intervals can allow other intervals to be joined.  Iteratively join
1649   // until we make no progress.
1650   bool ProgressMade = true;
1651   while (ProgressMade) {
1652     ProgressMade = false;
1653
1654     for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
1655       CopyRec &TheCopy = TryAgainList[i];
1656       if (!TheCopy.MI)
1657         continue;
1658
1659       bool Again = false;
1660       bool Success = JoinCopy(TheCopy, Again);
1661       if (Success || !Again) {
1662         TheCopy.MI = 0;   // Mark this one as done.
1663         ProgressMade = true;
1664       }
1665     }
1666   }
1667 }
1668
1669 /// Return true if the two specified registers belong to different register
1670 /// classes.  The registers may be either phys or virt regs.
1671 bool
1672 SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
1673                                                    unsigned RegB) const {
1674   // Get the register classes for the first reg.
1675   if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
1676     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1677            "Shouldn't consider two physregs!");
1678     return !mri_->getRegClass(RegB)->contains(RegA);
1679   }
1680
1681   // Compare against the regclass for the second reg.
1682   const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA);
1683   if (TargetRegisterInfo::isVirtualRegister(RegB)) {
1684     const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB);
1685     return RegClassA != RegClassB;
1686   }
1687   return !RegClassA->contains(RegB);
1688 }
1689
1690 /// lastRegisterUse - Returns the last (non-debug) use of the specific register
1691 /// between cycles Start and End or NULL if there are no uses.
1692 MachineOperand *
1693 SimpleRegisterCoalescing::lastRegisterUse(SlotIndex Start,
1694                                           SlotIndex End,
1695                                           unsigned Reg,
1696                                           SlotIndex &UseIdx) const{
1697   UseIdx = SlotIndex();
1698   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1699     MachineOperand *LastUse = NULL;
1700     for (MachineRegisterInfo::use_nodbg_iterator I = mri_->use_nodbg_begin(Reg),
1701            E = mri_->use_nodbg_end(); I != E; ++I) {
1702       MachineOperand &Use = I.getOperand();
1703       MachineInstr *UseMI = Use.getParent();
1704       unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1705       if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
1706           SrcReg == DstReg && SrcSubIdx == DstSubIdx)
1707         // Ignore identity copies.
1708         continue;
1709       SlotIndex Idx = li_->getInstructionIndex(UseMI);
1710       // FIXME: Should this be Idx != UseIdx? SlotIndex() will return something
1711       // that compares higher than any other interval.
1712       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
1713         LastUse = &Use;
1714         UseIdx = Idx.getUseIndex();
1715       }
1716     }
1717     return LastUse;
1718   }
1719
1720   SlotIndex s = Start;
1721   SlotIndex e = End.getPrevSlot().getBaseIndex();
1722   while (e >= s) {
1723     // Skip deleted instructions
1724     MachineInstr *MI = li_->getInstructionFromIndex(e);
1725     while (e != SlotIndex() && e.getPrevIndex() >= s && !MI) {
1726       e = e.getPrevIndex();
1727       MI = li_->getInstructionFromIndex(e);
1728     }
1729     if (e < s || MI == NULL)
1730       return NULL;
1731
1732     // Ignore identity copies.
1733     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1734     if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
1735           SrcReg == DstReg && SrcSubIdx == DstSubIdx))
1736       for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
1737         MachineOperand &Use = MI->getOperand(i);
1738         if (Use.isReg() && Use.isUse() && Use.getReg() &&
1739             tri_->regsOverlap(Use.getReg(), Reg)) {
1740           UseIdx = e.getUseIndex();
1741           return &Use;
1742         }
1743       }
1744
1745     e = e.getPrevIndex();
1746   }
1747
1748   return NULL;
1749 }
1750
1751 void SimpleRegisterCoalescing::releaseMemory() {
1752   JoinedCopies.clear();
1753   ReMatCopies.clear();
1754   ReMatDefs.clear();
1755 }
1756
1757 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
1758   mf_ = &fn;
1759   mri_ = &fn.getRegInfo();
1760   tm_ = &fn.getTarget();
1761   tri_ = tm_->getRegisterInfo();
1762   tii_ = tm_->getInstrInfo();
1763   li_ = &getAnalysis<LiveIntervals>();
1764   AA = &getAnalysis<AliasAnalysis>();
1765   loopInfo = &getAnalysis<MachineLoopInfo>();
1766
1767   DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
1768                << "********** Function: "
1769                << ((Value*)mf_->getFunction())->getName() << '\n');
1770
1771   allocatableRegs_ = tri_->getAllocatableSet(fn);
1772   for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(),
1773          E = tri_->regclass_end(); I != E; ++I)
1774     allocatableRCRegs_.insert(std::make_pair(*I,
1775                                              tri_->getAllocatableSet(fn, *I)));
1776
1777   // Join (coalesce) intervals if requested.
1778   if (EnableJoining) {
1779     joinIntervals();
1780     DEBUG({
1781         dbgs() << "********** INTERVALS POST JOINING **********\n";
1782         for (LiveIntervals::iterator I = li_->begin(), E = li_->end();
1783              I != E; ++I){
1784           I->second->print(dbgs(), tri_);
1785           dbgs() << "\n";
1786         }
1787       });
1788   }
1789
1790   // Perform a final pass over the instructions and compute spill weights
1791   // and remove identity moves.
1792   SmallVector<unsigned, 4> DeadDefs;
1793   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
1794        mbbi != mbbe; ++mbbi) {
1795     MachineBasicBlock* mbb = mbbi;
1796     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
1797          mii != mie; ) {
1798       MachineInstr *MI = mii;
1799       unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1800       if (JoinedCopies.count(MI)) {
1801         // Delete all coalesced copies.
1802         bool DoDelete = true;
1803         if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
1804           assert((MI->isExtractSubreg() || MI->isInsertSubreg() ||
1805                   MI->isSubregToReg()) && "Unrecognized copy instruction");
1806           SrcReg = MI->getOperand(MI->isSubregToReg() ? 2 : 1).getReg();
1807           if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
1808             // Do not delete extract_subreg, insert_subreg of physical
1809             // registers unless the definition is dead. e.g.
1810             // %DO<def> = INSERT_SUBREG %D0<undef>, %S0<kill>, 1
1811             // or else the scavenger may complain. LowerSubregs will
1812             // delete them later.
1813             DoDelete = false;
1814         }
1815         if (MI->allDefsAreDead()) {
1816           LiveInterval &li = li_->getInterval(SrcReg);
1817           if (!ShortenDeadCopySrcLiveRange(li, MI))
1818             ShortenDeadCopyLiveRange(li, MI);
1819           DoDelete = true;
1820         }
1821         if (!DoDelete)
1822           mii = llvm::next(mii);
1823         else {
1824           li_->RemoveMachineInstrFromMaps(MI);
1825           mii = mbbi->erase(mii);
1826           ++numPeep;
1827         }
1828         continue;
1829       }
1830
1831       // Now check if this is a remat'ed def instruction which is now dead.
1832       if (ReMatDefs.count(MI)) {
1833         bool isDead = true;
1834         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1835           const MachineOperand &MO = MI->getOperand(i);
1836           if (!MO.isReg())
1837             continue;
1838           unsigned Reg = MO.getReg();
1839           if (!Reg)
1840             continue;
1841           if (TargetRegisterInfo::isVirtualRegister(Reg))
1842             DeadDefs.push_back(Reg);
1843           if (MO.isDead())
1844             continue;
1845           if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
1846               !mri_->use_nodbg_empty(Reg)) {
1847             isDead = false;
1848             break;
1849           }
1850         }
1851         if (isDead) {
1852           while (!DeadDefs.empty()) {
1853             unsigned DeadDef = DeadDefs.back();
1854             DeadDefs.pop_back();
1855             RemoveDeadDef(li_->getInterval(DeadDef), MI);
1856           }
1857           li_->RemoveMachineInstrFromMaps(mii);
1858           mii = mbbi->erase(mii);
1859           continue;
1860         } else
1861           DeadDefs.clear();
1862       }
1863
1864       // If the move will be an identity move delete it
1865       bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
1866       if (isMove && SrcReg == DstReg && SrcSubIdx == DstSubIdx) {
1867         if (li_->hasInterval(SrcReg)) {
1868           LiveInterval &RegInt = li_->getInterval(SrcReg);
1869           // If def of this move instruction is dead, remove its live range
1870           // from the destination register's live interval.
1871           if (MI->allDefsAreDead()) {
1872             if (!ShortenDeadCopySrcLiveRange(RegInt, MI))
1873               ShortenDeadCopyLiveRange(RegInt, MI);
1874           }
1875         }
1876         li_->RemoveMachineInstrFromMaps(MI);
1877         mii = mbbi->erase(mii);
1878         ++numPeep;
1879         continue;
1880       }
1881
1882       ++mii;
1883
1884       // Check for now unnecessary kill flags.
1885       if (li_->isNotInMIMap(MI)) continue;
1886       SlotIndex DefIdx = li_->getInstructionIndex(MI).getDefIndex();
1887       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1888         MachineOperand &MO = MI->getOperand(i);
1889         if (!MO.isReg() || !MO.isKill()) continue;
1890         unsigned reg = MO.getReg();
1891         if (!reg || !li_->hasInterval(reg)) continue;
1892         if (!li_->getInterval(reg).killedAt(DefIdx))
1893           MO.setIsKill(false);
1894       }
1895     }
1896   }
1897
1898   DEBUG(dump());
1899   return true;
1900 }
1901
1902 /// print - Implement the dump method.
1903 void SimpleRegisterCoalescing::print(raw_ostream &O, const Module* m) const {
1904    li_->print(O, m);
1905 }
1906
1907 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() {
1908   return new SimpleRegisterCoalescing();
1909 }
1910
1911 // Make sure that anything that uses RegisterCoalescer pulls in this file...
1912 DEFINING_FILE_FOR(SimpleRegisterCoalescing)