llvm/lib/Target/AMDGPU/GCNVOPDUtils.cpp

//===- GCNVOPDUtils.cpp - GCN VOPD Utils  ------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
/// \file This file contains the AMDGPU DAG scheduling
/// mutation to pair VOPD instructions back to back. It also contains
//  subroutines useful in the creation of VOPD instructions
//
//===----------------------------------------------------------------------===//

#include "GCNVOPDUtils.h"
#include "AMDGPUSubtarget.h"
#include "GCNSubtarget.h"
#include "SIInstrInfo.h"
#include "Utils/AMDGPUBaseInfo.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MacroFusion.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/MC/MCInst.h"
#include "llvm/TargetParser/AMDGPUTargetParser.h"

using namespace llvm;

#define DEBUG_TYPE "gcn-vopd-utils"

// Return the register class of the VOPDOpc operand named
// src/vsrc<SrcIdx><CompIdx>, which is the slot src<SrcIdx> of MI<CompIdx> maps
// to.
static const TargetRegisterClass *getVOPDSrcRegClass(const SIInstrInfo &TII,
                                                     int VOPDOpc,
                                                     unsigned CompIdx,
                                                     unsigned SrcIdx) {
  using namespace AMDGPU;
  int OpIdx = -1;
  const bool IsX = CompIdx == VOPD::X;
  switch (SrcIdx) {
  case 0:
    OpIdx = getNamedOperandIdx(VOPDOpc, IsX ? OpName::src0X : OpName::src0Y);
    break;
  case 1:
    OpIdx = getNamedOperandIdx(VOPDOpc, IsX ? OpName::vsrc1X : OpName::vsrc1Y);
    break;
  case 2:
    OpIdx = getNamedOperandIdx(VOPDOpc, IsX ? OpName::vsrc2X : OpName::vsrc2Y);
    if (OpIdx == -1)
      OpIdx = getNamedOperandIdx(VOPDOpc, IsX ? OpName::src2X : OpName::src2Y);
    break;
  default:
    llvm_unreachable("unexpected VOPD source index");
  }

  assert(OpIdx != -1);
  return TII.getRegClass(TII.get(VOPDOpc), OpIdx);
}

// Check if physical register from src<SrcIdx> operand of MI<CompIdx> matches
// register class constraints in corresponding VOPDOpc operand with name
// src/vsrc<SrcIdx><CompIdx>.
static bool isValidVOPDSrc(const SIInstrInfo &TII, int VOPDOpc,
                           unsigned CompIdx, unsigned SrcIdx,
                           Register PhysSrcReg) {
  return getVOPDSrcRegClass(TII, VOPDOpc, CompIdx, SrcIdx)
      ->contains(PhysSrcReg);
}

static const MachineOperand &getNamedOp(const MachineInstr &MI,
                                        AMDGPU::OpName Name) {
  return MI.getOperand(getNamedOperandIdx(MI.getOpcode(), Name));
}

// Check if MI is a VOP3P instruction with operands that satisfy the constraints
// for mapping it to a VOP2/VOPD opcode: no modifiers, no clamp, src1 and src2
// are registers (src0 can be register or literal), and src2 is same as dst.
// An immediate in src1 is accepted if src0 is a register and the operands can
// be commuted. \p Commute is set if that is needed.
static bool canMapVOP3PToVOPD(const SIInstrInfo &TII, const MachineInstr &MI,
                              bool &Commute) {
  Commute = false;
  unsigned Opc = MI.getOpcode();
  if (Opc != AMDGPU::V_DOT2_F32_F16 && Opc != AMDGPU::V_DOT2_F32_BF16)
    return false;
  // src0 can be register or literal
  if (getNamedOp(MI, AMDGPU::OpName::src0_modifiers).getImm() !=
      SISrcMods::OP_SEL_1)
    return false;
  if (getNamedOp(MI, AMDGPU::OpName::src1_modifiers).getImm() !=
      SISrcMods::OP_SEL_1)
    return false;
  int Src0Idx = getNamedOperandIdx(Opc, AMDGPU::OpName::src0);
  int Src1Idx = getNamedOperandIdx(Opc, AMDGPU::OpName::src1);
  const MachineOperand &Src0 = MI.getOperand(Src0Idx);
  const MachineOperand &Src1 = MI.getOperand(Src1Idx);
  // VOPD needs a register in src1. If src1 is an immediate, the dot2 can still
  // be used once src0 and src1 are swapped.
  if (!Src1.isReg()) {
    if (!Src0.isReg() || !Src1.isImm() ||
        !TII.isLegalToSwap(MI, Src0Idx, Src1Idx))
      return false;
    Commute = true;
  }
  if (getNamedOp(MI, AMDGPU::OpName::src2_modifiers).getImm() !=
      SISrcMods::OP_SEL_1)
    return false;
  if (!getNamedOp(MI, AMDGPU::OpName::src2).isReg())
    return false;
  if (getNamedOp(MI, AMDGPU::OpName::clamp).getImm() != 0)
    return false;
  return getNamedOp(MI, AMDGPU::OpName::vdst).getReg() ==
         getNamedOp(MI, AMDGPU::OpName::src2).getReg();
}

