ScheduleDAGInstrs: Rework schedule graph builder.

[MatzeB]

Summary

The new algorithm remembers the uses encountered while walking backwards
until a matching def is found. Contrary to the previous version this:

• Works without LiveIntervals being available
• Allows to increase the precision to subregisters/lanemasks (not used for now)

The changes in the AMDGPU tests are necessary because the R600 scheduler
is not stable with respect to the order of nodes in the ready queues.

[qcolombet]

Hi Matthias,

The change looks mostly good to me.
There is one FIXME though, that I believe should be fixed before pushing.

Thanks,
-Quentin

include/llvm/CodeGen/ScheduleDAGInstrs.h

100

Should we mention the sub-register here?
I am wondering if it is clear for everybody that lane masks come from sub-registers.

lib/CodeGen/ScheduleDAGInstrs.cpp

371

I guess the constant used here is not very important since we consistently have the same for every virtual registers.
That being said, it feels more natural to use ~0U, to emphasize we set the whole register, however I reckon we would set too many “lane mask” bits.
What do you think?

376

Ditto.

402

Didn’t we come to the conclusion that the other lanes may be undef for this use but still live?
I.e., the kill mask is redundant with the def mask.

417

When do you plan to fix this?
I am guessing there is not much point in pushing the patch forward without that fixed.

[atrick]

LGTM. Thanks.

include/llvm/CodeGen/MachineScheduler.h

 };
 
 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
 /// schedules machine instructions according to the given MachineSchedStrategy
 /// without much extra book-keeping. This is the common functionality between
 /// PreRA and PostRA MachineScheduler.
 class ScheduleDAGMI : public ScheduleDAGInstrs {
 protected:
+  LiveIntervals *LIS;
   AliasAnalysis *AA;
   std::unique_ptr<MachineSchedStrategy> SchedImpl;
 
   /// Topo - A topological ordering for SUnits which permits fast IsReachable
   /// and similar queries.
   ScheduleDAGTopologicalSort Topo;
 
   /// Ordered list of DAG postprocessing steps.
#ifndef NDEBUG
   /// The number of instructions scheduled so far. Used to cut off the
   /// scheduler at the point determined by misched-cutoff.
   unsigned NumInstrsScheduled;
 #endif
 public:
   ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
                 bool IsPostRA)
       : ScheduleDAGInstrs(*C->MF, C->MLI, IsPostRA,
-                          /*RemoveKillFlags=*/IsPostRA, C->LIS),
-        AA(C->AA), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU), CurrentTop(),
-        CurrentBottom(), NextClusterPred(nullptr), NextClusterSucc(nullptr) {
+                          /*RemoveKillFlags=*/IsPostRA),
+        LIS(C->LIS), AA(C->AA), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU),
+        CurrentTop(), CurrentBottom(), NextClusterPred(nullptr),
+        NextClusterSucc(nullptr) {
 #ifndef NDEBUG
     NumInstrsScheduled = 0;
 #endif
   }
 
   // Provide a vtable anchor
   ~ScheduleDAGMI() override;
 
#endif
 
   const SUnit *getNextClusterPred() const { return NextClusterPred; }
 
   const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
 
   void viewGraph(const Twine &Name, const Twine &Title) override;
   void viewGraph() override;
 
+  LiveIntervals *getLIS() const { return LIS; }
+
 protected:
   // Top-Level entry points for the schedule() driver...
 
   /// Apply each ScheduleDAGMutation step in order. This allows different
   /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
   void postprocessDAG();
 
   /// Release ExitSU predecessors and setup scheduler queues.

