lib/CodeGen/SimpleRegisterCoalescing.cpp

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