//===- AMDGPUCoExecSchedStrategy.cpp - CoExec Scheduling Strategy ---------===//
//
// 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
/// Coexecution-focused scheduling strategy for AMDGPU.
//
//===----------------------------------------------------------------------===//

#include "AMDGPUCoExecSchedStrategy.h"
#include "AMDGPUBarrierLatency.h"
#include "AMDGPUIGroupLP.h"
#include "GCNHazardRecognizer.h"
#include "llvm/Support/Debug.h"

using namespace llvm;
using namespace llvm::AMDGPU;

#define DEBUG_TYPE "machine-scheduler"

static cl::opt<CarriedLatency> BlockCarriedLatency(
    "amdgpu-block-carried-latency", cl::Hidden, cl::init(CarriedLatency::Off),
    cl::desc("Estimate block-carried latency and include it in the effective "
             "candidate stall cost."),
    cl::values(
        clEnumValN(CarriedLatency::Off, "off",
                   "Disabled - do not pad latency."),
        clEnumValN(CarriedLatency::Fence, "fence",
                   "Only pad latency for memory fence (e.g. those surrounding "
                   "barrier_signal/wait)."),
        clEnumValN(
            CarriedLatency::All, "all",
            "Pad latency for any SU with an incoming ds_load dependency.")));

// Default VGPR threshold percent for coexec scheduler.
static constexpr unsigned DefaultCoExecVGPRThresholdPercent = 100;

namespace {

// Used to disable post-RA scheduling with function level granularity.
class GCNNoopPostScheduleDAG final : public ScheduleDAGInstrs {
public:
  explicit GCNNoopPostScheduleDAG(MachineSchedContext *C)
      : ScheduleDAGInstrs(*C->MF, C->MLI, /*RemoveKillFlags=*/true) {}

  // Do nothing.
  void schedule() override {}
};

} // namespace

static SUnit *pickOnlyChoice(SchedBoundary &Zone) {
  // pickOnlyChoice() releases pending instructions and checks for new hazards.
  SUnit *OnlyChoice = Zone.pickOnlyChoice();
  if (!Zone.Pending.empty())
    return nullptr;

  return OnlyChoice;
}

/// Apply \p ExtraBits to every slot in \p Info starting with \p StartIndex
/// Used by MFMA co-exec rules, because MFMA co-exec slots are incremental, i.e.
/// for every slot N it supports all instructions which were supported by the
/// previous slot N-1 and may support something extra.
static void allowCoExec(llvm::AMDGPU::CoExecInfo &Info,
                        llvm::AMDGPU::CoExecMaskT ExtraBits,
                        unsigned StartIndex) {
  for (unsigned Index = StartIndex; Index < Info.TotalWindow; ++Index)
    Info.Slots[Index].Mask |= ExtraBits;
}

