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"
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
+#include "obstack.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.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;
static bool lle_equal (lambda_linear_expression, lambda_linear_expression,
int, int);
-static lambda_lattice lambda_lattice_new (int, int);
-static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
+static lambda_lattice lambda_lattice_new (int, int, struct obstack *);
+static lambda_lattice lambda_lattice_compute_base (lambda_loopnest,
+ struct obstack *);
static tree find_induction_var_from_exit_cond (struct loop *);
static bool can_convert_to_perfect_nest (struct loop *);
/* Create a new lambda body vector. */
lambda_body_vector
-lambda_body_vector_new (int size)
+lambda_body_vector_new (int size, struct obstack * lambda_obstack)
{
lambda_body_vector ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = (lambda_body_vector)obstack_alloc (lambda_obstack, sizeof (*ret));
LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
LBV_SIZE (ret) = size;
LBV_DENOMINATOR (ret) = 1;
lambda_body_vector
lambda_body_vector_compute_new (lambda_trans_matrix transform,
- lambda_body_vector vect)
+ lambda_body_vector vect,
+ struct obstack * lambda_obstack)
{
lambda_body_vector temp;
int depth;
depth = LTM_ROWSIZE (transform);
- temp = lambda_body_vector_new (depth);
+ temp = lambda_body_vector_new (depth, lambda_obstack);
LBV_DENOMINATOR (temp) =
LBV_DENOMINATOR (vect) * LTM_DENOMINATOR (transform);
lambda_vector_matrix_mult (LBV_COEFFICIENTS (vect), depth,
of invariants INVARIANTS. */
lambda_linear_expression
-lambda_linear_expression_new (int dim, int invariants)
+lambda_linear_expression_new (int dim, int invariants,
+ struct obstack * lambda_obstack)
{
lambda_linear_expression ret;
- ret = ggc_alloc_cleared (sizeof (*ret));
-
+ ret = (lambda_linear_expression)obstack_alloc (lambda_obstack,
+ sizeof (*ret));
LLE_COEFFICIENTS (ret) = lambda_vector_new (dim);
LLE_CONSTANT (ret) = 0;
LLE_INVARIANT_COEFFICIENTS (ret) = lambda_vector_new (invariants);
number of invariants. */
lambda_loopnest
-lambda_loopnest_new (int depth, int invariants)
+lambda_loopnest_new (int depth, int invariants,
+ struct obstack * lambda_obstack)
{
lambda_loopnest ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = (lambda_loopnest)obstack_alloc (lambda_obstack, sizeof (*ret));
- LN_LOOPS (ret) = ggc_alloc_cleared (depth * sizeof (lambda_loop));
+ LN_LOOPS (ret) = (lambda_loop *)
+ obstack_alloc (lambda_obstack, depth * sizeof(LN_LOOPS(ret)));
LN_DEPTH (ret) = depth;
LN_INVARIANTS (ret) = invariants;
of invariants. */
static lambda_lattice
-lambda_lattice_new (int depth, int invariants)
+lambda_lattice_new (int depth, int invariants, struct obstack * lambda_obstack)
{
- lambda_lattice ret;
- ret = ggc_alloc (sizeof (*ret));
+ lambda_lattice ret
+ = (lambda_lattice)obstack_alloc (lambda_obstack, sizeof (*ret));
LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
identity matrix) if NEST is a sparse space. */
static lambda_lattice
-lambda_lattice_compute_base (lambda_loopnest nest)
+lambda_lattice_compute_base (lambda_loopnest nest,
+ struct obstack * lambda_obstack)
{
lambda_lattice ret;
int depth, invariants;
depth = LN_DEPTH (nest);
invariants = LN_INVARIANTS (nest);
- ret = lambda_lattice_new (depth, invariants);
+ ret = lambda_lattice_new (depth, invariants, lambda_obstack);
base = LATTICE_BASE (ret);
for (i = 0; i < depth; i++)
{
int invariants,
lambda_matrix A,
lambda_matrix B,
- lambda_vector a)
+ lambda_vector a,
+ struct obstack * lambda_obstack)
{
int multiple, f1, f2;
B1 = lambda_matrix_new (128, invariants);
a1 = lambda_vector_new (128);
- auxillary_nest = lambda_loopnest_new (depth, invariants);
+ auxillary_nest = lambda_loopnest_new (depth, invariants, lambda_obstack);
for (i = depth - 1; i >= 0; i--)
{
{
/* Any linear expression in the matrix with a coefficient less
than 0 becomes part of the new lower bound. */
- expression = lambda_linear_expression_new (depth, invariants);
+ expression = lambda_linear_expression_new (depth, invariants,
+ lambda_obstack);
for (k = 0; k < i; k++)
LLE_COEFFICIENTS (expression)[k] = A[j][k];
{
/* Any linear expression with a coefficient greater than 0
becomes part of the new upper bound. */
- expression = lambda_linear_expression_new (depth, invariants);
+ expression = lambda_linear_expression_new (depth, invariants,
+ lambda_obstack);
for (k = 0; k < i; k++)
LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k];
static lambda_loopnest
lambda_compute_auxillary_space (lambda_loopnest nest,
- lambda_trans_matrix trans)
+ lambda_trans_matrix trans,
+ struct obstack * lambda_obstack)
{
lambda_matrix A, B, A1, B1;
lambda_vector a, a1;
/* Compute the lattice base x = base * y + origin, where y is the
base space. */
- lattice = lambda_lattice_compute_base (nest);
+ lattice = lambda_lattice_compute_base (nest, lambda_obstack);
/* Ax <= a + B then becomes ALy <= a+B - A*origin. L is the lattice base */
lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
return compute_nest_using_fourier_motzkin (size, depth, invariants,
- A, B1, a1);
+ A, B1, a1, lambda_obstack);
}
/* Compute the loop bounds for the target space, using the bounds of
static lambda_loopnest
lambda_compute_target_space (lambda_loopnest auxillary_nest,
- lambda_trans_matrix H, lambda_vector stepsigns)
+ lambda_trans_matrix H, lambda_vector stepsigns,
+ struct obstack * lambda_obstack)
{
lambda_matrix inverse, H1;
int determinant, i, j;
target = lambda_matrix_new (depth, depth);
lambda_matrix_mult (H1, inverse, target, depth, depth, depth);
- target_nest = lambda_loopnest_new (depth, invariants);
+ target_nest = lambda_loopnest_new (depth, invariants, lambda_obstack);
for (i = 0; i < depth; i++)
{
for (j = 0; j < i; j++)
target[i][j] = target[i][j] / gcd1;
- expression = lambda_linear_expression_new (depth, invariants);
+ expression = lambda_linear_expression_new (depth, invariants,
+ lambda_obstack);
lambda_vector_copy (target[i], LLE_COEFFICIENTS (expression), depth);
LLE_DENOMINATOR (expression) = determinant / gcd1;
LLE_CONSTANT (expression) = 0;
for (; auxillary_expr != NULL;
auxillary_expr = LLE_NEXT (auxillary_expr))
{
- target_expr = lambda_linear_expression_new (depth, invariants);
+ target_expr = lambda_linear_expression_new (depth, invariants,
+ lambda_obstack);
lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
depth, inverse, depth,
LLE_COEFFICIENTS (target_expr));
for (; auxillary_expr != NULL;
auxillary_expr = LLE_NEXT (auxillary_expr))
{
- target_expr = lambda_linear_expression_new (depth, invariants);
+ target_expr = lambda_linear_expression_new (depth, invariants,
+ lambda_obstack);
lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
depth, inverse, depth,
LLE_COEFFICIENTS (target_expr));
triangular portion. */
lambda_loopnest
-lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans)
+lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans,
+ struct obstack * lambda_obstack)
{
lambda_loopnest auxillary_nest, target_nest;
}
/* Compute the lattice base. */
- lattice = lambda_lattice_compute_base (nest);
+ lattice = lambda_lattice_compute_base (nest, lambda_obstack);
trans1 = lambda_trans_matrix_new (depth, depth);
/* Multiply the transformation matrix by the lattice base. */
/* Compute the auxiliary loop nest's space from the unimodular
portion. */
- auxillary_nest = lambda_compute_auxillary_space (nest, U);
+ auxillary_nest = lambda_compute_auxillary_space (nest, U, lambda_obstack);
/* Compute the loop step signs from the old step signs and the
transformation matrix. */
/* Compute the target loop nest space from the auxiliary nest and
the lower triangular matrix H. */
- target_nest = lambda_compute_target_space (auxillary_nest, H, stepsigns);
+ target_nest = lambda_compute_target_space (auxillary_nest, H, stepsigns,
+ lambda_obstack);
origin = lambda_vector_new (depth);
origin_invariants = lambda_matrix_new (depth, invariants);
lambda_matrix_vector_mult (LTM_MATRIX (trans), depth, depth,
static lambda_linear_expression
gcc_tree_to_linear_expression (int depth, tree expr,
VEC(tree,heap) *outerinductionvars,
- VEC(tree,heap) *invariants, int extra)
+ VEC(tree,heap) *invariants, int extra,
+ struct obstack * lambda_obstack)
{
lambda_linear_expression lle = NULL;
switch (TREE_CODE (expr))
{
case INTEGER_CST:
{
- lle = lambda_linear_expression_new (depth, 2 * depth);
+ lle = lambda_linear_expression_new (depth, 2 * depth, lambda_obstack);
LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr);
if (extra != 0)
LLE_CONSTANT (lle) += extra;
{
if (SSA_NAME_VAR (iv) == SSA_NAME_VAR (expr))
{
- lle = lambda_linear_expression_new (depth, 2 * depth);
+ lle = lambda_linear_expression_new (depth, 2 * depth,
+ lambda_obstack);
LLE_COEFFICIENTS (lle)[i] = 1;
if (extra != 0)
LLE_CONSTANT (lle) = extra;
{
if (SSA_NAME_VAR (invar) == SSA_NAME_VAR (expr))
{
- lle = lambda_linear_expression_new (depth, 2 * depth);
+ lle = lambda_linear_expression_new (depth, 2 * depth,
+ lambda_obstack);
LLE_INVARIANT_COEFFICIENTS (lle)[i] = 1;
if (extra != 0)
LLE_CONSTANT (lle) = extra;
VEC(tree,heap) * outerinductionvars,
VEC(tree,heap) ** lboundvars,
VEC(tree,heap) ** uboundvars,
- VEC(int,heap) ** steps)
+ VEC(int,heap) ** steps,
+ struct obstack * lambda_obstack)
{
tree phi;
tree exit_cond;
lboundvar = PHI_ARG_DEF (phi, 1);
lbound = gcc_tree_to_linear_expression (depth, lboundvar,
outerinductionvars, *invariants,
- 0);
+ 0, lambda_obstack);
}
else
{
lboundvar = PHI_ARG_DEF (phi, 0);
lbound = gcc_tree_to_linear_expression (depth, lboundvar,
outerinductionvars, *invariants,
- 0);
+ 0, lambda_obstack);
}
if (!lbound)
ubound = gcc_tree_to_linear_expression (depth, uboundvar,
outerinductionvars,
- *invariants, extra);
+ *invariants, extra, lambda_obstack);
uboundresult = build2 (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
build_int_cst (TREE_TYPE (uboundvar), extra));
VEC_safe_push (tree, heap, *uboundvars, uboundresult);
lambda_loopnest
gcc_loopnest_to_lambda_loopnest (struct loop *loop_nest,
VEC(tree,heap) **inductionvars,
- VEC(tree,heap) **invariants)
+ VEC(tree,heap) **invariants,
+ struct obstack * lambda_obstack)
{
lambda_loopnest ret = NULL;
struct loop *temp = loop_nest;
newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
&inductionvar, *inductionvars,
&lboundvars, &uboundvars,
- &steps);
+ &steps, lambda_obstack);
if (!newloop)
goto fail;
"Successfully converted loop nest to perfect loop nest.\n");
}
- ret = lambda_loopnest_new (depth, 2 * depth);
+ ret = lambda_loopnest_new (depth, 2 * depth, lambda_obstack);
for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
LN_LOOPS (ret)[i] = newloop;
return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
}
+/* Remove the induction variable defined at IV_STMT. */
+
+void
+remove_iv (tree iv_stmt)
+{
+ if (TREE_CODE (iv_stmt) == PHI_NODE)
+ {
+ int i;
+
+ for (i = 0; i < PHI_NUM_ARGS (iv_stmt); i++)
+ {
+ 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));
+ }
+
+ remove_phi_node (iv_stmt, NULL_TREE, true);
+ }
+ else
+ {
+ block_stmt_iterator bsi = bsi_for_stmt (iv_stmt);
+
+ 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
lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
VEC(tree,heap) *old_ivs,
VEC(tree,heap) *invariants,
+ VEC(tree,heap) **remove_ivs,
lambda_loopnest new_loopnest,
- lambda_trans_matrix transform)
+ lambda_trans_matrix transform,
+ struct obstack * lambda_obstack)
{
struct loop *temp;
size_t i = 0;
/* Compute the new expression for the induction
variable. */
depth = VEC_length (tree, new_ivs);
- lbv = lambda_body_vector_new (depth);
+ lbv = lambda_body_vector_new (depth, lambda_obstack);
LBV_COEFFICIENTS (lbv)[i] = 1;
- newlbv = lambda_body_vector_compute_new (transform, lbv);
+ newlbv = lambda_body_vector_compute_new (transform, lbv,
+ lambda_obstack);
newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
new_ivs, &stmts);
propagate_value (use_p, newiv);
update_stmt (stmt);
}
+
+ /* Remove the now unused induction variable. */
+ VEC_safe_push (tree, heap, *remove_ivs, oldiv_stmt);
}
VEC_free (tree, heap, new_ivs);
}
size_t i;
tree exit_cond;
+ /* Loops at depth 0 are perfect nests. */
if (!loop->inner)
return true;
+
bbs = get_loop_body (loop);
exit_cond = get_loop_exit_condition (loop);
+
for (i = 0; i < loop->num_nodes; i++)
{
if (bbs[i]->loop_father == loop)
{
block_stmt_iterator bsi;
+
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) == COND_EXPR
+ && exit_cond != stmt)
+ goto non_perfectly_nested;
+
if (stmt == exit_cond
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
continue;
+
+ non_perfectly_nested:
free (bbs);
return false;
}
}
}
+
free (bbs);
- /* See if the inner loops are perfectly nested as well. */
- if (loop->inner)
- return perfect_nest_p (loop->inner);
- return true;
+
+ return perfect_nest_p (loop->inner);
}
/* Replace the USES of X in STMT, or uses with the same step as X with Y.
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;
OSDN Git Service
