lib/CodeGen/SimpleRegisterCoalescing.cpp

   1 //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 "llvm/CodeGen/SimpleRegisterCoalescing.h"
  17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  18 #include "VirtRegMap.h"
  19 #include "llvm/Value.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/CodeGen/LiveVariables.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/MRegisterInfo.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/ADT/SmallSet.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include <algorithm>
  35 #include <cmath>
  36 using namespace llvm;
  37
  38 STATISTIC(numJoins    , "Number of interval joins performed");
  39 STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
  40 STATISTIC(numAborts   , "Number of times interval joining aborted");
  41
  42 char SimpleRegisterCoalescing::ID = 0;
  43 namespace {
  44   static cl::opt<bool>
  45   EnableJoining("join-liveintervals",
  46                 cl::desc("Coalesce copies (default=true)"),
  47                 cl::init(true));
  48
  49   RegisterPass<SimpleRegisterCoalescing>
  50   X("simple-register-coalescing", "Simple Register Coalescing");
  51 }
  52
  53 const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo();
  54
  55 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
  56    //AU.addPreserved<LiveVariables>();
  57   AU.addPreserved<LiveIntervals>();
  58   AU.addPreservedID(PHIEliminationID);
  59   AU.addPreservedID(TwoAddressInstructionPassID);
  60   AU.addRequired<LiveVariables>();
  61   AU.addRequired<LiveIntervals>();
  62   AU.addRequired<LoopInfo>();
  63   MachineFunctionPass::getAnalysisUsage(AU);
  64 }
  65
  66 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
  67 /// being the source and IntB being the dest, thus this defines a value number
  68 /// in IntB.  If the source value number (in IntA) is defined by a copy from B,
  69 /// see if we can merge these two pieces of B into a single value number,
  70 /// eliminating a copy.  For example:
  71 ///
  72 ///  A3 = B0
  73 ///    ...
  74 ///  B1 = A3      <- this copy
  75 ///
  76 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
  77 /// value number to be replaced with B0 (which simplifies the B liveinterval).
  78 ///
  79 /// This returns true if an interval was modified.
  80 ///
  81 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
  82                                          MachineInstr *CopyMI) {
  83   unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
  84
  85   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
  86   // the example above.
  87   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
  88   unsigned BValNo = BLR->ValId;
  89
  90   // Get the location that B is defined at.  Two options: either this value has
  91   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
  92   // can't process it.
  93   unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo);
  94   if (BValNoDefIdx == ~0U) return false;
  95   assert(BValNoDefIdx == CopyIdx &&
  96          "Copy doesn't define the value?");
  97
  98   // AValNo is the value number in A that defines the copy, A0 in the example.
  99   LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1);
 100   unsigned AValNo = AValLR->ValId;
 101
 102   // If AValNo is defined as a copy from IntB, we can potentially process this.
 103
 104   // Get the instruction that defines this value number.
 105   unsigned SrcReg = IntA.getSrcRegForValNum(AValNo);
 106   if (!SrcReg) return false;  // Not defined by a copy.
 107
 108   // If the value number is not defined by a copy instruction, ignore it.
 109
 110   // If the source register comes from an interval other than IntB, we can't
 111   // handle this.
 112   if (rep(SrcReg) != IntB.reg) return false;
 113
 114   // Get the LiveRange in IntB that this value number starts with.
 115   unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo);
 116   LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1);
 117
 118   // Make sure that the end of the live range is inside the same block as
 119   // CopyMI.
 120   MachineInstr *ValLREndInst = li_->getInstructionFromIndex(ValLR->end-1);
 121   if (!ValLREndInst ||
 122       ValLREndInst->getParent() != CopyMI->getParent()) return false;
 123
 124   // Okay, we now know that ValLR ends in the same block that the CopyMI
 125   // live-range starts.  If there are no intervening live ranges between them in
 126   // IntB, we can merge them.
 127   if (ValLR+1 != BLR) return false;
 128
 129   DOUT << "\nExtending: "; IntB.print(DOUT, mri_);
 130
 131   // We are about to delete CopyMI, so need to remove it as the 'instruction
 132   // that defines this value #'.
 133   IntB.setValueNumberInfo(BValNo, std::make_pair(~0U, 0));
 134
 135   // Okay, we can merge them.  We need to insert a new liverange:
 136   // [ValLR.end, BLR.begin) of either value number, then we merge the
 137   // two value numbers.
 138   unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
 139   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
 140
 141   // If the IntB live range is assigned to a physical register, and if that
 142   // physreg has aliases,
 143   if (MRegisterInfo::isPhysicalRegister(IntB.reg)) {
 144     // Update the liveintervals of sub-registers.
 145     for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) {
 146       LiveInterval &AliasLI = li_->getInterval(*AS);
 147       AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
 148                                  AliasLI.getNextValue(~0U, 0)));
 149     }
 150   }
 151
 152   // Okay, merge "B1" into the same value number as "B0".
 153   if (BValNo != ValLR->ValId)
 154     IntB.MergeValueNumberInto(BValNo, ValLR->ValId);
 155   DOUT << "   result = "; IntB.print(DOUT, mri_);
 156   DOUT << "\n";
 157
 158   // If the source instruction was killing the source register before the
 159   // merge, unset the isKill marker given the live range has been extended.
 160   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
 161   if (UIdx != -1)
 162     ValLREndInst->getOperand(UIdx).unsetIsKill();
 163
 164   // Finally, delete the copy instruction.
 165   li_->RemoveMachineInstrFromMaps(CopyMI);
 166   CopyMI->eraseFromParent();
 167   ++numPeep;
 168   return true;
 169 }
 170
 171 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 172 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 173 /// if the copy was successfully coalesced away, or if it is never possible
 174 /// to coalesce this copy, due to register constraints.  It returns
 175 /// false if it is not currently possible to coalesce this interval, but
 176 /// it may be possible if other things get coalesced.
 177 bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
 178                              unsigned SrcReg, unsigned DstReg, bool PhysOnly) {
 179   DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI;
 180
 181   // Get representative registers.
 182   unsigned repSrcReg = rep(SrcReg);
 183   unsigned repDstReg = rep(DstReg);
 184
 185   // If they are already joined we continue.
 186   if (repSrcReg == repDstReg) {
 187     DOUT << "\tCopy already coalesced.\n";
 188     return true;  // Not coalescable.
 189   }
 190
 191   bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg);
 192   bool DstIsPhys = MRegisterInfo::isPhysicalRegister(repDstReg);
 193   if (PhysOnly && !SrcIsPhys && !DstIsPhys)
 194     // Only joining physical registers with virtual registers in this round.
 195     return true;
 196
 197   // If they are both physical registers, we cannot join them.
 198   if (SrcIsPhys && DstIsPhys) {
 199     DOUT << "\tCan not coalesce physregs.\n";
 200     return true;  // Not coalescable.
 201   }
 202
 203   // We only join virtual registers with allocatable physical registers.
 204   if (SrcIsPhys && !allocatableRegs_[repSrcReg]) {
 205     DOUT << "\tSrc reg is unallocatable physreg.\n";
 206     return true;  // Not coalescable.
 207   }
 208   if (DstIsPhys && !allocatableRegs_[repDstReg]) {
 209     DOUT << "\tDst reg is unallocatable physreg.\n";
 210     return true;  // Not coalescable.
 211   }
 212
 213   // If they are not of the same register class, we cannot join them.
 214   if (differingRegisterClasses(repSrcReg, repDstReg)) {
 215     DOUT << "\tSrc/Dest are different register classes.\n";
 216     return true;  // Not coalescable.
 217   }
 218
 219   LiveInterval &SrcInt = li_->getInterval(repSrcReg);
 220   LiveInterval &DstInt = li_->getInterval(repDstReg);
 221   assert(SrcInt.reg == repSrcReg && DstInt.reg == repDstReg &&
 222          "Register mapping is horribly broken!");
 223
 224   DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_);
 225   DOUT << " and "; DstInt.print(DOUT, mri_);
 226   DOUT << ": ";
 227
 228   // Check if it is necessary to propagate "isDead" property before intervals
 229   // are joined.
 230   MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg);
 231   bool isDead = mopd->isDead();
 232   bool isShorten = false;
 233   unsigned SrcStart = 0, RemoveStart = 0;
 234   unsigned SrcEnd = 0, RemoveEnd = 0;
 235   if (isDead) {
 236     unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
 237     LiveInterval::iterator SrcLR =
 238       SrcInt.FindLiveRangeContaining(li_->getUseIndex(CopyIdx));
 239     RemoveStart = SrcStart = SrcLR->start;
 240     RemoveEnd   = SrcEnd   = SrcLR->end;
 241     // The instruction which defines the src is only truly dead if there are
 242     // no intermediate uses and there isn't a use beyond the copy.
 243     // FIXME: find the last use, mark is kill and shorten the live range.
 244     if (SrcEnd > li_->getDefIndex(CopyIdx)) {
 245       isDead = false;
 246     } else {
 247       MachineOperand *MOU;
 248       MachineInstr *LastUse= lastRegisterUse(SrcStart, CopyIdx, repSrcReg, MOU);
 249       if (LastUse) {
 250         // Shorten the liveinterval to the end of last use.
 251         MOU->setIsKill();
 252         isDead = false;
 253         isShorten = true;
 254         RemoveStart = li_->getDefIndex(li_->getInstructionIndex(LastUse));
 255         RemoveEnd   = SrcEnd;
 256       } else {
 257         MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart);
 258         if (SrcMI) {
 259           MachineOperand *mops = findDefOperand(SrcMI, repSrcReg);
 260           if (mops)
 261             // A dead def should have a single cycle interval.
 262             ++RemoveStart;
 263         }
 264       }
 265     }
 266   }
 267
 268   // We need to be careful about coalescing a source physical register with a
 269   // virtual register. Once the coalescing is done, it cannot be broken and
 270   // these are not spillable! If the destination interval uses are far away,
 271   // think twice about coalescing them!
 272   if (!mopd->isDead() && (SrcIsPhys || DstIsPhys)) {
 273     LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
 274     unsigned JoinVReg = SrcIsPhys ? repDstReg : repSrcReg;
 275     unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg;
 276     const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg);
 277     unsigned Threshold = allocatableRCRegs_[RC].count();
 278
 279     // If the virtual register live interval is long has it has low use desity,
 280     // do not join them, instead mark the physical register as its allocation
 281     // preference.
 282     unsigned Length = JoinVInt.getSize() / InstrSlots::NUM;
 283     LiveVariables::VarInfo &vi = lv_->getVarInfo(JoinVReg);
 284     if (Length > Threshold &&
 285         (((float)vi.NumUses / Length) < (1.0 / Threshold))) {
 286       JoinVInt.preference = JoinPReg;
 287       ++numAborts;
 288       DOUT << "\tMay tie down a physical register, abort!\n";
 289       return false;
 290     }
 291   }
 292
 293   // Okay, attempt to join these two intervals.  On failure, this returns false.
 294   // Otherwise, if one of the intervals being joined is a physreg, this method
 295   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
 296   // been modified, so we can use this information below to update aliases.
 297   if (JoinIntervals(DstInt, SrcInt)) {
 298     if (isDead) {
 299       // Result of the copy is dead. Propagate this property.
 300       if (SrcStart == 0) {
 301         assert(MRegisterInfo::isPhysicalRegister(repSrcReg) &&
 302                "Live-in must be a physical register!");
 303         // Live-in to the function but dead. Remove it from entry live-in set.
 304         // JoinIntervals may end up swapping the two intervals.
 305         mf_->begin()->removeLiveIn(repSrcReg);
 306       } else {
 307         MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart);
 308         if (SrcMI) {
 309           MachineOperand *mops = findDefOperand(SrcMI, repSrcReg);
 310           if (mops)
 311             mops->setIsDead();
 312         }
 313       }
 314     }
 315
 316     if (isShorten || isDead) {
 317       // Shorten the live interval.
 318       LiveInterval &LiveInInt = (repSrcReg == DstInt.reg) ? DstInt : SrcInt;
 319       LiveInInt.removeRange(RemoveStart, RemoveEnd);
 320     }
 321   } else {
 322     // Coalescing failed.
 323
 324     // If we can eliminate the copy without merging the live ranges, do so now.
 325     if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI))
 326       return true;
 327
 328     // Otherwise, we are unable to join the intervals.
 329     DOUT << "Interference!\n";
 330     return false;
 331   }
 332
 333   bool Swapped = repSrcReg == DstInt.reg;
 334   if (Swapped)
 335     std::swap(repSrcReg, repDstReg);
 336   assert(MRegisterInfo::isVirtualRegister(repSrcReg) &&
 337          "LiveInterval::join didn't work right!");
 338
 339   // If we're about to merge live ranges into a physical register live range,
 340   // we have to update any aliased register's live ranges to indicate that they
 341   // have clobbered values for this range.
 342   if (MRegisterInfo::isPhysicalRegister(repDstReg)) {
 343     // Unset unnecessary kills.
 344     if (!DstInt.containsOneValue()) {
 345       for (LiveInterval::Ranges::const_iterator I = SrcInt.begin(),
 346              E = SrcInt.end(); I != E; ++I)
 347         unsetRegisterKills(I->start, I->end, repDstReg);
 348     }
 349
 350     // Update the liveintervals of sub-registers.
 351     for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS)
 352       li_->getInterval(*AS).MergeInClobberRanges(SrcInt);
 353   } else {
 354     // Merge use info if the destination is a virtual register.
 355     LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg);
 356     LiveVariables::VarInfo& sVI = lv_->getVarInfo(repSrcReg);
 357     dVI.NumUses += sVI.NumUses;
 358   }
 359
 360   DOUT << "\n\t\tJoined.  Result = "; DstInt.print(DOUT, mri_);
 361   DOUT << "\n";
 362
 363   // Remember these liveintervals have been joined.
 364   JoinedLIs.set(repSrcReg - MRegisterInfo::FirstVirtualRegister);
 365   if (MRegisterInfo::isVirtualRegister(repDstReg))
 366     JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister);
 367
 368   // If the intervals were swapped by Join, swap them back so that the register
 369   // mapping (in the r2i map) is correct.
 370   if (Swapped) SrcInt.swap(DstInt);
 371
 372   // repSrcReg is guarateed to be the register whose live interval that is
 373   // being merged.
 374   li_->removeInterval(repSrcReg);
 375   r2rMap_[repSrcReg] = repDstReg;
 376
 377   // Finally, delete the copy instruction.
 378   li_->RemoveMachineInstrFromMaps(CopyMI);
 379   CopyMI->eraseFromParent();
 380   ++numPeep;
 381   ++numJoins;
 382   return true;
 383 }
 384
 385 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
 386 /// compute what the resultant value numbers for each value in the input two
 387 /// ranges will be.  This is complicated by copies between the two which can
 388 /// and will commonly cause multiple value numbers to be merged into one.
 389 ///
 390 /// VN is the value number that we're trying to resolve.  InstDefiningValue
 391 /// keeps track of the new InstDefiningValue assignment for the result
 392 /// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
 393 /// whether a value in this or other is a copy from the opposite set.
 394 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
 395 /// already been assigned.
 396 ///
 397 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
 398 /// contains the value number the copy is from.
 399 ///
 400 static unsigned ComputeUltimateVN(unsigned VN,
 401                                   SmallVector<std::pair<unsigned,
 402                                                 unsigned>, 16> &ValueNumberInfo,
 403                                   SmallVector<int, 16> &ThisFromOther,
 404                                   SmallVector<int, 16> &OtherFromThis,
 405                                   SmallVector<int, 16> &ThisValNoAssignments,
 406                                   SmallVector<int, 16> &OtherValNoAssignments,
 407                                   LiveInterval &ThisLI, LiveInterval &OtherLI) {
 408   // If the VN has already been computed, just return it.
 409   if (ThisValNoAssignments[VN] >= 0)
 410     return ThisValNoAssignments[VN];
 411 //  assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?");
 412
 413   // If this val is not a copy from the other val, then it must be a new value
 414   // number in the destination.
 415   int OtherValNo = ThisFromOther[VN];
 416   if (OtherValNo == -1) {
 417     ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN));
 418     return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1;
 419   }
 420
 421   // Otherwise, this *is* a copy from the RHS.  If the other side has already
 422   // been computed, return it.
 423   if (OtherValNoAssignments[OtherValNo] >= 0)
 424     return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo];
 425
 426   // Mark this value number as currently being computed, then ask what the
 427   // ultimate value # of the other value is.
 428   ThisValNoAssignments[VN] = -2;
 429   unsigned UltimateVN =
 430     ComputeUltimateVN(OtherValNo, ValueNumberInfo,
 431                       OtherFromThis, ThisFromOther,
 432                       OtherValNoAssignments, ThisValNoAssignments,
 433                       OtherLI, ThisLI);
 434   return ThisValNoAssignments[VN] = UltimateVN;
 435 }
 436
 437 static bool InVector(unsigned Val, const SmallVector<unsigned, 8> &V) {
 438   return std::find(V.begin(), V.end(), Val) != V.end();
 439 }
 440
 441 /// SimpleJoin - Attempt to joint the specified interval into this one. The
 442 /// caller of this method must guarantee that the RHS only contains a single
 443 /// value number and that the RHS is not defined by a copy from this
 444 /// interval.  This returns false if the intervals are not joinable, or it
 445 /// joins them and returns true.
 446 bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) {
 447   assert(RHS.containsOneValue());
 448
 449   // Some number (potentially more than one) value numbers in the current
 450   // interval may be defined as copies from the RHS.  Scan the overlapping
 451   // portions of the LHS and RHS, keeping track of this and looking for
 452   // overlapping live ranges that are NOT defined as copies.  If these exist, we
 453   // cannot coalesce.
 454
 455   LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end();
 456   LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end();
 457
 458   if (LHSIt->start < RHSIt->start) {
 459     LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start);
 460     if (LHSIt != LHS.begin()) --LHSIt;
 461   } else if (RHSIt->start < LHSIt->start) {
 462     RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start);
 463     if (RHSIt != RHS.begin()) --RHSIt;
 464   }
 465
 466   SmallVector<unsigned, 8> EliminatedLHSVals;
 467
 468   while (1) {
 469     // Determine if these live intervals overlap.
 470     bool Overlaps = false;
 471     if (LHSIt->start <= RHSIt->start)
 472       Overlaps = LHSIt->end > RHSIt->start;
 473     else
 474       Overlaps = RHSIt->end > LHSIt->start;
 475
 476     // If the live intervals overlap, there are two interesting cases: if the
 477     // LHS interval is defined by a copy from the RHS, it's ok and we record
 478     // that the LHS value # is the same as the RHS.  If it's not, then we cannot
 479     // coalesce these live ranges and we bail out.
 480     if (Overlaps) {
 481       // If we haven't already recorded that this value # is safe, check it.
 482       if (!InVector(LHSIt->ValId, EliminatedLHSVals)) {
 483         // Copy from the RHS?
 484         unsigned SrcReg = LHS.getSrcRegForValNum(LHSIt->ValId);
 485         if (rep(SrcReg) != RHS.reg)
 486           return false;    // Nope, bail out.
 487
 488         EliminatedLHSVals.push_back(LHSIt->ValId);
 489       }
 490
 491       // We know this entire LHS live range is okay, so skip it now.
 492       if (++LHSIt == LHSEnd) break;
 493       continue;
 494     }
 495
 496     if (LHSIt->end < RHSIt->end) {
 497       if (++LHSIt == LHSEnd) break;
 498     } else {
 499       // One interesting case to check here.  It's possible that we have
 500       // something like "X3 = Y" which defines a new value number in the LHS,
 501       // and is the last use of this liverange of the RHS.  In this case, we
 502       // want to notice this copy (so that it gets coalesced away) even though
 503       // the live ranges don't actually overlap.
 504       if (LHSIt->start == RHSIt->end) {
 505         if (InVector(LHSIt->ValId, EliminatedLHSVals)) {
 506           // We already know that this value number is going to be merged in
 507           // if coalescing succeeds.  Just skip the liverange.
 508           if (++LHSIt == LHSEnd) break;
 509         } else {
 510           // Otherwise, if this is a copy from the RHS, mark it as being merged
 511           // in.
 512           if (rep(LHS.getSrcRegForValNum(LHSIt->ValId)) == RHS.reg) {
 513             EliminatedLHSVals.push_back(LHSIt->ValId);
 514
 515             // We know this entire LHS live range is okay, so skip it now.
 516             if (++LHSIt == LHSEnd) break;
 517           }
 518         }
 519       }
 520
 521       if (++RHSIt == RHSEnd) break;
 522     }
 523   }
 524
 525   // If we got here, we know that the coalescing will be successful and that
 526   // the value numbers in EliminatedLHSVals will all be merged together.  Since
 527   // the most common case is that EliminatedLHSVals has a single number, we
 528   // optimize for it: if there is more than one value, we merge them all into
 529   // the lowest numbered one, then handle the interval as if we were merging
 530   // with one value number.
 531   unsigned LHSValNo;
 532   if (EliminatedLHSVals.size() > 1) {
 533     // Loop through all the equal value numbers merging them into the smallest
 534     // one.
 535     unsigned Smallest = EliminatedLHSVals[0];
 536     for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) {
 537       if (EliminatedLHSVals[i] < Smallest) {
 538         // Merge the current notion of the smallest into the smaller one.
 539         LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]);
 540         Smallest = EliminatedLHSVals[i];
 541       } else {
 542         // Merge into the smallest.
 543         LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest);
 544       }
 545     }
 546     LHSValNo = Smallest;
 547   } else {
 548     assert(!EliminatedLHSVals.empty() && "No copies from the RHS?");
 549     LHSValNo = EliminatedLHSVals[0];
 550   }
 551
 552   // Okay, now that there is a single LHS value number that we're merging the
 553   // RHS into, update the value number info for the LHS to indicate that the
 554   // value number is defined where the RHS value number was.
 555   LHS.setValueNumberInfo(LHSValNo, RHS.getValNumInfo(0));
 556
 557   // Okay, the final step is to loop over the RHS live intervals, adding them to
 558   // the LHS.
 559   LHS.MergeRangesInAsValue(RHS, LHSValNo);
 560   LHS.weight += RHS.weight;
 561   if (RHS.preference && !LHS.preference)
 562     LHS.preference = RHS.preference;
 563
 564   return true;
 565 }
 566
 567 /// JoinIntervals - Attempt to join these two intervals.  On failure, this
 568 /// returns false.  Otherwise, if one of the intervals being joined is a
 569 /// physreg, this method always canonicalizes LHS to be it.  The output
 570 /// "RHS" will not have been modified, so we can use this information
 571 /// below to update aliases.
 572 bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) {
 573   // Compute the final value assignment, assuming that the live ranges can be
 574   // coalesced.
 575   SmallVector<int, 16> LHSValNoAssignments;
 576   SmallVector<int, 16> RHSValNoAssignments;
 577   SmallVector<std::pair<unsigned,unsigned>, 16> ValueNumberInfo;
 578
 579   // If a live interval is a physical register, conservatively check if any
 580   // of its sub-registers is overlapping the live interval of the virtual
 581   // register. If so, do not coalesce.
 582   if (MRegisterInfo::isPhysicalRegister(LHS.reg) &&
 583       *mri_->getSubRegisters(LHS.reg)) {
 584     for (const unsigned* SR = mri_->getSubRegisters(LHS.reg); *SR; ++SR)
 585       if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
 586         DOUT << "Interfere with sub-register ";
 587         DEBUG(li_->getInterval(*SR).print(DOUT, mri_));
 588         return false;
 589       }
 590   } else if (MRegisterInfo::isPhysicalRegister(RHS.reg) &&
 591              *mri_->getSubRegisters(RHS.reg)) {
 592     for (const unsigned* SR = mri_->getSubRegisters(RHS.reg); *SR; ++SR)
 593       if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) {
 594         DOUT << "Interfere with sub-register ";
 595         DEBUG(li_->getInterval(*SR).print(DOUT, mri_));
 596         return false;
 597       }
 598   }
 599
 600   // Compute ultimate value numbers for the LHS and RHS values.
 601   if (RHS.containsOneValue()) {
 602     // Copies from a liveinterval with a single value are simple to handle and
 603     // very common, handle the special case here.  This is important, because
 604     // often RHS is small and LHS is large (e.g. a physreg).
 605
 606     // Find out if the RHS is defined as a copy from some value in the LHS.
 607     int RHSValID = -1;
 608     std::pair<unsigned,unsigned> RHSValNoInfo;
 609     unsigned RHSSrcReg = RHS.getSrcRegForValNum(0);
 610     if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) {
 611       // If RHS is not defined as a copy from the LHS, we can use simpler and
 612       // faster checks to see if the live ranges are coalescable.  This joiner
 613       // can't swap the LHS/RHS intervals though.
 614       if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) {
 615         return SimpleJoin(LHS, RHS);
 616       } else {
 617         RHSValNoInfo = RHS.getValNumInfo(0);
 618       }
 619     } else {
 620       // It was defined as a copy from the LHS, find out what value # it is.
 621       unsigned ValInst = RHS.getInstForValNum(0);
 622       RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId;
 623       RHSValNoInfo = LHS.getValNumInfo(RHSValID);
 624     }
 625
 626     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
 627     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
 628     ValueNumberInfo.resize(LHS.getNumValNums());
 629
 630     // Okay, *all* of the values in LHS that are defined as a copy from RHS
 631     // should now get updated.
 632     for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
 633       if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) {
 634         if (rep(LHSSrcReg) != RHS.reg) {
 635           // If this is not a copy from the RHS, its value number will be
 636           // unmodified by the coalescing.
 637           ValueNumberInfo[VN] = LHS.getValNumInfo(VN);
 638           LHSValNoAssignments[VN] = VN;
 639         } else if (RHSValID == -1) {
 640           // Otherwise, it is a copy from the RHS, and we don't already have a
 641           // value# for it.  Keep the current value number, but remember it.
 642           LHSValNoAssignments[VN] = RHSValID = VN;
 643           ValueNumberInfo[VN] = RHSValNoInfo;
 644         } else {
 645           // Otherwise, use the specified value #.
 646           LHSValNoAssignments[VN] = RHSValID;
 647           if (VN != (unsigned)RHSValID)
 648             ValueNumberInfo[VN].first = ~1U;
 649           else
 650             ValueNumberInfo[VN] = RHSValNoInfo;
 651         }
 652       } else {
 653         ValueNumberInfo[VN] = LHS.getValNumInfo(VN);
 654         LHSValNoAssignments[VN] = VN;
 655       }
 656     }
 657
 658     assert(RHSValID != -1 && "Didn't find value #?");
 659     RHSValNoAssignments[0] = RHSValID;
 660
 661   } else {
 662     // Loop over the value numbers of the LHS, seeing if any are defined from
 663     // the RHS.
 664     SmallVector<int, 16> LHSValsDefinedFromRHS;
 665     LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1);
 666     for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
 667       unsigned ValSrcReg = LHS.getSrcRegForValNum(VN);
 668       if (ValSrcReg == 0)  // Src not defined by a copy?
 669         continue;
 670
 671       // DstReg is known to be a register in the LHS interval.  If the src is
 672       // from the RHS interval, we can use its value #.
 673       if (rep(ValSrcReg) != RHS.reg)
 674         continue;
 675
 676       // Figure out the value # from the RHS.
 677       unsigned ValInst = LHS.getInstForValNum(VN);
 678       LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId;
 679     }
 680
 681     // Loop over the value numbers of the RHS, seeing if any are defined from
 682     // the LHS.
 683     SmallVector<int, 16> RHSValsDefinedFromLHS;
 684     RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1);
 685     for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
 686       unsigned ValSrcReg = RHS.getSrcRegForValNum(VN);
 687       if (ValSrcReg == 0)  // Src not defined by a copy?
 688         continue;
 689
 690       // DstReg is known to be a register in the RHS interval.  If the src is
 691       // from the LHS interval, we can use its value #.
 692       if (rep(ValSrcReg) != LHS.reg)
 693         continue;
 694
 695       // Figure out the value # from the LHS.
 696       unsigned ValInst = RHS.getInstForValNum(VN);
 697       RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId;
 698     }
 699
 700     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
 701     RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
 702     ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
 703
 704     for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
 705       if (LHSValNoAssignments[VN] >= 0 || LHS.getInstForValNum(VN) == ~2U)
 706         continue;
 707       ComputeUltimateVN(VN, ValueNumberInfo,
 708                         LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
 709                         LHSValNoAssignments, RHSValNoAssignments, LHS, RHS);
 710     }
 711     for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
 712       if (RHSValNoAssignments[VN] >= 0 || RHS.getInstForValNum(VN) == ~2U)
 713         continue;
 714       // If this value number isn't a copy from the LHS, it's a new number.
 715       if (RHSValsDefinedFromLHS[VN] == -1) {
 716         ValueNumberInfo.push_back(RHS.getValNumInfo(VN));
 717         RHSValNoAssignments[VN] = ValueNumberInfo.size()-1;
 718         continue;
 719       }
 720
 721       ComputeUltimateVN(VN, ValueNumberInfo,
 722                         RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
 723                         RHSValNoAssignments, LHSValNoAssignments, RHS, LHS);
 724     }
 725   }
 726
 727   // Armed with the mappings of LHS/RHS values to ultimate values, walk the
 728   // interval lists to see if these intervals are coalescable.
 729   LiveInterval::const_iterator I = LHS.begin();
 730   LiveInterval::const_iterator IE = LHS.end();
 731   LiveInterval::const_iterator J = RHS.begin();
 732   LiveInterval::const_iterator JE = RHS.end();
 733
 734   // Skip ahead until the first place of potential sharing.
 735   if (I->start < J->start) {
 736     I = std::upper_bound(I, IE, J->start);
 737     if (I != LHS.begin()) --I;
 738   } else if (J->start < I->start) {
 739     J = std::upper_bound(J, JE, I->start);
 740     if (J != RHS.begin()) --J;
 741   }
 742
 743   while (1) {
 744     // Determine if these two live ranges overlap.
 745     bool Overlaps;
 746     if (I->start < J->start) {
 747       Overlaps = I->end > J->start;
 748     } else {
 749       Overlaps = J->end > I->start;
 750     }
 751
 752     // If so, check value # info to determine if they are really different.
 753     if (Overlaps) {
 754       // If the live range overlap will map to the same value number in the
 755       // result liverange, we can still coalesce them.  If not, we can't.
 756       if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId])
 757         return false;
 758     }
 759
 760     if (I->end < J->end) {
 761       ++I;
 762       if (I == IE) break;
 763     } else {
 764       ++J;
 765       if (J == JE) break;
 766     }
 767   }
 768
 769   // If we get here, we know that we can coalesce the live ranges.  Ask the
 770   // intervals to coalesce themselves now.
 771   LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],
 772            ValueNumberInfo);
 773   return true;
 774 }
 775
 776 namespace {
 777   // DepthMBBCompare - Comparison predicate that sort first based on the loop
 778   // depth of the basic block (the unsigned), and then on the MBB number.
 779   struct DepthMBBCompare {
 780     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
 781     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
 782       if (LHS.first > RHS.first) return true;   // Deeper loops first
 783       return LHS.first == RHS.first &&
 784         LHS.second->getNumber() < RHS.second->getNumber();
 785     }
 786   };
 787 }
 788
 789 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
 790                                 std::vector<CopyRec> *TryAgain, bool PhysOnly) {
 791   DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 792
 793   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
 794        MII != E;) {
 795     MachineInstr *Inst = MII++;
 796
 797     // If this isn't a copy, we can't join intervals.
 798     unsigned SrcReg, DstReg;
 799     if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue;
 800
 801     if (TryAgain && !JoinCopy(Inst, SrcReg, DstReg, PhysOnly))
 802       TryAgain->push_back(getCopyRec(Inst, SrcReg, DstReg));
 803   }
 804 }
 805
 806 void SimpleRegisterCoalescing::joinIntervals() {
 807   DOUT << "********** JOINING INTERVALS ***********\n";
 808
 809   JoinedLIs.resize(li_->getNumIntervals());
 810   JoinedLIs.reset();
 811
 812   std::vector<CopyRec> TryAgainList;
 813   const LoopInfo &LI = getAnalysis<LoopInfo>();
 814   if (LI.begin() == LI.end()) {
 815     // If there are no loops in the function, join intervals in function order.
 816     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
 817          I != E; ++I)
 818       CopyCoalesceInMBB(I, &TryAgainList);
 819   } else {
 820     // Otherwise, join intervals in inner loops before other intervals.
 821     // Unfortunately we can't just iterate over loop hierarchy here because
 822     // there may be more MBB's than BB's.  Collect MBB's for sorting.
 823
 824     // Join intervals in the function prolog first. We want to join physical
 825     // registers with virtual registers before the intervals got too long.
 826     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
 827     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); I != E;++I)
 828       MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I));
 829
 830     // Sort by loop depth.
 831     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
 832
 833     // Finally, join intervals in loop nest order.
 834     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
 835       CopyCoalesceInMBB(MBBs[i].second, NULL, true);
 836     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
 837       CopyCoalesceInMBB(MBBs[i].second, &TryAgainList, false);
 838   }
 839
 840   // Joining intervals can allow other intervals to be joined.  Iteratively join
 841   // until we make no progress.
 842   bool ProgressMade = true;
 843   while (ProgressMade) {
 844     ProgressMade = false;
 845
 846     for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
 847       CopyRec &TheCopy = TryAgainList[i];
 848       if (TheCopy.MI &&
 849           JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) {
 850         TheCopy.MI = 0;   // Mark this one as done.
 851         ProgressMade = true;
 852       }
 853     }
 854   }
 855
 856   // Some live range has been lengthened due to colaescing, eliminate the
 857   // unnecessary kills.
 858   int RegNum = JoinedLIs.find_first();
 859   while (RegNum != -1) {
 860     unsigned Reg = RegNum + MRegisterInfo::FirstVirtualRegister;
 861     unsigned repReg = rep(Reg);
 862     LiveInterval &LI = li_->getInterval(repReg);
 863     LiveVariables::VarInfo& svi = lv_->getVarInfo(Reg);
 864     for (unsigned i = 0, e = svi.Kills.size(); i != e; ++i) {
 865       MachineInstr *Kill = svi.Kills[i];
 866       // Suppose vr1 = op vr2, x
 867       // and vr1 and vr2 are coalesced. vr2 should still be marked kill
 868       // unless it is a two-address operand.
 869       if (li_->isRemoved(Kill) || hasRegisterDef(Kill, repReg))
 870         continue;
 871       if (LI.liveAt(li_->getInstructionIndex(Kill) + InstrSlots::NUM))
 872         unsetRegisterKill(Kill, repReg);
 873     }
 874     RegNum = JoinedLIs.find_next(RegNum);
 875   }
 876
 877   DOUT << "*** Register mapping ***\n";
 878   for (int i = 0, e = r2rMap_.size(); i != e; ++i)
 879     if (r2rMap_[i]) {
 880       DOUT << "  reg " << i << " -> ";
 881       DEBUG(printRegName(r2rMap_[i]));
 882       DOUT << "\n";
 883     }
 884 }
 885
 886 /// Return true if the two specified registers belong to different register
 887 /// classes.  The registers may be either phys or virt regs.
 888 bool SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
 889                                              unsigned RegB) const {
 890
 891   // Get the register classes for the first reg.
 892   if (MRegisterInfo::isPhysicalRegister(RegA)) {
 893     assert(MRegisterInfo::isVirtualRegister(RegB) &&
 894            "Shouldn't consider two physregs!");
 895     return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA);
 896   }
 897
 898   // Compare against the regclass for the second reg.
 899   const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA);
 900   if (MRegisterInfo::isVirtualRegister(RegB))
 901     return RegClass != mf_->getSSARegMap()->getRegClass(RegB);
 902   else
 903     return !RegClass->contains(RegB);
 904 }
 905
 906 /// lastRegisterUse - Returns the last use of the specific register between
 907 /// cycles Start and End. It also returns the use operand by reference. It
 908 /// returns NULL if there are no uses.
 909 MachineInstr *
 910 SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
 911                                MachineOperand *&MOU) {
 912   int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM;
 913   int s = Start;
 914   while (e >= s) {
 915     // Skip deleted instructions
 916     MachineInstr *MI = li_->getInstructionFromIndex(e);
 917     while ((e - InstrSlots::NUM) >= s && !MI) {
 918       e -= InstrSlots::NUM;
 919       MI = li_->getInstructionFromIndex(e);
 920     }
 921     if (e < s || MI == NULL)
 922       return NULL;
 923
 924     for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
 925       MachineOperand &MO = MI->getOperand(i);
 926       if (MO.isReg() && MO.isUse() && MO.getReg() &&
 927           mri_->regsOverlap(rep(MO.getReg()), Reg)) {
 928         MOU = &MO;
 929         return MI;
 930       }
 931     }
 932
 933     e -= InstrSlots::NUM;
 934   }
 935
 936   return NULL;
 937 }
 938
 939
 940 /// findDefOperand - Returns the MachineOperand that is a def of the specific
 941 /// register. It returns NULL if the def is not found.
 942 MachineOperand *SimpleRegisterCoalescing::findDefOperand(MachineInstr *MI, unsigned Reg) {
 943   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 944     MachineOperand &MO = MI->getOperand(i);
 945     if (MO.isReg() && MO.isDef() &&
 946         mri_->regsOverlap(rep(MO.getReg()), Reg))
 947       return &MO;
 948   }
 949   return NULL;
 950 }
 951
 952 /// unsetRegisterKill - Unset IsKill property of all uses of specific register
 953 /// of the specific instruction.
 954 void SimpleRegisterCoalescing::unsetRegisterKill(MachineInstr *MI, unsigned Reg) {
 955   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 956     MachineOperand &MO = MI->getOperand(i);
 957     if (MO.isReg() && MO.isKill() && MO.getReg() &&
 958         mri_->regsOverlap(rep(MO.getReg()), Reg))
 959       MO.unsetIsKill();
 960   }
 961 }
 962
 963 /// unsetRegisterKills - Unset IsKill property of all uses of specific register
 964 /// between cycles Start and End.
 965 void SimpleRegisterCoalescing::unsetRegisterKills(unsigned Start, unsigned End,
 966                                        unsigned Reg) {
 967   int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM;
 968   int s = Start;
 969   while (e >= s) {
 970     // Skip deleted instructions
 971     MachineInstr *MI = li_->getInstructionFromIndex(e);
 972     while ((e - InstrSlots::NUM) >= s && !MI) {
 973       e -= InstrSlots::NUM;
 974       MI = li_->getInstructionFromIndex(e);
 975     }
 976     if (e < s || MI == NULL)
 977       return;
 978
 979     for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
 980       MachineOperand &MO = MI->getOperand(i);
 981       if (MO.isReg() && MO.isKill() && MO.getReg() &&
 982           mri_->regsOverlap(rep(MO.getReg()), Reg)) {
 983         MO.unsetIsKill();
 984       }
 985     }
 986
 987     e -= InstrSlots::NUM;
 988   }
 989 }
 990
 991 /// hasRegisterDef - True if the instruction defines the specific register.
 992 ///
 993 bool SimpleRegisterCoalescing::hasRegisterDef(MachineInstr *MI, unsigned Reg) {
 994   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 995     MachineOperand &MO = MI->getOperand(i);
 996     if (MO.isReg() && MO.isDef() &&
 997         mri_->regsOverlap(rep(MO.getReg()), Reg))
 998       return true;
 999   }
