[Bug tree-optimization/60577] New: inefficient FDO instrumentation code

[Bug tree-optimization/60577] New: inefficient FDO instrumentation code

[carrot at google dot com]

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

            Bug ID: 60577
           Summary: inefficient FDO instrumentation code
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: carrot at google dot com

This is actually a regression caused by r175916.

Compile the following code with options -O2 -fno-strict-aliasing
-fprofile-generate


struct thread_param
{
  long* buf;
  long iterations;
  long accesses;
} param;

void access_buf(struct thread_param* p)
{
  long i,j;
  long iterations = p->iterations;
  long accesses = p->accesses;
  for (i=0; i<iterations; i++)
  {
    long* pbuf = p->buf;
    for (j=0; j<accesses; j++)
      pbuf[j] += 1;
  }
}



Trunk gcc generates following for innermost loop:

.L9:
        addq    $1, __gcov0.access_buf(%rip)
        addq    $1, (%rax)
        addq    $8, %rax
        cmpq    %rdx, %rax
        jne     .L9

The fdo counter in memory is incremented in each iteration.



GCC at revision r175915 generates following for innermost loop

        movq    .LPBX1(%rip), %rsi
    ...
.L4:
        addq    $1, (%rax)
        addq    $8, %rax
        cmpq    %rdx, %rax
        jne     .L4
        leaq    1(%rsi,%r9), %rsi
    ...
    movq    %rsi, .LPBX1(%rip)

The fdo counter doesn't bring any overhead to the innermost loop.



GCC at revision r175916 generates following for innermost loop

        movq    .LPBX1(%rip), %rcx
        xorl    %eax, %eax
        leaq    1(%rcx), %r8 
        .p2align 4,,10
        .p2align 3
.L4:
        leaq    (%r8,%rax), %rcx
        movq    %rcx, .LPBX1(%rip)
        addq    $1, (%rdx,%rax,8)
        addq    $1, %rax
        cmpq    %rsi, %rax
        jne     .L4

The fdo counter is incremented and written to memory in each iteration.

[Bug tree-optimization/60577] [4.9 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2014-03-19
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Target Milestone|---                         |4.9.0
            Summary|inefficient FDO             |[4.9 Regression]
                   |instrumentation code        |inefficient FDO
                   |                            |instrumentation code
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/60577] [4.7/4.8/4.9 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nathan at acm dot org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
In 4.6 for some unknown reason we are able to disambiguate

  *.LPBX1[0] and p_3(D)->buf and *D.1606_14

we built the static decls with !TREE_ADDRESSABLE, but starting with
4.7 we unconditionally set TREE_ADDRESSABLE on the decl (which formerly
was only set in case we asked for the address of it via
tree_coverage_counter_addr).

This happened with the big re-org in r181105 but undoing that change
does not fix the regression.  This is because the TREE_ADDRESSABLE
flag is set again in canonicalize_constructor_val:

#0  0x0000000000932775 in canonicalize_constructor_val (
    cval=<addr_expr 0x7ffff6d74900>, from_decl=<tree 0x0>)
    at /space/rguenther/src/svn/trunk/gcc/gimple-fold.c:207
#1  0x0000000000798015 in record_reference (tp=0x7ffff6d73698, 
    walk_subtrees=0x7fffffffd858, data=0x7fffffffdb50)
    at /space/rguenther/src/svn/trunk/gcc/cgraphbuild.c:62
#2  0x0000000000e6859f in walk_tree_1 (tp=0x7ffff6d73698, 
    func=0x797fdd <record_reference(tree*, int*, void*)>, data=0x7fffffffdb50, 
    pset=0x1ea9240, lh=0x0) at /space/rguenther/src/svn/trunk/gcc/tree.c:10921
#3  0x0000000000e6892c in walk_tree_1 (tp=0x7ffff6d736d0, 
    func=0x797fdd <record_reference(tree*, int*, void*)>, data=0x7fffffffdb50, 
    pset=0x1ea9240, lh=0x0) at /space/rguenther/src/svn/trunk/gcc/tree.c:10998
#4  0x0000000000e6892c in walk_tree_1 (tp=0x7ffff6d78808, 
    func=0x797fdd <record_reference(tree*, int*, void*)>, data=0x7fffffffdb50, 
    pset=0x1ea9240, lh=0x0) at /space/rguenther/src/svn/trunk/gcc/tree.c:10998
