LLVM  8.0.0svn
X86DomainReassignment.cpp
Go to the documentation of this file.
1 //===--- X86DomainReassignment.cpp - Selectively switch register classes---===//
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 // This pass attempts to find instruction chains (closures) in one domain,
11 // and convert them to equivalent instructions in a different domain,
12 // if profitable.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "X86.h"
17 #include "X86InstrInfo.h"
18 #include "X86Subtarget.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/DenseMapInfo.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/Printable.h"
30 #include <bitset>
31 
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "x86-domain-reassignment"
35 
36 STATISTIC(NumClosuresConverted, "Number of closures converted by the pass");
37 
39  "disable-x86-domain-reassignment", cl::Hidden,
40  cl::desc("X86: Disable Virtual Register Reassignment."), cl::init(false));
41 
42 namespace {
43 enum RegDomain { NoDomain = -1, GPRDomain, MaskDomain, OtherDomain, NumDomains };
44 
45 static bool isGPR(const TargetRegisterClass *RC) {
46  return X86::GR64RegClass.hasSubClassEq(RC) ||
47  X86::GR32RegClass.hasSubClassEq(RC) ||
48  X86::GR16RegClass.hasSubClassEq(RC) ||
49  X86::GR8RegClass.hasSubClassEq(RC);
50 }
51 
52 static bool isMask(const TargetRegisterClass *RC,
53  const TargetRegisterInfo *TRI) {
54  return X86::VK16RegClass.hasSubClassEq(RC);
55 }
56 
57 static RegDomain getDomain(const TargetRegisterClass *RC,
58  const TargetRegisterInfo *TRI) {
59  if (isGPR(RC))
60  return GPRDomain;
61  if (isMask(RC, TRI))
62  return MaskDomain;
63  return OtherDomain;
64 }
65 
66 /// Return a register class equivalent to \p SrcRC, in \p Domain.
67 static const TargetRegisterClass *getDstRC(const TargetRegisterClass *SrcRC,
68  RegDomain Domain) {
69  assert(Domain == MaskDomain && "add domain");
70  if (X86::GR8RegClass.hasSubClassEq(SrcRC))
71  return &X86::VK8RegClass;
72  if (X86::GR16RegClass.hasSubClassEq(SrcRC))
73  return &X86::VK16RegClass;
74  if (X86::GR32RegClass.hasSubClassEq(SrcRC))
75  return &X86::VK32RegClass;
76  if (X86::GR64RegClass.hasSubClassEq(SrcRC))
77  return &X86::VK64RegClass;
78  llvm_unreachable("add register class");
79  return nullptr;
80 }
81 
82 /// Abstract Instruction Converter class.
83 class InstrConverterBase {
84 protected:
85  unsigned SrcOpcode;
86 
87 public:
88  InstrConverterBase(unsigned SrcOpcode) : SrcOpcode(SrcOpcode) {}
89 
90  virtual ~InstrConverterBase() {}
91 
92  /// \returns true if \p MI is legal to convert.
93  virtual bool isLegal(const MachineInstr *MI,
94  const TargetInstrInfo *TII) const {
95  assert(MI->getOpcode() == SrcOpcode &&
96  "Wrong instruction passed to converter");
97  return true;
98  }
99 
100  /// Applies conversion to \p MI.
101  ///
102  /// \returns true if \p MI is no longer need, and can be deleted.
103  virtual bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
104  MachineRegisterInfo *MRI) const = 0;
105 
106  /// \returns the cost increment incurred by converting \p MI.
107  virtual double getExtraCost(const MachineInstr *MI,
108  MachineRegisterInfo *MRI) const = 0;
109 };
110 
111 /// An Instruction Converter which ignores the given instruction.
112 /// For example, PHI instructions can be safely ignored since only the registers
113 /// need to change.
114 class InstrIgnore : public InstrConverterBase {
115 public:
116  InstrIgnore(unsigned SrcOpcode) : InstrConverterBase(SrcOpcode) {}
117 
118  bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
119  MachineRegisterInfo *MRI) const override {
120  assert(isLegal(MI, TII) && "Cannot convert instruction");
121  return false;
122  }
123 
124  double getExtraCost(const MachineInstr *MI,
125  MachineRegisterInfo *MRI) const override {
126  return 0;
127  }
128 };
129 
130 /// An Instruction Converter which replaces an instruction with another.
131 class InstrReplacer : public InstrConverterBase {
132 public:
133  /// Opcode of the destination instruction.
134  unsigned DstOpcode;
135 
136  InstrReplacer(unsigned SrcOpcode, unsigned DstOpcode)
137  : InstrConverterBase(SrcOpcode), DstOpcode(DstOpcode) {}
138 
139  bool isLegal(const MachineInstr *MI,
140  const TargetInstrInfo *TII) const override {
141  if (!InstrConverterBase::isLegal(MI, TII))
142  return false;
143  // It's illegal to replace an instruction that implicitly defines a register
144  // with an instruction that doesn't, unless that register dead.
145  for (auto &MO : MI->implicit_operands())
146  if (MO.isReg() && MO.isDef() && !MO.isDead() &&
147  !TII->get(DstOpcode).hasImplicitDefOfPhysReg(MO.getReg()))
148  return false;
149  return true;
150  }
151 
152  bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
153  MachineRegisterInfo *MRI) const override {
154  assert(isLegal(MI, TII) && "Cannot convert instruction");
155  MachineInstrBuilder Bld =
156  BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), TII->get(DstOpcode));
157  // Transfer explicit operands from original instruction. Implicit operands
158  // are handled by BuildMI.
159  for (auto &Op : MI->explicit_operands())
160  Bld.add(Op);
161  return true;
162  }
163 
164  double getExtraCost(const MachineInstr *MI,
165  MachineRegisterInfo *MRI) const override {
166  // Assuming instructions have the same cost.
167  return 0;
168  }
169 };
170 
171 /// An Instruction Converter which replaces an instruction with another, and
172 /// adds a COPY from the new instruction's destination to the old one's.
173 class InstrReplacerDstCOPY : public InstrConverterBase {
174 public:
175  unsigned DstOpcode;
176 
177  InstrReplacerDstCOPY(unsigned SrcOpcode, unsigned DstOpcode)
178  : InstrConverterBase(SrcOpcode), DstOpcode(DstOpcode) {}
179 
180  bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
181  MachineRegisterInfo *MRI) const override {
182  assert(isLegal(MI, TII) && "Cannot convert instruction");
183  MachineBasicBlock *MBB = MI->getParent();
184  auto &DL = MI->getDebugLoc();
185 
186  unsigned Reg = MRI->createVirtualRegister(
187  TII->getRegClass(TII->get(DstOpcode), 0, MRI->getTargetRegisterInfo(),
188  *MBB->getParent()));
189  MachineInstrBuilder Bld = BuildMI(*MBB, MI, DL, TII->get(DstOpcode), Reg);
190  for (unsigned Idx = 1, End = MI->getNumOperands(); Idx < End; ++Idx)
191  Bld.add(MI->getOperand(Idx));
192 
193  BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::COPY))
194  .add(MI->getOperand(0))
195  .addReg(Reg);
196 
197  return true;
198  }
199 
200  double getExtraCost(const MachineInstr *MI,
201  MachineRegisterInfo *MRI) const override {
202  // Assuming instructions have the same cost, and that COPY is in the same
203  // domain so it will be eliminated.
204  return 0;
205  }
206 };
207 
208 /// An Instruction Converter for replacing COPY instructions.
209 class InstrCOPYReplacer : public InstrReplacer {
210 public:
211  RegDomain DstDomain;
212 
213  InstrCOPYReplacer(unsigned SrcOpcode, RegDomain DstDomain, unsigned DstOpcode)
214  : InstrReplacer(SrcOpcode, DstOpcode), DstDomain(DstDomain) {}
215 
216  bool isLegal(const MachineInstr *MI,
217  const TargetInstrInfo *TII) const override {
218  if (!InstrConverterBase::isLegal(MI, TII))
219  return false;
220 
221  // Don't allow copies to/flow GR8/GR16 physical registers.
222  // FIXME: Is there some better way to support this?
223  unsigned DstReg = MI->getOperand(0).getReg();
225  (X86::GR8RegClass.contains(DstReg) ||
226  X86::GR16RegClass.contains(DstReg)))
227  return false;
228  unsigned SrcReg = MI->getOperand(1).getReg();
230  (X86::GR8RegClass.contains(SrcReg) ||
231  X86::GR16RegClass.contains(SrcReg)))
232  return false;
233 
234  return true;
235  }
236 
237  double getExtraCost(const MachineInstr *MI,
238  MachineRegisterInfo *MRI) const override {
239  assert(MI->getOpcode() == TargetOpcode::COPY && "Expected a COPY");
240 
241  for (auto &MO : MI->operands()) {
242  // Physical registers will not be converted. Assume that converting the
243  // COPY to the destination domain will eventually result in a actual
244  // instruction.
246  return 1;
247 
248  RegDomain OpDomain = getDomain(MRI->getRegClass(MO.getReg()),
249  MRI->getTargetRegisterInfo());
250  // Converting a cross domain COPY to a same domain COPY should eliminate
251  // an insturction
252  if (OpDomain == DstDomain)
253  return -1;
254  }
255  return 0;
256  }
257 };
258 
259 /// An Instruction Converter which replaces an instruction with a COPY.
260 class InstrReplaceWithCopy : public InstrConverterBase {
261 public:
262  // Source instruction operand Index, to be used as the COPY source.
263  unsigned SrcOpIdx;
264 
265  InstrReplaceWithCopy(unsigned SrcOpcode, unsigned SrcOpIdx)
266  : InstrConverterBase(SrcOpcode), SrcOpIdx(SrcOpIdx) {}
267 
268  bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
269  MachineRegisterInfo *MRI) const override {
270  assert(isLegal(MI, TII) && "Cannot convert instruction");
271  BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
272  TII->get(TargetOpcode::COPY))
273  .add({MI->getOperand(0), MI->getOperand(SrcOpIdx)});
274  return true;
275  }
276 
277  double getExtraCost(const MachineInstr *MI,
278  MachineRegisterInfo *MRI) const override {
279  return 0;
280  }
281 };
282 
283 // Key type to be used by the Instruction Converters map.
284 // A converter is identified by <destination domain, source opcode>
285 typedef std::pair<int, unsigned> InstrConverterBaseKeyTy;
286 
288  InstrConverterBaseMap;
289 
290 /// A closure is a set of virtual register representing all of the edges in
291 /// the closure, as well as all of the instructions connected by those edges.
292 ///
293 /// A closure may encompass virtual registers in the same register bank that
294 /// have different widths. For example, it may contain 32-bit GPRs as well as
295 /// 64-bit GPRs.
296 ///
297 /// A closure that computes an address (i.e. defines a virtual register that is
298 /// used in a memory operand) excludes the instructions that contain memory
299 /// operands using the address. Such an instruction will be included in a
300 /// different closure that manipulates the loaded or stored value.
301 class Closure {
302 private:
303  /// Virtual registers in the closure.
304  DenseSet<unsigned> Edges;
305 
306  /// Instructions in the closure.
308 
309  /// Domains which this closure can legally be reassigned to.
310  std::bitset<NumDomains> LegalDstDomains;
311 
312  /// An ID to uniquely identify this closure, even when it gets
313  /// moved around
314  unsigned ID;
315 
316 public:
317  Closure(unsigned ID, std::initializer_list<RegDomain> LegalDstDomainList) : ID(ID) {
318  for (RegDomain D : LegalDstDomainList)
319  LegalDstDomains.set(D);
320  }
321 
322  /// Mark this closure as illegal for reassignment to all domains.
323  void setAllIllegal() { LegalDstDomains.reset(); }
324 
325  /// \returns true if this closure has domains which are legal to reassign to.
326  bool hasLegalDstDomain() const { return LegalDstDomains.any(); }
327 
328  /// \returns true if is legal to reassign this closure to domain \p RD.
329  bool isLegal(RegDomain RD) const { return LegalDstDomains[RD]; }
330 
331  /// Mark this closure as illegal for reassignment to domain \p RD.
332  void setIllegal(RegDomain RD) { LegalDstDomains[RD] = false; }
333 
334  bool empty() const { return Edges.empty(); }
335 
336  bool insertEdge(unsigned Reg) {
337  return Edges.insert(Reg).second;
338  }
339 
340  using const_edge_iterator = DenseSet<unsigned>::const_iterator;
342  return iterator_range<const_edge_iterator>(Edges.begin(), Edges.end());
343  }
344 
345  void addInstruction(MachineInstr *I) {
346  Instrs.push_back(I);
347  }
348 
350  return Instrs;
351  }
352 
353  LLVM_DUMP_METHOD void dump(const MachineRegisterInfo *MRI) const {
354  dbgs() << "Registers: ";
355  bool First = true;
356  for (unsigned Reg : Edges) {
357  if (!First)
358  dbgs() << ", ";
359  First = false;
360  dbgs() << printReg(Reg, MRI->getTargetRegisterInfo(), 0, MRI);
361  }
362  dbgs() << "\n" << "Instructions:";
363  for (MachineInstr *MI : Instrs) {
364  dbgs() << "\n ";
365  MI->print(dbgs());
366  }
367  dbgs() << "\n";
368  }
369 
370  unsigned getID() const {
371  return ID;
372  }
373 
374 };
375 
376 class X86DomainReassignment : public MachineFunctionPass {
377  const X86Subtarget *STI;
379  const X86InstrInfo *TII;
380 
381  /// All edges that are included in some closure
382  DenseSet<unsigned> EnclosedEdges;
383 
384  /// All instructions that are included in some closure.
385  DenseMap<MachineInstr *, unsigned> EnclosedInstrs;
386 
387 public:
388  static char ID;
389 
390  X86DomainReassignment() : MachineFunctionPass(ID) {
392  }
393 
394  bool runOnMachineFunction(MachineFunction &MF) override;
395 
396  void getAnalysisUsage(AnalysisUsage &AU) const override {
397  AU.setPreservesCFG();
399  }
400 
401  StringRef getPassName() const override {
402  return "X86 Domain Reassignment Pass";
403  }
404 
405 private:
406  /// A map of available Instruction Converters.
407  InstrConverterBaseMap Converters;
408 
409  /// Initialize Converters map.
410  void initConverters();
411 
412  /// Starting from \Reg, expand the closure as much as possible.
413  void buildClosure(Closure &, unsigned Reg);
414 
415  /// Enqueue \p Reg to be considered for addition to the closure.
416  void visitRegister(Closure &, unsigned Reg, RegDomain &Domain,
417  SmallVectorImpl<unsigned> &Worklist);
418 
419  /// Reassign the closure to \p Domain.
420  void reassign(const Closure &C, RegDomain Domain) const;
421 
422  /// Add \p MI to the closure.
423  void encloseInstr(Closure &C, MachineInstr *MI);
424 
425  /// /returns true if it is profitable to reassign the closure to \p Domain.
426  bool isReassignmentProfitable(const Closure &C, RegDomain Domain) const;
427 
428  /// Calculate the total cost of reassigning the closure to \p Domain.
429  double calculateCost(const Closure &C, RegDomain Domain) const;
430 };
431 
433 
434 } // End anonymous namespace.
435 
436 void X86DomainReassignment::visitRegister(Closure &C, unsigned Reg,
437  RegDomain &Domain,
438  SmallVectorImpl<unsigned> &Worklist) {
439  if (EnclosedEdges.count(Reg))
440  return;
441 
443  return;
444 
445  if (!MRI->hasOneDef(Reg))
446  return;
447 
448  RegDomain RD = getDomain(MRI->getRegClass(Reg), MRI->getTargetRegisterInfo());
449  // First edge in closure sets the domain.
450  if (Domain == NoDomain)
451  Domain = RD;
452 
453  if (Domain != RD)
454  return;
455 
456  Worklist.push_back(Reg);
457 }
458 
459 void X86DomainReassignment::encloseInstr(Closure &C, MachineInstr *MI) {
460  auto I = EnclosedInstrs.find(MI);
461  if (I != EnclosedInstrs.end()) {
462  if (I->second != C.getID())
463  // Instruction already belongs to another closure, avoid conflicts between
464  // closure and mark this closure as illegal.
465  C.setAllIllegal();
466  return;
467  }
468 
469  EnclosedInstrs[MI] = C.getID();
470  C.addInstruction(MI);
471 
472  // Mark closure as illegal for reassignment to domains, if there is no
473  // converter for the instruction or if the converter cannot convert the
474  // instruction.
475  for (int i = 0; i != NumDomains; ++i) {
476  if (C.isLegal((RegDomain)i)) {
477  InstrConverterBase *IC = Converters.lookup({i, MI->getOpcode()});
478  if (!IC || !IC->isLegal(MI, TII))
479  C.setIllegal((RegDomain)i);
480  }
481  }
482 }
483 
484 double X86DomainReassignment::calculateCost(const Closure &C,
485  RegDomain DstDomain) const {
486  assert(C.isLegal(DstDomain) && "Cannot calculate cost for illegal closure");
487 
488  double Cost = 0.0;
489  for (auto *MI : C.instructions())
490  Cost +=
491  Converters.lookup({DstDomain, MI->getOpcode()})->getExtraCost(MI, MRI);
492  return Cost;
493 }
494 
495 bool X86DomainReassignment::isReassignmentProfitable(const Closure &C,
496  RegDomain Domain) const {
497  return calculateCost(C, Domain) < 0.0;
498 }
499 
500 void X86DomainReassignment::reassign(const Closure &C, RegDomain Domain) const {
501  assert(C.isLegal(Domain) && "Cannot convert illegal closure");
502 
503  // Iterate all instructions in the closure, convert each one using the
504  // appropriate converter.
506  for (auto *MI : C.instructions())
507  if (Converters.lookup({Domain, MI->getOpcode()})
508  ->convertInstr(MI, TII, MRI))
509  ToErase.push_back(MI);
510 
511  // Iterate all registers in the closure, replace them with registers in the
512  // destination domain.
513  for (unsigned Reg : C.edges()) {
514  MRI->setRegClass(Reg, getDstRC(MRI->getRegClass(Reg), Domain));
515  for (auto &MO : MRI->use_operands(Reg)) {
516  if (MO.isReg())
517  // Remove all subregister references as they are not valid in the
518  // destination domain.
519  MO.setSubReg(0);
520  }
521  }
522 
523  for (auto MI : ToErase)
524  MI->eraseFromParent();
525 }
526 
527 /// \returns true when \p Reg is used as part of an address calculation in \p
528 /// MI.
529 static bool usedAsAddr(const MachineInstr &MI, unsigned Reg,
530  const TargetInstrInfo *TII) {
531  if (!MI.mayLoadOrStore())
532  return false;
533 
534  const MCInstrDesc &Desc = TII->get(MI.getOpcode());
535  int MemOpStart = X86II::getMemoryOperandNo(Desc.TSFlags);
536  if (MemOpStart == -1)
537  return false;
538 
539  MemOpStart += X86II::getOperandBias(Desc);
540  for (unsigned MemOpIdx = MemOpStart,
541  MemOpEnd = MemOpStart + X86::AddrNumOperands;
542  MemOpIdx < MemOpEnd; ++MemOpIdx) {
543  auto &Op = MI.getOperand(MemOpIdx);
544  if (Op.isReg() && Op.getReg() == Reg)
545  return true;
546  }
547  return false;
548 }
549 
550 void X86DomainReassignment::buildClosure(Closure &C, unsigned Reg) {
551  SmallVector<unsigned, 4> Worklist;
552  RegDomain Domain = NoDomain;
553  visitRegister(C, Reg, Domain, Worklist);
554  while (!Worklist.empty()) {
555  unsigned CurReg = Worklist.pop_back_val();
556 
557  // Register already in this closure.
558  if (!C.insertEdge(CurReg))
559  continue;
560 
561  MachineInstr *DefMI = MRI->getVRegDef(CurReg);
562  encloseInstr(C, DefMI);
563 
564  // Add register used by the defining MI to the worklist.
565  // Do not add registers which are used in address calculation, they will be
566  // added to a different closure.
567  int OpEnd = DefMI->getNumOperands();
568  const MCInstrDesc &Desc = DefMI->getDesc();
569  int MemOp = X86II::getMemoryOperandNo(Desc.TSFlags);
570  if (MemOp != -1)
571  MemOp += X86II::getOperandBias(Desc);
572  for (int OpIdx = 0; OpIdx < OpEnd; ++OpIdx) {
573  if (OpIdx == MemOp) {
574  // skip address calculation.
575  OpIdx += (X86::AddrNumOperands - 1);
576  continue;
577  }
578  auto &Op = DefMI->getOperand(OpIdx);
579  if (!Op.isReg() || !Op.isUse())
580  continue;
581  visitRegister(C, Op.getReg(), Domain, Worklist);
582  }
583 
584  // Expand closure through register uses.
585  for (auto &UseMI : MRI->use_nodbg_instructions(CurReg)) {
586  // We would like to avoid converting closures which calculare addresses,
587  // as this should remain in GPRs.
588  if (usedAsAddr(UseMI, CurReg, TII)) {
589  C.setAllIllegal();
590  continue;
591  }
592  encloseInstr(C, &UseMI);
593 
594  for (auto &DefOp : UseMI.defs()) {
595  if (!DefOp.isReg())
596  continue;
597 
598  unsigned DefReg = DefOp.getReg();
600  C.setAllIllegal();
601  continue;
602  }
603  visitRegister(C, DefReg, Domain, Worklist);
604  }
605  }
606  }
607 }
608 
609 void X86DomainReassignment::initConverters() {
610  Converters[{MaskDomain, TargetOpcode::PHI}] =
611  new InstrIgnore(TargetOpcode::PHI);
612 
613  Converters[{MaskDomain, TargetOpcode::IMPLICIT_DEF}] =
614  new InstrIgnore(TargetOpcode::IMPLICIT_DEF);
615 
616  Converters[{MaskDomain, TargetOpcode::INSERT_SUBREG}] =
617  new InstrReplaceWithCopy(TargetOpcode::INSERT_SUBREG, 2);
618 
619  Converters[{MaskDomain, TargetOpcode::COPY}] =
620  new InstrCOPYReplacer(TargetOpcode::COPY, MaskDomain, TargetOpcode::COPY);
621 
622  auto createReplacerDstCOPY = [&](unsigned From, unsigned To) {
623  Converters[{MaskDomain, From}] = new InstrReplacerDstCOPY(From, To);
624  };
625 
626  createReplacerDstCOPY(X86::MOVZX32rm16, X86::KMOVWkm);
627  createReplacerDstCOPY(X86::MOVZX64rm16, X86::KMOVWkm);
628 
629  createReplacerDstCOPY(X86::MOVZX32rr16, X86::KMOVWkk);
630  createReplacerDstCOPY(X86::MOVZX64rr16, X86::KMOVWkk);
631 
632  if (STI->hasDQI()) {
633  createReplacerDstCOPY(X86::MOVZX16rm8, X86::KMOVBkm);
634  createReplacerDstCOPY(X86::MOVZX32rm8, X86::KMOVBkm);
635  createReplacerDstCOPY(X86::MOVZX64rm8, X86::KMOVBkm);
636 
637  createReplacerDstCOPY(X86::MOVZX16rr8, X86::KMOVBkk);
638  createReplacerDstCOPY(X86::MOVZX32rr8, X86::KMOVBkk);
639  createReplacerDstCOPY(X86::MOVZX64rr8, X86::KMOVBkk);
640  }
641 
642  auto createReplacer = [&](unsigned From, unsigned To) {
643  Converters[{MaskDomain, From}] = new InstrReplacer(From, To);
644  };
645 
646  createReplacer(X86::MOV16rm, X86::KMOVWkm);
647  createReplacer(X86::MOV16mr, X86::KMOVWmk);
648  createReplacer(X86::MOV16rr, X86::KMOVWkk);
649  createReplacer(X86::SHR16ri, X86::KSHIFTRWri);
650  createReplacer(X86::SHL16ri, X86::KSHIFTLWri);
651  createReplacer(X86::NOT16r, X86::KNOTWrr);
652  createReplacer(X86::OR16rr, X86::KORWrr);
653  createReplacer(X86::AND16rr, X86::KANDWrr);
654  createReplacer(X86::XOR16rr, X86::KXORWrr);
655 
656  if (STI->hasBWI()) {
657  createReplacer(X86::MOV32rm, X86::KMOVDkm);
658  createReplacer(X86::MOV64rm, X86::KMOVQkm);
659 
660  createReplacer(X86::MOV32mr, X86::KMOVDmk);
661  createReplacer(X86::MOV64mr, X86::KMOVQmk);
662 
663  createReplacer(X86::MOV32rr, X86::KMOVDkk);
664  createReplacer(X86::MOV64rr, X86::KMOVQkk);
665 
666  createReplacer(X86::SHR32ri, X86::KSHIFTRDri);
667  createReplacer(X86::SHR64ri, X86::KSHIFTRQri);
668 
669  createReplacer(X86::SHL32ri, X86::KSHIFTLDri);
670  createReplacer(X86::SHL64ri, X86::KSHIFTLQri);
671 
672  createReplacer(X86::ADD32rr, X86::KADDDrr);
673  createReplacer(X86::ADD64rr, X86::KADDQrr);
674 
675  createReplacer(X86::NOT32r, X86::KNOTDrr);
676  createReplacer(X86::NOT64r, X86::KNOTQrr);
677 
678  createReplacer(X86::OR32rr, X86::KORDrr);
679  createReplacer(X86::OR64rr, X86::KORQrr);
680 
681  createReplacer(X86::AND32rr, X86::KANDDrr);
682  createReplacer(X86::AND64rr, X86::KANDQrr);
683 
684  createReplacer(X86::ANDN32rr, X86::KANDNDrr);
685  createReplacer(X86::ANDN64rr, X86::KANDNQrr);
686 
687  createReplacer(X86::XOR32rr, X86::KXORDrr);
688  createReplacer(X86::XOR64rr, X86::KXORQrr);
689 
690  // TODO: KTEST is not a replacement for TEST due to flag differences. Need
691  // to prove only Z flag is used.
692  //createReplacer(X86::TEST32rr, X86::KTESTDrr);
693  //createReplacer(X86::TEST64rr, X86::KTESTQrr);
694  }
695 
696  if (STI->hasDQI()) {
697  createReplacer(X86::ADD8rr, X86::KADDBrr);
698  createReplacer(X86::ADD16rr, X86::KADDWrr);
699 
700  createReplacer(X86::AND8rr, X86::KANDBrr);
701 
702  createReplacer(X86::MOV8rm, X86::KMOVBkm);
703  createReplacer(X86::MOV8mr, X86::KMOVBmk);
704  createReplacer(X86::MOV8rr, X86::KMOVBkk);
705 
706  createReplacer(X86::NOT8r, X86::KNOTBrr);
707 
708  createReplacer(X86::OR8rr, X86::KORBrr);
709 
710  createReplacer(X86::SHR8ri, X86::KSHIFTRBri);
711  createReplacer(X86::SHL8ri, X86::KSHIFTLBri);
712 
713  // TODO: KTEST is not a replacement for TEST due to flag differences. Need
714  // to prove only Z flag is used.
715  //createReplacer(X86::TEST8rr, X86::KTESTBrr);
716  //createReplacer(X86::TEST16rr, X86::KTESTWrr);
717 
718  createReplacer(X86::XOR8rr, X86::KXORBrr);
719  }
720 }
721 
722 bool X86DomainReassignment::runOnMachineFunction(MachineFunction &MF) {
723  if (skipFunction(MF.getFunction()))
724  return false;
726  return false;
727 
728  LLVM_DEBUG(
729  dbgs() << "***** Machine Function before Domain Reassignment *****\n");
730  LLVM_DEBUG(MF.print(dbgs()));
731 
732  STI = &MF.getSubtarget<X86Subtarget>();
733  // GPR->K is the only transformation currently supported, bail out early if no
734  // AVX512.
735  if (!STI->hasAVX512())
736  return false;
737 
738  MRI = &MF.getRegInfo();
739  assert(MRI->isSSA() && "Expected MIR to be in SSA form");
740 
741  TII = STI->getInstrInfo();
742  initConverters();
743  bool Changed = false;
744 
745  EnclosedEdges.clear();
746  EnclosedInstrs.clear();
747 
748  std::vector<Closure> Closures;
749 
750  // Go over all virtual registers and calculate a closure.
751  unsigned ClosureID = 0;
752  for (unsigned Idx = 0; Idx < MRI->getNumVirtRegs(); ++Idx) {
753  unsigned Reg = TargetRegisterInfo::index2VirtReg(Idx);
754 
755  // GPR only current source domain supported.
756  if (!isGPR(MRI->getRegClass(Reg)))
757  continue;
758 
759  // Register already in closure.
760  if (EnclosedEdges.count(Reg))
761  continue;
762 
763  // Calculate closure starting with Reg.
764  Closure C(ClosureID++, {MaskDomain});
765  buildClosure(C, Reg);
766 
767  // Collect all closures that can potentially be converted.
768  if (!C.empty() && C.isLegal(MaskDomain))
769  Closures.push_back(std::move(C));
770  }
771 
772  for (Closure &C : Closures) {
773  LLVM_DEBUG(C.dump(MRI));
774  if (isReassignmentProfitable(C, MaskDomain)) {
775  reassign(C, MaskDomain);
776  ++NumClosuresConverted;
777  Changed = true;
778  }
779  }
780 
781  DeleteContainerSeconds(Converters);
782 
783  LLVM_DEBUG(
784  dbgs() << "***** Machine Function after Domain Reassignment *****\n");
785  LLVM_DEBUG(MF.print(dbgs()));
786 
787  return Changed;
788 }
789 
790 INITIALIZE_PASS(X86DomainReassignment, "x86-domain-reassignment",
791  "X86 Domain Reassignment Pass", false, false)
792 
793 /// Returns an instance of the Domain Reassignment pass.
795  return new X86DomainReassignment();
796 }
void DeleteContainerSeconds(Container &C)
In a container of pairs (usually a map) whose second element is a pointer, deletes the second element...
Definition: STLExtras.h:1152
uint64_t CallInst * C
const MachineInstrBuilder & add(const MachineOperand &MO) const
static bool usedAsAddr(const MachineInstr &MI, unsigned Reg, const TargetInstrInfo *TII)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
This class represents lattice values for constants.
Definition: AllocatorList.h:24
iterator_range< mop_iterator > explicit_operands()
Definition: MachineInstr.h:465
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:383
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:164
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
Definition: MachineInstr.h:830
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:459
FunctionPass * createX86DomainReassignmentPass()
Return a Machine IR pass that reassigns instruction chains from one domain to another, when profitable.
return AArch64::GPR64RegClass contains(Reg)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:412
const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum...
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
INITIALIZE_PASS(X86DomainReassignment, "x86-domain-reassignment", "X86 Domain Reassignment Pass", false, false) FunctionPass *llvm
Returns an instance of the Domain Reassignment pass.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
AddrNumOperands - Total number of operands in a memory reference.
Definition: X86BaseInfo.h:42
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:406
static int getID(struct InternalInstruction *insn, const void *miiArg)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:419
const TargetRegisterInfo * getTargetRegisterInfo() const
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineInstrBuilder & UseMI
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:188
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
unsigned getOperandBias(const MCInstrDesc &Desc)
getOperandBias - compute whether all of the def operands are repeated in the uses and therefore shoul...
Definition: X86BaseInfo.h:658
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void initializeX86DomainReassignmentPass(PassRegistry &)
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:204
BlockVerifier::State From
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
MachineInstrBuilder MachineInstrBuilder & DefMI
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
A range adaptor for a pair of iterators.
iterator_range< mop_iterator > implicit_operands()
Definition: MachineInstr.h:473
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
static cl::opt< bool > DisableX86DomainReassignment("disable-x86-domain-reassignment", cl::Hidden, cl::desc("X86: Disable Virtual Register Reassignment."), cl::init(false))
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
#define I(x, y, z)
Definition: MD5.cpp:58
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:124
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
inst_range instructions(Function *F)
Definition: InstIterator.h:134
bool hasImplicitDefOfPhysReg(unsigned Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
Definition: MCInstrDesc.cpp:45
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
int getMemoryOperandNo(uint64_t TSFlags)
getMemoryOperandNo - The function returns the MCInst operand # for the first field of the memory oper...
Definition: X86BaseInfo.h:699