/// Get co-execution info for a gfx950 MFMA instruction.
/// The occupancy (cycles until the next MFMA may issue) is expressed as the
/// first stage carrying the WMMA bit.
llvm::AMDGPU::CoExecInfo llvm::AMDGPU::getMFMACoExecInfo(unsigned Opcode) {
  using namespace llvm;
  using namespace llvm::AMDGPU;
  CoExecInfo Res;
  for (unsigned I = 0; I < MaxCoExecStages; ++I)
    Res.Slots[I].Mask = CoExecMask::None;

  // TODO: Implement proper patterns support (for debugging purposes).
  // Existing pattern letters are WMMA-specific and will probably be confusing
  // if used as-is for MFMA. Inventing new MFMA-specific letters is an option,
  // but perhaps the pattern should be instead dynamically reconstructed when
  // needed by printing specific slots in full instead of a key for them.
  Res.Pattern = "undefinedundefinedundefinedundefined";

  switch (Opcode) {
  // 4-cycle occupancy, 8-cycle window.
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f4_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f4_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f4_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f4_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f6_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f6_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f6_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f6_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f4_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f4_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f4_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f4_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f6_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f6_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f6_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f6_gfx940_vcd:
  case V_MFMA_F32_16X16X32_BF16_e64:
  case V_MFMA_F32_16X16X32_BF16_vgprcd_e64:
  case V_MFMA_F32_16X16X32_BF16_gfx940_acd:
  case V_MFMA_F32_16X16X32_BF16_gfx940_vcd:
  case V_MFMA_I32_16X16X64_I8_e64:
  case V_MFMA_I32_16X16X64_I8_vgprcd_e64:
  case V_MFMA_I32_16X16X64_I8_gfx940_acd:
  case V_MFMA_I32_16X16X64_I8_gfx940_vcd:
  case V_MFMA_F32_16X16X32_F16_e64:
  case V_MFMA_F32_16X16X32_F16_vgprcd_e64:
  case V_MFMA_F32_16X16X32_F16_gfx940_acd:
  case V_MFMA_F32_16X16X32_F16_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f4_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f4_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f4_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f4_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f6_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f6_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f6_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f6_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f4_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f4_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f4_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f4_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f6_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f6_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f6_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f6_gfx940_vcd:
    // GFX9 Shader Programming Guide lists those SMFMAC separately, but for
    // intended purposes here all those instructions are the same. This comment
    // is to simplify reverse mapping to the SPG.
  case V_SMFMAC_F32_16X16X64_BF16_e64:
  case V_SMFMAC_F32_16X16X64_BF16_gfx940:
  case V_SMFMAC_I32_16X16X128_I8_e64:
  case V_SMFMAC_I32_16X16X128_I8_gfx940:
  case V_SMFMAC_F32_16X16X128_BF8_BF8_e64:
  case V_SMFMAC_F32_16X16X128_BF8_BF8_gfx940:
  case V_SMFMAC_F32_16X16X128_BF8_FP8_e64:
  case V_SMFMAC_F32_16X16X128_BF8_FP8_gfx940:
  case V_SMFMAC_F32_16X16X128_FP8_BF8_e64:
  case V_SMFMAC_F32_16X16X128_FP8_BF8_gfx940:
  case V_SMFMAC_F32_16X16X128_FP8_FP8_e64:
  case V_SMFMAC_F32_16X16X128_FP8_FP8_gfx940:
  case V_SMFMAC_F32_16X16X64_F16_e64:
  case V_SMFMAC_F32_16X16X64_F16_gfx940:
    Res.TotalWindow = 8;
    allowCoExec(Res, CoExecMask::SALU, 1);
    allowCoExec(Res, CoExecMask::DS | CoExecMask::VALU | CoExecMask::VMEM, 2);
    allowCoExec(Res, CoExecMask::WMMA, 4);
    return Res;

  // 8-cycle occupancy, 12-cycle window.
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f8_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f8_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f8_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f4_f8_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f8_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f8_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f8_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f6_f8_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f4_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f4_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f4_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f4_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f6_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f6_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f6_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f6_gfx940_vcd:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f8_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f8_vgprcd_e64:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f8_gfx940_acd:
  case V_MFMA_F32_16X16X128_F8F6F4_f8_f8_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f8_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f8_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f8_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f4_f8_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f8_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f8_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f8_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f6_f8_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f4_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f4_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f4_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f4_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f6_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f6_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f6_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f6_gfx940_vcd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f8_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f8_vgprcd_e64:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f8_gfx940_acd:
  case V_MFMA_SCALE_F32_16X16X128_F8F6F4_f8_f8_gfx940_vcd:
    Res.TotalWindow = 12;
    allowCoExec(Res, CoExecMask::SALU, 1);
    allowCoExec(Res, CoExecMask::DS | CoExecMask::VMEM, 2);
    allowCoExec(Res, CoExecMask::VALU, 3);
    allowCoExec(Res, CoExecMask::WMMA, 8);
    return Res;

  // 4-cycle occupancy, 8-cycle window.
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f4_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f4_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f4_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f4_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f4_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f4_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f6_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f6_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f6_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f6_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f6_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f6_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f4_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f4_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f4_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f4_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f4_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f4_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f6_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f6_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f6_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f6_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f6_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f6_gfx940_vcd:
  case V_MFMA_F32_32X32X16_BF16_e64:
  case V_MFMA_F32_32X32X16_BF16_mac_e64:
  case V_MFMA_F32_32X32X16_BF16_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X16_BF16_vgprcd_e64:
  case V_MFMA_F32_32X32X16_BF16_gfx940_acd:
  case V_MFMA_F32_32X32X16_BF16_gfx940_vcd:
  case V_MFMA_I32_32X32X32_I8_e64:
  case V_MFMA_I32_32X32X32_I8_mac_e64:
  case V_MFMA_I32_32X32X32_I8_mac_vgprcd_e64:
  case V_MFMA_I32_32X32X32_I8_vgprcd_e64:
  case V_MFMA_I32_32X32X32_I8_gfx940_acd:
  case V_MFMA_I32_32X32X32_I8_gfx940_vcd:
  case V_MFMA_F32_32X32X16_F16_e64:
  case V_MFMA_F32_32X32X16_F16_mac_e64:
  case V_MFMA_F32_32X32X16_F16_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X16_F16_vgprcd_e64:
  case V_MFMA_F32_32X32X16_F16_gfx940_acd:
  case V_MFMA_F32_32X32X16_F16_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f4_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f4_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f6_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f6_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f4_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f4_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f6_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f6_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f4_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f6_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f4_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f6_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f4_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f6_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f4_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f6_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f4_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f6_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f4_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f6_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f4_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f6_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f4_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f6_mac_vgprcd_e64:
    Res.TotalWindow = 8;
    allowCoExec(Res, CoExecMask::SALU, 1);
    allowCoExec(Res, CoExecMask::DS | CoExecMask::VALU | CoExecMask::VMEM, 2);
    allowCoExec(Res, CoExecMask::WMMA, 4);
    return Res;

  // 16-cycle occupancy, 20-cycle window.
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f8_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f8_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f8_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f8_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f8_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f4_f8_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f8_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f8_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f8_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f8_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f8_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f6_f8_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f4_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f4_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f4_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f4_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f4_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f4_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f6_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f6_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f6_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f6_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f6_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f6_gfx940_vcd:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f8_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f8_mac_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f8_mac_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f8_vgprcd_e64:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f8_gfx940_acd:
  case V_MFMA_F32_32X32X64_F8F6F4_f8_f8_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f8_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f8_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f4_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f6_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f8_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f8_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f8_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f4_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f6_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f8_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f8_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f8_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f4_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f6_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f8_mac_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f8_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f8_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f4_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f6_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f8_mac_vgprcd_e64:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f8_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f4_f8_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f8_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f6_f8_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f4_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f4_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f6_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f6_gfx940_vcd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f8_gfx940_acd:
  case V_MFMA_SCALE_F32_32X32X64_F8F6F4_f8_f8_gfx940_vcd:
    Res.TotalWindow = 20;
    allowCoExec(Res, CoExecMask::SALU, 1);
    allowCoExec(Res, CoExecMask::DS | CoExecMask::VMEM, 2);
    allowCoExec(Res, CoExecMask::VALU, 3);
    allowCoExec(Res, CoExecMask::WMMA, 16);
    return Res;

  // 9-cycle occupancy, 12-cycle window.
  case V_SMFMAC_F32_32X32X32_BF16_e64:
  case V_SMFMAC_F32_32X32X32_BF16_gfx940:
  case V_SMFMAC_I32_32X32X64_I8_e64:
  case V_SMFMAC_I32_32X32X64_I8_gfx940:
  case V_SMFMAC_F32_32X32X64_BF8_BF8_e64:
  case V_SMFMAC_F32_32X32X64_BF8_BF8_gfx940:
  case V_SMFMAC_F32_32X32X64_BF8_FP8_e64:
  case V_SMFMAC_F32_32X32X64_BF8_FP8_gfx940:
  case V_SMFMAC_F32_32X32X64_FP8_BF8_e64:
  case V_SMFMAC_F32_32X32X64_FP8_BF8_gfx940:
  case V_SMFMAC_F32_32X32X64_FP8_FP8_e64:
  case V_SMFMAC_F32_32X32X64_FP8_FP8_gfx940:
  case V_SMFMAC_F32_32X32X32_F16_e64:
  case V_SMFMAC_F32_32X32X32_F16_gfx940:
    Res.TotalWindow = 12;
    allowCoExec(Res, CoExecMask::SALU, 1);
    allowCoExec(Res, CoExecMask::DS | CoExecMask::VALU | CoExecMask::VMEM, 4);
    allowCoExec(Res, CoExecMask::WMMA, 9);
    return Res;

  // 18-cycle occupancy, 19-cycle window.
  case V_MFMA_F64_16X16X4F64_e64:
  case V_MFMA_F64_16X16X4F64_mac_e64:
  case V_MFMA_F64_16X16X4F64_mac_vgprcd_e64:
  case V_MFMA_F64_16X16X4F64_vgprcd_e64:
    Res.TotalWindow = 19;
    allowCoExec(Res, CoExecMask::DS | CoExecMask::SALU | CoExecMask::VMEM, 0);
    allowCoExec(Res, CoExecMask::WMMA | CoExecMask::VALU, 18);
    return Res;

  default:
    // Default fallback: permissive 8-cycle pattern
    return CoExecInfo::build(0, 9, "AAAAAAAAA");
  }
}

