lib/CodeGen/MachineTraceMetrics.h

   1 //===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the interface for the MachineTraceMetrics analysis pass
  11 // that estimates CPU resource usage and critical data dependency paths through
  12 // preferred traces. This is useful for super-scalar CPUs where execution speed
  13 // can be limited both by data dependencies and by limited execution resources.
  14 //
  15 // Out-of-order CPUs will often be executing instructions from multiple basic
  16 // blocks at the same time. This makes it difficult to estimate the resource
  17 // usage accurately in a single basic block. Resources can be estimated better
  18 // by looking at a trace through the current basic block.
  19 //
  20 // For every block, the MachineTraceMetrics pass will pick a preferred trace
  21 // that passes through the block. The trace is chosen based on loop structure,
  22 // branch probabilities, and resource usage. The intention is to pick likely
  23 // traces that would be the most affected by code transformations.
  24 //
  25 // It is expensive to compute a full arbitrary trace for every block, so to
  26 // save some computations, traces are chosen to be convergent. This means that
  27 // if the traces through basic blocks A and B ever cross when moving away from
  28 // A and B, they never diverge again. This applies in both directions - If the
  29 // traces meet above A and B, they won't diverge when going further back.
  30 //
  31 // Traces tend to align with loops. The trace through a block in an inner loop
  32 // will begin at the loop entry block and end at a back edge. If there are
  33 // nested loops, the trace may begin and end at those instead.
  34 //
  35 // For each trace, we compute the critical path length, which is the number of
  36 // cycles required to execute the trace when execution is limited by data
  37 // dependencies only. We also compute the resource height, which is the number
  38 // of cycles required to execute all instructions in the trace when ignoring
  39 // data dependencies.
  40 //
  41 // Every instruction in the current block has a slack - the number of cycles
  42 // execution of the instruction can be delayed without extending the critical
  43 // path.
  44 //
  45 //===----------------------------------------------------------------------===//
  46
  47 #ifndef LLVM_CODEGEN_MACHINE_TRACE_METRICS_H
  48 #define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H
  49
  50 #include "llvm/ADT/SmallVector.h"
  51 #include "llvm/CodeGen/MachineFunctionPass.h"
  52
  53 namespace llvm {
  54
  55 class TargetInstrInfo;
  56 class TargetRegisterInfo;
  57 class MachineBasicBlock;
  58 class MachineRegisterInfo;
  59 class MachineLoopInfo;
  60 class MachineLoop;
  61 class raw_ostream;
  62
  63 class MachineTraceMetrics : public MachineFunctionPass {
  64   const MachineFunction *MF;
  65   const TargetInstrInfo *TII;
  66   const TargetRegisterInfo *TRI;
  67   const MachineRegisterInfo *MRI;
  68   const MachineLoopInfo *Loops;
  69
  70 public:
  71   class Ensemble;
  72   class Trace;
  73   static char ID;
  74   MachineTraceMetrics();
  75   void getAnalysisUsage(AnalysisUsage&) const;
  76   bool runOnMachineFunction(MachineFunction&);
  77   void releaseMemory();
  78
  79   friend class Ensemble;
  80   friend class Trace;
  81
  82   /// Per-basic block information that doesn't depend on the trace through the
  83   /// block.
  84   struct FixedBlockInfo {
  85     /// The number of non-trivial instructions in the block.
  86     /// Doesn't count PHI and COPY instructions that are likely to be removed.
  87     unsigned InstrCount;
  88
  89     /// True when the block contains calls.
  90     bool HasCalls;
  91
  92     FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {}
  93
  94     /// Returns true when resource information for this block has been computed.
  95     bool hasResources() const { return InstrCount != ~0u; }
  96
  97     /// Invalidate resource information.
  98     void invalidate() { InstrCount = ~0u; }
  99   };
 100
 101   /// Get the fixed resource information about MBB. Compute it on demand.
 102   const FixedBlockInfo *getResources(const MachineBasicBlock*);
 103
 104   /// Per-basic block information that relates to a specific trace through the
 105   /// block. Convergent traces means that only one of these is required per
 106   /// block in a trace ensemble.
 107   struct TraceBlockInfo {
 108     /// Trace predecessor, or NULL for the first block in the trace.
 109     /// Valid when hasValidDepth().
 110     const MachineBasicBlock *Pred;
 111
 112     /// Trace successor, or NULL for the last block in the trace.
 113     /// Valid when hasValidHeight().
 114     const MachineBasicBlock *Succ;
 115
 116     /// The block number of the head of the trace. (When hasValidDepth()).
 117     unsigned Head;
 118
 119     /// The block number of the tail of the trace. (When hasValidHeight()).
 120     unsigned Tail;
 121
 122     /// Accumulated number of instructions in the trace above this block.
 123     /// Does not include instructions in this block.
 124     unsigned InstrDepth;
 125
 126     /// Accumulated number of instructions in the trace below this block.
 127     /// Includes instructions in this block.
 128     unsigned InstrHeight;
 129
 130     TraceBlockInfo() : Pred(0), Succ(0), InstrDepth(~0u), InstrHeight(~0u) {}
 131
 132     /// Returns true if the depth resources have been computed from the trace
 133     /// above this block.
 134     bool hasValidDepth() const { return InstrDepth != ~0u; }
 135
 136     /// Returns true if the height resources have been computed from the trace
 137     /// below this block.
 138     bool hasValidHeight() const { return InstrHeight != ~0u; }
 139
 140     /// Invalidate depth resources when some block above this one has changed.
 141     void invalidateDepth() { InstrDepth = ~0u; }
 142
 143     /// Invalidate height resources when a block below this one has changed.
 144     void invalidateHeight() { InstrHeight = ~0u; }
 145
 146     void print(raw_ostream&) const;
 147   };
 148
 149   /// A trace represents a plausible sequence of executed basic blocks that
 150   /// passes through the current basic block one. The Trace class serves as a
 151   /// handle to internal cached data structures.
 152   class Trace {
 153     Ensemble &TE;
 154     TraceBlockInfo &TBI;
 155
 156   public:
 157     explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {}
 158     void print(raw_ostream&) const;
 159
 160     /// Compute the total number of instructions in the trace.
 161     unsigned getInstrCount() const {
 162       return TBI.InstrDepth + TBI.InstrHeight;
 163     }
 164   };
 165
 166   /// A trace ensemble is a collection of traces selected using the same
 167   /// strategy, for example 'minimum resource height'. There is one trace for
 168   /// every block in the function.
 169   class Ensemble {
 170     SmallVector<TraceBlockInfo, 4> BlockInfo;
 171     friend class Trace;
 172
 173     void computeTrace(const MachineBasicBlock*);
 174     void computeDepthResources(const MachineBasicBlock*);
 175     void computeHeightResources(const MachineBasicBlock*);
 176
 177   protected:
 178     MachineTraceMetrics &CT;
 179     virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
 180     virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
 181     explicit Ensemble(MachineTraceMetrics*);
 182     const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
 183     const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
 184     const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
 185
 186   public:
 187     virtual ~Ensemble();
 188     virtual const char *getName() const =0;
 189     void print(raw_ostream&) const;
 190     void invalidate(const MachineBasicBlock *MBB);
 191     void verify() const;
 192
 193     /// Get the trace that passes through MBB.
 194     /// The trace is computed on demand.
 195     Trace getTrace(const MachineBasicBlock *MBB);
 196   };
 197
 198   /// Strategies for selecting traces.
 199   enum Strategy {
 200     /// Select the trace through a block that has the fewest instructions.
 201     TS_MinInstrCount,
 202
 203     TS_NumStrategies
 204   };
 205
 206   /// Get the trace ensemble representing the given trace selection strategy.
 207   /// The returned Ensemble object is owned by the MachineTraceMetrics analysis,
 208   /// and valid for the lifetime of the analysis pass.
 209   Ensemble *getEnsemble(Strategy);
 210
 211   /// Invalidate cached information about MBB. This must be called *before* MBB
 212   /// is erased, or the CFG is otherwise changed.
 213   void invalidate(const MachineBasicBlock *MBB);
 214
 215   /// Verify the internal consistency of cached data.
 216   /// This does nothing in NDEBUG builds.
 217   void verify() const;
 218
 219 private:
 220   // One entry per basic block, indexed by block number.
 221   SmallVector<FixedBlockInfo, 4> BlockInfo;
 222
 223   // One ensemble per strategy.
 224   Ensemble* Ensembles[TS_NumStrategies];
 225 };
 226
 227 inline raw_ostream &operator<<(raw_ostream &OS,
 228                                const MachineTraceMetrics::Trace &Tr) {
 229   Tr.print(OS);
 230   return OS;
 231 }
 232
 233 inline raw_ostream &operator<<(raw_ostream &OS,
 234                                const MachineTraceMetrics::Ensemble &En) {
 235   En.print(OS);
 236   return OS;
 237 }
 238 } // end namespace llvm
 239
 240 #endif