contrib/llvm/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/ArrayRef.h"
  51 #include "llvm/ADT/DenseMap.h"
  52 #include "llvm/CodeGen/MachineFunctionPass.h"
  53 #include "llvm/CodeGen/TargetSchedule.h"
  54
  55 namespace llvm {
  56
  57 class InstrItineraryData;
  58 class MachineBasicBlock;
  59 class MachineInstr;
  60 class MachineLoop;
  61 class MachineLoopInfo;
  62 class MachineRegisterInfo;
  63 class TargetInstrInfo;
  64 class TargetRegisterInfo;
  65 class raw_ostream;
  66
  67 class MachineTraceMetrics : public MachineFunctionPass {
  68   const MachineFunction *MF;
  69   const TargetInstrInfo *TII;
  70   const TargetRegisterInfo *TRI;
  71   const MachineRegisterInfo *MRI;
  72   const MachineLoopInfo *Loops;
  73   TargetSchedModel SchedModel;
  74
  75 public:
  76   class Ensemble;
  77   class Trace;
  78   static char ID;
  79   MachineTraceMetrics();
  80   void getAnalysisUsage(AnalysisUsage&) const;
  81   bool runOnMachineFunction(MachineFunction&);
  82   void releaseMemory();
  83   void verifyAnalysis() const;
  84
  85   friend class Ensemble;
  86   friend class Trace;
  87
  88   /// Per-basic block information that doesn't depend on the trace through the
  89   /// block.
  90   struct FixedBlockInfo {
  91     /// The number of non-trivial instructions in the block.
  92     /// Doesn't count PHI and COPY instructions that are likely to be removed.
  93     unsigned InstrCount;
  94
  95     /// True when the block contains calls.
  96     bool HasCalls;
  97
  98     FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {}
  99
 100     /// Returns true when resource information for this block has been computed.
 101     bool hasResources() const { return InstrCount != ~0u; }
 102
 103     /// Invalidate resource information.
 104     void invalidate() { InstrCount = ~0u; }
 105   };
 106
 107   /// Get the fixed resource information about MBB. Compute it on demand.
 108   const FixedBlockInfo *getResources(const MachineBasicBlock*);
 109
 110   /// A virtual register or regunit required by a basic block or its trace
 111   /// successors.
 112   struct LiveInReg {
 113     /// The virtual register required, or a register unit.
 114     unsigned Reg;
 115
 116     /// For virtual registers: Minimum height of the defining instruction.
 117     /// For regunits: Height of the highest user in the trace.
 118     unsigned Height;
 119
 120     LiveInReg(unsigned Reg, unsigned Height = 0) : Reg(Reg), Height(Height) {}
 121   };
 122
 123   /// Per-basic block information that relates to a specific trace through the
 124   /// block. Convergent traces means that only one of these is required per
 125   /// block in a trace ensemble.
 126   struct TraceBlockInfo {
 127     /// Trace predecessor, or NULL for the first block in the trace.
 128     /// Valid when hasValidDepth().
 129     const MachineBasicBlock *Pred;
 130
 131     /// Trace successor, or NULL for the last block in the trace.
 132     /// Valid when hasValidHeight().
 133     const MachineBasicBlock *Succ;
 134
 135     /// The block number of the head of the trace. (When hasValidDepth()).
 136     unsigned Head;
 137
 138     /// The block number of the tail of the trace. (When hasValidHeight()).
 139     unsigned Tail;
 140
 141     /// Accumulated number of instructions in the trace above this block.
 142     /// Does not include instructions in this block.
 143     unsigned InstrDepth;
 144
 145     /// Accumulated number of instructions in the trace below this block.
 146     /// Includes instructions in this block.
 147     unsigned InstrHeight;
 148
 149     TraceBlockInfo() :
 150       Pred(0), Succ(0),
 151       InstrDepth(~0u), InstrHeight(~0u),
 152       HasValidInstrDepths(false), HasValidInstrHeights(false) {}
 153
 154     /// Returns true if the depth resources have been computed from the trace
 155     /// above this block.
 156     bool hasValidDepth() const { return InstrDepth != ~0u; }
 157
 158     /// Returns true if the height resources have been computed from the trace
 159     /// below this block.
 160     bool hasValidHeight() const { return InstrHeight != ~0u; }
 161
 162     /// Invalidate depth resources when some block above this one has changed.
 163     void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; }
 164
 165     /// Invalidate height resources when a block below this one has changed.
 166     void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; }
 167
 168     /// Determine if this block belongs to the same trace as TBI and comes
 169     /// before it in the trace.
 170     /// Also returns true when TBI == this.
 171     bool isEarlierInSameTrace(const TraceBlockInfo &TBI) const {
 172       return hasValidDepth() && TBI.hasValidDepth() &&
 173         Head == TBI.Head && InstrDepth <= TBI.InstrDepth;
 174     }
 175
 176     // Data-dependency-related information. Per-instruction depth and height
 177     // are computed from data dependencies in the current trace, using
 178     // itinerary data.
 179
 180     /// Instruction depths have been computed. This implies hasValidDepth().
 181     bool HasValidInstrDepths;
 182
 183     /// Instruction heights have been computed. This implies hasValidHeight().
 184     bool HasValidInstrHeights;
 185
 186     /// Critical path length. This is the number of cycles in the longest data
 187     /// dependency chain through the trace. This is only valid when both
 188     /// HasValidInstrDepths and HasValidInstrHeights are set.
 189     unsigned CriticalPath;
 190
 191     /// Live-in registers. These registers are defined above the current block
 192     /// and used by this block or a block below it.
 193     /// This does not include PHI uses in the current block, but it does
 194     /// include PHI uses in deeper blocks.
 195     SmallVector<LiveInReg, 4> LiveIns;
 196
 197     void print(raw_ostream&) const;
 198   };
 199
 200   /// InstrCycles represents the cycle height and depth of an instruction in a
 201   /// trace.
 202   struct InstrCycles {
 203     /// Earliest issue cycle as determined by data dependencies and instruction
 204     /// latencies from the beginning of the trace. Data dependencies from
 205     /// before the trace are not included.
 206     unsigned Depth;
 207
 208     /// Minimum number of cycles from this instruction is issued to the of the
 209     /// trace, as determined by data dependencies and instruction latencies.
 210     unsigned Height;
 211   };
 212
 213   /// A trace represents a plausible sequence of executed basic blocks that
 214   /// passes through the current basic block one. The Trace class serves as a
 215   /// handle to internal cached data structures.
 216   class Trace {
 217     Ensemble &TE;
 218     TraceBlockInfo &TBI;
 219
 220     unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; }
 221
 222   public:
 223     explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {}
 224     void print(raw_ostream&) const;
 225
 226     /// Compute the total number of instructions in the trace.
 227     unsigned getInstrCount() const {
 228       return TBI.InstrDepth + TBI.InstrHeight;
 229     }
 230
 231     /// Return the resource depth of the top/bottom of the trace center block.
 232     /// This is the number of cycles required to execute all instructions from
 233     /// the trace head to the trace center block. The resource depth only
 234     /// considers execution resources, it ignores data dependencies.
 235     /// When Bottom is set, instructions in the trace center block are included.
 236     unsigned getResourceDepth(bool Bottom) const;
 237
 238     /// Return the resource length of the trace. This is the number of cycles
 239     /// required to execute the instructions in the trace if they were all
 240     /// independent, exposing the maximum instruction-level parallelism.
 241     ///
 242     /// Any blocks in Extrablocks are included as if they were part of the
 243     /// trace.
 244     unsigned getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks =
 245                                ArrayRef<const MachineBasicBlock*>()) const;
 246
 247     /// Return the length of the (data dependency) critical path through the
 248     /// trace.
 249     unsigned getCriticalPath() const { return TBI.CriticalPath; }
 250
 251     /// Return the depth and height of MI. The depth is only valid for
 252     /// instructions in or above the trace center block. The height is only
 253     /// valid for instructions in or below the trace center block.
 254     InstrCycles getInstrCycles(const MachineInstr *MI) const {
 255       return TE.Cycles.lookup(MI);
 256     }
 257
 258     /// Return the slack of MI. This is the number of cycles MI can be delayed
 259     /// before the critical path becomes longer.
 260     /// MI must be an instruction in the trace center block.
 261     unsigned getInstrSlack(const MachineInstr *MI) const;
 262
 263     /// Return the Depth of a PHI instruction in a trace center block successor.
 264     /// The PHI does not have to be part of the trace.
 265     unsigned getPHIDepth(const MachineInstr *PHI) const;
 266   };
 267
 268   /// A trace ensemble is a collection of traces selected using the same
 269   /// strategy, for example 'minimum resource height'. There is one trace for
 270   /// every block in the function.
 271   class Ensemble {
 272     SmallVector<TraceBlockInfo, 4> BlockInfo;
 273     DenseMap<const MachineInstr*, InstrCycles> Cycles;
 274     friend class Trace;
 275
 276     void computeTrace(const MachineBasicBlock*);
 277     void computeDepthResources(const MachineBasicBlock*);
 278     void computeHeightResources(const MachineBasicBlock*);
 279     unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&);
 280     void computeInstrDepths(const MachineBasicBlock*);
 281     void computeInstrHeights(const MachineBasicBlock*);
 282     void addLiveIns(const MachineInstr *DefMI, unsigned DefOp,
 283                     ArrayRef<const MachineBasicBlock*> Trace);
 284
 285   protected:
 286     MachineTraceMetrics &MTM;
 287     virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
 288     virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
 289     explicit Ensemble(MachineTraceMetrics*);
 290     const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
 291     const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
 292     const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
 293
 294   public:
 295     virtual ~Ensemble();
 296     virtual const char *getName() const =0;
 297     void print(raw_ostream&) const;
 298     void invalidate(const MachineBasicBlock *MBB);
 299     void verify() const;
 300
 301     /// Get the trace that passes through MBB.
 302     /// The trace is computed on demand.
 303     Trace getTrace(const MachineBasicBlock *MBB);
 304   };
 305
 306   /// Strategies for selecting traces.
 307   enum Strategy {
 308     /// Select the trace through a block that has the fewest instructions.
 309     TS_MinInstrCount,
 310
 311     TS_NumStrategies
 312   };
 313
 314   /// Get the trace ensemble representing the given trace selection strategy.
 315   /// The returned Ensemble object is owned by the MachineTraceMetrics analysis,
 316   /// and valid for the lifetime of the analysis pass.
 317   Ensemble *getEnsemble(Strategy);
 318
 319   /// Invalidate cached information about MBB. This must be called *before* MBB
 320   /// is erased, or the CFG is otherwise changed.
 321   ///
 322   /// This invalidates per-block information about resource usage for MBB only,
 323   /// and it invalidates per-trace information for any trace that passes
 324   /// through MBB.
 325   ///
 326   /// Call Ensemble::getTrace() again to update any trace handles.
 327   void invalidate(const MachineBasicBlock *MBB);
 328
 329 private:
 330   // One entry per basic block, indexed by block number.
 331   SmallVector<FixedBlockInfo, 4> BlockInfo;
 332
 333   // One ensemble per strategy.
 334   Ensemble* Ensembles[TS_NumStrategies];
 335 };
 336
 337 inline raw_ostream &operator<<(raw_ostream &OS,
 338                                const MachineTraceMetrics::Trace &Tr) {
 339   Tr.print(OS);
 340   return OS;
 341 }
 342
 343 inline raw_ostream &operator<<(raw_ostream &OS,
 344                                const MachineTraceMetrics::Ensemble &En) {
 345   En.print(OS);
 346   return OS;
 347 }
 348 } // end namespace llvm
 349
 350 #endif