- This patch detects cycles by phis and bails out if one is found.
- It prevents to violate DAG restrictions.

Abort pipelining in the below case

%1 = phi i32 [ %a, %entry ], [ %3, %loop ]
%2 = phi i32 [ %a, %entry ], [ %1, %loop ]
%3 = phi i32 [ %b, %entry ], [ %2, %loop ]

---------

Co-authored-by: Ryotaro Kasuga <kasuga.ryotaro@fujitsu.com>

Use it in `printVRegOrUnit()`, `getPressureSets()`/`PSetIterator`,
and in functions/classes dealing with register pressure.

Static type checking revealed several bugs, mainly in MachinePipeliner.
I'm not very familiar with this pass, so I left a bunch of FIXMEs.

There is one bug in `findUseBetween()` in RegisterPressure.cpp, also
annotated with a FIXME.

The dependency analysis in MachinePipeliner checks dependencies for
every pair of store instructions in the target basic block. This means
the time complexity of the analysis is `O(N^2)`, where `N` is the number
of store instructions. Therefore, compilation time can become
significantly long when there are too many store instructions.

To mitigate it, this patch introduces logic to count the number of store
instructions at the beginning of the pipeliner and bail out if it
exceeds the threshold. The default value if the threshold should be
large enough. Thus, in most practical cases where the pipeliner is
beneficial, this patch should not cause any performance regression.

Related issue: #150262

This patch replaces SmallSet<T *, N> with SmallPtrSet<T *, N>.  Note
that SmallSet.h "redirects" SmallSet to SmallPtrSet for pointer
element types:

  template <typename PointeeType, unsigned N>
class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N>
{};

We only have 140 instances that rely on this "redirection", with the
vast majority of them under llvm/. Since relying on the redirection
doesn't improve readability, this patch replaces SmallSet with
SmallPtrSet for pointer element types.

This patch fixes a bug introduced in #145878. A dependency was added in
the wrong direction, causing an assertion failure due to broken
topological order.

This patch adds an additional validation step to ensure that the
generated schedule does not violate loop-carried memory dependencies.
Prior to this patch, incorrect schedules could be produced due to the
lack of checks for the following types of dependencies:

- load-to-store backward (from bottom to top within the BB) dependencies
- store-to-load dependencies
- store-to-store dependencies

One possible solution to this issue is to add these dependencies
directly to the dependency graph, although doing so may lead to
performance degradation. In addition, no known cases of incorrect code
generation caused by these missing dependencies have been observed in
practice. Given these factors, this patch introduces a post-scheduling
validation phase to check for such previously missed dependencies,
instead of adding them to the graph before searching for a schedule.
Since no actual problems have been identified so far, it is likely that
most generated schedules are already valid. Therefore, this additional
validation is not expected to cause performance degradation in practice.

Split off from #135148 .

The remaining tasks are as follows:

- Address other missing loop-carried dependencies (e.g., output
dependencies between physical registers, barrier instructions, and
instructions that may raise floating-point exceptions)
- Remove code that are currently retained to maintain the existing
behavior but probably unnecessary.
- Eliminate `SwingSchedulerDAG::isLoopCarriedDep` and use
`SwingSchedulerDDG` to traverse edges after dependency analysis part.

In MachinePipeliner, loop-carried memory dependencies are represented by
DAG, which makes things complicated and causes some necessary
dependencies to be missing. This patch introduces a new class to manage
loop-carried memory dependencies to simplify the logic. The ultimate
goal is to add currently missing dependencies, but this is a first step
of that, and this patch doesn't intend to change current behavior. This
patch also adds new tests that show the missed dependencies, which
should be fixed in the future.

Split off from #135148

These are identified by misc-include-cleaner.  I've filtered out those
that break builds.  Also, I'm staying away from llvm-config.h,
config.h, and Compiler.h, which likely cause platform- or
compiler-specific build failures.

This patch moves a process in `addLoopCarriedDependences` that checks
for a loop-carried dependency between two instructions to another
function. This patch is preliminary to a later patch and is not intended
to change current behavior.

Split off from #135148