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;
Register__anon7eb497360111::Register41     Register(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
Register__anon7eb497360111::Register42     Register(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
operator ==__anon7eb497360111::Register43     bool operator== (const Register &Reg) const {
44       return R == Reg.R && S == Reg.S;
45     }
operator <__anon7eb497360111::Register46     bool operator< (const Register &Reg) const {
47       return R < Reg.R || (R == Reg.R && S < Reg.S);
48     }
49   };
50   struct PrintRegister {
PrintRegister__anon7eb497360111::PrintRegister51     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;
operator <<(raw_ostream & OS,const PrintRegister & PR)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;
HexagonGenPredicate()66     HexagonGenPredicate() : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0) {
67       initializeHexagonGenPredicatePass(*PassRegistry::getPassRegistry());
68     }
getPassName() const69     virtual const char *getPassName() const {
70       return "Hexagon generate predicate operations";
71     }
getAnalysisUsage(AnalysisUsage & AU) const72     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)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)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 
getPredForm(unsigned Opc)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 
isConvertibleToPredForm(const MachineInstr * MI)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 
collectPredicateGPR(MachineFunction & MF)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 
processPredicateGPR(const Register & Reg)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 
getPredRegFor(const Register & Reg)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 
isScalarCmp(unsigned Opc)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 
isScalarPred(Register PredReg)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 
convertToPredForm(MachineInstr * MI)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 
eliminatePredCopies(MachineFunction & MF)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 
runOnMachineFunction(MachineFunction & MF)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 
createHexagonGenPredicate()522 FunctionPass *llvm::createHexagonGenPredicate() {
523   return new HexagonGenPredicate();
524 }
525 
526