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