InstructionFlavor llvm::AMDGPU::classifyFlavor(const MachineInstr &MI,
                                               const SIInstrInfo &SII) {
  if (MI.isDebugInstr())
    return InstructionFlavor::Other;

  unsigned Opc = MI.getOpcode();

  // Check for specific opcodes first.
  if (Opc == AMDGPU::ATOMIC_FENCE || Opc == AMDGPU::S_BARRIER_WAIT ||
      Opc == AMDGPU::S_BARRIER_SIGNAL_IMM || SII.isWaitcnt(Opc))
    return InstructionFlavor::Fence;

  if (SII.isLDSDMA(MI))
    return InstructionFlavor::DMA;

  if (SII.isMFMA(MI)) {
    // TODO: Consider further sub-classifying this (XDL, XDL2x, S/DGEMM).
    // GFX9 SPG sub-classifies MFMA into XDL, XDL2x and S/DGEMM, because only
    // certain sub-classes can be co-executed in certain slots. For now, we
    // simply treat them all as one to simplify the change and leave the rest
    // to a follow-up fine-tuning.
    return InstructionFlavor::WMMA;
  }

  if (SII.isWMMA(MI) || SII.isSWMMAC(MI))
    return InstructionFlavor::WMMA;

  if (SII.isTRANS(MI))
    return InstructionFlavor::TRANS;

  if (SII.isVALU(MI, /*AllowLDSDMA=*/false)) {
    if (SII.getBlockingCycles(MI) > 1)
      return InstructionFlavor::MultiCycleVALU;

    return InstructionFlavor::SingleCycleVALU;
  }

  if (SII.isSMRD(MI))
    return InstructionFlavor::SMEM;

  if (SII.isDS(MI))
    return InstructionFlavor::DS;

  if (SII.isVMEM(MI))
    return InstructionFlavor::VMEM;

  if (SII.isSALU(MI))
    return InstructionFlavor::SALU;

  return InstructionFlavor::Other;
}

SUnit *HardwareUnitInfo::getNextTargetSU(bool LookDeep) const {
  for (SUnit *PrioritySU : PrioritySUs) {
    if (!PrioritySU->isTopReady())
      return PrioritySU;
  }

  if (!LookDeep)
    return nullptr;

  unsigned MinDepth = std::numeric_limits<unsigned int>::max();
  SUnit *TargetSU = nullptr;
  for (auto *SU : AllSUs) {
    if (SU->isScheduled)
      continue;

    if (SU->isTopReady())
      continue;

    if (SU->getDepth() < MinDepth) {
      MinDepth = SU->getDepth();
      TargetSU = SU;
    }
  }
  return TargetSU;
}

void HardwareUnitInfo::insert(SUnit *SU, unsigned BlockingCycles) {
  if (!AllSUs.insert(SU))
    llvm_unreachable("HardwareUnit already contains SU!");

  TotalCycles += BlockingCycles;

  if (PrioritySUs.empty()) {
    PrioritySUs.insert(SU);
    return;
  }
  unsigned SUDepth = SU->getDepth();
  unsigned CurrDepth = (*PrioritySUs.begin())->getDepth();
  if (SUDepth > CurrDepth)
    return;

  if (SUDepth == CurrDepth) {
    PrioritySUs.insert(SU);
    return;
  }

  // SU is lower depth and should be prioritized.
  PrioritySUs.clear();
  PrioritySUs.insert(SU);
}

void HardwareUnitInfo::markScheduled(SUnit *SU, unsigned BlockingCycles) {
  // We may want to ignore some HWUIs (e.g. InstructionFlavor::Other). To do so,
  // we just clear the HWUI. However, we still have instructions which map to
  // this HWUI. Don't bother managing the state for these HWUI.
  if (TotalCycles == 0)
    return;

  ScheduledSUs.push_back(SU);
  AllSUs.remove(SU);
  PrioritySUs.remove(SU);

  // BufferSize 0 is unlimited, while size 1 has no parallel buffering. In
  // either case, each SU uses the HardwareUnit for BlockingCycles.
  if (BufferSize <= 1 || (ScheduledSUs.size() % BufferSize == 0))
    TotalCycles -= std::min(TotalCycles, BlockingCycles);

  if (AllSUs.empty())
    return;
  if (PrioritySUs.empty()) {
    for (auto SU : AllSUs) {
      if (PrioritySUs.empty()) {
        PrioritySUs.insert(SU);
        continue;
      }
      unsigned SUDepth = SU->getDepth();
      unsigned CurrDepth = (*PrioritySUs.begin())->getDepth();
      if (SUDepth > CurrDepth)
        continue;

      if (SUDepth == CurrDepth) {
        PrioritySUs.insert(SU);
        continue;
      }

      // SU is lower depth and should be prioritized.
      PrioritySUs.clear();
      PrioritySUs.insert(SU);
    }
  }
}

void HardwareUnitInfo::finalizeCycles() {
  if (BufferSize == 0 || AllSUs.empty())
    return;

  // We estimate the amount of cycles it takes to free up a slot in the buffer
  // as the average cycles per SU.
  BufferCycles = TotalCycles / AllSUs.size();
  // A single-entry buffer does not reduce TotalCycles.
  if (BufferSize == 1)
    return;

  // The TotalCycles is normalized against the BufferSize.
  // This provides an estimate of the TotalCycles which is not always accurate
  // -- particularly in cases where we have fewer instructions than the
  // BufferSize. For example, if we have 2 instructions which each take 50
  // cycles and a BufferSize of 16, then a TotalCycles of 51 cycles would be
  // somewhat accurate. This normalization calculates TotalCycles as 6. However,
  // if we have 64 of these instructions, our normalized estimate of 200 is more
  // reasonable, given the more accurate measure is 264. Having a completely
  // accurate measure is not very important, since this metric is mainly used to
  // compare the relative demand per HardwareUnit across the region. The simpler
  // estimate makes managing the metric incrementally during scheduling much
  // simpler.
  TotalCycles /= BufferSize;
}

HardwareUnitInfo *
CandidateHeuristics::getHWUIFromFlavor(InstructionFlavor Flavor) {
  for (HardwareUnitInfo &HWUICand : HWUInfo) {
    if (HWUICand.getType() == Flavor) {
      return &HWUICand;
    }
  }
  return nullptr;
}

unsigned CandidateHeuristics::getMaxBlockingCycles(const MCSchedClassDesc *SC,
                                                   const MachineInstr *MI) {
  unsigned ReleaseAtCycle = 0;
  for (TargetSchedModel::ProcResIter PI = SchedModel->getWriteProcResBegin(SC),
                                     PE = SchedModel->getWriteProcResEnd(SC);
       PI != PE; ++PI) {
    ReleaseAtCycle =
        std::max(ReleaseAtCycle, static_cast<unsigned>(PI->ReleaseAtCycle));
  }
  ReleaseAtCycle = std::max(ReleaseAtCycle, SII->getBlockingCycles(*MI));
  return ReleaseAtCycle;
}

unsigned CandidateHeuristics::getHWUICyclesForMI(MachineInstr *MI) {
  assert(SchedModel && SchedModel->hasInstrSchedModel());
  if (MI->mayLoadOrStore())
    return SchedModel->computeInstrLatency(MI, false);
  return getMaxBlockingCycles(SchedModel->resolveSchedClass(MI), MI);
}

