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