[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 --- Comment #11 from Yvan Roux --- Author: yroux Date: Thu Mar 5 14:28:05 2015 New Revision: 221216 URL: https://gcc.gnu.org/viewcvs?rev=221216&root=gcc&view=rev Log: gcc/ 2015-03-05 Yvan Roux Backport from trunk r212011, r214942, r214957, r215012, r215016, r218115, r218733, r218746, r220491. 2015-02-06 Sebastian Pop Brian Rzycki PR tree-optimization/64878 * tree-ssa-threadedge.c: Include tree-ssa-loop.h. (fsm_find_control_statement_thread_paths): Add parameter seen_loop_phi. Stop recursion at loop phi nodes after having visited a loop phi node. 2014-12-15 Richard Biener PR middle-end/64246 * cfgloop.c (mark_loop_for_removal): Make safe against multiple invocations on the same loop. 2014-12-15 Richard Biener PR tree-optimization/64284 * tree-ssa-threadupdate.c (duplicate_seme_region): Mark the loop for removal if we copied the loop header. 2014-11-27 Richard Biener PR tree-optimization/64083 * tree-ssa-threadupdate.c (thread_through_all_blocks): Do not forcibly mark loop for removal the wrong way. 2014-09-08 Richard Biener PR ipa/63196 * tree-inline.c (copy_loops): The source loop header should always be non-NULL. (tree_function_versioning): If loops need fixup after removing unreachable blocks fix them. * omp-low.c (simd_clone_adjust): Do not add incr block to loop under construction. 2014-09-08 Richard Biener PR bootstrap/63204 * cfgloop.c (mark_loop_for_removal): Track former header unconditionally. * cfgloop.h (struct loop): Add former_header member unconditionally. * loop-init.c (fix_loop_structure): Enable bogus loop removal diagnostic unconditionally. 2014-09-05 Richard Biener * cfgloop.c (mark_loop_for_removal): Record former header when ENABLE_CHECKING. * cfgloop.h (strut loop): Add former_header member when ENABLE_CHECKING. * loop-init.c (fix_loop_structure): Sanity check loops marked for removal if they re-appeared. 2014-09-05 Richard Biener * cfgloop.c (mark_loop_for_removal): New function. * cfgloop.h (mark_loop_for_removal): Declare. * cfghooks.c (delete_basic_block): Use mark_loop_for_removal. (merge_blocks): Likewise. (duplicate_block): Likewise. * except.c (sjlj_emit_dispatch_table): Likewise. * tree-eh.c (cleanup_empty_eh_merge_phis): Likewise. * tree-ssa-threadupdate.c (ssa_redirect_edges): Likewise. (thread_through_loop_header): Likewise. 2014-06-26 Richard Biener PR tree-optimization/61607 * tree-ssa-threadupdate.c (ssa_redirect_edges): Cancel the loop if we redirected its latch edge. (thread_block_1): Do not cancel loops prematurely. gcc/testsuite/ 2015-03-05 Yvan Roux Backport from trunk r218115, r218733, r218746, r220491. 2015-02-06 Sebastian Pop Brian Rzycki PR tree-optimization/64878 * testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c: New. 2014-12-15 Richard Biener PR middle-end/64246 * gnat.dg/opt46.adb: New testcase. * gnat.dg/opt46.ads: Likewise. * gnat.dg/opt46_pkg.adb: Likewise. * gnat.dg/opt46_pkg.ads: Likewise. 2014-12-15 Richard Biener PR tree-optimization/64284 * gcc.dg/torture/pr64284.c: New testcase. 2014-11-27 Richard Biener PR tree-optimization/64083 * gcc.dg/torture/pr64083.c: New testcase. Added: branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64083.c branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64284.c branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46.adb branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46.ads branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46_pkg.adb branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46_pkg.ads Modified: branches/linaro/gcc-4_9-branch/gcc/ChangeLog.linaro branches/linaro/gcc-4_9-branch/gcc/cfghooks.c branches/linaro/gcc-4_9-branch/gcc/cfgloop.c branches/linaro/gcc-4_9-branch/gcc/cfgloop.h branches/linaro/gcc-4_9-branch/gcc/except.c branches/linaro/gcc-4_9-branch/gcc/loop-init.c branches/linaro/gcc-4_9-branch/gcc/omp-low.c branches/linaro/gcc-4_9-branch/gcc/testsuite/ChangeLog.linaro branches/linaro/gcc-4_9-branch/gcc/tree-eh.c branches/linaro/gcc-4_9-branch/gcc/tree-inline.c branches/linaro/gcc-4_9-branch/gcc/tree-ssa-threadedge.c branches/linaro/gcc-4_9-branch/gcc/tree-ssa-threadupdate.c
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 Jeffrey A. Law changed: What|Removed |Added Status|UNCONFIRMED |RESOLVED Resolution|--- |FIXED --- Comment #10 from Jeffrey A. Law --- Fixed by change to follow SSA_NAME_VALUE chains on the trunk + richi's improvements.
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 --- Comment #9 from Jeffrey A. Law --- So, the length of the SSA_NAME_VALUE chains is pretty much as expected. The overwhelming majority of the time there is nothing in the SSA_NAME_VALUE chain or a single entry. Then there's a very small percentage with a length of 2 and roughly the same very small percentage that have a loop. So we can reasonably iterate over the chain and break if we hit > 2 entries in the chain.
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 --- Comment #8 from Jeffrey A. Law --- FWIW, I vaguely recall experimenting with following the SSA_NAME_VALUE chains in the past and having problems with cycles. IIRC we can get cycles from things like recording equivalences created by equality tests. We could put a (small) upper limit on the number of SSA_NAME_VALUEs we walk. I'd expect the vast majority of the time we'd be walking just one node. I guess that's worth investigating.
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 Jeffrey A. Law changed: What|Removed |Added CC||law at redhat dot com --- Comment #7 from Jeffrey A. Law --- In my testing, the missed thread is due to not following the chain of SSA_NAME_VALUEs. We ought to easily discover that the two conditionals outside the loop are in fact equivalent and fully threadable. With a quick hack to follow the chain of values we're able to trivially discover both of the interesting jump threading opportunities: k.c.079t.dom1: Registering jump thread: (6, 7) incoming edge; (7, 8) normal; k.c.079t.dom1: Registering jump thread: (5, 7) incoming edge; (7, 9) normal;
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607
--- Comment #6 from Richard Biener ---
The bogus loop cancelling is fixed as well as the equivalence recording. Still
DOM does
Registering jump thread: (3, 4) incoming edge; (4, 5) joiner; (5, 6)
normal;
Registering jump thread: (5, 7) incoming edge; (7, 9) normal;
Registering jump thread: (2, 4) incoming edge; (4, 5) joiner; (5, 7)
normal;
Cancelling jump thread: (2, 4) incoming edge; (4, 5) joiner; (5, 7) normal;
Threaded jump 5 --> 7 to 10
with result
:
# inter_I_lsm.3_24 = PHI
# inter_I_lsm.4_25 = PHI
# inter_I_lsm.5_26 = PHI
# inter_I_lsm.6_27 = PHI
if (inter_I_lsm.4_25 != 0)
goto ;
else
goto ;
:
inter[0] = inter_I_lsm.3_24;
:
if (inter_I_lsm.4_25 != 0)
goto ;
else
goto ;
:
inter[1] = inter_I_lsm.5_26;
:
foo (&inter);
inter ={v} {CLOBBER};
return;
:
goto ;
but no attempt at threading of
(5, 6) incoming edge -> (6->7) joiner -> (7 -> 8) normal
VRP simplfies the conditional to true afterwards - so maybe this is just
a missed simplification-after-threading in DOM? Without VRP the
redundant conditional stays. It still looks like a trivial missing thing to
adjust the jump we thread through ...?
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 --- Comment #5 from Richard Biener --- Author: rguenth Date: Thu Jun 26 11:29:34 2014 New Revision: 212026 URL: https://gcc.gnu.org/viewcvs?rev=212026&root=gcc&view=rev Log: 2014-06-26 Richard Biener PR tree-optimization/61607 * tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust comment explaining why we restrict copies on loop depth. * tree-ssa-dom.c (cprop_operand): Remove restriction on on loop depth. (record_equivalences_from_phis): Instead add it here. * gcc.dg/tree-ssa/ssa-dom-thread-5.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-5.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-copy.c trunk/gcc/tree-ssa-dom.c
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 --- Comment #4 from Richard Biener --- Author: rguenth Date: Thu Jun 26 07:44:10 2014 New Revision: 212011 URL: https://gcc.gnu.org/viewcvs?rev=212011&root=gcc&view=rev Log: 2014-06-26 Richard Biener PR tree-optimization/61607 * tree-ssa-threadupdate.c (ssa_redirect_edges): Cancel the loop if we redirected its latch edge. (thread_block_1): Do not cancel loops prematurely. Modified: trunk/gcc/ChangeLog trunk/gcc/tree-ssa-threadupdate.c
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607
--- Comment #3 from Richard Biener ---
Like with
Index: gcc/tree-ssa-threadupdate.c
===
--- gcc/tree-ssa-threadupdate.c (revision 211969)
+++ gcc/tree-ssa-threadupdate.c (working copy)
@@ -764,6 +764,14 @@ ssa_redirect_edges (struct redirection_d
if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;
+ /* If we redirect a loop latch edge cancel its loop. */
+ if (e->src == e->src->loop_father->latch)
+ {
+ e->src->loop_father->header = NULL;
+ e->src->loop_father->latch = NULL;
+ loops_state_set (LOOPS_NEED_FIXUP);
+ }
+
/* Redirect the incoming edge (possibly to the joiner block) to the
appropriate duplicate block. */
e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
@@ -853,32 +861,6 @@ thread_block_1 (basic_block bb, bool nol
redirection_data
= new hash_table (EDGE_COUNT (bb->succs));
- /* If we thread the latch of the loop to its exit, the loop ceases to
- exist. Make sure we do not restrict ourselves in order to preserve
- this loop. */
- if (loop->header == bb)
-{
- e = loop_latch_edge (loop);
- vec *path = THREAD_PATH (e);
-
- if (path
- && (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && joiners)
- || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && !joiners)))
- {
- for (unsigned int i = 1; i < path->length (); i++)
- {
- edge e2 = (*path)[i]->e;
-
- if (loop_exit_edge_p (loop, e2))
- {
- loop->header = NULL;
- loop->latch = NULL;
- loops_state_set (LOOPS_NEED_FIXUP);
- }
- }
- }
-}
-
/* Record each unique threaded destination into a hash table for
efficient lookups. */
FOR_EACH_EDGE (e, ei, bb->preds)
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607
--- Comment #2 from Richard Biener ---
With the propagation limitation removed we get
Registering jump thread: (2, 4) incoming edge; (4, 5) joiner; (5, 7)
normal;
Cancelling jump thread: (2, 4) incoming edge; (4, 5) joiner; (5, 7) normal;
Jump threading proved probability of edge 7->9 too small (it is 3900, should be
5000).
Threaded jump 5 --> 7 to 10
fix_loop_structure: removing loop 1
flow_loops_find: discovered new loop 2 with header 4
:
# inter0p_13 = PHI
# inter1p_14 = PHI
if (inter0p_2 != 0)
goto ;
else
goto ;
:
inter[0] = 1;
:
if (inter0p_2 != 0)
goto ;
else
goto ;
:
inter[1] = 1;
:
foo (&inter);
inter ={v} {CLOBBER};
return;
:
goto ;
that still misses the threading of the true path. And it still destroys
loop info from:
static bool
thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
{
...
/* If we thread the latch of the loop to its exit, the loop ceases to
exist. Make sure we do not restrict ourselves in order to preserve
this loop. */
if (loop->header == bb)
{
e = loop_latch_edge (loop);
vec *path = THREAD_PATH (e);
if (path
&& (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && joiners)
|| ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && !joiners)))
{
for (unsigned int i = 1; i < path->length (); i++)
{
edge e2 = (*path)[i]->e;
if (loop_exit_edge_p (loop, e2))
{
loop->header = NULL;
loop->latch = NULL;
loops_state_set (LOOPS_NEED_FIXUP);
but it seems we cancel the threading later...
(gdb)
913 delete_jump_thread_path (path);
so it would be better if we destroyed the loop only if necessary
(I would have expected the actual edge redirection code takes care of that).
Cancelling loops unnecessarily is very bad.
[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607 --- Comment #1 from Richard Biener --- Optimizing block #5 1>>> COND 1 = i_1 ge_expr R_6(D) 1>>> COND 0 = i_1 lt_expr R_6(D) LKUP STMT inter0p_13 = PHI inter0p_13 = PHI 2>>> STMT inter0p_13 = PHI inter0p_13 = PHI LKUP STMT inter1p_14 = PHI inter1p_14 = PHI FIND: inter0p_2 0>>> COPY inter1p_14 = inter0p_2 At least record_equivalences_from_phis sets the SSA value of both to inter0p_2. But we don't propagate inter0p_2 into the conditionals because of /* Do not propagate copies if the propagated value is at a deeper loop depth than the propagatee. Otherwise, this may move loop variant variables outside of their loops and prevent coalescing opportunities. If the value was loop invariant, it will be hoisted by LICM and exposed for copy propagation. */ if (loop_depth_of_name (val) > loop_depth_of_name (op)) return; as inter0p_2 is defined inside the loop. Note that we don't replace inter1p_14 by inter0p_13 either because we recorded inter0p_2 for that as well ... So it seems the above limitation should be enforced in a different way (or removed). I don't get what the comment is after anyway... both FRE and PRE don't care and do the propagation (and the CSE).
