Separate ExecutionDepsFix into 4 parts - enable breaking false dependencies for all reg classes.

[myatsina]

Summary

Separate ExecutionDepsFix into 4 parts:

1. ReachingDefsAnalysis - Allows to identify for each instruction what is the “closest” reaching def of a certain register. Used by BreakFalseDeps (for clearance calculation) and ExecutionDomainFix (for arbitrating conflicting domains).
2. ExecutionDomainFix - Changes the variant of the instructions in order to minimize domain crossings.
3. BreakFalseDeps - Breaks false dependencies.
4. LoopTraversal - Creatws a traversal order of the basic blocks that is optimal for loops (introduced in revision L293571). Both ExecutionDomainFix and ReachingDefsAnalysis use this to determine the order they will traverse the basic blocks.

This also included the following changes to ExcecutionDepsFix original logic:

1. BreakFalseDeps and ReachingDefsAnalysis logic no longer restricted by a register class.
2. ReachingDefsAnalysis tracks liveness of reg units instead of reg indices into a given reg class.

Additional changes in affected files:

1. X86 and ARM targets now inherit from ExecutionDomainFix instead of ExecutionDepsFix. BreakFalseDeps also was added to the passes they activate.
2. Comments and references to ExecutionDepsFix replaced with ExecutionDomainFix and BreakFalseDeps, as appropriate.

Additional refactoring changes will follow.

This commit is (almost) NFC.
The only functional change is that now BreakFalseDeps will break dependency for all register classes.
Since no additional instructions were added to the list of instructions that have false dependencies, there is no actual change yet.
In a future commit several instructions (and tests) will be added.

This is the first of 5 patches that fix bugzilla https://bugs.llvm.org/show_bug.cgi?id=33869

Next patches:
https://reviews.llvm.org/D40331
https://reviews.llvm.org/D40332
https://reviews.llvm.org/D40333
https://reviews.llvm.org/D40334

[zvi]

LGTM with a minor comment. Thanks!

lib/CodeGen/ExecutionDepsFix.cpp

183 ↗

(On Diff #123863)

This is more compact and safe:

Defs.assign(numRegUnits, DefaultDefVal);

[myatsina]

Fixed vector intialization.
Also incorporated comments from https://reviews.llvm.org/D40333 in this patch, which seems to be more appropriate than the later one.

[myatsina]

Changes based on comments in https://reviews.llvm.org/D40333

Changed LoopTraversal to not be a pass, but rather a class which returns the BB order and other passes can then traverse and process the BBs.
Separated some logic to a ReachingDefAnalysis pass which is used by both BreakFalsDeps and ExecutionDomainFix.

[myatsina]

Ping

[craig.topper]

include/llvm/CodeGen/ExecutionDepsFix.h

136 ↗

(On Diff #126844)

twise->twice

170 ↗

(On Diff #126844)

Remove the const. It doesn't mean anything if you're returning a whole object.

lib/CodeGen/ExecutionDepsFix.cpp

878 ↗

(On Diff #126844)

traverse is returning an object not a reference so we shouldn't be capturing by reference.

You may want to consider having the caller pass a SmallVector to traverse. That way traverse doesn't have to hardcode an explicit size for the SmallVector.

897 ↗

(On Diff #126844)

Add blank line before this function

[myatsina]

I've addressed the comments in this review and done the commit based on the LGTM in https://reviews.llvm.org/D40333, which is the "end version" of all these refactoring changes after more refactoring and clang-format.

lib/CodeGen/ExecutionDepsFix.cpp

878 ↗

(On Diff #126844)

I've removed in the commit the redundant consts and references as you suggested.
In a later commit I define a dedicated type that obscures the SmallVector size (you can see it in the https://reviews.llvm.org/D40333 review).

llvm/trunk/include/llvm/CodeGen/ExecutionDepsFix.h

struct LiveReg {
 
   /// Instruction that defined this register, relative to the beginning of the
   /// current basic block.  When a LiveReg is used to represent a live-out
   /// register, this value is relative to the end of the basic block, so it
   /// will be a negative number.
   int Def;
 };
 
-class ExecutionDepsFix : public MachineFunctionPass {
-  SpecificBumpPtrAllocator<DomainValue> Allocator;
-  SmallVector<DomainValue*,16> Avail;
-
-  const TargetRegisterClass *const RC;
-  MachineFunction *MF;
-  const TargetInstrInfo *TII;
-  const TargetRegisterInfo *TRI;
-  RegisterClassInfo RegClassInfo;
-  std::vector<SmallVector<int, 1>> AliasMap;
-  const unsigned NumRegs;
-  LiveReg *LiveRegs;
+/// This class provides the basic blocks traversal order used by passes like
+/// ReachingDefAnalysis and ExecutionDomainFix.
+/// It identifies basic blocks that are part of loops and should to be visited twice 
+/// and returns efficient traversal order for all the blocks.
+class LoopTraversal {
+private:
   struct MBBInfo {
-    // Keeps clearance and domain information for all registers. Note that this
-    // is different from the usual definition notion of liveness. The CPU
-    // doesn't care whether or not we consider a register killed.
-    LiveReg *OutRegs = nullptr;
-
     // Whether we have gotten to this block in primary processing yet.
     bool PrimaryCompleted = false;
 
     // The number of predecessors for which primary processing has completed
     unsigned IncomingProcessed = 0;
 
     // The value of `IncomingProcessed` at the start of primary processing
     unsigned PrimaryIncoming = 0;
 
     // The number of predecessors for which all processing steps are done.
     unsigned IncomingCompleted = 0;
 
     MBBInfo() = default;
   };
   using MBBInfoMap = DenseMap<MachineBasicBlock *, MBBInfo>;
   MBBInfoMap MBBInfos;
 
-  /// List of undefined register reads in this block in forward order.
-  std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
+public:
+  struct TraversedMBBInfo {
+    MachineBasicBlock *MBB = nullptr;
+    bool PrimaryPass = true;
+    bool IsDone = true;
+
+    TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true,
+                     bool Done = true)
+        : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
+  };
+  LoopTraversal() {}
 
-  /// Storage for register unit liveness.
-  LivePhysRegs LiveRegSet;
+  SmallVector<TraversedMBBInfo, 4> traverse(MachineFunction &MF);
+
+private:
+  bool isBlockDone(MachineBasicBlock *MBB);
+
+};
+
+/// This class provides the reaching def analysis.
+class ReachingDefAnalysis : public MachineFunctionPass {
+private:
+  MachineFunction *MF;
+  const TargetInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  RegisterClassInfo RegClassInfo;
+  unsigned NumRegUnits;
+  LiveReg *LiveRegs;
+
+  // Keeps clearance information for all registers. Note that this
+  // is different from the usual definition notion of liveness. The CPU
+  // doesn't care whether or not we consider a register killed.
+  using OutRegsInfoMap = DenseMap<MachineBasicBlock *, LiveReg *>;
+  OutRegsInfoMap MBBOutRegsInfos;
 
   /// Current instruction number.
   /// The first instruction in each basic block is 0.
   int CurInstr;
 
+  /// Maps instructions to their instruction Ids, relative to the begining of
+  /// their basic blocks.
+  DenseMap<MachineInstr *, int> InstIds;
+
+  /// All reaching defs of a given RegUnit for a given MBB.
+  using MBBRegUnitDefs = SmallVector<int, 1>;
+  /// All reaching defs of all reg units for a given MBB
+  using MBBDefsInfo = std::vector<MBBRegUnitDefs>;
+  /// All reaching defs of all reg units for a all MBBs
+  using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>;
+  MBBReachingDefsInfo MBBReachingDefs;
+
 public:
-  ExecutionDepsFix(char &PassID, const TargetRegisterClass &RC)
+  static char ID; // Pass identification, replacement for typeid
+
+  ReachingDefAnalysis() : MachineFunctionPass(ID) {
+    initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry());
+  }
+  void releaseMemory() override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  MachineFunctionProperties getRequiredProperties() const override {
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::NoVRegs);
+  }
+
+  /// Provides the instruction id of the closest reaching def instruction of
+  /// PhysReg that reaches MI, relative to the begining of MI's basic block.
+  int getReachingDef(MachineInstr *MI, int PhysReg);
+  /// Provides the clearance - the number of instructions since the closest
+  /// reaching def instuction of PhysReg that reaches MI.
+  int getClearance(MachineInstr *MI, MCPhysReg PhysReg);
+
+private:
+  void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+  void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+  void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+  void processDefs(MachineInstr *);
+};
+
+class ExecutionDomainFix : public MachineFunctionPass {
+  SpecificBumpPtrAllocator<DomainValue> Allocator;
+  SmallVector<DomainValue*,16> Avail;
+
+  const TargetRegisterClass *const RC;
+  MachineFunction *MF;
+  const TargetInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  RegisterClassInfo RegClassInfo;
+  std::vector<SmallVector<int, 1>> AliasMap;
+  const unsigned NumRegs;
+  LiveReg *LiveRegs;
+  // Keeps domain information for all registers. Note that this
+  // is different from the usual definition notion of liveness. The CPU
+  // doesn't care whether or not we consider a register killed.
+  using OutRegsInfoMap = DenseMap<MachineBasicBlock *, LiveReg *>;
+  OutRegsInfoMap MBBOutRegsInfos;
+
+  ReachingDefAnalysis *RDA;
+
+public:
+  ExecutionDomainFix(char &PassID, const TargetRegisterClass &RC)
     : MachineFunctionPass(PassID), RC(&RC), NumRegs(RC.getNumRegs()) {}
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
+    AU.addRequired<ReachingDefAnalysis>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::NoVRegs);
private:
 
   // LiveRegs manipulations.
   void setLiveReg(int rx, DomainValue *DV);
   void kill(int rx);
   void force(int rx, unsigned domain);
   void collapse(DomainValue *dv, unsigned domain);
   bool merge(DomainValue *A, DomainValue *B);
 
-  void enterBasicBlock(MachineBasicBlock*);
-  void leaveBasicBlock(MachineBasicBlock*);
-  bool isBlockDone(MachineBasicBlock *);
-  void processBasicBlock(MachineBasicBlock *MBB, bool PrimaryPass);
+  void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+  void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+  void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
   bool visitInstr(MachineInstr *);
-  void processDefs(MachineInstr *, bool breakDependency, bool Kill);
+  void processDefs(MachineInstr *, bool Kill);
   void visitSoftInstr(MachineInstr*, unsigned mask);
   void visitHardInstr(MachineInstr*, unsigned domain);
+};
+
+class BreakFalseDeps : public MachineFunctionPass {
+private:
+  MachineFunction *MF;
+  const TargetInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  RegisterClassInfo RegClassInfo;
+
+  /// List of undefined register reads in this block in forward order.
+  std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
+
+  /// Storage for register unit liveness.
+  LivePhysRegs LiveRegSet;
+
+  ReachingDefAnalysis *RDA;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  BreakFalseDeps() : MachineFunctionPass(ID) {
+    initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+    AU.addRequired<ReachingDefAnalysis>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  MachineFunctionProperties getRequiredProperties() const override {
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::NoVRegs);
+  }
+
+private:
+  void processBasicBlock(MachineBasicBlock *MBB);
+  void processDefs(MachineInstr *MI);
   bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
                                 unsigned Pref);
   bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref);
   void processUndefReads(MachineBasicBlock*);
 };
 
 } // end namepsace llvm
 
 #endif // LLVM_CODEGEN_EXECUTIONDEPSFIX_H

llvm/trunk/include/llvm/InitializePasses.h

 void initializeBasicAAWrapperPassPass(PassRegistry&);
 void initializeBlockExtractorPassPass(PassRegistry&);
 void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry&);
 void initializeBoundsCheckingLegacyPassPass(PassRegistry&);
 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&);
 void initializeBranchRelaxationPass(PassRegistry&);
 void initializeBreakCriticalEdgesPass(PassRegistry&);
+void initializeBreakFalseDepsPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);

 void initializeProfileSummaryInfoWrapperPassPass(PassRegistry&);
 void initializePromoteLegacyPassPass(PassRegistry&);
 void initializePruneEHPass(PassRegistry&);
 void initializeRABasicPass(PassRegistry&);
 void initializeRegAllocFastPass(PassRegistry&);
 void initializeRAGreedyPass(PassRegistry&);
 void initializeReassociateLegacyPassPass(PassRegistry&);
 void initializeRegBankSelectPass(PassRegistry&);
+void initializeReachingDefAnalysisPass(PassRegistry&);
 void initializeRegToMemPass(PassRegistry&);
 void initializeRegionInfoPassPass(PassRegistry&);
 void initializeRegionOnlyPrinterPass(PassRegistry&);
 void initializeRegionOnlyViewerPass(PassRegistry&);
 void initializeRegionPrinterPass(PassRegistry&);
 void initializeRegionViewerPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
 void initializeRenameIndependentSubregsPass(PassRegistry&);

llvm/trunk/lib/CodeGen/ExecutionDepsFix.cpp

 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "execution-deps-fix"
 
+char ReachingDefAnalysis::ID = 0;
+INITIALIZE_PASS(ReachingDefAnalysis, "reaching-deps-analysis",
+                "ReachingDefAnalysis", false, true)
+
+char BreakFalseDeps::ID = 0;
+INITIALIZE_PASS_BEGIN(BreakFalseDeps, "break-false-deps", "BreakFalseDeps",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
+INITIALIZE_PASS_END(BreakFalseDeps, "break-false-deps", "BreakFalseDeps", false,
+                    false)
+
 /// Translate TRI register number to a list of indices into our smaller tables
 /// of interesting registers.
 iterator_range<SmallVectorImpl<int>::const_iterator>
-ExecutionDepsFix::regIndices(unsigned Reg) const {
+ExecutionDomainFix::regIndices(unsigned Reg) const {
   assert(Reg < AliasMap.size() && "Invalid register");
   const auto &Entry = AliasMap[Reg];
   return make_range(Entry.begin(), Entry.end());
 }
 
-DomainValue *ExecutionDepsFix::alloc(int domain) {
+DomainValue *ExecutionDomainFix::alloc(int domain) {
   DomainValue *dv = Avail.empty() ?
                       new(Allocator.Allocate()) DomainValue :
                       Avail.pop_back_val();
   if (domain >= 0)
     dv->addDomain(domain);
   assert(dv->Refs == 0 && "Reference count wasn't cleared");
   assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
   return dv;
 }
 
 /// Release a reference to DV.  When the last reference is released,
 /// collapse if needed.
-void ExecutionDepsFix::release(DomainValue *DV) {
+void ExecutionDomainFix::release(DomainValue *DV) {
   while (DV) {
     assert(DV->Refs && "Bad DomainValue");
     if (--DV->Refs)
       return;
 
     // There are no more DV references. Collapse any contained instructions.
     if (DV->AvailableDomains && !DV->isCollapsed())
       collapse(DV, DV->getFirstDomain());
 
     DomainValue *Next = DV->Next;
     DV->clear();
     Avail.push_back(DV);
     // Also release the next DomainValue in the chain.
     DV = Next;
   }
 }
 
 /// Follow the chain of dead DomainValues until a live DomainValue is reached.
 /// Update the referenced pointer when necessary.
-DomainValue *ExecutionDepsFix::resolve(DomainValue *&DVRef) {
+DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
   DomainValue *DV = DVRef;
   if (!DV || !DV->Next)
     return DV;
 
   // DV has a chain. Find the end.
   do DV = DV->Next;
   while (DV->Next);
 
   // Update DVRef to point to DV.
   retain(DV);
   release(DVRef);
   DVRef = DV;
   return DV;
 }
 
 /// Set LiveRegs[rx] = dv, updating reference counts.
-void ExecutionDepsFix::setLiveReg(int rx, DomainValue *dv) {
+void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
   assert(unsigned(rx) < NumRegs && "Invalid index");
   assert(LiveRegs && "Must enter basic block first.");
 
   if (LiveRegs[rx].Value == dv)
     return;
   if (LiveRegs[rx].Value)
     release(LiveRegs[rx].Value);
   LiveRegs[rx].Value = retain(dv);
 }
 
 // Kill register rx, recycle or collapse any DomainValue.
-void ExecutionDepsFix::kill(int rx) {
+void ExecutionDomainFix::kill(int rx) {
   assert(unsigned(rx) < NumRegs && "Invalid index");
   assert(LiveRegs && "Must enter basic block first.");
   if (!LiveRegs[rx].Value)
     return;
 
   release(LiveRegs[rx].Value);
   LiveRegs[rx].Value = nullptr;
 }
 
 /// Force register rx into domain.
-void ExecutionDepsFix::force(int rx, unsigned domain) {
+void ExecutionDomainFix::force(int rx, unsigned domain) {
   assert(unsigned(rx) < NumRegs && "Invalid index");
   assert(LiveRegs && "Must enter basic block first.");
   if (DomainValue *dv = LiveRegs[rx].Value) {
     if (dv->isCollapsed())
       dv->addDomain(domain);
     else if (dv->hasDomain(domain))
       collapse(dv, domain);
     else {
       // This is an incompatible open DomainValue. Collapse it to whatever and
       // force the new value into domain. This costs a domain crossing.
       collapse(dv, dv->getFirstDomain());
       assert(LiveRegs[rx].Value && "Not live after collapse?");
       LiveRegs[rx].Value->addDomain(domain);
     }
   } else {
     // Set up basic collapsed DomainValue.
     setLiveReg(rx, alloc(domain));
   }
 }
 
 /// Collapse open DomainValue into given domain. If there are multiple
 /// registers using dv, they each get a unique collapsed DomainValue.
-void ExecutionDepsFix::collapse(DomainValue *dv, unsigned domain) {
+void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
   assert(dv->hasDomain(domain) && "Cannot collapse");
 
   // Collapse all the instructions.
   while (!dv->Instrs.empty())
     TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
   dv->setSingleDomain(domain);
 
   // If there are multiple users, give them new, unique DomainValues.
   if (LiveRegs && dv->Refs > 1)
     for (unsigned rx = 0; rx != NumRegs; ++rx)
       if (LiveRegs[rx].Value == dv)
         setLiveReg(rx, alloc(domain));
 }
 
 /// All instructions and registers in B are moved to A, and B is released.
-bool ExecutionDepsFix::merge(DomainValue *A, DomainValue *B) {
+bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
   assert(!A->isCollapsed() && "Cannot merge into collapsed");
   assert(!B->isCollapsed() && "Cannot merge from collapsed");
   if (A == B)
     return true;
   // Restrict to the domains that A and B have in common.
   unsigned common = A->getCommonDomains(B->AvailableDomains);
   if (!common)
     return false;
for (unsigned rx = 0; rx != NumRegs; ++rx) {
     assert(LiveRegs && "no space allocated for live registers");
     if (LiveRegs[rx].Value == B)
       setLiveReg(rx, A);
   }
   return true;
 }
 
 /// Set up LiveRegs by merging predecessor live-out values.
-void ExecutionDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
+void ReachingDefAnalysis::enterBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+
+  MachineBasicBlock *MBB = TraversedMBB.MBB;
+  int MBBNumber = MBB->getNumber();
+  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
+
   // Reset instruction counter in each basic block.
   CurInstr = 0;
 
-  // Set up UndefReads to track undefined register reads.
-  UndefReads.clear();
-  LiveRegSet.clear();
-
   // Set up LiveRegs to represent registers entering MBB.
   if (!LiveRegs)
-    LiveRegs = new LiveReg[NumRegs];
+    LiveRegs = new LiveReg[NumRegUnits];
 
   // Default values are 'nothing happened a long time ago'.
-  for (unsigned rx = 0; rx != NumRegs; ++rx) {
-    LiveRegs[rx].Value = nullptr;
+  for (unsigned rx = 0; rx != NumRegUnits; ++rx) {
     LiveRegs[rx].Def = -(1 << 20);
   }
 
   // This is the entry block.
   if (MBB->pred_empty()) {
     for (const auto &LI : MBB->liveins()) {
-      for (int rx : regIndices(LI.PhysReg)) {
+      for (MCRegUnitIterator rx(LI.PhysReg, TRI); rx.isValid(); ++rx) {
         // Treat function live-ins as if they were defined just before the first
         // instruction.  Usually, function arguments are set up immediately
         // before the call.
-        LiveRegs[rx].Def = -1;
+        LiveRegs[*rx].Def = -1;
+        MBBReachingDefs[MBBNumber][*rx].push_back(LiveRegs[*rx].Def);
       }
     }
     DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
     return;
   }
 
   // Try to coalesce live-out registers from predecessors.
   for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
        pe = MBB->pred_end(); pi != pe; ++pi) {
-    auto fi = MBBInfos.find(*pi);
-    assert(fi != MBBInfos.end() &&
+    auto fi = MBBOutRegsInfos.find(*pi);
+    assert(fi != MBBOutRegsInfos.end() &&
            "Should have pre-allocated MBBInfos for all MBBs");
-    LiveReg *Incoming = fi->second.OutRegs;
+    LiveReg *Incoming = fi->second;
     // Incoming is null if this is a backedge from a BB
     // we haven't processed yet
     if (Incoming == nullptr) {
       continue;
     }
 
-    for (unsigned rx = 0; rx != NumRegs; ++rx) {
+    for (unsigned rx = 0; rx != NumRegUnits; ++rx) {
       // Use the most recent predecessor def for each register.
       LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, Incoming[rx].Def);
+      if ((LiveRegs[rx].Def  != -(1 << 20))) 
+        MBBReachingDefs[MBBNumber][rx].push_back(LiveRegs[rx].Def);
+    }
+  }
+
+  DEBUG(
+      dbgs() << printMBBReference(*MBB)
+             << (!TraversedMBB.IsDone ? ": incomplete\n" : ": all preds known\n"));
+}
+
+/// Set up LiveRegs by merging predecessor live-out values.
+void ExecutionDomainFix::enterBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+
+  MachineBasicBlock *MBB = TraversedMBB.MBB;
+
+  // Set up LiveRegs to represent registers entering MBB.
+  if (!LiveRegs)
+    LiveRegs = new LiveReg[NumRegs];
+
+  // Default values are 'nothing happened a long time ago'.
+  for (unsigned rx = 0; rx != NumRegs; ++rx) {
+    LiveRegs[rx].Value = nullptr;
+  }
+
+  // This is the entry block.
+  if (MBB->pred_empty()) {
+    DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
+    return;
+  }
+
+  // Try to coalesce live-out registers from predecessors.
+  for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
+       pe = MBB->pred_end(); pi != pe; ++pi) {
+    auto fi = MBBOutRegsInfos.find(*pi);
+    assert(fi != MBBOutRegsInfos.end() &&
+      "Should have pre-allocated MBBInfos for all MBBs");
+    LiveReg *Incoming = fi->second;
+    // Incoming is null if this is a backedge from a BB
+    // we haven't processed yet
+    if (Incoming == nullptr) {
+      continue;
+    }
 
+    for (unsigned rx = 0; rx != NumRegs; ++rx) {
       DomainValue *pdv = resolve(Incoming[rx].Value);
       if (!pdv)
         continue;
       if (!LiveRegs[rx].Value) {
         setLiveReg(rx, pdv);
         continue;
       }
 
for (unsigned rx = 0; rx != NumRegs; ++rx) {
       if (!pdv->isCollapsed())
         merge(LiveRegs[rx].Value, pdv);
       else
         force(rx, pdv->getFirstDomain());
     }
   }
   DEBUG(
       dbgs() << printMBBReference(*MBB)
-             << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"));
+             << (!TraversedMBB.IsDone ? ": incomplete\n" : ": all preds known\n"));
 }
 
-void ExecutionDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
+void ReachingDefAnalysis::leaveBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
   assert(LiveRegs && "Must enter basic block first.");
-  LiveReg *OldOutRegs = MBBInfos[MBB].OutRegs;
   // Save register clearances at end of MBB - used by enterBasicBlock().
-  MBBInfos[MBB].OutRegs = LiveRegs;
+  MBBOutRegsInfos[TraversedMBB.MBB] = LiveRegs;
 
   // While processing the basic block, we kept `Def` relative to the start
   // of the basic block for convenience. However, future use of this information
   // only cares about the clearance from the end of the block, so adjust
   // everything to be relative to the end of the basic block.
-  for (unsigned i = 0, e = NumRegs; i != e; ++i)
+  for (unsigned i = 0, e = NumRegUnits; i != e; ++i)
     LiveRegs[i].Def -= CurInstr;
+  LiveRegs = nullptr;
+}
+
+void ExecutionDomainFix::leaveBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+  assert(LiveRegs && "Must enter basic block first.");
+  LiveReg *OldOutRegs = MBBOutRegsInfos[TraversedMBB.MBB];
+  // Save register clearances at end of MBB - used by enterBasicBlock().
+  MBBOutRegsInfos[TraversedMBB.MBB] = LiveRegs;
   if (OldOutRegs) {
     // This must be the second pass.
     // Release all the DomainValues instead of keeping them.
     for (unsigned i = 0, e = NumRegs; i != e; ++i)
       release(OldOutRegs[i].Value);
     delete[] OldOutRegs;
   }
   LiveRegs = nullptr;
 }
 
-bool ExecutionDepsFix::visitInstr(MachineInstr *MI) {
+bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
   // Update instructions with explicit execution domains.
   std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
   if (DomP.first) {
     if (DomP.second)
       visitSoftInstr(MI, DomP.second);
     else
       visitHardInstr(MI, DomP.first);
   }
 
   return !DomP.first;
 }
 
 /// \brief Helps avoid false dependencies on undef registers by updating the
 /// machine instructions' undef operand to use a register that the instruction
 /// is truly dependent on, or use a register with clearance higher than Pref.
 /// Returns true if it was able to find a true dependency, thus not requiring
 /// a dependency breaking instruction regardless of clearance.
-bool ExecutionDepsFix::pickBestRegisterForUndef(MachineInstr *MI,
+bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI,
                                                 unsigned OpIdx, unsigned Pref) {
   MachineOperand &MO = MI->getOperand(OpIdx);
   assert(MO.isUndef() && "Expected undef machine operand");
 
   unsigned OriginalReg = MO.getReg();
 
-  // Update only undef operands that are mapped to one register.
-  if (AliasMap[OriginalReg].size() != 1)
+  // Update only undef operands that have reg units that are mapped to one root.
+  for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) {
+    unsigned NumRoots = 0;
+    for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) {
+      NumRoots++;
+      if (NumRoots > 1)
         return false;
+    }
+  }
 
   // Get the undef operand's register class
   const TargetRegisterClass *OpRC =
       TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
 
   // If the instruction has a true dependency, we can hide the false depdency
   // behind it.
   for (MachineOperand &CurrMO : MI->operands()) {
     if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
         !OpRC->contains(CurrMO.getReg()))
       continue;
     // We found a true dependency - replace the undef register with the true
     // dependency.
     MO.setReg(CurrMO.getReg());
     return true;
   }
 
   // Go over all registers in the register class and find the register with
   // max clearance or clearance higher than Pref.
   unsigned MaxClearance = 0;
   unsigned MaxClearanceReg = OriginalReg;
   ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
   for (auto Reg : Order) {
-    assert(AliasMap[Reg].size() == 1 &&
-           "Reg is expected to be mapped to a single index");
-    int RCrx = *regIndices(Reg).begin();
-    unsigned Clearance = CurInstr - LiveRegs[RCrx].Def;
+    unsigned Clearance = RDA->getClearance(MI, Reg);
     if (Clearance <= MaxClearance)
       continue;
     MaxClearance = Clearance;
     MaxClearanceReg = Reg;
 
     if (MaxClearance > Pref)
       break;
   }
 
   // Update the operand if we found a register with better clearance.
   if (MaxClearanceReg != OriginalReg)
     MO.setReg(MaxClearanceReg);
 
   return false;
 }
 
 /// \brief Return true to if it makes sense to break dependence on a partial def
 /// or undef use.
-bool ExecutionDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
-                                             unsigned Pref) {
+bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
   unsigned reg = MI->getOperand(OpIdx).getReg();
-  for (int rx : regIndices(reg)) {
-    unsigned Clearance = CurInstr - LiveRegs[rx].Def;
-    DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
+  unsigned Clearance = RDA->getClearance(MI, reg);
 
-    if (Pref > Clearance) {
-      DEBUG(dbgs() << ": Break dependency.\n");
-      continue;
-    }
-    DEBUG(dbgs() << ": OK .\n");
-    return false;
-  }
-  return true;
-}
+    return true;
 
 // Update def-ages for registers defined by MI.
 // If Kill is set, also kill off DomainValues clobbered by the defs.
 //
 // Also break dependencies on partial defs and undef uses.
