106 using namespace llvm;
108 #define DEBUG_TYPE "mips-branch-expansion"
110 STATISTIC(NumInsertedNops,
"Number of nops inserted");
111 STATISTIC(LongBranches,
"Number of long branches.");
119 cl::desc(
"MIPS: Expand all branches to long format."),
129 bool HasLongBranch =
false;
144 return "Mips Branch Expansion Pass";
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;
186 "Expand out of range branch instructions and fix forbidden"
192 return new MipsBranchExpansion();
198 Iter
I = Position,
E = Position->getParent()->end();
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.");
288 void 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);
309 int64_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)
330 uint64_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;
413 void 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)
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)
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);
745 template <
typename Pred,
typename Safe>
746 bool 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())
781 bool 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);
793 bool 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);
804 bool MipsBranchExpansion::handleLoadDelaySlot() {
810 [
this](
auto &
I) ->
bool {
return TII->HasLoadDelaySlot(
I); },
811 [
this](
auto &IInSlot,
auto &
I) ->
bool {
812 return TII->SafeInLoadDelaySlot(IInSlot,
I);
816 bool 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();