[MachineCombiner] Update instruction depths incrementally for large BBs.

[fhahn]

Summary

For large basic blocks with lots of combinable instructions, the
MachineTraceMetrics computations in MachineCombiner can dominate the compile
time, as computing the trace information is quadratic in the number of
instructions in a BB and it's relevant successors/predecessors.

In most cases, knowing the instruction depth should be enough to make
combination decisions. As we already iterate over all instructions in a basic
block, the instruction depth can be computed incrementally. This reduces the
cost of machine-combine drastically in cases where lots of instructions
are combined. The major drawback is that AFAIK, computing the critical path
length cannot be done incrementally. Therefore we only compute
instruction depths incrementally, for basic blocks with more
instructions than inc_threshold. The -machine-combiner-inc-threshold
option can be used to set the threshold and allows for easier
experimenting and checking if using incremental updates for all basic
blocks has any impact on the performance.

[efriedma]

For reference, I also ran into this problem at one point, and came up with a hack to just turn off trace-based optimizations for long basic blocks. This implementation looks nicer. :)

[fhahn]

Thanks for your feedback Eli. I've update the patch to only use incremental updates if the size of a BB is over a certain threshold. I've chosen 500 instructions for now, but a slightly higher one would probably be OK too.

I've also updated the patch to take the LiveRegUnits into account when doing incremental updates. Also, the code to compute the incremental info is only executed if we found viable patterns.

[fhahn]

ping

[Gerolf]

Hi Florian

This looks promising! Thanks for working on this nagging problem spot. More out of curiosity: Could you also share the data for your compile-time improvements?

Cheers
Gerolf

lib/CodeGen/MachineCombiner.cpp

273–274

What happened to the comment?

289

SlackIsAccurate is checked twice for OldCycleCount?! I think the old scheme is fine which just dumps the components of new and old root latencies. Perhaps only add whether or not SlackIsAccurate is set?

454–458

Typos (eg. Wwe -> We) and dups ('the first time'). What does 'relatively accurate' mean?

[fhahn]

Thanks for having a look!
Address review comments.

As for data for your compile-time improvements: I was looking into compile-time outliers for a proprietary benchmark suite, so unfortunately I cannot share the source. There was a module with a few large basic block (one with ~35000 instructions and a couple with > 3000 instructions), with lots of combinable instructions on AArch64 . Without this patch, time-passes on llc shows

