53#define DEBUG_TYPE "mips-delay-slot-filler"
55STATISTIC(FilledSlots,
"Number of delay slots filled");
56STATISTIC(UsefulSlots,
"Number of delay slots filled with instructions that"
60 "disable-mips-delay-filler",
62 cl::desc(
"Fill all delay slots with NOPs."),
66 "disable-mips-df-forward-search",
68 cl::desc(
"Disallow MIPS delay filler to search forward."),
72 "disable-mips-df-succbb-search",
74 cl::desc(
"Disallow MIPS delay filler to search successor basic blocks."),
78 "disable-mips-df-backward-search",
80 cl::desc(
"Disallow MIPS delay filler to search backward."),
95 cl::desc(
"MIPS Specific: Compact branch policy."),
97 "Do not use compact branches if possible."),
99 "Use compact branches where appropriate (default)."),
101 "Always use compact branches if possible.")));
133 bool isRegInSet(
const BitVector &RegSet,
unsigned Reg)
const;
140 class InspectMemInstr {
142 InspectMemInstr(
bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {}
143 virtual ~InspectMemInstr() =
default;
150 bool OrigSeenLoad =
false;
151 bool OrigSeenStore =
false;
152 bool SeenLoad =
false;
153 bool SeenStore =
false;
164 class NoMemInstr :
public InspectMemInstr {
166 NoMemInstr() : InspectMemInstr(
true) {}
173 class LoadFromStackOrConst :
public InspectMemInstr {
175 LoadFromStackOrConst() : InspectMemInstr(
false) {}
183 class MemDefsUses :
public InspectMemInstr {
195 bool updateDefsUses(
ValueType V,
bool MayStore);
206 bool SeenNoObjLoad =
false;
207 bool SeenNoObjStore =
false;
220 bool Changed =
false;
222 Changed |= runOnMachineBasicBlock(
MBB);
228 F.getRegInfo().invalidateLiveness();
235 MachineFunctionProperties::Property::NoVRegs);
254 bool delayHasHazard(
const MachineInstr &Candidate, RegDefsUses &RegDU,
255 InspectMemInstr &IM)
const;
259 template<
typename IterTy>
261 RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot,
262 IterTy &Filler)
const;
283 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
289 RegDefsUses &RegDU,
bool &HasMultipleSuccs,
290 BB2BrMap &
BrMap)
const;
292 bool terminateSearch(
const MachineInstr &Candidate)
const;
299char MipsDelaySlotFiller::ID = 0;
302 return MI->hasDelaySlot() && !
MI->isBundledWithSucc();
306 "Fill delay slot for MIPS",
false,
false)
309static
void insertDelayFiller(Iter Filler,
const BB2BrMap &
BrMap) {
327 if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg()))
333 "Shouldn't move an instruction with unallocatable registers across "
334 "basic block boundaries.");
347 update(
MI, 0,
MI.getDesc().getNumOperands());
357 update(
MI,
MI.getDesc().getNumOperands(),
MI.getNumOperands());
358 Defs.reset(Mips::AT);
368 if (
MI.definesRegister(Mips::RA,
nullptr) ||
369 MI.definesRegister(Mips::RA_64,
nullptr)) {
371 Defs.set(Mips::RA_64);
377 CallerSavedRegs.reset(Mips::ZERO);
378 CallerSavedRegs.reset(Mips::ZERO_64);
380 for (
const MCPhysReg *R =
TRI.getCalleeSavedRegs(
MI.getParent()->getParent());
383 CallerSavedRegs.reset(*AI);
385 Defs |= CallerSavedRegs;
391 for (
unsigned R : AllocSet.
set_bits())
395 AllocSet.
set(Mips::ZERO);
396 AllocSet.
set(Mips::ZERO_64);
398 Defs |= AllocSet.
flip();
405 for (
const auto &LI : S->liveins())
406 Uses.set(LI.PhysReg);
411 bool HasHazard =
false;
413 for (
unsigned I = Begin;
I !=
End; ++
I) {
417 if (checkRegDefsUses(NewDefs, NewUses, MO.
getReg(), MO.
isDef())) {
433 unsigned Reg,
bool IsDef)
const {
437 return (isRegInSet(Defs, Reg) || isRegInSet(
Uses, Reg));
442 return isRegInSet(Defs, Reg);
445bool RegDefsUses::isRegInSet(
const BitVector &RegSet,
unsigned Reg)
const {
448 if (RegSet.
test(*AI))
454 if (!
MI.mayStore() && !
MI.mayLoad())
460 OrigSeenLoad = SeenLoad;
461 OrigSeenStore = SeenStore;
462 SeenLoad |=
MI.mayLoad();
463 SeenStore |=
MI.mayStore();
467 if (
MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
468 ForbidMemInstr =
true;
472 return hasHazard_(
MI);
479 if (!
MI.hasOneMemOperand() || !(*
MI.memoperands_begin())->getPseudoValue())
483 (*
MI.memoperands_begin())->getPseudoValue()) {
484 if (isa<FixedStackPseudoSourceValue>(PSV))
486 return !PSV->isConstant(
nullptr) && !PSV->isStack();
493 : InspectMemInstr(
false), MFI(MFI_) {}
496 bool HasHazard =
false;
502 HasHazard |= updateDefsUses(VT,
MI.mayStore());
507 HasHazard =
MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
508 HasHazard |=
MI.mayLoad() || OrigSeenStore;
510 SeenNoObjLoad |=
MI.mayLoad();
511 SeenNoObjStore |=
MI.mayStore();
516bool MemDefsUses::updateDefsUses(
ValueType V,
bool MayStore) {
518 return !Defs.insert(V).second ||
Uses.count(V) || SeenNoObjStore ||
522 return Defs.count(V) || SeenNoObjStore;
528 if (!
MI.hasOneMemOperand())
531 auto & MMO = **
MI.memoperands_begin();
534 if (!PSV->isAliased(MFI))
540 if (
const Value *V = MMO.getValue()) {
544 for (
const Value *UValue : Objs) {
563 unsigned NewOpcode =
TII->getEquivalentCompactForm(Branch);
564 Branch =
TII->genInstrWithNewOpc(NewOpcode, Branch);
566 auto *ToErase = cast<MachineInstr>(&*std::next(Branch));
568 if (ToErase->shouldUpdateCallSiteInfo())
569 ToErase->getMF()->moveCallSiteInfo(ToErase, cast<MachineInstr>(&*Branch));
570 ToErase->eraseFromParent();
582 return Mips::BGEZALS_MM;
584 return Mips::BLTZALS_MM;
587 return Mips::JALS_MM;
589 return Mips::JALRS_MM;
590 case Mips::JALR16_MM:
591 return Mips::JALRS16_MM;
592 case Mips::TAILCALL_MM:
594 case Mips::TAILCALLREG:
595 return Mips::JR16_MM;
604 bool Changed =
false;
615 (
TM->getOptLevel() != CodeGenOptLevel::None) &&
621 !
TII->getEquivalentCompactForm(
I)) {
622 if (searchBackward(
MBB, *
I)) {
624 " in backwards search.\n");
626 }
else if (
I->isTerminator()) {
627 if (searchSuccBBs(
MBB,
I)) {
630 " in successor BB search.\n");
632 }
else if (searchForward(
MBB,
I)) {
634 " in forwards search.\n");
643 if (InMicroMipsMode &&
TII->getInstSizeInBytes(*std::next(DSI)) == 2 &&
670 if ((InMicroMipsMode ||
672 TII->getEquivalentCompactForm(
I)) {
673 I = replaceWithCompactBranch(
MBB,
I,
I->getDebugLoc());
681 TII->insertNop(
MBB, std::next(
I),
I->getDebugLoc());
690template <
typename IterTy>
692 IterTy
End, RegDefsUses &RegDU,
693 InspectMemInstr &IM, Iter Slot,
694 IterTy &Filler)
const {
695 for (IterTy
I = Begin;
I !=
End;) {
700 if (CurrI->isDebugInstr()) {
706 if (CurrI->isBundle()) {
710 RegDU.update(*CurrI, 0, CurrI->getNumOperands());
714 if (terminateSearch(*CurrI)) {
720 assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
721 "Cannot put calls, returns or branches in delay slot.");
723 if (CurrI->isKill()) {
724 CurrI->eraseFromParent();
728 if (delayHasHazard(*CurrI, RegDU, IM))
746 unsigned Opcode = (*Slot).getOpcode();
752 if (InMicroMipsMode &&
TII->getInstSizeInBytes(*CurrI) == 2 &&
753 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
754 Opcode == Mips::PseudoIndirectBranch_MM ||
755 Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
759 if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM ||
760 Opcode == Mips::MOVEP_MM))
779 RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
780 MemDefsUses MemDU(&Fn->getFrameInfo());
789 "slot using backwards search.\n");
793 MBB.
splice(std::next(SlotI), &
MBB, Filler.getReverse());
809 RegDU.setCallerSaved(*Slot);
811 if (!searchRange(
MBB, std::next(Slot),
MBB.
end(), RegDU, NM, Slot, Filler)) {
813 "slot using forwards search.\n");
834 bool HasMultipleSuccs =
false;
836 std::unique_ptr<InspectMemInstr> IM;
842 if (!examinePred(*Pred, *SuccBB, RegDU, HasMultipleSuccs,
BrMap))
847 RegDU.setUnallocatableRegs(*Fn);
851 if (HasMultipleSuccs) {
852 IM.
reset(
new LoadFromStackOrConst());
855 IM.reset(
new MemDefsUses(&MFI));
858 if (!searchRange(
MBB, SuccBB->
begin(), SuccBB->
end(), RegDU, *IM, Slot,
862 insertDelayFiller(Filler,
BrMap);
864 Filler->eraseFromParent();
875 auto &Prob = getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
877 B.succ_begin(),
B.succ_end(),
879 return Prob.getEdgeProbability(&B, Dst0) <
880 Prob.getEdgeProbability(&B, Dst1);
882 return S->
isEHPad() ? nullptr : S;
885std::pair<MipsInstrInfo::BranchType, MachineInstr *>
898 return std::make_pair(R,
nullptr);
906 return std::make_pair(R, BranchInstrs[0]);
909 assert((TrueBB == &Dst) || (FalseBB == &Dst));
925 bool &HasMultipleSuccs,
926 BB2BrMap &
BrMap)
const {
927 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
P =
928 getBranch(Pred, Succ);
937 HasMultipleSuccs =
true;
938 RegDU.addLiveOut(Pred, Succ);
945bool MipsDelaySlotFiller::delayHasHazard(
const MachineInstr &Candidate,
947 InspectMemInstr &IM)
const {
949 "KILL instructions should have been eliminated at this point.");
953 HasHazard |= IM.hasHazard(Candidate);
954 HasHazard |= RegDU.update(Candidate, 0, Candidate.
getNumOperands());
959bool MipsDelaySlotFiller::terminateSearch(
const MachineInstr &Candidate)
const {
968 return new MipsDelaySlotFiller();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
This file defines the DenseMap class.
static bool hasHazard(StateT State, function_ref< HazardFnResult(StateT &, const MachineInstr &)> IsHazard, function_ref< void(StateT &, const MachineInstr &)> UpdateState, const MachineBasicBlock *MBB, MachineBasicBlock::const_reverse_instr_iterator I, DenseSet< const MachineBasicBlock * > &Visited)
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
static bool hasUnoccupiedSlot(const MachineInstr *MI)
static cl::opt< bool > DisableDelaySlotFiller("disable-mips-delay-filler", cl::init(false), cl::desc("Fill all delay slots with NOPs."), cl::Hidden)
static cl::opt< bool > DisableBackwardSearch("disable-mips-df-backward-search", cl::init(false), cl::desc("Disallow MIPS delay filler to search backward."), cl::Hidden)
static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB)
This function adds registers Filler defines to MBB's live-in register list.
static cl::opt< bool > DisableSuccBBSearch("disable-mips-df-succbb-search", cl::init(true), cl::desc("Disallow MIPS delay filler to search successor basic blocks."), cl::Hidden)
static cl::opt< bool > DisableForwardSearch("disable-mips-df-forward-search", cl::init(true), cl::desc("Disallow MIPS delay filler to search forward."), cl::Hidden)
static cl::opt< CompactBranchPolicy > MipsCompactBranchPolicy("mips-compact-branches", cl::Optional, cl::init(CB_Optimal), cl::desc("MIPS Specific: Compact branch policy."), cl::values(clEnumValN(CB_Never, "never", "Do not use compact branches if possible."), clEnumValN(CB_Optimal, "optimal", "Use compact branches where appropriate (default)."), clEnumValN(CB_Always, "always", "Always use compact branches if possible.")))
@ CB_Never
The policy 'never' may in some circumstances or for some ISAs not be absolutely adhered to.
@ CB_Optimal
Optimal is the default and will produce compact branches when delay slots cannot be filled.
@ CB_Always
'always' may in some circumstances may not be absolutely adhered to there may not be a corresponding ...
static int getEquivalentCallShort(int Opcode)
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This file defines the PointerUnion class, which is a discriminated union of pointer types.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
bool test(unsigned Idx) const
iterator_range< const_set_bits_iterator > set_bits() const
FunctionPass class - This class is used to implement most global optimizations.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
MCRegAliasIterator enumerates all registers aliasing Reg.
Helper class for constructing bundles of MachineInstrs.
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
bool isEHPad() const
Returns true if the block is a landing pad.
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Instructions::iterator instr_iterator
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
void reset()
Reset the instance as if it was just created.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
bool isImplicitDef() const
bool isCall(QueryType Type=AnyInBundle) const
unsigned getNumOperands() const
Retuns the total number of operands.
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
bool inMicroMipsMode() const
const MipsInstrInfo * getInstrInfo() const override
const MipsRegisterInfo * getRegisterInfo() const override
bool isTargetNaCl() const
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Special value supplied for machine level alias analysis.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Primary interface to the complete machine description for the target machine.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC=nullptr) const
Returns a bitset indexed by register number indicating if a register is allocatable or not.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
LLVM Value Representation.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool isBasePlusOffsetMemoryAccess(unsigned Opcode, unsigned *AddrIdx, bool *IsStore=nullptr)
void initializeMipsDelaySlotFillerPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool baseRegNeedsLoadStoreMask(unsigned Reg)
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, const LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
FunctionPass * createMipsDelaySlotFillerPass()
createMipsDelaySlotFillerPass - Returns a pass that fills in delay slots in Mips MachineFunctions
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.