This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Teach VRP about NAME + CST1 vs CST2 comparison
- From: Eric Botcazou <ebotcazou at adacore dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 20 May 2016 11:20:01 +0200
- Subject: [patch] Teach VRP about NAME + CST1 vs CST2 comparison
- Authentication-results: sourceware.org; auth=none
Hi,
this enhances VRP, more precisely compare_values_warnv, so as not to give up
for the NAME + CST1 vs CST2 comparison if type overflow is undefined and the
difference CST2 - CST1 overflows or underflows. This makes it possible to
optimize out a class of overflow checks in Ada, typically:
function F (Val, Max : Integer) return Integer is
begin
if Val >= Max then
return Max;
end if;
return Val + 1; -- overflow check can never fail
end;
The patch also streamlines the handling of symbolic values in the function by
calling get_single_symbol instead of doing the decompostion manually twice.
The Ada part is a tweak to expose more opportunities to VRP by removing casts.
Tested on x86_64-suse-linux, OK for the mainline?
2016-05-20 Eric Botcazou <ebotcazou@adacore.com>
* tree-vrp.c (compare_values_warnv): Simplify handling of symbolic
ranges by calling get_single_symbol and tidy up. Look more closely
into NAME + CST1 vs CST2 comparisons if type overflow is undefined.
ada/
* gcc-interface/decl.c (gnat_to_gnu_entity)<E_Signed_Integer_Subtype>
Make same-sized subtypes of signed base types signed.
* gcc-interface/utils.c (make_type_from_size): Adjust to above
change.
(unchecked_convert): Likewise.
2016-05-20 Eric Botcazou <ebotcazou@adacore.com>
* gnat.dg/opt53.adb: New test.
* gnat.dg/opt54.adb: Likewise.
--
Eric BotcazouIndex: tree-vrp.c
===================================================================
--- tree-vrp.c (revision 236441)
+++ tree-vrp.c (working copy)
@@ -1187,129 +1187,77 @@ compare_values_warnv (tree val1, tree va
val2 = fold_convert (TREE_TYPE (val1), val2);
STRIP_USELESS_TYPE_CONVERSION (val2);
- if ((TREE_CODE (val1) == SSA_NAME
- || (TREE_CODE (val1) == NEGATE_EXPR
- && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME)
- || TREE_CODE (val1) == PLUS_EXPR
- || TREE_CODE (val1) == MINUS_EXPR)
- && (TREE_CODE (val2) == SSA_NAME
- || (TREE_CODE (val2) == NEGATE_EXPR
- && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME)
- || TREE_CODE (val2) == PLUS_EXPR
- || TREE_CODE (val2) == MINUS_EXPR))
+ const bool overflow_undefined
+ = INTEGRAL_TYPE_P (TREE_TYPE (val1))
+ && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1));
+ tree inv1, inv2;
+ bool neg1, neg2;
+ tree sym1 = get_single_symbol (val1, &neg1, &inv1);
+ tree sym2 = get_single_symbol (val2, &neg2, &inv2);
+
+ /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1
+ accordingly. If VAL1 and VAL2 don't use the same name, return -2. */
+ if (sym1 && sym2)
{
- tree n1, c1, n2, c2;
- enum tree_code code1, code2;
-
- /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME',
- return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
- same name, return -2. */
- if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR)
- {
- code1 = SSA_NAME;
- n1 = val1;
- c1 = NULL_TREE;
- }
- else
- {
- code1 = TREE_CODE (val1);
- n1 = TREE_OPERAND (val1, 0);
- c1 = TREE_OPERAND (val1, 1);
- if (tree_int_cst_sgn (c1) == -1)
- {
- if (is_negative_overflow_infinity (c1))
- return -2;
- c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
- if (!c1)
- return -2;
- code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
- }
- }
-
- if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR)
- {
- code2 = SSA_NAME;
- n2 = val2;
- c2 = NULL_TREE;
- }
- else
- {
- code2 = TREE_CODE (val2);
- n2 = TREE_OPERAND (val2, 0);
- c2 = TREE_OPERAND (val2, 1);
- if (tree_int_cst_sgn (c2) == -1)
- {
- if (is_negative_overflow_infinity (c2))
- return -2;
- c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
- if (!c2)
- return -2;
- code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
- }
- }
-
- /* Both values must use the same name. */
- if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR)
- {
- n1 = TREE_OPERAND (n1, 0);
- n2 = TREE_OPERAND (n2, 0);
- }
- if (n1 != n2)
+ /* Both values must use the same name with the same sign. */
+ if (sym1 != sym2 || neg1 != neg2)
return -2;
- if (code1 == SSA_NAME && code2 == SSA_NAME)
- /* NAME == NAME */
+ /* [-]NAME + CST == [-]NAME + CST. */
+ if (inv1 == inv2)
return 0;
/* If overflow is defined we cannot simplify more. */
- if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
+ if (!overflow_undefined)
return -2;
if (strict_overflow_p != NULL
- && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
- && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
+ && (!inv1 || !TREE_NO_WARNING (val1))
+ && (!inv2 || !TREE_NO_WARNING (val2)))
*strict_overflow_p = true;
- if (code1 == SSA_NAME)
- {
- if (code2 == PLUS_EXPR)
- /* NAME < NAME + CST */
- return -1;
- else if (code2 == MINUS_EXPR)
- /* NAME > NAME - CST */
- return 1;
- }
- else if (code1 == PLUS_EXPR)
- {
- if (code2 == SSA_NAME)
- /* NAME + CST > NAME */
- return 1;
- else if (code2 == PLUS_EXPR)
- /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
- return compare_values_warnv (c1, c2, strict_overflow_p);
- else if (code2 == MINUS_EXPR)
- /* NAME + CST1 > NAME - CST2 */
- return 1;
- }
- else if (code1 == MINUS_EXPR)
+ if (!inv1)
+ inv1 = build_int_cst (TREE_TYPE (val1), 0);
+ if (!inv2)
+ inv2 = build_int_cst (TREE_TYPE (val2), 0);
+
+ return compare_values_warnv (inv1, inv2, strict_overflow_p);
+ }
+
+ const bool cst1 = is_gimple_min_invariant (val1);
+ const bool cst2 = is_gimple_min_invariant (val2);
+
+ /* If one is of the form '[-]NAME + CST' and the other is constant, then
+ it might be possible to say something depending on the constants. */
+ if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1))
+ {
+ if (!overflow_undefined)
+ return -2;
+
+ if (strict_overflow_p != NULL
+ && (!sym1 || !TREE_NO_WARNING (val1))
+ && (!sym2 || !TREE_NO_WARNING (val2)))
+ *strict_overflow_p = true;
+
+ const signop sgn = TYPE_SIGN (TREE_TYPE (val1));
+ tree cst = cst1 ? val1 : val2;
+ tree inv = cst1 ? inv2 : inv1;
+
+ /* Compute the difference between the constants. If it overflows or
+ underflows, this means that we can trivially compare the NAME with
+ it and, consequently, the two values with each other. */
+ wide_int diff = wi::sub (cst, inv);
+ if (wi::cmp (0, inv, sgn) != wi::cmp (diff, cst, sgn))
{
- if (code2 == SSA_NAME)
- /* NAME - CST < NAME */
- return -1;
- else if (code2 == PLUS_EXPR)
- /* NAME - CST1 < NAME + CST2 */
- return -1;
- else if (code2 == MINUS_EXPR)
- /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
- C1 and C2 are swapped in the call to compare_values. */
- return compare_values_warnv (c2, c1, strict_overflow_p);
+ const int res = wi::cmp (cst, inv, sgn);
+ return cst1 ? res : -res;
}
- gcc_unreachable ();
+ return -2;
}
- /* We cannot compare non-constants. */
- if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
+ /* We cannot say anything more for non-constants. */
+ if (!cst1 || !cst2)
return -2;
if (!POINTER_TYPE_P (TREE_TYPE (val1)))
Index: ada/gcc-interface/decl.c
===================================================================
--- ada/gcc-interface/decl.c (revision 236441)
+++ ada/gcc-interface/decl.c (working copy)
@@ -1814,7 +1814,12 @@ gnat_to_gnu_entity (Entity_Id gnat_entit
/* First subtypes of Character are treated as Character; otherwise
this should be an unsigned type if the base type is unsigned or
if the lower bound is constant and non-negative or if the type
- is biased. */
+ is biased. However, even if the lower bound is constant and
+ non-negative, we use a signed type for a subtype with the same
+ size as its signed base type, because this eliminates useless
+ conversions to it and gives more leeway to the optimizer; but
+ this means that we will need to explicitly test for this case
+ when we change the representation based on the RM size. */
if (kind == E_Enumeration_Subtype
&& No (First_Literal (Etype (gnat_entity)))
&& Esize (gnat_entity) == RM_Size (gnat_entity)
@@ -1822,7 +1827,8 @@ gnat_to_gnu_entity (Entity_Id gnat_entit
&& flag_signed_char)
gnu_type = make_signed_type (CHAR_TYPE_SIZE);
else if (Is_Unsigned_Type (Etype (gnat_entity))
- || Is_Unsigned_Type (gnat_entity)
+ || (Esize (Etype (gnat_entity)) != Esize (gnat_entity)
+ && Is_Unsigned_Type (gnat_entity))
|| Has_Biased_Representation (gnat_entity))
gnu_type = make_unsigned_type (esize);
else
Index: ada/gcc-interface/utils.c
===================================================================
--- ada/gcc-interface/utils.c (revision 236441)
+++ ada/gcc-interface/utils.c (working copy)
@@ -1116,7 +1116,14 @@ make_type_from_size (tree type, tree siz
break;
biased_p |= for_biased;
- if (TYPE_UNSIGNED (type) || biased_p)
+
+ /* The type should be an unsigned type if the original type is unsigned
+ or if the lower bound is constant and non-negative or if the type is
+ biased, see E_Signed_Integer_Subtype case of gnat_to_gnu_entity. */
+ if (TYPE_UNSIGNED (type)
+ || (TREE_CODE (TYPE_MIN_VALUE (type)) == INTEGER_CST
+ && tree_int_cst_sgn (TYPE_MIN_VALUE (type)) >= 0)
+ || biased_p)
new_type = make_unsigned_type (size);
else
new_type = make_signed_type (size);
@@ -5111,7 +5118,9 @@ unchecked_convert (tree type, tree expr,
/* If the result is an integral type whose precision is not equal to its
size, sign- or zero-extend the result. We need not do this if the input
is an integral type of the same precision and signedness or if the output
- is a biased type or if both the input and output are unsigned. */
+ is a biased type or if both the input and output are unsigned, or if the
+ lower bound is constant and non-negative, see E_Signed_Integer_Subtype
+ case of gnat_to_gnu_entity. */
if (!notrunc_p
&& INTEGRAL_TYPE_P (type)
&& TYPE_RM_SIZE (type)
@@ -5123,7 +5132,10 @@ unchecked_convert (tree type, tree expr,
? TYPE_RM_SIZE (etype)
: TYPE_SIZE (etype)) == 0)
&& !(code == INTEGER_TYPE && TYPE_BIASED_REPRESENTATION_P (type))
- && !(TYPE_UNSIGNED (type) && TYPE_UNSIGNED (etype)))
+ && !((TYPE_UNSIGNED (type)
+ || (TREE_CODE (TYPE_MIN_VALUE (type)) == INTEGER_CST
+ && tree_int_cst_sgn (TYPE_MIN_VALUE (type)) >= 0))
+ && TYPE_UNSIGNED (etype)))
{
tree base_type
= gnat_type_for_size (TREE_INT_CST_LOW (TYPE_SIZE (type)),
-- { dg-do compile }
-- { dg-options "-O2 -fdump-tree-optimized" }
function Opt53 (Val, Max : Positive) return Positive is
begin
if Val >= Max then
return Max;
end if;
return Val + 1;
end;
-- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } }
-- { dg-do compile }
-- { dg-options "-O2 -fdump-tree-optimized" }
function Opt54 (Val, Max : Integer) return Integer is
begin
if Val >= Max then
return Max;
end if;
return Val + 1;
end;
-- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } }