llvm/lib/Target/AMDGPU/SIOptimizeExecMasking.cpp

   1 //===-- SIOptimizeExecMasking.cpp -----------------------------------------===//
   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
   9 #include "AMDGPU.h"
  10 #include "GCNSubtarget.h"
  11 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
  12 #include "llvm/CodeGen/MachineFunctionPass.h"
  13 #include "llvm/InitializePasses.h"
  14
  15 using namespace llvm;
  16
  17 #define DEBUG_TYPE "si-optimize-exec-masking"
  18
  19 namespace {
  20
  21 class SIOptimizeExecMasking : public MachineFunctionPass {
  22 public:
  23   static char ID;
  24
  25 public:
  26   SIOptimizeExecMasking() : MachineFunctionPass(ID) {
  27     initializeSIOptimizeExecMaskingPass(*PassRegistry::getPassRegistry());
  28   }
  29
  30   bool runOnMachineFunction(MachineFunction &MF) override;
  31
  32   StringRef getPassName() const override {
  33     return "SI optimize exec mask operations";
  34   }
  35
  36   void getAnalysisUsage(AnalysisUsage &AU) const override {
  37     AU.setPreservesCFG();
  38     MachineFunctionPass::getAnalysisUsage(AU);
  39   }
  40 };
  41
  42 } // End anonymous namespace.
  43
  44 INITIALIZE_PASS_BEGIN(SIOptimizeExecMasking, DEBUG_TYPE,
  45                       "SI optimize exec mask operations", false, false)
  46 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  47 INITIALIZE_PASS_END(SIOptimizeExecMasking, DEBUG_TYPE,
  48                     "SI optimize exec mask operations", false, false)
  49
  50 char SIOptimizeExecMasking::ID = 0;
  51
  52 char &llvm::SIOptimizeExecMaskingID = SIOptimizeExecMasking::ID;
  53
  54 /// If \p MI is a copy from exec, return the register copied to.
  55 static Register isCopyFromExec(const MachineInstr &MI, const GCNSubtarget &ST) {
  56   switch (MI.getOpcode()) {
  57   case AMDGPU::COPY:
  58   case AMDGPU::S_MOV_B64:
  59   case AMDGPU::S_MOV_B64_term:
  60   case AMDGPU::S_MOV_B32:
  61   case AMDGPU::S_MOV_B32_term: {
  62     const MachineOperand &Src = MI.getOperand(1);
  63     if (Src.isReg() &&
  64         Src.getReg() == (ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC))
  65       return MI.getOperand(0).getReg();
  66   }
  67   }
  68
  69   return AMDGPU::NoRegister;
  70 }
  71
  72 /// If \p MI is a copy to exec, return the register copied from.
  73 static Register isCopyToExec(const MachineInstr &MI, const GCNSubtarget &ST) {
  74   switch (MI.getOpcode()) {
  75   case AMDGPU::COPY:
  76   case AMDGPU::S_MOV_B64:
  77   case AMDGPU::S_MOV_B32: {
  78     const MachineOperand &Dst = MI.getOperand(0);
  79     if (Dst.isReg() &&
  80         Dst.getReg() == (ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC) &&
  81         MI.getOperand(1).isReg())
  82       return MI.getOperand(1).getReg();
  83     break;
  84   }
  85   case AMDGPU::S_MOV_B64_term:
  86   case AMDGPU::S_MOV_B32_term:
  87     llvm_unreachable("should have been replaced");
  88   }
  89
  90   return Register();
  91 }
  92
  93 /// If \p MI is a logical operation on an exec value,
  94 /// return the register copied to.
  95 static Register isLogicalOpOnExec(const MachineInstr &MI) {
  96   switch (MI.getOpcode()) {
  97   case AMDGPU::S_AND_B64:
  98   case AMDGPU::S_OR_B64:
  99   case AMDGPU::S_XOR_B64:
 100   case AMDGPU::S_ANDN2_B64:
 101   case AMDGPU::S_ORN2_B64:
 102   case AMDGPU::S_NAND_B64:
 103   case AMDGPU::S_NOR_B64:
 104   case AMDGPU::S_XNOR_B64: {
 105     const MachineOperand &Src1 = MI.getOperand(1);
 106     if (Src1.isReg() && Src1.getReg() == AMDGPU::EXEC)
 107       return MI.getOperand(0).getReg();
 108     const MachineOperand &Src2 = MI.getOperand(2);
 109     if (Src2.isReg() && Src2.getReg() == AMDGPU::EXEC)
 110       return MI.getOperand(0).getReg();
 111     break;
 112   }
 113   case AMDGPU::S_AND_B32:
 114   case AMDGPU::S_OR_B32:
 115   case AMDGPU::S_XOR_B32:
 116   case AMDGPU::S_ANDN2_B32:
 117   case AMDGPU::S_ORN2_B32:
 118   case AMDGPU::S_NAND_B32:
 119   case AMDGPU::S_NOR_B32:
 120   case AMDGPU::S_XNOR_B32: {
 121     const MachineOperand &Src1 = MI.getOperand(1);
 122     if (Src1.isReg() && Src1.getReg() == AMDGPU::EXEC_LO)
 123       return MI.getOperand(0).getReg();
 124     const MachineOperand &Src2 = MI.getOperand(2);
 125     if (Src2.isReg() && Src2.getReg() == AMDGPU::EXEC_LO)
 126       return MI.getOperand(0).getReg();
 127     break;
 128   }
 129   }
 130
 131   return AMDGPU::NoRegister;
 132 }
 133
 134 static unsigned getSaveExecOp(unsigned Opc) {
 135   switch (Opc) {
 136   case AMDGPU::S_AND_B64:
 137     return AMDGPU::S_AND_SAVEEXEC_B64;
 138   case AMDGPU::S_OR_B64:
 139     return AMDGPU::S_OR_SAVEEXEC_B64;
 140   case AMDGPU::S_XOR_B64:
 141     return AMDGPU::S_XOR_SAVEEXEC_B64;
 142   case AMDGPU::S_ANDN2_B64:
 143     return AMDGPU::S_ANDN2_SAVEEXEC_B64;
 144   case AMDGPU::S_ORN2_B64:
 145     return AMDGPU::S_ORN2_SAVEEXEC_B64;
 146   case AMDGPU::S_NAND_B64:
 147     return AMDGPU::S_NAND_SAVEEXEC_B64;
 148   case AMDGPU::S_NOR_B64:
 149     return AMDGPU::S_NOR_SAVEEXEC_B64;
 150   case AMDGPU::S_XNOR_B64:
 151     return AMDGPU::S_XNOR_SAVEEXEC_B64;
 152   case AMDGPU::S_AND_B32:
 153     return AMDGPU::S_AND_SAVEEXEC_B32;
 154   case AMDGPU::S_OR_B32:
 155     return AMDGPU::S_OR_SAVEEXEC_B32;
 156   case AMDGPU::S_XOR_B32:
 157     return AMDGPU::S_XOR_SAVEEXEC_B32;
 158   case AMDGPU::S_ANDN2_B32:
 159     return AMDGPU::S_ANDN2_SAVEEXEC_B32;
 160   case AMDGPU::S_ORN2_B32:
 161     return AMDGPU::S_ORN2_SAVEEXEC_B32;
 162   case AMDGPU::S_NAND_B32:
 163     return AMDGPU::S_NAND_SAVEEXEC_B32;
 164   case AMDGPU::S_NOR_B32:
 165     return AMDGPU::S_NOR_SAVEEXEC_B32;
 166   case AMDGPU::S_XNOR_B32:
 167     return AMDGPU::S_XNOR_SAVEEXEC_B32;
 168   default:
 169     return AMDGPU::INSTRUCTION_LIST_END;
 170   }
 171 }
 172
 173 // These are only terminators to get correct spill code placement during
 174 // register allocation, so turn them back into normal instructions.
 175 static bool removeTerminatorBit(const SIInstrInfo &TII, MachineInstr &MI) {
 176   switch (MI.getOpcode()) {
 177   case AMDGPU::S_MOV_B32_term: {
 178     bool RegSrc = MI.getOperand(1).isReg();
 179     MI.setDesc(TII.get(RegSrc ? AMDGPU::COPY : AMDGPU::S_MOV_B32));
 180     return true;
 181   }
 182   case AMDGPU::S_MOV_B64_term: {
 183     bool RegSrc = MI.getOperand(1).isReg();
 184     MI.setDesc(TII.get(RegSrc ? AMDGPU::COPY : AMDGPU::S_MOV_B64));
 185     return true;
 186   }
 187   case AMDGPU::S_XOR_B64_term: {
 188     // This is only a terminator to get the correct spill code placement during
 189     // register allocation.
 190     MI.setDesc(TII.get(AMDGPU::S_XOR_B64));
 191     return true;
 192   }
 193   case AMDGPU::S_XOR_B32_term: {
 194     // This is only a terminator to get the correct spill code placement during
 195     // register allocation.
 196     MI.setDesc(TII.get(AMDGPU::S_XOR_B32));
 197     return true;
 198   }
 199   case AMDGPU::S_OR_B64_term: {
 200     // This is only a terminator to get the correct spill code placement during
 201     // register allocation.
 202     MI.setDesc(TII.get(AMDGPU::S_OR_B64));
 203     return true;
 204   }
 205   case AMDGPU::S_OR_B32_term: {
 206     // This is only a terminator to get the correct spill code placement during
 207     // register allocation.
 208     MI.setDesc(TII.get(AMDGPU::S_OR_B32));
 209     return true;
 210   }
 211   case AMDGPU::S_ANDN2_B64_term: {
 212     // This is only a terminator to get the correct spill code placement during
 213     // register allocation.
 214     MI.setDesc(TII.get(AMDGPU::S_ANDN2_B64));
 215     return true;
 216   }
 217   case AMDGPU::S_ANDN2_B32_term: {
 218     // This is only a terminator to get the correct spill code placement during
 219     // register allocation.
 220     MI.setDesc(TII.get(AMDGPU::S_ANDN2_B32));
 221     return true;
 222   }
 223   case AMDGPU::S_AND_B64_term: {
 224     // This is only a terminator to get the correct spill code placement during
 225     // register allocation.
 226     MI.setDesc(TII.get(AMDGPU::S_AND_B64));
 227     return true;
 228   }
 229   case AMDGPU::S_AND_B32_term: {
 230     // This is only a terminator to get the correct spill code placement during
 231     // register allocation.
 232     MI.setDesc(TII.get(AMDGPU::S_AND_B32));
 233     return true;
 234   }
 235   default:
 236     return false;
 237   }
 238 }
 239
 240 // Turn all pseudoterminators in the block into their equivalent non-terminator
 241 // instructions. Returns the reverse iterator to the first non-terminator
 242 // instruction in the block.
 243 static MachineBasicBlock::reverse_iterator fixTerminators(
 244   const SIInstrInfo &TII,
 245   MachineBasicBlock &MBB) {
 246   MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend();
 247
 248   bool Seen = false;
 249   MachineBasicBlock::reverse_iterator FirstNonTerm = I;
 250   for (; I != E; ++I) {
 251     if (!I->isTerminator())
 252       return Seen ? FirstNonTerm : I;
 253
 254     if (removeTerminatorBit(TII, *I)) {
 255       if (!Seen) {
 256         FirstNonTerm = I;
 257         Seen = true;
 258       }
 259     }
 260   }
 261
 262   return FirstNonTerm;
 263 }
 264
 265 static MachineBasicBlock::reverse_iterator findExecCopy(
 266   const SIInstrInfo &TII,
 267   const GCNSubtarget &ST,
 268   MachineBasicBlock &MBB,
 269   MachineBasicBlock::reverse_iterator I,
 270   unsigned CopyToExec) {
 271   const unsigned InstLimit = 25;
 272
 273   auto E = MBB.rend();
 274   for (unsigned N = 0; N <= InstLimit && I != E; ++I, ++N) {
 275     Register CopyFromExec = isCopyFromExec(*I, ST);
 276     if (CopyFromExec.isValid())
 277       return I;
 278   }
 279
 280   return E;
 281 }
 282
 283 // XXX - Seems LivePhysRegs doesn't work correctly since it will incorrectly
 284 // report the register as unavailable because a super-register with a lane mask
 285 // is unavailable.
 286 static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg) {
 287   for (MachineBasicBlock *Succ : MBB.successors()) {
 288     if (Succ->isLiveIn(Reg))
 289       return true;
 290   }
 291
 292   return false;
 293 }
 294
 295 bool SIOptimizeExecMasking::runOnMachineFunction(MachineFunction &MF) {
 296   if (skipFunction(MF.getFunction()))
 297     return false;
 298
 299   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
 300   const SIRegisterInfo *TRI = ST.getRegisterInfo();
 301   const SIInstrInfo *TII = ST.getInstrInfo();
 302   MCRegister Exec = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
 303
 304   // Optimize sequences emitted for control flow lowering. They are originally
 305   // emitted as the separate operations because spill code may need to be
 306   // inserted for the saved copy of exec.
 307   //
 308   //     x = copy exec
 309   //     z = s_<op>_b64 x, y
 310   //     exec = copy z
 311   // =>
 312   //     x = s_<op>_saveexec_b64 y
 313   //
 314
 315   bool Changed = false;
 316   for (MachineBasicBlock &MBB : MF) {
 317     MachineBasicBlock::reverse_iterator I = fixTerminators(*TII, MBB);
 318     MachineBasicBlock::reverse_iterator E = MBB.rend();
 319     if (I == E)
 320       continue;
 321
 322     // It's possible to see other terminator copies after the exec copy. This
 323     // can happen if control flow pseudos had their outputs used by phis.
 324     Register CopyToExec;
 325
 326     unsigned SearchCount = 0;
 327     const unsigned SearchLimit = 5;
 328     while (I != E && SearchCount++ < SearchLimit) {
 329       CopyToExec = isCopyToExec(*I, ST);
 330       if (CopyToExec)
 331         break;
 332       ++I;
 333     }
 334
 335     if (!CopyToExec)
 336       continue;
 337
 338     // Scan backwards to find the def.
 339     auto CopyToExecInst = &*I;
 340     auto CopyFromExecInst = findExecCopy(*TII, ST, MBB, I, CopyToExec);
 341     if (CopyFromExecInst == E) {
 342       auto PrepareExecInst = std::next(I);
 343       if (PrepareExecInst == E)
 344         continue;
 345       // Fold exec = COPY (S_AND_B64 reg, exec) -> exec = S_AND_B64 reg, exec
 346       if (CopyToExecInst->getOperand(1).isKill() &&
 347           isLogicalOpOnExec(*PrepareExecInst) == CopyToExec) {
 348         LLVM_DEBUG(dbgs() << "Fold exec copy: " << *PrepareExecInst);
 349
 350         PrepareExecInst->getOperand(0).setReg(Exec);
 351
 352         LLVM_DEBUG(dbgs() << "into: " << *PrepareExecInst << '\n');
 353
 354         CopyToExecInst->eraseFromParent();
 355         Changed = true;
 356       }
 357
 358       continue;
 359     }
 360
 361     if (isLiveOut(MBB, CopyToExec)) {
 362       // The copied register is live out and has a second use in another block.
 363       LLVM_DEBUG(dbgs() << "Exec copy source register is live out\n");
 364       continue;
 365     }
 366
 367     Register CopyFromExec = CopyFromExecInst->getOperand(0).getReg();
 368     MachineInstr *SaveExecInst = nullptr;
 369     SmallVector<MachineInstr *, 4> OtherUseInsts;
 370
 371     for (MachineBasicBlock::iterator J
 372            = std::next(CopyFromExecInst->getIterator()), JE = I->getIterator();
 373          J != JE; ++J) {
 374       if (SaveExecInst && J->readsRegister(Exec, TRI)) {
 375         LLVM_DEBUG(dbgs() << "exec read prevents saveexec: " << *J << '\n');
 376         // Make sure this is inserted after any VALU ops that may have been
 377         // scheduled in between.
 378         SaveExecInst = nullptr;
 379         break;
 380       }
 381
 382       bool ReadsCopyFromExec = J->readsRegister(CopyFromExec, TRI);
 383
 384       if (J->modifiesRegister(CopyToExec, TRI)) {
 385         if (SaveExecInst) {
 386           LLVM_DEBUG(dbgs() << "Multiple instructions modify "
 387                             << printReg(CopyToExec, TRI) << '\n');
 388           SaveExecInst = nullptr;
 389           break;
 390         }
 391
 392         unsigned SaveExecOp = getSaveExecOp(J->getOpcode());
 393         if (SaveExecOp == AMDGPU::INSTRUCTION_LIST_END)
 394           break;
 395
 396         if (ReadsCopyFromExec) {
 397           SaveExecInst = &*J;
 398           LLVM_DEBUG(dbgs() << "Found save exec op: " << *SaveExecInst << '\n');
 399           continue;
 400         } else {
 401           LLVM_DEBUG(dbgs()
 402                      << "Instruction does not read exec copy: " << *J << '\n');
 403           break;
 404         }
 405       } else if (ReadsCopyFromExec && !SaveExecInst) {
 406         // Make sure no other instruction is trying to use this copy, before it
 407         // will be rewritten by the saveexec, i.e. hasOneUse. There may have
 408         // been another use, such as an inserted spill. For example:
 409         //
 410         // %sgpr0_sgpr1 = COPY %exec
 411         // spill %sgpr0_sgpr1
 412         // %sgpr2_sgpr3 = S_AND_B64 %sgpr0_sgpr1
 413         //
 414         LLVM_DEBUG(dbgs() << "Found second use of save inst candidate: " << *J
 415                           << '\n');
 416         break;
 417       }
 418
 419       if (SaveExecInst && J->readsRegister(CopyToExec, TRI)) {
 420         assert(SaveExecInst != &*J);
 421         OtherUseInsts.push_back(&*J);
 422       }
 423     }
 424
 425     if (!SaveExecInst)
 426       continue;
 427
 428     LLVM_DEBUG(dbgs() << "Insert save exec op: " << *SaveExecInst << '\n');
 429
 430     MachineOperand &Src0 = SaveExecInst->getOperand(1);
 431     MachineOperand &Src1 = SaveExecInst->getOperand(2);
 432
 433     MachineOperand *OtherOp = nullptr;
 434
 435     if (Src0.isReg() && Src0.getReg() == CopyFromExec) {
 436       OtherOp = &Src1;
 437     } else if (Src1.isReg() && Src1.getReg() == CopyFromExec) {
 438       if (!SaveExecInst->isCommutable())
 439         break;
 440
 441       OtherOp = &Src0;
 442     } else
 443       llvm_unreachable("unexpected");
 444
 445     CopyFromExecInst->eraseFromParent();
 446
 447     auto InsPt = SaveExecInst->getIterator();
 448     const DebugLoc &DL = SaveExecInst->getDebugLoc();
 449
 450     BuildMI(MBB, InsPt, DL, TII->get(getSaveExecOp(SaveExecInst->getOpcode())),
 451             CopyFromExec)
 452       .addReg(OtherOp->getReg());
 453     SaveExecInst->eraseFromParent();
 454
 455     CopyToExecInst->eraseFromParent();
 456
 457     for (MachineInstr *OtherInst : OtherUseInsts) {
 458       OtherInst->substituteRegister(CopyToExec, Exec,
 459                                     AMDGPU::NoSubRegister, *TRI);
 460     }
 461
 462     Changed = true;
 463   }
 464
 465   return Changed;
 466 }