On Wed, Feb 12, 2025 at 01:42:12PM -0700, Jeff Law wrote:
> > I'm fine if your patch is for GCC 15 limited to the easy cases with all 3
> > types compatible (that is the common case). Still, I think it would be nice
> > not to restrict to TYPE_UNSIGNED, just say check either that for a >= b or
> > a > b
> > b is not negative (using vr1min).
> >
> > And let's file a PR for GCC 16 to do it properly.
> The pause button was to give me time to get coffee in and brain turned on to
> walk through the cases.
>
> Note there's code later in that function which actually does computations
> based on known ranges to try and prove/disprove overflow state. There may
> be cases there we can improve range based analysis as well and there may be
> cases where the combination of range information and relationships couple be
> helpful. Those all felt out of scope to me in terms of addressing the
> regression. Happy to open a distinct issue on possibilities there.
>
> The regression can be resolved entirely by looking at the relationship
> between and the types of the inputs. Hence it's a distinct block of code in
> that routine and avoids most of the complexity in that routine.
Ok.
> I agree that the most common cases should be all the arguments the same
> type. I was working under the assumption that the args would be compatible
> types already, forgetting that IFNs are different in that regard than other
> gimple ops. I wouldn't want to go any further than all three operands the
> same with the easy to reason about relation checks.
>
>
> For gcc-16 I think we can extend that block fairly easily to handle certain
> mismatched size cases and we look to see if there's cases where the
> combination of a relationship between the arguments and some range
> information would allow us to capture further cases.
For the GCC 16 version, I think best would be (given Andrew's mail that
the relations aren't likely very useful for incompatible types) to
relation_kind rel = VREL_VARYING;
if (code == MINUS_EXPR
&& types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1))
{
rel = query->relation().query (s, op0, op1);
/* The result of the infinite precision subtraction of
the same values will be always 0. That will fit into any result
type. */
if (rel == VREL_EQ)
return true;
}
then do the current
int_range_max vr0, vr1;
if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
vr0.set_varying (TREE_TYPE (op0));
if (!query->range_of_expr (vr1, op1, s) || vr1.undefined_p ())
vr1.set_varying (TREE_TYPE (op1));
tree vr0min = wide_int_to_tree (TREE_TYPE (op0), vr0.lower_bound ());
tree vr0max = wide_int_to_tree (TREE_TYPE (op0), vr0.upper_bound ());
tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());
and then we can e.g. special case > and >=:
/* If op1 is not negative, op0 - op1 for op0 >= op1 will be always
in [0, op0] and so if vr0max - vr1min fits into type, there won't
be any overflow. */
if ((rel == VREL_GT || rel == VREL_GE)
&& tree_int_cst_sgn (vr1min) >= 0
&& !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
return true;
Would need to think about if anything could be simplified for
VREL_G{T,E} if tree_int_cst_sgn (vr1min) < 0.
As for VREL_LT, one would need to think it through as well for both
tree_int_cst_sgn (vr1min) >= 0 and tree_int_cst_sgn (vr1min) < 0.
For the former, the infinite precision of subtraction is known given
the relation to be < 0. Now obviously if TYPE_UNSIGNED (type) that
would imply always overflow. But for !TYPE_UNSIGNED (type) that isn't
necessarily the case and the question is if the relation helps with the
reasoning. Generally the code otherwise tries to check 2 boundaries
(for MULT_EXPR 4 but we don't care about that), if they both don't overflow,
it is ok, if only one overflows, we don't know, if both boundaries don't
overflow, we need to look further and check some corner cases in between.
Or just go with that even for GCC 15 (completely untested and dunno if
something needs to be done about s = NULL passed to query or not) for
now, with the advantage that it can do something even for the cases where
type is not compatible with types of arguments, and perhaps add additional
cases later?
--- gcc/vr-values.cc.jj 2025-01-13 09:12:09.461954569 +0100
+++ gcc/vr-values.cc 2025-02-12 22:18:51.696314406 +0100
@@ -85,6 +85,19 @@ check_for_binary_op_overflow (range_quer
enum tree_code subcode, tree type,
tree op0, tree op1, bool *ovf, gimple *s = NULL)
{
+ relation_kind rel = VREL_VARYING;
+ /* For subtraction see if relations could simplify it. */
+ if (code == MINUS_EXPR
+ && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1))
+ {
+ rel = query->relation().query (s, op0, op1);
+ /* The result of the infinite precision subtraction of
+ the same values will be always 0. That will fit into any result
+ type. */
+ if (rel == VREL_EQ)
+ return true;
+ }
+
int_range_max vr0, vr1;
if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
vr0.set_varying (TREE_TYPE (op0));
@@ -96,6 +109,25 @@ check_for_binary_op_overflow (range_quer
tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());
+ /* If op1 is not negative, op0 - op1 in infinite precision for op0 >= op1
+ will be always in [0, op0] and so if vr0max - vr1min fits into type,
+ there won't be any overflow. */
+ if ((rel == VREL_GT || rel == VREL_GE)
+ && tree_int_cst_sgn (vr1min) >= 0
+ && !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
+ return true;
+
+ /* If op1 is not negative, op0 - op1 in infinite precision for op0 < op1
+ will be always in [-inf, -1] and so will always overflow if type is
+ unsigned. */
+ if (rel == VREL_LT
+ && tree_int_cst_sgn (vr1min) >= 0
+ && TYPE_UNSIGNED (type))
+ {
+ *ovf = true;
+ return true;
+ }
+
*ovf = arith_overflowed_p (subcode, type, vr0min,
subcode == MINUS_EXPR ? vr1max : vr1min);
if (arith_overflowed_p (subcode, type, vr0max,
Jakub
