Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Mips/MipsDelaySlotFiller.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler -------------------===//
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
//
9
// Simple pass to fill delay slots with useful instructions.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "MCTargetDesc/MipsMCNaCl.h"
14
#include "Mips.h"
15
#include "MipsInstrInfo.h"
16
#include "MipsRegisterInfo.h"
17
#include "MipsSubtarget.h"
18
#include "llvm/ADT/BitVector.h"
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/ADT/PointerUnion.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/ADT/Statistic.h"
24
#include "llvm/ADT/StringRef.h"
25
#include "llvm/Analysis/AliasAnalysis.h"
26
#include "llvm/Analysis/ValueTracking.h"
27
#include "llvm/CodeGen/MachineBasicBlock.h"
28
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
29
#include "llvm/CodeGen/MachineFunction.h"
30
#include "llvm/CodeGen/MachineFunctionPass.h"
31
#include "llvm/CodeGen/MachineInstr.h"
32
#include "llvm/CodeGen/MachineInstrBuilder.h"
33
#include "llvm/CodeGen/MachineOperand.h"
34
#include "llvm/CodeGen/MachineRegisterInfo.h"
35
#include "llvm/CodeGen/PseudoSourceValue.h"
36
#include "llvm/CodeGen/TargetRegisterInfo.h"
37
#include "llvm/CodeGen/TargetSubtargetInfo.h"
38
#include "llvm/MC/MCInstrDesc.h"
39
#include "llvm/MC/MCRegisterInfo.h"
40
#include "llvm/Support/Casting.h"
41
#include "llvm/Support/CodeGen.h"
42
#include "llvm/Support/CommandLine.h"
43
#include "llvm/Support/ErrorHandling.h"
44
#include "llvm/Target/TargetMachine.h"
45
#include <algorithm>
46
#include <cassert>
47
#include <iterator>
48
#include <memory>
49
#include <utility>
50
51
using namespace llvm;
52
53
#define DEBUG_TYPE "mips-delay-slot-filler"
54
55
STATISTIC(FilledSlots, "Number of delay slots filled");
56
STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
57
                       " are not NOP.");
58
59
static cl::opt<bool> DisableDelaySlotFiller(
60
  "disable-mips-delay-filler",
61
  cl::init(false),
62
  cl::desc("Fill all delay slots with NOPs."),
63
  cl::Hidden);
64
65
static cl::opt<bool> DisableForwardSearch(
66
  "disable-mips-df-forward-search",
67
  cl::init(true),
68
  cl::desc("Disallow MIPS delay filler to search forward."),
69
  cl::Hidden);
70
71
static cl::opt<bool> DisableSuccBBSearch(
72
  "disable-mips-df-succbb-search",
73
  cl::init(true),
74
  cl::desc("Disallow MIPS delay filler to search successor basic blocks."),
75
  cl::Hidden);
76
77
static cl::opt<bool> DisableBackwardSearch(
78
  "disable-mips-df-backward-search",
79
  cl::init(false),
80
  cl::desc("Disallow MIPS delay filler to search backward."),
81
  cl::Hidden);
82
83
enum CompactBranchPolicy {
84
  CB_Never,   ///< The policy 'never' may in some circumstances or for some
85
              ///< ISAs not be absolutely adhered to.
86
  CB_Optimal, ///< Optimal is the default and will produce compact branches
87
              ///< when delay slots cannot be filled.
88
  CB_Always   ///< 'always' may in some circumstances may not be
89
              ///< absolutely adhered to there may not be a corresponding
90
              ///< compact form of a branch.
91
};
92
93
static cl::opt<CompactBranchPolicy> MipsCompactBranchPolicy(
94
  "mips-compact-branches",cl::Optional,
95
  cl::init(CB_Optimal),
96
  cl::desc("MIPS Specific: Compact branch policy."),
97
  cl::values(
98
    clEnumValN(CB_Never, "never", "Do not use compact branches if possible."),
99
    clEnumValN(CB_Optimal, "optimal", "Use compact branches where appropiate (default)."),
100
    clEnumValN(CB_Always, "always", "Always use compact branches if possible.")
101
  )
102
);
103
104
namespace {
105
106
  using Iter = MachineBasicBlock::iterator;
107
  using ReverseIter = MachineBasicBlock::reverse_iterator;
108
  using BB2BrMap = SmallDenseMap<MachineBasicBlock *, MachineInstr *, 2>;
109
110
  class RegDefsUses {
111
  public:
112
    RegDefsUses(const TargetRegisterInfo &TRI);
113
114
    void init(const MachineInstr &MI);
115
116
    /// This function sets all caller-saved registers in Defs.
117
    void setCallerSaved(const MachineInstr &MI);
118
119
    /// This function sets all unallocatable registers in Defs.
120
    void setUnallocatableRegs(const MachineFunction &MF);
121
122
    /// Set bits in Uses corresponding to MBB's live-out registers except for
123
    /// the registers that are live-in to SuccBB.
124
    void addLiveOut(const MachineBasicBlock &MBB,
125
                    const MachineBasicBlock &SuccBB);
126
127
    bool update(const MachineInstr &MI, unsigned Begin, unsigned End);
128
129
  private:
130
    bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg,
131
                          bool IsDef) const;
132
133
    /// Returns true if Reg or its alias is in RegSet.
134
    bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
135
136
    const TargetRegisterInfo &TRI;
137
    BitVector Defs, Uses;
138
  };
139
140
  /// Base class for inspecting loads and stores.
