PR82665 - missing value range optimization for memchr

[Prathamesh Kulkarni]

On 2 January 2018 at 17:49, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Jan 02, 2018 at 05:39:17PM +0530, Prathamesh Kulkarni wrote:
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c
>> @@ -0,0 +1,22 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +void f1 (char *p, __SIZE_TYPE__ sz)
>> +{
>> +  char *q = __builtin_memchr (p, 0, sz);
>> +  long n = q - p;
>
> Please use __PTRDIFF_TYPE__ instead of long, here and in other spots.
>
>> --- a/gcc/vr-values.c
>> +++ b/gcc/vr-values.c
>> @@ -793,6 +793,42 @@ vr_values::extract_range_from_binary_expr (value_range *vr,
>>
>>    extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
>>
>> +  /* Set value_range for n in following sequence:
>> +     def = __builtin_memchr (arg, 0, sz)
>> +     n = def - arg
>> +     Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
>> +
>> +  if (vr->type == VR_VARYING
>> +      && (code == POINTER_DIFF_EXPR)
>> +      && (TREE_CODE (op0) == SSA_NAME)
>> +      && (TREE_CODE (op1) == SSA_NAME))
>
> Please drop the useless ()s around the comparisons.  They are needed
> only if the condition is multi-line and needed for emacs indentation,
> or around assignments tested as conditions.
>
>> +      gcall *call_stmt = NULL;
>> +      if (def && arg
>> +       && (TREE_CODE (def) == SSA_NAME)
>
> Likewise (many times).
>
>> +       && ((TREE_CODE (TREE_TYPE (def)) == POINTER_TYPE)
>> +           && (TREE_TYPE (TREE_TYPE (def)) == char_type_node))
>> +       && (TREE_CODE (arg) == SSA_NAME)
>> +       && ((TREE_CODE (TREE_TYPE (arg)) == POINTER_TYPE)
>> +           && (TREE_TYPE (TREE_TYPE (arg)) == char_type_node))
>
> What is so special about char_type_node?  Why e.g. unsigned char or signed
> char pointer shouldn't be handled the same?
>
>> +       && (call_stmt = dyn_cast<gcall *>(SSA_NAME_DEF_STMT (def)))
>> +       && (gimple_call_combined_fn (call_stmt) == CFN_BUILT_IN_MEMCHR)
>
> We don't have an ifn for memchr, so why this?  On the other side, it should
> be making sure one doesn't use unprototyped memchr with weirdo argument
> types, so you need gimple_call_builtin_p.
Hi Jakub,
Thanks for the review. I have tried to address your suggestions in the
attached patch.
Does it look OK ?
Validation in progress.

Thanks,
Prathamesh
>
>> +       && operand_equal_p (def, gimple_call_lhs (call_stmt), 0)
>> +       && operand_equal_p (arg, gimple_call_arg (call_stmt, 0), 0)
>> +       && integer_zerop (gimple_call_arg (call_stmt, 1)))
>> +         {
>> +           tree max = vrp_val_max (ptrdiff_type_node);
>> +           wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
>> +           tree range_min = build_zero_cst (expr_type);
>> +           tree range_max = wide_int_to_tree (expr_type, wmax - 1);
>> +           set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
>> +           return;
>> +         }
>> +     }
>> +
>>    /* Try harder for PLUS and MINUS if the range of one operand is symbolic
>>       and based on the other operand, for example if it was deduced from a
>>       symbolic comparison.  When a bound of the range of the first operand
>
>
>         Jakub
-------------- next part --------------
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c b/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c
new file mode 100644
index 00000000000..e42ca34cc61
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void f1 (char *p, __SIZE_TYPE__ sz)
+{
+  char *q = __builtin_memchr (p, 0, sz);
+  __PTRDIFF_TYPE__ n = q - p;
+
+  if (n >= __PTRDIFF_MAX__)
+    __builtin_abort ();
+}
+
+void f2 (unsigned char *p, __PTRDIFF_TYPE__ sz)
+{
+  unsigned char *q = __builtin_memchr (p, 0, sz);
+  __PTRDIFF_TYPE__ n = q - p;
+
+  if (n >= __PTRDIFF_MAX__)
+    __builtin_abort ();
+}
+
+void f3 (signed char *p, __PTRDIFF_TYPE__ sz)
+{
+  signed char *q = __builtin_memchr (p, 0, sz);
+  __PTRDIFF_TYPE__ n = q - p;
+
+  if (n >= __PTRDIFF_MAX__)
+    __builtin_abort ();
+}
+
+
+/* { dg-final { scan-tree-dump-not "memchr" 0 "optimized" } } */
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 794b4635f9e..2c93f92438a 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -793,6 +793,47 @@ vr_values::extract_range_from_binary_expr (value_range *vr,
 
   extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
 
+  /* Set value_range for n in following sequence:
+     def = __builtin_memchr (arg, 0, sz)
+     n = def - arg
+     Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */
+
+  if (vr->type == VR_VARYING
+      && code == POINTER_DIFF_EXPR
+      && TREE_CODE (op0) == SSA_NAME
+      && TREE_CODE (op1) == SSA_NAME)
+    {
+      tree def = op0;
+      tree arg = op1;
+      tree def_type, arg_type;
+
+      gcall *call_stmt = NULL;
+      if (def && arg
+	  && TREE_CODE (def) == SSA_NAME
+	  && TREE_CODE (TREE_TYPE (def)) == POINTER_TYPE
+	  && (def_type = TREE_TYPE (TREE_TYPE (def)))
+	  && (def_type == char_type_node || def_type == signed_char_type_node
+	      || def_type == unsigned_char_type_node)
+	  && TREE_CODE (arg) == SSA_NAME
+	  && TREE_CODE (TREE_TYPE (arg)) == POINTER_TYPE
+	  && (arg_type = TREE_TYPE (TREE_TYPE (arg)))
+	  && (arg_type == char_type_node || arg_type == signed_char_type_node
+	      || arg_type == unsigned_char_type_node)
+	  && (call_stmt = dyn_cast<gcall *>(SSA_NAME_DEF_STMT (def)))
+	  && gimple_call_builtin_p (call_stmt, BUILT_IN_MEMCHR)
+	  && operand_equal_p (def, gimple_call_lhs (call_stmt), 0)
+	  && operand_equal_p (arg, gimple_call_arg (call_stmt, 0), 0)
+	  && integer_zerop (gimple_call_arg (call_stmt, 1)))
+	    {
+	      tree max = vrp_val_max (ptrdiff_type_node);
+	      wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
+	      tree range_min = build_zero_cst (expr_type);
+	      tree range_max = wide_int_to_tree (expr_type, wmax - 1);
+	      set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
+	      return;
+	    }
+     }
+
   /* Try harder for PLUS and MINUS if the range of one operand is symbolic
      and based on the other operand, for example if it was deduced from a
      symbolic comparison.  When a bound of the range of the first operand