Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===--------------------- ResourceManager.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

///

/// The classes here represent processor resource units and their management

/// strategy.  These classes are managed by the Scheduler.

///

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

#ifndef LLVM_MCA_HARDWAREUNITS_RESOURCEMANAGER_H

#define LLVM_MCA_HARDWAREUNITS_RESOURCEMANAGER_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/MC/MCSchedule.h"

#include "llvm/MCA/Instruction.h"

#include "llvm/MCA/Support.h"

namespace llvm {

namespace mca {

/// Used to notify the internal state of a processor resource.

///

/// A processor resource is available if it is not reserved, and there are

/// available slots in the buffer.  A processor resource is unavailable if it

/// is either reserved, or the associated buffer is full. A processor resource

/// with a buffer size of -1 is always available if it is not reserved.

///

/// Values of type ResourceStateEvent are returned by method

/// ResourceManager::canBeDispatched()

///

/// The naming convention for resource state events is:

///  * Event names start with prefix RS_

///  * Prefix RS_ is followed by a string describing the actual resource state.

enum ResourceStateEvent {

  RS_BUFFER_AVAILABLE,

  RS_BUFFER_UNAVAILABLE,

  RS_RESERVED

};

/// Resource allocation strategy used by hardware scheduler resources.

class ResourceStrategy {

  ResourceStrategy(const ResourceStrategy &) = delete;

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

public:

  ResourceStrategy() = default;

  virtual ~ResourceStrategy();

  /// Selects a processor resource unit from a ReadyMask.

  virtual uint64_t select(uint64_t ReadyMask) = 0;

  /// Called by the ResourceManager when a processor resource group, or a

  /// processor resource with multiple units has become unavailable.

  ///

  /// The default strategy uses this information to bias its selection logic.

  virtual void used(uint64_t ResourceMask) {}

};

/// Default resource allocation strategy used by processor resource groups and

/// processor resources with multiple units.

class DefaultResourceStrategy final : public ResourceStrategy {

  /// A Mask of resource unit identifiers.

  ///

  /// There is one bit set for every available resource unit.

  /// It defaults to the value of field ResourceSizeMask in ResourceState.

  const uint64_t ResourceUnitMask;

  /// A simple round-robin selector for processor resource units.

  /// Each bit of this mask identifies a sub resource within a group.

  ///

  /// As an example, lets assume that this is a default policy for a

  /// processor resource group composed by the following three units:

  ///   ResourceA -- 0b001

  ///   ResourceB -- 0b010

  ///   ResourceC -- 0b100

  ///

  /// Field NextInSequenceMask is used to select the next unit from the set of

  /// resource units. It defaults to the value of field `ResourceUnitMasks` (in

  /// this example, it defaults to mask '0b111').

  ///

  /// The round-robin selector would firstly select 'ResourceC', then

  /// 'ResourceB', and eventually 'ResourceA'.  When a resource R is used, the

  /// corresponding bit in NextInSequenceMask is cleared.  For example, if

  /// 'ResourceC' is selected, then the new value of NextInSequenceMask becomes

  /// 0xb011.

  ///

  /// When NextInSequenceMask becomes zero, it is automatically reset to the

  /// default value (i.e. ResourceUnitMask).

  uint64_t NextInSequenceMask;

  /// This field is used to track resource units that are used (i.e. selected)

  /// by other groups other than the one associated with this strategy object.

  ///

  /// In LLVM processor resource groups are allowed to partially (or fully)

  /// overlap. That means, a same unit may be visible to multiple groups.

  /// This field keeps track of uses that have originated from outside of

  /// this group. The idea is to bias the selection strategy, so that resources

  /// that haven't been used by other groups get prioritized.

  ///

  /// The end goal is to (try to) keep the resource distribution as much uniform

  /// as possible. By construction, this mask only tracks one-level of resource

  /// usage. Therefore, this strategy is expected to be less accurate when same

  /// units are used multiple times by other groups within a single round of

  /// select.

  ///

  /// Note: an LRU selector would have a better accuracy at the cost of being

  /// slightly more expensive (mostly in terms of runtime cost). Methods

  /// 'select' and 'used', are always in the hot execution path of llvm-mca.

