This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Compute ranges for lshr recurrences
ClosedPublic

Authored by reames on Mar 31 2021, 2:26 PM.

Details

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.

Diff Detail

Event Timeline

reames created this revision.Mar 31 2021, 2:26 PM
reames requested review of this revision.Mar 31 2021, 2:26 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 31 2021, 2:26 PM
reames added inline comments.Mar 31 2021, 2:28 PM
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.

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
5731

Any tests for two first cases?

reames planned changes to this revision.Apr 6 2021, 7:33 PM

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.

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 updated this revision to Diff 338944.Apr 20 2021, 11:45 AM
reames retitled this revision from [SCEV] Compute ranges for ashr/lshr recurrences to [SCEV] Compute ranges for lshr recurrences.

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

mkazantsev accepted this revision.Apr 22 2021, 1:28 AM

Thanks, LGTM!

This revision is now accepted and ready to land.Apr 22 2021, 1:28 AM
This revision was landed with ongoing or failed builds.Apr 22 2021, 11:06 AM
This revision was automatically updated to reflect the committed changes.