-void ExecutionDepsFix::processDefs(MachineInstr *MI, bool breakDependency,
-                                   bool Kill) {
+void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
+  assert(!MI->isDebugValue() && "Won't process debug values");
+  const MCInstrDesc &MCID = MI->getDesc();
+  for (unsigned i = 0,
+         e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
+         i != e; ++i) {
+    MachineOperand &MO = MI->getOperand(i);
+    if (!MO.isReg())
+      continue;
+    if (MO.isUse())
+      continue;
+    for (int rx : regIndices(MO.getReg())) {
+      // This instruction explicitly defines rx.
+      DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI);
+
+      // Kill off domains redefined by generic instructions.
+      if (Kill)
+        kill(rx);
+    }
+  }
+}
+
+// Update def-ages for registers defined by MI.
+// Also break dependencies on partial defs and undef uses.
+void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
+  assert(!MI->isDebugValue() && "Won't process debug values");
+
+  int MBBNumber = MI->getParent()->getNumber();
+  const MCInstrDesc &MCID = MI->getDesc();
+  for (unsigned i = 0,
+         e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
+         i != e; ++i) {
+    MachineOperand &MO = MI->getOperand(i);
+    if (!MO.isReg() || !MO.getReg())
+      continue;
+    if (MO.isUse())
+      continue;
+    for (MCRegUnitIterator rx(MO.getReg(), TRI); rx.isValid(); ++rx) {
+      // This instruction explicitly defines rx.
+      DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr << '\t'
+                   << *MI);
+
+      // How many instructions since this reg unit was last written?
+      LiveRegs[*rx].Def = CurInstr;
+      MBBReachingDefs[MBBNumber][*rx].push_back(CurInstr);
+    }
+  }
+  InstIds[MI] = CurInstr;
+  ++CurInstr;
+}
+
+// Update def-ages for registers defined by MI.
+// Also break dependencies on partial defs and undef uses.
+void BreakFalseDeps::processDefs(MachineInstr *MI) {
   assert(!MI->isDebugValue() && "Won't process debug values");
 
   // Break dependence on undef uses. Do this before updating LiveRegs below.
   unsigned OpNum;
-  if (breakDependency) {
-    unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
-    if (Pref) {
-      bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
-      // We don't need to bother trying to break a dependency if this
-      // instruction has a true dependency on that register through another
-      // operand - we'll have to wait for it to be available regardless.
-      if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
-        UndefReads.push_back(std::make_pair(MI, OpNum));
-    }
-  }
+
   const MCInstrDesc &MCID = MI->getDesc();
   for (unsigned i = 0,
          e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
          i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg())
+    if (!MO.isReg() || !MO.getReg())
       continue;
     if (MO.isUse())
       continue;
-    for (int rx : regIndices(MO.getReg())) {
-      // This instruction explicitly defines rx.
-      DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << CurInstr
-                   << '\t' << *MI);
-
-      if (breakDependency) {
-        // Check clearance before partial register updates.
-        // Call breakDependence before setting LiveRegs[rx].Def.
-        unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
-        if (Pref && shouldBreakDependence(MI, i, Pref))
-          TII->breakPartialRegDependency(*MI, i, TRI);
-      }
-
-      // How many instructions since rx was last written?
-      LiveRegs[rx].Def = CurInstr;
-
-      // Kill off domains redefined by generic instructions.
-      if (Kill)
-        kill(rx);
-    }
-  }
-  ++CurInstr;
 }
 
 /// \break Break false dependencies on undefined register reads.
 ///
 /// Walk the block backward computing precise liveness. This is expensive, so we
 /// only do it on demand. Note that the occurrence of undefined register reads
 /// that should be broken is very rare, but when they occur we may have many in
 /// a single block.
