[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

Richard Biener  changed:

   What|Removed |Added

 Status|UNCONFIRMED |RESOLVED
 Resolution|--- |INVALID

--- Comment #10 from Richard Biener  ---
.

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #9 from Marc Glisse  ---
(In reply to Martin Sebor from comment #8)
> I agree that in many cases there isn't enough information to tell that a
> range is final and can't be further improved.  But there certainly are such
> cases (the test case in comment #0 is an example of one)

The function could get inlined and i become constant...

> I think it should be possible to call set_range_info() on the result of the
> __builtin_object_size, and perhaps even on the offset variable in (p += i)
> since its value is constrained not only by the range of its type (before
> VRP1) and by statements like the 'if (i < 0 || 1 < i) i = 0;' (after VRP1)
> but also by the increment '(p += i)' which is only defined for i in [0, 3]
> as determined by the tree-object-size pass before VRP1.  Let me give that a
> try.

Careful with that last point. When we compute i+10 (in type int), we do not
restrict the range of i to [INT_MIN, INT_MAX-10]. The reason is that this
restriction is only valid starting from this statement, not from the definition
of i.

> It seems to me that there should many other opportunities to call
> set_range_info() in GCC that could help improve the generated code (and the
> ability to find bugs via warnings).  I count just 9 calls to the function in
> the whole code base.

It makes sense that most range computation happens in VRP (which has a single
set_range_info in a loop at the end). This pass duplicates variables to get
some sort of "local" range, which allows for tighter estimates. If you replace
'i = 0' with 'return' in your first example, then i may generally be any int,
but in the branch that contains __bos, it can only be in the range [0, 1],
which is something you are only aware of during the VRP pass.

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #8 from Martin Sebor  ---
No, I get the range for _2 with a "def_stmt _2 = (sizetype) i_4;"

i.0_1: [0, +INF]
_2: ~[2147483648, 18446744071562067967]
_3: [0, +INF]
i_4: VARYING
i_6(D): VARYING

...
  # i_4 = PHI 
  _2 = (sizetype) i_4;
  p_8 = "ab" + _2;

I don't think this is a bug (anymore).  I understand that it's 1) a limitation
of the EVRP pass as you explained (thank you), combined with 2) the sensible
get_range_info() property that it can return an increasingly refined range each
time it's called, combined with 3) the (possibly deliberate) limitation of the
tree-object-size pass that wasn't written to make use of VRP, and combined with
4) the quirk of POINTER_PLUS_EXPR taking an unsigned operand even for signed
arguments.  (Though the last one does feel like a design defect.)

I agree that in many cases there isn't enough information to tell that a range
is final and can't be further improved.  But there certainly are such cases
(the test case in comment #0 is an example of one) and it seems to me that
distinguishing the two sets from one another would be useful in order to avoid
recomputing the same result over and over.

I think it should be possible to call set_range_info() on the result of the
__builtin_object_size, and perhaps even on the offset variable in (p += i)
since its value is constrained not only by the range of its type (before VRP1)
and by statements like the 'if (i < 0 || 1 < i) i = 0;' (after VRP1) but also
by the increment '(p += i)' which is only defined for i in [0, 3] as determined
by the tree-object-size pass before VRP1.  Let me give that a try.

It seems to me that there should many other opportunities to call
set_range_info() in GCC that could help improve the generated code (and the
ability to find bugs via warnings).  I count just 9 calls to the function in
the whole code base.

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #7 from Marc Glisse  ---
(In reply to Martin Sebor from comment #6)
> I meant a subrange of the i variable (i.e., a subrange of int).  The range
> of every variable is necessarily bounded by its type so returning a range of
> [INT_MIN, INT_MAX] for an int isn't terribly helpful.

Do you actually get that range when calling get_range_info on the int i_6 (as
opposed to _2 or i.0_1, which are different variables of different types)? If
so, it looks like a bug.

> I understand that the range is the most accurate it can be at this stage
> (after EVRP and before VRP1) and the get_range_info() function doesn't have
> enough smarts to indicate whether there's a chance the range might improve
> (e.g., after inlining or even with LTO).

I can't think of many cases where you know there is no chance of improving the
range, but the result is not constant.

> I suspect your suggestion is what I'm going to have to go with.  What
> bothers me about it is that it means embedding assumptions into the
> tree-object-size pass about the number of times it runs, and throwing away
> possibly optimal results computed in the initial runs of the pass and only
> using the last one, even if the last one is no better than the first.
> 
> In general this approach also denies downstream clients of a pass the
> benefit of gradually refining their results based on gradual refinements of
> the results provided by it.  In this case, it means preventing the
> tree-object-size pass from returning a potentially useful if not optimal
> size of an object based on the type (but not the value) of the offset. 
> Instead, the tree-object-size pass must return a "don't know" value even
> though it "knows" that the value is in some range.

Hmm, now it sounds like you want to set a value range on the lhs of the __bos
call. Is there some reason not to do that?

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #6 from Martin Sebor  ---
I meant a subrange of the i variable (i.e., a subrange of int).  The range of
every variable is necessarily bounded by its type so returning a range of
[INT_MIN, INT_MAX] for an int isn't terribly helpful.  It's no different than
the range returned for i without the if statement:

void f (int i)
{
  const char *p = "ab";

  p += i;

  unsigned long n = __builtin_object_size (p, 2);

  if (n < 2 || 3 < n)
__builtin_abort ();
}

I understand that the range is the most accurate it can be at this stage (after
EVRP and before VRP1) and the get_range_info() function doesn't have enough
smarts to indicate whether there's a chance the range might improve (e.g.,
after inlining or even with LTO).

I suspect your suggestion is what I'm going to have to go with.  What bothers
me about it is that it means embedding assumptions into the tree-object-size
pass about the number of times it runs, and throwing away possibly optimal
results computed in the initial runs of the pass and only using the last one,
even if the last one is no better than the first.

In general this approach also denies downstream clients of a pass the benefit
of gradually refining their results based on gradual refinements of the results
provided by it.  In this case, it means preventing the tree-object-size pass
from returning a potentially useful if not optimal size of an object based on
the type (but not the value) of the offset.  Instead, the tree-object-size pass
must return a "don't know" value even though it "knows" that the value is in
some range.

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #5 from Marc Glisse  ---
(In reply to Martin Sebor from comment #4)
> I suppose I was expecting that that after EVRP (and before VRP1)
> get_range_info() would either succeed and return a range representing a
> subrange of the the variable's type or fail and return VR_VARYING.

But that's what it did! It succeeded in finding an anti-range that describes a
subrange of the variable's type (sizetype).

> If instead the first one or two times the tree-object-size pass ran
> it could somehow determine that a) the range it got from get_range_info()
> wasn't as good as it could be, and b) that it will run again and will get
> another chance to refine the result, it could avoid using the suboptimal
> results and ultimately return the correct answer.

Looks like you want to enable your new transformation only in the last
object-size pass? Otherwise, there is always a chance the range might shrink
before the next pass (though there might also be a possibility for a wider
range, if we commonize several calls to __bos).

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #4 from Martin Sebor  ---
I suppose I was expecting that that after EVRP (and before VRP1)
get_range_info() would either succeed and return a range representing a
subrange of the the variable's type or fail and return VR_VARYING.

If the range returned by get_range_info() gets refined as other passes provide
more insight into the data flow through the program (which makes perfect sense)
then there ought to be a way for callers to hold off on using the suboptimal
range if another one is coming than might be better.

To translate it to the case I'm dealing with: the tree-object-size pass runs
three times, the first time after EVRP but before VRP1, then again after VRP1,
and finally after VRP2.  If the first time it runs it calls get_range_info() to
compute the result of (p += 1) and gets back [INT_MIN, INT_MAX] then it will
set the minimum size of the object to which p points to 0 resulting in
__builtin_object_size (p, 2) returning a subopptimal value.  If instead the
first one or two times the tree-object-size pass ran it could somehow determine
that a) the range it got from get_range_info() wasn't as good as it could be,
and b) that it will run again and will get another chance to refine the result,
it could avoid using the suboptimal results and ultimately return the correct
answer.

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