  /// Therefore, a slow implementation of 'select' would have a negative impact

  /// on the overall performance of the tool.

  uint64_t RemovedFromNextInSequence;

public:

  DefaultResourceStrategy(uint64_t UnitMask)

      : ResourceUnitMask(UnitMask), NextInSequenceMask(UnitMask),

        RemovedFromNextInSequence(0) {}

  virtual ~DefaultResourceStrategy() = default;

  uint64_t select(uint64_t ReadyMask) override;

  void used(uint64_t Mask) override;

};

/// A processor resource descriptor.

///

/// There is an instance of this class for every processor resource defined by

/// the machine scheduling model.

/// Objects of class ResourceState dynamically track the usage of processor

/// resource units.

class ResourceState {

  /// An index to the MCProcResourceDesc entry in the processor model.

  const unsigned ProcResourceDescIndex;

  /// A resource mask. This is generated by the tool with the help of

  /// function `mca::computeProcResourceMasks' (see Support.h).

  ///

  /// Field ResourceMask only has one bit set if this resource state describes a

  /// processor resource unit (i.e. this is not a group). That means, we can

  /// quickly check if a resource is a group by simply counting the number of

  /// bits that are set in the mask.

  ///

  /// The most significant bit of a mask (MSB) uniquely identifies a resource.

  /// Remaining bits are used to describe the composition of a group (Group).

  ///

  /// Example (little endian):

  ///            Resource |  Mask      |  MSB       |  Group

  ///            ---------+------------+------------+------------

  ///            A        |  0b000001  |  0b000001  |  0b000000

  ///                     |            |            |

  ///            B        |  0b000010  |  0b000010  |  0b000000

  ///                     |            |            |

  ///            C        |  0b010000  |  0b010000  |  0b000000

  ///                     |            |            |

  ///            D        |  0b110010  |  0b100000  |  0b010010

  ///

  /// In this example, resources A, B and C are processor resource units.

  /// Only resource D is a group resource, and it contains resources B and C.

  /// That is because MSB(B) and MSB(C) are both contained within Group(D).

  const uint64_t ResourceMask;

  /// A ProcResource can have multiple units.

  ///

  /// For processor resource groups this field is a mask of contained resource

  /// units. It is obtained from ResourceMask by clearing the highest set bit.

  /// The number of resource units in a group can be simply computed as the

  /// population count of this field.

  ///

  /// For normal (i.e. non-group) resources, the number of bits set in this mask

  /// is equivalent to the number of units declared by the processor model (see

  /// field 'NumUnits' in 'ProcResourceUnits').

  uint64_t ResourceSizeMask;

  /// A mask of ready units.

  uint64_t ReadyMask;

  /// Buffered resources will have this field set to a positive number different

  /// than zero. A buffered resource behaves like a reservation station

  /// implementing its own buffer for out-of-order execution.

  ///

  /// A BufferSize of 1 is used by scheduler resources that force in-order

  /// execution.

  ///

  /// A BufferSize of 0 is used to model in-order issue/dispatch resources.

  /// Since in-order issue/dispatch resources don't implement buffers, dispatch

  /// events coincide with issue events.

  /// Also, no other instruction ca be dispatched/issue while this resource is

  /// in use. Only when all the "resource cycles" are consumed (after the issue

  /// event), a new instruction ca be dispatched.

  const int BufferSize;

  /// Available slots in the buffer (zero, if this is not a buffered resource).

  unsigned AvailableSlots;

  /// This field is set if this resource is currently reserved.

  ///

  /// Resources can be reserved for a number of cycles.

  /// Instructions can still be dispatched to reserved resources. However,

  /// istructions dispatched to a reserved resource cannot be issued to the

  /// underlying units (i.e. pipelines) until the resource is released.

  bool Unavailable;

  const bool IsAGroup;

  /// Checks for the availability of unit 'SubResMask' in the group.

  bool isSubResourceReady(uint64_t SubResMask) const {

    return ReadyMask & SubResMask;

  }

public:

  ResourceState(const MCProcResourceDesc &Desc, unsigned Index, uint64_t Mask);

  unsigned getProcResourceID() const { return ProcResourceDescIndex; }

  uint64_t getResourceMask() const { return ResourceMask; }

