Separate LoopTraversal and BreakFalseDeps out of ExecutionDomainFix into their own files

[myatsina]

Summary

Separate LoopTraversal and BreakFalseDeps into their own files.
Moving a couple of comments around to make the new code more readable (i.e. LoopTraversal algorithm is now descirbed in the LoopTraversal header file and not in the traverse() method implementation)

This change is NFC.

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

Previous patches:
https://reviews.llvm.org/D40330
https://reviews.llvm.org/D40331
https://reviews.llvm.org/D40332

Next patches:
https://reviews.llvm.org/D40334

[javed.absar]

lib/CodeGen/BreakFalseDeps.cpp

60 ↗

(On Diff #123866)

You could consider changing this to range-loop by using predecessors()

[myatsina]

lib/CodeGen/BreakFalseDeps.cpp

60 ↗

(On Diff #123866)

I've addressed your comment in the first patch fix (https://reviews.llvm.org/D40330).
I think this change is more appropriate there.

[MatzeB]

Some comments on the software engineering side, I didn't really look into the dependency breaking algorithms yet.

include/llvm/CodeGen/BreakFalseDeps.h

36 ↗

(On Diff #123866)

This is probably a bad use of inheritance. Saying "BreakFalseDeps is a LoopTraversal" feels odd. I believe this could be rewritten so that LoopTraversal is subclassed separately inside BreakFalseDeps.cpp without making it a supertype of BreakFalseDeps itself.

82 ↗

(On Diff #123866)

It's usually easiest to just document the functions with /// doxygen comments instead of forming groups of methods.

If you really want to form groups, the correct doxygen syntax would be:

/// \name Dependency Breaking
/// \{
...
/// \}

include/llvm/CodeGen/LoopTraversal.h

12–39 ↗

(On Diff #123866)

• The comment (except for the first \file sentence) would better fit in front of class LoopTraversal.

• It's good to see an example trying to explain the goals of the algorithm!

• You can simplify the explanation by removing descriptions of how things are not done (i.e. the "it's not using the two-pass or naive worklist approaches" parts). Instead you should describe what actually is done: A reverse postorder traversal with an intertwined worklist algorithm for backedges.

51–67 ↗

(On Diff #123866)

This looks to me like these datastructures could be private.

73–81 ↗

(On Diff #123866)

This API seems too complicated to me. Given that this is just a loop traversal API I would expect that traverse() and runOnBasicBlock() is enough.

See also my comment inside runOnBasicBlock(); isBlockDone() can be private so it is not part of the API I believe.

lib/CodeGen/LoopTraversal.cpp

18–19 ↗

(On Diff #123866)

It is usually more convenient for users of the API if the doxygen comments are in the header; similar for following methods.

21–23 ↗

(On Diff #123866)

As far as I can see all three of enterBasicBlock(), processBasicBlock(), leaveBasicBlock() are always called together in this order. So it could just as well be a single function. In fact I believe just adding virtual to runOnBasicBlock() and removing the three other methods would suffice.

36 ↗

(On Diff #123866)

Using MachineBasicBlock & instead of auto & is friendlier to people reading the code.

45–48 ↗

(On Diff #123866)

You could simplify this to:

for (MachineBasicBlock *MBB : RPOT) {
   // ...
}

Same with the loop after this one.

63–71 ↗

(On Diff #123866)

Don't use {} for 1 line ifs.

78–80 ↗

(On Diff #123866)

Can you explain how this happens? Both loops appear to be using a RPO traversal, how could the first one miss some that this 2nd pass catches?

[MatzeB]

include/llvm/CodeGen/LoopTraversal.h

66 ↗

(On Diff #123866)

You can use a less expensive SmallVector<> or IndexedMap<> instead of a DenseMap by using the fact that machine basic blocks have a dense numbering. See for example MachineTraceMetrics::BlockInfo or LiveRangeCalc::Map for examples on how this is can be done.

[myatsina]

Hi,

Thanks for the comments!
My changes are mostly refactoring of the old ExecutionDepsDix pass in a way that is (almost*) NFC.
This pass combined the logic of both breaking false dependencies and execution domain adjustments in one single pass that traversed the basic blocks in a very special way (optimizing traversal of loops).
I think the first review (https://reviews.llvm.org/D40330) in this bunch would make everything clearer for you.

In order to fix the bugzilla 33869 I had to make a small adjustment for the breaking false dependencies part, but because all this logic was inter-twined I had to first separate it.
The new logic I've added is pretty much summarized here https://reviews.llvm.org/D40334.

*almost NFC - The logic I've changed in all this refactoring compared to the original ExecutionDepsFix is that I've enabled the "break false dependecy" part of the logic to run on all register classes, and not only the register class that ExecutionDepsFix received in its c'tor.

I will definitely adopt some of you refactoring suggestions and upload a patch soon.

Thanks,
Marina

include/llvm/CodeGen/BreakFalseDeps.h

36 ↗

(On Diff #123866)

Both BreakFalseDeps and ExecutionDomainFix traverse the basic blocks in a special way.
The LoopTraversal provides the traversal algorithm and methods that allow inheriting passes to handle instructions, handle BBs, etc.
Do you have a better suggestion on how to do it without duplicating the traversal logic in both passes?

82 ↗

(On Diff #123866)

Some of these methods are documented in the cpp file.
This is how they were originally documented when they were part of the ExecutionDepsFix pass.
Do you think we take this refactoring a a chance to move all method documentation to the header file?

include/llvm/CodeGen/LoopTraversal.h

12–39 ↗

(On Diff #123866)

I think that mentioning the naive approach and what we are trying to optimize is actually making this traversal algorithm (and the motivation for it) much clearer.
I can refactor the comment so that we have "The algorithm does ..." and at the end add a few sentences like "A naive way of implementing this would have been ..., but the downside of this is ..., this is why the optimized way was chosen", or something of that sort.
Do you think this way will be better?

73–81 ↗

(On Diff #123866)

I was trying to avoid duplicating runOnBasicBlock() logic for the inheriting classes.
It is not a lot of duplication, it basically just activates the other 3 methodes (enterBB, processBB, leaveBB) and that's it, so we can simplify the API as you suggested and have both inheriting class implement runOnBB the same way.

lib/CodeGen/LoopTraversal.cpp

18–19 ↗

(On Diff #123866)

Sure, I'll move them.
I've was trying to keep it close to what was in the original ExecutionDepsFix header and cpp..

21–23 ↗

(On Diff #123866)

I can definitely do that, just keep in mind that this way you will see some duplication because both inheriting classes will implement it the same way (calling their own private enterBB, processBB and leaveBB).

78–80 ↗

(On Diff #123866)

Keno Fischer (@loladiro ) is the author of this code in ExecutionDepsFix.
Keno, can you explain?

[MatzeB]

include/llvm/CodeGen/BreakFalseDeps.h

1–18 ↗

(On Diff #123866)

Is there a need to make the whole class public in a header? It feels to me like a FunctionPass *createFalseDependencyPass(); in include/llvm/CodeGen/Passes.h should be enough here so the class definition and all the details can remain in BreakFalseDeps.cpp.

36 ↗

(On Diff #123866)

Factoring out the common logic makes a lot of sense and is a good thing.

I was mainly wondering about using subclassing as a tool to get there.

In this case it could be as simple as a single function as the public interface:

void dominanceLoopTraversal(MachineFunction &MF,
                            std::function<void(MachineBasicBlock *, bool)> runOnBasicBlock);

For the implementation you could still use a class (in the .cpp file) if that feels easier:

class LoopTraversalImpl {
  std::function... runOnBasicBlock;
  LoopTraversalImpl(std::function... runOnBasicBlock) : runOnBasicBlock(runOnBasicBlock) {}
  // ...
  void traverse(MachineFunction &MF) { /* as existing */ }
};

void dominanceLoopTraversal(MachineFunction &MF,
                            std::function<void(MachineBasicBlock *, bool)> runOnBasicBlock) {
  LoopTraversalImpl Traversal(runOnBasicBlock);
  Traversal.traverse(MF);
}

82 ↗

(On Diff #123866)

Having the documentation for private methods in the cpp file is fine. But then I'd be consistent and not have something like // Instruction processing. here which looks like documentation about the function.

On the other hand I suppose the // LoopTraversal overrides. comment is about the 3 methods following the comment. It is at least not very typical to document 3 methods with a single comment, while easy in this case in general it probably won't be obvious what groups of methods a comment is meant for. That's why I was talking about the doxygen groups. (Though in this specific case I'd tend to just not have a comment...)

include/llvm/CodeGen/LoopTraversal.h

1 ↗

(On Diff #123866)

Could we move it to lib/CodeGen/LoopTraversal.h and keep the API private to CodeGen for now?

12–39 ↗

(On Diff #123866)

Yes that sounds good.

52 ↗

(On Diff #123866)

This should be /// Whether ... in doxygen syntax.

73–81 ↗

(On Diff #123866)

The downside of having 3 functions IMO is that splitting into 3 function is in no way motivated by the fact that this is a loop traversal algorithm. It's just a small convenience that happens to match the two existing users. The downside from splitting is that a reader of the code has to wonder when each of them gets called and at least I would intuititvely assume there to be complicated rules, while if there is only a single function it is quite obvious what will happen.

[myatsina]

I've uploaded a new review here and in https://reviews.llvm.org/D40330.

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.

Between review D40330 and this review of deparating the code to different files I did some refactoring which is NFC (changing data types, moving comments etc). If you want I can upload the refactoring for review as well.

[myatsina]

Ping

[myatsina]

Matthias, did you get a chance to look at these changes (and at the changes in https://reviews.llvm.org/D40330) ? Are you OK with them?

Thanks,
Marina

[MatzeB]

LGTM.

llvm/trunk/include/llvm/CodeGen/ExecutionDomainFix.h

-//==--- llvm/CodeGen/ExecutionDepsFix.h - Execution Domain Fix -*- C++ -*---==//
+//==-- llvm/CodeGen/ExecutionDomainFix.h - Execution Domain Fix -*- C++ -*--==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file Execution Domain Fix pass.
 ///
 /// Some X86 SSE instructions like mov, and, or, xor are available in different
 /// variants for different operand types. These variant instructions are
 /// equivalent, but on Nehalem and newer cpus there is extra latency
 /// transferring data between integer and floating point domains.  ARM cores
 /// have similar issues when they are configured with both VFP and NEON
 /// pipelines.
 ///
 /// This pass changes the variant instructions to minimize domain crossings.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_CODEGEN_EXECUTIONDEPSFIX_H
-#define LLVM_CODEGEN_EXECUTIONDEPSFIX_H
+#ifndef LLVM_CODEGEN_EXECUTIONDOMAINFIX_H
+#define LLVM_CODEGEN_EXECUTIONDOMAINFIX_H
 
-#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/iterator_range.h"
-#include "llvm/CodeGen/LivePhysRegs.h"
+#include "llvm/CodeGen/LoopTraversal.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/ReachingDefAnalysis.h"
+#include "llvm/CodeGen/TargetRegisterInfo.h"
 
 namespace llvm {
 
 class MachineBasicBlock;
 class MachineInstr;
 class TargetInstrInfo;
 
 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
struct DomainValue {
   /// Clear this DomainValue and point to next which has all its data.
   void clear() {
     AvailableDomains = 0;
     Next = nullptr;
     Instrs.clear();
   }
 };
 
-/// 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.
-///
-/// We want to visit every instruction in every basic block in order to update
-/// it's execution domain or collect clearance information. However, for the
-/// clearance calculation, we need to know clearances from all predecessors
-/// (including any backedges), therfore we need to visit some blocks twice.
-/// As an example, consider the following loop.
-///
-///
-///    PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
-///          ^                                  |
-///          +----------------------------------+
-///
-/// The iteration order this pass will return is as follows:
-/// Optimized: PH A B C A' B' C' D
-///
-/// The basic block order is constructed as follows:
-/// Once we finish processing some block, we update the counters in MBBInfos
-/// and re-process any successors that are now 'done'.
-/// We call a block that is ready for its final round of processing `done`
-/// (isBlockDone), e.g. when all predecessor information is known.
-///
-/// Note that a naive traversal order would be to do two complete passes over
-/// all basic blocks/instructions, the first for recording clearances, the
-/// second for updating clearance based on backedges.
-/// However, for functions without backedges, or functions with a lot of
-/// straight-line code, and a small loop, that would be a lot of unnecessary
-/// work (since only the BBs that are part of the loop require two passes).
-///
-/// E.g., the naive iteration order for the above exmple is as follows:
-/// Naive: PH A B C D A' B' C' D'
-///
-/// In the optimized approach we avoid processing D twice, because we
-/// can entirely process the predecessors before getting to D.
-class LoopTraversal {
-private:
-  struct MBBInfo {
-    /// 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 = SmallVector<MBBInfo, 4>;
-  /// Helps keep track if we proccessed this block and all its predecessors.
-  MBBInfoMap MBBInfos;
-
-public:
-  struct TraversedMBBInfo {
-    /// The basic block.
-    MachineBasicBlock *MBB = nullptr;
-
-    /// True if this is the first time we process the basic block.
-    bool PrimaryPass = true;
-
-    /// True if the block that is ready for its final round of processing.
-    bool IsDone = true;
-
-    TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true,
-                     bool Done = true)
-        : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
-  };
-  LoopTraversal() {}
-
-  /// \brief Identifies basic blocks that are part of loops and should to be
-  ///  visited twise and returns efficient traversal order for all the blocks.
-  typedef SmallVector<TraversedMBBInfo, 4> TraversalOrder;
-  TraversalOrder traverse(MachineFunction &MF);
-
-private:
-  /// Returens true if the block is ready for its final round of processing.
-  bool isBlockDone(MachineBasicBlock *MBB);
-};
-
-/// This class provides the reaching def analysis.
-class ReachingDefAnalysis : public MachineFunctionPass {
-private:
-  MachineFunction *MF;
-  const TargetInstrInfo *TII;
-  const TargetRegisterInfo *TRI;
-  unsigned NumRegUnits;
-  /// Instruction that defined each register, relative to the beginning of the
-  /// current basic block.  When a LiveRegsDefInfo 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.
-  using LiveRegsDefInfo = std::vector<int>;
-  LiveRegsDefInfo 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 = SmallVector<LiveRegsDefInfo, 4>;
-  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;
-
-  /// Default values are 'nothing happened a long time ago'.
-  const int ReachingDedDefaultVal = -(1 << 20);
-
-public:
-  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:
-  /// Set up LiveRegs by merging predecessor live-out values.
-  void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
-
-  /// Update live-out values.
-  void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
-
-  /// Process he given basic block.
-  void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
-
-  /// Update def-ages for registers defined by MI.
-  /// Also break dependencies on partial defs and undef uses.
-  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;
private:
   /// A soft instruction can be changed to work in other domains given by mask.
   void visitSoftInstr(MachineInstr *, unsigned mask);
 
   /// A hard instruction only works in one domain. All input registers will be
   /// forced into that domain.
   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:
-  /// Process he given basic block.
-  void processBasicBlock(MachineBasicBlock *MBB);
-
-  /// Update def-ages for registers defined by MI.
-  /// Also break dependencies on partial defs and undef uses.
-  void processDefs(MachineInstr *MI);
-
-  /// \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 pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
-                                unsigned Pref);
-
-  /// \brief Return true to if it makes sense to break dependence on a partial
-  /// def or undef use.
-  bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);
-
-  /// \brief 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 processUndefReads(MachineBasicBlock *);
-};
-
 } // namespace llvm
 
-#endif // LLVM_CODEGEN_EXECUTIONDEPSFIX_H
+#endif // LLVM_CODEGEN_EXECUTIONDOMAINFIX_H

llvm/trunk/include/llvm/CodeGen/LoopTraversal.h

+//==------ llvm/CodeGen/LoopTraversal.h - Loop Traversal -*- C++ -*---------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file Loop Traversal logic.
+///
+/// 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.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_LOOPTRAVERSAL_H
+#define LLVM_CODEGEN_LOOPTRAVERSAL_H
+
+#include "llvm/ADT/SmallVector.h"
+
+namespace llvm {
+
+class MachineBasicBlock;
+class MachineFunction;
+
+/// 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.
+///
+/// We want to visit every instruction in every basic block in order to update
+/// it's execution domain or collect clearance information. However, for the
+/// clearance calculation, we need to know clearances from all predecessors
+/// (including any backedges), therfore we need to visit some blocks twice.
+/// As an example, consider the following loop.
+///
+///
+///    PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
+///          ^                                  |
+///          +----------------------------------+
+///
+/// The iteration order this pass will return is as follows:
+/// Optimized: PH A B C A' B' C' D
+///
+/// The basic block order is constructed as follows:
+/// Once we finish processing some block, we update the counters in MBBInfos
+/// and re-process any successors that are now 'done'.
+/// We call a block that is ready for its final round of processing `done`
+/// (isBlockDone), e.g. when all predecessor information is known.
+///
+/// Note that a naive traversal order would be to do two complete passes over
+/// all basic blocks/instructions, the first for recording clearances, the
+/// second for updating clearance based on backedges.
+/// However, for functions without backedges, or functions with a lot of
+/// straight-line code, and a small loop, that would be a lot of unnecessary
+/// work (since only the BBs that are part of the loop require two passes).
+///
+/// E.g., the naive iteration order for the above exmple is as follows:
+/// Naive: PH A B C D A' B' C' D'
+///
+/// In the optimized approach we avoid processing D twice, because we
+/// can entirely process the predecessors before getting to D.
+class LoopTraversal {
+private:
+  struct MBBInfo {
+    /// 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 = SmallVector<MBBInfo, 4>;
+  /// Helps keep track if we proccessed this block and all its predecessors.
+  MBBInfoMap MBBInfos;
+
+public:
+  struct TraversedMBBInfo {
+    /// The basic block.
+    MachineBasicBlock *MBB = nullptr;
+
+    /// True if this is the first time we process the basic block.
+    bool PrimaryPass = true;
+
+    /// True if the block that is ready for its final round of processing.
+    bool IsDone = true;
+
+    TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true,
+                     bool Done = true)
+        : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
+  };
+  LoopTraversal() {}
+
+  /// \brief Identifies basic blocks that are part of loops and should to be
+  ///  visited twice and returns efficient traversal order for all the blocks.
+  typedef SmallVector<TraversedMBBInfo, 4> TraversalOrder;
+  TraversalOrder traverse(MachineFunction &MF);
+
+private:
+  /// Returens true if the block is ready for its final round of processing.
+  bool isBlockDone(MachineBasicBlock *MBB);
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_LOOPTRAVERSAL_H

llvm/trunk/include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
 
   /// This pass expands the experimental reduction intrinsics into sequences of
   /// shuffles.
   FunctionPass *createExpandReductionsPass();
 
   // This pass expands memcmp() to load/stores.
   FunctionPass *createExpandMemCmpPass();
 
+  /// Creates Break False Dependencies pass. \see BreakFalseDeps.cpp
+  FunctionPass *createBreakFalseDeps();
+
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/CodeGen/ReachingDefAnalysis.h

+//==--- llvm/CodeGen/ReachingDefAnalysis.h - Reaching Def Analysis -*- C++ -*---==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file Reaching Defs Analysis pass.
+///
+/// This pass tracks for each instruction what is the “closest” reaching def of
+/// a given register. It is used by BreakFalseDeps (for clearance calculation)
+/// and ExecutionDomainFix (for arbitrating conflicting domains).
+///
+/// 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.
+///
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
+#define LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/LoopTraversal.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+
+class MachineBasicBlock;
+class MachineInstr;
+
+/// This class provides the reaching def analysis.
+class ReachingDefAnalysis : public MachineFunctionPass {
+private:
+  MachineFunction *MF;
+  const TargetRegisterInfo *TRI;
+  unsigned NumRegUnits;
+  /// Instruction that defined each register, relative to the beginning of the
+  /// current basic block.  When a LiveRegsDefInfo 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.
+  using LiveRegsDefInfo = std::vector<int>;
+  LiveRegsDefInfo 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 = SmallVector<LiveRegsDefInfo, 4>;
+  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;
+
+  /// Default values are 'nothing happened a long time ago'.
+  const int ReachingDedDefaultVal = -(1 << 20);
+
+public:
+  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:
+  /// Set up LiveRegs by merging predecessor live-out values.
+  void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+
+  /// Update live-out values.
+  void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+
+  /// Process he given basic block.
+  void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
+
+  /// Update def-ages for registers defined by MI.
+  /// Also break dependencies on partial defs and undef uses.
+  void processDefs(MachineInstr *);
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H

llvm/trunk/lib/CodeGen/BreakFalseDeps.cpp

+//==- llvm/CodeGen/BreakFalseDeps.cpp - Break False Dependency Fix -*- C++ -*==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file Break False Dependency pass.
+///
+/// Some instructions have false dependencies which cause unnecessary stalls.
+/// For exmaple, instructions that only write part of a register, and implicitly
+/// need to read the other parts of the register.  This may cause unwanted
+/// stalls preventing otherwise unrelated instructions from executing in
+/// parallel in an out-of-order CPU.
+/// This pass is aimed at identifying and avoiding these depepndencies when
+/// possible.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/LivePhysRegs.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/ReachingDefAnalysis.h"
+#include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+
+
+using namespace llvm;
+
+namespace llvm {
+
+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:
+  /// Process he given basic block.
+  void processBasicBlock(MachineBasicBlock *MBB);
+
+  /// Update def-ages for registers defined by MI.
+  /// Also break dependencies on partial defs and undef uses.
+  void processDefs(MachineInstr *MI);
+
+  /// \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 pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
+    unsigned Pref);
+
+  /// \brief Return true to if it makes sense to break dependence on a partial
+  /// def or undef use.
+  bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);
+
+  /// \brief 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 processUndefReads(MachineBasicBlock *);
+};
+
+} // namespace llvm
+
+#define DEBUG_TYPE "break-false-deps"
+
+char BreakFalseDeps::ID = 0;
+INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
+INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
+INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
+
+FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }
+
+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 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 (MCPhysReg Reg : Order) {
+    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;
+}
+
+bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
+  unsigned Pref) {
+  unsigned reg = MI->getOperand(OpIdx).getReg();
+  unsigned Clearance = RDA->getClearance(MI, reg);
+  DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
+
+  if (Pref > Clearance) {
+    DEBUG(dbgs() << ": Break dependency.\n");
+    return true;
+  }
+  DEBUG(dbgs() << ": OK .\n");
+  return false;
+}
+
+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;
+  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() || !MO.getReg())
+      continue;
+    if (MO.isUse())
+      continue;
+    // Check clearance before partial register updates.
+    unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
+    if (Pref && shouldBreakDependence(MI, i, Pref))
+      TII->breakPartialRegDependency(*MI, i, TRI);
+  }
+}
+
+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);
+
+  MachineInstr *UndefMI = UndefReads.back().first;
+  unsigned OpIdx = UndefReads.back().second;
+
+  for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
+    // Update liveness, including the current instruction's defs.
+    LiveRegSet.stepBackward(I);
+
+    if (UndefMI == &I) {
+      if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
+        TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
+
+      UndefReads.pop_back();
+      if (UndefReads.empty())
+        return;
+
+      UndefMI = UndefReads.back().first;
+      OpIdx = UndefReads.back().second;
+    }
+  }
+}
+
+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);
+  }
+  processUndefReads(MBB);
+}
+
+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;
+}

llvm/trunk/lib/CodeGen/CMakeLists.txt

 add_llvm_library(LLVMCodeGen
   AggressiveAntiDepBreaker.cpp
   AllocationOrder.cpp
   Analysis.cpp
   AtomicExpandPass.cpp
   BasicTargetTransformInfo.cpp
   BranchFolding.cpp
   BranchRelaxation.cpp
+  BreakFalseDeps.cpp
   BuiltinGCs.cpp
   CalcSpillWeights.cpp
   CallingConvLower.cpp
   CodeGen.cpp
   CodeGenPrepare.cpp
   CriticalAntiDepBreaker.cpp
   DeadMachineInstructionElim.cpp
   DetectDeadLanes.cpp
add_llvm_library(LLVMCodeGen
   LiveRangeEdit.cpp
   LiveRangeShrink.cpp
   LiveRegMatrix.cpp
   LiveRegUnits.cpp
   LiveStacks.cpp
   LiveVariables.cpp
   LLVMTargetMachine.cpp
   LocalStackSlotAllocation.cpp
+  LoopTraversal.cpp
   LowLevelType.cpp
   LowerEmuTLS.cpp
   MachineBasicBlock.cpp
   MachineBlockFrequencyInfo.cpp
   MachineBlockPlacement.cpp
   MachineBranchProbabilityInfo.cpp
   MachineCombiner.cpp
   MachineCopyPropagation.cpp
add_llvm_library(LLVMCodeGen
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   PostRAHazardRecognizer.cpp
   PostRASchedulerList.cpp
   PreISelIntrinsicLowering.cpp
   ProcessImplicitDefs.cpp
   PrologEpilogInserter.cpp
   PseudoSourceValue.cpp
+  ReachingDefAnalysis.cpp
   RegAllocBase.cpp
   RegAllocBasic.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp

llvm/trunk/lib/CodeGen/ExecutionDomainFix.cpp

-//===- ExecutionDepsFix.cpp - Fix execution domain issues ----*- C++ -*-===//
+//===- ExecutionDomainFix.cpp - Fix execution domain issues ----*- C++ -*--===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/ExecutionDomainFix.h"
-#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.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)
-
 iterator_range<SmallVectorImpl<int>::const_iterator>
 ExecutionDomainFix::regIndices(unsigned Reg) const {
   assert(Reg < AliasMap.size() && "Invalid register");
   const auto &Entry = AliasMap[Reg];
   return make_range(Entry.begin(), Entry.end());
 }
 
 DomainValue *ExecutionDomainFix::alloc(int domain) {
bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
   for (unsigned rx = 0; rx != NumRegs; ++rx) {
     assert(!LiveRegs.empty() && "no space allocated for live registers");
     if (LiveRegs[rx] == B)
       setLiveReg(rx, A);
   }
   return true;
 }
 
-void ReachingDefAnalysis::enterBasicBlock(
-    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
-
-  MachineBasicBlock *MBB = TraversedMBB.MBB;
-  int MBBNumber = MBB->getNumber();
-  assert(MBBNumber < MBBReachingDefs.size() &&
-         "Unexpected basic block number.");
-  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
-
-  // Reset instruction counter in each basic block.
-  CurInstr = 0;
-
-  // Set up LiveRegs to represent registers entering MBB.
-  // Default values are 'nothing happened a long time ago'.
-  if (LiveRegs.empty())
-    LiveRegs.assign(NumRegUnits, ReachingDedDefaultVal);
-
-  // This is the entry block.
-  if (MBB->pred_empty()) {
-    for (const auto &LI : MBB->liveins()) {
-      for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
-        // 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[*Unit] = -1;
-        MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
-      }
-    }
-    DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
-    return;
-  }
-
-  // Try to coalesce live-out registers from predecessors.
-  for (MachineBasicBlock *pred : MBB->predecessors()) {
-    assert(pred->getNumber() < MBBOutRegsInfos.size() &&
-           "Should have pre-allocated MBBInfos for all MBBs");
-    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
-    // Incoming is null if this is a backedge from a BB
-    // we haven't processed yet
-    if (Incoming.empty())
-      continue;
-
-    for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
-      // Use the most recent predecessor def for each register.
-      LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
-      if ((LiveRegs[Unit] != ReachingDedDefaultVal))
-        MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
-    }
-  }
-
-  DEBUG(dbgs() << printMBBReference(*MBB)
-               << (!TraversedMBB.IsDone ? ": incomplete\n"
-                                        : ": all preds known\n"));
-}
-
 void ExecutionDomainFix::enterBasicBlock(
     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
 
   MachineBasicBlock *MBB = TraversedMBB.MBB;
 
   // Set up LiveRegs to represent registers entering MBB.
   // Set default domain values to 'no domain' (nullptr)
   if (LiveRegs.empty())
for (unsigned rx = 0; rx != NumRegs; ++rx) {
         force(rx, pdv->getFirstDomain());
     }
   }
   DEBUG(dbgs() << printMBBReference(*MBB)
                << (!TraversedMBB.IsDone ? ": incomplete\n"
                                         : ": all preds known\n"));
 }
 
-void ReachingDefAnalysis::leaveBasicBlock(
-    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
-  assert(!LiveRegs.empty() && "Must enter basic block first.");
-  int MBBNumber = TraversedMBB.MBB->getNumber();
-  assert(MBBNumber < MBBOutRegsInfos.size() &&
-         "Unexpected basic block number.");
-  // Save register clearances at end of MBB - used by enterBasicBlock().
-  MBBOutRegsInfos[MBBNumber] = 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 (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
-    OutLiveReg -= CurInstr;
-  LiveRegs.clear();
-}
-
 void ExecutionDomainFix::leaveBasicBlock(
     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
   assert(!LiveRegs.empty() && "Must enter basic block first.");
   int MBBNumber = TraversedMBB.MBB->getNumber();
   assert(MBBNumber < MBBOutRegsInfos.size() &&
          "Unexpected basic block number.");
   // Save register clearances at end of MBB - used by enterBasicBlock().
   for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
if (DomP.second)
       visitSoftInstr(MI, DomP.second);
     else
       visitHardInstr(MI, DomP.first);
   }
 
   return !DomP.first;
 }
 
-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 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 (MCPhysReg Reg : Order) {
-    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;
-}
-
-bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
-                                           unsigned Pref) {
-  unsigned reg = MI->getOperand(OpIdx).getReg();
-  unsigned Clearance = RDA->getClearance(MI, reg);
-  DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
-
-  if (Pref > Clearance) {
-    DEBUG(dbgs() << ": Break dependency.\n");
-    return true;
-  }
-  DEBUG(dbgs() << ": OK .\n");
-  return false;
-}
-
 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);
     }
   }
 }
 
-void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
-  assert(!MI->isDebugValue() && "Won't process debug values");
-
-  int MBBNumber = MI->getParent()->getNumber();
-  assert(MBBNumber < MBBReachingDefs.size() &&
-         "Unexpected basic block number.");
-  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 Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
-      // This instruction explicitly defines the current reg unit.
-      DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr << '\t'
-                   << *MI);
-
-      // How many instructions since this reg unit was last written?
-      LiveRegs[*Unit] = CurInstr;
-      MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
-    }
-  }
-  InstIds[MI] = CurInstr;
-  ++CurInstr;
-}
-
-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;
-  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() || !MO.getReg())
-      continue;
-    if (MO.isUse())
-      continue;
-    // Check clearance before partial register updates.
-    unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
-    if (Pref && shouldBreakDependence(MI, i, Pref))
-      TII->breakPartialRegDependency(*MI, i, TRI);
-  }
-}
-
-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);
-
-  MachineInstr *UndefMI = UndefReads.back().first;
-  unsigned OpIdx = UndefReads.back().second;
-
-  for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
-    // Update liveness, including the current instruction's defs.
-    LiveRegSet.stepBackward(I);
-
-    if (UndefMI == &I) {
-      if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
-        TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
-
-      UndefReads.pop_back();
-      if (UndefReads.empty())
-        return;
-
-      UndefMI = UndefReads.back().first;
-      OpIdx = UndefReads.back().second;
-    }
-  }
-}
-
 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;
if (!MI.isDebugValue()) {
       if (TraversedMBB.PrimaryPass)
         Kill = visitInstr(&MI);
       processDefs(&MI, Kill);
     }
   }
   leaveBasicBlock(TraversedMBB);
 }
 
