llvm/llvm/lib/CodeGen/MachinePipeliner.cpp

//===- MachinePipeliner.cpp - Machine Software Pipeliner 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
//
//===----------------------------------------------------------------------===//
//
// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
//
// This SMS implementation is a target-independent back-end pass. When enabled,
// the pass runs just prior to the register allocation pass, while the machine
// IR is in SSA form. If software pipelining is successful, then the original
// loop is replaced by the optimized loop. The optimized loop contains one or
// more prolog blocks, the pipelined kernel, and one or more epilog blocks. If
// the instructions cannot be scheduled in a given MII, we increase the MII by
// one and try again.
//
// The SMS implementation is an extension of the ScheduleDAGInstrs class. We
// represent loop carried dependences in the DAG as order edges to the Phi
// nodes. We also perform several passes over the DAG to eliminate unnecessary
// edges that inhibit the ability to pipeline. The implementation uses the
// DFAPacketizer class to compute the minimum initiation interval and the check
// where an instruction may be inserted in the pipelined schedule.
//
// In order for the SMS pass to work, several target specific hooks need to be
// implemented to get information about the loop structure and to rewrite
// instructions.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/MachinePipeliner.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CycleAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/ModuloSchedule.h"
#include "llvm/CodeGen/Register.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Function.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iterator>
#include <map>
#include <memory>
#include <sstream>
#include <tuple>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline");
STATISTIC(NumPipelined, "Number of loops software pipelined");
STATISTIC(NumNodeOrderIssues, "Number of node order issues found");
STATISTIC(NumFailBranch, "Pipeliner abort due to unknown branch");
STATISTIC(NumFailLoop, "Pipeliner abort due to unsupported loop");
STATISTIC(NumFailPreheader, "Pipeliner abort due to missing preheader");
STATISTIC(NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large");
STATISTIC(NumFailZeroMII, "Pipeliner abort due to zero MII");
STATISTIC(NumFailNoSchedule, "Pipeliner abort due to no schedule found");
STATISTIC(NumFailZeroStage, "Pipeliner abort due to zero stage");
STATISTIC(NumFailLargeMaxStage, "Pipeliner abort due to too many stages");

/// A command line option to turn software pipelining on or off.
static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true),
                               cl::desc("Enable Software Pipelining"));

/// A command line option to enable SWP at -Os.
static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size",
                                      cl::desc("Enable SWP at Os."), cl::Hidden,
                                      cl::init(false));

/// A command line argument to limit minimum initial interval for pipelining.
static cl::opt<int> SwpMaxMii("pipeliner-max-mii",
                              cl::desc("Size limit for the MII."),
                              cl::Hidden, cl::init(27));

/// A command line argument to force pipeliner to use specified initial
/// interval.
static cl::opt<int> SwpForceII("pipeliner-force-ii",
                               cl::desc("Force pipeliner to use specified II."),
                               cl::Hidden, cl::init(-1));

/// A command line argument to limit the number of stages in the pipeline.
static cl::opt<int>
    SwpMaxStages("pipeliner-max-stages",
                 cl::desc("Maximum stages allowed in the generated scheduled."),
                 cl::Hidden, cl::init(3));

/// A command line option to disable the pruning of chain dependences due to
/// an unrelated Phi.
static cl::opt<bool>
    SwpPruneDeps("pipeliner-prune-deps",
                 cl::desc("Prune dependences between unrelated Phi nodes."),
                 cl::Hidden, cl::init(true));

/// A command line option to disable the pruning of loop carried order
/// dependences.
static cl::opt<bool>
    SwpPruneLoopCarried("pipeliner-prune-loop-carried",
                        cl::desc("Prune loop carried order dependences."),
                        cl::Hidden, cl::init(true));

#ifndef NDEBUG
static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
#endif

static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
                                     cl::ReallyHidden,
                                     cl::desc("Ignore RecMII"));

static cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden,
                                    cl::init(false));
static cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden,
                                      cl::init(false));

