lib/Target/ARM64/ARM64AdvSIMDScalarPass.cpp

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