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