static cl::opt<bool> EmitTestAnnotations(
    "pipeliner-annotate-for-testing", cl::Hidden, cl::init(false),
    cl::desc("Instead of emitting the pipelined code, annotate instructions "
             "with the generated schedule for feeding into the "
             "-modulo-schedule-test pass"));

static cl::opt<bool> ExperimentalCodeGen(
    "pipeliner-experimental-cg", cl::Hidden, cl::init(false),
    cl::desc(
        "Use the experimental peeling code generator for software pipelining"));

static cl::opt<int> SwpIISearchRange("pipeliner-ii-search-range",
                                     cl::desc("Range to search for II"),
                                     cl::Hidden, cl::init(10));

static cl::opt<bool>
    LimitRegPressure("pipeliner-register-pressure", cl::Hidden, cl::init(false),
                     cl::desc("Limit register pressure of scheduled loop"));

static cl::opt<int>
    RegPressureMargin("pipeliner-register-pressure-margin", cl::Hidden,
                      cl::init(5),
                      cl::desc("Margin representing the unused percentage of "
                               "the register pressure limit"));

static cl::opt<bool>
    MVECodeGen("pipeliner-mve-cg", cl::Hidden, cl::init(false),
               cl::desc("Use the MVE code generator for software pipelining"));

namespace llvm {

// A command line option to enable the CopyToPhi DAG mutation.
cl::opt<bool> SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
                                 cl::init(true),
                                 cl::desc("Enable CopyToPhi DAG Mutation"));

/// A command line argument to force pipeliner to use specified issue
/// width.
cl::opt<int> SwpForceIssueWidth(
    "pipeliner-force-issue-width",
    cl::desc("Force pipeliner to use specified issue width."), cl::Hidden,
    cl::init(-1));

/// A command line argument to set the window scheduling option.
cl::opt<WindowSchedulingFlag> WindowSchedulingOption(
    "window-sched", cl::Hidden, cl::init(WindowSchedulingFlag::WS_On),
    cl::desc("Set how to use window scheduling algorithm."),
    cl::values(clEnumValN(WindowSchedulingFlag::WS_Off, "off",
                          "Turn off window algorithm."),
               clEnumValN(WindowSchedulingFlag::WS_On, "on",
                          "Use window algorithm after SMS algorithm fails."),
               clEnumValN(WindowSchedulingFlag::WS_Force, "force",
                          "Use window algorithm instead of SMS algorithm.")));

} // end namespace llvm

unsigned SwingSchedulerDAG::Circuits::MaxPaths = …;
char MachinePipeliner::ID = …;
#ifndef NDEBUG
int MachinePipeliner::NumTries = 0;
#endif
char &llvm::MachinePipelinerID = …;

INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE,
                      "Modulo Software Pipelining", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE,
                    "Modulo Software Pipelining", false, false)

/// The "main" function for implementing Swing Modulo Scheduling.
bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) { … }

/// Attempt to perform the SMS algorithm on the specified loop. This function is
/// the main entry point for the algorithm.  The function identifies candidate
/// loops, calculates the minimum initiation interval, and attempts to schedule
/// the loop.
bool MachinePipeliner::scheduleLoop(MachineLoop &L) { … }

void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) { … }

/// Return true if the loop can be software pipelined.  The algorithm is
/// restricted to loops with a single basic block.  Make sure that the
/// branch in the loop can be analyzed.
bool MachinePipeliner::canPipelineLoop(MachineLoop &L) { … }

void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) { … }

/// The SMS algorithm consists of the following main steps:
/// 1. Computation and analysis of the dependence graph.
/// 2. Ordering of the nodes (instructions).
/// 3. Attempt to Schedule the loop.
bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) { … }

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

bool MachinePipeliner::runWindowScheduler(MachineLoop &L) { … }

bool MachinePipeliner::useSwingModuloScheduler() { … }

bool MachinePipeliner::useWindowScheduler(bool Changed) { … }

void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) { … }

void SwingSchedulerDAG::setMAX_II() { … }

