/* Loop invariant motion.
- Copyright (C) 2003 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
#include "params.h"
#include "tree-pass.h"
#include "flags.h"
+#include "real.h"
+
+/* TODO: Support for predicated code motion. I.e.
+
+ while (1)
+ {
+ if (cond)
+ {
+ a = inv;
+ something;
+ }
+ }
+
+ Where COND and INV are is invariants, but evaluating INV may trap or be
+ invalid from some other reason if !COND. This may be transformed to
+
+ if (cond)
+ a = inv;
+ while (1)
+ {
+ if (cond)
+ something;
+ } */
/* A type for the list of statements that have to be moved in order to be able
to hoist an invariant computation. */
MAX_LOOP loop. */
};
-#define LIM_DATA(STMT) ((struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
+#define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
+ ? NULL \
+ : (struct lim_aux_data *) (stmt_ann (STMT)->aux))
/* Description of a memory reference for store motion. */
block will be executed. */
#define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
-/* Maximum uid in the statement in the function. */
+static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
+ nodes are assigned using the versions of
+ ssa names they define. */
-static unsigned max_uid;
+/* Returns uid of statement STMT. */
+
+static unsigned
+get_stmt_uid (tree stmt)
+{
+ if (TREE_CODE (stmt) == PHI_NODE)
+ return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
+
+ return stmt_ann (stmt)->uid;
+}
/* Calls CBCK for each index in memory reference ADDR_P. There are two
kinds situations handled; in each of these cases, the memory reference
bool
for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
{
- tree *nxt;
+ tree *nxt, *idx;
for (; ; addr_p = nxt)
{
case SSA_NAME:
return cbck (*addr_p, addr_p, data);
+ case MISALIGNED_INDIRECT_REF:
+ case ALIGN_INDIRECT_REF:
case INDIRECT_REF:
nxt = &TREE_OPERAND (*addr_p, 0);
return cbck (*addr_p, nxt, data);
case BIT_FIELD_REF:
- case COMPONENT_REF:
case VIEW_CONVERT_EXPR:
case ARRAY_RANGE_REF:
case REALPART_EXPR:
nxt = &TREE_OPERAND (*addr_p, 0);
break;
+ case COMPONENT_REF:
+ /* If the component has varying offset, it behaves like index
+ as well. */
+ idx = &TREE_OPERAND (*addr_p, 2);
+ if (*idx
+ && !cbck (*addr_p, idx, data))
+ return false;
+
+ nxt = &TREE_OPERAND (*addr_p, 0);
+ break;
+
case ARRAY_REF:
nxt = &TREE_OPERAND (*addr_p, 0);
if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
return true;
default:
- abort ();
+ gcc_unreachable ();
}
}
}
{
/* If we perform unswitching, force the operands of the invariant
condition to be moved out of the loop. */
- get_stmt_operands (stmt);
-
return MOVE_POSSIBLE;
}
if (stmt_ends_bb_p (stmt))
return MOVE_IMPOSSIBLE;
- get_stmt_operands (stmt);
-
if (stmt_ann (stmt)->has_volatile_ops)
return MOVE_IMPOSSIBLE;
|| tree_could_trap_p (rhs))
return MOVE_PRESERVE_EXECUTION;
+ if (get_call_expr_in (stmt))
+ {
+ /* While pure or const call is guaranteed to have no side effects, we
+ cannot move it arbitrarily. Consider code like
+
+ char *s = something ();
+
+ while (1)
+ {
+ if (s)
+ t = strlen (s);
+ else
+ t = 0;
+ }
+
+ Here the strlen call cannot be moved out of the loop, even though
+ s is invariant. In addition to possibly creating a call with
+ invalid arguments, moving out a function call that is not executed
+ may cause performance regressions in case the call is costly and
+ not executed at all. */
+ return MOVE_PRESERVE_EXECUTION;
+ }
return MOVE_POSSIBLE;
}
static struct loop *
outermost_invariant_loop_expr (tree expr, struct loop *loop)
{
- char class = TREE_CODE_CLASS (TREE_CODE (expr));
+ enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
unsigned i, nops;
struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
|| is_gimple_min_invariant (expr))
return outermost_invariant_loop (expr, loop);
- if (class != '1'
- && class != '2'
- && class != 'e'
- && class != '<')
+ if (class != tcc_unary
+ && class != tcc_binary
+ && class != tcc_expression
+ && class != tcc_comparison)
return NULL;
- nops = first_rtl_op (TREE_CODE (expr));
+ nops = TREE_CODE_LENGTH (TREE_CODE (expr));
for (i = 0; i < nops; i++)
{
aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
static unsigned
stmt_cost (tree stmt)
{
- tree lhs, rhs;
+ tree rhs;
unsigned cost = 1;
/* Always try to create possibilities for unswitching. */
if (TREE_CODE (stmt) == COND_EXPR)
return LIM_EXPENSIVE;
- lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
/* Hoisting memory references out should almost surely be a win. */
- if (!is_gimple_variable (lhs))
- cost += 20;
- if (is_gimple_addressable (rhs) && !is_gimple_variable (rhs))
+ if (stmt_references_memory_p (stmt))
cost += 20;
switch (TREE_CODE (rhs))
/* Unless the call is a builtin_constant_p; this always folds to a
constant, so moving it is useless. */
rhs = get_callee_fndecl (rhs);
- if (DECL_BUILT_IN (rhs)
+ if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
&& DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
return 0;
case FLOOR_MOD_EXPR:
case ROUND_MOD_EXPR:
case TRUNC_MOD_EXPR:
+ case RDIV_EXPR:
/* Division and multiplication are usually expensive. */
cost += 20;
break;
if (!add_dependency (val, lim_data, loop, true))
return false;
- FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
+ FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
if (!add_dependency (val, lim_data, loop, false))
return false;
if (flow_loop_nested_p (stmt_loop, level))
return;
- if (!LIM_DATA (stmt))
- abort ();
-
- if (level != LIM_DATA (stmt)->max_loop
- && !flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level))
- abort ();
+ gcc_assert (LIM_DATA (stmt));
+ gcc_assert (level == LIM_DATA (stmt)->max_loop
+ || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
LIM_DATA (stmt)->tgt_loop = level;
for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
{
enum move_pos pos;
block_stmt_iterator bsi;
- tree stmt;
+ tree stmt, rhs;
bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
continue;
}
- stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
+ /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
+ to be hoisted out of loop, saving expensive divide. */
+ if (pos == MOVE_POSSIBLE
+ && (rhs = TREE_OPERAND (stmt, 1)) != NULL
+ && TREE_CODE (rhs) == RDIV_EXPR
+ && flag_unsafe_math_optimizations
+ && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1),
+ loop_containing_stmt (stmt)) != NULL
+ && outermost_invariant_loop_expr (rhs,
+ loop_containing_stmt (stmt)) == NULL)
+ {
+ tree lhs, stmt1, stmt2, var, name;
+
+ lhs = TREE_OPERAND (stmt, 0);
+
+ /* stmt must be MODIFY_EXPR. */
+ var = create_tmp_var (TREE_TYPE (rhs), "reciptmp");
+ add_referenced_tmp_var (var);
+
+ stmt1 = build2 (MODIFY_EXPR, void_type_node, var,
+ build2 (RDIV_EXPR, TREE_TYPE (rhs),
+ build_real (TREE_TYPE (rhs), dconst1),
+ TREE_OPERAND (rhs, 1)));
+ name = make_ssa_name (var, stmt1);
+ TREE_OPERAND (stmt1, 0) = name;
+ stmt2 = build2 (MODIFY_EXPR, void_type_node, lhs,
+ build2 (MULT_EXPR, TREE_TYPE (rhs),
+ name, TREE_OPERAND (rhs, 0)));
+
+ /* Replace division stmt with reciprocal and multiply stmts.
+ The multiply stmt is not invariant, so update iterator
+ and avoid rescanning. */
+ bsi_replace (&bsi, stmt1, true);
+ bsi_insert_after (&bsi, stmt2, BSI_NEW_STMT);
+ SSA_NAME_DEF_STMT (lhs) = stmt2;
+
+ /* Continue processing with invariant reciprocal statment. */
+ stmt = stmt1;
+ }
+
+ stmt_ann (stmt)->aux = xcalloc (1, sizeof (struct lim_aux_data));
LIM_DATA (stmt)->always_executed_in = outermost;
if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
basic_block bb;
old_last_basic_block = last_basic_block;
- bsi_commit_edge_inserts (NULL);
+ bsi_commit_edge_inserts ();
for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
{
bb = BASIC_BLOCK (i);
add_bb_to_loop (bb,
- find_common_loop (bb->succ->dest->loop_father,
- bb->pred->src->loop_father));
+ find_common_loop (single_pred (bb)->loop_father,
+ single_succ (bb)->loop_father));
}
}
cost = LIM_DATA (stmt)->cost;
level = LIM_DATA (stmt)->tgt_loop;
free_lim_aux_data (LIM_DATA (stmt));
- stmt_ann (stmt)->common.aux = NULL;
+ stmt_ann (stmt)->aux = NULL;
if (!level)
{
fini_walk_dominator_tree (&walk_data);
loop_commit_inserts ();
- rewrite_into_ssa (false);
- if (bitmap_first_set_bit (vars_to_rename) >= 0)
- {
- /* The rewrite of ssa names may cause violation of loop closed ssa
- form invariants. TODO -- avoid these rewrites completely.
- Information in virtual phi nodes is sufficient for it. */
- rewrite_into_loop_closed_ssa ();
- }
- bitmap_clear (vars_to_rename);
+ if (need_ssa_update_p ())
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
}
/* Checks whether the statement defining variable *INDEX can be hoisted
static void
force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
{
- char class = TREE_CODE_CLASS (TREE_CODE (expr));
+ enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
unsigned i, nops;
if (TREE_CODE (expr) == SSA_NAME)
return;
}
- if (class != '1'
- && class != '2'
- && class != 'e'
- && class != '<')
+ if (class != tcc_unary
+ && class != tcc_binary
+ && class != tcc_expression
+ && class != tcc_comparison)
return;
- nops = first_rtl_op (TREE_CODE (expr));
+ nops = TREE_CODE_LENGTH (TREE_CODE (expr));
for (i = 0; i < nops; i++)
force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
}
if (!def_bb
|| !flow_bb_inside_loop_p (loop, def_bb)
- || TEST_BIT (seen, stmt_ann (stmt)->uid))
+ || TEST_BIT (seen, get_stmt_uid (stmt)))
return;
- SET_BIT (seen, stmt_ann (stmt)->uid);
+ SET_BIT (seen, get_stmt_uid (stmt));
queue[(*in_queue)++] = stmt;
}
struct mem_ref **mem_refs,
bool *seen_call_stmt)
{
+ unsigned max_uid = max_stmt_uid + num_ssa_names;
tree *queue = xmalloc (sizeof (tree) * max_uid);
sbitmap seen = sbitmap_alloc (max_uid);
unsigned in_queue = 1;
- dataflow_t df;
- unsigned i, n;
+ unsigned i;
struct sra_data sra_data;
tree call;
tree val;
ssa_op_iter iter;
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
sbitmap_zero (seen);
sra_data.common_ref = NULL_TREE;
queue[0] = stmt;
- SET_BIT (seen, stmt_ann (stmt)->uid);
+ SET_BIT (seen, get_stmt_uid (stmt));
*seen_call_stmt = false;
while (in_queue)
case PHI_NODE:
for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
- maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
- seen, queue, &in_queue);
+ if (TREE_CODE (PHI_ARG_DEF (stmt, i)) == SSA_NAME)
+ maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
+ seen, queue, &in_queue);
break;
default:
}
/* Find uses of virtual names. */
- df = get_immediate_uses (stmt);
- n = num_immediate_uses (df);
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (stmt))))
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (stmt))
+ {
+ tree imm_stmt = USE_STMT (use_p);
- for (i = 0; i < n; i++)
- {
- stmt = immediate_use (df, i);
+ if (TEST_BIT (seen, get_stmt_uid (imm_stmt)))
+ continue;
- if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
- continue;
+ if (!flow_bb_inside_loop_p (loop, bb_for_stmt (imm_stmt)))
+ continue;
- if (TEST_BIT (seen, stmt_ann (stmt)->uid))
- continue;
- SET_BIT (seen, stmt_ann (stmt)->uid);
+ SET_BIT (seen, get_stmt_uid (imm_stmt));
- queue[in_queue++] = stmt;
+ queue[in_queue++] = imm_stmt;
+ }
}
+ else
+ FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
+ {
+ tree imm_stmt = USE_STMT (use_p);
+
+ if (TEST_BIT (seen, get_stmt_uid (imm_stmt)))
+ continue;
+
+ if (!flow_bb_inside_loop_p (loop, bb_for_stmt (imm_stmt)))
+ continue;
+
+ SET_BIT (seen, get_stmt_uid (imm_stmt));
+
+ queue[in_queue++] = imm_stmt;
+ }
}
free (queue);
for (; mem_refs; mem_refs = mem_refs->next)
{
- FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter,
- (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE))
- {
- var = SSA_NAME_VAR (var);
- bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
- }
+ FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
+ mark_sym_for_renaming (SSA_NAME_VAR (var));
*mem_refs->ref = tmp_var;
- modify_stmt (mem_refs->stmt);
+ update_stmt (mem_refs->stmt);
}
}
/* Emit the load & stores. */
load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
- get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
+ get_stmt_ann (load)->aux = xcalloc (1, sizeof (struct lim_aux_data));
LIM_DATA (load)->max_loop = loop;
LIM_DATA (load)->tgt_loop = loop;
is_call_clobbered_ref (tree ref)
{
tree base;
+ HOST_WIDE_INT offset, size;
+ subvar_t sv;
+ subvar_t svars;
+ tree sref = ref;
+ if (TREE_CODE (sref) == COMPONENT_REF
+ && (sref = okay_component_ref_for_subvars (sref, &offset, &size)))
+ {
+ svars = get_subvars_for_var (sref);
+ for (sv = svars; sv; sv = sv->next)
+ {
+ if (overlap_subvar (offset, size, sv, NULL)
+ && is_call_clobbered (sv->var))
+ return true;
+ }
+ }
+
base = get_base_address (ref);
if (!base)
return true;
if (DECL_P (base))
- return is_call_clobbered (base);
+ {
+ if (var_can_have_subvars (base)
+ && (svars = get_subvars_for_var (base)))
+ {
+ for (sv = svars; sv; sv = sv->next)
+ if (is_call_clobbered (sv->var))
+ return true;
+ return false;
+ }
+ else
+ return is_call_clobbered (base);
+ }
- if (TREE_CODE (base) == INDIRECT_REF)
+ if (INDIRECT_REF_P (base))
{
/* Check whether the alias tags associated with the pointer
are call clobbered. */
return false;
}
- abort ();
+ gcc_unreachable ();
}
/* Determine whether all memory references inside LOOP corresponding to the
return;
}
- for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
free (exits);
struct loop *loop;
basic_block bb;
+ if (!loops->tree_root->inner)
+ return;
+
/* Create a UID for each statement in the function. Ordering of the
UIDs is not important for this pass. */
- max_uid = 0;
+ max_stmt_uid = 0;
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
- tree phi;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- stmt_ann (bsi_stmt (bsi))->uid = max_uid++;
-
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
- stmt_ann (phi)->uid = max_uid++;
+ stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
}
- compute_immediate_uses (TDFA_USE_VOPS, NULL);
-
/* Pass the loops from the outermost. For each virtual operand loop phi node
check whether all the references inside the loop correspond to a single
address, and if so, move them. */
loop = loop->outer;
if (loop == loops->tree_root)
{
- free_df ();
loop_commit_inserts ();
return;
}
for (i = 0; i < loop->num_nodes; i++)
{
+ edge_iterator ei;
bb = bbs[i];
if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
if (TEST_BIT (contains_call, bb->index))
break;
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (!flow_bb_inside_loop_p (loop, e->dest))
break;
if (e)
OSDN Git Service
