[CodeGen][MISched] Rename instance of Cycle -> ReleaseAtCycle

b1ae461a5358932851de42b66ffde8748da51a83 renamed Cycle ->
ReleaseAtCycle.

7e09239e24b339f45f63a670e2e831150826bf70 was committed withou

[CodeGen][MISched] Rename instance of Cycle -> ReleaseAtCycle

b1ae461a5358932851de42b66ffde8748da51a83 renamed Cycle ->
ReleaseAtCycle.

7e09239e24b339f45f63a670e2e831150826bf70 was committed without rebasing
but used the old Cycle syntax.

This caused a build failure when
7e09239e24b339f45f63a670e2e831150826bf70 was squash-and-merged. This
patch fixes this problem.

show more ...

[CodeGen][MISched] Handle empty sized resource usage. (#75951)

TargetSchedule.td explicitly allows the usage of a ProcResource for zero
cycles, in order to represent that the ProcResource must be a

[CodeGen][MISched] Handle empty sized resource usage. (#75951)

TargetSchedule.td explicitly allows the usage of a ProcResource for zero
cycles, in order to represent that the ProcResource must be available
but is not consumed by the instruction. On the other hand,
ResourceSegments explicitly does not allow for a zero sized interval. In
order to remedy this, this patch handles the special case of when there
is an empty interval usage of a resource by not adding an empty
interval.

We ran into this issue downstream, but it makes sense to have
this upstream since it is explicitly allowed by TargetSchedule.td.

show more ...

[CodeGen][MISched][NFC] Rename some instances of Cycle -> ReleaseAtCycle

This is to match the naming of arguments in MachineScheduler.h

[MachineScheduler] Add option to control reordering for store/load clustering (#75338)

Reordering based on the sort order of the MemOpInfo array was disabled
in <https://reviews.llvm.org/D72706>. H

[MachineScheduler] Add option to control reordering for store/load clustering (#75338)

Reordering based on the sort order of the MemOpInfo array was disabled
in <https://reviews.llvm.org/D72706>. However, it's not clear this is
desirable for al targets. It also makes it more difficult to compare the
incremental benefit of enabling load clustering in the selectiondag
scheduler as well was the machinescheduler, as the sdag scheduler does
seem to allow this reordering.

This patch adds a parameter that can control the behaviour on a
per-target basis.

Split out from #73789.

show more ...

[CodeGen][MachineScheduler][NFC]Update some comments of scheduler (#74705)

The member functions of ScheduleDAGMI are called back from
PostMachineScheduler::runOnMachineFunction, instead of
Machine

[CodeGen][MachineScheduler][NFC]Update some comments of scheduler (#74705)

The member functions of ScheduleDAGMI are called back from
PostMachineScheduler::runOnMachineFunction, instead of
MachineScheduler::runOnMachineFunction.

show more ...

[MachineScheduler][NFCI] Add Offset and OffsetIsScalable args to shouldClusterMemOps (#73778)

These are picked up from getMemOperandsWithOffsetWidth but weren't then
being passed through to shouldC

[MachineScheduler][NFCI] Add Offset and OffsetIsScalable args to shouldClusterMemOps (#73778)

These are picked up from getMemOperandsWithOffsetWidth but weren't then
being passed through to shouldClusterMemOps, which forces backends to
collect the information again if they want to use the kind of heuristics
typically used for the similar shouldScheduleLoadsNear function (e.g.
checking the offset is within 1 cache line).

This patch just adds the parameters, but doesn't attempt to use them.
There is potential to use them in the current PPC and AArch64
shouldClusterMemOps implementation, and I intend to use the offset in
the heuristic for RISC-V. I've left these for future patches in the
interest of being as incremental as possible.

As noted in the review and in an inline FIXME, an ElementCount-style abstraction may later be used to condense these two parameters to one argument. ElementCount isn't quite suitable as it doesn't support negative offsets.

show more ...

[llvm] Fix duplicate word typos. NFC

Those fixes were taken from https://reviews.llvm.org/D137338

[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 ...

[MISched] Do not erase resource booking history for subunits.

When dealing with the subunits of a resource group, we should reset
the subunits availability at the first avaiable cycle of the resourc

[MISched] Do not erase resource booking history for subunits.

When dealing with the subunits of a resource group, we should reset
the subunits availability at the first avaiable cycle of the resource
that contains the subunits. Previously, the reset operation was
returning cycle 0, effectively erasing the booking history of the
subunits.

Without this change, when using intervals for models have make use of
subunits, the erasing of resource booking for subunits can raise the
assertion "A resource is being overwritten" in
`ResourceSegments::add`. The test added in the patch is one of such
cases.

Reviewed By: andreadb

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

show more ...

[MISched] Fix bug(s) in bottom-up scheduling.

BUG 1 - choosing the right cycle when booking a resource.
---------------------------------------------------------

Bottom up scheduling should take in

[MISched] Fix bug(s) in bottom-up scheduling.

BUG 1 - choosing the right cycle when booking a resource.
---------------------------------------------------------

Bottom up scheduling should take in account the current cycle at
the scheduling boundary when determing at what cycle a resource can be
issued. Supposed the schedule boundary is at cycle `C`, and that we
want to check at what cycle a 3 cycles resource can be instantiated.

We have two cases: A, in which the last seen resource cycle LSRC in
which the resource is known to be used is more than oe euqual to 3
cycles away from current cycle `C`, (`C - LSRC >=3`) and B in which
the LSRC is less than 3 cycles away from C (`C - LSRC < 3`). Note
that, in bottom-up scheduling LRS is always smaller or eaual to the
current cycle `C`.

The two cases can be schematized as follow:

```
... | C + 1 | C | C - 1 | C - 2 | C - 3 | C - 4 | ...
| | | | | | LSRC | -> Case A
| | | | LSRC | | | -> Case B

// Before allocating the resource
LSRC(A) = C - 4
LSRC(B) = C - 2
```

In case A, the scheduler sees cycles `C`, `C-1` and `C-2` being
available for booking the 3-cycles resource. Therefore the LSRC can be
updated to be `C`, and the resource can be scheduled from cycle `C`
(the `X` in the table):

```
... | C + 1 | C | C - 1 | C - 2 | C - 3 | C - 4 | ...
| | X | X | X | | | -> Case A
// After allocating the resource
LSRC(A) = C
```

In case B, the 3-cycle resource usage would clash with the LSRC if
allocated starting from cycle C:

```
... | C + 1 | C | C - 1 | C - 2 | C - 3 | C - 4 | ...
| | X | X | X | | | -> clash at cycle C - 2
| | | | LSRC | | | -> Case B
```

Therefore, the cycle in which the resource can be scheduled needs to
be greater than `C`. For the example, the resource is booked
in cycle `C + 1`.

```
... | C + 1 | C | C - 1 | C - 2 | C - 3 | C - 4 | ...
| X | X | X | | | |
// After allocating the resource
LSRC(B) = C + 1
```

The behavior we need to correctly support cases A and B is obtained by
computing the next value of the LSRC as the maximum between:

1. the current cycle `C`;

2. and the previous LSRC plus the number of cycle CYCLES the resource will need.

In formula:

```
LSRC(next) = max(C, LSRC(previous) + CYCLES)
```

BUG 2 - booking the resource for the correct number of cycles.
--------------------------------------------------------------

When storing the next LSRC, the funcion `getNextResourceCycle` was
being invoked setting to 0 the number of cycles a resource was using.
The invocation of `getNextResourceCycle` is now using the values of
`Cycles` instead of 0.

Effects on code generation
--------------------------

This fix have effects only on AArch64, for the Cortex-A55
scheduling model (`-mcpu=cortex-a55`).

The changes in the MIR tests caused by this patch show that the value
now reported by `getNextResourceCycle` is correct.

Other cortex-a55 tests have been touched by this change, where some
instructions have been swapped. The final generated code is equivalent
in term of the total number of cycles. The test
`llvm/test/CodeGen/AArch64/misched-detail-resource-booking-02.mir`
shows in details the correctness of the bottom up scheduling, and the
effect on the codegen change that are visible in the test
`llvm/test/CodeGen/AArch64/aarch64-smull.ll`.

Reviewed By: andreadb, dmgreen

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

show more ...

[llc][MISched] Add `-misched-detail-resource-booking` to llc.

The option `-misched-detail-resource-booking` prints the following
information every time the method
`SchedBoundary::getNextResourceCycl

[llc][MISched] Add `-misched-detail-resource-booking` to llc.

The option `-misched-detail-resource-booking` prints the following
information every time the method
`SchedBoundary::getNextResourceCycle` is invoked:

1. counters of the resources that have already been booked;

2. the values returned by `getNextResourceCycle`, which is the next
available cycle in which a resource can be booked.

The method is useful to debug low-level checks inside the machine
scheduler that make decisions based on the values returned by
`getNextResourceCycle`.

Reviewed By: andreadb

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

show more ...

Revert "[llc][MISched] Add `-misched-detail-resource-booking` to llc."

Reverting because of https://lab.llvm.org/buildbot#builders/75/builds/32485:

llvm-project/llvm/lib/CodeGen/MachineScheduler.cp

Revert "[llc][MISched] Add `-misched-detail-resource-booking` to llc."

Reverting because of https://lab.llvm.org/buildbot#builders/75/builds/32485:

llvm-project/llvm/lib/CodeGen/MachineScheduler.cpp:2374:7: error: use of undeclared identifier 'MischedDetailResourceBooking'
if (MischedDetailResourceBooking)

This reverts commit fc06262c1c365777e71207b6a5de281cba927c96.

show more ...

[llc][MISched] Add `-misched-detail-resource-booking` to llc.

The option `-misched-detail-resource-booking` prints the following
information every time the method
`SchedBoundary::getNextResourceCycl

[llc][MISched] Add `-misched-detail-resource-booking` to llc.

The option `-misched-detail-resource-booking` prints the following
information every time the method
`SchedBoundary::getNextResourceCycle` is invoked:

1. counters of the resources that have already been booked;

2. the values returned by `getNextResourceCycle`, which is the next
available cycle in which a resource can be booked.

The method is useful to debug low-level checks inside the machine
scheduler that make decisions based on the values returned by
`getNextResourceCycle`.

Reviewed By: andreadb

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

show more ...

[MISched][scheduleDump] Use stable_sort to prevent test failures.

When building the compiler with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON,
sometimes resources that are dumped in scheduled traces gets reor

[MISched][scheduleDump] Use stable_sort to prevent test failures.

When building the compiler with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON,
sometimes resources that are dumped in scheduled traces gets reordered
even if they are booked in the same cycle. Using `stable_sort`
guarantees that such occasional reordering does not happen.

This change should fix failures like the one seen in
https://lab.llvm.org/buildbot/#/builders/16/builds/49592.

Reviewed By: RKSimon

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

show more ...

[MISched] Use StartAtCycle in trace dumps.

This commit re-work the methods that dump traces with resource usage to take into account the StartAtCycle value added by https://reviews.llvm.org/D150310.

[MISched] Use StartAtCycle in trace dumps.

This commit re-work the methods that dump traces with resource usage to take into account the StartAtCycle value added by https://reviews.llvm.org/D150310.

For each i, the values of the lists StartAtCycle and ReservedCycles is are printed with the interval [StartAtCycle[i], ReservedCycles[i])

```
... | StartAtCycle[i] | ... | ReservedCycles[i] - 1 | ReservedCycles[i] | ...
| xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx | |
```

Reviewed By: andreadb

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

show more ...

[CodeGen] Fix a warning in release builds

This patch fixes:

llvm/lib/CodeGen/MachineScheduler.cpp:4223:9: error: unused type
alias 'IntervalTy' [-Werror,-Wunused-local-typedef]

[MISched][rework] Introduce and use ResourceSegments.

Re-landing the code that was reverted because of the buildbot failure
in https://lab.llvm.org/buildbot#builders/9/builds/27319.

Original commit

[MISched][rework] Introduce and use ResourceSegments.

Re-landing the code that was reverted because of the buildbot failure
in https://lab.llvm.org/buildbot#builders/9/builds/27319.

Original commit message
======================

The class `ResourceSegments` is used to keep track of the intervals
that represent resource usage of a list of instructions that are
being scheduled by the machine scheduler.

The collection is made of intervals that are closed on the left and
open on the right (represented by the standard notation `[a, b)`).

These collections of intervals can be extended by `add`ing new
intervals accordingly while scheduling a basic block.

Unit tests are added to verify the possible configurations of
intervals, and the relative possibility of scheduling a new
instruction in these configurations. Specifically, the methods
`getFirstAvailableAtFromBottom` and `getFirstAvailableAtFromTop` are
tested to make sure that both bottom-up and top-down scheduling work
when tracking resource usage across the basic block with
`ResourceSegments`.

Note that the scheduler tracks resource usage with two methods:

1. counters (via `std::vector<unsigned> ReservedCycles;`);

2. intervals (via `std::map<unsigned, ResourceSegments> ReservedResourceSegments;`).

This patch can be considered a NFC test for existing scheduling models
because the tracking system that uses intervals is turned off by
default (field `bit EnableIntervals = false;` in the tablegen class
`SchedMachineModel`).

Reviewed By: andreadb

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

show more ...

Revert "[MISched] Introduce and use ResourceSegments."

Reverted because it produces the following builbot failure at https://lab.llvm.org/buildbot#builders/9/builds/27319:

/b/ml-opt-rel-x86-64-b1/l

Revert "[MISched] Introduce and use ResourceSegments."

Reverted because it produces the following builbot failure at https://lab.llvm.org/buildbot#builders/9/builds/27319:

/b/ml-opt-rel-x86-64-b1/llvm-project/llvm/unittests/CodeGen/SchedBoundary.cpp: In member function ‘virtual void ResourceSegments_getFirstAvailableAtFromBottom_empty_Test::TestBody()’:
/b/ml-opt-rel-x86-64-b1/llvm-project/llvm/unittests/CodeGen/SchedBoundary.cpp:395:31: error: call of overloaded ‘ResourceSegments(<brace-enclosed initializer list>)’ is ambiguous
395 | auto X = ResourceSegments({});
| ^

This reverts commit dc312f0331309692e8d6e06e93b3492b6a40989f.

show more ...

[MISched] Introduce and use ResourceSegments.

The class `ResourceSegments` is used to keep track of the intervals
that represent resource usage of a list of instructions that are
being scheduled by

[MISched] Introduce and use ResourceSegments.

The class `ResourceSegments` is used to keep track of the intervals
that represent resource usage of a list of instructions that are
being scheduled by the machine scheduler.

The collection is made of intervals that are closed on the left and
open on the right (represented by the standard notation `[a, b)`).

These collections of intervals can be extended by `add`ing new
intervals accordingly while scheduling a basic block.

Unit tests are added to verify the possible configurations of
intervals, and the relative possibility of scheduling a new
instruction in these configurations. Specifically, the methods
`getFirstAvailableAtFromBottom` and `getFirstAvailableAtFromTop` are
tested to make sure that both bottom-up and top-down scheduling work
when tracking resource usage across the basic block with
`ResourceSegments`.

Note that the scheduler tracks resource usage with two methods:

1. counters (via `std::vector<unsigned> ReservedCycles;`);

2. intervals (via `std::map<unsigned, ResourceSegments> ReservedResourceSegments;`).

This patch can be considered a NFC test for existing scheduling models
because the tracking system that uses intervals is turned off by
default (field `bit EnableIntervals = false;` in the tablegen class
`SchedMachineModel`).

Reviewed By: andreadb

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

show more ...

[CodeGen] Make use of MachineInstr::all_defs and all_uses. NFCI.

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

Restore CodeGen/MachineValueType.h from `Support`

This is rework of;

- rG13e77db2df94 (r328395; MVT)

Since `LowLevelType.h` has been restored to `CodeGen`, `MachinveValueType.h`
can be restored

Restore CodeGen/MachineValueType.h from `Support`

This is rework of;

- rG13e77db2df94 (r328395; MVT)

Since `LowLevelType.h` has been restored to `CodeGen`, `MachinveValueType.h`
can be restored as well.

Depends on D148767

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

show more ...