diff options
Diffstat (limited to 'gcc/tree-ssa-loop-manip.c')
| -rw-r--r-- | gcc/tree-ssa-loop-manip.c | 1020 |
1 files changed, 1020 insertions, 0 deletions
diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c new file mode 100644 index 00000000000..5102cf3b349 --- /dev/null +++ b/gcc/tree-ssa-loop-manip.c @@ -0,0 +1,1020 @@ +/* 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" + +static basic_block lv_adjust_loop_entry_edge (basic_block, basic_block, edge, + tree); +static void lv_update_pending_stmts (edge e); +static void lv_adjust_loop_header_phi (basic_block, basic_block, basic_block, + edge); + +/* 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++) + { + tree nlist; + 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); + } + } + + /* neverse phi nodes to keep them in original order. */ + nlist = nreverse (phi_nodes (bb)); + set_phi_nodes (bb, nlist); + } + + 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; + ssa_name_ann_t ann; + tree *new_names; + bool abnormal; + + for (; definitions; definitions = TREE_CHAIN (definitions)) + { + def = TREE_VALUE (definitions); + ann = get_ssa_name_ann (def); + new_names = xmalloc (sizeof (tree) * (ndupl + 1)); + ann->common.aux = new_names; + + abnormal = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def); + for (i = 0; i <= ndupl; i++) + { + new_names[i] = duplicate_ssa_name (def, SSA_NAME_DEF_STMT (def)); + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_names[i]) = abnormal; + } + } +} + +/* 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) +{ + ssa_name_ann_t ann; + tree *new_names; + + if (TREE_CODE (*op_p) != SSA_NAME) + return; + + ann = ssa_name_ann (*op_p); + new_names = ann ? ann->common.aux : 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. The original ssa names + are released. */ + +static void +free_new_names (tree definitions) +{ + tree def; + ssa_name_ann_t ann; + + for (; definitions; definitions = TREE_CHAIN (definitions)) + { + def = TREE_VALUE (definitions); + ann = ssa_name_ann (def); + + free (ann->common.aux); + ann->common.aux = NULL; + + 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; +} + +/* Extends phi nodes on EXIT to the newly created edges. */ + +static void +extend_exit_phi_nodes (unsigned first_new_block, edge exit) +{ + basic_block exit_block = exit->dest; + edge ae; + tree phi, def; + + for (phi = phi_nodes (exit_block); phi; phi = TREE_CHAIN (phi)) + { + def = phi_element_for_edge (phi, exit)->def; + + for (ae = exit_block->pred; ae; ae = ae->pred_next) + { + if (ae->src->index < (int) first_new_block) + continue; + + if (ae->src->rbi->original != exit->src) + continue; + + add_phi_arg (&phi, def, ae); + } + } +} + +/* 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 bb; + unsigned i; + bool peeling = (e != loop_latch_edge (loop)); + edge latch, latch_copy; + tree phi, arg, map, def; + tree definitions; + edge *exits; + unsigned n_exits; + + if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) + return false; + if (!(loops->state & LOOPS_HAVE_PREHEADERS)) + return false; + +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif + + exits = get_loop_exit_edges (loop, &n_exits); + definitions = collect_defs (loop); + + 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 (); + + /* Extend exit phi nodes. */ + for (i = 0; i < n_exits; i++) + extend_exit_phi_nodes (first_new_block, exits[i]); + free (exits); + + /* Copy the phi nodes. */ + copy_phi_nodes (loop, first_new_block, peeling); + + /* Rename the variables. */ + rename_variables (first_new_block); + free_new_names (definitions); + + /* 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); + } + +#ifdef ENABLE_CHECKING + verify_loop_closed_ssa (); +#endif + + 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 (); + } +} + +/*--------------------------------------------------------------------------- + Loop versioning + ---------------------------------------------------------------------------*/ + +/* Adjust entry edge for lv. + + e is a incoming edge. + + --- edge e ---- > [second_head] + + Split it and insert new conditional expression and adjust edges. + + --- edge e ---> [cond expr] ---> [first_head] + | + +---------> [second_head] + +*/ + +static basic_block +lv_adjust_loop_entry_edge (basic_block first_head, + basic_block second_head, + edge e, + tree cond_expr) +{ + block_stmt_iterator bsi; + basic_block orig_head = e->src; + basic_block new_head = NULL; + tree goto1 = NULL_TREE; + tree goto2 = NULL_TREE; + tree new_cond_expr = NULL_TREE; + edge e0, e1; + + /* Split edge 'e'. This will create a new basic block, where we can + insert conditioanl expr. */ + new_head = split_edge (e); + set_immediate_dominator (CDI_DOMINATORS, new_head, orig_head); + + /* Build new conditional expr */ + goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head)); + goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head)); + new_cond_expr = build (COND_EXPR, void_type_node, cond_expr, goto1, goto2); + + /* Add new cond. in new head. */ + bsi = bsi_start (new_head); + bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT); + + /* Adjust edges appropriately to connect new head with first head + as well as second head. */ + e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE); + set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); + make_edge (new_head, second_head, EDGE_FALSE_VALUE); + set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); + + /* Adjust loop header phi nodes. */ + lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); + + /* When edge 'e' was split, it created a fall through edge + from new head to second head. Above created FALSE edge + from new head to second head and now we do not need the + fall through edge. */ + for (e0 = new_head->succ; e0; e0 = e0->succ_next) + if (e0->dest == second_head) + e0->flags &= ~EDGE_FALLTHRU; + + return new_head; +} + +/* Add phi args using PENDINT_STMT list. */ + +static void +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)) + { + def = TREE_VALUE (arg); + add_phi_arg (&phi, def, e); + } + + PENDING_STMT (e) = NULL; +} + +/* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy + of 'first'. Both of them are dominated by 'new_head' basic block. When + 'new_head' was created by 'second's incoming edge it received phi arguments + on the edge by split_edge(). Later, additional edge 'e' was created to + connect 'new_head' and 'first'. Now this routnine adds phi args on this + additional edge 'e' that new_head to second edge received as part of edge + splitting. +*/ + +static void +lv_adjust_loop_header_phi (basic_block first, basic_block second, + basic_block new_head, edge e) +{ + 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++) + { + if (PHI_ARG_EDGE (phi2, i)->src == new_head) + { + tree def = PHI_ARG_DEF (phi2, i); + add_phi_arg (&phi1, def, e); + } + } + } +} + + +/* Main entry point for Loop Versioning transformation. + +This transformation given a condition and a loop, creates +-if (condition) { loop_copy1 } else { loop_copy2 }, +where loop_copy1 is the loop transformed in one way, and loop_copy2 +is the loop transformed in another way (or unchanged). 'condition' +may be a run time test for things that were not resolved by static +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; + + /* CHECKME: Loop versioning does not handle nested loop at this point. */ + if (loop->inner) + return NULL; + + /* Record entry and latch edges for the loop */ + entry = loop_preheader_edge (loop); + + /* Note down head of loop as first_head. */ + first_head = entry->dest; + + /* Duplicate loop. */ + irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; + entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; + if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1, + NULL, NULL, NULL, NULL, 0)) + { + entry->flags |= irred_flag; + return NULL; + } + + /* After duplication entry edge now points to new loop head block. + Note down new head as second_head. */ + 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)); + + /* Adjust irreducible flag. */ + if (irred_flag) + { + (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP; + loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; + loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; + (*condition_bb)->pred->flags |= EDGE_IRREDUCIBLE_LOOP; + } + + /* 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 (loop_preheader_edge (loop), NULL); + loop_split_edge_with (loop_preheader_edge (nloop), NULL); + + /* Ensure that the latch has just a single successor. */ + loop_split_edge_with (loop_latch_edge (loop), NULL); + loop_split_edge_with (loop_latch_edge (nloop), NULL); + + 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) +{ + struct loop *loop; + unsigned i; + tree cond_expr; + + for (i = 1; i < loops->num; i = i+ 2) + { + struct loop *nloop; + basic_block condition_bb; + loop = loops->parray[i]; + + if (!loop) + continue; + + cond_expr = build (EQ_EXPR, boolean_type_node, + 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); + } + } + +} + +/* 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. SSA_NAMES is the array of ssa + names indexed by their versions. */ + +static void +add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits, + tree *ssa_names) +{ + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, + { + add_exit_phis_var (ssa_names[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 in NAMES_TO_RENAME. Record basic block BB where it is used + to USE_BLOCKS, and the ssa name itself to NAMES. */ + +static void +find_uses_to_rename_use (basic_block bb, tree use, bitmap names_to_rename, + bitmap *use_blocks, tree *names) +{ + 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; + + names[ver] = use; + 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)) + bitmap_set_bit (names_to_rename, ver); +} + +/* For uses in STMT, mark names that are used outside of the loop they are + defined in in NAMES_TO_RENAME. Record the set of blocks in that the ssa + names are defined to USE_BLOCKS, and the names themselves to NAMES. */ + +static void +find_uses_to_rename_stmt (tree stmt, bitmap names_to_rename, + bitmap *use_blocks, tree *names) +{ + use_optype uses; + vuse_optype vuses; + vdef_optype vdefs; + 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), + names_to_rename, use_blocks, names); + + vuses = VUSE_OPS (ann); + for (i = 0; i < NUM_VUSES (vuses); i++) + find_uses_to_rename_use (bb, VUSE_OP (vuses, i), + names_to_rename, use_blocks, names); + + vdefs = VDEF_OPS (ann); + for (i = 0; i < NUM_VDEFS (vdefs); i++) + find_uses_to_rename_use (bb, VDEF_OP (vdefs, i), + names_to_rename, use_blocks, names); +} + +/* Marks names that are used outside of the loop they are defined in + in NAMES_TO_RENAME. Records the set of blocks in that the ssa + names are defined to USE_BLOCKS, and the names themselves to NAMES. */ + +static void +find_uses_to_rename (bitmap names_to_rename, bitmap *use_blocks, tree *names) +{ + 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), + names_to_rename, use_blocks, names); + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + find_uses_to_rename_stmt (bsi_stmt (bsi), + names_to_rename, use_blocks, names); + } +} + +/* 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 strenghtening 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 names_to_rename = BITMAP_XMALLOC (); + bitmap loop_exits = get_loops_exits (); + bitmap *use_blocks; + tree *ssa_names; + unsigned i; + + tree_ssa_dce_no_cfg_changes (); + + use_blocks = xcalloc (highest_ssa_version, sizeof (bitmap)); + ssa_names = xcalloc (highest_ssa_version, sizeof (tree)); + + /* Find the uses outside loops. */ + find_uses_to_rename (names_to_rename, use_blocks, ssa_names); + + /* Add the phi nodes on exits of the loops for the names we need to + rewrite. */ + add_exit_phis (names_to_rename, use_blocks, loop_exits, ssa_names); + + for (i = 0; i < highest_ssa_version; i++) + BITMAP_XFREE (use_blocks[i]); + free (use_blocks); + free (ssa_names); + BITMAP_XFREE (loop_exits); + + /* Do the rewriting. */ + rewrite_ssa_into_ssa (names_to_rename); + BITMAP_XFREE (names_to_rename); + BITMAP_XFREE (loop_exits); +} + +/* 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; + vdef_optype vdefs; + 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)); + + vdefs = VDEF_OPS (ann); + for (i = 0; i < NUM_VDEFS (vdefs); i++) + check_loop_closed_ssa_use (bb, VDEF_OP (vdefs, 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)); + } +} |