Total Execution Time: 18.2227 seconds (18.2513 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
14.0113 ( 77.4%)   0.0338 ( 28.5%)  14.0451 ( 77.1%)  14.0672 ( 77.1%)  Machine InstCombiner
 2.0149 ( 11.1%)   0.0552 ( 46.5%)   2.0701 ( 11.4%)   2.0726 ( 11.4%)  Greedy Register Allocator
 0.9370 (  5.2%)   0.0184 ( 15.5%)   0.9554 (  5.2%)   0.9577 (  5.2%)  AArch64 Instruction Selection
 0.3403 (  1.9%)   0.0010 (  0.8%)   0.3413 (  1.9%)   0.3417 (  1.9%)  Machine Instruction Scheduler

With this patch

Total Execution Time: 4.9057 seconds (4.9158 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 2.0272 ( 42.1%)   0.0612 ( 64.8%)   2.0884 ( 42.6%)   2.0931 ( 42.6%)  Greedy Register Allocator
 0.9621 ( 20.0%)   0.0190 ( 20.1%)   0.9810 ( 20.0%)   0.9829 ( 20.0%)  AArch64 Instruction Selection
 0.6782 ( 14.1%)   0.0021 (  2.2%)   0.6803 ( 13.9%)   0.6812 ( 13.9%)  Machine InstCombiner

lib/CodeGen/MachineCombiner.cpp

273–274

I've added the comment again. Removing the comment was a left-over from an earlier iteration of the patch.

454–458

I am not sure how to put that. updateDepth() uses the live register info in RegUnits to track dependencies of physical registers. In the following case, the depths could be wrong (R1 being a physical register):

R1 <- I0 ....
R2 <- I1 R1
R1 <- I2 ...
.. <- I3 R2

If we replace I1 and I2 with ... <- I4 R1, when we are updating the depth of I4, RegUnits would contain something like (R1 defined by I2), and it would use that dependency for the depth calculation. But when the MachineCombiner is run, combined instructions should still use virtual registers. At least for the AArch64, it seems like physical registers are used only for argument passing at this stage.

[Gerolf]

Thank you for sharing your numbers. I was hoping you had that show-off case.
I just have a few minor comments about readability and asserts. I still need bit more time to convince myself that all the pieces fit together. I was wondering if you could add a test that dumps the depths w/ and w/o the incremental updates (compile w/ full comination + dumps depths, compile with a threashold of 1 + dump depths, diff the dump)?

Thanks
Gerolf

lib/CodeGen/MachineCombiner.cpp

351

Please add comments what the parameters mean. More parameters make it harder to read now.

362

The assumption is that LastUpdate and End are never Null. Would it make sense to document this with an assertion.

362

The loops under IncrementalUpdate in this function could be wrapped in a function (with start and end iterators as parameters).

363–368

Would it make sense for the RegUnit update be part of eraseFromParent...(),? E.g. have a bool parameter for that function indicating it?

[fhahn]

I really appreciate you taking time to review this change!

As a sanity check for the incremental update I did the following:

1. check-llvm-codegen passes with only using incremental depth computation (the full trace is computed before the main loop and IncremenalUpdate is initialized with true.

2. As you suggested, I compiled the MultiSource/Benchmarks programs from the LLVM test suite with 2 version of LLVM, one only using incremental depth computations and the other only using the existing mechanics. I printed the depths of all instructions of changed basic blocks and compared them. The depths are the same for both versions, with a few exceptions. The minor differences in heights are caused by nodes that depend on the depths of instructions in previous basic blocks (PHI nodes). In a few cases, the previous basic block has been invalidated, but is not in the set of basic blocks for which the depths are re-computed in getTrace(). If we do not invalidate the trace, all depths match. Maybe it would be worth to only invalidate the traces for all basic block we changed, at the end of MachineCombiner::runOnMachineFunction

lib/CodeGen/MachineCombiner.cpp

362

I think I am missing something about the assertion, but neither LatestUpdate nor End are pointers.

I've added an updateDepths function

363–368

I think updating RegUnits is only relevant for the incremental updates here and I am not sure if it is worth making Instruction::eraseFromParent... more compilcated.

[fhahn]

ping. @Gerolf did my last comments answer your questions adequately?

[Gerolf]

LGTM.

I added a few minor remarks that you might want to consider before commit. Again, thanks for working on this and your patience!

Cheers
Gerolf

lib/CodeGen/MachineCombiner.cpp

373

You could call updateDepths here as well. Also if you had code like if (IncrementalUpdate) MinInstr->updateDepths(...) else MinInstr->invalidate(MBB) you could spare two parameters (at the cost of adding such a line after each call). It feels more natural to me than packing the code inside the insertDelete...() procedure.

383

LastUpdate = BlockIter like in the code below?

[fhahn]

Thank you very much for having a look! I'll address your comments tomorrow and go ahead committing the patch. Also, this patch depends on D36696, which is a NFC that moves the code to update the instruction depths to a separate function (in MachineTraceMetrics.cpp). Pending further objections, I'll commit this patch as well tomorrow.

[fhahn]

lib/CodeGen/MachineCombiner.cpp

373

This is slightly more difficult, I think, as MachineBasicBlock::iterator iterates over instruction references while InsInstrs contains instruction pointers. I'll leave it as it is for now and will think a bit more if we can make this nicer.

I think it is slightly safer to update the state of the trace here, as this should always be done if we modify the basic block.

[fhahn]

Accepted in Phabricator to make arc happy.

include/llvm/CodeGen/MachineTraceMetrics.h

 // execution of the instruction can be delayed without extending the critical
 // path.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINETRACEMETRICS_H
 #define LLVM_CODEGEN_MACHINETRACEMETRICS_H
 
+#include "llvm/ADT/SparseSet.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 
 namespace llvm {
 
 class AnalysisUsage;
 class MachineBasicBlock;
 class MachineFunction;
 class MachineInstr;
 class MachineLoop;
 class MachineLoopInfo;
 class MachineRegisterInfo;
 struct MCSchedClassDesc;
 class raw_ostream;
 class TargetInstrInfo;
 class TargetRegisterInfo;
 
+// Keep track of physreg data dependencies by recording each live register unit.
+// Associate each regunit with an instruction operand. Depending on the
+// direction instructions are scanned, it could be the operand that defined the
+// regunit, or the highest operand to read the regunit.
+struct LiveRegUnit {
+  unsigned RegUnit;
+  unsigned Cycle = 0;
+  const MachineInstr *MI = nullptr;
+  unsigned Op = 0;
+
+  unsigned getSparseSetIndex() const { return RegUnit; }
+
+  LiveRegUnit(unsigned RU) : RegUnit(RU) {}
+};
+
+
 class MachineTraceMetrics : public MachineFunctionPass {
   const MachineFunction *MF = nullptr;
   const TargetInstrInfo *TII = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
   const MachineRegisterInfo *MRI = nullptr;
   const MachineLoopInfo *Loops = nullptr;
   TargetSchedModel SchedModel;
 
public:
   /// handle to internal cached data structures.
   class Trace {
     Ensemble &TE;
     TraceBlockInfo &TBI;
 
     unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; }
 
   public:
-    explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {}
 
     void print(raw_ostream&) const;
 
     /// Compute the total number of instructions in the trace.
     unsigned getInstrCount() const {
       return TBI.InstrDepth + TBI.InstrHeight;
     }
 
public:
     virtual const char *getName() const = 0;
     void print(raw_ostream&) const;
     void invalidate(const MachineBasicBlock *MBB);
     void verify() const;
 
     /// Get the trace that passes through MBB.
     /// The trace is computed on demand.
     Trace getTrace(const MachineBasicBlock *MBB);
+    void updateDepth(const MachineBasicBlock *, const MachineInstr&, SparseSet<LiveRegUnit> *RegUnits);
   };
 
   /// Strategies for selecting traces.
   enum Strategy {
     /// Select the trace through a block that has the fewest instructions.
     TS_MinInstrCount,
 
     TS_NumStrategies
   };
 
   /// Get the trace ensemble representing the given trace selection strategy.
   /// The returned Ensemble object is owned by the MachineTraceMetrics analysis,
   /// and valid for the lifetime of the analysis pass.
   Ensemble *getEnsemble(Strategy);
 
   /// Invalidate cached information about MBB. This must be called *before* MBB
   /// is erased, or the CFG is otherwise changed.
   ///
   /// This invalidates per-block information about resource usage for MBB only,
   /// and it invalidates per-trace information for any trace that passes
   /// through MBB.
   ///
   /// Call Ensemble::getTrace() again to update any trace handles.
   void invalidate(const MachineBasicBlock *MBB);
-
 private:
   // One entry per basic block, indexed by block number.
   SmallVector<FixedBlockInfo, 4> BlockInfo;
 
   // Cycles consumed on each processor resource per block.
   // The number of processor resource kinds is constant for a given subtarget,
   // but it is not known at compile time. The number of cycles consumed by
   // block B on processor resource R is at ProcResourceCycles[B*Kinds + R]

lib/CodeGen/MachineCombiner.cpp

 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-combiner"
 
 STATISTIC(NumInstCombined, "Number of machineinst combined");
 
 namespace {
+
 class MachineCombiner : public MachineFunctionPass {
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   MCSchedModel SchedModel;
   MachineRegisterInfo *MRI;
   MachineLoopInfo *MLI; // Current MachineLoopInfo
   MachineTraceMetrics *Traces;
   MachineTraceMetrics::Ensemble *MinInstr;
bool MachineCombiner::improvesCriticalPathLen(
   // NewRoot is the last instruction in the \p InsInstrs vector.
   unsigned NewRootIdx = InsInstrs.size() - 1;
   MachineInstr *NewRoot = InsInstrs[NewRootIdx];
 
   // Get depth and latency of NewRoot and Root.
   unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
   unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
 
-  DEBUG(dbgs() << "DEPENDENCE DATA FOR " << Root << "\n";
+  DEBUG(dbgs() << "DEPENDENCE DATA FOR " << *Root << "\n";
         dbgs() << " NewRootDepth: " << NewRootDepth << "\n";
         dbgs() << " RootDepth: " << RootDepth << "\n");
 
   // For a transform such as reassociation, the cost equation is
   // conservatively calculated so that we must improve the depth (data
   // dependency cycles) in the critical path to proceed with the transform.
   // Being conservative also protects against inaccuracies in the underlying
   // machine trace metrics and CPU models.
   if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth)
     return NewRootDepth < RootDepth;
 
-  // A more flexible cost calculation for the critical path includes the slack
-  // of the original code sequence. This may allow the transform to proceed
-  // even if the instruction depths (data dependency cycles) become worse.
-
   unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
   unsigned RootLatency = 0;
 
   for (auto I : DelInstrs)
     RootLatency += TSchedModel.computeInstrLatency(I);
 
-  unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
-
   DEBUG(dbgs() << " NewRootLatency: " << NewRootLatency << "\n";
         dbgs() << " RootLatency: " << RootLatency << "\n";
         dbgs() << " RootSlack: " << RootSlack << "\n";
         dbgs() << " NewRootDepth + NewRootLatency = "
                << NewRootDepth + NewRootLatency << "\n";
-        dbgs() << " RootDepth + RootLatency + RootSlack = "
-               << RootDepth + RootLatency + RootSlack << "\n";);
+        dbgs() << " RootDepth + RootLatency = "
+               << RootDepth + RootLatency << "\n";);
 
   unsigned NewCycleCount = NewRootDepth + NewRootLatency;
-  unsigned OldCycleCount = RootDepth + RootLatency + RootSlack;
-
+  unsigned OldCycleCount = RootDepth + RootLatency;
   return NewCycleCount <= OldCycleCount;
 }
 
 /// helper routine to convert instructions into SC
 void MachineCombiner::instr2instrSC(
     SmallVectorImpl<MachineInstr *> &Instrs,
     SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
   for (auto *InstrPtr : Instrs) {

 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
   if (OptSize && (NewSize < OldSize))
     return true;
   if (!TSchedModel.hasInstrSchedModelOrItineraries())
     return true;
   return false;
 }
 
 static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
                                      SmallVector<MachineInstr *, 16> InsInstrs,
                                      SmallVector<MachineInstr *, 16> DelInstrs,
-                                     MachineTraceMetrics *Traces) {
+                                     MachineTraceMetrics::Ensemble *MinInstr,
+                                     MachineBasicBlock::iterator &LastUpdate) {
   for (auto *InstrPtr : InsInstrs)
-    MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
-  for (auto *InstrPtr : DelInstrs)
+    MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
+
+  for (auto *InstrPtr : DelInstrs) {
+    if (InstrPtr->getIterator() == LastUpdate)
+      LastUpdate++;
     InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
-  ++NumInstCombined;
-  Traces->invalidate(MBB);
-  Traces->verifyAnalysis();
+  }
+
+  for (auto *InstrPtr : InsInstrs)
+    MinInstr->updateDepth(MBB, *InstrPtr, nullptr);
+
+  NumInstCombined++;
 }
 
 /// Substitute a slow code sequence with a faster one by
 /// evaluating instruction combining pattern.
 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
 /// combining based on machine trace metrics. Only combine a sequence of
 /// instructions  when this neither lengthens the critical path nor increases
 /// resource pressure. When optimizing for codesize always combine when the new
 /// sequence is shorter.
 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
   bool Changed = false;
   DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
 
   auto BlockIter = MBB->begin();
+  auto LastUpdate = MBB->begin();
   // Check if the block is in a loop.
   const MachineLoop *ML = MLI->getLoopFor(MBB);
+  if (!MinInstr)
+    MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
 
   while (BlockIter != MBB->end()) {
     auto &MI = *BlockIter++;
 
     DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
     SmallVector<MachineCombinerPattern, 16> Patterns;
     // The motivating example is:
     //
while (BlockIter != MBB->end()) {
     // The algorithm does not try to evaluate all patterns and pick the best.
     // This is only an artificial restriction though. In practice there is
     // mostly one pattern, and getMachineCombinerPatterns() can order patterns
     // based on an internal cost heuristic.
 
     if (!TII->getMachineCombinerPatterns(MI, Patterns))
       continue;
 
+    MinInstr->updateDepth(MBB, MI, nullptr);
     for (auto P : Patterns) {
       SmallVector<MachineInstr *, 16> InsInstrs;
       SmallVector<MachineInstr *, 16> DelInstrs;
       DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
-      if (!MinInstr)
-        MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
-      Traces->verifyAnalysis();
       TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
                                       InstrIdxForVirtReg);
       unsigned NewInstCount = InsInstrs.size();
       unsigned OldInstCount = DelInstrs.size();
       // Found pattern, but did not generate alternative sequence.
       // This can happen e.g. when an immediate could not be materialized
       // in a single instruction.
       if (!NewInstCount)
         continue;
 
       bool SubstituteAlways = false;
       if (ML && TII->isThroughputPattern(P))
         SubstituteAlways = true;
 
+      for (; LastUpdate != (MachineBasicBlock::iterator) &MI; LastUpdate++)
+        MinInstr->updateDepth(MBB, *LastUpdate, nullptr);
+
       // Substitute when we optimize for codesize and the new sequence has
       // fewer instructions OR
       // the new sequence neither lengthens the critical path nor increases
       // resource pressure.
       if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
-        insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, Traces);
+        insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr, LastUpdate);
         // Eagerly stop after the first pattern fires.
         Changed = true;
         break;
       } else {
-        // Calculating the trace metrics may be expensive,
-        // so only do this when necessary.
+        // We only compute the full trace the first time we hit this the first
+        // time. We do not invalidate the trace, but instead update the
+        // instruction depths incrementally.
+        // NOTE: Only the instruction depths up to MI are accurate. All other
+        // trace information is not updated.
         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
+        Traces->verifyAnalysis();
         if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
                                     InstrIdxForVirtReg, P) &&
             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
-          insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, Traces);
+          insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr, LastUpdate);
+
           // Eagerly stop after the first pattern fires.
           Changed = true;
           break;
         }
         // Cleanup instructions of the alternative code sequence. There is no
         // use for them.
         MachineFunction *MF = MBB->getParent();
         for (auto *InstrPtr : InsInstrs)
           MF->DeleteMachineInstr(InstrPtr);
       }
       InstrIdxForVirtReg.clear();
     }
   }
 
