llvm/llvm/lib/CodeGen/PostRASchedulerList.cpp

//===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
//
// 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 implements a top-down list scheduler, using standard algorithms.
// The basic approach uses a priority queue of available nodes to schedule.
// One at a time, nodes are taken from the priority queue (thus in priority
// order), checked for legality to schedule, and emitted if legal.
//
// Nodes may not be legal to schedule either due to structural hazards (e.g.
// pipeline or resource constraints) or because an input to the instruction has
// not completed execution.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/AntiDepBreaker.h"
#include "llvm/CodeGen/LatencyPriorityQueue.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumNoops, "Number of noops inserted");
STATISTIC(NumStalls, "Number of pipeline stalls");
STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");

// Post-RA scheduling is enabled with
// TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to
// override the target.
static cl::opt<bool>
EnablePostRAScheduler("post-RA-scheduler",
                       cl::desc("Enable scheduling after register allocation"),
                       cl::init(false), cl::Hidden);
static cl::opt<std::string>
EnableAntiDepBreaking("break-anti-dependencies",
                      cl::desc("Break post-RA scheduling anti-dependencies: "
                               "\"critical\", \"all\", or \"none\""),
                      cl::init("none"), cl::Hidden);

// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
static cl::opt<int>
DebugDiv("postra-sched-debugdiv",
                      cl::desc("Debug control MBBs that are scheduled"),
                      cl::init(0), cl::Hidden);
static cl::opt<int>
DebugMod("postra-sched-debugmod",
                      cl::desc("Debug control MBBs that are scheduled"),
                      cl::init(0), cl::Hidden);

AntiDepBreaker::~AntiDepBreaker() = default;

namespace {
  class PostRAScheduler : public MachineFunctionPass { … };
  char PostRAScheduler::ID = …;

  class SchedulePostRATDList : public ScheduleDAGInstrs { … };
}

char &llvm::PostRASchedulerID = …;

INITIALIZE_PASS(…)

SchedulePostRATDList::SchedulePostRATDList(
    MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
    const RegisterClassInfo &RCI,
    TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
    SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
    : … { … }

SchedulePostRATDList::~SchedulePostRATDList() { … }

/// Initialize state associated with the next scheduling region.
void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
                 MachineBasicBlock::iterator begin,
                 MachineBasicBlock::iterator end,
                 unsigned regioninstrs) { … }

/// Print the schedule before exiting the region.
void SchedulePostRATDList::exitRegion() { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// dumpSchedule - dump the scheduled Sequence.
LLVM_DUMP_METHOD void SchedulePostRATDList::dumpSchedule() const {
  for (const SUnit *SU : Sequence) {
    if (SU)
      dumpNode(*SU);
    else
      dbgs() << "**** NOOP ****\n";
  }
}
#endif

bool PostRAScheduler::enablePostRAScheduler(
    const TargetSubtargetInfo &ST, CodeGenOptLevel OptLevel,
    TargetSubtargetInfo::AntiDepBreakMode &Mode,
    TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const { … }

bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { … }

/// StartBlock - Initialize register live-range state for scheduling in
/// this block.
///
void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { … }

/// Schedule - Schedule the instruction range using list scheduling.
///
void SchedulePostRATDList::schedule() { … }

/// Observe - Update liveness information to account for the current
/// instruction, which will not be scheduled.
///
void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) { … }

/// FinishBlock - Clean up register live-range state.
///
void SchedulePostRATDList::finishBlock() { … }

/// Apply each ScheduleDAGMutation step in order.
void SchedulePostRATDList::postProcessDAG() { … }

//===----------------------------------------------------------------------===//
//  Top-Down Scheduling
//===----------------------------------------------------------------------===//

/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the PendingQueue if the count reaches zero.
void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { … }

/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { … }

/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { … }

/// emitNoop - Add a noop to the current instruction sequence.
void SchedulePostRATDList::emitNoop(unsigned CurCycle) { … }

/// ListScheduleTopDown - The main loop of list scheduling for top-down
/// schedulers.
void SchedulePostRATDList::ListScheduleTopDown() { … }

// EmitSchedule - Emit the machine code in scheduled order.
void SchedulePostRATDList::EmitSchedule() { … }