include/llvm/CodeGen/ScheduleDAGInstrs.h

 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 
 namespace llvm {
   class MachineFrameInfo;
   class MachineLoopInfo;
   class MachineDominatorTree;
-  class LiveIntervals;
   class RegPressureTracker;
   class PressureDiffs;
 
   /// An individual mapping from virtual register number to SUnit.
   struct VReg2SUnit {
     unsigned VirtReg;
+    unsigned LaneMask;
     SUnit *SU;
 
-    VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {}
+    VReg2SUnit(unsigned VReg, unsigned LaneMask, SUnit *SU)
+      : VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
 
     unsigned getSparseSetIndex() const {
       return TargetRegisterInfo::virtReg2Index(VirtReg);
     }
   };
 
   /// Record a physical register access.
   /// For non-data-dependent uses, OpIdx == -1.
namespace llvm {
   /// compares ValueT's, only unsigned keys. This allows the set to be cleared
   /// between scheduling regions in constant time as long as ValueT does not
   /// require a destructor.
   typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap;
 
   /// Track local uses of virtual registers. These uses are gathered by the DAG
   /// builder and may be consulted by the scheduler to avoid iterating an entire
   /// vreg use list.
-  typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2UseMap;
+  typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMultiMap;
 
   /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
   /// MachineInstrs.
   class ScheduleDAGInstrs : public ScheduleDAG {
   protected:
     const MachineLoopInfo *MLI;
     const MachineFrameInfo *MFI;
 
-    /// Live Intervals provides reaching defs in preRA scheduling.
-    LiveIntervals *LIS;
-
     /// TargetSchedModel provides an interface to the machine model.
     TargetSchedModel SchedModel;
 
     /// isPostRA flag indicates vregs cannot be present.
     bool IsPostRA;
 
     /// True if the DAG builder should remove kill flags (in preparation for
     /// rescheduling).
     bool RemoveKillFlags;
 
     /// The standard DAG builder does not normally include terminators as DAG
     /// nodes because it does not create the necessary dependencies to prevent
     /// reordering. A specialized scheduler can override
     /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
     /// it has taken responsibility for scheduling the terminator correctly.
     bool CanHandleTerminators;
 
+    /// Whether lane masks should get tracked.
+    bool TrackLaneMasks;
+
     /// State specific to the current scheduling region.
     /// ------------------------------------------------
 
     /// The block in which to insert instructions
     MachineBasicBlock *BB;
 
     /// The beginning of the range to be scheduled.
     MachineBasicBlock::iterator RegionBegin;
 
     /// The end of the range to be scheduled.
     MachineBasicBlock::iterator RegionEnd;
 
     /// Instructions in this region (distance(RegionBegin, RegionEnd)).
     unsigned NumRegionInstrs;
 
     /// After calling BuildSchedGraph, each machine instruction in the current
     /// scheduling region is mapped to an SUnit.
     DenseMap<MachineInstr*, SUnit*> MISUnitMap;
 
     /// After calling BuildSchedGraph, each vreg used in the scheduling region
     /// is mapped to a set of SUnits. These include all local vreg uses, not
     /// just the uses for a singly defined vreg.
-    VReg2UseMap VRegUses;
+    VReg2SUnitMultiMap VRegUses;
 
     /// State internal to DAG building.
     /// -------------------------------
 
     /// Defs, Uses - Remember where defs and uses of each register are as we
     /// iterate upward through the instructions. This is allocated here instead
     /// of inside BuildSchedGraph to avoid the need for it to be initialized and
     /// destructed for each block.
     Reg2SUnitsMap Defs;
     Reg2SUnitsMap Uses;
 
-    /// Track the last instruction in this region defining each virtual register.
-    VReg2SUnitMap VRegDefs;
+    /// Track the last instruction(s) in this region defining each virtual
+    /// register. There may be multiple current definitions for a register with
+    /// disjunct lanemasks.
+    VReg2SUnitMultiMap CurrentVRegDefs;
+    /// Track the last instructions in this region using each virtual register.
+    VReg2SUnitMultiMap CurrentVRegUses;
 
     /// PendingLoads - Remember where unknown loads are after the most recent
     /// unknown store, as we iterate. As with Defs and Uses, this is here
     /// to minimize construction/destruction.
     std::vector<SUnit *> PendingLoads;
 
     /// DbgValues - Remember instruction that precedes DBG_VALUE.
     /// These are generated by buildSchedGraph but persist so they can be
     /// referenced when emitting the final schedule.
     typedef std::vector<std::pair<MachineInstr *, MachineInstr *> >
       DbgValueVector;
     DbgValueVector DbgValues;
     MachineInstr *FirstDbgValue;
 
     /// Set of live physical registers for updating kill flags.
     BitVector LiveRegs;
 
   public:
     explicit ScheduleDAGInstrs(MachineFunction &mf,
                                const MachineLoopInfo *mli,
                                bool IsPostRAFlag,
-                               bool RemoveKillFlags = false,
-                               LiveIntervals *LIS = nullptr);
+                               bool RemoveKillFlags = false);
 
     ~ScheduleDAGInstrs() override {}
 
     bool isPostRA() const { return IsPostRA; }
 
-    /// \brief Expose LiveIntervals for use in DAG mutators and such.
-    LiveIntervals *getLIS() const { return LIS; }
-
     /// \brief Get the machine model for instruction scheduling.
     const TargetSchedModel *getSchedModel() const { return &SchedModel; }
 
     /// \brief Resolve and cache a resolved scheduling class for an SUnit.
     const MCSchedClassDesc *getSchedClass(SUnit *SU) const {
       if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
         SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
       return SU->SchedClass;
protected:
     /// \brief PostRA helper for rewriting kill flags.
     void startBlockForKills(MachineBasicBlock *BB);
 
     /// \brief Toggle a register operand kill flag.
     ///
     /// Other adjustments may be made to the instruction if necessary. Return
     /// true if the operand has been deleted, false if not.
     bool toggleKillFlag(MachineInstr *MI, MachineOperand &MO);
+
+    /// Return a mask for which lanes get read/written by the given (register)
+    /// machine operand.
+    unsigned getLaneMaskForMO(const MachineOperand &MO) const;
   };
 
   /// newSUnit - Creates a new SUnit and return a ptr to it.
   inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
 #ifndef NDEBUG
     const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
 #endif
     SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));