// In a VOPD3 whose OPX is a 64-bit operation, an OPY VGPR source operand reads
// back the wrong value if it is the last VGPR the wave owns.
// A wave always owns a whole number of VGPR allocation granules, so only a
// register just below a granule boundary can be the last one. The wave also
// owns at least as many VGPRs as this function uses, so a source which has a
// register above it in use here cannot be the last one either.
// The number of VGPRs the wave is actually given is not available until the
// assembler has seen the whole module, but that can only come out above this
// function's own usage, so this is conservatively correct.
static bool isVOPD3F64OPYSrcHazard(const SIInstrInfo &TII,
                                   const MachineInstr &MIX,
                                   const MachineInstr &MIY) {
  const MachineFunction &MF = *MIX.getMF();
  const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
  if (!ST.hasVOPD3F64OPYSrcHazard())
    return false;

  // Every 64-bit VOPD3 OPX opcode has a 64-bit vdst, and no 32-bit one has.
  int VDstIdx =
      AMDGPU::getNamedOperandIdx(MIX.getOpcode(), AMDGPU::OpName::vdst);
  assert(VDstIdx != -1 && "VOPD3 OPX component must have a vdst");
  if (TII.getOpSize(MIX, VDstIdx) != 8)
    return false;

  unsigned Granule =
      AMDGPU::getVGPRAllocGranule(ST.getTargetID().getGPUKind(), ST.isWave32());
  const SIRegisterInfo *TRI = ST.getRegisterInfo();
  unsigned NumVGPRs = TRI->getNumUsedPhysRegs(
      MF.getRegInfo(), AMDGPU::VGPR_32RegClass, /*IncludeCalls=*/false);
  for (AMDGPU::OpName Name :
       {AMDGPU::OpName::src0, AMDGPU::OpName::src1, AMDGPU::OpName::src2}) {
    const MachineOperand *Src = TII.getNamedOperand(MIY, Name);
    // Every OPY source which can be a VGPR is 32 bits wide.
    if (!Src || !Src->isReg() ||
        !AMDGPU::VGPR_32RegClass.contains(Src->getReg()))
      continue;
    unsigned Idx = TRI->getHWRegIndex(Src->getReg());
    if ((Idx + 1) % Granule == 0 && Idx + 1 >= NumVGPRs)
      return true;
  }
  return false;
}

static bool canMaterializeVOPDLiterals(const MachineFunction &MF) {
  // A free register cannot be found without liveness. A move also makes the
  // code longer, so a function which asked for small code keeps its literals.
  return MF.getProperties().hasTracksLiveness() &&
         !MF.getFunction().hasOptSize();
}