void CandidateHeuristics::updateForScheduling(SUnit *SU) {
  MachineInstr *MI = SU->getInstr();
  HardwareUnitInfo *HWUI = getHWUIFromFlavor(classifyFlavor(*MI, *SII));
  assert(HWUI);
  HWUI->markScheduled(SU, getHWUICyclesForMI(MI));
}

void CandidateHeuristics::initialize(ScheduleDAGMI *SchedDAG,
                                     const TargetSchedModel *TargetSchedModel,
                                     const TargetRegisterInfo *TRI,
                                     const MachineLoopInfo *LoopInfo) {
  DAG = SchedDAG;
  SchedModel = TargetSchedModel;
  MLI = LoopInfo;
  assert(SchedModel && SchedModel->hasInstrSchedModel());

  SRI = static_cast<const SIRegisterInfo *>(TRI);
  SII = static_cast<const SIInstrInfo *>(DAG->TII);

  HWUInfo.resize(static_cast<int>(InstructionFlavor::NUM_FLAVORS));

  for (unsigned I = 0; I < HWUInfo.size(); I++) {
    HWUInfo[I].reset();
    HWUInfo[I].setType(I);
  }

  HWUInfo[static_cast<int>(InstructionFlavor::WMMA)].setProducesCoexecWindow(
      true);
  HWUInfo[static_cast<int>(InstructionFlavor::MultiCycleVALU)]
      .setProducesCoexecWindow(true);
  HWUInfo[static_cast<int>(InstructionFlavor::TRANS)].setProducesCoexecWindow(
      true);
  HWUInfo[static_cast<int>(InstructionFlavor::DS)].setBufferSize(
      DefaultBufferSizes::DS);

  collectRegionSummary();
}

unsigned CandidateHeuristics::getCarriedLatency(SUnit *SU) {
  if (RegionCarriedLatency == CarriedLatency::Off)
    return 0;

  MachineInstr *MI = SU->getInstr();
  unsigned CarriedLatency = 0;
  const InstructionFlavor Flavor = classifyFlavor(*MI, *SII);
  if (Flavor == InstructionFlavor::Fence) {
    MachineBasicBlock *MBB = MI->getParent();
    // Scan each direct predecessor back to its nearest Fence or block start for
    // DS instructions.
    for (auto PredMBB : MBB->predecessors()) {
      auto I = PredMBB->rbegin();
      auto E = PredMBB->rend();
      for (; I != E; I++) {
        const InstructionFlavor ItFlavor = classifyFlavor(*I, *SII);
        if (ItFlavor == InstructionFlavor::Fence)
          break;

        // Found carried latency.
        if (ItFlavor == InstructionFlavor::DS)
          CarriedLatency = std::max(CarriedLatency, getHWUICyclesForMI(&*I));
      }
    }
  }

  if (RegionCarriedLatency == CarriedLatency::Fence)
    return CarriedLatency;

  for (MachineOperand &Op : MI->all_uses()) {
    auto Reg = Op.getReg();
    if (!Reg.isVirtual())
      continue;

    for (MachineInstr &Def : DAG->MRI.def_instructions(Reg)) {
      // We don't have the proper modelling to accurately measure all carried
      // latency. Just try to measure carried latency for long latency loads to
      // avoid long stalls.
      if (!Def.mayLoad())
        continue;

      unsigned Latency = getHWUICyclesForMI(&Def);

      // Load is carried across block.
      if (Def.getParent() != MI->getParent()) {
        bool FoundUseInDefBlock = false;
        for (MachineInstr &Use : DAG->MRI.use_nodbg_instructions(Reg)) {
          if (Use.getParent() != Def.getParent())
            continue;

          SlotIndex DefIdx = DAG->getLIS()->getInstructionIndex(Def);
          SlotIndex UseIdx = DAG->getLIS()->getInstructionIndex(Use);
          // We have a use of this load in the def block that occurs after the
          // load. In this case we must wait for the load in the def block, and
          // we do not have any carried latency from this load.
          if (SlotIndex::isEarlierInstr(DefIdx, UseIdx)) {
            FoundUseInDefBlock = true;
            break;
          }
        }
        if (!FoundUseInDefBlock)
          CarriedLatency = std::max(Latency, CarriedLatency);

        continue;
      }

      assert(Def.getParent() == MI->getParent());
      // Load is in the same block.
      SlotIndex LoadIdx = DAG->getLIS()->getInstructionIndex(Def);
      SlotIndex UseIdx = DAG->getLIS()->getInstructionIndex(*MI);
      // The load occurs after this use -- the latency is carried across loop
      // backedge.
      if (SlotIndex::isEarlierInstr(UseIdx, LoadIdx))
        CarriedLatency = std::max(Latency, CarriedLatency);
    }
  }
  return CarriedLatency;
}

void CandidateHeuristics::collectRegionSummary() {
  CarriedLatencies.clear();
  RegionCarriedLatency = CarriedLatency::Off;

  if (!SchedModel || !SchedModel->hasInstrSchedModel())
    return;

  // In some cases, we may end up with loads at the end of a predecssor block.
  // In these cases, it is preferable to defer scheduling a fence which
  // corresponds with a waitcnt for those loads until the latency of the load
  // has cleared. Unfortunately, there is no reliable way to determine whether
  // or not a predecessor block will end up scheduling loads at the end. Here,
  // we inspect the dependency structure to define a rough heuristic: if we
  // must schedule  ds_loads after wmma, then we carry the latency of ds_loads
  // to successor block fences. Currently this only checks for the loop-carried
  // case, as this will generally have the largest impact on performance.
  // TODO: 1. extend to different memory instructions, 2. teach carried
  // latencies about fence legalization.
  auto mustHaveDSAfter = [this]() {
    if (!DAG->SUnits.size())
      return false;

    MachineBasicBlock *MBB = DAG->begin()->getParent();
    MachineLoop *Loop = MLI->getLoopFor(MBB);
    if (!Loop || Loop->getNumBlocks() != 1)
      return false;

    SmallVector<SUnit *, 16> RegionWMMAs;

    for (auto &SU : DAG->SUnits) {
      if (!SU.getInstr())
        continue;
      MachineInstr *MI = SU.getInstr();
      const InstructionFlavor Flavor = classifyFlavor(*MI, *SII);
      if (Flavor == InstructionFlavor::WMMA)
        RegionWMMAs.push_back(&SU);
    }

    bool MustHaveDSAfter = RegionWMMAs.size();

    for (SUnit *SU : RegionWMMAs) {
      bool HasDSSucc = false;
      for (auto &Succ : SU->Succs) {
        if (!Succ.getSUnit()->getInstr())
          continue;
        if (classifyFlavor(*Succ.getSUnit()->getInstr(), *SII) ==
            InstructionFlavor::DS) {
          HasDSSucc = true;
          break;
        }
      }

      if (!HasDSSucc) {
        MustHaveDSAfter = false;
        break;
      }
    }

    return MustHaveDSAfter;
  };

  RegionCarriedLatency = BlockCarriedLatency.getNumOccurrences()
                             ? BlockCarriedLatency
                         : mustHaveDSAfter() ? CarriedLatency::Fence
                                             : CarriedLatency::Off;

  for (auto &SU : DAG->SUnits) {
    MachineInstr *MI = SU.getInstr();
    const InstructionFlavor Flavor = classifyFlavor(*MI, *SII);
    HWUInfo[static_cast<int>(Flavor)].insert(&SU, getHWUICyclesForMI(MI));
    unsigned CarriedLatency = getCarriedLatency(&SU);
    if (CarriedLatency)
      CarriedLatencies[MI] = CarriedLatency;
  }

  for (auto &HWUI : HWUInfo)
    HWUI.finalizeCycles();

  LLVM_DEBUG(dumpRegionSummary());
}

