LLVM  16.0.0git
X86DomainReassignment.cpp
Go to the documentation of this file.
1 //===--- X86DomainReassignment.cpp - Selectively switch register classes---===//
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 // This pass attempts to find instruction chains (closures) in one domain,
10 // and convert them to equivalent instructions in a different domain,
11 // if profitable.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "X86.h"
16 #include "X86InstrInfo.h"
17 #include "X86Subtarget.h"
18 #include "llvm/ADT/BitVector.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() = default;
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 (const 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  const DebugLoc &DL = MI->getDebugLoc();
185 
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 (const MachineOperand &MO : llvm::drop_begin(MI->operands()))
191  Bld.add(MO);
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  Register DstReg = MI->getOperand(0).getReg();
224  if (DstReg.isPhysical() && (X86::GR8RegClass.contains(DstReg) ||
225  X86::GR16RegClass.contains(DstReg)))
226  return false;
227  Register SrcReg = MI->getOperand(1).getReg();
228  if (SrcReg.isPhysical() && (X86::GR8RegClass.contains(SrcReg) ||
229  X86::GR16RegClass.contains(SrcReg)))
230  return false;
231 
232  return true;
233  }
234 
235  double getExtraCost(const MachineInstr *MI,
236  MachineRegisterInfo *MRI) const override {
237  assert(MI->getOpcode() == TargetOpcode::COPY && "Expected a COPY");
238 
239  for (const auto &MO : MI->operands()) {
240  // Physical registers will not be converted. Assume that converting the
241  // COPY to the destination domain will eventually result in a actual
242  // instruction.
243  if (Register::isPhysicalRegister(MO.getReg()))
244  return 1;
245 
246  RegDomain OpDomain = getDomain(MRI->getRegClass(MO.getReg()),
248  // Converting a cross domain COPY to a same domain COPY should eliminate
249  // an insturction
250  if (OpDomain == DstDomain)
251  return -1;
252  }
253  return 0;
254  }
255 };
256 
257 /// An Instruction Converter which replaces an instruction with a COPY.
258 class InstrReplaceWithCopy : public InstrConverterBase {
259 public:
260  // Source instruction operand Index, to be used as the COPY source.
261  unsigned SrcOpIdx;
262 
263  InstrReplaceWithCopy(unsigned SrcOpcode, unsigned SrcOpIdx)
264  : InstrConverterBase(SrcOpcode), SrcOpIdx(SrcOpIdx) {}
265 
266  bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
267  MachineRegisterInfo *MRI) const override {
268  assert(isLegal(MI, TII) && "Cannot convert instruction");
269  BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
270  TII->get(TargetOpcode::COPY))
271  .add({MI->getOperand(0), MI->getOperand(SrcOpIdx)});
272  return true;
273  }
274 
275  double getExtraCost(const MachineInstr *MI,
276  MachineRegisterInfo *MRI) const override {
277  return 0;
278  }
279 };
280 
281 // Key type to be used by the Instruction Converters map.
282 // A converter is identified by <destination domain, source opcode>
283 typedef std::pair<int, unsigned> InstrConverterBaseKeyTy;
284 
286  InstrConverterBaseMap;
287 
288 /// A closure is a set of virtual register representing all of the edges in
289 /// the closure, as well as all of the instructions connected by those edges.
290 ///
291 /// A closure may encompass virtual registers in the same register bank that
292 /// have different widths. For example, it may contain 32-bit GPRs as well as
293 /// 64-bit GPRs.
294 ///
295 /// A closure that computes an address (i.e. defines a virtual register that is
296 /// used in a memory operand) excludes the instructions that contain memory
297 /// operands using the address. Such an instruction will be included in a
298 /// different closure that manipulates the loaded or stored value.
299 class Closure {
300 private:
301  /// Virtual registers in the closure.
302  DenseSet<Register> Edges;
303 
304  /// Instructions in the closure.
306 
307  /// Domains which this closure can legally be reassigned to.
308  std::bitset<NumDomains> LegalDstDomains;
309 
310  /// An ID to uniquely identify this closure, even when it gets
311  /// moved around
312  unsigned ID;
313 
314 public:
315  Closure(unsigned ID, std::initializer_list<RegDomain> LegalDstDomainList) : ID(ID) {
316  for (RegDomain D : LegalDstDomainList)
317  LegalDstDomains.set(D);
318  }
319 
320  /// Mark this closure as illegal for reassignment to all domains.
321  void setAllIllegal() { LegalDstDomains.reset(); }
322 
323  /// \returns true if this closure has domains which are legal to reassign to.
324  bool hasLegalDstDomain() const { return LegalDstDomains.any(); }
325 
326  /// \returns true if is legal to reassign this closure to domain \p RD.
327  bool isLegal(RegDomain RD) const { return LegalDstDomains[RD]; }
328 
329  /// Mark this closure as illegal for reassignment to domain \p RD.
330  void setIllegal(RegDomain RD) { LegalDstDomains[RD] = false; }
331 
332  bool empty() const { return Edges.empty(); }
333 
334  bool insertEdge(Register Reg) { return Edges.insert(Reg).second; }
335 
336  using const_edge_iterator = DenseSet<Register>::const_iterator;
338  return iterator_range<const_edge_iterator>(Edges.begin(), Edges.end());
339  }
340 
341  void addInstruction(MachineInstr *I) {
342  Instrs.push_back(I);
343  }
344 
346  return Instrs;
347  }
348 
349  LLVM_DUMP_METHOD void dump(const MachineRegisterInfo *MRI) const {
350  dbgs() << "Registers: ";
351  bool First = true;
352  for (Register Reg : Edges) {
353  if (!First)
354  dbgs() << ", ";
355  First = false;
357  }
358  dbgs() << "\n" << "Instructions:";
359  for (MachineInstr *MI : Instrs) {
360  dbgs() << "\n ";
361  MI->print(dbgs());
362  }
363  dbgs() << "\n";
364  }
365 
366  unsigned getID() const {
367  return ID;
368  }
369 
370 };
371 
372 class X86DomainReassignment : public MachineFunctionPass {
373  const X86Subtarget *STI = nullptr;
374  MachineRegisterInfo *MRI = nullptr;
375  const X86InstrInfo *TII = nullptr;
376 
377  /// All edges that are included in some closure
378  BitVector EnclosedEdges{8, false};
379 
380  /// All instructions that are included in some closure.
381  DenseMap<MachineInstr *, unsigned> EnclosedInstrs;
382 
383 public:
384  static char ID;
385 
386  X86DomainReassignment() : MachineFunctionPass(ID) { }
387 
388  bool runOnMachineFunction(MachineFunction &MF) override;
389 
390  void getAnalysisUsage(AnalysisUsage &AU) const override {
391  AU.setPreservesCFG();
393  }
394 
395  StringRef getPassName() const override {
396  return "X86 Domain Reassignment Pass";
397  }
398 
399 private:
400  /// A map of available Instruction Converters.
401  InstrConverterBaseMap Converters;
402 
403  /// Initialize Converters map.
404  void initConverters();
405 
406  /// Starting from \Reg, expand the closure as much as possible.
407  void buildClosure(Closure &, Register Reg);
408 
409  /// Enqueue \p Reg to be considered for addition to the closure.
410  void visitRegister(Closure &, Register Reg, RegDomain &Domain,
411  SmallVectorImpl<unsigned> &Worklist);
412 
413  /// Reassign the closure to \p Domain.
414  void reassign(const Closure &C, RegDomain Domain) const;
415 
416  /// Add \p MI to the closure.
417  void encloseInstr(Closure &C, MachineInstr *MI);
418 
419  /// /returns true if it is profitable to reassign the closure to \p Domain.
420  bool isReassignmentProfitable(const Closure &C, RegDomain Domain) const;
421 
422  /// Calculate the total cost of reassigning the closure to \p Domain.
423  double calculateCost(const Closure &C, RegDomain Domain) const;
424 };
425 
427 
428 } // End anonymous namespace.
429 
430 void X86DomainReassignment::visitRegister(Closure &C, Register Reg,
431  RegDomain &Domain,
432  SmallVectorImpl<unsigned> &Worklist) {
433  if (!Reg.isVirtual())
434  return;
435 
436  if (EnclosedEdges.test(Register::virtReg2Index(Reg)))
437  return;
438 
439  if (!MRI->hasOneDef(Reg))
440  return;
441 
442  RegDomain RD = getDomain(MRI->getRegClass(Reg), MRI->getTargetRegisterInfo());
443  // First edge in closure sets the domain.
444  if (Domain == NoDomain)
445  Domain = RD;
446 
447  if (Domain != RD)
448  return;
449 
450  Worklist.push_back(Reg);
451 }
452 
453 void X86DomainReassignment::encloseInstr(Closure &C, MachineInstr *MI) {
454  auto I = EnclosedInstrs.find(MI);
455  if (I != EnclosedInstrs.end()) {
456  if (I->second != C.getID())
457  // Instruction already belongs to another closure, avoid conflicts between
458  // closure and mark this closure as illegal.
459  C.setAllIllegal();
460  return;
461  }
462 
463  EnclosedInstrs[MI] = C.getID();
464  C.addInstruction(MI);
465 
466  // Mark closure as illegal for reassignment to domains, if there is no
467  // converter for the instruction or if the converter cannot convert the
468  // instruction.
469  for (int i = 0; i != NumDomains; ++i) {
470  if (C.isLegal((RegDomain)i)) {
471  auto I = Converters.find({i, MI->getOpcode()});
472  if (I == Converters.end() || !I->second->isLegal(MI, TII))
473  C.setIllegal((RegDomain)i);
474  }
475  }
476 }
477 
478 double X86DomainReassignment::calculateCost(const Closure &C,
479  RegDomain DstDomain) const {
480  assert(C.isLegal(DstDomain) && "Cannot calculate cost for illegal closure");
481 
482  double Cost = 0.0;
483  for (auto *MI : C.instructions())
484  Cost += Converters.find({DstDomain, MI->getOpcode()})
485  ->second->getExtraCost(MI, MRI);
486  return Cost;
487 }
488 
489 bool X86DomainReassignment::isReassignmentProfitable(const Closure &C,
490  RegDomain Domain) const {
491  return calculateCost(C, Domain) < 0.0;
492 }
493 
494 void X86DomainReassignment::reassign(const Closure &C, RegDomain Domain) const {
495  assert(C.isLegal(Domain) && "Cannot convert illegal closure");
496 
497  // Iterate all instructions in the closure, convert each one using the
498  // appropriate converter.
500  for (auto *MI : C.instructions())
501  if (Converters.find({Domain, MI->getOpcode()})
502  ->second->convertInstr(MI, TII, MRI))
503  ToErase.push_back(MI);
504 
505  // Iterate all registers in the closure, replace them with registers in the
506  // destination domain.
507  for (Register Reg : C.edges()) {
508  MRI->setRegClass(Reg, getDstRC(MRI->getRegClass(Reg), Domain));
509  for (auto &MO : MRI->use_operands(Reg)) {
510  if (MO.isReg())
511  // Remove all subregister references as they are not valid in the
512  // destination domain.
513  MO.setSubReg(0);
514  }
515  }
516 
517  for (auto *MI : ToErase)
518  MI->eraseFromParent();
519 }
520 
521 /// \returns true when \p Reg is used as part of an address calculation in \p
522 /// MI.
523 static bool usedAsAddr(const MachineInstr &MI, Register Reg,
524  const TargetInstrInfo *TII) {
525  if (!MI.mayLoadOrStore())
526  return false;
527 
528  const MCInstrDesc &Desc = TII->get(MI.getOpcode());
529  int MemOpStart = X86II::getMemoryOperandNo(Desc.TSFlags);
530  if (MemOpStart == -1)
531  return false;
532 
533  MemOpStart += X86II::getOperandBias(Desc);
534  for (unsigned MemOpIdx = MemOpStart,
535  MemOpEnd = MemOpStart + X86::AddrNumOperands;
536  MemOpIdx < MemOpEnd; ++MemOpIdx) {
537  const MachineOperand &Op = MI.getOperand(MemOpIdx);
538  if (Op.isReg() && Op.getReg() == Reg)
539  return true;
540  }
541  return false;
542 }
543 
544 void X86DomainReassignment::buildClosure(Closure &C, Register Reg) {
545  SmallVector<unsigned, 4> Worklist;
546  RegDomain Domain = NoDomain;
547  visitRegister(C, Reg, Domain, Worklist);
548  while (!Worklist.empty()) {
549  unsigned CurReg = Worklist.pop_back_val();
550 
551  // Register already in this closure.
552  if (!C.insertEdge(CurReg))
553  continue;
554  EnclosedEdges.set(Register::virtReg2Index(Reg));
555 
556  MachineInstr *DefMI = MRI->getVRegDef(CurReg);
557  encloseInstr(C, DefMI);
558 
559  // Add register used by the defining MI to the worklist.
560  // Do not add registers which are used in address calculation, they will be
561  // added to a different closure.
562  int OpEnd = DefMI->getNumOperands();
563  const MCInstrDesc &Desc = DefMI->getDesc();
565  if (MemOp != -1)
566  MemOp += X86II::getOperandBias(Desc);
567  for (int OpIdx = 0; OpIdx < OpEnd; ++OpIdx) {
568  if (OpIdx == MemOp) {
569  // skip address calculation.
570  OpIdx += (X86::AddrNumOperands - 1);
571  continue;
572  }
573  auto &Op = DefMI->getOperand(OpIdx);
574  if (!Op.isReg() || !Op.isUse())
575  continue;
576  visitRegister(C, Op.getReg(), Domain, Worklist);
577  }
578 
579  // Expand closure through register uses.
580  for (auto &UseMI : MRI->use_nodbg_instructions(CurReg)) {
581  // We would like to avoid converting closures which calculare addresses,
582  // as this should remain in GPRs.
583  if (usedAsAddr(UseMI, CurReg, TII)) {
584  C.setAllIllegal();
585  continue;
586  }
587  encloseInstr(C, &UseMI);
588 
589  for (auto &DefOp : UseMI.defs()) {
590  if (!DefOp.isReg())
591  continue;
592 
593  Register DefReg = DefOp.getReg();
594  if (!DefReg.isVirtual()) {
595  C.setAllIllegal();
596  continue;
597  }
598  visitRegister(C, DefReg, Domain, Worklist);
599  }
600  }
601  }
602 }
603 
604 void X86DomainReassignment::initConverters() {
605  Converters[{MaskDomain, TargetOpcode::PHI}] =
606  std::make_unique<InstrIgnore>(TargetOpcode::PHI);
607 
608  Converters[{MaskDomain, TargetOpcode::IMPLICIT_DEF}] =
609  std::make_unique<InstrIgnore>(TargetOpcode::IMPLICIT_DEF);
610 
611  Converters[{MaskDomain, TargetOpcode::INSERT_SUBREG}] =
612  std::make_unique<InstrReplaceWithCopy>(TargetOpcode::INSERT_SUBREG, 2);
613 
614  Converters[{MaskDomain, TargetOpcode::COPY}] =
615  std::make_unique<InstrCOPYReplacer>(TargetOpcode::COPY, MaskDomain,
616  TargetOpcode::COPY);
617 
618  auto createReplacerDstCOPY = [&](unsigned From, unsigned To) {
619  Converters[{MaskDomain, From}] =
620  std::make_unique<InstrReplacerDstCOPY>(From, To);
621  };
622 
623  createReplacerDstCOPY(X86::MOVZX32rm16, X86::KMOVWkm);
624  createReplacerDstCOPY(X86::MOVZX64rm16, X86::KMOVWkm);
625 
626  createReplacerDstCOPY(X86::MOVZX32rr16, X86::KMOVWkk);
627  createReplacerDstCOPY(X86::MOVZX64rr16, X86::KMOVWkk);
628 
629  if (STI->hasDQI()) {
630  createReplacerDstCOPY(X86::MOVZX16rm8, X86::KMOVBkm);
631  createReplacerDstCOPY(X86::MOVZX32rm8, X86::KMOVBkm);
632  createReplacerDstCOPY(X86::MOVZX64rm8, X86::KMOVBkm);
633 
634  createReplacerDstCOPY(X86::MOVZX16rr8, X86::KMOVBkk);
635  createReplacerDstCOPY(X86::MOVZX32rr8, X86::KMOVBkk);
636  createReplacerDstCOPY(X86::MOVZX64rr8, X86::KMOVBkk);
637  }
638 
639  auto createReplacer = [&](unsigned From, unsigned To) {
640  Converters[{MaskDomain, From}] = std::make_unique<InstrReplacer>(From, To);
641  };
642 
643  createReplacer(X86::MOV16rm, X86::KMOVWkm);
644  createReplacer(X86::MOV16mr, X86::KMOVWmk);
645  createReplacer(X86::MOV16rr, X86::KMOVWkk);
646  createReplacer(X86::SHR16ri, X86::KSHIFTRWri);
647  createReplacer(X86::SHL16ri, X86::KSHIFTLWri);
648  createReplacer(X86::NOT16r, X86::KNOTWrr);
649  createReplacer(X86::OR16rr, X86::KORWrr);
650  createReplacer(X86::AND16rr, X86::KANDWrr);
651  createReplacer(X86::XOR16rr, X86::KXORWrr);
652 
653  if (STI->hasBWI()) {
654  createReplacer(X86::MOV32rm, X86::KMOVDkm);
655  createReplacer(X86::MOV64rm, X86::KMOVQkm);
656 
657  createReplacer(X86::MOV32mr, X86::KMOVDmk);
658  createReplacer(X86::MOV64mr, X86::KMOVQmk);
659 
660  createReplacer(X86::MOV32rr, X86::KMOVDkk);
661  createReplacer(X86::MOV64rr, X86::KMOVQkk);
662 
663  createReplacer(X86::SHR32ri, X86::KSHIFTRDri);
664  createReplacer(X86::SHR64ri, X86::KSHIFTRQri);
665 
666  createReplacer(X86::SHL32ri, X86::KSHIFTLDri);
667  createReplacer(X86::SHL64ri, X86::KSHIFTLQri);
668 
669  createReplacer(X86::ADD32rr, X86::KADDDrr);
670  createReplacer(X86::ADD64rr, X86::KADDQrr);
671 
672  createReplacer(X86::NOT32r, X86::KNOTDrr);
673  createReplacer(X86::NOT64r, X86::KNOTQrr);
674 
675  createReplacer(X86::OR32rr, X86::KORDrr);
676  createReplacer(X86::OR64rr, X86::KORQrr);
677 
678  createReplacer(X86::AND32rr, X86::KANDDrr);
679  createReplacer(X86::AND64rr, X86::KANDQrr);
680 
681  createReplacer(X86::ANDN32rr, X86::KANDNDrr);
682  createReplacer(X86::ANDN64rr, X86::KANDNQrr);
683 
684  createReplacer(X86::XOR32rr, X86::KXORDrr);
685  createReplacer(X86::XOR64rr, X86::KXORQrr);
686 
687  // TODO: KTEST is not a replacement for TEST due to flag differences. Need
688  // to prove only Z flag is used.
689  //createReplacer(X86::TEST32rr, X86::KTESTDrr);
690  //createReplacer(X86::TEST64rr, X86::KTESTQrr);
691  }
692 
693  if (STI->hasDQI()) {
694  createReplacer(X86::ADD8rr, X86::KADDBrr);
695  createReplacer(X86::ADD16rr, X86::KADDWrr);
696 
697  createReplacer(X86::AND8rr, X86::KANDBrr);
698 
699  createReplacer(X86::MOV8rm, X86::KMOVBkm);
700  createReplacer(X86::MOV8mr, X86::KMOVBmk);
701  createReplacer(X86::MOV8rr, X86::KMOVBkk);
702 
703  createReplacer(X86::NOT8r, X86::KNOTBrr);
704 
705  createReplacer(X86::OR8rr, X86::KORBrr);
706 
707  createReplacer(X86::SHR8ri, X86::KSHIFTRBri);
708  createReplacer(X86::SHL8ri, X86::KSHIFTLBri);
709 
710  // TODO: KTEST is not a replacement for TEST due to flag differences. Need
711  // to prove only Z flag is used.
712  //createReplacer(X86::TEST8rr, X86::KTESTBrr);
713  //createReplacer(X86::TEST16rr, X86::KTESTWrr);
714 
715  createReplacer(X86::XOR8rr, X86::KXORBrr);
716  }
717 }
718 
719 bool X86DomainReassignment::runOnMachineFunction(MachineFunction &MF) {
720  if (skipFunction(MF.getFunction()))
721  return false;
723  return false;
724 
725  LLVM_DEBUG(
726  dbgs() << "***** Machine Function before Domain Reassignment *****\n");
727  LLVM_DEBUG(MF.print(dbgs()));
728 
729  STI = &MF.getSubtarget<X86Subtarget>();
730  // GPR->K is the only transformation currently supported, bail out early if no
731  // AVX512.
732  // TODO: We're also bailing of AVX512BW isn't supported since we use VK32 and
733  // VK64 for GR32/GR64, but those aren't legal classes on KNL. If the register
734  // coalescer doesn't clean it up and we generate a spill we will crash.
735  if (!STI->hasAVX512() || !STI->hasBWI())
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  EnclosedEdges.resize(MRI->getNumVirtRegs());
747  EnclosedInstrs.clear();
748 
749  std::vector<Closure> Closures;
750 
751  // Go over all virtual registers and calculate a closure.
752  unsigned ClosureID = 0;
753  for (unsigned Idx = 0; Idx < MRI->getNumVirtRegs(); ++Idx) {
755 
756  // GPR only current source domain supported.
757  if (!isGPR(MRI->getRegClass(Reg)))
758  continue;
759 
760  // Register already in closure.
761  if (EnclosedEdges.test(Idx))
762  continue;
763 
764  // Calculate closure starting with Reg.
765  Closure C(ClosureID++, {MaskDomain});
766  buildClosure(C, Reg);
767 
768  // Collect all closures that can potentially be converted.
769  if (!C.empty() && C.isLegal(MaskDomain))
770  Closures.push_back(std::move(C));
771  }
772 
773  for (Closure &C : Closures) {
774  LLVM_DEBUG(C.dump(MRI));
775  if (isReassignmentProfitable(C, MaskDomain)) {
776  reassign(C, MaskDomain);
777  ++NumClosuresConverted;
778  Changed = true;
779  }
780  }
781 
782  LLVM_DEBUG(
783  dbgs() << "***** Machine Function after Domain Reassignment *****\n");
784  LLVM_DEBUG(MF.print(dbgs()));
785 
786  return Changed;
787 }
788 
789 INITIALIZE_PASS(X86DomainReassignment, "x86-domain-reassignment",
790  "X86 Domain Reassignment Pass", false, false)
791 
792 /// Returns an instance of the Domain Reassignment pass.
794  return new X86DomainReassignment();
795 }
i
i
Definition: README.txt:29
INITIALIZE_PASS
INITIALIZE_PASS(X86DomainReassignment, "x86-domain-reassignment", "X86 Domain Reassignment Pass", false, false) FunctionPass *llvm
Returns an instance of the Domain Reassignment pass.
Definition: X86DomainReassignment.cpp:789
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::X86II::getMemoryOperandNo
int getMemoryOperandNo(uint64_t TSFlags)
The function returns the MCInst operand # for the first field of the memory operand.
Definition: X86BaseInfo.h:1100
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:107
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:387
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::MachineRegisterInfo::createVirtualRegister
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
Definition: MachineRegisterInfo.cpp:156
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
X86Subtarget.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
Printable.h
llvm::MachineInstrBuilder::add
const MachineInstrBuilder & add(const MachineOperand &MO) const
Definition: MachineInstrBuilder.h:224
usedAsAddr
static bool usedAsAddr(const MachineInstr &MI, Register Reg, const TargetInstrInfo *TII)
Definition: X86DomainReassignment.cpp:523
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::X86Subtarget
Definition: X86Subtarget.h:52
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:151
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::MemOp
Definition: TargetLowering.h:111
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::MachineInstr::getDesc
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:513
DenseMap.h
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:477
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:770
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
STLExtras.h
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::MCInstrDesc::TSFlags
uint64_t TSFlags
Definition: MCInstrDesc.h:205
X86.h
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::X86::AddrNumOperands
@ AddrNumOperands
AddrNumOperands - Total number of operands in a memory reference.
Definition: X86BaseInfo.h:41
InlinePriorityMode::Cost
@ Cost
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:709
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
BitVector.h
DisableX86DomainReassignment
static cl::opt< bool > DisableX86DomainReassignment("disable-x86-domain-reassignment", cl::Hidden, cl::desc("X86: Disable Virtual Register Reassignment."), cl::init(false))
llvm::BitVector
Definition: BitVector.h:75
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:396
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
getDomain
Domain getDomain(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:711
llvm::Pass::print
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:130
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::MachineRegisterInfo::isSSA
bool isSSA() const
Definition: MachineRegisterInfo.h:183
llvm::Register::isVirtual
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::cl::opt< bool >
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::X86II::getOperandBias
unsigned getOperandBias(const MCInstrDesc &Desc)
Compute whether all of the def operands are repeated in the uses and therefore should be skipped.
Definition: X86BaseInfo.h:1060
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::createX86DomainReassignmentPass
FunctionPass * createX86DomainReassignmentPass()
Return a Machine IR pass that reassigns instruction chains from one domain to another,...
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::empty
bool empty() const
Definition: DenseSet.h:80
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
MachineFunctionPass.h
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::begin
iterator begin()
Definition: DenseSet.h:173
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineRegisterInfo::hasOneDef
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
Definition: MachineRegisterInfo.h:452
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::X86InstrInfo
Definition: X86InstrInfo.h:138
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:623
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::MachineFunction::print
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
Definition: MachineFunction.cpp:571
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
SmallVector.h
MachineInstrBuilder.h
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:108
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::SmallVectorImpl< unsigned >
DenseMapInfo.h
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::Register::virtReg2Index
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:413
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:111
X86InstrInfo.h
TargetRegisterInfo.h
Debug.h
llvm::MachineRegisterInfo::setRegClass
void setRegClass(Register Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
Definition: MachineRegisterInfo.cpp:56