HexagonGenPredicate.cpp revision 309124 
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
29using namespace llvm;
30
31namespace llvm {
32  void initializeHexagonGenPredicatePass(PassRegistry& Registry);
33  FunctionPass *createHexagonGenPredicate();
34}
35
36namespace {
37  struct Register {
38    unsigned R, S;
39    Register(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
40    Register(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
41    bool operator== (const Register &Reg) const {
42      return R == Reg.R && S == Reg.S;
43    }
44    bool operator< (const Register &Reg) const {
45      return R < Reg.R || (R == Reg.R && S < Reg.S);
46    }
47  };
48  struct PrintRegister {
49    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;
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;
64    HexagonGenPredicate() : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0) {
65      initializeHexagonGenPredicatePass(*PassRegistry::getPassRegistry());
66    }
67    virtual const char *getPassName() const {
68      return "Hexagon generate predicate operations";
69    }
70    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
104INITIALIZE_PASS_BEGIN(HexagonGenPredicate, "hexagon-gen-pred",
105  "Hexagon generate predicate operations", false, false)
106INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
107INITIALIZE_PASS_END(HexagonGenPredicate, "hexagon-gen-pred",
108  "Hexagon generate predicate operations", false, false)
109
110bool 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
118unsigned 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
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(2).isImm() && MI->getOperand(2).getImm() == 0)
176        return true;
177      break;
178  }
179  return false;
180}
181
182
183void 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
204void 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
224Register 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
265bool 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
302bool 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
348bool 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
434bool 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
478bool 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
522FunctionPass *llvm::createHexagonGenPredicate() {
523  return new HexagonGenPredicate();
524}
525
526