[PATCH] Fix PR56888

[PATCH] Fix PR56888

[Richard Biener]

The following fixes us to not transform loops into memcpy or memset
or not transform malloc + memset into calloc if we implement that
functionality itself (and thus we "alias" the symbol we'd call when
emitting a call to the builtin).

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

The code is pretty awkward as builtins have no cgraph node and their
assembler name is still the "wrong" one appearantly.

Ok?  Any better way to implement this?

Thanks,
Richard.

2016-02-22  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/56888
	* cgraph.c (cgraph_node::aliases): New function.
	* cgraph.h (cgraph_node::aliases): Declare.
	* tree-loop-distribution.c: Include cgraph.h.
	(classify_partition): Check whether the current function aliases
	memset, memcpy or memmove.
	* tree-ssa-strlen.c (handle_builtin_memset): Check whether the
	current function aliases calloc.

Index: gcc/cgraph.c
===================================================================
*** gcc/cgraph.c	(revision 233598)
--- gcc/cgraph.c	(working copy)
*************** cgraph_node::has_thunk_p (cgraph_node *n
*** 3541,3544 ****
--- 3541,3564 ----
    return false;
  }
  
+ /* Return true if NODE aliases FN.  */
+ 
+ bool
+ cgraph_node::aliases (enum built_in_function fn)
+ {
+   tree fndecl = builtin_decl_implicit (fn);
+   if (! fndecl || ! DECL_ASSEMBLER_NAME_SET_P (fndecl))
+     return false;
+ 
+   /* ???  Builtins with aliases are weird.  */
+   cgraph_node *fnnode
+     = cgraph_node::get_for_asmname (DECL_ASSEMBLER_NAME (fndecl));
+   if (! fnnode)
+     return false;
+ 
+   fndecl = fnnode->ultimate_alias_target ()->decl;
+   return symbol_table::decl_assembler_name_equal (decl,
+ 						  DECL_ASSEMBLER_NAME (fndecl));
+ }
+ 
  #include "gt-cgraph.h"
Index: gcc/cgraph.h
===================================================================
*** gcc/cgraph.h	(revision 233598)
--- gcc/cgraph.h	(working copy)
*************** public:
*** 1181,1186 ****
--- 1181,1189 ----
    /* Return true if function should be optimized for size.  */
    bool optimize_for_size_p (void);
  
+   /* Return true if NODE aliases the specified builtin.  */
+   bool aliases (enum built_in_function);
+ 
    /* Dump the callgraph to file F.  */
    static void dump_cgraph (FILE *f);
  
Index: gcc/tree-loop-distribution.c
===================================================================
*** gcc/tree-loop-distribution.c	(revision 233598)
--- gcc/tree-loop-distribution.c	(working copy)
*************** along with GCC; see the file COPYING3.
*** 64,69 ****
--- 64,70 ----
  #include "cfgloop.h"
  #include "tree-scalar-evolution.h"
  #include "tree-vectorizer.h"
+ #include "cgraph.h"
  
  
  /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
*************** classify_partition (loop_p loop, struct
*** 1078,1083 ****
--- 1079,1086 ----
  	  || !dominated_by_p (CDI_DOMINATORS,
  			      loop->latch, gimple_bb (stmt)))
  	return;
+       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMSET))
+ 	return;
        partition->kind = PKIND_MEMSET;
        partition->main_dr = single_store;
        partition->niter = nb_iter;
*************** classify_partition (loop_p loop, struct
*** 1135,1140 ****
--- 1138,1146 ----
  	}
        free_dependence_relation (ddr);
        loops.release ();
+       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMCPY)
+ 	  || cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMMOVE))
+ 	return;
        partition->kind = PKIND_MEMCPY;
        partition->main_dr = single_store;
        partition->secondary_dr = single_load;