#5  0x0000000000e6892c in walk_tree_1 (tp=0x7ffff6d788a0, 
    func=0x797fdd <record_reference(tree*, int*, void*)>, data=0x7fffffffdb50, 
    pset=0x1ea9240, lh=0x0) at /space/rguenther/src/svn/trunk/gcc/tree.c:10998
#6  0x0000000000798d82 in record_references_in_initializer (
    decl=<var_decl 0x7ffff6d78850 __gcov_.access_buf>, only_vars=false)
    at /space/rguenther/src/svn/trunk/gcc/cgraphbuild.c:435
#7  0x0000000000eac7fa in varpool_analyze_node (node=0x7ffff6d498f0)
    at /space/rguenther/src/svn/trunk/gcc/varpool.c:398

thus we _do_ take the address of the variable, from the global
constructor of __gcov.access_buf which looks like

{.D.1783=&*.LPBX0, .D.1784=1, .D.1785=4186437761, .D.1786=449688241,
.D.1787={{.D.1780=3, .D.1781=&__gcov0.access_buf}, {.D.1780=1,
.D.1781=&__gcov8.access_buf}}}

thus indeed p->buf may point to __gcov0.access_buf[1] and we can't optimize
those accesses.  This object was simply not present in GCC 4.6 and thus
TREE_ADDRESSABLE was never set and thus we could optimize this.

Which means the revision cited doesn't cause the regression (I highly doubt
so at least), but instead whoever added code to build that record or
whoever added code to record references in initializers (and set
TREE_ADDRESSABLE in that path... - coverage.c fails to do that and builds
a lot of addresses from the counters in places).

The idea of canonicalize_constructor_value is that the result will end up
in actual stmts, thus the addressable flag is important.  In this case
we only record references for the IPA references struct - thus setting
the flag there isn't important (well, that's not entirely true ... alias
disambiguation depends on the order of processing functions then).

Fixing both fixes the regression.