-void ReachingDefAnalysis::processBasicBlock(
-    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
-  enterBasicBlock(TraversedMBB);
-  for (MachineInstr &MI : *TraversedMBB.MBB) {
-    if (!MI.isDebugValue())
-      processDefs(&MI);
-  }
-  leaveBasicBlock(TraversedMBB);
-}
-
-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);
-  }
-  processUndefReads(MBB);
-}
-
-bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
-  int MBBNumber = MBB->getNumber();
-  assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
-  return MBBInfos[MBBNumber].PrimaryCompleted &&
-         MBBInfos[MBBNumber].IncomingCompleted ==
-             MBBInfos[MBBNumber].PrimaryIncoming &&
-         MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size();
-}
-
-LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {
-  // Initialize the MMBInfos
-  MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo());
-
-  MachineBasicBlock *Entry = &*MF.begin();
-  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(Entry);
-  SmallVector<MachineBasicBlock *, 4> Workqueue;
-  SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder;
-  for (MachineBasicBlock *MBB : RPOT) {
-    // N.B: IncomingProcessed and IncomingCompleted were already updated while
-    // processing this block's predecessors.
-    int MBBNumber = MBB->getNumber();
-    assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
-    MBBInfos[MBBNumber].PrimaryCompleted = true;
-    MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
-    bool Primary = true;
-    Workqueue.push_back(MBB);
-    while (!Workqueue.empty()) {
-      MachineBasicBlock *ActiveMBB = &*Workqueue.back();
-      Workqueue.pop_back();
-      bool Done = isBlockDone(ActiveMBB);
-      MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
-      for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
-        int SuccNumber = Succ->getNumber();
-        assert(SuccNumber < MBBInfos.size() &&
-               "Unexpected basic block number.");
-        if (!isBlockDone(Succ)) {
-          if (Primary)
-            MBBInfos[SuccNumber].IncomingProcessed++;
-          if (Done)
-            MBBInfos[SuccNumber].IncomingCompleted++;
-          if (isBlockDone(Succ))
-            Workqueue.push_back(Succ);
-        }
-      }
-      Primary = false;
-    }
-  }
-
-  // We need to go through again and finalize any blocks that are not done yet.
-  // This is possible if blocks have dead predecessors, so we didn't visit them
-  // above.
-  for (MachineBasicBlock *MBB : RPOT) {
-    if (!isBlockDone(MBB))
-      MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
-    // Don't update successors here. We'll get to them anyway through this
-    // loop.
-  }
-
-  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.clear();
   assert(NumRegs == RC->getNumRegs() && "Bad regclass");
