This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Preserve divisibility and min/max information in applyLoopGuards
ClosedPublic

Authored by alonkom on Feb 28 2023, 2:08 AM.

Details

Summary

applyLoopGuards doesn't always preserve information when there are multiple assumes.
This patch tries to deal with multiple assumes regarding a SCEV's divisibility and min/max values, and rewrite it into a SCEV that still preserves all of the information.
For example, let the trip count of the loop be TC. Consider the 3 following assumes:

  1. __builtin_assume(TC % 8 == 0);
  2. __builtin_assume(TC > 0);
  3. __builtin_assume(TC < 100);

Before this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 99), 1)

Looking at this SCEV, it doesn't preserve the divisibility by 8 information.

After this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 96), 8)

By aligning up 1 to 8, and aligning down 99 to 96, the new SCEV still preserves all of the original assumes.

Diff Detail

Event Timeline

alonkom created this revision.Feb 28 2023, 2:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 28 2023, 2:08 AM
alonkom requested review of this revision.Feb 28 2023, 2:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 28 2023, 2:08 AM

Generally looks fine, but let this chill for couple of days in case if the other reviewers have objections.

llvm/lib/Analysis/ScalarEvolution.cpp
15023

this return isn't needed

15032

If they are both constants, it's cheaper to make this check after the constant check below with their values via getAPInt.

15151

{ } not needed.

15158

{ } not needed.

15170

{ } not needed.

alonkom updated this revision to Diff 502410.Mar 5 2023, 1:51 AM
alonkom added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
15023

Done

15032

Done

15151

Done

15158

Done

15170

Done

alonkom marked 5 inline comments as done.Mar 5 2023, 1:52 AM
alonkom updated this revision to Diff 504431.Mar 12 2023, 6:41 AM

@mkazantsev let me know if you have any other comments

mkazantsev accepted this revision.Mar 14 2023, 2:46 AM

Should be fine now, thanks.

This revision is now accepted and ready to land.Mar 14 2023, 2:46 AM
alonkom updated this revision to Diff 505484.Mar 15 2023, 7:30 AM

@mkazantsev I made some changes due to the rebase on https://reviews.llvm.org/D145230 which was merged recently.
Should be ok, but let me know if it looks fine to you