Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Mips/MipsBranchExpansion.cpp
Line
Count
Source (jump to first uncovered line)
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
74
#include "MCTargetDesc/MipsABIInfo.h"
75
#include "MCTargetDesc/MipsBaseInfo.h"
76
#include "MCTargetDesc/MipsMCNaCl.h"
77
#include "MCTargetDesc/MipsMCTargetDesc.h"
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"
86
#include "llvm/CodeGen/MachineBasicBlock.h"
87
#include "llvm/CodeGen/MachineFunction.h"
88
#include "llvm/CodeGen/MachineFunctionPass.h"
89
#include "llvm/CodeGen/MachineInstr.h"
90
#include "llvm/CodeGen/MachineInstrBuilder.h"
91
#include "llvm/CodeGen/MachineModuleInfo.h"
92
#include "llvm/CodeGen/MachineOperand.h"
93
#include "llvm/CodeGen/TargetSubtargetInfo.h"
94
#include "llvm/IR/DebugLoc.h"
95
#include "llvm/Support/CommandLine.h"
96
#include "llvm/Support/ErrorHandling.h"
97
#include "llvm/Support/MathExtras.h"
98
#include "llvm/Target/TargetMachine.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
17.3k
  MBBInfo() = default;
132
};
133
134
class MipsBranchExpansion : public MachineFunctionPass {
135
public:
136
  static char ID;
137
138
2.09k
  MipsBranchExpansion() : MachineFunctionPass(ID), ABI(MipsABIInfo::Unknown()) {
139
2.09k
    initializeMipsBranchExpansionPass(*PassRegistry::getPassRegistry());
140
2.09k
  }
141
142
15.4k
  StringRef getPassName() const override {
143
15.4k
    return "Mips Branch Expansion Pass";
144
15.4k
  }
145
146
  bool runOnMachineFunction(MachineFunction &F) override;
147
148
2.04k
  MachineFunctionProperties getRequiredProperties() const override {
149
2.04k
    return MachineFunctionProperties().set(
150
2.04k
        MachineFunctionProperties::Property::NoVRegs);
151
2.04k
  }
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,
161
                         MachineBasicBlock::iterator Pos, DebugLoc DL);
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;
172
  MipsABIInfo ABI;
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.
186
2.09k
FunctionPass *llvm::createMipsBranchExpansion() {
187
2.09k
  return new MipsBranchExpansion();
188
2.09k
}
189
190
// Find the next real instruction from the current position in current basic
191
// block.
192
242
static Iter getNextMachineInstrInBB(Iter Position) {
193
242
  Iter I = Position, E = Position->getParent()->end();
194
242
  I = std::find_if_not(I, E,
195
242
                       [](const Iter &Insn) { return Insn->isTransient(); });
196
242
197
242
  return I;
198
242
}
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
242
                                                 MachineBasicBlock *Parent) {
204
242
  if (Position == Parent->end()) {
205
244
    do {
206
244
      MachineBasicBlock *Succ = Parent->getNextNode();
207
244
      if (Succ != nullptr && Parent->isSuccessor(Succ)) {
208
244
        Position = Succ->begin();
209
244
        Parent = Succ;
210
244
      } else {
211
0
        return std::make_pair(Position, true);
212
0
      }
213
244
    } while (Parent->empty());
214
242
  }
215
242
216
242
  Iter Instr = getNextMachineInstrInBB(Position);
217
242
  if (Instr == Parent->end()) {
218
1
    return getNextMachineInstr(Instr, Parent);
219
1
  }
220
241
  return std::make_pair(Instr, false);
221
241
}
222
223
/// Iterate over list of Br's operands and search for a MachineBasicBlock
224
/// operand.
225
2.32k
static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
226
5.57k
  for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; 
++I3.25k
) {
227
5.57k
    const MachineOperand &MO = Br.getOperand(I);
228
5.57k
229
5.57k
    if (MO.isMBB())
230
2.32k
      return MO.getMBB();
231
5.57k
  }