141
  class InspectMemInstr {
142
  public:
143
13.8k
    InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {}
144
13.8k
    virtual ~InspectMemInstr() = default;
145
146
    /// Return true if MI cannot be moved to delay slot.
147
    bool hasHazard(const MachineInstr &MI);
148
149
  protected:
150
    /// Flags indicating whether loads or stores have been seen.
151
    bool OrigSeenLoad = false;
152
    bool OrigSeenStore = false;
153
    bool SeenLoad = false;
154
    bool SeenStore = false;
155
156
    /// Memory instructions are not allowed to move to delay slot if this flag
157
    /// is true.
158
    bool ForbidMemInstr;
159
160
  private:
161
    virtual bool hasHazard_(const MachineInstr &MI) = 0;
162
  };
163
164
  /// This subclass rejects any memory instructions.
165
  class NoMemInstr : public InspectMemInstr {
166
  public:
167
6
    NoMemInstr() : InspectMemInstr(true) {}
168
169
  private:
170
0
    bool hasHazard_(const MachineInstr &MI) override { return true; }
171
  };
172
173
  /// This subclass accepts loads from stacks and constant loads.
174
  class LoadFromStackOrConst : public InspectMemInstr {
175
  public:
176
10
    LoadFromStackOrConst() : InspectMemInstr(false) {}
177
178
  private:
179
    bool hasHazard_(const MachineInstr &MI) override;
180
  };
181
182
  /// This subclass uses memory dependence information to determine whether a
183
  /// memory instruction can be moved to a delay slot.
184
  class MemDefsUses : public InspectMemInstr {
185
  public:
186
    MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI);
187
188
  private:
189
    using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;
190
191
    bool hasHazard_(const MachineInstr &MI) override;
192
193
    /// Update Defs and Uses. Return true if there exist dependences that
194
    /// disqualify the delay slot candidate between V and values in Uses and
195
    /// Defs.
196
    bool updateDefsUses(ValueType V, bool MayStore);
197
198
    /// Get the list of underlying objects of MI's memory operand.
199
    bool getUnderlyingObjects(const MachineInstr &MI,
200
                              SmallVectorImpl<ValueType> &Objects) const;
201
202
    const MachineFrameInfo *MFI;
203
    SmallPtrSet<ValueType, 4> Uses, Defs;
204
    const DataLayout &DL;
205
206
    /// Flags indicating whether loads or stores with no underlying objects have
207
    /// been seen.
208
    bool SeenNoObjLoad = false;
209
    bool SeenNoObjStore = false;
210
  };
211
212
  class MipsDelaySlotFiller : public MachineFunctionPass {
213
  public:
214
2.09k
    MipsDelaySlotFiller() : MachineFunctionPass(ID) {
215
2.09k
      initializeMipsDelaySlotFillerPass(*PassRegistry::getPassRegistry());
216
2.09k
    }
217
218
15.4k
    StringRef getPassName() const override { return "Mips Delay Slot Filler"; }
219
220
13.3k
    bool runOnMachineFunction(MachineFunction &F) override {
221
13.3k
      TM = &F.getTarget();
222
13.3k
      bool Changed = false;
223
13.3k
      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
224
30.1k
           FI != FE; 
++FI16.7k
)
225
16.7k
        Changed |= runOnMachineBasicBlock(*FI);
226
13.3k
227
13.3k
      // This pass invalidates liveness information when it reorders
228
13.3k
      // instructions to fill delay slot. Without this, -verify-machineinstrs
229
13.3k
      // will fail.
230
13.3k
      if (Changed)
231
12.9k
        F.getRegInfo().invalidateLiveness();
232
13.3k
233
13.3k
      return Changed;
234
13.3k
    }
235
236
2.04k
    MachineFunctionProperties getRequiredProperties() const override {
237
2.04k
      return MachineFunctionProperties().set(
238
2.04k
          MachineFunctionProperties::Property::NoVRegs);
239
2.04k
    }
240
241
2.04k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
242
2.04k
      AU.addRequired<MachineBranchProbabilityInfo>();
243
2.04k
      MachineFunctionPass::getAnalysisUsage(AU);
244
2.04k
    }
245
246
    static char ID;
247
248
  private:
249
    bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
250
251
    Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch,
252
                                  const DebugLoc &DL);
253
254
    /// This function checks if it is valid to move Candidate to the delay slot
255
    /// and returns true if it isn't. It also updates memory and register
256
    /// dependence information.
257
    bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
258
                        InspectMemInstr &IM) const;
259
260
    /// This function searches range [Begin, End) for an instruction that can be
261
    /// moved to the delay slot. Returns true on success.
262
    template<typename IterTy>
263
    bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
264
                     RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot,
265
                     IterTy &Filler) const;
266
267
    /// This function searches in the backward direction for an instruction that
268
    /// can be moved to the delay slot. Returns true on success.
269
    bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const;
270
271
    /// This function searches MBB in the forward direction for an instruction
272
    /// that can be moved to the delay slot. Returns true on success.
273
    bool searchForward(MachineBasicBlock &MBB, Iter Slot) const;
274
275
    /// This function searches one of MBB's successor blocks for an instruction
276
    /// that can be moved to the delay slot and inserts clones of the
277
    /// instruction into the successor's predecessor blocks.
278
    bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const;
279
280
    /// Pick a successor block of MBB. Return NULL if MBB doesn't have a
281
    /// successor block that is not a landing pad.
282
    MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const;
283
284
    /// This function analyzes MBB and returns an instruction with an unoccupied
285
    /// slot that branches to Dst.
286
    std::pair<MipsInstrInfo::BranchType, MachineInstr *>
287
    getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const;
288
289
    /// Examine Pred and see if it is possible to insert an instruction into
290
    /// one of its branches delay slot or its end.
291
    bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
292
                     RegDefsUses &RegDU, bool &HasMultipleSuccs,
293
                     BB2BrMap &BrMap) const;
294
295
    bool terminateSearch(const MachineInstr &Candidate) const;
