Do not consider loops with a zero backedge taken count as candidates for
interchange. This seems like a sensible thing because it suggests the loop
doesn't execute and there is no point in interchanging. As a bonus, this
seems to avoid triggering an assert about phis and their uses from source
code, so this is a partial fix for #163954 but it needs more work to properly
fix that.

This deals with a corner case of LCSSA phi nodes in the outer loop latch
block: the loop was in LCSSA form, some transformations can come along
(e.g. unswitch) and create an empty block:

     BB4:
       br label %BB5
     BB5:
       %old.cond.lcssa = phi i16 [ %cond, %BB4 ]
       br outer.header

Interchange then brings it in LCSSA form again and we get:

     BB4:
       %new.cond.lcssa = phi i16 [ %cond, %BB3 ]
       br label %BB5
     BB5:
       %old.cond.lcssa = phi i16 [ %new.cond.lcssa, %BB4 ]

Which means that we have a chain of LCSSA phi nodes from %new.cond.lcssa
to %old.cond.lcssa. The problem is that interchange can reoder blocks
BB4 and BB5 placing the use before the def if we don't check this. The
solution is to simplify lcssa phis, and remove them from non-exit blocks
if they are 1-input phi nodes.

Fixes #160068

If a direction vector with all `*` elements, like `[* * *]`, is present,
it indicates that none of the loop pairs are legal to interchange. In
such cases, continuing the analysis is meaningless.
This patch introduces a check to detect such direction vectors and exits
early when one is found. This slightly reduces compile time.

The vectorization heuristic of LoopInterchange attempts to move a
vectorizable loop to the innermost position. Before this patch, a loop
was deemed vectorizable if there are no loop-carried dependencies
induced by the loop.
This patch extends the vectorization heuristic by introducing the
concept of forward and backward dependencies, inspired by
LoopAccessAnalysis. Specifically, an additional element is appended to
each direction vector to indicate whether it represents a forward
dependency (`<`) or not (`*`). Among these, only the forward
dependencies (i.e., those whose last element is `<`) affect the
vectorization heuristic. Accordingly, the check is conservative, and
dependencies are considered forward only when this can be proven.
Currently, we only support perfectly nested loops whose body consists of
a single basic block. For other cases, dependencies are pessimistically
treated as non-forward.

This is and has been proven useful for testing purposes, to get more
test coverage.

This patch fixes:

  llvm/lib/Transforms/Scalar/LoopInterchange.cpp:863:20: error: unused
  variable 'OpCode' [-Werror,-Wunused-variable]

Before this patch, when a reduction exists in the loop, the legality
check of LoopInterchange only verified if there exists a
non-reassociative floating-point instruction in the reduction
calculation. However, it is insufficient, because reordering integer
reductions can also lead to incorrect transformations. Consider the
following example:

```c
int A[2][2] = {
  { INT_MAX, INT_MAX },
  { INT_MIN, INT_MIN },
};

int sum = 0;
for (int i = 0; i < 2; i++)
  for (int j = 0; j < 2; j++)
    sum += A[j][i];
```

To make this exchange legal, we must drop nuw/nsw flags from the
instructions involved in the reduction operations.

This patch extends the legality check to correctly handle such cases. In
particular, for integer addition and multiplication, it verifies that
the nsw and nuw flags are set on involved instructions, and drop them
when the transformation actually performed. This patch also introduces
explicit checks for the kind of reduction and permits only those that
are known to be safe for interchange. Consequently, some "unknown"
reductions (at the moment, `FindFirst*` and `FindLast*`) are rejected.

Fix #148228

LoopInterchange currently stop and exit its process when the number of
loads/stores in the loop is greater than `MaxMemInstrCount`. This
prevents excessive querying to DependenceAnalysis. However, computing
`CacheCost` also involves DependenceAnalysis queries, and their number
can grow to `O(N^2)` in the worst case, where `N` is the number of
loads/stores in the loop. Therefore, we should also avoid calculating it
if the loads/stores count exceeds `MaxMemInstrCount`.
This patch defers the calculation of `CacheCost` until it is actually
needed to reduce compile time. This avoids computing `CacheCost` when
the number of loads/stores is large. Additionally, since this patch
delays its calculation as much as possible, it is also effective in
other scenarios, e.g., when there are no legal loop pairs to exchange.