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