Re: [optimize3/3] VRP min/max exprs
On Tue, 11 Aug 2015, Nathan Sidwell wrote: > On 08/11/15 07:41, Richard Biener wrote: > > > The patch looks good. Note that with SSA name operands it can be > > still profitable to do compare_range_with_value, esp. if the other > > operand has a symbolical range. See > > vrp_evaluate_conditional_warnv_with_ops_using_ranges which actually > > implements a nice helper for evaluating comparisons for code-gen > > transforms. > > Ok, like this? Thanks for your help! > > tested on x86_64-linux. Ok. Thanks, Richard.
Re: [optimize3/3] VRP min/max exprs
On 08/11/15 07:41, Richard Biener wrote: The patch looks good. Note that with SSA name operands it can be still profitable to do compare_range_with_value, esp. if the other operand has a symbolical range. See vrp_evaluate_conditional_warnv_with_ops_using_ranges which actually implements a nice helper for evaluating comparisons for code-gen transforms. Ok, like this? Thanks for your help! tested on x86_64-linux. nathan 2015-08-10 Nathan Sidwell * tree-vrp.c (simplify_min_or_max_using_ranges): New. (simplify_stmt_using_ranges): Simplify MIN and MAX exprs. testsuite/ * gcc.dg/vrp-min-max-1.c: New. * gcc.dg/vrp-min-max-2.c: New. Index: tree-vrp.c === --- tree-vrp.c (revision 226779) +++ tree-vrp.c (working copy) @@ -7466,7 +7466,8 @@ compare_names (enum tree_code comp, tree return NULL_TREE; } -/* Helper function for vrp_evaluate_conditional_warnv. */ +/* Helper function for vrp_evaluate_conditional_warnv & other + optimizers. */ static tree vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code, @@ -9145,6 +9146,54 @@ simplify_div_or_mod_using_ranges (gimple return false; } +/* Simplify a min or max if the ranges of the two operands are + disjoint. Return true if we do simplify. */ + +static bool +simplify_min_or_max_using_ranges (gimple stmt) +{ + tree op0 = gimple_assign_rhs1 (stmt); + tree op1 = gimple_assign_rhs2 (stmt); + bool sop = false; + tree val; + + val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges + (LE_EXPR, op0, op1, &sop)); + if (!val) +{ + sop = false; + val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges + (LT_EXPR, op0, op1, &sop)); +} + + if (val) +{ + if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) + { + location_t location; + + if (!gimple_has_location (stmt)) + location = input_location; + else + location = gimple_location (stmt); + warning_at (location, OPT_Wstrict_overflow, + "assuming signed overflow does not occur when " + "simplifying % to % or %"); + } + + /* VAL == TRUE -> OP0 < or <= op1 + VAL == FALSE -> OP0 > or >= op1. */ + tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR) + == integer_zerop (val)) ? op0 : op1; + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_from_tree (&gsi, res); + update_stmt (stmt); + return true; +} + + return false; +} + /* If the operand to an ABS_EXPR is >= 0, then eliminate the ABS_EXPR. If the operand is <= 0, then simplify the ABS_EXPR into a NEGATE_EXPR. */ @@ -9987,6 +10036,11 @@ simplify_stmt_using_ranges (gimple_stmt_ return simplify_float_conversion_using_ranges (gsi, stmt); break; + case MIN_EXPR: + case MAX_EXPR: + return simplify_min_or_max_using_ranges (stmt); + break; + default: break; } Index: testsuite/gcc.dg/vrp-min-max-1.c === --- testsuite/gcc.dg/vrp-min-max-1.c (revision 0) +++ testsuite/gcc.dg/vrp-min-max-1.c (working copy) @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-mergephi2" } */ + +int bar (void); + +int foo1 (int x, int y) +{ + if (y < 10) return bar (); + if (x > 9) return bar (); + + return x < y ? x : y; +} + +int foo2 (int x, int y) +{ + if (y < 10) return bar (); + if (x > 9) return bar (); + + return x > y ? x : y; +} + +/* We expect to optimiz min/max in VRP*/ + +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "mergephi2" } } */ +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "mergephi2" } } */ +/* { dg-final { scan-tree-dump-not "MIN_EXPR" "vrp1" } } */ +/* { dg-final { scan-tree-dump-not "MAX_EXPR" "vrp1" } } */ Index: testsuite/gcc.dg/vrp-min-max-2.c === --- testsuite/gcc.dg/vrp-min-max-2.c (revision 0) +++ testsuite/gcc.dg/vrp-min-max-2.c (working copy) @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp2" } */ + +int Foo (int X) +{ + if (X < 0) +X = 0; + if (X > 191) +X = 191; + + return X << 23; +} + +/* We expect this min/max pair to survive. */ + +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "vrp2" } } */ +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "vrp2" } } */
Re: [optimize3/3] VRP min/max exprs
On Mon, 10 Aug 2015, Nathan Sidwell wrote: > Richard. > this is the patch for the min/max optimization I was trying to implement > before getting sidetracked with the phi bug and cleaning the vrp abs > optimization. > > This patch checks both min and max where both operands have a determined > range, and the case where the second op is a constant. When we determine the > operand values are disjoint (modulo a possible single overlapping value) we > replace the min or max with the appropriate operand. > > booted and tested with the other two patches I just posted. > > ok? The patch looks good. Note that with SSA name operands it can be still profitable to do compare_range_with_value, esp. if the other operand has a symbolical range. See vrp_evaluate_conditional_warnv_with_ops_using_ranges which actually implements a nice helper for evaluating comparisons for code-gen transforms. So I'd prefer that you'd simply call that instead of deciding for yourself on SSA name vs. non-SSA name. Thanks, Richard.
[optimize3/3] VRP min/max exprs
Richard. this is the patch for the min/max optimization I was trying to implement before getting sidetracked with the phi bug and cleaning the vrp abs optimization. This patch checks both min and max where both operands have a determined range, and the case where the second op is a constant. When we determine the operand values are disjoint (modulo a possible single overlapping value) we replace the min or max with the appropriate operand. booted and tested with the other two patches I just posted. ok? nathan 2015-08-10 Nathan Sidwell * tree-vrp.c (simplify_min_or_max_using_ranges): New. (simplify_stmt_using_ranges): Simplify MIN and MAX exprs. testsuite/ * gcc.dg/vrp-min-max-1.c: New. * gcc.dg/vrp-min-max-2.c: New. Index: tree-vrp.c === --- tree-vrp.c (revision 226749) +++ tree-vrp.c (working copy) @@ -9145,6 +9145,69 @@ simplify_div_or_mod_using_ranges (gimple return false; } +/* Simplify a min or max if the ranges of the two operands are + disjoint. Return true if we do simplify. */ + +static bool +simplify_min_or_max_using_ranges (gimple stmt) +{ + tree op0 = gimple_assign_rhs1 (stmt); + tree op1 = gimple_assign_rhs2 (stmt); + bool sop = false; + tree val; + value_range_t *vr0 = get_value_range (op0); + + if (TREE_CODE (op1) == SSA_NAME) +{ + /* SSA_NAME MIN/MAX SSA_NAME. Compare ranges. */ + value_range_t *vr1 = get_value_range (op1); + + val = compare_ranges (LE_EXPR, vr0, vr1, &sop); + if (!val) + { + sop = false; + val = compare_ranges (LT_EXPR, vr0, vr1, &sop); + } +} + else +{ + /* SSA_NAME MIN/MAX CONST. Compare range to value. */ + val = compare_range_with_value (LE_EXPR, vr0, op1, &sop); + if (!val) + { + sop = false; + val = compare_range_with_value (LT_EXPR, vr0, op1, &sop); + } +} + + if (val) +{ + if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) + { + location_t location; + + if (!gimple_has_location (stmt)) + location = input_location; + else + location = gimple_location (stmt); + warning_at (location, OPT_Wstrict_overflow, + "assuming signed overflow does not occur when " + "simplifying % to % or %"); + } + + /* VAL == TRUE -> OP0 < or <= op1 + VAL == FALSE -> OP0 > or >= op1. */ + tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR) + == integer_zerop (val)) ? op0 : op1; + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gimple_assign_set_rhs_from_tree (&gsi, res); + update_stmt (stmt); + return true; +} + + return false; +} + /* If the operand to an ABS_EXPR is >= 0, then eliminate the ABS_EXPR. If the operand is <= 0, then simplify the ABS_EXPR into a NEGATE_EXPR. */ @@ -,6 +10050,13 @@ simplify_stmt_using_ranges (gimple_stmt_ return simplify_float_conversion_using_ranges (gsi, stmt); break; + case MIN_EXPR: + case MAX_EXPR: + if (TREE_CODE (rhs1) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) + return simplify_min_or_max_using_ranges (stmt); + break; + default: break; } Index: testsuite/gcc.dg/vrp-min-max-1.c === --- testsuite/gcc.dg/vrp-min-max-1.c (revision 0) +++ testsuite/gcc.dg/vrp-min-max-1.c (working copy) @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-mergephi2" } */ + +int bar (void); + +int foo1 (int x, int y) +{ + if (y < 10) return bar (); + if (x > 9) return bar (); + + return x < y ? x : y; +} + +int foo2 (int x, int y) +{ + if (y < 10) return bar (); + if (x > 9) return bar (); + + return x > y ? x : y; +} + +/* We expect to optimiz min/max in VRP*/ + +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "mergephi2" } } */ +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "mergephi2" } } */ +/* { dg-final { scan-tree-dump-not "MIN_EXPR" "vrp1" } } */ +/* { dg-final { scan-tree-dump-not "MAX_EXPR" "vrp1" } } */ Index: testsuite/gcc.dg/vrp-min-max-2.c === --- testsuite/gcc.dg/vrp-min-max-2.c (revision 0) +++ testsuite/gcc.dg/vrp-min-max-2.c (working copy) @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp2" } */ + +int Foo (int X) +{ + if (X < 0) +X = 0; + if (X > 191) +X = 191; + + return X << 23; +} + +/* We expect this min/max pair to survive. */ + +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "vrp2" } } */ +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "vrp2" } } */