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