static bool checkVOPDRegConstraints(
    const SIInstrInfo &TII, const MachineInstr &MIX, const MachineInstr &MIY,
    bool IsVOPD3, bool AllowSameVGPR,
    SmallVectorImpl<VOPDLiteralFixup> &LiteralFixups, bool (&CommuteXY)[2]) {
  namespace VOPD = AMDGPU::VOPD;

  const MachineFunction *MF = MIX.getMF();
  const GCNSubtarget &ST = MF->getSubtarget<GCNSubtarget>();

  if (IsVOPD3 && !ST.hasVOPD3())
    return false;
  if (IsVOPD3 && isVOPD3F64OPYSrcHazard(TII, MIX, MIY))
    return false;
  // Components which only map once src0 and src1 are commuted. The checks
  // below look at their operands as they will be after the commute.
  bool Commute[2] = {false, false};
  if (!IsVOPD3 &&
      ((TII.isVOP3(MIX) && !canMapVOP3PToVOPD(TII, MIX, Commute[VOPD::X])) ||
       (TII.isVOP3(MIY) && !canMapVOP3PToVOPD(TII, MIY, Commute[VOPD::Y]))))
    return false;
  if (TII.isDPP(MIX) || TII.isDPP(MIY))
    return false;

  // Collected here and handed over only on success, so a failed check cannot
  // leave anything behind.
  SmallVector<VOPDLiteralFixup, 2> Fixups;

  const SIRegisterInfo *TRI = ST.getRegisterInfo();
  const MachineRegisterInfo &MRI = MF->getRegInfo();
  // Literals also count against scalar bus limit
  SmallVector<const MachineOperand *> UniqueLiterals;
  auto AddLiteral = [&](const MachineOperand &Op) {
    for (auto &Literal : UniqueLiterals) {
      if (Literal->isIdenticalTo(Op))
        return;
    }
    UniqueLiterals.push_back(&Op);
  };
  // Immediates which the caller will move into a scalar register. Identical
  // values share one register, so they count like one scalar operand each.
  SmallSet<int32_t, 2> MaterializedLiterals;
  SmallSet<Register, 4> UniqueScalarRegs;

  unsigned EncodingFamily = AMDGPU::getVOPDEncodingFamily(ST);
  unsigned XOpc = AMDGPU::getVOPDOpcode(MIX.getOpcode(), IsVOPD3);
  unsigned YOpc = AMDGPU::getVOPDOpcode(MIY.getOpcode(), IsVOPD3);
  int VOPDOpc = AMDGPU::getVOPDFull(XOpc, YOpc, EncodingFamily, IsVOPD3);
  assert(VOPDOpc != -1);

  auto InstInfo = AMDGPU::getVOPDInstInfo(MIX.getDesc(), MIY.getDesc());

  for (auto CompIdx : VOPD::COMPONENTS) {
    const MachineInstr &MI = (CompIdx == VOPD::X) ? MIX : MIY;
    const AMDGPU::OpName Src0Name =
        Commute[CompIdx] ? AMDGPU::OpName::src1 : AMDGPU::OpName::src0;
    const AMDGPU::OpName Src1Name =
        Commute[CompIdx] ? AMDGPU::OpName::src0 : AMDGPU::OpName::src1;

    const MachineOperand &Src0 = *TII.getNamedOperand(MI, Src0Name);
    if (Src0.isReg()) {
      if (!isValidVOPDSrc(TII, VOPDOpc, CompIdx, 0, Src0.getReg()))
        return false;
      if (TII.regUsesConstantBus(Src0, MRI))
        UniqueScalarRegs.insert(Src0.getReg());
    } else if (!TII.isInlineConstant(Src0)) {
      if (!IsVOPD3) {
        AddLiteral(Src0);
      } else {
        // A VOPD3 component cannot encode a literal, but src0 can read a
        // scalar register. The pair is therefore still possible if the caller
        // moves the value into one.
        if (!canMaterializeVOPDLiterals(*MF) || !Src0.isImm())
          return false;
        // Only a 32-bit slot is handled, because the caller produces the value
        // with a single S_MOV_B32.
        int OpIdx = getNamedOperandIdx(MI.getOpcode(), Src0Name);
        if (TII.getOpSize(MI, OpIdx) != 4)
          return false;
        const TargetRegisterClass *SlotRC =
            TRI->getCommonSubClass(getVOPDSrcRegClass(TII, VOPDOpc, CompIdx, 0),
                                   &AMDGPU::SGPR_32RegClass);
        if (!SlotRC)
          return false;
        // Only the low bits reach the register, so two operands which name
        // the same value share one move whichever way they were written.
        int32_t Imm = static_cast<int32_t>(Src0.getImm());
        MaterializedLiterals.insert(Imm);
        Fixups.push_back({CompIdx, static_cast<unsigned>(OpIdx), Imm, SlotRC});
      }
    }

    // V_FMAMK_F32 (src1) and V_FMAAK_F32 (src2) have a mandatory literal.
    // VOPD3 instructions don't set MandatoryLiteralIdx.
    if (InstInfo[CompIdx].hasMandatoryLiteral()) {
      auto CompOprIdx = InstInfo[CompIdx].getMandatoryLiteralCompOperandIndex();
      AddLiteral(MI.getOperand(CompOprIdx));
    }

    // VOPD only. Affects V_CNDMASK_B32_e32.
    if (MI.getDesc().hasImplicitUseOfPhysReg(AMDGPU::VCC))
      UniqueScalarRegs.insert(AMDGPU::VCC_LO);

    if (const MachineOperand *Src1 = TII.getNamedOperand(MI, Src1Name)) {
      if (Src1->isReg()) {
        if (!isValidVOPDSrc(TII, VOPDOpc, CompIdx, 1, Src1->getReg()))
          return false;
        assert(TRI->isVectorRegister(MRI, Src1->getReg()));
      } else if (IsVOPD3) {
        return false;
      }
    }

    if (IsVOPD3) {
      if (const MachineOperand *Src2 =
              TII.getNamedOperand(MI, AMDGPU::OpName::src2)) {
        if (AMDGPU::hasNamedOperand(MI.getOpcode(), AMDGPU::OpName::bitop3)) {
          // BITOP3 can be converted to DUAL_BITOP2 when src2 is zero.
          if (!Src2->isImm() || Src2->getImm())
            return false;
        } else {
          if (!Src2->isReg())
            return false;
          if (!isValidVOPDSrc(TII, VOPDOpc, CompIdx, 2, Src2->getReg()))
            return false;
          if (TII.regUsesConstantBus(*Src2, MRI)) {
            assert(MI.getOpcode() == AMDGPU::V_CNDMASK_B32_e64);
            UniqueScalarRegs.insert(Src2->getReg());
          }
        }
      }
      for (auto OpName : {AMDGPU::OpName::clamp, AMDGPU::OpName::omod,
                          AMDGPU::OpName::op_sel}) {
        if (TII.hasModifiersSet(MI, OpName))
          return false;
      }

      // Neg is allowed, other modifiers are not. NB: even though sext has the
      // same value as neg, there are no combinable instructions with sext.
      for (auto OpName :
           {AMDGPU::OpName::src0_modifiers, AMDGPU::OpName::src1_modifiers,
            AMDGPU::OpName::src2_modifiers}) {
        const MachineOperand *Mods = TII.getNamedOperand(MI, OpName);
        if (Mods && (Mods->getImm() & ~SISrcMods::NEG))
          return false;
      }
    }
  }

  if (UniqueLiterals.size() > 1)
    return false;
  // Keep materialization pair-local and do not increase instruction count or
  // register pressure by producing two different values for one pair.
  if (MaterializedLiterals.size() > 1)
    return false;
  if ((UniqueLiterals.size() + MaterializedLiterals.size() +
       UniqueScalarRegs.size()) > 2)
    return false;

  auto GetVRegIdx = [&](unsigned OpcodeIdx, unsigned OperandIdx) {
    const MachineInstr &MI = (OpcodeIdx == VOPD::X) ? MIX : MIY;
    if (Commute[OpcodeIdx]) {
      int Src0Idx = getNamedOperandIdx(MI.getOpcode(), AMDGPU::OpName::src0);
      int Src1Idx = getNamedOperandIdx(MI.getOpcode(), AMDGPU::OpName::src1);
      if ((int)OperandIdx == Src0Idx)
        OperandIdx = Src1Idx;
      else if ((int)OperandIdx == Src1Idx)
        OperandIdx = Src0Idx;
    }
    const MachineOperand &Operand = MI.getOperand(OperandIdx);
    if (Operand.isReg() && TRI->isVectorRegister(MRI, Operand.getReg()))
      return Operand.getReg();
    return Register();
  };

  // On GFX1170+ if both OpX and OpY are V_MOV_B32 then OPY uses SRC2
  // source-cache.
  bool SkipSrc = (ST.hasGFX11_7Insts() || ST.hasGFX12Insts()) &&
                 MIX.getOpcode() == AMDGPU::V_MOV_B32_e32 &&
                 MIY.getOpcode() == AMDGPU::V_MOV_B32_e32;

  // Check VGPR bank constraints for operand registers across both instructions.
  if (InstInfo.hasInvalidOperand(GetVRegIdx, *TRI, SkipSrc, AllowSameVGPR,
                                 IsVOPD3, ST.hasVOPDInterlockHazard()))
    return false;

  LLVM_DEBUG(dbgs() << "VOPD Reg Constraints Passed\n\tX: " << MIX
                    << "\n\tY: " << MIY << "\n");
  LiteralFixups.assign(Fixups);
  CommuteXY[VOPD::X] = Commute[VOPD::X];
  CommuteXY[VOPD::Y] = Commute[VOPD::Y];
  return true;
}

