This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Improve handling of pointer compares involving subtractions (WIP).
Needs ReviewPublic

Authored by fhahn on Feb 20 2021, 11:13 AM.

Details

Summary

WIP as I still need to do further testing and re-collecting &
applying the loop guards every time can be quite expensive in terms of
compile time. But I thought it would be good to share early, in case I
missed anything.

This patch improves handling of pointer comparisons involving
subtractions, by using knowledge that the involved variables are != 0
and signed positive.

It uses applyLoopGuards to add != 0 info to the involved expressions (by
re-writing them as umax expression. It also adds a new fold to move zext
into umax expressions and to move udiv expression inside subtraction, if
the operands guarantee a positive result.

The motivating code for this is eliminating range checks for code
like below from PR48965.

#include <assert.h>

void foo(const int *y, unsigned y_len) {
  const int *y_end = y + y_len;
  unsigned c = 0;
  for (const int *y_iter = y; y_iter != y_end; y_iter++, c++) {
    assert(c < y_len);
  }
  assert(c == y_len);
}

Proof for zext/umax fold: https://alive2.llvm.org/ce/z/t75T53

Proof for getUDivExpr extension:a https://alive2.llvm.org/ce/z/H_G2Q0

Proof for isKnownPredicateSubIdiom: https://alive2.llvm.org/ce/z/Gfe8mS

Diff Detail

Event Timeline

fhahn created this revision.Feb 20 2021, 11:13 AM
fhahn requested review of this revision.Feb 20 2021, 11:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 20 2021, 11:13 AM
This comment was removed by mkazantsev.
llvm/lib/Analysis/ScalarEvolution.cpp
3121

What C3 stands for? Is it actually C2?

10980

Please specify that <= and >= here are actually unsigned.

reames added inline comments.Feb 24 2021, 2:00 PM
llvm/lib/Analysis/ScalarEvolution.cpp
1840

Couple of comments on this transform:

  1. It's not clear why (or if) this is a profitable canonicalization. We're replacing one zext with two. I'd want an explanation of why this was the right idea, and in particular, why not to canonicalize the other direction.
  2. umax can have more than two operands.
  3. this should be a separate change once you're ready for actual review.
3125

Another way to consider approaching this:
(-C1 + X) /u C2

-C1/C2 + (-C1 % C2 + X) /u C2

(i.e. extract out the whole integer divisions and leave only the possible fractional part)

10983

You can also handle ULT without much work. isKnownNonNegative becomes isKnownPositive in that case.

10986

Do we canonicalize x + (-Y) to (-Y) + X somewhere? If not, you're missing some pattern matching cases here.

fhahn updated this revision to Diff 328304.Mar 4 2021, 2:06 PM
fhahn marked an inline comment as done.

Address comments, thanks!

fhahn marked 2 inline comments as done.Mar 4 2021, 2:13 PM
fhahn added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
1840

I will split this off in a separate review.

Initially I was planning on only restricting it to a umax with at least one constant operand, so the number of zexts stays the same. We already shift zexts inwards for other expressions above, so I think most code would expect them as 'inwards' as possible (but I might be wrong).

3121

It should be C2, thanks!

3125

Thanks, I'll have to think a bit more about that and see if there are any expressions that cannot be handled well by either.

10983

Done, but I still need to construct a test case.

10986

It looks like we don't do that, we only sort the operands by their complexity which should group the -1 * X parts together, but there could be other 'less complex' expression before them. I adjusted to also check for the swapped version.

I still need to construct a test case.

fhahn updated this revision to Diff 328306.Mar 4 2021, 2:15 PM
fhahn marked an inline comment as done.

Make sure to only handle adds with 2 operands.

mkazantsev added inline comments.Mar 12 2021, 1:24 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10991

For ule case the comment says that X is non-negative and the code checks it's non-positive. I guess it's a bug in code.

Re-ping

This is still marked as a WIP, what are you hoping for in terms of further reviewer involvement?

mkazantsev resigned from this revision.Jul 8 2021, 11:40 PM

This has been a WIP patch w/o author updates for a good while. Please add me back when it'll move somewhere.

reames resigned from this revision.Nov 30 2021, 10:01 AM

Pending author action, please re-add as reviewer if you ever return to this.