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 55namespace llvm { 56 57class InstrItineraryData; 58class MachineBasicBlock; 59class MachineInstr; 60class MachineLoop; 61class MachineLoopInfo; 62class MachineRegisterInfo; 63class TargetInstrInfo; 64class TargetRegisterInfo; 65class raw_ostream; 66 67class 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 75public: 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 329private: 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 337inline raw_ostream &operator<<(raw_ostream &OS, 338 const MachineTraceMetrics::Trace &Tr) { 339 Tr.print(OS); 340 return OS; 341} 342 343inline 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 351