[MachineTraceMetrics] Add computeDepth function (NFCI).

[fhahn]

Summary

This function is used in D36619 to update the instruction depths
incrementally.

[Gerolf]

LGTM. Just some food for thought for possible follow up commits.

lib/CodeGen/MachineTraceMetrics.cpp

782

It would make the side effects of this procedure more explicit if a reference to TBI rather than MBB is passed as the first parameter. Within MachineTraceMetrics this would also reduce the #accesss to BlockInfo.

812

You could simplify and update the CP when HasValidInstrHeights is true.

[fhahn]

Thanks for the comments, I added a updateDepth function that accepts a reference to TBI. I kept the version with MBB as well, as I think there's no way to get TBI for a basic block from outside MachineTraceMetrics (which we should not change IMO). I've also moved the code to set the CP, it should be slightly clearer now.

[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:
     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);
+
+    /// Updates the depth of an machine instruction, given RegUnits.
+    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/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))
+    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,