[Bug c++/57199] New: [4.8, 4.9] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[Bug c++/57199] New: [4.8, 4.9] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[ppluzhnikov at google dot com]

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

             Bug #: 57199
           Summary: [4.8, 4.9] Bogus warning: iteration NNNN invokes
                    undefined behavior -Waggressive-loop-optimizations
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ppluzhnikov@google.com


Google ref: b/8856275

Test case:



typedef decltype(sizeof(0)) size_t;

struct Foo {
  ~Foo();     // comment out -> problem disappears
  int x[20];
};

template <typename T, int N>
struct InlinedVector {
  inline InlinedVector() : size_(0) { }
  inline size_t size() const {
    return size_;
  }
  T* mutable_array();
  void resize(size_t n) {
    size_t s = size();
    DestroyElements(mutable_array() + n, s - n);
  }
  static void DestroyElements(T* ptr, size_t num) {
    for (size_t i = 0; i < num; i++) {
      ptr[i].~T();
    }
  }

  size_t size_;
};

struct CP {
  void Add();
  InlinedVector<Foo,1> foo_;
};

void CP::Add() {
  foo_.resize(foo_.size() + 1);
}



Using trunk r198689:

g++ -std=c++11 -O2 -c tt.cc
tt.cc: In member function ‘void CP::Add()’:
tt.cc:21:7: warning: iteration 230584300921369396ul invokes undefined behavior
[-Waggressive-loop-optimizations]
       ptr[i].~T();
       ^
tt.cc:20:5: note: containing loop
     for (size_t i = 0; i < num; i++) {
     ^
>From gcc-bugs-return-421782-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue May 07 22:17:31 2013
Return-Path: <gcc-bugs-return-421782-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 32442 invoked by alias); 7 May 2013 22:17:30 -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 32419 invoked by uid 48); 7 May 2013 22:17:27 -0000
From: "ppluzhnikov at google dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c/57200] New: [4.8/4.9] aggressive-loop-optimizations notes appear even when warning itself is suppressed
Date: Tue, 07 May 2013 22:17:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: ppluzhnikov at google dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Changed-Fields:
Message-ID: <bug-57200-4@http.gcc.gnu.org/bugzilla/>
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-SW-Source: 2013-05/txt/msg00455.txt.bz2
Content-length: 1054


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

             Bug #: 57200
           Summary: [4.8/4.9] aggressive-loop-optimizations notes appear
                    even when warning itself is suppressed
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ppluzhnikov@google.com


Test:

int x[10];

void fn ()
{
  int i;

  for (i = 0; i < 100; ++i)
    x[i] = 1;
}


Using trunk at r198689:

gcc -O2 -c t.c 
t.c: In function ‘fn’:
t.c:8:10: warning: iteration 10u invokes undefined behavior
[-Waggressive-loop-optimizations]
     x[i] = 1;
          ^
t.c:7:3: note: containing loop
   for (i = 0; i < 100; ++i)
   ^


Looks good. But this doesn't:

gcc -O2 -c t.c -w
t.c: In function ‘fn’:
t.c:7:3: note: containing loop
   for (i = 0; i < 100; ++i)
   ^

A note suddenly appears from "nowhere" :-(
>From gcc-bugs-return-421783-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue May 07 22:29:09 2013
Return-Path: <gcc-bugs-return-421783-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 4469 invoked by alias); 7 May 2013 22:29:09 -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 4369 invoked by uid 48); 7 May 2013 22:28:57 -0000
From: "mpolacek at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/55278] [4.8/4.9 Regression] Botan performance regressions apparently due to LRA
Date: Tue, 07 May 2013 22:29:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Keywords: missed-optimization, ra
X-Bugzilla-Severity: normal
X-Bugzilla-Who: mpolacek at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.8.1
X-Bugzilla-Changed-Fields: CC
Message-ID: <bug-55278-4-wm1OtsU9Ln@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-55278-4@http.gcc.gnu.org/bugzilla/>
References: <bug-55278-4@http.gcc.gnu.org/bugzilla/>
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
X-SW-Source: 2013-05/txt/msg00456.txt.bz2
Content-length: 3377


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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-05-07 22:28:56 UTC ---
Reduced by Jakub to this:

unsigned char KASUMI_SBOX_S7[128];
unsigned short KASUMI_SBOX_S9[512];

static inline unsigned short
rotate_left (unsigned short input, unsigned long rot)
{
  return ((input << rot) | (input >> (8 * sizeof (unsigned short) - rot)));
}

static inline unsigned short
reverse_bytes (unsigned short val)
{
  return rotate_left (val, 8);
}

static inline unsigned short
load_be (const unsigned char in[], unsigned long off)
{
  return reverse_bytes (*((in) + off));
}

static inline void
store_be (unsigned short in, unsigned char out[2])
{
  *out = reverse_bytes (in);
}

static inline void
store_be4 (unsigned char out[], unsigned short x0, unsigned short x1,
      unsigned short x2, unsigned short x3)
{
  store_be (x0, out + (0 * sizeof (unsigned short)));
  store_be (x1, out + (1 * sizeof (unsigned short)));
  store_be (x2, out + (2 * sizeof (unsigned short)));
  store_be (x3, out + (3 * sizeof (unsigned short)));
}

unsigned short
FI (unsigned short I, unsigned short K)
{
  unsigned short D9 = (I >> 7);
  unsigned char D7 = (I & 0x7F);
  D9 = KASUMI_SBOX_S9[D9] ^ D7;
  D7 = KASUMI_SBOX_S7[D7] ^ (D9 & 0x7F);

  D7 ^= (K >> 9);
  D9 = KASUMI_SBOX_S9[D9 ^ (K & 0x1FF)] ^ D7;
  D7 = KASUMI_SBOX_S7[D7] ^ (D9 & 0x7F);
  return (D7 << 9) | D9;
}

__attribute__((noinline, noclone))
void
encrypt_n (unsigned short **EK, const unsigned char in[], unsigned char out[],
       unsigned long blocks)
{
  unsigned long i, j;
  for (i = 0; i != blocks; ++i)
    {
      unsigned short B0 = load_be (in, 0);
      unsigned short B1 = load_be (in, 1);
      unsigned short B2 = load_be (in, 2);
      unsigned short B3 = load_be (in, 3);
      for (j = 0; j != 8; j += 2)
    {
      const unsigned short *K = &(*EK)[8 * j];
      unsigned short R = B1 ^ (rotate_left (B0, 1) & K[0]);
      unsigned short L = B0 ^ (rotate_left (R, 1) | K[1]);
      L = FI (L ^ K[2], K[3]) ^ R;
      R = FI (R ^ K[4], K[5]) ^ L;
      L = FI (L ^ K[6], K[7]) ^ R;
      R = B2 ^= R;
      L = B3 ^= L;
      R = FI (R ^ K[10], K[11]) ^ L;
      L = FI (L ^ K[12], K[13]) ^ R;
      R = FI (R ^ K[14], K[15]) ^ L;
      R ^= (rotate_left (L, 1) & K[8]);
      L ^= (rotate_left (R, 1) | K[9]);
      B0 ^= L;
      B1 ^= R;
    }
      store_be4 (out, B0, B1, B2, B3);
      in += 8;
      out += 8;
    }
}

unsigned char in[4096], out[4096];

int
main ()
{
  unsigned short EKb[64], *EK = EKb;
  __builtin_memset (EKb, 0, sizeof EKb);
  asm volatile ("" : : : "memory");
  int i;
  for (i = 0; i < 100000; i++)
    encrypt_n (&EK, in, out, 4096 / 8);
  return 0;
}

