This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] New fold_range_test optimizations
- From: Jakub Jelinek <jakub at redhat dot com>
- To: Richard Henderson <rth at redhat dot com>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 17 Jun 2004 13:35:29 +0200
- Subject: [PATCH] New fold_range_test optimizations
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
Hi!
I have noticed even simple tests like:
unsigned long l;
...
if (l == 0 || l == -1UL) foo ();
aren't optimized into a single comparison
if (l - 1 > -3UL) foo ();
while tests like if (l == 3 || l == 4 || l == 5) foo (); are.
The problem seems to be that when merge_ranges tests the ranges,
it only checks if high0 + 1 == low1, but doesn't check if the ranges
are adjacent the other way, i.e. high1 == max and low0 == min.
In this case this patch merges - [-, x] and - [y, -] into + [x + 1, y - 1]
(as long as x + 1 < y, if x + 1 == y into - [-, -]).
I hope this is a safe thing to do even for signed types in C, changing
int i;
...
assert (x > INT_MIN && x + 1 < y && y < INT_MAX);
if ((i >= INT_MIN && i <= x) || (i >= y && i <= INT_MAX))
into
if (!(i >= x + 1 && i <= y - 1))
.
The first hunk is just an speed optimization, build_range_check calls itself
recursively with the exact same arguments but different in_p and doesn't use
that argument anywhere in the rest of the function, so if the recursive
call returns 0, I don't think we need to go through the whole function
once again.
The middle hunk is for optimization of:
int i;
...
if (i == INT_MIN || i == INT_MAX)
Here, it is converted into if (!(i >= INT_MIN + 1 && i <= INT_MAX - 1))
range, but because etype is a signed type, INT_MAX - 1 - INT_MIN - 1
overflows. I hope we can safely retry with unsigned type.
I have added a couple of tests and further tests can be added into the
framework later.
Another optimization which might be useful would be to handle even tests
where the values don't come in sorted order.
ATM, GCC optimizes
if (i == 0 || i == 1 || i == 2 || i == 3 || i == 4 || i == 5)
but doesn't optimize
if (i == 0 || i == 3 || i == 1 || i == 4 || i == 2 || i == 5)
at all (as no consecutive tests build a meaningful range).
I wonder if fold_range_test shouldn't check for the same operators
as TREE_CODE (exp) and if it sees them, shouldn't make_range's individually,
sort them and try to merge them one by one after sorting.
With numbers unsorted comparisons perhaps don't happen that often in real
world, but with enums I'm pretty sure programmers don't write them
always in the order of ascending or descending values.
2004-06-17 Jakub Jelinek <jakub@redhat.com>
* fold-const.c (build_range_check): If !in_p and recursive call
fails, exit immediately. If high - low overflows and etype is
a signed type, retry with unsigned etype.
(merge_ranges): If !in0_p and !in1_p, handle even range2 adjacent
to range1 at TYPE_MAX_VALUE and TYPE_MIN_VALUE.
* gcc.dg/range-test-1.c: New test.
--- gcc/fold-const.c.jj 2004-06-14 16:22:42.000000000 +0200
+++ gcc/fold-const.c 2004-06-17 15:15:08.544767126 +0200
@@ -3787,9 +3787,14 @@ build_range_check (tree type, tree exp,
tree etype = TREE_TYPE (exp);
tree value;
- if (! in_p
- && (0 != (value = build_range_check (type, exp, 1, low, high))))
- return invert_truthvalue (value);
+ if (! in_p)
+ {
+ value = build_range_check (type, exp, 1, low, high);
+ if (value != 0)
+ return invert_truthvalue (value);
+
+ return 0;
+ }
if (low == 0 && high == 0)
return fold_convert (type, integer_one_node);
@@ -3845,8 +3850,17 @@ build_range_check (tree type, tree exp,
}
}
- if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
- && ! TREE_OVERFLOW (value))
+ value = const_binop (MINUS_EXPR, high, low, 0);
+ if (value != 0 && TREE_OVERFLOW (value) && ! TYPE_UNSIGNED (etype))
+ {
+ etype = lang_hooks.types.unsigned_type (etype);
+ high = fold_convert (etype, high);
+ low = fold_convert (etype, low);
+ exp = fold_convert (etype, exp);
+ value = const_binop (MINUS_EXPR, high, low, 0);
+ }
+
+ if (value != 0 && ! TREE_OVERFLOW (value))
return build_range_check (type,
fold (build2 (MINUS_EXPR, etype, exp, low)),
1, fold_convert (etype, integer_zero_node),
@@ -3976,7 +3990,80 @@ merge_ranges (int *pin_p, tree *plow, tr
1, low1, 0)))
in_p = 0, low = low0, high = high1;
else
- return 0;
+ {
+ /* Canonicalize - [min, x] into - [-, x]. */
+ if (low0 && TREE_CODE (low0) == INTEGER_CST)
+ switch (TREE_CODE (TREE_TYPE (low0)))
+ {
+ case INTEGER_TYPE:
+ case ENUMERAL_TYPE:
+ case CHAR_TYPE:
+ if (tree_int_cst_equal (low0,
+ TYPE_MIN_VALUE (TREE_TYPE (low0))))
+ low0 = 0;
+ break;
+ case POINTER_TYPE:
+ if (TYPE_UNSIGNED (TREE_TYPE (low0))
+ && integer_zerop (low0))
+ low0 = 0;
+ break;
+ default:
+ break;
+ }
+
+ /* Canonicalize - [x, max] into - [x, -]. */
+ if (high1 && TREE_CODE (high1) == INTEGER_CST)
+ switch (TREE_CODE (TREE_TYPE (high1)))
+ {
+ case INTEGER_TYPE:
+ case ENUMERAL_TYPE:
+ case CHAR_TYPE:
+ if (tree_int_cst_equal (high1,
+ TYPE_MAX_VALUE (TREE_TYPE (high1))))
+ high1 = 0;
+ break;
+ case POINTER_TYPE:
+ if (TYPE_UNSIGNED (TREE_TYPE (high1))
+ && integer_zerop (range_binop (PLUS_EXPR, NULL_TREE,
+ high1, 1,
+ integer_one_node, 1)))
+ high1 = 0;
+ break;
+ default:
+ break;
+ }
+
+ /* The ranges might be also adjacent between the maximum and
+ minimum values of the given type. */
+ if (low0 == 0 && high1 == 0)
+ {
+ tem = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
+ integer_one_node, 1);
+ if (tem == 0)
+ return 0;
+
+ /* For - [{min,-}, x] and - [x + 1, {max,-}] the result is
+ false. */
+ if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
+ tem, 1, low1, 1)))
+ in_p = 0, low = high = 0;
+ else
+ {
+ low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
+ integer_one_node, 1);
+ high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
+ integer_one_node, 0);
+ if (low == 0 || high == 0)
+ return 0;
+
+ /* For - [{min,-}, x] and - [y, {max,-}] where x + 1 < y
+ return + [x + 1, y - 1]. */
+ in_p = 1;
+ }
+ }
+ else
+ return 0;
+ }
}
else if (subset)
in_p = 0, low = low0, high = high0;
--- gcc/testsuite/gcc.dg/range-test-1.c.jj 2004-06-17 13:30:07.501996029 +0200
+++ gcc/testsuite/gcc.dg/range-test-1.c 2004-06-17 15:22:40.059849744 +0200
@@ -0,0 +1,165 @@
+/* Test fold-const.c (fold_range_test) optimizations. */
+/* { dg-do execute } */
+/* { dg-options "-O2" } */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <limits.h>
+
+#if (INT_MAX == 2147483647) && (INT_MIN == -2147483648) \
+ && (SCHAR_MIN == -128) && (SCHAR_MAX == 127) \
+ && (UCHAR_MIN == 0) && (UCHAR_MAX == 255)
+
+#ifndef T
+
+enum integers
+{
+ int_smallest = INT_MIN,
+ int_2ndsmallest = INT_MIN + 1,
+ int_3rdsmallest = INT_MIN + 2,
+ int_minus2 = -2,
+ int_minus1 = -1,
+ int_zero = 0,
+ int_one = 1,
+ int_two = 2,
+ int_3rdlargest = INT_MAX - 2,
+ int_2ndlargest = INT_MAX - 1,
+ int_largest = INT_MAX
+};
+
+int var;
+void
+check (void)
+{
+ ++var;
+}
+
+#define T(IDX, TYPE, TEST, YESARR, NOARR) \
+void __attribute__((noinline)) \
+test##IDX (TYPE x) \
+{ \
+ if (TEST) \
+ check (); \
+}
+#include "range-test-1.c"
+#undef T
+
+int
+main (void)
+{
+ int i, fails = 0;
+
+#define C ,
+#define T(IDX, TYPE, TEST, YESARR, NOARR) \
+ { \
+ static TYPE yesarr##IDX [] = YESARR; \
+ static TYPE noarr##IDX [] = NOARR; \
+ for (i = 0; i < (int) (sizeof (yesarr##IDX) / sizeof (TYPE)); ++i) \
+ { \
+ var = 0; \
+ test##IDX (yesarr##IDX [i]); \
+ if (var != 1) \
+ printf ("test" #IDX " failed for yesarr [%u]\n", i), ++fails; \
+ } \
+ var = 0; \
+ for (i = 0; i < (int) (sizeof (noarr##IDX) / sizeof (TYPE)); ++i) \
+ { \
+ test##IDX (noarr##IDX [i]); \
+ if (var != 0) \
+ printf ("test" #IDX " failed for noarr [%u]\n", i), ++fails; \
+ } \
+ }
+#include "range-test-1.c"
+#undef T
+
+ if (fails)
+ abort ();
+
+ exit (0);
+}
+
+#else
+
+/* Use `C' instead of `,' below to separate array entries. */
+
+/* These ought to be all optimized into single comparison. */
+T(1, unsigned int, x == 0 || x == 1,
+ { 0 C 1 }, { -1U C 2 C 12 C 35 C 0x7fffffff C 0x80000000 })
+T(2, unsigned int, x == 0 || x == -1U || x == -2U,
+ { 0 C -1U C -2U }, { -3U C -6U C 1 C 2 C 12 C 35 C 0x7fffffff C 0x80000000 })
+T(3, unsigned int, x == 0 || x == 1 || x == 2,
+ { 0 C 1 C 2 }, { -3U C -6U C -1U C -2U C 12 C 35 C 0x7fffffff C 0x80000000 })
+T(4, unsigned int, x == 3 || x == 4 || x == 5 || x == 6,
+ { 3 C 4 C 5 C 6 }, { -3U C 0 C 1 C 2 C 7 C 8 C 12 C 0x7fffffff C 0x80000000 })
+T(5, unsigned int, x == -3U || x == -4U || x == -5U || x == -6U,
+ { -3U C -4U C -5U C -6U }, { -7U C -8U C -2U C -1U C 1 C 2 C 0x7fffffff C 0x80000000 })
+T(6, unsigned int, x == -3U || x == -4U || x == -5U,
+ { -3U C -4U C -5U }, { -6U C -7U C -8U C -2U C -1U C 1 C 2 C 0x7fffffff C 0x80000000 })
+T(7, char *, x == (char *) -3UL || x == (char *) -4UL || x == (char *) -5UL,
+ { (char *) -3UL C (char *) -4UL C (char *) -5UL },
+ { (char *) -6UL C (char *) -20UL C (char *) -2UL C (char *) -1UL C (char *) 0
+ C (char *) 1UL C (char *) 35UL C (char *) 0x7fffffffUL C (char *) 0x80000000UL })
+T(8, unsigned long, x == -2UL || x == -1UL || x == 0,
+ { 0 C -1UL C -2UL }, { -3UL C -6UL C 1 C 2 C 12 C 35 C 0x7fffffff C 0x80000000 })
+T(9, unsigned long, x >= -4UL || x <= 8,
+ { -4UL C -3UL C -2UL C -1UL C 0 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 },
+ { -7UL C -5UL C 9 C 10 C 61 C 127 C 0x7fffffff C 0x80000000 })
+T(10, signed char, x == 0 || x == -1 || x == -2 || x == -3,
+ { 0 C -1 C -2 C -3 }, { -4 C -5 C 1 C 2 C 3 C 35 C -24 })
+T(11, int, x == 0 || x == 1,
+ { 0 C 1 }, { -1 C 2 C 12 C 35 C INT_MAX C INT_MIN })
+T(12, int, x == 0 || x == -1 || x == -2,
+ { 0 C -1 C -2 }, { -3 C -6 C 1 C 2 C 12 C 35 C INT_MAX C INT_MIN })
+T(13, int, x == 0 || x == 1 || x == 2,
+ { 0 C 1 C 2 }, { -3 C -6 C -1 C -2 C 12 C 35 C INT_MAX C INT_MIN })
+T(14, int, x == 3 || x == 4 || x == 5 || x == 6,
+ { 3 C 4 C 5 C 6 }, { -3 C 0 C 1 C 2 C 7 C 8 C 12 C INT_MAX C INT_MIN })
+T(15, int, x == -3 || x == -4 || x == -5 || x == -6,
+ { -3 C -4 C -5 C -6 }, { -7 C -8 C -2 C -1 C 1 C 2 C INT_MAX C INT_MIN })
+T(16, int, x == -3 || x == -4 || x == -5,
+ { -3 C -4 C -5 }, { -6 C -7 C -8 C -2 C -1 C 1 C 2 C INT_MAX C INT_MIN })
+T(17, unsigned int, (x >= -8U && x <= -3U) || x == -2U || x == -1U || x == 0 || x == 1 || x == 2,
+ { -8U C -7U C -6U C -5U C -4U C -3U C -2U C -1U C 0 C 1 C 2 },
+ { -9U C -10U C 3 C 4 C 12 C -54U C INT_MAX C INT_MIN })
+T(18, int, (x >= -8 && x <= -3) || x == -2 || x == -1 || x == 0 || x == 1 || x == 2,
+ { -8 C -7 C -6 C -5 C -4 C -3 C -2 C -1 C 0 C 1 C 2 },
+ { -9 C -10 C 3 C 4 C 12 C -54 C INT_MAX C INT_MIN })
+T(19, unsigned long, (x >= 0 && x <= 16) || (x >= 18 && x <= -1UL),
+ { -3UL C -6UL C -1UL C 0 C 1 C 2 C 12 C 15 C 16 C 18 C 19 C 35 C 0x7fffffff
+ C 0x80000000 }, { 17 })
+T(20, char *, x == (char *) -1UL || x == 0,
+ { (char *) -1UL C 0 }, { (char *) -6UL C (char *) -20UL C (char *) -2UL
+ C (char *) 1UL C (char *) 35UL C (char *) 0x7fffffffUL C (char *) 0x80000000UL })
+T(21, enum integers, x == int_zero || x == int_one,
+ { int_zero C int_one }, { int_minus1 C int_two C 12 C 35 C int_largest C int_smallest })
+T(22, int, x == INT_MIN || x == INT_MAX,
+ { INT_MIN C INT_MAX },
+ { -1 C 0 C 1 C INT_MAX - 1 C INT_MAX - 2 C INT_MIN + 1 C INT_MIN + 2 })
+T(23, int, x == INT_MIN + 1 || x == INT_MIN + 2 || x == INT_MIN || x == INT_MAX,
+ { INT_MIN + 1 C INT_MIN + 2 C INT_MIN C INT_MAX },
+ { -1 C 0 C 1 C INT_MAX - 1 C INT_MAX - 2 C INT_MIN + 3 C INT_MIN + 4 })
+T(24, signed char, x == SCHAR_MIN || x == SCHAR_MAX,
+ { SCHAR_MIN C SCHAR_MAX },
+ { -1 C 0 C 1 C SCHAR_MAX - 1 C SCHAR_MAX - 2 C SCHAR_MIN + 1 C SCHAR_MIN + 2 })
+T(25, enum integers, x == int_smallest || x == int_largest,
+ { int_smallest C int_largest }, { int_minus1 C int_zero C int_one
+ C int_2ndsmallest C int_2ndlargest C int_3rdsmallest C int_3rdlargest })
+
+/* This should be optimized into unconditional jump. */
+T(o1, unsigned long, (x >= 0 && x <= 16) || (x >= 17 && x <= -1UL),
+ { -3UL C -6UL C -1UL C 0 C 1 C 2 C 12 C 15 C 16 C 17 C 18 C 19 C 35 C 0x7fffffff
+ C 0x80000000 }, { })
+
+/* This should be eventually optimized into a single comparison. */
+T(td1, unsigned char, x == 0 || x == 4 || x == 1 || x == 5 || x == 2 || x == 6 || x == 3,
+ { 0 C 1 C 2 C 3 C 4 C 5 C 6 }, { 7 C 8 C 127 C 128 C 254 C 255 })
+
+#endif
+
+#else
+int
+main (void)
+{
+ return 0;
+}
+#endif
Jakub