960 lines · cpp
1//===----------------------- MipsBranchExpansion.cpp ----------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8/// \file9///10/// This pass do two things:11/// - it expands a branch or jump instruction into a long branch if its offset12/// is too large to fit into its immediate field,13/// - it inserts nops to prevent forbidden slot hazards.14///15/// The reason why this pass combines these two tasks is that one of these two16/// tasks can break the result of the previous one.17///18/// Example of that is a situation where at first, no branch should be expanded,19/// but after adding at least one nop somewhere in the code to prevent a20/// forbidden slot hazard, offset of some branches may go out of range. In that21/// case it is necessary to check again if there is some branch that needs22/// expansion. On the other hand, expanding some branch may cause a control23/// transfer instruction to appear in the forbidden slot, which is a hazard that24/// should be fixed. This pass alternates between this two tasks untill no25/// changes are made. Only then we can be sure that all branches are expanded26/// properly, and no hazard situations exist.27///28/// Regarding branch expanding:29///30/// When branch instruction like beqzc or bnezc has offset that is too large31/// to fit into its immediate field, it has to be expanded to another32/// instruction or series of instructions.33///34/// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.35/// TODO: Handle out of range bc, b (pseudo) instructions.36///37/// Regarding compact branch hazard prevention:38///39/// Hazards handled: forbidden slots for MIPSR6, FPU slots for MIPS3 and below,40/// load delay slots for MIPS1.41///42/// A forbidden slot hazard occurs when a compact branch instruction is executed43/// and the adjacent instruction in memory is a control transfer instruction44/// such as a branch or jump, ERET, ERETNC, DERET, WAIT and PAUSE.45///46/// For example:47///48/// 0x8004 bnec a1,v0,<P+0x18>49/// 0x8008 beqc a1,a2,<P+0x54>50///51/// In such cases, the processor is required to signal a Reserved Instruction52/// exception.53///54/// Here, if the instruction at 0x8004 is executed, the processor will raise an55/// exception as there is a control transfer instruction at 0x8008.56///57/// There are two sources of forbidden slot hazards:58///59/// A) A previous pass has created a compact branch directly.60/// B) Transforming a delay slot branch into compact branch. This case can be61/// difficult to process as lookahead for hazards is insufficient, as62/// backwards delay slot fillling can also produce hazards in previously63/// processed instuctions.64///65/// In future this pass can be extended (or new pass can be created) to handle66/// other pipeline hazards, such as various MIPS1 hazards, processor errata that67/// require instruction reorganization, etc.68///69/// This pass has to run after the delay slot filler as that pass can introduce70/// pipeline hazards such as compact branch hazard, hence the existing hazard71/// recognizer is not suitable.72///73//===----------------------------------------------------------------------===//74 75#include "MCTargetDesc/MipsABIInfo.h"76#include "MCTargetDesc/MipsBaseInfo.h"77#include "MCTargetDesc/MipsMCTargetDesc.h"78#include "Mips.h"79#include "MipsInstrInfo.h"80#include "MipsMachineFunction.h"81#include "MipsSubtarget.h"82#include "MipsTargetMachine.h"83#include "llvm/ADT/SmallVector.h"84#include "llvm/ADT/Statistic.h"85#include "llvm/ADT/StringRef.h"86#include "llvm/CodeGen/MachineBasicBlock.h"87#include "llvm/CodeGen/MachineFunction.h"88#include "llvm/CodeGen/MachineFunctionPass.h"89#include "llvm/CodeGen/MachineInstr.h"90#include "llvm/CodeGen/MachineInstrBuilder.h"91#include "llvm/CodeGen/MachineModuleInfo.h"92#include "llvm/CodeGen/MachineOperand.h"93#include "llvm/CodeGen/TargetSubtargetInfo.h"94#include "llvm/IR/DebugLoc.h"95#include "llvm/Support/CommandLine.h"96#include "llvm/Support/ErrorHandling.h"97#include "llvm/Target/TargetMachine.h"98#include <algorithm>99#include <cassert>100#include <cstdint>101#include <iterator>102#include <utility>103 104using namespace llvm;105 106#define DEBUG_TYPE "mips-branch-expansion"107 108STATISTIC(NumInsertedNops, "Number of nops inserted");109STATISTIC(LongBranches, "Number of long branches.");110 111static cl::opt<bool>112 SkipLongBranch("skip-mips-long-branch", cl::init(false),113 cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden);114 115static cl::opt<bool>116 ForceLongBranch("force-mips-long-branch", cl::init(false),117 cl::desc("MIPS: Expand all branches to long format."),118 cl::Hidden);119 120namespace {121 122using Iter = MachineBasicBlock::iterator;123using ReverseIter = MachineBasicBlock::reverse_iterator;124 125struct MBBInfo {126 uint64_t Size = 0;127 bool HasLongBranch = false;128 MachineInstr *Br = nullptr;129 uint64_t Offset = 0;130 MBBInfo() = default;131};132 133class MipsBranchExpansion : public MachineFunctionPass {134public:135 static char ID;136 137 MipsBranchExpansion()138 : MachineFunctionPass(ID), ABI(MipsABIInfo::Unknown()) {}139 140 StringRef getPassName() const override {141 return "Mips Branch Expansion Pass";142 }143 144 bool runOnMachineFunction(MachineFunction &F) override;145 146 MachineFunctionProperties getRequiredProperties() const override {147 return MachineFunctionProperties().setNoVRegs();148 }149 150private:151 void splitMBB(MachineBasicBlock *MBB);152 void initMBBInfo();153 int64_t computeOffset(const MachineInstr *Br);154 uint64_t computeOffsetFromTheBeginning(int MBB);155 void replaceBranch(MachineBasicBlock &MBB, Iter Br, const DebugLoc &DL,156 MachineBasicBlock *MBBOpnd);157 bool buildProperJumpMI(MachineBasicBlock *MBB,158 MachineBasicBlock::iterator Pos, DebugLoc DL);159 void expandToLongBranch(MBBInfo &Info);160 template <typename Pred, typename Safe>161 bool handleSlot(Pred Predicate, Safe SafeInSlot);162 bool handleForbiddenSlot();163 bool handleFPUDelaySlot();164 bool handleLoadDelaySlot();165 bool handlePossibleLongBranch();166 bool handleMFLO();167 template <typename Pred, typename Safe>168 bool handleMFLOSlot(Pred Predicate, Safe SafeInSlot);169 170 const MipsSubtarget *STI;171 const MipsInstrInfo *TII;172 173 MachineFunction *MFp;174 SmallVector<MBBInfo, 16> MBBInfos;175 bool IsPIC;176 MipsABIInfo ABI;177 bool ForceLongBranchFirstPass = false;178};179 180} // end of anonymous namespace181 182char MipsBranchExpansion::ID = 0;183 184INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE,185 "Expand out of range branch instructions and fix forbidden"186 " slot hazards",187 false, false)188 189/// Returns a pass that clears pipeline hazards.190FunctionPass *llvm::createMipsBranchExpansion() {191 return new MipsBranchExpansion();192}193 194// Find the next real instruction from the current position in current basic195// block.196static Iter getNextMachineInstrInBB(Iter Position) {197 Iter I = Position, E = Position->getParent()->end();198 I = std::find_if_not(I, E,199 [](const Iter &Insn) { return Insn->isTransient(); });200 201 return I;202}203 204// Find the next real instruction from the current position, looking through205// basic block boundaries.206static std::pair<Iter, bool> getNextMachineInstr(Iter Position,207 MachineBasicBlock *Parent) {208 if (Position == Parent->end()) {209 do {210 MachineBasicBlock *Succ = Parent->getNextNode();211 if (Succ != nullptr && Parent->isSuccessor(Succ)) {212 Position = Succ->begin();213 Parent = Succ;214 } else {215 return std::make_pair(Position, true);216 }217 } while (Parent->empty());218 }219 220 Iter Instr = getNextMachineInstrInBB(Position);221 if (Instr == Parent->end()) {222 return getNextMachineInstr(Instr, Parent);223 }224 return std::make_pair(Instr, false);225}226 227/// Iterate over list of Br's operands and search for a MachineBasicBlock228/// operand.229static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {230 for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {231 const MachineOperand &MO = Br.getOperand(I);232 233 if (MO.isMBB())234 return MO.getMBB();235 }236 237 llvm_unreachable("This instruction does not have an MBB operand.");238}239 240// Traverse the list of instructions backwards until a non-debug instruction is241// found or it reaches E.242static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) {243 for (; B != E; ++B)244 if (!B->isDebugInstr())245 return B;246 247 return E;248}249 250// Split MBB if it has two direct jumps/branches.251void MipsBranchExpansion::splitMBB(MachineBasicBlock *MBB) {252 ReverseIter End = MBB->rend();253 ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);254 255 // Return if MBB has no branch instructions.256 if ((LastBr == End) ||257 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))258 return;259 260 ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);261 262 // MBB has only one branch instruction if FirstBr is not a branch263 // instruction.264 if ((FirstBr == End) ||265 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))266 return;267 268 assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");269 270 // Create a new MBB. Move instructions in MBB to the newly created MBB.271 MachineBasicBlock *NewMBB =272 MFp->CreateMachineBasicBlock(MBB->getBasicBlock());273 274 // Insert NewMBB and fix control flow.275 MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);276 NewMBB->transferSuccessors(MBB);277 if (Tgt != getTargetMBB(*LastBr))278 NewMBB->removeSuccessor(Tgt, true);279 MBB->addSuccessor(NewMBB);280 MBB->addSuccessor(Tgt);281 MFp->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);282 283 NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->end());284}285 286// Fill MBBInfos.287void MipsBranchExpansion::initMBBInfo() {288 // Split the MBBs if they have two branches. Each basic block should have at289 // most one branch after this loop is executed.290 for (auto &MBB : *MFp)291 splitMBB(&MBB);292 293 MFp->RenumberBlocks();294 MBBInfos.clear();295 MBBInfos.resize(MFp->size());296 297 for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {298 MachineBasicBlock *MBB = MFp->getBlockNumbered(I);299 300 // Compute size of MBB.301 for (MachineInstr &MI : MBB->instrs())302 MBBInfos[I].Size += TII->getInstSizeInBytes(MI);303 }304}305 306// Compute offset of branch in number of bytes.307int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) {308 int64_t Offset = 0;309 int ThisMBB = Br->getParent()->getNumber();310 int TargetMBB = getTargetMBB(*Br)->getNumber();311 312 // Compute offset of a forward branch.313 if (ThisMBB < TargetMBB) {314 for (int N = ThisMBB + 1; N < TargetMBB; ++N)315 Offset += MBBInfos[N].Size;316 317 return Offset + 4;318 }319 320 // Compute offset of a backward branch.321 for (int N = ThisMBB; N >= TargetMBB; --N)322 Offset += MBBInfos[N].Size;323 324 return -Offset + 4;325}326 327// Returns the distance in bytes up until MBB328uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(int MBB) {329 uint64_t Offset = 0;330 for (int N = 0; N < MBB; ++N)331 Offset += MBBInfos[N].Size;332 return Offset;333}334 335// Replace Br with a branch which has the opposite condition code and a336// MachineBasicBlock operand MBBOpnd.337void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,338 const DebugLoc &DL,339 MachineBasicBlock *MBBOpnd) {340 unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());341 const MCInstrDesc &NewDesc = TII->get(NewOpc);342 343 MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);344 345 for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {346 MachineOperand &MO = Br->getOperand(I);347 348 switch (MO.getType()) {349 case MachineOperand::MO_Register:350 MIB.addReg(MO.getReg());351 break;352 case MachineOperand::MO_Immediate:353 // Octeon BBIT family of branch has an immediate operand354 // (e.g. BBIT0 $v0, 3, %bb.1).355 if (!TII->isBranchWithImm(Br->getOpcode()))356 llvm_unreachable("Unexpected immediate in branch instruction");357 MIB.addImm(MO.getImm());358 break;359 case MachineOperand::MO_MachineBasicBlock:360 MIB.addMBB(MBBOpnd);361 break;362 default:363 llvm_unreachable("Unexpected operand type in branch instruction");364 }365 }366 367 if (Br->hasDelaySlot()) {368 // Bundle the instruction in the delay slot to the newly created branch369 // and erase the original branch.370 assert(Br->isBundledWithSucc());371 MachineBasicBlock::instr_iterator II = Br.getInstrIterator();372 MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());373 }374 Br->eraseFromParent();375}376 377bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,378 MachineBasicBlock::iterator Pos,379 DebugLoc DL) {380 bool HasR6 = ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();381 bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();382 383 unsigned JR = ABI.IsN64() ? Mips::JR64 : Mips::JR;384 unsigned JIC = ABI.IsN64() ? Mips::JIC64 : Mips::JIC;385 unsigned JR_HB = ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;386 unsigned JR_HB_R6 = ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;387 388 unsigned JumpOp;389 if (STI->useIndirectJumpsHazard())390 JumpOp = HasR6 ? JR_HB_R6 : JR_HB;391 else392 JumpOp = HasR6 ? JIC : JR;393 394 if (JumpOp == Mips::JIC && STI->inMicroMipsMode())395 JumpOp = Mips::JIC_MMR6;396 397 unsigned ATReg = ABI.IsN64() ? Mips::AT_64 : Mips::AT;398 MachineInstrBuilder Instr =399 BuildMI(*MBB, Pos, DL, TII->get(JumpOp)).addReg(ATReg);400 if (AddImm)401 Instr.addImm(0);402 403 return !AddImm;404}405 406// Expand branch instructions to long branches.407// TODO: This function has to be fixed for beqz16 and bnez16, because it408// currently assumes that all branches have 16-bit offsets, and will produce409// wrong code if branches whose allowed offsets are [-128, -126, ..., 126]410// are present.411void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {412 MachineBasicBlock::iterator Pos;413 MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);414 DebugLoc DL = I.Br->getDebugLoc();415 const BasicBlock *BB = MBB->getBasicBlock();416 MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);417 MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);418 419 MFp->insert(FallThroughMBB, LongBrMBB);420 MBB->replaceSuccessor(TgtMBB, LongBrMBB);421 422 if (IsPIC) {423 MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);424 MFp->insert(FallThroughMBB, BalTgtMBB);425 LongBrMBB->addSuccessor(BalTgtMBB);426 BalTgtMBB->addSuccessor(TgtMBB);427 428 // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal429 // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an430 // pseudo-instruction wrapping BGEZAL).431 const unsigned BalOp =432 STI->hasMips32r6()433 ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC434 : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;435 436 if (!ABI.IsN64()) {437 // Pre R6:438 // $longbr:439 // addiu $sp, $sp, -8440 // sw $ra, 0($sp)441 // lui $at, %hi($tgt - $baltgt)442 // bal $baltgt443 // addiu $at, $at, %lo($tgt - $baltgt)444 // $baltgt:445 // addu $at, $ra, $at446 // lw $ra, 0($sp)447 // jr $at448 // addiu $sp, $sp, 8449 // $fallthrough:450 //451 452 // R6:453 // $longbr:454 // addiu $sp, $sp, -8455 // sw $ra, 0($sp)456 // lui $at, %hi($tgt - $baltgt)457 // addiu $at, $at, %lo($tgt - $baltgt)458 // balc $baltgt459 // $baltgt:460 // addu $at, $ra, $at461 // lw $ra, 0($sp)462 // addiu $sp, $sp, 8463 // jic $at, 0464 // $fallthrough:465 466 Pos = LongBrMBB->begin();467 468 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)469 .addReg(Mips::SP)470 .addImm(-8);471 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))472 .addReg(Mips::RA)473 .addReg(Mips::SP)474 .addImm(0);475 476 // LUi and ADDiu instructions create 32-bit offset of the target basic477 // block from the target of BAL(C) instruction. We cannot use immediate478 // value for this offset because it cannot be determined accurately when479 // the program has inline assembly statements. We therefore use the480 // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which481 // are resolved during the fixup, so the values will always be correct.482 //483 // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)484 // expressions at this point (it is possible only at the MC layer),485 // we replace LUi and ADDiu with pseudo instructions486 // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic487 // blocks as operands to these instructions. When lowering these pseudo488 // instructions to LUi and ADDiu in the MC layer, we will create489 // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as490 // operands to lowered instructions.491 492 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)493 .addMBB(TgtMBB, MipsII::MO_ABS_HI)494 .addMBB(BalTgtMBB);495 496 MachineInstrBuilder BalInstr =497 BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);498 MachineInstrBuilder ADDiuInstr =499 BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)500 .addReg(Mips::AT)501 .addMBB(TgtMBB, MipsII::MO_ABS_LO)502 .addMBB(BalTgtMBB);503 if (STI->hasMips32r6()) {504 LongBrMBB->insert(Pos, ADDiuInstr);505 LongBrMBB->insert(Pos, BalInstr);506 } else {507 LongBrMBB->insert(Pos, BalInstr);508 LongBrMBB->insert(Pos, ADDiuInstr);509 LongBrMBB->rbegin()->bundleWithPred();510 }511 512 Pos = BalTgtMBB->begin();513 514 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)515 .addReg(Mips::RA)516 .addReg(Mips::AT);517 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)518 .addReg(Mips::SP)519 .addImm(0);520 521 // For MIPS32R6, we can skip using a delay slot branch.522 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);523 524 if (!hasDelaySlot) {525 BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::ADDiu), Mips::SP)526 .addReg(Mips::SP)527 .addImm(8);528 }529 if (hasDelaySlot) {530 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)531 .addReg(Mips::SP)532 .addImm(8);533 BalTgtMBB->rbegin()->bundleWithPred();534 }535 } else {536 // Pre R6:537 // $longbr:538 // daddiu $sp, $sp, -16539 // sd $ra, 0($sp)540 // daddiu $at, $zero, %hi($tgt - $baltgt)541 // dsll $at, $at, 16542 // bal $baltgt543 // daddiu $at, $at, %lo($tgt - $baltgt)544 // $baltgt:545 // daddu $at, $ra, $at546 // ld $ra, 0($sp)547 // jr64 $at548 // daddiu $sp, $sp, 16549 // $fallthrough:550 551 // R6:552 // $longbr:553 // daddiu $sp, $sp, -16554 // sd $ra, 0($sp)555 // daddiu $at, $zero, %hi($tgt - $baltgt)556 // dsll $at, $at, 16557 // daddiu $at, $at, %lo($tgt - $baltgt)558 // balc $baltgt559 // $baltgt:560 // daddu $at, $ra, $at561 // ld $ra, 0($sp)562 // daddiu $sp, $sp, 16563 // jic $at, 0564 // $fallthrough:565 566 // We assume the branch is within-function, and that offset is within567 // +/- 2GB. High 32 bits will therefore always be zero.568 569 // Note that this will work even if the offset is negative, because570 // of the +1 modification that's added in that case. For example, if the571 // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is572 //573 // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000574 //575 // and the bits [47:32] are zero. For %highest576 //577 // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000578 //579 // and the bits [63:48] are zero.580 581 Pos = LongBrMBB->begin();582 583 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)584 .addReg(Mips::SP_64)585 .addImm(-16);586 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))587 .addReg(Mips::RA_64)588 .addReg(Mips::SP_64)589 .addImm(0);590 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),591 Mips::AT_64)592 .addReg(Mips::ZERO_64)593 .addMBB(TgtMBB, MipsII::MO_ABS_HI)594 .addMBB(BalTgtMBB);595 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)596 .addReg(Mips::AT_64)597 .addImm(16);598 599 MachineInstrBuilder BalInstr =600 BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);601 MachineInstrBuilder DADDiuInstr =602 BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)603 .addReg(Mips::AT_64)604 .addMBB(TgtMBB, MipsII::MO_ABS_LO)605 .addMBB(BalTgtMBB);606 if (STI->hasMips32r6()) {607 LongBrMBB->insert(Pos, DADDiuInstr);608 LongBrMBB->insert(Pos, BalInstr);609 } else {610 LongBrMBB->insert(Pos, BalInstr);611 LongBrMBB->insert(Pos, DADDiuInstr);612 LongBrMBB->rbegin()->bundleWithPred();613 }614 615 Pos = BalTgtMBB->begin();616 617 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)618 .addReg(Mips::RA_64)619 .addReg(Mips::AT_64);620 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)621 .addReg(Mips::SP_64)622 .addImm(0);623 624 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);625 // If there is no delay slot, Insert stack adjustment before626 if (!hasDelaySlot) {627 BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::DADDiu),628 Mips::SP_64)629 .addReg(Mips::SP_64)630 .addImm(16);631 } else {632 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)633 .addReg(Mips::SP_64)634 .addImm(16);635 BalTgtMBB->rbegin()->bundleWithPred();636 }637 }638 } else { // Not PIC639 Pos = LongBrMBB->begin();640 LongBrMBB->addSuccessor(TgtMBB);641 642 // Compute the position of the potentiall jump instruction (basic blocks643 // before + 4 for the instruction)644 uint64_t JOffset = computeOffsetFromTheBeginning(MBB->getNumber()) +645 MBBInfos[MBB->getNumber()].Size + 4;646 uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());647 // If it's a forward jump, then TgtMBBOffset will be shifted by two648 // instructions649 if (JOffset < TgtMBBOffset)650 TgtMBBOffset += 2 * 4;651 // Compare 4 upper bits to check if it's the same segment652 bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;653 654 if (STI->hasMips32r6() && TII->isBranchOffsetInRange(Mips::BC, I.Offset)) {655 // R6:656 // $longbr:657 // bc $tgt658 // $fallthrough:659 //660 BuildMI(*LongBrMBB, Pos, DL,661 TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))662 .addMBB(TgtMBB);663 } else if (SameSegmentJump) {664 // Pre R6:665 // $longbr:666 // j $tgt667 // nop668 // $fallthrough:669 //670 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::J)).addMBB(TgtMBB);671 TII->insertNop(*LongBrMBB, Pos, DL)->bundleWithPred();672 } else {673 // At this point, offset where we need to branch does not fit into674 // immediate field of the branch instruction and is not in the same675 // segment as jump instruction. Therefore we will break it into couple676 // instructions, where we first load the offset into register, and then we677 // do branch register.678 if (ABI.IsN64()) {679 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op_64),680 Mips::AT_64)681 .addMBB(TgtMBB, MipsII::MO_HIGHEST);682 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),683 Mips::AT_64)684 .addReg(Mips::AT_64)685 .addMBB(TgtMBB, MipsII::MO_HIGHER);686 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)687 .addReg(Mips::AT_64)688 .addImm(16);689 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),690 Mips::AT_64)691 .addReg(Mips::AT_64)692 .addMBB(TgtMBB, MipsII::MO_ABS_HI);693 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)694 .addReg(Mips::AT_64)695 .addImm(16);696 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),697 Mips::AT_64)698 .addReg(Mips::AT_64)699 .addMBB(TgtMBB, MipsII::MO_ABS_LO);700 } else {701 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op),702 Mips::AT)703 .addMBB(TgtMBB, MipsII::MO_ABS_HI);704 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_ADDiu2Op),705 Mips::AT)706 .addReg(Mips::AT)707 .addMBB(TgtMBB, MipsII::MO_ABS_LO);708 }709 buildProperJumpMI(LongBrMBB, Pos, DL);710 }711 }712 713 if (I.Br->isUnconditionalBranch()) {714 // Change branch destination.715 assert(I.Br->getDesc().getNumOperands() == 1);716 I.Br->removeOperand(0);717 I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));718 } else719 // Change branch destination and reverse condition.720 replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);721}722 723static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {724 MachineBasicBlock &MBB = F.front();725 MachineBasicBlock::iterator I = MBB.begin();726 DebugLoc DL = MBB.findDebugLoc(MBB.begin());727 BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)728 .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);729 BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)730 .addReg(Mips::V0)731 .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);732 MBB.removeLiveIn(Mips::V0);733}734 735template <typename Pred, typename Safe>736bool MipsBranchExpansion::handleMFLOSlot(Pred Predicate, Safe SafeInSlot) {737 bool Changed = false;738 bool hasPendingMFLO = false;739 740 for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {741 for (Iter I = FI->begin(); I != FI->end(); ++I) {742 743 if (!Predicate(*I) && !hasPendingMFLO) {744 continue;745 }746 747 Iter IInSlot;748 bool LastInstInFunction =749 std::next(I) == FI->end() && std::next(FI) == MFp->end();750 // We need process several situations:751 // mflo is last instruction, do not process;752 // mflo + div, add two nop between them;753 // mflo + none-div + none-div, do not process;754 // mflo + none-div + div, add nop between none-div and div.755 if (!LastInstInFunction) {756 std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);757 LastInstInFunction |= Res.second;758 IInSlot = Res.first;759 if (LastInstInFunction)760 continue;761 if (!SafeInSlot(*IInSlot, *I)) {762 Changed = true;763 TII->insertNop(*(I->getParent()), std::next(I), I->getDebugLoc())764 ->bundleWithPred();765 NumInsertedNops++;766 if (IsMFLOMFHI(I->getOpcode())) {767 TII->insertNop(*(I->getParent()), std::next(I), I->getDebugLoc())768 ->bundleWithPred();769 NumInsertedNops++;770 }771 if (hasPendingMFLO)772 hasPendingMFLO = false;773 } else if (hasPendingMFLO)774 hasPendingMFLO = false;775 else if (IsMFLOMFHI(I->getOpcode()))776 hasPendingMFLO = true;777 }778 }779 }780 781 return Changed;782}783 784template <typename Pred, typename Safe>785bool MipsBranchExpansion::handleSlot(Pred Predicate, Safe SafeInSlot) {786 bool Changed = false;787 788 for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {789 for (Iter I = FI->begin(); I != FI->end(); ++I) {790 791 // Delay slot hazard handling. Use lookahead over state.792 if (!Predicate(*I))793 continue;794 795 Iter IInSlot;796 bool LastInstInFunction =797 std::next(I) == FI->end() && std::next(FI) == MFp->end();798 if (!LastInstInFunction) {799 std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);800 LastInstInFunction |= Res.second;801 IInSlot = Res.first;802 }803 804 if (LastInstInFunction || !SafeInSlot(*IInSlot, *I)) {805 MachineBasicBlock::instr_iterator Iit = I->getIterator();806 if (std::next(Iit) == FI->end() ||807 std::next(Iit)->getOpcode() != Mips::NOP) {808 Changed = true;809 TII->insertNop(*(I->getParent()), std::next(I), I->getDebugLoc())810 ->bundleWithPred();811 NumInsertedNops++;812 }813 }814 }815 }816 817 return Changed;818}819 820bool MipsBranchExpansion::handleMFLO() {821 // mips1-4 require a minimum of 2 instructions between a mflo/mfhi822 // and the next mul/div instruction.823 if (STI->hasMips32() || STI->hasMips5())824 return false;825 826 return handleMFLOSlot(827 [this](auto &I) -> bool { return TII->IsMfloOrMfhi(I); },828 [this](auto &IInSlot, auto &I) -> bool {829 return TII->SafeAfterMflo(IInSlot);830 });831}832 833bool MipsBranchExpansion::handleForbiddenSlot() {834 // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.835 if (!STI->hasMips32r6() || STI->inMicroMipsMode())836 return false;837 838 return handleSlot(839 [this](auto &I) -> bool { return TII->HasForbiddenSlot(I); },840 [this](auto &IInSlot, auto &I) -> bool {841 return TII->SafeInForbiddenSlot(IInSlot);842 });843}844 845bool MipsBranchExpansion::handleFPUDelaySlot() {846 // FPU delay slots are only defined for MIPS3 and below.847 if (STI->hasMips32() || STI->hasMips4())848 return false;849 850 return handleSlot([this](auto &I) -> bool { return TII->HasFPUDelaySlot(I); },851 [this](auto &IInSlot, auto &I) -> bool {852 return TII->SafeInFPUDelaySlot(IInSlot, I);853 });854}855 856bool MipsBranchExpansion::handleLoadDelaySlot() {857 // Load delay slot hazards are only for MIPS1.858 if (STI->hasMips2())859 return false;860 861 return handleSlot(862 [this](auto &I) -> bool { return TII->HasLoadDelaySlot(I); },863 [this](auto &IInSlot, auto &I) -> bool {864 return TII->SafeInLoadDelaySlot(IInSlot, I);865 });866}867 868bool MipsBranchExpansion::handlePossibleLongBranch() {869 if (STI->inMips16Mode() || !STI->enableLongBranchPass())870 return false;871 872 if (SkipLongBranch)873 return false;874 875 bool EverMadeChange = false, MadeChange = true;876 877 while (MadeChange) {878 MadeChange = false;879 880 initMBBInfo();881 882 for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {883 MachineBasicBlock *MBB = MFp->getBlockNumbered(I);884 // Search for MBB's branch instruction.885 ReverseIter End = MBB->rend();886 ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);887 888 if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&889 (Br->isConditionalBranch() ||890 (Br->isUnconditionalBranch() && IsPIC))) {891 int64_t Offset = computeOffset(&*Br);892 893 if (ForceLongBranchFirstPass ||894 !TII->isBranchOffsetInRange(Br->getOpcode(), Offset)) {895 MBBInfos[I].Offset = Offset;896 MBBInfos[I].Br = &*Br;897 }898 }899 } // End for900 901 ForceLongBranchFirstPass = false;902 903 SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();904 905 for (I = MBBInfos.begin(); I != E; ++I) {906 // Skip if this MBB doesn't have a branch or the branch has already been907 // converted to a long branch.908 if (!I->Br)909 continue;910 911 expandToLongBranch(*I);912 ++LongBranches;913 EverMadeChange = MadeChange = true;914 }915 916 MFp->RenumberBlocks();917 }918 919 return EverMadeChange;920}921 922bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {923 const TargetMachine &TM = MF.getTarget();924 IsPIC = TM.isPositionIndependent();925 ABI = static_cast<const MipsTargetMachine &>(TM).getABI();926 STI = &MF.getSubtarget<MipsSubtarget>();927 TII = STI->getInstrInfo();928 929 if (IsPIC && ABI.IsO32() &&930 MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())931 emitGPDisp(MF, TII);932 933 MFp = &MF;934 935 ForceLongBranchFirstPass = ForceLongBranch;936 // Run these at least once.937 bool longBranchChanged = handlePossibleLongBranch();938 bool forbiddenSlotChanged = handleForbiddenSlot();939 bool fpuDelaySlotChanged = handleFPUDelaySlot();940 bool loadDelaySlotChanged = handleLoadDelaySlot();941 bool MfloChanged = handleMFLO();942 943 bool Changed = longBranchChanged || forbiddenSlotChanged ||944 fpuDelaySlotChanged || loadDelaySlotChanged || MfloChanged;945 946 // Then run them alternatively while there are changes.947 while (forbiddenSlotChanged) {948 longBranchChanged = handlePossibleLongBranch();949 fpuDelaySlotChanged = handleFPUDelaySlot();950 loadDelaySlotChanged = handleLoadDelaySlot();951 MfloChanged = handleMFLO();952 if (!longBranchChanged && !fpuDelaySlotChanged && !loadDelaySlotChanged &&953 !MfloChanged)954 break;955 forbiddenSlotChanged = handleForbiddenSlot();956 }957 958 return Changed;959}960