Index: gcc/tree-ssa-strlen.c
===================================================================
*** gcc/tree-ssa-strlen.c	(revision 233598)
--- gcc/tree-ssa-strlen.c	(working copy)
*************** handle_builtin_memset (gimple_stmt_itera
*** 1817,1823 ****
    if (code1 == BUILT_IN_CALLOC)
      /* Not touching stmt1 */ ;
    else if (code1 == BUILT_IN_MALLOC
! 	   && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
      {
        gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
        update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
--- 1817,1824 ----
    if (code1 == BUILT_IN_CALLOC)
      /* Not touching stmt1 */ ;
    else if (code1 == BUILT_IN_MALLOC
! 	   && operand_equal_p (gimple_call_arg (stmt1, 0), size, 0)
! 	   && ! cgraph_node::get (cfun->decl)->aliases (BUILT_IN_CALLOC))
      {
        gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
        update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
Index: gcc/testsuite/gcc.dg/pr56888.c
===================================================================
*** gcc/testsuite/gcc.dg/pr56888.c	(revision 0)
--- gcc/testsuite/gcc.dg/pr56888.c	(working copy)
***************
*** 0 ****
--- 1,21 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -ftree-loop-distribute-patterns -fdump-tree-optimized" } */
+ /* { dg-require-alias "" } */
+ /* { dg-require-weak "" } */
+ 
+ typedef __SIZE_TYPE__ size_t;
+ extern void *
+ memset (void *s, int c, size_t n) __attribute__ ((weak, alias("_memset")));
+ 
+ void *
+ _memset(void *s, int c, size_t n)
+ {
+   char *q = (char *)s;
+   while (n != 0)
+     {
+       *(q++) = c;
+       n--;
+     }
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "__builtin_memset" "optimized" } } */

Re: [PATCH] Fix PR56888

[Jakub Jelinek]

On Mon, Feb 22, 2016 at 01:44:09PM +0100, Richard Biener wrote:
> --- 1079,1086 ----
>   	  || !dominated_by_p (CDI_DOMINATORS,
>   			      loop->latch, gimple_bb (stmt)))
>   	return;
> +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMSET))
> + 	return;

Perhaps also punt here for:
BUILT_IN_MEMSET_CHK
BUILT_IN_TM_MEMSET
BUILT_IN_BZERO
?

>         partition->kind = PKIND_MEMSET;
>         partition->main_dr = single_store;
>         partition->niter = nb_iter;
> *************** classify_partition (loop_p loop, struct
> *** 1135,1140 ****
> --- 1138,1146 ----
>   	}
>         free_dependence_relation (ddr);
>         loops.release ();
> +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMCPY)
> + 	  || cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMMOVE))
> + 	return;

And here for
BUILT_IN_MEMCPY_CHK
BUILT_IN_TM_MEMCPY
BUILT_IN_TM_MEMCPY_RNWT
BUILT_IN_TM_MEMCPY_RTWN
BUILT_IN_MEMPCPY
BUILT_IN_MEMPCPY_CHK
BUILT_IN_MEMMOVE_CHK
BUILT_IN_TM_MEMMOVE
BUILT_IN_BCOPY
?

	Jakub

Re: [PATCH] Fix PR56888

[Richard Biener]

On Mon, 22 Feb 2016, Jakub Jelinek wrote:

> On Mon, Feb 22, 2016 at 01:44:09PM +0100, Richard Biener wrote:
> > --- 1079,1086 ----
> >   	  || !dominated_by_p (CDI_DOMINATORS,
> >   			      loop->latch, gimple_bb (stmt)))
> >   	return;
> > +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMSET))
> > + 	return;
> 
> Perhaps also punt here for:
> BUILT_IN_MEMSET_CHK
> BUILT_IN_TM_MEMSET
> BUILT_IN_BZERO
> ?
> 
> >         partition->kind = PKIND_MEMSET;
> >         partition->main_dr = single_store;
> >         partition->niter = nb_iter;
> > *************** classify_partition (loop_p loop, struct
> > *** 1135,1140 ****
> > --- 1138,1146 ----
> >   	}
> >         free_dependence_relation (ddr);
> >         loops.release ();
> > +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMCPY)
> > + 	  || cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMMOVE))
> > + 	return;
> 
> And here for
> BUILT_IN_MEMCPY_CHK
> BUILT_IN_TM_MEMCPY
> BUILT_IN_TM_MEMCPY_RNWT
> BUILT_IN_TM_MEMCPY_RTWN
> BUILT_IN_MEMPCPY
> BUILT_IN_MEMPCPY_CHK
> BUILT_IN_MEMMOVE_CHK
> BUILT_IN_TM_MEMMOVE
> BUILT_IN_BCOPY
> ?

I'm going to wait for Honzas feedback.  Testing all of the above
looks expensive - if those are implemented in terms of memcpy/memset
then hopefully in libc itself which hopefully always does local
calls.

It's not going to be an exhaustive check anyway, just a QOI one
covering those cases we've seen in the wild.  Esp. as indirection
will break the detection (so does using asm(".alias XXX") which glibc
does).

Richard.

Re: [PATCH] Fix PR56888

[Richard Biener]

On Mon, 22 Feb 2016, Richard Biener wrote:

