LLVM  6.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 "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 Filler : public MachineFunctionPass {
214  public:
215  Filler() : MachineFunctionPass(ID) {}
216 
217  StringRef getPassName() const override { return "Mips Delay Slot Filler"; }
218 
219  bool runOnMachineFunction(MachineFunction &F) override {
220  TM = &F.getTarget();
221  bool Changed = false;
222  for (MachineFunction::iterator FI = F.begin(), FE = F.end();
223  FI != FE; ++FI)
224  Changed |= runOnMachineBasicBlock(*FI);
225 
226  // This pass invalidates liveness information when it reorders
227  // instructions to fill delay slot. Without this, -verify-machineinstrs
228  // will fail.
229  if (Changed)
231 
232  return Changed;
233  }
234 
235  MachineFunctionProperties getRequiredProperties() const override {
238  }
239 
240  void getAnalysisUsage(AnalysisUsage &AU) const override {
243  }
244 
245  private:
246  bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
247 
248  Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch,
249  const DebugLoc &DL);
250 
251  /// This function checks if it is valid to move Candidate to the delay slot
252  /// and returns true if it isn't. It also updates memory and register
253  /// dependence information.
254  bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
255  InspectMemInstr &IM) const;
256 
257  /// This function searches range [Begin, End) for an instruction that can be
258  /// moved to the delay slot. Returns true on success.
259  template<typename IterTy>
260  bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
261  RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot,
262  IterTy &Filler) const;
263 
264  /// This function searches in the backward direction for an instruction that
265  /// can be moved to the delay slot. Returns true on success.
266  bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const;
267 
268  /// This function searches MBB in the forward direction for an instruction
269  /// that can be moved to the delay slot. Returns true on success.
270  bool searchForward(MachineBasicBlock &MBB, Iter Slot) const;
271 
272  /// This function searches one of MBB's successor blocks for an instruction
273  /// that can be moved to the delay slot and inserts clones of the
274  /// instruction into the successor's predecessor blocks.
275  bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const;
276 
277  /// Pick a successor block of MBB. Return NULL if MBB doesn't have a
278  /// successor block that is not a landing pad.
279  MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const;
280 
281  /// This function analyzes MBB and returns an instruction with an unoccupied
282  /// slot that branches to Dst.
283  std::pair<MipsInstrInfo::BranchType, MachineInstr *>
284  getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const;
285 
286  /// Examine Pred and see if it is possible to insert an instruction into
287  /// one of its branches delay slot or its end.
288  bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
289  RegDefsUses &RegDU, bool &HasMultipleSuccs,
290  BB2BrMap &BrMap) const;
291 
292  bool terminateSearch(const MachineInstr &Candidate) const;
293 
294  const TargetMachine *TM = nullptr;
295 
296  static char ID;
297  };
298 
299 } // end anonymous namespace
300 
301 char Filler::ID = 0;
302 
303 static bool hasUnoccupiedSlot(const MachineInstr *MI) {
304  return MI->hasDelaySlot() && !MI->isBundledWithSucc();
305 }
306 
307 /// This function inserts clones of Filler into predecessor blocks.
308 static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {
309  MachineFunction *MF = Filler->getParent()->getParent();
310 
311  for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) {
312  if (I->second) {
313  MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler));
314  ++UsefulSlots;
315  } else {
316  I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler));
317  }
318  }
319 }
320 
321 /// This function adds registers Filler defines to MBB's live-in register list.
322 static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {
323  for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) {
324  const MachineOperand &MO = Filler->getOperand(I);
325  unsigned R;
326 
327  if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg()))
328  continue;
329 
330 #ifndef NDEBUG
331  const MachineFunction &MF = *MBB.getParent();
333  "Shouldn't move an instruction with unallocatable registers across "
334  "basic block boundaries.");
335 #endif
336 
337  if (!MBB.isLiveIn(R))
338  MBB.addLiveIn(R);
339  }
340 }
341 
342 RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)
343  : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {}
344 
345 void RegDefsUses::init(const MachineInstr &MI) {
346  // Add all register operands which are explicit and non-variadic.
347  update(MI, 0, MI.getDesc().getNumOperands());
348 
349  // If MI is a call, add RA to Defs to prevent users of RA from going into
350  // delay slot.
351  if (MI.isCall())
352  Defs.set(Mips::RA);
353 
354  // Add all implicit register operands of branch instructions except
355  // register AT.
356  if (MI.isBranch()) {
357  update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands());
358  Defs.reset(Mips::AT);
359  }
360 }
361 
362 void RegDefsUses::setCallerSaved(const MachineInstr &MI) {
363  assert(MI.isCall());
364 
365  // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into
366  // the delay slot. The reason is that RA/RA_64 must not be changed
367  // in the delay slot so that the callee can return to the caller.
368  if (MI.definesRegister(Mips::RA) || MI.definesRegister(Mips::RA_64)) {
369  Defs.set(Mips::RA);
370  Defs.set(Mips::RA_64);
371  }
372 
373  // If MI is a call, add all caller-saved registers to Defs.
374  BitVector CallerSavedRegs(TRI.getNumRegs(), true);
375 
376  CallerSavedRegs.reset(Mips::ZERO);
377  CallerSavedRegs.reset(Mips::ZERO_64);
378 
379  for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent());
380  *R; ++R)
381  for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI)
382  CallerSavedRegs.reset(*AI);
383 
384  Defs |= CallerSavedRegs;
385 }
386 
387 void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {
388  BitVector AllocSet = TRI.getAllocatableSet(MF);
389 
390  for (unsigned R : AllocSet.set_bits())
391  for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI)
392  AllocSet.set(*AI);
393 
394  AllocSet.set(Mips::ZERO);
395  AllocSet.set(Mips::ZERO_64);
396 
397  Defs |= AllocSet.flip();
398 }
399 
400 void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
401  const MachineBasicBlock &SuccBB) {
403  SE = MBB.succ_end(); SI != SE; ++SI)
404  if (*SI != &SuccBB)
405  for (const auto &LI : (*SI)->liveins())
406  Uses.set(LI.PhysReg);
407 }
408 
409 bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {
410  BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());
411  bool HasHazard = false;
412 
413  for (unsigned I = Begin; I != End; ++I) {
414  const MachineOperand &MO = MI.getOperand(I);
415 
416  if (MO.isReg() && MO.getReg())
417  HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef());
418  }
419 
420  Defs |= NewDefs;
421  Uses |= NewUses;
422 
423  return HasHazard;
424 }
425 
426 bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
427  unsigned Reg, bool IsDef) const {
428  if (IsDef) {
429  NewDefs.set(Reg);
430  // check whether Reg has already been defined or used.
431  return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg));
432  }
433 
434  NewUses.set(Reg);
435  // check whether Reg has already been defined.
436  return isRegInSet(Defs, Reg);
437 }
438 
439 bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
440  // Check Reg and all aliased Registers.
441  for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
442  if (RegSet.test(*AI))
443  return true;
444  return false;
445 }
446 
447 bool InspectMemInstr::hasHazard(const MachineInstr &MI) {
448  if (!MI.mayStore() && !MI.mayLoad())
449  return false;
450 
451  if (ForbidMemInstr)
452  return true;
453 
454  OrigSeenLoad = SeenLoad;
455  OrigSeenStore = SeenStore;
456  SeenLoad |= MI.mayLoad();
457  SeenStore |= MI.mayStore();
458 
459  // If MI is an ordered or volatile memory reference, disallow moving
460  // subsequent loads and stores to delay slot.
461  if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
462  ForbidMemInstr = true;
463  return true;
464  }
465 
466  return hasHazard_(MI);
467 }
468 
469 bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) {
470  if (MI.mayStore())
471  return true;
472 
473  if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue())
474  return true;
475 
476  if (const PseudoSourceValue *PSV =
477  (*MI.memoperands_begin())->getPseudoValue()) {
478  if (isa<FixedStackPseudoSourceValue>(PSV))
479  return false;
480  return !PSV->isConstant(nullptr) && !PSV->isStack();
481  }
482 
483  return true;
484 }
485 
486 MemDefsUses::MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI_)
487  : InspectMemInstr(false), MFI(MFI_), DL(DL) {}
488 
489 bool MemDefsUses::hasHazard_(const MachineInstr &MI) {
490  bool HasHazard = false;
492 
493  // Check underlying object list.
494  if (getUnderlyingObjects(MI, Objs)) {
496  I != Objs.end(); ++I)
497  HasHazard |= updateDefsUses(*I, MI.mayStore());
498 
499  return HasHazard;
500  }
501 
502  // No underlying objects found.
503  HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
504  HasHazard |= MI.mayLoad() || OrigSeenStore;
505 
506  SeenNoObjLoad |= MI.mayLoad();
507  SeenNoObjStore |= MI.mayStore();
508 
509  return HasHazard;
510 }
511 
512 bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {
513  if (MayStore)
514  return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore ||
515  SeenNoObjLoad;
516 
517  Uses.insert(V);
518  return Defs.count(V) || SeenNoObjStore;
519 }
520 
521 bool MemDefsUses::
523  SmallVectorImpl<ValueType> &Objects) const {
524  if (!MI.hasOneMemOperand() ||
525  (!(*MI.memoperands_begin())->getValue() &&
526  !(*MI.memoperands_begin())->getPseudoValue()))
527  return false;
528 
529  if (const PseudoSourceValue *PSV =
530  (*MI.memoperands_begin())->getPseudoValue()) {
531  if (!PSV->isAliased(MFI))
532  return false;
533  Objects.push_back(PSV);
534  return true;
535  }
536 
537  const Value *V = (*MI.memoperands_begin())->getValue();
538 
540  GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL);
541 
542  for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), E = Objs.end();
543  I != E; ++I) {
544  if (!isIdentifiedObject(V))
545  return false;
546 
547  Objects.push_back(*I);
548  }
549 
550  return true;
551 }
552 
553 // Replace Branch with the compact branch instruction.
554 Iter Filler::replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch,
555  const DebugLoc &DL) {
556  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
557  const MipsInstrInfo *TII = STI.getInstrInfo();
558 
559  unsigned NewOpcode = TII->getEquivalentCompactForm(Branch);
560  Branch = TII->genInstrWithNewOpc(NewOpcode, Branch);
561 
562  std::next(Branch)->eraseFromParent();
563  return Branch;
564 }
565 
566 // For given opcode returns opcode of corresponding instruction with short
567 // delay slot.
568 // For the pseudo TAILCALL*_MM instructions return the short delay slot
569 // form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range
570 // that is too short to make use of for tail calls.
571 static int getEquivalentCallShort(int Opcode) {
572  switch (Opcode) {
573  case Mips::BGEZAL:
574  return Mips::BGEZALS_MM;
575  case Mips::BLTZAL:
576  return Mips::BLTZALS_MM;
577  case Mips::JAL:
578  return Mips::JALS_MM;
579  case Mips::JALR:
580  return Mips::JALRS_MM;
581  case Mips::JALR16_MM:
582  return Mips::JALRS16_MM;
583  case Mips::TAILCALL_MM:
584  llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!");
585  case Mips::TAILCALLREG:
586  return Mips::JR16_MM;
587  default:
588  llvm_unreachable("Unexpected call instruction for microMIPS.");
589  }
590 }
591 
592 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
593 /// We assume there is only one delay slot per delayed instruction.
594 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
595  bool Changed = false;
596  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
597  bool InMicroMipsMode = STI.inMicroMipsMode();
598  const MipsInstrInfo *TII = STI.getInstrInfo();
599 
600  if (InMicroMipsMode && STI.hasMips32r6()) {
601  // This is microMIPS32r6 or microMIPS64r6 processor. Delay slot for
602  // branching instructions is not needed.
603  return Changed;
604  }
605 
606  for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
607  if (!hasUnoccupiedSlot(&*I))
608  continue;
609 
610  ++FilledSlots;
611  Changed = true;
612 
613  // Delay slot filling is disabled at -O0.
614  if (!DisableDelaySlotFiller && (TM->getOptLevel() != CodeGenOpt::None)) {
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 the same function
643  // if it is in range.
644  DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode())));
645  }
646  continue;
647  }
648  }
649 
650  // For microMIPS if instruction is BEQ or BNE with one ZERO register, then
651  // instead of adding NOP replace this instruction with the corresponding
652  // compact branch instruction, i.e. BEQZC or BNEZC. Additionally
653  // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can
654  // be replaced with JRC16_MM.
655 
656  // For MIPSR6 attempt to produce the corresponding compact (no delay slot)
657  // form of the CTI. For indirect jumps this will not require inserting a
658  // NOP and for branches will hopefully avoid requiring a NOP.
659  if ((InMicroMipsMode ||
661  TII->getEquivalentCompactForm(I)) {
662  I = replaceWithCompactBranch(MBB, I, I->getDebugLoc());
663  continue;
664  }
665 
666  // Bundle the NOP to the instruction with the delay slot.
667  BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP));
668  MIBundleBuilder(MBB, I, std::next(I, 2));
669  }
670 
671  return Changed;
672 }
673 
674 template<typename IterTy>
675 bool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
676  RegDefsUses &RegDU, InspectMemInstr& IM, Iter Slot,
677  IterTy &Filler) const {
678  for (IterTy I = Begin; I != End;) {
679  IterTy CurrI = I;
680  ++I;
681 
682  // skip debug value
683  if (CurrI->isDebugValue())
684  continue;
685 
686  if (terminateSearch(*CurrI))
687  break;
688 
689  assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
690  "Cannot put calls, returns or branches in delay slot.");
691 
692  if (CurrI->isKill()) {
693  CurrI->eraseFromParent();
694  continue;
695  }
696 
697  if (delayHasHazard(*CurrI, RegDU, IM))
698  continue;
699 
700  const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
701  if (STI.isTargetNaCl()) {
702  // In NaCl, instructions that must be masked are forbidden in delay slots.
703  // We only check for loads, stores and SP changes. Calls, returns and
704  // branches are not checked because non-NaCl targets never put them in
705  // delay slots.
706  unsigned AddrIdx;
707  if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
708  baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) ||
709  CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo()))
710  continue;
711  }
712 
713  bool InMicroMipsMode = STI.inMicroMipsMode();
714  const MipsInstrInfo *TII = STI.getInstrInfo();
715  unsigned Opcode = (*Slot).getOpcode();
716  // This is complicated by the tail call optimization. For non-PIC code
717  // there is only a 32bit sized unconditional branch which can be assumed
718  // to be able to reach the target. b16 only has a range of +/- 1 KB.
719  // It's entirely possible that the target function is reachable with b16
720  // but we don't have enough information to make that decision.
721  if (InMicroMipsMode && TII->getInstSizeInBytes(*CurrI) == 2 &&
722  (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
723  Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
724  continue;
725 
726  Filler = CurrI;
727  return true;
728  }
729 
730  return false;
731 }
732 
733 bool Filler::searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const {
735  return false;
736 
737  auto *Fn = MBB.getParent();
738  RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
739  MemDefsUses MemDU(Fn->getDataLayout(), &Fn->getFrameInfo());
740  ReverseIter Filler;
741 
742  RegDU.init(Slot);
743 
744  MachineBasicBlock::iterator SlotI = Slot;
745  if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot,
746  Filler))
747  return false;
748 
749  MBB.splice(std::next(SlotI), &MBB, Filler.getReverse());
750  MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2));
751  ++UsefulSlots;
752  return true;
753 }
754 
755 bool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const {
756  // Can handle only calls.
757  if (DisableForwardSearch || !Slot->isCall())
758  return false;
759 
760  RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
761  NoMemInstr NM;
762  Iter Filler;
763 
764  RegDU.setCallerSaved(*Slot);
765 
766  if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler))
767  return false;
768 
769  MBB.splice(std::next(Slot), &MBB, Filler);
770  MIBundleBuilder(MBB, Slot, std::next(Slot, 2));
771  ++UsefulSlots;
772  return true;
773 }
774 
775 bool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const {
777  return false;
778 
779  MachineBasicBlock *SuccBB = selectSuccBB(MBB);
780 
781  if (!SuccBB)
782  return false;
783 
784  RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
785  bool HasMultipleSuccs = false;
786  BB2BrMap BrMap;
787  std::unique_ptr<InspectMemInstr> IM;
788  Iter Filler;
789  auto *Fn = MBB.getParent();
790 
791  // Iterate over SuccBB's predecessor list.
792  for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(),
793  PE = SuccBB->pred_end(); PI != PE; ++PI)
794  if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap))
795  return false;
796 
797  // Do not allow moving instructions which have unallocatable register operands
798  // across basic block boundaries.
799  RegDU.setUnallocatableRegs(*Fn);
800 
801  // Only allow moving loads from stack or constants if any of the SuccBB's
802  // predecessors have multiple successors.
803  if (HasMultipleSuccs) {
804  IM.reset(new LoadFromStackOrConst());
805  } else {
806  const MachineFrameInfo &MFI = Fn->getFrameInfo();
807  IM.reset(new MemDefsUses(Fn->getDataLayout(), &MFI));
808  }
809 
810  if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot,
811  Filler))
812  return false;
813 
814  insertDelayFiller(Filler, BrMap);
815  addLiveInRegs(Filler, *SuccBB);
816  Filler->eraseFromParent();
817 
818  return true;
819 }
820 
821 MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const {
822  if (B.succ_empty())
823  return nullptr;
824 
825  // Select the successor with the larget edge weight.
826  auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
827  MachineBasicBlock *S = *std::max_element(
828  B.succ_begin(), B.succ_end(),
829  [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) {
830  return Prob.getEdgeProbability(&B, Dst0) <
831  Prob.getEdgeProbability(&B, Dst1);
832  });
833  return S->isEHPad() ? nullptr : S;
834 }
835 
836 std::pair<MipsInstrInfo::BranchType, MachineInstr *>
837 Filler::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const {
838  const MipsInstrInfo *TII =
839  MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();
840  MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;
841  SmallVector<MachineInstr*, 2> BranchInstrs;
843 
845  TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs);
846 
848  return std::make_pair(R, nullptr);
849 
850  if (R != MipsInstrInfo::BT_CondUncond) {
851  if (!hasUnoccupiedSlot(BranchInstrs[0]))
852  return std::make_pair(MipsInstrInfo::BT_None, nullptr);
853 
854  assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));
855 
856  return std::make_pair(R, BranchInstrs[0]);
857  }
858 
859  assert((TrueBB == &Dst) || (FalseBB == &Dst));
860 
861  // Examine the conditional branch. See if its slot is occupied.
862  if (hasUnoccupiedSlot(BranchInstrs[0]))
863  return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]);
864 
865  // If that fails, try the unconditional branch.
866  if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst))
867  return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]);
868 
869  return std::make_pair(MipsInstrInfo::BT_None, nullptr);
870 }
871 
872 bool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
873  RegDefsUses &RegDU, bool &HasMultipleSuccs,
874  BB2BrMap &BrMap) const {
875  std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =
876  getBranch(Pred, Succ);
877 
878  // Return if either getBranch wasn't able to analyze the branches or there
879  // were no branches with unoccupied slots.
880  if (P.first == MipsInstrInfo::BT_None)
881  return false;
882 
883  if ((P.first != MipsInstrInfo::BT_Uncond) &&
884  (P.first != MipsInstrInfo::BT_NoBranch)) {
885  HasMultipleSuccs = true;
886  RegDU.addLiveOut(Pred, Succ);
887  }
888 
889  BrMap[&Pred] = P.second;
890  return true;
891 }
892 
893 bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,
894  InspectMemInstr &IM) const {
895  assert(!Candidate.isKill() &&
896  "KILL instructions should have been eliminated at this point.");
897 
898  bool HasHazard = Candidate.isImplicitDef();
899 
900  HasHazard |= IM.hasHazard(Candidate);
901  HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());
902 
903  return HasHazard;
904 }
905 
906 bool Filler::terminateSearch(const MachineInstr &Candidate) const {
907  return (Candidate.isTerminator() || Candidate.isCall() ||
908  Candidate.isPosition() || Candidate.isInlineAsm() ||
909  Candidate.hasUnmodeledSideEffects());
910 }
911 
912 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
913 /// slots in Mips MachineFunctions
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:109
BitVector & set()
Definition: BitVector.h:398
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:458
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:329
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.
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:560
bool isInlineAsm() const
Definition: MachineInstr.h:832
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")
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:210
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
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:251
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
Reg
All possible values of the reg field in the ModR/M byte.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:474
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:287
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:482
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:639
#define P(N)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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:626
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
&#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:404
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:957
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:831
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:389
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:864
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.
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:601
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:59
Basic Alias true
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap)
This function inserts clones of Filler into predecessor blocks.
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:830
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:626
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:814
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:57
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
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
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