LLVM  12.0.0git
MipsBranchExpansion.cpp
Go to the documentation of this file.
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.
40 ///
41 /// A forbidden slot hazard occurs when a compact branch instruction is executed
42 /// and the adjacent instruction in memory is a control transfer instruction
43 /// such as a branch or jump, ERET, ERETNC, DERET, WAIT and PAUSE.
44 ///
45 /// For example:
46 ///
47 /// 0x8004 bnec a1,v0,<P+0x18>
48 /// 0x8008 beqc a1,a2,<P+0x54>
49 ///
50 /// In such cases, the processor is required to signal a Reserved Instruction
51 /// exception.
52 ///
53 /// Here, if the instruction at 0x8004 is executed, the processor will raise an
54 /// exception as there is a control transfer instruction at 0x8008.
55 ///
56 /// There are two sources of forbidden slot hazards:
57 ///
58 /// A) A previous pass has created a compact branch directly.
59 /// B) Transforming a delay slot branch into compact branch. This case can be
60 /// difficult to process as lookahead for hazards is insufficient, as
61 /// backwards delay slot fillling can also produce hazards in previously
62 /// processed instuctions.
63 ///
64 /// In future this pass can be extended (or new pass can be created) to handle
65 /// other pipeline hazards, such as various MIPS1 hazards, processor errata that
66 /// require instruction reorganization, etc.
67 ///
68 /// This pass has to run after the delay slot filler as that pass can introduce
69 /// pipeline hazards such as compact branch hazard, hence the existing hazard
70 /// recognizer is not suitable.
71 ///
72 //===----------------------------------------------------------------------===//
73 
78 #include "Mips.h"
79 #include "MipsInstrInfo.h"
80 #include "MipsMachineFunction.h"
81 #include "MipsSubtarget.h"
82 #include "MipsTargetMachine.h"
83 #include "llvm/ADT/SmallVector.h"
84 #include "llvm/ADT/Statistic.h"
85 #include "llvm/ADT/StringRef.h"
94 #include "llvm/IR/DebugLoc.h"
99 #include <algorithm>
100 #include <cassert>
101 #include <cstdint>
102 #include <iterator>
103 #include <utility>
104 
105 using namespace llvm;
106 
107 #define DEBUG_TYPE "mips-branch-expansion"
108 
109 STATISTIC(NumInsertedNops, "Number of nops inserted");
110 STATISTIC(LongBranches, "Number of long branches.");
111 
112 static cl::opt<bool>
113  SkipLongBranch("skip-mips-long-branch", cl::init(false),
114  cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden);
115 
116 static cl::opt<bool>
117  ForceLongBranch("force-mips-long-branch", cl::init(false),
118  cl::desc("MIPS: Expand all branches to long format."),
119  cl::Hidden);
120 
121 namespace {
122 
123 using Iter = MachineBasicBlock::iterator;
124 using ReverseIter = MachineBasicBlock::reverse_iterator;
125 
126 struct MBBInfo {
127  uint64_t Size = 0;
128  bool HasLongBranch = false;
129  MachineInstr *Br = nullptr;
130  uint64_t Offset = 0;
131  MBBInfo() = default;
132 };
133 
134 class MipsBranchExpansion : public MachineFunctionPass {
135 public:
136  static char ID;
137 
138  MipsBranchExpansion() : MachineFunctionPass(ID), ABI(MipsABIInfo::Unknown()) {
140  }
141 
142  StringRef getPassName() const override {
143  return "Mips Branch Expansion Pass";
144  }
145 
146  bool runOnMachineFunction(MachineFunction &F) override;
147 
148  MachineFunctionProperties getRequiredProperties() const override {
151  }
152 
153 private:
155  void initMBBInfo();
156  int64_t computeOffset(const MachineInstr *Br);
157  uint64_t computeOffsetFromTheBeginning(int MBB);
158  void replaceBranch(MachineBasicBlock &MBB, Iter Br, const DebugLoc &DL,
159  MachineBasicBlock *MBBOpnd);
160  bool buildProperJumpMI(MachineBasicBlock *MBB,
162  void expandToLongBranch(MBBInfo &Info);
163  bool handleForbiddenSlot();
164  bool handlePossibleLongBranch();
165 
166  const MipsSubtarget *STI;
167  const MipsInstrInfo *TII;
168 
169  MachineFunction *MFp;
170  SmallVector<MBBInfo, 16> MBBInfos;
171  bool IsPIC;
173  bool ForceLongBranchFirstPass = false;
174 };
175 
176 } // end of anonymous namespace
177 
178 char MipsBranchExpansion::ID = 0;
179 
180 INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE,
181  "Expand out of range branch instructions and fix forbidden"
182  " slot hazards",
183  false, false)
184 
185 /// Returns a pass that clears pipeline hazards.
187  return new MipsBranchExpansion();
188 }
189 
190 // Find the next real instruction from the current position in current basic
191 // block.
193  Iter I = Position, E = Position->getParent()->end();
194  I = std::find_if_not(I, E,
195  [](const Iter &Insn) { return Insn->isTransient(); });
196 
197  return I;
198 }
199 
200 // Find the next real instruction from the current position, looking through
201 // basic block boundaries.
202 static std::pair<Iter, bool> getNextMachineInstr(Iter Position,
203  MachineBasicBlock *Parent) {
204  if (Position == Parent->end()) {
205  do {
206  MachineBasicBlock *Succ = Parent->getNextNode();
207  if (Succ != nullptr && Parent->isSuccessor(Succ)) {
208  Position = Succ->begin();
209  Parent = Succ;
210  } else {
211  return std::make_pair(Position, true);
212  }
213  } while (Parent->empty());
214  }
215 
216  Iter Instr = getNextMachineInstrInBB(Position);
217  if (Instr == Parent->end()) {
218  return getNextMachineInstr(Instr, Parent);
219  }
220  return std::make_pair(Instr, false);
221 }
222 
223 /// Iterate over list of Br's operands and search for a MachineBasicBlock
224 /// operand.
226  for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
227  const MachineOperand &MO = Br.getOperand(I);
228 
229  if (MO.isMBB())
230  return MO.getMBB();
231  }
232 
233  llvm_unreachable("This instruction does not have an MBB operand.");
234 }
235 
236 // Traverse the list of instructions backwards until a non-debug instruction is
237 // found or it reaches E.
238 static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) {
239  for (; B != E; ++B)
240  if (!B->isDebugInstr())
241  return B;
242 
243  return E;
244 }
245 
246 // Split MBB if it has two direct jumps/branches.
248  ReverseIter End = MBB->rend();
249  ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
250 
251  // Return if MBB has no branch instructions.
252  if ((LastBr == End) ||
253  (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
254  return;
255 
256  ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);
257 
258  // MBB has only one branch instruction if FirstBr is not a branch
259  // instruction.
260  if ((FirstBr == End) ||
261  (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
262  return;
263 
264  assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
265 
266  // Create a new MBB. Move instructions in MBB to the newly created MBB.
267  MachineBasicBlock *NewMBB =
268  MFp->CreateMachineBasicBlock(MBB->getBasicBlock());
269 
270  // Insert NewMBB and fix control flow.
271  MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
272  NewMBB->transferSuccessors(MBB);
273  if (Tgt != getTargetMBB(*LastBr))
274  NewMBB->removeSuccessor(Tgt, true);
275  MBB->addSuccessor(NewMBB);
276  MBB->addSuccessor(Tgt);
277  MFp->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
278 
279  NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->end());
280 }
281 
282 // Fill MBBInfos.
283 void MipsBranchExpansion::initMBBInfo() {
284  // Split the MBBs if they have two branches. Each basic block should have at
285  // most one branch after this loop is executed.
286  for (auto &MBB : *MFp)
287  splitMBB(&MBB);
288 
289  MFp->RenumberBlocks();
290  MBBInfos.clear();
291  MBBInfos.resize(MFp->size());
292 
293  for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
294  MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
295 
296  // Compute size of MBB.
298  MI != MBB->instr_end(); ++MI)
299  MBBInfos[I].Size += TII->getInstSizeInBytes(*MI);
300  }
301 }
302 
303 // Compute offset of branch in number of bytes.
304 int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) {
305  int64_t Offset = 0;
306  int ThisMBB = Br->getParent()->getNumber();
307  int TargetMBB = getTargetMBB(*Br)->getNumber();
308 
309  // Compute offset of a forward branch.
310  if (ThisMBB < TargetMBB) {
311  for (int N = ThisMBB + 1; N < TargetMBB; ++N)
312  Offset += MBBInfos[N].Size;
313 
314  return Offset + 4;
315  }
316 
317  // Compute offset of a backward branch.
318  for (int N = ThisMBB; N >= TargetMBB; --N)
319  Offset += MBBInfos[N].Size;
320 
321  return -Offset + 4;
322 }
323 
324 // Returns the distance in bytes up until MBB
325 uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(int MBB) {
326  uint64_t Offset = 0;
327  for (int N = 0; N < MBB; ++N)
328  Offset += MBBInfos[N].Size;
329  return Offset;
330 }
331 
332 // Replace Br with a branch which has the opposite condition code and a
333 // MachineBasicBlock operand MBBOpnd.
334 void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,
335  const DebugLoc &DL,
336  MachineBasicBlock *MBBOpnd) {
337  unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
338  const MCInstrDesc &NewDesc = TII->get(NewOpc);
339 
340  MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
341 
342  for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
343  MachineOperand &MO = Br->getOperand(I);
344 
345  switch (MO.getType()) {
347  MIB.addReg(MO.getReg());
348  break;
350  // Octeon BBIT family of branch has an immediate operand
351  // (e.g. BBIT0 $v0, 3, %bb.1).
352  if (!TII->isBranchWithImm(Br->getOpcode()))
353  llvm_unreachable("Unexpected immediate in branch instruction");
354  MIB.addImm(MO.getImm());
355  break;
357  MIB.addMBB(MBBOpnd);
358  break;
359  default:
360  llvm_unreachable("Unexpected operand type in branch instruction");
361  }
362  }
363 
364  if (Br->hasDelaySlot()) {
365  // Bundle the instruction in the delay slot to the newly created branch
366  // and erase the original branch.
367  assert(Br->isBundledWithSucc());
368  MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
369  MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
370  }
371  Br->eraseFromParent();
372 }
373 
374 bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,
376  DebugLoc DL) {
377  bool HasR6 = ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
378  bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
379 
380  unsigned JR = ABI.IsN64() ? Mips::JR64 : Mips::JR;
381  unsigned JIC = ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
382  unsigned JR_HB = ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
383  unsigned JR_HB_R6 = ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
384 
385  unsigned JumpOp;
386  if (STI->useIndirectJumpsHazard())
387  JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
388  else
389  JumpOp = HasR6 ? JIC : JR;
390 
391  if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
392  JumpOp = Mips::JIC_MMR6;
393 
394  unsigned ATReg = ABI.IsN64() ? Mips::AT_64 : Mips::AT;
395  MachineInstrBuilder Instr =
396  BuildMI(*MBB, Pos, DL, TII->get(JumpOp)).addReg(ATReg);
397  if (AddImm)
398  Instr.addImm(0);
399 
400  return !AddImm;
401 }
402 
403 // Expand branch instructions to long branches.
404 // TODO: This function has to be fixed for beqz16 and bnez16, because it
405 // currently assumes that all branches have 16-bit offsets, and will produce
406 // wrong code if branches whose allowed offsets are [-128, -126, ..., 126]
407 // are present.
408 void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {
410  MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
411  DebugLoc DL = I.Br->getDebugLoc();
412  const BasicBlock *BB = MBB->getBasicBlock();
414  MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);
415 
416  MFp->insert(FallThroughMBB, LongBrMBB);
417  MBB->replaceSuccessor(TgtMBB, LongBrMBB);
418 
419  if (IsPIC) {
420  MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
421  MFp->insert(FallThroughMBB, BalTgtMBB);
422  LongBrMBB->addSuccessor(BalTgtMBB);
423  BalTgtMBB->addSuccessor(TgtMBB);
424 
425  // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
426  // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
427  // pseudo-instruction wrapping BGEZAL).
428  const unsigned BalOp =
429  STI->hasMips32r6()
430  ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
431  : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
432 
433  if (!ABI.IsN64()) {
434  // Pre R6:
435  // $longbr:
436  // addiu $sp, $sp, -8
437  // sw $ra, 0($sp)
438  // lui $at, %hi($tgt - $baltgt)
439  // bal $baltgt
440  // addiu $at, $at, %lo($tgt - $baltgt)
441  // $baltgt:
442  // addu $at, $ra, $at
443  // lw $ra, 0($sp)
444  // jr $at
445  // addiu $sp, $sp, 8
446  // $fallthrough:
447  //
448 
449  // R6:
450  // $longbr:
451  // addiu $sp, $sp, -8
452  // sw $ra, 0($sp)
453  // lui $at, %hi($tgt - $baltgt)
454  // addiu $at, $at, %lo($tgt - $baltgt)
455  // balc $baltgt
456  // $baltgt:
457  // addu $at, $ra, $at
458  // lw $ra, 0($sp)
459  // addiu $sp, $sp, 8
460  // jic $at, 0
461  // $fallthrough:
462 
463  Pos = LongBrMBB->begin();
464 
465  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
466  .addReg(Mips::SP)
467  .addImm(-8);
468  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))
469  .addReg(Mips::RA)
470  .addReg(Mips::SP)
471  .addImm(0);
472 
473  // LUi and ADDiu instructions create 32-bit offset of the target basic
474  // block from the target of BAL(C) instruction. We cannot use immediate
475  // value for this offset because it cannot be determined accurately when
476  // the program has inline assembly statements. We therefore use the
477  // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
478  // are resolved during the fixup, so the values will always be correct.
479  //
480  // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
481  // expressions at this point (it is possible only at the MC layer),
482  // we replace LUi and ADDiu with pseudo instructions
483  // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
484  // blocks as operands to these instructions. When lowering these pseudo
485  // instructions to LUi and ADDiu in the MC layer, we will create
486  // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
487  // operands to lowered instructions.
488 
489  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
490  .addMBB(TgtMBB, MipsII::MO_ABS_HI)
491  .addMBB(BalTgtMBB);
492 
493  MachineInstrBuilder BalInstr =
494  BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
495  MachineInstrBuilder ADDiuInstr =
496  BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
497  .addReg(Mips::AT)
498  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
499  .addMBB(BalTgtMBB);
500  if (STI->hasMips32r6()) {
501  LongBrMBB->insert(Pos, ADDiuInstr);
502  LongBrMBB->insert(Pos, BalInstr);
503  } else {
504  LongBrMBB->insert(Pos, BalInstr);
505  LongBrMBB->insert(Pos, ADDiuInstr);
506  LongBrMBB->rbegin()->bundleWithPred();
507  }
508 
509  Pos = BalTgtMBB->begin();
510 
511  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
512  .addReg(Mips::RA)
513  .addReg(Mips::AT);
514  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
515  .addReg(Mips::SP)
516  .addImm(0);
517  if (STI->isTargetNaCl())
518  // Bundle-align the target of indirect branch JR.
519  TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
520 
521  // In NaCl, modifying the sp is not allowed in branch delay slot.
522  // For MIPS32R6, we can skip using a delay slot branch.
523  bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
524 
525  if (STI->isTargetNaCl() || !hasDelaySlot) {
526  BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::ADDiu), Mips::SP)
527  .addReg(Mips::SP)
528  .addImm(8);
529  }
530  if (hasDelaySlot) {
531  if (STI->isTargetNaCl()) {
532  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::NOP));
533  } else {
534  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
535  .addReg(Mips::SP)
536  .addImm(8);
537  }
538  BalTgtMBB->rbegin()->bundleWithPred();
539  }
540  } else {
541  // Pre R6:
542  // $longbr:
543  // daddiu $sp, $sp, -16
544  // sd $ra, 0($sp)
545  // daddiu $at, $zero, %hi($tgt - $baltgt)
546  // dsll $at, $at, 16
547  // bal $baltgt
548  // daddiu $at, $at, %lo($tgt - $baltgt)
549  // $baltgt:
550  // daddu $at, $ra, $at
551  // ld $ra, 0($sp)
552  // jr64 $at
553  // daddiu $sp, $sp, 16
554  // $fallthrough:
555 
556  // R6:
557  // $longbr:
558  // daddiu $sp, $sp, -16
559  // sd $ra, 0($sp)
560  // daddiu $at, $zero, %hi($tgt - $baltgt)
561  // dsll $at, $at, 16
562  // daddiu $at, $at, %lo($tgt - $baltgt)
563  // balc $baltgt
564  // $baltgt:
565  // daddu $at, $ra, $at
566  // ld $ra, 0($sp)
567  // daddiu $sp, $sp, 16
568  // jic $at, 0
569  // $fallthrough:
570 
571  // We assume the branch is within-function, and that offset is within
572  // +/- 2GB. High 32 bits will therefore always be zero.
573 
574  // Note that this will work even if the offset is negative, because
575  // of the +1 modification that's added in that case. For example, if the
576  // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
577  //
578  // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
579  //
580  // and the bits [47:32] are zero. For %highest
581  //
582  // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
583  //
584  // and the bits [63:48] are zero.
585 
586  Pos = LongBrMBB->begin();
587 
588  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
589  .addReg(Mips::SP_64)
590  .addImm(-16);
591  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))
592  .addReg(Mips::RA_64)
593  .addReg(Mips::SP_64)
594  .addImm(0);
595  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
596  Mips::AT_64)
597  .addReg(Mips::ZERO_64)
598  .addMBB(TgtMBB, MipsII::MO_ABS_HI)
599  .addMBB(BalTgtMBB);
600  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
601  .addReg(Mips::AT_64)
602  .addImm(16);
603 
604  MachineInstrBuilder BalInstr =
605  BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
606  MachineInstrBuilder DADDiuInstr =
607  BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
608  .addReg(Mips::AT_64)
609  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
610  .addMBB(BalTgtMBB);
611  if (STI->hasMips32r6()) {
612  LongBrMBB->insert(Pos, DADDiuInstr);
613  LongBrMBB->insert(Pos, BalInstr);
614  } else {
615  LongBrMBB->insert(Pos, BalInstr);
616  LongBrMBB->insert(Pos, DADDiuInstr);
617  LongBrMBB->rbegin()->bundleWithPred();
618  }
619 
620  Pos = BalTgtMBB->begin();
621 
622  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
623  .addReg(Mips::RA_64)
624  .addReg(Mips::AT_64);
625  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
626  .addReg(Mips::SP_64)
627  .addImm(0);
628 
629  bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
630  // If there is no delay slot, Insert stack adjustment before
631  if (!hasDelaySlot) {
632  BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::DADDiu),
633  Mips::SP_64)
634  .addReg(Mips::SP_64)
635  .addImm(16);
636  } else {
637  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
638  .addReg(Mips::SP_64)
639  .addImm(16);
640  BalTgtMBB->rbegin()->bundleWithPred();
641  }
642  }
643  } else { // Not PIC
644  Pos = LongBrMBB->begin();
645  LongBrMBB->addSuccessor(TgtMBB);
646 
647  // Compute the position of the potentiall jump instruction (basic blocks
648  // before + 4 for the instruction)
649  uint64_t JOffset = computeOffsetFromTheBeginning(MBB->getNumber()) +
650  MBBInfos[MBB->getNumber()].Size + 4;
651  uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
652  // If it's a forward jump, then TgtMBBOffset will be shifted by two
653  // instructions
654  if (JOffset < TgtMBBOffset)
655  TgtMBBOffset += 2 * 4;
656  // Compare 4 upper bits to check if it's the same segment
657  bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
658 
659  if (STI->hasMips32r6() && TII->isBranchOffsetInRange(Mips::BC, I.Offset)) {
660  // R6:
661  // $longbr:
662  // bc $tgt
663  // $fallthrough:
664  //
665  BuildMI(*LongBrMBB, Pos, DL,
666  TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
667  .addMBB(TgtMBB);
668  } else if (SameSegmentJump) {
669  // Pre R6:
670  // $longbr:
671  // j $tgt
672  // nop
673  // $fallthrough:
674  //
675  MIBundleBuilder(*LongBrMBB, Pos)
676  .append(BuildMI(*MFp, DL, TII->get(Mips::J)).addMBB(TgtMBB))
677  .append(BuildMI(*MFp, DL, TII->get(Mips::NOP)));
678  } else {
679  // At this point, offset where we need to branch does not fit into
680  // immediate field of the branch instruction and is not in the same
681  // segment as jump instruction. Therefore we will break it into couple
682  // instructions, where we first load the offset into register, and then we
683  // do branch register.
684  if (ABI.IsN64()) {
685  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op_64),
686  Mips::AT_64)
687  .addMBB(TgtMBB, MipsII::MO_HIGHEST);
688  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
689  Mips::AT_64)
690  .addReg(Mips::AT_64)
691  .addMBB(TgtMBB, MipsII::MO_HIGHER);
692  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
693  .addReg(Mips::AT_64)
694  .addImm(16);
695  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
696  Mips::AT_64)
697  .addReg(Mips::AT_64)
698  .addMBB(TgtMBB, MipsII::MO_ABS_HI);
699  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
700  .addReg(Mips::AT_64)
701  .addImm(16);
702  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
703  Mips::AT_64)
704  .addReg(Mips::AT_64)
705  .addMBB(TgtMBB, MipsII::MO_ABS_LO);
706  } else {
707  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op),
708  Mips::AT)
709  .addMBB(TgtMBB, MipsII::MO_ABS_HI);
710  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_ADDiu2Op),
711  Mips::AT)
712  .addReg(Mips::AT)
713  .addMBB(TgtMBB, MipsII::MO_ABS_LO);
714  }
715  buildProperJumpMI(LongBrMBB, Pos, DL);
716  }
717  }
718 
719  if (I.Br->isUnconditionalBranch()) {
720  // Change branch destination.
721  assert(I.Br->getDesc().getNumOperands() == 1);
722  I.Br->RemoveOperand(0);
723  I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
724  } else
725  // Change branch destination and reverse condition.
726  replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
727 }
728 
730  MachineBasicBlock &MBB = F.front();
732  DebugLoc DL = MBB.findDebugLoc(MBB.begin());
733  BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
734  .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
735  BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
736  .addReg(Mips::V0)
737  .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
738  MBB.removeLiveIn(Mips::V0);
739 }
740 
741 bool MipsBranchExpansion::handleForbiddenSlot() {
742  // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.
743  if (!STI->hasMips32r6() || STI->inMicroMipsMode())
744  return false;
745 
746  bool Changed = false;
747 
748  for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {
749  for (Iter I = FI->begin(); I != FI->end(); ++I) {
750 
751  // Forbidden slot hazard handling. Use lookahead over state.
752  if (!TII->HasForbiddenSlot(*I))
753  continue;
754 
755  Iter Inst;
756  bool LastInstInFunction =
757  std::next(I) == FI->end() && std::next(FI) == MFp->end();
758  if (!LastInstInFunction) {
759  std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
760  LastInstInFunction |= Res.second;
761  Inst = Res.first;
762  }
763 
764  if (LastInstInFunction || !TII->SafeInForbiddenSlot(*Inst)) {
765 
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  MIBundleBuilder(&*I).append(
771  BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
772  NumInsertedNops++;
773  }
774  }
775  }
776  }
777 
778  return Changed;
779 }
780 
781 bool MipsBranchExpansion::handlePossibleLongBranch() {
782  if (STI->inMips16Mode() || !STI->enableLongBranchPass())
783  return false;
784 
785  if (SkipLongBranch)
786  return false;
787 
788  bool EverMadeChange = false, MadeChange = true;
789 
790  while (MadeChange) {
791  MadeChange = false;
792 
793  initMBBInfo();
794 
795  for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
796  MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
797  // Search for MBB's branch instruction.
798  ReverseIter End = MBB->rend();
799  ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
800 
801  if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&
802  (Br->isConditionalBranch() ||
803  (Br->isUnconditionalBranch() && IsPIC))) {
804  int64_t Offset = computeOffset(&*Br);
805 
806  if (STI->isTargetNaCl()) {
807  // The offset calculation does not include sandboxing instructions
808  // that will be added later in the MC layer. Since at this point we
809  // don't know the exact amount of code that "sandboxing" will add, we
810  // conservatively estimate that code will not grow more than 100%.
811  Offset *= 2;
812  }
813 
814  if (ForceLongBranchFirstPass ||
815  !TII->isBranchOffsetInRange(Br->getOpcode(), Offset)) {
816  MBBInfos[I].Offset = Offset;
817  MBBInfos[I].Br = &*Br;
818  }
819  }
820  } // End for
821 
822  ForceLongBranchFirstPass = false;
823 
824  SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
825 
826  for (I = MBBInfos.begin(); I != E; ++I) {
827  // Skip if this MBB doesn't have a branch or the branch has already been
828  // converted to a long branch.
829  if (!I->Br)
830  continue;
831 
832  expandToLongBranch(*I);
833  ++LongBranches;
834  EverMadeChange = MadeChange = true;
835  }
836 
837  MFp->RenumberBlocks();
838  }
839 
840  return EverMadeChange;
841 }
842 
843 bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
844  const TargetMachine &TM = MF.getTarget();
845  IsPIC = TM.isPositionIndependent();
846  ABI = static_cast<const MipsTargetMachine &>(TM).getABI();
847  STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
848  TII = static_cast<const MipsInstrInfo *>(STI->getInstrInfo());
849 
850  if (IsPIC && ABI.IsO32() &&
851  MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
852  emitGPDisp(MF, TII);
853 
854  MFp = &MF;
855 
856  ForceLongBranchFirstPass = ForceLongBranch;
857  // Run these two at least once
858  bool longBranchChanged = handlePossibleLongBranch();
859  bool forbiddenSlotChanged = handleForbiddenSlot();
860 
861  bool Changed = longBranchChanged || forbiddenSlotChanged;
862 
863  // Then run them alternatively while there are changes
864  while (forbiddenSlotChanged) {
865  longBranchChanged = handlePossibleLongBranch();
866  if (!longBranchChanged)
867  break;
868  forbiddenSlotChanged = handleForbiddenSlot();
869  }
870 
871  return Changed;
872 }
void initializeMipsBranchExpansionPass(PassRegistry &)
static const Align MIPS_NACL_BUNDLE_ALIGN
Definition: MipsMCNaCl.h:18
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_begin()
instr_iterator instr_end()
MachineBasicBlock * getMBB() const
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static MachineBasicBlock * getTargetMBB(const MachineInstr &Br)
Iterate over list of Br&#39;s operands and search for a MachineBasicBlock operand.
MO_HIGHER/HIGHEST - Represents the highest or higher half word of a 64-bit symbol address...
Definition: MipsBaseInfo.h:85
FunctionPass * createMipsBranchExpansion()
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:187
static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E)
static Iter getNextMachineInstrInBB(Iter Position)
MachineBasicBlock reference.
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:33
F(f)
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
MachineBasicBlock & MBB
SI optimize exec mask operations pre RA
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:455
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:220
const HexagonInstrInfo * TII
Position
Position to insert a new instruction relative to an existing instruction.
MO_ABS_HI/LO - Represents the hi or low part of an absolute symbol address.
Definition: MipsBaseInfo.h:52
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:453
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
#define DEBUG_TYPE
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
reverse_iterator rend()
reverse_iterator rbegin()
Analysis containing CSE Info
Definition: CSEInfo.cpp:25
BasicBlockListType::iterator iterator
static cl::opt< bool > ForceLongBranch("force-mips-long-branch", cl::init(false), cl::desc("MIPS: Expand all branches to long format."), cl::Hidden)
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
MachineInstrBundleIterator< MachineInstr > iterator
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
auto find_if_not(R &&Range, UnaryPredicate P)
Definition: STLExtras.h:1523
const MachineBasicBlock & front() const
static cl::opt< bool > SkipLongBranch("skip-mips-long-branch", cl::init(false), cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden)
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
static std::pair< Iter, bool > getNextMachineInstr(Iter Position, MachineBasicBlock *Parent)
int64_t getImm() const
typename SuperClass::iterator iterator
Definition: SmallVector.h:365
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:280
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:62
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
bool isPositionIndependent() const
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
MipsFunctionInfo - This class is derived from MachineFunction private Mips target-specific informatio...
INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE, "Expand out of range branch instructions and fix forbidden" " slot hazards", false, false) FunctionPass *llvm
Returns a pass that clears pipeline hazards.
uint32_t Size
Definition: Profile.cpp:46
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:466
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII)
static bool splitMBB(BlockSplitInfo &BSI)
Splits a MachineBasicBlock to branch before SplitBefore.
const MachineInstrBuilder & addExternalSymbol(const char *FnName, unsigned TargetFlags=0) const
Properties which a MachineFunction may have at a given point in time.
Helper class for constructing bundles of MachineInstrs.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL