lib/CodeGen/RegisterCoalescer.cpp

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