[Tree-optimization/PR89772] fold memchr builtins for character not in constant nul-padded string

Message ID 40b287af-4c87-f8d2-daeb-774861f430f9@linux.alibaba.com
State New
Headers show
Series
  • [Tree-optimization/PR89772] fold memchr builtins for character not in constant nul-padded string
Related show

Commit Message

JunMa March 21, 2019, 4:51 a.m.
Hi
For now, gcc can not fold code like:

const char a[5] = "123"
__builtin_memchr (a, '7', sizeof a)

It tries to avoid folding out of string length although length of a is 5.
This is a bit conservative, it's safe to folding memchr/bcmp/memcmp
builtins when constant string stores in array with some trailing nuls.

This patch folds these cases by exposing additional length of
trailing nuls in c_getstr().
Bootstrapped/regtested on x86_64-linux, ok for trunk?

Regards
JunMa


gcc/ChangeLog

2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

     PR Tree-optimization/89772
     * fold-const.c (c_getstr): Add new parameter to get length of 
additional
     trailing nuls after constant string.
     * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in
     out-of-bound accesses checking.
     * fold-const-call.c (fold_const_call): Likewise.


gcc/testsuite/ChangeLog

2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

     PR Tree-optimization/89772
     * gcc.dg/builtin-memchr-4.c: New test.
---
 gcc/fold-const-call.c                   | 14 +++++++-------
 gcc/fold-const.c                        | 14 +++++++-------
 gcc/fold-const.h                        |  3 ++-
 gcc/gimple-fold.c                       |  5 +++--
 gcc/testsuite/gcc.dg/builtin-memchr-4.c | 30 ++++++++++++++++++++++++++++++
 5 files changed, 49 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/builtin-memchr-4.c

Comments

Bin.Cheng March 21, 2019, 5:06 a.m. | #1
On Thu, Mar 21, 2019 at 12:57 PM JunMa <JunMa@linux.alibaba.com> wrote:
>

> Hi

> For now, gcc can not fold code like:

>

> const char a[5] = "123"

> __builtin_memchr (a, '7', sizeof a)

>

> It tries to avoid folding out of string length although length of a is 5.

> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

> builtins when constant string stores in array with some trailing nuls.

>

> This patch folds these cases by exposing additional length of

> trailing nuls in c_getstr().

> Bootstrapped/regtested on x86_64-linux, ok for trunk?

I suppose that it's for GCC10?

Thanks,
bin
>

> Regards

> JunMa

>

>

> gcc/ChangeLog

>

> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>

>      PR Tree-optimization/89772

>      * fold-const.c (c_getstr): Add new parameter to get length of

> additional

>      trailing nuls after constant string.

>      * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>      out-of-bound accesses checking.

>      * fold-const-call.c (fold_const_call): Likewise.

>

>

> gcc/testsuite/ChangeLog

>

> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>

>      PR Tree-optimization/89772

>      * gcc.dg/builtin-memchr-4.c: New test.
JunMa March 21, 2019, 5:20 a.m. | #2
在 2019/3/21 下午1:06, Bin.Cheng 写道:
> On Thu, Mar 21, 2019 at 12:57 PM JunMa <JunMa@linux.alibaba.com> wrote:

>> Hi

>> For now, gcc can not fold code like:

>>

>> const char a[5] = "123"

>> __builtin_memchr (a, '7', sizeof a)

>>

>> It tries to avoid folding out of string length although length of a is 5.

>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>> builtins when constant string stores in array with some trailing nuls.

>>

>> This patch folds these cases by exposing additional length of

>> trailing nuls in c_getstr().

>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

> I suppose that it's for GCC10?

>

> Thanks,

> bin

Since it's a P3 normal bug, so the patch is for GCC10.
Sorry for the misleading, and thanks for pointing it out.

Regards Jun
>> Regards

>> JunMa

>>

>>

>> gcc/ChangeLog

>>

>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>

>>       PR Tree-optimization/89772

>>       * fold-const.c (c_getstr): Add new parameter to get length of

>> additional

>>       trailing nuls after constant string.

>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>>       out-of-bound accesses checking.

>>       * fold-const-call.c (fold_const_call): Likewise.

>>

>>

>> gcc/testsuite/ChangeLog

>>

>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>

>>       PR Tree-optimization/89772

>>       * gcc.dg/builtin-memchr-4.c: New test.
JunMa May 5, 2019, 1:19 a.m. | #3
在 2019/3/21 下午12:51, JunMa 写道:
> Hi

> For now, gcc can not fold code like:

>

> const char a[5] = "123"

> __builtin_memchr (a, '7', sizeof a)

>

> It tries to avoid folding out of string length although length of a is 5.

> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

> builtins when constant string stores in array with some trailing nuls.

>

> This patch folds these cases by exposing additional length of

> trailing nuls in c_getstr().

> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>

> Regards

> JunMa

>

>

> gcc/ChangeLog

>

> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>

>     PR Tree-optimization/89772

>     * fold-const.c (c_getstr): Add new parameter to get length of 

> additional

>     trailing nuls after constant string.

>     * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing 

> nuls in

>     out-of-bound accesses checking.

>     * fold-const-call.c (fold_const_call): Likewise.

>

>

> gcc/testsuite/ChangeLog

>

> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>

>     PR Tree-optimization/89772

>     * gcc.dg/builtin-memchr-4.c: New test.


Ping.

Regards
JunMa
Richard Biener May 6, 2019, 10:02 a.m. | #4
On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:
>

> Hi

> For now, gcc can not fold code like:

>

> const char a[5] = "123"

> __builtin_memchr (a, '7', sizeof a)

>

> It tries to avoid folding out of string length although length of a is 5.

> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

> builtins when constant string stores in array with some trailing nuls.

>

> This patch folds these cases by exposing additional length of

> trailing nuls in c_getstr().

> Bootstrapped/regtested on x86_64-linux, ok for trunk?


It's probably better if gimple_fold_builtin_memchr uses string_constant
directly instead?

You are changing memcmp constant folding but only have a testcase
for memchr.

If we decide to amend c_getstr I would rather make it return the
total length instead of the number of trailing zeros.

Richard.

> Regards

> JunMa

>

>

> gcc/ChangeLog

>

> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>

>      PR Tree-optimization/89772

>      * fold-const.c (c_getstr): Add new parameter to get length of

> additional

>      trailing nuls after constant string.

>      * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>      out-of-bound accesses checking.

>      * fold-const-call.c (fold_const_call): Likewise.

>

>

> gcc/testsuite/ChangeLog

>

> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>

>      PR Tree-optimization/89772

>      * gcc.dg/builtin-memchr-4.c: New test.
JunMa May 6, 2019, 11:58 a.m. | #5
在 2019/5/6 下午6:02, Richard Biener 写道:
> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>> Hi

>> For now, gcc can not fold code like:

>>

>> const char a[5] = "123"

