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() << LLVM_FUNCTION_NAME << ": "
 206                << PrintReg(Reg.R, TRI, Reg.S) << "\n");
 207   typedef MachineRegisterInfo::use_iterator use_iterator;
 208   use_iterator I = MRI->use_begin(Reg.R), E = MRI->use_end();
 209   if (I == E) {
 210     DEBUG(dbgs() << "Dead reg: " << PrintReg(Reg.R, TRI, Reg.S) << '\n');
 211     MachineInstr *DefI = MRI->getVRegDef(Reg.R);
 212     DefI->eraseFromParent();
 213     return;
 214   }
 215
 216   for (; I != E; ++I) {
 217     MachineInstr *UseI = I->getParent();
 218     if (isConvertibleToPredForm(UseI))
 219       PUsers.insert(UseI);
 220   }
 221 }
 222
 223
 224 Register HexagonGenPredicate::getPredRegFor(const Register &Reg) {
 225   // Create a predicate register for a given Reg. The newly created register
 226   // will have its value copied from Reg, so that it can be later used as
 227   // an operand in other instructions.
 228   assert(TargetRegisterInfo::isVirtualRegister(Reg.R));
 229   RegToRegMap::iterator F = G2P.find(Reg);
 230   if (F != G2P.end())
 231     return F->second;
 232
 233   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << PrintRegister(Reg, *TRI));
 234   MachineInstr *DefI = MRI->getVRegDef(Reg.R);
 235   assert(DefI);
 236   unsigned Opc = DefI->getOpcode();
 237   if (Opc == Hexagon::C2_tfrpr || Opc == TargetOpcode::COPY) {
 238     assert(DefI->getOperand(0).isDef() && DefI->getOperand(1).isUse());
 239     Register PR = DefI->getOperand(1);
 240     G2P.insert(std::make_pair(Reg, PR));
 241     DEBUG(dbgs() << " -> " << PrintRegister(PR, *TRI) << '\n');
 242     return PR;
 243   }
 244
 245   MachineBasicBlock &B = *DefI->getParent();
 246   DebugLoc DL = DefI->getDebugLoc();
 247   const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 248   unsigned NewPR = MRI->createVirtualRegister(PredRC);
 249
 250   // For convertible instructions, do not modify them, so that they can
 251   // be coverted later.  Generate a copy from Reg to NewPR.
 252   if (isConvertibleToPredForm(DefI)) {
 253     MachineBasicBlock::iterator DefIt = DefI;
 254     BuildMI(B, std::next(DefIt), DL, TII->get(TargetOpcode::COPY), NewPR)
 255       .addReg(Reg.R, 0, Reg.S);
 256     G2P.insert(std::make_pair(Reg, Register(NewPR)));
 257     DEBUG(dbgs() << " -> !" << PrintRegister(Register(NewPR), *TRI) << '\n');
 258     return Register(NewPR);
 259   }
 260
 261   llvm_unreachable("Invalid argument");
 262 }
 263
 264
 265 bool HexagonGenPredicate::isScalarCmp(unsigned Opc) {
 266   switch (Opc) {
 267     case Hexagon::C2_cmpeq:
 268     case Hexagon::C2_cmpgt:
 269     case Hexagon::C2_cmpgtu:
 270     case Hexagon::C2_cmpeqp:
 271     case Hexagon::C2_cmpgtp:
 272     case Hexagon::C2_cmpgtup:
 273     case Hexagon::C2_cmpeqi:
 274     case Hexagon::C2_cmpgti:
 275     case Hexagon::C2_cmpgtui:
 276     case Hexagon::C2_cmpgei:
 277     case Hexagon::C2_cmpgeui:
 278     case Hexagon::C4_cmpneqi:
 279     case Hexagon::C4_cmpltei:
 280     case Hexagon::C4_cmplteui:
 281     case Hexagon::C4_cmpneq:
 282     case Hexagon::C4_cmplte:
 283     case Hexagon::C4_cmplteu:
 284     case Hexagon::A4_cmpbeq:
 285     case Hexagon::A4_cmpbeqi:
 286     case Hexagon::A4_cmpbgtu:
 287     case Hexagon::A4_cmpbgtui:
 288     case Hexagon::A4_cmpbgt:
 289     case Hexagon::A4_cmpbgti:
 290     case Hexagon::A4_cmpheq:
 291     case Hexagon::A4_cmphgt:
 292     case Hexagon::A4_cmphgtu:
 293     case Hexagon::A4_cmpheqi:
 294     case Hexagon::A4_cmphgti:
 295     case Hexagon::A4_cmphgtui:
 296       return true;
 297   }
 298   return false;
 299 }
 300
 301
 302 bool HexagonGenPredicate::isScalarPred(Register PredReg) {
 303   std::queue<Register> WorkQ;
 304   WorkQ.push(PredReg);
 305
 306   while (!WorkQ.empty()) {
 307     Register PR = WorkQ.front();
 308     WorkQ.pop();
 309     const MachineInstr *DefI = MRI->getVRegDef(PR.R);
 310     if (!DefI)
 311       return false;
 312     unsigned DefOpc = DefI->getOpcode();
 313     switch (DefOpc) {
 314       case TargetOpcode::COPY: {
 315         const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 316         if (MRI->getRegClass(PR.R) != PredRC)
 317           return false;
 318         // If it is a copy between two predicate registers, fall through.
 319       }
 320       case Hexagon::C2_and:
 321       case Hexagon::C2_andn:
 322       case Hexagon::C4_and_and:
 323       case Hexagon::C4_and_andn:
 324       case Hexagon::C4_and_or:
 325       case Hexagon::C2_or:
 326       case Hexagon::C2_orn:
 327       case Hexagon::C4_or_and:
 328       case Hexagon::C4_or_andn:
 329       case Hexagon::C4_or_or:
 330       case Hexagon::C4_or_orn:
 331       case Hexagon::C2_xor:
 332         // Add operands to the queue.
 333         for (ConstMIOperands Mo(DefI); Mo.isValid(); ++Mo)
 334           if (Mo->isReg() && Mo->isUse())
 335             WorkQ.push(Register(Mo->getReg()));
 336         break;
 337
 338       // All non-vector compares are ok, everything else is bad.
 339       default:
 340         return isScalarCmp(DefOpc);
 341     }
 342   }
 343
 344   return true;
 345 }
 346
 347
 348 bool HexagonGenPredicate::convertToPredForm(MachineInstr *MI) {
 349   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << MI << " " << *MI);
 350
 351   unsigned Opc = MI->getOpcode();
 352   assert(isConvertibleToPredForm(MI));
 353   unsigned NumOps = MI->getNumOperands();
 354   for (unsigned i = 0; i < NumOps; ++i) {
 355     MachineOperand &MO = MI->getOperand(i);
 356     if (!MO.isReg() || !MO.isUse())
 357       continue;
 358     Register Reg(MO);
 359     if (Reg.S && Reg.S != Hexagon::subreg_loreg)
 360       return false;
 361     if (!PredGPRs.count(Reg))
 362       return false;
 363   }
 364
 365   MachineBasicBlock &B = *MI->getParent();
 366   DebugLoc DL = MI->getDebugLoc();
 367
 368   unsigned NewOpc = getPredForm(Opc);
 369   // Special case for comparisons against 0.
 370   if (NewOpc == 0) {
 371     switch (Opc) {
 372       case Hexagon::C2_cmpeqi:
 373         NewOpc = Hexagon::C2_not;
 374         break;
 375       case Hexagon::C4_cmpneqi:
 376         NewOpc = TargetOpcode::COPY;
 377         break;
 378       default:
 379         return false;
 380     }
 381
 382     // If it's a scalar predicate register, then all bits in it are
 383     // the same. Otherwise, to determine whether all bits are 0 or not
 384     // we would need to use any8.
 385     Register PR = getPredRegFor(MI->getOperand(1));
 386     if (!isScalarPred(PR))
 387       return false;
 388     // This will skip the immediate argument when creating the predicate
 389     // version instruction.
 390     NumOps = 2;
 391   }
 392
 393   // Some sanity: check that def is in operand #0.
 394   MachineOperand &Op0 = MI->getOperand(0);
 395   assert(Op0.isDef());
 396   Register OutR(Op0);
 397
 398   // Don't use getPredRegFor, since it will create an association between
 399   // the argument and a created predicate register (i.e. it will insert a
 400   // copy if a new predicate register is created).
 401   const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 402   Register NewPR = MRI->createVirtualRegister(PredRC);
 403   MachineInstrBuilder MIB = BuildMI(B, MI, DL, TII->get(NewOpc), NewPR.R);
 404
 405   // Add predicate counterparts of the GPRs.
 406   for (unsigned i = 1; i < NumOps; ++i) {
 407     Register GPR = MI->getOperand(i);
 408     Register Pred = getPredRegFor(GPR);
 409     MIB.addReg(Pred.R, 0, Pred.S);
 410   }
 411   DEBUG(dbgs() << "generated: " << *MIB);
 412
 413   // Generate a copy-out: NewGPR = NewPR, and replace all uses of OutR
 414   // with NewGPR.
 415   const TargetRegisterClass *RC = MRI->getRegClass(OutR.R);
 416   unsigned NewOutR = MRI->createVirtualRegister(RC);
 417   BuildMI(B, MI, DL, TII->get(TargetOpcode::COPY), NewOutR)
 418     .addReg(NewPR.R, 0, NewPR.S);
 419   MRI->replaceRegWith(OutR.R, NewOutR);
 420   MI->eraseFromParent();
 421
 422   // If the processed instruction was C2_tfrrp (i.e. Rn = Pm; Pk = Rn),
 423   // then the output will be a predicate register.  Do not visit the
 424   // users of it.
 425   if (!isPredReg(NewOutR)) {
 426     Register R(NewOutR);
 427     PredGPRs.insert(R);
 428     processPredicateGPR(R);
 429   }
 430   return true;
 431 }
 432
 433
 434 bool HexagonGenPredicate::eliminatePredCopies(MachineFunction &MF) {
 435   DEBUG(dbgs() << LLVM_FUNCTION_NAME << "\n");
 436   const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
 437   bool Changed = false;
 438   VectOfInst Erase;
 439
 440   // First, replace copies
 441   //   IntR = PredR1
 442   //   PredR2 = IntR
 443   // with
 444   //   PredR2 = PredR1
 445   // Such sequences can be generated when a copy-into-pred is generated from
 446   // a gpr register holding a result of a convertible instruction. After
 447   // the convertible instruction is converted, its predicate result will be
 448   // copied back into the original gpr.
 449
 450   for (MachineFunction::iterator A = MF.begin(), Z = MF.end(); A != Z; ++A) {
 451     MachineBasicBlock &B = *A;
 452     for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) {
 453       if (I->getOpcode() != TargetOpcode::COPY)
 454         continue;
 455       Register DR = I->getOperand(0);
 456       Register SR = I->getOperand(1);
 457       if (!TargetRegisterInfo::isVirtualRegister(DR.R))
 458         continue;
 459       if (!TargetRegisterInfo::isVirtualRegister(SR.R))
 460         continue;
 461       if (MRI->getRegClass(DR.R) != PredRC)
 462         continue;
 463       if (MRI->getRegClass(SR.R) != PredRC)
 464         continue;
 465       assert(!DR.S && !SR.S && "Unexpected subregister");
 466       MRI->replaceRegWith(DR.R, SR.R);
 467       Erase.insert(I);
 468       Changed = true;
 469     }
 470   }
 471
 472   for (VectOfInst::iterator I = Erase.begin(), E = Erase.end(); I != E; ++I)
 473     (*I)->eraseFromParent();
 474
 475   return Changed;
 476 }
 477
 478
 479 bool HexagonGenPredicate::runOnMachineFunction(MachineFunction &MF) {
 480   TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
 481   TRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
 482   MRI = &MF.getRegInfo();
 483   PredGPRs.clear();
 484   PUsers.clear();
 485   G2P.clear();
 486
 487   bool Changed = false;
 488   collectPredicateGPR(MF);
 489   for (SetOfReg::iterator I = PredGPRs.begin(), E = PredGPRs.end(); I != E; ++I)
 490     processPredicateGPR(*I);
 491
 492   bool Again;
 493   do {
 494     Again = false;
 495     VectOfInst Processed, Copy;
 496
 497     typedef VectOfInst::iterator iterator;
 498     Copy = PUsers;
 499     for (iterator I = Copy.begin(), E = Copy.end(); I != E; ++I) {
 500       MachineInstr *MI = *I;
 501       bool Done = convertToPredForm(MI);
 502       if (Done) {
 503         Processed.insert(MI);
 504         Again = true;
 505       }
 506     }
 507     Changed |= Again;
 508
 509     auto Done = [Processed] (MachineInstr *MI) -> bool {
 510       return Processed.count(MI);
 511     };
 512     PUsers.remove_if(Done);
 513   } while (Again);
 514
 515   Changed |= eliminatePredCopies(MF);
 516   return Changed;
 517 }
 518
 519
 520 FunctionPass *llvm::createHexagonGenPredicate() {
 521   return new HexagonGenPredicate();
 522 }
 523