llvm/llvm/lib/CodeGen/SelectionDAG/ResourcePriorityQueue.cpp

//===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==//
//
// 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 file implements the ResourcePriorityQueue class, which is a
// SchedulingPriorityQueue that prioritizes instructions using DFA state to
// reduce the length of the critical path through the basic block
// on VLIW platforms.
// The scheduler is basically a top-down adaptable list scheduler with DFA
// resource tracking added to the cost function.
// DFA is queried as a state machine to model "packets/bundles" during
// schedule. Currently packets/bundles are discarded at the end of
// scheduling, affecting only order of instructions.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/ResourcePriorityQueue.h"
#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Support/CommandLine.h"

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool>
    DisableDFASched("disable-dfa-sched", cl::Hidden,
                    cl::desc("Disable use of DFA during scheduling"));

static cl::opt<int> RegPressureThreshold(
    "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::init(5),
    cl::desc("Track reg pressure and switch priority to in-depth"));

ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS)
    : … { … }

unsigned
ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) { … }

unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
                                                    unsigned RCId) { … }

static unsigned numberCtrlDepsInSU(SUnit *SU) { … }

static unsigned numberCtrlPredInSU(SUnit *SU) { … }

///
/// Initialize nodes.
///
void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) { … }

/// This heuristic is used if DFA scheduling is not desired
/// for some VLIW platform.
bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { … }


/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
/// of SU, return it, otherwise return null.
SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) { … }

void ResourcePriorityQueue::push(SUnit *SU) { … }

/// Check if scheduling of this SU is possible
/// in the current packet.
bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) { … }

/// Keep track of available resources.
void ResourcePriorityQueue::reserveResources(SUnit *SU) { … }

int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) { … }

/// Estimates change in reg pressure from this SU.
/// It is achieved by trivial tracking of defined
/// and used vregs in dependent instructions.
/// The RawPressure flag makes this function to ignore
/// existing reg file sizes, and report raw def/use
/// balance.
int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) { … }

// Constants used to denote relative importance of
// heuristic components for cost computation.
static const unsigned PriorityOne = …;
static const unsigned PriorityTwo = …;
static const unsigned PriorityThree = …;
static const unsigned PriorityFour = …;
static const unsigned ScaleOne = …;
static const unsigned ScaleTwo = …;
static const unsigned ScaleThree = …;
static const unsigned FactorOne = …;

/// Returns single number reflecting benefit of scheduling SU
/// in the current cycle.
int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) { … }


/// Main resource tracking point.
void ResourcePriorityQueue::scheduledNode(SUnit *SU) { … }

void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) { … }

/// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
/// scheduled.  If SU is not itself available, then there is at least one
/// predecessor node that has not been scheduled yet.  If SU has exactly ONE
/// unscheduled predecessor, we want to increase its priority: it getting
/// scheduled will make this node available, so it is better than some other
/// node of the same priority that will not make a node available.
void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) { … }


/// Main access point - returns next instructions
/// to be placed in scheduling sequence.
SUnit *ResourcePriorityQueue::pop() { … }


void ResourcePriorityQueue::remove(SUnit *SU) { … }