lib/CodeGen/SimpleRegisterCoalescing.cpp

   1 //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a simple register coalescing pass that attempts to
  11 // aggressively coalesce every register copy that it can.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "regcoalescing"
  16 #include "SimpleRegisterCoalescing.h"
  17 #include "VirtRegMap.h"
  18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  19 #include "llvm/Value.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineLoopInfo.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/RegisterCoalescer.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Target/TargetMachine.h"
  28 #include "llvm/Support/CommandLine.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/ADT/SmallSet.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/ADT/STLExtras.h"
  33 #include <algorithm>
  34 #include <cmath>
  35 using namespace llvm;
  36
  37 STATISTIC(numJoins    , "Number of interval joins performed");
  38 STATISTIC(numSubJoins , "Number of subclass joins performed");
  39 STATISTIC(numCommutes , "Number of instruction commuting performed");
  40 STATISTIC(numExtends  , "Number of copies extended");
  41 STATISTIC(NumReMats   , "Number of instructions re-materialized");
  42 STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
  43 STATISTIC(numAborts   , "Number of times interval joining aborted");
  44
  45 char SimpleRegisterCoalescing::ID = 0;
  46 static cl::opt<bool>
  47 EnableJoining("join-liveintervals",
  48               cl::desc("Coalesce copies (default=true)"),
  49               cl::init(true));
  50
  51 static cl::opt<bool>
  52 NewHeuristic("new-coalescer-heuristic",
  53              cl::desc("Use new coalescer heuristic"),
  54              cl::init(false), cl::Hidden);
  55
  56 static cl::opt<bool>
  57 CrossClassJoin("join-subclass-copies",
  58                cl::desc("Coalesce copies to sub- register class"),
  59                cl::init(false), cl::Hidden);
  60
  61 static RegisterPass<SimpleRegisterCoalescing>
  62 X("simple-register-coalescing", "Simple Register Coalescing");
  63
  64 // Declare that we implement the RegisterCoalescer interface
  65 static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
  66
  67 const PassInfo *const llvm::SimpleRegisterCoalescingID = &X;
  68
  69 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
  70   AU.addPreserved<LiveIntervals>();
  71   AU.addPreserved<MachineLoopInfo>();
  72   AU.addPreservedID(MachineDominatorsID);
  73   AU.addPreservedID(PHIEliminationID);
  74   AU.addPreservedID(TwoAddressInstructionPassID);
  75   AU.addRequired<LiveIntervals>();
  76   AU.addRequired<MachineLoopInfo>();
  77   MachineFunctionPass::getAnalysisUsage(AU);
  78 }
  79
  80 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
  81 /// being the source and IntB being the dest, thus this defines a value number
  82 /// in IntB.  If the source value number (in IntA) is defined by a copy from B,
  83 /// see if we can merge these two pieces of B into a single value number,
  84 /// eliminating a copy.  For example:
  85 ///
  86 ///  A3 = B0
  87 ///    ...
  88 ///  B1 = A3      <- this copy
  89 ///
  90 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
  91 /// value number to be replaced with B0 (which simplifies the B liveinterval).
  92 ///
  93 /// This returns true if an interval was modified.
  94 ///
  95 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
  96                                                     LiveInterval &IntB,
  97                                                     MachineInstr *CopyMI) {
  98   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
  99
 100   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
 101   // the example above.
 102   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 103   if (BLR == IntB.end()) // Should never happen!
 104     return false;
 105   VNInfo *BValNo = BLR->valno;
 106
 107   // Get the location that B is defined at.  Two options: either this value has
 108   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 109   // can't process it.
 110   if (!BValNo->copy) return false;
 111   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 112
 113   // AValNo is the value number in A that defines the copy, A3 in the example.
 114   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
 115   if (ALR == IntA.end()) // Should never happen!
 116     return false;
 117   VNInfo *AValNo = ALR->valno;
 118
 119   // If AValNo is defined as a copy from IntB, we can potentially process this.
 120   // Get the instruction that defines this value number.
 121   unsigned SrcReg = li_->getVNInfoSourceReg(AValNo);
 122   if (!SrcReg) return false;  // Not defined by a copy.
 123
 124   // If the value number is not defined by a copy instruction, ignore it.
 125
 126   // If the source register comes from an interval other than IntB, we can't
 127   // handle this.
 128   if (SrcReg != IntB.reg) return false;
 129
 130   // Get the LiveRange in IntB that this value number starts with.
 131   LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1);
 132   if (ValLR == IntB.end()) // Should never happen!
 133     return false;
 134
 135   // Make sure that the end of the live range is inside the same block as
 136   // CopyMI.
 137   MachineInstr *ValLREndInst = li_->getInstructionFromIndex(ValLR->end-1);
 138   if (!ValLREndInst ||
 139       ValLREndInst->getParent() != CopyMI->getParent()) return false;
 140
 141   // Okay, we now know that ValLR ends in the same block that the CopyMI
 142   // live-range starts.  If there are no intervening live ranges between them in
 143   // IntB, we can merge them.
 144   if (ValLR+1 != BLR) return false;
 145
 146   // If a live interval is a physical register, conservatively check if any
 147   // of its sub-registers is overlapping the live interval of the virtual
 148   // register. If so, do not coalesce.
 149   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) &&
 150       *tri_->getSubRegisters(IntB.reg)) {
 151     for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
 152       if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) {
 153         DOUT << "Interfere with sub-register ";
 154         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
 155         return false;
 156       }
 157   }
 158
 159   DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
 160
 161   unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
 162   // We are about to delete CopyMI, so need to remove it as the 'instruction
 163   // that defines this value #'. Update the the valnum with the new defining
 164   // instruction #.
 165   BValNo->def  = FillerStart;
 166   BValNo->copy = NULL;
 167
 168   // Okay, we can merge them.  We need to insert a new liverange:
 169   // [ValLR.end, BLR.begin) of either value number, then we merge the
 170   // two value numbers.
 171   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
 172
 173   // If the IntB live range is assigned to a physical register, and if that
 174   // physreg has aliases,
 175   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
 176     // Update the liveintervals of sub-registers.
 177     for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) {
 178       LiveInterval &AliasLI = li_->getInterval(*AS);
 179       AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
 180               AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator())));
 181     }
 182   }
 183
 184   // Okay, merge "B1" into the same value number as "B0".
 185   if (BValNo != ValLR->valno) {
 186     IntB.addKills(ValLR->valno, BValNo->kills);
 187     IntB.MergeValueNumberInto(BValNo, ValLR->valno);
 188   }
 189   DOUT << "   result = "; IntB.print(DOUT, tri_);
 190   DOUT << "\n";
 191
 192   // If the source instruction was killing the source register before the
 193   // merge, unset the isKill marker given the live range has been extended.
 194   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
 195   if (UIdx != -1) {
 196     ValLREndInst->getOperand(UIdx).setIsKill(false);
 197     IntB.removeKill(ValLR->valno, FillerStart);
 198   }
 199
 200   ++numExtends;
 201   return true;
 202 }
 203
 204 /// HasOtherReachingDefs - Return true if there are definitions of IntB
 205 /// other than BValNo val# that can reach uses of AValno val# of IntA.
 206 bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA,
 207                                                     LiveInterval &IntB,
 208                                                     VNInfo *AValNo,
 209                                                     VNInfo *BValNo) {
 210   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 211        AI != AE; ++AI) {
 212     if (AI->valno != AValNo) continue;
 213     LiveInterval::Ranges::iterator BI =
 214       std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
 215     if (BI != IntB.ranges.begin())
 216       --BI;
 217     for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
 218       if (BI->valno == BValNo)
 219         continue;
 220       if (BI->start <= AI->start && BI->end > AI->start)
 221         return true;
 222       if (BI->start > AI->start && BI->start < AI->end)
 223         return true;
 224     }
 225   }
 226   return false;
 227 }
 228
 229 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA
 230 /// being the source and IntB being the dest, thus this defines a value number
 231 /// in IntB.  If the source value number (in IntA) is defined by a commutable
 232 /// instruction and its other operand is coalesced to the copy dest register,
 233 /// see if we can transform the copy into a noop by commuting the definition. For
 234 /// example,
 235 ///
 236 ///  A3 = op A2 B0<kill>
 237 ///    ...
 238 ///  B1 = A3      <- this copy
 239 ///    ...
 240 ///     = op A3   <- more uses
 241 ///
 242 /// ==>
 243 ///
 244 ///  B2 = op B0 A2<kill>
 245 ///    ...
 246 ///  B1 = B2      <- now an identify copy
 247 ///    ...
 248 ///     = op B2   <- more uses
 249 ///
 250 /// This returns true if an interval was modified.
 251 ///
 252 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
 253                                                         LiveInterval &IntB,
 254                                                         MachineInstr *CopyMI) {
 255   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
 256
 257   // FIXME: For now, only eliminate the copy by commuting its def when the
 258   // source register is a virtual register. We want to guard against cases
 259   // where the copy is a back edge copy and commuting the def lengthen the
 260   // live interval of the source register to the entire loop.
 261   if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
 262     return false;
 263
 264   // BValNo is a value number in B that is defined by a copy from A. 'B3' in
 265   // the example above.
 266   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 267   if (BLR == IntB.end()) // Should never happen!
 268     return false;
 269   VNInfo *BValNo = BLR->valno;
 270
 271   // Get the location that B is defined at.  Two options: either this value has
 272   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 273   // can't process it.
 274   if (!BValNo->copy) return false;
 275   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 276
 277   // AValNo is the value number in A that defines the copy, A3 in the example.
 278   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
 279   if (ALR == IntA.end()) // Should never happen!
 280     return false;
 281   VNInfo *AValNo = ALR->valno;
 282   // If other defs can reach uses of this def, then it's not safe to perform
 283   // the optimization.
 284   if (AValNo->def == ~0U || AValNo->def == ~1U || AValNo->hasPHIKill)
 285     return false;
 286   MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def);
 287   const TargetInstrDesc &TID = DefMI->getDesc();
 288   unsigned NewDstIdx;
 289   if (!TID.isCommutable() ||
 290       !tii_->CommuteChangesDestination(DefMI, NewDstIdx))
 291     return false;
 292
 293   MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
 294   unsigned NewReg = NewDstMO.getReg();
 295   if (NewReg != IntB.reg || !NewDstMO.isKill())
 296     return false;
 297
 298   // Make sure there are no other definitions of IntB that would reach the
 299   // uses which the new definition can reach.
 300   if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
 301     return false;
 302
 303   // If some of the uses of IntA.reg is already coalesced away, return false.
 304   // It's not possible to determine whether it's safe to perform the coalescing.
 305   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
 306          UE = mri_->use_end(); UI != UE; ++UI) {
 307     MachineInstr *UseMI = &*UI;
 308     unsigned UseIdx = li_->getInstructionIndex(UseMI);
 309     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 310     if (ULR == IntA.end())
 311       continue;
 312     if (ULR->valno == AValNo && JoinedCopies.count(UseMI))
 313       return false;
 314   }
 315
 316   // At this point we have decided that it is legal to do this
 317   // transformation.  Start by commuting the instruction.
 318   MachineBasicBlock *MBB = DefMI->getParent();
 319   MachineInstr *NewMI = tii_->commuteInstruction(DefMI);
 320   if (!NewMI)
 321     return false;
 322   if (NewMI != DefMI) {
 323     li_->ReplaceMachineInstrInMaps(DefMI, NewMI);
 324     MBB->insert(DefMI, NewMI);
 325     MBB->erase(DefMI);
 326   }
 327   unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
 328   NewMI->getOperand(OpIdx).setIsKill();
 329
 330   bool BHasPHIKill = BValNo->hasPHIKill;
 331   SmallVector<VNInfo*, 4> BDeadValNos;
 332   SmallVector<unsigned, 4> BKills;
 333   std::map<unsigned, unsigned> BExtend;
 334
 335   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
 336   // A = or A, B
 337   // ...
 338   // B = A
 339   // ...
 340   // C = A<kill>
 341   // ...
 342   //   = B
 343   //
 344   // then do not add kills of A to the newly created B interval.
 345   bool Extended = BLR->end > ALR->end && ALR->end != ALR->start;
 346   if (Extended)
 347     BExtend[ALR->end] = BLR->end;
 348
 349   // Update uses of IntA of the specific Val# with IntB.
 350   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
 351          UE = mri_->use_end(); UI != UE;) {
 352     MachineOperand &UseMO = UI.getOperand();
 353     MachineInstr *UseMI = &*UI;
 354     ++UI;
 355     if (JoinedCopies.count(UseMI))
 356       continue;
 357     unsigned UseIdx = li_->getInstructionIndex(UseMI);
 358     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 359     if (ULR == IntA.end() || ULR->valno != AValNo)
 360       continue;
 361     UseMO.setReg(NewReg);
 362     if (UseMI == CopyMI)
 363       continue;
 364     if (UseMO.isKill()) {
 365       if (Extended)
 366         UseMO.setIsKill(false);
 367       else
 368         BKills.push_back(li_->getUseIndex(UseIdx)+1);
 369     }
 370     unsigned SrcReg, DstReg;
 371     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg))
 372       continue;
 373     if (DstReg == IntB.reg) {
 374       // This copy will become a noop. If it's defining a new val#,
 375       // remove that val# as well. However this live range is being
 376       // extended to the end of the existing live range defined by the copy.
 377       unsigned DefIdx = li_->getDefIndex(UseIdx);
 378       const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
 379       BHasPHIKill |= DLR->valno->hasPHIKill;
 380       assert(DLR->valno->def == DefIdx);
 381       BDeadValNos.push_back(DLR->valno);
 382       BExtend[DLR->start] = DLR->end;
 383       JoinedCopies.insert(UseMI);
 384       // If this is a kill but it's going to be removed, the last use
 385       // of the same val# is the new kill.
 386       if (UseMO.isKill())
 387         BKills.pop_back();
 388     }
 389   }
 390
 391   // We need to insert a new liverange: [ALR.start, LastUse). It may be we can
 392   // simply extend BLR if CopyMI doesn't end the range.
 393   DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
 394
 395   // Remove val#'s defined by copies that will be coalesced away.
 396   for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i)
 397     IntB.removeValNo(BDeadValNos[i]);
 398
 399   // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
 400   // is updated. Kills are also updated.
 401   VNInfo *ValNo = BValNo;
 402   ValNo->def = AValNo->def;
 403   ValNo->copy = NULL;
 404   for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) {
 405     unsigned Kill = ValNo->kills[j];
 406     if (Kill != BLR->end)
 407       BKills.push_back(Kill);
 408   }
 409   ValNo->kills.clear();
 410   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 411        AI != AE; ++AI) {
 412     if (AI->valno != AValNo) continue;
 413     unsigned End = AI->end;
 414     std::map<unsigned, unsigned>::iterator EI = BExtend.find(End);
 415     if (EI != BExtend.end())
 416       End = EI->second;
 417     IntB.addRange(LiveRange(AI->start, End, ValNo));
 418   }
 419   IntB.addKills(ValNo, BKills);
 420   ValNo->hasPHIKill = BHasPHIKill;
 421
 422   DOUT << "   result = "; IntB.print(DOUT, tri_);
 423   DOUT << "\n";
 424
 425   DOUT << "\nShortening: "; IntA.print(DOUT, tri_);
 426   IntA.removeValNo(AValNo);
 427   DOUT << "   result = "; IntA.print(DOUT, tri_);
 428   DOUT << "\n";
 429
 430   ++numCommutes;
 431   return true;
 432 }
 433
 434 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
 435 /// computation, replace the copy by rematerialize the definition.
 436 bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
 437                                                        unsigned DstReg,
 438                                                        MachineInstr *CopyMI) {
 439   unsigned CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI));
 440   LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
 441   if (SrcLR == SrcInt.end()) // Should never happen!
 442     return false;
 443   VNInfo *ValNo = SrcLR->valno;
 444   // If other defs can reach uses of this def, then it's not safe to perform
 445   // the optimization.
 446   if (ValNo->def == ~0U || ValNo->def == ~1U || ValNo->hasPHIKill)
 447     return false;
 448   MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def);
 449   const TargetInstrDesc &TID = DefMI->getDesc();
 450   if (!TID.isAsCheapAsAMove())
 451     return false;
 452   bool SawStore = false;
 453   if (!DefMI->isSafeToMove(tii_, SawStore))
 454     return false;
 455
 456   unsigned DefIdx = li_->getDefIndex(CopyIdx);
 457   const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx);
 458   DLR->valno->copy = NULL;
 459
 460   MachineBasicBlock::iterator MII = CopyMI;
 461   MachineBasicBlock *MBB = CopyMI->getParent();
 462   tii_->reMaterialize(*MBB, MII, DstReg, DefMI);
 463   MachineInstr *NewMI = prior(MII);
 464   // CopyMI may have implicit instructions, transfer them over to the newly
 465   // rematerialized instruction. And update implicit def interval valnos.
 466   for (unsigned i = CopyMI->getDesc().getNumOperands(),
 467          e = CopyMI->getNumOperands(); i != e; ++i) {
 468     MachineOperand &MO = CopyMI->getOperand(i);
 469     if (MO.isRegister() && MO.isImplicit())
 470       NewMI->addOperand(MO);
 471     if (MO.isDef() && li_->hasInterval(MO.getReg())) {
 472       unsigned Reg = MO.getReg();
 473       DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
 474       if (DLR && DLR->valno->copy == CopyMI)
 475         DLR->valno->copy = NULL;
 476     }
 477   }
 478
 479   li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
 480   CopyMI->eraseFromParent();
 481   ReMatCopies.insert(CopyMI);
 482   ReMatDefs.insert(DefMI);
 483   ++NumReMats;
 484   return true;
 485 }
 486
 487 /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy.
 488 ///
 489 bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI,
 490                                               unsigned DstReg) const {
 491   MachineBasicBlock *MBB = CopyMI->getParent();
 492   const MachineLoop *L = loopInfo->getLoopFor(MBB);
 493   if (!L)
 494     return false;
 495   if (MBB != L->getLoopLatch())
 496     return false;
 497
 498   LiveInterval &LI = li_->getInterval(DstReg);
 499   unsigned DefIdx = li_->getInstructionIndex(CopyMI);
 500   LiveInterval::const_iterator DstLR =
 501     LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx));
 502   if (DstLR == LI.end())
 503     return false;
 504   unsigned KillIdx = li_->getMBBEndIdx(MBB) + 1;
 505   if (DstLR->valno->kills.size() == 1 &&
 506       DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill)
 507     return true;
 508   return false;
 509 }
 510
 511 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 512 /// update the subregister number if it is not zero. If DstReg is a
 513 /// physical register and the existing subregister number of the def / use
 514 /// being updated is not zero, make sure to set it to the correct physical
 515 /// subregister.
 516 void
 517 SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
 518                                             unsigned SubIdx) {
 519   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 520   if (DstIsPhys && SubIdx) {
 521     // Figure out the real physical register we are updating with.
 522     DstReg = tri_->getSubReg(DstReg, SubIdx);
 523     SubIdx = 0;
 524   }
 525
 526   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
 527          E = mri_->reg_end(); I != E; ) {
 528     MachineOperand &O = I.getOperand();
 529     MachineInstr *UseMI = &*I;
 530     ++I;
 531     unsigned OldSubIdx = O.getSubReg();
 532     if (DstIsPhys) {
 533       unsigned UseDstReg = DstReg;
 534       if (OldSubIdx)
 535           UseDstReg = tri_->getSubReg(DstReg, OldSubIdx);
 536
 537       unsigned CopySrcReg, CopyDstReg;
 538       if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
 539           CopySrcReg != CopyDstReg &&
 540           CopySrcReg == SrcReg && CopyDstReg != UseDstReg) {
 541         // If the use is a copy and it won't be coalesced away, and its source
 542         // is defined by a trivial computation, try to rematerialize it instead.
 543         if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg,UseMI))
 544           continue;
 545       }
 546
 547       O.setReg(UseDstReg);
 548       O.setSubReg(0);
 549       continue;
 550     }
 551
 552     // Sub-register indexes goes from small to large. e.g.
 553     // RAX: 1 -> AL, 2 -> AX, 3 -> EAX
 554     // EAX: 1 -> AL, 2 -> AX
 555     // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose
 556     // sub-register 2 is also AX.
 557     if (SubIdx && OldSubIdx && SubIdx != OldSubIdx)
 558       assert(OldSubIdx < SubIdx && "Conflicting sub-register index!");
 559     else if (SubIdx)
 560       O.setSubReg(SubIdx);
 561     // Remove would-be duplicated kill marker.
 562     if (O.isKill() && UseMI->killsRegister(DstReg))
 563       O.setIsKill(false);
 564     O.setReg(DstReg);
 565
 566     // After updating the operand, check if the machine instruction has
 567     // become a copy. If so, update its val# information.
 568     const TargetInstrDesc &TID = UseMI->getDesc();
 569     unsigned CopySrcReg, CopyDstReg;
 570     if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 &&
 571         tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
 572         CopySrcReg != CopyDstReg &&
 573         (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
 574          allocatableRegs_[CopyDstReg])) {
 575       LiveInterval &LI = li_->getInterval(CopyDstReg);
 576       unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(UseMI));
 577       const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx);
 578       if (DLR->valno->def == DefIdx)
 579         DLR->valno->copy = UseMI;
 580     }
 581   }
 582 }
 583
 584 /// RemoveDeadImpDef - Remove implicit_def instructions which are "re-defining"
 585 /// registers due to insert_subreg coalescing. e.g.
 586 /// r1024 = op
 587 /// r1025 = implicit_def
 588 /// r1025 = insert_subreg r1025, r1024
 589 ///       = op r1025
 590 /// =>
 591 /// r1025 = op
 592 /// r1025 = implicit_def
 593 /// r1025 = insert_subreg r1025, r1025
 594 ///       = op r1025
 595 void
 596 SimpleRegisterCoalescing::RemoveDeadImpDef(unsigned Reg, LiveInterval &LI) {
 597   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
 598          E = mri_->reg_end(); I != E; ) {
 599     MachineOperand &O = I.getOperand();
 600     MachineInstr *DefMI = &*I;
 601     ++I;
 602     if (!O.isDef())
 603       continue;
 604     if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF)
 605       continue;
 606     if (!LI.liveBeforeAndAt(li_->getInstructionIndex(DefMI)))
 607       continue;
 608     li_->RemoveMachineInstrFromMaps(DefMI);
 609     DefMI->eraseFromParent();
 610   }
 611 }
 612
 613 /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate
 614 /// due to live range lengthening as the result of coalescing.
 615 void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg,
 616                                                       LiveInterval &LI) {
 617   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
 618          UE = mri_->use_end(); UI != UE; ++UI) {
 619     MachineOperand &UseMO = UI.getOperand();
 620     if (UseMO.isKill()) {
 621       MachineInstr *UseMI = UseMO.getParent();
 622       unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
 623       if (JoinedCopies.count(UseMI))
 624         continue;
 625       const LiveRange *UI = LI.getLiveRangeContaining(UseIdx);
 626       if (!UI || !LI.isKill(UI->valno, UseIdx+1))
 627         UseMO.setIsKill(false);
 628     }
 629   }
 630 }
 631
 632 /// removeRange - Wrapper for LiveInterval::removeRange. This removes a range
 633 /// from a physical register live interval as well as from the live intervals
 634 /// of its sub-registers.
 635 static void removeRange(LiveInterval &li, unsigned Start, unsigned End,
 636                         LiveIntervals *li_, const TargetRegisterInfo *tri_) {
 637   li.removeRange(Start, End, true);
 638   if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
 639     for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
 640       if (!li_->hasInterval(*SR))
 641         continue;
 642       LiveInterval &sli = li_->getInterval(*SR);
 643       unsigned RemoveEnd = Start;
 644       while (RemoveEnd != End) {
 645         LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start);
 646         if (LR == sli.end())
 647           break;
 648         RemoveEnd = (LR->end < End) ? LR->end : End;
 649         sli.removeRange(Start, RemoveEnd, true);
 650         Start = RemoveEnd;
 651       }
 652     }
 653   }
 654 }
 655
 656 /// removeIntervalIfEmpty - Check if the live interval of a physical register
 657 /// is empty, if so remove it and also remove the empty intervals of its
 658 /// sub-registers. Return true if live interval is removed.
 659 static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
 660                                   const TargetRegisterInfo *tri_) {
 661   if (li.empty()) {
 662     if (TargetRegisterInfo::isPhysicalRegister(li.reg))
 663       for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
 664         if (!li_->hasInterval(*SR))
 665           continue;
 666         LiveInterval &sli = li_->getInterval(*SR);
 667         if (sli.empty())
 668           li_->removeInterval(*SR);
 669       }
 670     li_->removeInterval(li.reg);
 671     return true;
 672   }
 673   return false;
 674 }
 675
 676 /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
 677 /// Return true if live interval is removed.
 678 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
 679                                                         MachineInstr *CopyMI) {
 680   unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
 681   LiveInterval::iterator MLR =
 682     li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
 683   if (MLR == li.end())
 684     return false;  // Already removed by ShortenDeadCopySrcLiveRange.
 685   unsigned RemoveStart = MLR->start;
 686   unsigned RemoveEnd = MLR->end;
 687   // Remove the liverange that's defined by this.
 688   if (RemoveEnd == li_->getDefIndex(CopyIdx)+1) {
 689     removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
 690     return removeIntervalIfEmpty(li, li_, tri_);
 691   }
 692   return false;
 693 }
 694
 695 /// PropagateDeadness - Propagate the dead marker to the instruction which
 696 /// defines the val#.
 697 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
 698                               unsigned &LRStart, LiveIntervals *li_,
 699                               const TargetRegisterInfo* tri_) {
 700   MachineInstr *DefMI =
 701     li_->getInstructionFromIndex(li_->getDefIndex(LRStart));
 702   if (DefMI && DefMI != CopyMI) {
 703     int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false, tri_);
 704     if (DeadIdx != -1) {
 705       DefMI->getOperand(DeadIdx).setIsDead();
 706       // A dead def should have a single cycle interval.
 707       ++LRStart;
 708     }
 709   }
 710 }
 711
 712 /// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
 713 /// fallthoughs to SuccMBB.
 714 static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
 715                                   MachineBasicBlock *SuccMBB,
 716                                   const TargetInstrInfo *tii_) {
 717   if (MBB == SuccMBB)
 718     return true;
 719   MachineBasicBlock *TBB = 0, *FBB = 0;
 720   SmallVector<MachineOperand, 4> Cond;
 721   return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
 722     MBB->isSuccessor(SuccMBB);
 723 }
 724
 725 /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
 726 /// extended by a dead copy. Mark the last use (if any) of the val# as kill as
 727 /// ends the live range there. If there isn't another use, then this live range
 728 /// is dead. Return true if live interval is removed.
 729 bool
 730 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
 731                                                       MachineInstr *CopyMI) {
 732   unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
 733   if (CopyIdx == 0) {
 734     // FIXME: special case: function live in. It can be a general case if the
 735     // first instruction index starts at > 0 value.
 736     assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
 737     // Live-in to the function but dead. Remove it from entry live-in set.
 738     if (mf_->begin()->isLiveIn(li.reg))
 739       mf_->begin()->removeLiveIn(li.reg);
 740     const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
 741     removeRange(li, LR->start, LR->end, li_, tri_);
 742     return removeIntervalIfEmpty(li, li_, tri_);
 743   }
 744
 745   LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx-1);
 746   if (LR == li.end())
 747     // Livein but defined by a phi.
 748     return false;
 749
 750   unsigned RemoveStart = LR->start;
 751   unsigned RemoveEnd = li_->getDefIndex(CopyIdx)+1;
 752   if (LR->end > RemoveEnd)
 753     // More uses past this copy? Nothing to do.
 754     return false;
 755
 756   MachineBasicBlock *CopyMBB = CopyMI->getParent();
 757   unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
 758   unsigned LastUseIdx;
 759   MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg,
 760                                             LastUseIdx);
 761   if (LastUse) {
 762     MachineInstr *LastUseMI = LastUse->getParent();
 763     if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
 764       // r1024 = op
 765       // ...
 766       // BB1:
 767       //       = r1024
 768       //
 769       // BB2:
 770       // r1025<dead> = r1024<kill>
 771       if (MBBStart < LR->end)
 772         removeRange(li, MBBStart, LR->end, li_, tri_);
 773       return false;
 774     }
 775
 776     // There are uses before the copy, just shorten the live range to the end
 777     // of last use.
 778     LastUse->setIsKill();
 779     removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
 780     unsigned SrcReg, DstReg;
 781     if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg) &&
 782         DstReg == li.reg) {
 783       // Last use is itself an identity code.
 784       int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_);
 785       LastUseMI->getOperand(DeadIdx).setIsDead();
 786     }
 787     return false;
 788   }
 789
 790   // Is it livein?
 791   if (LR->start <= MBBStart && LR->end > MBBStart) {
 792     if (LR->start == 0) {
 793       assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
 794       // Live-in to the function but dead. Remove it from entry live-in set.
 795       mf_->begin()->removeLiveIn(li.reg);
 796     }
 797     // FIXME: Shorten intervals in BBs that reaches this BB.
 798   }
 799
 800   if (LR->valno->def == RemoveStart)
 801     // If the def MI defines the val#, propagate the dead marker.
 802     PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
 803
 804   removeRange(li, RemoveStart, LR->end, li_, tri_);
 805   return removeIntervalIfEmpty(li, li_, tri_);
 806 }
 807
 808 /// CanCoalesceWithImpDef - Returns true if the specified copy instruction
 809 /// from an implicit def to another register can be coalesced away.
 810 bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI,
 811                                                      LiveInterval &li,
 812                                                      LiveInterval &ImpLi) const{
 813   if (!CopyMI->killsRegister(ImpLi.reg))
 814     return false;
 815   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
 816   LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx);
 817   if (LR == li.end())
 818     return false;
 819   if (LR->valno->hasPHIKill)
 820     return false;
 821   if (LR->valno->def != CopyIdx)
 822     return false;
 823   // Make sure all of val# uses are copies.
 824   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(li.reg),
 825          UE = mri_->use_end(); UI != UE;) {
 826     MachineInstr *UseMI = &*UI;
 827     ++UI;
 828     if (JoinedCopies.count(UseMI))
 829       continue;
 830     unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
 831     LiveInterval::iterator ULR = li.FindLiveRangeContaining(UseIdx);
 832     if (ULR == li.end() || ULR->valno != LR->valno)
 833       continue;
 834     // If the use is not a use, then it's not safe to coalesce the move.
 835     unsigned SrcReg, DstReg;
 836     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg)) {
 837       if (UseMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG &&
 838           UseMI->getOperand(1).getReg() == li.reg)
 839         continue;
 840       return false;
 841     }
 842   }
 843   return true;
 844 }
 845
 846
 847 /// RemoveCopiesFromValNo - The specified value# is defined by an implicit
 848 /// def and it is being removed. Turn all copies from this value# into
 849 /// identity copies so they will be removed.
 850 void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li,
 851                                                      VNInfo *VNI) {
 852   SmallVector<MachineInstr*, 4> ImpDefs;
 853   MachineOperand *LastUse = NULL;
 854   unsigned LastUseIdx = li_->getUseIndex(VNI->def);
 855   for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg),
 856          RE = mri_->reg_end(); RI != RE;) {
 857     MachineOperand *MO = &RI.getOperand();
 858     MachineInstr *MI = &*RI;
 859     ++RI;
 860     if (MO->isDef()) {
 861       if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
 862         ImpDefs.push_back(MI);
 863       }
 864       continue;
 865     }
 866     if (JoinedCopies.count(MI))
 867       continue;
 868     unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(MI));
 869     LiveInterval::iterator ULR = li.FindLiveRangeContaining(UseIdx);
 870     if (ULR == li.end() || ULR->valno != VNI)
 871       continue;
 872     // If the use is a copy, turn it into an identity copy.
 873     unsigned SrcReg, DstReg;
 874     if (tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == li.reg) {
 875       // Each use MI may have multiple uses of this register. Change them all.
 876       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 877         MachineOperand &MO = MI->getOperand(i);
 878         if (MO.isRegister() && MO.getReg() == li.reg)
 879           MO.setReg(DstReg);
 880       }
 881       JoinedCopies.insert(MI);
 882     } else if (UseIdx > LastUseIdx) {
 883       LastUseIdx = UseIdx;
 884       LastUse = MO;
 885     }
 886   }
 887   if (LastUse)
 888     LastUse->setIsKill();
 889   else {
 890     // Remove dead implicit_def's.
 891     while (!ImpDefs.empty()) {
 892       MachineInstr *ImpDef = ImpDefs.back();
 893       ImpDefs.pop_back();
 894       li_->RemoveMachineInstrFromMaps(ImpDef);
 895       ImpDef->eraseFromParent();
 896     }
 897   }
 898 }
 899
 900 /// getMatchingSuperReg - Return a super-register of the specified register
 901 /// Reg so its sub-register of index SubIdx is Reg.
 902 static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx,
 903                                     const TargetRegisterClass *RC,
 904                                     const TargetRegisterInfo* TRI) {
 905   for (const unsigned *SRs = TRI->getSuperRegisters(Reg);
 906        unsigned SR = *SRs; ++SRs)
 907     if (Reg == TRI->getSubReg(SR, SubIdx) && RC->contains(SR))
 908       return SR;
 909   return 0;
 910 }
 911
 912 /// isProfitableToCoalesceToSubRC - Given that register class of DstReg is
 913 /// a subset of the register class of SrcReg, return true if it's profitable
 914 /// to coalesce the two registers.
 915 bool
 916 SimpleRegisterCoalescing::isProfitableToCoalesceToSubRC(unsigned SrcReg,
 917                                                         unsigned DstReg,
 918                                                         MachineBasicBlock *MBB){
 919   if (!CrossClassJoin)
 920     return false;
 921
 922   // First let's make sure all uses are in the same MBB.
 923   for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(SrcReg),
 924          RE = mri_->reg_end(); RI != RE; ++RI) {
 925     MachineInstr &MI = *RI;
 926     if (MI.getParent() != MBB)
 927       return false;
 928   }
 929   for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(DstReg),
 930          RE = mri_->reg_end(); RI != RE; ++RI) {
 931     MachineInstr &MI = *RI;
 932     if (MI.getParent() != MBB)
 933       return false;
 934   }
 935
 936   // Then make sure the intervals are *short*.
 937   LiveInterval &SrcInt = li_->getInterval(SrcReg);
 938   LiveInterval &DstInt = li_->getInterval(DstReg);
 939   unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt);
 940   unsigned DstSize = li_->getApproximateInstructionCount(DstInt);
 941   const TargetRegisterClass *RC = mri_->getRegClass(DstReg);
 942   unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
 943   return (SrcSize + DstSize) <= Threshold;
 944 }
 945
 946 /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual
 947 /// register with a physical register, check if any of the virtual register
 948 /// operand is a sub-register use or def. If so, make sure it won't result
 949 /// in an illegal extract_subreg or insert_subreg instruction. e.g.
 950 /// vr1024 = extract_subreg vr1025, 1
 951 /// ...
 952 /// vr1024 = mov8rr AH
 953 /// If vr1024 is coalesced with AH, the extract_subreg is now illegal since
 954 /// AH does not have a super-reg whose sub-register 1 is AH.
 955 bool
 956 SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI,
 957                                                       unsigned VirtReg,
 958                                                       unsigned PhysReg) {
 959   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(VirtReg),
 960          E = mri_->reg_end(); I != E; ++I) {
 961     MachineOperand &O = I.getOperand();
 962     MachineInstr *MI = &*I;
 963     if (MI == CopyMI || JoinedCopies.count(MI))
 964       continue;
 965     unsigned SubIdx = O.getSubReg();
 966     if (SubIdx && !tri_->getSubReg(PhysReg, SubIdx))
 967       return true;
 968     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
 969       SubIdx = MI->getOperand(2).getImm();
 970       if (O.isUse() && !tri_->getSubReg(PhysReg, SubIdx))
 971         return true;
 972       if (O.isDef()) {
 973         unsigned SrcReg = MI->getOperand(1).getReg();
 974         const TargetRegisterClass *RC =
 975           TargetRegisterInfo::isPhysicalRegister(SrcReg)
 976           ? tri_->getPhysicalRegisterRegClass(SrcReg)
 977           : mri_->getRegClass(SrcReg);
 978         if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_))
 979           return true;
 980       }
 981     }
 982     if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
 983       SubIdx = MI->getOperand(3).getImm();
 984       if (VirtReg == MI->getOperand(0).getReg()) {
 985         if (!tri_->getSubReg(PhysReg, SubIdx))
 986           return true;
 987       } else {
 988         unsigned DstReg = MI->getOperand(0).getReg();
 989         const TargetRegisterClass *RC =
 990           TargetRegisterInfo::isPhysicalRegister(DstReg)
 991           ? tri_->getPhysicalRegisterRegClass(DstReg)
 992           : mri_->getRegClass(DstReg);
 993         if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_))
 994           return true;
 995       }
 996     }
 997   }
 998   return false;
 999 }