>> __builtin_memchr (a, '7', sizeof a)

>>

>> It tries to avoid folding out of string length although length of a is 5.

>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>> builtins when constant string stores in array with some trailing nuls.

>>

>> This patch folds these cases by exposing additional length of

>> trailing nuls in c_getstr().

>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

> It's probably better if gimple_fold_builtin_memchr uses string_constant

> directly instead?

We can use string_constant in gimple_fold_builtin_memchr, however it is a
bit complex to use it in memchr/memcmp constant folding.
> You are changing memcmp constant folding but only have a testcase

> for memchr.

I'll add later.
> If we decide to amend c_getstr I would rather make it return the

> total length instead of the number of trailing zeros.

I think return the total length is safe in other place as well.
I used the argument in patch since I do not want any impact on
other part at all.

Thanks
JunMa
> Richard.

>

>> Regards

>> JunMa

>>

>>

>> gcc/ChangeLog

>>

>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>

>>       PR Tree-optimization/89772

>>       * fold-const.c (c_getstr): Add new parameter to get length of

>> additional

>>       trailing nuls after constant string.

>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>>       out-of-bound accesses checking.

>>       * fold-const-call.c (fold_const_call): Likewise.

>>

>>

>> gcc/testsuite/ChangeLog

>>

>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>

>>       PR Tree-optimization/89772

>>       * gcc.dg/builtin-memchr-4.c: New test.
Martin Sebor May 6, 2019, 6:05 p.m. | #6
On 5/6/19 5:58 AM, JunMa wrote:
> 在 2019/5/6 下午6:02, Richard Biener 写道:

>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>> Hi

>>> For now, gcc can not fold code like:

>>>

>>> const char a[5] = "123"

>>> __builtin_memchr (a, '7', sizeof a)

>>>

>>> It tries to avoid folding out of string length although length of a 

>>> is 5.

>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>> builtins when constant string stores in array with some trailing nuls.

>>>

>>> This patch folds these cases by exposing additional length of

>>> trailing nuls in c_getstr().

>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>> It's probably better if gimple_fold_builtin_memchr uses string_constant

>> directly instead?

> We can use string_constant in gimple_fold_builtin_memchr, however it is a

> bit complex to use it in memchr/memcmp constant folding.

>> You are changing memcmp constant folding but only have a testcase

>> for memchr.

> I'll add later.

>> If we decide to amend c_getstr I would rather make it return the

>> total length instead of the number of trailing zeros.

> I think return the total length is safe in other place as well.

> I used the argument in patch since I do not want any impact on

> other part at all.


Using c_getstr is simpler than string_constant so it seems fine
to me but I agree that returning a size of the array rather than
the number of trailing nuls would make the API more intuitive.
I would also suggest to use a name for the variable/parameter
that makes that clear.  E.g., string_size or array_size.
(Since trailing nuls don't contribute to the length of a string
referring to length in the name is misleading.)

Martin

> Thanks

> JunMa

>> Richard.

>>

>>> Regards

>>> JunMa

>>>

>>>

>>> gcc/ChangeLog

>>>

>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>

>>>       PR Tree-optimization/89772

>>>       * fold-const.c (c_getstr): Add new parameter to get length of

>>> additional

>>>       trailing nuls after constant string.

>>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing 

>>> nuls in

>>>       out-of-bound accesses checking.

>>>       * fold-const-call.c (fold_const_call): Likewise.

>>>

>>>

>>> gcc/testsuite/ChangeLog

>>>

>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>

>>>       PR Tree-optimization/89772

>>>       * gcc.dg/builtin-memchr-4.c: New test.

> 

>
JunMa May 7, 2019, 2:34 a.m. | #7
在 2019/5/6 下午7:58, JunMa 写道:
> 在 2019/5/6 下午6:02, Richard Biener 写道:

>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>> Hi

>>> For now, gcc can not fold code like:

>>>

>>> const char a[5] = "123"

>>> __builtin_memchr (a, '7', sizeof a)

>>>

>>> It tries to avoid folding out of string length although length of a 

>>> is 5.

>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>> builtins when constant string stores in array with some trailing nuls.

>>>

>>> This patch folds these cases by exposing additional length of

>>> trailing nuls in c_getstr().

>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>> It's probably better if gimple_fold_builtin_memchr uses string_constant

>> directly instead?

> We can use string_constant in gimple_fold_builtin_memchr, however it is a

> bit complex to use it in memchr/memcmp constant folding.

>> You are changing memcmp constant folding but only have a testcase

>> for memchr.

> I'll add later.

>> If we decide to amend c_getstr I would rather make it return the

>> total length instead of the number of trailing zeros.

> I think return the total length is safe in other place as well.

> I used the argument in patch since I do not want any impact on

> other part at all.

>


Although it is safe to use total length, I found that function
inline_expand_builtin_string_cmp() which used c_getstr() may emit
redundant rtls for trailing null chars when total length is returned.

Also it is trivial to handle constant string with trailing null chars.

So this updated patch follow richard's suggestion: using string_constant
directly.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

Regards
JunMa

gcc/ChangeLog

2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

     PR Tree-optimization/89772
     * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in
     out-of-bound accesses checking.

gcc/testsuite/ChangeLog

2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

     PR Tree-optimization/89772
     * gcc.dg/builtin-memchr-4.c: New test.
> Thanks

> JunMa

>> Richard.

>>

>>> Regards

>>> JunMa

>>>

>>>

>>> gcc/ChangeLog

>>>

>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>

>>>       PR Tree-optimization/89772

>>>       * fold-const.c (c_getstr): Add new parameter to get length of

>>> additional

>>>       trailing nuls after constant string.

>>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider 

>>> trailing nuls in

>>>       out-of-bound accesses checking.

>>>       * fold-const-call.c (fold_const_call): Likewise.

>>>

>>>

>>> gcc/testsuite/ChangeLog

>>>

>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>

>>>       PR Tree-optimization/89772

>>>       * gcc.dg/builtin-memchr-4.c: New test.

>
---
 gcc/gimple-fold.c                       |  9 ++++++++-
 gcc/testsuite/gcc.dg/builtin-memchr-4.c | 30 ++++++++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/builtin-memchr-4.c

diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index 1b10bae..7ee5aea 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -2557,7 +2557,14 @@ gimple_fold_builtin_memchr (gimple_stmt_iterator *gsi)
       const char *r = (const char *)memchr (p1, c, MIN (length, string_length));
       if (r == NULL)
 	{
-	  if (length <= string_length)
+	  tree mem_size, offset_node;
+	  string_constant (arg1, &offset_node, &mem_size, NULL);
+	  unsigned HOST_WIDE_INT offset = (offset_node == NULL_TREE)
+					  ? 0 : tree_to_uhwi (offset_node);
+	  /* MEM_SIZE is the size of the array the string literal
+	     is stored in.  */
+	  unsigned HOST_WIDE_INT string_size = tree_to_uhwi (mem_size) - offset;
+	  if (length <= string_size)
 	    {
 	      replace_call_with_value (gsi, build_int_cst (ptr_type_node, 0));
 	      return true;
diff --git a/gcc/testsuite/gcc.dg/builtin-memchr-4.c b/gcc/testsuite/gcc.dg/builtin-memchr-4.c
new file mode 100644
index 0000000..3ef424c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/builtin-memchr-4.c
@@ -0,0 +1,30 @@
+/* PR tree-optimization/89772
+   Verify that memchr calls with a pointer to a constant character
+   are folded as expected.
+   { dg-do compile }
+   { dg-options "-O1 -Wall -fdump-tree-lower" } */
+
+typedef __SIZE_TYPE__  size_t;
+typedef __WCHAR_TYPE__ wchar_t;
+
+extern void* memchr (const void*, int, size_t);
+extern int printf (const char*, ...);
+extern void abort (void);
+
+#define A(expr)						\
+  ((expr)						\
+   ? (void)0						\
+   : (printf ("assertion failed on line %i: %s\n",	\
+	      __LINE__, #expr),				\
+      abort ()))
+
+const char a[8] = {'a',0,'b'};
+
+void test_memchr_cst_char (void)
+{
+  A (!memchr (a, 'c', 2));
+  A (!memchr (a, 'c', 5));
+  A (!memchr (a, 'c', sizeof a));
+}
+
+/* { dg-final { scan-tree-dump-not "abort" "gimple" } } */
JunMa May 7, 2019, 2:51 a.m. | #8
在 2019/5/7 上午2:05, Martin Sebor 写道:
> On 5/6/19 5:58 AM, JunMa wrote:

>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>> Hi

>>>> For now, gcc can not fold code like:

>>>>

>>>> const char a[5] = "123"

>>>> __builtin_memchr (a, '7', sizeof a)

>>>>

>>>> It tries to avoid folding out of string length although length of a 

>>>> is 5.

>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>> builtins when constant string stores in array with some trailing nuls.

>>>>

>>>> This patch folds these cases by exposing additional length of

>>>> trailing nuls in c_getstr().

>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>> It's probably better if gimple_fold_builtin_memchr uses string_constant

>>> directly instead?

>> We can use string_constant in gimple_fold_builtin_memchr, however it 

>> is a

>> bit complex to use it in memchr/memcmp constant folding.

>>> You are changing memcmp constant folding but only have a testcase

>>> for memchr.

>> I'll add later.

>>> If we decide to amend c_getstr I would rather make it return the

>>> total length instead of the number of trailing zeros.

>> I think return the total length is safe in other place as well.

>> I used the argument in patch since I do not want any impact on

>> other part at all.

>

> Using c_getstr is simpler than string_constant so it seems fine

> to me but I agree that returning a size of the array rather than

> the number of trailing nuls would make the API more intuitive.

> I would also suggest to use a name for the variable/parameter

> that makes that clear.  E.g., string_size or array_size.

> (Since trailing nuls don't contribute to the length of a string

> referring to length in the name is misleading.)

>


I found that the return length of c_getstr() is used in function
inline_expand_builtin_string_cmp(). It may emit redundant rtls for
trailing null chars when total length is returned. So Although it
is safe to return total length, It seems that using string_constant
is better.

Thanks
JunMa


> Martin

>

>> Thanks

>> JunMa

>>> Richard.

>>>

>>>> Regards

>>>> JunMa

>>>>

>>>>

>>>> gcc/ChangeLog

>>>>

>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>

>>>>       PR Tree-optimization/89772

>>>>       * fold-const.c (c_getstr): Add new parameter to get length of

>>>> additional

>>>>       trailing nuls after constant string.

>>>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider 

>>>> trailing nuls in

>>>>       out-of-bound accesses checking.

>>>>       * fold-const-call.c (fold_const_call): Likewise.

>>>>

>>>>

>>>> gcc/testsuite/ChangeLog

>>>>

>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>

>>>>       PR Tree-optimization/89772

>>>>       * gcc.dg/builtin-memchr-4.c: New test.

>>

>>
Richard Biener May 8, 2019, 2:31 p.m. | #9
On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:
>

> 在 2019/5/6 下午7:58, JunMa 写道:

> > 在 2019/5/6 下午6:02, Richard Biener 写道:

> >> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

> >>> Hi

> >>> For now, gcc can not fold code like:

> >>>

> >>> const char a[5] = "123"

> >>> __builtin_memchr (a, '7', sizeof a)

> >>>

> >>> It tries to avoid folding out of string length although length of a

> >>> is 5.

> >>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

> >>> builtins when constant string stores in array with some trailing nuls.

> >>>

> >>> This patch folds these cases by exposing additional length of

> >>> trailing nuls in c_getstr().

> >>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

> >> It's probably better if gimple_fold_builtin_memchr uses string_constant

> >> directly instead?

> > We can use string_constant in gimple_fold_builtin_memchr, however it is a

> > bit complex to use it in memchr/memcmp constant folding.

> >> You are changing memcmp constant folding but only have a testcase

> >> for memchr.

> > I'll add later.

> >> If we decide to amend c_getstr I would rather make it return the

> >> total length instead of the number of trailing zeros.

> > I think return the total length is safe in other place as well.

> > I used the argument in patch since I do not want any impact on

> > other part at all.

> >

>

> Although it is safe to use total length, I found that function

> inline_expand_builtin_string_cmp() which used c_getstr() may emit

> redundant rtls for trailing null chars when total length is returned.

>

> Also it is trivial to handle constant string with trailing null chars.

>

> So this updated patch follow richard's suggestion: using string_constant

> directly.

>

> Bootstrapped/regtested on x86_64-linux, ok for trunk?


Doesn't this fold to NULL for the case where seaching for '0' and it
doesn't occur in the string constant but only the zero-padding?
So you'd need to conditionalize on c being not zero (or handle
that case specially by actually finding the first zero in the padding)?
I think there was work to have all string constants zero terminated
but I'm not sure if we can rely on that here.  Bernd?

Richard.

> Regards

> JunMa

>

> gcc/ChangeLog

>

> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>

>      PR Tree-optimization/89772

>      * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>      out-of-bound accesses checking.

>

> gcc/testsuite/ChangeLog

>

> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>

>      PR Tree-optimization/89772

>      * gcc.dg/builtin-memchr-4.c: New test.

> > Thanks

> > JunMa

> >> Richard.

> >>

> >>> Regards

> >>> JunMa

> >>>

> >>>

> >>> gcc/ChangeLog

> >>>

> >>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

> >>>

> >>>       PR Tree-optimization/89772

> >>>       * fold-const.c (c_getstr): Add new parameter to get length of

> >>> additional

> >>>       trailing nuls after constant string.

> >>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider

> >>> trailing nuls in

> >>>       out-of-bound accesses checking.

> >>>       * fold-const-call.c (fold_const_call): Likewise.

> >>>

> >>>

> >>> gcc/testsuite/ChangeLog

> >>>

> >>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

> >>>

> >>>       PR Tree-optimization/89772

> >>>       * gcc.dg/builtin-memchr-4.c: New test.

> >

>
Bernd Edlinger May 8, 2019, 7:02 p.m. | #10
On 5/8/19 4:31 PM, Richard Biener wrote:
> On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>

>> 在 2019/5/6 下午7:58, JunMa 写道:

>>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>>> Hi

>>>>> For now, gcc can not fold code like:

>>>>>

>>>>> const char a[5] = "123"

>>>>> __builtin_memchr (a, '7', sizeof a)

>>>>>

>>>>> It tries to avoid folding out of string length although length of a

>>>>> is 5.

>>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>>> builtins when constant string stores in array with some trailing nuls.

>>>>>

>>>>> This patch folds these cases by exposing additional length of

>>>>> trailing nuls in c_getstr().

>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>> It's probably better if gimple_fold_builtin_memchr uses string_constant

>>>> directly instead?

>>> We can use string_constant in gimple_fold_builtin_memchr, however it is a

>>> bit complex to use it in memchr/memcmp constant folding.

>>>> You are changing memcmp constant folding but only have a testcase

>>>> for memchr.

>>> I'll add later.

>>>> If we decide to amend c_getstr I would rather make it return the

>>>> total length instead of the number of trailing zeros.

>>> I think return the total length is safe in other place as well.

>>> I used the argument in patch since I do not want any impact on

>>> other part at all.

>>>

>>

>> Although it is safe to use total length, I found that function

>> inline_expand_builtin_string_cmp() which used c_getstr() may emit

>> redundant rtls for trailing null chars when total length is returned.

>>

>> Also it is trivial to handle constant string with trailing null chars.

>>

>> So this updated patch follow richard's suggestion: using string_constant

>> directly.

>>

>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

> 

> Doesn't this fold to NULL for the case where seaching for '0' and it

> doesn't occur in the string constant but only the zero-padding?

> So you'd need to conditionalize on c being not zero (or handle

> that case specially by actually finding the first zero in the padding)?

> I think there was work to have all string constants zero terminated

> but I'm not sure if we can rely on that here.  Bernd?

> 


It turned out that there is a number of languages that don't have zero-terminated
strings by default, which would have complicated the patch just too much for too
little benefit.

In the end, it was more important to guarantee that mem_size >= string_length holds.

In C it is just a convention that string constants have usually a zero-termination,
but even with C there are ways how strings constants can be not zero-terminated.

There can in theory be optimizations that introduce not zero-terminated strings,
like tree-ssa-forwprop.c, where a not zero-terminated string constant is folded
in simplify_builtin_call.

In such a case, c_getstr might in theory return a string without zero-termination,
but I think it will be rather difficult to find a C test case for that.

Well, if I had a test case for that I would probably fix it in c_getstr to consider
the implicit padding as equivalent to an explicit zero-termination.


Bernd.


> Richard.

> 

>> Regards

>> JunMa

>>

>> gcc/ChangeLog

>>

>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>

>>      PR Tree-optimization/89772

>>      * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>>      out-of-bound accesses checking.

>>

>> gcc/testsuite/ChangeLog

>>

>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>

>>      PR Tree-optimization/89772

>>      * gcc.dg/builtin-memchr-4.c: New test.

>>> Thanks

>>> JunMa

>>>> Richard.

>>>>

>>>>> Regards

>>>>> JunMa

>>>>>

>>>>>

>>>>> gcc/ChangeLog

>>>>>

>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>

>>>>>       PR Tree-optimization/89772

>>>>>       * fold-const.c (c_getstr): Add new parameter to get length of

>>>>> additional

>>>>>       trailing nuls after constant string.

>>>>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider

>>>>> trailing nuls in

>>>>>       out-of-bound accesses checking.

>>>>>       * fold-const-call.c (fold_const_call): Likewise.

>>>>>

>>>>>

>>>>> gcc/testsuite/ChangeLog

>>>>>

>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>

>>>>>       PR Tree-optimization/89772

>>>>>       * gcc.dg/builtin-memchr-4.c: New test.

>>>

>>
JunMa May 9, 2019, 2 a.m. | #11
在 2019/5/8 下午10:31, Richard Biener 写道:
> On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:

>> 在 2019/5/6 下午7:58, JunMa 写道:

>>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>>> Hi

>>>>> For now, gcc can not fold code like:

>>>>>

>>>>> const char a[5] = "123"

>>>>> __builtin_memchr (a, '7', sizeof a)

>>>>>

>>>>> It tries to avoid folding out of string length although length of a

>>>>> is 5.

>>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>>> builtins when constant string stores in array with some trailing nuls.

>>>>>

>>>>> This patch folds these cases by exposing additional length of

>>>>> trailing nuls in c_getstr().

>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>> It's probably better if gimple_fold_builtin_memchr uses string_constant

>>>> directly instead?

>>> We can use string_constant in gimple_fold_builtin_memchr, however it is a

>>> bit complex to use it in memchr/memcmp constant folding.

>>>> You are changing memcmp constant folding but only have a testcase

>>>> for memchr.

>>> I'll add later.

>>>> If we decide to amend c_getstr I would rather make it return the

>>>> total length instead of the number of trailing zeros.

>>> I think return the total length is safe in other place as well.

>>> I used the argument in patch since I do not want any impact on

>>> other part at all.

>>>

>> Although it is safe to use total length, I found that function

>> inline_expand_builtin_string_cmp() which used c_getstr() may emit

>> redundant rtls for trailing null chars when total length is returned.

>>

>> Also it is trivial to handle constant string with trailing null chars.

>>

>> So this updated patch follow richard's suggestion: using string_constant

>> directly.

>>

>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

> Doesn't this fold to NULL for the case where seaching for '0' and it

> doesn't occur in the string constant but only the zero-padding?



For C case like:

   const char str[100] = “hello world”
   const char ch = '\0';
   ret = (char*)memchr(str, ch, strlen(str));
   ret2 = (char*)memchr(str, ch, sizeof str);

then ret is null,  ret2 is not


> So you'd need to conditionalize on c being not zero (or handle

> that case specially by actually finding the first zero in the padding)?



