[SCEV] Compute ranges for lshr recurrences

[reames]

Summary

Straight forward extension to the recently added infrastructure which was pioneered with shl.

@reviewers - I always have trouble with wrapping arithmetic, so please sanity check my usage of ranges and reasoning.

[reames]

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

664

The choice of the inverted range here looks odd. I dug into this a bit, and am suspecting a generic bug in the preferred range mechanism in ConstantRange. The key point is that we're making a heuristic driven chosen between two possible ranges, and we simply happen to pick the other one after this patch.

[mkazantsev]

I couldn't find tests for the following scenarios:

• Saturated ashr for positive & negative start;
• Zero shift value (for any operation & start);
• Start/end value not being power of 2 (power of 2 - 1). I am a bit worried that the boundaries of the ranges are always powers of 2, and no test shows that the rounding is correct.

(I don't claim there is none, but I could not find them in this test file :) )
Could you please point out on them (if they exist) or add them?

llvm/lib/Analysis/ScalarEvolution.cpp

5732

Any tests for two first cases?

[reames]

Need to add additional tests (or pointers to them), but also intentionally stalling this until issues with handling of unreachable code in the underlying infrastructure are resolved and nothing new pops up for a few days.

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

664

Dug into this further, and it's not a bug in the code, it was a bug in my understanding. The broad point about it being a legal choice for the answer still holds though.

[reames]

In D99687#2668491, @mkazantsev wrote:

I couldn't find tests for the following scenarios:

• Saturated ashr for positive & negative start;

test_ashr_tc_positive and test_ashr_tc_negative - not that 128 is INT_MIN for i8

• Zero shift value (for any operation & start);

added as test_lshr_zero_shift and test_ashr_zero_shift

• Start/end value not being power of 2 (power of 2 - 1). I am a bit worried that the boundaries of the ranges are always powers of 2, and no test shows that the rounding is correct.

Added as test_lshr_power_of_2_start, test_lshr_arbitrary_start, and test_lshr_start_power_of_2_plus_one

[reames]

Rebase over requested tests, and narrow initial scope to lshr only. Will return to ashr once this lands.

[mkazantsev]

Thanks, LGTM!