void CandidateHeuristics::dumpRegionSummary() {
  MachineBasicBlock *BB = DAG->begin()->getParent();
  dbgs() << "\n=== Region: " << DAG->MF.getName() << " BB" << BB->getNumber()
         << " (" << DAG->SUnits.size() << " SUs) ===\n";

  dbgs() << "\nHWUI Resource Pressure:\n";
  for (auto &HWUI : HWUInfo) {
    if (HWUI.getTotalCycles() == 0)
      continue;

    StringRef Name = getFlavorName(HWUI.getType());
    dbgs() << "  " << Name << ": " << HWUI.getTotalCycles() << " cycles, "
           << HWUI.size() << " instrs\n";
  }
  dbgs() << "\n";
}

void CandidateHeuristics::sortHWUIResources() {
  // Highest priority should be first.
  llvm::sort(HWUInfo, [](HardwareUnitInfo &A, HardwareUnitInfo &B) {
    // Prefer CoexecWindow producers
    if (A.producesCoexecWindow() != B.producesCoexecWindow())
      return A.producesCoexecWindow();

    // Prefer more demanded resources
    if (A.getTotalCycles() != B.getTotalCycles())
      return A.getTotalCycles() > B.getTotalCycles();

    // In ties -- prefer the resource with more instructions
    if (A.size() != B.size())
      return A.size() < B.size();

    // Default to Flavor order
    return static_cast<unsigned>(A.getType()) <
           static_cast<unsigned>(B.getType());
  });
}

unsigned CandidateHeuristics::getStructuralStallCycles(SchedBoundary &Zone,
                                                       SUnit *SU) {
  assert(Zone.isTop() && "effective stall comparison requires top boundary");
  if (!SU)
    return 0;

  MachineInstr *MI = SU->getInstr();
  unsigned CurrCycle = Zone.getCurrCycle();
  unsigned Stall = 0;

  // Query SchedModel for resource stalls (unbuffered resources).
  if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
    const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
    for (const MCWriteProcResEntry &PE :
         make_range(SchedModel->getWriteProcResBegin(SC),
                    SchedModel->getWriteProcResEnd(SC))) {
      unsigned NextAvail =
          Zone.getNextResourceCycle(SC, PE.ProcResourceIdx, PE.ReleaseAtCycle,
                                    PE.AcquireAtCycle)
              .first;
      if (NextAvail > CurrCycle)
        Stall = std::max(Stall, NextAvail - CurrCycle);
    }
  }

  // Query HazardRecognizer for sequence-dependent hazard penalties.
  if (Zone.HazardRec && Zone.HazardRec->isEnabled()) {
    auto *HR = static_cast<GCNHazardRecognizer *>(Zone.HazardRec.get());
    Stall = std::max(Stall, HR->getHazardWaitStates(MI));
  }

  return Stall;
}

CandidateHeuristics::StallCosts
CandidateHeuristics::getStallCosts(SUnit *SU, SchedBoundary &Zone) {
  if (!Zone.isTop())
    return {};

  auto getBufferFullStalls = [this, &Zone](SUnit *SU) -> unsigned {
    InstructionFlavor Flavor = classifyFlavor(
        *SU->getInstr(), *static_cast<const SIInstrInfo *>(DAG->TII));
    HardwareUnitInfo *HWUI = getHWUIFromFlavor(Flavor);

    // A BufferSize of 0 means "unlimited" buffer, thus we will never fill it.
    if (HWUI->getBufferSize() == 0)
      return 0;

    unsigned CurrCycle = Zone.getCurrCycle();
    unsigned BufferReadyCycle = HWUI->getBufferAvailableCycle(CurrCycle);
    if (BufferReadyCycle <= CurrCycle)
      return 0;

    return BufferReadyCycle - CurrCycle;
  };

  unsigned CurrCycle = Zone.getCurrCycle();

  auto getFenceStalls = [this, &CurrCycle](SUnit *SU) -> unsigned {
    InstructionFlavor Flavor = classifyFlavor(
        *SU->getInstr(), *static_cast<const SIInstrInfo *>(DAG->TII));

    if (Flavor != InstructionFlavor::Fence)
      return 0;

    HardwareUnitInfo *ConsumerHWUI = getHWUIFromFlavor(Flavor);
    HardwareUnitInfo *ProducerHWUI = getHWUIFromFlavor(InstructionFlavor::DS);

    SUnit *LastProducer = ProducerHWUI->getLastScheduledSU();
    if (!LastProducer)
      return 0;

    SUnit *LastConsumer = ConsumerHWUI->getLastScheduledSU();
    unsigned LastConsumerCycle = LastConsumer ? LastConsumer->TopReadyCycle : 0;
    unsigned LastProducerCycle = LastProducer->TopReadyCycle;

    if (LastProducerCycle < LastConsumerCycle)
      return 0;

    unsigned FenceStallFinish =
        LastProducerCycle + getHWUICyclesForMI(LastProducer->getInstr());
    return FenceStallFinish <= CurrCycle ? 0 : FenceStallFinish - CurrCycle;
  };

  unsigned ReadyCycle = SU->TopReadyCycle;
  StallCosts Costs;
  Costs.Ready = ReadyCycle > CurrCycle ? ReadyCycle - CurrCycle : 0;
  Costs.Structural = getStructuralStallCycles(Zone, SU);
  Costs.Latency = Zone.getLatencyStallCycles(SU);
  unsigned CarriedLatency = CarriedLatencies.lookup_or(SU->getInstr(), 0);
  Costs.Carried = CarriedLatency > CurrCycle ? CarriedLatency - CurrCycle : 0;
  Costs.Buffer = getBufferFullStalls(SU);
  Costs.Fence = getFenceStalls(SU);
  Costs.Effective = std::max({Costs.Ready, Costs.Structural, Costs.Latency,
                              Costs.Carried, Costs.Buffer, Costs.Fence});
  return Costs;
}

