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