Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Lanai/LanaiMemAluCombiner.cpp
Line
Count
Source (jump to first uncovered line)
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"
29
#include "llvm/CodeGen/MachineFunctionPass.h"
30
#include "llvm/CodeGen/MachineInstrBuilder.h"
31
#include "llvm/CodeGen/RegisterScavenging.h"
32
#include "llvm/CodeGen/TargetInstrInfo.h"
33
#include "llvm/Support/CommandLine.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
43
static llvm::cl::opt<bool> DisableMemAluCombiner(
44
    "disable-lanai-mem-alu-combiner", llvm::cl::init(false),
45
    llvm::cl::desc("Do not combine ALU and memory operators"),
46
    llvm::cl::Hidden);
47
48
namespace llvm {
49
void initializeLanaiMemAluCombinerPass(PassRegistry &);
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
22
  explicit LanaiMemAluCombiner() : MachineFunctionPass(ID) {
60
22
    initializeLanaiMemAluCombinerPass(*PassRegistry::getPassRegistry());
61
22
  }
62
63
114
  StringRef getPassName() const override {
64
114
    return "Lanai load / store optimization pass";
65
114
  }
66
67
  bool runOnMachineFunction(MachineFunction &F) override;
68
69
22
  MachineFunctionProperties getRequiredProperties() const override {
70
22
    return MachineFunctionProperties().set(
71
22
        MachineFunctionProperties::Property::NoVRegs);
72
22
  }
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
89
char LanaiMemAluCombiner::ID = 0;
90
91
INITIALIZE_PASS(LanaiMemAluCombiner, DEBUG_TYPE,
92
                "Lanai memory ALU combiner pass", false, false)
93
94
namespace {
95
128
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
71
unsigned mergedOpcode(unsigned OldOpcode, bool ImmediateOffset) {
101
71
  switch (OldOpcode) {
102
71
  case Lanai::LDW_RI:
103
63
  case Lanai::LDW_RR:
104
63
    if (ImmediateOffset)
105
1
      return Lanai::LDW_RI;
106
62
    return Lanai::LDW_RR;
107
62
  case Lanai::LDHs_RI:
108
0
  case Lanai::LDHs_RR:
109
0
    if (ImmediateOffset)
110
0
      return Lanai::LDHs_RI;
111
0
    return Lanai::LDHs_RR;
112
2
  case Lanai::LDHz_RI:
113
2
  case Lanai::LDHz_RR:
114
2
    if (ImmediateOffset)
115
0
      return Lanai::LDHz_RI;
116
2
    return Lanai::LDHz_RR;
117
2
  case Lanai::LDBs_RI:
118
0
  case Lanai::LDBs_RR:
119
0
    if (ImmediateOffset)
120
0
      return Lanai::LDBs_RI;
121
0
    return Lanai::LDBs_RR;
122
0
  case Lanai::LDBz_RI:
123
0
  case Lanai::LDBz_RR:
124
0
    if (ImmediateOffset)
125
0
      return Lanai::LDBz_RI;
126
0
    return Lanai::LDBz_RR;
127
3
  case Lanai::SW_RI:
128
3
  case Lanai::SW_RR:
129
3
    if (ImmediateOffset)
130
0
      return Lanai::SW_RI;
131
3
    return Lanai::SW_RR;
132
3
  case Lanai::STB_RI:
133
0
  case Lanai::STB_RR:
134
0
    if (ImmediateOffset)
135
0
      return Lanai::STB_RI;
136
0
    return Lanai::STB_RR;
137
2
  case Lanai::STH_RI:
138
2
  case Lanai::STH_RR:
139
2
    if (ImmediateOffset)
140
0
      return Lanai::STH_RI;
141
2
    return Lanai::STH_RR;
142
2
  default:
143
1
    return 0;
144
71
  }
145
71
}
146
147
// Check if the machine instruction has non-volatile memory operands of the type
148
// supported for combining with ALU instructions.
149
895
bool isNonVolatileMemoryOp(const MachineInstr &MI) {
150
895
  if (!MI.hasOneMemOperand())
151
825
    return false;
152
70
153
70
  // Determine if the machine instruction is a supported memory operation by
154
70
  // testing if the computed merge opcode is a valid memory operation opcode.
155
70
  if (mergedOpcode(MI.getOpcode(), false) == 0)
156
1
    return false;
157
69
158
69
  const MachineMemOperand *MemOperand = *MI.memoperands_begin();
159
69
160
69
  // Don't move volatile memory accesses
161
69
  // TODO: unclear if we need to be as conservative about atomics
162
69
  if (MemOperand->isVolatile() || 
MemOperand->isAtomic()68
)
163
1
    return false;
164
68
165
68
  return true;
166
68
}
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
688
bool isSameOperand(const MachineOperand &Op1, const MachineOperand &Op2) {
171
688
  if (Op1.getType() != Op2.getType())
172
99
    return false;
173
589
174
589
  switch (Op1.getType()) {
175
589
  case MachineOperand::MO_Register:
176
589
    return Op1.getReg() == Op2.getReg();
177
589
  case MachineOperand::MO_Immediate:
178
0
    return Op1.getImm() == Op2.getImm();
179
589
  default:
180
0
    return false;
181
589
  }
182
589
}
183
184
1
bool isZeroOperand(const MachineOperand &Op) {
185
1
  return ((Op.isReg() && 
Op.getReg() == Lanai::R00
) ||
186
1
          (Op.isImm() && Op.getImm() == 0));
187
1
}
188
189
// Determines whether a register is used by an instruction.
190
214
bool InstrUsesReg(const MbbIterator &Instr, const MachineOperand *Reg) {
191
214
  for (MachineInstr::const_mop_iterator Mop = Instr->operands_begin();
192
629
       Mop != Instr->operands_end(); 
++Mop415
) {
193
530
    if (isSameOperand(*Mop, *Reg))
194
115
      return true;
195
530
  }
196
214
  
return false99
;
197
214
}
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
1
LPAC::AluCode mergedAluCode(unsigned AluOpcode) {
203
1
  switch (AluOpcode) {
204
1
  case Lanai::ADD_I_LO:
205
1
  case Lanai::ADD_R:
206
1
    return LPAC::ADD;
207
1
  case Lanai::SUB_I_LO:
208
0
  case Lanai::SUB_R:
209
0
    return LPAC::SUB;
210
0
  case Lanai::AND_I_LO:
211
0
  case Lanai::AND_R:
212
0
    return LPAC::AND;
213
0
  case Lanai::OR_I_LO:
214
0
  case Lanai::OR_R:
215
0
    return LPAC::OR;
216
0
  case Lanai::XOR_I_LO:
217
0
  case Lanai::XOR_R:
218
0
    return LPAC::XOR;
219
0
  case Lanai::SHL_R:
220
0
    return LPAC::SHL;
221
0
  case Lanai::SRL_R:
222
0
    return LPAC::SRL;
223
0
  case Lanai::SRA_R:
224
0
    return LPAC::SRA;
225
0
  case Lanai::SA_I:
226
0
  case Lanai::SL_I:
227
0
  default:
228
0
    return LPAC::UNKNOWN;
229
1
  }
230
1
}
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
1
                                                  bool Before) {
240
1
  // Insert new combined load/store + alu operation
241
1
  MachineOperand Dest = MemInstr->getOperand(0);
242
1
  MachineOperand Base = MemInstr->getOperand(1);
243
1
  MachineOperand MemOffset = MemInstr->getOperand(2);
244
1
  MachineOperand AluOffset = AluInstr->getOperand(2);
245
1
246
1
  // Abort if ALU offset is not a register or immediate
247
1
  assert((AluOffset.isReg() || AluOffset.isImm()) &&
248
1
         "Unsupported operand type in merge");
249
1
250
1
  // Determined merged instructions opcode and ALU code
251
1
  LPAC::AluCode AluOpcode = mergedAluCode(AluInstr->getOpcode());
252
1
  unsigned NewOpc = mergedOpcode(MemInstr->getOpcode(), AluOffset.isImm());
253
1
254
1
  assert(AluOpcode != LPAC::UNKNOWN && "Unknown ALU code in merging");
255
1
  assert(NewOpc != 0 && "Unknown merged node opcode");
256
1
257
1
  // Build and insert new machine instruction
258
1
  MachineInstrBuilder InstrBuilder =
259
1
      BuildMI(*BB, MemInstr, MemInstr->getDebugLoc(), TII->get(NewOpc));
260
1
  InstrBuilder.addReg(Dest.getReg(), getDefRegState(true));
261
1
  InstrBuilder.addReg(Base.getReg(), getKillRegState(true));
262
1
263
1
  // Add offset to machine instruction
264
1
  if (AluOffset.isReg())
265
0
    InstrBuilder.addReg(AluOffset.getReg());
266
1
  else if (AluOffset.isImm())
267
1
    InstrBuilder.addImm(AluOffset.getImm());
268
1
  else
269
1
    
llvm_unreachable0
("Unsupported ld/st ALU merge.");
270
1
271
1
  // Create a pre-op if the ALU operation preceded the memory operation or the
272
1
  // MemOffset is non-zero (i.e. the memory value should be adjusted before
273
1
  // accessing it), else create a post-op.
274
1
  if (Before || !isZeroOperand(MemOffset))
275
0
    InstrBuilder.addImm(LPAC::makePreOp(AluOpcode));
276
1
  else
277
1
    InstrBuilder.addImm(LPAC::makePostOp(AluOpcode));
278
1
279
1
  // Transfer memory operands.
280
1
  InstrBuilder.setMemRefs(MemInstr->memoperands());
281
1
}
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
215
                        const MachineOperand &Offset) {
288
215
  // ALU operations have 3 operands
289
215
  if (AluIter->getNumOperands() != 3)
290
89
    return false;
291
126
292
126
  MachineOperand &Dest = AluIter->getOperand(0);
293
126
  MachineOperand &Op1 = AluIter->getOperand(1);
294
126
  MachineOperand &Op2 = AluIter->getOperand(2);
295
126
296
126
  // Only match instructions using the base register as destination and with the
297
126
  // base and first operand equal
298
126
  if (!isSameOperand(Dest, Base) || 
!isSameOperand(Dest, Op1)32
)
299
123
    return false;
300
3
301
3
  if (Op2.isImm()) {
302
1
    // It is not a match if the 2nd operand in the ALU operation is an
303
1
    // immediate but the ALU operation is not an addition.
304
1
    if (AluIter->getOpcode() != Lanai::ADD_I_LO)
305
0
      return false;
306
1
307
1
    if (Offset.isReg() && 
Offset.getReg() == Lanai::R00
)
308
0
      return true;
309
1
310
1
    if (Offset.isImm() &&
311
1
        ((Offset.getImm() == 0 &&
312
1
          // Check that the Op2 would fit in the immediate field of the
313
1
          // memory operation.
314
1
          ((IsSpls && 
isInt<10>(Op2.getImm())0
) ||
315
1
           (!IsSpls && isInt<16>(Op2.getImm())))) ||
316
1
         
Offset.getImm() == Op2.getImm()0
))
317
1
      return true;
318
2
  } else if (Op2.isReg()) {
319
0
    // The Offset and 2nd operand are both registers and equal
320
0
    if (Offset.isReg() && Op2.getReg() == Offset.getReg())
321
0
      return true;
322
2
  } else
323
2
    // Only consider operations with register or immediate values
324
2
    return false;
325
0
326
0
  return false;
327
0
}
328
329
MbbIterator LanaiMemAluCombiner::findClosestSuitableAluInstr(
330
128
    MachineBasicBlock *BB, const MbbIterator &MemInstr, const bool Decrement) {
331
128
  MachineOperand *Base = &MemInstr->getOperand(1);
332
128
  MachineOperand *Offset = &MemInstr->getOperand(2);
333
128
  bool IsSpls = isSpls(MemInstr->getOpcode());
334
128
335
128
  MbbIterator First = MemInstr;
336
128
  MbbIterator Last = Decrement ? 
BB->begin()64
:
BB->end()64
;
337
128
338
227
  while (First != Last) {
339
224
    Decrement ? 
--First94
:
++First130
;
340
224
341
224
    if (First == Last)
342
9
      break;
343
215
344
215
    // Skip over debug instructions
345
215
    if (First->isDebugInstr())
346
0
      continue;
347
215
348
215
    if (isSuitableAluInstr(IsSpls, First, *Base, *Offset)) {
349
1
      return First;
350
1
    }
351
214
352
214
    // Usage of the base or offset register is not a form suitable for merging.
353
214
    if (First != Last) {
354
214
      if (InstrUsesReg(First, Base))
355
115
        break;
356
99
      if (Offset->isReg() && 
InstrUsesReg(First, Offset)0
)
357
0
        break;
358
99
    }
359
214
  }
360
128
361
128
  
return MemInstr127
;
362
128
}
363
364
116
bool LanaiMemAluCombiner::combineMemAluInBasicBlock(MachineBasicBlock *BB) {
365
116
  bool Modified = false;
366
116
367
116
  MbbIterator MBBIter = BB->begin(), End = BB->end();
368
1.01k
  while (MBBIter != End) {
369
895
    bool IsMemOp = isNonVolatileMemoryOp(*MBBIter);
370
895
371
895
    if (IsMemOp) {
372
68
      MachineOperand AluOperand = MBBIter->getOperand(3);
373
68
      unsigned int DestReg = MBBIter->getOperand(0).getReg(),
374
68
                   BaseReg = MBBIter->getOperand(1).getReg();
375
68
      assert(AluOperand.isImm() && "Unexpected memory operator type");
376
68
      LPAC::AluCode AluOpcode = static_cast<LPAC::AluCode>(AluOperand.getImm());
377
68
378
68
      // Skip memory operations that already modify the base register or if
379
68
      // the destination and base register are the same
380
68
      if (!LPAC::modifiesOp(AluOpcode) && DestReg != BaseReg) {
381
191
        for (int Inc = 0; Inc <= 1; 
++Inc127
) {
382
128
          MbbIterator AluIter =
383
128
              findClosestSuitableAluInstr(BB, MBBIter, Inc == 0);
384
128
          if (AluIter != MBBIter) {
385
1
            insertMergedInstruction(BB, MBBIter, AluIter, Inc == 0);
386
1
387
1
            ++NumLdStAluCombined;
388
1
            Modified = true;
389
1
390
1
            // Erase the matching ALU instruction
391
1
            BB->erase(AluIter);
392
1
            // Erase old load/store instruction
393
1
            BB->erase(MBBIter++);
394
1
            break;
395
1
          }
396
128
        }
397
64
      }
398
68
    }
399
895
    if (MBBIter == End)
400
0
      break;
401
895
    ++MBBIter;
402
895
  }
403
116
404
116
  return Modified;
405
116
}
406
407
// Driver function that iterates over the machine basic building blocks of a
408
// machine function
409
92
bool LanaiMemAluCombiner::runOnMachineFunction(MachineFunction &MF) {
410
92
  if (DisableMemAluCombiner)
411
1
    return false;
412
91
413
91
  TII = MF.getSubtarget<LanaiSubtarget>().getInstrInfo();
414
91
  bool Modified = false;
415
207
  for (MfIterator MFI = MF.begin(); MFI != MF.end(); 
++MFI116
) {
416
116
    Modified |= combineMemAluInBasicBlock(&*MFI);
417
116
  }
418
91
  return Modified;
419
91
}
420
} // namespace
421
422
22
FunctionPass *llvm::createLanaiMemAluCombinerPass() {
423
22
  return new LanaiMemAluCombiner();
424
22
}