[Bug tree-optimization/63841] New: Incorrect strlen optimization after complete unroll

[Bug tree-optimization/63841] New: Incorrect strlen optimization after complete unroll

[tejohnson at google dot com]

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

            Bug ID: 63841
           Summary: Incorrect strlen optimization after complete unroll
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tejohnson at google dot com

The following test fails with trunk:

$ cat bug_test.cc
#include <cstdio>
#include <cassert>
#include <string>

std::string __attribute__ ((noinline)) comp_test_write() {
  std::string data;

  for (int i = 0; i < 2; ++i) {
    char b = 1 >> (i * 8);
    data.append(&b, 1);
  }

  return data;
}

std::string __attribute__ ((noinline)) comp_test_write_good() {
  std::string data;

  char b;
  for (int i = 0; i < 2; ++i) {
    b = 1 >> (i * 8);
    data.append(&b, 1);
  }

  return data;
}

int main() {
  std::string bad = comp_test_write();
  printf("BAD: %hx\n", *(short*)bad.c_str());

  std::string good = comp_test_write_good();
  printf("GOOD: %hx\n", *(short*)good.c_str());

  return good != bad;
}

% g++ bug_test.cc -O2 
% a.out
BAD: 101
GOOD: 1

Notice that the difference between comp_test_write_good (GOOD) and
comp_test_write (BAD) is that declaration "char b" is moved outside the loop in
the good case.

In both cases cunrolli completely unrolls the loop. The main difference is that
there is a clobber at the start of the second unrolled iteration in the bad
case:

   # .MEM_26 = VDEF <.MEM_25>
  bD.13054 ={v} {CLOBBER};
  [./bug_test2.cc : 8:3] # DEBUG iD.13053 => 1
  # DEBUG iD.13053 => 1
  [./bug_test2.cc : 9:25] # .MEM_33 = VDEF <.MEM_26>
  bD.13054 = 0;
  [./bug_test2.cc : 10:23] [LP 2] # .MEM_34 = VDEF <.MEM_33>
  # USE = nonlocal null { D.12110 D.13054 D.13371 } (glob)
  # CLB = nonlocal null { D.12110 D.13054 D.13371 } (glob)
  _ZNSs6appendEPKcmD.11551 (data_4(D), &bD.13054, 1);

Above is the code just before tree-strlen. The tree-strlen removes the
"bD.13054 = 0" incorrectly. If I compile with -fdisable-tree-strlen the test
passes.

I tracked this down to the code in handle_char_store in tree-ssa-strlen.c with
the following comment:

              /* When storing '\0', the store can be removed
                 if we know it has been stored in the current function.  */

When we hit this routine for the store "bD.13054 = 0" there is a saved strinfo
struct that indicates there was a store to this string with length 0, and it
thinks it is safe to remove this null termination store.

The strinfo struct was created during the prior call to handle_char_store for
store "bD.13054 ={v} {CLOBBER}". It is created with length zero because
initializer_zerop returns true for the RHS. The reason initializer_zerop
returns true is that the RHS is a constructor with 0 length. Therefore this
code in initializer_zerop:
        FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
          if (!initializer_zerop (elt))
            return false;
        return true;
falls through to the "return true" without executing any loop iterations.

A couple possible solutions that all work:
1) handle_char_store does not consider the store RHS to be a zero
initialization if the statement is a clobber.
2) initializer_zerop returns false if the constructor is a clobber
3) initializer_zerop returns false if there are no elements in the constructor
array.

It seems to me like #3 is the correct solution - I don't think an empty
constructor should be considered a zero initialization. The regression tests
pass with that change so I will send it for review

[Bug tree-optimization/63841] Incorrect strlen optimization after complete unroll

[tejohnson at google dot com]

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

--- Comment #1 from Teresa Johnson <tejohnson at google dot com> ---
Google ref b/18344370

[Bug tree-optimization/63841] Incorrect strlen optimization after complete unroll

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-11-13
                 CC|                            |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  Seems to be an opportunity to remove the clobber to be able to
remove a dead store... ;)

[Bug tree-optimization/63841] [4.8/4.9/5 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at google dot com]

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

--- Comment #4 from Teresa Johnson <tejohnson at google dot com> ---
On Thu, Nov 13, 2014 at 1:27 AM, jakub at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63841
>
> Jakub Jelinek <jakub at gcc dot gnu.org> changed:
>
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>              Status|NEW                         |ASSIGNED
>            Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
>    Target Milestone|---                         |4.8.4
>             Summary|Incorrect strlen            |[4.8/4.9/5 Regression]
>                    |optimization after complete |Incorrect strlen
>                    |unroll                      |optimization after complete
>                    |                            |unroll
>
> --- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> Started with r181172.  I'll take a look during stage3.

I have a fix under review:
https://gcc.gnu.org/ml/gcc-patches/2014-11/msg01481.html

Teresa

>
> --
> You are receiving this mail because:
> You are on the CC list for the bug.
> You reported the bug.

[Bug tree-optimization/63841] [4.8/4.9/5 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at gcc dot gnu.org]

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

--- Comment #5 from tejohnson at gcc dot gnu.org ---
Author: tejohnson
Date: Thu Nov 13 15:36:48 2014
New Revision: 217505

URL: https://gcc.gnu.org/viewcvs?rev=217505&root=gcc&view=rev
Log:
2014-11-13  Teresa Johnson  <tejohnson@google.com>

gcc:
    PR tree-optimization/63841
    * tree.c (initializer_zerop): A clobber does not zero initialize.

gcc/testsuite:
    PR tree-optimization/63841
    * g++.dg/tree-ssa/pr63841.C: New test.

Added:
    trunk/gcc/testsuite/g++.dg/tree-ssa/pr63841.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree.c