/// We override the schedule function in ScheduleDAGInstrs to implement the
/// scheduling part of the Swing Modulo Scheduling algorithm.
void SwingSchedulerDAG::schedule() { … }

/// Clean up after the software pipeliner runs.
void SwingSchedulerDAG::finishBlock() { … }

/// Return the register values for  the operands of a Phi instruction.
/// This function assume the instruction is a Phi.
static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
                       unsigned &InitVal, unsigned &LoopVal) { … }

/// Return the Phi register value that comes the loop block.
static unsigned getLoopPhiReg(const MachineInstr &Phi,
                              const MachineBasicBlock *LoopBB) { … }

/// Return true if SUb can be reached from SUa following the chain edges.
static bool isSuccOrder(SUnit *SUa, SUnit *SUb) { … }

/// Return true if the instruction causes a chain between memory
/// references before and after it.
static bool isDependenceBarrier(MachineInstr &MI) { … }

/// Return the underlying objects for the memory references of an instruction.
/// This function calls the code in ValueTracking, but first checks that the
/// instruction has a memory operand.
static void getUnderlyingObjects(const MachineInstr *MI,
                                 SmallVectorImpl<const Value *> &Objs) { … }

/// Add a chain edge between a load and store if the store can be an
/// alias of the load on a subsequent iteration, i.e., a loop carried
/// dependence. This code is very similar to the code in ScheduleDAGInstrs
/// but that code doesn't create loop carried dependences.
void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) { … }

/// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer
/// processes dependences for PHIs. This function adds true dependences
/// from a PHI to a use, and a loop carried dependence from the use to the
/// PHI. The loop carried dependence is represented as an anti dependence
/// edge. This function also removes chain dependences between unrelated
/// PHIs.
void SwingSchedulerDAG::updatePhiDependences() { … }

/// Iterate over each DAG node and see if we can change any dependences
/// in order to reduce the recurrence MII.
void SwingSchedulerDAG::changeDependences() { … }

/// Create an instruction stream that represents a single iteration and stage of
/// each instruction. This function differs from SMSchedule::finalizeSchedule in
/// that this doesn't have any side-effect to SwingSchedulerDAG. That is, this
/// function is an approximation of SMSchedule::finalizeSchedule with all
/// non-const operations removed.
static void computeScheduledInsts(const SwingSchedulerDAG *SSD,
                                  SMSchedule &Schedule,
                                  std::vector<MachineInstr *> &OrderedInsts,
                                  DenseMap<MachineInstr *, unsigned> &Stages) { … }

namespace {

// FuncUnitSorter - Comparison operator used to sort instructions by
// the number of functional unit choices.
struct FuncUnitSorter { … };

/// Calculate the maximum register pressure of the scheduled instructions stream
class HighRegisterPressureDetector { … };

} // end anonymous namespace

/// Calculate the resource constrained minimum initiation interval for the
/// specified loop. We use the DFA to model the resources needed for
/// each instruction, and we ignore dependences. A different DFA is created
/// for each cycle that is required. When adding a new instruction, we attempt
/// to add it to each existing DFA, until a legal space is found. If the
/// instruction cannot be reserved in an existing DFA, we create a new one.
unsigned SwingSchedulerDAG::calculateResMII() { … }

/// Calculate the recurrence-constrainted minimum initiation interval.
/// Iterate over each circuit.  Compute the delay(c) and distance(c)
/// for each circuit. The II needs to satisfy the inequality
/// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest
/// II that satisfies the inequality, and the RecMII is the maximum
/// of those values.
unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) { … }

/// Swap all the anti dependences in the DAG. That means it is no longer a DAG,
/// but we do this to find the circuits, and then change them back.
static void swapAntiDependences(std::vector<SUnit> &SUnits) { … }

/// Create the adjacency structure of the nodes in the graph.
void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
    SwingSchedulerDAG *DAG) { … }

/// Identify an elementary circuit in the dependence graph starting at the
/// specified node.
bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
                                          const SwingSchedulerDAG *DAG,
                                          bool HasBackedge) { … }

