Bug 91326 - VRP does not handle array value range
Summary: VRP does not handle array value range
Status: RESOLVED DUPLICATE of bug 80603
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 10.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
Keywords: missed-optimization
Depends on:
Blocks: VRP
  Show dependency treegraph
Reported: 2019-08-02 12:40 UTC by Zdenek Sojka
Modified: 2020-01-28 15:19 UTC (History)
3 users (show)

See Also:
Known to work:
Known to fail:
Last reconfirmed: 2020-01-28 00:00:00

testcase (179 bytes, text/plain)
2019-08-02 12:40 UTC, Zdenek Sojka

Note You need to log in before you can comment on or make changes to this bug.
Description Zdenek Sojka 2019-08-02 12:40:56 UTC
Created attachment 46659 [details]

For the attached code, gcc "10.0.0 20190730" -O3 generates:

        movsx   rdi, edi
        mov     eax, 1
        mov     edx, DWORD PTR arr[0+rdi*4]
        test    edx, edx
        je      .L1
        xor     eax, eax
        cmp     edx, 10
        setg    al
        add     eax, eax

        xor     eax, eax
        cmp     edi, 2
        seta    al

        xor     eax, eax

clang "7.1.0" and "8.0.1" -O3 generate the optimal code for all 3 versions:

        xor     eax, eax

        xor     eax, eax

        xor     eax, eax
Comment 1 Marc Glisse 2019-08-02 13:25:13 UTC
For bar, we don't take advantage of the uninitialized variable enough, we still have "a_3(D) == 0" at expansion time (RTL gets rid of it, but too conservatively).

For foo, indeed computing the min and max values of the array to get a range for any access to it would be nice.
Comment 2 Martin Sebor 2019-08-02 18:45:31 UTC
Associating the minimum and maximum with the declaration of each constant array object would be a simple way of doing it but I'm not sure how much it would gain.  Doing better would mean a linear traversal of the array.  That seems to be what Clang does -- it folds even equalities with values in the range [MIN, MAX] that aren't in the array.  An only slightly less costly approach would be to only search the elements between the lower and upper bounds of the index.

I pondered doing this for strcmp and strlen but the linear search felt too expensive (Clang doesn't do it).  It might be worth getting some data on how often it would trigger and what it would cost.
Comment 3 Jakub Jelinek 2019-08-03 15:05:32 UTC
Related to https://gcc.gnu.org/ml/gcc-patches/2017-04/msg01559.html (which hasn't been applied).
Comment 4 Jakub Jelinek 2020-01-28 15:19:21 UTC

*** This bug has been marked as a duplicate of bug 80603 ***