Convert strlen pass from evrp to ranger.

  The following patch converts the strlen pass from evrp to ranger,
leaving DOM as the last remaining user.

No additional cleanups have been done.  For example, the strlen pass
still has uses of VR_ANTI_RANGE, and the sprintf still passes around
pairs of integers instead of using a proper range.  Fixing this
could further improve these passes.

As a further enhancement, if the relevant maintainers deem useful,
the domwalk could be removed from strlen.  That is, unless the pass
needs it for something else.

With ranger we are now able to remove the range calculation from
before_dom_children entirely.  Just working with the ranger on-demand
catches all the strlen and sprintf testcases with the exception of
builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
code.  I have XFAILed the test and documented what the problem is.

It looks like the same problem in the sprintf test triggers a false
positive in gimple-ssa-warn-access.cc so I have added
-Wno-format-overflow until it can be fixed.

I can expand on the false positive if necessary, but the gist is that
this:

    _17 = strlen (_132);
    _18 = strlen (_136);
    _19 = _18 + _17;
    if (_19 > 75)
      goto <bb 59>; [0.00%]
    else
      goto <bb 61>; [100.00%]

...dominates the sprintf in BB61.  This means that ranger can figure
out that the _17 and _18 are [0, 75].  On the other hand, evrp
returned a range of [0, 9223372036854775805] which presumably the
sprintf code was ignoring as a false positive here:

	      char sizstr[80];
	      ...
	      ...
	      char *s1 = print_generic_expr_to_str (sizrng[1]);
	      gcc_checking_assert (strlen (s0) + strlen (s1)
				   < sizeof sizstr - 4);
	      sprintf (sizstr, "[%s, %s]", s0, s1);

The warning triggers with:

gimple-ssa-warn-access.cc: In member function ‘void {anonymous}::pass_waccess::maybe_check_access_sizes(rdwr_map*, tree, tree, gimple*)’:
gimple-ssa-warn-access.cc:2916:32: warning: ‘%s’ directive writing up to 75 bytes into a region of size between 2 and 77 [-Wformat-overflow=]
 2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
      |                                ^~~~~~~~~~
gimple-ssa-warn-access.cc:2916:23: note: ‘sprintf’ output between 5 and 155 bytes into a destination of size 80
 2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

On a positive note, these changes found two possible sprintf overflow
bugs in the C++ and Fortran front-ends which I have fixed below.

Bootstrap and regtested on x86-64 Linux.  I also ran it through our
callgrind harness and there was no overall change in overall
compilation time.

OK?

gcc/ChangeLog:

	* Makefile.in: Disable -Wformat-overflow for
	gimple-ssa-warn-access.o.
	* tree-ssa-strlen.c (compare_nonzero_chars): Pass statement
	context to ranger.
	(get_addr_stridx): Same.
	(get_stridx): Same.
	(get_range_strlen_dynamic): Same.
	(handle_builtin_strlen): Same.
	(handle_builtin_strchr): Same.
	(handle_builtin_strcpy): Same.
	(maybe_diag_stxncpy_trunc): Same.
	(handle_builtin_stxncpy_strncat):
	(handle_builtin_memcpy): Same.
	(handle_builtin_strcat): Same.
	(handle_alloc_call): Same.
	(handle_builtin_memset): Same.
	(handle_builtin_string_cmp): Same.
	(handle_pointer_plus): Same.
	(count_nonzero_bytes_addr): Same.
	(count_nonzero_bytes): Same.
	(handle_store): Same.
	(fold_strstr_to_strncmp): Same.
	(handle_integral_assign): Same.
	(check_and_optimize_stmt): Same.
	(class strlen_dom_walker): Replace evrp with ranger.
	(strlen_dom_walker::before_dom_children): Remove evrp.
	(strlen_dom_walker::after_dom_children): Remove evrp.

gcc/cp/ChangeLog:

	* ptree.c (cxx_print_xnode): Add more space to pfx array.

gcc/fortran/ChangeLog:

	* misc.c (gfc_dummy_typename): Make sure ts->kind is
	non-negative.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/builtin-sprintf-warn-22.c: XFAIL.
---
 gcc/Makefile.in                               |   1 +
 gcc/cp/ptree.c                                |   2 +-
 gcc/fortran/misc.c                            |   2 +-
 .../gcc.dg/tree-ssa/builtin-sprintf-warn-22.c |  13 +-
 gcc/tree-ssa-strlen.c                         | 145 ++++++++++--------
 5 files changed, 92 insertions(+), 71 deletions(-)
  

On 10/8/21 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> The following patch converts the strlen pass from evrp to ranger,
> leaving DOM as the last remaining user.

Thanks for doing this.  I know I said I'd work on it but I'm still
bogged down in my stage 1 work that's not going so great :(  I just
have a few minor comments/questions on the strlen change (inline)
but I am a bit concerned about the test failure.

> 
> No additional cleanups have been done.  For example, the strlen pass
> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> pairs of integers instead of using a proper range.  Fixing this
> could further improve these passes.
> 
> As a further enhancement, if the relevant maintainers deem useful,
> the domwalk could be removed from strlen.  That is, unless the pass
> needs it for something else.
> 
> With ranger we are now able to remove the range calculation from
> before_dom_children entirely.  Just working with the ranger on-demand
> catches all the strlen and sprintf testcases with the exception of
> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
> code.  I have XFAILed the test and documented what the problem is.

builtin-sprintf-warn-22.c is a regression test for a false positive
in Glibc.  If it fails we'll have to deal with the Glibc failure
again, which I would rather avoid.  Have you checked to see if
Glibc is affected by the change?

> 
> It looks like the same problem in the sprintf test triggers a false
> positive in gimple-ssa-warn-access.cc so I have added
> -Wno-format-overflow until it can be fixed.
> 
> I can expand on the false positive if necessary, but the gist is that
> this:
> 
>      _17 = strlen (_132);
>      _18 = strlen (_136);
>      _19 = _18 + _17;
>      if (_19 > 75)
>        goto <bb 59>; [0.00%]
>      else
>        goto <bb 61>; [100.00%]
> 
> ...dominates the sprintf in BB61.  This means that ranger can figure
> out that the _17 and _18 are [0, 75].  On the other hand, evrp
> returned a range of [0, 9223372036854775805] which presumably the
> sprintf code was ignoring as a false positive here:

This is a feature designed to avoid false positives when the sprintf
pass doesn't know anything about the strings (i.e., their lengths
are unconstrained by either the sizes of the arrays they're stored
in or any expressions like asserts involving their lengths).

It sounds like the strlen/ranger improvement partially propagates
constraints from subsequent expressions into the strlen results
but it doesn't go far enough for them to actually fully satisfy
the constraint, which is what in turn triggers the warning.

I.e., in the test:

void g (char *s1, char *s2)
{
   char b[1025];
   size_t n = __builtin_strlen (s1), d = __builtin_strlen (s2);
   if (n + d + 1 >= 1025)
     return;

   sprintf (b, "%s.%s", s1, s2); // { dg-bogus "\\\[-Wformat-overflow" }

the range of n and d is [0, INF] and so the sprintf call doesn't
trigger a warning.  With your change, because their range is
[0, 1023] each (and there's no way to express that their sum
is less than 1025), the warning triggers because it considers
the worst case scenario (the upper bounds of both).

> 
> 	      char sizstr[80];
> 	      ...
> 	      ...
> 	      char *s1 = print_generic_expr_to_str (sizrng[1]);
> 	      gcc_checking_assert (strlen (s0) + strlen (s1)
> 				   < sizeof sizstr - 4);
> 	      sprintf (sizstr, "[%s, %s]", s0, s1);
> 
> The warning triggers with:
> 
> gimple-ssa-warn-access.cc: In member function ‘void {anonymous}::pass_waccess::maybe_check_access_sizes(rdwr_map*, tree, tree, gimple*)’:
> gimple-ssa-warn-access.cc:2916:32: warning: ‘%s’ directive writing up to 75 bytes into a region of size between 2 and 77 [-Wformat-overflow=]
>   2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
>        |                                ^~~~~~~~~~
> gimple-ssa-warn-access.cc:2916:23: note: ‘sprintf’ output between 5 and 155 bytes into a destination of size 80
>   2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
>        |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 

Yes, that does look like the same problem.  It's a side-effect
of the checking_assert.  What's troubling is that it's one that
has exactly the opposite effect of what's intended: it causes
warnings when it's intended to avoid them, which was the main
goal of the strlen/sprintf integration.

Suppressing the warning in these cases, while technically simple,
would be a design change.  We might just have to live with this.
The asserts still work to constrain individual lenghts, they just
won't work for more complex expressions involving relationships
between two or more strings.

> On a positive note, these changes found two possible sprintf overflow
> bugs in the C++ and Fortran front-ends which I have fixed below.

That's good to hear! :)

> 
> Bootstrap and regtested on x86-64 Linux.  I also ran it through our
> callgrind harness and there was no overall change in overall
> compilation time.
> 
> OK?
> 
...
> @@ -269,7 +270,7 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
>       return -1;
>   
>     value_range vr;
> -  if (!rvals->range_of_expr (vr, si->nonzero_chars, si->stmt))
> +  if (!rvals->range_of_expr (vr, si->nonzero_chars, stmt))

We need stmt rather than si->stmt because the latter may be different
or null when the former will always refer to the current statement,
correct?

>       return -1;
>     value_range_kind rng = vr.kind ();
>     if (rng != VR_RANGE)
> @@ -324,7 +325,8 @@ get_next_strinfo (strinfo *si)
>      information.  */
>   
>   static int
> -get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
> +get_addr_stridx (tree exp, gimple *stmt,
> +		 tree ptr, unsigned HOST_WIDE_INT *offset_out,
>   		 range_query *rvals = NULL)

I think there still are quite a few calls to get_addr_stridx() and
get_addr() that don't pass in rvals.  I started doing this back in
the GCC 11 cycle but didn't finish the job.  Eventually, rvals
should be passed to all their callers (or they made class members
with a ranger member).  I mention this in case it has an effect on
the range propagation (since the pass also sets ranges).

>   {
>     HOST_WIDE_INT off;
...
> @@ -4653,7 +4662,7 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>   	       && TREE_CODE (si->nonzero_chars) == SSA_NAME)
>   	{
>   	  value_range vr;
> -	  rvals->range_of_expr (vr, si->nonzero_chars, si->stmt);
> +	  rvals->range_of_expr (vr, si->nonzero_chars, stmt);


Same question about si->stmt.  (Just making sure I understand.)

Thanks
Martin
  

On 10/8/21 12:51 PM, Martin Sebor via Gcc-patches wrote:
>
>
> I.e., in the test:
>
> void g (char *s1, char *s2)
> {
>   char b[1025];
>   size_t n = __builtin_strlen (s1), d = __builtin_strlen (s2);
>   if (n + d + 1 >= 1025)
>     return;
>
>   sprintf (b, "%s.%s", s1, s2); // { dg-bogus "\\\[-Wformat-overflow" }
>
> the range of n and d is [0, INF] and so the sprintf call doesn't
> trigger a warning.  With your change, because their range is
> [0, 1023] each (and there's no way to express that their sum
> is less than 1025), the warning triggers because it considers
> the worst case scenario (the upper bounds of both).
>
So the warning operates on the assumption that no info is OK, but 
improved information causes them to break because it can't figure out 
what to do with it?

Does this ever work when there is more than 1 string in the sprintf?  It 
seems that its the inherent lack of being able to associate an 
expression with a predicate that is the problem here.  If this is a 
single string, then an accurate  range should be able to come up with an 
accurate answer.  But as soon as there is a second string, this is bound 
to fail unless the strings are known to be 1/2 their size, and likewise 
if there were 3 strings, 1/3 their size...

Should we even be attempting to warn for multiple strings if we aren't 
going to be able to calculate them accurately? It seems like a recipe 
for a lot of false positives.   And then once we figure out how to 
combine the range info with the appropriate predicates, turn it back on?

Andrew
  

On 10/8/21 11:56 AM, Andrew MacLeod wrote:
> On 10/8/21 12:51 PM, Martin Sebor via Gcc-patches wrote:
>>
>>
>> I.e., in the test:
>>
>> void g (char *s1, char *s2)
>> {
>>   char b[1025];
>>   size_t n = __builtin_strlen (s1), d = __builtin_strlen (s2);
>>   if (n + d + 1 >= 1025)
>>     return;
>>
>>   sprintf (b, "%s.%s", s1, s2); // { dg-bogus "\\\[-Wformat-overflow" }
>>
>> the range of n and d is [0, INF] and so the sprintf call doesn't
>> trigger a warning.  With your change, because their range is
>> [0, 1023] each (and there's no way to express that their sum
>> is less than 1025), the warning triggers because it considers
>> the worst case scenario (the upper bounds of both).
>>
> So the warning operates on the assumption that no info is OK, but 
> improved information causes them to break because it can't figure out 
> what to do with it?

The idea is that input that appears unconstrained might have been
constrained somewhere else that we can't see, but constrained input
suggests it may not be constrained enough.   In the above, pointing
s1 and s2 at arrays same size as b, there's a decent chance that
the strings stored in them could be as long as fits (otherwise why
use such big arrays?) which would overflow the destination.

> 
> Does this ever work when there is more than 1 string in the sprintf?  It 
> seems that its the inherent lack of being able to associate an 
> expression with a predicate that is the problem here.  If this is a 
> single string, then an accurate  range should be able to come up with an 
> accurate answer.  But as soon as there is a second string, this is bound 
> to fail unless the strings are known to be 1/2 their size, and likewise 
> if there were 3 strings, 1/3 their size...

Right.  The logic is of course not bulletproof which is why we
integrated the sprintf pass with strlen: to get at the actual
string lengths when they're available instead of relying solely
on the worst case array size approximation.  (The array size
heuristic still applies when we don't have any strlen info.)
Even with the strlen info we don't get full accuracy because
the string lengths may be just lower bounds (e.g., as a result
of memcpy(a, "123", 3), strlen(a) no less than 3 but may be
as long as sizeof a - 1, and the warning uses the upper bound).

This, by the way, isn't just about strings.  It's the same for
numbers:

   sprintf (a, "%i %i", i, j);

will warn if i and j are in some constrained range whose upper
bound would result in overflowing a.

> 
> Should we even be attempting to warn for multiple strings if we aren't 
> going to be able to calculate them accurately? It seems like a recipe 
> for a lot of false positives.   And then once we figure out how to 
> combine the range info with the appropriate predicates, turn it back on?

It's been this way since the warning was introduced in GCC 7
and the false positives haven't been too bad (we have just
12 in Bugzilla).  Even with perfect ranges zero false positive
rate isn't achievable with the current design (or any design),
just like we can never come close to zero false negatives.

Every now and then it seems that a three level warning might
have been better than two, with level 1 using an even more
conservative approach.  But the most conservative approach is
next to useless: it would have to assume strings of length
zero (or one), all integers between 0 and 9, and floats have
few fractional digits.  That rarely happens.  It's all based
on judgment calls.

Martin
  

On Fri, Oct 8, 2021 at 6:52 PM Martin Sebor <msebor@gmail.com> wrote:
>
> On 10/8/21 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> > The following patch converts the strlen pass from evrp to ranger,
> > leaving DOM as the last remaining user.
>
> Thanks for doing this.  I know I said I'd work on it but I'm still
> bogged down in my stage 1 work that's not going so great :(  I just
> have a few minor comments/questions on the strlen change (inline)
> but I am a bit concerned about the test failure.
>
> >
> > No additional cleanups have been done.  For example, the strlen pass
> > still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> > pairs of integers instead of using a proper range.  Fixing this
> > could further improve these passes.
> >
> > As a further enhancement, if the relevant maintainers deem useful,
> > the domwalk could be removed from strlen.  That is, unless the pass
> > needs it for something else.
> >
> > With ranger we are now able to remove the range calculation from
> > before_dom_children entirely.  Just working with the ranger on-demand
> > catches all the strlen and sprintf testcases with the exception of
> > builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
> > code.  I have XFAILed the test and documented what the problem is.
>
> builtin-sprintf-warn-22.c is a regression test for a false positive
> in Glibc.  If it fails we'll have to deal with the Glibc failure
> again, which I would rather avoid.  Have you checked to see if
> Glibc is affected by the change?
>
> >
> > It looks like the same problem in the sprintf test triggers a false
> > positive in gimple-ssa-warn-access.cc so I have added
> > -Wno-format-overflow until it can be fixed.
> >
> > I can expand on the false positive if necessary, but the gist is that
> > this:
> >
> >      _17 = strlen (_132);
> >      _18 = strlen (_136);
> >      _19 = _18 + _17;
> >      if (_19 > 75)
> >        goto <bb 59>; [0.00%]
> >      else
> >        goto <bb 61>; [100.00%]
> >
> > ...dominates the sprintf in BB61.  This means that ranger can figure
> > out that the _17 and _18 are [0, 75].  On the other hand, evrp
> > returned a range of [0, 9223372036854775805] which presumably the
> > sprintf code was ignoring as a false positive here:
>
> This is a feature designed to avoid false positives when the sprintf
> pass doesn't know anything about the strings (i.e., their lengths
> are unconstrained by either the sizes of the arrays they're stored
> in or any expressions like asserts involving their lengths).
>
> It sounds like the strlen/ranger improvement partially propagates
> constraints from subsequent expressions into the strlen results
> but it doesn't go far enough for them to actually fully satisfy
> the constraint, which is what in turn triggers the warning.
>
> I.e., in the test:
>
> void g (char *s1, char *s2)
> {
>    char b[1025];
>    size_t n = __builtin_strlen (s1), d = __builtin_strlen (s2);
>    if (n + d + 1 >= 1025)
>      return;
>
>    sprintf (b, "%s.%s", s1, s2); // { dg-bogus "\\\[-Wformat-overflow" }
>
> the range of n and d is [0, INF] and so the sprintf call doesn't
> trigger a warning.  With your change, because their range is
> [0, 1023] each (and there's no way to express that their sum
> is less than 1025), the warning triggers because it considers
> the worst case scenario (the upper bounds of both).

I agree with Andrew.  If this doesn't work with more than 1 string we
shouldn't even attempt it, as it's bound to be riddled with false
positives, which you'll get more of with enhanced ranges at this
point.

> > @@ -269,7 +270,7 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
> >       return -1;
> >
> >     value_range vr;
> > -  if (!rvals->range_of_expr (vr, si->nonzero_chars, si->stmt))
> > +  if (!rvals->range_of_expr (vr, si->nonzero_chars, stmt))
>
> We need stmt rather than si->stmt because the latter may be different
> or null when the former will always refer to the current statement,
> correct?

Yes.

> I think there still are quite a few calls to get_addr_stridx() and
> get_addr() that don't pass in rvals.  I started doing this back in
> the GCC 11 cycle but didn't finish the job.  Eventually, rvals
> should be passed to all their callers (or they made class members
> with a ranger member).  I mention this in case it has an effect on
> the range propagation (since the pass also sets ranges).

Definitely.  You'll get even better ranges, though perhaps more false
positives as discussed above :-/.

Aldy
  

On 10/9/21 9:04 AM, Aldy Hernandez wrote:
> On Fri, Oct 8, 2021 at 6:52 PM Martin Sebor <msebor@gmail.com> wrote:
>>
>> On 10/8/21 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>> The following patch converts the strlen pass from evrp to ranger,
>>> leaving DOM as the last remaining user.
>>
>> Thanks for doing this.  I know I said I'd work on it but I'm still
>> bogged down in my stage 1 work that's not going so great :(  I just
>> have a few minor comments/questions on the strlen change (inline)
>> but I am a bit concerned about the test failure.
>>
>>>
>>> No additional cleanups have been done.  For example, the strlen pass
>>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
>>> pairs of integers instead of using a proper range.  Fixing this
>>> could further improve these passes.
>>>
>>> As a further enhancement, if the relevant maintainers deem useful,
>>> the domwalk could be removed from strlen.  That is, unless the pass
>>> needs it for something else.
>>>
>>> With ranger we are now able to remove the range calculation from
>>> before_dom_children entirely.  Just working with the ranger on-demand
>>> catches all the strlen and sprintf testcases with the exception of
>>> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
>>> code.  I have XFAILed the test and documented what the problem is.
>>
>> builtin-sprintf-warn-22.c is a regression test for a false positive
>> in Glibc.  If it fails we'll have to deal with the Glibc failure
>> again, which I would rather avoid.  Have you checked to see if
>> Glibc is affected by the change?

Have you tested Glibc with the patch to see if the warning comes
back?  If it does there are other ways to suppress it, and I can
take care of it.  I just want us to avoid reintroducing it without
doing our due diligence first.

...
>> I think there still are quite a few calls to get_addr_stridx() and
>> get_addr() that don't pass in rvals.  I started doing this back in
>> the GCC 11 cycle but didn't finish the job.  Eventually, rvals
>> should be passed to all their callers (or they made class members
>> with a ranger member).  I mention this in case it has an effect on
>> the range propagation (since the pass also sets ranges).
> 
> Definitely.  You'll get even better ranges, though perhaps more false
> positives as discussed above :-/.

We want better ranges and better analysis.  Ultimately, it will
lead to better quality warnings, as has been one of the goals
behind Ranger.  If along the way it means a few false positives
in some edge cases, we'll deal with them.  I don't see this one
as a significant problem.

Martin
  

On 10/9/21 10:19 AM, Martin Sebor wrote:
> On 10/9/21 9:04 AM, Aldy Hernandez wrote:
>> On Fri, Oct 8, 2021 at 6:52 PM Martin Sebor <msebor@gmail.com> wrote:
>>>
>>> On 10/8/21 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>>> The following patch converts the strlen pass from evrp to ranger,
>>>> leaving DOM as the last remaining user.
>>>
>>> Thanks for doing this.  I know I said I'd work on it but I'm still
>>> bogged down in my stage 1 work that's not going so great :(  I just
>>> have a few minor comments/questions on the strlen change (inline)
>>> but I am a bit concerned about the test failure.
>>>
>>>>
>>>> No additional cleanups have been done.  For example, the strlen pass
>>>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
>>>> pairs of integers instead of using a proper range.  Fixing this
>>>> could further improve these passes.
>>>>
>>>> As a further enhancement, if the relevant maintainers deem useful,
>>>> the domwalk could be removed from strlen.  That is, unless the pass
>>>> needs it for something else.
>>>>
>>>> With ranger we are now able to remove the range calculation from
>>>> before_dom_children entirely.  Just working with the ranger on-demand
>>>> catches all the strlen and sprintf testcases with the exception of
>>>> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
>>>> code.  I have XFAILed the test and documented what the problem is.
>>>
>>> builtin-sprintf-warn-22.c is a regression test for a false positive
>>> in Glibc.  If it fails we'll have to deal with the Glibc failure
>>> again, which I would rather avoid.  Have you checked to see if
>>> Glibc is affected by the change?
> 
> Have you tested Glibc with the patch to see if the warning comes
> back?  If it does there are other ways to suppress it, and I can
> take care of it.  I just want us to avoid reintroducing it without
> doing our due diligence first.

I've built Glibc with the latest GCC and your patch applied and
the warning is back so we'll need to suppress it there.  I opened
Glibc bug 28439 and will submit a patch for it:

   https://sourceware.org/bugzilla/show_bug.cgi?id=28439

There are other Glibc warnings to deal with so I don't think your
patch needs to wait until this one is resolved.

I also missed the following in your patch:

 > gcc/ChangeLog:
 >
 > 	* Makefile.in: Disable -Wformat-overflow for
 > 	gimple-ssa-warn-access.o.

Rather than disabling the warning for the whole file (or any
others), unless suppressing it in the code is overly intrusive,
doing it that way is preferable.  For %s sprintf directives,
specifying precision can be used to constrain the output.  In
this case where each %s output is the result of formatting
an (at most) 64-bit integer, we know that the length of each
%s argument is at most 21 bytes, so specifying a precision as
big as 37 should both make sure the output fits and avoid
the warning.  I.e., this should (and in my tests does) work:

	      char *s1 = print_generic_expr_to_str (sizrng[1]);
	      sprintf (sizstr, "[%.37s, %.37s]", s0, s1);
	      free (s1);

Thanks
Martin

> ...
>>> I think there still are quite a few calls to get_addr_stridx() and
>>> get_addr() that don't pass in rvals.  I started doing this back in
>>> the GCC 11 cycle but didn't finish the job.  Eventually, rvals
>>> should be passed to all their callers (or they made class members
>>> with a ranger member).  I mention this in case it has an effect on
>>> the range propagation (since the pass also sets ranges).
>>
>> Definitely.  You'll get even better ranges, though perhaps more false
>> positives as discussed above :-/.
> 
> We want better ranges and better analysis.  Ultimately, it will
> lead to better quality warnings, as has been one of the goals
> behind Ranger.  If along the way it means a few false positives
> in some edge cases, we'll deal with them.  I don't see this one
> as a significant problem.
> 
> Martin
  

We seem to be passing a lot of context around in the strlen code.  I
certainly don't want to contribute to more.

Most of the handle_* functions are passing the gsi as well as either
ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
of that in the strlen pass object (well, the dom walker object, but we
can rename it to be less dom centric)?

Something like the attached (untested) patch could be the basis for
further cleanups.

Jakub, would this line of work interest you?

Aldy

On Fri, Oct 8, 2021 at 5:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> The following patch converts the strlen pass from evrp to ranger,
> leaving DOM as the last remaining user.
>
> No additional cleanups have been done.  For example, the strlen pass
> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> pairs of integers instead of using a proper range.  Fixing this
> could further improve these passes.
>
> As a further enhancement, if the relevant maintainers deem useful,
> the domwalk could be removed from strlen.  That is, unless the pass
> needs it for something else.
>
> With ranger we are now able to remove the range calculation from
> before_dom_children entirely.  Just working with the ranger on-demand
> catches all the strlen and sprintf testcases with the exception of
> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
> code.  I have XFAILed the test and documented what the problem is.
>
> It looks like the same problem in the sprintf test triggers a false
> positive in gimple-ssa-warn-access.cc so I have added
> -Wno-format-overflow until it can be fixed.
>
> I can expand on the false positive if necessary, but the gist is that
> this:
>
>     _17 = strlen (_132);
>     _18 = strlen (_136);
>     _19 = _18 + _17;
>     if (_19 > 75)
>       goto <bb 59>; [0.00%]
>     else
>       goto <bb 61>; [100.00%]
>
> ...dominates the sprintf in BB61.  This means that ranger can figure
> out that the _17 and _18 are [0, 75].  On the other hand, evrp
> returned a range of [0, 9223372036854775805] which presumably the
> sprintf code was ignoring as a false positive here:
>
>               char sizstr[80];
>               ...
>               ...
>               char *s1 = print_generic_expr_to_str (sizrng[1]);
>               gcc_checking_assert (strlen (s0) + strlen (s1)
>                                    < sizeof sizstr - 4);
>               sprintf (sizstr, "[%s, %s]", s0, s1);
>
> The warning triggers with:
>
> gimple-ssa-warn-access.cc: In member function ‘void {anonymous}::pass_waccess::maybe_check_access_sizes(rdwr_map*, tree, tree, gimple*)’:
> gimple-ssa-warn-access.cc:2916:32: warning: ‘%s’ directive writing up to 75 bytes into a region of size between 2 and 77 [-Wformat-overflow=]
>  2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
>       |                                ^~~~~~~~~~
> gimple-ssa-warn-access.cc:2916:23: note: ‘sprintf’ output between 5 and 155 bytes into a destination of size 80
>  2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
>       |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> On a positive note, these changes found two possible sprintf overflow
> bugs in the C++ and Fortran front-ends which I have fixed below.
>
> Bootstrap and regtested on x86-64 Linux.  I also ran it through our
> callgrind harness and there was no overall change in overall
> compilation time.
>
> OK?
>
> gcc/ChangeLog:
>
>         * Makefile.in: Disable -Wformat-overflow for
>         gimple-ssa-warn-access.o.
>         * tree-ssa-strlen.c (compare_nonzero_chars): Pass statement
>         context to ranger.
>         (get_addr_stridx): Same.
>         (get_stridx): Same.
>         (get_range_strlen_dynamic): Same.
>         (handle_builtin_strlen): Same.
>         (handle_builtin_strchr): Same.
>         (handle_builtin_strcpy): Same.
>         (maybe_diag_stxncpy_trunc): Same.
>         (handle_builtin_stxncpy_strncat):
>         (handle_builtin_memcpy): Same.
>         (handle_builtin_strcat): Same.
>         (handle_alloc_call): Same.
>         (handle_builtin_memset): Same.
>         (handle_builtin_string_cmp): Same.
>         (handle_pointer_plus): Same.
>         (count_nonzero_bytes_addr): Same.
>         (count_nonzero_bytes): Same.
>         (handle_store): Same.
>         (fold_strstr_to_strncmp): Same.
>         (handle_integral_assign): Same.
>         (check_and_optimize_stmt): Same.
>         (class strlen_dom_walker): Replace evrp with ranger.
>         (strlen_dom_walker::before_dom_children): Remove evrp.
>         (strlen_dom_walker::after_dom_children): Remove evrp.
>
> gcc/cp/ChangeLog:
>
>         * ptree.c (cxx_print_xnode): Add more space to pfx array.
>
> gcc/fortran/ChangeLog:
>
>         * misc.c (gfc_dummy_typename): Make sure ts->kind is
>         non-negative.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/builtin-sprintf-warn-22.c: XFAIL.
> ---
>  gcc/Makefile.in                               |   1 +
>  gcc/cp/ptree.c                                |   2 +-
>  gcc/fortran/misc.c                            |   2 +-
>  .../gcc.dg/tree-ssa/builtin-sprintf-warn-22.c |  13 +-
>  gcc/tree-ssa-strlen.c                         | 145 ++++++++++--------
>  5 files changed, 92 insertions(+), 71 deletions(-)
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index f36ffa4740b..dfd2a40e80a 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -222,6 +222,7 @@ libgcov-merge-tool.o-warn = -Wno-error
>  gimple-match.o-warn = -Wno-unused
>  generic-match.o-warn = -Wno-unused
>  dfp.o-warn = -Wno-strict-aliasing
> +gimple-ssa-warn-access.o-warn = -Wno-format-overflow
>
>  # All warnings have to be shut off in stage1 if the compiler used then
>  # isn't gcc; configure determines that.  WARN_CFLAGS will be either
> diff --git a/gcc/cp/ptree.c b/gcc/cp/ptree.c
> index 1dcd764af01..ca7884db39b 100644
> --- a/gcc/cp/ptree.c
> +++ b/gcc/cp/ptree.c
> @@ -292,7 +292,7 @@ cxx_print_xnode (FILE *file, tree node, int indent)
>         for (unsigned ix = 0; ix != len; ix++)
>           {
>             binding_cluster *cluster = &BINDING_VECTOR_CLUSTER (node, ix);
> -           char pfx[24];
> +           char pfx[32];
>             for (unsigned jx = 0; jx != BINDING_VECTOR_SLOTS_PER_CLUSTER; jx++)
>               if (cluster->indices[jx].span)
>                 {
> diff --git a/gcc/fortran/misc.c b/gcc/fortran/misc.c
> index 3d449ae17fe..c1520307c90 100644
> --- a/gcc/fortran/misc.c
> +++ b/gcc/fortran/misc.c
> @@ -284,7 +284,7 @@ gfc_dummy_typename (gfc_typespec *ts)
>         {
>           if (ts->kind == gfc_default_character_kind)
>             sprintf(buffer, "CHARACTER(*)");
> -         else if (ts->kind < 10)
> +         else if (ts->kind >= 0 && ts->kind < 10)
>             sprintf(buffer, "CHARACTER(*,%d)", ts->kind);
>           else
>             sprintf(buffer, "CHARACTER(*,?)");
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c
> index 685a4fd8c89..82eb5851c59 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c
> @@ -18,7 +18,18 @@ void g (char *s1, char *s2)
>    if (n + d + 1 >= 1025)
>      return;
>
> -  sprintf (b, "%s.%s", s1, s2);     // { dg-bogus "\\\[-Wformat-overflow" }
> +  /* Ranger can find ranges here:
> +     [1] n_6: size_t [0, 1023]
> +     [2] d_8: size_t [0, 1023]
> +
> +     Whereas evrp can't really:
> +     [1] n_6: size_t [0, 9223372036854775805]
> +     [2] d_8: size_t [0, 9223372036854775805]
> +
> +     This is causing the sprintf warning pass to issue a false
> +     positive here.  */
> +
> +  sprintf (b, "%s.%s", s1, s2);     // { dg-bogus "\\\[-Wformat-overflow" "" { xfail *-*-* } }
>
>    f (b);
>  }
> diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
> index 7c568a42d49..df0c2d5ee7a 100644
> --- a/gcc/tree-ssa-strlen.c
> +++ b/gcc/tree-ssa-strlen.c
> @@ -59,7 +59,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-ssa-loop.h"
>  #include "tree-scalar-evolution.h"
>  #include "vr-values.h"
> -#include "gimple-ssa-evrp-analyze.h"
> +#include "gimple-range.h"
>  #include "tree-ssa.h"
>
>  /* A vector indexed by SSA_NAME_VERSION.  0 means unknown, positive value
> @@ -256,7 +256,8 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
>     Uses RVALS to determine length range.  */
>
>  static int
> -compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
> +compare_nonzero_chars (strinfo *si, gimple *stmt,
> +                      unsigned HOST_WIDE_INT off,
>                        range_query *rvals)
>  {
>    if (!si->nonzero_chars)
> @@ -269,7 +270,7 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
>      return -1;
>
>    value_range vr;
> -  if (!rvals->range_of_expr (vr, si->nonzero_chars, si->stmt))
> +  if (!rvals->range_of_expr (vr, si->nonzero_chars, stmt))
>      return -1;
>    value_range_kind rng = vr.kind ();
>    if (rng != VR_RANGE)
> @@ -324,7 +325,8 @@ get_next_strinfo (strinfo *si)
>     information.  */
>
>  static int
> -get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
> +get_addr_stridx (tree exp, gimple *stmt,
> +                tree ptr, unsigned HOST_WIDE_INT *offset_out,
>                  range_query *rvals = NULL)
>  {
>    HOST_WIDE_INT off;
> @@ -363,7 +365,7 @@ get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
>        unsigned HOST_WIDE_INT rel_off
>         = (unsigned HOST_WIDE_INT) off - last->offset;
>        strinfo *si = get_strinfo (last->idx);
> -      if (si && compare_nonzero_chars (si, rel_off, rvals) >= 0)
> +      if (si && compare_nonzero_chars (si, stmt, rel_off, rvals) >= 0)
>         {
>           if (offset_out)
>             {
> @@ -385,7 +387,8 @@ get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
>     When nonnull, uses RVALS to determine range information.  */
>
>  static int
> -get_stridx (tree exp, wide_int offrng[2] = NULL, range_query *rvals = NULL)
> +get_stridx (tree exp, gimple *stmt,
> +           wide_int offrng[2] = NULL, range_query *rvals = NULL)
>  {
>    if (offrng)
>      offrng[0] = offrng[1] = wi::zero (TYPE_PRECISION (ptrdiff_type_node));
> @@ -522,7 +525,7 @@ get_stridx (tree exp, wide_int offrng[2] = NULL, range_query *rvals = NULL)
>
>    if (TREE_CODE (exp) == ADDR_EXPR)
>      {
> -      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp, NULL);
> +      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), stmt, exp, NULL);
>        if (idx != 0)
>         return idx;
>      }
> @@ -1016,7 +1019,7 @@ get_range_strlen_dynamic (tree src, gimple *stmt,
>                           c_strlen_data *pdata, bitmap *visited,
>                           range_query *rvals, unsigned *pssa_def_max)
>  {
> -  int idx = get_stridx (src);
> +  int idx = get_stridx (src, stmt);
>    if (!idx)
>      {
>        if (TREE_CODE (src) == SSA_NAME)
> @@ -2124,7 +2127,7 @@ handle_builtin_strlen (gimple_stmt_iterator *gsi)
>    tree src = gimple_call_arg (stmt, 0);
>    tree bound = (DECL_FUNCTION_CODE (callee) == BUILT_IN_STRNLEN
>                 ? gimple_call_arg (stmt, 1) : NULL_TREE);
> -  int idx = get_stridx (src);
> +  int idx = get_stridx (src, stmt);
>    if (idx || (bound && integer_zerop (bound)))
>      {
>        strinfo *si = NULL;
> @@ -2304,7 +2307,7 @@ handle_builtin_strchr (gimple_stmt_iterator *gsi)
>    if (!check_nul_terminated_array (NULL_TREE, src))
>      return;
>
> -  int idx = get_stridx (src);
> +  int idx = get_stridx (src, stmt);
>    if (idx)
>      {
>        strinfo *si = NULL;
> @@ -2411,12 +2414,12 @@ handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>    src = gimple_call_arg (stmt, 1);
>    dst = gimple_call_arg (stmt, 0);
>    lhs = gimple_call_lhs (stmt);
> -  idx = get_stridx (src);
> +  idx = get_stridx (src, stmt);
>    si = NULL;
>    if (idx > 0)
>      si = get_strinfo (idx);
>
> -  didx = get_stridx (dst);
> +  didx = get_stridx (dst, stmt);
>    olddsi = NULL;
>    oldlen = NULL_TREE;
>    if (didx > 0)
> @@ -2818,7 +2821,7 @@ maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt,
>       when ssa_ver_to_stridx is empty.  That implies the caller isn't
>       running under the control of this pass and ssa_ver_to_stridx hasn't
>       been created yet.  */
> -  int sidx = ssa_ver_to_stridx.length () ? get_stridx (src) : 0;
> +  int sidx = ssa_ver_to_stridx.length () ? get_stridx (src, stmt) : 0;
>    if (sidx < 0 && wi::gtu_p (cntrange[0], ~sidx))
>      return false;
>
> @@ -3092,7 +3095,7 @@ handle_builtin_stxncpy_strncat (bool append_p, gimple_stmt_iterator *gsi)
>       a lower bound).  */
>    tree dstlenp1 = NULL_TREE, srclenp1 = NULL_TREE;;
>
> -  int didx = get_stridx (dst);
> +  int didx = get_stridx (dst, stmt);
>    if (strinfo *sidst = didx > 0 ? get_strinfo (didx) : NULL)
>      {
>        /* Compute the size of the destination string including the nul
> @@ -3118,7 +3121,7 @@ handle_builtin_stxncpy_strncat (bool append_p, gimple_stmt_iterator *gsi)
>        dst = sidst->ptr;
>      }
>
> -  int sidx = get_stridx (src);
> +  int sidx = get_stridx (src, stmt);
>    strinfo *sisrc = sidx > 0 ? get_strinfo (sidx) : NULL;
>    if (sisrc)
>      {
> @@ -3228,7 +3231,7 @@ handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>    tree src = gimple_call_arg (stmt, 1);
>    tree dst = gimple_call_arg (stmt, 0);
>
> -  int didx = get_stridx (dst);
> +  int didx = get_stridx (dst, stmt);
>    strinfo *olddsi = NULL;
>    if (didx > 0)
>      olddsi = get_strinfo (didx);
> @@ -3242,7 +3245,7 @@ handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>        adjust_last_stmt (olddsi, stmt, false, ptr_qry);
>      }
>
> -  int idx = get_stridx (src);
> +  int idx = get_stridx (src, stmt);
>    if (idx == 0)
>      return;
>
> @@ -3418,7 +3421,7 @@ handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>
>    tree lhs = gimple_call_lhs (stmt);
>
> -  didx = get_stridx (dst);
> +  didx = get_stridx (dst, stmt);
>    if (didx < 0)
>      return;
>
> @@ -3428,7 +3431,7 @@ handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>
>    srclen = NULL_TREE;
>    si = NULL;
> -  idx = get_stridx (src);
> +  idx = get_stridx (src, stmt);
>    if (idx < 0)
>      srclen = build_int_cst (size_type_node, ~idx);
>    else if (idx > 0)
> @@ -3650,7 +3653,7 @@ handle_alloc_call (enum built_in_function bcode, gimple_stmt_iterator *gsi)
>    if (lhs == NULL_TREE)
>      return;
>
> -  gcc_assert (get_stridx (lhs) == 0);
> +  gcc_assert (get_stridx (lhs, stmt) == 0);
>    int idx = new_stridx (lhs);
>    tree length = NULL_TREE;
>    if (bcode == BUILT_IN_CALLOC)
> @@ -3687,7 +3690,7 @@ handle_builtin_memset (gimple_stmt_iterator *gsi, bool *zero_write,
>    tree ptr = gimple_call_arg (memset_stmt, 0);
>    /* Set to the non-constant offset added to PTR.  */
>    wide_int offrng[2];
> -  int idx1 = get_stridx (ptr, offrng, ptr_qry.rvals);
> +  int idx1 = get_stridx (ptr, memset_stmt, offrng, ptr_qry.rvals);
>    if (idx1 <= 0)
>      return false;
>    strinfo *si1 = get_strinfo (idx1);
> @@ -4178,8 +4181,8 @@ handle_builtin_string_cmp (gimple_stmt_iterator *gsi, range_query *rvals)
>
>    tree arg1 = gimple_call_arg (stmt, 0);
>    tree arg2 = gimple_call_arg (stmt, 1);
> -  int idx1 = get_stridx (arg1);
> -  int idx2 = get_stridx (arg2);
> +  int idx1 = get_stridx (arg1, stmt);
> +  int idx2 = get_stridx (arg2, stmt);
>
>    /* For strncmp set to the value of the third argument if known.  */
>    HOST_WIDE_INT bound = -1;
> @@ -4318,7 +4321,7 @@ handle_pointer_plus (gimple_stmt_iterator *gsi)
>  {
>    gimple *stmt = gsi_stmt (*gsi);
>    tree lhs = gimple_assign_lhs (stmt), off;
> -  int idx = get_stridx (gimple_assign_rhs1 (stmt));
> +  int idx = get_stridx (gimple_assign_rhs1 (stmt), stmt);
>    strinfo *si, *zsi;
>
>    if (idx == 0)
> @@ -4396,7 +4399,8 @@ nonzero_bytes_for_type (tree type, unsigned lenrange[3],
>  }
>
>  static bool
> -count_nonzero_bytes_addr (tree, unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
> +count_nonzero_bytes_addr (tree, gimple *stmt,
> +                         unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
>                           unsigned [3], bool *, bool *, bool *,
>                           range_query *, ssa_name_limit_t &);
>
> @@ -4416,7 +4420,8 @@ count_nonzero_bytes_addr (tree, unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
>     Returns true on success and false otherwise.  */
>
>  static bool
> -count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
> +count_nonzero_bytes (tree exp, gimple *stmt,
> +                    unsigned HOST_WIDE_INT offset,
>                      unsigned HOST_WIDE_INT nbytes,
>                      unsigned lenrange[3], bool *nulterm,
>                      bool *allnul, bool *allnonnul, range_query *rvals,
> @@ -4435,7 +4440,8 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>              exact value is not known) recurse once to set the range
>              for an arbitrary constant.  */
>           exp = build_int_cst (type, 1);
> -         return count_nonzero_bytes (exp, offset, 1, lenrange,
> +         return count_nonzero_bytes (exp, stmt,
> +                                     offset, 1, lenrange,
>                                       nulterm, allnul, allnonnul, rvals, snlim);
>         }
>
> @@ -4462,7 +4468,8 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>           for (unsigned i = 0; i != n; i++)
>             {
>               tree def = gimple_phi_arg_def (stmt, i);
> -             if (!count_nonzero_bytes (def, offset, nbytes, lenrange, nulterm,
> +             if (!count_nonzero_bytes (def, stmt,
> +                                       offset, nbytes, lenrange, nulterm,
>                                         allnul, allnonnul, rvals, snlim))
>                 return false;
>             }
> @@ -4519,7 +4526,8 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>         return false;
>
>        /* Handle MEM_REF = SSA_NAME types of assignments.  */
> -      return count_nonzero_bytes_addr (arg, offset, nbytes, lenrange, nulterm,
> +      return count_nonzero_bytes_addr (arg, stmt,
> +                                      offset, nbytes, lenrange, nulterm,
>                                        allnul, allnonnul, rvals, snlim);
>      }
>
> @@ -4631,13 +4639,14 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>     bytes that are pointed to by EXP, which should be a pointer.  */
>
>  static bool
> -count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
> +count_nonzero_bytes_addr (tree exp, gimple *stmt,
> +                         unsigned HOST_WIDE_INT offset,
>                           unsigned HOST_WIDE_INT nbytes,
>                           unsigned lenrange[3], bool *nulterm,
>                           bool *allnul, bool *allnonnul,
>                           range_query *rvals, ssa_name_limit_t &snlim)
>  {
> -  int idx = get_stridx (exp);
> +  int idx = get_stridx (exp, stmt);
>    if (idx > 0)
>      {
>        strinfo *si = get_strinfo (idx);
> @@ -4653,7 +4662,7 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>                && TREE_CODE (si->nonzero_chars) == SSA_NAME)
>         {
>           value_range vr;
> -         rvals->range_of_expr (vr, si->nonzero_chars, si->stmt);
> +         rvals->range_of_expr (vr, si->nonzero_chars, stmt);
>           if (vr.kind () != VR_RANGE)
>             return false;
>
> @@ -4699,7 +4708,8 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>      }
>
>    if (TREE_CODE (exp) == ADDR_EXPR)
> -    return count_nonzero_bytes (TREE_OPERAND (exp, 0), offset, nbytes,
> +    return count_nonzero_bytes (TREE_OPERAND (exp, 0), stmt,
> +                               offset, nbytes,
>                                 lenrange, nulterm, allnul, allnonnul, rvals,
>                                 snlim);
>
> @@ -4719,7 +4729,8 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>           for (unsigned i = 0; i != n; i++)
>             {
>               tree def = gimple_phi_arg_def (stmt, i);
> -             if (!count_nonzero_bytes_addr (def, offset, nbytes, lenrange,
> +             if (!count_nonzero_bytes_addr (def, stmt,
> +                                            offset, nbytes, lenrange,
>                                              nulterm, allnul, allnonnul, rvals,
>                                              snlim))
>                 return false;
> @@ -4747,7 +4758,8 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>     (the results of strlen).  */
>
>  static bool
> -count_nonzero_bytes (tree expr_or_type, unsigned lenrange[3], bool *nulterm,
> +count_nonzero_bytes (tree expr_or_type, gimple *stmt,
> +                    unsigned lenrange[3], bool *nulterm,
>                      bool *allnul, bool *allnonnul, range_query *rvals)
>  {
>    if (TYPE_P (expr_or_type))
> @@ -4765,7 +4777,8 @@ count_nonzero_bytes (tree expr_or_type, unsigned lenrange[3], bool *nulterm,
>
>    ssa_name_limit_t snlim;
>    tree expr = expr_or_type;
> -  return count_nonzero_bytes (expr, 0, 0, lenrange, nulterm, allnul, allnonnul,
> +  return count_nonzero_bytes (expr, stmt,
> +                             0, 0, lenrange, nulterm, allnul, allnonnul,
>                               rvals, snlim);
>  }
>
> @@ -4818,18 +4831,19 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>              least OFFSET nonzero characters.  This is trivially true if
>              OFFSET is zero.  */
>           offset = tree_to_uhwi (mem_offset);
> -         idx = get_stridx (TREE_OPERAND (lhs, 0));
> +         idx = get_stridx (TREE_OPERAND (lhs, 0), stmt);
>           if (idx > 0)
>             si = get_strinfo (idx);
>           if (offset == 0)
>             ssaname = TREE_OPERAND (lhs, 0);
> -         else if (si == NULL || compare_nonzero_chars (si, offset, rvals) < 0)
> +         else if (si == NULL
> +                  || compare_nonzero_chars (si, stmt, offset, rvals) < 0)
>             {
>               *zero_write = rhs ? initializer_zerop (rhs) : false;
>
>               bool dummy;
>               unsigned lenrange[] = { UINT_MAX, 0, 0 };
> -             if (count_nonzero_bytes (rhs ? rhs : storetype, lenrange,
> +             if (count_nonzero_bytes (rhs ? rhs : storetype, stmt, lenrange,
>                                        &dummy, &dummy, &dummy, rvals))
>                 maybe_warn_overflow (stmt, true, lenrange[2], ptr_qry);
>
> @@ -4839,7 +4853,7 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>      }
>    else
>      {
> -      idx = get_addr_stridx (lhs, NULL_TREE, &offset, rvals);
> +      idx = get_addr_stridx (lhs, stmt, NULL_TREE, &offset, rvals);
>        if (idx > 0)
>         si = get_strinfo (idx);
>      }
> @@ -4862,7 +4876,8 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>    bool full_string_p;
>
>    const bool ranges_valid
> -    = count_nonzero_bytes (rhs ? rhs : storetype, lenrange, &full_string_p,
> +    = count_nonzero_bytes (rhs ? rhs : storetype, stmt,
> +                          lenrange, &full_string_p,
>                            &storing_all_zeros_p, &storing_all_nonzero_p,
>                            rvals);
>
> @@ -4895,15 +4910,18 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>         {
>           /* The offset of the last stored byte.  */
>           unsigned HOST_WIDE_INT endoff = offset + lenrange[2] - 1;
> -         store_before_nul[0] = compare_nonzero_chars (si, offset, rvals);
> +         store_before_nul[0]
> +           = compare_nonzero_chars (si, stmt, offset, rvals);
>           if (endoff == offset)
>             store_before_nul[1] = store_before_nul[0];
>           else
> -           store_before_nul[1] = compare_nonzero_chars (si, endoff, rvals);
> +           store_before_nul[1]
> +             = compare_nonzero_chars (si, stmt, endoff, rvals);
>         }
>        else
>         {
> -         store_before_nul[0] = compare_nonzero_chars (si, offset, rvals);
> +         store_before_nul[0]
> +           = compare_nonzero_chars (si, stmt, offset, rvals);
>           store_before_nul[1] = store_before_nul[0];
>           gcc_assert (offset == 0 || store_before_nul[0] >= 0);
>         }
> @@ -5128,7 +5146,7 @@ fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple *stmt)
>         {
>           tree arg1 = gimple_call_arg (call_stmt, 1);
>           tree arg1_len = NULL_TREE;
> -         int idx = get_stridx (arg1);
> +         int idx = get_stridx (arg1, call_stmt);
>
>           if (idx)
>             {
> @@ -5342,7 +5360,7 @@ handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>        tree rhs1 = gimple_assign_rhs1 (stmt);
>        if (code == MEM_REF)
>         {
> -         idx = get_stridx (TREE_OPERAND (rhs1, 0));
> +         idx = get_stridx (TREE_OPERAND (rhs1, 0), stmt);
>           if (idx > 0)
>             {
>               strinfo *si = get_strinfo (idx);
> @@ -5359,7 +5377,7 @@ handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>             }
>         }
>        if (idx <= 0)
> -       idx = get_addr_stridx (rhs1, NULL_TREE, &coff);
> +       idx = get_addr_stridx (rhs1, stmt, NULL_TREE, &coff);
>        if (idx > 0)
>         {
>           strinfo *si = get_strinfo (idx);
> @@ -5421,7 +5439,8 @@ handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>           unsigned lenrange[] = { UINT_MAX, 0, 0 };
>           tree rhs = gimple_assign_rhs1 (stmt);
>           const bool ranges_valid
> -           = count_nonzero_bytes (rhs, lenrange, &full_string_p,
> +           = count_nonzero_bytes (rhs, stmt,
> +                                  lenrange, &full_string_p,
>                                    &storing_all_zeros_p, &storing_all_nonzero_p,
>                                    rvals);
>           if (ranges_valid)
> @@ -5520,7 +5539,7 @@ check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>               || (gimple_assign_cast_p (stmt)
>                   && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
>             {
> -             int idx = get_stridx (gimple_assign_rhs1 (stmt));
> +             int idx = get_stridx (gimple_assign_rhs1 (stmt), stmt);
>               ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
>             }
>           else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
> @@ -5602,20 +5621,20 @@ class strlen_dom_walker : public dom_walker
>  public:
>    strlen_dom_walker (cdi_direction direction)
>      : dom_walker (direction),
> -    evrp (false),
> -    ptr_qry (&evrp, &var_cache),
> -    var_cache (),
> -    m_cleanup_cfg (false)
> -  { }
> +      ptr_qry (&m_ranger, &var_cache),
> +      var_cache (),
> +      m_cleanup_cfg (false)
> +  {
> +  }
>
>    ~strlen_dom_walker ();
>
>    virtual edge before_dom_children (basic_block);
>    virtual void after_dom_children (basic_block);
>
> -  /* EVRP analyzer used for printf argument range processing, and
> +  /* Ranger used for printf argument range processing, and
>       to track strlen results across integer variable assignments.  */
> -  evrp_range_analyzer evrp;
> +  gimple_ranger m_ranger;
>
>    /* A pointer_query object and its cache to store information about
>       pointers and their targets in.  */
> @@ -5640,8 +5659,6 @@ strlen_dom_walker::~strlen_dom_walker ()
>  edge
>  strlen_dom_walker::before_dom_children (basic_block bb)
>  {
> -  evrp.enter (bb);
> -
>    basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
>
>    if (dombb == NULL)
> @@ -5698,12 +5715,12 @@ strlen_dom_walker::before_dom_children (basic_block bb)
>        tree result = gimple_phi_result (phi);
>        if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
>         {
> -         int idx = get_stridx (gimple_phi_arg_def (phi, 0));
> +         int idx = get_stridx (gimple_phi_arg_def (phi, 0), phi);
>           if (idx != 0)
>             {
>               unsigned int i, n = gimple_phi_num_args (phi);
>               for (i = 1; i < n; i++)
> -               if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
> +               if (idx != get_stridx (gimple_phi_arg_def (phi, i), phi))
>                   break;
>               if (i == n)
>                 ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
> @@ -5716,12 +5733,6 @@ strlen_dom_walker::before_dom_children (basic_block bb)
>    /* Attempt to optimize individual statements.  */
>    for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
>      {
> -      gimple *stmt = gsi_stmt (gsi);
> -
> -      /* First record ranges generated by this statement so they
> -        can be used by printf argument processing.  */
> -      evrp.record_ranges_from_stmt (stmt, false);
> -
>        /* Reset search depth preformance counter.  */
>        ptr_qry.depth = 0;
>
> @@ -5744,8 +5755,6 @@ strlen_dom_walker::before_dom_children (basic_block bb)
>  void
>  strlen_dom_walker::after_dom_children (basic_block bb)
>  {
> -  evrp.leave (bb);
> -
>    if (bb->aux)
>      {
>        stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) bb->aux);
> --
> 2.31.1
>
  

On Sat, Oct 9, 2021 at 7:59 PM Martin Sebor <msebor@gmail.com> wrote:
>
> On 10/9/21 10:19 AM, Martin Sebor wrote:
> > On 10/9/21 9:04 AM, Aldy Hernandez wrote:
> >> On Fri, Oct 8, 2021 at 6:52 PM Martin Sebor <msebor@gmail.com> wrote:
> >>>
> >>> On 10/8/21 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> >>>> The following patch converts the strlen pass from evrp to ranger,
> >>>> leaving DOM as the last remaining user.
> >>>
> >>> Thanks for doing this.  I know I said I'd work on it but I'm still
> >>> bogged down in my stage 1 work that's not going so great :(  I just
> >>> have a few minor comments/questions on the strlen change (inline)
> >>> but I am a bit concerned about the test failure.
> >>>
> >>>>
> >>>> No additional cleanups have been done.  For example, the strlen pass
> >>>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> >>>> pairs of integers instead of using a proper range.  Fixing this
> >>>> could further improve these passes.
> >>>>
> >>>> As a further enhancement, if the relevant maintainers deem useful,
> >>>> the domwalk could be removed from strlen.  That is, unless the pass
> >>>> needs it for something else.
> >>>>
> >>>> With ranger we are now able to remove the range calculation from
> >>>> before_dom_children entirely.  Just working with the ranger on-demand
> >>>> catches all the strlen and sprintf testcases with the exception of
> >>>> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
> >>>> code.  I have XFAILed the test and documented what the problem is.
> >>>
> >>> builtin-sprintf-warn-22.c is a regression test for a false positive
> >>> in Glibc.  If it fails we'll have to deal with the Glibc failure
> >>> again, which I would rather avoid.  Have you checked to see if
> >>> Glibc is affected by the change?
> >
> > Have you tested Glibc with the patch to see if the warning comes
> > back?  If it does there are other ways to suppress it, and I can
> > take care of it.  I just want us to avoid reintroducing it without
> > doing our due diligence first.
>
> I've built Glibc with the latest GCC and your patch applied and
> the warning is back so we'll need to suppress it there.  I opened
> Glibc bug 28439 and will submit a patch for it:
>
>    https://sourceware.org/bugzilla/show_bug.cgi?id=28439

The above patch rewrites the sprintf call into a pair of strcpy.  This
seems like a burdensome thing to ask of our users to silence a false
positive, but I leave it to the glibc experts to opine.

>
> There are other Glibc warnings to deal with so I don't think your
> patch needs to wait until this one is resolved.
>
> I also missed the following in your patch:
>
>  > gcc/ChangeLog:
>  >
>  >      * Makefile.in: Disable -Wformat-overflow for
>  >      gimple-ssa-warn-access.o.
>
> Rather than disabling the warning for the whole file (or any
> others), unless suppressing it in the code is overly intrusive,
> doing it that way is preferable.  For %s sprintf directives,
> specifying precision can be used to constrain the output.  In
> this case where each %s output is the result of formatting
> an (at most) 64-bit integer, we know that the length of each
> %s argument is at most 21 bytes, so specifying a precision as
> big as 37 should both make sure the output fits and avoid
> the warning.  I.e., this should (and in my tests does) work:
>
>               char *s1 = print_generic_expr_to_str (sizrng[1]);
>               sprintf (sizstr, "[%.37s, %.37s]", s0, s1);
>               free (s1);

Thanks.  I've tweaked the patch accordingly.

Aldy
  

On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
> We seem to be passing a lot of context around in the strlen code.  I
> certainly don't want to contribute to more.
> 
> Most of the handle_* functions are passing the gsi as well as either
> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
> of that in the strlen pass object (well, the dom walker object, but we
> can rename it to be less dom centric)?
> 
> Something like the attached (untested) patch could be the basis for
> further cleanups.
> 
> Jakub, would this line of work interest you?

You didn't ask me but since no one spoke up against it let me add
some encouragement: this is exactly what I was envisioning and in
line with other such modernization we have been doing elsewhere.
Could you please submit it for review?

Martin

> 
> Aldy
> 
> On Fri, Oct 8, 2021 at 5:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> The following patch converts the strlen pass from evrp to ranger,
>> leaving DOM as the last remaining user.
>>
>> No additional cleanups have been done.  For example, the strlen pass
>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
>> pairs of integers instead of using a proper range.  Fixing this
>> could further improve these passes.
>>
>> As a further enhancement, if the relevant maintainers deem useful,
>> the domwalk could be removed from strlen.  That is, unless the pass
>> needs it for something else.
>>
>> With ranger we are now able to remove the range calculation from
>> before_dom_children entirely.  Just working with the ranger on-demand
>> catches all the strlen and sprintf testcases with the exception of
>> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
>> code.  I have XFAILed the test and documented what the problem is.
>>
>> It looks like the same problem in the sprintf test triggers a false
>> positive in gimple-ssa-warn-access.cc so I have added
>> -Wno-format-overflow until it can be fixed.
>>
>> I can expand on the false positive if necessary, but the gist is that
>> this:
>>
>>      _17 = strlen (_132);
>>      _18 = strlen (_136);
>>      _19 = _18 + _17;
>>      if (_19 > 75)
>>        goto <bb 59>; [0.00%]
>>      else
>>        goto <bb 61>; [100.00%]
>>
>> ...dominates the sprintf in BB61.  This means that ranger can figure
>> out that the _17 and _18 are [0, 75].  On the other hand, evrp
>> returned a range of [0, 9223372036854775805] which presumably the
>> sprintf code was ignoring as a false positive here:
>>
>>                char sizstr[80];
>>                ...
>>                ...
>>                char *s1 = print_generic_expr_to_str (sizrng[1]);
>>                gcc_checking_assert (strlen (s0) + strlen (s1)
>>                                     < sizeof sizstr - 4);
>>                sprintf (sizstr, "[%s, %s]", s0, s1);
>>
>> The warning triggers with:
>>
>> gimple-ssa-warn-access.cc: In member function ‘void {anonymous}::pass_waccess::maybe_check_access_sizes(rdwr_map*, tree, tree, gimple*)’:
>> gimple-ssa-warn-access.cc:2916:32: warning: ‘%s’ directive writing up to 75 bytes into a region of size between 2 and 77 [-Wformat-overflow=]
>>   2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
>>        |                                ^~~~~~~~~~
>> gimple-ssa-warn-access.cc:2916:23: note: ‘sprintf’ output between 5 and 155 bytes into a destination of size 80
>>   2916 |               sprintf (sizstr, "[%s, %s]", s0, s1);
>>        |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>
>> On a positive note, these changes found two possible sprintf overflow
>> bugs in the C++ and Fortran front-ends which I have fixed below.
>>
>> Bootstrap and regtested on x86-64 Linux.  I also ran it through our
>> callgrind harness and there was no overall change in overall
>> compilation time.
>>
>> OK?
>>
>> gcc/ChangeLog:
>>
>>          * Makefile.in: Disable -Wformat-overflow for
>>          gimple-ssa-warn-access.o.
>>          * tree-ssa-strlen.c (compare_nonzero_chars): Pass statement
>>          context to ranger.
>>          (get_addr_stridx): Same.
>>          (get_stridx): Same.
>>          (get_range_strlen_dynamic): Same.
>>          (handle_builtin_strlen): Same.
>>          (handle_builtin_strchr): Same.
>>          (handle_builtin_strcpy): Same.
>>          (maybe_diag_stxncpy_trunc): Same.
>>          (handle_builtin_stxncpy_strncat):
>>          (handle_builtin_memcpy): Same.
>>          (handle_builtin_strcat): Same.
>>          (handle_alloc_call): Same.
>>          (handle_builtin_memset): Same.
>>          (handle_builtin_string_cmp): Same.
>>          (handle_pointer_plus): Same.
>>          (count_nonzero_bytes_addr): Same.
>>          (count_nonzero_bytes): Same.
>>          (handle_store): Same.
>>          (fold_strstr_to_strncmp): Same.
>>          (handle_integral_assign): Same.
>>          (check_and_optimize_stmt): Same.
>>          (class strlen_dom_walker): Replace evrp with ranger.
>>          (strlen_dom_walker::before_dom_children): Remove evrp.
>>          (strlen_dom_walker::after_dom_children): Remove evrp.
>>
>> gcc/cp/ChangeLog:
>>
>>          * ptree.c (cxx_print_xnode): Add more space to pfx array.
>>
>> gcc/fortran/ChangeLog:
>>
>>          * misc.c (gfc_dummy_typename): Make sure ts->kind is
>>          non-negative.
>>
>> gcc/testsuite/ChangeLog:
>>
>>          * gcc.dg/tree-ssa/builtin-sprintf-warn-22.c: XFAIL.
>> ---
>>   gcc/Makefile.in                               |   1 +
>>   gcc/cp/ptree.c                                |   2 +-
>>   gcc/fortran/misc.c                            |   2 +-
>>   .../gcc.dg/tree-ssa/builtin-sprintf-warn-22.c |  13 +-
>>   gcc/tree-ssa-strlen.c                         | 145 ++++++++++--------
>>   5 files changed, 92 insertions(+), 71 deletions(-)
>>
>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>> index f36ffa4740b..dfd2a40e80a 100644
>> --- a/gcc/Makefile.in
>> +++ b/gcc/Makefile.in
>> @@ -222,6 +222,7 @@ libgcov-merge-tool.o-warn = -Wno-error
>>   gimple-match.o-warn = -Wno-unused
>>   generic-match.o-warn = -Wno-unused
>>   dfp.o-warn = -Wno-strict-aliasing
>> +gimple-ssa-warn-access.o-warn = -Wno-format-overflow
>>
>>   # All warnings have to be shut off in stage1 if the compiler used then
>>   # isn't gcc; configure determines that.  WARN_CFLAGS will be either
>> diff --git a/gcc/cp/ptree.c b/gcc/cp/ptree.c
>> index 1dcd764af01..ca7884db39b 100644
>> --- a/gcc/cp/ptree.c
>> +++ b/gcc/cp/ptree.c
>> @@ -292,7 +292,7 @@ cxx_print_xnode (FILE *file, tree node, int indent)
>>          for (unsigned ix = 0; ix != len; ix++)
>>            {
>>              binding_cluster *cluster = &BINDING_VECTOR_CLUSTER (node, ix);
>> -           char pfx[24];
>> +           char pfx[32];
>>              for (unsigned jx = 0; jx != BINDING_VECTOR_SLOTS_PER_CLUSTER; jx++)
>>                if (cluster->indices[jx].span)
>>                  {
>> diff --git a/gcc/fortran/misc.c b/gcc/fortran/misc.c
>> index 3d449ae17fe..c1520307c90 100644
>> --- a/gcc/fortran/misc.c
>> +++ b/gcc/fortran/misc.c
>> @@ -284,7 +284,7 @@ gfc_dummy_typename (gfc_typespec *ts)
>>          {
>>            if (ts->kind == gfc_default_character_kind)
>>              sprintf(buffer, "CHARACTER(*)");
>> -         else if (ts->kind < 10)
>> +         else if (ts->kind >= 0 && ts->kind < 10)
>>              sprintf(buffer, "CHARACTER(*,%d)", ts->kind);
>>            else
>>              sprintf(buffer, "CHARACTER(*,?)");
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c
>> index 685a4fd8c89..82eb5851c59 100644
>> --- a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-22.c
>> @@ -18,7 +18,18 @@ void g (char *s1, char *s2)
>>     if (n + d + 1 >= 1025)
>>       return;
>>
>> -  sprintf (b, "%s.%s", s1, s2);     // { dg-bogus "\\\[-Wformat-overflow" }
>> +  /* Ranger can find ranges here:
>> +     [1] n_6: size_t [0, 1023]
>> +     [2] d_8: size_t [0, 1023]
>> +
>> +     Whereas evrp can't really:
>> +     [1] n_6: size_t [0, 9223372036854775805]
>> +     [2] d_8: size_t [0, 9223372036854775805]
>> +
>> +     This is causing the sprintf warning pass to issue a false
>> +     positive here.  */
>> +
>> +  sprintf (b, "%s.%s", s1, s2);     // { dg-bogus "\\\[-Wformat-overflow" "" { xfail *-*-* } }
>>
>>     f (b);
>>   }
>> diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
>> index 7c568a42d49..df0c2d5ee7a 100644
>> --- a/gcc/tree-ssa-strlen.c
>> +++ b/gcc/tree-ssa-strlen.c
>> @@ -59,7 +59,7 @@ along with GCC; see the file COPYING3.  If not see
>>   #include "tree-ssa-loop.h"
>>   #include "tree-scalar-evolution.h"
>>   #include "vr-values.h"
>> -#include "gimple-ssa-evrp-analyze.h"
>> +#include "gimple-range.h"
>>   #include "tree-ssa.h"
>>
>>   /* A vector indexed by SSA_NAME_VERSION.  0 means unknown, positive value
>> @@ -256,7 +256,8 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
>>      Uses RVALS to determine length range.  */
>>
>>   static int
>> -compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
>> +compare_nonzero_chars (strinfo *si, gimple *stmt,
>> +                      unsigned HOST_WIDE_INT off,
>>                         range_query *rvals)
>>   {
>>     if (!si->nonzero_chars)
>> @@ -269,7 +270,7 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
>>       return -1;
>>
>>     value_range vr;
>> -  if (!rvals->range_of_expr (vr, si->nonzero_chars, si->stmt))
>> +  if (!rvals->range_of_expr (vr, si->nonzero_chars, stmt))
>>       return -1;
>>     value_range_kind rng = vr.kind ();
>>     if (rng != VR_RANGE)
>> @@ -324,7 +325,8 @@ get_next_strinfo (strinfo *si)
>>      information.  */
>>
>>   static int
>> -get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
>> +get_addr_stridx (tree exp, gimple *stmt,
>> +                tree ptr, unsigned HOST_WIDE_INT *offset_out,
>>                   range_query *rvals = NULL)
>>   {
>>     HOST_WIDE_INT off;
>> @@ -363,7 +365,7 @@ get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
>>         unsigned HOST_WIDE_INT rel_off
>>          = (unsigned HOST_WIDE_INT) off - last->offset;
>>         strinfo *si = get_strinfo (last->idx);
>> -      if (si && compare_nonzero_chars (si, rel_off, rvals) >= 0)
>> +      if (si && compare_nonzero_chars (si, stmt, rel_off, rvals) >= 0)
>>          {
>>            if (offset_out)
>>              {
>> @@ -385,7 +387,8 @@ get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out,
>>      When nonnull, uses RVALS to determine range information.  */
>>
>>   static int
>> -get_stridx (tree exp, wide_int offrng[2] = NULL, range_query *rvals = NULL)
>> +get_stridx (tree exp, gimple *stmt,
>> +           wide_int offrng[2] = NULL, range_query *rvals = NULL)
>>   {
>>     if (offrng)
>>       offrng[0] = offrng[1] = wi::zero (TYPE_PRECISION (ptrdiff_type_node));
>> @@ -522,7 +525,7 @@ get_stridx (tree exp, wide_int offrng[2] = NULL, range_query *rvals = NULL)
>>
>>     if (TREE_CODE (exp) == ADDR_EXPR)
>>       {
>> -      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp, NULL);
>> +      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), stmt, exp, NULL);
>>         if (idx != 0)
>>          return idx;
>>       }
>> @@ -1016,7 +1019,7 @@ get_range_strlen_dynamic (tree src, gimple *stmt,
>>                            c_strlen_data *pdata, bitmap *visited,
>>                            range_query *rvals, unsigned *pssa_def_max)
>>   {
>> -  int idx = get_stridx (src);
>> +  int idx = get_stridx (src, stmt);
>>     if (!idx)
>>       {
>>         if (TREE_CODE (src) == SSA_NAME)
>> @@ -2124,7 +2127,7 @@ handle_builtin_strlen (gimple_stmt_iterator *gsi)
>>     tree src = gimple_call_arg (stmt, 0);
>>     tree bound = (DECL_FUNCTION_CODE (callee) == BUILT_IN_STRNLEN
>>                  ? gimple_call_arg (stmt, 1) : NULL_TREE);
>> -  int idx = get_stridx (src);
>> +  int idx = get_stridx (src, stmt);
>>     if (idx || (bound && integer_zerop (bound)))
>>       {
>>         strinfo *si = NULL;
>> @@ -2304,7 +2307,7 @@ handle_builtin_strchr (gimple_stmt_iterator *gsi)
>>     if (!check_nul_terminated_array (NULL_TREE, src))
>>       return;
>>
>> -  int idx = get_stridx (src);
>> +  int idx = get_stridx (src, stmt);
>>     if (idx)
>>       {
>>         strinfo *si = NULL;
>> @@ -2411,12 +2414,12 @@ handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>>     src = gimple_call_arg (stmt, 1);
>>     dst = gimple_call_arg (stmt, 0);
>>     lhs = gimple_call_lhs (stmt);
>> -  idx = get_stridx (src);
>> +  idx = get_stridx (src, stmt);
>>     si = NULL;
>>     if (idx > 0)
>>       si = get_strinfo (idx);
>>
>> -  didx = get_stridx (dst);
>> +  didx = get_stridx (dst, stmt);
>>     olddsi = NULL;
>>     oldlen = NULL_TREE;
>>     if (didx > 0)
>> @@ -2818,7 +2821,7 @@ maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt,
>>        when ssa_ver_to_stridx is empty.  That implies the caller isn't
>>        running under the control of this pass and ssa_ver_to_stridx hasn't
>>        been created yet.  */
>> -  int sidx = ssa_ver_to_stridx.length () ? get_stridx (src) : 0;
>> +  int sidx = ssa_ver_to_stridx.length () ? get_stridx (src, stmt) : 0;
>>     if (sidx < 0 && wi::gtu_p (cntrange[0], ~sidx))
>>       return false;
>>
>> @@ -3092,7 +3095,7 @@ handle_builtin_stxncpy_strncat (bool append_p, gimple_stmt_iterator *gsi)
>>        a lower bound).  */
>>     tree dstlenp1 = NULL_TREE, srclenp1 = NULL_TREE;;
>>
>> -  int didx = get_stridx (dst);
>> +  int didx = get_stridx (dst, stmt);
>>     if (strinfo *sidst = didx > 0 ? get_strinfo (didx) : NULL)
>>       {
>>         /* Compute the size of the destination string including the nul
>> @@ -3118,7 +3121,7 @@ handle_builtin_stxncpy_strncat (bool append_p, gimple_stmt_iterator *gsi)
>>         dst = sidst->ptr;
>>       }
>>
>> -  int sidx = get_stridx (src);
>> +  int sidx = get_stridx (src, stmt);
>>     strinfo *sisrc = sidx > 0 ? get_strinfo (sidx) : NULL;
>>     if (sisrc)
>>       {
>> @@ -3228,7 +3231,7 @@ handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>>     tree src = gimple_call_arg (stmt, 1);
>>     tree dst = gimple_call_arg (stmt, 0);
>>
>> -  int didx = get_stridx (dst);
>> +  int didx = get_stridx (dst, stmt);
>>     strinfo *olddsi = NULL;
>>     if (didx > 0)
>>       olddsi = get_strinfo (didx);
>> @@ -3242,7 +3245,7 @@ handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>>         adjust_last_stmt (olddsi, stmt, false, ptr_qry);
>>       }
>>
>> -  int idx = get_stridx (src);
>> +  int idx = get_stridx (src, stmt);
>>     if (idx == 0)
>>       return;
>>
>> @@ -3418,7 +3421,7 @@ handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>>
>>     tree lhs = gimple_call_lhs (stmt);
>>
>> -  didx = get_stridx (dst);
>> +  didx = get_stridx (dst, stmt);
>>     if (didx < 0)
>>       return;
>>
>> @@ -3428,7 +3431,7 @@ handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi,
>>
>>     srclen = NULL_TREE;
>>     si = NULL;
>> -  idx = get_stridx (src);
>> +  idx = get_stridx (src, stmt);
>>     if (idx < 0)
>>       srclen = build_int_cst (size_type_node, ~idx);
>>     else if (idx > 0)
>> @@ -3650,7 +3653,7 @@ handle_alloc_call (enum built_in_function bcode, gimple_stmt_iterator *gsi)
>>     if (lhs == NULL_TREE)
>>       return;
>>
>> -  gcc_assert (get_stridx (lhs) == 0);
>> +  gcc_assert (get_stridx (lhs, stmt) == 0);
>>     int idx = new_stridx (lhs);
>>     tree length = NULL_TREE;
>>     if (bcode == BUILT_IN_CALLOC)
>> @@ -3687,7 +3690,7 @@ handle_builtin_memset (gimple_stmt_iterator *gsi, bool *zero_write,
>>     tree ptr = gimple_call_arg (memset_stmt, 0);
>>     /* Set to the non-constant offset added to PTR.  */
>>     wide_int offrng[2];
>> -  int idx1 = get_stridx (ptr, offrng, ptr_qry.rvals);
>> +  int idx1 = get_stridx (ptr, memset_stmt, offrng, ptr_qry.rvals);
>>     if (idx1 <= 0)
>>       return false;
>>     strinfo *si1 = get_strinfo (idx1);
>> @@ -4178,8 +4181,8 @@ handle_builtin_string_cmp (gimple_stmt_iterator *gsi, range_query *rvals)
>>
>>     tree arg1 = gimple_call_arg (stmt, 0);
>>     tree arg2 = gimple_call_arg (stmt, 1);
>> -  int idx1 = get_stridx (arg1);
>> -  int idx2 = get_stridx (arg2);
>> +  int idx1 = get_stridx (arg1, stmt);
>> +  int idx2 = get_stridx (arg2, stmt);
>>
>>     /* For strncmp set to the value of the third argument if known.  */
>>     HOST_WIDE_INT bound = -1;
>> @@ -4318,7 +4321,7 @@ handle_pointer_plus (gimple_stmt_iterator *gsi)
>>   {
>>     gimple *stmt = gsi_stmt (*gsi);
>>     tree lhs = gimple_assign_lhs (stmt), off;
>> -  int idx = get_stridx (gimple_assign_rhs1 (stmt));
>> +  int idx = get_stridx (gimple_assign_rhs1 (stmt), stmt);
>>     strinfo *si, *zsi;
>>
>>     if (idx == 0)
>> @@ -4396,7 +4399,8 @@ nonzero_bytes_for_type (tree type, unsigned lenrange[3],
>>   }
>>
>>   static bool
>> -count_nonzero_bytes_addr (tree, unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
>> +count_nonzero_bytes_addr (tree, gimple *stmt,
>> +                         unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
>>                            unsigned [3], bool *, bool *, bool *,
>>                            range_query *, ssa_name_limit_t &);
>>
>> @@ -4416,7 +4420,8 @@ count_nonzero_bytes_addr (tree, unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
>>      Returns true on success and false otherwise.  */
>>
>>   static bool
>> -count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>> +count_nonzero_bytes (tree exp, gimple *stmt,
>> +                    unsigned HOST_WIDE_INT offset,
>>                       unsigned HOST_WIDE_INT nbytes,
>>                       unsigned lenrange[3], bool *nulterm,
>>                       bool *allnul, bool *allnonnul, range_query *rvals,
>> @@ -4435,7 +4440,8 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>>               exact value is not known) recurse once to set the range
>>               for an arbitrary constant.  */
>>            exp = build_int_cst (type, 1);
>> -         return count_nonzero_bytes (exp, offset, 1, lenrange,
>> +         return count_nonzero_bytes (exp, stmt,
>> +                                     offset, 1, lenrange,
>>                                        nulterm, allnul, allnonnul, rvals, snlim);
>>          }
>>
>> @@ -4462,7 +4468,8 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>>            for (unsigned i = 0; i != n; i++)
>>              {
>>                tree def = gimple_phi_arg_def (stmt, i);
>> -             if (!count_nonzero_bytes (def, offset, nbytes, lenrange, nulterm,
>> +             if (!count_nonzero_bytes (def, stmt,
>> +                                       offset, nbytes, lenrange, nulterm,
>>                                          allnul, allnonnul, rvals, snlim))
>>                  return false;
>>              }
>> @@ -4519,7 +4526,8 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>>          return false;
>>
>>         /* Handle MEM_REF = SSA_NAME types of assignments.  */
>> -      return count_nonzero_bytes_addr (arg, offset, nbytes, lenrange, nulterm,
>> +      return count_nonzero_bytes_addr (arg, stmt,
>> +                                      offset, nbytes, lenrange, nulterm,
>>                                         allnul, allnonnul, rvals, snlim);
>>       }
>>
>> @@ -4631,13 +4639,14 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
>>      bytes that are pointed to by EXP, which should be a pointer.  */
>>
>>   static bool
>> -count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>> +count_nonzero_bytes_addr (tree exp, gimple *stmt,
>> +                         unsigned HOST_WIDE_INT offset,
>>                            unsigned HOST_WIDE_INT nbytes,
>>                            unsigned lenrange[3], bool *nulterm,
>>                            bool *allnul, bool *allnonnul,
>>                            range_query *rvals, ssa_name_limit_t &snlim)
>>   {
>> -  int idx = get_stridx (exp);
>> +  int idx = get_stridx (exp, stmt);
>>     if (idx > 0)
>>       {
>>         strinfo *si = get_strinfo (idx);
>> @@ -4653,7 +4662,7 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>>                 && TREE_CODE (si->nonzero_chars) == SSA_NAME)
>>          {
>>            value_range vr;
>> -         rvals->range_of_expr (vr, si->nonzero_chars, si->stmt);
>> +         rvals->range_of_expr (vr, si->nonzero_chars, stmt);
>>            if (vr.kind () != VR_RANGE)
>>              return false;
>>
>> @@ -4699,7 +4708,8 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>>       }
>>
>>     if (TREE_CODE (exp) == ADDR_EXPR)
>> -    return count_nonzero_bytes (TREE_OPERAND (exp, 0), offset, nbytes,
>> +    return count_nonzero_bytes (TREE_OPERAND (exp, 0), stmt,
>> +                               offset, nbytes,
>>                                  lenrange, nulterm, allnul, allnonnul, rvals,
>>                                  snlim);
>>
>> @@ -4719,7 +4729,8 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>>            for (unsigned i = 0; i != n; i++)
>>              {
>>                tree def = gimple_phi_arg_def (stmt, i);
>> -             if (!count_nonzero_bytes_addr (def, offset, nbytes, lenrange,
>> +             if (!count_nonzero_bytes_addr (def, stmt,
>> +                                            offset, nbytes, lenrange,
>>                                               nulterm, allnul, allnonnul, rvals,
>>                                               snlim))
>>                  return false;
>> @@ -4747,7 +4758,8 @@ count_nonzero_bytes_addr (tree exp, unsigned HOST_WIDE_INT offset,
>>      (the results of strlen).  */
>>
>>   static bool
>> -count_nonzero_bytes (tree expr_or_type, unsigned lenrange[3], bool *nulterm,
>> +count_nonzero_bytes (tree expr_or_type, gimple *stmt,
>> +                    unsigned lenrange[3], bool *nulterm,
>>                       bool *allnul, bool *allnonnul, range_query *rvals)
>>   {
>>     if (TYPE_P (expr_or_type))
>> @@ -4765,7 +4777,8 @@ count_nonzero_bytes (tree expr_or_type, unsigned lenrange[3], bool *nulterm,
>>
>>     ssa_name_limit_t snlim;
>>     tree expr = expr_or_type;
>> -  return count_nonzero_bytes (expr, 0, 0, lenrange, nulterm, allnul, allnonnul,
>> +  return count_nonzero_bytes (expr, stmt,
>> +                             0, 0, lenrange, nulterm, allnul, allnonnul,
>>                                rvals, snlim);
>>   }
>>
>> @@ -4818,18 +4831,19 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>>               least OFFSET nonzero characters.  This is trivially true if
>>               OFFSET is zero.  */
>>            offset = tree_to_uhwi (mem_offset);
>> -         idx = get_stridx (TREE_OPERAND (lhs, 0));
>> +         idx = get_stridx (TREE_OPERAND (lhs, 0), stmt);
>>            if (idx > 0)
>>              si = get_strinfo (idx);
>>            if (offset == 0)
>>              ssaname = TREE_OPERAND (lhs, 0);
>> -         else if (si == NULL || compare_nonzero_chars (si, offset, rvals) < 0)
>> +         else if (si == NULL
>> +                  || compare_nonzero_chars (si, stmt, offset, rvals) < 0)
>>              {
>>                *zero_write = rhs ? initializer_zerop (rhs) : false;
>>
>>                bool dummy;
>>                unsigned lenrange[] = { UINT_MAX, 0, 0 };
>> -             if (count_nonzero_bytes (rhs ? rhs : storetype, lenrange,
>> +             if (count_nonzero_bytes (rhs ? rhs : storetype, stmt, lenrange,
>>                                         &dummy, &dummy, &dummy, rvals))
>>                  maybe_warn_overflow (stmt, true, lenrange[2], ptr_qry);
>>
>> @@ -4839,7 +4853,7 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>>       }
>>     else
>>       {
>> -      idx = get_addr_stridx (lhs, NULL_TREE, &offset, rvals);
>> +      idx = get_addr_stridx (lhs, stmt, NULL_TREE, &offset, rvals);
>>         if (idx > 0)
>>          si = get_strinfo (idx);
>>       }
>> @@ -4862,7 +4876,8 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>>     bool full_string_p;
>>
>>     const bool ranges_valid
>> -    = count_nonzero_bytes (rhs ? rhs : storetype, lenrange, &full_string_p,
>> +    = count_nonzero_bytes (rhs ? rhs : storetype, stmt,
>> +                          lenrange, &full_string_p,
>>                             &storing_all_zeros_p, &storing_all_nonzero_p,
>>                             rvals);
>>
>> @@ -4895,15 +4910,18 @@ handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
>>          {
>>            /* The offset of the last stored byte.  */
>>            unsigned HOST_WIDE_INT endoff = offset + lenrange[2] - 1;
>> -         store_before_nul[0] = compare_nonzero_chars (si, offset, rvals);
>> +         store_before_nul[0]
>> +           = compare_nonzero_chars (si, stmt, offset, rvals);
>>            if (endoff == offset)
>>              store_before_nul[1] = store_before_nul[0];
>>            else
>> -           store_before_nul[1] = compare_nonzero_chars (si, endoff, rvals);
>> +           store_before_nul[1]
>> +             = compare_nonzero_chars (si, stmt, endoff, rvals);
>>          }
>>         else
>>          {
>> -         store_before_nul[0] = compare_nonzero_chars (si, offset, rvals);
>> +         store_before_nul[0]
>> +           = compare_nonzero_chars (si, stmt, offset, rvals);
>>            store_before_nul[1] = store_before_nul[0];
>>            gcc_assert (offset == 0 || store_before_nul[0] >= 0);
>>          }
>> @@ -5128,7 +5146,7 @@ fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple *stmt)
>>          {
>>            tree arg1 = gimple_call_arg (call_stmt, 1);
>>            tree arg1_len = NULL_TREE;
>> -         int idx = get_stridx (arg1);
>> +         int idx = get_stridx (arg1, call_stmt);
>>
>>            if (idx)
>>              {
>> @@ -5342,7 +5360,7 @@ handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>>         tree rhs1 = gimple_assign_rhs1 (stmt);
>>         if (code == MEM_REF)
>>          {
>> -         idx = get_stridx (TREE_OPERAND (rhs1, 0));
>> +         idx = get_stridx (TREE_OPERAND (rhs1, 0), stmt);
>>            if (idx > 0)
>>              {
>>                strinfo *si = get_strinfo (idx);
>> @@ -5359,7 +5377,7 @@ handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>>              }
>>          }
>>         if (idx <= 0)
>> -       idx = get_addr_stridx (rhs1, NULL_TREE, &coff);
>> +       idx = get_addr_stridx (rhs1, stmt, NULL_TREE, &coff);
>>         if (idx > 0)
>>          {
>>            strinfo *si = get_strinfo (idx);
>> @@ -5421,7 +5439,8 @@ handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>>            unsigned lenrange[] = { UINT_MAX, 0, 0 };
>>            tree rhs = gimple_assign_rhs1 (stmt);
>>            const bool ranges_valid
>> -           = count_nonzero_bytes (rhs, lenrange, &full_string_p,
>> +           = count_nonzero_bytes (rhs, stmt,
>> +                                  lenrange, &full_string_p,
>>                                     &storing_all_zeros_p, &storing_all_nonzero_p,
>>                                     rvals);
>>            if (ranges_valid)
>> @@ -5520,7 +5539,7 @@ check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
>>                || (gimple_assign_cast_p (stmt)
>>                    && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
>>              {
>> -             int idx = get_stridx (gimple_assign_rhs1 (stmt));
>> +             int idx = get_stridx (gimple_assign_rhs1 (stmt), stmt);
>>                ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = idx;
>>              }
>>            else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
>> @@ -5602,20 +5621,20 @@ class strlen_dom_walker : public dom_walker
>>   public:
>>     strlen_dom_walker (cdi_direction direction)
>>       : dom_walker (direction),
>> -    evrp (false),
>> -    ptr_qry (&evrp, &var_cache),
>> -    var_cache (),
>> -    m_cleanup_cfg (false)
>> -  { }
>> +      ptr_qry (&m_ranger, &var_cache),
>> +      var_cache (),
>> +      m_cleanup_cfg (false)
>> +  {
>> +  }
>>
>>     ~strlen_dom_walker ();
>>
>>     virtual edge before_dom_children (basic_block);
>>     virtual void after_dom_children (basic_block);
>>
>> -  /* EVRP analyzer used for printf argument range processing, and
>> +  /* Ranger used for printf argument range processing, and
>>        to track strlen results across integer variable assignments.  */
>> -  evrp_range_analyzer evrp;
>> +  gimple_ranger m_ranger;
>>
>>     /* A pointer_query object and its cache to store information about
>>        pointers and their targets in.  */
>> @@ -5640,8 +5659,6 @@ strlen_dom_walker::~strlen_dom_walker ()
>>   edge
>>   strlen_dom_walker::before_dom_children (basic_block bb)
>>   {
>> -  evrp.enter (bb);
>> -
>>     basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
>>
>>     if (dombb == NULL)
>> @@ -5698,12 +5715,12 @@ strlen_dom_walker::before_dom_children (basic_block bb)
>>         tree result = gimple_phi_result (phi);
>>         if (!virtual_operand_p (result) && POINTER_TYPE_P (TREE_TYPE (result)))
>>          {
>> -         int idx = get_stridx (gimple_phi_arg_def (phi, 0));
>> +         int idx = get_stridx (gimple_phi_arg_def (phi, 0), phi);
>>            if (idx != 0)
>>              {
>>                unsigned int i, n = gimple_phi_num_args (phi);
>>                for (i = 1; i < n; i++)
>> -               if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
>> +               if (idx != get_stridx (gimple_phi_arg_def (phi, i), phi))
>>                    break;
>>                if (i == n)
>>                  ssa_ver_to_stridx[SSA_NAME_VERSION (result)] = idx;
>> @@ -5716,12 +5733,6 @@ strlen_dom_walker::before_dom_children (basic_block bb)
>>     /* Attempt to optimize individual statements.  */
>>     for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
>>       {
>> -      gimple *stmt = gsi_stmt (gsi);
>> -
>> -      /* First record ranges generated by this statement so they
>> -        can be used by printf argument processing.  */
>> -      evrp.record_ranges_from_stmt (stmt, false);
>> -
>>         /* Reset search depth preformance counter.  */
>>         ptr_qry.depth = 0;
>>
>> @@ -5744,8 +5755,6 @@ strlen_dom_walker::before_dom_children (basic_block bb)
>>   void
>>   strlen_dom_walker::after_dom_children (basic_block bb)
>>   {
>> -  evrp.leave (bb);
>> -
>>     if (bb->aux)
>>       {
>>         stridx_to_strinfo = ((vec<strinfo *, va_heap, vl_embed> *) bb->aux);
>> --
>> 2.31.1
>>
  

On 10/14/2021 4:07 PM, Martin Sebor via Gcc-patches wrote:
> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
>> We seem to be passing a lot of context around in the strlen code.  I
>> certainly don't want to contribute to more.
>>
>> Most of the handle_* functions are passing the gsi as well as either
>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
>> of that in the strlen pass object (well, the dom walker object, but we
>> can rename it to be less dom centric)?
>>
>> Something like the attached (untested) patch could be the basis for
>> further cleanups.
>>
>> Jakub, would this line of work interest you?
>
> You didn't ask me but since no one spoke up against it let me add
> some encouragement: this is exactly what I was envisioning and in
> line with other such modernization we have been doing elsewhere.
> Could you please submit it for review?
Agreed.
jeff
  

On 10/14/21 6:07 PM, Martin Sebor via Gcc-patches wrote:
> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
>> We seem to be passing a lot of context around in the strlen code.  I
>> certainly don't want to contribute to more.
>>
>> Most of the handle_* functions are passing the gsi as well as either
>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
>> of that in the strlen pass object (well, the dom walker object, but we
>> can rename it to be less dom centric)?
>>
>> Something like the attached (untested) patch could be the basis for
>> further cleanups.
>>
>> Jakub, would this line of work interest you?
>
> You didn't ask me but since no one spoke up against it let me add
> some encouragement: this is exactly what I was envisioning and in
> line with other such modernization we have been doing elsewhere.
> Could you please submit it for review?
>
> Martin

I'm willing to bet he didn't submit it for review because he doesn't 
have time this release to polish and track it...  (I think the threader 
has been quite consuming).  Rather, it was offered as a starting point 
for someone else who might be interested in continuing to pursue this 
work...  *everyone* is interested in cleanup work others do :-)

Of course, I could be wrong...

Andrew
  

On 10/15/21 2:47 AM, Andrew MacLeod wrote:
> On 10/14/21 6:07 PM, Martin Sebor via Gcc-patches wrote:
>> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
>>> We seem to be passing a lot of context around in the strlen code.  I
>>> certainly don't want to contribute to more.
>>>
>>> Most of the handle_* functions are passing the gsi as well as either
>>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
>>> of that in the strlen pass object (well, the dom walker object, but we
>>> can rename it to be less dom centric)?
>>>
>>> Something like the attached (untested) patch could be the basis for
>>> further cleanups.
>>>
>>> Jakub, would this line of work interest you?
>>
>> You didn't ask me but since no one spoke up against it let me add
>> some encouragement: this is exactly what I was envisioning and in
>> line with other such modernization we have been doing elsewhere.
>> Could you please submit it for review?
>>
>> Martin
> 
> I'm willing to bet he didn't submit it for review because he doesn't 
> have time this release to polish and track it...  (I think the threader 
> has been quite consuming).  Rather, it was offered as a starting point 
> for someone else who might be interested in continuing to pursue this 
> work...  *everyone* is interested in cleanup work others do :-)

Exactly.  There's a lot of work that could be done in this area, and I'm 
trying to avoid the situation with the threaders where what started as 
refactoring ended up with me basically owning them ;-).

That being said, I there are enough cleanups that are useful on their 
own.  I've removed all the passing around of GSIs, as well as ptr_qry, 
with the exception of anything dealing with the sprintf pass, since it 
has a slightly different interface.

This is patch 0001, which I'm formally submitting for inclusion.  No 
functional changes with this patch.  OK for trunk?

Also, I am PINGing patch 0002, which is the strlen pass conversion to 
the ranger.  As mentioned, this is just a change from an evrp client to 
a ranger client.  The APIs are exactly the same, and besides, the evrp 
analyzer is deprecated and slated for removal.  OK for trunk?

Aldy
  

On 10/15/2021 4:39 AM, Aldy Hernandez wrote:
>
>
> On 10/15/21 2:47 AM, Andrew MacLeod wrote:
>> On 10/14/21 6:07 PM, Martin Sebor via Gcc-patches wrote:
>>> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
>>>> We seem to be passing a lot of context around in the strlen code.  I
>>>> certainly don't want to contribute to more.
>>>>
>>>> Most of the handle_* functions are passing the gsi as well as either
>>>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
>>>> of that in the strlen pass object (well, the dom walker object, but we
>>>> can rename it to be less dom centric)?
>>>>
>>>> Something like the attached (untested) patch could be the basis for
>>>> further cleanups.
>>>>
>>>> Jakub, would this line of work interest you?
>>>
>>> You didn't ask me but since no one spoke up against it let me add
>>> some encouragement: this is exactly what I was envisioning and in
>>> line with other such modernization we have been doing elsewhere.
>>> Could you please submit it for review?
>>>
>>> Martin
>>
>> I'm willing to bet he didn't submit it for review because he doesn't 
>> have time this release to polish and track it...  (I think the 
>> threader has been quite consuming).  Rather, it was offered as a 
>> starting point for someone else who might be interested in continuing 
>> to pursue this work...  *everyone* is interested in cleanup work 
>> others do :-)
>
> Exactly.  There's a lot of work that could be done in this area, and 
> I'm trying to avoid the situation with the threaders where what 
> started as refactoring ended up with me basically owning them ;-).
I wouldn't go that far ;-)  I'm still here, just focused on other stuff.

>
> That being said, I there are enough cleanups that are useful on their 
> own.  I've removed all the passing around of GSIs, as well as ptr_qry, 
> with the exception of anything dealing with the sprintf pass, since it 
> has a slightly different interface.
You know, it's funny.   The 0001 patch looks a lot like what I ended up 
doing here and there i when I start cleaning things up.  Pull state into 
a class, make functions which need the state member functions, repeat 
until it works.
>
> This is patch 0001, which I'm formally submitting for inclusion. No 
> functional changes with this patch.  OK for trunk?
I'll ACK this now :-)


>
> Also, I am PINGing patch 0002, which is the strlen pass conversion to 
> the ranger.  As mentioned, this is just a change from an evrp client 
> to a ranger client.  The APIs are exactly the same, and besides, the 
> evrp analyzer is deprecated and slated for removal. OK for trunk?
I'll defer on this a bit.  I've got to step away and may not be back 
online tonight.  I worry more about the unintended testsuite fallout 
here more than anything.  Which argues it should go into the tester to 
see if there is any such fallout :-)


jeff
  

On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> The following patch converts the strlen pass from evrp to ranger,
> leaving DOM as the last remaining user.
So is there any reason why we can't convert DOM as well?   DOM's use of 
EVRP is pretty limited.  You've mentioned FP bits before, but my 
recollection is those are not part of the EVRP analysis DOM uses. Hell, 
give me a little guidance and I'll do the work...

>
> No additional cleanups have been done.  For example, the strlen pass
> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> pairs of integers instead of using a proper range.  Fixing this
> could further improve these passes.
>
> As a further enhancement, if the relevant maintainers deem useful,
> the domwalk could be removed from strlen.  That is, unless the pass
> needs it for something else.
The dom walk was strictly for the benefit of EVRP when it was added.  So 
I think it can get zapped once the pass is converted.

Jeff
  

On 10/18/21 12:49 AM, Jeff Law wrote:
> 
> 
> On 10/15/2021 4:39 AM, Aldy Hernandez wrote:
>>
>>
>> On 10/15/21 2:47 AM, Andrew MacLeod wrote:
>>> On 10/14/21 6:07 PM, Martin Sebor via Gcc-patches wrote:
>>>> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
>>>>> We seem to be passing a lot of context around in the strlen code.  I
>>>>> certainly don't want to contribute to more.
>>>>>
>>>>> Most of the handle_* functions are passing the gsi as well as either
>>>>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
>>>>> of that in the strlen pass object (well, the dom walker object, but we
>>>>> can rename it to be less dom centric)?
>>>>>
>>>>> Something like the attached (untested) patch could be the basis for
>>>>> further cleanups.
>>>>>
>>>>> Jakub, would this line of work interest you?
>>>>
>>>> You didn't ask me but since no one spoke up against it let me add
>>>> some encouragement: this is exactly what I was envisioning and in
>>>> line with other such modernization we have been doing elsewhere.
>>>> Could you please submit it for review?
>>>>
>>>> Martin
>>>
>>> I'm willing to bet he didn't submit it for review because he doesn't 
>>> have time this release to polish and track it...  (I think the 
>>> threader has been quite consuming).  Rather, it was offered as a 
>>> starting point for someone else who might be interested in continuing 
>>> to pursue this work...  *everyone* is interested in cleanup work 
>>> others do :-)
>>
>> Exactly.  There's a lot of work that could be done in this area, and 
>> I'm trying to avoid the situation with the threaders where what 
>> started as refactoring ended up with me basically owning them ;-).
> I wouldn't go that far ;-)  I'm still here, just focused on other stuff.

Heh.  Indeed, and I'm very grateful for your guidance and quick reviews. 
  They've made a huge difference!

What I should've said was that I'm trying to avoid going too deep here, 
because things that seem simple tend to grow tentacles that drag me into 
months of work, or in the case of ranger, years ;-).

I'm hoping that by next year we can unify all the threaders, and I can 
put them back in the Pandora's box where they belong.

> 
>>
>> That being said, I there are enough cleanups that are useful on their 
>> own.  I've removed all the passing around of GSIs, as well as ptr_qry, 
>> with the exception of anything dealing with the sprintf pass, since it 
>> has a slightly different interface.
> You know, it's funny.   The 0001 patch looks a lot like what I ended up 
> doing here and there i when I start cleaning things up.  Pull state into 
> a class, make functions which need the state member functions, repeat 
> until it works.

I've found that abstracting all this out not only helps understand the 
code better, but it separates functionality making glimmers of APIs 
shine through.

>>
>> This is patch 0001, which I'm formally submitting for inclusion. No 
>> functional changes with this patch.  OK for trunk?
> I'll ACK this now :-)
> 
> 
>>
>> Also, I am PINGing patch 0002, which is the strlen pass conversion to 
>> the ranger.  As mentioned, this is just a change from an evrp client 
>> to a ranger client.  The APIs are exactly the same, and besides, the 
>> evrp analyzer is deprecated and slated for removal. OK for trunk?
> I'll defer on this a bit.  I've got to step away and may not be back 
> online tonight.  I worry more about the unintended testsuite fallout 
> here more than anything.  Which argues it should go into the tester to 
> see if there is any such fallout :-)

Thanks for doing this.

Aldy
  

On 10/18/21 12:52 AM, Jeff Law wrote:
> 
> 
> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>> The following patch converts the strlen pass from evrp to ranger,
>> leaving DOM as the last remaining user.
> So is there any reason why we can't convert DOM as well?   DOM's use of 
> EVRP is pretty limited.  You've mentioned FP bits before, but my 
> recollection is those are not part of the EVRP analysis DOM uses. Hell, 
> give me a little guidance and I'll do the work...

Not only will I take you up on that offer, but I can provide 90% of the 
work.  Here be dragons, though (well, for me, maybe not for you ;-)).

DOM is actually an evrp pass at -O1 in disguise.  The reason it really 
is a covert evrp pass is because:

a) It calls extract_range_from_stmt on each statement.

b) It folds conditionals with simplify_using_ranges.

c) But most importantly, it exports discovered ranges when it's done 
(evrp_range_analyzer(true)).

If you look at the evrp pass, you'll notice that that's basically what 
it does, albeit with the substitute and fold engine, which also calls 
gimple fold plus other goodies.

But I could argue that we've made DOM into an evrp pass without 
noticing.  The last item (c) is particularly invasive because these 
exported ranges show up in other passes unexpectedly.  For instance, I 
saw an RTL pass at -O1 miss an optimization because it was dependent on 
some global range being set.  IMO, DOM should not export global ranges 
it discovered during its walk (do one thing and do it well), but I leave 
it to you experts to pontificate.

The attached patch is rather trivial.  It's mostly deleting state.  It 
seems DOM spends a lot of time massaging the IL so that it can fold 
conditionals or thread paths.  None of this is needed, because the 
ranger can do all of this.  Well, except floats, but...

...You'll notice that converting to the threader is an exercise in code 
deletion.  Basically, inherit from the hybrid threader while still using 
the copies/avail_exprs business.  This has the added benefit of keeping 
our float threading capabilities intact, while pulling in all the hybrid 
threader goodness.

Over the past year or so, I've been cleaning up evrp clients to use the 
common range_query API.  This makes this conversion easier, as it mostly 
involves replacing evrp_range_analyzer with the ranger and removing the 
state pushing/popping business.

That's the good news.  The bad news is that DOM changes the IL as it 
goes and the patch doesn't bootstrap.  Andrew insists that we should 
work even with DOM's changing IL, but last time we played this dance 
with the substitute_and_fold engine, there were some tweaks needed to 
the ranger.  Could be this, but I haven't investigated.  It could also 
be that the failures I was seeing were just DOM things that were no 
longer needed (shuffling the IL to simplify things for evrp).

This just needs a little shepherding from a DOM expert ;-).  If you get 
it to bootstrap, I could take care of the tests, performance, and making 
sure we're getting the same number of threads etc.

> 
>>
>> No additional cleanups have been done.  For example, the strlen pass
>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
>> pairs of integers instead of using a proper range.  Fixing this
>> could further improve these passes.
>>
>> As a further enhancement, if the relevant maintainers deem useful,
>> the domwalk could be removed from strlen.  That is, unless the pass
>> needs it for something else.
> The dom walk was strictly for the benefit of EVRP when it was added.  So 
> I think it can get zapped once the pass is converted.

Jakub mentioned a while ago, that the strlen pass itself needs DOM, so 
perhaps this needs to stay.

Aldy
  

On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>
>
> On 10/18/21 12:52 AM, Jeff Law wrote:
>>
>>
>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>> The following patch converts the strlen pass from evrp to ranger,
>>> leaving DOM as the last remaining user.
>> So is there any reason why we can't convert DOM as well?   DOM's use 
>> of EVRP is pretty limited.  You've mentioned FP bits before, but my 
>> recollection is those are not part of the EVRP analysis DOM uses. 
>> Hell, give me a little guidance and I'll do the work...
>
> Not only will I take you up on that offer, but I can provide 90% of 
> the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
>
> DOM is actually an evrp pass at -O1 in disguise.  The reason it really 
> is a covert evrp pass is because:
>
> a) It calls extract_range_from_stmt on each statement.
>
> b) It folds conditionals with simplify_using_ranges.
>
> c) But most importantly, it exports discovered ranges when it's done 
> (evrp_range_analyzer(true)).
>
> If you look at the evrp pass, you'll notice that that's basically what 
> it does, albeit with the substitute and fold engine, which also calls 
> gimple fold plus other goodies.
>
> But I could argue that we've made DOM into an evrp pass without 
> noticing.  The last item (c) is particularly invasive because these 
> exported ranges show up in other passes unexpectedly.  For instance, I 
> saw an RTL pass at -O1 miss an optimization because it was dependent 
> on some global range being set.  IMO, DOM should not export global 
> ranges it discovered during its walk (do one thing and do it well), 
> but I leave it to you experts to pontificate.
All true.  But I don't think we've got many, if any, hard dependencies 
on those behaviors.

>
> The attached patch is rather trivial.  It's mostly deleting state.  It 
> seems DOM spends a lot of time massaging the IL so that it can fold 
> conditionals or thread paths.  None of this is needed, because the 
> ranger can do all of this.  Well, except floats, but...
Massaging the IL should only take two forms IIRC.

First, if we have a simplification we can do.  That could be const/copy 
propagation, replacing an expression with an SSA_NAME or constant and 
the like.  It doesn't massage the IL just to massage the IL.

Second, we do temporarily copy propagate the current known values of an 
SSA name into use points and then see if that allows us to determine if 
a statement is already in the hash tables.  But we undo that so that 
nobody should see that temporary change in state.

Finally, it does create some expressions & statements on the fly to 
enter them into the tables.  For example, if it sees a store, it'll 
create a load with the source & dest interchanged and enter that into 
the expression table.  But none of this stuff ever shows up in the IL.  
It's just to create entries in the expression tables.

So ITSM the only real concern would be if those temporary const/copy 
propagations were still in the IL and we called back into Ranger and it 
poked at that data somehow.
>
> That's the good news.  The bad news is that DOM changes the IL as it 
> goes and the patch doesn't bootstrap.  Andrew insists that we should 
> work even with DOM's changing IL, but last time we played this dance 
> with the substitute_and_fold engine, there were some tweaks needed to 
> the ranger.  Could be this, but I haven't investigated.  It could also 
> be that the failures I was seeing were just DOM things that were no 
> longer needed (shuffling the IL to simplify things for evrp).
So if we're referring to those temporary const/copy propagations 
"escaping" into Ranger, then I would fully expect that to cause 
problems.  Essentially they're path sensitive const/copy propagations 
and may not be valid on all the paths through the CFG to the statement 
where the propagation occurs



>
> This just needs a little shepherding from a DOM expert ;-).  If you 
> get it to bootstrap, I could take care of the tests, performance, and 
> making sure we're getting the same number of threads etc.
>
>>
>>>
>>> No additional cleanups have been done.  For example, the strlen pass
>>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
>>> pairs of integers instead of using a proper range.  Fixing this
>>> could further improve these passes.
>>>
>>> As a further enhancement, if the relevant maintainers deem useful,
>>> the domwalk could be removed from strlen.  That is, unless the pass
>>> needs it for something else.
>> The dom walk was strictly for the benefit of EVRP when it was added.  
>> So I think it can get zapped once the pass is converted.
>
> Jakub mentioned a while ago, that the strlen pass itself needs DOM, so 
> perhaps this needs to stay.
Yes, strlen wants DOM.  But the printf bits don't really need it. Well,  
maybe they do now that the printf warnings are more tightly integrated 
with the strlen bits.


jeff
  

> Massaging the IL should only take two forms IIRC.
>
> First, if we have a simplification we can do.  That could be const/copy
> propagation, replacing an expression with an SSA_NAME or constant and
> the like.  It doesn't massage the IL just to massage the IL.
>
> Second, we do temporarily copy propagate the current known values of an
> SSA name into use points and then see if that allows us to determine if
> a statement is already in the hash tables.  But we undo that so that
> nobody should see that temporary change in state.
>
> Finally, it does create some expressions & statements on the fly to
> enter them into the tables.  For example, if it sees a store, it'll
> create a load with the source & dest interchanged and enter that into
> the expression table.  But none of this stuff ever shows up in the IL.
> It's just to create entries in the expression tables.
>
> So ITSM the only real concern would be if those temporary const/copy
> propagations were still in the IL and we called back into Ranger and it
> poked at that data somehow.

Hmmm, this is all very good insight.  Thanks.

One thing that would have to be adjusted then is remove the
enable_ranger() call in the patch.  This sets a global ranger, and
there are users of get_range_query() that will use it to get on-demand
ranges.  One such use that I added was ssa_name_has_boolean_range in
tree-ssa-dom.c.  This means that if the IL has been temporarily
changed, this function can and will use the global ranger.  The
alternative here would be to just create a new local ranger:

-  gimple_ranger *ranger = enable_ranger (fun);
+  gimple_ranger *ranger = new gimple_ranger;

and then obviously deallocate it at the disable_ranger call site.

This will cause any users of get_range_query() in the compiler to just
use global ranges.  Hopefully, none of these downstream users of
get_range_query() from DOM need context sensitive results.
ssa_name_has_boolean_range??

I think what you'd need to do is check that there are no calls to the
ranger from cprop_into_stmt (?? this is the place where IL changes??),
until wherever the undoing happens (I couldn't find it).  I see a call
to simplify_using_ranges in optimize_stmt that looks like it could be
called with the IL in mid-flight.  Maybe this call needs to happen
before the IL is altered?

> So if we're referring to those temporary const/copy propagations
> "escaping" into Ranger, then I would fully expect that to cause
> problems.  Essentially they're path sensitive const/copy propagations
> and may not be valid on all the paths through the CFG to the statement
> where the propagation occurs

Yeah.  disabling the global ranger should help, plus making sure you
don't use the ranger in the midst of the path sensitive changes.

Aldy
  

On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
> >
> >
> > On 10/18/21 12:52 AM, Jeff Law wrote:
> >>
> >>
> >> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> >>> The following patch converts the strlen pass from evrp to ranger,
> >>> leaving DOM as the last remaining user.
> >> So is there any reason why we can't convert DOM as well?   DOM's use
> >> of EVRP is pretty limited.  You've mentioned FP bits before, but my
> >> recollection is those are not part of the EVRP analysis DOM uses.
> >> Hell, give me a little guidance and I'll do the work...
> >
> > Not only will I take you up on that offer, but I can provide 90% of
> > the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
> >
> > DOM is actually an evrp pass at -O1 in disguise.  The reason it really
> > is a covert evrp pass is because:
> >
> > a) It calls extract_range_from_stmt on each statement.
> >
> > b) It folds conditionals with simplify_using_ranges.
> >
> > c) But most importantly, it exports discovered ranges when it's done
> > (evrp_range_analyzer(true)).
> >
> > If you look at the evrp pass, you'll notice that that's basically what
> > it does, albeit with the substitute and fold engine, which also calls
> > gimple fold plus other goodies.
> >
> > But I could argue that we've made DOM into an evrp pass without
> > noticing.  The last item (c) is particularly invasive because these
> > exported ranges show up in other passes unexpectedly.  For instance, I
> > saw an RTL pass at -O1 miss an optimization because it was dependent
> > on some global range being set.  IMO, DOM should not export global
> > ranges it discovered during its walk (do one thing and do it well),
> > but I leave it to you experts to pontificate.
> All true.  But I don't think we've got many, if any, hard dependencies
> on those behaviors.
>
> >
> > The attached patch is rather trivial.  It's mostly deleting state.  It
> > seems DOM spends a lot of time massaging the IL so that it can fold
> > conditionals or thread paths.  None of this is needed, because the
> > ranger can do all of this.  Well, except floats, but...
> Massaging the IL should only take two forms IIRC.
>
> First, if we have a simplification we can do.  That could be const/copy
> propagation, replacing an expression with an SSA_NAME or constant and
> the like.  It doesn't massage the IL just to massage the IL.
>
> Second, we do temporarily copy propagate the current known values of an
> SSA name into use points and then see if that allows us to determine if
> a statement is already in the hash tables.  But we undo that so that
> nobody should see that temporary change in state.

Are you sure we still do that?  I can't find it at least.

>
> Finally, it does create some expressions & statements on the fly to
> enter them into the tables.  For example, if it sees a store, it'll
> create a load with the source & dest interchanged and enter that into
> the expression table.  But none of this stuff ever shows up in the IL.
> It's just to create entries in the expression tables.
>
> So ITSM the only real concern would be if those temporary const/copy
> propagations were still in the IL and we called back into Ranger and it
> poked at that data somehow.
> >
> > That's the good news.  The bad news is that DOM changes the IL as it
> > goes and the patch doesn't bootstrap.  Andrew insists that we should
> > work even with DOM's changing IL, but last time we played this dance
> > with the substitute_and_fold engine, there were some tweaks needed to
> > the ranger.  Could be this, but I haven't investigated.  It could also
> > be that the failures I was seeing were just DOM things that were no
> > longer needed (shuffling the IL to simplify things for evrp).
> So if we're referring to those temporary const/copy propagations
> "escaping" into Ranger, then I would fully expect that to cause
> problems.  Essentially they're path sensitive const/copy propagations
> and may not be valid on all the paths through the CFG to the statement
> where the propagation occurs
>
>
>
> >
> > This just needs a little shepherding from a DOM expert ;-).  If you
> > get it to bootstrap, I could take care of the tests, performance, and
> > making sure we're getting the same number of threads etc.
> >
> >>
> >>>
> >>> No additional cleanups have been done.  For example, the strlen pass
> >>> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> >>> pairs of integers instead of using a proper range.  Fixing this
> >>> could further improve these passes.
> >>>
> >>> As a further enhancement, if the relevant maintainers deem useful,
> >>> the domwalk could be removed from strlen.  That is, unless the pass
> >>> needs it for something else.
> >> The dom walk was strictly for the benefit of EVRP when it was added.
> >> So I think it can get zapped once the pass is converted.
> >
> > Jakub mentioned a while ago, that the strlen pass itself needs DOM, so
> > perhaps this needs to stay.
> Yes, strlen wants DOM.  But the printf bits don't really need it. Well,
> maybe they do now that the printf warnings are more tightly integrated
> with the strlen bits.
>
>
> jeff
>
  

On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
> >
> >
> >
> > On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
> > >
> > >
> > > On 10/18/21 12:52 AM, Jeff Law wrote:
> > >>
> > >>
> > >> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> > >>> The following patch converts the strlen pass from evrp to ranger,
> > >>> leaving DOM as the last remaining user.
> > >> So is there any reason why we can't convert DOM as well?   DOM's use
> > >> of EVRP is pretty limited.  You've mentioned FP bits before, but my
> > >> recollection is those are not part of the EVRP analysis DOM uses.
> > >> Hell, give me a little guidance and I'll do the work...
> > >
> > > Not only will I take you up on that offer, but I can provide 90% of
> > > the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
> > >
> > > DOM is actually an evrp pass at -O1 in disguise.  The reason it really
> > > is a covert evrp pass is because:
> > >
> > > a) It calls extract_range_from_stmt on each statement.
> > >
> > > b) It folds conditionals with simplify_using_ranges.
> > >
> > > c) But most importantly, it exports discovered ranges when it's done
> > > (evrp_range_analyzer(true)).
> > >
> > > If you look at the evrp pass, you'll notice that that's basically what
> > > it does, albeit with the substitute and fold engine, which also calls
> > > gimple fold plus other goodies.
> > >
> > > But I could argue that we've made DOM into an evrp pass without
> > > noticing.  The last item (c) is particularly invasive because these
> > > exported ranges show up in other passes unexpectedly.  For instance, I
> > > saw an RTL pass at -O1 miss an optimization because it was dependent
> > > on some global range being set.  IMO, DOM should not export global
> > > ranges it discovered during its walk (do one thing and do it well),
> > > but I leave it to you experts to pontificate.
> > All true.  But I don't think we've got many, if any, hard dependencies
> > on those behaviors.
> >
> > >
> > > The attached patch is rather trivial.  It's mostly deleting state.  It
> > > seems DOM spends a lot of time massaging the IL so that it can fold
> > > conditionals or thread paths.  None of this is needed, because the
> > > ranger can do all of this.  Well, except floats, but...
> > Massaging the IL should only take two forms IIRC.
> >
> > First, if we have a simplification we can do.  That could be const/copy
> > propagation, replacing an expression with an SSA_NAME or constant and
> > the like.  It doesn't massage the IL just to massage the IL.
> >
> > Second, we do temporarily copy propagate the current known values of an
> > SSA name into use points and then see if that allows us to determine if
> > a statement is already in the hash tables.  But we undo that so that
> > nobody should see that temporary change in state.
>
> Are you sure we still do that?  I can't find it at least.

I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
copy propagation that happens in the DOM's use of the threader:

      /* Make a copy of the uses & vuses into USES_COPY, then cprop into
         the operands.  */
      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
        {
          tree tmp = NULL;
          tree use = USE_FROM_PTR (use_p);

          copy[i++] = use;
          if (TREE_CODE (use) == SSA_NAME)
        tmp = SSA_NAME_VALUE (use);
          if (tmp)
        SET_USE (use_p, tmp);
        }

      cached_lhs = simplifier->simplify (stmt, stmt, bb, this);

      /* Restore the statement's original uses/defs.  */
      i = 0;
      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
        SET_USE (use_p, copy[i++]);

Aldy
  

On Thu, Oct 21, 2021 at 2:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
> > >
> > >
> > >
> > > On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
> > > >
> > > >
> > > > On 10/18/21 12:52 AM, Jeff Law wrote:
> > > >>
> > > >>
> > > >> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> > > >>> The following patch converts the strlen pass from evrp to ranger,
> > > >>> leaving DOM as the last remaining user.
> > > >> So is there any reason why we can't convert DOM as well?   DOM's use
> > > >> of EVRP is pretty limited.  You've mentioned FP bits before, but my
> > > >> recollection is those are not part of the EVRP analysis DOM uses.
> > > >> Hell, give me a little guidance and I'll do the work...
> > > >
> > > > Not only will I take you up on that offer, but I can provide 90% of
> > > > the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
> > > >
> > > > DOM is actually an evrp pass at -O1 in disguise.  The reason it really
> > > > is a covert evrp pass is because:
> > > >
> > > > a) It calls extract_range_from_stmt on each statement.
> > > >
> > > > b) It folds conditionals with simplify_using_ranges.
> > > >
> > > > c) But most importantly, it exports discovered ranges when it's done
> > > > (evrp_range_analyzer(true)).
> > > >
> > > > If you look at the evrp pass, you'll notice that that's basically what
> > > > it does, albeit with the substitute and fold engine, which also calls
> > > > gimple fold plus other goodies.
> > > >
> > > > But I could argue that we've made DOM into an evrp pass without
> > > > noticing.  The last item (c) is particularly invasive because these
> > > > exported ranges show up in other passes unexpectedly.  For instance, I
> > > > saw an RTL pass at -O1 miss an optimization because it was dependent
> > > > on some global range being set.  IMO, DOM should not export global
> > > > ranges it discovered during its walk (do one thing and do it well),
> > > > but I leave it to you experts to pontificate.
> > > All true.  But I don't think we've got many, if any, hard dependencies
> > > on those behaviors.
> > >
> > > >
> > > > The attached patch is rather trivial.  It's mostly deleting state.  It
> > > > seems DOM spends a lot of time massaging the IL so that it can fold
> > > > conditionals or thread paths.  None of this is needed, because the
> > > > ranger can do all of this.  Well, except floats, but...
> > > Massaging the IL should only take two forms IIRC.
> > >
> > > First, if we have a simplification we can do.  That could be const/copy
> > > propagation, replacing an expression with an SSA_NAME or constant and
> > > the like.  It doesn't massage the IL just to massage the IL.
> > >
> > > Second, we do temporarily copy propagate the current known values of an
> > > SSA name into use points and then see if that allows us to determine if
> > > a statement is already in the hash tables.  But we undo that so that
> > > nobody should see that temporary change in state.
> >
> > Are you sure we still do that?  I can't find it at least.
>
> I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
> copy propagation that happens in the DOM's use of the threader:
>
>       /* Make a copy of the uses & vuses into USES_COPY, then cprop into
>          the operands.  */
>       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>         {
>           tree tmp = NULL;
>           tree use = USE_FROM_PTR (use_p);
>
>           copy[i++] = use;
>           if (TREE_CODE (use) == SSA_NAME)
>         tmp = SSA_NAME_VALUE (use);
>           if (tmp)
>         SET_USE (use_p, tmp);
>         }
>
>       cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
>
>       /* Restore the statement's original uses/defs.  */
>       i = 0;
>       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>         SET_USE (use_p, copy[i++]);

Ah, likely.  These days we'd likely use a gimple_match_op but then
this seems heavily abstracted, no idea where simplifier->simplify
might lead to ;)
I'm also not sure why the threader would do the valueization here and
not the simplify() function (and lookup_avail_expr misses an 'exploded' operand
lookup as well).  Lot's of legacy code ;)

But I think the above is not going to be an issue unless ranger runs in
circles around backedges, arriving at this very same stmt again?  A way
out might be to copy the stmt to the stack, adjust operands and use that
for the simplify entry.

Richard.

> Aldy
>
  

On 10/21/21 3:14 PM, Richard Biener wrote:
> On Thu, Oct 21, 2021 at 2:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>>
>>> On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>>>
>>>>
>>>>
>>>> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>>>>>
>>>>>
>>>>> On 10/18/21 12:52 AM, Jeff Law wrote:
>>>>>>
>>>>>>
>>>>>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>>>>>> The following patch converts the strlen pass from evrp to ranger,
>>>>>>> leaving DOM as the last remaining user.
>>>>>> So is there any reason why we can't convert DOM as well?   DOM's use
>>>>>> of EVRP is pretty limited.  You've mentioned FP bits before, but my
>>>>>> recollection is those are not part of the EVRP analysis DOM uses.
>>>>>> Hell, give me a little guidance and I'll do the work...
>>>>>
>>>>> Not only will I take you up on that offer, but I can provide 90% of
>>>>> the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
>>>>>
>>>>> DOM is actually an evrp pass at -O1 in disguise.  The reason it really
>>>>> is a covert evrp pass is because:
>>>>>
>>>>> a) It calls extract_range_from_stmt on each statement.
>>>>>
>>>>> b) It folds conditionals with simplify_using_ranges.
>>>>>
>>>>> c) But most importantly, it exports discovered ranges when it's done
>>>>> (evrp_range_analyzer(true)).
>>>>>
>>>>> If you look at the evrp pass, you'll notice that that's basically what
>>>>> it does, albeit with the substitute and fold engine, which also calls
>>>>> gimple fold plus other goodies.
>>>>>
>>>>> But I could argue that we've made DOM into an evrp pass without
>>>>> noticing.  The last item (c) is particularly invasive because these
>>>>> exported ranges show up in other passes unexpectedly.  For instance, I
>>>>> saw an RTL pass at -O1 miss an optimization because it was dependent
>>>>> on some global range being set.  IMO, DOM should not export global
>>>>> ranges it discovered during its walk (do one thing and do it well),
>>>>> but I leave it to you experts to pontificate.
>>>> All true.  But I don't think we've got many, if any, hard dependencies
>>>> on those behaviors.
>>>>
>>>>>
>>>>> The attached patch is rather trivial.  It's mostly deleting state.  It
>>>>> seems DOM spends a lot of time massaging the IL so that it can fold
>>>>> conditionals or thread paths.  None of this is needed, because the
>>>>> ranger can do all of this.  Well, except floats, but...
>>>> Massaging the IL should only take two forms IIRC.
>>>>
>>>> First, if we have a simplification we can do.  That could be const/copy
>>>> propagation, replacing an expression with an SSA_NAME or constant and
>>>> the like.  It doesn't massage the IL just to massage the IL.
>>>>
>>>> Second, we do temporarily copy propagate the current known values of an
>>>> SSA name into use points and then see if that allows us to determine if
>>>> a statement is already in the hash tables.  But we undo that so that
>>>> nobody should see that temporary change in state.
>>>
>>> Are you sure we still do that?  I can't find it at least.
>>
>> I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
>> copy propagation that happens in the DOM's use of the threader:
>>
>>        /* Make a copy of the uses & vuses into USES_COPY, then cprop into
>>           the operands.  */
>>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>>          {
>>            tree tmp = NULL;
>>            tree use = USE_FROM_PTR (use_p);
>>
>>            copy[i++] = use;
>>            if (TREE_CODE (use) == SSA_NAME)
>>          tmp = SSA_NAME_VALUE (use);
>>            if (tmp)
>>          SET_USE (use_p, tmp);
>>          }
>>
>>        cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
>>
>>        /* Restore the statement's original uses/defs.  */
>>        i = 0;
>>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>>          SET_USE (use_p, copy[i++]);
> 
> Ah, likely.  These days we'd likely use a gimple_match_op but then
> this seems heavily abstracted, no idea where simplifier->simplify
> might lead to ;)
> I'm also not sure why the threader would do the valueization here and
> not the simplify() function (and lookup_avail_expr misses an 'exploded' operand
> lookup as well).  Lot's of legacy code ;)

Yes, there's a lot of legacy code I've left mostly alone.

There are two copies of simplify() now, the DOM version 
(dom_jt_simplifier::simplify) and the VRP version 
(hybrid_jt_simplifier::simplify).  Each do slightly different things, as 
has always been the case.  It's just that the separation is now explicit.

No idea what's up with the valueization either.  The VRP version doesn't 
need any of this valuezation or on the side structures.  You just ask 
the range of a stmt on a path and it gives you an answer.

> 
> But I think the above is not going to be an issue unless ranger runs in
> circles around backedges, arriving at this very same stmt again?  A way
> out might be to copy the stmt to the stack, adjust operands and use that
> for the simplify entry.

If you look at the patch I sent Jeff, you'll see that I've removed most 
of what's in that function.  There's no need to propagate anything.  The 
ranger can simplify the final conditional without having to set up anything.

Aldy
  

On 10/21/2021 6:56 AM, Aldy Hernandez wrote:
> On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>>
>>>
>>> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>>>>
>>>> On 10/18/21 12:52 AM, Jeff Law wrote:
>>>>>
>>>>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>>>>> The following patch converts the strlen pass from evrp to ranger,
>>>>>> leaving DOM as the last remaining user.
>>>>> So is there any reason why we can't convert DOM as well?   DOM's use
>>>>> of EVRP is pretty limited.  You've mentioned FP bits before, but my
>>>>> recollection is those are not part of the EVRP analysis DOM uses.
>>>>> Hell, give me a little guidance and I'll do the work...
>>>> Not only will I take you up on that offer, but I can provide 90% of
>>>> the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
>>>>
>>>> DOM is actually an evrp pass at -O1 in disguise.  The reason it really
>>>> is a covert evrp pass is because:
>>>>
>>>> a) It calls extract_range_from_stmt on each statement.
>>>>
>>>> b) It folds conditionals with simplify_using_ranges.
>>>>
>>>> c) But most importantly, it exports discovered ranges when it's done
>>>> (evrp_range_analyzer(true)).
>>>>
>>>> If you look at the evrp pass, you'll notice that that's basically what
>>>> it does, albeit with the substitute and fold engine, which also calls
>>>> gimple fold plus other goodies.
>>>>
>>>> But I could argue that we've made DOM into an evrp pass without
>>>> noticing.  The last item (c) is particularly invasive because these
>>>> exported ranges show up in other passes unexpectedly.  For instance, I
>>>> saw an RTL pass at -O1 miss an optimization because it was dependent
>>>> on some global range being set.  IMO, DOM should not export global
>>>> ranges it discovered during its walk (do one thing and do it well),
>>>> but I leave it to you experts to pontificate.
>>> All true.  But I don't think we've got many, if any, hard dependencies
>>> on those behaviors.
>>>
>>>> The attached patch is rather trivial.  It's mostly deleting state.  It
>>>> seems DOM spends a lot of time massaging the IL so that it can fold
>>>> conditionals or thread paths.  None of this is needed, because the
>>>> ranger can do all of this.  Well, except floats, but...
>>> Massaging the IL should only take two forms IIRC.
>>>
>>> First, if we have a simplification we can do.  That could be const/copy
>>> propagation, replacing an expression with an SSA_NAME or constant and
>>> the like.  It doesn't massage the IL just to massage the IL.
>>>
>>> Second, we do temporarily copy propagate the current known values of an
>>> SSA name into use points and then see if that allows us to determine if
>>> a statement is already in the hash tables.  But we undo that so that
>>> nobody should see that temporary change in state.
>> Are you sure we still do that?  I can't find it at least.
> I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
> copy propagation that happens in the DOM's use of the threader:
>
>        /* Make a copy of the uses & vuses into USES_COPY, then cprop into
>           the operands.  */
>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>          {
>            tree tmp = NULL;
>            tree use = USE_FROM_PTR (use_p);
>
>            copy[i++] = use;
>            if (TREE_CODE (use) == SSA_NAME)
>          tmp = SSA_NAME_VALUE (use);
>            if (tmp)
>          SET_USE (use_p, tmp);
>          }
>
>        cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
>
>        /* Restore the statement's original uses/defs.  */
>        i = 0;
>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>          SET_USE (use_p, copy[i++]);
Exactly what I was referring to.  It may be worth an experiment -- I 
can't recall when this code went in.  It might be a remnant from the 
original threader that pre-dates block copying.  In that world we had to 
look up expressions in the table as part of the step to verify that we 
could safely ignore statements at the start of a block.

Or it could be something that was added to improve threading when the 
condition we're trying to thread through is partially redundant on the 
thread path.  This would allow us to discover that partial redundancy 
and exploit it for threading.

In either case this code may have outlived its usefulness.  I wonder 
what would happen if we just took it out.

jeff
  

On Thu, Oct 21, 2021 at 3:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 10/21/21 3:14 PM, Richard Biener wrote:
> > On Thu, Oct 21, 2021 at 2:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >> On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
> >> <richard.guenther@gmail.com> wrote:
> >>>
> >>> On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
> >>>>
> >>>>
> >>>>
> >>>> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
> >>>>>
> >>>>>
> >>>>> On 10/18/21 12:52 AM, Jeff Law wrote:
> >>>>>>
> >>>>>>
> >>>>>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> >>>>>>> The following patch converts the strlen pass from evrp to ranger,
> >>>>>>> leaving DOM as the last remaining user.
> >>>>>> So is there any reason why we can't convert DOM as well?   DOM's use
> >>>>>> of EVRP is pretty limited.  You've mentioned FP bits before, but my
> >>>>>> recollection is those are not part of the EVRP analysis DOM uses.
> >>>>>> Hell, give me a little guidance and I'll do the work...
> >>>>>
> >>>>> Not only will I take you up on that offer, but I can provide 90% of
> >>>>> the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
> >>>>>
> >>>>> DOM is actually an evrp pass at -O1 in disguise.  The reason it really
> >>>>> is a covert evrp pass is because:
> >>>>>
> >>>>> a) It calls extract_range_from_stmt on each statement.
> >>>>>
> >>>>> b) It folds conditionals with simplify_using_ranges.
> >>>>>
> >>>>> c) But most importantly, it exports discovered ranges when it's done
> >>>>> (evrp_range_analyzer(true)).
> >>>>>
> >>>>> If you look at the evrp pass, you'll notice that that's basically what
> >>>>> it does, albeit with the substitute and fold engine, which also calls
> >>>>> gimple fold plus other goodies.
> >>>>>
> >>>>> But I could argue that we've made DOM into an evrp pass without
> >>>>> noticing.  The last item (c) is particularly invasive because these
> >>>>> exported ranges show up in other passes unexpectedly.  For instance, I
> >>>>> saw an RTL pass at -O1 miss an optimization because it was dependent
> >>>>> on some global range being set.  IMO, DOM should not export global
> >>>>> ranges it discovered during its walk (do one thing and do it well),
> >>>>> but I leave it to you experts to pontificate.
> >>>> All true.  But I don't think we've got many, if any, hard dependencies
> >>>> on those behaviors.
> >>>>
> >>>>>
> >>>>> The attached patch is rather trivial.  It's mostly deleting state.  It
> >>>>> seems DOM spends a lot of time massaging the IL so that it can fold
> >>>>> conditionals or thread paths.  None of this is needed, because the
> >>>>> ranger can do all of this.  Well, except floats, but...
> >>>> Massaging the IL should only take two forms IIRC.
> >>>>
> >>>> First, if we have a simplification we can do.  That could be const/copy
> >>>> propagation, replacing an expression with an SSA_NAME or constant and
> >>>> the like.  It doesn't massage the IL just to massage the IL.
> >>>>
> >>>> Second, we do temporarily copy propagate the current known values of an
> >>>> SSA name into use points and then see if that allows us to determine if
> >>>> a statement is already in the hash tables.  But we undo that so that
> >>>> nobody should see that temporary change in state.
> >>>
> >>> Are you sure we still do that?  I can't find it at least.
> >>
> >> I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
> >> copy propagation that happens in the DOM's use of the threader:
> >>
> >>        /* Make a copy of the uses & vuses into USES_COPY, then cprop into
> >>           the operands.  */
> >>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
> >>          {
> >>            tree tmp = NULL;
> >>            tree use = USE_FROM_PTR (use_p);
> >>
> >>            copy[i++] = use;
> >>            if (TREE_CODE (use) == SSA_NAME)
> >>          tmp = SSA_NAME_VALUE (use);
> >>            if (tmp)
> >>          SET_USE (use_p, tmp);
> >>          }
> >>
> >>        cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
> >>
> >>        /* Restore the statement's original uses/defs.  */
> >>        i = 0;
> >>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
> >>          SET_USE (use_p, copy[i++]);
> >
> > Ah, likely.  These days we'd likely use a gimple_match_op but then
> > this seems heavily abstracted, no idea where simplifier->simplify
> > might lead to ;)
> > I'm also not sure why the threader would do the valueization here and
> > not the simplify() function (and lookup_avail_expr misses an 'exploded' operand
> > lookup as well).  Lot's of legacy code ;)
>
> Yes, there's a lot of legacy code I've left mostly alone.
>
> There are two copies of simplify() now, the DOM version
> (dom_jt_simplifier::simplify) and the VRP version
> (hybrid_jt_simplifier::simplify).  Each do slightly different things, as
> has always been the case.  It's just that the separation is now explicit.
>
> No idea what's up with the valueization either.  The VRP version doesn't
> need any of this valuezation or on the side structures.  You just ask
> the range of a stmt on a path and it gives you an answer.

Yeah, but it doesn't "simplify", it uses ranger to do constant folding
... (ick).
For random expressions I'd have used gimple_simplify (in fact it somehow
tries to do value-numbering or sth like that to derive new equivalences).

> >
> > But I think the above is not going to be an issue unless ranger runs in
> > circles around backedges, arriving at this very same stmt again?  A way
> > out might be to copy the stmt to the stack, adjust operands and use that
> > for the simplify entry.
>
> If you look at the patch I sent Jeff, you'll see that I've removed most
> of what's in that function.  There's no need to propagate anything.  The
> ranger can simplify the final conditional without having to set up anything.

So maybe we can remove all that code (jt_state::register_equivs_stmt).

Richard.

> Aldy
>
  

On 10/21/21 3:46 PM, Richard Biener wrote:
> On Thu, Oct 21, 2021 at 3:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 10/21/21 3:14 PM, Richard Biener wrote:
>>> On Thu, Oct 21, 2021 at 2:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>> On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>>
>>>>> On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>>>>>>>
>>>>>>>
>>>>>>> On 10/18/21 12:52 AM, Jeff Law wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>>>>>>>> The following patch converts the strlen pass from evrp to ranger,
>>>>>>>>> leaving DOM as the last remaining user.
>>>>>>>> So is there any reason why we can't convert DOM as well?   DOM's use
>>>>>>>> of EVRP is pretty limited.  You've mentioned FP bits before, but my
>>>>>>>> recollection is those are not part of the EVRP analysis DOM uses.
>>>>>>>> Hell, give me a little guidance and I'll do the work...
>>>>>>>
>>>>>>> Not only will I take you up on that offer, but I can provide 90% of
>>>>>>> the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
>>>>>>>
>>>>>>> DOM is actually an evrp pass at -O1 in disguise.  The reason it really
>>>>>>> is a covert evrp pass is because:
>>>>>>>
>>>>>>> a) It calls extract_range_from_stmt on each statement.
>>>>>>>
>>>>>>> b) It folds conditionals with simplify_using_ranges.
>>>>>>>
>>>>>>> c) But most importantly, it exports discovered ranges when it's done
>>>>>>> (evrp_range_analyzer(true)).
>>>>>>>
>>>>>>> If you look at the evrp pass, you'll notice that that's basically what
>>>>>>> it does, albeit with the substitute and fold engine, which also calls
>>>>>>> gimple fold plus other goodies.
>>>>>>>
>>>>>>> But I could argue that we've made DOM into an evrp pass without
>>>>>>> noticing.  The last item (c) is particularly invasive because these
>>>>>>> exported ranges show up in other passes unexpectedly.  For instance, I
>>>>>>> saw an RTL pass at -O1 miss an optimization because it was dependent
>>>>>>> on some global range being set.  IMO, DOM should not export global
>>>>>>> ranges it discovered during its walk (do one thing and do it well),
>>>>>>> but I leave it to you experts to pontificate.
>>>>>> All true.  But I don't think we've got many, if any, hard dependencies
>>>>>> on those behaviors.
>>>>>>
>>>>>>>
>>>>>>> The attached patch is rather trivial.  It's mostly deleting state.  It
>>>>>>> seems DOM spends a lot of time massaging the IL so that it can fold
>>>>>>> conditionals or thread paths.  None of this is needed, because the
>>>>>>> ranger can do all of this.  Well, except floats, but...
>>>>>> Massaging the IL should only take two forms IIRC.
>>>>>>
>>>>>> First, if we have a simplification we can do.  That could be const/copy
>>>>>> propagation, replacing an expression with an SSA_NAME or constant and
>>>>>> the like.  It doesn't massage the IL just to massage the IL.
>>>>>>
>>>>>> Second, we do temporarily copy propagate the current known values of an
>>>>>> SSA name into use points and then see if that allows us to determine if
>>>>>> a statement is already in the hash tables.  But we undo that so that
>>>>>> nobody should see that temporary change in state.
>>>>>
>>>>> Are you sure we still do that?  I can't find it at least.
>>>>
>>>> I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
>>>> copy propagation that happens in the DOM's use of the threader:
>>>>
>>>>         /* Make a copy of the uses & vuses into USES_COPY, then cprop into
>>>>            the operands.  */
>>>>         FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>>>>           {
>>>>             tree tmp = NULL;
>>>>             tree use = USE_FROM_PTR (use_p);
>>>>
>>>>             copy[i++] = use;
>>>>             if (TREE_CODE (use) == SSA_NAME)
>>>>           tmp = SSA_NAME_VALUE (use);
>>>>             if (tmp)
>>>>           SET_USE (use_p, tmp);
>>>>           }
>>>>
>>>>         cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
>>>>
>>>>         /* Restore the statement's original uses/defs.  */
>>>>         i = 0;
>>>>         FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>>>>           SET_USE (use_p, copy[i++]);
>>>
>>> Ah, likely.  These days we'd likely use a gimple_match_op but then
>>> this seems heavily abstracted, no idea where simplifier->simplify
>>> might lead to ;)
>>> I'm also not sure why the threader would do the valueization here and
>>> not the simplify() function (and lookup_avail_expr misses an 'exploded' operand
>>> lookup as well).  Lot's of legacy code ;)
>>
>> Yes, there's a lot of legacy code I've left mostly alone.
>>
>> There are two copies of simplify() now, the DOM version
>> (dom_jt_simplifier::simplify) and the VRP version
>> (hybrid_jt_simplifier::simplify).  Each do slightly different things, as
>> has always been the case.  It's just that the separation is now explicit.
>>
>> No idea what's up with the valueization either.  The VRP version doesn't
>> need any of this valuezation or on the side structures.  You just ask
>> the range of a stmt on a path and it gives you an answer.
> 
> Yeah, but it doesn't "simplify", it uses ranger to do constant folding
> ... (ick).
> For random expressions I'd have used gimple_simplify (in fact it somehow
> tries to do value-numbering or sth like that to derive new equivalences).

The ranger is read-only.  It is not folding anything.  The simplify() 
callback is only returning the singleton the conditional resolves to (1 
or 0 iirc).  It is up to the caller (the forward threader in this case) 
to do any changes.  This is how it always has been with either evrp, or 
VRP, or the const/copies/avails clients.

> 
>>>
>>> But I think the above is not going to be an issue unless ranger runs in
>>> circles around backedges, arriving at this very same stmt again?  A way
>>> out might be to copy the stmt to the stack, adjust operands and use that
>>> for the simplify entry.
>>
>> If you look at the patch I sent Jeff, you'll see that I've removed most
>> of what's in that function.  There's no need to propagate anything.  The
>> ranger can simplify the final conditional without having to set up anything.
> 
> So maybe we can remove all that code (jt_state::register_equivs_stmt).

That's the plan!  But for that to happen we need to remove the evrp use 
in DOM and its threader.  I've done most of the work in the patch, but 
it still needs some TLC.  I'm unlikely to have time to finish it in this 
release, as I'm trying to remove the VRP threader altogether.

Aldy
  

On 10/21/21 3:43 PM, Jeff Law wrote:
> 
> 
> On 10/21/2021 6:56 AM, Aldy Hernandez wrote:
>> On Thu, Oct 21, 2021 at 12:20 PM Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Wed, Oct 20, 2021 at 10:58 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>>>
>>>>
>>>> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>>>>>
>>>>> On 10/18/21 12:52 AM, Jeff Law wrote:
>>>>>>
>>>>>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>>>>>> The following patch converts the strlen pass from evrp to ranger,
>>>>>>> leaving DOM as the last remaining user.
>>>>>> So is there any reason why we can't convert DOM as well?   DOM's use
>>>>>> of EVRP is pretty limited.  You've mentioned FP bits before, but my
>>>>>> recollection is those are not part of the EVRP analysis DOM uses.
>>>>>> Hell, give me a little guidance and I'll do the work...
>>>>> Not only will I take you up on that offer, but I can provide 90% of
>>>>> the work.  Here be dragons, though (well, for me, maybe not for you 
>>>>> ;-)).
>>>>>
>>>>> DOM is actually an evrp pass at -O1 in disguise.  The reason it really
>>>>> is a covert evrp pass is because:
>>>>>
>>>>> a) It calls extract_range_from_stmt on each statement.
>>>>>
>>>>> b) It folds conditionals with simplify_using_ranges.
>>>>>
>>>>> c) But most importantly, it exports discovered ranges when it's done
>>>>> (evrp_range_analyzer(true)).
>>>>>
>>>>> If you look at the evrp pass, you'll notice that that's basically what
>>>>> it does, albeit with the substitute and fold engine, which also calls
>>>>> gimple fold plus other goodies.
>>>>>
>>>>> But I could argue that we've made DOM into an evrp pass without
>>>>> noticing.  The last item (c) is particularly invasive because these
>>>>> exported ranges show up in other passes unexpectedly.  For instance, I
>>>>> saw an RTL pass at -O1 miss an optimization because it was dependent
>>>>> on some global range being set.  IMO, DOM should not export global
>>>>> ranges it discovered during its walk (do one thing and do it well),
>>>>> but I leave it to you experts to pontificate.
>>>> All true.  But I don't think we've got many, if any, hard dependencies
>>>> on those behaviors.
>>>>
>>>>> The attached patch is rather trivial.  It's mostly deleting state.  It
>>>>> seems DOM spends a lot of time massaging the IL so that it can fold
>>>>> conditionals or thread paths.  None of this is needed, because the
>>>>> ranger can do all of this.  Well, except floats, but...
>>>> Massaging the IL should only take two forms IIRC.
>>>>
>>>> First, if we have a simplification we can do.  That could be const/copy
>>>> propagation, replacing an expression with an SSA_NAME or constant and
>>>> the like.  It doesn't massage the IL just to massage the IL.
>>>>
>>>> Second, we do temporarily copy propagate the current known values of an
>>>> SSA name into use points and then see if that allows us to determine if
>>>> a statement is already in the hash tables.  But we undo that so that
>>>> nobody should see that temporary change in state.
>>> Are you sure we still do that?  I can't find it at least.
>> I couldn't either, but perhaps what Jeff is referring to is the ad-hoc
>> copy propagation that happens in the DOM's use of the threader:
>>
>>        /* Make a copy of the uses & vuses into USES_COPY, then cprop into
>>           the operands.  */
>>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>>          {
>>            tree tmp = NULL;
>>            tree use = USE_FROM_PTR (use_p);
>>
>>            copy[i++] = use;
>>            if (TREE_CODE (use) == SSA_NAME)
>>          tmp = SSA_NAME_VALUE (use);
>>            if (tmp)
>>          SET_USE (use_p, tmp);
>>          }
>>
>>        cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
>>
>>        /* Restore the statement's original uses/defs.  */
>>        i = 0;
>>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>>          SET_USE (use_p, copy[i++]);
> Exactly what I was referring to.  It may be worth an experiment -- I 
> can't recall when this code went in.  It might be a remnant from the 
> original threader that pre-dates block copying.  In that world we had to 
> look up expressions in the table as part of the step to verify that we 
> could safely ignore statements at the start of a block.
> 
> Or it could be something that was added to improve threading when the 
> condition we're trying to thread through is partially redundant on the 
> thread path.  This would allow us to discover that partial redundancy 
> and exploit it for threading.
> 
> In either case this code may have outlived its usefulness.  I wonder 
> what would happen if we just took it out.

Look at the patch I sent you.  I rip most of it out, as ranger doesn't 
need it.  Perhaps DOM+evrp+threader doesn't either??

Aldy
  

On 10/21/2021 1:42 AM, Aldy Hernandez wrote:
>> Massaging the IL should only take two forms IIRC.
>>
>> First, if we have a simplification we can do.  That could be const/copy
>> propagation, replacing an expression with an SSA_NAME or constant and
>> the like.  It doesn't massage the IL just to massage the IL.
>>
>> Second, we do temporarily copy propagate the current known values of an
>> SSA name into use points and then see if that allows us to determine if
>> a statement is already in the hash tables.  But we undo that so that
>> nobody should see that temporary change in state.
>>
>> Finally, it does create some expressions & statements on the fly to
>> enter them into the tables.  For example, if it sees a store, it'll
>> create a load with the source & dest interchanged and enter that into
>> the expression table.  But none of this stuff ever shows up in the IL.
>> It's just to create entries in the expression tables.
>>
>> So ITSM the only real concern would be if those temporary const/copy
>> propagations were still in the IL and we called back into Ranger and it
>> poked at that data somehow.
> Hmmm, this is all very good insight.  Thanks.
>
> One thing that would have to be adjusted then is remove the
> enable_ranger() call in the patch.  This sets a global ranger, and
> there are users of get_range_query() that will use it to get on-demand
> ranges.  One such use that I added was ssa_name_has_boolean_range in
> tree-ssa-dom.c.  This means that if the IL has been temporarily
> changed, this function can and will use the global ranger.  The
> alternative here would be to just create a new local ranger:
>
> -  gimple_ranger *ranger = enable_ranger (fun);
> +  gimple_ranger *ranger = new gimple_ranger;
>
> and then obviously deallocate it at the disable_ranger call site.
>
> This will cause any users of get_range_query() in the compiler to just
> use global ranges.  Hopefully, none of these downstream users of
> get_range_query() from DOM need context sensitive results.
> ssa_name_has_boolean_range??
>
> I think what you'd need to do is check that there are no calls to the
> ranger from cprop_into_stmt (?? this is the place where IL changes??),
> until wherever the undoing happens (I couldn't find it).  I see a call
> to simplify_using_ranges in optimize_stmt that looks like it could be
> called with the IL in mid-flight.  Maybe this call needs to happen
> before the IL is altered?
>
>> So if we're referring to those temporary const/copy propagations
>> "escaping" into Ranger, then I would fully expect that to cause
>> problems.  Essentially they're path sensitive const/copy propagations
>> and may not be valid on all the paths through the CFG to the statement
>> where the propagation occurs
> Yeah.  disabling the global ranger should help, plus making sure you
> don't use the ranger in the midst of the path sensitive changes.
I think we should first try to remove those temporary const/copy 
propagations.  As I noted in a different follow-up, I can't remember if 
they were done as part of the original non-copying threader or if they 
enabled further optimizations in the copying threader.  If its the 
former, then they can go away and that would be my preference. I'll try 
to poke at that over the weekend.

jeff
  

On Fri, Oct 15, 2021 at 12:39 PM Aldy Hernandez <aldyh@redhat.com> wrote:

> Also, I am PINGing patch 0002, which is the strlen pass conversion to
> the ranger.  As mentioned, this is just a change from an evrp client to
> a ranger client.  The APIs are exactly the same, and besides, the evrp
> analyzer is deprecated and slated for removal.  OK for trunk?

PING*2
  

On 10/21/2021 12:20 PM, Jeff Law wrote:
>
>>
>>> So if we're referring to those temporary const/copy propagations
>>> "escaping" into Ranger, then I would fully expect that to cause
>>> problems.  Essentially they're path sensitive const/copy propagations
>>> and may not be valid on all the paths through the CFG to the statement
>>> where the propagation occurs
>> Yeah.  disabling the global ranger should help, plus making sure you
>> don't use the ranger in the midst of the path sensitive changes.
> I think we should first try to remove those temporary const/copy 
> propagations.  As I noted in a different follow-up, I can't remember 
> if they were done as part of the original non-copying threader or if 
> they enabled further optimizations in the copying threader.  If its 
> the former, then they can go away and that would be my preference. 
> I'll try to poke at that over the weekend.
OK.  So those temporary propagations are still useful.  Here's a simple 
example (pr36550, but there are others):


[ ... ]
;;   basic block 3, loop depth 0, count 536870912 (estimated locally), 
maybe hot
;;    prev block 2, next block 4, flags: (NEW, VISITED)
;;    pred:       2 [50.0% (guessed)]  count:536870912 (estimated 
locally) (TRUE_VALUE,EXECUTABLE)
   # VUSE <.MEM_10>
   _20 = *argv_12(D);
   if (_20 != 0B)
     goto <bb 4>; [70.00%]
   else
     goto <bb 7>; [30.00%]
;;    succ:       4 [70.0% (guessed)]  count:375809640 (estimated 
locally) (TRUE_VALUE,EXECUTABLE)
;;                7 [30.0% (guessed)]  count:161061272 (estimated 
locally) (FALSE_VALUE,EXECUTABLE)

[ ... ]

;;   basic block 7, loop depth 0, count 536763538 (estimated locally), 
maybe hot
;;    prev block 6, next block 8, flags: (NEW, VISITED)
;;    pred:       3 [30.0% (guessed)]  count:161061272 (estimated 
locally) (FALSE_VALUE,EXECUTABLE)
;;                4 [always]  count:375809640 (estimated locally) 
(FALLTHRU,EXECUTABLE)
   # argv_32 = PHI <argv_12(D)(3), argv_21(4)>
   # bug_33 = PHI <bug_16(D)(3), bug_22(4)>
   # VUSE <.MEM_10>
   _3 = *argv_32;
   if (_3 == 0B)
     goto <bb 9>; [18.09%]
   else
     goto <bb 8>; [81.91%]
;;    succ:       9 [18.1% (guessed)]  count:97100524 (estimated 
locally) (TRUE_VALUE,EXECUTABLE)
;;                8 [81.9% (guessed)]  count:439663014 (estimated 
locally) (FALSE_VALUE,EXECUTABLE)


So when we reach block 7 directly from block 3 we'll have _20 = 
*argv_12(MEM_10) = _20 in the expression hash table and _20 = 0 in the 
const/copies table.

The first statement in block #7 loads *argv_32.  Without the temporary 
propagation we'll lookup *argv_32(MEM_10) in the hash table which misses 
and we're unable to thread the subsequent conditional in block #7.

With the temporary propagation instead of looking up *argv_32(MEM_10), 
we propagate argv_12 for argv32 and lookup *argv32(MEM_10) which hits 
with the LHS value _20 which we then lookup in const/copies getting the 
constant 0.   Thus we know *argv_32 will have the value 0 when block 7 
is reached directly via block 3.  That in turn allows us to know that 
the conditional at the end of block #7 is threadable when reached via 
block #3.

In this particular testcase we end up getting a failure because... 
drumroll.... the failure to thread 3->7->9 leaves an infeasible path in 
the CFG which in turn causes a bogus Wuninitialized warning.

Instead of actually propagating the arguments into the statement, we 
could revamp the hashing bits so that they used the data from the 
const/copy tables.    That would avoid twiddling the IL.  Though I'm 
still not sure how the IL twiddling could be escaping at this point.

jeff
  

On 10/23/2021 3:32 PM, Jeff Law wrote:
>
>
> On 10/21/2021 12:20 PM, Jeff Law wrote:
>>
>>>
>>>> So if we're referring to those temporary const/copy propagations
>>>> "escaping" into Ranger, then I would fully expect that to cause
>>>> problems.  Essentially they're path sensitive const/copy propagations
>>>> and may not be valid on all the paths through the CFG to the statement
>>>> where the propagation occurs
>>> Yeah.  disabling the global ranger should help, plus making sure you
>>> don't use the ranger in the midst of the path sensitive changes.
>> I think we should first try to remove those temporary const/copy 
>> propagations.  As I noted in a different follow-up, I can't remember 
>> if they were done as part of the original non-copying threader or if 
>> they enabled further optimizations in the copying threader.  If its 
>> the former, then they can go away and that would be my preference. 
>> I'll try to poke at that over the weekend.
> OK.  So those temporary propagations are still useful.  Here's a 
> simple example (pr36550, but there are others):
Actually, isn't pr36550 the one you already noted?

I saw a few other issues when I just removed that chunk of code.

First, we get an *execution* failure in c-torture/builtins/<something>

That one was exceedingly strange.  I didn't save it, but it'll almost 
definitely raise its ugly head again.

Wnon-null-4.C.  We fail to thread a path and as a result trigger a bogus 
warning

One of the other W* tests failed with a bogus warning too.  But it's 
fixed by some pending work from Martin S, so I didn't worry much about it.

So in all, not too bad.  I may do some instrumentation for the pr36550 
issue -- while it's not showing a lot of fallout in the testsuite, it 
would be interesting to see how it affects codegen on gcc itself.

Jeff
  

On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>
>
> On 10/18/21 12:52 AM, Jeff Law wrote:
>>
>>
>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>> The following patch converts the strlen pass from evrp to ranger,
>>> leaving DOM as the last remaining user.
>> So is there any reason why we can't convert DOM as well?   DOM's use 
>> of EVRP is pretty limited.  You've mentioned FP bits before, but my 
>> recollection is those are not part of the EVRP analysis DOM uses. 
>> Hell, give me a little guidance and I'll do the work...
>
> Not only will I take you up on that offer, but I can provide 90% of 
> the work.  Here be dragons, though (well, for me, maybe not for you ;-)).
[ ... ]
So the failure I see it a bootstrap comparison failure affecting 
omp-expand.c and cp/cp-gimplify.c.  We end up generating different code 
with and without debug symbols.

The real differences start in dom2 (I guess that's a positive since 
that's the pass the patch changes).  Stripping away the DEBUG statements 
in the IL, then diffing the .dom2 output shows this:
*************** Optimizing block #35
*** 2133,2138 ****
--- 2133,2139 ----
   LKUP STMT loop_1045 = PHI <single_outer_732, single_outer_732>
   2>>> STMT loop_1045 = PHI <single_outer_732, single_outer_732>
   <<<< STMT loop_1045 = PHI <single_outer_732, single_outer_732>
+   Replaced 'loop_1045' with variable 'single_outer_732'
    Registering value_relation (loop_1045 == single_outer_732) (bb35) at 
loop_1045 = PHI <single_outer_732(32), single_outer_732(34)>
   Optimizing statement if (loop_1045 != 0B)
     Replaced 'loop_1045' with variable 'single_outer_732'
*************** Optimizing statement if (loop_1045 != 0B
*** 2140,2156 ****
   Visiting conditional with predicate: if (single_outer_732 != 0B)

   With known ranges
!       single_outer_732: struct loop * [1B, +INF]

! Predicate evaluates to: 1
! 0>>> COPY loop_1045 = 0B
! <<<< COPY loop_1045 = 0B


   Optimizing block #565

! 1>>> STMT 1 = loop_1045 ne_expr 0B
! 1>>> STMT 0 = loop_1045 eq_expr 0B


   Optimizing block #36
--- 2141,2158 ----
   Visiting conditional with predicate: if (single_outer_732 != 0B)

   With known ranges
!       single_outer_732: struct loop * VARYING

! Predicate evaluates to: DON'T KNOW
! LKUP STMT single_outer_732 ne_expr 0B
! 0>>> COPY single_outer_732 = 0B
! <<<< COPY single_outer_732 = 0B


   Optimizing block #565

! 1>>> STMT 1 = single_outer_732 ne_expr 0B
! 1>>> STMT 0 = single_outer_732 eq_expr 0B


   Optimizing block #36


The first hunk is the stage1 compiler, the second is the stage2 
compiler.  Stage2 does a replacement of the LHS with the RHS of a 
generate PHI.  But the stage1 compiler is able to statically compute a 
test while the stage2 compiler is not.  And things cascade from there.

I think all that means there's some kind of inconsistency in the 
const_and_copies table between the stage1 and stage2 compilers.  Not 
sure how that's possible, but that's what the signs point to.

jeff
  

On 10/24/2021 8:15 PM, Jeff Law wrote:
>
>
> On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
>>
>>
>> On 10/18/21 12:52 AM, Jeff Law wrote:
>>>
>>>
>>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
>>>> The following patch converts the strlen pass from evrp to ranger,
>>>> leaving DOM as the last remaining user.
>>> So is there any reason why we can't convert DOM as well? DOM's use 
>>> of EVRP is pretty limited.  You've mentioned FP bits before, but my 
>>> recollection is those are not part of the EVRP analysis DOM uses. 
>>> Hell, give me a little guidance and I'll do the work...
>>
>> Not only will I take you up on that offer, but I can provide 90% of 
>> the work.  Here be dragons, though (well, for me, maybe not for you 
>> ;-)).
> [ ... ]
> So the failure I see it a bootstrap comparison failure affecting 
> omp-expand.c and cp/cp-gimplify.c.  We end up generating different 
> code with and without debug symbols.
Replying to myself....


So we're getting different results from a call to fold_range_internal 
for this statement in bb #35 of expand_omp_target:

(gdb) p debug_gimple_stmt (stmt)
if (loop_171 != 0B)


259         res = fold_range_internal (r, s, NULL_TREE);
(gdb) n
283       if (idx)
(gdb) p res
$60 = true
(gdb) p r
$61 = (irange &) @0x7fffffffdb20: {m_num_ranges = 1 '\001',
   m_max_ranges = 2 '\002', m_kind = VR_RANGE, m_base = 0x7fffffffdb30}


vs

259         res = fold_range_internal (r, s, NULL_TREE);
(gdb)
283       if (idx)
(gdb) p res
$16 = true
(gdb) p r
$17 = (irange &) @0x7fffffffdba0: {m_num_ranges = 1 '\001', m_max_ranges 
= 2 '\002', m_kind = VR_VARYING,
   m_base = 0x7fffffffdbb0}

Anyway, not sure when I'll be able to look at this again, perhaps 
Wednesday.  But my sense is something isn't right WRT the range of loop_171.

Jeff
  

On Mon, Oct 25, 2021 at 6:42 AM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 10/24/2021 8:15 PM, Jeff Law wrote:
> >
> >
> > On 10/18/2021 2:17 AM, Aldy Hernandez wrote:
> >>
> >>
> >> On 10/18/21 12:52 AM, Jeff Law wrote:
> >>>
> >>>
> >>> On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
> >>>> The following patch converts the strlen pass from evrp to ranger,
> >>>> leaving DOM as the last remaining user.
> >>> So is there any reason why we can't convert DOM as well? DOM's use
> >>> of EVRP is pretty limited.  You've mentioned FP bits before, but my
> >>> recollection is those are not part of the EVRP analysis DOM uses.
> >>> Hell, give me a little guidance and I'll do the work...
> >>
> >> Not only will I take you up on that offer, but I can provide 90% of
> >> the work.  Here be dragons, though (well, for me, maybe not for you
> >> ;-)).
> > [ ... ]
> > So the failure I see it a bootstrap comparison failure affecting
> > omp-expand.c and cp/cp-gimplify.c.  We end up generating different
> > code with and without debug symbols.
> Replying to myself....
>
>
> So we're getting different results from a call to fold_range_internal
> for this statement in bb #35 of expand_omp_target:
>
> (gdb) p debug_gimple_stmt (stmt)
> if (loop_171 != 0B)
>
>
> 259         res = fold_range_internal (r, s, NULL_TREE);
> (gdb) n
> 283       if (idx)
> (gdb) p res
> $60 = true
> (gdb) p r
> $61 = (irange &) @0x7fffffffdb20: {m_num_ranges = 1 '\001',
>    m_max_ranges = 2 '\002', m_kind = VR_RANGE, m_base = 0x7fffffffdb30}
>
>
> vs
>
> 259         res = fold_range_internal (r, s, NULL_TREE);
> (gdb)
> 283       if (idx)
> (gdb) p res
> $16 = true
> (gdb) p r
> $17 = (irange &) @0x7fffffffdba0: {m_num_ranges = 1 '\001', m_max_ranges
> = 2 '\002', m_kind = VR_VARYING,
>    m_base = 0x7fffffffdbb0}
>
> Anyway, not sure when I'll be able to look at this again, perhaps
> Wednesday.  But my sense is something isn't right WRT the range of loop_171.

You can print the range in gdb by calling debug(r) or alternatively r->debug().

It'd be interesting to see why the statement got folded to two
different ranges.  Did the IL change?  Was a global range recorded in
SSA_NAME_RANGE_INFO that perhaps the ranger picked up?  Actually, even
if the IL changed, it'd be interesting to see what exactly caused the
disparity.

Can you call gimple_ranger::dump_bb() on the problematic BB on both
compiles to see what the ranger sees for that BB?

You could also call debug_ranger() from within gdb and get a dump of
what a fresh ranger would be able to calculate with the current IL.
Try it on both compiles and send it to us, if you don't want to spam
the list.

Thanks.
Aldy
  

On Fri, Oct 15, 2021, 12:39 Aldy Hernandez <aldyh@redhat.com> wrote:

>
>
> On 10/15/21 2:47 AM, Andrew MacLeod wrote:
> > On 10/14/21 6:07 PM, Martin Sebor via Gcc-patches wrote:
> >> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
> >>> We seem to be passing a lot of context around in the strlen code.  I
> >>> certainly don't want to contribute to more.
> >>>
> >>> Most of the handle_* functions are passing the gsi as well as either
> >>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
> >>> of that in the strlen pass object (well, the dom walker object, but we
> >>> can rename it to be less dom centric)?
> >>>
> >>> Something like the attached (untested) patch could be the basis for
> >>> further cleanups.
> >>>
> >>> Jakub, would this line of work interest you?
> >>
> >> You didn't ask me but since no one spoke up against it let me add
> >> some encouragement: this is exactly what I was envisioning and in
> >> line with other such modernization we have been doing elsewhere.
> >> Could you please submit it for review?
> >>
> >> Martin
> >
> > I'm willing to bet he didn't submit it for review because he doesn't
> > have time this release to polish and track it...  (I think the threader
> > has been quite consuming).  Rather, it was offered as a starting point
> > for someone else who might be interested in continuing to pursue this
> > work...  *everyone* is interested in cleanup work others do :-)
>
> Exactly.  There's a lot of work that could be done in this area, and I'm
> trying to avoid the situation with the threaders where what started as
> refactoring ended up with me basically owning them ;-).
>
> That being said, I there are enough cleanups that are useful on their
> own.  I've removed all the passing around of GSIs, as well as ptr_qry,
> with the exception of anything dealing with the sprintf pass, since it
> has a slightly different interface.
>
> This is patch 0001, which I'm formally submitting for inclusion.  No
> functional changes with this patch.  OK for trunk?
>
> Also, I am PINGing patch 0002, which is the strlen pass conversion to
> the ranger.  As mentioned, this is just a change from an evrp client to
> a ranger client.  The APIs are exactly the same, and besides, the evrp
> analyzer is deprecated and slated for removal.  OK for trunk?
>

Ping * 2 for patch 2, although I'm sure it needs massaging after Martin
Sebor's in the same area.

Aldy
  

On 10/15/2021 4:39 AM, Aldy Hernandez wrote:
>
>
> On 10/15/21 2:47 AM, Andrew MacLeod wrote:
>> On 10/14/21 6:07 PM, Martin Sebor via Gcc-patches wrote:
>>> On 10/9/21 12:47 PM, Aldy Hernandez via Gcc-patches wrote:
>>>> We seem to be passing a lot of context around in the strlen code.  I
>>>> certainly don't want to contribute to more.
>>>>
>>>> Most of the handle_* functions are passing the gsi as well as either
>>>> ptr_qry or rvals.  That looks a bit messy.  May I suggest putting all
>>>> of that in the strlen pass object (well, the dom walker object, but we
>>>> can rename it to be less dom centric)?
>>>>
>>>> Something like the attached (untested) patch could be the basis for
>>>> further cleanups.
>>>>
>>>> Jakub, would this line of work interest you?
>>>
>>> You didn't ask me but since no one spoke up against it let me add
>>> some encouragement: this is exactly what I was envisioning and in
>>> line with other such modernization we have been doing elsewhere.
>>> Could you please submit it for review?
>>>
>>> Martin
>>
>> I'm willing to bet he didn't submit it for review because he doesn't 
>> have time this release to polish and track it...  (I think the 
>> threader has been quite consuming).  Rather, it was offered as a 
>> starting point for someone else who might be interested in continuing 
>> to pursue this work...  *everyone* is interested in cleanup work 
>> others do :-)
>
> Exactly.  There's a lot of work that could be done in this area, and 
> I'm trying to avoid the situation with the threaders where what 
> started as refactoring ended up with me basically owning them ;-).
>
> That being said, I there are enough cleanups that are useful on their 
> own.  I've removed all the passing around of GSIs, as well as ptr_qry, 
> with the exception of anything dealing with the sprintf pass, since it 
> has a slightly different interface.
>
> This is patch 0001, which I'm formally submitting for inclusion. No 
> functional changes with this patch.  OK for trunk?
>
> Also, I am PINGing patch 0002, which is the strlen pass conversion to 
> the ranger.  As mentioned, this is just a change from an evrp client 
> to a ranger client.  The APIs are exactly the same, and besides, the 
> evrp analyzer is deprecated and slated for removal. OK for trunk?
>
> Aldy
>
> 0001-Convert-strlen-pass-from-evrp-to-ranger.patch
>
>  From 152bc3a1dad9a960b7c0c53c65d6690532d9da5a Mon Sep 17 00:00:00 2001
> From: Aldy Hernandez<aldyh@redhat.com>
> Date: Fri, 8 Oct 2021 15:54:23 +0200
> Subject: [PATCH] Convert strlen pass from evrp to ranger.
>
> The following patch converts the strlen pass from evrp to ranger,
> leaving DOM as the last remaining user.
>
> No additional cleanups have been done.  For example, the strlen pass
> still has uses of VR_ANTI_RANGE, and the sprintf still passes around
> pairs of integers instead of using a proper range.  Fixing this
> could further improve these passes.
>
> Basically the entire patch is just adjusting the calls to range_of_expr
> to include context.  The previous context of si->stmt was mostly
> empty, so not really useful ;-).
>
> With ranger we are now able to remove the range calculation from
> before_dom_children entirely.  Just working with the ranger on-demand
> catches all the strlen and sprintf testcases with the exception of
> builtin-sprintf-warn-22.c which is due to a limitation of the sprintf
> code.  I have XFAILed the test and documented what the problem is.
>
> On a positive note, these changes found two possible sprintf overflow
> bugs in the C++ and Fortran front-ends which I have fixed below.
>
> Tested on x86-64 Linux.
>
> gcc/ChangeLog:
>
> 	* tree-ssa-strlen.c (compare_nonzero_chars): Pass statement
> 	context to ranger.
> 	(get_addr_stridx): Same.
> 	(get_stridx): Same.
> 	(get_range_strlen_dynamic): Same.
> 	(handle_builtin_strlen): Same.
> 	(handle_builtin_strchr): Same.
> 	(handle_builtin_strcpy): Same.
> 	(maybe_diag_stxncpy_trunc): Same.
> 	(handle_builtin_stxncpy_strncat):
> 	(handle_builtin_memcpy): Same.
> 	(handle_builtin_strcat): Same.
> 	(handle_alloc_call): Same.
> 	(handle_builtin_memset): Same.
> 	(handle_builtin_string_cmp): Same.
> 	(handle_pointer_plus): Same.
> 	(count_nonzero_bytes_addr): Same.
> 	(count_nonzero_bytes): Same.
> 	(handle_store): Same.
> 	(fold_strstr_to_strncmp): Same.
> 	(handle_integral_assign): Same.
> 	(check_and_optimize_stmt): Same.
> 	(class strlen_dom_walker): Replace evrp with ranger.
> 	(strlen_dom_walker::before_dom_children): Remove evrp.
> 	(strlen_dom_walker::after_dom_children): Remove evrp.
> 	* gimple-ssa-warn-access.cc (maybe_check_access_sizes):
> 	Restrict sprintf output.
>
> gcc/cp/ChangeLog:
>
> 	* ptree.c (cxx_print_xnode): Add more space to pfx array.
>
> gcc/fortran/ChangeLog:
>
> 	* misc.c (gfc_dummy_typename): Make sure ts->kind is
> 	non-negative.
>
> gcc/testsuite/ChangeLog:
>
> 	* gcc.dg/tree-ssa/builtin-sprintf-warn-22.c: XFAIL.
OK.  Had I realized 99% was just adding the new argument to a bunch of 
call sites, I would have taken care of it earlier.
jeff