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) ||
MI.definesRegister(Mips::RA_64)) {
370 Defs.set(Mips::RA_64);
376 CallerSavedRegs.reset(Mips::ZERO);
377 CallerSavedRegs.reset(Mips::ZERO_64);
379 for (
const MCPhysReg *R =
TRI.getCalleeSavedRegs(
MI.getParent()->getParent());
382 CallerSavedRegs.reset(*AI);
384 Defs |= CallerSavedRegs;
390 for (
unsigned R : AllocSet.
set_bits())
394 AllocSet.
set(Mips::ZERO);
395 AllocSet.
set(Mips::ZERO_64);
397 Defs |= AllocSet.
flip();
404 for (
const auto &LI : S->liveins())
405 Uses.set(LI.PhysReg);
410 bool HasHazard =
false;
412 for (
unsigned I = Begin;
I !=
End; ++
I) {
416 if (checkRegDefsUses(NewDefs, NewUses, MO.
getReg(), MO.
isDef())) {
432 unsigned Reg,
bool IsDef)
const {
436 return (isRegInSet(Defs, Reg) || isRegInSet(
Uses, Reg));
441 return isRegInSet(Defs, Reg);
444bool RegDefsUses::isRegInSet(
const BitVector &RegSet,
unsigned Reg)
const {
447 if (RegSet.
test(*AI))
453 if (!
MI.mayStore() && !
MI.mayLoad())
459 OrigSeenLoad = SeenLoad;
460 OrigSeenStore = SeenStore;
461 SeenLoad |=
MI.mayLoad();
462 SeenStore |=
MI.mayStore();
466 if (
MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
467 ForbidMemInstr =
true;
471 return hasHazard_(
MI);
478 if (!
MI.hasOneMemOperand() || !(*
MI.memoperands_begin())->getPseudoValue())
482 (*
MI.memoperands_begin())->getPseudoValue()) {
483 if (isa<FixedStackPseudoSourceValue>(PSV))
485 return !PSV->isConstant(
nullptr) && !PSV->isStack();
492 : InspectMemInstr(
false), MFI(MFI_) {}
495 bool HasHazard =
false;
501 HasHazard |= updateDefsUses(VT,
MI.mayStore());
506 HasHazard =
MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
507 HasHazard |=
MI.mayLoad() || OrigSeenStore;
509 SeenNoObjLoad |=
MI.mayLoad();
510 SeenNoObjStore |=
MI.mayStore();
515bool MemDefsUses::updateDefsUses(
ValueType V,
bool MayStore) {
517 return !Defs.insert(V).second ||
Uses.count(V) || SeenNoObjStore ||
521 return Defs.count(V) || SeenNoObjStore;
527 if (!
MI.hasOneMemOperand())
530 auto & MMO = **
MI.memoperands_begin();
533 if (!PSV->isAliased(MFI))
539 if (
const Value *V = MMO.getValue()) {
543 for (
const Value *UValue : Objs) {
562 unsigned NewOpcode =
TII->getEquivalentCompactForm(Branch);
563 Branch =
TII->genInstrWithNewOpc(NewOpcode, Branch);
565 auto *ToErase = cast<MachineInstr>(&*std::next(Branch));
567 if (ToErase->shouldUpdateCallSiteInfo())
568 ToErase->getMF()->moveCallSiteInfo(ToErase, cast<MachineInstr>(&*Branch));
569 ToErase->eraseFromParent();
581 return Mips::BGEZALS_MM;
583 return Mips::BLTZALS_MM;
586 return Mips::JALS_MM;
588 return Mips::JALRS_MM;
589 case Mips::JALR16_MM:
590 return Mips::JALRS16_MM;
591 case Mips::TAILCALL_MM:
593 case Mips::TAILCALLREG:
594 return Mips::JR16_MM;
603 bool Changed =
false;
614 (
TM->getOptLevel() != CodeGenOptLevel::None) &&
620 !
TII->getEquivalentCompactForm(
I)) {
621 if (searchBackward(
MBB, *
I)) {
623 " in backwards search.\n");
625 }
else if (
I->isTerminator()) {
626 if (searchSuccBBs(
MBB,
I)) {
629 " in successor BB search.\n");
631 }
else if (searchForward(
MBB,
I)) {
633 " in forwards search.\n");
642 if (InMicroMipsMode &&
TII->getInstSizeInBytes(*std::next(DSI)) == 2 &&
669 if ((InMicroMipsMode ||
671 TII->getEquivalentCompactForm(
I)) {
672 I = replaceWithCompactBranch(
MBB,
I,
I->getDebugLoc());
680 TII->insertNop(
MBB, std::next(
I),
I->getDebugLoc());
689template <
typename IterTy>
691 IterTy
End, RegDefsUses &RegDU,
692 InspectMemInstr &IM, Iter Slot,
693 IterTy &Filler)
const {
694 for (IterTy
I = Begin;
I !=
End;) {
699 if (CurrI->isDebugInstr()) {
705 if (CurrI->isBundle()) {
709 RegDU.update(*CurrI, 0, CurrI->getNumOperands());
713 if (terminateSearch(*CurrI)) {
719 assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
720 "Cannot put calls, returns or branches in delay slot.");
722 if (CurrI->isKill()) {
723 CurrI->eraseFromParent();
727 if (delayHasHazard(*CurrI, RegDU, IM))
745 unsigned Opcode = (*Slot).getOpcode();
751 if (InMicroMipsMode &&
TII->getInstSizeInBytes(*CurrI) == 2 &&
752 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
753 Opcode == Mips::PseudoIndirectBranch_MM ||
754 Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
758 if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM ||
759 Opcode == Mips::MOVEP_MM))
778 RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
779 MemDefsUses MemDU(&Fn->getFrameInfo());
788 "slot using backwards search.\n");
792 MBB.
splice(std::next(SlotI), &
MBB, Filler.getReverse());
808 RegDU.setCallerSaved(*Slot);
810 if (!searchRange(
MBB, std::next(Slot),
MBB.
end(), RegDU, NM, Slot, Filler)) {
812 "slot using forwards search.\n");
833 bool HasMultipleSuccs =
false;
835 std::unique_ptr<InspectMemInstr> IM;
841 if (!examinePred(*Pred, *SuccBB, RegDU, HasMultipleSuccs,
BrMap))
846 RegDU.setUnallocatableRegs(*Fn);
850 if (HasMultipleSuccs) {
851 IM.
reset(
new LoadFromStackOrConst());
854 IM.reset(
new MemDefsUses(&MFI));
857 if (!searchRange(
MBB, SuccBB->
begin(), SuccBB->
end(), RegDU, *IM, Slot,
861 insertDelayFiller(Filler,
BrMap);
863 Filler->eraseFromParent();
874 auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
876 B.succ_begin(),
B.succ_end(),
878 return Prob.getEdgeProbability(&B, Dst0) <
879 Prob.getEdgeProbability(&B, Dst1);
881 return S->
isEHPad() ? nullptr : S;
884std::pair<MipsInstrInfo::BranchType, MachineInstr *>
897 return std::make_pair(R,
nullptr);
905 return std::make_pair(R, BranchInstrs[0]);
908 assert((TrueBB == &Dst) || (FalseBB == &Dst));
924 bool &HasMultipleSuccs,
925 BB2BrMap &
BrMap)
const {
926 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
P =
927 getBranch(Pred, Succ);
936 HasMultipleSuccs =
true;
937 RegDU.addLiveOut(Pred, Succ);
944bool MipsDelaySlotFiller::delayHasHazard(
const MachineInstr &Candidate,
946 InspectMemInstr &IM)
const {
948 "KILL instructions should have been eliminated at this point.");
952 HasHazard |= IM.hasHazard(Candidate);
953 HasHazard |= RegDU.update(Candidate, 0, Candidate.
getNumOperands());
958bool MipsDelaySlotFiller::terminateSearch(
const MachineInstr &Candidate)
const {
967 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.
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.
Iterator for intrusive lists based on ilist_node.
#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, 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.