This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[LNO] Update loop versioning
- From: Devang Patel <dpatel at apple dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 29 Mar 2004 14:50:13 -0800
- Subject: [LNO] Update loop versioning
This patch includes following fixes:
- Update copy_phi_nodes() to keep phi node list in original order.
- Update lv_adjust_loop_header_phi() to walk phi nodes in parallel
because now there are guaranteed to be in same order.
- Provide new api update_lv_condition () to update condition that
selects loop version.
Bootstrapped on powerpc-darwin
2004-03-29 Devang Patel <dpatel@apple.com>
* tree-flow.h (tree_ssa_loop_version): Add new parameter,
basic_block *.
(update_lv_condition): New.
* tree-ssa-loop-manip.c (copy_phi_nodes): nreverse copied phi
nodes list
to ensure that phi nodes remain in same order.
(lv_update_pending_stmts): Do not nreverse pending list.
(lv_adjust_loop_header_phi): Walk two phi nodes list in
parallel.
(tree_ssa_loop_version): Now condition_bb is input parameter.
Fix
irregular flags after duplication.
(update_lv_condition): New.
(test_loop_versioning): Use update_lv_condition.
* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Update function
tree_ssa_loop_version () call by adding 4th parameter.
--
Devang
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.20
diff -Idpatel.pbxuser -c -3 -p -r1.1.4.177.2.20 tree-flow.h
*** tree-flow.h 23 Mar 2004 20:13:28 -0000 1.1.4.177.2.20
--- tree-flow.h 29 Mar 2004 22:39:53 -0000
*************** bool tree_duplicate_loop_to_header_edge
*** 604,610 ****
void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator
*, bool,
tree *, tree *);
void test_loop_versioning (struct loops *loops);
! struct loop *tree_ssa_loop_version (struct loops *, struct loop *,
tree);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
void linear_transform_loops (struct loops *, varray_type);
void loop_commit_inserts (void);
--- 604,612 ----
void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator
*, bool,
tree *, tree *);
void test_loop_versioning (struct loops *loops);
! struct loop *tree_ssa_loop_version (struct loops *, struct loop *,
tree,
! basic_block *);
! void update_lv_condition (basic_block *, tree);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
void linear_transform_loops (struct loops *, varray_type);
void loop_commit_inserts (void);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-manip.c,v
retrieving revision 1.1.2.6
diff -Idpatel.pbxuser -c -3 -p -r1.1.2.6 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c 21 Mar 2004 13:34:21 -0000 1.1.2.6
--- tree-ssa-loop-manip.c 29 Mar 2004 22:39:53 -0000
*************** copy_phi_nodes (struct loop *loop, unsig
*** 66,71 ****
--- 66,72 ----
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
{
+ tree nlist;
bb = BASIC_BLOCK (i);
orig = bb->rbi->original;
*************** copy_phi_nodes (struct loop *loop, unsig
*** 97,102 ****
--- 98,107 ----
add_phi_arg (&new_phi, def, new_e);
}
}
+
+ /* neverse phi nodes to keep them in original order. */
+ nlist = nreverse (phi_nodes (bb));
+ set_phi_nodes (bb, nlist);
}
if (peeling)
*************** static void
*** 569,585 ****
lv_update_pending_stmts (edge e)
{
basic_block dest;
! tree pending, phi, arg, def;
if (!PENDING_STMT (e))
return;
dest = e->dest;
! pending = nreverse (PENDING_STMT (e));
! PENDING_STMT (e) = NULL;
!
! for (phi = phi_nodes (dest), arg = pending;
phi;
phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
{
--- 574,587 ----
lv_update_pending_stmts (edge e)
{
basic_block dest;
! tree phi, arg, def;
if (!PENDING_STMT (e))
return;
dest = e->dest;
! for (phi = phi_nodes (dest), arg = PENDING_STMT (e);
phi;
phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
{
*************** lv_update_pending_stmts (edge e)
*** 587,592 ****
--- 589,595 ----
add_phi_arg (&phi, def, e);
}
+ PENDING_STMT (e) = NULL;
}
/* Adjust phi nodes for 'first' basic block. 'second' basic block is
a copy
*************** lv_adjust_loop_header_phi (basic_block f
*** 604,613 ****
{
tree phi1, phi2;
! /* Browse all 'second' basic block phi nodes and find phi args that
! are part of and edge from 'new_head' basic block. */
! for (phi2 = phi_nodes (second); phi2; phi2 = TREE_CHAIN (phi2))
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
--- 607,618 ----
{
tree phi1, phi2;
! /* Browse all 'second' basic block phi nodes and add phi args to
! edge 'e' for 'first' head. PHI args are always in correct order.
*/
! for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
! phi2 && phi1;
! phi2 = TREE_CHAIN (phi2), phi1 = TREE_CHAIN (phi1))
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
*************** lv_adjust_loop_header_phi (basic_block f
*** 615,643 ****
if (PHI_ARG_EDGE (phi2, i)->src == new_head)
{
tree def = PHI_ARG_DEF (phi2, i);
! tree var2 = SSA_NAME_VAR (PHI_RESULT (phi2));
!
! /* This phi node is on the edge whose soure is
'new_head'.
! Find corrosponding phi node for 'first' basic block.
*/
!
! for (phi1 = phi_nodes (first); phi1; phi1 = TREE_CHAIN
(phi1))
! {
! tree var1 = SSA_NAME_VAR (PHI_RESULT (phi1));
! if (var1 == var2)
! {
! /* Add phi arg to edge 'e'. */
! add_phi_arg (&phi1, def, e);
!
! /* There can not be second phi node for the same
variable.
! Get out of the for loop that walks phi nodes
of 'first'.
! */
! break;
! }
! }
!
! /* In a phi node, there is only one edge from 'new_head'.
! Get out of the for loop that walks phi nodes for
'second'. */
! break;
}
}
}
--- 620,626 ----
if (PHI_ARG_EDGE (phi2, i)->src == new_head)
{
tree def = PHI_ARG_DEF (phi2, i);
! add_phi_arg (&phi1, def, e);
}
}
}
*************** may be a run time test for things that w
*** 654,663 ****
analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
struct loop *
! tree_ssa_loop_version (struct loops *loops, struct loop * loop, tree
cond_expr)
{
edge entry, latch_edge;
! basic_block first_head, second_head, condition_bb;
int irred_flag;
struct loop *nloop;
--- 637,647 ----
analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
struct loop *
! tree_ssa_loop_version (struct loops *loops, struct loop * loop,
! tree cond_expr, basic_block *condition_bb)
{
edge entry, latch_edge;
! basic_block first_head, second_head;
int irred_flag;
struct loop *nloop;
*************** tree_ssa_loop_version (struct loops *loo
*** 687,713 ****
second_head = entry->dest;
/* Split loop entry edge and insert new block with cond expr. */
! condition_bb = lv_adjust_loop_entry_edge (first_head, second_head,
entry,
cond_expr);
latch_edge = loop->latch->rbi->copy->succ;
nloop = loopify (loops,
latch_edge,
loop->header->rbi->copy->pred,
! condition_bb,
false /* Do not redirect all edges. */);
/* loopify redirected latch_edge. Update its PENDING_STMTS. */
lv_update_pending_stmts (latch_edge);
/* loopify redirected condition_bb's succ edge. Update its
PENDING_STMTS. */
! lv_update_pending_stmts (FALLTHRU_EDGE (condition_bb));
/* At this point condition_bb is loop predheader with two
successors,
first_head and second_head. Make sure that loop predheader has
only
one successor. */
! loop_split_edge_with (find_edge (condition_bb, first_head), NULL);
! loop_split_edge_with (find_edge (condition_bb, second_head), NULL);
/* Ensure that the latch has just a single successor. */
loop_split_edge_with (loop_latch_edge (loop), NULL);
--- 671,712 ----
second_head = entry->dest;
/* Split loop entry edge and insert new block with cond expr. */
! *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head,
entry,
cond_expr);
+ /* Adjust irreducle flag. */
+ if (irred_flag)
+ {
+ (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
+ (*condition_bb)->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
+ (*condition_bb)->succ->succ_next->flags |=
EDGE_IRREDUCIBLE_LOOP;
+ }
+ else
+ {
+ (*condition_bb)->flags &= ~BB_IRREDUCIBLE_LOOP;
+ (*condition_bb)->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+ (*condition_bb)->succ->succ_next->flags &=
~EDGE_IRREDUCIBLE_LOOP;
+ }
+
latch_edge = loop->latch->rbi->copy->succ;
nloop = loopify (loops,
latch_edge,
loop->header->rbi->copy->pred,
! *condition_bb,
false /* Do not redirect all edges. */);
/* loopify redirected latch_edge. Update its PENDING_STMTS. */
lv_update_pending_stmts (latch_edge);
/* loopify redirected condition_bb's succ edge. Update its
PENDING_STMTS. */
! lv_update_pending_stmts (FALLTHRU_EDGE (*condition_bb));
! /*lv_update_pending_stmts (BRANCH_EDGE (*condition_bb));*/
/* At this point condition_bb is loop predheader with two
successors,
first_head and second_head. Make sure that loop predheader has
only
one successor. */
! loop_split_edge_with (find_edge (*condition_bb, first_head), NULL);
! loop_split_edge_with (find_edge (*condition_bb, second_head), NULL);
/* Ensure that the latch has just a single successor. */
loop_split_edge_with (loop_latch_edge (loop), NULL);
*************** tree_ssa_loop_version (struct loops *loo
*** 716,721 ****
--- 715,739 ----
return nloop;
}
+ /* Update loop versioning condition.
+ This is used by other optimizations/transformations to disable
+ one loop version. */
+ void
+ update_lv_condition (basic_block *bb, tree new_cond)
+ {
+ tree stmt;
+ block_stmt_iterator bsi = bsi_last (*bb);
+
+ stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) == COND_EXPR)
+ {
+ TREE_OPERAND (stmt, 0) = new_cond;
+ modify_stmt (stmt);
+ }
+ else
+ abort ();
+ }
void
test_loop_versioning (struct loops *loops)
*************** test_loop_versioning (struct loops *loop
*** 726,731 ****
--- 744,751 ----
for (i = 1; i < loops->num; i = i+ 2)
{
+ struct loop *nloop;
+ basic_block condition_bb;
loop = loops->parray[i];
if (!loop)
*************** test_loop_versioning (struct loops *loop
*** 735,744 ****
integer_one_node,
integer_zero_node);
! tree_ssa_loop_version (loops, loop, cond_expr);
! verify_loop_structure (loops);
! verify_ssa ();
}
}
--- 755,770 ----
integer_one_node,
integer_zero_node);
! nloop = tree_ssa_loop_version (loops, loop, cond_expr,
&condition_bb);
! if (nloop)
! {
! verify_loop_structure (loops);
! verify_dominators (CDI_DOMINATORS);
! verify_ssa ();
!
! update_lv_condition (&condition_bb, boolean_true_node);
! }
}
}
Index: tree-ssa-loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-unswitch.c,v
retrieving revision 1.1.2.1
diff -Idpatel.pbxuser -c -3 -p -r1.1.2.1 tree-ssa-loop-unswitch.c
*** tree-ssa-loop-unswitch.c 21 Mar 2004 13:34:54 -0000 1.1.2.1
--- tree-ssa-loop-unswitch.c 29 Mar 2004 22:39:53 -0000
*************** static struct loop *
*** 268,273 ****
--- 268,274 ----
tree_unswitch_loop (struct loops *loops, struct loop *loop,
basic_block unswitch_on, tree cond)
{
+ basic_block condition_bb;
/* Some sanity checking. */
if (!flow_bb_inside_loop_p (loop, unswitch_on))
abort ();
*************** tree_unswitch_loop (struct loops *loops,
*** 277,281 ****
if (loop->inner)
abort ();
! return tree_ssa_loop_version (loops, loop, unshare_expr (cond));
}
--- 278,283 ----
if (loop->inner)
abort ();
! return tree_ssa_loop_version (loops, loop, unshare_expr (cond),
! &condition_bb);
}