From 42759f1ea05f7893f3bee4adbab74becf1a9f764 Mon Sep 17 00:00:00 2001 From: Zdenek Dvorak Date: Thu, 16 Sep 2004 23:29:43 +0200 Subject: [PATCH] Makefile.in (tree-cfg.o): Add CFGLAYOUT_H dependency. * Makefile.in (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, add_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. * gcc.dg/tree-ssa/copy-headers.c: Update outcome. From-SVN: r87614 --- gcc/ChangeLog | 20 ++ gcc/Makefile.in | 3 +- gcc/basic-block.h | 2 + gcc/dominance.c | 26 ++ gcc/testsuite/ChangeLog | 4 + gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c | 4 +- gcc/tree-cfg.c | 395 ++++++++++++++++++++++++++- gcc/tree-flow.h | 7 + gcc/tree-ssa-loop-ch.c | 132 ++++----- 9 files changed, 504 insertions(+), 89 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1c3e9dd..3d6a38c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,23 @@ +2004-09-16 Zdenek Dvorak + + * Makefile.in (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, add_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. + 2004-09-16 Frank Ch. Eigler * profile.c (branch_prob): Restore support for USE_MAPPED_LOCATION. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 4c60618..44d7140 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1667,7 +1667,8 @@ tree-vn.o : tree-vn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) \ 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_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 diff --git a/gcc/basic-block.h b/gcc/basic-block.h index eed7638..05baeba 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -732,6 +732,8 @@ extern void set_immediate_dominator (enum cdi_direction, basic_block, 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); diff --git a/gcc/dominance.c b/gcc/dominance.c index 5d7f824..2782547 100644 --- a/gcc/dominance.c +++ b/gcc/dominance.c @@ -738,6 +738,32 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs) 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, diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 62c5c37..88ebcdc 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2004-09-16 Zdenek Dvorak + + * gcc.dg/tree-ssa/copy-headers.c: Update outcome. + 2004-09-16 Frank Ch. Eigler * gcc.misc-tests/bprob.exp, g++.dg/bprob/bprob.exp: Iterate tests diff --git a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c index efe831b..4241b40 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/copy-headers.c @@ -11,5 +11,5 @@ void bla (void) foo (i); } -/* There should be a header scheduled for duplication. */ -/* { dg-final { scan-tree-dump-times "Scheduled" 1 "ch"} } */ +/* There should be a header duplicated. */ +/* { dg-final { scan-tree-dump-times "Duplicating header" 1 "ch"} } */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index b8b712b..f7c5155 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -43,6 +43,7 @@ Boston, MA 02111-1307, USA. */ #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. */ @@ -4237,7 +4238,6 @@ tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED) return true; } - /* Create a duplicate of the basic block BB. NOTE: This does not preserve SSA form. */ @@ -4251,10 +4251,15 @@ tree_duplicate_bb (basic_block bb) 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)) @@ -4283,6 +4288,394 @@ tree_duplicate_bb (basic_block bb) 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; + + gcc_assert (e != NULL); + } + + 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); + + gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy)); + 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; + + gcc_assert (TREE_CODE (name) == SSA_NAME); + + 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; + edge redirected; + + 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; + } + + gcc_assert (!any_marked_for_rewrite_p ()); + + /* 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. */ + redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy); + gcc_assert (redirected != NULL); + 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) */ diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 2ae08f2..bdcd4aa 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -495,6 +495,13 @@ extern void clear_special_calls (void); 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); diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c index a03dabd..6ba77da 100644 --- a/gcc/tree-ssa-loop-ch.c +++ b/gcc/tree-ssa-loop-ch.c @@ -98,59 +98,6 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop, 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; - - gcc_assert (header->aux); - 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 @@ -183,12 +130,14 @@ copy_loop_headers (void) unsigned i; struct loop *loop; basic_block header; - edge preheader_edge; - varray_type bbs_to_duplicate = NULL; + 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. */ @@ -198,14 +147,15 @@ copy_loop_headers (void) 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]; - preheader_edge = loop_preheader_edge (loop); - header = preheader_edge->dest; + 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), @@ -218,44 +168,56 @@ copy_loop_headers (void) 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. */ + postdominator. */ + + exit = NULL; + n_bbs = 0; 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; + exit = header->succ; else - preheader_edge = header->succ->succ_next; - header = preheader_edge->dest; + exit = header->succ->succ_next; + bbs[n_bbs++] = header; + header = exit->dest; } - } - loop_optimizer_finalize (loops, NULL); + if (!exit) + continue; - if (bbs_to_duplicate) - { - duplicate_blocks (bbs_to_duplicate); - VARRAY_FREE (bbs_to_duplicate); + 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. */ @@ -277,7 +239,7 @@ struct tree_opt_pass pass_ch = NULL, /* next */ 0, /* static_pass_number */ TV_TREE_CH, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ -- 2.7.4