108#define DEBUG_TYPE "mips-branch-expansion"
119 cl::desc(
"MIPS: Expand all branches to long format."),
129 bool HasLongBranch =
false;
144 return "Mips Branch Expansion Pass";
151 MachineFunctionProperties::Property::NoVRegs);
163 void expandToLongBranch(MBBInfo &Info);
164 template <
typename Pred,
typename Safe>
165 bool handleSlot(Pred Predicate, Safe SafeInSlot);
166 bool handleForbiddenSlot();
167 bool handleFPUDelaySlot();
168 bool handleLoadDelaySlot();
169 bool handlePossibleLongBranch();
178 bool ForceLongBranchFirstPass =
false;
183char MipsBranchExpansion::ID = 0;
186 "Expand out of range branch instructions and fix forbidden"
192 return new MipsBranchExpansion();
198 Iter
I = Position,
E = Position->getParent()->end();
199 I = std::find_if_not(
I,
E,
200 [](
const Iter &
Insn) {
return Insn->isTransient(); });
209 if (Position == Parent->
end()) {
212 if (Succ !=
nullptr && Parent->
isSuccessor(Succ)) {
213 Position = Succ->
begin();
216 return std::make_pair(Position,
true);
218 }
while (Parent->
empty());
222 if (Instr == Parent->
end()) {
225 return std::make_pair(Instr,
false);
245 if (!
B->isDebugInstr())
257 if ((LastBr ==
End) ||
258 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
265 if ((FirstBr ==
End) ||
266 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
269 assert(!FirstBr->isIndirectBranch() &&
"Unexpected indirect branch found.");
288void MipsBranchExpansion::initMBBInfo() {
291 for (
auto &
MBB : *MFp)
294 MFp->RenumberBlocks();
296 MBBInfos.resize(MFp->size());
298 for (
unsigned I = 0,
E = MBBInfos.size();
I <
E; ++
I) {
304 MBBInfos[
I].Size +=
TII->getInstSizeInBytes(*
MI);
309int64_t MipsBranchExpansion::computeOffset(
const MachineInstr *Br) {
315 if (ThisMBB < TargetMBB) {
316 for (
int N = ThisMBB + 1;
N < TargetMBB; ++
N)
323 for (
int N = ThisMBB;
N >= TargetMBB; --
N)
330uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(
int MBB) {
332 for (
int N = 0;
N <
MBB; ++
N)
342 unsigned NewOpc =
TII->getOppositeBranchOpc(Br->getOpcode());
347 for (
unsigned I = 0,
E = Br->getDesc().getNumOperands();
I <
E; ++
I) {
357 if (!
TII->isBranchWithImm(Br->getOpcode()))
369 if (Br->hasDelaySlot()) {
372 assert(Br->isBundledWithSucc());
376 Br->eraseFromParent();
382 bool HasR6 =
ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
383 bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
385 unsigned JR =
ABI.IsN64() ? Mips::JR64 : Mips::JR;
386 unsigned JIC =
ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
387 unsigned JR_HB =
ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
388 unsigned JR_HB_R6 =
ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
391 if (STI->useIndirectJumpsHazard())
392 JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
394 JumpOp = HasR6 ? JIC : JR;
396 if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
397 JumpOp = Mips::JIC_MMR6;
399 unsigned ATReg =
ABI.IsN64() ? Mips::AT_64 : Mips::AT;
413void MipsBranchExpansion::expandToLongBranch(MBBInfo &
I) {
421 MFp->
insert(FallThroughMBB, LongBrMBB);
426 MFp->
insert(FallThroughMBB, BalTgtMBB);
433 const unsigned BalOp =
435 ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
436 : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
468 Pos = LongBrMBB->
begin();
470 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::ADDiu), Mips::SP)
494 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
501 BuildMI(*MFp,
DL,
TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
505 if (STI->hasMips32r6()) {
506 LongBrMBB->
insert(Pos, ADDiuInstr);
507 LongBrMBB->
insert(Pos, BalInstr);
509 LongBrMBB->
insert(Pos, BalInstr);
510 LongBrMBB->
insert(Pos, ADDiuInstr);
511 LongBrMBB->
rbegin()->bundleWithPred();
514 Pos = BalTgtMBB->
begin();
516 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::ADDu), Mips::AT)
519 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::LW), Mips::RA)
522 if (STI->isTargetNaCl())
528 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos,
DL);
530 if (STI->isTargetNaCl() || !hasDelaySlot) {
531 BuildMI(*BalTgtMBB, std::prev(Pos),
DL,
TII->get(Mips::ADDiu), Mips::SP)
536 if (STI->isTargetNaCl()) {
537 TII->insertNop(*BalTgtMBB, Pos,
DL);
539 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::ADDiu), Mips::SP)
543 BalTgtMBB->
rbegin()->bundleWithPred();
591 Pos = LongBrMBB->
begin();
593 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DADDiu), Mips::SP_64)
600 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu),
605 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
612 BuildMI(*MFp,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
616 if (STI->hasMips32r6()) {
617 LongBrMBB->
insert(Pos, DADDiuInstr);
618 LongBrMBB->
insert(Pos, BalInstr);
620 LongBrMBB->
insert(Pos, BalInstr);
621 LongBrMBB->
insert(Pos, DADDiuInstr);
622 LongBrMBB->
rbegin()->bundleWithPred();
625 Pos = BalTgtMBB->
begin();
627 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::DADDu), Mips::AT_64)
630 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::LD), Mips::RA_64)
634 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos,
DL);
637 BuildMI(*BalTgtMBB, std::prev(Pos),
DL,
TII->get(Mips::DADDiu),
642 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::DADDiu), Mips::SP_64)
645 BalTgtMBB->
rbegin()->bundleWithPred();
649 Pos = LongBrMBB->
begin();
656 uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
659 if (JOffset < TgtMBBOffset)
660 TgtMBBOffset += 2 * 4;
662 bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
664 if (STI->hasMips32r6() &&
TII->isBranchOffsetInRange(Mips::BC,
I.Offset)) {
671 TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
673 }
else if (SameSegmentJump) {
681 TII->insertNop(*LongBrMBB, Pos,
DL)->bundleWithPred();
689 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi2Op_64),
692 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
696 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
699 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
703 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
706 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
711 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi2Op),
714 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_ADDiu2Op),
719 buildProperJumpMI(LongBrMBB, Pos,
DL);
723 if (
I.Br->isUnconditionalBranch()) {
725 assert(
I.Br->getDesc().getNumOperands() == 1);
726 I.Br->removeOperand(0);
730 replaceBranch(*
MBB,
I.Br,
DL, &*FallThroughMBB);
745template <
typename Pred,
typename Safe>
746bool MipsBranchExpansion::handleSlot(Pred Predicate, Safe SafeInSlot) {
747 bool Changed =
false;
750 for (Iter
I = FI->begin();
I != FI->end(); ++
I) {
757 bool LastInstInFunction =
758 std::next(
I) == FI->end() && std::next(FI) == MFp->end();
759 if (!LastInstInFunction) {
761 LastInstInFunction |= Res.second;
765 if (LastInstInFunction || !SafeInSlot(*IInSlot, *
I)) {
767 if (std::next(Iit) == FI->end() ||
768 std::next(Iit)->getOpcode() != Mips::NOP) {
770 TII->insertNop(*(
I->getParent()), std::next(
I),
I->getDebugLoc())
781bool MipsBranchExpansion::handleForbiddenSlot() {
783 if (!STI->hasMips32r6() || STI->inMicroMipsMode())
787 [
this](
auto &
I) ->
bool {
return TII->HasForbiddenSlot(
I); },
788 [
this](
auto &IInSlot,
auto &
I) ->
bool {
789 return TII->SafeInForbiddenSlot(IInSlot);
793bool MipsBranchExpansion::handleFPUDelaySlot() {
795 if (STI->hasMips32() || STI->hasMips4())
798 return handleSlot([
this](
auto &
I) ->
bool {
return TII->HasFPUDelaySlot(
I); },
799 [
this](
auto &IInSlot,
auto &
I) ->
bool {
800 return TII->SafeInFPUDelaySlot(IInSlot,
I);
804bool MipsBranchExpansion::handleLoadDelaySlot() {
810 [
this](
auto &
I) ->
bool {
return TII->HasLoadDelaySlot(
I); },
811 [
this](
auto &IInSlot,
auto &
I) ->
bool {
812 return TII->SafeInLoadDelaySlot(IInSlot,
I);
816bool MipsBranchExpansion::handlePossibleLongBranch() {
817 if (STI->inMips16Mode() || !STI->enableLongBranchPass())
823 bool EverMadeChange =
false, MadeChange =
true;
830 for (
unsigned I = 0,
E = MBBInfos.size();
I <
E; ++
I) {
836 if ((Br !=
End) && Br->isBranch() && !Br->isIndirectBranch() &&
837 (Br->isConditionalBranch() ||
838 (Br->isUnconditionalBranch() && IsPIC))) {
839 int64_t
Offset = computeOffset(&*Br);
841 if (STI->isTargetNaCl()) {
849 if (ForceLongBranchFirstPass ||
850 !
TII->isBranchOffsetInRange(Br->getOpcode(),
Offset)) {
852 MBBInfos[
I].Br = &*Br;
857 ForceLongBranchFirstPass =
false;
861 for (
I = MBBInfos.begin();
I !=
E; ++
I) {
867 expandToLongBranch(*
I);
869 EverMadeChange = MadeChange =
true;
872 MFp->RenumberBlocks();
875 return EverMadeChange;
880 IsPIC =
TM.isPositionIndependent();
885 if (IsPIC &&
ABI.IsO32() &&
893 bool longBranchChanged = handlePossibleLongBranch();
894 bool forbiddenSlotChanged = handleForbiddenSlot();
895 bool fpuDelaySlotChanged = handleFPUDelaySlot();
896 bool loadDelaySlotChanged = handleLoadDelaySlot();
898 bool Changed = longBranchChanged || forbiddenSlotChanged ||
899 fpuDelaySlotChanged || loadDelaySlotChanged;
902 while (forbiddenSlotChanged) {
903 longBranchChanged = handlePossibleLongBranch();
904 fpuDelaySlotChanged = handleFPUDelaySlot();
905 loadDelaySlotChanged = handleLoadDelaySlot();
906 if (!longBranchChanged && !fpuDelaySlotChanged && !loadDelaySlotChanged)
908 forbiddenSlotChanged = handleForbiddenSlot();
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-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)
static bool splitMBB(BlockSplitInfo &BSI)
Splits a MachineBasicBlock to branch before SplitBefore.
const char LLVMTargetMachineRef TM
#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.
instr_iterator instr_begin()
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 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
instr_iterator instr_end()
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
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
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.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
BasicBlockListType::iterator iterator
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
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.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
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