Bug 113440 - Missed optimization for redundancy computation elimination because of missed judgment for unsigned overflow
Summary: Missed optimization for redundancy computation elimination because of missed ...
Status: UNCONFIRMED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 14.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks: VRP
  Show dependency treegraph
 
Reported: 2024-01-17 12:02 UTC by Yi
Modified: 2024-01-17 16:01 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Yi 2024-01-17 12:02:54 UTC
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.
Comment 1 Richard Biener 2024-01-17 13:36:20 UTC
Yeah, looks like

 if (a+a < a)

for unsigned doesn't register the appropriate range on the false edge.
Comment 2 Andrew Macleod 2024-01-17 16:01:47 UTC
(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.