/// Unblock a node in the circuit finding algorithm.
void SwingSchedulerDAG::Circuits::unblock(int U) { … }

/// Identify all the elementary circuits in the dependence graph using
/// Johnson's circuit algorithm.
void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) { … }

// Create artificial dependencies between the source of COPY/REG_SEQUENCE that
// is loop-carried to the USE in next iteration. This will help pipeliner avoid
// additional copies that are needed across iterations. An artificial dependence
// edge is added from USE to SOURCE of COPY/REG_SEQUENCE.

// PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried)
// SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE
// PHI-------True-Dep------> USEOfPhi

// The mutation creates
// USEOfPHI -------Artificial-Dep---> SRCOfCopy

// This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy
// (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled
// late  to avoid additional copies across iterations. The possible scheduling
// order would be
// USEOfPHI --- SRCOfCopy---  COPY/REG_SEQUENCE.

void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) { … }

/// Return true for DAG nodes that we ignore when computing the cost functions.
/// We ignore the back-edge recurrence in order to avoid unbounded recursion
/// in the calculation of the ASAP, ALAP, etc functions.
static bool ignoreDependence(const SDep &D, bool isPred) { … }

/// Compute several functions need to order the nodes for scheduling.
///  ASAP - Earliest time to schedule a node.
///  ALAP - Latest time to schedule a node.
///  MOV - Mobility function, difference between ALAP and ASAP.
///  D - Depth of each node.
///  H - Height of each node.
void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) { … }

/// Compute the Pred_L(O) set, as defined in the paper. The set is defined
/// as the predecessors of the elements of NodeOrder that are not also in
/// NodeOrder.
static bool pred_L(SetVector<SUnit *> &NodeOrder,
                   SmallSetVector<SUnit *, 8> &Preds,
                   const NodeSet *S = nullptr) { … }

/// Compute the Succ_L(O) set, as defined in the paper. The set is defined
/// as the successors of the elements of NodeOrder that are not also in
/// NodeOrder.
static bool succ_L(SetVector<SUnit *> &NodeOrder,
                   SmallSetVector<SUnit *, 8> &Succs,
                   const NodeSet *S = nullptr) { … }

/// Return true if there is a path from the specified node to any of the nodes
/// in DestNodes. Keep track and return the nodes in any path.
static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
                        SetVector<SUnit *> &DestNodes,
                        SetVector<SUnit *> &Exclude,
                        SmallPtrSet<SUnit *, 8> &Visited) { … }

/// Compute the live-out registers for the instructions in a node-set.
/// The live-out registers are those that are defined in the node-set,
/// but not used. Except for use operands of Phis.
static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker,
                            NodeSet &NS) { … }

/// A heuristic to filter nodes in recurrent node-sets if the register
/// pressure of a set is too high.
void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) { … }

/// A heuristic to colocate node sets that have the same set of
/// successors.
void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) { … }

/// Check if the existing node-sets are profitable. If not, then ignore the
/// recurrent node-sets, and attempt to schedule all nodes together. This is
/// a heuristic. If the MII is large and all the recurrent node-sets are small,
/// then it's best to try to schedule all instructions together instead of
/// starting with the recurrent node-sets.
void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) { … }

/// Add the nodes that do not belong to a recurrence set into groups
/// based upon connected components.
void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) { … }

/// Add the node to the set, and add all of its connected nodes to the set.
void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
                                          SetVector<SUnit *> &NodesAdded) { … }

/// Return true if Set1 contains elements in Set2. The elements in common
/// are returned in a different container.
static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2,
                        SmallSetVector<SUnit *, 8> &Result) { … }

/// Merge the recurrence node sets that have the same initial node.
void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) { … }

/// Remove nodes that have been scheduled in previous NodeSets.
void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) { … }

/// Compute an ordered list of the dependence graph nodes, which
/// indicates the order that the nodes will be scheduled.  This is a
/// two-level algorithm. First, a partial order is created, which
/// consists of a list of sets ordered from highest to lowest priority.
void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) { … }

