[patch] Lno branch merge part 9 -- Rewrite of loop header copying
Zdenek Dvorak
rakdver@kam.mff.cuni.cz
Thu Aug 5 12:16:00 GMT 2004
Hello,
this patch rewrites loop header copying, so that it avoids using
rewrite_ssa_into_ssa and can be used as a subroutine in other loop
manipulations. We do it by implementing a function to copy a region
such that any definition inside the region is live only at a single
exit. In order for this to be sufficient we of course need a loop
closed ssa form.
Bootstrapped & regtested on i686.
Zdenek
* tree-ssa-loop-manip.c: New file.
* Makefile.in (tree-ssa-loop-manip.o): Add.
(tree-cfg.o): Add CFGLAYOUT_H dependency.
* basic-block.h (get_dominated_by_region): Declare.
* dominance.c (get_dominated_by_region): New function.
* tree-cfg.c: Include cfglayout.h.
(tree_duplicate_bb): Duplicate also phi nodes.
(struct ssa_name_map_entry): New type.
(add_phi_args_after_copy_bb, add_phi_args_after_copy,
ssa_name_map_entry_hash, ssa_name_map_entry_eq,
allocate_ssa_names, rewrite_to_new_ssa_names_def,
rewrite_to_new_ssa_names_use, rewrite_to_new_ssa_names_bb,
rewrite_to_new_ssa_names, tree_duplicate_sese_region): New functions.
* tree-flow.h (tree_duplicate_sese_region, dd_phi_args_after_copy_bb,
add_phi_args_after_copy, rewrite_to_new_ssa_names_bb,
rewrite_to_new_ssa_names, allocate_ssa_names,
rewrite_into_loop_closed_ssa, verify_loop_closed_ssa): Declare.
* tree-ssa-loop-ch.c (duplicate_blocks): Removed.
(copy_loop_headers): Use tree_duplicate_sese_region.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1337
diff -c -3 -p -r1.1337 Makefile.in
*** Makefile.in 4 Aug 2004 20:55:04 -0000 1.1337
--- Makefile.in 5 Aug 2004 09:36:04 -0000
*************** OBJS-common = \
*** 898,904 ****
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.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-ssa-loop-niter.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 \
--- 898,904 ----
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.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-ssa-loop-niter.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-vn.o : tree-vn.c $(CONFIG_H) $(SYST
*** 1657,1663 ****
tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
! $(TREE_DUMP_H) except.h langhooks.h $(CFGLOOP_H) gt-tree-cfg.h tree-pass.h
tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
$(TREE_DUMP_H) diagnostic.h except.h tree-pass.h $(FLAGS_H) langhooks.h
--- 1657,1664 ----
tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
! $(TREE_DUMP_H) except.h langhooks.h $(CFGLOOP_H) gt-tree-cfg.h tree-pass.h \
! $(CFGLAYOUT_H)
tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
$(TREE_DUMP_H) diagnostic.h except.h tree-pass.h $(FLAGS_H) langhooks.h
*************** tree-ssa-loop.o : tree-ssa-loop.c $(TREE
*** 1681,1686 ****
--- 1682,1691 ----
$(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 $(FLAGS_H) tree-inline.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 $(FLAGS_H) cfglayout.h tree-scalar-evolution.h
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.205
diff -c -3 -p -r1.205 basic-block.h
*** basic-block.h 4 Aug 2004 21:37:03 -0000 1.205
--- basic-block.h 5 Aug 2004 09:36:04 -0000
*************** extern void set_immediate_dominator (enu
*** 720,725 ****
--- 720,727 ----
extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block);
extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **);
+ extern unsigned get_dominated_by_region (enum cdi_direction, basic_block *,
+ unsigned, basic_block *);
extern void add_to_dominance_info (enum cdi_direction, basic_block);
extern void delete_from_dominance_info (enum cdi_direction, basic_block);
basic_block recount_dominator (enum cdi_direction, basic_block);
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dominance.c,v
retrieving revision 1.26
diff -c -3 -p -r1.26 dominance.c
*** dominance.c 29 Jul 2004 17:47:31 -0000 1.26
--- dominance.c 5 Aug 2004 09:36:04 -0000
*************** get_dominated_by (enum cdi_direction dir
*** 746,751 ****
--- 746,777 ----
return n;
}
+ /* Find all basic blocks that are immediately dominated (in direction DIR)
+ by some block between N_REGION ones stored in REGION, except for blocks
+ in the REGION itself. The found blocks are stored to DOMS and their number
+ is returned. */
+
+ unsigned
+ get_dominated_by_region (enum cdi_direction dir, basic_block *region,
+ unsigned n_region, basic_block *doms)
+ {
+ unsigned n_doms = 0, i;
+ basic_block dom;
+
+ for (i = 0; i < n_region; i++)
+ region[i]->rbi->duplicated = 1;
+ for (i = 0; i < n_region; i++)
+ for (dom = first_dom_son (dir, region[i]);
+ dom;
+ dom = next_dom_son (dir, dom))
+ if (!dom->rbi->duplicated)
+ doms[n_doms++] = dom;
+ for (i = 0; i < n_region; i++)
+ region[i]->rbi->duplicated = 0;
+
+ return n_doms;
+ }
+
/* Redirect all edges pointing to BB to TO. */
void
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.38
diff -c -3 -p -r2.38 tree-cfg.c
*** tree-cfg.c 4 Aug 2004 21:37:06 -0000 2.38
--- tree-cfg.c 5 Aug 2004 09:36:04 -0000
*************** Boston, MA 02111-1307, USA. */
*** 43,48 ****
--- 43,49 ----
#include "toplev.h"
#include "except.h"
#include "cfgloop.h"
+ #include "cfglayout.h"
/* This file contains functions for building the Control Flow Graph (CFG)
for a function tree. */
*************** tree_can_duplicate_bb_p (basic_block bb
*** 4289,4295 ****
return true;
}
-
/* Create a duplicate of the basic block BB. NOTE: This does not
preserve SSA form. */
--- 4290,4295 ----
*************** tree_duplicate_bb (basic_block bb)
*** 4306,4315 ****
--- 4306,4320 ----
new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+ /* First copy the phi nodes. We do not copy phi node arguments here,
+ since the edges are not ready yet. Keep the chain of phi nodes in
+ the same order, so that we can add them later. */
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
mark_for_rewrite (PHI_RESULT (phi));
+ create_phi_node (PHI_RESULT (phi), new_bb);
}
+ set_phi_nodes (new_bb, nreverse (phi_nodes (new_bb)));
bsi_tgt = bsi_start (new_bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
*************** tree_duplicate_bb (basic_block bb)
*** 4347,4352 ****
--- 4352,4748 ----
return new_bb;
}
+ /* Basic block BB_COPY was created by code duplication. Add phi node
+ arguments for edges going out of BB_COPY. The blocks that were
+ duplicated have rbi->duplicated set to one. */
+
+ void
+ add_phi_args_after_copy_bb (basic_block bb_copy)
+ {
+ basic_block bb, dest;
+ edge e, e_copy;
+ tree phi, phi_copy, phi_next, def;
+
+ bb = bb_copy->rbi->original;
+
+ for (e_copy = bb_copy->succ; e_copy; e_copy = e_copy->succ_next)
+ {
+ if (!phi_nodes (e_copy->dest))
+ continue;
+
+ if (e_copy->dest->rbi->duplicated)
+ dest = e_copy->dest->rbi->original;
+ else
+ dest = e_copy->dest;
+
+ e = find_edge (bb, dest);
+ if (!e)
+ {
+ /* During loop unrolling the target of the latch edge is copied.
+ In this case we are not looking for edge to dest, but to
+ duplicated block whose original was dest. */
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e->dest->rbi->duplicated
+ && e->dest->rbi->original == dest)
+ break;
+
+ if (!e)
+ abort ();
+ }
+
+ for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
+ phi;
+ phi = phi_next, phi_copy = TREE_CHAIN (phi_copy))
+ {
+ phi_next = TREE_CHAIN (phi);
+
+ if (PHI_RESULT (phi) != PHI_RESULT (phi_copy))
+ abort ();
+ def = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ add_phi_arg (&phi_copy, def, e_copy);
+ }
+ }
+ }
+
+ /* Blocks in REGION_COPY array of length N_REGION were created by
+ duplication of basic blocks. Add phi node arguments for edges
+ going from these blocks. */
+
+ void
+ add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
+ {
+ unsigned i;
+
+ for (i = 0; i < n_region; i++)
+ region_copy[i]->rbi->duplicated = 1;
+
+ for (i = 0; i < n_region; i++)
+ add_phi_args_after_copy_bb (region_copy[i]);
+
+ for (i = 0; i < n_region; i++)
+ region_copy[i]->rbi->duplicated = 0;
+ }
+
+ /* Maps the old ssa name FROM_NAME to TO_NAME. */
+
+ struct ssa_name_map_entry
+ {
+ tree from_name;
+ tree to_name;
+ };
+
+ /* Hash function for ssa_name_map_entry. */
+
+ static hashval_t
+ ssa_name_map_entry_hash (const void *entry)
+ {
+ const struct ssa_name_map_entry *en = entry;
+ return SSA_NAME_VERSION (en->from_name);
+ }
+
+ /* Equality function for ssa_name_map_entry. */
+
+ static int
+ ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
+ {
+ const struct ssa_name_map_entry *en = in_table;
+
+ return en->from_name == ssa_name;
+ }
+
+ /* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
+ to MAP. */
+
+ void
+ allocate_ssa_names (bitmap definitions, htab_t *map)
+ {
+ tree name;
+ struct ssa_name_map_entry *entry;
+ PTR *slot;
+ unsigned ver;
+
+ if (!*map)
+ *map = htab_create (10, ssa_name_map_entry_hash,
+ ssa_name_map_entry_eq, free);
+ EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver,
+ {
+ name = ssa_name (ver);
+ slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
+ INSERT);
+ if (*slot)
+ entry = *slot;
+ else
+ {
+ entry = xmalloc (sizeof (struct ssa_name_map_entry));
+ entry->from_name = name;
+ *slot = entry;
+ }
+ entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
+ });
+ }
+
+ /* Rewrite the definition DEF in statement STMT to new ssa name as specified
+ by the mapping MAP. */
+
+ static void
+ rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
+ {
+ tree name = DEF_FROM_PTR (def);
+ struct ssa_name_map_entry *entry;
+
+ if (TREE_CODE (name) != SSA_NAME)
+ abort ();
+
+ entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
+ if (!entry)
+ return;
+
+ SET_DEF (def, entry->to_name);
+ SSA_NAME_DEF_STMT (entry->to_name) = stmt;
+ }
+
+ /* Rewrite the USE to new ssa name as specified by the mapping MAP. */
+
+ static void
+ rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
+ {
+ tree name = USE_FROM_PTR (use);
+ struct ssa_name_map_entry *entry;
+
+ if (TREE_CODE (name) != SSA_NAME)
+ return;
+
+ entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
+ if (!entry)
+ return;
+
+ SET_USE (use, entry->to_name);
+ }
+
+ /* Rewrite the ssa names in basic block BB to new ones as specified by the
+ mapping MAP. */
+
+ void
+ rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
+ {
+ unsigned i;
+ edge e;
+ tree phi, stmt;
+ block_stmt_iterator bsi;
+ use_optype uses;
+ vuse_optype vuses;
+ def_optype defs;
+ v_may_def_optype v_may_defs;
+ v_must_def_optype v_must_defs;
+ stmt_ann_t ann;
+
+ for (e = bb->pred; e; e = e->pred_next)
+ if (e->flags & EDGE_ABNORMAL)
+ break;
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ {
+ rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
+ if (e)
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
+ }
+
+ 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++)
+ rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
+
+ defs = DEF_OPS (ann);
+ for (i = 0; i < NUM_DEFS (defs); i++)
+ rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ {
+ rewrite_to_new_ssa_names_use
+ (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
+ rewrite_to_new_ssa_names_def
+ (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
+ }
+
+ v_must_defs = V_MUST_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
+ rewrite_to_new_ssa_names_def
+ (V_MUST_DEF_OP_PTR (v_must_defs, i), stmt, map);
+ }
+
+ for (e = bb->succ; e; e = e->succ_next)
+ for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ {
+ rewrite_to_new_ssa_names_use
+ (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
+
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
+ }
+ }
+ }
+
+ /* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
+ by the mapping MAP. */
+
+ void
+ rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
+ {
+ unsigned r;
+
+ for (r = 0; r < n_region; r++)
+ rewrite_to_new_ssa_names_bb (region[r], map);
+ }
+
+ /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
+ important exit edge EXIT. By important we mean that no SSA name defined
+ inside region is live over the other exit edges of the region. All entry
+ edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
+ to the duplicate of the region. SSA form, dominance and loop information
+ is updated. The new basic blocks are stored to REGION_COPY in the same
+ order as they had in REGION, provided that REGION_COPY is not NULL.
+ The function returns false if it is unable to copy the region,
+ true otherwise. */
+
+ bool
+ tree_duplicate_sese_region (edge entry, edge exit,
+ basic_block *region, unsigned n_region,
+ basic_block *region_copy)
+ {
+ unsigned i, n_doms, ver;
+ bool free_region_copy = false, copying_header = false;
+ struct loop *loop = entry->dest->loop_father;
+ edge exit_copy;
+ bitmap definitions;
+ tree phi, var;
+ basic_block *doms;
+ htab_t ssa_name_map = NULL;
+
+ if (!can_copy_bbs_p (region, n_region))
+ return false;
+
+ /* Some sanity checking. Note that we do not check for all possible
+ missuses of the functions. I.e. if you ask to copy something weird,
+ it will work, but the state of structures probably will not be
+ correct. */
+
+ for (i = 0; i < n_region; i++)
+ {
+ /* We do not handle subloops, i.e. all the blocks must belong to the
+ same loop. */
+ if (region[i]->loop_father != loop)
+ return false;
+
+ if (region[i] != entry->dest
+ && region[i] == loop->header)
+ return false;
+ }
+
+ loop->copy = loop;
+
+ /* In case the function is used for loop header copying (which is the primary
+ use), ensure that EXIT and its copy will be new latch and entry edges. */
+ if (loop->header == entry->dest)
+ {
+ copying_header = true;
+ loop->copy = loop->outer;
+
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
+ return false;
+
+ for (i = 0; i < n_region; i++)
+ if (region[i] != exit->src
+ && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
+ return false;
+ }
+
+ if (!region_copy)
+ {
+ region_copy = xmalloc (sizeof (basic_block) * n_region);
+ free_region_copy = true;
+ }
+
+ if (any_marked_for_rewrite_p ())
+ abort ();
+
+ /* Record blocks outside the region that are duplicated by something
+ inside. */
+ doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
+
+ copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
+ definitions = marked_ssa_names ();
+
+ if (copying_header)
+ {
+ loop->header = exit->dest;
+ loop->latch = exit->src;
+ }
+
+ /* Redirect the entry and add the phi node arguments. */
+ if (!redirect_edge_and_branch (entry, entry->dest->rbi->copy))
+ abort ();
+ for (phi = phi_nodes (entry->dest), var = PENDING_STMT (entry);
+ phi;
+ phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
+ add_phi_arg (&phi, TREE_VALUE (var), entry);
+ PENDING_STMT (entry) = NULL;
+
+ /* Concerning updating of dominators: We must recount dominators
+ for entry block and its copy. Anything that is outside of the region, but
+ was dominated by something inside needs recounting as well. */
+ set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
+ doms[n_doms++] = entry->dest->rbi->original;
+ iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
+ free (doms);
+
+ /* Add the other phi node arguments. */
+ add_phi_args_after_copy (region_copy, n_region);
+
+ /* Add phi nodes for definitions at exit. TODO -- once we have immediate
+ uses, it should be possible to emit phi nodes just for definitions that
+ are used outside region. */
+ EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver,
+ {
+ tree name = ssa_name (ver);
+
+ phi = create_phi_node (name, exit->dest);
+ add_phi_arg (&phi, name, exit);
+ add_phi_arg (&phi, name, exit_copy);
+
+ SSA_NAME_DEF_STMT (name) = phi;
+ });
+
+ /* And create new definitions inside region and its copy. TODO -- once we
+ have immediate uses, it might be better to leave definitions in region
+ unchanged, create new ssa names for phi nodes on exit, and rewrite
+ the uses, to avoid changing the copied region. */
+ allocate_ssa_names (definitions, &ssa_name_map);
+ rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
+ allocate_ssa_names (definitions, &ssa_name_map);
+ rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
+ htab_delete (ssa_name_map);
+
+ if (free_region_copy)
+ free (region_copy);
+
+ unmark_all_for_rewrite ();
+ BITMAP_XFREE (definitions);
+
+ return true;
+ }
/* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.30
diff -c -3 -p -r2.30 tree-flow.h
*** tree-flow.h 4 Aug 2004 20:37:38 -0000 2.30
--- tree-flow.h 5 Aug 2004 09:36:04 -0000
*************** extern void compute_dominance_frontiers
*** 493,498 ****
--- 493,505 ----
extern void verify_stmts (void);
extern tree tree_block_label (basic_block bb);
extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
+ extern bool tree_duplicate_sese_region (edge, edge, basic_block *, unsigned,
+ basic_block *);
+ extern void add_phi_args_after_copy_bb (basic_block);
+ extern void add_phi_args_after_copy (basic_block *, unsigned);
+ extern void rewrite_to_new_ssa_names_bb (basic_block, struct htab *);
+ extern void rewrite_to_new_ssa_names (basic_block *, unsigned, htab_t);
+ extern void allocate_ssa_names (bitmap, struct htab **);
extern bool tree_purge_dead_eh_edges (basic_block);
extern bool tree_purge_all_dead_eh_edges (bitmap);
extern tree gimplify_val (block_stmt_iterator *, tree, tree);
*************** tree can_count_iv_in_wider_type (struct
*** 647,652 ****
--- 654,661 ----
void free_numbers_of_iterations_estimates (struct loops *);
void loop_commit_inserts (void);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
+ void rewrite_into_loop_closed_ssa (void);
+ void verify_loop_closed_ssa (void);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
Index: tree-ssa-loop-ch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ch.c,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-ssa-loop-ch.c
*** tree-ssa-loop-ch.c 4 Aug 2004 20:37:38 -0000 2.3
--- tree-ssa-loop-ch.c 5 Aug 2004 09:36:04 -0000
*************** should_duplicate_loop_header_p (basic_bl
*** 99,158 ****
return true;
}
- /* Duplicates destinations of edges in BBS_TO_DUPLICATE. */
-
- static void
- duplicate_blocks (varray_type bbs_to_duplicate)
- {
- unsigned i;
- edge preheader_edge, e, e1;
- basic_block header, new_header;
- tree phi, new_phi, var;
-
- /* TODO: It should be quite easy to keep the dominance information
- up-to-date. */
- free_dominance_info (CDI_DOMINATORS);
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
- {
- preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
- header = preheader_edge->dest;
-
- if (!header->aux)
- abort ();
- header->aux = NULL;
-
- new_header = duplicate_block (header, preheader_edge);
-
- /* Create the phi nodes on on entry to new_header. */
- for (phi = phi_nodes (header), var = PENDING_STMT (preheader_edge);
- phi;
- phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
- {
- new_phi = create_phi_node (PHI_RESULT (phi), new_header);
- add_phi_arg (&new_phi, TREE_VALUE (var), preheader_edge);
- }
- PENDING_STMT (preheader_edge) = NULL;
-
- /* Add the phi arguments to the outgoing edges. */
- for (e = header->succ; e; e = e->succ_next)
- {
- for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next)
- continue;
-
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
- {
- tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
- add_phi_arg (&phi, def, e1);
- }
- }
- }
-
- calculate_dominance_info (CDI_DOMINATORS);
-
- rewrite_ssa_into_ssa ();
- }
-
/* Checks whether LOOP is a do-while style loop. */
static bool
--- 99,104 ----
*************** copy_loop_headers (void)
*** 185,196 ****
unsigned i;
struct loop *loop;
basic_block header;
! edge preheader_edge;
! varray_type bbs_to_duplicate = NULL;
loops = loop_optimizer_init (dump_file);
if (!loops)
return;
/* We do not try to keep the information about irreducible regions
up-to-date. */
--- 131,144 ----
unsigned i;
struct loop *loop;
basic_block header;
! edge exit;
! basic_block *bbs;
! unsigned n_bbs;
loops = loop_optimizer_init (dump_file);
if (!loops)
return;
+ rewrite_into_loop_closed_ssa ();
/* We do not try to keep the information about irreducible regions
up-to-date. */
*************** copy_loop_headers (void)
*** 200,213 ****
verify_loop_structure (loops);
#endif
for (i = 1; i < loops->num; i++)
{
/* Copy at most 20 insns. */
int limit = 20;
loop = loops->parray[i];
! preheader_edge = loop_preheader_edge (loop);
! header = preheader_edge->dest;
/* If the loop is already a do-while style one (either because it was
written as such, or because jump threading transformed it into one),
--- 148,162 ----
verify_loop_structure (loops);
#endif
+ bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
+
for (i = 1; i < loops->num; i++)
{
/* Copy at most 20 insns. */
int limit = 20;
loop = loops->parray[i];
! header = loop->header;
/* If the loop is already a do-while style one (either because it was
written as such, or because jump threading transformed it into one),
*************** copy_loop_headers (void)
*** 220,263 ****
like while (a && b) {...}, where we want to have both of the conditions
copied. TODO -- handle while (a || b) - like cases, by not requiring
the header to have just a single successor and copying up to
! postdominator.
!
! We do not really copy the blocks immediately, so that we do not have
! to worry about updating loop structures, and also so that we do not
! have to rewrite variables out of and into ssa form for each block.
! Instead we just record the block into worklist and duplicate all of
! them at once. */
while (should_duplicate_loop_header_p (header, loop, &limit))
{
- if (!bbs_to_duplicate)
- VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10,
- "bbs_to_duplicate");
- VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge);
- header->aux = &header->aux;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- "Scheduled basic block %d for duplication.\n",
- header->index);
-
/* Find a successor of header that is inside a loop; i.e. the new
header after the condition is copied. */
if (flow_bb_inside_loop_p (loop, header->succ->dest))
! preheader_edge = header->succ;
else
! preheader_edge = header->succ->succ_next;
! header = preheader_edge->dest;
}
- }
! loop_optimizer_finalize (loops, NULL);
! if (bbs_to_duplicate)
! {
! duplicate_blocks (bbs_to_duplicate);
! VARRAY_FREE (bbs_to_duplicate);
}
/* Run cleanup_tree_cfg here regardless of whether we have done anything, so
that we cleanup the blocks created in order to get the loops into a
canonical shape. */
--- 169,224 ----
like while (a && b) {...}, where we want to have both of the conditions
copied. TODO -- handle while (a || b) - like cases, by not requiring
the header to have just a single successor and copying up to
! postdominator. */
!
! exit = NULL;
! n_bbs = 0;
while (should_duplicate_loop_header_p (header, loop, &limit))
{
/* Find a successor of header that is inside a loop; i.e. the new
header after the condition is copied. */
if (flow_bb_inside_loop_p (loop, header->succ->dest))
! exit = header->succ;
else
! exit = header->succ->succ_next;
! bbs[n_bbs++] = header;
! header = exit->dest;
}
! if (!exit)
! continue;
! if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file,
! "Duplicating header of the loop %d up to edge %d->%d.\n",
! loop->num, exit->src->index, exit->dest->index);
!
! /* Ensure that the header will have just the latch as a predecessor
! inside the loop. */
! if (exit->dest->pred->pred_next)
! exit = loop_split_edge_with (exit, NULL)->succ;
!
! if (!tree_duplicate_sese_region (loop_preheader_edge (loop), exit,
! bbs, n_bbs, NULL))
! {
! fprintf (dump_file, "Duplication failed.\n");
! continue;
! }
!
! /* Ensure that the latch and the preheader is simple (we know that they
! are not now, since there was the loop exit condition. */
! loop_split_edge_with (loop_preheader_edge (loop), NULL);
! loop_split_edge_with (loop_latch_edge (loop), NULL);
}
+ free (bbs);
+
+ #ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ #endif
+
+ loop_optimizer_finalize (loops, NULL);
+
/* Run cleanup_tree_cfg here regardless of whether we have done anything, so
that we cleanup the blocks created in order to get the loops into a
canonical shape. */
*************** struct tree_opt_pass pass_ch =
*** 279,285 ****
NULL, /* next */
0, /* static_pass_number */
TV_TREE_CH, /* tv_id */
! PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
--- 240,246 ----
NULL, /* next */
0, /* static_pass_number */
TV_TREE_CH, /* tv_id */
! PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
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 5 Aug 2004 09:36:04 -0000
***************
*** 0 ****
--- 1,339 ----
+ /* 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"
+ #include "cfglayout.h"
+ #include "tree-scalar-evolution.h"
+
+ /* Add exit phis for the USE on EXIT. */
+
+ static void
+ add_exit_phis_edge (basic_block exit, tree use)
+ {
+ tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
+ basic_block def_bb = bb_for_stmt (def_stmt);
+ struct loop *def_loop;
+ edge e;
+
+ /* Check that some of the edges entering the EXIT block exits a loop in
+ that USE is defined. */
+ for (e = exit->pred; e; e = e->pred_next)
+ {
+ def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
+ if (!flow_bb_inside_loop_p (def_loop, e->dest))
+ break;
+ }
+
+ if (!e)
+ return;
+
+ phi = create_phi_node (use, exit);
+
+ for (e = exit->pred; e; e = e->pred_next)
+ add_phi_arg (&phi, use, e);
+
+ SSA_NAME_DEF_STMT (use) = def_stmt;
+ }
+
+ /* Add exit phis for VAR that is used in LIVEIN.
+ Exits of the loops are stored in EXITS. */
+
+ static void
+ add_exit_phis_var (tree var, bitmap livein, bitmap exits)
+ {
+ bitmap def;
+ int index;
+ basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+
+ bitmap_clear_bit (livein, def_bb->index);
+
+ def = BITMAP_XMALLOC ();
+ bitmap_set_bit (def, def_bb->index);
+ compute_global_livein (livein, def);
+ BITMAP_XFREE (def);
+
+ EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index,
+ add_exit_phis_edge (BASIC_BLOCK (index), var));
+ }
+
+ /* Add exit phis for the names marked in NAMES_TO_RENAME.
+ Exits of the loops are stored in EXITS. Sets of blocks where the ssa
+ names are used are stored in USE_BLOCKS. */
+
+ static void
+ add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
+ {
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
+ {
+ add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+ });
+ }
+
+ /* Returns a bitmap of all loop exit edge targets. */
+
+ static bitmap
+ get_loops_exits (void)
+ {
+ bitmap exits = BITMAP_XMALLOC ();
+ basic_block bb;
+ edge e;
+
+ FOR_EACH_BB (bb)
+ {
+ for (e = bb->pred; e; e = e->pred_next)
+ if (e->src != ENTRY_BLOCK_PTR
+ && !flow_bb_inside_loop_p (e->src->loop_father, bb))
+ {
+ bitmap_set_bit (exits, bb->index);
+ break;
+ }
+ }
+
+ return exits;
+ }
+
+ /* For USE in BB, if it is used outside of the loop it is defined in,
+ mark it for rewrite. Record basic block BB where it is used
+ to USE_BLOCKS. */
+
+ static void
+ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
+ {
+ unsigned ver;
+ basic_block def_bb;
+ struct loop *def_loop;
+
+ if (TREE_CODE (use) != SSA_NAME)
+ return;
+
+ ver = SSA_NAME_VERSION (use);
+ def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
+ if (!def_bb)
+ return;
+ def_loop = def_bb->loop_father;
+
+ /* If the definition is not inside loop, it is not interesting. */
+ if (!def_loop->outer)
+ return;
+
+ if (!use_blocks[ver])
+ use_blocks[ver] = BITMAP_XMALLOC ();
+ bitmap_set_bit (use_blocks[ver], bb->index);
+
+ if (!flow_bb_inside_loop_p (def_loop, bb))
+ mark_for_rewrite (use);
+ }
+
+ /* For uses in STMT, mark names that are used outside of the loop they are
+ defined to rewrite. Record the set of blocks in that the ssa
+ names are defined to USE_BLOCKS. */
+
+ static void
+ find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
+ {
+ use_optype uses;
+ vuse_optype vuses;
+ v_may_def_optype v_may_defs;
+ stmt_ann_t ann;
+ unsigned i;
+ basic_block bb = bb_for_stmt (stmt);
+
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ find_uses_to_rename_use (bb, USE_OP (uses, i), use_blocks);
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ find_uses_to_rename_use (bb, VUSE_OP (vuses, i),use_blocks);
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i), use_blocks);
+ }
+
+ /* Marks names that are used outside of the loop they are defined in
+ for rewrite. Records the set of blocks in that the ssa
+ names are defined to USE_BLOCKS. */
+
+ static void
+ find_uses_to_rename (bitmap *use_blocks)
+ {
+ basic_block bb;
+ block_stmt_iterator bsi;
+ tree phi;
+ unsigned i;
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
+ PHI_ARG_DEF (phi, i), use_blocks);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+ }
+ }
+
+ /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
+ phi nodes to ensure that no variable is used outside the loop it is
+ defined in.
+
+ This strengthening of the basic ssa form has several advantages:
+
+ 1) Updating it during unrolling/peeling/versioning is trivial, since
+ we do not need to care about the uses outside of the loop.
+ 2) The behavior of all uses of an induction variable is the same.
+ Without this, you need to distinguish the case when the variable
+ is used outside of the loop it is defined in, for example
+
+ for (i = 0; i < 100; i++)
+ {
+ for (j = 0; j < 100; j++)
+ {
+ k = i + j;
+ use1 (k);
+ }
+ use2 (k);
+ }
+
+ Looking from the outer loop with the normal SSA form, the first use of k
+ is not well-behaved, while the second one is an induction variable with
+ base 99 and step 1. */
+
+ void
+ rewrite_into_loop_closed_ssa (void)
+ {
+ bitmap loop_exits = get_loops_exits ();
+ bitmap *use_blocks;
+ unsigned i;
+ bitmap names_to_rename;
+
+ if (any_marked_for_rewrite_p ())
+ abort ();
+
+ use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
+
+ /* Find the uses outside loops. */
+ find_uses_to_rename (use_blocks);
+
+ /* Add the phi nodes on exits of the loops for the names we need to
+ rewrite. */
+ names_to_rename = marked_ssa_names ();
+ add_exit_phis (names_to_rename, use_blocks, loop_exits);
+
+ for (i = 0; i < num_ssa_names; i++)
+ BITMAP_XFREE (use_blocks[i]);
+ free (use_blocks);
+ BITMAP_XFREE (loop_exits);
+ BITMAP_XFREE (names_to_rename);
+
+ /* Do the rewriting. */
+ rewrite_ssa_into_ssa ();
+ }
+
+ /* Check invariants of the loop closed ssa form for the USE in BB. */
+
+ static void
+ check_loop_closed_ssa_use (basic_block bb, tree use)
+ {
+ tree def;
+ basic_block def_bb;
+
+ if (TREE_CODE (use) != SSA_NAME)
+ return;
+
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = bb_for_stmt (def);
+ if (def_bb
+ && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
+ abort ();
+ }
+
+ /* Checks invariants of loop closed ssa form in statement STMT in BB. */
+
+ static void
+ check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
+ {
+ use_optype uses;
+ vuse_optype vuses;
+ v_may_def_optype v_may_defs;
+ stmt_ann_t ann;
+ unsigned i;
+
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ check_loop_closed_ssa_use (bb, USE_OP (uses, i));
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i));
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i));
+ }
+
+ /* Checks that invariants of the loop closed ssa form are preserved. */
+
+ void
+ verify_loop_closed_ssa (void)
+ {
+ basic_block bb;
+ block_stmt_iterator bsi;
+ tree phi;
+ unsigned i;
+
+ verify_ssa ();
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
+ PHI_ARG_DEF (phi, i));
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
+ }
+ }
More information about the Gcc-patches
mailing list