1 //===-- llvm/CodeGen/Rewriter.cpp - Rewriter -----------------------------===//
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 #define DEBUG_TYPE "virtregrewriter"
11 #include "VirtRegRewriter.h"
12 #include "llvm/Support/Compiler.h"
13 #include "llvm/Support/ErrorHandling.h"
14 #include "llvm/Support/raw_ostream.h"
15 #include "llvm/Target/TargetLowering.h"
16 #include "llvm/ADT/DepthFirstIterator.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/STLExtras.h"
22 STATISTIC(NumDSE
, "Number of dead stores elided");
23 STATISTIC(NumDSS
, "Number of dead spill slots removed");
24 STATISTIC(NumCommutes
, "Number of instructions commuted");
25 STATISTIC(NumDRM
, "Number of re-materializable defs elided");
26 STATISTIC(NumStores
, "Number of stores added");
27 STATISTIC(NumPSpills
, "Number of physical register spills");
28 STATISTIC(NumOmitted
, "Number of reloads omited");
29 STATISTIC(NumAvoided
, "Number of reloads deemed unnecessary");
30 STATISTIC(NumCopified
, "Number of available reloads turned into copies");
31 STATISTIC(NumReMats
, "Number of re-materialization");
32 STATISTIC(NumLoads
, "Number of loads added");
33 STATISTIC(NumReused
, "Number of values reused");
34 STATISTIC(NumDCE
, "Number of copies elided");
35 STATISTIC(NumSUnfold
, "Number of stores unfolded");
36 STATISTIC(NumModRefUnfold
, "Number of modref unfolded");
39 enum RewriterName
{ local
, trivial
};
42 static cl::opt
<RewriterName
>
43 RewriterOpt("rewriter",
44 cl::desc("Rewriter to use: (default: local)"),
46 cl::values(clEnumVal(local
, "local rewriter"),
47 clEnumVal(trivial
, "trivial rewriter"),
52 ScheduleSpills("schedule-spills",
53 cl::desc("Schedule spill code"),
56 VirtRegRewriter::~VirtRegRewriter() {}
60 /// This class is intended for use with the new spilling framework only. It
61 /// rewrites vreg def/uses to use the assigned preg, but does not insert any
63 struct VISIBILITY_HIDDEN TrivialRewriter
: public VirtRegRewriter
{
65 bool runOnMachineFunction(MachineFunction
&MF
, VirtRegMap
&VRM
,
67 DOUT
<< "********** REWRITE MACHINE CODE **********\n";
68 DEBUG(errs() << "********** Function: "
69 << MF
.getFunction()->getName() << '\n');
70 DOUT
<< "**** Machine Instrs"
71 << "(NOTE! Does not include spills and reloads!) ****\n";
74 MachineRegisterInfo
*mri
= &MF
.getRegInfo();
78 for (LiveIntervals::iterator liItr
= LIs
->begin(), liEnd
= LIs
->end();
79 liItr
!= liEnd
; ++liItr
) {
81 if (TargetRegisterInfo::isVirtualRegister(liItr
->first
)) {
82 if (VRM
.hasPhys(liItr
->first
)) {
83 unsigned preg
= VRM
.getPhys(liItr
->first
);
84 mri
->replaceRegWith(liItr
->first
, preg
);
85 mri
->setPhysRegUsed(preg
);
90 if (!liItr
->second
->empty()) {
91 mri
->setPhysRegUsed(liItr
->first
);
97 DOUT
<< "**** Post Machine Instrs ****\n";
107 // ************************************************************************ //
111 /// AvailableSpills - As the local rewriter is scanning and rewriting an MBB
112 /// from top down, keep track of which spill slots or remat are available in
115 /// Note that not all physregs are created equal here. In particular, some
116 /// physregs are reloads that we are allowed to clobber or ignore at any time.
117 /// Other physregs are values that the register allocated program is using
118 /// that we cannot CHANGE, but we can read if we like. We keep track of this
119 /// on a per-stack-slot / remat id basis as the low bit in the value of the
120 /// SpillSlotsAvailable entries. The predicate 'canClobberPhysReg()' checks
121 /// this bit and addAvailable sets it if.
122 class VISIBILITY_HIDDEN AvailableSpills
{
123 const TargetRegisterInfo
*TRI
;
124 const TargetInstrInfo
*TII
;
126 // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled
127 // or remat'ed virtual register values that are still available, due to
128 // being loaded or stored to, but not invalidated yet.
129 std::map
<int, unsigned> SpillSlotsOrReMatsAvailable
;
131 // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable,
132 // indicating which stack slot values are currently held by a physreg. This
133 // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a
134 // physreg is modified.
135 std::multimap
<unsigned, int> PhysRegsAvailable
;
137 void disallowClobberPhysRegOnly(unsigned PhysReg
);
139 void ClobberPhysRegOnly(unsigned PhysReg
);
141 AvailableSpills(const TargetRegisterInfo
*tri
, const TargetInstrInfo
*tii
)
142 : TRI(tri
), TII(tii
) {
145 /// clear - Reset the state.
147 SpillSlotsOrReMatsAvailable
.clear();
148 PhysRegsAvailable
.clear();
151 const TargetRegisterInfo
*getRegInfo() const { return TRI
; }
153 /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is
154 /// available in a physical register, return that PhysReg, otherwise
156 unsigned getSpillSlotOrReMatPhysReg(int Slot
) const {
157 std::map
<int, unsigned>::const_iterator I
=
158 SpillSlotsOrReMatsAvailable
.find(Slot
);
159 if (I
!= SpillSlotsOrReMatsAvailable
.end()) {
160 return I
->second
>> 1; // Remove the CanClobber bit.
165 /// addAvailable - Mark that the specified stack slot / remat is available
166 /// in the specified physreg. If CanClobber is true, the physreg can be
167 /// modified at any time without changing the semantics of the program.
168 void addAvailable(int SlotOrReMat
, unsigned Reg
, bool CanClobber
= true) {
169 // If this stack slot is thought to be available in some other physreg,
170 // remove its record.
171 ModifyStackSlotOrReMat(SlotOrReMat
);
173 PhysRegsAvailable
.insert(std::make_pair(Reg
, SlotOrReMat
));
174 SpillSlotsOrReMatsAvailable
[SlotOrReMat
]= (Reg
<< 1) |
175 (unsigned)CanClobber
;
177 if (SlotOrReMat
> VirtRegMap::MAX_STACK_SLOT
)
178 DOUT
<< "Remembering RM#" << SlotOrReMat
-VirtRegMap::MAX_STACK_SLOT
-1;
180 DOUT
<< "Remembering SS#" << SlotOrReMat
;
181 DOUT
<< " in physreg " << TRI
->getName(Reg
) << "\n";
184 /// canClobberPhysRegForSS - Return true if the spiller is allowed to change
185 /// the value of the specified stackslot register if it desires. The
186 /// specified stack slot must be available in a physreg for this query to
188 bool canClobberPhysRegForSS(int SlotOrReMat
) const {
189 assert(SpillSlotsOrReMatsAvailable
.count(SlotOrReMat
) &&
190 "Value not available!");
191 return SpillSlotsOrReMatsAvailable
.find(SlotOrReMat
)->second
& 1;
194 /// canClobberPhysReg - Return true if the spiller is allowed to clobber the
195 /// physical register where values for some stack slot(s) might be
197 bool canClobberPhysReg(unsigned PhysReg
) const {
198 std::multimap
<unsigned, int>::const_iterator I
=
199 PhysRegsAvailable
.lower_bound(PhysReg
);
200 while (I
!= PhysRegsAvailable
.end() && I
->first
== PhysReg
) {
201 int SlotOrReMat
= I
->second
;
203 if (!canClobberPhysRegForSS(SlotOrReMat
))
209 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
210 /// stackslot register. The register is still available but is no longer
211 /// allowed to be modifed.
212 void disallowClobberPhysReg(unsigned PhysReg
);
214 /// ClobberPhysReg - This is called when the specified physreg changes
215 /// value. We use this to invalidate any info about stuff that lives in
216 /// it and any of its aliases.
217 void ClobberPhysReg(unsigned PhysReg
);
219 /// ModifyStackSlotOrReMat - This method is called when the value in a stack
220 /// slot changes. This removes information about which register the
221 /// previous value for this slot lives in (as the previous value is dead
223 void ModifyStackSlotOrReMat(int SlotOrReMat
);
225 /// AddAvailableRegsToLiveIn - Availability information is being kept coming
226 /// into the specified MBB. Add available physical registers as potential
227 /// live-in's. If they are reused in the MBB, they will be added to the
228 /// live-in set to make register scavenger and post-allocation scheduler.
229 void AddAvailableRegsToLiveIn(MachineBasicBlock
&MBB
, BitVector
&RegKills
,
230 std::vector
<MachineOperand
*> &KillOps
);
235 // ************************************************************************ //
237 // Given a location where a reload of a spilled register or a remat of
238 // a constant is to be inserted, attempt to find a safe location to
239 // insert the load at an earlier point in the basic-block, to hide
240 // latency of the load and to avoid address-generation interlock
242 static MachineBasicBlock::iterator
243 ComputeReloadLoc(MachineBasicBlock::iterator
const InsertLoc
,
244 MachineBasicBlock::iterator
const Begin
,
246 const TargetRegisterInfo
*TRI
,
249 const TargetInstrInfo
*TII
,
250 const MachineFunction
&MF
)
255 // Spill backscheduling is of primary interest to addresses, so
256 // don't do anything if the register isn't in the register class
257 // used for pointers.
259 const TargetLowering
*TL
= MF
.getTarget().getTargetLowering();
261 if (!TL
->isTypeLegal(TL
->getPointerTy()))
262 // Believe it or not, this is true on PIC16.
265 const TargetRegisterClass
*ptrRegClass
=
266 TL
->getRegClassFor(TL
->getPointerTy());
267 if (!ptrRegClass
->contains(PhysReg
))
270 // Scan upwards through the preceding instructions. If an instruction doesn't
271 // reference the stack slot or the register we're loading, we can
272 // backschedule the reload up past it.
273 MachineBasicBlock::iterator NewInsertLoc
= InsertLoc
;
274 while (NewInsertLoc
!= Begin
) {
275 MachineBasicBlock::iterator Prev
= prior(NewInsertLoc
);
276 for (unsigned i
= 0; i
< Prev
->getNumOperands(); ++i
) {
277 MachineOperand
&Op
= Prev
->getOperand(i
);
278 if (!DoReMat
&& Op
.isFI() && Op
.getIndex() == SSorRMId
)
281 if (Prev
->findRegisterUseOperandIdx(PhysReg
) != -1 ||
282 Prev
->findRegisterDefOperand(PhysReg
))
284 for (const unsigned *Alias
= TRI
->getAliasSet(PhysReg
); *Alias
; ++Alias
)
285 if (Prev
->findRegisterUseOperandIdx(*Alias
) != -1 ||
286 Prev
->findRegisterDefOperand(*Alias
))
292 // If we made it to the beginning of the block, turn around and move back
293 // down just past any existing reloads. They're likely to be reloads/remats
294 // for instructions earlier than what our current reload/remat is for, so
295 // they should be scheduled earlier.
296 if (NewInsertLoc
== Begin
) {
298 while (InsertLoc
!= NewInsertLoc
&&
299 (TII
->isLoadFromStackSlot(NewInsertLoc
, FrameIdx
) ||
300 TII
->isTriviallyReMaterializable(NewInsertLoc
)))
309 // ReusedOp - For each reused operand, we keep track of a bit of information,
310 // in case we need to rollback upon processing a new operand. See comments
313 // The MachineInstr operand that reused an available value.
316 // StackSlotOrReMat - The spill slot or remat id of the value being reused.
317 unsigned StackSlotOrReMat
;
319 // PhysRegReused - The physical register the value was available in.
320 unsigned PhysRegReused
;
322 // AssignedPhysReg - The physreg that was assigned for use by the reload.
323 unsigned AssignedPhysReg
;
325 // VirtReg - The virtual register itself.
328 ReusedOp(unsigned o
, unsigned ss
, unsigned prr
, unsigned apr
,
330 : Operand(o
), StackSlotOrReMat(ss
), PhysRegReused(prr
),
331 AssignedPhysReg(apr
), VirtReg(vreg
) {}
334 /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
335 /// is reused instead of reloaded.
336 class VISIBILITY_HIDDEN ReuseInfo
{
338 std::vector
<ReusedOp
> Reuses
;
339 BitVector PhysRegsClobbered
;
341 ReuseInfo(MachineInstr
&mi
, const TargetRegisterInfo
*tri
) : MI(mi
) {
342 PhysRegsClobbered
.resize(tri
->getNumRegs());
345 bool hasReuses() const {
346 return !Reuses
.empty();
349 /// addReuse - If we choose to reuse a virtual register that is already
350 /// available instead of reloading it, remember that we did so.
351 void addReuse(unsigned OpNo
, unsigned StackSlotOrReMat
,
352 unsigned PhysRegReused
, unsigned AssignedPhysReg
,
354 // If the reload is to the assigned register anyway, no undo will be
356 if (PhysRegReused
== AssignedPhysReg
) return;
358 // Otherwise, remember this.
359 Reuses
.push_back(ReusedOp(OpNo
, StackSlotOrReMat
, PhysRegReused
,
360 AssignedPhysReg
, VirtReg
));
363 void markClobbered(unsigned PhysReg
) {
364 PhysRegsClobbered
.set(PhysReg
);
367 bool isClobbered(unsigned PhysReg
) const {
368 return PhysRegsClobbered
.test(PhysReg
);
371 /// GetRegForReload - We are about to emit a reload into PhysReg. If there
372 /// is some other operand that is using the specified register, either pick
373 /// a new register to use, or evict the previous reload and use this reg.
374 unsigned GetRegForReload(const TargetRegisterClass
*RC
, unsigned PhysReg
,
375 MachineFunction
&MF
, MachineInstr
*MI
,
376 AvailableSpills
&Spills
,
377 std::vector
<MachineInstr
*> &MaybeDeadStores
,
378 SmallSet
<unsigned, 8> &Rejected
,
380 std::vector
<MachineOperand
*> &KillOps
,
383 /// GetRegForReload - Helper for the above GetRegForReload(). Add a
384 /// 'Rejected' set to remember which registers have been considered and
385 /// rejected for the reload. This avoids infinite looping in case like
388 /// t2 <- assigned r0 for use by the reload but ended up reuse r1
389 /// t3 <- assigned r1 for use by the reload but ended up reuse r0
391 /// sees r1 is taken by t2, tries t2's reload register r0
392 /// sees r0 is taken by t3, tries t3's reload register r1
393 /// sees r1 is taken by t2, tries t2's reload register r0 ...
394 unsigned GetRegForReload(unsigned VirtReg
, unsigned PhysReg
, MachineInstr
*MI
,
395 AvailableSpills
&Spills
,
396 std::vector
<MachineInstr
*> &MaybeDeadStores
,
398 std::vector
<MachineOperand
*> &KillOps
,
400 SmallSet
<unsigned, 8> Rejected
;
401 MachineFunction
&MF
= *MI
->getParent()->getParent();
402 const TargetRegisterClass
* RC
= MF
.getRegInfo().getRegClass(VirtReg
);
403 return GetRegForReload(RC
, PhysReg
, MF
, MI
, Spills
, MaybeDeadStores
,
404 Rejected
, RegKills
, KillOps
, VRM
);
410 // ****************** //
411 // Utility Functions //
412 // ****************** //
414 /// findSinglePredSuccessor - Return via reference a vector of machine basic
415 /// blocks each of which is a successor of the specified BB and has no other
417 static void findSinglePredSuccessor(MachineBasicBlock
*MBB
,
418 SmallVectorImpl
<MachineBasicBlock
*> &Succs
) {
419 for (MachineBasicBlock::succ_iterator SI
= MBB
->succ_begin(),
420 SE
= MBB
->succ_end(); SI
!= SE
; ++SI
) {
421 MachineBasicBlock
*SuccMBB
= *SI
;
422 if (SuccMBB
->pred_size() == 1)
423 Succs
.push_back(SuccMBB
);
427 /// InvalidateKill - Invalidate register kill information for a specific
428 /// register. This also unsets the kills marker on the last kill operand.
429 static void InvalidateKill(unsigned Reg
,
430 const TargetRegisterInfo
* TRI
,
432 std::vector
<MachineOperand
*> &KillOps
) {
434 KillOps
[Reg
]->setIsKill(false);
435 // KillOps[Reg] might be a def of a super-register.
436 unsigned KReg
= KillOps
[Reg
]->getReg();
437 KillOps
[KReg
] = NULL
;
438 RegKills
.reset(KReg
);
439 for (const unsigned *SR
= TRI
->getSubRegisters(KReg
); *SR
; ++SR
) {
441 KillOps
[*SR
]->setIsKill(false);
449 /// InvalidateKills - MI is going to be deleted. If any of its operands are
450 /// marked kill, then invalidate the information.
451 static void InvalidateKills(MachineInstr
&MI
,
452 const TargetRegisterInfo
* TRI
,
454 std::vector
<MachineOperand
*> &KillOps
,
455 SmallVector
<unsigned, 2> *KillRegs
= NULL
) {
456 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
457 MachineOperand
&MO
= MI
.getOperand(i
);
458 if (!MO
.isReg() || !MO
.isUse() || !MO
.isKill() || MO
.isUndef())
460 unsigned Reg
= MO
.getReg();
461 if (TargetRegisterInfo::isVirtualRegister(Reg
))
464 KillRegs
->push_back(Reg
);
465 assert(Reg
< KillOps
.size());
466 if (KillOps
[Reg
] == &MO
) {
469 for (const unsigned *SR
= TRI
->getSubRegisters(Reg
); *SR
; ++SR
) {
479 /// InvalidateRegDef - If the def operand of the specified def MI is now dead
480 /// (since it's spill instruction is removed), mark it isDead. Also checks if
481 /// the def MI has other definition operands that are not dead. Returns it by
483 static bool InvalidateRegDef(MachineBasicBlock::iterator I
,
484 MachineInstr
&NewDef
, unsigned Reg
,
486 // Due to remat, it's possible this reg isn't being reused. That is,
487 // the def of this reg (by prev MI) is now dead.
488 MachineInstr
*DefMI
= I
;
489 MachineOperand
*DefOp
= NULL
;
490 for (unsigned i
= 0, e
= DefMI
->getNumOperands(); i
!= e
; ++i
) {
491 MachineOperand
&MO
= DefMI
->getOperand(i
);
492 if (!MO
.isReg() || !MO
.isUse() || !MO
.isKill() || MO
.isUndef())
494 if (MO
.getReg() == Reg
)
496 else if (!MO
.isDead())
502 bool FoundUse
= false, Done
= false;
503 MachineBasicBlock::iterator E
= &NewDef
;
505 for (; !Done
&& I
!= E
; ++I
) {
506 MachineInstr
*NMI
= I
;
507 for (unsigned j
= 0, ee
= NMI
->getNumOperands(); j
!= ee
; ++j
) {
508 MachineOperand
&MO
= NMI
->getOperand(j
);
509 if (!MO
.isReg() || MO
.getReg() != Reg
)
513 Done
= true; // Stop after scanning all the operands of this MI.
524 /// UpdateKills - Track and update kill info. If a MI reads a register that is
525 /// marked kill, then it must be due to register reuse. Transfer the kill info
527 static void UpdateKills(MachineInstr
&MI
, const TargetRegisterInfo
* TRI
,
529 std::vector
<MachineOperand
*> &KillOps
) {
530 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
531 MachineOperand
&MO
= MI
.getOperand(i
);
532 if (!MO
.isReg() || !MO
.isUse() || MO
.isUndef())
534 unsigned Reg
= MO
.getReg();
538 if (RegKills
[Reg
] && KillOps
[Reg
]->getParent() != &MI
) {
539 // That can't be right. Register is killed but not re-defined and it's
540 // being reused. Let's fix that.
541 KillOps
[Reg
]->setIsKill(false);
542 // KillOps[Reg] might be a def of a super-register.
543 unsigned KReg
= KillOps
[Reg
]->getReg();
544 KillOps
[KReg
] = NULL
;
545 RegKills
.reset(KReg
);
547 // Must be a def of a super-register. Its other sub-regsters are no
548 // longer killed as well.
549 for (const unsigned *SR
= TRI
->getSubRegisters(KReg
); *SR
; ++SR
) {
554 if (!MI
.isRegTiedToDefOperand(i
))
555 // Unless it's a two-address operand, this is the new kill.
561 for (const unsigned *SR
= TRI
->getSubRegisters(Reg
); *SR
; ++SR
) {
568 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
569 const MachineOperand
&MO
= MI
.getOperand(i
);
570 if (!MO
.isReg() || !MO
.isDef())
572 unsigned Reg
= MO
.getReg();
575 // It also defines (or partially define) aliases.
576 for (const unsigned *SR
= TRI
->getSubRegisters(Reg
); *SR
; ++SR
) {
583 /// ReMaterialize - Re-materialize definition for Reg targetting DestReg.
585 static void ReMaterialize(MachineBasicBlock
&MBB
,
586 MachineBasicBlock::iterator
&MII
,
587 unsigned DestReg
, unsigned Reg
,
588 const TargetInstrInfo
*TII
,
589 const TargetRegisterInfo
*TRI
,
591 MachineInstr
*ReMatDefMI
= VRM
.getReMaterializedMI(Reg
);
593 const TargetInstrDesc
&TID
= ReMatDefMI
->getDesc();
594 assert(TID
.getNumDefs() == 1 &&
595 "Don't know how to remat instructions that define > 1 values!");
597 TII
->reMaterialize(MBB
, MII
, DestReg
,
598 ReMatDefMI
->getOperand(0).getSubReg(), ReMatDefMI
);
599 MachineInstr
*NewMI
= prior(MII
);
600 for (unsigned i
= 0, e
= NewMI
->getNumOperands(); i
!= e
; ++i
) {
601 MachineOperand
&MO
= NewMI
->getOperand(i
);
602 if (!MO
.isReg() || MO
.getReg() == 0)
604 unsigned VirtReg
= MO
.getReg();
605 if (TargetRegisterInfo::isPhysicalRegister(VirtReg
))
608 unsigned SubIdx
= MO
.getSubReg();
609 unsigned Phys
= VRM
.getPhys(VirtReg
);
611 unsigned RReg
= SubIdx
? TRI
->getSubReg(Phys
, SubIdx
) : Phys
;
618 /// findSuperReg - Find the SubReg's super-register of given register class
619 /// where its SubIdx sub-register is SubReg.
620 static unsigned findSuperReg(const TargetRegisterClass
*RC
, unsigned SubReg
,
621 unsigned SubIdx
, const TargetRegisterInfo
*TRI
) {
622 for (TargetRegisterClass::iterator I
= RC
->begin(), E
= RC
->end();
625 if (TRI
->getSubReg(Reg
, SubIdx
) == SubReg
)
631 // ******************************** //
632 // Available Spills Implementation //
633 // ******************************** //
635 /// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified
636 /// stackslot register. The register is still available but is no longer
637 /// allowed to be modifed.
638 void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg
) {
639 std::multimap
<unsigned, int>::iterator I
=
640 PhysRegsAvailable
.lower_bound(PhysReg
);
641 while (I
!= PhysRegsAvailable
.end() && I
->first
== PhysReg
) {
642 int SlotOrReMat
= I
->second
;
644 assert((SpillSlotsOrReMatsAvailable
[SlotOrReMat
] >> 1) == PhysReg
&&
645 "Bidirectional map mismatch!");
646 SpillSlotsOrReMatsAvailable
[SlotOrReMat
] &= ~1;
647 DOUT
<< "PhysReg " << TRI
->getName(PhysReg
)
648 << " copied, it is available for use but can no longer be modified\n";
652 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
653 /// stackslot register and its aliases. The register and its aliases may
654 /// still available but is no longer allowed to be modifed.
655 void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg
) {
656 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
); *AS
; ++AS
)
657 disallowClobberPhysRegOnly(*AS
);
658 disallowClobberPhysRegOnly(PhysReg
);
661 /// ClobberPhysRegOnly - This is called when the specified physreg changes
662 /// value. We use this to invalidate any info about stuff we thing lives in it.
663 void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg
) {
664 std::multimap
<unsigned, int>::iterator I
=
665 PhysRegsAvailable
.lower_bound(PhysReg
);
666 while (I
!= PhysRegsAvailable
.end() && I
->first
== PhysReg
) {
667 int SlotOrReMat
= I
->second
;
668 PhysRegsAvailable
.erase(I
++);
669 assert((SpillSlotsOrReMatsAvailable
[SlotOrReMat
] >> 1) == PhysReg
&&
670 "Bidirectional map mismatch!");
671 SpillSlotsOrReMatsAvailable
.erase(SlotOrReMat
);
672 DOUT
<< "PhysReg " << TRI
->getName(PhysReg
)
673 << " clobbered, invalidating ";
674 if (SlotOrReMat
> VirtRegMap::MAX_STACK_SLOT
)
675 DOUT
<< "RM#" << SlotOrReMat
-VirtRegMap::MAX_STACK_SLOT
-1 << "\n";
677 DOUT
<< "SS#" << SlotOrReMat
<< "\n";
681 /// ClobberPhysReg - This is called when the specified physreg changes
682 /// value. We use this to invalidate any info about stuff we thing lives in
683 /// it and any of its aliases.
684 void AvailableSpills::ClobberPhysReg(unsigned PhysReg
) {
685 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
); *AS
; ++AS
)
686 ClobberPhysRegOnly(*AS
);
687 ClobberPhysRegOnly(PhysReg
);
690 /// AddAvailableRegsToLiveIn - Availability information is being kept coming
691 /// into the specified MBB. Add available physical registers as potential
692 /// live-in's. If they are reused in the MBB, they will be added to the
693 /// live-in set to make register scavenger and post-allocation scheduler.
694 void AvailableSpills::AddAvailableRegsToLiveIn(MachineBasicBlock
&MBB
,
696 std::vector
<MachineOperand
*> &KillOps
) {
697 std::set
<unsigned> NotAvailable
;
698 for (std::multimap
<unsigned, int>::iterator
699 I
= PhysRegsAvailable
.begin(), E
= PhysRegsAvailable
.end();
701 unsigned Reg
= I
->first
;
702 const TargetRegisterClass
* RC
= TRI
->getPhysicalRegisterRegClass(Reg
);
703 // FIXME: A temporary workaround. We can't reuse available value if it's
704 // not safe to move the def of the virtual register's class. e.g.
705 // X86::RFP* register classes. Do not add it as a live-in.
706 if (!TII
->isSafeToMoveRegClassDefs(RC
))
707 // This is no longer available.
708 NotAvailable
.insert(Reg
);
711 InvalidateKill(Reg
, TRI
, RegKills
, KillOps
);
714 // Skip over the same register.
715 std::multimap
<unsigned, int>::iterator NI
= next(I
);
716 while (NI
!= E
&& NI
->first
== Reg
) {
722 for (std::set
<unsigned>::iterator I
= NotAvailable
.begin(),
723 E
= NotAvailable
.end(); I
!= E
; ++I
) {
725 for (const unsigned *SubRegs
= TRI
->getSubRegisters(*I
);
727 ClobberPhysReg(*SubRegs
);
731 /// ModifyStackSlotOrReMat - This method is called when the value in a stack
732 /// slot changes. This removes information about which register the previous
733 /// value for this slot lives in (as the previous value is dead now).
734 void AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat
) {
735 std::map
<int, unsigned>::iterator It
=
736 SpillSlotsOrReMatsAvailable
.find(SlotOrReMat
);
737 if (It
== SpillSlotsOrReMatsAvailable
.end()) return;
738 unsigned Reg
= It
->second
>> 1;
739 SpillSlotsOrReMatsAvailable
.erase(It
);
741 // This register may hold the value of multiple stack slots, only remove this
742 // stack slot from the set of values the register contains.
743 std::multimap
<unsigned, int>::iterator I
= PhysRegsAvailable
.lower_bound(Reg
);
745 assert(I
!= PhysRegsAvailable
.end() && I
->first
== Reg
&&
746 "Map inverse broken!");
747 if (I
->second
== SlotOrReMat
) break;
749 PhysRegsAvailable
.erase(I
);
752 // ************************** //
753 // Reuse Info Implementation //
754 // ************************** //
756 /// GetRegForReload - We are about to emit a reload into PhysReg. If there
757 /// is some other operand that is using the specified register, either pick
758 /// a new register to use, or evict the previous reload and use this reg.
759 unsigned ReuseInfo::GetRegForReload(const TargetRegisterClass
*RC
,
762 MachineInstr
*MI
, AvailableSpills
&Spills
,
763 std::vector
<MachineInstr
*> &MaybeDeadStores
,
764 SmallSet
<unsigned, 8> &Rejected
,
766 std::vector
<MachineOperand
*> &KillOps
,
768 const TargetInstrInfo
* TII
= MF
.getTarget().getInstrInfo();
769 const TargetRegisterInfo
*TRI
= Spills
.getRegInfo();
771 if (Reuses
.empty()) return PhysReg
; // This is most often empty.
773 for (unsigned ro
= 0, e
= Reuses
.size(); ro
!= e
; ++ro
) {
774 ReusedOp
&Op
= Reuses
[ro
];
775 // If we find some other reuse that was supposed to use this register
776 // exactly for its reload, we can change this reload to use ITS reload
777 // register. That is, unless its reload register has already been
778 // considered and subsequently rejected because it has also been reused
779 // by another operand.
780 if (Op
.PhysRegReused
== PhysReg
&&
781 Rejected
.count(Op
.AssignedPhysReg
) == 0 &&
782 RC
->contains(Op
.AssignedPhysReg
)) {
783 // Yup, use the reload register that we didn't use before.
784 unsigned NewReg
= Op
.AssignedPhysReg
;
785 Rejected
.insert(PhysReg
);
786 return GetRegForReload(RC
, NewReg
, MF
, MI
, Spills
, MaybeDeadStores
, Rejected
,
787 RegKills
, KillOps
, VRM
);
789 // Otherwise, we might also have a problem if a previously reused
790 // value aliases the new register. If so, codegen the previous reload
792 unsigned PRRU
= Op
.PhysRegReused
;
793 if (TRI
->areAliases(PRRU
, PhysReg
)) {
794 // Okay, we found out that an alias of a reused register
795 // was used. This isn't good because it means we have
796 // to undo a previous reuse.
797 MachineBasicBlock
*MBB
= MI
->getParent();
798 const TargetRegisterClass
*AliasRC
=
799 MBB
->getParent()->getRegInfo().getRegClass(Op
.VirtReg
);
801 // Copy Op out of the vector and remove it, we're going to insert an
802 // explicit load for it.
804 Reuses
.erase(Reuses
.begin()+ro
);
806 // Ok, we're going to try to reload the assigned physreg into the
807 // slot that we were supposed to in the first place. However, that
808 // register could hold a reuse. Check to see if it conflicts or
809 // would prefer us to use a different register.
810 unsigned NewPhysReg
= GetRegForReload(RC
, NewOp
.AssignedPhysReg
,
811 MF
, MI
, Spills
, MaybeDeadStores
,
812 Rejected
, RegKills
, KillOps
, VRM
);
814 bool DoReMat
= NewOp
.StackSlotOrReMat
> VirtRegMap::MAX_STACK_SLOT
;
815 int SSorRMId
= DoReMat
816 ? VRM
.getReMatId(NewOp
.VirtReg
) : NewOp
.StackSlotOrReMat
;
818 // Back-schedule reloads and remats.
819 MachineBasicBlock::iterator InsertLoc
=
820 ComputeReloadLoc(MI
, MBB
->begin(), PhysReg
, TRI
,
821 DoReMat
, SSorRMId
, TII
, MF
);
824 ReMaterialize(*MBB
, InsertLoc
, NewPhysReg
, NewOp
.VirtReg
, TII
,
827 TII
->loadRegFromStackSlot(*MBB
, InsertLoc
, NewPhysReg
,
828 NewOp
.StackSlotOrReMat
, AliasRC
);
829 MachineInstr
*LoadMI
= prior(InsertLoc
);
830 VRM
.addSpillSlotUse(NewOp
.StackSlotOrReMat
, LoadMI
);
831 // Any stores to this stack slot are not dead anymore.
832 MaybeDeadStores
[NewOp
.StackSlotOrReMat
] = NULL
;
835 Spills
.ClobberPhysReg(NewPhysReg
);
836 Spills
.ClobberPhysReg(NewOp
.PhysRegReused
);
838 unsigned SubIdx
= MI
->getOperand(NewOp
.Operand
).getSubReg();
839 unsigned RReg
= SubIdx
? TRI
->getSubReg(NewPhysReg
, SubIdx
) : NewPhysReg
;
840 MI
->getOperand(NewOp
.Operand
).setReg(RReg
);
841 MI
->getOperand(NewOp
.Operand
).setSubReg(0);
843 Spills
.addAvailable(NewOp
.StackSlotOrReMat
, NewPhysReg
);
844 UpdateKills(*prior(InsertLoc
), TRI
, RegKills
, KillOps
);
845 DOUT
<< '\t' << *prior(InsertLoc
);
847 DOUT
<< "Reuse undone!\n";
850 // Finally, PhysReg is now available, go ahead and use it.
858 // ************************************************************************ //
860 /// FoldsStackSlotModRef - Return true if the specified MI folds the specified
861 /// stack slot mod/ref. It also checks if it's possible to unfold the
862 /// instruction by having it define a specified physical register instead.
863 static bool FoldsStackSlotModRef(MachineInstr
&MI
, int SS
, unsigned PhysReg
,
864 const TargetInstrInfo
*TII
,
865 const TargetRegisterInfo
*TRI
,
867 if (VRM
.hasEmergencySpills(&MI
) || VRM
.isSpillPt(&MI
))
871 VirtRegMap::MI2VirtMapTy::const_iterator I
, End
;
872 for (tie(I
, End
) = VRM
.getFoldedVirts(&MI
); I
!= End
; ++I
) {
873 unsigned VirtReg
= I
->second
.first
;
874 VirtRegMap::ModRef MR
= I
->second
.second
;
875 if (MR
& VirtRegMap::isModRef
)
876 if (VRM
.getStackSlot(VirtReg
) == SS
) {
877 Found
= TII
->getOpcodeAfterMemoryUnfold(MI
.getOpcode(), true, true) != 0;
884 // Does the instruction uses a register that overlaps the scratch register?
885 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
886 MachineOperand
&MO
= MI
.getOperand(i
);
887 if (!MO
.isReg() || MO
.getReg() == 0)
889 unsigned Reg
= MO
.getReg();
890 if (TargetRegisterInfo::isVirtualRegister(Reg
)) {
891 if (!VRM
.hasPhys(Reg
))
893 Reg
= VRM
.getPhys(Reg
);
895 if (TRI
->regsOverlap(PhysReg
, Reg
))
901 /// FindFreeRegister - Find a free register of a given register class by looking
902 /// at (at most) the last two machine instructions.
903 static unsigned FindFreeRegister(MachineBasicBlock::iterator MII
,
904 MachineBasicBlock
&MBB
,
905 const TargetRegisterClass
*RC
,
906 const TargetRegisterInfo
*TRI
,
907 BitVector
&AllocatableRegs
) {
908 BitVector
Defs(TRI
->getNumRegs());
909 BitVector
Uses(TRI
->getNumRegs());
910 SmallVector
<unsigned, 4> LocalUses
;
911 SmallVector
<unsigned, 4> Kills
;
913 // Take a look at 2 instructions at most.
914 for (unsigned Count
= 0; Count
< 2; ++Count
) {
915 if (MII
== MBB
.begin())
917 MachineInstr
*PrevMI
= prior(MII
);
918 for (unsigned i
= 0, e
= PrevMI
->getNumOperands(); i
!= e
; ++i
) {
919 MachineOperand
&MO
= PrevMI
->getOperand(i
);
920 if (!MO
.isReg() || MO
.getReg() == 0)
922 unsigned Reg
= MO
.getReg();
925 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
)
928 LocalUses
.push_back(Reg
);
929 if (MO
.isKill() && AllocatableRegs
[Reg
])
930 Kills
.push_back(Reg
);
934 for (unsigned i
= 0, e
= Kills
.size(); i
!= e
; ++i
) {
935 unsigned Kill
= Kills
[i
];
936 if (!Defs
[Kill
] && !Uses
[Kill
] &&
937 TRI
->getPhysicalRegisterRegClass(Kill
) == RC
)
940 for (unsigned i
= 0, e
= LocalUses
.size(); i
!= e
; ++i
) {
941 unsigned Reg
= LocalUses
[i
];
943 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
)
954 void AssignPhysToVirtReg(MachineInstr
*MI
, unsigned VirtReg
, unsigned PhysReg
) {
955 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
956 MachineOperand
&MO
= MI
->getOperand(i
);
957 if (MO
.isReg() && MO
.getReg() == VirtReg
)
964 bool operator()(const std::pair
<MachineInstr
*, int> &A
,
965 const std::pair
<MachineInstr
*, int> &B
) {
966 return A
.second
< B
.second
;
971 // ***************************** //
972 // Local Spiller Implementation //
973 // ***************************** //
977 class VISIBILITY_HIDDEN LocalRewriter
: public VirtRegRewriter
{
978 MachineRegisterInfo
*RegInfo
;
979 const TargetRegisterInfo
*TRI
;
980 const TargetInstrInfo
*TII
;
981 BitVector AllocatableRegs
;
982 DenseMap
<MachineInstr
*, unsigned> DistanceMap
;
985 bool runOnMachineFunction(MachineFunction
&MF
, VirtRegMap
&VRM
,
986 LiveIntervals
* LIs
) {
987 RegInfo
= &MF
.getRegInfo();
988 TRI
= MF
.getTarget().getRegisterInfo();
989 TII
= MF
.getTarget().getInstrInfo();
990 AllocatableRegs
= TRI
->getAllocatableSet(MF
);
991 DEBUG(errs() << "\n**** Local spiller rewriting function '"
992 << MF
.getFunction()->getName() << "':\n");
993 DOUT
<< "**** Machine Instrs (NOTE! Does not include spills and reloads!)"
997 // Spills - Keep track of which spilled values are available in physregs
998 // so that we can choose to reuse the physregs instead of emitting
999 // reloads. This is usually refreshed per basic block.
1000 AvailableSpills
Spills(TRI
, TII
);
1002 // Keep track of kill information.
1003 BitVector
RegKills(TRI
->getNumRegs());
1004 std::vector
<MachineOperand
*> KillOps
;
1005 KillOps
.resize(TRI
->getNumRegs(), NULL
);
1007 // SingleEntrySuccs - Successor blocks which have a single predecessor.
1008 SmallVector
<MachineBasicBlock
*, 4> SinglePredSuccs
;
1009 SmallPtrSet
<MachineBasicBlock
*,16> EarlyVisited
;
1011 // Traverse the basic blocks depth first.
1012 MachineBasicBlock
*Entry
= MF
.begin();
1013 SmallPtrSet
<MachineBasicBlock
*,16> Visited
;
1014 for (df_ext_iterator
<MachineBasicBlock
*,
1015 SmallPtrSet
<MachineBasicBlock
*,16> >
1016 DFI
= df_ext_begin(Entry
, Visited
), E
= df_ext_end(Entry
, Visited
);
1018 MachineBasicBlock
*MBB
= *DFI
;
1019 if (!EarlyVisited
.count(MBB
))
1020 RewriteMBB(*MBB
, VRM
, LIs
, Spills
, RegKills
, KillOps
);
1022 // If this MBB is the only predecessor of a successor. Keep the
1023 // availability information and visit it next.
1025 // Keep visiting single predecessor successor as long as possible.
1026 SinglePredSuccs
.clear();
1027 findSinglePredSuccessor(MBB
, SinglePredSuccs
);
1028 if (SinglePredSuccs
.empty())
1031 // FIXME: More than one successors, each of which has MBB has
1032 // the only predecessor.
1033 MBB
= SinglePredSuccs
[0];
1034 if (!Visited
.count(MBB
) && EarlyVisited
.insert(MBB
)) {
1035 Spills
.AddAvailableRegsToLiveIn(*MBB
, RegKills
, KillOps
);
1036 RewriteMBB(*MBB
, VRM
, LIs
, Spills
, RegKills
, KillOps
);
1041 // Clear the availability info.
1045 DOUT
<< "**** Post Machine Instrs ****\n";
1048 // Mark unused spill slots.
1049 MachineFrameInfo
*MFI
= MF
.getFrameInfo();
1050 int SS
= VRM
.getLowSpillSlot();
1051 if (SS
!= VirtRegMap::NO_STACK_SLOT
)
1052 for (int e
= VRM
.getHighSpillSlot(); SS
<= e
; ++SS
)
1053 if (!VRM
.isSpillSlotUsed(SS
)) {
1054 MFI
->RemoveStackObject(SS
);
1063 /// OptimizeByUnfold2 - Unfold a series of load / store folding instructions if
1064 /// a scratch register is available.
1065 /// xorq %r12<kill>, %r13
1066 /// addq %rax, -184(%rbp)
1067 /// addq %r13, -184(%rbp)
1069 /// xorq %r12<kill>, %r13
1070 /// movq -184(%rbp), %r12
1073 /// movq %r12, -184(%rbp)
1074 bool OptimizeByUnfold2(unsigned VirtReg
, int SS
,
1075 MachineBasicBlock
&MBB
,
1076 MachineBasicBlock::iterator
&MII
,
1077 std::vector
<MachineInstr
*> &MaybeDeadStores
,
1078 AvailableSpills
&Spills
,
1079 BitVector
&RegKills
,
1080 std::vector
<MachineOperand
*> &KillOps
,
1083 MachineBasicBlock::iterator NextMII
= next(MII
);
1084 if (NextMII
== MBB
.end())
1087 if (TII
->getOpcodeAfterMemoryUnfold(MII
->getOpcode(), true, true) == 0)
1090 // Now let's see if the last couple of instructions happens to have freed up
1092 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1093 unsigned PhysReg
= FindFreeRegister(MII
, MBB
, RC
, TRI
, AllocatableRegs
);
1097 MachineFunction
&MF
= *MBB
.getParent();
1098 TRI
= MF
.getTarget().getRegisterInfo();
1099 MachineInstr
&MI
= *MII
;
1100 if (!FoldsStackSlotModRef(MI
, SS
, PhysReg
, TII
, TRI
, VRM
))
1103 // If the next instruction also folds the same SS modref and can be unfoled,
1104 // then it's worthwhile to issue a load from SS into the free register and
1105 // then unfold these instructions.
1106 if (!FoldsStackSlotModRef(*NextMII
, SS
, PhysReg
, TII
, TRI
, VRM
))
1109 // Back-schedule reloads and remats.
1110 MachineBasicBlock::iterator InsertLoc
=
1111 ComputeReloadLoc(MII
, MBB
.begin(), PhysReg
, TRI
, false, SS
, TII
, MF
);
1113 // Load from SS to the spare physical register.
1114 TII
->loadRegFromStackSlot(MBB
, MII
, PhysReg
, SS
, RC
);
1115 // This invalidates Phys.
1116 Spills
.ClobberPhysReg(PhysReg
);
1117 // Remember it's available.
1118 Spills
.addAvailable(SS
, PhysReg
);
1119 MaybeDeadStores
[SS
] = NULL
;
1121 // Unfold current MI.
1122 SmallVector
<MachineInstr
*, 4> NewMIs
;
1123 if (!TII
->unfoldMemoryOperand(MF
, &MI
, VirtReg
, false, false, NewMIs
))
1124 llvm_unreachable("Unable unfold the load / store folding instruction!");
1125 assert(NewMIs
.size() == 1);
1126 AssignPhysToVirtReg(NewMIs
[0], VirtReg
, PhysReg
);
1127 VRM
.transferRestorePts(&MI
, NewMIs
[0]);
1128 MII
= MBB
.insert(MII
, NewMIs
[0]);
1129 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
1130 VRM
.RemoveMachineInstrFromMaps(&MI
);
1134 // Unfold next instructions that fold the same SS.
1136 MachineInstr
&NextMI
= *NextMII
;
1137 NextMII
= next(NextMII
);
1139 if (!TII
->unfoldMemoryOperand(MF
, &NextMI
, VirtReg
, false, false, NewMIs
))
1140 llvm_unreachable("Unable unfold the load / store folding instruction!");
1141 assert(NewMIs
.size() == 1);
1142 AssignPhysToVirtReg(NewMIs
[0], VirtReg
, PhysReg
);
1143 VRM
.transferRestorePts(&NextMI
, NewMIs
[0]);
1144 MBB
.insert(NextMII
, NewMIs
[0]);
1145 InvalidateKills(NextMI
, TRI
, RegKills
, KillOps
);
1146 VRM
.RemoveMachineInstrFromMaps(&NextMI
);
1149 if (NextMII
== MBB
.end())
1151 } while (FoldsStackSlotModRef(*NextMII
, SS
, PhysReg
, TII
, TRI
, VRM
));
1153 // Store the value back into SS.
1154 TII
->storeRegToStackSlot(MBB
, NextMII
, PhysReg
, true, SS
, RC
);
1155 MachineInstr
*StoreMI
= prior(NextMII
);
1156 VRM
.addSpillSlotUse(SS
, StoreMI
);
1157 VRM
.virtFolded(VirtReg
, StoreMI
, VirtRegMap::isMod
);
1162 /// OptimizeByUnfold - Turn a store folding instruction into a load folding
1163 /// instruction. e.g.
1165 /// movl %eax, -32(%ebp)
1166 /// movl -36(%ebp), %eax
1167 /// orl %eax, -32(%ebp)
1170 /// orl -36(%ebp), %eax
1171 /// mov %eax, -32(%ebp)
1172 /// This enables unfolding optimization for a subsequent instruction which will
1173 /// also eliminate the newly introduced store instruction.
1174 bool OptimizeByUnfold(MachineBasicBlock
&MBB
,
1175 MachineBasicBlock::iterator
&MII
,
1176 std::vector
<MachineInstr
*> &MaybeDeadStores
,
1177 AvailableSpills
&Spills
,
1178 BitVector
&RegKills
,
1179 std::vector
<MachineOperand
*> &KillOps
,
1181 MachineFunction
&MF
= *MBB
.getParent();
1182 MachineInstr
&MI
= *MII
;
1183 unsigned UnfoldedOpc
= 0;
1184 unsigned UnfoldPR
= 0;
1185 unsigned UnfoldVR
= 0;
1186 int FoldedSS
= VirtRegMap::NO_STACK_SLOT
;
1187 VirtRegMap::MI2VirtMapTy::const_iterator I
, End
;
1188 for (tie(I
, End
) = VRM
.getFoldedVirts(&MI
); I
!= End
; ) {
1189 // Only transform a MI that folds a single register.
1192 UnfoldVR
= I
->second
.first
;
1193 VirtRegMap::ModRef MR
= I
->second
.second
;
1194 // MI2VirtMap be can updated which invalidate the iterator.
1195 // Increment the iterator first.
1197 if (VRM
.isAssignedReg(UnfoldVR
))
1199 // If this reference is not a use, any previous store is now dead.
1200 // Otherwise, the store to this stack slot is not dead anymore.
1201 FoldedSS
= VRM
.getStackSlot(UnfoldVR
);
1202 MachineInstr
* DeadStore
= MaybeDeadStores
[FoldedSS
];
1203 if (DeadStore
&& (MR
& VirtRegMap::isModRef
)) {
1204 unsigned PhysReg
= Spills
.getSpillSlotOrReMatPhysReg(FoldedSS
);
1205 if (!PhysReg
|| !DeadStore
->readsRegister(PhysReg
))
1208 UnfoldedOpc
= TII
->getOpcodeAfterMemoryUnfold(MI
.getOpcode(),
1217 // Look for other unfolding opportunities.
1218 return OptimizeByUnfold2(UnfoldVR
, FoldedSS
, MBB
, MII
,
1219 MaybeDeadStores
, Spills
, RegKills
, KillOps
, VRM
);
1222 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
1223 MachineOperand
&MO
= MI
.getOperand(i
);
1224 if (!MO
.isReg() || MO
.getReg() == 0 || !MO
.isUse())
1226 unsigned VirtReg
= MO
.getReg();
1227 if (TargetRegisterInfo::isPhysicalRegister(VirtReg
) || MO
.getSubReg())
1229 if (VRM
.isAssignedReg(VirtReg
)) {
1230 unsigned PhysReg
= VRM
.getPhys(VirtReg
);
1231 if (PhysReg
&& TRI
->regsOverlap(PhysReg
, UnfoldPR
))
1233 } else if (VRM
.isReMaterialized(VirtReg
))
1235 int SS
= VRM
.getStackSlot(VirtReg
);
1236 unsigned PhysReg
= Spills
.getSpillSlotOrReMatPhysReg(SS
);
1238 if (TRI
->regsOverlap(PhysReg
, UnfoldPR
))
1242 if (VRM
.hasPhys(VirtReg
)) {
1243 PhysReg
= VRM
.getPhys(VirtReg
);
1244 if (!TRI
->regsOverlap(PhysReg
, UnfoldPR
))
1248 // Ok, we'll need to reload the value into a register which makes
1249 // it impossible to perform the store unfolding optimization later.
1250 // Let's see if it is possible to fold the load if the store is
1251 // unfolded. This allows us to perform the store unfolding
1253 SmallVector
<MachineInstr
*, 4> NewMIs
;
1254 if (TII
->unfoldMemoryOperand(MF
, &MI
, UnfoldVR
, false, false, NewMIs
)) {
1255 assert(NewMIs
.size() == 1);
1256 MachineInstr
*NewMI
= NewMIs
.back();
1258 int Idx
= NewMI
->findRegisterUseOperandIdx(VirtReg
, false);
1260 SmallVector
<unsigned, 1> Ops
;
1262 MachineInstr
*FoldedMI
= TII
->foldMemoryOperand(MF
, NewMI
, Ops
, SS
);
1264 VRM
.addSpillSlotUse(SS
, FoldedMI
);
1265 if (!VRM
.hasPhys(UnfoldVR
))
1266 VRM
.assignVirt2Phys(UnfoldVR
, UnfoldPR
);
1267 VRM
.virtFolded(VirtReg
, FoldedMI
, VirtRegMap::isRef
);
1268 MII
= MBB
.insert(MII
, FoldedMI
);
1269 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
1270 VRM
.RemoveMachineInstrFromMaps(&MI
);
1272 MF
.DeleteMachineInstr(NewMI
);
1275 MF
.DeleteMachineInstr(NewMI
);
1282 /// CommuteChangesDestination - We are looking for r0 = op r1, r2 and
1283 /// where SrcReg is r1 and it is tied to r0. Return true if after
1284 /// commuting this instruction it will be r0 = op r2, r1.
1285 static bool CommuteChangesDestination(MachineInstr
*DefMI
,
1286 const TargetInstrDesc
&TID
,
1288 const TargetInstrInfo
*TII
,
1290 if (TID
.getNumDefs() != 1 && TID
.getNumOperands() != 3)
1292 if (!DefMI
->getOperand(1).isReg() ||
1293 DefMI
->getOperand(1).getReg() != SrcReg
)
1296 if (!DefMI
->isRegTiedToDefOperand(1, &DefIdx
) || DefIdx
!= 0)
1298 unsigned SrcIdx1
, SrcIdx2
;
1299 if (!TII
->findCommutedOpIndices(DefMI
, SrcIdx1
, SrcIdx2
))
1301 if (SrcIdx1
== 1 && SrcIdx2
== 2) {
1308 /// CommuteToFoldReload -
1311 /// r1 = op r1, r2<kill>
1314 /// If op is commutable and r2 is killed, then we can xform these to
1315 /// r2 = op r2, fi#1
1317 bool CommuteToFoldReload(MachineBasicBlock
&MBB
,
1318 MachineBasicBlock::iterator
&MII
,
1319 unsigned VirtReg
, unsigned SrcReg
, int SS
,
1320 AvailableSpills
&Spills
,
1321 BitVector
&RegKills
,
1322 std::vector
<MachineOperand
*> &KillOps
,
1323 const TargetRegisterInfo
*TRI
,
1325 if (MII
== MBB
.begin() || !MII
->killsRegister(SrcReg
))
1328 MachineFunction
&MF
= *MBB
.getParent();
1329 MachineInstr
&MI
= *MII
;
1330 MachineBasicBlock::iterator DefMII
= prior(MII
);
1331 MachineInstr
*DefMI
= DefMII
;
1332 const TargetInstrDesc
&TID
= DefMI
->getDesc();
1334 if (DefMII
!= MBB
.begin() &&
1335 TID
.isCommutable() &&
1336 CommuteChangesDestination(DefMI
, TID
, SrcReg
, TII
, NewDstIdx
)) {
1337 MachineOperand
&NewDstMO
= DefMI
->getOperand(NewDstIdx
);
1338 unsigned NewReg
= NewDstMO
.getReg();
1339 if (!NewDstMO
.isKill() || TRI
->regsOverlap(NewReg
, SrcReg
))
1341 MachineInstr
*ReloadMI
= prior(DefMII
);
1343 unsigned DestReg
= TII
->isLoadFromStackSlot(ReloadMI
, FrameIdx
);
1344 if (DestReg
!= SrcReg
|| FrameIdx
!= SS
)
1346 int UseIdx
= DefMI
->findRegisterUseOperandIdx(DestReg
, false);
1350 if (!MI
.isRegTiedToDefOperand(UseIdx
, &DefIdx
))
1352 assert(DefMI
->getOperand(DefIdx
).isReg() &&
1353 DefMI
->getOperand(DefIdx
).getReg() == SrcReg
);
1355 // Now commute def instruction.
1356 MachineInstr
*CommutedMI
= TII
->commuteInstruction(DefMI
, true);
1359 SmallVector
<unsigned, 1> Ops
;
1360 Ops
.push_back(NewDstIdx
);
1361 MachineInstr
*FoldedMI
= TII
->foldMemoryOperand(MF
, CommutedMI
, Ops
, SS
);
1362 // Not needed since foldMemoryOperand returns new MI.
1363 MF
.DeleteMachineInstr(CommutedMI
);
1367 VRM
.addSpillSlotUse(SS
, FoldedMI
);
1368 VRM
.virtFolded(VirtReg
, FoldedMI
, VirtRegMap::isRef
);
1369 // Insert new def MI and spill MI.
1370 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1371 TII
->storeRegToStackSlot(MBB
, &MI
, NewReg
, true, SS
, RC
);
1373 MachineInstr
*StoreMI
= MII
;
1374 VRM
.addSpillSlotUse(SS
, StoreMI
);
1375 VRM
.virtFolded(VirtReg
, StoreMI
, VirtRegMap::isMod
);
1376 MII
= MBB
.insert(MII
, FoldedMI
); // Update MII to backtrack.
1378 // Delete all 3 old instructions.
1379 InvalidateKills(*ReloadMI
, TRI
, RegKills
, KillOps
);
1380 VRM
.RemoveMachineInstrFromMaps(ReloadMI
);
1381 MBB
.erase(ReloadMI
);
1382 InvalidateKills(*DefMI
, TRI
, RegKills
, KillOps
);
1383 VRM
.RemoveMachineInstrFromMaps(DefMI
);
1385 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
1386 VRM
.RemoveMachineInstrFromMaps(&MI
);
1389 // If NewReg was previously holding value of some SS, it's now clobbered.
1390 // This has to be done now because it's a physical register. When this
1391 // instruction is re-visited, it's ignored.
1392 Spills
.ClobberPhysReg(NewReg
);
1401 /// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if
1402 /// the last store to the same slot is now dead. If so, remove the last store.
1403 void SpillRegToStackSlot(MachineBasicBlock
&MBB
,
1404 MachineBasicBlock::iterator
&MII
,
1405 int Idx
, unsigned PhysReg
, int StackSlot
,
1406 const TargetRegisterClass
*RC
,
1407 bool isAvailable
, MachineInstr
*&LastStore
,
1408 AvailableSpills
&Spills
,
1409 SmallSet
<MachineInstr
*, 4> &ReMatDefs
,
1410 BitVector
&RegKills
,
1411 std::vector
<MachineOperand
*> &KillOps
,
1414 TII
->storeRegToStackSlot(MBB
, next(MII
), PhysReg
, true, StackSlot
, RC
);
1415 MachineInstr
*StoreMI
= next(MII
);
1416 VRM
.addSpillSlotUse(StackSlot
, StoreMI
);
1417 DOUT
<< "Store:\t" << *StoreMI
;
1419 // If there is a dead store to this stack slot, nuke it now.
1421 DOUT
<< "Removed dead store:\t" << *LastStore
;
1423 SmallVector
<unsigned, 2> KillRegs
;
1424 InvalidateKills(*LastStore
, TRI
, RegKills
, KillOps
, &KillRegs
);
1425 MachineBasicBlock::iterator PrevMII
= LastStore
;
1426 bool CheckDef
= PrevMII
!= MBB
.begin();
1429 VRM
.RemoveMachineInstrFromMaps(LastStore
);
1430 MBB
.erase(LastStore
);
1432 // Look at defs of killed registers on the store. Mark the defs
1433 // as dead since the store has been deleted and they aren't
1435 for (unsigned j
= 0, ee
= KillRegs
.size(); j
!= ee
; ++j
) {
1436 bool HasOtherDef
= false;
1437 if (InvalidateRegDef(PrevMII
, *MII
, KillRegs
[j
], HasOtherDef
)) {
1438 MachineInstr
*DeadDef
= PrevMII
;
1439 if (ReMatDefs
.count(DeadDef
) && !HasOtherDef
) {
1440 // FIXME: This assumes a remat def does not have side effects.
1441 VRM
.RemoveMachineInstrFromMaps(DeadDef
);
1450 LastStore
= next(MII
);
1452 // If the stack slot value was previously available in some other
1453 // register, change it now. Otherwise, make the register available,
1455 Spills
.ModifyStackSlotOrReMat(StackSlot
);
1456 Spills
.ClobberPhysReg(PhysReg
);
1457 Spills
.addAvailable(StackSlot
, PhysReg
, isAvailable
);
1461 /// TransferDeadness - A identity copy definition is dead and it's being
1462 /// removed. Find the last def or use and mark it as dead / kill.
1463 void TransferDeadness(MachineBasicBlock
*MBB
, unsigned CurDist
,
1464 unsigned Reg
, BitVector
&RegKills
,
1465 std::vector
<MachineOperand
*> &KillOps
,
1467 SmallPtrSet
<MachineInstr
*, 4> Seens
;
1468 SmallVector
<std::pair
<MachineInstr
*, int>,8> Refs
;
1469 for (MachineRegisterInfo::reg_iterator RI
= RegInfo
->reg_begin(Reg
),
1470 RE
= RegInfo
->reg_end(); RI
!= RE
; ++RI
) {
1471 MachineInstr
*UDMI
= &*RI
;
1472 if (UDMI
->getParent() != MBB
)
1474 DenseMap
<MachineInstr
*, unsigned>::iterator DI
= DistanceMap
.find(UDMI
);
1475 if (DI
== DistanceMap
.end() || DI
->second
> CurDist
)
1477 if (Seens
.insert(UDMI
))
1478 Refs
.push_back(std::make_pair(UDMI
, DI
->second
));
1483 std::sort(Refs
.begin(), Refs
.end(), RefSorter());
1485 while (!Refs
.empty()) {
1486 MachineInstr
*LastUDMI
= Refs
.back().first
;
1489 MachineOperand
*LastUD
= NULL
;
1490 for (unsigned i
= 0, e
= LastUDMI
->getNumOperands(); i
!= e
; ++i
) {
1491 MachineOperand
&MO
= LastUDMI
->getOperand(i
);
1492 if (!MO
.isReg() || MO
.getReg() != Reg
)
1494 if (!LastUD
|| (LastUD
->isUse() && MO
.isDef()))
1496 if (LastUDMI
->isRegTiedToDefOperand(i
))
1499 if (LastUD
->isDef()) {
1500 // If the instruction has no side effect, delete it and propagate
1501 // backward further. Otherwise, mark is dead and we are done.
1502 if (!TII
->isDeadInstruction(LastUDMI
)) {
1503 LastUD
->setIsDead();
1506 VRM
.RemoveMachineInstrFromMaps(LastUDMI
);
1507 MBB
->erase(LastUDMI
);
1509 LastUD
->setIsKill();
1511 KillOps
[Reg
] = LastUD
;
1517 /// rewriteMBB - Keep track of which spills are available even after the
1518 /// register allocator is done with them. If possible, avid reloading vregs.
1519 void RewriteMBB(MachineBasicBlock
&MBB
, VirtRegMap
&VRM
,
1521 AvailableSpills
&Spills
, BitVector
&RegKills
,
1522 std::vector
<MachineOperand
*> &KillOps
) {
1524 DEBUG(errs() << "\n**** Local spiller rewriting MBB '"
1525 << MBB
.getBasicBlock()->getName() << "':\n");
1527 MachineFunction
&MF
= *MBB
.getParent();
1529 // MaybeDeadStores - When we need to write a value back into a stack slot,
1530 // keep track of the inserted store. If the stack slot value is never read
1531 // (because the value was used from some available register, for example), and
1532 // subsequently stored to, the original store is dead. This map keeps track
1533 // of inserted stores that are not used. If we see a subsequent store to the
1534 // same stack slot, the original store is deleted.
1535 std::vector
<MachineInstr
*> MaybeDeadStores
;
1536 MaybeDeadStores
.resize(MF
.getFrameInfo()->getObjectIndexEnd(), NULL
);
1538 // ReMatDefs - These are rematerializable def MIs which are not deleted.
1539 SmallSet
<MachineInstr
*, 4> ReMatDefs
;
1542 SmallSet
<unsigned, 2> KilledMIRegs
;
1545 KillOps
.resize(TRI
->getNumRegs(), NULL
);
1548 DistanceMap
.clear();
1549 for (MachineBasicBlock::iterator MII
= MBB
.begin(), E
= MBB
.end();
1551 MachineBasicBlock::iterator NextMII
= next(MII
);
1553 VirtRegMap::MI2VirtMapTy::const_iterator I
, End
;
1554 bool Erased
= false;
1555 bool BackTracked
= false;
1556 if (OptimizeByUnfold(MBB
, MII
,
1557 MaybeDeadStores
, Spills
, RegKills
, KillOps
, VRM
))
1558 NextMII
= next(MII
);
1560 MachineInstr
&MI
= *MII
;
1562 if (VRM
.hasEmergencySpills(&MI
)) {
1563 // Spill physical register(s) in the rare case the allocator has run out
1564 // of registers to allocate.
1565 SmallSet
<int, 4> UsedSS
;
1566 std::vector
<unsigned> &EmSpills
= VRM
.getEmergencySpills(&MI
);
1567 for (unsigned i
= 0, e
= EmSpills
.size(); i
!= e
; ++i
) {
1568 unsigned PhysReg
= EmSpills
[i
];
1569 const TargetRegisterClass
*RC
=
1570 TRI
->getPhysicalRegisterRegClass(PhysReg
);
1571 assert(RC
&& "Unable to determine register class!");
1572 int SS
= VRM
.getEmergencySpillSlot(RC
);
1573 if (UsedSS
.count(SS
))
1574 llvm_unreachable("Need to spill more than one physical registers!");
1576 TII
->storeRegToStackSlot(MBB
, MII
, PhysReg
, true, SS
, RC
);
1577 MachineInstr
*StoreMI
= prior(MII
);
1578 VRM
.addSpillSlotUse(SS
, StoreMI
);
1580 // Back-schedule reloads and remats.
1581 MachineBasicBlock::iterator InsertLoc
=
1582 ComputeReloadLoc(next(MII
), MBB
.begin(), PhysReg
, TRI
, false,
1585 TII
->loadRegFromStackSlot(MBB
, InsertLoc
, PhysReg
, SS
, RC
);
1587 MachineInstr
*LoadMI
= prior(InsertLoc
);
1588 VRM
.addSpillSlotUse(SS
, LoadMI
);
1590 DistanceMap
.insert(std::make_pair(LoadMI
, Dist
++));
1592 NextMII
= next(MII
);
1595 // Insert restores here if asked to.
1596 if (VRM
.isRestorePt(&MI
)) {
1597 std::vector
<unsigned> &RestoreRegs
= VRM
.getRestorePtRestores(&MI
);
1598 for (unsigned i
= 0, e
= RestoreRegs
.size(); i
!= e
; ++i
) {
1599 unsigned VirtReg
= RestoreRegs
[e
-i
-1]; // Reverse order.
1600 if (!VRM
.getPreSplitReg(VirtReg
))
1601 continue; // Split interval spilled again.
1602 unsigned Phys
= VRM
.getPhys(VirtReg
);
1603 RegInfo
->setPhysRegUsed(Phys
);
1605 // Check if the value being restored if available. If so, it must be
1606 // from a predecessor BB that fallthrough into this BB. We do not
1612 // ... # r1 not clobbered
1615 bool DoReMat
= VRM
.isReMaterialized(VirtReg
);
1616 int SSorRMId
= DoReMat
1617 ? VRM
.getReMatId(VirtReg
) : VRM
.getStackSlot(VirtReg
);
1618 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1619 unsigned InReg
= Spills
.getSpillSlotOrReMatPhysReg(SSorRMId
);
1620 if (InReg
== Phys
) {
1621 // If the value is already available in the expected register, save
1622 // a reload / remat.
1624 DOUT
<< "Reusing RM#" << SSorRMId
-VirtRegMap::MAX_STACK_SLOT
-1;
1626 DOUT
<< "Reusing SS#" << SSorRMId
;
1627 DOUT
<< " from physreg "
1628 << TRI
->getName(InReg
) << " for vreg"
1629 << VirtReg
<<" instead of reloading into physreg "
1630 << TRI
->getName(Phys
) << "\n";
1633 } else if (InReg
&& InReg
!= Phys
) {
1635 DOUT
<< "Reusing RM#" << SSorRMId
-VirtRegMap::MAX_STACK_SLOT
-1;
1637 DOUT
<< "Reusing SS#" << SSorRMId
;
1638 DOUT
<< " from physreg "
1639 << TRI
->getName(InReg
) << " for vreg"
1640 << VirtReg
<<" by copying it into physreg "
1641 << TRI
->getName(Phys
) << "\n";
1643 // If the reloaded / remat value is available in another register,
1644 // copy it to the desired register.
1646 // Back-schedule reloads and remats.
1647 MachineBasicBlock::iterator InsertLoc
=
1648 ComputeReloadLoc(MII
, MBB
.begin(), Phys
, TRI
, DoReMat
,
1651 TII
->copyRegToReg(MBB
, InsertLoc
, Phys
, InReg
, RC
, RC
);
1653 // This invalidates Phys.
1654 Spills
.ClobberPhysReg(Phys
);
1655 // Remember it's available.
1656 Spills
.addAvailable(SSorRMId
, Phys
);
1659 MachineInstr
*CopyMI
= prior(InsertLoc
);
1660 MachineOperand
*KillOpnd
= CopyMI
->findRegisterUseOperand(InReg
);
1661 KillOpnd
->setIsKill();
1662 UpdateKills(*CopyMI
, TRI
, RegKills
, KillOps
);
1664 DOUT
<< '\t' << *CopyMI
;
1669 // Back-schedule reloads and remats.
1670 MachineBasicBlock::iterator InsertLoc
=
1671 ComputeReloadLoc(MII
, MBB
.begin(), Phys
, TRI
, DoReMat
,
1674 if (VRM
.isReMaterialized(VirtReg
)) {
1675 ReMaterialize(MBB
, InsertLoc
, Phys
, VirtReg
, TII
, TRI
, VRM
);
1677 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1678 TII
->loadRegFromStackSlot(MBB
, InsertLoc
, Phys
, SSorRMId
, RC
);
1679 MachineInstr
*LoadMI
= prior(InsertLoc
);
1680 VRM
.addSpillSlotUse(SSorRMId
, LoadMI
);
1682 DistanceMap
.insert(std::make_pair(LoadMI
, Dist
++));
1685 // This invalidates Phys.
1686 Spills
.ClobberPhysReg(Phys
);
1687 // Remember it's available.
1688 Spills
.addAvailable(SSorRMId
, Phys
);
1690 UpdateKills(*prior(InsertLoc
), TRI
, RegKills
, KillOps
);
1691 DOUT
<< '\t' << *prior(MII
);
1695 // Insert spills here if asked to.
1696 if (VRM
.isSpillPt(&MI
)) {
1697 std::vector
<std::pair
<unsigned,bool> > &SpillRegs
=
1698 VRM
.getSpillPtSpills(&MI
);
1699 for (unsigned i
= 0, e
= SpillRegs
.size(); i
!= e
; ++i
) {
1700 unsigned VirtReg
= SpillRegs
[i
].first
;
1701 bool isKill
= SpillRegs
[i
].second
;
1702 if (!VRM
.getPreSplitReg(VirtReg
))
1703 continue; // Split interval spilled again.
1704 const TargetRegisterClass
*RC
= RegInfo
->getRegClass(VirtReg
);
1705 unsigned Phys
= VRM
.getPhys(VirtReg
);
1706 int StackSlot
= VRM
.getStackSlot(VirtReg
);
1707 TII
->storeRegToStackSlot(MBB
, next(MII
), Phys
, isKill
, StackSlot
, RC
);
1708 MachineInstr
*StoreMI
= next(MII
);
1709 VRM
.addSpillSlotUse(StackSlot
, StoreMI
);
1710 DOUT
<< "Store:\t" << *StoreMI
;
1711 VRM
.virtFolded(VirtReg
, StoreMI
, VirtRegMap::isMod
);
1713 NextMII
= next(MII
);
1716 /// ReusedOperands - Keep track of operand reuse in case we need to undo
1718 ReuseInfo
ReusedOperands(MI
, TRI
);
1719 SmallVector
<unsigned, 4> VirtUseOps
;
1720 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
1721 MachineOperand
&MO
= MI
.getOperand(i
);
1722 if (!MO
.isReg() || MO
.getReg() == 0)
1723 continue; // Ignore non-register operands.
1725 unsigned VirtReg
= MO
.getReg();
1726 if (TargetRegisterInfo::isPhysicalRegister(VirtReg
)) {
1727 // Ignore physregs for spilling, but remember that it is used by this
1729 RegInfo
->setPhysRegUsed(VirtReg
);
1733 // We want to process implicit virtual register uses first.
1734 if (MO
.isImplicit())
1735 // If the virtual register is implicitly defined, emit a implicit_def
1736 // before so scavenger knows it's "defined".
1737 // FIXME: This is a horrible hack done the by register allocator to
1738 // remat a definition with virtual register operand.
1739 VirtUseOps
.insert(VirtUseOps
.begin(), i
);
1741 VirtUseOps
.push_back(i
);
1744 // Process all of the spilled uses and all non spilled reg references.
1745 SmallVector
<int, 2> PotentialDeadStoreSlots
;
1746 KilledMIRegs
.clear();
1747 for (unsigned j
= 0, e
= VirtUseOps
.size(); j
!= e
; ++j
) {
1748 unsigned i
= VirtUseOps
[j
];
1749 MachineOperand
&MO
= MI
.getOperand(i
);
1750 unsigned VirtReg
= MO
.getReg();
1751 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
1752 "Not a virtual register?");
1754 unsigned SubIdx
= MO
.getSubReg();
1755 if (VRM
.isAssignedReg(VirtReg
)) {
1756 // This virtual register was assigned a physreg!
1757 unsigned Phys
= VRM
.getPhys(VirtReg
);
1758 RegInfo
->setPhysRegUsed(Phys
);
1760 ReusedOperands
.markClobbered(Phys
);
1761 unsigned RReg
= SubIdx
? TRI
->getSubReg(Phys
, SubIdx
) : Phys
;
1762 MI
.getOperand(i
).setReg(RReg
);
1763 MI
.getOperand(i
).setSubReg(0);
1764 if (VRM
.isImplicitlyDefined(VirtReg
))
1765 // FIXME: Is this needed?
1766 BuildMI(MBB
, &MI
, MI
.getDebugLoc(),
1767 TII
->get(TargetInstrInfo::IMPLICIT_DEF
), RReg
);
1771 // This virtual register is now known to be a spilled value.
1773 continue; // Handle defs in the loop below (handle use&def here though)
1775 bool AvoidReload
= MO
.isUndef();
1776 // Check if it is defined by an implicit def. It should not be spilled.
1777 // Note, this is for correctness reason. e.g.
1778 // 8 %reg1024<def> = IMPLICIT_DEF
1779 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1780 // The live range [12, 14) are not part of the r1024 live interval since
1781 // it's defined by an implicit def. It will not conflicts with live
1782 // interval of r1025. Now suppose both registers are spilled, you can
1783 // easily see a situation where both registers are reloaded before
1784 // the INSERT_SUBREG and both target registers that would overlap.
1785 bool DoReMat
= VRM
.isReMaterialized(VirtReg
);
1786 int SSorRMId
= DoReMat
1787 ? VRM
.getReMatId(VirtReg
) : VRM
.getStackSlot(VirtReg
);
1788 int ReuseSlot
= SSorRMId
;
1790 // Check to see if this stack slot is available.
1791 unsigned PhysReg
= Spills
.getSpillSlotOrReMatPhysReg(SSorRMId
);
1793 // If this is a sub-register use, make sure the reuse register is in the
1794 // right register class. For example, for x86 not all of the 32-bit
1795 // registers have accessible sub-registers.
1796 // Similarly so for EXTRACT_SUBREG. Consider this:
1798 // MOV32_mr fi#1, EDI
1800 // = EXTRACT_SUBREG fi#1
1801 // fi#1 is available in EDI, but it cannot be reused because it's not in
1802 // the right register file.
1803 if (PhysReg
&& !AvoidReload
&&
1804 (SubIdx
|| MI
.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG
)) {
1805 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1806 if (!RC
->contains(PhysReg
))
1810 if (PhysReg
&& !AvoidReload
) {
1811 // This spilled operand might be part of a two-address operand. If this
1812 // is the case, then changing it will necessarily require changing the
1813 // def part of the instruction as well. However, in some cases, we
1814 // aren't allowed to modify the reused register. If none of these cases
1816 bool CanReuse
= true;
1817 bool isTied
= MI
.isRegTiedToDefOperand(i
);
1819 // Okay, we have a two address operand. We can reuse this physreg as
1820 // long as we are allowed to clobber the value and there isn't an
1821 // earlier def that has already clobbered the physreg.
1822 CanReuse
= !ReusedOperands
.isClobbered(PhysReg
) &&
1823 Spills
.canClobberPhysReg(PhysReg
);
1827 // If this stack slot value is already available, reuse it!
1828 if (ReuseSlot
> VirtRegMap::MAX_STACK_SLOT
)
1829 DOUT
<< "Reusing RM#" << ReuseSlot
-VirtRegMap::MAX_STACK_SLOT
-1;
1831 DOUT
<< "Reusing SS#" << ReuseSlot
;
1832 DOUT
<< " from physreg "
1833 << TRI
->getName(PhysReg
) << " for vreg"
1834 << VirtReg
<<" instead of reloading into physreg "
1835 << TRI
->getName(VRM
.getPhys(VirtReg
)) << "\n";
1836 unsigned RReg
= SubIdx
? TRI
->getSubReg(PhysReg
, SubIdx
) : PhysReg
;
1837 MI
.getOperand(i
).setReg(RReg
);
1838 MI
.getOperand(i
).setSubReg(0);
1840 // The only technical detail we have is that we don't know that
1841 // PhysReg won't be clobbered by a reloaded stack slot that occurs
1842 // later in the instruction. In particular, consider 'op V1, V2'.
1843 // If V1 is available in physreg R0, we would choose to reuse it
1844 // here, instead of reloading it into the register the allocator
1845 // indicated (say R1). However, V2 might have to be reloaded
1846 // later, and it might indicate that it needs to live in R0. When
1847 // this occurs, we need to have information available that
1848 // indicates it is safe to use R1 for the reload instead of R0.
1850 // To further complicate matters, we might conflict with an alias,
1851 // or R0 and R1 might not be compatible with each other. In this
1852 // case, we actually insert a reload for V1 in R1, ensuring that
1853 // we can get at R0 or its alias.
1854 ReusedOperands
.addReuse(i
, ReuseSlot
, PhysReg
,
1855 VRM
.getPhys(VirtReg
), VirtReg
);
1857 // Only mark it clobbered if this is a use&def operand.
1858 ReusedOperands
.markClobbered(PhysReg
);
1861 if (MI
.getOperand(i
).isKill() &&
1862 ReuseSlot
<= VirtRegMap::MAX_STACK_SLOT
) {
1864 // The store of this spilled value is potentially dead, but we
1865 // won't know for certain until we've confirmed that the re-use
1866 // above is valid, which means waiting until the other operands
1867 // are processed. For now we just track the spill slot, we'll
1868 // remove it after the other operands are processed if valid.
1870 PotentialDeadStoreSlots
.push_back(ReuseSlot
);
1873 // Mark is isKill if it's there no other uses of the same virtual
1874 // register and it's not a two-address operand. IsKill will be
1875 // unset if reg is reused.
1876 if (!isTied
&& KilledMIRegs
.count(VirtReg
) == 0) {
1877 MI
.getOperand(i
).setIsKill();
1878 KilledMIRegs
.insert(VirtReg
);
1884 // Otherwise we have a situation where we have a two-address instruction
1885 // whose mod/ref operand needs to be reloaded. This reload is already
1886 // available in some register "PhysReg", but if we used PhysReg as the
1887 // operand to our 2-addr instruction, the instruction would modify
1888 // PhysReg. This isn't cool if something later uses PhysReg and expects
1889 // to get its initial value.
1891 // To avoid this problem, and to avoid doing a load right after a store,
1892 // we emit a copy from PhysReg into the designated register for this
1894 unsigned DesignatedReg
= VRM
.getPhys(VirtReg
);
1895 assert(DesignatedReg
&& "Must map virtreg to physreg!");
1897 // Note that, if we reused a register for a previous operand, the
1898 // register we want to reload into might not actually be
1899 // available. If this occurs, use the register indicated by the
1901 if (ReusedOperands
.hasReuses())
1902 DesignatedReg
= ReusedOperands
.GetRegForReload(VirtReg
,
1904 Spills
, MaybeDeadStores
, RegKills
, KillOps
, VRM
);
1906 // If the mapped designated register is actually the physreg we have
1907 // incoming, we don't need to inserted a dead copy.
1908 if (DesignatedReg
== PhysReg
) {
1909 // If this stack slot value is already available, reuse it!
1910 if (ReuseSlot
> VirtRegMap::MAX_STACK_SLOT
)
1911 DOUT
<< "Reusing RM#" << ReuseSlot
-VirtRegMap::MAX_STACK_SLOT
-1;
1913 DOUT
<< "Reusing SS#" << ReuseSlot
;
1914 DOUT
<< " from physreg " << TRI
->getName(PhysReg
)
1915 << " for vreg" << VirtReg
1916 << " instead of reloading into same physreg.\n";
1917 unsigned RReg
= SubIdx
? TRI
->getSubReg(PhysReg
, SubIdx
) : PhysReg
;
1918 MI
.getOperand(i
).setReg(RReg
);
1919 MI
.getOperand(i
).setSubReg(0);
1920 ReusedOperands
.markClobbered(RReg
);
1925 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1926 RegInfo
->setPhysRegUsed(DesignatedReg
);
1927 ReusedOperands
.markClobbered(DesignatedReg
);
1929 // Back-schedule reloads and remats.
1930 MachineBasicBlock::iterator InsertLoc
=
1931 ComputeReloadLoc(&MI
, MBB
.begin(), PhysReg
, TRI
, DoReMat
,
1934 TII
->copyRegToReg(MBB
, InsertLoc
, DesignatedReg
, PhysReg
, RC
, RC
);
1936 MachineInstr
*CopyMI
= prior(InsertLoc
);
1937 UpdateKills(*CopyMI
, TRI
, RegKills
, KillOps
);
1939 // This invalidates DesignatedReg.
1940 Spills
.ClobberPhysReg(DesignatedReg
);
1942 Spills
.addAvailable(ReuseSlot
, DesignatedReg
);
1944 SubIdx
? TRI
->getSubReg(DesignatedReg
, SubIdx
) : DesignatedReg
;
1945 MI
.getOperand(i
).setReg(RReg
);
1946 MI
.getOperand(i
).setSubReg(0);
1947 DOUT
<< '\t' << *prior(MII
);
1952 // Otherwise, reload it and remember that we have it.
1953 PhysReg
= VRM
.getPhys(VirtReg
);
1954 assert(PhysReg
&& "Must map virtreg to physreg!");
1956 // Note that, if we reused a register for a previous operand, the
1957 // register we want to reload into might not actually be
1958 // available. If this occurs, use the register indicated by the
1960 if (ReusedOperands
.hasReuses())
1961 PhysReg
= ReusedOperands
.GetRegForReload(VirtReg
, PhysReg
, &MI
,
1962 Spills
, MaybeDeadStores
, RegKills
, KillOps
, VRM
);
1964 RegInfo
->setPhysRegUsed(PhysReg
);
1965 ReusedOperands
.markClobbered(PhysReg
);
1969 // Back-schedule reloads and remats.
1970 MachineBasicBlock::iterator InsertLoc
=
1971 ComputeReloadLoc(MII
, MBB
.begin(), PhysReg
, TRI
, DoReMat
,
1975 ReMaterialize(MBB
, InsertLoc
, PhysReg
, VirtReg
, TII
, TRI
, VRM
);
1977 const TargetRegisterClass
* RC
= RegInfo
->getRegClass(VirtReg
);
1978 TII
->loadRegFromStackSlot(MBB
, InsertLoc
, PhysReg
, SSorRMId
, RC
);
1979 MachineInstr
*LoadMI
= prior(InsertLoc
);
1980 VRM
.addSpillSlotUse(SSorRMId
, LoadMI
);
1982 DistanceMap
.insert(std::make_pair(LoadMI
, Dist
++));
1984 // This invalidates PhysReg.
1985 Spills
.ClobberPhysReg(PhysReg
);
1987 // Any stores to this stack slot are not dead anymore.
1989 MaybeDeadStores
[SSorRMId
] = NULL
;
1990 Spills
.addAvailable(SSorRMId
, PhysReg
);
1991 // Assumes this is the last use. IsKill will be unset if reg is reused
1992 // unless it's a two-address operand.
1993 if (!MI
.isRegTiedToDefOperand(i
) &&
1994 KilledMIRegs
.count(VirtReg
) == 0) {
1995 MI
.getOperand(i
).setIsKill();
1996 KilledMIRegs
.insert(VirtReg
);
1999 UpdateKills(*prior(InsertLoc
), TRI
, RegKills
, KillOps
);
2000 DOUT
<< '\t' << *prior(InsertLoc
);
2002 unsigned RReg
= SubIdx
? TRI
->getSubReg(PhysReg
, SubIdx
) : PhysReg
;
2003 MI
.getOperand(i
).setReg(RReg
);
2004 MI
.getOperand(i
).setSubReg(0);
2007 // Ok - now we can remove stores that have been confirmed dead.
2008 for (unsigned j
= 0, e
= PotentialDeadStoreSlots
.size(); j
!= e
; ++j
) {
2009 // This was the last use and the spilled value is still available
2010 // for reuse. That means the spill was unnecessary!
2011 int PDSSlot
= PotentialDeadStoreSlots
[j
];
2012 MachineInstr
* DeadStore
= MaybeDeadStores
[PDSSlot
];
2014 DOUT
<< "Removed dead store:\t" << *DeadStore
;
2015 InvalidateKills(*DeadStore
, TRI
, RegKills
, KillOps
);
2016 VRM
.RemoveMachineInstrFromMaps(DeadStore
);
2017 MBB
.erase(DeadStore
);
2018 MaybeDeadStores
[PDSSlot
] = NULL
;
2027 // If we have folded references to memory operands, make sure we clear all
2028 // physical registers that may contain the value of the spilled virtual
2030 SmallSet
<int, 2> FoldedSS
;
2031 for (tie(I
, End
) = VRM
.getFoldedVirts(&MI
); I
!= End
; ) {
2032 unsigned VirtReg
= I
->second
.first
;
2033 VirtRegMap::ModRef MR
= I
->second
.second
;
2034 DOUT
<< "Folded vreg: " << VirtReg
<< " MR: " << MR
;
2036 // MI2VirtMap be can updated which invalidate the iterator.
2037 // Increment the iterator first.
2039 int SS
= VRM
.getStackSlot(VirtReg
);
2040 if (SS
== VirtRegMap::NO_STACK_SLOT
)
2042 FoldedSS
.insert(SS
);
2043 DOUT
<< " - StackSlot: " << SS
<< "\n";
2045 // If this folded instruction is just a use, check to see if it's a
2046 // straight load from the virt reg slot.
2047 if ((MR
& VirtRegMap::isRef
) && !(MR
& VirtRegMap::isMod
)) {
2049 unsigned DestReg
= TII
->isLoadFromStackSlot(&MI
, FrameIdx
);
2050 if (DestReg
&& FrameIdx
== SS
) {
2051 // If this spill slot is available, turn it into a copy (or nothing)
2052 // instead of leaving it as a load!
2053 if (unsigned InReg
= Spills
.getSpillSlotOrReMatPhysReg(SS
)) {
2054 DOUT
<< "Promoted Load To Copy: " << MI
;
2055 if (DestReg
!= InReg
) {
2056 const TargetRegisterClass
*RC
= RegInfo
->getRegClass(VirtReg
);
2057 TII
->copyRegToReg(MBB
, &MI
, DestReg
, InReg
, RC
, RC
);
2058 MachineOperand
*DefMO
= MI
.findRegisterDefOperand(DestReg
);
2059 unsigned SubIdx
= DefMO
->getSubReg();
2060 // Revisit the copy so we make sure to notice the effects of the
2061 // operation on the destreg (either needing to RA it if it's
2062 // virtual or needing to clobber any values if it's physical).
2064 --NextMII
; // backtrack to the copy.
2065 // Propagate the sub-register index over.
2067 DefMO
= NextMII
->findRegisterDefOperand(DestReg
);
2068 DefMO
->setSubReg(SubIdx
);
2072 MachineOperand
*KillOpnd
= NextMII
->findRegisterUseOperand(InReg
);
2073 KillOpnd
->setIsKill();
2077 DOUT
<< "Removing now-noop copy: " << MI
;
2078 // Unset last kill since it's being reused.
2079 InvalidateKill(InReg
, TRI
, RegKills
, KillOps
);
2080 Spills
.disallowClobberPhysReg(InReg
);
2083 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
2084 VRM
.RemoveMachineInstrFromMaps(&MI
);
2087 goto ProcessNextInst
;
2090 unsigned PhysReg
= Spills
.getSpillSlotOrReMatPhysReg(SS
);
2091 SmallVector
<MachineInstr
*, 4> NewMIs
;
2093 TII
->unfoldMemoryOperand(MF
, &MI
, PhysReg
, false, false, NewMIs
)) {
2094 MBB
.insert(MII
, NewMIs
[0]);
2095 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
2096 VRM
.RemoveMachineInstrFromMaps(&MI
);
2099 --NextMII
; // backtrack to the unfolded instruction.
2101 goto ProcessNextInst
;
2106 // If this reference is not a use, any previous store is now dead.
2107 // Otherwise, the store to this stack slot is not dead anymore.
2108 MachineInstr
* DeadStore
= MaybeDeadStores
[SS
];
2110 bool isDead
= !(MR
& VirtRegMap::isRef
);
2111 MachineInstr
*NewStore
= NULL
;
2112 if (MR
& VirtRegMap::isModRef
) {
2113 unsigned PhysReg
= Spills
.getSpillSlotOrReMatPhysReg(SS
);
2114 SmallVector
<MachineInstr
*, 4> NewMIs
;
2115 // We can reuse this physreg as long as we are allowed to clobber
2116 // the value and there isn't an earlier def that has already clobbered
2119 !ReusedOperands
.isClobbered(PhysReg
) &&
2120 Spills
.canClobberPhysReg(PhysReg
) &&
2121 !TII
->isStoreToStackSlot(&MI
, SS
)) { // Not profitable!
2122 MachineOperand
*KillOpnd
=
2123 DeadStore
->findRegisterUseOperand(PhysReg
, true);
2124 // Note, if the store is storing a sub-register, it's possible the
2125 // super-register is needed below.
2126 if (KillOpnd
&& !KillOpnd
->getSubReg() &&
2127 TII
->unfoldMemoryOperand(MF
, &MI
, PhysReg
, false, true,NewMIs
)){
2128 MBB
.insert(MII
, NewMIs
[0]);
2129 NewStore
= NewMIs
[1];
2130 MBB
.insert(MII
, NewStore
);
2131 VRM
.addSpillSlotUse(SS
, NewStore
);
2132 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
2133 VRM
.RemoveMachineInstrFromMaps(&MI
);
2137 --NextMII
; // backtrack to the unfolded instruction.
2145 if (isDead
) { // Previous store is dead.
2146 // If we get here, the store is dead, nuke it now.
2147 DOUT
<< "Removed dead store:\t" << *DeadStore
;
2148 InvalidateKills(*DeadStore
, TRI
, RegKills
, KillOps
);
2149 VRM
.RemoveMachineInstrFromMaps(DeadStore
);
2150 MBB
.erase(DeadStore
);
2155 MaybeDeadStores
[SS
] = NULL
;
2157 // Treat this store as a spill merged into a copy. That makes the
2158 // stack slot value available.
2159 VRM
.virtFolded(VirtReg
, NewStore
, VirtRegMap::isMod
);
2160 goto ProcessNextInst
;
2164 // If the spill slot value is available, and this is a new definition of
2165 // the value, the value is not available anymore.
2166 if (MR
& VirtRegMap::isMod
) {
2167 // Notice that the value in this stack slot has been modified.
2168 Spills
.ModifyStackSlotOrReMat(SS
);
2170 // If this is *just* a mod of the value, check to see if this is just a
2171 // store to the spill slot (i.e. the spill got merged into the copy). If
2172 // so, realize that the vreg is available now, and add the store to the
2173 // MaybeDeadStore info.
2175 if (!(MR
& VirtRegMap::isRef
)) {
2176 if (unsigned SrcReg
= TII
->isStoreToStackSlot(&MI
, StackSlot
)) {
2177 assert(TargetRegisterInfo::isPhysicalRegister(SrcReg
) &&
2178 "Src hasn't been allocated yet?");
2180 if (CommuteToFoldReload(MBB
, MII
, VirtReg
, SrcReg
, StackSlot
,
2181 Spills
, RegKills
, KillOps
, TRI
, VRM
)) {
2182 NextMII
= next(MII
);
2184 goto ProcessNextInst
;
2187 // Okay, this is certainly a store of SrcReg to [StackSlot]. Mark
2188 // this as a potentially dead store in case there is a subsequent
2189 // store into the stack slot without a read from it.
2190 MaybeDeadStores
[StackSlot
] = &MI
;
2192 // If the stack slot value was previously available in some other
2193 // register, change it now. Otherwise, make the register
2194 // available in PhysReg.
2195 Spills
.addAvailable(StackSlot
, SrcReg
, MI
.killsRegister(SrcReg
));
2201 // Process all of the spilled defs.
2202 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
2203 MachineOperand
&MO
= MI
.getOperand(i
);
2204 if (!(MO
.isReg() && MO
.getReg() && MO
.isDef()))
2207 unsigned VirtReg
= MO
.getReg();
2208 if (!TargetRegisterInfo::isVirtualRegister(VirtReg
)) {
2209 // Check to see if this is a noop copy. If so, eliminate the
2210 // instruction before considering the dest reg to be changed.
2211 // Also check if it's copying from an "undef", if so, we can't
2212 // eliminate this or else the undef marker is lost and it will
2213 // confuses the scavenger. This is extremely rare.
2214 unsigned Src
, Dst
, SrcSR
, DstSR
;
2215 if (TII
->isMoveInstr(MI
, Src
, Dst
, SrcSR
, DstSR
) && Src
== Dst
&&
2216 !MI
.findRegisterUseOperand(Src
)->isUndef()) {
2218 DOUT
<< "Removing now-noop copy: " << MI
;
2219 SmallVector
<unsigned, 2> KillRegs
;
2220 InvalidateKills(MI
, TRI
, RegKills
, KillOps
, &KillRegs
);
2221 if (MO
.isDead() && !KillRegs
.empty()) {
2222 // Source register or an implicit super/sub-register use is killed.
2223 assert(KillRegs
[0] == Dst
||
2224 TRI
->isSubRegister(KillRegs
[0], Dst
) ||
2225 TRI
->isSuperRegister(KillRegs
[0], Dst
));
2226 // Last def is now dead.
2227 TransferDeadness(&MBB
, Dist
, Src
, RegKills
, KillOps
, VRM
);
2229 VRM
.RemoveMachineInstrFromMaps(&MI
);
2232 Spills
.disallowClobberPhysReg(VirtReg
);
2233 goto ProcessNextInst
;
2236 // If it's not a no-op copy, it clobbers the value in the destreg.
2237 Spills
.ClobberPhysReg(VirtReg
);
2238 ReusedOperands
.markClobbered(VirtReg
);
2240 // Check to see if this instruction is a load from a stack slot into
2241 // a register. If so, this provides the stack slot value in the reg.
2243 if (unsigned DestReg
= TII
->isLoadFromStackSlot(&MI
, FrameIdx
)) {
2244 assert(DestReg
== VirtReg
&& "Unknown load situation!");
2246 // If it is a folded reference, then it's not safe to clobber.
2247 bool Folded
= FoldedSS
.count(FrameIdx
);
2248 // Otherwise, if it wasn't available, remember that it is now!
2249 Spills
.addAvailable(FrameIdx
, DestReg
, !Folded
);
2250 goto ProcessNextInst
;
2256 unsigned SubIdx
= MO
.getSubReg();
2257 bool DoReMat
= VRM
.isReMaterialized(VirtReg
);
2259 ReMatDefs
.insert(&MI
);
2261 // The only vregs left are stack slot definitions.
2262 int StackSlot
= VRM
.getStackSlot(VirtReg
);
2263 const TargetRegisterClass
*RC
= RegInfo
->getRegClass(VirtReg
);
2265 // If this def is part of a two-address operand, make sure to execute
2266 // the store from the correct physical register.
2269 if (MI
.isRegTiedToUseOperand(i
, &TiedOp
)) {
2270 PhysReg
= MI
.getOperand(TiedOp
).getReg();
2272 unsigned SuperReg
= findSuperReg(RC
, PhysReg
, SubIdx
, TRI
);
2273 assert(SuperReg
&& TRI
->getSubReg(SuperReg
, SubIdx
) == PhysReg
&&
2274 "Can't find corresponding super-register!");
2278 PhysReg
= VRM
.getPhys(VirtReg
);
2279 if (ReusedOperands
.isClobbered(PhysReg
)) {
2280 // Another def has taken the assigned physreg. It must have been a
2281 // use&def which got it due to reuse. Undo the reuse!
2282 PhysReg
= ReusedOperands
.GetRegForReload(VirtReg
, PhysReg
, &MI
,
2283 Spills
, MaybeDeadStores
, RegKills
, KillOps
, VRM
);
2287 assert(PhysReg
&& "VR not assigned a physical register?");
2288 RegInfo
->setPhysRegUsed(PhysReg
);
2289 unsigned RReg
= SubIdx
? TRI
->getSubReg(PhysReg
, SubIdx
) : PhysReg
;
2290 ReusedOperands
.markClobbered(RReg
);
2291 MI
.getOperand(i
).setReg(RReg
);
2292 MI
.getOperand(i
).setSubReg(0);
2295 MachineInstr
*&LastStore
= MaybeDeadStores
[StackSlot
];
2296 SpillRegToStackSlot(MBB
, MII
, -1, PhysReg
, StackSlot
, RC
, true,
2297 LastStore
, Spills
, ReMatDefs
, RegKills
, KillOps
, VRM
);
2298 NextMII
= next(MII
);
2300 // Check to see if this is a noop copy. If so, eliminate the
2301 // instruction before considering the dest reg to be changed.
2303 unsigned Src
, Dst
, SrcSR
, DstSR
;
2304 if (TII
->isMoveInstr(MI
, Src
, Dst
, SrcSR
, DstSR
) && Src
== Dst
) {
2306 DOUT
<< "Removing now-noop copy: " << MI
;
2307 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
2308 VRM
.RemoveMachineInstrFromMaps(&MI
);
2311 UpdateKills(*LastStore
, TRI
, RegKills
, KillOps
);
2312 goto ProcessNextInst
;
2318 // Delete dead instructions without side effects.
2319 if (!Erased
&& !BackTracked
&& TII
->isDeadInstruction(&MI
)) {
2320 InvalidateKills(MI
, TRI
, RegKills
, KillOps
);
2321 VRM
.RemoveMachineInstrFromMaps(&MI
);
2326 DistanceMap
.insert(std::make_pair(&MI
, Dist
++));
2327 if (!Erased
&& !BackTracked
) {
2328 for (MachineBasicBlock::iterator II
= &MI
; II
!= NextMII
; ++II
)
2329 UpdateKills(*II
, TRI
, RegKills
, KillOps
);
2340 llvm::VirtRegRewriter
* llvm::createVirtRegRewriter() {
2341 switch (RewriterOpt
) {
2342 default: llvm_unreachable("Unreachable!");
2344 return new LocalRewriter();
2346 return new TrivialRewriter();