#include "Mips.h"
#include "MipsInstrInfo.h"
#include "MipsSubtarget.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachinePassManager.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/Analysis.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
#include <iterator>
#include <memory>
#include <utility>

Macros
#define	DEBUG_TYPE "mips-delay-slot-filler"

Functions
	STATISTIC (FilledSlots, "Number of delay slots filled")
	STATISTIC (UsefulSlots, "Number of delay slots filled with instructions that" " are not NOP.")
	STATISTIC (R5900ShortLoopNops, "Number of delay slots left as NOP for R5900 " "short loop fix")
static bool	hasUnoccupiedSlot (const MachineInstr *MI)
static bool	isR5900ShortLoopBranch (const MachineInstr *MI, const MachineBasicBlock &MBB)
	Check if a branch is a short backward loop that triggers the R5900 erratum.
	INITIALIZE_PASS (MipsDelaySlotFillerLegacy, DEBUG_TYPE, "Fill delay slot for MIPS", false, false) static void insertDelayFiller(Iter Filler
	This function inserts clones of Filler into predecessor blocks.
	for (const auto &I :BrMap)
static void	addLiveInRegs (Iter Filler, MachineBasicBlock &MBB)
	This function adds registers Filler defines to MBB's live-in register list.
static Iter	replaceWithCompactBranch (MachineBasicBlock &MBB, Iter Branch, const DebugLoc &DL)
static int	getEquivalentCallShort (int Opcode)
static bool	terminateSearch (const MachineInstr &Candidate)
static bool	delayExposesHazard (const BranchInformation &BranchInfo, const MachineInstr &Candidate, function_ref< bool(const MachineInstr &, const MachineInstr &)> IsSafe)
	Returns true if putting the candidate in the delay slot could let the branch target, or the instruction after the slot, read its result too early, or if those cannot be determined.
static bool	delayHasHazard (const MipsSubtarget &STI, const MachineInstr &Candidate, const BranchInformation &BranchInfo, RegDefsUses &RegDU, InspectMemInstr &IM)
	This function checks if it is valid to move Candidate to the delay slot and returns true if it isn't.
template<typename IterTy>
static bool	searchRange (MachineBasicBlock &MBB, IterTy Begin, IterTy End, const BranchInformation &BranchInfo, RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot, IterTy &Filler)
	This function searches range [Begin, End) for an instruction that can be moved to the delay slot.
static bool	searchBackward (MachineBasicBlock &MBB, MachineInstr &Slot, const BranchInformation &BranchInfo)
	This function searches in the backward direction for an instruction that can be moved to the delay slot.
static bool	searchForward (MachineBasicBlock &MBB, Iter Slot, const BranchInformation &BranchInfo)
	This function searches MBB in the forward direction for an instruction that can be moved to the delay slot.
static MachineBasicBlock *	selectSuccBB (MachineBasicBlock &B, function_ref< MachineBranchProbabilityInfo &()> GetMBPI)
	Pick a successor block of MBB.
static std::pair< MipsInstrInfo::BranchType, MachineInstr * >	getBranch (MachineBasicBlock &MBB, const MachineBasicBlock &Dst)
	This function analyzes MBB and returns an instruction with an unoccupied slot that branches to Dst.
static bool	examinePred (MachineBasicBlock &Pred, const MachineBasicBlock &Succ, RegDefsUses &RegDU, bool &HasMultipleSuccs, BB2BrMap &BrMap)
	Examine Pred and see if it is possible to insert an instruction into one of its branches delay slot or its end.
static bool	searchSuccBBs (MachineBasicBlock &MBB, Iter Slot, const BranchInformation &BranchInfo, function_ref< MachineBranchProbabilityInfo &()> GetMBPI)
	This function searches one of MBB's successor blocks for an instruction that can be moved to the delay slot and inserts clones of the instruction into the successor's predecessor blocks.
static bool	runOnMachineBasicBlock (MachineBasicBlock &MBB, MachineInstr *FirstNextMBBInstr, function_ref< MachineBranchProbabilityInfo &()> GetMBPI)
	runOnMachineBasicBlock - Fill in delay slots for the given basic block.
static bool	runDelaySlotFillerOnFunction (MachineFunction &MF, function_ref< MachineBranchProbabilityInfo &()> GetMBPI)

Variables
const BB2BrMap &	BrMap

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "mips-delay-slot-filler"

Definition at line 54 of file MipsDelaySlotFiller.cpp.

Function Documentation

◆ addLiveInRegs()

void addLiveInRegs	(	Iter	Filler,
		MachineBasicBlock &	MBB )

static

This function adds registers Filler defines to MBB's live-in register list.

Definition at line 368 of file MipsDelaySlotFiller.cpp.

References assert(), llvm::TargetRegisterInfo::getAllocatableSet(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), MBB, and llvm::BitVector::test().

Referenced by searchSuccBBs().

◆ delayExposesHazard()

bool delayExposesHazard	(	const BranchInformation &	BranchInfo,
		const MachineInstr &	Candidate,
		function_ref< bool(const MachineInstr &, const MachineInstr &)>	IsSafe )

static

Returns true if putting the candidate in the delay slot could let the branch target, or the instruction after the slot, read its result too early, or if those cannot be determined.

Definition at line 655 of file MipsDelaySlotFiller.cpp.

References llvm::MachineBasicBlock::empty(), and llvm::MachineBasicBlock::instr_front().

Referenced by delayHasHazard().

◆ delayHasHazard()

bool delayHasHazard	(	const MipsSubtarget &	STI,
		const MachineInstr &	Candidate,
		const BranchInformation &	BranchInfo,
		RegDefsUses &	RegDU,
		InspectMemInstr &	IM )

static

This function checks if it is valid to move Candidate to the delay slot and returns true if it isn't.

It also updates memory and register dependence information.

Definition at line 683 of file MipsDelaySlotFiller.cpp.

References assert(), delayExposesHazard(), llvm::MipsSubtarget::getInstrInfo(), llvm::MachineInstr::getNumOperands(), llvm::MipsSubtarget::hasMips1(), llvm::MipsSubtarget::hasMips2(), llvm::MipsSubtarget::hasMips32(), llvm::MipsSubtarget::hasMips4(), llvm::MachineInstr::isImplicitDef(), llvm::MachineInstr::isKill(), and TII.

Referenced by searchRange().

◆ examinePred()

bool examinePred	(	MachineBasicBlock &	Pred,
		const MachineBasicBlock &	Succ,
		RegDefsUses &	RegDU,
		bool &	HasMultipleSuccs,
		BB2BrMap &	BrMap )

static

Examine Pred and see if it is possible to insert an instruction into one of its branches delay slot or its end.

Definition at line 919 of file MipsDelaySlotFiller.cpp.

References BrMap, llvm::MipsInstrInfo::BT_NoBranch, llvm::MipsInstrInfo::BT_None, llvm::MipsInstrInfo::BT_Uncond, getBranch(), P, and Pred.

Referenced by searchSuccBBs().

◆ for()

for ( const auto &I :BrMap )

Definition at line 357 of file MipsDelaySlotFiller.cpp.

References llvm::MIBundleBuilder::append(), BrMap, and I.

◆ getBranch()

std::pair< MipsInstrInfo::BranchType, MachineInstr * > getBranch	(	MachineBasicBlock &	MBB,
		const MachineBasicBlock &	Dst )

static

This function analyzes MBB and returns an instruction with an unoccupied slot that branches to Dst.

Definition at line 882 of file MipsDelaySlotFiller.cpp.

References assert(), llvm::MipsInstrInfo::BT_Cond, llvm::MipsInstrInfo::BT_CondUncond, llvm::MipsInstrInfo::BT_NoBranch, llvm::MipsInstrInfo::BT_None, llvm::MipsInstrInfo::BT_Uncond, Cond, hasUnoccupiedSlot(), MBB, and TII.

Referenced by examinePred().

◆ getEquivalentCallShort()

int getEquivalentCallShort ( int Opcode )

static

Definition at line 624 of file MipsDelaySlotFiller.cpp.

References llvm_unreachable.

Referenced by runOnMachineBasicBlock().

◆ hasUnoccupiedSlot()

bool hasUnoccupiedSlot ( const MachineInstr * MI )

static

Definition at line 275 of file MipsDelaySlotFiller.cpp.

References MI.

Referenced by getBranch(), and runOnMachineBasicBlock().

◆ INITIALIZE_PASS()

INITIALIZE_PASS	(	MipsDelaySlotFillerLegacy	,
		DEBUG_TYPE	,
		"Fill delay slot for MIPS"	,
		false	,
		false	)

This function inserts clones of Filler into predecessor blocks.

References DEBUG_TYPE.

◆ isR5900ShortLoopBranch()

bool isR5900ShortLoopBranch	(	const MachineInstr *	MI,
		const MachineBasicBlock &	MBB )

static

Check if a branch is a short backward loop that triggers the R5900 erratum.

Quote from binutils-gdb/gas/config/tc-mips.c:

On the R5900 short loops need to be fixed by inserting a NOP in the branch delay slot.

The short loop bug under certain conditions causes loops to execute only once or twice. We must ensure that the assembler never generates loops that satisfy all of the following conditions:

a loop consists of less than or equal to six instructions (including the branch delay slot);
a loop contains only one conditional branch instruction at the end of the loop;
a loop does not contain any other branch or jump instructions;
a branch delay slot of the loop is not NOP (EE 2.9 or later).

We need to do this because of a hardware bug in the R5900 chip.

Definition at line 297 of file MipsDelaySlotFiller.cpp.

References InstrCount, MBB, and MI.

Referenced by runOnMachineBasicBlock().

◆ replaceWithCompactBranch()

Iter replaceWithCompactBranch	(	MachineBasicBlock &	MBB,
		Iter	Branch,
		const DebugLoc &	DL )

static

Definition at line 602 of file MipsDelaySlotFiller.cpp.

References llvm::cast(), DL, llvm::MipsSubtarget::getInstrInfo(), MBB, and TII.

Referenced by runOnMachineBasicBlock().

◆ runDelaySlotFillerOnFunction()

bool runDelaySlotFillerOnFunction	(	MachineFunction &	MF,
		function_ref< MachineBranchProbabilityInfo &()>	GetMBPI )

static

Definition at line 1107 of file MipsDelaySlotFiller.cpp.

References llvm::MachineFunction::begin(), Changed, llvm::MachineFunction::end(), llvm::MachineFunction::getRegInfo(), llvm::MachineRegisterInfo::invalidateLiveness(), MBB, and runOnMachineBasicBlock().

Referenced by llvm::MipsDelaySlotFillerPass::run().

◆ runOnMachineBasicBlock()

bool runOnMachineBasicBlock	(	MachineBasicBlock &	MBB,
		MachineInstr *	FirstNextMBBInstr,
		function_ref< MachineBranchProbabilityInfo &()>	GetMBPI )

static

runOnMachineBasicBlock - Fill in delay slots for the given basic block.

We assume there is only one delay slot per delayed instruction.

Definition at line 996 of file MipsDelaySlotFiller.cpp.

References llvm::Always, Changed, llvm::dbgs(), DEBUG_TYPE, llvm::MipsSubtarget::fixR5900(), getEquivalentCallShort(), llvm::MipsSubtarget::getInstrInfo(), llvm::TargetMachine::getOptLevel(), llvm::MipsSubtarget::hasMips32r6(), hasUnoccupiedSlot(), I, llvm::MipsSubtarget::inMicroMipsMode(), isR5900ShortLoopBranch(), LLVM_DEBUG, MBB, llvm::Never, llvm::None, replaceWithCompactBranch(), searchBackward(), searchForward(), searchSuccBBs(), and TII.

Referenced by runDelaySlotFillerOnFunction().

◆ searchBackward()

bool searchBackward	(	MachineBasicBlock &	MBB,
		MachineInstr &	Slot,
		const BranchInformation &	BranchInfo )

static

This function searches in the backward direction for an instruction that can be moved to the delay slot.

Returns true on success.

Definition at line 803 of file MipsDelaySlotFiller.cpp.

References llvm::dbgs(), DEBUG_TYPE, llvm::MachineInstrBundleIterator< Ty, IsReverse >::getReverse(), LLVM_DEBUG, MBB, and searchRange().

Referenced by runOnMachineBasicBlock().

◆ searchForward()

bool searchForward	(	MachineBasicBlock &	MBB,
		Iter	Slot,
		const BranchInformation &	BranchInfo )

static

This function searches MBB in the forward direction for an instruction that can be moved to the delay slot.

Returns true on success.

Definition at line 833 of file MipsDelaySlotFiller.cpp.

References llvm::dbgs(), DEBUG_TYPE, LLVM_DEBUG, MBB, and searchRange().

Referenced by runOnMachineBasicBlock().

◆ searchRange()

template<typename IterTy>

bool searchRange	(	MachineBasicBlock &	MBB,
		IterTy	Begin,
		IterTy	End,
		const BranchInformation &	BranchInfo,
		RegDefsUses &	RegDU,
		InspectMemInstr &	IM,
		Iter	Slot,
		IterTy &	Filler )

static

This function searches range [Begin, End) for an instruction that can be moved to the delay slot.

Returns true on success.

Definition at line 723 of file MipsDelaySlotFiller.cpp.

References assert(), llvm::dbgs(), DEBUG_TYPE, delayHasHazard(), llvm::End, llvm::MipsSubtarget::getInstrInfo(), llvm::MipsSubtarget::hasMips32(), llvm::MipsSubtarget::hasMips5(), I, llvm::MipsSubtarget::inMicroMipsMode(), IsMFLOMFHI, LLVM_DEBUG, MBB, terminateSearch(), and TII.

Referenced by searchBackward(), searchForward(), and searchSuccBBs().

◆ searchSuccBBs()

bool searchSuccBBs	(	MachineBasicBlock &	MBB,
		Iter	Slot,
		const BranchInformation &	BranchInfo,
		function_ref< MachineBranchProbabilityInfo &()>	GetMBPI )

static

This function searches one of MBB's successor blocks for an instruction that can be moved to the delay slot and inserts clones of the instruction into the successor's predecessor blocks.

Definition at line 944 of file MipsDelaySlotFiller.cpp.

References addLiveInRegs(), llvm::MachineBasicBlock::begin(), BrMap, llvm::MachineBasicBlock::end(), examinePred(), MBB, Pred, llvm::MachineBasicBlock::predecessors(), searchRange(), and selectSuccBB().

Referenced by runOnMachineBasicBlock().

◆ selectSuccBB()

MachineBasicBlock * selectSuccBB	(	MachineBasicBlock &	B,
		function_ref< MachineBranchProbabilityInfo &()>	GetMBPI )

static

Pick a successor block of MBB.

Return NULL if MBB doesn't have a successor block that is not a landing pad.

Definition at line 863 of file MipsDelaySlotFiller.cpp.

References B(), llvm::MachineBasicBlock::isEHPad(), and llvm::max_element().

Referenced by searchSuccBBs().

◆ STATISTIC() [1/3]

STATISTIC	(	FilledSlots	,
		"Number of delay slots filled"	)

◆ STATISTIC() [2/3]

STATISTIC	(	R5900ShortLoopNops	,
		"Number of delay slots left as NOP for R5900 " "short loop fix"	)

◆ STATISTIC() [3/3]

STATISTIC	(	UsefulSlots	,
		"Number of delay slots filled with instructions that" " are not NOP."	)

◆ terminateSearch()

bool terminateSearch ( const MachineInstr & Candidate )

static

Definition at line 646 of file MipsDelaySlotFiller.cpp.

References llvm::MachineInstr::hasUnmodeledSideEffects(), llvm::MachineInstr::isCall(), llvm::MachineInstr::isInlineAsm(), llvm::MachineInstr::isPosition(), and llvm::MachineInstr::isTerminator().

Referenced by searchRange().

Variable Documentation

◆ BrMap

const BB2BrMap& BrMap

Initial value:

{

MachineFunction *MF = Filler->getParent()->getParent()

llvm::MachineFunction

Definition MachineFunction.h:286

Definition at line 354 of file MipsDelaySlotFiller.cpp.

Referenced by examinePred(), for(), and searchSuccBBs().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ addLiveInRegs()

◆ delayExposesHazard()

◆ delayHasHazard()

◆ examinePred()

◆ for()

◆ getBranch()

◆ getEquivalentCallShort()

◆ hasUnoccupiedSlot()

◆ INITIALIZE_PASS()

◆ isR5900ShortLoopBranch()

◆ replaceWithCompactBranch()

◆ runDelaySlotFillerOnFunction()

◆ runOnMachineBasicBlock()

◆ searchBackward()

◆ searchForward()

◆ searchRange()

◆ searchSuccBBs()

◆ selectSuccBB()

◆ STATISTIC() [1/3]

◆ STATISTIC() [2/3]

◆ STATISTIC() [3/3]

◆ terminateSearch()

Variable Documentation

◆ BrMap