Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- VLIWMachineScheduler.h - VLIW-Focused Scheduling Pass ----*- 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

//

//===----------------------------------------------------------------------===//

//                                                                            //

//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_VLIWMACHINESCHEDULER_H

#define LLVM_CODEGEN_VLIWMACHINESCHEDULER_H

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/Twine.h"

#include "llvm/CodeGen/MachineScheduler.h"

#include "llvm/CodeGen/TargetSchedule.h"

#include <limits>

#include <memory>

#include <utility>

namespace llvm {

class DFAPacketizer;

class RegisterClassInfo;

class ScheduleHazardRecognizer;

class SUnit;

class TargetInstrInfo;

class TargetSubtargetInfo;

class VLIWResourceModel {

protected:

  const TargetInstrInfo *TII;

  /// ResourcesModel - Represents VLIW state.

  /// Not limited to VLIW targets per se, but assumes definition of resource

  /// model by a target.

  DFAPacketizer *ResourcesModel;

  const TargetSchedModel *SchedModel;

  /// Local packet/bundle model. Purely

  /// internal to the MI scheduler at the time.

  SmallVector<SUnit *> Packet;

  /// Total packets created.

  unsigned TotalPackets = 0;

public:

  VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM);

  virtual ~VLIWResourceModel();

  virtual void reset();

  virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu);

  virtual bool isResourceAvailable(SUnit *SU, bool IsTop);

  virtual bool reserveResources(SUnit *SU, bool IsTop);

  unsigned getTotalPackets() const { return TotalPackets; }

  size_t getPacketInstCount() const { return Packet.size(); }

  bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }

protected:

  virtual DFAPacketizer *createPacketizer(const TargetSubtargetInfo &STI) const;

};

/// Extend the standard ScheduleDAGMILive to provide more context and override

/// the top-level schedule() driver.

class VLIWMachineScheduler : public ScheduleDAGMILive {

public:

  VLIWMachineScheduler(MachineSchedContext *C,

                       std::unique_ptr<MachineSchedStrategy> S)

      : ScheduleDAGMILive(C, std::move(S)) {}

  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's

  /// time to do some work.

  void schedule() override;

  RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }

  int getBBSize() { return BB->size(); }

};

//===----------------------------------------------------------------------===//

// ConvergingVLIWScheduler - Implementation of a VLIW-aware

// MachineSchedStrategy.

//===----------------------------------------------------------------------===//

class ConvergingVLIWScheduler : public MachineSchedStrategy {

protected:

  /// Store the state used by ConvergingVLIWScheduler heuristics, required

  ///  for the lifetime of one invocation of pickNode().

  struct SchedCandidate {

    // The best SUnit candidate.

    SUnit *SU = nullptr;

    // Register pressure values for the best candidate.

    RegPressureDelta RPDelta;

    // Best scheduling cost.

    int SCost = 0;

    SchedCandidate() = default;

  };

  /// Represent the type of SchedCandidate found within a single queue.

  enum CandResult {

    NoCand,

    NodeOrder,

    SingleExcess,

    SingleCritical,

    SingleMax,

    MultiPressure,

    BestCost,

    Weak

  };

  // Constants used to denote relative importance of

  // heuristic components for cost computation.

  static constexpr unsigned PriorityOne = 200;

  static constexpr unsigned PriorityTwo = 50;

  static constexpr unsigned PriorityThree = 75;

  static constexpr unsigned ScaleTwo = 10;

  /// Each Scheduling boundary is associated with ready queues. It tracks the

  /// current cycle in whichever direction at has moved, and maintains the state

  /// of "hazards" and other interlocks at the current cycle.

  struct VLIWSchedBoundary {

    VLIWMachineScheduler *DAG = nullptr;

    const TargetSchedModel *SchedModel = nullptr;

    ReadyQueue Available;

    ReadyQueue Pending;

    bool CheckPending = false;

    ScheduleHazardRecognizer *HazardRec = nullptr;