> On Mon, 22 Feb 2016, Jakub Jelinek wrote:
> 
> > On Mon, Feb 22, 2016 at 01:44:09PM +0100, Richard Biener wrote:
> > > --- 1079,1086 ----
> > >   	  || !dominated_by_p (CDI_DOMINATORS,
> > >   			      loop->latch, gimple_bb (stmt)))
> > >   	return;
> > > +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMSET))
> > > + 	return;
> > 
> > Perhaps also punt here for:
> > BUILT_IN_MEMSET_CHK
> > BUILT_IN_TM_MEMSET
> > BUILT_IN_BZERO
> > ?
> > 
> > >         partition->kind = PKIND_MEMSET;
> > >         partition->main_dr = single_store;
> > >         partition->niter = nb_iter;
> > > *************** classify_partition (loop_p loop, struct
> > > *** 1135,1140 ****
> > > --- 1138,1146 ----
> > >   	}
> > >         free_dependence_relation (ddr);
> > >         loops.release ();
> > > +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMCPY)
> > > + 	  || cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMMOVE))
> > > + 	return;
> > 
> > And here for
> > BUILT_IN_MEMCPY_CHK
> > BUILT_IN_TM_MEMCPY
> > BUILT_IN_TM_MEMCPY_RNWT
> > BUILT_IN_TM_MEMCPY_RTWN
> > BUILT_IN_MEMPCPY
> > BUILT_IN_MEMPCPY_CHK
> > BUILT_IN_MEMMOVE_CHK
> > BUILT_IN_TM_MEMMOVE
> > BUILT_IN_BCOPY
> > ?
> 
> I'm going to wait for Honzas feedback.  Testing all of the above
> looks expensive - if those are implemented in terms of memcpy/memset
> then hopefully in libc itself which hopefully always does local
> calls.
> 
> It's not going to be an exhaustive check anyway, just a QOI one
> covering those cases we've seen in the wild.  Esp. as indirection
> will break the detection (so does using asm(".alias XXX") which glibc
> does).

Ok, so maybe a better question to symtab would be if there is an
actual definition for what __builtin_FOO will call.  Not really
whether that definition is cfun.  Of course all the fortify
always-inline wrappers should not count as such (just in case
the symtab code is confused about those).

So,

bool symbol_table::have_definition (enum built_in_fn);

?  Not sure how to best implement that either.  asmname lookups are
expensive ...

Richard.

Re: [PATCH] Fix PR56888

[Jan Hubicka]

> On Mon, 22 Feb 2016, Jakub Jelinek wrote:
> 
> > On Mon, Feb 22, 2016 at 01:44:09PM +0100, Richard Biener wrote:
> > > --- 1079,1086 ----
> > >   	  || !dominated_by_p (CDI_DOMINATORS,
> > >   			      loop->latch, gimple_bb (stmt)))
> > >   	return;
> > > +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMSET))
> > > + 	return;
> > 
> > Perhaps also punt here for:
> > BUILT_IN_MEMSET_CHK
> > BUILT_IN_TM_MEMSET
> > BUILT_IN_BZERO
> > ?
> > 
> > >         partition->kind = PKIND_MEMSET;
> > >         partition->main_dr = single_store;
> > >         partition->niter = nb_iter;
> > > *************** classify_partition (loop_p loop, struct
> > > *** 1135,1140 ****
> > > --- 1138,1146 ----
> > >   	}
> > >         free_dependence_relation (ddr);
> > >         loops.release ();
> > > +       if (cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMCPY)
> > > + 	  || cgraph_node::get (cfun->decl)->aliases (BUILT_IN_MEMMOVE))
> > > + 	return;
> > 
> > And here for
> > BUILT_IN_MEMCPY_CHK
> > BUILT_IN_TM_MEMCPY
> > BUILT_IN_TM_MEMCPY_RNWT
> > BUILT_IN_TM_MEMCPY_RTWN
> > BUILT_IN_MEMPCPY
> > BUILT_IN_MEMPCPY_CHK
> > BUILT_IN_MEMMOVE_CHK
> > BUILT_IN_TM_MEMMOVE
> > BUILT_IN_BCOPY
> > ?
> 
> I'm going to wait for Honzas feedback.  Testing all of the above
> looks expensive - if those are implemented in terms of memcpy/memset
> then hopefully in libc itself which hopefully always does local
> calls.

Well, other problem will be if memcpy itself is implemented by calling a
function that does the actual copying job (for example, for large block sizes
or so). So for ultimate QOI fix you really want to check if the function you
are optimizing is reachable from any of those bultins. This is of course
doable by means of simple propagation pass, but I am not sure if it makes
sense to get that far.

The checks however should not be that bad - they are done only when we
recognize the memcpy pattern and want to optimize it and that is not too common
case, right?
> 
> It's not going to be an exhaustive check anyway, just a QOI one
> covering those cases we've seen in the wild.  Esp. as indirection
> will break the detection (so does using asm(".alias XXX") which glibc
> does).

