LLVM  8.0.1
MipsBranchExpansion.cpp
Go to the documentation of this file.
1 //===----------------------- MipsBranchExpansion.cpp ----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// This pass do two things:
12 /// - it expands a branch or jump instruction into a long branch if its offset
13 /// is too large to fit into its immediate field,
14 /// - it inserts nops to prevent forbidden slot hazards.
15 ///
16 /// The reason why this pass combines these two tasks is that one of these two
17 /// tasks can break the result of the previous one.
18 ///
19 /// Example of that is a situation where at first, no branch should be expanded,
20 /// but after adding at least one nop somewhere in the code to prevent a
21 /// forbidden slot hazard, offset of some branches may go out of range. In that
22 /// case it is necessary to check again if there is some branch that needs
23 /// expansion. On the other hand, expanding some branch may cause a control
24 /// transfer instruction to appear in the forbidden slot, which is a hazard that
25 /// should be fixed. This pass alternates between this two tasks untill no
26 /// changes are made. Only then we can be sure that all branches are expanded
27 /// properly, and no hazard situations exist.
28 ///
29 /// Regarding branch expanding:
30 ///
31 /// When branch instruction like beqzc or bnezc has offset that is too large
32 /// to fit into its immediate field, it has to be expanded to another
33 /// instruction or series of instructions.
34 ///
35 /// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.
36 /// TODO: Handle out of range bc, b (pseudo) instructions.
37 ///
38 /// Regarding compact branch hazard prevention:
39 ///
40 /// Hazards handled: forbidden slots for MIPSR6.
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 
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"
95 #include "llvm/IR/DebugLoc.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 
139  MipsBranchExpansion() : MachineFunctionPass(ID), ABI(MipsABIInfo::Unknown()) {
141  }
142 
143  StringRef getPassName() const override {
144  return "Mips Branch Expansion Pass";
145  }
146 
147  bool runOnMachineFunction(MachineFunction &F) override;
148 
149  MachineFunctionProperties getRequiredProperties() const override {
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,
163  void expandToLongBranch(MBBInfo &Info);
164  bool handleForbiddenSlot();
165  bool handlePossibleLongBranch();
166 
167  const MipsSubtarget *STI;
168  const MipsInstrInfo *TII;
169 
170  MachineFunction *MFp;
171  SmallVector<MBBInfo, 16> MBBInfos;
172  bool IsPIC;
173  MipsABIInfo ABI;
174  bool ForceLongBranchFirstPass = false;
175 };
176 
177 } // end of anonymous namespace
178 
179 char MipsBranchExpansion::ID = 0;
180 
181 INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE,
182  "Expand out of range branch instructions and fix forbidden"
183  " slot hazards",
184  false, false)
185 
186 /// Returns a pass that clears pipeline hazards.
188  return new MipsBranchExpansion();
189 }
190 
191 // Find the next real instruction from the current position in current basic
192 // block.
194  Iter I = Position, E = Position->getParent()->end();
195  I = std::find_if_not(I, E,
196  [](const Iter &Insn) { return Insn->isTransient(); });
197 
198  return I;
199 }
200 
201 // Find the next real instruction from the current position, looking through
202 // basic block boundaries.
203 static std::pair<Iter, bool> getNextMachineInstr(Iter Position,
204  MachineBasicBlock *Parent) {
205  if (Position == Parent->end()) {
206  do {
207  MachineBasicBlock *Succ = Parent->getNextNode();
208  if (Succ != nullptr && Parent->isSuccessor(Succ)) {
209  Position = Succ->begin();
210  Parent = Succ;
211  } else {
212  return std::make_pair(Position, true);
213  }
214  } while (Parent->empty());
215  }
216 
217  Iter Instr = getNextMachineInstrInBB(Position);
218  if (Instr == Parent->end()) {
219  return getNextMachineInstr(Instr, Parent);
220  }
221  return std::make_pair(Instr, false);
222 }
223 
224 /// Iterate over list of Br's operands and search for a MachineBasicBlock
225 /// operand.
227  for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
228  const MachineOperand &MO = Br.getOperand(I);
229 
230  if (MO.isMBB())
231  return MO.getMBB();
232  }
233 
234  llvm_unreachable("This instruction does not have an MBB operand.");
235 }
236 
237 // Traverse the list of instructions backwards until a non-debug instruction is
238 // found or it reaches E.
239 static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) {
240  for (; B != E; ++B)
241  if (!B->isDebugInstr())
242  return B;
243 
244  return E;
245 }
246 
247 // Split MBB if it has two direct jumps/branches.
249  ReverseIter End = MBB->rend();
250  ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
251 
252  // Return if MBB has no branch instructions.
253  if ((LastBr == End) ||
254  (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
255  return;
256 
257  ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);
258 
259  // MBB has only one branch instruction if FirstBr is not a branch
260  // instruction.
261  if ((FirstBr == End) ||
262  (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
263  return;
264 
265  assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
266 
267  // Create a new MBB. Move instructions in MBB to the newly created MBB.
268  MachineBasicBlock *NewMBB =
269  MFp->CreateMachineBasicBlock(MBB->getBasicBlock());
270 
271  // Insert NewMBB and fix control flow.
272  MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
273  NewMBB->transferSuccessors(MBB);
274  if (Tgt != getTargetMBB(*LastBr))
275  NewMBB->removeSuccessor(Tgt, true);
276  MBB->addSuccessor(NewMBB);
277  MBB->addSuccessor(Tgt);
278  MFp->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
279 
280  NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->end());
281 }
282 
283 // Fill MBBInfos.
284 void MipsBranchExpansion::initMBBInfo() {
285  // Split the MBBs if they have two branches. Each basic block should have at
286  // most one branch after this loop is executed.
287  for (auto &MBB : *MFp)
288  splitMBB(&MBB);
289 
290  MFp->RenumberBlocks();
291  MBBInfos.clear();
292  MBBInfos.resize(MFp->size());
293 
294  for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
295  MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
296 
297  // Compute size of MBB.
299  MI != MBB->instr_end(); ++MI)
300  MBBInfos[I].Size += TII->getInstSizeInBytes(*MI);
301  }
302 }
303 
304 // Compute offset of branch in number of bytes.
305 int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) {
306  int64_t Offset = 0;
307  int ThisMBB = Br->getParent()->getNumber();
308  int TargetMBB = getTargetMBB(*Br)->getNumber();
309 
310  // Compute offset of a forward branch.
311  if (ThisMBB < TargetMBB) {
312  for (int N = ThisMBB + 1; N < TargetMBB; ++N)
313  Offset += MBBInfos[N].Size;
314 
315  return Offset + 4;
316  }
317 
318  // Compute offset of a backward branch.
319  for (int N = ThisMBB; N >= TargetMBB; --N)
320  Offset += MBBInfos[N].Size;
321 
322  return -Offset + 4;
323 }
324 
325 // Returns the distance in bytes up until MBB
326 uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(int MBB) {
327  uint64_t Offset = 0;
328  for (int N = 0; N < MBB; ++N)
329  Offset += MBBInfos[N].Size;
330  return Offset;
331 }
332 
333 // Replace Br with a branch which has the opposite condition code and a
334 // MachineBasicBlock operand MBBOpnd.
335 void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,
336  const DebugLoc &DL,
337  MachineBasicBlock *MBBOpnd) {
338  unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
339  const MCInstrDesc &NewDesc = TII->get(NewOpc);
340 
341  MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
342 
343  for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
344  MachineOperand &MO = Br->getOperand(I);
345 
346  if (!MO.isReg()) {
347  assert(MO.isMBB() && "MBB operand expected.");
348  break;
349  }
350 
351  MIB.addReg(MO.getReg());
352  }
353 
354  MIB.addMBB(MBBOpnd);
355 
356  if (Br->hasDelaySlot()) {
357  // Bundle the instruction in the delay slot to the newly created branch
358  // and erase the original branch.
359  assert(Br->isBundledWithSucc());
360  MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
361  MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
362  }
363  Br->eraseFromParent();
364 }
365 
366 bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,
368  DebugLoc DL) {
369  bool HasR6 = ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
370  bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
371 
372  unsigned JR = ABI.IsN64() ? Mips::JR64 : Mips::JR;
373  unsigned JIC = ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
374  unsigned JR_HB = ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
375  unsigned JR_HB_R6 = ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
376 
377  unsigned JumpOp;
378  if (STI->useIndirectJumpsHazard())
379  JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
380  else
381  JumpOp = HasR6 ? JIC : JR;
382 
383  if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
384  JumpOp = Mips::JIC_MMR6;
385 
386  unsigned ATReg = ABI.IsN64() ? Mips::AT_64 : Mips::AT;
387  MachineInstrBuilder Instr =
388  BuildMI(*MBB, Pos, DL, TII->get(JumpOp)).addReg(ATReg);
389  if (AddImm)
390  Instr.addImm(0);
391 
392  return !AddImm;
393 }
394 
395 // Expand branch instructions to long branches.
396 // TODO: This function has to be fixed for beqz16 and bnez16, because it
397 // currently assumes that all branches have 16-bit offsets, and will produce
398 // wrong code if branches whose allowed offsets are [-128, -126, ..., 126]
399 // are present.
400 void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {
402  MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
403  DebugLoc DL = I.Br->getDebugLoc();
404  const BasicBlock *BB = MBB->getBasicBlock();
406  MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);
407 
408  MFp->insert(FallThroughMBB, LongBrMBB);
409  MBB->replaceSuccessor(TgtMBB, LongBrMBB);
410 
411  if (IsPIC) {
412  MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
413  MFp->insert(FallThroughMBB, BalTgtMBB);
414  LongBrMBB->addSuccessor(BalTgtMBB);
415  BalTgtMBB->addSuccessor(TgtMBB);
416 
417  // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
418  // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
419  // pseudo-instruction wrapping BGEZAL).
420  const unsigned BalOp =
421  STI->hasMips32r6()
422  ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
423  : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
424 
425  if (!ABI.IsN64()) {
426  // Pre R6:
427  // $longbr:
428  // addiu $sp, $sp, -8
429  // sw $ra, 0($sp)
430  // lui $at, %hi($tgt - $baltgt)
431  // bal $baltgt
432  // addiu $at, $at, %lo($tgt - $baltgt)
433  // $baltgt:
434  // addu $at, $ra, $at
435  // lw $ra, 0($sp)
436  // jr $at
437  // addiu $sp, $sp, 8
438  // $fallthrough:
439  //
440 
441  // R6:
442  // $longbr:
443  // addiu $sp, $sp, -8
444  // sw $ra, 0($sp)
445  // lui $at, %hi($tgt - $baltgt)
446  // addiu $at, $at, %lo($tgt - $baltgt)
447  // balc $baltgt
448  // $baltgt:
449  // addu $at, $ra, $at
450  // lw $ra, 0($sp)
451  // addiu $sp, $sp, 8
452  // jic $at, 0
453  // $fallthrough:
454 
455  Pos = LongBrMBB->begin();
456 
457  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
458  .addReg(Mips::SP)
459  .addImm(-8);
460  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))
461  .addReg(Mips::RA)
462  .addReg(Mips::SP)
463  .addImm(0);
464 
465  // LUi and ADDiu instructions create 32-bit offset of the target basic
466  // block from the target of BAL(C) instruction. We cannot use immediate
467  // value for this offset because it cannot be determined accurately when
468  // the program has inline assembly statements. We therefore use the
469  // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
470  // are resolved during the fixup, so the values will always be correct.
471  //
472  // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
473  // expressions at this point (it is possible only at the MC layer),
474  // we replace LUi and ADDiu with pseudo instructions
475  // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
476  // blocks as operands to these instructions. When lowering these pseudo
477  // instructions to LUi and ADDiu in the MC layer, we will create
478  // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
479  // operands to lowered instructions.
480 
481  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
482  .addMBB(TgtMBB, MipsII::MO_ABS_HI)
483  .addMBB(BalTgtMBB);
484 
485  MachineInstrBuilder BalInstr =
486  BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
487  MachineInstrBuilder ADDiuInstr =
488  BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
489  .addReg(Mips::AT)
490  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
491  .addMBB(BalTgtMBB);
492  if (STI->hasMips32r6()) {
493  LongBrMBB->insert(Pos, ADDiuInstr);
494  LongBrMBB->insert(Pos, BalInstr);
495  } else {
496  LongBrMBB->insert(Pos, BalInstr);
497  LongBrMBB->insert(Pos, ADDiuInstr);
498  LongBrMBB->rbegin()->bundleWithPred();
499  }
500 
501  Pos = BalTgtMBB->begin();
502 
503  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
504  .addReg(Mips::RA)
505  .addReg(Mips::AT);
506  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
507  .addReg(Mips::SP)
508  .addImm(0);
509  if (STI->isTargetNaCl())
510  // Bundle-align the target of indirect branch JR.
511  TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
512 
513  // In NaCl, modifying the sp is not allowed in branch delay slot.
514  // For MIPS32R6, we can skip using a delay slot branch.
515  bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
516 
517  if (STI->isTargetNaCl() || !hasDelaySlot) {
518  BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::ADDiu), Mips::SP)
519  .addReg(Mips::SP)
520  .addImm(8);
521  }
522  if (hasDelaySlot) {
523  if (STI->isTargetNaCl()) {
524  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::NOP));
525  } else {
526  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
527  .addReg(Mips::SP)
528  .addImm(8);
529  }
530  BalTgtMBB->rbegin()->bundleWithPred();
531  }
532  } else {
533  // Pre R6:
534  // $longbr:
535  // daddiu $sp, $sp, -16
536  // sd $ra, 0($sp)
537  // daddiu $at, $zero, %hi($tgt - $baltgt)
538  // dsll $at, $at, 16
539  // bal $baltgt
540  // daddiu $at, $at, %lo($tgt - $baltgt)
541  // $baltgt:
542  // daddu $at, $ra, $at
543  // ld $ra, 0($sp)
544  // jr64 $at
545  // daddiu $sp, $sp, 16
546  // $fallthrough:
547 
548  // R6:
549  // $longbr:
550  // daddiu $sp, $sp, -16
551  // sd $ra, 0($sp)
552  // daddiu $at, $zero, %hi($tgt - $baltgt)
553  // dsll $at, $at, 16
554  // daddiu $at, $at, %lo($tgt - $baltgt)
555  // balc $baltgt
556  // $baltgt:
557  // daddu $at, $ra, $at
558  // ld $ra, 0($sp)
559  // daddiu $sp, $sp, 16
560  // jic $at, 0
561  // $fallthrough:
562 
563  // We assume the branch is within-function, and that offset is within
564  // +/- 2GB. High 32 bits will therefore always be zero.
565 
566  // Note that this will work even if the offset is negative, because
567  // of the +1 modification that's added in that case. For example, if the
568  // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
569  //
570  // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
571  //
572  // and the bits [47:32] are zero. For %highest
573  //
574  // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
575  //
576  // and the bits [63:48] are zero.
577 
578  Pos = LongBrMBB->begin();
579 
580  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
581  .addReg(Mips::SP_64)
582  .addImm(-16);
583  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))
584  .addReg(Mips::RA_64)
585  .addReg(Mips::SP_64)
586  .addImm(0);
587  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
588  Mips::AT_64)
589  .addReg(Mips::ZERO_64)
590  .addMBB(TgtMBB, MipsII::MO_ABS_HI)
591  .addMBB(BalTgtMBB);
592  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
593  .addReg(Mips::AT_64)
594  .addImm(16);
595 
596  MachineInstrBuilder BalInstr =
597  BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
598  MachineInstrBuilder DADDiuInstr =
599  BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
600  .addReg(Mips::AT_64)
601  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
602  .addMBB(BalTgtMBB);
603  if (STI->hasMips32r6()) {
604  LongBrMBB->insert(Pos, DADDiuInstr);
605  LongBrMBB->insert(Pos, BalInstr);
606  } else {
607  LongBrMBB->insert(Pos, BalInstr);
608  LongBrMBB->insert(Pos, DADDiuInstr);
609  LongBrMBB->rbegin()->bundleWithPred();
610  }
611 
612  Pos = BalTgtMBB->begin();
613 
614  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
615  .addReg(Mips::RA_64)
616  .addReg(Mips::AT_64);
617  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
618  .addReg(Mips::SP_64)
619  .addImm(0);
620 
621  bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
622  // If there is no delay slot, Insert stack adjustment before
623  if (!hasDelaySlot) {
624  BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::DADDiu),
625  Mips::SP_64)
626  .addReg(Mips::SP_64)
627  .addImm(16);
628  } else {
629  BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
630  .addReg(Mips::SP_64)
631  .addImm(16);
632  BalTgtMBB->rbegin()->bundleWithPred();
633  }
634  }
635  } else { // Not PIC
636  Pos = LongBrMBB->begin();
637  LongBrMBB->addSuccessor(TgtMBB);
638 
639  // Compute the position of the potentiall jump instruction (basic blocks
640  // before + 4 for the instruction)
641  uint64_t JOffset = computeOffsetFromTheBeginning(MBB->getNumber()) +
642  MBBInfos[MBB->getNumber()].Size + 4;
643  uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
644  // If it's a forward jump, then TgtMBBOffset will be shifted by two
645  // instructions
646  if (JOffset < TgtMBBOffset)
647  TgtMBBOffset += 2 * 4;
648  // Compare 4 upper bits to check if it's the same segment
649  bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
650 
651  if (STI->hasMips32r6() && TII->isBranchOffsetInRange(Mips::BC, I.Offset)) {
652  // R6:
653  // $longbr:
654  // bc $tgt
655  // $fallthrough:
656  //
657  BuildMI(*LongBrMBB, Pos, DL,
658  TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
659  .addMBB(TgtMBB);
660  } else if (SameSegmentJump) {
661  // Pre R6:
662  // $longbr:
663  // j $tgt
664  // nop
665  // $fallthrough:
666  //
667  MIBundleBuilder(*LongBrMBB, Pos)
668  .append(BuildMI(*MFp, DL, TII->get(Mips::J)).addMBB(TgtMBB))
669  .append(BuildMI(*MFp, DL, TII->get(Mips::NOP)));
670  } else {
671  // At this point, offset where we need to branch does not fit into
672  // immediate field of the branch instruction and is not in the same
673  // segment as jump instruction. Therefore we will break it into couple
674  // instructions, where we first load the offset into register, and then we
675  // do branch register.
676  if (ABI.IsN64()) {
677  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op_64),
678  Mips::AT_64)
679  .addMBB(TgtMBB, MipsII::MO_HIGHEST);
680  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
681  Mips::AT_64)
682  .addReg(Mips::AT_64)
683  .addMBB(TgtMBB, MipsII::MO_HIGHER);
684  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
685  .addReg(Mips::AT_64)
686  .addImm(16);
687  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
688  Mips::AT_64)
689  .addReg(Mips::AT_64)
690  .addMBB(TgtMBB, MipsII::MO_ABS_HI);
691  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
692  .addReg(Mips::AT_64)
693  .addImm(16);
694  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
695  Mips::AT_64)
696  .addReg(Mips::AT_64)
697  .addMBB(TgtMBB, MipsII::MO_ABS_LO);
698  } else {
699  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op),
700  Mips::AT)
701  .addMBB(TgtMBB, MipsII::MO_ABS_HI);
702  BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_ADDiu2Op),
703  Mips::AT)
704  .addReg(Mips::AT)
705  .addMBB(TgtMBB, MipsII::MO_ABS_LO);
706  }
707  buildProperJumpMI(LongBrMBB, Pos, DL);
708  }
709  }
710 
711  if (I.Br->isUnconditionalBranch()) {
712  // Change branch destination.
713  assert(I.Br->getDesc().getNumOperands() == 1);
714  I.Br->RemoveOperand(0);
715  I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
716  } else
717  // Change branch destination and reverse condition.
718  replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
719 }
720 
722  MachineBasicBlock &MBB = F.front();
724  DebugLoc DL = MBB.findDebugLoc(MBB.begin());
725  BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
726  .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
727  BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
728  .addReg(Mips::V0)
729  .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
730  MBB.removeLiveIn(Mips::V0);
731 }
732 
733 bool MipsBranchExpansion::handleForbiddenSlot() {
734  // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.
735  if (!STI->hasMips32r6() || STI->inMicroMipsMode())
736  return false;
737 
738  bool Changed = false;
739 
740  for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {
741  for (Iter I = FI->begin(); I != FI->end(); ++I) {
742 
743  // Forbidden slot hazard handling. Use lookahead over state.
744  if (!TII->HasForbiddenSlot(*I))
745  continue;
746 
747  Iter Inst;
748  bool LastInstInFunction =
749  std::next(I) == FI->end() && std::next(FI) == MFp->end();
750  if (!LastInstInFunction) {
751  std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
752  LastInstInFunction |= Res.second;
753  Inst = Res.first;
754  }
755 
756  if (LastInstInFunction || !TII->SafeInForbiddenSlot(*Inst)) {
757 
758  MachineBasicBlock::instr_iterator Iit = I->getIterator();
759  if (std::next(Iit) == FI->end() ||
760  std::next(Iit)->getOpcode() != Mips::NOP) {
761  Changed = true;
762  MIBundleBuilder(&*I).append(
763  BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
764  NumInsertedNops++;
765  }
766  }
767  }
768  }
769 
770  return Changed;
771 }
772 
773 bool MipsBranchExpansion::handlePossibleLongBranch() {
774  if (STI->inMips16Mode() || !STI->enableLongBranchPass())
775  return false;
776 
777  if (SkipLongBranch)
778  return false;
779 
780  bool EverMadeChange = false, MadeChange = true;
781 
782  while (MadeChange) {
783  MadeChange = false;
784 
785  initMBBInfo();
786 
787  for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
788  MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
789  // Search for MBB's branch instruction.
790  ReverseIter End = MBB->rend();
791  ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
792 
793  if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&
794  (Br->isConditionalBranch() ||
795  (Br->isUnconditionalBranch() && IsPIC))) {
796  int64_t Offset = computeOffset(&*Br);
797 
798  if (STI->isTargetNaCl()) {
799  // The offset calculation does not include sandboxing instructions
800  // that will be added later in the MC layer. Since at this point we
801  // don't know the exact amount of code that "sandboxing" will add, we
802  // conservatively estimate that code will not grow more than 100%.
803  Offset *= 2;
804  }
805 
806  if (ForceLongBranchFirstPass ||
807  !TII->isBranchOffsetInRange(Br->getOpcode(), Offset)) {
808  MBBInfos[I].Offset = Offset;
809  MBBInfos[I].Br = &*Br;
810  }
811  }
812  } // End for
813 
814  ForceLongBranchFirstPass = false;
815 
816  SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
817 
818  for (I = MBBInfos.begin(); I != E; ++I) {
819  // Skip if this MBB doesn't have a branch or the branch has already been
820  // converted to a long branch.
821  if (!I->Br)
822  continue;
823 
824  expandToLongBranch(*I);
825  ++LongBranches;
826  EverMadeChange = MadeChange = true;
827  }
828 
829  MFp->RenumberBlocks();
830  }
831 
832  return EverMadeChange;
833 }
834 
835 bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
836  const TargetMachine &TM = MF.getTarget();
837  IsPIC = TM.isPositionIndependent();
838  ABI = static_cast<const MipsTargetMachine &>(TM).getABI();
839  STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
840  TII = static_cast<const MipsInstrInfo *>(STI->getInstrInfo());
841 
842  if (IsPIC && ABI.IsO32() &&
843  MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
844  emitGPDisp(MF, TII);
845 
846  MFp = &MF;
847 
848  ForceLongBranchFirstPass = ForceLongBranch;
849  // Run these two at least once
850  bool longBranchChanged = handlePossibleLongBranch();
851  bool forbiddenSlotChanged = handleForbiddenSlot();
852 
853  bool Changed = longBranchChanged || forbiddenSlotChanged;
854 
855  // Then run them alternatively while there are changes
856  while (forbiddenSlotChanged) {
857  longBranchChanged = handlePossibleLongBranch();
858  if (!longBranchChanged)
859  break;
860  forbiddenSlotChanged = handleForbiddenSlot();
861  }
862 
863  return Changed;
864 }
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:289
This class represents lattice values for constants.
Definition: AllocatorList.h:24
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: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:34
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:480
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:42
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:406
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:21
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:423
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")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:285
auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Definition: STLExtras.h:1219
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:847
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:254
MachineFunctionProperties & set(Property P)
static const unsigned MIPS_NACL_BUNDLE_ALIGN
Definition: MipsMCNaCl.h:18
Representation of each machine instruction.
Definition: MachineInstr.h:64
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:47
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:59
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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:414
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.