contrib/llvm/lib/Target/Hexagon/HexagonGenPredicate.cpp

   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 "HexagonInstrInfo.h"
  13 #include "HexagonSubtarget.h"
  14 #include "llvm/ADT/SetVector.h"
  15 #include "llvm/ADT/StringRef.h"
  16 #include "llvm/CodeGen/MachineBasicBlock.h"
  17 #include "llvm/CodeGen/MachineDominators.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineInstr.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineOperand.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/IR/DebugLoc.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/Support/Compiler.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Target/TargetRegisterInfo.h"
  31 #include <cassert>
  32 #include <iterator>
  33 #include <map>
  34 #include <queue>
  35 #include <set>
  36 #include <utility>
  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   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
 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 (!TargetRegisterInfo::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             Register RD = MI->getOperand(0);
 216             if (TargetRegisterInfo::isVirtualRegister(RD.R))
 217               PredGPRs.insert(RD);
 218           }
 219           break;
 220       }
 221     }
 222   }
 223 }
 224
 225 void 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
 244 Register 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
 284 bool 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
 320 bool 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       }
 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   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   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   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     typedef VectOfInst::iterator iterator;
 515     Copy = PUsers;
 516     for (iterator I = Copy.begin(), E = Copy.end(); I != E; ++I) {
 517       MachineInstr *MI = *I;
 518       bool Done = convertToPredForm(MI);
 519       if (Done) {
 520         Processed.insert(MI);
 521         Again = true;
 522       }
 523     }
 524     Changed |= Again;
 525
 526     auto Done = [Processed] (MachineInstr *MI) -> bool {
 527       return Processed.count(MI);
 528     };
 529     PUsers.remove_if(Done);
 530   } while (Again);
 531
 532   Changed |= eliminatePredCopies(MF);
 533   return Changed;
 534 }
 535
 536 FunctionPass *llvm::createHexagonGenPredicate() {
 537   return new HexagonGenPredicate();
 538 }