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