X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineTraceMetrics.h;h=460730b040591c7cebc0ecbc8945f5e228f7ffd5;hb=fb9ebbf236974beac31705eaeb9f50ab585af6ab;hp=732e4f6ef397a06d753cc63af57cd5e37387b33d;hpb=20f13c50d88560d75129f4a691fe6b477d04dc70;p=oota-llvm.git diff --git a/lib/CodeGen/MachineTraceMetrics.h b/lib/CodeGen/MachineTraceMetrics.h index 732e4f6ef39..460730b0405 100644 --- a/lib/CodeGen/MachineTraceMetrics.h +++ b/lib/CodeGen/MachineTraceMetrics.h @@ -47,17 +47,21 @@ #ifndef LLVM_CODEGEN_MACHINE_TRACE_METRICS_H #define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/TargetSchedule.h" namespace llvm { -class TargetInstrInfo; -class TargetRegisterInfo; +class InstrItineraryData; class MachineBasicBlock; -class MachineRegisterInfo; -class MachineLoopInfo; +class MachineInstr; class MachineLoop; +class MachineLoopInfo; +class MachineRegisterInfo; +class TargetInstrInfo; +class TargetRegisterInfo; class raw_ostream; class MachineTraceMetrics : public MachineFunctionPass { @@ -66,6 +70,7 @@ class MachineTraceMetrics : public MachineFunctionPass { const TargetRegisterInfo *TRI; const MachineRegisterInfo *MRI; const MachineLoopInfo *Loops; + TargetSchedModel SchedModel; public: class Ensemble; @@ -102,6 +107,19 @@ public: /// 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. @@ -128,7 +146,10 @@ public: /// Includes instructions in this block. unsigned InstrHeight; - TraceBlockInfo() : Pred(0), Succ(0), InstrDepth(~0u), InstrHeight(~0u) {} + 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. @@ -139,14 +160,56 @@ public: bool hasValidHeight() const { return InstrHeight != ~0u; } /// Invalidate depth resources when some block above this one has changed. - void invalidateDepth() { InstrDepth = ~0u; } + void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; } /// Invalidate height resources when a block below this one has changed. - void invalidateHeight() { InstrHeight = ~0u; } + 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 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. @@ -154,6 +217,8 @@ public: 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; @@ -162,6 +227,42 @@ public: 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 Extrablocks = + ArrayRef()) 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 @@ -169,14 +270,20 @@ public: /// every block in the function. class Ensemble { SmallVector BlockInfo; + DenseMap 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 Trace); protected: - MachineTraceMetrics &CT; + MachineTraceMetrics &MTM; virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0; virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0; explicit Ensemble(MachineTraceMetrics*);