I happen to have a patch for PR55964 around - preparatory work
to make loop distribution (and vectorization) handle nested loops.
It mostly kills the broken way loop distribution copies loops
(which is where we ICE in this PR). So instead of trying to
make that old logic slightly less broken I consider to simply
apply this work now ... (I've posted this before in December).
I'm re-bootstrapping and testing this on x86_64-unknown-linux-gnu.
So ... ok at this stage?
Thanks,
Richard.
2013-01-14 Richard Biener <rguent...@suse.de>
PR tree-optimization/55964
* tree-flow.h (rename_variables_in_loop): Remove.
(rename_variables_in_bb): Likewise.
* tree-loop-distribution.c (update_phis_for_loop_copy): Remove.
(copy_loop_before): Adjust and delete update-ssa status.
* tree-vect-loop-manip.c (rename_variables_in_bb): Make static.
(rename_variables_in_bb): Likewise. Properly walk over
predecessors.
(rename_variables_in_loop): Remove.
(slpeel_update_phis_for_duplicate_loop): Likewise.
(slpeel_tree_duplicate_loop_to_edge_cfg): Handle nested loops,
use available cfg machinery instead of duplicating it.
Update PHI nodes and perform poor-mans SSA update here.
(slpeel_tree_peel_loop_to_edge): Adjust.
* gcc.dg/torture/pr55964.c: New testcase.
Index: trunk/gcc/tree-loop-distribution.c
===================================================================
*** trunk.orig/gcc/tree-loop-distribution.c 2013-01-14 16:44:58.000000000
+0100
--- trunk/gcc/tree-loop-distribution.c 2013-01-14 16:45:07.609800223 +0100
*************** stmt_has_scalar_dependences_outside_loop
*** 151,208 ****
return false;
}
- /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
- ORIG_LOOP. */
-
- static void
- update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
- {
- tree new_ssa_name;
- gimple_stmt_iterator si_new, si_orig;
- edge orig_loop_latch = loop_latch_edge (orig_loop);
- edge orig_entry_e = loop_preheader_edge (orig_loop);
- edge new_loop_entry_e = loop_preheader_edge (new_loop);
-
- /* Scan the phis in the headers of the old and new loops
- (they are organized in exactly the same order). */
- for (si_new = gsi_start_phis (new_loop->header),
- si_orig = gsi_start_phis (orig_loop->header);
- !gsi_end_p (si_new) && !gsi_end_p (si_orig);
- gsi_next (&si_new), gsi_next (&si_orig))
- {
- tree def;
- source_location locus;
- gimple phi_new = gsi_stmt (si_new);
- gimple phi_orig = gsi_stmt (si_orig);
-
- /* Add the first phi argument for the phi in NEW_LOOP (the one
- associated with the entry of NEW_LOOP) */
- def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
- locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e);
- add_phi_arg (phi_new, def, new_loop_entry_e, locus);
-
- /* Add the second phi argument for the phi in NEW_LOOP (the one
- associated with the latch of NEW_LOOP) */
- def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
- locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
-
- if (TREE_CODE (def) == SSA_NAME)
- {
- new_ssa_name = get_current_def (def);
-
- if (!new_ssa_name)
- /* This only happens if there are no definitions inside the
- loop. Use the the invariant in the new loop as is. */
- new_ssa_name = def;
- }
- else
- /* Could be an integer. */
- new_ssa_name = def;
-
- add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
- }
- }
-
/* Return a copy of LOOP placed before LOOP. */
static struct loop *
--- 151,156 ----
*************** copy_loop_before (struct loop *loop)
*** 215,223 ****
res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
gcc_assert (res != NULL);
free_original_copy_tables ();
!
! update_phis_for_loop_copy (loop, res);
! rename_variables_in_loop (res);
return res;
}
--- 163,169 ----
res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
gcc_assert (res != NULL);
free_original_copy_tables ();
! delete_update_ssa ();
return res;
}
Index: trunk/gcc/tree-flow.h
===================================================================
*** trunk.orig/gcc/tree-flow.h 2013-01-14 16:44:58.000000000 +0100
--- trunk/gcc/tree-flow.h 2013-01-14 16:45:07.610800234 +0100
*************** bool gimple_duplicate_loop_to_header_edg
*** 654,661 ****
edge, vec<edge> *,
int);
struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *, edge);
- void rename_variables_in_loop (struct loop *);
- void rename_variables_in_bb (basic_block bb);
tree expand_simple_operations (tree);
void substitute_in_loop_info (struct loop *, tree, tree);
edge single_dom_exit (struct loop *);
--- 654,659 ----
Index: trunk/gcc/tree-vect-loop-manip.c
===================================================================
*** trunk.orig/gcc/tree-vect-loop-manip.c 2013-01-14 16:44:58.000000000
+0100
--- trunk/gcc/tree-vect-loop-manip.c 2013-01-14 16:45:07.612800256 +0100
*************** rename_use_op (use_operand_p op_p)
*** 67,73 ****
/* Renames the variables in basic block BB. */
! void
rename_variables_in_bb (basic_block bb)
{
gimple_stmt_iterator gsi;
--- 67,73 ----
/* Renames the variables in basic block BB. */
! static void
rename_variables_in_bb (basic_block bb)
{
gimple_stmt_iterator gsi;
*************** rename_variables_in_bb (basic_block bb)
*** 85,116 ****
rename_use_op (use_p);
}
! FOR_EACH_EDGE (e, ei, bb->succs)
{
! if (!flow_bb_inside_loop_p (loop, e->dest))
continue;
! for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
}
}
- /* Renames variables in new generated LOOP. */
-
- void
- rename_variables_in_loop (struct loop *loop)
- {
- unsigned i;
- basic_block *bbs;
-
- bbs = get_loop_body (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- rename_variables_in_bb (bbs[i]);
-
- free (bbs);
- }
-
typedef struct
{
tree from, to;
--- 85,100 ----
rename_use_op (use_p);
}
! FOR_EACH_EDGE (e, ei, bb->preds)
{
! if (!flow_bb_inside_loop_p (loop, e->src))
continue;
! for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
}
}
typedef struct
{
tree from, to;
*************** adjust_phi_and_debug_stmts (gimple updat
*** 234,334 ****
}
- /* Update the PHI nodes of NEW_LOOP.
-
- NEW_LOOP is a duplicate of ORIG_LOOP.
- AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
- AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
- executes before it. */
-
- static void
- slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
- struct loop *new_loop, bool after)
- {
- tree new_ssa_name;
- gimple phi_new, phi_orig;
- tree def;
- edge orig_loop_latch = loop_latch_edge (orig_loop);
- edge orig_entry_e = loop_preheader_edge (orig_loop);
- edge new_loop_exit_e = single_exit (new_loop);
- edge new_loop_entry_e = loop_preheader_edge (new_loop);
- edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
- gimple_stmt_iterator gsi_new, gsi_orig;
-
- /*
- step 1. For each loop-header-phi:
- Add the first phi argument for the phi in NEW_LOOP
- (the one associated with the entry of NEW_LOOP)
-
- step 2. For each loop-header-phi:
- Add the second phi argument for the phi in NEW_LOOP
- (the one associated with the latch of NEW_LOOP)
-
- step 3. Update the phis in the successor block of NEW_LOOP.
-
- case 1: NEW_LOOP was placed before ORIG_LOOP:
- The successor block of NEW_LOOP is the header of ORIG_LOOP.
- Updating the phis in the successor block can therefore be done
- along with the scanning of the loop header phis, because the
- header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
- phi nodes, organized in the same order.
-
- case 2: NEW_LOOP was placed after ORIG_LOOP:
- The successor block of NEW_LOOP is the original exit block of
- ORIG_LOOP - the phis to be updated are the loop-closed-ssa
phis.
- We postpone updating these phis to a later stage (when
- loop guards are added).
- */
-
-
- /* Scan the phis in the headers of the old and new loops
- (they are organized in exactly the same order). */
-
- for (gsi_new = gsi_start_phis (new_loop->header),
- gsi_orig = gsi_start_phis (orig_loop->header);
- !gsi_end_p (gsi_new) && !gsi_end_p (gsi_orig);
- gsi_next (&gsi_new), gsi_next (&gsi_orig))
- {
- source_location locus;
- phi_new = gsi_stmt (gsi_new);
- phi_orig = gsi_stmt (gsi_orig);
-
- /* step 1. */
- def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
- locus = gimple_phi_arg_location_from_edge (phi_orig, entry_arg_e);
- add_phi_arg (phi_new, unshare_expr (def), new_loop_entry_e, locus);
-
- /* step 2. */
- def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
- locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
- if (TREE_CODE (def) != SSA_NAME)
- continue;
-
- new_ssa_name = get_current_def (def);
- if (!new_ssa_name)
- {
- /* This only happens if there are no definitions
- inside the loop. use the phi_result in this case. */
- new_ssa_name = PHI_RESULT (phi_new);
- }
-
- /* An ordinary ssa name defined in the loop. */
- add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
-
- /* Drop any debug references outside the loop, if they would
- become ill-formed SSA. */
- adjust_debug_stmts (def, NULL, single_exit (orig_loop)->dest);
-
- /* step 3 (case 1). */
- if (!after)
- {
- gcc_assert (new_loop_exit_e == orig_entry_e);
- adjust_phi_and_debug_stmts (phi_orig, new_loop_exit_e, new_ssa_name);
- }
- }
- }
-
-
/* Update PHI nodes for a guard of the LOOP.
Input:
--- 218,223 ----
*************** slpeel_tree_duplicate_loop_to_edge_cfg (
*** 809,824 ****
bool at_exit;
bool was_imm_dom;
basic_block exit_dest;
- gimple phi;
- tree phi_arg;
edge exit, new_exit;
- gimple_stmt_iterator gsi;
! at_exit = (e == single_exit (loop));
if (!at_exit && e != loop_preheader_edge (loop))
return NULL;
! bbs = get_loop_body (loop);
/* Check whether duplication is possible. */
if (!can_copy_bbs_p (bbs, loop->num_nodes))
--- 698,712 ----
bool at_exit;
bool was_imm_dom;
basic_block exit_dest;
edge exit, new_exit;
! exit = single_exit (loop);
! at_exit = (e == exit);
if (!at_exit && e != loop_preheader_edge (loop))
return NULL;
! bbs = XNEWVEC (basic_block, loop->num_nodes + 1);
! get_loop_body_with_size (loop, bbs, loop->num_nodes);
/* Check whether duplication is possible. */
if (!can_copy_bbs_p (bbs, loop->num_nodes))
*************** slpeel_tree_duplicate_loop_to_edge_cfg (
*** 829,919 ****
/* Generate new loop structure. */
new_loop = duplicate_loop (loop, loop_outer (loop));
! if (!new_loop)
! {
! free (bbs);
! return NULL;
! }
! exit_dest = single_exit (loop)->dest;
was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
exit_dest) == loop->header ?
true : false);
! new_bbs = XNEWVEC (basic_block, loop->num_nodes);
! exit = single_exit (loop);
! copy_bbs (bbs, loop->num_nodes, new_bbs,
&exit, 1, &new_exit, NULL,
e->src);
! /* Duplicating phi args at exit bbs as coming
! also from exit of duplicated loop. */
! for (gsi = gsi_start_phis (exit_dest); !gsi_end_p (gsi); gsi_next (&gsi))
! {
! phi = gsi_stmt (gsi);
! phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
! if (phi_arg)
! {
! edge new_loop_exit_edge;
! source_location locus;
!
! locus = gimple_phi_arg_location_from_edge (phi, single_exit (loop));
! if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
! new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
! else
! new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
!
! add_phi_arg (phi, phi_arg, new_loop_exit_edge, locus);
! }
! }
if (at_exit) /* Add the loop copy at exit. */
{
! redirect_edge_and_branch_force (e, new_loop->header);
! PENDING_STMT (e) = NULL;
! set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
if (was_imm_dom)
set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
}
else /* Add the copy at entry. */
{
! edge new_exit_e;
! edge entry_e = loop_preheader_edge (loop);
! basic_block preheader = entry_e->src;
!
! if (!flow_bb_inside_loop_p (new_loop,
! EDGE_SUCC (new_loop->header, 0)->dest))
! new_exit_e = EDGE_SUCC (new_loop->header, 0);
! else
! new_exit_e = EDGE_SUCC (new_loop->header, 1);
!
! redirect_edge_and_branch_force (new_exit_e, loop->header);
! PENDING_STMT (new_exit_e) = NULL;
! set_immediate_dominator (CDI_DOMINATORS, loop->header,
! new_exit_e->src);
!
! /* We have to add phi args to the loop->header here as coming
! from new_exit_e edge. */
! for (gsi = gsi_start_phis (loop->header);
! !gsi_end_p (gsi);
! gsi_next (&gsi))
! {
! phi = gsi_stmt (gsi);
! phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
! if (phi_arg)
! add_phi_arg (phi, phi_arg, new_exit_e,
! gimple_phi_arg_location_from_edge (phi, entry_e));
! }
!
! redirect_edge_and_branch_force (entry_e, new_loop->header);
! PENDING_STMT (entry_e) = NULL;
! set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
}
free (new_bbs);
free (bbs);
return new_loop;
}
--- 717,787 ----
/* Generate new loop structure. */
new_loop = duplicate_loop (loop, loop_outer (loop));
! duplicate_subloops (loop, new_loop);
! exit_dest = exit->dest;
was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
exit_dest) == loop->header ?
true : false);
! /* Also copy the pre-header, this avoids jumping through hoops to
! duplicate the loop entry PHI arguments. Create an empty
! pre-header unconditionally for this. */
! basic_block preheader = split_edge (loop_preheader_edge (loop));
! edge entry_e = single_pred_edge (preheader);
! bbs[loop->num_nodes] = preheader;
! new_bbs = XNEWVEC (basic_block, loop->num_nodes + 1);
! copy_bbs (bbs, loop->num_nodes + 1, new_bbs,
&exit, 1, &new_exit, NULL,
e->src);
+ basic_block new_preheader = new_bbs[loop->num_nodes];
! add_phi_args_after_copy (new_bbs, loop->num_nodes + 1, NULL);
if (at_exit) /* Add the loop copy at exit. */
{
! redirect_edge_and_branch_force (e, new_preheader);
! flush_pending_stmts (e);
! set_immediate_dominator (CDI_DOMINATORS, new_preheader, e->src);
if (was_imm_dom)
set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
+
+ /* And remove the non-necessary forwarder again. Keep the other
+ one so we have a proper pre-header for the loop at the exit edge. */
+ redirect_edge_pred (single_succ_edge (preheader), single_pred
(preheader));
+ delete_basic_block (preheader);
+ set_immediate_dominator (CDI_DOMINATORS, loop->header,
+ loop_preheader_edge (loop)->src);
}
else /* Add the copy at entry. */
{
! redirect_edge_and_branch_force (entry_e, new_preheader);
! flush_pending_stmts (entry_e);
! set_immediate_dominator (CDI_DOMINATORS, new_preheader, entry_e->src);
!
! redirect_edge_and_branch_force (new_exit, preheader);
! flush_pending_stmts (new_exit);
! set_immediate_dominator (CDI_DOMINATORS, preheader, new_exit->src);
!
! /* And remove the non-necessary forwarder again. Keep the other
! one so we have a proper pre-header for the loop at the exit edge. */
! redirect_edge_pred (single_succ_edge (new_preheader), single_pred
(new_preheader));
! delete_basic_block (new_preheader);
! set_immediate_dominator (CDI_DOMINATORS, new_loop->header,
! loop_preheader_edge (new_loop)->src);
}
+ for (unsigned i = 0; i < loop->num_nodes+1; i++)
+ rename_variables_in_bb (new_bbs[i]);
+
free (new_bbs);
free (bbs);
+ #ifdef ENABLE_CHECKING
+ verify_dominators (CDI_DOMINATORS);
+ #endif
+
return new_loop;
}
*************** slpeel_tree_peel_loop_to_edge (struct lo
*** 1265,1274 ****
second_loop = loop;
}
- slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
- rename_variables_in_loop (new_loop);
-
-
/* 2. Add the guard code in one of the following ways:
2.a Add the guard that controls whether the first loop is executed.
--- 1133,1138 ----
*************** slpeel_tree_peel_loop_to_edge (struct lo
*** 1355,1361 ****
*/
bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
! bb_before_second_loop = split_edge (single_exit (first_loop));
probability_of_second_loop = (inverse_probability (first_guard_probability)
+ combine_probabilities
(second_guard_probability,
--- 1219,1226 ----
*/
bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
! /* Loop copying insterted a forwarder block for us here. */
! bb_before_second_loop = single_exit (first_loop)->dest;
probability_of_second_loop = (inverse_probability (first_guard_probability)
+ combine_probabilities
(second_guard_probability,
Index: trunk/gcc/testsuite/gcc.dg/torture/pr55964.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/torture/pr55964.c 2013-01-14
16:44:58.537699878 +0100
***************
*** 0 ****
--- 1,24 ----
+ /* { dg-do compile } */
+ /* { dg-options "-ftree-loop-distribution -funswitch-loops" } */
+
+ int a, b;
+
+ void f(void)
+ {
+ lbl1:
+ for(b = 0; b < 1; b++)
+ {
+ int u = 1;
+
+ if((b %= 0) * (b ? 0 : a) - 1 && (u /= 0))
+ {
+ int *q = &u, **k = q;
+ goto lbl1;
+ lbl2:
+ lbl3:
+ a = **k;
+ goto lbl2;
+ }
+ }
+ goto lbl3;
+ }
