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