lib/CodeGen/MachineScheduler.cpp

for (unsigned LUIdx = 0, LUEnd = LiveUses.size(); LUIdx != LUEnd; ++LUIdx) {
     if (I == BB->end())
       VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
     else {
       LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(I));
       VNI = LRQ.valueIn();
     }
     // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
     assert(VNI && "No live value at use.");
-    for (VReg2UseMap::iterator
+    for (VReg2SUnitMultiMap::iterator
            UI = VRegUses.find(Reg); UI != VRegUses.end(); ++UI) {
       SUnit *SU = UI->SU;
       DEBUG(dbgs() << "  UpdateRegP: SU(" << SU->NodeNum << ") "
             << *SU->getInstr());
       // If this use comes before the reaching def, it cannot be a last use, so
       // descrease its pressure change.
       if (!SU->isScheduled && SU != &ExitSU) {
         LiveQueryResult LRQ
for (ArrayRef<unsigned>::iterator RI = LiveOuts.begin(), RE = LiveOuts.end();
     MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def);
     const SUnit *DefSU = getSUnit(DefMI);
     if (!DefSU)
       continue;
 
     unsigned LiveOutHeight = DefSU->getHeight();
     unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;
     // Visit all local users of the vreg def.
-    for (VReg2UseMap::iterator
+    for (VReg2SUnitMultiMap::iterator
            UI = VRegUses.find(Reg); UI != VRegUses.end(); ++UI) {
       if (UI->SU == &ExitSU)
         continue;
 
       // Only consider uses of the phi.
       LiveQueryResult LRQ =
         LI.Query(LIS->getInstructionIndex(UI->SU->getInstr()));
       if (!LRQ.valueIn()->isPHIDef())

lib/CodeGen/ScheduleDAGInstrs.cpp

 //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This implements the ScheduleDAGInstrs class, which implements re-scheduling
 // of MachineInstrs.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
+#include "llvm/ADT/IntEqClasses.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
-#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/ScheduleDFS.h"
 #include "llvm/IR/Operator.h"
static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
     cl::ZeroOrMore, cl::init(false),
     cl::desc("Enable use of AA during MI DAG construction"));
 
 static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
     cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));
 
 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
                                      const MachineLoopInfo *mli,
-                                     bool IsPostRAFlag, bool RemoveKillFlags,
-                                     LiveIntervals *lis)
-    : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), LIS(lis),
+                                     bool IsPostRAFlag, bool RemoveKillFlags)
+    : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
       IsPostRA(IsPostRAFlag), RemoveKillFlags(RemoveKillFlags),
