Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===------------------------- LSUnit.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 Load/Store unit class that models load/store queues and that implements

/// a simple weak memory consistency model.

///

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

#ifndef LLVM_MCA_HARDWAREUNITS_LSUNIT_H

#define LLVM_MCA_HARDWAREUNITS_LSUNIT_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/MC/MCSchedule.h"

#include "llvm/MCA/HardwareUnits/HardwareUnit.h"

#include "llvm/MCA/Instruction.h"

namespace llvm {

namespace mca {

/// A node of a memory dependency graph. A MemoryGroup describes a set of

/// instructions with same memory dependencies.

///

/// By construction, instructions of a MemoryGroup don't depend on each other.

/// At dispatch stage, instructions are mapped by the LSUnit to MemoryGroups.

/// A Memory group identifier is then stored as a "token" in field

/// Instruction::LSUTokenID of each dispatched instructions. That token is used

/// internally by the LSUnit to track memory dependencies.

class MemoryGroup {

  unsigned NumPredecessors;

  unsigned NumExecutingPredecessors;

  unsigned NumExecutedPredecessors;

  unsigned NumInstructions;

  unsigned NumExecuting;

  unsigned NumExecuted;

  // Successors that are in a order dependency with this group.

  SmallVector<MemoryGroup *, 4> OrderSucc;

  // Successors that are in a data dependency with this group.

  SmallVector<MemoryGroup *, 4> DataSucc;

  CriticalDependency CriticalPredecessor;

  InstRef CriticalMemoryInstruction;

  MemoryGroup(const MemoryGroup &) = delete;

  MemoryGroup &operator=(const MemoryGroup &) = delete;

public:

  MemoryGroup()

      : NumPredecessors(0), NumExecutingPredecessors(0),

        NumExecutedPredecessors(0), NumInstructions(0), NumExecuting(0),

        NumExecuted(0), CriticalPredecessor() {}

  MemoryGroup(MemoryGroup &&) = default;

  size_t getNumSuccessors() const {

    return OrderSucc.size() + DataSucc.size();

  }

  unsigned getNumPredecessors() const { return NumPredecessors; }

  unsigned getNumExecutingPredecessors() const {

    return NumExecutingPredecessors;

  }

  unsigned getNumExecutedPredecessors() const {

    return NumExecutedPredecessors;

  }

  unsigned getNumInstructions() const { return NumInstructions; }

  unsigned getNumExecuting() const { return NumExecuting; }

  unsigned getNumExecuted() const { return NumExecuted; }

  const InstRef &getCriticalMemoryInstruction() const {

    return CriticalMemoryInstruction;

  }

  const CriticalDependency &getCriticalPredecessor() const {

    return CriticalPredecessor;

  }

  void addSuccessor(MemoryGroup *Group, bool IsDataDependent) {

    // Do not need to add a dependency if there is no data

    // dependency and all instructions from this group have been

    // issued already.

    if (!IsDataDependent && isExecuting())

      return;

    Group->NumPredecessors++;

    assert(!isExecuted() && "Should have been removed!");

    if (isExecuting())

      Group->onGroupIssued(CriticalMemoryInstruction, IsDataDependent);

    if (IsDataDependent)

      DataSucc.emplace_back(Group);

    else

      OrderSucc.emplace_back(Group);

  }

  bool isWaiting() const {

    return NumPredecessors >

           (NumExecutingPredecessors + NumExecutedPredecessors);

  }

  bool isPending() const {

    return NumExecutingPredecessors &&

           ((NumExecutedPredecessors + NumExecutingPredecessors) ==

            NumPredecessors);

  }

  bool isReady() const { return NumExecutedPredecessors == NumPredecessors; }

  bool isExecuting() const {

    return NumExecuting && (NumExecuting == (NumInstructions - NumExecuted));

  }

  bool isExecuted() const { return NumInstructions == NumExecuted; }

  void onGroupIssued(const InstRef &IR, bool ShouldUpdateCriticalDep) {

    assert(!isReady() && "Unexpected group-start event!");

    NumExecutingPredecessors++;

    if (!ShouldUpdateCriticalDep)

      return;

    unsigned Cycles = IR.getInstruction()->getCyclesLeft();

    if (CriticalPredecessor.Cycles < Cycles) {

      CriticalPredecessor.IID = IR.getSourceIndex();

      CriticalPredecessor.Cycles = Cycles;

    }

  }

  void onGroupExecuted() {

    assert(!isReady() && "Inconsistent state found!");

    NumExecutingPredecessors--;

    NumExecutedPredecessors++;

  }