    VLIWResourceModel *ResourceModel = nullptr;

    unsigned CurrCycle = 0;

    unsigned IssueCount = 0;

    unsigned CriticalPathLength = 0;

    /// MinReadyCycle - Cycle of the soonest available instruction.

    unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();

    // Remember the greatest min operand latency.

    unsigned MaxMinLatency = 0;

    /// Pending queues extend the ready queues with the same ID and the

    /// PendingFlag set.

    VLIWSchedBoundary(unsigned ID, const Twine &Name)

        : Available(ID, Name + ".A"),

          Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name + ".P") {}

    ~VLIWSchedBoundary();

    void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {

      DAG = dag;

      SchedModel = smodel;

      CurrCycle = 0;

      IssueCount = 0;

      // Initialize the critical path length limit, which used by the scheduling

      // cost model to determine the value for scheduling an instruction. We use

      // a slightly different heuristic for small and large functions. For small

      // functions, it's important to use the height/depth of the instruction.

      // For large functions, prioritizing by height or depth increases spills.

      CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();

      if (DAG->getBBSize() < 50)

        // We divide by two as a cheap and simple heuristic to reduce the

        // critcal path length, which increases the priority of using the graph

        // height/depth in the scheduler's cost computation.

        CriticalPathLength >>= 1;

      else {

        // For large basic blocks, we prefer a larger critical path length to

        // decrease the priority of using the graph height/depth.

        unsigned MaxPath = 0;

        for (auto &SU : DAG->SUnits)

          MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());

        CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;

      }

    }

    bool isTop() const {

      return Available.getID() == ConvergingVLIWScheduler::TopQID;

    }

    bool checkHazard(SUnit *SU);

    void releaseNode(SUnit *SU, unsigned ReadyCycle);

    void bumpCycle();

    void bumpNode(SUnit *SU);

    void releasePending();

    void removeReady(SUnit *SU);

    SUnit *pickOnlyChoice();

    bool isLatencyBound(SUnit *SU) {

      if (CurrCycle >= CriticalPathLength)

        return true;

      unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();

      return CriticalPathLength - CurrCycle <= PathLength;

    }

  };

  VLIWMachineScheduler *DAG = nullptr;

  const TargetSchedModel *SchedModel = nullptr;

  // State of the top and bottom scheduled instruction boundaries.

  VLIWSchedBoundary Top;

  VLIWSchedBoundary Bot;

  /// List of pressure sets that have a high pressure level in the region.

  SmallVector<bool> HighPressureSets;

public:

  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)

  enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 };

  ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}

  virtual ~ConvergingVLIWScheduler() = default;

  void initialize(ScheduleDAGMI *dag) override;

  SUnit *pickNode(bool &IsTopNode) override;

  void schedNode(SUnit *SU, bool IsTopNode) override;

  void releaseTopNode(SUnit *SU) override;

  void releaseBottomNode(SUnit *SU) override;

  unsigned reportPackets() {

    return Top.ResourceModel->getTotalPackets() +

           Bot.ResourceModel->getTotalPackets();

  }

protected:

  virtual VLIWResourceModel *

  createVLIWResourceModel(const TargetSubtargetInfo &STI,

                          const TargetSchedModel *SchedModel) const;

  SUnit *pickNodeBidrectional(bool &IsTopNode);

  int pressureChange(const SUnit *SU, bool isBotUp);

  virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU,

                             SchedCandidate &Candidate, RegPressureDelta &Delta,

                             bool verbose);

  CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,

                               const RegPressureTracker &RPTracker,

                               SchedCandidate &Candidate);

#ifndef NDEBUG

  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,

                      int Cost, PressureChange P = PressureChange());

  void readyQueueVerboseDump(const RegPressureTracker &RPTracker,

                             SchedCandidate &Candidate, ReadyQueue &Q);

#endif

};

ScheduleDAGMILive *createVLIWSched(MachineSchedContext *C);

} // end namespace llvm

#endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H