| Message ID | CAAgBjMnTFvbWBih_527jGrzVOk=ieMeosvhqNeDef-HTBJ7nQQ@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: > Hi, > The attached patch adds special-casing for strcpy/strncpy to dse pass. > Bootstrapped+tested on x86_64-unknown-linux-gnu. > OK for GCC 8 ? What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you don't know the length they store (at least not in general), you don't know the value, all you know is that they are for the first argument plain store without remembering the pointer or anything based on it anywhere except in the return value. I believe stpcpy, stpncpy, strcat, strncat at least have the same behavior. On the other side, without knowing the length of the store, you can't treat it as killing something (ok, some calls like strcpy or stpcpy store at least the first byte). > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c > new file mode 100644 > index 0000000..1a832ca > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c > @@ -0,0 +1,12 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-dse-details" } */ > + > +void f(const char *s) > +{ > + unsigned n = __builtin_strlen (s) + 1; > + char *p = __builtin_malloc (n); > + __builtin_strcpy (p, s); > + __builtin_free (p); > +} > + > +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */ > diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c > index 53feaf3..6d3c3c3 100644 > --- a/gcc/tree-ssa-dse.c > +++ b/gcc/tree-ssa-dse.c > @@ -97,6 +97,8 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) > case BUILT_IN_MEMCPY: > case BUILT_IN_MEMMOVE: > case BUILT_IN_MEMSET: > + case BUILT_IN_STRNCPY: > + case BUILT_IN_STRCPY: > { > tree size = NULL_TREE; > if (gimple_call_num_args (stmt) == 3) > @@ -395,6 +397,8 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) > { > case BUILT_IN_MEMCPY: > case BUILT_IN_MEMMOVE: > + case BUILT_IN_STRNCPY: > + case BUILT_IN_STRCPY: > { > int head_trim, tail_trim; > compute_trims (ref, live, &head_trim, &tail_trim, stmt); > @@ -713,6 +717,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) > case BUILT_IN_MEMCPY: > case BUILT_IN_MEMMOVE: > case BUILT_IN_MEMSET: > + case BUILT_IN_STRNCPY: > { > /* Occasionally calls with an explicit length of zero > show up in the IL. It's pointless to do analysis > @@ -723,7 +728,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) > delete_dead_call (gsi); > return; > } > - > + } > + /* fallthru */ > + case BUILT_IN_STRCPY: > + { > gimple *use_stmt; > enum dse_store_status store_status; > m_byte_tracking_enabled Jakub
On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote: > On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: >> Hi, >> The attached patch adds special-casing for strcpy/strncpy to dse pass. >> Bootstrapped+tested on x86_64-unknown-linux-gnu. >> OK for GCC 8 ? > > What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you don't > know the length they store (at least not in general), you don't know the > value, all you know is that they are for the first argument plain store > without remembering the pointer or anything based on it anywhere except in > the return value. > I believe stpcpy, stpncpy, strcat, strncat at least have the same behavior. > On the other side, without knowing the length of the store, you can't treat > it as killing something (ok, some calls like strcpy or stpcpy store at least > the first byte). Well, I assumed a store to dest by strcpy (and friends), which gets immediately freed would count as a dead store since free would kill the whole memory block pointed to by dest ? For the test-case: void f (unsigned n, char *s2) { char *p = __builtin_malloc (n); __builtin_strcpy (p, s2); __builtin_free (p); } With patch, similar to memcpy, in dse_classify_store when temp equals __builtin_free (p), stmt_kills_ref_p (temp, ref) returns true (the condition for case BUILT_IN_FREE) which causes the loop to break and dse_classify_store returns DSE_STORE_DEAD. Thanks, Prathamesh > >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c >> new file mode 100644 >> index 0000000..1a832ca >> --- /dev/null >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c >> @@ -0,0 +1,12 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-dse-details" } */ >> + >> +void f(const char *s) >> +{ >> + unsigned n = __builtin_strlen (s) + 1; >> + char *p = __builtin_malloc (n); >> + __builtin_strcpy (p, s); >> + __builtin_free (p); >> +} >> + >> +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */ >> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c >> index 53feaf3..6d3c3c3 100644 >> --- a/gcc/tree-ssa-dse.c >> +++ b/gcc/tree-ssa-dse.c >> @@ -97,6 +97,8 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) >> case BUILT_IN_MEMCPY: >> case BUILT_IN_MEMMOVE: >> case BUILT_IN_MEMSET: >> + case BUILT_IN_STRNCPY: >> + case BUILT_IN_STRCPY: >> { >> tree size = NULL_TREE; >> if (gimple_call_num_args (stmt) == 3) >> @@ -395,6 +397,8 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) >> { >> case BUILT_IN_MEMCPY: >> case BUILT_IN_MEMMOVE: >> + case BUILT_IN_STRNCPY: >> + case BUILT_IN_STRCPY: >> { >> int head_trim, tail_trim; >> compute_trims (ref, live, &head_trim, &tail_trim, stmt); >> @@ -713,6 +717,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) >> case BUILT_IN_MEMCPY: >> case BUILT_IN_MEMMOVE: >> case BUILT_IN_MEMSET: >> + case BUILT_IN_STRNCPY: >> { >> /* Occasionally calls with an explicit length of zero >> show up in the IL. It's pointless to do analysis >> @@ -723,7 +728,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) >> delete_dead_call (gsi); >> return; >> } >> - >> + } >> + /* fallthru */ >> + case BUILT_IN_STRCPY: >> + { >> gimple *use_stmt; >> enum dse_store_status store_status; >> m_byte_tracking_enabled > > > Jakub
On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: > On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote: >> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: >>> Hi, >>> The attached patch adds special-casing for strcpy/strncpy to dse pass. >>> Bootstrapped+tested on x86_64-unknown-linux-gnu. >>> OK for GCC 8 ? >> >> What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you don't >> know the length they store (at least not in general), you don't know the >> value, all you know is that they are for the first argument plain store >> without remembering the pointer or anything based on it anywhere except in >> the return value. >> I believe stpcpy, stpncpy, strcat, strncat at least have the same behavior. >> On the other side, without knowing the length of the store, you can't treat >> it as killing something (ok, some calls like strcpy or stpcpy store at least >> the first byte). > Well, I assumed a store to dest by strcpy (and friends), which gets > immediately freed would count > as a dead store since free would kill the whole memory block pointed > to by dest ? Yes. But does it happen often in practice? I wouldn't mind exploring this for gcc-8, but I'd like to see real-world code where this happens. jeff
On Tue, 28 Feb 2017, Jeff Law wrote: > On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: > > On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote: > > > On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: > > > > Hi, > > > > The attached patch adds special-casing for strcpy/strncpy to dse pass. > > > > Bootstrapped+tested on x86_64-unknown-linux-gnu. > > > > OK for GCC 8 ? > > > > > > What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you > > > don't > > > know the length they store (at least not in general), you don't know the > > > value, all you know is that they are for the first argument plain store > > > without remembering the pointer or anything based on it anywhere except in > > > the return value. > > > I believe stpcpy, stpncpy, strcat, strncat at least have the same > > > behavior. > > > On the other side, without knowing the length of the store, you can't > > > treat > > > it as killing something (ok, some calls like strcpy or stpcpy store at > > > least > > > the first byte). > > Well, I assumed a store to dest by strcpy (and friends), which gets > > immediately freed would count > > as a dead store since free would kill the whole memory block pointed > > to by dest ? > Yes. But does it happen often in practice? I wouldn't mind exploring this > for gcc-8, but I'd like to see real-world code where this happens. Actually I don't mind for "real-world code" - the important part is that I believe it's reasonable to assume it can happen from some C++ abstraction and optimization. Richard.
On 1 March 2017 at 13:24, Richard Biener <rguenther@suse.de> wrote: > On Tue, 28 Feb 2017, Jeff Law wrote: > >> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: >> > On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote: >> > > On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: >> > > > Hi, >> > > > The attached patch adds special-casing for strcpy/strncpy to dse pass. >> > > > Bootstrapped+tested on x86_64-unknown-linux-gnu. >> > > > OK for GCC 8 ? >> > > >> > > What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you >> > > don't >> > > know the length they store (at least not in general), you don't know the >> > > value, all you know is that they are for the first argument plain store >> > > without remembering the pointer or anything based on it anywhere except in >> > > the return value. >> > > I believe stpcpy, stpncpy, strcat, strncat at least have the same >> > > behavior. >> > > On the other side, without knowing the length of the store, you can't >> > > treat >> > > it as killing something (ok, some calls like strcpy or stpcpy store at >> > > least >> > > the first byte). >> > Well, I assumed a store to dest by strcpy (and friends), which gets >> > immediately freed would count >> > as a dead store since free would kill the whole memory block pointed >> > to by dest ? >> Yes. But does it happen often in practice? I wouldn't mind exploring this >> for gcc-8, but I'd like to see real-world code where this happens. > > Actually I don't mind for "real-world code" - the important part is > that I believe it's reasonable to assume it can happen from some C++ > abstraction and optimization. Hi, I have updated the patch to include stp[n]cpy and str[n]cat. In initialize_ao_ref_for_dse for strncat, I suppose for strncat we need to treat size as NULL_TREE instead of setting it 2nd arg since we cannot know size (in general) after strncat ? Patch passes bootstrap+test on x86_64-unknown-linux-gnu. Cross-tested on arm*-*-*, aarch64*-*-*. Thanks, Prathamesh > > Richard. 2017-04-24 Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org> * tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY, BUILT_IN_STPCPY, BUILT_IN_STRNCAT, BUILT_IN_STRCAT. (maybe_trim_memstar_call): Likewise. (dse_dom_walker::dse_optimize_stmt): Likewise. testsuite/ * gcc.dg/tree-ssa/pr79715.c: New test.diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c new file mode 100644 index 0000000..2cd4c99 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c @@ -0,0 +1,42 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dse-details" } */ + +void f1(const char *s) +{ + unsigned n = __builtin_strlen (s) + 1; + char *p = __builtin_malloc (n); + __builtin_strcpy (p, s); + __builtin_free (p); +} + +void f2(const char *s, unsigned n) +{ + char *p = __builtin_malloc (n); + __builtin_strncpy (p, s, n); + __builtin_free (p); +} + +void f3(const char *s, unsigned n) +{ + char *p = __builtin_malloc (n); + __builtin_stpncpy (p, s, n); + __builtin_free (p); +} + +void f4(char *s, char *t) +{ + __builtin_strcat (s, t); + __builtin_free (s); +} + +void f5(char *s, char *t, unsigned n) +{ + __builtin_strncat (s, t, n); + __builtin_free (s); +} + +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */ +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strncpy" "dse1" } } */ +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_stpncpy" "dse1" } } */ +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcat" "dse1" } } */ +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strncat" "dse1" } } */ diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 90230ab..752b2fa 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) /* It's advantageous to handle certain mem* functions. */ if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) { + tree size = NULL_TREE; switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) { case BUILT_IN_MEMCPY: case BUILT_IN_MEMMOVE: case BUILT_IN_MEMSET: + case BUILT_IN_STRNCPY: + case BUILT_IN_STRCPY: + case BUILT_IN_STPNCPY: + case BUILT_IN_STPCPY: { - tree size = NULL_TREE; if (gimple_call_num_args (stmt) == 3) size = gimple_call_arg (stmt, 2); + } + /* fallthrough. */ + case BUILT_IN_STRCAT: + case BUILT_IN_STRNCAT: + { tree ptr = gimple_call_arg (stmt, 0); ao_ref_init_from_ptr_and_size (write, ptr, size); return true; @@ -395,6 +404,12 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) { case BUILT_IN_MEMCPY: case BUILT_IN_MEMMOVE: + case BUILT_IN_STRNCPY: + case BUILT_IN_STRCPY: + case BUILT_IN_STPNCPY: + case BUILT_IN_STPCPY: + case BUILT_IN_STRNCAT: + case BUILT_IN_STRCAT: { int head_trim, tail_trim; compute_trims (ref, live, &head_trim, &tail_trim, stmt); @@ -714,6 +729,9 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) case BUILT_IN_MEMCPY: case BUILT_IN_MEMMOVE: case BUILT_IN_MEMSET: + case BUILT_IN_STRNCPY: + case BUILT_IN_STPNCPY: + case BUILT_IN_STRNCAT: { /* Occasionally calls with an explicit length of zero show up in the IL. It's pointless to do analysis @@ -724,7 +742,12 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) delete_dead_call (gsi); return; } - + } + /* fallthru */ + case BUILT_IN_STRCPY: + case BUILT_IN_STPCPY: + case BUILT_IN_STRCAT: + { gimple *use_stmt; enum dse_store_status store_status; m_byte_tracking_enabled
On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote: > On 1 March 2017 at 13:24, Richard Biener<rguenther@suse.de> wrote: >> On Tue, 28 Feb 2017, Jeff Law wrote: >> >>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: >>>> On 28 February 2017 at 15:40, Jakub Jelinek<jakub@redhat.com> wrote: >>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: >>>>>> Hi, >>>>>> The attached patch adds special-casing for strcpy/strncpy to dse pass. >>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu. >>>>>> OK for GCC 8 ? >>>>> What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you >>>>> don't >>>>> know the length they store (at least not in general), you don't know the >>>>> value, all you know is that they are for the first argument plain store >>>>> without remembering the pointer or anything based on it anywhere except in >>>>> the return value. >>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same >>>>> behavior. >>>>> On the other side, without knowing the length of the store, you can't >>>>> treat >>>>> it as killing something (ok, some calls like strcpy or stpcpy store at >>>>> least >>>>> the first byte). >>>> Well, I assumed a store to dest by strcpy (and friends), which gets >>>> immediately freed would count >>>> as a dead store since free would kill the whole memory block pointed >>>> to by dest ? >>> Yes. But does it happen often in practice? I wouldn't mind exploring this >>> for gcc-8, but I'd like to see real-world code where this happens. >> Actually I don't mind for "real-world code" - the important part is >> that I believe it's reasonable to assume it can happen from some C++ >> abstraction and optimization. > Hi, > I have updated the patch to include stp[n]cpy and str[n]cat. > In initialize_ao_ref_for_dse for strncat, I suppose for strncat we > need to treat size as NULL_TREE > instead of setting it 2nd arg since we cannot know size (in general) > after strncat ? The problem isn't the size, strncat will write the appropriate number of characters, just like strncpy, stpncpy. The problem is that we don't know where the write will start. I'll touch further on this. > Patch passes bootstrap+test on x86_64-unknown-linux-gnu. > Cross-tested on arm*-*-*, aarch64*-*-*. > > Thanks, > Prathamesh >> Richard. > > pr79715-2.txt > > > 2017-04-24 Prathamesh Kulkarni<prathamesh.kulkarni@linaro.org> > > * tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for > BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY, BUILT_IN_STPCPY, > BUILT_IN_STRNCAT, BUILT_IN_STRCAT. > (maybe_trim_memstar_call): Likewise. > (dse_dom_walker::dse_optimize_stmt): Likewise. > > testsuite/ > * gcc.dg/tree-ssa/pr79715.c: New test. I'd still be surprised if this kind of think happens in the real world, even with layers of abstraction & templates. > diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c > index 90230ab..752b2fa 100644 > --- a/gcc/tree-ssa-dse.c > +++ b/gcc/tree-ssa-dse.c > @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) > /* It's advantageous to handle certain mem* functions. */ > if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) > { > + tree size = NULL_TREE; > switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) > { > case BUILT_IN_MEMCPY: > case BUILT_IN_MEMMOVE: > case BUILT_IN_MEMSET: > + case BUILT_IN_STRNCPY: > + case BUILT_IN_STRCPY: > + case BUILT_IN_STPNCPY: > + case BUILT_IN_STPCPY: > { > - tree size = NULL_TREE; > if (gimple_call_num_args (stmt) == 3) > size = gimple_call_arg (stmt, 2)This part seems reasonable. We know the size for strncpy, stpncpy which we extract from argument #3. For strcpy and stpcpy we'd have NULL for the size which is perfect. In all 4 cases the write starts at offset 0 in the destination string. . > + } > + /* fallthrough. */ > + case BUILT_IN_STRCAT: > + case BUILT_IN_STRNCAT: > + { > tree ptr = gimple_call_arg (stmt, 0); > ao_ref_init_from_ptr_and_size (write, ptr, size); For str[n]cat, I think this is going to result in WRITE not accurately reflecting what bytes are going to be written -- write.offset would have to account for the length of the destination string. I don't see a way in the ao_ref structure to indicate that the offset of a write is unknown. I'm really hesitant to allow handling of str[n]cat given the inaccuracy in how WRITE is initialized. To handle str[n]cat I think you have to either somehow indicate the offset is unknown or arrange to get the offset set correctly. I realize this isn't important for the case where the object dies immediately via free(), but it seems bad to allow this as-is. > return true; > @@ -395,6 +404,12 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) > { > case BUILT_IN_MEMCPY: > case BUILT_IN_MEMMOVE: > + case BUILT_IN_STRNCPY: > + case BUILT_IN_STRCPY: > + case BUILT_IN_STPNCPY: > + case BUILT_IN_STPCPY: > + case BUILT_IN_STRNCAT: > + case BUILT_IN_STRCAT: For strcpy, stpcpy and strcat I don't see how you can do trimming without knowing something about the source string. For str[n]cat we'd need a correctly initialized structure for the memory write, which we don't have because the offset does not account for the length of the destination string. The only trimming possibility I see is for strncpy and stpncpy where we could trim from the either end. I think you should remove the other cases. > { > int head_trim, tail_trim; > compute_trims (ref, live, &head_trim, &tail_trim, stmt); > @@ -714,6 +729,9 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) > case BUILT_IN_MEMCPY: > case BUILT_IN_MEMMOVE: > case BUILT_IN_MEMSET: > + case BUILT_IN_STRNCPY: > + case BUILT_IN_STPNCPY: > + case BUILT_IN_STRNCAT: I don't think you can support strncat here because we don't have a valid offset within the write descriptor. > { > /* Occasionally calls with an explicit length of zero > show up in the IL. It's pointless to do analysis > @@ -724,7 +742,12 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) > delete_dead_call (gsi); > return; > } > - > + } > + /* fallthru */ > + case BUILT_IN_STRCPY: > + case BUILT_IN_STPCPY: > + case BUILT_IN_STRCAT: Similarly here, I don't think you can support strcat because we don't have a valid write descriptor. Jeff
On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote: > On 1 March 2017 at 13:24, Richard Biener <rguenther@suse.de> wrote: >> On Tue, 28 Feb 2017, Jeff Law wrote: >> >>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: >>>> On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote: >>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote: >>>>>> Hi, >>>>>> The attached patch adds special-casing for strcpy/strncpy to dse pass. >>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu. >>>>>> OK for GCC 8 ? >>>>> >>>>> What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, you >>>>> don't >>>>> know the length they store (at least not in general), you don't know the >>>>> value, all you know is that they are for the first argument plain store >>>>> without remembering the pointer or anything based on it anywhere except in >>>>> the return value. >>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same >>>>> behavior. >>>>> On the other side, without knowing the length of the store, you can't >>>>> treat >>>>> it as killing something (ok, some calls like strcpy or stpcpy store at >>>>> least >>>>> the first byte). >>>> Well, I assumed a store to dest by strcpy (and friends), which gets >>>> immediately freed would count >>>> as a dead store since free would kill the whole memory block pointed >>>> to by dest ? >>> Yes. But does it happen often in practice? I wouldn't mind exploring this >>> for gcc-8, but I'd like to see real-world code where this happens. >> >> Actually I don't mind for "real-world code" - the important part is >> that I believe it's reasonable to assume it can happen from some C++ >> abstraction and optimization. > Hi, > I have updated the patch to include stp[n]cpy and str[n]cat. > In initialize_ao_ref_for_dse for strncat, I suppose for strncat we > need to treat size as NULL_TREE > instead of setting it 2nd arg since we cannot know size (in general) > after strncat ? > Patch passes bootstrap+test on x86_64-unknown-linux-gnu. > Cross-tested on arm*-*-*, aarch64*-*-*. I think I made a mistake when I opened PR79715: I used the wrong -fdump-tree- option and was looking at the wrong dump. It turns out that the test case there is optimized as I expected, except by a later pass, and has been since r233267. I resolved the bug as fixed before I realized that this patch (that I've been meaning to review) is for that bug, except that it enables the optimization to take place earlier. That sounds like a fine idea to me but now that I closed the bug I wonder if it should be done under a different bug. This is just a suggestion and if you don't want to take the time to raise a new bug for I don't mind if you reopen bug 79715. Sorry if I made things more complicated than they need to be. Martin
On April 28, 2017 8:14:56 PM GMT+02:00, Jeff Law <law@redhat.com> wrote: >On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote: >> On 1 March 2017 at 13:24, Richard Biener<rguenther@suse.de> wrote: >>> On Tue, 28 Feb 2017, Jeff Law wrote: >>> >>>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: >>>>> On 28 February 2017 at 15:40, Jakub Jelinek<jakub@redhat.com> >wrote: >>>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni >wrote: >>>>>>> Hi, >>>>>>> The attached patch adds special-casing for strcpy/strncpy to dse >pass. >>>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu. >>>>>>> OK for GCC 8 ? >>>>>> What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, >you >>>>>> don't >>>>>> know the length they store (at least not in general), you don't >know the >>>>>> value, all you know is that they are for the first argument plain >store >>>>>> without remembering the pointer or anything based on it anywhere >except in >>>>>> the return value. >>>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same >>>>>> behavior. >>>>>> On the other side, without knowing the length of the store, you >can't >>>>>> treat >>>>>> it as killing something (ok, some calls like strcpy or stpcpy >store at >>>>>> least >>>>>> the first byte). >>>>> Well, I assumed a store to dest by strcpy (and friends), which >gets >>>>> immediately freed would count >>>>> as a dead store since free would kill the whole memory block >pointed >>>>> to by dest ? >>>> Yes. But does it happen often in practice? I wouldn't mind >exploring this >>>> for gcc-8, but I'd like to see real-world code where this happens. >>> Actually I don't mind for "real-world code" - the important part is >>> that I believe it's reasonable to assume it can happen from some C++ >>> abstraction and optimization. >> Hi, >> I have updated the patch to include stp[n]cpy and str[n]cat. >> In initialize_ao_ref_for_dse for strncat, I suppose for strncat we >> need to treat size as NULL_TREE >> instead of setting it 2nd arg since we cannot know size (in general) >> after strncat ? >The problem isn't the size, strncat will write the appropriate number >of >characters, just like strncpy, stpncpy. The problem is that we don't >know where the write will start. I'll touch further on this. > > >> Patch passes bootstrap+test on x86_64-unknown-linux-gnu. >> Cross-tested on arm*-*-*, aarch64*-*-*. >> >> Thanks, >> Prathamesh >>> Richard. >> >> pr79715-2.txt >> >> >> 2017-04-24 Prathamesh Kulkarni<prathamesh.kulkarni@linaro.org> >> >> * tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for >> BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY, >BUILT_IN_STPCPY, >> BUILT_IN_STRNCAT, BUILT_IN_STRCAT. >> (maybe_trim_memstar_call): Likewise. >> (dse_dom_walker::dse_optimize_stmt): Likewise. >> >> testsuite/ >> * gcc.dg/tree-ssa/pr79715.c: New test. >I'd still be surprised if this kind of think happens in the real world, > >even with layers of abstraction & templates. > > > >> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c >> index 90230ab..752b2fa 100644 >> --- a/gcc/tree-ssa-dse.c >> +++ b/gcc/tree-ssa-dse.c >> @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref >*write) >> /* It's advantageous to handle certain mem* functions. */ >> if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) >> { >> + tree size = NULL_TREE; >> switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) >> { >> case BUILT_IN_MEMCPY: >> case BUILT_IN_MEMMOVE: >> case BUILT_IN_MEMSET: >> + case BUILT_IN_STRNCPY: >> + case BUILT_IN_STRCPY: >> + case BUILT_IN_STPNCPY: >> + case BUILT_IN_STPCPY: >> { >> - tree size = NULL_TREE; >> if (gimple_call_num_args (stmt) == 3) >> size = gimple_call_arg (stmt, 2)This part seems reasonable. We >know the size for strncpy, stpncpy which >we extract from argument #3. For strcpy and stpcpy we'd have NULL for >the size which is perfect. In all 4 cases the write starts at offset 0 > >in the destination string. >. > > > >> + } >> + /* fallthrough. */ >> + case BUILT_IN_STRCAT: >> + case BUILT_IN_STRNCAT: >> + { >> tree ptr = gimple_call_arg (stmt, 0); >> ao_ref_init_from_ptr_and_size (write, ptr, size); >For str[n]cat, I think this is going to result in WRITE not accurately >reflecting what bytes are going to be written -- write.offset would >have >to account for the length of the destination string. > >I don't see a way in the ao_ref structure to indicate that the offset >of >a write is unknown. You can't make offset entirely unknown but you can use, for strcat, offset zero, size and max_size -1. It matters that the access range is correct. This is similar to how we treat array accesses with variable index. > >I'm really hesitant to allow handling of str[n]cat given the inaccuracy > >in how WRITE is initialized. > >To handle str[n]cat I think you have to either somehow indicate the >offset is unknown or arrange to get the offset set correctly. > >I realize this isn't important for the case where the object dies >immediately via free(), but it seems bad to allow this as-is. > > >> return true; >> @@ -395,6 +404,12 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap >live, gimple *stmt) >> { >> case BUILT_IN_MEMCPY: >> case BUILT_IN_MEMMOVE: >> + case BUILT_IN_STRNCPY: >> + case BUILT_IN_STRCPY: >> + case BUILT_IN_STPNCPY: >> + case BUILT_IN_STPCPY: >> + case BUILT_IN_STRNCAT: >> + case BUILT_IN_STRCAT: >For strcpy, stpcpy and strcat I don't see how you can do trimming >without knowing something about the source string. > >For str[n]cat we'd need a correctly initialized structure for the >memory >write, which we don't have because the offset does not account for the >length of the destination string. > >The only trimming possibility I see is for strncpy and stpncpy where we > >could trim from the either end. I think you should remove the other >cases. > > >> { >> int head_trim, tail_trim; >> compute_trims (ref, live, &head_trim, &tail_trim, stmt); >> @@ -714,6 +729,9 @@ dse_dom_walker::dse_optimize_stmt >(gimple_stmt_iterator *gsi) >> case BUILT_IN_MEMCPY: >> case BUILT_IN_MEMMOVE: >> case BUILT_IN_MEMSET: >> + case BUILT_IN_STRNCPY: >> + case BUILT_IN_STPNCPY: >> + case BUILT_IN_STRNCAT: >I don't think you can support strncat here because we don't have a >valid >offset within the write descriptor. > >> { >> /* Occasionally calls with an explicit length of zero >> show up in the IL. It's pointless to do analysis >> @@ -724,7 +742,12 @@ dse_dom_walker::dse_optimize_stmt >(gimple_stmt_iterator *gsi) >> delete_dead_call (gsi); >> return; >> } >> - >> + } >> + /* fallthru */ >> + case BUILT_IN_STRCPY: >> + case BUILT_IN_STPCPY: >> + case BUILT_IN_STRCAT: >Similarly here, I don't think you can support strcat because we don't >have a valid write descriptor. > >Jeff
On 05/01/2017 12:17 PM, Richard Biener wrote: > On April 28, 2017 8:14:56 PM GMT+02:00, Jeff Law <law@redhat.com> wrote: >> On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote: >>> On 1 March 2017 at 13:24, Richard Biener<rguenther@suse.de> wrote: >>>> On Tue, 28 Feb 2017, Jeff Law wrote: >>>> >>>>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote: >>>>>> On 28 February 2017 at 15:40, Jakub Jelinek<jakub@redhat.com> >> wrote: >>>>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni >> wrote: >>>>>>>> Hi, >>>>>>>> The attached patch adds special-casing for strcpy/strncpy to dse >> pass. >>>>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu. >>>>>>>> OK for GCC 8 ? >>>>>>> What is special on strcpy/strncpy? Unlike memcpy/memmove/memset, >> you >>>>>>> don't >>>>>>> know the length they store (at least not in general), you don't >> know the >>>>>>> value, all you know is that they are for the first argument plain >> store >>>>>>> without remembering the pointer or anything based on it anywhere >> except in >>>>>>> the return value. >>>>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same >>>>>>> behavior. >>>>>>> On the other side, without knowing the length of the store, you >> can't >>>>>>> treat >>>>>>> it as killing something (ok, some calls like strcpy or stpcpy >> store at >>>>>>> least >>>>>>> the first byte). >>>>>> Well, I assumed a store to dest by strcpy (and friends), which >> gets >>>>>> immediately freed would count >>>>>> as a dead store since free would kill the whole memory block >> pointed >>>>>> to by dest ? >>>>> Yes. But does it happen often in practice? I wouldn't mind >> exploring this >>>>> for gcc-8, but I'd like to see real-world code where this happens. >>>> Actually I don't mind for "real-world code" - the important part is >>>> that I believe it's reasonable to assume it can happen from some C++ >>>> abstraction and optimization. >>> Hi, >>> I have updated the patch to include stp[n]cpy and str[n]cat. >>> In initialize_ao_ref_for_dse for strncat, I suppose for strncat we >>> need to treat size as NULL_TREE >>> instead of setting it 2nd arg since we cannot know size (in general) >>> after strncat ? >> The problem isn't the size, strncat will write the appropriate number >> of >> characters, just like strncpy, stpncpy. The problem is that we don't >> know where the write will start. I'll touch further on this. >> >> >>> Patch passes bootstrap+test on x86_64-unknown-linux-gnu. >>> Cross-tested on arm*-*-*, aarch64*-*-*. >>> >>> Thanks, >>> Prathamesh >>>> Richard. >>> >>> pr79715-2.txt >>> >>> >>> 2017-04-24 Prathamesh Kulkarni<prathamesh.kulkarni@linaro.org> >>> >>> * tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for >>> BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY, >> BUILT_IN_STPCPY, >>> BUILT_IN_STRNCAT, BUILT_IN_STRCAT. >>> (maybe_trim_memstar_call): Likewise. >>> (dse_dom_walker::dse_optimize_stmt): Likewise. >>> >>> testsuite/ >>> * gcc.dg/tree-ssa/pr79715.c: New test. >> I'd still be surprised if this kind of think happens in the real world, >> >> even with layers of abstraction & templates. >> >> >> >>> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c >>> index 90230ab..752b2fa 100644 >>> --- a/gcc/tree-ssa-dse.c >>> +++ b/gcc/tree-ssa-dse.c >>> @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref >> *write) >>> /* It's advantageous to handle certain mem* functions. */ >>> if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) >>> { >>> + tree size = NULL_TREE; >>> switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) >>> { >>> case BUILT_IN_MEMCPY: >>> case BUILT_IN_MEMMOVE: >>> case BUILT_IN_MEMSET: >>> + case BUILT_IN_STRNCPY: >>> + case BUILT_IN_STRCPY: >>> + case BUILT_IN_STPNCPY: >>> + case BUILT_IN_STPCPY: >>> { >>> - tree size = NULL_TREE; >>> if (gimple_call_num_args (stmt) == 3) >>> size = gimple_call_arg (stmt, 2)This part seems reasonable. We >> know the size for strncpy, stpncpy which >> we extract from argument #3. For strcpy and stpcpy we'd have NULL for >> the size which is perfect. In all 4 cases the write starts at offset 0 >> >> in the destination string. >> . >> >> >> >>> + } >>> + /* fallthrough. */ >>> + case BUILT_IN_STRCAT: >>> + case BUILT_IN_STRNCAT: >>> + { >>> tree ptr = gimple_call_arg (stmt, 0); >>> ao_ref_init_from_ptr_and_size (write, ptr, size); >> For str[n]cat, I think this is going to result in WRITE not accurately >> reflecting what bytes are going to be written -- write.offset would >> have >> to account for the length of the destination string. >> >> I don't see a way in the ao_ref structure to indicate that the offset >> of >> a write is unknown. > > You can't make offset entirely unknown but you can use, for strcat, offset zero, size and max_size -1. It matters that the access range is correct. This is similar to how we treat array accesses with variable index. I suspect with a size/maxsize of -1 other code in DSE would probably reject the ao_ref. Though that's probably easier to solve in a way that would allow removal of the dead strcat/strncat calls, but not muck up other things. jeff
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c new file mode 100644 index 0000000..1a832ca --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dse-details" } */ + +void f(const char *s) +{ + unsigned n = __builtin_strlen (s) + 1; + char *p = __builtin_malloc (n); + __builtin_strcpy (p, s); + __builtin_free (p); +} + +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */ diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 53feaf3..6d3c3c3 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -97,6 +97,8 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) case BUILT_IN_MEMCPY: case BUILT_IN_MEMMOVE: case BUILT_IN_MEMSET: + case BUILT_IN_STRNCPY: + case BUILT_IN_STRCPY: { tree size = NULL_TREE; if (gimple_call_num_args (stmt) == 3) @@ -395,6 +397,8 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) { case BUILT_IN_MEMCPY: case BUILT_IN_MEMMOVE: + case BUILT_IN_STRNCPY: + case BUILT_IN_STRCPY: { int head_trim, tail_trim; compute_trims (ref, live, &head_trim, &tail_trim, stmt); @@ -713,6 +717,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) case BUILT_IN_MEMCPY: case BUILT_IN_MEMMOVE: case BUILT_IN_MEMSET: + case BUILT_IN_STRNCPY: { /* Occasionally calls with an explicit length of zero show up in the IL. It's pointless to do analysis @@ -723,7 +728,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) delete_dead_call (gsi); return; } - + } + /* fallthru */ + case BUILT_IN_STRCPY: + { gimple *use_stmt; enum dse_store_status store_status; m_byte_tracking_enabled