Using -O3  -finline-functions  -D_REENTRANT -Wno-long-long -W -Wall -fPIC
-fvisibility=hidden, then trunk gcc:
$ time ./a.out
real    0m15.727s
user    0m15.639s
sys    0m0.004s

while with trunk clang:
$ time ./a.out
real    0m7.864s
user    0m7.796s
sys    0m0.005s

[Bug c++/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-05-07
            Version|unknown                     |4.9.0
            Summary|[4.8, 4.9] Bogus warning:   |[4.8/4.9 Regression] Bogus
                   |iteration NNNN invokes      |warning: iteration NNNN
                   |undefined behavior          |invokes undefined behavior
                   |-Waggressive-loop-optimizat |-Waggressive-loop-optimizat
                   |ions                        |ions
     Ever Confirmed|0                           |1

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2013-05-08 08:57:45 UTC ---
Note that there seems to be an error in the source:

    void resize(size_t n) {
        size_t s = size();
        DestroyElements(mutable_array() + n, s - n);

for the call with n == size () + 1 the function calls DestroyElements
with -1U elements which we figure out and optimize the caller to

  <bb 3>:
  _13 = i_12 * 80;
  _14 = _11 + _13;
  Foo::~Foo (_14);
  i_15 = i_12 + 1;

  <bb 4>:
  # i_12 = PHI <0(2), i_15(3)>
  if (i_12 != 18446744073709551615)
    goto <bb 3>;
  else
    goto <bb 5>;

which then causes the addition to overflow and invoke undefined behavior
and we warn.

Thus, the warning, while not 100% helpful, points at a real problem.

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[ppluzhnikov at google dot com]

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

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|INVALID                     |

--- Comment #2 from Paul Pluzhnikov <ppluzhnikov at google dot com> 2013-05-08 12:55:31 UTC ---
> Thus, the warning, while not 100% helpful, points at a real problem.

There is no real problem in the original source, which reads:

  size_t s = size();
  if (n < s)
    DestroyElements(mutable_array() + n, s - n);
  else ...

and produces the same warning.

Here is updated test with above condition; confirmed to still show the warning
with trunk @r198709.



typedef decltype(sizeof(0)) size_t;

struct Foo {
  ~Foo();      // comment out -> problem disappears
  int x[20];
};

template <typename T, int N>
struct InlinedVector {
  inline InlinedVector() : size_(0) { }
  inline size_t size() const {
    return size_;
  }
  T* mutable_array();
  void resize(size_t n) {
    size_t s = size();
    if (n < s)
      DestroyElements(mutable_array() + n, s - n);
  }
  static void DestroyElements(T* ptr, size_t num) {
    for (size_t i = 0; i < num; i++) {
      ptr[i].~T();
    }
  }

  size_t size_;
};

struct CP {
  void Add();
  InlinedVector<Foo,1> foo_;
};

void CP::Add() {
  foo_.resize(foo_.size() + 1);
}

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.1

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I don't think the warning is bogus.
At phiprop we have:
  long unsigned int _3;
  size_t _6;
  size_t _7;
  long unsigned int _8;

  <bb 2>:
  _6 = MEM[(const struct InlinedVector *)this_1(D)].size_;
  _3 = _6 + 1;
...
  _7 = MEM[(const struct InlinedVector *)this_1(D)].size_;
  if (_3 < _7)
    goto <bb 3>;
  else
    goto <bb 6>;

  <bb 3>:
  _8 = _7 - _3;

and fre2 turns this into:

  _6 = MEM[(const struct InlinedVector *)this_1(D)].size_;
  _3 = _6 + 1;
...
  _7 = _6;
  if (_3 < _7)
    goto <bb 3>;
  else
    goto <bb 6>;

  <bb 3>:
  _8 = 18446744073709551615;

i.e. it can't prove the following loop that uses _8 as upper bound is dead, but
the loop has at that point constant bounds and triggers undefined behavior in
it if executed.  The loop can be only executed if foo_.size() is (size_t) -1,
but if you call it with this value, you'll surely hit the undefined behavior
the warning is complaining about.

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[ppluzhnikov at google dot com]

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

--- Comment #4 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
(In reply to Jakub Jelinek from comment #3)
> it can't prove the following loop that uses _8 as upper bound is dead, ...

Do we need a separate "may invoke undefined behavior" warning?

In our codebase of 100+ million lines of C++, we've found ~20 instances of real
"invokes undefined behavior" (so we don't want to turn the
-Waggressive-loop-optimizations off).

But we also have ~5 instances where the warning is bogus, and there is no easy
way to turn them off, short of sprinkling -Wno-aggresive-loop-optimizations
over our BUILD files.

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
But this isn't any form of the may invoke, the loop certainly unconditionally
invokes undefined behavior, just the whole loop is very unlikely to be ever
executed (in this case if size is supposed to represent the length of an array
with elements bigger than 1, then already the size would need to be invalid,
but that is something the compiler can't understand, for it the size_t field is
likely any other field, and there is no guarantee it won't be -1).

It is in principle no different from say:

void
foo (size_t x)
{
  if (x == (size_t) -1)
    {
      unsigned int a[128];
      int i;

      for (i = 0; i < 128; ++i)     /* { dg-message "note: containing loop" }
*/
        a[i] = i * 0x02000001;      /* { dg-warning "invokes undefined
behavior" } */
      bar (a);
    }
}

where you know you are never going to call foo with (size_t) -1, but the
compiler doesn't know.  How is the above different from say:
void
bar (void)
{
  unsigned int a[128];
  int i;

  for (i = 0; i < 128; ++i)     /* { dg-message "note: containing loop" } */
    a[i] = i * 0x02000001;      /* { dg-warning "invokes undefined behavior" }
*/
  bar (a);
}
...
/* in another CU */
void
baz (size_t x)
{
  if (x == (size_t) -1)
    bar ();
}

In your original testcase, you wouldn't get the warning if size was a signed
integer instead of unsigned one, then the compiler would know it is undefined
behavior if the size wraps and would just optimize the loop away altogether. 
Or perhaps some __builtin_unreachable assert that size isn't (size_t) -1?

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[ppluzhnikov at google dot com]

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

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |WONTFIX

--- Comment #6 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
> perhaps some __builtin_unreachable assert that size isn't (size_t) -1?

That works. Thanks for the suggestion.

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[dichlofos-mv at yandex dot ru]

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

Mikhail Veltishchev <dichlofos-mv at yandex dot ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dichlofos-mv at yandex dot ru

--- Comment #7 from Mikhail Veltishchev <dichlofos-mv at yandex dot ru> ---
(In reply to Paul Pluzhnikov from comment #6)
> > perhaps some __builtin_unreachable assert that size isn't (size_t) -1?
> 
> That works. Thanks for the suggestion.
Please, can you explain how you fixed this? We have almost the same problem.

[Bug tree-optimization/57199] [4.8/4.9 Regression] Bogus warning: iteration NNNN invokes undefined behavior -Waggressive-loop-optimizations

[ppluzhnikov at google dot com]

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

--- Comment #8 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
(In reply to Mikhail Veltishchev from comment #7)

> Please, can you explain how you fixed this? We have almost the same problem.

Here is the fix we deployed (test case from comment#2):

$ diff -u pr57199.cc pr57199a.cc
--- pr57199.cc  2014-03-26 13:50:25.682351842 -0700
+++ pr57199a.cc 2014-03-26 13:54:12.880279926 -0700
@@ -18,6 +18,9 @@
       DestroyElements(mutable_array() + n, s - n);
   }
   static void DestroyElements(T* ptr, size_t num) {
+    if (__builtin_expect (num == (size_t) -1, 0)) {
+      __builtin_unreachable();
+    }
     for (size_t i = 0; i < num; i++) {
       ptr[i].~T();
     }