+  if (Changed)
+    Traces->invalidate(MBB);
   return Changed;
 }
 
 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   TII = STI.getInstrInfo();
   TRI = STI.getRegisterInfo();
   SchedModel = STI.getSchedModel();

lib/CodeGen/MachineTraceMetrics.cpp

for (unsigned i = 1; i != UseMI.getNumOperands(); i += 2) {
     if (UseMI.getOperand(i + 1).getMBB() == Pred) {
       unsigned Reg = UseMI.getOperand(i).getReg();
       Deps.push_back(DataDep(MRI, Reg, i));
       return;
     }
   }
 }
 
-// Keep track of physreg data dependencies by recording each live register unit.
-// Associate each regunit with an instruction operand. Depending on the
-// direction instructions are scanned, it could be the operand that defined the
-// regunit, or the highest operand to read the regunit.
-namespace {
-
-struct LiveRegUnit {
-  unsigned RegUnit;
-  unsigned Cycle = 0;
-  const MachineInstr *MI = nullptr;
-  unsigned Op = 0;
-
-  unsigned getSparseSetIndex() const { return RegUnit; }
-
-  LiveRegUnit(unsigned RU) : RegUnit(RU) {}
-};
-
-} // end anonymous namespace
-
 // Identify physreg dependencies for UseMI, and update the live regunit
 // tracking set when scanning instructions downwards.
 static void updatePhysDepsDownwards(const MachineInstr *UseMI,
                                     SmallVectorImpl<DataDep> &Deps,
                                     SparseSet<LiveRegUnit> &RegUnits,
                                     const TargetRegisterInfo *TRI) {
   SmallVector<unsigned, 8> Kills;
   SmallVector<unsigned, 8> LiveDefOps;
for (const LiveInReg &LIR : TBI.LiveIns) {
     if (!DefTBI.isUsefulDominator(TBI))
       continue;
     unsigned Len = LIR.Height + Cycles[DefMI].Depth;
     MaxLen = std::max(MaxLen, Len);
   }
   return MaxLen;
 }
 