/// Core pair-eligibility check for a single VOPD encoding variant (VOPD or
/// VOPD3).  Returns the X/Y assignment on success, or std::nullopt otherwise.
static std::optional<VOPDMatchInfo>
tryMatchVOPDPairVariant(const SIInstrInfo &TII, unsigned EncodingFamily,
                        MachineInstr &FirstMI, MachineInstr &SecondMI,
                        bool IsVOPD3) {
  unsigned Opc = FirstMI.getOpcode();
  unsigned Opc2 = SecondMI.getOpcode();
  AMDGPU::CanBeVOPD FirstCanBeVOPD =
      AMDGPU::getCanBeVOPD(Opc, EncodingFamily, IsVOPD3);
  AMDGPU::CanBeVOPD SecondCanBeVOPD =
      AMDGPU::getCanBeVOPD(Opc2, EncodingFamily, IsVOPD3);

  if (!(FirstCanBeVOPD.X && SecondCanBeVOPD.Y) &&
      !(FirstCanBeVOPD.Y && SecondCanBeVOPD.X))
    return std::nullopt;

  // If SecondMI depends on FirstMI they cannot execute at the same time.
  if (TII.hasRAWDependency(FirstMI, SecondMI))
    return std::nullopt;

  const GCNSubtarget &ST = TII.getSubtarget();
  bool AllowSameVGPR = ST.hasGFX12Insts();

  // Only a VOPD3 component can need a fixup; a plain one may hold a literal.
  // checkVOPDRegConstraints() only writes these when it succeeds.
  SmallVector<VOPDLiteralFixup, 2> Fixups;
  bool CommuteXY[2] = {false, false};

  if (FirstCanBeVOPD.X && SecondCanBeVOPD.Y) {
    if (checkVOPDRegConstraints(TII, FirstMI, SecondMI, IsVOPD3, AllowSameVGPR,
                                Fixups, CommuteXY))
      return VOPDMatchInfo{
          {&FirstMI, &SecondMI},
          0,
          IsVOPD3,
          std::move(Fixups),
          {CommuteXY[AMDGPU::VOPD::X], CommuteXY[AMDGPU::VOPD::Y]}};
  }

  if (FirstCanBeVOPD.Y && SecondCanBeVOPD.X) {
    // AllowSameVGPR relaxes the VGPR bank overlap check for source operands.
    // Only enable it when there is no antidependency.
    bool IsAntiDep = TII.hasRAWDependency(SecondMI, FirstMI);
    AllowSameVGPR &= !IsAntiDep;
    if (IsAntiDep && !TII.isVOPDAntidependencyAllowed(SecondMI))
      return std::nullopt;
    if (checkVOPDRegConstraints(TII, SecondMI, FirstMI, IsVOPD3, AllowSameVGPR,
                                Fixups, CommuteXY))
      return VOPDMatchInfo{
          {&FirstMI, &SecondMI},
          1,
          IsVOPD3,
          std::move(Fixups),
          {CommuteXY[AMDGPU::VOPD::Y], CommuteXY[AMDGPU::VOPD::X]}};
  }

  return std::nullopt;
}

