Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/AArch64/AArch64AdvSIMDScalarPass.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- AArch64AdvSIMDScalar.cpp - Replace dead defs w/ zero reg --===//
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
// When profitable, replace GPR targeting i64 instructions with their
9
// AdvSIMD scalar equivalents. Generally speaking, "profitable" is defined
10
// as minimizing the number of cross-class register copies.
11
//===----------------------------------------------------------------------===//
12
13
//===----------------------------------------------------------------------===//
14
// TODO: Graph based predicate heuristics.
15
// Walking the instruction list linearly will get many, perhaps most, of
16
// the cases, but to do a truly thorough job of this, we need a more
17
// wholistic approach.
18
//
19
// This optimization is very similar in spirit to the register allocator's
20
// spill placement, only here we're determining where to place cross-class
21
// register copies rather than spills. As such, a similar approach is
22
// called for.
23
//
24
// We want to build up a set of graphs of all instructions which are candidates
25
// for transformation along with instructions which generate their inputs and
26
// consume their outputs. For each edge in the graph, we assign a weight
27
// based on whether there is a copy required there (weight zero if not) and
28
// the block frequency of the block containing the defining or using
29
// instruction, whichever is less. Our optimization is then a graph problem
30
// to minimize the total weight of all the graphs, then transform instructions
31
// and add or remove copy instructions as called for to implement the
32
// solution.
33
//===----------------------------------------------------------------------===//
34
35
#include "AArch64.h"
36
#include "AArch64InstrInfo.h"
37
#include "AArch64RegisterInfo.h"
38
#include "llvm/ADT/Statistic.h"
39
#include "llvm/CodeGen/MachineFunction.h"
40
#include "llvm/CodeGen/MachineFunctionPass.h"
41
#include "llvm/CodeGen/MachineInstr.h"
42
#include "llvm/CodeGen/MachineInstrBuilder.h"
43
#include "llvm/CodeGen/MachineRegisterInfo.h"
44
#include "llvm/Support/CommandLine.h"
45
#include "llvm/Support/Debug.h"
46
#include "llvm/Support/raw_ostream.h"
47
using namespace llvm;
48
49
#define DEBUG_TYPE "aarch64-simd-scalar"
50
51
// Allow forcing all i64 operations with equivalent SIMD instructions to use
52
// them. For stress-testing the transformation function.
53
static cl::opt<bool>
54
TransformAll("aarch64-simd-scalar-force-all",
55
             cl::desc("Force use of AdvSIMD scalar instructions everywhere"),
56
             cl::init(false), cl::Hidden);
57
58
STATISTIC(NumScalarInsnsUsed, "Number of scalar instructions used");
59
STATISTIC(NumCopiesDeleted, "Number of cross-class copies deleted");
60
STATISTIC(NumCopiesInserted, "Number of cross-class copies inserted");
61
62
68
#define AARCH64_ADVSIMD_NAME "AdvSIMD Scalar Operation Optimization"
63
64
namespace {
65
class AArch64AdvSIMDScalar : public MachineFunctionPass {
66
  MachineRegisterInfo *MRI;
67
  const TargetInstrInfo *TII;
68
69
private:
70
  // isProfitableToTransform - Predicate function to determine whether an
71
  // instruction should be transformed to its equivalent AdvSIMD scalar
72
  // instruction. "add Xd, Xn, Xm" ==> "add Dd, Da, Db", for example.
73
  bool isProfitableToTransform(const MachineInstr &MI) const;
74
75
  // transformInstruction - Perform the transformation of an instruction
76
  // to its equivalant AdvSIMD scalar instruction. Update inputs and outputs
77
  // to be the correct register class, minimizing cross-class copies.
78
  void transformInstruction(MachineInstr &MI);
79
80
  // processMachineBasicBlock - Main optimzation loop.
81
  bool processMachineBasicBlock(MachineBasicBlock *MBB);
82
83
public:
84
  static char ID; // Pass identification, replacement for typeid.
85
5
  explicit AArch64AdvSIMDScalar() : MachineFunctionPass(ID) {
86
5
    initializeAArch64AdvSIMDScalarPass(*PassRegistry::getPassRegistry());
87
5
  }
88
89
  bool runOnMachineFunction(MachineFunction &F) override;
90
91
68
  StringRef getPassName() const override { return AARCH64_ADVSIMD_NAME; }
92
93
5
  void getAnalysisUsage(AnalysisUsage &AU) const override {
94
5
    AU.setPreservesCFG();
95
5
    MachineFunctionPass::getAnalysisUsage(AU);
96
5
  }
97
};
98
char AArch64AdvSIMDScalar::ID = 0;
99
} // end anonymous namespace
100
101
INITIALIZE_PASS(AArch64AdvSIMDScalar, "aarch64-simd-scalar",
102
                AARCH64_ADVSIMD_NAME, false, false)