/// Process the nodes in the computed order and create the pipelined schedule
/// of the instructions, if possible. Return true if a schedule is found.
bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) { … }

/// Return true if we can compute the amount the instruction changes
/// during each iteration. Set Delta to the amount of the change.
bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) const { … }

/// Check if we can change the instruction to use an offset value from the
/// previous iteration. If so, return true and set the base and offset values
/// so that we can rewrite the load, if necessary.
///   v1 = Phi(v0, v3)
///   v2 = load v1, 0
///   v3 = post_store v1, 4, x
/// This function enables the load to be rewritten as v2 = load v3, 4.
bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI,
                                              unsigned &BasePos,
                                              unsigned &OffsetPos,
                                              unsigned &NewBase,
                                              int64_t &Offset) { … }

/// Apply changes to the instruction if needed. The changes are need
/// to improve the scheduling and depend up on the final schedule.
void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI,
                                         SMSchedule &Schedule) { … }

/// Return the instruction in the loop that defines the register.
/// If the definition is a Phi, then follow the Phi operand to
/// the instruction in the loop.
MachineInstr *SwingSchedulerDAG::findDefInLoop(Register Reg) { … }

/// Return true for an order or output dependence that is loop carried
/// potentially. A dependence is loop carried if the destination defines a value
/// that may be used or defined by the source in a subsequent iteration.
bool SwingSchedulerDAG::isLoopCarriedDep(SUnit *Source, const SDep &Dep,
                                         bool isSucc) const { … }

void SwingSchedulerDAG::postProcessDAG() { … }

/// Try to schedule the node at the specified StartCycle and continue
/// until the node is schedule or the EndCycle is reached.  This function
/// returns true if the node is scheduled.  This routine may search either
/// forward or backward for a place to insert the instruction based upon
/// the relative values of StartCycle and EndCycle.
bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) { … }

// Return the cycle of the earliest scheduled instruction in the chain.
int SMSchedule::earliestCycleInChain(const SDep &Dep) { … }

// Return the cycle of the latest scheduled instruction in the chain.
int SMSchedule::latestCycleInChain(const SDep &Dep) { … }

/// If an instruction has a use that spans multiple iterations, then
/// return true. These instructions are characterized by having a back-ege
/// to a Phi, which contains a reference to another Phi.
static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) { … }

/// Compute the scheduling start slot for the instruction.  The start slot
/// depends on any predecessor or successor nodes scheduled already.
void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
                              int II, SwingSchedulerDAG *DAG) { … }

/// Order the instructions within a cycle so that the definitions occur
/// before the uses. Returns true if the instruction is added to the start
/// of the list, or false if added to the end.
void SMSchedule::orderDependence(const SwingSchedulerDAG *SSD, SUnit *SU,
                                 std::deque<SUnit *> &Insts) const { … }

/// Return true if the scheduled Phi has a loop carried operand.
bool SMSchedule::isLoopCarried(const SwingSchedulerDAG *SSD,
                               MachineInstr &Phi) const { … }

/// Return true if the instruction is a definition that is loop carried
/// and defines the use on the next iteration.
///        v1 = phi(v2, v3)
///  (Def) v3 = op v1
///  (MO)   = v1
/// If MO appears before Def, then v1 and v3 may get assigned to the same
/// register.
bool SMSchedule::isLoopCarriedDefOfUse(const SwingSchedulerDAG *SSD,
                                       MachineInstr *Def,
                                       MachineOperand &MO) const { … }

/// Return true if all scheduled predecessors are loop-carried output/order
/// dependencies.
bool SMSchedule::onlyHasLoopCarriedOutputOrOrderPreds(
    SUnit *SU, SwingSchedulerDAG *DAG) const { … }

/// Determine transitive dependences of unpipelineable instructions
SmallSet<SUnit *, 8> SMSchedule::computeUnpipelineableNodes(
    SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) { … }

// Determine all instructions upon which any unpipelineable instruction depends
// and ensure that they are in stage 0.  If unable to do so, return false.
bool SMSchedule::normalizeNonPipelinedInstructions(
    SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) { … }