  void onInstructionIssued(const InstRef &IR) {

    assert(!isExecuting() && "Invalid internal state!");

    ++NumExecuting;

    // update the CriticalMemDep.

    const Instruction &IS = *IR.getInstruction();

    if ((bool)CriticalMemoryInstruction) {

      const Instruction &OtherIS = *CriticalMemoryInstruction.getInstruction();

      if (OtherIS.getCyclesLeft() < IS.getCyclesLeft())

        CriticalMemoryInstruction = IR;

    } else {

      CriticalMemoryInstruction = IR;

    }

    if (!isExecuting())

      return;

    // Notify successors that this group started execution.

    for (MemoryGroup *MG : OrderSucc) {

      MG->onGroupIssued(CriticalMemoryInstruction, false);

      // Release the order dependency with this group.

      MG->onGroupExecuted();

    }

    for (MemoryGroup *MG : DataSucc)

      MG->onGroupIssued(CriticalMemoryInstruction, true);

  }

  void onInstructionExecuted(const InstRef &IR) {

    assert(isReady() && !isExecuted() && "Invalid internal state!");

    --NumExecuting;

    ++NumExecuted;

    if (CriticalMemoryInstruction &&

        CriticalMemoryInstruction.getSourceIndex() == IR.getSourceIndex()) {

      CriticalMemoryInstruction.invalidate();

    }

    if (!isExecuted())

      return;

    // Notify data dependent successors that this group has finished execution.

    for (MemoryGroup *MG : DataSucc)

      MG->onGroupExecuted();

  }

  void addInstruction() {

    assert(!getNumSuccessors() && "Cannot add instructions to this group!");

    ++NumInstructions;

  }

  void cycleEvent() {

    if (isWaiting() && CriticalPredecessor.Cycles)

      CriticalPredecessor.Cycles--;

  }

};

/// Abstract base interface for LS (load/store) units in llvm-mca.

class LSUnitBase : public HardwareUnit {

  /// Load queue size.

  ///

  /// A value of zero for this field means that the load queue is unbounded.

  /// Processor models can declare the size of a load queue via tablegen (see

  /// the definition of tablegen class LoadQueue in

  /// llvm/Target/TargetSchedule.td).

  unsigned LQSize;

  /// Load queue size.

  ///

  /// A value of zero for this field means that the store queue is unbounded.

  /// Processor models can declare the size of a store queue via tablegen (see

  /// the definition of tablegen class StoreQueue in

  /// llvm/Target/TargetSchedule.td).

  unsigned SQSize;

  unsigned UsedLQEntries;

  unsigned UsedSQEntries;

  /// True if loads don't alias with stores.

  ///

  /// By default, the LS unit assumes that loads and stores don't alias with

  /// eachother. If this field is set to false, then loads are always assumed to

  /// alias with stores.

  const bool NoAlias;

  /// Used to map group identifiers to MemoryGroups.

  DenseMap<unsigned, std::unique_ptr<MemoryGroup>> Groups;

  unsigned NextGroupID;

public:

  LSUnitBase(const MCSchedModel &SM, unsigned LoadQueueSize,

             unsigned StoreQueueSize, bool AssumeNoAlias);

  virtual ~LSUnitBase();

  /// Returns the total number of entries in the load queue.

  unsigned getLoadQueueSize() const { return LQSize; }

  /// Returns the total number of entries in the store queue.

  unsigned getStoreQueueSize() const { return SQSize; }

  unsigned getUsedLQEntries() const { return UsedLQEntries; }

  unsigned getUsedSQEntries() const { return UsedSQEntries; }

  void acquireLQSlot() { ++UsedLQEntries; }

  void acquireSQSlot() { ++UsedSQEntries; }

  void releaseLQSlot() { --UsedLQEntries; }

  void releaseSQSlot() { --UsedSQEntries; }

  bool assumeNoAlias() const { return NoAlias; }

  enum Status {

    LSU_AVAILABLE = 0,

    LSU_LQUEUE_FULL, // Load Queue unavailable

    LSU_SQUEUE_FULL  // Store Queue unavailable

  };

  /// This method checks the availability of the load/store buffers.

  ///

  /// Returns LSU_AVAILABLE if there are enough load/store queue entries to

  /// accomodate instruction IR. By default, LSU_AVAILABLE is returned if IR is

  /// not a memory operation.

  virtual Status isAvailable(const InstRef &IR) const = 0;

  /// Allocates LS resources for instruction IR.

  ///

  /// This method assumes that a previous call to `isAvailable(IR)` succeeded

  /// with a LSUnitBase::Status value of LSU_AVAILABLE.

  /// Returns the GroupID associated with this instruction. That value will be

  /// used to set the LSUTokenID field in class Instruction.

  virtual unsigned dispatch(const InstRef &IR) = 0;

  bool isSQEmpty() const { return !UsedSQEntries; }

  bool isLQEmpty() const { return !UsedLQEntries; }

  bool isSQFull() const { return SQSize && SQSize == UsedSQEntries; }

