LLVM 19.0.0git
MipsDelaySlotFiller.cpp
Go to the documentation of this file.
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
14#include "Mips.h"
15#include "MipsInstrInfo.h"
16#include "MipsRegisterInfo.h"
17#include "MipsSubtarget.h"
18#include "llvm/ADT/BitVector.h"
19#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/ADT/StringRef.h"
38#include "llvm/MC/MCInstrDesc.h"
45#include <algorithm>
46#include <cassert>
47#include <iterator>
48#include <memory>
49#include <utility>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "mips-delay-slot-filler"
54
55STATISTIC(FilledSlots, "Number of delay slots filled");
56STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
57 " are not NOP.");
58
60 "disable-mips-delay-filler",
61 cl::init(false),
62 cl::desc("Fill all delay slots with NOPs."),
64
66 "disable-mips-df-forward-search",
67 cl::init(true),
68 cl::desc("Disallow MIPS delay filler to search forward."),
70
72 "disable-mips-df-succbb-search",
73 cl::init(true),
74 cl::desc("Disallow MIPS delay filler to search successor basic blocks."),
76
78 "disable-mips-df-backward-search",
79 cl::init(false),
80 cl::desc("Disallow MIPS delay filler to search backward."),
82
84 CB_Never, ///< The policy 'never' may in some circumstances or for some
85 ///< ISAs not be absolutely adhered to.
86 CB_Optimal, ///< Optimal is the default and will produce compact branches
87 ///< when delay slots cannot be filled.
88 CB_Always ///< 'always' may in some circumstances may not be
89 ///< absolutely adhered to there may not be a corresponding
90 ///< compact form of a branch.
91};
92
94 "mips-compact-branches", cl::Optional, cl::init(CB_Optimal),
95 cl::desc("MIPS Specific: Compact branch policy."),
97 "Do not use compact branches if possible."),
98 clEnumValN(CB_Optimal, "optimal",
99 "Use compact branches where appropriate (default)."),
100 clEnumValN(CB_Always, "always",
101 "Always use compact branches if possible.")));
102
103namespace {
104
105 using Iter = MachineBasicBlock::iterator;
106 using ReverseIter = MachineBasicBlock::reverse_iterator;
108
109 class RegDefsUses {
110 public:
111 RegDefsUses(const TargetRegisterInfo &TRI);
112
113 void init(const MachineInstr &MI);
114
115 /// This function sets all caller-saved registers in Defs.
116 void setCallerSaved(const MachineInstr &MI);
117
118 /// This function sets all unallocatable registers in Defs.
119 void setUnallocatableRegs(const MachineFunction &MF);
120
121 /// Set bits in Uses corresponding to MBB's live-out registers except for
122 /// the registers that are live-in to SuccBB.
123 void addLiveOut(const MachineBasicBlock &MBB,
124 const MachineBasicBlock &SuccBB);
125
126 bool update(const MachineInstr &MI, unsigned Begin, unsigned End);
127
128 private:
129 bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg,
130 bool IsDef) const;
131
132 /// Returns true if Reg or its alias is in RegSet.
133 bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;
134
135 const TargetRegisterInfo &TRI;
136 BitVector Defs, Uses;
137 };
138
139 /// Base class for inspecting loads and stores.
140 class InspectMemInstr {
141 public:
142 InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {}
143 virtual ~InspectMemInstr() = default;
144
145 /// Return true if MI cannot be moved to delay slot.
146 bool hasHazard(const MachineInstr &MI);
147
148 protected:
149 /// Flags indicating whether loads or stores have been seen.
150 bool OrigSeenLoad = false;
151 bool OrigSeenStore = false;
152 bool SeenLoad = false;
153 bool SeenStore = false;
154
155 /// Memory instructions are not allowed to move to delay slot if this flag
156 /// is true.
157 bool ForbidMemInstr;
158
159 private:
160 virtual bool hasHazard_(const MachineInstr &MI) = 0;
161 };
162
163 /// This subclass rejects any memory instructions.
164 class NoMemInstr : public InspectMemInstr {
165 public:
166 NoMemInstr() : InspectMemInstr(true) {}
167
168 private:
169 bool hasHazard_(const MachineInstr &MI) override { return true; }
170 };
171
172 /// This subclass accepts loads from stacks and constant loads.
173 class LoadFromStackOrConst : public InspectMemInstr {
174 public:
175 LoadFromStackOrConst() : InspectMemInstr(false) {}
176
177 private:
178 bool hasHazard_(const MachineInstr &MI) override;
179 };
180
181 /// This subclass uses memory dependence information to determine whether a
182 /// memory instruction can be moved to a delay slot.
183 class MemDefsUses : public InspectMemInstr {
184 public:
185 explicit MemDefsUses(const MachineFrameInfo *MFI);
186
187 private:
189
190 bool hasHazard_(const MachineInstr &MI) override;
191
192 /// Update Defs and Uses. Return true if there exist dependences that
193 /// disqualify the delay slot candidate between V and values in Uses and
194 /// Defs.
195 bool updateDefsUses(ValueType V, bool MayStore);
196
197 /// Get the list of underlying objects of MI's memory operand.
199 SmallVectorImpl<ValueType> &Objects) const;
200
201 const MachineFrameInfo *MFI;
203
204 /// Flags indicating whether loads or stores with no underlying objects have
205 /// been seen.
206 bool SeenNoObjLoad = false;
207 bool SeenNoObjStore = false;
208 };
209
210 class MipsDelaySlotFiller : public MachineFunctionPass {
211 public:
212 MipsDelaySlotFiller() : MachineFunctionPass(ID) {
214 }
215
216 StringRef getPassName() const override { return "Mips Delay Slot Filler"; }
217
218 bool runOnMachineFunction(MachineFunction &F) override {
219 TM = &F.getTarget();
220 bool Changed = false;
221 for (MachineBasicBlock &MBB : F)
222 Changed |= runOnMachineBasicBlock(MBB);
223
224 // This pass invalidates liveness information when it reorders
225 // instructions to fill delay slot. Without this, -verify-machineinstrs
226 // will fail.
227 if (Changed)
228 F.getRegInfo().invalidateLiveness();
229
230 return Changed;
231 }
232
235 MachineFunctionProperties::Property::NoVRegs);
236 }
237
238 void getAnalysisUsage(AnalysisUsage &AU) const override {
241 }
242
243 static char ID;
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
297} // end anonymous namespace
298
299char MipsDelaySlotFiller::ID = 0;
300
301static bool hasUnoccupiedSlot(const MachineInstr *MI) {
302 return MI->hasDelaySlot() && !MI->isBundledWithSucc();
303}
304
305INITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE,
306 "Fill delay slot for MIPS", false, false)
307
308/// This function inserts clones of Filler into predecessor blocks.
309static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {
310 MachineFunction *MF = Filler->getParent()->getParent();
311
312 for (const auto &I : BrMap) {
313 if (I.second) {
314 MIBundleBuilder(I.second).append(MF->CloneMachineInstr(&*Filler));
315 ++UsefulSlots;
316 } else {
317 I.first->push_back(MF->CloneMachineInstr(&*Filler));
318 }
319 }
320}
321
322/// This function adds registers Filler defines to MBB's live-in register list.
323static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {
324 for (const MachineOperand &MO : Filler->operands()) {
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
342RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)
343 : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {}
344
345void 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
362void 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
387void 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
400void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
401 const MachineBasicBlock &SuccBB) {
402 for (const MachineBasicBlock *S : MBB.successors())
403 if (S != &SuccBB)
404 for (const auto &LI : S->liveins())
405 Uses.set(LI.PhysReg);
406}
407
408bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {
409 BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());
410 bool HasHazard = false;
411
412 for (unsigned I = Begin; I != End; ++I) {
413 const MachineOperand &MO = MI.getOperand(I);
414
415 if (MO.isReg() && MO.getReg()) {
416 if (checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef())) {
417 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found register hazard for operand "
418 << I << ": ";
419 MO.dump());
420 HasHazard = true;
421 }
422 }
423 }
424
425 Defs |= NewDefs;
426 Uses |= NewUses;
427
428 return HasHazard;
429}
430
431bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
432 unsigned Reg, bool IsDef) const {
433 if (IsDef) {
434 NewDefs.set(Reg);
435 // check whether Reg has already been defined or used.
436 return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg));
437 }
438
439 NewUses.set(Reg);
440 // check whether Reg has already been defined.
441 return isRegInSet(Defs, Reg);
442}
443
444bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const {
445 // Check Reg and all aliased Registers.
446 for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
447 if (RegSet.test(*AI))
448 return true;
449 return false;
450}
451
452bool InspectMemInstr::hasHazard(const MachineInstr &MI) {
453 if (!MI.mayStore() && !MI.mayLoad())
454 return false;
455
456 if (ForbidMemInstr)
457 return true;
458
459 OrigSeenLoad = SeenLoad;
460 OrigSeenStore = SeenStore;
461 SeenLoad |= MI.mayLoad();
462 SeenStore |= MI.mayStore();
463
464 // If MI is an ordered or volatile memory reference, disallow moving
465 // subsequent loads and stores to delay slot.
466 if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) {
467 ForbidMemInstr = true;
468 return true;
469 }
470
471 return hasHazard_(MI);
472}
473
474bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) {
475 if (MI.mayStore())
476 return true;
477
478 if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue())
479 return true;
480
481 if (const PseudoSourceValue *PSV =
482 (*MI.memoperands_begin())->getPseudoValue()) {
483 if (isa<FixedStackPseudoSourceValue>(PSV))
484 return false;
485 return !PSV->isConstant(nullptr) && !PSV->isStack();
486 }
487
488 return true;
489}
490
491MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_)
492 : InspectMemInstr(false), MFI(MFI_) {}
493
494bool MemDefsUses::hasHazard_(const MachineInstr &MI) {
495 bool HasHazard = false;
496
497 // Check underlying object list.
499 if (getUnderlyingObjects(MI, Objs)) {
500 for (ValueType VT : Objs)
501 HasHazard |= updateDefsUses(VT, MI.mayStore());
502 return HasHazard;
503 }
504
505 // No underlying objects found.
506 HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore);
507 HasHazard |= MI.mayLoad() || OrigSeenStore;
508
509 SeenNoObjLoad |= MI.mayLoad();
510 SeenNoObjStore |= MI.mayStore();
511
512 return HasHazard;
513}
514
515bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {
516 if (MayStore)
517 return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore ||
518 SeenNoObjLoad;
519
520 Uses.insert(V);
521 return Defs.count(V) || SeenNoObjStore;
522}
523
524bool MemDefsUses::
525getUnderlyingObjects(const MachineInstr &MI,
526 SmallVectorImpl<ValueType> &Objects) const {
527 if (!MI.hasOneMemOperand())
528 return false;
529
530 auto & MMO = **MI.memoperands_begin();
531
532 if (const PseudoSourceValue *PSV = MMO.getPseudoValue()) {
533 if (!PSV->isAliased(MFI))
534 return false;
535 Objects.push_back(PSV);
536 return true;
537 }
538
539 if (const Value *V = MMO.getValue()) {
541 ::getUnderlyingObjects(V, Objs);
542
543 for (const Value *UValue : Objs) {
544 if (!isIdentifiedObject(V))
545 return false;
546
547 Objects.push_back(UValue);
548 }
549 return true;
550 }
551
552 return false;
553}
554
555// Replace Branch with the compact branch instruction.
556Iter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB,
557 Iter Branch,
558 const DebugLoc &DL) {
560 const MipsInstrInfo *TII = STI.getInstrInfo();
561
562 unsigned NewOpcode = TII->getEquivalentCompactForm(Branch);
563 Branch = TII->genInstrWithNewOpc(NewOpcode, Branch);
564
565 auto *ToErase = cast<MachineInstr>(&*std::next(Branch));
566 // Update call site info for the Branch.
567 if (ToErase->shouldUpdateCallSiteInfo())
568 ToErase->getMF()->moveCallSiteInfo(ToErase, cast<MachineInstr>(&*Branch));
569 ToErase->eraseFromParent();
570 return Branch;
571}
572
573// For given opcode returns opcode of corresponding instruction with short
574// delay slot.
575// For the pseudo TAILCALL*_MM instructions return the short delay slot
576// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range
577// that is too short to make use of for tail calls.
578static int getEquivalentCallShort(int Opcode) {
579 switch (Opcode) {
580 case Mips::BGEZAL:
581 return Mips::BGEZALS_MM;
582 case Mips::BLTZAL:
583 return Mips::BLTZALS_MM;
584 case Mips::JAL:
585 case Mips::JAL_MM:
586 return Mips::JALS_MM;
587 case Mips::JALR:
588 return Mips::JALRS_MM;
589 case Mips::JALR16_MM:
590 return Mips::JALRS16_MM;
591 case Mips::TAILCALL_MM:
592 llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!");
593 case Mips::TAILCALLREG:
594 return Mips::JR16_MM;
595 default:
596 llvm_unreachable("Unexpected call instruction for microMIPS.");
597 }
598}
599
600/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
601/// We assume there is only one delay slot per delayed instruction.
602bool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
603 bool Changed = false;
605 bool InMicroMipsMode = STI.inMicroMipsMode();
606 const MipsInstrInfo *TII = STI.getInstrInfo();
607
608 for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
609 if (!hasUnoccupiedSlot(&*I))
610 continue;
611
612 // Delay slot filling is disabled at -O0, or in microMIPS32R6.
614 (TM->getOptLevel() != CodeGenOptLevel::None) &&
615 !(InMicroMipsMode && STI.hasMips32r6())) {
616
617 bool Filled = false;
618
619 if (MipsCompactBranchPolicy.getValue() != CB_Always ||
620 !TII->getEquivalentCompactForm(I)) {
621 if (searchBackward(MBB, *I)) {
622 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"
623 " in backwards search.\n");
624 Filled = true;
625 } else if (I->isTerminator()) {
626 if (searchSuccBBs(MBB, I)) {
627 Filled = true;
628 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"
629 " in successor BB search.\n");
630 }
631 } else if (searchForward(MBB, I)) {
632 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"
633 " in forwards search.\n");
634 Filled = true;
635 }
636 }
637
638 if (Filled) {
639 // Get instruction with delay slot.
640 MachineBasicBlock::instr_iterator DSI = I.getInstrIterator();
641
642 if (InMicroMipsMode && TII->getInstSizeInBytes(*std::next(DSI)) == 2 &&
643 DSI->isCall()) {
644 // If instruction in delay slot is 16b change opcode to
645 // corresponding instruction with short delay slot.
646
647 // TODO: Implement an instruction mapping table of 16bit opcodes to
648 // 32bit opcodes so that an instruction can be expanded. This would
649 // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop.
650 // TODO: Permit b16 when branching backwards to the same function
651 // if it is in range.
652 DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode())));
653 }
654 ++FilledSlots;
655 Changed = true;
656 continue;
657 }
658 }
659
660 // For microMIPS if instruction is BEQ or BNE with one ZERO register, then
661 // instead of adding NOP replace this instruction with the corresponding
662 // compact branch instruction, i.e. BEQZC or BNEZC. Additionally
663 // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can
664 // be replaced with JRC16_MM.
665
666 // For MIPSR6 attempt to produce the corresponding compact (no delay slot)
667 // form of the CTI. For indirect jumps this will not require inserting a
668 // NOP and for branches will hopefully avoid requiring a NOP.
669 if ((InMicroMipsMode ||
671 TII->getEquivalentCompactForm(I)) {
672 I = replaceWithCompactBranch(MBB, I, I->getDebugLoc());
673 Changed = true;
674 continue;
675 }
676
677 // Bundle the NOP to the instruction with the delay slot.
678 LLVM_DEBUG(dbgs() << DEBUG_TYPE << ": could not fill delay slot for ";
679 I->dump());
680 TII->insertNop(MBB, std::next(I), I->getDebugLoc());
681 MIBundleBuilder(MBB, I, std::next(I, 2));
682 ++FilledSlots;
683 Changed = true;
684 }
685
686 return Changed;
687}
688
689template <typename IterTy>
690bool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin,
691 IterTy End, RegDefsUses &RegDU,
692 InspectMemInstr &IM, Iter Slot,
693 IterTy &Filler) const {
694 for (IterTy I = Begin; I != End;) {
695 IterTy CurrI = I;
696 ++I;
697 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": checking instruction: "; CurrI->dump());
698 // skip debug value
699 if (CurrI->isDebugInstr()) {
700 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring debug instruction: ";
701 CurrI->dump());
702 continue;
703 }
704
705 if (CurrI->isBundle()) {
706 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring BUNDLE instruction: ";
707 CurrI->dump());
708 // However, we still need to update the register def-use information.
709 RegDU.update(*CurrI, 0, CurrI->getNumOperands());
710 continue;
711 }
712
713 if (terminateSearch(*CurrI)) {
714 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": should terminate search: ";
715 CurrI->dump());
716 break;
717 }
718
719 assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&
720 "Cannot put calls, returns or branches in delay slot.");
721
722 if (CurrI->isKill()) {
723 CurrI->eraseFromParent();
724 continue;
725 }
726
727 if (delayHasHazard(*CurrI, RegDU, IM))
728 continue;
729
731 if (STI.isTargetNaCl()) {
732 // In NaCl, instructions that must be masked are forbidden in delay slots.
733 // We only check for loads, stores and SP changes. Calls, returns and
734 // branches are not checked because non-NaCl targets never put them in
735 // delay slots.
736 unsigned AddrIdx;
737 if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) &&
738 baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) ||
739 CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo()))
740 continue;
741 }
742
743 bool InMicroMipsMode = STI.inMicroMipsMode();
744 const MipsInstrInfo *TII = STI.getInstrInfo();
745 unsigned Opcode = (*Slot).getOpcode();
746 // This is complicated by the tail call optimization. For non-PIC code
747 // there is only a 32bit sized unconditional branch which can be assumed
748 // to be able to reach the target. b16 only has a range of +/- 1 KB.
749 // It's entirely possible that the target function is reachable with b16
750 // but we don't have enough information to make that decision.
751 if (InMicroMipsMode && TII->getInstSizeInBytes(*CurrI) == 2 &&
752 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||
753 Opcode == Mips::PseudoIndirectBranch_MM ||
754 Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))
755 continue;
756 // Instructions LWP/SWP and MOVEP should not be in a delay slot as that
757 // results in unpredictable behaviour
758 if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM ||
759 Opcode == Mips::MOVEP_MM))
760 continue;
761
762 Filler = CurrI;
763 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot: ";
764 CurrI->dump());
765
766 return true;
767 }
768
769 return false;
770}
771
772bool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB,
773 MachineInstr &Slot) const {
775 return false;
776
777 auto *Fn = MBB.getParent();
778 RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());
779 MemDefsUses MemDU(&Fn->getFrameInfo());
780 ReverseIter Filler;
781
782 RegDU.init(Slot);
783
785 if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot,
786 Filler)) {
787 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay "
788 "slot using backwards search.\n");
789 return false;
790 }
791
792 MBB.splice(std::next(SlotI), &MBB, Filler.getReverse());
793 MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2));
794 ++UsefulSlots;
795 return true;
796}
797
798bool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB,
799 Iter Slot) const {
800 // Can handle only calls.
801 if (DisableForwardSearch || !Slot->isCall())
802 return false;
803
804 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
805 NoMemInstr NM;
806 Iter Filler;
807
808 RegDU.setCallerSaved(*Slot);
809
810 if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler)) {
811 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay "
812 "slot using forwards search.\n");
813 return false;
814 }
815
816 MBB.splice(std::next(Slot), &MBB, Filler);
817 MIBundleBuilder(MBB, Slot, std::next(Slot, 2));
818 ++UsefulSlots;
819 return true;
820}
821
822bool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB,
823 Iter Slot) const {
825 return false;
826
827 MachineBasicBlock *SuccBB = selectSuccBB(MBB);
828
829 if (!SuccBB)
830 return false;
831
832 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());
833 bool HasMultipleSuccs = false;
834 BB2BrMap BrMap;
835 std::unique_ptr<InspectMemInstr> IM;
836 Iter Filler;
837 auto *Fn = MBB.getParent();
838
839 // Iterate over SuccBB's predecessor list.
840 for (MachineBasicBlock *Pred : SuccBB->predecessors())
841 if (!examinePred(*Pred, *SuccBB, RegDU, HasMultipleSuccs, BrMap))
842 return false;
843
844 // Do not allow moving instructions which have unallocatable register operands
845 // across basic block boundaries.
846 RegDU.setUnallocatableRegs(*Fn);
847
848 // Only allow moving loads from stack or constants if any of the SuccBB's
849 // predecessors have multiple successors.
850 if (HasMultipleSuccs) {
851 IM.reset(new LoadFromStackOrConst());
852 } else {
853 const MachineFrameInfo &MFI = Fn->getFrameInfo();
854 IM.reset(new MemDefsUses(&MFI));
855 }
856
857 if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot,
858 Filler))
859 return false;
860
861 insertDelayFiller(Filler, BrMap);
862 addLiveInRegs(Filler, *SuccBB);
863 Filler->eraseFromParent();
864
865 return true;
866}
867
869MipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const {
870 if (B.succ_empty())
871 return nullptr;
872
873 // Select the successor with the larget edge weight.
874 auto &Prob = getAnalysis<MachineBranchProbabilityInfo>();
875 MachineBasicBlock *S = *std::max_element(
876 B.succ_begin(), B.succ_end(),
877 [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) {
878 return Prob.getEdgeProbability(&B, Dst0) <
879 Prob.getEdgeProbability(&B, Dst1);
880 });
881 return S->isEHPad() ? nullptr : S;
882}
883
884std::pair<MipsInstrInfo::BranchType, MachineInstr *>
885MipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB,
886 const MachineBasicBlock &Dst) const {
887 const MipsInstrInfo *TII =
888 MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();
889 MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;
892
894 TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs);
895
897 return std::make_pair(R, nullptr);
898
900 if (!hasUnoccupiedSlot(BranchInstrs[0]))
901 return std::make_pair(MipsInstrInfo::BT_None, nullptr);
902
903 assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));
904
905 return std::make_pair(R, BranchInstrs[0]);
906 }
907
908 assert((TrueBB == &Dst) || (FalseBB == &Dst));
909
910 // Examine the conditional branch. See if its slot is occupied.
911 if (hasUnoccupiedSlot(BranchInstrs[0]))
912 return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]);
913
914 // If that fails, try the unconditional branch.
915 if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst))
916 return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]);
917
918 return std::make_pair(MipsInstrInfo::BT_None, nullptr);
919}
920
921bool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred,
922 const MachineBasicBlock &Succ,
923 RegDefsUses &RegDU,
924 bool &HasMultipleSuccs,
925 BB2BrMap &BrMap) const {
926 std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =
927 getBranch(Pred, Succ);
928
929 // Return if either getBranch wasn't able to analyze the branches or there
930 // were no branches with unoccupied slots.
931 if (P.first == MipsInstrInfo::BT_None)
932 return false;
933
934 if ((P.first != MipsInstrInfo::BT_Uncond) &&
935 (P.first != MipsInstrInfo::BT_NoBranch)) {
936 HasMultipleSuccs = true;
937 RegDU.addLiveOut(Pred, Succ);
938 }
939
940 BrMap[&Pred] = P.second;
941 return true;
942}
943
944bool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate,
945 RegDefsUses &RegDU,
946 InspectMemInstr &IM) const {
947 assert(!Candidate.isKill() &&
948 "KILL instructions should have been eliminated at this point.");
949
950 bool HasHazard = Candidate.isImplicitDef();
951
952 HasHazard |= IM.hasHazard(Candidate);
953 HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());
954
955 return HasHazard;
956}
957
958bool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const {
959 return (Candidate.isTerminator() || Candidate.isCall() ||
960 Candidate.isPosition() || Candidate.isInlineAsm() ||
961 Candidate.hasUnmodeledSideEffects());
962}
963
964/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
965/// slots in Mips MachineFunctions
967 return new MipsDelaySlotFiller();
968}
aarch64 promote const
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
basic Basic Alias true
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:693
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
bool End
Definition: ELF_riscv.cpp:480
static bool hasHazard(StateT State, function_ref< HazardFnResult(StateT &, const MachineInstr &)> IsHazard, function_ref< void(StateT &, const MachineInstr &)> UpdateState, const MachineBasicBlock *MBB, MachineBasicBlock::const_reverse_instr_iterator I, DenseSet< const MachineBasicBlock * > &Visited)
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
static bool hasUnoccupiedSlot(const MachineInstr *MI)
static cl::opt< bool > DisableDelaySlotFiller("disable-mips-delay-filler", cl::init(false), cl::desc("Fill all delay slots with NOPs."), cl::Hidden)
static cl::opt< bool > DisableBackwardSearch("disable-mips-df-backward-search", cl::init(false), cl::desc("Disallow MIPS delay filler to search backward."), cl::Hidden)
static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB)
This function adds registers Filler defines to MBB's live-in register list.
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)
const BB2BrMap & BrMap
static cl::opt< bool > DisableForwardSearch("disable-mips-df-forward-search", cl::init(true), cl::desc("Disallow MIPS delay filler to search forward."), cl::Hidden)
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 appropriate (default)."), clEnumValN(CB_Always, "always", "Always use compact branches if possible.")))
CompactBranchPolicy
@ CB_Never
The policy 'never' may in some circumstances or for some ISAs not be absolutely adhered to.
@ CB_Optimal
Optimal is the default and will produce compact branches when delay slots cannot be filled.
@ CB_Always
'always' may in some circumstances may not be absolutely adhered to there may not be a corresponding ...
static int getEquivalentCallShort(int Opcode)
#define DEBUG_TYPE
#define P(N)
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file defines the PointerUnion class, which is a discriminated union of pointer types.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & set()
Definition: BitVector.h:351
BitVector & flip()
Definition: BitVector.h:431
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:140
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
MCRegAliasIterator enumerates all registers aliasing Reg.
Helper class for constructing bundles of MachineInstrs.
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
bool isEHPad() const
Returns true if the block is a landing pad.
reverse_iterator rend()
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Instructions::iterator instr_iterator
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
void reset()
Reset the instance as if it was just created.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
Definition: MachineInstr.h:69
bool isPosition() const
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:940
bool isImplicitDef() const
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:916
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:547
bool isInlineAsm() const
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
bool isKill() const
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
bool hasMips32r6() const
bool inMicroMipsMode() const
const MipsInstrInfo * getInstrInfo() const override
const MipsRegisterInfo * getRegisterInfo() const override
bool isTargetNaCl() const
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Special value supplied for machine level alias analysis.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:76
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
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.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
LLVM Value Representation.
Definition: Value.h:74
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:718
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isBasePlusOffsetMemoryAccess(unsigned Opcode, unsigned *AddrIdx, bool *IsStore=nullptr)
void initializeMipsDelaySlotFillerPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool baseRegNeedsLoadStoreMask(unsigned Reg)
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
FunctionPass * createMipsDelaySlotFillerPass()
createMipsDelaySlotFillerPass - Returns a pass that fills in delay slots in Mips MachineFunctions
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.