-      CanHandleTerminators(false), FirstDbgValue(nullptr) {
-  assert((IsPostRA || LIS) && "PreRA scheduling requires LiveIntervals");
+      CanHandleTerminators(false), TrackLaneMasks(false),
+      FirstDbgValue(nullptr) {
   DbgValues.clear();
   assert(!(IsPostRA && MRI.getNumVirtRegs()) &&
          "Virtual registers must be removed prior to PostRA scheduling");
 
   const TargetSubtargetInfo &ST = mf.getSubtarget();
   SchedModel.init(ST.getSchedModel(), &ST, TII);
 }
 
if (!MO.isDead()) {
       }
     }
 
     // Defs are pushed in the order they are visited and never reordered.
     Defs.insert(PhysRegSUOper(SU, OperIdx, Reg));
   }
 }
 
+unsigned ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const {
+  if (!TrackLaneMasks)
+    return 1;
+  unsigned Reg = MO.getReg();
+  // No point in tracking lanemasks if we don't have interesting subregisters.
+  const TargetRegisterClass &RC = *MRI.getRegClass(Reg);
+  if (!RC.HasDisjunctSubRegs)
+    return 1;
+
+  unsigned SubReg = MO.getSubReg();
+  if (SubReg == 0)
+    return MRI.getMaxLaneMaskForVReg(Reg);
+  return TRI->getSubRegIndexLaneMask(SubReg);
+}
+
 /// addVRegDefDeps - Add register output and data dependencies from this SUnit
 /// to instructions that occur later in the same scheduling region if they read
 /// from or write to the virtual register defined at OperIdx.
 ///
 /// TODO: Hoist loop induction variable increments. This has to be
 /// reevaluated. Generally, IV scheduling should be done before coalescing.
 void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
   const MachineInstr *MI = SU->getInstr();
-  unsigned Reg = MI->getOperand(OperIdx).getReg();
+  const MachineOperand &MO = MI->getOperand(OperIdx);
+  unsigned Reg = MO.getReg();
+  unsigned DefLaneMask = getLaneMaskForMO(MO);
+
+  if (MO.isDead()) {
+    assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() &&
+           "Dead defs should have no uses");
+  } else {
+    // If we have a <read-undef> flag, none of the lane values comes from an
+    // earlier instruction.
+    unsigned KillLaneMask = MO.isUndef() ? ~0u : DefLaneMask;
+    // Add data dependence to all uses we found so far.
+    const TargetSubtargetInfo &ST = MF.getSubtarget();
+    for (VReg2SUnitMultiMap::iterator I = CurrentVRegUses.find(Reg),
+         E = CurrentVRegUses.end(); I != E; /*empty*/) {
+      // Ignore uses of other lanes.
+      if ((I->LaneMask & KillLaneMask) == 0) {
+        ++I;
+        continue;
+      }
+
+      if ((I->LaneMask & DefLaneMask) != 0) {
+        SUnit *UseSU = I->SU;
+        MachineInstr *Use = UseSU->getInstr();
+        SDep Dep(SU, SDep::Data, Reg);
+        unsigned UseOperIdx = 0; // TODO! FIXME! Get a proper value!
+        Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use,
+                                                        UseOperIdx));
+        ST.adjustSchedDependency(SU, UseSU, Dep);
+        UseSU->addPred(Dep);
+      }
+
+      // If none of the lanes can have come from an earlier instruction remove
+      // the Use from the list.
+      I->LaneMask &= ~KillLaneMask;
+      if (I->LaneMask == 0)
+        I = CurrentVRegUses.erase(I);
+      else
+        ++I;
+    }
+  }
 
   // Singly defined vregs do not have output/anti dependencies.
   // The current operand is a def, so we have at least one.
   // Check here if there are any others...
   if (MRI.hasOneDef(Reg))
     return;
 