  bool isLQFull() const { return LQSize && LQSize == UsedLQEntries; }

  bool isValidGroupID(unsigned Index) const {

    return Index && (Groups.find(Index) != Groups.end());

  }

  /// Check if a peviously dispatched instruction IR is now ready for execution.

  bool isReady(const InstRef &IR) const {

    unsigned GroupID = IR.getInstruction()->getLSUTokenID();

    const MemoryGroup &Group = getGroup(GroupID);

    return Group.isReady();

  }

  /// Check if instruction IR only depends on memory instructions that are

  /// currently executing.

  bool isPending(const InstRef &IR) const {

    unsigned GroupID = IR.getInstruction()->getLSUTokenID();

    const MemoryGroup &Group = getGroup(GroupID);

    return Group.isPending();

  }

  /// Check if instruction IR is still waiting on memory operations, and the

  /// wait time is still unknown.

  bool isWaiting(const InstRef &IR) const {

    unsigned GroupID = IR.getInstruction()->getLSUTokenID();

    const MemoryGroup &Group = getGroup(GroupID);

    return Group.isWaiting();

  }

  bool hasDependentUsers(const InstRef &IR) const {

    unsigned GroupID = IR.getInstruction()->getLSUTokenID();

    const MemoryGroup &Group = getGroup(GroupID);

    return !Group.isExecuted() && Group.getNumSuccessors();

  }

  const MemoryGroup &getGroup(unsigned Index) const {

    assert(isValidGroupID(Index) && "Group doesn't exist!");

    return *Groups.find(Index)->second;

  }

  MemoryGroup &getGroup(unsigned Index) {

    assert(isValidGroupID(Index) && "Group doesn't exist!");

    return *Groups.find(Index)->second;

  }

  unsigned createMemoryGroup() {

    Groups.insert(

        std::make_pair(NextGroupID, std::make_unique<MemoryGroup>()));

    return NextGroupID++;

  }

  virtual void onInstructionExecuted(const InstRef &IR);

  // Loads are tracked by the LDQ (load queue) from dispatch until completion.

  // Stores are tracked by the STQ (store queue) from dispatch until commitment.

  // By default we conservatively assume that the LDQ receives a load at

  // dispatch. Loads leave the LDQ at retirement stage.

  virtual void onInstructionRetired(const InstRef &IR);

  virtual void onInstructionIssued(const InstRef &IR) {

    unsigned GroupID = IR.getInstruction()->getLSUTokenID();

    Groups[GroupID]->onInstructionIssued(IR);

  }

  virtual void cycleEvent();

#ifndef NDEBUG

  void dump() const;

#endif

};

/// Default Load/Store Unit (LS Unit) for simulated processors.

///

/// Each load (or store) consumes one entry in the load (or store) queue.

///

/// Rules are:

/// 1) A younger load is allowed to pass an older load only if there are no

///    stores nor barriers in between the two loads.

/// 2) An younger store is not allowed to pass an older store.

/// 3) A younger store is not allowed to pass an older load.

/// 4) A younger load is allowed to pass an older store only if the load does

///    not alias with the store.

///

/// This class optimistically assumes that loads don't alias store operations.

/// Under this assumption, younger loads are always allowed to pass older

/// stores (this would only affects rule 4).

/// Essentially, this class doesn't perform any sort alias analysis to

/// identify aliasing loads and stores.

///

/// To enforce aliasing between loads and stores, flag `AssumeNoAlias` must be

/// set to `false` by the constructor of LSUnit.

///

/// Note that this class doesn't know about the existence of different memory

/// types for memory operations (example: write-through, write-combining, etc.).

/// Derived classes are responsible for implementing that extra knowledge, and

/// provide different sets of rules for loads and stores by overriding method

/// `isReady()`.

/// To emulate a write-combining memory type, rule 2. must be relaxed in a

/// derived class to enable the reordering of non-aliasing store operations.

///

/// No assumptions are made by this class on the size of the store buffer.  This

/// class doesn't know how to identify cases where store-to-load forwarding may

/// occur.

///

/// LSUnit doesn't attempt to predict whether a load or store hits or misses

/// the L1 cache. To be more specific, LSUnit doesn't know anything about

/// cache hierarchy and memory types.

/// It only knows if an instruction "mayLoad" and/or "mayStore". For loads, the

/// scheduling model provides an "optimistic" load-to-use latency (which usually

/// matches the load-to-use latency for when there is a hit in the L1D).

/// Derived classes may expand this knowledge.

///

/// Class MCInstrDesc in LLVM doesn't know about serializing operations, nor

/// memory-barrier like instructions.

/// LSUnit conservatively assumes that an instruction which `mayLoad` and has

/// `unmodeled side effects` behave like a "soft" load-barrier. That means, it

/// serializes loads without forcing a flush of the load queue.

/// Similarly, instructions that both `mayStore` and have `unmodeled side

/// effects` are treated like store barriers. A full memory

/// barrier is a 'mayLoad' and 'mayStore' instruction with unmodeled side

/// effects. This is obviously inaccurate, but this is the best that we can do

/// at the moment.

///

/// Each load/store barrier consumes one entry in the load/store queue. A

/// load/store barrier enforces ordering of loads/stores:

///  - A younger load cannot pass a load barrier.

///  - A younger store cannot pass a store barrier.

///

/// A younger load has to wait for the memory load barrier to execute.

/// A load/store barrier is "executed" when it becomes the oldest entry in

/// the load/store queue(s). That also means, all the older loads/stores have

/// already been executed.

class LSUnit : public LSUnitBase {