232
2.32k
233
2.32k
  
llvm_unreachable0
("This instruction does not have an MBB operand.");
234
2.32k
}
235
236
// Traverse the list of instructions backwards until a non-debug instruction is
237
// found or it reaches E.
238
37.0k
static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) {
239
37.0k
  for (; B != E; 
++B1
)
240
36.4k
    if (!B->isDebugInstr())
241
36.4k
      return B;
242
37.0k
243
37.0k
  
return E634
;
244
37.0k
}
245
246
// Split MBB if it has two direct jumps/branches.
247
17.3k
void MipsBranchExpansion::splitMBB(MachineBasicBlock *MBB) {
248
17.3k
  ReverseIter End = MBB->rend();
249
17.3k
  ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
250
17.3k
251
17.3k
  // Return if MBB has no branch instructions.
252
17.3k
  if ((LastBr == End) ||
253
17.3k
      
(17.3k
!LastBr->isConditionalBranch()17.3k
&&
!LastBr->isUnconditionalBranch()15.6k
))
254
14.9k
    return;
255
2.37k
256
2.37k
  ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);
257
2.37k
258
2.37k
  // MBB has only one branch instruction if FirstBr is not a branch
259
2.37k
  // instruction.
260
2.37k
  if ((FirstBr == End) ||
261
2.37k
      
(1.81k
!FirstBr->isConditionalBranch()1.81k
&&
!FirstBr->isUnconditionalBranch()1.71k
))
262
2.28k
    return;
263
92
264
92
  assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
265
92
266
92
  // Create a new MBB. Move instructions in MBB to the newly created MBB.
267
92
  MachineBasicBlock *NewMBB =
268
92
      MFp->CreateMachineBasicBlock(MBB->getBasicBlock());
269
92
270
92
  // Insert NewMBB and fix control flow.
271
92
  MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
272
92
  NewMBB->transferSuccessors(MBB);
273
92
  if (Tgt != getTargetMBB(*LastBr))
274
90
    NewMBB->removeSuccessor(Tgt, true);
275
92
  MBB->addSuccessor(NewMBB);
276
92
  MBB->addSuccessor(Tgt);
277
92
  MFp->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
278
92
279
92
  NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->end());
280
92
}
281
282
// Fill MBBInfos.
283
13.2k
void MipsBranchExpansion::initMBBInfo() {
284
13.2k
  // Split the MBBs if they have two branches. Each basic block should have at
285
13.2k
  // most one branch after this loop is executed.
286
13.2k
  for (auto &MBB : *MFp)
287
17.3k
    splitMBB(&MBB);
288
13.2k
289
13.2k
  MFp->RenumberBlocks();
290
13.2k
  MBBInfos.clear();
291
13.2k
  MBBInfos.resize(MFp->size());
292
13.2k
293
30.6k
  for (unsigned I = 0, E = MBBInfos.size(); I < E; 
++I17.3k
) {
294
17.3k
    MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
295
17.3k
296
17.3k
    // Compute size of MBB.
297
17.3k
    for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
298
146k
         MI != MBB->instr_end(); 
++MI129k
)
299
129k
      MBBInfos[I].Size += TII->getInstSizeInBytes(*MI);
300
17.3k
  }
