[IRCE] Smart range intersection

Authored by mkazantsev on Nov 13 2017, 4:10 AM.



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:

  %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

  %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:

  %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

  %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.

Diff Detail

mkazantsev created this revision.Nov 13 2017, 4:10 AM
anna added inline comments.Nov 14 2017, 11:15 AM
1624 ↗(On Diff #122631)

Could you please state here what exactly L stands for?

1665 ↗(On Diff #122631)


1697 ↗(On Diff #122631)

is UpperLimit guaranteed to be in [0, SINT_MAX] ?

anna added a comment.Nov 14 2017, 11:37 AM

Max, the patch explanation and logic of using SCEV subtraction LGTM. I'll need to take a closer look at your rules and the calculation in subtraction lambda.

1658 ↗(On Diff #122631)

To clarify: In both cases - signed and unsigned latch, the SCEV subtraction and rules you have below will always give us a value in range [0, SINT_MAX], i.e. we will never cross the signed border.
Here we are just "strengthening" the range and using unambiguous values for range intersection later on IRCE.

mkazantsev added inline comments.Nov 14 2017, 7:06 PM
1624 ↗(On Diff #122631)

Here L denotes right border of the safe iteration space of the given range check. If there is no such border (e.g. the check was iv > low), it is in fact SINT_MAX + 1, but we strengthen it to SINT_MAX.

1658 ↗(On Diff #122631)

It is not true. If we substract -5 from SINT_MAX in unsigned case, we have a value greater than SINT_MAX.

1665 ↗(On Diff #122631)

Will fix.

mkazantsev added inline comments.Nov 14 2017, 7:22 PM
1697 ↗(On Diff #122631)

We fail the assertion on line 1656 if it is not. It getEnd() exists, it is ensured by IsNonNegativeAndNotLoopVarying invocation in parseRangeCheckICmp. Otherwise SINT_MAX is non-negative.

anna added inline comments.Nov 15 2017, 6:36 AM
1624 ↗(On Diff #122631)

So, in the code below, L is the "EndLimit".

1629 ↗(On Diff #122631)

"if IndVar is unsigned, (0 - M) overflows, when M > 0".
The inequality is 0 <= M + IndVar, so M can be 0 right..

1658 ↗(On Diff #122631)

err.. I'm not sure what I'm missing. In the case you state, X = SINT_MAX, and Y = -5, latch is unsigned.
XMinusSIntMax = 0.
Y s< XMinusSIntMax ( i.e. -5 s< 0), i.e. it satisfies Rule 3.
So, what we are returning here is X - (XMinusSintMax) = X = SINT_MAX.

In other words, I think, if M = -5, and upperLimit = SINT_MAX, latch is unsigned, what we want the safe iteration space to be is [0, SINT_MAX + 5].
So what am I missing?

1668 ↗(On Diff #122631)

"to subtract in all cases"

mkazantsev added inline comments.Nov 16 2017, 2:43 AM
1624 ↗(On Diff #122631)

Yes, I will rename it to make it more clear.

1629 ↗(On Diff #122631)

Right, thanks for pointing out.

1658 ↗(On Diff #122631)

That Y s< XMinusSIntMax ( i.e. -5 s< 0) is a rule for signed latch.

Rules for unsigned latch are in else branch of this if :) Y = -5 goes under Rule 1: Y <s 0 ---> Y. SINT_MAX - (-5) = SINT_MAX + 5 which is still a positive value in unsigned iteration space.

mkazantsev marked 5 inline comments as done.

Addressed style comments.

mkazantsev added inline comments.Nov 16 2017, 2:56 AM
1658 ↗(On Diff #122631)

In other words, for Y = -5, Range Check range [0, SINT_MAX), unsigned latch we have result [5, SINT_MAX + 5) according to Rule 1 for unsigned latches.

anna added inline comments.Nov 16 2017, 6:24 AM
1658 ↗(On Diff #122631)

ah I was only going by the signed rules :)
Now it makes sense.
Could you please spell it out in the comment for the lambda?
"the subtract stays within the iteration space" actually implies:
if latch is Signed, then X is treated as signed, and the subtract returns:
If latch is unsigned, X is treated as unsigned and subtract returns:
In other words, they will never overflow from the iteration space where X is proven to be.
Or you could have this stated separately for the isLatchSigned and else case, like a summary for the rules.


mkazantsev added inline comments.Nov 16 2017, 8:52 PM
1658 ↗(On Diff #122631)

Actually if latch is Signed, then substract returns [SINT_MIN, SINT_MAX], as well as for unsigned latch it returns [UINT_MIN, UINT_MAX], but the rest is correct.

mkazantsev added inline comments.Nov 16 2017, 9:03 PM
1667 ↗(On Diff #123146)

should be SINT_MAX

mkazantsev marked 2 inline comments as done.

Added a more detailed comment to Lambda, fixed a typo.

Also renamed the lambda to make it more clear.

anna accepted this revision.Nov 17 2017, 10:33 AM

LGTM. thanks for the comments and clarification.

This revision is now accepted and ready to land.Nov 17 2017, 10:33 AM
This revision was automatically updated to reflect the committed changes.