xref: /freebsd/contrib/llvm-project/llvm/lib/Target/X86/X86DomainReassignment.cpp (revision f976241773df2260e6170317080761d1c5814fe5)
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"
23 #include "llvm/CodeGen/MachineFunctionPass.h"
24 #include "llvm/CodeGen/MachineInstrBuilder.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/TargetRegisterInfo.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 
37 static cl::opt<bool> DisableX86DomainReassignment(
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 (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     auto &DL = MI->getDebugLoc();
184 
185     unsigned Reg = MRI->createVirtualRegister(
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     unsigned DstReg = MI->getOperand(0).getReg();
223     if (TargetRegisterInfo::isPhysicalRegister(DstReg) &&
224         (X86::GR8RegClass.contains(DstReg) ||
225          X86::GR16RegClass.contains(DstReg)))
226       return false;
227     unsigned SrcReg = MI->getOperand(1).getReg();
228     if (TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
229         (X86::GR8RegClass.contains(SrcReg) ||
230          X86::GR16RegClass.contains(SrcReg)))
231       return false;
232 
233     return true;
234   }
235 
236   double getExtraCost(const MachineInstr *MI,
237                       MachineRegisterInfo *MRI) const override {
238     assert(MI->getOpcode() == TargetOpcode::COPY && "Expected a COPY");
239 
240     for (auto &MO : MI->operands()) {
241       // Physical registers will not be converted. Assume that converting the
242       // COPY to the destination domain will eventually result in a actual
243       // instruction.
244       if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
245         return 1;
246 
247       RegDomain OpDomain = getDomain(MRI->getRegClass(MO.getReg()),
248                                      MRI->getTargetRegisterInfo());
249       // Converting a cross domain COPY to a same domain COPY should eliminate
250       // an insturction
251       if (OpDomain == DstDomain)
252         return -1;
253     }
254     return 0;
255   }
256 };
257 
258 /// An Instruction Converter which replaces an instruction with a COPY.
259 class InstrReplaceWithCopy : public InstrConverterBase {
260 public:
261   // Source instruction operand Index, to be used as the COPY source.
262   unsigned SrcOpIdx;
263 
264   InstrReplaceWithCopy(unsigned SrcOpcode, unsigned SrcOpIdx)
265       : InstrConverterBase(SrcOpcode), SrcOpIdx(SrcOpIdx) {}
266 
267   bool convertInstr(MachineInstr *MI, const TargetInstrInfo *TII,
268                     MachineRegisterInfo *MRI) const override {
269     assert(isLegal(MI, TII) && "Cannot convert instruction");
270     BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
271             TII->get(TargetOpcode::COPY))
272         .add({MI->getOperand(0), MI->getOperand(SrcOpIdx)});
273     return true;
274   }
275 
276   double getExtraCost(const MachineInstr *MI,
277                       MachineRegisterInfo *MRI) const override {
278     return 0;
279   }
280 };
281 
282 // Key type to be used by the Instruction Converters map.
283 // A converter is identified by <destination domain, source opcode>
284 typedef std::pair<int, unsigned> InstrConverterBaseKeyTy;
285 
286 typedef DenseMap<InstrConverterBaseKeyTy, InstrConverterBase *>
287     InstrConverterBaseMap;
288 
289 /// A closure is a set of virtual register representing all of the edges in
290 /// the closure, as well as all of the instructions connected by those edges.
291 ///
292 /// A closure may encompass virtual registers in the same register bank that
293 /// have different widths. For example, it may contain 32-bit GPRs as well as
294 /// 64-bit GPRs.
295 ///
296 /// A closure that computes an address (i.e. defines a virtual register that is
297 /// used in a memory operand) excludes the instructions that contain memory
298 /// operands using the address. Such an instruction will be included in a
299 /// different closure that manipulates the loaded or stored value.
300 class Closure {
301 private:
302   /// Virtual registers in the closure.
303   DenseSet<unsigned> Edges;
304 
305   /// Instructions in the closure.
306   SmallVector<MachineInstr *, 8> Instrs;
307 
308   /// Domains which this closure can legally be reassigned to.
309   std::bitset<NumDomains> LegalDstDomains;
310 
311   /// An ID to uniquely identify this closure, even when it gets
312   /// moved around
313   unsigned ID;
314 
315 public:
316   Closure(unsigned ID, std::initializer_list<RegDomain> LegalDstDomainList) : ID(ID) {
317     for (RegDomain D : LegalDstDomainList)
318       LegalDstDomains.set(D);
319   }
320 
321   /// Mark this closure as illegal for reassignment to all domains.
322   void setAllIllegal() { LegalDstDomains.reset(); }
323 
324   /// \returns true if this closure has domains which are legal to reassign to.
325   bool hasLegalDstDomain() const { return LegalDstDomains.any(); }
326 
327   /// \returns true if is legal to reassign this closure to domain \p RD.
328   bool isLegal(RegDomain RD) const { return LegalDstDomains[RD]; }
329 
330   /// Mark this closure as illegal for reassignment to domain \p RD.
331   void setIllegal(RegDomain RD) { LegalDstDomains[RD] = false; }
332 
333   bool empty() const { return Edges.empty(); }
334 
335   bool insertEdge(unsigned Reg) {
336     return Edges.insert(Reg).second;
337   }
338 
339   using const_edge_iterator = DenseSet<unsigned>::const_iterator;
340   iterator_range<const_edge_iterator> edges() const {
341     return iterator_range<const_edge_iterator>(Edges.begin(), Edges.end());
342   }
343 
344   void addInstruction(MachineInstr *I) {
345     Instrs.push_back(I);
346   }
347 
348   ArrayRef<MachineInstr *> instructions() const {
349     return Instrs;
350   }
351 
352   LLVM_DUMP_METHOD void dump(const MachineRegisterInfo *MRI) const {
353     dbgs() << "Registers: ";
354     bool First = true;
355     for (unsigned Reg : Edges) {
356       if (!First)
357         dbgs() << ", ";
358       First = false;
359       dbgs() << printReg(Reg, MRI->getTargetRegisterInfo(), 0, MRI);
360     }
361     dbgs() << "\n" << "Instructions:";
362     for (MachineInstr *MI : Instrs) {
363       dbgs() << "\n  ";
364       MI->print(dbgs());
365     }
366     dbgs() << "\n";
367   }
368 
369   unsigned getID() const {
370     return ID;
371   }
372 
373 };
374 
375 class X86DomainReassignment : public MachineFunctionPass {
376   const X86Subtarget *STI;
377   MachineRegisterInfo *MRI;
378   const X86InstrInfo *TII;
379 
380   /// All edges that are included in some closure
381   DenseSet<unsigned> EnclosedEdges;
382 
383   /// All instructions that are included in some closure.
384   DenseMap<MachineInstr *, unsigned> EnclosedInstrs;
385 
386 public:
387   static char ID;
388 
389   X86DomainReassignment() : MachineFunctionPass(ID) { }
390 
391   bool runOnMachineFunction(MachineFunction &MF) override;
392 
393   void getAnalysisUsage(AnalysisUsage &AU) const override {
394     AU.setPreservesCFG();
395     MachineFunctionPass::getAnalysisUsage(AU);
396   }
397 
398   StringRef getPassName() const override {
399     return "X86 Domain Reassignment Pass";
400   }
401 
402 private:
403   /// A map of available Instruction Converters.
404   InstrConverterBaseMap Converters;
405 
406   /// Initialize Converters map.
407   void initConverters();
408 
409   /// Starting from \Reg, expand the closure as much as possible.
410   void buildClosure(Closure &, unsigned Reg);
411 
412   /// Enqueue \p Reg to be considered for addition to the closure.
413   void visitRegister(Closure &, unsigned Reg, RegDomain &Domain,
414                      SmallVectorImpl<unsigned> &Worklist);
415 
416   /// Reassign the closure to \p Domain.
417   void reassign(const Closure &C, RegDomain Domain) const;
418 
419   /// Add \p MI to the closure.
420   void encloseInstr(Closure &C, MachineInstr *MI);
421 
422   /// /returns true if it is profitable to reassign the closure to \p Domain.
423   bool isReassignmentProfitable(const Closure &C, RegDomain Domain) const;
424 
425   /// Calculate the total cost of reassigning the closure to \p Domain.
426   double calculateCost(const Closure &C, RegDomain Domain) const;
427 };
428 
429 char X86DomainReassignment::ID = 0;
430 
431 } // End anonymous namespace.
432 
433 void X86DomainReassignment::visitRegister(Closure &C, unsigned Reg,
434                                           RegDomain &Domain,
435                                           SmallVectorImpl<unsigned> &Worklist) {
436   if (EnclosedEdges.count(Reg))
437     return;
438 
439   if (!TargetRegisterInfo::isVirtualRegister(Reg))
440     return;
441 
442   if (!MRI->hasOneDef(Reg))
443     return;
444 
445   RegDomain RD = getDomain(MRI->getRegClass(Reg), MRI->getTargetRegisterInfo());
446   // First edge in closure sets the domain.
447   if (Domain == NoDomain)
448     Domain = RD;
449 
450   if (Domain != RD)
451     return;
452 
453   Worklist.push_back(Reg);
454 }
455 
456 void X86DomainReassignment::encloseInstr(Closure &C, MachineInstr *MI) {
457   auto I = EnclosedInstrs.find(MI);
458   if (I != EnclosedInstrs.end()) {
459     if (I->second != C.getID())
460       // Instruction already belongs to another closure, avoid conflicts between
461       // closure and mark this closure as illegal.
462       C.setAllIllegal();
463     return;
464   }
465 
466   EnclosedInstrs[MI] = C.getID();
467   C.addInstruction(MI);
468 
469   // Mark closure as illegal for reassignment to domains, if there is no
470   // converter for the instruction or if the converter cannot convert the
471   // instruction.
472   for (int i = 0; i != NumDomains; ++i) {
473     if (C.isLegal((RegDomain)i)) {
474       InstrConverterBase *IC = Converters.lookup({i, MI->getOpcode()});
475       if (!IC || !IC->isLegal(MI, TII))
476         C.setIllegal((RegDomain)i);
477     }
478   }
479 }
480 
481 double X86DomainReassignment::calculateCost(const Closure &C,
482                                             RegDomain DstDomain) const {
483   assert(C.isLegal(DstDomain) && "Cannot calculate cost for illegal closure");
484 
485   double Cost = 0.0;
486   for (auto *MI : C.instructions())
487     Cost +=
488         Converters.lookup({DstDomain, MI->getOpcode()})->getExtraCost(MI, MRI);
489   return Cost;
490 }
491 
492 bool X86DomainReassignment::isReassignmentProfitable(const Closure &C,
493                                                      RegDomain Domain) const {
494   return calculateCost(C, Domain) < 0.0;
495 }
496 
497 void X86DomainReassignment::reassign(const Closure &C, RegDomain Domain) const {
498   assert(C.isLegal(Domain) && "Cannot convert illegal closure");
499 
500   // Iterate all instructions in the closure, convert each one using the
501   // appropriate converter.
502   SmallVector<MachineInstr *, 8> ToErase;
503   for (auto *MI : C.instructions())
504     if (Converters.lookup({Domain, MI->getOpcode()})
505             ->convertInstr(MI, TII, MRI))
506       ToErase.push_back(MI);
507 
508   // Iterate all registers in the closure, replace them with registers in the
509   // destination domain.
510   for (unsigned Reg : C.edges()) {
511     MRI->setRegClass(Reg, getDstRC(MRI->getRegClass(Reg), Domain));
512     for (auto &MO : MRI->use_operands(Reg)) {
513       if (MO.isReg())
514         // Remove all subregister references as they are not valid in the
515         // destination domain.
516         MO.setSubReg(0);
517     }
518   }
519 
520   for (auto MI : ToErase)
521     MI->eraseFromParent();
522 }
523 
524 /// \returns true when \p Reg is used as part of an address calculation in \p
525 /// MI.
526 static bool usedAsAddr(const MachineInstr &MI, unsigned Reg,
527                        const TargetInstrInfo *TII) {
528   if (!MI.mayLoadOrStore())
529     return false;
530 
531   const MCInstrDesc &Desc = TII->get(MI.getOpcode());
532   int MemOpStart = X86II::getMemoryOperandNo(Desc.TSFlags);
533   if (MemOpStart == -1)
534     return false;
535 
536   MemOpStart += X86II::getOperandBias(Desc);
537   for (unsigned MemOpIdx = MemOpStart,
538                 MemOpEnd = MemOpStart + X86::AddrNumOperands;
539        MemOpIdx < MemOpEnd; ++MemOpIdx) {
540     auto &Op = MI.getOperand(MemOpIdx);
541     if (Op.isReg() && Op.getReg() == Reg)
542       return true;
543   }
544   return false;
545 }
546 
547 void X86DomainReassignment::buildClosure(Closure &C, unsigned Reg) {
548   SmallVector<unsigned, 4> Worklist;
549   RegDomain Domain = NoDomain;
550   visitRegister(C, Reg, Domain, Worklist);
551   while (!Worklist.empty()) {
552     unsigned CurReg = Worklist.pop_back_val();
553 
554     // Register already in this closure.
555     if (!C.insertEdge(CurReg))
556       continue;
557     EnclosedEdges.insert(Reg);
558 
559     MachineInstr *DefMI = MRI->getVRegDef(CurReg);
560     encloseInstr(C, DefMI);
561 
562     // Add register used by the defining MI to the worklist.
563     // Do not add registers which are used in address calculation, they will be
564     // added to a different closure.
565     int OpEnd = DefMI->getNumOperands();
566     const MCInstrDesc &Desc = DefMI->getDesc();
567     int MemOp = X86II::getMemoryOperandNo(Desc.TSFlags);
568     if (MemOp != -1)
569       MemOp += X86II::getOperandBias(Desc);
570     for (int OpIdx = 0; OpIdx < OpEnd; ++OpIdx) {
571       if (OpIdx == MemOp) {
572         // skip address calculation.
573         OpIdx += (X86::AddrNumOperands - 1);
574         continue;
575       }
576       auto &Op = DefMI->getOperand(OpIdx);
577       if (!Op.isReg() || !Op.isUse())
578         continue;
579       visitRegister(C, Op.getReg(), Domain, Worklist);
580     }
581 
582     // Expand closure through register uses.
583     for (auto &UseMI : MRI->use_nodbg_instructions(CurReg)) {
584       // We would like to avoid converting closures which calculare addresses,
585       // as this should remain in GPRs.
586       if (usedAsAddr(UseMI, CurReg, TII)) {
587         C.setAllIllegal();
588         continue;
589       }
590       encloseInstr(C, &UseMI);
591 
592       for (auto &DefOp : UseMI.defs()) {
593         if (!DefOp.isReg())
594           continue;
595 
596         unsigned DefReg = DefOp.getReg();
597         if (!TargetRegisterInfo::isVirtualRegister(DefReg)) {
598           C.setAllIllegal();
599           continue;
600         }
601         visitRegister(C, DefReg, Domain, Worklist);
602       }
603     }
604   }
605 }
606 
607 void X86DomainReassignment::initConverters() {
608   Converters[{MaskDomain, TargetOpcode::PHI}] =
609       new InstrIgnore(TargetOpcode::PHI);
610 
611   Converters[{MaskDomain, TargetOpcode::IMPLICIT_DEF}] =
612       new InstrIgnore(TargetOpcode::IMPLICIT_DEF);
613 
614   Converters[{MaskDomain, TargetOpcode::INSERT_SUBREG}] =
615       new InstrReplaceWithCopy(TargetOpcode::INSERT_SUBREG, 2);
616 
617   Converters[{MaskDomain, TargetOpcode::COPY}] =
618       new InstrCOPYReplacer(TargetOpcode::COPY, MaskDomain, TargetOpcode::COPY);
619 
620   auto createReplacerDstCOPY = [&](unsigned From, unsigned To) {
621     Converters[{MaskDomain, From}] = new InstrReplacerDstCOPY(From, To);
622   };
623 
624   createReplacerDstCOPY(X86::MOVZX32rm16, X86::KMOVWkm);
625   createReplacerDstCOPY(X86::MOVZX64rm16, X86::KMOVWkm);
626 
627   createReplacerDstCOPY(X86::MOVZX32rr16, X86::KMOVWkk);
628   createReplacerDstCOPY(X86::MOVZX64rr16, X86::KMOVWkk);
629 
630   if (STI->hasDQI()) {
631     createReplacerDstCOPY(X86::MOVZX16rm8, X86::KMOVBkm);
632     createReplacerDstCOPY(X86::MOVZX32rm8, X86::KMOVBkm);
633     createReplacerDstCOPY(X86::MOVZX64rm8, X86::KMOVBkm);
634 
635     createReplacerDstCOPY(X86::MOVZX16rr8, X86::KMOVBkk);
636     createReplacerDstCOPY(X86::MOVZX32rr8, X86::KMOVBkk);
637     createReplacerDstCOPY(X86::MOVZX64rr8, X86::KMOVBkk);
638   }
639 
640   auto createReplacer = [&](unsigned From, unsigned To) {
641     Converters[{MaskDomain, From}] = new InstrReplacer(From, To);
642   };
643 
644   createReplacer(X86::MOV16rm, X86::KMOVWkm);
645   createReplacer(X86::MOV16mr, X86::KMOVWmk);
646   createReplacer(X86::MOV16rr, X86::KMOVWkk);
647   createReplacer(X86::SHR16ri, X86::KSHIFTRWri);
648   createReplacer(X86::SHL16ri, X86::KSHIFTLWri);
649   createReplacer(X86::NOT16r, X86::KNOTWrr);
650   createReplacer(X86::OR16rr, X86::KORWrr);
651   createReplacer(X86::AND16rr, X86::KANDWrr);
652   createReplacer(X86::XOR16rr, X86::KXORWrr);
653 
654   if (STI->hasBWI()) {
655     createReplacer(X86::MOV32rm, X86::KMOVDkm);
656     createReplacer(X86::MOV64rm, X86::KMOVQkm);
657 
658     createReplacer(X86::MOV32mr, X86::KMOVDmk);
659     createReplacer(X86::MOV64mr, X86::KMOVQmk);
660 
661     createReplacer(X86::MOV32rr, X86::KMOVDkk);
662     createReplacer(X86::MOV64rr, X86::KMOVQkk);
663 
664     createReplacer(X86::SHR32ri, X86::KSHIFTRDri);
665     createReplacer(X86::SHR64ri, X86::KSHIFTRQri);
666 
667     createReplacer(X86::SHL32ri, X86::KSHIFTLDri);
668     createReplacer(X86::SHL64ri, X86::KSHIFTLQri);
669 
670     createReplacer(X86::ADD32rr, X86::KADDDrr);
671     createReplacer(X86::ADD64rr, X86::KADDQrr);
672 
673     createReplacer(X86::NOT32r, X86::KNOTDrr);
674     createReplacer(X86::NOT64r, X86::KNOTQrr);
675 
676     createReplacer(X86::OR32rr, X86::KORDrr);
677     createReplacer(X86::OR64rr, X86::KORQrr);
678 
679     createReplacer(X86::AND32rr, X86::KANDDrr);
680     createReplacer(X86::AND64rr, X86::KANDQrr);
681 
682     createReplacer(X86::ANDN32rr, X86::KANDNDrr);
683     createReplacer(X86::ANDN64rr, X86::KANDNQrr);
684 
685     createReplacer(X86::XOR32rr, X86::KXORDrr);
686     createReplacer(X86::XOR64rr, X86::KXORQrr);
687 
688     // TODO: KTEST is not a replacement for TEST due to flag differences. Need
689     // to prove only Z flag is used.
690     //createReplacer(X86::TEST32rr, X86::KTESTDrr);
691     //createReplacer(X86::TEST64rr, X86::KTESTQrr);
692   }
693 
694   if (STI->hasDQI()) {
695     createReplacer(X86::ADD8rr, X86::KADDBrr);
696     createReplacer(X86::ADD16rr, X86::KADDWrr);
697 
698     createReplacer(X86::AND8rr, X86::KANDBrr);
699 
700     createReplacer(X86::MOV8rm, X86::KMOVBkm);
701     createReplacer(X86::MOV8mr, X86::KMOVBmk);
702     createReplacer(X86::MOV8rr, X86::KMOVBkk);
703 
704     createReplacer(X86::NOT8r, X86::KNOTBrr);
705 
706     createReplacer(X86::OR8rr, X86::KORBrr);
707 
708     createReplacer(X86::SHR8ri, X86::KSHIFTRBri);
709     createReplacer(X86::SHL8ri, X86::KSHIFTLBri);
710 
711     // TODO: KTEST is not a replacement for TEST due to flag differences. Need
712     // to prove only Z flag is used.
713     //createReplacer(X86::TEST8rr, X86::KTESTBrr);
714     //createReplacer(X86::TEST16rr, X86::KTESTWrr);
715 
716     createReplacer(X86::XOR8rr, X86::KXORBrr);
717   }
718 }
719 
720 bool X86DomainReassignment::runOnMachineFunction(MachineFunction &MF) {
721   if (skipFunction(MF.getFunction()))
722     return false;
723   if (DisableX86DomainReassignment)
724     return false;
725 
726   LLVM_DEBUG(
727       dbgs() << "***** Machine Function before Domain Reassignment *****\n");
728   LLVM_DEBUG(MF.print(dbgs()));
729 
730   STI = &MF.getSubtarget<X86Subtarget>();
731   // GPR->K is the only transformation currently supported, bail out early if no
732   // AVX512.
733   // TODO: We're also bailing of AVX512BW isn't supported since we use VK32 and
734   // VK64 for GR32/GR64, but those aren't legal classes on KNL. If the register
735   // coalescer doesn't clean it up and we generate a spill we will crash.
736   if (!STI->hasAVX512() || !STI->hasBWI())
737     return false;
738 
739   MRI = &MF.getRegInfo();
740   assert(MRI->isSSA() && "Expected MIR to be in SSA form");
741 
742   TII = STI->getInstrInfo();
743   initConverters();
744   bool Changed = false;
745 
746   EnclosedEdges.clear();
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) {
754     unsigned Reg = TargetRegisterInfo::index2VirtReg(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.count(Reg))
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   DeleteContainerSeconds(Converters);
783 
784   LLVM_DEBUG(
785       dbgs() << "***** Machine Function after Domain Reassignment *****\n");
786   LLVM_DEBUG(MF.print(dbgs()));
787 
788   return Changed;
789 }
790 
791 INITIALIZE_PASS(X86DomainReassignment, "x86-domain-reassignment",
792                 "X86 Domain Reassignment Pass", false, false)
793 
794 /// Returns an instance of the Domain Reassignment pass.
795 FunctionPass *llvm::createX86DomainReassignmentPass() {
796   return new X86DomainReassignment();
797 }
798