--- Comment #3 from Marc Glisse  ---
(In reply to Martin Sebor from comment #2)
> I may also be confused about other things but below is what I see in GDB
> when I call get_range_info() from plus_stmt_object_size() on the offset in
> POINTER_PLUS_EXPR (get_offset_range is a function I've added in my patch for
> bug 77608).  As best I can tell the anti-range doesn't correspond to the
> range of the variable i which is [0, 1].

You seem to be assuming that EVRP is clever enough to find out that the range
of i_4 is [0, 1], as VRP1 does. However, EVRP is a limited version, which
doesn't manage it in this case. All it knows is that _2 is an unsigned long
obtained by casting from some arbitrary int, so its range is the union of [0,
INT_MAX] (if the int is non-negative) and [ULONG_MAX+INT_MIN+1,ULONG_MAX] (if
the int is negative), which is represented as an anti-range. This conservative
(anti-)range is valid, since it contains [0,1].

Now maybe evrp could be enhanced to find a tighter range without making it too
costly, I don't know.

[Bug tree-optimization/77898] incorrect VR_ANTI_RANGE after evrp and before vrp1

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77898

Martin Sebor  changed:

   What|Removed |Added

 Status|RESOLVED|UNCONFIRMED
 Resolution|INVALID |---
Summary|VR_RANGE with inverted  |incorrect VR_ANTI_RANGE
   |bounds after evrp and   |after evrp and before vrp1
   |before vrp1 |

--- Comment #2 from Martin Sebor  ---
I may have made a mistake and miread the VR_ANTI_RANGE as VR_RANGE here.  Sorry
about that.  I've adjusted the Summary.

I may also be confused about other things but below is what I see in GDB when I
call get_range_info() from plus_stmt_object_size() on the offset in
POINTER_PLUS_EXPR (get_offset_range is a function I've added in my patch for
bug 77608).  As best I can tell the anti-range doesn't correspond to the range
of the variable i which is [0, 1].

Breakpoint 1, get_offset_range (op1=0x70daa990, offrange=0x7fffd360)
at /src/gcc/77608/gcc/tree-object-size.c:824
824   bool antirange = false;
(gdb) n
826   if (TREE_CODE (op1) == SSA_NAME)
(gdb) n
829   wide_int min, max;
(gdb) n
830   enum value_range_type range_type = get_range_info (op1, ,
);
(gdb) n
831   if (range_type == VR_RANGE || (antirange = range_type ==
VR_ANTI_RANGE))
(gdb) p debug_tree(op1)
 
unit size 
align 64 symtab 0 alias set -1 canonical type 0x70da41f8 precision
64 min  max >
static visited
def_stmt _2 = (sizetype) i_4;
version 2
ptr-info 0x70ec8f80>
$1 = void
(gdb) p range_type
$2 = VR_ANTI_RANGE
(gdb) p min
$3 = { = {val = {2147483648, 18061790, 140737235423104}, 
len = 1, precision = 64}, static is_sign_extended = }
(gdb) p max
$4 = { = {val = {-2147483649, 18061836, 140737235423104}, 
len = 1, precision = 64}, static is_sign_extended = }
(gdb) p debug_tree(gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op1)))
 
unit size 
align 32 symtab 0 alias set -1 canonical type 0x70da47e0 precision
32 min  max 
pointer_to_this >
visited var 
def_stmt i_4 = PHI 
version 4>