103
104
static bool isGPR64(unsigned Reg, unsigned SubReg,
105
168
                    const MachineRegisterInfo *MRI) {
106
168
  if (SubReg)
107
0
    return false;
108
168
  if (TargetRegisterInfo::isVirtualRegister(Reg))
109
168
    return MRI->getRegClass(Reg)->hasSuperClassEq(&AArch64::GPR64RegClass);
110
0
  return AArch64::GPR64RegClass.contains(Reg);
111
0
}
112
113
static bool isFPR64(unsigned Reg, unsigned SubReg,
114
312
                    const MachineRegisterInfo *MRI) {
115
312
  if (TargetRegisterInfo::isVirtualRegister(Reg))
116
304
    return (MRI->getRegClass(Reg)->hasSuperClassEq(&AArch64::FPR64RegClass) &&
117
304
            
SubReg == 032
) ||
118
304
           
(272
MRI->getRegClass(Reg)->hasSuperClassEq(&AArch64::FPR128RegClass)272
&&
119
272
            
SubReg == AArch64::dsub128
);
120
8
  // Physical register references just check the register class directly.
121
8
  return (AArch64::FPR64RegClass.contains(Reg) && 
SubReg == 00
) ||
122
8
         (AArch64::FPR128RegClass.contains(Reg) && 
SubReg == AArch64::dsub0
);
123
8
}
124
125
// getSrcFromCopy - Get the original source register for a GPR64 <--> FPR64
126
// copy instruction. Return zero_reg if the instruction is not a copy.
127
static MachineOperand *getSrcFromCopy(MachineInstr *MI,
128
                                      const MachineRegisterInfo *MRI,
129
180
                                      unsigned &SubReg) {
130
180
  SubReg = 0;
131
180
  // The "FMOV Xd, Dn" instruction is the typical form.
132
180
  if (MI->getOpcode() == AArch64::FMOVDXr ||
133
180
      MI->getOpcode() == AArch64::FMOVXDr)
134
0
    return &MI->getOperand(1);
135
180
  // A lane zero extract "UMOV.d Xd, Vn[0]" is equivalent. We shouldn't see
136
180
  // these at this stage, but it's easy to check for.
137
180
  if (MI->getOpcode() == AArch64::UMOVvi64 && 
MI->getOperand(2).getImm() == 00
) {
138
0
    SubReg = AArch64::dsub;
139
0
    return &MI->getOperand(1);
140
0
  }
141
180
  // Or just a plain COPY instruction. This can be directly to/from FPR64,
142
180
  // or it can be a dsub subreg reference to an FPR128.
143
180
  if (MI->getOpcode() == AArch64::COPY) {
144
168
    if (isFPR64(MI->getOperand(0).getReg(), MI->getOperand(0).getSubReg(),
145
168
                MRI) &&
146
168
        
isGPR64(MI->getOperand(1).getReg(), MI->getOperand(1).getSubReg(), MRI)24
)
147
24
      return &MI->getOperand(1);
148
144
    if (isGPR64(MI->getOperand(0).getReg(), MI->getOperand(0).getSubReg(),
149
144
                MRI) &&
150
144
        isFPR64(MI->getOperand(1).getReg(), MI->getOperand(1).getSubReg(),
151
144
                MRI)) {
152
136
      SubReg = MI->getOperand(1).getSubReg();
153
136
      return &MI->getOperand(1);
154
136
    }
155
20
  }
156
20
157
20
  // Otherwise, this is some other kind of instruction.
158
20
  return nullptr;
159
20
}
160
161
// getTransformOpcode - For any opcode for which there is an AdvSIMD equivalent
162
// that we're considering transforming to, return that AdvSIMD opcode. For all
163
// others, return the original opcode.
164
475
static unsigned getTransformOpcode(unsigned Opc) {
165
475
  switch (Opc) {
166
475
  default:
167
399
    break;
168
475
  // FIXME: Lots more possibilities.
169
475
  case AArch64::ADDXrr:
170
24
    return AArch64::ADDv1i64;
171
475
  case AArch64::SUBXrr:
172
28
    return AArch64::SUBv1i64;
173
475
  case AArch64::ANDXrr:
174
8
    return AArch64::ANDv8i8;
175
475
  case AArch64::EORXrr:
176
8
    return AArch64::EORv8i8;
177
475
  case AArch64::ORRXrr:
178
8
    return AArch64::ORRv8i8;
179
399
  }
180
399
  // No AdvSIMD equivalent, so just return the original opcode.
181
399
  return Opc;
182
399
}
183
184
439
static bool isTransformable(const MachineInstr &MI) {
185
439
  unsigned Opc = MI.getOpcode();
186
439
  return Opc != getTransformOpcode(Opc);
187
439
}
188
189
// isProfitableToTransform - Predicate function to determine whether an
190
// instruction should be transformed to its equivalent AdvSIMD scalar
191
// instruction. "add Xd, Xn, Xm" ==> "add Dd, Da, Db", for example.
192
bool AArch64AdvSIMDScalar::isProfitableToTransform(
193
427
    const MachineInstr &MI) const {
194
427
  // If this instruction isn't eligible to be transformed (no SIMD equivalent),
195
427
  // early exit since that's the common case.
196
427
  if (!isTransformable(MI))
197
391
    return false;
198
36
199
36
  // Count the number of copies we'll need to add and approximate the number
200
36
  // of copies that a transform will enable us to remove.
201
36
  unsigned NumNewCopies = 3;
202
36
  unsigned NumRemovableCopies = 0;
203
36
204
36
  unsigned OrigSrc0 = MI.getOperand(1).getReg();
205
36
  unsigned OrigSrc1 = MI.getOperand(2).getReg();
206
36
  unsigned SubReg0;
207
36
  unsigned SubReg1;
208
36
  if (!MRI->def_empty(OrigSrc0)) {
209
36
    MachineRegisterInfo::def_instr_iterator Def =
210
36
        MRI->def_instr_begin(OrigSrc0);
211
36
    assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
212
36
    MachineOperand *MOSrc0 = getSrcFromCopy(&*Def, MRI, SubReg0);
213
36
    // If the source was from a copy, we don't need to insert a new copy.
214
36
    if (MOSrc0)
215
32
      --NumNewCopies;
216
36
    // If there are no other users of the original source, we can delete
217
36
    // that instruction.
218
36
    if (MOSrc0 && 
MRI->hasOneNonDBGUse(OrigSrc0)32
)
219
28
      ++NumRemovableCopies;
220
36
  }
221
36
  if (!MRI->def_empty(OrigSrc1)) {
222
36
    MachineRegisterInfo::def_instr_iterator Def =
223
36
        MRI->def_instr_begin(OrigSrc1);
224
36
    assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
225
36
    MachineOperand *MOSrc1 = getSrcFromCopy(&*Def, MRI, SubReg1);
226
36
    if (MOSrc1)
227
36
      --NumNewCopies;
228
36
    // If there are no other users of the original source, we can delete
229
36
    // that instruction.
230
36
    if (MOSrc1 && MRI->hasOneNonDBGUse(OrigSrc1))
231
32
      ++NumRemovableCopies;
232
36
  }
233
36
234
36
  // If any of the uses of the original instructions is a cross class copy,
235
36
  // that's a copy that will be removable if we transform. Likewise, if
236
36
  // any of the uses is a transformable instruction, it's likely the tranforms
237
36
  // will chain, enabling us to save a copy there, too. This is an aggressive
238
36
  // heuristic that approximates the graph based cost analysis described above.
239
36
  unsigned Dst = MI.getOperand(0).getReg();
240
36
  bool AllUsesAreCopies = true;
241
36
  for (MachineRegisterInfo::use_instr_nodbg_iterator
242
36
           Use = MRI->use_instr_nodbg_begin(Dst),
243
36
           E = MRI->use_instr_nodbg_end();
244
72
       Use != E; 
++Use36
) {
245
36
    unsigned SubReg;
246
36
    if (getSrcFromCopy(&*Use, MRI, SubReg) || 
isTransformable(*Use)12
)
247
28
      ++NumRemovableCopies;
248
8
    // If the use is an INSERT_SUBREG, that's still something that can
249
8
    // directly use the FPR64, so we don't invalidate AllUsesAreCopies. It's
250
8
    // preferable to have it use the FPR64 in most cases, as if the source
251
8
    // vector is an IMPLICIT_DEF, the INSERT_SUBREG just goes away entirely.
252
8
    // Ditto for a lane insert.
253
8
    else if (Use->getOpcode() == AArch64::INSERT_SUBREG ||
254
8
             
Use->getOpcode() == AArch64::INSvi64gpr4
)
255
8
      ;
256
0
    else
257
0
      AllUsesAreCopies = false;
258
36
  }
259
36
  // If all of the uses of the original destination register are copies to
260
36
  // FPR64, then we won't end up having a new copy back to GPR64 either.
261
36
  if (AllUsesAreCopies)
262
36
    --NumNewCopies;
263
36
264
36
  // If a transform will not increase the number of cross-class copies required,
265
36
  // return true.
266
36
  if (NumNewCopies <= NumRemovableCopies)
267
36
    return true;
268
0
269
0
  // Finally, even if we otherwise wouldn't transform, check if we're forcing
270
0
  // transformation of everything.
271
0
  return TransformAll;
272
0
}
273
274
static MachineInstr *insertCopy(const TargetInstrInfo *TII, MachineInstr &MI,
275
40
                                unsigned Dst, unsigned Src, bool IsKill) {
276
40
  MachineInstrBuilder MIB = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
277
40
                                    TII->get(AArch64::COPY), Dst)
