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 later
+ 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
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/>. */
#include "config.h"
#include "system.h"
VEC(tree,heap) *);
/* Lattice stuff that is internal to the code generation algorithm. */
-typedef struct
+typedef struct lambda_lattice_s
{
/* Lattice base matrix. */
lambda_matrix base;
{
lambda_body_vector ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = GGC_NEW (struct lambda_body_vector_s);
LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
LBV_SIZE (ret) = size;
LBV_DENOMINATOR (ret) = 1;
{
lambda_linear_expression ret;
- ret = ggc_alloc_cleared (sizeof (*ret));
+ ret = GGC_CNEW (struct lambda_linear_expression_s);
LLE_COEFFICIENTS (ret) = lambda_vector_new (dim);
LLE_CONSTANT (ret) = 0;
lambda_loopnest_new (int depth, int invariants)
{
lambda_loopnest ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = GGC_NEW (struct lambda_loopnest_s);
- LN_LOOPS (ret) = ggc_alloc_cleared (depth * sizeof (lambda_loop));
+ LN_LOOPS (ret) = GGC_CNEWVEC (lambda_loop, depth);
LN_DEPTH (ret) = depth;
LN_INVARIANTS (ret) = invariants;
lambda_lattice_new (int depth, int invariants)
{
lambda_lattice ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = GGC_NEW (struct lambda_lattice_s);
LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
{
if (is_gimple_min_invariant (op))
return true;
- if (loop->depth == 0)
+ if (loop_depth (loop) == 0)
return true;
if (!expr_invariant_in_loop_p (loop, op))
return false;
- if (loop->outer
- && !invariant_in_loop_and_outer_loops (loop->outer, op))
+ if (!invariant_in_loop_and_outer_loops (loop_outer (loop), op))
return false;
return true;
}
tree type, VEC(tree,heap) *induction_vars,
tree *stmts_to_insert)
{
- tree stmts, stmt, resvar, name;
- tree iv;
- size_t i;
- tree_stmt_iterator tsi;
+ int k;
+ tree resvar;
+ tree expr = build_linear_expr (type, LBV_COEFFICIENTS (lbv), induction_vars);
+
+ k = LBV_DENOMINATOR (lbv);
+ gcc_assert (k != 0);
+ if (k != 1)
+ expr = fold_build2 (CEIL_DIV_EXPR, type, expr, build_int_cst (type, k));
- /* Create a statement list and a linear expression temporary. */
- stmts = alloc_stmt_list ();
resvar = create_tmp_var (type, "lbvtmp");
add_referenced_var (resvar);
-
- /* Start at 0. */
- stmt = build_gimple_modify_stmt (resvar,
- fold_convert (type, integer_zero_node));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
- {
- if (LBV_COEFFICIENTS (lbv)[i] != 0)
- {
- tree newname;
- tree coeffmult;
-
- /* newname = coefficient * induction_variable */
- coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
- stmt = build_gimple_modify_stmt (resvar,
- fold_build2 (MULT_EXPR, type,
- iv, coeffmult));
-
- newname = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = newname;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* name = name + newname */
- stmt = build_gimple_modify_stmt (resvar,
- build2 (PLUS_EXPR, type,
- name, newname));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- }
- }
-
- /* Handle any denominator that occurs. */
- if (LBV_DENOMINATOR (lbv) != 1)
- {
- tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
- stmt = build_gimple_modify_stmt (resvar,
- build2 (CEIL_DIV_EXPR, type,
- name, denominator));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
- *stmts_to_insert = stmts;
- return name;
+ return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
}
/* Convert a linear expression from coefficient and constant form to a
VEC(tree,heap) *invariants,
enum tree_code wrap, tree *stmts_to_insert)
{
- tree stmts, stmt, resvar, name;
- size_t i;
- tree_stmt_iterator tsi;
- tree iv, invar;
+ int k;
+ tree resvar;
+ tree expr = NULL_TREE;
VEC(tree,heap) *results = NULL;
gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR);
- name = NULL_TREE;
- /* Create a statement list and a linear expression temporary. */
- stmts = alloc_stmt_list ();
- resvar = create_tmp_var (type, "lletmp");
- add_referenced_var (resvar);
- /* Build up the linear expressions, and put the variable representing the
- result in the results array. */
+ /* Build up the linear expressions. */
for (; lle != NULL; lle = LLE_NEXT (lle))
{
- /* Start at name = 0. */
- stmt = build_gimple_modify_stmt (resvar,
- fold_convert (type, integer_zero_node));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* First do the induction variables.
- at the end, name = name + all the induction variables added
- together. */
- for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
- {
- if (LLE_COEFFICIENTS (lle)[i] != 0)
- {
- tree newname;
- tree mult;
- tree coeff;
+ expr = build_linear_expr (type, LLE_COEFFICIENTS (lle), induction_vars);
+ expr = fold_build2 (PLUS_EXPR, type, expr,
+ build_linear_expr (type,
+ LLE_INVARIANT_COEFFICIENTS (lle),
+ invariants));
+
+ k = LLE_CONSTANT (lle);
+ if (k)
+ expr = fold_build2 (PLUS_EXPR, type, expr, build_int_cst (type, k));
+
+ k = LLE_CONSTANT (offset);
+ if (k)
+ expr = fold_build2 (PLUS_EXPR, type, expr, build_int_cst (type, k));
+
+ k = LLE_DENOMINATOR (lle);
+ if (k != 1)
+ expr = fold_build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
+ type, expr, build_int_cst (type, k));
+
+ expr = fold (expr);
+ VEC_safe_push (tree, heap, results, expr);
+ }
- /* mult = induction variable * coefficient. */
- if (LLE_COEFFICIENTS (lle)[i] == 1)
- {
- mult = VEC_index (tree, induction_vars, i);
- }
- else
- {
- coeff = build_int_cst (type,
- LLE_COEFFICIENTS (lle)[i]);
- mult = fold_build2 (MULT_EXPR, type, iv, coeff);
- }
+ gcc_assert (expr);
- /* newname = mult */
- stmt = build_gimple_modify_stmt (resvar, mult);
- newname = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = newname;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* name = name + newname */
- stmt = build_gimple_modify_stmt (resvar,
- build2 (PLUS_EXPR, type,
- name, newname));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
- }
+ /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */
+ if (VEC_length (tree, results) > 1)
+ {
+ size_t i;
+ tree op;
- /* Handle our invariants.
- At the end, we have name = name + result of adding all multiplied
- invariants. */
- for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
- {
- if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
- {
- tree newname;
- tree mult;
- tree coeff;
- int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
- /* mult = invariant * coefficient */
- if (invcoeff == 1)
- {
- mult = invar;
- }
- else
- {
- coeff = build_int_cst (type, invcoeff);
- mult = fold_build2 (MULT_EXPR, type, invar, coeff);
- }
+ expr = VEC_index (tree, results, 0);
+ for (i = 1; VEC_iterate (tree, results, i, op); i++)
+ expr = fold_build2 (wrap, type, expr, op);
+ }
- /* newname = mult */
- stmt = build_gimple_modify_stmt (resvar, mult);
- newname = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = newname;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* name = name + newname */
- stmt = build_gimple_modify_stmt (resvar,
- build2 (PLUS_EXPR, type,
- name, newname));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
- }
+ VEC_free (tree, heap, results);
- /* Now handle the constant.
- name = name + constant. */
- if (LLE_CONSTANT (lle) != 0)
- {
- tree incr = build_int_cst (type, LLE_CONSTANT (lle));
- stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
- name, incr));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
+ resvar = create_tmp_var (type, "lletmp");
+ add_referenced_var (resvar);
+ return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
+}
- /* Now handle the offset.
- name = name + linear offset. */
- if (LLE_CONSTANT (offset) != 0)
- {
- tree incr = build_int_cst (type, LLE_CONSTANT (offset));
- stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
- name, incr));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
+/* Remove the induction variable defined at IV_STMT. */
+
+static void
+remove_iv (tree iv_stmt)
+{
+ if (TREE_CODE (iv_stmt) == PHI_NODE)
+ {
+ int i;
- /* Handle any denominator that occurs. */
- if (LLE_DENOMINATOR (lle) != 1)
+ for (i = 0; i < PHI_NUM_ARGS (iv_stmt); i++)
{
- stmt = build_int_cst (type, LLE_DENOMINATOR (lle));
- stmt = build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
- type, name, stmt);
- stmt = build_gimple_modify_stmt (resvar, stmt);
-
- /* name = {ceil, floor}(name/denominator) */
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ tree stmt;
+ imm_use_iterator imm_iter;
+ tree arg = PHI_ARG_DEF (iv_stmt, i);
+ bool used = false;
+
+ if (TREE_CODE (arg) != SSA_NAME)
+ continue;
+
+ FOR_EACH_IMM_USE_STMT (stmt, imm_iter, arg)
+ if (stmt != iv_stmt)
+ used = true;
+
+ if (!used)
+ remove_iv (SSA_NAME_DEF_STMT (arg));
}
- VEC_safe_push (tree, heap, results, name);
- }
- /* Again, out of laziness, we don't handle this case yet. It's not
- hard, it just hasn't occurred. */
- gcc_assert (VEC_length (tree, results) <= 2);
-
- /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */
- if (VEC_length (tree, results) > 1)
- {
- tree op1 = VEC_index (tree, results, 0);
- tree op2 = VEC_index (tree, results, 1);
- stmt = build_gimple_modify_stmt (resvar, build2 (wrap, type, op1, op2));
- name = make_ssa_name (resvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = name;
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ remove_phi_node (iv_stmt, NULL_TREE, true);
}
+ else
+ {
+ block_stmt_iterator bsi = bsi_for_stmt (iv_stmt);
- VEC_free (tree, heap, results);
-
- *stmts_to_insert = stmts;
- return name;
+ bsi_remove (&bsi, true);
+ release_defs (iv_stmt);
+ }
}
+
/* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
it, back into gcc code. This changes the
loops, their induction variables, and their bodies, so that they
type,
new_ivs,
invariants, MAX_EXPR, &stmts);
- bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
- bsi_commit_edge_inserts ();
+
+ if (stmts)
+ {
+ bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
+ bsi_commit_edge_inserts ();
+ }
/* Build the new upper bound and insert its statements in the
basic block of the exit condition */
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
exit = single_exit (temp);
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
- bsi = bsi_start (bb);
- bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
+ bsi = bsi_after_labels (bb);
+ if (stmts)
+ bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
/* Create the new iv. */
newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
new_ivs, &stmts);
- bsi = bsi_for_stmt (stmt);
- /* Insert the statements to build that
- expression. */
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ if (stmts)
+ {
+ bsi = bsi_for_stmt (stmt);
+ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ }
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
propagate_value (use_p, newiv);
update_stmt (stmt);
}
+
+ /* Remove the now unused induction variable. */
+ remove_iv (oldiv_stmt);
}
VEC_free (tree, heap, new_ivs);
}
temporaries. */
in.hash = htab_hash_pointer (use);
in.base.from = use;
- h = htab_find_with_hash (replacements, &in, in.hash);
+ h = (struct tree_map *) htab_find_with_hash (replacements, &in, in.hash);
if (h != NULL)
{
SET_USE (use_p, h->to);
which sets Y. */
var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
add_referenced_var (var);
- val = force_gimple_operand_bsi (firstbsi, val, false, NULL);
+ val = force_gimple_operand_bsi (firstbsi, val, false, NULL,
+ true, BSI_SAME_STMT);
setstmt = build_gimple_modify_stmt (var, val);
var = make_ssa_name (var, setstmt);
GIMPLE_STMT_OPERAND (setstmt, 0) = var;
bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
update_stmt (setstmt);
SET_USE (use_p, var);
- h = ggc_alloc (sizeof (struct tree_map));
+ h = GGC_NEW (struct tree_map);
h->hash = in.hash;
h->base.from = use;
h->to = var;
{
tree arg_stmt = SSA_NAME_DEF_STMT (arg);
- if (bb_for_stmt (arg_stmt)->loop_father
- == loop->inner)
+ if (bb_for_stmt (arg_stmt)
+ && (bb_for_stmt (arg_stmt)->loop_father
+ == loop->inner))
goto fail;
}
}
{
basic_block *bbs;
tree exit_condition;
- tree then_label, else_label, cond_stmt;
+ tree cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
int i;
block_stmt_iterator bsi, firstbsi;
bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
make_edge (headerbb, bodybb, EDGE_FALLTHRU);
- then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (latchbb));
- else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (olddest));
cond_stmt = build3 (COND_EXPR, void_type_node,
build2 (NE_EXPR, boolean_type_node,
integer_one_node,
integer_zero_node),
- then_label, else_label);
+ NULL_TREE, NULL_TREE);
bsi = bsi_start (bodybb);
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
set_immediate_dominator (CDI_DOMINATORS, preheaderbb,
single_exit (loop)->src);
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
- set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
+ set_immediate_dominator (CDI_DOMINATORS, olddest,
+ recompute_dominator (CDI_DOMINATORS, olddest));
/* Create the new iv. */
oldivvar = VEC_index (tree, loopivs, 0);
ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
OSDN Git Service
