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