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