301
13.2k
}
302
303
// Compute offset of branch in number of bytes.
304
1.94k
int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) {
305
1.94k
  int64_t Offset = 0;
306
1.94k
  int ThisMBB = Br->getParent()->getNumber();
307
1.94k
  int TargetMBB = getTargetMBB(*Br)->getNumber();
308
1.94k
309
1.94k
  // Compute offset of a forward branch.
310
1.94k
  if (ThisMBB < TargetMBB) {
311
2.93k
    for (int N = ThisMBB + 1; N < TargetMBB; 
++N1.69k
)
312
1.69k
      Offset += MBBInfos[N].Size;
313
1.23k
314
1.23k
    return Offset + 4;
315
1.23k
  }
316
711
317
711
  // Compute offset of a backward branch.
318
1.81k
  
for (int N = ThisMBB; 711
N >= TargetMBB;
--N1.10k
)
319
1.10k
    Offset += MBBInfos[N].Size;
320
711
321
711
  return -Offset + 4;
322
711
}
323
324
// Returns the distance in bytes up until MBB
325
204
uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(int MBB) {
326
204
  uint64_t Offset = 0;
327
426
  for (int N = 0; N < MBB; 
++N222
)
328
222
    Offset += MBBInfos[N].Size;
329
204
  return Offset;
330
204
}
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
193
                                        MachineBasicBlock *MBBOpnd) {
337
193
  unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
338
193
  const MCInstrDesc &NewDesc = TII->get(NewOpc);
339
193
340
193
  MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
341
193
342
458
  for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; 
++I265
) {
343
458
    MachineOperand &MO = Br->getOperand(I);
344
458
345
458
    if (!MO.isReg()) {
346
193
      assert(MO.isMBB() && "MBB operand expected.");
347
193
      break;
348
193
    }
349
265
350
265
    MIB.addReg(MO.getReg());
351
265
  }
352
193
353
193
  MIB.addMBB(MBBOpnd);
354
193
355
193
  if (Br->hasDelaySlot()) {
356
95
    // Bundle the instruction in the delay slot to the newly created branch
357
95
    // and erase the original branch.
358
95
    assert(Br->isBundledWithSucc());
359
95
    MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
360
95
    MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
361
95
  }
362
193
  Br->eraseFromParent();
363
193
}
364
365
bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,
366
                                            MachineBasicBlock::iterator Pos,
367
101
                                            DebugLoc DL) {
368
101
  bool HasR6 = ABI.IsN64() ? 
STI->hasMips64r6()37
:
STI->hasMips32r6()64
;
369
101
  bool AddImm = HasR6 && 
!STI->useIndirectJumpsHazard()38
;
370
101
371
101
  unsigned JR = ABI.IsN64() ? 
Mips::JR6437
:
Mips::JR64
;
372
101
  unsigned JIC = ABI.IsN64() ? 
Mips::JIC6437
:
Mips::JIC64
;
373
101
  unsigned JR_HB = ABI.IsN64() ? 
Mips::JR_HB6437
:
Mips::JR_HB64
;
374
101
  unsigned JR_HB_R6 = ABI.IsN64() ? 
Mips::JR_HB64_R637
:
Mips::JR_HB_R664
;
375
101
376
101
  unsigned JumpOp;
377
101
  if (STI->useIndirectJumpsHazard())
378
8
    JumpOp = HasR6 ? 
JR_HB_R64
:
JR_HB4
;
379
93
  else
380
93
    JumpOp = HasR6 ? 
JIC34
:
JR59
;
381
101
382
101
  if (JumpOp == Mips::JIC && 
STI->inMicroMipsMode()32
)
383
15
    JumpOp = Mips::JIC_MMR6;
384
101
385
101
  unsigned ATReg = ABI.IsN64() ? 
Mips::AT_6437
:
Mips::AT64
;
386
101
  MachineInstrBuilder Instr =
387
101
      BuildMI(*MBB, Pos, DL, TII->get(JumpOp)).addReg(ATReg);
388
101
  if (AddImm)
389
34
    Instr.addImm(0);
390
101
391
101
  return !AddImm;
392
101
}
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
195
void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {
400
195
  MachineBasicBlock::iterator Pos;
401
195
  MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
402
195
  DebugLoc DL = I.Br->getDebugLoc();
403
195
  const BasicBlock *BB = MBB->getBasicBlock();
404
195
  MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
405
195
  MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);
406
195
407
195
  MFp->insert(FallThroughMBB, LongBrMBB);
408
195
  MBB->replaceSuccessor(TgtMBB, LongBrMBB);
