diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/MachineTraceMetrics.h')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/MachineTraceMetrics.h | 350 |
1 files changed, 0 insertions, 350 deletions
diff --git a/contrib/llvm/lib/CodeGen/MachineTraceMetrics.h b/contrib/llvm/lib/CodeGen/MachineTraceMetrics.h deleted file mode 100644 index 460730b..0000000 --- a/contrib/llvm/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 |
