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" 48 using 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. 54 static cl::opt<bool> 55 TransformAll("aarch64-simd-scalar-force-all", 56 cl::desc("Force use of AdvSIMD scalar instructions everywhere"), 57 cl::init(false), cl::Hidden); 58 59 STATISTIC(NumScalarInsnsUsed, "Number of scalar instructions used"); 60 STATISTIC(NumCopiesDeleted, "Number of cross-class copies deleted"); 61 STATISTIC(NumCopiesInserted, "Number of cross-class copies inserted"); 62 63 namespace { 64 class AArch64AdvSIMDScalar : public MachineFunctionPass { 65 MachineRegisterInfo *MRI; 66 const AArch64InstrInfo *TII; 67 68 private: 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 82 public: 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 }; 97 char AArch64AdvSIMDScalar::ID = 0; 98 } // end anonymous namespace 99 100 static 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 109 static 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. 123 static 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. 160 static 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 174 static 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. 182 bool 183 AArch64AdvSIMDScalar::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 264 static 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. 278 void 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. 354 bool 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. 368 bool 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. 385 FunctionPass *llvm::createAArch64AdvSIMDScalar() { 386 return new AArch64AdvSIMDScalar(); 387 } 388