[Bug tree-optimization/64601] New: Missed PRE on std::vector move assignment

[Bug tree-optimization/64601] New: Missed PRE on std::vector move assignment

[glisse at gcc dot gnu.org]

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

            Bug ID: 64601
           Summary: Missed PRE on std::vector move assignment
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org

Comparing these 2 ways (not necessarily 100% equivalent) to move a std::vector,
we generate significantly better code for f than for g, which is not really
what users expect.

#include <vector>
#include <utility>

typedef std::vector<int> V;
void f(V&v,V&w){
  V(std::move(w)).swap(v);
}
void g(V&v,V&w){
  v=std::move(w);
}


For f (good code):

  <bb 2>:
  _3 = MEM[(int * &)w_2(D)];
  MEM[(int * &)w_2(D)] = 0B;
  _6 = MEM[(int * &)w_2(D) + 8];
  MEM[(int * &)w_2(D) + 8] = 0B;
  _7 = MEM[(int * &)w_2(D) + 16];
  MEM[(int * &)w_2(D) + 16] = 0B;
  _8 = MEM[(int * &)v_4(D)];
  MEM[(int * &)v_4(D)] = _3;
  MEM[(int * &)v_4(D) + 8] = _6;
  MEM[(int * &)v_4(D) + 16] = _7;
  if (_8 != 0B)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  operator delete (_8); [tail call]

  <bb 4>:
  return;


While for g (not as good):

  <bb 2>:
  __tmp.0_5 = MEM[(int * &)v_4(D)];
  MEM[(int * &)v_4(D)] = 0B;
  MEM[(int * &)v_4(D) + 8] = 0B;
  MEM[(int * &)v_4(D) + 16] = 0B;
  _6 = MEM[(int * &)w_2(D)];
  MEM[(int * &)v_4(D)] = _6;
  MEM[(int * &)w_2(D)] = 0B;
  __tmp.0_7 = MEM[(int * &)v_4(D) + 8];
  _8 = MEM[(int * &)w_2(D) + 8];
  MEM[(int * &)v_4(D) + 8] = _8;
  MEM[(int * &)w_2(D) + 8] = __tmp.0_7;
  __tmp.0_9 = MEM[(int * &)v_4(D) + 16];
  _10 = MEM[(int * &)w_2(D) + 16];
  MEM[(int * &)v_4(D) + 16] = _10;
  MEM[(int * &)w_2(D) + 16] = __tmp.0_9;
  if (__tmp.0_5 != 0B)
  [...]

The first really surprising line is the definition of __tmp.0_7 (always 0). Gcc
should know that the stores to v+0 and v+16 don't alias v+8 (same base, known
size+offset), and it should also know that w+0 and v+8 don't alias (same base
type, different fields). I am wondering if the issue could be related to having
directly an int* MEM_REF (it appears during early inline) instead of several
COMPONENT_REF (which would show as ._M_impl._M_start in the dump).

