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 - 2In 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) = CIn 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 BTherefore, 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 + 1The behavior we need to correctly support cases A and B is obtained by
computing the next value of the LSRC as the maximum between:
- the current cycle C;
- 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.