// Check if the generated schedule is valid. This function checks if
// an instruction that uses a physical register is scheduled in a
// different stage than the definition. The pipeliner does not handle
// physical register values that may cross a basic block boundary.
// Furthermore, if a physical def/use pair is assigned to the same
// cycle, orderDependence does not guarantee def/use ordering, so that
// case should be considered invalid.  (The test checks for both
// earlier and same-cycle use to be more robust.)
bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) { … }

/// A property of the node order in swing-modulo-scheduling is
/// that for nodes outside circuits the following holds:
/// none of them is scheduled after both a successor and a
/// predecessor.
/// The method below checks whether the property is met.
/// If not, debug information is printed and statistics information updated.
/// Note that we do not use an assert statement.
/// The reason is that although an invalid node oder may prevent
/// the pipeliner from finding a pipelined schedule for arbitrary II,
/// it does not lead to the generation of incorrect code.
void SwingSchedulerDAG::checkValidNodeOrder(const NodeSetType &Circuits) const { … }

/// Attempt to fix the degenerate cases when the instruction serialization
/// causes the register lifetimes to overlap. For example,
///   p' = store_pi(p, b)
///      = load p, offset
/// In this case p and p' overlap, which means that two registers are needed.
/// Instead, this function changes the load to use p' and updates the offset.
void SwingSchedulerDAG::fixupRegisterOverlaps(std::deque<SUnit *> &Instrs) { … }

std::deque<SUnit *>
SMSchedule::reorderInstructions(const SwingSchedulerDAG *SSD,
                                const std::deque<SUnit *> &Instrs) const { … }

/// After the schedule has been formed, call this function to combine
/// the instructions from the different stages/cycles.  That is, this
/// function creates a schedule that represents a single iteration.
void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) { … }

void NodeSet::print(raw_ostream &os) const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// Print the schedule information to the given output.
void SMSchedule::print(raw_ostream &os) const {
  // Iterate over each cycle.
  for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
    // Iterate over each instruction in the cycle.
    const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
    for (SUnit *CI : cycleInstrs->second) {
      os << "cycle " << cycle << " (" << stageScheduled(CI) << ") ";
      os << "(" << CI->NodeNum << ") ";
      CI->getInstr()->print(os);
      os << "\n";
    }
  }
}

/// Utility function used for debugging to print the schedule.
LLVM_DUMP_METHOD void SMSchedule::dump() const { print(dbgs()); }
LLVM_DUMP_METHOD void NodeSet::dump() const { print(dbgs()); }

void ResourceManager::dumpMRT() const {
  LLVM_DEBUG({
    if (UseDFA)
      return;
    std::stringstream SS;
    SS << "MRT:\n";
    SS << std::setw(4) << "Slot";
    for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I)
      SS << std::setw(3) << I;
    SS << std::setw(7) << "#Mops"
       << "\n";
    for (int Slot = 0; Slot < InitiationInterval; ++Slot) {
      SS << std::setw(4) << Slot;
      for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I)
        SS << std::setw(3) << MRT[Slot][I];
      SS << std::setw(7) << NumScheduledMops[Slot] << "\n";
    }
    dbgs() << SS.str();
  });
}
#endif

void ResourceManager::initProcResourceVectors(
    const MCSchedModel &SM, SmallVectorImpl<uint64_t> &Masks) { … }

bool ResourceManager::canReserveResources(SUnit &SU, int Cycle) { … }

void ResourceManager::reserveResources(SUnit &SU, int Cycle) { … }

void ResourceManager::reserveResources(const MCSchedClassDesc *SCDesc,
                                       int Cycle) { … }

void ResourceManager::unreserveResources(const MCSchedClassDesc *SCDesc,
                                         int Cycle) { … }

bool ResourceManager::isOverbooked() const { … }

int ResourceManager::calculateResMIIDFA() const { … }

int ResourceManager::calculateResMII() const { … }

void ResourceManager::init(int II) { … }