LLVM  13.0.0git
LanaiMemAluCombiner.cpp
Go to the documentation of this file.
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 "LanaiAluCode.h"
26 #include "LanaiTargetMachine.h"
27 #include "llvm/ADT/SmallSet.h"
28 #include "llvm/ADT/Statistic.h"
34 using namespace llvm;
35 
36 #define GET_INSTRMAP_INFO
37 #include "LanaiGenInstrInfo.inc"
38 
39 #define DEBUG_TYPE "lanai-mem-alu-combiner"
40 
41 STATISTIC(NumLdStAluCombined, "Number of memory and ALU instructions combined");
42 
44  "disable-lanai-mem-alu-combiner", llvm::cl::init(false),
45  llvm::cl::desc("Do not combine ALU and memory operators"),
47 
48 namespace llvm {
50 } // namespace llvm
51 
52 namespace {
53 typedef MachineBasicBlock::iterator MbbIterator;
54 typedef MachineFunction::iterator MfIterator;
55 
56 class LanaiMemAluCombiner : public MachineFunctionPass {
57 public:
58  static char ID;
59  explicit LanaiMemAluCombiner() : MachineFunctionPass(ID) {
61  }
62 
63  StringRef getPassName() const override {
64  return "Lanai load / store optimization pass";
65  }
66 
67  bool runOnMachineFunction(MachineFunction &F) override;
68 
69  MachineFunctionProperties getRequiredProperties() const override {
72  }
73 
74 private:
75  MbbIterator findClosestSuitableAluInstr(MachineBasicBlock *BB,
76  const MbbIterator &MemInstr,
77  bool Decrement);
78  void insertMergedInstruction(MachineBasicBlock *BB,
79  const MbbIterator &MemInstr,
80  const MbbIterator &AluInstr, bool Before);
81  bool combineMemAluInBasicBlock(MachineBasicBlock *BB);
82 
83  // Target machine description which we query for register names, data
84  // layout, etc.
85  const TargetInstrInfo *TII;
86 };
87 } // namespace
88 
90 
91 INITIALIZE_PASS(LanaiMemAluCombiner, DEBUG_TYPE,
92  "Lanai memory ALU combiner pass", false, false)
93 
94 namespace {
95 bool isSpls(uint16_t Opcode) { return Lanai::splsIdempotent(Opcode) == Opcode; }
96 
97 // Determine the opcode for the merged instruction created by considering the
98 // old memory operation's opcode and whether the merged opcode will have an
99 // immediate offset.
100 unsigned mergedOpcode(unsigned OldOpcode, bool ImmediateOffset) {
101  switch (OldOpcode) {
102  case Lanai::LDW_RI:
103  case Lanai::LDW_RR:
104  if (ImmediateOffset)
105  return Lanai::LDW_RI;
106  return Lanai::LDW_RR;
107  case Lanai::LDHs_RI:
108  case Lanai::LDHs_RR:
109  if (ImmediateOffset)
110  return Lanai::LDHs_RI;
111  return Lanai::LDHs_RR;
112  case Lanai::LDHz_RI:
113  case Lanai::LDHz_RR:
114  if (ImmediateOffset)
115  return Lanai::LDHz_RI;
116  return Lanai::LDHz_RR;
117  case Lanai::LDBs_RI:
118  case Lanai::LDBs_RR:
119  if (ImmediateOffset)
120  return Lanai::LDBs_RI;
121  return Lanai::LDBs_RR;
122  case Lanai::LDBz_RI:
123  case Lanai::LDBz_RR:
124  if (ImmediateOffset)
125  return Lanai::LDBz_RI;
126  return Lanai::LDBz_RR;
127  case Lanai::SW_RI:
128  case Lanai::SW_RR:
129  if (ImmediateOffset)
130  return Lanai::SW_RI;
131  return Lanai::SW_RR;
132  case Lanai::STB_RI:
133  case Lanai::STB_RR:
134  if (ImmediateOffset)
135  return Lanai::STB_RI;
136  return Lanai::STB_RR;
137  case Lanai::STH_RI:
138  case Lanai::STH_RR:
139  if (ImmediateOffset)
140  return Lanai::STH_RI;
141  return Lanai::STH_RR;
142  default:
143  return 0;
144  }
145 }
146 
147 // Check if the machine instruction has non-volatile memory operands of the type
148 // supported for combining with ALU instructions.
149 bool isNonVolatileMemoryOp(const MachineInstr &MI) {
150  if (!MI.hasOneMemOperand())
151  return false;
152 
153  // Determine if the machine instruction is a supported memory operation by
154  // testing if the computed merge opcode is a valid memory operation opcode.
155  if (mergedOpcode(MI.getOpcode(), false) == 0)
156  return false;
157 
158  const MachineMemOperand *MemOperand = *MI.memoperands_begin();
159 
160  // Don't move volatile memory accesses
161  // TODO: unclear if we need to be as conservative about atomics
162  if (MemOperand->isVolatile() || MemOperand->isAtomic())
163  return false;
164 
165  return true;
166 }
167 
168 // Test to see if two machine operands are of the same type. This test is less
169 // strict than the MachineOperand::isIdenticalTo function.
170 bool isSameOperand(const MachineOperand &Op1, const MachineOperand &Op2) {
171  if (Op1.getType() != Op2.getType())
172  return false;
173 
174  switch (Op1.getType()) {
176  return Op1.getReg() == Op2.getReg();
178  return Op1.getImm() == Op2.getImm();
179  default:
180  return false;
181  }
182 }
183 
184 bool isZeroOperand(const MachineOperand &Op) {
185  return ((Op.isReg() && Op.getReg() == Lanai::R0) ||
186  (Op.isImm() && Op.getImm() == 0));
187 }
188 
189 // Determines whether a register is used by an instruction.
190 bool InstrUsesReg(const MbbIterator &Instr, const MachineOperand *Reg) {
191  for (MachineInstr::const_mop_iterator Mop = Instr->operands_begin();
192  Mop != Instr->operands_end(); ++Mop) {
193  if (isSameOperand(*Mop, *Reg))
194  return true;
195  }
196  return false;
197 }
198 
199 // Converts between machine opcode and AluCode.
200 // Flag using/modifying ALU operations should not be considered for merging and
201 // are omitted from this list.
202 LPAC::AluCode mergedAluCode(unsigned AluOpcode) {
203  switch (AluOpcode) {
204  case Lanai::ADD_I_LO:
205  case Lanai::ADD_R:
206  return LPAC::ADD;
207  case Lanai::SUB_I_LO:
208  case Lanai::SUB_R:
209  return LPAC::SUB;
210  case Lanai::AND_I_LO:
211  case Lanai::AND_R:
212  return LPAC::AND;
213  case Lanai::OR_I_LO:
214  case Lanai::OR_R:
215  return LPAC::OR;
216  case Lanai::XOR_I_LO:
217  case Lanai::XOR_R:
218  return LPAC::XOR;
219  case Lanai::SHL_R:
220  return LPAC::SHL;
221  case Lanai::SRL_R:
222  return LPAC::SRL;
223  case Lanai::SRA_R:
224  return LPAC::SRA;
225  case Lanai::SA_I:
226  case Lanai::SL_I:
227  default:
228  return LPAC::UNKNOWN;
229  }
230 }
231 
232 // Insert a new combined memory and ALU operation instruction.
233 //
234 // This function builds a new machine instruction using the MachineInstrBuilder
235 // class and inserts it before the memory instruction.
236 void LanaiMemAluCombiner::insertMergedInstruction(MachineBasicBlock *BB,
237  const MbbIterator &MemInstr,
238  const MbbIterator &AluInstr,
239  bool Before) {
240  // Insert new combined load/store + alu operation
241  MachineOperand Dest = MemInstr->getOperand(0);
242  MachineOperand Base = MemInstr->getOperand(1);
243  MachineOperand MemOffset = MemInstr->getOperand(2);
244  MachineOperand AluOffset = AluInstr->getOperand(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(AluInstr->getOpcode());
252  unsigned NewOpc = mergedOpcode(MemInstr->getOpcode(), 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, MemInstr, MemInstr->getDebugLoc(), TII->get(NewOpc));
260  InstrBuilder.addReg(Dest.getReg(), getDefRegState(true));
261  InstrBuilder.addReg(Base.getReg(), getKillRegState(true));
262 
263  // Add offset to machine instruction
264  if (AluOffset.isReg())
265  InstrBuilder.addReg(AluOffset.getReg());
266  else if (AluOffset.isImm())
267  InstrBuilder.addImm(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(MemOffset))
275  InstrBuilder.addImm(LPAC::makePreOp(AluOpcode));
276  else
277  InstrBuilder.addImm(LPAC::makePostOp(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.
285 bool 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(0);
293  MachineOperand &Op1 = AluIter->getOperand(1);
294  MachineOperand &Op2 = AluIter->getOperand(2);
295 
296  // Only match instructions using the base register as destination and with the
297  // base and first operand equal
298  if (!isSameOperand(Dest, Base) || !isSameOperand(Dest, 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>(Op2.getImm())) ||
315  (!IsSpls && isInt<16>(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 
329 MbbIterator LanaiMemAluCombiner::findClosestSuitableAluInstr(
330  MachineBasicBlock *BB, const MbbIterator &MemInstr, const bool Decrement) {
331  MachineOperand *Base = &MemInstr->getOperand(1);
332  MachineOperand *Offset = &MemInstr->getOperand(2);
333  bool IsSpls = isSpls(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, First, *Base, *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(First, Base))
355  break;
356  if (Offset->isReg() && InstrUsesReg(First, Offset))
357  break;
358  }
359  }
360 
361  return MemInstr;
362 }
363 
364 bool LanaiMemAluCombiner::combineMemAluInBasicBlock(MachineBasicBlock *BB) {
365  bool Modified = false;
366 
367  MbbIterator MBBIter = BB->begin(), End = BB->end();
368  while (MBBIter != End) {
369  bool IsMemOp = isNonVolatileMemoryOp(*MBBIter);
370 
371  if (IsMemOp) {
372  MachineOperand AluOperand = MBBIter->getOperand(3);
373  unsigned int DestReg = MBBIter->getOperand(0).getReg(),
374  BaseReg = MBBIter->getOperand(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(AluOpcode) && DestReg != BaseReg) {
381  for (int Inc = 0; Inc <= 1; ++Inc) {
382  MbbIterator AluIter =
383  findClosestSuitableAluInstr(BB, MBBIter, Inc == 0);
384  if (AluIter != MBBIter) {
385  insertMergedInstruction(BB, MBBIter, AluIter, Inc == 0);
386 
387  ++NumLdStAluCombined;
388  Modified = true;
389 
390  // Erase the matching ALU instruction
391  BB->erase(AluIter);
392  // Erase old load/store instruction
393  BB->erase(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
409 bool LanaiMemAluCombiner::runOnMachineFunction(MachineFunction &MF) {
411  return false;
412 
413  TII = MF.getSubtarget<LanaiSubtarget>().getInstrInfo();
414  bool Modified = false;
415  for (MfIterator MFI = MF.begin(); MFI != MF.end(); ++MFI) {
416  Modified |= combineMemAluInBasicBlock(&*MFI);
417  }
418  return Modified;
419 }
420 } // namespace
421 
423  return new LanaiMemAluCombiner();
424 }
llvm::LPAC::ADD
@ ADD
Definition: LanaiAluCode.h:23
llvm::LPAC::OR
@ OR
Definition: LanaiAluCode.h:28
LanaiAluCode.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:102
llvm::MachineOperand::MO_Immediate
@ MO_Immediate
Immediate operand.
Definition: MachineOperand.h:53
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LPAC::AluCode
AluCode
Definition: LanaiAluCode.h:22
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:760
llvm::LPAC::modifiesOp
static bool modifiesOp(unsigned AluOp)
Definition: LanaiAluCode.h:72
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::LPAC::SRA
@ SRA
Definition: LanaiAluCode.h:37
TargetInstrInfo.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:127
llvm::LPAC::SHL
@ SHL
Definition: LanaiAluCode.h:35
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::MachineOperand::MO_Register
@ MO_Register
Register operand.
Definition: MachineOperand.h:52
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::LPAC::AND
@ AND
Definition: LanaiAluCode.h:27
CommandLine.h
llvm::getDefRegState
unsigned getDefRegState(bool B)
Definition: MachineInstrBuilder.h:502
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::LPAC::SRL
@ SRL
Definition: LanaiAluCode.h:36
INITIALIZE_PASS
INITIALIZE_PASS(LanaiMemAluCombiner, DEBUG_TYPE, "Lanai memory ALU combiner pass", false, false) namespace
Definition: LanaiMemAluCombiner.cpp:91
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:537
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::LPAC::makePreOp
static unsigned makePreOp(unsigned AluOp)
Definition: LanaiAluCode.h:62
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:169
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
LoopDeletionResult::Modified
@ Modified
llvm::LPAC::XOR
@ XOR
Definition: LanaiAluCode.h:29
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:758
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:576
llvm::LPAC::SUB
@ SUB
Definition: LanaiAluCode.h:25
llvm::cl::opt< bool >
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
llvm::createLanaiMemAluCombinerPass
FunctionPass * createLanaiMemAluCombinerPass()
Definition: LanaiMemAluCombiner.cpp:422
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::MachineOperand::getType
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
Definition: MachineOperand.h:219
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DisableMemAluCombiner
static llvm::cl::opt< bool > DisableMemAluCombiner("disable-lanai-mem-alu-combiner", llvm::cl::init(false), llvm::cl::desc("Do not combine ALU and memory operators"), llvm::cl::Hidden)
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::LPAC::makePostOp
static unsigned makePostOp(unsigned AluOp)
Definition: LanaiAluCode.h:67
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::initializeLanaiMemAluCombinerPass
void initializeLanaiMemAluCombinerPass(PassRegistry &)
llvm::LanaiSubtarget
Definition: LanaiSubtarget.h:29
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LanaiMemAluCombiner.cpp:39
llvm::LPAC::UNKNOWN
@ UNKNOWN
Definition: LanaiAluCode.h:40
llvm::isInt< 16 >
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:370
llvm::MachineMemOperand::isVolatile
bool isVolatile() const
Definition: MachineMemOperand.h:277
uint16_t
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::MachineInstrBuilder::setMemRefs
const MachineInstrBuilder & setMemRefs(ArrayRef< MachineMemOperand * > MMOs) const
Definition: MachineInstrBuilder.h:208
llvm::MachineMemOperand::isAtomic
bool isAtomic() const
Returns true if this operation has an atomic ordering requirement of unordered or higher,...
Definition: MachineMemOperand.h:284
llvm::MachineOperand::isImm
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Definition: MachineOperand.h:323
llvm::getKillRegState
unsigned getKillRegState(bool B)
Definition: MachineInstrBuilder.h:508
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
LanaiTargetMachine.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::cl::desc
Definition: CommandLine.h:414
RegisterScavenging.h
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38