1000
1001
1002 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
1003 /// which are the src/dst of the copy instruction CopyMI.  This returns true
1004 /// if the copy was successfully coalesced away. If it is not currently
1005 /// possible to coalesce this interval, but it may be possible if other
1006 /// things get coalesced, then it returns true by reference in 'Again'.
1007 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
1008   MachineInstr *CopyMI = TheCopy.MI;
1009
1010   Again = false;
1011   if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI))
1012     return false; // Already done.
1013
1014   DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI;
1015
1016   unsigned SrcReg;
1017   unsigned DstReg;
1018   bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG;
1019   bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG;
1020   unsigned SubIdx = 0;
1021   if (isExtSubReg) {
1022     DstReg = CopyMI->getOperand(0).getReg();
1023     SrcReg = CopyMI->getOperand(1).getReg();
1024   } else if (isInsSubReg) {
1025     if (CopyMI->getOperand(2).getSubReg()) {
1026       DOUT << "\tSource of insert_subreg is already coalesced "
1027            << "to another register.\n";
1028       return false;  // Not coalescable.
1029     }
1030     DstReg = CopyMI->getOperand(0).getReg();
1031     SrcReg = CopyMI->getOperand(2).getReg();
1032   } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
1033     assert(0 && "Unrecognized copy instruction!");
1034     return false;
1035   }
1036
1037   // If they are already joined we continue.
1038   if (SrcReg == DstReg) {
1039     DOUT << "\tCopy already coalesced.\n";
1040     return false;  // Not coalescable.
1041   }
1042
1043   bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
1044   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1045
1046   // If they are both physical registers, we cannot join them.
1047   if (SrcIsPhys && DstIsPhys) {
1048     DOUT << "\tCan not coalesce physregs.\n";
1049     return false;  // Not coalescable.
1050   }
1051
1052   // We only join virtual registers with allocatable physical registers.
1053   if (SrcIsPhys && !allocatableRegs_[SrcReg]) {
1054     DOUT << "\tSrc reg is unallocatable physreg.\n";
1055     return false;  // Not coalescable.
1056   }
1057   if (DstIsPhys && !allocatableRegs_[DstReg]) {
1058     DOUT << "\tDst reg is unallocatable physreg.\n";
1059     return false;  // Not coalescable.
1060   }
1061
1062   // Should be non-null only when coalescing to a sub-register class.
1063   const TargetRegisterClass *SubRC = NULL;
1064   MachineBasicBlock *CopyMBB = CopyMI->getParent();
1065   unsigned RealDstReg = 0;
1066   unsigned RealSrcReg = 0;
1067   if (isExtSubReg || isInsSubReg) {
1068     SubIdx = CopyMI->getOperand(isExtSubReg ? 2 : 3).getImm();
1069     if (SrcIsPhys && isExtSubReg) {
1070       // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be
1071       // coalesced with AX.
1072       unsigned DstSubIdx = CopyMI->getOperand(0).getSubReg();
1073       if (DstSubIdx) {
1074         // r1024<2> = EXTRACT_SUBREG EAX, 2. Then r1024 has already been
1075         // coalesced to a larger register so the subreg indices cancel out.
1076         if (DstSubIdx != SubIdx) {
1077           DOUT << "\t Sub-register indices mismatch.\n";
1078           return false; // Not coalescable.
1079         }
1080       } else
1081         SrcReg = tri_->getSubReg(SrcReg, SubIdx);
1082       SubIdx = 0;
1083     } else if (DstIsPhys && isInsSubReg) {
1084       // EAX = INSERT_SUBREG EAX, r1024, 0
1085       unsigned SrcSubIdx = CopyMI->getOperand(2).getSubReg();
1086       if (SrcSubIdx) {
1087         // EAX = INSERT_SUBREG EAX, r1024<2>, 2 Then r1024 has already been
1088         // coalesced to a larger register so the subreg indices cancel out.
1089         if (SrcSubIdx != SubIdx) {
1090           DOUT << "\t Sub-register indices mismatch.\n";
1091           return false; // Not coalescable.
1092         }
1093       } else
1094         DstReg = tri_->getSubReg(DstReg, SubIdx);
1095       SubIdx = 0;
1096     } else if ((DstIsPhys && isExtSubReg) || (SrcIsPhys && isInsSubReg)) {
1097       // If this is a extract_subreg where dst is a physical register, e.g.
1098       // cl = EXTRACT_SUBREG reg1024, 1
1099       // then create and update the actual physical register allocated to RHS.
1100       // Ditto for
1101       // reg1024 = INSERT_SUBREG r1024, cl, 1
1102       if (CopyMI->getOperand(1).getSubReg()) {
1103         DOUT << "\tSrc of extract_ / insert_subreg already coalesced with reg"
1104              << " of a super-class.\n";
1105         return false; // Not coalescable.
1106       }
1107       const TargetRegisterClass *RC =
1108         mri_->getRegClass(isExtSubReg ? SrcReg : DstReg);
1109       if (isExtSubReg) {
1110         RealDstReg = getMatchingSuperReg(DstReg, SubIdx, RC, tri_);
1111         assert(RealDstReg && "Invalid extract_subreg instruction!");
1112       } else {
1113         RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_);
1114         assert(RealSrcReg && "Invalid extract_subreg instruction!");
1115       }
1116
1117       // For this type of EXTRACT_SUBREG, conservatively
1118       // check if the live interval of the source register interfere with the
1119       // actual super physical register we are trying to coalesce with.
1120       unsigned PhysReg = isExtSubReg ? RealDstReg : RealSrcReg;
1121       LiveInterval &RHS = li_->getInterval(isExtSubReg ? SrcReg : DstReg);
1122       if (li_->hasInterval(PhysReg) &&
1123           RHS.overlaps(li_->getInterval(PhysReg))) {
1124         DOUT << "Interfere with register ";
1125         DEBUG(li_->getInterval(PhysReg).print(DOUT, tri_));
1126         return false; // Not coalescable
1127       }
1128       for (const unsigned* SR = tri_->getSubRegisters(PhysReg); *SR; ++SR)
1129         if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
1130           DOUT << "Interfere with sub-register ";
1131           DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
1132           return false; // Not coalescable
1133         }
1134       SubIdx = 0;
1135     } else {
1136       unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg()
1137         : CopyMI->getOperand(2).getSubReg();
1138       if (OldSubIdx) {
1139         if (OldSubIdx == SubIdx &&
1140             !differingRegisterClasses(SrcReg, DstReg, SubRC))
1141           // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been
1142           // coalesced to a larger register so the subreg indices cancel out.
1143           // Also check if the other larger register is of the same register
1144           // class as the would be resulting register.
1145           SubIdx = 0;
1146         else {
1147           DOUT << "\t Sub-register indices mismatch.\n";
1148           return false; // Not coalescable.
1149         }
1150       }
1151       if (SubIdx) {
1152         unsigned LargeReg = isExtSubReg ? SrcReg : DstReg;
1153         unsigned SmallReg = isExtSubReg ? DstReg : SrcReg;
1154         unsigned LargeRegSize =
1155           li_->getApproximateInstructionCount(li_->getInterval(LargeReg));
1156         unsigned SmallRegSize =
1157           li_->getApproximateInstructionCount(li_->getInterval(SmallReg));
1158         const TargetRegisterClass *RC = mri_->getRegClass(SmallReg);
1159         unsigned Threshold = allocatableRCRegs_[RC].count();
1160         // Be conservative. If both sides are virtual registers, do not coalesce
1161         // if this will cause a high use density interval to target a smaller
1162         // set of registers.
1163         if (SmallRegSize > Threshold || LargeRegSize > Threshold) {
1164           if ((float)std::distance(mri_->use_begin(SmallReg),
1165                                    mri_->use_end()) / SmallRegSize <
1166               (float)std::distance(mri_->use_begin(LargeReg),
1167                                    mri_->use_end()) / LargeRegSize) {
1168             Again = true;  // May be possible to coalesce later.
1169             return false;
1170           }
1171         }
1172       }
1173     }
1174   } else if (differingRegisterClasses(SrcReg, DstReg, SubRC)) {
1175     // FIXME: What if the resul of a EXTRACT_SUBREG is then coalesced
1176     // with another? If it's the resulting destination register, then
1177     // the subidx must be propagated to uses (but only those defined
1178     // by the EXTRACT_SUBREG). If it's being coalesced into another
1179     // register, it should be safe because register is assumed to have
1180     // the register class of the super-register.
1181
1182     if (!SubRC || !isProfitableToCoalesceToSubRC(SrcReg, DstReg, CopyMBB)) {
1183       // If they are not of the same register class, we cannot join them.
1184       DOUT << "\tSrc/Dest are different register classes.\n";
1185       // Allow the coalescer to try again in case either side gets coalesced to
1186       // a physical register that's compatible with the other side. e.g.
1187       // r1024 = MOV32to32_ r1025
1188       // but later r1024 is assigned EAX then r1025 may be coalesced with EAX.
1189       Again = true;  // May be possible to coalesce later.
1190       return false;
1191     }
1192   }
1193
1194   // Will it create illegal extract_subreg / insert_subreg?
1195   if (SrcIsPhys && HasIncompatibleSubRegDefUse(CopyMI, DstReg, SrcReg))
1196     return false;
1197   if (DstIsPhys && HasIncompatibleSubRegDefUse(CopyMI, SrcReg, DstReg))
1198     return false;
1199
1200   LiveInterval &SrcInt = li_->getInterval(SrcReg);
1201   LiveInterval &DstInt = li_->getInterval(DstReg);
1202   assert(SrcInt.reg == SrcReg && DstInt.reg == DstReg &&
1203          "Register mapping is horribly broken!");
1204
1205   DOUT << "\t\tInspecting "; SrcInt.print(DOUT, tri_);
1206   DOUT << " and "; DstInt.print(DOUT, tri_);
1207   DOUT << ": ";
1208
1209   // If one interval is earlyclobber and the other is overlaps-earlyclobber,
1210   // we cannot coalesce them.
1211   if ((SrcInt.isEarlyClobber && DstInt.overlapsEarlyClobber) ||
1212       (DstInt.isEarlyClobber && SrcInt.overlapsEarlyClobber)) {
1213     DOUT << "\t\tCannot join due to earlyclobber.";
1214     return false;
1215   }
1216
1217   // Check if it is necessary to propagate "isDead" property.
1218   if (!isExtSubReg && !isInsSubReg) {
1219     MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false);
1220     bool isDead = mopd->isDead();
1221
1222     // We need to be careful about coalescing a source physical register with a
1223     // virtual register. Once the coalescing is done, it cannot be broken and
1224     // these are not spillable! If the destination interval uses are far away,
1225     // think twice about coalescing them!
1226     if (!isDead && (SrcIsPhys || DstIsPhys)) {
1227       LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
1228       unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg;
1229       unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg;
1230       const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg);
1231       unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
1232       if (TheCopy.isBackEdge)
1233         Threshold *= 2; // Favors back edge copies.
1234
1235       // If the virtual register live interval is long but it has low use desity,
1236       // do not join them, instead mark the physical register as its allocation
1237       // preference.
1238       unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
1239       if (Length > Threshold &&
1240           (((float)std::distance(mri_->use_begin(JoinVReg),
1241                               mri_->use_end()) / Length) < (1.0 / Threshold))) {
1242         JoinVInt.preference = JoinPReg;
1243         ++numAborts;
1244         DOUT << "\tMay tie down a physical register, abort!\n";
1245         Again = true;  // May be possible to coalesce later.
1246         return false;
1247       }
1248     }
1249   }
1250
1251   // Okay, attempt to join these two intervals.  On failure, this returns false.
1252   // Otherwise, if one of the intervals being joined is a physreg, this method
1253   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
1254   // been modified, so we can use this information below to update aliases.
1255   bool Swapped = false;
1256   // If SrcInt is implicitly defined, it's safe to coalesce.
1257   bool isEmpty = SrcInt.empty();
1258   if (isEmpty && !CanCoalesceWithImpDef(CopyMI, DstInt, SrcInt)) {
1259     // Only coalesce an empty interval (defined by implicit_def) with
1260     // another interval which has a valno defined by the CopyMI and the CopyMI
1261     // is a kill of the implicit def.
1262     DOUT << "Not profitable!\n";
1263     return false;
1264   }
1265
1266   if (!isEmpty && !JoinIntervals(DstInt, SrcInt, Swapped)) {
1267     // Coalescing failed.
1268
1269     // If definition of source is defined by trivial computation, try
1270     // rematerializing it.
1271     if (!isExtSubReg && !isInsSubReg &&
1272         ReMaterializeTrivialDef(SrcInt, DstInt.reg, CopyMI))
1273       return true;
1274
1275     // If we can eliminate the copy without merging the live ranges, do so now.
1276     if (!isExtSubReg && !isInsSubReg &&
1277         (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) ||
1278          RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) {
1279       JoinedCopies.insert(CopyMI);
1280       return true;
1281     }
1282
1283     // Otherwise, we are unable to join the intervals.
1284     DOUT << "Interference!\n";
1285     Again = true;  // May be possible to coalesce later.
1286     return false;
1287   }
1288
1289   LiveInterval *ResSrcInt = &SrcInt;
1290   LiveInterval *ResDstInt = &DstInt;
1291   if (Swapped) {
1292     std::swap(SrcReg, DstReg);
1293     std::swap(ResSrcInt, ResDstInt);
1294   }
1295   assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
1296          "LiveInterval::join didn't work right!");
1297
1298   // If we're about to merge live ranges into a physical register live range,
1299   // we have to update any aliased register's live ranges to indicate that they
1300   // have clobbered values for this range.
1301   if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
1302     // If this is a extract_subreg where dst is a physical register, e.g.
1303     // cl = EXTRACT_SUBREG reg1024, 1
1304     // then create and update the actual physical register allocated to RHS.
1305     if (RealDstReg || RealSrcReg) {
1306       LiveInterval &RealInt =
1307         li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg);
1308       SmallSet<const VNInfo*, 4> CopiedValNos;
1309       for (LiveInterval::Ranges::const_iterator I = ResSrcInt->ranges.begin(),
1310              E = ResSrcInt->ranges.end(); I != E; ++I) {
1311         const LiveRange *DstLR = ResDstInt->getLiveRangeContaining(I->start);
1312         assert(DstLR  && "Invalid joined interval!");
1313         const VNInfo *DstValNo = DstLR->valno;
1314         if (CopiedValNos.insert(DstValNo)) {
1315           VNInfo *ValNo = RealInt.getNextValue(DstValNo->def, DstValNo->copy,
1316                                                li_->getVNInfoAllocator());
1317           ValNo->hasPHIKill = DstValNo->hasPHIKill;
1318           RealInt.addKills(ValNo, DstValNo->kills);
1319           RealInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo);
1320         }
1321       }
1322
1323       DstReg = RealDstReg ? RealDstReg : RealSrcReg;
1324     }
1325
1326     // Update the liveintervals of sub-registers.
1327     for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
1328       li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
1329                                                  li_->getVNInfoAllocator());
1330   }
1331
1332   // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the
1333   // larger super-register.
1334   if ((isExtSubReg || isInsSubReg) && !SrcIsPhys && !DstIsPhys) {
1335     if ((isExtSubReg && !Swapped) || (isInsSubReg && Swapped)) {
1336       ResSrcInt->Copy(*ResDstInt, li_->getVNInfoAllocator());
1337       std::swap(SrcReg, DstReg);
1338       std::swap(ResSrcInt, ResDstInt);
1339     }
1340   }
1341
1342   // Coalescing to a virtual register that is of a sub-register class of the
1343   // other. Make sure the resulting register is set to the right register class.
1344   if (SubRC) {
1345     mri_->setRegClass(DstReg, SubRC);
1346     ++numSubJoins;
1347   }
1348
1349   if (NewHeuristic) {
1350     // Add all copies that define val# in the source interval into the queue.
1351     for (LiveInterval::const_vni_iterator i = ResSrcInt->vni_begin(),
1352            e = ResSrcInt->vni_end(); i != e; ++i) {
1353       const VNInfo *vni = *i;
1354       if (!vni->def || vni->def == ~1U || vni->def == ~0U)
1355         continue;
1356       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
1357       unsigned NewSrcReg, NewDstReg;
1358       if (CopyMI &&
1359           JoinedCopies.count(CopyMI) == 0 &&
1360           tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg)) {
1361         unsigned LoopDepth = loopInfo->getLoopDepth(CopyMBB);
1362         JoinQueue->push(CopyRec(CopyMI, LoopDepth,
1363                                 isBackEdgeCopy(CopyMI, DstReg)));
1364       }
1365     }
1366   }
1367
1368   // Remember to delete the copy instruction.
1369   JoinedCopies.insert(CopyMI);
1370
1371   // Some live range has been lengthened due to colaescing, eliminate the
1372   // unnecessary kills.
1373   RemoveUnnecessaryKills(SrcReg, *ResDstInt);
1374   if (TargetRegisterInfo::isVirtualRegister(DstReg))
1375     RemoveUnnecessaryKills(DstReg, *ResDstInt);
1376
1377   // Merge the earlyclobber bits.
1378   ResDstInt->isEarlyClobber |= ResSrcInt->isEarlyClobber;
1379   ResDstInt->overlapsEarlyClobber |= ResSrcInt->overlapsEarlyClobber;
1380
1381   if (isInsSubReg)
1382     // Avoid:
1383     // r1024 = op
1384     // r1024 = implicit_def
1385     // ...
1386     //       = r1024
1387     RemoveDeadImpDef(DstReg, *ResDstInt);
1388   UpdateRegDefsUses(SrcReg, DstReg, SubIdx);
1389
1390   // SrcReg is guarateed to be the register whose live interval that is
1391   // being merged.
1392   li_->removeInterval(SrcReg);
1393
1394   if (isEmpty) {
1395     // Now the copy is being coalesced away, the val# previously defined
1396     // by the copy is being defined by an IMPLICIT_DEF which defines a zero
1397     // length interval. Remove the val#.
1398     unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
1399     const LiveRange *LR = ResDstInt->getLiveRangeContaining(CopyIdx);
1400     VNInfo *ImpVal = LR->valno;
1401     assert(ImpVal->def == CopyIdx);
1402     unsigned NextDef = LR->end;
1403     RemoveCopiesFromValNo(*ResDstInt, ImpVal);
1404     ResDstInt->removeValNo(ImpVal);
1405     LR = ResDstInt->FindLiveRangeContaining(NextDef);
1406     if (LR != ResDstInt->end() && LR->valno->def == NextDef) {
1407       // Special case: vr1024 = implicit_def
1408       //               vr1024 = insert_subreg vr1024, vr1025, c
1409       // The insert_subreg becomes a "copy" that defines a val# which can itself
1410       // be coalesced away.
1411       MachineInstr *DefMI = li_->getInstructionFromIndex(NextDef);
1412       if (DefMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
1413         LR->valno->copy = DefMI;
1414     }
1415   }
1416
1417   // If resulting interval has a preference that no longer fits because of subreg
1418   // coalescing, just clear the preference.
1419   if (ResDstInt->preference && (isExtSubReg || isInsSubReg) &&
1420       TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) {
1421     const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg);
1422     if (!RC->contains(ResDstInt->preference))
1423       ResDstInt->preference = 0;
1424   }
1425
1426   DOUT << "\n\t\tJoined.  Result = "; ResDstInt->print(DOUT, tri_);
1427   DOUT << "\n";
1428
1429   ++numJoins;
1430   return true;
1431 }
1432
1433 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
1434 /// compute what the resultant value numbers for each value in the input two
1435 /// ranges will be.  This is complicated by copies between the two which can
1436 /// and will commonly cause multiple value numbers to be merged into one.
1437 ///
1438 /// VN is the value number that we're trying to resolve.  InstDefiningValue
1439 /// keeps track of the new InstDefiningValue assignment for the result
1440 /// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
1441 /// whether a value in this or other is a copy from the opposite set.
1442 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
1443 /// already been assigned.
1444 ///
1445 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
1446 /// contains the value number the copy is from.
1447 ///
1448 static unsigned ComputeUltimateVN(VNInfo *VNI,
1449                                   SmallVector<VNInfo*, 16> &NewVNInfo,
1450                                   DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
1451                                   DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
1452                                   SmallVector<int, 16> &ThisValNoAssignments,
1453                                   SmallVector<int, 16> &OtherValNoAssignments) {
1454   unsigned VN = VNI->id;
1455
1456   // If the VN has already been computed, just return it.
1457   if (ThisValNoAssignments[VN] >= 0)
1458     return ThisValNoAssignments[VN];
1459 //  assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?");
1460
1461   // If this val is not a copy from the other val, then it must be a new value
1462   // number in the destination.
1463   DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
1464   if (I == ThisFromOther.end()) {
1465     NewVNInfo.push_back(VNI);
1466     return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
1467   }
1468   VNInfo *OtherValNo = I->second;
1469
1470   // Otherwise, this *is* a copy from the RHS.  If the other side has already
1471   // been computed, return it.
1472   if (OtherValNoAssignments[OtherValNo->id] >= 0)
1473     return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
1474
1475   // Mark this value number as currently being computed, then ask what the
1476   // ultimate value # of the other value is.
1477   ThisValNoAssignments[VN] = -2;
1478   unsigned UltimateVN =
1479     ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
1480                       OtherValNoAssignments, ThisValNoAssignments);
1481   return ThisValNoAssignments[VN] = UltimateVN;
1482 }
1483
1484 static bool InVector(VNInfo *Val, const SmallVector<VNInfo*, 8> &V) {
1485   return std::find(V.begin(), V.end(), Val) != V.end();
1486 }
1487
1488 /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of
1489 /// the specified live interval is defined by a copy from the specified
1490 /// register.
1491 bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li,
1492                                                            LiveRange *LR,
1493                                                            unsigned Reg) {
1494   unsigned SrcReg = li_->getVNInfoSourceReg(LR->valno);
1495   if (SrcReg == Reg)
1496     return true;
1497   if (LR->valno->def == ~0U &&
1498       TargetRegisterInfo::isPhysicalRegister(li.reg) &&
1499       *tri_->getSuperRegisters(li.reg)) {
1500     // It's a sub-register live interval, we may not have precise information.
1501     // Re-compute it.
1502     MachineInstr *DefMI = li_->getInstructionFromIndex(LR->start);
1503     unsigned SrcReg, DstReg;
1504     if (DefMI && tii_->isMoveInstr(*DefMI, SrcReg, DstReg) &&
1505         DstReg == li.reg && SrcReg == Reg) {
1506       // Cache computed info.
1507       LR->valno->def  = LR->start;
1508       LR->valno->copy = DefMI;
1509       return true;
1510     }
1511   }
1512   return false;
1513 }
1514
1515 /// SimpleJoin - Attempt to joint the specified interval into this one. The
1516 /// caller of this method must guarantee that the RHS only contains a single
1517 /// value number and that the RHS is not defined by a copy from this
1518 /// interval.  This returns false if the intervals are not joinable, or it
1519 /// joins them and returns true.
1520 bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){
1521   assert(RHS.containsOneValue());
1522
1523   // Some number (potentially more than one) value numbers in the current
1524   // interval may be defined as copies from the RHS.  Scan the overlapping
1525   // portions of the LHS and RHS, keeping track of this and looking for
1526   // overlapping live ranges that are NOT defined as copies.  If these exist, we
1527   // cannot coalesce.
1528
1529   LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end();
1530   LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end();
1531
1532   if (LHSIt->start < RHSIt->start) {
1533     LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start);
1534     if (LHSIt != LHS.begin()) --LHSIt;
1535   } else if (RHSIt->start < LHSIt->start) {
1536     RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start);
1537     if (RHSIt != RHS.begin()) --RHSIt;
1538   }
1539
1540   SmallVector<VNInfo*, 8> EliminatedLHSVals;
1541
1542   while (1) {
1543     // Determine if these live intervals overlap.
1544     bool Overlaps = false;
1545     if (LHSIt->start <= RHSIt->start)
1546       Overlaps = LHSIt->end > RHSIt->start;
1547     else
1548       Overlaps = RHSIt->end > LHSIt->start;
1549
1550     // If the live intervals overlap, there are two interesting cases: if the
1551     // LHS interval is defined by a copy from the RHS, it's ok and we record
1552     // that the LHS value # is the same as the RHS.  If it's not, then we cannot
1553     // coalesce these live ranges and we bail out.
1554     if (Overlaps) {
1555       // If we haven't already recorded that this value # is safe, check it.
1556       if (!InVector(LHSIt->valno, EliminatedLHSVals)) {
1557         // Copy from the RHS?
1558         if (!RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg))
1559           return false;    // Nope, bail out.
1560
1561         if (LHSIt->contains(RHSIt->valno->def))
1562           // Here is an interesting situation:
1563           // BB1:
1564           //   vr1025 = copy vr1024
1565           //   ..
1566           // BB2:
1567           //   vr1024 = op
1568           //          = vr1025
1569           // Even though vr1025 is copied from vr1024, it's not safe to
1570           // coalesced them since live range of vr1025 intersects the
1571           // def of vr1024. This happens because vr1025 is assigned the
1572           // value of the previous iteration of vr1024.
1573           return false;
1574         EliminatedLHSVals.push_back(LHSIt->valno);
1575       }
1576
1577       // We know this entire LHS live range is okay, so skip it now.
1578       if (++LHSIt == LHSEnd) break;
1579       continue;
1580     }
1581
1582     if (LHSIt->end < RHSIt->end) {
1583       if (++LHSIt == LHSEnd) break;
1584     } else {
1585       // One interesting case to check here.  It's possible that we have
1586       // something like "X3 = Y" which defines a new value number in the LHS,
1587       // and is the last use of this liverange of the RHS.  In this case, we
1588       // want to notice this copy (so that it gets coalesced away) even though
1589       // the live ranges don't actually overlap.
1590       if (LHSIt->start == RHSIt->end) {
1591         if (InVector(LHSIt->valno, EliminatedLHSVals)) {
1592           // We already know that this value number is going to be merged in
1593           // if coalescing succeeds.  Just skip the liverange.
1594           if (++LHSIt == LHSEnd) break;
1595         } else {
1596           // Otherwise, if this is a copy from the RHS, mark it as being merged
1597           // in.
1598           if (RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg)) {
1599             if (LHSIt->contains(RHSIt->valno->def))
1600               // Here is an interesting situation:
1601               // BB1:
1602               //   vr1025 = copy vr1024
1603               //   ..
1604               // BB2:
1605               //   vr1024 = op
1606               //          = vr1025
1607               // Even though vr1025 is copied from vr1024, it's not safe to
1608               // coalesced them since live range of vr1025 intersects the
1609               // def of vr1024. This happens because vr1025 is assigned the
1610               // value of the previous iteration of vr1024.
1611               return false;
1612             EliminatedLHSVals.push_back(LHSIt->valno);
1613
1614             // We know this entire LHS live range is okay, so skip it now.
1615             if (++LHSIt == LHSEnd) break;
1616           }
1617         }
1618       }
1619
1620       if (++RHSIt == RHSEnd) break;
1621     }
1622   }
1623
1624   // If we got here, we know that the coalescing will be successful and that
1625   // the value numbers in EliminatedLHSVals will all be merged together.  Since
1626   // the most common case is that EliminatedLHSVals has a single number, we
1627   // optimize for it: if there is more than one value, we merge them all into
1628   // the lowest numbered one, then handle the interval as if we were merging
1629   // with one value number.
1630   VNInfo *LHSValNo;
1631   if (EliminatedLHSVals.size() > 1) {
1632     // Loop through all the equal value numbers merging them into the smallest
1633     // one.
1634     VNInfo *Smallest = EliminatedLHSVals[0];
1635     for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) {
1636       if (EliminatedLHSVals[i]->id < Smallest->id) {
1637         // Merge the current notion of the smallest into the smaller one.
1638         LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]);
1639         Smallest = EliminatedLHSVals[i];
1640       } else {
1641         // Merge into the smallest.
1642         LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest);
1643       }
1644     }
1645     LHSValNo = Smallest;
1646   } else if (EliminatedLHSVals.empty()) {
1647     if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) &&
1648         *tri_->getSuperRegisters(LHS.reg))
1649       // Imprecise sub-register information. Can't handle it.
1650       return false;
1651     assert(0 && "No copies from the RHS?");
1652   } else {
1653     LHSValNo = EliminatedLHSVals[0];
1654   }
1655
1656   // Okay, now that there is a single LHS value number that we're merging the
1657   // RHS into, update the value number info for the LHS to indicate that the
1658   // value number is defined where the RHS value number was.
1659   const VNInfo *VNI = RHS.getValNumInfo(0);
1660   LHSValNo->def  = VNI->def;
1661   LHSValNo->copy = VNI->copy;
1662
1663   // Okay, the final step is to loop over the RHS live intervals, adding them to
1664   // the LHS.
1665   LHSValNo->hasPHIKill |= VNI->hasPHIKill;
1666   LHS.addKills(LHSValNo, VNI->kills);
1667   LHS.MergeRangesInAsValue(RHS, LHSValNo);
1668   LHS.weight += RHS.weight;
1669   if (RHS.preference && !LHS.preference)
1670     LHS.preference = RHS.preference;
1671
1672   return true;
1673 }
1674
1675 /// JoinIntervals - Attempt to join these two intervals.  On failure, this
1676 /// returns false.  Otherwise, if one of the intervals being joined is a
1677 /// physreg, this method always canonicalizes LHS to be it.  The output
1678 /// "RHS" will not have been modified, so we can use this information
1679 /// below to update aliases.
1680 bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS,
1681                                              LiveInterval &RHS, bool &Swapped) {
1682   // Compute the final value assignment, assuming that the live ranges can be
1683   // coalesced.
1684   SmallVector<int, 16> LHSValNoAssignments;
1685   SmallVector<int, 16> RHSValNoAssignments;
1686   DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
1687   DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
1688   SmallVector<VNInfo*, 16> NewVNInfo;
1689
1690   // If a live interval is a physical register, conservatively check if any
1691   // of its sub-registers is overlapping the live interval of the virtual
1692   // register. If so, do not coalesce.
1693   if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) &&
1694       *tri_->getSubRegisters(LHS.reg)) {
1695     for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR)
1696       if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
1697         DOUT << "Interfere with sub-register ";
1698         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
1699         return false;
1700       }
1701   } else if (TargetRegisterInfo::isPhysicalRegister(RHS.reg) &&
1702              *tri_->getSubRegisters(RHS.reg)) {
1703     for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR)
1704       if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) {
1705         DOUT << "Interfere with sub-register ";
1706         DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
1707         return false;
1708       }
1709   }
1710
1711   // Compute ultimate value numbers for the LHS and RHS values.
1712   if (RHS.containsOneValue()) {
1713     // Copies from a liveinterval with a single value are simple to handle and
1714     // very common, handle the special case here.  This is important, because
1715     // often RHS is small and LHS is large (e.g. a physreg).
1716
1717     // Find out if the RHS is defined as a copy from some value in the LHS.
1718     int RHSVal0DefinedFromLHS = -1;
1719     int RHSValID = -1;
1720     VNInfo *RHSValNoInfo = NULL;
1721     VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0);
1722     unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0);
1723     if ((RHSSrcReg == 0 || RHSSrcReg != LHS.reg)) {
1724       // If RHS is not defined as a copy from the LHS, we can use simpler and
1725       // faster checks to see if the live ranges are coalescable.  This joiner
1726       // can't swap the LHS/RHS intervals though.
1727       if (!TargetRegisterInfo::isPhysicalRegister(RHS.reg)) {
1728         return SimpleJoin(LHS, RHS);
1729       } else {
1730         RHSValNoInfo = RHSValNoInfo0;
1731       }
1732     } else {
1733       // It was defined as a copy from the LHS, find out what value # it is.
1734       RHSValNoInfo = LHS.getLiveRangeContaining(RHSValNoInfo0->def-1)->valno;
1735       RHSValID = RHSValNoInfo->id;
1736       RHSVal0DefinedFromLHS = RHSValID;
1737     }
1738
1739     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1740     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1741     NewVNInfo.resize(LHS.getNumValNums(), NULL);
1742
1743     // Okay, *all* of the values in LHS that are defined as a copy from RHS
1744     // should now get updated.
1745     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1746          i != e; ++i) {
1747       VNInfo *VNI = *i;
1748       unsigned VN = VNI->id;
1749       if (unsigned LHSSrcReg = li_->getVNInfoSourceReg(VNI)) {
1750         if (LHSSrcReg != RHS.reg) {
1751           // If this is not a copy from the RHS, its value number will be
1752           // unmodified by the coalescing.
1753           NewVNInfo[VN] = VNI;
1754           LHSValNoAssignments[VN] = VN;
1755         } else if (RHSValID == -1) {
1756           // Otherwise, it is a copy from the RHS, and we don't already have a
1757           // value# for it.  Keep the current value number, but remember it.
1758           LHSValNoAssignments[VN] = RHSValID = VN;
1759           NewVNInfo[VN] = RHSValNoInfo;
1760           LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0;
1761         } else {
1762           // Otherwise, use the specified value #.
1763           LHSValNoAssignments[VN] = RHSValID;
1764           if (VN == (unsigned)RHSValID) {  // Else this val# is dead.
1765             NewVNInfo[VN] = RHSValNoInfo;
1766             LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0;
1767           }
1768         }
1769       } else {
1770         NewVNInfo[VN] = VNI;
1771         LHSValNoAssignments[VN] = VN;
1772       }
1773     }
1774
1775     assert(RHSValID != -1 && "Didn't find value #?");
1776     RHSValNoAssignments[0] = RHSValID;
1777     if (RHSVal0DefinedFromLHS != -1) {
1778       // This path doesn't go through ComputeUltimateVN so just set
1779       // it to anything.
1780       RHSValsDefinedFromLHS[RHSValNoInfo0] = (VNInfo*)1;
1781     }
1782   } else {
1783     // Loop over the value numbers of the LHS, seeing if any are defined from
1784     // the RHS.
1785     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1786          i != e; ++i) {
1787       VNInfo *VNI = *i;
1788       if (VNI->def == ~1U || VNI->copy == 0)  // Src not defined by a copy?
1789         continue;
1790
1791       // DstReg is known to be a register in the LHS interval.  If the src is
1792       // from the RHS interval, we can use its value #.
1793       if (li_->getVNInfoSourceReg(VNI) != RHS.reg)
1794         continue;
1795
1796       // Figure out the value # from the RHS.
1797       LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno;
1798     }
1799
1800     // Loop over the value numbers of the RHS, seeing if any are defined from
1801     // the LHS.
1802     for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1803          i != e; ++i) {
1804       VNInfo *VNI = *i;
1805       if (VNI->def == ~1U || VNI->copy == 0)  // Src not defined by a copy?
1806         continue;
1807
1808       // DstReg is known to be a register in the RHS interval.  If the src is
1809       // from the LHS interval, we can use its value #.
1810       if (li_->getVNInfoSourceReg(VNI) != LHS.reg)
1811         continue;
1812
1813       // Figure out the value # from the LHS.
1814       RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno;
1815     }
1816
1817     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1818     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1819     NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
1820
1821     for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1822          i != e; ++i) {
1823       VNInfo *VNI = *i;
1824       unsigned VN = VNI->id;
1825       if (LHSValNoAssignments[VN] >= 0 || VNI->def == ~1U)
1826         continue;
1827       ComputeUltimateVN(VNI, NewVNInfo,
1828                         LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
1829                         LHSValNoAssignments, RHSValNoAssignments);
1830     }
1831     for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1832          i != e; ++i) {
1833       VNInfo *VNI = *i;
1834       unsigned VN = VNI->id;
1835       if (RHSValNoAssignments[VN] >= 0 || VNI->def == ~1U)
1836         continue;
1837       // If this value number isn't a copy from the LHS, it's a new number.
1838       if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
1839         NewVNInfo.push_back(VNI);
1840         RHSValNoAssignments[VN] = NewVNInfo.size()-1;
1841         continue;
1842       }
1843
1844       ComputeUltimateVN(VNI, NewVNInfo,
1845                         RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
1846                         RHSValNoAssignments, LHSValNoAssignments);
1847     }
1848   }
1849
1850   // Armed with the mappings of LHS/RHS values to ultimate values, walk the
1851   // interval lists to see if these intervals are coalescable.
1852   LiveInterval::const_iterator I = LHS.begin();
1853   LiveInterval::const_iterator IE = LHS.end();
1854   LiveInterval::const_iterator J = RHS.begin();
1855   LiveInterval::const_iterator JE = RHS.end();
1856
1857   // Skip ahead until the first place of potential sharing.
1858   if (I->start < J->start) {
1859     I = std::upper_bound(I, IE, J->start);
1860     if (I != LHS.begin()) --I;
1861   } else if (J->start < I->start) {
1862     J = std::upper_bound(J, JE, I->start);
1863     if (J != RHS.begin()) --J;
1864   }
1865
1866   while (1) {
1867     // Determine if these two live ranges overlap.
1868     bool Overlaps;
1869     if (I->start < J->start) {
1870       Overlaps = I->end > J->start;
1871     } else {
1872       Overlaps = J->end > I->start;
1873     }
1874
1875     // If so, check value # info to determine if they are really different.
1876     if (Overlaps) {
1877       // If the live range overlap will map to the same value number in the
1878       // result liverange, we can still coalesce them.  If not, we can't.
1879       if (LHSValNoAssignments[I->valno->id] !=
1880           RHSValNoAssignments[J->valno->id])
1881         return false;
1882     }
1883
1884     if (I->end < J->end) {
1885       ++I;
1886       if (I == IE) break;
1887     } else {
1888       ++J;
1889       if (J == JE) break;
1890     }
1891   }
1892
1893   // Update kill info. Some live ranges are extended due to copy coalescing.
1894   for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(),
1895          E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
1896     VNInfo *VNI = I->first;
1897     unsigned LHSValID = LHSValNoAssignments[VNI->id];
1898     LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def);
1899     NewVNInfo[LHSValID]->hasPHIKill |= VNI->hasPHIKill;
1900     RHS.addKills(NewVNInfo[LHSValID], VNI->kills);
1901   }
1902
1903   // Update kill info. Some live ranges are extended due to copy coalescing.
1904   for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(),
1905          E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
1906     VNInfo *VNI = I->first;
1907     unsigned RHSValID = RHSValNoAssignments[VNI->id];
1908     LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def);
1909     NewVNInfo[RHSValID]->hasPHIKill |= VNI->hasPHIKill;
1910     LHS.addKills(NewVNInfo[RHSValID], VNI->kills);
1911   }
1912
1913   // If we get here, we know that we can coalesce the live ranges.  Ask the
1914   // intervals to coalesce themselves now.
1915   if ((RHS.ranges.size() > LHS.ranges.size() &&
1916       TargetRegisterInfo::isVirtualRegister(LHS.reg)) ||
1917       TargetRegisterInfo::isPhysicalRegister(RHS.reg)) {
1918     RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo);
1919     Swapped = true;
1920   } else {
1921     LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo);
1922     Swapped = false;
1923   }
1924   return true;
1925 }
1926
1927 namespace {
1928   // DepthMBBCompare - Comparison predicate that sort first based on the loop
1929   // depth of the basic block (the unsigned), and then on the MBB number.
1930   struct DepthMBBCompare {
1931     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
1932     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
1933       if (LHS.first > RHS.first) return true;   // Deeper loops first
1934       return LHS.first == RHS.first &&
1935         LHS.second->getNumber() < RHS.second->getNumber();
1936     }
1937   };
1938 }
1939
1940 /// getRepIntervalSize - Returns the size of the interval that represents the
1941 /// specified register.
1942 template<class SF>
1943 unsigned JoinPriorityQueue<SF>::getRepIntervalSize(unsigned Reg) {
1944   return Rc->getRepIntervalSize(Reg);
1945 }
1946
1947 /// CopyRecSort::operator - Join priority queue sorting function.
1948 ///
1949 bool CopyRecSort::operator()(CopyRec left, CopyRec right) const {
1950   // Inner loops first.
1951   if (left.LoopDepth > right.LoopDepth)
1952     return false;
1953   else if (left.LoopDepth == right.LoopDepth)
1954     if (left.isBackEdge && !right.isBackEdge)
1955       return false;
1956   return true;
1957 }
1958
1959 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
1960                                                std::vector<CopyRec> &TryAgain) {
1961   DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
1962
1963   std::vector<CopyRec> VirtCopies;
1964   std::vector<CopyRec> PhysCopies;
1965   std::vector<CopyRec> ImpDefCopies;
1966   unsigned LoopDepth = loopInfo->getLoopDepth(MBB);
1967   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
1968        MII != E;) {
1969     MachineInstr *Inst = MII++;
1970
1971     // If this isn't a copy nor a extract_subreg, we can't join intervals.
1972     unsigned SrcReg, DstReg;
1973     if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
1974       DstReg = Inst->getOperand(0).getReg();
1975       SrcReg = Inst->getOperand(1).getReg();
1976     } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
1977       DstReg = Inst->getOperand(0).getReg();
1978       SrcReg = Inst->getOperand(2).getReg();
1979     } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg))
1980       continue;
1981
1982     bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
1983     bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1984     if (NewHeuristic) {
1985       JoinQueue->push(CopyRec(Inst, LoopDepth, isBackEdgeCopy(Inst, DstReg)));
1986     } else {
1987       if (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty())
1988         ImpDefCopies.push_back(CopyRec(Inst, 0, false));
1989       else if (SrcIsPhys || DstIsPhys)
1990         PhysCopies.push_back(CopyRec(Inst, 0, false));
1991       else
1992         VirtCopies.push_back(CopyRec(Inst, 0, false));
1993     }
1994   }
1995
1996   if (NewHeuristic)
1997     return;
1998
1999   // Try coalescing implicit copies first, followed by copies to / from
2000   // physical registers, then finally copies from virtual registers to
2001   // virtual registers.
2002   for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) {
2003     CopyRec &TheCopy = ImpDefCopies[i];
2004     bool Again = false;
2005     if (!JoinCopy(TheCopy, Again))
2006       if (Again)
2007         TryAgain.push_back(TheCopy);
2008   }
2009   for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) {
2010     CopyRec &TheCopy = PhysCopies[i];
2011     bool Again = false;
2012     if (!JoinCopy(TheCopy, Again))
2013       if (Again)
2014         TryAgain.push_back(TheCopy);
2015   }
2016   for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) {
2017     CopyRec &TheCopy = VirtCopies[i];
2018     bool Again = false;
2019     if (!JoinCopy(TheCopy, Again))
2020       if (Again)
2021         TryAgain.push_back(TheCopy);
2022   }
2023 }
2024
2025 void SimpleRegisterCoalescing::joinIntervals() {
2026   DOUT << "********** JOINING INTERVALS ***********\n";
2027
2028   if (NewHeuristic)
2029     JoinQueue = new JoinPriorityQueue<CopyRecSort>(this);
2030
2031   std::vector<CopyRec> TryAgainList;
2032   if (loopInfo->empty()) {
2033     // If there are no loops in the function, join intervals in function order.
2034     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
2035          I != E; ++I)
2036       CopyCoalesceInMBB(I, TryAgainList);
2037   } else {
2038     // Otherwise, join intervals in inner loops before other intervals.
2039     // Unfortunately we can't just iterate over loop hierarchy here because
2040     // there may be more MBB's than BB's.  Collect MBB's for sorting.
2041
2042     // Join intervals in the function prolog first. We want to join physical
2043     // registers with virtual registers before the intervals got too long.
2044     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
2045     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){
2046       MachineBasicBlock *MBB = I;
2047       MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I));
2048     }
2049
2050     // Sort by loop depth.
2051     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
2052
2053     // Finally, join intervals in loop nest order.
2054     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
2055       CopyCoalesceInMBB(MBBs[i].second, TryAgainList);
2056   }
2057
2058   // Joining intervals can allow other intervals to be joined.  Iteratively join
2059   // until we make no progress.
2060   if (NewHeuristic) {
2061     SmallVector<CopyRec, 16> TryAgain;
2062     bool ProgressMade = true;
2063     while (ProgressMade) {
2064       ProgressMade = false;
2065       while (!JoinQueue->empty()) {
2066         CopyRec R = JoinQueue->pop();
2067         bool Again = false;
2068         bool Success = JoinCopy(R, Again);
2069         if (Success)
2070           ProgressMade = true;
2071         else if (Again)
2072           TryAgain.push_back(R);
2073       }
2074
2075       if (ProgressMade) {
2076         while (!TryAgain.empty()) {
2077           JoinQueue->push(TryAgain.back());
2078           TryAgain.pop_back();
2079         }
2080       }
2081     }
2082   } else {
2083     bool ProgressMade = true;
2084     while (ProgressMade) {
2085       ProgressMade = false;
2086
2087       for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
2088         CopyRec &TheCopy = TryAgainList[i];
2089         if (TheCopy.MI) {
2090           bool Again = false;
2091           bool Success = JoinCopy(TheCopy, Again);
2092           if (Success || !Again) {
2093             TheCopy.MI = 0;   // Mark this one as done.
2094             ProgressMade = true;
2095           }
2096         }
2097       }
2098     }
2099   }
2100
2101   if (NewHeuristic)
2102     delete JoinQueue;
2103 }
2104
2105 /// Return true if the two specified registers belong to different register
2106 /// classes.  The registers may be either phys or virt regs. In the
2107 /// case where both registers are virtual registers, it would also returns
2108 /// true by reference the RegB register class in SubRC if it is a subset of
2109 /// RegA's register class.
2110 bool
2111 SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB,
2112                                       const TargetRegisterClass *&SubRC) const {
2113
2114   // Get the register classes for the first reg.
2115   if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
2116     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
2117            "Shouldn't consider two physregs!");
2118     return !mri_->getRegClass(RegB)->contains(RegA);
2119   }
2120
2121   // Compare against the regclass for the second reg.
2122   const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA);
2123   if (TargetRegisterInfo::isVirtualRegister(RegB)) {
2124     const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB);
2125     if (RegClassA == RegClassB)
2126       return false;
2127     SubRC = (RegClassA->hasSubClass(RegClassB)) ? RegClassB : NULL;
2128     return true;
2129   }
2130   return !RegClassA->contains(RegB);
2131 }
2132
2133 /// lastRegisterUse - Returns the last use of the specific register between
2134 /// cycles Start and End or NULL if there are no uses.
2135 MachineOperand *
2136 SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
2137                                           unsigned Reg, unsigned &UseIdx) const{
2138   UseIdx = 0;
2139   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2140     MachineOperand *LastUse = NULL;
2141     for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg),
2142            E = mri_->use_end(); I != E; ++I) {
2143       MachineOperand &Use = I.getOperand();
2144       MachineInstr *UseMI = Use.getParent();
2145       unsigned SrcReg, DstReg;
2146       if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg) && SrcReg == DstReg)
2147         // Ignore identity copies.
2148         continue;
2149       unsigned Idx = li_->getInstructionIndex(UseMI);
2150       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
2151         LastUse = &Use;
2152         UseIdx = Idx;
2153       }
2154     }
2155     return LastUse;
2156   }
2157
2158   int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM;
2159   int s = Start;
2160   while (e >= s) {
2161     // Skip deleted instructions
2162     MachineInstr *MI = li_->getInstructionFromIndex(e);
2163     while ((e - InstrSlots::NUM) >= s && !MI) {
2164       e -= InstrSlots::NUM;
2165       MI = li_->getInstructionFromIndex(e);
2166     }
2167     if (e < s || MI == NULL)
2168       return NULL;
2169
2170     // Ignore identity copies.
2171     unsigned SrcReg, DstReg;
2172     if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg))
2173       for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
2174         MachineOperand &Use = MI->getOperand(i);
2175         if (Use.isRegister() && Use.isUse() && Use.getReg() &&
2176             tri_->regsOverlap(Use.getReg(), Reg)) {
2177           UseIdx = e;
2178           return &Use;
2179         }
2180       }
2181
2182     e -= InstrSlots::NUM;
2183   }
2184
2185   return NULL;
2186 }
2187
2188
2189 void SimpleRegisterCoalescing::printRegName(unsigned reg) const {
2190   if (TargetRegisterInfo::isPhysicalRegister(reg))
2191     cerr << tri_->getName(reg);
2192   else
2193     cerr << "%reg" << reg;
2194 }
2195
2196 void SimpleRegisterCoalescing::releaseMemory() {
2197   JoinedCopies.clear();
2198   ReMatCopies.clear();
2199   ReMatDefs.clear();
2200 }
2201
2202 static bool isZeroLengthInterval(LiveInterval *li) {
2203   for (LiveInterval::Ranges::const_iterator
2204          i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
2205     if (i->end - i->start > LiveIntervals::InstrSlots::NUM)
2206       return false;
2207   return true;
2208 }
2209
2210 /// TurnCopyIntoImpDef - If source of the specified copy is an implicit def,
2211 /// turn the copy into an implicit def.
2212 bool
2213 SimpleRegisterCoalescing::TurnCopyIntoImpDef(MachineBasicBlock::iterator &I,
2214                                              MachineBasicBlock *MBB,
2215                                              unsigned DstReg, unsigned SrcReg) {
2216   MachineInstr *CopyMI = &*I;
2217   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
2218   if (!li_->hasInterval(SrcReg))
2219     return false;
2220   LiveInterval &SrcInt = li_->getInterval(SrcReg);
2221   if (!SrcInt.empty())
2222     return false;
2223   if (!li_->hasInterval(DstReg))
2224     return false;
2225   LiveInterval &DstInt = li_->getInterval(DstReg);
2226   const LiveRange *DstLR = DstInt.getLiveRangeContaining(CopyIdx);
2227   DstInt.removeValNo(DstLR->valno);
2228   CopyMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
2229   for (int i = CopyMI->getNumOperands() - 1, e = 0; i > e; --i)
2230     CopyMI->RemoveOperand(i);
2231   bool NoUse = mri_->use_empty(SrcReg);
2232   if (NoUse) {
2233     for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
2234            E = mri_->reg_end(); I != E; ) {
2235       assert(I.getOperand().isDef());
2236       MachineInstr *DefMI = &*I;
2237       ++I;
2238       // The implicit_def source has no other uses, delete it.
2239       assert(DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF);
2240       li_->RemoveMachineInstrFromMaps(DefMI);
2241       DefMI->eraseFromParent();
2242     }
2243   }
2244   ++I;
2245   return true;
2246 }
2247
2248
2249 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
2250   mf_ = &fn;
2251   mri_ = &fn.getRegInfo();
2252   tm_ = &fn.getTarget();
2253   tri_ = tm_->getRegisterInfo();
2254   tii_ = tm_->getInstrInfo();
2255   li_ = &getAnalysis<LiveIntervals>();
2256   loopInfo = &getAnalysis<MachineLoopInfo>();
2257
2258   DOUT << "********** SIMPLE REGISTER COALESCING **********\n"
2259        << "********** Function: "
2260        << ((Value*)mf_->getFunction())->getName() << '\n';
2261
2262   allocatableRegs_ = tri_->getAllocatableSet(fn);
2263   for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(),
2264          E = tri_->regclass_end(); I != E; ++I)
2265     allocatableRCRegs_.insert(std::make_pair(*I,
2266                                              tri_->getAllocatableSet(fn, *I)));
2267
2268   // Join (coalesce) intervals if requested.
2269   if (EnableJoining) {
2270     joinIntervals();
2271     DOUT << "********** INTERVALS POST JOINING **********\n";
2272     for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){
2273       I->second->print(DOUT, tri_);
2274       DOUT << "\n";
2275     }
2276   }
2277
2278   // Perform a final pass over the instructions and compute spill weights
2279   // and remove identity moves.
2280   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
2281        mbbi != mbbe; ++mbbi) {
2282     MachineBasicBlock* mbb = mbbi;
2283     unsigned loopDepth = loopInfo->getLoopDepth(mbb);
2284
2285     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
2286          mii != mie; ) {
2287       MachineInstr *MI = mii;
2288       unsigned SrcReg, DstReg;
2289       if (JoinedCopies.count(MI)) {
2290         // Delete all coalesced copies.
2291         if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) {
2292           assert((MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
2293                   MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) &&
2294                  "Unrecognized copy instruction");
2295           DstReg = MI->getOperand(0).getReg();
2296         }
2297         if (MI->registerDefIsDead(DstReg)) {
2298           LiveInterval &li = li_->getInterval(DstReg);
2299           if (!ShortenDeadCopySrcLiveRange(li, MI))
2300             ShortenDeadCopyLiveRange(li, MI);
2301         }
2302         li_->RemoveMachineInstrFromMaps(MI);
2303         mii = mbbi->erase(mii);
2304         ++numPeep;
2305         continue;
2306       }
2307
2308       // Now check if this is a remat'ed def instruction which is now dead.
2309       if (ReMatDefs.count(MI)) {
2310         bool isDead = true;
2311         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2312           const MachineOperand &MO = MI->getOperand(i);
2313           if (!MO.isRegister() || MO.isDead())
2314             continue;
2315           unsigned Reg = MO.getReg();
2316           if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
2317               !mri_->use_empty(Reg)) {
2318             isDead = false;
2319             break;
2320           }
2321         }
2322         if (isDead) {
2323           li_->RemoveMachineInstrFromMaps(mii);
2324           mii = mbbi->erase(mii);
2325           continue;
2326         }
2327       }
2328
2329       // If the move will be an identity move delete it
2330       bool isMove = tii_->isMoveInstr(*MI, SrcReg, DstReg);
2331       if (isMove && SrcReg == DstReg) {
2332         if (li_->hasInterval(SrcReg)) {
2333           LiveInterval &RegInt = li_->getInterval(SrcReg);
2334           // If def of this move instruction is dead, remove its live range
2335           // from the dstination register's live interval.
2336           if (MI->registerDefIsDead(DstReg)) {
2337             if (!ShortenDeadCopySrcLiveRange(RegInt, MI))
2338               ShortenDeadCopyLiveRange(RegInt, MI);
2339           }
2340         }
2341         li_->RemoveMachineInstrFromMaps(MI);
2342         mii = mbbi->erase(mii);
2343         ++numPeep;
2344       } else if (!isMove || !TurnCopyIntoImpDef(mii, mbb, DstReg, SrcReg)) {
2345         SmallSet<unsigned, 4> UniqueUses;
2346         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2347           const MachineOperand &mop = MI->getOperand(i);
2348           if (mop.isRegister() && mop.getReg() &&
2349               TargetRegisterInfo::isVirtualRegister(mop.getReg())) {
2350             unsigned reg = mop.getReg();
2351             // Multiple uses of reg by the same instruction. It should not
2352             // contribute to spill weight again.
2353             if (UniqueUses.count(reg) != 0)
2354               continue;
2355             LiveInterval &RegInt = li_->getInterval(reg);
2356             RegInt.weight +=
2357               li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth);
2358             UniqueUses.insert(reg);
2359           }
2360         }
2361         ++mii;
2362       }
2363     }
2364   }
2365
2366   for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) {
2367     LiveInterval &LI = *I->second;
2368     if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
2369       // If the live interval length is essentially zero, i.e. in every live
2370       // range the use follows def immediately, it doesn't make sense to spill
2371       // it and hope it will be easier to allocate for this li.
2372       if (isZeroLengthInterval(&LI))
2373         LI.weight = HUGE_VALF;
2374       else {
2375         bool isLoad = false;
2376         if (li_->isReMaterializable(LI, isLoad)) {
2377           // If all of the definitions of the interval are re-materializable,
2378           // it is a preferred candidate for spilling. If non of the defs are
2379           // loads, then it's potentially very cheap to re-materialize.
2380           // FIXME: this gets much more complicated once we support non-trivial
2381           // re-materialization.
2382           if (isLoad)
2383             LI.weight *= 0.9F;
2384           else
2385             LI.weight *= 0.5F;
2386         }
2387       }
2388
2389       // Slightly prefer live interval that has been assigned a preferred reg.
2390       if (LI.preference)
2391         LI.weight *= 1.01F;
2392
2393       // Divide the weight of the interval by its size.  This encourages
2394       // spilling of intervals that are large and have few uses, and
2395       // discourages spilling of small intervals with many uses.
2396       LI.weight /= li_->getApproximateInstructionCount(LI) * InstrSlots::NUM;
2397     }
2398   }
2399
2400   DEBUG(dump());
2401   return true;
2402 }
2403
2404 /// print - Implement the dump method.
2405 void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const {
2406    li_->print(O, m);
2407 }
2408
2409 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() {
2410   return new SimpleRegisterCoalescing();
2411 }
2412
2413 // Make sure that anything that uses RegisterCoalescer pulls in this file...
2414 DEFINING_FILE_FOR(SimpleRegisterCoalescing)