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