[RFA][PATCH] Convert sprintf warning code to use a dominator walk

[RFA][PATCH] Convert sprintf warning code to use a dominator walk

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 1330 bytes --]


Martin,

I'd like your thoughts on this patch.

One of the things I'm working on is changes that would allow passes that
use dominator walks to trivially perform context sensitive range
analysis as a part of their dominator walk.

As I outlined earlier this would allow us to easily fix the false
positive sprintf warning reported a week or two ago.

This patch converts the sprintf warning code to perform a dominator walk
rather than just walking the blocks in whatever order they appear in the
basic block array.

From an implementation standpoint we derive a new class sprintf_dom_walk
from the dom_walker class.  Like other dom walkers we walk statements
from within the before_dom_children member function.  Very standard stuff.

I moved handle_gimple_call and various dependencies into the
sprintf_dom_walker class to facilitate calling handle_gimple_call from
within the before_dom_children member function.  There's light fallout
in various places where the call_info structure was explicitly expected
to be found in the pass_sprintf_length class, but is now found in the
sprintf_dom_walker class.

This has been bootstrapped and regression tested on x86_64-linux-gnu.
I've also layered my embedded VRP analysis on top of this work and
verified that it does indeed fix the reported false positive.

Thoughts?

Jeff






[-- Attachment #2: P --]
[-- Type: text/plain, Size: 6343 bytes --]


	* gimple-ssa-sprintf.c: Include domwalk.h.
	(class sprintf_dom_walker): New class, derived from dom_walker.
	(sprintf_dom_walker::before_dom_children): New function.
	(struct call_info): Moved into sprintf_dom_walker class
	(compute_formath_length, handle_gimple_call): Likewise.
	(sprintf_length::execute): Call the dominator walker rather
	than walking the statements.

diff --git a/gcc/gimple-ssa-sprintf.c b/gcc/gimple-ssa-sprintf.c
index 9770df7..2223f24 100644
--- a/gcc/gimple-ssa-sprintf.c
+++ b/gcc/gimple-ssa-sprintf.c
@@ -79,6 +79,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "toplev.h"
 #include "substring-locations.h"
 #include "diagnostic.h"
+#include "domwalk.h"
 
 /* The likely worst case value of MB_LEN_MAX for the target, large enough
    for UTF-8.  Ideally, this would be obtained by a target hook if it were
@@ -113,6 +114,19 @@ static int warn_level;
 
 struct format_result;
 
+class sprintf_dom_walker : public dom_walker
+{
+ public:
+  sprintf_dom_walker () : dom_walker (CDI_DOMINATORS) {}
+  ~sprintf_dom_walker () {}
+
+  virtual edge before_dom_children (basic_block);
+  bool handle_gimple_call (gimple_stmt_iterator *);
+
+  struct call_info;
+  bool compute_format_length (call_info &, format_result *);
+};
+
 class pass_sprintf_length : public gimple_opt_pass
 {
   bool fold_return_value;
@@ -135,10 +149,6 @@ public:
       fold_return_value = param;
     }
 
-  bool handle_gimple_call (gimple_stmt_iterator *);
-
-  struct call_info;
-  bool compute_format_length (call_info &, format_result *);
 };
 
 bool
@@ -976,7 +986,7 @@ bytes_remaining (unsigned HOST_WIDE_INT navail, const format_result &res)
 
 /* Description of a call to a formatted function.  */
 
-struct pass_sprintf_length::call_info
+struct sprintf_dom_walker::call_info
 {
   /* Function call statement.  */
   gimple *callstmt;
@@ -2348,7 +2358,7 @@ format_plain (const directive &dir, tree)
    should be diagnosed given the AVAILable space in the destination.  */
 
 static bool
-should_warn_p (const pass_sprintf_length::call_info &info,
+should_warn_p (const sprintf_dom_walker::call_info &info,
 	       const result_range &avail, const result_range &result)
 {
   if (result.max <= avail.min)
@@ -2419,7 +2429,7 @@ should_warn_p (const pass_sprintf_length::call_info &info,
 
 static bool
 maybe_warn (substring_loc &dirloc, location_t argloc,
-	    const pass_sprintf_length::call_info &info,
+	    const sprintf_dom_walker::call_info &info,
 	    const result_range &avail_range, const result_range &res,
 	    const directive &dir)
 {
@@ -2716,7 +2726,7 @@ maybe_warn (substring_loc &dirloc, location_t argloc,
    in *RES.  Return true if the directive has been handled.  */
 
 static bool
-format_directive (const pass_sprintf_length::call_info &info,
+format_directive (const sprintf_dom_walker::call_info &info,
 		  format_result *res, const directive &dir)
 {
   /* Offset of the beginning of the directive from the beginning
@@ -3004,7 +3014,7 @@ format_directive (const pass_sprintf_length::call_info &info,
    the directive.  */
 
 static size_t
-parse_directive (pass_sprintf_length::call_info &info,
+parse_directive (sprintf_dom_walker::call_info &info,
 		 directive &dir, format_result *res,
 		 const char *str, unsigned *argno)
 {
@@ -3431,7 +3441,7 @@ parse_directive (pass_sprintf_length::call_info &info,
    that caused the processing to be terminated early).  */
 
 bool
-pass_sprintf_length::compute_format_length (call_info &info,
+sprintf_dom_walker::compute_format_length (call_info &info,
 					    format_result *res)
 {
   if (dump_file)
@@ -3514,7 +3524,7 @@ get_destination_size (tree dest)
    of its return values.  */
 
 static bool
-is_call_safe (const pass_sprintf_length::call_info &info,
+is_call_safe (const sprintf_dom_walker::call_info &info,
 	      const format_result &res, bool under4k,
 	      unsigned HOST_WIDE_INT retval[2])
 {
@@ -3573,7 +3583,7 @@ is_call_safe (const pass_sprintf_length::call_info &info,
 
 static bool
 try_substitute_return_value (gimple_stmt_iterator *gsi,
-			     const pass_sprintf_length::call_info &info,
+			     const sprintf_dom_walker::call_info &info,
 			     const format_result &res)
 {
   tree lhs = gimple_get_lhs (info.callstmt);
@@ -3690,7 +3700,7 @@ try_substitute_return_value (gimple_stmt_iterator *gsi,
 
 static bool
 try_simplify_call (gimple_stmt_iterator *gsi,
-		   const pass_sprintf_length::call_info &info,
+		   const sprintf_dom_walker::call_info &info,
 		   const format_result &res)
 {
   unsigned HOST_WIDE_INT dummy[2];
@@ -3717,7 +3727,7 @@ try_simplify_call (gimple_stmt_iterator *gsi,
    and gsi_next should not be performed in the caller.  */
 
 bool
-pass_sprintf_length::handle_gimple_call (gimple_stmt_iterator *gsi)
+sprintf_dom_walker::handle_gimple_call (gimple_stmt_iterator *gsi)
 {
   call_info info = call_info ();
 
@@ -3982,6 +3992,24 @@ pass_sprintf_length::handle_gimple_call (gimple_stmt_iterator *gsi)
   return call_removed;
 }
 
+edge
+sprintf_dom_walker::before_dom_children (basic_block bb)
+{
+  for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); )
+    {
+      /* Iterate over statements, looking for function calls.  */
+      gimple *stmt = gsi_stmt (si);
+
+      if (is_gimple_call (stmt) && handle_gimple_call (&si))
+	/* If handle_gimple_call returns true, the iterator is
+	   already pointing to the next statement.  */
+	continue;
+
+      gsi_next (&si);
+    }
+  return NULL;
+}
+
 /* Execute the pass for function FUN.  */
 
 unsigned int
@@ -3989,26 +4017,13 @@ pass_sprintf_length::execute (function *fun)
 {
   init_target_to_host_charmap ();
 
-  basic_block bb;
-  FOR_EACH_BB_FN (bb, fun)
-    {
-      for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); )
-	{
-	  /* Iterate over statements, looking for function calls.  */
-	  gimple *stmt = gsi_stmt (si);
-
-	  if (is_gimple_call (stmt) && handle_gimple_call (&si))
-	    /* If handle_gimple_call returns true, the iterator is
-	       already pointing to the next statement.  */
-	    continue;
+  calculate_dominance_info (CDI_DOMINATORS);
 
-	  gsi_next (&si);
-	}
-    }
+  sprintf_dom_walker sprintf_dom_walker;
+  sprintf_dom_walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
 
   /* Clean up object size info.  */
   fini_object_sizes ();
-
   return 0;
 }
 

Re: [RFA][PATCH] Convert sprintf warning code to use a dominator walk

[Martin Sebor]

On 10/23/2017 05:14 PM, Jeff Law wrote:
>
> Martin,
>
> I'd like your thoughts on this patch.
>
> One of the things I'm working on is changes that would allow passes that
> use dominator walks to trivially perform context sensitive range
> analysis as a part of their dominator walk.
>
> As I outlined earlier this would allow us to easily fix the false
> positive sprintf warning reported a week or two ago.
>
> This patch converts the sprintf warning code to perform a dominator walk
> rather than just walking the blocks in whatever order they appear in the
> basic block array.
>
> From an implementation standpoint we derive a new class sprintf_dom_walk
> from the dom_walker class.  Like other dom walkers we walk statements
> from within the before_dom_children member function.  Very standard stuff.
>
> I moved handle_gimple_call and various dependencies into the
> sprintf_dom_walker class to facilitate calling handle_gimple_call from
> within the before_dom_children member function.  There's light fallout
> in various places where the call_info structure was explicitly expected
> to be found in the pass_sprintf_length class, but is now found in the
> sprintf_dom_walker class.
>
> This has been bootstrapped and regression tested on x86_64-linux-gnu.
> I've also layered my embedded VRP analysis on top of this work and
> verified that it does indeed fix the reported false positive.
>
> Thoughts?

If it lets us improve the quality of the range information I can't
think of a downside.

Besides the sprintf pass, a number of other areas depend on ranges,
most of all the -Wstringop-overflow and truncation warnings and
now -Wrestrict (once my enhancement is approved).  It would be nice
to be able to get the same improvements there.  Does it mean that
those warnings will need to be moved into a standalone pass?  (I'm
not opposed to it, just wondering what to expect if this is
the route we want to go.)

Martin

Re: [RFA][PATCH] Convert sprintf warning code to use a dominator walk

[Jeff Law]

On 10/24/2017 11:35 AM, Martin Sebor wrote:
> On 10/23/2017 05:14 PM, Jeff Law wrote:
>>
>> Martin,
>>
>> I'd like your thoughts on this patch.
>>
>> One of the things I'm working on is changes that would allow passes that
>> use dominator walks to trivially perform context sensitive range
>> analysis as a part of their dominator walk.
>>
>> As I outlined earlier this would allow us to easily fix the false
>> positive sprintf warning reported a week or two ago.
>>
>> This patch converts the sprintf warning code to perform a dominator walk
>> rather than just walking the blocks in whatever order they appear in the
>> basic block array.
>>
>> From an implementation standpoint we derive a new class sprintf_dom_walk
>> from the dom_walker class.  Like other dom walkers we walk statements
>> from within the before_dom_children member function.  Very standard
>> stuff.
>>
>> I moved handle_gimple_call and various dependencies into the
>> sprintf_dom_walker class to facilitate calling handle_gimple_call from
>> within the before_dom_children member function.  There's light fallout
>> in various places where the call_info structure was explicitly expected
>> to be found in the pass_sprintf_length class, but is now found in the
>> sprintf_dom_walker class.
>>
>> This has been bootstrapped and regression tested on x86_64-linux-gnu.
>> I've also layered my embedded VRP analysis on top of this work and
>> verified that it does indeed fix the reported false positive.
>>
>> Thoughts?
> 
> If it lets us improve the quality of the range information I can't
> think of a downside.
It's potentially slower simply because the domwalk interface is more
expensive than just iterating over the blocks with FOR_EACH_BB.  But
that's about it.  I think the ability to get more accurate range
information will make the compile-time hit worth it.

> 
> Besides the sprintf pass, a number of other areas depend on ranges,
> most of all the -Wstringop-overflow and truncation warnings and
> now -Wrestrict (once my enhancement is approved).  It would be nice
> to be able to get the same improvements there.  Does it mean that
> those warnings will need to be moved into a standalone pass?  (I'm
> not opposed to it, just wondering what to expect if this is
> the route we want to go.)
They don't necessarily have to be a standalone pass -- they just have to
be implementable as part of a dominator walk to get the cheap context
sensitive range data.

So IIRC you've got some code to add additional warnings within the
strlen pass.  That pass is already a dominator walk.  In theory you'll
just add a member to the strlen_dom_walker class, then a call in
before_dom_children and after_dom_children virtuals and you should be
able to query the context sensitive range information.

For warnings that occur in code that is not easily structured as a
dominator walk, Andrew's work will definitely be a better choice.

Andrew's work will almost certainly also generate even finer grained
ranges because it can work on an arbitrary path through the CFG rather
than relying on dominance relationships.  Consider

    A
   / \
  B   C
   \ /
    D

Range information implied by the edge A->B is usable within B because
the edge A->B dominates B.  Similarly for range information implied by
A->C being available in C.  But range information implied by A->B is not
available in D because A->B does not dominate D.  SImilarly range
information implied by A->C is not available in D.

I touched on this in a private message recently.  Namely that exploiting
range data in non-dominated blocks feels a *lot* like jump threading and
should likely be structured as a backwards walk query (and thus is more
suitable for Andrew's infrastructure).


jeff

Re: [RFA][PATCH] Convert sprintf warning code to use a dominator walk

[Richard Biener]

On Wed, Oct 25, 2017 at 5:44 PM, Jeff Law <law@redhat.com> wrote:
> On 10/24/2017 11:35 AM, Martin Sebor wrote:
>> On 10/23/2017 05:14 PM, Jeff Law wrote:
>>>
>>> Martin,
>>>
>>> I'd like your thoughts on this patch.
>>>
>>> One of the things I'm working on is changes that would allow passes that
>>> use dominator walks to trivially perform context sensitive range
>>> analysis as a part of their dominator walk.
>>>
>>> As I outlined earlier this would allow us to easily fix the false
>>> positive sprintf warning reported a week or two ago.
>>>
>>> This patch converts the sprintf warning code to perform a dominator walk
>>> rather than just walking the blocks in whatever order they appear in the
>>> basic block array.
>>>
>>> From an implementation standpoint we derive a new class sprintf_dom_walk
>>> from the dom_walker class.  Like other dom walkers we walk statements
>>> from within the before_dom_children member function.  Very standard
>>> stuff.
>>>
>>> I moved handle_gimple_call and various dependencies into the
>>> sprintf_dom_walker class to facilitate calling handle_gimple_call from
>>> within the before_dom_children member function.  There's light fallout
>>> in various places where the call_info structure was explicitly expected
>>> to be found in the pass_sprintf_length class, but is now found in the
>>> sprintf_dom_walker class.
>>>
>>> This has been bootstrapped and regression tested on x86_64-linux-gnu.
>>> I've also layered my embedded VRP analysis on top of this work and
>>> verified that it does indeed fix the reported false positive.
>>>
>>> Thoughts?
>>
>> If it lets us improve the quality of the range information I can't
>> think of a downside.
> It's potentially slower simply because the domwalk interface is more
> expensive than just iterating over the blocks with FOR_EACH_BB.  But
> that's about it.  I think the ability to get more accurate range
> information will make the compile-time hit worth it.
>
>>
>> Besides the sprintf pass, a number of other areas depend on ranges,
>> most of all the -Wstringop-overflow and truncation warnings and
>> now -Wrestrict (once my enhancement is approved).  It would be nice
>> to be able to get the same improvements there.  Does it mean that
>> those warnings will need to be moved into a standalone pass?  (I'm
>> not opposed to it, just wondering what to expect if this is
>> the route we want to go.)
> They don't necessarily have to be a standalone pass -- they just have to
> be implementable as part of a dominator walk to get the cheap context
> sensitive range data.
>
> So IIRC you've got some code to add additional warnings within the
> strlen pass.  That pass is already a dominator walk.  In theory you'll
> just add a member to the strlen_dom_walker class, then a call in
> before_dom_children and after_dom_children virtuals and you should be
> able to query the context sensitive range information.
>
> For warnings that occur in code that is not easily structured as a
> dominator walk, Andrew's work will definitely be a better choice.
>
> Andrew's work will almost certainly also generate even finer grained
> ranges because it can work on an arbitrary path through the CFG rather
> than relying on dominance relationships.  Consider
>
>     A
>    / \
>   B   C
>    \ /
>     D
>
> Range information implied by the edge A->B is usable within B because
> the edge A->B dominates B.  Similarly for range information implied by
> A->C being available in C.  But range information implied by A->B is not
> available in D because A->B does not dominate D.  SImilarly range
> information implied by A->C is not available in D.
>
> I touched on this in a private message recently.  Namely that exploiting
> range data in non-dominated blocks feels a *lot* like jump threading and
> should likely be structured as a backwards walk query (and thus is more
> suitable for Andrew's infrastructure).

On the contrary - with a backward walk you don't know which way to go.
From D to B or to C?  With a forward walk there's no such ambiguity
(unless you start from A).

Note I have patches for EVRP merging ranges from B and C to make
the info available for D but usually there's nothing to recover here
that isn't also valid in A.  Just ranges derived from non-conditional
stmts (by means of exploiting undefined behavior) can help here.

Richard.

>
> jeff

Re: [RFA][PATCH] Convert sprintf warning code to use a dominator walk

[Jeff Law]

On 10/26/2017 03:09 AM, Richard Biener wrote:
> On Wed, Oct 25, 2017 at 5:44 PM, Jeff Law <law@redhat.com> wrote:
>> On 10/24/2017 11:35 AM, Martin Sebor wrote:
>>> On 10/23/2017 05:14 PM, Jeff Law wrote:
>>>>
>>>> Martin,
>>>>
>>>> I'd like your thoughts on this patch.
>>>>
>>>> One of the things I'm working on is changes that would allow passes that
>>>> use dominator walks to trivially perform context sensitive range
>>>> analysis as a part of their dominator walk.
>>>>
>>>> As I outlined earlier this would allow us to easily fix the false
>>>> positive sprintf warning reported a week or two ago.
>>>>
>>>> This patch converts the sprintf warning code to perform a dominator walk
>>>> rather than just walking the blocks in whatever order they appear in the
>>>> basic block array.
>>>>
>>>> From an implementation standpoint we derive a new class sprintf_dom_walk
>>>> from the dom_walker class.  Like other dom walkers we walk statements
>>>> from within the before_dom_children member function.  Very standard
>>>> stuff.
>>>>
>>>> I moved handle_gimple_call and various dependencies into the
>>>> sprintf_dom_walker class to facilitate calling handle_gimple_call from
>>>> within the before_dom_children member function.  There's light fallout
>>>> in various places where the call_info structure was explicitly expected
>>>> to be found in the pass_sprintf_length class, but is now found in the
>>>> sprintf_dom_walker class.
>>>>
>>>> This has been bootstrapped and regression tested on x86_64-linux-gnu.
>>>> I've also layered my embedded VRP analysis on top of this work and
>>>> verified that it does indeed fix the reported false positive.
>>>>
>>>> Thoughts?
>>>
>>> If it lets us improve the quality of the range information I can't
>>> think of a downside.
>> It's potentially slower simply because the domwalk interface is more
>> expensive than just iterating over the blocks with FOR_EACH_BB.  But
>> that's about it.  I think the ability to get more accurate range
>> information will make the compile-time hit worth it.
>>
>>>
>>> Besides the sprintf pass, a number of other areas depend on ranges,
>>> most of all the -Wstringop-overflow and truncation warnings and
>>> now -Wrestrict (once my enhancement is approved).  It would be nice
>>> to be able to get the same improvements there.  Does it mean that
>>> those warnings will need to be moved into a standalone pass?  (I'm
>>> not opposed to it, just wondering what to expect if this is
>>> the route we want to go.)
>> They don't necessarily have to be a standalone pass -- they just have to
>> be implementable as part of a dominator walk to get the cheap context
>> sensitive range data.
>>
>> So IIRC you've got some code to add additional warnings within the
>> strlen pass.  That pass is already a dominator walk.  In theory you'll
>> just add a member to the strlen_dom_walker class, then a call in
>> before_dom_children and after_dom_children virtuals and you should be
>> able to query the context sensitive range information.
>>
>> For warnings that occur in code that is not easily structured as a
>> dominator walk, Andrew's work will definitely be a better choice.
>>
>> Andrew's work will almost certainly also generate even finer grained
>> ranges because it can work on an arbitrary path through the CFG rather
>> than relying on dominance relationships.  Consider
>>
>>     A
>>    / \
>>   B   C
>>    \ /
>>     D
>>
>> Range information implied by the edge A->B is usable within B because
>> the edge A->B dominates B.  Similarly for range information implied by
>> A->C being available in C.  But range information implied by A->B is not
>> available in D because A->B does not dominate D.  SImilarly range
>> information implied by A->C is not available in D.
>>
>> I touched on this in a private message recently.  Namely that exploiting
>> range data in non-dominated blocks feels a *lot* like jump threading and
>> should likely be structured as a backwards walk query (and thus is more
>> suitable for Andrew's infrastructure).
> 
> On the contrary - with a backward walk you don't know which way to go.
> From D to B or to C?  With a forward walk there's no such ambiguity
> (unless you start from A).
> 
> Note I have patches for EVRP merging ranges from B and C to make
> the info available for D but usually there's nothing to recover here
> that isn't also valid in A.  Just ranges derived from non-conditional
> stmts (by means of exploiting undefined behavior) can help here.
My point is the range information that is specific to the A->B edge is
not usable to optimize D because it does not hold on all paths to D.
But it can be used to improve preciseness of warnings for code within D.


It's certainly possible to merge the range information for the A->B edge
and the information for the A->C edge as we enter D (in the original
graph).  For range data implied by the edge traversal I suspect what you
end up is rarely, if ever better than what we had in A.  But if there
are range generating statements within B and C, then unioning those as
we enter D may be useful.

--


If the existence of range information due to the A->B edge would be
useful to optimize D, then what we want to do is duplicate D so that our
CFG looks like

    A
   / \
  B   C
  |   |
  D'  D


Now the range data for the A->B edge dominates D' and we can optimize D'
as a result.

Which is ultimately what we do with jump threading.

Jeff