1 //===- HexagonGenPredicate.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 "Hexagon.h" 10 #include "HexagonInstrInfo.h" 11 #include "HexagonSubtarget.h" 12 #include "llvm/ADT/SetVector.h" 13 #include "llvm/ADT/StringRef.h" 14 #include "llvm/CodeGen/MachineBasicBlock.h" 15 #include "llvm/CodeGen/MachineDominators.h" 16 #include "llvm/CodeGen/MachineFunction.h" 17 #include "llvm/CodeGen/MachineFunctionPass.h" 18 #include "llvm/CodeGen/MachineInstr.h" 19 #include "llvm/CodeGen/MachineInstrBuilder.h" 20 #include "llvm/CodeGen/MachineOperand.h" 21 #include "llvm/CodeGen/MachineRegisterInfo.h" 22 #include "llvm/CodeGen/TargetRegisterInfo.h" 23 #include "llvm/IR/DebugLoc.h" 24 #include "llvm/InitializePasses.h" 25 #include "llvm/Pass.h" 26 #include "llvm/Support/Compiler.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/ErrorHandling.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include <cassert> 31 #include <iterator> 32 #include <queue> 33 #include <utility> 34 35 #define DEBUG_TYPE "gen-pred" 36 37 using namespace llvm; 38 39 namespace { 40 41 using RegSubRegPair = TargetInstrInfo::RegSubRegPair; 42 43 struct PrintRegister { 44 friend raw_ostream &operator<<(raw_ostream &OS, const PrintRegister &PR); 45 46 PrintRegister(RegSubRegPair R, const TargetRegisterInfo &I) 47 : Reg(R), TRI(I) {} 48 49 private: 50 RegSubRegPair Reg; 51 const TargetRegisterInfo &TRI; 52 }; 53 54 raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) 55 LLVM_ATTRIBUTE_UNUSED; 56 raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) { 57 return OS << printReg(PR.Reg.Reg, &PR.TRI, PR.Reg.SubReg); 58 } 59 60 class HexagonGenPredicate : public MachineFunctionPass { 61 public: 62 static char ID; 63 64 HexagonGenPredicate() : MachineFunctionPass(ID) {} 65 66 StringRef getPassName() const override { 67 return "Hexagon generate predicate operations"; 68 } 69 70 void getAnalysisUsage(AnalysisUsage &AU) const override { 71 AU.addRequired<MachineDominatorTreeWrapperPass>(); 72 AU.addPreserved<MachineDominatorTreeWrapperPass>(); 73 MachineFunctionPass::getAnalysisUsage(AU); 74 } 75 76 bool runOnMachineFunction(MachineFunction &MF) override; 77 78 private: 79 using VectOfInst = SetVector<MachineInstr *>; 80 using SetOfReg = SetVector<RegSubRegPair>; 81 using RegToRegMap = DenseMap<RegSubRegPair, RegSubRegPair>; 82 83 const HexagonInstrInfo *TII = nullptr; 84 const HexagonRegisterInfo *TRI = nullptr; 85 MachineRegisterInfo *MRI = nullptr; 86 SetOfReg PredGPRs; 87 VectOfInst PUsers; 88 RegToRegMap G2P; 89 90 bool isPredReg(Register R); 91 void collectPredicateGPR(MachineFunction &MF); 92 void processPredicateGPR(const RegSubRegPair &Reg); 93 unsigned getPredForm(unsigned Opc); 94 bool isConvertibleToPredForm(const MachineInstr *MI); 95 bool isScalarCmp(unsigned Opc); 96 bool isScalarPred(RegSubRegPair PredReg); 97 RegSubRegPair getPredRegFor(const RegSubRegPair &Reg); 98 bool convertToPredForm(MachineInstr *MI); 99 bool eliminatePredCopies(MachineFunction &MF); 100 }; 101 102 } // end anonymous namespace 103 104 char HexagonGenPredicate::ID = 0; 105 106 INITIALIZE_PASS_BEGIN(HexagonGenPredicate, "hexagon-gen-pred-pass", 107 "Hexagon generate predicate operations", false, false) 108 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) 109 INITIALIZE_PASS_END(HexagonGenPredicate, "hexagon-gen-pred-pass", 110 "Hexagon generate predicate operations", false, false) 111 112 bool HexagonGenPredicate::isPredReg(Register R) { 113 if (!R.isVirtual()) 114 return false; 115 const TargetRegisterClass *RC = MRI->getRegClass(R); 116 return RC == &Hexagon::PredRegsRegClass; 117 } 118 119 unsigned HexagonGenPredicate::getPredForm(unsigned Opc) { 120 using namespace Hexagon; 121 122 switch (Opc) { 123 case A2_and: 124 case A2_andp: 125 return C2_and; 126 case A4_andn: 127 case A4_andnp: 128 return C2_andn; 129 case M4_and_and: 130 return C4_and_and; 131 case M4_and_andn: 132 return C4_and_andn; 133 case M4_and_or: 134 return C4_and_or; 135 136 case A2_or: 137 case A2_orp: 138 return C2_or; 139 case A4_orn: 140 case A4_ornp: 141 return C2_orn; 142 case M4_or_and: 143 return C4_or_and; 144 case M4_or_andn: 145 return C4_or_andn; 146 case M4_or_or: 147 return C4_or_or; 148 149 case A2_xor: 150 case A2_xorp: 151 return C2_xor; 152 153 case C2_tfrrp: 154 return COPY; 155 } 156 // The opcode corresponding to 0 is TargetOpcode::PHI. We can use 0 here 157 // to denote "none", but we need to make sure that none of the valid opcodes 158 // that we return will ever be 0. 159 static_assert(PHI == 0, "Use different value for <none>"); 160 return 0; 161 } 162 163 bool HexagonGenPredicate::isConvertibleToPredForm(const MachineInstr *MI) { 164 unsigned Opc = MI->getOpcode(); 165 if (getPredForm(Opc) != 0) 166 return true; 167 168 // Comparisons against 0 are also convertible. This does not apply to 169 // A4_rcmpeqi or A4_rcmpneqi, since they produce values 0 or 1, which 170 // may not match the value that the predicate register would have if 171 // it was converted to a predicate form. 172 switch (Opc) { 173 case Hexagon::C2_cmpeqi: 174 case Hexagon::C4_cmpneqi: 175 if (MI->getOperand(2).isImm() && MI->getOperand(2).getImm() == 0) 176 return true; 177 break; 178 } 179 return false; 180 } 181 182 void HexagonGenPredicate::collectPredicateGPR(MachineFunction &MF) { 183 for (MachineBasicBlock &B : MF) { 184 for (MachineInstr &MI : B) { 185 unsigned Opc = MI.getOpcode(); 186 switch (Opc) { 187 case Hexagon::C2_tfrpr: 188 case TargetOpcode::COPY: 189 if (isPredReg(MI.getOperand(1).getReg())) { 190 RegSubRegPair RD = getRegSubRegPair(MI.getOperand(0)); 191 if (RD.Reg.isVirtual()) 192 PredGPRs.insert(RD); 193 } 194 break; 195 } 196 } 197 } 198 } 199 200 void HexagonGenPredicate::processPredicateGPR(const RegSubRegPair &Reg) { 201 LLVM_DEBUG(dbgs() << __func__ << ": " << printReg(Reg.Reg, TRI, Reg.SubReg) 202 << "\n"); 203 using use_iterator = MachineRegisterInfo::use_iterator; 204 205 use_iterator I = MRI->use_begin(Reg.Reg), E = MRI->use_end(); 206 if (I == E) { 207 LLVM_DEBUG(dbgs() << "Dead reg: " << printReg(Reg.Reg, TRI, Reg.SubReg) 208 << '\n'); 209 MachineInstr *DefI = MRI->getVRegDef(Reg.Reg); 210 DefI->eraseFromParent(); 211 return; 212 } 213 214 for (; I != E; ++I) { 215 MachineInstr *UseI = I->getParent(); 216 if (isConvertibleToPredForm(UseI)) 217 PUsers.insert(UseI); 218 } 219 } 220 221 RegSubRegPair HexagonGenPredicate::getPredRegFor(const RegSubRegPair &Reg) { 222 // Create a predicate register for a given Reg. The newly created register 223 // will have its value copied from Reg, so that it can be later used as 224 // an operand in other instructions. 225 assert(Reg.Reg.isVirtual()); 226 RegToRegMap::iterator F = G2P.find(Reg); 227 if (F != G2P.end()) 228 return F->second; 229 230 LLVM_DEBUG(dbgs() << __func__ << ": " << PrintRegister(Reg, *TRI)); 231 MachineInstr *DefI = MRI->getVRegDef(Reg.Reg); 232 assert(DefI); 233 unsigned Opc = DefI->getOpcode(); 234 if (Opc == Hexagon::C2_tfrpr || Opc == TargetOpcode::COPY) { 235 assert(DefI->getOperand(0).isDef() && DefI->getOperand(1).isUse()); 236 RegSubRegPair PR = getRegSubRegPair(DefI->getOperand(1)); 237 G2P.insert(std::make_pair(Reg, PR)); 238 LLVM_DEBUG(dbgs() << " -> " << PrintRegister(PR, *TRI) << '\n'); 239 return PR; 240 } 241 242 MachineBasicBlock &B = *DefI->getParent(); 243 DebugLoc DL = DefI->getDebugLoc(); 244 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; 245 Register NewPR = MRI->createVirtualRegister(PredRC); 246 247 // For convertible instructions, do not modify them, so that they can 248 // be converted later. Generate a copy from Reg to NewPR. 249 if (isConvertibleToPredForm(DefI)) { 250 MachineBasicBlock::iterator DefIt = DefI; 251 BuildMI(B, std::next(DefIt), DL, TII->get(TargetOpcode::COPY), NewPR) 252 .addReg(Reg.Reg, 0, Reg.SubReg); 253 G2P.insert(std::make_pair(Reg, RegSubRegPair(NewPR))); 254 LLVM_DEBUG(dbgs() << " -> !" << PrintRegister(RegSubRegPair(NewPR), *TRI) 255 << '\n'); 256 return RegSubRegPair(NewPR); 257 } 258 259 llvm_unreachable("Invalid argument"); 260 } 261 262 bool HexagonGenPredicate::isScalarCmp(unsigned Opc) { 263 switch (Opc) { 264 case Hexagon::C2_cmpeq: 265 case Hexagon::C2_cmpgt: 266 case Hexagon::C2_cmpgtu: 267 case Hexagon::C2_cmpeqp: 268 case Hexagon::C2_cmpgtp: 269 case Hexagon::C2_cmpgtup: 270 case Hexagon::C2_cmpeqi: 271 case Hexagon::C2_cmpgti: 272 case Hexagon::C2_cmpgtui: 273 case Hexagon::C2_cmpgei: 274 case Hexagon::C2_cmpgeui: 275 case Hexagon::C4_cmpneqi: 276 case Hexagon::C4_cmpltei: 277 case Hexagon::C4_cmplteui: 278 case Hexagon::C4_cmpneq: 279 case Hexagon::C4_cmplte: 280 case Hexagon::C4_cmplteu: 281 case Hexagon::A4_cmpbeq: 282 case Hexagon::A4_cmpbeqi: 283 case Hexagon::A4_cmpbgtu: 284 case Hexagon::A4_cmpbgtui: 285 case Hexagon::A4_cmpbgt: 286 case Hexagon::A4_cmpbgti: 287 case Hexagon::A4_cmpheq: 288 case Hexagon::A4_cmphgt: 289 case Hexagon::A4_cmphgtu: 290 case Hexagon::A4_cmpheqi: 291 case Hexagon::A4_cmphgti: 292 case Hexagon::A4_cmphgtui: 293 return true; 294 } 295 return false; 296 } 297 298 bool HexagonGenPredicate::isScalarPred(RegSubRegPair PredReg) { 299 std::queue<RegSubRegPair> WorkQ; 300 WorkQ.push(PredReg); 301 302 while (!WorkQ.empty()) { 303 RegSubRegPair PR = WorkQ.front(); 304 WorkQ.pop(); 305 const MachineInstr *DefI = MRI->getVRegDef(PR.Reg); 306 if (!DefI) 307 return false; 308 unsigned DefOpc = DefI->getOpcode(); 309 switch (DefOpc) { 310 case TargetOpcode::COPY: { 311 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; 312 if (MRI->getRegClass(PR.Reg) != PredRC) 313 return false; 314 // If it is a copy between two predicate registers, fall through. 315 [[fallthrough]]; 316 } 317 case Hexagon::C2_and: 318 case Hexagon::C2_andn: 319 case Hexagon::C4_and_and: 320 case Hexagon::C4_and_andn: 321 case Hexagon::C4_and_or: 322 case Hexagon::C2_or: 323 case Hexagon::C2_orn: 324 case Hexagon::C4_or_and: 325 case Hexagon::C4_or_andn: 326 case Hexagon::C4_or_or: 327 case Hexagon::C4_or_orn: 328 case Hexagon::C2_xor: 329 // Add operands to the queue. 330 for (const MachineOperand &MO : DefI->operands()) 331 if (MO.isReg() && MO.isUse()) 332 WorkQ.push(RegSubRegPair(MO.getReg())); 333 break; 334 335 // All non-vector compares are ok, everything else is bad. 336 default: 337 return isScalarCmp(DefOpc); 338 } 339 } 340 341 return true; 342 } 343 344 bool HexagonGenPredicate::convertToPredForm(MachineInstr *MI) { 345 LLVM_DEBUG(dbgs() << __func__ << ": " << MI << " " << *MI); 346 347 unsigned Opc = MI->getOpcode(); 348 assert(isConvertibleToPredForm(MI)); 349 unsigned NumOps = MI->getNumOperands(); 350 for (unsigned i = 0; i < NumOps; ++i) { 351 MachineOperand &MO = MI->getOperand(i); 352 if (!MO.isReg() || !MO.isUse()) 353 continue; 354 RegSubRegPair Reg(getRegSubRegPair(MO)); 355 if (Reg.SubReg && Reg.SubReg != Hexagon::isub_lo) 356 return false; 357 if (!PredGPRs.count(Reg)) 358 return false; 359 } 360 361 MachineBasicBlock &B = *MI->getParent(); 362 DebugLoc DL = MI->getDebugLoc(); 363 364 unsigned NewOpc = getPredForm(Opc); 365 // Special case for comparisons against 0. 366 if (NewOpc == 0) { 367 switch (Opc) { 368 case Hexagon::C2_cmpeqi: 369 NewOpc = Hexagon::C2_not; 370 break; 371 case Hexagon::C4_cmpneqi: 372 NewOpc = TargetOpcode::COPY; 373 break; 374 default: 375 return false; 376 } 377 378 // If it's a scalar predicate register, then all bits in it are 379 // the same. Otherwise, to determine whether all bits are 0 or not 380 // we would need to use any8. 381 RegSubRegPair PR = getPredRegFor(getRegSubRegPair(MI->getOperand(1))); 382 if (!isScalarPred(PR)) 383 return false; 384 // This will skip the immediate argument when creating the predicate 385 // version instruction. 386 NumOps = 2; 387 } 388 389 // Check that def is in operand #0. 390 MachineOperand &Op0 = MI->getOperand(0); 391 assert(Op0.isDef()); 392 RegSubRegPair OutR(getRegSubRegPair(Op0)); 393 394 // Don't use getPredRegFor, since it will create an association between 395 // the argument and a created predicate register (i.e. it will insert a 396 // copy if a new predicate register is created). 397 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; 398 RegSubRegPair NewPR = MRI->createVirtualRegister(PredRC); 399 MachineInstrBuilder MIB = BuildMI(B, MI, DL, TII->get(NewOpc), NewPR.Reg); 400 401 // Add predicate counterparts of the GPRs. 402 for (unsigned i = 1; i < NumOps; ++i) { 403 RegSubRegPair GPR = getRegSubRegPair(MI->getOperand(i)); 404 RegSubRegPair Pred = getPredRegFor(GPR); 405 MIB.addReg(Pred.Reg, 0, Pred.SubReg); 406 } 407 LLVM_DEBUG(dbgs() << "generated: " << *MIB); 408 409 // Generate a copy-out: NewGPR = NewPR, and replace all uses of OutR 410 // with NewGPR. 411 const TargetRegisterClass *RC = MRI->getRegClass(OutR.Reg); 412 Register NewOutR = MRI->createVirtualRegister(RC); 413 BuildMI(B, MI, DL, TII->get(TargetOpcode::COPY), NewOutR) 414 .addReg(NewPR.Reg, 0, NewPR.SubReg); 415 MRI->replaceRegWith(OutR.Reg, NewOutR); 416 MI->eraseFromParent(); 417 418 // If the processed instruction was C2_tfrrp (i.e. Rn = Pm; Pk = Rn), 419 // then the output will be a predicate register. Do not visit the 420 // users of it. 421 if (!isPredReg(NewOutR)) { 422 RegSubRegPair R(NewOutR); 423 PredGPRs.insert(R); 424 processPredicateGPR(R); 425 } 426 return true; 427 } 428 429 bool HexagonGenPredicate::eliminatePredCopies(MachineFunction &MF) { 430 LLVM_DEBUG(dbgs() << __func__ << "\n"); 431 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; 432 bool Changed = false; 433 VectOfInst Erase; 434 435 // First, replace copies 436 // IntR = PredR1 437 // PredR2 = IntR 438 // with 439 // PredR2 = PredR1 440 // Such sequences can be generated when a copy-into-pred is generated from 441 // a gpr register holding a result of a convertible instruction. After 442 // the convertible instruction is converted, its predicate result will be 443 // copied back into the original gpr. 444 445 for (MachineBasicBlock &MBB : MF) { 446 for (MachineInstr &MI : MBB) { 447 if (MI.getOpcode() != TargetOpcode::COPY) 448 continue; 449 RegSubRegPair DR = getRegSubRegPair(MI.getOperand(0)); 450 RegSubRegPair SR = getRegSubRegPair(MI.getOperand(1)); 451 if (!DR.Reg.isVirtual()) 452 continue; 453 if (!SR.Reg.isVirtual()) 454 continue; 455 if (MRI->getRegClass(DR.Reg) != PredRC) 456 continue; 457 if (MRI->getRegClass(SR.Reg) != PredRC) 458 continue; 459 assert(!DR.SubReg && !SR.SubReg && "Unexpected subregister"); 460 MRI->replaceRegWith(DR.Reg, SR.Reg); 461 Erase.insert(&MI); 462 Changed = true; 463 } 464 } 465 466 for (MachineInstr *MI : Erase) 467 MI->eraseFromParent(); 468 469 return Changed; 470 } 471 472 bool HexagonGenPredicate::runOnMachineFunction(MachineFunction &MF) { 473 if (skipFunction(MF.getFunction())) 474 return false; 475 476 TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); 477 TRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo(); 478 MRI = &MF.getRegInfo(); 479 PredGPRs.clear(); 480 PUsers.clear(); 481 G2P.clear(); 482 483 bool Changed = false; 484 collectPredicateGPR(MF); 485 for (const RegSubRegPair &R : PredGPRs) 486 processPredicateGPR(R); 487 488 bool Again; 489 do { 490 Again = false; 491 VectOfInst Processed, Copy; 492 493 Copy = PUsers; 494 for (MachineInstr *MI : Copy) { 495 bool Done = convertToPredForm(MI); 496 if (Done) { 497 Processed.insert(MI); 498 Again = true; 499 } 500 } 501 Changed |= Again; 502 503 auto Done = [Processed] (MachineInstr *MI) -> bool { 504 return Processed.count(MI); 505 }; 506 PUsers.remove_if(Done); 507 } while (Again); 508 509 Changed |= eliminatePredCopies(MF); 510 return Changed; 511 } 512 513 FunctionPass *llvm::createHexagonGenPredicate() { 514 return new HexagonGenPredicate(); 515 } 516