Home | History | Annotate | Download | only in Hexagon 
      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 
    526