[Bug tree-optimization/66610] New: Compound assignments prevent value-numbering optimization

[Bug tree-optimization/66610] New: Compound assignments prevent value-numbering optimization

[dmalcolm at gcc dot gnu.org]

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

            Bug ID: 66610
           Summary: Compound assignments prevent value-numbering
                    optimization
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dmalcolm at gcc dot gnu.org
  Target Milestone: ---

Created attachment 35818
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35818&action=edit
Minimal testcase demonstrating the issue

libgccjit showed poor performance relative to a LLVM backend within an
experimental JIT-compiler for Lua (https://github.com/dibyendumajumdar/ravi).

On investigation it appears to be due to unions and structs stopping
value-numbering from working.

I'm attaching a minimal reproducer for the issue.

If the code copies the struct and the union within it field-wise, pass_fre
(tree-ssa-pre.c) uses value numbering to eliminate the copy of the loop index
through *arr, and turns loop_using_union_field_assignment into:

  loop_using_union_field_assignment (int num_iters, struct s * arr)
  {
    int i;

    <bb 2>:
    goto <bb 4>;

    <bb 3>:
    arr_6(D)->union_field.int_field = i_1;
    MEM[(struct s *)arr_6(D) + 4B].union_field.int_field = i_1;
    i_11 = i_1 + 1;

    <bb 4>:
    # i_1 = PHI <0(2), i_11(3)>
    if (i_1 < num_iters_5(D))
      goto <bb 3>;
    else
      goto <bb 5>;

    <bb 5>:
    return;
  }

and the loop is eliminated altogether by cddce2.

However, if the code does a compound copy, pass_fre doesn't eliminate the copy
of the loop index and the loop can't be eliminated (with a big performance
loss); in the example, functions "loop_using_struct_assignment" and
"loop_using_union_assignment" fail to have their loops optimized away at -O3.

Hence the libgccjit user has patched things at their end to direct copying the
fields (fwiw their workaround was this commit
https://github.com/dibyendumajumdar/ravi/commit/a5b192cd4f4213cd544e31b08b02eb9082142b20
)

Should compound assignments be optimizable via value-numbering?  Would it make
sense to split out the compound assignments field-wise internally before doing
value-numbering?

This is all with gcc trunk (r224625 aka
e3a904dbdc78cb45b98e8b109e0e49e759315b7c) on x86_64 at -O3.

[Bug tree-optimization/66610] Compound assignments prevent value-numbering optimization with unions

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
            Summary|Compound assignments        |Compound assignments
                   |prevent value-numbering     |prevent value-numbering
                   |optimization                |optimization with unions

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
IIRC VN has some struct copy infrastructure which could be used here but unions
are special and that might the cause.

[Bug tree-optimization/66610] Compound assignments prevent value-numbering optimization with unions

[dmalcolm at gcc dot gnu.org]

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

--- Comment #2 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Created attachment 35820
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35820&action=edit
A less minimal example

FWIW, here's a less minimal example, better showing what the code was doing
(interpreter values were a union plus a type code).

As in the previous example, fre2 is able to do this optimization of the copy of
arr[1] to arr[0] when doing the copy field-wise:
  Replaced arr_6(D)->union_field.int_field with i_1 in all uses of _10 =
arr_6(D)->union_field.int_field;
  Replaced arr_6(D)->type_code with 0 in all uses of _13 = arr_6(D)->type_code;

turning the loop body into:
  <bb 3>:
  arr_6(D)->union_field.int_field = i_1;
  arr_6(D)->type_code = 0;
  MEM[(struct value *)arr_6(D) + 16B].union_field.int_field = i_1;
  MEM[(struct value *)arr_6(D) + 16B].type_code = 0;
  i_15 = i_1 + 1;

allowing the loop to later be optimized away by cddce2.

[Bug tree-optimization/66610] Aggregate assignment prevents store-motion

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-06-22
                 CC|                            |rguenth at gcc dot gnu.org
            Summary|Compound assignments        |Aggregate assignment
                   |prevent value-numbering     |prevents store-motion
                   |optimization with unions    |
     Ever confirmed|0                           |1

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
This isn't about value-numbering but about sinking the stores out of the loop
(so it becomes empty).  For the field case it is loop store motion that
performs this conditional(!?) movement.  For the non-field cases it determines
a dependence:

Memory reference 1: arr_5(D)->union_field.int_field
Unanalyzed memory reference 0: MEM[(struct s *)arr_5(D) + 4B].union_field =
arr_5(D)->union_field;
Querying dependencies of ref 1 in loop 1: dependent

because it doesn't handle aggregate assignments (simple_mem_ref_in_stmt
fails).

Confirmed.

[Bug tree-optimization/66610] Aggregate assignment prevents store-motion

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |99728

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
PR99728 is similar, but I think that store-motion itself is the wrong place to
"tear apart" aggregate assignments.  Taking the first example from the
testcase:

/* This loop doesn't get optimized away.  */
void
loop2_using_struct_assignment (int num_iters, struct value *arr)
{
  int i;
  for (i = 0; i < num_iters; i++)
    {
      arr[0].union_field.int_field = i;
      arr[0].type_code             = TYPE_CODE_INT;
      arr[1] = arr[0];
    }
}

the aggregate assignment could be sunk out of the loop but then this moves
loads later which store-motion does not do in general.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99728
[Bug 99728] code pessimization when using wrapper classes around SIMD types