409
195
410
195
  if (IsPIC) {
411
93
    MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
412
93
    MFp->insert(FallThroughMBB, BalTgtMBB);
413
93
    LongBrMBB->addSuccessor(BalTgtMBB);
414
93
    BalTgtMBB->addSuccessor(TgtMBB);
415
93
416
93
    // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
417
93
    // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
418
93
    // pseudo-instruction wrapping BGEZAL).
419
93
    const unsigned BalOp =
420
93
        STI->hasMips32r6()
421
93
            ? 
STI->inMicroMipsMode() 34
?
Mips::BALC_MMR615
:
Mips::BALC19
422
93
            : 
STI->inMicroMipsMode() 59
?
Mips::BAL_BR_MM15
:
Mips::BAL_BR44
;
423
93
424
93
    if (!ABI.IsN64()) {
425
60
      // Pre R6:
426
60
      // $longbr:
427
60
      //  addiu $sp, $sp, -8
428
60
      //  sw $ra, 0($sp)
429
60
      //  lui $at, %hi($tgt - $baltgt)
430
60
      //  bal $baltgt
431
60
      //  addiu $at, $at, %lo($tgt - $baltgt)
432
60
      // $baltgt:
433
60
      //  addu $at, $ra, $at
434
60
      //  lw $ra, 0($sp)
435
60
      //  jr $at
436
60
      //  addiu $sp, $sp, 8
437
60
      // $fallthrough:
438
60
      //
439
60
440
60
      // R6:
441
60
      // $longbr:
442
60
      //  addiu $sp, $sp, -8
443
60
      //  sw $ra, 0($sp)
444
60
      //  lui $at, %hi($tgt - $baltgt)
445
60
      //  addiu $at, $at, %lo($tgt - $baltgt)
446
60
      //  balc $baltgt
447
60
      // $baltgt:
448
60
      //  addu $at, $ra, $at
449
60
      //  lw $ra, 0($sp)
450
60
      //  addiu $sp, $sp, 8
451
60
      //  jic $at, 0
452
60
      // $fallthrough:
453
60
454
60
      Pos = LongBrMBB->begin();
455
60
456
60
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
457
60
          .addReg(Mips::SP)
458
60
          .addImm(-8);
459
60
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))
460
60
          .addReg(Mips::RA)
461
60
          .addReg(Mips::SP)
462
60
          .addImm(0);
463
60
464
60
      // LUi and ADDiu instructions create 32-bit offset of the target basic
465
60
      // block from the target of BAL(C) instruction.  We cannot use immediate
466
60
      // value for this offset because it cannot be determined accurately when
467
60
      // the program has inline assembly statements.  We therefore use the
468
60
      // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
469
60
      // are resolved during the fixup, so the values will always be correct.
470
60
      //
471
60
      // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
472
60
      // expressions at this point (it is possible only at the MC layer),
473
60
      // we replace LUi and ADDiu with pseudo instructions
474
60
      // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
475
60
      // blocks as operands to these instructions.  When lowering these pseudo
476
60
      // instructions to LUi and ADDiu in the MC layer, we will create
477
60
      // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
478
60
      // operands to lowered instructions.
479
60
480
60
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
481
60
          .addMBB(TgtMBB, MipsII::MO_ABS_HI)
482
60
          .addMBB(BalTgtMBB);
483
60
484
60
      MachineInstrBuilder BalInstr =
485
60
          BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
486
60
      MachineInstrBuilder ADDiuInstr =
487
60
          BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
488
60
              .addReg(Mips::AT)
489
60
              .addMBB(TgtMBB, MipsII::MO_ABS_LO)
490
60
              .addMBB(BalTgtMBB);
491
60
      if (STI->hasMips32r6()) {
492
32
        LongBrMBB->insert(Pos, ADDiuInstr);
493
32
        LongBrMBB->insert(Pos, BalInstr);
494
32
      } else {
495
28
        LongBrMBB->insert(Pos, BalInstr);
496
28
        LongBrMBB->insert(Pos, ADDiuInstr);
497
28
        LongBrMBB->rbegin()->bundleWithPred();
498
28
      }
499
60
500
60
      Pos = BalTgtMBB->begin();
