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