[Bug tree-optimization/113440] New: Missed optimization for redundancy computation elimination because of missed judgment for unsigned overflow

[Bug tree-optimization/113440] New: Missed optimization for redundancy computation elimination because of missed judgment for unsigned overflow

[652023330028 at smail dot nju.edu.cn]

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

            Bug ID: 113440
           Summary: Missed optimization for redundancy computation
                    elimination because of missed judgment for unsigned
                    overflow
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: 652023330028 at smail dot nju.edu.cn
  Target Milestone: ---

Hello, we noticed that maybe there is a missed optimization for redundancy
computation elimination because of missed judgment for unsigned overflow.

https://godbolt.org/z/r54ezx9ea

unsigned n;
void func(unsigned a){
    if((a+a<a&&a>0) || a==0) return;   
    n=(a+a)/a;
}

GCC -O3:
func(unsigned int):
        lea     eax, [rdi+rdi]
        lea     edx, [rdi-1]
        cmp     edx, eax
        jb      .L4
        ret
.L4:
        xor     edx, edx
        div     edi
        mov     DWORD PTR n[rip], eax
        ret

Expected code (Clang):
func(unsigned int):                               # @func(unsigned int)
        test    edi, edi
        jle     .LBB0_2
        mov     dword ptr [rip + n], 2
.LBB0_2:                                # %return
        ret


Compare this to:
void func2(unsigned a){
    if(a>2147483647 || a==0) return;   
    n=(a+a)/a;
}
evrp (tree) of func2:
Folding statement: _3 = _2 / a_5(D);
Applying pattern match.pd:954, gimple-match-3.cc:2072
gimple_simplified to _3 = 2;
Global Exported: _3 = [irange] unsigned int [0, 4294967294]
Folded into: _3 = 2;

Therefore, it may be because gcc misses a judgment on unsigned overflow or
value ranges.

Thank you very much for your time and effort! We look forward to hearing from
you.

[Bug tree-optimization/113440] Missed optimization for redundancy computation elimination because of missed judgment for unsigned overflow

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
                 CC|                            |amacleod at redhat dot com
             Blocks|                            |85316

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Yeah, looks like

 if (a+a < a)

for unsigned doesn't register the appropriate range on the false edge.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases

[Bug tree-optimization/113440] Missed optimization for redundancy computation elimination because of missed judgment for unsigned overflow

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Richard Biener from comment #1)
> Yeah, looks like
> 
>  if (a+a < a)
> 
> for unsigned doesn't register the appropriate range on the false edge.

 _1 = a_5(D) * 2;
  if (_1 < a_5(D))
    goto <bb 4>; [INV]
  else
    goto <bb 3>; [INV]

  <bb 3> :
Relational : (_1 >= a_5(D))
  if (a_5(D) == 0)
    goto <bb 4>; [INV]
  else
    goto <bb 5>; [INV]

_1      [irange] unsigned int [0, 0][2, +INF] MASK 0xfffffffe VALUE 0x0
a_5(D)  [irange] unsigned int [1, +INF]
    <bb 5> :
    _3 = _1 / a_5(D);
    n = _3;



I think the ranges as such are fine, but the missing bit is that we KNOW _1 >=
a_5, but we do not use that information.

1) Ranger doesn't fullt leverage relations everywhere yet, in particaulr
multiply makes no attempt to use them or the recomputation _1 would be [2,
+INF] in bb5  (Since a_5 is now [1, +INF])
2) ranger could then utilize that in the divide to set the range of _3 to [1,
+INF] (which we don't do currently).   

But neither of those are the real issue. 

3) It requires a simplification type operation to look at _1 and understand
that the divide is a_5 * 2 / a_5,   with the known relation that a_5 * 2 >=
a_5.     This would be fairly trivial with the relation oracle if we can wire
it into one of the simplification routines.

For example, If I look in
simplify_using_ranges::simplify_div_or_mod_using_ranges
when we process the _3 = _1 / a_5(D) statement:

p query->query_relation (stmt, op0, op1)
VREL_GE

so we know...  but we do not look at _1 to see that it is defined as op1 * 2.

I don't know if we can push that sort of thing into the more general match.pd
code... it seems like it would be useful there too.

It is something on the list to eventually look into.