reference, declarationdefinition
definition → references, declarations, derived classes, virtual overrides
reference to multiple definitions → definitions
unreferenced
    1
    2
    3
    4
    5
    6
    7
    8
    9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97
   98
   99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  201
  202
  203
  204
  205
  206
  207
  208
  209
  210
  211
  212
  213
  214
  215
  216
  217
  218
  219
  220
  221
  222
  223
  224
  225
  226
  227
  228
  229
  230
  231
  232
  233
  234
  235
  236
  237
  238
  239
  240
  241
  242
  243
  244
  245
  246
  247
  248
  249
  250
  251
  252
  253
  254
  255
  256
  257
  258
  259
  260
  261
  262
  263
  264
  265
  266
  267
  268
  269
  270
  271
  272
  273
  274
  275
  276
  277
  278
  279
//===--------------------- Scheduler.h ------------------------*- 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
//
//===----------------------------------------------------------------------===//
/// \file
///
/// A scheduler for Processor Resource Units and Processor Resource Groups.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_MCA_SCHEDULER_H
#define LLVM_MCA_SCHEDULER_H

#include "llvm/ADT/SmallVector.h"
#include "llvm/MC/MCSchedule.h"
#include "llvm/MCA/HardwareUnits/HardwareUnit.h"
#include "llvm/MCA/HardwareUnits/LSUnit.h"
#include "llvm/MCA/HardwareUnits/ResourceManager.h"
#include "llvm/MCA/Support.h"

namespace llvm {
namespace mca {

class SchedulerStrategy {
public:
  SchedulerStrategy() = default;
  virtual ~SchedulerStrategy();

  /// Returns true if Lhs should take priority over Rhs.
  ///
  /// This method is used by class Scheduler to select the "best" ready
  /// instruction to issue to the underlying pipelines.
  virtual bool compare(const InstRef &Lhs, const InstRef &Rhs) const = 0;
};

/// Default instruction selection strategy used by class Scheduler.
class DefaultSchedulerStrategy : public SchedulerStrategy {
  /// This method ranks instructions based on their age, and the number of known
  /// users. The lower the rank value, the better.
  int computeRank(const InstRef &Lhs) const {
    return Lhs.getSourceIndex() - Lhs.getInstruction()->getNumUsers();
  }

public:
  DefaultSchedulerStrategy() = default;
  virtual ~DefaultSchedulerStrategy();

  bool compare(const InstRef &Lhs, const InstRef &Rhs) const override {
    int LhsRank = computeRank(Lhs);
    int RhsRank = computeRank(Rhs);

    /// Prioritize older instructions over younger instructions to minimize the
    /// pressure on the reorder buffer.
    if (LhsRank == RhsRank)
      return Lhs.getSourceIndex() < Rhs.getSourceIndex();
    return LhsRank < RhsRank;
  }
};

/// Class Scheduler is responsible for issuing instructions to pipeline
/// resources.
///
/// Internally, it delegates to a ResourceManager the management of processor
/// resources. This class is also responsible for tracking the progress of
/// instructions from the dispatch stage, until the write-back stage.
///
class Scheduler : public HardwareUnit {
  LSUnitBase &LSU;

  // Instruction selection strategy for this Scheduler.
  std::unique_ptr<SchedulerStrategy> Strategy;

  // Hardware resources that are managed by this scheduler.
  std::unique_ptr<ResourceManager> Resources;

