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