-  // Add output dependence to the next nearest def of this vreg.
+  // Add output dependence to the next nearest def(s) of this vreg.
   //
   // Unless this definition is dead, the output dependence should be
   // transitively redundant with antidependencies from this definition's
   // uses. We're conservative for now until we have a way to guarantee the uses
   // are not eliminated sometime during scheduling. The output dependence edge
   // is also useful if output latency exceeds def-use latency.
-  VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
-  if (DefI == VRegDefs.end())
-    VRegDefs.insert(VReg2SUnit(Reg, SU));
-  else {
-    SUnit *DefSU = DefI->SU;
-    if (DefSU != SU && DefSU != &ExitSU) {
-      SDep Dep(SU, SDep::Output, Reg);
-      Dep.setLatency(
-        SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
-      DefSU->addPred(Dep);
-    }
-    DefI->SU = SU;
-  }
+  unsigned LaneMask = DefLaneMask;
+  for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
+                                     CurrentVRegDefs.end())) {
+    // Ignore defs for other lanes.
+    if ((V2SU.LaneMask & LaneMask) == 0)
+      continue;
+    // Add an output dependence.
+    SUnit *DefSU = V2SU.SU;
+    // We may have multiple defs of the same lanes in the instruction. This
+    // can happen because lanemasks are shared for targets with too many
+    // subregisters. We also use some representration tricks/hacks where we
+    // add super-register defs/uses, to imply that although we only access
+    // parts of the reg we care about the full one.
+    if (DefSU == SU)
+      continue;
+
+    // Update current definition. This can get tricky if the def was about a
+    // bigger lanemask before. We then have to shrink it and create a new
+    // VReg2SUnit for the non-overlapping part.
+    unsigned OverlapMask = V2SU.LaneMask & LaneMask;
+    unsigned NonOverlapMask = V2SU.LaneMask & ~LaneMask;
+    if (NonOverlapMask != 0)
+      CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, V2SU.SU));
+    V2SU.SU = SU;
+    V2SU.LaneMask = OverlapMask;
+  }
+  // If there are any lanes left we didn't cover yet add a new VReg2SUnit.
+  if (LaneMask != 0)
+    CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU));
 }
 
 /// addVRegUseDeps - Add a register data dependency if the instruction that
 /// defines the virtual register used at OperIdx is mapped to an SUnit. Add a
 /// register antidependency from this SUnit to instructions that occur later in
 /// the same scheduling region if they write the virtual register.
 ///
 /// TODO: Handle ExitSU "uses" properly.
 void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
   MachineInstr *MI = SU->getInstr();
-  unsigned Reg = MI->getOperand(OperIdx).getReg();
+  const MachineOperand &MO = MI->getOperand(OperIdx);
+  unsigned Reg = MO.getReg();
 
   // Record this local VReg use.
-  VReg2UseMap::iterator UI = VRegUses.find(Reg);
+  VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg);
   for (; UI != VRegUses.end(); ++UI) {
     if (UI->SU == SU)
       break;
   }
   if (UI == VRegUses.end())
-    VRegUses.insert(VReg2SUnit(Reg, SU));
+    VRegUses.insert(VReg2SUnit(Reg, 0, SU));
 
