[Bug c/102405] New: Loop index limited by a function return value considered to result in too big array subscript

[Bug c/102405] New: Loop index limited by a function return value considered to result in too big array subscript

[cazfi74 at gmail dot com]

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

            Bug ID: 102405
           Summary: Loop index limited by a function return value
                    considered to result in too big array subscript
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: cazfi74 at gmail dot com
  Target Milestone: ---

For a code where for-loop terminates before index variable gets value 25*8,
compiler gives a warning that the variable/8 used as array subscript has value
of 25 and is thus above array bounds.

Warning (turned to an error by -Werror):
In function 'pick_random_tech_to_lose',
    inlined from 'update_bulbs' at ../../../src/server/techtools.c:621:42:
../../../src/server/techtools.c:674:271: error: array subscript 25 is above
array bounds of 'unsigned char[25]' [-Werror=array-bounds]
  674 |       if (BV_ISSET(eligible_techs, i)) {
      |                                                                        
                                                                               
                                                                               
                                      ^          
In file included from ../../../src/common/player.h:31,
                 from ../../../src/common/game.h:36,
                 from ../../../src/server/techtools.c:27:
../../../src/common/tech.h: In function 'update_bulbs':
../../../src/common/tech.h:144:32: note: while referencing 'vec'
  144 | BV_DEFINE(bv_techs, A_LAST);
      |                                ^  
cc1: all warnings being treated as errors

The code compiles fine with gcc-11 (and number of earlier versions). It has
failed for some weeks with the Debian's gcc-12 development snapshot, with
latest update just today:
$ /usr/lib/gcc-snapshot/bin/gcc --version
gcc (Debian 20210918-1) 12.0.0 20210918 (experimental) [master
r12-3644-g7afcb534239]
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

The loop termination is determined by a function call, like this:
'for (; _index < advance_count(); _index++) {'
If 'advance_count()' is replaced by '(25*8)', it compiles fine. The compiler
doesn't know what values advance_count() can return (it's implemented in a
different source file) - the compile fails even if it's implemented as simple
'return 25*8;'

There's a lot of macro magic around in the original code (if you think that the
warning is what one should get from the attached .i, then the bug is probably
preprocessor side)

The command line:
/usr/lib/gcc-snapshot/bin/gcc -v -save-temps -DHAVE_CONFIG_H -I.
-I../../../src/server -I../gen_headers -I../../../src/ai
-I../../../src/ai/classic -I../../../src/common -I../../../src/common/aicore
-I../../../src/common/scriptcore -I../../../src/utility
-I../../../src/server/advisors -I../../../src/server/generator
-I../../../src/server/scripting -DLOCALEDIR="/usr/local/share/locale"
-DBINDIR="/usr/local/bin" -DFC_CONF_PATH="/usr/local/etc/freeciv"
-DDEFAULT_DATA_PATH=".:data:~/.freeciv/2.6:/usr/local/share/freeciv"
-DDEFAULT_SAVE_PATH=".:~/.freeciv/saves"
-DDEFAULT_SCENARIO_PATH=".:data/scenarios:~/.freeciv/2.6/scenarios:~/.freeciv/scenarios:/usr/local/share/freeciv/scenarios"
-Wall -Wpointer-arith -Wcast-align -Werror -Wmissing-prototypes
-Wmissing-declarations -Wformat -Wformat-security -Wnested-externs -Wshadow
-Wold-style-declaration -Wno-tautological-compare -Wno-nonnull-compare -g -O2
-MT techtools.lo -MD -MP -MF .deps/techtools.Tpo -c
../../../src/server/techtools.c -o techtools.o

[Bug c/102405] Loop index limited by a function return value considered to result in too big array subscript

[cazfi74 at gmail dot com]

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

--- Comment #1 from Marko Lindqvist <cazfi74 at gmail dot com> ---
Created attachment 51482
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51482&action=edit
preprocessed file

[Bug tree-optimization/102405] Loop index limited by a function return value considered to result in too big array subscript

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |msebor at gcc dot gnu.org
         Resolution|---                         |INVALID

--- Comment #2 from Martin Sebor <msebor at gcc dot gnu.org> ---
The warning triggers for the IL below as designed.  Your analysis is also on
the mark: GCC cannot determine that the index is in the bounds of the vec
array, and so it emits code for the cases when it isn't.

  <bb 17> [local count: 883471484]:
  i.42_76 = (unsigned int) i_74;
  if (i.42_76 > 199)
    goto <bb 20>; [33.00%]   >>> i is in [200, UINT_MAX]
  else
    goto <bb 18>; [67.00%]

  ...

  <bb 20> [local count: 291545588]:
  nologmsg.43_77 = nologmsg;
  fc_assert_fail ("../../../src/server/techtools.c", &__FUNCTION__, 674, "(i)
>= 0 && (i) < (signed int) sizeof((eligible_techs).vec) * 8", nologmsg.43_77,
nologmsg.43_77);
  _78 = i_74 >> 3;
  _79 = eligible_techs.vec[_78];   <<< -Warray-bounds: _78 is in [25, UINT_MAX
>> 3]
  _80 = (unsigned int) _79;
  _81 = i_74 & 7;
  _82 = _80 >> _81;
  _83 = (_Bool) _82;
  if (_83 != 0)
    goto <bb 21>; [50.00%]
  else
    goto <bb 49>; [50.00%]


This kind of a transformation isn't uncommon and can be the result of optimizer
improvements or other changes.  Having said that, I see the function asserts
that the index is in bounds just before using it:

  { Tech_type_id i = (1); for (; i < advance_count(); i++) { {
    if (((((i) >= 0 && (i) < (signed int) sizeof((eligible_techs).vec) * 8) ?
(void) 0 : fc_assert_fail("../../../src/server/techtools.c", __FUNCTION__, 713,
"(i) >= 0 && (i) < (signed int) sizeof((eligible_techs).vec) * 8", nologmsg,
nologmsg)), ((eligible_techs).vec[((i) / 8)] & (1u << ((i) & 0x7))) != 0)) {
      chosen--;
      if (chosen == 0) {
        return i;
      }
    }
  } } };


Assuming fc_assert_fail() behaves similar to aborts() and doesn't return to the
caller, annotating it as such is one of the recommended ways to communicate pre
and postconditions to GCC, improve the emitted code, and avoid warnings for
that GCC cannot prove is unreachable, like so:

void fc_assert_fail(const char *file, const char *function, int line,
                    const char *assertion, const char *message, ...)
  __attribute__((__format__ (__printf__, 5, 6), noreturn));

With that, I'm going to resolve the problem as invalid.  (If I misunderstood
your point please clarify.)