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 #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
  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         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
 366 bool 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
 451 bool 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
 494 bool 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
 537 FunctionPass *llvm::createHexagonGenPredicate() {
 538   return new HexagonGenPredicate();
 539 }