[PATCH] Factor out division by squares and remove division around comparisons (1/2)
Hi all, The patch implements the division opitmizations discussed in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 . The implemented change differs slightly from the proposed one in that we re-associate: C / x comparison 0.0 -> x comparison' 0.0 Where C is any constant and comparison' is changed as appropriate if C is negative. The implementations also removes the division from: x / C comparison 0.0 -> x comparison' 0.0 Where again, comparison' is changed as appropriate if C is negative. We also change the association of x / (y * C) -> (x / C) / y If C is a constant. All of the above require -funsafe-math-optimizations. We also change: x / (- y) -> (-x) / y Which requires -fno-trapping-math. Bootstrapped and regtested (with part 2 of this patch) on aarch64. OK for trunk? (Apologies if the recipients in the 'to' field received this twice, I accidentally sent this from an email gcc-patches doesn't accept) Jackson gcc/ 2017-08-03 Jackson Woodruff PR 71026/tree-optimization * match.pd: New patterns. gcc/testsuite 2017-08-03 Jackson Woodruff PR 71026/tree-optimization * gcc.dg/associate_comparison_1.c: New. * gcc.dg/associate_division_2.c: New.
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
And have now attached that patch. Jackson On 08/10/2017 03:09 PM, Jackson Woodruff wrote: Hi all, The patch implements the division opitmizations discussed in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 . The implemented change differs slightly from the proposed one in that we re-associate: C / x comparison 0.0 -> x comparison' 0.0 Where C is any constant and comparison' is changed as appropriate if C is negative. The implementations also removes the division from: x / C comparison 0.0 -> x comparison' 0.0 Where again, comparison' is changed as appropriate if C is negative. We also change the association of x / (y * C) -> (x / C) / y If C is a constant. All of the above require -funsafe-math-optimizations. We also change: x / (- y) -> (-x) / y Which requires -fno-trapping-math. Bootstrapped and regtested (with part 2 of this patch) on aarch64. OK for trunk? (Apologies if the recipients in the 'to' field received this twice, I accidentally sent this from an email gcc-patches doesn't accept) Jackson gcc/ 2017-08-03 Jackson Woodruff PR 71026/tree-optimization * match.pd: New patterns. gcc/testsuite 2017-08-03 Jackson Woodruff PR 71026/tree-optimization * gcc.dg/associate_comparison_1.c: New. * gcc.dg/associate_division_2.c: New. diff --git a/gcc/match.pd b/gcc/match.pd index e98db52af84946cf579c6434e06d450713a47162..7abfd11601a956ecb59c945256c9f30dc0b6f6c9 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -342,16 +342,42 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (negate @0))) (if (flag_reciprocal_math) - /* Convert (A/B)/C to A/(B*C) */ + /* Convert (A/B)/C to A/(B*C) where B is not a constant. */ (simplify (rdiv (rdiv:s @0 @1) @2) - (rdiv @0 (mult @1 @2))) + (if (TREE_CODE (@1) != REAL_CST) +(rdiv @0 (mult @1 @2 + + /* Simplify x / (C * y) to (x / C) / y where C is a constant. */ + (simplify + (rdiv @0 + (mult @1 REAL_CST@2)) + (rdiv (rdiv @0 @2) @1)) /* Convert A/(B/C) to (A/B)*C */ (simplify (rdiv @0 (rdiv:s @1 @2)) (mult (rdiv @0 @1) @2))) +(if (!flag_trapping_math) + /* Simplify x / (- y) to -x / y. */ + (simplify +(rdiv @0 (negate @1)) +(rdiv (negate @0) @1))) + +(if (flag_unsafe_math_optimizations) + /* Simplify (C / x op 0.0) to x op 0.0 for C > 0. */ + (for op (lt le gt ge) + neg_op (gt ge lt le) +(simplify + (op (rdiv REAL_CST@0 @1) real_zerop@2) + (switch + (if (!real_equal (TREE_REAL_CST_PTR (@0), &dconst0) + && !REAL_VALUE_NEGATIVE (TREE_REAL_CST (@0))) + (op @1 @2)) + (if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (@0))) + (neg_op @1 @2)) + /* Optimize (X & (-A)) / A where A is a power of 2, to X >> log2(A) */ (for div (trunc_div ceil_div floor_div round_div exact_div) (simplify @@ -3446,6 +3472,21 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (!HONOR_SNANS (type)) @0)) + /* Simplify (x * C1) cmp C2 -> x cmp C2 / C1 +and simplify (x / C1) cmp C2 -> x cmp C2 * C1. */ + (for cmp (lt le gt ge) + neg_cmp (gt ge lt le) + (for op (mult rdiv) + inv_op (rdiv mult) + (simplify + (cmp (op @0 REAL_CST@1) REAL_CST@2) + (switch + (if (!real_equal (TREE_REAL_CST_PTR (@1), &dconst0) +&& !REAL_VALUE_NEGATIVE (TREE_REAL_CST (@1))) +(cmp @0 (inv_op @2 @1))) + (if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (@1))) +(neg_cmp @0 (inv_op @2 @1))) + /* Simplify sqrt(x) * sqrt(y) -> sqrt(x*y). */ (for root (SQRT CBRT) (simplify diff --git a/gcc/testsuite/gcc.dg/associate_comparison_1.c b/gcc/testsuite/gcc.dg/associate_comparison_1.c new file mode 100644 index ..c12e5cfb2a8388068fa1731cc2305f9fe5139fd6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/associate_comparison_1.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-funsafe-math-optimizations -fdump-tree-optimized" } */ + +int +lt_cmp (float x, float y) +{ + return x / 2 <= 0; +} + +int +inv_cmp (float x, float y) +{ + return 5 / x >= 0; +} + + +/* { dg-final { scan-tree-dump-not " / " "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/associate_division_2.c b/gcc/testsuite/gcc.dg/associate_division_2.c new file mode 100644 index ..1f9c1741ce980f1148016e37399134aa8a619b1d --- /dev/null +++ b/gcc/testsuite/gcc.dg/associate_division_2.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-Ofast -fdump-tree-optimized" } */ + +float +neg_mov (float w, float x, float *y, float *z) +{ + *z = x / (- w); + *y = 3 / w; + + return 5 / w; +} + +/* { dg-final { scan-tree-dump-times " / " 1 "optimized" } } */
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Thu, 10 Aug 2017, Jackson Woodruff wrote: > > We also change: > > > > x / (- y) -> (-x) / y > > > > Which requires -fno-trapping-math. I don't see why that requires -fno-trapping-math. The exceptions should be identical from both variants, as should the result, as far as defined by C or IEEE 754 (it's possible it might affect the sign of a NaN result on some architectures, but only where that sign is unspecified in C and IEEE 754 terms, so such a change is OK). -- Joseph S. Myers jos...@codesourcery.com
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Thu, Aug 10, 2017 at 4:09 PM, Jackson Woodruff wrote: > Hi all, > > The patch implements the division opitmizations discussed in > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 . > > The implemented change differs slightly from the > proposed one in that we re-associate: > > C / x comparison 0.0 -> x comparison' 0.0 > > Where C is any constant and comparison' is changed as > appropriate if C is negative. > > The implementations also removes the division from: > > x / C comparison 0.0 -> x comparison' 0.0 > > Where again, comparison' is changed as appropriate if C is > negative. > > We also change the association of > > x / (y * C) -> (x / C) / y > > If C is a constant. Why's that profitable? > All of the above require > -funsafe-math-optimizations. > > We also change: > > x / (- y) -> (-x) / y Why? (it's only one of the possible canonicalizations) Note there are exactly two RDIV_EXPR simplifications remaining in fold_binary_loc, maybe you can move them to match.pd (beware of negate_expr_p ... this negate optimization should eventually move to backprop). > Which requires -fno-trapping-math. > > Bootstrapped and regtested (with part 2 of this patch) on aarch64. > > OK for trunk? > > (Apologies if the recipients in the 'to' field received this twice, > I accidentally sent this from an email gcc-patches doesn't accept) > > Jackson > > gcc/ > > 2017-08-03 Jackson Woodruff > > PR 71026/tree-optimization > * match.pd: New patterns. > > > gcc/testsuite > > 2017-08-03 Jackson Woodruff > > PR 71026/tree-optimization > * gcc.dg/associate_comparison_1.c: New. > * gcc.dg/associate_division_2.c: New. >
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
Richard Biener wrote: > > We also change the association of > > > > x / (y * C) -> (x / C) / y > > > > If C is a constant. > > Why's that profitable? It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. Also 1/y is now available to the reciprocal optimization, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. > > x / (- y) -> (-x) / y > > Why? (it's only one of the possible canonicalizations) Same here, y is now available for reciprocal optimization. The negate may now be optimized, for example (a * b) / -y -> (-a*b) / y will use a negated multiple on various targets. Wilco
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra wrote: > Richard Biener wrote: >> > We also change the association of >> > >> > x / (y * C) -> (x / C) / y >> > >> > If C is a constant. >> >> Why's that profitable? > > It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. > Also 1/y is now available to the reciprocal optimization, see > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. Sure, but on its own it's going to be slower. So this isn't the correct way to enable those followup transforms. >> > x / (- y) -> (-x) / y >> >> Why? (it's only one of the possible canonicalizations) > > Same here, y is now available for reciprocal optimization. The > negate may now be optimized, for example (a * b) / -y -> (-a*b) / y > will use a negated multiple on various targets. Fair enough. Though if it were x / -(a*b) you'd regress that case. Richard. > > Wilco
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
Richard Biener wrote: > On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra > wrote: > > Richard Biener wrote: >>> > We also change the association of >>> > >>> > x / (y * C) -> (x / C) / y >>> > >>> > If C is a constant. >>> >>> Why's that profitable? >> >> It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. >> Also 1/y is now available to the reciprocal optimization, see >> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. > > Sure, but on its own it's going to be slower. So this isn't the > correct way to enable those followup transforms. How can it be any slower? It's one division and one multiply in both cases. >>> > x / (- y) -> (-x) / y >>> >>> Why? (it's only one of the possible canonicalizations) >> >> Same here, y is now available for reciprocal optimization. The >> negate may now be optimized, for example (a * b) / -y -> (-a*b) / y >> will use a negated multiple on various targets. > > Fair enough. Though if it were x / -(a*b) you'd regress that case. Possibly. You might still be able to merge the negate if the result is used in an addition or multiply, which wouldn't be possible if it were hiding in a subexpression. Without global analysis it seems best to move constants/negates to the toplevel if they can't be trivially removed in a subexpression. Eg. -x / (a * b * -c). Wilco
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Thu, Aug 17, 2017 at 11:55 AM, Wilco Dijkstra wrote: > Richard Biener wrote: >> On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra >> wrote: >> > Richard Biener wrote: > We also change the association of > > x / (y * C) -> (x / C) / y > > If C is a constant. Why's that profitable? >>> >>> It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. >>> Also 1/y is now available to the reciprocal optimization, see >>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. >> >> Sure, but on its own it's going to be slower. So this isn't the >> correct way to enable those followup transforms. > > How can it be any slower? It's one division and one multiply in both cases. (x / C) / y is two divisions. If you restrict it to the case where we can transform this to (x * C') / y then it's indeed one. > x / (- y) -> (-x) / y Why? (it's only one of the possible canonicalizations) >>> >>> Same here, y is now available for reciprocal optimization. The >>> negate may now be optimized, for example (a * b) / -y -> (-a*b) / y >>> will use a negated multiple on various targets. >> >> Fair enough. Though if it were x / -(a*b) you'd regress that case. > > Possibly. You might still be able to merge the negate if the result is used > in an > addition or multiply, which wouldn't be possible if it were hiding in a > subexpression. > Without global analysis it seems best to move constants/negates to the > toplevel > if they can't be trivially removed in a subexpression. Eg. -x / (a * b * -c). Sure. So both patterns are canonicalization which is fine for match.pd. Those followup transforms should be done at a place that can look at more complicated patterns. We have the reassoc pass, then backprop (not exactly matching), and the recip pattern matching / cse pass. Richard. > Wilco
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Thu, 17 Aug 2017, Richard Biener wrote: > > Without global analysis it seems best to move constants/negates to the > > toplevel if they can't be trivially removed in a subexpression. Eg. -x > > / (a * b * -c). > > Sure. So both patterns are canonicalization which is fine for match.pd. > Those followup transforms should be done at a place that can look at > more complicated patterns. We have the reassoc pass, then backprop (not > exactly matching), and the recip pattern matching / cse pass. Watch out for -frounding-math issues, though. -a * b is always the same as a * -b, but not the same as -(a * b) with -frounding-math, and similarly, -frounding-math should prevent eliminating the negations from the -x / (a * b * -c) expression (whereas elimination from -x / -(a * b * c) would be fine). -- Joseph S. Myers jos...@codesourcery.com
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 08/17/2017 03:55 AM, Wilco Dijkstra wrote: > Richard Biener wrote: >> On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra >> wrote: >>> Richard Biener wrote: > We also change the association of > > x / (y * C) -> (x / C) / y > > If C is a constant. Why's that profitable? >>> >>> It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. >>> Also 1/y is now available to the reciprocal optimization, see >>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. >> >> Sure, but on its own it's going to be slower. So this isn't the >> correct way to enable those followup transforms. > > How can it be any slower? It's one division and one multiply in both cases. x / (y * C) -> (x / C) / y Goes from one division and one multiplication to two divisions. I'm guessing that's what Richi is (reasonably) concerned about. So it may be the case that we need more complex pattern matching here for when to perform the first transformation to ultimately enable the second. Jeff
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
Hi all, Apologies again to those CC'ed, who (again) received this twice. Joseph: Yes you are correct. I misread the original thread, now fixed. Richard: I've moved the optimizations out of fold-const.c. One has been replicated in match.pd, and the other (x / C +- y / C -> (x +- y) / C) I've deleted as it only introduced a new optimization when running with the flags '-O0 -funsafe-math-optimizations'. On O1 and up, the pattern that replaces 'x / C' with 'x * (1 / C)' is enabled and then the pattern is covered by that and (x * C +- y * C -> C * (x +- y)) (which is already present in match.pd) I have also updated the testcase for those optimizations to use 'O1' to avoid that case. On 08/24/2017 10:06 PM, Jeff Law wrote: On 08/17/2017 03:55 AM, Wilco Dijkstra wrote: Richard Biener wrote: On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra wrote: Richard Biener wrote: We also change the association of x / (y * C) -> (x / C) / y If C is a constant. Why's that profitable? It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. Also 1/y is now available to the reciprocal optimization, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. Sure, but on its own it's going to be slower. So this isn't the correct way to enable those followup transforms. How can it be any slower? It's one division and one multiply in both cases. x / (y * C) -> (x / C) / y Goes from one division and one multiplication to two divisions. I'm guessing that's what Richi is (reasonably) concerned about. So it may be the case that we need more complex pattern matching here for when to perform the first transformation to ultimately enable the second. The only case where we don't remove the division but still execute this pattern is when run with'-O0 -freciprocal-math'. As long as we have 'O1' or greater (and -freciprocal-math), that is enough to enable the removal of the reciprocal. Jackson. Jeff diff --git a/gcc/fold-const.c b/gcc/fold-const.c index eeeff1ed166734328a612142fdf6235274f9e858..907d96c3d994db1ec8dc0ef692ac0b4d59c99a4c 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -3834,47 +3834,6 @@ invert_truthvalue_loc (location_t loc, tree arg) : TRUTH_NOT_EXPR, type, arg); } - -/* Knowing that ARG0 and ARG1 are both RDIV_EXPRs, simplify a binary operation - with code CODE. This optimization is unsafe. */ -static tree -distribute_real_division (location_t loc, enum tree_code code, tree type, - tree arg0, tree arg1) -{ - bool mul0 = TREE_CODE (arg0) == MULT_EXPR; - bool mul1 = TREE_CODE (arg1) == MULT_EXPR; - - /* (A / C) +- (B / C) -> (A +- B) / C. */ - if (mul0 == mul1 - && operand_equal_p (TREE_OPERAND (arg0, 1), - TREE_OPERAND (arg1, 1), 0)) -return fold_build2_loc (loc, mul0 ? MULT_EXPR : RDIV_EXPR, type, - fold_build2_loc (loc, code, type, -TREE_OPERAND (arg0, 0), -TREE_OPERAND (arg1, 0)), - TREE_OPERAND (arg0, 1)); - - /* (A / C1) +- (A / C2) -> A * (1 / C1 +- 1 / C2). */ - if (operand_equal_p (TREE_OPERAND (arg0, 0), - TREE_OPERAND (arg1, 0), 0) - && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST - && TREE_CODE (TREE_OPERAND (arg1, 1)) == REAL_CST) -{ - REAL_VALUE_TYPE r0, r1; - r0 = TREE_REAL_CST (TREE_OPERAND (arg0, 1)); - r1 = TREE_REAL_CST (TREE_OPERAND (arg1, 1)); - if (!mul0) - real_arithmetic (&r0, RDIV_EXPR, &dconst1, &r0); - if (!mul1) -real_arithmetic (&r1, RDIV_EXPR, &dconst1, &r1); - real_arithmetic (&r0, code, &r0, &r1); - return fold_build2_loc (loc, MULT_EXPR, type, - TREE_OPERAND (arg0, 0), - build_real (type, r0)); -} - - return NULL_TREE; -} /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER starting at BITPOS. The field is unsigned if UNSIGNEDP is nonzero @@ -9419,12 +9378,6 @@ fold_binary_loc (location_t loc, } } - if (flag_unsafe_math_optimizations - && (TREE_CODE (arg0) == RDIV_EXPR || TREE_CODE (arg0) == MULT_EXPR) - && (TREE_CODE (arg1) == RDIV_EXPR || TREE_CODE (arg1) == MULT_EXPR) - && (tem = distribute_real_division (loc, code, type, arg0, arg1))) - return tem; - /* Convert a + (b*c + d*e) into (a + b*c) + d*e. We associate floats only if the user has specified -fassociative-math. */ @@ -9772,13 +9725,6 @@ fold_binary_loc (location_t loc, return tem; } - if (FLOAT_TYPE_P (type) - && flag_unsafe_math_optimizations - && (TREE_CODE (arg0) == RDIV_EXPR || TREE_CODE (arg0) == MULT_EXPR) - && (TREE_CODE (arg1) == RDIV_EXPR || TREE_CODE (arg1) == MULT_EXPR) -
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Tue, Aug 29, 2017 at 1:35 PM, Jackson Woodruff wrote: > Hi all, > > Apologies again to those CC'ed, who (again) received this twice. > > Joseph: Yes you are correct. I misread the original thread, now fixed. > > Richard: I've moved the optimizations out of fold-const.c. One has been > replicated in match.pd, and the other (x / C +- y / C -> (x +- y) / C) I've > deleted as it only introduced a new optimization when running with the flags > '-O0 -funsafe-math-optimizations'. Hmm, how did you verify that, that it only adds sth with -O0 -funsafe-math-optimizations? Is that because in GIMPLE the reassoc pass should do this transform? You added +/* Simplify x / (- y) to -x / y. */ +(simplify + (rdiv @0 (negate @1)) + (rdiv (negate @0) @1)) for /* (-A) / (-B) -> A / B */ if (TREE_CODE (arg0) == NEGATE_EXPR && negate_expr_p (arg1)) return fold_build2_loc (loc, RDIV_EXPR, type, TREE_OPERAND (arg0, 0), negate_expr (arg1)); if (TREE_CODE (arg1) == NEGATE_EXPR && negate_expr_p (arg0)) return fold_build2_loc (loc, RDIV_EXPR, type, negate_expr (arg0), TREE_OPERAND (arg1, 0)); presumably? This isn't equivalent. It's more like (simplify (rdiv (negate_expr_p @0) (negate @1)) (rdiv (negate @0) @1)) (simplify (rdiv (negate @0) (negate_expr_p @1)) (rdiv @0 (negate @1))) and you should remove the corresponding fold-const.c code. Please do these changes independently to aid bisecting in case of issues. (if (flag_reciprocal_math) - /* Convert (A/B)/C to A/(B*C) */ + /* Convert (A/B)/C to A/(B*C) where neither B nor C are constant. */ (simplify (rdiv (rdiv:s @0 @1) @2) - (rdiv @0 (mult @1 @2))) + (if (TREE_CODE (@1) != REAL_CST && TREE_CODE (@1) != REAL_CST) +(rdiv @0 (mult @1 @2 why? I guess to avoid ping-poning with + /* Simplify x / (C * y) to (x / C) / y where C is a constant. */ + (simplify + (rdiv @0 + (mult @1 REAL_CST@2)) + (rdiv (rdiv @0 @2) @1)) ? If so why not just disallow for @1 == REAL_CST? > On O1 and up, the pattern that replaces 'x / C' with 'x * (1 / C)' > is enabled and then the pattern is covered by that and > (x * C +- y * C -> C * (x +- y)) (which is already present in match.pd) > > I have also updated the testcase for those optimizations to use 'O1' to > avoid that case. > > > On 08/24/2017 10:06 PM, Jeff Law wrote: >> >> On 08/17/2017 03:55 AM, Wilco Dijkstra wrote: >>> >>> Richard Biener wrote: On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra wrote: > > Richard Biener wrote: >>> >>> We also change the association of >>> >>>x / (y * C) -> (x / C) / y >>> >>> If C is a constant. >> >> >> Why's that profitable? > > > It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. > Also 1/y is now available to the reciprocal optimization, see > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 for details. Sure, but on its own it's going to be slower. So this isn't the correct way to enable those followup transforms. >>> >>> >>> How can it be any slower? It's one division and one multiply in both >>> cases. >> >> x / (y * C) -> (x / C) / y >> >> Goes from one division and one multiplication to two divisions. I'm >> guessing that's what Richi is (reasonably) concerned about. >> >> So it may be the case that we need more complex pattern matching here >> for when to perform the first transformation to ultimately enable the >> second. >> > > The only case where we don't remove the division but still execute this > pattern is when run with'-O0 -freciprocal-math'. > > As long as we have 'O1' or greater (and -freciprocal-math), that is enough > to enable the removal of the reciprocal. I don't see this. I presume you mean this happens in the recip pass? But we don't optimize this when optimizing for size (but the above pattern still applies) or when targetm.min_divisions_for_recip_mul is too large. So I still think this is the wrong place to do this and instead the recip pass should be extended. > > Jackson. > >> >> Jeff >> >
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 08/29/2017 01:13 PM, Richard Biener wrote: On Tue, Aug 29, 2017 at 1:35 PM, Jackson Woodruff wrote: Hi all, Apologies again to those CC'ed, who (again) received this twice. Joseph: Yes you are correct. I misread the original thread, now fixed. Richard: I've moved the optimizations out of fold-const.c. One has been replicated in match.pd, and the other (x / C +- y / C -> (x +- y) / C) I've deleted as it only introduced a new optimization when running with the flags '-O0 -funsafe-math-optimizations'. Hmm, how did you verify that, that it only adds sth with -O0 -funsafe-math-optimizations? By checking with various flags, although not exhaustively. I looked for reasons for the behavior in match.pd (explained below). I have also since discovered that the combinations of '-funsafe-math-optimizations -frounding-math' (at all levels) and '-fno-recriprocal-math -funsafe-math-optimizations' mean this pattern adds something. Is that because in GIMPLE the reassoc pass should do this transform? It's because the pattern that changes (X / C) -> X * (1 / C) is gated with O1: (for cst (REAL_CST COMPLEX_CST VECTOR_CST) (simplify (rdiv @0 cst@1) ->(if (optimize) -> (if (flag_reciprocal_math && !real_zerop (@1)) (with { tree tem = const_binop (RDIV_EXPR, type, build_one_cst (type), @1); } (if (tem) (mult @0 { tem; } ))) (if (cst != COMPLEX_CST) (with { tree inverse = exact_inverse (type, @1); } (if (inverse) (mult @0 { inverse; } I've flagged the two lines that are particularly relevant to this. Removing this pattern, as I would expect, means that the divisions in the above optimization (and the one further down) are not removed. So then there is the question of edge cases. This pattern is (ignoring the second case) going to fail when const_binop returns null. Looking through that function says that it will fail (for reals) when: - Either argument is null (not the case) - The operation is not in the list (PLUS_EXPR, MINUS_EXPR, MULT_EXPR, RDIV_EXPR, MIN_EXPR, MAX_EXPR) (again not the case) - We honor Signalling NaNs and one of the operands is a sNaN. - The operation is a division, and the second argument is zero and dividing by 0.0 raises an exception. - The result is infinity and neither of the operands were infinity and flag_trapping_math is set. - The result isn't exact and flag_rounding_math is set. For (x / ( y * C) -> (x / C) / y), I will add some gating for each of these so that the pattern is never executed if one of these would be the case. The additional cases where this isn't converted to a multiplication by the reciprocal appear to be when -freciprocal-math is used, but we don't have -fno-rounding-math, or funsafe-math-optimizations. For the removal of (x / C +- y / C -> (x +- y) / C), there is a trade-off of whether it is worth having an extra pattern for these edge cases. On this I'm not sure. You added +/* Simplify x / (- y) to -x / y. */ +(simplify + (rdiv @0 (negate @1)) + (rdiv (negate @0) @1)) Sorry, this was unclear, the changes to fold const should be split up from the additions to match.pd. This was one of the changes discussed before. The idea is to canonicalize this so that y can be extracted in the cse_reciprocals pass. for /* (-A) / (-B) -> A / B */ if (TREE_CODE (arg0) == NEGATE_EXPR && negate_expr_p (arg1)) return fold_build2_loc (loc, RDIV_EXPR, type, TREE_OPERAND (arg0, 0), negate_expr (arg1)); if (TREE_CODE (arg1) == NEGATE_EXPR && negate_expr_p (arg0)) return fold_build2_loc (loc, RDIV_EXPR, type, negate_expr (arg0), TREE_OPERAND (arg1, 0)); presumably? This isn't equivalent. It's more like (simplify (rdiv (negate_expr_p @0) (negate @1)) (rdiv (negate @0) @1)) (simplify (rdiv (negate @0) (negate_expr_p @1)) (rdiv @0 (negate @1))) and you should remove the corresponding fold-const.c code. Please do these changes independently to aid bisecting in case of issues. I'll resubmit two different patches when I can get them separated. It should also make it easier to review when it is clearer what belongs where. (if (flag_reciprocal_math) - /* Convert (A/B)/C to A/(B*C) */ + /* Convert (A/B)/C to A/(B*C) where neither B nor C are constant. */ (simplify (rdiv (rdiv:s @0 @1) @2) - (rdiv @0 (mult @1 @2))) + (if (TREE_CODE (@1) != REAL_CST && TREE_CODE (@1) != REAL_CST) +(rdiv @0 (mult @1 @2 why? I guess to avoid ping-poning with Yes, although there is a mistake there. It should be: (if (TREE_CODE (@1) != REAL_CST && TREE_CODE (@2) != REAL_CST) I'll fix that up. + /* Simplify x / (C * y) to (x / C) / y where C is a constant. */ + (simplify + (rdiv @0 + (mult @1 REAL_CST@2)) + (rdiv (rdiv @0 @2) @1)) ? If so why not just d
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Wed, Aug 30, 2017 at 11:46 AM, Jackson Woodruff wrote: > On 08/29/2017 01:13 PM, Richard Biener wrote: >> >> On Tue, Aug 29, 2017 at 1:35 PM, Jackson Woodruff >> wrote: >>> >>> Hi all, >>> >>> Apologies again to those CC'ed, who (again) received this twice. >>> >>> Joseph: Yes you are correct. I misread the original thread, now fixed. >>> >>> Richard: I've moved the optimizations out of fold-const.c. One has been >>> replicated in match.pd, and the other (x / C +- y / C -> (x +- y) / C) >>> I've >>> deleted as it only introduced a new optimization when running with the >>> flags >>> '-O0 -funsafe-math-optimizations'. >> >> >> Hmm, how did you verify that, that it only adds sth with -O0 >> -funsafe-math-optimizations? > > > By checking with various flags, although not exhaustively. I looked for > reasons for the behavior in match.pd (explained below). > > I have also since discovered that the combinations of > '-funsafe-math-optimizations -frounding-math' (at all levels) and > '-fno-recriprocal-math -funsafe-math-optimizations' mean this pattern adds > something. > >> Is that because in GIMPLE the reassoc pass should do this transform? > > It's because the pattern that changes (X / C) -> X * (1 / C) is gated with > O1: > > (for cst (REAL_CST COMPLEX_CST VECTOR_CST) >(simplify > (rdiv @0 cst@1) > ->(if (optimize) > -> (if (flag_reciprocal_math > && !real_zerop (@1)) > (with >{ tree tem = const_binop (RDIV_EXPR, type, build_one_cst (type), @1); > } >(if (tem) > (mult @0 { tem; } ))) > (if (cst != COMPLEX_CST) >(with { tree inverse = exact_inverse (type, @1); } > (if (inverse) > (mult @0 { inverse; } > > > I've flagged the two lines that are particularly relevant to this. So this means we go x / (C * y) -> (x / C) / y -> (x * (1/C)) / y why's that in any way preferable? I suppose this is again to enable the recip pass to detect / y (as opposed to / (C * y))? What's the reason to believe that / y is more "frequent"? > Removing this pattern, as I would expect, means that the divisions in the > above optimization (and the one further down) are not removed. > > So then there is the question of edge cases. This pattern is (ignoring the > second case) going to fail when const_binop returns null. Looking through > that function says that it will fail (for reals) when: > > - Either argument is null (not the case) > > - The operation is not in the list (PLUS_EXPR, > MINUS_EXPR, MULT_EXPR, RDIV_EXPR, MIN_EXPR, MAX_EXPR) > (again not the case) > > - We honor Signalling NaNs and one of the operands is a sNaN. > > - The operation is a division, and the second argument is zero > and dividing by 0.0 raises an exception. > > - The result is infinity and neither of the operands were infinity > and flag_trapping_math is set. > > - The result isn't exact and flag_rounding_math is set. > > > For (x / ( y * C) -> (x / C) / y), I will add some gating for each of these > so that the pattern is never executed if one of these would be the case. Why not transform this directly to (x * (1/C)) / y then (and only then)? That makes it obvious not two divisions prevail. That said, I'm questioning this canonicalization. I can come up with a testcase where it makes things worse: tem = x / (y * C); tem2 = z / (y * C); should generate rdivtmp = 1 / (y*C); tem = x *rdivtmp; tem2= z * rdivtmp; instead of rdivtmp = 1/y; tem = x * 1/C * rdivtmp; tem2 = z * 1/C * rdivtmp; > The additional cases where this isn't converted to a multiplication by the > reciprocal appear to be when -freciprocal-math is used, but we don't have > -fno-rounding-math, or funsafe-math-optimizations. > > For the removal of (x / C +- y / C -> (x +- y) / C), there is a trade-off of > whether it is worth having an extra pattern for these edge cases. On this > I'm not sure. Well, at least leave it in fold-const.c if you can't move it. >> >> You added >> >> +/* Simplify x / (- y) to -x / y. */ >> +(simplify >> + (rdiv @0 (negate @1)) >> + (rdiv (negate @0) @1)) > > > Sorry, this was unclear, the changes to fold const should be split up from > the additions to match.pd. > > This was one of the changes discussed before. The idea is to canonicalize > this so that y can be extracted in the cse_reciprocals pass. As said elsewhere I think cse_reciprocals needs a rewrite to not rely on arbitrary canonicalization to do its work but consider association opportunities globally with a focus on CSE. > >> >> for >> >>/* (-A) / (-B) -> A / B */ >>if (TREE_CODE (arg0) == NEGATE_EXPR && negate_expr_p (arg1)) >> return fold_build2_loc (loc, RDIV_EXPR, type, >> TREE_OPERAND (arg0, 0), >> negate_expr (arg1)); >>if (TREE_CODE (arg1) == NEGATE_EXPR && negate_expr_p (arg0)) >> return fold_build2_loc (loc, RDIV_EXPR, type, >> negate_expr (arg0),
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 09/16/2017 03:39 PM, Bernhard Reutner-Fischer wrote: > On 15 September 2017 18:50:26 CEST, Jeff Law wrote: >> On 09/13/2017 03:20 PM, Wilco Dijkstra wrote: >>> Jeff Law wrote: On 09/06/2017 03:55 AM, Jackson Woodruff wrote: > On 08/30/2017 01:46 PM, Richard Biener wrote: >>> >>rdivtmp = 1 / (y*C); >>tem = x *rdivtmp; >>tem2= z * rdivtmp; >> >> instead of >> >>rdivtmp = 1/y; >>tem = x * 1/C * rdivtmp; >>tem2 = z * 1/C * rdivtmp; > > Ideally we would be able to CSE that into > > rdivtmp = 1/y * 1/C; > tem = x * rdivtmp; > tem2 = z * rdivtmp; So why is your sequence significantly better than Richi's desired seqeuence? They both seem to need 3 mults and a division (which in >> both cases might be a reciprocal estimation).In Richi's sequence we >> have to mult and feed the result as an operand into the reciprocal insn. >> In yours we feed the result of the reciprocal into the multiply. >>> >>> Basically this stuff happens a lot in real code, which is exactly why >> I proposed it. >>> I even provided counts of how many divisions each transformation >> avoids: >>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026. >> I don't doubt that it happens in real code. There's a reason why MIPS >> IV added recip and rsqrt 20 years ago. Our ability to exploit them has >> always been fairly limited though. >> >> What I'm trying to avoid is a transformation where the two forms are >> roughly equal in terms of what they expose vs what they hide. >> >> If pulling the 1/c out is consistently better, then that's obviously >> good. If it's essentially a toss-up because of the other interactions >> with CSE, then we need to think about it more deeply. >> >> I _suspect_ that pulling the 1/c out is generally better, but something >> more concrete than my intuition would be helpful. >> >> >> >> >>> >>> Note this transformation is a canonicalization - if you can't merge a >>> constant somehow, moving it out to the LHS can expose more >>> opportunities, like in (C1 * x) / (C2 * y) -> (C1 * x * C2) / y -> >> (C3 * x) / y. >>> Same for negation as it behaves like * -1. >> FWIW, I generally agree. >> >>> >>> The key here is that it is at least an order of magnitude worse if >> you have >>> to execute an extra division than if you have an extra multiply. >> No doubt. I'll trade a division for a multiply any day. Similarly 1/C >> is just a constant, so I consider it essentially free. >> >> >>> ISTM in the end if y*C or 1/(y*C) is a CSE, then Richi's sequence >> wins. Similarly if 1/y is a CSE, then yours wins. Is there some reason >> to believe that one is a more likely CSE than the other? >>> >>> The idea is that 1/y is much more likely a CSE than 1/(y*C). >> Do we have anything other than intuition to back that up? >>> >>> We could make the pattern only fire in single use cases and see >> whether >>> that makes a difference. It would be easy to test old vs new vs >> single-use >>> new and count how many divisions we end up with. We could add 1/ (y * >> C) >>> to the reciprocal phase if it is unacceptable as a canonicalization, >> but then >>> you won't be able to optimize (C1 * x * C2) / y. >> We could. I think the question would then become does restricting to >> the single-use case kill too many opportunities. >> >> Sigh. I think the 4 of us could go round and round on this forever in >> the pursuit of the perfect code. Though in reality I'm happy with a >> clear improvement. > > > Btw reminds me a little bit of > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=28417 > which IIRC never was applied. Maybe someone could talk Denys (a colleague of > yours nowadays, Jeff) into submitting a real patch? ;) Denys has been a Red Hatter for a long time (approaching 10 years now I think). He's not in the compiler group, but is in the same organization as the compiler group. Tege hasn't worked on GCC regularly in years and Denys hasn't ever really engaged the GCC community all that well. I wouldn't expect 28417 to move forward without something other than Tege and Denys pushing on it. jeff
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
Jeff Law wrote: >> Btw reminds me a little bit of >> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=28417 > I wouldn't expect 28417 > to move forward without something other than Tege and Denys pushing on it. Hmm that doesn't look optimal. You can typically do a multiply with the magic constant arranged in such a way that on 32-bit targets you don't need a shift at all. There isn't much to the proof either, code like this is always self-proving: it tries several possible magic constants until a solution is found that has no error for the max input. Given there are usually several valid solutions, you can then select the best shift/magic value combination. Wilco
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 08/30/2017 01:46 PM, Richard Biener wrote: On Wed, Aug 30, 2017 at 11:46 AM, Jackson Woodruff wrote: On 08/29/2017 01:13 PM, Richard Biener wrote: On Tue, Aug 29, 2017 at 1:35 PM, Jackson Woodruff wrote: Hi all, Apologies again to those CC'ed, who (again) received this twice. Joseph: Yes you are correct. I misread the original thread, now fixed. Richard: I've moved the optimizations out of fold-const.c. One has been replicated in match.pd, and the other (x / C +- y / C -> (x +- y) / C) I've deleted as it only introduced a new optimization when running with the flags '-O0 -funsafe-math-optimizations'. Hmm, how did you verify that, that it only adds sth with -O0 -funsafe-math-optimizations? By checking with various flags, although not exhaustively. I looked for reasons for the behavior in match.pd (explained below). I have also since discovered that the combinations of '-funsafe-math-optimizations -frounding-math' (at all levels) and '-fno-recriprocal-math -funsafe-math-optimizations' mean this pattern adds something. Is that because in GIMPLE the reassoc pass should do this transform? It's because the pattern that changes (X / C) -> X * (1 / C) is gated with O1: (for cst (REAL_CST COMPLEX_CST VECTOR_CST) (simplify (rdiv @0 cst@1) ->(if (optimize) -> (if (flag_reciprocal_math && !real_zerop (@1)) (with { tree tem = const_binop (RDIV_EXPR, type, build_one_cst (type), @1); } (if (tem) (mult @0 { tem; } ))) (if (cst != COMPLEX_CST) (with { tree inverse = exact_inverse (type, @1); } (if (inverse) (mult @0 { inverse; } I've flagged the two lines that are particularly relevant to this. So this means we go x / (C * y) -> (x / C) / y -> (x * (1/C)) / y why's that in any way preferable? I suppose this is again to enable the recip pass to detect / y (as opposed to / (C * y))? What's the reason to believe that / y is more "frequent"? Removing this pattern, as I would expect, means that the divisions in the above optimization (and the one further down) are not removed. So then there is the question of edge cases. This pattern is (ignoring the second case) going to fail when const_binop returns null. Looking through that function says that it will fail (for reals) when: - Either argument is null (not the case) - The operation is not in the list (PLUS_EXPR, MINUS_EXPR, MULT_EXPR, RDIV_EXPR, MIN_EXPR, MAX_EXPR) (again not the case) - We honor Signalling NaNs and one of the operands is a sNaN. - The operation is a division, and the second argument is zero and dividing by 0.0 raises an exception. - The result is infinity and neither of the operands were infinity and flag_trapping_math is set. - The result isn't exact and flag_rounding_math is set. For (x / ( y * C) -> (x / C) / y), I will add some gating for each of these so that the pattern is never executed if one of these would be the case. Why not transform this directly to (x * (1/C)) / y then (and only then)? That makes it obvious not two divisions prevail. Done. That said, I'm questioning this canonicalization. I can come up with a testcase where it makes things worse: tem = x / (y * C); tem2 = z / (y * C); should generate rdivtmp = 1 / (y*C); tem = x *rdivtmp; tem2= z * rdivtmp; instead of rdivtmp = 1/y; tem = x * 1/C * rdivtmp; tem2 = z * 1/C * rdivtmp; Ideally we would be able to CSE that into rdivtmp = 1/y * 1/C; tem = x * rdivtmp; tem2 = z * rdivtmp; Although we currently do not. An equally (perhaps more?) problematic case is something like: tem = x / (y * C) tem2 = y * C Which becomes: tem = x * (1 / C) / y tem2 = y * C Instead of K = y * C tem = x / K tem2 = K Which ultimately requires context awareness to avoid. This does seem to be a general problem with a large number of match.pd patterns rather than anything specific to this one. For example, a similar example can be constructed for (say) (A / B) / C -> (A / (B * C)). The additional cases where this isn't converted to a multiplication by the reciprocal appear to be when -freciprocal-math is used, but we don't have -fno-rounding-math, or funsafe-math-optimizations. >> On O1 and up, the pattern that replaces 'x / C' with 'x * (1 / C)' is enabled and then the pattern is covered by that and (x * C +- y * C -> C * (x +- y)) (which is already present in match.pd) I have also updated the testcase for those optimizations to use 'O1' to avoid that case. On 08/24/2017 10:06 PM, Jeff Law wrote: On 08/17/2017 03:55 AM, Wilco Dijkstra wrote: Richard Biener wrote: On Tue, Aug 15, 2017 at 4:11 PM, Wilco Dijkstra wrote: Richard Biener wrote: We also change the association of x / (y * C) -> (x / C) / y If C is a constant. Why's that profitable? It enables (x * C1) / (y * C2) -> (x * C1/C2) / y for example. Also 1/y is now available to the reciprocal optimization, see https://gcc.g
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 09/06/2017 03:55 AM, Jackson Woodruff wrote: > On 08/30/2017 01:46 PM, Richard Biener wrote: >> On Wed, Aug 30, 2017 at 11:46 AM, Jackson Woodruff >> wrote: >>> On 08/29/2017 01:13 PM, Richard Biener wrote: On Tue, Aug 29, 2017 at 1:35 PM, Jackson Woodruff wrote: > > Hi all, > > Apologies again to those CC'ed, who (again) received this twice. > > Joseph: Yes you are correct. I misread the original thread, now fixed. > > Richard: I've moved the optimizations out of fold-const.c. One has > been > replicated in match.pd, and the other (x / C +- y / C -> (x +- y) / C) > I've > deleted as it only introduced a new optimization when running with the > flags > '-O0 -funsafe-math-optimizations'. Hmm, how did you verify that, that it only adds sth with -O0 -funsafe-math-optimizations? >>> >>> >>> By checking with various flags, although not exhaustively. I looked for >>> reasons for the behavior in match.pd (explained below). >>> >>> I have also since discovered that the combinations of >>> '-funsafe-math-optimizations -frounding-math' (at all levels) and >>> '-fno-recriprocal-math -funsafe-math-optimizations' mean this pattern >>> adds >>> something. >>> Is that because in GIMPLE the reassoc pass should do this transform? >>> >>> It's because the pattern that changes (X / C) -> X * (1 / C) is gated >>> with >>> O1: >>> >>>(for cst (REAL_CST COMPLEX_CST VECTOR_CST) >>> (simplify >>> (rdiv @0 cst@1) >>> ->(if (optimize) >>> -> (if (flag_reciprocal_math >>>&& !real_zerop (@1)) >>>(with >>> { tree tem = const_binop (RDIV_EXPR, type, build_one_cst >>> (type), @1); >>> } >>> (if (tem) >>> (mult @0 { tem; } ))) >>>(if (cst != COMPLEX_CST) >>> (with { tree inverse = exact_inverse (type, @1); } >>> (if (inverse) >>> (mult @0 { inverse; } >>> >>> >>> I've flagged the two lines that are particularly relevant to this. >> >> So this means we go x / (C * y) -> (x / C) / y -> (x * (1/C)) / y >> why's that in any way preferable? I suppose this is again to enable >> the recip pass to detect / y (as opposed to / (C * y))? What's the >> reason to believe that / y is more "frequent"? >> >>> Removing this pattern, as I would expect, means that the divisions in >>> the >>> above optimization (and the one further down) are not removed. >>> >>> So then there is the question of edge cases. This pattern is >>> (ignoring the >>> second case) going to fail when const_binop returns null. Looking >>> through >>> that function says that it will fail (for reals) when: >>> >>> - Either argument is null (not the case) >>> >>> - The operation is not in the list (PLUS_EXPR, >>>MINUS_EXPR, MULT_EXPR, RDIV_EXPR, MIN_EXPR, MAX_EXPR) >>>(again not the case) >>> >>> - We honor Signalling NaNs and one of the operands is a sNaN. >>> >>> - The operation is a division, and the second argument is zero >>>and dividing by 0.0 raises an exception. >>> >>> - The result is infinity and neither of the operands were infinity >>>and flag_trapping_math is set. >>> >>> - The result isn't exact and flag_rounding_math is set. >>> >>> >>> For (x / ( y * C) -> (x / C) / y), I will add some gating for each of >>> these >>> so that the pattern is never executed if one of these would be the case. >> >> Why not transform this directly to (x * (1/C)) / y then (and only then)? >> That makes it obvious not two divisions prevail. > > Done. > >> >> That said, I'm questioning this canonicalization. I can come up with a >> testcase where it makes things worse: >> >> tem = x / (y * C); >> tem2 = z / (y * C); >> >> should generate >> >> rdivtmp = 1 / (y*C); >> tem = x *rdivtmp; >> tem2= z * rdivtmp; >> >> instead of >> >> rdivtmp = 1/y; >> tem = x * 1/C * rdivtmp; >> tem2 = z * 1/C * rdivtmp; > > Ideally we would be able to CSE that into > > rdivtmp = 1/y * 1/C; > tem = x * rdivtmp; > tem2 = z * rdivtmp; So why is your sequence significantly better than Richi's desired seqeuence? They both seem to need 3 mults and a division (which in both cases might be a reciprocal estimation).In Richi's sequence we have to mult and feed the result as an operand into the reciprocal insn. In yours we feed the result of the reciprocal into the multiply. ISTM in the end if y*C or 1/(y*C) is a CSE, then Richi's sequence wins. Similarly if 1/y is a CSE, then yours wins. Is there some reason to believe that one is a more likely CSE than the other? > Although we currently do not. An equally (perhaps more?) problematic > case is something like: > > tem = x / (y * C) > tem2 = y * C > > Which becomes: > > tem = x * (1 / C) / y > tem2 = y * C > > Instead of > > K = y * C > tem = x / K > tem2 = K > > Which ultimately requires context awareness to avoid. This does seem to > be a general problem with a large number of match.pd patterns rather > than anythin
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
Jeff Law wrote: > On 09/06/2017 03:55 AM, Jackson Woodruff wrote: > > On 08/30/2017 01:46 PM, Richard Biener wrote: >>> rdivtmp = 1 / (y*C); >>> tem = x *rdivtmp; >>> tem2= z * rdivtmp; >>> >>> instead of >>> >>> rdivtmp = 1/y; >>> tem = x * 1/C * rdivtmp; >>> tem2 = z * 1/C * rdivtmp; >> >> Ideally we would be able to CSE that into >> >> rdivtmp = 1/y * 1/C; >> tem = x * rdivtmp; >> tem2 = z * rdivtmp; > So why is your sequence significantly better than Richi's desired > seqeuence? They both seem to need 3 mults and a division (which in both > cases might be a reciprocal estimation). In Richi's sequence we have > to mult and feed the result as an operand into the reciprocal insn. In > yours we feed the result of the reciprocal into the multiply. Basically this stuff happens a lot in real code, which is exactly why I proposed it. I even provided counts of how many divisions each transformation avoids: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026. Note this transformation is a canonicalization - if you can't merge a constant somehow, moving it out to the LHS can expose more opportunities, like in (C1 * x) / (C2 * y) -> (C1 * x * C2) / y -> (C3 * x) / y. Same for negation as it behaves like * -1. The key here is that it is at least an order of magnitude worse if you have to execute an extra division than if you have an extra multiply. > ISTM in the end if y*C or 1/(y*C) is a CSE, then Richi's sequence wins. > Similarly if 1/y is a CSE, then yours wins. Is there some reason to > believe that one is a more likely CSE than the other? The idea is that 1/y is much more likely a CSE than 1/(y*C). We could make the pattern only fire in single use cases and see whether that makes a difference. It would be easy to test old vs new vs single-use new and count how many divisions we end up with. We could add 1/ (y * C) to the reciprocal phase if it is unacceptable as a canonicalization, but then you won't be able to optimize (C1 * x * C2) / y. > I think there's a fundamental phase ordering problem here. You want to > CSE stuff as much as possible, then expose reciprocals, then CSE again > because exposing reciprocals can expose new CSE opportunities. I agree there are phase ordering issues and various problems in reassociation, CSE and division optimizations not being able to find and optimize complex cases that are worthwhile. However I don't agree doing CSE before reciprocals is a good idea. We want to expose reciprocals early on, even if that means we find fewer CSEs as a result - again because division is so much more expensive than any other operation. CSE is generally not smart enough to CSE a * x in a * b * x and a * c * x, something which is likely to happen quite frequently - unlike the made up division examples here. > And I suspect that no matter how hard we try, there's going to be cases > that get exposed by various transformations in the pipeline such that to > fully optimize the cse - reciprocal - cse sequence would need to be > repeated to fully optimize. We may have to live with not being > particularly good at picking up the those second order effects. > > I do think that the need for cse - reciprocal - cse sequencing suggests > that match.pd may not be the right place for these transformations. I > think Richi has pointed this out a couple times already. I don't think you can ever expect to find the optimal case by repeating optimizations. It's quite easy to construct examples where first doing CSE makes things significantly worse. Ultimately to get something optimal you'd need to try lots of permutations and count for each possible permutation how many multiplies and divisons you end up after full optimization. Quite impractical... > I'm not going to accept or reject at this time. I think we need to make > a higher level decision. Are these transformations better suited for > match.pd or the reciprocal transformation pass? I realize that some > patterns are already in match.pd, but let's try to settle the higher > level issue before we add more. The first question is whether you see it as a canonicalization. If so, then match.pd should be fine. Wilco
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On Wed, Sep 13, 2017 at 11:20 PM, Wilco Dijkstra wrote: > Jeff Law wrote: >> On 09/06/2017 03:55 AM, Jackson Woodruff wrote: >> > On 08/30/2017 01:46 PM, Richard Biener wrote: > rdivtmp = 1 / (y*C); tem = x *rdivtmp; tem2= z * rdivtmp; instead of rdivtmp = 1/y; tem = x * 1/C * rdivtmp; tem2 = z * 1/C * rdivtmp; >>> >>> Ideally we would be able to CSE that into >>> >>> rdivtmp = 1/y * 1/C; >>> tem = x * rdivtmp; >>> tem2 = z * rdivtmp; >> So why is your sequence significantly better than Richi's desired >> seqeuence? They both seem to need 3 mults and a division (which in both >> cases might be a reciprocal estimation).In Richi's sequence we have >> to mult and feed the result as an operand into the reciprocal insn. In >> yours we feed the result of the reciprocal into the multiply. > > Basically this stuff happens a lot in real code, which is exactly why I > proposed it. > I even provided counts of how many divisions each transformation avoids: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026. > > Note this transformation is a canonicalization - if you can't merge a > constant somehow, moving it out to the LHS can expose more > opportunities, like in (C1 * x) / (C2 * y) -> (C1 * x * C2) / y -> (C3 * x) / > y. > Same for negation as it behaves like * -1. > > The key here is that it is at least an order of magnitude worse if you have > to execute an extra division than if you have an extra multiply. > >> ISTM in the end if y*C or 1/(y*C) is a CSE, then Richi's sequence wins. >> Similarly if 1/y is a CSE, then yours wins. Is there some reason to >> believe that one is a more likely CSE than the other? > > The idea is that 1/y is much more likely a CSE than 1/(y*C). > > We could make the pattern only fire in single use cases and see whether > that makes a difference. It would be easy to test old vs new vs single-use > new and count how many divisions we end up with. We could add 1/ (y * C) > to the reciprocal phase if it is unacceptable as a canonicalization, but then > you won't be able to optimize (C1 * x * C2) / y. > >> I think there's a fundamental phase ordering problem here. You want to >> CSE stuff as much as possible, then expose reciprocals, then CSE again >> because exposing reciprocals can expose new CSE opportunities. > > I agree there are phase ordering issues and various problems in > reassociation, CSE and division optimizations not being able to find and > optimize complex cases that are worthwhile. > > However I don't agree doing CSE before reciprocals is a good idea. We > want to expose reciprocals early on, even if that means we find fewer > CSEs as a result - again because division is so much more expensive than > any other operation. CSE is generally not smart enough to CSE a * x in > a * b * x and a * c * x, something which is likely to happen quite frequently > - > unlike the made up division examples here. > >> And I suspect that no matter how hard we try, there's going to be cases >> that get exposed by various transformations in the pipeline such that to >> fully optimize the cse - reciprocal - cse sequence would need to be >> repeated to fully optimize. We may have to live with not being >> particularly good at picking up the those second order effects. >> >> I do think that the need for cse - reciprocal - cse sequencing suggests >> that match.pd may not be the right place for these transformations. I >> think Richi has pointed this out a couple times already. > > I don't think you can ever expect to find the optimal case by repeating > optimizations. It's quite easy to construct examples where first doing CSE > makes things significantly worse. Ultimately to get something optimal you'd > need to try lots of permutations and count for each possible permutation > how many multiplies and divisons you end up after full optimization. > Quite impractical... > >> I'm not going to accept or reject at this time. I think we need to make >> a higher level decision. Are these transformations better suited for >> match.pd or the reciprocal transformation pass? I realize that some >> patterns are already in match.pd, but let's try to settle the higher >> level issue before we add more. > > The first question is whether you see it as a canonicalization. If so, then > match.pd should be fine. A canonicalization to more divisions is not fine. That is, if we think that x / (C * y) is non-canonical because constant parts should be in the denominator then fine, canonicalize it as (x * C') / y with C' = 1/C. But then implement it so, not in a pattern that suggests you'll end up with two divisions. Let me repeat though that this looks like a job for re-association. >From that perspective the part of the patch doing + /* Simplify x / (C * y) to (x * (1 / C)) / y where C is a constant. */ + (if (optimize) + (simplify + (rdiv @0 +(mult @1 REAL_CST@2)) + (if (!real_zerop (@1)) +(with + { tree tem = const_b
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 09/13/2017 03:20 PM, Wilco Dijkstra wrote: > Jeff Law wrote: >> On 09/06/2017 03:55 AM, Jackson Woodruff wrote: >>> On 08/30/2017 01:46 PM, Richard Biener wrote: > rdivtmp = 1 / (y*C); tem = x *rdivtmp; tem2= z * rdivtmp; instead of rdivtmp = 1/y; tem = x * 1/C * rdivtmp; tem2 = z * 1/C * rdivtmp; >>> >>> Ideally we would be able to CSE that into >>> >>> rdivtmp = 1/y * 1/C; >>> tem = x * rdivtmp; >>> tem2 = z * rdivtmp; >> So why is your sequence significantly better than Richi's desired >> seqeuence? They both seem to need 3 mults and a division (which in both >> cases might be a reciprocal estimation).In Richi's sequence we have >> to mult and feed the result as an operand into the reciprocal insn. In >> yours we feed the result of the reciprocal into the multiply. > > Basically this stuff happens a lot in real code, which is exactly why I > proposed it. > I even provided counts of how many divisions each transformation avoids: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026. I don't doubt that it happens in real code. There's a reason why MIPS IV added recip and rsqrt 20 years ago. Our ability to exploit them has always been fairly limited though. What I'm trying to avoid is a transformation where the two forms are roughly equal in terms of what they expose vs what they hide. If pulling the 1/c out is consistently better, then that's obviously good. If it's essentially a toss-up because of the other interactions with CSE, then we need to think about it more deeply. I _suspect_ that pulling the 1/c out is generally better, but something more concrete than my intuition would be helpful. > > Note this transformation is a canonicalization - if you can't merge a > constant somehow, moving it out to the LHS can expose more > opportunities, like in (C1 * x) / (C2 * y) -> (C1 * x * C2) / y -> (C3 * x) / > y. > Same for negation as it behaves like * -1. FWIW, I generally agree. > > The key here is that it is at least an order of magnitude worse if you have > to execute an extra division than if you have an extra multiply. No doubt. I'll trade a division for a multiply any day. Similarly 1/C is just a constant, so I consider it essentially free. > >> ISTM in the end if y*C or 1/(y*C) is a CSE, then Richi's sequence wins. >> Similarly if 1/y is a CSE, then yours wins. Is there some reason to >> believe that one is a more likely CSE than the other? > > The idea is that 1/y is much more likely a CSE than 1/(y*C). Do we have anything other than intuition to back that up? > > We could make the pattern only fire in single use cases and see whether > that makes a difference. It would be easy to test old vs new vs single-use > new and count how many divisions we end up with. We could add 1/ (y * C) > to the reciprocal phase if it is unacceptable as a canonicalization, but then > you won't be able to optimize (C1 * x * C2) / y. We could. I think the question would then become does restricting to the single-use case kill too many opportunities. Sigh. I think the 4 of us could go round and round on this forever in the pursuit of the perfect code. Though in reality I'm happy with a clear improvement. > >> I think there's a fundamental phase ordering problem here. You want to >> CSE stuff as much as possible, then expose reciprocals, then CSE again >> because exposing reciprocals can expose new CSE opportunities. > > I agree there are phase ordering issues and various problems in > reassociation, CSE and division optimizations not being able to find and > optimize complex cases that are worthwhile. > > However I don't agree doing CSE before reciprocals is a good idea. We > want to expose reciprocals early on, even if that means we find fewer > CSEs as a result - again because division is so much more expensive than > any other operation. CSE is generally not smart enough to CSE a * x in > a * b * x and a * c * x, something which is likely to happen quite frequently > - > unlike the made up division examples here. We have much stronger reassociation capabilities for multiplication -- it's a well understood problem and if we fail to pick up a * x across those two kind of expressions, I'd consider our reassociation code as failing pretty badly, particularly for integer types. BUt yes, division is expensive. And I'm all for a tranformation that turns a division into a multiplication. That's almost always a win. > > The first question is whether you see it as a canonicalization. If so, then > match.pd should be fine. Pulling the constant part out of the denominator and turning it into a multiplication by the recip constant should likely be considered canonicalization. I think Richi largely agreed to this in the thread as well and asked for that hunk of the patch to be extracted and submitted independent of the other changes so that it could go ahead and move forward while we figure out the rest. Note that tre
Re: [PATCH] Factor out division by squares and remove division around comparisons (1/2)
On 15 September 2017 18:50:26 CEST, Jeff Law wrote: >On 09/13/2017 03:20 PM, Wilco Dijkstra wrote: >> Jeff Law wrote: >>> On 09/06/2017 03:55 AM, Jackson Woodruff wrote: On 08/30/2017 01:46 PM, Richard Biener wrote: >> >rdivtmp = 1 / (y*C); >tem = x *rdivtmp; >tem2= z * rdivtmp; > > instead of > >rdivtmp = 1/y; >tem = x * 1/C * rdivtmp; >tem2 = z * 1/C * rdivtmp; Ideally we would be able to CSE that into rdivtmp = 1/y * 1/C; tem = x * rdivtmp; tem2 = z * rdivtmp; >>> So why is your sequence significantly better than Richi's desired >>> seqeuence? They both seem to need 3 mults and a division (which in >both >>> cases might be a reciprocal estimation).In Richi's sequence we >have >>> to mult and feed the result as an operand into the reciprocal insn. >In >>> yours we feed the result of the reciprocal into the multiply. >> >> Basically this stuff happens a lot in real code, which is exactly why >I proposed it. >> I even provided counts of how many divisions each transformation >avoids: >> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026. >I don't doubt that it happens in real code. There's a reason why MIPS >IV added recip and rsqrt 20 years ago. Our ability to exploit them has >always been fairly limited though. > >What I'm trying to avoid is a transformation where the two forms are >roughly equal in terms of what they expose vs what they hide. > >If pulling the 1/c out is consistently better, then that's obviously >good. If it's essentially a toss-up because of the other interactions >with CSE, then we need to think about it more deeply. > >I _suspect_ that pulling the 1/c out is generally better, but something >more concrete than my intuition would be helpful. > > > > >> >> Note this transformation is a canonicalization - if you can't merge a >> constant somehow, moving it out to the LHS can expose more >> opportunities, like in (C1 * x) / (C2 * y) -> (C1 * x * C2) / y -> >(C3 * x) / y. >> Same for negation as it behaves like * -1. >FWIW, I generally agree. > >> >> The key here is that it is at least an order of magnitude worse if >you have >> to execute an extra division than if you have an extra multiply. >No doubt. I'll trade a division for a multiply any day. Similarly 1/C >is just a constant, so I consider it essentially free. > > >> >>> ISTM in the end if y*C or 1/(y*C) is a CSE, then Richi's sequence >wins. >>> Similarly if 1/y is a CSE, then yours wins. Is there some reason >to >>> believe that one is a more likely CSE than the other? >> >> The idea is that 1/y is much more likely a CSE than 1/(y*C). >Do we have anything other than intuition to back that up? >> >> We could make the pattern only fire in single use cases and see >whether >> that makes a difference. It would be easy to test old vs new vs >single-use >> new and count how many divisions we end up with. We could add 1/ (y * >C) >> to the reciprocal phase if it is unacceptable as a canonicalization, >but then >> you won't be able to optimize (C1 * x * C2) / y. >We could. I think the question would then become does restricting to >the single-use case kill too many opportunities. > >Sigh. I think the 4 of us could go round and round on this forever in >the pursuit of the perfect code. Though in reality I'm happy with a >clear improvement. Btw reminds me a little bit of https://gcc.gnu.org/bugzilla/show_bug.cgi?id=28417 which IIRC never was applied. Maybe someone could talk Denys (a colleague of yours nowadays, Jeff) into submitting a real patch? ;) Cheers, > >> >>> I think there's a fundamental phase ordering problem here. You want >to >>> CSE stuff as much as possible, then expose reciprocals, then CSE >again >>> because exposing reciprocals can expose new CSE opportunities. >> >> I agree there are phase ordering issues and various problems in >> reassociation, CSE and division optimizations not being able to find >and >> optimize complex cases that are worthwhile. >> >> However I don't agree doing CSE before reciprocals is a good idea. We >> want to expose reciprocals early on, even if that means we find fewer >> CSEs as a result - again because division is so much more expensive >than >> any other operation. CSE is generally not smart enough to CSE a * x >in >> a * b * x and a * c * x, something which is likely to happen quite >frequently - >> unlike the made up division examples here. >We have much stronger reassociation capabilities for multiplication -- >it's a well understood problem and if we fail to pick up a * x across >those two kind of expressions, I'd consider our reassociation code as >failing pretty badly, particularly for integer types. > >BUt yes, division is expensive. And I'm all for a tranformation that >turns a division into a multiplication. That's almost always a win. > >> >> The first question is whether you see it as a canonicalization. If >so, then >> match.pd should be fine. >Pull