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
RegisterSubReg__anon92fec6620111::RegisterSubReg53 RegisterSubReg(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
RegisterSubReg__anon92fec6620111::RegisterSubReg54 RegisterSubReg(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
RegisterSubReg__anon92fec6620111::RegisterSubReg55 RegisterSubReg(const Register &Reg) : R(Reg), S(0) {}
56
operator ==__anon92fec6620111::RegisterSubReg57 bool operator== (const RegisterSubReg &Reg) const {
58 return R == Reg.R && S == Reg.S;
59 }
60
operator <__anon92fec6620111::RegisterSubReg61 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
PrintRegister__anon92fec6620111::PrintRegister69 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;
operator <<(raw_ostream & OS,const PrintRegister & PR)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
HexagonGenPredicate()86 HexagonGenPredicate() : MachineFunctionPass(ID) {
87 initializeHexagonGenPredicatePass(*PassRegistry::getPassRegistry());
88 }
89
getPassName() const90 StringRef getPassName() const override {
91 return "Hexagon generate predicate operations";
92 }
93
getAnalysisUsage(AnalysisUsage & AU) const94 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)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)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
getPredForm(unsigned Opc)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
isConvertibleToPredForm(const MachineInstr * MI)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
collectPredicateGPR(MachineFunction & MF)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
processPredicateGPR(const RegisterSubReg & Reg)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
getPredRegFor(const RegisterSubReg & Reg)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
isScalarCmp(unsigned Opc)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
isScalarPred(RegisterSubReg PredReg)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
convertToPredForm(MachineInstr * MI)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
eliminatePredCopies(MachineFunction & MF)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
runOnMachineFunction(MachineFunction & MF)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
createHexagonGenPredicate()540 FunctionPass *llvm::createHexagonGenPredicate() {
541 return new HexagonGenPredicate();
542 }
543