/* Single entry single exit control flow regions.
- Copyright (C) 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Jan Sjodin <jan.sjodin@amd.com> and
Sebastian Pop <sebastian.pop@amd.com>.
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
#include "tree-flow.h"
#include "toplev.h"
#include "tree-dump.h"
hashval_t
rename_map_elt_info (const void *elt)
{
- return htab_hash_pointer (((const struct rename_map_elt_s *) elt)->old_name);
+ return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
}
/* Compares database elements E1 and E2. */
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;
}
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. */
+ VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
XDELETE (region);
}
}
}
-/* Returns the name associated to OLD_NAME in MAP. */
+/* 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);
return old_name;
}
-/* Register in MAP the rename tuple (old_name, expr). */
+/* Register in MAP the rename tuple (OLD_NAME, EXPR). */
void
set_rename (htab_t map, tree old_name, tree expr)
*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
unsigned i;
unsigned false_i = 0;
gimple phi = gsi_stmt (si);
+ tree res = gimple_phi_result (phi);
- if (!is_gimple_reg (PHI_RESULT (phi)))
+ if (!is_gimple_reg (res))
{
sese_adjust_vphi (region, phi, true_e);
continue;
}
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
+static void
rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
{
ssa_op_iter iter;
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);
+ 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)))
to translate the names of induction variables. */
static tree
-expand_scalar_variables_ssa_name (tree op0, basic_block bb,
- sese region, htab_t map,
+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 get_rename (map, 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. */
if (new_op != op0
&& gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
- return new_op;
-
+ 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 new_op;
+ return fold_convert (type, new_op);
}
else
{
if (!gimple_bb (def_stmt)
|| !bb_in_sese_p (gimple_bb (def_stmt), region))
- return new_op;
+ return fold_convert (type, new_op);
switch (gimple_code (def_stmt))
{
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,
+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 old_name = TREE_OPERAND (op0, 0);
tree expr = expand_scalar_variables_ssa_name
- (old_name, bb, region, map, gsi);
+ (type, old_name, bb, region, map, gsi);
if (TREE_CODE (expr) != SSA_NAME
&& is_gimple_reg (old_name))
return build4 (ARRAY_REF, type, base, subscript, op02, op03);
}
+ case COMPONENT_REF:
+ return op0;
+
default:
/* The above cases should catch everything. */
gcc_unreachable ();
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 (code == SSA_NAME)
- return expand_scalar_variables_ssa_name (op0, bb, region, map, gsi);
+ return expand_scalar_variables_ssa_name (type, op0, bb, region, map, gsi);
if (code == ADDR_EXPR)
- return op0;
+ {
+ 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;
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)
induction variables renaming mapping, and is used to translate the
names of induction variables. */
-static void
+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);
/* Rename all the SSA_NAMEs from block BB according to the MAP. */
-static void
+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);
}
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->flags & EDGE_TRUE_VALUE)
+ if (e->flags & EDGE_TRUE_VALUE)
return e;
gcc_unreachable ();
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->flags & EDGE_TRUE_VALUE))
+ if (!(e->flags & EDGE_TRUE_VALUE))
return e;
gcc_unreachable ();
/* Returns true when NAME is defined in LOOP. */
static bool
-defined_in_loop_p (tree name, loop_p loop)
+name_defined_in_loop_p (tree name, loop_p loop)
{
- gimple stmt = SSA_NAME_DEF_STMT (name);
+ 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);
- return (gimple_bb (stmt)->loop_father == loop);
+ default:
+ return false;
+ }
}
/* Returns the gimple statement that uses NAME outside the loop it is
struct rename_map_elt_s *entry;
alep_p a;
loop_p loop;
- tree expr, new_name;
+ tree expr, new_name, old_name;
bool def_in_loop_p, used_outside_p, need_close_phi_p;
gimple old_close_phi;
- if (!slot || !data)
+ if (!slot || !*slot || !data)
return 1;
entry = (struct rename_map_elt_s *) *slot;
a = (alep_p) data;
loop = a->loop;
- expr = entry->expr;
+ 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;
- new_name = expr;
- def_in_loop_p = defined_in_loop_p (new_name, loop);
- old_close_phi = alive_after_loop (entry->old_name);
+ old_close_phi = alive_after_loop (old_name);
used_outside_p = (old_close_phi != NULL);
- need_close_phi_p = (def_in_loop_p && used_outside_p
+ need_close_phi_p = (used_outside_p
&& close_phi_not_yet_inserted_p (loop, new_name));
/* Insert a loop close phi node. */
new_res));
}
- /* Remove the old rename from the map. */
- if (def_in_loop_p && *slot)
- {
- free (*slot);
- *slot = NULL;
- }
-
return 1;
}
/* 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)
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)
/* Creates an IFSESE with CONDITION on edge ENTRY. */
-ifsese
+static 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);
+ 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;
move_sese_in_condition (sese region)
{
basic_block pred_block = split_edge (SESE_ENTRY (region));
- ifsese if_region = NULL;
+ 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);
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. */
OSDN Git Service
