From 8dc2384cc96eeab306f1267118a194a50eb37953 Mon Sep 17 00:00:00 2001 From: Roger Sayle Date: Sat, 8 May 2004 17:36:21 +0000 Subject: [PATCH] fold-const.c (fold_div_compare): New function to optimize X/C1 op C2 where op is a comparison operator and C1... * fold-const.c (fold_div_compare): New function to optimize X/C1 op C2 where op is a comparison operator and C1 and C2 are integer constants into a range check. (fold): Call fold_div_compare. * gcc.c-torture/execute/divcmp-1.c: New test case. * gcc.c-torture/execute/divcmp-2.c: New test case. * gcc.c-torture/execute/divcmp-3.c: New test case. From-SVN: r81645 --- gcc/ChangeLog | 7 + gcc/fold-const.c | 165 ++++++++++++ gcc/testsuite/ChangeLog | 6 + gcc/testsuite/gcc.c-torture/execute/divcmp-1.c | 356 +++++++++++++++++++++++++ gcc/testsuite/gcc.c-torture/execute/divcmp-2.c | 92 +++++++ gcc/testsuite/gcc.c-torture/execute/divcmp-3.c | 97 +++++++ 6 files changed, 723 insertions(+) create mode 100644 gcc/testsuite/gcc.c-torture/execute/divcmp-1.c create mode 100644 gcc/testsuite/gcc.c-torture/execute/divcmp-2.c create mode 100644 gcc/testsuite/gcc.c-torture/execute/divcmp-3.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 545eed8..9b395e8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2004-05-08 Roger Sayle + + * fold-const.c (fold_div_compare): New function to optimize X/C1 op C2 + where op is a comparison operator and C1 and C2 are integer constants + into a range check. + (fold): Call fold_div_compare. + 2004-05-08 Eric Botcazou * doc/install.texi (sparc-sun-solaris2*): Document bootstrap diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 1c2bdf4..7d04db6 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -109,6 +109,7 @@ static bool fold_real_zero_addition_p (tree, tree, int); static tree fold_mathfn_compare (enum built_in_function, enum tree_code, tree, tree, tree); static tree fold_inf_compare (enum tree_code, tree, tree, tree); +static tree fold_div_compare (enum tree_code, tree, tree, tree); static bool reorder_operands_p (tree, tree); static bool tree_swap_operands_p (tree, tree, bool); @@ -5215,6 +5216,156 @@ fold_inf_compare (enum tree_code code, tree type, tree arg0, tree arg1) return NULL_TREE; } +/* Subroutine of fold() that optimizes comparisons of a division by + a non-zero integer constant against an integer constant, i.e. + X/C1 op C2. + + CODE is the comparison operator: EQ_EXPR, NE_EXPR, GT_EXPR, LT_EXPR, + GE_EXPR or LE_EXPR. TYPE is the type of the result and ARG0 and ARG1 + are the operands of the comparison. ARG1 must be a TREE_REAL_CST. + + The function returns the constant folded tree if a simplification + can be made, and NULL_TREE otherwise. */ + +static tree +fold_div_compare (enum tree_code code, tree type, tree arg0, tree arg1) +{ + tree prod, tmp, hi, lo; + tree arg00 = TREE_OPERAND (arg0, 0); + tree arg01 = TREE_OPERAND (arg0, 1); + unsigned HOST_WIDE_INT lpart; + HOST_WIDE_INT hpart; + int overflow; + + /* We have to do this the hard way to detect unsigned overflow. + prod = int_const_binop (MULT_EXPR, arg01, arg1, 0); */ + overflow = mul_double (TREE_INT_CST_LOW (arg01), + TREE_INT_CST_HIGH (arg01), + TREE_INT_CST_LOW (arg1), + TREE_INT_CST_HIGH (arg1), &lpart, &hpart); + prod = build_int_2 (lpart, hpart); + TREE_TYPE (prod) = TREE_TYPE (arg00); + TREE_OVERFLOW (prod) = force_fit_type (prod, overflow) + || TREE_INT_CST_HIGH (prod) != hpart + || TREE_INT_CST_LOW (prod) != lpart; + TREE_CONSTANT_OVERFLOW (prod) = TREE_OVERFLOW (prod); + + if (TYPE_UNSIGNED (TREE_TYPE (arg0))) + { + tmp = int_const_binop (MINUS_EXPR, arg01, integer_one_node, 0); + lo = prod; + + /* Likewise hi = int_const_binop (PLUS_EXPR, prod, tmp, 0). */ + overflow = add_double (TREE_INT_CST_LOW (prod), + TREE_INT_CST_HIGH (prod), + TREE_INT_CST_LOW (tmp), + TREE_INT_CST_HIGH (tmp), + &lpart, &hpart); + hi = build_int_2 (lpart, hpart); + TREE_TYPE (hi) = TREE_TYPE (arg00); + TREE_OVERFLOW (hi) = force_fit_type (hi, overflow) + || TREE_INT_CST_HIGH (hi) != hpart + || TREE_INT_CST_LOW (hi) != lpart + || TREE_OVERFLOW (prod); + TREE_CONSTANT_OVERFLOW (hi) = TREE_OVERFLOW (hi); + } + else if (tree_int_cst_sgn (arg01) >= 0) + { + tmp = int_const_binop (MINUS_EXPR, arg01, integer_one_node, 0); + switch (tree_int_cst_sgn (arg1)) + { + case -1: + lo = int_const_binop (MINUS_EXPR, prod, tmp, 0); + hi = prod; + break; + + case 0: + lo = fold_negate_const (tmp, TREE_TYPE (arg0)); + hi = tmp; + break; + + case 1: + hi = int_const_binop (PLUS_EXPR, prod, tmp, 0); + lo = prod; + break; + + default: + abort (); + } + } + else + { + tmp = int_const_binop (PLUS_EXPR, arg01, integer_one_node, 0); + switch (tree_int_cst_sgn (arg1)) + { + case -1: + hi = int_const_binop (MINUS_EXPR, prod, tmp, 0); + lo = prod; + break; + + case 0: + hi = fold_negate_const (tmp, TREE_TYPE (arg0)); + lo = tmp; + break; + + case 1: + lo = int_const_binop (PLUS_EXPR, prod, tmp, 0); + hi = prod; + break; + + default: + abort (); + } + } + + switch (code) + { + case EQ_EXPR: + if (TREE_OVERFLOW (lo) && TREE_OVERFLOW (hi)) + return omit_one_operand (type, integer_zero_node, arg00); + if (TREE_OVERFLOW (hi)) + return fold (build2 (GE_EXPR, type, arg00, lo)); + if (TREE_OVERFLOW (lo)) + return fold (build2 (LE_EXPR, type, arg00, hi)); + return build_range_check (type, arg00, 1, lo, hi); + + case NE_EXPR: + if (TREE_OVERFLOW (lo) && TREE_OVERFLOW (hi)) + return omit_one_operand (type, integer_one_node, arg00); + if (TREE_OVERFLOW (hi)) + return fold (build2 (LT_EXPR, type, arg00, lo)); + if (TREE_OVERFLOW (lo)) + return fold (build2 (GT_EXPR, type, arg00, hi)); + return build_range_check (type, arg00, 0, lo, hi); + + case LT_EXPR: + if (TREE_OVERFLOW (lo)) + return omit_one_operand (type, integer_zero_node, arg00); + return fold (build2 (LT_EXPR, type, arg00, lo)); + + case LE_EXPR: + if (TREE_OVERFLOW (hi)) + return omit_one_operand (type, integer_one_node, arg00); + return fold (build2 (LE_EXPR, type, arg00, hi)); + + case GT_EXPR: + if (TREE_OVERFLOW (hi)) + return omit_one_operand (type, integer_zero_node, arg00); + return fold (build2 (GT_EXPR, type, arg00, hi)); + + case GE_EXPR: + if (TREE_OVERFLOW (lo)) + return omit_one_operand (type, integer_one_node, arg00); + return fold (build2 (GE_EXPR, type, arg00, lo)); + + default: + break; + } + + return NULL_TREE; +} + + /* If CODE with arguments ARG0 and ARG1 represents a single bit equality/inequality test, then return a simplified form of the test using shifts and logical operations. Otherwise return @@ -7902,6 +8053,20 @@ fold (tree expr) integer_zero_node)); } + /* We can fold X/C1 op C2 where C1 and C2 are integer constants + into a single range test. */ + if (TREE_CODE (arg0) == TRUNC_DIV_EXPR + && TREE_CODE (arg1) == INTEGER_CST + && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST + && !integer_zerop (TREE_OPERAND (arg0, 1)) + && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)) + && !TREE_OVERFLOW (arg1)) + { + t1 = fold_div_compare (code, type, arg0, arg1); + if (t1 != NULL_TREE) + return t1; + } + /* Both ARG0 and ARG1 are known to be constants at this point. */ t1 = fold_relational_const (code, type, arg0, arg1); return (t1 == NULL_TREE ? t : t1); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index cb5a6b8..09ca29a 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2004-05-08 Roger Sayle + + * gcc.c-torture/execute/divcmp-1.c: New test case. + * gcc.c-torture/execute/divcmp-2.c: New test case. + * gcc.c-torture/execute/divcmp-3.c: New test case. + 2004-05-07 Eric Botcazou * g++.dg/other/pragma-re-2.C: New test. diff --git a/gcc/testsuite/gcc.c-torture/execute/divcmp-1.c b/gcc/testsuite/gcc.c-torture/execute/divcmp-1.c new file mode 100644 index 0000000..0a7f305 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/divcmp-1.c @@ -0,0 +1,356 @@ +extern void abort(void); + +int test1(int x) +{ + return x/10 == 2; +} + +int test1u(unsigned int x) +{ + return x/10U == 2; +} + +int test2(int x) +{ + return x/10 == 0; +} + +int test2u(unsigned int x) +{ + return x/10U == 0; +} + +int test3(int x) +{ + return x/10 != 2; +} + +int test3u(unsigned int x) +{ + return x/10U != 2; +} + +int test4(int x) +{ + return x/10 != 0; +} + +int test4u(unsigned int x) +{ + return x/10U != 0; +} + +int test5(int x) +{ + return x/10 < 2; +} + +int test5u(unsigned int x) +{ + return x/10U < 2; +} + +int test6(int x) +{ + return x/10 < 0; +} + +int test7(int x) +{ + return x/10 <= 2; +} + +int test7u(unsigned int x) +{ + return x/10U <= 2; +} + +int test8(int x) +{ + return x/10 <= 0; +} + +int test8u(unsigned int x) +{ + return x/10U <= 0; +} + +int test9(int x) +{ + return x/10 > 2; +} + +int test9u(unsigned int x) +{ + return x/10U > 2; +} + +int test10(int x) +{ + return x/10 > 0; +} + +int test10u(unsigned int x) +{ + return x/10U > 0; +} + +int test11(int x) +{ + return x/10 >= 2; +} + +int test11u(unsigned int x) +{ + return x/10U >= 2; +} + +int test12(int x) +{ + return x/10 >= 0; +} + + +int main() +{ + if (test1(19) != 0) + abort (); + if (test1(20) != 1) + abort (); + if (test1(29) != 1) + abort (); + if (test1(30) != 0) + abort (); + + if (test1u(19) != 0) + abort (); + if (test1u(20) != 1) + abort (); + if (test1u(29) != 1) + abort (); + if (test1u(30) != 0) + abort (); + + if (test2(0) != 1) + abort (); + if (test2(9) != 1) + abort (); + if (test2(10) != 0) + abort (); + if (test2(-1) != 1) + abort (); + if (test2(-9) != 1) + abort (); + if (test2(-10) != 0) + abort (); + + if (test2u(0) != 1) + abort (); + if (test2u(9) != 1) + abort (); + if (test2u(10) != 0) + abort (); + if (test2u(-1) != 0) + abort (); + if (test2u(-9) != 0) + abort (); + if (test2u(-10) != 0) + abort (); + + if (test3(19) != 1) + abort (); + if (test3(20) != 0) + abort (); + if (test3(29) != 0) + abort (); + if (test3(30) != 1) + abort (); + + if (test3u(19) != 1) + abort (); + if (test3u(20) != 0) + abort (); + if (test3u(29) != 0) + abort (); + if (test3u(30) != 1) + abort (); + + if (test4(0) != 0) + abort (); + if (test4(9) != 0) + abort (); + if (test4(10) != 1) + abort (); + if (test4(-1) != 0) + abort (); + if (test4(-9) != 0) + abort (); + if (test4(-10) != 1) + abort (); + + if (test4u(0) != 0) + abort (); + if (test4u(9) != 0) + abort (); + if (test4u(10) != 1) + abort (); + if (test4u(-1) != 1) + abort (); + if (test4u(-9) != 1) + abort (); + if (test4u(-10) != 1) + abort (); + + if (test5(19) != 1) + abort (); + if (test5(20) != 0) + abort (); + if (test5(29) != 0) + abort (); + if (test5(30) != 0) + abort (); + + if (test5u(19) != 1) + abort (); + if (test5u(20) != 0) + abort (); + if (test5u(29) != 0) + abort (); + if (test5u(30) != 0) + abort (); + + if (test6(0) != 0) + abort (); + if (test6(9) != 0) + abort (); + if (test6(10) != 0) + abort (); + if (test6(-1) != 0) + abort (); + if (test6(-9) != 0) + abort (); + if (test6(-10) != 1) + abort (); + + if (test7(19) != 1) + abort (); + if (test7(20) != 1) + abort (); + if (test7(29) != 1) + abort (); + if (test7(30) != 0) + abort (); + + if (test7u(19) != 1) + abort (); + if (test7u(20) != 1) + abort (); + if (test7u(29) != 1) + abort (); + if (test7u(30) != 0) + abort (); + + if (test8(0) != 1) + abort (); + if (test8(9) != 1) + abort (); + if (test8(10) != 0) + abort (); + if (test8(-1) != 1) + abort (); + if (test8(-9) != 1) + abort (); + if (test8(-10) != 1) + abort (); + + if (test8u(0) != 1) + abort (); + if (test8u(9) != 1) + abort (); + if (test8u(10) != 0) + abort (); + if (test8u(-1) != 0) + abort (); + if (test8u(-9) != 0) + abort (); + if (test8u(-10) != 0) + abort (); + + if (test9(19) != 0) + abort (); + if (test9(20) != 0) + abort (); + if (test9(29) != 0) + abort (); + if (test9(30) != 1) + abort (); + + if (test9u(19) != 0) + abort (); + if (test9u(20) != 0) + abort (); + if (test9u(29) != 0) + abort (); + if (test9u(30) != 1) + abort (); + + if (test10(0) != 0) + abort (); + if (test10(9) != 0) + abort (); + if (test10(10) != 1) + abort (); + if (test10(-1) != 0) + abort (); + if (test10(-9) != 0) + abort (); + if (test10(-10) != 0) + abort (); + + if (test10u(0) != 0) + abort (); + if (test10u(9) != 0) + abort (); + if (test10u(10) != 1) + abort (); + if (test10u(-1) != 1) + abort (); + if (test10u(-9) != 1) + abort (); + if (test10u(-10) != 1) + abort (); + + if (test11(19) != 0) + abort (); + if (test11(20) != 1) + abort (); + if (test11(29) != 1) + abort (); + if (test11(30) != 1) + abort (); + + if (test11u(19) != 0) + abort (); + if (test11u(20) != 1) + abort (); + if (test11u(29) != 1) + abort (); + if (test11u(30) != 1) + abort (); + + if (test12(0) != 1) + abort (); + if (test12(9) != 1) + abort (); + if (test12(10) != 1) + abort (); + if (test12(-1) != 1) + abort (); + if (test12(-9) != 1) + abort (); + if (test12(-10) != 0) + abort (); + + return 0; +} + diff --git a/gcc/testsuite/gcc.c-torture/execute/divcmp-2.c b/gcc/testsuite/gcc.c-torture/execute/divcmp-2.c new file mode 100644 index 0000000..b059b8f --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/divcmp-2.c @@ -0,0 +1,92 @@ +extern void abort (void); + +int test1(int x) +{ + return x/10 == 2; +} + +int test2(int x) +{ + return x/10 == 0; +} + +int test3(int x) +{ + return x/10 == -2; +} + +int test4(int x) +{ + return x/-10 == 2; +} + +int test5(int x) +{ + return x/-10 == 0; +} + +int test6(int x) +{ + return x/-10 == -2; +} + + +int main() +{ + if (test1(19) != 0) + abort (); + if (test1(20) != 1) + abort (); + if (test1(29) != 1) + abort (); + if (test1(30) != 0) + abort (); + + if (test2(-10) != 0) + abort (); + if (test2(-9) != 1) + abort (); + if (test2(9) != 1) + abort (); + if (test2(10) != 0) + abort (); + + if (test3(-30) != 0) + abort (); + if (test3(-29) != 1) + abort (); + if (test3(-20) != 1) + abort (); + if (test3(-19) != 0) + abort (); + + if (test4(-30) != 0) + abort (); + if (test4(-29) != 1) + abort (); + if (test4(-20) != 1) + abort (); + if (test4(-19) != 0) + abort (); + + if (test5(-10) != 0) + abort (); + if (test5(-9) != 1) + abort (); + if (test5(9) != 1) + abort (); + if (test5(10) != 0) + abort (); + + if (test6(19) != 0) + abort (); + if (test6(20) != 1) + abort (); + if (test6(29) != 1) + abort (); + if (test6(30) != 0) + abort (); + + return 0; +} + diff --git a/gcc/testsuite/gcc.c-torture/execute/divcmp-3.c b/gcc/testsuite/gcc.c-torture/execute/divcmp-3.c new file mode 100644 index 0000000..ba52c9e --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/divcmp-3.c @@ -0,0 +1,97 @@ +extern void abort(void); + +int test1(char x) +{ + return x/100 == 3; +} + +int test1u(unsigned char x) +{ + return x/100 == 3; +} + +int test2(char x) +{ + return x/100 != 3; +} + +int test2u(unsigned char x) +{ + return x/100 != 3; +} + +int test3(char x) +{ + return x/100 < 3; +} + +int test3u(unsigned char x) +{ + return x/100 < 3; +} + +int test4(char x) +{ + return x/100 <= 3; +} + +int test4u(unsigned char x) +{ + return x/100 <= 3; +} + +int test5(char x) +{ + return x/100 > 3; +} + +int test5u(unsigned char x) +{ + return x/100 > 3; +} + +int test6(char x) +{ + return x/100 >= 3; +} + +int test6u(unsigned char x) +{ + return x/100 >= 3; +} + + +int main() +{ + int c; + + for (c=-128; c<256; c++) + { + if (test1(c) != 0) + abort (); + if (test1u(c) != 0) + abort (); + if (test2(c) != 1) + abort (); + if (test2u(c) != 1) + abort (); + if (test3(c) != 1) + abort (); + if (test3u(c) != 1) + abort (); + if (test4(c) != 1) + abort (); + if (test4u(c) != 1) + abort (); + if (test5(c) != 0) + abort (); + if (test5u(c) != 0) + abort (); + if (test6(c) != 0) + abort (); + if (test6u(c) != 0) + abort (); + } + return 0; +} + -- 2.7.4