LLVM  9.0.0svn
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 "Lanai.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  if (MemOperand->isVolatile())
162  return false;
163 
164  return true;
165 }
166 
167 // Test to see if two machine operands are of the same type. This test is less
168 // strict than the MachineOperand::isIdenticalTo function.
169 bool isSameOperand(const MachineOperand &Op1, const MachineOperand &Op2) {
170  if (Op1.getType() != Op2.getType())
171  return false;
172 
173  switch (Op1.getType()) {
175  return Op1.getReg() == Op2.getReg();
177  return Op1.getImm() == Op2.getImm();
178  default:
179  return false;
180  }
181 }
182 
183 bool isZeroOperand(const MachineOperand &Op) {
184  return ((Op.isReg() && Op.getReg() == Lanai::R0) ||
185  (Op.isImm() && Op.getImm() == 0));
186 }
187 
188 // Determines whether a register is used by an instruction.
189 bool InstrUsesReg(const MbbIterator &Instr, const MachineOperand *Reg) {
190  for (MachineInstr::const_mop_iterator Mop = Instr->operands_begin();
191  Mop != Instr->operands_end(); ++Mop) {
192  if (isSameOperand(*Mop, *Reg))
193  return true;
194  }
195  return false;
196 }
197 
198 // Converts between machine opcode and AluCode.
199 // Flag using/modifying ALU operations should not be considered for merging and
200 // are omitted from this list.
201 LPAC::AluCode mergedAluCode(unsigned AluOpcode) {
202  switch (AluOpcode) {
203  case Lanai::ADD_I_LO:
204  case Lanai::ADD_R:
205  return LPAC::ADD;
206  case Lanai::SUB_I_LO:
207  case Lanai::SUB_R:
208  return LPAC::SUB;
209  case Lanai::AND_I_LO:
210  case Lanai::AND_R:
211  return LPAC::AND;
212  case Lanai::OR_I_LO:
213  case Lanai::OR_R:
214  return LPAC::OR;
215  case Lanai::XOR_I_LO:
216  case Lanai::XOR_R:
217  return LPAC::XOR;
218  case Lanai::SHL_R:
219  return LPAC::SHL;
220  case Lanai::SRL_R:
221  return LPAC::SRL;
222  case Lanai::SRA_R:
223  return LPAC::SRA;
224  case Lanai::SA_I:
225  case Lanai::SL_I:
226  default:
227  return LPAC::UNKNOWN;
228  }
229 }
230 
231 // Insert a new combined memory and ALU operation instruction.
232 //
233 // This function builds a new machine instruction using the MachineInstrBuilder
234 // class and inserts it before the memory instruction.
235 void LanaiMemAluCombiner::insertMergedInstruction(MachineBasicBlock *BB,
236  const MbbIterator &MemInstr,
237  const MbbIterator &AluInstr,
238  bool Before) {
239  // Insert new combined load/store + alu operation
240  MachineOperand Dest = MemInstr->getOperand(0);
241  MachineOperand Base = MemInstr->getOperand(1);
242  MachineOperand MemOffset = MemInstr->getOperand(2);
243  MachineOperand AluOffset = AluInstr->getOperand(2);
244 
245  // Abort if ALU offset is not a register or immediate
246  assert((AluOffset.isReg() || AluOffset.isImm()) &&
247  "Unsupported operand type in merge");
248 
249  // Determined merged instructions opcode and ALU code
250  LPAC::AluCode AluOpcode = mergedAluCode(AluInstr->getOpcode());
251  unsigned NewOpc = mergedOpcode(MemInstr->getOpcode(), AluOffset.isImm());
252 
253  assert(AluOpcode != LPAC::UNKNOWN && "Unknown ALU code in merging");
254  assert(NewOpc != 0 && "Unknown merged node opcode");
255 
256  // Build and insert new machine instruction
257  MachineInstrBuilder InstrBuilder =
258  BuildMI(*BB, MemInstr, MemInstr->getDebugLoc(), TII->get(NewOpc));
259  InstrBuilder.addReg(Dest.getReg(), getDefRegState(true));
260  InstrBuilder.addReg(Base.getReg(), getKillRegState(true));
261 
262  // Add offset to machine instruction
263  if (AluOffset.isReg())
264  InstrBuilder.addReg(AluOffset.getReg());
265  else if (AluOffset.isImm())
266  InstrBuilder.addImm(AluOffset.getImm());
267  else
268  llvm_unreachable("Unsupported ld/st ALU merge.");
269 
270  // Create a pre-op if the ALU operation preceded the memory operation or the
271  // MemOffset is non-zero (i.e. the memory value should be adjusted before
272  // accessing it), else create a post-op.
273  if (Before || !isZeroOperand(MemOffset))
274  InstrBuilder.addImm(LPAC::makePreOp(AluOpcode));
275  else
276  InstrBuilder.addImm(LPAC::makePostOp(AluOpcode));
277 
278  // Transfer memory operands.
279  InstrBuilder.setMemRefs(MemInstr->memoperands());
280 }
281 
282 // Function determines if ALU operation (in alu_iter) can be combined with
283 // a load/store with base and offset.
284 bool isSuitableAluInstr(bool IsSpls, const MbbIterator &AluIter,
285  const MachineOperand &Base,
286  const MachineOperand &Offset) {
287  // ALU operations have 3 operands
288  if (AluIter->getNumOperands() != 3)
289  return false;
290 
291  MachineOperand &Dest = AluIter->getOperand(0);
292  MachineOperand &Op1 = AluIter->getOperand(1);
293  MachineOperand &Op2 = AluIter->getOperand(2);
294 
295  // Only match instructions using the base register as destination and with the
296  // base and first operand equal
297  if (!isSameOperand(Dest, Base) || !isSameOperand(Dest, Op1))
298  return false;
299 
300  if (Op2.isImm()) {
301  // It is not a match if the 2nd operand in the ALU operation is an
302  // immediate but the ALU operation is not an addition.
303  if (AluIter->getOpcode() != Lanai::ADD_I_LO)
304  return false;
305 
306  if (Offset.isReg() && Offset.getReg() == Lanai::R0)
307  return true;
308 
309  if (Offset.isImm() &&
310  ((Offset.getImm() == 0 &&
311  // Check that the Op2 would fit in the immediate field of the
312  // memory operation.
313  ((IsSpls && isInt<10>(Op2.getImm())) ||
314  (!IsSpls && isInt<16>(Op2.getImm())))) ||
315  Offset.getImm() == Op2.getImm()))
316  return true;
317  } else if (Op2.isReg()) {
318  // The Offset and 2nd operand are both registers and equal
319  if (Offset.isReg() && Op2.getReg() == Offset.getReg())
320  return true;
321  } else
322  // Only consider operations with register or immediate values
323  return false;
324 
325  return false;
326 }
327 
328 MbbIterator LanaiMemAluCombiner::findClosestSuitableAluInstr(
329  MachineBasicBlock *BB, const MbbIterator &MemInstr, const bool Decrement) {
330  MachineOperand *Base = &MemInstr->getOperand(1);
331  MachineOperand *Offset = &MemInstr->getOperand(2);
332  bool IsSpls = isSpls(MemInstr->getOpcode());
333 
334  MbbIterator First = MemInstr;
335  MbbIterator Last = Decrement ? BB->begin() : BB->end();
336 
337  while (First != Last) {
338  Decrement ? --First : ++First;
339 
340  if (First == Last)
341  break;
342 
343  // Skip over debug instructions
344  if (First->isDebugInstr())
345  continue;
346 
347  if (isSuitableAluInstr(IsSpls, First, *Base, *Offset)) {
348  return First;
349  }
350 
351  // Usage of the base or offset register is not a form suitable for merging.
352  if (First != Last) {
353  if (InstrUsesReg(First, Base))
354  break;
355  if (Offset->isReg() && InstrUsesReg(First, Offset))
356  break;
357  }
358  }
359 
360  return MemInstr;
361 }
362 
363 bool LanaiMemAluCombiner::combineMemAluInBasicBlock(MachineBasicBlock *BB) {
364  bool Modified = false;
365 
366  MbbIterator MBBIter = BB->begin(), End = BB->end();
367  while (MBBIter != End) {
368  bool IsMemOp = isNonVolatileMemoryOp(*MBBIter);
369 
370  if (IsMemOp) {
371  MachineOperand AluOperand = MBBIter->getOperand(3);
372  unsigned int DestReg = MBBIter->getOperand(0).getReg(),
373  BaseReg = MBBIter->getOperand(1).getReg();
374  assert(AluOperand.isImm() && "Unexpected memory operator type");
375  LPAC::AluCode AluOpcode = static_cast<LPAC::AluCode>(AluOperand.getImm());
376 
377  // Skip memory operations that already modify the base register or if
378  // the destination and base register are the same
379  if (!LPAC::modifiesOp(AluOpcode) && DestReg != BaseReg) {
380  for (int Inc = 0; Inc <= 1; ++Inc) {
381  MbbIterator AluIter =
382  findClosestSuitableAluInstr(BB, MBBIter, Inc == 0);
383  if (AluIter != MBBIter) {
384  insertMergedInstruction(BB, MBBIter, AluIter, Inc == 0);
385 
386  ++NumLdStAluCombined;
387  Modified = true;
388 
389  // Erase the matching ALU instruction
390  BB->erase(AluIter);
391  // Erase old load/store instruction
392  BB->erase(MBBIter++);
393  break;
394  }
395  }
396  }
397  }
398  if (MBBIter == End)
399  break;
400  ++MBBIter;
401  }
402 
403  return Modified;
404 }
405 
406 // Driver function that iterates over the machine basic building blocks of a
407 // machine function
408 bool LanaiMemAluCombiner::runOnMachineFunction(MachineFunction &MF) {
410  return false;
411 
412  TII = MF.getSubtarget<LanaiSubtarget>().getInstrInfo();
413  bool Modified = false;
414  for (MfIterator MFI = MF.begin(); MFI != MF.end(); ++MFI) {
415  Modified |= combineMemAluInBasicBlock(&*MFI);
416  }
417  return Modified;
418 }
419 } // namespace
420 
422  return new LanaiMemAluCombiner();
423 }
const MachineInstrBuilder & setMemRefs(ArrayRef< MachineMemOperand *> MMOs) const
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool modifiesOp(unsigned AluOp)
Definition: LanaiAluCode.h:72
void initializeLanaiMemAluCombinerPass(PassRegistry &)
unsigned getReg() const
getReg - Returns the register number.
unsigned Reg
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:305
STATISTIC(NumFunctions, "Total number of functions")
F(f)
INITIALIZE_PASS(LanaiMemAluCombiner, DEBUG_TYPE, "Lanai memory ALU combiner pass", false, false) namespace
FunctionPass * createLanaiMemAluCombinerPass()
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static unsigned makePostOp(unsigned AluOp)
Definition: LanaiAluCode.h:67
A description of a memory reference used in the backend.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
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)
unsigned getKillRegState(bool B)
TargetInstrInfo - Interface to description of machine instruction set.
unsigned getDefRegState(bool B)
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
This file declares the machine register scavenger class.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool hasOneMemOperand() const
Return true if this instruction has exactly one MachineMemOperand.
Definition: MachineInstr.h:548
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:533
MachineOperand class - Representation of each machine instruction operand.
int64_t getImm() const
static unsigned makePreOp(unsigned AluOp)
Definition: LanaiAluCode.h:62
MachineFunctionProperties & set(Property P)
#define DEBUG_TYPE
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
Properties which a MachineFunction may have at a given point in time.