  // Instructions dispatched to the Scheduler are internally classified based on
  // the instruction stage (see Instruction::InstrStage).
  //
  // An Instruction dispatched to the Scheduler is added to the WaitSet if not
  // all its register operands are available, and at least one latency is
  // unknown.  By construction, the WaitSet only contains instructions that are
  // in the IS_DISPATCHED stage.
  //
  // An Instruction transitions from the WaitSet to the PendingSet if the
  // instruction is not ready yet, but the latency of every register read is
  // known.  Instructions in the PendingSet can only be in the IS_PENDING or
  // IS_READY stage.  Only IS_READY instructions that are waiting on memory
  // dependencies can be added to the PendingSet.
  //
  // Instructions in the PendingSet are immediately dominated only by
  // instructions that have already been issued to the underlying pipelines.  In
  // the presence of bottlenecks caused by data dependencies, the PendingSet can
  // be inspected to identify problematic data dependencies between
  // instructions.
  //
  // An instruction is moved to the ReadySet when all register operands become
  // available, and all memory dependencies are met.  Instructions that are
  // moved from the PendingSet to the ReadySet must transition to the 'IS_READY'
  // stage.
  //
  // On every cycle, the Scheduler checks if it can promote instructions from the
  // PendingSet to the ReadySet.
  //
  // An Instruction is moved from the ReadySet to the `IssuedSet` when it starts
  // exection. This event also causes an instruction state transition (i.e. from
  // state IS_READY, to state IS_EXECUTING). An Instruction leaves the IssuedSet
  // only when it reaches the write-back stage.
  std::vector<InstRef> WaitSet;
  std::vector<InstRef> PendingSet;
  std::vector<InstRef> ReadySet;
  std::vector<InstRef> IssuedSet;

  // A mask of busy resource units. It defaults to the empty set (i.e. a zero
  // mask), and it is cleared at the beginning of every cycle.
  // It is updated every time the scheduler fails to issue an instruction from
  // the ready set due to unavailable pipeline resources.
  // Each bit of the mask represents an unavailable resource.
  uint64_t BusyResourceUnits;

  // Counts the number of instructions in the pending set that were dispatched
  // during this cycle.
  unsigned NumDispatchedToThePendingSet;

  // True if the previous pipeline Stage was unable to dispatch a full group of
  // opcodes because scheduler buffers (or LS queues) were unavailable.
  bool HadTokenStall;

  /// Verify the given selection strategy and set the Strategy member
  /// accordingly.  If no strategy is provided, the DefaultSchedulerStrategy is
  /// used.
  void initializeStrategy(std::unique_ptr<SchedulerStrategy> S);

  /// Issue an instruction without updating the ready queue.
  void issueInstructionImpl(
      InstRef &IR,
      SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);

  // Identify instructions that have finished executing, and remove them from
  // the IssuedSet. References to executed instructions are added to input
  // vector 'Executed'.
  void updateIssuedSet(SmallVectorImpl<InstRef> &Executed);

  // Try to promote instructions from the PendingSet to the ReadySet.
  // Add promoted instructions to the 'Ready' vector in input.
  // Returns true if at least one instruction was promoted.
  bool promoteToReadySet(SmallVectorImpl<InstRef> &Ready);

  // Try to promote instructions from the WaitSet to the PendingSet.
  // Add promoted instructions to the 'Pending' vector in input.
  // Returns true if at least one instruction was promoted.
  bool promoteToPendingSet(SmallVectorImpl<InstRef> &Pending);

public:
  Scheduler(const MCSchedModel &Model, LSUnitBase &Lsu)
      : Scheduler(Model, Lsu, nullptr) {}

  Scheduler(const MCSchedModel &Model, LSUnitBase &Lsu,
            std::unique_ptr<SchedulerStrategy> SelectStrategy)
      : Scheduler(std::make_unique<ResourceManager>(Model), Lsu,
                  std::move(SelectStrategy)) {}

  Scheduler(std::unique_ptr<ResourceManager> RM, LSUnitBase &Lsu,
            std::unique_ptr<SchedulerStrategy> SelectStrategy)
      : LSU(Lsu), Resources(std::move(RM)), BusyResourceUnits(0),
        NumDispatchedToThePendingSet(0), HadTokenStall(false) {
    initializeStrategy(std::move(SelectStrategy));
  }

  // Stalls generated by the scheduler.
  enum Status {
    SC_AVAILABLE,
    SC_LOAD_QUEUE_FULL,
    SC_STORE_QUEUE_FULL,
    SC_BUFFERS_FULL,
    SC_DISPATCH_GROUP_STALL,
  };

  /// Check if the instruction in 'IR' can be dispatched during this cycle.
  /// Return SC_AVAILABLE if both scheduler and LS resources are available.
  ///
  /// This method is also responsible for setting field HadTokenStall if
  /// IR cannot be dispatched to the Scheduler due to unavailable resources.
  Status isAvailable(const InstRef &IR);

