[Bug c/109071] New: -Warray-bounds warning when array index checked via inline

[Bug c/109071] New: -Warray-bounds warning when array index checked via inline

[kees at outflux dot net]

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

            Bug ID: 109071
           Summary: -Warray-bounds warning when array index checked via
                    inline
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kees at outflux dot net
  Target Milestone: ---

Created attachment 54611
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54611&action=edit
PoC for -Warray-bounds false positive

The Linux kernel is seeing -Warray-bounds warnings when array indexes are being
checked via inlines. This appears to be in the overly noisy/false positive
territory, but I don't actually know what's going on.

The upstream report is here:
https://lore.kernel.org/lkml/20230306220947.1982272-1-trix@redhat.com/

Originally I thought this was another -fsanitizer=shift issue, but after
reducing the test-case, it seems to be related to inlining or some other aspect
of optimization passes.

If the "assign" function is open-coded in the caller, the warning goes away.

If the index checks are moved before the "assign" calls, the warning goes away.

If there is only 1 call to "assign", the warning goes away.

Fundamentally there should be no warning at all since the value of "index" is
entirely unknown _except_ when it makes the call to "warn".

$ cat test.c
extern void warn(void);

#define MAX_ENTRIES     4

static inline void assign(int val, int *regs, int index)
{
        if (index >= MAX_ENTRIES)
                warn();
        *regs = val;
}

struct nums {
        int vals[MAX_ENTRIES];
};

void sparx5_psfp_sg_set(int *ptr, struct nums *sg, int index)
{
        int *val;

        val = &sg->vals[index];

        assign(0,    ptr, index);
        assign(*val, ptr, index);
}

$ gcc -Wall -O2  -c -o test.o test.c
test.c: In function 'sparx5_psfp_sg_set':
test.c:20:24: warning: array subscript 4 is above array bounds of 'int[4]'
[-Warray-bounds=]
   20 |         val = &sg->vals[index];
      |                ~~~~~~~~^~~~~~~
test.c:13:13: note: while referencing 'vals'
   13 |         int vals[MAX_ENTRIES];
      |             ^~~~

[Bug tree-optimization/109071] -Warray-bounds warning when array index checked via inline

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Jump threading is happening which is causing some code to be duplicated. I am
100% sure there is a dup of this bug already filed too.

[Bug tree-optimization/109071] -Warray-bounds warning when array index checked via inline

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-03-09

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Yep, so we produce

<bb 2> [local count: 1073741824]:
if (index_3(D) > 3)
  goto <bb 4>; [33.00%]
else
  goto <bb 3>; [67.00%]

<bb 4> [local count: 354334800]:
warn ();
*ptr_5(D) = 0;
_17 = MEM <struct nums> [(int *)sg_2(D)].vals[index_3(D)];
warn ();

<bb 5> [local count: 1073741824]:
# _18 = PHI <_14(3), _17(4)>
*ptr_5(D) = _18;
return;

(and BB 3 with a BB4 duplicate w/o warn () calls).  If warn () were
noreturn this wouldn't happen.

And yes, we do have (plenty?) duplicates.

[Bug tree-optimization/109071] -Warray-bounds warning when array index checked via inline

[kees at outflux dot net]

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

--- Comment #3 from Kees Cook <kees at outflux dot net> ---
Is there a viable path to a solution here? This seems to cause enough false
positives with -Warray-bounds that at least Linux can't enable the flag. I'd
really like to have it enabled, though, since it finds plenty of real (and
usually serious) bugs.

[Bug tree-optimization/109071] -Warray-bounds warning when array index checked via inline

[qinzhao at gcc dot gnu.org]

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

qinzhao at gcc dot gnu.org changed:

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