Yes, the string length return from c_getstr() including the termination
NULL most of the time(when string_length <= string_size).
If ch is NULL and the string length >= 3rd argument of memchr,
then we donot need to handle this.

Thanks
JunMa


> I think there was work to have all string constants zero terminated

> but I'm not sure if we can rely on that here.  Bernd?

>

> Richard.

>

>> Regards

>> JunMa

>>

>> gcc/ChangeLog

>>

>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>

>>       PR Tree-optimization/89772

>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>>       out-of-bound accesses checking.

>>

>> gcc/testsuite/ChangeLog

>>

>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>

>>       PR Tree-optimization/89772

>>       * gcc.dg/builtin-memchr-4.c: New test.

>>> Thanks

>>> JunMa

>>>> Richard.

>>>>

>>>>> Regards

>>>>> JunMa

>>>>>

>>>>>

>>>>> gcc/ChangeLog

>>>>>

>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>

>>>>>        PR Tree-optimization/89772

>>>>>        * fold-const.c (c_getstr): Add new parameter to get length of

>>>>> additional

>>>>>        trailing nuls after constant string.

>>>>>        * gimple-fold.c (gimple_fold_builtin_memchr): consider

>>>>> trailing nuls in

>>>>>        out-of-bound accesses checking.

>>>>>        * fold-const-call.c (fold_const_call): Likewise.

