This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Optimize X/10 == 2 as (X-20) < 10
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 2 May 2004 13:44:51 -0600 (MDT)
- Subject: [PATCH] Optimize X/10 == 2 as (X-20) < 10
The following patch converts expressions of the form X/C1 op C2
into a range test, where C1 and C2 are integer constants, C1 is
not zero, and op is a relational/comparison operator.
For example, X/C == 0 is converted into "X < C" for unsigned
division, and the equivalent of "X > -C && X < C" for signed
division. It also handles boundary conditions, for example if
X is an unsigned char, X/100 >= 3 is always false, and X/100 == 2
is equivalent to X >= 200 (no need to test for an upper bound).
The following patch has been tested on i686-pc-linux-gnu with a
full "make bootstrap", all languages except treelang and regression
tested with a top-level "make -k check" with no new failures.
Ok for mainline? If there's no explicit approval or comment
after a week or so, I propose to go ahead and check this patch
in if there isn't any objection.
2004-05-02 Roger Sayle <roger@eyesopen.com>
* fold-const.c (fold): Optimize X/C1 op C2 where op is a comparison
operator and C1 and C2 are integer constants into a range check.
* 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.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.371
diff -c -3 -p -r1.371 fold-const.c
*** fold-const.c 29 Apr 2004 15:39:12 -0000 1.371
--- fold-const.c 2 May 2004 17:32:01 -0000
*************** fold (tree expr)
*** 7897,7902 ****
--- 7897,8044 ----
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))
+ {
+ 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;
+ }
+ }
+
/* 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);
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;
}
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;
}
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;
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833