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