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