  /// Reserves buffer and LSUnit queue resources that are necessary to issue
  /// this instruction.
  ///
  /// Returns true if instruction IR is ready to be issued to the underlying
  /// pipelines. Note that this operation cannot fail; it assumes that a
  /// previous call to method `isAvailable(IR)` returned `SC_AVAILABLE`.
  ///
  /// If IR is a memory operation, then the Scheduler queries the LS unit to
  /// obtain a LS token. An LS token is used internally to track memory
  /// dependencies.
  bool dispatch(InstRef &IR);

  /// Issue an instruction and populates a vector of used pipeline resources,
  /// and a vector of instructions that transitioned to the ready state as a
  /// result of this event.
  void issueInstruction(
      InstRef &IR,
      SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Used,
      SmallVectorImpl<InstRef> &Pending,
      SmallVectorImpl<InstRef> &Ready);

  /// Returns true if IR has to be issued immediately, or if IR is a zero
  /// latency instruction.
  bool mustIssueImmediately(const InstRef &IR) const;

  /// This routine notifies the Scheduler that a new cycle just started.
  ///
  /// It notifies the underlying ResourceManager that a new cycle just started.
  /// Vector `Freed` is populated with resourceRef related to resources that
  /// have changed in state, and that are now available to new instructions.
  /// Instructions executed are added to vector Executed, while vector Ready is
  /// populated with instructions that have become ready in this new cycle.
  /// Vector Pending is popluated by instructions that have transitioned through
  /// the pending stat during this cycle. The Pending and Ready sets may not be
  /// disjoint. An instruction is allowed to transition from the WAIT state to
  /// the READY state (going through the PENDING state) within a single cycle.
  /// That means, instructions may appear in both the Pending and Ready set.
  void cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
                  SmallVectorImpl<InstRef> &Executed,
                  SmallVectorImpl<InstRef> &Pending,
                  SmallVectorImpl<InstRef> &Ready);

  /// Convert a resource mask into a valid llvm processor resource identifier.
  ///
  /// Only the most significant bit of the Mask is used by this method to
  /// identify the processor resource.
  unsigned getResourceID(uint64_t Mask) const {
    return Resources->resolveResourceMask(Mask);
  }

  /// Select the next instruction to issue from the ReadySet. Returns an invalid
  /// instruction reference if there are no ready instructions, or if processor
  /// resources are not available.
  InstRef select();

  bool isReadySetEmpty() const { return ReadySet.empty(); }
  bool isWaitSetEmpty() const { return WaitSet.empty(); }

  /// This method is called by the ExecuteStage at the end of each cycle to
  /// identify bottlenecks caused by data dependencies. Vector RegDeps is
  /// populated by instructions that were not issued because of unsolved
  /// register dependencies.  Vector MemDeps is populated by instructions that
  /// were not issued because of unsolved memory dependencies.
  void analyzeDataDependencies(SmallVectorImpl<InstRef> &RegDeps,
                               SmallVectorImpl<InstRef> &MemDeps);

  /// Returns a mask of busy resources, and populates vector Insts with
  /// instructions that could not be issued to the underlying pipelines because
  /// not all pipeline resources were available.
  uint64_t analyzeResourcePressure(SmallVectorImpl<InstRef> &Insts);

  // Returns true if the dispatch logic couldn't dispatch a full group due to
  // unavailable scheduler and/or LS resources.
  bool hadTokenStall() const { return HadTokenStall; }

#ifndef NDEBUG
  // Update the ready queues.
  void dump() const;

  // This routine performs a sanity check.  This routine should only be called
  // when we know that 'IR' is not in the scheduler's instruction queues.
  void sanityCheck(const InstRef &IR) const {
    assert(find(WaitSet, IR) == WaitSet.end() && "Already in the wait set!");
    assert(find(ReadySet, IR) == ReadySet.end() && "Already in the ready set!");
    assert(find(IssuedSet, IR) == IssuedSet.end() && "Already executing!");
  }
#endif // !NDEBUG
};
} // namespace mca
} // namespace llvm

#endif // LLVM_MCA_SCHEDULER_H