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