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