/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
-
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
+
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 2, or (at your option) any
+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 COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This pass tries to find the optimal set of induction variables for the loop.
It optimizes just the basic linear induction variables (although adding
4) The trees are transformed to use the new variables, the dead code is
removed.
-
+
All of this is done loop by loop. Doing it globally is theoretically
possible, it might give a better performance and it might enable us
to decide costs more precisely, but getting all the interactions right
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
-#include "varray.h"
#include "expr.h"
#include "tree-pass.h"
#include "ggc.h"
struct iv *iv; /* Induction variable description. */
bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
an expression that is not an induction variable. */
- unsigned inv_id; /* Id of an invariant. */
bool preserve_biv; /* For the original biv, whether to preserve it. */
+ unsigned inv_id; /* Id of an invariant. */
};
/* Types of uses. */
USE_COMPARE /* Use is a compare. */
};
+/* Cost of a computation. */
+typedef struct
+{
+ int cost; /* The runtime cost. */
+ unsigned complexity; /* The estimate of the complexity of the code for
+ the computation (in no concrete units --
+ complexity field should be larger for more
+ complex expressions and addressing modes). */
+} comp_cost;
+
+static const comp_cost zero_cost = {0, 0};
+static const comp_cost infinite_cost = {INFTY, INFTY};
+
/* The candidate - cost pair. */
struct cost_pair
{
struct iv_cand *cand; /* The candidate. */
- unsigned cost; /* The cost. */
+ comp_cost cost; /* The cost. */
bitmap depends_on; /* The list of invariants that have to be
preserved. */
tree value; /* For final value elimination, the expression for
unsigned id; /* The id of the use. */
enum use_type type; /* Type of the use. */
struct iv *iv; /* The induction variable it is based on. */
- tree stmt; /* Statement in that it occurs. */
+ gimple stmt; /* Statement in that it occurs. */
tree *op_p; /* The place where it occurs. */
bitmap related_cands; /* The set of "related" iv candidates, plus the common
important ones. */
{
IP_NORMAL, /* At the end, just before the exit condition. */
IP_END, /* At the end of the latch block. */
+ IP_BEFORE_USE, /* Immediately before a specific use. */
+ IP_AFTER_USE, /* Immediately after a specific use. */
IP_ORIGINAL /* The original biv. */
};
unsigned id; /* The number of the candidate. */
bool important; /* Whether this is an "important" candidate, i.e. such
that it should be considered by all uses. */
- enum iv_position pos; /* Where it is computed. */
- tree incremented_at; /* For original biv, the statement where it is
+ ENUM_BITFIELD(iv_position) pos : 8; /* Where it is computed. */
+ gimple incremented_at;/* For original biv, the statement where it is
incremented. */
tree var_before; /* The variable used for it before increment. */
tree var_after; /* The variable used for it after increment. */
to replace the final value of an iv by direct
computation of the value. */
unsigned cost; /* Cost of the candidate. */
+ unsigned cost_step; /* Cost of the candidate's increment operation. */
+ struct iv_use *ainc_use; /* For IP_{BEFORE,AFTER}_USE candidates, the place
+ where it is incremented. */
bitmap depends_on; /* The list of invariants that are used in step of the
biv. */
};
/* The currently optimized loop. */
struct loop *current_loop;
- /* Number of registers used in it. */
- unsigned regs_used;
-
/* Numbers of iterations for all exits of the current loop. */
struct pointer_map_t *niters;
+ /* Number of registers used in it. */
+ unsigned regs_used;
+
/* The size of version_info array allocated. */
unsigned version_info_size;
/* The bitmap of indices in version_info whose value was changed. */
bitmap relevant;
- /* The maximum invariant id. */
- unsigned max_inv_id;
-
/* The uses of induction variables. */
VEC(iv_use_p,heap) *iv_uses;
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* The maximum invariant id. */
+ unsigned max_inv_id;
+
/* Whether to consider just related and important candidates when replacing a
use. */
bool consider_all_candidates;
+
+ /* Are we optimizing for speed? */
+ bool speed;
};
/* An assignment of iv candidates to uses. */
unsigned n_regs;
/* Total cost of expressing uses. */
- unsigned cand_use_cost;
+ comp_cost cand_use_cost;
/* Total cost of candidates. */
unsigned cand_cost;
unsigned *n_invariant_uses;
/* Total cost of the assignment. */
- unsigned cost;
+ comp_cost cost;
};
/* Difference of two iv candidate assignments. */
}
fprintf (file, " in statement ");
- print_generic_expr (file, use->stmt, TDF_SLIM);
+ print_gimple_stmt (file, use->stmt, 0, 0);
fprintf (file, "\n");
fprintf (file, " at position ");
fprintf (file, " incremented before exit test\n");
break;
+ case IP_BEFORE_USE:
+ fprintf (file, " incremented before use %d\n", cand->ainc_use->id);
+ break;
+
+ case IP_AFTER_USE:
+ fprintf (file, " incremented after use %d\n", cand->ainc_use->id);
+ break;
+
case IP_END:
fprintf (file, " incremented at end\n");
break;
emitted in LOOP. */
static bool
-stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
+stmt_after_ip_normal_pos (struct loop *loop, gimple stmt)
{
- basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
+ basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);
gcc_assert (bb);
}
/* Returns true if STMT if after the place where the original induction
- variable CAND is incremented. */
+ variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
+ if the positions are identical. */
static bool
-stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
+stmt_after_inc_pos (struct iv_cand *cand, gimple stmt, bool true_if_equal)
{
- basic_block cand_bb = bb_for_stmt (cand->incremented_at);
- basic_block stmt_bb = bb_for_stmt (stmt);
- block_stmt_iterator bsi;
+ basic_block cand_bb = gimple_bb (cand->incremented_at);
+ basic_block stmt_bb = gimple_bb (stmt);
if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
return false;
if (stmt_bb != cand_bb)
return true;
- /* Scan the block from the end, since the original ivs are usually
- incremented at the end of the loop body. */
- for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
- {
- if (bsi_stmt (bsi) == cand->incremented_at)
- return false;
- if (bsi_stmt (bsi) == stmt)
- return true;
- }
+ if (true_if_equal
+ && gimple_uid (stmt) == gimple_uid (cand->incremented_at))
+ return true;
+ return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
}
/* Returns true if STMT if after the place where the induction variable
CAND is incremented in LOOP. */
static bool
-stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
+stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple stmt)
{
switch (cand->pos)
{
return stmt_after_ip_normal_pos (loop, stmt);
case IP_ORIGINAL:
- return stmt_after_ip_original_pos (cand, stmt);
+ case IP_AFTER_USE:
+ return stmt_after_inc_pos (cand, stmt, false);
+
+ case IP_BEFORE_USE:
+ return stmt_after_inc_pos (cand, stmt, true);
default:
gcc_unreachable ();
idx_contains_abnormal_ssa_name_p (tree base, tree *index,
void *data ATTRIBUTE_UNUSED)
{
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
return false;
/* If this is a pointer casted to any type, we need to determine
the base object for the pointer; so handle conversions before
throwing away non-pointer expressions. */
- if (TREE_CODE (expr) == NOP_EXPR
- || TREE_CODE (expr) == CONVERT_EXPR)
+ if (CONVERT_EXPR_P (expr))
return determine_base_object (TREE_OPERAND (expr, 0));
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
if (!name_info (data, var)->iv)
{
- bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ bb = gimple_bb (SSA_NAME_DEF_STMT (var));
if (!bb
|| !flow_bb_inside_loop_p (data->current_loop, bb))
not define a simple affine biv with nonzero step. */
static tree
-determine_biv_step (tree phi)
+determine_biv_step (gimple phi)
{
- struct loop *loop = bb_for_stmt (phi)->loop_father;
+ struct loop *loop = gimple_bb (phi)->loop_father;
tree name = PHI_RESULT (phi);
affine_iv iv;
if (!is_gimple_reg (name))
return NULL_TREE;
- if (!simple_iv (loop, phi, name, &iv, true))
+ if (!simple_iv (loop, loop, name, &iv, true))
return NULL_TREE;
return integer_zerop (iv.step) ? NULL_TREE : iv.step;
static bool
find_bivs (struct ivopts_data *data)
{
- tree phi, step, type, base;
+ gimple phi;
+ tree step, type, base;
bool found = false;
struct loop *loop = data->current_loop;
+ gimple_stmt_iterator psi;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
+
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
continue;
type = TREE_TYPE (PHI_RESULT (phi));
base = fold_convert (type, base);
if (step)
- step = fold_convert (type, step);
+ {
+ if (POINTER_TYPE_P (type))
+ step = fold_convert (sizetype, step);
+ else
+ step = fold_convert (type, step);
+ }
set_iv (data, PHI_RESULT (phi), base, step);
found = true;
static void
mark_bivs (struct ivopts_data *data)
{
- tree phi, var;
+ gimple phi;
+ tree var;
struct iv *iv, *incr_iv;
struct loop *loop = data->current_loop;
basic_block incr_bb;
+ gimple_stmt_iterator psi;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
+
iv = get_iv (data, PHI_RESULT (phi));
if (!iv)
continue;
continue;
/* If the increment is in the subloop, ignore it. */
- incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ incr_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
if (incr_bb->loop_father != data->current_loop
|| (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
continue;
parameters to IV. */
static bool
-find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
+find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv)
{
tree lhs;
struct loop *loop = data->current_loop;
iv->base = NULL_TREE;
iv->step = NULL_TREE;
- if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
return false;
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, GIMPLE_STMT_OPERAND (stmt, 1), iv, true))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
return false;
iv->base = expand_simple_operations (iv->base);
/* Finds general ivs in statement STMT. */
static void
-find_givs_in_stmt (struct ivopts_data *data, tree stmt)
+find_givs_in_stmt (struct ivopts_data *data, gimple stmt)
{
affine_iv iv;
if (!find_givs_in_stmt_scev (data, stmt, &iv))
return;
- set_iv (data, GIMPLE_STMT_OPERAND (stmt, 0), iv.base, iv.step);
+ set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step);
}
/* Finds general ivs in basic block BB. */
static void
find_givs_in_bb (struct ivopts_data *data, basic_block bb)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_givs_in_stmt (data, bsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_givs_in_stmt (data, gsi_stmt (bsi));
}
/* Finds general ivs. */
print_generic_expr (dump_file, niter, TDF_SLIM);
fprintf (dump_file, "\n\n");
};
-
+
fprintf (dump_file, "Induction variables:\n\n");
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
static struct iv_use *
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
- tree stmt, enum use_type use_type)
+ gimple stmt, enum use_type use_type)
{
struct iv_use *use = XCNEW (struct iv_use);
|| !is_gimple_reg (op))
return;
- bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
+ bb = gimple_bb (SSA_NAME_DEF_STMT (op));
if (bb
&& flow_bb_inside_loop_p (data->current_loop, bb))
return;
{
struct iv *iv;
struct iv *civ;
- tree stmt;
+ gimple stmt;
struct iv_use *use;
if (TREE_CODE (op) != SSA_NAME)
iv = get_iv (data, op);
if (!iv)
return NULL;
-
+
if (iv->have_use_for)
{
use = iv_use (data, iv->use_id);
*civ = *iv;
stmt = SSA_NAME_DEF_STMT (op);
- gcc_assert (TREE_CODE (stmt) == PHI_NODE
- || TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
+ gcc_assert (gimple_code (stmt) == GIMPLE_PHI
+ || is_gimple_assign (stmt));
use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
iv->use_id = use->id;
return use;
}
-/* Given a condition *COND_P, checks whether it is a compare of an induction
- variable and an invariant. If this is the case, CONTROL_VAR is set
- to location of the iv, BOUND to the location of the invariant,
- IV_VAR and IV_BOUND are set to the corresponding induction variable
- descriptions, and true is returned. If this is not the case,
- CONTROL_VAR and BOUND are set to the arguments of the condition and
- false is returned. */
+/* Given a condition in statement STMT, checks whether it is a compare
+ of an induction variable and an invariant. If this is the case,
+ CONTROL_VAR is set to location of the iv, BOUND to the location of
+ the invariant, IV_VAR and IV_BOUND are set to the corresponding
+ induction variable descriptions, and true is returned. If this is not
+ the case, CONTROL_VAR and BOUND are set to the arguments of the
+ condition and false is returned. */
static bool
-extract_cond_operands (struct ivopts_data *data, tree *cond_p,
+extract_cond_operands (struct ivopts_data *data, gimple stmt,
tree **control_var, tree **bound,
struct iv **iv_var, struct iv **iv_bound)
{
- /* The nodes returned when COND has just one operand. Note that you should
- not modify anything in BOUND or IV_BOUND because of this. */
+ /* The objects returned when COND has constant operands. */
static struct iv const_iv;
static tree zero;
- tree cond = *cond_p;
tree *op0 = &zero, *op1 = &zero, *tmp_op;
struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
bool ret = false;
- zero = integer_zero_node;
- const_iv.step = integer_zero_node;
-
- if (TREE_CODE (cond) == SSA_NAME)
+ if (gimple_code (stmt) == GIMPLE_COND)
{
- op0 = cond_p;
- iv0 = get_iv (data, cond);
- ret = (iv0 && !integer_zerop (iv0->step));
- goto end;
+ op0 = gimple_cond_lhs_ptr (stmt);
+ op1 = gimple_cond_rhs_ptr (stmt);
}
-
- if (!COMPARISON_CLASS_P (cond))
+ else
{
- op0 = cond_p;
- goto end;
+ op0 = gimple_assign_rhs1_ptr (stmt);
+ op1 = gimple_assign_rhs2_ptr (stmt);
}
- op0 = &TREE_OPERAND (cond, 0);
- op1 = &TREE_OPERAND (cond, 1);
+ zero = integer_zero_node;
+ const_iv.step = integer_zero_node;
+
if (TREE_CODE (*op0) == SSA_NAME)
iv0 = get_iv (data, *op0);
if (TREE_CODE (*op1) == SSA_NAME)
return ret;
}
-/* Checks whether the condition *COND_P in STMT is interesting
- and if so, records it. */
+/* Checks whether the condition in STMT is interesting and if so,
+ records it. */
static void
-find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+find_interesting_uses_cond (struct ivopts_data *data, gimple stmt)
{
tree *var_p, *bound_p;
struct iv *var_iv, *civ;
- if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
+ if (!extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL))
{
find_interesting_uses_op (data, *var_p);
find_interesting_uses_op (data, *bound_p);
civ = XNEW (struct iv);
*civ = *var_iv;
- record_use (data, cond_p, civ, stmt, USE_COMPARE);
+ record_use (data, NULL, civ, stmt, USE_COMPARE);
}
/* Returns true if expression EXPR is obviously invariant in LOOP,
- i.e. if all its operands are defined outside of the LOOP. */
+ i.e. if all its operands are defined outside of the LOOP. LOOP
+ should not be the function body. */
bool
expr_invariant_in_loop_p (struct loop *loop, tree expr)
basic_block def_bb;
unsigned i, len;
+ gcc_assert (loop_depth (loop) > 0);
+
if (is_gimple_min_invariant (expr))
return true;
if (TREE_CODE (expr) == SSA_NAME)
{
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return false;
return true;
}
- if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
+ if (!EXPR_P (expr))
return false;
len = TREE_OPERAND_LENGTH (expr);
return true;
}
+/* Returns true if statement STMT is obviously invariant in LOOP,
+ i.e. if all its operands on the RHS are defined outside of the LOOP.
+ LOOP should not be the function body. */
+
+bool
+stmt_invariant_in_loop_p (struct loop *loop, gimple stmt)
+{
+ unsigned i;
+ tree lhs;
+
+ gcc_assert (loop_depth (loop) > 0);
+
+ lhs = gimple_get_lhs (stmt);
+ for (i = 0; i < gimple_num_ops (stmt); i++)
+ {
+ tree op = gimple_op (stmt, i);
+ if (op != lhs && !expr_invariant_in_loop_p (loop, op))
+ return false;
+ }
+
+ return true;
+}
+
/* Cumulates the steps of indices into DATA and replaces their values with the
initial ones. Returns false when the value of the index cannot be determined.
Callback for for_each_index. */
struct ifs_ivopts_data
{
struct ivopts_data *ivopts_data;
- tree stmt;
+ gimple stmt;
tree step;
};
reference out of the loop (in order to take its address in strength
reduction). In order for this to work we need both lower bound
and step to be loop invariants. */
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
+ /* Moreover, for a range, the size needs to be invariant as well. */
+ if (TREE_CODE (base) == ARRAY_RANGE_REF
+ && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))))
+ return false;
+
step = array_ref_element_size (base);
lbound = array_ref_low_bound (base);
if (integer_zerop (iv->step))
return true;
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
step = array_ref_element_size (base);
{
struct ivopts_data *data = (struct ivopts_data *) vdata;
find_interesting_uses_op (data, *idx);
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
find_interesting_uses_op (data, array_ref_element_size (base));
find_interesting_uses_op (data, array_ref_low_bound (base));
return true;
}
-/* Returns true if memory reference REF may be unaligned. */
+/* If we can prove that TOP = cst * BOT for some constant cst,
+ store cst to MUL and return true. Otherwise return false.
+ The returned value is always sign-extended, regardless of the
+ signedness of TOP and BOT. */
static bool
-may_be_unaligned_p (tree ref)
+constant_multiple_of (tree top, tree bot, double_int *mul)
+{
+ tree mby;
+ enum tree_code code;
+ double_int res, p0, p1;
+ unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
+
+ STRIP_NOPS (top);
+ STRIP_NOPS (bot);
+
+ if (operand_equal_p (top, bot, 0))
+ {
+ *mul = double_int_one;
+ return true;
+ }
+
+ code = TREE_CODE (top);
+ switch (code)
+ {
+ case MULT_EXPR:
+ mby = TREE_OPERAND (top, 1);
+ if (TREE_CODE (mby) != INTEGER_CST)
+ return false;
+
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
+ return false;
+
+ *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
+ precision);
+ return true;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
+ || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
+ return false;
+
+ if (code == MINUS_EXPR)
+ p1 = double_int_neg (p1);
+ *mul = double_int_sext (double_int_add (p0, p1), precision);
+ return true;
+
+ case INTEGER_CST:
+ if (TREE_CODE (bot) != INTEGER_CST)
+ return false;
+
+ p0 = double_int_sext (tree_to_double_int (top), precision);
+ p1 = double_int_sext (tree_to_double_int (bot), precision);
+ if (double_int_zero_p (p1))
+ return false;
+ *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
+ precision);
+ return double_int_zero_p (res);
+
+ default:
+ return false;
+ }
+}
+
+/* Returns true if memory reference REF with step STEP may be unaligned. */
+
+static bool
+may_be_unaligned_p (tree ref, tree step)
{
tree base;
tree base_type;
base_type = TREE_TYPE (base);
base_align = TYPE_ALIGN (base_type);
- if (mode != BLKmode
- && (base_align < GET_MODE_ALIGNMENT (mode)
- || bitpos % GET_MODE_ALIGNMENT (mode) != 0
- || bitpos % BITS_PER_UNIT != 0))
- return true;
+ if (mode != BLKmode)
+ {
+ unsigned mode_align = GET_MODE_ALIGNMENT (mode);
+
+ if (base_align < mode_align
+ || (bitpos % mode_align) != 0
+ || (bitpos % BITS_PER_UNIT) != 0)
+ return true;
+
+ if (toffset
+ && (highest_pow2_factor (toffset) * BITS_PER_UNIT) < mode_align)
+ return true;
+
+ if ((highest_pow2_factor (step) * BITS_PER_UNIT) < mode_align)
+ return true;
+ }
return false;
}
{
switch (TREE_CODE (expr))
{
+ case TARGET_MEM_REF:
+ /* TARGET_MEM_REFs are translated directly to valid MEMs on the
+ target, thus they are always addressable. */
+ return false;
+
case COMPONENT_REF:
return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
|| may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
- case ARRAY_REF:
- case ARRAY_RANGE_REF:
- return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
-
case VIEW_CONVERT_EXPR:
/* This kind of view-conversions may wrap non-addressable objects
and make them look addressable. After some processing the
non-addressability may be uncovered again, causing ADDR_EXPRs
of inappropriate objects to be built. */
- return AGGREGATE_TYPE_P (TREE_TYPE (expr))
- && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
+ if (is_gimple_reg (TREE_OPERAND (expr, 0))
+ || !is_gimple_addressable (TREE_OPERAND (expr, 0)))
+ return true;
+
+ /* ... fall through ... */
+
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+ CASE_CONVERT:
+ return true;
default:
break;
/* Finds addresses in *OP_P inside STMT. */
static void
-find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
+find_interesting_uses_address (struct ivopts_data *data, gimple stmt, tree *op_p)
{
tree base = *op_p, step = build_int_cst (sizetype, 0);
struct iv *civ;
/* Do not play with volatile memory references. A bit too conservative,
perhaps, but safe. */
- if (stmt_ann (stmt)->has_volatile_ops)
+ if (gimple_has_volatile_ops (stmt))
goto fail;
/* Ignore bitfields for now. Not really something terribly complicated
if (TREE_CODE (base) == BIT_FIELD_REF)
goto fail;
- if (may_be_nonaddressable_p (base))
- goto fail;
-
- if (STRICT_ALIGNMENT
- && may_be_unaligned_p (base))
- goto fail;
-
base = unshare_expr (base);
if (TREE_CODE (base) == TARGET_MEM_REF)
gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+ /* Check that the base expression is addressable. This needs
+ to be done after substituting bases of IVs into it. */
+ if (may_be_nonaddressable_p (base))
+ goto fail;
+
+ /* Moreover, on strict alignment platforms, check that it is
+ sufficiently aligned. */
+ if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
+ goto fail;
+
base = build_fold_addr_expr (base);
/* Substituting bases of IVs into the base expression might
while (handled_component_p (*ref))
ref = &TREE_OPERAND (*ref, 0);
if (TREE_CODE (*ref) == INDIRECT_REF)
- *ref = fold_indirect_ref (*ref);
+ {
+ tree tem = gimple_fold_indirect_ref (TREE_OPERAND (*ref, 0));
+ if (tem)
+ *ref = tem;
+ }
}
}
/* Finds and records invariants used in STMT. */
static void
-find_invariants_stmt (struct ivopts_data *data, tree stmt)
+find_invariants_stmt (struct ivopts_data *data, gimple stmt)
{
ssa_op_iter iter;
use_operand_p use_p;
/* Finds interesting uses of induction variables in the statement STMT. */
static void
-find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
+find_interesting_uses_stmt (struct ivopts_data *data, gimple stmt)
{
struct iv *iv;
- tree op, lhs, rhs;
+ tree op, *lhs, *rhs;
ssa_op_iter iter;
use_operand_p use_p;
+ enum tree_code code;
find_invariants_stmt (data, stmt);
- if (TREE_CODE (stmt) == COND_EXPR)
+ if (gimple_code (stmt) == GIMPLE_COND)
{
- find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
+ find_interesting_uses_cond (data, stmt);
return;
}
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ if (is_gimple_assign (stmt))
{
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ lhs = gimple_assign_lhs_ptr (stmt);
+ rhs = gimple_assign_rhs1_ptr (stmt);
- if (TREE_CODE (lhs) == SSA_NAME)
+ if (TREE_CODE (*lhs) == SSA_NAME)
{
/* If the statement defines an induction variable, the uses are not
interesting by themselves. */
- iv = get_iv (data, lhs);
+ iv = get_iv (data, *lhs);
if (iv && !integer_zerop (iv->step))
return;
}
- switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
+ code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+ && (REFERENCE_CLASS_P (*rhs)
+ || is_gimple_val (*rhs)))
{
- case tcc_comparison:
- find_interesting_uses_cond (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 1));
- return;
+ if (REFERENCE_CLASS_P (*rhs))
+ find_interesting_uses_address (data, stmt, rhs);
+ else
+ find_interesting_uses_op (data, *rhs);
- case tcc_reference:
- find_interesting_uses_address (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 1));
- if (REFERENCE_CLASS_P (lhs))
- find_interesting_uses_address (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 0));
+ if (REFERENCE_CLASS_P (*lhs))
+ find_interesting_uses_address (data, stmt, lhs);
return;
-
- default: ;
}
-
- if (REFERENCE_CLASS_P (lhs)
- && is_gimple_val (rhs))
+ else if (TREE_CODE_CLASS (code) == tcc_comparison)
{
- find_interesting_uses_address (data, stmt,
- &GIMPLE_STMT_OPERAND (stmt, 0));
- find_interesting_uses_op (data, rhs);
+ find_interesting_uses_cond (data, stmt);
return;
}
call (memory). */
}
- if (TREE_CODE (stmt) == PHI_NODE
- && bb_for_stmt (stmt) == data->current_loop->header)
+ if (gimple_code (stmt) == GIMPLE_PHI
+ && gimple_bb (stmt) == data->current_loop->header)
{
- lhs = PHI_RESULT (stmt);
- iv = get_iv (data, lhs);
+ iv = get_iv (data, PHI_RESULT (stmt));
if (iv && !integer_zerop (iv->step))
return;
static void
find_interesting_uses_outside (struct ivopts_data *data, edge exit)
{
- tree phi, def;
+ gimple phi;
+ gimple_stmt_iterator psi;
+ tree def;
- for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
if (is_gimple_reg (def))
find_interesting_uses_op (data, def);
find_interesting_uses (struct ivopts_data *data)
{
basic_block bb;
- block_stmt_iterator bsi;
- tree phi;
+ gimple_stmt_iterator bsi;
basic_block *body = get_loop_body (data->current_loop);
unsigned i;
struct version_info *info;
&& !flow_bb_inside_loop_p (data->current_loop, e->dest))
find_interesting_uses_outside (data, e);
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- find_interesting_uses_stmt (data, phi);
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_interesting_uses_stmt (data, bsi_stmt (bsi));
+ for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ if (!is_gimple_debug (gsi_stmt (bsi)))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
}
if (dump_file && (dump_flags & TDF_DETAILS))
return fold_convert (orig_type, expr);
+ case MULT_EXPR:
+ op1 = TREE_OPERAND (expr, 1);
+ if (!cst_and_fits_in_hwi (op1))
+ return orig_expr;
+
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, false, false, &off0);
+ if (op0 == TREE_OPERAND (expr, 0))
+ return orig_expr;
+
+ *offset = off0 * int_cst_value (op1);
+ if (integer_zerop (op0))
+ expr = op0;
+ else
+ expr = fold_build2 (MULT_EXPR, type, op0, op1);
+
+ return fold_convert (orig_type, expr);
+
case ARRAY_REF:
+ case ARRAY_RANGE_REF:
if (!inside_addr)
return orig_expr;
static struct iv_cand *
add_candidate_1 (struct ivopts_data *data,
tree base, tree step, bool important, enum iv_position pos,
- struct iv_use *use, tree incremented_at)
+ struct iv_use *use, gimple incremented_at)
{
unsigned i;
struct iv_cand *cand = NULL;
tree type, orig_type;
-
+
if (base)
{
orig_type = TREE_TYPE (base);
if (cand->pos != pos)
continue;
- if (cand->incremented_at != incremented_at)
+ if (cand->incremented_at != incremented_at
+ || ((pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+ && cand->ainc_use != use))
continue;
if (!cand->iv)
walk_tree (&step, find_depends, &cand->depends_on, NULL);
}
+ if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+ cand->ainc_use = use;
+ else
+ cand->ainc_use = NULL;
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_cand (dump_file, cand);
}
return false;
}
+/* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
+ Important field is set to IMPORTANT. */
+
+static void
+add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
+ bool important, struct iv_use *use)
+{
+ basic_block use_bb = gimple_bb (use->stmt);
+ enum machine_mode mem_mode;
+ unsigned HOST_WIDE_INT cstepi;
+
+ /* If we insert the increment in any position other than the standard
+ ones, we must ensure that it is incremented once per iteration.
+ It must not be in an inner nested loop, or one side of an if
+ statement. */
+ if (use_bb->loop_father != data->current_loop
+ || !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
+ || stmt_could_throw_p (use->stmt)
+ || !cst_and_fits_in_hwi (step))
+ return;
+
+ cstepi = int_cst_value (step);
+
+ mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
+ if ((HAVE_PRE_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+ || (HAVE_PRE_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+ {
+ enum tree_code code = MINUS_EXPR;
+ tree new_base;
+ tree new_step = step;
+
+ if (POINTER_TYPE_P (TREE_TYPE (base)))
+ {
+ new_step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
+ code = POINTER_PLUS_EXPR;
+ }
+ else
+ new_step = fold_convert (TREE_TYPE (base), new_step);
+ new_base = fold_build2 (code, TREE_TYPE (base), base, new_step);
+ add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
+ use->stmt);
+ }
+ if ((HAVE_POST_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+ || (HAVE_POST_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+ {
+ add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
+ use->stmt);
+ }
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. The candidate computation is scheduled on all available positions. */
static void
-add_candidate (struct ivopts_data *data,
+add_candidate (struct ivopts_data *data,
tree base, tree step, bool important, struct iv_use *use)
{
if (ip_normal_pos (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
+ add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL);
if (ip_end_pos (data->current_loop)
&& allow_ip_end_pos_p (data->current_loop))
- add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
+ add_candidate_1 (data, base, step, important, IP_END, use, NULL);
+
+ if (use != NULL && use->type == USE_ADDRESS)
+ add_autoinc_candidates (data, base, step, important, use);
}
/* Add a standard "0 + 1 * iteration" iv candidate for a
static void
add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
{
- tree phi, def;
+ gimple phi;
+ tree def;
struct iv_cand *cand;
add_candidate (data, iv->base, iv->step, true, NULL);
/* The same, but with initial value zero. */
- add_candidate (data,
- build_int_cst (TREE_TYPE (iv->base), 0),
- iv->step, true, NULL);
+ if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
+ add_candidate (data, size_int (0), iv->step, true, NULL);
+ else
+ add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
+ iv->step, true, NULL);
phi = SSA_NAME_DEF_STMT (iv->ssa_name);
- if (TREE_CODE (phi) == PHI_NODE)
+ if (gimple_code (phi) == GIMPLE_PHI)
{
/* Additionally record the possibility of leaving the original iv
untouched. */
{
unsigned HOST_WIDE_INT offset;
tree base;
+ tree basetype;
add_candidate (data, iv->base, iv->step, false, use);
/* The same, but with initial value zero. Make such variable important,
since it is generic enough so that possibly many uses may be based
on it. */
- add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
+ basetype = TREE_TYPE (iv->base);
+ if (POINTER_TYPE_P (basetype))
+ basetype = sizetype;
+ add_candidate (data, build_int_cst (basetype, 0),
iv->step, true, use);
- /* Third, try removing the constant offset. */
+ /* Third, try removing the constant offset. Make sure to even
+ add a candidate for &a[0] vs. (T *)&a. */
base = strip_offset (iv->base, &offset);
- if (offset)
+ if (offset
+ || base != iv->base)
add_candidate (data, base, iv->step, false, use);
}
}
}
-/* Finds the candidates for the induction variables. */
-
-static void
-find_iv_candidates (struct ivopts_data *data)
-{
- /* Add commonly used ivs. */
- add_standard_iv_candidates (data);
-
- /* Add old induction variables. */
- add_old_ivs_candidates (data);
-
- /* Add induction variables derived from uses. */
- add_derived_ivs_candidates (data);
-
- /* Record the important candidates. */
- record_important_candidates (data);
-}
-
/* Allocates the data structure mapping the (use, candidate) pairs to costs.
If consider_all_candidates is true, we use a two-dimensional array, otherwise
we allocate a simple list to every use. */
}
}
+/* Returns description of computation cost of expression whose runtime
+ cost is RUNTIME and complexity corresponds to COMPLEXITY. */
+
+static comp_cost
+new_cost (unsigned runtime, unsigned complexity)
+{
+ comp_cost cost;
+
+ cost.cost = runtime;
+ cost.complexity = complexity;
+
+ return cost;
+}
+
+/* Adds costs COST1 and COST2. */
+
+static comp_cost
+add_costs (comp_cost cost1, comp_cost cost2)
+{
+ cost1.cost += cost2.cost;
+ cost1.complexity += cost2.complexity;
+
+ return cost1;
+}
+/* Subtracts costs COST1 and COST2. */
+
+static comp_cost
+sub_costs (comp_cost cost1, comp_cost cost2)
+{
+ cost1.cost -= cost2.cost;
+ cost1.complexity -= cost2.complexity;
+
+ return cost1;
+}
+
+/* Returns a negative number if COST1 < COST2, a positive number if
+ COST1 > COST2, and 0 if COST1 = COST2. */
+
+static int
+compare_costs (comp_cost cost1, comp_cost cost2)
+{
+ if (cost1.cost == cost2.cost)
+ return cost1.complexity - cost2.complexity;
+
+ return cost1.cost - cost2.cost;
+}
+
+/* Returns true if COST is infinite. */
+
+static bool
+infinite_cost_p (comp_cost cost)
+{
+ return cost.cost == INFTY;
+}
+
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
on invariants DEPENDS_ON and that the value used in expressing it
- is VALUE.*/
+ is VALUE. */
static void
set_use_iv_cost (struct ivopts_data *data,
- struct iv_use *use, struct iv_cand *cand, unsigned cost,
- bitmap depends_on, tree value)
+ struct iv_use *use, struct iv_cand *cand,
+ comp_cost cost, bitmap depends_on, tree value)
{
unsigned i, s;
- if (cost == INFTY)
+ if (infinite_cost_p (cost))
{
BITMAP_FREE (depends_on);
return;
return ret;
}
-
+
/* n_map_members is a power of two, so this computes modulo. */
s = cand->id & (use->n_map_members - 1);
for (i = s; i < use->n_map_members; i++)
/* Returns estimate on cost of computing SEQ. */
static unsigned
-seq_cost (rtx seq)
+seq_cost (rtx seq, bool speed)
{
unsigned cost = 0;
rtx set;
{
set = single_set (seq);
if (set)
- cost += rtx_cost (set, SET);
+ cost += rtx_cost (set, SET,speed);
else
cost++;
}
static rtx
produce_memory_decl_rtl (tree obj, int *regno)
{
+ addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj));
+ enum machine_mode address_mode = targetm.addr_space.address_mode (as);
rtx x;
-
+
gcc_assert (obj);
if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
{
const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
- x = gen_rtx_SYMBOL_REF (Pmode, name);
+ x = gen_rtx_SYMBOL_REF (address_mode, name);
SET_SYMBOL_REF_DECL (x, obj);
x = gen_rtx_MEM (DECL_MODE (obj), x);
+ set_mem_addr_space (x, as);
targetm.encode_section_info (obj, x, true);
}
else
{
- x = gen_raw_REG (Pmode, (*regno)++);
+ x = gen_raw_REG (address_mode, (*regno)++);
x = gen_rtx_MEM (DECL_MODE (obj), x);
+ set_mem_addr_space (x, as);
}
return x;
/* Determines cost of the computation of EXPR. */
static unsigned
-computation_cost (tree expr)
+computation_cost (tree expr, bool speed)
{
rtx seq, rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
/* Avoid using hard regs in ways which may be unsupported. */
int regno = LAST_VIRTUAL_REGISTER + 1;
+ struct cgraph_node *node = cgraph_node (current_function_decl);
+ enum node_frequency real_frequency = node->frequency;
+ node->frequency = NODE_FREQUENCY_NORMAL;
+ crtl->maybe_hot_insn_p = speed;
walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
start_sequence ();
rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
seq = get_insns ();
end_sequence ();
+ default_rtl_profile ();
+ node->frequency = real_frequency;
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (MEM_P (rslt))
- cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
+ cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type),
+ TYPE_ADDR_SPACE (type), speed);
return cost;
}
/* Returns variable containing the value of candidate CAND at statement AT. */
static tree
-var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
+var_at_stmt (struct loop *loop, struct iv_cand *cand, gimple stmt)
{
if (stmt_after_increment (loop, cand, stmt))
return cand->var_after;
- else
- return cand->var_before;
-}
-
-/* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
- but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
-
-int
-tree_int_cst_sign_bit (tree t)
-{
- unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
- unsigned HOST_WIDE_INT w;
-
- if (bitno < HOST_BITS_PER_WIDE_INT)
- w = TREE_INT_CST_LOW (t);
- else
- {
- w = TREE_INT_CST_HIGH (t);
- bitno -= HOST_BITS_PER_WIDE_INT;
- }
-
- return (w >> bitno) & 1;
-}
-
-/* If we can prove that TOP = cst * BOT for some constant cst,
- store cst to MUL and return true. Otherwise return false.
- The returned value is always sign-extended, regardless of the
- signedness of TOP and BOT. */
-
-static bool
-constant_multiple_of (tree top, tree bot, double_int *mul)
-{
- tree mby;
- enum tree_code code;
- double_int res, p0, p1;
- unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
-
- STRIP_NOPS (top);
- STRIP_NOPS (bot);
-
- if (operand_equal_p (top, bot, 0))
- {
- *mul = double_int_one;
- return true;
- }
-
- code = TREE_CODE (top);
- switch (code)
- {
- case MULT_EXPR:
- mby = TREE_OPERAND (top, 1);
- if (TREE_CODE (mby) != INTEGER_CST)
- return false;
-
- if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
- return false;
-
- *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
- precision);
- return true;
-
- case PLUS_EXPR:
- case MINUS_EXPR:
- if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
- || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
- return false;
-
- if (code == MINUS_EXPR)
- p1 = double_int_neg (p1);
- *mul = double_int_sext (double_int_add (p0, p1), precision);
- return true;
+ else
+ return cand->var_before;
+}
- case INTEGER_CST:
- if (TREE_CODE (bot) != INTEGER_CST)
- return false;
+/* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
+ but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
- p0 = double_int_sext (tree_to_double_int (top), precision);
- p1 = double_int_sext (tree_to_double_int (bot), precision);
- if (double_int_zero_p (p1))
- return false;
- *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
- precision);
- return double_int_zero_p (res);
+int
+tree_int_cst_sign_bit (const_tree t)
+{
+ unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
+ unsigned HOST_WIDE_INT w;
- default:
- return false;
+ if (bitno < HOST_BITS_PER_WIDE_INT)
+ w = TREE_INT_CST_LOW (t);
+ else
+ {
+ w = TREE_INT_CST_HIGH (t);
+ bitno -= HOST_BITS_PER_WIDE_INT;
}
+
+ return (w >> bitno) & 1;
}
/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
tree suba, subb;
tree atype = TREE_TYPE (*a);
- if ((TREE_CODE (*a) == NOP_EXPR
- || TREE_CODE (*a) == CONVERT_EXPR))
+ if (CONVERT_EXPR_P (*a))
{
suba = TREE_OPERAND (*a, 0);
wider_type = TREE_TYPE (suba);
else
return atype;
- if ((TREE_CODE (*b) == NOP_EXPR
- || TREE_CODE (*b) == CONVERT_EXPR))
+ if (CONVERT_EXPR_P (*b))
{
subb = TREE_OPERAND (*b, 0);
if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
static bool
get_computation_aff (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at,
+ struct iv_use *use, struct iv_cand *cand, gimple at,
struct affine_tree_combination *aff)
{
tree ubase = use->iv->base;
if (stmt_after_increment (loop, cand, at))
{
aff_tree cstep_aff;
-
+
if (common_type != uutype)
cstep_common = fold_convert (common_type, cstep);
else
static tree
get_computation_at (struct loop *loop,
- struct iv_use *use, struct iv_cand *cand, tree at)
+ struct iv_use *use, struct iv_cand *cand, gimple at)
{
aff_tree aff;
tree type = TREE_TYPE (use->iv->base);
/* Returns cost of addition in MODE. */
static unsigned
-add_cost (enum machine_mode mode)
+add_cost (enum machine_mode mode, bool speed)
{
static unsigned costs[NUM_MACHINE_MODES];
rtx seq;
seq = get_insns ();
end_sequence ();
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (!cost)
cost = 1;
costs[mode] = cost;
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Addition in %s costs %d\n",
GET_MODE_NAME (mode), cost);
/* Returns cost of multiplication by constant CST in MODE. */
unsigned
-multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
+multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
{
static htab_t costs;
struct mbc_entry **cached, act;
gen_int_mode (cst, mode), NULL_RTX, 0);
seq = get_insns ();
end_sequence ();
-
- cost = seq_cost (seq);
+
+ cost = seq_cost (seq, speed);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
}
/* Returns true if multiplying by RATIO is allowed in an address. Test the
- validity for a memory reference accessing memory of mode MODE. */
+ validity for a memory reference accessing memory of mode MODE in
+ address space AS. */
+
+DEF_VEC_P (sbitmap);
+DEF_VEC_ALLOC_P (sbitmap, heap);
bool
-multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode,
+ addr_space_t as)
{
#define MAX_RATIO 128
- static sbitmap valid_mult[MAX_MACHINE_MODE];
-
- if (!valid_mult[mode])
+ unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mode;
+ static VEC (sbitmap, heap) *valid_mult_list;
+ sbitmap valid_mult;
+
+ if (data_index >= VEC_length (sbitmap, valid_mult_list))
+ VEC_safe_grow_cleared (sbitmap, heap, valid_mult_list, data_index + 1);
+
+ valid_mult = VEC_index (sbitmap, valid_mult_list, data_index);
+ if (!valid_mult)
{
- rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+ enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ rtx reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
rtx addr;
HOST_WIDE_INT i;
- valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
- sbitmap_zero (valid_mult[mode]);
- addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
+ valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
+ sbitmap_zero (valid_mult);
+ addr = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
{
- XEXP (addr, 1) = gen_int_mode (i, Pmode);
- if (memory_address_p (mode, addr))
- SET_BIT (valid_mult[mode], i + MAX_RATIO);
+ XEXP (addr, 1) = gen_int_mode (i, address_mode);
+ if (memory_address_addr_space_p (mode, addr, as))
+ SET_BIT (valid_mult, i + MAX_RATIO);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " allowed multipliers:");
for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
- if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
+ if (TEST_BIT (valid_mult, i + MAX_RATIO))
fprintf (dump_file, " %d", (int) i);
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
}
+
+ VEC_replace (sbitmap, valid_mult_list, data_index, valid_mult);
}
if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
return false;
- return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
+ return TEST_BIT (valid_mult, ratio + MAX_RATIO);
}
/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
variable is omitted. Compute the cost for a memory reference that accesses
- a memory location of mode MEM_MODE.
+ a memory location of mode MEM_MODE in address space AS.
+
+ MAY_AUTOINC is set to true if the autoincrement (increasing index by
+ size of MEM_MODE / RATIO) is available. To make this determination, we
+ look at the size of the increment to be made, which is given in CSTEP.
+ CSTEP may be zero if the step is unknown.
+ STMT_AFTER_INC is true iff the statement we're looking at is after the
+ increment of the original biv.
TODO -- there must be some better way. This all is quite crude. */
-static unsigned
+typedef struct
+{
+ HOST_WIDE_INT min_offset, max_offset;
+ unsigned costs[2][2][2][2];
+} *address_cost_data;
+
+DEF_VEC_P (address_cost_data);
+DEF_VEC_ALLOC_P (address_cost_data, heap);
+
+static comp_cost
get_address_cost (bool symbol_present, bool var_present,
unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
- enum machine_mode mem_mode)
-{
- static bool initialized[MAX_MACHINE_MODE];
- static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
- static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
- static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
- unsigned cost, acost;
- bool offset_p, ratio_p;
- HOST_WIDE_INT s_offset;
+ HOST_WIDE_INT cstep, enum machine_mode mem_mode,
+ addr_space_t as, bool speed,
+ bool stmt_after_inc, bool *may_autoinc)
+{
+ enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+ static VEC(address_cost_data, heap) *address_cost_data_list;
+ unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mem_mode;
+ address_cost_data data;
+ static bool has_preinc[MAX_MACHINE_MODE], has_postinc[MAX_MACHINE_MODE];
+ static bool has_predec[MAX_MACHINE_MODE], has_postdec[MAX_MACHINE_MODE];
+ unsigned cost, acost, complexity;
+ bool offset_p, ratio_p, autoinc;
+ HOST_WIDE_INT s_offset, autoinc_offset, msize;
unsigned HOST_WIDE_INT mask;
unsigned bits;
- if (!initialized[mem_mode])
+ if (data_index >= VEC_length (address_cost_data, address_cost_data_list))
+ VEC_safe_grow_cleared (address_cost_data, heap, address_cost_data_list,
+ data_index + 1);
+
+ data = VEC_index (address_cost_data, address_cost_data_list, data_index);
+ if (!data)
{
HOST_WIDE_INT i;
HOST_WIDE_INT start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
+ HOST_WIDE_INT rat, off;
int old_cse_not_expected;
unsigned sym_p, var_p, off_p, rat_p, add_c;
rtx seq, addr, base;
rtx reg0, reg1;
- initialized[mem_mode] = true;
+ data = (address_cost_data) xcalloc (1, sizeof (*data));
- reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+ reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
- addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
+ addr = gen_rtx_fmt_ee (PLUS, address_mode, reg1, NULL_RTX);
for (i = start; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = gen_int_mode (i, Pmode);
- if (!memory_address_p (mem_mode, addr))
+ XEXP (addr, 1) = gen_int_mode (i, address_mode);
+ if (!memory_address_addr_space_p (mem_mode, addr, as))
break;
}
- max_offset[mem_mode] = i == start ? 0 : i >> 1;
- off[mem_mode] = max_offset[mem_mode];
+ data->max_offset = i == start ? 0 : i >> 1;
+ off = data->max_offset;
for (i = start; i <= 1 << 20; i <<= 1)
{
- XEXP (addr, 1) = gen_int_mode (-i, Pmode);
- if (!memory_address_p (mem_mode, addr))
+ XEXP (addr, 1) = gen_int_mode (-i, address_mode);
+ if (!memory_address_addr_space_p (mem_mode, addr, as))
break;
}
- min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
+ data->min_offset = i == start ? 0 : -(i >> 1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "get_address_cost:\n");
fprintf (dump_file, " min offset %s %d\n",
GET_MODE_NAME (mem_mode),
- (int) min_offset[mem_mode]);
+ (int) data->min_offset);
fprintf (dump_file, " max offset %s %d\n",
GET_MODE_NAME (mem_mode),
- (int) max_offset[mem_mode]);
+ (int) data->max_offset);
}
- rat[mem_mode] = 1;
+ rat = 1;
for (i = 2; i <= MAX_RATIO; i++)
- if (multiplier_allowed_in_address_p (i, mem_mode))
+ if (multiplier_allowed_in_address_p (i, mem_mode, as))
{
- rat[mem_mode] = i;
+ rat = i;
break;
}
/* Compute the cost of various addressing modes. */
acost = 0;
- reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
- reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
+ reg0 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
+ reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
+ if (HAVE_PRE_DECREMENT)
+ {
+ addr = gen_rtx_PRE_DEC (address_mode, reg0);
+ has_predec[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ if (HAVE_POST_DECREMENT)
+ {
+ addr = gen_rtx_POST_DEC (address_mode, reg0);
+ has_postdec[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ if (HAVE_PRE_INCREMENT)
+ {
+ addr = gen_rtx_PRE_INC (address_mode, reg0);
+ has_preinc[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
+ if (HAVE_POST_INCREMENT)
+ {
+ addr = gen_rtx_POST_INC (address_mode, reg0);
+ has_postinc[mem_mode]
+ = memory_address_addr_space_p (mem_mode, addr, as);
+ }
for (i = 0; i < 16; i++)
{
sym_p = i & 1;
addr = reg0;
if (rat_p)
- addr = gen_rtx_fmt_ee (MULT, Pmode, addr,
- gen_int_mode (rat[mem_mode], Pmode));
+ addr = gen_rtx_fmt_ee (MULT, address_mode, addr,
+ gen_int_mode (rat, address_mode));
if (var_p)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+ addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, reg1);
if (sym_p)
{
- base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
+ base = gen_rtx_SYMBOL_REF (address_mode, ggc_strdup (""));
/* ??? We can run into trouble with some backends by presenting
- it with symbols which havn't been properly passed through
+ it with symbols which haven't been properly passed through
targetm.encode_section_info. By setting the local bit, we
enhance the probability of things working. */
SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
if (off_p)
- base = gen_rtx_fmt_e (CONST, Pmode,
- gen_rtx_fmt_ee (PLUS, Pmode,
- base,
- gen_int_mode (off[mem_mode],
- Pmode)));
+ base = gen_rtx_fmt_e (CONST, address_mode,
+ gen_rtx_fmt_ee
+ (PLUS, address_mode, base,
+ gen_int_mode (off, address_mode)));
}
else if (off_p)
- base = gen_int_mode (off[mem_mode], Pmode);
+ base = gen_int_mode (off, address_mode);
else
base = NULL_RTX;
-
+
if (base)
- addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
-
+ addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, base);
+
start_sequence ();
/* To avoid splitting addressing modes, pretend that no cse will
follow. */
old_cse_not_expected = cse_not_expected;
cse_not_expected = true;
- addr = memory_address (mem_mode, addr);
+ addr = memory_address_addr_space (mem_mode, addr, as);
cse_not_expected = old_cse_not_expected;
seq = get_insns ();
end_sequence ();
- acost = seq_cost (seq);
- acost += address_cost (addr, mem_mode);
+ acost = seq_cost (seq, speed);
+ acost += address_cost (addr, mem_mode, as, speed);
if (!acost)
acost = 1;
- costs[mem_mode][sym_p][var_p][off_p][rat_p] = acost;
+ data->costs[sym_p][var_p][off_p][rat_p] = acost;
}
/* On some targets, it is quite expensive to load symbol to a register,
If VAR_PRESENT is true, try whether the mode with
SYMBOL_PRESENT = false is cheaper even with cost of addition, and
if this is the case, use it. */
- add_c = add_cost (Pmode);
+ add_c = add_cost (address_mode, speed);
for (i = 0; i < 8; i++)
{
var_p = i & 1;
off_p = (i >> 1) & 1;
rat_p = (i >> 2) & 1;
- acost = costs[mem_mode][0][1][off_p][rat_p] + 1;
+ acost = data->costs[0][1][off_p][rat_p] + 1;
if (var_p)
acost += add_c;
- if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
- costs[mem_mode][1][var_p][off_p][rat_p] = acost;
+ if (acost < data->costs[1][var_p][off_p][rat_p])
+ data->costs[1][var_p][off_p][rat_p] = acost;
}
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Address costs:\n");
-
+
for (i = 0; i < 16; i++)
{
sym_p = i & 1;
if (rat_p)
fprintf (dump_file, "rat * ");
- acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
+ acost = data->costs[sym_p][var_p][off_p][rat_p];
fprintf (dump_file, "index costs %d\n", acost);
}
+ if (has_predec[mem_mode] || has_postdec[mem_mode]
+ || has_preinc[mem_mode] || has_postinc[mem_mode])
+ fprintf (dump_file, " May include autoinc/dec\n");
fprintf (dump_file, "\n");
}
+
+ VEC_replace (address_cost_data, address_cost_data_list,
+ data_index, data);
}
- bits = GET_MODE_BITSIZE (Pmode);
+ bits = GET_MODE_BITSIZE (address_mode);
mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
offset &= mask;
if ((offset >> (bits - 1) & 1))
offset |= ~mask;
s_offset = offset;
+ autoinc = false;
+ msize = GET_MODE_SIZE (mem_mode);
+ autoinc_offset = offset;
+ if (stmt_after_inc)
+ autoinc_offset += ratio * cstep;
+ if (symbol_present || var_present || ratio != 1)
+ autoinc = false;
+ else if ((has_postinc[mem_mode] && autoinc_offset == 0
+ && msize == cstep)
+ || (has_postdec[mem_mode] && autoinc_offset == 0
+ && msize == -cstep)
+ || (has_preinc[mem_mode] && autoinc_offset == msize
+ && msize == cstep)
+ || (has_predec[mem_mode] && autoinc_offset == -msize
+ && msize == -cstep))
+ autoinc = true;
+
cost = 0;
offset_p = (s_offset != 0
- && min_offset[mem_mode] <= s_offset
- && s_offset <= max_offset[mem_mode]);
+ && data->min_offset <= s_offset
+ && s_offset <= data->max_offset);
ratio_p = (ratio != 1
- && multiplier_allowed_in_address_p (ratio, mem_mode));
+ && multiplier_allowed_in_address_p (ratio, mem_mode, as));
if (ratio != 1 && !ratio_p)
- cost += multiply_by_cost (ratio, Pmode);
+ cost += multiply_by_cost (ratio, address_mode, speed);
if (s_offset && !offset_p && !symbol_present)
- cost += add_cost (Pmode);
+ cost += add_cost (address_mode, speed);
- acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
- return cost + acost;
+ if (may_autoinc)
+ *may_autoinc = autoinc;
+ acost = data->costs[symbol_present][var_present][offset_p][ratio_p];
+ complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
+ return new_cost (cost + acost, complexity);
}
/* Estimates cost of forcing expression EXPR into a variable. */
-unsigned
-force_expr_to_var_cost (tree expr)
+static comp_cost
+force_expr_to_var_cost (tree expr, bool speed)
{
static bool costs_initialized = false;
- static unsigned integer_cost;
- static unsigned symbol_cost;
- static unsigned address_cost;
+ static unsigned integer_cost [2];
+ static unsigned symbol_cost [2];
+ static unsigned address_cost [2];
tree op0, op1;
- unsigned cost0, cost1, cost;
+ comp_cost cost0, cost1, cost;
enum machine_mode mode;
if (!costs_initialized)
tree type = build_pointer_type (integer_type_node);
tree var, addr;
rtx x;
+ int i;
var = create_tmp_var_raw (integer_type_node, "test_var");
TREE_STATIC (var) = 1;
x = produce_memory_decl_rtl (var, NULL);
SET_DECL_RTL (var, x);
- integer_cost = computation_cost (build_int_cst (integer_type_node,
- 2000));
-
addr = build1 (ADDR_EXPR, type, var);
- symbol_cost = computation_cost (addr) + 1;
- address_cost
- = computation_cost (build2 (POINTER_PLUS_EXPR, type,
- addr,
- build_int_cst (sizetype, 2000))) + 1;
- if (dump_file && (dump_flags & TDF_DETAILS))
+
+ for (i = 0; i < 2; i++)
{
- fprintf (dump_file, "force_expr_to_var_cost:\n");
- fprintf (dump_file, " integer %d\n", (int) integer_cost);
- fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
- fprintf (dump_file, " address %d\n", (int) address_cost);
- fprintf (dump_file, " other %d\n", (int) target_spill_cost);
- fprintf (dump_file, "\n");
+ integer_cost[i] = computation_cost (build_int_cst (integer_type_node,
+ 2000), i);
+
+ symbol_cost[i] = computation_cost (addr, i) + 1;
+
+ address_cost[i]
+ = computation_cost (build2 (POINTER_PLUS_EXPR, type,
+ addr,
+ build_int_cst (sizetype, 2000)), i) + 1;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
+ fprintf (dump_file, " integer %d\n", (int) integer_cost[i]);
+ fprintf (dump_file, " symbol %d\n", (int) symbol_cost[i]);
+ fprintf (dump_file, " address %d\n", (int) address_cost[i]);
+ fprintf (dump_file, " other %d\n", (int) target_spill_cost[i]);
+ fprintf (dump_file, "\n");
+ }
}
costs_initialized = true;
STRIP_NOPS (expr);
if (SSA_VAR_P (expr))
- return 0;
+ return zero_cost;
- if (TREE_INVARIANT (expr))
+ if (is_gimple_min_invariant (expr))
{
if (TREE_CODE (expr) == INTEGER_CST)
- return integer_cost;
+ return new_cost (integer_cost [speed], 0);
if (TREE_CODE (expr) == ADDR_EXPR)
{
if (TREE_CODE (obj) == VAR_DECL
|| TREE_CODE (obj) == PARM_DECL
|| TREE_CODE (obj) == RESULT_DECL)
- return symbol_cost;
+ return new_cost (symbol_cost [speed], 0);
}
- return address_cost;
+ return new_cost (address_cost [speed], 0);
}
switch (TREE_CODE (expr))
STRIP_NOPS (op1);
if (is_gimple_val (op0))
- cost0 = 0;
+ cost0 = zero_cost;
else
- cost0 = force_expr_to_var_cost (op0);
+ cost0 = force_expr_to_var_cost (op0, speed);
if (is_gimple_val (op1))
- cost1 = 0;
+ cost1 = zero_cost;
+ else
+ cost1 = force_expr_to_var_cost (op1, speed);
+
+ break;
+
+ case NEGATE_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ STRIP_NOPS (op0);
+ op1 = NULL_TREE;
+
+ if (is_gimple_val (op0))
+ cost0 = zero_cost;
else
- cost1 = force_expr_to_var_cost (op1);
+ cost0 = force_expr_to_var_cost (op0, speed);
+ cost1 = zero_cost;
break;
default:
/* Just an arbitrary value, FIXME. */
- return target_spill_cost;
+ return new_cost (target_spill_cost[speed], 0);
}
mode = TYPE_MODE (TREE_TYPE (expr));
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
- cost = add_cost (mode);
+ case NEGATE_EXPR:
+ cost = new_cost (add_cost (mode, speed), 0);
break;
case MULT_EXPR:
if (cst_and_fits_in_hwi (op0))
- cost = multiply_by_cost (int_cst_value (op0), mode);
+ cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
else if (cst_and_fits_in_hwi (op1))
- cost = multiply_by_cost (int_cst_value (op1), mode);
+ cost = new_cost (multiply_by_cost (int_cst_value (op1), mode, speed), 0);
else
- return target_spill_cost;
+ return new_cost (target_spill_cost [speed], 0);
break;
default:
gcc_unreachable ();
}
- cost += cost0;
- cost += cost1;
+ cost = add_costs (cost, cost0);
+ cost = add_costs (cost, cost1);
/* Bound the cost by target_spill_cost. The parts of complicated
computations often are either loop invariant or at least can
be shared between several iv uses, so letting this grow without
limits would not give reasonable results. */
- return cost < target_spill_cost ? cost : target_spill_cost;
+ if (cost.cost > (int) target_spill_cost [speed])
+ cost.cost = target_spill_cost [speed];
+
+ return cost;
}
/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
invariants the computation depends on. */
-static unsigned
+static comp_cost
force_var_cost (struct ivopts_data *data,
tree expr, bitmap *depends_on)
{
walk_tree (&expr, find_depends, depends_on, NULL);
}
- return force_expr_to_var_cost (expr);
+ return force_expr_to_var_cost (expr, data->speed);
}
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
to false if the corresponding part is missing. DEPENDS_ON is a set of the
invariants the computation depends on. */
-static unsigned
+static comp_cost
split_address_cost (struct ivopts_data *data,
tree addr, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
tree toffset;
enum machine_mode mode;
int unsignedp, volatilep;
-
+
core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
&unsignedp, &volatilep, false);
*var_present = true;
fd_ivopts_data = data;
walk_tree (&addr, find_depends, depends_on, NULL);
- return target_spill_cost;
+ return new_cost (target_spill_cost[data->speed], 0);
}
*offset += bitpos / BITS_PER_UNIT;
{
*symbol_present = true;
*var_present = false;
- return 0;
+ return zero_cost;
}
-
+
*symbol_present = false;
*var_present = true;
- return 0;
+ return zero_cost;
}
/* Estimates cost of expressing difference of addresses E1 - E2 as
part is missing. DEPENDS_ON is a set of the invariants the computation
depends on. */
-static unsigned
+static comp_cost
ptr_difference_cost (struct ivopts_data *data,
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
HOST_WIDE_INT diff = 0;
- unsigned cost;
+ aff_tree aff_e1, aff_e2;
+ tree type;
gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
*offset += diff;
*symbol_present = false;
*var_present = false;
- return 0;
+ return zero_cost;
}
- if (e2 == integer_zero_node)
+ if (integer_zerop (e2))
return split_address_cost (data, TREE_OPERAND (e1, 0),
symbol_present, var_present, offset, depends_on);
*symbol_present = false;
*var_present = true;
-
- cost = force_var_cost (data, e1, depends_on);
- cost += force_var_cost (data, e2, depends_on);
- cost += add_cost (Pmode);
- return cost;
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
+
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Estimates cost of expressing difference E1 - E2 as
part is missing. DEPENDS_ON is a set of the invariants the computation
depends on. */
-static unsigned
+static comp_cost
difference_cost (struct ivopts_data *data,
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- unsigned cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
+ aff_tree aff_e1, aff_e2;
+ tree type;
e1 = strip_offset (e1, &off1);
e2 = strip_offset (e2, &off2);
STRIP_NOPS (e2);
if (TREE_CODE (e1) == ADDR_EXPR)
- return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
- depends_on);
+ return ptr_difference_cost (data, e1, e2, symbol_present, var_present,
+ offset, depends_on);
*symbol_present = false;
if (operand_equal_p (e1, e2, 0))
{
*var_present = false;
- return 0;
+ return zero_cost;
}
+
*var_present = true;
+
if (integer_zerop (e2))
return force_var_cost (data, e1, depends_on);
if (integer_zerop (e1))
{
- cost = force_var_cost (data, e2, depends_on);
- cost += multiply_by_cost (-1, mode);
-
+ comp_cost cost = force_var_cost (data, e2, depends_on);
+ cost.cost += multiply_by_cost (-1, mode, data->speed);
return cost;
}
- cost = force_var_cost (data, e1, depends_on);
- cost += force_var_cost (data, e2, depends_on);
- cost += add_cost (mode);
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
- return cost;
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Determines the cost of the computation by that USE is expressed
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
register. A set of invariants we depend on is stored in
- DEPENDS_ON. AT is the statement at that the value is computed. */
+ DEPENDS_ON. AT is the statement at that the value is computed.
+ If CAN_AUTOINC is nonnull, use it to record whether autoinc
+ addressing is likely. */
-static unsigned
+static comp_cost
get_computation_cost_at (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on, tree at)
+ bool address_p, bitmap *depends_on, gimple at,
+ bool *can_autoinc)
{
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
tree utype = TREE_TYPE (ubase), ctype;
unsigned HOST_WIDE_INT cstepi, offset = 0;
HOST_WIDE_INT ratio, aratio;
- bool var_present, symbol_present;
- unsigned cost = 0, n_sums;
+ bool var_present, symbol_present, stmt_is_after_inc;
+ comp_cost cost;
double_int rat;
+ bool speed = optimize_bb_for_speed_p (gimple_bb (at));
*depends_on = NULL;
/* Only consider real candidates. */
if (!cand->iv)
- return INFTY;
+ return infinite_cost;
cbase = cand->iv->base;
cstep = cand->iv->step;
if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
{
/* We do not have a precision to express the values of use. */
- return INFTY;
+ return infinite_cost;
}
if (address_p)
if (use->iv->base_object
&& cand->iv->base_object
&& !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
- return INFTY;
+ return infinite_cost;
}
- if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
cstepi = 0;
if (!constant_multiple_of (ustep, cstep, &rat))
- return INFTY;
-
+ return infinite_cost;
+
if (double_int_fits_in_shwi_p (rat))
ratio = double_int_to_shwi (rat);
else
- return INFTY;
+ return infinite_cost;
+
+ STRIP_NOPS (cbase);
+ ctype = TREE_TYPE (cbase);
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
-
+
ubase - ratio * cbase + ratio * var
-
+
(also holds in the case ratio == -1, TODO. */
if (cst_and_fits_in_hwi (cbase))
{
- offset = - ratio * int_cst_value (cbase);
- cost += difference_cost (data,
- ubase, integer_zero_node,
- &symbol_present, &var_present, &offset,
- depends_on);
+ offset = - ratio * int_cst_value (cbase);
+ cost = difference_cost (data,
+ ubase, build_int_cst (utype, 0),
+ &symbol_present, &var_present, &offset,
+ depends_on);
}
else if (ratio == 1)
{
- cost += difference_cost (data,
- ubase, cbase,
- &symbol_present, &var_present, &offset,
- depends_on);
+ cost = difference_cost (data,
+ ubase, cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
+ }
+ else if (address_p
+ && !POINTER_TYPE_P (ctype)
+ && multiplier_allowed_in_address_p
+ (ratio, TYPE_MODE (TREE_TYPE (utype)),
+ TYPE_ADDR_SPACE (TREE_TYPE (utype))))
+ {
+ cbase
+ = fold_build2 (MULT_EXPR, ctype, cbase, build_int_cst (ctype, ratio));
+ cost = difference_cost (data,
+ ubase, cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
}
else
{
- cost += force_var_cost (data, cbase, depends_on);
- cost += add_cost (TYPE_MODE (ctype));
- cost += difference_cost (data,
- ubase, integer_zero_node,
- &symbol_present, &var_present, &offset,
- depends_on);
+ cost = force_var_cost (data, cbase, depends_on);
+ cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
+ cost = add_costs (cost,
+ difference_cost (data,
+ ubase, build_int_cst (utype, 0),
+ &symbol_present, &var_present,
+ &offset, depends_on));
}
/* If we are after the increment, the value of the candidate is higher by
one iteration. */
- if (stmt_after_increment (data->current_loop, cand, at))
+ stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
+ if (stmt_is_after_inc)
offset -= ratio * cstepi;
/* Now the computation is in shape symbol + var1 + const + ratio * var2.
- (symbol/var/const parts may be omitted). If we are looking for an address,
- find the cost of addressing this. */
+ (symbol/var1/const parts may be omitted). If we are looking for an
+ address, find the cost of addressing this. */
if (address_p)
- return cost + get_address_cost (symbol_present, var_present, offset, ratio,
- TYPE_MODE (TREE_TYPE (*use->op_p)));
+ return add_costs (cost,
+ get_address_cost (symbol_present, var_present,
+ offset, ratio, cstepi,
+ TYPE_MODE (TREE_TYPE (utype)),
+ TYPE_ADDR_SPACE (TREE_TYPE (utype)),
+ speed, stmt_is_after_inc,
+ can_autoinc));
/* Otherwise estimate the costs for computing the expression. */
- aratio = ratio > 0 ? ratio : -ratio;
if (!symbol_present && !var_present && !offset)
{
if (ratio != 1)
- cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
-
+ cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
return cost;
}
- if (aratio != 1)
- cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
+ /* Symbol + offset should be compile-time computable so consider that they
+ are added once to the variable, if present. */
+ if (var_present && (symbol_present || offset))
+ cost.cost += add_cost (TYPE_MODE (ctype), speed)
+ / AVG_LOOP_NITER (data->current_loop);
- n_sums = 1;
- if (var_present
- /* Symbol + offset should be compile-time computable. */
- && (symbol_present || offset))
- n_sums++;
+ /* Having offset does not affect runtime cost in case it is added to
+ symbol, but it increases complexity. */
+ if (offset)
+ cost.complexity++;
+
+ cost.cost += add_cost (TYPE_MODE (ctype), speed);
- return cost + n_sums * add_cost (TYPE_MODE (ctype));
+ aratio = ratio > 0 ? ratio : -ratio;
+ if (aratio != 1)
+ cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
fallback:
+ if (can_autoinc)
+ *can_autoinc = false;
+
{
/* Just get the expression, expand it and measure the cost. */
tree comp = get_computation_at (data->current_loop, use, cand, at);
if (!comp)
- return INFTY;
+ return infinite_cost;
if (address_p)
comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
- return computation_cost (comp);
+ return new_cost (computation_cost (comp, speed), 0);
}
}
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
register. A set of invariants we depend on is stored in
- DEPENDS_ON. */
+ DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
+ autoinc addressing is likely. */
-static unsigned
+static comp_cost
get_computation_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on)
+ bool address_p, bitmap *depends_on, bool *can_autoinc)
{
return get_computation_cost_at (data,
- use, cand, address_p, depends_on, use->stmt);
+ use, cand, address_p, depends_on, use->stmt,
+ can_autoinc);
}
/* Determines cost of basing replacement of USE on CAND in a generic
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost;
+ comp_cost cost;
/* The simple case first -- if we need to express value of the preserved
original biv, the cost is 0. This also prevents us from counting the
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
- set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
+ set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE);
return true;
}
- cost = get_computation_cost (data, use, cand, false, &depends_on);
+ cost = get_computation_cost (data, use, cand, false, &depends_on, NULL);
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
- return cost != INFTY;
+ return !infinite_cost_p (cost);
}
/* Determines cost of basing replacement of USE on CAND in an address. */
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
+ bool can_autoinc;
+ comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on,
+ &can_autoinc);
+ if (cand->ainc_use == use)
+ {
+ if (can_autoinc)
+ cost.cost -= cand->cost_step;
+ /* If we generated the candidate solely for exploiting autoincrement
+ opportunities, and it turns out it can't be used, set the cost to
+ infinity to make sure we ignore it. */
+ else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
+ cost = infinite_cost;
+ }
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
- return cost != INFTY;
+ return !infinite_cost_p (cost);
}
/* Computes value of candidate CAND at position AT in iteration NITER, and
stores it to VAL. */
static void
-cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter,
+cand_value_at (struct loop *loop, struct iv_cand *cand, gimple at, tree niter,
aff_tree *val)
{
aff_tree step, delta, nit;
struct iv *iv = cand->iv;
tree type = TREE_TYPE (iv->base);
+ tree steptype = type;
+ if (POINTER_TYPE_P (type))
+ steptype = sizetype;
- tree_to_aff_combination (iv->step, type, &step);
+ tree_to_aff_combination (iv->step, steptype, &step);
tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
- aff_combination_convert (&nit, type);
+ aff_combination_convert (&nit, steptype);
aff_combination_mult (&nit, &step, &delta);
if (stmt_after_increment (loop, cand, at))
aff_combination_add (&delta, &step);
basic_block ex_bb;
edge exit;
- ex_bb = bb_for_stmt (use->stmt);
+ ex_bb = gimple_bb (use->stmt);
exit = EDGE_SUCC (ex_bb, 0);
if (flow_bb_inside_loop_p (loop, exit->dest))
exit = EDGE_SUCC (ex_bb, 1);
{
basic_block ex_bb;
edge exit;
- tree nit, nit_type;
- tree wider_type, period, per_type;
+ tree nit, period;
struct loop *loop = data->current_loop;
aff_tree bnd;
-
+
if (TREE_CODE (cand->iv->step) != INTEGER_CST)
return false;
- /* For now works only for exits that dominate the loop latch. TODO -- extend
- for other conditions inside loop body. */
- ex_bb = bb_for_stmt (use->stmt);
+ /* For now works only for exits that dominate the loop latch.
+ TODO: extend to other conditions inside loop body. */
+ ex_bb = gimple_bb (use->stmt);
if (use->stmt != last_stmt (ex_bb)
- || TREE_CODE (use->stmt) != COND_EXPR)
- return false;
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
+ || gimple_code (use->stmt) != GIMPLE_COND
+ || !dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
return false;
exit = EDGE_SUCC (ex_bb, 0);
if (!nit)
return false;
- nit_type = TREE_TYPE (nit);
-
- /* Determine whether we may use the variable to test whether niter iterations
- elapsed. This is the case iff the period of the induction variable is
- greater than the number of iterations. */
+ /* Determine whether we can use the variable to test the exit condition.
+ This is the case iff the period of the induction variable is greater
+ than the number of iterations for which the exit condition is true. */
period = iv_period (cand->iv);
- if (!period)
- return false;
- per_type = TREE_TYPE (period);
- wider_type = TREE_TYPE (period);
- if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
- wider_type = per_type;
- else
- wider_type = nit_type;
+ /* If the number of iterations is constant, compare against it directly. */
+ if (TREE_CODE (nit) == INTEGER_CST)
+ {
+ if (!tree_int_cst_lt (nit, period))
+ return false;
+ }
+
+ /* If not, and if this is the only possible exit of the loop, see whether
+ we can get a conservative estimate on the number of iterations of the
+ entire loop and compare against that instead. */
+ else if (loop_only_exit_p (loop, exit))
+ {
+ double_int period_value, max_niter;
+ if (!estimated_loop_iterations (loop, true, &max_niter))
+ return false;
+ period_value = tree_to_double_int (period);
+ if (double_int_ucmp (max_niter, period_value) >= 0)
+ return false;
+ }
- if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
- fold_convert (wider_type, period),
- fold_convert (wider_type, nit))))
+ /* Otherwise, punt. */
+ else
return false;
cand_value_at (loop, cand, use->stmt, nit, &bnd);
+
*bound = aff_combination_to_tree (&bnd);
+ /* It is unlikely that computing the number of iterations using division
+ would be more profitable than keeping the original induction variable. */
+ if (expression_expensive_p (*bound))
+ return false;
return true;
}
tree bound = NULL_TREE;
struct iv *cmp_iv;
bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
- unsigned elim_cost, express_cost, cost;
+ comp_cost elim_cost, express_cost, cost;
bool ok;
+ tree *control_var, *bound_cst;
/* Only consider real candidates. */
if (!cand->iv)
{
- set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
+ set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE);
return false;
}
/* Try iv elimination. */
if (may_eliminate_iv (data, use, cand, &bound))
- elim_cost = force_var_cost (data, bound, &depends_on_elim);
+ {
+ elim_cost = force_var_cost (data, bound, &depends_on_elim);
+ /* The bound is a loop invariant, so it will be only computed
+ once. */
+ elim_cost.cost /= AVG_LOOP_NITER (data->current_loop);
+ }
else
- elim_cost = INFTY;
+ elim_cost = infinite_cost;
/* Try expressing the original giv. If it is compared with an invariant,
note that we cannot get rid of it. */
- ok = extract_cond_operands (data, use->op_p, NULL, NULL, NULL, &cmp_iv);
+ ok = extract_cond_operands (data, use->stmt, &control_var, &bound_cst,
+ NULL, &cmp_iv);
gcc_assert (ok);
+ /* When the condition is a comparison of the candidate IV against
+ zero, prefer this IV.
+
+ TODO: The constant that we're substracting from the cost should
+ be target-dependent. This information should be added to the
+ target costs for each backend. */
+ if (!infinite_cost_p (elim_cost) /* Do not try to decrease infinite! */
+ && integer_zerop (*bound_cst)
+ && (operand_equal_p (*control_var, cand->var_after, 0)
+ || operand_equal_p (*control_var, cand->var_before, 0)))
+ elim_cost.cost -= 1;
+
express_cost = get_computation_cost (data, use, cand, false,
- &depends_on_express);
+ &depends_on_express, NULL);
fd_ivopts_data = data;
walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
- /* Choose the better approach. */
- if (elim_cost < express_cost)
+ /* Choose the better approach, preferring the eliminated IV. */
+ if (compare_costs (elim_cost, express_cost) <= 0)
{
cost = elim_cost;
depends_on = depends_on_elim;
if (depends_on_express)
BITMAP_FREE (depends_on_express);
- return cost != INFTY;
+ return !infinite_cost_p (cost);
}
/* Determines cost of basing replacement of USE on CAND. Returns false
}
}
+/* Return true if get_computation_cost indicates that autoincrement is
+ a possibility for the pair of USE and CAND, false otherwise. */
+
+static bool
+autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use,
+ struct iv_cand *cand)
+{
+ bitmap depends_on;
+ bool can_autoinc;
+ comp_cost cost;
+
+ if (use->type != USE_ADDRESS)
+ return false;
+
+ cost = get_computation_cost (data, use, cand, true, &depends_on,
+ &can_autoinc);
+
+ BITMAP_FREE (depends_on);
+
+ return !infinite_cost_p (cost) && can_autoinc;
+}
+
+/* Examine IP_ORIGINAL candidates to see if they are incremented next to a
+ use that allows autoincrement, and set their AINC_USE if possible. */
+
+static void
+set_autoinc_for_original_candidates (struct ivopts_data *data)
+{
+ unsigned i, j;
+
+ for (i = 0; i < n_iv_cands (data); i++)
+ {
+ struct iv_cand *cand = iv_cand (data, i);
+ struct iv_use *closest = NULL;
+ if (cand->pos != IP_ORIGINAL)
+ continue;
+ for (j = 0; j < n_iv_uses (data); j++)
+ {
+ struct iv_use *use = iv_use (data, j);
+ unsigned uid = gimple_uid (use->stmt);
+ if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at)
+ || uid > gimple_uid (cand->incremented_at))
+ continue;
+ if (closest == NULL || uid > gimple_uid (closest->stmt))
+ closest = use;
+ }
+ if (closest == NULL || !autoinc_possible_for_pair (data, closest, cand))
+ continue;
+ cand->ainc_use = closest;
+ }
+}
+
+/* Finds the candidates for the induction variables. */
+
+static void
+find_iv_candidates (struct ivopts_data *data)
+{
+ /* Add commonly used ivs. */
+ add_standard_iv_candidates (data);
+
+ /* Add old induction variables. */
+ add_old_ivs_candidates (data);
+
+ /* Add induction variables derived from uses. */
+ add_derived_ivs_candidates (data);
+
+ set_autoinc_for_original_candidates (data);
+
+ /* Record the important candidates. */
+ record_important_candidates (data);
+}
+
/* Determines costs of basing the use of the iv on an iv candidate. */
static void
use = iv_use (data, i);
fprintf (dump_file, "Use %d:\n", i);
- fprintf (dump_file, " cand\tcost\tdepends on\n");
+ fprintf (dump_file, " cand\tcost\tcompl.\tdepends on\n");
for (j = 0; j < use->n_map_members; j++)
{
if (!use->cost_map[j].cand
- || use->cost_map[j].cost == INFTY)
+ || infinite_cost_p (use->cost_map[j].cost))
continue;
- fprintf (dump_file, " %d\t%d\t",
+ fprintf (dump_file, " %d\t%d\t%d\t",
use->cost_map[j].cand->id,
- use->cost_map[j].cost);
+ use->cost_map[j].cost.cost,
+ use->cost_map[j].cost.complexity);
if (use->cost_map[j].depends_on)
bitmap_print (dump_file,
use->cost_map[j].depends_on, "","");
static void
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
- unsigned cost_base, cost_step;
+ comp_cost cost_base;
+ unsigned cost, cost_step;
tree base;
if (!cand->iv)
base = cand->iv->base;
cost_base = force_var_cost (data, base, NULL);
- cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
+ cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
- cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
+ cost = cost_step + cost_base.cost / AVG_LOOP_NITER (current_loop);
+
+ /* Prefer the original ivs unless we may gain something by replacing it.
+ The reason is to make debugging simpler; so this is not relevant for
+ artificial ivs created by other optimization passes. */
+ if (cand->pos != IP_ORIGINAL
+ || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
+ cost++;
- /* Prefer the original iv unless we may gain something by replacing it;
- this is not really relevant for artificial ivs created by other
- passes. */
- if (cand->pos == IP_ORIGINAL
- && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
- cand->cost--;
-
/* Prefer not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
if (cand->pos == IP_END
&& empty_block_p (ip_end_pos (data->current_loop)))
- cand->cost++;
+ cost++;
+
+ cand->cost = cost;
+ cand->cost_step = cost_step;
}
/* Determines costs of computation of the candidates. */
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " %d\t%d\n", i, cand->cost);
}
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n");
}
{
/* We add size to the cost, so that we prefer eliminating ivs
if possible. */
- return size + estimate_reg_pressure_cost (size, data->regs_used);
+ return size + estimate_reg_pressure_cost (size, data->regs_used, data->speed);
}
/* For each size of the induction variable set determine the penalty. */
determine_set_costs (struct ivopts_data *data)
{
unsigned j, n;
- tree phi, op;
+ gimple phi;
+ gimple_stmt_iterator psi;
+ tree op;
struct loop *loop = data->current_loop;
bitmap_iterator bi;
etc.). For now the reserve is a constant 3.
Let I be the number of induction variables.
-
+
-- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
make a lot of ivs without a reason).
-- if A - R < U + I <= A, the cost is I * PRES_COST
{
fprintf (dump_file, "Global costs:\n");
fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
- fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost);
- fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
+ fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost[data->speed]);
+ fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost[data->speed]);
}
n = 0;
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
op = PHI_RESULT (phi);
if (!is_gimple_reg (op))
static bool
cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
{
+ int cmp;
+
if (!a)
return false;
if (!b)
return true;
- if (a->cost < b->cost)
+ cmp = compare_costs (a->cost, b->cost);
+ if (cmp < 0)
return true;
- if (a->cost > b->cost)
+ if (cmp > 0)
return false;
/* In case the costs are the same, prefer the cheaper candidate. */
static void
iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned cost = 0;
-
- cost += ivs->cand_use_cost;
- cost += ivs->cand_cost;
- cost += ivopts_global_cost_for_size (data, ivs->n_regs);
+ comp_cost cost = ivs->cand_use_cost;
+ cost.cost += ivs->cand_cost;
+ cost.cost += ivopts_global_cost_for_size (data, ivs->n_regs);
ivs->cost = cost;
}
iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
}
- ivs->cand_use_cost -= cp->cost;
+ ivs->cand_use_cost = sub_costs (ivs->cand_use_cost, cp->cost);
iv_ca_set_remove_invariants (ivs, cp->depends_on);
iv_ca_recount_cost (data, ivs);
iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
}
- ivs->cand_use_cost += cp->cost;
+ ivs->cand_use_cost = add_costs (ivs->cand_use_cost, cp->cost);
iv_ca_set_add_invariants (ivs, cp->depends_on);
iv_ca_recount_cost (data, ivs);
}
/* Get cost for assignment IVS. */
-static unsigned
+static comp_cost
iv_ca_cost (struct iv_ca *ivs)
{
- return (ivs->bad_uses ? INFTY : ivs->cost);
+ /* This was a conditional expression but it triggered a bug in
+ Sun C 5.5. */
+ if (ivs->bad_uses)
+ return infinite_cost;
+ else
+ return ivs->cost;
}
/* Returns true if all dependences of CP are among invariants in IVS. */
nw->cands = BITMAP_ALLOC (NULL);
nw->n_cands = 0;
nw->n_regs = 0;
- nw->cand_use_cost = 0;
+ nw->cand_use_cost = zero_cost;
nw->cand_cost = 0;
nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
- nw->cost = 0;
+ nw->cost = zero_cost;
return nw;
}
{
const char *pref = " invariants ";
unsigned i;
+ comp_cost cost = iv_ca_cost (ivs);
- fprintf (file, " cost %d\n", iv_ca_cost (ivs));
+ fprintf (file, " cost %d (complexity %d)\n", cost.cost, cost.complexity);
bitmap_print (file, ivs->cands, " candidates ","\n");
for (i = 1; i <= data->max_inv_id; i++)
new set, and store differences in DELTA. Number of induction variables
in the new set is stored to N_IVS. */
-static unsigned
+static comp_cost
iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta,
unsigned *n_ivs)
{
- unsigned i, cost;
+ unsigned i;
+ comp_cost cost;
struct iv_use *use;
struct cost_pair *old_cp, *new_cp;
if (!iv_ca_has_deps (ivs, new_cp))
continue;
-
+
if (!cheaper_cost_pair (new_cp, old_cp))
continue;
/* Try narrowing set IVS by removing CAND. Return the cost of
the new set and store the differences in DELTA. */
-static unsigned
+static comp_cost
iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *cand, struct iv_ca_delta **delta)
{
struct cost_pair *old_cp, *new_cp, *cp;
bitmap_iterator bi;
struct iv_cand *cnd;
- unsigned cost;
+ comp_cost cost;
*delta = NULL;
for (i = 0; i < n_iv_uses (data); i++)
continue;
if (!iv_ca_has_deps (ivs, cp))
continue;
-
+
if (!cheaper_cost_pair (cp, new_cp))
continue;
continue;
if (!iv_ca_has_deps (ivs, cp))
continue;
-
+
if (!cheaper_cost_pair (cp, new_cp))
continue;
if (!new_cp)
{
iv_ca_delta_free (delta);
- return INFTY;
+ return infinite_cost;
}
*delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
from to EXCEPT_CAND from it. Return cost of the new set, and store
differences in DELTA. */
-static unsigned
+static comp_cost
iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_cand *except_cand, struct iv_ca_delta **delta)
{
bitmap_iterator bi;
struct iv_ca_delta *act_delta, *best_delta;
- unsigned i, best_cost, acost;
+ unsigned i;
+ comp_cost best_cost, acost;
struct iv_cand *cand;
best_delta = NULL;
acost = iv_ca_narrow (data, ivs, cand, &act_delta);
- if (acost < best_cost)
+ if (compare_costs (acost, best_cost) < 0)
{
best_cost = acost;
iv_ca_delta_free (&best_delta);
try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use)
{
- unsigned best_cost, act_cost;
+ comp_cost best_cost, act_cost;
unsigned i;
bitmap_iterator bi;
struct iv_cand *cand;
iv_ca_set_no_cp (data, ivs, use);
}
- /* First try important candidates. Only if it fails, try the specific ones.
- Rationale -- in loops with many variables the best choice often is to use
- just one generic biv. If we added here many ivs specific to the uses,
- the optimization algorithm later would be likely to get stuck in a local
- minimum, thus causing us to create too many ivs. The approach from
- few ivs to more seems more likely to be successful -- starting from few
- ivs, replacing an expensive use by a specific iv should always be a
- win. */
+ /* First try important candidates not based on any memory object. Only if
+ this fails, try the specific ones. Rationale -- in loops with many
+ variables the best choice often is to use just one generic biv. If we
+ added here many ivs specific to the uses, the optimization algorithm later
+ would be likely to get stuck in a local minimum, thus causing us to create
+ too many ivs. The approach from few ivs to more seems more likely to be
+ successful -- starting from few ivs, replacing an expensive use by a
+ specific iv should always be a win. */
EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
{
cand = iv_cand (data, i);
+ if (cand->iv->base_object != NULL_TREE)
+ continue;
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
iv_ca_set_no_cp (data, ivs, use);
act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
- if (act_cost < best_cost)
+ if (compare_costs (act_cost, best_cost) < 0)
{
best_cost = act_cost;
iv_ca_delta_free (&act_delta);
}
- if (best_cost == INFTY)
+ if (infinite_cost_p (best_cost))
{
for (i = 0; i < use->n_map_members; i++)
{
continue;
/* Already tried this. */
- if (cand->important)
+ if (cand->important && cand->iv->base_object == NULL_TREE)
continue;
-
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
cp, act_delta);
- if (act_cost < best_cost)
+ if (compare_costs (act_cost, best_cost) < 0)
{
best_cost = act_cost;
iv_ca_delta_commit (data, ivs, best_delta, true);
iv_ca_delta_free (&best_delta);
- return (best_cost != INFTY);
+ return !infinite_cost_p (best_cost);
}
/* Finds an initial assignment of candidates to uses. */
static bool
try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
{
- unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
+ unsigned i, n_ivs;
+ comp_cost acost, best_cost = iv_ca_cost (ivs);
struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
struct iv_cand *cand;
for (i = 0; i < n_iv_cands (data); i++)
{
cand = iv_cand (data, i);
-
+
if (iv_ca_cand_used_p (ivs, cand))
continue;
act_delta = iv_ca_delta_join (act_delta, tmp_delta);
}
- if (acost < best_cost)
+ if (compare_costs (acost, best_cost) < 0)
{
best_cost = acost;
iv_ca_delta_free (&best_delta);
}
iv_ca_delta_commit (data, ivs, best_delta, true);
- gcc_assert (best_cost == iv_ca_cost (ivs));
+ gcc_assert (compare_costs (best_cost, iv_ca_cost (ivs)) == 0);
iv_ca_delta_free (&best_delta);
return true;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
+ {
+ comp_cost cost = iv_ca_cost (set);
+ fprintf (dump_file, "Final cost %d (complexity %d)\n\n", cost.cost, cost.complexity);
+ }
for (i = 0; i < n_iv_uses (data); i++)
{
static void
create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
{
- block_stmt_iterator incr_pos;
+ gimple_stmt_iterator incr_pos;
tree base;
bool after = false;
switch (cand->pos)
{
case IP_NORMAL:
- incr_pos = bsi_last (ip_normal_pos (data->current_loop));
+ incr_pos = gsi_last_bb (ip_normal_pos (data->current_loop));
break;
case IP_END:
- incr_pos = bsi_last (ip_end_pos (data->current_loop));
+ incr_pos = gsi_last_bb (ip_end_pos (data->current_loop));
+ after = true;
+ break;
+
+ case IP_AFTER_USE:
after = true;
+ /* fall through */
+ case IP_BEFORE_USE:
+ incr_pos = gsi_for_stmt (cand->incremented_at);
break;
case IP_ORIGINAL:
/* Rewrite the increment so that it uses var_before directly. */
find_interesting_uses_op (data, cand->var_after)->selected = cand;
-
+
return;
}
-
+
gimple_add_tmp_var (cand->var_before);
add_referenced_var (cand->var_before);
}
}
-/* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
- is true, remove also the ssa name defined by the statement. */
-
-static void
-remove_statement (tree stmt, bool including_defined_name)
-{
- if (TREE_CODE (stmt) == PHI_NODE)
- {
- remove_phi_node (stmt, NULL_TREE, including_defined_name);
- }
- else
- {
- block_stmt_iterator bsi = bsi_for_stmt (stmt);
-
- bsi_remove (&bsi, true);
- release_defs (stmt);
- }
-}
/* Rewrites USE (definition of iv used in a nonlinear expression)
using candidate CAND. */
struct iv_use *use, struct iv_cand *cand)
{
tree comp;
- tree op, tgt, ass;
- block_stmt_iterator bsi;
+ tree op, tgt;
+ gimple ass;
+ gimple_stmt_iterator bsi;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
&& cand->incremented_at == use->stmt)
{
tree step, ctype, utype;
- enum tree_code incr_code = PLUS_EXPR;
+ enum tree_code incr_code = PLUS_EXPR, old_code;
- gcc_assert (TREE_CODE (use->stmt) == GIMPLE_MODIFY_STMT);
- gcc_assert (GIMPLE_STMT_OPERAND (use->stmt, 0) == cand->var_after);
+ gcc_assert (is_gimple_assign (use->stmt));
+ gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
step = cand->iv->step;
ctype = TREE_TYPE (step);
computations in the loop -- otherwise, the computation
we rely upon may be removed in remove_unused_ivs,
thus leading to ICE. */
- op = GIMPLE_STMT_OPERAND (use->stmt, 1);
- if (TREE_CODE (op) == PLUS_EXPR
- || TREE_CODE (op) == MINUS_EXPR
- || TREE_CODE (op) == POINTER_PLUS_EXPR)
+ old_code = gimple_assign_rhs_code (use->stmt);
+ if (old_code == PLUS_EXPR
+ || old_code == MINUS_EXPR
+ || old_code == POINTER_PLUS_EXPR)
{
- if (TREE_OPERAND (op, 0) == cand->var_before)
- op = TREE_OPERAND (op, 1);
- else if (TREE_CODE (op) != MINUS_EXPR
- && TREE_OPERAND (op, 1) == cand->var_before)
- op = TREE_OPERAND (op, 0);
+ if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs2 (use->stmt);
+ else if (old_code != MINUS_EXPR
+ && gimple_assign_rhs2 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs1 (use->stmt);
else
op = NULL_TREE;
}
gcc_assert (comp != NULL_TREE);
}
- switch (TREE_CODE (use->stmt))
+ switch (gimple_code (use->stmt))
{
- case PHI_NODE:
+ case GIMPLE_PHI:
tgt = PHI_RESULT (use->stmt);
/* If we should keep the biv, do not replace it. */
if (name_info (data, tgt)->preserve_biv)
return;
- bsi = bsi_after_labels (bb_for_stmt (use->stmt));
+ bsi = gsi_after_labels (gimple_bb (use->stmt));
break;
- case GIMPLE_MODIFY_STMT:
- tgt = GIMPLE_STMT_OPERAND (use->stmt, 0);
- bsi = bsi_for_stmt (use->stmt);
+ case GIMPLE_ASSIGN:
+ tgt = gimple_assign_lhs (use->stmt);
+ bsi = gsi_for_stmt (use->stmt);
break;
default:
gcc_unreachable ();
}
- op = force_gimple_operand_bsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
- true, BSI_SAME_STMT);
+ op = force_gimple_operand_gsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
+ true, GSI_SAME_STMT);
- if (TREE_CODE (use->stmt) == PHI_NODE)
+ if (gimple_code (use->stmt) == GIMPLE_PHI)
{
- ass = build_gimple_modify_stmt (tgt, op);
- bsi_insert_before (&bsi, ass, BSI_SAME_STMT);
- remove_statement (use->stmt, false);
- SSA_NAME_DEF_STMT (tgt) = ass;
+ ass = gimple_build_assign (tgt, op);
+ gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
+
+ bsi = gsi_for_stmt (use->stmt);
+ remove_phi_node (&bsi, false);
}
else
- GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
+ {
+ gimple_assign_set_rhs_from_tree (&bsi, op);
+ use->stmt = gsi_stmt (bsi);
+ }
}
/* Replaces ssa name in index IDX by its basic variable. Callback for
if (TREE_CODE (*idx) == SSA_NAME)
*idx = SSA_NAME_VAR (*idx);
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
op = &TREE_OPERAND (base, 2);
if (*op
return ref;
}
-/* Extract the alias analysis info for the memory reference REF. There are
- several ways how this information may be stored and what precisely is
- its semantics depending on the type of the reference, but there always is
- somewhere hidden one _DECL node that is used to determine the set of
- virtual operands for the reference. The code below deciphers this jungle
- and extracts this single useful piece of information. */
-
-static tree
-get_ref_tag (tree ref, tree orig)
-{
- tree var = get_base_address (ref);
- tree aref = NULL_TREE, tag, sv;
- HOST_WIDE_INT offset, size, maxsize;
-
- for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
- {
- aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
- if (ref)
- break;
- }
-
- if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
- return unshare_expr (sv);
-
- if (!var)
- return NULL_TREE;
-
- if (TREE_CODE (var) == INDIRECT_REF)
- {
- /* If the base is a dereference of a pointer, first check its name memory
- tag. If it does not have one, use its symbol memory tag. */
- var = TREE_OPERAND (var, 0);
- if (TREE_CODE (var) != SSA_NAME)
- return NULL_TREE;
-
- if (SSA_NAME_PTR_INFO (var))
- {
- tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
- if (tag)
- return tag;
- }
-
- var = SSA_NAME_VAR (var);
- tag = symbol_mem_tag (var);
- gcc_assert (tag != NULL_TREE);
- return tag;
- }
- else
- {
- if (!DECL_P (var))
- return NULL_TREE;
-
- tag = symbol_mem_tag (var);
- if (tag)
- return tag;
-
- return var;
- }
-}
-
/* Copies the reference information from OLD_REF to NEW_REF. */
static void
else
{
TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
- TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
+ TREE_SIDE_EFFECTS (new_ref) = TREE_SIDE_EFFECTS (old_ref);
+ TREE_THIS_VOLATILE (new_ref) = TREE_THIS_VOLATILE (old_ref);
}
}
struct iv_use *use, struct iv_cand *cand)
{
aff_tree aff;
- block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+ tree base_hint = NULL_TREE;
tree ref;
bool ok;
gcc_assert (ok);
unshare_aff_combination (&aff);
- ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
+ /* To avoid undefined overflow problems, all IV candidates use unsigned
+ integer types. The drawback is that this makes it impossible for
+ create_mem_ref to distinguish an IV that is based on a memory object
+ from one that represents simply an offset.
+
+ To work around this problem, we pass a hint to create_mem_ref that
+ indicates which variable (if any) in aff is an IV based on a memory
+ object. Note that we only consider the candidate. If this is not
+ based on an object, the base of the reference is in some subexpression
+ of the use -- but these will use pointer types, so they are recognized
+ by the create_mem_ref heuristics anyway. */
+ if (cand->iv->base_object)
+ base_hint = var_at_stmt (data->current_loop, cand, use->stmt);
+
+ ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, base_hint,
+ data->speed);
copy_ref_info (ref, *use->op_p);
*use->op_p = ref;
}
struct iv_use *use, struct iv_cand *cand)
{
tree comp, *var_p, op, bound;
- block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
+ gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
enum tree_code compare;
struct cost_pair *cp = get_use_iv_cost (data, use, cand);
bool ok;
{
tree var = var_at_stmt (data->current_loop, cand, use->stmt);
tree var_type = TREE_TYPE (var);
+ gimple_seq stmts;
compare = iv_elimination_compare (data, use);
bound = unshare_expr (fold_convert (var_type, bound));
- op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE,
- true, BSI_SAME_STMT);
-
- *use->op_p = build2 (compare, boolean_type_node, var, op);
+ op = force_gimple_operand (bound, &stmts, true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (
+ loop_preheader_edge (data->current_loop),
+ stmts);
+
+ gimple_cond_set_lhs (use->stmt, var);
+ gimple_cond_set_code (use->stmt, compare);
+ gimple_cond_set_rhs (use->stmt, op);
return;
}
comp = get_computation (data->current_loop, use, cand);
gcc_assert (comp != NULL_TREE);
- ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
+ ok = extract_cond_operands (data, use->stmt, &var_p, NULL, NULL, NULL);
gcc_assert (ok);
- *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
- true, BSI_SAME_STMT);
+ *var_p = force_gimple_operand_gsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
+ true, GSI_SAME_STMT);
}
/* Rewrites USE using candidate CAND. */
static void
rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
{
- push_stmt_changes (&use->stmt);
-
switch (use->type)
{
case USE_NONLINEAR_EXPR:
gcc_unreachable ();
}
- pop_stmt_changes (&use->stmt);
+ update_stmt (use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
{
unsigned j;
bitmap_iterator bi;
+ bitmap toremove = BITMAP_ALLOC (NULL);
+ /* Figure out an order in which to release SSA DEFs so that we don't
+ release something that we'd have to propagate into a debug stmt
+ afterwards. */
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
{
struct version_info *info;
&& !info->inv_id
&& !info->iv->have_use_for
&& !info->preserve_biv)
- remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
+ bitmap_set_bit (toremove, SSA_NAME_VERSION (info->iv->ssa_name));
}
+
+ release_defs_bitset (toremove);
+
+ BITMAP_FREE (toremove);
}
/* Frees data allocated by the optimization of a single loop. */
bool changed = false;
struct iv_ca *iv_ca;
edge exit;
+ basic_block *body;
gcc_assert (!data->niters);
data->current_loop = loop;
+ data->speed = optimize_loop_for_speed_p (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Processing loop %d\n", loop->num);
-
+
exit = single_dom_exit (loop);
if (exit)
{
fprintf (dump_file, " single exit %d -> %d, exit condition ",
exit->src->index, exit->dest->index);
- print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
+ print_gimple_stmt (dump_file, last_stmt (exit->src), 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
fprintf (dump_file, "\n");
}
+ body = get_loop_body (loop);
+ renumber_gimple_stmt_uids_in_blocks (body, loop->num_nodes);
+ free (body);
+
/* For each ssa name determines whether it behaves as an induction variable
in some loop. */
if (!find_induction_variables (data))
find_iv_candidates (data);
/* Calculates the costs (item 3, part 1). */
- determine_use_iv_costs (data);
determine_iv_costs (data);
+ determine_use_iv_costs (data);
determine_set_costs (data);
/* Find the optimal set of induction variables (item 3, part 2). */
/* Create the new induction variables (item 4, part 1). */
create_new_ivs (data, iv_ca);
iv_ca_free (&iv_ca);
-
+
/* Rewrite the uses (item 4, part 2). */
rewrite_uses (data);
OSDN Git Service
