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