* Move optimize_minmax_comparison to match.pd
@ 2016-06-12 8:30 Marc Glisse
2016-06-13 10:16 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Marc Glisse @ 2016-06-12 8:30 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: TEXT/PLAIN, Size: 504 bytes --]
Hello,
this move is pretty straightforward. The transformation would probably
work just fine for any type (floats, vectors), but I didn't want the
headache of checking the behavior for NaN.
Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
2016-06-13 Marc Glisse <marc.glisse@inria.fr>
* fold-const.c (optimize_minmax_comparison): Remove.
(fold_comparison): Remove call to the above.
* match.pd (MIN (X, Y) == X, MIN (X, 5) == 0, MIN (X, C1) < C2):
New transformations.
--
Marc Glisse
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-diff; name=minmax.diff, Size: 9173 bytes --]
Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c (revision 237336)
+++ gcc/fold-const.c (working copy)
@@ -121,22 +121,20 @@ static tree eval_subst (location_t, tree
static tree optimize_bit_field_compare (location_t, enum tree_code,
tree, tree, tree);
static int simple_operand_p (const_tree);
static bool simple_operand_p_2 (tree);
static tree range_binop (enum tree_code, tree, tree, int, tree, int);
static tree range_predecessor (tree);
static tree range_successor (tree);
static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
static tree fold_cond_expr_with_comparison (location_t, tree, tree, tree, tree);
static tree unextend (tree, int, int, tree);
-static tree optimize_minmax_comparison (location_t, enum tree_code,
- tree, tree, tree);
static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
static tree extract_muldiv_1 (tree, tree, enum tree_code, tree, bool *);
static tree fold_binary_op_with_conditional_arg (location_t,
enum tree_code, tree,
tree, tree,
tree, tree, int);
static tree fold_div_compare (location_t, enum tree_code, tree, tree, tree);
static bool reorder_operands_p (const_tree, const_tree);
static tree fold_negate_const (tree, tree);
static tree fold_not_const (const_tree, tree);
@@ -5972,124 +5970,20 @@ fold_truth_andor_1 (location_t loc, enum
ll_unsignedp || rl_unsignedp, ll_reversep);
ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask);
if (! all_ones_mask_p (ll_mask, lnbitsize))
result = build2_loc (loc, BIT_AND_EXPR, lntype, result, ll_mask);
return build2_loc (loc, wanted_code, truth_type, result,
const_binop (BIT_IOR_EXPR, l_const, r_const));
}
\f
-/* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
- constant. */
-
-static tree
-optimize_minmax_comparison (location_t loc, enum tree_code code, tree type,
- tree op0, tree op1)
-{
- tree arg0 = op0;
- enum tree_code op_code;
- tree comp_const;
- tree minmax_const;
- int consts_equal, consts_lt;
- tree inner;
-
- STRIP_SIGN_NOPS (arg0);
-
- op_code = TREE_CODE (arg0);
- minmax_const = TREE_OPERAND (arg0, 1);
- comp_const = fold_convert_loc (loc, TREE_TYPE (arg0), op1);
- consts_equal = tree_int_cst_equal (minmax_const, comp_const);
- consts_lt = tree_int_cst_lt (minmax_const, comp_const);
- inner = TREE_OPERAND (arg0, 0);
-
- /* If something does not permit us to optimize, return the original tree. */
- if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
- || TREE_CODE (comp_const) != INTEGER_CST
- || TREE_OVERFLOW (comp_const)
- || TREE_CODE (minmax_const) != INTEGER_CST
- || TREE_OVERFLOW (minmax_const))
- return NULL_TREE;
-
- /* Now handle all the various comparison codes. We only handle EQ_EXPR
- and GT_EXPR, doing the rest with recursive calls using logical
- simplifications. */
- switch (code)
- {
- case NE_EXPR: case LT_EXPR: case LE_EXPR:
- {
- tree tem
- = optimize_minmax_comparison (loc,
- invert_tree_comparison (code, false),
- type, op0, op1);
- if (tem)
- return invert_truthvalue_loc (loc, tem);
- return NULL_TREE;
- }
-
- case GE_EXPR:
- return
- fold_build2_loc (loc, TRUTH_ORIF_EXPR, type,
- optimize_minmax_comparison
- (loc, EQ_EXPR, type, arg0, comp_const),
- optimize_minmax_comparison
- (loc, GT_EXPR, type, arg0, comp_const));
-
- case EQ_EXPR:
- if (op_code == MAX_EXPR && consts_equal)
- /* MAX (X, 0) == 0 -> X <= 0 */
- return fold_build2_loc (loc, LE_EXPR, type, inner, comp_const);
-
- else if (op_code == MAX_EXPR && consts_lt)
- /* MAX (X, 0) == 5 -> X == 5 */
- return fold_build2_loc (loc, EQ_EXPR, type, inner, comp_const);
-
- else if (op_code == MAX_EXPR)
- /* MAX (X, 0) == -1 -> false */
- return omit_one_operand_loc (loc, type, integer_zero_node, inner);
-
- else if (consts_equal)
- /* MIN (X, 0) == 0 -> X >= 0 */
- return fold_build2_loc (loc, GE_EXPR, type, inner, comp_const);
-
- else if (consts_lt)
- /* MIN (X, 0) == 5 -> false */
- return omit_one_operand_loc (loc, type, integer_zero_node, inner);
-
- else
- /* MIN (X, 0) == -1 -> X == -1 */
- return fold_build2_loc (loc, EQ_EXPR, type, inner, comp_const);
-
- case GT_EXPR:
- if (op_code == MAX_EXPR && (consts_equal || consts_lt))
- /* MAX (X, 0) > 0 -> X > 0
- MAX (X, 0) > 5 -> X > 5 */
- return fold_build2_loc (loc, GT_EXPR, type, inner, comp_const);
-
- else if (op_code == MAX_EXPR)
- /* MAX (X, 0) > -1 -> true */
- return omit_one_operand_loc (loc, type, integer_one_node, inner);
-
- else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
- /* MIN (X, 0) > 0 -> false
- MIN (X, 0) > 5 -> false */
- return omit_one_operand_loc (loc, type, integer_zero_node, inner);
-
- else
- /* MIN (X, 0) > -1 -> X > -1 */
- return fold_build2_loc (loc, GT_EXPR, type, inner, comp_const);
-
- default:
- return NULL_TREE;
- }
-}
-\f
/* T is an integer expression that is being multiplied, divided, or taken a
modulus (CODE says which and what kind of divide or modulus) by a
constant C. See if we can eliminate that operation by folding it with
other operations already in T. WIDE_TYPE, if non-null, is a type that
should be used for the computation if wider than our type.
For example, if we are dividing (X * 8) + (Y * 16) by 4, we can return
(X * 2) + (Y * 4). We must, however, be assured that either the original
expression would not overflow or that overflow is undefined for the type
in the language in question.
@@ -8712,32 +8606,20 @@ fold_comparison (location_t loc, enum tr
TREE_TYPE (arg0),
variable1, cst),
variable2);
}
}
tem = maybe_canonicalize_comparison (loc, code, type, arg0, arg1);
if (tem)
return tem;
- /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
- constant, we can simplify it. */
- if (TREE_CODE (arg1) == INTEGER_CST
- && (TREE_CODE (arg0) == MIN_EXPR
- || TREE_CODE (arg0) == MAX_EXPR)
- && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
- {
- tem = optimize_minmax_comparison (loc, code, type, op0, op1);
- if (tem)
- return tem;
- }
-
/* If we are comparing an expression that just has comparisons
of two integer values, arithmetic expressions of those comparisons,
and constants, we can simplify it. There are only three cases
to check: the two values can either be equal, the first can be
greater, or the second can be greater. Fold the expression for
those three values. Since each value must be 0 or 1, we have
eight possibilities, each of which corresponds to the constant 0
or 1 or one of the six possible comparisons.
This handles common cases like (a > b) == 0 but also handles
Index: gcc/match.pd
===================================================================
--- gcc/match.pd (revision 237336)
+++ gcc/match.pd (working copy)
@@ -1305,20 +1305,52 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))))
(negate (maxmin @0 @1)))))
/* MIN (~X, ~Y) -> ~MAX (X, Y)
MAX (~X, ~Y) -> ~MIN (X, Y) */
(for minmax (min max)
maxmin (max min)
(simplify
(minmax (bit_not:s@2 @0) (bit_not:s@3 @1))
(bit_not (maxmin @0 @1))))
+/* MIN (X, Y) == X -> X <= Y */
+(for minmax (min min max max)
+ cmp (eq ne eq ne )
+ out (le gt ge lt )
+ (simplify
+ (cmp:c (minmax:c @0 @1) @0)
+ (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+ (out @0 @1))))
+/* MIN (X, 5) == 0 -> X == 0
+ MIN (X, 5) == 7 -> false */
+(for cmp (eq ne)
+ (simplify
+ (cmp (min @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (wi::lt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
+ { constant_boolean_node (cmp == NE_EXPR, type); }
+ (if (wi::gt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
+ (cmp @0 @2)))))
+(for cmp (eq ne)
+ (simplify
+ (cmp (max @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (wi::gt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
+ { constant_boolean_node (cmp == NE_EXPR, type); }
+ (if (wi::lt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
+ (cmp @0 @2)))))
+/* MIN (X, C1) < C2 -> X < C2 || C1 < C2 */
+(for minmax (min min max max min min max max )
+ cmp (lt le gt ge gt ge lt le )
+ comb (bit_ior bit_ior bit_ior bit_ior bit_and bit_and bit_and bit_and)
+ (simplify
+ (cmp (minmax @0 INTEGER_CST@1) INTEGER_CST@2)
+ (comb (cmp @0 @2) (cmp @1 @2))))
+
/* Simplifications of shift and rotates. */
(for rotate (lrotate rrotate)
(simplify
(rotate integer_all_onesp@0 @1)
@0))
/* Optimize -1 >> x for arithmetic right shifts. */
(simplify
(rshift integer_all_onesp@0 @1)
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: Move optimize_minmax_comparison to match.pd
2016-06-12 8:30 Move optimize_minmax_comparison to match.pd Marc Glisse
@ 2016-06-13 10:16 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2016-06-13 10:16 UTC (permalink / raw)
To: Marc Glisse; +Cc: GCC Patches
On Sun, Jun 12, 2016 at 10:30 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> this move is pretty straightforward. The transformation would probably work
> just fine for any type (floats, vectors), but I didn't want the headache of
> checking the behavior for NaN.
>
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
Ok.
Thanks,
Richard.
> 2016-06-13 Marc Glisse <marc.glisse@inria.fr>
>
> * fold-const.c (optimize_minmax_comparison): Remove.
> (fold_comparison): Remove call to the above.
> * match.pd (MIN (X, Y) == X, MIN (X, 5) == 0, MIN (X, C1) < C2):
> New transformations.
>
> --
> Marc Glisse
> Index: gcc/fold-const.c
> ===================================================================
> --- gcc/fold-const.c (revision 237336)
> +++ gcc/fold-const.c (working copy)
> @@ -121,22 +121,20 @@ static tree eval_subst (location_t, tree
> static tree optimize_bit_field_compare (location_t, enum tree_code,
> tree, tree, tree);
> static int simple_operand_p (const_tree);
> static bool simple_operand_p_2 (tree);
> static tree range_binop (enum tree_code, tree, tree, int, tree, int);
> static tree range_predecessor (tree);
> static tree range_successor (tree);
> static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
> static tree fold_cond_expr_with_comparison (location_t, tree, tree, tree,
> tree);
> static tree unextend (tree, int, int, tree);
> -static tree optimize_minmax_comparison (location_t, enum tree_code,
> - tree, tree, tree);
> static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
> static tree extract_muldiv_1 (tree, tree, enum tree_code, tree, bool *);
> static tree fold_binary_op_with_conditional_arg (location_t,
> enum tree_code, tree,
> tree, tree,
> tree, tree, int);
> static tree fold_div_compare (location_t, enum tree_code, tree, tree,
> tree);
> static bool reorder_operands_p (const_tree, const_tree);
> static tree fold_negate_const (tree, tree);
> static tree fold_not_const (const_tree, tree);
> @@ -5972,124 +5970,20 @@ fold_truth_andor_1 (location_t loc, enum
> ll_unsignedp || rl_unsignedp, ll_reversep);
>
> ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask);
> if (! all_ones_mask_p (ll_mask, lnbitsize))
> result = build2_loc (loc, BIT_AND_EXPR, lntype, result, ll_mask);
>
> return build2_loc (loc, wanted_code, truth_type, result,
> const_binop (BIT_IOR_EXPR, l_const, r_const));
> }
>
> -/* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
> - constant. */
> -
> -static tree
> -optimize_minmax_comparison (location_t loc, enum tree_code code, tree type,
> - tree op0, tree op1)
> -{
> - tree arg0 = op0;
> - enum tree_code op_code;
> - tree comp_const;
> - tree minmax_const;
> - int consts_equal, consts_lt;
> - tree inner;
> -
> - STRIP_SIGN_NOPS (arg0);
> -
> - op_code = TREE_CODE (arg0);
> - minmax_const = TREE_OPERAND (arg0, 1);
> - comp_const = fold_convert_loc (loc, TREE_TYPE (arg0), op1);
> - consts_equal = tree_int_cst_equal (minmax_const, comp_const);
> - consts_lt = tree_int_cst_lt (minmax_const, comp_const);
> - inner = TREE_OPERAND (arg0, 0);
> -
> - /* If something does not permit us to optimize, return the original tree.
> */
> - if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
> - || TREE_CODE (comp_const) != INTEGER_CST
> - || TREE_OVERFLOW (comp_const)
> - || TREE_CODE (minmax_const) != INTEGER_CST
> - || TREE_OVERFLOW (minmax_const))
> - return NULL_TREE;
> -
> - /* Now handle all the various comparison codes. We only handle EQ_EXPR
> - and GT_EXPR, doing the rest with recursive calls using logical
> - simplifications. */
> - switch (code)
> - {
> - case NE_EXPR: case LT_EXPR: case LE_EXPR:
> - {
> - tree tem
> - = optimize_minmax_comparison (loc,
> - invert_tree_comparison (code,
> false),
> - type, op0, op1);
> - if (tem)
> - return invert_truthvalue_loc (loc, tem);
> - return NULL_TREE;
> - }
> -
> - case GE_EXPR:
> - return
> - fold_build2_loc (loc, TRUTH_ORIF_EXPR, type,
> - optimize_minmax_comparison
> - (loc, EQ_EXPR, type, arg0, comp_const),
> - optimize_minmax_comparison
> - (loc, GT_EXPR, type, arg0, comp_const));
> -
> - case EQ_EXPR:
> - if (op_code == MAX_EXPR && consts_equal)
> - /* MAX (X, 0) == 0 -> X <= 0 */
> - return fold_build2_loc (loc, LE_EXPR, type, inner, comp_const);
> -
> - else if (op_code == MAX_EXPR && consts_lt)
> - /* MAX (X, 0) == 5 -> X == 5 */
> - return fold_build2_loc (loc, EQ_EXPR, type, inner, comp_const);
> -
> - else if (op_code == MAX_EXPR)
> - /* MAX (X, 0) == -1 -> false */
> - return omit_one_operand_loc (loc, type, integer_zero_node, inner);
> -
> - else if (consts_equal)
> - /* MIN (X, 0) == 0 -> X >= 0 */
> - return fold_build2_loc (loc, GE_EXPR, type, inner, comp_const);
> -
> - else if (consts_lt)
> - /* MIN (X, 0) == 5 -> false */
> - return omit_one_operand_loc (loc, type, integer_zero_node, inner);
> -
> - else
> - /* MIN (X, 0) == -1 -> X == -1 */
> - return fold_build2_loc (loc, EQ_EXPR, type, inner, comp_const);
> -
> - case GT_EXPR:
> - if (op_code == MAX_EXPR && (consts_equal || consts_lt))
> - /* MAX (X, 0) > 0 -> X > 0
> - MAX (X, 0) > 5 -> X > 5 */
> - return fold_build2_loc (loc, GT_EXPR, type, inner, comp_const);
> -
> - else if (op_code == MAX_EXPR)
> - /* MAX (X, 0) > -1 -> true */
> - return omit_one_operand_loc (loc, type, integer_one_node, inner);
> -
> - else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
> - /* MIN (X, 0) > 0 -> false
> - MIN (X, 0) > 5 -> false */
> - return omit_one_operand_loc (loc, type, integer_zero_node, inner);
> -
> - else
> - /* MIN (X, 0) > -1 -> X > -1 */
> - return fold_build2_loc (loc, GT_EXPR, type, inner, comp_const);
> -
> - default:
> - return NULL_TREE;
> - }
> -}
> -
> /* T is an integer expression that is being multiplied, divided, or taken a
> modulus (CODE says which and what kind of divide or modulus) by a
> constant C. See if we can eliminate that operation by folding it with
> other operations already in T. WIDE_TYPE, if non-null, is a type that
> should be used for the computation if wider than our type.
>
> For example, if we are dividing (X * 8) + (Y * 16) by 4, we can return
> (X * 2) + (Y * 4). We must, however, be assured that either the
> original
> expression would not overflow or that overflow is undefined for the type
> in the language in question.
> @@ -8712,32 +8606,20 @@ fold_comparison (location_t loc, enum tr
> TREE_TYPE (arg0),
> variable1, cst),
> variable2);
> }
> }
>
> tem = maybe_canonicalize_comparison (loc, code, type, arg0, arg1);
> if (tem)
> return tem;
>
> - /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
> - constant, we can simplify it. */
> - if (TREE_CODE (arg1) == INTEGER_CST
> - && (TREE_CODE (arg0) == MIN_EXPR
> - || TREE_CODE (arg0) == MAX_EXPR)
> - && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
> - {
> - tem = optimize_minmax_comparison (loc, code, type, op0, op1);
> - if (tem)
> - return tem;
> - }
> -
> /* If we are comparing an expression that just has comparisons
> of two integer values, arithmetic expressions of those comparisons,
> and constants, we can simplify it. There are only three cases
> to check: the two values can either be equal, the first can be
> greater, or the second can be greater. Fold the expression for
> those three values. Since each value must be 0 or 1, we have
> eight possibilities, each of which corresponds to the constant 0
> or 1 or one of the six possible comparisons.
>
> This handles common cases like (a > b) == 0 but also handles
> Index: gcc/match.pd
> ===================================================================
> --- gcc/match.pd (revision 237336)
> +++ gcc/match.pd (working copy)
> @@ -1305,20 +1305,52 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))))
> (negate (maxmin @0 @1)))))
> /* MIN (~X, ~Y) -> ~MAX (X, Y)
> MAX (~X, ~Y) -> ~MIN (X, Y) */
> (for minmax (min max)
> maxmin (max min)
> (simplify
> (minmax (bit_not:s@2 @0) (bit_not:s@3 @1))
> (bit_not (maxmin @0 @1))))
>
> +/* MIN (X, Y) == X -> X <= Y */
> +(for minmax (min min max max)
> + cmp (eq ne eq ne )
> + out (le gt ge lt )
> + (simplify
> + (cmp:c (minmax:c @0 @1) @0)
> + (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0)))
> + (out @0 @1))))
> +/* MIN (X, 5) == 0 -> X == 0
> + MIN (X, 5) == 7 -> false */
> +(for cmp (eq ne)
> + (simplify
> + (cmp (min @0 INTEGER_CST@1) INTEGER_CST@2)
> + (if (wi::lt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
> + { constant_boolean_node (cmp == NE_EXPR, type); }
> + (if (wi::gt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
> + (cmp @0 @2)))))
> +(for cmp (eq ne)
> + (simplify
> + (cmp (max @0 INTEGER_CST@1) INTEGER_CST@2)
> + (if (wi::gt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
> + { constant_boolean_node (cmp == NE_EXPR, type); }
> + (if (wi::lt_p (@1, @2, TYPE_SIGN (TREE_TYPE (@0))))
> + (cmp @0 @2)))))
> +/* MIN (X, C1) < C2 -> X < C2 || C1 < C2 */
> +(for minmax (min min max max min min max max
> )
> + cmp (lt le gt ge gt ge lt le
> )
> + comb (bit_ior bit_ior bit_ior bit_ior bit_and bit_and bit_and
> bit_and)
> + (simplify
> + (cmp (minmax @0 INTEGER_CST@1) INTEGER_CST@2)
> + (comb (cmp @0 @2) (cmp @1 @2))))
> +
> /* Simplifications of shift and rotates. */
>
> (for rotate (lrotate rrotate)
> (simplify
> (rotate integer_all_onesp@0 @1)
> @0))
>
> /* Optimize -1 >> x for arithmetic right shifts. */
> (simplify
> (rshift integer_all_onesp@0 @1)
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2016-06-13 10:16 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-06-12 8:30 Move optimize_minmax_comparison to match.pd Marc Glisse
2016-06-13 10:16 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).