On Mon, Jan 31, 2022 at 2:16 PM Tom de Vries <tdevr...@suse.de> wrote:
>
> On 9/17/21 10:08, Richard Biener via Gcc-patches wrote:
> > On Mon, Sep 13, 2021 at 4:53 PM Stefan Schulze Frielinghaus
> > <stefa...@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
> >>> <stefa...@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?
It is still valid - and yes, I think we need to guard it with this flag
but please do it in the caller to transform_reduction_loop.
>
> Thanks,
> - Tom