for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
     }
   }
   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.clear();
-  NumRegUnits = TRI->getNumRegUnits();
-
-  MBBReachingDefs.resize(mf.getNumBlockIDs());
-
-  DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
-
-  // Initialize the MBBOutRegsInfos
-  MBBOutRegsInfos.resize(mf.getNumBlockIDs());
-
-  // Traverse the basic blocks.
-  LoopTraversal Traversal;
-  LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
-  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
-    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 internal vectors.
-  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) {
-  assert(InstIds.count(MI) && "Unexpected machine instuction.");
-  int InstId = InstIds[MI];
-  int DefRes = ReachingDedDefaultVal;
-  int MBBNumber = MI->getParent()->getNumber();
-  assert(MBBNumber < MBBReachingDefs.size() &&
-         "Unexpected basic block number.");
-  int LatestDef = ReachingDedDefaultVal;
-  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) {
-  assert(InstIds.count(MI) && "Unexpected machine instuction.");
-  return InstIds[MI] - getReachingDef(MI, PhysReg);
-}

llvm/trunk/lib/CodeGen/LoopTraversal.cpp

+//===- LoopTraversal.cpp - Optimal basic block traversal order --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/LoopTraversal.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/CodeGen/MachineFunction.h"
+
+using namespace llvm;
+
+bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
+  int MBBNumber = MBB->getNumber();
+  assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
+  return MBBInfos[MBBNumber].PrimaryCompleted &&
+         MBBInfos[MBBNumber].IncomingCompleted ==
+             MBBInfos[MBBNumber].PrimaryIncoming &&
+         MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size();
+}
+
+LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {
+  // Initialize the MMBInfos
+  MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo());
+
+  MachineBasicBlock *Entry = &*MF.begin();
+  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(Entry);
+  SmallVector<MachineBasicBlock *, 4> Workqueue;
+  SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder;
+  for (MachineBasicBlock *MBB : RPOT) {
+    // N.B: IncomingProcessed and IncomingCompleted were already updated while
+    // processing this block's predecessors.
+    int MBBNumber = MBB->getNumber();
+    assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
+    MBBInfos[MBBNumber].PrimaryCompleted = true;
+    MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
+    bool Primary = true;
+    Workqueue.push_back(MBB);
+    while (!Workqueue.empty()) {
+      MachineBasicBlock *ActiveMBB = &*Workqueue.back();
+      Workqueue.pop_back();
+      bool Done = isBlockDone(ActiveMBB);
+      MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
+      for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
+        int SuccNumber = Succ->getNumber();
+        assert(SuccNumber < MBBInfos.size() &&
+               "Unexpected basic block number.");
+        if (!isBlockDone(Succ)) {
+          if (Primary)
+            MBBInfos[SuccNumber].IncomingProcessed++;
+          if (Done)
+            MBBInfos[SuccNumber].IncomingCompleted++;
+          if (isBlockDone(Succ))
+            Workqueue.push_back(Succ);
+        }
+      }
+      Primary = false;
+    }
+  }
+
+  // We need to go through again and finalize any blocks that are not done yet.
+  // This is possible if blocks have dead predecessors, so we didn't visit them
+  // above.
+  for (MachineBasicBlock *MBB : RPOT) {
+    if (!isBlockDone(MBB))
+      MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
+    // Don't update successors here. We'll get to them anyway through this
+    // loop.
+  }
+
+  MBBInfos.clear();
+
+  return MBBTraversalOrder;
+}

