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