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