>>>>>

>>>>>

>>>>> gcc/testsuite/ChangeLog

>>>>>

>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>

>>>>>        PR Tree-optimization/89772

>>>>>        * gcc.dg/builtin-memchr-4.c: New test.
JunMa May 9, 2019, 2:22 a.m. | #12
在 2019/5/9 上午3:02, Bernd Edlinger 写道:
> On 5/8/19 4:31 PM, Richard Biener wrote:

>> On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>> 在 2019/5/6 下午7:58, JunMa 写道:

>>>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>>>> Hi

>>>>>> For now, gcc can not fold code like:

>>>>>>

>>>>>> const char a[5] = "123"

>>>>>> __builtin_memchr (a, '7', sizeof a)

>>>>>>

>>>>>> It tries to avoid folding out of string length although length of a

>>>>>> is 5.

>>>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>>>> builtins when constant string stores in array with some trailing nuls.

>>>>>>

>>>>>> This patch folds these cases by exposing additional length of

>>>>>> trailing nuls in c_getstr().

>>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>>> It's probably better if gimple_fold_builtin_memchr uses string_constant

>>>>> directly instead?

>>>> We can use string_constant in gimple_fold_builtin_memchr, however it is a

>>>> bit complex to use it in memchr/memcmp constant folding.

>>>>> You are changing memcmp constant folding but only have a testcase

>>>>> for memchr.

>>>> I'll add later.

>>>>> If we decide to amend c_getstr I would rather make it return the

>>>>> total length instead of the number of trailing zeros.

>>>> I think return the total length is safe in other place as well.

>>>> I used the argument in patch since I do not want any impact on

>>>> other part at all.

>>>>

>>> Although it is safe to use total length, I found that function

>>> inline_expand_builtin_string_cmp() which used c_getstr() may emit

>>> redundant rtls for trailing null chars when total length is returned.

>>>

>>> Also it is trivial to handle constant string with trailing null chars.

>>>

>>> So this updated patch follow richard's suggestion: using string_constant

>>> directly.

>>>

>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>> Doesn't this fold to NULL for the case where seaching for '0' and it

>> doesn't occur in the string constant but only the zero-padding?

>> So you'd need to conditionalize on c being not zero (or handle

>> that case specially by actually finding the first zero in the padding)?

>> I think there was work to have all string constants zero terminated

>> but I'm not sure if we can rely on that here.  Bernd?

>>

> It turned out that there is a number of languages that don't have zero-terminated

> strings by default, which would have complicated the patch just too much for too

> little benefit.

>

> In the end, it was more important to guarantee that mem_size >= string_length holds.


The string_length returned form  c_getstr() is equal to mem_size when 
string_length > string_size, so I'll add assert

in the patch.

> In C it is just a convention that string constants have usually a zero-termination,

> but even with C there are ways how strings constants can be not zero-terminated.

>

> There can in theory be optimizations that introduce not zero-terminated strings,

> like tree-ssa-forwprop.c, where a not zero-terminated string constant is folded

> in simplify_builtin_call.

>

> In such a case, c_getstr might in theory return a string without zero-termination,

> but I think it will be rather difficult to find a C test case for that.

>

> Well, if I had a test case for that I would probably fix it in c_getstr to consider

> the implicit padding as equivalent to an explicit zero-termination.



c_getstr() makes sure  the returned string has zero-termination when 2nd 
argument is NULL, but not when
string_length is returned.  I think it is the caller's responsibility to 
take care of both of the returned string and length.


Thanks
JunMa


>

> Bernd.

>

>

>> Richard.

>>

>>> Regards

>>> JunMa

>>>

>>> gcc/ChangeLog

>>>

>>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>>

>>>       PR Tree-optimization/89772

>>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider trailing nuls in

>>>       out-of-bound accesses checking.

>>>

>>> gcc/testsuite/ChangeLog

>>>

>>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>>

>>>       PR Tree-optimization/89772

>>>       * gcc.dg/builtin-memchr-4.c: New test.

>>>> Thanks

>>>> JunMa

>>>>> Richard.

>>>>>

>>>>>> Regards

>>>>>> JunMa

>>>>>>

>>>>>>

>>>>>> gcc/ChangeLog

>>>>>>

>>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>>

>>>>>>        PR Tree-optimization/89772

>>>>>>        * fold-const.c (c_getstr): Add new parameter to get length of

>>>>>> additional

>>>>>>        trailing nuls after constant string.

>>>>>>        * gimple-fold.c (gimple_fold_builtin_memchr): consider

>>>>>> trailing nuls in

>>>>>>        out-of-bound accesses checking.

>>>>>>        * fold-const-call.c (fold_const_call): Likewise.

>>>>>>

>>>>>>

>>>>>> gcc/testsuite/ChangeLog

>>>>>>

>>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>>

>>>>>>        PR Tree-optimization/89772

>>>>>>        * gcc.dg/builtin-memchr-4.c: New test.
JunMa May 9, 2019, 8:01 a.m. | #13
在 2019/5/9 上午10:22, JunMa 写道:
> 在 2019/5/9 上午3:02, Bernd Edlinger 写道:

>> On 5/8/19 4:31 PM, Richard Biener wrote:

>>> On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>> 在 2019/5/6 下午7:58, JunMa 写道:

>>>>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>>>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com> 

>>>>>> wrote:

>>>>>>> Hi

>>>>>>> For now, gcc can not fold code like:

>>>>>>>

>>>>>>> const char a[5] = "123"

>>>>>>> __builtin_memchr (a, '7', sizeof a)

>>>>>>>

>>>>>>> It tries to avoid folding out of string length although length of a

>>>>>>> is 5.

>>>>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>>>>> builtins when constant string stores in array with some trailing 

>>>>>>> nuls.

>>>>>>>

>>>>>>> This patch folds these cases by exposing additional length of

>>>>>>> trailing nuls in c_getstr().

>>>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>>>> It's probably better if gimple_fold_builtin_memchr uses 

>>>>>> string_constant

>>>>>> directly instead?

>>>>> We can use string_constant in gimple_fold_builtin_memchr, however 

>>>>> it is a

