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