1 //===-- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler ------------------===//
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 // Simple pass to fill delay slots with useful instructions.
12 //===----------------------------------------------------------------------===//
14 #include "MCTargetDesc/MipsMCNaCl.h"
16 #include "MipsInstrInfo.h"
17 #include "MipsTargetMachine.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/AliasAnalysis.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/MachineRegisterInfo.h"
27 #include "llvm/CodeGen/PseudoSourceValue.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
35 #define DEBUG_TYPE "delay-slot-filler"
37 STATISTIC(FilledSlots
, "Number of delay slots filled");
38 STATISTIC(UsefulSlots
, "Number of delay slots filled with instructions that"
41 static cl::opt
<bool> DisableDelaySlotFiller(
42 "disable-mips-delay-filler",
44 cl::desc("Fill all delay slots with NOPs."),
47 static cl::opt
<bool> DisableForwardSearch(
48 "disable-mips-df-forward-search",
50 cl::desc("Disallow MIPS delay filler to search forward."),
53 static cl::opt
<bool> DisableSuccBBSearch(
54 "disable-mips-df-succbb-search",
56 cl::desc("Disallow MIPS delay filler to search successor basic blocks."),
59 static cl::opt
<bool> DisableBackwardSearch(
60 "disable-mips-df-backward-search",
62 cl::desc("Disallow MIPS delay filler to search backward."),
66 typedef MachineBasicBlock::iterator Iter
;
67 typedef MachineBasicBlock::reverse_iterator ReverseIter
;
68 typedef SmallDenseMap
<MachineBasicBlock
*, MachineInstr
*, 2> BB2BrMap
;
72 RegDefsUses(TargetMachine
&TM
);
73 void init(const MachineInstr
&MI
);
75 /// This function sets all caller-saved registers in Defs.
76 void setCallerSaved(const MachineInstr
&MI
);
78 /// This function sets all unallocatable registers in Defs.
79 void setUnallocatableRegs(const MachineFunction
&MF
);
81 /// Set bits in Uses corresponding to MBB's live-out registers except for
82 /// the registers that are live-in to SuccBB.
83 void addLiveOut(const MachineBasicBlock
&MBB
,
84 const MachineBasicBlock
&SuccBB
);
86 bool update(const MachineInstr
&MI
, unsigned Begin
, unsigned End
);
89 bool checkRegDefsUses(BitVector
&NewDefs
, BitVector
&NewUses
, unsigned Reg
,
92 /// Returns true if Reg or its alias is in RegSet.
93 bool isRegInSet(const BitVector
&RegSet
, unsigned Reg
) const;
95 const TargetRegisterInfo
&TRI
;
99 /// Base class for inspecting loads and stores.
100 class InspectMemInstr
{
102 InspectMemInstr(bool ForbidMemInstr_
)
103 : OrigSeenLoad(false), OrigSeenStore(false), SeenLoad(false),
104 SeenStore(false), ForbidMemInstr(ForbidMemInstr_
) {}
106 /// Return true if MI cannot be moved to delay slot.
107 bool hasHazard(const MachineInstr
&MI
);
109 virtual ~InspectMemInstr() {}
112 /// Flags indicating whether loads or stores have been seen.
113 bool OrigSeenLoad
, OrigSeenStore
, SeenLoad
, SeenStore
;
115 /// Memory instructions are not allowed to move to delay slot if this flag
120 virtual bool hasHazard_(const MachineInstr
&MI
) = 0;
123 /// This subclass rejects any memory instructions.
124 class NoMemInstr
: public InspectMemInstr
{
126 NoMemInstr() : InspectMemInstr(true) {}
128 bool hasHazard_(const MachineInstr
&MI
) override
{ return true; }
131 /// This subclass accepts loads from stacks and constant loads.
132 class LoadFromStackOrConst
: public InspectMemInstr
{
134 LoadFromStackOrConst() : InspectMemInstr(false) {}
136 bool hasHazard_(const MachineInstr
&MI
) override
;
139 /// This subclass uses memory dependence information to determine whether a
140 /// memory instruction can be moved to a delay slot.
141 class MemDefsUses
: public InspectMemInstr
{
143 MemDefsUses(const MachineFrameInfo
*MFI
);
146 typedef PointerUnion
<const Value
*, const PseudoSourceValue
*> ValueType
;
148 bool hasHazard_(const MachineInstr
&MI
) override
;
150 /// Update Defs and Uses. Return true if there exist dependences that
151 /// disqualify the delay slot candidate between V and values in Uses and
153 bool updateDefsUses(ValueType V
, bool MayStore
);
155 /// Get the list of underlying objects of MI's memory operand.
156 bool getUnderlyingObjects(const MachineInstr
&MI
,
157 SmallVectorImpl
<ValueType
> &Objects
) const;
159 const MachineFrameInfo
*MFI
;
160 SmallPtrSet
<ValueType
, 4> Uses
, Defs
;
162 /// Flags indicating whether loads or stores with no underlying objects have
164 bool SeenNoObjLoad
, SeenNoObjStore
;
167 class Filler
: public MachineFunctionPass
{
169 Filler(TargetMachine
&tm
)
170 : MachineFunctionPass(ID
), TM(tm
) { }
172 const char *getPassName() const override
{
173 return "Mips Delay Slot Filler";
176 bool runOnMachineFunction(MachineFunction
&F
) override
{
177 bool Changed
= false;
178 for (MachineFunction::iterator FI
= F
.begin(), FE
= F
.end();
180 Changed
|= runOnMachineBasicBlock(*FI
);
182 // This pass invalidates liveness information when it reorders
183 // instructions to fill delay slot. Without this, -verify-machineinstrs
186 F
.getRegInfo().invalidateLiveness();
191 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
192 AU
.addRequired
<MachineBranchProbabilityInfo
>();
193 MachineFunctionPass::getAnalysisUsage(AU
);
197 bool runOnMachineBasicBlock(MachineBasicBlock
&MBB
);
199 Iter
replaceWithCompactBranch(MachineBasicBlock
&MBB
,
200 Iter Branch
, DebugLoc DL
);
202 /// This function checks if it is valid to move Candidate to the delay slot
203 /// and returns true if it isn't. It also updates memory and register
204 /// dependence information.
205 bool delayHasHazard(const MachineInstr
&Candidate
, RegDefsUses
&RegDU
,
206 InspectMemInstr
&IM
) const;
208 /// This function searches range [Begin, End) for an instruction that can be
209 /// moved to the delay slot. Returns true on success.
210 template<typename IterTy
>
211 bool searchRange(MachineBasicBlock
&MBB
, IterTy Begin
, IterTy End
,
212 RegDefsUses
&RegDU
, InspectMemInstr
&IM
,
213 IterTy
&Filler
, Iter Slot
) const;
215 /// This function searches in the backward direction for an instruction that
216 /// can be moved to the delay slot. Returns true on success.
217 bool searchBackward(MachineBasicBlock
&MBB
, Iter Slot
) const;
219 /// This function searches MBB in the forward direction for an instruction
220 /// that can be moved to the delay slot. Returns true on success.
221 bool searchForward(MachineBasicBlock
&MBB
, Iter Slot
) const;
223 /// This function searches one of MBB's successor blocks for an instruction
224 /// that can be moved to the delay slot and inserts clones of the
225 /// instruction into the successor's predecessor blocks.
226 bool searchSuccBBs(MachineBasicBlock
&MBB
, Iter Slot
) const;
228 /// Pick a successor block of MBB. Return NULL if MBB doesn't have a
229 /// successor block that is not a landing pad.
230 MachineBasicBlock
*selectSuccBB(MachineBasicBlock
&B
) const;
232 /// This function analyzes MBB and returns an instruction with an unoccupied
233 /// slot that branches to Dst.
234 std::pair
<MipsInstrInfo::BranchType
, MachineInstr
*>
235 getBranch(MachineBasicBlock
&MBB
, const MachineBasicBlock
&Dst
) const;
237 /// Examine Pred and see if it is possible to insert an instruction into
238 /// one of its branches delay slot or its end.
239 bool examinePred(MachineBasicBlock
&Pred
, const MachineBasicBlock
&Succ
,
240 RegDefsUses
&RegDU
, bool &HasMultipleSuccs
,
241 BB2BrMap
&BrMap
) const;
243 bool terminateSearch(const MachineInstr
&Candidate
) const;
250 } // end of anonymous namespace
252 static bool hasUnoccupiedSlot(const MachineInstr
*MI
) {
253 return MI
->hasDelaySlot() && !MI
->isBundledWithSucc();
256 /// This function inserts clones of Filler into predecessor blocks.
257 static void insertDelayFiller(Iter Filler
, const BB2BrMap
&BrMap
) {
258 MachineFunction
*MF
= Filler
->getParent()->getParent();
260 for (BB2BrMap::const_iterator I
= BrMap
.begin(); I
!= BrMap
.end(); ++I
) {
262 MIBundleBuilder(I
->second
).append(MF
->CloneMachineInstr(&*Filler
));
265 I
->first
->insert(I
->first
->end(), MF
->CloneMachineInstr(&*Filler
));
270 /// This function adds registers Filler defines to MBB's live-in register list.
271 static void addLiveInRegs(Iter Filler
, MachineBasicBlock
&MBB
) {
272 for (unsigned I
= 0, E
= Filler
->getNumOperands(); I
!= E
; ++I
) {
273 const MachineOperand
&MO
= Filler
->getOperand(I
);
276 if (!MO
.isReg() || !MO
.isDef() || !(R
= MO
.getReg()))
280 const MachineFunction
&MF
= *MBB
.getParent();
281 assert(MF
.getTarget()
284 ->getAllocatableSet(MF
)
286 "Shouldn't move an instruction with unallocatable registers across "
287 "basic block boundaries.");
290 if (!MBB
.isLiveIn(R
))
295 RegDefsUses::RegDefsUses(TargetMachine
&TM
)
296 : TRI(*TM
.getSubtargetImpl()->getRegisterInfo()),
297 Defs(TRI
.getNumRegs(), false), Uses(TRI
.getNumRegs(), false) {}
299 void RegDefsUses::init(const MachineInstr
&MI
) {
300 // Add all register operands which are explicit and non-variadic.
301 update(MI
, 0, MI
.getDesc().getNumOperands());
303 // If MI is a call, add RA to Defs to prevent users of RA from going into
308 // Add all implicit register operands of branch instructions except
311 update(MI
, MI
.getDesc().getNumOperands(), MI
.getNumOperands());
312 Defs
.reset(Mips::AT
);
316 void RegDefsUses::setCallerSaved(const MachineInstr
&MI
) {
319 // If MI is a call, add all caller-saved registers to Defs.
320 BitVector
CallerSavedRegs(TRI
.getNumRegs(), true);
322 CallerSavedRegs
.reset(Mips::ZERO
);
323 CallerSavedRegs
.reset(Mips::ZERO_64
);
325 for (const MCPhysReg
*R
= TRI
.getCalleeSavedRegs(); *R
; ++R
)
326 for (MCRegAliasIterator
AI(*R
, &TRI
, true); AI
.isValid(); ++AI
)
327 CallerSavedRegs
.reset(*AI
);
329 Defs
|= CallerSavedRegs
;
332 void RegDefsUses::setUnallocatableRegs(const MachineFunction
&MF
) {
333 BitVector AllocSet
= TRI
.getAllocatableSet(MF
);
335 for (int R
= AllocSet
.find_first(); R
!= -1; R
= AllocSet
.find_next(R
))
336 for (MCRegAliasIterator
AI(R
, &TRI
, false); AI
.isValid(); ++AI
)
339 AllocSet
.set(Mips::ZERO
);
340 AllocSet
.set(Mips::ZERO_64
);
342 Defs
|= AllocSet
.flip();
345 void RegDefsUses::addLiveOut(const MachineBasicBlock
&MBB
,
346 const MachineBasicBlock
&SuccBB
) {
347 for (MachineBasicBlock::const_succ_iterator SI
= MBB
.succ_begin(),
348 SE
= MBB
.succ_end(); SI
!= SE
; ++SI
)
350 for (MachineBasicBlock::livein_iterator LI
= (*SI
)->livein_begin(),
351 LE
= (*SI
)->livein_end(); LI
!= LE
; ++LI
)
355 bool RegDefsUses::update(const MachineInstr
&MI
, unsigned Begin
, unsigned End
) {
356 BitVector
NewDefs(TRI
.getNumRegs()), NewUses(TRI
.getNumRegs());
357 bool HasHazard
= false;
359 for (unsigned I
= Begin
; I
!= End
; ++I
) {
360 const MachineOperand
&MO
= MI
.getOperand(I
);
362 if (MO
.isReg() && MO
.getReg())
363 HasHazard
|= checkRegDefsUses(NewDefs
, NewUses
, MO
.getReg(), MO
.isDef());
372 bool RegDefsUses::checkRegDefsUses(BitVector
&NewDefs
, BitVector
&NewUses
,
373 unsigned Reg
, bool IsDef
) const {
376 // check whether Reg has already been defined or used.
377 return (isRegInSet(Defs
, Reg
) || isRegInSet(Uses
, Reg
));
381 // check whether Reg has already been defined.
382 return isRegInSet(Defs
, Reg
);
385 bool RegDefsUses::isRegInSet(const BitVector
&RegSet
, unsigned Reg
) const {
386 // Check Reg and all aliased Registers.
387 for (MCRegAliasIterator
AI(Reg
, &TRI
, true); AI
.isValid(); ++AI
)
388 if (RegSet
.test(*AI
))
393 bool InspectMemInstr::hasHazard(const MachineInstr
&MI
) {
394 if (!MI
.mayStore() && !MI
.mayLoad())
400 OrigSeenLoad
= SeenLoad
;
401 OrigSeenStore
= SeenStore
;
402 SeenLoad
|= MI
.mayLoad();
403 SeenStore
|= MI
.mayStore();
405 // If MI is an ordered or volatile memory reference, disallow moving
406 // subsequent loads and stores to delay slot.
407 if (MI
.hasOrderedMemoryRef() && (OrigSeenLoad
|| OrigSeenStore
)) {
408 ForbidMemInstr
= true;
412 return hasHazard_(MI
);
415 bool LoadFromStackOrConst::hasHazard_(const MachineInstr
&MI
) {
419 if (!MI
.hasOneMemOperand() || !(*MI
.memoperands_begin())->getPseudoValue())
422 if (const PseudoSourceValue
*PSV
=
423 (*MI
.memoperands_begin())->getPseudoValue()) {
424 if (isa
<FixedStackPseudoSourceValue
>(PSV
))
426 return !PSV
->isConstant(nullptr) && PSV
!= PseudoSourceValue::getStack();
432 MemDefsUses::MemDefsUses(const MachineFrameInfo
*MFI_
)
433 : InspectMemInstr(false), MFI(MFI_
), SeenNoObjLoad(false),
434 SeenNoObjStore(false) {}
436 bool MemDefsUses::hasHazard_(const MachineInstr
&MI
) {
437 bool HasHazard
= false;
438 SmallVector
<ValueType
, 4> Objs
;
440 // Check underlying object list.
441 if (getUnderlyingObjects(MI
, Objs
)) {
442 for (SmallVectorImpl
<ValueType
>::const_iterator I
= Objs
.begin();
443 I
!= Objs
.end(); ++I
)
444 HasHazard
|= updateDefsUses(*I
, MI
.mayStore());
449 // No underlying objects found.
450 HasHazard
= MI
.mayStore() && (OrigSeenLoad
|| OrigSeenStore
);
451 HasHazard
|= MI
.mayLoad() || OrigSeenStore
;
453 SeenNoObjLoad
|= MI
.mayLoad();
454 SeenNoObjStore
|= MI
.mayStore();
459 bool MemDefsUses::updateDefsUses(ValueType V
, bool MayStore
) {
461 return !Defs
.insert(V
).second
|| Uses
.count(V
) || SeenNoObjStore
||
465 return Defs
.count(V
) || SeenNoObjStore
;
469 getUnderlyingObjects(const MachineInstr
&MI
,
470 SmallVectorImpl
<ValueType
> &Objects
) const {
471 if (!MI
.hasOneMemOperand() ||
472 (!(*MI
.memoperands_begin())->getValue() &&
473 !(*MI
.memoperands_begin())->getPseudoValue()))
476 if (const PseudoSourceValue
*PSV
=
477 (*MI
.memoperands_begin())->getPseudoValue()) {
478 if (!PSV
->isAliased(MFI
))
480 Objects
.push_back(PSV
);
484 const Value
*V
= (*MI
.memoperands_begin())->getValue();
486 SmallVector
<Value
*, 4> Objs
;
487 GetUnderlyingObjects(const_cast<Value
*>(V
), Objs
);
489 for (SmallVectorImpl
<Value
*>::iterator I
= Objs
.begin(), E
= Objs
.end();
491 if (!isIdentifiedObject(V
))
494 Objects
.push_back(*I
);
500 // Replace Branch with the compact branch instruction.
501 Iter
Filler::replaceWithCompactBranch(MachineBasicBlock
&MBB
,
502 Iter Branch
, DebugLoc DL
) {
503 const MipsInstrInfo
*TII
= static_cast<const MipsInstrInfo
*>(
504 TM
.getSubtargetImpl()->getInstrInfo());
507 (((unsigned) Branch
->getOpcode()) == Mips::BEQ
) ? Mips::BEQZC_MM
510 const MCInstrDesc
&NewDesc
= TII
->get(NewOpcode
);
511 MachineInstrBuilder MIB
= BuildMI(MBB
, Branch
, DL
, NewDesc
);
513 MIB
.addReg(Branch
->getOperand(0).getReg());
514 MIB
.addMBB(Branch
->getOperand(2).getMBB());
516 Iter tmpIter
= Branch
;
517 Branch
= std::prev(Branch
);
523 // For given opcode returns opcode of corresponding instruction with short
525 static int getEquivalentCallShort(int Opcode
) {
528 return Mips::BGEZALS_MM
;
530 return Mips::BLTZALS_MM
;
532 return Mips::JALS_MM
;
534 return Mips::JALRS_MM
;
535 case Mips::JALR16_MM
:
536 return Mips::JALRS16_MM
;
538 llvm_unreachable("Unexpected call instruction for microMIPS.");
542 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
543 /// We assume there is only one delay slot per delayed instruction.
544 bool Filler::runOnMachineBasicBlock(MachineBasicBlock
&MBB
) {
545 bool Changed
= false;
546 bool InMicroMipsMode
= TM
.getSubtarget
<MipsSubtarget
>().inMicroMipsMode();
547 const MipsInstrInfo
*TII
=
548 static_cast<const MipsInstrInfo
*>(TM
.getSubtargetImpl()->getInstrInfo());
550 for (Iter I
= MBB
.begin(); I
!= MBB
.end(); ++I
) {
551 if (!hasUnoccupiedSlot(&*I
))
557 // Delay slot filling is disabled at -O0.
558 if (!DisableDelaySlotFiller
&& (TM
.getOptLevel() != CodeGenOpt::None
)) {
561 if (searchBackward(MBB
, I
)) {
563 } else if (I
->isTerminator()) {
564 if (searchSuccBBs(MBB
, I
)) {
567 } else if (searchForward(MBB
, I
)) {
572 // Get instruction with delay slot.
573 MachineBasicBlock::instr_iterator
DSI(I
);
575 if (InMicroMipsMode
&& TII
->GetInstSizeInBytes(std::next(DSI
)) == 2 &&
577 // If instruction in delay slot is 16b change opcode to
578 // corresponding instruction with short delay slot.
579 DSI
->setDesc(TII
->get(getEquivalentCallShort(DSI
->getOpcode())));
586 // If instruction is BEQ or BNE with one ZERO register, then instead of
587 // adding NOP replace this instruction with the corresponding compact
588 // branch instruction, i.e. BEQZC or BNEZC.
589 unsigned Opcode
= I
->getOpcode();
590 if (InMicroMipsMode
&&
591 (Opcode
== Mips::BEQ
|| Opcode
== Mips::BNE
) &&
592 ((unsigned) I
->getOperand(1).getReg()) == Mips::ZERO
) {
594 I
= replaceWithCompactBranch(MBB
, I
, I
->getDebugLoc());
597 // Bundle the NOP to the instruction with the delay slot.
598 BuildMI(MBB
, std::next(I
), I
->getDebugLoc(), TII
->get(Mips::NOP
));
599 MIBundleBuilder(MBB
, I
, std::next(I
, 2));
606 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
607 /// slots in Mips MachineFunctions
608 FunctionPass
*llvm::createMipsDelaySlotFillerPass(MipsTargetMachine
&tm
) {
609 return new Filler(tm
);
612 template<typename IterTy
>
613 bool Filler::searchRange(MachineBasicBlock
&MBB
, IterTy Begin
, IterTy End
,
614 RegDefsUses
&RegDU
, InspectMemInstr
& IM
,
615 IterTy
&Filler
, Iter Slot
) const {
616 for (IterTy I
= Begin
; I
!= End
; ++I
) {
618 if (I
->isDebugValue())
621 if (terminateSearch(*I
))
624 assert((!I
->isCall() && !I
->isReturn() && !I
->isBranch()) &&
625 "Cannot put calls, returns or branches in delay slot.");
627 if (delayHasHazard(*I
, RegDU
, IM
))
630 if (TM
.getSubtarget
<MipsSubtarget
>().isTargetNaCl()) {
631 // In NaCl, instructions that must be masked are forbidden in delay slots.
632 // We only check for loads, stores and SP changes. Calls, returns and
633 // branches are not checked because non-NaCl targets never put them in
636 if ((isBasePlusOffsetMemoryAccess(I
->getOpcode(), &AddrIdx
) &&
637 baseRegNeedsLoadStoreMask(I
->getOperand(AddrIdx
).getReg())) ||
638 I
->modifiesRegister(Mips::SP
,
639 TM
.getSubtargetImpl()->getRegisterInfo()))
643 bool InMicroMipsMode
= TM
.getSubtarget
<MipsSubtarget
>().inMicroMipsMode();
644 const MipsInstrInfo
*TII
= static_cast<const MipsInstrInfo
*>(
645 TM
.getSubtargetImpl()->getInstrInfo());
646 unsigned Opcode
= (*Slot
).getOpcode();
647 if (InMicroMipsMode
&& TII
->GetInstSizeInBytes(&(*I
)) == 2 &&
648 (Opcode
== Mips::JR
|| Opcode
== Mips::PseudoIndirectBranch
||
649 Opcode
== Mips::PseudoReturn
))
659 bool Filler::searchBackward(MachineBasicBlock
&MBB
, Iter Slot
) const {
660 if (DisableBackwardSearch
)
663 RegDefsUses
RegDU(TM
);
664 MemDefsUses
MemDU(MBB
.getParent()->getFrameInfo());
669 if (!searchRange(MBB
, ReverseIter(Slot
), MBB
.rend(), RegDU
, MemDU
, Filler
,
673 MBB
.splice(std::next(Slot
), &MBB
, std::next(Filler
).base());
674 MIBundleBuilder(MBB
, Slot
, std::next(Slot
, 2));
679 bool Filler::searchForward(MachineBasicBlock
&MBB
, Iter Slot
) const {
680 // Can handle only calls.
681 if (DisableForwardSearch
|| !Slot
->isCall())
684 RegDefsUses
RegDU(TM
);
688 RegDU
.setCallerSaved(*Slot
);
690 if (!searchRange(MBB
, std::next(Slot
), MBB
.end(), RegDU
, NM
, Filler
, Slot
))
693 MBB
.splice(std::next(Slot
), &MBB
, Filler
);
694 MIBundleBuilder(MBB
, Slot
, std::next(Slot
, 2));
699 bool Filler::searchSuccBBs(MachineBasicBlock
&MBB
, Iter Slot
) const {
700 if (DisableSuccBBSearch
)
703 MachineBasicBlock
*SuccBB
= selectSuccBB(MBB
);
708 RegDefsUses
RegDU(TM
);
709 bool HasMultipleSuccs
= false;
711 std::unique_ptr
<InspectMemInstr
> IM
;
714 // Iterate over SuccBB's predecessor list.
715 for (MachineBasicBlock::pred_iterator PI
= SuccBB
->pred_begin(),
716 PE
= SuccBB
->pred_end(); PI
!= PE
; ++PI
)
717 if (!examinePred(**PI
, *SuccBB
, RegDU
, HasMultipleSuccs
, BrMap
))
720 // Do not allow moving instructions which have unallocatable register operands
721 // across basic block boundaries.
722 RegDU
.setUnallocatableRegs(*MBB
.getParent());
724 // Only allow moving loads from stack or constants if any of the SuccBB's
725 // predecessors have multiple successors.
726 if (HasMultipleSuccs
) {
727 IM
.reset(new LoadFromStackOrConst());
729 const MachineFrameInfo
*MFI
= MBB
.getParent()->getFrameInfo();
730 IM
.reset(new MemDefsUses(MFI
));
733 if (!searchRange(MBB
, SuccBB
->begin(), SuccBB
->end(), RegDU
, *IM
, Filler
,
737 insertDelayFiller(Filler
, BrMap
);
738 addLiveInRegs(Filler
, *SuccBB
);
739 Filler
->eraseFromParent();
744 MachineBasicBlock
*Filler::selectSuccBB(MachineBasicBlock
&B
) const {
748 // Select the successor with the larget edge weight.
749 auto &Prob
= getAnalysis
<MachineBranchProbabilityInfo
>();
750 MachineBasicBlock
*S
= *std::max_element(B
.succ_begin(), B
.succ_end(),
751 [&](const MachineBasicBlock
*Dst0
,
752 const MachineBasicBlock
*Dst1
) {
753 return Prob
.getEdgeWeight(&B
, Dst0
) < Prob
.getEdgeWeight(&B
, Dst1
);
755 return S
->isLandingPad() ? nullptr : S
;
758 std::pair
<MipsInstrInfo::BranchType
, MachineInstr
*>
759 Filler::getBranch(MachineBasicBlock
&MBB
, const MachineBasicBlock
&Dst
) const {
760 const MipsInstrInfo
*TII
=
761 static_cast<const MipsInstrInfo
*>(TM
.getSubtargetImpl()->getInstrInfo());
762 MachineBasicBlock
*TrueBB
= nullptr, *FalseBB
= nullptr;
763 SmallVector
<MachineInstr
*, 2> BranchInstrs
;
764 SmallVector
<MachineOperand
, 2> Cond
;
766 MipsInstrInfo::BranchType R
=
767 TII
->AnalyzeBranch(MBB
, TrueBB
, FalseBB
, Cond
, false, BranchInstrs
);
769 if ((R
== MipsInstrInfo::BT_None
) || (R
== MipsInstrInfo::BT_NoBranch
))
770 return std::make_pair(R
, nullptr);
772 if (R
!= MipsInstrInfo::BT_CondUncond
) {
773 if (!hasUnoccupiedSlot(BranchInstrs
[0]))
774 return std::make_pair(MipsInstrInfo::BT_None
, nullptr);
776 assert(((R
!= MipsInstrInfo::BT_Uncond
) || (TrueBB
== &Dst
)));
778 return std::make_pair(R
, BranchInstrs
[0]);
781 assert((TrueBB
== &Dst
) || (FalseBB
== &Dst
));
783 // Examine the conditional branch. See if its slot is occupied.
784 if (hasUnoccupiedSlot(BranchInstrs
[0]))
785 return std::make_pair(MipsInstrInfo::BT_Cond
, BranchInstrs
[0]);
787 // If that fails, try the unconditional branch.
788 if (hasUnoccupiedSlot(BranchInstrs
[1]) && (FalseBB
== &Dst
))
789 return std::make_pair(MipsInstrInfo::BT_Uncond
, BranchInstrs
[1]);
791 return std::make_pair(MipsInstrInfo::BT_None
, nullptr);
794 bool Filler::examinePred(MachineBasicBlock
&Pred
, const MachineBasicBlock
&Succ
,
795 RegDefsUses
&RegDU
, bool &HasMultipleSuccs
,
796 BB2BrMap
&BrMap
) const {
797 std::pair
<MipsInstrInfo::BranchType
, MachineInstr
*> P
=
798 getBranch(Pred
, Succ
);
800 // Return if either getBranch wasn't able to analyze the branches or there
801 // were no branches with unoccupied slots.
802 if (P
.first
== MipsInstrInfo::BT_None
)
805 if ((P
.first
!= MipsInstrInfo::BT_Uncond
) &&
806 (P
.first
!= MipsInstrInfo::BT_NoBranch
)) {
807 HasMultipleSuccs
= true;
808 RegDU
.addLiveOut(Pred
, Succ
);
811 BrMap
[&Pred
] = P
.second
;
815 bool Filler::delayHasHazard(const MachineInstr
&Candidate
, RegDefsUses
&RegDU
,
816 InspectMemInstr
&IM
) const {
817 bool HasHazard
= (Candidate
.isImplicitDef() || Candidate
.isKill());
819 HasHazard
|= IM
.hasHazard(Candidate
);
820 HasHazard
|= RegDU
.update(Candidate
, 0, Candidate
.getNumOperands());
825 bool Filler::terminateSearch(const MachineInstr
&Candidate
) const {
826 return (Candidate
.isTerminator() || Candidate
.isCall() ||
827 Candidate
.isPosition() || Candidate
.isInlineAsm() ||
828 Candidate
.hasUnmodeledSideEffects());