1//===-- LanaiMemAluCombiner.cpp - Pass to combine memory & ALU operations -===//
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// Simple pass to combine memory and ALU operations
9//
10// The Lanai ISA supports instructions where a load/store modifies the base
11// register used in the load/store operation. This pass finds suitable
12// load/store and ALU instructions and combines them into one instruction.
13//
14// For example,
15// ld [ %r6 -- ], %r12
16// is a supported instruction that is not currently generated by the instruction
17// selection pass of this backend. This pass generates these instructions by
18// merging
19// add %r6, -4, %r6
20// followed by
21// ld [ %r6 ], %r12
22// in the same machine basic block into one machine instruction.
23//===----------------------------------------------------------------------===//
24
25#include "Lanai.h"
26#include "LanaiAluCode.h"
27#include "LanaiTargetMachine.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstrBuilder.h"
32#include "llvm/CodeGen/MachinePassManager.h"
33#include "llvm/CodeGen/RegisterScavenging.h"
34#include "llvm/CodeGen/TargetInstrInfo.h"
35#include "llvm/IR/Analysis.h"
36#include "llvm/Support/CommandLine.h"
37using namespace llvm;
38
39#define GET_INSTRMAP_INFO
40#include "LanaiGenInstrInfo.inc"
41
42#define DEBUG_TYPE "lanai-mem-alu-combiner"
43
44STATISTIC(NumLdStAluCombined, "Number of memory and ALU instructions combined");
45
46static llvm::cl::opt<bool> DisableMemAluCombiner(
47 "disable-lanai-mem-alu-combiner", llvm::cl::init(Val: false),
48 llvm::cl::desc("Do not combine ALU and memory operators"),
49 llvm::cl::Hidden);
50
51namespace {
52typedef MachineBasicBlock::iterator MbbIterator;
53typedef MachineFunction::iterator MfIterator;
54
55class LanaiMemAluCombinerImpl {
56public:
57 bool runOnMachineFunction(MachineFunction &MF);
58
59private:
60 MbbIterator findClosestSuitableAluInstr(MachineBasicBlock *BB,
61 const MbbIterator &MemInstr,
62 bool Decrement);
63 void insertMergedInstruction(MachineBasicBlock *BB,
64 const MbbIterator &MemInstr,
65 const MbbIterator &AluInstr, bool Before);
66 bool combineMemAluInBasicBlock(MachineBasicBlock *BB);
67
68 // Target machine description which we query for register names, data
69 // layout, etc.
70 const TargetInstrInfo *TII;
71};
72
73class LanaiMemAluCombinerLegacy : public MachineFunctionPass {
74public:
75 static char ID;
76 explicit LanaiMemAluCombinerLegacy() : MachineFunctionPass(ID) {}
77
78 StringRef getPassName() const override {
79 return "Lanai load / store optimization pass";
80 }
81
82 MachineFunctionProperties getRequiredProperties() const override {
83 return MachineFunctionProperties().setNoVRegs();
84 }
85
86 bool runOnMachineFunction(MachineFunction &MF) override;
87};
88} // namespace
89
90char LanaiMemAluCombinerLegacy::ID = 0;
91
92INITIALIZE_PASS(LanaiMemAluCombinerLegacy, DEBUG_TYPE,
93 "Lanai memory ALU combiner pass", false, false)
94
95namespace {
96bool isSpls(uint16_t Opcode) { return Lanai::splsIdempotent(Opcode) == Opcode; }
97
98// Determine the opcode for the merged instruction created by considering the
99// old memory operation's opcode and whether the merged opcode will have an
100// immediate offset.
101unsigned mergedOpcode(unsigned OldOpcode, bool ImmediateOffset) {
102 switch (OldOpcode) {
103 case Lanai::LDW_RI:
104 case Lanai::LDW_RR:
105 if (ImmediateOffset)
106 return Lanai::LDW_RI;
107 return Lanai::LDW_RR;
108 case Lanai::LDHs_RI:
109 case Lanai::LDHs_RR:
110 if (ImmediateOffset)
111 return Lanai::LDHs_RI;
112 return Lanai::LDHs_RR;
113 case Lanai::LDHz_RI:
114 case Lanai::LDHz_RR:
115 if (ImmediateOffset)
116 return Lanai::LDHz_RI;
117 return Lanai::LDHz_RR;
118 case Lanai::LDBs_RI:
119 case Lanai::LDBs_RR:
120 if (ImmediateOffset)
121 return Lanai::LDBs_RI;
122 return Lanai::LDBs_RR;
123 case Lanai::LDBz_RI:
124 case Lanai::LDBz_RR:
125 if (ImmediateOffset)
126 return Lanai::LDBz_RI;
127 return Lanai::LDBz_RR;
128 case Lanai::SW_RI:
129 case Lanai::SW_RR:
130 if (ImmediateOffset)
131 return Lanai::SW_RI;
132 return Lanai::SW_RR;
133 case Lanai::STB_RI:
134 case Lanai::STB_RR:
135 if (ImmediateOffset)
136 return Lanai::STB_RI;
137 return Lanai::STB_RR;
138 case Lanai::STH_RI:
139 case Lanai::STH_RR:
140 if (ImmediateOffset)
141 return Lanai::STH_RI;
142 return Lanai::STH_RR;
143 default:
144 return 0;
145 }
146}
147
148// Check if the machine instruction has non-volatile memory operands of the type
149// supported for combining with ALU instructions.
150bool isNonVolatileMemoryOp(const MachineInstr &MI) {
151 if (!MI.hasOneMemOperand())
152 return false;
153
154 // Determine if the machine instruction is a supported memory operation by
155 // testing if the computed merge opcode is a valid memory operation opcode.
156 if (mergedOpcode(OldOpcode: MI.getOpcode(), ImmediateOffset: false) == 0)
157 return false;
158
159 const MachineMemOperand *MemOperand = *MI.memoperands_begin();
160
161 // Don't move volatile memory accesses
162 // TODO: unclear if we need to be as conservative about atomics
163 if (MemOperand->isVolatile() || MemOperand->isAtomic())
164 return false;
165
166 return true;
167}
168
169// Test to see if two machine operands are of the same type. This test is less
170// strict than the MachineOperand::isIdenticalTo function.
171bool isSameOperand(const MachineOperand &Op1, const MachineOperand &Op2) {
172 if (Op1.getType() != Op2.getType())
173 return false;
174
175 switch (Op1.getType()) {
176 case MachineOperand::MO_Register:
177 return Op1.getReg() == Op2.getReg();
178 case MachineOperand::MO_Immediate:
179 return Op1.getImm() == Op2.getImm();
180 default:
181 return false;
182 }
183}
184
185bool isZeroOperand(const MachineOperand &Op) {
186 return ((Op.isReg() && Op.getReg() == Lanai::R0) ||
187 (Op.isImm() && Op.getImm() == 0));
188}
189
190// Determines whether a register is used by an instruction.
191bool InstrUsesReg(const MbbIterator &Instr, const MachineOperand *Reg) {
192 for (MachineInstr::const_mop_iterator Mop = Instr->operands_begin();
193 Mop != Instr->operands_end(); ++Mop) {
194 if (isSameOperand(Op1: *Mop, Op2: *Reg))
195 return true;
196 }
197 return false;
198}
199
200// Converts between machine opcode and AluCode.
201// Flag using/modifying ALU operations should not be considered for merging and
202// are omitted from this list.
203LPAC::AluCode mergedAluCode(unsigned AluOpcode) {
204 switch (AluOpcode) {
205 case Lanai::ADD_I_LO:
206 case Lanai::ADD_R:
207 return LPAC::ADD;
208 case Lanai::SUB_I_LO:
209 case Lanai::SUB_R:
210 return LPAC::SUB;
211 case Lanai::AND_I_LO:
212 case Lanai::AND_R:
213 return LPAC::AND;
214 case Lanai::OR_I_LO:
215 case Lanai::OR_R:
216 return LPAC::OR;
217 case Lanai::XOR_I_LO:
218 case Lanai::XOR_R:
219 return LPAC::XOR;
220 case Lanai::SHL_R:
221 return LPAC::SHL;
222 case Lanai::SRL_R:
223 return LPAC::SRL;
224 case Lanai::SRA_R:
225 return LPAC::SRA;
226 case Lanai::SA_I:
227 case Lanai::SL_I:
228 default:
229 return LPAC::UNKNOWN;
230 }
231}
232
233// Insert a new combined memory and ALU operation instruction.
234//
235// This function builds a new machine instruction using the MachineInstrBuilder
236// class and inserts it before the memory instruction.
237void LanaiMemAluCombinerImpl::insertMergedInstruction(
238 MachineBasicBlock *BB, const MbbIterator &MemInstr,
239 const MbbIterator &AluInstr, bool Before) {
240 // Insert new combined load/store + alu operation
241 MachineOperand Dest = MemInstr->getOperand(i: 0);
242 MachineOperand Base = MemInstr->getOperand(i: 1);
243 MachineOperand MemOffset = MemInstr->getOperand(i: 2);
244 MachineOperand AluOffset = AluInstr->getOperand(i: 2);
245
246 // Abort if ALU offset is not a register or immediate
247 assert((AluOffset.isReg() || AluOffset.isImm()) &&
248 "Unsupported operand type in merge");
249
250 // Determined merged instructions opcode and ALU code
251 LPAC::AluCode AluOpcode = mergedAluCode(AluOpcode: AluInstr->getOpcode());
252 unsigned NewOpc = mergedOpcode(OldOpcode: MemInstr->getOpcode(), ImmediateOffset: AluOffset.isImm());
253
254 assert(AluOpcode != LPAC::UNKNOWN && "Unknown ALU code in merging");
255 assert(NewOpc != 0 && "Unknown merged node opcode");
256
257 // Build and insert new machine instruction
258 MachineInstrBuilder InstrBuilder =
259 BuildMI(BB&: *BB, I: MemInstr, MIMD: MemInstr->getDebugLoc(), MCID: TII->get(Opcode: NewOpc));
260 InstrBuilder.addReg(RegNo: Dest.getReg(), Flags: getDefRegState(B: true));
261 InstrBuilder.addReg(RegNo: Base.getReg(), Flags: getKillRegState(B: true));
262
263 // Add offset to machine instruction
264 if (AluOffset.isReg())
265 InstrBuilder.addReg(RegNo: AluOffset.getReg());
266 else if (AluOffset.isImm())
267 InstrBuilder.addImm(Val: AluOffset.getImm());
268 else
269 llvm_unreachable("Unsupported ld/st ALU merge.");
270
271 // Create a pre-op if the ALU operation preceded the memory operation or the
272 // MemOffset is non-zero (i.e. the memory value should be adjusted before
273 // accessing it), else create a post-op.
274 if (Before || !isZeroOperand(Op: MemOffset))
275 InstrBuilder.addImm(Val: LPAC::makePreOp(AluOp: AluOpcode));
276 else
277 InstrBuilder.addImm(Val: LPAC::makePostOp(AluOp: AluOpcode));
278
279 // Transfer memory operands.
280 InstrBuilder.setMemRefs(MemInstr->memoperands());
281}
282
283// Function determines if ALU operation (in alu_iter) can be combined with
284// a load/store with base and offset.
285bool isSuitableAluInstr(bool IsSpls, const MbbIterator &AluIter,
286 const MachineOperand &Base,
287 const MachineOperand &Offset) {
288 // ALU operations have 3 operands
289 if (AluIter->getNumOperands() != 3)
290 return false;
291
292 MachineOperand &Dest = AluIter->getOperand(i: 0);
293 MachineOperand &Op1 = AluIter->getOperand(i: 1);
294 MachineOperand &Op2 = AluIter->getOperand(i: 2);
295
296 // Only match instructions using the base register as destination and with the
297 // base and first operand equal
298 if (!isSameOperand(Op1: Dest, Op2: Base) || !isSameOperand(Op1: Dest, Op2: Op1))
299 return false;
300
301 if (Op2.isImm()) {
302 // It is not a match if the 2nd operand in the ALU operation is an
303 // immediate but the ALU operation is not an addition.
304 if (AluIter->getOpcode() != Lanai::ADD_I_LO)
305 return false;
306
307 if (Offset.isReg() && Offset.getReg() == Lanai::R0)
308 return true;
309
310 if (Offset.isImm() &&
311 ((Offset.getImm() == 0 &&
312 // Check that the Op2 would fit in the immediate field of the
313 // memory operation.
314 ((IsSpls && isInt<10>(x: Op2.getImm())) ||
315 (!IsSpls && isInt<16>(x: Op2.getImm())))) ||
316 Offset.getImm() == Op2.getImm()))
317 return true;
318 } else if (Op2.isReg()) {
319 // The Offset and 2nd operand are both registers and equal
320 if (Offset.isReg() && Op2.getReg() == Offset.getReg())
321 return true;
322 } else
323 // Only consider operations with register or immediate values
324 return false;
325
326 return false;
327}
328
329MbbIterator LanaiMemAluCombinerImpl::findClosestSuitableAluInstr(
330 MachineBasicBlock *BB, const MbbIterator &MemInstr, const bool Decrement) {
331 MachineOperand *Base = &MemInstr->getOperand(i: 1);
332 MachineOperand *Offset = &MemInstr->getOperand(i: 2);
333 bool IsSpls = isSpls(Opcode: MemInstr->getOpcode());
334
335 MbbIterator First = MemInstr;
336 MbbIterator Last = Decrement ? BB->begin() : BB->end();
337
338 while (First != Last) {
339 Decrement ? --First : ++First;
340
341 if (First == Last)
342 break;
343
344 // Skip over debug instructions
345 if (First->isDebugInstr())
346 continue;
347
348 if (isSuitableAluInstr(IsSpls, AluIter: First, Base: *Base, Offset: *Offset)) {
349 return First;
350 }
351
352 // Usage of the base or offset register is not a form suitable for merging.
353 if (First != Last) {
354 if (InstrUsesReg(Instr: First, Reg: Base))
355 break;
356 if (Offset->isReg() && InstrUsesReg(Instr: First, Reg: Offset))
357 break;
358 }
359 }
360
361 return MemInstr;
362}
363
364bool LanaiMemAluCombinerImpl::combineMemAluInBasicBlock(MachineBasicBlock *BB) {
365 bool Modified = false;
366
367 MbbIterator MBBIter = BB->begin(), End = BB->end();
368 while (MBBIter != End) {
369 bool IsMemOp = isNonVolatileMemoryOp(MI: *MBBIter);
370
371 if (IsMemOp) {
372 MachineOperand AluOperand = MBBIter->getOperand(i: 3);
373 unsigned int DestReg = MBBIter->getOperand(i: 0).getReg(),
374 BaseReg = MBBIter->getOperand(i: 1).getReg();
375 assert(AluOperand.isImm() && "Unexpected memory operator type");
376 LPAC::AluCode AluOpcode = static_cast<LPAC::AluCode>(AluOperand.getImm());
377
378 // Skip memory operations that already modify the base register or if
379 // the destination and base register are the same
380 if (!LPAC::modifiesOp(AluOp: AluOpcode) && DestReg != BaseReg) {
381 for (int Inc = 0; Inc <= 1; ++Inc) {
382 MbbIterator AluIter =
383 findClosestSuitableAluInstr(BB, MemInstr: MBBIter, Decrement: Inc == 0);
384 if (AluIter != MBBIter) {
385 insertMergedInstruction(BB, MemInstr: MBBIter, AluInstr: AluIter, Before: Inc == 0);
386
387 ++NumLdStAluCombined;
388 Modified = true;
389
390 // Erase the matching ALU instruction
391 BB->erase(I: AluIter);
392 // Erase old load/store instruction
393 BB->erase(I: MBBIter++);
394 break;
395 }
396 }
397 }
398 }
399 if (MBBIter == End)
400 break;
401 ++MBBIter;
402 }
403
404 return Modified;
405}
406
407// Driver function that iterates over the machine basic building blocks of a
408// machine function
409bool LanaiMemAluCombinerImpl::runOnMachineFunction(MachineFunction &MF) {
410 if (DisableMemAluCombiner)
411 return false;
412
413 TII = MF.getSubtarget<LanaiSubtarget>().getInstrInfo();
414 bool Modified = false;
415 for (MachineBasicBlock &MBB : MF)
416 Modified |= combineMemAluInBasicBlock(BB: &MBB);
417 return Modified;
418}
419} // namespace
420
421FunctionPass *llvm::createLanaiMemAluCombinerLegacyPass() {
422 return new LanaiMemAluCombinerLegacy();
423}
424
425bool LanaiMemAluCombinerLegacy::runOnMachineFunction(MachineFunction &MF) {
426 LanaiMemAluCombinerImpl Impl;
427 return Impl.runOnMachineFunction(MF);
428}
429
430PreservedAnalyses
431LanaiMemAluCombinerPass::run(MachineFunction &MF,
432 MachineFunctionAnalysisManager &MFAM) {
433 LanaiMemAluCombinerImpl Impl;
434 return Impl.runOnMachineFunction(MF)
435 ? getMachineFunctionPassPreservedAnalyses()
436 .preserveSet<CFGAnalyses>()
437 : PreservedAnalyses::all();
438}
439