Page MenuHomePhabricator

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

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



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:

Proof for getUDivExpr extension:a

Proof for isKnownPredicateSubIdiom:

Diff Detail

Unit TestsFailed

90 msx64 debian > LLVM.CodeGen/Thumb2::mve-blockplacement.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/llc -mtriple=thumbv8.1m.main-none-none-eabi -verify-machineinstrs -mattr=+mve /mnt/disks/ssd0/agent/llvm-project/llvm/test/CodeGen/Thumb2/mve-blockplacement.ll -o - | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/CodeGen/Thumb2/mve-blockplacement.ll
130 msx64 windows > LLVM.CodeGen/Thumb2::mve-blockplacement.ll
Script: -- : 'RUN: at line 2'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\llc.exe -mtriple=thumbv8.1m.main-none-none-eabi -verify-machineinstrs -mattr=+mve C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\Thumb2\mve-blockplacement.ll -o - | c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\Thumb2\mve-blockplacement.ll

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.

What C3 stands for? Is it actually C2?


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

reames added inline comments.Feb 24 2021, 2:00 PM

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.

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)


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


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.

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


It should be C2, thanks!


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.


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


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

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.