296
297
    const TargetMachine *TM = nullptr;
298
  };
299
300
} // end anonymous namespace
301
302
char MipsDelaySlotFiller::ID = 0;
303
304
129k
static bool hasUnoccupiedSlot(const MachineInstr *MI) {
305
129k
  return MI->hasDelaySlot() && 
!MI->isBundledWithSucc()16.8k
;
306
129k
}
307
308
INITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE,
309
                "Fill delay slot for MIPS", false, false)
310
311
/// This function inserts clones of Filler into predecessor blocks.
312
8
static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {
313
8
  MachineFunction *MF = Filler->getParent()->getParent();
314
8
315
18
  for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); 
++I10
) {
316
10
    if (I->second) {
317
9
      MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler));
318
9
      ++UsefulSlots;
319
9
    } else {
320
1
      I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler));
321
1
    }
322
10
  }
323
8
}
324
325
/// This function adds registers Filler defines to MBB's live-in register list.
326
8
static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {
327
31
  for (unsigned I = 0, E = Filler->getNumOperands(); I != E; 
++I23
) {
328
23
    const MachineOperand &MO = Filler->getOperand(I);
329
23
    unsigned R;
330
23
331
23
    if (!MO.isReg() || 
!MO.isDef()17
||
!(R = MO.getReg())8
)
332
15
      continue;
333
8
334
#ifndef NDEBUG
335
    const MachineFunction &MF = *MBB.getParent();
336
    assert(MF.getSubtarget().getRegisterInfo()->getAllocatableSet(MF).test(R) &&
337
           "Shouldn't move an instruction with unallocatable registers across "
338
           "basic block boundaries.");
339
#endif
340
341
8
    if (!MBB.isLiveIn(R))
342
7
      MBB.addLiveIn(R);
343
8
  }
344
8
}
345
346
RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)
347
13.8k
    : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {}
348
349
13.7k
void RegDefsUses::init(const MachineInstr &MI) {
350
13.7k
  // Add all register operands which are explicit and non-variadic.
351
13.7k
  update(MI, 0, MI.getDesc().getNumOperands());
352
13.7k
353
13.7k
  // If MI is a call, add RA to Defs to prevent users of RA from going into
354
13.7k
  // delay slot.
355
13.7k
  if (MI.isCall())
356
1.53k
    Defs.set(Mips::RA);
357
13.7k
358
13.7k
  // Add all implicit register operands of branch instructions except
359
13.7k
  // register AT.
360
13.7k
  if (MI.isBranch()) {
361
1.29k
    update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands());
362
1.29k
    Defs.reset(Mips::AT);
363
1.29k
  }
364
13.7k
}
365
366
6
void RegDefsUses::setCallerSaved(const MachineInstr &MI) {
367
6
  assert(MI.isCall());
368
6
369
6
  // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into
370
6
  // the delay slot. The reason is that RA/RA_64 must not be changed
371
6
  // in the delay slot so that the callee can return to the caller.
372
6
  if (MI.definesRegister(Mips::RA) || 
MI.definesRegister(Mips::RA_64)0
) {
373
6
    Defs.set(Mips::RA);
374
6
    Defs.set(Mips::RA_64);
375
6
  }
376
6
377
6
  // If MI is a call, add all caller-saved registers to Defs.
378
6
  BitVector CallerSavedRegs(TRI.getNumRegs(), true);
379
6
380
6
  CallerSavedRegs.reset(Mips::ZERO);
381
6
  CallerSavedRegs.reset(Mips::ZERO_64);
382
6
383
6
  for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent());
384
102
       *R; 
++R96
)
385
504
    
for (MCRegAliasIterator AI(*R, &TRI, true); 96
AI.isValid();
++AI408
)
386
408
      CallerSavedRegs.reset(*AI);
387
6
388
6
  Defs |= CallerSavedRegs;
389
6
}
390
391
10
void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {
392
10
  BitVector AllocSet = TRI.getAllocatableSet(MF);
393
10
394
10
  for (unsigned R : AllocSet.set_bits())
395
7.88k
    
for (MCRegAliasIterator AI(R, &TRI, false); 1.84k
AI.isValid();
++AI6.04k
)
396
6.04k
      AllocSet.set(*AI);
397
10
398
10
  AllocSet.set(Mips::ZERO);
399
10
  AllocSet.set(Mips::ZERO_64);
400
10
401
10
  Defs |= AllocSet.flip();
402
10
}
403
404
void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
405
11
                             const MachineBasicBlock &SuccBB) {
406
11
  for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
407
33
       SE = MBB.succ_end(); SI != SE; 
++SI22
)
408
22
    if (*SI != &SuccBB)
409
11
      for (const auto &LI : (*SI)->liveins())
410
40
        Uses.set(LI.PhysReg);
411
11
}
412
413
30.1k
bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {
414
30.1k
  BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());
415
30.1k
  bool HasHazard = false;
416
30.1k
417
92.5k
  for (unsigned I = Begin; I != End; 
++I62.3k
) {
418
62.3k
    const MachineOperand &MO = MI.getOperand(I);
419
62.3k
420
62.3k
    if (MO.isReg() && 
MO.getReg()49.8k
)
421
49.8k
      HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef());
422
62.3k
  }
423
30.1k
424
30.1k
  Defs |= NewDefs;
425
30.1k
  Uses |= NewUses;
426
30.1k
427
30.1k
  return HasHazard;
