1 //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a simple register coalescing pass that attempts to
11 // aggressively coalesce every register copy that it can.
13 //===----------------------------------------------------------------------===//
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"
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");
51 char SimpleRegisterCoalescing::ID = 0;
53 EnableJoining("join-liveintervals",
54 cl::desc("Coalesce copies (default=true)"),
58 DisableCrossClassJoin("disable-cross-class-join",
59 cl::desc("Avoid coalescing cross register class copies"),
60 cl::init(false), cl::Hidden);
62 static RegisterPass<SimpleRegisterCoalescing>
63 X("simple-register-coalescing", "Simple Register Coalescing");
65 // Declare that we implement the RegisterCoalescer interface
66 static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
68 const PassInfo *const llvm::SimpleRegisterCoalescingID = &X;
70 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
72 AU.addRequired<AliasAnalysis>();
73 AU.addRequired<LiveIntervals>();
74 AU.addPreserved<LiveIntervals>();
75 AU.addPreserved<SlotIndexes>();
76 AU.addRequired<MachineLoopInfo>();
77 AU.addPreserved<MachineLoopInfo>();
78 AU.addPreservedID(MachineDominatorsID);
80 AU.addPreservedID(StrongPHIEliminationID);
82 AU.addPreservedID(PHIEliminationID);
83 AU.addPreservedID(TwoAddressInstructionPassID);
84 MachineFunctionPass::getAnalysisUsage(AU);
87 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
88 /// being the source and IntB being the dest, thus this defines a value number
89 /// in IntB. If the source value number (in IntA) is defined by a copy from B,
90 /// see if we can merge these two pieces of B into a single value number,
91 /// eliminating a copy. For example:
95 /// B1 = A3 <- this copy
97 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
98 /// value number to be replaced with B0 (which simplifies the B liveinterval).
100 /// This returns true if an interval was modified.
102 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(const CoalescerPair &CP,
103 MachineInstr *CopyMI) {
105 li_->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
107 li_->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
108 SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
110 // BValNo is a value number in B that is defined by a copy from A. 'B3' in
111 // the example above.
112 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
113 assert(BLR != IntB.end() && "Live range not found!");
114 VNInfo *BValNo = BLR->valno;
116 // Get the location that B is defined at. Two options: either this value has
117 // an unknown definition point or it is defined at CopyIdx. If unknown, we
119 if (!BValNo->getCopy()) return false;
120 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
122 // AValNo is the value number in A that defines the copy, A3 in the example.
123 SlotIndex CopyUseIdx = CopyIdx.getUseIndex();
124 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
125 assert(ALR != IntA.end() && "Live range not found!");
126 VNInfo *AValNo = ALR->valno;
127 // If it's re-defined by an early clobber somewhere in the live range, then
128 // it's not safe to eliminate the copy. FIXME: This is a temporary workaround.
130 // 172 %ECX<def> = MOV32rr %reg1039<kill>
131 // 180 INLINEASM <es:subl $5,$1
132 // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9,
134 // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0
135 // 188 %EAX<def> = MOV32rr %EAX<kill>
136 // 196 %ECX<def> = MOV32rr %ECX<kill>
137 // 204 %ECX<def> = MOV32rr %ECX<kill>
138 // 212 %EAX<def> = MOV32rr %EAX<kill>
139 // 220 %EAX<def> = MOV32rr %EAX
140 // 228 %reg1039<def> = MOV32rr %ECX<kill>
141 // The early clobber operand ties ECX input to the ECX def.
143 // The live interval of ECX is represented as this:
144 // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47)
145 // The coalescer has no idea there was a def in the middle of [174,230].
146 if (AValNo->hasRedefByEC())
149 // If AValNo is defined as a copy from IntB, we can potentially process this.
150 // Get the instruction that defines this value number.
151 if (!CP.isCoalescable(AValNo->getCopy()))
154 // Get the LiveRange in IntB that this value number starts with.
155 LiveInterval::iterator ValLR =
156 IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot());
157 if (ValLR == IntB.end())
160 // Make sure that the end of the live range is inside the same block as
162 MachineInstr *ValLREndInst =
163 li_->getInstructionFromIndex(ValLR->end.getPrevSlot());
164 if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent())
167 // Okay, we now know that ValLR ends in the same block that the CopyMI
168 // live-range starts. If there are no intervening live ranges between them in
169 // IntB, we can merge them.
170 if (ValLR+1 != BLR) return false;
172 // If a live interval is a physical register, conservatively check if any
173 // of its sub-registers is overlapping the live interval of the virtual
174 // register. If so, do not coalesce.
175 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) &&
176 *tri_->getSubRegisters(IntB.reg)) {
177 for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
178 if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) {
180 dbgs() << "\t\tInterfere with sub-register ";
181 li_->getInterval(*SR).print(dbgs(), tri_);
188 dbgs() << "Extending: ";
189 IntB.print(dbgs(), tri_);
192 SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
193 // We are about to delete CopyMI, so need to remove it as the 'instruction
194 // that defines this value #'. Update the valnum with the new defining
196 BValNo->def = FillerStart;
199 // Okay, we can merge them. We need to insert a new liverange:
200 // [ValLR.end, BLR.begin) of either value number, then we merge the
201 // two value numbers.
202 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
204 // If the IntB live range is assigned to a physical register, and if that
205 // physreg has sub-registers, update their live intervals as well.
206 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
207 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
208 LiveInterval &SRLI = li_->getInterval(*SR);
209 SRLI.addRange(LiveRange(FillerStart, FillerEnd,
210 SRLI.getNextValue(FillerStart, 0, true,
211 li_->getVNInfoAllocator())));
215 // Okay, merge "B1" into the same value number as "B0".
216 if (BValNo != ValLR->valno) {
217 IntB.MergeValueNumberInto(BValNo, ValLR->valno);
220 dbgs() << " result = ";
221 IntB.print(dbgs(), tri_);
225 // If the source instruction was killing the source register before the
226 // merge, unset the isKill marker given the live range has been extended.
227 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
229 ValLREndInst->getOperand(UIdx).setIsKill(false);
232 // If the copy instruction was killing the destination register before the
233 // merge, find the last use and trim the live range. That will also add the
235 if (ALR->end == CopyIdx)
236 TrimLiveIntervalToLastUse(CopyUseIdx, CopyMI->getParent(), IntA, ALR);
242 /// HasOtherReachingDefs - Return true if there are definitions of IntB
243 /// other than BValNo val# that can reach uses of AValno val# of IntA.
244 bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA,
248 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
250 if (AI->valno != AValNo) continue;
251 LiveInterval::Ranges::iterator BI =
252 std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
253 if (BI != IntB.ranges.begin())
255 for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
256 if (BI->valno == BValNo)
258 // When BValNo is null, we're looking for a dummy clobber-value for a subreg.
259 if (!BValNo && !BI->valno->isDefAccurate() && !BI->valno->getCopy())
261 if (BI->start <= AI->start && BI->end > AI->start)
263 if (BI->start > AI->start && BI->start < AI->end)
271 TransferImplicitOps(MachineInstr *MI, MachineInstr *NewMI) {
272 for (unsigned i = MI->getDesc().getNumOperands(), e = MI->getNumOperands();
274 MachineOperand &MO = MI->getOperand(i);
275 if (MO.isReg() && MO.isImplicit())
276 NewMI->addOperand(MO);
280 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with
281 /// IntA being the source and IntB being the dest, thus this defines a value
282 /// number in IntB. If the source value number (in IntA) is defined by a
283 /// commutable instruction and its other operand is coalesced to the copy dest
284 /// register, see if we can transform the copy into a noop by commuting the
285 /// definition. For example,
287 /// A3 = op A2 B0<kill>
289 /// B1 = A3 <- this copy
291 /// = op A3 <- more uses
295 /// B2 = op B0 A2<kill>
297 /// B1 = B2 <- now an identify copy
299 /// = op B2 <- more uses
301 /// This returns true if an interval was modified.
303 bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
305 MachineInstr *CopyMI) {
307 li_->getInstructionIndex(CopyMI).getDefIndex();
309 // FIXME: For now, only eliminate the copy by commuting its def when the
310 // source register is a virtual register. We want to guard against cases
311 // where the copy is a back edge copy and commuting the def lengthen the
312 // live interval of the source register to the entire loop.
313 if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
316 // BValNo is a value number in B that is defined by a copy from A. 'B3' in
317 // the example above.
318 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
319 assert(BLR != IntB.end() && "Live range not found!");
320 VNInfo *BValNo = BLR->valno;
322 // Get the location that B is defined at. Two options: either this value has
323 // an unknown definition point or it is defined at CopyIdx. If unknown, we
325 if (!BValNo->getCopy()) return false;
326 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
328 // AValNo is the value number in A that defines the copy, A3 in the example.
329 LiveInterval::iterator ALR =
330 IntA.FindLiveRangeContaining(CopyIdx.getUseIndex()); //
332 assert(ALR != IntA.end() && "Live range not found!");
333 VNInfo *AValNo = ALR->valno;
334 // If other defs can reach uses of this def, then it's not safe to perform
335 // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be
337 if (AValNo->isPHIDef() || !AValNo->isDefAccurate() ||
338 AValNo->isUnused() || AValNo->hasPHIKill())
340 MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def);
341 const TargetInstrDesc &TID = DefMI->getDesc();
342 if (!TID.isCommutable())
344 // If DefMI is a two-address instruction then commuting it will change the
345 // destination register.
346 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg);
347 assert(DefIdx != -1);
349 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
351 unsigned Op1, Op2, NewDstIdx;
352 if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2))
356 else if (Op2 == UseOpIdx)
361 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
362 unsigned NewReg = NewDstMO.getReg();
363 if (NewReg != IntB.reg || !NewDstMO.isKill())
366 // Make sure there are no other definitions of IntB that would reach the
367 // uses which the new definition can reach.
368 if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
371 bool BHasSubRegs = false;
372 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg))
373 BHasSubRegs = *tri_->getSubRegisters(IntB.reg);
375 // Abort if the subregisters of IntB.reg have values that are not simply the
376 // clobbers from the superreg.
378 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
379 if (HasOtherReachingDefs(IntA, li_->getInterval(*SR), AValNo, 0))
382 // If some of the uses of IntA.reg is already coalesced away, return false.
383 // It's not possible to determine whether it's safe to perform the coalescing.
384 for (MachineRegisterInfo::use_nodbg_iterator UI =
385 mri_->use_nodbg_begin(IntA.reg),
386 UE = mri_->use_nodbg_end(); UI != UE; ++UI) {
387 MachineInstr *UseMI = &*UI;
388 SlotIndex UseIdx = li_->getInstructionIndex(UseMI);
389 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
390 if (ULR == IntA.end())
392 if (ULR->valno == AValNo && JoinedCopies.count(UseMI))
396 // At this point we have decided that it is legal to do this
397 // transformation. Start by commuting the instruction.
398 MachineBasicBlock *MBB = DefMI->getParent();
399 MachineInstr *NewMI = tii_->commuteInstruction(DefMI);
402 if (NewMI != DefMI) {
403 li_->ReplaceMachineInstrInMaps(DefMI, NewMI);
404 MBB->insert(DefMI, NewMI);
407 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
408 NewMI->getOperand(OpIdx).setIsKill();
410 bool BHasPHIKill = BValNo->hasPHIKill();
411 SmallVector<VNInfo*, 4> BDeadValNos;
412 std::map<SlotIndex, SlotIndex> BExtend;
414 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
422 bool Extended = BLR->end > ALR->end && ALR->end != ALR->start;
424 BExtend[ALR->end] = BLR->end;
426 // Update uses of IntA of the specific Val# with IntB.
427 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
428 UE = mri_->use_end(); UI != UE;) {
429 MachineOperand &UseMO = UI.getOperand();
430 MachineInstr *UseMI = &*UI;
432 if (JoinedCopies.count(UseMI))
434 if (UseMI->isDebugValue()) {
435 // FIXME These don't have an instruction index. Not clear we have enough
436 // info to decide whether to do this replacement or not. For now do it.
437 UseMO.setReg(NewReg);
440 SlotIndex UseIdx = li_->getInstructionIndex(UseMI).getUseIndex();
441 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
442 if (ULR == IntA.end() || ULR->valno != AValNo)
444 UseMO.setReg(NewReg);
447 if (UseMO.isKill()) {
449 UseMO.setIsKill(false);
451 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
452 if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
454 if (DstReg == IntB.reg && DstSubIdx == 0) {
455 // This copy will become a noop. If it's defining a new val#,
456 // remove that val# as well. However this live range is being
457 // extended to the end of the existing live range defined by the copy.
458 SlotIndex DefIdx = UseIdx.getDefIndex();
459 const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
460 BHasPHIKill |= DLR->valno->hasPHIKill();
461 assert(DLR->valno->def == DefIdx);
462 BDeadValNos.push_back(DLR->valno);
463 BExtend[DLR->start] = DLR->end;
464 JoinedCopies.insert(UseMI);
468 // We need to insert a new liverange: [ALR.start, LastUse). It may be we can
469 // simply extend BLR if CopyMI doesn't end the range.
471 dbgs() << "Extending: ";
472 IntB.print(dbgs(), tri_);
475 // Remove val#'s defined by copies that will be coalesced away.
476 for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) {
477 VNInfo *DeadVNI = BDeadValNos[i];
479 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
480 LiveInterval &SRLI = li_->getInterval(*SR);
481 const LiveRange *SRLR = SRLI.getLiveRangeContaining(DeadVNI->def);
482 SRLI.removeValNo(SRLR->valno);
485 IntB.removeValNo(BDeadValNos[i]);
488 // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
490 VNInfo *ValNo = BValNo;
491 ValNo->def = AValNo->def;
493 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
495 if (AI->valno != AValNo) continue;
496 SlotIndex End = AI->end;
497 std::map<SlotIndex, SlotIndex>::iterator
498 EI = BExtend.find(End);
499 if (EI != BExtend.end())
501 IntB.addRange(LiveRange(AI->start, End, ValNo));
503 // If the IntB live range is assigned to a physical register, and if that
504 // physreg has sub-registers, update their live intervals as well.
506 for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
507 LiveInterval &SRLI = li_->getInterval(*SR);
508 SRLI.MergeInClobberRange(*li_, AI->start, End,
509 li_->getVNInfoAllocator());
513 ValNo->setHasPHIKill(BHasPHIKill);
516 dbgs() << " result = ";
517 IntB.print(dbgs(), tri_);
518 dbgs() << "\nShortening: ";
519 IntA.print(dbgs(), tri_);
522 IntA.removeValNo(AValNo);
525 dbgs() << " result = ";
526 IntA.print(dbgs(), tri_);
534 /// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
535 /// fallthoughs to SuccMBB.
536 static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
537 MachineBasicBlock *SuccMBB,
538 const TargetInstrInfo *tii_) {
541 MachineBasicBlock *TBB = 0, *FBB = 0;
542 SmallVector<MachineOperand, 4> Cond;
543 return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
544 MBB->isSuccessor(SuccMBB);
547 /// removeRange - Wrapper for LiveInterval::removeRange. This removes a range
548 /// from a physical register live interval as well as from the live intervals
549 /// of its sub-registers.
550 static void removeRange(LiveInterval &li,
551 SlotIndex Start, SlotIndex End,
552 LiveIntervals *li_, const TargetRegisterInfo *tri_) {
553 li.removeRange(Start, End, true);
554 if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
555 for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
556 if (!li_->hasInterval(*SR))
558 LiveInterval &sli = li_->getInterval(*SR);
559 SlotIndex RemoveStart = Start;
560 SlotIndex RemoveEnd = Start;
562 while (RemoveEnd != End) {
563 LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart);
566 RemoveEnd = (LR->end < End) ? LR->end : End;
567 sli.removeRange(RemoveStart, RemoveEnd, true);
568 RemoveStart = RemoveEnd;
574 /// TrimLiveIntervalToLastUse - If there is a last use in the same basic block
575 /// as the copy instruction, trim the live interval to the last use and return
578 SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(SlotIndex CopyIdx,
579 MachineBasicBlock *CopyMBB,
581 const LiveRange *LR) {
582 SlotIndex MBBStart = li_->getMBBStartIdx(CopyMBB);
583 SlotIndex LastUseIdx;
584 MachineOperand *LastUse =
585 lastRegisterUse(LR->start, CopyIdx.getPrevSlot(), li.reg, LastUseIdx);
587 MachineInstr *LastUseMI = LastUse->getParent();
588 if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
595 // r1025<dead> = r1024<kill>
596 if (MBBStart < LR->end)
597 removeRange(li, MBBStart, LR->end, li_, tri_);
601 // There are uses before the copy, just shorten the live range to the end
603 LastUse->setIsKill();
604 removeRange(li, LastUseIdx.getDefIndex(), LR->end, li_, tri_);
605 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
606 if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
607 DstReg == li.reg && DstSubIdx == 0) {
608 // Last use is itself an identity code.
609 int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg,
611 LastUseMI->getOperand(DeadIdx).setIsDead();
617 if (LR->start <= MBBStart && LR->end > MBBStart) {
618 if (LR->start == li_->getZeroIndex()) {
619 assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
620 // Live-in to the function but dead. Remove it from entry live-in set.
621 mf_->begin()->removeLiveIn(li.reg);
623 // FIXME: Shorten intervals in BBs that reaches this BB.
629 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
630 /// computation, replace the copy by rematerialize the definition.
631 bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
634 MachineInstr *CopyMI) {
635 SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getUseIndex();
636 LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
637 assert(SrcLR != SrcInt.end() && "Live range not found!");
638 VNInfo *ValNo = SrcLR->valno;
639 // If other defs can reach uses of this def, then it's not safe to perform
640 // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be
642 if (ValNo->isPHIDef() || !ValNo->isDefAccurate() ||
643 ValNo->isUnused() || ValNo->hasPHIKill())
645 MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def);
646 assert(DefMI && "Defining instruction disappeared");
647 const TargetInstrDesc &TID = DefMI->getDesc();
648 if (!TID.isAsCheapAsAMove())
650 if (!tii_->isTriviallyReMaterializable(DefMI, AA))
652 bool SawStore = false;
653 if (!DefMI->isSafeToMove(tii_, AA, SawStore))
655 if (TID.getNumDefs() != 1)
657 if (!DefMI->isImplicitDef()) {
658 // Make sure the copy destination register class fits the instruction
659 // definition register class. The mismatch can happen as a result of earlier
660 // extract_subreg, insert_subreg, subreg_to_reg coalescing.
661 const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_);
662 if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
663 if (mri_->getRegClass(DstReg) != RC)
665 } else if (!RC->contains(DstReg))
669 // If destination register has a sub-register index on it, make sure it mtches
670 // the instruction register class.
672 const TargetInstrDesc &TID = DefMI->getDesc();
673 if (TID.getNumDefs() != 1)
675 const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg);
676 const TargetRegisterClass *DstSubRC =
677 DstRC->getSubRegisterRegClass(DstSubIdx);
678 const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_);
681 else if (DefRC != DstSubRC)
685 RemoveCopyFlag(DstReg, CopyMI);
687 // If copy kills the source register, find the last use and propagate
689 bool checkForDeadDef = false;
690 MachineBasicBlock *MBB = CopyMI->getParent();
691 if (SrcLR->end == CopyIdx.getDefIndex())
692 if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) {
693 checkForDeadDef = true;
696 MachineBasicBlock::iterator MII =
697 llvm::next(MachineBasicBlock::iterator(CopyMI));
698 tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI, *tri_);
699 MachineInstr *NewMI = prior(MII);
701 if (checkForDeadDef) {
702 // PR4090 fix: Trim interval failed because there was no use of the
703 // source interval in this MBB. If the def is in this MBB too then we
704 // should mark it dead:
705 if (DefMI->getParent() == MBB) {
706 DefMI->addRegisterDead(SrcInt.reg, tri_);
707 SrcLR->end = SrcLR->start.getNextSlot();
711 // CopyMI may have implicit operands, transfer them over to the newly
712 // rematerialized instruction. And update implicit def interval valnos.
713 for (unsigned i = CopyMI->getDesc().getNumOperands(),
714 e = CopyMI->getNumOperands(); i != e; ++i) {
715 MachineOperand &MO = CopyMI->getOperand(i);
716 if (MO.isReg() && MO.isImplicit())
717 NewMI->addOperand(MO);
719 RemoveCopyFlag(MO.getReg(), CopyMI);
722 TransferImplicitOps(CopyMI, NewMI);
723 li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
724 CopyMI->eraseFromParent();
725 ReMatCopies.insert(CopyMI);
726 ReMatDefs.insert(DefMI);
727 DEBUG(dbgs() << "Remat: " << *NewMI);
732 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
733 /// update the subregister number if it is not zero. If DstReg is a
734 /// physical register and the existing subregister number of the def / use
735 /// being updated is not zero, make sure to set it to the correct physical
738 SimpleRegisterCoalescing::UpdateRegDefsUses(const CoalescerPair &CP) {
739 bool DstIsPhys = CP.isPhys();
740 unsigned SrcReg = CP.getSrcReg();
741 unsigned DstReg = CP.getDstReg();
742 unsigned SubIdx = CP.getSubIdx();
744 // Collect all the instructions using SrcReg.
745 SmallPtrSet<MachineInstr*, 32> Instrs;
746 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
747 E = mri_->reg_end(); I != E; ++I)
750 for (SmallPtrSet<MachineInstr*, 32>::const_iterator I = Instrs.begin(),
751 E = Instrs.end(); I != E; ++I) {
752 MachineInstr *UseMI = *I;
754 // A PhysReg copy that won't be coalesced can perhaps be rematerialized
757 unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
758 if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
759 CopySrcSubIdx, CopyDstSubIdx) &&
760 CopySrcSubIdx == 0 && CopyDstSubIdx == 0 &&
761 CopySrcReg != CopyDstReg && CopySrcReg == SrcReg &&
762 CopyDstReg != DstReg && !JoinedCopies.count(UseMI) &&
763 ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg, 0,
768 SmallVector<unsigned,8> Ops;
770 tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
771 bool Kills = false, Deads = false;
773 // Replace SrcReg with DstReg in all UseMI operands.
774 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
775 MachineOperand &MO = UseMI->getOperand(Ops[i]);
776 Kills |= MO.isKill();
777 Deads |= MO.isDead();
780 MO.substPhysReg(DstReg, *tri_);
782 MO.substVirtReg(DstReg, SubIdx, *tri_);
785 // This instruction is a copy that will be removed.
786 if (JoinedCopies.count(UseMI))
790 // If UseMI was a simple SrcReg def, make sure we didn't turn it into a
791 // read-modify-write of DstReg.
793 UseMI->addRegisterDead(DstReg, tri_);
794 else if (!Reads && Writes)
795 UseMI->addRegisterDefined(DstReg, tri_);
797 // Kill flags apply to the whole physical register.
798 if (DstIsPhys && Kills)
799 UseMI->addRegisterKilled(DstReg, tri_);
803 dbgs() << "\t\tupdated: ";
804 if (!UseMI->isDebugValue())
805 dbgs() << li_->getInstructionIndex(UseMI) << "\t";
810 // After updating the operand, check if the machine instruction has
811 // become a copy. If so, update its val# information.
812 const TargetInstrDesc &TID = UseMI->getDesc();
813 if (DstIsPhys || TID.getNumDefs() != 1 || TID.getNumOperands() <= 2)
816 unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
817 if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
818 CopySrcSubIdx, CopyDstSubIdx) &&
819 CopySrcReg != CopyDstReg &&
820 (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
821 allocatableRegs_[CopyDstReg])) {
822 LiveInterval &LI = li_->getInterval(CopyDstReg);
824 li_->getInstructionIndex(UseMI).getDefIndex();
825 if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) {
826 if (DLR->valno->def == DefIdx)
827 DLR->valno->setCopy(UseMI);
833 /// removeIntervalIfEmpty - Check if the live interval of a physical register
834 /// is empty, if so remove it and also remove the empty intervals of its
835 /// sub-registers. Return true if live interval is removed.
836 static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
837 const TargetRegisterInfo *tri_) {
839 if (TargetRegisterInfo::isPhysicalRegister(li.reg))
840 for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
841 if (!li_->hasInterval(*SR))
843 LiveInterval &sli = li_->getInterval(*SR);
845 li_->removeInterval(*SR);
847 li_->removeInterval(li.reg);
853 /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
854 /// Return true if live interval is removed.
855 bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
856 MachineInstr *CopyMI) {
857 SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
858 LiveInterval::iterator MLR =
859 li.FindLiveRangeContaining(CopyIdx.getDefIndex());
861 return false; // Already removed by ShortenDeadCopySrcLiveRange.
862 SlotIndex RemoveStart = MLR->start;
863 SlotIndex RemoveEnd = MLR->end;
864 SlotIndex DefIdx = CopyIdx.getDefIndex();
865 // Remove the liverange that's defined by this.
866 if (RemoveStart == DefIdx && RemoveEnd == DefIdx.getStoreIndex()) {
867 removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
868 return removeIntervalIfEmpty(li, li_, tri_);
873 /// RemoveDeadDef - If a def of a live interval is now determined dead, remove
874 /// the val# it defines. If the live interval becomes empty, remove it as well.
875 bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
876 MachineInstr *DefMI) {
877 SlotIndex DefIdx = li_->getInstructionIndex(DefMI).getDefIndex();
878 LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
879 if (DefIdx != MLR->valno->def)
881 li.removeValNo(MLR->valno);
882 return removeIntervalIfEmpty(li, li_, tri_);
885 void SimpleRegisterCoalescing::RemoveCopyFlag(unsigned DstReg,
886 const MachineInstr *CopyMI) {
887 SlotIndex DefIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
888 if (li_->hasInterval(DstReg)) {
889 LiveInterval &LI = li_->getInterval(DstReg);
890 if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx))
891 if (LR->valno->getCopy() == CopyMI)
892 LR->valno->setCopy(0);
894 if (!TargetRegisterInfo::isPhysicalRegister(DstReg))
896 for (const unsigned* AS = tri_->getAliasSet(DstReg); *AS; ++AS) {
897 if (!li_->hasInterval(*AS))
899 LiveInterval &LI = li_->getInterval(*AS);
900 if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx))
901 if (LR->valno->getCopy() == CopyMI)
902 LR->valno->setCopy(0);
906 /// PropagateDeadness - Propagate the dead marker to the instruction which
907 /// defines the val#.
908 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
909 SlotIndex &LRStart, LiveIntervals *li_,
910 const TargetRegisterInfo* tri_) {
911 MachineInstr *DefMI =
912 li_->getInstructionFromIndex(LRStart.getDefIndex());
913 if (DefMI && DefMI != CopyMI) {
914 int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg);
916 DefMI->getOperand(DeadIdx).setIsDead();
918 DefMI->addOperand(MachineOperand::CreateReg(li.reg,
919 /*def*/true, /*implicit*/true, /*kill*/false, /*dead*/true));
920 LRStart = LRStart.getNextSlot();
924 /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
925 /// extended by a dead copy. Mark the last use (if any) of the val# as kill as
926 /// ends the live range there. If there isn't another use, then this live range
927 /// is dead. Return true if live interval is removed.
929 SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
930 MachineInstr *CopyMI) {
931 SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
932 if (CopyIdx == SlotIndex()) {
933 // FIXME: special case: function live in. It can be a general case if the
934 // first instruction index starts at > 0 value.
935 assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
936 // Live-in to the function but dead. Remove it from entry live-in set.
937 if (mf_->begin()->isLiveIn(li.reg))
938 mf_->begin()->removeLiveIn(li.reg);
939 const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
940 removeRange(li, LR->start, LR->end, li_, tri_);
941 return removeIntervalIfEmpty(li, li_, tri_);
944 LiveInterval::iterator LR =
945 li.FindLiveRangeContaining(CopyIdx.getPrevIndex().getStoreIndex());
947 // Livein but defined by a phi.
950 SlotIndex RemoveStart = LR->start;
951 SlotIndex RemoveEnd = CopyIdx.getStoreIndex();
952 if (LR->end > RemoveEnd)
953 // More uses past this copy? Nothing to do.
956 // If there is a last use in the same bb, we can't remove the live range.
957 // Shorten the live interval and return.
958 MachineBasicBlock *CopyMBB = CopyMI->getParent();
959 if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR))
962 // There are other kills of the val#. Nothing to do.
963 if (!li.isOnlyLROfValNo(LR))
966 MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart);
967 if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_))
968 // If the live range starts in another mbb and the copy mbb is not a fall
969 // through mbb, then we can only cut the range from the beginning of the
971 RemoveStart = li_->getMBBStartIdx(CopyMBB).getNextIndex().getBaseIndex();
973 if (LR->valno->def == RemoveStart) {
974 // If the def MI defines the val# and this copy is the only kill of the
975 // val#, then propagate the dead marker.
976 PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
980 removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
981 return removeIntervalIfEmpty(li, li_, tri_);
985 /// isWinToJoinCrossClass - Return true if it's profitable to coalesce
986 /// two virtual registers from different register classes.
988 SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned SrcReg,
990 const TargetRegisterClass *SrcRC,
991 const TargetRegisterClass *DstRC,
992 const TargetRegisterClass *NewRC) {
993 unsigned NewRCCount = allocatableRCRegs_[NewRC].count();
994 // This heuristics is good enough in practice, but it's obviously not *right*.
995 // 4 is a magic number that works well enough for x86, ARM, etc. It filter
996 // out all but the most restrictive register classes.
997 if (NewRCCount > 4 ||
998 // Early exit if the function is fairly small, coalesce aggressively if
999 // that's the case. For really special register classes with 3 or
1000 // fewer registers, be a bit more careful.
1001 (li_->getFuncInstructionCount() / NewRCCount) < 8)
1003 LiveInterval &SrcInt = li_->getInterval(SrcReg);
1004 LiveInterval &DstInt = li_->getInterval(DstReg);
1005 unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt);
1006 unsigned DstSize = li_->getApproximateInstructionCount(DstInt);
1007 if (SrcSize <= NewRCCount && DstSize <= NewRCCount)
1009 // Estimate *register use density*. If it doubles or more, abort.
1010 unsigned SrcUses = std::distance(mri_->use_nodbg_begin(SrcReg),
1011 mri_->use_nodbg_end());
1012 unsigned DstUses = std::distance(mri_->use_nodbg_begin(DstReg),
1013 mri_->use_nodbg_end());
1014 unsigned NewUses = SrcUses + DstUses;
1015 unsigned NewSize = SrcSize + DstSize;
1016 if (SrcRC != NewRC && SrcSize > NewRCCount) {
1017 unsigned SrcRCCount = allocatableRCRegs_[SrcRC].count();
1018 if (NewUses*SrcSize*SrcRCCount > 2*SrcUses*NewSize*NewRCCount)
1021 if (DstRC != NewRC && DstSize > NewRCCount) {
1022 unsigned DstRCCount = allocatableRCRegs_[DstRC].count();
1023 if (NewUses*DstSize*DstRCCount > 2*DstUses*NewSize*NewRCCount)
1030 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
1031 /// which are the src/dst of the copy instruction CopyMI. This returns true
1032 /// if the copy was successfully coalesced away. If it is not currently
1033 /// possible to coalesce this interval, but it may be possible if other
1034 /// things get coalesced, then it returns true by reference in 'Again'.
1035 bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
1036 MachineInstr *CopyMI = TheCopy.MI;
1039 if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI))
1040 return false; // Already done.
1042 DEBUG(dbgs() << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI);
1044 CoalescerPair CP(*tii_, *tri_);
1045 if (!CP.setRegisters(CopyMI)) {
1046 DEBUG(dbgs() << "\tNot coalescable.\n");
1050 // If they are already joined we continue.
1051 if (CP.getSrcReg() == CP.getDstReg()) {
1052 DEBUG(dbgs() << "\tCopy already coalesced.\n");
1053 return false; // Not coalescable.
1056 DEBUG(dbgs() << "\tConsidering merging %reg" << CP.getSrcReg());
1058 // Enforce policies.
1060 DEBUG(dbgs() <<" with physreg %" << tri_->getName(CP.getDstReg()) << "\n");
1061 // Only coalesce to allocatable physreg.
1062 if (!allocatableRegs_[CP.getDstReg()]) {
1063 DEBUG(dbgs() << "\tRegister is an unallocatable physreg.\n");
1064 return false; // Not coalescable.
1068 dbgs() << " with reg%" << CP.getDstReg();
1070 dbgs() << ":" << tri_->getSubRegIndexName(CP.getSubIdx());
1071 dbgs() << " to " << CP.getNewRC()->getName() << "\n";
1074 // Avoid constraining virtual register regclass too much.
1075 if (CP.isCrossClass()) {
1076 if (DisableCrossClassJoin) {
1077 DEBUG(dbgs() << "\tCross-class joins disabled.\n");
1080 if (!isWinToJoinCrossClass(CP.getSrcReg(), CP.getDstReg(),
1081 mri_->getRegClass(CP.getSrcReg()),
1082 mri_->getRegClass(CP.getDstReg()),
1084 DEBUG(dbgs() << "\tAvoid coalescing to constrained register class: "
1085 << CP.getNewRC()->getName() << ".\n");
1086 Again = true; // May be possible to coalesce later.
1091 // When possible, let DstReg be the larger interval.
1092 if (!CP.getSubIdx() && li_->getInterval(CP.getSrcReg()).ranges.size() >
1093 li_->getInterval(CP.getDstReg()).ranges.size())
1097 // We need to be careful about coalescing a source physical register with a
1098 // virtual register. Once the coalescing is done, it cannot be broken and
1099 // these are not spillable! If the destination interval uses are far away,
1100 // think twice about coalescing them!
1101 // FIXME: Why are we skipping this test for partial copies?
1102 // CodeGen/X86/phys_subreg_coalesce-3.ll needs it.
1103 if (!CP.isPartial() && CP.isPhys()) {
1104 LiveInterval &JoinVInt = li_->getInterval(CP.getSrcReg());
1106 // Don't join with physregs that have a ridiculous number of live
1107 // ranges. The data structure performance is really bad when that
1109 if (li_->hasInterval(CP.getDstReg()) &&
1110 li_->getInterval(CP.getDstReg()).ranges.size() > 1000) {
1111 mri_->setRegAllocationHint(CP.getSrcReg(), 0, CP.getDstReg());
1114 << "\tPhysical register live interval too complicated, abort!\n");
1118 const TargetRegisterClass *RC = mri_->getRegClass(CP.getSrcReg());
1119 unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
1120 unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
1121 if (Length > Threshold &&
1122 std::distance(mri_->use_nodbg_begin(CP.getSrcReg()),
1123 mri_->use_nodbg_end()) * Threshold < Length) {
1124 // Before giving up coalescing, if definition of source is defined by
1125 // trivial computation, try rematerializing it.
1126 if (!CP.isFlipped() &&
1127 ReMaterializeTrivialDef(JoinVInt, CP.getDstReg(), 0, CopyMI))
1130 mri_->setRegAllocationHint(CP.getSrcReg(), 0, CP.getDstReg());
1132 DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
1133 Again = true; // May be possible to coalesce later.
1138 // We may need the source interval after JoinIntervals has destroyed it.
1139 OwningPtr<LiveInterval> SavedLI;
1140 if (CP.getOrigDstReg() != CP.getDstReg())
1141 SavedLI.reset(li_->dupInterval(&li_->getInterval(CP.getSrcReg())));
1143 // Okay, attempt to join these two intervals. On failure, this returns false.
1144 // Otherwise, if one of the intervals being joined is a physreg, this method
1145 // always canonicalizes DstInt to be it. The output "SrcInt" will not have
1146 // been modified, so we can use this information below to update aliases.
1147 if (!JoinIntervals(CP)) {
1148 // Coalescing failed.
1150 // If definition of source is defined by trivial computation, try
1151 // rematerializing it.
1152 if (!CP.isFlipped() &&
1153 ReMaterializeTrivialDef(li_->getInterval(CP.getSrcReg()),
1154 CP.getDstReg(), 0, CopyMI))
1157 // If we can eliminate the copy without merging the live ranges, do so now.
1158 if (!CP.isPartial()) {
1159 LiveInterval *UseInt = &li_->getInterval(CP.getSrcReg());
1160 LiveInterval *DefInt = &li_->getInterval(CP.getDstReg());
1162 std::swap(UseInt, DefInt);
1163 if (AdjustCopiesBackFrom(CP, CopyMI) ||
1164 RemoveCopyByCommutingDef(*UseInt, *DefInt, CopyMI)) {
1165 JoinedCopies.insert(CopyMI);
1166 DEBUG(dbgs() << "\tTrivial!\n");
1171 // Otherwise, we are unable to join the intervals.
1172 DEBUG(dbgs() << "\tInterference!\n");
1173 Again = true; // May be possible to coalesce later.
1178 // If this is a extract_subreg where dst is a physical register, e.g.
1179 // cl = EXTRACT_SUBREG reg1024, 1
1180 // then create and update the actual physical register allocated to RHS.
1181 unsigned LargerDstReg = CP.getDstReg();
1182 if (CP.getOrigDstReg() != CP.getDstReg()) {
1183 if (tri_->isSubRegister(CP.getOrigDstReg(), LargerDstReg))
1184 LargerDstReg = CP.getOrigDstReg();
1185 LiveInterval &RealInt = li_->getOrCreateInterval(CP.getDstReg());
1186 for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(),
1187 E = SavedLI->vni_end(); I != E; ++I) {
1188 const VNInfo *ValNo = *I;
1189 VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(),
1190 false, // updated at *
1191 li_->getVNInfoAllocator());
1192 NewValNo->setFlags(ValNo->getFlags()); // * updated here.
1193 RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo);
1195 RealInt.weight += SavedLI->weight;
1198 // Update the liveintervals of sub-registers.
1199 LiveInterval &LargerInt = li_->getInterval(LargerDstReg);
1200 for (const unsigned *AS = tri_->getSubRegisters(LargerDstReg); *AS; ++AS) {
1201 LiveInterval &SRI = li_->getOrCreateInterval(*AS);
1202 SRI.MergeInClobberRanges(*li_, LargerInt, li_->getVNInfoAllocator());
1204 dbgs() << "\t\tsubreg: "; SRI.print(dbgs(), tri_); dbgs() << "\n";
1209 // Coalescing to a virtual register that is of a sub-register class of the
1210 // other. Make sure the resulting register is set to the right register class.
1211 if (CP.isCrossClass()) {
1213 mri_->setRegClass(CP.getDstReg(), CP.getNewRC());
1216 // Remember to delete the copy instruction.
1217 JoinedCopies.insert(CopyMI);
1219 UpdateRegDefsUses(CP);
1221 // If we have extended the live range of a physical register, make sure we
1222 // update live-in lists as well.
1224 SmallVector<MachineBasicBlock*, 16> BlockSeq;
1225 // JoinIntervals invalidates the VNInfos in SrcInt, but we only need the
1226 // ranges for this, and they are preserved.
1227 LiveInterval &SrcInt = li_->getInterval(CP.getSrcReg());
1228 for (LiveInterval::const_iterator I = SrcInt.begin(), E = SrcInt.end();
1230 li_->findLiveInMBBs(I->start, I->end, BlockSeq);
1231 for (unsigned idx = 0, size = BlockSeq.size(); idx != size; ++idx) {
1232 MachineBasicBlock &block = *BlockSeq[idx];
1233 if (!block.isLiveIn(CP.getDstReg()))
1234 block.addLiveIn(CP.getDstReg());
1240 // SrcReg is guarateed to be the register whose live interval that is
1242 li_->removeInterval(CP.getSrcReg());
1244 // Update regalloc hint.
1245 tri_->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *mf_);
1248 LiveInterval &DstInt = li_->getInterval(CP.getDstReg());
1249 dbgs() << "\tJoined. Result = ";
1250 DstInt.print(dbgs(), tri_);
1258 /// ComputeUltimateVN - Assuming we are going to join two live intervals,
1259 /// compute what the resultant value numbers for each value in the input two
1260 /// ranges will be. This is complicated by copies between the two which can
1261 /// and will commonly cause multiple value numbers to be merged into one.
1263 /// VN is the value number that we're trying to resolve. InstDefiningValue
1264 /// keeps track of the new InstDefiningValue assignment for the result
1265 /// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of
1266 /// whether a value in this or other is a copy from the opposite set.
1267 /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
1268 /// already been assigned.
1270 /// ThisFromOther[x] - If x is defined as a copy from the other interval, this
1271 /// contains the value number the copy is from.
1273 static unsigned ComputeUltimateVN(VNInfo *VNI,
1274 SmallVector<VNInfo*, 16> &NewVNInfo,
1275 DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
1276 DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
1277 SmallVector<int, 16> &ThisValNoAssignments,
1278 SmallVector<int, 16> &OtherValNoAssignments) {
1279 unsigned VN = VNI->id;
1281 // If the VN has already been computed, just return it.
1282 if (ThisValNoAssignments[VN] >= 0)
1283 return ThisValNoAssignments[VN];
1284 assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers");
1286 // If this val is not a copy from the other val, then it must be a new value
1287 // number in the destination.
1288 DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
1289 if (I == ThisFromOther.end()) {
1290 NewVNInfo.push_back(VNI);
1291 return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
1293 VNInfo *OtherValNo = I->second;
1295 // Otherwise, this *is* a copy from the RHS. If the other side has already
1296 // been computed, return it.
1297 if (OtherValNoAssignments[OtherValNo->id] >= 0)
1298 return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
1300 // Mark this value number as currently being computed, then ask what the
1301 // ultimate value # of the other value is.
1302 ThisValNoAssignments[VN] = -2;
1303 unsigned UltimateVN =
1304 ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
1305 OtherValNoAssignments, ThisValNoAssignments);
1306 return ThisValNoAssignments[VN] = UltimateVN;
1309 /// JoinIntervals - Attempt to join these two intervals. On failure, this
1311 bool SimpleRegisterCoalescing::JoinIntervals(CoalescerPair &CP) {
1312 LiveInterval &RHS = li_->getInterval(CP.getSrcReg());
1313 DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), tri_); dbgs() << "\n"; });
1315 // FIXME: Join into CP.getDstReg instead of CP.getOrigDstReg.
1317 // %reg2000 = EXTRACT_SUBREG %EAX, sub_16bit
1318 // we really want to join %reg2000 with %AX ( = CP.getDstReg). We are actually
1319 // joining into %EAX ( = CP.getOrigDstReg) because it is guaranteed to have an
1320 // existing live interval, and we are better equipped to handle interference.
1321 // JoinCopy cleans up the mess by taking a copy of RHS before calling here,
1322 // and merging that copy into CP.getDstReg after.
1324 // If a live interval is a physical register, conservatively check if any
1325 // of its sub-registers is overlapping the live interval of the virtual
1326 // register. If so, do not coalesce.
1327 if (CP.isPhys() && *tri_->getSubRegisters(CP.getOrigDstReg())) {
1328 // If it's coalescing a virtual register to a physical register, estimate
1329 // its live interval length. This is the *cost* of scanning an entire live
1330 // interval. If the cost is low, we'll do an exhaustive check instead.
1332 // If this is something like this:
1340 // That is, the live interval of v1024 crosses a bb. Then we can't rely on
1341 // less conservative check. It's possible a sub-register is defined before
1342 // v1024 (or live in) and live out of BB1.
1343 if (RHS.containsOneValue() &&
1344 li_->intervalIsInOneMBB(RHS) &&
1345 li_->getApproximateInstructionCount(RHS) <= 10) {
1346 // Perform a more exhaustive check for some common cases.
1347 if (li_->conflictsWithAliasRef(RHS, CP.getOrigDstReg(), JoinedCopies))
1350 for (const unsigned* SR = tri_->getAliasSet(CP.getOrigDstReg()); *SR;
1352 if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
1354 dbgs() << "\tInterfere with sub-register ";
1355 li_->getInterval(*SR).print(dbgs(), tri_);
1362 // Compute the final value assignment, assuming that the live ranges can be
1364 SmallVector<int, 16> LHSValNoAssignments;
1365 SmallVector<int, 16> RHSValNoAssignments;
1366 DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
1367 DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
1368 SmallVector<VNInfo*, 16> NewVNInfo;
1370 LiveInterval &LHS = li_->getInterval(CP.getOrigDstReg());
1371 DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), tri_); dbgs() << "\n"; });
1373 // Loop over the value numbers of the LHS, seeing if any are defined from
1375 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1378 if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy?
1381 // Never join with a register that has EarlyClobber redefs.
1382 if (VNI->hasRedefByEC())
1385 // DstReg is known to be a register in the LHS interval. If the src is
1386 // from the RHS interval, we can use its value #.
1387 if (!CP.isCoalescable(VNI->getCopy()))
1390 // Figure out the value # from the RHS.
1391 LiveRange *lr = RHS.getLiveRangeContaining(VNI->def.getPrevSlot());
1392 // The copy could be to an aliased physreg.
1394 LHSValsDefinedFromRHS[VNI] = lr->valno;
1397 // Loop over the value numbers of the RHS, seeing if any are defined from
1399 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1402 if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy?
1405 // Never join with a register that has EarlyClobber redefs.
1406 if (VNI->hasRedefByEC())
1409 // DstReg is known to be a register in the RHS interval. If the src is
1410 // from the LHS interval, we can use its value #.
1411 if (!CP.isCoalescable(VNI->getCopy()))
1414 // Figure out the value # from the LHS.
1415 LiveRange *lr = LHS.getLiveRangeContaining(VNI->def.getPrevSlot());
1416 // The copy could be to an aliased physreg.
1418 RHSValsDefinedFromLHS[VNI] = lr->valno;
1421 LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
1422 RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
1423 NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
1425 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
1428 unsigned VN = VNI->id;
1429 if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused())
1431 ComputeUltimateVN(VNI, NewVNInfo,
1432 LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
1433 LHSValNoAssignments, RHSValNoAssignments);
1435 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
1438 unsigned VN = VNI->id;
1439 if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused())
1441 // If this value number isn't a copy from the LHS, it's a new number.
1442 if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
1443 NewVNInfo.push_back(VNI);
1444 RHSValNoAssignments[VN] = NewVNInfo.size()-1;
1448 ComputeUltimateVN(VNI, NewVNInfo,
1449 RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
1450 RHSValNoAssignments, LHSValNoAssignments);
1453 // Armed with the mappings of LHS/RHS values to ultimate values, walk the
1454 // interval lists to see if these intervals are coalescable.
1455 LiveInterval::const_iterator I = LHS.begin();
1456 LiveInterval::const_iterator IE = LHS.end();
1457 LiveInterval::const_iterator J = RHS.begin();
1458 LiveInterval::const_iterator JE = RHS.end();
1460 // Skip ahead until the first place of potential sharing.
1461 if (I != IE && J != JE) {
1462 if (I->start < J->start) {
1463 I = std::upper_bound(I, IE, J->start);
1464 if (I != LHS.begin()) --I;
1465 } else if (J->start < I->start) {
1466 J = std::upper_bound(J, JE, I->start);
1467 if (J != RHS.begin()) --J;
1471 while (I != IE && J != JE) {
1472 // Determine if these two live ranges overlap.
1474 if (I->start < J->start) {
1475 Overlaps = I->end > J->start;
1477 Overlaps = J->end > I->start;
1480 // If so, check value # info to determine if they are really different.
1482 // If the live range overlap will map to the same value number in the
1483 // result liverange, we can still coalesce them. If not, we can't.
1484 if (LHSValNoAssignments[I->valno->id] !=
1485 RHSValNoAssignments[J->valno->id])
1487 // If it's re-defined by an early clobber somewhere in the live range,
1488 // then conservatively abort coalescing.
1489 if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC())
1493 if (I->end < J->end)
1499 // Update kill info. Some live ranges are extended due to copy coalescing.
1500 for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(),
1501 E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
1502 VNInfo *VNI = I->first;
1503 unsigned LHSValID = LHSValNoAssignments[VNI->id];
1504 if (VNI->hasPHIKill())
1505 NewVNInfo[LHSValID]->setHasPHIKill(true);
1508 // Update kill info. Some live ranges are extended due to copy coalescing.
1509 for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(),
1510 E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
1511 VNInfo *VNI = I->first;
1512 unsigned RHSValID = RHSValNoAssignments[VNI->id];
1513 if (VNI->hasPHIKill())
1514 NewVNInfo[RHSValID]->setHasPHIKill(true);
1517 if (LHSValNoAssignments.empty())
1518 LHSValNoAssignments.push_back(-1);
1519 if (RHSValNoAssignments.empty())
1520 RHSValNoAssignments.push_back(-1);
1522 // If we get here, we know that we can coalesce the live ranges. Ask the
1523 // intervals to coalesce themselves now.
1524 LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo,
1530 // DepthMBBCompare - Comparison predicate that sort first based on the loop
1531 // depth of the basic block (the unsigned), and then on the MBB number.
1532 struct DepthMBBCompare {
1533 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
1534 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
1535 // Deeper loops first
1536 if (LHS.first != RHS.first)
1537 return LHS.first > RHS.first;
1539 // Prefer blocks that are more connected in the CFG. This takes care of
1540 // the most difficult copies first while intervals are short.
1541 unsigned cl = LHS.second->pred_size() + LHS.second->succ_size();
1542 unsigned cr = RHS.second->pred_size() + RHS.second->succ_size();
1546 // As a last resort, sort by block number.
1547 return LHS.second->getNumber() < RHS.second->getNumber();
1552 void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
1553 std::vector<CopyRec> &TryAgain) {
1554 DEBUG(dbgs() << MBB->getName() << ":\n");
1556 std::vector<CopyRec> VirtCopies;
1557 std::vector<CopyRec> PhysCopies;
1558 std::vector<CopyRec> ImpDefCopies;
1559 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
1561 MachineInstr *Inst = MII++;
1563 // If this isn't a copy nor a extract_subreg, we can't join intervals.
1564 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1565 bool isInsUndef = false;
1566 if (Inst->isExtractSubreg()) {
1567 DstReg = Inst->getOperand(0).getReg();
1568 SrcReg = Inst->getOperand(1).getReg();
1569 } else if (Inst->isInsertSubreg()) {
1570 DstReg = Inst->getOperand(0).getReg();
1571 SrcReg = Inst->getOperand(2).getReg();
1572 if (Inst->getOperand(1).isUndef())
1574 } else if (Inst->isInsertSubreg() || Inst->isSubregToReg()) {
1575 DstReg = Inst->getOperand(0).getReg();
1576 SrcReg = Inst->getOperand(2).getReg();
1577 } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1580 bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
1581 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1583 (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()))
1584 ImpDefCopies.push_back(CopyRec(Inst, 0));
1585 else if (SrcIsPhys || DstIsPhys)
1586 PhysCopies.push_back(CopyRec(Inst, 0));
1588 VirtCopies.push_back(CopyRec(Inst, 0));
1591 // Try coalescing implicit copies and insert_subreg <undef> first,
1592 // followed by copies to / from physical registers, then finally copies
1593 // from virtual registers to virtual registers.
1594 for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) {
1595 CopyRec &TheCopy = ImpDefCopies[i];
1597 if (!JoinCopy(TheCopy, Again))
1599 TryAgain.push_back(TheCopy);
1601 for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) {
1602 CopyRec &TheCopy = PhysCopies[i];
1604 if (!JoinCopy(TheCopy, Again))
1606 TryAgain.push_back(TheCopy);
1608 for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) {
1609 CopyRec &TheCopy = VirtCopies[i];
1611 if (!JoinCopy(TheCopy, Again))
1613 TryAgain.push_back(TheCopy);
1617 void SimpleRegisterCoalescing::joinIntervals() {
1618 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
1620 std::vector<CopyRec> TryAgainList;
1621 if (loopInfo->empty()) {
1622 // If there are no loops in the function, join intervals in function order.
1623 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
1625 CopyCoalesceInMBB(I, TryAgainList);
1627 // Otherwise, join intervals in inner loops before other intervals.
1628 // Unfortunately we can't just iterate over loop hierarchy here because
1629 // there may be more MBB's than BB's. Collect MBB's for sorting.
1631 // Join intervals in the function prolog first. We want to join physical
1632 // registers with virtual registers before the intervals got too long.
1633 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
1634 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){
1635 MachineBasicBlock *MBB = I;
1636 MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I));
1639 // Sort by loop depth.
1640 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
1642 // Finally, join intervals in loop nest order.
1643 for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
1644 CopyCoalesceInMBB(MBBs[i].second, TryAgainList);
1647 // Joining intervals can allow other intervals to be joined. Iteratively join
1648 // until we make no progress.
1649 bool ProgressMade = true;
1650 while (ProgressMade) {
1651 ProgressMade = false;
1653 for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
1654 CopyRec &TheCopy = TryAgainList[i];
1659 bool Success = JoinCopy(TheCopy, Again);
1660 if (Success || !Again) {
1661 TheCopy.MI = 0; // Mark this one as done.
1662 ProgressMade = true;
1668 /// Return true if the two specified registers belong to different register
1669 /// classes. The registers may be either phys or virt regs.
1671 SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
1672 unsigned RegB) const {
1673 // Get the register classes for the first reg.
1674 if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
1675 assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1676 "Shouldn't consider two physregs!");
1677 return !mri_->getRegClass(RegB)->contains(RegA);
1680 // Compare against the regclass for the second reg.
1681 const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA);
1682 if (TargetRegisterInfo::isVirtualRegister(RegB)) {
1683 const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB);
1684 return RegClassA != RegClassB;
1686 return !RegClassA->contains(RegB);
1689 /// lastRegisterUse - Returns the last (non-debug) use of the specific register
1690 /// between cycles Start and End or NULL if there are no uses.
1692 SimpleRegisterCoalescing::lastRegisterUse(SlotIndex Start,
1695 SlotIndex &UseIdx) const{
1696 UseIdx = SlotIndex();
1697 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1698 MachineOperand *LastUse = NULL;
1699 for (MachineRegisterInfo::use_nodbg_iterator I = mri_->use_nodbg_begin(Reg),
1700 E = mri_->use_nodbg_end(); I != E; ++I) {
1701 MachineOperand &Use = I.getOperand();
1702 MachineInstr *UseMI = Use.getParent();
1703 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1704 if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
1705 SrcReg == DstReg && SrcSubIdx == DstSubIdx)
1706 // Ignore identity copies.
1708 SlotIndex Idx = li_->getInstructionIndex(UseMI);
1709 // FIXME: Should this be Idx != UseIdx? SlotIndex() will return something
1710 // that compares higher than any other interval.
1711 if (Idx >= Start && Idx < End && Idx >= UseIdx) {
1713 UseIdx = Idx.getUseIndex();
1719 SlotIndex s = Start;
1720 SlotIndex e = End.getPrevSlot().getBaseIndex();
1722 // Skip deleted instructions
1723 MachineInstr *MI = li_->getInstructionFromIndex(e);
1724 while (e != SlotIndex() && e.getPrevIndex() >= s && !MI) {
1725 e = e.getPrevIndex();
1726 MI = li_->getInstructionFromIndex(e);
1728 if (e < s || MI == NULL)
1731 // Ignore identity copies.
1732 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1733 if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
1734 SrcReg == DstReg && SrcSubIdx == DstSubIdx))
1735 for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
1736 MachineOperand &Use = MI->getOperand(i);
1737 if (Use.isReg() && Use.isUse() && Use.getReg() &&
1738 tri_->regsOverlap(Use.getReg(), Reg)) {
1739 UseIdx = e.getUseIndex();
1744 e = e.getPrevIndex();
1750 void SimpleRegisterCoalescing::releaseMemory() {
1751 JoinedCopies.clear();
1752 ReMatCopies.clear();
1756 bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
1758 mri_ = &fn.getRegInfo();
1759 tm_ = &fn.getTarget();
1760 tri_ = tm_->getRegisterInfo();
1761 tii_ = tm_->getInstrInfo();
1762 li_ = &getAnalysis<LiveIntervals>();
1763 AA = &getAnalysis<AliasAnalysis>();
1764 loopInfo = &getAnalysis<MachineLoopInfo>();
1766 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
1767 << "********** Function: "
1768 << ((Value*)mf_->getFunction())->getName() << '\n');
1770 allocatableRegs_ = tri_->getAllocatableSet(fn);
1771 for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(),
1772 E = tri_->regclass_end(); I != E; ++I)
1773 allocatableRCRegs_.insert(std::make_pair(*I,
1774 tri_->getAllocatableSet(fn, *I)));
1776 // Join (coalesce) intervals if requested.
1777 if (EnableJoining) {
1780 dbgs() << "********** INTERVALS POST JOINING **********\n";
1781 for (LiveIntervals::iterator I = li_->begin(), E = li_->end();
1783 I->second->print(dbgs(), tri_);
1789 // Perform a final pass over the instructions and compute spill weights
1790 // and remove identity moves.
1791 SmallVector<unsigned, 4> DeadDefs;
1792 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
1793 mbbi != mbbe; ++mbbi) {
1794 MachineBasicBlock* mbb = mbbi;
1795 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
1797 MachineInstr *MI = mii;
1798 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1799 if (JoinedCopies.count(MI)) {
1800 // Delete all coalesced copies.
1801 bool DoDelete = true;
1802 if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
1803 assert((MI->isExtractSubreg() || MI->isInsertSubreg() ||
1804 MI->isSubregToReg()) && "Unrecognized copy instruction");
1805 SrcReg = MI->getOperand(MI->isSubregToReg() ? 2 : 1).getReg();
1806 if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
1807 // Do not delete extract_subreg, insert_subreg of physical
1808 // registers unless the definition is dead. e.g.
1809 // %DO<def> = INSERT_SUBREG %D0<undef>, %S0<kill>, 1
1810 // or else the scavenger may complain. LowerSubregs will
1811 // delete them later.
1814 if (MI->allDefsAreDead()) {
1815 LiveInterval &li = li_->getInterval(SrcReg);
1816 if (!ShortenDeadCopySrcLiveRange(li, MI))
1817 ShortenDeadCopyLiveRange(li, MI);
1821 mii = llvm::next(mii);
1823 li_->RemoveMachineInstrFromMaps(MI);
1824 mii = mbbi->erase(mii);
1830 // Now check if this is a remat'ed def instruction which is now dead.
1831 if (ReMatDefs.count(MI)) {
1833 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1834 const MachineOperand &MO = MI->getOperand(i);
1837 unsigned Reg = MO.getReg();
1840 if (TargetRegisterInfo::isVirtualRegister(Reg))
1841 DeadDefs.push_back(Reg);
1844 if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
1845 !mri_->use_nodbg_empty(Reg)) {
1851 while (!DeadDefs.empty()) {
1852 unsigned DeadDef = DeadDefs.back();
1853 DeadDefs.pop_back();
1854 RemoveDeadDef(li_->getInterval(DeadDef), MI);
1856 li_->RemoveMachineInstrFromMaps(mii);
1857 mii = mbbi->erase(mii);
1863 // If the move will be an identity move delete it
1864 bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
1865 if (isMove && SrcReg == DstReg && SrcSubIdx == DstSubIdx) {
1866 if (li_->hasInterval(SrcReg)) {
1867 LiveInterval &RegInt = li_->getInterval(SrcReg);
1868 // If def of this move instruction is dead, remove its live range
1869 // from the destination register's live interval.
1870 if (MI->allDefsAreDead()) {
1871 if (!ShortenDeadCopySrcLiveRange(RegInt, MI))
1872 ShortenDeadCopyLiveRange(RegInt, MI);
1875 li_->RemoveMachineInstrFromMaps(MI);
1876 mii = mbbi->erase(mii);
1883 // Check for now unnecessary kill flags.
1884 if (li_->isNotInMIMap(MI)) continue;
1885 SlotIndex DefIdx = li_->getInstructionIndex(MI).getDefIndex();
1886 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1887 MachineOperand &MO = MI->getOperand(i);
1888 if (!MO.isReg() || !MO.isKill()) continue;
1889 unsigned reg = MO.getReg();
1890 if (!reg || !li_->hasInterval(reg)) continue;
1891 if (!li_->getInterval(reg).killedAt(DefIdx))
1892 MO.setIsKill(false);
1901 /// print - Implement the dump method.
1902 void SimpleRegisterCoalescing::print(raw_ostream &O, const Module* m) const {
1906 RegisterCoalescer* llvm::createSimpleRegisterCoalescer() {
1907 return new SimpleRegisterCoalescing();
1910 // Make sure that anything that uses RegisterCoalescer pulls in this file...
1911 DEFINING_FILE_FOR(SimpleRegisterCoalescing)