[Bug tree-optimization/62156] New: memcmp doesn't see through memcpy at compile-time

[Bug tree-optimization/62156] New: memcmp doesn't see through memcpy at compile-time

[glisse at gcc dot gnu.org]

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

            Bug ID: 62156
           Summary: memcmp doesn't see through memcpy at compile-time
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org

int f(){
  const char*a="abcdefghijkl";
  const char*b="acbdefghijkl";
  char*c=(char*)__builtin_malloc(42);
  __builtin_memcpy(c,b,13);
  return __builtin_memcmp(a,c,5);
}

We have no problem computing strlen(c) or memcmp(a,b,5) at compile-time, but we
don't manage to fold this. This type of code is what we get with std::string
when we inline everything.

[Bug tree-optimization/62156] memcmp doesn't see through memcpy at compile-time

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-08-18
                 CC|                            |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hm, yeah.  Well, not sure if this is worth having a special case for in
tree-ssa-sccvn.c or in gimple_fold_stmt_to_constant_1.  I'd probably
try a simple pattern matching in gimple_fold_stmt_to_constant_1.

What kind of std::string code is this?  That is, can we expect
memcmp and memcpy to be adjacent (without intermediate memory operations?)

[Bug tree-optimization/62156] memcmp doesn't see through memcpy at compile-time

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> What kind of std::string code is this?  That is, can we expect
> memcmp and memcpy to be adjacent (without intermediate memory operations?)

I don't remember the exact code, but it was similar to:
std::string("foo")=="bar"
which, with _GLIBCXX_EXTERN_TEMPLATE=0 (or LTO) gives:

  _29 = _50 + 24;
  __builtin_memcpy (_29, "foo", 3);
  if (_50 != &_S_empty_rep_storage)
    goto <bb 3>;

  <bb 3>:
  MEM[(struct _Rep *)_50].D.20711._M_length = 3;
  MEM[(char_type &)_50 + 27] = 0;
  __r_86 = __builtin_memcmp (_29, "bar", 3);

So it is setting the null character right after the string (could have used
memcpy of size 4?) and the length right before, which requires tight alias
checking to be sure that memcmp is not affected :-(

Probably a bit too specific to be worth it.

[Bug tree-optimization/62156] memcmp doesn't see through memcpy at compile-time

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
Not much difference using __gnu_cxx::__vstring (no reference counting, small
string optimization):

__builtin_memcpy (&MEM[(struct __sso_string_base
*)&D.28720].D.23707._M_local_data, "foo", 3);
MEM[(size_type *)&D.28720 + 8B] = 3;
MEM[(char_type &)&D.28720 + 19] = 0;
__r_46 = __builtin_memcmp (&MEM[(struct __sso_string_base
*)&D.28720].D.23707._M_local_data, "bar", 3);

[Bug tree-optimization/62156] memcmp doesn't see through memcpy at compile-time

[rguenther at suse dot de]

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

--- Comment #4 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 18 Aug 2014, glisse at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62156
> 
> --- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #1)
> > What kind of std::string code is this?  That is, can we expect
> > memcmp and memcpy to be adjacent (without intermediate memory operations?)
> 
> I don't remember the exact code, but it was similar to:
> std::string("foo")=="bar"
> which, with _GLIBCXX_EXTERN_TEMPLATE=0 (or LTO) gives:
> 
>   _29 = _50 + 24;
>   __builtin_memcpy (_29, "foo", 3);
>   if (_50 != &_S_empty_rep_storage)
>     goto <bb 3>;
> 
>   <bb 3>:
>   MEM[(struct _Rep *)_50].D.20711._M_length = 3;
>   MEM[(char_type &)_50 + 27] = 0;
>   __r_86 = __builtin_memcmp (_29, "bar", 3);
> 
> So it is setting the null character right after the string (could have used
> memcpy of size 4?) and the length right before, which requires tight alias
> checking to be sure that memcmp is not affected :-(
> 
> Probably a bit too specific to be worth it.

Eventually worth "fixing" the libstdc++ side to generate better
initial code?

Other than that it seems this would need careful special-handling
in value-numbering ... not sure if optimizing std::string("foo") == "bar"
is important.

[Bug tree-optimization/62156] memcmp doesn't see through memcpy at compile-time

[glisse at gcc dot gnu.org]

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

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #4)
> Eventually worth "fixing" the libstdc++ side to generate better
> initial code?

Replacing memcpy(,,3)+assign(,'\0') with memcpy(,,4) can indeed be done at the
libstdc++ level (although simplify_builtin_call in tree-ssa-forwprop.c already
does a transformation extremely similar and could be extended). As shown in
comment #3, the test/jump will disappear when we move to C++11.

But essentially, it can't avoid doing memcpy, setting the length of the string,
and calling memcmp.

One surprising thing it does not is, at the beginning of operator==, check if
the sizes are the same before calling memcmp...

> Other than that it seems this would need careful special-handling
> in value-numbering ...

That seems like the best place indeed.

> not sure if optimizing std::string("foo") == "bar" is important.

The question is how many other optimizations this would enable. I remember
other cases where we couldn't see through memcpy well enough (PR 58483 for
instance, there were others probably more relevant), but I don't know if this
would help them.

In any case, I agree this isn't a priority.

[Bug tree-optimization/62156] memcmp doesn't see through memcpy at compile-time

[rguenther at suse dot de]

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

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 19 Aug 2014, glisse at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62156
> 
> --- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
> (In reply to rguenther@suse.de from comment #4)
> > Eventually worth "fixing" the libstdc++ side to generate better
> > initial code?
> 
> Replacing memcpy(,,3)+assign(,'\0') with memcpy(,,4) can indeed be done at the
> libstdc++ level (although simplify_builtin_call in tree-ssa-forwprop.c already
> does a transformation extremely similar and could be extended). As shown in
> comment #3, the test/jump will disappear when we move to C++11.
> 
> But essentially, it can't avoid doing memcpy, setting the length of the string,
> and calling memcmp.
> 
> One surprising thing it does not is, at the beginning of operator==, check if
> the sizes are the same before calling memcmp...
> 
> > Other than that it seems this would need careful special-handling
> > in value-numbering ...
> 
> That seems like the best place indeed.
> 
> > not sure if optimizing std::string("foo") == "bar" is important.
> 
> The question is how many other optimizations this would enable. I remember
> other cases where we couldn't see through memcpy well enough (PR 58483 for
> instance, there were others probably more relevant), but I don't know if this
> would help them.
> 
> In any case, I agree this isn't a priority.

The special thing with memcmp is that it evaluates to a value
we'd like to compute while the usual look-through-memcpy is
for value-numbering loads.

So it won't be that easy...

IMHO it would be nicer if we'd fix PR52171 which should be able
to catch your simple case then via existing value-numbering code
at least if the compare includes the trailing zero.