501
60
502
60
      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
503
60
          .addReg(Mips::RA)
504
60
          .addReg(Mips::AT);
505
60
      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
506
60
          .addReg(Mips::SP)
507
60
          .addImm(0);
508
60
      if (STI->isTargetNaCl())
509
1
        // Bundle-align the target of indirect branch JR.
510
1
        TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
511
60
512
60
      // In NaCl, modifying the sp is not allowed in branch delay slot.
513
60
      // For MIPS32R6, we can skip using a delay slot branch.
514
60
      bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
515
60
516
60
      if (STI->isTargetNaCl() || 
!hasDelaySlot59
) {
517
32
        BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::ADDiu), Mips::SP)
518
32
            .addReg(Mips::SP)
519
32
            .addImm(8);
520
32
      }
521
60
      if (hasDelaySlot) {
522
29
        if (STI->isTargetNaCl()) {
523
1
          BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::NOP));
524
28
        } else {
525
28
          BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
526
28
              .addReg(Mips::SP)
527
28
              .addImm(8);
528
28
        }
529
29
        BalTgtMBB->rbegin()->bundleWithPred();
530
29
      }
531
60
    } else {
532
33
      // Pre R6:
533
33
      // $longbr:
534
33
      //  daddiu $sp, $sp, -16
535
33
      //  sd $ra, 0($sp)
536
33
      //  daddiu $at, $zero, %hi($tgt - $baltgt)
537
33
      //  dsll $at, $at, 16
538
33
      //  bal $baltgt
539
33
      //  daddiu $at, $at, %lo($tgt - $baltgt)
540
33
      // $baltgt:
541
33
      //  daddu $at, $ra, $at
542
33
      //  ld $ra, 0($sp)
543
33
      //  jr64 $at
544
33
      //  daddiu $sp, $sp, 16
545
33
      // $fallthrough:
546
33
547
33
      // R6:
548
33
      // $longbr:
549
33
      //  daddiu $sp, $sp, -16
550
33
      //  sd $ra, 0($sp)
551
33
      //  daddiu $at, $zero, %hi($tgt - $baltgt)
552
33
      //  dsll $at, $at, 16
553
33
      //  daddiu $at, $at, %lo($tgt - $baltgt)
554
33
      //  balc $baltgt
555
33
      // $baltgt:
556
33
      //  daddu $at, $ra, $at
557
33
      //  ld $ra, 0($sp)
558
33
      //  daddiu $sp, $sp, 16
559
33
      //  jic $at, 0
560
33
      // $fallthrough:
561
33
562
33
      // We assume the branch is within-function, and that offset is within
563
33
      // +/- 2GB.  High 32 bits will therefore always be zero.
564
33
565
33
      // Note that this will work even if the offset is negative, because
566
33
      // of the +1 modification that's added in that case.  For example, if the
567
33
      // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
568
33
      //
569
33
      // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
570
33
      //
571
33
      // and the bits [47:32] are zero.  For %highest
572
33
      //
573
33
      // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
574
33
      //
575
33
      // and the bits [63:48] are zero.
576
33
577
33
      Pos = LongBrMBB->begin();
578
33
579
33
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
580
33
          .addReg(Mips::SP_64)
581
33
          .addImm(-16);
582
33
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))
583
33
          .addReg(Mips::RA_64)
584
33
          .addReg(Mips::SP_64)
585
33
          .addImm(0);
586
33
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
587
33
              Mips::AT_64)
588
33
          .addReg(Mips::ZERO_64)
589
33
          .addMBB(TgtMBB, MipsII::MO_ABS_HI)
590
33
          .addMBB(BalTgtMBB);
591
33
      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
592
33
          .addReg(Mips::AT_64)
593
33
          .addImm(16);
594
33
595
33
      MachineInstrBuilder BalInstr =
596
33
          BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
597
33
      MachineInstrBuilder DADDiuInstr =
598
33
          BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
599
33
              .addReg(Mips::AT_64)
600
33
              .addMBB(TgtMBB, MipsII::MO_ABS_LO)
