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   assert(DefMI && "Defining instruction disappeared");
 667   const TargetInstrDesc &TID = DefMI->getDesc();
 668   if (!TID.isAsCheapAsAMove())
 669     return false;
 670   if (!tii_->isTriviallyReMaterializable(DefMI, AA))
 671     return false;
 672   bool SawStore = false;
 673   if (!DefMI->isSafeToMove(tii_, AA, SawStore))
 674     return false;
 675   if (TID.getNumDefs() != 1)
 676     return false;
 677   if (!DefMI->isImplicitDef()) {
 678     // Make sure the copy destination register class fits the instruction
 679     // definition register class. The mismatch can happen as a result of earlier
 680     // extract_subreg, insert_subreg, subreg_to_reg coalescing.
 681     const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_);
 682     if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
 683       if (mri_->getRegClass(DstReg) != RC)
 684         return false;
 685     } else if (!RC->contains(DstReg))
 686       return false;
 687   }
 688
 689   // If destination register has a sub-register index on it, make sure it mtches
 690   // the instruction register class.
 691   if (DstSubIdx) {
 692     const TargetInstrDesc &TID = DefMI->getDesc();
 693     if (TID.getNumDefs() != 1)
 694       return false;
 695     const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg);
 696     const TargetRegisterClass *DstSubRC =
 697       DstRC->getSubRegisterRegClass(DstSubIdx);
 698     const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_);
 699     if (DefRC == DstRC)
 700       DstSubIdx = 0;
 701     else if (DefRC != DstSubRC)
 702       return false;
 703   }
 704
 705   RemoveCopyFlag(DstReg, CopyMI);
 706
 707   // If copy kills the source register, find the last use and propagate
 708   // kill.
 709   bool checkForDeadDef = false;
 710   MachineBasicBlock *MBB = CopyMI->getParent();
 711   if (SrcLR->valno->isKill(CopyIdx.getDefIndex()))
 712     if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) {
 713       checkForDeadDef = true;
 714     }
 715
 716   MachineBasicBlock::iterator MII =
 717     llvm::next(MachineBasicBlock::iterator(CopyMI));
 718   tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI, *tri_);
 719   MachineInstr *NewMI = prior(MII);
 720
 721   if (checkForDeadDef) {
 722     // PR4090 fix: Trim interval failed because there was no use of the
 723     // source interval in this MBB. If the def is in this MBB too then we
 724     // should mark it dead:
 725     if (DefMI->getParent() == MBB) {
 726       DefMI->addRegisterDead(SrcInt.reg, tri_);
 727       SrcLR->end = SrcLR->start.getNextSlot();
 728     }
 729   }
 730
 731   // CopyMI may have implicit operands, transfer them over to the newly
 732   // rematerialized instruction. And update implicit def interval valnos.
 733   for (unsigned i = CopyMI->getDesc().getNumOperands(),
 734          e = CopyMI->getNumOperands(); i != e; ++i) {
 735     MachineOperand &MO = CopyMI->getOperand(i);
 736     if (MO.isReg() && MO.isImplicit())
 737       NewMI->addOperand(MO);
 738     if (MO.isDef())
 739       RemoveCopyFlag(MO.getReg(), CopyMI);
 740   }
 741
 742   TransferImplicitOps(CopyMI, NewMI);
 743   li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
 744   CopyMI->eraseFromParent();
 745   ReMatCopies.insert(CopyMI);
 746   ReMatDefs.insert(DefMI);
 747   DEBUG(dbgs() << "Remat: " << *NewMI);
 748   ++NumReMats;
 749   return true;
 750 }
 751
 752 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 753 /// update the subregister number if it is not zero. If DstReg is a
 754 /// physical register and the existing subregister number of the def / use
 755 /// being updated is not zero, make sure to set it to the correct physical
 756 /// subregister.
 757 void
 758 SimpleRegisterCoalescing::UpdateRegDefsUses(const CoalescerPair &CP) {
 759   bool DstIsPhys = CP.isPhys();
 760   unsigned SrcReg = CP.getSrcReg();
 761   unsigned DstReg = CP.getDstReg();
 762   unsigned SubIdx = CP.getSubIdx();
 763
 764   // Collect all the instructions using SrcReg.
 765   SmallPtrSet<MachineInstr*, 32> Instrs;
 766   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
 767          E = mri_->reg_end(); I != E; ++I)
 768     Instrs.insert(&*I);
 769
 770   for (SmallPtrSet<MachineInstr*, 32>::const_iterator I = Instrs.begin(),
 771        E = Instrs.end(); I != E; ++I) {
 772     MachineInstr *UseMI = *I;
 773
 774     // A PhysReg copy that won't be coalesced can perhaps be rematerialized
 775     // instead.
 776     if (DstIsPhys) {
 777       unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
 778       if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
 779                             CopySrcSubIdx, CopyDstSubIdx) &&
 780           CopySrcSubIdx == 0 && CopyDstSubIdx == 0 &&
 781           CopySrcReg != CopyDstReg && CopySrcReg == SrcReg &&
 782           CopyDstReg != DstReg && !JoinedCopies.count(UseMI) &&
 783           ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg, 0,
 784                                   UseMI))
 785         continue;
 786     }
 787
 788     SmallVector<unsigned,8> Ops;
 789     bool Reads, Writes;
 790     tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
 791     bool Kills = false, Deads = false;
 792
 793     // Replace SrcReg with DstReg in all UseMI operands.
 794     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 795       MachineOperand &MO = UseMI->getOperand(Ops[i]);
 796       Kills |= MO.isKill();
 797       Deads |= MO.isDead();
 798
 799       if (DstIsPhys)
 800         MO.substPhysReg(DstReg, *tri_);
 801       else
 802         MO.substVirtReg(DstReg, SubIdx, *tri_);
 803     }
 804
 805     // This instruction is a copy that will be removed.
 806     if (JoinedCopies.count(UseMI))
 807       continue;
 808
 809     if (SubIdx) {
 810       // If UseMI was a simple SrcReg def, make sure we didn't turn it into a
 811       // read-modify-write of DstReg.
 812       if (Deads)
 813         UseMI->addRegisterDead(DstReg, tri_);
 814       else if (!Reads && Writes)
 815         UseMI->addRegisterDefined(DstReg, tri_);
 816
 817       // Kill flags apply to the whole physical register.
 818       if (DstIsPhys && Kills)
 819         UseMI->addRegisterKilled(DstReg, tri_);
 820     }
 821
 822     DEBUG({
 823         dbgs() << "\t\tupdated: ";
 824         if (!UseMI->isDebugValue())
 825           dbgs() << li_->getInstructionIndex(UseMI) << "\t";
 826         dbgs() << *UseMI;
 827       });
 828
 829
 830     // After updating the operand, check if the machine instruction has
 831     // become a copy. If so, update its val# information.
 832     const TargetInstrDesc &TID = UseMI->getDesc();
 833     if (DstIsPhys || TID.getNumDefs() != 1 || TID.getNumOperands() <= 2)
 834       continue;
 835
 836     unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
 837     if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
 838                           CopySrcSubIdx, CopyDstSubIdx) &&
 839         CopySrcReg != CopyDstReg &&
 840         (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
 841          allocatableRegs_[CopyDstReg])) {
 842       LiveInterval &LI = li_->getInterval(CopyDstReg);
 843       SlotIndex DefIdx =
 844         li_->getInstructionIndex(UseMI).getDefIndex();
 845       if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) {
 846         if (DLR->valno->def == DefIdx)
 847           DLR->valno->setCopy(UseMI);
 848       }
 849     }
 850   }
 851 }
 852
 853 /// removeIntervalIfEmpty - Check if the live interval of a physical register
 854 /// is empty, if so remove it and also remove the empty intervals of its
 855 /// sub-registers. Return true if live interval is removed.
 856 static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
 857                                   const TargetRegisterInfo *tri_) {
 858   if (li.empty()) {
 859     if (TargetRegisterInfo::isPhysicalRegister(li.reg))
 860       for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
 861         if (!li_->hasInterval(*SR))
 862           continue;
 863         LiveInterval &sli = li_->getInterval(*SR);
 864         if (sli.empty())
 865           li_->removeInterval(*SR);
 866       }
 867     li_->removeInterval(li.reg);
 868     return true;
 869   }
 870   return false;
 871 }
 872
 873 /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
 874 /// Return true if live interval is removed.
 875 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
 876                                                         MachineInstr *CopyMI) {
 877   SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
 878   LiveInterval::iterator MLR =
 879     li.FindLiveRangeContaining(CopyIdx.getDefIndex());
 880   if (MLR == li.end())
 881     return false;  // Already removed by ShortenDeadCopySrcLiveRange.
 882   SlotIndex RemoveStart = MLR->start;
 883   SlotIndex RemoveEnd = MLR->end;
 884   SlotIndex DefIdx = CopyIdx.getDefIndex();
 885   // Remove the liverange that's defined by this.
 886   if (RemoveStart == DefIdx && RemoveEnd == DefIdx.getStoreIndex()) {
 887     removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
 888     return removeIntervalIfEmpty(li, li_, tri_);
 889   }
 890   return false;
 891 }
 892
 893 /// RemoveDeadDef - If a def of a live interval is now determined dead, remove
 894 /// the val# it defines. If the live interval becomes empty, remove it as well.
 895 bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
 896                                              MachineInstr *DefMI) {
 897   SlotIndex DefIdx = li_->getInstructionIndex(DefMI).getDefIndex();
 898   LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
 899   if (DefIdx != MLR->valno->def)
 900     return false;
 901   li.removeValNo(MLR->valno);
 902   return removeIntervalIfEmpty(li, li_, tri_);
 903 }
 904
 905 void SimpleRegisterCoalescing::RemoveCopyFlag(unsigned DstReg,
 906                                               const MachineInstr *CopyMI) {
 907   SlotIndex DefIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
 908   if (li_->hasInterval(DstReg)) {
 909     LiveInterval &LI = li_->getInterval(DstReg);
 910     if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx))
 911       if (LR->valno->getCopy() == CopyMI)
 912         LR->valno->setCopy(0);
 913   }
 914   if (!TargetRegisterInfo::isPhysicalRegister(DstReg))
 915     return;
 916   for (const unsigned* AS = tri_->getAliasSet(DstReg); *AS; ++AS) {
 917     if (!li_->hasInterval(*AS))
 918       continue;
 919     LiveInterval &LI = li_->getInterval(*AS);
 920     if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx))
 921       if (LR->valno->getCopy() == CopyMI)
 922         LR->valno->setCopy(0);
 923   }
 924 }
 925
 926 /// PropagateDeadness - Propagate the dead marker to the instruction which
 927 /// defines the val#.
 928 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
 929                               SlotIndex &LRStart, LiveIntervals *li_,
 930                               const TargetRegisterInfo* tri_) {
 931   MachineInstr *DefMI =
 932     li_->getInstructionFromIndex(LRStart.getDefIndex());
 933   if (DefMI && DefMI != CopyMI) {
 934     int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg);
 935     if (DeadIdx != -1)
 936       DefMI->getOperand(DeadIdx).setIsDead();
 937     else
 938       DefMI->addOperand(MachineOperand::CreateReg(li.reg,
 939                    /*def*/true, /*implicit*/true, /*kill*/false, /*dead*/true));
 940     LRStart = LRStart.getNextSlot();
 941   }
 942 }
 943
 944 /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
 945 /// extended by a dead copy. Mark the last use (if any) of the val# as kill as
 946 /// ends the live range there. If there isn't another use, then this live range
 947 /// is dead. Return true if live interval is removed.
 948 bool
 949 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
 950                                                       MachineInstr *CopyMI) {
 951   SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
 952   if (CopyIdx == SlotIndex()) {
 953     // FIXME: special case: function live in. It can be a general case if the
 954     // first instruction index starts at > 0 value.
 955     assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
 956     // Live-in to the function but dead. Remove it from entry live-in set.
 957     if (mf_->begin()->isLiveIn(li.reg))
 958       mf_->begin()->removeLiveIn(li.reg);
 959     const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
 960     removeRange(li, LR->start, LR->end, li_, tri_);
 961     return removeIntervalIfEmpty(li, li_, tri_);
 962   }
 963
 964   LiveInterval::iterator LR =
 965     li.FindLiveRangeContaining(CopyIdx.getPrevIndex().getStoreIndex());
 966   if (LR == li.end())
 967     // Livein but defined by a phi.
 968     return false;
 969
 970   SlotIndex RemoveStart = LR->start;
 971   SlotIndex RemoveEnd = CopyIdx.getStoreIndex();
 972   if (LR->end > RemoveEnd)
 973     // More uses past this copy? Nothing to do.
 974     return false;
 975
 976   // If there is a last use in the same bb, we can't remove the live range.
 977   // Shorten the live interval and return.
 978   MachineBasicBlock *CopyMBB = CopyMI->getParent();
 979   if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR))
 980     return false;
 981
 982   // There are other kills of the val#. Nothing to do.
 983   if (!li.isOnlyLROfValNo(LR))
 984     return false;
 985
 986   MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart);
 987   if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_))
 988     // If the live range starts in another mbb and the copy mbb is not a fall
 989     // through mbb, then we can only cut the range from the beginning of the
 990     // copy mbb.
 991     RemoveStart = li_->getMBBStartIdx(CopyMBB).getNextIndex().getBaseIndex();
 992
 993   if (LR->valno->def == RemoveStart) {
 994     // If the def MI defines the val# and this copy is the only kill of the
 995     // val#, then propagate the dead marker.
 996     PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
 997     ++numDeadValNo;
 998
 999     if (LR->valno->isKill(RemoveEnd))
1000       LR->valno->removeKill(RemoveEnd);
1001   }
1002
1003   removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
1004   return removeIntervalIfEmpty(li, li_, tri_);
1005 }
1006
1007
1008 /// isWinToJoinCrossClass - Return true if it's profitable to coalesce
1009 /// two virtual registers from different register classes.
1010 bool
1011 SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned SrcReg,
1012                                                 unsigned DstReg,
1013                                              const TargetRegisterClass *SrcRC,
1014                                              const TargetRegisterClass *DstRC,
1015                                              const TargetRegisterClass *NewRC) {
1016   unsigned NewRCCount = allocatableRCRegs_[NewRC].count();
1017   // This heuristics is good enough in practice, but it's obviously not *right*.
1018   // 4 is a magic number that works well enough for x86, ARM, etc. It filter
1019   // out all but the most restrictive register classes.
1020   if (NewRCCount > 4 ||
1021       // Early exit if the function is fairly small, coalesce aggressively if
1022       // that's the case. For really special register classes with 3 or
1023       // fewer registers, be a bit more careful.
1024       (li_->getFuncInstructionCount() / NewRCCount) < 8)
1025     return true;
1026   LiveInterval &SrcInt = li_->getInterval(SrcReg);
1027   LiveInterval &DstInt = li_->getInterval(DstReg);
1028   unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt);
1029   unsigned DstSize = li_->getApproximateInstructionCount(DstInt);
1030   if (SrcSize <= NewRCCount && DstSize <= NewRCCount)
1031     return true;
1032   // Estimate *register use density*. If it doubles or more, abort.
1033   unsigned SrcUses = std::distance(mri_->use_nodbg_begin(SrcReg),
1034                                    mri_->use_nodbg_end());
1035   unsigned DstUses = std::distance(mri_->use_nodbg_begin(DstReg),
1036                                    mri_->use_nodbg_end());
1037   unsigned NewUses = SrcUses + DstUses;
1038   unsigned NewSize = SrcSize + DstSize;
1039   if (SrcRC != NewRC && SrcSize > NewRCCount) {
1040     unsigned SrcRCCount = allocatableRCRegs_[SrcRC].count();
1041     if (NewUses*SrcSize*SrcRCCount > 2*SrcUses*NewSize*NewRCCount)
1042       return false;
1043   }
1044   if (DstRC != NewRC && DstSize > NewRCCount) {
1045     unsigned DstRCCount = allocatableRCRegs_[DstRC].count();
1046     if (NewUses*DstSize*DstRCCount > 2*DstUses*NewSize*NewRCCount)
1047       return false;
1048   }
1049   return true;
1050 }
1051
1052
1053 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
1054 /// which are the src/dst of the copy instruction CopyMI.  This returns true
1055 /// if the copy was successfully coalesced away. If it is not currently
1056 /// possible to coalesce this interval, but it may be possible if other
1057 /// things get coalesced, then it returns true by reference in 'Again'.
1058 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
1059   MachineInstr *CopyMI = TheCopy.MI;
1060
1061   Again = false;
1062   if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI))
1063     return false; // Already done.
1064
1065   DEBUG(dbgs() << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI);
1066
1067   CoalescerPair CP(*tii_, *tri_);
1068   if (!CP.setRegisters(CopyMI)) {
1069     DEBUG(dbgs() << "\tNot coalescable.\n");
1070     return false;
1071   }
1072
1073   // If they are already joined we continue.
1074   if (CP.getSrcReg() == CP.getDstReg()) {
1075     DEBUG(dbgs() << "\tCopy already coalesced.\n");
1076     return false;  // Not coalescable.
1077   }
1078
1079   DEBUG(dbgs() << "\tConsidering merging %reg" << CP.getSrcReg());
1080
1081   // Enforce policies.
1082   if (CP.isPhys()) {
1083     DEBUG(dbgs() <<" with physreg %" << tri_->getName(CP.getDstReg()) << "\n");
1084     // Only coalesce to allocatable physreg.
1085     if (!allocatableRegs_[CP.getDstReg()]) {
1086       DEBUG(dbgs() << "\tRegister is an unallocatable physreg.\n");
1087       return false;  // Not coalescable.
1088     }
1089   } else {
1090     DEBUG({
1091       dbgs() << " with reg%" << CP.getDstReg();
1092       if (CP.getSubIdx())
1093         dbgs() << ":" << tri_->getSubRegIndexName(CP.getSubIdx());
1094       dbgs() << " to " << CP.getNewRC()->getName() << "\n";
1095     });
1096
1097     // Avoid constraining virtual register regclass too much.
1098     if (CP.isCrossClass()) {
1099       if (DisableCrossClassJoin) {
1100         DEBUG(dbgs() << "\tCross-class joins disabled.\n");
1101         return false;
1102       }
1103       if (!isWinToJoinCrossClass(CP.getSrcReg(), CP.getDstReg(),
1104                                  mri_->getRegClass(CP.getSrcReg()),
1105                                  mri_->getRegClass(CP.getDstReg()),
1106                                  CP.getNewRC())) {
1107         DEBUG(dbgs() << "\tAvoid coalescing to constrained register class: "
1108                      << CP.getNewRC()->getName() << ".\n");
1109         Again = true;  // May be possible to coalesce later.
1110         return false;
1111       }
1112     }
1113
1114     // When possible, let DstReg be the larger interval.
1115     if (!CP.getSubIdx() && li_->getInterval(CP.getSrcReg()).ranges.size() >
1116                            li_->getInterval(CP.getDstReg()).ranges.size())
1117       CP.flip();
1118   }
1119
1120   // We need to be careful about coalescing a source physical register with a
1121   // virtual register. Once the coalescing is done, it cannot be broken and
1122   // these are not spillable! If the destination interval uses are far away,
1123   // think twice about coalescing them!
1124   // FIXME: Why are we skipping this test for partial copies?
1125   //        CodeGen/X86/phys_subreg_coalesce-3.ll needs it.
1126   if (!CP.isPartial() && CP.isPhys()) {
1127     LiveInterval &JoinVInt = li_->getInterval(CP.getSrcReg());
1128
1129     // Don't join with physregs that have a ridiculous number of live
1130     // ranges. The data structure performance is really bad when that
1131     // happens.
1132     if (li_->hasInterval(CP.getDstReg()) &&
1133         li_->getInterval(CP.getDstReg()).ranges.size() > 1000) {
1134       mri_->setRegAllocationHint(CP.getSrcReg(), 0, CP.getDstReg());
1135       ++numAborts;
1136       DEBUG(dbgs()
1137            << "\tPhysical register live interval too complicated, abort!\n");
1138       return false;
1139     }
1140
1141     const TargetRegisterClass *RC = mri_->getRegClass(CP.getSrcReg());
1142     unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
1143     unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
1144     if (Length > Threshold &&
1145         std::distance(mri_->use_nodbg_begin(CP.getSrcReg()),
1146                       mri_->use_nodbg_end()) * Threshold < Length) {
1147       // Before giving up coalescing, if definition of source is defined by
1148       // trivial computation, try rematerializing it.
1149       if (!CP.isFlipped() &&
1150           ReMaterializeTrivialDef(JoinVInt, CP.getDstReg(), 0, CopyMI))
1151         return true;
1152
1153       mri_->setRegAllocationHint(CP.getSrcReg(), 0, CP.getDstReg());
1154       ++numAborts;
1155       DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
1156       Again = true;  // May be possible to coalesce later.
1157       return false;
1158     }
1159   }
1160
1161   // We may need the source interval after JoinIntervals has destroyed it.
1162   OwningPtr<LiveInterval> SavedLI;
1163   if (CP.getOrigDstReg() != CP.getDstReg())
1164     SavedLI.reset(li_->dupInterval(&li_->getInterval(CP.getSrcReg())));
1165
1166   // Okay, attempt to join these two intervals.  On failure, this returns false.
1167   // Otherwise, if one of the intervals being joined is a physreg, this method
1168   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
1169   // been modified, so we can use this information below to update aliases.
1170   if (!JoinIntervals(CP)) {
1171     // Coalescing failed.
1172
1173     // If definition of source is defined by trivial computation, try
1174     // rematerializing it.
1175     if (!CP.isFlipped() &&
1176         ReMaterializeTrivialDef(li_->getInterval(CP.getSrcReg()),
1177                                 CP.getDstReg(), 0, CopyMI))
1178       return true;
1179
1180     // If we can eliminate the copy without merging the live ranges, do so now.
1181     if (!CP.isPartial()) {
1182       LiveInterval *UseInt = &li_->getInterval(CP.getSrcReg());
1183       LiveInterval *DefInt = &li_->getInterval(CP.getDstReg());
1184       if (CP.isFlipped())
1185         std::swap(UseInt, DefInt);
1186       if (AdjustCopiesBackFrom(*UseInt, *DefInt, CopyMI) ||
1187           RemoveCopyByCommutingDef(*UseInt, *DefInt, CopyMI)) {
1188         JoinedCopies.insert(CopyMI);
1189         DEBUG(dbgs() << "\tTrivial!\n");
1190         return true;
1191       }
1192     }
1193
1194     // Otherwise, we are unable to join the intervals.
1195     DEBUG(dbgs() << "\tInterference!\n");
1196     Again = true;  // May be possible to coalesce later.
1197     return false;
1198   }
1199
1200   if (CP.isPhys()) {
1201     // If this is a extract_subreg where dst is a physical register, e.g.
1202     // cl = EXTRACT_SUBREG reg1024, 1
1203     // then create and update the actual physical register allocated to RHS.
1204     unsigned LargerDstReg = CP.getDstReg();
1205     if (CP.getOrigDstReg() != CP.getDstReg()) {
1206       if (tri_->isSubRegister(CP.getOrigDstReg(), LargerDstReg))
1207         LargerDstReg = CP.getOrigDstReg();
1208       LiveInterval &RealInt = li_->getOrCreateInterval(CP.getDstReg());
1209       for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(),
1210              E = SavedLI->vni_end(); I != E; ++I) {
1211         const VNInfo *ValNo = *I;
1212         VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(),
1213                                                 false, // updated at *
1214                                                 li_->getVNInfoAllocator());
1215         NewValNo->setFlags(ValNo->getFlags()); // * updated here.
1216         RealInt.addKills(NewValNo, ValNo->kills);
1217         RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo);
1218       }
1219       RealInt.weight += SavedLI->weight;
1220     }
1221
1222     // Update the liveintervals of sub-registers.
1223     LiveInterval &LargerInt = li_->getInterval(LargerDstReg);
1224     for (const unsigned *AS = tri_->getSubRegisters(LargerDstReg); *AS; ++AS) {
1225       LiveInterval &SRI = li_->getOrCreateInterval(*AS);
1226       SRI.MergeInClobberRanges(*li_, LargerInt, li_->getVNInfoAllocator());
1227       DEBUG({
1228         dbgs() << "\t\tsubreg: "; SRI.print(dbgs(), tri_); dbgs() << "\n";
1229       });
1230     }
1231   }
1232
1233   // Coalescing to a virtual register that is of a sub-register class of the
1234   // other. Make sure the resulting register is set to the right register class.
1235   if (CP.isCrossClass()) {
1236     ++numCrossRCs;
1237     mri_->setRegClass(CP.getDstReg(), CP.getNewRC());
1238   }
1239
1240   // Remember to delete the copy instruction.
1241   JoinedCopies.insert(CopyMI);
1242
1243   UpdateRegDefsUses(CP);
1244
1245   // If we have extended the live range of a physical register, make sure we
1246   // update live-in lists as well.
1247   if (CP.isPhys()) {
1248     SmallVector<MachineBasicBlock*, 16> BlockSeq;
1249     // JoinIntervals invalidates the VNInfos in SrcInt, but we only need the
1250     // ranges for this, and they are preserved.
1251     LiveInterval &SrcInt = li_->getInterval(CP.getSrcReg());
1252     for (LiveInterval::const_iterator I = SrcInt.begin(), E = SrcInt.end();
1253          I != E; ++I ) {
1254       li_->findLiveInMBBs(I->start, I->end, BlockSeq);
1255       for (unsigned idx = 0, size = BlockSeq.size(); idx != size; ++idx) {
1256         MachineBasicBlock &block = *BlockSeq[idx];
1257         if (!block.isLiveIn(CP.getDstReg()))
1258           block.addLiveIn(CP.getDstReg());
1259       }
1260       BlockSeq.clear();
1261     }
1262   }
1263
1264   // SrcReg is guarateed to be the register whose live interval that is
1265   // being merged.
1266   li_->removeInterval(CP.getSrcReg());
1267
1268   // Update regalloc hint.
1269   tri_->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *mf_);
1270
1271   DEBUG({
1272     LiveInterval &DstInt = li_->getInterval(CP.getDstReg());
1273     dbgs() << "\tJoined. Result = ";
1274     DstInt.print(dbgs(), tri_);
1275     dbgs() << "\n";
1276   });
1277
1278   ++numJoins;
1279   return true;
1280 }
1281
1282 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
1283 /// compute what the resultant value numbers for each value in the input two
1284 /// ranges will be.  This is complicated by copies between the two which can
1285 /// and will commonly cause multiple value numbers to be merged into one.
1286 ///
1287 /// VN is the value number that we're trying to resolve.  InstDefiningValue
1288 /// keeps track of the new InstDefiningValue assignment for the result
1289 /// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
1290 /// whether a value in this or other is a copy from the opposite set.
1291 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
1292 /// already been assigned.
1293 ///
1294 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
1295 /// contains the value number the copy is from.
1296 ///
1297 static unsigned ComputeUltimateVN(VNInfo *VNI,
1298                                   SmallVector<VNInfo*, 16> &NewVNInfo,
1299                                   DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
1300                                   DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
1301                                   SmallVector<int, 16> &ThisValNoAssignments,
1302                                   SmallVector<int, 16> &OtherValNoAssignments) {
1303   unsigned VN = VNI->id;
1304
1305   // If the VN has already been computed, just return it.
1306   if (ThisValNoAssignments[VN] >= 0)
1307     return ThisValNoAssignments[VN];
1308   assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers");
1309
1310   // If this val is not a copy from the other val, then it must be a new value
1311   // number in the destination.
1312   DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
1313   if (I == ThisFromOther.end()) {
1314     NewVNInfo.push_back(VNI);
1315     return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
1316   }
1317   VNInfo *OtherValNo = I->second;
1318
1319   // Otherwise, this *is* a copy from the RHS.  If the other side has already
1320   // been computed, return it.
1321   if (OtherValNoAssignments[OtherValNo->id] >= 0)
1322     return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
1323
1324   // Mark this value number as currently being computed, then ask what the
1325   // ultimate value # of the other value is.
1326   ThisValNoAssignments[VN] = -2;
1327   unsigned UltimateVN =
1328     ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
1329                       OtherValNoAssignments, ThisValNoAssignments);
1330   return ThisValNoAssignments[VN] = UltimateVN;
1331 }
1332
1333 /// JoinIntervals - Attempt to join these two intervals.  On failure, this
1334 /// returns false.
1335 bool SimpleRegisterCoalescing::JoinIntervals(CoalescerPair &CP) {
1336   LiveInterval &RHS = li_->getInterval(CP.getSrcReg());
1337   DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), tri_); dbgs() << "\n"; });
1338
1339   // FIXME: Join into CP.getDstReg instead of CP.getOrigDstReg.
1340   // When looking at
1341   //   %reg2000 = EXTRACT_SUBREG %EAX, sub_16bit
1342   // we really want to join %reg2000 with %AX ( = CP.getDstReg). We are actually
1343   // joining into %EAX ( = CP.getOrigDstReg) because it is guaranteed to have an
1344   // existing live interval, and we are better equipped to handle interference.
1345   // JoinCopy cleans up the mess by taking a copy of RHS before calling here,
1346   // and merging that copy into CP.getDstReg after.
1347
1348   // If a live interval is a physical register, conservatively check if any
1349   // of its sub-registers is overlapping the live interval of the virtual
1350   // register. If so, do not coalesce.
1351   if (CP.isPhys() && *tri_->getSubRegisters(CP.getOrigDstReg())) {
1352     // If it's coalescing a virtual register to a physical register, estimate
1353     // its live interval length. This is the *cost* of scanning an entire live
1354     // interval. If the cost is low, we'll do an exhaustive check instead.
1355
1356     // If this is something like this:
1357     // BB1:
1358     // v1024 = op
1359     // ...
1360     // BB2:
1361     // ...
1362     // RAX   = v1024
1363     //
1364     // That is, the live interval of v1024 crosses a bb. Then we can't rely on
1365     // less conservative check. It's possible a sub-register is defined before
1366     // v1024 (or live in) and live out of BB1.
1367     if (RHS.containsOneValue() &&
1368         li_->intervalIsInOneMBB(RHS) &&
1369         li_->getApproximateInstructionCount(RHS) <= 10) {
1370       // Perform a more exhaustive check for some common cases.
1371       if (li_->conflictsWithAliasRef(RHS, CP.getOrigDstReg(), JoinedCopies))
1372         return false;
1373     } else {
1374       for (const unsigned* SR = tri_->getAliasSet(CP.getOrigDstReg()); *SR;
1375            ++SR)
1376         if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
1377           DEBUG({
1378               dbgs() << "\tInterfere with sub-register ";
1379               li_->getInterval(*SR).print(dbgs(), tri_);
1380             });
1381           return false;
1382         }
1383     }
1384   }
1385
1386   // Compute the final value assignment, assuming that the live ranges can be
1387   // coalesced.
1388   SmallVector<int, 16> LHSValNoAssignments;
1389   SmallVector<int, 16> RHSValNoAssignments;
1390   DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
1391   DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
1392   SmallVector<VNInfo*, 16> NewVNInfo;
1393
1394   LiveInterval &LHS = li_->getInterval(CP.getOrigDstReg());
1395   DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), tri_); dbgs() << "\n"; });
1396
1397   // Loop over the value numbers of the LHS, seeing if any are defined from
1398   // the RHS.
1399   for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1400        i != e; ++i) {
1401     VNInfo *VNI = *i;
1402     if (VNI->isUnused() || VNI->getCopy() == 0)  // Src not defined by a copy?
1403       continue;
1404
1405     // Never join with a register that has EarlyClobber redefs.
1406     if (VNI->hasRedefByEC())
1407       return false;
1408
1409     // DstReg is known to be a register in the LHS interval.  If the src is
1410     // from the RHS interval, we can use its value #.
1411     if (!CP.isCoalescable(VNI->getCopy()))
1412       continue;
1413
1414     // Figure out the value # from the RHS.
1415     LiveRange *lr = RHS.getLiveRangeContaining(VNI->def.getPrevSlot());
1416     // The copy could be to an aliased physreg.
1417     if (!lr) continue;
1418     LHSValsDefinedFromRHS[VNI] = lr->valno;
1419   }
1420
1421   // Loop over the value numbers of the RHS, seeing if any are defined from
1422   // the LHS.
1423   for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1424        i != e; ++i) {
1425     VNInfo *VNI = *i;
1426     if (VNI->isUnused() || VNI->getCopy() == 0)  // Src not defined by a copy?
1427       continue;
1428
1429     // Never join with a register that has EarlyClobber redefs.
1430     if (VNI->hasRedefByEC())
1431       return false;
1432
1433     // DstReg is known to be a register in the RHS interval.  If the src is
1434     // from the LHS interval, we can use its value #.
1435     if (!CP.isCoalescable(VNI->getCopy()))
1436       continue;
1437
1438     // Figure out the value # from the LHS.
1439     LiveRange *lr = LHS.getLiveRangeContaining(VNI->def.getPrevSlot());
1440     // The copy could be to an aliased physreg.
1441     if (!lr) continue;
1442     RHSValsDefinedFromLHS[VNI] = lr->valno;
1443   }
1444
1445   LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1446   RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1447   NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
1448
1449   for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1450        i != e; ++i) {
1451     VNInfo *VNI = *i;
1452     unsigned VN = VNI->id;
1453     if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused())
1454       continue;
1455     ComputeUltimateVN(VNI, NewVNInfo,
1456                       LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
1457                       LHSValNoAssignments, RHSValNoAssignments);
1458   }
1459   for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1460        i != e; ++i) {
1461     VNInfo *VNI = *i;
1462     unsigned VN = VNI->id;
1463     if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused())
1464       continue;
1465     // If this value number isn't a copy from the LHS, it's a new number.
1466     if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
1467       NewVNInfo.push_back(VNI);
1468       RHSValNoAssignments[VN] = NewVNInfo.size()-1;
1469       continue;
1470     }
1471
1472     ComputeUltimateVN(VNI, NewVNInfo,
1473                       RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
1474                       RHSValNoAssignments, LHSValNoAssignments);
1475   }
1476
1477   // Armed with the mappings of LHS/RHS values to ultimate values, walk the
1478   // interval lists to see if these intervals are coalescable.
1479   LiveInterval::const_iterator I = LHS.begin();
1480   LiveInterval::const_iterator IE = LHS.end();
1481   LiveInterval::const_iterator J = RHS.begin();
1482   LiveInterval::const_iterator JE = RHS.end();
1483
1484   // Skip ahead until the first place of potential sharing.
1485   if (I != IE && J != JE) {
1486     if (I->start < J->start) {
1487       I = std::upper_bound(I, IE, J->start);
1488       if (I != LHS.begin()) --I;
1489     } else if (J->start < I->start) {
1490       J = std::upper_bound(J, JE, I->start);
1491       if (J != RHS.begin()) --J;
1492     }
1493   }
1494
1495   while (I != IE && J != JE) {
1496     // Determine if these two live ranges overlap.
1497     bool Overlaps;
1498     if (I->start < J->start) {
1499       Overlaps = I->end > J->start;
1500     } else {
1501       Overlaps = J->end > I->start;
1502     }
1503
1504     // If so, check value # info to determine if they are really different.
1505     if (Overlaps) {
1506       // If the live range overlap will map to the same value number in the
1507       // result liverange, we can still coalesce them.  If not, we can't.
1508       if (LHSValNoAssignments[I->valno->id] !=
1509           RHSValNoAssignments[J->valno->id])
1510         return false;
1511       // If it's re-defined by an early clobber somewhere in the live range,
1512       // then conservatively abort coalescing.
1513       if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC())
1514         return false;
1515     }
1516
1517     if (I->end < J->end)
1518       ++I;
1519     else
1520       ++J;
1521   }
1522
1523   // Update kill info. Some live ranges are extended due to copy coalescing.
1524   for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(),
1525          E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
1526     VNInfo *VNI = I->first;
1527     unsigned LHSValID = LHSValNoAssignments[VNI->id];
1528     NewVNInfo[LHSValID]->removeKill(VNI->def);
1529     if (VNI->hasPHIKill())
1530       NewVNInfo[LHSValID]->setHasPHIKill(true);
1531     RHS.addKills(NewVNInfo[LHSValID], VNI->kills);
1532   }
1533
1534   // Update kill info. Some live ranges are extended due to copy coalescing.
1535   for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(),
1536          E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
1537     VNInfo *VNI = I->first;
1538     unsigned RHSValID = RHSValNoAssignments[VNI->id];
1539     NewVNInfo[RHSValID]->removeKill(VNI->def);
1540     if (VNI->hasPHIKill())
1541       NewVNInfo[RHSValID]->setHasPHIKill(true);
1542     LHS.addKills(NewVNInfo[RHSValID], VNI->kills);
1543   }
1544
1545   if (LHSValNoAssignments.empty())
1546     LHSValNoAssignments.push_back(-1);
1547   if (RHSValNoAssignments.empty())
1548     RHSValNoAssignments.push_back(-1);
1549
1550   // If we get here, we know that we can coalesce the live ranges.  Ask the
1551   // intervals to coalesce themselves now.
1552   LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo,
1553            mri_);
1554   return true;
1555 }
1556
1557 namespace {
1558   // DepthMBBCompare - Comparison predicate that sort first based on the loop
1559   // depth of the basic block (the unsigned), and then on the MBB number.
1560   struct DepthMBBCompare {
1561     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
1562     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
1563       // Deeper loops first
1564       if (LHS.first != RHS.first)
1565         return LHS.first > RHS.first;
1566
1567       // Prefer blocks that are more connected in the CFG. This takes care of
1568       // the most difficult copies first while intervals are short.
1569       unsigned cl = LHS.second->pred_size() + LHS.second->succ_size();
1570       unsigned cr = RHS.second->pred_size() + RHS.second->succ_size();
1571       if (cl != cr)
1572         return cl > cr;
1573
1574       // As a last resort, sort by block number.
1575       return LHS.second->getNumber() < RHS.second->getNumber();
1576     }
1577   };
1578 }
1579
1580 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
1581                                                std::vector<CopyRec> &TryAgain) {
1582   DEBUG(dbgs() << MBB->getName() << ":\n");
1583
1584   std::vector<CopyRec> VirtCopies;
1585   std::vector<CopyRec> PhysCopies;
1586   std::vector<CopyRec> ImpDefCopies;
1587   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
1588        MII != E;) {
1589     MachineInstr *Inst = MII++;
1590
1591     // If this isn't a copy nor a extract_subreg, we can't join intervals.
1592     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1593     bool isInsUndef = false;
1594     if (Inst->isExtractSubreg()) {
1595       DstReg = Inst->getOperand(0).getReg();
1596       SrcReg = Inst->getOperand(1).getReg();
1597     } else if (Inst->isInsertSubreg()) {
1598       DstReg = Inst->getOperand(0).getReg();
1599       SrcReg = Inst->getOperand(2).getReg();
1600       if (Inst->getOperand(1).isUndef())
1601         isInsUndef = true;
1602     } else if (Inst->isInsertSubreg() || Inst->isSubregToReg()) {
1603       DstReg = Inst->getOperand(0).getReg();
1604       SrcReg = Inst->getOperand(2).getReg();
1605     } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1606       continue;
1607
1608     bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
1609     bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1610     if (isInsUndef ||
1611         (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()))
1612       ImpDefCopies.push_back(CopyRec(Inst, 0));
1613     else if (SrcIsPhys || DstIsPhys)
1614       PhysCopies.push_back(CopyRec(Inst, 0));
1615     else
1616       VirtCopies.push_back(CopyRec(Inst, 0));
1617   }
1618
1619   // Try coalescing implicit copies and insert_subreg <undef> first,
1620   // followed by copies to / from physical registers, then finally copies
1621   // from virtual registers to virtual registers.
1622   for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) {
1623     CopyRec &TheCopy = ImpDefCopies[i];
1624     bool Again = false;
1625     if (!JoinCopy(TheCopy, Again))
1626       if (Again)
1627         TryAgain.push_back(TheCopy);
1628   }
1629   for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) {
1630     CopyRec &TheCopy = PhysCopies[i];
1631     bool Again = false;
1632     if (!JoinCopy(TheCopy, Again))
1633       if (Again)
1634         TryAgain.push_back(TheCopy);
1635   }
1636   for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) {
1637     CopyRec &TheCopy = VirtCopies[i];
1638     bool Again = false;
1639     if (!JoinCopy(TheCopy, Again))
1640       if (Again)
1641         TryAgain.push_back(TheCopy);
1642   }
1643 }
1644
1645 void SimpleRegisterCoalescing::joinIntervals() {
1646   DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
1647
1648   std::vector<CopyRec> TryAgainList;
1649   if (loopInfo->empty()) {
1650     // If there are no loops in the function, join intervals in function order.
1651     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
1652          I != E; ++I)
1653       CopyCoalesceInMBB(I, TryAgainList);
1654   } else {
1655     // Otherwise, join intervals in inner loops before other intervals.
1656     // Unfortunately we can't just iterate over loop hierarchy here because
1657     // there may be more MBB's than BB's.  Collect MBB's for sorting.
1658
1659     // Join intervals in the function prolog first. We want to join physical
1660     // registers with virtual registers before the intervals got too long.
1661     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
1662     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){
1663       MachineBasicBlock *MBB = I;
1664       MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I));
1665     }
1666
1667     // Sort by loop depth.
1668     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
1669
1670     // Finally, join intervals in loop nest order.
1671     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
1672       CopyCoalesceInMBB(MBBs[i].second, TryAgainList);
1673   }
1674
1675   // Joining intervals can allow other intervals to be joined.  Iteratively join
1676   // until we make no progress.
1677   bool ProgressMade = true;
1678   while (ProgressMade) {
1679     ProgressMade = false;
1680
1681     for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
1682       CopyRec &TheCopy = TryAgainList[i];
1683       if (!TheCopy.MI)
1684         continue;
1685
1686       bool Again = false;
1687       bool Success = JoinCopy(TheCopy, Again);
1688       if (Success || !Again) {
1689         TheCopy.MI = 0;   // Mark this one as done.
1690         ProgressMade = true;
1691       }
1692     }
1693   }
1694 }
1695
1696 /// Return true if the two specified registers belong to different register
1697 /// classes.  The registers may be either phys or virt regs.
1698 bool
1699 SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
1700                                                    unsigned RegB) const {
1701   // Get the register classes for the first reg.
1702   if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
1703     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1704            "Shouldn't consider two physregs!");
1705     return !mri_->getRegClass(RegB)->contains(RegA);
1706   }
1707
1708   // Compare against the regclass for the second reg.
1709   const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA);
1710   if (TargetRegisterInfo::isVirtualRegister(RegB)) {
1711     const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB);
1712     return RegClassA != RegClassB;
1713   }
1714   return !RegClassA->contains(RegB);
1715 }
1716
1717 /// lastRegisterUse - Returns the last (non-debug) use of the specific register
1718 /// between cycles Start and End or NULL if there are no uses.
1719 MachineOperand *
1720 SimpleRegisterCoalescing::lastRegisterUse(SlotIndex Start,
1721                                           SlotIndex End,
1722                                           unsigned Reg,
1723                                           SlotIndex &UseIdx) const{
1724   UseIdx = SlotIndex();
1725   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1726     MachineOperand *LastUse = NULL;
1727     for (MachineRegisterInfo::use_nodbg_iterator I = mri_->use_nodbg_begin(Reg),
1728            E = mri_->use_nodbg_end(); I != E; ++I) {
1729       MachineOperand &Use = I.getOperand();
1730       MachineInstr *UseMI = Use.getParent();
1731       unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1732       if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
1733           SrcReg == DstReg && SrcSubIdx == DstSubIdx)
1734         // Ignore identity copies.
1735         continue;
1736       SlotIndex Idx = li_->getInstructionIndex(UseMI);
1737       // FIXME: Should this be Idx != UseIdx? SlotIndex() will return something
1738       // that compares higher than any other interval.
1739       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
1740         LastUse = &Use;
1741         UseIdx = Idx.getUseIndex();
1742       }
1743     }
1744     return LastUse;
1745   }
1746
1747   SlotIndex s = Start;
1748   SlotIndex e = End.getPrevSlot().getBaseIndex();
1749   while (e >= s) {
1750     // Skip deleted instructions
1751     MachineInstr *MI = li_->getInstructionFromIndex(e);
1752     while (e != SlotIndex() && e.getPrevIndex() >= s && !MI) {
1753       e = e.getPrevIndex();
1754       MI = li_->getInstructionFromIndex(e);
1755     }
1756     if (e < s || MI == NULL)
1757       return NULL;
1758
1759     // Ignore identity copies.
1760     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1761     if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
1762           SrcReg == DstReg && SrcSubIdx == DstSubIdx))
1763       for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
1764         MachineOperand &Use = MI->getOperand(i);
1765         if (Use.isReg() && Use.isUse() && Use.getReg() &&
1766             tri_->regsOverlap(Use.getReg(), Reg)) {
1767           UseIdx = e.getUseIndex();
1768           return &Use;
1769         }
1770       }
1771
1772     e = e.getPrevIndex();
1773   }
1774
1775   return NULL;
1776 }
1777
1778 void SimpleRegisterCoalescing::releaseMemory() {
1779   JoinedCopies.clear();
1780   ReMatCopies.clear();
1781   ReMatDefs.clear();
1782 }
1783
1784 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
1785   mf_ = &fn;
1786   mri_ = &fn.getRegInfo();
1787   tm_ = &fn.getTarget();
1788   tri_ = tm_->getRegisterInfo();
1789   tii_ = tm_->getInstrInfo();
1790   li_ = &getAnalysis<LiveIntervals>();
1791   AA = &getAnalysis<AliasAnalysis>();
1792   loopInfo = &getAnalysis<MachineLoopInfo>();
1793
1794   DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
1795                << "********** Function: "
1796                << ((Value*)mf_->getFunction())->getName() << '\n');
1797
1798   allocatableRegs_ = tri_->getAllocatableSet(fn);
1799   for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(),
1800          E = tri_->regclass_end(); I != E; ++I)
1801     allocatableRCRegs_.insert(std::make_pair(*I,
1802                                              tri_->getAllocatableSet(fn, *I)));
1803
1804   // Join (coalesce) intervals if requested.
1805   if (EnableJoining) {
1806     joinIntervals();
1807     DEBUG({
1808         dbgs() << "********** INTERVALS POST JOINING **********\n";
1809         for (LiveIntervals::iterator I = li_->begin(), E = li_->end();
1810              I != E; ++I){
1811           I->second->print(dbgs(), tri_);
1812           dbgs() << "\n";
1813         }
1814       });
1815   }
1816
1817   // Perform a final pass over the instructions and compute spill weights
1818   // and remove identity moves.
1819   SmallVector<unsigned, 4> DeadDefs;
1820   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
1821        mbbi != mbbe; ++mbbi) {
1822     MachineBasicBlock* mbb = mbbi;
1823     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
1824          mii != mie; ) {
1825       MachineInstr *MI = mii;
1826       unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1827       if (JoinedCopies.count(MI)) {
1828         // Delete all coalesced copies.
1829         bool DoDelete = true;
1830         if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
1831           assert((MI->isExtractSubreg() || MI->isInsertSubreg() ||
1832                   MI->isSubregToReg()) && "Unrecognized copy instruction");
1833           SrcReg = MI->getOperand(MI->isSubregToReg() ? 2 : 1).getReg();
1834           if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
1835             // Do not delete extract_subreg, insert_subreg of physical
1836             // registers unless the definition is dead. e.g.
1837             // %DO<def> = INSERT_SUBREG %D0<undef>, %S0<kill>, 1
1838             // or else the scavenger may complain. LowerSubregs will
1839             // delete them later.
1840             DoDelete = false;
1841         }
1842         if (MI->allDefsAreDead()) {
1843           LiveInterval &li = li_->getInterval(SrcReg);
1844           if (!ShortenDeadCopySrcLiveRange(li, MI))
1845             ShortenDeadCopyLiveRange(li, MI);
1846           DoDelete = true;
1847         }
1848         if (!DoDelete)
1849           mii = llvm::next(mii);
1850         else {
1851           li_->RemoveMachineInstrFromMaps(MI);
1852           mii = mbbi->erase(mii);
1853           ++numPeep;
1854         }
1855         continue;
1856       }
1857
1858       // Now check if this is a remat'ed def instruction which is now dead.
1859       if (ReMatDefs.count(MI)) {
1860         bool isDead = true;
1861         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1862           const MachineOperand &MO = MI->getOperand(i);
1863           if (!MO.isReg())
1864             continue;
1865           unsigned Reg = MO.getReg();
1866           if (!Reg)
1867             continue;
1868           if (TargetRegisterInfo::isVirtualRegister(Reg))
1869             DeadDefs.push_back(Reg);
1870           if (MO.isDead())
1871             continue;
1872           if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
1873               !mri_->use_nodbg_empty(Reg)) {
1874             isDead = false;
1875             break;
1876           }
1877         }
1878         if (isDead) {
1879           while (!DeadDefs.empty()) {
1880             unsigned DeadDef = DeadDefs.back();
1881             DeadDefs.pop_back();
1882             RemoveDeadDef(li_->getInterval(DeadDef), MI);
1883           }
1884           li_->RemoveMachineInstrFromMaps(mii);
1885           mii = mbbi->erase(mii);
1886           continue;
1887         } else
1888           DeadDefs.clear();
1889       }
1890
1891       // If the move will be an identity move delete it
1892       bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
1893       if (isMove && SrcReg == DstReg && SrcSubIdx == DstSubIdx) {
1894         if (li_->hasInterval(SrcReg)) {
1895           LiveInterval &RegInt = li_->getInterval(SrcReg);
1896           // If def of this move instruction is dead, remove its live range
1897           // from the dstination register's live interval.
1898           if (MI->registerDefIsDead(DstReg)) {
1899             if (!ShortenDeadCopySrcLiveRange(RegInt, MI))
1900               ShortenDeadCopyLiveRange(RegInt, MI);
1901           } else {
1902             // If a value is killed here remove the marker.
1903             SlotIndex UseIdx = li_->getInstructionIndex(MI).getUseIndex();
1904             if (const LiveRange *LR = RegInt.getLiveRangeContaining(UseIdx))
1905               LR->valno->removeKill(UseIdx.getDefIndex());
1906           }
1907         }
1908         li_->RemoveMachineInstrFromMaps(MI);
1909         mii = mbbi->erase(mii);
1910         ++numPeep;
1911         continue;
1912       }
1913
1914       ++mii;
1915
1916       // Check for now unnecessary kill flags.
1917       if (li_->isNotInMIMap(MI)) continue;
1918       SlotIndex UseIdx = li_->getInstructionIndex(MI).getUseIndex();
1919       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1920         MachineOperand &MO = MI->getOperand(i);
1921         if (!MO.isReg() || !MO.isKill()) continue;
1922         unsigned reg = MO.getReg();
1923         if (!reg || !li_->hasInterval(reg)) continue;
1924         LiveInterval &LI = li_->getInterval(reg);
1925         const LiveRange *LR = LI.getLiveRangeContaining(UseIdx);
1926         if (!LR ||
1927             (!LR->valno->isKill(UseIdx.getDefIndex()) &&
1928              LR->valno->def != UseIdx.getDefIndex()))
1929           MO.setIsKill(false);
1930       }
1931     }
1932   }
1933
1934   DEBUG(dump());
1935   return true;
1936 }
1937
1938 /// print - Implement the dump method.
1939 void SimpleRegisterCoalescing::print(raw_ostream &O, const Module* m) const {
1940    li_->print(O, m);
1941 }
1942
1943 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() {
1944   return new SimpleRegisterCoalescing();
1945 }
1946
1947 // Make sure that anything that uses RegisterCoalescer pulls in this file...
1948 DEFINING_FILE_FOR(SimpleRegisterCoalescing)