dependencies in same cycle

Dependency checks were insufficient when reordering instructions with
physical register dependencies (i.e. Anti/Output dependencies). This
could result in generating incorrect code.

Added a new restriction for window scheduling.
Window scheduling is disabled when llvm.loop.pipeline.initiationinterval
is set.

- Add `LiveIntervalsAnalysis`.
- Add `LiveIntervalsPrinterPass`.
- Use `LiveIntervalsWrapperPass` in legacy pass manager.
- Use `std::unique_ptr` instead of raw pointer for `LICalc`, so
destructor and default move constructor can handle it correctly.

This would be the last analysis required by `PHIElimination`.

- Add `MachineLoopAnalysis`.
- Add `MachineLoopPrinterPass`.
- Convert to `MachineLoopInfoWrapperPass` in legacy pass manager.

…ain cases" (#97246)

This reverts commit e6a961dbef773b16bda2cebc4bf9f3d1e0da42fc.

There is no difference from the original change. I re-ran the failed
test and it passed. So the failure wasn't caused by this change.
test result: https://lab.llvm.org/buildbot/#/builders/176/builds/585

Reverts llvm/llvm-project#95356

Due to ppc64le test failures caught by the LLVM Buildbot.
https://lab.llvm.org/buildbot/#/builders/176/builds/576

when scheduling

When scheduling an instruction, if both any predecessors and any
successors of the instruction are already scheduled, `SchedStart` isn't
taken into account. It may result generating incorrect code. This patch
fixes the problem. Also, this patch merges `SchedStart` into
`EarlyStart` (same for `SchedEnd`).

Fixes https://github.com/llvm/llvm-project/issues/93936

This commit implements the Window Scheduler as described in the RFC:

https://discourse.llvm.org/t/rfc-window-scheduling-algorithm-for-machinepipeliner-in-llvm/74718

This Window Scheduler implements the window algorithm designed by
Steven Muchnick in the book "Advanced Compiler Design And
Implementation",
with some improvements:

1. Copy 3 times of the loop kernel and construct the corresponding DAG
   to identify dependencies between MIs;
2. Use heuristic algorithm to obtain a set of window offsets.

The window algorithm is equivalent to modulo scheduling algorithm with a
stage of 2. It is mainly applied in targets where hardware resource
conflicts are severe, and the SMS algorithm often fails in such cases.
On our own DSA, this window algorithm typically can achieve a
performance
improvement of over 10%.

Co-authored-by: Kai Yan <aklkaiyan@tencent.com>
Co-authored-by: Ran Xiao <lennyxiao@tencent.com>

---------

Co-authored-by: Kai Yan <aklkaiyan@tencent.com>
Co-authored-by: Ran Xiao <lennyxiao@tencent.com>

Modulo variable expansion is a technique that resolves overlap of
variable lifetimes by unrolling. The existing implementation solves it
by making a copy by move instruction for processors with ordinary
registers such as Arm and x86. This method may result in a very large
number of move instructions, which can cause performance problems.

Modulo variable expansion is enabled by specifying -pipeliner-mve-cg. A
backend must implement some newly defined interfaces in
PipelinerLoopInfo. They were implemented for AArch64.

Discourse thread:
https://discourse.llvm.org/t/implementing-modulo-variable-expansion-for-machinepipeliner