1//===- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Simple pass to fill delay slots with useful instructions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Mips.h"
14#include "MipsInstrInfo.h"
15#include "MipsSubtarget.h"
16#include "llvm/ADT/BitVector.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/PointerUnion.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/CodeGen/MachineBasicBlock.h"
27#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstr.h"
32#include "llvm/CodeGen/MachineInstrBuilder.h"
33#include "llvm/CodeGen/MachineOperand.h"
34#include "llvm/CodeGen/MachinePassManager.h"
35#include "llvm/CodeGen/MachineRegisterInfo.h"
36#include "llvm/CodeGen/PseudoSourceValue.h"
37#include "llvm/CodeGen/TargetRegisterInfo.h"
38#include "llvm/CodeGen/TargetSubtargetInfo.h"
39#include "llvm/IR/Analysis.h"
40#include "llvm/MC/MCInstrDesc.h"
41#include "llvm/MC/MCRegisterInfo.h"
42#include "llvm/Support/Casting.h"
43#include "llvm/Support/CodeGen.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46#include "llvm/Target/TargetMachine.h"
47#include <cassert>
48#include <iterator>
49#include <memory>
50#include <utility>
51
52using namespace llvm;
53
54#define DEBUG_TYPE "mips-delay-slot-filler"
55
56STATISTIC(FilledSlots, "Number of delay slots filled");
57STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
58 " are not NOP.");
59STATISTIC(R5900ShortLoopNops, "Number of delay slots left as NOP for R5900 "
60 "short loop fix");
61
62namespace {
63
64 using Iter = MachineBasicBlock::iterator;
65 using ReverseIter = MachineBasicBlock::reverse_iterator;
66 using BB2BrMap = SmallDenseMap<MachineBasicBlock *, MachineInstr *, 2>;
67
68 // Holds information about one branch instruction
69 // This is used by the MIPS1 target to easily find all paths of a branch to
70 // then check the first instruction for possible load delay hazards
71 class BranchInformation {
72 private:
73 // The pointer to the actual branch instruction
74 const MachineInstr *BranchInstr = nullptr;
75 // The pointer to the instruction after the branch (= the `else` case)
76 const MachineInstr *ElseBranchInstr = nullptr;
77
78 // Check if `Adr` is a pseudo instruction and if so, then treat it as non
79 // existing
80 static const MachineInstr *filterPseudoInstr(const MachineInstr *Adr) {
81 if (Adr && !Adr->isPseudo()) {
82 return Adr;
83 }
84 return nullptr;
85 }
86
87 public:
88 // Creates a new `BranchInformation` from the branch candidate `CurrentSlot`
89 // together with the end (`MBBEnd`) of the current MBB and the first
90 // instruction of the next MBB `NextMBBInstr`
91 BranchInformation(MachineInstrBundleIterator<MachineInstr> CurrentSlot,
92 MachineInstrBundleIterator<MachineInstr> MBBEnd,
93 const MachineInstr *NextMBBInstr)
94 : BranchInstr(
95 CurrentSlot->isBranch()
96 ? BranchInformation::filterPseudoInstr(Adr: &(*CurrentSlot))
97 : nullptr),
98 ElseBranchInstr(
99 (++CurrentSlot) == MBBEnd
100 ? BranchInformation::filterPseudoInstr(Adr: NextMBBInstr)
101 : BranchInformation::filterPseudoInstr(Adr: &(*CurrentSlot))) {}
102
103 // Checks if we have a branch
104 constexpr bool hasBranchInstr() const { return this->BranchInstr; }
105
106 // Checks if we have an else branch
107 constexpr bool hasBranchElseInstr() const { return this->ElseBranchInstr; }
108
109 // Checks if we have an indirect branch
110 constexpr bool isIndirectBranch() const {
111 if (this->BranchInstr) {
112 return this->BranchInstr->isIndirectBranch();
113 }
114 return false;
115 }
116
117 // Checks if we have an unconditional branch
118 constexpr bool isUnconditionalBranch() const {
119 if (this->BranchInstr) {
120 return this->BranchInstr->isUnconditionalBranch();
121 }
122 return false;
123 }
124
125 // Accesses the branch instruction
126 const MachineInstr *getBranchInstr() const { return this->BranchInstr; }
127
128 // Accesses the instruction after the branch
129 const MachineInstr *getBranchElseInstr() const {
130 return this->ElseBranchInstr;
131 }
132
133 // Gets the target of the branch
134 const MachineBasicBlock *getBranchTarget() const {
135 if (this->isIndirectBranch() || !this->hasBranchInstr()) {
136 // Indirect branch has no known target
137 return nullptr;
138 }
139
140 for (const MachineOperand &MO : this->BranchInstr->operands()) {
141 if (MO.isMBB()) {
142 return MO.getMBB();
143 }
144 }
145 return nullptr;
146 }
147 };
148
149 class RegDefsUses {
150 public:
151 RegDefsUses(const TargetRegisterInfo &TRI);
152
153 void init(const MachineInstr &MI);
154
155 /// This function sets all caller-saved registers in Defs.
156 void setCallerSaved(const MachineInstr &MI);
157
158 /// This function sets all unallocatable registers in Defs.
159 void setUnallocatableRegs(const MachineFunction &MF);
160
161 /// Set bits in Uses corresponding to MBB's live-out registers except for
162 /// the registers that are live-in to SuccBB.
163 void addLiveOut(const MachineBasicBlock &MBB,
164 const MachineBasicBlock &SuccBB);
165
166 bool update(const MachineInstr &MI, unsigned Begin, unsigned End);
167
168 private:
169 bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg,
170 bool IsDef) const;
171
172 /// Returns true if Reg or its alias is in RegSet.
173 bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
174
175 const TargetRegisterInfo &TRI;
176 BitVector Defs, Uses;
177 };
178
179 /// Base class for inspecting loads and stores.
180 class InspectMemInstr {
181 public:
182 InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {}
183 virtual ~InspectMemInstr() = default;
184
185 /// Return true if MI cannot be moved to delay slot.
186 bool hasHazard(const MachineInstr &MI);
187
188 protected:
189 /// Flags indicating whether loads or stores have been seen.
190 bool OrigSeenLoad = false;
191 bool OrigSeenStore = false;
192 bool SeenLoad = false;
193 bool SeenStore = false;
194
195 /// Memory instructions are not allowed to move to delay slot if this flag
196 /// is true.
197 bool ForbidMemInstr;
198
199 private:
200 virtual bool hasHazard_(const MachineInstr &MI) = 0;
201 };
202
203 /// This subclass rejects any memory instructions.
204 class NoMemInstr : public InspectMemInstr {
205 public:
206 NoMemInstr() : InspectMemInstr(true) {}
207
208 private:
209 bool hasHazard_(const MachineInstr &MI) override { return true; }
210 };
211
212 /// This subclass accepts loads from stacks and constant loads.
213 class LoadFromStackOrConst : public InspectMemInstr {
214 public:
215 LoadFromStackOrConst() : InspectMemInstr(false) {}
216
217 private:
218 bool hasHazard_(const MachineInstr &MI) override;
219 };
220
221 /// This subclass uses memory dependence information to determine whether a
222 /// memory instruction can be moved to a delay slot.
223 class MemDefsUses : public InspectMemInstr {
224 public:
225 explicit MemDefsUses(const MachineFrameInfo *MFI);
226
227 private:
228 using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;
229
230 bool hasHazard_(const MachineInstr &MI) override;
231
232 /// Update Defs and Uses. Return true if there exist dependences that
233 /// disqualify the delay slot candidate between V and values in Uses and
234 /// Defs.
235 bool updateDefsUses(ValueType V, bool MayStore);
236
237 /// Get the list of underlying objects of MI's memory operand.
238 bool getUnderlyingObjects(const MachineInstr &MI,
239 SmallVectorImpl<ValueType> &Objects) const;
240
241 const MachineFrameInfo *MFI;
242 SmallPtrSet<ValueType, 4> Uses, Defs;
243
244 /// Flags indicating whether loads or stores with no underlying objects have
245 /// been seen.
246 bool SeenNoObjLoad = false;
247 bool SeenNoObjStore = false;
248 };
249
250 class MipsDelaySlotFillerLegacy : public MachineFunctionPass {
251 public:
252 MipsDelaySlotFillerLegacy() : MachineFunctionPass(ID) {}
253
254 StringRef getPassName() const override { return "Mips Delay Slot Filler"; }
255
256 bool runOnMachineFunction(MachineFunction &F) override;
257
258 MachineFunctionProperties getRequiredProperties() const override {
259 return MachineFunctionProperties().setNoVRegs();
260 }
261
262 void getAnalysisUsage(AnalysisUsage &AU) const override {
263 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
264 AU.setPreservesCFG();
265 MachineFunctionPass::getAnalysisUsage(AU);
266 }
267
268 static char ID;
269 };
270
271} // end anonymous namespace
272
273char MipsDelaySlotFillerLegacy::ID = 0;
274
275static bool hasUnoccupiedSlot(const MachineInstr *MI) {
276 return MI->hasDelaySlot() && !MI->isBundledWithSucc();
277}
278
279/// Check if a branch is a short backward loop that triggers the R5900 erratum.
280/// Quote from binutils-gdb/gas/config/tc-mips.c:
281///
282/// On the R5900 short loops need to be fixed by inserting a NOP in the
283/// branch delay slot.
284///
285/// The short loop bug under certain conditions causes loops to execute
286/// only once or twice. We must ensure that the assembler never
287/// generates loops that satisfy all of the following conditions:
288///
289/// - a loop consists of less than or equal to six instructions
290/// (including the branch delay slot);
291/// - a loop contains only one conditional branch instruction at the end
292/// of the loop;
293/// - a loop does not contain any other branch or jump instructions;
294/// - a branch delay slot of the loop is not NOP (EE 2.9 or later).
295///
296/// We need to do this because of a hardware bug in the R5900 chip.
297static bool isR5900ShortLoopBranch(const MachineInstr *MI,
298 const MachineBasicBlock &MBB) {
299 // Must be a conditional branch (not jump or indirect branch)
300 if (!MI->isBranch() || MI->isIndirectBranch())
301 return false;
302
303 // Check if this is a conditional branch by looking for an MBB operand
304 const MachineBasicBlock *TargetMBB = nullptr;
305 for (const MachineOperand &MO : MI->operands()) {
306 if (MO.isMBB()) {
307 TargetMBB = MO.getMBB();
308 break;
309 }
310 }
311
312 // Must have a target and must target the same basic block (backward branch)
313 if (!TargetMBB || TargetMBB != &MBB)
314 return false;
315
316 // Count instructions from the beginning of the block to the branch
317 // A short loop is 6 instructions or fewer (including branch + delay slot)
318 // The delay slot adds 1 more, so we check if instructions before branch <= 5
319 unsigned InstrCount = 0;
320 bool HasOtherBranch = false;
321
322 for (const MachineInstr &Instr : MBB) {
323 if (&Instr == MI)
324 break;
325
326 // Skip debug and pseudo instructions
327 if (Instr.isDebugInstr() || Instr.isTransient())
328 continue;
329
330 ++InstrCount;
331
332 // If there's another branch in the loop, the erratum doesn't apply
333 if (Instr.isBranch() || Instr.isCall()) {
334 HasOtherBranch = true;
335 break;
336 }
337 }
338
339 // If there's another branch/call in the loop, erratum doesn't apply
340 if (HasOtherBranch)
341 return false;
342
343 // Add 1 for the branch itself, +1 for delay slot = InstrCount + 2
344 // Erratum triggers when total <= 6, so InstrCount + 2 <= 6 => InstrCount <= 4
345 // But we're conservative: if InstrCount <= 5 (total <= 7), skip filling
346 // to match the exact condition from r5900check: offset -5 to -1 (2-6 instrs)
347 return InstrCount <= 5;
348}
349
350INITIALIZE_PASS(MipsDelaySlotFillerLegacy, DEBUG_TYPE,
351 "Fill delay slot for MIPS", false, false)
352
353/// This function inserts clones of Filler into predecessor blocks.
354static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {
355 MachineFunction *MF = Filler->getParent()->getParent();
356
357 for (const auto &I : BrMap) {
358 if (I.second) {
359 MIBundleBuilder(I.second).append(MI: MF->CloneMachineInstr(Orig: &*Filler));
360 ++UsefulSlots;
361 } else {
362 I.first->push_back(MI: MF->CloneMachineInstr(Orig: &*Filler));
363 }
364 }
365}
366
367/// This function adds registers Filler defines to MBB's live-in register list.
368static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {
369 for (const MachineOperand &MO : Filler->operands()) {
370 unsigned R;
371
372 if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg()))
373 continue;
374
375#ifndef NDEBUG
376 const MachineFunction &MF = *MBB.getParent();
377 assert(MF.getSubtarget().getRegisterInfo()->getAllocatableSet(MF).test(R) &&
378 "Shouldn't move an instruction with unallocatable registers across "
379 "basic block boundaries.");
380#endif
381
382 if (!MBB.isLiveIn(Reg: R))
383 MBB.addLiveIn(PhysReg: R);
384 }
385}
386
387RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)
388 : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {}
389
390void RegDefsUses::init(const MachineInstr &MI) {
391 // Add all register operands which are explicit and non-variadic.
392 update(MI, Begin: 0, End: MI.getDesc().getNumOperands());
393
394 // If MI is a call, add RA to Defs to prevent users of RA from going into
395 // delay slot.
396 if (MI.isCall())
397 Defs.set(Mips::RA);
398
399 // Add all implicit register operands of branch instructions except
400 // register AT.
401 if (MI.isBranch()) {
402 update(MI, Begin: MI.getDesc().getNumOperands(), End: MI.getNumOperands());
403 Defs.reset(Idx: Mips::R1);
404 }
405}
406
407void RegDefsUses::setCallerSaved(const MachineInstr &MI) {
408 assert(MI.isCall());
409
410 // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into
411 // the delay slot. The reason is that RA/RA_64 must not be changed
412 // in the delay slot so that the callee can return to the caller.
413 if (MI.definesRegister(Reg: Mips::RA, /*TRI=*/nullptr) ||
414 MI.definesRegister(Reg: Mips::RA_64, /*TRI=*/nullptr)) {
415 Defs.set(Mips::RA);
416 Defs.set(Mips::RA_64);
417 }
418
419 // If MI is a call, add all caller-saved registers to Defs.
420 BitVector CallerSavedRegs(TRI.getNumRegs(), true);
421
422 CallerSavedRegs.reset(Idx: Mips::R0);
423 CallerSavedRegs.reset(Idx: Mips::R0_64);
424
425 for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MF: MI.getParent()->getParent());
426 *R; ++R)
427 for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI)
428 CallerSavedRegs.reset(Idx: *AI);
429
430 Defs |= CallerSavedRegs;
431}
432
433void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {
434 BitVector AllocSet = TRI.getAllocatableSet(MF);
435
436 for (unsigned R : AllocSet.set_bits())
437 for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI)
438 AllocSet.set(*AI);
439
440 AllocSet.set(Mips::R0);
441 AllocSet.set(Mips::R0_64);
442
443 Defs |= AllocSet.flip();
444}
445
446void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
447 const MachineBasicBlock &SuccBB) {
448 for (const MachineBasicBlock *S : MBB.successors())
449 if (S != &SuccBB)
450 for (const auto &LI : S->liveins())
451 Uses.set(LI.PhysReg.id());
452}
453
454bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {
455 BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());
456 bool HasHazard = false;
457
458 for (unsigned I = Begin; I != End; ++I) {
459 const MachineOperand &MO = MI.getOperand(i: I);
460
461 if (MO.isReg() && MO.getReg()) {
462 if (checkRegDefsUses(NewDefs, NewUses, Reg: MO.getReg(), IsDef: MO.isDef())) {
463 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found register hazard for operand "
464 << I << ": ";
465 MO.dump());
466 HasHazard = true;
467 }
468 }
469 }
470
471 Defs |= NewDefs;
472 Uses |= NewUses;
473
474 return HasHazard;
475}
476
477bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
478 unsigned Reg, bool IsDef) const {
479 if (IsDef) {
480 NewDefs.set(Reg);
481 // check whether Reg has already been defined or used.
482 return (isRegInSet(RegSet: Defs, Reg) || isRegInSet(RegSet: Uses, Reg));
483 }
484
485 NewUses.set(Reg);
486 // check whether Reg has already been defined.
487 return isRegInSet(RegSet: Defs, Reg);
488}
489
490bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
491 // Check Reg and all aliased Registers.
492 for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
493 if (RegSet.test(Idx: *AI))
494 return true;
495 return false;
496}
497
498bool InspectMemInstr::hasHazard(const MachineInstr &MI) {
499 if (!MI.mayStore() && !MI.mayLoad())
500 return false;
501
502 if (ForbidMemInstr)
503 return true;
504
505 OrigSeenLoad = SeenLoad;
506 OrigSeenStore = SeenStore;
507 SeenLoad |= MI.mayLoad();
508 SeenStore |= MI.mayStore();
509
510 // If MI is an ordered or volatile memory reference, disallow moving
511 // subsequent loads and stores to delay slot.
512 if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
513 ForbidMemInstr = true;
514 return true;
515 }
516
517 return hasHazard_(MI);
518}
519
520bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) {
521 if (MI.mayStore())
522 return true;
523
524 if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue())
525 return true;
526
527 if (const PseudoSourceValue *PSV =
528 (*MI.memoperands_begin())->getPseudoValue()) {
529 if (isa<FixedStackPseudoSourceValue>(Val: PSV))
530 return false;
531 return !PSV->isConstant(nullptr) && !PSV->isStack();
532 }
533
534 return true;
535}
536
537MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_)
538 : InspectMemInstr(false), MFI(MFI_) {}
539
540bool MemDefsUses::hasHazard_(const MachineInstr &MI) {
541 bool HasHazard = false;
542
543 // Check underlying object list.
544 SmallVector<ValueType, 4> Objs;
545 if (getUnderlyingObjects(MI, Objects&: Objs)) {
546 for (ValueType VT : Objs)
547 HasHazard |= updateDefsUses(V: VT, MayStore: MI.mayStore());
548 return HasHazard;
549 }
550
551 // No underlying objects found.
552 HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
553 HasHazard |= MI.mayLoad() || OrigSeenStore;
554
555 SeenNoObjLoad |= MI.mayLoad();
556 SeenNoObjStore |= MI.mayStore();
557
558 return HasHazard;
559}
560
561bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {
562 if (MayStore)
563 return !Defs.insert(Ptr: V).second || Uses.count(Ptr: V) || SeenNoObjStore ||
564 SeenNoObjLoad;
565
566 Uses.insert(Ptr: V);
567 return Defs.count(Ptr: V) || SeenNoObjStore;
568}
569
570bool MemDefsUses::
571getUnderlyingObjects(const MachineInstr &MI,
572 SmallVectorImpl<ValueType> &Objects) const {
573 if (!MI.hasOneMemOperand())
574 return false;
575
576 auto & MMO = **MI.memoperands_begin();
577
578 if (const PseudoSourceValue *PSV = MMO.getPseudoValue()) {
579 if (!PSV->isAliased(MFI))
580 return false;
581 Objects.push_back(Elt: PSV);
582 return true;
583 }
584
585 if (const Value *V = MMO.getValue()) {
586 SmallVector<const Value *, 4> Objs;
587 ::getUnderlyingObjects(V, Objects&: Objs);
588
589 for (const Value *UValue : Objs) {
590 if (!isIdentifiedObject(V))
591 return false;
592
593 Objects.push_back(Elt: UValue);
594 }
595 return true;
596 }
597
598 return false;
599}
600
601// Replace Branch with the compact branch instruction.
602static Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch,
603 const DebugLoc &DL) {
604 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
605 const MipsInstrInfo *TII = STI.getInstrInfo();
606
607 unsigned NewOpcode = TII->getEquivalentCompactForm(I: Branch);
608 Branch = TII->genInstrWithNewOpc(NewOpc: NewOpcode, I: Branch);
609
610 auto *ToErase = cast<MachineInstr>(Val: &*std::next(x: Branch));
611 // Update call info for the Branch.
612 if (ToErase->shouldUpdateAdditionalCallInfo())
613 ToErase->getMF()->moveAdditionalCallInfo(Old: ToErase,
614 New: cast<MachineInstr>(Val: &*Branch));
615 ToErase->eraseFromParent();
616 return Branch;
617}
618
619// For given opcode returns opcode of corresponding instruction with short
620// delay slot.
621// For the pseudo TAILCALL*_MM instructions return the short delay slot
622// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range
623// that is too short to make use of for tail calls.
624static int getEquivalentCallShort(int Opcode) {
625 switch (Opcode) {
626 case Mips::BGEZAL:
627 return Mips::BGEZALS_MM;
628 case Mips::BLTZAL:
629 return Mips::BLTZALS_MM;
630 case Mips::JAL:
631 case Mips::JAL_MM:
632 return Mips::JALS_MM;
633 case Mips::JALR:
634 return Mips::JALRS_MM;
635 case Mips::JALR16_MM:
636 return Mips::JALRS16_MM;
637 case Mips::TAILCALL_MM:
638 llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!");
639 case Mips::TAILCALLREG:
640 return Mips::JR16_MM;
641 default:
642 llvm_unreachable("Unexpected call instruction for microMIPS.");
643 }
644}
645
646static bool terminateSearch(const MachineInstr &Candidate) {
647 return (Candidate.isTerminator() || Candidate.isCall() ||
648 Candidate.isPosition() || Candidate.isInlineAsm() ||
649 Candidate.hasUnmodeledSideEffects());
650}
651
652/// Returns true if putting the candidate in the delay slot could let the
653/// branch target, or the instruction after the slot, read its result too
654/// early, or if those cannot be determined.
655static bool delayExposesHazard(
656 const BranchInformation &BranchInfo, const MachineInstr &Candidate,
657 function_ref<bool(const MachineInstr &, const MachineInstr &)> IsSafe) {
658 // With no branch, or a branch whose target we cannot see, we do not know
659 // which instruction executes next. Assume the worst.
660 if (!BranchInfo.hasBranchInstr() || BranchInfo.isIndirectBranch())
661 return true;
662
663 const MachineBasicBlock *TargetMBB = BranchInfo.getBranchTarget();
664 if (!TargetMBB || TargetMBB->empty())
665 return true;
666
667 bool Exposed = !IsSafe(TargetMBB->instr_front(), Candidate);
668
669 // A conditional branch also falls through, so the instruction after the
670 // delay slot can be the one that reads the result.
671 if (!BranchInfo.isUnconditionalBranch()) {
672 if (!BranchInfo.hasBranchElseInstr())
673 return true;
674 Exposed |= !IsSafe(*BranchInfo.getBranchElseInstr(), Candidate);
675 }
676
677 return Exposed;
678}
679
680/// This function checks if it is valid to move Candidate to the delay slot
681/// and returns true if it isn't. It also updates memory and register
682/// dependence information.
683static bool delayHasHazard(const MipsSubtarget &STI,
684 const MachineInstr &Candidate,
685 const BranchInformation &BranchInfo,
686 RegDefsUses &RegDU, InspectMemInstr &IM) {
687 assert(!Candidate.isKill() &&
688 "KILL instructions should have been eliminated at this point.");
689
690 bool HasHazard = Candidate.isImplicitDef();
691
692 HasHazard |= IM.hasHazard(MI: Candidate);
693 HasHazard |= RegDU.update(MI: Candidate, Begin: 0, End: Candidate.getNumOperands());
694
695 if (!HasHazard) {
696 const MipsInstrInfo *TII = STI.getInstrInfo();
697
698 // MIPS-I has no load-use interlock: the instruction executed after a load
699 // must not read the loaded register.
700 if (STI.hasMips1() && !STI.hasMips2() && TII->HasLoadDelaySlot(MI: Candidate))
701 return delayExposesHazard(
702 BranchInfo, Candidate,
703 IsSafe: [TII](const MachineInstr &InShadow, const MachineInstr &Cand) {
704 return TII->SafeInLoadDelaySlot(MIInSlot: InShadow, LoadMI: Cand);
705 });
706
707 // MIPS-I through MIPS-III have the same problem when a value is moved
708 // out of the floating point unit:
709 if (!STI.hasMips32() && !STI.hasMips4() && TII->HasFPUDelaySlot(MI: Candidate))
710 return delayExposesHazard(
711 BranchInfo, Candidate,
712 IsSafe: [TII](const MachineInstr &InShadow, const MachineInstr &Cand) {
713 return TII->SafeInFPUDelaySlot(MIInSlot: InShadow, FPUMI: Cand);
714 });
715 }
716
717 return HasHazard;
718}
719
720/// This function searches range [Begin, End) for an instruction that can be
721/// moved to the delay slot. Returns true on success.
722template <typename IterTy>
723static bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,
724 const BranchInformation &BranchInfo, RegDefsUses &RegDU,
725 InspectMemInstr &IM, Iter Slot, IterTy &Filler) {
726 for (IterTy I = Begin; I != End;) {
727 IterTy CurrI = I;
728 ++I;
729 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": checking instruction: "; CurrI->dump());
730
731 if (terminateSearch(*CurrI)) {
732 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": should terminate search: ";
733 CurrI->dump());
734 break;
735 }
736 // Skip debug and pseudo instructions.
737 // Instruction TargetOpcode::JUMP_TABLE_DEBUG_INFO is only used to note
738 // jump table debug info.
739 if (CurrI->isDebugInstr() || CurrI->isJumpTableDebugInfo() ||
740 CurrI->isMetaInstruction()) {
741 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring debug instruction: ";
742 CurrI->dump());
743 continue;
744 }
745
746 if (CurrI->isBundle()) {
747 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring BUNDLE instruction: ";
748 CurrI->dump());
749 // However, we still need to update the register def-use information.
750 RegDU.update(MI: *CurrI, Begin: 0, End: CurrI->getNumOperands());
751 continue;
752 }
753
754 assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
755 "Cannot put calls, returns or branches in delay slot.");
756
757 if (CurrI->isKill()) {
758 CurrI->eraseFromParent();
759 continue;
760 }
761
762 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
763 if (delayHasHazard(STI, *CurrI, BranchInfo, RegDU, IM))
764 continue;
765
766 bool InMicroMipsMode = STI.inMicroMipsMode();
767 const MipsInstrInfo *TII = STI.getInstrInfo();
768 unsigned Opcode = (*Slot).getOpcode();
769
770 // In mips1-4, should not put mflo into the delay slot for the return.
771 if ((IsMFLOMFHI(CurrI->getOpcode())) &&
772 (!STI.hasMips32() && !STI.hasMips5()))
773 continue;
774
775 // This is complicated by the tail call optimization. For non-PIC code
776 // there is only a 32bit sized unconditional branch which can be assumed
777 // to be able to reach the target. b16 only has a range of +/- 1 KB.
778 // It's entirely possible that the target function is reachable with b16
779 // but we don't have enough information to make that decision.
780 if (InMicroMipsMode && TII->getInstSizeInBytes(MI: *CurrI) == 2 &&
781 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
782 Opcode == Mips::PseudoIndirectBranch_MM ||
783 Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
784 continue;
785 // Instructions LWP/SWP and MOVEP should not be in a delay slot as that
786 // results in unpredictable behaviour
787 if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM ||
788 Opcode == Mips::MOVEP_MM))
789 continue;
790
791 Filler = CurrI;
792 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot: ";
793 CurrI->dump());
794
795 return true;
796 }
797
798 return false;
799}
800
801/// This function searches in the backward direction for an instruction that
802/// can be moved to the delay slot. Returns true on success.
803static bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot,
804 const BranchInformation &BranchInfo) {
805 const MipsOptions &CLOpts =
806 MBB.getParent()->getSubtarget<MipsSubtarget>().getCLOpts();
807 if (CLOpts.disable_mips_df_backward_search)
808 return false;
809
810 auto *Fn = MBB.getParent();
811 RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
812 MemDefsUses MemDU(&Fn->getFrameInfo());
813 ReverseIter Filler;
814
815 RegDU.init(MI: Slot);
816
817 MachineBasicBlock::iterator SlotI = Slot;
818 if (!searchRange(MBB, Begin: ++SlotI.getReverse(), End: MBB.rend(), BranchInfo, RegDU,
819 IM&: MemDU, Slot, Filler)) {
820 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay "
821 "slot using backwards search.\n");
822 return false;
823 }
824
825 MBB.splice(Where: std::next(x: SlotI), Other: &MBB, From: Filler.getReverse());
826 MIBundleBuilder(MBB, SlotI, std::next(x: SlotI, n: 2));
827 ++UsefulSlots;
828 return true;
829}
830
831/// This function searches MBB in the forward direction for an instruction
832/// that can be moved to the delay slot. Returns true on success.
833static bool searchForward(MachineBasicBlock &MBB, Iter Slot,
834 const BranchInformation &BranchInfo) {
835 const MipsOptions &CLOpts =
836 MBB.getParent()->getSubtarget<MipsSubtarget>().getCLOpts();
837 // Can handle only calls.
838 if (CLOpts.disable_mips_df_forward_search || !Slot->isCall())
839 return false;
840
841 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
842 NoMemInstr NM;
843 Iter Filler;
844
845 RegDU.setCallerSaved(*Slot);
846
847 if (!searchRange(MBB, Begin: std::next(x: Slot), End: MBB.end(), BranchInfo, RegDU, IM&: NM, Slot,
848 Filler)) {
849 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay "
850 "slot using forwards search.\n");
851 return false;
852 }
853
854 MBB.splice(Where: std::next(x: Slot), Other: &MBB, From: Filler);
855 MIBundleBuilder(MBB, Slot, std::next(x: Slot, n: 2));
856 ++UsefulSlots;
857 return true;
858}
859
860/// Pick a successor block of MBB. Return NULL if MBB doesn't have a
861/// successor block that is not a landing pad.
862static MachineBasicBlock *
863selectSuccBB(MachineBasicBlock &B,
864 function_ref<MachineBranchProbabilityInfo &()> GetMBPI) {
865 if (B.succ_empty())
866 return nullptr;
867
868 // Select the successor with the larget edge weight.
869 MachineBranchProbabilityInfo &Prob = GetMBPI();
870 MachineBasicBlock *S =
871 *llvm::max_element(Range: B.successors(), C: [&](const MachineBasicBlock *Dst0,
872 const MachineBasicBlock *Dst1) {
873 return Prob.getEdgeProbability(Src: &B, Dst: Dst0) <
874 Prob.getEdgeProbability(Src: &B, Dst: Dst1);
875 });
876 return S->isEHPad() ? nullptr : S;
877}
878
879/// This function analyzes MBB and returns an instruction with an unoccupied
880/// slot that branches to Dst.
881static std::pair<MipsInstrInfo::BranchType, MachineInstr *>
882getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) {
883 const MipsInstrInfo *TII =
884 MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();
885 MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;
886 SmallVector<MachineInstr*, 2> BranchInstrs;
887 SmallVector<MachineOperand, 2> Cond;
888
889 MipsInstrInfo::BranchType R =
890 TII->analyzeBranch(MBB, TBB&: TrueBB, FBB&: FalseBB, Cond, AllowModify: false, BranchInstrs);
891
892 if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch))
893 return std::make_pair(x&: R, y: nullptr);
894
895 if (R != MipsInstrInfo::BT_CondUncond) {
896 if (!hasUnoccupiedSlot(MI: BranchInstrs[0]))
897 return std::make_pair(x: MipsInstrInfo::BT_None, y: nullptr);
898
899 assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));
900
901 return std::make_pair(x&: R, y&: BranchInstrs[0]);
902 }
903
904 assert((TrueBB == &Dst) || (FalseBB == &Dst));
905
906 // Examine the conditional branch. See if its slot is occupied.
907 if (hasUnoccupiedSlot(MI: BranchInstrs[0]))
908 return std::make_pair(x: MipsInstrInfo::BT_Cond, y&: BranchInstrs[0]);
909
910 // If that fails, try the unconditional branch.
911 if (hasUnoccupiedSlot(MI: BranchInstrs[1]) && (FalseBB == &Dst))
912 return std::make_pair(x: MipsInstrInfo::BT_Uncond, y&: BranchInstrs[1]);
913
914 return std::make_pair(x: MipsInstrInfo::BT_None, y: nullptr);
915}
916
917/// Examine Pred and see if it is possible to insert an instruction into
918/// one of its branches delay slot or its end.
919static bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,
920 RegDefsUses &RegDU, bool &HasMultipleSuccs,
921 BB2BrMap &BrMap) {
922 std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =
923 getBranch(MBB&: Pred, Dst: Succ);
924
925 // Return if either getBranch wasn't able to analyze the branches or there
926 // were no branches with unoccupied slots.
927 if (P.first == MipsInstrInfo::BT_None)
928 return false;
929
930 if ((P.first != MipsInstrInfo::BT_Uncond) &&
931 (P.first != MipsInstrInfo::BT_NoBranch)) {
932 HasMultipleSuccs = true;
933 RegDU.addLiveOut(MBB: Pred, SuccBB: Succ);
934 }
935
936 BrMap[&Pred] = P.second;
937 return true;
938}
939
940/// This function searches one of MBB's successor blocks for an instruction
941/// that can be moved to the delay slot and inserts clones of the
942/// instruction into the successor's predecessor blocks.
943static bool
944searchSuccBBs(MachineBasicBlock &MBB, Iter Slot,
945 const BranchInformation &BranchInfo,
946 function_ref<MachineBranchProbabilityInfo &()> GetMBPI) {
947 const MipsOptions &CLOpts =
948 MBB.getParent()->getSubtarget<MipsSubtarget>().getCLOpts();
949 if (CLOpts.disable_mips_df_succbb_search)
950 return false;
951
952 MachineBasicBlock *SuccBB = selectSuccBB(B&: MBB, GetMBPI);
953
954 if (!SuccBB)
955 return false;
956
957 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
958 bool HasMultipleSuccs = false;
959 BB2BrMap BrMap;
960 std::unique_ptr<InspectMemInstr> IM;
961 Iter Filler;
962 auto *Fn = MBB.getParent();
963
964 // Iterate over SuccBB's predecessor list.
965 for (MachineBasicBlock *Pred : SuccBB->predecessors())
966 if (!examinePred(Pred&: *Pred, Succ: *SuccBB, RegDU, HasMultipleSuccs, BrMap))
967 return false;
968
969 // Do not allow moving instructions which have unallocatable register operands
970 // across basic block boundaries.
971 RegDU.setUnallocatableRegs(*Fn);
972
973 // Only allow moving loads from stack or constants if any of the SuccBB's
974 // predecessors have multiple successors.
975 if (HasMultipleSuccs) {
976 IM.reset(p: new LoadFromStackOrConst());
977 } else {
978 const MachineFrameInfo &MFI = Fn->getFrameInfo();
979 IM.reset(p: new MemDefsUses(&MFI));
980 }
981
982 if (!searchRange(MBB, Begin: SuccBB->begin(), End: SuccBB->end(), BranchInfo, RegDU, IM&: *IM,
983 Slot, Filler))
984 return false;
985
986 insertDelayFiller(Filler, BrMap);
987 addLiveInRegs(Filler, MBB&: *SuccBB);
988 Filler->eraseFromParent();
989
990 return true;
991}
992
993/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
994/// We assume there is only one delay slot per delayed instruction.
995static bool
996runOnMachineBasicBlock(MachineBasicBlock &MBB, MachineInstr *FirstNextMBBInstr,
997 function_ref<MachineBranchProbabilityInfo &()> GetMBPI) {
998 const MipsOptions &CLOpts =
999 MBB.getParent()->getSubtarget<MipsSubtarget>().getCLOpts();
1000 const TargetMachine &TM = MBB.getParent()->getTarget();
1001 bool Changed = false;
1002 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();
1003 bool InMicroMipsMode = STI.inMicroMipsMode();
1004 const MipsInstrInfo *TII = STI.getInstrInfo();
1005
1006 for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
1007 if (!hasUnoccupiedSlot(MI: &*I))
1008 continue;
1009
1010 // R5900 short loop erratum fix: skip delay slot filling for short backward
1011 // loops to avoid triggering a hardware bug where short loops may exit
1012 // early. The fix can be controlled with -mfix-r5900 / -mno-fix-r5900.
1013 bool SkipForFixR5900 = false;
1014 if (STI.fixR5900() && isR5900ShortLoopBranch(MI: &*I, MBB)) {
1015 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": skipping delay slot fill for R5900 "
1016 "short loop branch.\n");
1017 ++R5900ShortLoopNops;
1018 SkipForFixR5900 = true;
1019 }
1020
1021 // Delay slot filling is disabled at -O0, in microMIPS32R6, or for R5900
1022 // short loop branches.
1023 if (!CLOpts.disable_mips_delay_filler &&
1024 (TM.getOptLevel() != CodeGenOptLevel::None) &&
1025 !(InMicroMipsMode && STI.hasMips32r6()) && !SkipForFixR5900) {
1026
1027 bool Filled = false;
1028 const auto BranchInfo =
1029 BranchInformation(I, MBB.end(), FirstNextMBBInstr);
1030
1031 if (CLOpts.compact_branches != CompactBranchPolicy::Always ||
1032 !TII->getEquivalentCompactForm(I)) {
1033 if (searchBackward(MBB, Slot&: *I, BranchInfo)) {
1034 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"
1035 " in backwards search.\n");
1036 Filled = true;
1037 } else if (I->isTerminator()) {
1038 if (searchSuccBBs(MBB, Slot: I, BranchInfo, GetMBPI)) {
1039 Filled = true;
1040 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"
1041 " in successor BB search.\n");
1042 }
1043 } else if (searchForward(MBB, Slot: I, BranchInfo)) {
1044 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"
1045 " in forwards search.\n");
1046 Filled = true;
1047 }
1048 }
1049
1050 if (Filled) {
1051 // Get instruction with delay slot.
1052 MachineBasicBlock::instr_iterator DSI = I.getInstrIterator();
1053
1054 if (InMicroMipsMode && TII->getInstSizeInBytes(MI: *std::next(x: DSI)) == 2 &&
1055 DSI->isCall()) {
1056 // If instruction in delay slot is 16b change opcode to
1057 // corresponding instruction with short delay slot.
1058
1059 // TODO: Implement an instruction mapping table of 16bit opcodes to
1060 // 32bit opcodes so that an instruction can be expanded. This would
1061 // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop.
1062 // TODO: Permit b16 when branching backwards to the same function
1063 // if it is in range.
1064 DSI->setDesc(TII->get(Opcode: getEquivalentCallShort(Opcode: DSI->getOpcode())));
1065 }
1066 ++FilledSlots;
1067 Changed = true;
1068 continue;
1069 }
1070 }
1071
1072 // For microMIPS if instruction is BEQ or BNE with one ZERO register, then
1073 // instead of adding NOP replace this instruction with the corresponding
1074 // compact branch instruction, i.e. BEQZC or BNEZC. Additionally
1075 // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can
1076 // be replaced with JRC16_MM.
1077
1078 // For MIPSR6 attempt to produce the corresponding compact (no delay slot)
1079 // form of the CTI. For indirect jumps this will not require inserting a
1080 // NOP and for branches will hopefully avoid requiring a NOP.
1081 if ((InMicroMipsMode ||
1082 (STI.hasMips32r6() &&
1083 CLOpts.compact_branches != CompactBranchPolicy::Never)) &&
1084 TII->getEquivalentCompactForm(I)) {
1085 I = replaceWithCompactBranch(MBB, Branch: I, DL: I->getDebugLoc());
1086 Changed = true;
1087 continue;
1088 }
1089
1090 // Bundle the NOP to the instruction with the delay slot.
1091 LLVM_DEBUG(dbgs() << DEBUG_TYPE << ": could not fill delay slot for ";
1092 I->dump());
1093 TII->insertNop(MBB, MI: std::next(x: I), DL: I->getDebugLoc());
1094 MIBundleBuilder(MBB, I, std::next(x: I, n: 2));
1095 ++FilledSlots;
1096 Changed = true;
1097 }
1098 return Changed;
1099}
1100
1101/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
1102/// slots in Mips MachineFunctions
1103FunctionPass *llvm::createMipsDelaySlotFillerLegacyPass() {
1104 return new MipsDelaySlotFillerLegacy();
1105}
1106
1107static bool runDelaySlotFillerOnFunction(
1108 MachineFunction &MF,
1109 function_ref<MachineBranchProbabilityInfo &()> GetMBPI) {
1110 bool Changed = false;
1111 for (auto MBB = MF.begin(); MBB != MF.end();) {
1112 auto curMBB = MBB;
1113 MBB++;
1114
1115 Changed |= runOnMachineBasicBlock(
1116 MBB&: *curMBB,
1117 FirstNextMBBInstr: (MBB != MF.end() && !(*MBB).empty()) ? &(*MBB).instr_front() : nullptr,
1118 GetMBPI);
1119 }
1120
1121 // This pass invalidates liveness information when it reorders
1122 // instructions to fill delay slot. Without this, -verify-machineinstrs
1123 // will fail.
1124 if (Changed)
1125 MF.getRegInfo().invalidateLiveness();
1126
1127 return Changed;
1128}
1129
1130bool MipsDelaySlotFillerLegacy::runOnMachineFunction(MachineFunction &MF) {
1131 return runDelaySlotFillerOnFunction(
1132 MF, GetMBPI: [&]() -> MachineBranchProbabilityInfo & {
1133 return getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1134 });
1135}
1136
1137PreservedAnalyses
1138MipsDelaySlotFillerPass::run(MachineFunction &MF,
1139 MachineFunctionAnalysisManager &MFAM) {
1140 MFPropsModifier _(*this, MF);
1141 bool Changed =
1142 runDelaySlotFillerOnFunction(MF, GetMBPI: [&]() -> MachineBranchProbabilityInfo & {
1143 return MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF);
1144 });
1145 if (!Changed)
1146 return PreservedAnalyses::all();
1147 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
1148}
1149