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 bool 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).getRegSlot(); 94 SlotIndex SelIdx = LIS->getInstructionIndex(Sel).getRegSlot(); 95 96 if (Reg.isVirtual()) 97 return isDefBetween(LIS->getInterval(Reg), AndIdx, SelIdx); 98 99 for (MCRegUnit Unit : TRI.regunits(Reg.asMCReg())) { 100 if (isDefBetween(LIS->getRegUnit(Unit), 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, %sel 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 true on success. 123 bool SIOptimizeExecMaskingPreRA::optimizeVcndVcmpPair(MachineBasicBlock &MBB) { 124 auto I = llvm::find_if(MBB.terminators(), [](const MachineInstr &MI) { 125 unsigned Opc = MI.getOpcode(); 126 return Opc == AMDGPU::S_CBRANCH_VCCZ || 127 Opc == AMDGPU::S_CBRANCH_VCCNZ; }); 128 if (I == MBB.terminators().end()) 129 return false; 130 131 auto *And = 132 TRI->findReachingDef(CondReg, AMDGPU::NoSubRegister, *I, *MRI, LIS); 133 if (!And || And->getOpcode() != AndOpc || 134 !And->getOperand(1).isReg() || !And->getOperand(2).isReg()) 135 return false; 136 137 MachineOperand *AndCC = &And->getOperand(1); 138 Register CmpReg = AndCC->getReg(); 139 unsigned CmpSubReg = AndCC->getSubReg(); 140 if (CmpReg == Register(ExecReg)) { 141 AndCC = &And->getOperand(2); 142 CmpReg = AndCC->getReg(); 143 CmpSubReg = AndCC->getSubReg(); 144 } else if (And->getOperand(2).getReg() != Register(ExecReg)) { 145 return false; 146 } 147 148 auto *Cmp = TRI->findReachingDef(CmpReg, CmpSubReg, *And, *MRI, LIS); 149 if (!Cmp || !(Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e32 || 150 Cmp->getOpcode() == AMDGPU::V_CMP_NE_U32_e64) || 151 Cmp->getParent() != And->getParent()) 152 return false; 153 154 MachineOperand *Op1 = TII->getNamedOperand(*Cmp, AMDGPU::OpName::src0); 155 MachineOperand *Op2 = TII->getNamedOperand(*Cmp, AMDGPU::OpName::src1); 156 if (Op1->isImm() && Op2->isReg()) 157 std::swap(Op1, Op2); 158 if (!Op1->isReg() || !Op2->isImm() || Op2->getImm() != 1) 159 return false; 160 161 Register SelReg = Op1->getReg(); 162 if (SelReg.isPhysical()) 163 return false; 164 165 auto *Sel = TRI->findReachingDef(SelReg, Op1->getSubReg(), *Cmp, *MRI, LIS); 166 if (!Sel || Sel->getOpcode() != AMDGPU::V_CNDMASK_B32_e64) 167 return false; 168 169 if (TII->hasModifiersSet(*Sel, AMDGPU::OpName::src0_modifiers) || 170 TII->hasModifiersSet(*Sel, AMDGPU::OpName::src1_modifiers)) 171 return false; 172 173 Op1 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src0); 174 Op2 = TII->getNamedOperand(*Sel, AMDGPU::OpName::src1); 175 MachineOperand *CC = TII->getNamedOperand(*Sel, AMDGPU::OpName::src2); 176 if (!Op1->isImm() || !Op2->isImm() || !CC->isReg() || 177 Op1->getImm() != 0 || Op2->getImm() != 1) 178 return false; 179 180 Register CCReg = CC->getReg(); 181 182 // If there was a def between the select and the and, we would need to move it 183 // to fold this. 184 if (isDefBetween(*TRI, LIS, CCReg, *Sel, *And)) 185 return false; 186 187 // Cannot safely mirror live intervals with PHI nodes, so check for these 188 // before optimization. 189 SlotIndex SelIdx = LIS->getInstructionIndex(*Sel); 190 LiveInterval *SelLI = &LIS->getInterval(SelReg); 191 if (llvm::any_of(SelLI->vnis(), 192 [](const VNInfo *VNI) { 193 return VNI->isPHIDef(); 194 })) 195 return false; 196 197 // TODO: Guard against implicit def operands? 198 LLVM_DEBUG(dbgs() << "Folding sequence:\n\t" << *Sel << '\t' << *Cmp << '\t' 199 << *And); 200 201 MachineInstr *Andn2 = 202 BuildMI(MBB, *And, And->getDebugLoc(), TII->get(Andn2Opc), 203 And->getOperand(0).getReg()) 204 .addReg(ExecReg) 205 .addReg(CCReg, getUndefRegState(CC->isUndef()), CC->getSubReg()); 206 MachineOperand &AndSCC = And->getOperand(3); 207 assert(AndSCC.getReg() == AMDGPU::SCC); 208 MachineOperand &Andn2SCC = Andn2->getOperand(3); 209 assert(Andn2SCC.getReg() == AMDGPU::SCC); 210 Andn2SCC.setIsDead(AndSCC.isDead()); 211 212 SlotIndex AndIdx = LIS->ReplaceMachineInstrInMaps(*And, *Andn2); 213 And->eraseFromParent(); 214 215 LLVM_DEBUG(dbgs() << "=>\n\t" << *Andn2 << '\n'); 216 217 // Update live intervals for CCReg before potentially removing CmpReg/SelReg, 218 // and their associated liveness information. 219 SlotIndex CmpIdx = LIS->getInstructionIndex(*Cmp); 220 if (CCReg.isVirtual()) { 221 LiveInterval &CCLI = LIS->getInterval(CCReg); 222 auto CCQ = CCLI.Query(SelIdx.getRegSlot()); 223 if (CCQ.valueIn()) { 224 LIS->removeInterval(CCReg); 225 LIS->createAndComputeVirtRegInterval(CCReg); 226 } 227 } else 228 LIS->removeAllRegUnitsForPhysReg(CCReg); 229 230 // Try to remove compare. Cmp value should not used in between of cmp 231 // and s_and_b64 if VCC or just unused if any other register. 232 LiveInterval *CmpLI = CmpReg.isVirtual() ? &LIS->getInterval(CmpReg) : nullptr; 233 if ((CmpLI && CmpLI->Query(AndIdx.getRegSlot()).isKill()) || 234 (CmpReg == Register(CondReg) && 235 std::none_of(std::next(Cmp->getIterator()), Andn2->getIterator(), 236 [&](const MachineInstr &MI) { 237 return MI.readsRegister(CondReg, TRI); 238 }))) { 239 LLVM_DEBUG(dbgs() << "Erasing: " << *Cmp << '\n'); 240 if (CmpLI) 241 LIS->removeVRegDefAt(*CmpLI, CmpIdx.getRegSlot()); 242 LIS->RemoveMachineInstrFromMaps(*Cmp); 243 Cmp->eraseFromParent(); 244 245 // Try to remove v_cndmask_b32. 246 // Kill status must be checked before shrinking the live range. 247 bool IsKill = SelLI->Query(CmpIdx.getRegSlot()).isKill(); 248 LIS->shrinkToUses(SelLI); 249 bool IsDead = SelLI->Query(SelIdx.getRegSlot()).isDeadDef(); 250 if (MRI->use_nodbg_empty(SelReg) && (IsKill || IsDead)) { 251 LLVM_DEBUG(dbgs() << "Erasing: " << *Sel << '\n'); 252 253 LIS->removeVRegDefAt(*SelLI, SelIdx.getRegSlot()); 254 LIS->RemoveMachineInstrFromMaps(*Sel); 255 bool ShrinkSel = Sel->getOperand(0).readsReg(); 256 Sel->eraseFromParent(); 257 if (ShrinkSel) { 258 // The result of the V_CNDMASK was a subreg def which counted as a read 259 // from the other parts of the reg. Shrink their live ranges. 260 LIS->shrinkToUses(SelLI); 261 } 262 } 263 } 264 265 return true; 266 } 267 268 // Optimize sequence 269 // %dst = S_OR_SAVEEXEC %src 270 // ... instructions not modifying exec ... 271 // %tmp = S_AND $exec, %dst 272 // $exec = S_XOR_term $exec, %tmp 273 // => 274 // %dst = S_OR_SAVEEXEC %src 275 // ... instructions not modifying exec ... 276 // $exec = S_XOR_term $exec, %dst 277 // 278 // Clean up potentially unnecessary code added for safety during 279 // control flow lowering. 280 // 281 // Return whether any changes were made to MBB. 282 bool SIOptimizeExecMaskingPreRA::optimizeElseBranch(MachineBasicBlock &MBB) { 283 if (MBB.empty()) 284 return false; 285 286 // Check this is an else block. 287 auto First = MBB.begin(); 288 MachineInstr &SaveExecMI = *First; 289 if (SaveExecMI.getOpcode() != OrSaveExecOpc) 290 return false; 291 292 auto I = llvm::find_if(MBB.terminators(), [this](const MachineInstr &MI) { 293 return MI.getOpcode() == XorTermrOpc; 294 }); 295 if (I == MBB.terminators().end()) 296 return false; 297 298 MachineInstr &XorTermMI = *I; 299 if (XorTermMI.getOperand(1).getReg() != Register(ExecReg)) 300 return false; 301 302 Register SavedExecReg = SaveExecMI.getOperand(0).getReg(); 303 Register DstReg = XorTermMI.getOperand(2).getReg(); 304 305 // Find potentially unnecessary S_AND 306 MachineInstr *AndExecMI = nullptr; 307 I--; 308 while (I != First && !AndExecMI) { 309 if (I->getOpcode() == AndOpc && I->getOperand(0).getReg() == DstReg && 310 I->getOperand(1).getReg() == Register(ExecReg)) 311 AndExecMI = &*I; 312 I--; 313 } 314 if (!AndExecMI) 315 return false; 316 317 // Check for exec modifying instructions. 318 // Note: exec defs do not create live ranges beyond the 319 // instruction so isDefBetween cannot be used. 320 // Instead just check that the def segments are adjacent. 321 SlotIndex StartIdx = LIS->getInstructionIndex(SaveExecMI); 322 SlotIndex EndIdx = LIS->getInstructionIndex(*AndExecMI); 323 for (MCRegUnit Unit : TRI->regunits(ExecReg)) { 324 LiveRange &RegUnit = LIS->getRegUnit(Unit); 325 if (RegUnit.find(StartIdx) != std::prev(RegUnit.find(EndIdx))) 326 return false; 327 } 328 329 // Remove unnecessary S_AND 330 LIS->removeInterval(SavedExecReg); 331 LIS->removeInterval(DstReg); 332 333 SaveExecMI.getOperand(0).setReg(DstReg); 334 335 LIS->RemoveMachineInstrFromMaps(*AndExecMI); 336 AndExecMI->eraseFromParent(); 337 338 LIS->createAndComputeVirtRegInterval(DstReg); 339 340 return true; 341 } 342 343 bool SIOptimizeExecMaskingPreRA::runOnMachineFunction(MachineFunction &MF) { 344 if (skipFunction(MF.getFunction())) 345 return false; 346 347 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>(); 348 TRI = ST.getRegisterInfo(); 349 TII = ST.getInstrInfo(); 350 MRI = &MF.getRegInfo(); 351 LIS = &getAnalysis<LiveIntervals>(); 352 353 const bool Wave32 = ST.isWave32(); 354 AndOpc = Wave32 ? AMDGPU::S_AND_B32 : AMDGPU::S_AND_B64; 355 Andn2Opc = Wave32 ? AMDGPU::S_ANDN2_B32 : AMDGPU::S_ANDN2_B64; 356 OrSaveExecOpc = 357 Wave32 ? AMDGPU::S_OR_SAVEEXEC_B32 : AMDGPU::S_OR_SAVEEXEC_B64; 358 XorTermrOpc = Wave32 ? AMDGPU::S_XOR_B32_term : AMDGPU::S_XOR_B64_term; 359 CondReg = MCRegister::from(Wave32 ? AMDGPU::VCC_LO : AMDGPU::VCC); 360 ExecReg = MCRegister::from(Wave32 ? AMDGPU::EXEC_LO : AMDGPU::EXEC); 361 362 DenseSet<Register> RecalcRegs({AMDGPU::EXEC_LO, AMDGPU::EXEC_HI}); 363 bool Changed = false; 364 365 for (MachineBasicBlock &MBB : MF) { 366 367 if (optimizeElseBranch(MBB)) { 368 RecalcRegs.insert(AMDGPU::SCC); 369 Changed = true; 370 } 371 372 if (optimizeVcndVcmpPair(MBB)) { 373 RecalcRegs.insert(AMDGPU::VCC_LO); 374 RecalcRegs.insert(AMDGPU::VCC_HI); 375 RecalcRegs.insert(AMDGPU::SCC); 376 Changed = true; 377 } 378 379 // Try to remove unneeded instructions before s_endpgm. 380 if (MBB.succ_empty()) { 381 if (MBB.empty()) 382 continue; 383 384 // Skip this if the endpgm has any implicit uses, otherwise we would need 385 // to be careful to update / remove them. 386 // S_ENDPGM always has a single imm operand that is not used other than to 387 // end up in the encoding 388 MachineInstr &Term = MBB.back(); 389 if (Term.getOpcode() != AMDGPU::S_ENDPGM || Term.getNumOperands() != 1) 390 continue; 391 392 SmallVector<MachineBasicBlock*, 4> Blocks({&MBB}); 393 394 while (!Blocks.empty()) { 395 auto CurBB = Blocks.pop_back_val(); 396 auto I = CurBB->rbegin(), E = CurBB->rend(); 397 if (I != E) { 398 if (I->isUnconditionalBranch() || I->getOpcode() == AMDGPU::S_ENDPGM) 399 ++I; 400 else if (I->isBranch()) 401 continue; 402 } 403 404 while (I != E) { 405 if (I->isDebugInstr()) { 406 I = std::next(I); 407 continue; 408 } 409 410 if (I->mayStore() || I->isBarrier() || I->isCall() || 411 I->hasUnmodeledSideEffects() || I->hasOrderedMemoryRef()) 412 break; 413 414 LLVM_DEBUG(dbgs() 415 << "Removing no effect instruction: " << *I << '\n'); 416 417 for (auto &Op : I->operands()) { 418 if (Op.isReg()) 419 RecalcRegs.insert(Op.getReg()); 420 } 421 422 auto Next = std::next(I); 423 LIS->RemoveMachineInstrFromMaps(*I); 424 I->eraseFromParent(); 425 I = Next; 426 427 Changed = true; 428 } 429 430 if (I != E) 431 continue; 432 433 // Try to ascend predecessors. 434 for (auto *Pred : CurBB->predecessors()) { 435 if (Pred->succ_size() == 1) 436 Blocks.push_back(Pred); 437 } 438 } 439 continue; 440 } 441 442 // If the only user of a logical operation is move to exec, fold it now 443 // to prevent forming of saveexec. I.e.: 444 // 445 // %0:sreg_64 = COPY $exec 446 // %1:sreg_64 = S_AND_B64 %0:sreg_64, %2:sreg_64 447 // => 448 // %1 = S_AND_B64 $exec, %2:sreg_64 449 unsigned ScanThreshold = 10; 450 for (auto I = MBB.rbegin(), E = MBB.rend(); I != E 451 && ScanThreshold--; ++I) { 452 // Continue scanning if this is not a full exec copy 453 if (!(I->isFullCopy() && I->getOperand(1).getReg() == Register(ExecReg))) 454 continue; 455 456 Register SavedExec = I->getOperand(0).getReg(); 457 if (SavedExec.isVirtual() && MRI->hasOneNonDBGUse(SavedExec)) { 458 MachineInstr *SingleExecUser = &*MRI->use_instr_nodbg_begin(SavedExec); 459 int Idx = SingleExecUser->findRegisterUseOperandIdx(SavedExec); 460 assert(Idx != -1); 461 if (SingleExecUser->getParent() == I->getParent() && 462 !SingleExecUser->getOperand(Idx).isImplicit() && 463 TII->isOperandLegal(*SingleExecUser, Idx, &I->getOperand(1))) { 464 LLVM_DEBUG(dbgs() << "Redundant EXEC COPY: " << *I << '\n'); 465 LIS->RemoveMachineInstrFromMaps(*I); 466 I->eraseFromParent(); 467 MRI->replaceRegWith(SavedExec, ExecReg); 468 LIS->removeInterval(SavedExec); 469 Changed = true; 470 } 471 } 472 break; 473 } 474 } 475 476 if (Changed) { 477 for (auto Reg : RecalcRegs) { 478 if (Reg.isVirtual()) { 479 LIS->removeInterval(Reg); 480 if (!MRI->reg_empty(Reg)) 481 LIS->createAndComputeVirtRegInterval(Reg); 482 } else { 483 LIS->removeAllRegUnitsForPhysReg(Reg); 484 } 485 } 486 } 487 488 return Changed; 489 } 490