-  // Lookup this operand's reaching definition.
-  assert(LIS && "vreg dependencies requires LiveIntervals");
-  LiveQueryResult LRQ
-    = LIS->getInterval(Reg).Query(LIS->getInstructionIndex(MI));
-  VNInfo *VNI = LRQ.valueIn();
-
-  // VNI will be valid because MachineOperand::readsReg() is checked by caller.
-  assert(VNI && "No value to read by operand");
-  MachineInstr *Def = LIS->getInstructionFromIndex(VNI->def);
-  // Phis and other noninstructions (after coalescing) have a NULL Def.
-  if (Def) {
-    SUnit *DefSU = getSUnit(Def);
-    if (DefSU) {
-      // The reaching Def lives within this scheduling region.
-      // Create a data dependence.
-      SDep dep(DefSU, SDep::Data, Reg);
-      // Adjust the dependence latency using operand def/use information, then
-      // allow the target to perform its own adjustments.
-      int DefOp = Def->findRegisterDefOperandIdx(Reg);
-      dep.setLatency(SchedModel.computeOperandLatency(Def, DefOp, MI, OperIdx));
+  unsigned LaneMask = getLaneMaskForMO(MO);
 
-      const TargetSubtargetInfo &ST = MF.getSubtarget();
-      ST.adjustSchedDependency(DefSU, SU, const_cast<SDep &>(dep));
-      SU->addPred(dep);
-    }
-  }
+  // Remember the use, SDeps will be added once we find the Def.
+  CurrentVRegUses.insert(VReg2SUnit(Reg, LaneMask, SU));
+
+  // Add antidependences to the following defs of the vreg.
+  for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
+                                     CurrentVRegDefs.end())) {
+    // Ignore defs for other lanes.
+    unsigned PrevDefLaneMask = V2SU.LaneMask;
+    if ((PrevDefLaneMask & LaneMask) == 0)
+      continue;
+    if (V2SU.SU == SU)
+      continue;
 
-  // Add antidependence to the following def of the vreg it uses.
-  VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
-  if (DefI != VRegDefs.end() && DefI->SU != SU)
-    DefI->SU->addPred(SDep(SU, SDep::Anti, Reg));
+    V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg));
+  }
 }
 
 /// Return true if MI is an instruction we are unable to reason about
 /// (like a call or something with unmodeled side effects).
 static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) {
   if (MI->isCall() || MI->hasUnmodeledSideEffects() ||
       (MI->hasOrderedMemoryRef() &&
        (!MI->mayLoad() || !MI->isInvariantLoad(AA))))
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
   DbgValues.clear();
   FirstDbgValue = nullptr;
 
   assert(Defs.empty() && Uses.empty() &&
          "Only BuildGraph should update Defs/Uses");
   Defs.setUniverse(TRI->getNumRegs());
   Uses.setUniverse(TRI->getNumRegs());
 
-  assert(VRegDefs.empty() && "Only BuildSchedGraph may access VRegDefs");
+  assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
+  assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
+  unsigned NumVirtRegs = MRI.getNumVirtRegs();
+  CurrentVRegDefs.setUniverse(NumVirtRegs);
+  CurrentVRegUses.setUniverse(NumVirtRegs);
+
   VRegUses.clear();
-  VRegDefs.setUniverse(MRI.getNumVirtRegs());
-  VRegUses.setUniverse(MRI.getNumVirtRegs());
+  VRegUses.setUniverse(NumVirtRegs);
 
   // Model data dependencies between instructions being scheduled and the
   // ExitSU.
   addSchedBarrierDeps();
 
   // Walk the list of instructions, from bottom moving up.
   MachineInstr *DbgMI = nullptr;
   for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
new_alias_chain:
       }
     }
   }
   if (DbgMI)
     FirstDbgValue = DbgMI;
 
   Defs.clear();
   Uses.clear();
-  VRegDefs.clear();
+  CurrentVRegDefs.clear();
+  CurrentVRegUses.clear();
   PendingLoads.clear();
 }
 
 /// \brief Initialize register live-range state for updating kills.
 void ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) {
   // Start with no live registers.
   LiveRegs.reset();