[SimpleLoopUnswitch] Inject loop-invariant conditions and unswitch them when it's profitable

Based on https://discourse.llvm.org/t/rfc-inject-invariant-conditions-to-loops-to-enable-unswitching-and-constraint-elimination

This transform attempts to handle the following loop:
```
for (...) {
  x = <some variant>
  if (x <u C1) {} else break;
  if (x <u C2) {} else break;
}
```
Here `x` is some loop-variant value, and `C1` and `C2` are loop invariants.
As we see, this loop has no invariant checks we can unswitch on. However, there is an
invariant condition that can make the second check redundant. Specifically, it is `C1 <=u C2`.
We can modify this code in the following way:
```
for (...) {
  x = <some variant>
  if (x <u C1) {} else break;
  if (C1 <=u C2) {
  /* no check is required */
  }
  else {
    // do the check normally
    if (x <u C2) {} else break;
  }
}
```
Now we have an invariant condition `C1 <=u C2` and can unswitch on it.

This patch introduces the basic version of this transform, with some limitations,
all of them seem liftable (but needs more work & testing):
- All checks are `ult` condition;
- All branches in question stay in loop if the said condition is true and leave it otherwise;
- All in-loop branches are hot enough;

There is also a room for improvement cost model. So far we evalutate the cost of
unswitching this newly injected invariant branch the same as if we would unswitch
on 2nd condition, which is not exactly precise (but also not grossly wrong).

Differential Revision: https://reviews.llvm.org/D136233
Reviewed By: skatkov

0 files changed, 0 insertions, 0 deletions