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