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