/* Loop invariant motion.
- Copyright (C) 2003, 2004 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. */
#define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
? NULL \
- : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
+ : (struct lim_aux_data *) (stmt_ann (STMT)->aux))
/* Description of a memory reference for store motion. */
{
/* 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 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. */
/* 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;
{
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)
{
bb = BASIC_BLOCK (i);
add_bb_to_loop (bb,
- find_common_loop (EDGE_SUCC (bb, 0)->dest->loop_father,
- EDGE_PRED (bb, 0)->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_empty_p (vars_to_rename))
- {
- /* 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
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);
}
/* 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, get_stmt_uid (stmt)))
- continue;
- SET_BIT (seen, get_stmt_uid (stmt));
+ 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_ALL_VIRTUALS)
- {
- var = SSA_NAME_VAR (var);
- bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
- }
+ 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 (INDIRECT_REF_P (base))
{
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_stmt_uid = 0;
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;
}
OSDN Git Service