[Bug tree-optimization/63841] [4.8/4.9/5 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at gcc dot gnu.org]

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

--- Comment #6 from tejohnson at gcc dot gnu.org ---
Author: tejohnson
Date: Thu Nov 13 21:51:11 2014
New Revision: 217522

URL: https://gcc.gnu.org/viewcvs?rev=217522&root=gcc&view=rev
Log:
2014-11-13  Teresa Johnson  <tejohnson@google.com>

gcc:
    PR tree-optimization/63841
    * tree-ssa-strlen.c (strlen_optimize_stmt): Ignore clobbers.

2014-11-13  Teresa Johnson  <tejohnson@google.com>

gcc/testsuite:
    PR tree-optimization/63841
    * testsuite/g++.dg/tree-ssa/pr63841.C: New test.

Added:
    branches/gcc-4_9-branch/gcc/testsuite/g++.dg/tree-ssa/pr63841.C
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_9-branch/gcc/tree-ssa-strlen.c

[Bug tree-optimization/63841] [4.8/4.9/5 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at gcc dot gnu.org]

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

--- Comment #7 from tejohnson at gcc dot gnu.org ---
Author: tejohnson
Date: Fri Nov 14 06:35:35 2014
New Revision: 217537

URL: https://gcc.gnu.org/viewcvs?rev=217537&root=gcc&view=rev
Log:
2014-11-13  Teresa Johnson  <tejohnson@google.com>

gcc:
    PR tree-optimization/63841
    * tree-ssa-strlen.c (strlen_optimize_stmt): Ignore clobbers.

2014-11-13  Teresa Johnson  <tejohnson@google.com>

gcc/testsuite:
    PR tree-optimization/63841
    * g++.dg/tree-ssa/pr63841.C: Remove prints, use abort.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/g++.dg/tree-ssa/pr63841.C
    trunk/gcc/tree-ssa-strlen.c

[Bug tree-optimization/63841] [4.8/4.9/5 Regression] Incorrect strlen optimization after complete unroll

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
           Assignee|jakub at gcc dot gnu.org           |unassigned at gcc dot gnu.org

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed by Teresa.

[Bug tree-optimization/63841] [4.8 Regression] Incorrect strlen optimization after complete unroll

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
      Known to work|                            |4.9.3, 5.0
         Resolution|FIXED                       |---
            Summary|[4.8/4.9/5 Regression]      |[4.8 Regression] Incorrect
                   |Incorrect strlen            |strlen optimization after
                   |optimization after complete |complete unroll
                   |unroll                      |

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Ah, though not on the 4.8 branch.

[Bug tree-optimization/63841] [4.8 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at google dot com]

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

--- Comment #10 from Teresa Johnson <tejohnson at google dot com> ---
Missed that one, I will backport to 4.8.
Teresa

On Mon, Nov 17, 2014 at 1:17 PM, jakub at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63841
>
> Jakub Jelinek <jakub at gcc dot gnu.org> changed:
>
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>              Status|RESOLVED                    |REOPENED
>       Known to work|                            |4.9.3, 5.0
>          Resolution|FIXED                       |---
>             Summary|[4.8/4.9/5 Regression]      |[4.8 Regression] Incorrect
>                    |Incorrect strlen            |strlen optimization after
>                    |optimization after complete |complete unroll
>                    |unroll                      |
>
> --- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> Ah, though not on the 4.8 branch.
>
> --
> You are receiving this mail because:
> You are on the CC list for the bug.
> You reported the bug.

[Bug tree-optimization/63841] [4.8 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at gcc dot gnu.org]

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

--- Comment #11 from tejohnson at gcc dot gnu.org ---
Author: tejohnson
Date: Tue Nov 18 14:20:58 2014
New Revision: 217715

URL: https://gcc.gnu.org/viewcvs?rev=217715&root=gcc&view=rev
Log:
2014-11-18  Teresa Johnson  <tejohnson@google.com>

    Backport from mainline and gcc-4_9 branch.

    2014-11-13  Teresa Johnson  <tejohnson@google.com>

    PR tree-optimization/63841
    * tree-ssa-strlen.c (strlen_optimize_stmt): Ignore clobbers.

    2014-11-13  Teresa Johnson  <tejohnson@google.com>

    PR tree-optimization/63841
    * testsuite/g++.dg/tree-ssa/pr63841.C: New test.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/g++.dg/tree-ssa/pr63841.C
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-ssa-strlen.c

[Bug tree-optimization/63841] [4.8 Regression] Incorrect strlen optimization after complete unroll

[tejohnson at gcc dot gnu.org]

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

--- Comment #12 from tejohnson at gcc dot gnu.org ---
Author: tejohnson
Date: Thu Nov 20 14:29:41 2014
New Revision: 217858

URL: https://gcc.gnu.org/viewcvs?rev=217858&root=gcc&view=rev
Log:
2014-11-20  Teresa Johnson  <tejohnson@google.com>

    Backport r217522 from gcc-4_9 for Google ref b/18344370 and b/18455179.

    2014-11-13  Teresa Johnson  <tejohnson@google.com>

    PR tree-optimization/63841
    * tree-ssa-strlen.c (strlen_optimize_stmt): Ignore clobbers.

    2014-11-13  Teresa Johnson  <tejohnson@google.com>

    PR tree-optimization/63841
    * testsuite/g++.dg/tree-ssa/pr63841.C: New test.

Added:
    branches/google/gcc-4_9/gcc/testsuite/g++.dg/tree-ssa/pr63841.C
Modified:
    branches/google/gcc-4_9/gcc/tree-ssa-strlen.c

[Bug tree-optimization/63841] [4.8 Regression] Incorrect strlen optimization after complete unroll

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.