LLVM  7.0.0svn
MipsDelaySlotFiller.cpp
Go to the documentation of this file.
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 
15 #include "Mips.h"
16 #include "MipsInstrInfo.h"
17 #include "MipsRegisterInfo.h"
18 #include "MipsSubtarget.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/PointerUnion.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
39 #include "llvm/MC/MCInstrDesc.h"
40 #include "llvm/MC/MCRegisterInfo.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/CodeGen.h"
46 #include <algorithm>
47 #include <cassert>
48 #include <iterator>
49 #include <memory>
50 #include <utility>
51 
52 using namespace llvm;
53 
54 #define DEBUG_TYPE "mips-delay-slot-filler"
55 
56 STATISTIC(FilledSlots, "Number of delay slots filled");
57 STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
58  " are not NOP.");
59 
61  "disable-mips-delay-filler",
62  cl::init(false),
63  cl::desc("Fill all delay slots with NOPs."),
64  cl::Hidden);
65 
67  "disable-mips-df-forward-search",
68  cl::init(true),
69  cl::desc("Disallow MIPS delay filler to search forward."),
70  cl::Hidden);
71 
73  "disable-mips-df-succbb-search",
74  cl::init(true),
75  cl::desc("Disallow MIPS delay filler to search successor basic blocks."),
76  cl::Hidden);
77 
79  "disable-mips-df-backward-search",
80  cl::init(false),
81  cl::desc("Disallow MIPS delay filler to search backward."),
82  cl::Hidden);
83 
85  CB_Never, ///< The policy 'never' may in some circumstances or for some
86  ///< ISAs not be absolutely adhered to.
87  CB_Optimal, ///< Optimal is the default and will produce compact branches
88  ///< when delay slots cannot be filled.
89  CB_Always ///< 'always' may in some circumstances may not be
90  ///< absolutely adhered to there may not be a corresponding
91  ///< compact form of a branch.
92 };
93 
95  "mips-compact-branches",cl::Optional,
97  cl::desc("MIPS Specific: Compact branch policy."),
98  cl::values(
99  clEnumValN(CB_Never, "never", "Do not use compact branches if possible."),
100  clEnumValN(CB_Optimal, "optimal", "Use compact branches where appropiate (default)."),
101  clEnumValN(CB_Always, "always", "Always use compact branches if possible.")
102  )
103 );
104 
105 namespace {
106 
107  using Iter = MachineBasicBlock::iterator;
108  using ReverseIter = MachineBasicBlock::reverse_iterator;
110 
111  class RegDefsUses {
112  public:
113  RegDefsUses(const TargetRegisterInfo &TRI);
114 
115  void init(const MachineInstr &MI);
116 
117  /// This function sets all caller-saved registers in Defs.
118  void setCallerSaved(const MachineInstr &MI);
119 
120  /// This function sets all unallocatable registers in Defs.
121  void setUnallocatableRegs(const MachineFunction &MF);
122 
123  /// Set bits in Uses corresponding to MBB's live-out registers except for
124  /// the registers that are live-in to SuccBB.
125  void addLiveOut(const MachineBasicBlock &MBB,
126  const MachineBasicBlock &SuccBB);
127 
128  bool update(const MachineInstr &MI, unsigned Begin, unsigned End);
129 
130  private:
131  bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg,
132  bool IsDef) const;
133 
134  /// Returns true if Reg or its alias is in RegSet.
135  bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
136 
137  const TargetRegisterInfo &TRI;
138  BitVector Defs, Uses;
139  };
140 
141  /// Base class for inspecting loads and stores.
142  class InspectMemInstr {
143  public:
144  InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {}
145  virtual ~InspectMemInstr() = default;
146 
147  /// Return true if MI cannot be moved to delay slot.
148  bool hasHazard(const MachineInstr &MI);
149 
150  protected:
151  /// Flags indicating whether loads or stores have been seen.
152  bool OrigSeenLoad = false;
153  bool OrigSeenStore = false;
154  bool SeenLoad = false;
155  bool SeenStore = false;
156 
157  /// Memory instructions are not allowed to move to delay slot if this flag
158  /// is true.
159  bool ForbidMemInstr;
160 
161  private:
162  virtual bool hasHazard_(const MachineInstr &MI) = 0;
163  };
164 
165  /// This subclass rejects any memory instructions.
166  class NoMemInstr : public InspectMemInstr {
167  public:
168  NoMemInstr() : InspectMemInstr(true) {}
169 
170  private:
171  bool hasHazard_(const MachineInstr &MI) override { return true; }
172  };
173 
174  /// This subclass accepts loads from stacks and constant loads.
175  class LoadFromStackOrConst : public InspectMemInstr {
176  public:
177  LoadFromStackOrConst() : InspectMemInstr(false) {}
178 
179  private:
180  bool hasHazard_(const MachineInstr &MI) override;
181  };
182 
183  /// This subclass uses memory dependence information to determine whether a
184  /// memory instruction can be moved to a delay slot.
185  class MemDefsUses : public InspectMemInstr {
186  public:
187  MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI);
188 
189  private:
191 
192  bool hasHazard_(const MachineInstr &MI) override;
193 
194  /// Update Defs and Uses. Return true if there exist dependences that
195  /// disqualify the delay slot candidate between V and values in Uses and
196  /// Defs.
197  bool updateDefsUses(ValueType V, bool MayStore);
198 
199  /// Get the list of underlying objects of MI's memory operand.
201  SmallVectorImpl<ValueType> &Objects) const;
202 
203  const MachineFrameInfo *MFI;
204  SmallPtrSet<ValueType, 4> Uses, Defs;
205  const DataLayout &DL;
206 
207  /// Flags indicating whether loads or stores with no underlying objects have
208  /// been seen.
209  bool SeenNoObjLoad = false;
210  bool SeenNoObjStore = false;
211  };
212 
213  class MipsDelaySlotFiller : public MachineFunctionPass {
214  public:
215  MipsDelaySlotFiller() : MachineFunctionPass(ID) {
217  }
218 
219  StringRef getPassName() const override { return "Mips Delay Slot Filler"; }
220 
221  bool runOnMachineFunction(MachineFunction &F) override {
222  TM = &F.getTarget();
223  bool Changed = false;
224  for (MachineFunction::iterator FI = F.begin(), FE = F.end();
225  FI != FE; ++FI)
226  Changed |= runOnMachineBasicBlock(*FI);
227 
228  // This pass invalidates liveness information when it reorders
229  // instructions to fill delay slot. Without this, -verify-machineinstrs
230  // will fail.
231  if (Changed)
233 
234  return Changed;
235  }
236 
237  MachineFunctionProperties getRequiredProperties() const override {
240  }
241 
242  void getAnalysisUsage(AnalysisUsage &AU) const override {
245  }
246 
247  static char ID;
248 
249  private:
250  bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
251 
252  Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch,
253  const DebugLoc &DL);
254 
255  /// This function checks if it is valid to move Candidate to the delay slot
256  /// and returns true if it isn't. It also updates memory and register
257  /// dependence information.
258  bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
259  InspectMemInstr &IM) const;
260 
261  /// This function searches range [Begin, End) for an instruction that can be
262  /// moved to the delay slot. Returns true on success.
263  template<typename IterTy>
264  bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
265  RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot,
266  IterTy &Filler) const;
267 
268  /// This function searches in the backward direction for an instruction that
269  /// can be moved to the delay slot. Returns true on success.
270  bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const;
271 
272  /// This function searches MBB in the forward direction for an instruction
273  /// that can be moved to the delay slot. Returns true on success.
274  bool searchForward(MachineBasicBlock &MBB, Iter Slot) const;
275 
276  /// This function searches one of MBB's successor blocks for an instruction
277  /// that can be moved to the delay slot and inserts clones of the
278  /// instruction into the successor's predecessor blocks.
279  bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const;
280 
281  /// Pick a successor block of MBB. Return NULL if MBB doesn't have a
282  /// successor block that is not a landing pad.
283  MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const;
284 
285  /// This function analyzes MBB and returns an instruction with an unoccupied
286  /// slot that branches to Dst.
287  std::pair<MipsInstrInfo::BranchType, MachineInstr *>
288  getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const;
289 
290  /// Examine Pred and see if it is possible to insert an instruction into
291  /// one of its branches delay slot or its end.
292  bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
293  RegDefsUses &RegDU, bool &HasMultipleSuccs,
294  BB2BrMap &BrMap) const;
295 
296  bool terminateSearch(const MachineInstr &Candidate) const;
297 
298  const TargetMachine *TM = nullptr;
299  };
300 
301 } // end anonymous namespace
302 
303 char MipsDelaySlotFiller::ID = 0;
304 
305 static bool hasUnoccupiedSlot(const MachineInstr *MI) {
306  return MI->hasDelaySlot() && !MI->isBundledWithSucc();
307 }
308 
309 INITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE,
310  "Fill delay slot for MIPS", false, false)
311 
312 /// This function inserts clones of Filler into predecessor blocks.
313 static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {
314  MachineFunction *MF = Filler->getParent()->getParent();
315 
316  for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) {
317  if (I->second) {
318  MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler));
319  ++UsefulSlots;
320  } else {
321  I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler));
322  }
323  }
324 }
325 
326 /// This function adds registers Filler defines to MBB's live-in register list.
327 static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {
328  for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) {
329  const MachineOperand &MO = Filler->getOperand(I);
330  unsigned R;
331 
332  if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg()))
333  continue;
334 
335 #ifndef NDEBUG
336  const MachineFunction &MF = *MBB.getParent();
338  "Shouldn't move an instruction with unallocatable registers across "
339  "basic block boundaries.");
340 #endif
341 
342  if (!MBB.isLiveIn(R))
343  MBB.addLiveIn(R);
344  }
345 }
346 
347 RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)
348  : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {}
349 
350 void RegDefsUses::init(const MachineInstr &MI) {
351  // Add all register operands which are explicit and non-variadic.
352  update(MI, 0, MI.getDesc().getNumOperands());
353 
354  // If MI is a call, add RA to Defs to prevent users of RA from going into
355  // delay slot.
356  if (MI.isCall())
357  Defs.set(Mips::RA);
358 
359  // Add all implicit register operands of branch instructions except
360  // register AT.
361  if (MI.isBranch()) {
362  update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands());
363  Defs.reset(Mips::AT);
364  }
365 }
366 
367 void RegDefsUses::setCallerSaved(const MachineInstr &MI) {
368  assert(MI.isCall());
369 
370  // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into
371  // the delay slot. The reason is that RA/RA_64 must not be changed
372  // in the delay slot so that the callee can return to the caller.
373  if (MI.definesRegister(Mips::RA) || MI.definesRegister(Mips::RA_64)) {
374  Defs.set(Mips::RA);
375  Defs.set(Mips::RA_64);
376  }
377 
378  // If MI is a call, add all caller-saved registers to Defs.
379  BitVector CallerSavedRegs(TRI.getNumRegs(), true);
380 
381  CallerSavedRegs.reset(Mips::ZERO);
382  CallerSavedRegs.reset(Mips::ZERO_64);
383 
384  for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent());
385  *R; ++R)
386  for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI)
387  CallerSavedRegs.reset(*AI);
388 
389  Defs |= CallerSavedRegs;
390 }
391 
392 void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {
393  BitVector AllocSet = TRI.getAllocatableSet(MF);
394 
395  for (unsigned R : AllocSet.set_bits())
396  for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI)
397  AllocSet.set(*AI);
398 
399  AllocSet.set(Mips::ZERO);
400  AllocSet.set(Mips::ZERO_64);
401 
402  Defs |= AllocSet.flip();
403 }
404 
405 void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
406  const MachineBasicBlock &SuccBB) {
408  SE = MBB.succ_end(); SI != SE; ++SI)
409  if (*SI != &SuccBB)
410  for (const auto &LI : (*SI)->liveins())
411  Uses.set(LI.PhysReg);
412 }
413 
414 bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {
415  BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());
416  bool HasHazard = false;
417 
418  for (unsigned I = Begin; I != End; ++I) {
419  const MachineOperand &MO = MI.getOperand(I);
420 
421  if (MO.isReg() && MO.getReg())
422  HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef());
423  }
424 
425  Defs |= NewDefs;
426  Uses |= NewUses;
427 
428  return HasHazard;
429 }
430 
431 bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
432  unsigned Reg, bool IsDef) const {
433  if (IsDef) {
434  NewDefs.set(Reg);
435  // check whether Reg has already been defined or used.
436  return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg));
437  }
438 
439  NewUses.set(Reg);
440  // check whether Reg has already been defined.
441  return isRegInSet(Defs, Reg);
442 }
443 
444 bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
445  // Check Reg and all aliased Registers.
446  for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
447  if (RegSet.test(*AI))
448  return true;
449  return false;
450 }
451 
452 bool InspectMemInstr::hasHazard(const MachineInstr &MI) {
453  if (!MI.mayStore() && !MI.mayLoad())
454  return false;
455 
456  if (ForbidMemInstr)
457  return true;
458 
459  OrigSeenLoad = SeenLoad;
460  OrigSeenStore = SeenStore;
461  SeenLoad |= MI.mayLoad();
462  SeenStore |= MI.mayStore();
463 
464  // If MI is an ordered or volatile memory reference, disallow moving
465  // subsequent loads and stores to delay slot.
466  if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
467  ForbidMemInstr = true;
468  return true;
469  }
470 
471  return hasHazard_(MI);
472 }
473 
474 bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) {
475  if (MI.mayStore())
476  return true;
477 
478  if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue())
479  return true;
480 
481  if (const PseudoSourceValue *PSV =
482  (*MI.memoperands_begin())->getPseudoValue()) {
483  if (isa<FixedStackPseudoSourceValue>(PSV))
484  return false;
485  return !PSV->isConstant(nullptr) && !PSV->isStack();
486  }
487 
488  return true;
489 }
490 
491 MemDefsUses::MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI_)
492  : InspectMemInstr(false), MFI(MFI_), DL(DL) {}
493 
494 bool MemDefsUses::hasHazard_(const MachineInstr &MI) {
495  bool HasHazard = false;
497 
498  // Check underlying object list.
499  if (getUnderlyingObjects(MI, Objs)) {
501  I != Objs.end(); ++I)
502  HasHazard |= updateDefsUses(*I, MI.mayStore());
503 
504  return HasHazard;
505  }
506 
507  // No underlying objects found.
508  HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
509  HasHazard |= MI.mayLoad() || OrigSeenStore;
510 
511  SeenNoObjLoad |= MI.mayLoad();
512  SeenNoObjStore |= MI.mayStore();
513 
514  return HasHazard;
515 }
516 
517 bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {
518  if (MayStore)
519  return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore ||
520  SeenNoObjLoad;
521 
522  Uses.insert(V);
523  return Defs.count(V) || SeenNoObjStore;
524 }
525 
526 bool MemDefsUses::
528  SmallVectorImpl<ValueType> &Objects) const {
529  if (!MI.hasOneMemOperand() ||
530  (!(*MI.memoperands_begin())->getValue() &&
531  !(*MI.memoperands_begin())->getPseudoValue()))
532  return false;
533 
534  if (const PseudoSourceValue *PSV =
535  (*MI.memoperands_begin())->getPseudoValue()) {
536  if (!PSV->isAliased(MFI))
537  return false;
538  Objects.push_back(PSV);
539  return true;
540  }
541 
542  const Value *V = (*MI.memoperands_begin())->getValue();
543 
545  GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL);
546 
547  for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), E = Objs.end();
548  I != E; ++I) {
549  if (!isIdentifiedObject(V))
550  return false;
551 
552  Objects.push_back(*I);
553  }
554 
555  return true;
556 }
557 
558 // Replace Branch with the compact branch instruction.
559 Iter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB,
560  Iter Branch,
561  const DebugLoc &DL) {
562  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
563  const MipsInstrInfo *TII = STI.getInstrInfo();
564 
565  unsigned NewOpcode = TII->getEquivalentCompactForm(Branch);
566  Branch = TII->genInstrWithNewOpc(NewOpcode, Branch);
567 
568  std::next(Branch)->eraseFromParent();
569  return Branch;
570 }
571 
572 // For given opcode returns opcode of corresponding instruction with short
573 // delay slot.
574 // For the pseudo TAILCALL*_MM instructions return the short delay slot
575 // form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range
576 // that is too short to make use of for tail calls.
577 static int getEquivalentCallShort(int Opcode) {
578  switch (Opcode) {
579  case Mips::BGEZAL:
580  return Mips::BGEZALS_MM;
581  case Mips::BLTZAL:
582  return Mips::BLTZALS_MM;
583  case Mips::JAL:
584  case Mips::JAL_MM:
585  return Mips::JALS_MM;
586  case Mips::JALR:
587  return Mips::JALRS_MM;
588  case Mips::JALR16_MM:
589  return Mips::JALRS16_MM;
590  case Mips::TAILCALL_MM:
591  llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!");
592  case Mips::TAILCALLREG:
593  return Mips::JR16_MM;
594  default:
595  llvm_unreachable("Unexpected call instruction for microMIPS.");
596  }
597 }
598 
599 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
600 /// We assume there is only one delay slot per delayed instruction.
601 bool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
602  bool Changed = false;
603  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
604  bool InMicroMipsMode = STI.inMicroMipsMode();
605  const MipsInstrInfo *TII = STI.getInstrInfo();
606 
607  for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
608  if (!hasUnoccupiedSlot(&*I))
609  continue;
610 
611  // Delay slot filling is disabled at -O0, or in microMIPS32R6.
612  if (!DisableDelaySlotFiller && (TM->getOptLevel() != CodeGenOpt::None) &&
613  !(InMicroMipsMode && STI.hasMips32r6())) {
614 
615  bool Filled = false;
616 
617  if (MipsCompactBranchPolicy.getValue() != CB_Always ||
618  !TII->getEquivalentCompactForm(I)) {
619  if (searchBackward(MBB, *I)) {
620  Filled = true;
621  } else if (I->isTerminator()) {
622  if (searchSuccBBs(MBB, I)) {
623  Filled = true;
624  }
625  } else if (searchForward(MBB, I)) {
626  Filled = true;
627  }
628  }
629 
630  if (Filled) {
631  // Get instruction with delay slot.
632  MachineBasicBlock::instr_iterator DSI = I.getInstrIterator();
633 
634  if (InMicroMipsMode && TII->getInstSizeInBytes(*std::next(DSI)) == 2 &&
635  DSI->isCall()) {
636  // If instruction in delay slot is 16b change opcode to
637  // corresponding instruction with short delay slot.
638 
639  // TODO: Implement an instruction mapping table of 16bit opcodes to
640  // 32bit opcodes so that an instruction can be expanded. This would
641  // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop.
642  // TODO: Permit b16 when branching backwards to the same function
643  // if it is in range.
644  DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode())));
645  }
646  ++FilledSlots;
647  Changed = true;
648  continue;
649  }
650  }
651 
652  // For microMIPS if instruction is BEQ or BNE with one ZERO register, then
653  // instead of adding NOP replace this instruction with the corresponding
654  // compact branch instruction, i.e. BEQZC or BNEZC. Additionally
655  // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can
656  // be replaced with JRC16_MM.
657 
658  // For MIPSR6 attempt to produce the corresponding compact (no delay slot)
659  // form of the CTI. For indirect jumps this will not require inserting a
660  // NOP and for branches will hopefully avoid requiring a NOP.
661  if ((InMicroMipsMode ||
663  TII->getEquivalentCompactForm(I)) {
664  I = replaceWithCompactBranch(MBB, I, I->getDebugLoc());
665  Changed = true;
666  continue;
667  }
668 
669  // Bundle the NOP to the instruction with the delay slot.
670  BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
671  MIBundleBuilder(MBB, I, std::next(I, 2));
672  ++FilledSlots;
673  Changed = true;
674  }
675 
676  return Changed;
677 }
678 
679 template <typename IterTy>
680 bool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin,
681  IterTy End, RegDefsUses &RegDU,
682  InspectMemInstr &IM, Iter Slot,
683  IterTy &Filler) const {
684  for (IterTy I = Begin; I != End;) {
685  IterTy CurrI = I;
686  ++I;
687 
688  // skip debug value
689  if (CurrI->isDebugInstr())
690  continue;
691 
692  if (terminateSearch(*CurrI))
693  break;
694 
695  assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
696  "Cannot put calls, returns or branches in delay slot.");
697 
698  if (CurrI->isKill()) {
699  CurrI->eraseFromParent();
700  continue;
701  }
702 
703  if (delayHasHazard(*CurrI, RegDU, IM))
704  continue;
705 
706  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
707  if (STI.isTargetNaCl()) {
708  // In NaCl, instructions that must be masked are forbidden in delay slots.
709  // We only check for loads, stores and SP changes. Calls, returns and
710  // branches are not checked because non-NaCl targets never put them in
711  // delay slots.
712  unsigned AddrIdx;
713  if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
714  baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) ||
715  CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo()))
716  continue;
717  }
718 
719  bool InMicroMipsMode = STI.inMicroMipsMode();
720  const MipsInstrInfo *TII = STI.getInstrInfo();
721  unsigned Opcode = (*Slot).getOpcode();
722  // This is complicated by the tail call optimization. For non-PIC code
723  // there is only a 32bit sized unconditional branch which can be assumed
724  // to be able to reach the target. b16 only has a range of +/- 1 KB.
725  // It's entirely possible that the target function is reachable with b16
726  // but we don't have enough information to make that decision.
727  if (InMicroMipsMode && TII->getInstSizeInBytes(*CurrI) == 2 &&
728  (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
729  Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
730  continue;
731  // Instructions LWP/SWP should not be in a delay slot as that
732  // results in unpredictable behaviour
733  if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM))
734  continue;
735 
736  Filler = CurrI;
737  return true;
738  }
739 
740  return false;
741 }
742 
743 bool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB,
744  MachineInstr &Slot) const {
746  return false;
747 
748  auto *Fn = MBB.getParent();
749  RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
750  MemDefsUses MemDU(Fn->getDataLayout(), &Fn->getFrameInfo());
751  ReverseIter Filler;
752 
753  RegDU.init(Slot);
754 
755  MachineBasicBlock::iterator SlotI = Slot;
756  if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot,
757  Filler))
758  return false;
759 
760  MBB.splice(std::next(SlotI), &MBB, Filler.getReverse());
761  MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2));
762  ++UsefulSlots;
763  return true;
764 }
765 
766 bool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB,
767  Iter Slot) const {
768  // Can handle only calls.
769  if (DisableForwardSearch || !Slot->isCall())
770  return false;
771 
772  RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
773  NoMemInstr NM;
774  Iter Filler;
775 
776  RegDU.setCallerSaved(*Slot);
777 
778  if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler))
779  return false;
780 
781  MBB.splice(std::next(Slot), &MBB, Filler);
782  MIBundleBuilder(MBB, Slot, std::next(Slot, 2));
783  ++UsefulSlots;
784  return true;
785 }
786 
787 bool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB,
788  Iter Slot) const {
790  return false;
791 
792  MachineBasicBlock *SuccBB = selectSuccBB(MBB);
793 
794  if (!SuccBB)
795  return false;
796 
797  RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
798  bool HasMultipleSuccs = false;
799  BB2BrMap BrMap;
800  std::unique_ptr<InspectMemInstr> IM;
801  Iter Filler;
802  auto *Fn = MBB.getParent();
803 
804  // Iterate over SuccBB's predecessor list.
805  for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(),
806  PE = SuccBB->pred_end(); PI != PE; ++PI)
807  if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap))
808  return false;
809 
810  // Do not allow moving instructions which have unallocatable register operands
811  // across basic block boundaries.
812  RegDU.setUnallocatableRegs(*Fn);
813 
814  // Only allow moving loads from stack or constants if any of the SuccBB's
815  // predecessors have multiple successors.
816  if (HasMultipleSuccs) {
817  IM.reset(new LoadFromStackOrConst());
818  } else {
819  const MachineFrameInfo &MFI = Fn->getFrameInfo();
820  IM.reset(new MemDefsUses(Fn->getDataLayout(), &MFI));
821  }
822 
823  if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot,
824  Filler))
825  return false;
826 
827  insertDelayFiller(Filler, BrMap);
828  addLiveInRegs(Filler, *SuccBB);
829  Filler->eraseFromParent();
830 
831  return true;
832 }
833 
835 MipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const {
836  if (B.succ_empty())
837  return nullptr;
838 
839  // Select the successor with the larget edge weight.
840  auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
841  MachineBasicBlock *S = *std::max_element(
842  B.succ_begin(), B.succ_end(),
843  [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) {
844  return Prob.getEdgeProbability(&B, Dst0) <
845  Prob.getEdgeProbability(&B, Dst1);
846  });
847  return S->isEHPad() ? nullptr : S;
848 }
849 
850 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
851 MipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB,
852  const MachineBasicBlock &Dst) const {
853  const MipsInstrInfo *TII =
854  MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();
855  MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;
856  SmallVector<MachineInstr*, 2> BranchInstrs;
858 
860  TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs);
861 
863  return std::make_pair(R, nullptr);
864 
865  if (R != MipsInstrInfo::BT_CondUncond) {
866  if (!hasUnoccupiedSlot(BranchInstrs[0]))
867  return std::make_pair(MipsInstrInfo::BT_None, nullptr);
868 
869  assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));
870 
871  return std::make_pair(R, BranchInstrs[0]);
872  }
873 
874  assert((TrueBB == &Dst) || (FalseBB == &Dst));
875 
876  // Examine the conditional branch. See if its slot is occupied.
877  if (hasUnoccupiedSlot(BranchInstrs[0]))
878  return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]);
879 
880  // If that fails, try the unconditional branch.
881  if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst))
882  return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]);
883 
884  return std::make_pair(MipsInstrInfo::BT_None, nullptr);
885 }
886 
887 bool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred,
888  const MachineBasicBlock &Succ,
889  RegDefsUses &RegDU,
890  bool &HasMultipleSuccs,
891  BB2BrMap &BrMap) const {
892  std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =
893  getBranch(Pred, Succ);
894 
895  // Return if either getBranch wasn't able to analyze the branches or there
896  // were no branches with unoccupied slots.
897  if (P.first == MipsInstrInfo::BT_None)
898  return false;
899 
900  if ((P.first != MipsInstrInfo::BT_Uncond) &&
901  (P.first != MipsInstrInfo::BT_NoBranch)) {
902  HasMultipleSuccs = true;
903  RegDU.addLiveOut(Pred, Succ);
904  }
905 
906  BrMap[&Pred] = P.second;
907  return true;
908 }
909 
910 bool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate,
911  RegDefsUses &RegDU,
912  InspectMemInstr &IM) const {
913  assert(!Candidate.isKill() &&
914  "KILL instructions should have been eliminated at this point.");
915 
916  bool HasHazard = Candidate.isImplicitDef();
917 
918  HasHazard |= IM.hasHazard(Candidate);
919  HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());
920 
921  return HasHazard;
922 }
923 
924 bool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const {
925  return (Candidate.isTerminator() || Candidate.isCall() ||
926  Candidate.isPosition() || Candidate.isInlineAsm() ||
927  Candidate.hasUnmodeledSideEffects());
928 }
929 
930 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
931 /// slots in Mips MachineFunctions
932 FunctionPass *llvm::createMipsDelaySlotFillerPass() { return new MipsDelaySlotFiller(); }
BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC=nullptr) const
Returns a bitset indexed by register number indicating if a register is allocatable or not...
unsigned getInstSizeInBytes(const MachineInstr &MI) const override
Return the number of bytes of code the specified instruction may be.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
BitVector & set()
Definition: BitVector.h:398
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:485
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:328
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Branch Analysis.
static cl::opt< CompactBranchPolicy > MipsCompactBranchPolicy("mips-compact-branches", cl::Optional, cl::init(CB_Optimal), cl::desc("MIPS Specific: Compact branch policy."), cl::values(clEnumValN(CB_Never, "never", "Do not use compact branches if possible."), clEnumValN(CB_Optimal, "optimal", "Use compact branches where appropiate (default)."), clEnumValN(CB_Always, "always", "Always use compact branches if possible.")))
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool isBasePlusOffsetMemoryAccess(unsigned Opcode, unsigned *AddrIdx, bool *IsStore=nullptr)
unsigned getReg() const
getReg - Returns the register number.
static void getUnderlyingObjects(MachineInstr *MI, SmallVectorImpl< Value *> &Objs, const DataLayout &DL)
Return the underlying objects for the memory references of an instruction.
unsigned Reg
bool hasDelaySlot(QueryType Type=AnyInBundle) const
Returns true if the specified instruction has a delay slot which must be filled by the code generator...
Definition: MachineInstr.h:593
bool isInlineAsm() const
Definition: MachineInstr.h:867
const MipsInstrInfo * getInstrInfo() const override
bool test(unsigned Idx) const
Definition: BitVector.h:502
Optimal is the default and will produce compact branches when delay slots cannot be filled...
FunctionPass * createMipsDelaySlotFillerPass()
createMipsDelaySlotFillerPass - Returns a pass that fills in delay slots in Mips MachineFunctions ...
static bool hasUnoccupiedSlot(const MachineInstr *MI)
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:34
F(f)
static cl::opt< bool > DisableDelaySlotFiller("disable-mips-delay-filler", cl::init(false), cl::desc("Fill all delay slots with NOPs."), cl::Hidden)
SI optimize exec mask operations pre RA
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:208
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:314
bool inMicroMipsMode() const
bool isBundledWithSucc() const
Return true if this instruction is part of a bundle, and it is not the last instruction in the bundle...
Definition: MachineInstr.h:268
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:501
bool hasMips32r6() const
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
bool baseRegNeedsLoadStoreMask(unsigned Reg)
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB)
This function adds registers Filler defines to MBB&#39;s live-in register list.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:308
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
static cl::opt< bool > DisableBackwardSearch("disable-mips-df-backward-search", cl::init(false), cl::desc("Disallow MIPS delay filler to search backward."), cl::Hidden)
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
static cl::opt< bool > DisableForwardSearch("disable-mips-df-forward-search", cl::init(true), cl::desc("Disallow MIPS delay filler to search forward."), cl::Hidden)
virtual const MCPhysReg * getCalleeSavedRegs(const MachineFunction *MF) const =0
Return a null-terminated list of all of the callee-saved registers on this target.
reverse_iterator rend()
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:509
bool isTargetNaCl() const
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:672
#define P(N)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
INITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE, "Fill delay slot for MIPS", false, false) static void insertDelayFiller(Iter Filler
This function inserts clones of Filler into predecessor blocks.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
MachineInstrBundleIterator< MachineInstr > iterator
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:630
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:117
&#39;always&#39; may in some circumstances may not be absolutely adhered to there may not be a corresponding ...
unsigned getEquivalentCompactForm(const MachineBasicBlock::iterator I) const
Determine the opcode of a non-delay slot form for a branch if one exists.
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
bool hasOneMemOperand() const
Return true if this instruction has exactly one MachineMemOperand.
Definition: MachineInstr.h:431
BitVector & reset()
Definition: BitVector.h:439
CompactBranchPolicy
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
bool definesRegister(unsigned Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr fully defines the specified register.
Definition: MachineInstr.h:995
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
std::vector< MachineBasicBlock * >::iterator pred_iterator
static cl::opt< bool > DisableSuccBBSearch("disable-mips-df-succbb-search", cl::init(true), cl::desc("Disallow MIPS delay filler to search successor basic blocks."), cl::Hidden)
bool isImplicitDef() const
Definition: MachineInstr.h:866
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:416
const MipsRegisterInfo * getRegisterInfo() const override
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
bool hasOrderedMemoryRef() const
Return true if this instruction may have an ordered or volatile memory reference, or if the informati...
BitVector & flip()
Definition: BitVector.h:478
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
#define DEBUG_TYPE
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Special value supplied for machine level alias analysis.
static int getEquivalentCallShort(int Opcode)
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:605
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:156
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:60
Basic Alias true
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:121
const BB2BrMap & BrMap
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
#define I(x, y, z)
Definition: MD5.cpp:58
bool isKill() const
Definition: MachineInstr.h:865
The policy &#39;never&#39; may in some circumstances or for some ISAs not be absolutely adhered to...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void GetUnderlyingObjects(Value *V, SmallVectorImpl< Value *> &Objects, const DataLayout &DL, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to GetUnderlyingObject except that it can look through phi and select instruct...
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:659
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:130
LLVM Value Representation.
Definition: Value.h:73
bool isPosition() const
Definition: MachineInstr.h:847
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:59
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
void initializeMipsDelaySlotFillerPass(PassRegistry &)
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:316
Properties which a MachineFunction may have at a given point in time.
Helper class for constructing bundles of MachineInstrs.
A discriminated union of two pointer types, with the discriminator in the low bit of the pointer...
Definition: PointerUnion.h:87