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