428
30.1k
}
429
430
bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
431
49.8k
                                   unsigned Reg, bool IsDef) const {
432
49.8k
  if (IsDef) {
433
12.7k
    NewDefs.set(Reg);
434
12.7k
    // check whether Reg has already been defined or used.
435
12.7k
    return (isRegInSet(Defs, Reg) || 
isRegInSet(Uses, Reg)11.6k
);
436
12.7k
  }
437
37.1k
438
37.1k
  NewUses.set(Reg);
439
37.1k
  // check whether Reg has already been defined.
440
37.1k
  return isRegInSet(Defs, Reg);
441
37.1k
}
442
443
61.4k
bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
444
61.4k
  // Check Reg and all aliased Registers.
445
208k
  for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); 
++AI146k
)
446
151k
    if (RegSet.test(*AI))
447
4.47k
      return true;
448
61.4k
  
return false57.0k
;
449
61.4k
}
450
451
15.0k
bool InspectMemInstr::hasHazard(const MachineInstr &MI) {
452
15.0k
  if (!MI.mayStore() && 
!MI.mayLoad()11.3k
)
453
9.56k
    return false;
454
5.51k
455
5.51k
  if (ForbidMemInstr)
456
147
    return true;
457
5.36k
458
5.36k
  OrigSeenLoad = SeenLoad;
459
5.36k
  OrigSeenStore = SeenStore;
460
5.36k
  SeenLoad |= MI.mayLoad();
461
5.36k
  SeenStore |= MI.mayStore();
462
5.36k
463
5.36k
  // If MI is an ordered or volatile memory reference, disallow moving
464
5.36k
  // subsequent loads and stores to delay slot.
465
5.36k
  if (MI.hasOrderedMemoryRef() && 
(270
OrigSeenLoad270
||
OrigSeenStore262
)) {
466
8
    ForbidMemInstr = true;
467
8
    return true;
468
8
  }
469
5.36k
470
5.36k
  return hasHazard_(MI);
471
5.36k
}
472
473
10
bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) {
474
10
  if (MI.mayStore())
475
2
    return true;
476
8
477
8
  if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue())
478
3
    return true;
479
5
480
5
  if (const PseudoSourceValue *PSV =
481
5
      (*MI.memoperands_begin())->getPseudoValue()) {
482
5
    if (isa<FixedStackPseudoSourceValue>(PSV))
483
3
      return false;
484
2
    return !PSV->isConstant(nullptr) && 
!PSV->isStack()0
;
485
2
  }
486
0
487
0
  return true;
488
0
}
489
490
MemDefsUses::MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI_)
491
13.7k
    : InspectMemInstr(false), MFI(MFI_), DL(DL) {}
492
493
5.35k
bool MemDefsUses::hasHazard_(const MachineInstr &MI) {
494
5.35k
  bool HasHazard = false;
495
5.35k
496
5.35k
  // Check underlying object list.
497
5.35k
  SmallVector<ValueType, 4> Objs;
498
5.35k
  if (getUnderlyingObjects(MI, Objs)) {
499
2.11k
    for (ValueType VT : Objs)
500
2.11k
      HasHazard |= updateDefsUses(VT, MI.mayStore());
501
2.11k
    return HasHazard;
502
2.11k
  }
503
3.23k
504
3.23k
  // No underlying objects found.
505
3.23k
  HasHazard = MI.mayStore() && 
(1.93k
OrigSeenLoad1.93k
||
OrigSeenStore1.76k
);
506
3.23k
  HasHazard |= MI.mayLoad() || 
OrigSeenStore1.93k
;
507
3.23k
508
3.23k
  SeenNoObjLoad |= MI.mayLoad();
509
3.23k
  SeenNoObjStore |= MI.mayStore();
510
3.23k
511
3.23k
  return HasHazard;
512
3.23k
}
513
514
2.11k
bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {
515
2.11k
  if (MayStore)
516
1.80k
    return !Defs.insert(V).second || 
Uses.count(V)1.80k
||
SeenNoObjStore1.79k
||
517
1.80k
           
SeenNoObjLoad1.79k
;
518
313
519
313
  Uses.insert(V);
520
313
  return Defs.count(V) || 
SeenNoObjStore312
;
521
313
}
522
523
bool MemDefsUses::
524
getUnderlyingObjects(const MachineInstr &MI,
525
5.35k
                     SmallVectorImpl<ValueType> &Objects) const {
526
5.35k
  if (!MI.hasOneMemOperand())
527
14
    return false;
528
5.33k
529
5.33k
  auto & MMO = **MI.memoperands_begin();
530
5.33k
531
5.33k
  if (const PseudoSourceValue *PSV = MMO.getPseudoValue()) {
532
997
    if (!PSV->isAliased(MFI))
533
976
      return false;
534
21
    Objects.push_back(PSV);
535
21
    return true;
536
21
  }
537
4.33k
538
4.33k
  if (const Value *V = MMO.getValue()) {
539
4.06k
    SmallVector<const Value *, 4> Objs;
540
4.06k
    GetUnderlyingObjects(V, Objs, DL);
541
4.06k
542
4.06k
    for (const Value *UValue : Objs) {
543
4.06k
      if (!isIdentifiedObject(V))
544
1.96k
        return false;
545
2.09k
546
2.09k
      Objects.push_back(UValue);
547
2.09k
    }
548
4.06k
    
return true2.09k
;
549
277
  }
550
277
551
277
  return false;
552
277
}
553
554
// Replace Branch with the compact branch instruction.
555
Iter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB,
556
                                                   Iter Branch,
