//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// 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_MACHINETRACEMETRICS_H
#define LLVM_CODEGEN_MACHINETRACEMETRICS_H
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/TargetSchedule.h"
namespace llvm {
class AnalysisUsage;
class MachineFunction;
class MachineInstr;
class MachineLoop;
class MachineLoopInfo;
class MachineRegisterInfo;
struct MCSchedClassDesc;
class raw_ostream;
class TargetInstrInfo;
class TargetRegisterInfo;
// Keep track of physreg data dependencies by recording each live register unit.
// Associate each regunit with an instruction operand. Depending on the
// direction instructions are scanned, it could be the operand that defined the
// regunit, or the highest operand to read the regunit.
struct LiveRegUnit {
unsigned RegUnit;
unsigned Cycle = 0;
const MachineInstr *MI = nullptr;
unsigned Op = 0;
unsigned getSparseSetIndex() const { return RegUnit; }
LiveRegUnit(unsigned RU) : RegUnit(RU) {}
};
class MachineTraceMetrics : public MachineFunctionPass {
const MachineFunction *MF = nullptr;
const TargetInstrInfo *TII = nullptr;
const TargetRegisterInfo *TRI = nullptr;
const MachineRegisterInfo *MRI = nullptr;
const MachineLoopInfo *Loops = nullptr;
TargetSchedModel SchedModel;
public:
friend class Ensemble;
friend class Trace;
class Ensemble;
static char ID;
MachineTraceMetrics();
void getAnalysisUsage(AnalysisUsage&) const override;
bool runOnMachineFunction(MachineFunction&) override;
void releaseMemory() override;
void verifyAnalysis() const override;
/// 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 = ~0u;
/// True when the block contains calls.
bool HasCalls = false;
FixedBlockInfo() = default;
/// 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*);
/// Get the scaled number of cycles used per processor resource in MBB.
/// This is an array with SchedModel.getNumProcResourceKinds() entries.
/// The getResources() function above must have been called first.
///
/// These numbers have already been scaled by SchedModel.getResourceFactor().
ArrayRef<unsigned> getProcResourceCycles(unsigned MBBNum) const;
/// A virtual register or regunit required by a basic block or its trace
/// successors.
struct LiveInReg {
/// The virtual register required, or a register unit.
Register Reg;
/// For virtual registers: Minimum height of the defining instruction.
/// For regunits: Height of the highest user in the trace.
unsigned Height;
LiveInReg(Register 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 = nullptr;
/// Trace successor, or NULL for the last block in the trace.
/// Valid when hasValidHeight().
const MachineBasicBlock *Succ = nullptr;
/// 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 = ~0u;
/// Accumulated number of instructions in the trace below this block.
/// Includes instructions in this block.
unsigned InstrHeight = ~0u;
TraceBlockInfo() = default;
/// 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; }
/// Assuming that this is a dominator of TBI, determine if it contains
/// useful instruction depths. A dominating block can be above the current
/// trace head, and any dependencies from such a far away dominator are not
/// expected to affect the critical path.
///
/// Also returns true when TBI == this.
bool isUsefulDominator(const TraceBlockInfo &TBI) const {
// The trace for TBI may not even be calculated yet.
if (!hasValidDepth() || !TBI.hasValidDepth())
return false;
// Instruction depths are only comparable if the traces share a head.
if (Head != TBI.Head)
return false;
// It is almost always the case that TBI belongs to the same trace as
// this block, but rare convoluted cases involving irreducible control
// flow, a dominator may share a trace head without actually being on the
// same trace as TBI. This is not a big problem as long as it doesn't
// increase the instruction depth.
return HasValidInstrDepths && 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 = false;
/// Instruction heights have been computed. This implies hasValidHeight().
bool HasValidInstrHeights = false;
/// 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. Likewise, extra resources required by the specified scheduling
/// classes are included. For the caller to account for extra machine
/// instructions, it must first resolve each instruction's scheduling class.
unsigned getResourceLength(
ArrayRef<const MachineBasicBlock *> Extrablocks = std::nullopt,
ArrayRef<const MCSchedClassDesc *> ExtraInstrs = std::nullopt,
ArrayRef<const MCSchedClassDesc *> RemoveInstrs = std::nullopt) 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 dependence is useful if the basic block of the defining instruction
/// is part of the trace of the user instruction. It is assumed that DefMI
/// dominates UseMI (see also isUsefulDominator).
bool isDepInTrace(const MachineInstr &DefMI,
const MachineInstr &UseMI) 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 {
friend class Trace;
SmallVector<TraceBlockInfo, 4> BlockInfo;
DenseMap<const MachineInstr*, InstrCycles> Cycles;
SmallVector<unsigned, 0> ProcResourceDepths;
SmallVector<unsigned, 0> ProcResourceHeights;
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;
explicit Ensemble(MachineTraceMetrics*);
virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
ArrayRef<unsigned> getProcResourceDepths(unsigned MBBNum) const;
ArrayRef<unsigned> getProcResourceHeights(unsigned MBBNum) 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);
/// Updates the depth of an machine instruction, given RegUnits.
void updateDepth(TraceBlockInfo &TBI, const MachineInstr&,
SparseSet<LiveRegUnit> &RegUnits);
void updateDepth(const MachineBasicBlock *, const MachineInstr&,
SparseSet<LiveRegUnit> &RegUnits);
/// Updates the depth of the instructions from Start to End.
void updateDepths(MachineBasicBlock::iterator Start,
MachineBasicBlock::iterator End,
SparseSet<LiveRegUnit> &RegUnits);
};
/// 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;
// Cycles consumed on each processor resource per block.
// The number of processor resource kinds is constant for a given subtarget,
// but it is not known at compile time. The number of cycles consumed by
// block B on processor resource R is at ProcResourceCycles[B*Kinds + R]
// where Kinds = SchedModel.getNumProcResourceKinds().
SmallVector<unsigned, 0> ProcResourceCycles;
// One ensemble per strategy.
Ensemble* Ensembles[TS_NumStrategies];
// Convert scaled resource usage to a cycle count that can be compared with
// latencies.
unsigned getCycles(unsigned Scaled) {
unsigned Factor = SchedModel.getLatencyFactor();
return (Scaled + Factor - 1) / Factor;
}
};
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 // LLVM_CODEGEN_MACHINETRACEMETRICS_H