Bug 63841 - [4.8 Regression] Incorrect strlen optimization after complete unroll
Summary: [4.8 Regression] Incorrect strlen optimization after complete unroll
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 5.0
: P3 normal
Target Milestone: 4.8.4
Assignee: Not yet assigned to anyone
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2014-11-12 22:00 UTC by Teresa Johnson
Modified: 2014-12-10 13:16 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.9.3, 5.0
Known to fail:
Last reconfirmed: 2014-11-13 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Teresa Johnson 2014-11-12 22:00:22 UTC
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
Comment 1 Teresa Johnson 2014-11-12 22:00:53 UTC
Google ref b/18344370
Comment 2 Richard Biener 2014-11-13 09:20:01 UTC
Confirmed.  Seems to be an opportunity to remove the clobber to be able to remove a dead store... ;)
Comment 3 Jakub Jelinek 2014-11-13 09:27:19 UTC
Started with r181172.  I'll take a look during stage3.
Comment 4 Teresa Johnson 2014-11-13 14:27:06 UTC
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.
Comment 5 tejohnson 2014-11-13 15:37:20 UTC
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
Comment 6 tejohnson 2014-11-13 21:51:43 UTC
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
Comment 7 tejohnson 2014-11-14 06:36:07 UTC
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
Comment 8 Jakub Jelinek 2014-11-17 21:16:43 UTC
Fixed by Teresa.
Comment 9 Jakub Jelinek 2014-11-17 21:17:49 UTC
Ah, though not on the 4.8 branch.
Comment 10 Teresa Johnson 2014-11-17 21:27:47 UTC
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.
Comment 11 tejohnson 2014-11-18 14:21:30 UTC
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
Comment 12 tejohnson 2014-11-20 14:30:13 UTC
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
Comment 13 Richard Biener 2014-12-10 13:16:47 UTC
Fixed.