std::optional<VOPDMatchInfo> llvm::tryMatchVOPDPair(const SIInstrInfo &TII,
                                                    MachineInstr &FirstMI,
                                                    MachineInstr &SecondMI) {
  const GCNSubtarget &ST = TII.getSubtarget();
  unsigned EncodingFamily = AMDGPU::getVOPDEncodingFamily(ST);
  if (auto Match = tryMatchVOPDPairVariant(TII, EncodingFamily, FirstMI,
                                           SecondMI, /*IsVOPD3=*/false))
    return Match;
  if (ST.hasVOPD3())
    return tryMatchVOPDPairVariant(TII, EncodingFamily, FirstMI, SecondMI,
                                   /*IsVOPD3=*/true);
  return std::nullopt;
}

/// Check if the instr pair, FirstMI and SecondMI, should be scheduled
/// together. Given SecondMI, when FirstMI is unspecified, then check if
/// SecondMI may be part of a fused pair at all.
static bool shouldScheduleVOPDAdjacent(const TargetInstrInfo &TII,
                                       const TargetSubtargetInfo &TSI,
                                       const MachineInstr *FirstMI,
                                       const MachineInstr &SecondMI,
                                       const SDep *) {
  const SIInstrInfo &STII = static_cast<const SIInstrInfo &>(TII);
  const GCNSubtarget &ST = STII.getSubtarget();

  // One instruction case: just check whether SecondMI is eligible at all.
  if (!FirstMI) {
    unsigned EncodingFamily = AMDGPU::getVOPDEncodingFamily(ST);
    unsigned Opc2 = SecondMI.getOpcode();
    auto CheckCanBeVOPD = [&](bool VOPD3) {
      AMDGPU::CanBeVOPD CanBeVOPD =
          AMDGPU::getCanBeVOPD(Opc2, EncodingFamily, VOPD3);
      return CanBeVOPD.Y || CanBeVOPD.X;
    };
    return CheckCanBeVOPD(false) || (ST.hasVOPD3() && CheckCanBeVOPD(true));
  }

#ifdef EXPENSIVE_CHECKS
  assert([&]() -> bool {
    for (auto MII = MachineBasicBlock::const_iterator(FirstMI);
         MII != FirstMI->getParent()->instr_end(); ++MII) {
      if (&*MII == &SecondMI)
        return true;
    }
    return false;
  }() && "Expected FirstMI to precede SecondMI");
#endif

  return tryMatchVOPDPair(STII, *const_cast<MachineInstr *>(FirstMI),
                          const_cast<MachineInstr &>(SecondMI))
      .has_value();
}