1000   return false;
1001 }
1002
1003 void SimpleRegisterCoalescing::printRegName(unsigned reg) const {
1004   if (MRegisterInfo::isPhysicalRegister(reg))
1005     cerr << mri_->getName(reg);
1006   else
1007     cerr << "%reg" << reg;
1008 }
1009
1010 void SimpleRegisterCoalescing::releaseMemory() {
1011    r2rMap_.clear();
1012    JoinedLIs.clear();
1013 }
1014
1015 static bool isZeroLengthInterval(LiveInterval *li) {
1016   for (LiveInterval::Ranges::const_iterator
1017          i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
1018     if (i->end - i->start > LiveIntervals::InstrSlots::NUM)
1019       return false;
1020   return true;
1021 }
1022
1023 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
1024   mf_ = &fn;
1025   tm_ = &fn.getTarget();
1026   mri_ = tm_->getRegisterInfo();
1027   tii_ = tm_->getInstrInfo();
1028   li_ = &getAnalysis<LiveIntervals>();
1029   lv_ = &getAnalysis<LiveVariables>();
1030
1031   DOUT << "********** SIMPLE REGISTER COALESCING **********\n"
1032        << "********** Function: "
1033        << ((Value*)mf_->getFunction())->getName() << '\n';
1034
1035   allocatableRegs_ = mri_->getAllocatableSet(fn);
1036   for (MRegisterInfo::regclass_iterator I = mri_->regclass_begin(),
1037          E = mri_->regclass_end(); I != E; ++I)
1038     allocatableRCRegs_.insert(std::make_pair(*I,mri_->getAllocatableSet(fn, *I)));
1039
1040   r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg());
1041
1042   // Join (coalesce) intervals if requested.
1043   if (EnableJoining) {
1044     joinIntervals();
1045     DOUT << "********** INTERVALS POST JOINING **********\n";
1046     for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) {
1047       I->second.print(DOUT, mri_);
1048       DOUT << "\n";
1049     }
1050   }
1051
1052   // perform a final pass over the instructions and compute spill
1053   // weights, coalesce virtual registers and remove identity moves.
1054   const LoopInfo &loopInfo = getAnalysis<LoopInfo>();
1055
1056   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
1057        mbbi != mbbe; ++mbbi) {
1058     MachineBasicBlock* mbb = mbbi;
1059     unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());
1060
1061     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
1062          mii != mie; ) {
1063       // if the move will be an identity move delete it
1064       unsigned srcReg, dstReg, RegRep;
1065       if (tii_->isMoveInstr(*mii, srcReg, dstReg) &&
1066           (RegRep = rep(srcReg)) == rep(dstReg)) {
1067         // remove from def list
1068         LiveInterval &RegInt = li_->getOrCreateInterval(RegRep);
1069         MachineOperand *MO = mii->findRegisterDefOperand(dstReg);
1070         // If def of this move instruction is dead, remove its live range from
1071         // the dstination register's live interval.
1072         if (MO->isDead()) {
1073           unsigned MoveIdx = li_->getDefIndex(li_->getInstructionIndex(mii));
1074           LiveInterval::iterator MLR = RegInt.FindLiveRangeContaining(MoveIdx);
1075           RegInt.removeRange(MLR->start, MoveIdx+1);
1076           if (RegInt.empty())
1077             li_->removeInterval(RegRep);
1078         }
1079         li_->RemoveMachineInstrFromMaps(mii);
1080         mii = mbbi->erase(mii);
1081         ++numPeep;
1082       } else {
1083         SmallSet<unsigned, 4> UniqueUses;
1084         for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
1085           const MachineOperand &mop = mii->getOperand(i);
1086           if (mop.isRegister() && mop.getReg() &&
1087               MRegisterInfo::isVirtualRegister(mop.getReg())) {
1088             // replace register with representative register
1089             unsigned reg = rep(mop.getReg());
1090             mii->getOperand(i).setReg(reg);
1091
1092             // Multiple uses of reg by the same instruction. It should not
1093             // contribute to spill weight again.
1094             if (UniqueUses.count(reg) != 0)
1095               continue;
1096             LiveInterval &RegInt = li_->getInterval(reg);
1097             float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth);
1098             // If the definition instruction is re-materializable, its spill
1099             // weight is half of what it would have been normally unless it's
1100             // a load from fixed stack slot.
1101             int Dummy;
1102             if (RegInt.remat && !tii_->isLoadFromStackSlot(RegInt.remat, Dummy))
1103               w /= 2;
1104             RegInt.weight += w;
1105             UniqueUses.insert(reg);
1106           }
1107         }
1108         ++mii;
1109       }
1110     }
1111   }
1112
1113   for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) {
1114     LiveInterval &LI = I->second;
1115     if (MRegisterInfo::isVirtualRegister(LI.reg)) {
1116       // If the live interval length is essentially zero, i.e. in every live
1117       // range the use follows def immediately, it doesn't make sense to spill
1118       // it and hope it will be easier to allocate for this li.
1119       if (isZeroLengthInterval(&LI))
1120         LI.weight = HUGE_VALF;
1121
1122       // Slightly prefer live interval that has been assigned a preferred reg.
1123       if (LI.preference)
1124         LI.weight *= 1.01F;
1125
1126       // Divide the weight of the interval by its size.  This encourages
1127       // spilling of intervals that are large and have few uses, and
1128       // discourages spilling of small intervals with many uses.
1129       LI.weight /= LI.getSize();
1130     }
1131   }
1132
1133   DEBUG(dump());
1134   return true;
1135 }
1136
1137 /// print - Implement the dump method.
1138 void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const {
1139    li_->print(O, m);
1140 }