* calloc = malloc + memset
@ 2014-02-28 22:48 Marc Glisse
2014-03-01 12:26 ` Paolo Carlini
` (3 more replies)
0 siblings, 4 replies; 26+ messages in thread
From: Marc Glisse @ 2014-02-28 22:48 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: TEXT/PLAIN, Size: 437 bytes --]
Hello,
this is a stage 1 patch, and I'll ping it then, but if you have comments
now...
Passes bootstrap+testsuite on x86_64-linux-gnu.
2014-02-28 Marc Glisse <marc.glisse@inria.fr>
PR tree-optimization/57742
gcc/
* tree-ssa-forwprop.c (simplify_malloc_memset): New function.
(simplify_builtin_call): Call it.
gcc/testsuite/
* g++.dg/tree-ssa/calloc.C: New testcase.
* gcc.dg/tree-ssa/calloc.c: Likewise.
--
Marc Glisse
[-- Attachment #2: Type: TEXT/PLAIN, Size: 8810 bytes --]
Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
===================================================================
--- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
+++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-std=gnu++11 -O3 -fdump-tree-optimized" } */
+
+#include <new>
+#include <vector>
+#include <cstdlib>
+
+void g(void*);
+inline void* operator new(std::size_t sz) _GLIBCXX_THROW (std::bad_alloc)
+{
+ void *p;
+
+ if (sz == 0)
+ sz = 1;
+
+ // Slightly modified from the libsupc++ version, that one has 2 calls
+ // to malloc which makes it too hard to optimize.
+ while ((p = std::malloc (sz)) == 0)
+ {
+ std::new_handler handler = std::get_new_handler ();
+ if (! handler)
+ _GLIBCXX_THROW_OR_ABORT(std::bad_alloc());
+ handler ();
+ }
+ return p;
+}
+
+void f(void*p,int n){
+ new(p)std::vector<int>(n);
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Property changes on: gcc/testsuite/g++.dg/tree-ssa/calloc.C
___________________________________________________________________
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Index: gcc/testsuite/gcc.dg/tree-ssa/calloc.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/calloc.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/calloc.c (working copy)
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#include <stdlib.h>
+#include <string.h>
+
+extern int a;
+extern int* b;
+int n;
+void* f(long*q){
+ int*p=malloc(n);
+ ++*q;
+ if(p){
+ ++*q;
+ a=2;
+ memset(p,0,n);
+ *b=3;
+ }
+ return p;
+}
+void* g(void){
+ float*p=calloc(8,4);
+ return memset(p,0,32);
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Property changes on: gcc/testsuite/gcc.dg/tree-ssa/calloc.c
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: gcc/tree-ssa-forwprop.c
===================================================================
--- gcc/tree-ssa-forwprop.c (revision 208224)
+++ gcc/tree-ssa-forwprop.c (working copy)
@@ -1487,20 +1487,149 @@ constant_pointer_difference (tree p1, tr
}
for (i = 0; i < cnt[0]; i++)
for (j = 0; j < cnt[1]; j++)
if (exps[0][i] == exps[1][j])
return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
return NULL_TREE;
}
+/* Optimize
+ ptr = malloc (n);
+ memset (ptr, 0, n);
+ into
+ ptr = calloc (n);
+ gsi_p is known to point to a call to __builtin_memset. */
+static bool
+simplify_malloc_memset (gimple_stmt_iterator *gsi_p)
+{
+ /* First make sure we have:
+ ptr = malloc (n);
+ memset (ptr, 0, n); */
+ gimple stmt2 = gsi_stmt (*gsi_p);
+ if (!integer_zerop (gimple_call_arg (stmt2, 1)))
+ return false;
+ tree ptr1, ptr2 = gimple_call_arg (stmt2, 0);
+ tree size = gimple_call_arg (stmt2, 2);
+ if (TREE_CODE (ptr2) != SSA_NAME)
+ return false;
+ gimple stmt1 = SSA_NAME_DEF_STMT (ptr2);
+ tree callee1;
+ /* Handle the case where STMT1 is a unary PHI, which happends
+ for instance with:
+ while (!(p = malloc (n))) { ... }
+ memset (p, 0, n); */
+ if (!stmt1)
+ return false;
+ if (gimple_code (stmt1) == GIMPLE_PHI
+ && gimple_phi_num_args (stmt1) == 1)
+ {
+ ptr1 = gimple_phi_arg_def (stmt1, 0);
+ if (TREE_CODE (ptr1) != SSA_NAME)
+ return false;
+ stmt1 = SSA_NAME_DEF_STMT (ptr1);
+ }
+ else
+ ptr1 = ptr2;
+ if (!stmt1
+ || !is_gimple_call (stmt1)
+ || !(callee1 = gimple_call_fndecl (stmt1)))
+ return false;
+
+ bool is_calloc;
+ if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MALLOC)
+ {
+ is_calloc = false;
+ if (!operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
+ return false;
+ }
+ else if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_CALLOC)
+ {
+ is_calloc = true;
+ tree arg1 = gimple_call_arg (stmt1, 0);
+ tree arg2 = gimple_call_arg (stmt1, 1);
+ tree size1 = fold_build2 (MULT_EXPR, TREE_TYPE (size), arg1, arg2);
+ if (!operand_equal_p (size1, size, 0))
+ return false;
+ /* We could look at SSA_NAME_DEF_STMT (size), but there can be many casts
+ mixed with the MULT_EXPR which makes it hard to match with size1. */
+ }
+ else
+ return false;
+
+ /* We only allow two simple CFG forms for now. Either stmt1 and stmt2 are
+ in the same BB (in this order), or BB1 (malloc) ends with:
+ if (ptr) goto BB2 (memset) */
+ basic_block bb1 = gimple_bb (stmt1);
+ basic_block bb2 = gimple_bb (stmt2);
+ if (bb1 != bb2)
+ {
+ if (!single_pred_p (bb2) || single_pred (bb2) != bb1)
+ return false;
+ gimple cond = last_stmt (bb1);
+ if (gimple_code (cond) != GIMPLE_COND
+ || !integer_zerop (gimple_cond_rhs (cond))
+ || gimple_cond_lhs (cond) != ptr1)
+ return false;
+ int branch;
+ tree_code comp = gimple_cond_code (cond);
+ if (comp == NE_EXPR)
+ branch = EDGE_TRUE_VALUE;
+ else if (comp == EQ_EXPR)
+ branch = EDGE_FALSE_VALUE;
+ else
+ return false;
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb1->succs)
+ if ((e->flags & branch) && e->dest != bb2)
+ return false;
+ }
+
+ /* Finally, make sure the memory is not used before stmt2. */
+ ao_ref ref;
+ ao_ref_init_from_ptr_and_size (&ref, ptr1, size);
+ tree vdef = gimple_vuse (stmt2);
+ if (vdef == NULL)
+ return false;
+ while (true)
+ {
+ gimple cur = SSA_NAME_DEF_STMT (vdef);
+ if (cur == stmt1) break;
+ if (stmt_may_clobber_ref_p_1 (cur, &ref))
+ return false;
+ vdef = gimple_vuse (cur);
+ }
+
+ /* Replace malloc with calloc and remove memset. */
+ if (!is_calloc)
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
+ update_gimple_call (&gsi, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
+ size, build_one_cst (size_type_node));
+ }
+ tree lhs = gimple_call_lhs (stmt2);
+ unlink_stmt_vdef (stmt2);
+ if (lhs)
+ {
+ gimple assign = gimple_build_assign (lhs, ptr2);
+ gsi_replace (gsi_p, assign, false);
+ }
+ else
+ {
+ gsi_remove (gsi_p, true);
+ release_defs (stmt2);
+ }
+ return true;
+}
+
/* *GSI_P is a GIMPLE_CALL to a builtin function.
Optimize
memcpy (p, "abcd", 4);
memset (p + 4, ' ', 3);
into
memcpy (p, "abcd ", 7);
call if the latter can be stored by pieces during expansion. */
static bool
simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
@@ -1508,38 +1637,44 @@ simplify_builtin_call (gimple_stmt_itera
gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
tree vuse = gimple_vuse (stmt2);
if (vuse == NULL)
return false;
stmt1 = SSA_NAME_DEF_STMT (vuse);
switch (DECL_FUNCTION_CODE (callee2))
{
case BUILT_IN_MEMSET:
if (gimple_call_num_args (stmt2) != 3
- || gimple_call_lhs (stmt2)
|| CHAR_BIT != 8
|| BITS_PER_UNIT != 8)
break;
else
{
+ if (simplify_malloc_memset (gsi_p))
+ return true;
+
tree callee1;
tree ptr1, src1, str1, off1, len1, lhs1;
tree ptr2 = gimple_call_arg (stmt2, 0);
tree val2 = gimple_call_arg (stmt2, 1);
tree len2 = gimple_call_arg (stmt2, 2);
tree diff, vdef, new_str_cst;
gimple use_stmt;
unsigned int ptr1_align;
unsigned HOST_WIDE_INT src_len;
char *src_buf;
use_operand_p use_p;
+ /* Not implemented yet. */
+ if (gimple_call_lhs (stmt2))
+ break;
+
if (!tree_fits_shwi_p (val2)
|| !tree_fits_uhwi_p (len2))
break;
if (is_gimple_call (stmt1))
{
/* If first stmt is a call, it needs to be memcpy
or mempcpy, with string literal as second argument and
constant length. */
callee1 = gimple_call_fndecl (stmt1);
if (callee1 == NULL_TREE
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-02-28 22:48 calloc = malloc + memset Marc Glisse
@ 2014-03-01 12:26 ` Paolo Carlini
2014-03-01 14:51 ` Marc Glisse
2014-03-03 9:50 ` Richard Biener
` (2 subsequent siblings)
3 siblings, 1 reply; 26+ messages in thread
From: Paolo Carlini @ 2014-03-01 12:26 UTC (permalink / raw)
To: Marc Glisse; +Cc: gcc-patches
Hi
> On 28/feb/2014, at 23:48, Marc Glisse <marc.glisse@inria.fr> wrote:
>
> Hello,
>
> this is a stage 1 patch, and I'll ping it then, but if you have comments now...
>
> Passes bootstrap+testsuite on x86_64-linux-gnu.
>
> 2014-02-28 Marc Glisse <marc.glisse@inria.fr>
>
> PR tree-optimization/57742
> gcc/
> * tree-ssa-forwprop.c (simplify_malloc_memset): New function.
> (simplify_builtin_call): Call it.
> gcc/testsuite/
> * g++.dg/tree-ssa/calloc.C: New testcase.
> * gcc.dg/tree-ssa/calloc.c: Likewise.
>
> --
> Marc Glisse
> Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
> ===================================================================
> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
> @@ -0,0 +1,35 @@
> +/* { dg-do compile } */
> +/* { dg-options "-std=gnu++11 -O3 -fdump-tree-optimized" } */
> +
> +#include <new>
> +#include <vector>
> +#include <cstdlib>
> +
> +void g(void*);
> +inline void* operator new(std::size_t sz) _GLIBCXX_THROW (std::bad_alloc)
Unless *really* necessary I would recommend not including the large <vector> (that also couples quite seriously the front-end testsuite to the library testsuite, we already discussed those topics in the past). Using the internal macros seems also unnecessary.
Paolo
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-03-01 12:26 ` Paolo Carlini
@ 2014-03-01 14:51 ` Marc Glisse
0 siblings, 0 replies; 26+ messages in thread
From: Marc Glisse @ 2014-03-01 14:51 UTC (permalink / raw)
To: Paolo Carlini; +Cc: gcc-patches
On Sat, 1 Mar 2014, Paolo Carlini wrote:
> Hi
>
>> On 28/feb/2014, at 23:48, Marc Glisse <marc.glisse@inria.fr> wrote:
>>
>> Hello,
>>
>> this is a stage 1 patch, and I'll ping it then, but if you have comments now...
>>
>> Passes bootstrap+testsuite on x86_64-linux-gnu.
>>
>> 2014-02-28 Marc Glisse <marc.glisse@inria.fr>
>>
>> PR tree-optimization/57742
>> gcc/
>> * tree-ssa-forwprop.c (simplify_malloc_memset): New function.
>> (simplify_builtin_call): Call it.
>> gcc/testsuite/
>> * g++.dg/tree-ssa/calloc.C: New testcase.
>> * gcc.dg/tree-ssa/calloc.c: Likewise.
>>
>> --
>> Marc Glisse
>> Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
>> ===================================================================
>> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
>> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
>> @@ -0,0 +1,35 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-std=gnu++11 -O3 -fdump-tree-optimized" } */
>> +
>> +#include <new>
>> +#include <vector>
>> +#include <cstdlib>
>> +
>> +void g(void*);
>> +inline void* operator new(std::size_t sz) _GLIBCXX_THROW (std::bad_alloc)
>
> Unless *really* necessary I would recommend not including the large
> <vector> (that also couples quite seriously the front-end testsuite to
> the library testsuite, we already discussed those topics in the past).
> Using the internal macros seems also unnecessary.
I think it might be the first time I include large headers in a compiler
testcase (note that there are already 16 other testcases including
<vector> in g++.dg). In this case, it seems to be what I want to test
though. I already have some elementary tests in gcc.dg. This testcase is
the original motivation for working on this. It requires a combination of
quite a few optimizations (inlining, recognizing that a loop is a memset,
aliasing, this optimization (the complicated version with a PHI node)),
and I want to test that we won't for instance shuffle the passes in a way
that breaks it. Also, if the library changes vector enough that this
doesn't optimize anymore, I want to know about it, either the library
change was wrong or the middle-end needs to improve some optimization
before the next release.
I wanted to keep the implementation of new as close to the one in
libsupc++ as possible (mimic LTO), so I copy-pasted (and slightly edited,
I may propose a patch to libsupc++ later). I agree that I should remove
the exception specification (since I am compiling in C++11 to have access
to get_new_handler) and replace _GLIBCXX_THROW_OR_ABORT with just throw,
and I just did it locally, thanks.
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-02-28 22:48 calloc = malloc + memset Marc Glisse
2014-03-01 12:26 ` Paolo Carlini
@ 2014-03-03 9:50 ` Richard Biener
2014-03-03 13:45 ` Marc Glisse
2014-03-23 19:47 ` Marc Glisse
2014-06-23 18:20 ` Andi Kleen
2014-07-15 12:38 ` Bernd Schmidt
3 siblings, 2 replies; 26+ messages in thread
From: Richard Biener @ 2014-03-03 9:50 UTC (permalink / raw)
To: Marc Glisse; +Cc: GCC Patches
On Fri, Feb 28, 2014 at 11:48 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> this is a stage 1 patch, and I'll ping it then, but if you have comments
> now...
>
> Passes bootstrap+testsuite on x86_64-linux-gnu.
>
> 2014-02-28 Marc Glisse <marc.glisse@inria.fr>
>
> PR tree-optimization/57742
> gcc/
> * tree-ssa-forwprop.c (simplify_malloc_memset): New function.
> (simplify_builtin_call): Call it.
> gcc/testsuite/
> * g++.dg/tree-ssa/calloc.C: New testcase.
> * gcc.dg/tree-ssa/calloc.c: Likewise.
>
> --
> Marc Glisse
> Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
> ===================================================================
> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
> @@ -0,0 +1,35 @@
> +/* { dg-do compile } */
> +/* { dg-options "-std=gnu++11 -O3 -fdump-tree-optimized" } */
> +
> +#include <new>
> +#include <vector>
> +#include <cstdlib>
> +
> +void g(void*);
> +inline void* operator new(std::size_t sz) _GLIBCXX_THROW (std::bad_alloc)
> +{
> + void *p;
> +
> + if (sz == 0)
> + sz = 1;
> +
> + // Slightly modified from the libsupc++ version, that one has 2 calls
> + // to malloc which makes it too hard to optimize.
> + while ((p = std::malloc (sz)) == 0)
> + {
> + std::new_handler handler = std::get_new_handler ();
> + if (! handler)
> + _GLIBCXX_THROW_OR_ABORT(std::bad_alloc());
> + handler ();
> + }
> + return p;
> +}
> +
> +void f(void*p,int n){
> + new(p)std::vector<int>(n);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
> Property changes on: gcc/testsuite/g++.dg/tree-ssa/calloc.C
> ___________________________________________________________________
> Added: svn:eol-style
> ## -0,0 +1 ##
> +native
> \ No newline at end of property
> Added: svn:keywords
> ## -0,0 +1 ##
> +Author Date Id Revision URL
> \ No newline at end of property
> Index: gcc/testsuite/gcc.dg/tree-ssa/calloc.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/calloc.c (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc.c (working copy)
> @@ -0,0 +1,29 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#include <stdlib.h>
> +#include <string.h>
> +
> +extern int a;
> +extern int* b;
> +int n;
> +void* f(long*q){
> + int*p=malloc(n);
> + ++*q;
> + if(p){
> + ++*q;
> + a=2;
> + memset(p,0,n);
> + *b=3;
> + }
> + return p;
> +}
> +void* g(void){
> + float*p=calloc(8,4);
> + return memset(p,0,32);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
> Property changes on: gcc/testsuite/gcc.dg/tree-ssa/calloc.c
> ___________________________________________________________________
> Added: svn:keywords
> ## -0,0 +1 ##
> +Author Date Id Revision URL
> \ No newline at end of property
> Added: svn:eol-style
> ## -0,0 +1 ##
> +native
> \ No newline at end of property
> Index: gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc/tree-ssa-forwprop.c (revision 208224)
> +++ gcc/tree-ssa-forwprop.c (working copy)
> @@ -1487,20 +1487,149 @@ constant_pointer_difference (tree p1, tr
> }
>
> for (i = 0; i < cnt[0]; i++)
> for (j = 0; j < cnt[1]; j++)
> if (exps[0][i] == exps[1][j])
> return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
>
> return NULL_TREE;
> }
>
> +/* Optimize
> + ptr = malloc (n);
> + memset (ptr, 0, n);
> + into
> + ptr = calloc (n);
> + gsi_p is known to point to a call to __builtin_memset. */
> +static bool
> +simplify_malloc_memset (gimple_stmt_iterator *gsi_p)
> +{
> + /* First make sure we have:
> + ptr = malloc (n);
> + memset (ptr, 0, n); */
> + gimple stmt2 = gsi_stmt (*gsi_p);
> + if (!integer_zerop (gimple_call_arg (stmt2, 1)))
> + return false;
> + tree ptr1, ptr2 = gimple_call_arg (stmt2, 0);
> + tree size = gimple_call_arg (stmt2, 2);
> + if (TREE_CODE (ptr2) != SSA_NAME)
> + return false;
> + gimple stmt1 = SSA_NAME_DEF_STMT (ptr2);
> + tree callee1;
> + /* Handle the case where STMT1 is a unary PHI, which happends
> + for instance with:
> + while (!(p = malloc (n))) { ... }
> + memset (p, 0, n); */
> + if (!stmt1)
> + return false;
> + if (gimple_code (stmt1) == GIMPLE_PHI
> + && gimple_phi_num_args (stmt1) == 1)
> + {
> + ptr1 = gimple_phi_arg_def (stmt1, 0);
> + if (TREE_CODE (ptr1) != SSA_NAME)
> + return false;
> + stmt1 = SSA_NAME_DEF_STMT (ptr1);
> + }
> + else
> + ptr1 = ptr2;
> + if (!stmt1
> + || !is_gimple_call (stmt1)
> + || !(callee1 = gimple_call_fndecl (stmt1)))
> + return false;
That's a bit much of ad-hoc pattern-matching ... wouldn't be
p = malloc (n);
memset (p, 0, n);
transform better suited to the strlen opt pass? After all that tracks
what 'string' is associated with a SSA name pointer through
arbitrary satements using a lattice.
> + bool is_calloc;
> + if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MALLOC)
> + {
> + is_calloc = false;
> + if (!operand_equal_p (gimple_call_arg (stmt1, 0), size, 0))
> + return false;
> + }
> + else if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_CALLOC)
> + {
> + is_calloc = true;
> + tree arg1 = gimple_call_arg (stmt1, 0);
> + tree arg2 = gimple_call_arg (stmt1, 1);
> + tree size1 = fold_build2 (MULT_EXPR, TREE_TYPE (size), arg1, arg2);
> + if (!operand_equal_p (size1, size, 0))
> + return false;
> + /* We could look at SSA_NAME_DEF_STMT (size), but there can be many
> casts
> + mixed with the MULT_EXPR which makes it hard to match with size1.
> */
The same probably applies to calloc(); memset (, 0,); though here you
could even match points-to info (after all even only clearing a portion of
the calloc()ed memory is dead code). If points-to conservatively computes
that the memset pointer only points to null or the memory tag the
calloc return value points to then you can discard it without further
checking ...
> + }
> + else
> + return false;
> +
> + /* We only allow two simple CFG forms for now. Either stmt1 and stmt2 are
> + in the same BB (in this order), or BB1 (malloc) ends with:
> + if (ptr) goto BB2 (memset) */
> + basic_block bb1 = gimple_bb (stmt1);
> + basic_block bb2 = gimple_bb (stmt2);
> + if (bb1 != bb2)
> + {
> + if (!single_pred_p (bb2) || single_pred (bb2) != bb1)
> + return false;
> + gimple cond = last_stmt (bb1);
> + if (gimple_code (cond) != GIMPLE_COND
> + || !integer_zerop (gimple_cond_rhs (cond))
> + || gimple_cond_lhs (cond) != ptr1)
> + return false;
> + int branch;
> + tree_code comp = gimple_cond_code (cond);
> + if (comp == NE_EXPR)
> + branch = EDGE_TRUE_VALUE;
> + else if (comp == EQ_EXPR)
> + branch = EDGE_FALSE_VALUE;
> + else
> + return false;
> + edge e;
> + edge_iterator ei;
> + FOR_EACH_EDGE (e, ei, bb1->succs)
> + if ((e->flags & branch) && e->dest != bb2)
> + return false;
> + }
CFG matching in forwprop ... ehhh. This really asks for integrating
this with a propagation engine.
> + /* Finally, make sure the memory is not used before stmt2. */
> + ao_ref ref;
> + ao_ref_init_from_ptr_and_size (&ref, ptr1, size);
> + tree vdef = gimple_vuse (stmt2);
> + if (vdef == NULL)
> + return false;
> + while (true)
> + {
> + gimple cur = SSA_NAME_DEF_STMT (vdef);
> + if (cur == stmt1) break;
> + if (stmt_may_clobber_ref_p_1 (cur, &ref))
> + return false;
> + vdef = gimple_vuse (cur);
> + }
We have walk_aliased_vdefs() for this.
That said, please try to integrate this kind of transforms with
the strlen opt pass (even if it requires making its lattice more generic).
The memset removal even looks like a candidate for DSE.
Thanks,
Richard.
> + /* Replace malloc with calloc and remove memset. */
> + if (!is_calloc)
> + {
> + gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
> + update_gimple_call (&gsi, builtin_decl_implicit (BUILT_IN_CALLOC), 2,
> + size, build_one_cst (size_type_node));
> + }
> + tree lhs = gimple_call_lhs (stmt2);
> + unlink_stmt_vdef (stmt2);
> + if (lhs)
> + {
> + gimple assign = gimple_build_assign (lhs, ptr2);
> + gsi_replace (gsi_p, assign, false);
> + }
> + else
> + {
> + gsi_remove (gsi_p, true);
> + release_defs (stmt2);
> + }
> + return true;
> +}
> +
> /* *GSI_P is a GIMPLE_CALL to a builtin function.
> Optimize
> memcpy (p, "abcd", 4);
> memset (p + 4, ' ', 3);
> into
> memcpy (p, "abcd ", 7);
> call if the latter can be stored by pieces during expansion. */
>
> static bool
> simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
> @@ -1508,38 +1637,44 @@ simplify_builtin_call (gimple_stmt_itera
> gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
> tree vuse = gimple_vuse (stmt2);
> if (vuse == NULL)
> return false;
> stmt1 = SSA_NAME_DEF_STMT (vuse);
>
> switch (DECL_FUNCTION_CODE (callee2))
> {
> case BUILT_IN_MEMSET:
> if (gimple_call_num_args (stmt2) != 3
> - || gimple_call_lhs (stmt2)
> || CHAR_BIT != 8
> || BITS_PER_UNIT != 8)
> break;
> else
> {
> + if (simplify_malloc_memset (gsi_p))
> + return true;
> +
> tree callee1;
> tree ptr1, src1, str1, off1, len1, lhs1;
> tree ptr2 = gimple_call_arg (stmt2, 0);
> tree val2 = gimple_call_arg (stmt2, 1);
> tree len2 = gimple_call_arg (stmt2, 2);
> tree diff, vdef, new_str_cst;
> gimple use_stmt;
> unsigned int ptr1_align;
> unsigned HOST_WIDE_INT src_len;
> char *src_buf;
> use_operand_p use_p;
>
> + /* Not implemented yet. */
> + if (gimple_call_lhs (stmt2))
> + break;
> +
> if (!tree_fits_shwi_p (val2)
> || !tree_fits_uhwi_p (len2))
> break;
> if (is_gimple_call (stmt1))
> {
> /* If first stmt is a call, it needs to be memcpy
> or mempcpy, with string literal as second argument and
> constant length. */
> callee1 = gimple_call_fndecl (stmt1);
> if (callee1 == NULL_TREE
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-03-03 9:50 ` Richard Biener
@ 2014-03-03 13:45 ` Marc Glisse
2014-03-23 19:47 ` Marc Glisse
1 sibling, 0 replies; 26+ messages in thread
From: Marc Glisse @ 2014-03-03 13:45 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches
On Mon, 3 Mar 2014, Richard Biener wrote:
> That's a bit much of ad-hoc pattern-matching ... wouldn't be
> p = malloc (n);
> memset (p, 0, n);
>
> transform better suited to the strlen opt pass? After all that tracks
> what 'string' is associated with a SSA name pointer through
> arbitrary satements using a lattice.
Too early, it needs to run later than ldist, or there won't be any
memset to match in the std::vector case. Would you consider moving or
duplicating either strlen or ldist so they are run in the order I need?
> The same probably applies to calloc(); memset (, 0,);
Oh, you mean the length doesn't have to match for calloc? That's true, I
completely missed that.
> though here you
> could even match points-to info (after all even only clearing a portion of
> the calloc()ed memory is dead code). If points-to conservatively computes
> that the memset pointer only points to null or the memory tag the
> calloc return value points to then you can discard it without further
> checking ...
I'll look into it (and DSE). Note that the calloc case is just an
afterthought, what I really care about is replacing malloc.
>> + /* Finally, make sure the memory is not used before stmt2. */
>> + ao_ref ref;
>> + ao_ref_init_from_ptr_and_size (&ref, ptr1, size);
>> + tree vdef = gimple_vuse (stmt2);
>> + if (vdef == NULL)
>> + return false;
>> + while (true)
>> + {
>> + gimple cur = SSA_NAME_DEF_STMT (vdef);
>> + if (cur == stmt1) break;
>> + if (stmt_may_clobber_ref_p_1 (cur, &ref))
>> + return false;
>> + vdef = gimple_vuse (cur);
>> + }
>
> We have walk_aliased_vdefs() for this.
As explained in the PR, walk_aliased_vdefs misses the call to malloc (it
doesn't clobber the memory pointed to by p). You then suggested:
"Exact pattern matching of the CFG involved might be the easiest, plus
manually implementing walk_aliased_vdefs by simply walking the use-def
chain of the virtual operands from the memset operation to the malloc and
checking stmt_may_clobber_ref_p_1 on the ao_ref_init_from_ptr_and_size
ref."
> That said, please try to integrate this kind of transforms with
> the strlen opt pass (even if it requires making its lattice more generic).
Assuming the passes have a chance of being reordered, I'll try to
understand how strlen works.
Thanks for the comments,
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-03-03 9:50 ` Richard Biener
2014-03-03 13:45 ` Marc Glisse
@ 2014-03-23 19:47 ` Marc Glisse
2014-04-15 19:06 ` Marc Glisse
2014-04-18 11:31 ` Jakub Jelinek
1 sibling, 2 replies; 26+ messages in thread
From: Marc Glisse @ 2014-03-23 19:47 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches
[-- Attachment #1: Type: TEXT/PLAIN, Size: 1302 bytes --]
On Mon, 3 Mar 2014, Richard Biener wrote:
> That's a bit much of ad-hoc pattern-matching ... wouldn't be
> p = malloc (n);
> memset (p, 0, n);
>
> transform better suited to the strlen opt pass? After all that tracks
> what 'string' is associated with a SSA name pointer through
> arbitrary satements using a lattice.
Like this? I had to move the strlen pass after the loop passes (and
after dom or everything was too dirty) but long enough before the end
(some optimizations are necessary after strlen). As a bonus, one more
strlen is optimized in the current testcases :-)
Running the pass twice would be another option I guess (it would require
implementing the clone method), but without a testcase showing it is
needed...
Passes bootstrap+testsuite on x86_64-linux-gnu.
2014-03-23 Marc Glisse <marc.glisse@inria.fr>
PR tree-optimization/57742
gcc/
* tree-ssa-strlen.c (get_string_length): Ignore malloc.
(handle_builtin_malloc, handle_builtin_memset): New functions.
(strlen_optimize_stmt): Call them.
* passes.def: Move strlen after loop+dom.
gcc/testsuite/
* g++.dg/tree-ssa/calloc.C: New testcase.
* gcc.dg/tree-ssa/calloc-1.c: Likewise.
* gcc.dg/tree-ssa/calloc-2.c: Likewise.
* gcc.dg/strlenopt-9.c: Adapt.
--
Marc Glisse
[-- Attachment #2: Type: TEXT/PLAIN, Size: 11605 bytes --]
Index: gcc/passes.def
===================================================================
--- gcc/passes.def (revision 208772)
+++ gcc/passes.def (working copy)
@@ -176,21 +176,20 @@ along with GCC; see the file COPYING3.
DOM and erroneous path isolation should be due to degenerate PHI nodes.
So rather than run the full propagators, run a specialized pass which
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_dce);
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
- NEXT_PASS (pass_strlen);
NEXT_PASS (pass_ccp);
/* After CCP we rewrite no longer addressed locals into SSA
form if possible. */
NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_cse_sincos);
NEXT_PASS (pass_optimize_bswap);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
NEXT_PASS (pass_sink_code);
NEXT_PASS (pass_asan);
@@ -235,20 +234,21 @@ along with GCC; see the file COPYING3.
NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_strength_reduction);
NEXT_PASS (pass_dominator);
/* The only const/copy propagation opportunities left after
DOM should be due to degenerate PHI nodes. So rather than
run the full propagators, run a specialized pass which
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
+ NEXT_PASS (pass_strlen);
NEXT_PASS (pass_vrp);
NEXT_PASS (pass_cd_dce);
NEXT_PASS (pass_tracer);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
NEXT_PASS (pass_fold_builtins);
NEXT_PASS (pass_optimize_widening_mul);
NEXT_PASS (pass_tail_calls);
NEXT_PASS (pass_rename_ssa_copies);
Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
===================================================================
--- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
+++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
@@ -0,0 +1,35 @@
+/* { dg-do compile { target c++11 } } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+#include <new>
+#include <vector>
+#include <cstdlib>
+
+void g(void*);
+inline void* operator new(std::size_t sz)
+{
+ void *p;
+
+ if (sz == 0)
+ sz = 1;
+
+ // Slightly modified from the libsupc++ version, that one has 2 calls
+ // to malloc which makes it too hard to optimize.
+ while ((p = std::malloc (sz)) == 0)
+ {
+ std::new_handler handler = std::get_new_handler ();
+ if (! handler)
+ throw std::bad_alloc();
+ handler ();
+ }
+ return p;
+}
+
+void f(void*p,int n){
+ new(p)std::vector<int>(n);
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Property changes on: gcc/testsuite/g++.dg/tree-ssa/calloc.C
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: gcc/testsuite/gcc.dg/strlenopt-9.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 208772)
+++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
@@ -11,21 +11,21 @@ fn1 (int r)
optimized away. */
return strchr (p, '\0');
}
__attribute__((noinline, noclone)) size_t
fn2 (int r)
{
char *p, q[10];
strcpy (q, "abc");
p = r ? "a" : q;
- /* String length for p varies, therefore strlen below isn't
+ /* String length is constant for both alternatives, and strlen is
optimized away. */
return strlen (p);
}
__attribute__((noinline, noclone)) size_t
fn3 (char *p, int n)
{
int i;
p = strchr (p, '\0');
/* strcat here can be optimized into memcpy. */
@@ -91,19 +91,19 @@ main ()
|| memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcd", 33) != 0
|| memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdefg", 32) != 0)
abort ();
if (fn4 (b, 256) != 4
|| memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcdabcd", 37) != 0
|| memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdabcdefgefg", 39) != 0)
abort ();
return 0;
}
-/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */
+/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */
/* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */
/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
/* { dg-final { cleanup-tree-dump "strlen" } } */
/* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#include <stdlib.h>
+#include <string.h>
+
+extern int a;
+extern int* b;
+int n;
+void* f(long*q){
+ int*p=malloc(n);
+ ++*q;
+ if(p){
+ ++*q;
+ a=2;
+ memset(p,0,n);
+ *b=3;
+ }
+ return p;
+}
+void* g(void){
+ float*p=calloc(8,4);
+ return memset(p,0,24); // not 32
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Property changes on: gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: gcc/tree-ssa-strlen.c
===================================================================
--- gcc/tree-ssa-strlen.c (revision 208772)
+++ gcc/tree-ssa-strlen.c (working copy)
@@ -496,20 +496,23 @@ get_string_length (strinfo si)
case BUILT_IN_STPCPY_CHK:
gcc_assert (lhs != NULL_TREE);
loc = gimple_location (stmt);
si->endptr = lhs;
si->stmt = NULL;
lhs = fold_convert_loc (loc, size_type_node, lhs);
si->length = fold_convert_loc (loc, size_type_node, si->ptr);
si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
lhs, si->length);
break;
+ case BUILT_IN_MALLOC:
+ break;
+ /* calloc always has si->length set. */
default:
gcc_unreachable ();
break;
}
}
return si->length;
}
/* Invalidate string length information for strings whose length
@@ -521,20 +524,21 @@ maybe_invalidate (gimple stmt)
strinfo si;
unsigned int i;
bool nonempty = false;
for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
if (si != NULL)
{
if (!si->dont_invalidate)
{
ao_ref r;
+ // Do not use si->length.
ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
if (stmt_may_clobber_ref_p_1 (stmt, &r))
{
set_strinfo (i, NULL);
free_strinfo (si);
continue;
}
}
si->dont_invalidate = false;
nonempty = true;
@@ -1608,20 +1612,90 @@ handle_builtin_strcat (enum built_in_fun
{
laststmt.stmt = stmt;
laststmt.len = srclen;
laststmt.stridx = dsi->idx;
}
}
else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
fprintf (dump_file, "not possible.\n");
}
+/* Handle a call to malloc or calloc. */
+
+static void
+handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+{
+ gimple stmt = gsi_stmt (*gsi);
+ tree lhs = gimple_call_lhs (stmt);
+ gcc_assert (get_stridx (lhs) == 0);
+ int idx = new_stridx (lhs);
+ tree length = NULL_TREE;
+ if (bcode == BUILT_IN_CALLOC)
+ length = build_int_cst (size_type_node, 0);
+ strinfo si = new_strinfo (lhs, idx, length);
+ if (bcode == BUILT_IN_CALLOC)
+ si->endptr = lhs;
+ set_strinfo (idx, si);
+ si->writable = true;
+ si->stmt = stmt;
+ si->dont_invalidate = true;
+}
+
+/* Handle a call to memset.
+ After a call to calloc, memset(,0,) is unnecessary.
+ memset(malloc(n),0,n) is calloc(n,1). */
+
+static bool
+handle_builtin_memset (gimple_stmt_iterator *gsi)
+{
+ gimple stmt1, stmt2 = gsi_stmt (*gsi);
+ if (!integer_zerop (gimple_call_arg (stmt2, 1)))
+ return true;
+ tree ptr = gimple_call_arg (stmt2, 0);
+ int idx1 = get_stridx (ptr);
+ if (idx1 <= 0)
+ return true;
+ strinfo si1 = get_strinfo (idx1);
+ if (!si1 || !(stmt1 = si1->stmt) || !is_gimple_call (stmt1))
+ return true;
+ tree callee1 = gimple_call_fndecl (stmt1);
+ if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
+ return true;
+ enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
+ tree size = gimple_call_arg (stmt2, 2);
+ 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,
+ size, build_one_cst (size_type_node));
+ }
+ else
+ return true;
+ tree lhs = gimple_call_lhs (stmt2);
+ unlink_stmt_vdef (stmt2);
+ if (lhs)
+ {
+ gimple assign = gimple_build_assign (lhs, ptr);
+ gsi_replace (gsi, assign, false);
+ }
+ else
+ {
+ gsi_remove (gsi, true);
+ release_defs (stmt2);
+ }
+
+ return false;
+}
+
/* Handle a POINTER_PLUS_EXPR statement.
For p = "abcd" + 2; compute associated length, or if
p = q + off is pointing to a '\0' character of a string, call
zero_length_string on it. */
static void
handle_pointer_plus (gimple_stmt_iterator *gsi)
{
gimple stmt = gsi_stmt (*gsi);
tree lhs = gimple_assign_lhs (stmt), off;
@@ -1845,20 +1919,28 @@ strlen_optimize_stmt (gimple_stmt_iterat
case BUILT_IN_MEMCPY:
case BUILT_IN_MEMCPY_CHK:
case BUILT_IN_MEMPCPY:
case BUILT_IN_MEMPCPY_CHK:
handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
break;
case BUILT_IN_STRCAT:
case BUILT_IN_STRCAT_CHK:
handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
break;
+ case BUILT_IN_MALLOC:
+ case BUILT_IN_CALLOC:
+ handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
+ break;
+ case BUILT_IN_MEMSET:
+ if (!handle_builtin_memset (gsi))
+ return false;
+ break;
default:
break;
}
}
else if (is_gimple_assign (stmt))
{
tree lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
{
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-03-23 19:47 ` Marc Glisse
@ 2014-04-15 19:06 ` Marc Glisse
2014-04-18 11:31 ` Jakub Jelinek
1 sibling, 0 replies; 26+ messages in thread
From: Marc Glisse @ 2014-04-15 19:06 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches
Let me ping this. There's no hurry, but it may have got lost with 4.9
approaching.
http://gcc.gnu.org/ml/gcc-patches/2014-03/msg01205.html
On Sun, 23 Mar 2014, Marc Glisse wrote:
> On Mon, 3 Mar 2014, Richard Biener wrote:
>
>> That's a bit much of ad-hoc pattern-matching ... wouldn't be
>> p = malloc (n);
>> memset (p, 0, n);
>>
>> transform better suited to the strlen opt pass? After all that tracks
>> what 'string' is associated with a SSA name pointer through
>> arbitrary satements using a lattice.
>
> Like this? I had to move the strlen pass after the loop passes (and
> after dom or everything was too dirty) but long enough before the end
> (some optimizations are necessary after strlen). As a bonus, one more
> strlen is optimized in the current testcases :-)
>
> Running the pass twice would be another option I guess (it would require
> implementing the clone method), but without a testcase showing it is
> needed...
>
> Passes bootstrap+testsuite on x86_64-linux-gnu.
>
> 2014-03-23 Marc Glisse <marc.glisse@inria.fr>
>
> PR tree-optimization/57742
> gcc/
> * tree-ssa-strlen.c (get_string_length): Ignore malloc.
> (handle_builtin_malloc, handle_builtin_memset): New functions.
> (strlen_optimize_stmt): Call them.
> * passes.def: Move strlen after loop+dom.
> gcc/testsuite/
> * g++.dg/tree-ssa/calloc.C: New testcase.
> * gcc.dg/tree-ssa/calloc-1.c: Likewise.
> * gcc.dg/tree-ssa/calloc-2.c: Likewise.
> * gcc.dg/strlenopt-9.c: Adapt.
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-03-23 19:47 ` Marc Glisse
2014-04-15 19:06 ` Marc Glisse
@ 2014-04-18 11:31 ` Jakub Jelinek
2014-04-18 18:34 ` Marc Glisse
1 sibling, 1 reply; 26+ messages in thread
From: Jakub Jelinek @ 2014-04-18 11:31 UTC (permalink / raw)
To: Marc Glisse; +Cc: Richard Biener, GCC Patches
On Sun, Mar 23, 2014 at 05:13:46PM +0100, Marc Glisse wrote:
> 2014-03-23 Marc Glisse <marc.glisse@inria.fr>
>
> PR tree-optimization/57742
> gcc/
> * tree-ssa-strlen.c (get_string_length): Ignore malloc.
> (handle_builtin_malloc, handle_builtin_memset): New functions.
> (strlen_optimize_stmt): Call them.
> * passes.def: Move strlen after loop+dom.
> gcc/testsuite/
> * g++.dg/tree-ssa/calloc.C: New testcase.
> * gcc.dg/tree-ssa/calloc-1.c: Likewise.
> * gcc.dg/tree-ssa/calloc-2.c: Likewise.
> * gcc.dg/strlenopt-9.c: Adapt.
Some CL lines are indented by 8 spaces instead of tabs.
The passes.def change makes me a little bit nervous, but if it works,
perhaps.
> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
> @@ -0,0 +1,35 @@
> +/* { dg-do compile { target c++11 } } */
> +/* { dg-options "-O3 -fdump-tree-optimized" } */
> +
> +#include <new>
> +#include <vector>
> +#include <cstdlib>
> +
> +void g(void*);
> +inline void* operator new(std::size_t sz)
> +{
> + void *p;
> +
> + if (sz == 0)
> + sz = 1;
> +
> + // Slightly modified from the libsupc++ version, that one has 2 calls
> + // to malloc which makes it too hard to optimize.
> + while ((p = std::malloc (sz)) == 0)
> + {
> + std::new_handler handler = std::get_new_handler ();
> + if (! handler)
> + throw std::bad_alloc();
> + handler ();
> + }
> + return p;
> +}
> +
> +void f(void*p,int n){
> + new(p)std::vector<int>(n);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
This looks to me way too much fragile, any time the libstdc++
or glibc headers change a little bit, you might need to adjust the
dg-final directives. Much better would be if you just provided
the prototypes yourself and subset of the std::vector you really need for
the testcase. You can throw some class or int, it doesn't have to be
std::bad_alloc, etc.
> --- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 208772)
> +++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
> @@ -11,21 +11,21 @@ fn1 (int r)
> optimized away. */
> return strchr (p, '\0');
> }
>
> __attribute__((noinline, noclone)) size_t
> fn2 (int r)
> {
> char *p, q[10];
> strcpy (q, "abc");
> p = r ? "a" : q;
> - /* String length for p varies, therefore strlen below isn't
> + /* String length is constant for both alternatives, and strlen is
> optimized away. */
> return strlen (p);
Is this because of jump threading?
> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
> @@ -0,0 +1,29 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#include <stdlib.h>
> +#include <string.h>
Even this I find unsafe. The strlenopt*.c tests use it's custom
strlenopt.h header for a reason, you might just add a calloc
prototype in there and use that header.
> --- gcc/tree-ssa-strlen.c (revision 208772)
> +++ gcc/tree-ssa-strlen.c (working copy)
> @@ -496,20 +496,23 @@ get_string_length (strinfo si)
> case BUILT_IN_STPCPY_CHK:
> gcc_assert (lhs != NULL_TREE);
> loc = gimple_location (stmt);
> si->endptr = lhs;
> si->stmt = NULL;
> lhs = fold_convert_loc (loc, size_type_node, lhs);
> si->length = fold_convert_loc (loc, size_type_node, si->ptr);
> si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
> lhs, si->length);
> break;
> + case BUILT_IN_MALLOC:
> + break;
> + /* calloc always has si->length set. */
I guess it would be better to talk about BUILT_IN_CALLOC here, and align
the comment with case and default column, to make it clear the comment
is not about BUILT_IN_MALLOC. Or is it?
But, see below.
> default:
> if (!si->dont_invalidate)
> {
> ao_ref r;
> + // Do not use si->length.
As the whole file uses /* ... */ comments, can you use them here too?
> ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
> if (stmt_may_clobber_ref_p_1 (stmt, &r))
> {
> set_strinfo (i, NULL);
> free_strinfo (si);
> continue;
> }
> }
> si->dont_invalidate = false;
> nonempty = true;
> @@ -1608,20 +1612,90 @@ handle_builtin_strcat (enum built_in_fun
> {
> laststmt.stmt = stmt;
> laststmt.len = srclen;
> laststmt.stridx = dsi->idx;
> }
> }
> else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
> fprintf (dump_file, "not possible.\n");
> }
>
> +/* Handle a call to malloc or calloc. */
> +
> +static void
> +handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
> +{
> + gimple stmt = gsi_stmt (*gsi);
> + tree lhs = gimple_call_lhs (stmt);
> + gcc_assert (get_stridx (lhs) == 0);
> + int idx = new_stridx (lhs);
> + tree length = NULL_TREE;
> + if (bcode == BUILT_IN_CALLOC)
> + length = build_int_cst (size_type_node, 0);
Is this safe? I mean, if you call int a = 0; ptr = calloc (a, n);
or ptr = calloc (n, a); or ptr = calloc (0, 0); etc., then there is no
zero termination. Sure, calling strlen or strchr etc. on the result
is undefined behavior, just wondering if it isn't going to break anything.
Though, the result is zero length and thus any dereferencing would be a bug,
so perhaps we are fine.
> +static bool
> +handle_builtin_memset (gimple_stmt_iterator *gsi)
> +{
> + gimple stmt1, stmt2 = gsi_stmt (*gsi);
> + if (!integer_zerop (gimple_call_arg (stmt2, 1)))
> + return true;
> + tree ptr = gimple_call_arg (stmt2, 0);
> + int idx1 = get_stridx (ptr);
> + if (idx1 <= 0)
> + return true;
> + strinfo si1 = get_strinfo (idx1);
> + if (!si1 || !(stmt1 = si1->stmt) || !is_gimple_call (stmt1))
> + return true;
Please avoid assignments in if conditions if easily possible, in this
case just using separate if (si1 == NULL) return true; and
stmt1 = si1->stmt; and another if is IMHO better.
Jakub
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-04-18 11:31 ` Jakub Jelinek
@ 2014-04-18 18:34 ` Marc Glisse
2014-04-23 14:05 ` Richard Biener
0 siblings, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-04-18 18:34 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Biener, GCC Patches
[-- Attachment #1: Type: TEXT/PLAIN, Size: 6494 bytes --]
Thanks for the comments!
On Fri, 18 Apr 2014, Jakub Jelinek wrote:
> The passes.def change makes me a little bit nervous, but if it works,
> perhaps.
Would you prefer running the pass twice? I thought there would be less
resistance to moving the pass than duplicating it. By the way, I think
even passes we run only once should have the required functions
implemented so they can be run several times (at least most of them), in
case users want to do that in plugins. I was surprised when I tried adding
a second strlen pass and the compiler refused.
>> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
>> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
>> @@ -0,0 +1,35 @@
>> +/* { dg-do compile { target c++11 } } */
>> +/* { dg-options "-O3 -fdump-tree-optimized" } */
>> +
>> +#include <new>
>> +#include <vector>
>> +#include <cstdlib>
>> +
>> +void g(void*);
>> +inline void* operator new(std::size_t sz)
>> +{
>> + void *p;
>> +
>> + if (sz == 0)
>> + sz = 1;
>> +
>> + // Slightly modified from the libsupc++ version, that one has 2 calls
>> + // to malloc which makes it too hard to optimize.
>> + while ((p = std::malloc (sz)) == 0)
>> + {
>> + std::new_handler handler = std::get_new_handler ();
>> + if (! handler)
>> + throw std::bad_alloc();
>> + handler ();
>> + }
>> + return p;
>> +}
>> +
>> +void f(void*p,int n){
>> + new(p)std::vector<int>(n);
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
> This looks to me way too much fragile, any time the libstdc++
> or glibc headers change a little bit, you might need to adjust the
> dg-final directives. Much better would be if you just provided
> the prototypes yourself and subset of the std::vector you really need for
> the testcase. You can throw some class or int, it doesn't have to be
> std::bad_alloc, etc.
I don't understand what seems so fragile to you. There is a single
function in the .optimized dump, which just calls calloc in a loop. It
doesn't seem that likely that a change in glibc/libstdc++ would make an
extra memset pop up. A change in libstdc++ could easily prevent the
optimization completely (I'd like to hope we can avoid that, half of the
purpose of the testcase was making sure libstdc++ didn't change in a bad
way), but I don't really see how it could keep it in a way that requires
tweaking dg-final.
While trying to write a standalone version, I hit again many missed
optimizations, getting such nice things in the .optimized dump as:
_12 = p_13 + sz_7;
if (_12 != p_13)
or:
_12 = p_13 + sz_7;
_30 = (unsigned long) _12;
_9 = p_13 + 4;
_10 = (unsigned long) _9;
_11 = _30 - _10;
_22 = _11 /[ex] 4;
_21 = _22;
_40 = _21 + 1;
_34 = _40 * 4;
It is embarrassing... I hope the combiner GSoC will work well and we can
just add a dozen patterns to handle this before 4.10.
>> --- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 208772)
>> +++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
>> @@ -11,21 +11,21 @@ fn1 (int r)
>> optimized away. */
>> return strchr (p, '\0');
>> }
>>
>> __attribute__((noinline, noclone)) size_t
>> fn2 (int r)
>> {
>> char *p, q[10];
>> strcpy (q, "abc");
>> p = r ? "a" : q;
>> - /* String length for p varies, therefore strlen below isn't
>> + /* String length is constant for both alternatives, and strlen is
>> optimized away. */
>> return strlen (p);
>
> Is this because of jump threading?
It is PRE that turns:
if (r_4(D) == 0)
goto <bb 5>;
else
goto <bb 3>;
<bb 5>:
goto <bb 4>;
<bb 3>:
<bb 4>:
# p_1 = PHI <&q(5), "a"(3)>
_5 = __builtin_strlen (p_1);
into:
if (r_4(D) == 0)
goto <bb 5>;
else
goto <bb 3>;
<bb 5>:
_7 = __builtin_strlen (&q);
pretmp_8 = _7;
goto <bb 4>;
<bb 3>:
<bb 4>:
# p_1 = PHI <&q(5), "a"(3)>
# prephitmp_9 = PHI <pretmp_8(5), 1(3)>
_5 = prephitmp_9;
It says:
Found partial redundancy for expression
{call_expr<__builtin_strlen>,p_1}@.MEM_3 (0005)
>> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
>> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
>> @@ -0,0 +1,29 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +#include <stdlib.h>
>> +#include <string.h>
>
> Even this I find unsafe. The strlenopt*.c tests use it's custom
> strlenopt.h header for a reason, you might just add a calloc
> prototype in there and use that header.
Might as well use __builtin_* then.
>> +/* Handle a call to malloc or calloc. */
>> +
>> +static void
>> +handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
>> +{
>> + gimple stmt = gsi_stmt (*gsi);
>> + tree lhs = gimple_call_lhs (stmt);
>> + gcc_assert (get_stridx (lhs) == 0);
>> + int idx = new_stridx (lhs);
>> + tree length = NULL_TREE;
>> + if (bcode == BUILT_IN_CALLOC)
>> + length = build_int_cst (size_type_node, 0);
>
> Is this safe? I mean, if you call int a = 0; ptr = calloc (a, n);
> or ptr = calloc (n, a); or ptr = calloc (0, 0); etc., then there is no
> zero termination. Sure, calling strlen or strchr etc. on the result
> is undefined behavior, just wondering if it isn't going to break anything.
> Though, the result is zero length and thus any dereferencing would be a bug,
> so perhaps we are fine.
You know the pass better than I do... I don't think the pass does anything
like: "all 0-length strings are equivalent, let's replace one by another
one", so I think we should be ok, but I don't mind treating calloc like
malloc here if you think it is too risky, I don't think people call
strlen(calloc(a,b)) very often, and it would let me remove the "don't use
si->length" comment.
Updated and tested on x86_64-linux-gnu.
2014-04-18 Marc Glisse <marc.glisse@inria.fr>
PR tree-optimization/57742
gcc/
* tree-ssa-strlen.c (get_string_length): Ignore malloc.
(handle_builtin_malloc, handle_builtin_memset): New functions.
(strlen_optimize_stmt): Call them.
* passes.def: Move strlen after loop+dom.
gcc/testsuite/
* g++.dg/tree-ssa/calloc.C: New testcase.
* gcc.dg/tree-ssa/calloc-1.c: Likewise.
* gcc.dg/tree-ssa/calloc-2.c: Likewise.
* gcc.dg/strlenopt-9.c: Adapt.
--
Marc Glisse
[-- Attachment #2: Type: TEXT/PLAIN, Size: 12219 bytes --]
Index: gcc/passes.def
===================================================================
--- gcc/passes.def (revision 209516)
+++ gcc/passes.def (working copy)
@@ -176,21 +176,20 @@ along with GCC; see the file COPYING3.
DOM and erroneous path isolation should be due to degenerate PHI nodes.
So rather than run the full propagators, run a specialized pass which
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_dce);
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
- NEXT_PASS (pass_strlen);
NEXT_PASS (pass_ccp);
/* After CCP we rewrite no longer addressed locals into SSA
form if possible. */
NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_cse_sincos);
NEXT_PASS (pass_optimize_bswap);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
NEXT_PASS (pass_sink_code);
NEXT_PASS (pass_asan);
@@ -235,20 +234,21 @@ along with GCC; see the file COPYING3.
NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_strength_reduction);
NEXT_PASS (pass_dominator);
/* The only const/copy propagation opportunities left after
DOM should be due to degenerate PHI nodes. So rather than
run the full propagators, run a specialized pass which
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
+ NEXT_PASS (pass_strlen);
NEXT_PASS (pass_vrp);
NEXT_PASS (pass_cd_dce);
NEXT_PASS (pass_tracer);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
NEXT_PASS (pass_fold_builtins);
NEXT_PASS (pass_optimize_widening_mul);
NEXT_PASS (pass_tail_calls);
NEXT_PASS (pass_rename_ssa_copies);
Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
===================================================================
--- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
+++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+typedef __SIZE_TYPE__ size_t;
+inline void* operator new(size_t, void* p) throw() { return p; }
+
+typedef void (*handler_t)(void);
+extern handler_t get_handle();
+
+inline void* operator new(size_t sz)
+{
+ void *p;
+
+ if (sz == 0)
+ sz = 1;
+
+ while ((p = __builtin_malloc (sz)) == 0)
+ {
+ handler_t handler = get_handle ();
+ if (! handler)
+ throw 42;
+ handler ();
+ }
+ return p;
+}
+
+struct vect {
+ int *start, *end;
+ vect(size_t n) {
+ start = end = 0;
+ if (n > (size_t)-1 / sizeof(int))
+ throw 33;
+ if (n != 0)
+ start = static_cast<int*> (operator new (n * sizeof(int)));
+ end = start + n;
+ int *p = start;
+ for (size_t l = n; l > 0; --l, ++p)
+ *p = 0;
+ }
+};
+
+void f (void *p, int n)
+{
+ new (p) vect(n);
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/strlenopt-9.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 209516)
+++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
@@ -11,21 +11,21 @@ fn1 (int r)
optimized away. */
return strchr (p, '\0');
}
__attribute__((noinline, noclone)) size_t
fn2 (int r)
{
char *p, q[10];
strcpy (q, "abc");
p = r ? "a" : q;
- /* String length for p varies, therefore strlen below isn't
+ /* String length is constant for both alternatives, and strlen is
optimized away. */
return strlen (p);
}
__attribute__((noinline, noclone)) size_t
fn3 (char *p, int n)
{
int i;
p = strchr (p, '\0');
/* strcat here can be optimized into memcpy. */
@@ -91,19 +91,19 @@ main ()
|| memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcd", 33) != 0
|| memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdefg", 32) != 0)
abort ();
if (fn4 (b, 256) != 4
|| memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcdabcd", 37) != 0
|| memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdabcdefgefg", 39) != 0)
abort ();
return 0;
}
-/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */
+/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */
/* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */
/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
/* { dg-final { cleanup-tree-dump "strlen" } } */
/* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+extern int a;
+extern int *b;
+int n;
+void* f(long *q)
+{
+ int *p = __builtin_malloc (n);
+ ++*q;
+ if (p)
+ {
+ ++*q;
+ a = 2;
+ __builtin_memset (p, 0, n);
+ *b = 3;
+ }
+ return p;
+}
+void* g(void)
+{
+ float *p = __builtin_calloc (8, 4);
+ return __builtin_memset (p, 0, 24); // not 32
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (working copy)
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int n, nn;
+void* f()
+{
+ char *p = __builtin_calloc (n, 1);
+ p[42] = '\n';
+ __builtin_memset (p, 0, nn);
+ return p;
+}
+
+void* g(int m1, int m2)
+{
+ char *p = __builtin_malloc (m2);
+ while (--m1)
+ {
+ __builtin_memset (p, 0, m2);
+ p[n] = 'b';
+ }
+ return p;
+}
+
+/* { dg-final { scan-tree-dump-times "malloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "memset" 2 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/tree-ssa-strlen.c
===================================================================
--- gcc/tree-ssa-strlen.c (revision 209516)
+++ gcc/tree-ssa-strlen.c (working copy)
@@ -496,20 +496,23 @@ get_string_length (strinfo si)
case BUILT_IN_STPCPY_CHK:
gcc_assert (lhs != NULL_TREE);
loc = gimple_location (stmt);
si->endptr = lhs;
si->stmt = NULL;
lhs = fold_convert_loc (loc, size_type_node, lhs);
si->length = fold_convert_loc (loc, size_type_node, si->ptr);
si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
lhs, si->length);
break;
+ case BUILT_IN_MALLOC:
+ break;
+ /* BUILT_IN_CALLOC always has si->length set. */
default:
gcc_unreachable ();
break;
}
}
return si->length;
}
/* Invalidate string length information for strings whose length
@@ -521,20 +524,21 @@ maybe_invalidate (gimple stmt)
strinfo si;
unsigned int i;
bool nonempty = false;
for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
if (si != NULL)
{
if (!si->dont_invalidate)
{
ao_ref r;
+ /* Do not use si->length. */
ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
if (stmt_may_clobber_ref_p_1 (stmt, &r))
{
set_strinfo (i, NULL);
free_strinfo (si);
continue;
}
}
si->dont_invalidate = false;
nonempty = true;
@@ -1608,20 +1612,93 @@ handle_builtin_strcat (enum built_in_fun
{
laststmt.stmt = stmt;
laststmt.len = srclen;
laststmt.stridx = dsi->idx;
}
}
else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
fprintf (dump_file, "not possible.\n");
}
+/* Handle a call to malloc or calloc. */
+
+static void
+handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+{
+ gimple stmt = gsi_stmt (*gsi);
+ tree lhs = gimple_call_lhs (stmt);
+ gcc_assert (get_stridx (lhs) == 0);
+ int idx = new_stridx (lhs);
+ tree length = NULL_TREE;
+ if (bcode == BUILT_IN_CALLOC)
+ length = build_int_cst (size_type_node, 0);
+ strinfo si = new_strinfo (lhs, idx, length);
+ if (bcode == BUILT_IN_CALLOC)
+ si->endptr = lhs;
+ set_strinfo (idx, si);
+ si->writable = true;
+ si->stmt = stmt;
+ si->dont_invalidate = true;
+}
+
+/* Handle a call to memset.
+ After a call to calloc, memset(,0,) is unnecessary.
+ memset(malloc(n),0,n) is calloc(n,1). */
+
+static bool
+handle_builtin_memset (gimple_stmt_iterator *gsi)
+{
+ gimple stmt2 = gsi_stmt (*gsi);
+ if (!integer_zerop (gimple_call_arg (stmt2, 1)))
+ return true;
+ tree ptr = gimple_call_arg (stmt2, 0);
+ int idx1 = get_stridx (ptr);
+ if (idx1 <= 0)
+ return true;
+ strinfo si1 = get_strinfo (idx1);
+ if (!si1)
+ return true;
+ gimple stmt1 = si1->stmt;
+ if (!stmt1 || !is_gimple_call (stmt1))
+ return true;
+ tree callee1 = gimple_call_fndecl (stmt1);
+ if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
+ return true;
+ enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
+ tree size = gimple_call_arg (stmt2, 2);
+ 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,
+ size, build_one_cst (size_type_node));
+ }
+ else
+ return true;
+ tree lhs = gimple_call_lhs (stmt2);
+ unlink_stmt_vdef (stmt2);
+ if (lhs)
+ {
+ gimple assign = gimple_build_assign (lhs, ptr);
+ gsi_replace (gsi, assign, false);
+ }
+ else
+ {
+ gsi_remove (gsi, true);
+ release_defs (stmt2);
+ }
+
+ return false;
+}
+
/* Handle a POINTER_PLUS_EXPR statement.
For p = "abcd" + 2; compute associated length, or if
p = q + off is pointing to a '\0' character of a string, call
zero_length_string on it. */
static void
handle_pointer_plus (gimple_stmt_iterator *gsi)
{
gimple stmt = gsi_stmt (*gsi);
tree lhs = gimple_assign_lhs (stmt), off;
@@ -1845,20 +1922,28 @@ strlen_optimize_stmt (gimple_stmt_iterat
case BUILT_IN_MEMCPY:
case BUILT_IN_MEMCPY_CHK:
case BUILT_IN_MEMPCPY:
case BUILT_IN_MEMPCPY_CHK:
handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
break;
case BUILT_IN_STRCAT:
case BUILT_IN_STRCAT_CHK:
handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
break;
+ case BUILT_IN_MALLOC:
+ case BUILT_IN_CALLOC:
+ handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
+ break;
+ case BUILT_IN_MEMSET:
+ if (!handle_builtin_memset (gsi))
+ return false;
+ break;
default:
break;
}
}
else if (is_gimple_assign (stmt))
{
tree lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
{
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-04-18 18:34 ` Marc Glisse
@ 2014-04-23 14:05 ` Richard Biener
2014-05-17 14:19 ` Marc Glisse
0 siblings, 1 reply; 26+ messages in thread
From: Richard Biener @ 2014-04-23 14:05 UTC (permalink / raw)
To: Marc Glisse; +Cc: Jakub Jelinek, GCC Patches
On Fri, Apr 18, 2014 at 8:27 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Thanks for the comments!
>
>
> On Fri, 18 Apr 2014, Jakub Jelinek wrote:
>
>> The passes.def change makes me a little bit nervous, but if it works,
>> perhaps.
>
>
> Would you prefer running the pass twice? I thought there would be less
> resistance to moving the pass than duplicating it.
Indeed. I think placing it after loops and CSE (thus what you have done)
makes sense. strlenopt itself shouldn't enable much additional
optimizations. But well, pass ordering is always tricky.
Didn't look at the rest of the changes, but Jakub is certainly able to
approve the patch so I leave it to him.
Thanks,
Richard.
> By the way, I think even
> passes we run only once should have the required functions implemented so
> they can be run several times (at least most of them), in case users want to
> do that in plugins. I was surprised when I tried adding a second strlen pass
> and the compiler refused.
>
>
>>> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
>>> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
>>> @@ -0,0 +1,35 @@
>>> +/* { dg-do compile { target c++11 } } */
>>> +/* { dg-options "-O3 -fdump-tree-optimized" } */
>>> +
>>> +#include <new>
>>> +#include <vector>
>>> +#include <cstdlib>
>>> +
>>> +void g(void*);
>>> +inline void* operator new(std::size_t sz)
>>> +{
>>> + void *p;
>>> +
>>> + if (sz == 0)
>>> + sz = 1;
>>> +
>>> + // Slightly modified from the libsupc++ version, that one has 2 calls
>>> + // to malloc which makes it too hard to optimize.
>>> + while ((p = std::malloc (sz)) == 0)
>>> + {
>>> + std::new_handler handler = std::get_new_handler ();
>>> + if (! handler)
>>> + throw std::bad_alloc();
>>> + handler ();
>>> + }
>>> + return p;
>>> +}
>>> +
>>> +void f(void*p,int n){
>>> + new(p)std::vector<int>(n);
>>> +}
>>> +
>>> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
>>> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
>>> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
>>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>>
>>
>> This looks to me way too much fragile, any time the libstdc++
>> or glibc headers change a little bit, you might need to adjust the
>> dg-final directives. Much better would be if you just provided
>> the prototypes yourself and subset of the std::vector you really need for
>> the testcase. You can throw some class or int, it doesn't have to be
>> std::bad_alloc, etc.
>
>
> I don't understand what seems so fragile to you. There is a single function
> in the .optimized dump, which just calls calloc in a loop. It doesn't seem
> that likely that a change in glibc/libstdc++ would make an extra memset pop
> up. A change in libstdc++ could easily prevent the optimization completely
> (I'd like to hope we can avoid that, half of the purpose of the testcase was
> making sure libstdc++ didn't change in a bad way), but I don't really see
> how it could keep it in a way that requires tweaking dg-final.
>
> While trying to write a standalone version, I hit again many missed
> optimizations, getting such nice things in the .optimized dump as:
>
> _12 = p_13 + sz_7;
> if (_12 != p_13)
>
> or:
>
> _12 = p_13 + sz_7;
> _30 = (unsigned long) _12;
> _9 = p_13 + 4;
> _10 = (unsigned long) _9;
> _11 = _30 - _10;
> _22 = _11 /[ex] 4;
> _21 = _22;
> _40 = _21 + 1;
> _34 = _40 * 4;
>
> It is embarrassing... I hope the combiner GSoC will work well and we can
> just add a dozen patterns to handle this before 4.10.
>
>
>>> --- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 208772)
>>> +++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
>>> @@ -11,21 +11,21 @@ fn1 (int r)
>>> optimized away. */
>>> return strchr (p, '\0');
>>> }
>>>
>>> __attribute__((noinline, noclone)) size_t
>>> fn2 (int r)
>>> {
>>> char *p, q[10];
>>> strcpy (q, "abc");
>>> p = r ? "a" : q;
>>> - /* String length for p varies, therefore strlen below isn't
>>> + /* String length is constant for both alternatives, and strlen is
>>> optimized away. */
>>> return strlen (p);
>>
>>
>> Is this because of jump threading?
>
>
> It is PRE that turns:
>
> if (r_4(D) == 0)
> goto <bb 5>;
> else
> goto <bb 3>;
>
> <bb 5>:
> goto <bb 4>;
>
> <bb 3>:
>
> <bb 4>:
> # p_1 = PHI <&q(5), "a"(3)>
> _5 = __builtin_strlen (p_1);
>
> into:
>
> if (r_4(D) == 0)
> goto <bb 5>;
> else
> goto <bb 3>;
>
> <bb 5>:
> _7 = __builtin_strlen (&q);
> pretmp_8 = _7;
> goto <bb 4>;
>
> <bb 3>:
>
> <bb 4>:
> # p_1 = PHI <&q(5), "a"(3)>
> # prephitmp_9 = PHI <pretmp_8(5), 1(3)>
> _5 = prephitmp_9;
>
> It says:
>
> Found partial redundancy for expression
> {call_expr<__builtin_strlen>,p_1}@.MEM_3 (0005)
>
>
>>> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
>>> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
>>> @@ -0,0 +1,29 @@
>>> +/* { dg-do compile } */
>>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>>> +
>>> +#include <stdlib.h>
>>> +#include <string.h>
>>
>>
>> Even this I find unsafe. The strlenopt*.c tests use it's custom
>> strlenopt.h header for a reason, you might just add a calloc
>> prototype in there and use that header.
>
>
> Might as well use __builtin_* then.
>
>
>>> +/* Handle a call to malloc or calloc. */
>>> +
>>> +static void
>>> +handle_builtin_malloc (enum built_in_function bcode,
>>> gimple_stmt_iterator *gsi)
>>> +{
>>> + gimple stmt = gsi_stmt (*gsi);
>>> + tree lhs = gimple_call_lhs (stmt);
>>> + gcc_assert (get_stridx (lhs) == 0);
>>> + int idx = new_stridx (lhs);
>>> + tree length = NULL_TREE;
>>> + if (bcode == BUILT_IN_CALLOC)
>>> + length = build_int_cst (size_type_node, 0);
>>
>>
>> Is this safe? I mean, if you call int a = 0; ptr = calloc (a, n);
>> or ptr = calloc (n, a); or ptr = calloc (0, 0); etc., then there is no
>> zero termination. Sure, calling strlen or strchr etc. on the result
>> is undefined behavior, just wondering if it isn't going to break anything.
>> Though, the result is zero length and thus any dereferencing would be a
>> bug,
>> so perhaps we are fine.
>
>
> You know the pass better than I do... I don't think the pass does anything
> like: "all 0-length strings are equivalent, let's replace one by another
> one", so I think we should be ok, but I don't mind treating calloc like
> malloc here if you think it is too risky, I don't think people call
> strlen(calloc(a,b)) very often, and it would let me remove the "don't use
> si->length" comment.
>
>
> Updated and tested on x86_64-linux-gnu.
>
> 2014-04-18 Marc Glisse <marc.glisse@inria.fr>
>
>
> PR tree-optimization/57742
> gcc/
> * tree-ssa-strlen.c (get_string_length): Ignore malloc.
> (handle_builtin_malloc, handle_builtin_memset): New functions.
> (strlen_optimize_stmt): Call them.
> * passes.def: Move strlen after loop+dom.
> gcc/testsuite/
> * g++.dg/tree-ssa/calloc.C: New testcase.
> * gcc.dg/tree-ssa/calloc-1.c: Likewise.
> * gcc.dg/tree-ssa/calloc-2.c: Likewise.
> * gcc.dg/strlenopt-9.c: Adapt.
>
> --
> Marc Glisse
> Index: gcc/passes.def
> ===================================================================
> --- gcc/passes.def (revision 209516)
> +++ gcc/passes.def (working copy)
> @@ -176,21 +176,20 @@ along with GCC; see the file COPYING3.
> DOM and erroneous path isolation should be due to degenerate PHI
> nodes.
> So rather than run the full propagators, run a specialized pass
> which
> only examines PHIs to discover const/copy propagation
> opportunities. */
> NEXT_PASS (pass_phi_only_cprop);
> NEXT_PASS (pass_dse);
> NEXT_PASS (pass_reassoc);
> NEXT_PASS (pass_dce);
> NEXT_PASS (pass_forwprop);
> NEXT_PASS (pass_phiopt);
> - NEXT_PASS (pass_strlen);
> NEXT_PASS (pass_ccp);
> /* After CCP we rewrite no longer addressed locals into SSA
> form if possible. */
> NEXT_PASS (pass_copy_prop);
> NEXT_PASS (pass_cse_sincos);
> NEXT_PASS (pass_optimize_bswap);
> NEXT_PASS (pass_split_crit_edges);
> NEXT_PASS (pass_pre);
> NEXT_PASS (pass_sink_code);
> NEXT_PASS (pass_asan);
> @@ -235,20 +234,21 @@ along with GCC; see the file COPYING3.
> NEXT_PASS (pass_cse_reciprocals);
> NEXT_PASS (pass_reassoc);
> NEXT_PASS (pass_strength_reduction);
> NEXT_PASS (pass_dominator);
> /* The only const/copy propagation opportunities left after
> DOM should be due to degenerate PHI nodes. So rather than
> run the full propagators, run a specialized pass which
> only examines PHIs to discover const/copy propagation
> opportunities. */
> NEXT_PASS (pass_phi_only_cprop);
> + NEXT_PASS (pass_strlen);
> NEXT_PASS (pass_vrp);
> NEXT_PASS (pass_cd_dce);
> NEXT_PASS (pass_tracer);
> NEXT_PASS (pass_dse);
> NEXT_PASS (pass_forwprop);
> NEXT_PASS (pass_phiopt);
> NEXT_PASS (pass_fold_builtins);
> NEXT_PASS (pass_optimize_widening_mul);
> NEXT_PASS (pass_tail_calls);
> NEXT_PASS (pass_rename_ssa_copies);
> Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
> ===================================================================
> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
> @@ -0,0 +1,50 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-optimized" } */
> +
> +typedef __SIZE_TYPE__ size_t;
> +inline void* operator new(size_t, void* p) throw() { return p; }
> +
> +typedef void (*handler_t)(void);
> +extern handler_t get_handle();
> +
> +inline void* operator new(size_t sz)
> +{
> + void *p;
> +
> + if (sz == 0)
> + sz = 1;
> +
> + while ((p = __builtin_malloc (sz)) == 0)
> + {
> + handler_t handler = get_handle ();
> + if (! handler)
> + throw 42;
> + handler ();
> + }
> + return p;
> +}
> +
> +struct vect {
> + int *start, *end;
> + vect(size_t n) {
> + start = end = 0;
> + if (n > (size_t)-1 / sizeof(int))
> + throw 33;
> + if (n != 0)
> + start = static_cast<int*> (operator new (n * sizeof(int)));
> + end = start + n;
> + int *p = start;
> + for (size_t l = n; l > 0; --l, ++p)
> + *p = 0;
> + }
> +};
> +
> +void f (void *p, int n)
> +{
> + new (p) vect(n);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc/testsuite/gcc.dg/strlenopt-9.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 209516)
> +++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
> @@ -11,21 +11,21 @@ fn1 (int r)
> optimized away. */
> return strchr (p, '\0');
> }
>
> __attribute__((noinline, noclone)) size_t
> fn2 (int r)
> {
> char *p, q[10];
> strcpy (q, "abc");
> p = r ? "a" : q;
> - /* String length for p varies, therefore strlen below isn't
> + /* String length is constant for both alternatives, and strlen is
> optimized away. */
> return strlen (p);
> }
>
> __attribute__((noinline, noclone)) size_t
> fn3 (char *p, int n)
> {
> int i;
> p = strchr (p, '\0');
> /* strcat here can be optimized into memcpy. */
> @@ -91,19 +91,19 @@ main ()
> || memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcd", 33) != 0
> || memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdefg", 32) != 0)
> abort ();
> if (fn4 (b, 256) != 4
> || memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcdabcd", 37) != 0
> || memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdabcdefgefg", 39) != 0)
> abort ();
> return 0;
> }
>
> -/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */
> +/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */
> /* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */
> /* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */
> /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
> /* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */
> /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
> /* { dg-final { cleanup-tree-dump "strlen" } } */
> /* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */
> /* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
> @@ -0,0 +1,29 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +extern int a;
> +extern int *b;
> +int n;
> +void* f(long *q)
> +{
> + int *p = __builtin_malloc (n);
> + ++*q;
> + if (p)
> + {
> + ++*q;
> + a = 2;
> + __builtin_memset (p, 0, n);
> + *b = 3;
> + }
> + return p;
> +}
> +void* g(void)
> +{
> + float *p = __builtin_calloc (8, 4);
> + return __builtin_memset (p, 0, 24); // not 32
> +}
> +
> +/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (working copy)
> @@ -0,0 +1,27 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int n, nn;
> +void* f()
> +{
> + char *p = __builtin_calloc (n, 1);
> + p[42] = '\n';
> + __builtin_memset (p, 0, nn);
> + return p;
> +}
> +
> +void* g(int m1, int m2)
> +{
> + char *p = __builtin_malloc (m2);
> + while (--m1)
> + {
> + __builtin_memset (p, 0, m2);
> + p[n] = 'b';
> + }
> + return p;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "malloc" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "memset" 2 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc/tree-ssa-strlen.c
> ===================================================================
> --- gcc/tree-ssa-strlen.c (revision 209516)
> +++ gcc/tree-ssa-strlen.c (working copy)
> @@ -496,20 +496,23 @@ get_string_length (strinfo si)
> case BUILT_IN_STPCPY_CHK:
> gcc_assert (lhs != NULL_TREE);
> loc = gimple_location (stmt);
> si->endptr = lhs;
> si->stmt = NULL;
> lhs = fold_convert_loc (loc, size_type_node, lhs);
> si->length = fold_convert_loc (loc, size_type_node, si->ptr);
> si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
> lhs, si->length);
> break;
> + case BUILT_IN_MALLOC:
> + break;
> + /* BUILT_IN_CALLOC always has si->length set. */
> default:
> gcc_unreachable ();
> break;
> }
> }
>
> return si->length;
> }
>
> /* Invalidate string length information for strings whose length
> @@ -521,20 +524,21 @@ maybe_invalidate (gimple stmt)
> strinfo si;
> unsigned int i;
> bool nonempty = false;
>
> for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
> if (si != NULL)
> {
> if (!si->dont_invalidate)
> {
> ao_ref r;
> + /* Do not use si->length. */
> ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
> if (stmt_may_clobber_ref_p_1 (stmt, &r))
> {
> set_strinfo (i, NULL);
> free_strinfo (si);
> continue;
> }
> }
> si->dont_invalidate = false;
> nonempty = true;
> @@ -1608,20 +1612,93 @@ handle_builtin_strcat (enum built_in_fun
> {
> laststmt.stmt = stmt;
> laststmt.len = srclen;
> laststmt.stridx = dsi->idx;
> }
> }
> else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
> fprintf (dump_file, "not possible.\n");
> }
>
> +/* Handle a call to malloc or calloc. */
> +
> +static void
> +handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator
> *gsi)
> +{
> + gimple stmt = gsi_stmt (*gsi);
> + tree lhs = gimple_call_lhs (stmt);
> + gcc_assert (get_stridx (lhs) == 0);
> + int idx = new_stridx (lhs);
> + tree length = NULL_TREE;
> + if (bcode == BUILT_IN_CALLOC)
> + length = build_int_cst (size_type_node, 0);
> + strinfo si = new_strinfo (lhs, idx, length);
> + if (bcode == BUILT_IN_CALLOC)
> + si->endptr = lhs;
> + set_strinfo (idx, si);
> + si->writable = true;
> + si->stmt = stmt;
> + si->dont_invalidate = true;
> +}
> +
> +/* Handle a call to memset.
> + After a call to calloc, memset(,0,) is unnecessary.
> + memset(malloc(n),0,n) is calloc(n,1). */
> +
> +static bool
> +handle_builtin_memset (gimple_stmt_iterator *gsi)
> +{
> + gimple stmt2 = gsi_stmt (*gsi);
> + if (!integer_zerop (gimple_call_arg (stmt2, 1)))
> + return true;
> + tree ptr = gimple_call_arg (stmt2, 0);
> + int idx1 = get_stridx (ptr);
> + if (idx1 <= 0)
> + return true;
> + strinfo si1 = get_strinfo (idx1);
> + if (!si1)
> + return true;
> + gimple stmt1 = si1->stmt;
> + if (!stmt1 || !is_gimple_call (stmt1))
> + return true;
> + tree callee1 = gimple_call_fndecl (stmt1);
> + if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
> + return true;
> + enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
> + tree size = gimple_call_arg (stmt2, 2);
> + 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,
> + size, build_one_cst (size_type_node));
> + }
> + else
> + return true;
> + tree lhs = gimple_call_lhs (stmt2);
> + unlink_stmt_vdef (stmt2);
> + if (lhs)
> + {
> + gimple assign = gimple_build_assign (lhs, ptr);
> + gsi_replace (gsi, assign, false);
> + }
> + else
> + {
> + gsi_remove (gsi, true);
> + release_defs (stmt2);
> + }
> +
> + return false;
> +}
> +
> /* Handle a POINTER_PLUS_EXPR statement.
> For p = "abcd" + 2; compute associated length, or if
> p = q + off is pointing to a '\0' character of a string, call
> zero_length_string on it. */
>
> static void
> handle_pointer_plus (gimple_stmt_iterator *gsi)
> {
> gimple stmt = gsi_stmt (*gsi);
> tree lhs = gimple_assign_lhs (stmt), off;
> @@ -1845,20 +1922,28 @@ strlen_optimize_stmt (gimple_stmt_iterat
> case BUILT_IN_MEMCPY:
> case BUILT_IN_MEMCPY_CHK:
> case BUILT_IN_MEMPCPY:
> case BUILT_IN_MEMPCPY_CHK:
> handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
> break;
> case BUILT_IN_STRCAT:
> case BUILT_IN_STRCAT_CHK:
> handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
> break;
> + case BUILT_IN_MALLOC:
> + case BUILT_IN_CALLOC:
> + handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
> + break;
> + case BUILT_IN_MEMSET:
> + if (!handle_builtin_memset (gsi))
> + return false;
> + break;
> default:
> break;
> }
> }
> else if (is_gimple_assign (stmt))
> {
> tree lhs = gimple_assign_lhs (stmt);
>
> if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
> {
>
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-04-23 14:05 ` Richard Biener
@ 2014-05-17 14:19 ` Marc Glisse
2014-06-03 14:00 ` Marc Glisse
0 siblings, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-05-17 14:19 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: GCC Patches
Ping Jakub?
https://gcc.gnu.org/ml/gcc-patches/2014-04/msg01104.html
On Wed, 23 Apr 2014, Richard Biener wrote:
> On Fri, Apr 18, 2014 at 8:27 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Thanks for the comments!
>>
>>
>> On Fri, 18 Apr 2014, Jakub Jelinek wrote:
>>
>>> The passes.def change makes me a little bit nervous, but if it works,
>>> perhaps.
>>
>>
>> Would you prefer running the pass twice? I thought there would be less
>> resistance to moving the pass than duplicating it.
>
> Indeed. I think placing it after loops and CSE (thus what you have done)
> makes sense. strlenopt itself shouldn't enable much additional
> optimizations. But well, pass ordering is always tricky.
>
> Didn't look at the rest of the changes, but Jakub is certainly able to
> approve the patch so I leave it to him.
>
> Thanks,
> Richard.
>
>> By the way, I think even
>> passes we run only once should have the required functions implemented so
>> they can be run several times (at least most of them), in case users want to
>> do that in plugins. I was surprised when I tried adding a second strlen pass
>> and the compiler refused.
>>
>>
>>>> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
>>>> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
>>>> @@ -0,0 +1,35 @@
>>>> +/* { dg-do compile { target c++11 } } */
>>>> +/* { dg-options "-O3 -fdump-tree-optimized" } */
>>>> +
>>>> +#include <new>
>>>> +#include <vector>
>>>> +#include <cstdlib>
>>>> +
>>>> +void g(void*);
>>>> +inline void* operator new(std::size_t sz)
>>>> +{
>>>> + void *p;
>>>> +
>>>> + if (sz == 0)
>>>> + sz = 1;
>>>> +
>>>> + // Slightly modified from the libsupc++ version, that one has 2 calls
>>>> + // to malloc which makes it too hard to optimize.
>>>> + while ((p = std::malloc (sz)) == 0)
>>>> + {
>>>> + std::new_handler handler = std::get_new_handler ();
>>>> + if (! handler)
>>>> + throw std::bad_alloc();
>>>> + handler ();
>>>> + }
>>>> + return p;
>>>> +}
>>>> +
>>>> +void f(void*p,int n){
>>>> + new(p)std::vector<int>(n);
>>>> +}
>>>> +
>>>> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
>>>> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
>>>> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
>>>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>>>
>>>
>>> This looks to me way too much fragile, any time the libstdc++
>>> or glibc headers change a little bit, you might need to adjust the
>>> dg-final directives. Much better would be if you just provided
>>> the prototypes yourself and subset of the std::vector you really need for
>>> the testcase. You can throw some class or int, it doesn't have to be
>>> std::bad_alloc, etc.
>>
>>
>> I don't understand what seems so fragile to you. There is a single function
>> in the .optimized dump, which just calls calloc in a loop. It doesn't seem
>> that likely that a change in glibc/libstdc++ would make an extra memset pop
>> up. A change in libstdc++ could easily prevent the optimization completely
>> (I'd like to hope we can avoid that, half of the purpose of the testcase was
>> making sure libstdc++ didn't change in a bad way), but I don't really see
>> how it could keep it in a way that requires tweaking dg-final.
>>
>> While trying to write a standalone version, I hit again many missed
>> optimizations, getting such nice things in the .optimized dump as:
>>
>> _12 = p_13 + sz_7;
>> if (_12 != p_13)
>>
>> or:
>>
>> _12 = p_13 + sz_7;
>> _30 = (unsigned long) _12;
>> _9 = p_13 + 4;
>> _10 = (unsigned long) _9;
>> _11 = _30 - _10;
>> _22 = _11 /[ex] 4;
>> _21 = _22;
>> _40 = _21 + 1;
>> _34 = _40 * 4;
>>
>> It is embarrassing... I hope the combiner GSoC will work well and we can
>> just add a dozen patterns to handle this before 4.10.
>>
>>
>>>> --- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 208772)
>>>> +++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
>>>> @@ -11,21 +11,21 @@ fn1 (int r)
>>>> optimized away. */
>>>> return strchr (p, '\0');
>>>> }
>>>>
>>>> __attribute__((noinline, noclone)) size_t
>>>> fn2 (int r)
>>>> {
>>>> char *p, q[10];
>>>> strcpy (q, "abc");
>>>> p = r ? "a" : q;
>>>> - /* String length for p varies, therefore strlen below isn't
>>>> + /* String length is constant for both alternatives, and strlen is
>>>> optimized away. */
>>>> return strlen (p);
>>>
>>>
>>> Is this because of jump threading?
>>
>>
>> It is PRE that turns:
>>
>> if (r_4(D) == 0)
>> goto <bb 5>;
>> else
>> goto <bb 3>;
>>
>> <bb 5>:
>> goto <bb 4>;
>>
>> <bb 3>:
>>
>> <bb 4>:
>> # p_1 = PHI <&q(5), "a"(3)>
>> _5 = __builtin_strlen (p_1);
>>
>> into:
>>
>> if (r_4(D) == 0)
>> goto <bb 5>;
>> else
>> goto <bb 3>;
>>
>> <bb 5>:
>> _7 = __builtin_strlen (&q);
>> pretmp_8 = _7;
>> goto <bb 4>;
>>
>> <bb 3>:
>>
>> <bb 4>:
>> # p_1 = PHI <&q(5), "a"(3)>
>> # prephitmp_9 = PHI <pretmp_8(5), 1(3)>
>> _5 = prephitmp_9;
>>
>> It says:
>>
>> Found partial redundancy for expression
>> {call_expr<__builtin_strlen>,p_1}@.MEM_3 (0005)
>>
>>
>>>> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
>>>> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
>>>> @@ -0,0 +1,29 @@
>>>> +/* { dg-do compile } */
>>>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>>>> +
>>>> +#include <stdlib.h>
>>>> +#include <string.h>
>>>
>>>
>>> Even this I find unsafe. The strlenopt*.c tests use it's custom
>>> strlenopt.h header for a reason, you might just add a calloc
>>> prototype in there and use that header.
>>
>>
>> Might as well use __builtin_* then.
>>
>>
>>>> +/* Handle a call to malloc or calloc. */
>>>> +
>>>> +static void
>>>> +handle_builtin_malloc (enum built_in_function bcode,
>>>> gimple_stmt_iterator *gsi)
>>>> +{
>>>> + gimple stmt = gsi_stmt (*gsi);
>>>> + tree lhs = gimple_call_lhs (stmt);
>>>> + gcc_assert (get_stridx (lhs) == 0);
>>>> + int idx = new_stridx (lhs);
>>>> + tree length = NULL_TREE;
>>>> + if (bcode == BUILT_IN_CALLOC)
>>>> + length = build_int_cst (size_type_node, 0);
>>>
>>>
>>> Is this safe? I mean, if you call int a = 0; ptr = calloc (a, n);
>>> or ptr = calloc (n, a); or ptr = calloc (0, 0); etc., then there is no
>>> zero termination. Sure, calling strlen or strchr etc. on the result
>>> is undefined behavior, just wondering if it isn't going to break anything.
>>> Though, the result is zero length and thus any dereferencing would be a
>>> bug,
>>> so perhaps we are fine.
>>
>>
>> You know the pass better than I do... I don't think the pass does anything
>> like: "all 0-length strings are equivalent, let's replace one by another
>> one", so I think we should be ok, but I don't mind treating calloc like
>> malloc here if you think it is too risky, I don't think people call
>> strlen(calloc(a,b)) very often, and it would let me remove the "don't use
>> si->length" comment.
>>
>>
>> Updated and tested on x86_64-linux-gnu.
>>
>> 2014-04-18 Marc Glisse <marc.glisse@inria.fr>
>>
>>
>> PR tree-optimization/57742
>> gcc/
>> * tree-ssa-strlen.c (get_string_length): Ignore malloc.
>> (handle_builtin_malloc, handle_builtin_memset): New functions.
>> (strlen_optimize_stmt): Call them.
>> * passes.def: Move strlen after loop+dom.
>> gcc/testsuite/
>> * g++.dg/tree-ssa/calloc.C: New testcase.
>> * gcc.dg/tree-ssa/calloc-1.c: Likewise.
>> * gcc.dg/tree-ssa/calloc-2.c: Likewise.
>> * gcc.dg/strlenopt-9.c: Adapt.
>>
>> --
>> Marc Glisse
>> Index: gcc/passes.def
>> ===================================================================
>> --- gcc/passes.def (revision 209516)
>> +++ gcc/passes.def (working copy)
>> @@ -176,21 +176,20 @@ along with GCC; see the file COPYING3.
>> DOM and erroneous path isolation should be due to degenerate PHI
>> nodes.
>> So rather than run the full propagators, run a specialized pass
>> which
>> only examines PHIs to discover const/copy propagation
>> opportunities. */
>> NEXT_PASS (pass_phi_only_cprop);
>> NEXT_PASS (pass_dse);
>> NEXT_PASS (pass_reassoc);
>> NEXT_PASS (pass_dce);
>> NEXT_PASS (pass_forwprop);
>> NEXT_PASS (pass_phiopt);
>> - NEXT_PASS (pass_strlen);
>> NEXT_PASS (pass_ccp);
>> /* After CCP we rewrite no longer addressed locals into SSA
>> form if possible. */
>> NEXT_PASS (pass_copy_prop);
>> NEXT_PASS (pass_cse_sincos);
>> NEXT_PASS (pass_optimize_bswap);
>> NEXT_PASS (pass_split_crit_edges);
>> NEXT_PASS (pass_pre);
>> NEXT_PASS (pass_sink_code);
>> NEXT_PASS (pass_asan);
>> @@ -235,20 +234,21 @@ along with GCC; see the file COPYING3.
>> NEXT_PASS (pass_cse_reciprocals);
>> NEXT_PASS (pass_reassoc);
>> NEXT_PASS (pass_strength_reduction);
>> NEXT_PASS (pass_dominator);
>> /* The only const/copy propagation opportunities left after
>> DOM should be due to degenerate PHI nodes. So rather than
>> run the full propagators, run a specialized pass which
>> only examines PHIs to discover const/copy propagation
>> opportunities. */
>> NEXT_PASS (pass_phi_only_cprop);
>> + NEXT_PASS (pass_strlen);
>> NEXT_PASS (pass_vrp);
>> NEXT_PASS (pass_cd_dce);
>> NEXT_PASS (pass_tracer);
>> NEXT_PASS (pass_dse);
>> NEXT_PASS (pass_forwprop);
>> NEXT_PASS (pass_phiopt);
>> NEXT_PASS (pass_fold_builtins);
>> NEXT_PASS (pass_optimize_widening_mul);
>> NEXT_PASS (pass_tail_calls);
>> NEXT_PASS (pass_rename_ssa_copies);
>> Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
>> ===================================================================
>> --- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
>> +++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
>> @@ -0,0 +1,50 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O3 -fdump-tree-optimized" } */
>> +
>> +typedef __SIZE_TYPE__ size_t;
>> +inline void* operator new(size_t, void* p) throw() { return p; }
>> +
>> +typedef void (*handler_t)(void);
>> +extern handler_t get_handle();
>> +
>> +inline void* operator new(size_t sz)
>> +{
>> + void *p;
>> +
>> + if (sz == 0)
>> + sz = 1;
>> +
>> + while ((p = __builtin_malloc (sz)) == 0)
>> + {
>> + handler_t handler = get_handle ();
>> + if (! handler)
>> + throw 42;
>> + handler ();
>> + }
>> + return p;
>> +}
>> +
>> +struct vect {
>> + int *start, *end;
>> + vect(size_t n) {
>> + start = end = 0;
>> + if (n > (size_t)-1 / sizeof(int))
>> + throw 33;
>> + if (n != 0)
>> + start = static_cast<int*> (operator new (n * sizeof(int)));
>> + end = start + n;
>> + int *p = start;
>> + for (size_t l = n; l > 0; --l, ++p)
>> + *p = 0;
>> + }
>> +};
>> +
>> +void f (void *p, int n)
>> +{
>> + new (p) vect(n);
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>> Index: gcc/testsuite/gcc.dg/strlenopt-9.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 209516)
>> +++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
>> @@ -11,21 +11,21 @@ fn1 (int r)
>> optimized away. */
>> return strchr (p, '\0');
>> }
>>
>> __attribute__((noinline, noclone)) size_t
>> fn2 (int r)
>> {
>> char *p, q[10];
>> strcpy (q, "abc");
>> p = r ? "a" : q;
>> - /* String length for p varies, therefore strlen below isn't
>> + /* String length is constant for both alternatives, and strlen is
>> optimized away. */
>> return strlen (p);
>> }
>>
>> __attribute__((noinline, noclone)) size_t
>> fn3 (char *p, int n)
>> {
>> int i;
>> p = strchr (p, '\0');
>> /* strcat here can be optimized into memcpy. */
>> @@ -91,19 +91,19 @@ main ()
>> || memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcd", 33) != 0
>> || memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdefg", 32) != 0)
>> abort ();
>> if (fn4 (b, 256) != 4
>> || memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcdabcd", 37) != 0
>> || memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdabcdefgefg", 39) != 0)
>> abort ();
>> return 0;
>> }
>>
>> -/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */
>> +/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */
>> /* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */
>> /* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */
>> /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
>> /* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */
>> /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
>> /* { dg-final { cleanup-tree-dump "strlen" } } */
>> /* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */
>> /* { dg-final { cleanup-tree-dump "optimized" } } */
>> Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
>> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
>> @@ -0,0 +1,29 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +extern int a;
>> +extern int *b;
>> +int n;
>> +void* f(long *q)
>> +{
>> + int *p = __builtin_malloc (n);
>> + ++*q;
>> + if (p)
>> + {
>> + ++*q;
>> + a = 2;
>> + __builtin_memset (p, 0, n);
>> + *b = 3;
>> + }
>> + return p;
>> +}
>> +void* g(void)
>> +{
>> + float *p = __builtin_calloc (8, 4);
>> + return __builtin_memset (p, 0, 24); // not 32
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>> Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (revision 0)
>> +++ gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (working copy)
>> @@ -0,0 +1,27 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +int n, nn;
>> +void* f()
>> +{
>> + char *p = __builtin_calloc (n, 1);
>> + p[42] = '\n';
>> + __builtin_memset (p, 0, nn);
>> + return p;
>> +}
>> +
>> +void* g(int m1, int m2)
>> +{
>> + char *p = __builtin_malloc (m2);
>> + while (--m1)
>> + {
>> + __builtin_memset (p, 0, m2);
>> + p[n] = 'b';
>> + }
>> + return p;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "malloc" 1 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times "memset" 2 "optimized" } } */
>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>> Index: gcc/tree-ssa-strlen.c
>> ===================================================================
>> --- gcc/tree-ssa-strlen.c (revision 209516)
>> +++ gcc/tree-ssa-strlen.c (working copy)
>> @@ -496,20 +496,23 @@ get_string_length (strinfo si)
>> case BUILT_IN_STPCPY_CHK:
>> gcc_assert (lhs != NULL_TREE);
>> loc = gimple_location (stmt);
>> si->endptr = lhs;
>> si->stmt = NULL;
>> lhs = fold_convert_loc (loc, size_type_node, lhs);
>> si->length = fold_convert_loc (loc, size_type_node, si->ptr);
>> si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
>> lhs, si->length);
>> break;
>> + case BUILT_IN_MALLOC:
>> + break;
>> + /* BUILT_IN_CALLOC always has si->length set. */
>> default:
>> gcc_unreachable ();
>> break;
>> }
>> }
>>
>> return si->length;
>> }
>>
>> /* Invalidate string length information for strings whose length
>> @@ -521,20 +524,21 @@ maybe_invalidate (gimple stmt)
>> strinfo si;
>> unsigned int i;
>> bool nonempty = false;
>>
>> for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
>> if (si != NULL)
>> {
>> if (!si->dont_invalidate)
>> {
>> ao_ref r;
>> + /* Do not use si->length. */
>> ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
>> if (stmt_may_clobber_ref_p_1 (stmt, &r))
>> {
>> set_strinfo (i, NULL);
>> free_strinfo (si);
>> continue;
>> }
>> }
>> si->dont_invalidate = false;
>> nonempty = true;
>> @@ -1608,20 +1612,93 @@ handle_builtin_strcat (enum built_in_fun
>> {
>> laststmt.stmt = stmt;
>> laststmt.len = srclen;
>> laststmt.stridx = dsi->idx;
>> }
>> }
>> else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
>> fprintf (dump_file, "not possible.\n");
>> }
>>
>> +/* Handle a call to malloc or calloc. */
>> +
>> +static void
>> +handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator
>> *gsi)
>> +{
>> + gimple stmt = gsi_stmt (*gsi);
>> + tree lhs = gimple_call_lhs (stmt);
>> + gcc_assert (get_stridx (lhs) == 0);
>> + int idx = new_stridx (lhs);
>> + tree length = NULL_TREE;
>> + if (bcode == BUILT_IN_CALLOC)
>> + length = build_int_cst (size_type_node, 0);
>> + strinfo si = new_strinfo (lhs, idx, length);
>> + if (bcode == BUILT_IN_CALLOC)
>> + si->endptr = lhs;
>> + set_strinfo (idx, si);
>> + si->writable = true;
>> + si->stmt = stmt;
>> + si->dont_invalidate = true;
>> +}
>> +
>> +/* Handle a call to memset.
>> + After a call to calloc, memset(,0,) is unnecessary.
>> + memset(malloc(n),0,n) is calloc(n,1). */
>> +
>> +static bool
>> +handle_builtin_memset (gimple_stmt_iterator *gsi)
>> +{
>> + gimple stmt2 = gsi_stmt (*gsi);
>> + if (!integer_zerop (gimple_call_arg (stmt2, 1)))
>> + return true;
>> + tree ptr = gimple_call_arg (stmt2, 0);
>> + int idx1 = get_stridx (ptr);
>> + if (idx1 <= 0)
>> + return true;
>> + strinfo si1 = get_strinfo (idx1);
>> + if (!si1)
>> + return true;
>> + gimple stmt1 = si1->stmt;
>> + if (!stmt1 || !is_gimple_call (stmt1))
>> + return true;
>> + tree callee1 = gimple_call_fndecl (stmt1);
>> + if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
>> + return true;
>> + enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
>> + tree size = gimple_call_arg (stmt2, 2);
>> + 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,
>> + size, build_one_cst (size_type_node));
>> + }
>> + else
>> + return true;
>> + tree lhs = gimple_call_lhs (stmt2);
>> + unlink_stmt_vdef (stmt2);
>> + if (lhs)
>> + {
>> + gimple assign = gimple_build_assign (lhs, ptr);
>> + gsi_replace (gsi, assign, false);
>> + }
>> + else
>> + {
>> + gsi_remove (gsi, true);
>> + release_defs (stmt2);
>> + }
>> +
>> + return false;
>> +}
>> +
>> /* Handle a POINTER_PLUS_EXPR statement.
>> For p = "abcd" + 2; compute associated length, or if
>> p = q + off is pointing to a '\0' character of a string, call
>> zero_length_string on it. */
>>
>> static void
>> handle_pointer_plus (gimple_stmt_iterator *gsi)
>> {
>> gimple stmt = gsi_stmt (*gsi);
>> tree lhs = gimple_assign_lhs (stmt), off;
>> @@ -1845,20 +1922,28 @@ strlen_optimize_stmt (gimple_stmt_iterat
>> case BUILT_IN_MEMCPY:
>> case BUILT_IN_MEMCPY_CHK:
>> case BUILT_IN_MEMPCPY:
>> case BUILT_IN_MEMPCPY_CHK:
>> handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
>> break;
>> case BUILT_IN_STRCAT:
>> case BUILT_IN_STRCAT_CHK:
>> handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
>> break;
>> + case BUILT_IN_MALLOC:
>> + case BUILT_IN_CALLOC:
>> + handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
>> + break;
>> + case BUILT_IN_MEMSET:
>> + if (!handle_builtin_memset (gsi))
>> + return false;
>> + break;
>> default:
>> break;
>> }
>> }
>> else if (is_gimple_assign (stmt))
>> {
>> tree lhs = gimple_assign_lhs (stmt);
>>
>> if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
>> {
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-05-17 14:19 ` Marc Glisse
@ 2014-06-03 14:00 ` Marc Glisse
2014-06-23 7:32 ` Jakub Jelinek
0 siblings, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-06-03 14:00 UTC (permalink / raw)
To: GCC Patches
Ping?
On Sat, 17 May 2014, Marc Glisse wrote:
> Ping Jakub?
> https://gcc.gnu.org/ml/gcc-patches/2014-04/msg01104.html
>
> On Wed, 23 Apr 2014, Richard Biener wrote:
>
>> On Fri, Apr 18, 2014 at 8:27 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>> Thanks for the comments!
>>>
>>>
>>> On Fri, 18 Apr 2014, Jakub Jelinek wrote:
>>>
>>>> The passes.def change makes me a little bit nervous, but if it works,
>>>> perhaps.
>>>
>>>
>>> Would you prefer running the pass twice? I thought there would be less
>>> resistance to moving the pass than duplicating it.
>>
>> Indeed. I think placing it after loops and CSE (thus what you have done)
>> makes sense. strlenopt itself shouldn't enable much additional
>> optimizations. But well, pass ordering is always tricky.
>>
>> Didn't look at the rest of the changes, but Jakub is certainly able to
>> approve the patch so I leave it to him.
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-03 14:00 ` Marc Glisse
@ 2014-06-23 7:32 ` Jakub Jelinek
2014-06-23 15:52 ` Marc Glisse
0 siblings, 1 reply; 26+ messages in thread
From: Jakub Jelinek @ 2014-06-23 7:32 UTC (permalink / raw)
To: Marc Glisse; +Cc: GCC Patches
On Tue, Jun 03, 2014 at 04:00:17PM +0200, Marc Glisse wrote:
> Ping?
Ok for trunk, sorry for the delay.
Jakub
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 7:32 ` Jakub Jelinek
@ 2014-06-23 15:52 ` Marc Glisse
2014-06-23 16:11 ` Richard Biener
0 siblings, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-06-23 15:52 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: GCC Patches, richard.guenther
[-- Attachment #1: Type: TEXT/PLAIN, Size: 863 bytes --]
On Mon, 23 Jun 2014, Jakub Jelinek wrote:
> Ok for trunk, sorry for the delay.
Thanks. Richard has moved the passes a bit since then, but I still have
exactly one spot where the testsuite is ok :-) I need strlen to be after
dom (for calloc.C) and before vrp (for several strlenopt-*.c). I'll commit
it tomorrow if there aren't any comments on the pass placement.
2014-06-24 Marc Glisse <marc.glisse@inria.fr>
PR tree-optimization/57742
gcc/
* tree-ssa-strlen.c (get_string_length): Ignore malloc.
(handle_builtin_malloc, handle_builtin_memset): New functions.
(strlen_optimize_stmt): Call them.
* passes.def: Move strlen after loop+dom but before vrp.
gcc/testsuite/
* g++.dg/tree-ssa/calloc.C: New testcase.
* gcc.dg/tree-ssa/calloc-1.c: Likewise.
* gcc.dg/tree-ssa/calloc-2.c: Likewise.
* gcc.dg/strlenopt-9.c: Adapt.
--
Marc Glisse
[-- Attachment #2: Type: TEXT/PLAIN, Size: 12199 bytes --]
Index: gcc/passes.def
===================================================================
--- gcc/passes.def (revision 211886)
+++ gcc/passes.def (working copy)
@@ -179,21 +179,20 @@ along with GCC; see the file COPYING3.
DOM and erroneous path isolation should be due to degenerate PHI nodes.
So rather than run the full propagators, run a specialized pass which
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_dce);
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
- NEXT_PASS (pass_strlen);
NEXT_PASS (pass_ccp);
/* After CCP we rewrite no longer addressed locals into SSA
form if possible. */
NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_cse_sincos);
NEXT_PASS (pass_optimize_bswap);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
NEXT_PASS (pass_sink_code);
NEXT_PASS (pass_asan);
@@ -232,20 +231,21 @@ along with GCC; see the file COPYING3.
NEXT_PASS (pass_loop_prefetch);
NEXT_PASS (pass_iv_optimize);
NEXT_PASS (pass_lim);
NEXT_PASS (pass_tree_loop_done);
POP_INSERT_PASSES ()
NEXT_PASS (pass_lower_vector_ssa);
NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_strength_reduction);
NEXT_PASS (pass_dominator);
+ NEXT_PASS (pass_strlen);
NEXT_PASS (pass_vrp);
/* The only const/copy propagation opportunities left after
DOM and VRP should be due to degenerate PHI nodes. So rather than
run the full propagators, run a specialized pass which
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
NEXT_PASS (pass_cd_dce);
NEXT_PASS (pass_tracer);
NEXT_PASS (pass_dse);
Index: gcc/testsuite/g++.dg/tree-ssa/calloc.C
===================================================================
--- gcc/testsuite/g++.dg/tree-ssa/calloc.C (revision 0)
+++ gcc/testsuite/g++.dg/tree-ssa/calloc.C (working copy)
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+typedef __SIZE_TYPE__ size_t;
+inline void* operator new(size_t, void* p) throw() { return p; }
+
+typedef void (*handler_t)(void);
+extern handler_t get_handle();
+
+inline void* operator new(size_t sz)
+{
+ void *p;
+
+ if (sz == 0)
+ sz = 1;
+
+ while ((p = __builtin_malloc (sz)) == 0)
+ {
+ handler_t handler = get_handle ();
+ if (! handler)
+ throw 42;
+ handler ();
+ }
+ return p;
+}
+
+struct vect {
+ int *start, *end;
+ vect(size_t n) {
+ start = end = 0;
+ if (n > (size_t)-1 / sizeof(int))
+ throw 33;
+ if (n != 0)
+ start = static_cast<int*> (operator new (n * sizeof(int)));
+ end = start + n;
+ int *p = start;
+ for (size_t l = n; l > 0; --l, ++p)
+ *p = 0;
+ }
+};
+
+void f (void *p, int n)
+{
+ new (p) vect(n);
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/strlenopt-9.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-9.c (revision 211886)
+++ gcc/testsuite/gcc.dg/strlenopt-9.c (working copy)
@@ -11,21 +11,21 @@ fn1 (int r)
optimized away. */
return strchr (p, '\0');
}
__attribute__((noinline, noclone)) size_t
fn2 (int r)
{
char *p, q[10];
strcpy (q, "abc");
p = r ? "a" : q;
- /* String length for p varies, therefore strlen below isn't
+ /* String length is constant for both alternatives, and strlen is
optimized away. */
return strlen (p);
}
__attribute__((noinline, noclone)) size_t
fn3 (char *p, int n)
{
int i;
p = strchr (p, '\0');
/* strcat here can be optimized into memcpy. */
@@ -91,19 +91,19 @@ main ()
|| memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcd", 33) != 0
|| memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdefg", 32) != 0)
abort ();
if (fn4 (b, 256) != 4
|| memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcdabcd", 37) != 0
|| memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdabcdefgefg", 39) != 0)
abort ();
return 0;
}
-/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */
+/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */
/* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */
/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
/* { dg-final { cleanup-tree-dump "strlen" } } */
/* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/calloc-1.c (working copy)
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+extern int a;
+extern int *b;
+int n;
+void* f(long *q)
+{
+ int *p = __builtin_malloc (n);
+ ++*q;
+ if (p)
+ {
+ ++*q;
+ a = 2;
+ __builtin_memset (p, 0, n);
+ *b = 3;
+ }
+ return p;
+}
+void* g(void)
+{
+ float *p = __builtin_calloc (8, 4);
+ return __builtin_memset (p, 0, 24); // not 32
+}
+
+/* { dg-final { scan-tree-dump-times "calloc" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/calloc-2.c (working copy)
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int n, nn;
+void* f()
+{
+ char *p = __builtin_calloc (n, 1);
+ p[42] = '\n';
+ __builtin_memset (p, 0, nn);
+ return p;
+}
+
+void* g(int m1, int m2)
+{
+ char *p = __builtin_malloc (m2);
+ while (--m1)
+ {
+ __builtin_memset (p, 0, m2);
+ p[n] = 'b';
+ }
+ return p;
+}
+
+/* { dg-final { scan-tree-dump-times "malloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "calloc" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "memset" 2 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/tree-ssa-strlen.c
===================================================================
--- gcc/tree-ssa-strlen.c (revision 211886)
+++ gcc/tree-ssa-strlen.c (working copy)
@@ -496,20 +496,23 @@ get_string_length (strinfo si)
case BUILT_IN_STPCPY_CHK:
gcc_assert (lhs != NULL_TREE);
loc = gimple_location (stmt);
si->endptr = lhs;
si->stmt = NULL;
lhs = fold_convert_loc (loc, size_type_node, lhs);
si->length = fold_convert_loc (loc, size_type_node, si->ptr);
si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
lhs, si->length);
break;
+ case BUILT_IN_MALLOC:
+ break;
+ /* BUILT_IN_CALLOC always has si->length set. */
default:
gcc_unreachable ();
break;
}
}
return si->length;
}
/* Invalidate string length information for strings whose length
@@ -521,20 +524,21 @@ maybe_invalidate (gimple stmt)
strinfo si;
unsigned int i;
bool nonempty = false;
for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
if (si != NULL)
{
if (!si->dont_invalidate)
{
ao_ref r;
+ /* Do not use si->length. */
ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
if (stmt_may_clobber_ref_p_1 (stmt, &r))
{
set_strinfo (i, NULL);
free_strinfo (si);
continue;
}
}
si->dont_invalidate = false;
nonempty = true;
@@ -1608,20 +1612,93 @@ handle_builtin_strcat (enum built_in_fun
{
laststmt.stmt = stmt;
laststmt.len = srclen;
laststmt.stridx = dsi->idx;
}
}
else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
fprintf (dump_file, "not possible.\n");
}
+/* Handle a call to malloc or calloc. */
+
+static void
+handle_builtin_malloc (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+{
+ gimple stmt = gsi_stmt (*gsi);
+ tree lhs = gimple_call_lhs (stmt);
+ gcc_assert (get_stridx (lhs) == 0);
+ int idx = new_stridx (lhs);
+ tree length = NULL_TREE;
+ if (bcode == BUILT_IN_CALLOC)
+ length = build_int_cst (size_type_node, 0);
+ strinfo si = new_strinfo (lhs, idx, length);
+ if (bcode == BUILT_IN_CALLOC)
+ si->endptr = lhs;
+ set_strinfo (idx, si);
+ si->writable = true;
+ si->stmt = stmt;
+ si->dont_invalidate = true;
+}
+
+/* Handle a call to memset.
+ After a call to calloc, memset(,0,) is unnecessary.
+ memset(malloc(n),0,n) is calloc(n,1). */
+
+static bool
+handle_builtin_memset (gimple_stmt_iterator *gsi)
+{
+ gimple stmt2 = gsi_stmt (*gsi);
+ if (!integer_zerop (gimple_call_arg (stmt2, 1)))
+ return true;
+ tree ptr = gimple_call_arg (stmt2, 0);
+ int idx1 = get_stridx (ptr);
+ if (idx1 <= 0)
+ return true;
+ strinfo si1 = get_strinfo (idx1);
+ if (!si1)
+ return true;
+ gimple stmt1 = si1->stmt;
+ if (!stmt1 || !is_gimple_call (stmt1))
+ return true;
+ tree callee1 = gimple_call_fndecl (stmt1);
+ if (!gimple_call_builtin_p (stmt1, BUILT_IN_NORMAL))
+ return true;
+ enum built_in_function code1 = DECL_FUNCTION_CODE (callee1);
+ tree size = gimple_call_arg (stmt2, 2);
+ 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,
+ size, build_one_cst (size_type_node));
+ }
+ else
+ return true;
+ tree lhs = gimple_call_lhs (stmt2);
+ unlink_stmt_vdef (stmt2);
+ if (lhs)
+ {
+ gimple assign = gimple_build_assign (lhs, ptr);
+ gsi_replace (gsi, assign, false);
+ }
+ else
+ {
+ gsi_remove (gsi, true);
+ release_defs (stmt2);
+ }
+
+ return false;
+}
+
/* Handle a POINTER_PLUS_EXPR statement.
For p = "abcd" + 2; compute associated length, or if
p = q + off is pointing to a '\0' character of a string, call
zero_length_string on it. */
static void
handle_pointer_plus (gimple_stmt_iterator *gsi)
{
gimple stmt = gsi_stmt (*gsi);
tree lhs = gimple_assign_lhs (stmt), off;
@@ -1845,20 +1922,28 @@ strlen_optimize_stmt (gimple_stmt_iterat
case BUILT_IN_MEMCPY:
case BUILT_IN_MEMCPY_CHK:
case BUILT_IN_MEMPCPY:
case BUILT_IN_MEMPCPY_CHK:
handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
break;
case BUILT_IN_STRCAT:
case BUILT_IN_STRCAT_CHK:
handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
break;
+ case BUILT_IN_MALLOC:
+ case BUILT_IN_CALLOC:
+ handle_builtin_malloc (DECL_FUNCTION_CODE (callee), gsi);
+ break;
+ case BUILT_IN_MEMSET:
+ if (!handle_builtin_memset (gsi))
+ return false;
+ break;
default:
break;
}
}
else if (is_gimple_assign (stmt))
{
tree lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
{
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 15:52 ` Marc Glisse
@ 2014-06-23 16:11 ` Richard Biener
2014-06-23 16:19 ` Marc Glisse
0 siblings, 1 reply; 26+ messages in thread
From: Richard Biener @ 2014-06-23 16:11 UTC (permalink / raw)
To: Marc Glisse, Jakub Jelinek; +Cc: GCC Patches
On June 23, 2014 5:51:30 PM CEST, Marc Glisse <marc.glisse@inria.fr> wrote:
>On Mon, 23 Jun 2014, Jakub Jelinek wrote:
>
>> Ok for trunk, sorry for the delay.
>
>Thanks. Richard has moved the passes a bit since then, but I still have
>
>exactly one spot where the testsuite is ok :-) I need strlen to be
>after
>dom (for calloc.C) and before vrp (for several strlenopt-*.c). I'll
>commit
>it tomorrow if there aren't any comments on the pass placement.
But vrp does not run at -O1 - does strlenopt?
>2014-06-24 Marc Glisse <marc.glisse@inria.fr>
>
> PR tree-optimization/57742
>gcc/
> * tree-ssa-strlen.c (get_string_length): Ignore malloc.
> (handle_builtin_malloc, handle_builtin_memset): New functions.
> (strlen_optimize_stmt): Call them.
> * passes.def: Move strlen after loop+dom but before vrp.
>gcc/testsuite/
> * g++.dg/tree-ssa/calloc.C: New testcase.
> * gcc.dg/tree-ssa/calloc-1.c: Likewise.
> * gcc.dg/tree-ssa/calloc-2.c: Likewise.
> * gcc.dg/strlenopt-9.c: Adapt.
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 16:11 ` Richard Biener
@ 2014-06-23 16:19 ` Marc Glisse
2014-06-23 16:45 ` Richard Biener
0 siblings, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-06-23 16:19 UTC (permalink / raw)
To: Richard Biener; +Cc: Jakub Jelinek, GCC Patches
On Mon, 23 Jun 2014, Richard Biener wrote:
> On June 23, 2014 5:51:30 PM CEST, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Mon, 23 Jun 2014, Jakub Jelinek wrote:
>>
>>> Ok for trunk, sorry for the delay.
>>
>> Thanks. Richard has moved the passes a bit since then, but I still have
>>
>> exactly one spot where the testsuite is ok :-) I need strlen to be
>> after
>> dom (for calloc.C) and before vrp (for several strlenopt-*.c). I'll
>> commit
>> it tomorrow if there aren't any comments on the pass placement.
>
> But vrp does not run at -O1 - does strlenopt?
{ OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_vrp, NULL, 1 },
So that's just a missed optimization at -Os, I guess.
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 16:19 ` Marc Glisse
@ 2014-06-23 16:45 ` Richard Biener
0 siblings, 0 replies; 26+ messages in thread
From: Richard Biener @ 2014-06-23 16:45 UTC (permalink / raw)
To: Marc Glisse; +Cc: Jakub Jelinek, GCC Patches
On Mon, Jun 23, 2014 at 6:19 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 23 Jun 2014, Richard Biener wrote:
>
>> On June 23, 2014 5:51:30 PM CEST, Marc Glisse <marc.glisse@inria.fr>
>> wrote:
>>>
>>> On Mon, 23 Jun 2014, Jakub Jelinek wrote:
>>>
>>>> Ok for trunk, sorry for the delay.
>>>
>>>
>>> Thanks. Richard has moved the passes a bit since then, but I still have
>>>
>>> exactly one spot where the testsuite is ok :-) I need strlen to be
>>> after
>>> dom (for calloc.C) and before vrp (for several strlenopt-*.c). I'll
>>> commit
>>> it tomorrow if there aren't any comments on the pass placement.
>>
>>
>> But vrp does not run at -O1 - does strlenopt?
>
>
> { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 },
> { OPT_LEVELS_2_PLUS, OPT_ftree_vrp, NULL, 1 },
>
> So that's just a missed optimization at -Os, I guess.
Ok, that's fine (not sure why we restrict all of strilenopt instead of
just those
transforms that are harmful for -Os).
Richard.
> --
> Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-02-28 22:48 calloc = malloc + memset Marc Glisse
2014-03-01 12:26 ` Paolo Carlini
2014-03-03 9:50 ` Richard Biener
@ 2014-06-23 18:20 ` Andi Kleen
2014-06-23 18:51 ` Andrew Pinski
2014-06-23 19:00 ` Marc Glisse
2014-07-15 12:38 ` Bernd Schmidt
3 siblings, 2 replies; 26+ messages in thread
From: Andi Kleen @ 2014-06-23 18:20 UTC (permalink / raw)
To: Marc Glisse; +Cc: gcc-patches
Marc Glisse <marc.glisse@inria.fr> writes:
> Hello,
>
> this is a stage 1 patch, and I'll ping it then, but if you have
> comments now...
FWIW i believe the transformation will break a large variety of micro benchmarks.
calloc internally knows that memory fresh from the OS is zeroed.
But the memory may not be faulted in yet.
memset always faults in the memory.
So if you have some test like
buf = malloc(...)
memset(buf, ...)
start = get_time();
... do something with buf
end = get_time()
Now the times will be completely off because the measured times includes
the page faults.
-Andi
--
ak@linux.intel.com -- Speaking for myself only
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 18:20 ` Andi Kleen
@ 2014-06-23 18:51 ` Andrew Pinski
2014-06-23 19:00 ` Marc Glisse
1 sibling, 0 replies; 26+ messages in thread
From: Andrew Pinski @ 2014-06-23 18:51 UTC (permalink / raw)
To: Andi Kleen; +Cc: Marc Glisse, GCC Patches
On Mon, Jun 23, 2014 at 11:17 AM, Andi Kleen <andi@firstfloor.org> wrote:
> Marc Glisse <marc.glisse@inria.fr> writes:
>
>> Hello,
>>
>> this is a stage 1 patch, and I'll ping it then, but if you have
>> comments now...
>
> FWIW i believe the transformation will break a large variety of micro benchmarks.
>
> calloc internally knows that memory fresh from the OS is zeroed.
> But the memory may not be faulted in yet.
>
> memset always faults in the memory.
>
> So if you have some test like
>
> buf = malloc(...)
> memset(buf, ...)
> start = get_time();
> ... do something with buf
> end = get_time()
>
> Now the times will be completely off because the measured times includes
> the page faults.
Easy way for these benchmarks to get around this.
volatile char *vbuf = (char*)buf;
for(i=0;i<bufsize;i++)
*vbuf = 0;
before get_time ();
Now there is no way for the compiler to optimize away the inlined
memset and will always be 100% correct in the future.
Also micro-benchmarking is going to have issues like this too with
future optimizations.
Thanks,
Andrew
>
> -Andi
>
> --
> ak@linux.intel.com -- Speaking for myself only
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 18:20 ` Andi Kleen
2014-06-23 18:51 ` Andrew Pinski
@ 2014-06-23 19:00 ` Marc Glisse
2014-06-23 19:37 ` Andi Kleen
1 sibling, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-06-23 19:00 UTC (permalink / raw)
To: Andi Kleen; +Cc: gcc-patches
On Mon, 23 Jun 2014, Andi Kleen wrote:
> FWIW i believe the transformation will break a large variety of micro benchmarks.
>
> calloc internally knows that memory fresh from the OS is zeroed.
> But the memory may not be faulted in yet.
>
> memset always faults in the memory.
>
> So if you have some test like
>
> buf = malloc(...)
> memset(buf, ...)
> start = get_time();
> ... do something with buf
> end = get_time()
>
> Now the times will be completely off because the measured times includes
> the page faults.
Good point. I guess working around compiler optimizations is part of the
game for micro benchmarks, and their authors would be disappointed if the
compiler didn't mess it up regularly in new and entertaining ways ;-)
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 19:00 ` Marc Glisse
@ 2014-06-23 19:37 ` Andi Kleen
2014-06-23 20:14 ` Marc Glisse
0 siblings, 1 reply; 26+ messages in thread
From: Andi Kleen @ 2014-06-23 19:37 UTC (permalink / raw)
To: Marc Glisse; +Cc: Andi Kleen, gcc-patches
On Mon, Jun 23, 2014 at 09:00:02PM +0200, Marc Glisse wrote:
> On Mon, 23 Jun 2014, Andi Kleen wrote:
>
> >FWIW i believe the transformation will break a large variety of micro benchmarks.
> >
> >calloc internally knows that memory fresh from the OS is zeroed.
> >But the memory may not be faulted in yet.
> >
> >memset always faults in the memory.
> >
> >So if you have some test like
> >
> > buf = malloc(...)
> > memset(buf, ...)
> > start = get_time();
> > ... do something with buf
> > end = get_time()
> >
> >Now the times will be completely off because the measured times includes
> >the page faults.
>
> Good point. I guess working around compiler optimizations is part of
> the game for micro benchmarks, and their authors would be
> disappointed if the compiler didn't mess it up regularly in new and
> entertaining ways ;-)
I would prefer to not do it. I'm not sure it has a lot of benefit.
If you want to keep it please make sure there is an easy way to turn
it off.
-Andi
--
ak@linux.intel.com -- Speaking for myself only.
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 19:37 ` Andi Kleen
@ 2014-06-23 20:14 ` Marc Glisse
2014-06-23 20:21 ` Andi Kleen
0 siblings, 1 reply; 26+ messages in thread
From: Marc Glisse @ 2014-06-23 20:14 UTC (permalink / raw)
To: Andi Kleen; +Cc: gcc-patches
On Mon, 23 Jun 2014, Andi Kleen wrote:
> I would prefer to not do it.
For the sake of micro benchmarks?
> I'm not sure it has a lot of benefit.
It has a non-zero benefit.
> If you want to keep it please make sure there is an easy way to turn
> it off.
Any of these flags works:
-fdisable-tree-strlen
-fno-builtin-malloc
-fno-builtin-memset (assuming you wrote 'memset' explicitly in your code)
-fno-builtin
-ffreestanding
-O1
-Os
In the code, you can hide that the pointer passed to memset is the one
returned by malloc by storing it in a volatile variable, or any other
trick to hide from the compiler that we are doing memset(malloc(n),0,n).
--
Marc Glisse
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 20:14 ` Marc Glisse
@ 2014-06-23 20:21 ` Andi Kleen
2014-06-23 20:25 ` Andrew Pinski
0 siblings, 1 reply; 26+ messages in thread
From: Andi Kleen @ 2014-06-23 20:21 UTC (permalink / raw)
To: Marc Glisse; +Cc: Andi Kleen, gcc-patches
On Mon, Jun 23, 2014 at 10:14:25PM +0200, Marc Glisse wrote:
> On Mon, 23 Jun 2014, Andi Kleen wrote:
>
> >I would prefer to not do it.
>
> For the sake of micro benchmarks?
Yes benchmarks are important.
-Andi
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-06-23 20:21 ` Andi Kleen
@ 2014-06-23 20:25 ` Andrew Pinski
0 siblings, 0 replies; 26+ messages in thread
From: Andrew Pinski @ 2014-06-23 20:25 UTC (permalink / raw)
To: Andi Kleen; +Cc: Marc Glisse, GCC Patches
On Mon, Jun 23, 2014 at 1:21 PM, Andi Kleen <andi@firstfloor.org> wrote:
> On Mon, Jun 23, 2014 at 10:14:25PM +0200, Marc Glisse wrote:
>> On Mon, 23 Jun 2014, Andi Kleen wrote:
>>
>> >I would prefer to not do it.
>>
>> For the sake of micro benchmarks?
>
> Yes benchmarks are important.
But micro-benchmarks are not important. In fact this patch could
improve some benchmarks as you no longer thrash your cache.
So benchmarks are important but micro-benchmarks are not.
Thanks,
Andrew
>
> -Andi
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-02-28 22:48 calloc = malloc + memset Marc Glisse
` (2 preceding siblings ...)
2014-06-23 18:20 ` Andi Kleen
@ 2014-07-15 12:38 ` Bernd Schmidt
2014-07-15 13:15 ` Richard Biener
3 siblings, 1 reply; 26+ messages in thread
From: Bernd Schmidt @ 2014-07-15 12:38 UTC (permalink / raw)
To: Marc Glisse, gcc-patches
On 02/28/2014 11:48 PM, Marc Glisse wrote:
> /* Optimize
> + ptr = malloc (n);
> + memset (ptr, 0, n);
> + into
> + ptr = calloc (n);
> + gsi_p is known to point to a call to __builtin_memset. */
Is there anything in here to prevent us making an infinite loop if the
above pattern occurs in a function called "calloc"?
Bernd
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: calloc = malloc + memset
2014-07-15 12:38 ` Bernd Schmidt
@ 2014-07-15 13:15 ` Richard Biener
0 siblings, 0 replies; 26+ messages in thread
From: Richard Biener @ 2014-07-15 13:15 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Marc Glisse, GCC Patches
On Tue, Jul 15, 2014 at 2:33 PM, Bernd Schmidt <bernds_cb1@t-online.de> wrote:
> On 02/28/2014 11:48 PM, Marc Glisse wrote:
>>
>> /* Optimize
>> + ptr = malloc (n);
>> + memset (ptr, 0, n);
>> + into
>> + ptr = calloc (n);
>> + gsi_p is known to point to a call to __builtin_memset. */
>
>
> Is there anything in here to prevent us making an infinite loop if the above
> pattern occurs in a function called "calloc"?
Nothing. See how I ended up doing
2014-05-06 Richard Biener <rguenther@suse.de>
* c-opts.c (c_common_post_options): For -freestanding,
-fno-hosted and -fno-builtin disable pattern recognition
if not enabled explicitely.
to avoid sth like this for memset/memcpy/memmove recognition.
Richard.
>
> Bernd
>
^ permalink raw reply [flat|nested] 26+ messages in thread
end of thread, other threads:[~2014-07-15 12:38 UTC | newest]
Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-02-28 22:48 calloc = malloc + memset Marc Glisse
2014-03-01 12:26 ` Paolo Carlini
2014-03-01 14:51 ` Marc Glisse
2014-03-03 9:50 ` Richard Biener
2014-03-03 13:45 ` Marc Glisse
2014-03-23 19:47 ` Marc Glisse
2014-04-15 19:06 ` Marc Glisse
2014-04-18 11:31 ` Jakub Jelinek
2014-04-18 18:34 ` Marc Glisse
2014-04-23 14:05 ` Richard Biener
2014-05-17 14:19 ` Marc Glisse
2014-06-03 14:00 ` Marc Glisse
2014-06-23 7:32 ` Jakub Jelinek
2014-06-23 15:52 ` Marc Glisse
2014-06-23 16:11 ` Richard Biener
2014-06-23 16:19 ` Marc Glisse
2014-06-23 16:45 ` Richard Biener
2014-06-23 18:20 ` Andi Kleen
2014-06-23 18:51 ` Andrew Pinski
2014-06-23 19:00 ` Marc Glisse
2014-06-23 19:37 ` Andi Kleen
2014-06-23 20:14 ` Marc Glisse
2014-06-23 20:21 ` Andi Kleen
2014-06-23 20:25 ` Andrew Pinski
2014-07-15 12:38 ` Bernd Schmidt
2014-07-15 13:15 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).