* [PATCH] reassoc: Reassociate integral multiplies [PR95867[
@ 2021-01-10 14:56 Jakub Jelinek
2021-01-11 8:17 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2021-01-10 14:56 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
Hi!
For floating point multiply, we have nice code in reassoc to reassociate
multiplications to almost optimal sequence of as few multiplications as
possible (or library call), but for integral types we just give up
because there is no __builtin_powi* for those types.
As there is no library routine we could use, instead of adding new internal
call just to hold it temporarily and then lower to multiplications again,
this patch for the integral types calls into the sincos pass routine that
expands it into multiplications right away.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2021-01-09 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/95867
* tree-ssa-math-opts.h: New header.
* tree-ssa-math-opts.c: Include tree-ssa-math-opts.h.
(powi_as_mults): No longer static. Use build_one_cst instead of
build_real. Formatting fix.
* tree-ssa-reassoc.c: Include tree-ssa-math-opts.h.
(attempt_builtin_powi): Handle multiplication reassociation without
powi_fndecl using powi_as_mults.
(reassociate_bb): For integral types don't require
-funsafe-math-optimizations to call attempt_builtin_powi.
* gcc.dg/tree-ssa/pr95867.c: New test.
--- gcc/tree-ssa-math-opts.h.jj 2021-01-09 16:54:58.301092357 +0100
+++ gcc/tree-ssa-math-opts.h 2021-01-09 16:56:32.098024806 +0100
@@ -0,0 +1,26 @@
+/* Global, SSA-based optimizations using mathematical identities.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef GCC_TREE_SSA_MATH_OPTS_H
+#define GCC_TREE_SSA_MATH_OPTS_H
+
+extern tree powi_as_mults (gimple_stmt_iterator *, location_t,
+ tree, HOST_WIDE_INT);
+
+#endif /* GCC_TREE_SSA_MATH_OPTS_H */
--- gcc/tree-ssa-math-opts.c.jj 2021-01-09 10:47:18.000000000 +0100
+++ gcc/tree-ssa-math-opts.c 2021-01-09 16:58:59.442347773 +0100
@@ -115,6 +115,7 @@ along with GCC; see the file COPYING3.
#include "tree-eh.h"
#include "targhooks.h"
#include "domwalk.h"
+#include "tree-ssa-math-opts.h"
/* This structure represents one basic block that either computes a
division, or is a common dominator for basic block that compute a
@@ -1527,7 +1528,7 @@ powi_as_mults_1 (gimple_stmt_iterator *g
/* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
This function needs to be kept in sync with powi_cost above. */
-static tree
+tree
powi_as_mults (gimple_stmt_iterator *gsi, location_t loc,
tree arg0, HOST_WIDE_INT n)
{
@@ -1536,9 +1537,9 @@ powi_as_mults (gimple_stmt_iterator *gsi
tree target;
if (n == 0)
- return build_real (type, dconst1);
+ return build_one_cst (type);
- memset (cache, 0, sizeof (cache));
+ memset (cache, 0, sizeof (cache));
cache[1] = arg0;
result = powi_as_mults_1 (gsi, loc, type, (n < 0) ? -n : n, cache);
--- gcc/tree-ssa-reassoc.c.jj 2021-01-05 16:37:36.254185194 +0100
+++ gcc/tree-ssa-reassoc.c 2021-01-09 17:20:48.205462550 +0100
@@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.
#include "gimplify.h"
#include "case-cfn-macros.h"
#include "tree-ssa-reassoc.h"
+#include "tree-ssa-math-opts.h"
/* This is a simple global reassociation pass. It is, in part, based
on the LLVM pass of the same name (They do some things more/less
@@ -5976,8 +5977,8 @@ attempt_builtin_powi (gimple *stmt, vec<
gimple *mul_stmt, *pow_stmt;
/* Nothing to do if BUILT_IN_POWI doesn't exist for this type and
- target. */
- if (!powi_fndecl)
+ target, unless type is integral. */
+ if (!powi_fndecl && !INTEGRAL_TYPE_P (type))
return NULL_TREE;
/* Allocate the repeated factor vector. */
@@ -6086,14 +6087,33 @@ attempt_builtin_powi (gimple *stmt, vec<
}
else
{
- iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
- pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
- build_int_cst (integer_type_node,
- power));
- gimple_call_set_lhs (pow_stmt, iter_result);
- gimple_set_location (pow_stmt, gimple_location (stmt));
- gimple_set_uid (pow_stmt, gimple_uid (stmt));
- gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
+ if (INTEGRAL_TYPE_P (type))
+ {
+ gcc_assert (power > 1);
+ gimple_stmt_iterator gsip = gsi;
+ gsi_prev (&gsip);
+ iter_result = powi_as_mults (&gsi, gimple_location (stmt),
+ rf1->repr, power);
+ gimple_stmt_iterator gsic = gsi;
+ while (gsi_stmt (gsic) != gsi_stmt (gsip))
+ {
+ gimple_set_uid (gsi_stmt (gsic), gimple_uid (stmt));
+ gimple_set_visited (gsi_stmt (gsic), true);
+ gsi_prev (&gsic);
+ }
+ }
+ else
+ {
+ iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
+ pow_stmt
+ = gimple_build_call (powi_fndecl, 2, rf1->repr,
+ build_int_cst (integer_type_node,
+ power));
+ gimple_call_set_lhs (pow_stmt, iter_result);
+ gimple_set_location (pow_stmt, gimple_location (stmt));
+ gimple_set_uid (pow_stmt, gimple_uid (stmt));
+ gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -6188,14 +6208,32 @@ attempt_builtin_powi (gimple *stmt, vec<
/* Form a call to __builtin_powi for the maximum product
just formed, raised to the power obtained earlier. */
rf1 = &repeat_factor_vec[j];
- iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
- pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
- build_int_cst (integer_type_node,
- power));
- gimple_call_set_lhs (pow_stmt, iter_result);
- gimple_set_location (pow_stmt, gimple_location (stmt));
- gimple_set_uid (pow_stmt, gimple_uid (stmt));
- gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
+ if (INTEGRAL_TYPE_P (type))
+ {
+ gcc_assert (power > 1);
+ gimple_stmt_iterator gsip = gsi;
+ gsi_prev (&gsip);
+ iter_result = powi_as_mults (&gsi, gimple_location (stmt),
+ rf1->repr, power);
+ gimple_stmt_iterator gsic = gsi;
+ while (gsi_stmt (gsic) != gsi_stmt (gsip))
+ {
+ gimple_set_uid (gsi_stmt (gsic), gimple_uid (stmt));
+ gimple_set_visited (gsi_stmt (gsic), true);
+ gsi_prev (&gsic);
+ }
+ }
+ else
+ {
+ iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
+ pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
+ build_int_cst (integer_type_node,
+ power));
+ gimple_call_set_lhs (pow_stmt, iter_result);
+ gimple_set_location (pow_stmt, gimple_location (stmt));
+ gimple_set_uid (pow_stmt, gimple_uid (stmt));
+ gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
+ }
}
/* If we previously formed at least one other builtin_powi call,
@@ -6522,7 +6560,8 @@ reassociate_bb (basic_block bb)
attempt_builtin_copysign (&ops);
if (reassoc_insert_powi_p
- && flag_unsafe_math_optimizations)
+ && (flag_unsafe_math_optimizations
+ || (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))))
powi_result = attempt_builtin_powi (stmt, &ops);
}
--- gcc/testsuite/gcc.dg/tree-ssa/pr95867.c.jj 2021-01-09 17:49:53.935641884 +0100
+++ gcc/testsuite/gcc.dg/tree-ssa/pr95867.c 2021-01-09 17:49:36.896835332 +0100
@@ -0,0 +1,14 @@
+/* PR tree-optimization/95867 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-times " \\* " 13 "optimized" } } */
+
+#define A n * n * n * n * n * n * n * n
+#define B A * A * A * A * A * A * A * A
+#define C B * B * B * B * B * B * B * B
+
+unsigned
+foo (unsigned n)
+{
+ return C * B * B * A * n * n * n * n * n;
+}
Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] reassoc: Reassociate integral multiplies [PR95867[
2021-01-10 14:56 [PATCH] reassoc: Reassociate integral multiplies [PR95867[ Jakub Jelinek
@ 2021-01-11 8:17 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2021-01-11 8:17 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches
On Sun, 10 Jan 2021, Jakub Jelinek wrote:
> Hi!
>
> For floating point multiply, we have nice code in reassoc to reassociate
> multiplications to almost optimal sequence of as few multiplications as
> possible (or library call), but for integral types we just give up
> because there is no __builtin_powi* for those types.
>
> As there is no library routine we could use, instead of adding new internal
> call just to hold it temporarily and then lower to multiplications again,
> this patch for the integral types calls into the sincos pass routine that
> expands it into multiplications right away.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Thanks,
Richard.
> 2021-01-09 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/95867
> * tree-ssa-math-opts.h: New header.
> * tree-ssa-math-opts.c: Include tree-ssa-math-opts.h.
> (powi_as_mults): No longer static. Use build_one_cst instead of
> build_real. Formatting fix.
> * tree-ssa-reassoc.c: Include tree-ssa-math-opts.h.
> (attempt_builtin_powi): Handle multiplication reassociation without
> powi_fndecl using powi_as_mults.
> (reassociate_bb): For integral types don't require
> -funsafe-math-optimizations to call attempt_builtin_powi.
>
> * gcc.dg/tree-ssa/pr95867.c: New test.
>
> --- gcc/tree-ssa-math-opts.h.jj 2021-01-09 16:54:58.301092357 +0100
> +++ gcc/tree-ssa-math-opts.h 2021-01-09 16:56:32.098024806 +0100
> @@ -0,0 +1,26 @@
> +/* Global, SSA-based optimizations using mathematical identities.
> + Copyright (C) 2021 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it under
> +the terms of the GNU General Public License as published by the Free
> +Software Foundation; either version 3, or (at your option) any later
> +version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
> +for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +#ifndef GCC_TREE_SSA_MATH_OPTS_H
> +#define GCC_TREE_SSA_MATH_OPTS_H
> +
> +extern tree powi_as_mults (gimple_stmt_iterator *, location_t,
> + tree, HOST_WIDE_INT);
> +
> +#endif /* GCC_TREE_SSA_MATH_OPTS_H */
> --- gcc/tree-ssa-math-opts.c.jj 2021-01-09 10:47:18.000000000 +0100
> +++ gcc/tree-ssa-math-opts.c 2021-01-09 16:58:59.442347773 +0100
> @@ -115,6 +115,7 @@ along with GCC; see the file COPYING3.
> #include "tree-eh.h"
> #include "targhooks.h"
> #include "domwalk.h"
> +#include "tree-ssa-math-opts.h"
>
> /* This structure represents one basic block that either computes a
> division, or is a common dominator for basic block that compute a
> @@ -1527,7 +1528,7 @@ powi_as_mults_1 (gimple_stmt_iterator *g
> /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
> This function needs to be kept in sync with powi_cost above. */
>
> -static tree
> +tree
> powi_as_mults (gimple_stmt_iterator *gsi, location_t loc,
> tree arg0, HOST_WIDE_INT n)
> {
> @@ -1536,9 +1537,9 @@ powi_as_mults (gimple_stmt_iterator *gsi
> tree target;
>
> if (n == 0)
> - return build_real (type, dconst1);
> + return build_one_cst (type);
>
> - memset (cache, 0, sizeof (cache));
> + memset (cache, 0, sizeof (cache));
> cache[1] = arg0;
>
> result = powi_as_mults_1 (gsi, loc, type, (n < 0) ? -n : n, cache);
> --- gcc/tree-ssa-reassoc.c.jj 2021-01-05 16:37:36.254185194 +0100
> +++ gcc/tree-ssa-reassoc.c 2021-01-09 17:20:48.205462550 +0100
> @@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.
> #include "gimplify.h"
> #include "case-cfn-macros.h"
> #include "tree-ssa-reassoc.h"
> +#include "tree-ssa-math-opts.h"
>
> /* This is a simple global reassociation pass. It is, in part, based
> on the LLVM pass of the same name (They do some things more/less
> @@ -5976,8 +5977,8 @@ attempt_builtin_powi (gimple *stmt, vec<
> gimple *mul_stmt, *pow_stmt;
>
> /* Nothing to do if BUILT_IN_POWI doesn't exist for this type and
> - target. */
> - if (!powi_fndecl)
> + target, unless type is integral. */
> + if (!powi_fndecl && !INTEGRAL_TYPE_P (type))
> return NULL_TREE;
>
> /* Allocate the repeated factor vector. */
> @@ -6086,14 +6087,33 @@ attempt_builtin_powi (gimple *stmt, vec<
> }
> else
> {
> - iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
> - pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
> - build_int_cst (integer_type_node,
> - power));
> - gimple_call_set_lhs (pow_stmt, iter_result);
> - gimple_set_location (pow_stmt, gimple_location (stmt));
> - gimple_set_uid (pow_stmt, gimple_uid (stmt));
> - gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
> + if (INTEGRAL_TYPE_P (type))
> + {
> + gcc_assert (power > 1);
> + gimple_stmt_iterator gsip = gsi;
> + gsi_prev (&gsip);
> + iter_result = powi_as_mults (&gsi, gimple_location (stmt),
> + rf1->repr, power);
> + gimple_stmt_iterator gsic = gsi;
> + while (gsi_stmt (gsic) != gsi_stmt (gsip))
> + {
> + gimple_set_uid (gsi_stmt (gsic), gimple_uid (stmt));
> + gimple_set_visited (gsi_stmt (gsic), true);
> + gsi_prev (&gsic);
> + }
> + }
> + else
> + {
> + iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
> + pow_stmt
> + = gimple_build_call (powi_fndecl, 2, rf1->repr,
> + build_int_cst (integer_type_node,
> + power));
> + gimple_call_set_lhs (pow_stmt, iter_result);
> + gimple_set_location (pow_stmt, gimple_location (stmt));
> + gimple_set_uid (pow_stmt, gimple_uid (stmt));
> + gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
> + }
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> {
> @@ -6188,14 +6208,32 @@ attempt_builtin_powi (gimple *stmt, vec<
> /* Form a call to __builtin_powi for the maximum product
> just formed, raised to the power obtained earlier. */
> rf1 = &repeat_factor_vec[j];
> - iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
> - pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
> - build_int_cst (integer_type_node,
> - power));
> - gimple_call_set_lhs (pow_stmt, iter_result);
> - gimple_set_location (pow_stmt, gimple_location (stmt));
> - gimple_set_uid (pow_stmt, gimple_uid (stmt));
> - gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
> + if (INTEGRAL_TYPE_P (type))
> + {
> + gcc_assert (power > 1);
> + gimple_stmt_iterator gsip = gsi;
> + gsi_prev (&gsip);
> + iter_result = powi_as_mults (&gsi, gimple_location (stmt),
> + rf1->repr, power);
> + gimple_stmt_iterator gsic = gsi;
> + while (gsi_stmt (gsic) != gsi_stmt (gsip))
> + {
> + gimple_set_uid (gsi_stmt (gsic), gimple_uid (stmt));
> + gimple_set_visited (gsi_stmt (gsic), true);
> + gsi_prev (&gsic);
> + }
> + }
> + else
> + {
> + iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
> + pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
> + build_int_cst (integer_type_node,
> + power));
> + gimple_call_set_lhs (pow_stmt, iter_result);
> + gimple_set_location (pow_stmt, gimple_location (stmt));
> + gimple_set_uid (pow_stmt, gimple_uid (stmt));
> + gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
> + }
> }
>
> /* If we previously formed at least one other builtin_powi call,
> @@ -6522,7 +6560,8 @@ reassociate_bb (basic_block bb)
> attempt_builtin_copysign (&ops);
>
> if (reassoc_insert_powi_p
> - && flag_unsafe_math_optimizations)
> + && (flag_unsafe_math_optimizations
> + || (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))))
> powi_result = attempt_builtin_powi (stmt, &ops);
> }
>
> --- gcc/testsuite/gcc.dg/tree-ssa/pr95867.c.jj 2021-01-09 17:49:53.935641884 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr95867.c 2021-01-09 17:49:36.896835332 +0100
> @@ -0,0 +1,14 @@
> +/* PR tree-optimization/95867 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-times " \\* " 13 "optimized" } } */
> +
> +#define A n * n * n * n * n * n * n * n
> +#define B A * A * A * A * A * A * A * A
> +#define C B * B * B * B * B * B * B * B
> +
> +unsigned
> +foo (unsigned n)
> +{
> + return C * B * B * A * n * n * n * n * n;
> +}
>
> Jakub
>
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-01-11 8:17 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-01-10 14:56 [PATCH] reassoc: Reassociate integral multiplies [PR95867[ Jakub Jelinek
2021-01-11 8:17 ` 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).