601
33
              .addMBB(BalTgtMBB);
602
33
      if (STI->hasMips32r6()) {
603
2
        LongBrMBB->insert(Pos, DADDiuInstr);
604
2
        LongBrMBB->insert(Pos, BalInstr);
605
31
      } else {
606
31
        LongBrMBB->insert(Pos, BalInstr);
607
31
        LongBrMBB->insert(Pos, DADDiuInstr);
608
31
        LongBrMBB->rbegin()->bundleWithPred();
609
31
      }
610
33
611
33
      Pos = BalTgtMBB->begin();
612
33
613
33
      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
614
33
          .addReg(Mips::RA_64)
615
33
          .addReg(Mips::AT_64);
616
33
      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
617
33
          .addReg(Mips::SP_64)
618
33
          .addImm(0);
619
33
620
33
      bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
621
33
      // If there is no delay slot, Insert stack adjustment before
622
33
      if (!hasDelaySlot) {
623
1
        BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::DADDiu),
624
1
                Mips::SP_64)
625
1
            .addReg(Mips::SP_64)
626
1
            .addImm(16);
627
32
      } else {
628
32
        BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
629
32
            .addReg(Mips::SP_64)
630
32
            .addImm(16);
631
32
        BalTgtMBB->rbegin()->bundleWithPred();
632
32
      }
633
33
    }
634
102
  } else { // Not PIC
635
102
    Pos = LongBrMBB->begin();
636
102
    LongBrMBB->addSuccessor(TgtMBB);
637
102
638
102
    // Compute the position of the potentiall jump instruction (basic blocks
639
102
    // before + 4 for the instruction)
640
102
    uint64_t JOffset = computeOffsetFromTheBeginning(MBB->getNumber()) +
641
102
                       MBBInfos[MBB->getNumber()].Size + 4;
642
102
    uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
643
102
    // If it's a forward jump, then TgtMBBOffset will be shifted by two
644
102
    // instructions
645
102
    if (JOffset < TgtMBBOffset)
646
102
      TgtMBBOffset += 2 * 4;
647
102
    // Compare 4 upper bits to check if it's the same segment
648
102
    bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
649
102
650
102
    if (STI->hasMips32r6() && 
TII->isBranchOffsetInRange(Mips::BC, I.Offset)47
) {
651
41
      // R6:
652
41
      // $longbr:
653
41
      //  bc $tgt
654
41
      // $fallthrough:
655
41
      //
656
41
      BuildMI(*LongBrMBB, Pos, DL,
657
41
              TII->get(STI->inMicroMipsMode() ? 
Mips::BC_MMR615
:
Mips::BC26
))
658
41
          .addMBB(TgtMBB);
659
61
    } else if (SameSegmentJump) {
660
53
      // Pre R6:
661
53
      // $longbr:
662
53
      //  j $tgt
663
53
      //  nop
664
53
      // $fallthrough:
665
53
      //
666
53
      MIBundleBuilder(*LongBrMBB, Pos)
667
53
          .append(BuildMI(*MFp, DL, TII->get(Mips::J)).addMBB(TgtMBB))
668
53
          .append(BuildMI(*MFp, DL, TII->get(Mips::NOP)));
669
53
    } else {
670
8
      // At this point, offset where we need to branch does not fit into
671
8
      // immediate field of the branch instruction and is not in the same
672
8
      // segment as jump instruction. Therefore we will break it into couple
673
8
      // instructions, where we first load the offset into register, and then we
674
8
      // do branch register.
675
8
      if (ABI.IsN64()) {
676
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op_64),
677
4
                Mips::AT_64)
678
4
            .addMBB(TgtMBB, MipsII::MO_HIGHEST);
679
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
680
4
                Mips::AT_64)
681
4
            .addReg(Mips::AT_64)
682
4
            .addMBB(TgtMBB, MipsII::MO_HIGHER);
683
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
684
4
            .addReg(Mips::AT_64)
685
4
            .addImm(16);
