MachineTraceMetrics.cpp | Explore in Territory

//===- lib/CodeGen/MachineTraceMetrics.cpp --------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/MachineTraceMetrics.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <tuple>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

char MachineTraceMetrics::ID = …;

char &llvm::MachineTraceMetricsID = …;

INITIALIZE_PASS_BEGIN(MachineTraceMetrics, DEBUG_TYPE,
                      "Machine Trace Metrics", false, true)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_END(MachineTraceMetrics, DEBUG_TYPE,
                    "Machine Trace Metrics", false, true)

MachineTraceMetrics::MachineTraceMetrics() : … { … }

void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { … }

void MachineTraceMetrics::releaseMemory() { … }

//===----------------------------------------------------------------------===//
//                          Fixed block information
//===----------------------------------------------------------------------===//
//
// The number of instructions in a basic block and the CPU resources used by
// those instructions don't depend on any given trace strategy.

/// Compute the resource usage in basic block MBB.
const MachineTraceMetrics::FixedBlockInfo*
MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { … }

ArrayRef<unsigned>
MachineTraceMetrics::getProcReleaseAtCycles(unsigned MBBNum) const { … }

//===----------------------------------------------------------------------===//
//                         Ensemble utility functions
//===----------------------------------------------------------------------===//

MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct)
  : … { … }

// Virtual destructor serves as an anchor.
MachineTraceMetrics::Ensemble::~Ensemble() = default;

const MachineLoop*
MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { … }

// Update resource-related information in the TraceBlockInfo for MBB.
// Only update resources related to the trace above MBB.
void MachineTraceMetrics::Ensemble::
computeDepthResources(const MachineBasicBlock *MBB) { … }

// Update resource-related information in the TraceBlockInfo for MBB.
// Only update resources related to the trace below MBB.
void MachineTraceMetrics::Ensemble::
computeHeightResources(const MachineBasicBlock *MBB) { … }

// Check if depth resources for MBB are valid and return the TBI.
// Return NULL if the resources have been invalidated.
const MachineTraceMetrics::TraceBlockInfo*
MachineTraceMetrics::Ensemble::
getDepthResources(const MachineBasicBlock *MBB) const { … }

// Check if height resources for MBB are valid and return the TBI.
// Return NULL if the resources have been invalidated.
const MachineTraceMetrics::TraceBlockInfo*
MachineTraceMetrics::Ensemble::
getHeightResources(const MachineBasicBlock *MBB) const { … }

/// Get an array of processor resource depths for MBB. Indexed by processor
/// resource kind, this array contains the scaled processor resources consumed
/// by all blocks preceding MBB in its trace. It does not include instructions
/// in MBB.
///
/// Compare TraceBlockInfo::InstrDepth.
ArrayRef<unsigned>
MachineTraceMetrics::Ensemble::
getProcResourceDepths(unsigned MBBNum) const { … }

/// Get an array of processor resource heights for MBB. Indexed by processor
/// resource kind, this array contains the scaled processor resources consumed
/// by this block and all blocks following it in its trace.
///
/// Compare TraceBlockInfo::InstrHeight.
ArrayRef<unsigned>
MachineTraceMetrics::Ensemble::
getProcResourceHeights(unsigned MBBNum) const { … }

//===----------------------------------------------------------------------===//
//                         Trace Selection Strategies
//===----------------------------------------------------------------------===//
//
// A trace selection strategy is implemented as a sub-class of Ensemble. The
// trace through a block B is computed by two DFS traversals of the CFG
// starting from B. One upwards, and one downwards. During the upwards DFS,
// pickTracePred() is called on the post-ordered blocks. During the downwards
// DFS, pickTraceSucc() is called in a post-order.
//

// We never allow traces that leave loops, but we do allow traces to enter
// nested loops. We also never allow traces to contain back-edges.
//
// This means that a loop header can never appear above the center block of a
// trace, except as the trace head. Below the center block, loop exiting edges
// are banned.
//
// Return true if an edge from the From loop to the To loop is leaving a loop.
// Either of To and From can be null.
static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) { … }

// MinInstrCountEnsemble - Pick the trace that executes the least number of
// instructions.
namespace {

class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { … };

/// Pick only the current basic block for the trace and do not choose any
/// predecessors/successors.
class LocalEnsemble : public MachineTraceMetrics::Ensemble { … };
} // end anonymous namespace

// Select the preferred predecessor for MBB.
const MachineBasicBlock*
MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { … }

// Select the preferred successor for MBB.
const MachineBasicBlock*
MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { … }

// Get an Ensemble sub-class for the requested trace strategy.
MachineTraceMetrics::Ensemble *
MachineTraceMetrics::getEnsemble(MachineTraceStrategy strategy) { … }

void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { … }

void MachineTraceMetrics::verifyAnalysis() const { … }

//===----------------------------------------------------------------------===//
//                               Trace building
//===----------------------------------------------------------------------===//
//
// Traces are built by two CFG traversals. To avoid recomputing too much, use a
// set abstraction that confines the search to the current loop, and doesn't
// revisit blocks.

namespace {

struct LoopBounds { … };

} // end anonymous namespace

// Specialize po_iterator_storage in order to prune the post-order traversal so
// it is limited to the current loop and doesn't traverse the loop back edges.
namespace llvm {

template<>
class po_iterator_storage<LoopBounds, true> { … };

} // end namespace llvm

