Bug 98357 - Bounds check not eliminated
Summary: Bounds check not eliminated
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 11.0
: P3 normal
Target Milestone: 12.0
Assignee: Not yet assigned to anyone
Keywords: missed-optimization
Depends on:
Blocks: VRP
  Show dependency treegraph
Reported: 2020-12-17 17:09 UTC by Jeff Muizelaar
Modified: 2021-09-05 00:21 UTC (History)
4 users (show)

See Also:
Known to work:
Known to fail:
Last reconfirmed: 2021-01-05 00:00:00


Note You need to log in before you can comment on or make changes to this bug.
Description Jeff Muizelaar 2020-12-17 17:09:55 UTC
#include <stdlib.h>
char foo(char* data, size_t len, size_t i, size_t j) {
    if (i < len && j <= i) {
        if (j < len) {
            return data[j];
        } else {
    } else {
        return 0;

compiles to:

foo(char*, unsigned long, unsigned long, unsigned long):
        cmp     rdx, rsi
        jnb     .L4
        cmp     rdx, rcx
        jb      .L4
        cmp     rsi, rcx
        jbe     .L3
        movzx   eax, BYTE PTR [rdi+rcx]
        xor     eax, eax
        push    rax
        mov     edi, 1
        call    exit

The call to exit should be eliminated.
Comment 1 Jeff Muizelaar 2020-12-17 18:39:52 UTC
Clang compiles this to:

foo(char*, unsigned long, unsigned long, unsigned long):                            # @foo(char*, unsigned long, unsigned long, unsigned long)
        xor     eax, eax
        cmp     rdx, rsi
        jae     .LBB0_3
        cmp     rcx, rdx
        ja      .LBB0_3
        mov     al, byte ptr [rdi + rcx]

with -O2 -mllvm -enable-constraint-elimination
Comment 2 Richard Biener 2021-01-05 08:43:57 UTC
So VRP computes

Visiting conditional with predicate: if (len_13 > j_14)

With known ranges
        len_13: size_t [i_6(D) + 1, +INF]  EQUIVALENCES: { len_7(D) } (1 elements)      j_14: long unsigned int [0, i_6(D)]  EQUIVALENCES: { j_8(D) } (1 elements)

Predicate evaluates to: DON'T KNOW

where I guess the issue is that we assume i_6(D) + 1 may overflow to zero
(the [i_6(D) + 1, +INF] range is computed from len_7(D) > i_6(D) where
we _know_ that i_6(D) + 1 cannot overflow.

The representation of symbolic relations as ranges makes things awkward
(we for sure cannot generally assume i_6(D) + 1 cannot overflow).  We
could possibly mark ranges as originally derived to not have overflowing
bound computations somehow (maybe with a flag in on value-range).

symbolic range VRP is most important for Ada so CCing Eric
Comment 3 Andrew Macleod 2021-02-19 14:47:11 UTC
We should be able to handle this in GCC 12 . The WIP relation support in ranger currently is showing:

    <bb 2> :
    _1 = i_6(D) < len_7(D);
    _2 = i_6(D) >= j_8(D);
    _3 = _1 & _2;
    if (_3 != 0)
      goto <bb 3>; [INV]
      goto <bb 6>; [INV]

=========== BB 3 ============
len_7(D)        size_t [1, +INF]
j_8(D)  size_t VARYING
Relational : (i_6(D) >= j_8(D))
Relational : (i_6(D) < len_7(D))
    <bb 3> :
    if (len_7(D) > j_8(D))
      goto <bb 4>; [INV]
      goto <bb 5>; [INV]

So once I get the transitive queries of relations working, we should be able to recognize
  len_7 > i_6 >= j_8 
and then the condition will fold trivially eliminating the call to exit().
Comment 4 Andrew Pinski 2021-09-05 00:21:55 UTC
Fixed on the trunk by some of the improvements to VRP (range).