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 "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(Val: false),
113 cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden);
114
115static cl::opt<bool>
116 ForceLongBranch("force-mips-long-branch", cl::init(Val: 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 namespace
181
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 basic
195// block.
196static Iter getNextMachineInstrInBB(Iter Position) {
197 Iter I = Position, E = Position->getParent()->end();
198 I = std::find_if_not(first: I, last: E,
199 pred: [](const Iter &Insn) { return Insn->isTransient(); });
200
201 return I;
202}
203
204// Find the next real instruction from the current position, looking through
205// 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(MBB: Succ)) {
212 Position = Succ->begin();
213 Parent = Succ;
214 } else {
215 return std::make_pair(x&: Position, y: true);
216 }
217 } while (Parent->empty());
218 }
219
220 Iter Instr = getNextMachineInstrInBB(Position);
221 if (Instr == Parent->end()) {
222 return getNextMachineInstr(Position: Instr, Parent);
223 }
224 return std::make_pair(x&: Instr, y: false);
225}
226
227/// Iterate over list of Br's operands and search for a MachineBasicBlock
228/// 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: 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 is
241// 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(B: MBB->rbegin(), E: 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(B: std::next(x: LastBr), E: End);
261
262 // MBB has only one branch instruction if FirstBr is not a branch
263 // 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(BB: MBB->getBasicBlock());
273
274 // Insert NewMBB and fix control flow.
275 MachineBasicBlock *Tgt = getTargetMBB(Br: *FirstBr);
276 NewMBB->transferSuccessors(FromMBB: MBB);
277 if (Tgt != getTargetMBB(Br: *LastBr))
278 NewMBB->removeSuccessor(Succ: Tgt, NormalizeSuccProbs: true);
279 MBB->addSuccessor(Succ: NewMBB);
280 MBB->addSuccessor(Succ: Tgt);
281 MFp->insert(MBBI: std::next(x: MachineFunction::iterator(MBB)), MBB: NewMBB);
282
283 NewMBB->splice(Where: NewMBB->end(), Other: MBB, From: LastBr.getReverse(), To: MBB->end());
284}
285
286// Fill MBBInfos.
287void MipsBranchExpansion::initMBBInfo() {
288 // Split the MBBs if they have two branches. Each basic block should have at
289 // most one branch after this loop is executed.
290 for (auto &MBB : *MFp)
291 splitMBB(MBB: &MBB);
292
293 MFp->RenumberBlocks();
294 MBBInfos.clear();
295 MBBInfos.resize(N: MFp->size());
296
297 for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
298 MachineBasicBlock *MBB = MFp->getBlockNumbered(N: 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: *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 MBB
328uint64_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 a
336// MachineBasicBlock operand MBBOpnd.
337void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,
338 const DebugLoc &DL,
339 MachineBasicBlock *MBBOpnd) {
340 unsigned NewOpc = TII->getOppositeBranchOpc(Opc: Br->getOpcode());
341 const MCInstrDesc &NewDesc = TII->get(Opcode: NewOpc);
342
343 MachineInstrBuilder MIB = BuildMI(BB&: MBB, I: Br, MIMD: DL, MCID: NewDesc);
344
345 for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
346 MachineOperand &MO = Br->getOperand(i: I);
347
348 switch (MO.getType()) {
349 case MachineOperand::MO_Register:
350 MIB.addReg(RegNo: MO.getReg());
351 break;
352 case MachineOperand::MO_Immediate:
353 // Octeon BBIT family of branch has an immediate operand
354 // (e.g. BBIT0 $v0, 3, %bb.1).
355 if (!TII->isBranchWithImm(Opc: Br->getOpcode()))
356 llvm_unreachable("Unexpected immediate in branch instruction");
357 MIB.addImm(Val: MO.getImm());
358 break;
359 case MachineOperand::MO_MachineBasicBlock:
360 MIB.addMBB(MBB: 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 branch
369 // and erase the original branch.
370 assert(Br->isBundledWithSucc());
371 MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
372 MIBundleBuilder(&*MIB).append(MI: (++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 else
392 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(BB&: *MBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: JumpOp)).addReg(RegNo: ATReg);
400 if (AddImm)
401 Instr.addImm(Val: 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 it
408// currently assumes that all branches have 16-bit offsets, and will produce
409// 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(Br: *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(MBBI: FallThroughMBB, MBB: LongBrMBB);
420 MBB->replaceSuccessor(Old: TgtMBB, New: LongBrMBB);
421
422 if (IsPIC) {
423 MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
424 MFp->insert(MBBI: FallThroughMBB, MBB: BalTgtMBB);
425 LongBrMBB->addSuccessor(Succ: BalTgtMBB);
426 BalTgtMBB->addSuccessor(Succ: TgtMBB);
427
428 // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
429 // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
430 // pseudo-instruction wrapping BGEZAL).
431 const unsigned BalOp =
432 STI->hasMips32r6()
433 ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
434 : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
435
436 if (!ABI.IsN64()) {
437 // Pre R6:
438 // $longbr:
439 // addiu $sp, $sp, -8
440 // sw $ra, 0($sp)
441 // lui $at, %hi($tgt - $baltgt)
442 // bal $baltgt
443 // addiu $at, $at, %lo($tgt - $baltgt)
444 // $baltgt:
445 // addu $at, $ra, $at
446 // lw $ra, 0($sp)
447 // jr $at
448 // addiu $sp, $sp, 8
449 // $fallthrough:
450 //
451
452 // R6:
453 // $longbr:
454 // addiu $sp, $sp, -8
455 // sw $ra, 0($sp)
456 // lui $at, %hi($tgt - $baltgt)
457 // addiu $at, $at, %lo($tgt - $baltgt)
458 // balc $baltgt
459 // $baltgt:
460 // addu $at, $ra, $at
461 // lw $ra, 0($sp)
462 // addiu $sp, $sp, 8
463 // jic $at, 0
464 // $fallthrough:
465
466 Pos = LongBrMBB->begin();
467
468 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::ADDiu), DestReg: Mips::SP)
469 .addReg(RegNo: Mips::SP)
470 .addImm(Val: -8);
471 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::SW))
472 .addReg(RegNo: Mips::RA)
473 .addReg(RegNo: Mips::SP)
474 .addImm(Val: 0);
475
476 // LUi and ADDiu instructions create 32-bit offset of the target basic
477 // block from the target of BAL(C) instruction. We cannot use immediate
478 // value for this offset because it cannot be determined accurately when
479 // the program has inline assembly statements. We therefore use the
480 // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
481 // 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 instructions
486 // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
487 // blocks as operands to these instructions. When lowering these pseudo
488 // instructions to LUi and ADDiu in the MC layer, we will create
489 // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
490 // operands to lowered instructions.
491
492 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_LUi), DestReg: Mips::AT)
493 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_HI)
494 .addMBB(MBB: BalTgtMBB);
495
496 MachineInstrBuilder BalInstr =
497 BuildMI(MF&: *MFp, MIMD: DL, MCID: TII->get(Opcode: BalOp)).addMBB(MBB: BalTgtMBB);
498 MachineInstrBuilder ADDiuInstr =
499 BuildMI(MF&: *MFp, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_ADDiu), DestReg: Mips::AT)
500 .addReg(RegNo: Mips::AT)
501 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_LO)
502 .addMBB(MBB: BalTgtMBB);
503 if (STI->hasMips32r6()) {
504 LongBrMBB->insert(I: Pos, MI: ADDiuInstr);
505 LongBrMBB->insert(I: Pos, MI: BalInstr);
506 } else {
507 LongBrMBB->insert(I: Pos, MI: BalInstr);
508 LongBrMBB->insert(I: Pos, MI: ADDiuInstr);
509 LongBrMBB->rbegin()->bundleWithPred();
510 }
511
512 Pos = BalTgtMBB->begin();
513
514 BuildMI(BB&: *BalTgtMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::ADDu), DestReg: Mips::AT)
515 .addReg(RegNo: Mips::RA)
516 .addReg(RegNo: Mips::AT);
517 BuildMI(BB&: *BalTgtMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LW), DestReg: Mips::RA)
518 .addReg(RegNo: Mips::SP)
519 .addImm(Val: 0);
520
521 // For MIPS32R6, we can skip using a delay slot branch.
522 bool hasDelaySlot = buildProperJumpMI(MBB: BalTgtMBB, Pos, DL);
523
524 if (!hasDelaySlot) {
525 BuildMI(BB&: *BalTgtMBB, I: std::prev(x: Pos), MIMD: DL, MCID: TII->get(Opcode: Mips::ADDiu), DestReg: Mips::SP)
526 .addReg(RegNo: Mips::SP)
527 .addImm(Val: 8);
528 }
529 if (hasDelaySlot) {
530 BuildMI(BB&: *BalTgtMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::ADDiu), DestReg: Mips::SP)
531 .addReg(RegNo: Mips::SP)
532 .addImm(Val: 8);
533 BalTgtMBB->rbegin()->bundleWithPred();
534 }
535 } else {
536 // Pre R6:
537 // $longbr:
538 // daddiu $sp, $sp, -16
539 // sd $ra, 0($sp)
540 // daddiu $at, $zero, %hi($tgt - $baltgt)
541 // dsll $at, $at, 16
542 // bal $baltgt
543 // daddiu $at, $at, %lo($tgt - $baltgt)
544 // $baltgt:
545 // daddu $at, $ra, $at
546 // ld $ra, 0($sp)
547 // jr64 $at
548 // daddiu $sp, $sp, 16
549 // $fallthrough:
550
551 // R6:
552 // $longbr:
553 // daddiu $sp, $sp, -16
554 // sd $ra, 0($sp)
555 // daddiu $at, $zero, %hi($tgt - $baltgt)
556 // dsll $at, $at, 16
557 // daddiu $at, $at, %lo($tgt - $baltgt)
558 // balc $baltgt
559 // $baltgt:
560 // daddu $at, $ra, $at
561 // ld $ra, 0($sp)
562 // daddiu $sp, $sp, 16
563 // jic $at, 0
564 // $fallthrough:
565
566 // We assume the branch is within-function, and that offset is within
567 // +/- 2GB. High 32 bits will therefore always be zero.
568
569 // Note that this will work even if the offset is negative, because
570 // of the +1 modification that's added in that case. For example, if the
571 // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
572 //
573 // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
574 //
575 // and the bits [47:32] are zero. For %highest
576 //
577 // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
578 //
579 // and the bits [63:48] are zero.
580
581 Pos = LongBrMBB->begin();
582
583 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::DADDiu), DestReg: Mips::SP_64)
584 .addReg(RegNo: Mips::SP_64)
585 .addImm(Val: -16);
586 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::SD))
587 .addReg(RegNo: Mips::RA_64)
588 .addReg(RegNo: Mips::SP_64)
589 .addImm(Val: 0);
590 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_DADDiu),
591 DestReg: Mips::AT_64)
592 .addReg(RegNo: Mips::ZERO_64)
593 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_HI)
594 .addMBB(MBB: BalTgtMBB);
595 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::DSLL), DestReg: Mips::AT_64)
596 .addReg(RegNo: Mips::AT_64)
597 .addImm(Val: 16);
598
599 MachineInstrBuilder BalInstr =
600 BuildMI(MF&: *MFp, MIMD: DL, MCID: TII->get(Opcode: BalOp)).addMBB(MBB: BalTgtMBB);
601 MachineInstrBuilder DADDiuInstr =
602 BuildMI(MF&: *MFp, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_DADDiu), DestReg: Mips::AT_64)
603 .addReg(RegNo: Mips::AT_64)
604 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_LO)
605 .addMBB(MBB: BalTgtMBB);
606 if (STI->hasMips32r6()) {
607 LongBrMBB->insert(I: Pos, MI: DADDiuInstr);
608 LongBrMBB->insert(I: Pos, MI: BalInstr);
609 } else {
610 LongBrMBB->insert(I: Pos, MI: BalInstr);
611 LongBrMBB->insert(I: Pos, MI: DADDiuInstr);
612 LongBrMBB->rbegin()->bundleWithPred();
613 }
614
615 Pos = BalTgtMBB->begin();
616
617 BuildMI(BB&: *BalTgtMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::DADDu), DestReg: Mips::AT_64)
618 .addReg(RegNo: Mips::RA_64)
619 .addReg(RegNo: Mips::AT_64);
620 BuildMI(BB&: *BalTgtMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LD), DestReg: Mips::RA_64)
621 .addReg(RegNo: Mips::SP_64)
622 .addImm(Val: 0);
623
624 bool hasDelaySlot = buildProperJumpMI(MBB: BalTgtMBB, Pos, DL);
625 // If there is no delay slot, Insert stack adjustment before
626 if (!hasDelaySlot) {
627 BuildMI(BB&: *BalTgtMBB, I: std::prev(x: Pos), MIMD: DL, MCID: TII->get(Opcode: Mips::DADDiu),
628 DestReg: Mips::SP_64)
629 .addReg(RegNo: Mips::SP_64)
630 .addImm(Val: 16);
631 } else {
632 BuildMI(BB&: *BalTgtMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::DADDiu), DestReg: Mips::SP_64)
633 .addReg(RegNo: Mips::SP_64)
634 .addImm(Val: 16);
635 BalTgtMBB->rbegin()->bundleWithPred();
636 }
637 }
638 } else { // Not PIC
639 Pos = LongBrMBB->begin();
640 LongBrMBB->addSuccessor(Succ: TgtMBB);
641
642 // Compute the position of the potentiall jump instruction (basic blocks
643 // before + 4 for the instruction)
644 uint64_t JOffset = computeOffsetFromTheBeginning(MBB: MBB->getNumber()) +
645 MBBInfos[MBB->getNumber()].Size + 4;
646 uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(MBB: TgtMBB->getNumber());
647 // If it's a forward jump, then TgtMBBOffset will be shifted by two
648 // instructions
649 if (JOffset < TgtMBBOffset)
650 TgtMBBOffset += 2 * 4;
651 // Compare 4 upper bits to check if it's the same segment
652 bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
653
654 if (STI->hasMips32r6() && TII->isBranchOffsetInRange(BranchOpc: Mips::BC, BrOffset: I.Offset)) {
655 // R6:
656 // $longbr:
657 // bc $tgt
658 // $fallthrough:
659 //
660 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL,
661 MCID: TII->get(Opcode: STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
662 .addMBB(MBB: TgtMBB);
663 } else if (SameSegmentJump) {
664 // Pre R6:
665 // $longbr:
666 // j $tgt
667 // nop
668 // $fallthrough:
669 //
670 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::J)).addMBB(MBB: TgtMBB);
671 TII->insertNop(MBB&: *LongBrMBB, MI: Pos, DL)->bundleWithPred();
672 } else {
673 // At this point, offset where we need to branch does not fit into
674 // immediate field of the branch instruction and is not in the same
675 // segment as jump instruction. Therefore we will break it into couple
676 // instructions, where we first load the offset into register, and then we
677 // do branch register.
678 if (ABI.IsN64()) {
679 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_LUi2Op_64),
680 DestReg: Mips::AT_64)
681 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_HIGHEST);
682 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_DADDiu2Op),
683 DestReg: Mips::AT_64)
684 .addReg(RegNo: Mips::AT_64)
685 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_HIGHER);
686 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::DSLL), DestReg: Mips::AT_64)
687 .addReg(RegNo: Mips::AT_64)
688 .addImm(Val: 16);
689 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_DADDiu2Op),
690 DestReg: Mips::AT_64)
691 .addReg(RegNo: Mips::AT_64)
692 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_HI);
693 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::DSLL), DestReg: Mips::AT_64)
694 .addReg(RegNo: Mips::AT_64)
695 .addImm(Val: 16);
696 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_DADDiu2Op),
697 DestReg: Mips::AT_64)
698 .addReg(RegNo: Mips::AT_64)
699 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_LO);
700 } else {
701 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_LUi2Op),
702 DestReg: Mips::AT)
703 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_HI);
704 BuildMI(BB&: *LongBrMBB, I: Pos, MIMD: DL, MCID: TII->get(Opcode: Mips::LONG_BRANCH_ADDiu2Op),
705 DestReg: Mips::AT)
706 .addReg(RegNo: Mips::AT)
707 .addMBB(MBB: TgtMBB, TargetFlags: MipsII::MO_ABS_LO);
708 }
709 buildProperJumpMI(MBB: 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(OpNo: 0);
717 I.Br->addOperand(Op: MachineOperand::CreateMBB(MBB: LongBrMBB));
718 } else
719 // Change branch destination and reverse condition.
720 replaceBranch(MBB&: *MBB, Br: I.Br, DL, MBBOpnd: &*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(MBBI: MBB.begin());
727 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: Mips::LUi), DestReg: Mips::V0)
728 .addExternalSymbol(FnName: "_gp_disp", TargetFlags: MipsII::MO_ABS_HI);
729 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: Mips::ADDiu), DestReg: Mips::V0)
730 .addReg(RegNo: Mips::V0)
731 .addExternalSymbol(FnName: "_gp_disp", TargetFlags: MipsII::MO_ABS_LO);
732 MBB.removeLiveIn(Reg: 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(x: I) == FI->end() && std::next(x: 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(Position: std::next(x: I), Parent: &*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(MBB&: *(I->getParent()), MI: std::next(x: I), DL: I->getDebugLoc())
764 ->bundleWithPred();
765 NumInsertedNops++;
766 if (IsMFLOMFHI(I->getOpcode())) {
767 TII->insertNop(MBB&: *(I->getParent()), MI: std::next(x: I), DL: 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(x: I) == FI->end() && std::next(x: FI) == MFp->end();
798 if (!LastInstInFunction) {
799 std::pair<Iter, bool> Res = getNextMachineInstr(Position: std::next(x: I), Parent: &*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(x: Iit) == FI->end() ||
807 std::next(x: Iit)->getOpcode() != Mips::NOP) {
808 Changed = true;
809 TII->insertNop(MBB&: *(I->getParent()), MI: std::next(x: I), DL: 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/mfhi
822 // and the next mul/div instruction.
823 if (STI->hasMips32() || STI->hasMips5())
824 return false;
825
826 return handleMFLOSlot(
827 Predicate: [this](auto &I) -> bool { return TII->IsMfloOrMfhi(MI: I); },
828 SafeInSlot: [this](auto &IInSlot, auto &I) -> bool {
829 return TII->SafeAfterMflo(MI: 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 Predicate: [this](auto &I) -> bool { return TII->HasForbiddenSlot(MI: I); },
840 SafeInSlot: [this](auto &IInSlot, auto &I) -> bool {
841 return TII->SafeInForbiddenSlot(MI: 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(Predicate: [this](auto &I) -> bool { return TII->HasFPUDelaySlot(MI: I); },
851 SafeInSlot: [this](auto &IInSlot, auto &I) -> bool {
852 return TII->SafeInFPUDelaySlot(MIInSlot: IInSlot, FPUMI: 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 Predicate: [this](auto &I) -> bool { return TII->HasLoadDelaySlot(MI: I); },
863 SafeInSlot: [this](auto &IInSlot, auto &I) -> bool {
864 return TII->SafeInLoadDelaySlot(MIInSlot: IInSlot, LoadMI: 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(N: I);
884 // Search for MBB's branch instruction.
885 ReverseIter End = MBB->rend();
886 ReverseIter Br = getNonDebugInstr(B: MBB->rbegin(), E: End);
887
888 if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&
889 (Br->isConditionalBranch() ||
890 (Br->isUnconditionalBranch() && IsPIC))) {
891 int64_t Offset = computeOffset(Br: &*Br);
892
893 if (ForceLongBranchFirstPass ||
894 !TII->isBranchOffsetInRange(BranchOpc: Br->getOpcode(), BrOffset: Offset)) {
895 MBBInfos[I].Offset = Offset;
896 MBBInfos[I].Br = &*Br;
897 }
898 }
899 } // End for
900
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 been
907 // converted to a long branch.
908 if (!I->Br)
909 continue;
910
911 expandToLongBranch(I&: *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(F&: 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