MachineCombiner.cpp | Explore in Territory

//===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// The machine combiner pass uses machine trace metrics to ensure the combined
// instructions do not lengthen the critical path or the resource depth.
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineCombinerPattern.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineSizeOpts.h"
#include "llvm/CodeGen/MachineTraceMetrics.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumInstCombined, "Number of machineinst combined");

static cl::opt<unsigned>
inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
              cl::desc("Incremental depth computation will be used for basic "
                       "blocks with more instructions."), cl::init(500));

static cl::opt<bool> dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden,
                                cl::desc("Dump all substituted intrs"),
                                cl::init(false));

#ifdef EXPENSIVE_CHECKS
static cl::opt<bool> VerifyPatternOrder(
    "machine-combiner-verify-pattern-order", cl::Hidden,
    cl::desc(
        "Verify that the generated patterns are ordered by increasing latency"),
    cl::init(true));
#else
static cl::opt<bool> VerifyPatternOrder(
    "machine-combiner-verify-pattern-order", cl::Hidden,
    cl::desc(
        "Verify that the generated patterns are ordered by increasing latency"),
    cl::init(false));
#endif

namespace {
class MachineCombiner : public MachineFunctionPass { … };
}

char MachineCombiner::ID = …;
char &llvm::MachineCombinerID = …;

INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
                      "Machine InstCombiner", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
                    false, false)

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

MachineInstr *
MachineCombiner::getOperandDef(const MachineOperand &MO) { … }

/// Return true if MI is unlikely to generate an actual target instruction.
bool MachineCombiner::isTransientMI(const MachineInstr *MI) { … }

/// Computes depth of instructions in vector \InsInstr.
///
/// \param InsInstrs is a vector of machine instructions
/// \param InstrIdxForVirtReg is a dense map of virtual register to index
/// of defining machine instruction in \p InsInstrs
/// \param BlockTrace is a trace of machine instructions
///
/// \returns Depth of last instruction in \InsInstrs ("NewRoot")
unsigned
MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
                          DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
                          MachineTraceMetrics::Trace BlockTrace,
                          const MachineBasicBlock &MBB) { … }

/// Computes instruction latency as max of latency of defined operands.
///
/// \param Root is a machine instruction that could be replaced by NewRoot.
/// It is used to compute a more accurate latency information for NewRoot in
/// case there is a dependent instruction in the same trace (\p BlockTrace)
/// \param NewRoot is the instruction for which the latency is computed
/// \param BlockTrace is a trace of machine instructions
///
/// \returns Latency of \p NewRoot
unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
                                     MachineTraceMetrics::Trace BlockTrace) { … }

CombinerObjective MachineCombiner::getCombinerObjective(unsigned Pattern) { … }

/// Estimate the latency of the new and original instruction sequence by summing
/// up the latencies of the inserted and deleted instructions. This assumes
/// that the inserted and deleted instructions are dependent instruction chains,
/// which might not hold in all cases.
std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
    MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
    SmallVectorImpl<MachineInstr *> &DelInstrs,
    MachineTraceMetrics::Trace BlockTrace) { … }

bool MachineCombiner::reduceRegisterPressure(
    MachineInstr &Root, MachineBasicBlock *MBB,
    SmallVectorImpl<MachineInstr *> &InsInstrs,
    SmallVectorImpl<MachineInstr *> &DelInstrs, unsigned Pattern) { … }

/// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
/// The new code sequence ends in MI NewRoot. A necessary condition for the new
/// sequence to replace the old sequence is that it cannot lengthen the critical
/// path. The definition of "improve" may be restricted by specifying that the
/// new path improves the data dependency chain (MustReduceDepth).
bool MachineCombiner::improvesCriticalPathLen(
    MachineBasicBlock *MBB, MachineInstr *Root,
    MachineTraceMetrics::Trace BlockTrace,
    SmallVectorImpl<MachineInstr *> &InsInstrs,
    SmallVectorImpl<MachineInstr *> &DelInstrs,
    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg, unsigned Pattern,
    bool SlackIsAccurate) { … }

/// helper routine to convert instructions into SC
void MachineCombiner::instr2instrSC(
    SmallVectorImpl<MachineInstr *> &Instrs,
    SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) { … }

/// True when the new instructions do not increase resource length
bool MachineCombiner::preservesResourceLen(
    MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
    SmallVectorImpl<MachineInstr *> &InsInstrs,
    SmallVectorImpl<MachineInstr *> &DelInstrs) { … }

/// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
/// depths if requested.
///
/// \param MBB basic block to insert instructions in
/// \param MI current machine instruction
/// \param InsInstrs new instructions to insert in \p MBB
/// \param DelInstrs instruction to delete from \p MBB
/// \param TraceEnsemble is a pointer to the machine trace information
/// \param RegUnits set of live registers, needed to compute instruction depths
/// \param TII is target instruction info, used to call target hook
/// \param Pattern is used to call target hook finalizeInsInstrs
/// \param IncrementalUpdate if true, compute instruction depths incrementally,
///                          otherwise invalidate the trace
static void
insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
                         SmallVectorImpl<MachineInstr *> &InsInstrs,
                         SmallVectorImpl<MachineInstr *> &DelInstrs,
                         MachineTraceMetrics::Ensemble *TraceEnsemble,
                         SparseSet<LiveRegUnit> &RegUnits,
                         const TargetInstrInfo *TII, unsigned Pattern,
                         bool IncrementalUpdate) { … }

// Check that the difference between original and new latency is decreasing for
// later patterns. This helps to discover sub-optimal pattern orderings.
void MachineCombiner::verifyPatternOrder(MachineBasicBlock *MBB,
                                         MachineInstr &Root,
                                         SmallVector<unsigned, 16> &Patterns) { … }

/// Substitute a slow code sequence with a faster one by
/// evaluating instruction combining pattern.
/// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
/// combining based on machine trace metrics. Only combine a sequence of
/// instructions  when this neither lengthens the critical path nor increases
/// resource pressure. When optimizing for codesize always combine when the new
/// sequence is shorter.
bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) { … }

bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) { … }
llvm/llvm/lib/CodeGen/MachineCombiner.cpp
