[lno] Unrolling and peeling
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Thu Jan 22 01:29:00 GMT 2004
Hello,
this patch adds a possibility to unroll or peel a loop while preserving
the ssa form. To make it feasible, it is required that all the loop's
exits lead to the same place; many loops satisfy this property.
Zdenek
* tree-ssa-loop-manip.c: New file.
* Makefile.in (tree-ssa-loop-manip.o): Add.
* basic-block.h (struct reorder_block_def): New field copy_number.
* cfghooks.c (split_block, make_forwarder_block): Update irreducible
loop information.
* cfgloopmanip.c (duplicate_loop_to_header_edge): Set copy_number.
* tree-cfg.c (tree_duplicate_bb): Duplicate also virtual operands.
* tree-flow.h (enum tree_ann_type): Add MISC_ANN.
(struct misc_ann_d): New.
(union tree_ann_d): Add misc field.
(test_unrolling_and_peeling, tree_duplicate_loop_to_header_edge):
Declare.
* tree-ssa-loop.c (tree_ssa_loop_opt): Call
test_unrolling_and_peeling.
* tree-ssa-operands.c (copy_virtual_operands): New.
* tree-ssa-operands.h (copy_virtual_operands): Declare.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.5
diff -c -3 -p -r1.903.2.158.2.5 Makefile.in
*** Makefile.in 21 Jan 2004 12:59:04 -0000 1.903.2.158.2.5
--- Makefile.in 22 Jan 2004 01:09:30 -0000
*************** OBJS-common = \
*** 874,880 ****
tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
! tree-vectorizer.o tree-ssa-loop-im.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
--- 874,880 ----
tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
! tree-vectorizer.o tree-ssa-loop-im.o tree-ssa-loop-manip.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
*************** tree-ssa-loop.o : tree-ssa-loop.c $(TREE
*** 1594,1599 ****
--- 1594,1603 ----
tree-pass.h flags.h
tree-ssa-loop-im.o : tree-ssa-loop-im.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h domwalk.h $(PARAMS_H)\
+ output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+ tree-pass.h
+ tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
+ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h
tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.153.2.39.2.2
diff -c -3 -p -r1.153.2.39.2.2 basic-block.h
*** basic-block.h 21 Jan 2004 09:24:58 -0000 1.153.2.39.2.2
--- basic-block.h 22 Jan 2004 01:09:30 -0000
*************** typedef struct reorder_block_def
*** 287,292 ****
--- 287,293 ----
/* Used by loop copying. */
basic_block copy;
int duplicated;
+ int copy_number;
/* These fields are used by bb-reorder pass. */
int visited;
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.1.2.4.2.2
diff -c -3 -p -r1.1.2.4.2.2 cfghooks.c
*** cfghooks.c 21 Jan 2004 09:24:58 -0000 1.1.2.4.2.2
--- cfghooks.c 22 Jan 2004 01:09:30 -0000
*************** edge
*** 303,308 ****
--- 303,310 ----
split_block (basic_block bb, void *i)
{
basic_block new_bb;
+ bool irr = (bb->flags & BB_IRREDUCIBLE_LOOP) != 0;
+ int flags = EDGE_FALLTHRU;
if (!cfg_hooks->split_block)
internal_error ("%s does not support split_block.", cfg_hooks->name);
*************** split_block (basic_block bb, void *i)
*** 314,319 ****
--- 316,326 ----
new_bb->count = bb->count;
new_bb->frequency = bb->frequency;
new_bb->loop_depth = bb->loop_depth;
+ if (irr)
+ {
+ new_bb->flags |= BB_IRREDUCIBLE_LOOP;
+ flags |= EDGE_IRREDUCIBLE_LOOP;
+ }
if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
{
*************** split_block (basic_block bb, void *i)
*** 321,327 ****
set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
}
! return make_edge (bb, new_bb, EDGE_FALLTHRU);
}
/* Splits block BB just after labels. The newly created edge is returned. */
--- 328,334 ----
set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
}
! return make_edge (bb, new_bb, flags);
}
/* Splits block BB just after labels. The newly created edge is returned. */
*************** make_forwarder_block (basic_block bb, bo
*** 519,524 ****
--- 526,532 ----
{
edge e, next_e, fallthru;
basic_block dummy, jump;
+ bool fst_irr = false;
if (!cfg_hooks->make_forwarder_block)
internal_error ("%s does not support make_forwarder_block.",
*************** make_forwarder_block (basic_block bb, bo
*** 533,539 ****
{
next_e = e->pred_next;
if (redirect_edge_p (e))
! continue;
dummy->frequency -= EDGE_FREQUENCY (e);
dummy->count -= e->count;
--- 541,550 ----
{
next_e = e->pred_next;
if (redirect_edge_p (e))
! {
! fst_irr |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
! continue;
! }
dummy->frequency -= EDGE_FREQUENCY (e);
dummy->count -= e->count;
*************** make_forwarder_block (basic_block bb, bo
*** 545,550 ****
--- 556,567 ----
jump = redirect_edge_and_branch_force (e, bb);
if (jump)
new_bb_cbk (jump);
+ }
+
+ if (!fst_irr)
+ {
+ dummy->flags &= ~BB_IRREDUCIBLE_LOOP;
+ fallthru->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.3.2.11.2.2
diff -c -3 -p -r1.3.2.11.2.2 cfgloopmanip.c
*** cfgloopmanip.c 21 Jan 2004 01:10:11 -0000 1.3.2.11.2.2
--- cfgloopmanip.c 22 Jan 2004 01:09:31 -0000
*************** duplicate_loop_to_header_edge (struct lo
*** 967,972 ****
--- 967,975 ----
/* Copy bbs. */
copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop);
+ for (i = 0; i < n; i++)
+ new_bbs[i]->rbi->copy_number = j + 1;
+
/* Note whether the blocks and edges belong to an irreducible loop. */
if (add_irreducible_flag)
{
*************** duplicate_loop_to_header_edge (struct lo
*** 1045,1050 ****
--- 1048,1055 ----
int n_dom_bbs,j;
bb = bbs[i];
+ bb->rbi->copy_number = 0;
+
n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
for (j = 0; j < n_dom_bbs; j++)
{
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.244.2.3
diff -c -3 -p -r1.1.4.244.2.3 tree-cfg.c
*** tree-cfg.c 21 Jan 2004 09:24:58 -0000 1.1.4.244.2.3
--- tree-cfg.c 22 Jan 2004 01:09:31 -0000
*************** tree_duplicate_bb (basic_block bb)
*** 3687,3697 ****
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
! bsi_insert_after (&bsi_tgt, unshare_expr (stmt), BSI_NEW_STMT);
}
return new_bb;
--- 3687,3704 ----
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
+ tree copy;
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
! copy = unshare_expr (stmt);
!
! /* Copy also the virtual operands. */
! get_stmt_ann (copy);
! copy_virtual_operands (copy, stmt);
!
! bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
}
return new_bb;
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.4
diff -c -3 -p -r1.1.4.177.2.4 tree-flow.h
*** tree-flow.h 21 Jan 2004 09:24:58 -0000 1.1.4.177.2.4
--- tree-flow.h 22 Jan 2004 01:09:31 -0000
*************** typedef struct basic_block_def *basic_bl
*** 40,46 ****
/*---------------------------------------------------------------------------
Tree annotations stored in tree_common.ann
---------------------------------------------------------------------------*/
! enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN };
struct tree_ann_common_d GTY(())
{
--- 40,46 ----
/*---------------------------------------------------------------------------
Tree annotations stored in tree_common.ann
---------------------------------------------------------------------------*/
! enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN, MISC_ANN };
struct tree_ann_common_d GTY(())
{
*************** struct dataflow_d GTY(())
*** 193,198 ****
--- 193,204 ----
typedef struct dataflow_d *dataflow_t;
+ struct misc_ann_d GTY(())
+ {
+ struct tree_ann_common_d common;
+
+ PTR GTY ((skip (""))) data;
+ };
struct stmt_ann_d GTY(())
{
*************** union tree_ann_d GTY((desc ("ann_type ((
*** 247,252 ****
--- 253,259 ----
struct tree_ann_common_d GTY((tag ("TREE_ANN_COMMON"))) common;
struct var_ann_d GTY((tag ("VAR_ANN"))) decl;
struct stmt_ann_d GTY((tag ("STMT_ANN"))) stmt;
+ struct misc_ann_d GTY((tag ("MISC_ANN"))) misc;
};
typedef union tree_ann_d *tree_ann;
*************** extern void propagate_copy (tree *, tree
*** 534,539 ****
--- 541,551 ----
/* In tree-ssa-loop*.c */
void tree_ssa_lim (struct loops *loops);
+ void test_unrolling_and_peeling (struct loops *loops);
+ bool tree_duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
+ unsigned int, sbitmap,
+ edge, edge *,
+ unsigned int *, int);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: tree-ssa-loop-manip.c
diff -N tree-ssa-loop-manip.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-manip.c 22 Jan 2004 01:09:31 -0000
***************
*** 0 ****
--- 1,488 ----
+ /* High-level loop manipulation functions.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "timevar.h"
+ #include "cfgloop.h"
+ #include "tree-pass.h"
+
+ /* Checks whether E is an exit edge of the MFB_REE_LOOP. Callback for
+ make_forwarder_block. */
+
+ static struct loop *mfb_ree_loop;
+ static bool
+ mfb_redirect_exit_edges (edge e)
+ {
+ return flow_bb_inside_loop_p (mfb_ree_loop, e->src);
+ }
+
+ /* Copies phi nodes in newly created copies of the LOOP. The new blocks start
+ since FIRST_NEW_BLOCK index. PEELING is true if we were peeling
+ the loop. */
+
+ static void
+ copy_phi_nodes (struct loop *loop, unsigned first_new_block, bool peeling)
+ {
+ unsigned i;
+ basic_block bb, orig;
+ tree phi, new_phi, def;
+ edge e, new_e;
+ edge latch = loop_latch_edge (loop), entry = loop_preheader_edge (loop);
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ {
+ bb = BASIC_BLOCK (i);
+ orig = bb->rbi->original;
+
+ for (phi = phi_nodes (orig); phi; phi = TREE_CHAIN (phi))
+ {
+ new_phi = create_phi_node (PHI_RESULT (phi), bb);
+
+ if (orig == loop->header)
+ {
+ if (!bb->pred || bb->pred->pred_next)
+ abort ();
+
+ new_e = bb->pred;
+ e = (peeling && bb->rbi->copy_number == 1
+ ? entry
+ : latch);
+ def = phi_element_for_edge (phi, e)->def;
+ add_phi_arg (&new_phi, def, new_e);
+ continue;
+ }
+
+ for (new_e = bb->pred; new_e; new_e = new_e->pred_next)
+ {
+ e = find_edge (new_e->src->rbi->original, orig);
+ if (!e)
+ abort ();
+
+ def = phi_element_for_edge (phi, e)->def;
+ add_phi_arg (&new_phi, def, new_e);
+ }
+ }
+ }
+
+ if (peeling)
+ {
+ /* Update the phi nodes in the header so that the latch value comes from
+ both edges. */
+ for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
+ {
+ def = phi_element_for_edge (phi, latch)->def;
+ phi_element_for_edge (phi, entry)->def = def;
+ }
+ }
+ }
+
+ /* Constructs list of all ssa names defined inside LOOP. */
+
+ static tree
+ collect_defs (struct loop *loop)
+ {
+ basic_block *body = get_loop_body (loop);
+ unsigned i, j;
+ tree phi, stmt;
+ block_stmt_iterator bsi;
+ def_optype defs;
+ vdef_optype vdefs;
+ tree ret = NULL_TREE;
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+
+ get_stmt_operands (stmt);
+
+ defs = STMT_DEF_OPS (stmt);
+ for (j = 0; j < NUM_DEFS (defs); j++)
+ ret = tree_cons (NULL, DEF_OP (defs, j), ret);
+
+ vdefs = STMT_VDEF_OPS (stmt);
+ for (j = 0; j < NUM_VDEFS (vdefs); j++)
+ ret = tree_cons (NULL, VDEF_RESULT (vdefs, j), ret);
+ }
+
+ for (phi = phi_nodes (body[i]); phi; phi = TREE_CHAIN (phi))
+ ret = tree_cons (NULL, PHI_RESULT (phi), ret);
+ }
+
+ return ret;
+ }
+
+ /* For each definition in DEFINITIONS allocates NDUPL + 1 copies
+ (one for each duplicate of the loop body). */
+
+ static void
+ allocate_new_names (tree definitions, unsigned ndupl)
+ {
+ tree def;
+ unsigned i;
+ struct misc_ann_d *ann;
+ tree *new_names;
+
+ for (; definitions; definitions = TREE_CHAIN (definitions))
+ {
+ def = TREE_VALUE (definitions);
+ ann = xmalloc (sizeof (struct misc_ann_d));
+ new_names = xmalloc (sizeof (tree) * (ndupl + 1));
+ ann->data = new_names;
+
+ for (i = 0; i <= ndupl; i++)
+ new_names[i] = make_ssa_name (SSA_NAME_VAR (def),
+ SSA_NAME_DEF_STMT (def));
+ def->common.ann = (union tree_ann_d *) ann;
+ }
+ }
+
+ /* Renames the variable *OP_P in statement STMT. If DEF is true,
+ *OP_P is defined by the statement. N_COPY is the number of the
+ copy of the loop body we are renaming. */
+
+ static void
+ rename_op (tree *op_p, bool def, tree stmt, unsigned n_copy)
+ {
+ struct misc_ann_d *ann;
+ tree *new_names;
+
+ if (TREE_CODE (*op_p) != SSA_NAME)
+ return;
+
+ ann = &(*op_p)->common.ann->misc;
+ new_names = ann ? ann->data : NULL;
+
+ /* Something defined outside of the loop. */
+ if (!new_names)
+ return;
+
+ /* An ordinary ssa name defined in the loop. */
+
+ *op_p = new_names[n_copy];
+ if (def)
+ SSA_NAME_DEF_STMT (*op_p) = stmt;
+ }
+
+ /* Renames the variables in basic block BB. */
+
+ static void
+ rename_variables_in_bb (basic_block bb)
+ {
+ tree phi;
+ block_stmt_iterator bsi;
+ tree stmt;
+ stmt_ann_t ann;
+ use_optype uses;
+ vuse_optype vuses;
+ def_optype defs;
+ vdef_optype vdefs;
+ unsigned i, nbb = bb->rbi->copy_number;
+ edge e;
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ rename_op (&PHI_RESULT (phi), true, phi, nbb);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ rename_op (USE_OP_PTR (uses, i), false, stmt, nbb);
+
+ defs = DEF_OPS (ann);
+ for (i = 0; i < NUM_DEFS (defs); i++)
+ rename_op (DEF_OP_PTR (defs, i), true, stmt, nbb);
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ rename_op (VUSE_OP_PTR (vuses, i), false, stmt, nbb);
+
+ vdefs = VDEF_OPS (ann);
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ {
+ rename_op (VDEF_OP_PTR (vdefs, i), false, stmt, nbb);
+ rename_op (VDEF_RESULT_PTR (vdefs, i), true, stmt, nbb);
+ }
+ }
+
+ for (e = bb->succ; e; e = e->succ_next)
+ for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ rename_op (&phi_element_for_edge (phi, e)->def, false, phi, nbb);
+ }
+
+ /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
+ FIRST_NEW_BLOCK is the first block in the copied area. */
+
+ static void
+ rename_variables (unsigned first_new_block)
+ {
+ unsigned i;
+ basic_block bb;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ {
+ bb = BASIC_BLOCK (i);
+
+ rename_variables_in_bb (bb);
+
+ if (bb->rbi->copy_number == 1)
+ rename_variables_in_bb (bb->rbi->original);
+ }
+ }
+
+ /* Releases the structures holding the new ssa names. If FREE_VARS is true,
+ also the original ssa names are released. */
+
+ static void
+ free_new_names (tree definitions, bool free_vars)
+ {
+ tree def;
+ struct misc_ann_d *ann;
+
+ for (; definitions; definitions = TREE_CHAIN (definitions))
+ {
+ def = TREE_VALUE (definitions);
+ ann = &def->common.ann->misc;
+
+ free (ann->data);
+ free (ann);
+ def->common.ann = NULL;
+
+ if (free_vars)
+ release_ssa_name (def);
+ }
+ }
+
+ /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */
+
+ static void
+ set_phi_def_stmts (basic_block bb)
+ {
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
+ }
+
+ /* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
+ ssa. In order to achieve this, only loops whose exits all lead to the same
+ location are handled.
+
+ FIXME: we create some degenerate phi nodes that could be avoided by copy
+ propagating them instead. Unfortunately this is not completely
+ straightforward due to problems with constant folding. */
+
+ bool
+ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
+ struct loops *loops,
+ unsigned int ndupl, sbitmap wont_exit,
+ edge orig, edge *to_remove,
+ unsigned int *n_to_remove, int flags)
+ {
+ unsigned first_new_block;
+ basic_block exit_block = NULL, bb;
+ unsigned n_exits, i;
+ edge *exits = get_loop_exit_edges (loop, &n_exits);
+ bool peeling = (e != loop_latch_edge (loop));
+ edge latch, latch_copy, ae, oe;
+ tree phi, arg, map, def;
+ tree definitions, usable_outside;
+
+ if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
+ return false;
+ if (!(loops->state & LOOPS_HAVE_PREHEADERS))
+ return false;
+
+ for (i = 0; i < n_exits; i++)
+ {
+ /* Edges to exit can be safely ignored, since no uses may be reached
+ through them. */
+ if(exits[i]->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (!exit_block)
+ exit_block = exits[i]->dest;
+ else if (exits[i]->dest != exit_block)
+ {
+ free (exits);
+ return false;
+ }
+ }
+ free (exits);
+
+ /* Ensure that only exits of the loop enter the exit_block. */
+ if (exit_block)
+ {
+ for (ae = exit_block->pred; ae; ae = ae->pred_next)
+ if (!flow_bb_inside_loop_p (loop, ae->src))
+ break;
+
+ if (ae)
+ {
+ mfb_ree_loop = loop;
+ make_forwarder_block (exit_block, mfb_redirect_exit_edges, NULL);
+ bb = exit_block->succ->dest;
+ add_bb_to_loop (bb, exit_block->loop_father);
+
+ if (exit_block->loop_father->latch == exit_block)
+ exit_block->loop_father->latch = bb;
+ }
+ }
+
+ definitions = collect_defs (loop);
+ usable_outside = NULL_TREE;
+ if (exit_block)
+ {
+ for (arg = definitions; arg; arg = TREE_CHAIN (arg))
+ {
+ def = TREE_VALUE (arg);
+ if (!dominated_by_p (CDI_DOMINATORS, exit_block,
+ bb_for_stmt (SSA_NAME_DEF_STMT (def))))
+ continue;
+
+ usable_outside = tree_cons (NULL, def, usable_outside);
+ }
+ }
+
+ first_new_block = last_basic_block;
+ if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
+ orig, to_remove, n_to_remove, flags))
+ return false;
+
+ allocate_new_names (definitions, ndupl);
+
+ /* Readd the removed phi args for e. */
+ latch = loop_latch_edge (loop);
+ latch_copy = peeling ? loop_preheader_edge (loop) : latch;
+ map = PENDING_STMT (e);
+ PENDING_STMT (e) = NULL;
+
+ for (phi = phi_nodes (loop->header), arg = map;
+ phi;
+ phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
+ {
+ def = TREE_VALUE (arg);
+ add_phi_arg (&phi, def, latch_copy);
+ }
+ if (arg)
+ abort ();
+
+ if (exit_block)
+ {
+ /* Extend the phi nodes in exit_block. */
+ for (phi = phi_nodes (exit_block); phi; phi = TREE_CHAIN (phi))
+ {
+ for (ae = exit_block->pred; ae; ae = ae->pred_next)
+ {
+ if (ae->src->rbi->copy_number == 0)
+ continue;
+
+ oe = find_edge (ae->src->rbi->original, exit_block);
+ if (!oe)
+ abort ();
+
+ def = phi_element_for_edge (phi, oe)->def;
+ add_phi_arg (&phi, def, ae);
+ }
+ }
+
+ /* Add phi nodes for definitions to exit_block (we could find out
+ which of them are really used outside of the loop and don't emit the
+ phi nodes for the remaining ones; for this we would however need
+ to know immediate uses). */
+ for (arg = usable_outside; arg; arg = TREE_CHAIN (arg))
+ {
+ def = TREE_VALUE (arg);
+ phi = create_phi_node (def, exit_block);
+ for (ae = exit_block->pred; ae; ae = ae->pred_next)
+ add_phi_arg (&phi, def, ae);
+ }
+ }
+
+ /* Copy the phi nodes. */
+ copy_phi_nodes (loop, first_new_block, peeling);
+
+ /* Rename the variables. */
+ rename_variables (first_new_block);
+ free_new_names (definitions, exit_block == NULL);
+
+ /* For some time we have the identical ssa names as results in multiple phi
+ nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
+ to the new copy. This means that we cannot easily ensure that the ssa
+ names defined in those phis are pointing to the right one -- so just
+ recompute SSA_NAME_DEF_STMT for them. */
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ {
+ bb = BASIC_BLOCK (i);
+ set_phi_def_stmts (bb);
+ if (bb->rbi->copy_number == 1)
+ set_phi_def_stmts (bb->rbi->original);
+ }
+ if (exit_block)
+ set_phi_def_stmts (exit_block);
+
+ return true;
+ }
+
+ /* Unrolls and peels each loop twice for testing. */
+
+ void
+ test_unrolling_and_peeling (struct loops *loops)
+ {
+ struct loop *loop;
+ unsigned i;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+
+ if (!loop
+ || loop->inner)
+ continue;
+
+ tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
+ loops, 2, NULL, NULL, NULL, NULL, 0);
+ verify_loop_structure (loops);
+ verify_ssa ();
+
+ tree_duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
+ loops, 2, NULL, NULL, NULL, NULL, 0);
+ verify_loop_structure (loops);
+ verify_ssa ();
+ }
+ }
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop.c,v
retrieving revision 1.1.2.3.2.3
diff -c -3 -p -r1.1.2.3.2.3 tree-ssa-loop.c
*** tree-ssa-loop.c 21 Jan 2004 09:24:58 -0000 1.1.2.3.2.3
--- tree-ssa-loop.c 22 Jan 2004 01:09:31 -0000
*************** tree_ssa_loop_opt (void)
*** 51,57 ****
if (loops)
{
/* Ensure there is a place to move the computations to. */
! create_preheaders (loops, 0);
/* Move the expensive loop invariants. */
tree_ssa_lim (loops);
--- 51,60 ----
if (loops)
{
/* Ensure there is a place to move the computations to. */
! create_preheaders (loops, CP_SIMPLE_PREHEADERS);
!
! /* Test unrolling and peeling. */
! test_unrolling_and_peeling (loops);
/* Move the expensive loop invariants. */
tree_ssa_lim (loops);
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-operands.c,v
retrieving revision 1.1.2.3.2.1
diff -c -3 -p -r1.1.2.3.2.1 tree-ssa-operands.c
*** tree-ssa-operands.c 21 Jan 2004 01:10:54 -0000 1.1.2.3.2.1
--- tree-ssa-operands.c 22 Jan 2004 01:09:31 -0000
*************** add_call_read_ops (tree stmt, voperands_
*** 1262,1265 ****
--- 1262,1294 ----
}
}
+ /* Copies virtual operands from SRC to DST. */
+
+ void
+ copy_virtual_operands (tree dst, tree src)
+ {
+ vuse_optype vuses = STMT_VUSE_OPS (src);
+ vdef_optype vdefs = STMT_VDEF_OPS (src);
+ vuse_optype *vuses_new = &stmt_ann (dst)->vuse_ops;
+ vdef_optype *vdefs_new = &stmt_ann (dst)->vdef_ops;
+ unsigned i;
+
+ if (vuses)
+ {
+ *vuses_new = allocate_vuse_optype (NUM_VUSES (vuses));
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ *VUSE_OP_PTR (*vuses_new, i) = VUSE_OP (vuses, i);
+ }
+
+ if (vdefs)
+ {
+ *vdefs_new = allocate_vdef_optype (NUM_VDEFS (vdefs));
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ {
+ *VDEF_OP_PTR (*vdefs_new, i) = VDEF_OP (vdefs, i);
+ *VDEF_RESULT_PTR (*vdefs_new, i) = VDEF_RESULT (vdefs, i);
+ }
+ }
+ }
+
#include "gt-tree-ssa-operands.h"
Index: tree-ssa-operands.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-operands.h,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 tree-ssa-operands.h
*** tree-ssa-operands.h 16 Dec 2003 21:42:31 -0000 1.1.2.2
--- tree-ssa-operands.h 22 Jan 2004 01:09:31 -0000
*************** void add_vuse (tree, tree);
*** 93,97 ****
--- 93,98 ----
extern void get_stmt_operands (tree);
extern void remove_vuses (tree);
extern void remove_vdefs (tree);
+ extern void copy_virtual_operands (tree, tree);
#endif /* GCC_TREE_SSA_OPERANDS_H */
More information about the Gcc-patches
mailing list