1//===-- LanaiDelaySlotFiller.cpp - Lanai 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 "Lanai.h"
14#include "LanaiTargetMachine.h"
15#include "llvm/ADT/SmallSet.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/CodeGen/MachineInstrBuilder.h"
20#include "llvm/CodeGen/MachinePassManager.h"
21#include "llvm/CodeGen/TargetInstrInfo.h"
22#include "llvm/IR/Analysis.h"
23#include "llvm/Support/CommandLine.h"
24
25using namespace llvm;
26
27#define DEBUG_TYPE "delay-slot-filler"
28
29STATISTIC(FilledSlots, "Number of delay slots filled");
30
31static cl::opt<bool>
32 NopDelaySlotFiller("lanai-nop-delay-filler", cl::init(Val: false),
33 cl::desc("Fill Lanai delay slots with NOPs."),
34 cl::Hidden);
35
36namespace {
37struct FillerImpl {
38 // Target machine description which we query for reg. names, data
39 // layout, etc.
40 const TargetInstrInfo *TII;
41 const TargetRegisterInfo *TRI;
42 MachineBasicBlock::instr_iterator LastFiller;
43
44 bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
45
46 bool runOnMachineFunction(MachineFunction &MF) {
47 const LanaiSubtarget &Subtarget = MF.getSubtarget<LanaiSubtarget>();
48 TII = Subtarget.getInstrInfo();
49 TRI = Subtarget.getRegisterInfo();
50
51 bool Changed = false;
52 for (MachineBasicBlock &MBB : MF)
53 Changed |= runOnMachineBasicBlock(MBB);
54 return Changed;
55 }
56
57 void insertDefsUses(MachineBasicBlock::instr_iterator MI,
58 SmallSet<unsigned, 32> &RegDefs,
59 SmallSet<unsigned, 32> &RegUses);
60
61 bool isRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg);
62
63 bool delayHasHazard(MachineBasicBlock::instr_iterator MI, bool &SawLoad,
64 bool &SawStore, SmallSet<unsigned, 32> &RegDefs,
65 SmallSet<unsigned, 32> &RegUses);
66
67 bool findDelayInstr(MachineBasicBlock &MBB,
68 MachineBasicBlock::instr_iterator Slot,
69 MachineBasicBlock::instr_iterator &Filler);
70};
71
72class LanaiDelaySlotFillerLegacy : public MachineFunctionPass {
73 static char ID;
74
75public:
76 explicit LanaiDelaySlotFillerLegacy() : MachineFunctionPass(ID) {}
77
78 StringRef getPassName() const override { return "Lanai Delay Slot Filler"; }
79
80 MachineFunctionProperties getRequiredProperties() const override {
81 return MachineFunctionProperties().setNoVRegs();
82 }
83
84 bool runOnMachineFunction(MachineFunction &MF) override;
85};
86char LanaiDelaySlotFillerLegacy::ID = 0;
87} // end of anonymous namespace
88
89// createLanaiDelaySlotFillerPass - Returns a pass that fills in delay
90// slots in Lanai MachineFunctions
91FunctionPass *
92llvm::createLanaiDelaySlotFillerLegacyPass(const LanaiTargetMachine & /*tm*/) {
93 return new LanaiDelaySlotFillerLegacy();
94}
95
96// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
97// There is one or two delay slot per delayed instruction.
98bool FillerImpl::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
99 bool Changed = false;
100 LastFiller = MBB.instr_end();
101
102 for (MachineBasicBlock::instr_iterator I = MBB.instr_begin();
103 I != MBB.instr_end(); ++I) {
104 if (I->getDesc().hasDelaySlot()) {
105 MachineBasicBlock::instr_iterator InstrWithSlot = I;
106 MachineBasicBlock::instr_iterator J = I;
107
108 // Treat RET specially as it is only instruction with 2 delay slots
109 // generated while all others generated have 1 delay slot.
110 if (I->getOpcode() == Lanai::RET) {
111 // RET is generated as part of epilogue generation and hence we know
112 // what the two instructions preceding it are and that it is safe to
113 // insert RET above them.
114 MachineBasicBlock::reverse_instr_iterator RI = ++I.getReverse();
115 assert(RI->getOpcode() == Lanai::LDW_RI && RI->getOperand(0).isReg() &&
116 RI->getOperand(0).getReg() == Lanai::FP &&
117 RI->getOperand(1).isReg() &&
118 RI->getOperand(1).getReg() == Lanai::FP &&
119 RI->getOperand(2).isImm() && RI->getOperand(2).getImm() == -8);
120 ++RI;
121 assert(RI->getOpcode() == Lanai::ADD_I_LO &&
122 RI->getOperand(0).isReg() &&
123 RI->getOperand(0).getReg() == Lanai::SP &&
124 RI->getOperand(1).isReg() &&
125 RI->getOperand(1).getReg() == Lanai::FP);
126 MachineBasicBlock::instr_iterator FI = RI.getReverse();
127 MBB.splice(Where: std::next(x: I), Other: &MBB, From: FI, To: I);
128 FilledSlots += 2;
129 } else {
130 if (!NopDelaySlotFiller && findDelayInstr(MBB, Slot: I, Filler&: J)) {
131 MBB.splice(Where: std::next(x: I), Other: &MBB, From: J);
132 } else {
133 BuildMI(BB&: MBB, I: std::next(x: I), MIMD: DebugLoc(), MCID: TII->get(Opcode: Lanai::NOP));
134 }
135 ++FilledSlots;
136 }
137
138 Changed = true;
139 // Record the filler instruction that filled the delay slot.
140 // The instruction after it will be visited in the next iteration.
141 LastFiller = ++I;
142 // RET has 2 delay slots, so we need to advance past the second filler
143 // too.
144 if (InstrWithSlot->getOpcode() == Lanai::RET)
145 ++LastFiller;
146
147 // Bundle the delay slot filler to InstrWithSlot so that the machine
148 // verifier doesn't expect this instruction to be a terminator.
149 MIBundleBuilder(MBB, InstrWithSlot, std::next(x: LastFiller));
150 }
151 }
152 return Changed;
153}
154
155bool FillerImpl::findDelayInstr(MachineBasicBlock &MBB,
156 MachineBasicBlock::instr_iterator Slot,
157 MachineBasicBlock::instr_iterator &Filler) {
158 SmallSet<unsigned, 32> RegDefs;
159 SmallSet<unsigned, 32> RegUses;
160
161 insertDefsUses(MI: Slot, RegDefs, RegUses);
162
163 bool SawLoad = false;
164 bool SawStore = false;
165
166 for (MachineBasicBlock::reverse_instr_iterator I = ++Slot.getReverse();
167 I != MBB.instr_rend(); ++I) {
168 // skip debug value
169 if (I->isDebugInstr())
170 continue;
171
172 // Convert to forward iterator.
173 MachineBasicBlock::instr_iterator FI = I.getReverse();
174
175 if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isLabel() ||
176 FI == LastFiller || I->isPseudo())
177 break;
178
179 if (delayHasHazard(MI: FI, SawLoad, SawStore, RegDefs, RegUses)) {
180 insertDefsUses(MI: FI, RegDefs, RegUses);
181 continue;
182 }
183 Filler = FI;
184 return true;
185 }
186 return false;
187}
188
189bool FillerImpl::delayHasHazard(MachineBasicBlock::instr_iterator MI,
190 bool &SawLoad, bool &SawStore,
191 SmallSet<unsigned, 32> &RegDefs,
192 SmallSet<unsigned, 32> &RegUses) {
193 if (MI->isImplicitDef() || MI->isKill())
194 return true;
195
196 // Loads or stores cannot be moved past a store to the delay slot
197 // and stores cannot be moved past a load.
198 if (MI->mayLoad()) {
199 if (SawStore)
200 return true;
201 SawLoad = true;
202 }
203
204 if (MI->mayStore()) {
205 if (SawStore)
206 return true;
207 SawStore = true;
208 if (SawLoad)
209 return true;
210 }
211
212 assert((!MI->isCall() && !MI->isReturn()) &&
213 "Cannot put calls or returns in delay slot.");
214
215 for (const MachineOperand &MO : MI->operands()) {
216 unsigned Reg;
217
218 if (!MO.isReg() || !(Reg = MO.getReg()))
219 continue; // skip
220
221 if (MO.isDef()) {
222 // check whether Reg is defined or used before delay slot.
223 if (isRegInSet(RegSet&: RegDefs, Reg) || isRegInSet(RegSet&: RegUses, Reg))
224 return true;
225 }
226 if (MO.isUse()) {
227 // check whether Reg is defined before delay slot.
228 if (isRegInSet(RegSet&: RegDefs, Reg))
229 return true;
230 }
231 }
232 return false;
233}
234
235// Insert Defs and Uses of MI into the sets RegDefs and RegUses.
236void FillerImpl::insertDefsUses(MachineBasicBlock::instr_iterator MI,
237 SmallSet<unsigned, 32> &RegDefs,
238 SmallSet<unsigned, 32> &RegUses) {
239 for (const MachineOperand &MO : MI->operands()) {
240 if (MO.isRegMask()) {
241 // For calls, the regmask clobbers many registers. However, we don't
242 // want to add all of those to RegDefs as it would prevent any useful
243 // delay slot filling. The caller-saved registers will be handled
244 // separately.
245 continue;
246 }
247
248 if (!MO.isReg())
249 continue;
250
251 Register Reg = MO.getReg();
252 if (Reg != MO.getReg())
253 continue;
254
255 // For calls/returns, we must track implicit uses (function arguments)
256 // to prevent moving their definitions into the delay slot. We previously
257 // only looked at explicit operands which missed implicit argument uses.
258 if (MO.isDef()) {
259 // For implicit defs from calls (like return value $rv), we add them.
260 // But we've already filtered out regmasks above.
261 RegDefs.insert(V: Reg);
262 } else if (MO.isUse()) {
263 RegUses.insert(V: Reg);
264 }
265 }
266
267 // Call & return instructions define SP implicitly. Instructions modifying SP
268 // cannot be inserted in the delay slot of a call/return as these instructions
269 // are expanded to multiple instructions with SP modified before the branch
270 // that has the delay slot.
271 if (MI->isCall() || MI->isReturn())
272 RegDefs.insert(V: Lanai::SP);
273}
274
275// Returns true if the Reg or its alias is in the RegSet.
276bool FillerImpl::isRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg) {
277 // Check Reg and all aliased Registers.
278 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
279 if (RegSet.count(V: *AI))
280 return true;
281 return false;
282}
283
284bool LanaiDelaySlotFillerLegacy::runOnMachineFunction(MachineFunction &MF) {
285 FillerImpl Impl;
286 return Impl.runOnMachineFunction(MF);
287}
288
289PreservedAnalyses
290LanaiDelaySlotFillerPass::run(MachineFunction &MF,
291 MachineFunctionAnalysisManager &MFAM) {
292 FillerImpl Impl;
293 return Impl.runOnMachineFunction(MF)
294 ? getMachineFunctionPassPreservedAnalyses()
295 .preserveSet<CFGAnalyses>()
296 : PreservedAnalyses::all();
297}
298