/// Compute the trace through MBB.
void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { … }

/// Invalidate traces through BadMBB.
void
MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { … }

void MachineTraceMetrics::Ensemble::verify() const { … }

//===----------------------------------------------------------------------===//
//                             Data Dependencies
//===----------------------------------------------------------------------===//
//
// Compute the depth and height of each instruction based on data dependencies
// and instruction latencies. These cycle numbers assume that the CPU can issue
// an infinite number of instructions per cycle as long as their dependencies
// are ready.

// A data dependency is represented as a defining MI and operand numbers on the
// defining and using MI.
namespace {

struct DataDep { … };

} // end anonymous namespace

// Get the input data dependencies that must be ready before UseMI can issue.
// Return true if UseMI has any physreg operands.
static bool getDataDeps(const MachineInstr &UseMI,
                        SmallVectorImpl<DataDep> &Deps,
                        const MachineRegisterInfo *MRI) { … }

// Get the input data dependencies of a PHI instruction, using Pred as the
// preferred predecessor.
// This will add at most one dependency to Deps.
static void getPHIDeps(const MachineInstr &UseMI,
                       SmallVectorImpl<DataDep> &Deps,
                       const MachineBasicBlock *Pred,
                       const MachineRegisterInfo *MRI) { … }

// Identify physreg dependencies for UseMI, and update the live regunit
// tracking set when scanning instructions downwards.
static void updatePhysDepsDownwards(const MachineInstr *UseMI,
                                    SmallVectorImpl<DataDep> &Deps,
                                    SparseSet<LiveRegUnit> &RegUnits,
                                    const TargetRegisterInfo *TRI) { … }

/// The length of the critical path through a trace is the maximum of two path
/// lengths:
///
/// 1. The maximum height+depth over all instructions in the trace center block.
///
/// 2. The longest cross-block dependency chain. For small blocks, it is
///    possible that the critical path through the trace doesn't include any
///    instructions in the block.
///
/// This function computes the second number from the live-in list of the
/// center block.
unsigned MachineTraceMetrics::Ensemble::
computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) { … }

void MachineTraceMetrics::Ensemble::
updateDepth(MachineTraceMetrics::TraceBlockInfo &TBI, const MachineInstr &UseMI,
            SparseSet<LiveRegUnit> &RegUnits) { … }

void MachineTraceMetrics::Ensemble::
updateDepth(const MachineBasicBlock *MBB, const MachineInstr &UseMI,
            SparseSet<LiveRegUnit> &RegUnits) { … }

void MachineTraceMetrics::Ensemble::
updateDepths(MachineBasicBlock::iterator Start,
             MachineBasicBlock::iterator End,
             SparseSet<LiveRegUnit> &RegUnits) { … }

/// Compute instruction depths for all instructions above or in MBB in its
/// trace. This assumes that the trace through MBB has already been computed.
void MachineTraceMetrics::Ensemble::
computeInstrDepths(const MachineBasicBlock *MBB) { … }

// Identify physreg dependencies for MI when scanning instructions upwards.
// Return the issue height of MI after considering any live regunits.
// Height is the issue height computed from virtual register dependencies alone.
static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height,
                                      SparseSet<LiveRegUnit> &RegUnits,
                                      const TargetSchedModel &SchedModel,
                                      const TargetInstrInfo *TII,
                                      const TargetRegisterInfo *TRI) { … }

MIHeightMap;

// Push the height of DefMI upwards if required to match UseMI.
// Return true if this is the first time DefMI was seen.
static bool pushDepHeight(const DataDep &Dep, const MachineInstr &UseMI,
                          unsigned UseHeight, MIHeightMap &Heights,
                          const TargetSchedModel &SchedModel,
                          const TargetInstrInfo *TII) { … }

/// Assuming that the virtual register defined by DefMI:DefOp was used by
/// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop
/// when reaching the block that contains DefMI.
void MachineTraceMetrics::Ensemble::
addLiveIns(const MachineInstr *DefMI, unsigned DefOp,
           ArrayRef<const MachineBasicBlock*> Trace) { … }

/// Compute instruction heights in the trace through MBB. This updates MBB and
/// the blocks below it in the trace. It is assumed that the trace has already
/// been computed.
void MachineTraceMetrics::Ensemble::
computeInstrHeights(const MachineBasicBlock *MBB) { … }

MachineTraceMetrics::Trace
MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { … }

unsigned
MachineTraceMetrics::Trace::getInstrSlack(const MachineInstr &MI) const { … }

unsigned
MachineTraceMetrics::Trace::getPHIDepth(const MachineInstr &PHI) const { … }

/// When bottom is set include instructions in current block in estimate.
unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { … }

unsigned MachineTraceMetrics::Trace::getResourceLength(
    ArrayRef<const MachineBasicBlock *> Extrablocks,
    ArrayRef<const MCSchedClassDesc *> ExtraInstrs,
    ArrayRef<const MCSchedClassDesc *> RemoveInstrs) const { … }

bool MachineTraceMetrics::Trace::isDepInTrace(const MachineInstr &DefMI,
                                              const MachineInstr &UseMI) const { … }

void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { … }

void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { … }

void MachineTraceMetrics::Trace::print(raw_ostream &OS) const { … }
llvm/llvm/lib/CodeGen/MachineTraceMetrics.cpp