557
1.61k
                                                   const DebugLoc &DL) {
558
1.61k
  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
559
1.61k
  const MipsInstrInfo *TII = STI.getInstrInfo();
560
1.61k
561
1.61k
  unsigned NewOpcode = TII->getEquivalentCompactForm(Branch);
562
1.61k
  Branch = TII->genInstrWithNewOpc(NewOpcode, Branch);
563
1.61k
564
1.61k
  std::next(Branch)->eraseFromParent();
565
1.61k
  return Branch;
566
1.61k
}
567
568
// For given opcode returns opcode of corresponding instruction with short
569
// delay slot.
570
// For the pseudo TAILCALL*_MM instructions return the short delay slot
571
// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range
572
// that is too short to make use of for tail calls.
573
12
static int getEquivalentCallShort(int Opcode) {
574
12
  switch (Opcode) {
575
12
  case Mips::BGEZAL:
576
0
    return Mips::BGEZALS_MM;
577
12
  case Mips::BLTZAL:
578
0
    return Mips::BLTZALS_MM;
579
12
  case Mips::JAL:
580
8
  case Mips::JAL_MM:
581
8
    return Mips::JALS_MM;
582
8
  case Mips::JALR:
583
0
    return Mips::JALRS_MM;
584
8
  case Mips::JALR16_MM:
585
4
    return Mips::JALRS16_MM;
586
8
  case Mips::TAILCALL_MM:
587
0
    llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!");
588
8
  case Mips::TAILCALLREG:
589
0
    return Mips::JR16_MM;
590
8
  default:
591
0
    llvm_unreachable("Unexpected call instruction for microMIPS.");
592
12
  }
593
12
}
594
595
/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
596
/// We assume there is only one delay slot per delayed instruction.
597
16.7k
bool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
598
16.7k
  bool Changed = false;
599
16.7k
  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
600
16.7k
  bool InMicroMipsMode = STI.inMicroMipsMode();
601
16.7k
  const MipsInstrInfo *TII = STI.getInstrInfo();
602
16.7k
603
145k
  for (Iter I = MBB.begin(); I != MBB.end(); 
++I129k
) {
604
129k
    if (!hasUnoccupiedSlot(&*I))
605
112k
      continue;
606
16.8k
607
16.8k
    // Delay slot filling is disabled at -O0, or in microMIPS32R6.
608
16.8k
    if (!DisableDelaySlotFiller && 
(TM->getOptLevel() != CodeGenOpt::None)15.5k
&&
609
16.8k
        
!(14.2k
InMicroMipsMode14.2k
&&
STI.hasMips32r6()1.10k
)) {
610
13.8k
611
13.8k
      bool Filled = false;
612
13.8k
613
13.8k
      if (MipsCompactBranchPolicy.getValue() != CB_Always ||
614
13.8k
           
!TII->getEquivalentCompactForm(I)11
) {
615
13.8k
        if (searchBackward(MBB, *I)) {
616
11.1k
          Filled = true;
617
11.1k
        } else 
if (2.70k
I->isTerminator()2.70k
) {
618
2.06k
          if (searchSuccBBs(MBB, I)) {
619
8
            Filled = true;
620
8
          }
621
2.06k
        } else 
if (638
searchForward(MBB, I)638
) {
622
1
          Filled = true;
623
1
        }
624
13.8k
      }
625
13.8k
626
13.8k
      if (Filled) {
627
11.1k
        // Get instruction with delay slot.
628
11.1k
        MachineBasicBlock::instr_iterator DSI = I.getInstrIterator();
629
11.1k
630
11.1k
        if (InMicroMipsMode && 
TII->getInstSizeInBytes(*std::next(DSI)) == 2265
&&
631
11.1k
            
DSI->isCall()13
) {
632
12
          // If instruction in delay slot is 16b change opcode to
633
12
          // corresponding instruction with short delay slot.
634
12
635
12
          // TODO: Implement an instruction mapping table of 16bit opcodes to
636
12
          // 32bit opcodes so that an instruction can be expanded. This would
637
12
          // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop.
638
12
          // TODO: Permit b16 when branching backwards to the same function
639
12
          // if it is in range.
640
12
          DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode())));
641
12
        }
642
11.1k
        ++FilledSlots;
643
11.1k
        Changed = true;
644
11.1k
        continue;
645
11.1k
      }
646
5.77k
    }
647
5.77k
648
5.77k
    // For microMIPS if instruction is BEQ or BNE with one ZERO register, then
649
5.77k
    // instead of adding NOP replace this instruction with the corresponding
650
5.77k
    // compact branch instruction, i.e. BEQZC or BNEZC. Additionally
651
5.77k
    // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can
652
5.77k
    // be replaced with JRC16_MM.
653
5.77k
654
5.77k
    // For MIPSR6 attempt to produce the corresponding compact (no delay slot)
655
5.77k
    // form of the CTI. For indirect jumps this will not require inserting a
656
5.77k
    // NOP and for branches will hopefully avoid requiring a NOP.
657
5.77k
    if ((InMicroMipsMode ||
658
5.77k
         
(4.90k
STI.hasMips32r6()4.90k
&&
MipsCompactBranchPolicy != CB_Never1.04k
)) &&
659
5.77k
        
TII->getEquivalentCompactForm(I)1.89k
) {
660
1.61k
      I = replaceWithCompactBranch(MBB, I, I->getDebugLoc());
661
1.61k
      Changed = true;
662
1.61k
      continue;
663
1.61k
    }
664
4.15k
665
4.15k
    // Bundle the NOP to the instruction with the delay slot.
666
4.15k
    BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
667
4.15k
    MIBundleBuilder(MBB, I, std::next(I, 2));
668
4.15k
    ++FilledSlots;
669
4.15k
    Changed = true;
670
4.15k
  }
671
16.7k
672
16.7k
  return Changed;
673
16.7k
}
674
675
template <typename IterTy>
676
bool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin,
677
                                      IterTy End, RegDefsUses &RegDU,
678
                                      InspectMemInstr &IM, Iter Slot,