  uint64_t getReadyMask() const { return ReadyMask; }

  int getBufferSize() const { return BufferSize; }

  bool isBuffered() const { return BufferSize > 0; }

  bool isInOrder() const { return BufferSize == 1; }

  /// Returns true if this is an in-order dispatch/issue resource.

  bool isADispatchHazard() const { return BufferSize == 0; }

  bool isReserved() const { return Unavailable; }

  void setReserved() { Unavailable = true; }

  void clearReserved() { Unavailable = false; }

  /// Returs true if this resource is not reserved, and if there are at least

  /// `NumUnits` available units.

  bool isReady(unsigned NumUnits = 1) const;

  bool isAResourceGroup() const { return IsAGroup; }

  bool containsResource(uint64_t ID) const { return ResourceMask & ID; }

  void markSubResourceAsUsed(uint64_t ID) {

    assert(isSubResourceReady(ID));

    ReadyMask ^= ID;

  }

  void releaseSubResource(uint64_t ID) {

    assert(!isSubResourceReady(ID));

    ReadyMask ^= ID;

  }

  unsigned getNumUnits() const {

    return isAResourceGroup() ? 1U : llvm::popcount(ResourceSizeMask);

  }

  /// Checks if there is an available slot in the resource buffer.

  ///

  /// Returns RS_BUFFER_AVAILABLE if this is not a buffered resource, or if

  /// there is a slot available.

  ///

  /// Returns RS_RESERVED if this buffered resource is a dispatch hazard, and it

  /// is reserved.

  ///

  /// Returns RS_BUFFER_UNAVAILABLE if there are no available slots.

  ResourceStateEvent isBufferAvailable() const;

  /// Reserve a buffer slot.

  ///

  /// Returns true if the buffer is not full.

  /// It always returns true if BufferSize is set to zero.

  bool reserveBuffer() {

    if (BufferSize <= 0)

      return true;

    --AvailableSlots;

    assert(AvailableSlots <= static_cast<unsigned>(BufferSize));

    return AvailableSlots;

  }

  /// Releases a slot in the buffer.

  void releaseBuffer() {

    // Ignore dispatch hazards or invalid buffer sizes.

    if (BufferSize <= 0)

      return;

    ++AvailableSlots;

    assert(AvailableSlots <= static_cast<unsigned>(BufferSize));

  }

#ifndef NDEBUG

  void dump() const;

#endif

};

/// A resource unit identifier.

///

/// This is used to identify a specific processor resource unit using a pair

/// of indices where the 'first' index is a processor resource mask, and the

/// 'second' index is an index for a "sub-resource" (i.e. unit).

typedef std::pair<uint64_t, uint64_t> ResourceRef;

// First: a MCProcResourceDesc index identifying a buffered resource.

// Second: max number of buffer entries used in this resource.

typedef std::pair<unsigned, unsigned> BufferUsageEntry;

/// A resource manager for processor resource units and groups.

///

/// This class owns all the ResourceState objects, and it is responsible for

/// acting on requests from a Scheduler by updating the internal state of

/// ResourceState objects.

/// This class doesn't know about instruction itineraries and functional units.

/// In future, it can be extended to support itineraries too through the same

/// public interface.

class ResourceManager {

  // Set of resources available on the subtarget.

  //

  // There is an instance of ResourceState for every resource declared by the

  // target scheduling model.

  //

  // Elements of this vector are ordered by resource kind. In particular,

  // resource units take precedence over resource groups.

  //

  // The index of a processor resource in this vector depends on the value of

  // its mask (see the description of field ResourceState::ResourceMask).  In

  // particular, it is computed as the position of the most significant bit set

  // (MSB) in the mask plus one (since we want to ignore the invalid resource

  // descriptor at index zero).

  //

  // Example (little endian):

  //

  //             Resource | Mask    |  MSB    | Index

  //             ---------+---------+---------+-------

  //                 A    | 0b00001 | 0b00001 |   1

  //                      |         |         |

  //                 B    | 0b00100 | 0b00100 |   3

  //                      |         |         |

  //                 C    | 0b10010 | 0b10000 |   5

  //

  //

  // The same index is also used to address elements within vector `Strategies`

