summaryrefslogtreecommitdiff
path: root/include/llvm/MCA
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/MCA')
-rw-r--r--include/llvm/MCA/Context.h21
-rw-r--r--include/llvm/MCA/HWEventListener.h38
-rw-r--r--include/llvm/MCA/HardwareUnits/HardwareUnit.h7
-rw-r--r--include/llvm/MCA/HardwareUnits/LSUnit.h393
-rw-r--r--include/llvm/MCA/HardwareUnits/RegisterFile.h10
-rw-r--r--include/llvm/MCA/HardwareUnits/ResourceManager.h31
-rw-r--r--include/llvm/MCA/HardwareUnits/RetireControlUnit.h7
-rw-r--r--include/llvm/MCA/HardwareUnits/Scheduler.h138
-rw-r--r--include/llvm/MCA/InstrBuilder.h7
-rw-r--r--include/llvm/MCA/Instruction.h161
-rw-r--r--include/llvm/MCA/Pipeline.h7
-rw-r--r--include/llvm/MCA/SourceMgr.h7
-rw-r--r--include/llvm/MCA/Stages/DispatchStage.h13
-rw-r--r--include/llvm/MCA/Stages/EntryStage.h7
-rw-r--r--include/llvm/MCA/Stages/ExecuteStage.h20
-rw-r--r--include/llvm/MCA/Stages/InstructionTables.h7
-rw-r--r--include/llvm/MCA/Stages/MicroOpQueueStage.h88
-rw-r--r--include/llvm/MCA/Stages/RetireStage.h7
-rw-r--r--include/llvm/MCA/Stages/Stage.h7
-rw-r--r--include/llvm/MCA/Support.h33
20 files changed, 758 insertions, 251 deletions
diff --git a/include/llvm/MCA/Context.h b/include/llvm/MCA/Context.h
index 6b2bee0fdc42..503d780d4947 100644
--- a/include/llvm/MCA/Context.h
+++ b/include/llvm/MCA/Context.h
@@ -1,9 +1,8 @@
//===---------------------------- Context.h ---------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -32,15 +31,21 @@ namespace mca {
/// This is a convenience struct to hold the parameters necessary for creating
/// the pre-built "default" out-of-order pipeline.
struct PipelineOptions {
- PipelineOptions(unsigned DW, unsigned RFS, unsigned LQS, unsigned SQS,
- bool NoAlias)
- : DispatchWidth(DW), RegisterFileSize(RFS), LoadQueueSize(LQS),
- StoreQueueSize(SQS), AssumeNoAlias(NoAlias) {}
+ PipelineOptions(unsigned UOPQSize, unsigned DecThr, unsigned DW, unsigned RFS,
+ unsigned LQS, unsigned SQS, bool NoAlias,
+ bool ShouldEnableBottleneckAnalysis = false)
+ : MicroOpQueueSize(UOPQSize), DecodersThroughput(DecThr),
+ DispatchWidth(DW), RegisterFileSize(RFS), LoadQueueSize(LQS),
+ StoreQueueSize(SQS), AssumeNoAlias(NoAlias),
+ EnableBottleneckAnalysis(ShouldEnableBottleneckAnalysis) {}
+ unsigned MicroOpQueueSize;
+ unsigned DecodersThroughput; // Instructions per cycle.
unsigned DispatchWidth;
unsigned RegisterFileSize;
unsigned LoadQueueSize;
unsigned StoreQueueSize;
bool AssumeNoAlias;
+ bool EnableBottleneckAnalysis;
};
class Context {
diff --git a/include/llvm/MCA/HWEventListener.h b/include/llvm/MCA/HWEventListener.h
index 3b32b2cd6577..e11d06de2b2e 100644
--- a/include/llvm/MCA/HWEventListener.h
+++ b/include/llvm/MCA/HWEventListener.h
@@ -1,9 +1,8 @@
//===----------------------- HWEventListener.h ------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -40,6 +39,7 @@ public:
// Events generated by the Retire Control Unit.
Retired,
// Events generated by the Scheduler.
+ Pending,
Ready,
Issued,
Executed,
@@ -126,6 +126,35 @@ public:
const InstRef &IR;
};
+// A HWPressureEvent describes an increase in backend pressure caused by
+// the presence of data dependencies or unavailability of pipeline resources.
+class HWPressureEvent {
+public:
+ enum GenericReason {
+ INVALID = 0,
+ // Scheduler was unable to issue all the ready instructions because some
+ // pipeline resources were unavailable.
+ RESOURCES,
+ // Instructions could not be issued because of register data dependencies.
+ REGISTER_DEPS,
+ // Instructions could not be issued because of memory dependencies.
+ MEMORY_DEPS
+ };
+
+ HWPressureEvent(GenericReason reason, ArrayRef<InstRef> Insts,
+ uint64_t Mask = 0)
+ : Reason(reason), AffectedInstructions(Insts), ResourceMask(Mask) {}
+
+ // Reason for this increase in backend pressure.
+ GenericReason Reason;
+
+ // Instructions affected (i.e. delayed) by this increase in backend pressure.
+ ArrayRef<InstRef> AffectedInstructions;
+
+ // A mask of unavailable processor resources.
+ const uint64_t ResourceMask;
+};
+
class HWEventListener {
public:
// Generic events generated by the pipeline.
@@ -134,6 +163,7 @@ public:
virtual void onEvent(const HWInstructionEvent &Event) {}
virtual void onEvent(const HWStallEvent &Event) {}
+ virtual void onEvent(const HWPressureEvent &Event) {}
using ResourceRef = std::pair<uint64_t, uint64_t>;
virtual void onResourceAvailable(const ResourceRef &RRef) {}
diff --git a/include/llvm/MCA/HardwareUnits/HardwareUnit.h b/include/llvm/MCA/HardwareUnits/HardwareUnit.h
index 104a2009f219..f6e178bcff10 100644
--- a/include/llvm/MCA/HardwareUnits/HardwareUnit.h
+++ b/include/llvm/MCA/HardwareUnits/HardwareUnit.h
@@ -1,9 +1,8 @@
//===-------------------------- HardwareUnit.h ------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/HardwareUnits/LSUnit.h b/include/llvm/MCA/HardwareUnits/LSUnit.h
index e217fc50f780..ae9a49c64855 100644
--- a/include/llvm/MCA/HardwareUnits/LSUnit.h
+++ b/include/llvm/MCA/HardwareUnits/LSUnit.h
@@ -1,9 +1,8 @@
//===------------------------- LSUnit.h --------------------------*- C++-*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -16,21 +15,298 @@
#ifndef LLVM_MCA_LSUNIT_H
#define LLVM_MCA_LSUNIT_H
-#include "llvm/ADT/SmallSet.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 {
-class InstRef;
class Scheduler;
-/// A Load/Store Unit implementing a load and store queues.
+/// A node of a memory dependency graph. A MemoryGroup describes a set of
+/// instructions with same memory dependencies.
///
-/// This class implements a load queue and a store queue to emulate the
-/// out-of-order execution of memory operations.
-/// Each load (or store) consumes an entry in the load (or store) queue.
+/// 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;
+ SmallVector<MemoryGroup *, 4> Succ;
+
+ 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(), CriticalMemoryInstruction() {}
+ MemoryGroup(MemoryGroup &&) = default;
+
+ ArrayRef<MemoryGroup *> getSuccessors() const { return Succ; }
+ unsigned getNumSuccessors() const { return Succ.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) {
+ Group->NumPredecessors++;
+ assert(!isExecuted() && "Should have been removed!");
+ if (isExecuting())
+ Group->onGroupIssued(CriticalMemoryInstruction);
+ Succ.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) {
+ assert(!isReady() && "Unexpected group-start event!");
+ NumExecutingPredecessors++;
+
+ 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 : Succ)
+ MG->onGroupIssued(CriticalMemoryInstruction);
+ }
+
+ void onInstructionExecuted() {
+ assert(isReady() && !isExecuted() && "Invalid internal state!");
+ --NumExecuting;
+ ++NumExecuted;
+
+ if (!isExecuted())
+ return;
+
+ // Notify successors that this group has finished execution.
+ for (MemoryGroup *MG : Succ)
+ 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; }
+ unsigned assignLQSlot() { return UsedLQEntries++; }
+ unsigned assignSQSlot() { return 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, llvm::make_unique<MemoryGroup>()));
+ return NextGroupID++;
+ }
+
+ // Instruction executed event handlers.
+ virtual void onInstructionExecuted(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
@@ -89,26 +365,7 @@ class Scheduler;
/// 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 HardwareUnit {
- // Load queue size.
- // LQ_Size == 0 means that there are infinite slots in the load queue.
- unsigned LQ_Size;
-
- // Store queue size.
- // SQ_Size == 0 means that there are infinite slots in the store queue.
- unsigned SQ_Size;
-
- // If true, loads will never alias with stores. This is the default.
- bool NoAlias;
-
- // When a `MayLoad` instruction is dispatched to the schedulers for execution,
- // the LSUnit reserves an entry in the `LoadQueue` for it.
- //
- // LoadQueue keeps track of all the loads that are in-flight. A load
- // instruction is eventually removed from the LoadQueue when it reaches
- // completion stage. That means, a load leaves the queue whe it is 'executed',
- // and its value can be forwarded on the data path to outside units.
- //
+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.
@@ -139,66 +396,50 @@ class LSUnit : public HardwareUnit {
// alternative approaches that let instructions specify the number of
// load/store queue entries which they consume at dispatch stage (See
// PR39830).
- SmallSet<unsigned, 16> LoadQueue;
- SmallSet<unsigned, 16> StoreQueue;
-
- void assignLQSlot(unsigned Index);
- void assignSQSlot(unsigned Index);
- bool isReadyNoAlias(unsigned Index) const;
-
+ //
// 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.
- SmallSet<unsigned, 8> StoreBarriers;
-
+ //
// 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.
- SmallSet<unsigned, 8> LoadBarriers;
-
- bool isSQEmpty() const { return StoreQueue.empty(); }
- bool isLQEmpty() const { return LoadQueue.empty(); }
- bool isSQFull() const { return SQ_Size != 0 && StoreQueue.size() == SQ_Size; }
- bool isLQFull() const { return LQ_Size != 0 && LoadQueue.size() == LQ_Size; }
+ unsigned CurrentLoadGroupID;
+ unsigned CurrentLoadBarrierGroupID;
+ unsigned CurrentStoreGroupID;
public:
- LSUnit(const MCSchedModel &SM, unsigned LQ = 0, unsigned SQ = 0,
- bool AssumeNoAlias = false);
+ 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) {}
-#ifndef NDEBUG
- void dump() const;
-#endif
-
- enum Status { LSU_AVAILABLE = 0, LSU_LQUEUE_FULL, LSU_SQUEUE_FULL };
-
- // Returns LSU_AVAILABLE if there are enough load/store queue entries to serve
- // IR. It also returns LSU_AVAILABLE if IR is not a memory operation.
- Status isAvailable(const InstRef &IR) const;
-
- // Allocates load/store queue resources for IR.
- //
- // This method assumes that a previous call to `isAvailable(IR)` returned
- // LSU_AVAILABLE, and that IR is a memory operation.
- void dispatch(const InstRef &IR);
+ /// Returns LSU_AVAILABLE if there are enough load/store queue entries to
+ /// accomodate instruction IR.
+ Status isAvailable(const InstRef &IR) const override;
- // 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.
- virtual bool isReady(const InstRef &IR) const;
+ /// 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;
- // Load and store instructions are tracked by their corresponding queues from
- // dispatch until the "instruction executed" event.
- // Only when a load instruction reaches the 'Executed' stage, its value
- // becomes available to the users. At that point, the load no longer needs to
- // be tracked by the load queue.
// FIXME: For simplicity, we optimistically assume a similar behavior for
// store instructions. In practice, store operations don't tend to leave the
// store queue until they reach the 'Retired' stage (See PR39830).
- void onInstructionExecuted(const InstRef &IR);
+ void onInstructionExecuted(const InstRef &IR) override;
};
} // namespace mca
diff --git a/include/llvm/MCA/HardwareUnits/RegisterFile.h b/include/llvm/MCA/HardwareUnits/RegisterFile.h
index c23ab0389234..36506327bd29 100644
--- a/include/llvm/MCA/HardwareUnits/RegisterFile.h
+++ b/include/llvm/MCA/HardwareUnits/RegisterFile.h
@@ -1,9 +1,8 @@
//===--------------------- RegisterFile.h -----------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -21,6 +20,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/MC/MCSchedule.h"
+#include "llvm/MC/MCSubtargetInfo.h"
#include "llvm/MCA/HardwareUnits/HardwareUnit.h"
#include "llvm/Support/Error.h"
@@ -196,7 +196,7 @@ public:
// Collect writes that are in a data dependency with RS, and update RS
// internal state.
- void addRegisterRead(ReadState &RS, SmallVectorImpl<WriteRef> &Writes) const;
+ void addRegisterRead(ReadState &RS, const MCSubtargetInfo &STI) const;
// Removes write \param WS from the register mappings.
// Physical registers may be released to reflect this update.
diff --git a/include/llvm/MCA/HardwareUnits/ResourceManager.h b/include/llvm/MCA/HardwareUnits/ResourceManager.h
index 549a46c247fe..2f91185516fb 100644
--- a/include/llvm/MCA/HardwareUnits/ResourceManager.h
+++ b/include/llvm/MCA/HardwareUnits/ResourceManager.h
@@ -1,9 +1,8 @@
//===--------------------- ResourceManager.h --------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -335,13 +334,26 @@ class ResourceManager {
// Used to quickly identify groups that own a particular resource unit.
std::vector<uint64_t> Resource2Groups;
- // A table to map processor resource IDs to processor resource masks.
+ // 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 resource groups that are currently reserved.
+ uint64_t ReservedResourceGroups;
+
// Returns the actual resource unit that will be used.
ResourceRef selectPipe(uint64_t ResourceID);
@@ -389,7 +401,14 @@ public:
// Release a previously reserved processor resource.
void releaseResource(uint64_t ResourceID);
- bool canBeIssued(const InstrDesc &Desc) const;
+ // 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,
diff --git a/include/llvm/MCA/HardwareUnits/RetireControlUnit.h b/include/llvm/MCA/HardwareUnits/RetireControlUnit.h
index 71360e984ade..06290141739e 100644
--- a/include/llvm/MCA/HardwareUnits/RetireControlUnit.h
+++ b/include/llvm/MCA/HardwareUnits/RetireControlUnit.h
@@ -1,9 +1,8 @@
//===---------------------- RetireControlUnit.h -----------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/HardwareUnits/Scheduler.h b/include/llvm/MCA/HardwareUnits/Scheduler.h
index 351ea4827df9..27beb842dfd2 100644
--- a/include/llvm/MCA/HardwareUnits/Scheduler.h
+++ b/include/llvm/MCA/HardwareUnits/Scheduler.h
@@ -1,9 +1,8 @@
//===--------------------- Scheduler.h ------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -68,22 +67,6 @@ public:
/// resources. This class is also responsible for tracking the progress of
/// instructions from the dispatch stage, until the write-back stage.
///
-/// An instruction dispatched to the Scheduler is initially placed into either
-/// the 'WaitSet' or the 'ReadySet' depending on the availability of the input
-/// operands.
-///
-/// An instruction is moved from the WaitSet to the ReadySet when register
-/// operands become available, and all memory dependencies are met.
-/// Instructions that are moved from the WaitSet to the ReadySet transition
-/// in state from 'IS_AVAILABLE' to 'IS_READY'.
-///
-/// On every cycle, the Scheduler checks if it can promote instructions from the
-/// WaitSet to the ReadySet.
-///
-/// An Instruction is moved from the ReadySet the `IssuedSet` when it is issued
-/// to a (one or more) pipeline(s). This event also causes an instruction state
-/// transition (i.e. from state IS_READY, to state IS_EXECUTING). An Instruction
-/// leaves the IssuedSet when it reaches the write-back stage.
class Scheduler : public HardwareUnit {
LSUnit &LSU;
@@ -93,10 +76,58 @@ class Scheduler : public HardwareUnit {
// 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.
@@ -112,9 +143,15 @@ class Scheduler : public HardwareUnit {
// vector 'Executed'.
void updateIssuedSet(SmallVectorImpl<InstRef> &Executed);
- // Try to promote instructions from WaitSet to ReadySet.
+ // Try to promote instructions from the PendingSet to the ReadySet.
// Add promoted instructions to the 'Ready' vector in input.
- void promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
+ // 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, LSUnit &Lsu)
@@ -127,7 +164,8 @@ public:
Scheduler(std::unique_ptr<ResourceManager> RM, LSUnit &Lsu,
std::unique_ptr<SchedulerStrategy> SelectStrategy)
- : LSU(Lsu), Resources(std::move(RM)) {
+ : LSU(Lsu), Resources(std::move(RM)), BusyResourceUnits(0),
+ NumDispatchedToThePendingSet(0), HadTokenStall(false) {
initializeStrategy(std::move(SelectStrategy));
}
@@ -140,15 +178,12 @@ public:
SC_DISPATCH_GROUP_STALL,
};
- /// Check if the instruction in 'IR' can be dispatched and returns an answer
- /// in the form of a Status value.
+ /// Check if the instruction in 'IR' can be dispatched during this cycle.
+ /// Return SC_AVAILABLE if both scheduler and LS resources are available.
///
- /// The DispatchStage is responsible for querying the Scheduler before
- /// dispatching new instructions. This routine is used for performing such
- /// a query. If the instruction 'IR' can be dispatched, then true is
- /// returned, otherwise false is returned with Event set to the stall type.
- /// Internally, it also checks if the load/store unit is available.
- Status isAvailable(const InstRef &IR) const;
+ /// 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.
@@ -156,11 +191,11 @@ public:
/// 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`.
- void dispatch(const InstRef &IR);
-
- /// Returns true if IR is ready to be executed by the underlying pipelines.
- /// This method assumes that IR has been previously dispatched.
- bool isReady(const InstRef &IR) const;
+ ///
+ /// 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
@@ -168,6 +203,7 @@ public:
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
@@ -181,9 +217,15 @@ public:
/// 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> &Ready,
- SmallVectorImpl<InstRef> &Executed);
+ SmallVectorImpl<InstRef> &Executed,
+ SmallVectorImpl<InstRef> &Pending,
+ SmallVectorImpl<InstRef> &Ready);
/// Convert a resource mask into a valid llvm processor resource identifier.
unsigned getResourceID(uint64_t Mask) const {
@@ -195,6 +237,26 @@ public:
/// 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;
diff --git a/include/llvm/MCA/InstrBuilder.h b/include/llvm/MCA/InstrBuilder.h
index 5f998db5e4ce..690016354f7a 100644
--- a/include/llvm/MCA/InstrBuilder.h
+++ b/include/llvm/MCA/InstrBuilder.h
@@ -1,9 +1,8 @@
//===--------------------- InstrBuilder.h -----------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/Instruction.h b/include/llvm/MCA/Instruction.h
index b91610c64d85..d4d3f22797f7 100644
--- a/include/llvm/MCA/Instruction.h
+++ b/include/llvm/MCA/Instruction.h
@@ -1,9 +1,8 @@
//===--------------------- Instruction.h ------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -81,6 +80,15 @@ struct ReadDescriptor {
class ReadState;
+/// A critical data dependency descriptor.
+///
+/// Field RegID is set to the invalid register for memory dependencies.
+struct CriticalDependency {
+ unsigned IID;
+ unsigned RegID;
+ unsigned Cycles;
+};
+
/// Tracks uses of a register definition (e.g. register write).
///
/// Each implicit/explicit register write is associated with an instance of
@@ -124,9 +132,11 @@ class WriteState {
// A partial write that is in a false dependency with this write.
WriteState *PartialWrite;
-
unsigned DependentWriteCyclesLeft;
+ // Critical register dependency for this write.
+ CriticalDependency CRD;
+
// A list of dependent reads. Users is a set of dependent
// reads. A dependent read is added to the set only if CyclesLeft
// is "unknown". As soon as CyclesLeft is 'known', each user in the set
@@ -141,7 +151,7 @@ public:
: WD(&Desc), CyclesLeft(UNKNOWN_CYCLES), RegisterID(RegID), PRFID(0),
ClearsSuperRegs(clearsSuperRegs), WritesZero(writesZero),
IsEliminated(false), DependentWrite(nullptr), PartialWrite(nullptr),
- DependentWriteCyclesLeft(0) {}
+ DependentWriteCyclesLeft(0), CRD() {}
WriteState(const WriteState &Other) = default;
WriteState &operator=(const WriteState &Other) = default;
@@ -151,13 +161,21 @@ public:
unsigned getRegisterID() const { return RegisterID; }
unsigned getRegisterFileID() const { return PRFID; }
unsigned getLatency() const { return WD->Latency; }
-
- void addUser(ReadState *Use, int ReadAdvance);
- void addUser(WriteState *Use);
-
unsigned getDependentWriteCyclesLeft() const {
return DependentWriteCyclesLeft;
}
+ const WriteState *getDependentWrite() const { return DependentWrite; }
+ const CriticalDependency &getCriticalRegDep() const { return CRD; }
+
+ // This method adds Use to the set of data dependent reads. IID is the
+ // instruction identifier associated with this write. ReadAdvance is the
+ // number of cycles to subtract from the latency of this data dependency.
+ // Use is in a RAW dependency with this write.
+ void addUser(unsigned IID, ReadState *Use, int ReadAdvance);
+
+ // Use is a younger register write that is in a false dependency with this
+ // write. IID is the instruction identifier associated with this write.
+ void addUser(unsigned IID, WriteState *Use);
unsigned getNumUsers() const {
unsigned NumUsers = Users.size();
@@ -169,17 +187,20 @@ public:
bool clearsSuperRegisters() const { return ClearsSuperRegs; }
bool isWriteZero() const { return WritesZero; }
bool isEliminated() const { return IsEliminated; }
- bool isExecuted() const {
- return CyclesLeft != UNKNOWN_CYCLES && CyclesLeft <= 0;
+
+ bool isReady() const {
+ if (DependentWrite)
+ return false;
+ unsigned CyclesLeft = getDependentWriteCyclesLeft();
+ return !CyclesLeft || CyclesLeft < getLatency();
}
- const WriteState *getDependentWrite() const { return DependentWrite; }
- void setDependentWrite(WriteState *Other) { DependentWrite = Other; }
- void writeStartEvent(unsigned Cycles) {
- DependentWriteCyclesLeft = Cycles;
- DependentWrite = nullptr;
+ bool isExecuted() const {
+ return CyclesLeft != UNKNOWN_CYCLES && CyclesLeft <= 0;
}
+ void setDependentWrite(const WriteState *Other) { DependentWrite = Other; }
+ void writeStartEvent(unsigned IID, unsigned RegID, unsigned Cycles);
void setWriteZero() { WritesZero = true; }
void setEliminated() {
assert(Users.empty() && "Write is in an inconsistent state.");
@@ -191,7 +212,7 @@ public:
// On every cycle, update CyclesLeft and notify dependent users.
void cycleEvent();
- void onInstructionIssued();
+ void onInstructionIssued(unsigned IID);
#ifndef NDEBUG
void dump() const;
@@ -221,6 +242,8 @@ class ReadState {
// dependent writes (i.e. field DependentWrite) is zero, this value is
// propagated to field CyclesLeft.
unsigned TotalCycles;
+ // Longest register dependency.
+ CriticalDependency CRD;
// This field is set to true only if there are no dependent writes, and
// there are no `CyclesLeft' to wait.
bool IsReady;
@@ -232,14 +255,16 @@ class ReadState {
public:
ReadState(const ReadDescriptor &Desc, unsigned RegID)
: RD(&Desc), RegisterID(RegID), PRFID(0), DependentWrites(0),
- CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), IsReady(true),
+ CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), CRD(), IsReady(true),
IsZero(false), IndependentFromDef(false) {}
const ReadDescriptor &getDescriptor() const { return *RD; }
unsigned getSchedClass() const { return RD->SchedClassID; }
unsigned getRegisterID() const { return RegisterID; }
unsigned getRegisterFileID() const { return PRFID; }
+ const CriticalDependency &getCriticalRegDep() const { return CRD; }
+ bool isPending() const { return !IndependentFromDef && CyclesLeft > 0; }
bool isReady() const { return IsReady; }
bool isImplicitRead() const { return RD->isImplicitRead(); }
@@ -247,7 +272,7 @@ public:
void setIndependentFromDef() { IndependentFromDef = true; }
void cycleEvent();
- void writeStartEvent(unsigned Cycles);
+ void writeStartEvent(unsigned IID, unsigned RegID, unsigned Cycles);
void setDependentWrites(unsigned Writes) {
DependentWrites = Writes;
IsReady = !Writes;
@@ -330,9 +355,16 @@ struct InstrDesc {
// A list of buffered resources consumed by this instruction.
SmallVector<uint64_t, 4> Buffers;
+ unsigned UsedProcResUnits;
+ unsigned UsedProcResGroups;
+
unsigned MaxLatency;
// Number of MicroOps for this instruction.
unsigned NumMicroOps;
+ // SchedClassID used to construct this InstrDesc.
+ // This information is currently used by views to do fast queries on the
+ // subtarget when computing the reciprocal throughput.
+ unsigned SchedClassID;
bool MayLoad;
bool MayStore;
@@ -398,6 +430,7 @@ public:
// Returns true if this instruction is a candidate for move elimination.
bool isOptimizableMove() const { return IsOptimizableMove; }
void setOptimizableMove() { IsOptimizableMove = true; }
+ bool isMemOp() const { return Desc.MayLoad || Desc.MayStore; }
};
/// An instruction propagated through the simulated instruction pipeline.
@@ -406,12 +439,13 @@ public:
/// that are sent to the various components of the simulated hardware pipeline.
class Instruction : public InstructionBase {
enum InstrStage {
- IS_INVALID, // Instruction in an invalid state.
- IS_AVAILABLE, // Instruction dispatched but operands are not ready.
- IS_READY, // Instruction dispatched and operands ready.
- IS_EXECUTING, // Instruction issued.
- IS_EXECUTED, // Instruction executed. Values are written back.
- IS_RETIRED // Instruction retired.
+ IS_INVALID, // Instruction in an invalid state.
+ IS_DISPATCHED, // Instruction dispatched but operands are not ready.
+ IS_PENDING, // Instruction is not ready, but operand latency is known.
+ IS_READY, // Instruction dispatched and operands ready.
+ IS_EXECUTING, // Instruction issued.
+ IS_EXECUTED, // Instruction executed. Values are written back.
+ IS_RETIRED // Instruction retired.
};
// The current instruction stage.
@@ -424,12 +458,34 @@ class Instruction : public InstructionBase {
// Retire Unit token ID for this instruction.
unsigned RCUTokenID;
+ // LS token ID for this instruction.
+ // This field is set to the invalid null token if this is not a memory
+ // operation.
+ unsigned LSUTokenID;
+
+ // Critical register dependency.
+ CriticalDependency CriticalRegDep;
+
+ // Critical memory dependency.
+ CriticalDependency CriticalMemDep;
+
+ // A bitmask of busy processor resource units.
+ // This field is set to zero only if execution is not delayed during this
+ // cycle because of unavailable pipeline resources.
+ uint64_t CriticalResourceMask;
+
+ // True if this instruction has been optimized at register renaming stage.
+ bool IsEliminated;
+
public:
Instruction(const InstrDesc &D)
: InstructionBase(D), Stage(IS_INVALID), CyclesLeft(UNKNOWN_CYCLES),
- RCUTokenID(0) {}
+ RCUTokenID(0), LSUTokenID(0), CriticalRegDep(), CriticalMemDep(),
+ CriticalResourceMask(0), IsEliminated(false) {}
unsigned getRCUTokenID() const { return RCUTokenID; }
+ unsigned getLSUTokenID() const { return LSUTokenID; }
+ void setLSUTokenID(unsigned LSUTok) { LSUTokenID = LSUTok; }
int getCyclesLeft() const { return CyclesLeft; }
// Transition to the dispatch stage, and assign a RCUToken to this
@@ -438,37 +494,48 @@ public:
void dispatch(unsigned RCUTokenID);
// Instruction issued. Transition to the IS_EXECUTING state, and update
- // all the definitions.
- void execute();
+ // all the register definitions.
+ void execute(unsigned IID);
- // Force a transition from the IS_AVAILABLE state to the IS_READY state if
- // input operands are all ready. State transitions normally occur at the
- // beginning of a new cycle (see method cycleEvent()). However, the scheduler
- // may decide to promote instructions from the wait queue to the ready queue
- // as the result of another issue event. This method is called every time the
- // instruction might have changed in state.
+ // Force a transition from the IS_DISPATCHED state to the IS_READY or
+ // IS_PENDING state. State transitions normally occur either at the beginning
+ // of a new cycle (see method cycleEvent()), or as a result of another issue
+ // event. This method is called every time the instruction might have changed
+ // in state. It internally delegates to method updateDispatched() and
+ // updateWaiting().
void update();
+ bool updateDispatched();
+ bool updatePending();
- bool isDispatched() const { return Stage == IS_AVAILABLE; }
+ bool isDispatched() const { return Stage == IS_DISPATCHED; }
+ bool isPending() const { return Stage == IS_PENDING; }
bool isReady() const { return Stage == IS_READY; }
bool isExecuting() const { return Stage == IS_EXECUTING; }
bool isExecuted() const { return Stage == IS_EXECUTED; }
bool isRetired() const { return Stage == IS_RETIRED; }
+ bool isEliminated() const { return IsEliminated; }
- bool isEliminated() const {
- return isReady() && getDefs().size() &&
- all_of(getDefs(),
- [](const WriteState &W) { return W.isEliminated(); });
- }
-
- // Forces a transition from state IS_AVAILABLE to state IS_EXECUTED.
+ // Forces a transition from state IS_DISPATCHED to state IS_EXECUTED.
void forceExecuted();
+ void setEliminated() { IsEliminated = true; }
void retire() {
assert(isExecuted() && "Instruction is in an invalid state!");
Stage = IS_RETIRED;
}
+ const CriticalDependency &getCriticalRegDep() const { return CriticalRegDep; }
+ const CriticalDependency &getCriticalMemDep() const { return CriticalMemDep; }
+ const CriticalDependency &computeCriticalRegDep();
+ void setCriticalMemDep(const CriticalDependency &MemDep) {
+ CriticalMemDep = MemDep;
+ }
+
+ uint64_t getCriticalResourceMask() const { return CriticalResourceMask; }
+ void setCriticalResourceMask(uint64_t ResourceMask) {
+ CriticalResourceMask = ResourceMask;
+ }
+
void cycleEvent();
};
@@ -483,13 +550,17 @@ public:
InstRef(unsigned Index, Instruction *I) : Data(std::make_pair(Index, I)) {}
bool operator==(const InstRef &Other) const { return Data == Other.Data; }
+ bool operator!=(const InstRef &Other) const { return Data != Other.Data; }
+ bool operator<(const InstRef &Other) const {
+ return Data.first < Other.Data.first;
+ }
unsigned getSourceIndex() const { return Data.first; }
Instruction *getInstruction() { return Data.second; }
const Instruction *getInstruction() const { return Data.second; }
/// Returns true if this references a valid instruction.
- operator bool() const { return Data.second != nullptr; }
+ explicit operator bool() const { return Data.second != nullptr; }
/// Invalidate this reference.
void invalidate() { Data.second = nullptr; }
@@ -537,7 +608,7 @@ public:
return !WS || WS->isExecuted();
}
- bool isValid() const { return Data.first != INVALID_IID && Data.second; }
+ bool isValid() const { return Data.second && Data.first != INVALID_IID; }
bool operator==(const WriteRef &Other) const { return Data == Other.Data; }
#ifndef NDEBUG
diff --git a/include/llvm/MCA/Pipeline.h b/include/llvm/MCA/Pipeline.h
index acd256060bdd..935033f67f8b 100644
--- a/include/llvm/MCA/Pipeline.h
+++ b/include/llvm/MCA/Pipeline.h
@@ -1,9 +1,8 @@
//===--------------------- Pipeline.h ---------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/SourceMgr.h b/include/llvm/MCA/SourceMgr.h
index 5e0ca6419f5d..dbe31db1b1dd 100644
--- a/include/llvm/MCA/SourceMgr.h
+++ b/include/llvm/MCA/SourceMgr.h
@@ -1,9 +1,8 @@
//===--------------------- SourceMgr.h --------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/Stages/DispatchStage.h b/include/llvm/MCA/Stages/DispatchStage.h
index f015cd7522eb..d80ededeaca1 100644
--- a/include/llvm/MCA/Stages/DispatchStage.h
+++ b/include/llvm/MCA/Stages/DispatchStage.h
@@ -1,9 +1,8 @@
//===----------------------- DispatchStage.h --------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -62,8 +61,6 @@ class DispatchStage final : public Stage {
bool canDispatch(const InstRef &IR) const;
Error dispatch(InstRef IR);
- void updateRAWDependencies(ReadState &RS, const MCSubtargetInfo &STI);
-
void notifyInstructionDispatched(const InstRef &IR,
ArrayRef<unsigned> UsedPhysRegs,
unsigned uOps) const;
@@ -71,9 +68,7 @@ class DispatchStage final : public Stage {
public:
DispatchStage(const MCSubtargetInfo &Subtarget, const MCRegisterInfo &MRI,
unsigned MaxDispatchWidth, RetireControlUnit &R,
- RegisterFile &F)
- : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth),
- CarryOver(0U), CarriedOver(), STI(Subtarget), RCU(R), PRF(F) {}
+ RegisterFile &F);
bool isAvailable(const InstRef &IR) const override;
diff --git a/include/llvm/MCA/Stages/EntryStage.h b/include/llvm/MCA/Stages/EntryStage.h
index cd9a65b8cc2b..59a2daff886e 100644
--- a/include/llvm/MCA/Stages/EntryStage.h
+++ b/include/llvm/MCA/Stages/EntryStage.h
@@ -1,9 +1,8 @@
//===---------------------- EntryStage.h ------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/Stages/ExecuteStage.h b/include/llvm/MCA/Stages/ExecuteStage.h
index 8cb287e06d9f..03737e0220eb 100644
--- a/include/llvm/MCA/Stages/ExecuteStage.h
+++ b/include/llvm/MCA/Stages/ExecuteStage.h
@@ -1,9 +1,8 @@
//===---------------------- ExecuteStage.h ----------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -29,6 +28,12 @@ namespace mca {
class ExecuteStage final : public Stage {
Scheduler &HWS;
+ unsigned NumDispatchedOpcodes;
+ unsigned NumIssuedOpcodes;
+
+ // True if this stage should notify listeners of HWPressureEvents.
+ bool EnablePressureEvents;
+
Error issueInstruction(InstRef &IR);
// Called at the beginning of each cycle to issue already dispatched
@@ -42,7 +47,10 @@ class ExecuteStage final : public Stage {
ExecuteStage &operator=(const ExecuteStage &Other) = delete;
public:
- ExecuteStage(Scheduler &S) : Stage(), HWS(S) {}
+ ExecuteStage(Scheduler &S) : ExecuteStage(S, false) {}
+ ExecuteStage(Scheduler &S, bool ShouldPerformBottleneckAnalysis)
+ : Stage(), HWS(S), NumDispatchedOpcodes(0), NumIssuedOpcodes(0),
+ EnablePressureEvents(ShouldPerformBottleneckAnalysis) {}
// This stage works under the assumption that the Pipeline will eventually
// execute a retire stage. We don't need to check if pipelines and/or
@@ -61,12 +69,14 @@ public:
// Instructions that transitioned to the 'Executed' state are automatically
// moved to the next stage (i.e. RetireStage).
Error cycleStart() override;
+ Error cycleEnd() override;
Error execute(InstRef &IR) override;
void notifyInstructionIssued(
const InstRef &IR,
MutableArrayRef<std::pair<ResourceRef, ResourceCycles>> Used) const;
void notifyInstructionExecuted(const InstRef &IR) const;
+ void notifyInstructionPending(const InstRef &IR) const;
void notifyInstructionReady(const InstRef &IR) const;
void notifyResourceAvailable(const ResourceRef &RR) const;
diff --git a/include/llvm/MCA/Stages/InstructionTables.h b/include/llvm/MCA/Stages/InstructionTables.h
index 34e338f0ce6b..4b463c9b51c1 100644
--- a/include/llvm/MCA/Stages/InstructionTables.h
+++ b/include/llvm/MCA/Stages/InstructionTables.h
@@ -1,9 +1,8 @@
//===--------------------- InstructionTables.h ------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/Stages/MicroOpQueueStage.h b/include/llvm/MCA/Stages/MicroOpQueueStage.h
new file mode 100644
index 000000000000..50a5ef87b2d2
--- /dev/null
+++ b/include/llvm/MCA/Stages/MicroOpQueueStage.h
@@ -0,0 +1,88 @@
+//===---------------------- MicroOpQueueStage.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
+///
+/// This file defines a stage that implements a queue of micro opcodes.
+/// It can be used to simulate a hardware micro-op queue that serves opcodes to
+/// the out of order backend.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_MCA_MICRO_OP_QUEUE_STAGE_H
+#define LLVM_MCA_MICRO_OP_QUEUE_STAGE_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/MCA/Stages/Stage.h"
+
+namespace llvm {
+namespace mca {
+
+/// A stage that simulates a queue of instruction opcodes.
+class MicroOpQueueStage : public Stage {
+ SmallVector<InstRef, 8> Buffer;
+ unsigned NextAvailableSlotIdx;
+ unsigned CurrentInstructionSlotIdx;
+
+ // Limits the number of instructions that can be written to this buffer every
+ // cycle. A value of zero means that there is no limit to the instruction
+ // throughput in input.
+ const unsigned MaxIPC;
+ unsigned CurrentIPC;
+
+ // Number of entries that are available during this cycle.
+ unsigned AvailableEntries;
+
+ // True if instructions dispatched to this stage don't need to wait for the
+ // next cycle before moving to the next stage.
+ // False if this buffer acts as a one cycle delay in the execution pipeline.
+ bool IsZeroLatencyStage;
+
+ MicroOpQueueStage(const MicroOpQueueStage &Other) = delete;
+ MicroOpQueueStage &operator=(const MicroOpQueueStage &Other) = delete;
+
+ // By default, an instruction consumes a number of buffer entries equal to its
+ // number of micro opcodes (see field `InstrDesc::NumMicroOpcodes`). The
+ // number of entries consumed by an instruction is normalized to the
+ // minimum value between NumMicroOpcodes and the buffer size. This is to avoid
+ // problems with (microcoded) instructions that generate a number of micro
+ // opcodes than doesn't fit in the buffer.
+ unsigned getNormalizedOpcodes(const InstRef &IR) const {
+ unsigned NormalizedOpcodes =
+ std::min(static_cast<unsigned>(Buffer.size()),
+ IR.getInstruction()->getDesc().NumMicroOps);
+ return NormalizedOpcodes ? NormalizedOpcodes : 1U;
+ }
+
+ Error moveInstructions();
+
+public:
+ MicroOpQueueStage(unsigned Size, unsigned IPC = 0,
+ bool ZeroLatencyStage = true);
+
+ bool isAvailable(const InstRef &IR) const override {
+ if (MaxIPC && CurrentIPC == MaxIPC)
+ return false;
+ unsigned NormalizedOpcodes = getNormalizedOpcodes(IR);
+ if (NormalizedOpcodes > AvailableEntries)
+ return false;
+ return true;
+ }
+
+ bool hasWorkToComplete() const override {
+ return AvailableEntries != Buffer.size();
+ }
+
+ Error execute(InstRef &IR) override;
+ Error cycleStart() override;
+ Error cycleEnd() override;
+};
+
+} // namespace mca
+} // namespace llvm
+
+#endif // LLVM_MCA_MICRO_OP_QUEUE_STAGE_H
diff --git a/include/llvm/MCA/Stages/RetireStage.h b/include/llvm/MCA/Stages/RetireStage.h
index 2051ce5c86ad..08c216ac7bf4 100644
--- a/include/llvm/MCA/Stages/RetireStage.h
+++ b/include/llvm/MCA/Stages/RetireStage.h
@@ -1,9 +1,8 @@
//===---------------------- RetireStage.h -----------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/Stages/Stage.h b/include/llvm/MCA/Stages/Stage.h
index fc7ab569bb0f..46b242caa6cf 100644
--- a/include/llvm/MCA/Stages/Stage.h
+++ b/include/llvm/MCA/Stages/Stage.h
@@ -1,9 +1,8 @@
//===---------------------- Stage.h -----------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
diff --git a/include/llvm/MCA/Support.h b/include/llvm/MCA/Support.h
index 7b0c5bf3a486..1da097c90922 100644
--- a/include/llvm/MCA/Support.h
+++ b/include/llvm/MCA/Support.h
@@ -1,9 +1,8 @@
//===--------------------- Support.h ----------------------------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
@@ -61,24 +60,13 @@ public:
return (Denominator == 1) ? Numerator : (double)Numerator / Denominator;
}
+ unsigned getNumerator() const { return Numerator; }
+ unsigned getDenominator() const { return Denominator; }
+
// Add the components of RHS to this instance. Instead of calculating
// the final value here, we keep track of the numerator and denominator
// separately, to reduce floating point error.
- ResourceCycles &operator+=(const ResourceCycles &RHS) {
- if (Denominator == RHS.Denominator)
- Numerator += RHS.Numerator;
- else {
- // Create a common denominator for LHS and RHS by calculating the least
- // common multiple from the GCD.
- unsigned GCD = GreatestCommonDivisor64(Denominator, RHS.Denominator);
- unsigned LCM = (Denominator * RHS.Denominator) / GCD;
- unsigned LHSNumerator = Numerator * (LCM / Denominator);
- unsigned RHSNumerator = RHS.Numerator * (LCM / RHS.Denominator);
- Numerator = LHSNumerator + RHSNumerator;
- Denominator = LCM;
- }
- return *this;
- }
+ ResourceCycles &operator+=(const ResourceCycles &RHS);
};
/// Populates vector Masks with processor resource masks.
@@ -106,6 +94,13 @@ public:
void computeProcResourceMasks(const MCSchedModel &SM,
MutableArrayRef<uint64_t> Masks);
+// Returns the index of the highest bit set. For resource masks, the position of
+// the highest bit set can be used to construct a resource mask identifier.
+inline unsigned getResourceStateIndex(uint64_t Mask) {
+ assert(Mask && "Processor Resource Mask cannot be zero!");
+ return (std::numeric_limits<uint64_t>::digits - countLeadingZeros(Mask)) - 1;
+}
+
/// Compute the reciprocal block throughput from a set of processor resource
/// cycles. The reciprocal block throughput is computed as the MAX between:
/// - NumMicroOps / DispatchWidth
generated by cgit v1.3 (git 2.53.0) at 2026-07-25 07:33:24 +0000