llvm/trunk/lib/CodeGen/ReachingDefAnalysis.cpp

+//===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ReachingDefAnalysis.h"
+#include "llvm/CodeGen/TargetRegisterInfo.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "reaching-deps-analysis"
+
+char ReachingDefAnalysis::ID = 0;
+INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
+                true)
+
+void ReachingDefAnalysis::enterBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+
+  MachineBasicBlock *MBB = TraversedMBB.MBB;
+  int MBBNumber = MBB->getNumber();
+  assert(MBBNumber < MBBReachingDefs.size() &&
+         "Unexpected basic block number.");
+  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
+
+  // Reset instruction counter in each basic block.
+  CurInstr = 0;
+
+  // Set up LiveRegs to represent registers entering MBB.
+  // Default values are 'nothing happened a long time ago'.
+  if (LiveRegs.empty())
+    LiveRegs.assign(NumRegUnits, ReachingDedDefaultVal);
+
+  // This is the entry block.
+  if (MBB->pred_empty()) {
+    for (const auto &LI : MBB->liveins()) {
+      for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
+        // 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[*Unit] = -1;
+        MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
+      }
+    }
+    DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
+    return;
+  }
+
+  // Try to coalesce live-out registers from predecessors.
+  for (MachineBasicBlock *pred : MBB->predecessors()) {
+    assert(pred->getNumber() < MBBOutRegsInfos.size() &&
+           "Should have pre-allocated MBBInfos for all MBBs");
+    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
+    // Incoming is null if this is a backedge from a BB
+    // we haven't processed yet
+    if (Incoming.empty())
+      continue;
+
+    for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
+      // Use the most recent predecessor def for each register.
+      LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
+      if ((LiveRegs[Unit] != ReachingDedDefaultVal))
+        MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
+    }
+  }
+
+  DEBUG(dbgs() << printMBBReference(*MBB)
+               << (!TraversedMBB.IsDone ? ": incomplete\n"
+                                        : ": all preds known\n"));
+}
+
+void ReachingDefAnalysis::leaveBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+  assert(!LiveRegs.empty() && "Must enter basic block first.");
+  int MBBNumber = TraversedMBB.MBB->getNumber();
+  assert(MBBNumber < MBBOutRegsInfos.size() &&
+         "Unexpected basic block number.");
+  // Save register clearances at end of MBB - used by enterBasicBlock().
+  MBBOutRegsInfos[MBBNumber] = 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 (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
+    OutLiveReg -= CurInstr;
+  LiveRegs.clear();
+}
+
+void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
+  assert(!MI->isDebugValue() && "Won't process debug values");
+
+  int MBBNumber = MI->getParent()->getNumber();
+  assert(MBBNumber < MBBReachingDefs.size() &&
+         "Unexpected basic block number.");
+  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 Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
+      // This instruction explicitly defines the current reg unit.
+      DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr << '\t'
+                   << *MI);
+
+      // How many instructions since this reg unit was last written?
+      LiveRegs[*Unit] = CurInstr;
+      MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
+    }
+  }
+  InstIds[MI] = CurInstr;
+  ++CurInstr;
+}
+
+void ReachingDefAnalysis::processBasicBlock(
+    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
+  enterBasicBlock(TraversedMBB);
+  for (MachineInstr &MI : *TraversedMBB.MBB) {
+    if (!MI.isDebugValue())
+      processDefs(&MI);
+  }
+  leaveBasicBlock(TraversedMBB);
+}
+
+bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
+  if (skipFunction(mf.getFunction()))
+    return false;
+  MF = &mf;
+  TRI = MF->getSubtarget().getRegisterInfo();
+
+  LiveRegs.clear();
+  NumRegUnits = TRI->getNumRegUnits();
+
+  MBBReachingDefs.resize(mf.getNumBlockIDs());
+
+  DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
+
+  // Initialize the MBBOutRegsInfos
+  MBBOutRegsInfos.resize(mf.getNumBlockIDs());
+
+  // Traverse the basic blocks.
+  LoopTraversal Traversal;
+  LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
+  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
+    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 internal vectors.
+  MBBOutRegsInfos.clear();
+  MBBReachingDefs.clear();
+  InstIds.clear();
+}
+
+int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
+  assert(InstIds.count(MI) && "Unexpected machine instuction.");
+  int InstId = InstIds[MI];
+  int DefRes = ReachingDedDefaultVal;
+  int MBBNumber = MI->getParent()->getNumber();
+  assert(MBBNumber < MBBReachingDefs.size() &&
+         "Unexpected basic block number.");
+  int LatestDef = ReachingDedDefaultVal;
+  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) {
+  assert(InstIds.count(MI) && "Unexpected machine instuction.");
+  return InstIds[MI] - getReachingDef(MI, PhysReg);
+}

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

 }
 
 void ARMPassConfig::addPreSched2() {
   if (getOptLevel() != CodeGenOpt::None) {
     if (EnableARMLoadStoreOpt)
       addPass(createARMLoadStoreOptimizationPass());
 
     addPass(new ARMExecutionDomainFix());
-    addPass(new BreakFalseDeps());
+    addPass(createBreakFalseDeps());
   }
 
   // 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/X86TargetMachine.cpp

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