[Bug tree-optimization/59892] New: out of bounds array access is misoptimized

[Bug tree-optimization/59892] New: out of bounds array access is misoptimized

[alexei.starovoitov at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59892

            Bug ID: 59892
           Summary: out of bounds array access is misoptimized
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: alexei.starovoitov at gmail dot com

Created attachment 31901
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31901&action=edit
test case

attached test case was narrowed down from linux kernel
file drivers/scsi/isci/host.h

#define for_each_isci_host(id, ihost, pdev) \
        for (id = 0, ihost = to_pci_info(pdev)->hosts[id]; \
             id < ARRAY_SIZE(to_pci_info(pdev)->hosts) && ihost; \
             ihost = to_pci_info(pdev)->hosts[++id])

'hosts' array has fixed size of 2:
struct isci_pci_info {
        struct msix_entry msix_entries[SCI_MAX_MSIX_INT];
        struct isci_host *hosts[SCI_MAX_CONTROLLERS];
        struct isci_orom *orom;
};

and loop is accessing 3rd element of the array.
Behavior is undefined, but gcc 4.7 and older were ok,
whereas GCC 4.8 and the latest 4.9 are misoptimizing the code
by dropping 'id < 2' loop condition.

$ gcc -O0 array_out_of_bounds.c
$ ./a.out
(0 < 2) == 1
(1 < 2) == 1
$ gcc -O2 array_out_of_bounds.c
$ ./a.out
(0 < 2) == 1
(1 < 2) == 1
Segmentation fault (core dumped)

'cunrolli' pass is confused with such loop condition and produces wrong tree:
  <bb 3>:
  _19 = (int) _16;
  printf ("(%d < %d) == %d\n", 0, 2, _19);
  i_21 = 1;
  isci_host_22 = v.hosts[i_21];
  _6 = i_21 <= 1;
  _7 = isci_host_22 != 0B;
  _8 = _6 & _7;
  if (_8 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:
  _9 = (int) _6;
  printf ("(%d < %d) == %d\n", i_21, 2, _9);
  i_11 = i_21 + 1;
  __builtin_unreachable ();

if 'cunrolli' is disabled, the VRP pass is equally confused:
  <bb 3>:
  _9 = 1;
  printf ("(%d < %d) == %d\n", i_1, 2, 1);
  i_11 = i_1 + 1;
  isci_host_12 = v.hosts[i_11];

  <bb 4>:
  # i_1 = PHI <0(2), i_11(3)>
  # isci_host_2 = PHI <isci_host_5(2), isci_host_12(3)>
  _6 = 1;
  _7 = isci_host_2 != 0B;
  _8 = _7;
  if (_8 != 0)
    goto <bb 3>;
  else
    goto <bb 5>;

  <bb 5>:
  return 0;

and optimizes i<=1 condition into _6 = 1 above, whereas bb4 can
be executed for i=2

worst is that compiler doesn't warn on the problem.
-Wall and -Warray-bounds don't see it.

Though the code is erroneous by C standard definition, GCC should be smarter
and prevent misoptimization where it can. As a minimum it should warn about
such cases.

[Bug tree-optimization/59892] out of bounds array access is misoptimized

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59892

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The warning should be there already.

[Bug tree-optimization/59892] out of bounds array access is misoptimized

[trippels at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59892

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

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

--- Comment #2 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
struct isci_host;
struct isci_orom;

struct isci_pci_info {
  struct isci_host *hosts[2];
  struct isci_orom *orom;
} v = {{(struct isci_host *)1,(struct isci_host *)1}, 0};

int printf(const char *fmt, ...);

int isci_pci_probe()
{
  int i;
  struct isci_host *isci_host;

  for (i = 0, isci_host = v.hosts[i];
       i < 2 && isci_host;
       isci_host = v.hosts[++i]) {
    printf("(%d < %d) == %d\n", i, 2, (i < 2));
  }

  return 0;
}

int main()
{
  isci_pci_probe();
}

When v.hosts[0] or v.hosts[1] is NULL the loop is fine, so there is
no reason for a warning.
The testcase is obviously invalid.

[Bug tree-optimization/59892] out of bounds array access is misoptimized

[lukasz.dorau at intel dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59892

--- Comment #3 from Lukasz Dorau <lukasz.dorau at intel dot com> ---
(In reply to Markus Trippelsdorf from comment #2)
> When v.hosts[0] or v.hosts[1] is NULL the loop is fine, so there is
> no reason for a warning.
> The testcase is obviously invalid.
>
But v.hosts[0] and v.hosts[1] do not have to be NULL. What's more, they are
supposed not to be NULL. So why is it invalid?
I understand that the loop is erroneous, but I do not understand why
misoptimizing the code by dropping 'id < 2' loop condition is a right thing to
do? And even without any warning?

[Bug tree-optimization/59892] out of bounds array access is misoptimized

[trippels at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59892

--- Comment #4 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
(In reply to Lukasz Dorau from comment #3)
> (In reply to Markus Trippelsdorf from comment #2)
> > When v.hosts[0] or v.hosts[1] is NULL the loop is fine, so there is
> > no reason for a warning.
> > The testcase is obviously invalid.
> >
> But v.hosts[0] and v.hosts[1] do not have to be NULL. What's more, they are
> supposed not to be NULL. So why is it invalid?
> I understand that the loop is erroneous, but I do not understand why
> misoptimizing the code by dropping 'id < 2' loop condition is a right thing
> to do? And even without any warning?

Please note that you can use -fno-aggressive-loop-optimization if you 
dislike this behavior.

From http://gcc.gnu.org/bugs/:
 »if compiling with -fno-strict-aliasing -fwrapv
-fno-aggressive-loop-optimizations makes a difference, your code probably is
not correct«

And -Wno-aggressive-loop-optimizations doesn't handle early loop exits.
>From gcc-bugs-return-441133-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Jan 21 17:35:59 2014
Return-Path: <gcc-bugs-return-441133-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 20310 invoked by alias); 21 Jan 2014 17:35:58 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 20271 invoked by uid 48); 21 Jan 2014 17:35:55 -0000
From: "lukasz.dorau at intel dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/59892] out of bounds array access is misoptimized
Date: Tue, 21 Jan 2014 17:35:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: lukasz.dorau at intel dot com
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-59892-4-fxXeGMo8oZ@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-59892-4@http.gcc.gnu.org/bugzilla/>
References: <bug-59892-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-01/txt/msg02275.txt.bz2
Content-length: 154

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY892

--- Comment #5 from Lukasz Dorau <lukasz.dorau at intel dot com> ---
I see. Now I understand. Thanks!