Index: gcc/coverage.c
===================================================================
--- gcc/coverage.c      (revision 208642)
+++ gcc/coverage.c      (working copy)
@@ -466,6 +466,8 @@ tree_coverage_counter_addr (unsigned cou
   gcc_assert (no < fn_n_ctrs[counter] - fn_b_ctrs[counter]);
   no += fn_b_ctrs[counter];

+  TREE_ADDRESSABLE (fn_v_ctrs[counter]) = 1;
+
   /* "no" here is an array index, scaled to bytes later.  */
   return build_fold_addr_expr (build4 (ARRAY_REF, gcov_type_node,
                                       fn_v_ctrs[counter],
@@ -720,7 +722,6 @@ build_var (tree fn_decl, tree type, int
   memcpy (buf + len, fn_name, fn_name_len + 1);
   DECL_NAME (var) = get_identifier (buf);
   TREE_STATIC (var) = 1;
-  TREE_ADDRESSABLE (var) = 1;
   DECL_ALIGN (var) = TYPE_ALIGN (type);

   return var;
Index: gcc/gimple-fold.h
===================================================================
--- gcc/gimple-fold.h   (revision 208642)
+++ gcc/gimple-fold.h   (working copy)
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.
 #ifndef GCC_GIMPLE_FOLD_H
 #define GCC_GIMPLE_FOLD_H

+extern tree canonicalize_constructor_val_1 (tree, tree, bool);
 extern tree canonicalize_constructor_val (tree, tree);
 extern tree get_symbol_constant_value (tree);
 extern void gimplify_and_update_call_from_tree (gimple_stmt_iterator *, tree);
Index: gcc/gimple-fold.c
===================================================================
--- gcc/gimple-fold.c   (revision 208642)
+++ gcc/gimple-fold.c   (working copy)
@@ -169,7 +169,8 @@ can_refer_decl_in_current_unit_p (tree d
    FROM_DECL (if non-NULL) specify variable whose constructor contains CVAL. 
*/

 tree
-canonicalize_constructor_val (tree cval, tree from_decl)
+canonicalize_constructor_val_1 (tree cval, tree from_decl,
+                               bool mark_addressable)
 {
   tree orig_cval = cval;
   STRIP_NOPS (cval);
@@ -203,7 +204,8 @@ canonicalize_constructor_val (tree cval,
           || TREE_CODE (base) == FUNCTION_DECL)
          && !can_refer_decl_in_current_unit_p (base, from_decl))
        return NULL_TREE;
-      if (TREE_CODE (base) == VAR_DECL)
+      if (TREE_CODE (base) == VAR_DECL
+         && mark_addressable)
        TREE_ADDRESSABLE (base) = 1;
       else if (TREE_CODE (base) == FUNCTION_DECL)
        {
@@ -225,6 +227,12 @@ canonicalize_constructor_val (tree cval,
   return orig_cval;
 }

+tree
+canonicalize_constructor_val (tree cval, tree from_decl)
+{
+  return canonicalize_constructor_val_1 (cval, from_decl, true);
+}
+
 /* If SYM is a constant variable with known value, return the value.
    NULL_TREE is returned otherwise.  */


but I am not sure this is a valid thing to do... (I can imagine producing
a testcase that breaks with the delayed TREE_ADDRESSABLE setting)

Why do we have to record addresses of these arrays?

[Bug tree-optimization/60577] [4.7/4.8/4.9 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So - if we delay marking any decl addressable during IPA reference recording
then we need an IPA pass that computes whether any of the taken IPA_REF_ADDR
may leak into the IL.  We need to do that conservatively before any alias
queries (thus eventually again at WPA stage to optimize more).

So if there isn't any reference to __gcov_.access_buf inside the program
this would make us optimize things again.

But there is one from .LPBX1 in the testcase which is refered to from .LPBX0
which is refered from _GLOBAL__sub_I_65535_0_access_buf, so it doesn't
help ... (and it seems it really is necessary to have those addresses)

Considering LTO-ing libgcov there is no way we can magically mark those decls
to be disregarded from alias analysis either.

Which leaves the possibility of more cleverly instrumenting the program
in the first place ...

[Bug tree-optimization/60577] [4.7/4.8/4.9 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> Which leaves the possibility of more cleverly instrumenting the program
> in the first place ...

Which shouldn't be so hard as we are in SSA form and have loop structures
set up.  But it's of course "old" code (profile.c:branch_prob) which was
written with "only" a CFG in mind.  Unfortunately the code chooses
to instrument a non-latch edge in the testcase (loop latches would have
been easy to special-case in gimple_gen_edge_profiler).  This is the
other edge out of a block with a loop exit - so we can special-case
single-exit loops that have such edge instrumented where the edge source
dominates the loop latch.  Or find some even more clever way of placing
the loads / stores (you can always use a scalar as counter and load/store
in a dominating / post-dominating block of course, but that may have
detrimental effects on register pressure ...).  Maybe still do that, but
only if the counter update is in a loop.  Note that applying store motion
here may introduce no-op load/store which may have issues with thread
safety.

[Bug tree-optimization/60577] [4.7/4.8/4.9 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32393
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32393&action=edit
hack

Like this (hack alert).  Applies store motion one level for a restricted set
of loops.  Requires us to add preheaders and record exits (and disambiguate
multiple latches) and compute dominators.

[Bug tree-optimization/60577] [4.7/4.8/4.9 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32403
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32403&action=edit
alternative patch

This restores previous behavior by considering all coverage/profile related
counters to not alias with any other access through a pointer.

[Bug tree-optimization/60577] [4.7/4.8 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.9.0
            Summary|[4.7/4.8/4.9 Regression]    |[4.7/4.8 Regression]
                   |inefficient FDO             |inefficient FDO
                   |instrumentation code        |instrumentation code

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

[Bug tree-optimization/60577] [4.7/4.8 Regression] inefficient FDO instrumentation code

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Mar 21 11:52:50 2014
New Revision: 208746

URL: http://gcc.gnu.org/viewcvs?rev=208746&root=gcc&view=rev
Log:
2014-03-21  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/60577
    * tree-core.h (struct tree_base): Document nothrow_flag use
    in VAR_DECL_NONALIASED.
    * tree.h (VAR_DECL_NONALIASED): New.
    (may_be_aliased): Adjust.
    * coverage.c (build_var): Set VAR_DECL_NONALIASED.

    * gcc.dg/tree-ssa/ssa-lim-11.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-11.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/coverage.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-core.h
    trunk/gcc/tree.h

[Bug tree-optimization/60577] [4.7/4.8 Regression] inefficient FDO instrumentation code

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.0                       |4.9.1

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.0 has been released

[Bug tree-optimization/60577] [4.8 Regression] inefficient FDO instrumentation code

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.1                       |4.9.2

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.1 has been released.

[Bug tree-optimization/60577] [4.8 Regression] inefficient FDO instrumentation code

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.2                       |4.9.3

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.2 has been released.