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