Please review writeup for fixing PR 78809 (inline strcmp for small constant strings)

[Jeff Law]

On 11/03/2017 08:59 AM, Qing Zhao wrote:
> Hi, 
> 
> This is the first time I am asking for a design review for fixing a GCC enhancement request, Let me know if I need to send this email to other mailing list as well.
> 
> I have been studying PR 78809 for some time
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78809 <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78809>
> 
> with a lot of help from Wilco and other people, and detailed study about the previous discussion and current GCC behavior, I was able to come up with the following writeup
> (basically serve as a design doc), and ready for implementation. 
> 
> Please take a look at it, and let me know any comments and suggestions:
> 
> thanks a lot.
> 
> Qing
> 
> ========================================
> str(n)cmp and memcmp optimization in gcc
> -- A design document for PR78809
> 
> 11/01/2017
> 
> Qing Zhao
> ===========================================================
> 
> 0. Summary:
> 
>    For PR 78809 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78809,
>    Will add the following str(n)cmp and memcmp optimizations into GCC 8:
> 
>    A. for strncmp (s1, s2, n) 
>       if one of "s1" or "s2" is a constant string, "n" is a constant, and larger than the length of the constant string:
>       change strncmp (s1, s2, n) to strcmp (s1, s2);
Seems reasonable.  We could easily look at this as canonicalization.


> 
>    B. for strncmp (s1, s2, n) (!)= 0 or strcmp (s1, s2) (!)= 0
>       if the result is ONLY used to do a simple equality test against zero, one of "s1" or "s2" is a small constant string, n is a constant, and the other non-constant string is guaranteed to not read beyond the end of the string:
>       change strncmp (s1, s2, n) or strcmp (s1, s2) to corresponding memcmp (s1, s2, n); 
So how to you determine the non-constant string is long enough to avoid
reading past its end?  I guess you might get that from range
information.  But when it applies it seems reasoanble.  Again, this
could be considered a canonicalization step.


> 
>    C. for strcmp (s1, s2), strncmp (s1, s2, n), and memcmp (s1, s2, n)
>       if the result is NOT used to do simple equality test against zero, one of "s1" or "s2" is a small constant string, n is a constant, and the Min value of the length of the constant string and "n" is smaller than a predefined threshold T, 
>       inline the call by a byte-to-byte comparision sequence to avoid calling overhead. 
Also seems reasonable.


> 
>    A would like to be put in gimple fold phase (in routine "gimple_fold_builtin_string_compare" of gimple-fold.cOK.  Note that various optimizations can expose N or one of the strings
to be a constant.  So having it as part of the folders makes a lot of
sense .

>    B would like to be put in strlen phase (add new "handle_builtin_str(n)cmp" routines in tree-ssa-strlen.c)
Which is where you're most likely to have some kind of range information
which ISTM you need to prove the non-constant string is large enough
that you're not reading past its end.

>    C would like to be put in expand phase (tree-ssa-strlen.c or builtins.c): run-time performance testing is needed to decide the predefined threshold T. 
If you wanted to put it into expansion, I wouldn't object -- we could
always do experiments to see if there's any value in moving it early
(expansion to byte comparisons could possible expose other optimizations).

In general I like what you're suggesting.  And on a higher level I like
that we're looking to rationalize where these kinds of things happen
(compiler vs library).  It's something I've wanted to see happen for a
long time.


Jeff