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