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"
47using 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.
53static cl::opt<bool>
54TransformAll("aarch64-simd-scalar-force-all",
55 cl::desc("Force use of AdvSIMD scalar instructions everywhere"),
56 cl::init(Val: false), cl::Hidden);
57
58STATISTIC(NumScalarInsnsUsed, "Number of scalar instructions used");
59STATISTIC(NumCopiesDeleted, "Number of cross-class copies deleted");
60STATISTIC(NumCopiesInserted, "Number of cross-class copies inserted");
61
62#define AARCH64_ADVSIMD_NAME "AdvSIMD Scalar Operation Optimization"
63
64namespace {
65class AArch64AdvSIMDScalarImpl {
66public:
67 bool run(MachineFunction &MF);
68
69private:
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 equivalent 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 optimization loop.
81 bool processMachineBasicBlock(MachineBasicBlock *MBB);
82
83 MachineRegisterInfo *MRI;
84 const TargetInstrInfo *TII;
85};
86
87class AArch64AdvSIMDScalarLegacy : public MachineFunctionPass {
88public:
89 static char ID; // Pass identification, replacement for typeid.
90 explicit AArch64AdvSIMDScalarLegacy() : MachineFunctionPass(ID) {}
91
92 bool runOnMachineFunction(MachineFunction &F) override;
93
94 StringRef getPassName() const override { return AARCH64_ADVSIMD_NAME; }
95
96 void getAnalysisUsage(AnalysisUsage &AU) const override {
97 AU.setPreservesCFG();
98 MachineFunctionPass::getAnalysisUsage(AU);
99 }
100};
101char AArch64AdvSIMDScalarLegacy::ID = 0;
102} // end anonymous namespace
103
104INITIALIZE_PASS(AArch64AdvSIMDScalarLegacy, "aarch64-simd-scalar",
105 AARCH64_ADVSIMD_NAME, false, false)
106
107PreservedAnalyses
108AArch64AdvSIMDScalarPass::run(MachineFunction &MF,
109 MachineFunctionAnalysisManager &MFAM) {
110 const bool Changed = AArch64AdvSIMDScalarImpl().run(MF);
111 if (!Changed)
112 return PreservedAnalyses::all();
113 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
114 PA.preserveSet<CFGAnalyses>();
115 return PA;
116}
117
118static bool isGPR64(unsigned Reg, unsigned SubReg,
119 const MachineRegisterInfo *MRI) {
120 if (SubReg)
121 return false;
122 if (Register::isVirtualRegister(Reg))
123 return MRI->getRegClass(Reg)->hasSuperClassEq(RC: &AArch64::GPR64RegClass);
124 return AArch64::GPR64RegClass.contains(Reg);
125}
126
127static bool isFPR64(unsigned Reg, unsigned SubReg,
128 const MachineRegisterInfo *MRI) {
129 if (Register::isVirtualRegister(Reg))
130 return (MRI->getRegClass(Reg)->hasSuperClassEq(RC: &AArch64::FPR64RegClass) &&
131 SubReg == 0) ||
132 (MRI->getRegClass(Reg)->hasSuperClassEq(RC: &AArch64::FPR128RegClass) &&
133 SubReg == AArch64::dsub);
134 // Physical register references just check the register class directly.
135 return (AArch64::FPR64RegClass.contains(Reg) && SubReg == 0) ||
136 (AArch64::FPR128RegClass.contains(Reg) && SubReg == AArch64::dsub);
137}
138
139// getSrcFromCopy - Get the original source register for a GPR64 <--> FPR64
140// copy instruction. Return nullptr if the instruction is not a copy.
141static MachineOperand *getSrcFromCopy(MachineInstr *MI,
142 const MachineRegisterInfo *MRI,
143 unsigned &SubReg) {
144 SubReg = 0;
145 // The "FMOV Xd, Dn" instruction is the typical form.
146 if (MI->getOpcode() == AArch64::FMOVDXr ||
147 MI->getOpcode() == AArch64::FMOVXDr)
148 return &MI->getOperand(i: 1);
149 // A lane zero extract "UMOV.d Xd, Vn[0]" is equivalent. We shouldn't see
150 // these at this stage, but it's easy to check for.
151 if (MI->getOpcode() == AArch64::UMOVvi64 && MI->getOperand(i: 2).getImm() == 0) {
152 SubReg = AArch64::dsub;
153 return &MI->getOperand(i: 1);
154 }
155 // Or just a plain COPY instruction. This can be directly to/from FPR64,
156 // or it can be a dsub subreg reference to an FPR128.
157 if (MI->getOpcode() == AArch64::COPY) {
158 if (isFPR64(Reg: MI->getOperand(i: 0).getReg(), SubReg: MI->getOperand(i: 0).getSubReg(),
159 MRI) &&
160 isGPR64(Reg: MI->getOperand(i: 1).getReg(), SubReg: MI->getOperand(i: 1).getSubReg(), MRI))
161 return &MI->getOperand(i: 1);
162 if (isGPR64(Reg: MI->getOperand(i: 0).getReg(), SubReg: MI->getOperand(i: 0).getSubReg(),
163 MRI) &&
164 isFPR64(Reg: MI->getOperand(i: 1).getReg(), SubReg: MI->getOperand(i: 1).getSubReg(),
165 MRI)) {
166 SubReg = MI->getOperand(i: 1).getSubReg();
167 return &MI->getOperand(i: 1);
168 }
169 }
170
171 // Otherwise, this is some other kind of instruction.
172 return nullptr;
173}
174
175// getTransformOpcode - For any opcode for which there is an AdvSIMD equivalent
176// that we're considering transforming to, return that AdvSIMD opcode. For all
177// others, return the original opcode.
178static unsigned getTransformOpcode(unsigned Opc) {
179 switch (Opc) {
180 default:
181 break;
182 // FIXME: Lots more possibilities.
183 case AArch64::ADDXrr:
184 return AArch64::ADDv1i64;
185 case AArch64::SUBXrr:
186 return AArch64::SUBv1i64;
187 case AArch64::ANDXrr:
188 return AArch64::ANDv8i8;
189 case AArch64::EORXrr:
190 return AArch64::EORv8i8;
191 case AArch64::ORRXrr:
192 return AArch64::ORRv8i8;
193 }
194 // No AdvSIMD equivalent, so just return the original opcode.
195 return Opc;
196}
197
198static bool isTransformable(const MachineInstr &MI) {
199 unsigned Opc = MI.getOpcode();
200 return Opc != getTransformOpcode(Opc);
201}
202
203// isProfitableToTransform - Predicate function to determine whether an
204// instruction should be transformed to its equivalent AdvSIMD scalar
205// instruction. "add Xd, Xn, Xm" ==> "add Dd, Da, Db", for example.
206bool AArch64AdvSIMDScalarImpl::isProfitableToTransform(
207 const MachineInstr &MI) const {
208 // If this instruction isn't eligible to be transformed (no SIMD equivalent),
209 // early exit since that's the common case.
210 if (!isTransformable(MI))
211 return false;
212
213 // Count the number of copies we'll need to add and approximate the number
214 // of copies that a transform will enable us to remove.
215 unsigned NumNewCopies = 3;
216 unsigned NumRemovableCopies = 0;
217
218 Register OrigSrc0 = MI.getOperand(i: 1).getReg();
219 Register OrigSrc1 = MI.getOperand(i: 2).getReg();
220 unsigned SubReg0;
221 unsigned SubReg1;
222 if (!MRI->def_empty(RegNo: OrigSrc0)) {
223 MachineRegisterInfo::def_instr_iterator Def =
224 MRI->def_instr_begin(RegNo: OrigSrc0);
225 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
226 MachineOperand *MOSrc0 = getSrcFromCopy(MI: &*Def, MRI, SubReg&: SubReg0);
227 // If the source was from a copy, we don't need to insert a new copy.
228 if (MOSrc0)
229 --NumNewCopies;
230 // If there are no other users of the original source, we can delete
231 // that instruction.
232 if (MOSrc0 && MRI->hasOneNonDBGUse(RegNo: OrigSrc0))
233 ++NumRemovableCopies;
234 }
235 if (!MRI->def_empty(RegNo: OrigSrc1)) {
236 MachineRegisterInfo::def_instr_iterator Def =
237 MRI->def_instr_begin(RegNo: OrigSrc1);
238 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
239 MachineOperand *MOSrc1 = getSrcFromCopy(MI: &*Def, MRI, SubReg&: SubReg1);
240 if (MOSrc1)
241 --NumNewCopies;
242 // If there are no other users of the original source, we can delete
243 // that instruction.
244 if (MOSrc1 && MRI->hasOneNonDBGUse(RegNo: OrigSrc1))
245 ++NumRemovableCopies;
246 }
247
248 // If any of the uses of the original instructions is a cross class copy,
249 // that's a copy that will be removable if we transform. Likewise, if
250 // any of the uses is a transformable instruction, it's likely the transforms
251 // will chain, enabling us to save a copy there, too. This is an aggressive
252 // heuristic that approximates the graph based cost analysis described above.
253 Register Dst = MI.getOperand(i: 0).getReg();
254 bool AllUsesAreCopies = true;
255 for (MachineRegisterInfo::use_instr_nodbg_iterator
256 Use = MRI->use_instr_nodbg_begin(RegNo: Dst),
257 E = MRI->use_instr_nodbg_end();
258 Use != E; ++Use) {
259 unsigned SubReg;
260 if (getSrcFromCopy(MI: &*Use, MRI, SubReg) || isTransformable(MI: *Use))
261 ++NumRemovableCopies;
262 // If the use is an INSERT_SUBREG, that's still something that can
263 // directly use the FPR64, so we don't invalidate AllUsesAreCopies. It's
264 // preferable to have it use the FPR64 in most cases, as if the source
265 // vector is an IMPLICIT_DEF, the INSERT_SUBREG just goes away entirely.
266 // Ditto for a lane insert.
267 else if (Use->getOpcode() == AArch64::INSERT_SUBREG ||
268 Use->getOpcode() == AArch64::INSvi64gpr)
269 ;
270 else
271 AllUsesAreCopies = false;
272 }
273 // If all of the uses of the original destination register are copies to
274 // FPR64, then we won't end up having a new copy back to GPR64 either.
275 if (AllUsesAreCopies)
276 --NumNewCopies;
277
278 // If a transform will not increase the number of cross-class copies required,
279 // return true.
280 if (NumNewCopies <= NumRemovableCopies)
281 return true;
282
283 // Finally, even if we otherwise wouldn't transform, check if we're forcing
284 // transformation of everything.
285 return TransformAll;
286}
287
288static MachineInstr *insertCopy(const TargetInstrInfo *TII, MachineInstr &MI,
289 unsigned Dst, unsigned Src, bool IsKill) {
290 MachineInstrBuilder MIB = BuildMI(BB&: *MI.getParent(), I&: MI, MIMD: MI.getDebugLoc(),
291 MCID: TII->get(Opcode: AArch64::COPY), DestReg: Dst)
292 .addReg(RegNo: Src, Flags: getKillRegState(B: IsKill));
293 LLVM_DEBUG(dbgs() << " adding copy: " << *MIB);
294 ++NumCopiesInserted;
295 return MIB;
296}
297
298// transformInstruction - Perform the transformation of an instruction
299// to its equivalent AdvSIMD scalar instruction. Update inputs and outputs
300// to be the correct register class, minimizing cross-class copies.
301void AArch64AdvSIMDScalarImpl::transformInstruction(MachineInstr &MI) {
302 LLVM_DEBUG(dbgs() << "Scalar transform: " << MI);
303
304 MachineBasicBlock *MBB = MI.getParent();
305 unsigned OldOpc = MI.getOpcode();
306 unsigned NewOpc = getTransformOpcode(Opc: OldOpc);
307 assert(OldOpc != NewOpc && "transform an instruction to itself?!");
308
309 // Check if we need a copy for the source registers.
310 Register OrigSrc0 = MI.getOperand(i: 1).getReg();
311 Register OrigSrc1 = MI.getOperand(i: 2).getReg();
312 unsigned Src0 = 0, SubReg0;
313 unsigned Src1 = 0, SubReg1;
314 bool KillSrc0 = false, KillSrc1 = false;
315 if (!MRI->def_empty(RegNo: OrigSrc0)) {
316 MachineRegisterInfo::def_instr_iterator Def =
317 MRI->def_instr_begin(RegNo: OrigSrc0);
318 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
319 MachineOperand *MOSrc0 = getSrcFromCopy(MI: &*Def, MRI, SubReg&: SubReg0);
320 // If there are no other users of the original source, we can delete
321 // that instruction.
322 if (MOSrc0) {
323 Src0 = MOSrc0->getReg();
324 KillSrc0 = MOSrc0->isKill();
325 // Src0 is going to be reused, thus, it cannot be killed anymore.
326 MOSrc0->setIsKill(false);
327 if (MRI->hasOneNonDBGUse(RegNo: OrigSrc0)) {
328 assert(MOSrc0 && "Can't delete copy w/o a valid original source!");
329 Def->eraseFromParent();
330 ++NumCopiesDeleted;
331 }
332 }
333 }
334 if (!MRI->def_empty(RegNo: OrigSrc1)) {
335 MachineRegisterInfo::def_instr_iterator Def =
336 MRI->def_instr_begin(RegNo: OrigSrc1);
337 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");
338 MachineOperand *MOSrc1 = getSrcFromCopy(MI: &*Def, MRI, SubReg&: SubReg1);
339 // If there are no other users of the original source, we can delete
340 // that instruction.
341 if (MOSrc1) {
342 Src1 = MOSrc1->getReg();
343 KillSrc1 = MOSrc1->isKill();
344 // Src0 is going to be reused, thus, it cannot be killed anymore.
345 MOSrc1->setIsKill(false);
346 if (MRI->hasOneNonDBGUse(RegNo: OrigSrc1)) {
347 assert(MOSrc1 && "Can't delete copy w/o a valid original source!");
348 Def->eraseFromParent();
349 ++NumCopiesDeleted;
350 }
351 }
352 }
353 // If we weren't able to reference the original source directly, create a
354 // copy.
355 if (!Src0) {
356 SubReg0 = 0;
357 Src0 = MRI->createVirtualRegister(RegClass: &AArch64::FPR64RegClass);
358 insertCopy(TII, MI, Dst: Src0, Src: OrigSrc0, IsKill: KillSrc0);
359 KillSrc0 = true;
360 }
361 if (!Src1) {
362 SubReg1 = 0;
363 Src1 = MRI->createVirtualRegister(RegClass: &AArch64::FPR64RegClass);
364 insertCopy(TII, MI, Dst: Src1, Src: OrigSrc1, IsKill: KillSrc1);
365 KillSrc1 = true;
366 }
367
368 // Create a vreg for the destination.
369 // FIXME: No need to do this if the ultimate user expects an FPR64.
370 // Check for that and avoid the copy if possible.
371 Register Dst = MRI->createVirtualRegister(RegClass: &AArch64::FPR64RegClass);
372
373 // For now, all of the new instructions have the same simple three-register
374 // form, so no need to special case based on what instruction we're
375 // building.
376 BuildMI(BB&: *MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: NewOpc), DestReg: Dst)
377 .addReg(RegNo: Src0, Flags: getKillRegState(B: KillSrc0), SubReg: SubReg0)
378 .addReg(RegNo: Src1, Flags: getKillRegState(B: KillSrc1), SubReg: SubReg1);
379
380 // Now copy the result back out to a GPR.
381 // FIXME: Try to avoid this if all uses could actually just use the FPR64
382 // directly.
383 insertCopy(TII, MI, Dst: MI.getOperand(i: 0).getReg(), Src: Dst, IsKill: true);
384
385 // Erase the old instruction.
386 MI.eraseFromParent();
387
388 ++NumScalarInsnsUsed;
389}
390
391// processMachineBasicBlock - Main optimization loop.
392bool AArch64AdvSIMDScalarImpl::processMachineBasicBlock(
393 MachineBasicBlock *MBB) {
394 bool Changed = false;
395 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
396 if (isProfitableToTransform(MI)) {
397 transformInstruction(MI);
398 Changed = true;
399 }
400 }
401 return Changed;
402}
403
404// runOnMachineFunction - Pass entry point from PassManager.
405bool AArch64AdvSIMDScalarLegacy::runOnMachineFunction(MachineFunction &MF) {
406 if (skipFunction(F: MF.getFunction()))
407 return false;
408
409 return AArch64AdvSIMDScalarImpl().run(MF);
410}
411
412bool AArch64AdvSIMDScalarImpl::run(MachineFunction &MF) {
413 bool Changed = false;
414 LLVM_DEBUG(dbgs() << "***** AArch64AdvSIMDScalar *****\n");
415
416 MRI = &MF.getRegInfo();
417 TII = MF.getSubtarget().getInstrInfo();
418
419 // Just check things on a one-block-at-a-time basis.
420 for (MachineBasicBlock &MBB : MF)
421 if (processMachineBasicBlock(MBB: &MBB))
422 Changed = true;
423 return Changed;
424}
425
426// createAArch64AdvSIMDScalar - Factory function used by AArch64TargetMachine
427// to add the pass to the PassManager.
428FunctionPass *llvm::createAArch64AdvSIMDScalar() {
429 return new AArch64AdvSIMDScalarLegacy();
430}
431