contrib/llvm/lib/Target/X86/X86DomainReassignment.cpp

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