[Bug c++/64491] New: warning: loop exit may only be reached after undefined behavior

[Bug c++/64491] New: warning: loop exit may only be reached after undefined behavior

[stuwph at live dot de]

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

            Bug ID: 64491
           Summary: warning: loop exit may only be reached after undefined
                    behavior
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: stuwph at live dot de

gcc -fno-exceptions -Wno-long-long -fno-rtti -ansi -pedantic -DNDEBUG -O3
-DIS_64BIT -DUSE_BSFQ -DUSE_PREFETCH -static -s


In function 'void Bitboards::init()': 
warning: loop exit may only be reached after undefined behavior
[-Waggressive-loop-optimizations] 
for (File f = FILE_A; f <= FILE_H; ++f) 
                        ^ 
note: possible undefined statement is here 
AdjacentFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f
+ 1] : 0);                                            ^



/// Bitboards::init() initializes various bitboard tables. It is called at
/// startup and relies on global objects to be already zero-initialized.

void Bitboards::init() {

  for (Square s = SQ_A1; s <= SQ_H8; ++s)
  {
      SquareBB[s] = 1ULL << s;
      BSFTable[bsf_index(SquareBB[s])] = s;
  }

  for (Bitboard b = 1; b < 256; ++b)
      MS1BTable[b] = more_than_one(b) ? MS1BTable[b - 1] : lsb(b);

  for (File f = FILE_A; f <= FILE_H; ++f)
      FileBB[f] = f > FILE_A ? FileBB[f - 1] << 1 : FileABB;

  for (Rank r = RANK_1; r <= RANK_8; ++r)
      RankBB[r] = r > RANK_1 ? RankBB[r - 1] << 8 : Rank1BB;


/// warning here:

  for (File f = FILE_A; f <= FILE_H; ++f)
      AdjacentFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ?
FileBB[f] : 0);

  for (Rank r = RANK_1; r < RANK_8; ++r)
      InFrontBB[WHITE][r] = ~(InFrontBB[BLACK][r + 1] = InFrontBB[BLACK][r] |
RankBB[r]);

...


*** definitely it is a gcc bug, the warning is wrong.

My guess is that gcc consider that FileBB[f + 1] could reach out of bound when
f == FILE_H, ignoring that out of bound access is guarded by the condition (f <
FILE_H)


*** solution to let the warning disappear:

for (File f = FILE_A; f <= FILE_H; ++f)
AdjacentFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f]
: 0);

[Bug c++/64491] warning: loop exit may only be reached after undefined behavior

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2015-01-04
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Please read https://gcc.gnu.org/bugs/ and provide the missing information.

[Bug c++/64491] warning: loop exit may only be reached after undefined behavior

[joona.kiiski at iki dot fi]

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

joona.kiiski at iki dot fi changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |joona.kiiski at iki dot fi

--- Comment #2 from joona.kiiski at iki dot fi ---
Hi,

