diff options
author | Sebastian Pop <spop@gcc.gnu.org> | 2009-07-31 02:43:11 +0000 |
---|---|---|
committer | Sebastian Pop <spop@gcc.gnu.org> | 2009-07-31 02:43:11 +0000 |
commit | 2abae5f13adafd84ac3f4e2da2890da4515fd1fe (patch) | |
tree | 624d5145af586181a9560d3ebefda21001a91b62 /gcc/sese.c | |
parent | e7c705bbbdc98ccb45cb953582f8964cfa3de61e (diff) | |
download | gcc-2abae5f13adafd84ac3f4e2da2890da4515fd1fe.zip gcc-2abae5f13adafd84ac3f4e2da2890da4515fd1fe.tar.gz gcc-2abae5f13adafd84ac3f4e2da2890da4515fd1fe.tar.bz2 |
New Graphite files.
2009-07-30 Sebastian Pop <sebastian.pop@amd.com>
* ChangeLog.graphite: New.
* graphite-blocking.c: New.
* graphite-clast-to-gimple.c: New.
* graphite-clast-to-gimple.h: New.
* graphite-dependences.c: New.
* graphite-dependences.h: New.
* graphite-interchange.c: New.
* graphite-poly.c: New.
* graphite-poly.h: New.
* graphite-ppl.c: New.
* graphite-ppl.h: New.
* graphite-scop-detection.c: New.
* graphite-scop-detection.h: New.
* graphite-sese-to-poly.c: New.
* graphite-sese-to-poly.h: New.
* sese.c: New.
* sese.h: New.
From-SVN: r150300
Diffstat (limited to 'gcc/sese.c')
-rw-r--r-- | gcc/sese.c | 1386 |
1 files changed, 1386 insertions, 0 deletions
diff --git a/gcc/sese.c b/gcc/sese.c new file mode 100644 index 0000000..25c5703 --- /dev/null +++ b/gcc/sese.c @@ -0,0 +1,1386 @@ +/* Single entry single exit control flow regions. + Copyright (C) 2008, 2009 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 htab_hash_pointer (((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)) + FOR_EACH_SSA_USE_OPERAND (use_p, gsi_stmt (bsi), iter, SSA_OP_ALL_USES) + sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); +} + +/* 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); +} + +/* 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); + SESE_PARAMS_INDEX (region) = htab_create (10, clast_name_index_elt_info, + eq_clast_name_indexes, free); + SESE_PARAMS_NAMES (region) = XNEWVEC (char *, num_ssa_names); + + 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)); + + if (SESE_PARAMS_INDEX (region)) + htab_delete (SESE_PARAMS_INDEX (region)); + + /* Do not free SESE_PARAMS_NAMES: CLooG does that. */ + + 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 def_stmt = SSA_NAME_DEF_STMT (name); + basic_block def_bb = gimple_bb (def_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 (def_stmt)) + { + case GIMPLE_PHI: + for (i = 0; i < gimple_phi_num_args (def_stmt); i++) + { + tree arg = gimple_phi_arg_def (def_stmt, i); + tree res = get_vdef_before_sese (region, arg, visited); + if (res) + return res; + } + return NULL_TREE; + + 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 name associated to OLD_NAME in MAP. */ + +static tree +get_rename (htab_t map, tree old_name) +{ + struct rename_map_elt_s tmp; + PTR *slot; + + 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); +} + +/* 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); + + if (!is_gimple_reg (PHI_RESULT (phi))) + { + 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); + } + } +} + +/* 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 = get_rename (map, use); + tree type_use = TREE_TYPE (use); + tree type_expr = TREE_TYPE (expr); + gimple_seq stmts; + + if (use == expr) + continue; + + if (type_use != type_expr + || (TREE_CODE (expr) != SSA_NAME + && is_gimple_reg (use))) + { + tree 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 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 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 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 new_op; + } + else + { + if (!gimple_bb (def_stmt) + || !bb_in_sese_p (gimple_bb (def_stmt), region)) + return 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 + (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); + } + + 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 (op0, bb, region, map, gsi); + + if (code == ADDR_EXPR) + 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 (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 +defined_in_loop_p (tree name, loop_p loop) +{ + gimple stmt = SSA_NAME_DEF_STMT (name); + + return (gimple_bb (stmt)->loop_father == loop); +} + +/* 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; + bool def_in_loop_p, used_outside_p, need_close_phi_p; + gimple old_close_phi; + + if (!slot || !data) + return 1; + + entry = (struct rename_map_elt_s *) *slot; + a = (alep_p) data; + loop = a->loop; + expr = entry->expr; + + if (TREE_CODE (expr) != SSA_NAME) + return 1; + + new_name = expr; + def_in_loop_p = defined_in_loop_p (new_name, loop); + old_close_phi = alive_after_loop (entry->old_name); + used_outside_p = (old_close_phi != NULL); + need_close_phi_p = (def_in_loop_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)); + } + + /* Remove the old rename from the map. */ + if (def_in_loop_p && *slot) + { + free (*slot); + *slot = NULL; + } + + 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; +} + +/* 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 name1 = entry->expr; + tree name2 = default_before_guard (i->before_guard, entry->old_name); + gimple phi; + tree res; + gimple_seq stmts; + + /* Nothing to be merged if the name before the guard is the same as + the one after. */ + if (name1 == name2) + return 1; + + if (TREE_TYPE (name1) != TREE_TYPE (name2)) + name1 = fold_convert (TREE_TYPE (name2), name1); + + if (TREE_CODE (name1) != SSA_NAME + && (TREE_CODE (name2) != SSA_NAME + || is_gimple_reg (name2))) + { + tree type = TREE_TYPE (name2); + tree var = create_tmp_var (type, "var"); + + name1 = build2 (MODIFY_EXPR, type, var, name1); + name1 = force_gimple_operand (name1, &stmts, true, NULL); + gsi_insert_seq_on_edge_immediate (true_edge, stmts); + } + + phi = create_phi_node (entry->old_name, 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; + int region; + 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)); + + region = lookup_stmt_eh_region (stmt); + if (region >= 0) + add_stmt_to_eh_region (copy, region); + 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_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 = GGC_NEW (struct sese_s); + sese true_region = GGC_NEW (struct sese_s); + sese false_region = GGC_NEW (struct sese_s); + ifsese if_region = GGC_NEW (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 = NULL; + + 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; +} + +/* Reset the loop->aux pointer for all loops in REGION. */ + +void +sese_reset_aux_in_loops (sese region) +{ + int i; + loop_p loop; + + for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) + loop->aux = NULL; +} + +/* 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); +} |