19f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===// 29f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 39f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 49f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 59f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 69f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 79f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 89f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 99f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 109f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// This file defines the interface for the MachineTraceMetrics analysis pass 119f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// that estimates CPU resource usage and critical data dependency paths through 129f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// preferred traces. This is useful for super-scalar CPUs where execution speed 139f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// can be limited both by data dependencies and by limited execution resources. 149f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 159f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// Out-of-order CPUs will often be executing instructions from multiple basic 169f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// blocks at the same time. This makes it difficult to estimate the resource 179f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// usage accurately in a single basic block. Resources can be estimated better 189f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// by looking at a trace through the current basic block. 199f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 209f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// For every block, the MachineTraceMetrics pass will pick a preferred trace 219f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// that passes through the block. The trace is chosen based on loop structure, 229f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// branch probabilities, and resource usage. The intention is to pick likely 239f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// traces that would be the most affected by code transformations. 249f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 259f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// It is expensive to compute a full arbitrary trace for every block, so to 269f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// save some computations, traces are chosen to be convergent. This means that 279f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// if the traces through basic blocks A and B ever cross when moving away from 289f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// A and B, they never diverge again. This applies in both directions - If the 299f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// traces meet above A and B, they won't diverge when going further back. 309f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 319f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// Traces tend to align with loops. The trace through a block in an inner loop 329f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// will begin at the loop entry block and end at a back edge. If there are 339f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// nested loops, the trace may begin and end at those instead. 349f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 359f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// For each trace, we compute the critical path length, which is the number of 369f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// cycles required to execute the trace when execution is limited by data 379f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// dependencies only. We also compute the resource height, which is the number 389f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// of cycles required to execute all instructions in the trace when ignoring 399f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// data dependencies. 409f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 419f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// Every instruction in the current block has a slack - the number of cycles 429f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// execution of the instruction can be delayed without extending the critical 439f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// path. 449f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen// 459f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 469f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 479f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen#ifndef LLVM_CODEGEN_MACHINE_TRACE_METRICS_H 489f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen#define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H 499f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 50c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen#include "llvm/ADT/ArrayRef.h" 515f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 529f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 539f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 549f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesennamespace llvm { 559f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 565f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesenclass InstrItineraryData; 579f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesenclass MachineBasicBlock; 585f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesenclass MachineInstr; 599f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesenclass MachineLoop; 605f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesenclass MachineLoopInfo; 615f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesenclass MachineRegisterInfo; 625f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesenclass TargetInstrInfo; 635f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesenclass TargetRegisterInfo; 649f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesenclass raw_ostream; 659f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 669f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesenclass MachineTraceMetrics : public MachineFunctionPass { 67a1b2bf79796d8c44b1321a69a7236b85c33ef7caJakob Stoklund Olesen const MachineFunction *MF; 689f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const TargetInstrInfo *TII; 699f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 705f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen const InstrItineraryData *ItinData; 719f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const MachineRegisterInfo *MRI; 729f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const MachineLoopInfo *Loops; 739f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 749f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesenpublic: 759f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen class Ensemble; 769f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen class Trace; 779f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen static char ID; 789f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen MachineTraceMetrics(); 799f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void getAnalysisUsage(AnalysisUsage&) const; 809f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen bool runOnMachineFunction(MachineFunction&); 819f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void releaseMemory(); 82ef6c76c984f821ea866902a7f9e695b16e971468Jakob Stoklund Olesen void verifyAnalysis() const; 839f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 849f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen friend class Ensemble; 859f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen friend class Trace; 869f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 879f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Per-basic block information that doesn't depend on the trace through the 889f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// block. 899f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen struct FixedBlockInfo { 909f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// The number of non-trivial instructions in the block. 919f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Doesn't count PHI and COPY instructions that are likely to be removed. 929f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen unsigned InstrCount; 939f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 949f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// True when the block contains calls. 959f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen bool HasCalls; 969f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 979f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {} 989f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 999f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Returns true when resource information for this block has been computed. 1009f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen bool hasResources() const { return InstrCount != ~0u; } 1019f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1029f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Invalidate resource information. 1039f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void invalidate() { InstrCount = ~0u; } 1049f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen }; 1059f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1069f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Get the fixed resource information about MBB. Compute it on demand. 1079f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const FixedBlockInfo *getResources(const MachineBasicBlock*); 1089f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 109c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// A virtual register or regunit required by a basic block or its trace 110c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// successors. 111c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen struct LiveInReg { 112c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// The virtual register required, or a register unit. 113c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen unsigned Reg; 114c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen 115c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// For virtual registers: Minimum height of the defining instruction. 116c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// For regunits: Height of the highest user in the trace. 117c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen unsigned Height; 118c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen 119c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen LiveInReg(unsigned Reg, unsigned Height = 0) : Reg(Reg), Height(Height) {} 120c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen }; 121c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen 1229f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Per-basic block information that relates to a specific trace through the 1239f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// block. Convergent traces means that only one of these is required per 1249f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// block in a trace ensemble. 1259f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen struct TraceBlockInfo { 1269f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Trace predecessor, or NULL for the first block in the trace. 12708f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen /// Valid when hasValidDepth(). 1289f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const MachineBasicBlock *Pred; 1299f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1309f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Trace successor, or NULL for the last block in the trace. 13108f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen /// Valid when hasValidHeight(). 1329f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const MachineBasicBlock *Succ; 1339f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1340271a5fa29f73150fad891ca4c43a0a89a64b3bfJakob Stoklund Olesen /// The block number of the head of the trace. (When hasValidDepth()). 1350271a5fa29f73150fad891ca4c43a0a89a64b3bfJakob Stoklund Olesen unsigned Head; 1360271a5fa29f73150fad891ca4c43a0a89a64b3bfJakob Stoklund Olesen 1370271a5fa29f73150fad891ca4c43a0a89a64b3bfJakob Stoklund Olesen /// The block number of the tail of the trace. (When hasValidHeight()). 1380271a5fa29f73150fad891ca4c43a0a89a64b3bfJakob Stoklund Olesen unsigned Tail; 1390271a5fa29f73150fad891ca4c43a0a89a64b3bfJakob Stoklund Olesen 1409f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Accumulated number of instructions in the trace above this block. 1419f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Does not include instructions in this block. 1429f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen unsigned InstrDepth; 1439f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1449f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Accumulated number of instructions in the trace below this block. 1459f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Includes instructions in this block. 1469f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen unsigned InstrHeight; 1479f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1485f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen TraceBlockInfo() : 1495f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen Pred(0), Succ(0), 1505f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen InstrDepth(~0u), InstrHeight(~0u), 1515f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen HasValidInstrDepths(false), HasValidInstrHeights(false) {} 1529f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1539f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Returns true if the depth resources have been computed from the trace 1549f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// above this block. 1559f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen bool hasValidDepth() const { return InstrDepth != ~0u; } 1569f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1579f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Returns true if the height resources have been computed from the trace 1589f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// below this block. 1599f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen bool hasValidHeight() const { return InstrHeight != ~0u; } 1609f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1619f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Invalidate depth resources when some block above this one has changed. 1625f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; } 1639f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 1649f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Invalidate height resources when a block below this one has changed. 1655f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; } 1665f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen 1675f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen // Data-dependency-related information. Per-instruction depth and height 1685f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen // are computed from data dependencies in the current trace, using 1695f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen // itinerary data. 1705f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen 1715f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen /// Instruction depths have been computed. This implies hasValidDepth(). 1725f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen bool HasValidInstrDepths; 1735f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen 1745f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen /// Instruction heights have been computed. This implies hasValidHeight(). 1755f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen bool HasValidInstrHeights; 17608f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen 17779a20ce6f0d6c1041a5031aca41b50a1e58b1d4bJakob Stoklund Olesen /// Critical path length. This is the number of cycles in the longest data 17879a20ce6f0d6c1041a5031aca41b50a1e58b1d4bJakob Stoklund Olesen /// dependency chain through the trace. This is only valid when both 17979a20ce6f0d6c1041a5031aca41b50a1e58b1d4bJakob Stoklund Olesen /// HasValidInstrDepths and HasValidInstrHeights are set. 18079a20ce6f0d6c1041a5031aca41b50a1e58b1d4bJakob Stoklund Olesen unsigned CriticalPath; 18179a20ce6f0d6c1041a5031aca41b50a1e58b1d4bJakob Stoklund Olesen 182c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// Live-in registers. These registers are defined above the current block 183c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// and used by this block or a block below it. 184c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// This does not include PHI uses in the current block, but it does 185c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen /// include PHI uses in deeper blocks. 186c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen SmallVector<LiveInReg, 4> LiveIns; 187c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen 18808f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen void print(raw_ostream&) const; 1899f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen }; 1909f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 19184ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// InstrCycles represents the cycle height and depth of an instruction in a 19284ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// trace. 19384ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen struct InstrCycles { 19484ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// Earliest issue cycle as determined by data dependencies and instruction 19584ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// latencies from the beginning of the trace. Data dependencies from 19684ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// before the trace are not included. 19784ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen unsigned Depth; 19884ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen 19984ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// Minimum number of cycles from this instruction is issued to the of the 20084ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// trace, as determined by data dependencies and instruction latencies. 20184ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen unsigned Height; 20284ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen }; 20384ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen 2049f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// A trace represents a plausible sequence of executed basic blocks that 2059f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// passes through the current basic block one. The Trace class serves as a 2069f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// handle to internal cached data structures. 2079f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen class Trace { 2089f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen Ensemble &TE; 2099f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen TraceBlockInfo &TBI; 2109f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 21184ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; } 21284ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen 2139f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen public: 2149f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {} 2159f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void print(raw_ostream&) const; 2169f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2179f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Compute the total number of instructions in the trace. 2189f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen unsigned getInstrCount() const { 2199f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen return TBI.InstrDepth + TBI.InstrHeight; 2209f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen } 2219f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2227a8f311ece7108e44ded601237091c23ef7782ebJakob Stoklund Olesen /// Return the resource depth of the top/bottom of the trace center block. 22384ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// This is the number of cycles required to execute all instructions from 22484ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// the trace head to the trace center block. The resource depth only 22584ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// considers execution resources, it ignores data dependencies. 22684ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// When Bottom is set, instructions in the trace center block are included. 22784ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen unsigned getResourceDepth(bool Bottom) const; 22884ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen 2295413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// Return the resource length of the trace. This is the number of cycles 2305413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// required to execute the instructions in the trace if they were all 2315413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// independent, exposing the maximum instruction-level parallelism. 2325413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// 2335413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// Any blocks in Extrablocks are included as if they were part of the 2345413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// trace. 2355413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen unsigned getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks = 2365413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen ArrayRef<const MachineBasicBlock*>()) const; 2375413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen 23884ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// Return the length of the (data dependency) critical path through the 23984ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// trace. 24084ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen unsigned getCriticalPath() const { return TBI.CriticalPath; } 24184ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen 24284ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// Return the depth and height of MI. The depth is only valid for 24384ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// instructions in or above the trace center block. The height is only 24484ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// valid for instructions in or below the trace center block. 24584ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen InstrCycles getInstrCycles(const MachineInstr *MI) const { 24684ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen return TE.Cycles.lookup(MI); 24784ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen } 2485f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen 24984ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// Return the slack of MI. This is the number of cycles MI can be delayed 25084ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// before the critical path becomes longer. 25184ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen /// MI must be an instruction in the trace center block. 25284ef6ba44394f983d985b02e328cbb2dd779e4b0Jakob Stoklund Olesen unsigned getInstrSlack(const MachineInstr *MI) const; 2535413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen 2545413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// Return the Depth of a PHI instruction in a trace center block successor. 2555413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen /// The PHI does not have to be part of the trace. 2565413b68b1f59041a821287790dbc1ee2e272cf4eJakob Stoklund Olesen unsigned getPHIDepth(const MachineInstr *PHI) const; 2575f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen }; 2585f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen 2599f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// A trace ensemble is a collection of traces selected using the same 2609f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// strategy, for example 'minimum resource height'. There is one trace for 2619f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// every block in the function. 2629f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen class Ensemble { 2639f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen SmallVector<TraceBlockInfo, 4> BlockInfo; 2645f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen DenseMap<const MachineInstr*, InstrCycles> Cycles; 2659f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen friend class Trace; 2669f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2679f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void computeTrace(const MachineBasicBlock*); 2689f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void computeDepthResources(const MachineBasicBlock*); 2699f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void computeHeightResources(const MachineBasicBlock*); 27079a20ce6f0d6c1041a5031aca41b50a1e58b1d4bJakob Stoklund Olesen unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&); 2715f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen void computeInstrDepths(const MachineBasicBlock*); 2725f8e8bd656bb174b3e22c0e56ce3d1eb958ac2e2Jakob Stoklund Olesen void computeInstrHeights(const MachineBasicBlock*); 273c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen void addLiveIns(const MachineInstr *DefMI, 274c7f44b8b8fca87cdd28ffe420c3b87141d88c099Jakob Stoklund Olesen ArrayRef<const MachineBasicBlock*> Trace); 2759f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2769f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen protected: 27764e2973bf78970aedecbb5fda44e19f93f56dd9bJakob Stoklund Olesen MachineTraceMetrics &MTM; 2789f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0; 2799f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0; 2809f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen explicit Ensemble(MachineTraceMetrics*); 281a1b2bf79796d8c44b1321a69a7236b85c33ef7caJakob Stoklund Olesen const MachineLoop *getLoopFor(const MachineBasicBlock*) const; 2829f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const; 2839f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const; 2849f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2859f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen public: 2869f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen virtual ~Ensemble(); 28708f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen virtual const char *getName() const =0; 28808f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen void print(raw_ostream&) const; 2899f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void invalidate(const MachineBasicBlock *MBB); 290a1b2bf79796d8c44b1321a69a7236b85c33ef7caJakob Stoklund Olesen void verify() const; 2919f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2929f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Get the trace that passes through MBB. 2939f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// The trace is computed on demand. 2949f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen Trace getTrace(const MachineBasicBlock *MBB); 2959f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen }; 2969f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 2979f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Strategies for selecting traces. 2989f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen enum Strategy { 2999f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Select the trace through a block that has the fewest instructions. 3009f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen TS_MinInstrCount, 3019f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3029f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen TS_NumStrategies 3039f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen }; 3049f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3059f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Get the trace ensemble representing the given trace selection strategy. 3069f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// The returned Ensemble object is owned by the MachineTraceMetrics analysis, 3079f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// and valid for the lifetime of the analysis pass. 3089f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen Ensemble *getEnsemble(Strategy); 3099f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3109f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// Invalidate cached information about MBB. This must be called *before* MBB 3119f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen /// is erased, or the CFG is otherwise changed. 31220f13c50d88560d75129f4a691fe6b477d04dc70Jakob Stoklund Olesen /// 31320f13c50d88560d75129f4a691fe6b477d04dc70Jakob Stoklund Olesen /// This invalidates per-block information about resource usage for MBB only, 31420f13c50d88560d75129f4a691fe6b477d04dc70Jakob Stoklund Olesen /// and it invalidates per-trace information for any trace that passes 31520f13c50d88560d75129f4a691fe6b477d04dc70Jakob Stoklund Olesen /// through MBB. 31620f13c50d88560d75129f4a691fe6b477d04dc70Jakob Stoklund Olesen /// 31720f13c50d88560d75129f4a691fe6b477d04dc70Jakob Stoklund Olesen /// Call Ensemble::getTrace() again to update any trace handles. 3189f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen void invalidate(const MachineBasicBlock *MBB); 3199f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3209f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesenprivate: 3219f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen // One entry per basic block, indexed by block number. 3229f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen SmallVector<FixedBlockInfo, 4> BlockInfo; 3239f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3249f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen // One ensemble per strategy. 3259f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen Ensemble* Ensembles[TS_NumStrategies]; 3269f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen}; 3279f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3289f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Oleseninline raw_ostream &operator<<(raw_ostream &OS, 3299f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen const MachineTraceMetrics::Trace &Tr) { 3309f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen Tr.print(OS); 3319f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen return OS; 3329f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen} 3339f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 33408f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Oleseninline raw_ostream &operator<<(raw_ostream &OS, 33508f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen const MachineTraceMetrics::Ensemble &En) { 33608f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen En.print(OS); 33708f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen return OS; 33808f6ef6a7807250d84446661b7a6ec4afa762099Jakob Stoklund Olesen} 3399f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen} // end namespace llvm 3409f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen 3419f63e104271eb91e545fa8cdb16fb9e10a8a9578Jakob Stoklund Olesen#endif 342