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