[Bug tree-optimization/94356] New: Missed optimisation: useless multiplication generated for pointer comparison

[Bug tree-optimization/94356] New: Missed optimisation: useless multiplication generated for pointer comparison

[pascal_cuoq at hotmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

            Bug ID: 94356
           Summary: Missed optimisation: useless multiplication generated
                    for pointer comparison
           Product: gcc
           Version: 9.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pascal_cuoq at hotmail dot com
  Target Milestone: ---

The closest existing ticket I found for this one is
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48316 but this seems different
enough, although it might be linked.

Consider the function:

typedef int t[100000];

int f(t *p, long long o) {
    return p < p+o;
}

GCC 9.3 with -O2, targeting x86-64, correctly simplifies by p, but still
generates a 64x64->64 multiplication in the computation of the offset:

f:
        imulq   $400000, %rsi, %rsi
        xorl    %eax, %eax
        testq   %rsi, %rsi
        setg    %al
        ret

(Compiler Explorer link: https://gcc.godbolt.org/z/_pT8E- )

Clang 10 avoids generating the multiplication on this example:

f:                                      # @f
        xorl    %eax, %eax
        testq   %rsi, %rsi
        setg    %al
        retq

A variant of this example is this other function g with two offsets:

int g(t *p, long long o1, long long o2) {
    return p+o1 < p+o2;
}

Clang generates the same code as for “o1<o2”, 
whereas GCC generates two multiplications:

g:
        imulq   $400000, %rsi, %rsi
        xorl    %eax, %eax
        imulq   $400000, %rdx, %rdx
        cmpq    %rdx, %rsi
        setl    %al
        ret

Compiler Explorer link: https://gcc.godbolt.org/z/sDJyHP

[Bug tree-optimization/94356] Missed optimisation: useless multiplication generated for pointer comparison

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
That's because internally we use an unsigned type for offsets (including for
the multiplication). There have been tries to change that...

[Bug tree-optimization/94356] Missed optimisation: useless multiplication generated for pointer comparison

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Given
struct S { char a[37]; };
int f1 (struct S *s, int a) { struct S *sa = s + a; return s < sa; }
int f2 (struct S *s, int a, int b) { struct S *sa = s + a; return sa < s + b; }
int f3 (struct S *s, int a) { struct S *sa = s + a; return s == sa; }
int f4 (struct S *s, int a, int b) { struct S *sa = s + a; return sa == s + b;
}
f3 is optimized in:
/* X + Y < Y is the same as X < 0 when there is no overflow.  */
...
/* For equality, this is also true with wrapping overflow.  */
...
 (simplify
  (op:c (nop_convert?@3 (pointer_plus@2 (convert1? @0) @1)) (convert2? @0))
  (if (tree_nop_conversion_p (TREE_TYPE (@2), TREE_TYPE (@0))
       && tree_nop_conversion_p (TREE_TYPE (@3), TREE_TYPE (@0))
       && (CONSTANT_CLASS_P (@1) || (single_use (@2) && single_use (@3))))
   (op @1 { build_zero_cst (TREE_TYPE (@1)); }))))
f4 is optimized too, but not exactly sure where, partly e.g. in
/* For integral types with wrapping overflow and C odd fold
   x * C EQ/NE y * C into x EQ/NE y.  */
(for cmp (eq ne)
 (simplify
  (cmp (mult @0 INTEGER_CST@1) (mult @2 @1))
  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
       && (TREE_INT_CST_LOW (@1) & 1) != 0)
   (cmp @0 @2))))
For f1/f2 we likely only optimize the ptr + x < ptr + y into x < y at RTL time,
and in any case, the multiplications are done right now in sizetype which is
unsigned type.

[Bug tree-optimization/94356] Missed optimisation: useless multiplication generated for pointer comparison

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
I tried https://gcc.gnu.org/pipermail/gcc-patches/2017-May/475037.html some
time ago. Having a different type for the multiplication and the offsetting
introduced a lot of NOPs and caused a few regressions (from my notes,
pta-ptrarith-3.c and ssa-pre-8.c were just testsuite issues, but there were
others). I filed a bug or 2 about those (PR 88926 at least). Then I tried to
also make the offsets signed, to be consistent, but that's a much bigger piece
and I ran out of time and motivation.

[Bug tree-optimization/94356] Missed optimisation: useless multiplication generated for pointer comparison

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-03-30

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I also remember tackling this in pointer_int_sum at some point (also with mixed
results).  Keep in mind the sizetype requirement for POINTER_PLUS_EXPR which
IMHO should change to either ssizetype or [s]sizetype - Bin tried the change
to ssizetype with again mixed results ;)

[Bug tree-optimization/94356] Missed optimisation: useless multiplication generated for pointer comparison

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm, the following is worse:

typedef int t[100000];

int f(t *p, long long o) {
    t *p1 = p+o;
    return p < p1;
}

[Bug tree-optimization/94356] Missed optimisation: useless multiplication generated for pointer comparison

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94356

--- Comment #6 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> Hmm, the following is worse:

That looks like a separate issue. We have fold_comparison for GENERIC, and
match.pd has related patterns for integers, or for pointers with ==, but not
for pointers with <. Strange, I thought I had added those, possibly together
with pointer_diff since the behavior is similar.