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