/// Collect all load (dependents if \p Forward else dependencies) that connect
/// to the \p Head SU.
/// \p Visited should allocate enough bits for the number of SUnits, but its
/// value can otherwise be uninitialized.
static void collectLoads(SmallPtrSet<SUnit *, 8> &Loads, BitVector &Visited,
                         SUnit &Head, bool Forward, bool StopAtLoads) {
  if (Head.isBoundaryNode())
    return;

  Visited.reset();

  SmallVector<SUnit *> Stack;
  Stack.push_back(&Head);
  while (!Stack.empty()) {
    SUnit *SU = Stack.pop_back_val();
    const SmallVector<SDep, 4> &Deps = Forward ? SU->Succs : SU->Preds;
    for (const SDep &Edge : Deps) {
      if (StopAtLoads && Edge.getKind() != SDep::Data)
        continue;
      SUnit *Dep = Edge.getSUnit();
      if (Dep->isBoundaryNode() || Visited.test(Dep->NodeNum))
        continue;
      Visited.set(Dep->NodeNum);

      if (Dep->isInstr() && Dep->getInstr()->mayLoad()) {
        Loads.insert(Dep);
        if (StopAtLoads)
          continue;
      }
      Stack.push_back(Dep);
    }
  }
}

/// Checks whether fusing SU \p I with SU \p J would force the loads preceding
/// \p J to complete before loads depending on \p I.
///
/// \p ILoadSuccs should hold all first load successors of \p I (via
/// collectLoads with StopAtLoads=true). For set bits in \p LoadPredsComputed,
/// the corresponding set in \p LoadPredsCache should hold all transitive load
/// dependencies (via collectLoads with StopAtLoads=false). The \p Scratch
/// bitvector should allocate enough bits for the number of SUnits.
static bool loadsMayOverlap(
    [[maybe_unused]] SUnit &I, const SmallPtrSet<SUnit *, 8> &ILoadSuccs,
    SUnit &J, BitVector &LoadPredsComputed,
    SmallVector<SmallPtrSet<SUnit *, 8>> &LoadPredsCache, BitVector &Scratch) {

  if (ILoadSuccs.empty())
    return false;

  SmallPtrSet<SUnit *, 8> &JLoadPreds = LoadPredsCache[J.NodeNum];
  if (!LoadPredsComputed.test(J.NodeNum)) {
    collectLoads(JLoadPreds, Scratch, J, /*Forward=*/false,
                 /*StopAtLoads=*/true);
    LoadPredsComputed.set(J.NodeNum);
  }
  if (JLoadPreds.empty())
    return false;

  for (SUnit *ILoad : ILoadSuccs) {
    SmallPtrSet<SUnit *, 8> &ILoadDeps = LoadPredsCache[ILoad->NodeNum];
    if (!LoadPredsComputed.test(ILoad->NodeNum)) {
      collectLoads(ILoadDeps, Scratch, *ILoad, /*Forward=*/false,
                   /*StopAtLoads=*/false);
      LoadPredsComputed.set(ILoad->NodeNum);
    }

    for (SUnit *JLoad : JLoadPreds) {
      if (ILoad == JLoad) {
        LLVM_DEBUG(
            dbgs() << "Will not pair " << I << " with " << J << "\n"
                   << "  Fusion would introduce a cyclic dependency with "
                   << *ILoad << "\n");
        return true;
      }

      if (!ILoadDeps.contains(JLoad)) {
        LLVM_DEBUG(dbgs() << "Will not pair " << I << " with " << J << "\n"
                          << "  Fusion may force " << *JLoad
                          << " to complete its load before dispatching "
                          << *ILoad << "\n");
        return true;
      }
    }
  }
  return false;
}

