Restoring authorship annotation for <[email protected]>. Commit 1 of 2.

1 files changed, 444 insertions, 444 deletions

diff --git a/contrib/libs/llvm12/include/llvm/CodeGen/MachineTraceMetrics.h b/contrib/libs/llvm12/include/llvm/CodeGen/MachineTraceMetrics.h
index 2d9da27f75d..8314a79c186 100644
--- a/contrib/libs/llvm12/include/llvm/CodeGen/MachineTraceMetrics.h
+++ b/contrib/libs/llvm12/include/llvm/CodeGen/MachineTraceMetrics.h
@@ -1,446 +1,446 @@
-#pragma once
-
-#ifdef __GNUC__
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wunused-parameter"
-#endif
-
-//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the interface for the MachineTraceMetrics analysis pass
-// that estimates CPU resource usage and critical data dependency paths through
-// preferred traces. This is useful for super-scalar CPUs where execution speed
-// can be limited both by data dependencies and by limited execution resources.
-//
-// Out-of-order CPUs will often be executing instructions from multiple basic
-// blocks at the same time. This makes it difficult to estimate the resource
-// usage accurately in a single basic block. Resources can be estimated better
-// by looking at a trace through the current basic block.
-//
-// For every block, the MachineTraceMetrics pass will pick a preferred trace
-// that passes through the block. The trace is chosen based on loop structure,
-// branch probabilities, and resource usage. The intention is to pick likely
-// traces that would be the most affected by code transformations.
-//
-// It is expensive to compute a full arbitrary trace for every block, so to
-// save some computations, traces are chosen to be convergent. This means that
-// if the traces through basic blocks A and B ever cross when moving away from
-// A and B, they never diverge again. This applies in both directions - If the
-// traces meet above A and B, they won't diverge when going further back.
-//
-// Traces tend to align with loops. The trace through a block in an inner loop
-// will begin at the loop entry block and end at a back edge. If there are
-// nested loops, the trace may begin and end at those instead.
-//
-// For each trace, we compute the critical path length, which is the number of
-// cycles required to execute the trace when execution is limited by data
-// dependencies only. We also compute the resource height, which is the number
-// of cycles required to execute all instructions in the trace when ignoring
-// data dependencies.
-//
-// Every instruction in the current block has a slack - the number of cycles
-// 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/MachineBasicBlock.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/TargetSchedule.h"
-
-namespace llvm {
-
-class AnalysisUsage;
-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:
-  friend class Ensemble;
-  friend class Trace;
-
-  class Ensemble;
-
-  static char ID;
-
-  MachineTraceMetrics();
-
-  void getAnalysisUsage(AnalysisUsage&) const override;
-  bool runOnMachineFunction(MachineFunction&) override;
-  void releaseMemory() override;
-  void verifyAnalysis() const override;
-
-  /// Per-basic block information that doesn't depend on the trace through the
-  /// block.
-  struct FixedBlockInfo {
-    /// The number of non-trivial instructions in the block.
-    /// Doesn't count PHI and COPY instructions that are likely to be removed.
-    unsigned InstrCount = ~0u;
-
-    /// True when the block contains calls.
-    bool HasCalls = false;
-
-    FixedBlockInfo() = default;
-
-    /// Returns true when resource information for this block has been computed.
-    bool hasResources() const { return InstrCount != ~0u; }
-
-    /// Invalidate resource information.
-    void invalidate() { InstrCount = ~0u; }
-  };
-
-  /// Get the fixed resource information about MBB. Compute it on demand.
-  const FixedBlockInfo *getResources(const MachineBasicBlock*);
-
-  /// Get the scaled number of cycles used per processor resource in MBB.
-  /// This is an array with SchedModel.getNumProcResourceKinds() entries.
-  /// The getResources() function above must have been called first.
-  ///
-  /// These numbers have already been scaled by SchedModel.getResourceFactor().
-  ArrayRef<unsigned> getProcResourceCycles(unsigned MBBNum) const;
-
-  /// A virtual register or regunit required by a basic block or its trace
-  /// successors.
-  struct LiveInReg {
-    /// The virtual register required, or a register unit.
+#pragma once 
+ 
+#ifdef __GNUC__ 
+#pragma GCC diagnostic push 
+#pragma GCC diagnostic ignored "-Wunused-parameter" 
+#endif 
+ 
+//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===// 
+// 
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 
+// See https://llvm.org/LICENSE.txt for license information. 
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 
+// 
+//===----------------------------------------------------------------------===// 
+// 
+// This file defines the interface for the MachineTraceMetrics analysis pass 
+// that estimates CPU resource usage and critical data dependency paths through 
+// preferred traces. This is useful for super-scalar CPUs where execution speed 
+// can be limited both by data dependencies and by limited execution resources. 
+// 
+// Out-of-order CPUs will often be executing instructions from multiple basic 
+// blocks at the same time. This makes it difficult to estimate the resource 
+// usage accurately in a single basic block. Resources can be estimated better 
+// by looking at a trace through the current basic block. 
+// 
+// For every block, the MachineTraceMetrics pass will pick a preferred trace 
+// that passes through the block. The trace is chosen based on loop structure, 
+// branch probabilities, and resource usage. The intention is to pick likely 
+// traces that would be the most affected by code transformations. 
+// 
+// It is expensive to compute a full arbitrary trace for every block, so to 
+// save some computations, traces are chosen to be convergent. This means that 
+// if the traces through basic blocks A and B ever cross when moving away from 
+// A and B, they never diverge again. This applies in both directions - If the 
+// traces meet above A and B, they won't diverge when going further back. 
+// 
+// Traces tend to align with loops. The trace through a block in an inner loop 
+// will begin at the loop entry block and end at a back edge. If there are 
+// nested loops, the trace may begin and end at those instead. 
+// 
+// For each trace, we compute the critical path length, which is the number of 
+// cycles required to execute the trace when execution is limited by data 
+// dependencies only. We also compute the resource height, which is the number 
+// of cycles required to execute all instructions in the trace when ignoring 
+// data dependencies. 
+// 
+// Every instruction in the current block has a slack - the number of cycles 
+// 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/MachineBasicBlock.h" 
+#include "llvm/CodeGen/MachineFunctionPass.h" 
+#include "llvm/CodeGen/TargetSchedule.h" 
+ 
+namespace llvm { 
+ 
+class AnalysisUsage; 
+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: 
+  friend class Ensemble; 
+  friend class Trace; 
+ 
+  class Ensemble; 
+ 
+  static char ID; 
+ 
+  MachineTraceMetrics(); 
+ 
+  void getAnalysisUsage(AnalysisUsage&) const override; 
+  bool runOnMachineFunction(MachineFunction&) override; 
+  void releaseMemory() override; 
+  void verifyAnalysis() const override; 
+ 
+  /// Per-basic block information that doesn't depend on the trace through the 
+  /// block. 
+  struct FixedBlockInfo { 
+    /// The number of non-trivial instructions in the block. 
+    /// Doesn't count PHI and COPY instructions that are likely to be removed. 
+    unsigned InstrCount = ~0u; 
+ 
+    /// True when the block contains calls. 
+    bool HasCalls = false; 
+ 
+    FixedBlockInfo() = default; 
+ 
+    /// Returns true when resource information for this block has been computed. 
+    bool hasResources() const { return InstrCount != ~0u; } 
+ 
+    /// Invalidate resource information. 
+    void invalidate() { InstrCount = ~0u; } 
+  }; 
+ 
+  /// Get the fixed resource information about MBB. Compute it on demand. 
+  const FixedBlockInfo *getResources(const MachineBasicBlock*); 
+ 
+  /// Get the scaled number of cycles used per processor resource in MBB. 
+  /// This is an array with SchedModel.getNumProcResourceKinds() entries. 
+  /// The getResources() function above must have been called first. 
+  /// 
+  /// These numbers have already been scaled by SchedModel.getResourceFactor(). 
+  ArrayRef<unsigned> getProcResourceCycles(unsigned MBBNum) const; 
+ 
+  /// A virtual register or regunit required by a basic block or its trace 
+  /// successors. 
+  struct LiveInReg { 
+    /// The virtual register required, or a register unit. 
     Register Reg;
-
-    /// For virtual registers: Minimum height of the defining instruction.
-    /// For regunits: Height of the highest user in the trace.
-    unsigned Height;
-
+ 
+    /// For virtual registers: Minimum height of the defining instruction. 
+    /// For regunits: Height of the highest user in the trace. 
+    unsigned Height; 
+ 
     LiveInReg(Register Reg, unsigned Height = 0) : Reg(Reg), Height(Height) {}
-  };
-
-  /// Per-basic block information that relates to a specific trace through the
-  /// block. Convergent traces means that only one of these is required per
-  /// block in a trace ensemble.
-  struct TraceBlockInfo {
-    /// Trace predecessor, or NULL for the first block in the trace.
-    /// Valid when hasValidDepth().
-    const MachineBasicBlock *Pred = nullptr;
-
-    /// Trace successor, or NULL for the last block in the trace.
-    /// Valid when hasValidHeight().
-    const MachineBasicBlock *Succ = nullptr;
-
-    /// The block number of the head of the trace. (When hasValidDepth()).
-    unsigned Head;
-
-    /// The block number of the tail of the trace. (When hasValidHeight()).
-    unsigned Tail;
-
-    /// Accumulated number of instructions in the trace above this block.
-    /// Does not include instructions in this block.
-    unsigned InstrDepth = ~0u;
-
-    /// Accumulated number of instructions in the trace below this block.
-    /// Includes instructions in this block.
-    unsigned InstrHeight = ~0u;
-
-    TraceBlockInfo() = default;
-
-    /// Returns true if the depth resources have been computed from the trace
-    /// above this block.
-    bool hasValidDepth() const { return InstrDepth != ~0u; }
-
-    /// Returns true if the height resources have been computed from the trace
-    /// below this block.
-    bool hasValidHeight() const { return InstrHeight != ~0u; }
-
-    /// Invalidate depth resources when some block above this one has changed.
-    void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; }
-
-    /// Invalidate height resources when a block below this one has changed.
-    void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; }
-
-    /// Assuming that this is a dominator of TBI, determine if it contains
-    /// useful instruction depths. A dominating block can be above the current
-    /// trace head, and any dependencies from such a far away dominator are not
-    /// expected to affect the critical path.
-    ///
-    /// Also returns true when TBI == this.
-    bool isUsefulDominator(const TraceBlockInfo &TBI) const {
-      // The trace for TBI may not even be calculated yet.
-      if (!hasValidDepth() || !TBI.hasValidDepth())
-        return false;
-      // Instruction depths are only comparable if the traces share a head.
-      if (Head != TBI.Head)
-        return false;
-      // It is almost always the case that TBI belongs to the same trace as
-      // this block, but rare convoluted cases involving irreducible control
-      // flow, a dominator may share a trace head without actually being on the
-      // same trace as TBI. This is not a big problem as long as it doesn't
-      // increase the instruction depth.
-      return HasValidInstrDepths && InstrDepth <= TBI.InstrDepth;
-    }
-
-    // Data-dependency-related information. Per-instruction depth and height
-    // are computed from data dependencies in the current trace, using
-    // itinerary data.
-
-    /// Instruction depths have been computed. This implies hasValidDepth().
-    bool HasValidInstrDepths = false;
-
-    /// Instruction heights have been computed. This implies hasValidHeight().
-    bool HasValidInstrHeights = false;
-
-    /// Critical path length. This is the number of cycles in the longest data
-    /// dependency chain through the trace. This is only valid when both
-    /// HasValidInstrDepths and HasValidInstrHeights are set.
-    unsigned CriticalPath;
-
-    /// Live-in registers. These registers are defined above the current block
-    /// and used by this block or a block below it.
-    /// This does not include PHI uses in the current block, but it does
-    /// include PHI uses in deeper blocks.
-    SmallVector<LiveInReg, 4> LiveIns;
-
-    void print(raw_ostream&) const;
-  };
-
-  /// InstrCycles represents the cycle height and depth of an instruction in a
-  /// trace.
-  struct InstrCycles {
-    /// Earliest issue cycle as determined by data dependencies and instruction
-    /// latencies from the beginning of the trace. Data dependencies from
-    /// before the trace are not included.
-    unsigned Depth;
-
-    /// Minimum number of cycles from this instruction is issued to the of the
-    /// trace, as determined by data dependencies and instruction latencies.
-    unsigned Height;
-  };
-
-  /// A trace represents a plausible sequence of executed basic blocks that
-  /// passes through the current basic block one. The Trace class serves as a
-  /// 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;
-    }
-
-    /// Return the resource depth of the top/bottom of the trace center block.
-    /// This is the number of cycles required to execute all instructions from
-    /// the trace head to the trace center block. The resource depth only
-    /// considers execution resources, it ignores data dependencies.
-    /// When Bottom is set, instructions in the trace center block are included.
-    unsigned getResourceDepth(bool Bottom) const;
-
-    /// Return the resource length of the trace. This is the number of cycles
-    /// required to execute the instructions in the trace if they were all
-    /// independent, exposing the maximum instruction-level parallelism.
-    ///
-    /// Any blocks in Extrablocks are included as if they were part of the
-    /// trace. Likewise, extra resources required by the specified scheduling
-    /// classes are included. For the caller to account for extra machine
-    /// instructions, it must first resolve each instruction's scheduling class.
-    unsigned getResourceLength(
-        ArrayRef<const MachineBasicBlock *> Extrablocks = None,
-        ArrayRef<const MCSchedClassDesc *> ExtraInstrs = None,
-        ArrayRef<const MCSchedClassDesc *> RemoveInstrs = None) const;
-
-    /// Return the length of the (data dependency) critical path through the
-    /// trace.
-    unsigned getCriticalPath() const { return TBI.CriticalPath; }
-
-    /// Return the depth and height of MI. The depth is only valid for
-    /// instructions in or above the trace center block. The height is only
-    /// valid for instructions in or below the trace center block.
-    InstrCycles getInstrCycles(const MachineInstr &MI) const {
-      return TE.Cycles.lookup(&MI);
-    }
-
-    /// Return the slack of MI. This is the number of cycles MI can be delayed
-    /// before the critical path becomes longer.
-    /// MI must be an instruction in the trace center block.
-    unsigned getInstrSlack(const MachineInstr &MI) const;
-
-    /// Return the Depth of a PHI instruction in a trace center block successor.
-    /// The PHI does not have to be part of the trace.
-    unsigned getPHIDepth(const MachineInstr &PHI) const;
-
-    /// A dependence is useful if the basic block of the defining instruction
-    /// is part of the trace of the user instruction. It is assumed that DefMI
-    /// dominates UseMI (see also isUsefulDominator).
-    bool isDepInTrace(const MachineInstr &DefMI,
-                      const MachineInstr &UseMI) const;
-  };
-
-  /// A trace ensemble is a collection of traces selected using the same
-  /// strategy, for example 'minimum resource height'. There is one trace for
-  /// every block in the function.
-  class Ensemble {
-    friend class Trace;
-
-    SmallVector<TraceBlockInfo, 4> BlockInfo;
-    DenseMap<const MachineInstr*, InstrCycles> Cycles;
-    SmallVector<unsigned, 0> ProcResourceDepths;
-    SmallVector<unsigned, 0> ProcResourceHeights;
-
-    void computeTrace(const MachineBasicBlock*);
-    void computeDepthResources(const MachineBasicBlock*);
-    void computeHeightResources(const MachineBasicBlock*);
-    unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&);
-    void computeInstrDepths(const MachineBasicBlock*);
-    void computeInstrHeights(const MachineBasicBlock*);
-    void addLiveIns(const MachineInstr *DefMI, unsigned DefOp,
-                    ArrayRef<const MachineBasicBlock*> Trace);
-
-  protected:
-    MachineTraceMetrics &MTM;
-
-    explicit Ensemble(MachineTraceMetrics*);
-
-    virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
-    virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
-    const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
-    const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
-    const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
-    ArrayRef<unsigned> getProcResourceDepths(unsigned MBBNum) const;
-    ArrayRef<unsigned> getProcResourceHeights(unsigned MBBNum) const;
-
-  public:
-    virtual ~Ensemble();
-
-    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(TraceBlockInfo &TBI, const MachineInstr&,
-                     SparseSet<LiveRegUnit> &RegUnits);
-    void updateDepth(const MachineBasicBlock *, const MachineInstr&,
-                     SparseSet<LiveRegUnit> &RegUnits);
-
-    /// Updates the depth of the instructions from Start to End.
-    void updateDepths(MachineBasicBlock::iterator Start,
-                      MachineBasicBlock::iterator End,
-                      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]
-  // where Kinds = SchedModel.getNumProcResourceKinds().
-  SmallVector<unsigned, 0> ProcResourceCycles;
-
-  // One ensemble per strategy.
-  Ensemble* Ensembles[TS_NumStrategies];
-
-  // Convert scaled resource usage to a cycle count that can be compared with
-  // latencies.
-  unsigned getCycles(unsigned Scaled) {
-    unsigned Factor = SchedModel.getLatencyFactor();
-    return (Scaled + Factor - 1) / Factor;
-  }
-};
-
-inline raw_ostream &operator<<(raw_ostream &OS,
-                               const MachineTraceMetrics::Trace &Tr) {
-  Tr.print(OS);
-  return OS;
-}
-
-inline raw_ostream &operator<<(raw_ostream &OS,
-                               const MachineTraceMetrics::Ensemble &En) {
-  En.print(OS);
-  return OS;
-}
-
-} // end namespace llvm
-
-#endif // LLVM_CODEGEN_MACHINETRACEMETRICS_H
-
-#ifdef __GNUC__
-#pragma GCC diagnostic pop
-#endif
+  }; 
+ 
+  /// Per-basic block information that relates to a specific trace through the 
+  /// block. Convergent traces means that only one of these is required per 
+  /// block in a trace ensemble. 
+  struct TraceBlockInfo { 
+    /// Trace predecessor, or NULL for the first block in the trace. 
+    /// Valid when hasValidDepth(). 
+    const MachineBasicBlock *Pred = nullptr; 
+ 
+    /// Trace successor, or NULL for the last block in the trace. 
+    /// Valid when hasValidHeight(). 
+    const MachineBasicBlock *Succ = nullptr; 
+ 
+    /// The block number of the head of the trace. (When hasValidDepth()). 
+    unsigned Head; 
+ 
+    /// The block number of the tail of the trace. (When hasValidHeight()). 
+    unsigned Tail; 
+ 
+    /// Accumulated number of instructions in the trace above this block. 
+    /// Does not include instructions in this block. 
+    unsigned InstrDepth = ~0u; 
+ 
+    /// Accumulated number of instructions in the trace below this block. 
+    /// Includes instructions in this block. 
+    unsigned InstrHeight = ~0u; 
+ 
+    TraceBlockInfo() = default; 
+ 
+    /// Returns true if the depth resources have been computed from the trace 
+    /// above this block. 
+    bool hasValidDepth() const { return InstrDepth != ~0u; } 
+ 
+    /// Returns true if the height resources have been computed from the trace 
+    /// below this block. 
+    bool hasValidHeight() const { return InstrHeight != ~0u; } 
+ 
+    /// Invalidate depth resources when some block above this one has changed. 
+    void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; } 
+ 
+    /// Invalidate height resources when a block below this one has changed. 
+    void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; } 
+ 
+    /// Assuming that this is a dominator of TBI, determine if it contains 
+    /// useful instruction depths. A dominating block can be above the current 
+    /// trace head, and any dependencies from such a far away dominator are not 
+    /// expected to affect the critical path. 
+    /// 
+    /// Also returns true when TBI == this. 
+    bool isUsefulDominator(const TraceBlockInfo &TBI) const { 
+      // The trace for TBI may not even be calculated yet. 
+      if (!hasValidDepth() || !TBI.hasValidDepth()) 
+        return false; 
+      // Instruction depths are only comparable if the traces share a head. 
+      if (Head != TBI.Head) 
+        return false; 
+      // It is almost always the case that TBI belongs to the same trace as 
+      // this block, but rare convoluted cases involving irreducible control 
+      // flow, a dominator may share a trace head without actually being on the 
+      // same trace as TBI. This is not a big problem as long as it doesn't 
+      // increase the instruction depth. 
+      return HasValidInstrDepths && InstrDepth <= TBI.InstrDepth; 
+    } 
+ 
+    // Data-dependency-related information. Per-instruction depth and height 
+    // are computed from data dependencies in the current trace, using 
+    // itinerary data. 
+ 
+    /// Instruction depths have been computed. This implies hasValidDepth(). 
+    bool HasValidInstrDepths = false; 
+ 
+    /// Instruction heights have been computed. This implies hasValidHeight(). 
+    bool HasValidInstrHeights = false; 
+ 
+    /// Critical path length. This is the number of cycles in the longest data 
+    /// dependency chain through the trace. This is only valid when both 
+    /// HasValidInstrDepths and HasValidInstrHeights are set. 
+    unsigned CriticalPath; 
+ 
+    /// Live-in registers. These registers are defined above the current block 
+    /// and used by this block or a block below it. 
+    /// This does not include PHI uses in the current block, but it does 
+    /// include PHI uses in deeper blocks. 
+    SmallVector<LiveInReg, 4> LiveIns; 
+ 
+    void print(raw_ostream&) const; 
+  }; 
+ 
+  /// InstrCycles represents the cycle height and depth of an instruction in a 
+  /// trace. 
+  struct InstrCycles { 
+    /// Earliest issue cycle as determined by data dependencies and instruction 
+    /// latencies from the beginning of the trace. Data dependencies from 
+    /// before the trace are not included. 
+    unsigned Depth; 
+ 
+    /// Minimum number of cycles from this instruction is issued to the of the 
+    /// trace, as determined by data dependencies and instruction latencies. 
+    unsigned Height; 
+  }; 
+ 
+  /// A trace represents a plausible sequence of executed basic blocks that 
+  /// passes through the current basic block one. The Trace class serves as a 
+  /// 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; 
+    } 
+ 
+    /// Return the resource depth of the top/bottom of the trace center block. 
+    /// This is the number of cycles required to execute all instructions from 
+    /// the trace head to the trace center block. The resource depth only 
+    /// considers execution resources, it ignores data dependencies. 
+    /// When Bottom is set, instructions in the trace center block are included. 
+    unsigned getResourceDepth(bool Bottom) const; 
+ 
+    /// Return the resource length of the trace. This is the number of cycles 
+    /// required to execute the instructions in the trace if they were all 
+    /// independent, exposing the maximum instruction-level parallelism. 
+    /// 
+    /// Any blocks in Extrablocks are included as if they were part of the 
+    /// trace. Likewise, extra resources required by the specified scheduling 
+    /// classes are included. For the caller to account for extra machine 
+    /// instructions, it must first resolve each instruction's scheduling class. 
+    unsigned getResourceLength( 
+        ArrayRef<const MachineBasicBlock *> Extrablocks = None, 
+        ArrayRef<const MCSchedClassDesc *> ExtraInstrs = None, 
+        ArrayRef<const MCSchedClassDesc *> RemoveInstrs = None) const; 
+ 
+    /// Return the length of the (data dependency) critical path through the 
+    /// trace. 
+    unsigned getCriticalPath() const { return TBI.CriticalPath; } 
+ 
+    /// Return the depth and height of MI. The depth is only valid for 
+    /// instructions in or above the trace center block. The height is only 
+    /// valid for instructions in or below the trace center block. 
+    InstrCycles getInstrCycles(const MachineInstr &MI) const { 
+      return TE.Cycles.lookup(&MI); 
+    } 
+ 
+    /// Return the slack of MI. This is the number of cycles MI can be delayed 
+    /// before the critical path becomes longer. 
+    /// MI must be an instruction in the trace center block. 
+    unsigned getInstrSlack(const MachineInstr &MI) const; 
+ 
+    /// Return the Depth of a PHI instruction in a trace center block successor. 
+    /// The PHI does not have to be part of the trace. 
+    unsigned getPHIDepth(const MachineInstr &PHI) const; 
+ 
+    /// A dependence is useful if the basic block of the defining instruction 
+    /// is part of the trace of the user instruction. It is assumed that DefMI 
+    /// dominates UseMI (see also isUsefulDominator). 
+    bool isDepInTrace(const MachineInstr &DefMI, 
+                      const MachineInstr &UseMI) const; 
+  }; 
+ 
+  /// A trace ensemble is a collection of traces selected using the same 
+  /// strategy, for example 'minimum resource height'. There is one trace for 
+  /// every block in the function. 
+  class Ensemble { 
+    friend class Trace; 
+ 
+    SmallVector<TraceBlockInfo, 4> BlockInfo; 
+    DenseMap<const MachineInstr*, InstrCycles> Cycles; 
+    SmallVector<unsigned, 0> ProcResourceDepths; 
+    SmallVector<unsigned, 0> ProcResourceHeights; 
+ 
+    void computeTrace(const MachineBasicBlock*); 
+    void computeDepthResources(const MachineBasicBlock*); 
+    void computeHeightResources(const MachineBasicBlock*); 
+    unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&); 
+    void computeInstrDepths(const MachineBasicBlock*); 
+    void computeInstrHeights(const MachineBasicBlock*); 
+    void addLiveIns(const MachineInstr *DefMI, unsigned DefOp, 
+                    ArrayRef<const MachineBasicBlock*> Trace); 
+ 
+  protected: 
+    MachineTraceMetrics &MTM; 
+ 
+    explicit Ensemble(MachineTraceMetrics*); 
+ 
+    virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0; 
+    virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0; 
+    const MachineLoop *getLoopFor(const MachineBasicBlock*) const; 
+    const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const; 
+    const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const; 
+    ArrayRef<unsigned> getProcResourceDepths(unsigned MBBNum) const; 
+    ArrayRef<unsigned> getProcResourceHeights(unsigned MBBNum) const; 
+ 
+  public: 
+    virtual ~Ensemble(); 
+ 
+    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(TraceBlockInfo &TBI, const MachineInstr&, 
+                     SparseSet<LiveRegUnit> &RegUnits); 
+    void updateDepth(const MachineBasicBlock *, const MachineInstr&, 
+                     SparseSet<LiveRegUnit> &RegUnits); 
+ 
+    /// Updates the depth of the instructions from Start to End. 
+    void updateDepths(MachineBasicBlock::iterator Start, 
+                      MachineBasicBlock::iterator End, 
+                      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] 
+  // where Kinds = SchedModel.getNumProcResourceKinds(). 
+  SmallVector<unsigned, 0> ProcResourceCycles; 
+ 
+  // One ensemble per strategy. 
+  Ensemble* Ensembles[TS_NumStrategies]; 
+ 
+  // Convert scaled resource usage to a cycle count that can be compared with 
+  // latencies. 
+  unsigned getCycles(unsigned Scaled) { 
+    unsigned Factor = SchedModel.getLatencyFactor(); 
+    return (Scaled + Factor - 1) / Factor; 
+  } 
+}; 
+ 
+inline raw_ostream &operator<<(raw_ostream &OS, 
+                               const MachineTraceMetrics::Trace &Tr) { 
+  Tr.print(OS); 
+  return OS; 
+} 
+ 
+inline raw_ostream &operator<<(raw_ostream &OS, 
+                               const MachineTraceMetrics::Ensemble &En) { 
+  En.print(OS); 
+  return OS; 
+} 
+ 
+} // end namespace llvm 
+ 
+#endif // LLVM_CODEGEN_MACHINETRACEMETRICS_H 
+ 
+#ifdef __GNUC__ 
+#pragma GCC diagnostic pop 
+#endif