--- Comment #4 from qinzhao at gcc dot gnu.org ---
(In reply to Andrew Pinski from comment #1)
> Jump threading is happening which is causing some code to be duplicated. I
> am 100% sure there is a dup of this bug already filed too.

Yes, the false positive warning is due to the code duplication by jump
threading. 

***without jump threading (adding fno-thread-jumps), the IR in vrp1 is:

  <bb 2> [local count: 1073741824]:
  if (index_3(D) > 3)
    goto <bb 3>; [33.00%]
  else
    goto <bb 4>; [67.00%]

  <bb 3> [local count: 354334800]:
  warn ();

  <bb 4> [local count: 1073741824]:
  *ptr_5(D) = 0;
  _1 = MEM <struct nums> [(int *)sg_2(D)].vals[index_3(D)];
  if (index_3(D) > 3)
    goto <bb 5>; [33.00%]
  else
    goto <bb 6>; [67.00%]

  <bb 5> [local count: 354334800]:
  warn ();

***with jump threading, the "Bad" IR in vrp1 is:

  <bb 2> [local count: 1073741824]:
  if (index_3(D) > 3)
    goto <bb 4>; [33.00%]
  else
    goto <bb 3>; [67.00%]

  <bb 3> [local count: 719407024]:
  *ptr_5(D) = 0;
  _14 = MEM <struct nums> [(int *)sg_2(D)].vals[index_3(D)];
  goto <bb 5>; [100.00%]

  <bb 4> [local count: 354334800]:
  warn ();
  *ptr_5(D) = 0;
  _17 = MEM <struct nums> [(int *)sg_2(D)].vals[index_3(D)];
  warn ();

in the above "Bad" IR with jump threading, we can see the problematic part is:

  <bb 4> [local count: 354334800]:
  warn ();
  *ptr_5(D) = 0;
  _17 = MEM <struct nums> [(int *)sg_2(D)].vals[index_3(D)];
  warn ();

in which the "_17 = MEM <struct nums> [(int *)sg_2(D)].vals[index_3(D)];" is
the one that was duplicated by jump threading and also is the one that caused
array bound checker to report the false positive warning based on the value
range propagation result in block 4: the value range for "index_3" is > 3,
which is out-of-range of the array "Vals", therefore the warning. 

my though is:

1. the jump threading and code duplication are all correct optimization;
2. but the duplication of the array reference caused the false positive
warning;

So, the following is my proposed solution to this problem:

1. when jump threading applies the code duplication, mark those array
references that are duplicated as ARTIFICIAL (or something else..);
2. during array bound checker, check whether the array references are
ARTIFICIAL, if it's true, do not emit the warning.

is the proposed solution feasible?

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[qinzhao at gcc dot gnu.org]

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

--- Comment #5 from qinzhao at gcc dot gnu.org ---
adding __attribute__ ((noreturn)) to the routine "warn" can eliminate the false
positive warning.

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[kees at outflux dot net]

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

--- Comment #6 from Kees Cook <kees at outflux dot net> ---
(In reply to qinzhao from comment #5)
> adding __attribute__ ((noreturn)) to the routine "warn" can eliminate the
> false positive warning.

But it does return... it's not an assert.

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[qinzhao at gcc dot gnu.org]

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

--- Comment #7 from qinzhao at gcc dot gnu.org ---
(In reply to Kees Cook from comment #6)
> (In reply to qinzhao from comment #5)
> > adding __attribute__ ((noreturn)) to the routine "warn" can eliminate the
> > false positive warning.
> 
> But it does return... it's not an assert.

***the original code is:

if (index >= 4)
  warn ();
*regs = sg->vals[index];

if the routine "warn" does return, then
it's reasonable to convert the above original code to:

***the transformed code:

if (index >= 4)
  {
    warn ();
    *regs = sg->vals[index];   /* here, index >= 4, therefore, out-of-bound */
  }
else
  *regs = sg->vals[index];

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[kees at outflux dot net]

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

--- Comment #8 from Kees Cook <kees at outflux dot net> ---
The warning is about:

      val = &sg->vals[index];


  poc.c:20:20: warning: array subscript 4 is above array bounds of 'int[4]'
[-Warray-bounds=]
   20 |     val = &sg->vals[index];
      |            ~~~~~~~~^~~~~~~


which happens before the warn(). And if the check is moved out of the
"assign()" function, the warning goes away:


    val = &sg->vals[index];

    if (index >= MAX_ENTRIES)
        warn();

    assign(0,    ptr, index);
    assign(*val, ptr, index);

Normally -Warray-bounds doesn't warn when a value is totally unknown (i.e.
"index" here can be [-INT_MAX,INT_MAX]). Why does the warning change when the
MAX_ENTRIES test is moved inside assign()?

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[qinzhao at gcc dot gnu.org]

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

--- Comment #9 from qinzhao at gcc dot gnu.org ---
(In reply to Kees Cook from comment #8)

> Normally -Warray-bounds doesn't warn when a value is totally unknown (i.e.
> "index" here can be [-INT_MAX,INT_MAX]). Why does the warning change when
> the MAX_ENTRIES test is moved inside assign()?

it's due to both inline transformation + thread jump optimization (and some
other compiler transformation inbetween). 

***After GCC inlines both calls to "assign" into the caller "sparx5_set" and
applies some other optimizations on the caller body before thread jump phase,
the body of the routine "sparx5_set" is (logically):

void sparx5_set (int * ptr, struct nums * sg, int index)
{
  if (index >= 4)
    warn ();
  *ptr = 0;

  *val = sg->vals[index];
  if (index >= 4)
    warn ();
  *ptr = *val;

  return;
}

***Thread jump optimization tried to reduce the # of branches inside the
routine "sparx5_set", in order to do this, sometime it needs to duplicate the
code. for the above routine, after thread jump optimization, the body of the
routine "sparx5_set" becomes (logically):

void sparx5_set (int * ptr, struct nums * sg, int index)
{
  if (index >= 4)
    { 
      warn ();
      *ptr = 0;               // code duplications since "warn" does return;
      *val = sg->vals[index]; // same this line. in this path, since it's under
                              // the condition "index >= 4", the compiler knows
                              // the value of "index" is larger then 4,
therefore
                              // the out-of-bound warning.
      warn ();
    }
  else
    { 
      *ptr = 0;
      *val = sg->vals[index];
    }
  *ptr = *val;
  return;

}

with the thread jump optimization, the # of branches inside the routine
"sparx5_set" is reduced from 2 to 1, however, due to the code duplication
(which is needed for the correctness of the code), we got a out-of-bound
warning. 

actually, I don't think that the compiler's behavior is wrong. and it's not
very reasonable for the users of -Warray-bounds to assume there is zero false
positive warnings. 
However, it might be reasonable to put such warnings to -Warray-bounds=2 but
not in -Warray-bounds=1?

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[qinzhao at gcc dot gnu.org]

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

--- Comment #10 from qinzhao at gcc dot gnu.org ---
with the following added heuristic in array-bound checker:

+  /* If the stmt is duplicated and splitted, the warning level is not 2,
+     and the current block is not dominating the exit block, not report
+     the warning.  */
+  if (is_splitted && warn_array_bounds < 2
+      && !is_dominate_exit)
+    return false;
+

such false positive warnings are moved from -Warray-bound=1 to -Warray-bound=2.
[opc@qinzhao-ol8u3-x86 109071]$ /home/opc/Install/latest-d/bin/gcc -O2
-Warray-bounds=2 -c -o t.o t.c
t.c: In function ‘sparx5_set’:
t.c:12:29: warning: array subscript 4 is above array bounds of ‘int[4]’
[-Warray-bounds=]
   12 |         int *val = &sg->vals[index];
      |                     ~~~~~~~~^~~~~~~
t.c:8:18: note: while referencing ‘vals’
    8 | struct nums {int vals[4];};
      |                  ^~~~
[opc@qinzhao-ol8u3-x86 109071]$ /home/opc/Install/latest-d/bin/gcc -O2
-Warray-bounds=1 -c -o t.o t.c
[opc@qinzhao-ol8u3-x86 109071]$

[Bug tree-optimization/109071] -Warray-bounds false positive warnings due to code duplication from jump threading

[qinzhao at gcc dot gnu.org]

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

--- Comment #11 from qinzhao at gcc dot gnu.org ---
please see discussion at:
https://gcc.gnu.org/pipermail/gcc-patches/2024-May/651482.html

A summary of the discussion:

1. The current warning is correct, which catches a potential source code error
that should be fixed in the source code level;
2. The best way to fix the source code level error is:
   make the routine "warn" a non-return function, and use the attribute
__noreturn __ to mark it.
3. Although the warning is correct in theory, the warning message itself is
confusing to the end-user since there is information that cannot be connected
to the source code directly.
4. It will be a nice improvement to add more information in the warning message
to report the location info on where such index value come from, for example:

warning: array index always above array bounds
events 1:

| 3 |  if (index >= 4)
        |
       (1) when index >= 4

then the end-user will know how such out-of-bound access come from.
We also need to clarify in the documentation part on how to fix such warnings
in the source code level. 
5. In order to implement the above 4, we might need to record the location
information to somewhere (in STMT or in Block) during the code duplication
phase. more details need to be worked out on this.