686
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
687
4
                Mips::AT_64)
688
4
            .addReg(Mips::AT_64)
689
4
            .addMBB(TgtMBB, MipsII::MO_ABS_HI);
690
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
691
4
            .addReg(Mips::AT_64)
692
4
            .addImm(16);
693
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
694
4
                Mips::AT_64)
695
4
            .addReg(Mips::AT_64)
696
4
            .addMBB(TgtMBB, MipsII::MO_ABS_LO);
697
4
      } else {
698
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op),
699
4
                Mips::AT)
700
4
            .addMBB(TgtMBB, MipsII::MO_ABS_HI);
701
4
        BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_ADDiu2Op),
702
4
                Mips::AT)
703
4
            .addReg(Mips::AT)
704
4
            .addMBB(TgtMBB, MipsII::MO_ABS_LO);
705
4
      }
706
8
      buildProperJumpMI(LongBrMBB, Pos, DL);
707
8
    }
708
102
  }
709
195
710
195
  if (I.Br->isUnconditionalBranch()) {
711
2
    // Change branch destination.
712
2
    assert(I.Br->getDesc().getNumOperands() == 1);
713
2
    I.Br->RemoveOperand(0);
714
2
    I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
715
2
  } else
716
193
    // Change branch destination and reverse condition.
717
193
    replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
718
195
}
719
720
2.14k
static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
721
2.14k
  MachineBasicBlock &MBB = F.front();
722
2.14k
  MachineBasicBlock::iterator I = MBB.begin();
723
2.14k
  DebugLoc DL = MBB.findDebugLoc(MBB.begin());
724
2.14k
  BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
725
2.14k
      .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
726
2.14k
  BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
727
2.14k
      .addReg(Mips::V0)
728
2.14k
      .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
729
2.14k
  MBB.removeLiveIn(Mips::V0);
730
2.14k
}
731
732
13.3k
bool MipsBranchExpansion::handleForbiddenSlot() {
733
13.3k
  // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.
734
13.3k
  if (!STI->hasMips32r6() || 
STI->inMicroMipsMode()1.88k
)
735
11.8k
    return false;
736
1.48k
737
1.48k
  bool Changed = false;
738
1.48k
739
3.70k
  for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); 