+void MachineTraceMetrics::Ensemble::
+updateDepth(const MachineBasicBlock *MBB, const MachineInstr &UseMI,
+            SparseSet<LiveRegUnit> *RegUnits) {
+  TraceBlockInfo &TBI =  BlockInfo[MBB->getNumber()];
+  SmallVector<DataDep, 8> Deps;
+  // Collect all data dependencies.
+  if (UseMI.isPHI())
+    getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI);
+  else if (getDataDeps(UseMI, Deps, MTM.MRI) && RegUnits)
+    updatePhysDepsDownwards(&UseMI, Deps, *RegUnits, MTM.TRI);
+
+  // Filter and process dependencies, computing the earliest issue cycle.
+  unsigned Cycle = 0;
+  for (const DataDep &Dep : Deps) {
+    const TraceBlockInfo&DepTBI =
+      BlockInfo[Dep.DefMI->getParent()->getNumber()];
+    // Ignore dependencies from outside the current trace.
+    if (!DepTBI.isUsefulDominator(TBI))
+      continue;
+    assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency");
+    unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth;
+    // Add latency if DefMI is a real instruction. Transients get latency 0.
+    if (!Dep.DefMI->isTransient())
+      DepCycle += MTM.SchedModel
+        .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp);
+    Cycle = std::max(Cycle, DepCycle);
+  }
+  // Remember the instruction depth.
+  InstrCycles &MICycles = Cycles[&UseMI];
+  MICycles.Depth = Cycle;
+
+  if (!TBI.HasValidInstrHeights) {
+    DEBUG(dbgs() << Cycle << '\t' << UseMI);
+    return;
+  }
+
+
+  // Update critical path length.
+  TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height);
+  DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI);
+
+}
 /// Compute instruction depths for all instructions above or in MBB in its
 /// trace. This assumes that the trace through MBB has already been computed.
 void MachineTraceMetrics::Ensemble::
 computeInstrDepths(const MachineBasicBlock *MBB) {
   // The top of the trace may already be computed, and HasValidInstrDepths
   // implies Head->HasValidInstrDepths, so we only need to start from the first
   // block in the trace that needs to be recomputed.
   SmallVector<const MachineBasicBlock*, 8> Stack;
   do {
     TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
     assert(TBI.hasValidDepth() && "Incomplete trace");
     if (TBI.HasValidInstrDepths)
       break;
     Stack.push_back(MBB);
     MBB = TBI.Pred;
   } while (MBB);
 
   // FIXME: If MBB is non-null at this point, it is the last pre-computed block
   // in the trace. We should track any live-out physregs that were defined in
   // the trace. This is quite rare in SSA form, typically created by CSE
   // hoisting a compare.
+
   SparseSet<LiveRegUnit> RegUnits;
   RegUnits.setUniverse(MTM.TRI->getNumRegUnits());
-
   // Go through trace blocks in top-down order, stopping after the center block.
-  SmallVector<DataDep, 8> Deps;
   while (!Stack.empty()) {
     MBB = Stack.pop_back_val();
     DEBUG(dbgs() << "\nDepths for BB#" << MBB->getNumber() << ":\n");
     TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
     TBI.HasValidInstrDepths = true;
     TBI.CriticalPath = 0;
 
     // Print out resource depths here as well.
DEBUG({
         }
     });
 
     // Also compute the critical path length through MBB when possible.
     if (TBI.HasValidInstrHeights)
       TBI.CriticalPath = computeCrossBlockCriticalPath(TBI);
 
     for (const auto &UseMI : *MBB) {
-      // Collect all data dependencies.
-      Deps.clear();
-      if (UseMI.isPHI())
-        getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI);
-      else if (getDataDeps(UseMI, Deps, MTM.MRI))
-        updatePhysDepsDownwards(&UseMI, Deps, RegUnits, MTM.TRI);
-
-      // Filter and process dependencies, computing the earliest issue cycle.
-      unsigned Cycle = 0;
-      for (const DataDep &Dep : Deps) {
-        const TraceBlockInfo&DepTBI =
-          BlockInfo[Dep.DefMI->getParent()->getNumber()];
-        // Ignore dependencies from outside the current trace.
-        if (!DepTBI.isUsefulDominator(TBI))
-          continue;
-        assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency");
-        unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth;
-        // Add latency if DefMI is a real instruction. Transients get latency 0.
-        if (!Dep.DefMI->isTransient())
-          DepCycle += MTM.SchedModel
-            .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp);
-        Cycle = std::max(Cycle, DepCycle);
-      }
-      // Remember the instruction depth.
-      InstrCycles &MICycles = Cycles[&UseMI];
-      MICycles.Depth = Cycle;
-
-      if (!TBI.HasValidInstrHeights) {
-        DEBUG(dbgs() << Cycle << '\t' << UseMI);
-        continue;
-      }
-      // Update critical path length.
-      TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height);
-      DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI);
+      updateDepth(MBB, UseMI, &RegUnits);
     }
   }
 }
 
 // Identify physreg dependencies for MI when scanning instructions upwards.
 // Return the issue height of MI after considering any live regunits.
 // Height is the issue height computed from virtual register dependencies alone.
 static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height,