To lookup definition of the bulitin, you don't really need assembler name
lookup.  Just get cgraph node for the builtin decl and look
next_sharing_asm_name and prev_shaing_asm_name lists (this works only when asm
name hash is initialized, so to be sure just call
symtab->symtab_initialize_asm_name_hash ();

For next stage1 I have queued patch that makes duplicated decls to be
transparent alises, so you will need to only lookup the ultimate alias target.
I did not commited it to mainline becuase it requires lto-symtab like linking
to be done each time new duplciate is inserted into the symbol table and it
tends to find new user errors on misuse of asm("...") constructs.
Also one needs to fix the chkp issues....

Honza
> 
> Richard.

Re: [PATCH] Fix PR56888

[Jan Hubicka]

> 
> Ok, so maybe a better question to symtab would be if there is an
> actual definition for what __builtin_FOO will call.  Not really
> whether that definition is cfun.  Of course all the fortify
> always-inline wrappers should not count as such (just in case
> the symtab code is confused about those).

Also GNU extern inlines that are often used to deal special cases.
> 
> So,
> 
> bool symbol_table::have_definition (enum built_in_fn);
> 
> ?  Not sure how to best implement that either.  asmname lookups are
> expensive ...

I am back from China trip, so i can handle you patch if you want.

I see that by stopping the optimization on whole translation unit that
defines memcpy/memset will solve the reachability issue I mentioned
in previous mail, but also when LTOing stuff like Linux kernel, it will
prevent the optimization on the whole program.
I am not quite sure how to deal with the alwaysinline wrappers however,
because there theoretically may contain memcpy/memset loops themselves.

Honza
> 
> Richard.

Re: [PATCH] Fix PR56888

[Richard Biener]

On Tue, 23 Feb 2016, Jan Hubicka wrote:

> > 
> > Ok, so maybe a better question to symtab would be if there is an
> > actual definition for what __builtin_FOO will call.  Not really
> > whether that definition is cfun.  Of course all the fortify
> > always-inline wrappers should not count as such (just in case
> > the symtab code is confused about those).
> 
> Also GNU extern inlines that are often used to deal special cases.
> > 
> > So,
> > 
> > bool symbol_table::have_definition (enum built_in_fn);
> > 
> > ?  Not sure how to best implement that either.  asmname lookups are
> > expensive ...
> 
> I am back from China trip, so i can handle you patch if you want.
> 
> I see that by stopping the optimization on whole translation unit that
> defines memcpy/memset will solve the reachability issue I mentioned
> in previous mail, but also when LTOing stuff like Linux kernel, it will
> prevent the optimization on the whole program.

Yes, but I think it's reasonable to disable such transform if the
memcpy implementation is being optimized.

> I am not quite sure how to deal with the alwaysinline wrappers however,
> because there theoretically may contain memcpy/memset loops themselves.

It might be a non-issue as we are doing the transforms only after
inlining when those bodies should be gone and thus symtab shouldn't see
such implementation.

Better to double-check, of course.  We'd want

#include <string.h>

int main()
{
  int s[1204];
  for (int i = 0; i < 1204; ++i)
   s[i] = 0;
  memset (s, 0, sizeof (s));
}

still be optimized as memset.

Richard.

> Honza
> > 
> > Richard.
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH] Fix PR56888

[Richard Biener]

On Tue, Feb 23, 2016 at 12:32 PM, Richard Biener <rguenther@suse.de> wrote:
> On Tue, 23 Feb 2016, Jan Hubicka wrote:
>
>> >
>> > Ok, so maybe a better question to symtab would be if there is an
>> > actual definition for what __builtin_FOO will call.  Not really
>> > whether that definition is cfun.  Of course all the fortify
>> > always-inline wrappers should not count as such (just in case
>> > the symtab code is confused about those).
>>
>> Also GNU extern inlines that are often used to deal special cases.
>> >
>> > So,
>> >
>> > bool symbol_table::have_definition (enum built_in_fn);
>> >
>> > ?  Not sure how to best implement that either.  asmname lookups are
>> > expensive ...
>>
>> I am back from China trip, so i can handle you patch if you want.

Honza - ping.  Can you please think of a symtab predicate that tells me
whether a cgraph node is an implementation for BUILT_IN_X?  (see original
patch in this thread).

It's before another GCC release and we're trying to improve QOI wise for
almost 3 releases now...

Thanks a lot,
Richard.