bool CandidateHeuristics::tryEffectiveStall(
    GenericSchedulerBase::SchedCandidate &TryCand,
    GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone) {
  // Only implemented for top-down scheduling
  if (!Zone.isTop())
    return 0;

  StallCosts TryCosts = getStallCosts(TryCand.SU, Zone);
  StallCosts CandCosts = getStallCosts(Cand.SU, Zone);

  LLVM_DEBUG(if (TryCosts.Effective || CandCosts.Effective) {
    dbgs() << "Effective stalls: try=" << TryCosts.Effective
           << " (ready=" << TryCosts.Ready << ", struct=" << TryCosts.Structural
           << ", lat=" << TryCosts.Latency << ", carried=" << TryCosts.Carried
           << ", buffer=" << TryCosts.Buffer << ", fence=" << TryCosts.Fence
           << ") cand=" << CandCosts.Effective << " (ready=" << CandCosts.Ready
           << ", struct=" << CandCosts.Structural
           << ", lat=" << CandCosts.Latency << ", carried=" << CandCosts.Carried
           << ", buffer=" << CandCosts.Buffer << ", fence=" << CandCosts.Fence
           << ")\n";
  });

  return tryLess(TryCosts.Effective, CandCosts.Effective, TryCand, Cand,
                 AMDGPUCoExecSchedStrategy::Stall);
}

bool CandidateHeuristics::tryMemoryPipeline(
    GenericSchedulerBase::SchedCandidate &TryCand,
    GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone) {

  InstructionFlavor TryFlavor = classifyFlavor(*TryCand.SU->getInstr(), *SII);

  InstructionFlavor CandFlavor = classifyFlavor(*Cand.SU->getInstr(), *SII);

  bool TryIsMemoryPipeline = TryFlavor == InstructionFlavor::DMA ||
                             TryFlavor == InstructionFlavor::Fence;
  bool CandIsMemoryPipeline = CandFlavor == InstructionFlavor::DMA ||
                              CandFlavor == InstructionFlavor::Fence;

  if (!(TryIsMemoryPipeline || CandIsMemoryPipeline))
    return false;

  if (TryIsMemoryPipeline)
    TryIsMemoryPipeline &= getStallCosts(TryCand.SU, Zone).Effective == 0;

  if (CandIsMemoryPipeline)
    CandIsMemoryPipeline &= getStallCosts(Cand.SU, Zone).Effective == 0;

  if (TryIsMemoryPipeline == CandIsMemoryPipeline)
    return false;

  if (CandIsMemoryPipeline) {
    if (Cand.Reason > GenericSchedulerBase::RegCritical)
      Cand.Reason = GenericSchedulerBase::RegCritical;

    return true;
  }

  TryCand.Reason = GenericSchedulerBase::RegCritical;
  return true;
}

bool CandidateHeuristics::tryCriticalResourceDependency(
    GenericSchedulerBase::SchedCandidate &TryCand,
    GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary *Zone) const {

  auto HasPrioritySU = [this, &Cand, &TryCand](unsigned ResourceIdx) {
    const HardwareUnitInfo &HWUI = HWUInfo[ResourceIdx];

    auto CandFlavor = classifyFlavor(*Cand.SU->getInstr(), *SII);
    auto TryCandFlavor = classifyFlavor(*TryCand.SU->getInstr(), *SII);
    bool LookDeep = (CandFlavor == InstructionFlavor::DS ||
                     TryCandFlavor == InstructionFlavor::DS) &&
                    HWUI.getType() == InstructionFlavor::WMMA;
    auto *TargetSU = HWUI.getNextTargetSU(LookDeep);

    // If we do not have a TargetSU for this resource, then it is not critical.
    if (!TargetSU)
      return false;

    return true;
  };

  auto TryEnablesResource = [&Cand, &TryCand, this](unsigned ResourceIdx) {
    const HardwareUnitInfo &HWUI = HWUInfo[ResourceIdx];
    auto CandFlavor = classifyFlavor(*Cand.SU->getInstr(), *SII);

    // We want to ensure our DS order matches WMMA order.
    bool LookDeep = CandFlavor == InstructionFlavor::DS &&
                    HWUI.getType() == InstructionFlavor::WMMA;
    auto *TargetSU = HWUI.getNextTargetSU(LookDeep);

    bool CandEnables =
        TargetSU != Cand.SU && DAG->IsReachable(TargetSU, Cand.SU);
    bool TryCandEnables =
        TargetSU != TryCand.SU && DAG->IsReachable(TargetSU, TryCand.SU);

    if (!CandEnables && !TryCandEnables)
      return false;

    if (CandEnables && !TryCandEnables) {
      if (Cand.Reason > GenericSchedulerBase::RegCritical)
        Cand.Reason = GenericSchedulerBase::RegCritical;

      return true;
    }

    if (!CandEnables && TryCandEnables) {
      TryCand.Reason = GenericSchedulerBase::RegCritical;
      return true;
    }

    // Both enable, prefer the critical path.
    unsigned CandHeight = Cand.SU->getHeight();
    unsigned TryCandHeight = TryCand.SU->getHeight();

    if (CandHeight > TryCandHeight) {
      if (Cand.Reason > GenericSchedulerBase::RegCritical)
        Cand.Reason = GenericSchedulerBase::RegCritical;

      return true;
    }

    if (CandHeight < TryCandHeight) {
      TryCand.Reason = GenericSchedulerBase::RegCritical;
      return true;
    }

    // Same critical path, just prefer original candidate.
    if (Cand.Reason > GenericSchedulerBase::RegCritical)
      Cand.Reason = GenericSchedulerBase::RegCritical;

    return true;
  };

  for (unsigned I = 0; I < HWUInfo.size(); I++) {
    // If we have encountered a resource that is not critical, then neither
    // candidate enables a critical resource
    if (!HasPrioritySU(I))
      continue;

    bool Enabled = TryEnablesResource(I);
    // If neither has enabled the resource, continue to the next resource
    if (Enabled)
      return true;
  }
  return false;
}

bool CandidateHeuristics::tryCriticalResource(
    GenericSchedulerBase::SchedCandidate &TryCand,
    GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary *Zone) const {
  for (unsigned I = 0; I < HWUInfo.size(); I++) {
    const HardwareUnitInfo &HWUI = HWUInfo[I];

    bool CandUsesCrit = HWUI.contains(Cand.SU);
    bool TryCandUsesCrit = HWUI.contains(TryCand.SU);

    if (!CandUsesCrit && !TryCandUsesCrit)
      continue;

    if (CandUsesCrit != TryCandUsesCrit) {
      if (CandUsesCrit) {
        if (Cand.Reason > GenericSchedulerBase::RegCritical)
          Cand.Reason = GenericSchedulerBase::RegCritical;
        return true;
      }
      TryCand.Reason = GenericSchedulerBase::RegCritical;
      return true;
    }

    // Otherwise, both use the critical resource
    // For longer latency InstructionFlavors, we should prioritize first by
    // their enablement of critical resources
    if (HWUI.getType() == InstructionFlavor::DS) {
      if (tryCriticalResourceDependency(TryCand, Cand, Zone))
        return true;
    }

    // Prioritize based on HWUI priorities.
    SUnit *Match = HWUI.getHigherPriority(Cand.SU, TryCand.SU);
    if (Match) {
      if (Match == Cand.SU) {
        if (Cand.Reason > GenericSchedulerBase::RegCritical)
          Cand.Reason = GenericSchedulerBase::RegCritical;
        return true;
      }
      TryCand.Reason = GenericSchedulerBase::RegCritical;
      return true;
    }
  }

  return false;
}

