| /* Single entry single exit control flow regions. |
| Copyright (C) 2008, 2009, 2010 |
| Free Software Foundation, Inc. |
| Contributed by Jan Sjodin <jan.sjodin@amd.com> and |
| Sebastian Pop <sebastian.pop@amd.com>. |
| |
| 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 3, 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 COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "tm.h" |
| #include "ggc.h" |
| #include "tree.h" |
| #include "rtl.h" |
| #include "basic-block.h" |
| #include "diagnostic.h" |
| #include "tree-flow.h" |
| #include "toplev.h" |
| #include "tree-dump.h" |
| #include "timevar.h" |
| #include "cfgloop.h" |
| #include "tree-chrec.h" |
| #include "tree-data-ref.h" |
| #include "tree-scalar-evolution.h" |
| #include "tree-pass.h" |
| #include "domwalk.h" |
| #include "value-prof.h" |
| #include "pointer-set.h" |
| #include "gimple.h" |
| #include "sese.h" |
| |
| /* Print to stderr the element ELT. */ |
| |
| static void |
| debug_rename_elt (rename_map_elt elt) |
| { |
| fprintf (stderr, "("); |
| print_generic_expr (stderr, elt->old_name, 0); |
| fprintf (stderr, ", "); |
| print_generic_expr (stderr, elt->expr, 0); |
| fprintf (stderr, ")\n"); |
| } |
| |
| /* Helper function for debug_rename_map. */ |
| |
| static int |
| debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) |
| { |
| struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; |
| debug_rename_elt (entry); |
| return 1; |
| } |
| |
| /* Print to stderr all the elements of MAP. */ |
| |
| void |
| debug_rename_map (htab_t map) |
| { |
| htab_traverse (map, debug_rename_map_1, NULL); |
| } |
| |
| /* Computes a hash function for database element ELT. */ |
| |
| hashval_t |
| rename_map_elt_info (const void *elt) |
| { |
| return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name); |
| } |
| |
| /* Compares database elements E1 and E2. */ |
| |
| int |
| eq_rename_map_elts (const void *e1, const void *e2) |
| { |
| const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1; |
| const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2; |
| |
| return (elt1->old_name == elt2->old_name); |
| } |
| |
| |
| |
| /* Print to stderr the element ELT. */ |
| |
| static void |
| debug_ivtype_elt (ivtype_map_elt elt) |
| { |
| fprintf (stderr, "(%s, ", elt->cloog_iv); |
| print_generic_expr (stderr, elt->type, 0); |
| fprintf (stderr, ")\n"); |
| } |
| |
| /* Helper function for debug_ivtype_map. */ |
| |
| static int |
| debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) |
| { |
| struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot; |
| debug_ivtype_elt (entry); |
| return 1; |
| } |
| |
| /* Print to stderr all the elements of MAP. */ |
| |
| void |
| debug_ivtype_map (htab_t map) |
| { |
| htab_traverse (map, debug_ivtype_map_1, NULL); |
| } |
| |
| /* Computes a hash function for database element ELT. */ |
| |
| hashval_t |
| ivtype_map_elt_info (const void *elt) |
| { |
| return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv); |
| } |
| |
| /* Compares database elements E1 and E2. */ |
| |
| int |
| eq_ivtype_map_elts (const void *e1, const void *e2) |
| { |
| const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1; |
| const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2; |
| |
| return (elt1->cloog_iv == elt2->cloog_iv); |
| } |
| |
| |
| |
| /* Record LOOP as occuring in REGION. */ |
| |
| static void |
| sese_record_loop (sese region, loop_p loop) |
| { |
| if (sese_contains_loop (region, loop)) |
| return; |
| |
| bitmap_set_bit (SESE_LOOPS (region), loop->num); |
| VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop); |
| } |
| |
| /* Build the loop nests contained in REGION. Returns true when the |
| operation was successful. */ |
| |
| void |
| build_sese_loop_nests (sese region) |
| { |
| unsigned i; |
| basic_block bb; |
| struct loop *loop0, *loop1; |
| |
| FOR_EACH_BB (bb) |
| if (bb_in_sese_p (bb, region)) |
| { |
| struct loop *loop = bb->loop_father; |
| |
| /* Only add loops if they are completely contained in the SCoP. */ |
| if (loop->header == bb |
| && bb_in_sese_p (loop->latch, region)) |
| sese_record_loop (region, loop); |
| } |
| |
| /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It |
| can be the case that an inner loop is inserted before an outer |
| loop. To avoid this, semi-sort once. */ |
| for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++) |
| { |
| if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1) |
| break; |
| |
| loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1); |
| if (loop0->num > loop1->num) |
| { |
| VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1); |
| VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0); |
| } |
| } |
| } |
| |
| /* For a USE in BB, if BB is outside REGION, mark the USE in the |
| LIVEOUTS set. */ |
| |
| static void |
| sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb, |
| tree use) |
| { |
| unsigned ver; |
| basic_block def_bb; |
| |
| if (TREE_CODE (use) != SSA_NAME) |
| return; |
| |
| ver = SSA_NAME_VERSION (use); |
| def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
| |
| if (!def_bb |
| || !bb_in_sese_p (def_bb, region) |
| || bb_in_sese_p (bb, region)) |
| return; |
| |
| bitmap_set_bit (liveouts, ver); |
| } |
| |
| /* Marks for rewrite all the SSA_NAMES defined in REGION and that are |
| used in BB that is outside of the REGION. */ |
| |
| static void |
| sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb) |
| { |
| gimple_stmt_iterator bsi; |
| edge e; |
| edge_iterator ei; |
| ssa_op_iter iter; |
| use_operand_p use_p; |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) |
| sese_build_liveouts_use (region, liveouts, bb, |
| PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e)); |
| |
| for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) |
| { |
| gimple stmt = gsi_stmt (bsi); |
| |
| if (is_gimple_debug (stmt)) |
| continue; |
| |
| FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) |
| sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); |
| } |
| } |
| |
| /* For a USE in BB, return true if BB is outside REGION and it's not |
| in the LIVEOUTS set. */ |
| |
| static bool |
| sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb, |
| tree use) |
| { |
| unsigned ver; |
| basic_block def_bb; |
| |
| if (TREE_CODE (use) != SSA_NAME) |
| return false; |
| |
| ver = SSA_NAME_VERSION (use); |
| |
| /* If it's in liveouts, the variable will get a new PHI node, and |
| the debug use will be properly adjusted. */ |
| if (bitmap_bit_p (liveouts, ver)) |
| return false; |
| |
| def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); |
| |
| if (!def_bb |
| || !bb_in_sese_p (def_bb, region) |
| || bb_in_sese_p (bb, region)) |
| return false; |
| |
| return true; |
| } |
| |
| /* Reset debug stmts that reference SSA_NAMES defined in REGION that |
| are not marked as liveouts. */ |
| |
| static void |
| sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb) |
| { |
| gimple_stmt_iterator bsi; |
| ssa_op_iter iter; |
| use_operand_p use_p; |
| |
| for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) |
| { |
| gimple stmt = gsi_stmt (bsi); |
| |
| if (!is_gimple_debug (stmt)) |
| continue; |
| |
| FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) |
| if (sese_bad_liveouts_use (region, liveouts, bb, |
| USE_FROM_PTR (use_p))) |
| { |
| gimple_debug_bind_reset_value (stmt); |
| update_stmt (stmt); |
| break; |
| } |
| } |
| } |
| |
| /* Build the LIVEOUTS of REGION: the set of variables defined inside |
| and used outside the REGION. */ |
| |
| static void |
| sese_build_liveouts (sese region, bitmap liveouts) |
| { |
| basic_block bb; |
| |
| FOR_EACH_BB (bb) |
| sese_build_liveouts_bb (region, liveouts, bb); |
| if (MAY_HAVE_DEBUG_INSNS) |
| FOR_EACH_BB (bb) |
| sese_reset_debug_liveouts_bb (region, liveouts, bb); |
| } |
| |
| /* Builds a new SESE region from edges ENTRY and EXIT. */ |
| |
| sese |
| new_sese (edge entry, edge exit) |
| { |
| sese region = XNEW (struct sese_s); |
| |
| SESE_ENTRY (region) = entry; |
| SESE_EXIT (region) = exit; |
| SESE_LOOPS (region) = BITMAP_ALLOC (NULL); |
| SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3); |
| SESE_ADD_PARAMS (region) = true; |
| SESE_PARAMS (region) = VEC_alloc (tree, heap, 3); |
| |
| return region; |
| } |
| |
| /* Deletes REGION. */ |
| |
| void |
| free_sese (sese region) |
| { |
| if (SESE_LOOPS (region)) |
| SESE_LOOPS (region) = BITMAP_ALLOC (NULL); |
| |
| VEC_free (tree, heap, SESE_PARAMS (region)); |
| VEC_free (loop_p, heap, SESE_LOOP_NEST (region)); |
| |
| XDELETE (region); |
| } |
| |
| /* Add exit phis for USE on EXIT. */ |
| |
| static void |
| sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) |
| { |
| gimple phi = create_phi_node (use, exit); |
| |
| create_new_def_for (gimple_phi_result (phi), phi, |
| gimple_phi_result_ptr (phi)); |
| add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); |
| add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); |
| } |
| |
| /* Insert in the block BB phi nodes for variables defined in REGION |
| and used outside the REGION. The code generation moves REGION in |
| the else clause of an "if (1)" and generates code in the then |
| clause that is at this point empty: |
| |
| | if (1) |
| | empty; |
| | else |
| | REGION; |
| */ |
| |
| void |
| sese_insert_phis_for_liveouts (sese region, basic_block bb, |
| edge false_e, edge true_e) |
| { |
| unsigned i; |
| bitmap_iterator bi; |
| bitmap liveouts = BITMAP_ALLOC (NULL); |
| |
| update_ssa (TODO_update_ssa); |
| |
| sese_build_liveouts (region, liveouts); |
| EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) |
| sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); |
| BITMAP_FREE (liveouts); |
| |
| update_ssa (TODO_update_ssa); |
| } |
| |
| /* Get the definition of NAME before the SESE. Keep track of the |
| basic blocks that have been VISITED in a bitmap. */ |
| |
| static tree |
| get_vdef_before_sese (sese region, tree name, sbitmap visited) |
| { |
| unsigned i; |
| gimple stmt = SSA_NAME_DEF_STMT (name); |
| basic_block def_bb = gimple_bb (stmt); |
| |
| if (!def_bb || !bb_in_sese_p (def_bb, region)) |
| return name; |
| |
| if (TEST_BIT (visited, def_bb->index)) |
| return NULL_TREE; |
| |
| SET_BIT (visited, def_bb->index); |
| |
| switch (gimple_code (stmt)) |
| { |
| case GIMPLE_PHI: |
| for (i = 0; i < gimple_phi_num_args (stmt); i++) |
| { |
| tree arg = gimple_phi_arg_def (stmt, i); |
| tree res; |
| |
| if (gimple_bb (SSA_NAME_DEF_STMT (arg)) |
| && def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (arg))->index) |
| continue; |
| |
| res = get_vdef_before_sese (region, arg, visited); |
| if (res) |
| return res; |
| } |
| return NULL_TREE; |
| |
| case GIMPLE_ASSIGN: |
| case GIMPLE_CALL: |
| { |
| use_operand_p use_p = gimple_vuse_op (stmt); |
| tree use = USE_FROM_PTR (use_p); |
| |
| if (def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (use))->index) |
| RESET_BIT (visited, def_bb->index); |
| |
| return get_vdef_before_sese (region, use, visited); |
| } |
| |
| default: |
| return NULL_TREE; |
| } |
| } |
| |
| /* Adjust a virtual phi node PHI that is placed at the end of the |
| generated code for SCOP: |
| |
| | if (1) |
| | generated code from REGION; |
| | else |
| | REGION; |
| |
| The FALSE_E edge comes from the original code, TRUE_E edge comes |
| from the code generated for the SCOP. */ |
| |
| static void |
| sese_adjust_vphi (sese region, gimple phi, edge true_e) |
| { |
| unsigned i; |
| |
| gcc_assert (gimple_phi_num_args (phi) == 2); |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| if (gimple_phi_arg_edge (phi, i) == true_e) |
| { |
| tree true_arg, false_arg, before_scop_arg; |
| sbitmap visited; |
| |
| true_arg = gimple_phi_arg_def (phi, i); |
| if (!SSA_NAME_IS_DEFAULT_DEF (true_arg)) |
| return; |
| |
| false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0); |
| if (SSA_NAME_IS_DEFAULT_DEF (false_arg)) |
| return; |
| |
| visited = sbitmap_alloc (last_basic_block); |
| sbitmap_zero (visited); |
| before_scop_arg = get_vdef_before_sese (region, false_arg, visited); |
| gcc_assert (before_scop_arg != NULL_TREE); |
| SET_PHI_ARG_DEF (phi, i, before_scop_arg); |
| sbitmap_free (visited); |
| } |
| } |
| |
| /* Returns the expression associated to OLD_NAME in MAP. */ |
| |
| static tree |
| get_rename (htab_t map, tree old_name) |
| { |
| struct rename_map_elt_s tmp; |
| PTR *slot; |
| |
| gcc_assert (TREE_CODE (old_name) == SSA_NAME); |
| tmp.old_name = old_name; |
| slot = htab_find_slot (map, &tmp, NO_INSERT); |
| |
| if (slot && *slot) |
| return ((rename_map_elt) *slot)->expr; |
| |
| return old_name; |
| } |
| |
| /* Register in MAP the rename tuple (OLD_NAME, EXPR). */ |
| |
| void |
| set_rename (htab_t map, tree old_name, tree expr) |
| { |
| struct rename_map_elt_s tmp; |
| PTR *slot; |
| |
| if (old_name == expr) |
| return; |
| |
| tmp.old_name = old_name; |
| slot = htab_find_slot (map, &tmp, INSERT); |
| |
| if (!slot) |
| return; |
| |
| if (*slot) |
| free (*slot); |
| |
| *slot = new_rename_map_elt (old_name, expr); |
| } |
| |
| /* Renames the expression T following the tuples (OLD_NAME, EXPR) in |
| the rename map M. Returns the expression T after renaming. */ |
| |
| static tree |
| rename_variables_in_expr (htab_t m, tree t) |
| { |
| if (!t) |
| return t; |
| |
| if (TREE_CODE (t) == SSA_NAME) |
| return get_rename (m, t); |
| |
| switch (TREE_CODE_LENGTH (TREE_CODE (t))) |
| { |
| case 3: |
| TREE_OPERAND (t, 2) = rename_variables_in_expr (m, TREE_OPERAND (t, 2)); |
| |
| case 2: |
| TREE_OPERAND (t, 1) = rename_variables_in_expr (m, TREE_OPERAND (t, 1)); |
| |
| case 1: |
| TREE_OPERAND (t, 0) = rename_variables_in_expr (m, TREE_OPERAND (t, 0)); |
| |
| default: |
| return t; |
| } |
| } |
| |
| /* Renames all the loop->nb_iterations expressions following the |
| tuples (OLD_NAME, EXPR) in RENAME_MAP. */ |
| |
| void |
| rename_nb_iterations (htab_t rename_map) |
| { |
| loop_iterator li; |
| struct loop *loop; |
| |
| FOR_EACH_LOOP (li, loop, 0) |
| loop->nb_iterations = rename_variables_in_expr (rename_map, |
| loop->nb_iterations); |
| } |
| |
| /* Renames all the parameters of SESE following the tuples (OLD_NAME, |
| EXPR) in RENAME_MAP. */ |
| |
| void |
| rename_sese_parameters (htab_t rename_map, sese region) |
| { |
| int i; |
| tree p; |
| |
| for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) |
| VEC_replace (tree, SESE_PARAMS (region), i, |
| rename_variables_in_expr (rename_map, p)); |
| } |
| |
| /* Adjusts the phi nodes in the block BB for variables defined in |
| SCOP_REGION and used outside the SCOP_REGION. The code generation |
| moves SCOP_REGION in the else clause of an "if (1)" and generates |
| code in the then clause: |
| |
| | if (1) |
| | generated code from REGION; |
| | else |
| | REGION; |
| |
| To adjust the phi nodes after the condition, the RENAME_MAP is |
| used. */ |
| |
| void |
| sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb, |
| edge false_e, edge true_e) |
| { |
| gimple_stmt_iterator si; |
| |
| for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) |
| { |
| unsigned i; |
| unsigned false_i = 0; |
| gimple phi = gsi_stmt (si); |
| tree res = gimple_phi_result (phi); |
| |
| if (!is_gimple_reg (res)) |
| { |
| sese_adjust_vphi (region, phi, true_e); |
| continue; |
| } |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| if (gimple_phi_arg_edge (phi, i) == false_e) |
| { |
| false_i = i; |
| break; |
| } |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| if (gimple_phi_arg_edge (phi, i) == true_e) |
| { |
| tree old_name = gimple_phi_arg_def (phi, false_i); |
| tree expr = get_rename (rename_map, old_name); |
| gimple_seq stmts; |
| |
| gcc_assert (old_name != expr); |
| |
| if (TREE_CODE (expr) != SSA_NAME |
| && is_gimple_reg (old_name)) |
| { |
| tree type = TREE_TYPE (old_name); |
| tree var = create_tmp_var (type, "var"); |
| |
| expr = build2 (MODIFY_EXPR, type, var, expr); |
| expr = force_gimple_operand (expr, &stmts, true, NULL); |
| gsi_insert_seq_on_edge_immediate (true_e, stmts); |
| } |
| |
| SET_PHI_ARG_DEF (phi, i, expr); |
| set_rename (rename_map, old_name, res); |
| } |
| } |
| } |
| |
| /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */ |
| |
| static void |
| rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi) |
| { |
| ssa_op_iter iter; |
| use_operand_p use_p; |
| |
| FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) |
| { |
| tree use = USE_FROM_PTR (use_p); |
| tree expr, type_use, type_expr; |
| gimple_seq stmts; |
| |
| if (TREE_CODE (use) != SSA_NAME) |
| continue; |
| |
| expr = get_rename (map, use); |
| if (use == expr) |
| continue; |
| |
| type_use = TREE_TYPE (use); |
| type_expr = TREE_TYPE (expr); |
| |
| if (type_use != type_expr |
| || (TREE_CODE (expr) != SSA_NAME |
| && is_gimple_reg (use))) |
| { |
| tree var; |
| |
| if (is_gimple_debug (stmt)) |
| { |
| if (gimple_debug_bind_p (stmt)) |
| gimple_debug_bind_reset_value (stmt); |
| else |
| gcc_unreachable (); |
| |
| break; |
| } |
| |
| var = create_tmp_var (type_use, "var"); |
| |
| if (type_use != type_expr) |
| expr = fold_convert (type_use, expr); |
| |
| expr = build2 (MODIFY_EXPR, type_use, var, expr); |
| expr = force_gimple_operand (expr, &stmts, true, NULL); |
| gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT); |
| } |
| |
| replace_exp (use_p, expr); |
| } |
| |
| update_stmt (stmt); |
| } |
| |
| /* Returns true if NAME is a parameter of SESE. */ |
| |
| static bool |
| is_parameter (sese region, tree name) |
| { |
| int i; |
| tree p; |
| |
| for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) |
| if (p == name) |
| return true; |
| |
| return false; |
| } |
| |
| /* Returns true if NAME is an induction variable. */ |
| |
| static bool |
| is_iv (tree name) |
| { |
| return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI; |
| } |
| |
| static void expand_scalar_variables_stmt (gimple, basic_block, sese, |
| htab_t, gimple_stmt_iterator *); |
| static tree |
| expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block, |
| sese, htab_t, gimple_stmt_iterator *); |
| |
| static tree |
| expand_scalar_variables_call (gimple stmt, basic_block bb, sese region, |
| htab_t map, gimple_stmt_iterator *gsi) |
| { |
| int i, nargs = gimple_call_num_args (stmt); |
| VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs); |
| tree fn_type = TREE_TYPE (gimple_call_fn (stmt)); |
| tree fn = gimple_call_fndecl (stmt); |
| tree call_expr, var, lhs; |
| gimple call; |
| |
| for (i = 0; i < nargs; i++) |
| { |
| tree arg = gimple_call_arg (stmt, i); |
| tree t = TREE_TYPE (arg); |
| |
| var = create_tmp_var (t, "var"); |
| arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL, |
| bb, region, map, gsi); |
| arg = build2 (MODIFY_EXPR, t, var, arg); |
| arg = force_gimple_operand_gsi (gsi, arg, true, NULL, |
| true, GSI_SAME_STMT); |
| VEC_quick_push (tree, args, arg); |
| } |
| |
| lhs = gimple_call_lhs (stmt); |
| var = create_tmp_var (TREE_TYPE (lhs), "var"); |
| call_expr = build_call_vec (fn_type, fn, args); |
| call = gimple_build_call_from_tree (call_expr); |
| var = make_ssa_name (var, call); |
| gimple_call_set_lhs (call, var); |
| gsi_insert_before (gsi, call, GSI_SAME_STMT); |
| |
| return var; |
| } |
| |
| /* Copies at GSI all the scalar computations on which the ssa_name OP0 |
| depends on in the SESE: these are all the scalar variables used in |
| the definition of OP0, that are defined outside BB and still in the |
| SESE, i.e. not a parameter of the SESE. The expression that is |
| returned contains only induction variables from the generated code: |
| MAP contains the induction variables renaming mapping, and is used |
| to translate the names of induction variables. */ |
| |
| static tree |
| expand_scalar_variables_ssa_name (tree type, tree op0, basic_block bb, |
| sese region, htab_t map, |
| gimple_stmt_iterator *gsi) |
| { |
| gimple def_stmt; |
| tree new_op; |
| |
| if (is_parameter (region, op0) |
| || is_iv (op0)) |
| return fold_convert (type, get_rename (map, op0)); |
| |
| def_stmt = SSA_NAME_DEF_STMT (op0); |
| |
| /* Check whether we already have a rename for OP0. */ |
| new_op = get_rename (map, op0); |
| |
| if (new_op != op0 |
| && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb) |
| return fold_convert (type, new_op); |
| |
| if (gimple_bb (def_stmt) == bb) |
| { |
| /* If the defining statement is in the basic block already |
| we do not need to create a new expression for it, we |
| only need to ensure its operands are expanded. */ |
| expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi); |
| return fold_convert (type, new_op); |
| } |
| else |
| { |
| if (!gimple_bb (def_stmt) |
| || !bb_in_sese_p (gimple_bb (def_stmt), region)) |
| return fold_convert (type, new_op); |
| |
| switch (gimple_code (def_stmt)) |
| { |
| case GIMPLE_ASSIGN: |
| { |
| tree var0 = gimple_assign_rhs1 (def_stmt); |
| enum tree_code subcode = gimple_assign_rhs_code (def_stmt); |
| tree var1 = gimple_assign_rhs2 (def_stmt); |
| tree type = gimple_expr_type (def_stmt); |
| |
| return expand_scalar_variables_expr (type, var0, subcode, var1, bb, |
| region, map, gsi); |
| } |
| |
| case GIMPLE_CALL: |
| return expand_scalar_variables_call (def_stmt, bb, region, map, gsi); |
| |
| default: |
| gcc_unreachable (); |
| return new_op; |
| } |
| } |
| } |
| |
| /* Copies at GSI all the scalar computations on which the expression |
| OP0 CODE OP1 depends on in the SESE: these are all the scalar |
| variables used in OP0 and OP1, defined outside BB and still defined |
| in the SESE, i.e. not a parameter of the SESE. The expression that |
| is returned contains only induction variables from the generated |
| code: MAP contains the induction variables renaming mapping, and is |
| used to translate the names of induction variables. */ |
| |
| static tree |
| expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, |
| tree op1, basic_block bb, sese region, |
| htab_t map, gimple_stmt_iterator *gsi) |
| { |
| if (TREE_CODE_CLASS (code) == tcc_constant |
| || TREE_CODE_CLASS (code) == tcc_declaration) |
| return op0; |
| |
| /* For data references we have to duplicate also its memory |
| indexing. */ |
| if (TREE_CODE_CLASS (code) == tcc_reference) |
| { |
| switch (code) |
| { |
| case REALPART_EXPR: |
| case IMAGPART_EXPR: |
| { |
| tree op = TREE_OPERAND (op0, 0); |
| tree res = expand_scalar_variables_expr |
| (type, op, TREE_CODE (op), NULL, bb, region, map, gsi); |
| return build1 (code, type, res); |
| } |
| |
| case INDIRECT_REF: |
| { |
| tree old_name = TREE_OPERAND (op0, 0); |
| tree expr = expand_scalar_variables_ssa_name |
| (type, old_name, bb, region, map, gsi); |
| |
| if (TREE_CODE (expr) != SSA_NAME |
| && is_gimple_reg (old_name)) |
| { |
| tree type = TREE_TYPE (old_name); |
| tree var = create_tmp_var (type, "var"); |
| |
| expr = build2 (MODIFY_EXPR, type, var, expr); |
| expr = force_gimple_operand_gsi (gsi, expr, true, NULL, |
| true, GSI_SAME_STMT); |
| } |
| |
| return fold_build1 (code, type, expr); |
| } |
| |
| case ARRAY_REF: |
| { |
| tree op00 = TREE_OPERAND (op0, 0); |
| tree op01 = TREE_OPERAND (op0, 1); |
| tree op02 = TREE_OPERAND (op0, 2); |
| tree op03 = TREE_OPERAND (op0, 3); |
| tree base = expand_scalar_variables_expr |
| (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region, |
| map, gsi); |
| tree subscript = expand_scalar_variables_expr |
| (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region, |
| map, gsi); |
| |
| return build4 (ARRAY_REF, type, base, subscript, op02, op03); |
| } |
| |
| case COMPONENT_REF: |
| return op0; |
| |
| default: |
| /* The above cases should catch everything. */ |
| gcc_unreachable (); |
| } |
| } |
| |
| if (TREE_CODE_CLASS (code) == tcc_unary) |
| { |
| tree op0_type = TREE_TYPE (op0); |
| enum tree_code op0_code = TREE_CODE (op0); |
| tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code, |
| NULL, bb, region, map, gsi); |
| |
| return fold_build1 (code, type, op0_expr); |
| } |
| |
| if (TREE_CODE_CLASS (code) == tcc_binary |
| || TREE_CODE_CLASS (code) == tcc_comparison) |
| { |
| tree op0_type = TREE_TYPE (op0); |
| enum tree_code op0_code = TREE_CODE (op0); |
| tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code, |
| NULL, bb, region, map, gsi); |
| tree op1_type = TREE_TYPE (op1); |
| enum tree_code op1_code = TREE_CODE (op1); |
| tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code, |
| NULL, bb, region, map, gsi); |
| |
| return fold_build2 (code, type, op0_expr, op1_expr); |
| } |
| |
| if (code == SSA_NAME) |
| return expand_scalar_variables_ssa_name (type, op0, bb, region, map, gsi); |
| |
| if (code == ADDR_EXPR) |
| { |
| tree op00 = TREE_OPERAND (op0, 0); |
| |
| if (handled_component_p (op00) |
| && TREE_CODE (op00) == ARRAY_REF) |
| { |
| tree e = expand_scalar_variables_expr (TREE_TYPE (op00), op00, |
| TREE_CODE (op00), |
| NULL, bb, region, map, gsi); |
| return fold_build1 (code, TREE_TYPE (op0), e); |
| } |
| |
| return op0; |
| } |
| |
| gcc_unreachable (); |
| return NULL; |
| } |
| |
| /* Copies at the beginning of BB all the scalar computations on which |
| STMT depends on in the SESE: these are all the scalar variables used |
| in STMT, defined outside BB and still defined in the SESE, i.e. not a |
| parameter of the SESE. The expression that is returned contains |
| only induction variables from the generated code: MAP contains the |
| induction variables renaming mapping, and is used to translate the |
| names of induction variables. */ |
| |
| static void |
| expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region, |
| htab_t map, gimple_stmt_iterator *gsi) |
| { |
| ssa_op_iter iter; |
| use_operand_p use_p; |
| |
| FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) |
| { |
| tree use = USE_FROM_PTR (use_p); |
| tree type = TREE_TYPE (use); |
| enum tree_code code = TREE_CODE (use); |
| tree use_expr; |
| |
| if (!is_gimple_reg (use)) |
| continue; |
| |
| /* Don't expand USE if we already have a rename for it. */ |
| use_expr = get_rename (map, use); |
| if (use_expr != use) |
| continue; |
| |
| use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb, |
| region, map, gsi); |
| use_expr = fold_convert (type, use_expr); |
| |
| if (use_expr == use) |
| continue; |
| |
| if (is_gimple_debug (stmt)) |
| { |
| if (gimple_debug_bind_p (stmt)) |
| gimple_debug_bind_reset_value (stmt); |
| else |
| gcc_unreachable (); |
| |
| break; |
| } |
| |
| if (TREE_CODE (use_expr) != SSA_NAME) |
| { |
| tree var = create_tmp_var (type, "var"); |
| |
| use_expr = build2 (MODIFY_EXPR, type, var, use_expr); |
| use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL, |
| true, GSI_SAME_STMT); |
| } |
| |
| replace_exp (use_p, use_expr); |
| } |
| |
| update_stmt (stmt); |
| } |
| |
| /* Copies at the beginning of BB all the scalar computations on which |
| BB depends on in the SESE: these are all the scalar variables used |
| in BB, defined outside BB and still defined in the SESE, i.e. not a |
| parameter of the SESE. The expression that is returned contains |
| only induction variables from the generated code: MAP contains the |
| induction variables renaming mapping, and is used to translate the |
| names of induction variables. */ |
| |
| static void |
| expand_scalar_variables (basic_block bb, sese region, htab_t map) |
| { |
| gimple_stmt_iterator gsi; |
| |
| for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);) |
| { |
| gimple stmt = gsi_stmt (gsi); |
| expand_scalar_variables_stmt (stmt, bb, region, map, &gsi); |
| gsi_next (&gsi); |
| } |
| } |
| |
| /* Rename all the SSA_NAMEs from block BB according to the MAP. */ |
| |
| static void |
| rename_variables (basic_block bb, htab_t map) |
| { |
| gimple_stmt_iterator gsi; |
| gimple_stmt_iterator insert_gsi = gsi_start_bb (bb); |
| |
| for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
| rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi); |
| } |
| |
| /* Remove condition from BB. */ |
| |
| static void |
| remove_condition (basic_block bb) |
| { |
| gimple last = last_stmt (bb); |
| |
| if (last && gimple_code (last) == GIMPLE_COND) |
| { |
| gimple_stmt_iterator gsi = gsi_last_bb (bb); |
| gsi_remove (&gsi, true); |
| } |
| } |
| |
| /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ |
| |
| edge |
| get_true_edge_from_guard_bb (basic_block bb) |
| { |
| edge e; |
| edge_iterator ei; |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| if (e->flags & EDGE_TRUE_VALUE) |
| return e; |
| |
| gcc_unreachable (); |
| return NULL; |
| } |
| |
| /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ |
| |
| edge |
| get_false_edge_from_guard_bb (basic_block bb) |
| { |
| edge e; |
| edge_iterator ei; |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| if (!(e->flags & EDGE_TRUE_VALUE)) |
| return e; |
| |
| gcc_unreachable (); |
| return NULL; |
| } |
| |
| /* Returns true when NAME is defined in LOOP. */ |
| |
| static bool |
| name_defined_in_loop_p (tree name, loop_p loop) |
| { |
| return !SSA_NAME_IS_DEFAULT_DEF (name) |
| && gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father == loop; |
| } |
| |
| /* Returns true when EXPR contains SSA_NAMEs defined in LOOP. */ |
| |
| static bool |
| expr_defined_in_loop_p (tree expr, loop_p loop) |
| { |
| switch (TREE_CODE_LENGTH (TREE_CODE (expr))) |
| { |
| case 3: |
| return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop) |
| || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop) |
| || expr_defined_in_loop_p (TREE_OPERAND (expr, 2), loop); |
| |
| case 2: |
| return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop) |
| || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop); |
| |
| case 1: |
| return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop); |
| |
| case 0: |
| return TREE_CODE (expr) == SSA_NAME |
| && name_defined_in_loop_p (expr, loop); |
| |
| default: |
| return false; |
| } |
| } |
| |
| /* Returns the gimple statement that uses NAME outside the loop it is |
| defined in, returns NULL if there is no such loop close phi node. |
| An invariant of the loop closed SSA form is that the only use of a |
| variable, outside the loop it is defined in, is in the loop close |
| phi node that just follows the loop. */ |
| |
| static gimple |
| alive_after_loop (tree name) |
| { |
| use_operand_p use_p; |
| imm_use_iterator imm_iter; |
| loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father; |
| |
| FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name) |
| { |
| gimple stmt = USE_STMT (use_p); |
| |
| if (gimple_code (stmt) == GIMPLE_PHI |
| && gimple_bb (stmt)->loop_father != loop) |
| return stmt; |
| } |
| |
| return NULL; |
| } |
| |
| /* Return true if a close phi has not yet been inserted for the use of |
| variable NAME on the single exit of LOOP. */ |
| |
| static bool |
| close_phi_not_yet_inserted_p (loop_p loop, tree name) |
| { |
| gimple_stmt_iterator psi; |
| basic_block bb = single_exit (loop)->dest; |
| |
| for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) |
| if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name) |
| return false; |
| |
| return true; |
| } |
| |
| /* A structure for passing parameters to add_loop_exit_phis. */ |
| |
| typedef struct alep { |
| loop_p loop; |
| VEC (rename_map_elt, heap) *new_renames; |
| } *alep_p; |
| |
| /* Helper function for htab_traverse in insert_loop_close_phis. */ |
| |
| static int |
| add_loop_exit_phis (void **slot, void *data) |
| { |
| struct rename_map_elt_s *entry; |
| alep_p a; |
| loop_p loop; |
| tree expr, new_name, old_name; |
| bool def_in_loop_p, used_outside_p, need_close_phi_p; |
| gimple old_close_phi; |
| |
| if (!slot || !*slot || !data) |
| return 1; |
| |
| entry = (struct rename_map_elt_s *) *slot; |
| a = (alep_p) data; |
| loop = a->loop; |
| new_name = expr = entry->expr; |
| old_name = entry->old_name; |
| |
| def_in_loop_p = expr_defined_in_loop_p (expr, loop); |
| if (!def_in_loop_p) |
| return 1; |
| |
| /* Remove the old rename from the map when the expression is defined |
| in the loop that we're closing. */ |
| free (*slot); |
| *slot = NULL; |
| |
| if (TREE_CODE (expr) != SSA_NAME) |
| return 1; |
| |
| old_close_phi = alive_after_loop (old_name); |
| used_outside_p = (old_close_phi != NULL); |
| need_close_phi_p = (used_outside_p |
| && close_phi_not_yet_inserted_p (loop, new_name)); |
| |
| /* Insert a loop close phi node. */ |
| if (need_close_phi_p) |
| { |
| basic_block bb = single_exit (loop)->dest; |
| gimple phi = create_phi_node (new_name, bb); |
| tree new_res = create_new_def_for (gimple_phi_result (phi), phi, |
| gimple_phi_result_ptr (phi)); |
| |
| add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION); |
| VEC_safe_push (rename_map_elt, heap, a->new_renames, |
| new_rename_map_elt (gimple_phi_result (old_close_phi), |
| new_res)); |
| } |
| |
| return 1; |
| } |
| |
| /* Traverses MAP and removes from it all the tuples (OLD, NEW) where |
| NEW is defined in LOOP. Inserts on the exit of LOOP the close phi |
| node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in |
| the original code. Inserts in MAP the tuple (OLD_RES, RES). */ |
| |
| void |
| insert_loop_close_phis (htab_t map, loop_p loop) |
| { |
| int i; |
| struct alep a; |
| rename_map_elt elt; |
| |
| a.loop = loop; |
| a.new_renames = VEC_alloc (rename_map_elt, heap, 3); |
| update_ssa (TODO_update_ssa); |
| htab_traverse (map, add_loop_exit_phis, &a); |
| update_ssa (TODO_update_ssa); |
| |
| for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++) |
| { |
| set_rename (map, elt->old_name, elt->expr); |
| free (elt); |
| } |
| |
| VEC_free (rename_map_elt, heap, a.new_renames); |
| } |
| |
| /* Helper structure for htab_traverse in insert_guard_phis. */ |
| |
| struct igp { |
| basic_block bb; |
| edge true_edge, false_edge; |
| htab_t before_guard; |
| }; |
| |
| /* Return the default name that is before the guard. */ |
| |
| static tree |
| default_before_guard (htab_t before_guard, tree old_name) |
| { |
| tree res = get_rename (before_guard, old_name); |
| |
| if (res == old_name) |
| { |
| if (is_gimple_reg (res)) |
| return fold_convert (TREE_TYPE (res), integer_zero_node); |
| return gimple_default_def (cfun, SSA_NAME_VAR (res)); |
| } |
| |
| return res; |
| } |
| |
| /* Prepares EXPR to be a good phi argument when the phi result is |
| RES. Insert needed statements on edge E. */ |
| |
| static tree |
| convert_for_phi_arg (tree expr, tree res, edge e) |
| { |
| tree type = TREE_TYPE (res); |
| |
| if (TREE_TYPE (expr) != type) |
| expr = fold_convert (type, expr); |
| |
| if (TREE_CODE (expr) != SSA_NAME |
| && !is_gimple_min_invariant (expr)) |
| { |
| tree var = create_tmp_var (type, "var"); |
| gimple_seq stmts; |
| |
| expr = build2 (MODIFY_EXPR, type, var, expr); |
| expr = force_gimple_operand (expr, &stmts, true, NULL); |
| gsi_insert_seq_on_edge_immediate (e, stmts); |
| } |
| |
| return expr; |
| } |
| |
| /* Helper function for htab_traverse in insert_guard_phis. */ |
| |
| static int |
| add_guard_exit_phis (void **slot, void *s) |
| { |
| struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; |
| struct igp *i = (struct igp *) s; |
| basic_block bb = i->bb; |
| edge true_edge = i->true_edge; |
| edge false_edge = i->false_edge; |
| tree res = entry->old_name; |
| tree name1 = entry->expr; |
| tree name2 = default_before_guard (i->before_guard, res); |
| gimple phi; |
| |
| /* Nothing to be merged if the name before the guard is the same as |
| the one after. */ |
| if (name1 == name2) |
| return 1; |
| |
| name1 = convert_for_phi_arg (name1, res, true_edge); |
| name2 = convert_for_phi_arg (name2, res, false_edge); |
| |
| phi = create_phi_node (res, bb); |
| res = create_new_def_for (gimple_phi_result (phi), phi, |
| gimple_phi_result_ptr (phi)); |
| |
| add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION); |
| add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION); |
| |
| entry->expr = res; |
| *slot = entry; |
| return 1; |
| } |
| |
| /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1). |
| If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD, |
| with NAME1 different than NAME2, then insert in BB the phi node: |
| |
| | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))" |
| |
| if there is no tuple for OLD in BEFORE_GUARD, insert |
| |
| | RES = phi (NAME1 (on TRUE_EDGE), |
| | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))". |
| |
| Finally register in RENAME_MAP the tuple (OLD, RES). */ |
| |
| void |
| insert_guard_phis (basic_block bb, edge true_edge, edge false_edge, |
| htab_t before_guard, htab_t rename_map) |
| { |
| struct igp i; |
| i.bb = bb; |
| i.true_edge = true_edge; |
| i.false_edge = false_edge; |
| i.before_guard = before_guard; |
| |
| update_ssa (TODO_update_ssa); |
| htab_traverse (rename_map, add_guard_exit_phis, &i); |
| update_ssa (TODO_update_ssa); |
| } |
| |
| /* Create a duplicate of the basic block BB. NOTE: This does not |
| preserve SSA form. */ |
| |
| static void |
| graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) |
| { |
| gimple_stmt_iterator gsi, gsi_tgt; |
| |
| gsi_tgt = gsi_start_bb (new_bb); |
| for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| def_operand_p def_p; |
| ssa_op_iter op_iter; |
| gimple stmt = gsi_stmt (gsi); |
| gimple copy; |
| |
| if (gimple_code (stmt) == GIMPLE_LABEL) |
| continue; |
| |
| /* Create a new copy of STMT and duplicate STMT's virtual |
| operands. */ |
| copy = gimple_copy (stmt); |
| gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); |
| mark_sym_for_renaming (gimple_vop (cfun)); |
| |
| maybe_duplicate_eh_stmt (copy, stmt); |
| gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); |
| |
| /* Create new names for all the definitions created by COPY and |
| add replacement mappings for each new name. */ |
| FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) |
| { |
| tree old_name = DEF_FROM_PTR (def_p); |
| tree new_name = create_new_def_for (old_name, copy, def_p); |
| set_rename (map, old_name, new_name); |
| } |
| } |
| } |
| |
| /* Copies BB and includes in the copied BB all the statements that can |
| be reached following the use-def chains from the memory accesses, |
| and returns the next edge following this new block. */ |
| |
| edge |
| copy_bb_and_scalar_dependences (basic_block bb, sese region, |
| edge next_e, htab_t map) |
| { |
| basic_block new_bb = split_edge (next_e); |
| |
| next_e = single_succ_edge (new_bb); |
| graphite_copy_stmts_from_block (bb, new_bb, map); |
| remove_condition (new_bb); |
| remove_phi_nodes (new_bb); |
| expand_scalar_variables (new_bb, region, map); |
| rename_variables (new_bb, map); |
| |
| return next_e; |
| } |
| |
| /* Returns the outermost loop in SCOP that contains BB. */ |
| |
| struct loop * |
| outermost_loop_in_sese (sese region, basic_block bb) |
| { |
| struct loop *nest; |
| |
| nest = bb->loop_father; |
| while (loop_outer (nest) |
| && loop_in_sese_p (loop_outer (nest), region)) |
| nest = loop_outer (nest); |
| |
| return nest; |
| } |
| |
| /* Sets the false region of an IF_REGION to REGION. */ |
| |
| void |
| if_region_set_false_region (ifsese if_region, sese region) |
| { |
| basic_block condition = if_region_get_condition_block (if_region); |
| edge false_edge = get_false_edge_from_guard_bb (condition); |
| basic_block dummy = false_edge->dest; |
| edge entry_region = SESE_ENTRY (region); |
| edge exit_region = SESE_EXIT (region); |
| basic_block before_region = entry_region->src; |
| basic_block last_in_region = exit_region->src; |
| void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region, |
| htab_hash_pointer (exit_region), |
| NO_INSERT); |
| |
| entry_region->flags = false_edge->flags; |
| false_edge->flags = exit_region->flags; |
| |
| redirect_edge_pred (entry_region, condition); |
| redirect_edge_pred (exit_region, before_region); |
| redirect_edge_pred (false_edge, last_in_region); |
| redirect_edge_succ (false_edge, single_succ (dummy)); |
| delete_basic_block (dummy); |
| |
| exit_region->flags = EDGE_FALLTHRU; |
| recompute_all_dominators (); |
| |
| SESE_EXIT (region) = false_edge; |
| |
| if (if_region->false_region) |
| free (if_region->false_region); |
| if_region->false_region = region; |
| |
| if (slot) |
| { |
| struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit); |
| |
| memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit)); |
| htab_clear_slot (current_loops->exits, slot); |
| |
| slot = htab_find_slot_with_hash (current_loops->exits, false_edge, |
| htab_hash_pointer (false_edge), |
| INSERT); |
| loop_exit->e = false_edge; |
| *slot = loop_exit; |
| false_edge->src->loop_father->exits->next = loop_exit; |
| } |
| } |
| |
| /* Creates an IFSESE with CONDITION on edge ENTRY. */ |
| |
| ifsese |
| create_if_region_on_edge (edge entry, tree condition) |
| { |
| edge e; |
| edge_iterator ei; |
| sese sese_region = XNEW (struct sese_s); |
| sese true_region = XNEW (struct sese_s); |
| sese false_region = XNEW (struct sese_s); |
| ifsese if_region = XNEW (struct ifsese_s); |
| edge exit = create_empty_if_region_on_edge (entry, condition); |
| |
| if_region->region = sese_region; |
| if_region->region->entry = entry; |
| if_region->region->exit = exit; |
| |
| FOR_EACH_EDGE (e, ei, entry->dest->succs) |
| { |
| if (e->flags & EDGE_TRUE_VALUE) |
| { |
| true_region->entry = e; |
| true_region->exit = single_succ_edge (e->dest); |
| if_region->true_region = true_region; |
| } |
| else if (e->flags & EDGE_FALSE_VALUE) |
| { |
| false_region->entry = e; |
| false_region->exit = single_succ_edge (e->dest); |
| if_region->false_region = false_region; |
| } |
| } |
| |
| return if_region; |
| } |
| |
| /* Moves REGION in a condition expression: |
| | if (1) |
| | ; |
| | else |
| | REGION; |
| */ |
| |
| ifsese |
| move_sese_in_condition (sese region) |
| { |
| basic_block pred_block = split_edge (SESE_ENTRY (region)); |
| ifsese if_region; |
| |
| SESE_ENTRY (region) = single_succ_edge (pred_block); |
| if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node); |
| if_region_set_false_region (if_region, region); |
| |
| return if_region; |
| } |
| |
| /* Replaces the condition of the IF_REGION with CONDITION: |
| | if (CONDITION) |
| | true_region; |
| | else |
| | false_region; |
| */ |
| |
| void |
| set_ifsese_condition (ifsese if_region, tree condition) |
| { |
| sese region = if_region->region; |
| edge entry = region->entry; |
| basic_block bb = entry->dest; |
| gimple last = last_stmt (bb); |
| gimple_stmt_iterator gsi = gsi_last_bb (bb); |
| gimple cond_stmt; |
| |
| gcc_assert (gimple_code (last) == GIMPLE_COND); |
| |
| gsi_remove (&gsi, true); |
| gsi = gsi_last_bb (bb); |
| condition = force_gimple_operand_gsi (&gsi, condition, true, NULL, |
| false, GSI_NEW_STMT); |
| cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); |
| gsi = gsi_last_bb (bb); |
| gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); |
| } |
| |
| /* Returns the scalar evolution of T in REGION. Every variable that |
| is not defined in the REGION is considered a parameter. */ |
| |
| tree |
| scalar_evolution_in_region (sese region, loop_p loop, tree t) |
| { |
| gimple def; |
| struct loop *def_loop; |
| basic_block before = block_before_sese (region); |
| |
| if (TREE_CODE (t) != SSA_NAME |
| || loop_in_sese_p (loop, region)) |
| return instantiate_scev (before, loop, |
| analyze_scalar_evolution (loop, t)); |
| |
| if (!defined_in_sese_p (t, region)) |
| return t; |
| |
| def = SSA_NAME_DEF_STMT (t); |
| def_loop = loop_containing_stmt (def); |
| |
| if (loop_in_sese_p (def_loop, region)) |
| { |
| t = analyze_scalar_evolution (def_loop, t); |
| def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1); |
| t = compute_overall_effect_of_inner_loop (def_loop, t); |
| return t; |
| } |
| else |
| return instantiate_scev (before, loop, t); |
| } |