Re: [RFC] ldist: Recognize rawmemchr loop patterns

[Tom de Vries <tdevries@suse.de>]

On 9/17/21 10:08, Richard Biener via Gcc-patches wrote:
> On Mon, Sep 13, 2021 at 4:53 PM Stefan Schulze Frielinghaus
> <stefansf@linux.ibm.com> wrote:
>>
>> On Mon, Sep 06, 2021 at 11:56:21AM +0200, Richard Biener wrote:
>>> On Fri, Sep 3, 2021 at 10:01 AM Stefan Schulze Frielinghaus
>>> <stefansf@linux.ibm.com> wrote:
>>>>
>>>> On Fri, Aug 20, 2021 at 12:35:58PM +0200, Richard Biener wrote:
>>>> [...]
>>>>>>>
>>>>>>> +  /* Handle strlen like loops.  */
>>>>>>> +  if (store_dr == NULL
>>>>>>> +      && integer_zerop (pattern)
>>>>>>> +      && TREE_CODE (reduction_iv.base) == INTEGER_CST
>>>>>>> +      && TREE_CODE (reduction_iv.step) == INTEGER_CST
>>>>>>> +      && integer_onep (reduction_iv.step)
>>>>>>> +      && (types_compatible_p (TREE_TYPE (reduction_var), size_type_node)
>>>>>>> +         || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (reduction_var))))
>>>>>>> +    {
>>>>>>>
>>>>>>> I wonder what goes wrong with a larger or smaller wrapping IV type?
>>>>>>> The iteration
>>>>>>> only stops when you load a NUL and the increments just wrap along (you're
>>>>>>> using the pointer IVs to compute the strlen result).  Can't you simply truncate?
>>>>>>
>>>>>> I think truncation is enough as long as no overflow occurs in strlen or
>>>>>> strlen_using_rawmemchr.
>>>>>>
>>>>>>> For larger than size_type_node (actually larger than ptr_type_node would matter
>>>>>>> I guess), the argument is that since pointer wrapping would be undefined anyway
>>>>>>> the IV cannot wrap either.  Now, the correct check here would IMHO be
>>>>>>>
>>>>>>>        TYPE_PRECISION (TREE_TYPE (reduction_var)) < TYPE_PRECISION
>>>>>>> (ptr_type_node)
>>>>>>>         || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (pointer-iv-var))
>>>>>>>
>>>>>>> ?
>>>>>>
>>>>>> Regarding the implementation which makes use of rawmemchr:
>>>>>>
>>>>>> We can count at most PTRDIFF_MAX many bytes without an overflow.  Thus,
>>>>>> the maximal length we can determine of a string where each character has
>>>>>> size S is PTRDIFF_MAX / S without an overflow.  Since an overflow for
>>>>>> ptrdiff type is undefined we have to make sure that if an overflow
>>>>>> occurs, then an overflow occurs for reduction variable, too, and that
>>>>>> this is undefined, too.  However, I'm not sure anymore whether we want
>>>>>> to respect overflows in all cases.  If TYPE_PRECISION (ptr_type_node)
>>>>>> equals TYPE_PRECISION (ptrdiff_type_node) and an overflow occurs, then
>>>>>> this would mean that a single string consumes more than half of the
>>>>>> virtual addressable memory.  At least for architectures where
>>>>>> TYPE_PRECISION (ptrdiff_type_node) == 64 holds, I think it is reasonable
>>>>>> to neglect the case where computing pointer difference may overflow.
>>>>>> Otherwise we are talking about strings with lenghts of multiple
>>>>>> pebibytes.  For other architectures we might have to be more precise
>>>>>> and make sure that reduction variable overflows first and that this is
>>>>>> undefined.
>>>>>>
>>>>>> Thus a conservative condition would be (I assumed that the size of any
>>>>>> integral type is a power of two which I'm not sure if this really holds;
>>>>>> IIRC the C standard requires only that the alignment is a power of two
>>>>>> but not necessarily the size so I might need to change this):
>>>>>>
>>>>>> /* Compute precision (reduction_var) < (precision (ptrdiff_type) - 1 - log2 (sizeof (load_type))
>>>>>>     or in other words return true if reduction variable overflows first
>>>>>>     and false otherwise.  */
>>>>>>
>>>>>> static bool
>>>>>> reduction_var_overflows_first (tree reduction_var, tree load_type)
>>>>>> {
>>>>>>    unsigned precision_ptrdiff = TYPE_PRECISION (ptrdiff_type_node);
>>>>>>    unsigned precision_reduction_var = TYPE_PRECISION (TREE_TYPE (reduction_var));
>>>>>>    unsigned size_exponent = wi::exact_log2 (wi::to_wide (TYPE_SIZE_UNIT (load_type)));
>>>>>>    return wi::ltu_p (precision_reduction_var, precision_ptrdiff - 1 - size_exponent);
>>>>>> }
>>>>>>
>>>>>> TYPE_PRECISION (ptrdiff_type_node) == 64
>>>>>> || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (reduction_var))
>>>>>>      && reduction_var_overflows_first (reduction_var, load_type)
>>>>>>
>>>>>> Regarding the implementation which makes use of strlen:
>>>>>>
>>>>>> I'm not sure what it means if strlen is called for a string with a
>>>>>> length greater than SIZE_MAX.  Therefore, similar to the implementation
>>>>>> using rawmemchr where we neglect the case of an overflow for 64bit
>>>>>> architectures, a conservative condition would be:
>>>>>>
>>>>>> TYPE_PRECISION (size_type_node) == 64
>>>>>> || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (reduction_var))
>>>>>>      && TYPE_PRECISION (reduction_var) <= TYPE_PRECISION (size_type_node))
>>>>>>
>>>>>> I still included the overflow undefined check for reduction variable in
>>>>>> order to rule out situations where the reduction variable is unsigned
>>>>>> and overflows as many times until strlen(,_using_rawmemchr) overflows,
>>>>>> too.  Maybe this is all theoretical nonsense but I'm afraid of uncommon
>>>>>> architectures.  Anyhow, while writing this down it becomes clear that
>>>>>> this deserves a comment which I will add once it becomes clear which way
>>>>>> to go.
>>>>>
>>>>> I think all the arguments about objects bigger than half of the address-space
>>>>> also are valid for 32bit targets and thus 32bit size_type_node (or
>>>>> 32bit pointer size).
>>>>> I'm not actually sure what's the canonical type to check against, whether
>>>>> it's size_type_node (Cs size_t), ptr_type_node (Cs void *) or sizetype (the
>>>>> middle-end "offset" type used for all address computations).  For weird reasons
>>>>> I'd lean towards 'sizetype' (for example some embedded targets have 24bit
>>>>> pointers but 16bit 'sizetype').
>>>>
>>>> Ok, for the strlen implementation I changed from size_type_node to
>>>> sizetype and assume that no overflow occurs for string objects bigger
>>>> than half of the address space for 32-bit targets and up:
>>>>
>>>>    (TYPE_PRECISION (sizetype) >= TYPE_PRECISION (ptr_type_node) - 1
>>>>     && TYPE_PRECISION (ptr_type_node) >= 32)
>>>>    || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (reduction_var))
>>>>        && TYPE_PRECISION (reduction_var) <= TYPE_PRECISION (sizetype))
>>>>
>>>> and similarly for the rawmemchr implementation:
>>>>
>>>>    (TYPE_PRECISION (ptrdiff_type_node) == TYPE_PRECISION (ptr_type_node)
>>>>     && TYPE_PRECISION (ptrdiff_type_node) >= 32)
>>>>    || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (reduction_var))
>>>>        && reduction_var_overflows_first (reduction_var, load_type))
>>>>
>>>>>
>>>>>>>
>>>>>>> +      if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (reduction_var)))
>>>>>>> +       {
>>>>>>> +         const char *msg = G_("assuming signed overflow does not occur "
>>>>>>> +                              "when optimizing strlen like loop");
>>>>>>> +         fold_overflow_warning (msg, WARN_STRICT_OVERFLOW_MISC);
>>>>>>> +       }
>>>>>>>
>>>>>>> no, please don't add any new strict-overflow warnings ;)
>>>>>>
>>>>>> I just stumbled over code which produces such a warning and thought this
>>>>>> is a hard requirement :D The new patch doesn't contain it anymore.
>>>>>>
>>>>>>>
>>>>>>> The generate_*_builtin routines need some factoring - if you code-generate
>>>>>>> into a gimple_seq you could use gimple_build () which would do the fold_stmt
>>>>>>> (not sure why you do that - you should see to fold the call, not necessarily
>>>>>>> the rest).  The replacement of reduction_var and the dumping could be shared.
>>>>>>> There's also GET_MODE_NAME for the printing.
>>>>>>
>>>>>> I wasn't really sure which way to go.  Use a gsi, as it is done by
>>>>>> existing generate_* functions, or make use of gimple_seq.  Since the
>>>>>> latter uses internally also gsi I thought it is better to stick to gsi
>>>>>> in the first place.  Now, after changing to gimple_seq I see the beauty
>>>>>> of it :)
>>>>>>
>>>>>> I created two helper functions generate_strlen_builtin_1 and
>>>>>> generate_reduction_builtin_1 in order to reduce code duplication.
>>>>>>
>>>>>> In function generate_strlen_builtin I changed from using
>>>>>> builtin_decl_implicit (BUILT_IN_STRLEN) to builtin_decl_explicit
>>>>>> (BUILT_IN_STRLEN) since the former could return a NULL pointer. I'm not
>>>>>> sure whether my intuition about the difference between implicit and
>>>>>> explicit builtins is correct.  In builtins.def there is a small example
>>>>>> given which I would paraphrase as "use builtin_decl_explicit if the
>>>>>> semantics of the builtin is defined by the C standard; otherwise use
>>>>>> builtin_decl_implicit" but probably my intuition is wrong?
>>>>>>
>>>>>> Beside that I'm not sure whether I really have to call
>>>>>> build_fold_addr_expr which looks superfluous to me since
>>>>>> gimple_build_call can deal with ADDR_EXPR as well as FUNCTION_DECL:
>>>>>>
>>>>>> tree fn = build_fold_addr_expr (builtin_decl_explicit (BUILT_IN_STRLEN));
>>>>>> gimple *fn_call = gimple_build_call (fn, 1, mem);
>>>>>>
>>>>>> However, since it is also used that way in the context of
>>>>>> generate_memset_builtin I didn't remove it so far.
>>>>>>
>>>>>>> I think overall the approach is sound now but the details still need work.
>>>>>>
>>>>>> Once again thank you very much for your review.  Really appreciated!
>>>>>
>>>>> The patch lacks a changelog entry / description.  It's nice if patches sent
>>>>> out for review are basically the rev as git format-patch produces.
>>>>>
>>>>> The rawmemchr optab needs documenting in md.texi
>>>>
>>>> While writing the documentation in md.texi I realised that other
>>>> instructions expect an address to be a memory operand which is not the
>>>> case for rawmemchr currently. At the moment the address is either an
>>>> SSA_NAME or ADDR_EXPR with a tree pointer type in expand_RAWMEMCHR. As a
>>>> consequence in the backend define_expand rawmemchr<mode> expects a
>>>> register operand and not a memory operand. Would it make sense to build
>>>> a MEM_REF out of SSA_NAME/ADDR_EXPR in expand_RAWMEMCHR? Not sure if
>>>> MEM_REF is supposed to be the canonical form here.
>>>
>>> I suppose the expander could use code similar to what
>>> expand_builtin_memset_args does,
>>> using get_memory_rtx.  I suppose that we're using MEM operands because those
>>> can convey things like alias info or alignment info, something which
>>> REG operands cannot
>>> (easily).  I wouldn't build a MEM_REF and try to expand that.
>>
>> The new patch contains the following changes:
>>
>> - In expand_RAWMEMCHR I'm using get_memory_rtx now.  This means I had to
>>    change linkage of get_memory_rtx to extern.
>>
>> - In function generate_strlen_builtin_using_rawmemchr I'm not
>>    reconstructing the load type anymore from the base pointer but rather
>>    pass it as a parameter from function transform_reduction_loop where we
>>    also ensured that it is of integral type.  Reconstructing the load
>>    type was error prone since e.g. I didn't distinct between
>>    pointer_plus_expr or addr_expr.  Thus passing the load type should be
>>    more solid.
>>
>> Regtested on IBM Z and x86.  Ok for mainline?
> 
> OK, and sorry for all the repeated delays.
> 