-void ExecutionDepsFix::processUndefReads(MachineBasicBlock *MBB) {
+void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
   if (UndefReads.empty())
     return;
 
   // Collect this block's live out register units.
   LiveRegSet.init(*TRI);
   // We do not need to care about pristine registers as they are just preserved
   // but not actually used in the function.
   LiveRegSet.addLiveOutsNoPristines(*MBB);
if (UndefMI == &I) {
       UndefMI = UndefReads.back().first;
       OpIdx = UndefReads.back().second;
     }
   }
 }
 
 // A hard instruction only works in one domain. All input registers will be
 // forced into that domain.
-void ExecutionDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
+void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
   // Collapse all uses.
   for (unsigned i = mi->getDesc().getNumDefs(),
                 e = mi->getDesc().getNumOperands(); i != e; ++i) {
     MachineOperand &mo = mi->getOperand(i);
     if (!mo.isReg()) continue;
     for (int rx : regIndices(mo.getReg())) {
       force(rx, domain);
     }
   }
 
   // Kill all defs and force them.
   for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
     MachineOperand &mo = mi->getOperand(i);
     if (!mo.isReg()) continue;
     for (int rx : regIndices(mo.getReg())) {
       kill(rx);
       force(rx, domain);
     }
   }
 }
 
 // A soft instruction can be changed to work in other domains given by mask.
