Move MachineTraceMetrics.h into include/llvm/CodeGen.

Let targets use it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172688 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 3 insertions, 354 deletions

diff --git a/lib/CodeGen/EarlyIfConversion.cpp b/lib/CodeGen/EarlyIfConversion.cpp
index f332925b0e..fac207e3b3 100644
--- a/lib/CodeGen/EarlyIfConversion.cpp
+++ b/lib/CodeGen/EarlyIfConversion.cpp
@@ -17,8 +17,6 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "early-ifcvt"
-#include "llvm/CodeGen/Passes.h"
-#include "MachineTraceMetrics.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
@@ -31,6 +29,8 @@
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineTraceMetrics.h"
+#include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
diff --git a/lib/CodeGen/MachineTraceMetrics.cpp b/lib/CodeGen/MachineTraceMetrics.cpp
index 685ccab162..f77a7b17ed 100644
--- a/lib/CodeGen/MachineTraceMetrics.cpp
+++ b/lib/CodeGen/MachineTraceMetrics.cpp
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "machine-trace-metrics"
-#include "MachineTraceMetrics.h"
+#include "llvm/CodeGen/MachineTraceMetrics.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SparseSet.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
diff --git a/lib/CodeGen/MachineTraceMetrics.h b/lib/CodeGen/MachineTraceMetrics.h
deleted file mode 100644
index 460730b040..0000000000
--- a/lib/CodeGen/MachineTraceMetrics.h
+++ /dev/null
@@ -1,350 +0,0 @@
-//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// 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_MACHINE_TRACE_METRICS_H
-#define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/TargetSchedule.h"
-
-namespace llvm {
-
-class InstrItineraryData;
-class MachineBasicBlock;
-class MachineInstr;
-class MachineLoop;
-class MachineLoopInfo;
-class MachineRegisterInfo;
-class TargetInstrInfo;
-class TargetRegisterInfo;
-class raw_ostream;
-
-class MachineTraceMetrics : public MachineFunctionPass {
-  const MachineFunction *MF;
-  const TargetInstrInfo *TII;
-  const TargetRegisterInfo *TRI;
-  const MachineRegisterInfo *MRI;
-  const MachineLoopInfo *Loops;
-  TargetSchedModel SchedModel;
-
-public:
-  class Ensemble;
-  class Trace;
-  static char ID;
-  MachineTraceMetrics();
-  void getAnalysisUsage(AnalysisUsage&) const;
-  bool runOnMachineFunction(MachineFunction&);
-  void releaseMemory();
-  void verifyAnalysis() const;
-
-  friend class Ensemble;
-  friend class Trace;
-
-  /// 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;
-
-    /// True when the block contains calls.
-    bool HasCalls;
-
-    FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {}
-
-    /// 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*);
-
-  /// A virtual register or regunit required by a basic block or its trace
-  /// successors.
-  struct LiveInReg {
-    /// The virtual register required, or a register unit.
-    unsigned Reg;
-
-    /// For virtual registers: Minimum height of the defining instruction.
-    /// For regunits: Height of the highest user in the trace.
-    unsigned Height;
-
-    LiveInReg(unsigned 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;
-
-    /// Trace successor, or NULL for the last block in the trace.
-    /// Valid when hasValidHeight().
-    const MachineBasicBlock *Succ;
-
-    /// 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;
-
-    /// Accumulated number of instructions in the trace below this block.
-    /// Includes instructions in this block.
-    unsigned InstrHeight;
-
-    TraceBlockInfo() :
-      Pred(0), Succ(0),
-      InstrDepth(~0u), InstrHeight(~0u),
-      HasValidInstrDepths(false), HasValidInstrHeights(false) {}
-
-    /// 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; }
-
-    /// Determine if this block belongs to the same trace as TBI and comes
-    /// before it in the trace.
-    /// Also returns true when TBI == this.
-    bool isEarlierInSameTrace(const TraceBlockInfo &TBI) const {
-      return hasValidDepth() && TBI.hasValidDepth() &&
-        Head == TBI.Head && 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;
-
-    /// Instruction heights have been computed. This implies hasValidHeight().
-    bool HasValidInstrHeights;
-
-    /// 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.
-    unsigned getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks =
-                               ArrayRef<const MachineBasicBlock*>()) 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 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 {
-    SmallVector<TraceBlockInfo, 4> BlockInfo;
-    DenseMap<const MachineInstr*, InstrCycles> Cycles;
-    friend class Trace;
-
-    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;
-    virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
-    virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
-    explicit Ensemble(MachineTraceMetrics*);
-    const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
-    const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
-    const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) 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);
-  };
-
-  /// 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;
-
-  // One ensemble per strategy.
-  Ensemble* Ensembles[TS_NumStrategies];
-};
-
-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
diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp
index 42502eb238..c173293f6f 100644
--- a/lib/CodeGen/StackColoring.cpp
+++ b/lib/CodeGen/StackColoring.cpp
@@ -23,7 +23,6 @@
 
 #define DEBUG_TYPE "stackcoloring"
 #include "llvm/CodeGen/Passes.h"
-#include "MachineTraceMetrics.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PostOrderIterator.h"