679
13.8k
                                      IterTy &Filler) const {
680
17.8k
  for (IterTy I = Begin; I != End;) {
681
16.6k
    IterTy CurrI = I;
682
16.6k
    ++I;
683
16.6k
684
16.6k
    // skip debug value
685
16.6k
    if (CurrI->isDebugInstr())
686
2
      continue;
687
16.6k
688
16.6k
    if (terminateSearch(*CurrI))
689
1.50k
      break;
690
15.1k
691
15.1k
    assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
692
15.1k
           "Cannot put calls, returns or branches in delay slot.");
693
15.1k
694
15.1k
    if (CurrI->isKill()) {
695
44
      CurrI->eraseFromParent();
696
44
      continue;
697
44
    }
698
15.0k
699
15.0k
    if (delayHasHazard(*CurrI, RegDU, IM))
700
3.82k
      continue;
701
11.2k
702
11.2k
    const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
703
11.2k
    if (STI.isTargetNaCl()) {
704
30
      // In NaCl, instructions that must be masked are forbidden in delay slots.
705
30
      // We only check for loads, stores and SP changes.  Calls, returns and
706
30
      // branches are not checked because non-NaCl targets never put them in
707
30
      // delay slots.
708
30
      unsigned AddrIdx;
709
30
      if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
710
30
           
baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())8
) ||
711
30
          
CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo())22
)
712
20
        continue;
713
11.2k
    }
714
11.2k
715
11.2k
    bool InMicroMipsMode = STI.inMicroMipsMode();
716
11.2k
    const MipsInstrInfo *TII = STI.getInstrInfo();
717
11.2k
    unsigned Opcode = (*Slot).getOpcode();
718
11.2k
    // This is complicated by the tail call optimization. For non-PIC code
719
11.2k
    // there is only a 32bit sized unconditional branch which can be assumed
720
11.2k
    // to be able to reach the target. b16 only has a range of +/- 1 KB.
721
11.2k
    // It's entirely possible that the target function is reachable with b16
722
11.2k
    // but we don't have enough information to make that decision.
723
11.2k
     if (InMicroMipsMode && 
TII->getInstSizeInBytes(*CurrI) == 2387
&&
724
11.2k
        
(135
Opcode == Mips::JR135
||
Opcode == Mips::PseudoIndirectBranch135
||
725
135
         Opcode == Mips::PseudoIndirectBranch_MM ||
726
135
         
Opcode == Mips::PseudoReturn134
||
Opcode == Mips::TAILCALL13
))
727
122
      continue;
728
11.1k
     // Instructions LWP/SWP and MOVEP should not be in a delay slot as that
729
11.1k
     // results in unpredictable behaviour
730
11.1k
     if (InMicroMipsMode && 
(265
Opcode == Mips::LWP_MM265
||
Opcode == Mips::SWP_MM265
||
731
265
                             Opcode == Mips::MOVEP_MM))
732
0
       continue;
733
11.1k
734
11.1k
    Filler = CurrI;
735
11.1k
    return true;
736
11.1k
  }
737
13.8k
738
13.8k
  
return false2.68k
;
739
13.8k
}
MipsDelaySlotFiller.cpp:bool (anonymous namespace)::MipsDelaySlotFiller::searchRange<llvm::MachineInstrBundleIterator<llvm::MachineInstr, true> >(llvm::MachineBasicBlock&, llvm::MachineInstrBundleIterator<llvm::MachineInstr, true>, llvm::MachineInstrBundleIterator<llvm::MachineInstr, true>, (anonymous namespace)::RegDefsUses&, (anonymous namespace)::InspectMemInstr&, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, llvm::MachineInstrBundleIterator<llvm::MachineInstr, true>&) const
Line
Count
Source
679
13.7k
                                      IterTy &Filler) const {
680
17.7k
  for (IterTy I = Begin; I != End;) {
681
16.6k
    IterTy CurrI = I;
682
16.6k
    ++I;
683
16.6k
684
16.6k
    // skip debug value
685
16.6k
    if (CurrI->isDebugInstr())
686
2
      continue;
687
16.6k
688
16.6k
    if (terminateSearch(*CurrI))
689
1.50k
      break;
690
15.0k
691
15.0k
    assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
692
15.0k
           "Cannot put calls, returns or branches in delay slot.");
693
15.0k
694
15.0k
    if (CurrI->isKill()) {
695
44
      CurrI->eraseFromParent();
696
44
      continue;
697
44
    }
698
15.0k
699
15.0k
    if (delayHasHazard(*CurrI, RegDU, IM))
700
3.81k
      continue;
701
11.2k
702
11.2k
    const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
703
11.2k
    if (STI.isTargetNaCl()) {
704
30
      // In NaCl, instructions that must be masked are forbidden in delay slots.
705
30
      // We only check for loads, stores and SP changes.  Calls, returns and
706
30
      // branches are not checked because non-NaCl targets never put them in
707
30
      // delay slots.
708
30
      unsigned AddrIdx;
709
30
      if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
710
30
           
baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())8
) ||
711
30
          
CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo())22
)
712
20
        continue;
713
11.2k
    }
714
11.2k
715
11.2k
    bool InMicroMipsMode = STI.inMicroMipsMode();
716
11.2k
    const MipsInstrInfo *TII = STI.getInstrInfo();
717
11.2k
    unsigned Opcode = (*Slot).getOpcode();
718
11.2k
    // This is complicated by the tail call optimization. For non-PIC code
719
11.2k
    // there is only a 32bit sized unconditional branch which can be assumed
720
11.2k
    // to be able to reach the target. b16 only has a range of +/- 1 KB.
721
11.2k
    // It's entirely possible that the target function is reachable with b16
722
11.2k
    // but we don't have enough information to make that decision.
