107#define DEBUG_TYPE "mips-branch-expansion"
118 cl::desc(
"MIPS: Expand all branches to long format."),
128 bool HasLongBranch =
false;
143 return "Mips Branch Expansion Pass";
150 MachineFunctionProperties::Property::NoVRegs);
162 void expandToLongBranch(MBBInfo &Info);
163 template <
typename Pred,
typename Safe>
164 bool handleSlot(Pred
Predicate, Safe SafeInSlot);
165 bool handleForbiddenSlot();
166 bool handleFPUDelaySlot();
167 bool handleLoadDelaySlot();
168 bool handlePossibleLongBranch();
170 template <
typename Pred,
typename Safe>
171 bool handleMFLOSlot(Pred
Predicate, Safe SafeInSlot);
180 bool ForceLongBranchFirstPass =
false;
185char MipsBranchExpansion::ID = 0;
188 "Expand out of range branch instructions and fix forbidden"
194 return new MipsBranchExpansion();
200 Iter
I = Position, E = Position->getParent()->end();
201 I = std::find_if_not(
I, E,
202 [](
const Iter &
Insn) {
return Insn->isTransient(); });
211 if (Position == Parent->
end()) {
214 if (Succ !=
nullptr && Parent->
isSuccessor(Succ)) {
215 Position = Succ->
begin();
218 return std::make_pair(Position,
true);
220 }
while (Parent->
empty());
224 if (Instr == Parent->
end()) {
227 return std::make_pair(Instr,
false);
247 if (!
B->isDebugInstr())
259 if ((LastBr ==
End) ||
260 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
267 if ((FirstBr ==
End) ||
268 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
271 assert(!FirstBr->isIndirectBranch() &&
"Unexpected indirect branch found.");
290void MipsBranchExpansion::initMBBInfo() {
293 for (
auto &
MBB : *MFp)
296 MFp->RenumberBlocks();
298 MBBInfos.resize(MFp->size());
300 for (
unsigned I = 0, E = MBBInfos.size();
I < E; ++
I) {
305 MBBInfos[
I].Size +=
TII->getInstSizeInBytes(
MI);
310int64_t MipsBranchExpansion::computeOffset(
const MachineInstr *Br) {
316 if (ThisMBB < TargetMBB) {
317 for (
int N = ThisMBB + 1;
N < TargetMBB; ++
N)
324 for (
int N = ThisMBB;
N >= TargetMBB; --
N)
331uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(
int MBB) {
333 for (
int N = 0;
N <
MBB; ++
N)
343 unsigned NewOpc =
TII->getOppositeBranchOpc(Br->getOpcode());
348 for (
unsigned I = 0, E = Br->getDesc().getNumOperands();
I < E; ++
I) {
358 if (!
TII->isBranchWithImm(Br->getOpcode()))
370 if (Br->hasDelaySlot()) {
373 assert(Br->isBundledWithSucc());
377 Br->eraseFromParent();
383 bool HasR6 =
ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
384 bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
386 unsigned JR =
ABI.IsN64() ? Mips::JR64 : Mips::JR;
387 unsigned JIC =
ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
388 unsigned JR_HB =
ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
389 unsigned JR_HB_R6 =
ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
392 if (STI->useIndirectJumpsHazard())
393 JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
395 JumpOp = HasR6 ? JIC : JR;
397 if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
398 JumpOp = Mips::JIC_MMR6;
400 unsigned ATReg =
ABI.IsN64() ? Mips::AT_64 : Mips::AT;
414void MipsBranchExpansion::expandToLongBranch(MBBInfo &
I) {
422 MFp->
insert(FallThroughMBB, LongBrMBB);
427 MFp->
insert(FallThroughMBB, BalTgtMBB);
434 const unsigned BalOp =
436 ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
437 : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
469 Pos = LongBrMBB->
begin();
471 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::ADDiu), Mips::SP)
495 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
502 BuildMI(*MFp,
DL,
TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
506 if (STI->hasMips32r6()) {
507 LongBrMBB->
insert(Pos, ADDiuInstr);
508 LongBrMBB->
insert(Pos, BalInstr);
510 LongBrMBB->
insert(Pos, BalInstr);
511 LongBrMBB->
insert(Pos, ADDiuInstr);
512 LongBrMBB->
rbegin()->bundleWithPred();
515 Pos = BalTgtMBB->
begin();
517 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::ADDu), Mips::AT)
520 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::LW), Mips::RA)
523 if (STI->isTargetNaCl())
529 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos,
DL);
531 if (STI->isTargetNaCl() || !hasDelaySlot) {
532 BuildMI(*BalTgtMBB, std::prev(Pos),
DL,
TII->get(Mips::ADDiu), Mips::SP)
537 if (STI->isTargetNaCl()) {
538 TII->insertNop(*BalTgtMBB, Pos,
DL);
540 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::ADDiu), Mips::SP)
544 BalTgtMBB->
rbegin()->bundleWithPred();
592 Pos = LongBrMBB->
begin();
594 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DADDiu), Mips::SP_64)
601 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu),
606 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
613 BuildMI(*MFp,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
617 if (STI->hasMips32r6()) {
618 LongBrMBB->
insert(Pos, DADDiuInstr);
619 LongBrMBB->
insert(Pos, BalInstr);
621 LongBrMBB->
insert(Pos, BalInstr);
622 LongBrMBB->
insert(Pos, DADDiuInstr);
623 LongBrMBB->
rbegin()->bundleWithPred();
626 Pos = BalTgtMBB->
begin();
628 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::DADDu), Mips::AT_64)
631 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::LD), Mips::RA_64)
635 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos,
DL);
638 BuildMI(*BalTgtMBB, std::prev(Pos),
DL,
TII->get(Mips::DADDiu),
643 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::DADDiu), Mips::SP_64)
646 BalTgtMBB->
rbegin()->bundleWithPred();
650 Pos = LongBrMBB->
begin();
657 uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
660 if (JOffset < TgtMBBOffset)
661 TgtMBBOffset += 2 * 4;
663 bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
665 if (STI->hasMips32r6() &&
TII->isBranchOffsetInRange(Mips::BC,
I.Offset)) {
672 TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
674 }
else if (SameSegmentJump) {
682 TII->insertNop(*LongBrMBB, Pos,
DL)->bundleWithPred();
690 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi2Op_64),
693 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
697 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
700 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
704 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
707 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
712 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi2Op),
715 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_ADDiu2Op),
720 buildProperJumpMI(LongBrMBB, Pos,
DL);
724 if (
I.Br->isUnconditionalBranch()) {
726 assert(
I.Br->getDesc().getNumOperands() == 1);
727 I.Br->removeOperand(0);
731 replaceBranch(*
MBB,
I.Br,
DL, &*FallThroughMBB);
746template <
typename Pred,
typename Safe>
747bool MipsBranchExpansion::handleMFLOSlot(Pred
Predicate, Safe SafeInSlot) {
748 bool Changed =
false;
749 bool hasPendingMFLO =
false;
752 for (Iter
I = FI->begin();
I != FI->end(); ++
I) {
759 bool LastInstInFunction =
760 std::next(
I) == FI->end() && std::next(FI) == MFp->end();
766 if (!LastInstInFunction) {
768 LastInstInFunction |= Res.second;
770 if (LastInstInFunction)
772 if (!SafeInSlot(*IInSlot, *
I)) {
774 TII->insertNop(*(
I->getParent()), std::next(
I),
I->getDebugLoc())
778 TII->insertNop(*(
I->getParent()), std::next(
I),
I->getDebugLoc())
783 hasPendingMFLO =
false;
784 }
else if (hasPendingMFLO)
785 hasPendingMFLO =
false;
787 hasPendingMFLO =
true;
795template <
typename Pred,
typename Safe>
796bool MipsBranchExpansion::handleSlot(Pred
Predicate, Safe SafeInSlot) {
797 bool Changed =
false;
800 for (Iter
I = FI->begin();
I != FI->end(); ++
I) {
807 bool LastInstInFunction =
808 std::next(
I) == FI->end() && std::next(FI) == MFp->end();
809 if (!LastInstInFunction) {
811 LastInstInFunction |= Res.second;
815 if (LastInstInFunction || !SafeInSlot(*IInSlot, *
I)) {
817 if (std::next(Iit) == FI->end() ||
818 std::next(Iit)->getOpcode() != Mips::NOP) {
820 TII->insertNop(*(
I->getParent()), std::next(
I),
I->getDebugLoc())
831bool MipsBranchExpansion::handleMFLO() {
834 if (STI->hasMips32() || STI->hasMips5())
837 return handleMFLOSlot(
838 [
this](
auto &
I) ->
bool {
return TII->IsMfloOrMfhi(
I); },
839 [
this](
auto &IInSlot,
auto &
I) ->
bool {
840 return TII->SafeAfterMflo(IInSlot);
844bool MipsBranchExpansion::handleForbiddenSlot() {
846 if (!STI->hasMips32r6() || STI->inMicroMipsMode())
850 [
this](
auto &
I) ->
bool {
return TII->HasForbiddenSlot(
I); },
851 [
this](
auto &IInSlot,
auto &
I) ->
bool {
852 return TII->SafeInForbiddenSlot(IInSlot);
856bool MipsBranchExpansion::handleFPUDelaySlot() {
858 if (STI->hasMips32() || STI->hasMips4())
861 return handleSlot([
this](
auto &
I) ->
bool {
return TII->HasFPUDelaySlot(
I); },
862 [
this](
auto &IInSlot,
auto &
I) ->
bool {
863 return TII->SafeInFPUDelaySlot(IInSlot,
I);
867bool MipsBranchExpansion::handleLoadDelaySlot() {
873 [
this](
auto &
I) ->
bool {
return TII->HasLoadDelaySlot(
I); },
874 [
this](
auto &IInSlot,
auto &
I) ->
bool {
875 return TII->SafeInLoadDelaySlot(IInSlot,
I);
879bool MipsBranchExpansion::handlePossibleLongBranch() {
880 if (STI->inMips16Mode() || !STI->enableLongBranchPass())
886 bool EverMadeChange =
false, MadeChange =
true;
893 for (
unsigned I = 0, E = MBBInfos.size();
I < E; ++
I) {
899 if ((Br !=
End) && Br->isBranch() && !Br->isIndirectBranch() &&
900 (Br->isConditionalBranch() ||
901 (Br->isUnconditionalBranch() && IsPIC))) {
902 int64_t
Offset = computeOffset(&*Br);
904 if (STI->isTargetNaCl()) {
912 if (ForceLongBranchFirstPass ||
913 !
TII->isBranchOffsetInRange(Br->getOpcode(),
Offset)) {
915 MBBInfos[
I].Br = &*Br;
920 ForceLongBranchFirstPass =
false;
924 for (
I = MBBInfos.begin();
I != E; ++
I) {
930 expandToLongBranch(*
I);
932 EverMadeChange = MadeChange =
true;
935 MFp->RenumberBlocks();
938 return EverMadeChange;
943 IsPIC =
TM.isPositionIndependent();
948 if (IsPIC &&
ABI.IsO32() &&
956 bool longBranchChanged = handlePossibleLongBranch();
957 bool forbiddenSlotChanged = handleForbiddenSlot();
958 bool fpuDelaySlotChanged = handleFPUDelaySlot();
959 bool loadDelaySlotChanged = handleLoadDelaySlot();
960 bool MfloChanged = handleMFLO();
962 bool Changed = longBranchChanged || forbiddenSlotChanged ||
963 fpuDelaySlotChanged || loadDelaySlotChanged || MfloChanged;
966 while (forbiddenSlotChanged) {
967 longBranchChanged = handlePossibleLongBranch();
968 fpuDelaySlotChanged = handleFPUDelaySlot();
969 loadDelaySlotChanged = handleLoadDelaySlot();
970 MfloChanged = handleMFLO();
971 if (!longBranchChanged && !fpuDelaySlotChanged && !loadDelaySlotChanged &&
974 forbiddenSlotChanged = handleForbiddenSlot();
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const HexagonInstrInfo * TII
static std::pair< Iter, bool > getNextMachineInstr(Iter Position, MachineBasicBlock *Parent)
static cl::opt< bool > ForceLongBranch("force-mips-long-branch", cl::init(false), cl::desc("MIPS: Expand all branches to long format."), cl::Hidden)
static cl::opt< bool > SkipLongBranch("skip-mips-long-branch", cl::init(false), cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden)
static MachineBasicBlock * getTargetMBB(const MachineInstr &Br)
Iterate over list of Br's operands and search for a MachineBasicBlock operand.
static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII)
static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E)
static Iter getNextMachineInstrInBB(Iter Position)
#define IsMFLOMFHI(instr)
uint64_t IntrinsicInst * II
static bool splitMBB(BlockSplitInfo &BSI)
Splits a MachineBasicBlock to branch before SplitBefore.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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)
LLVM Basic Block Representation.
FunctionPass class - This class is used to implement most global optimizations.
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Helper class for constructing bundles of MachineInstrs.
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void removeLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
Instructions::iterator instr_iterator
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
reverse_iterator rbegin()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
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
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
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.
BasicBlockListType::iterator iterator
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
const MachineInstrBuilder & addExternalSymbol(const char *FnName, unsigned TargetFlags=0) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
MachineBasicBlock * getMBB() const
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
Register getReg() const
getReg - Returns the register number.
@ MO_Immediate
Immediate operand.
@ MO_MachineBasicBlock
MachineBasicBlock reference.
@ MO_Register
Register operand.
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
MipsFunctionInfo - This class is derived from MachineFunction private Mips target-specific informatio...
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.
typename SuperClass::iterator iterator
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.
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
#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.
@ MO_ABS_HI
MO_ABS_HI/LO - Represents the hi or low part of an absolute symbol address.
@ MO_HIGHER
MO_HIGHER/HIGHEST - Represents the highest or higher half word of a 64-bit symbol address.
initializer< Ty > init(const Ty &Val)
NodeAddr< InstrNode * > Instr
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void initializeMipsBranchExpansionPass(PassRegistry &)
FunctionPass * createMipsBranchExpansion()
static const Align MIPS_NACL_BUNDLE_ALIGN