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