LLVM  9.0.0svn
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:
154  void splitMBB(MachineBasicBlock *MBB);
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  if (!MO.isReg()) {
346  assert(MO.isMBB() && "MBB operand expected.");
347  break;
348  }
349 
350  MIB.addReg(MO.getReg());
351  }
352 
353  MIB.addMBB(MBBOpnd);
354 
355  if (Br->hasDelaySlot()) {
356  // Bundle the instruction in the delay slot to the newly created branch
357  // and erase the original branch.
358  assert(Br->isBundledWithSucc());
359  MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
360  MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
361  }
362  Br->eraseFromParent();
363 }
364 
365 bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,
367  DebugLoc DL) {
368  bool HasR6 = ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
369  bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
370 
371  unsigned JR = ABI.IsN64() ? Mips::JR64 : Mips::JR;
372  unsigned JIC = ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
373  unsigned JR_HB = ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
374  unsigned JR_HB_R6 = ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
375 
376  unsigned JumpOp;
377  if (STI->useIndirectJumpsHazard())
378  JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
379  else
380  JumpOp = HasR6 ? JIC : JR;
381 
382  if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
383  JumpOp = Mips::JIC_MMR6;
384 
385  unsigned ATReg = ABI.IsN64() ? Mips::AT_64 : Mips::AT;
386  MachineInstrBuilder Instr =
387  BuildMI(*MBB, Pos, DL, TII->get(JumpOp)).addReg(ATReg);
388  if (AddImm)
389  Instr.addImm(0);
390 
391  return !AddImm;
392 }
393 
394 // Expand branch instructions to long branches.
395 // TODO: This function has to be fixed for beqz16 and bnez16, because it
396 // currently assumes that all branches have 16-bit offsets, and will produce
397 // wrong code if branches whose allowed offsets are [-128, -126, ..., 126]
398 // are present.
399 void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {
401  MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
402  DebugLoc DL = I.Br->getDebugLoc();
403  const BasicBlock *BB = MBB->getBasicBlock();
405  MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);
406 
407  MFp->insert(FallThroughMBB, LongBrMBB);
408  MBB->replaceSuccessor(TgtMBB, LongBrMBB);
409 
410  if (IsPIC) {
411  MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
412  MFp->insert(FallThroughMBB, BalTgtMBB);
413  LongBrMBB->addSuccessor(BalTgtMBB);
414  BalTgtMBB->addSuccessor(TgtMBB);
415 
416  // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
417  // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
418  // pseudo-instruction wrapping BGEZAL).
419  const unsigned BalOp =
420  STI->hasMips32r6()
421  ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
422  : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
423 
424  if (!ABI.IsN64()) {
425  // Pre R6:
426  // $longbr:
427  // addiu $sp, $sp, -8
428  // sw $ra, 0($sp)
429  // lui $at, %hi($tgt - $baltgt)
430  // bal $baltgt
431  // addiu $at, $at, %lo($tgt - $baltgt)
432  // $baltgt:
433  // addu $at, $ra, $at
434  // lw $ra, 0($sp)
435  // jr $at
436  // addiu $sp, $sp, 8
437  // $fallthrough:
438  //
439 
440  // R6:
441  // $longbr:
442  // addiu $sp, $sp, -8
443  // sw $ra, 0($sp)
444  // lui $at, %hi($tgt - $baltgt)
445  // addiu $at, $at, %lo($tgt - $baltgt)
446  // balc $baltgt
447  // $baltgt:
448  // addu $at, $ra, $at
449  // lw $ra, 0($sp)
450  // addiu $sp, $sp, 8
451  // jic $at, 0
452  // $fallthrough:
453 
454  Pos = LongBrMBB->begin();
455 
456  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
457  .addReg(Mips::SP)
458  .addImm(-8);
459  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))
460  .addReg(Mips::RA)
461  .addReg(Mips::SP)
462  .addImm(0);
463 
464  // LUi and ADDiu instructions create 32-bit offset of the target basic
465  // block from the target of BAL(C) instruction. We cannot use immediate
466  // value for this offset because it cannot be determined accurately when
467  // the program has inline assembly statements. We therefore use the
468  // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
469  // are resolved during the fixup, so the values will always be correct.
470  //
471  // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
472  // expressions at this point (it is possible only at the MC layer),
473  // we replace LUi and ADDiu with pseudo instructions
474  // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
475  // blocks as operands to these instructions. When lowering these pseudo
476  // instructions to LUi and ADDiu in the MC layer, we will create
477  // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
478  // operands to lowered instructions.
479 
480  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
481  .addMBB(TgtMBB, MipsII::MO_ABS_HI)
482  .addMBB(BalTgtMBB);
483 
484  MachineInstrBuilder BalInstr =
485  BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
486  MachineInstrBuilder ADDiuInstr =
487  BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
488  .addReg(Mips::AT)
489  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
490  .addMBB(BalTgtMBB);
491  if (STI->hasMips32r6()) {
492  LongBrMBB->insert(Pos, ADDiuInstr);
493  LongBrMBB->insert(Pos, BalInstr);
494  } else {
495  LongBrMBB->insert(Pos, BalInstr);
496  LongBrMBB->insert(Pos, ADDiuInstr);
497  LongBrMBB->rbegin()->bundleWithPred();
498  }
499 
500  Pos = BalTgtMBB->begin();
501 
502  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
503  .addReg(Mips::RA)
504  .addReg(Mips::AT);
505  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
506  .addReg(Mips::SP)
507  .addImm(0);
508  if (STI->isTargetNaCl())
509  // Bundle-align the target of indirect branch JR.
510  TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
511 
512  // In NaCl, modifying the sp is not allowed in branch delay slot.
513  // For MIPS32R6, we can skip using a delay slot branch.
514  bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
515 
516  if (STI->isTargetNaCl() || !hasDelaySlot) {
517  BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::ADDiu), Mips::SP)
518  .addReg(Mips::SP)
519  .addImm(8);
520  }
521  if (hasDelaySlot) {
522  if (STI->isTargetNaCl()) {
523  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::NOP));
524  } else {
525  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
526  .addReg(Mips::SP)
527  .addImm(8);
528  }
529  BalTgtMBB->rbegin()->bundleWithPred();
530  }
531  } else {
532  // Pre R6:
533  // $longbr:
534  // daddiu $sp, $sp, -16
535  // sd $ra, 0($sp)
536  // daddiu $at, $zero, %hi($tgt - $baltgt)
537  // dsll $at, $at, 16
538  // bal $baltgt
539  // daddiu $at, $at, %lo($tgt - $baltgt)
540  // $baltgt:
541  // daddu $at, $ra, $at
542  // ld $ra, 0($sp)
543  // jr64 $at
544  // daddiu $sp, $sp, 16
545  // $fallthrough:
546 
547  // R6:
548  // $longbr:
549  // daddiu $sp, $sp, -16
550  // sd $ra, 0($sp)
551  // daddiu $at, $zero, %hi($tgt - $baltgt)
552  // dsll $at, $at, 16
553  // daddiu $at, $at, %lo($tgt - $baltgt)
554  // balc $baltgt
555  // $baltgt:
556  // daddu $at, $ra, $at
557  // ld $ra, 0($sp)
558  // daddiu $sp, $sp, 16
559  // jic $at, 0
560  // $fallthrough:
561 
562  // We assume the branch is within-function, and that offset is within
563  // +/- 2GB. High 32 bits will therefore always be zero.
564 
565  // Note that this will work even if the offset is negative, because
566  // of the +1 modification that's added in that case. For example, if the
567  // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
568  //
569  // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
570  //
571  // and the bits [47:32] are zero. For %highest
572  //
573  // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
574  //
575  // and the bits [63:48] are zero.
576 
577  Pos = LongBrMBB->begin();
578 
579  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
580  .addReg(Mips::SP_64)
581  .addImm(-16);
582  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))
583  .addReg(Mips::RA_64)
584  .addReg(Mips::SP_64)
585  .addImm(0);
586  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
587  Mips::AT_64)
588  .addReg(Mips::ZERO_64)
589  .addMBB(TgtMBB, MipsII::MO_ABS_HI)
590  .addMBB(BalTgtMBB);
591  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
592  .addReg(Mips::AT_64)
593  .addImm(16);
594 
595  MachineInstrBuilder BalInstr =
596  BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
597  MachineInstrBuilder DADDiuInstr =
598  BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
599  .addReg(Mips::AT_64)
600  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
601  .addMBB(BalTgtMBB);
602  if (STI->hasMips32r6()) {
603  LongBrMBB->insert(Pos, DADDiuInstr);
604  LongBrMBB->insert(Pos, BalInstr);
605  } else {
606  LongBrMBB->insert(Pos, BalInstr);
607  LongBrMBB->insert(Pos, DADDiuInstr);
608  LongBrMBB->rbegin()->bundleWithPred();
609  }
610 
611  Pos = BalTgtMBB->begin();
612 
613  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
614  .addReg(Mips::RA_64)
615  .addReg(Mips::AT_64);
616  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
617  .addReg(Mips::SP_64)
618  .addImm(0);
619 
620  bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
621  // If there is no delay slot, Insert stack adjustment before
622  if (!hasDelaySlot) {
623  BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::DADDiu),
624  Mips::SP_64)
625  .addReg(Mips::SP_64)
626  .addImm(16);
627  } else {
628  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
629  .addReg(Mips::SP_64)
630  .addImm(16);
631  BalTgtMBB->rbegin()->bundleWithPred();
632  }
633  }
634  } else { // Not PIC
635  Pos = LongBrMBB->begin();
636  LongBrMBB->addSuccessor(TgtMBB);
637 
638  // Compute the position of the potentiall jump instruction (basic blocks
639  // before + 4 for the instruction)
640  uint64_t JOffset = computeOffsetFromTheBeginning(MBB->getNumber()) +
641  MBBInfos[MBB->getNumber()].Size + 4;
642  uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
643  // If it's a forward jump, then TgtMBBOffset will be shifted by two
644  // instructions
645  if (JOffset < TgtMBBOffset)
646  TgtMBBOffset += 2 * 4;
647  // Compare 4 upper bits to check if it's the same segment
648  bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
649 
650  if (STI->hasMips32r6() && TII->isBranchOffsetInRange(Mips::BC, I.Offset)) {
651  // R6:
652  // $longbr:
653  // bc $tgt
654  // $fallthrough:
655  //
656  BuildMI(*LongBrMBB, Pos, DL,
657  TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
658  .addMBB(TgtMBB);
659  } else if (SameSegmentJump) {
660  // Pre R6:
661  // $longbr:
662  // j $tgt
663  // nop
664  // $fallthrough:
665  //
666  MIBundleBuilder(*LongBrMBB, Pos)
667  .append(BuildMI(*MFp, DL, TII->get(Mips::J)).addMBB(TgtMBB))
668  .append(BuildMI(*MFp, DL, TII->get(Mips::NOP)));
669  } else {
670  // At this point, offset where we need to branch does not fit into
671  // immediate field of the branch instruction and is not in the same
672  // segment as jump instruction. Therefore we will break it into couple
673  // instructions, where we first load the offset into register, and then we
674  // do branch register.
675  if (ABI.IsN64()) {
676  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op_64),
677  Mips::AT_64)
678  .addMBB(TgtMBB, MipsII::MO_HIGHEST);
679  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
680  Mips::AT_64)
681  .addReg(Mips::AT_64)
682  .addMBB(TgtMBB, MipsII::MO_HIGHER);
683  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
684  .addReg(Mips::AT_64)
685  .addImm(16);
686  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
687  Mips::AT_64)
688  .addReg(Mips::AT_64)
689  .addMBB(TgtMBB, MipsII::MO_ABS_HI);
690  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
691  .addReg(Mips::AT_64)
692  .addImm(16);
693  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
694  Mips::AT_64)
695  .addReg(Mips::AT_64)
696  .addMBB(TgtMBB, MipsII::MO_ABS_LO);
697  } else {
698  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op),
699  Mips::AT)
700  .addMBB(TgtMBB, MipsII::MO_ABS_HI);
701  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_ADDiu2Op),
702  Mips::AT)
703  .addReg(Mips::AT)
704  .addMBB(TgtMBB, MipsII::MO_ABS_LO);
705  }
706  buildProperJumpMI(LongBrMBB, Pos, DL);
707  }
708  }
709 
710  if (I.Br->isUnconditionalBranch()) {
711  // Change branch destination.
712  assert(I.Br->getDesc().getNumOperands() == 1);
713  I.Br->RemoveOperand(0);
714  I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
715  } else
716  // Change branch destination and reverse condition.
717  replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
718 }
719 
721  MachineBasicBlock &MBB = F.front();
723  DebugLoc DL = MBB.findDebugLoc(MBB.begin());
724  BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
725  .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
726  BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
727  .addReg(Mips::V0)
728  .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
729  MBB.removeLiveIn(Mips::V0);
730 }
731 
732 bool MipsBranchExpansion::handleForbiddenSlot() {
733  // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.
734  if (!STI->hasMips32r6() || STI->inMicroMipsMode())
735  return false;
736 
737  bool Changed = false;
738 
739  for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {
740  for (Iter I = FI->begin(); I != FI->end(); ++I) {
741 
742  // Forbidden slot hazard handling. Use lookahead over state.
743  if (!TII->HasForbiddenSlot(*I))
744  continue;
745 
746  Iter Inst;
747  bool LastInstInFunction =
748  std::next(I) == FI->end() && std::next(FI) == MFp->end();
749  if (!LastInstInFunction) {
750  std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
751  LastInstInFunction |= Res.second;
752  Inst = Res.first;
753  }
754 
755  if (LastInstInFunction || !TII->SafeInForbiddenSlot(*Inst)) {
756 
757  MachineBasicBlock::instr_iterator Iit = I->getIterator();
758  if (std::next(Iit) == FI->end() ||
759  std::next(Iit)->getOpcode() != Mips::NOP) {
760  Changed = true;
761  MIBundleBuilder(&*I).append(
762  BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
763  NumInsertedNops++;
764  }
765  }
766  }
767  }
768 
769  return Changed;
770 }
771 
772 bool MipsBranchExpansion::handlePossibleLongBranch() {
773  if (STI->inMips16Mode() || !STI->enableLongBranchPass())
774  return false;
775 
776  if (SkipLongBranch)
777  return false;
778 
779  bool EverMadeChange = false, MadeChange = true;
780 
781  while (MadeChange) {
782  MadeChange = false;
783 
784  initMBBInfo();
785 
786  for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
787  MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
788  // Search for MBB's branch instruction.
789  ReverseIter End = MBB->rend();
790  ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
791 
792  if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&
793  (Br->isConditionalBranch() ||
794  (Br->isUnconditionalBranch() && IsPIC))) {
795  int64_t Offset = computeOffset(&*Br);
796 
797  if (STI->isTargetNaCl()) {
798  // The offset calculation does not include sandboxing instructions
799  // that will be added later in the MC layer. Since at this point we
800  // don't know the exact amount of code that "sandboxing" will add, we
801  // conservatively estimate that code will not grow more than 100%.
802  Offset *= 2;
803  }
804 
805  if (ForceLongBranchFirstPass ||
806  !TII->isBranchOffsetInRange(Br->getOpcode(), Offset)) {
807  MBBInfos[I].Offset = Offset;
808  MBBInfos[I].Br = &*Br;
809  }
810  }
811  } // End for
812 
813  ForceLongBranchFirstPass = false;
814 
815  SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
816 
817  for (I = MBBInfos.begin(); I != E; ++I) {
818  // Skip if this MBB doesn't have a branch or the branch has already been
819  // converted to a long branch.
820  if (!I->Br)
821  continue;
822 
823  expandToLongBranch(*I);
824  ++LongBranches;
825  EverMadeChange = MadeChange = true;
826  }
827 
828  MFp->RenumberBlocks();
829  }
830 
831  return EverMadeChange;
832 }
833 
834 bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
835  const TargetMachine &TM = MF.getTarget();
836  IsPIC = TM.isPositionIndependent();
837  ABI = static_cast<const MipsTargetMachine &>(TM).getABI();
838  STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
839  TII = static_cast<const MipsInstrInfo *>(STI->getInstrInfo());
840 
841  if (IsPIC && ABI.IsO32() &&
842  MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
843  emitGPDisp(MF, TII);
844 
845  MFp = &MF;
846 
847  ForceLongBranchFirstPass = ForceLongBranch;
848  // Run these two at least once
849  bool longBranchChanged = handlePossibleLongBranch();
850  bool forbiddenSlotChanged = handleForbiddenSlot();
851 
852  bool Changed = longBranchChanged || forbiddenSlotChanged;
853 
854  // Then run them alternatively while there are changes
855  while (forbiddenSlotChanged) {
856  longBranchChanged = handlePossibleLongBranch();
857  if (!longBranchChanged)
858  break;
859  forbiddenSlotChanged = handleForbiddenSlot();
860  }
861 
862  return Changed;
863 }
void initializeMipsBranchExpansionPass(PassRegistry &)
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:84
FunctionPass * createMipsBranchExpansion()
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:164
unsigned getReg() const
getReg - Returns the register number.
static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E)
static Iter getNextMachineInstrInBB(Iter Position)
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:33
F(f)
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
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:211
const HexagonInstrInfo * TII
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
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:51
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
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:20
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:432
MachineInstrBundleIterator< MachineInstr > iterator
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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) -> decltype(adl_begin(Range))
Definition: STLExtras.h:1225
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:837
static std::pair< Iter, bool > getNextMachineInstr(Iter Position, MachineBasicBlock *Parent)
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineFunctionProperties & set(Property P)
static const unsigned MIPS_NACL_BUNDLE_ALIGN
Definition: MipsMCNaCl.h:17
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0)
bool isPositionIndependent() const
const MachineInstrBuilder & addExternalSymbol(const char *FnName, unsigned char TargetFlags=0) const
#define I(x, y, z)
Definition: MD5.cpp:58
#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
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
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
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:48
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0) const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII)
static bool splitMBB(BlockSplitInfo &BSI)
Splits a MachineBasicBlock to branch before SplitBefore.
Properties which a MachineFunction may have at a given point in time.
Helper class for constructing bundles of MachineInstrs.