723
11.2k
     if (InMicroMipsMode && 
TII->getInstSizeInBytes(*CurrI) == 2387
&&
724
11.2k
        
(135
Opcode == Mips::JR135
||
Opcode == Mips::PseudoIndirectBranch135
||
725
135
         Opcode == Mips::PseudoIndirectBranch_MM ||
726
135
         
Opcode == Mips::PseudoReturn134
||
Opcode == Mips::TAILCALL13
))
727
122
      continue;
728
11.1k
     // Instructions LWP/SWP and MOVEP should not be in a delay slot as that
729
11.1k
     // results in unpredictable behaviour
730
11.1k
     if (InMicroMipsMode && 
(265
Opcode == Mips::LWP_MM265
||
Opcode == Mips::SWP_MM265
||
731
265
                             Opcode == Mips::MOVEP_MM))
732
0
       continue;
733
11.1k
734
11.1k
    Filler = CurrI;
735
11.1k
    return true;
736
11.1k
  }
737
13.7k
738
13.7k
  
return false2.68k
;
739
13.7k
}
MipsDelaySlotFiller.cpp:bool (anonymous namespace)::MipsDelaySlotFiller::searchRange<llvm::MachineInstrBundleIterator<llvm::MachineInstr, false> >(llvm::MachineBasicBlock&, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, (anonymous namespace)::RegDefsUses&, (anonymous namespace)::InspectMemInstr&, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>&) const
Line
Count
Source
679
16
                                      IterTy &Filler) const {
680
31
  for (IterTy I = Begin; I != End;) {
681
29
    IterTy CurrI = I;
682
29
    ++I;
683
29
684
29
    // skip debug value
685
29
    if (CurrI->isDebugInstr())
686
0
      continue;
687
29
688
29
    if (terminateSearch(*CurrI))
689
5
      break;
690
24
691
24
    assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
692
24
           "Cannot put calls, returns or branches in delay slot.");
693
24
694
24
    if (CurrI->isKill()) {
695
0
      CurrI->eraseFromParent();
696
0
      continue;
697
0
    }
698
24
699
24
    if (delayHasHazard(*CurrI, RegDU, IM))
700
15
      continue;
701
9
702
9
    const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
703
9
    if (STI.isTargetNaCl()) {
704
0
      // In NaCl, instructions that must be masked are forbidden in delay slots.
705
0
      // We only check for loads, stores and SP changes.  Calls, returns and
706
0
      // branches are not checked because non-NaCl targets never put them in
707
0
      // delay slots.
708
0
      unsigned AddrIdx;
709
0
      if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
710
0
           baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) ||
711
0
          CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo()))
712
0
        continue;
713
9
    }
714
9
715
9
    bool InMicroMipsMode = STI.inMicroMipsMode();
716
9
    const MipsInstrInfo *TII = STI.getInstrInfo();
717
9
    unsigned Opcode = (*Slot).getOpcode();
718
9
    // This is complicated by the tail call optimization. For non-PIC code
719
9
    // there is only a 32bit sized unconditional branch which can be assumed
720
9
    // to be able to reach the target. b16 only has a range of +/- 1 KB.
721
9
    // It's entirely possible that the target function is reachable with b16
722
9
    // but we don't have enough information to make that decision.
723
9
     if (InMicroMipsMode && 
TII->getInstSizeInBytes(*CurrI) == 20
&&
724
9
        
(0
Opcode == Mips::JR0
||
Opcode == Mips::PseudoIndirectBranch0
||
725
0
         Opcode == Mips::PseudoIndirectBranch_MM ||
726
0
         Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
727
0
      continue;
728
9
     // Instructions LWP/SWP and MOVEP should not be in a delay slot as that
729
9
     // results in unpredictable behaviour
730
9
     if (InMicroMipsMode && 
(0
Opcode == Mips::LWP_MM0
||
Opcode == Mips::SWP_MM0
||
731
0
                             Opcode == Mips::MOVEP_MM))
732
0
       continue;
733
9
734
9
    Filler = CurrI;
735
9
    return true;
736
9
  }
737
16
738
16
  
return false7
;
739
16
}
740
741
bool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB,
742
13.8k
                                         MachineInstr &Slot) const {
743
13.8k
  if (DisableBackwardSearch)
744
23
    return false;
745
13.7k
746
13.7k
  auto *Fn = MBB.getParent();
747
13.7k
  RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
748
13.7k
  MemDefsUses MemDU(Fn->getDataLayout(), &Fn->getFrameInfo());
749
13.7k
  ReverseIter Filler;
750
13.7k
751
13.7k
  RegDU.init(Slot);
752
13.7k
753
13.7k
  MachineBasicBlock::iterator SlotI = Slot;
754
13.7k
  if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot,
755
13.7k
                   Filler))
756
2.68k
    return false;
757
11.1k
758
11.1k
  MBB.splice(std::next(SlotI), &MBB, Filler.getReverse());
759
11.1k
  MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2));
760
11.1k
  ++UsefulSlots;
761
11.1k
  return true;
762
11.1k
}
763
764
bool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB,
765
638
                                        Iter Slot) const {
766
638
  // Can handle only calls.
767
638
  if (DisableForwardSearch || 
!Slot->isCall()6
)
768
632
    return false;
769
6
770
6
  RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
771
6
  NoMemInstr NM;
772
6
  Iter Filler;
773
6
774
6
  RegDU.setCallerSaved(*Slot);
775
6
776
6
  if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler))
777
5
    return false;
778
1
779
1
  MBB.splice(std::next(Slot), &MBB, Filler);
780
1
  MIBundleBuilder(MBB, Slot, std::next(Slot, 2));
781
1
  ++UsefulSlots;
782
1
  return true;