278
40
                                .addReg(Src, getKillRegState(IsKill));
279
40
  LLVM_DEBUG(dbgs() << "    adding copy: " << *MIB);
280
40
  ++NumCopiesInserted;
281
40
  return MIB;
282
40
}
283
284
// transformInstruction - Perform the transformation of an instruction
285
// to its equivalant AdvSIMD scalar instruction. Update inputs and outputs
286
// to be the correct register class, minimizing cross-class copies.
287
36
void AArch64AdvSIMDScalar::transformInstruction(MachineInstr &MI) {
288
36
  LLVM_DEBUG(dbgs() << "Scalar transform: " << MI);
289
36
290
36
  MachineBasicBlock *MBB = MI.getParent();
291
36
  unsigned OldOpc = MI.getOpcode();
292
36
  unsigned NewOpc = getTransformOpcode(OldOpc);
293
36
  assert(OldOpc != NewOpc && "transform an instruction to itself?!");
294
36
295
36
  // Check if we need a copy for the source registers.
296
36
  unsigned OrigSrc0 = MI.getOperand(1).getReg();
297
36
  unsigned OrigSrc1 = MI.getOperand(2).getReg();
298
36
  unsigned Src0 = 0, SubReg0;
299
36
  unsigned Src1 = 0, SubReg1;
300
36
  bool KillSrc0 = false, KillSrc1 = false;
301
36
  if (!MRI->def_empty(OrigSrc0)) {
302
36
    MachineRegisterInfo::def_instr_iterator Def =
303
36
        MRI->def_instr_begin(OrigSrc0);
304
36
    assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
305
36
    MachineOperand *MOSrc0 = getSrcFromCopy(&*Def, MRI, SubReg0);
306
36
    // If there are no other users of the original source, we can delete
307
36
    // that instruction.
308
36
    if (MOSrc0) {
309
32
      Src0 = MOSrc0->getReg();
310
32
      KillSrc0 = MOSrc0->isKill();
311
32
      // Src0 is going to be reused, thus, it cannot be killed anymore.
312
32
      MOSrc0->setIsKill(false);
313
32
      if (MRI->hasOneNonDBGUse(OrigSrc0)) {
314
28
        assert(MOSrc0 && "Can't delete copy w/o a valid original source!");
315
28
        Def->eraseFromParent();
316
28
        ++NumCopiesDeleted;
317
28
      }
318
32
    }
319
36
  }
320
36
  if (!MRI->def_empty(OrigSrc1)) {
321
36
    MachineRegisterInfo::def_instr_iterator Def =
322
36
        MRI->def_instr_begin(OrigSrc1);
323
36
    assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
324
36
    MachineOperand *MOSrc1 = getSrcFromCopy(&*Def, MRI, SubReg1);
325
36
    // If there are no other users of the original source, we can delete
326
36
    // that instruction.
327
36
    if (MOSrc1) {
328
36
      Src1 = MOSrc1->getReg();
329
36
      KillSrc1 = MOSrc1->isKill();
330
36
      // Src0 is going to be reused, thus, it cannot be killed anymore.
331
36
      MOSrc1->setIsKill(false);
332
36
      if (MRI->hasOneNonDBGUse(OrigSrc1)) {
333
32
        assert(MOSrc1 && "Can't delete copy w/o a valid original source!");
334
32
        Def->eraseFromParent();
335
32
        ++NumCopiesDeleted;
336
32
      }
337
36
    }
338
36
  }
339
36
  // If we weren't able to reference the original source directly, create a
340
36
  // copy.
341
36
  if (!Src0) {
342
4
    SubReg0 = 0;
343
4
    Src0 = MRI->createVirtualRegister(&AArch64::FPR64RegClass);
344
4
    insertCopy(TII, MI, Src0, OrigSrc0, KillSrc0);
345
4
    KillSrc0 = true;
346
4
  }
347
36
  if (!Src1) {
348
0
    SubReg1 = 0;
349
0
    Src1 = MRI->createVirtualRegister(&AArch64::FPR64RegClass);
350
0
    insertCopy(TII, MI, Src1, OrigSrc1, KillSrc1);
351
0
    KillSrc1 = true;
352
0
  }
353
36
354
36
  // Create a vreg for the destination.
355
36
  // FIXME: No need to do this if the ultimate user expects an FPR64.
356
36
  // Check for that and avoid the copy if possible.
357
36
  unsigned Dst = MRI->createVirtualRegister(&AArch64::FPR64RegClass);
358
36
359
36
  // For now, all of the new instructions have the same simple three-register
360
36
  // form, so no need to special case based on what instruction we're
361
36
  // building.
362
36
  BuildMI(*MBB, MI, MI.getDebugLoc(), TII->get(NewOpc), Dst)
363
36
      .addReg(Src0, getKillRegState(KillSrc0), SubReg0)
364
36
      .addReg(Src1, getKillRegState(KillSrc1), SubReg1);
365
36
366
36
  // Now copy the result back out to a GPR.
367
36
  // FIXME: Try to avoid this if all uses could actually just use the FPR64
368
36
  // directly.
369
36
  insertCopy(TII, MI, MI.getOperand(0).getReg(), Dst, true);
370
36
371
36
  // Erase the old instruction.
372
36
  MI.eraseFromParent();
373
36
374
36
  ++NumScalarInsnsUsed;
375
36
}
376
377
// processMachineBasicBlock - Main optimzation loop.
378
63
bool AArch64AdvSIMDScalar::processMachineBasicBlock(MachineBasicBlock *MBB) {
379
63
  bool Changed = false;
380
490
  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) {
381
427
    MachineInstr &MI = *I++;
382
427
    if (isProfitableToTransform(MI)) {
383
36
      transformInstruction(MI);
384
36
      Changed = true;
385
36
    }
386
427
  }
387
63
  return Changed;
388
63
}
389
390
// runOnMachineFunction - Pass entry point from PassManager.
391
63
bool AArch64AdvSIMDScalar::runOnMachineFunction(MachineFunction &mf) {
392
63
  bool Changed = false;
393
63
  LLVM_DEBUG(dbgs() << "***** AArch64AdvSIMDScalar *****\n");
394
63
395
63
  if (skipFunction(mf.getFunction()))
396
0
    return false;
397
63
398
63
  MRI = &mf.getRegInfo();
399
63
  TII = mf.getSubtarget().getInstrInfo();
400
63
401
63
  // Just check things on a one-block-at-a-time basis.
402
126
  for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; 
++I63
)
403
63
    if (processMachineBasicBlock(&*I))
404
28
      Changed = true;
405
63
  return Changed;
406
63
}
407
408
// createAArch64AdvSIMDScalar - Factory function used by AArch64TargetMachine
409
// to add the pass to the PassManager.
410
5
FunctionPass *llvm::createAArch64AdvSIMDScalar() {
411
5
  return new AArch64AdvSIMDScalar();
412
5
}