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