++FI2.22k
) {
740
16.0k
    for (Iter I = FI->begin(); I != FI->end(); 
++I13.8k
) {
741
13.8k
742
13.8k
      // Forbidden slot hazard handling. Use lookahead over state.
743
13.8k
      if (!TII->HasForbiddenSlot(*I))
744
13.5k
        continue;
745
241
746
241
      Iter Inst;
747
241
      bool LastInstInFunction =
748
241
          std::next(I) == FI->end() && std::next(FI) == MFp->end();
749
241
      if (!LastInstInFunction) {
750
241
        std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
751
241
        LastInstInFunction |= Res.second;
752
241
        Inst = Res.first;
753
241
      }
754
241
755
241
      if (LastInstInFunction || !TII->SafeInForbiddenSlot(*Inst)) {
756
101
757
101
        MachineBasicBlock::instr_iterator Iit = I->getIterator();
758
101
        if (std::next(Iit) == FI->end() ||
759
101
            
std::next(Iit)->getOpcode() != Mips::NOP2
) {
760
99
          Changed = true;
761
99
          MIBundleBuilder(&*I).append(
762
99
              BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
763
99
          NumInsertedNops++;
764
99
        }
765
101
      }
766
241
    }
767
2.22k
  }
768
1.48k
769
1.48k
  return Changed;
770
1.48k
}
771
772
13.4k
bool MipsBranchExpansion::handlePossibleLongBranch() {
773
13.4k
  if (STI->inMips16Mode() || 
!STI->enableLongBranchPass()13.0k
)
774
380
    return false;
775
13.0k
776
13.0k
  if (SkipLongBranch)
777
0
    return false;
778
13.0k
779
13.0k
  bool EverMadeChange = false, MadeChange = true;
780
13.0k
781
26.3k
  while (MadeChange) {
782
13.2k
    MadeChange = false;
783
13.2k
784
13.2k
    initMBBInfo();
785
13.2k
786
30.6k
    for (unsigned I = 0, E = MBBInfos.size(); I < E; 
++I17.3k
) {
787
17.3k
      MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
788
17.3k
      // Search for MBB's branch instruction.
789
17.3k
      ReverseIter End = MBB->rend();
790
17.3k
      ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
791
17.3k
792
17.3k
      if ((Br != End) && 
Br->isBranch()17.3k
&&
!Br->isIndirectBranch()3.86k
&&
793
17.3k
          
(2.37k
Br->isConditionalBranch()2.37k
||
794
2.37k
           
(622
Br->isUnconditionalBranch()622
&&
IsPIC622
))) {
795
1.94k
        int64_t Offset = computeOffset(&*Br);
796
1.94k
797
1.94k
        if (STI->isTargetNaCl()) {
798
4
          // The offset calculation does not include sandboxing instructions
799
4
          // that will be added later in the MC layer.  Since at this point we
800
4
          // don't know the exact amount of code that "sandboxing" will add, we
801
4
          // conservatively estimate that code will not grow more than 100%.
802
4
          Offset *= 2;
803
4
        }
804
1.94k
805
1.94k
        if (ForceLongBranchFirstPass ||
806
1.94k
            
!TII->isBranchOffsetInRange(Br->getOpcode(), Offset)1.92k
) {
807
195
          MBBInfos[I].Offset = Offset;
808
195
          MBBInfos[I].Br = &*Br;
809
195
        }
810
1.94k
      }
811
17.3k
    } // End for
812
13.2k
813
13.2k
    ForceLongBranchFirstPass = false;
814
13.2k
815
13.2k
    SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
816
13.2k
817
30.6k
    for (I = MBBInfos.begin(); I != E; 
++I17.3k
) {
818
17.3k
      // Skip if this MBB doesn't have a branch or the branch has already been
819
17.3k
      // converted to a long branch.
820
17.3k
      if (!I->Br)
821
17.1k
        continue;
822
195
823
195
      expandToLongBranch(*I);
824
195
      ++LongBranches;
825
195
      EverMadeChange = MadeChange = true;
826
195
    }
827
13.2k
828
13.2k
    MFp->RenumberBlocks();
829
13.2k
  }
830
13.0k
831
13.0k
  return EverMadeChange;
832
13.0k
}
833
834
13.3k
bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
835
13.3k
  const TargetMachine &TM = MF.getTarget();
836
13.3k
  IsPIC = TM.isPositionIndependent();
837
13.3k
  ABI = static_cast<const MipsTargetMachine &>(TM).getABI();
838
13.3k
  STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
839
13.3k
  TII = static_cast<const MipsInstrInfo *>(STI->getInstrInfo());
840
13.3k
841
13.3k
  if (IsPIC && 
ABI.IsO32()5.40k
&&
842
13.3k
      
MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet()3.07k
)
843
2.14k
    emitGPDisp(MF, TII);
844
13.3k
845
13.3k
  MFp = &MF;
846
13.3k
847
13.3k
  ForceLongBranchFirstPass = ForceLongBranch;
848
13.3k
  // Run these two at least once
849
13.3k
  bool longBranchChanged = handlePossibleLongBranch();
850
13.3k
  bool forbiddenSlotChanged = handleForbiddenSlot();
851
13.3k
852
13.3k
  bool Changed = longBranchChanged || 
forbiddenSlotChanged13.1k
;
853
13.3k
854
13.3k
  // Then run them alternatively while there are changes
855
13.3k
  while (forbiddenSlotChanged) {
856
94
    longBranchChanged = handlePossibleLongBranch();
857
94
    if (!longBranchChanged)
858
92
      break;
859
2
    forbiddenSlotChanged = handleForbiddenSlot();
860
2
  }
861
13.3k
862
13.3k
  return Changed;
863
13.3k
}