-void ExecutionDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
+void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
   // Bitmask of available domains for this instruction after taking collapsed
   // operands into account.
   unsigned available = mask;
 
   // Scan the explicit use operands for incoming domains.
   SmallVector<int, 4> used;
   if (LiveRegs)
     for (unsigned i = mi->getDesc().getNumDefs(),
if (isPowerOf2_32(available)) {
     return;
   }
 
   // Kill off any remaining uses that don't match available, and build a list of
   // incoming DomainValues that we want to merge.
   SmallVector<const LiveReg *, 4> Regs;
   for (int rx : used) {
     assert(LiveRegs && "no space allocated for live registers");
-    const LiveReg &LR = LiveRegs[rx];
+    LiveReg &LR = LiveRegs[rx];
+    LR.Def = RDA->getReachingDef(mi, RC->getRegister(rx));
     // This useless DomainValue could have been missed above.
     if (!LR.Value->getCommonDomains(available)) {
       kill(rx);
       continue;
     }
     // Sorted insertion.
     auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
                               [](const LiveReg *LHS, const LiveReg *RHS) {
for (int rx : regIndices(mo.getReg())) {
       if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
         kill(rx);
         setLiveReg(rx, dv);
       }
     }
   }
 }
 
-void ExecutionDepsFix::processBasicBlock(MachineBasicBlock *MBB,
-                                         bool PrimaryPass) {
-  enterBasicBlock(MBB);
+void ExecutionDomainFix::processBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+  enterBasicBlock(TraversedMBB);
   // If this block is not done, it makes little sense to make any decisions
   // based on clearance information. We need to make a second pass anyway,
   // and by then we'll have better information, so we can avoid doing the work
   // to try and break dependencies now.
-  bool breakDependency = isBlockDone(MBB);
-  for (MachineInstr &MI : *MBB) {
+  for (MachineInstr &MI : *TraversedMBB.MBB) {
     if (!MI.isDebugValue()) {
       bool Kill = false;
-      if (PrimaryPass)
+      if (TraversedMBB.PrimaryPass)
         Kill = visitInstr(&MI);
-      processDefs(&MI, breakDependency, Kill);
+      processDefs(&MI, Kill);
     }
   }
-  if (breakDependency)
-    processUndefReads(MBB);
-  leaveBasicBlock(MBB);
+  leaveBasicBlock(TraversedMBB);
 }
 
-bool ExecutionDepsFix::isBlockDone(MachineBasicBlock *MBB) {
-  return MBBInfos[MBB].PrimaryCompleted &&
-         MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
-         MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
+void ReachingDefAnalysis::processBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+  enterBasicBlock(TraversedMBB);
+  for (MachineInstr &MI : *TraversedMBB.MBB) {
+    if (!MI.isDebugValue())
+      processDefs(&MI);
+  }
+  leaveBasicBlock(TraversedMBB);
 }
 
-bool ExecutionDepsFix::runOnMachineFunction(MachineFunction &mf) {
-  if (skipFunction(mf.getFunction()))
-    return false;
-  MF = &mf;
-  TII = MF->getSubtarget().getInstrInfo();
-  TRI = MF->getSubtarget().getRegisterInfo();
-  RegClassInfo.runOnMachineFunction(mf);
-  LiveRegs = nullptr;
-  assert(NumRegs == RC->getNumRegs() && "Bad regclass");
-
-  DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
-               << TRI->getRegClassName(RC) << " **********\n");
-
-  // If no relevant registers are used in the function, we can skip it
-  // completely.
-  bool anyregs = false;
-  const MachineRegisterInfo &MRI = mf.getRegInfo();
-  for (unsigned Reg : *RC) {
-    if (MRI.isPhysRegUsed(Reg)) {
-      anyregs = true;
-      break;
+void BreakFalseDeps::processBasicBlock(MachineBasicBlock* MBB) {
+  UndefReads.clear();
+  // If this block is not done, it makes little sense to make any decisions
+  // based on clearance information. We need to make a second pass anyway,
+  // and by then we'll have better information, so we can avoid doing the work
+  // to try and break dependencies now.
+  for (MachineInstr &MI : *MBB) {
+    if (!MI.isDebugValue()) {
+      processDefs(&MI);
     }
   }
-  if (!anyregs) return false;
+  processUndefReads(MBB);
+}
 
-  // Initialize the AliasMap on the first use.
-  if (AliasMap.empty()) {
-    // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
-    // therefore the LiveRegs array.
-    AliasMap.resize(TRI->getNumRegs());
-    for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
-      for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
-           AI.isValid(); ++AI)
-        AliasMap[*AI].push_back(i);
-  }
+bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
+  return MBBInfos[MBB].PrimaryCompleted &&
+         MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
+         MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
 
+SmallVector<LoopTraversal::TraversedMBBInfo, 4>
+LoopTraversal::traverse(MachineFunction &MF) {
   // Initialize the MMBInfos
-  for (auto &MBB : mf) {
+  for (auto &MBB : MF) {
     MBBInfo InitialInfo;
     MBBInfos.insert(std::make_pair(&MBB, InitialInfo));
   }
 
   /*
    *  We want to visit every instruction in every basic block in order to update
    *  it's execution domain or break any false dependencies. However, for the
    *  dependency breaking, we need to know clearances from all predecessors
LoopTraversal::traverse(MachineFunction &MF) {
    *
    *  Note that we avoid processing D twice, because we can entirely process
    *  the predecessors before getting to D. We call a block that is ready
    *  for its second round of processing `done` (isBlockDone). Once we finish
    *  processing some block, we update the counters in MBBInfos and re-process
    *  any successors that are now done.
    */
 
-  MachineBasicBlock *Entry = &*MF->begin();
+  MachineBasicBlock *Entry = &*MF.begin();
   ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
   SmallVector<MachineBasicBlock *, 4> Workqueue;
+  SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder;
   for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
          MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
     MachineBasicBlock *MBB = *MBBI;
     // N.B: IncomingProcessed and IncomingCompleted were already updated while
     // processing this block's predecessors.
     MBBInfos[MBB].PrimaryCompleted = true;
     MBBInfos[MBB].PrimaryIncoming = MBBInfos[MBB].IncomingProcessed;
     bool Primary = true;
     Workqueue.push_back(MBB);
     while (!Workqueue.empty()) {
       MachineBasicBlock *ActiveMBB = &*Workqueue.back();
       Workqueue.pop_back();
-      processBasicBlock(ActiveMBB, Primary);
       bool Done = isBlockDone(ActiveMBB);
+      MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
       for (auto *Succ : ActiveMBB->successors()) {
         if (!isBlockDone(Succ)) {
           if (Primary) {
             MBBInfos[Succ].IncomingProcessed++;
           }
           if (Done) {
             MBBInfos[Succ].IncomingCompleted++;
           }
LoopTraversal::traverse(MachineFunction &MF) {
   // This is possible if blocks have dead predecessors, so we didn't visit them
   // above.
   for (ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
            MBBI = RPOT.begin(),
            MBBE = RPOT.end();
        MBBI != MBBE; ++MBBI) {
     MachineBasicBlock *MBB = *MBBI;
     if (!isBlockDone(MBB)) {
-      processBasicBlock(MBB, false);
+      MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
       // Don't update successors here. We'll get to them anyway through this
       // loop.
     }
   }
 
-  // Clear the LiveOuts vectors and collapse any remaining DomainValues.
-  for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
-         MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
-    auto FI = MBBInfos.find(*MBBI);
-    if (FI == MBBInfos.end() || !FI->second.OutRegs)
+  MBBInfos.clear();
+
+  return MBBTraversalOrder;
+}
+
+bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
+  if (skipFunction(mf.getFunction()))
+    return false;
+  MF = &mf;
+  TII = MF->getSubtarget().getInstrInfo();
+  TRI = MF->getSubtarget().getRegisterInfo();
+  LiveRegs = nullptr;
+  assert(NumRegs == RC->getNumRegs() && "Bad regclass");
+
+  RDA = &getAnalysis<ReachingDefAnalysis>();
+
+  DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "
+               << TRI->getRegClassName(RC) << " **********\n");
+
+  // If no relevant registers are used in the function, we can skip it
+  // completely.
+  bool anyregs = false;
+  const MachineRegisterInfo &MRI = mf.getRegInfo();
+  for (unsigned Reg : *RC) {
+    if (MRI.isPhysRegUsed(Reg)) {
+      anyregs = true;
+      break;
+    }
+  }
+  if (!anyregs) return false;
+
+  // Initialize the AliasMap on the first use.
+  if (AliasMap.empty()) {
+    // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
+    // therefore the LiveRegs array.
+    AliasMap.resize(TRI->getNumRegs());
+    for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
+      for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
+           AI.isValid(); ++AI)
+        AliasMap[*AI].push_back(i);
+  }
+
+  // Initialize the MBBOutRegsInfos
+  for (auto &MBB : mf) {
+    MBBOutRegsInfos.insert(std::make_pair(&MBB, nullptr));
+  }
+
+  // Traverse the basic blocks.
+  LoopTraversal Traversal;
+  SmallVector<LoopTraversal::TraversedMBBInfo, 4> TraversedMBBInfoOrder =
+      Traversal.traverse(mf);
+  for (auto TraversedMBB : TraversedMBBInfoOrder) {
+    processBasicBlock(TraversedMBB);
+  }
+
+  for (auto MBBOutRegs : MBBOutRegsInfos) {
+    if (!MBBOutRegs.second)
       continue;
     for (unsigned i = 0, e = NumRegs; i != e; ++i)
-      if (FI->second.OutRegs[i].Value)
-        release(FI->second.OutRegs[i].Value);
-    delete[] FI->second.OutRegs;
+      if (MBBOutRegs.second[i].Value)
+        release(MBBOutRegs.second[i].Value);
+    delete[] MBBOutRegs.second;
   }
-  MBBInfos.clear();
-  UndefReads.clear();
+  MBBOutRegsInfos.clear();
   Avail.clear();
   Allocator.DestroyAll();
 
   return false;
 }
+
+bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
+  if (skipFunction(mf.getFunction()))
+    return false;
+  MF = &mf;
+  TII = MF->getSubtarget().getInstrInfo();
+  TRI = MF->getSubtarget().getRegisterInfo();
+
+  LiveRegs = nullptr;
+  NumRegUnits = TRI->getNumRegUnits();
+
+  MBBReachingDefs.resize(mf.getNumBlockIDs());
+
+  DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
+
+  // Initialize the MBBOutRegsInfos
+  for (auto &MBB : mf) {
+    MBBOutRegsInfos.insert(std::make_pair(&MBB, nullptr));
+  }
+
+  // Traverse the basic blocks.
+  LoopTraversal Traversal;
+  SmallVector<LoopTraversal::TraversedMBBInfo, 4> TraversedMBBInfoOrder =
+      Traversal.traverse(mf);
+  for (auto TraversedMBB : TraversedMBBInfoOrder) {
+    processBasicBlock(TraversedMBB);
+  }
+
+  // Sorting all reaching defs found for a ceartin reg unit in a given BB.
+  for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
+    for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
+      std::sort(RegUnitDefs.begin(), RegUnitDefs.end());
+  }
+
+  return false;
+}
+
+void ReachingDefAnalysis::releaseMemory() {
+  // Clear the LiveOuts vectors and collapse any remaining DomainValues.
+  for (auto MBBOutRegs : MBBOutRegsInfos) {
+    if (!MBBOutRegs.second)
+      continue;
+    delete[] MBBOutRegs.second;
+  }
+  MBBOutRegsInfos.clear();
+  MBBReachingDefs.clear();
+  InstIds.clear();
+}
+
+bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {
+  if (skipFunction(mf.getFunction()))
+    return false;
+  MF = &mf;
+  TII = MF->getSubtarget().getInstrInfo();
+  TRI = MF->getSubtarget().getRegisterInfo();
+  RDA = &getAnalysis<ReachingDefAnalysis>();
+
+  RegClassInfo.runOnMachineFunction(mf);
+
+  DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
+
+  // Traverse the basic blocks.
+  for (MachineBasicBlock &MBB : mf) {
+    processBasicBlock(&MBB);
+  }
+
+  return false;
+}
+
+int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
+  int InstId = InstIds[MI];
+  int DefRes = -(1 << 20);
+  int MBBNumber = MI->getParent()->getNumber();
+  int LatestDef = -(1 << 20);
+  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
+    for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
+      if (Def >= InstId)
+        break;
+      DefRes = Def;
+    }
+    LatestDef = std::max(LatestDef, DefRes);
+  }
+  return LatestDef;
+}
+
+int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
+  return InstIds[MI] - getReachingDef(MI, PhysReg);
+}

