410 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8// When profitable, replace GPR targeting i64 instructions with their9// AdvSIMD scalar equivalents. Generally speaking, "profitable" is defined10// 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, of16// the cases, but to do a truly thorough job of this, we need a more17// wholistic approach.18//19// This optimization is very similar in spirit to the register allocator's20// spill placement, only here we're determining where to place cross-class21// register copies rather than spills. As such, a similar approach is22// called for.23//24// We want to build up a set of graphs of all instructions which are candidates25// for transformation along with instructions which generate their inputs and26// consume their outputs. For each edge in the graph, we assign a weight27// based on whether there is a copy required there (weight zero if not) and28// the block frequency of the block containing the defining or using29// instruction, whichever is less. Our optimization is then a graph problem30// to minimize the total weight of all the graphs, then transform instructions31// and add or remove copy instructions as called for to implement the32// 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 use52// 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(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 AArch64AdvSIMDScalar : public MachineFunctionPass {66 MachineRegisterInfo *MRI;67 const TargetInstrInfo *TII;68 69private:70 // isProfitableToTransform - Predicate function to determine whether an71 // instruction should be transformed to its equivalent AdvSIMD scalar72 // 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 instruction76 // to its equivalent AdvSIMD scalar instruction. Update inputs and outputs77 // 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 83public:84 static char ID; // Pass identification, replacement for typeid.85 explicit AArch64AdvSIMDScalar() : MachineFunctionPass(ID) {}86 87 bool runOnMachineFunction(MachineFunction &F) override;88 89 StringRef getPassName() const override { return AARCH64_ADVSIMD_NAME; }90 91 void getAnalysisUsage(AnalysisUsage &AU) const override {92 AU.setPreservesCFG();93 MachineFunctionPass::getAnalysisUsage(AU);94 }95};96char AArch64AdvSIMDScalar::ID = 0;97} // end anonymous namespace98 99INITIALIZE_PASS(AArch64AdvSIMDScalar, "aarch64-simd-scalar",100 AARCH64_ADVSIMD_NAME, false, false)101 102static bool isGPR64(unsigned Reg, unsigned SubReg,103 const MachineRegisterInfo *MRI) {104 if (SubReg)105 return false;106 if (Register::isVirtualRegister(Reg))107 return MRI->getRegClass(Reg)->hasSuperClassEq(&AArch64::GPR64RegClass);108 return AArch64::GPR64RegClass.contains(Reg);109}110 111static bool isFPR64(unsigned Reg, unsigned SubReg,112 const MachineRegisterInfo *MRI) {113 if (Register::isVirtualRegister(Reg))114 return (MRI->getRegClass(Reg)->hasSuperClassEq(&AArch64::FPR64RegClass) &&115 SubReg == 0) ||116 (MRI->getRegClass(Reg)->hasSuperClassEq(&AArch64::FPR128RegClass) &&117 SubReg == AArch64::dsub);118 // Physical register references just check the register class directly.119 return (AArch64::FPR64RegClass.contains(Reg) && SubReg == 0) ||120 (AArch64::FPR128RegClass.contains(Reg) && SubReg == AArch64::dsub);121}122 123// getSrcFromCopy - Get the original source register for a GPR64 <--> FPR64124// copy instruction. Return nullptr if the instruction is not a copy.125static MachineOperand *getSrcFromCopy(MachineInstr *MI,126 const MachineRegisterInfo *MRI,127 unsigned &SubReg) {128 SubReg = 0;129 // The "FMOV Xd, Dn" instruction is the typical form.130 if (MI->getOpcode() == AArch64::FMOVDXr ||131 MI->getOpcode() == AArch64::FMOVXDr)132 return &MI->getOperand(1);133 // A lane zero extract "UMOV.d Xd, Vn[0]" is equivalent. We shouldn't see134 // these at this stage, but it's easy to check for.135 if (MI->getOpcode() == AArch64::UMOVvi64 && MI->getOperand(2).getImm() == 0) {136 SubReg = AArch64::dsub;137 return &MI->getOperand(1);138 }139 // Or just a plain COPY instruction. This can be directly to/from FPR64,140 // or it can be a dsub subreg reference to an FPR128.141 if (MI->getOpcode() == AArch64::COPY) {142 if (isFPR64(MI->getOperand(0).getReg(), MI->getOperand(0).getSubReg(),143 MRI) &&144 isGPR64(MI->getOperand(1).getReg(), MI->getOperand(1).getSubReg(), MRI))145 return &MI->getOperand(1);146 if (isGPR64(MI->getOperand(0).getReg(), MI->getOperand(0).getSubReg(),147 MRI) &&148 isFPR64(MI->getOperand(1).getReg(), MI->getOperand(1).getSubReg(),149 MRI)) {150 SubReg = MI->getOperand(1).getSubReg();151 return &MI->getOperand(1);152 }153 }154 155 // Otherwise, this is some other kind of instruction.156 return nullptr;157}158 159// getTransformOpcode - For any opcode for which there is an AdvSIMD equivalent160// that we're considering transforming to, return that AdvSIMD opcode. For all161// others, return the original opcode.162static unsigned getTransformOpcode(unsigned Opc) {163 switch (Opc) {164 default:165 break;166 // FIXME: Lots more possibilities.167 case AArch64::ADDXrr:168 return AArch64::ADDv1i64;169 case AArch64::SUBXrr:170 return AArch64::SUBv1i64;171 case AArch64::ANDXrr:172 return AArch64::ANDv8i8;173 case AArch64::EORXrr:174 return AArch64::EORv8i8;175 case AArch64::ORRXrr:176 return AArch64::ORRv8i8;177 }178 // No AdvSIMD equivalent, so just return the original opcode.179 return Opc;180}181 182static bool isTransformable(const MachineInstr &MI) {183 unsigned Opc = MI.getOpcode();184 return Opc != getTransformOpcode(Opc);185}186 187// isProfitableToTransform - Predicate function to determine whether an188// instruction should be transformed to its equivalent AdvSIMD scalar189// instruction. "add Xd, Xn, Xm" ==> "add Dd, Da, Db", for example.190bool AArch64AdvSIMDScalar::isProfitableToTransform(191 const MachineInstr &MI) const {192 // If this instruction isn't eligible to be transformed (no SIMD equivalent),193 // early exit since that's the common case.194 if (!isTransformable(MI))195 return false;196 197 // Count the number of copies we'll need to add and approximate the number198 // of copies that a transform will enable us to remove.199 unsigned NumNewCopies = 3;200 unsigned NumRemovableCopies = 0;201 202 Register OrigSrc0 = MI.getOperand(1).getReg();203 Register OrigSrc1 = MI.getOperand(2).getReg();204 unsigned SubReg0;205 unsigned SubReg1;206 if (!MRI->def_empty(OrigSrc0)) {207 MachineRegisterInfo::def_instr_iterator Def =208 MRI->def_instr_begin(OrigSrc0);209 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");210 MachineOperand *MOSrc0 = getSrcFromCopy(&*Def, MRI, SubReg0);211 // If the source was from a copy, we don't need to insert a new copy.212 if (MOSrc0)213 --NumNewCopies;214 // If there are no other users of the original source, we can delete215 // that instruction.216 if (MOSrc0 && MRI->hasOneNonDBGUse(OrigSrc0))217 ++NumRemovableCopies;218 }219 if (!MRI->def_empty(OrigSrc1)) {220 MachineRegisterInfo::def_instr_iterator Def =221 MRI->def_instr_begin(OrigSrc1);222 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");223 MachineOperand *MOSrc1 = getSrcFromCopy(&*Def, MRI, SubReg1);224 if (MOSrc1)225 --NumNewCopies;226 // If there are no other users of the original source, we can delete227 // that instruction.228 if (MOSrc1 && MRI->hasOneNonDBGUse(OrigSrc1))229 ++NumRemovableCopies;230 }231 232 // If any of the uses of the original instructions is a cross class copy,233 // that's a copy that will be removable if we transform. Likewise, if234 // any of the uses is a transformable instruction, it's likely the transforms235 // will chain, enabling us to save a copy there, too. This is an aggressive236 // heuristic that approximates the graph based cost analysis described above.237 Register Dst = MI.getOperand(0).getReg();238 bool AllUsesAreCopies = true;239 for (MachineRegisterInfo::use_instr_nodbg_iterator240 Use = MRI->use_instr_nodbg_begin(Dst),241 E = MRI->use_instr_nodbg_end();242 Use != E; ++Use) {243 unsigned SubReg;244 if (getSrcFromCopy(&*Use, MRI, SubReg) || isTransformable(*Use))245 ++NumRemovableCopies;246 // If the use is an INSERT_SUBREG, that's still something that can247 // directly use the FPR64, so we don't invalidate AllUsesAreCopies. It's248 // preferable to have it use the FPR64 in most cases, as if the source249 // vector is an IMPLICIT_DEF, the INSERT_SUBREG just goes away entirely.250 // Ditto for a lane insert.251 else if (Use->getOpcode() == AArch64::INSERT_SUBREG ||252 Use->getOpcode() == AArch64::INSvi64gpr)253 ;254 else255 AllUsesAreCopies = false;256 }257 // If all of the uses of the original destination register are copies to258 // FPR64, then we won't end up having a new copy back to GPR64 either.259 if (AllUsesAreCopies)260 --NumNewCopies;261 262 // If a transform will not increase the number of cross-class copies required,263 // return true.264 if (NumNewCopies <= NumRemovableCopies)265 return true;266 267 // Finally, even if we otherwise wouldn't transform, check if we're forcing268 // transformation of everything.269 return TransformAll;270}271 272static MachineInstr *insertCopy(const TargetInstrInfo *TII, MachineInstr &MI,273 unsigned Dst, unsigned Src, bool IsKill) {274 MachineInstrBuilder MIB = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),275 TII->get(AArch64::COPY), Dst)276 .addReg(Src, getKillRegState(IsKill));277 LLVM_DEBUG(dbgs() << " adding copy: " << *MIB);278 ++NumCopiesInserted;279 return MIB;280}281 282// transformInstruction - Perform the transformation of an instruction283// to its equivalent AdvSIMD scalar instruction. Update inputs and outputs284// to be the correct register class, minimizing cross-class copies.285void AArch64AdvSIMDScalar::transformInstruction(MachineInstr &MI) {286 LLVM_DEBUG(dbgs() << "Scalar transform: " << MI);287 288 MachineBasicBlock *MBB = MI.getParent();289 unsigned OldOpc = MI.getOpcode();290 unsigned NewOpc = getTransformOpcode(OldOpc);291 assert(OldOpc != NewOpc && "transform an instruction to itself?!");292 293 // Check if we need a copy for the source registers.294 Register OrigSrc0 = MI.getOperand(1).getReg();295 Register OrigSrc1 = MI.getOperand(2).getReg();296 unsigned Src0 = 0, SubReg0;297 unsigned Src1 = 0, SubReg1;298 bool KillSrc0 = false, KillSrc1 = false;299 if (!MRI->def_empty(OrigSrc0)) {300 MachineRegisterInfo::def_instr_iterator Def =301 MRI->def_instr_begin(OrigSrc0);302 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");303 MachineOperand *MOSrc0 = getSrcFromCopy(&*Def, MRI, SubReg0);304 // If there are no other users of the original source, we can delete305 // that instruction.306 if (MOSrc0) {307 Src0 = MOSrc0->getReg();308 KillSrc0 = MOSrc0->isKill();309 // Src0 is going to be reused, thus, it cannot be killed anymore.310 MOSrc0->setIsKill(false);311 if (MRI->hasOneNonDBGUse(OrigSrc0)) {312 assert(MOSrc0 && "Can't delete copy w/o a valid original source!");313 Def->eraseFromParent();314 ++NumCopiesDeleted;315 }316 }317 }318 if (!MRI->def_empty(OrigSrc1)) {319 MachineRegisterInfo::def_instr_iterator Def =320 MRI->def_instr_begin(OrigSrc1);321 assert(std::next(Def) == MRI->def_instr_end() && "Multiple def in SSA!");322 MachineOperand *MOSrc1 = getSrcFromCopy(&*Def, MRI, SubReg1);323 // If there are no other users of the original source, we can delete324 // that instruction.325 if (MOSrc1) {326 Src1 = MOSrc1->getReg();327 KillSrc1 = MOSrc1->isKill();328 // Src0 is going to be reused, thus, it cannot be killed anymore.329 MOSrc1->setIsKill(false);330 if (MRI->hasOneNonDBGUse(OrigSrc1)) {331 assert(MOSrc1 && "Can't delete copy w/o a valid original source!");332 Def->eraseFromParent();333 ++NumCopiesDeleted;334 }335 }336 }337 // If we weren't able to reference the original source directly, create a338 // copy.339 if (!Src0) {340 SubReg0 = 0;341 Src0 = MRI->createVirtualRegister(&AArch64::FPR64RegClass);342 insertCopy(TII, MI, Src0, OrigSrc0, KillSrc0);343 KillSrc0 = true;344 }345 if (!Src1) {346 SubReg1 = 0;347 Src1 = MRI->createVirtualRegister(&AArch64::FPR64RegClass);348 insertCopy(TII, MI, Src1, OrigSrc1, KillSrc1);349 KillSrc1 = true;350 }351 352 // Create a vreg for the destination.353 // FIXME: No need to do this if the ultimate user expects an FPR64.354 // Check for that and avoid the copy if possible.355 Register Dst = MRI->createVirtualRegister(&AArch64::FPR64RegClass);356 357 // For now, all of the new instructions have the same simple three-register358 // form, so no need to special case based on what instruction we're359 // building.360 BuildMI(*MBB, MI, MI.getDebugLoc(), TII->get(NewOpc), Dst)361 .addReg(Src0, getKillRegState(KillSrc0), SubReg0)362 .addReg(Src1, getKillRegState(KillSrc1), SubReg1);363 364 // Now copy the result back out to a GPR.365 // FIXME: Try to avoid this if all uses could actually just use the FPR64366 // directly.367 insertCopy(TII, MI, MI.getOperand(0).getReg(), Dst, true);368 369 // Erase the old instruction.370 MI.eraseFromParent();371 372 ++NumScalarInsnsUsed;373}374 375// processMachineBasicBlock - Main optimization loop.376bool AArch64AdvSIMDScalar::processMachineBasicBlock(MachineBasicBlock *MBB) {377 bool Changed = false;378 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {379 if (isProfitableToTransform(MI)) {380 transformInstruction(MI);381 Changed = true;382 }383 }384 return Changed;385}386 387// runOnMachineFunction - Pass entry point from PassManager.388bool AArch64AdvSIMDScalar::runOnMachineFunction(MachineFunction &mf) {389 bool Changed = false;390 LLVM_DEBUG(dbgs() << "***** AArch64AdvSIMDScalar *****\n");391 392 if (skipFunction(mf.getFunction()))393 return false;394 395 MRI = &mf.getRegInfo();396 TII = mf.getSubtarget().getInstrInfo();397 398 // Just check things on a one-block-at-a-time basis.399 for (MachineBasicBlock &MBB : mf)400 if (processMachineBasicBlock(&MBB))401 Changed = true;402 return Changed;403}404 405// createAArch64AdvSIMDScalar - Factory function used by AArch64TargetMachine406// to add the pass to the PassManager.407FunctionPass *llvm::createAArch64AdvSIMDScalar() {408 return new AArch64AdvSIMDScalar();409}410