public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug tree-optimization/57186] New: implement load sinking in loops @ 2013-05-06 14:50 ebotcazou at gcc dot gnu.org 2013-05-06 14:51 ` [Bug tree-optimization/57186] " ebotcazou at gcc dot gnu.org ` (4 more replies) 0 siblings, 5 replies; 6+ messages in thread From: ebotcazou at gcc dot gnu.org @ 2013-05-06 14:50 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57186 Bug #: 57186 Summary: implement load sinking in loops Classification: Unclassified Product: gcc Version: 4.9.0 URL: http://gcc.gnu.org/ml/gcc-patches/2012-10/msg00742.htm l Status: UNCONFIRMED Keywords: missed-optimization Severity: enhancement Priority: P3 Component: tree-optimization AssignedTo: unassigned@gcc.gnu.org ReportedBy: ebotcazou@gcc.gnu.org Created attachment 30040 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30040 Original implementation Even at -O3, the compiler doesn't figure out that the following loop is dumb: #define SIZE 64 int foo (int v[]) { int r; for (i = 0; i < SIZE; i++) r = v[i]; return r; } This isn't entirely unexpected, as it probably matters only for (slightly) pathological cases. The attached patch nevertheless implements a form of load sinking in loops so as to optimize these cases. It's combined with invariant motion to optimize: int foo (int v[], int a) { int r, i; for (i = 0; i < SIZE; i++) r = v[i] + a; return r; } and with store sinking to optimize: int foo (int v1[], int v2[]) { int r[SIZE]; int i, j; for (j = 0; j < SIZE; j++) for (i = 0; i < SIZE; i++) r[j] = v1[j] + v2[i]; return r[SIZE - 1]; } The optimization is enabled at -O2 in the patch for measurement purposes but, given how rarely it triggers (e.g. exactly 10 occurrences in a GCC bootstrap, compiler-only, all languages except Go), it's probably best suited to -O3. It also comes with 3 testcases. ^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/57186] implement load sinking in loops 2013-05-06 14:50 [Bug tree-optimization/57186] New: implement load sinking in loops ebotcazou at gcc dot gnu.org @ 2013-05-06 14:51 ` ebotcazou at gcc dot gnu.org 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org ` (3 subsequent siblings) 4 siblings, 0 replies; 6+ messages in thread From: ebotcazou at gcc dot gnu.org @ 2013-05-06 14:51 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57186 --- Comment #1 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2013-05-06 14:51:30 UTC --- Created attachment 30041 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30041 Testcase #1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/57186] implement load sinking in loops 2013-05-06 14:50 [Bug tree-optimization/57186] New: implement load sinking in loops ebotcazou at gcc dot gnu.org 2013-05-06 14:51 ` [Bug tree-optimization/57186] " ebotcazou at gcc dot gnu.org @ 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org ` (2 subsequent siblings) 4 siblings, 0 replies; 6+ messages in thread From: ebotcazou at gcc dot gnu.org @ 2013-05-06 14:52 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57186 --- Comment #2 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2013-05-06 14:51:58 UTC --- Created attachment 30042 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30042 Testcase #2 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/57186] implement load sinking in loops 2013-05-06 14:50 [Bug tree-optimization/57186] New: implement load sinking in loops ebotcazou at gcc dot gnu.org 2013-05-06 14:51 ` [Bug tree-optimization/57186] " ebotcazou at gcc dot gnu.org 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org @ 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org 2013-05-07 9:02 ` rguenth at gcc dot gnu.org 2021-07-26 22:09 ` pinskia at gcc dot gnu.org 4 siblings, 0 replies; 6+ messages in thread From: ebotcazou at gcc dot gnu.org @ 2013-05-06 14:52 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57186 --- Comment #3 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2013-05-06 14:52:25 UTC --- Created attachment 30043 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30043 Testcase #3 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/57186] implement load sinking in loops 2013-05-06 14:50 [Bug tree-optimization/57186] New: implement load sinking in loops ebotcazou at gcc dot gnu.org ` (2 preceding siblings ...) 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org @ 2013-05-07 9:02 ` rguenth at gcc dot gnu.org 2021-07-26 22:09 ` pinskia at gcc dot gnu.org 4 siblings, 0 replies; 6+ messages in thread From: rguenth at gcc dot gnu.org @ 2013-05-07 9:02 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57186 Richard Biener <rguenth at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|UNCONFIRMED |NEW Last reconfirmed| |2013-05-07 CC| |rguenth at gcc dot gnu.org Ever Confirmed|0 |1 --- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2013-05-07 09:02:48 UTC --- In theory we have the SCCP patch to address at least case #1. It looks at loop exit PHIs and tries to replace them with the overall effect of the loop (using SCEV analysis, which is why it fails for loads). <bb 4>: # i_15 = PHI <i_10(3), 0(2)> _4 = (long unsigned int) i_15; _5 = _4 * 4; _7 = v_6(D) + _5; r_9 = *_7; i_10 = i_15 + 1; if (i_10 != 64) goto <bb 3>; else goto <bb 5>; <bb 5>: # r_20 = PHI <r_9(4)> the complication with handling the above in existing passes (for example code sinking) is that the final value of _7 is needed to sink the dependent computations. So I think what SCCP should do here is look at the single-use chain from the defs of r_20 and analyze the evolution of the dependent loop variant SSA names, performing sinking of the dependencies as well. Conveniently LIM runs before SCCP and performs the necessary store sinking to allow handling of the last case. ^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/57186] implement load sinking in loops 2013-05-06 14:50 [Bug tree-optimization/57186] New: implement load sinking in loops ebotcazou at gcc dot gnu.org ` (3 preceding siblings ...) 2013-05-07 9:02 ` rguenth at gcc dot gnu.org @ 2021-07-26 22:09 ` pinskia at gcc dot gnu.org 4 siblings, 0 replies; 6+ messages in thread From: pinskia at gcc dot gnu.org @ 2021-07-26 22:09 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57186 Andrew Pinski <pinskia at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Target Milestone|--- |5.0 Resolution|--- |FIXED Status|NEW |RESOLVED --- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> --- Fixed in GCC 5 by r5-1146 . ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2021-07-26 22:09 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-05-06 14:50 [Bug tree-optimization/57186] New: implement load sinking in loops ebotcazou at gcc dot gnu.org 2013-05-06 14:51 ` [Bug tree-optimization/57186] " ebotcazou at gcc dot gnu.org 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org 2013-05-06 14:52 ` ebotcazou at gcc dot gnu.org 2013-05-07 9:02 ` rguenth at gcc dot gnu.org 2021-07-26 22: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).