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