convert -Wrestrict pass to ranger

[Martin, as the original author of this pass, do you have any concerns?]

This patch converts the -Wrestrict pass to use an on-demand ranger 
instead of global ranges.

No effort was made to convert value_range's into multi-ranges. 
Basically, the places that were using value_range's, and looking at 
kind(), are still doing so.  This can be fixed as a follow-up patch, but 
it's not high on my list.

Note that there are still calls into get_range_info (global range info) 
when no ranger has been passed, because some of these functions are 
called from gimple fold during gimple lowering (builtin expansion as 
well??).

This patch depends on the ranger, and will likely be tweaked before 
going in.

Aldy

     gcc/ChangeLog:

             * calls.c (get_size_range): Adjust to work with ranger.
             * calls.h (get_size_range): Add ranger argument to prototype.
             * gimple-ssa-warn-restrict.c (class wrestrict_dom_walker): 
Remove.
             (check_call): Pull out of wrestrict_dom_walker into a
             static function.
             (wrestrict_dom_walker::before_dom_children): Rename to...
             (wrestrict_walk): ...this.
             (pass_wrestrict::execute): Instantiate ranger.
             (class builtin_memref): Add stmt and query fields.
             (builtin_access::builtin_access): Add range_query field.
             (builtin_memref::builtin_memref): Same.
             (builtin_memref::extend_offset_range): Same.
             (builtin_access::builtin_access): Make work with ranger.
             (wrestrict_dom_walker::check_call): Pull out into...
             (check_call): ...here.
             (check_bounds_or_overlap): Add range_query argument.
             * gimple-ssa-warn-restrict.h (check_bounds_or_overlap):
             Add range_query and gimple stmt arguments.

     gcc/testsuite/ChangeLog:

             * gcc.dg/Wrestrict-22.c: New test.

+}

On 10/5/20 8:50 AM, Aldy Hernandez via Gcc-patches wrote:
> [Martin, as the original author of this pass, do you have any concerns?]
> 

No concerns, just a few minor things.

> This patch converts the -Wrestrict pass to use an on-demand ranger 
> instead of global ranges.
> 
> No effort was made to convert value_range's into multi-ranges. 
> Basically, the places that were using value_range's, and looking at 
> kind(), are still doing so.  This can be fixed as a follow-up patch, but 
> it's not high on my list.
> 
> Note that there are still calls into get_range_info (global range info) 
> when no ranger has been passed, because some of these functions are 
> called from gimple fold during gimple lowering (builtin expansion as 
> well??).
> 
> This patch depends on the ranger, and will likely be tweaked before 
> going in.
> 
> Aldy
> 
>      gcc/ChangeLog:
> 
>              * calls.c (get_size_range): Adjust to work with ranger.
>              * calls.h (get_size_range): Add ranger argument to prototype.
>              * gimple-ssa-warn-restrict.c (class wrestrict_dom_walker): 
> Remove.
>              (check_call): Pull out of wrestrict_dom_walker into a
>              static function.
>              (wrestrict_dom_walker::before_dom_children): Rename to...
>              (wrestrict_walk): ...this.
>              (pass_wrestrict::execute): Instantiate ranger.
>              (class builtin_memref): Add stmt and query fields.
>              (builtin_access::builtin_access): Add range_query field.
>              (builtin_memref::builtin_memref): Same.
>              (builtin_memref::extend_offset_range): Same.
>              (builtin_access::builtin_access): Make work with ranger.
>              (wrestrict_dom_walker::check_call): Pull out into...
>              (check_call): ...here.
>              (check_bounds_or_overlap): Add range_query argument.
>              * gimple-ssa-warn-restrict.h (check_bounds_or_overlap):
>              Add range_query and gimple stmt arguments.
> 
>      gcc/testsuite/ChangeLog:
> 
>              * gcc.dg/Wrestrict-22.c: New test.
> 
> diff --git a/gcc/calls.c b/gcc/calls.c
> index ed4363811c8..c9c71657e54 100644
> --- a/gcc/calls.c
> +++ b/gcc/calls.c
> @@ -58,7 +58,7 @@ along with GCC; see the file COPYING3.  If not see
>   #include "attribs.h"
>   #include "builtins.h"
>   #include "gimple-fold.h"
> -
> +#include "value-query.h"
>   #include "tree-pretty-print.h"
> 
>   /* Like PREFERRED_STACK_BOUNDARY but in units of bytes, not bits.  */
> @@ -1251,7 +1251,8 @@ alloc_max_size (void)
>      functions like memset.  */
> 
>   bool
> -get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
> +get_size_range (range_query *query, tree exp, gimple *stmt, tree range[2],
> +        bool allow_zero /* = false */)
>   {
>     if (!exp)
>       return false;
> @@ -1270,7 +1271,21 @@ get_size_range (tree exp, tree range[2], bool 
> allow_zero /* = false */)
>     enum value_range_kind range_type;
> 
>     if (integral)
> -    range_type = determine_value_range (exp, &min, &max);
> +    {
> +      if (query)
> +    {
> +      value_range vr;
> +      gcc_assert (TREE_CODE (exp) == SSA_NAME
> +              || TREE_CODE (exp) == INTEGER_CST);
> +      gcc_assert (query->range_of_expr (vr, exp, stmt));

Will the call to the function in the assert above not be eliminated
if the assert is turned into a no-op?  If it can't happen (it looks
like it shouldn't anymore), it would still be nice to break it out
of the macro.  Those of us used to the semantics of the C standard
assert macro might wonder.

> +      range_type = vr.kind ();
> +      min = wi::to_wide (vr.min ());
> +      max = wi::to_wide (vr.max ());
> +    }
> +      else
> +    range_type = determine_value_range (exp, &min, &max);
> +
> +    }
>     else
>       range_type = VR_VARYING;
> 
> @@ -1351,6 +1366,13 @@ get_size_range (tree exp, tree range[2], bool 
> allow_zero /* = false */)
>     return true;
>   }
> 
> +bool
> +get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
> +{
> +  return get_size_range (/*query=*/NULL, exp, /*stmt=*/NULL, range,
> +             allow_zero);
> +}
> +

