+2010-04-22 Laurynas Biveinis <laurynas.biveinis@gmail.com>
+
+ * tree-parloops.c (loop_parallel_p): New argument
+ parloop_obstack. Pass it down.
+ (parallelize_loops): New variable parloop_obstack. Initialize it,
+ pass it down, free it.
+
+ * tree-loop-linear.c (linear_transform_loops): Pass down
+ lambda_obstack.
+
+ * tree-data-ref.h (lambda_compute_access_matrices): New argument
+ of type struct obstack *.
+
+ * tree-data-ref.c (analyze_subscript_affine_affine): New variable
+ scratch_obstack. Initialize it, pass down, free it.
+
+ * lambda.h (lambda_loop_new): Remove.
+ (lambda_matrix_new, lambda_matrix_inverse)
+ (lambda_trans_matrix_new, lambda_trans_matrix_inverse): New
+ argument of type struct obstack *.
+
+ * lambda-trans.c (lambda_trans_matrix_new): New argument
+ lambda_obstack. Pass it down, use obstack allocation for ret.
+ (lambda_trans_matrix_inverse): New argument lambda_obstack. Pass
+ it down.
+
+ * lambda-mat.c (lambda_matrix_get_column)
+ (lambda_matrix_project_to_null): Remove.
+ (lambda_matrix_new): New argument lambda_obstack. Use obstack
+ allocation for mat.
+ (lambda_matrix_inverse_hard, lambda_matrix_inverse): New argument
+ lambda_obstack.
+
+ * lambda-code.c (lambda_loop_new): New function.
+ (lambda_lattice_new, compute_nest_using_fourier_motzkin)
+ (lambda_compute_auxillary_space, lambda_compute_target_space)
+ (lambda_loopnest_transform, gcc_loop_to_lambda_loop)
+ (lambda_loopnest_to_gcc_loopnest): Pass down lambda_obstack.
+ (build_access_matrix): New argument lambda_obstack. Use obstack
+ allocation for am.
+ (lambda_compute_step_signs, lambda_compute_access_matrices): New
+ argument lambda_obstack. Pass it down.
+
2010-04-22 Bernd Schmidt <bernds@codesourcery.com>
* optabs.h (expand_widening_mult): Declare.
static bool can_convert_to_perfect_nest (struct loop *);
+/* Create a new lambda loop in LAMBDA_OBSTACK. */
+
+static lambda_loop
+lambda_loop_new (struct obstack * lambda_obstack)
+{
+ lambda_loop result = (lambda_loop)
+ obstack_alloc (lambda_obstack, sizeof (struct lambda_loop_s));
+ memset (result, 0, sizeof (struct lambda_loop_s));
+ return result;
+}
+
/* Create a new lambda body vector. */
lambda_body_vector
{
lambda_body_vector ret;
- ret = (lambda_body_vector)obstack_alloc (lambda_obstack, 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_lattice ret
= (lambda_lattice)obstack_alloc (lambda_obstack, sizeof (*ret));
- LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
+ LATTICE_BASE (ret) = lambda_matrix_new (depth, depth, lambda_obstack);
LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
- LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
+ LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants,
+ lambda_obstack);
LATTICE_DIMENSION (ret) = depth;
LATTICE_INVARIANTS (ret) = invariants;
return ret;
lambda_vector swapvector, a1;
int newsize;
- A1 = lambda_matrix_new (128, depth);
- B1 = lambda_matrix_new (128, invariants);
+ A1 = lambda_matrix_new (128, depth, lambda_obstack);
+ B1 = lambda_matrix_new (128, invariants, lambda_obstack);
a1 = lambda_vector_new (128);
auxillary_nest = lambda_loopnest_new (depth, invariants, lambda_obstack);
for (i = depth - 1; i >= 0; i--)
{
- loop = lambda_loop_new ();
+ loop = lambda_loop_new (lambda_obstack);
LN_LOOPS (auxillary_nest)[i] = loop;
LL_STEP (loop) = 1;
/* Unfortunately, we can't know the number of constraints we'll have
ahead of time, but this should be enough even in ridiculous loop nest
cases. We must not go over this limit. */
- A = lambda_matrix_new (128, depth);
- B = lambda_matrix_new (128, invariants);
+ A = lambda_matrix_new (128, depth, lambda_obstack);
+ B = lambda_matrix_new (128, invariants, lambda_obstack);
a = lambda_vector_new (128);
- A1 = lambda_matrix_new (128, depth);
- B1 = lambda_matrix_new (128, invariants);
+ A1 = lambda_matrix_new (128, depth, lambda_obstack);
+ B1 = lambda_matrix_new (128, invariants, lambda_obstack);
a1 = lambda_vector_new (128);
/* Store the bounds in the equation matrix A, constant vector a, and
/* Now compute the auxiliary space bounds by first inverting U, multiplying
it by A1, then performing Fourier-Motzkin. */
- invertedtrans = lambda_matrix_new (depth, depth);
+ invertedtrans = lambda_matrix_new (depth, depth, lambda_obstack);
/* Compute the inverse of U. */
lambda_matrix_inverse (LTM_MATRIX (trans),
- invertedtrans, depth);
+ invertedtrans, depth, lambda_obstack);
/* A = A1 inv(U). */
lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
depth = LN_DEPTH (auxillary_nest);
invariants = LN_INVARIANTS (auxillary_nest);
- inverse = lambda_matrix_new (depth, depth);
- determinant = lambda_matrix_inverse (LTM_MATRIX (H), inverse, depth);
+ inverse = lambda_matrix_new (depth, depth, lambda_obstack);
+ determinant = lambda_matrix_inverse (LTM_MATRIX (H), inverse, depth,
+ lambda_obstack);
/* H1 is H excluding its diagonal. */
- H1 = lambda_matrix_new (depth, depth);
+ H1 = lambda_matrix_new (depth, depth, lambda_obstack);
lambda_matrix_copy (LTM_MATRIX (H), H1, depth, depth);
for (i = 0; i < depth; i++)
H1[i][i] = 0;
/* Computes the linear offsets of the loop bounds. */
- target = lambda_matrix_new (depth, depth);
+ target = lambda_matrix_new (depth, depth, lambda_obstack);
lambda_matrix_mult (H1, inverse, target, depth, depth, depth);
target_nest = lambda_loopnest_new (depth, invariants, lambda_obstack);
{
/* Get a new loop structure. */
- target_loop = lambda_loop_new ();
+ target_loop = lambda_loop_new (lambda_obstack);
LN_LOOPS (target_nest)[i] = target_loop;
/* Computes the gcd of the coefficients of the linear part. */
result. */
static lambda_vector
-lambda_compute_step_signs (lambda_trans_matrix trans, lambda_vector stepsigns)
+lambda_compute_step_signs (lambda_trans_matrix trans,
+ lambda_vector stepsigns,
+ struct obstack * lambda_obstack)
{
lambda_matrix matrix, H;
int size;
matrix = LTM_MATRIX (trans);
size = LTM_ROWSIZE (trans);
- H = lambda_matrix_new (size, size);
+ H = lambda_matrix_new (size, size, lambda_obstack);
newsteps = lambda_vector_new (size);
lambda_vector_copy (stepsigns, newsteps, size);
/* Compute the lattice base. */
lattice = lambda_lattice_compute_base (nest, lambda_obstack);
- trans1 = lambda_trans_matrix_new (depth, depth);
+ trans1 = lambda_trans_matrix_new (depth, depth, lambda_obstack);
/* Multiply the transformation matrix by the lattice base. */
LTM_MATRIX (trans1), depth, depth, depth);
/* Compute the Hermite normal form for the new transformation matrix. */
- H = lambda_trans_matrix_new (depth, depth);
- U = lambda_trans_matrix_new (depth, depth);
+ H = lambda_trans_matrix_new (depth, depth, lambda_obstack);
+ U = lambda_trans_matrix_new (depth, depth, lambda_obstack);
lambda_matrix_hermite (LTM_MATRIX (trans1), depth, LTM_MATRIX (H),
LTM_MATRIX (U));
/* Compute the auxiliary loop nest's space from the unimodular
portion. */
- auxillary_nest = lambda_compute_auxillary_space (nest, U, lambda_obstack);
+ auxillary_nest = lambda_compute_auxillary_space (nest, U,
+ lambda_obstack);
/* Compute the loop step signs from the old step signs and the
transformation matrix. */
- stepsigns = lambda_compute_step_signs (trans1, stepsigns);
+ stepsigns = lambda_compute_step_signs (trans1, stepsigns,
+ lambda_obstack);
/* 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,
lambda_obstack);
origin = lambda_vector_new (depth);
- origin_invariants = lambda_matrix_new (depth, invariants);
+ origin_invariants = lambda_matrix_new (depth, invariants, lambda_obstack);
lambda_matrix_vector_mult (LTM_MATRIX (trans), depth, depth,
LATTICE_ORIGIN (lattice), origin);
lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_ORIGIN_INVARIANTS (lattice),
return NULL;
}
- lloop = lambda_loop_new ();
+ lloop = lambda_loop_new (lambda_obstack);
LL_STEP (lloop) = stepint;
LL_LOWER_BOUND (lloop) = lbound;
LL_UPPER_BOUND (lloop) = ubound;
tree oldiv;
gimple_stmt_iterator bsi;
- transform = lambda_trans_matrix_inverse (transform);
+ transform = lambda_trans_matrix_inverse (transform, lambda_obstack);
if (dump_file)
{
static bool
build_access_matrix (data_reference_p data_reference,
- VEC (tree, heap) *parameters, VEC (loop_p, heap) *nest)
+ VEC (tree, heap) *parameters,
+ VEC (loop_p, heap) *nest,
+ struct obstack * lambda_obstack)
{
- struct access_matrix *am = GGC_NEW (struct access_matrix);
+ struct access_matrix *am = (struct access_matrix *)
+ obstack_alloc(lambda_obstack, sizeof (struct access_matrix));
unsigned i, ndim = DR_NUM_DIMENSIONS (data_reference);
unsigned nivs = VEC_length (loop_p, nest);
unsigned lambda_nb_columns;
bool
lambda_compute_access_matrices (VEC (data_reference_p, heap) *datarefs,
VEC (tree, heap) *parameters,
- VEC (loop_p, heap) *nest)
+ VEC (loop_p, heap) *nest,
+ struct obstack * lambda_obstack)
{
data_reference_p dataref;
unsigned ix;
for (ix = 0; VEC_iterate (data_reference_p, datarefs, ix, dataref); ix++)
- if (!build_access_matrix (dataref, parameters, nest))
+ if (!build_access_matrix (dataref, parameters, nest, lambda_obstack))
return false;
return true;
#include "tree-flow.h"
#include "lambda.h"
-static void lambda_matrix_get_column (lambda_matrix, int, int,
- lambda_vector);
-
/* Allocate a matrix of M rows x N cols. */
lambda_matrix
-lambda_matrix_new (int m, int n)
+lambda_matrix_new (int m, int n, struct obstack * lambda_obstack)
{
lambda_matrix mat;
int i;
- mat = GGC_NEWVEC (lambda_vector, m);
+ mat = (lambda_matrix) obstack_alloc (lambda_obstack,
+ sizeof (lambda_vector *) * m);
for (i = 0; i < m; i++)
mat[i] = lambda_vector_new (n);
}
}
-/* Get column COL from the matrix MAT and store it in VEC. MAT has
- N rows, so the length of VEC must be N. */
-
-static void
-lambda_matrix_get_column (lambda_matrix mat, int n, int col,
- lambda_vector vec)
-{
- int i;
-
- for (i = 0; i < n; i++)
- vec[i] = mat[i][col];
-}
-
/* Delete rows r1 to r2 (not including r2). */
void
When MAT is a 2 x 2 matrix, we don't go through the whole process, because
it is easily inverted by inspection and it is a very common case. */
-static int lambda_matrix_inverse_hard (lambda_matrix, lambda_matrix, int);
+static int lambda_matrix_inverse_hard (lambda_matrix, lambda_matrix, int,
+ struct obstack *);
int
-lambda_matrix_inverse (lambda_matrix mat, lambda_matrix inv, int n)
+lambda_matrix_inverse (lambda_matrix mat, lambda_matrix inv, int n,
+ struct obstack * lambda_obstack)
{
if (n == 2)
{
return det;
}
else
- return lambda_matrix_inverse_hard (mat, inv, n);
+ return lambda_matrix_inverse_hard (mat, inv, n, lambda_obstack);
}
/* If MAT is not a special case, invert it the hard way. */
static int
-lambda_matrix_inverse_hard (lambda_matrix mat, lambda_matrix inv, int n)
+lambda_matrix_inverse_hard (lambda_matrix mat, lambda_matrix inv, int n,
+ struct obstack * lambda_obstack)
{
lambda_vector row;
lambda_matrix temp;
int i, j;
int determinant;
- temp = lambda_matrix_new (n, n);
+ temp = lambda_matrix_new (n, n, lambda_obstack);
lambda_matrix_copy (mat, temp, n, n);
lambda_matrix_id (inv, n);
return rowsize;
}
-/* Calculate the projection of E sub k to the null space of B. */
-
-void
-lambda_matrix_project_to_null (lambda_matrix B, int rowsize,
- int colsize, int k, lambda_vector x)
-{
- lambda_matrix M1, M2, M3, I;
- int determinant;
-
- /* Compute c(I-B^T inv(B B^T) B) e sub k. */
-
- /* M1 is the transpose of B. */
- M1 = lambda_matrix_new (colsize, colsize);
- lambda_matrix_transpose (B, M1, rowsize, colsize);
-
- /* M2 = B * B^T */
- M2 = lambda_matrix_new (colsize, colsize);
- lambda_matrix_mult (B, M1, M2, rowsize, colsize, rowsize);
-
- /* M3 = inv(M2) */
- M3 = lambda_matrix_new (colsize, colsize);
- determinant = lambda_matrix_inverse (M2, M3, rowsize);
-
- /* M2 = B^T (inv(B B^T)) */
- lambda_matrix_mult (M1, M3, M2, colsize, rowsize, rowsize);
-
- /* M1 = B^T (inv(B B^T)) B */
- lambda_matrix_mult (M2, B, M1, colsize, rowsize, colsize);
- lambda_matrix_negate (M1, M1, colsize, colsize);
-
- I = lambda_matrix_new (colsize, colsize);
- lambda_matrix_id (I, colsize);
-
- lambda_matrix_add_mc (I, determinant, M1, 1, M2, colsize, colsize);
-
- lambda_matrix_get_column (M2, colsize, k - 1, x);
-
-}
-
/* Multiply a vector VEC by a matrix MAT.
MAT is an M*N matrix, and VEC is a vector with length N. The result
is stored in DEST which must be a vector of length M. */
/* Allocate a new transformation matrix. */
lambda_trans_matrix
-lambda_trans_matrix_new (int colsize, int rowsize)
+lambda_trans_matrix_new (int colsize, int rowsize,
+ struct obstack * lambda_obstack)
{
lambda_trans_matrix ret;
- ret = GGC_NEW (struct lambda_trans_matrix_s);
- LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize);
+ ret = (lambda_trans_matrix)
+ obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
+ LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
LTM_ROWSIZE (ret) = rowsize;
LTM_COLSIZE (ret) = colsize;
LTM_DENOMINATOR (ret) = 1;
/* Compute the inverse of the transformation matrix MAT. */
lambda_trans_matrix
-lambda_trans_matrix_inverse (lambda_trans_matrix mat)
+lambda_trans_matrix_inverse (lambda_trans_matrix mat,
+ struct obstack * lambda_obstack)
{
lambda_trans_matrix inverse;
int determinant;
- inverse = lambda_trans_matrix_new (LTM_ROWSIZE (mat), LTM_COLSIZE (mat));
+ inverse = lambda_trans_matrix_new (LTM_ROWSIZE (mat), LTM_COLSIZE (mat),
+ lambda_obstack);
determinant = lambda_matrix_inverse (LTM_MATRIX (mat), LTM_MATRIX (inverse),
- LTM_ROWSIZE (mat));
+ LTM_ROWSIZE (mat), lambda_obstack);
LTM_DENOMINATOR (inverse) = determinant;
return inverse;
}
bool perfect_nest_p (struct loop *);
void print_lambda_loopnest (FILE *, lambda_loopnest, char);
-#define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
-
void print_lambda_loop (FILE *, lambda_loop, int, int, char);
-lambda_matrix lambda_matrix_new (int, int);
+lambda_matrix lambda_matrix_new (int, int, struct obstack *);
void lambda_matrix_id (lambda_matrix, int);
bool lambda_matrix_id_p (lambda_matrix, int);
void lambda_matrix_col_add (lambda_matrix, int, int, int, int);
void lambda_matrix_col_negate (lambda_matrix, int, int);
void lambda_matrix_col_mc (lambda_matrix, int, int, int);
-int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int);
+int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int, struct obstack *);
void lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix);
void lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
void lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
lambda_vector);
void print_lambda_matrix (FILE *, lambda_matrix, int, int);
-lambda_trans_matrix lambda_trans_matrix_new (int, int);
+lambda_trans_matrix lambda_trans_matrix_new (int, int, struct obstack *);
bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix);
bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix);
int lambda_trans_matrix_rank (lambda_trans_matrix);
lambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix);
lambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix);
-lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix);
+lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix,
+ struct obstack *);
void print_lambda_trans_matrix (FILE *, lambda_trans_matrix);
void lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector,
lambda_vector);
unsigned nb_vars_a, nb_vars_b, dim;
HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
lambda_matrix A, U, S;
+ struct obstack scratch_obstack;
if (eq_evolutions_p (chrec_a, chrec_b))
{
nb_vars_a = nb_vars_in_chrec (chrec_a);
nb_vars_b = nb_vars_in_chrec (chrec_b);
+ gcc_obstack_init (&scratch_obstack);
+
dim = nb_vars_a + nb_vars_b;
- U = lambda_matrix_new (dim, dim);
- A = lambda_matrix_new (dim, 1);
- S = lambda_matrix_new (dim, 1);
+ U = lambda_matrix_new (dim, dim, &scratch_obstack);
+ A = lambda_matrix_new (dim, 1, &scratch_obstack);
+ S = lambda_matrix_new (dim, 1, &scratch_obstack);
init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
}
end_analyze_subs_aa:
+ obstack_free (&scratch_obstack, NULL);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (overlaps_a = ");
void lambda_collect_parameters (VEC (data_reference_p, heap) *,
VEC (tree, heap) **);
bool lambda_compute_access_matrices (VEC (data_reference_p, heap) *,
- VEC (tree, heap) *, VEC (loop_p, heap) *);
+ VEC (tree, heap) *,
+ VEC (loop_p, heap) *,
+ struct obstack *);
/* In tree-data-ref.c */
void split_constant_offset (tree , tree *, tree *);
goto free_and_continue;
lambda_collect_parameters (datarefs, &lambda_parameters);
- if (!lambda_compute_access_matrices (datarefs, lambda_parameters, nest))
+ if (!lambda_compute_access_matrices (datarefs, lambda_parameters,
+ nest, &lambda_obstack))
goto free_and_continue;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_ddrs (dump_file, dependence_relations);
/* Build the transformation matrix. */
- trans = lambda_trans_matrix_new (depth, depth);
+ trans = lambda_trans_matrix_new (depth, depth, &lambda_obstack);
lambda_matrix_id (LTM_MATRIX (trans), depth);
trans = try_interchange_loops (trans, depth, dependence_relations,
datarefs, loop_nest);
in parallel). */
static bool
-loop_parallel_p (struct loop *loop)
+loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
{
VEC (ddr_p, heap) * dependence_relations;
VEC (data_reference_p, heap) *datarefs;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_data_dependence_relations (dump_file, dependence_relations);
- trans = lambda_trans_matrix_new (1, 1);
+ trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
LTM_MATRIX (trans)[0][0] = -1;
if (lambda_transform_legal_p (trans, 1, dependence_relations))
struct tree_niter_desc niter_desc;
loop_iterator li;
htab_t reduction_list;
+ struct obstack parloop_obstack;
HOST_WIDE_INT estimated;
LOC loop_loc;
-
+
/* Do not parallelize loops in the functions created by parallelization. */
if (parallelized_function_p (cfun->decl))
return false;
if (cfun->has_nonlocal_label)
return false;
+ gcc_obstack_init (&parloop_obstack);
reduction_list = htab_create (10, reduction_info_hash,
reduction_info_eq, free);
init_stmt_vec_info_vec ();
if (!try_create_reduction_list (loop, reduction_list))
continue;
- if (!flag_loop_parallelize_all && !loop_parallel_p (loop))
+ if (!flag_loop_parallelize_all
+ && !loop_parallel_p (loop, &parloop_obstack))
continue;
changed = true;
free_stmt_vec_info_vec ();
htab_delete (reduction_list);
+ obstack_free (&parloop_obstack, NULL);
/* Parallelization will cause new function calls to be inserted through
which local variables will escape. Reset the points-to solution