783
1
}
784
785
bool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB,
786
2.06k
                                        Iter Slot) const {
787
2.06k
  if (DisableSuccBBSearch)
788
2.04k
    return false;
789
20
790
20
  MachineBasicBlock *SuccBB = selectSuccBB(MBB);
791
20
792
20
  if (!SuccBB)
793
10
    return false;
794
10
795
10
  RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
796
10
  bool HasMultipleSuccs = false;
797
10
  BB2BrMap BrMap;
798
10
  std::unique_ptr<InspectMemInstr> IM;
799
10
  Iter Filler;
800
10
  auto *Fn = MBB.getParent();
801
10
802
10
  // Iterate over SuccBB's predecessor list.
803
10
  for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(),
804
22
       PE = SuccBB->pred_end(); PI != PE; 
++PI12
)
805
12
    if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap))
806
0
      return false;
807
10
808
10
  // Do not allow moving instructions which have unallocatable register operands
809
10
  // across basic block boundaries.
810
10
  RegDU.setUnallocatableRegs(*Fn);
811
10
812
10
  // Only allow moving loads from stack or constants if any of the SuccBB's
813
10
  // predecessors have multiple successors.
814
10
  if (HasMultipleSuccs) {
815
10
    IM.reset(new LoadFromStackOrConst());
816
10
  } else {
817
0
    const MachineFrameInfo &MFI = Fn->getFrameInfo();
818
0
    IM.reset(new MemDefsUses(Fn->getDataLayout(), &MFI));
819
0
  }
820
10
821
10
  if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot,
822
10
                   Filler))
823
2
    return false;
824
8
825
8
  insertDelayFiller(Filler, BrMap);
826
8
  addLiveInRegs(Filler, *SuccBB);
827
8
  Filler->eraseFromParent();
828
8
829
8
  return true;
830
8
}
831
832
MachineBasicBlock *
833
20
MipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const {
834
20
  if (B.succ_empty())
835
10
    return nullptr;
836
10
837
10
  // Select the successor with the larget edge weight.
838
10
  auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
839
10
  MachineBasicBlock *S = *std::max_element(
840
10
      B.succ_begin(), B.succ_end(),
841
10
      [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) {
842
10
        return Prob.getEdgeProbability(&B, Dst0) <
843
10
               Prob.getEdgeProbability(&B, Dst1);
844
10
      });
845
10
  return S->isEHPad() ? 
nullptr0
: S;
846
10
}
847
848
std::pair<MipsInstrInfo::BranchType, MachineInstr *>
849
MipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB,
850
12
                               const MachineBasicBlock &Dst) const {
851
12
  const MipsInstrInfo *TII =
852
12
      MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();
853
12
  MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;
854
12
  SmallVector<MachineInstr*, 2> BranchInstrs;
855
12
  SmallVector<MachineOperand, 2> Cond;
856
12
857
12
  MipsInstrInfo::BranchType R =
858
12
      TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs);
859
12
860
12
  if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch))
861
1
    return std::make_pair(R, nullptr);
862
11
863
11
  if (R != MipsInstrInfo::BT_CondUncond) {
864
11
    if (!hasUnoccupiedSlot(BranchInstrs[0]))
865
0
      return std::make_pair(MipsInstrInfo::BT_None, nullptr);
866
11
867
11
    assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));
868
11
869
11
    return std::make_pair(R, BranchInstrs[0]);
870
11
  }
871
0
872
0
  assert((TrueBB == &Dst) || (FalseBB == &Dst));
873
0
874
0
  // Examine the conditional branch. See if its slot is occupied.
875
0
  if (hasUnoccupiedSlot(BranchInstrs[0]))
876
0
    return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]);
877
0
878
0
  // If that fails, try the unconditional branch.
879
0
  if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst))
880
0
    return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]);
881
0
882
0
  return std::make_pair(MipsInstrInfo::BT_None, nullptr);
883
0
}
884
885
bool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred,
886
                                      const MachineBasicBlock &Succ,
887
                                      RegDefsUses &RegDU,
888
                                      bool &HasMultipleSuccs,
889
12
                                      BB2BrMap &BrMap) const {
890
12
  std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =
891
12
      getBranch(Pred, Succ);
892
12
893
12
  // Return if either getBranch wasn't able to analyze the branches or there
894
12
  // were no branches with unoccupied slots.
895
12
  if (P.first == MipsInstrInfo::BT_None)
896
0
    return false;
897
12
898
12
  if ((P.first != MipsInstrInfo::BT_Uncond) &&
899
12
      (P.first != MipsInstrInfo::BT_NoBranch)) {
900
11
    HasMultipleSuccs = true;
901
11
    RegDU.addLiveOut(Pred, Succ);
902
11
  }
903
12
904
12
  BrMap[&Pred] = P.second;
905
12
  return true;
906
12
}
907
908
bool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate,
909
                                         RegDefsUses &RegDU,
910
15.0k
                                         InspectMemInstr &IM) const {
911
15.0k
  assert(!Candidate.isKill() &&
912
15.0k
         "KILL instructions should have been eliminated at this point.");
913
15.0k
914
15.0k
  bool HasHazard = Candidate.isImplicitDef();
915
15.0k
916
15.0k
  HasHazard |= IM.hasHazard(Candidate);
917
15.0k
  HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());
918
15.0k
919
15.0k
  return HasHazard;
920
15.0k
}
921
922
16.6k
bool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const {
923
16.6k
  return (Candidate.isTerminator() || 
Candidate.isCall()16.6k
||
924
16.6k
          
Candidate.isPosition()16.5k
||
Candidate.isInlineAsm()16.0k
||
925
16.6k
          
Candidate.hasUnmodeledSideEffects()15.9k
);
926
16.6k
}
927
928
/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
929
/// slots in Mips MachineFunctions
930
2.09k
FunctionPass *llvm::createMipsDelaySlotFillerPass() { return new MipsDelaySlotFiller(); }