AMDGPUCoExecSchedStrategy::AMDGPUCoExecSchedStrategy(
    const MachineSchedContext *C)
    : GCNSchedStrategy(C) {
  SchedStages.push_back(GCNSchedStageID::ILPInitialSchedule);
  SchedStages.push_back(GCNSchedStageID::RewriteMFMAForm);
  SchedStages.push_back(GCNSchedStageID::LiveIntervalRPReschedule);
  SchedStages.push_back(GCNSchedStageID::PreRARematerialize);
  // Use more accurate GCN pressure trackers.
  UseGCNTrackers = true;

  if (!VGPRThresholdPercentOpt.getNumOccurrences())
    VGPRThresholdPercent = DefaultCoExecVGPRThresholdPercent;
}

void AMDGPUCoExecSchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
                                           MachineBasicBlock::iterator End,
                                           unsigned NumRegionInstrs) {
  GCNSchedStrategy::initPolicy(Begin, End, NumRegionInstrs);
  if (getPreRADirection() == MISched::BottomUp ||
      getPreRADirection() == MISched::Bidirectional)
    report_fatal_error("CoExecSchedStrategy only support TopDown scheduling.");
  RegionPolicy.OnlyTopDown = true;
  RegionPolicy.OnlyBottomUp = false;
  RegionPolicy.ShouldTrackLaneMasks = true;
}

void AMDGPUCoExecSchedStrategy::initialize(ScheduleDAGMI *DAG) {
  // Coexecution scheduling strategy is only done top-down to support new
  // resource balancing heuristics.
  RegionPolicy.OnlyTopDown = true;
  RegionPolicy.OnlyBottomUp = false;

  GCNSchedStrategy::initialize(DAG);
  Heurs.initialize(DAG, SchedModel, TRI, Context->MLI);

  // Replace the default hazard recognizer with our PreRA one so that pre-RA
  // scheduling accounts for WMMA co-execution slot constraints. This must
  // happen after GCNSchedStrategy::initialize() because
  // GenericScheduler::initialize() calls SchedBoundary::reset(), which deletes
  // and recreates the hazard recognizer each region.
  Top.HazardRec = std::make_unique<GCNHazardRecognizer>(
      DAG->MF, GCNHazardRecognizer::OperatingMode::PreRA);
}

void AMDGPUCoExecSchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
  Heurs.updateForScheduling(SU);
  GCNSchedStrategy::schedNode(SU, IsTopNode);
}

SUnit *AMDGPUCoExecSchedStrategy::pickNode(bool &IsTopNode) {
  assert(RegionPolicy.OnlyTopDown && !RegionPolicy.OnlyBottomUp &&
         "coexec scheduler only supports top-down scheduling");

  if (DAG->top() == DAG->bottom()) {
    assert(Top.Available.empty() && Top.Pending.empty() &&
           Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
    return nullptr;
  }

  bool PickedPending = false;
  SUnit *SU = nullptr;
#ifndef NDEBUG
  SchedCandidate *PickedCand = nullptr;
#endif
  do {
    PickedPending = false;
    SU = pickOnlyChoice(Top);
    if (!SU) {
      CandPolicy NoPolicy;
      TopCand.reset(NoPolicy);
      pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand,
                        PickedPending, /*IsBottomUp=*/false);
      assert(TopCand.Reason != NoCand && "failed to find a candidate");
      SU = TopCand.SU;
#ifndef NDEBUG
      PickedCand = &TopCand;
#endif
    }
    IsTopNode = true;
  } while (SU->isScheduled);

  LLVM_DEBUG(if (PickedCand) dumpPickSummary(SU, IsTopNode, *PickedCand));

  if (PickedPending) {
    unsigned ReadyCycle = SU->TopReadyCycle;
    unsigned CurrentCycle = Top.getCurrCycle();
    if (ReadyCycle > CurrentCycle)
      Top.bumpCycle(ReadyCycle);

    // checkHazard() does not expose the exact cycle where the hazard clears.
    while (Top.checkHazard(SU))
      Top.bumpCycle(Top.getCurrCycle() + 1);

    Top.releasePending();
  }

  if (SU->isTopReady())
    Top.removeReady(SU);
  if (SU->isBottomReady())
    Bot.removeReady(SU);

  LLVM_DEBUG(dbgs() << "Scheduling " << *SU << " " << *SU->getInstr());

  assert(IsTopNode && "coexec scheduler must only schedule from top boundary");
  return SU;
}

void AMDGPUCoExecSchedStrategy::pickNodeFromQueue(
    SchedBoundary &Zone, const CandPolicy &ZonePolicy,
    const RegPressureTracker &RPTracker, SchedCandidate &Cand,
    bool &PickedPending, bool IsBottomUp) {
  assert(Zone.isTop() && "coexec scheduler only supports top boundary");
  assert(!IsBottomUp && "coexec scheduler only supports top-down scheduling");

  const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo *>(TRI);
  ArrayRef<unsigned> Pressure = RPTracker.getRegSetPressureAtPos();
  unsigned SGPRPressure = 0;
  unsigned VGPRPressure = 0;
  unsigned AGPRPressure = 0;
  PickedPending = false;
  if (DAG->isTrackingPressure()) {
    if (!useGCNTrackers()) {
      SGPRPressure = Pressure[AMDGPU::RegisterPressureSets::SReg_32];
      VGPRPressure = Pressure[AMDGPU::RegisterPressureSets::VGPR_32];
      AGPRPressure = Pressure[AMDGPU::RegisterPressureSets::AGPR_32];
    } else {
      SGPRPressure = DownwardTracker.getPressure().getSGPRNum();
      VGPRPressure = DownwardTracker.getPressure().getArchVGPRNum();
      AGPRPressure = DownwardTracker.getPressure().getAGPRNum();
    }
  }

  auto EvaluateQueue = [&](ReadyQueue &Q, bool FromPending) {
    for (SUnit *SU : Q) {
      SchedCandidate TryCand(ZonePolicy);
      initCandidate(TryCand, SU, Zone.isTop(), RPTracker, SRI, SGPRPressure,
                    VGPRPressure, AGPRPressure, IsBottomUp);
      SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
      tryCandidateCoexec(Cand, TryCand, ZoneArg);
      if (TryCand.Reason != NoCand) {
        if (TryCand.ResDelta == SchedResourceDelta())
          TryCand.initResourceDelta(Zone.DAG, SchedModel);
        LLVM_DEBUG(printCandidateDecision(Cand, TryCand));
        PickedPending = FromPending;
        Cand.setBest(TryCand);
      } else {
        LLVM_DEBUG(printCandidateDecision(TryCand, Cand));
      }
    }
  };

  LLVM_DEBUG(dbgs() << "Available Q:\n");
  EvaluateQueue(Zone.Available, /*FromPending=*/false);

  LLVM_DEBUG(dbgs() << "Pending Q:\n");
  EvaluateQueue(Zone.Pending, /*FromPending=*/true);
}

