public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c/65855] New: missing optimization: triangular numbers
@ 2015-04-23 4:52 shawn at churchofgit dot com
2015-04-23 5:32 ` [Bug middle-end/65855] " pinskia at gcc dot gnu.org
` (8 more replies)
0 siblings, 9 replies; 10+ messages in thread
From: shawn at churchofgit dot com @ 2015-04-23 4:52 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Bug ID: 65855
Summary: missing optimization: triangular numbers
Product: gcc
Version: 5.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c
Assignee: unassigned at gcc dot gnu.org
Reporter: shawn at churchofgit dot com
Created attachment 35388
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35388&action=edit
triangle.c
If a register mode is available to avoid multiplication overflow, a loop that
is calculating triangular numbers could be optimized to a multiplication:
uint64_t triangle(uint32_t n) {
uint64_t t = 0;
for (uint64_t i=1;i<=n;i++) t += i;
return t;
}
=>
uint64_t triangle_fast(uint32_t _n) {
uint64_t t, n = _n;
t = (n * (n + 1)) / 2;
return t;
}
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
@ 2015-04-23 5:32 ` pinskia at gcc dot gnu.org
2015-04-25 4:26 ` shawn at churchofgit dot com
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2015-04-23 5:32 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |missed-optimization
Version|5.0 |5.1.0
Severity|normal |enhancement
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
2015-04-23 5:32 ` [Bug middle-end/65855] " pinskia at gcc dot gnu.org
@ 2015-04-25 4:26 ` shawn at churchofgit dot com
2015-04-27 12:11 ` rguenth at gcc dot gnu.org
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: shawn at churchofgit dot com @ 2015-04-25 4:26 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
--- Comment #2 from Shawn Landden <shawn at churchofgit dot com> ---
Created attachment 35399
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35399&action=edit
triange, 64-bit version
This can also work with 128-bit multiple of course as well.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
2015-04-23 5:32 ` [Bug middle-end/65855] " pinskia at gcc dot gnu.org
2015-04-25 4:26 ` shawn at churchofgit dot com
@ 2015-04-27 12:11 ` rguenth at gcc dot gnu.org
2015-10-23 12:05 ` rguenth at gcc dot gnu.org
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: rguenth at gcc dot gnu.org @ 2015-04-27 12:11 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |ktietz at gcc dot gnu.org,
| |rguenth at gcc dot gnu.org
--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
shorten_compare in the C frontend family performs the (long unsigned int)
n_3(D) != 18446744073709551615 simplification. Nothing in fold-const.c or
match.pd does.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
` (2 preceding siblings ...)
2015-04-27 12:11 ` rguenth at gcc dot gnu.org
@ 2015-10-23 12:05 ` rguenth at gcc dot gnu.org
2015-10-23 12:42 ` rguenth at gcc dot gnu.org
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: rguenth at gcc dot gnu.org @ 2015-10-23 12:05 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
match.pd now has the desired simplification. So we run into
(chrec_apply
(varying_loop = 1
)
(chrec = {1, +, {2, +, 1}_1}_1)
(x = (long unsigned int) n_3(D) + 18446744073709551615)
(res = scev_not_known))
the question is if we can handle this kind of CHREC in chrec_apply generally
or not.
{ x, +, { y, +, C}_N }_N
specifically. I suppose it's simply x + y*X + C*X*(X+1)/2.
Now the question is whether it's generally profitable to handle this. We'll
see.
I have a patch that produces
(chrec_apply
(varying_loop = 1
)
(chrec = {1, +, {2, +, 1}_1}_1)
(x = (long unsigned int) n_3(D) + 18446744073709551615)
(res = (((long unsigned int) n_3(D) * ((long unsigned int) n_3(D) +
18446744073709551615)) /[ex] 2 + (uint64_t) n_3(D) * 2) +
18446744073709551615))
but that's somehow off.
Index: gcc/tree-chrec.c
===================================================================
--- gcc/tree-chrec.c (revision 229233)
+++ gcc/tree-chrec.c (working copy)
@@ -602,19 +602,37 @@ chrec_apply (unsigned var,
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (evolution_function_is_affine_p (chrec))
+ if (CHREC_VARIABLE (chrec) != var)
+ return build_polynomial_chrec
+ (CHREC_VARIABLE (chrec),
+ chrec_apply (var, CHREC_LEFT (chrec), x),
+ chrec_apply (var, CHREC_RIGHT (chrec), x));
+ else if (evolution_function_is_affine_p (chrec))
{
- if (CHREC_VARIABLE (chrec) != var)
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec),
- chrec_apply (var, CHREC_LEFT (chrec), x),
- chrec_apply (var, CHREC_RIGHT (chrec), x));
-
/* "{a, +, b} (x)" -> "a + b*x". */
x = chrec_convert_rhs (type, x, NULL);
res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
}
+ else if (evolution_function_is_affine_p (CHREC_RIGHT (chrec))
+ && CHREC_VARIABLE (CHREC_RIGHT (chrec)) == var)
+ {
+ /* "{a, +, {b, +, c} } (x)" -> "a + b*x + c*x*(x+1)/2". */
+ tree chrecr = CHREC_RIGHT (chrec);
+ x = chrec_convert_rhs (type, x, NULL);
+ /* c*x*(x+1)/2 */
+ res = chrec_fold_plus (type, x, build_int_cst (type, 1));
+ res = chrec_fold_multiply (type, res, x);
+ res = fold_build2 (EXACT_DIV_EXPR, type, res,
+ build_int_cst (type, 2));
+ res = chrec_fold_multiply (type, CHREC_RIGHT (chrecr), res);
+ /* + b*x */
+ res = chrec_fold_plus (type, res,
+ chrec_fold_multiply (type, x,
+ CHREC_LEFT (chrecr)));
+ /* + a */
+ res = chrec_fold_plus (type, res, CHREC_LEFT (chrec));
+ }
else if (TREE_CODE (x) == INTEGER_CST
&& tree_int_cst_sgn (x) == 1)
/* testsuite/.../ssa-chrec-38.c. */
produces 76 for n == 11 and 298 for n == 23. Testcase that works with SCCP
disabled:
extern void abort (void);
typedef __UINT64_TYPE__ uint64_t;
typedef __UINT32_TYPE__ uint32_t;
uint64_t __attribute__((noinline,noclone))
triangle(uint32_t n)
{
uint64_t t = 0;
for (uint64_t i=1;i<=n;i++) t += i;
return t;
}
int main()
{
uint64_t t11 = triangle (11);
uint64_t t23 = triangle (23);
if (t11 != 66 || t23 != 276)
abort ();
return 0;
}
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
` (3 preceding siblings ...)
2015-10-23 12:05 ` rguenth at gcc dot gnu.org
@ 2015-10-23 12:42 ` rguenth at gcc dot gnu.org
2021-08-07 6:42 ` [Bug middle-end/65855] SCEV / SCCP " pinskia at gcc dot gnu.org
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: rguenth at gcc dot gnu.org @ 2015-10-23 12:42 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |spop at gcc dot gnu.org
--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Looks like SCEV analysis is broken for this case.
<bb 3>:
# t_11 = PHI <0(5), t_5(7)>
# i_13 = PHI <1(5), i_6(7)>
t_5 = t_11 + i_13;
i_6 = i_13 + 1;
if (i_6 <= _10)
goto <bb 7>;
else
goto <bb 8>;
<bb 7>:
goto <bb 3>;
<bb 8>:
# t_2 = PHI <t_5(3)>
t_11 = { 0, +, i_13 }_1 (ok)
i_13 = {1, +, 1}_1 (ok)
(instantiate_scev
(instantiate_below = 5)
(evolution_loop = 1)
(chrec = {0, +, i_13}_1)
(analyze_scalar_evolution
(loop_nb = 1)
(scalar = i_13)
(get_scalar_evolution
(scalar = i_13)
(scalar_evolution = {1, +, 1}_1))
(set_scalar_evolution
instantiated_below = 5
(scalar = i_13)
(scalar_evolution = {1, +, 1}_1))
)
(res = {0, +, {1, +, 1}_1}_1))
(instantiate_scev
(instantiate_below = 5)
(evolution_loop = 1)
(chrec = {1, +, 1}_1)
(res = {1, +, 1}_1))
(set_scalar_evolution
instantiated_below = 5
(scalar = t_5)
(scalar_evolution = {1, +, {2, +, 1}_1}_1))
not sure where the latter result comes from. It comes from
#10 0x0000000000eac871 in scev_const_prop ()
at /space/rguenther/src/svn/trunk/gcc/tree-scalar-evolution.c:3456
3456 NULL);
(gdb) l
3451 if (!POINTER_TYPE_P (type)
3452 && !INTEGRAL_TYPE_P (type))
3453 continue;
3454
3455 ev = resolve_mixers (loop, analyze_scalar_evolution (loop,
name),
3456 NULL);
analyzing the evolution of t_2.
So we end up looking at t_5 = t_11 + i_13 which is {0, +, {1,+, 1}_1}_1 +
{1,+,1}_1 but that isn't {1, +, {2, +, 1}_1 }_1 as chrec_fold_plus_poly_poly
maintains?
But maybe this kind of CHREC is just ill-formed in the first place?
Sebastian, any ideas here?
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] SCEV / SCCP missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
` (4 preceding siblings ...)
2015-10-23 12:42 ` rguenth at gcc dot gnu.org
@ 2021-08-07 6:42 ` pinskia at gcc dot gnu.org
2021-08-28 23:42 ` pinskia at gcc dot gnu.org
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2021-08-07 6:42 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |dmalcolm at gcc dot gnu.org
--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 82519 has been marked as a duplicate of this bug. ***
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] SCEV / SCCP missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
` (5 preceding siblings ...)
2021-08-07 6:42 ` [Bug middle-end/65855] SCEV / SCCP " pinskia at gcc dot gnu.org
@ 2021-08-28 23:42 ` pinskia at gcc dot gnu.org
2023-06-10 16:02 ` pinskia at gcc dot gnu.org
2023-11-22 0:09 ` pinskia at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2021-08-28 23:42 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jak@jak-linux.org
--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 46186 has been marked as a duplicate of this bug. ***
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] SCEV / SCCP missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
` (6 preceding siblings ...)
2021-08-28 23:42 ` pinskia at gcc dot gnu.org
@ 2023-06-10 16:02 ` pinskia at gcc dot gnu.org
2023-11-22 0:09 ` pinskia at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-06-10 16:02 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |gabravier at gmail dot com
--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 98960 has been marked as a duplicate of this bug. ***
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/65855] SCEV / SCCP missing optimization: triangular numbers
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
` (7 preceding siblings ...)
2023-06-10 16:02 ` pinskia at gcc dot gnu.org
@ 2023-11-22 0:09 ` pinskia at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-11-22 0:09 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65855
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |goon.pri.low at gmail dot com
--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 112663 has been marked as a duplicate of this bug. ***
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2023-11-22 0:09 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-04-23 4:52 [Bug c/65855] New: missing optimization: triangular numbers shawn at churchofgit dot com
2015-04-23 5:32 ` [Bug middle-end/65855] " pinskia at gcc dot gnu.org
2015-04-25 4:26 ` shawn at churchofgit dot com
2015-04-27 12:11 ` rguenth at gcc dot gnu.org
2015-10-23 12:05 ` rguenth at gcc dot gnu.org
2015-10-23 12:42 ` rguenth at gcc dot gnu.org
2021-08-07 6:42 ` [Bug middle-end/65855] SCEV / SCCP " pinskia at gcc dot gnu.org
2021-08-28 23:42 ` pinskia at gcc dot gnu.org
2023-06-10 16:02 ` pinskia at gcc dot gnu.org
2023-11-22 0:09 ` pinskia 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).