>>>>> bit complex to use it in memchr/memcmp constant folding.

>>>>>> You are changing memcmp constant folding but only have a testcase

>>>>>> for memchr.

>>>>> I'll add later.

>>>>>> If we decide to amend c_getstr I would rather make it return the

>>>>>> total length instead of the number of trailing zeros.

>>>>> I think return the total length is safe in other place as well.

>>>>> I used the argument in patch since I do not want any impact on

>>>>> other part at all.

>>>>>

>>>> Although it is safe to use total length, I found that function

>>>> inline_expand_builtin_string_cmp() which used c_getstr() may emit

>>>> redundant rtls for trailing null chars when total length is returned.

>>>>

>>>> Also it is trivial to handle constant string with trailing null chars.

>>>>

>>>> So this updated patch follow richard's suggestion: using 

>>>> string_constant

>>>> directly.

>>>>

>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>> Doesn't this fold to NULL for the case where seaching for '0' and it

>>> doesn't occur in the string constant but only the zero-padding?

>>> So you'd need to conditionalize on c being not zero (or handle

>>> that case specially by actually finding the first zero in the padding)?

>>> I think there was work to have all string constants zero terminated

>>> but I'm not sure if we can rely on that here.  Bernd?

>>>

>> It turned out that there is a number of languages that don't have 

>> zero-terminated

>> strings by default, which would have complicated the patch just too 

>> much for too

>> little benefit.

>>

>> In the end, it was more important to guarantee that mem_size >= 

>> string_length holds.

>

> The string_length returned form  c_getstr() is equal to mem_size when 

> string_length > string_size, so I'll add assert

>

> in the patch.

>

>> In C it is just a convention that string constants have usually a 

>> zero-termination,

>> but even with C there are ways how strings constants can be not 

>> zero-terminated.

>>

>> There can in theory be optimizations that introduce not 

>> zero-terminated strings,

>> like tree-ssa-forwprop.c, where a not zero-terminated string constant 

>> is folded

>> in simplify_builtin_call.

>>

>> In such a case, c_getstr might in theory return a string without 

>> zero-termination,

>> but I think it will be rather difficult to find a C test case for that.

>>

>> Well, if I had a test case for that I would probably fix it in 

>> c_getstr to consider

>> the implicit padding as equivalent to an explicit zero-termination.

>

>

> c_getstr() makes sure  the returned string has zero-termination when 

> 2nd argument is NULL, but not when

> string_length is returned.  I think it is the caller's responsibility 

> to take care of both of the returned string and length.

>

>


Update the patch with assert checking on condition
string_length <= string_size. FYI.

Also Bootstrapped/regtested on x86_64-linux.

Regards
JunMa


> Thanks

> JunMa

>

>

>>

>> Bernd.

>>

>>

>>> Richard.

>>>

>>>> Regards

>>>> JunMa

>>>>

>>>> gcc/ChangeLog

>>>>

>>>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>>>

>>>>       PR Tree-optimization/89772

>>>>       * gimple-fold.c (gimple_fold_builtin_memchr): consider 

>>>> trailing nuls in

>>>>       out-of-bound accesses checking.

>>>>

>>>> gcc/testsuite/ChangeLog

>>>>

>>>> 2019-05-07  Jun Ma <JunMa@linux.alibaba.com>

>>>>

>>>>       PR Tree-optimization/89772

>>>>       * gcc.dg/builtin-memchr-4.c: New test.

>>>>> Thanks

>>>>> JunMa

>>>>>> Richard.

>>>>>>

>>>>>>> Regards

>>>>>>> JunMa

>>>>>>>

>>>>>>>

>>>>>>> gcc/ChangeLog

>>>>>>>

>>>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>>>

>>>>>>>        PR Tree-optimization/89772

>>>>>>>        * fold-const.c (c_getstr): Add new parameter to get 

>>>>>>> length of

>>>>>>> additional

>>>>>>>        trailing nuls after constant string.

>>>>>>>        * gimple-fold.c (gimple_fold_builtin_memchr): consider

>>>>>>> trailing nuls in

>>>>>>>        out-of-bound accesses checking.

>>>>>>>        * fold-const-call.c (fold_const_call): Likewise.

>>>>>>>

>>>>>>>

>>>>>>> gcc/testsuite/ChangeLog

>>>>>>>

>>>>>>> 2019-03-21  Jun Ma <JunMa@linux.alibaba.com>

>>>>>>>

>>>>>>>        PR Tree-optimization/89772

>>>>>>>        * gcc.dg/builtin-memchr-4.c: New test.

>
---
 gcc/gimple-fold.c                       | 10 +++++++++-
 gcc/testsuite/gcc.dg/builtin-memchr-4.c | 30 ++++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/builtin-memchr-4.c

diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index 1b10bae..c4fd5b1 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -2557,7 +2557,15 @@ gimple_fold_builtin_memchr (gimple_stmt_iterator *gsi)
       const char *r = (const char *)memchr (p1, c, MIN (length, string_length));
       if (r == NULL)
 	{
-	  if (length <= string_length)
+	  tree mem_size, offset_node;
+	  string_constant (arg1, &offset_node, &mem_size, NULL);
+	  unsigned HOST_WIDE_INT offset = (offset_node == NULL_TREE)
+					  ? 0 : tree_to_uhwi (offset_node);
+	  /* MEM_SIZE is the size of the array the string literal
+	     is stored in.  */
+	  unsigned HOST_WIDE_INT string_size = tree_to_uhwi (mem_size) - offset;
+	  gcc_checking_assert (string_length <= string_size);
+	  if (length <= string_size)
 	    {
 	      replace_call_with_value (gsi, build_int_cst (ptr_type_node, 0));
 	      return true;
diff --git a/gcc/testsuite/gcc.dg/builtin-memchr-4.c b/gcc/testsuite/gcc.dg/builtin-memchr-4.c
new file mode 100644
index 0000000..3ef424c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/builtin-memchr-4.c
@@ -0,0 +1,30 @@
+/* PR tree-optimization/89772
+   Verify that memchr calls with a pointer to a constant character
+   are folded as expected.
+   { dg-do compile }
+   { dg-options "-O1 -Wall -fdump-tree-lower" } */
+
+typedef __SIZE_TYPE__  size_t;
+typedef __WCHAR_TYPE__ wchar_t;
+
+extern void* memchr (const void*, int, size_t);
+extern int printf (const char*, ...);
+extern void abort (void);
+
+#define A(expr)						\
+  ((expr)						\
+   ? (void)0						\
+   : (printf ("assertion failed on line %i: %s\n",	\
+	      __LINE__, #expr),				\
+      abort ()))
+
+const char a[8] = {'a',0,'b'};
+
+void test_memchr_cst_char (void)
+{
+  A (!memchr (a, 'c', 2));
+  A (!memchr (a, 'c', 5));
+  A (!memchr (a, 'c', sizeof a));
+}
+
+/* { dg-final { scan-tree-dump-not "abort" "gimple" } } */
Jeff Law June 17, 2019, 10:46 p.m. | #14
On 5/9/19 2:01 AM, JunMa wrote:
> 在 2019/5/9 上午10:22, JunMa 写道:

>> 在 2019/5/9 上午3:02, Bernd Edlinger 写道:

>>> On 5/8/19 4:31 PM, Richard Biener wrote:

>>>> On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>>> 在 2019/5/6 下午7:58, JunMa 写道:

>>>>>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>>>>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com>

>>>>>>> wrote:

>>>>>>>> Hi

>>>>>>>> For now, gcc can not fold code like:

>>>>>>>>

>>>>>>>> const char a[5] = "123"

>>>>>>>> __builtin_memchr (a, '7', sizeof a)

>>>>>>>>

>>>>>>>> It tries to avoid folding out of string length although length of a

>>>>>>>> is 5.

>>>>>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>>>>>> builtins when constant string stores in array with some trailing

>>>>>>>> nuls.

>>>>>>>>

>>>>>>>> This patch folds these cases by exposing additional length of

>>>>>>>> trailing nuls in c_getstr().

>>>>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>>>>> It's probably better if gimple_fold_builtin_memchr uses

>>>>>>> string_constant

>>>>>>> directly instead?

>>>>>> We can use string_constant in gimple_fold_builtin_memchr, however

>>>>>> it is a

>>>>>> bit complex to use it in memchr/memcmp constant folding.

>>>>>>> You are changing memcmp constant folding but only have a testcase

>>>>>>> for memchr.

>>>>>> I'll add later.

>>>>>>> If we decide to amend c_getstr I would rather make it return the

>>>>>>> total length instead of the number of trailing zeros.

>>>>>> I think return the total length is safe in other place as well.

>>>>>> I used the argument in patch since I do not want any impact on

>>>>>> other part at all.

>>>>>>

>>>>> Although it is safe to use total length, I found that function

>>>>> inline_expand_builtin_string_cmp() which used c_getstr() may emit

>>>>> redundant rtls for trailing null chars when total length is returned.

>>>>>

>>>>> Also it is trivial to handle constant string with trailing null chars.

>>>>>

>>>>> So this updated patch follow richard's suggestion: using

>>>>> string_constant

>>>>> directly.

>>>>>

>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>> Doesn't this fold to NULL for the case where seaching for '0' and it

>>>> doesn't occur in the string constant but only the zero-padding?

So I'm not sure if JunMa addressed this question specifically.  What
happens is we'll get back a NULL terminated string from c_getstr, but
the returned length will include the NUL terminator.  Then we call
memchr on the result with a length that would include that NUL
terminator.  So I'm pretty sure the current patch will DTRT in that case.

It'd be better to have a stronger test which verified not only that the
call was folded away, but what the resultant value was and whether or
not it was the right value.

That would include testing for NUL in the string as well as testing for
NUL in the tail padding.

I'll ack the change to gimple-fold, but please improve the testcase a
bit and commit the change to gimple-fold and the improved testcase together.

Thanks, and sorry for the delays.

jeff
JunMa June 27, 2019, 7:36 a.m. | #15
在 2019/6/18 上午6:46, Jeff Law 写道:
> On 5/9/19 2:01 AM, JunMa wrote:

>> 在 2019/5/9 上午10:22, JunMa 写道:

>>> 在 2019/5/9 上午3:02, Bernd Edlinger 写道:

>>>> On 5/8/19 4:31 PM, Richard Biener wrote:

>>>>> On Tue, May 7, 2019 at 4:34 AM JunMa <JunMa@linux.alibaba.com> wrote:

>>>>>> 在 2019/5/6 下午7:58, JunMa 写道:

>>>>>>> 在 2019/5/6 下午6:02, Richard Biener 写道:

>>>>>>>> On Thu, Mar 21, 2019 at 5:57 AM JunMa <JunMa@linux.alibaba.com>

>>>>>>>> wrote:

>>>>>>>>> Hi

>>>>>>>>> For now, gcc can not fold code like:

>>>>>>>>>

>>>>>>>>> const char a[5] = "123"

>>>>>>>>> __builtin_memchr (a, '7', sizeof a)

>>>>>>>>>

>>>>>>>>> It tries to avoid folding out of string length although length of a

>>>>>>>>> is 5.

>>>>>>>>> This is a bit conservative, it's safe to folding memchr/bcmp/memcmp

>>>>>>>>> builtins when constant string stores in array with some trailing

>>>>>>>>> nuls.

>>>>>>>>>

>>>>>>>>> This patch folds these cases by exposing additional length of

>>>>>>>>> trailing nuls in c_getstr().

>>>>>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>>>>>> It's probably better if gimple_fold_builtin_memchr uses

>>>>>>>> string_constant

>>>>>>>> directly instead?

>>>>>>> We can use string_constant in gimple_fold_builtin_memchr, however

>>>>>>> it is a

>>>>>>> bit complex to use it in memchr/memcmp constant folding.

>>>>>>>> You are changing memcmp constant folding but only have a testcase

>>>>>>>> for memchr.

>>>>>>> I'll add later.

>>>>>>>> If we decide to amend c_getstr I would rather make it return the

>>>>>>>> total length instead of the number of trailing zeros.

>>>>>>> I think return the total length is safe in other place as well.

>>>>>>> I used the argument in patch since I do not want any impact on

>>>>>>> other part at all.

>>>>>>>

>>>>>> Although it is safe to use total length, I found that function

>>>>>> inline_expand_builtin_string_cmp() which used c_getstr() may emit

>>>>>> redundant rtls for trailing null chars when total length is returned.

>>>>>>

>>>>>> Also it is trivial to handle constant string with trailing null chars.

>>>>>>

>>>>>> So this updated patch follow richard's suggestion: using

>>>>>> string_constant

>>>>>> directly.

>>>>>>

>>>>>> Bootstrapped/regtested on x86_64-linux, ok for trunk?

>>>>> Doesn't this fold to NULL for the case where seaching for '0' and it

>>>>> doesn't occur in the string constant but only the zero-padding?

> So I'm not sure if JunMa addressed this question specifically.  What

> happens is we'll get back a NULL terminated string from c_getstr, but

> the returned length will include the NUL terminator.  Then we call

> memchr on the result with a length that would include that NUL

> terminator.  So I'm pretty sure the current patch will DTRT in that case.

>

> It'd be better to have a stronger test which verified not only that the

> call was folded away, but what the resultant value was and whether or

> not it was the right value.

>

> That would include testing for NUL in the string as well as testing for

> NUL in the tail padding.

>

> I'll ack the change to gimple-fold, but please improve the testcase a

> bit and commit the change to gimple-fold and the improved testcase together.

>

> Thanks, and sorry for the delays.

Thanks, I'll update the testcase and check in after pass the regtest.

Regards
Jun
> jeff

Patch

diff --git a/gcc/fold-const-call.c b/gcc/fold-const-call.c
index 702c8b4..ea81f6a 100644
--- a/gcc/fold-const-call.c
+++ b/gcc/fold-const-call.c
@@ -1720,7 +1720,7 @@  fold_const_call (combined_fn fn, tree type, tree arg0, tree arg1, tree arg2)
 {
   const char *p0, *p1;
   char c;
-  unsigned HOST_WIDE_INT s0, s1;
+  unsigned HOST_WIDE_INT s0, s1, s3, s4;
   size_t s2 = 0;
   switch (fn)
     {
@@ -1756,10 +1756,10 @@  fold_const_call (combined_fn fn, tree type, tree arg0, tree arg1, tree arg2)
 	  && !TREE_SIDE_EFFECTS (arg0)
 	  && !TREE_SIDE_EFFECTS (arg1))
 	return build_int_cst (type, 0);
-      if ((p0 = c_getstr (arg0, &s0))
-	  && (p1 = c_getstr (arg1, &s1))
-	  && s2 <= s0
-	  && s2 <= s1)
+      if ((p0 = c_getstr (arg0, &s0, &s3))
+	  && (p1 = c_getstr (arg1, &s1, &s4))
+	  && s2 <= s0 + s3
+	  && s2 <= s1 + s4)
 	return build_cmp_result (type, memcmp (p0, p1, s2));
       return NULL_TREE;
 
@@ -1770,8 +1770,8 @@  fold_const_call (combined_fn fn, tree type, tree arg0, tree arg1, tree arg2)
 	  && !TREE_SIDE_EFFECTS (arg0)
 	  && !TREE_SIDE_EFFECTS (arg1))
 	return build_int_cst (type, 0);
-      if ((p0 = c_getstr (arg0, &s0))
-	  && s2 <= s0
+      if ((p0 = c_getstr (arg0, &s0, &s3))
+	  && s2 <= s0 + s3
 	  && target_char_cst_p (arg1, &c))
 	{
 	  const char *r = (const char *) memchr (p0, c, s2);
diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index ec28b43..413f0f0 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -14607,10 +14607,13 @@  fold_build_pointer_plus_hwi_loc (location_t loc, tree ptr, HOST_WIDE_INT off)
    characters within it if SRC is a reference to a string plus some
    constant offset).  If STRLEN is non-null, store the number of bytes
    in the string constant including the terminating NUL char.  *STRLEN is
-   typically strlen(P) + 1 in the absence of embedded NUL characters.  */
+   typically strlen(P) + 1 in the absence of embedded NUL characters.
+   If TRAILINGNULSLEN is non-null, store the number of trailing NUL chars
+   after terminating NUL char of pointer P.  */
 
 const char *
-c_getstr (tree src, unsigned HOST_WIDE_INT *strlen /* = NULL */)
+c_getstr (tree src, unsigned HOST_WIDE_INT *strlen /* = NULL */,
+	  unsigned HOST_WIDE_INT *trailingnulslen /* =NULL */)
 {
   tree offset_node;
   tree mem_size;
@@ -14639,16 +14642,13 @@  c_getstr (tree src, unsigned HOST_WIDE_INT *strlen /* = NULL */)
      literal is stored in.  */
   unsigned HOST_WIDE_INT string_length = TREE_STRING_LENGTH (src);
   unsigned HOST_WIDE_INT string_size = tree_to_uhwi (mem_size);
-
-  /* Ideally this would turn into a gcc_checking_assert over time.  */
-  if (string_length > string_size)
-    string_length = string_size;
-
   const char *string = TREE_STRING_POINTER (src);
 
   /* Ideally this would turn into a gcc_checking_assert over time.  */
   if (string_length > string_size)
     string_length = string_size;
+  if (trailingnulslen)
+    *trailingnulslen = string_size - string_length;
 
   if (string_length == 0
       || offset >= string_size)
diff --git a/gcc/fold-const.h b/gcc/fold-const.h
index 049fee9..5073138 100644
--- a/gcc/fold-const.h
+++ b/gcc/fold-const.h
@@ -187,7 +187,8 @@  extern bool expr_not_equal_to (tree t, const wide_int &);
 extern tree const_unop (enum tree_code, tree, tree);
 extern tree const_binop (enum tree_code, tree, tree, tree);
 extern bool negate_mathfn_p (combined_fn);
-extern const char *c_getstr (tree, unsigned HOST_WIDE_INT * = NULL);
+extern const char *c_getstr (tree, unsigned HOST_WIDE_INT * = NULL,
+			     unsigned HOST_WIDE_INT * = NULL);
 extern wide_int tree_nonzero_bits (const_tree);
 
 /* Return OFF converted to a pointer offset type suitable as offset for
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index 62d2e0a..096b950 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -2541,14 +2541,15 @@  gimple_fold_builtin_memchr (gimple_stmt_iterator *gsi)
 
   unsigned HOST_WIDE_INT length = tree_to_uhwi (len);
   unsigned HOST_WIDE_INT string_length;
-  const char *p1 = c_getstr (arg1, &string_length);
+  unsigned HOST_WIDE_INT trailingnuls_length;
+  const char *p1 = c_getstr (arg1, &string_length, &trailingnuls_length);
 
   if (p1)
     {
       const char *r = (const char *)memchr (p1, c, MIN (length, string_length));
       if (r == NULL)
 	{
-	  if (length <= string_length)
+	  if (length <= string_length + trailingnuls_length)
 	    {
 	      replace_call_with_value (gsi, build_int_cst (ptr_type_node, 0));
 	      return true;
diff --git a/gcc/testsuite/gcc.dg/builtin-memchr-4.c b/gcc/testsuite/gcc.dg/builtin-memchr-4.c
new file mode 100644
index 0000000..c37df60
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/builtin-memchr-4.c
@@ -0,0 +1,30 @@ 
+/* PR tree-optimization/89772
+   Verify that memchr calls with a pointer to a constant character
+   are folded as expected.
+   { dg-do compile }
+   { dg-options "-O1 -Wall -fdump-tree-gimple" } */
+
+typedef __SIZE_TYPE__  size_t;
+typedef __WCHAR_TYPE__ wchar_t;
+
+extern void* memchr (const void*, int, size_t);
+extern int printf (const char*, ...);
+extern void abort (void);
+
+#define A(expr)						\
+  ((expr)						\
+   ? (void)0						\
+   : (printf ("assertion failed on line %i: %s\n",	\
+	      __LINE__, #expr),				\
+      abort ()))
+
+const char a[8] = {'a',0,'b'};
+
+void test_memchr_cst_char (void)
+{
+  A (!memchr (a, 'c', 2));
+  A (!memchr (a, 'c', 5));
+  A (!memchr (a, 'c', sizeof a));
+}
+
+/* { dg-final { scan-tree-dump-not "abort" "gimple" } } */