contrib/llvm/lib/CodeGen/DetectDeadLanes.cpp

   1 //===- DetectDeadLanes.cpp - SubRegister Lane Usage Analysis --*- C++ -*---===//
   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 /// \file
  11 /// Analysis that tracks defined/used subregister lanes across COPY instructions
  12 /// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE,
  13 /// INSERT_SUBREG, EXTRACT_SUBREG).
  14 /// The information is used to detect dead definitions and the usage of
  15 /// (completely) undefined values and mark the operands as such.
  16 /// This pass is necessary because the dead/undef status is not obvious anymore
  17 /// when subregisters are involved.
  18 ///
  19 /// Example:
  20 ///    %vreg0 = some definition
  21 ///    %vreg1 = IMPLICIT_DEF
  22 ///    %vreg2 = REG_SEQUENCE %vreg0, sub0, %vreg1, sub1
  23 ///    %vreg3 = EXTRACT_SUBREG %vreg2, sub1
  24 ///           = use %vreg3
  25 /// The %vreg0 definition is dead and %vreg3 contains an undefined value.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include <deque>
  30 #include <vector>
  31
  32 #include "llvm/ADT/BitVector.h"
  33 #include "llvm/ADT/SetVector.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/InitializePasses.h"
  38 #include "llvm/Pass.h"
  39 #include "llvm/PassRegistry.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/raw_ostream.h"
  42 #include "llvm/Target/TargetInstrInfo.h"
  43 #include "llvm/Target/TargetRegisterInfo.h"
  44 #include "llvm/Target/TargetSubtargetInfo.h"
  45
  46 using namespace llvm;
  47
  48 #define DEBUG_TYPE "detect-dead-lanes"
  49
  50 namespace {
  51
  52 /// Contains a bitmask of which lanes of a given virtual register are
  53 /// defined and which ones are actually used.
  54 struct VRegInfo {
  55   LaneBitmask UsedLanes;
  56   LaneBitmask DefinedLanes;
  57 };
  58
  59 class DetectDeadLanes : public MachineFunctionPass {
  60 public:
  61   bool runOnMachineFunction(MachineFunction &MF) override;
  62
  63   static char ID;
  64   DetectDeadLanes() : MachineFunctionPass(ID) {}
  65
  66   StringRef getPassName() const override { return "Detect Dead Lanes"; }
  67
  68   void getAnalysisUsage(AnalysisUsage &AU) const override {
  69     AU.setPreservesCFG();
  70     MachineFunctionPass::getAnalysisUsage(AU);
  71   }
  72
  73 private:
  74   /// Add used lane bits on the register used by operand \p MO. This translates
  75   /// the bitmask based on the operands subregister, and puts the register into
  76   /// the worklist if any new bits were added.
  77   void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
  78
  79   /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
  80   /// COPY-like instruction determine the lanes used on the use operands
  81   /// and call addUsedLanesOnOperand() for them.
  82   void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes);
  83
  84   /// Given a use regiser operand \p Use and a mask of defined lanes, check
  85   /// if the operand belongs to a lowersToCopies() instruction, transfer the
  86   /// mask to the def and put the instruction into the worklist.
  87   void transferDefinedLanesStep(const MachineOperand &Use,
  88                                 LaneBitmask DefinedLanes);
  89
  90   /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
  91   /// of COPY-like instruction, determine which lanes are defined at the output
  92   /// operand \p Def.
  93   LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
  94                                    LaneBitmask DefinedLanes) const;
  95
  96   /// Given a mask \p UsedLanes used from the output of instruction \p MI
  97   /// determine which lanes are used from operand \p MO of this instruction.
  98   LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes,
  99                                 const MachineOperand &MO) const;
 100
 101   bool runOnce(MachineFunction &MF);
 102
 103   LaneBitmask determineInitialDefinedLanes(unsigned Reg);
 104   LaneBitmask determineInitialUsedLanes(unsigned Reg);
 105
 106   bool isUndefRegAtInput(const MachineOperand &MO,
 107                          const VRegInfo &RegInfo) const;
 108
 109   bool isUndefInput(const MachineOperand &MO, bool *CrossCopy) const;
 110
 111   const MachineRegisterInfo *MRI;
 112   const TargetRegisterInfo *TRI;
 113
 114   void PutInWorklist(unsigned RegIdx) {
 115     if (WorklistMembers.test(RegIdx))
 116       return;
 117     WorklistMembers.set(RegIdx);
 118     Worklist.push_back(RegIdx);
 119   }
 120
 121   VRegInfo *VRegInfos;
 122   /// Worklist containing virtreg indexes.
 123   std::deque<unsigned> Worklist;
 124   BitVector WorklistMembers;
 125   /// This bitvector is set for each vreg index where the vreg is defined
 126   /// by an instruction where lowersToCopies()==true.
 127   BitVector DefinedByCopy;
 128 };
 129
 130 } // end anonymous namespace
 131
 132 char DetectDeadLanes::ID = 0;
 133 char &llvm::DetectDeadLanesID = DetectDeadLanes::ID;
 134
 135 INITIALIZE_PASS(DetectDeadLanes, "detect-dead-lanes", "Detect Dead Lanes",
 136                 false, false)
 137
 138 /// Returns true if \p MI will get lowered to a series of COPY instructions.
 139 /// We call this a COPY-like instruction.
 140 static bool lowersToCopies(const MachineInstr &MI) {
 141   // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
 142   // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
 143   // are not lowered to a COPY.
 144   switch (MI.getOpcode()) {
 145   case TargetOpcode::COPY:
 146   case TargetOpcode::PHI:
 147   case TargetOpcode::INSERT_SUBREG:
 148   case TargetOpcode::REG_SEQUENCE:
 149   case TargetOpcode::EXTRACT_SUBREG:
 150     return true;
 151   }
 152   return false;
 153 }
 154
 155 static bool isCrossCopy(const MachineRegisterInfo &MRI,
 156                         const MachineInstr &MI,
 157                         const TargetRegisterClass *DstRC,
 158                         const MachineOperand &MO) {
 159   assert(lowersToCopies(MI));
 160   unsigned SrcReg = MO.getReg();
 161   const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
 162   if (DstRC == SrcRC)
 163     return false;
 164
 165   unsigned SrcSubIdx = MO.getSubReg();
 166
 167   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 168   unsigned DstSubIdx = 0;
 169   switch (MI.getOpcode()) {
 170   case TargetOpcode::INSERT_SUBREG:
 171     if (MI.getOperandNo(&MO) == 2)
 172       DstSubIdx = MI.getOperand(3).getImm();
 173     break;
 174   case TargetOpcode::REG_SEQUENCE: {
 175     unsigned OpNum = MI.getOperandNo(&MO);
 176     DstSubIdx = MI.getOperand(OpNum+1).getImm();
 177     break;
 178   }
 179   case TargetOpcode::EXTRACT_SUBREG: {
 180     unsigned SubReg = MI.getOperand(2).getImm();
 181     SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
 182   }
 183   }
 184
 185   unsigned PreA, PreB; // Unused.
 186   if (SrcSubIdx && DstSubIdx)
 187     return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
 188                                        PreB);
 189   if (SrcSubIdx)
 190     return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
 191   if (DstSubIdx)
 192     return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
 193   return !TRI.getCommonSubClass(SrcRC, DstRC);
 194 }
 195
 196 void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
 197                                             LaneBitmask UsedLanes) {
 198   if (!MO.readsReg())
 199     return;
 200   unsigned MOReg = MO.getReg();
 201   if (!TargetRegisterInfo::isVirtualRegister(MOReg))
 202     return;
 203
 204   unsigned MOSubReg = MO.getSubReg();
 205   if (MOSubReg != 0)
 206     UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
 207   UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
 208
 209   unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
 210   VRegInfo &MORegInfo = VRegInfos[MORegIdx];
 211   LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
 212   // Any change at all?
 213   if ((UsedLanes & ~PrevUsedLanes).none())
 214     return;
 215
 216   // Set UsedLanes and remember instruction for further propagation.
 217   MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
 218   if (DefinedByCopy.test(MORegIdx))
 219     PutInWorklist(MORegIdx);
 220 }
 221
 222 void DetectDeadLanes::transferUsedLanesStep(const MachineInstr &MI,
 223                                             LaneBitmask UsedLanes) {
 224   for (const MachineOperand &MO : MI.uses()) {
 225     if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 226       continue;
 227     LaneBitmask UsedOnMO = transferUsedLanes(MI, UsedLanes, MO);
 228     addUsedLanesOnOperand(MO, UsedOnMO);
 229   }
 230 }
 231
 232 LaneBitmask DetectDeadLanes::transferUsedLanes(const MachineInstr &MI,
 233                                                LaneBitmask UsedLanes,
 234                                                const MachineOperand &MO) const {
 235   unsigned OpNum = MI.getOperandNo(&MO);
 236   assert(lowersToCopies(MI) && DefinedByCopy[
 237            TargetRegisterInfo::virtReg2Index(MI.getOperand(0).getReg())]);
 238
 239   switch (MI.getOpcode()) {
 240   case TargetOpcode::COPY:
 241   case TargetOpcode::PHI:
 242     return UsedLanes;
 243   case TargetOpcode::REG_SEQUENCE: {
 244     assert(OpNum % 2 == 1);
 245     unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
 246     return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
 247   }
 248   case TargetOpcode::INSERT_SUBREG: {
 249     unsigned SubIdx = MI.getOperand(3).getImm();
 250     LaneBitmask MO2UsedLanes =
 251         TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
 252     if (OpNum == 2)
 253       return MO2UsedLanes;
 254
 255     const MachineOperand &Def = MI.getOperand(0);
 256     unsigned DefReg = Def.getReg();
 257     const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
 258     LaneBitmask MO1UsedLanes;
 259     if (RC->CoveredBySubRegs)
 260       MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
 261     else
 262       MO1UsedLanes = RC->LaneMask;
 263
 264     assert(OpNum == 1);
 265     return MO1UsedLanes;
 266   }
 267   case TargetOpcode::EXTRACT_SUBREG: {
 268     assert(OpNum == 1);
 269     unsigned SubIdx = MI.getOperand(2).getImm();
 270     return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
 271   }
 272   default:
 273     llvm_unreachable("function must be called with COPY-like instruction");
 274   }
 275 }
 276
 277 void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
 278                                                LaneBitmask DefinedLanes) {
 279   if (!Use.readsReg())
 280     return;
 281   // Check whether the operand writes a vreg and is part of a COPY-like
 282   // instruction.
 283   const MachineInstr &MI = *Use.getParent();
 284   if (MI.getDesc().getNumDefs() != 1)
 285     return;
 286   // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
 287   // they really need to be modeled differently!
 288   if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
 289     return;
 290   const MachineOperand &Def = *MI.defs().begin();
 291   unsigned DefReg = Def.getReg();
 292   if (!TargetRegisterInfo::isVirtualRegister(DefReg))
 293     return;
 294   unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
 295   if (!DefinedByCopy.test(DefRegIdx))
 296     return;
 297
 298   unsigned OpNum = MI.getOperandNo(&Use);
 299   DefinedLanes =
 300       TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
 301   DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
 302
 303   VRegInfo &RegInfo = VRegInfos[DefRegIdx];
 304   LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
 305   // Any change at all?
 306   if ((DefinedLanes & ~PrevDefinedLanes).none())
 307     return;
 308
 309   RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
 310   PutInWorklist(DefRegIdx);
 311 }
 312
 313 LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
 314     unsigned OpNum, LaneBitmask DefinedLanes) const {
 315   const MachineInstr &MI = *Def.getParent();
 316   // Translate DefinedLanes if necessary.
 317   switch (MI.getOpcode()) {
 318   case TargetOpcode::REG_SEQUENCE: {
 319     unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
 320     DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
 321     DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
 322     break;
 323   }
 324   case TargetOpcode::INSERT_SUBREG: {
 325     unsigned SubIdx = MI.getOperand(3).getImm();
 326     if (OpNum == 2) {
 327       DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
 328       DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
 329     } else {
 330       assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
 331       // Ignore lanes defined by operand 2.
 332       DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
 333     }
 334     break;
 335   }
 336   case TargetOpcode::EXTRACT_SUBREG: {
 337     unsigned SubIdx = MI.getOperand(2).getImm();
 338     assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
 339     DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
 340     break;
 341   }
 342   case TargetOpcode::COPY:
 343   case TargetOpcode::PHI:
 344     break;
 345   default:
 346     llvm_unreachable("function must be called with COPY-like instruction");
 347   }
 348
 349   assert(Def.getSubReg() == 0 &&
 350          "Should not have subregister defs in machine SSA phase");
 351   DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
 352   return DefinedLanes;
 353 }
 354
 355 LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
 356   // Live-In or unused registers have no definition but are considered fully
 357   // defined.
 358   if (!MRI->hasOneDef(Reg))
 359     return LaneBitmask::getAll();
 360
 361   const MachineOperand &Def = *MRI->def_begin(Reg);
 362   const MachineInstr &DefMI = *Def.getParent();
 363   if (lowersToCopies(DefMI)) {
 364     // Start optimisatically with no used or defined lanes for copy
 365     // instructions. The following dataflow analysis will add more bits.
 366     unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
 367     DefinedByCopy.set(RegIdx);
 368     PutInWorklist(RegIdx);
 369
 370     if (Def.isDead())
 371       return LaneBitmask::getNone();
 372
 373     // COPY/PHI can copy across unrelated register classes (example: float/int)
 374     // with incompatible subregister structure. Do not include these in the
 375     // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
 376     const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
 377
 378     // Determine initially DefinedLanes.
 379     LaneBitmask DefinedLanes;
 380     for (const MachineOperand &MO : DefMI.uses()) {
 381       if (!MO.isReg() || !MO.readsReg())
 382         continue;
 383       unsigned MOReg = MO.getReg();
 384       if (!MOReg)
 385         continue;
 386
 387       LaneBitmask MODefinedLanes;
 388       if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
 389         MODefinedLanes = LaneBitmask::getAll();
 390       } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
 391         MODefinedLanes = LaneBitmask::getAll();
 392       } else {
 393         assert(TargetRegisterInfo::isVirtualRegister(MOReg));
 394         if (MRI->hasOneDef(MOReg)) {
 395           const MachineOperand &MODef = *MRI->def_begin(MOReg);
 396           const MachineInstr &MODefMI = *MODef.getParent();
 397           // Bits from copy-like operations will be added later.
 398           if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())
 399             continue;
 400         }
 401         unsigned MOSubReg = MO.getSubReg();
 402         MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
 403         MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
 404             MOSubReg, MODefinedLanes);
 405       }
 406
 407       unsigned OpNum = DefMI.getOperandNo(&MO);
 408       DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
 409     }
 410     return DefinedLanes;
 411   }
 412   if (DefMI.isImplicitDef() || Def.isDead())
 413     return LaneBitmask::getNone();
 414
 415   assert(Def.getSubReg() == 0 &&
 416          "Should not have subregister defs in machine SSA phase");
 417   return MRI->getMaxLaneMaskForVReg(Reg);
 418 }
 419
 420 LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
 421   LaneBitmask UsedLanes = LaneBitmask::getNone();
 422   for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
 423     if (!MO.readsReg())
 424       continue;
 425
 426     const MachineInstr &UseMI = *MO.getParent();
 427     if (UseMI.isKill())
 428       continue;
 429
 430     unsigned SubReg = MO.getSubReg();
 431     if (lowersToCopies(UseMI)) {
 432       assert(UseMI.getDesc().getNumDefs() == 1);
 433       const MachineOperand &Def = *UseMI.defs().begin();
 434       unsigned DefReg = Def.getReg();
 435       // The used lanes of COPY-like instruction operands are determined by the
 436       // following dataflow analysis.
 437       if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
 438         // But ignore copies across incompatible register classes.
 439         bool CrossCopy = false;
 440         if (lowersToCopies(UseMI)) {
 441           const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
 442           CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
 443           if (CrossCopy)
 444             DEBUG(dbgs() << "Copy accross incompatible classes: " << UseMI);
 445         }
 446
 447         if (!CrossCopy)
 448           continue;
 449       }
 450     }
 451
 452     // Shortcut: All lanes are used.
 453     if (SubReg == 0)
 454       return MRI->getMaxLaneMaskForVReg(Reg);
 455
 456     UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
 457   }
 458   return UsedLanes;
 459 }
 460
 461 bool DetectDeadLanes::isUndefRegAtInput(const MachineOperand &MO,
 462                                         const VRegInfo &RegInfo) const {
 463   unsigned SubReg = MO.getSubReg();
 464   LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
 465   return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();
 466 }
 467
 468 bool DetectDeadLanes::isUndefInput(const MachineOperand &MO,
 469                                    bool *CrossCopy) const {
 470   if (!MO.isUse())
 471     return false;
 472   const MachineInstr &MI = *MO.getParent();
 473   if (!lowersToCopies(MI))
 474     return false;
 475   const MachineOperand &Def = MI.getOperand(0);
 476   unsigned DefReg = Def.getReg();
 477   if (!TargetRegisterInfo::isVirtualRegister(DefReg))
 478     return false;
 479   unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
 480   if (!DefinedByCopy.test(DefRegIdx))
 481     return false;
 482
 483   const VRegInfo &DefRegInfo = VRegInfos[DefRegIdx];
 484   LaneBitmask UsedLanes = transferUsedLanes(MI, DefRegInfo.UsedLanes, MO);
 485   if (UsedLanes.any())
 486     return false;
 487
 488   unsigned MOReg = MO.getReg();
 489   if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
 490     const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
 491     *CrossCopy = isCrossCopy(*MRI, MI, DstRC, MO);
 492   }
 493   return true;
 494 }
 495
 496 bool DetectDeadLanes::runOnce(MachineFunction &MF) {
 497   // First pass: Populate defs/uses of vregs with initial values
 498   unsigned NumVirtRegs = MRI->getNumVirtRegs();
 499   for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
 500     unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
 501
 502     // Determine used/defined lanes and add copy instructions to worklist.
 503     VRegInfo &Info = VRegInfos[RegIdx];
 504     Info.DefinedLanes = determineInitialDefinedLanes(Reg);
 505     Info.UsedLanes = determineInitialUsedLanes(Reg);
 506   }
 507
 508   // Iterate as long as defined lanes/used lanes keep changing.
 509   while (!Worklist.empty()) {
 510     unsigned RegIdx = Worklist.front();
 511     Worklist.pop_front();
 512     WorklistMembers.reset(RegIdx);
 513     VRegInfo &Info = VRegInfos[RegIdx];
 514     unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
 515
 516     // Transfer UsedLanes to operands of DefMI (backwards dataflow).
 517     MachineOperand &Def = *MRI->def_begin(Reg);
 518     const MachineInstr &MI = *Def.getParent();
 519     transferUsedLanesStep(MI, Info.UsedLanes);
 520     // Transfer DefinedLanes to users of Reg (forward dataflow).
 521     for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
 522       transferDefinedLanesStep(MO, Info.DefinedLanes);
 523   }
 524
 525   DEBUG(
 526     dbgs() << "Defined/Used lanes:\n";
 527     for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {
 528       unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
 529       const VRegInfo &Info = VRegInfos[RegIdx];
 530       dbgs() << PrintReg(Reg, nullptr)
 531              << " Used: " << PrintLaneMask(Info.UsedLanes)
 532              << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
 533     }
 534     dbgs() << "\n";
 535   );
 536
 537   bool Again = false;
 538   // Mark operands as dead/unused.
 539   for (MachineBasicBlock &MBB : MF) {
 540     for (MachineInstr &MI : MBB) {
 541       for (MachineOperand &MO : MI.operands()) {
 542         if (!MO.isReg())
 543           continue;
 544         unsigned Reg = MO.getReg();
 545         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 546           continue;
 547         unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
 548         const VRegInfo &RegInfo = VRegInfos[RegIdx];
 549         if (MO.isDef() && !MO.isDead() && RegInfo.UsedLanes.none()) {
 550           DEBUG(dbgs() << "Marking operand '" << MO << "' as dead in " << MI);
 551           MO.setIsDead();
 552         }
 553         if (MO.readsReg()) {
 554           bool CrossCopy = false;
 555           if (isUndefRegAtInput(MO, RegInfo)) {
 556             DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
 557                   << MI);
 558             MO.setIsUndef();
 559           } else if (isUndefInput(MO, &CrossCopy)) {
 560             DEBUG(dbgs() << "Marking operand '" << MO << "' as undef in "
 561                   << MI);
 562             MO.setIsUndef();
 563             if (CrossCopy)
 564               Again = true;
 565           }
 566         }
 567       }
 568     }
 569   }
 570
 571   return Again;
 572 }
 573
 574 bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
 575   // Don't bother if we won't track subregister liveness later.  This pass is
 576   // required for correctness if subregister liveness is enabled because the
 577   // register coalescer cannot deal with hidden dead defs. However without
 578   // subregister liveness enabled, the expected benefits of this pass are small
 579   // so we safe the compile time.
 580   MRI = &MF.getRegInfo();
 581   if (!MRI->subRegLivenessEnabled()) {
 582     DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
 583     return false;
 584   }
 585
 586   TRI = MRI->getTargetRegisterInfo();
 587
 588   unsigned NumVirtRegs = MRI->getNumVirtRegs();
 589   VRegInfos = new VRegInfo[NumVirtRegs];
 590   WorklistMembers.resize(NumVirtRegs);
 591   DefinedByCopy.resize(NumVirtRegs);
 592
 593   bool Again;
 594   do {
 595     Again = runOnce(MF);
 596   } while(Again);
 597
 598   DefinedByCopy.clear();
 599   WorklistMembers.clear();
 600   delete[] VRegInfos;
 601   return true;
 602 }