I'm running into PR56888 ( 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56888 ) on nvptx due to 
this, f.i. in gcc/testsuite/gcc.c-torture/execute/builtins/strlen.c, 
where gcc/testsuite/gcc.c-torture/execute/builtins/lib/strlen.c contains 
a strlen function, with a strlen loop, which is transformed by 
pass_loop_distribution into a __builtin_strlen, which is then expanded 
into a strlen call, creating a self-recursive function. [ And on nvptx, 
that happens to result in a compilation failure, which is how I found 
this. ]

According to this ( 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56888#c21 ) comment:
...
-fno-tree-loop-distribute-patterns is the reliable way to not
transform loops into library calls.
...

Then should we have something along the lines of:
...
$ git diff
diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 6fe59cd56855..9a211d30cd7e 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -3683,7 +3683,11 @@ loop_distribution::transform_reduction_loop
                && TYPE_PRECISION (ptr_type_node) >= 32)
               || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
                   && TYPE_PRECISION (reduction_var_type) <= 
TYPE_PRECISION (sizetype)))
-         && builtin_decl_implicit (BUILT_IN_STRLEN))
+         && builtin_decl_implicit (BUILT_IN_STRLEN)
+         && flag_tree_loop_distribute_patterns)
         generate_strlen_builtin (loop, reduction_var, load_iv.base,
                                  reduction_iv.base, loc);
        else if (direct_optab_handler (rawmemchr_optab, TYPE_MODE 
(load_type))
...
?

Or is the comment no longer valid?

Thanks,
- Tom