I realize its purpose is obvious from the context but can you please
add a brief comment above the new function?

>   /* Diagnose a call EXP to function FN decorated with attribute alloc_size
>      whose argument numbers given by IDX with values given by ARGS exceed
>      the maximum object size or cause an unsigned oveflow (wrapping) when
> diff --git a/gcc/calls.h b/gcc/calls.h
> index dfb951ca45b..ab56b48fee4 100644
> --- a/gcc/calls.h
> +++ b/gcc/calls.h
> @@ -134,6 +134,8 @@ extern void maybe_warn_alloc_args_overflow (tree, 
> tree, tree[2], int[2]);
>   extern tree get_attr_nonstring_decl (tree, tree * = NULL);
>   extern bool maybe_warn_nonstring_arg (tree, tree);
>   extern bool get_size_range (tree, tree[2], bool = false);
> +extern bool get_size_range (class range_query *, tree, gimple *,
> +                tree[2], bool = false);
>   extern rtx rtx_for_static_chain (const_tree, bool);
>   extern bool cxx17_empty_base_field_p (const_tree);
> 
> diff --git a/gcc/gimple-ssa-warn-restrict.c 
> b/gcc/gimple-ssa-warn-restrict.c
> index 512fc138528..7961c51c5b0 100644
> --- a/gcc/gimple-ssa-warn-restrict.c
> +++ b/gcc/gimple-ssa-warn-restrict.c
> @@ -25,7 +25,6 @@
>   #include "backend.h"
>   #include "tree.h"
>   #include "gimple.h"
> -#include "domwalk.h"
>   #include "tree-pass.h"
>   #include "builtins.h"
>   #include "ssa.h"
> @@ -41,6 +40,7 @@
>   #include "calls.h"
>   #include "cfgloop.h"
>   #include "intl.h"
> +#include "gimple-range.h"
> 
>   namespace {
> 
> @@ -77,21 +77,10 @@ pass_wrestrict::gate (function *fun ATTRIBUTE_UNUSED)
>     return warn_array_bounds || warn_restrict || warn_stringop_overflow;
>   }
> 
> -/* Class to walk the basic blocks of a function in dominator order.  */
> -class wrestrict_dom_walker : public dom_walker
> -{
> - public:
> -  wrestrict_dom_walker () : dom_walker (CDI_DOMINATORS) {}
> +static void check_call (range_query *, gimple *);
> 
> -  edge before_dom_children (basic_block) FINAL OVERRIDE;
> -  bool handle_gimple_call (gimple_stmt_iterator *);
> -
> - private:
> -  void check_call (gimple *);
> -};
> -
> -edge
> -wrestrict_dom_walker::before_dom_children (basic_block bb)
> +static void
> +wrestrict_walk (range_query *query, basic_block bb)
>   {
>     /* Iterate over statements, looking for function calls.  */
>     for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
> @@ -101,21 +90,17 @@ wrestrict_dom_walker::before_dom_children 
> (basic_block bb)
>         if (!is_gimple_call (stmt))
>       continue;
> 
> -      check_call (stmt);
> +      check_call (query, stmt);
>       }
> -
> -  return NULL;
>   }
> 
> -/* Execute the pass for function FUN, walking in dominator order.  */
> -
>   unsigned
>   pass_wrestrict::execute (function *fun)
>   {
> -  calculate_dominance_info (CDI_DOMINATORS);
> -
> -  wrestrict_dom_walker walker;
> -  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
> +  gimple_ranger ranger;
> +  basic_block bb;
> +  FOR_EACH_BB_FN (bb, fun)
> +    wrestrict_walk (&ranger, bb);
> 
>     return 0;
>   }
> @@ -159,11 +144,14 @@ public:
>        only the destination reference is.  */
>     bool strbounded_p;
> 
> -  builtin_memref (tree, tree);
> +  builtin_memref (range_query *, gimple *, tree, tree);
> 
>     tree offset_out_of_bounds (int, offset_int[3]) const;
> 
>   private:
> +  gimple *stmt;
> +
> +  range_query *query;

Also please add a comment above STMT to make it clear it's the call
statement to the builtin.

For QUERY, I'm not sure adding a member to every class that needs
to compute ranges is the right design.  At the same time, adding
an argument to every function that computes ranges isn't great
either.  It seems like there should be one shared ranger instance
that could be used by all clients/passes as well as untility
functions called from them.  It could be a global object set/pushed
by each pass when it starts and popped when it ends, and managed by
the ranger API.  Say a static member function:

   range_query* range_query::instance ();
   range_query* range_query::push_instance (range_query*);
   range_query* range_query::pop_instance ();