My name is Joona Kiiski, I'm one the authors of Stockfish chess software
(https://stockfishchess.org/). This bug was originally reported to us a week
ago. 

After initial analysis it looked obviously like a gcc bug, so we advised the
reporter to raise a bug against GCC. Unfortunately, he wasn't able to give you
nearly enough details. I hope that what I can provide below meets your
expectations:

- Environment: qemu-x86-64 running debian sid
- GCC: Debian snapshot 20141812 5.0

- The bug appears when compiling the Stockfish master branch from
https://github.com/official-stockfish/Stockfish.git with this snapshot.

- For you convenience I've reduced the problem to:

<test.cpp>
int A[8];
int B[8];
int C;

int main() {
    for (int f = 0; f <= 7; ++f)
        A[f] = f;
    for (int f = 0; f <= 7; ++f)
        B[f] = (f > 0 ? A[f - 1] : 0) | (f < 7 ? A[f + 1] : 0);
    C = B[7];
}
</test.cpp>

Compile with

<Makefile>
CXXFLAGS += -O3 -flto
LDFLAGS += $(CXXFLAGS)
test: test.o
    $(CXX) -o $@ test.o $(LDFLAGS)
</Makefile>

Files above are also viewable at
https://github.com/official-stockfish/Stockfis/tree/gcc_bug/src

This produces the bogus warning mentioned in the original bug report.

If you need any further details, please let me know.

Kind Regards,
Joona Kiiski

[Bug c++/64491] warning: loop exit may only be reached after undefined behavior

[joona.kiiski at iki dot fi]

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

--- Comment #3 from joona.kiiski at iki dot fi ---
The correct link is:
https://github.com/official-stockfish/Stockfish/tree/gcc_bug/src

[Bug c++/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[Joost.VandeVondele at mat dot ethz.ch]

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

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
   Last reconfirmed|2015-01-04 00:00:00         |2015-1-10
                 CC|                            |Joost.VandeVondele at mat dot ethz
                   |                            |.ch
            Summary|warning: loop exit may only |[5 Regression] incorrect
                   |be reached after undefined  |warning: loop exit may only
                   |behavior                    |be reached after undefined
                   |                            |behavior
      Known to fail|                            |5.0

--- Comment #4 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> ---
The incorrect warning is confirmed. 

I wonder if this incorrect analysis could lead to wrong code generation.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[joona.kiiski at gmail dot com]

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

--- Comment #5 from joona.kiiski at gmail dot com ---
Thanks for confirming the problem, Joost!

* The original reporter stated that also 4.9 branch is affected, but I
haven't tested this myself. No idea about 4.8 branch.

* Latest gcc stable releases (4.7.4, 4.8.4, 4.9.2) compile Stockfish
without this warning, so I assume that they are not affected.

* For Stockfish, the generated code is correct (despite the wrong analysis
by GCC). However I'm aware that GCC can do some aggressive optimizations in
this area, so in other cases, who knows...


On Sat, Jan 10, 2015 at 4:49 PM, Joost.VandeVondele at mat dot ethz.ch <
gcc-bugzilla@gcc.gnu.org> wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64491
>
> Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:
>
>            What    |Removed                     |Added
>
> ----------------------------------------------------------------------------
>              Status|WAITING                     |NEW
>    Last reconfirmed|2015-01-04 00:00:00         |2015-1-10
>                  CC|                            |Joost.VandeVondele at mat
> dot ethz
>                    |                            |.ch
>             Summary|warning: loop exit may only |[5 Regression] incorrect
>                    |be reached after undefined  |warning: loop exit may
> only
>                    |behavior                    |be reached after undefined
>                    |                            |behavior
>       Known to fail|                            |5.0
>
> --- Comment #4 from Joost VandeVondele <Joost.VandeVondele at mat dot
> ethz.ch> ---
> The incorrect warning is confirmed.
>
> I wonder if this incorrect analysis could lead to wrong code generation.
>
> --
> You are receiving this mail because:
> You are on the CC list for the bug.
>

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[Joost.VandeVondele at mat dot ethz.ch]

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

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.9.2, 4.9.3

--- Comment #6 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> ---
In my testing current 4.9 branch doesn't warn about this.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |5.0

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think this is just a bogus warning introduced in r217891, the generated code
looks ok.
Code like:
  <bb 5>:
  # f_27 = PHI <f_23(4), f_17(8)>
  if (f_27 != 0)
    goto <bb 6>;
  else
    goto <bb 7>;

  <bb 6>:
  _11 = f_27 + -1;
  iftmp.0_12 = A[_11];
  if (f_27 != 7)
    goto <bb 7>;
  else
    goto <bb 8>;

  <bb 7>:
  # iftmp.0_28 = PHI <iftmp.0_12(6), 0(5)>
  _13 = f_27 + 1;
  iftmp.1_14 = A[_13];

  <bb 8>:
  # iftmp.1_4 = PHI <iftmp.1_14(7), 0(6)>
  # iftmp.0_29 = PHI <iftmp.0_28(7), iftmp.0_12(6)>
  _15 = iftmp.0_29 | iftmp.1_4;
  B[f_27] = _15;
  f_17 = f_27 + 1;
  if (f_17 == 8)
    goto <bb 9>;
  else
    goto <bb 5>;
is transformed by dom1 into an extra early exit from the loop, if f_27 == 7, we
jump to a new bb outside of the loop that does:
  <bb 11>:
  # iftmp.1_2 = PHI <0(6)>
  # iftmp.0_3 = PHI <iftmp.0_12(6)>
  _1 = iftmp.0_3 | iftmp.1_2;
  B[f_27] = _1;
  f_26 = f_27 + 1;
  goto <bb 10>;
But indeed dom nor anything else doesn't figure out that the f_17 == 8
exit condition of the loop is then never true, the loop will always exit
through the jump to bb 11.
Supposedly the warning needs to be limited to the case where the loop has only
a single exit, or when the undefined behavior occurs on all loop exits.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[ams at gcc dot gnu.org]

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

--- Comment #8 from Andrew Stubbs <ams at gcc dot gnu.org> ---
Just silencing the warning may not be enough. The compiler may optimize away
loop exit conditions based on this analysis. The warning mirrors the logic
rather than shares it (due to the way the logic is distributed) so this may not
actually be a problem, in this case, but I'd have to look closer.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Andrew Stubbs from comment #8)
> Just silencing the warning may not be enough. The compiler may optimize away
> loop exit conditions based on this analysis. The warning mirrors the logic
> rather than shares it (due to the way the logic is distributed) so this may
> not actually be a problem, in this case, but I'd have to look closer.

Sure, it is desirable if the compiler optimizes away the loop exit test, it
really is dead, because the loop will always be exit through the other loop
exit earlier.  But there is no user bug in there, so you shouldn't emit a false
positive.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[ams at gcc dot gnu.org]

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

--- Comment #10 from Andrew Stubbs <ams at gcc dot gnu.org> ---
I'm trying to look at this problem, but so far all my builds are failing.
Probably I have some local cruft.

In the meantime, the workaround is to use -Wno-aggressive-loop-optimizations, I
think.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[ams at gcc dot gnu.org]

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

--- Comment #11 from Andrew Stubbs <ams at gcc dot gnu.org> ---
The compiler has constructed the loop such that it reads like this:

f = 0;
tmp = 0;
do {
  B[f] = tmp | A[f + 1];
  if (f + 1 == 8)
    break;

  if (f + 1 > 0)
    tmp = A[f];

  if (f + 1 == 7) {
    B[f + 1] = tmp;
    break;
  }

  f++;
} while (1);

It calculates the upper bound for f to be 7, which would make f + 1 a problem.
maybe_lower_iteration_bound then correctly identifies this, and reduces the
upper bound to 6. Consequently, the unnecessary "if (f + 1 == 8)" is removed,
and all is well with the world.

The problem is that leaves no path, from the loop header, that reaches a loop
exit without passing the "undefined" statement.

This makes it difficult to tell the difference between UB in the source code,
and this temporary UB introduced by the compiler. I've no idea why the bounds
are reduced here, rather than set properly in the first place?

I've tried only warning when *all* the exit routes are to be removed, but
they're not all listed in loop->bounds, so I'm stuck.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[jakub at gcc dot gnu.org]

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
One possibility is just not to warn at all about loops with multiple exits,
because for those you have no guarantee the iteration that triggers undefined
behavior will be ever encountered.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |diagnostic
           Priority|P3                          |P2

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[jakub at gcc dot gnu.org]

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

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So perhaps we just can't warn for your testcase, if we can't detect it
reliably.

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[ams at gcc dot gnu.org]

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

--- Comment #16 from Andrew Stubbs <ams at gcc dot gnu.org> ---
Author: ams
Date: Wed Mar 18 14:27:13 2015
New Revision: 221492

URL: https://gcc.gnu.org/viewcvs?rev=221492&root=gcc&view=rev
Log:
Fix PR64491

2015-03-18  Andrew Stubbs  <ams@codesourcery.com>

    PR middle-end/64491
    Revert:
    2014-11-20  Andrew Stubbs  <ams@codesourcery.com>

    * tree-ssa-loop-niter.c (maybe_lower_iteration_bound): Warn if a loop
    condition would be removed due to undefined behaviour.

2015-03-18  Andrew Stubbs  <ams@codesourcery.com>

    PR middle-end/64491
    Revert:
    2014-11-20  Andrew Stubbs  <ams@codesourcery.com>

    * gcc.dg/undefined-loop-1.c: New file.
    * gcc.dg/undefined-loop-2.c: New file.

    2014-12-24  Andrew Stubbs  <ams@codesourcery.com>

    PR testsuite/64032
    * gcc.dg/undefined-loop-2.c: Don't allow GCC to optimize away the
    loop exits too early.

Removed:
    trunk/gcc/testsuite/gcc.dg/undefined-loop-1.c
    trunk/gcc/testsuite/gcc.dg/undefined-loop-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-niter.c

[Bug middle-end/64491] [5 Regression] incorrect warning: loop exit may only be reached after undefined behavior

[ams at gcc dot gnu.org]

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

Andrew Stubbs <ams at gcc dot gnu.org> changed:

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

--- Comment #17 from Andrew Stubbs <ams at gcc dot gnu.org> ---
Patch reverted; problem fixed.