(alternatively, gcc could notice that the potential clobbering value is the
same as the old value, but that's a separate, known issue)

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's indeed that GCC only sees int accesses based on w and v and thus has to
consider they might alias.

Maybe it's time to try that "trick" with the same clobbering value...

TBAA cannot be strengthened easily here because the stores change the
dynamic type of the memory.

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> It's indeed that GCC only sees int accesses based on w and v and thus has to
> consider they might alias.
> 
> TBAA cannot be strengthened easily here because the stores change the
> dynamic type of the memory.

struct A { int i; };
inline void z(int*i){*i=0;}
void f(struct A *a){ a->i=0; }
void g(struct A *a){ z(&a->i); }

f uses a_2(D)->i
g uses MEM[(int *)a_1(D)] (folded from *_2 where _2 = &a_1(D)->i)

Is it really true that we can't treat g the same as f? That sounds quite bad to
me. Or a version without stores:

struct A { int i; };
inline int z(int*i){return*i;}
int f(struct A *a){ return a->i; }
int g(struct A *a){ return z(&a->i); }

still has a_2(D)->i in f and MEM[(int *)a_1(D)] in g.

I don't think Jonathan and Paolo will be happy if I send a patch hand-inlining
std::swap in various places in libstdc++ :-(

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
Actually there is no need for inlining.

struct A { int i; };
void f(struct A *a){ *&a->i=0; }
void g(struct A *a){ int*p=&a->i;*p=0; }

The main difference seems to be that the first one gets through fold-const.c
while the second is handled by tree-ssa-forwprop.c.

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #3)
> Actually there is no need for inlining.
> 
> struct A { int i; };
> void f(struct A *a){ *&a->i=0; }
> void g(struct A *a){ int*p=&a->i;*p=0; }
> 
> The main difference seems to be that the first one gets through fold-const.c
> while the second is handled by tree-ssa-forwprop.c.

&a->i is merely an address calculation, not an access to type A at a.  Thus
it's valid to write

 struct B { int i; int j; };
 struct B b;
 int *p = &((struct A *)&b)->i;
 *p = 0;

and it's only required that the actual access (here a int * dereference)
honors TBAA rules.

So generally you can't "reconstruct" access paths when forwarding address
calculations into dereferences.  We've had very elaborate code "guessing"
access paths in oder releases which broke down very easily for moderately
complex testcases.

We still have some of that code in forwprop (I still believe it's not
100% correct...) which handles

struct A { int i[4]; };
void g(struct A *a, int j) { int *p = &a->i[j]; *p = 0;}

generating

  MEM[(int *)a_1(D)].i[j_2(D)] = 0;
  return;

but the case comes after forwarding invariant addresses.  If we'd swap them
(really believing in its correctness) then we also handle your case.
But as I said - that "If ... and the value type is the same as that of the
pointed-to type of the address" is really bogus - the type of the address
doesn't have any meaning in GIMPLE (all pointer type conversions are
useless).

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[rguenth at gcc dot gnu.org]

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

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

This is what I am talking about (I think it's wrong and instead we have
to remove the case completely)

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Note that we do it correctly even - forcing a TBAA type of just 'int' and thus
disabling path-based disambiguation.

So doing this won't help you, it just will generate larger trees:

void f(V&, V&) (struct V & v, struct V & w)
{
  int * _3;
  int * _6;
  int * _7;
  int * _8;

  <bb 2>:
  _3 = MEM[(int * &)w_2(D)].D.14881._M_impl._M_start;
  MEM[(int * &)w_2(D)].D.14881._M_impl._M_start = 0B;
  _6 = MEM[(int * &)w_2(D)].D.14881._M_impl._M_finish;
  MEM[(int * &)w_2(D)].D.14881._M_impl._M_finish = 0B;
  _7 = MEM[(int * &)w_2(D)].D.14881._M_impl._M_end_of_storage;
  MEM[(int * &)w_2(D)].D.14881._M_impl._M_end_of_storage = 0B;
  _8 = MEM[(int * &)v_4(D)].D.14881._M_impl._M_start;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_start = _3;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_finish = _6;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_end_of_storage = _7;
...

void g(V&, V&) (struct V & v, struct V & w)
{
  int * __tmp.0_5;
  int * _6;
  int * __tmp.0_7;
  int * _8;
  int * __tmp.0_9;
  int * _10;

  <bb 2>:
  __tmp.0_5 = MEM[(int * &)v_4(D)].D.14881._M_impl._M_start;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_start = 0B;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_finish = 0B;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_end_of_storage = 0B;
  _6 = MEM[(int * &)w_2(D)].D.14881._M_impl._M_start;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_start = _6;
  MEM[(int * &)w_2(D)].D.14881._M_impl._M_start = 0B;
  __tmp.0_7 = MEM[(int * &)v_4(D)].D.14881._M_impl._M_finish;
  _8 = MEM[(int * &)w_2(D)].D.14881._M_impl._M_finish;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_finish = _8;
  MEM[(int * &)w_2(D)].D.14881._M_impl._M_finish = __tmp.0_7;
  __tmp.0_9 = MEM[(int * &)v_4(D)].D.14881._M_impl._M_end_of_storage;
  _10 = MEM[(int * &)w_2(D)].D.14881._M_impl._M_end_of_storage;
  MEM[(int * &)v_4(D)].D.14881._M_impl._M_end_of_storage = _10;
  MEM[(int * &)w_2(D)].D.14881._M_impl._M_end_of_storage = __tmp.0_9;

they are still all plain int * accesses.

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[glisse at gcc dot gnu.org]

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

--- Comment #7 from Marc Glisse <glisse at gcc dot gnu.org> ---
I am testing the following hack, I hope there will be at least 1 failure in the
testsuite that will help me understand why it is wrong. It bootstraps and gives
accesses like MEM[(struct _Vector_impl *)v_4(D)]._M_start.

> struct B { int i; int j; };
> struct B b;
> int *p = &((struct A *)&b)->i;
> *p = 0;

Hmmm, yeah, that's ugly... I wish it weren't legal... I'll have to play with it
to see exactly how bad it is... Thanks for the example.

--- tree-ssa-forwprop.c    (revision 219694)
+++ tree-ssa-forwprop.c    (working copy)
@@ -777,20 +777,41 @@ forward_propagate_addr_expr_1 (tree name
                     new_def_rhs);
       else if (is_gimple_min_invariant (new_def_rhs))
     gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR, new_def_rhs);
       else
     return false;
       gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
       update_stmt (use_stmt);
       return true;
     }

+  /* *&X -> X.  */
+  if (TREE_CODE (lhs) == MEM_REF
+      && TREE_OPERAND (lhs, 0) == name
+      && integer_zerop (TREE_OPERAND (lhs, 1))
+      && useless_type_conversion_p (TREE_TYPE (lhs),
+                    TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
+    {
+      gimple_assign_set_lhs (use_stmt, unshare_expr (TREE_OPERAND (def_rhs,
0)));
+      tidy_after_forward_propagate_addr (use_stmt);
+      return true;
+    }
+  else if (TREE_CODE (rhs) == MEM_REF
+      && TREE_OPERAND (rhs, 0) == name
+      && integer_zerop (TREE_OPERAND (rhs, 1))
+      && useless_type_conversion_p (TREE_TYPE (rhs),
+                    TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
+    {
+      gimple_assign_set_rhs1 (use_stmt, unshare_expr (TREE_OPERAND (def_rhs,
0)));
+      tidy_after_forward_propagate_addr (use_stmt);
+      return true;
+    }
   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
      ADDR_EXPR will not appear on the LHS.  */
   tree *lhsp = gimple_assign_lhs_ptr (use_stmt);
   while (handled_component_p (*lhsp))
     lhsp = &TREE_OPERAND (*lhsp, 0);
   lhs = *lhsp;

   /* Now see if the LHS node is a MEM_REF using NAME.  If so,
      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
   if (TREE_CODE (lhs) == MEM_REF

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[glisse at gcc dot gnu.org]

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

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> ---
With the modified hack below, the testsuite passes, except:

gcc.dg/tree-ssa/scev-[34].c those go from xfail to pass, that sounds good
g++.dg/tree-ssa/pr31146.C seems that the scan-tree-dump is too strict
c-c++-common/ubsan/object-size-9.c for some reason it prints <memory cannot be
printed> instead of a bunch of 0s but I can't reproduce outside the dg
framework, doesn't seem very important.

I had to add a couple checks compared to the first version. Giving up on
volatile operands, sure, there is probably a better way but whatever. Forwprop
tends to feed artificial &MEM_REF[(void*)...] to this function in many cases
(POINTER_PLUS_EXPR in particular), which causes a number of issues (including,
surprisingly, assuming too strong alignment). Testing for ptr_type_node is a
hack, but the necessity for it is just an artifact of placing the
transformation there, it shouldn't be necessary if I put it elsewhere.

The transformation is triggered by dereferences, and compares the types of
objects, not pointers, so it isn't obvious that the issues you were describing
apply to it.

--- tree-ssa-forwprop.c    (revision 219694)
+++ tree-ssa-forwprop.c    (working copy)
@@ -777,20 +777,49 @@ forward_propagate_addr_expr_1 (tree name
                     new_def_rhs);
       else if (is_gimple_min_invariant (new_def_rhs))
     gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR, new_def_rhs);
       else
     return false;
       gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
       update_stmt (use_stmt);
       return true;
     }

+  /* *&X -> X.  */
+  if (TREE_CODE (lhs) == MEM_REF
+      && !gimple_has_volatile_ops (use_stmt)
+      && TREE_OPERAND (lhs, 0) == name
+      && integer_zerop (TREE_OPERAND (lhs, 1))
+      && (TREE_CODE (TREE_OPERAND (def_rhs, 0)) != MEM_REF
+      || TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_rhs, 0), 1))
+         != ptr_type_node)
+      && useless_type_conversion_p (TREE_TYPE (lhs),
+                    TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
+    {
+      gimple_assign_set_lhs (use_stmt, unshare_expr (TREE_OPERAND (def_rhs,
0)));
+      tidy_after_forward_propagate_addr (use_stmt);
+      return true;
+    }
+  else if (TREE_CODE (rhs) == MEM_REF
+      && !gimple_has_volatile_ops (use_stmt)
+      && TREE_OPERAND (rhs, 0) == name
+      && integer_zerop (TREE_OPERAND (rhs, 1))
+      && (TREE_CODE (TREE_OPERAND (def_rhs, 0)) != MEM_REF
+      || TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_rhs, 0), 1))
+         != ptr_type_node)
+      && useless_type_conversion_p (TREE_TYPE (rhs),
+                    TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
+    {
+      gimple_assign_set_rhs1 (use_stmt, unshare_expr (TREE_OPERAND (def_rhs,
0)));
+      tidy_after_forward_propagate_addr (use_stmt);
+      return true;
+    }
   /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
      ADDR_EXPR will not appear on the LHS.  */
   tree *lhsp = gimple_assign_lhs_ptr (use_stmt);
   while (handled_component_p (*lhsp))
     lhsp = &TREE_OPERAND (*lhsp, 0);
   lhs = *lhsp;

   /* Now see if the LHS node is a MEM_REF using NAME.  If so,
      propagate the ADDR_EXPR into the use of NAME and fold the result.  */
   if (TREE_CODE (lhs) == MEM_REF

[Bug tree-optimization/64601] Missed PRE on std::vector move assignment

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #9 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #8)
> The transformation is triggered by dereferences, and compares the types of
> objects, not pointers, so it isn't obvious that the issues you were
> describing apply to it.

It looks like they still do apply. I was just lucky that the folding was done
in an order where nothing bad happened in the tests. Your example

 int *p = &((struct A *)&b)->i;
 *p = 0;

becomes *(int*)&b=0, which is fine. But in a different order, what I wanted
could give: (*(struct A *)&b).i=0 (access b as an A) which would be wrong for
TBAA. Although I don't see the point of writing that kind of code instead of:

 int *p = (int*)((char*)&b + offsetof(A, i));

So basically, a struct A * as an argument of a function doesn't carry any more
information than a void* :-( It is only if we can see an actual VAR_DECL or
similar that we may be able to reconstruct the access, but then we don't often
need to...

It is strange that [basic.lval] (or 6.5 Expressions in C99) is so lenient.
[class.mem] is a little bit more restrictive but still not much.

There is a little bit of divergence on function f below:

void f(struct A *a){ *&a->i=0; }
void g(struct A *a){ int*p=&a->i;*p=0; }
void h(struct A *a){ a->i=0; }

gcc, intel and oracle handle f like h, while clang is more conservative and
handles it like g (I actually tested on a function taking 2 std::pair<int,int>
by reference if a.first and b.second could alias).

Ok, I am starting to understand vaguely what C/C++ are saying about type
aliasing. I am horrified (this is a huge abstraction penalty), but at least I
am less confused. I'll close this PR as INVALID (the trick about the same
clobbering value is already in several other PRs, no need to keep this one as
well) (if you want to remove some current unsafe transformations, it would
probably be less confusing to open a different PR).

I wonder how feasible it would be to define a dialect where any non-zero struct
A* really points to a struct A... (we already have void* and char* for
"untyped" pointers)