llvm/lib/Target/AMDGPU/SIOptimizeExecMaskingPreRA.cpp

   1 //===-- SIOptimizeExecMaskingPreRA.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 /// \file
  10 /// This pass performs exec mask handling peephole optimizations which needs
  11 /// to be done before register allocation to reduce register pressure.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "AMDGPU.h"
  16 #include "GCNSubtarget.h"
  17 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
  18 #include "llvm/CodeGen/LiveIntervals.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/InitializePasses.h"
  21
  22 using namespace llvm;
  23
  24 #define DEBUG_TYPE "si-optimize-exec-masking-pre-ra"
  25
  26 namespace {
  27
  28 class SIOptimizeExecMaskingPreRA : public MachineFunctionPass {
  29 private:
  30   const SIRegisterInfo *TRI;
  31   const SIInstrInfo *TII;
  32   MachineRegisterInfo *MRI;
  33   LiveIntervals *LIS;
  34
  35   unsigned AndOpc;
  36   unsigned Andn2Opc;
  37   unsigned OrSaveExecOpc;
  38   unsigned XorTermrOpc;
  39   MCRegister CondReg;
  40   MCRegister ExecReg;
  41
  42   Register optimizeVcndVcmpPair(MachineBasicBlock &MBB);
  43   bool optimizeElseBranch(MachineBasicBlock &MBB);
  44
  45 public:
  46   static char ID;
  47
  48   SIOptimizeExecMaskingPreRA() : MachineFunctionPass(ID) {
  49     initializeSIOptimizeExecMaskingPreRAPass(*PassRegistry::getPassRegistry());
  50   }
  51
  52   bool runOnMachineFunction(MachineFunction &MF) override;
  53
  54   StringRef getPassName() const override {
  55     return "SI optimize exec mask operations pre-RA";
  56   }
  57
  58   void getAnalysisUsage(AnalysisUsage &AU) const override {
  59     AU.addRequired<LiveIntervals>();
  60     AU.setPreservesAll();
  61     MachineFunctionPass::getAnalysisUsage(AU);
  62   }
  63 };
  64
  65 } // End anonymous namespace.
  66
  67 INITIALIZE_PASS_BEGIN(SIOptimizeExecMaskingPreRA, DEBUG_TYPE,
  68                       "SI optimize exec mask operations pre-RA", false, false)
  69 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  70 INITIALIZE_PASS_END(SIOptimizeExecMaskingPreRA, DEBUG_TYPE,
  71                     "SI optimize exec mask operations pre-RA", false, false)
  72
  73 char SIOptimizeExecMaskingPreRA::ID = 0;
  74
  75 char &llvm::SIOptimizeExecMaskingPreRAID = SIOptimizeExecMaskingPreRA::ID;
  76
  77 FunctionPass *llvm::createSIOptimizeExecMaskingPreRAPass() {
  78   return new SIOptimizeExecMaskingPreRA();
  79 }
  80
  81 // See if there is a def between \p AndIdx and \p SelIdx that needs to live
  82 // beyond \p AndIdx.
  83 static bool isDefBetween(const LiveRange &LR, SlotIndex AndIdx,
  84                          SlotIndex SelIdx) {
  85   LiveQueryResult AndLRQ = LR.Query(AndIdx);
  86   return (!AndLRQ.isKill() && AndLRQ.valueIn() != LR.Query(SelIdx).valueOut());
  87 }
  88
  89 // FIXME: Why do we bother trying to handle physical registers here?
  90 static bool isDefBetween(const SIRegisterInfo &TRI,
  91                          LiveIntervals *LIS, Register Reg,
  92                          const MachineInstr &Sel, const MachineInstr &And) {
  93   SlotIndex AndIdx = LIS->getInstructionIndex(And);
  94   SlotIndex SelIdx = LIS->getInstructionIndex(Sel);
  95
  96   if (Reg.isVirtual())
  97     return isDefBetween(LIS->getInterval(Reg), AndIdx, SelIdx);
  98
  99   for (MCRegUnitIterator UI(Reg.asMCReg(), &TRI); UI.isValid(); ++UI) {
 100     if (isDefBetween(LIS->getRegUnit(*UI), AndIdx, SelIdx))
 101       return true;
 102   }
 103
 104   return false;
 105 }
 106
 107 // Optimize sequence
 108 //    %sel = V_CNDMASK_B32_e64 0, 1, %cc
 109 //    %cmp = V_CMP_NE_U32 1, %1
 110 //    $vcc = S_AND_B64 $exec, %cmp
 111 //    S_CBRANCH_VCC[N]Z
 112 // =>
 113 //    $vcc = S_ANDN2_B64 $exec, %cc
 114 //    S_CBRANCH_VCC[N]Z
 115 //
 116 // It is the negation pattern inserted by DAGCombiner::visitBRCOND() in the
 117 // rebuildSetCC(). We start with S_CBRANCH to avoid exhaustive search, but
 118 // only 3 first instructions are really needed. S_AND_B64 with exec is a
 119 // required part of the pattern since V_CNDMASK_B32 writes zeroes for inactive
 120 // lanes.
 121 //
 122 // Returns %cc register on success.
 123 Register
 124 SIOptimizeExecMaskingPreRA::optimizeVcndVcmpPair(MachineBasicBlock &MBB) {
 125   auto I = llvm::find_if(MBB.terminators(), [](const MachineInstr &MI) {
 126                            unsigned Opc = MI.getOpcode();
 127                            return Opc == AMDGPU::S_CBRANCH_VCCZ ||
 128                                   Opc == AMDGPU::S_CBRANCH_VCCNZ; });
 129   if (I == MBB.terminators().end())
 130     return Register();
 131
 132   auto *And =
 133       TRI->findReachingDef(CondReg, AMDGPU::NoSubRegister, *I, *MRI, LIS);
 134   if (!And || And->getOpcode() != AndOpc ||
 135       !And->getOperand(1).isReg() || !And->getOperand(2).isReg())
 136     return Register();
 137
 138   MachineOperand *AndCC = &And->getOperand(1);
 139   Register CmpReg = AndCC->getReg();
 140   unsigned CmpSubReg = AndCC->getSubReg();
 141   if (CmpReg == Register(ExecReg)) {
 142     AndCC = &And->getOperand(2);
 143     CmpReg = AndCC->getReg();
 144     CmpSubReg = AndCC->getSubReg();
 145   } else if (And->getOperand(2).getReg() != Register(ExecReg)) {
 146     return Register();
 147   }
 148
 149   auto *Cmp = TRI->findReachingDef(CmpReg, CmpSubReg, *And, *MRI, LIS);
 150   if (!Cmp || !(Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e32 ||
 151                 Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e64) ||
 152       Cmp->getParent() != And->getParent())
 153     return Register();
 154
 155   MachineOperand *Op1 = TII->getNamedOperand(*Cmp, AMDGPU::OpName::src0);
 156   MachineOperand *Op2 = TII->getNamedOperand(*Cmp, AMDGPU::OpName::src1);
 157   if (Op1->isImm() && Op2->isReg())
 158     std::swap(Op1, Op2);
 159   if (!Op1->isReg() || !Op2->isImm() || Op2->getImm() != 1)
 160     return Register();
 161
 162   Register SelReg = Op1->getReg();
 163   auto *Sel = TRI->findReachingDef(SelReg, Op1->getSubReg(), *Cmp, *MRI, LIS);
 164   if (!Sel || Sel->getOpcode() != AMDGPU::V_CNDMASK_B32_e64)
 165     return Register();
 166
 167   if (TII->hasModifiersSet(*Sel, AMDGPU::OpName::src0_modifiers) ||
 168       TII->hasModifiersSet(*Sel, AMDGPU::OpName::src1_modifiers))
 169     return Register();
 170
 171   Op1 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src0);
 172   Op2 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src1);
 173   MachineOperand *CC = TII->getNamedOperand(*Sel, AMDGPU::OpName::src2);
 174   if (!Op1->isImm() || !Op2->isImm() || !CC->isReg() ||
 175       Op1->getImm() != 0 || Op2->getImm() != 1)
 176     return Register();
 177
 178   Register CCReg = CC->getReg();
 179
 180   // If there was a def between the select and the and, we would need to move it
 181   // to fold this.
 182   if (isDefBetween(*TRI, LIS, CCReg, *Sel, *And))
 183     return Register();
 184
 185   LLVM_DEBUG(dbgs() << "Folding sequence:\n\t" << *Sel << '\t' << *Cmp << '\t'
 186                     << *And);
 187
 188   LIS->RemoveMachineInstrFromMaps(*And);
 189   MachineInstr *Andn2 =
 190       BuildMI(MBB, *And, And->getDebugLoc(), TII->get(Andn2Opc),
 191               And->getOperand(0).getReg())
 192           .addReg(ExecReg)
 193           .addReg(CCReg, getUndefRegState(CC->isUndef()), CC->getSubReg());
 194   MachineOperand &AndSCC = And->getOperand(3);
 195   assert(AndSCC.getReg() == AMDGPU::SCC);
 196   MachineOperand &Andn2SCC = Andn2->getOperand(3);
 197   assert(Andn2SCC.getReg() == AMDGPU::SCC);
 198   Andn2SCC.setIsDead(AndSCC.isDead());
 199   And->eraseFromParent();
 200   LIS->InsertMachineInstrInMaps(*Andn2);
 201
 202   LLVM_DEBUG(dbgs() << "=>\n\t" << *Andn2 << '\n');
 203
 204   // Try to remove compare. Cmp value should not used in between of cmp
 205   // and s_and_b64 if VCC or just unused if any other register.
 206   if ((CmpReg.isVirtual() && MRI->use_nodbg_empty(CmpReg)) ||
 207       (CmpReg == Register(CondReg) &&
 208        std::none_of(std::next(Cmp->getIterator()), Andn2->getIterator(),
 209                     [&](const MachineInstr &MI) {
 210                       return MI.readsRegister(CondReg, TRI);
 211                     }))) {
 212     LLVM_DEBUG(dbgs() << "Erasing: " << *Cmp << '\n');
 213
 214     LIS->RemoveMachineInstrFromMaps(*Cmp);
 215     Cmp->eraseFromParent();
 216
 217     // Try to remove v_cndmask_b32.
 218     if (SelReg.isVirtual() && MRI->use_nodbg_empty(SelReg)) {
 219       LLVM_DEBUG(dbgs() << "Erasing: " << *Sel << '\n');
 220
 221       LIS->RemoveMachineInstrFromMaps(*Sel);
 222       Sel->eraseFromParent();
 223     }
 224   }
 225
 226   return CCReg;
 227 }
 228
 229 // Optimize sequence
 230 //    %dst = S_OR_SAVEEXEC %src
 231 //    ... instructions not modifying exec ...
 232 //    %tmp = S_AND $exec, %dst
 233 //    $exec = S_XOR_term $exec, %tmp
 234 // =>
 235 //    %dst = S_OR_SAVEEXEC %src
 236 //    ... instructions not modifying exec ...
 237 //    $exec = S_XOR_term $exec, %dst
 238 //
 239 // Clean up potentially unnecessary code added for safety during
 240 // control flow lowering.
 241 //
 242 // Return whether any changes were made to MBB.
 243 bool SIOptimizeExecMaskingPreRA::optimizeElseBranch(MachineBasicBlock &MBB) {
 244   if (MBB.empty())
 245     return false;
 246
 247   // Check this is an else block.
 248   auto First = MBB.begin();
 249   MachineInstr &SaveExecMI = *First;
 250   if (SaveExecMI.getOpcode() != OrSaveExecOpc)
 251     return false;
 252
 253   auto I = llvm::find_if(MBB.terminators(), [this](const MachineInstr &MI) {
 254     return MI.getOpcode() == XorTermrOpc;
 255   });
 256   if (I == MBB.terminators().end())
 257     return false;
 258
 259   MachineInstr &XorTermMI = *I;
 260   if (XorTermMI.getOperand(1).getReg() != Register(ExecReg))
 261     return false;
 262
 263   Register SavedExecReg = SaveExecMI.getOperand(0).getReg();
 264   Register DstReg = XorTermMI.getOperand(2).getReg();
 265
 266   // Find potentially unnecessary S_AND
 267   MachineInstr *AndExecMI = nullptr;
 268   I--;
 269   while (I != First && !AndExecMI) {
 270     if (I->getOpcode() == AndOpc && I->getOperand(0).getReg() == DstReg &&
 271         I->getOperand(1).getReg() == Register(ExecReg))
 272       AndExecMI = &*I;
 273     I--;
 274   }
 275   if (!AndExecMI)
 276     return false;
 277
 278   // Check for exec modifying instructions.
 279   // Note: exec defs do not create live ranges beyond the
 280   // instruction so isDefBetween cannot be used.
 281   // Instead just check that the def segments are adjacent.
 282   SlotIndex StartIdx = LIS->getInstructionIndex(SaveExecMI);
 283   SlotIndex EndIdx = LIS->getInstructionIndex(*AndExecMI);
 284   for (MCRegUnitIterator UI(ExecReg, TRI); UI.isValid(); ++UI) {
 285     LiveRange &RegUnit = LIS->getRegUnit(*UI);
 286     if (RegUnit.find(StartIdx) != std::prev(RegUnit.find(EndIdx)))
 287       return false;
 288   }
 289
 290   // Remove unnecessary S_AND
 291   LIS->removeInterval(SavedExecReg);
 292   LIS->removeInterval(DstReg);
 293
 294   SaveExecMI.getOperand(0).setReg(DstReg);
 295
 296   LIS->RemoveMachineInstrFromMaps(*AndExecMI);
 297   AndExecMI->eraseFromParent();
 298
 299   LIS->createAndComputeVirtRegInterval(DstReg);
 300
 301   return true;
 302 }
 303
 304 bool SIOptimizeExecMaskingPreRA::runOnMachineFunction(MachineFunction &MF) {
 305   if (skipFunction(MF.getFunction()))
 306     return false;
 307
 308   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
 309   TRI = ST.getRegisterInfo();
 310   TII = ST.getInstrInfo();
 311   MRI = &MF.getRegInfo();
 312   LIS = &getAnalysis<LiveIntervals>();
 313
 314   const bool Wave32 = ST.isWave32();
 315   AndOpc = Wave32 ? AMDGPU::S_AND_B32 : AMDGPU::S_AND_B64;
 316   Andn2Opc = Wave32 ? AMDGPU::S_ANDN2_B32 : AMDGPU::S_ANDN2_B64;
 317   OrSaveExecOpc =
 318       Wave32 ? AMDGPU::S_OR_SAVEEXEC_B32 : AMDGPU::S_OR_SAVEEXEC_B64;
 319   XorTermrOpc = Wave32 ? AMDGPU::S_XOR_B32_term : AMDGPU::S_XOR_B64_term;
 320   CondReg = MCRegister::from(Wave32 ? AMDGPU::VCC_LO : AMDGPU::VCC);
 321   ExecReg = MCRegister::from(Wave32 ? AMDGPU::EXEC_LO : AMDGPU::EXEC);
 322
 323   DenseSet<Register> RecalcRegs({AMDGPU::EXEC_LO, AMDGPU::EXEC_HI});
 324   bool Changed = false;
 325
 326   for (MachineBasicBlock &MBB : MF) {
 327
 328     if (optimizeElseBranch(MBB)) {
 329       RecalcRegs.insert(AMDGPU::SCC);
 330       Changed = true;
 331     }
 332
 333     if (Register Reg = optimizeVcndVcmpPair(MBB)) {
 334       RecalcRegs.insert(Reg);
 335       RecalcRegs.insert(AMDGPU::VCC_LO);
 336       RecalcRegs.insert(AMDGPU::VCC_HI);
 337       RecalcRegs.insert(AMDGPU::SCC);
 338       Changed = true;
 339     }
 340
 341     // Try to remove unneeded instructions before s_endpgm.
 342     if (MBB.succ_empty()) {
 343       if (MBB.empty())
 344         continue;
 345
 346       // Skip this if the endpgm has any implicit uses, otherwise we would need
 347       // to be careful to update / remove them.
 348       // S_ENDPGM always has a single imm operand that is not used other than to
 349       // end up in the encoding
 350       MachineInstr &Term = MBB.back();
 351       if (Term.getOpcode() != AMDGPU::S_ENDPGM || Term.getNumOperands() != 1)
 352         continue;
 353
 354       SmallVector<MachineBasicBlock*, 4> Blocks({&MBB});
 355
 356       while (!Blocks.empty()) {
 357         auto CurBB = Blocks.pop_back_val();
 358         auto I = CurBB->rbegin(), E = CurBB->rend();
 359         if (I != E) {
 360           if (I->isUnconditionalBranch() || I->getOpcode() == AMDGPU::S_ENDPGM)
 361             ++I;
 362           else if (I->isBranch())
 363             continue;
 364         }
 365
 366         while (I != E) {
 367           if (I->isDebugInstr()) {
 368             I = std::next(I);
 369             continue;
 370           }
 371
 372           if (I->mayStore() || I->isBarrier() || I->isCall() ||
 373               I->hasUnmodeledSideEffects() || I->hasOrderedMemoryRef())
 374             break;
 375
 376           LLVM_DEBUG(dbgs()
 377                      << "Removing no effect instruction: " << *I << '\n');
 378
 379           for (auto &Op : I->operands()) {
 380             if (Op.isReg())
 381               RecalcRegs.insert(Op.getReg());
 382           }
 383
 384           auto Next = std::next(I);
 385           LIS->RemoveMachineInstrFromMaps(*I);
 386           I->eraseFromParent();
 387           I = Next;
 388
 389           Changed = true;
 390         }
 391
 392         if (I != E)
 393           continue;
 394
 395         // Try to ascend predecessors.
 396         for (auto *Pred : CurBB->predecessors()) {
 397           if (Pred->succ_size() == 1)
 398             Blocks.push_back(Pred);
 399         }
 400       }
 401       continue;
 402     }
 403
 404     // If the only user of a logical operation is move to exec, fold it now
 405     // to prevent forming of saveexec. I.e:
 406     //
 407     //    %0:sreg_64 = COPY $exec
 408     //    %1:sreg_64 = S_AND_B64 %0:sreg_64, %2:sreg_64
 409     // =>
 410     //    %1 = S_AND_B64 $exec, %2:sreg_64
 411     unsigned ScanThreshold = 10;
 412     for (auto I = MBB.rbegin(), E = MBB.rend(); I != E
 413          && ScanThreshold--; ++I) {
 414       // Continue scanning if this is not a full exec copy
 415       if (!(I->isFullCopy() && I->getOperand(1).getReg() == Register(ExecReg)))
 416         continue;
 417
 418       Register SavedExec = I->getOperand(0).getReg();
 419       if (SavedExec.isVirtual() && MRI->hasOneNonDBGUse(SavedExec)) {
 420         MachineInstr *SingleExecUser = &*MRI->use_instr_nodbg_begin(SavedExec);
 421         int Idx = SingleExecUser->findRegisterUseOperandIdx(SavedExec);
 422         assert(Idx != -1);
 423         if (SingleExecUser->getParent() == I->getParent() &&
 424             !SingleExecUser->getOperand(Idx).isImplicit() &&
 425             TII->isOperandLegal(*SingleExecUser, Idx, &I->getOperand(1))) {
 426           LLVM_DEBUG(dbgs() << "Redundant EXEC COPY: " << *I << '\n');
 427           LIS->RemoveMachineInstrFromMaps(*I);
 428           I->eraseFromParent();
 429           MRI->replaceRegWith(SavedExec, ExecReg);
 430           LIS->removeInterval(SavedExec);
 431           Changed = true;
 432         }
 433       }
 434       break;
 435     }
 436   }
 437
 438   if (Changed) {
 439     for (auto Reg : RecalcRegs) {
 440       if (Reg.isVirtual()) {
 441         LIS->removeInterval(Reg);
 442         if (!MRI->reg_empty(Reg))
 443           LIS->createAndComputeVirtRegInterval(Reg);
 444       } else {
 445         LIS->removeAllRegUnitsForPhysReg(Reg);
 446       }
 447     }
 448   }
 449
 450   return Changed;
 451 }