In rL316552, we intersection of unsigned latch range with signed range check and vice

versa, unless the entire range check iteration space is known positive. It was a correct

functional fix that saved us from dealing with ambiguous values, but it also appeared

to be a very restrictive limitation. In particular, in the following case:

loop: %iv = phi i32 [ 0, %preheader ], [ %iv.next, %latch] %iv.offset = add i32 %iv, 10 %rc = icmp slt i32 %iv.offset, %len br i1 %rc, label %latch, label %deopt latch: %iv.next = add i32 %iv, 11 %cond = icmp i32 ult %iv.next, 100 br it %cond, label %loop, label %exit

Here, the unsigned iteration range is `[0, 100)`, and the safe range for range

check is `[-10, %len - 10)`. For unsigned iteration spaces, we use unsigned

min/max functions for range intersection. Given this, we wanted to avoid dealing

with `-10` because it is interpreted as a very big unsigned value. Semantically, range

check's safe range goes through unsigned border, so in fact it is two disjoint

ranges in IV's iteration space. Intersection of such ranges is not trivial, so we prohibited

this case saying that we are not allowed to intersect such ranges.

What semantics of this safe range actually means is that we can start from `-10` and go

up increasing the `%iv` by one until we reach `%len - 10` (for simplicity let's assume that

`%len - 10` is a reasonably big positive value).

In particular, this safe iteration space includes `0, 1, 2, ..., %len - 11`. So if we were able to return

safe iteration space `[0, %len - 10)`, we could safely intersect it with IV's iteration space. All

values in this range are non-negative, so using signed/unsigned min/max for them is unambiguous.

In this patch, we alter the algorithm of safe range calculation so that it returnes a subset of the

original safe space which is represented by one continuous range that does not go through wrap.

In order to reach this, we use modified SCEV substraction function. It can be imagined as a function

that substracts by `1` (or `-1`) as long as the further substraction does not cause a wrap in IV iteration

space. This allows us to perform IRCE in many situations when we deal with IV space and range check

of different types (in terms of signed/unsigned).

We apply this approach for both matching and not matching types of IV iteration space and the

range check. One implication of this is that now IRCE became smarter in detection of empty safe

ranges. For example, in this case:

loop: %iv = phi i32 [ %begin, %preheader ], [ %iv.next, %latch] %iv.offset = sub i32 %iv, 10 %rc = icmp ult i32 %iv.offset, %len br i1 %rc, label %latch, label %deopt latch: %iv.next = add i32 %iv, 11 %cond = icmp i32 ult %iv.next, 100 br it %cond, label %loop, label %exit

If `%len` was less than 10 but SCEV failed to trivially prove that `%begin - 10 >u %len- 10`,

we could end up executing entire loop in safe preloop while the main loop was still generated,

but never executed. Now, cutting the ranges so that if both `begin - 10` and `%len - 10` overflow,

we have a trivially empty range of `[0, 0)`. This in some cases prevents us from meaningless optimization.