>> I see that by stopping the optimization on whole translation unit that
>> defines memcpy/memset will solve the reachability issue I mentioned
>> in previous mail, but also when LTOing stuff like Linux kernel, it will
>> prevent the optimization on the whole program.
>
> Yes, but I think it's reasonable to disable such transform if the
> memcpy implementation is being optimized.
>
>> I am not quite sure how to deal with the alwaysinline wrappers however,
>> because there theoretically may contain memcpy/memset loops themselves.
>
> It might be a non-issue as we are doing the transforms only after
> inlining when those bodies should be gone and thus symtab shouldn't see
> such implementation.
>
> Better to double-check, of course.  We'd want
>
> #include <string.h>
>
> int main()
> {
>   int s[1204];
>   for (int i = 0; i < 1204; ++i)
>    s[i] = 0;
>   memset (s, 0, sizeof (s));
> }
>
> still be optimized as memset.
>
> Richard.
>
>> Honza
>> >
>> > Richard.
>>
>>
>
> --
> Richard Biener <rguenther@suse.de>
> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH] Fix PR56888

[Jan Hubicka]

> On Tue, Feb 23, 2016 at 12:32 PM, Richard Biener <rguenther@suse.de> wrote:
> > On Tue, 23 Feb 2016, Jan Hubicka wrote:
> >
> >> >
> >> > Ok, so maybe a better question to symtab would be if there is an
> >> > actual definition for what __builtin_FOO will call.  Not really
> >> > whether that definition is cfun.  Of course all the fortify
> >> > always-inline wrappers should not count as such (just in case
> >> > the symtab code is confused about those).
> >>
> >> Also GNU extern inlines that are often used to deal special cases.
> >> >
> >> > So,
> >> >
> >> > bool symbol_table::have_definition (enum built_in_fn);
> >> >
> >> > ?  Not sure how to best implement that either.  asmname lookups are
> >> > expensive ...
> >>
> >> I am back from China trip, so i can handle you patch if you want.
> 
> Honza - ping.  Can you please think of a symtab predicate that tells me
> whether a cgraph node is an implementation for BUILT_IN_X?  (see original
> patch in this thread).
> 
> It's before another GCC release and we're trying to improve QOI wise for
> almost 3 releases now...

Hi,
I hope the following should do the trick...

Honza

Index: cgraph.h
===================================================================
--- cgraph.h	(revision 245506)
+++ cgraph.h	(working copy)
@@ -1214,6 +1214,9 @@ public:
      direct calls.  */
   bool can_remove_if_no_direct_calls_p (bool will_inline = false);
 
+  /* Return true if symbol can possibly alias with implementation of FNCODE.  */
+  bool implements(enum built_in_function fncode);
+
   /* Return true when callgraph node is a function with Gimple body defined
      in current unit.  Functions can also be define externally or they
      can be thunks with no Gimple representation.
Index: cgraph.c
===================================================================
--- cgraph.c	(revision 245506)
+++ cgraph.c	(working copy)
@@ -3814,4 +3814,45 @@ cgraph_node::has_thunk_p (cgraph_node *n
   return false;
 }
 
+/* Return true if symbol can possibly alias with implementation of FNCODE.  */
+
+bool
+cgraph_node::implements (enum built_in_function fncode)
+{
+  struct cgraph_node *node = ultimate_alias_target ();
+  tree name = builtin_decl_explicit (fncode);
+
+  if (name)
+    name = DECL_ASSEMBLER_NAME (name);
+  else
+    name = NULL;
+
+  if ((DECL_BUILT_IN (node->decl)
+       && DECL_BUILT_IN_CLASS (node->decl) == BUILT_IN_NORMAL
+       && DECL_FUNCTION_CODE (node->decl) == fncode)
+      || (name && DECL_ASSEMBLER_NAME_SET_P (node->decl)
+	  && symbol_table::assembler_names_equal_p
+			  (IDENTIFIER_POINTER (name),
+			   IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME
+			     (node->decl)))))
+    return true;
+
+  ipa_ref *ref;
+  FOR_EACH_ALIAS (node, ref)
+    {
+      cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring);
+      if ((DECL_BUILT_IN (alias->decl)
+	   && DECL_BUILT_IN_CLASS (alias->decl) == BUILT_IN_NORMAL
+	   && DECL_FUNCTION_CODE (alias->decl) == fncode)
+	  || (name && DECL_ASSEMBLER_NAME_SET_P (alias->decl)
+	      && symbol_table::assembler_names_equal_p
+			      (IDENTIFIER_POINTER (name),
+			       IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME
+				 (alias->decl)))))
+	return true;
+    }
+
+  return false;
+}
+
 #include "gt-cgraph.h"