lib/Target/Hexagon/HexagonGenPredicate.cpp

   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   // FIXME: Use TargetInstrInfo::RegSubRegPair
  49   struct RegisterSubReg {
  50     unsigned R, S;
  51
  52     RegisterSubReg(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
  53     RegisterSubReg(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
  54     RegisterSubReg(const Register &Reg) : R(Reg), S(0) {}
  55
  56     bool operator== (const RegisterSubReg &Reg) const {
  57       return R == Reg.R && S == Reg.S;
  58     }
  59
  60     bool operator< (const RegisterSubReg &Reg) const {
  61       return R < Reg.R || (R == Reg.R && S < Reg.S);
  62     }
  63   };
  64
  65   struct PrintRegister {
  66     friend raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR);
  67
  68     PrintRegister(RegisterSubReg R, const TargetRegisterInfo &I) : Reg(R), TRI(I) {}
  69
  70   private:
  71     RegisterSubReg Reg;
  72     const TargetRegisterInfo &TRI;
  73   };
  74
  75   raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR)
  76     LLVM_ATTRIBUTE_UNUSED;
  77   raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) {
  78     return OS << printReg(PR.Reg.R, &PR.TRI, PR.Reg.S);
  79   }
  80
  81   class HexagonGenPredicate : public MachineFunctionPass {
  82   public:
  83     static char ID;
  84
  85     HexagonGenPredicate() : MachineFunctionPass(ID) {
  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     using VectOfInst = SetVector<MachineInstr *>;
 103     using SetOfReg = std::set<RegisterSubReg>;
 104     using RegToRegMap = std::map<RegisterSubReg, RegisterSubReg>;
 105
 106     const HexagonInstrInfo *TII = nullptr;
 107     const HexagonRegisterInfo *TRI = nullptr;
 108     MachineRegisterInfo *MRI = nullptr;
 109     SetOfReg PredGPRs;
 110     VectOfInst PUsers;
 111     RegToRegMap G2P;
 112
 113     bool isPredReg(unsigned R);
 114     void collectPredicateGPR(MachineFunction &MF);
 115     void processPredicateGPR(const RegisterSubReg &Reg);
 116     unsigned getPredForm(unsigned Opc);
 117     bool isConvertibleToPredForm(const MachineInstr *MI);
 118     bool isScalarCmp(unsigned Opc);
 119     bool isScalarPred(RegisterSubReg PredReg);
 120     RegisterSubReg getPredRegFor(const RegisterSubReg &Reg);
 121     bool convertToPredForm(MachineInstr *MI);
 122     bool eliminatePredCopies(MachineFunction &MF);
 123   };
 124
 125 } // end anonymous namespace
 126
 127 char HexagonGenPredicate::ID = 0;
 128
 129 INITIALIZE_PASS_BEGIN(HexagonGenPredicate, "hexagon-gen-pred",
 130   "Hexagon generate predicate operations", false, false)
 131 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 132 INITIALIZE_PASS_END(HexagonGenPredicate, "hexagon-gen-pred",
 133   "Hexagon generate predicate operations", false, false)
 134
 135 bool HexagonGenPredicate::isPredReg(unsigned R) {
 136   if (!Register::isVirtualRegister(R))
 137     return false;
 138   const TargetRegisterClass *RC = MRI->getRegClass(R);
 139   return RC == &Hexagon::PredRegsRegClass;
 140 }
 141
 142 unsigned 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
 186 bool 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
 205 void 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             RegisterSubReg RD = MI->getOperand(0);
 216             if (Register::isVirtualRegister(RD.R))
 217               PredGPRs.insert(RD);
 218           }
 219           break;
 220       }
 221     }
 222   }
 223 }
 224
 225 void HexagonGenPredicate::processPredicateGPR(const RegisterSubReg &Reg) {
 226   LLVM_DEBUG(dbgs() << __func__ << ": " << printReg(Reg.R, TRI, Reg.S) << "\n");
 227   using use_iterator = MachineRegisterInfo::use_iterator;
 228
 229   use_iterator I = MRI->use_begin(Reg.R), E = MRI->use_end();
 230   if (I == E) {
 231     LLVM_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
 244 RegisterSubReg HexagonGenPredicate::getPredRegFor(const RegisterSubReg &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(Register::isVirtualRegister(Reg.R));
 249   RegToRegMap::iterator F = G2P.find(Reg);
 250   if (F != G2P.end())
 251     return F->second;
 252
 253   LLVM_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     RegisterSubReg PR = DefI->getOperand(1);
 260     G2P.insert(std::make_pair(Reg, PR));
 261     LLVM_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   Register 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, RegisterSubReg(NewPR)));
 277     LLVM_DEBUG(dbgs() << " -> !" << PrintRegister(RegisterSubReg(NewPR), *TRI)
 278                       << '\n');
 279     return RegisterSubReg(NewPR);
 280   }
 281
 282   llvm_unreachable("Invalid argument");
 283 }
 284
 285 bool HexagonGenPredicate::isScalarCmp(unsigned Opc) {
 286   switch (Opc) {
 287     case Hexagon::C2_cmpeq:
 288     case Hexagon::C2_cmpgt:
 289     case Hexagon::C2_cmpgtu:
 290     case Hexagon::C2_cmpeqp:
 291     case Hexagon::C2_cmpgtp:
 292     case Hexagon::C2_cmpgtup:
 293     case Hexagon::C2_cmpeqi:
 294     case Hexagon::C2_cmpgti:
 295     case Hexagon::C2_cmpgtui:
 296     case Hexagon::C2_cmpgei:
 297     case Hexagon::C2_cmpgeui:
 298     case Hexagon::C4_cmpneqi:
 299     case Hexagon::C4_cmpltei:
 300     case Hexagon::C4_cmplteui:
 301     case Hexagon::C4_cmpneq:
 302     case Hexagon::C4_cmplte:
 303     case Hexagon::C4_cmplteu:
 304     case Hexagon::A4_cmpbeq:
 305     case Hexagon::A4_cmpbeqi:
 306     case Hexagon::A4_cmpbgtu:
 307     case Hexagon::A4_cmpbgtui:
 308     case Hexagon::A4_cmpbgt:
 309     case Hexagon::A4_cmpbgti:
 310     case Hexagon::A4_cmpheq:
 311     case Hexagon::A4_cmphgt:
 312     case Hexagon::A4_cmphgtu:
 313     case Hexagon::A4_cmpheqi:
 314     case Hexagon::A4_cmphgti:
 315     case Hexagon::A4_cmphgtui:
 316       return true;
 317   }
 318   return false;
 319 }
 320
 321 bool HexagonGenPredicate::isScalarPred(RegisterSubReg PredReg) {
 322   std::queue<RegisterSubReg> WorkQ;
 323   WorkQ.push(PredReg);
 324
 325   while (!WorkQ.empty()) {
 326     RegisterSubReg PR = WorkQ.front();
 327     WorkQ.pop();
 328     const MachineInstr *DefI = MRI->getVRegDef(PR.R);
 329     if (!DefI)
 330       return false;
 331     unsigned DefOpc = DefI->getOpcode();
 332     switch (DefOpc) {
 333       case TargetOpcode::COPY: {
 334         const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 335         if (MRI->getRegClass(PR.R) != PredRC)
 336           return false;
 337         // If it is a copy between two predicate registers, fall through.
 338         LLVM_FALLTHROUGH;
 339       }
 340       case Hexagon::C2_and:
 341       case Hexagon::C2_andn:
 342       case Hexagon::C4_and_and:
 343       case Hexagon::C4_and_andn:
 344       case Hexagon::C4_and_or:
 345       case Hexagon::C2_or:
 346       case Hexagon::C2_orn:
 347       case Hexagon::C4_or_and:
 348       case Hexagon::C4_or_andn:
 349       case Hexagon::C4_or_or:
 350       case Hexagon::C4_or_orn:
 351       case Hexagon::C2_xor:
 352         // Add operands to the queue.
 353         for (const MachineOperand &MO : DefI->operands())
 354           if (MO.isReg() && MO.isUse())
 355             WorkQ.push(RegisterSubReg(MO.getReg()));
 356         break;
 357
 358       // All non-vector compares are ok, everything else is bad.
 359       default:
 360         return isScalarCmp(DefOpc);
 361     }
 362   }
 363
 364   return true;
 365 }
 366
 367 bool HexagonGenPredicate::convertToPredForm(MachineInstr *MI) {
 368   LLVM_DEBUG(dbgs() << __func__ << ": " << MI << " " << *MI);
 369
 370   unsigned Opc = MI->getOpcode();
 371   assert(isConvertibleToPredForm(MI));
 372   unsigned NumOps = MI->getNumOperands();
 373   for (unsigned i = 0; i < NumOps; ++i) {
 374     MachineOperand &MO = MI->getOperand(i);
 375     if (!MO.isReg() || !MO.isUse())
 376       continue;
 377     RegisterSubReg Reg(MO);
 378     if (Reg.S && Reg.S != Hexagon::isub_lo)
 379       return false;
 380     if (!PredGPRs.count(Reg))
 381       return false;
 382   }
 383
 384   MachineBasicBlock &B = *MI->getParent();
 385   DebugLoc DL = MI->getDebugLoc();
 386
 387   unsigned NewOpc = getPredForm(Opc);
 388   // Special case for comparisons against 0.
 389   if (NewOpc == 0) {
 390     switch (Opc) {
 391       case Hexagon::C2_cmpeqi:
 392         NewOpc = Hexagon::C2_not;
 393         break;
 394       case Hexagon::C4_cmpneqi:
 395         NewOpc = TargetOpcode::COPY;
 396         break;
 397       default:
 398         return false;
 399     }
 400
 401     // If it's a scalar predicate register, then all bits in it are
 402     // the same. Otherwise, to determine whether all bits are 0 or not
 403     // we would need to use any8.
 404     RegisterSubReg PR = getPredRegFor(MI->getOperand(1));
 405     if (!isScalarPred(PR))
 406       return false;
 407     // This will skip the immediate argument when creating the predicate
 408     // version instruction.
 409     NumOps = 2;
 410   }
 411
 412   // Some sanity: check that def is in operand #0.
 413   MachineOperand &Op0 = MI->getOperand(0);
 414   assert(Op0.isDef());
 415   RegisterSubReg OutR(Op0);
 416
 417   // Don't use getPredRegFor, since it will create an association between
 418   // the argument and a created predicate register (i.e. it will insert a
 419   // copy if a new predicate register is created).
 420   const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 421   RegisterSubReg NewPR = MRI->createVirtualRegister(PredRC);
 422   MachineInstrBuilder MIB = BuildMI(B, MI, DL, TII->get(NewOpc), NewPR.R);
 423
 424   // Add predicate counterparts of the GPRs.
 425   for (unsigned i = 1; i < NumOps; ++i) {
 426     RegisterSubReg GPR = MI->getOperand(i);
 427     RegisterSubReg Pred = getPredRegFor(GPR);
 428     MIB.addReg(Pred.R, 0, Pred.S);
 429   }
 430   LLVM_DEBUG(dbgs() << "generated: " << *MIB);
 431
 432   // Generate a copy-out: NewGPR = NewPR, and replace all uses of OutR
 433   // with NewGPR.
 434   const TargetRegisterClass *RC = MRI->getRegClass(OutR.R);
 435   Register NewOutR = MRI->createVirtualRegister(RC);
 436   BuildMI(B, MI, DL, TII->get(TargetOpcode::COPY), NewOutR)
 437     .addReg(NewPR.R, 0, NewPR.S);
 438   MRI->replaceRegWith(OutR.R, NewOutR);
 439   MI->eraseFromParent();
 440
 441   // If the processed instruction was C2_tfrrp (i.e. Rn = Pm; Pk = Rn),
 442   // then the output will be a predicate register.  Do not visit the
 443   // users of it.
 444   if (!isPredReg(NewOutR)) {
 445     RegisterSubReg R(NewOutR);
 446     PredGPRs.insert(R);
 447     processPredicateGPR(R);
 448   }
 449   return true;
 450 }
 451
 452 bool HexagonGenPredicate::eliminatePredCopies(MachineFunction &MF) {
 453   LLVM_DEBUG(dbgs() << __func__ << "\n");
 454   const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 455   bool Changed = false;
 456   VectOfInst Erase;
 457
 458   // First, replace copies
 459   //   IntR = PredR1
 460   //   PredR2 = IntR
 461   // with
 462   //   PredR2 = PredR1
 463   // Such sequences can be generated when a copy-into-pred is generated from
 464   // a gpr register holding a result of a convertible instruction. After
 465   // the convertible instruction is converted, its predicate result will be
 466   // copied back into the original gpr.
 467
 468   for (MachineBasicBlock &MBB : MF) {
 469     for (MachineInstr &MI : MBB) {
 470       if (MI.getOpcode() != TargetOpcode::COPY)
 471         continue;
 472       RegisterSubReg DR = MI.getOperand(0);
 473       RegisterSubReg SR = MI.getOperand(1);
 474       if (!Register::isVirtualRegister(DR.R))
 475         continue;
 476       if (!Register::isVirtualRegister(SR.R))
 477         continue;
 478       if (MRI->getRegClass(DR.R) != PredRC)
 479         continue;
 480       if (MRI->getRegClass(SR.R) != PredRC)
 481         continue;
 482       assert(!DR.S && !SR.S && "Unexpected subregister");
 483       MRI->replaceRegWith(DR.R, SR.R);
 484       Erase.insert(&MI);
 485       Changed = true;
 486     }
 487   }
 488
 489   for (VectOfInst::iterator I = Erase.begin(), E = Erase.end(); I != E; ++I)
 490     (*I)->eraseFromParent();
 491
 492   return Changed;
 493 }
 494
 495 bool HexagonGenPredicate::runOnMachineFunction(MachineFunction &MF) {
 496   if (skipFunction(MF.getFunction()))
 497     return false;
 498
 499   TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
 500   TRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
 501   MRI = &MF.getRegInfo();
 502   PredGPRs.clear();
 503   PUsers.clear();
 504   G2P.clear();
 505
 506   bool Changed = false;
 507   collectPredicateGPR(MF);
 508   for (SetOfReg::iterator I = PredGPRs.begin(), E = PredGPRs.end(); I != E; ++I)
 509     processPredicateGPR(*I);
 510
 511   bool Again;
 512   do {
 513     Again = false;
 514     VectOfInst Processed, Copy;
 515
 516     using iterator = VectOfInst::iterator;
 517
 518     Copy = PUsers;
 519     for (iterator I = Copy.begin(), E = Copy.end(); I != E; ++I) {
 520       MachineInstr *MI = *I;
 521       bool Done = convertToPredForm(MI);
 522       if (Done) {
 523         Processed.insert(MI);
 524         Again = true;
 525       }
 526     }
 527     Changed |= Again;
 528
 529     auto Done = [Processed] (MachineInstr *MI) -> bool {
 530       return Processed.count(MI);
 531     };
 532     PUsers.remove_if(Done);
 533   } while (Again);
 534
 535   Changed |= eliminatePredCopies(MF);
 536   return Changed;
 537 }
 538
 539 FunctionPass *llvm::createHexagonGenPredicate() {
 540   return new HexagonGenPredicate();
 541 }