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) {
303 MBBInfos[
I].Size +=
TII->getInstSizeInBytes(
MI);
308int64_t MipsBranchExpansion::computeOffset(
const MachineInstr *Br) {
314 if (ThisMBB < TargetMBB) {
315 for (
int N = ThisMBB + 1;
N < TargetMBB; ++
N)
322 for (
int N = ThisMBB;
N >= TargetMBB; --
N)
329uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(
int MBB) {
331 for (
int N = 0;
N <
MBB; ++
N)
341 unsigned NewOpc =
TII->getOppositeBranchOpc(Br->getOpcode());
346 for (
unsigned I = 0, E = Br->getDesc().getNumOperands();
I < E; ++
I) {
356 if (!
TII->isBranchWithImm(Br->getOpcode()))
368 if (Br->hasDelaySlot()) {
371 assert(Br->isBundledWithSucc());
375 Br->eraseFromParent();
381 bool HasR6 =
ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
382 bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
384 unsigned JR =
ABI.IsN64() ? Mips::JR64 : Mips::JR;
385 unsigned JIC =
ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
386 unsigned JR_HB =
ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
387 unsigned JR_HB_R6 =
ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
390 if (STI->useIndirectJumpsHazard())
391 JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
393 JumpOp = HasR6 ? JIC : JR;
395 if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
396 JumpOp = Mips::JIC_MMR6;
398 unsigned ATReg =
ABI.IsN64() ? Mips::AT_64 : Mips::AT;
412void MipsBranchExpansion::expandToLongBranch(MBBInfo &
I) {
420 MFp->
insert(FallThroughMBB, LongBrMBB);
425 MFp->
insert(FallThroughMBB, BalTgtMBB);
432 const unsigned BalOp =
434 ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
435 : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
467 Pos = LongBrMBB->
begin();
469 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::ADDiu), Mips::SP)
493 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
500 BuildMI(*MFp,
DL,
TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
504 if (STI->hasMips32r6()) {
505 LongBrMBB->
insert(Pos, ADDiuInstr);
506 LongBrMBB->
insert(Pos, BalInstr);
508 LongBrMBB->
insert(Pos, BalInstr);
509 LongBrMBB->
insert(Pos, ADDiuInstr);
510 LongBrMBB->
rbegin()->bundleWithPred();
513 Pos = BalTgtMBB->
begin();
515 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::ADDu), Mips::AT)
518 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::LW), Mips::RA)
521 if (STI->isTargetNaCl())
527 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos,
DL);
529 if (STI->isTargetNaCl() || !hasDelaySlot) {
530 BuildMI(*BalTgtMBB, std::prev(Pos),
DL,
TII->get(Mips::ADDiu), Mips::SP)
535 if (STI->isTargetNaCl()) {
536 TII->insertNop(*BalTgtMBB, Pos,
DL);
538 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::ADDiu), Mips::SP)
542 BalTgtMBB->
rbegin()->bundleWithPred();
590 Pos = LongBrMBB->
begin();
592 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DADDiu), Mips::SP_64)
599 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu),
604 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
611 BuildMI(*MFp,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
615 if (STI->hasMips32r6()) {
616 LongBrMBB->
insert(Pos, DADDiuInstr);
617 LongBrMBB->
insert(Pos, BalInstr);
619 LongBrMBB->
insert(Pos, BalInstr);
620 LongBrMBB->
insert(Pos, DADDiuInstr);
621 LongBrMBB->
rbegin()->bundleWithPred();
624 Pos = BalTgtMBB->
begin();
626 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::DADDu), Mips::AT_64)
629 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::LD), Mips::RA_64)
633 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos,
DL);
636 BuildMI(*BalTgtMBB, std::prev(Pos),
DL,
TII->get(Mips::DADDiu),
641 BuildMI(*BalTgtMBB, Pos,
DL,
TII->get(Mips::DADDiu), Mips::SP_64)
644 BalTgtMBB->
rbegin()->bundleWithPred();
648 Pos = LongBrMBB->
begin();
655 uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
658 if (JOffset < TgtMBBOffset)
659 TgtMBBOffset += 2 * 4;
661 bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
663 if (STI->hasMips32r6() &&
TII->isBranchOffsetInRange(Mips::BC,
I.Offset)) {
670 TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
672 }
else if (SameSegmentJump) {
680 TII->insertNop(*LongBrMBB, Pos,
DL)->bundleWithPred();
688 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi2Op_64),
691 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
695 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
698 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
702 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::DSLL), Mips::AT_64)
705 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
710 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_LUi2Op),
713 BuildMI(*LongBrMBB, Pos,
DL,
TII->get(Mips::LONG_BRANCH_ADDiu2Op),
718 buildProperJumpMI(LongBrMBB, Pos,
DL);
722 if (
I.Br->isUnconditionalBranch()) {
724 assert(
I.Br->getDesc().getNumOperands() == 1);
725 I.Br->removeOperand(0);
729 replaceBranch(*
MBB,
I.Br,
DL, &*FallThroughMBB);
744template <
typename Pred,
typename Safe>
745bool MipsBranchExpansion::handleSlot(Pred Predicate, Safe SafeInSlot) {
746 bool Changed =
false;
749 for (Iter
I = FI->begin();
I != FI->end(); ++
I) {
756 bool LastInstInFunction =
757 std::next(
I) == FI->end() && std::next(FI) == MFp->end();
758 if (!LastInstInFunction) {
760 LastInstInFunction |= Res.second;
764 if (LastInstInFunction || !SafeInSlot(*IInSlot, *
I)) {
766 if (std::next(Iit) == FI->end() ||
767 std::next(Iit)->getOpcode() != Mips::NOP) {
769 TII->insertNop(*(
I->getParent()), std::next(
I),
I->getDebugLoc())
780bool MipsBranchExpansion::handleForbiddenSlot() {
782 if (!STI->hasMips32r6() || STI->inMicroMipsMode())
786 [
this](
auto &
I) ->
bool {
return TII->HasForbiddenSlot(
I); },
787 [
this](
auto &IInSlot,
auto &
I) ->
bool {
788 return TII->SafeInForbiddenSlot(IInSlot);
792bool MipsBranchExpansion::handleFPUDelaySlot() {
794 if (STI->hasMips32() || STI->hasMips4())
797 return handleSlot([
this](
auto &
I) ->
bool {
return TII->HasFPUDelaySlot(
I); },
798 [
this](
auto &IInSlot,
auto &
I) ->
bool {
799 return TII->SafeInFPUDelaySlot(IInSlot,
I);
803bool MipsBranchExpansion::handleLoadDelaySlot() {
809 [
this](
auto &
I) ->
bool {
return TII->HasLoadDelaySlot(
I); },
810 [
this](
auto &IInSlot,
auto &
I) ->
bool {
811 return TII->SafeInLoadDelaySlot(IInSlot,
I);
815bool MipsBranchExpansion::handlePossibleLongBranch() {
816 if (STI->inMips16Mode() || !STI->enableLongBranchPass())
822 bool EverMadeChange =
false, MadeChange =
true;
829 for (
unsigned I = 0, E = MBBInfos.size();
I < E; ++
I) {
835 if ((Br !=
End) && Br->isBranch() && !Br->isIndirectBranch() &&
836 (Br->isConditionalBranch() ||
837 (Br->isUnconditionalBranch() && IsPIC))) {
838 int64_t
Offset = computeOffset(&*Br);
840 if (STI->isTargetNaCl()) {
848 if (ForceLongBranchFirstPass ||
849 !
TII->isBranchOffsetInRange(Br->getOpcode(),
Offset)) {
851 MBBInfos[
I].Br = &*Br;
856 ForceLongBranchFirstPass =
false;
860 for (
I = MBBInfos.begin();
I != E; ++
I) {
866 expandToLongBranch(*
I);
868 EverMadeChange = MadeChange =
true;
871 MFp->RenumberBlocks();
874 return EverMadeChange;
879 IsPIC =
TM.isPositionIndependent();
884 if (IsPIC &&
ABI.IsO32() &&
892 bool longBranchChanged = handlePossibleLongBranch();
893 bool forbiddenSlotChanged = handleForbiddenSlot();
894 bool fpuDelaySlotChanged = handleFPUDelaySlot();
895 bool loadDelaySlotChanged = handleLoadDelaySlot();
897 bool Changed = longBranchChanged || forbiddenSlotChanged ||
898 fpuDelaySlotChanged || loadDelaySlotChanged;
901 while (forbiddenSlotChanged) {
902 longBranchChanged = handlePossibleLongBranch();
903 fpuDelaySlotChanged = handleFPUDelaySlot();
904 loadDelaySlotChanged = handleLoadDelaySlot();
905 if (!longBranchChanged && !fpuDelaySlotChanged && !loadDelaySlotChanged)
907 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)
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 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
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