MachineCopyPropagation.cpp | Explore in Territory

//===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
//
// 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 is an extremely simple MachineInstr-level copy propagation pass.
//
// This pass forwards the source of COPYs to the users of their destinations
// when doing so is legal.  For example:
//
//   %reg1 = COPY %reg0
//   ...
//   ... = OP %reg1
//
// If
//   - %reg0 has not been clobbered by the time of the use of %reg1
//   - the register class constraints are satisfied
//   - the COPY def is the only value that reaches OP
// then this pass replaces the above with:
//
//   %reg1 = COPY %reg0
//   ...
//   ... = OP %reg0
//
// This pass also removes some redundant COPYs.  For example:
//
//    %R1 = COPY %R0
//    ... // No clobber of %R1
//    %R0 = COPY %R1 <<< Removed
//
// or
//
//    %R1 = COPY %R0
//    ... // No clobber of %R0
//    %R1 = COPY %R0 <<< Removed
//
// or
//
//    $R0 = OP ...
//    ... // No read/clobber of $R0 and $R1
//    $R1 = COPY $R0 // $R0 is killed
// Replace $R0 with $R1 and remove the COPY
//    $R1 = OP ...
//    ...
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegister.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <iterator>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumDeletes, "Number of dead copies deleted");
STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
STATISTIC(SpillageChainsLength, "Length of spillage chains");
STATISTIC(NumSpillageChains, "Number of spillage chains");
DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
              "Controls which register COPYs are forwarded");

static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false),
                                     cl::Hidden);
static cl::opt<cl::boolOrDefault>
    EnableSpillageCopyElimination("enable-spill-copy-elim", cl::Hidden);

namespace {

static std::optional<DestSourcePair> isCopyInstr(const MachineInstr &MI,
                                                 const TargetInstrInfo &TII,
                                                 bool UseCopyInstr) { … }

class CopyTracker { … };

class MachineCopyPropagation : public MachineFunctionPass { … };

} // end anonymous namespace

char MachineCopyPropagation::ID = …;

char &llvm::MachineCopyPropagationID = …;

INITIALIZE_PASS(…)

void MachineCopyPropagation::ReadRegister(MCRegister Reg, MachineInstr &Reader,
                                          DebugType DT) { … }

void MachineCopyPropagation::readSuccessorLiveIns(
    const MachineBasicBlock &MBB) { … }

/// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
/// This fact may have been obscured by sub register usage or may not be true at
/// all even though Src and Def are subregisters of the registers used in
/// PreviousCopy. e.g.
/// isNopCopy("ecx = COPY eax", AX, CX) == true
/// isNopCopy("ecx = COPY eax", AH, CL) == false
static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src,
                      MCRegister Def, const TargetRegisterInfo *TRI,
                      const TargetInstrInfo *TII, bool UseCopyInstr) { … }

/// Remove instruction \p Copy if there exists a previous copy that copies the
/// register \p Src to the register \p Def; This may happen indirectly by
/// copying the super registers.
bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy,
                                              MCRegister Src, MCRegister Def) { … }

bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
    const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) { … }

/// Decide whether we should forward the source of \param Copy to its use in
/// \param UseI based on the physical register class constraints of the opcode
/// and avoiding introducing more cross-class COPYs.
bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
                                                       const MachineInstr &UseI,
                                                       unsigned UseIdx) { … }

/// Check that \p MI does not have implicit uses that overlap with it's \p Use
/// operand (the register being replaced), since these can sometimes be
/// implicitly tied to other operands.  For example, on AMDGPU:
///
/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
///
/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
/// way of knowing we need to update the latter when updating the former.
bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
                                                const MachineOperand &Use) { … }

/// For an MI that has multiple definitions, check whether \p MI has
/// a definition that overlaps with another of its definitions.
/// For example, on ARM: umull   r9, r9, lr, r0
/// The umull instruction is unpredictable unless RdHi and RdLo are different.
bool MachineCopyPropagation::hasOverlappingMultipleDef(
    const MachineInstr &MI, const MachineOperand &MODef, Register Def) { … }

/// Look for available copies whose destination register is used by \p MI and
/// replace the use in \p MI with the copy's source register.
void MachineCopyPropagation::forwardUses(MachineInstr &MI) { … }

void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) { … }

static bool isBackwardPropagatableCopy(const DestSourcePair &CopyOperands,
                                       const MachineRegisterInfo &MRI) { … }

void MachineCopyPropagation::propagateDefs(MachineInstr &MI) { … }

void MachineCopyPropagation::BackwardCopyPropagateBlock(
    MachineBasicBlock &MBB) { … }

static void LLVM_ATTRIBUTE_UNUSED printSpillReloadChain(
    DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &SpillChain,
    DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &ReloadChain,
    MachineInstr *Leader) { … }

// Remove spill-reload like copy chains. For example
// r0 = COPY r1
// r1 = COPY r2
// r2 = COPY r3
// r3 = COPY r4
// <def-use r4>
// r4 = COPY r3
// r3 = COPY r2
// r2 = COPY r1
// r1 = COPY r0
// will be folded into
// r0 = COPY r1
// r1 = COPY r4
// <def-use r4>
// r4 = COPY r1
// r1 = COPY r0
// TODO: Currently we don't track usage of r0 outside the chain, so we
// conservatively keep its value as it was before the rewrite.
//
// The algorithm is trying to keep
// property#1: No Def of spill COPY in the chain is used or defined until the
// paired reload COPY in the chain uses the Def.
//
// property#2: NO Source of COPY in the chain is used or defined until the next
// COPY in the chain defines the Source, except the innermost spill-reload
// pair.
//
// The algorithm is conducted by checking every COPY inside the MBB, assuming
// the COPY is a reload COPY, then try to find paired spill COPY by searching
// the COPY defines the Src of the reload COPY backward. If such pair is found,
// it either belongs to an existing chain or a new chain depends on
// last available COPY uses the Def of the reload COPY.
// Implementation notes, we use CopyTracker::findLastDefCopy(Reg, ...) to find
// out last COPY that defines Reg; we use CopyTracker::findLastUseCopy(Reg, ...)
// to find out last COPY that uses Reg. When we are encountered with a Non-COPY
// instruction, we check registers in the operands of this instruction. If this
// Reg is defined by a COPY, we untrack this Reg via
// CopyTracker::clobberRegister(Reg, ...).
void MachineCopyPropagation::EliminateSpillageCopies(MachineBasicBlock &MBB) { … }

bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { … }

MachineFunctionPass *
llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) { … }
llvm/llvm/lib/CodeGen/MachineCopyPropagation.cpp
