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