#ifndef NDEBUG
void AMDGPUCoExecSchedStrategy::dumpPickSummary(SUnit *SU, bool IsTopNode,
                                                SchedCandidate &Cand) {
  const SIInstrInfo *SII = static_cast<const SIInstrInfo *>(DAG->TII);
  unsigned Cycle = IsTopNode ? Top.getCurrCycle() : Bot.getCurrCycle();

  dbgs() << "=== Pick @ Cycle " << Cycle << " ===\n";

  const InstructionFlavor Flavor = classifyFlavor(*SU->getInstr(), *SII);
  dbgs() << "Picked: " << *SU << " ";
  SU->getInstr()->print(dbgs(), /*IsStandalone=*/true, /*SkipOpers=*/false,
                        /*SkipDebugLoc=*/true);
  dbgs() << " [" << getFlavorName(Flavor) << "]\n";

  dbgs() << "  Reason: ";
  if (LastAMDGPUReason != AMDGPUSchedReason::None)
    dbgs() << getReasonName(LastAMDGPUReason);
  else if (Cand.Reason != NoCand)
    dbgs() << GenericSchedulerBase::getReasonStr(Cand.Reason);
  else
    dbgs() << "Unknown";
  dbgs() << "\n\n";

  LastAMDGPUReason = AMDGPUSchedReason::None;
}
#endif

bool AMDGPUCoExecSchedStrategy::tryCandidateCoexec(SchedCandidate &Cand,
                                                   SchedCandidate &TryCand,
                                                   SchedBoundary *Zone) {
  // Initialize the candidate if needed.
  if (!Cand.isValid()) {
    TryCand.Reason = FirstValid;
    return true;
  }

  // Bias PhysReg Defs and copies to their uses and defined respectively.
  if (tryGreater(biasPhysReg(TryCand.SU, TryCand.AtTop),
                 biasPhysReg(Cand.SU, Cand.AtTop), TryCand, Cand, PhysReg))
    return TryCand.Reason != NoCand;

  // Avoid exceeding the target's limit.
  if (DAG->isTrackingPressure() &&
      tryPressure(TryCand.RPDelta.Excess, Cand.RPDelta.Excess, TryCand, Cand,
                  RegExcess, TRI, DAG->MF))
    return TryCand.Reason != NoCand;

  // We only compare a subset of features when comparing nodes between
  // Top and Bottom boundary. Some properties are simply incomparable, in many
  // other instances we should only override the other boundary if something
  // is a clear good pick on one boundary. Skip heuristics that are more
  // "tie-breaking" in nature.
  bool SameBoundary = Zone != nullptr;
  if (SameBoundary) {
    // Compare candidates by the stall they would introduce if
    // scheduled in the current cycle.
    if (Heurs.tryEffectiveStall(TryCand, Cand, *Zone)) {
      LastAMDGPUReason = AMDGPUSchedReason::Stall;
      return TryCand.Reason != NoCand;
    }

    if (Heurs.tryMemoryPipeline(TryCand, Cand, *Zone)) {
      LastAMDGPUReason = AMDGPUSchedReason::MemoryPipeline;
      return TryCand.Reason != NoCand;
    }

    Heurs.sortHWUIResources();
    if (Heurs.tryCriticalResource(TryCand, Cand, Zone)) {
      LastAMDGPUReason = AMDGPUSchedReason::CritResourceBalance;
      return TryCand.Reason != NoCand;
    }

    if (Heurs.tryCriticalResourceDependency(TryCand, Cand, Zone)) {
      LastAMDGPUReason = AMDGPUSchedReason::CritResourceDep;
      return TryCand.Reason != NoCand;
    }
  }

  // Keep clustered nodes together to encourage downstream peephole
  // optimizations which may reduce resource requirements.
  //
  // This is a best effort to set things up for a post-RA pass. Optimizations
  // like generating loads of multiple registers should ideally be done within
  // the scheduler pass by combining the loads during DAG postprocessing.
  unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
  unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
  bool CandIsClusterSucc =
      isTheSameCluster(CandZoneCluster, Cand.SU->ParentClusterIdx);
  bool TryCandIsClusterSucc =
      isTheSameCluster(TryCandZoneCluster, TryCand.SU->ParentClusterIdx);

  if (tryGreater(TryCandIsClusterSucc, CandIsClusterSucc, TryCand, Cand,
                 Cluster))
    return TryCand.Reason != NoCand;

  if (SameBoundary) {
    // Weak edges are for clustering and other constraints.
    if (tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop),
                getWeakLeft(Cand.SU, Cand.AtTop), TryCand, Cand, Weak))
      return TryCand.Reason != NoCand;
  }

  // Avoid increasing the max pressure of the entire region.
  if (DAG->isTrackingPressure() &&
      tryPressure(TryCand.RPDelta.CurrentMax, Cand.RPDelta.CurrentMax, TryCand,
                  Cand, RegMax, TRI, DAG->MF))
    return TryCand.Reason != NoCand;

  if (SameBoundary) {
    // Avoid serializing long latency dependence chains.
    // For acyclic path limited loops, latency was already checked above.
    if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
        !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, *Zone))
      return TryCand.Reason != NoCand;

    // Fall through to original instruction order.
    if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) ||
        (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
      TryCand.Reason = NodeOrder;
      return true;
    }
  }

  return false;
}

ScheduleDAGInstrs *
llvm::createGCNCoExecMachineScheduler(MachineSchedContext *C) {
  LLVM_DEBUG(dbgs() << "AMDGPU coexec preRA scheduler selected for "
                    << C->MF->getName() << '\n');
  ScheduleDAGMILive *DAG = new GCNScheduleDAGMILive(
      C, std::make_unique<AMDGPUCoExecSchedStrategy>(C));
  DAG->addMutation(createIGroupLPDAGMutation(AMDGPU::SchedulingPhase::Initial));
  DAG->addMutation(createAMDGPUBarrierLatencyDAGMutation(C->MF));
  return DAG;
}

ScheduleDAGInstrs *
llvm::createGCNNoopPostMachineScheduler(MachineSchedContext *C) {
  LLVM_DEBUG(dbgs() << "AMDGPU nop postRA scheduler selected for "
                    << C->MF->getName() << '\n');
  return new GCNNoopPostScheduleDAG(C);
}