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