public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t
@ 2020-06-24 12:40 gabravier at gmail dot com
2020-06-24 12:46 ` [Bug tree-optimization/95867] " gabravier at gmail dot com
` (6 more replies)
0 siblings, 7 replies; 8+ messages in thread
From: gabravier at gmail dot com @ 2020-06-24 12:40 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
Bug ID: 95867
Summary: Failure to optimize successive multiplications of
___uint128_t
Product: gcc
Version: 11.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: gabravier at gmail dot com
Target Milestone: ---
__uint128_t f(__uint128_t n)
{
return
n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n*n;
}
This can be optimized to
__uint128_t f2(__uint128_t n)
{
__uint128_t tmp = n * n;
tmp = (tmp * tmp) * n;
tmp *= tmp;
tmp *= tmp;
tmp *= tmp;
tmp = (tmp * tmp) * n;
tmp = (tmp * tmp) * n;
tmp *= tmp;
return (tmp * n) * tmp;
}
This transformation is done by LLVM, but not by GCC.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
@ 2020-06-24 12:46 ` gabravier at gmail dot com
2020-06-24 13:42 ` jakub at gcc dot gnu.org
` (5 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: gabravier at gmail dot com @ 2020-06-24 12:46 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
--- Comment #1 from Gabriel Ravier <gabravier at gmail dot com> ---
PS : Of course this can be optimized in the general case, I was only giving an
example here, I wouldn't want only the pattern of 653 successive
multiplications to be optimized
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
2020-06-24 12:46 ` [Bug tree-optimization/95867] " gabravier at gmail dot com
@ 2020-06-24 13:42 ` jakub at gcc dot gnu.org
2020-06-24 13:58 ` rguenth at gcc dot gnu.org
` (4 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: jakub at gcc dot gnu.org @ 2020-06-24 13:42 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jakub at gcc dot gnu.org
--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Not really __uint128_t related. Since PR18589 we perform such optimizations on
floating point multiply, and on signed integers we punt on reassociation
because of the undefined signed overflow issues (the proposal to do a very late
reassoc that would essentially turn on -fwrapv from that point onwards or at
least turn rewritten expressions into unsigned ones has not materialized yet),
but for unsigned integral types we could indeed replace those with the minimal
number of multiplications.
Or alternatively we could do that in forwprop1, which can handle similar case
for addition into multiplications, though I guess only reassoc will be able to
handle it if it isn't just one variable as the multiplication operands, but
several.
return x * x * y * z * x * z * x * w * w * u * x * z * y * w * u * x * x * w *
w * w;
etc.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
2020-06-24 12:46 ` [Bug tree-optimization/95867] " gabravier at gmail dot com
2020-06-24 13:42 ` jakub at gcc dot gnu.org
@ 2020-06-24 13:58 ` rguenth at gcc dot gnu.org
2020-06-24 14:02 ` rguenth at gcc dot gnu.org
` (3 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2020-06-24 13:58 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Ever confirmed|0 |1
Status|UNCONFIRMED |NEW
Last reconfirmed| |2020-06-24
Keywords| |missed-optimization
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
` (2 preceding siblings ...)
2020-06-24 13:58 ` rguenth at gcc dot gnu.org
@ 2020-06-24 14:02 ` rguenth at gcc dot gnu.org
2021-01-09 18:50 ` jakub at gcc dot gnu.org
` (2 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2020-06-24 14:02 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's done through POWI internally, I guess we could open the internal function
to also operate on integers...
As for overflow for a multiplication chain of the same operand there shouldn't
be any issue, but not sure how far we should go with signed arithmetic support
early (for the late reassoc the idea is still to set flag_wrapv = 1).
We could carefully handle some cases by ensuring to only perform
"safe" linearization and for the resulting chains adjust operand sorting
to only perform "safe" commutations (basically not sort, only optimize
trailing constants / cancellations).
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
` (3 preceding siblings ...)
2020-06-24 14:02 ` rguenth at gcc dot gnu.org
@ 2021-01-09 18:50 ` jakub at gcc dot gnu.org
2021-01-11 9:36 ` cvs-commit at gcc dot gnu.org
2021-01-11 9:37 ` jakub at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: jakub at gcc dot gnu.org @ 2021-01-09 18:50 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |ASSIGNED
Assignee|unassigned at gcc dot gnu.org |jakub at gcc dot gnu.org
--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49927
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49927&action=edit
gcc11-pr95867.patch
Untested fix.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
` (4 preceding siblings ...)
2021-01-09 18:50 ` jakub at gcc dot gnu.org
@ 2021-01-11 9:36 ` cvs-commit at gcc dot gnu.org
2021-01-11 9:37 ` jakub at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-01-11 9:36 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:
https://gcc.gnu.org/g:9a6c37e6ae520534993ef76dd45d016c8c86db21
commit r11-6581-g9a6c37e6ae520534993ef76dd45d016c8c86db21
Author: Jakub Jelinek <jakub@redhat.com>
Date: Mon Jan 11 10:35:10 2021 +0100
reassoc: Reassociate integral multiplies [PR95867]
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.
2021-01-11 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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/95867] Failure to optimize successive multiplications of ___uint128_t
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
` (5 preceding siblings ...)
2021-01-11 9:36 ` cvs-commit at gcc dot gnu.org
@ 2021-01-11 9:37 ` jakub at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: jakub at gcc dot gnu.org @ 2021-01-11 9:37 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95867
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Resolution|--- |FIXED
Status|ASSIGNED |RESOLVED
--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2021-01-11 9:37 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-06-24 12:40 [Bug tree-optimization/95867] New: Failure to optimize successive multiplications of ___uint128_t gabravier at gmail dot com
2020-06-24 12:46 ` [Bug tree-optimization/95867] " gabravier at gmail dot com
2020-06-24 13:42 ` jakub at gcc dot gnu.org
2020-06-24 13:58 ` rguenth at gcc dot gnu.org
2020-06-24 14:02 ` rguenth at gcc dot gnu.org
2021-01-09 18:50 ` jakub at gcc dot gnu.org
2021-01-11 9:36 ` cvs-commit at gcc dot gnu.org
2021-01-11 9:37 ` jakub at gcc dot gnu.org
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).