llvm/trunk/lib/Target/ARM/ARMTargetMachine.cpp

EnableARMLoadStoreOpt("arm-load-store-opt", cl::Hidden,
                       cl::init(true));
 
 // FIXME: Unify control over GlobalMerge.
 static cl::opt<cl::boolOrDefault>
 EnableGlobalMerge("arm-global-merge", cl::Hidden,
                   cl::desc("Enable the global merge pass"));
 
 namespace llvm {
-  void initializeARMExecutionDepsFixPass(PassRegistry&);
+  void initializeARMExecutionDomainFixPass(PassRegistry&);
 }
 
 extern "C" void LLVMInitializeARMTarget() {
   // Register the target.
   RegisterTargetMachine<ARMLETargetMachine> X(getTheARMLETarget());
   RegisterTargetMachine<ARMLETargetMachine> A(getTheThumbLETarget());
   RegisterTargetMachine<ARMBETargetMachine> Y(getTheARMBETarget());
   RegisterTargetMachine<ARMBETargetMachine> B(getTheThumbBETarget());
 
   PassRegistry &Registry = *PassRegistry::getPassRegistry();
   initializeGlobalISel(Registry);
   initializeARMLoadStoreOptPass(Registry);
   initializeARMPreAllocLoadStoreOptPass(Registry);
   initializeARMConstantIslandsPass(Registry);
-  initializeARMExecutionDepsFixPass(Registry);
+  initializeARMExecutionDomainFixPass(Registry);
   initializeARMExpandPseudoPass(Registry);
   initializeThumb2SizeReducePass(Registry);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {
   if (TT.isOSBinFormatMachO())
     return llvm::make_unique<TargetLoweringObjectFileMachO>();
   if (TT.isOSWindows())
public:
   bool addLegalizeMachineIR() override;
   bool addRegBankSelect() override;
   bool addGlobalInstructionSelect() override;
   void addPreRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
 
-class ARMExecutionDepsFix : public ExecutionDepsFix {
+class ARMExecutionDomainFix : public ExecutionDomainFix {
 public:
   static char ID;
-  ARMExecutionDepsFix() : ExecutionDepsFix(ID, ARM::DPRRegClass) {}
+  ARMExecutionDomainFix() : ExecutionDomainFix(ID, ARM::DPRRegClass) {}
   StringRef getPassName() const override {
-    return "ARM Execution Dependency Fix";
+    return "ARM Execution Domain Fix";
   }
 };
-char ARMExecutionDepsFix::ID;
+char ARMExecutionDomainFix::ID;
 
 } // end anonymous namespace
 
-INITIALIZE_PASS(ARMExecutionDepsFix, "arm-execution-deps-fix",
-                "ARM Execution Dependency Fix", false, false)
+INITIALIZE_PASS_BEGIN(ARMExecutionDomainFix, "arm-execution-domain-fix",
+  "ARM Execution Domain Fix", false, false)
+INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
+INITIALIZE_PASS_END(ARMExecutionDomainFix, "arm-execution-domain-fix",
+  "ARM Execution Domain Fix", false, false)
 
 TargetPassConfig *ARMBaseTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new ARMPassConfig(*this, PM);
 }
 
 void ARMPassConfig::addIRPasses() {
   if (TM->Options.ThreadModel == ThreadModel::Single)
     addPass(createLowerAtomicPass());
void ARMPassConfig::addPreRegAlloc() {
   }
 }
 
 void ARMPassConfig::addPreSched2() {
   if (getOptLevel() != CodeGenOpt::None) {
     if (EnableARMLoadStoreOpt)
       addPass(createARMLoadStoreOptimizationPass());
 
-    addPass(new ARMExecutionDepsFix());
+    addPass(new ARMExecutionDomainFix());
+    addPass(new BreakFalseDeps());
   }
 
   // Expand some pseudo instructions into multiple instructions to allow
   // proper scheduling.
   addPass(createARMExpandPseudoPass());
 
   if (getOptLevel() != CodeGenOpt::None) {
     // in v8, IfConversion depends on Thumb instruction widths

llvm/trunk/lib/Target/X86/X86ISelLowering.cpp

if (!C)
     return SDValue();
   SDValue Scale = DAG.getTargetConstant(C->getZExtValue(), dl, MVT::i8);
   EVT MaskVT = Mask.getValueType();
   SDVTList VTs = DAG.getVTList(Op.getValueType(), MaskVT, MVT::Other);
   SDValue Disp = DAG.getTargetConstant(0, dl, MVT::i32);
   SDValue Segment = DAG.getRegister(0, MVT::i32);
   // If source is undef or we know it won't be used, use a zero vector
   // to break register dependency.
-  // TODO: use undef instead and let ExecutionDepsFix deal with it?
+  // TODO: use undef instead and let BreakFalseDeps deal with it?
   if (Src.isUndef() || ISD::isBuildVectorAllOnes(Mask.getNode()))
     Src = getZeroVector(Op.getSimpleValueType(), Subtarget, DAG, dl);
   SDValue Ops[] = {Src, Base, Scale, Index, Disp, Segment, Mask, Chain};
   SDNode *Res = DAG.getMachineNode(Opc, dl, VTs, Ops);
   SDValue RetOps[] = { SDValue(Res, 0), SDValue(Res, 2) };
   return DAG.getMergeValues(RetOps, dl);
 }
 
MVT MaskVT = MVT::getVectorVT(MVT::i1,
                              Index.getSimpleValueType().getVectorNumElements());
 
   SDValue VMask = getMaskNode(Mask, MaskVT, Subtarget, DAG, dl);
   SDVTList VTs = DAG.getVTList(Op.getValueType(), MaskVT, MVT::Other);
   SDValue Disp = DAG.getTargetConstant(0, dl, MVT::i32);
   SDValue Segment = DAG.getRegister(0, MVT::i32);
   // If source is undef or we know it won't be used, use a zero vector
   // to break register dependency.
-  // TODO: use undef instead and let ExecutionDepsFix deal with it?
+  // TODO: use undef instead and let BreakFalseDeps deal with it?
   if (Src.isUndef() || ISD::isBuildVectorAllOnes(VMask.getNode()))
     Src = getZeroVector(Op.getSimpleValueType(), Subtarget, DAG, dl);
   SDValue Ops[] = {Src, VMask, Base, Scale, Index, Disp, Segment, Chain};
   SDNode *Res = DAG.getMachineNode(Opc, dl, VTs, Ops);
   SDValue RetOps[] = { SDValue(Res, 0), SDValue(Res, 2) };
   return DAG.getMergeValues(RetOps, dl);
 }
 

llvm/trunk/lib/Target/X86/X86InstrAVX512.td

AVX512_maskable_custom<O, F, Outs, Ins,
                           [(set _.RC:$dst,
                                 (Select _.KRCWM:$mask, MaskedRHS,
                                         _.ImmAllZerosV))],
                           itin, "$src0 = $dst", IsCommutable>;
 
 
 // Alias instruction that maps zero vector to pxor / xorp* for AVX-512.
 // This is expanded by ExpandPostRAPseudos to an xorps / vxorps, and then
-// swizzled by ExecutionDepsFix to pxor.
+// swizzled by ExecutionDomainFix to pxor.
 // We set canFoldAsLoad because this can be converted to a constant-pool
 // load of an all-zeros value if folding it would be beneficial.
 let isReMaterializable = 1, isAsCheapAsAMove = 1, canFoldAsLoad = 1,
     isPseudo = 1, Predicates = [HasAVX512], SchedRW = [WriteZero] in {
 def AVX512_512_SET0 : I<0, Pseudo, (outs VR512:$dst), (ins), "",
                [(set VR512:$dst, (v16i32 immAllZerosV))]>;
 def AVX512_512_SETALLONES : I<0, Pseudo, (outs VR512:$dst), (ins), "",
                [(set VR512:$dst, (v16i32 immAllOnesV))]>;

llvm/trunk/lib/Target/X86/X86InstrInfo.cpp

static bool hasPartialRegUpdate(unsigned Opcode) {
   case X86::SQRTSDr_Int:
   case X86::SQRTSDm_Int:
     return true;
   }
 
   return false;
 }
 
-/// Inform the ExecutionDepsFix pass how many idle
+/// Inform the BreakFalseDeps pass how many idle
 /// instructions we would like before a partial register update.
 unsigned X86InstrInfo::getPartialRegUpdateClearance(
     const MachineInstr &MI, unsigned OpNum,
     const TargetRegisterInfo *TRI) const {
   if (OpNum != 0 || !hasPartialRegUpdate(MI.getOpcode()))
     return 0;
 
   // If MI is marked as reading Reg, the partial register update is wanted.
static bool hasUndefRegUpdate(unsigned Opcode) {
   case X86::VSQRTSDZm:
   case X86::VSQRTSDZm_Int:
     return true;
   }
 
   return false;
 }
 
-/// Inform the ExecutionDepsFix pass how many idle instructions we would like
+/// Inform the BreakFalseDeps pass how many idle instructions we would like
 /// before certain undef register reads.
 ///
 /// This catches the VCVTSI2SD family of instructions:
 ///
 /// vcvtsi2sdq %rax, undef %xmm0, %xmm14
 ///
 /// We should to be careful *not* to catch VXOR idioms which are presumably
 /// handled specially in the pipeline:

llvm/trunk/lib/Target/X86/X86InstrSSE.td

 }
 
 //===----------------------------------------------------------------------===//
 // AVX & SSE - Zero/One Vectors
 //===----------------------------------------------------------------------===//
 
 // Alias instruction that maps zero vector to pxor / xorp* for sse.
 // This is expanded by ExpandPostRAPseudos to an xorps / vxorps, and then