As some background, when I wrote the builtin_access access
I envisioned using it as a general-purpose class in other similar
contexts.  That hasn't quite happened yet but there is a class
kind of like it that might eventually end up taking the place of
builtin_access.  It's access_ref in builtins.h.  And while neither
class crates a lot of instances so far, I'm about to post a patch
that does create one or two instances of access_ref per SSA_NAME
of pointer type.  Having an extra member in each instance just
to gain access to an API would be excessive.

I'm not saying all this as an objection to the change but more
as something to think about going forward.

>     /* Ctor helper to set or extend OFFRANGE based on argument.  */
>     void extend_offset_range (tree);
> @@ -197,7 +185,7 @@ class builtin_access
>           && detect_overlap != &builtin_access::no_overlap);
>     }
> 
> -  builtin_access (gimple *, builtin_memref &, builtin_memref &);
> +  builtin_access (range_query *, gimple *, builtin_memref &, 
> builtin_memref &);
> 
>     /* Entry point to determine overlap.  */
>     bool overlap ();
> @@ -233,9 +221,10 @@ class builtin_access
> 
>   /* Initialize a memory reference representation from a pointer EXPR and
>      a size SIZE in bytes.  If SIZE is NULL_TREE then the size is assumed
> -   to be unknown.  */
> +   to be unknown.  STMT is the statement in which expr appears in.  */
> 
> -builtin_memref::builtin_memref (tree expr, tree size)
> +builtin_memref::builtin_memref (range_query *query, gimple *stmt, tree 
> expr,
> +                tree size)
>   : ptr (expr),
>     ref (),
>     base (),
> @@ -245,7 +234,9 @@ builtin_memref::builtin_memref (tree expr, tree size)
>     offrange (),
>     sizrange (),
>     maxobjsize (tree_to_shwi (max_object_size ())),
> -  strbounded_p ()
> +  strbounded_p (),
> +  stmt (stmt),
> +  query (query)
>   {
>     /* Unfortunately, wide_int default ctor is a no-op so array members
>        of the type must be set individually.  */
> @@ -264,7 +255,7 @@ builtin_memref::builtin_memref (tree expr, tree size)
>         tree range[2];
>         /* Determine the size range, allowing for the result to be [0, 0]
>        for SIZE in the anti-range ~[0, N] where N >= PTRDIFF_MAX.  */
> -      get_size_range (size, range, true);
> +      get_size_range (query, size, stmt, range, true);
>         sizrange[0] = wi::to_offset (range[0]);
>         sizrange[1] = wi::to_offset (range[1]);
>         /* get_size_range returns SIZE_MAX for the maximum size.
> @@ -341,7 +332,25 @@ builtin_memref::extend_offset_range (tree offset)
>         /* A pointer offset is represented as sizetype but treated
>        as signed.  */
>         wide_int min, max;
> -      value_range_kind rng = get_range_info (offset, &min, &max);
> +      value_range_kind rng;
> +      if (query)
> +    {
> +      value_range vr;
> +      gcc_assert (query->range_of_expr (vr, offset, stmt));
> +      rng = vr.kind ();
> +      if (!vr.undefined_p ())
> +        {
> +          min = wi::to_wide (vr.min ());
> +          max = wi::to_wide (vr.max ());
> +        }
> +    }
> +      else
> +    {
> +      /* There is a global version here because
> +         check_bounds_or_overlap may be called from gimple
> +         fold during gimple lowering.  */
> +      rng = get_range_info (offset, &min, &max);
> +    }
>         if (rng == VR_ANTI_RANGE && wi::lts_p (max, min))
>       {
>         /* Convert an anti-range whose upper bound is less than
> @@ -658,7 +667,8 @@ builtin_memref::offset_out_of_bounds (int strict, 
> offset_int ooboff[3]) const
>   /* Create an association between the memory references DST and SRC
>      for access by a call EXPR to a memory or string built-in funtion.  */
> 
> -builtin_access::builtin_access (gimple *call, builtin_memref &dst,
> +builtin_access::builtin_access (range_query *query, gimple *call,
> +                builtin_memref &dst,
>                   builtin_memref &src)
>   : dstref (&dst), srcref (&src), sizrange (), ovloff (), ovlsiz (),
>     dstoff (), srcoff (), dstsiz (), srcsiz ()
> @@ -797,7 +807,7 @@ builtin_access::builtin_access (gimple *call, 
> builtin_memref &dst,
> 
>         tree size = gimple_call_arg (call, sizeargno);
>         tree range[2];
> -      if (get_size_range (size, range, true))
> +      if (get_size_range (query, size, call, range, true))
>       {
>         bounds[0] = wi::to_offset (range[0]);
>         bounds[1] = wi::to_offset (range[1]);
> @@ -1873,8 +1883,8 @@ maybe_diag_access_bounds (gimple *call, tree func, 
> int strict,
>   /* Check a CALL statement for restrict-violations and issue warnings
>      if/when appropriate.  */
> 
> -void
> -wrestrict_dom_walker::check_call (gimple *call)
> +static void
> +check_call (range_query *query, gimple *call)
>   {
>     /* Avoid checking the call if it has already been diagnosed for
>        some reason.  */
> @@ -1964,7 +1974,7 @@ wrestrict_dom_walker::check_call (gimple *call)
>         || (dstwr && !INTEGRAL_TYPE_P (TREE_TYPE (dstwr))))
>       return;
> 
> -  if (!check_bounds_or_overlap (call, dst, src, dstwr, NULL_TREE))
> +  if (!check_bounds_or_overlap (query, call, dst, src, dstwr, NULL_TREE))
>       return;
> 
>     /* Avoid diagnosing the call again.  */
> @@ -1984,15 +1994,26 @@ int
>   check_bounds_or_overlap (gimple *call, tree dst, tree src, tree dstsize,
>                tree srcsize, bool bounds_only /* = false */,
>                bool do_warn /* = true */)
> +{
> +  return check_bounds_or_overlap (/*range_query=*/NULL,
> +                  call, dst, src, dstsize, srcsize,
> +                  bounds_only, do_warn);
> +}
> +
> +int
> +check_bounds_or_overlap (range_query *query,
> +             gimple *call, tree dst, tree src, tree dstsize,
> +             tree srcsize, bool bounds_only /* = false */,
> +             bool do_warn /* = true */)

Similarly here, a comment please.

>   {
>     tree func = gimple_call_fndecl (call);
> 
> -  builtin_memref dstref (dst, dstsize);
> -  builtin_memref srcref (src, srcsize);
> +  builtin_memref dstref (query, call, dst, dstsize);
> +  builtin_memref srcref (query, call, src, srcsize);
> 
>     /* Create a descriptor of the access.  This may adjust both DSTREF
>        and SRCREF based on one another and the kind of the access.  */
> -  builtin_access acs (call, dstref, srcref);
> +  builtin_access acs (query, call, dstref, srcref);

Since/if the query pointer is a member of builtin_memref which is
passed to the builtin_access ctor there should be no need to pass
a second (and third) copy to it as well.

> 
>     /* Set STRICT to the value of the -Warray-bounds=N argument for
>        string functions or when N > 1.  */
> diff --git a/gcc/gimple-ssa-warn-restrict.h 
> b/gcc/gimple-ssa-warn-restrict.h
> index 7bae95a9ad1..3dba9c0fe58 100644
> --- a/gcc/gimple-ssa-warn-restrict.h
> +++ b/gcc/gimple-ssa-warn-restrict.h
> @@ -22,5 +22,8 @@
> 
>   extern int check_bounds_or_overlap (gimple *, tree, tree, tree, tree,
>                       bool = false, bool = true);
> +extern int check_bounds_or_overlap (class range_query *, gimple *,
> +                    tree, tree, tree, tree,
> +                    bool = false, bool = true);
> 
>   #endif /* GIMPLE_SSA_WARN_RESTRICT_H */
> diff --git a/gcc/testsuite/gcc.dg/Wrestrict-22.c 
> b/gcc/testsuite/gcc.dg/Wrestrict-22.c
> new file mode 100644
> index 00000000000..798d399db3c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/Wrestrict-22.c
> @@ -0,0 +1,9 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -Wrestrict" } */
> +
> +void test_memcpy_warn (char *d, unsigned n)
> +{
> +  for (unsigned i = n; i < 30; ++i)
> +    if (i > 10)
> +      __builtin_memcpy (d, d + 2, i); /* { dg-warning "overlaps 
> between" } */

Nice!  Do you happen to have an outline of the major improvements
like this one that the range brings over EVRP?   (We should add
tests for these new capabilities to other warnings as well.)

FWIW, it should be possible to warn even here (even with the current
ranges):

   void test_memcpy_warn (char *d, unsigned n)
   {
     for (unsigned i = n; i < 30; ++i)
       __builtin_memcpy (d, d + 2, i);
   }

and for the overflow here:

   char a[30];

   void f (void)
   {
     for (unsigned i = 1; i < 30; ++i)
       __builtin_memmove (a + i, a, i);
   }

Martin

On 10/5/20 4:16 PM, Martin Sebor wrote:
> On 10/5/20 8:50 AM, Aldy Hernandez via Gcc-patches wrote:
>> [Martin, as the original author of this pass, do you have any concerns?]
>>
>
>> @@ -1270,7 +1271,21 @@ get_size_range (tree exp, tree range[2], bool 
>> allow_zero /* = false */)
>>     enum value_range_kind range_type;
>>
>>     if (integral)
>> -    range_type = determine_value_range (exp, &min, &max);
>> +    {
>> +      if (query)
>> +    {
>> +      value_range vr;
>> +      gcc_assert (TREE_CODE (exp) == SSA_NAME
>> +              || TREE_CODE (exp) == INTEGER_CST);
>> +      gcc_assert (query->range_of_expr (vr, exp, stmt));
>
> Will the call to the function in the assert above not be eliminated
> if the assert is turned into a no-op?  If it can't happen (it looks
> like it shouldn't anymore), it would still be nice to break it out
> of the macro.  Those of us used to the semantics of the C standard
> assert macro might wonder.
>
gcc_assert contents will not be eliminated in a release compiler, only 
the actual check of the return value.    The body of the assert will 
continue to be executed.

This exists because if we were to try to check the return value, we'd 
have to do something like
   bool ret = range_of_expr (...)
   gcc_checking_assert (ret);

and when the checking assert goes away, we're left with an unused 
variable 'ret' warning.   the gcc_assert ()  resolves that issue.

I'm not a huge fan of them, but they do serve a purpose and seem better 
than the alternatives :-P

The first assert should however be a gcc_checking_assert since its just 
a check.. and then that will go away in a release compiler.

>> -/* Execute the pass for function FUN, walking in dominator order.  */
>> -
>>   unsigned
>>   pass_wrestrict::execute (function *fun)
>>   {
>> -  calculate_dominance_info (CDI_DOMINATORS);
>> -
>> -  wrestrict_dom_walker walker;
>> -  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
>> +  gimple_ranger ranger;
>> +  basic_block bb;
>> +  FOR_EACH_BB_FN (bb, fun)
>> +    wrestrict_walk (&ranger, bb);
>>
>>     return 0;
>>   }
>> @@ -159,11 +144,14 @@ public:
>>        only the destination reference is.  */
>>     bool strbounded_p;
>>
>> -  builtin_memref (tree, tree);
>> +  builtin_memref (range_query *, gimple *, tree, tree);
>>
>>     tree offset_out_of_bounds (int, offset_int[3]) const;
>>
>>   private:
>> +  gimple *stmt;
>> +
>> +  range_query *query;
>
> Also please add a comment above STMT to make it clear it's the call
> statement to the builtin.
>
> For QUERY, I'm not sure adding a member to every class that needs
> to compute ranges is the right design.  At the same time, adding
> an argument to every function that computes ranges isn't great
> either.  It seems like there should be one shared ranger instance
> that could be used by all clients/passes as well as untility
> functions called from them.  It could be a global object set/pushed
> by each pass when it starts and popped when it ends, and managed by
> the ranger API.  Say a static member function:
>
>   range_query* range_query::instance ();
>   range_query* range_query::push_instance (range_query*);
>   range_query* range_query::pop_instance ();
>
> As some background, when I wrote the builtin_access access
> I envisioned using it as a general-purpose class in other similar
> contexts.  That hasn't quite happened yet but there is a class
> kind of like it that might eventually end up taking the place of
> builtin_access.  It's access_ref in builtins.h.  And while neither
> class crates a lot of instances so far, I'm about to post a patch
> that does create one or two instances of access_ref per SSA_NAME
> of pointer type.  Having an extra member in each instance just
> to gain access to an API would be excessive.
>
> I'm not saying all this as an objection to the change but more
> as something to think about going forward.

Long term, I would expect we might have some sort of general access... 
probably thru cfun.     so any pass/routines would just ask for
     RANGE_INFO (cfun)->range_of_expr()
The default would be a general value_range implementation which probably 
implements something like determine_value_range_1 ().. and if a pass 
wants to use a ranger, then it could register a ranger, and when its 
done delete it.  and it would just work for everyone everywhere.

but we're not there yet, and we havent worked out the details :-) for 
the moment, passes need to figure out themselves how to access the 
ranger they create if they want one.   They had to manage a 
range_analyzer before if the used anything other than global ranges, so 
that is nothing new.

>> -  builtin_memref dstref (dst, dstsize);
>> -  builtin_memref srcref (src, srcsize);
>> +  builtin_memref dstref (query, call, dst, dstsize);
>> +  builtin_memref srcref (query, call, src, srcsize);
>>
>>     /* Create a descriptor of the access.  This may adjust both DSTREF
>>        and SRCREF based on one another and the kind of the access.  */
>> -  builtin_access acs (call, dstref, srcref);
>> +  builtin_access acs (query, call, dstref, srcref);
> 
> Since/if the query pointer is a member of builtin_memref which is
> passed to the builtin_access ctor there should be no need to pass
> a second (and third) copy to it as well.

builtin_memref seems like an independent object altogether, and the 
query is a private member of said object.  Are you proposing making it 
public, or making builtin_access a friend of builtin_memref (eeech)?

Aldy

On 10/6/20 3:45 AM, Aldy Hernandez wrote:
>>> -  builtin_memref dstref (dst, dstsize);
>>> -  builtin_memref srcref (src, srcsize);
>>> +  builtin_memref dstref (query, call, dst, dstsize);
>>> +  builtin_memref srcref (query, call, src, srcsize);
>>>
>>>     /* Create a descriptor of the access.  This may adjust both DSTREF
>>>        and SRCREF based on one another and the kind of the access.  */
>>> -  builtin_access acs (call, dstref, srcref);
>>> +  builtin_access acs (query, call, dstref, srcref);
>>
>> Since/if the query pointer is a member of builtin_memref which is
>> passed to the builtin_access ctor there should be no need to pass
>> a second (and third) copy to it as well.
> 
> builtin_memref seems like an independent object altogether, and the 
> query is a private member of said object.  Are you proposing making it 
> public, or making builtin_access a friend of builtin_memref (eeech)?

Either one of those seems preferable to the duplication for the time
being, until there's an API to access the global ranger instance.

A better alternative, in view of your expectation of exposing
the instance via (cfun)->range_of_expr(), is to add some static
namespace scope function to access the range instance.  That
should make adopting the envisioned solution minimally disruptive.

Martin

On 10/6/20 10:30 AM, Martin Sebor wrote:
> On 10/6/20 3:45 AM, Aldy Hernandez wrote:
>>>> -  builtin_memref dstref (dst, dstsize);
>>>> -  builtin_memref srcref (src, srcsize);
>>>> +  builtin_memref dstref (query, call, dst, dstsize);
>>>> +  builtin_memref srcref (query, call, src, srcsize);
>>>>
>>>>     /* Create a descriptor of the access.  This may adjust both DSTREF
>>>>        and SRCREF based on one another and the kind of the access.  */
>>>> -  builtin_access acs (call, dstref, srcref);
>>>> +  builtin_access acs (query, call, dstref, srcref);
>>>
>>> Since/if the query pointer is a member of builtin_memref which is
>>> passed to the builtin_access ctor there should be no need to pass
>>> a second (and third) copy to it as well.
>>
>> builtin_memref seems like an independent object altogether, and the 
>> query is a private member of said object.  Are you proposing making 
>> it public, or making builtin_access a friend of builtin_memref (eeech)?
>
> Either one of those seems preferable to the duplication for the time
> being, until there's an API to access the global ranger instance.
>
> A better alternative, in view of your expectation of exposing
> the instance via (cfun)->range_of_expr(), is to add some static
> namespace scope function to access the range instance.  That
> should make adopting the envisioned solution minimally disruptive.
>
The point was we don't have a fully envisioned solution yet... that is  
just one possibility and may never come to pass.   Each pass should do 
"the right thing" for themselves for now.

On 10/6/20 8:42 AM, Andrew MacLeod wrote:
> On 10/6/20 10:30 AM, Martin Sebor wrote:
>> On 10/6/20 3:45 AM, Aldy Hernandez wrote:
>>>>> -  builtin_memref dstref (dst, dstsize);
>>>>> -  builtin_memref srcref (src, srcsize);
>>>>> +  builtin_memref dstref (query, call, dst, dstsize);
>>>>> +  builtin_memref srcref (query, call, src, srcsize);
>>>>>
>>>>>     /* Create a descriptor of the access.  This may adjust both DSTREF
>>>>>        and SRCREF based on one another and the kind of the access.  */
>>>>> -  builtin_access acs (call, dstref, srcref);
>>>>> +  builtin_access acs (query, call, dstref, srcref);
>>>>
>>>> Since/if the query pointer is a member of builtin_memref which is
>>>> passed to the builtin_access ctor there should be no need to pass
>>>> a second (and third) copy to it as well.
>>>
>>> builtin_memref seems like an independent object altogether, and the 
>>> query is a private member of said object.  Are you proposing making 
>>> it public, or making builtin_access a friend of builtin_memref (eeech)?
>>
>> Either one of those seems preferable to the duplication for the time
>> being, until there's an API to access the global ranger instance.
>>
>> A better alternative, in view of your expectation of exposing
>> the instance via (cfun)->range_of_expr(), is to add some static
>> namespace scope function to access the range instance.  That
>> should make adopting the envisioned solution minimally disruptive.
>>
> The point was we don't have a fully envisioned solution yet... that is 
> just one possibility and may never come to pass.   Each pass should do 
> "the right thing" for themselves for now.

Yes, I got that.  Which is why I suggest to add a namespace scope
function to the restrict pass that can then be easily replaced with
whatever solution we ultimately end up with.

What's certain (in my mind anyway) is that storing a pointer to some
global (or per-pass) range instance as a member in each class that
needs to access it is not the solution we want long term.

Martin

On 10/6/20 4:51 PM, Martin Sebor wrote:
> On 10/6/20 8:42 AM, Andrew MacLeod wrote:
>> On 10/6/20 10:30 AM, Martin Sebor wrote:
>>> On 10/6/20 3:45 AM, Aldy Hernandez wrote:
>>>>>> -  builtin_memref dstref (dst, dstsize);
>>>>>> -  builtin_memref srcref (src, srcsize);
>>>>>> +  builtin_memref dstref (query, call, dst, dstsize);
>>>>>> +  builtin_memref srcref (query, call, src, srcsize);
>>>>>>
>>>>>>     /* Create a descriptor of the access.  This may adjust both 
>>>>>> DSTREF
>>>>>>        and SRCREF based on one another and the kind of the 
>>>>>> access.  */
>>>>>> -  builtin_access acs (call, dstref, srcref);
>>>>>> +  builtin_access acs (query, call, dstref, srcref);
>>>>>
>>>>> Since/if the query pointer is a member of builtin_memref which is
>>>>> passed to the builtin_access ctor there should be no need to pass
>>>>> a second (and third) copy to it as well.
>>>>
>>>> builtin_memref seems like an independent object altogether, and the 
>>>> query is a private member of said object.  Are you proposing making 
>>>> it public, or making builtin_access a friend of builtin_memref (eeech)?
>>>
>>> Either one of those seems preferable to the duplication for the time
>>> being, until there's an API to access the global ranger instance.
>>>
>>> A better alternative, in view of your expectation of exposing
>>> the instance via (cfun)->range_of_expr(), is to add some static
>>> namespace scope function to access the range instance.  That
>>> should make adopting the envisioned solution minimally disruptive.
>>>
>> The point was we don't have a fully envisioned solution yet... that is 
>> just one possibility and may never come to pass.   Each pass should do 
>> "the right thing" for themselves for now.
> 
> Yes, I got that.  Which is why I suggest to add a namespace scope
> function to the restrict pass that can then be easily replaced with
> whatever solution we ultimately end up with.
> 
> What's certain (in my mind anyway) is that storing a pointer to some
> global (or per-pass) range instance as a member in each class that
> needs to access it is not the solution we want long term.

Tell you what.  I'll make your class public, access it's internal 
members as you describe (ughh), and you can do anything else post-commit.

Aldy

On 10/5/20 8:18 PM, Andrew MacLeod wrote:
> On 10/5/20 4:16 PM, Martin Sebor wrote:
>> On 10/5/20 8:50 AM, Aldy Hernandez via Gcc-patches wrote:
>>> [Martin, as the original author of this pass, do you have any concerns?]
>>>
>>
>>> @@ -1270,7 +1271,21 @@ get_size_range (tree exp, tree range[2], bool 
>>> allow_zero /* = false */)
>>>     enum value_range_kind range_type;
>>>
>>>     if (integral)
>>> -    range_type = determine_value_range (exp, &min, &max);
>>> +    {
>>> +      if (query)
>>> +    {
>>> +      value_range vr;
>>> +      gcc_assert (TREE_CODE (exp) == SSA_NAME
>>> +              || TREE_CODE (exp) == INTEGER_CST);
>>> +      gcc_assert (query->range_of_expr (vr, exp, stmt));
>>
>> Will the call to the function in the assert above not be eliminated
>> if the assert is turned into a no-op?  If it can't happen (it looks
>> like it shouldn't anymore), it would still be nice to break it out
>> of the macro.  Those of us used to the semantics of the C standard
>> assert macro might wonder.
>>
> gcc_assert contents will not be eliminated in a release compiler, only 
> the actual check of the return value.    The body of the assert will 
> continue to be executed.
> 
> This exists because if we were to try to check the return value, we'd 
> have to do something like
>    bool ret = range_of_expr (...)
>    gcc_checking_assert (ret);
> 
> and when the checking assert goes away, we're left with an unused 
> variable 'ret' warning.   the gcc_assert ()  resolves that issue.

Right.  The unused warning for the variable would of course have to
be avoided.  There are several ways of doing that we're all familiar
with.  What I wasn't sure about and had to go out of my way to
convince myself of is that the gcc_assert() argument isn't eliminated
when checking is disabled.  There's still a definition of gcc_assert
in gcc/system.h where it is eliminated, but that definition is never
used).  I think the code should be changed so that others (or me if
I forget) don't wonder the same thing in the future.  Another
possibility is to add a comment reassuring the reader that
the argument is always evaluated.

> 
> I'm not a huge fan of them, but they do serve a purpose and seem better 
> than the alternatives :-P
> 
> The first assert should however be a gcc_checking_assert since its just 
> a check.. and then that will go away in a release compiler.
> 
>>> -/* Execute the pass for function FUN, walking in dominator order.  */
>>> -
>>>   unsigned
>>>   pass_wrestrict::execute (function *fun)
>>>   {
>>> -  calculate_dominance_info (CDI_DOMINATORS);
>>> -
>>> -  wrestrict_dom_walker walker;
>>> -  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
>>> +  gimple_ranger ranger;
>>> +  basic_block bb;
>>> +  FOR_EACH_BB_FN (bb, fun)
>>> +    wrestrict_walk (&ranger, bb);
>>>
>>>     return 0;
>>>   }
>>> @@ -159,11 +144,14 @@ public:
>>>        only the destination reference is.  */
>>>     bool strbounded_p;
>>>
>>> -  builtin_memref (tree, tree);
>>> +  builtin_memref (range_query *, gimple *, tree, tree);
>>>
>>>     tree offset_out_of_bounds (int, offset_int[3]) const;
>>>
>>>   private:
>>> +  gimple *stmt;
>>> +
>>> +  range_query *query;
>>
>> Also please add a comment above STMT to make it clear it's the call
>> statement to the builtin.
>>
>> For QUERY, I'm not sure adding a member to every class that needs
>> to compute ranges is the right design.  At the same time, adding
>> an argument to every function that computes ranges isn't great
>> either.  It seems like there should be one shared ranger instance
>> that could be used by all clients/passes as well as untility
>> functions called from them.  It could be a global object set/pushed
>> by each pass when it starts and popped when it ends, and managed by
>> the ranger API.  Say a static member function:
>>
>>   range_query* range_query::instance ();
>>   range_query* range_query::push_instance (range_query*);
>>   range_query* range_query::pop_instance ();
>>
>> As some background, when I wrote the builtin_access access
>> I envisioned using it as a general-purpose class in other similar
>> contexts.  That hasn't quite happened yet but there is a class
>> kind of like it that might eventually end up taking the place of
>> builtin_access.  It's access_ref in builtins.h.  And while neither
>> class crates a lot of instances so far, I'm about to post a patch
>> that does create one or two instances of access_ref per SSA_NAME
>> of pointer type.  Having an extra member in each instance just
>> to gain access to an API would be excessive.
>>
>> I'm not saying all this as an objection to the change but more
>> as something to think about going forward.
> 
> Long term, I would expect we might have some sort of general access... 
> probably thru cfun.     so any pass/routines would just ask for
>      RANGE_INFO (cfun)->range_of_expr()
> The default would be a general value_range implementation which probably 
> implements something like determine_value_range_1 ().. and if a pass 
> wants to use a ranger, then it could register a ranger, and when its 
> done delete it.  and it would just work for everyone everywhere.

That would work too.

As a side note, I don't yet fully understand when it might be useful
to have different range_query instances.  We talked about value_query
and range_query but those are provided because some passes work with
just values and others with just ranges.  When might one want to have
an instance of some other type altogether and tie it to a function?

> 
> but we're not there yet, and we havent worked out the details :-) for 
> the moment, passes need to figure out themselves how to access the 
> ranger they create if they want one.   They had to manage a 
> range_analyzer before if the used anything other than global ranges, so 
> that is nothing new.

For EVRP, yes.  For everything else there's the global get_range_info.
It got ugly when a utility function like get_size_range was changed
to work with both.  I made that change and didn't like it then.  I'm
trying to brainstorm ways to avoid spreading that wart too much
further.


Martin

On 10/6/20 3:27 PM, Martin Sebor wrote:
> On 10/5/20 8:18 PM, Andrew MacLeod wrote:
>> On 10/5/20 4:16 PM, Martin Sebor wrote:
>> Long term, I would expect we might have some sort of general 
>> access... probably thru cfun.     so any pass/routines would just ask 
>> for
>>      RANGE_INFO (cfun)->range_of_expr()
>> The default would be a general value_range implementation which 
>> probably implements something like determine_value_range_1 ().. and 
>> if a pass wants to use a ranger, then it could register a ranger, and 
>> when its done delete it.  and it would just work for everyone 
>> everywhere.
>
> That would work too.
>
> As a side note, I don't yet fully understand when it might be useful
> to have different range_query instances.  We talked about value_query
> and range_query but those are provided because some passes work with
> just values and others with just ranges.  When might one want to have
> an instance of some other type altogether and tie it to a function?
>

I don't know what you are asking. An instance of some other type 
altogether?

we have 2 instances of range_query already.     m_range_analyzer and 
ranger.
we have multiple instances of value_query as well, in that they are used 
by CCP and the other converted passes and they provide their own version 
of value_of_expr to get what they want.
the hybrid ranger utilizes 2 concurrent instances of different 
range_query's to function right now, and uses the combined results.

GCC currently has no concept of a "global" range analyzer.  Its all been 
pass specific with EVRP and VRP being the 2 engines, and they both set 
some minimal global ranges that can be picked up elsewhere.   EVRP was 
enhanced to allow other passes to hook into it via a DOM walk (Like DOM 
and threading), but it was still pass specific information.  We've added 
Ranger with the longer term goal to replace both of the other engines.

The other passes have all been converted to this model fairly painlessly 
as most passes have some sort of local pass information awareness, so 
creating and accessing a range query engine wasnt a big deal.

I dont know if or when we will "promote" a ranger to a global access 
thing.. there hasn't been a need, but if there is more and more good 
reason, then its something we will certainly look at.  Maintaining 
global ranges across passes is not something that is easy to do, and not 
something we are likely to, so we'll need to respawn a new ranger for 
any pass that needs it anyway.  So having a pass spawn its own doesnt 
seem like a big stretch for now.


>>
>> but we're not there yet, and we havent worked out the details :-) for 
>> the moment, passes need to figure out themselves how to access the 
>> ranger they create if they want one.   They had to manage a 
>> range_analyzer before if they used anything other than global ranges, 
>> so that is nothing new.
>
> For EVRP, yes.  For everything else there's the global get_range_info.
> It got ugly when a utility function like get_size_range was changed
> to work with both.  I made that change and didn't like it then. I'm
> trying to brainstorm ways to avoid spreading that wart too much
> further.
>
>

Its not just evrp, and I assure you, thats not the ugliest thing in GCC :-).

we cant do everything up front, or it would be another 2 years before 
things happen.  until then, we work around things and fix them up when 
we can get to them.

Seems to me that either get_size_range takes a range_query object to get 
a range, or there are 2 versions.., or  it is in the wrong place now 
because its a global function trying to access contextual information, 
and becomes part of a class which has/is/uses a range_query object.   
Looking at it, it doesnt seem to be anything more than range_of_expr, 
plus some odd ANTI_RANGE stuff which can be completely avoided with a 
ranger and multirange support.

in fact, I think
   if (range_of_expr (r, exp, stmt)

pretty much does it?   handles all the integral values, constants. 
symbolic lookups  and returns FALSE if it isnt integral. You wont see an 
anti range if you use int_range<2> or higher, but you might see multiple 
ranges if it was an anti range before.. although you may only care about 
the lower_bound()  and upper_bound()... I dont know.

Of course you still need to access a ranger to make that call :-)

rangers are pretty lightweight for occasional queries... maybe the place 
to start is simply spawning a new one for each request and see where 
that gets you.  In fact, I think  thats what Aldy use to do in 
determine_value_range on the branch :-P     I think the bottom line is 
if a pass is going to move from purely global information to something 
that is contextual, it has new constraints it didnt have before and may 
need some additional reshuffling to look pretty.


Andrew