  // and vector `Resource2Groups`.

  std::vector<std::unique_ptr<ResourceState>> Resources;

  std::vector<std::unique_ptr<ResourceStrategy>> Strategies;

  // Used to quickly identify groups that own a particular resource unit.

  std::vector<uint64_t> Resource2Groups;

  // A table that maps processor resource IDs to processor resource masks.

  SmallVector<uint64_t, 8> ProcResID2Mask;

  // A table that maps resource indices to actual processor resource IDs in the

  // scheduling model.

  SmallVector<unsigned, 8> ResIndex2ProcResID;

  // Keeps track of which resources are busy, and how many cycles are left

  // before those become usable again.

  SmallDenseMap<ResourceRef, unsigned> BusyResources;

  // Set of processor resource units available on the target.

  uint64_t ProcResUnitMask;

  // Set of processor resource units that are available during this cycle.

  uint64_t AvailableProcResUnits;

  // Set of processor resources that are currently reserved.

  uint64_t ReservedResourceGroups;

  // Set of unavailable scheduler buffer resources. This is used internally to

  // speedup `canBeDispatched()` queries.

  uint64_t AvailableBuffers;

  // Set of dispatch hazard buffer resources that are currently unavailable.

  uint64_t ReservedBuffers;

  // Returns the actual resource unit that will be used.

  ResourceRef selectPipe(uint64_t ResourceID);

  void use(const ResourceRef &RR);

  void release(const ResourceRef &RR);

  unsigned getNumUnits(uint64_t ResourceID) const;

  // Overrides the selection strategy for the processor resource with the given

  // mask.

  void setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,

                             uint64_t ResourceMask);

public:

  ResourceManager(const MCSchedModel &SM);

  virtual ~ResourceManager() = default;

  // Overrides the selection strategy for the resource at index ResourceID in

  // the MCProcResourceDesc table.

  void setCustomStrategy(std::unique_ptr<ResourceStrategy> S,

                         unsigned ResourceID) {

    assert(ResourceID < ProcResID2Mask.size() &&

           "Invalid resource index in input!");

    return setCustomStrategyImpl(std::move(S), ProcResID2Mask[ResourceID]);

  }

  // Returns RS_BUFFER_AVAILABLE if buffered resources are not reserved, and if

  // there are enough available slots in the buffers.

  ResourceStateEvent canBeDispatched(uint64_t ConsumedBuffers) const;

  // Return the processor resource identifier associated to this Mask.

  unsigned resolveResourceMask(uint64_t Mask) const;

  // Acquires a slot from every buffered resource in mask `ConsumedBuffers`.

  // Units that are dispatch hazards (i.e. BufferSize=0) are marked as reserved.

  void reserveBuffers(uint64_t ConsumedBuffers);

  // Releases a slot from every buffered resource in mask `ConsumedBuffers`.

  // ConsumedBuffers is a bitmask of previously acquired buffers (using method

  // `reserveBuffers`). Units that are dispatch hazards (i.e. BufferSize=0) are

  // not automatically unreserved by this method.

  void releaseBuffers(uint64_t ConsumedBuffers);

  // Reserve a processor resource. A reserved resource is not available for

  // instruction issue until it is released.

  void reserveResource(uint64_t ResourceID);

  // Release a previously reserved processor resource.

  void releaseResource(uint64_t ResourceID);

  // Returns a zero mask if resources requested by Desc are all available during

  // this cycle. It returns a non-zero mask value only if there are unavailable

  // processor resources; each bit set in the mask represents a busy processor

  // resource unit or a reserved processor resource group.

  uint64_t checkAvailability(const InstrDesc &Desc) const;

  uint64_t getProcResUnitMask() const { return ProcResUnitMask; }

  uint64_t getAvailableProcResUnits() const { return AvailableProcResUnits; }

  void issueInstruction(

      const InstrDesc &Desc,

      SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);

  void cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed);

#ifndef NDEBUG

  void dump() const {

    for (const std::unique_ptr<ResourceState> &Resource : Resources)

      Resource->dump();

  }

#endif

};

} // namespace mca

} // namespace llvm

#endif // LLVM_MCA_HARDWAREUNITS_RESOURCEMANAGER_H