-// swizzled by ExecutionDepsFix to pxor.
+// swizzled by ExecutionDomainFix to pxor.
 // We set canFoldAsLoad because this can be converted to a constant-pool
 // load of an all-zeros value if folding it would be beneficial.
 let isReMaterializable = 1, isAsCheapAsAMove = 1, canFoldAsLoad = 1,
     isPseudo = 1, SchedRW = [WriteZero] in {
 def V_SET0 : I<0, Pseudo, (outs VR128:$dst), (ins), "",
                [(set VR128:$dst, (v4f32 immAllZerosV))]>;
 }
 
multiclass avx_fp_unop_s<bits<8> opc, string OpcodeStr, RegisterClass RC,
   // We don't want to fold scalar loads into these instructions unless
   // optimizing for size. This is because the folded instruction will have a
   // partial register update, while the unfolded sequence will not, e.g.
   // vmovss mem, %xmm0
   // vrcpss %xmm0, %xmm0, %xmm0
   // which has a clobber before the rcp, vs.
   // vrcpss mem, %xmm0, %xmm0
   // TODO: In theory, we could fold the load, and avoid the stall caused by
-  // the partial register store, either in ExecutionDepsFix or with smarter RA.
+  // the partial register store, either in BreakFalseDeps or with smarter RA.
   let Predicates = [target] in {
    def : Pat<(OpNode RC:$src),  (!cast<Instruction>("V"#NAME#Suffix##r)
                                 (ScalarVT (IMPLICIT_DEF)), RC:$src)>;
    def : Pat<(Intr VR128:$src),
              (!cast<Instruction>("V"#NAME#Suffix##r_Int) VR128:$src,
                                  VR128:$src)>;
   }
   let Predicates = [target, OptForSize] in {

llvm/trunk/lib/Target/X86/X86RegisterInfo.cpp

if (Is64Bit) {
     StackPtr = X86::ESP;
     FramePtr = X86::EBP;
     BasePtr = X86::ESI;
   }
 }
 
 bool
 X86RegisterInfo::trackLivenessAfterRegAlloc(const MachineFunction &MF) const {
-  // ExecutionDepsFixer and PostRAScheduler require liveness.
+  // ExecutionDomainFix, BreakFalseDeps and PostRAScheduler require liveness.
   return true;
 }
 
 int
 X86RegisterInfo::getSEHRegNum(unsigned i) const {
   return getEncodingValue(i);
 }
 

llvm/trunk/lib/Target/X86/X86TargetMachine.cpp

static cl::opt<bool> EnableMachineCombinerPass("x86-machine-combiner",
                                cl::init(true), cl::Hidden);
 
 namespace llvm {
 
 void initializeWinEHStatePassPass(PassRegistry &);
 void initializeFixupLEAPassPass(PassRegistry &);
 void initializeX86CallFrameOptimizationPass(PassRegistry &);
 void initializeX86CmovConverterPassPass(PassRegistry &);
-void initializeX86ExecutionDepsFixPass(PassRegistry &);
+void initializeX86ExecutionDomainFixPass(PassRegistry &);
 void initializeX86DomainReassignmentPass(PassRegistry &);
 
 } // end namespace llvm
 
 extern "C" void LLVMInitializeX86Target() {
   // Register the target.
   RegisterTargetMachine<X86TargetMachine> X(getTheX86_32Target());
   RegisterTargetMachine<X86TargetMachine> Y(getTheX86_64Target());
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   initializeGlobalISel(PR);
   initializeWinEHStatePassPass(PR);
   initializeFixupBWInstPassPass(PR);
   initializeEvexToVexInstPassPass(PR);
   initializeFixupLEAPassPass(PR);
   initializeX86CallFrameOptimizationPass(PR);
   initializeX86CmovConverterPassPass(PR);
-  initializeX86ExecutionDepsFixPass(PR);
+  initializeX86ExecutionDomainFixPass(PR);
   initializeX86DomainReassignmentPass(PR);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {
   if (TT.isOSBinFormatMachO()) {
     if (TT.getArch() == Triple::x86_64)
       return llvm::make_unique<X86_64MachoTargetObjectFile>();
     return llvm::make_unique<TargetLoweringObjectFileMachO>();
public:
   bool addPreISel() override;
   void addMachineSSAOptimization() override;
   void addPreRegAlloc() override;
   void addPostRegAlloc() override;
   void addPreEmitPass() override;
   void addPreSched2() override;
 };
 
-class X86ExecutionDepsFix : public ExecutionDepsFix {
+class X86ExecutionDomainFix : public ExecutionDomainFix {
 public:
   static char ID;
-  X86ExecutionDepsFix() : ExecutionDepsFix(ID, X86::VR128XRegClass) {}
+  X86ExecutionDomainFix() : ExecutionDomainFix(ID, X86::VR128XRegClass) {}
   StringRef getPassName() const override {
     return "X86 Execution Dependency Fix";
   }
 };
-char X86ExecutionDepsFix::ID;
+char X86ExecutionDomainFix::ID;
 
 } // end anonymous namespace
 
-INITIALIZE_PASS(X86ExecutionDepsFix, "x86-execution-deps-fix",
-                "X86 Execution Dependency Fix", false, false)
+INITIALIZE_PASS_BEGIN(X86ExecutionDomainFix, "x86-execution-domain-fix",
+  "X86 Execution Domain Fix", false, false)
+INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
+INITIALIZE_PASS_END(X86ExecutionDomainFix, "x86-execution-domain-fix",
+  "X86 Execution Domain Fix", false, false)
 
 TargetPassConfig *X86TargetMachine::createPassConfig(PassManagerBase &PM) {
   return new X86PassConfig(*this, PM);
 }
 
 void X86PassConfig::addIRPasses() {
   addPass(createAtomicExpandPass());
 

 
 void X86PassConfig::addPostRegAlloc() {
   addPass(createX86FloatingPointStackifierPass());
 }
 
 void X86PassConfig::addPreSched2() { addPass(createX86ExpandPseudoPass()); }
 
 void X86PassConfig::addPreEmitPass() {
-  if (getOptLevel() != CodeGenOpt::None)
-    addPass(new X86ExecutionDepsFix());
+  if (getOptLevel() != CodeGenOpt::None) {
+    addPass(new X86ExecutionDomainFix());
+    addPass(new BreakFalseDeps());
+  }
 
   addPass(createX86IndirectBranchTrackingPass());
 
   if (UseVZeroUpper)
     addPass(createX86IssueVZeroUpperPass());
 
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(createX86FixupBWInsts());
     addPass(createX86PadShortFunctions());
     addPass(createX86FixupLEAs());
     addPass(createX86EvexToVexInsts());
   }
 }

llvm/trunk/test/CodeGen/ARM/deps-fix.ll

 ; RUN: llc < %s -mcpu=cortex-a9 -mattr=+neon,+neonfp -float-abi=hard -mtriple armv7-linux-gnueabi | FileCheck %s
 
-;; This test checks that the ExecutionDepsFix pass performs the domain changes
+;; This test checks that the ExecutionDomainFix pass performs the domain changes
 ;; even when some dependencies are propagated through implicit definitions.
 
 ; CHECK: fun_a
 define <4 x float> @fun_a(<4 x float> %in, <4 x float> %x, float %y) nounwind {
 ; CHECK: vext
 ; CHECK: vext
 ; CHECK: vadd.f32
   %1 = insertelement <4 x float> %in, float %y, i32 0

llvm/trunk/test/CodeGen/X86/break-false-dep.ll

 
 declare float @llvm.sqrt.f32(float)
 declare double @llvm.sqrt.f64(double)
 
 ; SSE-LABEL: loopdep1
 ; SSE: for.body{{$}}
 ;
 ; This loop contains two cvtsi2ss instructions that update the same xmm
-; register.  Verify that the execution dependency fix pass breaks those
+; register.  Verify that the break false dependency fix pass breaks those
 ; dependencies by inserting xorps instructions.
 ;
 ; If the register allocator chooses different registers for the two cvtsi2ss
 ; instructions, they are still dependent on themselves.
 ; SSE: xorps [[XMM1:%xmm[0-9]+]]
 ; SSE: , [[XMM1]]
 ; SSE: cvtsi2ssl %{{.*}}, [[XMM1]]
 ; SSE: xorps [[XMM2:%xmm[0-9]+]]
loop:
   br i1 %exitcond, label %ret, label %loop
 ret:
   ret i64 %s2
 }
 
 ; This loop contains a cvtsi2sd instruction that has a loop-carried
 ; false dependency on an xmm that is modified by other scalar instructions
 ; that follow it in the loop. Additionally, the source of convert is a
-; memory operand. Verify the execution dependency fix pass breaks this
+; memory operand. Verify the break false dependency fix pass breaks this
 ; dependency by inserting a xor before the convert.
 @x = common global [1024 x double] zeroinitializer, align 16
 @y = common global [1024 x double] zeroinitializer, align 16
 @z = common global [1024 x double] zeroinitializer, align 16
 @w = common global [1024 x double] zeroinitializer, align 16
 @v = common global [1024 x i32] zeroinitializer, align 16
 
 define void @loopdep3() {