  // This class doesn't know about the latency of a load instruction. So, it

  // conservatively/pessimistically assumes that the latency of a load opcode

  // matches the instruction latency.

  //

  // FIXME: In the absence of cache misses (i.e. L1I/L1D/iTLB/dTLB hits/misses),

  // and load/store conflicts, the latency of a load is determined by the depth

  // of the load pipeline. So, we could use field `LoadLatency` in the

  // MCSchedModel to model that latency.

  // Field `LoadLatency` often matches the so-called 'load-to-use' latency from

  // L1D, and it usually already accounts for any extra latency due to data

  // forwarding.

  // When doing throughput analysis, `LoadLatency` is likely to

  // be a better predictor of load latency than instruction latency. This is

  // particularly true when simulating code with temporal/spatial locality of

  // memory accesses.

  // Using `LoadLatency` (instead of the instruction latency) is also expected

  // to improve the load queue allocation for long latency instructions with

  // folded memory operands (See PR39829).

  //

  // FIXME: On some processors, load/store operations are split into multiple

  // uOps. For example, X86 AMD Jaguar natively supports 128-bit data types, but

  // not 256-bit data types. So, a 256-bit load is effectively split into two

  // 128-bit loads, and each split load consumes one 'LoadQueue' entry. For

  // simplicity, this class optimistically assumes that a load instruction only

  // consumes one entry in the LoadQueue.  Similarly, store instructions only

  // consume a single entry in the StoreQueue.

  // In future, we should reassess the quality of this design, and consider

  // alternative approaches that let instructions specify the number of

  // load/store queue entries which they consume at dispatch stage (See

  // PR39830).

  //

  // An instruction that both 'mayStore' and 'HasUnmodeledSideEffects' is

  // conservatively treated as a store barrier. It forces older store to be

  // executed before newer stores are issued.

  //

  // An instruction that both 'MayLoad' and 'HasUnmodeledSideEffects' is

  // conservatively treated as a load barrier. It forces older loads to execute

  // before newer loads are issued.

  unsigned CurrentLoadGroupID;

  unsigned CurrentLoadBarrierGroupID;

  unsigned CurrentStoreGroupID;

  unsigned CurrentStoreBarrierGroupID;

public:

  LSUnit(const MCSchedModel &SM)

      : LSUnit(SM, /* LQSize */ 0, /* SQSize */ 0, /* NoAlias */ false) {}

  LSUnit(const MCSchedModel &SM, unsigned LQ, unsigned SQ)

      : LSUnit(SM, LQ, SQ, /* NoAlias */ false) {}

  LSUnit(const MCSchedModel &SM, unsigned LQ, unsigned SQ, bool AssumeNoAlias)

      : LSUnitBase(SM, LQ, SQ, AssumeNoAlias), CurrentLoadGroupID(0),

        CurrentLoadBarrierGroupID(0), CurrentStoreGroupID(0),

        CurrentStoreBarrierGroupID(0) {}

  /// Returns LSU_AVAILABLE if there are enough load/store queue entries to

  /// accomodate instruction IR.

  Status isAvailable(const InstRef &IR) const override;

  /// Allocates LS resources for instruction IR.

  ///

  /// This method assumes that a previous call to `isAvailable(IR)` succeeded

  /// returning LSU_AVAILABLE.

  ///

  /// Rules are:

  /// By default, rules are:

  /// 1. A store may not pass a previous store.

  /// 2. A load may not pass a previous store unless flag 'NoAlias' is set.

  /// 3. A load may pass a previous load.

  /// 4. A store may not pass a previous load (regardless of flag 'NoAlias').

  /// 5. A load has to wait until an older load barrier is fully executed.

  /// 6. A store has to wait until an older store barrier is fully executed.

  unsigned dispatch(const InstRef &IR) override;

  void onInstructionExecuted(const InstRef &IR) override;

};

} // namespace mca

} // namespace llvm

#endif // LLVM_MCA_HARDWAREUNITS_LSUNIT_H