@@ -1138,6 +1138,130 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(minus @0 (minus @0 @1))
@1)
+ /* ((T)(A +- CST)) +- CST -> (T)(A) +- CST) */
+#if GIMPLE
+ (for outer_op (plus minus)
+ (for inner_op (plus minus)
+ (simplify
+ (outer_op (convert (inner_op@3 @0 INTEGER_CST@1)) INTEGER_CST@2)
+ (with
+ {
+ /* If the inner operation is wrapped inside a conversion, we have
+ to check it overflows/underflows and can only then perform the
+ simplification, i.e. add the second constant to the first
+ (wrapped) and convert afterwards. */
+ bool inner_ovf = false;
+
+ bool combine_ovf = true;
+ tree cst = NULL_TREE;
+ bool combine_constants = false;
+ bool types_ok = false;
+
+ tree inner_type = TREE_TYPE (@3);
+ /* Check overflow in wrapped binop? */
+ bool check_inner_ovf = !TYPE_OVERFLOW_UNDEFINED (inner_type);
+ bool check_combine_ovf = !TYPE_OVERFLOW_WRAPS (type);
+
+ signop s1 = TYPE_SIGN (type);
+
+ if (TYPE_PRECISION (type) >= TYPE_PRECISION (inner_type))
+ {
+ types_ok = true;
+
+ /* Check if the inner binop does not overflow i.e. we have VRP
+ information and can prove prove it. */
+ if (check_inner_ovf)
+ {
+ value_range vr = VR_INITIALIZER;
+ if (@0 == NULL_TREE || @1 == NULL_TREE
+ || inner_type == NULL_TREE
+ || TREE_CODE (type) != INTEGER_TYPE)
+ {
+ inner_ovf = true;
+ }
+ else
+ {
+ extract_range_from_binary_expr (&vr, inner_op,
+ inner_type, @0, @1, true, &inner_ovf);
+ }
+ }
+ else
+ inner_ovf = false;
+
+ wide_int w1 = @1;
+ wide_int w2 = @2;
+
+ wide_int combined_cst;
+
+ /* Convert to TYPE keeping possible signedness even when
+ dealing with unsigned types. */
+ wide_int v1;
+ v1 = v1.from (w1, w2.get_precision(), tree_int_cst_sgn (@1) ?
+ SIGNED : UNSIGNED);
+
+ if (inner_op == MINUS_EXPR)
+ w1 = wi::neg (w1);
+
+ if (outer_op == MINUS_EXPR)
+ w2 = wi::neg (w2);
+
+ /* Combine in outer, larger type. */
+ combined_cst = wi::add (v1, w2,
+ TYPE_SIGN (type), &combine_ovf);
+
+ /* The combined constant is ok if its type does not exhibit
+ undefined overflow (caught by !inner_ovf) or there was
+ no overflow when combining. */
+ bool combined_cst_ok = !check_combine_ovf || !combine_ovf;
+ if (!inner_ovf && combined_cst_ok)
+ {
+ /* convert to tree of outer type */
+ cst = wide_int_to_tree (type, combined_cst);
+ combine_constants = true;
+ }
+ }
+ }
+ (if (types_ok && combine_constants && cst)
+ (outer_op (convert { @0; }) { cst; }))
+ ))))
+#endif
+
+ /* ((T)(A)) +- CST -> (T)(A +- CST) */
+#if GIMPLE
+ (for outer_op (plus minus)
+ (simplify
+ (outer_op (convert @0) INTEGER_CST@2)
+ /* Perform binary operation inside the cast if the constant fits
+ and there is no overflow. */
+ (with
+ {
+ bool simplify = false;
+
+ wide_int cst = @2;
+ tree inner_type = TREE_TYPE (@0);
+ tree cst_inner;
+ bool inner_ovf = true;
+ value_range vr = VR_INITIALIZER;
+
+ if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type)
+ || TREE_CODE (inner_type) != INTEGER_TYPE
+ || @0 == NULL_TREE || inner_type == NULL_TREE
+ || TREE_CODE (type) != INTEGER_TYPE)
+ simplify = false;
+ else
+ {
+ cst_inner = wide_int_to_tree (inner_type, cst);
+ extract_range_from_binary_expr (&vr, outer_op, inner_type,
+ @0, cst_inner, true, &inner_ovf);
+ if (!inner_ovf)
+ simplify = true;
+ }
+ }
+ (if (simplify)
+ (convert (outer_op @0 { cst_inner; })))
+ )))
+#endif
+
/* (A +- CST) +- CST -> A + CST */
(for outer_op (plus minus)
(for inner_op (plus minus)
@@ -1151,6 +1275,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (cst && !TREE_OVERFLOW (cst))
(inner_op @0 { cst; } ))))))
+
/* (CST - A) +- CST -> CST - A */
(for outer_op (plus minus)
(simplify
new file mode 100644
@@ -0,0 +1,76 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ccp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 11 "ccp1" } } */
+
+#include <limits.h>
+
+// should simplify, ignore possible signed overflow in (a - 2) and combine
+// constants
+long foo(int a)
+{
+ return (long)(a - 2) + 1;
+}
+
+// should simplify
+long bar(int a)
+{
+ return (long)(a + 3) - 1;
+}
+
+// should simplify with combined constant in outer type
+long baz(int a)
+{
+ return (long)(a - 1) + 2;
+}
+
+// should simplify
+long baf(int a)
+{
+ return (long)(a + 1) - 2;
+}
+
+// should simplify (same as above)
+long bak(int a)
+{
+ return (long)(a + 1) + 3;
+}
+
+// should simplify (same)
+long bal(int a)
+{
+ return (long)(a - 7) - 4;
+}
+
+// should simplify with combined constant in inner type, no overflow in
+// combined constant in inner type (1 - INT_MAX)
+long bam(int a)
+{
+ return (long)(a - 1) - INT_MAX;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long bam2(int a)
+{
+ return (long)(a + 1) + INT_MAX;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long ban(int a)
+{
+ return (long)(a - 1) + INT_MIN;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long ban2(int a)
+{
+ return (long)(a + 1) - INT_MIN;
+}
+
+// should simplify, assumes no inner overflow
+unsigned long baq(int a)
+{
+ return (unsigned long)(a + 1) - 1;
+}
new file mode 100644
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ccp1-details -fdump-tree-vrp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 0 "ccp1" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 0 "vrp1" } } */
+
+#include <limits.h>
+#include <assert.h>
+
+// should not simplify, 2 + LONG_MAX overflows
+long bao(int a)
+{
+ return (long)(a + 2) + LONG_MAX;
+}
+
+// should not simplify
+long bar(int a)
+{
+ return (long)(a - 2) - LONG_MAX;
+}
+
+// should not simplify although at first looks like (long)(a - 1) + 1 on
+// tree level, but a is promoted to long
+long bas(int a)
+{
+ return (long)(a + UINT_MAX) + 1;
+}
new file mode 100644
@@ -0,0 +1,48 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ccp1-details -fdump-tree-vrp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 1 "ccp1" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 5 "vrp1" } } */
+
+#include <limits.h>
+
+// should simplify
+unsigned long oof2(unsigned int a)
+{
+ if (a > 3 && a < INT_MAX - 100)
+ return (unsigned long)(a - 1) + 1;
+}
+
+// same
+unsigned long bap(unsigned int a)
+{
+ if (a > 3 && a < INT_MAX - 100)
+ return (unsigned long)(a + 1) + ULONG_MAX;
+}
+
+// should simplify
+unsigned long bar3(unsigned int a)
+{
+ if (a > 3 && a < INT_MAX - 100)
+ return (unsigned long)(a + 1) - 5;
+}
+
+// should simplify in outer type as we cannot prove non-overflow
+unsigned long bar4(unsigned int a)
+{
+ if (a > 3 && a < INT_MAX - 100)
+ return (unsigned long)(a + 1) - 6;
+}
+
+// should simplify
+unsigned long baq(int a)
+{
+ return (unsigned long)(a - 2) + 1;
+}
+
+// should simplify
+long baq3(unsigned int a)
+{
+ if (a > 3 && a < INT_MAX - 100)
+ return (long)(a - 1) + 1;
+}
+
new file mode 100644
@@ -0,0 +1,29 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+#include <assert.h>
+#include <limits.h>
+
+unsigned int a = 3;
+unsigned int aa = UINT_MAX;
+
+int main()
+{
+ volatile unsigned long b = (unsigned long)(aa + 1) - 1;
+ assert (b == 18446744073709551615ul);
+
+ volatile unsigned long c = (unsigned long)(a - 4) + 1;
+ assert (c == 4294967296);
+
+ volatile unsigned long d = (unsigned long)(a + UINT_MAX - 4) + 2;
+ assert (d == 4294967296);
+
+ volatile unsigned long e = (unsigned long)(a - UINT_MAX) + UINT_MAX;
+ assert (e == 4294967299);
+
+ volatile unsigned long f = (unsigned long)(a + UINT_MAX) - UINT_MAX;
+ assert (f == 18446744069414584323ul);
+
+ volatile long g = (long)(a - 4) + 1;
+ assert (g == 4294967296);
+}
@@ -1105,10 +1105,10 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
/* Replace real uses in the statement. */
did_replace |= replace_uses_in (stmt, get_value_fn);
- /* If we made a replacement, fold the statement. */
- if (did_replace)
+ /* Fold the statement. */
+ if (fold_stmt (&i, follow_single_use_edges))
{
- fold_stmt (&i, follow_single_use_edges);
+ did_replace = true;
stmt = gsi_stmt (i);
}
@@ -61,8 +61,6 @@ along with GCC; see the file COPYING3. If not see
#include "params.h"
#include "alloc-pool.h"
-#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
-
/* Allocation pools for tree-vrp allocations. */
static object_allocator<value_range> vrp_value_range_pool ("Tree VRP value ranges");
static bitmap_obstack vrp_equiv_obstack;
@@ -2154,7 +2152,8 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
static void
extract_range_from_binary_expr_1 (value_range *vr,
enum tree_code code, tree expr_type,
- value_range *vr0_, value_range *vr1_)
+ value_range *vr0_, value_range *vr1_,
+ bool get_ovf, bool *ovf)
{
value_range vr0 = *vr0_, vr1 = *vr1_;
value_range vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
@@ -2213,12 +2212,13 @@ extract_range_from_binary_expr_1 (value_range *vr,
if (vr0.type == VR_ANTI_RANGE
&& ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
{
- extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
+ extract_range_from_binary_expr_1 (vr, code, expr_type,
+ &vrtem0, vr1_, get_ovf, ovf);
if (vrtem1.type != VR_UNDEFINED)
{
value_range vrres = VR_INITIALIZER;
extract_range_from_binary_expr_1 (&vrres, code, expr_type,
- &vrtem1, vr1_);
+ &vrtem1, vr1_, get_ovf, ovf);
vrp_meet (vr, &vrres);
}
return;
@@ -2227,12 +2227,13 @@ extract_range_from_binary_expr_1 (value_range *vr,
if (vr1.type == VR_ANTI_RANGE
&& ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
{
- extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
+ extract_range_from_binary_expr_1 (vr, code, expr_type,
+ vr0_, &vrtem0, get_ovf, ovf);
if (vrtem1.type != VR_UNDEFINED)
{
value_range vrres = VR_INITIALIZER;
extract_range_from_binary_expr_1 (&vrres, code, expr_type,
- vr0_, &vrtem1);
+ vr0_, &vrtem1, get_ovf, ovf);
vrp_meet (vr, &vrres);
}
return;
@@ -2445,6 +2446,11 @@ extract_range_from_binary_expr_1 (value_range *vr,
max_ovf = 1;
}
+ if (get_ovf)
+ {
+ *ovf = wi::gt_p (wmin, wmax, TYPE_SIGN (expr_type));
+ }
+
/* If we have overflow for the constant part and the resulting
range will be symbolic, drop to VR_VARYING. */
if ((min_ovf && sym_min_op0 != sym_min_op1)
@@ -2787,7 +2793,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
saved_flag_wrapv = flag_wrapv;
flag_wrapv = 1;
extract_range_from_binary_expr_1 (vr, MULT_EXPR, expr_type,
- &vr0, &vr1p);
+ &vr0, &vr1p, get_ovf, ovf);
flag_wrapv = saved_flag_wrapv;
return;
}
@@ -3165,35 +3171,67 @@ extract_range_from_binary_expr_1 (value_range *vr,
set_value_range (vr, type, min, max, NULL);
}
+static void
+extract_range_from_binary_expr_1 (value_range *vr,
+ enum tree_code code, tree expr_type,
+ value_range *vr0_, value_range *vr1_)
+{
+ bool tmp = true;
+ extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, vr1_,
+ false, &tmp);
+}
+
/* Extract range information from a binary expression OP0 CODE OP1 based on
the ranges of each of its operands with resulting type EXPR_TYPE.
The resulting range is stored in *VR. */
-static void
+void
extract_range_from_binary_expr (value_range *vr,
enum tree_code code,
- tree expr_type, tree op0, tree op1)
+ tree expr_type, tree op0, tree op1,
+ bool get_ovf, bool *ovf)
{
value_range vr0 = VR_INITIALIZER;
value_range vr1 = VR_INITIALIZER;
+ if (get_ovf)
+ *ovf = true;
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
if (TREE_CODE (op0) == SSA_NAME)
- vr0 = *(get_value_range (op0));
+ {
+ value_range *vtmp = get_value_range (op0);
+ if (vtmp == NULL)
+ {
+ vr->type = VR_VARYING;
+ return;
+ }
+ else
+ vr0 = *vtmp;
+ }
else if (is_gimple_min_invariant (op0))
set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
if (TREE_CODE (op1) == SSA_NAME)
- vr1 = *(get_value_range (op1));
+ {
+ value_range *vtmp = get_value_range (op1);
+ if (vtmp == NULL)
+ {
+ vr->type = VR_VARYING;
+ return;
+ }
+ else
+ vr1 = *vtmp;
+ }
else if (is_gimple_min_invariant (op1))
set_value_range_to_value (&vr1, op1, NULL);
else
set_value_range_to_varying (&vr1);
- extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1,
+ get_ovf, ovf);
/* Try harder for PLUS and MINUS if the range of one operand is symbolic
and based on the other operand, for example if it was deduced from a
@@ -3221,7 +3259,8 @@ extract_range_from_binary_expr (value_range *vr,
else
set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
- extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1,
+ get_ovf, ovf);
}
if (vr->type == VR_VARYING
@@ -3245,10 +3284,21 @@ extract_range_from_binary_expr (value_range *vr,
else
set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
- extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1,
+ get_ovf, ovf);
}
}
+static void
+extract_range_from_binary_expr (value_range *vr,
+ enum tree_code code,
+ tree expr_type, tree op0, tree op1)
+{
+ bool tmp = true;
+ extract_range_from_binary_expr (vr, code, expr_type, op0, op1,
+ false, &tmp);
+}
+
/* Extract range information from a unary operation CODE based on
the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE.
The resulting range is stored in *VR. */
@@ -10443,7 +10493,7 @@ identify_jump_threads (void)
/* We're basically looking for a switch or any kind of conditional with
integral or pointer type arguments. Note the type of the second
argument will be the same as the first argument, so no need to
- check it explicitly.
+ check it explicitly.
We also handle the case where there are no statements in the
block. This come up with forwarder blocks that are not
@@ -48,7 +48,13 @@ struct GTY(()) value_range
bitmap equiv;
};
+#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
+
extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1);
extern void vrp_meet (value_range *vr0, const value_range *vr1);
extern void dump_value_range (FILE *, const value_range *);
-
+extern bool binop_overflow (enum tree_code op, tree t1, tree t2, tree type);
+extern void extract_range_from_binary_expr (value_range *vr,
+ enum tree_code code,
+ tree expr_type, tree op0, tree op1,
+ bool get_ovf, bool *ovf);