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