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__anon2a26800b0111::RegisterSubReg54 RegisterSubReg(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
RegisterSubReg__anon2a26800b0111::RegisterSubReg55 RegisterSubReg(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
RegisterSubReg__anon2a26800b0111::RegisterSubReg56 RegisterSubReg(const Register &Reg) : R(Reg), S(0) {}
57
operator ==__anon2a26800b0111::RegisterSubReg58 bool operator== (const RegisterSubReg &Reg) const {
59 return R == Reg.R && S == Reg.S;
60 }
61
operator <__anon2a26800b0111::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__anon2a26800b0111::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