namespace {
/// Adapts design from MacroFusion
/// Puts valid candidate instructions back-to-back so they can easily
/// be turned into VOPD instructions
/// Greedily pairs instruction candidates. O(n^2) algorithm.
struct VOPDPairingMutation : ScheduleDAGMutation {
  MacroFusionPredTy shouldScheduleAdjacent; // NOLINT: function pointer

  VOPDPairingMutation(
      MacroFusionPredTy shouldScheduleAdjacent) // NOLINT: function pointer
      : shouldScheduleAdjacent(shouldScheduleAdjacent) {}

  void apply(ScheduleDAGInstrs *DAG) override {
    const TargetInstrInfo &TII = *DAG->TII;
    const GCNSubtarget &ST = DAG->MF.getSubtarget<GCNSubtarget>();
    if (!AMDGPU::hasVOPD(ST) || !ST.isWave32()) {
      LLVM_DEBUG(dbgs() << "Target does not support VOPDPairingMutation\n");
      return;
    }

    BitVector VOPDCapable(DAG->SUnits.size());
    unsigned IIdx = 0;
    // Pre-compute whether each individual instruction can be VOPD
    for (auto ISUI = DAG->SUnits.begin(), E = DAG->SUnits.end(); ISUI != E;
         ++ISUI, ++IIdx) {
      const MachineInstr *IMI = ISUI->getInstr();
      if (shouldScheduleAdjacent(TII, ST, nullptr, *IMI, nullptr) &&
          hasLessThanNumFused(*ISUI, 2))
        VOPDCapable[IIdx] = true;
    }

    IIdx = 0;
    SmallPtrSet<SUnit *, 8> ILoadSuccs;

    // Cache collected load predecessors.
    // For VOPDCapable nodes, this caches collectLoads with StopAtLoads=true
    // For loads, this caches collectLoads with StopAtLoads=false
    BitVector LoadPredsComputed(DAG->SUnits.size());
    SmallVector<SmallPtrSet<SUnit *, 8>> LoadPredsCache(DAG->SUnits.size());

    BitVector Scratch(DAG->SUnits.size());
    for (auto ISUI = DAG->SUnits.begin(), E = DAG->SUnits.end(); ISUI != E;
         ++ISUI, ++IIdx) {
      if (!VOPDCapable[IIdx])
        continue;
      const MachineInstr *IMI = ISUI->getInstr();

      ILoadSuccs.clear();
      collectLoads(ILoadSuccs, Scratch, *ISUI, /*Forward=*/true,
                   /*StopAtLoads=*/true);

      unsigned JIdx = IIdx + 1;
      for (auto JSUI = ISUI + 1; JSUI != E; ++JSUI, ++JIdx) {
        if (!VOPDCapable[JIdx] || JSUI->isBoundaryNode())
          continue;
        const MachineInstr *JMI = JSUI->getInstr();
        if (!hasLessThanNumFused(*JSUI, 2) ||
            !shouldScheduleAdjacent(TII, ST, IMI, *JMI, nullptr))
          continue;

        if (loadsMayOverlap(*ISUI, ILoadSuccs, *JSUI, LoadPredsComputed,
                            LoadPredsCache, Scratch))
          continue;

        if (fuseInstructionPair(*DAG, *ISUI, *JSUI)) {
          // Clear to prevent future checks/fusing
          VOPDCapable[JIdx] = false;
          break;
        }
      }
    }
    LLVM_DEBUG(dbgs() << "Completed VOPDPairingMutation\n");
  }
};
} // namespace

std::unique_ptr<ScheduleDAGMutation> llvm::createVOPDPairingMutation() {
  return std::make_unique<VOPDPairingMutation>(shouldScheduleVOPDAdjacent);
}