llvm-mca: Disentangle `MemoryGroup` from `LSUnitBase` (#114159)

In MCA, the load/store unit is modeled through a `LSUnitBase` class.
Judging from the name `LSUnitBase`, I believe there is an intent

llvm-mca: Disentangle `MemoryGroup` from `LSUnitBase` (#114159)

In MCA, the load/store unit is modeled through a `LSUnitBase` class.
Judging from the name `LSUnitBase`, I believe there is an intent to
allow for different specialized load/store unit implementations.
(However, currently there is only one implementation used in-tree,
`LSUnit`.)

PR #101534 fixed one instance where the specialized `LSUnit` was
hard-coded, opening the door for other subclasses to be used, but what
subclasses can do is, in my opinion, still overly limited due to a
reliance on the `MemoryGroup` class, e.g.
[here](https://github.com/llvm/llvm-project/blob/8b55162e195783dd27e1c69fb4d97971ef76725b/llvm/lib/MCA/HardwareUnits/Scheduler.cpp#L88).

The `MemoryGroup` class is currently used in the default `LSUnit`
implementation to model data dependencies/hazards in the pipeline.
`MemoryGroups` form a graph of memory dependencies that inform the
scheduler when load/store instructions can be executed relative to each
other.

In my eyes, this is an implementation detail. Other `LSUnit`s may want
to keep track of data dependencies in different ways. As a concrete
example, a downstream use I am working on^[1] uses a custom
load/store unit that makes use of available aliasing information. I
haven't been able to shoehorn our additional aliasing information into
the existing `MemoryGroup` abstraction. I think there is no need to
force subclasses to use `MemoryGroup`s; users of `LSUnitBase` are only
concerned with when, and for how long, a load/store instruction
executes.

This PR makes changes to instead leave it up to the subclasses how to
model such dependencies, and only prescribes an abstract interface in
`LSUnitBase`. It also moves data members and methods that are not
necessary to provide an abstract interface from `LSUnitBase` to the
`LSUnit` subclass. I decided to make the `MemoryGroup` a protected
subclass of `LSUnit`; that way, specializations may inherit from
`LSUnit` and still make use of `MemoryGroup`s if they wish to do so
(e.g. if they want to only overwrite the `dispatch` method).

**Drawbacks / Considerations**

My reason for suggesting this PR is an out-of-tree use. As such, these
changes don't introduce any new functionality for in-tree LLVM uses.
However, in my opinion, these changes improve code clarity and prescribe
a clear interface, which would be the main benefit for the LLVM
community.

A drawback of the more abstract interface is that virtual dispatching is
used in more places. However, note that virtual dispatch is already
currently used in some critical parts of the `LSUnitBase`, e.g. the
`isAvailable` and `dispatch` methods. As a quick check to ensure these
changes don't significantly negatively impact performance, I also ran
`time llvm-mca -mtriple=x86_64-unknown-unknown -mcpu=btver2
-iterations=3000 llvm/test/tools/llvm-mca/X86/BtVer2/dot-product.s`
before and after the changes; there was no observable difference in
runtimes (`0.292 s` total before, `0.286 s` total after changes).

^{[1]: MCAD started by @mshockwave and @chinmaydd.}

show more ...

[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics

D150312 added a TODO:

TODO: consider renaming the field `StartAtCycle` and `Cycles` to
`AcquireAtCycle` and `ReleaseAtCycle` r

[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics

D150312 added a TODO:

TODO: consider renaming the field `StartAtCycle` and `Cycles` to
`AcquireAtCycle` and `ReleaseAtCycle` respectively, to stress the
fact that resource allocation is now represented as an interval,
relatively to the issue cycle of the instruction.

This patch implements that TODO. This naming clarifies how to use these
fields in the scheduler. In addition it was confusing that `StartAtCycle` was
singular but `Cycles` was plural. This renaming fixes this inconsistency.

This commit as previously reverted since it missed renaming that came
down after rebasing. This version of the commit fixes those problems.

Differential Revision: https://reviews.llvm.org/D158568

show more ...

Revert "[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics"

This reverts commit 5b854f2c23ea1b000cb4cac4c0fea77326c03d43.

Build still failing.

[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics

D150312 added a TODO:

TODO: consider renaming the field `StartAtCycle` and `Cycles` to
`AcquireAtCycle` and `ReleaseAtCycle` r

[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics

D150312 added a TODO:

TODO: consider renaming the field `StartAtCycle` and `Cycles` to
`AcquireAtCycle` and `ReleaseAtCycle` respectively, to stress the
fact that resource allocation is now represented as an interval,
relatively to the issue cycle of the instruction.

This patch implements that TODO. This naming clarifies how to use these
fields in the scheduler. In addition it was confusing that `StartAtCycle` was
singular but `Cycles` was plural. This renaming fixes this inconsistency.

This commit as previously reverted since it missed renaming that came
down after rebasing. This version of the commit fixes those problems.

Differential Revision: https://reviews.llvm.org/D158568

show more ...

Revert "[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics"

This reverts commit 030d33409568b2f0ea61116e83fd40ca27ba33ac.

This commit is causing build failures

[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics

D150312 added a TODO:

TODO: consider renaming the field `StartAtCycle` and `Cycles` to
`AcquireAtCycle` and `ReleaseAtCycle` r

[TableGen] Rename ResourceCycles and StartAtCycle to clarify semantics

D150312 added a TODO:

TODO: consider renaming the field `StartAtCycle` and `Cycles` to
`AcquireAtCycle` and `ReleaseAtCycle` respectively, to stress the
fact that resource allocation is now represented as an interval,
relatively to the issue cycle of the instruction.

This patch implements that TODO. This naming clarifies how to use these
fields in the scheduler. In addition it was confusing that `StartAtCycle` was
singular but `Cycles` was plural. This renaming fixes this inconsistency.

Differential Revision: https://reviews.llvm.org/D158568

show more ...

[llvm] Use llvm::append_range (NFC)

[llvm] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
of

[llvm] Migrate llvm::make_unique to std::make_unique

Now that we've moved to C++14, we no longer need the llvm::make_unique
implementation from STLExtras.h. This patch is a mechanical replacement
of (hopefully) all the llvm::make_unique instances across the monorepo.

llvm-svn: 369013

show more ...

[MCA] Slightly refactor class RetireControlUnit, and add the ability to override the mask of used buffered resources in class mca::Instruction. NFCI

This patch teaches the RCU how to peek 'next' RCU

[MCA] Slightly refactor class RetireControlUnit, and add the ability to override the mask of used buffered resources in class mca::Instruction. NFCI

This patch teaches the RCU how to peek 'next' RCUTokens. A new method has been
added to the RetireControlUnit class with the goal of minimizing the complexity
of follow-up patches that will enable macro-fusion support in mca.

This patch also adds method Instruction::getNumMicroOpcodes() to simplify common
interactions with the instruction descriptor (a pattern quite common in some
pipeline stages).

Added the ability to override the default set of consumed scheduler resources
(this -again- is to simplify future patches that add support for macro-op fusion).

No functional change intended.

llvm-svn: 369010

show more ...

[MCA] Slightly refactor the logic in ResourceManager. NFCI

This patch slightly changes the API in the attempt to simplify resource buffer
queries. It is done in preparation for a patch that will ena

[MCA] Slightly refactor the logic in ResourceManager. NFCI

This patch slightly changes the API in the attempt to simplify resource buffer
queries. It is done in preparation for a patch that will enable support for
macro fusion.

llvm-svn: 368994

show more ...

[MCA] Further refactor the bottleneck analysis view. NFCI.

llvm-svn: 362933

[MCA][Scheduler] Change how memory instructions are dispatched to the pending set. NFCI

llvm-svn: 362302

[MCA] Refactor class LSUnit. NFCI

This should be the last bit of refactoring in preparation for a patch that would
finally fix PR37494.

This patch introduces the concept of memory dependency groups

[MCA] Refactor class LSUnit. NFCI

This should be the last bit of refactoring in preparation for a patch that would
finally fix PR37494.

This patch introduces the concept of memory dependency groups (class
MemoryGroup) and "Load/Store Unit token" (LSUToken) to track the status of a
memory operation.

A MemoryGroup is a node of a memory dependency graph. It is used internally to
classify memory operations based on the memory operations they depend on. Let I
and J be two memory operations, we say that I and J equivalent (for the purpose
of mapping instructions to memory dependency groups) if the set of memory
operations they depend depend on is identical.

MemoryGroups are identified by so-called LSUToken (a unique group identifier
assigned by the LSUnit to every group). When an instruction I is dispatched to
the LSUnit, the LSUnit maps I to a group, and then returns a LSUToken.
LSUTokens are used by class Scheduler to track memory dependencies.

This patch simplifies the LSUnit interface and moves most of the implementation
details to its base class (LSUnitBase). There is no user visible change to the
output.

llvm-svn: 361950

show more ...

[MCA][Scheduler] Improved critical memory dependency computation.

This fixes a problem where back-pressure increases caused by register
dependencies were not correctly notified if execution was also

[MCA][Scheduler] Improved critical memory dependency computation.

This fixes a problem where back-pressure increases caused by register
dependencies were not correctly notified if execution was also delayed by memory
dependencies.

llvm-svn: 361740

show more ...

[MCA] Refactor the logic that computes the critical memory dependency info. NFCI

CriticalRegDep has been renamed CriticalDependency, and it is now used by class
Instruction to store information abou

[MCA] Refactor the logic that computes the critical memory dependency info. NFCI

CriticalRegDep has been renamed CriticalDependency, and it is now used by class
Instruction to store information about the critical register dependency and the
critical memory dependency. No functional change intendend.

llvm-svn: 361737

show more ...

[MCA] Introduce class LSUnitBase and let LSUnit derive from it.

Class LSUnitBase provides a abstract interface for all the concrete LS units in
llvm-mca.

Methods exposed by the public abstract LSUn

[MCA] Introduce class LSUnitBase and let LSUnit derive from it.

Class LSUnitBase provides a abstract interface for all the concrete LS units in
llvm-mca.

Methods exposed by the public abstract LSUnitBase interface are:
- Status isAvailable(const InstRef&);
- void dispatch(const InstRef &);
- const InstRef &isReady(const InstRef &);

LSUnitBase standardises the API, but not the data structures internally used by
LS units. This allows for more flexibility.
Previously, only method `isReady()` was declared virtual by class LSUnit.
Also, derived classes had to inherit all the internal data members of LSUnit.

No functional change intended.

llvm-svn: 361496

show more ...

[MCA] Notify event listeners when instructions transition to the Pending state. NFCI

llvm-svn: 359983

[MCA] Highlight kernel bottlenecks in the summary view.

This patch adds a new flag named -bottleneck-analysis to print out information
about throughput bottlenecks.

MCA knows how to identify and cl

[MCA] Highlight kernel bottlenecks in the summary view.

This patch adds a new flag named -bottleneck-analysis to print out information
about throughput bottlenecks.

MCA knows how to identify and classify dynamic dispatch stalls. However, it
doesn't know how to analyze and highlight kernel bottlenecks. The goal of this
patch is to teach MCA how to correlate increases in backend pressure to backend
stalls (and therefore, the loss of throughput).

From a Scheduler point of view, backend pressure is a function of the scheduler
buffer usage (i.e. how the number of uOps in the scheduler buffers changes over
time). Backend pressure increases (or decreases) when there is a mismatch
between the number of opcodes dispatched, and the number of opcodes issued in
the same cycle. Since buffer resources are limited, continuous increases in
backend pressure would eventually leads to dispatch stalls. So, there is a
strong correlation between dispatch stalls, and how backpressure changed over
time.

This patch teaches how to identify situations where backend pressure increases
due to:
- unavailable pipeline resources.
- data dependencies.

Data dependencies may delay execution of instructions and therefore increase the
time that uOps have to spend in the scheduler buffers. That often translates to
an increase in backend pressure which may eventually lead to a bottleneck.
Contention on pipeline resources may also delay execution of instructions, and
lead to a temporary increase in backend pressure.

Internally, the Scheduler classifies instructions based on whether register /
memory operands are available or not.

An instruction is marked as "ready to execute" only if data dependencies are
fully resolved.
Every cycle, the Scheduler attempts to execute all instructions that are ready
to execute. If an instruction cannot execute because of unavailable pipeline
resources, then the Scheduler internally updates a BusyResourceUnits mask with
the ID of each unavailable resource.

ExecuteStage is responsible for tracking changes in backend pressure. If backend
pressure increases during a cycle because of contention on pipeline resources,
then ExecuteStage sends a "backend pressure" event to the listeners.
That event would contain information about instructions delayed by resource
pressure, as well as the BusyResourceUnits mask.

Note that ExecuteStage also knows how to identify situations where backpressure
increased because of delays introduced by data dependencies.

The SummaryView observes "backend pressure" events and prints out a "bottleneck
report".

Example of bottleneck report:

```
Cycles with backend pressure increase [ 99.89% ]
Throughput Bottlenecks:
Resource Pressure [ 0.00% ]
Data Dependencies: [ 99.89% ]
- Register Dependencies [ 0.00% ]
- Memory Dependencies [ 99.89% ]
```

A bottleneck report is printed out only if increases in backend pressure
eventually caused backend stalls.

About the time complexity:

Time complexity is linear in the number of instructions in the
Scheduler::PendingSet.

The average slowdown tends to be in the range of ~5-6%.
For memory intensive kernels, the slowdown can be significant if flag
-noalias=false is specified. In the worst case scenario I have observed a
slowdown of ~30% when flag -noalias=false was specified.

We can definitely recover part of that slowdown if we optimize class LSUnit (by
doing extra bookkeeping to speedup queries). For now, this new analysis is
disabled by default, and it can be enabled via flag -bottleneck-analysis. Users
of MCA as a library can enable the generation of pressure events through the
constructor of ExecuteStage.

This patch partially addresses https://bugs.llvm.org/show_bug.cgi?id=37494

Differential Revision: https://reviews.llvm.org/D58728

llvm-svn: 355308

show more ...

[MCA] Always check if scheduler resources are unavailable when reporting dispatch stalls.

Dispatch stall cycles may be associated to multiple dispatch stall events.
Before this patch, each stall cyc

[MCA] Always check if scheduler resources are unavailable when reporting dispatch stalls.

Dispatch stall cycles may be associated to multiple dispatch stall events.
Before this patch, each stall cycle was associated with a single stall event.
This patch also improves a couple of code comments, and adds a helper method to
query the Scheduler for dispatch stalls.

llvm-svn: 354877

show more ...

[MCA][Scheduler] Collect resource pressure and memory dependency bottlenecks.

Every cycle, the Scheduler checks if instructions in the ReadySet can be issued
to the underlying pipelines. If an instr

[MCA][Scheduler] Collect resource pressure and memory dependency bottlenecks.

Every cycle, the Scheduler checks if instructions in the ReadySet can be issued
to the underlying pipelines. If an instruction cannot be issued because one or
more pipeline resources are unavailable, then field
Instruction::CriticalResourceMask is updated with the resource identifier of the
unavailable resources.

If an instruction cannot be promoted from the PendingSet to the ReadySet because
of a memory dependency, then field Instruction::CriticalMemDep is updated with
the identifier of the dependending memory instruction.

Bottleneck information is collected after every cycle for instructions that are
waiting to execute. The idea is to help identify causes of bottlenecks; this
information can be used in future to implement a bottleneck analysis.

llvm-svn: 354490

show more ...

[MCA] Slightly refactor method writeStartEvent in WriteState and ReadState. NFCI

This is another change in preparation for PR37494.
No functional change intended.

llvm-svn: 354261

[MCA][LSUnit] Return the ID of the dependent memory operation from method
isReady(). NFCI

This is yet another change in preparation for a fix for PR37494.

llvm-svn: 354150

[MCA][Scheduler] Use latency information to further classify busy instructions.

This patch introduces a new instruction stage named 'IS_PENDING'.
An instruction transitions from the IS_DISPATCHED to

[MCA][Scheduler] Use latency information to further classify busy instructions.

This patch introduces a new instruction stage named 'IS_PENDING'.
An instruction transitions from the IS_DISPATCHED to the IS_PENDING stage if
input registers are not available, but their latency is known.

This patch also adds a new set of instructions named 'PendingSet' to class
Scheduler. The idea is that the PendingSet will only contain instructions that
have reached the IS_PENDING stage.
By construction, an instruction in the PendingSet is only dependent on
instructions that have already reached the execution stage. The plan is to use
this knowledge to identify bottlenecks caused by data dependencies (see
PR37494).

Differential Revision: https://reviews.llvm.org/D58066

llvm-svn: 353937

show more ...

[MCA][Scheduler] Track resources that were found busy when issuing an instruction.

This is a follow up of r353706. When the scheduler fails to issue a ready
instruction to the underlying pipelines,

[MCA][Scheduler] Track resources that were found busy when issuing an instruction.

This is a follow up of r353706. When the scheduler fails to issue a ready
instruction to the underlying pipelines, it now updates a mask of 'busy resource
units'. That information will be used in future to obtain the set of
"problematic" resources in the case of bottlenecks caused by resource pressure.
No functional change intended.

llvm-svn: 353728

show more ...

[MCA] Return a mask of busy resources from method ResourceManager::checkAvailability(). NFCI

In case of bottlenecks caused by pipeline pressure, we want to be able to
correctly report the set of pro

[MCA] Return a mask of busy resources from method ResourceManager::checkAvailability(). NFCI

In case of bottlenecks caused by pipeline pressure, we want to be able to
correctly report the set of problematic pipelines. This is a first step towards
adding support for bottleneck hints in llvm-mca (see PR37494). No functional
change intended.

llvm-svn: 353706

show more ...