diff options
author | Sebastian Pop <sebastian.pop@amd.com> | 2011-01-25 21:24:23 +0000 |
---|---|---|
committer | Sebastian Pop <spop@gcc.gnu.org> | 2011-01-25 21:24:23 +0000 |
commit | b305e3dab4edef2ea58213e04a65a12408a97894 (patch) | |
tree | 95b39b6193ad1bd1417d5ce2c4c7944ac0abc0ee /gcc/lambda-mat.c | |
parent | 6bdfdb96eeec5da99a6aa4ca592af1d6b9cef237 (diff) | |
download | gcc-b305e3dab4edef2ea58213e04a65a12408a97894.zip gcc-b305e3dab4edef2ea58213e04a65a12408a97894.tar.gz gcc-b305e3dab4edef2ea58213e04a65a12408a97894.tar.bz2 |
Remove the lambda framework and make -ftree-loop-linear an alias of -floop-interchange.
2011-01-17 Sebastian Pop <sebastian.pop@amd.com>
toplev/
* MAINTAINERS (linear loop transforms): Removed.
toplev/gcc/
* Makefile.in (LAMBDA_H): Removed.
(TREE_DATA_REF_H): Remove dependence on LAMBDA_H.
(OBJS-common): Remove dependence on lambda-code.o, lambda-mat.o,
lambda-trans.o, and tree-loop-linear.o.
(lto-symtab.o): Remove dependence on LAMBDA_H.
(tree-loop-linear.o): Remove rule.
(lambda-mat.o): Same.
(lambda-trans.o): Same.
(lambda-code.o): Same.
(tree-vect-loop.o): Add missing dependence on TREE_DATA_REF_H.
(tree-vect-slp.o): Same.
* hwint.h (gcd): Moved here.
(least_common_multiple): Same.
* lambda-code.c: Removed.
* lambda-mat.c: Removed.
* lambda-trans.c: Removed.
* lambda.h: Removed.
* tree-loop-linear.c: Removed.
* lto-symtab.c: Do not include lambda.h.
* omega.c (gcd): Removed.
* passes.c (init_optimization_passes): Remove pass_linear_transform.
* tree-data-ref.c (print_lambda_vector): Moved here.
(lambda_vector_copy): Same.
(lambda_matrix_copy): Same.
(lambda_matrix_id): Same.
(lambda_vector_first_nz): Same.
(lambda_matrix_row_add): Same.
(lambda_matrix_row_exchange): Same.
(lambda_vector_mult_const): Same.
(lambda_vector_negate): Same.
(lambda_matrix_row_negate): Same.
(lambda_vector_equal): Same.
(lambda_matrix_right_hermite): Same.
* tree-data-ref.h: Do not include lambda.h.
(lambda_vector): Moved here.
(lambda_matrix): Same.
(dependence_level): Same.
(lambda_transform_legal_p): Removed declaration.
(lambda_collect_parameters): Same.
(lambda_compute_access_matrices): Same.
(lambda_vector_gcd): Same.
(lambda_vector_new): Same.
(lambda_vector_clear): Same.
(lambda_vector_lexico_pos): Same.
(lambda_vector_zerop): Same.
(lambda_matrix_new): Same.
* tree-flow.h (least_common_multiple): Removed declaration.
* tree-parloops.c (lambda_trans_matrix): Moved here.
(LTM_MATRIX): Same.
(LTM_ROWSIZE): Same.
(LTM_COLSIZE): Same.
(LTM_DENOMINATOR): Same.
(lambda_trans_matrix_new): Same.
(lambda_matrix_vector_mult): Same.
(lambda_transform_legal_p): Same.
* tree-pass.h (pass_linear_transform): Removed declaration.
* tree-ssa-loop.c (tree_linear_transform): Removed.
(gate_tree_linear_transform): Removed.
(pass_linear_transform): Removed.
(gate_graphite_transforms): Make flag_tree_loop_linear an alias of
flag_loop_interchange.
toplev/gcc/testsuite/
* gfortran.dg/graphite/interchange-4.f: New.
* gfortran.dg/graphite/interchange-5.f: New.
* gcc.dg/tree-ssa/ltrans-1.c: Removed.
* gcc.dg/tree-ssa/ltrans-2.c: Removed.
* gcc.dg/tree-ssa/ltrans-3.c: Removed.
* gcc.dg/tree-ssa/ltrans-4.c: Removed.
* gcc.dg/tree-ssa/ltrans-5.c: Removed.
* gcc.dg/tree-ssa/ltrans-6.c: Removed.
* gcc.dg/tree-ssa/ltrans-8.c: Removed.
* gfortran.dg/ltrans-7.f90: Removed.
* gcc.dg/tree-ssa/data-dep-1.c: Removed.
* gcc.dg/pr18792.c: -> gcc.dg/graphite/pr18792.c
* gcc.dg/pr19910.c: -> gcc.dg/graphite/pr19910.c
* gcc.dg/tree-ssa/20041110-1.c: -> gcc.dg/graphite/pr20041110-1.c
* gcc.dg/tree-ssa/pr20256.c: -> gcc.dg/graphite/pr20256.c
* gcc.dg/pr23625.c: -> gcc.dg/graphite/pr23625.c
* gcc.dg/tree-ssa/pr23820.c: -> gcc.dg/graphite/pr23820.c
* gcc.dg/tree-ssa/pr24309.c: -> gcc.dg/graphite/pr24309.c
* gcc.dg/tree-ssa/pr26435.c: -> gcc.dg/graphite/pr26435.c
* gcc.dg/pr29330.c: -> gcc.dg/graphite/pr29330.c
* gcc.dg/pr29581-1.c: -> gcc.dg/graphite/pr29581-1.c
* gcc.dg/pr29581-2.c: -> gcc.dg/graphite/pr29581-2.c
* gcc.dg/pr29581-3.c: -> gcc.dg/graphite/pr29581-3.c
* gcc.dg/pr29581-4.c: -> gcc.dg/graphite/pr29581-4.c
* gcc.dg/tree-ssa/loop-27.c: -> gcc.dg/graphite/pr30565.c
* gcc.dg/tree-ssa/pr31183.c: -> gcc.dg/graphite/pr31183.c
* gcc.dg/tree-ssa/pr33576.c: -> gcc.dg/graphite/pr33576.c
* gcc.dg/tree-ssa/pr33766.c: -> gcc.dg/graphite/pr33766.c
* gcc.dg/pr34016.c: -> gcc.dg/graphite/pr34016.c
* gcc.dg/tree-ssa/pr34017.c: -> gcc.dg/graphite/pr34017.c
* gcc.dg/tree-ssa/pr34123.c: -> gcc.dg/graphite/pr34123.c
* gcc.dg/tree-ssa/pr36287.c: -> gcc.dg/graphite/pr36287.c
* gcc.dg/tree-ssa/pr37686.c: -> gcc.dg/graphite/pr37686.c
* gcc.dg/pr42917.c: -> gcc.dg/graphite/pr42917.c
* gfortran.dg/loop_nest_1.f90: -> gfortran.dg/graphite/pr29290.f90
* gfortran.dg/pr29581.f90: -> gfortran.dg/graphite/pr29581.f90
* gfortran.dg/pr36286.f90: -> gfortran.dg/graphite/pr36286.f90
* gfortran.dg/pr36922.f: -> gfortran.dg/graphite/pr36922.f
* gfortran.dg/pr39516.f: -> gfortran.dg/graphite/pr39516.f
From-SVN: r169251
Diffstat (limited to 'gcc/lambda-mat.c')
-rw-r--r-- | gcc/lambda-mat.c | 608 |
1 files changed, 0 insertions, 608 deletions
diff --git a/gcc/lambda-mat.c b/gcc/lambda-mat.c deleted file mode 100644 index c57fb58..0000000 --- a/gcc/lambda-mat.c +++ /dev/null @@ -1,608 +0,0 @@ -/* Integer matrix math routines - Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010 - Free Software Foundation, Inc. - Contributed by Daniel Berlin <dberlin@dberlin.org>. - -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 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 COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "tree-flow.h" -#include "lambda.h" - -/* Allocate a matrix of M rows x N cols. */ - -lambda_matrix -lambda_matrix_new (int m, int n, struct obstack * lambda_obstack) -{ - lambda_matrix mat; - int i; - - mat = (lambda_matrix) obstack_alloc (lambda_obstack, - sizeof (lambda_vector *) * m); - - for (i = 0; i < m; i++) - mat[i] = lambda_vector_new (n); - - return mat; -} - -/* Copy the elements of M x N matrix MAT1 to MAT2. */ - -void -lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2, - int m, int n) -{ - int i; - - for (i = 0; i < m; i++) - lambda_vector_copy (mat1[i], mat2[i], n); -} - -/* Store the N x N identity matrix in MAT. */ - -void -lambda_matrix_id (lambda_matrix mat, int size) -{ - int i, j; - - for (i = 0; i < size; i++) - for (j = 0; j < size; j++) - mat[i][j] = (i == j) ? 1 : 0; -} - -/* Return true if MAT is the identity matrix of SIZE */ - -bool -lambda_matrix_id_p (lambda_matrix mat, int size) -{ - int i, j; - for (i = 0; i < size; i++) - for (j = 0; j < size; j++) - { - if (i == j) - { - if (mat[i][j] != 1) - return false; - } - else - { - if (mat[i][j] != 0) - return false; - } - } - return true; -} - -/* Negate the elements of the M x N matrix MAT1 and store it in MAT2. */ - -void -lambda_matrix_negate (lambda_matrix mat1, lambda_matrix mat2, int m, int n) -{ - int i; - - for (i = 0; i < m; i++) - lambda_vector_negate (mat1[i], mat2[i], n); -} - -/* Take the transpose of matrix MAT1 and store it in MAT2. - MAT1 is an M x N matrix, so MAT2 must be N x M. */ - -void -lambda_matrix_transpose (lambda_matrix mat1, lambda_matrix mat2, int m, int n) -{ - int i, j; - - for (i = 0; i < n; i++) - for (j = 0; j < m; j++) - mat2[i][j] = mat1[j][i]; -} - - -/* Add two M x N matrices together: MAT3 = MAT1+MAT2. */ - -void -lambda_matrix_add (lambda_matrix mat1, lambda_matrix mat2, - lambda_matrix mat3, int m, int n) -{ - int i; - - for (i = 0; i < m; i++) - lambda_vector_add (mat1[i], mat2[i], mat3[i], n); -} - -/* MAT3 = CONST1 * MAT1 + CONST2 * MAT2. All matrices are M x N. */ - -void -lambda_matrix_add_mc (lambda_matrix mat1, int const1, - lambda_matrix mat2, int const2, - lambda_matrix mat3, int m, int n) -{ - int i; - - for (i = 0; i < m; i++) - lambda_vector_add_mc (mat1[i], const1, mat2[i], const2, mat3[i], n); -} - -/* Multiply two matrices: MAT3 = MAT1 * MAT2. - MAT1 is an M x R matrix, and MAT2 is R x N. The resulting MAT2 - must therefore be M x N. */ - -void -lambda_matrix_mult (lambda_matrix mat1, lambda_matrix mat2, - lambda_matrix mat3, int m, int r, int n) -{ - - int i, j, k; - - for (i = 0; i < m; i++) - { - for (j = 0; j < n; j++) - { - mat3[i][j] = 0; - for (k = 0; k < r; k++) - mat3[i][j] += mat1[i][k] * mat2[k][j]; - } - } -} - -/* Delete rows r1 to r2 (not including r2). */ - -void -lambda_matrix_delete_rows (lambda_matrix mat, int rows, int from, int to) -{ - int i; - int dist; - dist = to - from; - - for (i = to; i < rows; i++) - mat[i - dist] = mat[i]; - - for (i = rows - dist; i < rows; i++) - mat[i] = NULL; -} - -/* Swap rows R1 and R2 in matrix MAT. */ - -void -lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2) -{ - lambda_vector row; - - row = mat[r1]; - mat[r1] = mat[r2]; - mat[r2] = row; -} - -/* Add a multiple of row R1 of matrix MAT with N columns to row R2: - R2 = R2 + CONST1 * R1. */ - -void -lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1) -{ - int i; - - if (const1 == 0) - return; - - for (i = 0; i < n; i++) - mat[r2][i] += const1 * mat[r1][i]; -} - -/* Negate row R1 of matrix MAT which has N columns. */ - -void -lambda_matrix_row_negate (lambda_matrix mat, int n, int r1) -{ - lambda_vector_negate (mat[r1], mat[r1], n); -} - -/* Multiply row R1 of matrix MAT with N columns by CONST1. */ - -void -lambda_matrix_row_mc (lambda_matrix mat, int n, int r1, int const1) -{ - int i; - - for (i = 0; i < n; i++) - mat[r1][i] *= const1; -} - -/* Exchange COL1 and COL2 in matrix MAT. M is the number of rows. */ - -void -lambda_matrix_col_exchange (lambda_matrix mat, int m, int col1, int col2) -{ - int i; - int tmp; - for (i = 0; i < m; i++) - { - tmp = mat[i][col1]; - mat[i][col1] = mat[i][col2]; - mat[i][col2] = tmp; - } -} - -/* Add a multiple of column C1 of matrix MAT with M rows to column C2: - C2 = C2 + CONST1 * C1. */ - -void -lambda_matrix_col_add (lambda_matrix mat, int m, int c1, int c2, int const1) -{ - int i; - - if (const1 == 0) - return; - - for (i = 0; i < m; i++) - mat[i][c2] += const1 * mat[i][c1]; -} - -/* Negate column C1 of matrix MAT which has M rows. */ - -void -lambda_matrix_col_negate (lambda_matrix mat, int m, int c1) -{ - int i; - - for (i = 0; i < m; i++) - mat[i][c1] *= -1; -} - -/* Multiply column C1 of matrix MAT with M rows by CONST1. */ - -void -lambda_matrix_col_mc (lambda_matrix mat, int m, int c1, int const1) -{ - int i; - - for (i = 0; i < m; i++) - mat[i][c1] *= const1; -} - -/* Compute the inverse of the N x N matrix MAT and store it in INV. - - We don't _really_ compute the inverse of MAT. Instead we compute - det(MAT)*inv(MAT), and we return det(MAT) to the caller as the function - result. This is necessary to preserve accuracy, because we are dealing - with integer matrices here. - - The algorithm used here is a column based Gauss-Jordan elimination on MAT - and the identity matrix in parallel. The inverse is the result of applying - the same operations on the identity matrix that reduce MAT to the identity - matrix. - - 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, - struct obstack *); - -int -lambda_matrix_inverse (lambda_matrix mat, lambda_matrix inv, int n, - struct obstack * lambda_obstack) -{ - if (n == 2) - { - int a, b, c, d, det; - a = mat[0][0]; - b = mat[1][0]; - c = mat[0][1]; - d = mat[1][1]; - inv[0][0] = d; - inv[0][1] = -c; - inv[1][0] = -b; - inv[1][1] = a; - det = (a * d - b * c); - if (det < 0) - { - det *= -1; - inv[0][0] *= -1; - inv[1][0] *= -1; - inv[0][1] *= -1; - inv[1][1] *= -1; - } - return det; - } - else - 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, - struct obstack * lambda_obstack) -{ - lambda_vector row; - lambda_matrix temp; - int i, j; - int determinant; - - temp = lambda_matrix_new (n, n, lambda_obstack); - lambda_matrix_copy (mat, temp, n, n); - lambda_matrix_id (inv, n); - - /* Reduce TEMP to a lower triangular form, applying the same operations on - INV which starts as the identity matrix. N is the number of rows and - columns. */ - for (j = 0; j < n; j++) - { - row = temp[j]; - - /* Make every element in the current row positive. */ - for (i = j; i < n; i++) - if (row[i] < 0) - { - lambda_matrix_col_negate (temp, n, i); - lambda_matrix_col_negate (inv, n, i); - } - - /* Sweep the upper triangle. Stop when only the diagonal element in the - current row is nonzero. */ - while (lambda_vector_first_nz (row, n, j + 1) < n) - { - int min_col = lambda_vector_min_nz (row, n, j); - lambda_matrix_col_exchange (temp, n, j, min_col); - lambda_matrix_col_exchange (inv, n, j, min_col); - - for (i = j + 1; i < n; i++) - { - int factor; - - factor = -1 * row[i]; - if (row[j] != 1) - factor /= row[j]; - - lambda_matrix_col_add (temp, n, j, i, factor); - lambda_matrix_col_add (inv, n, j, i, factor); - } - } - } - - /* Reduce TEMP from a lower triangular to the identity matrix. Also compute - the determinant, which now is simply the product of the elements on the - diagonal of TEMP. If one of these elements is 0, the matrix has 0 as an - eigenvalue so it is singular and hence not invertible. */ - determinant = 1; - for (j = n - 1; j >= 0; j--) - { - int diagonal; - - row = temp[j]; - diagonal = row[j]; - - /* The matrix must not be singular. */ - gcc_assert (diagonal); - - determinant = determinant * diagonal; - - /* If the diagonal is not 1, then multiply the each row by the - diagonal so that the middle number is now 1, rather than a - rational. */ - if (diagonal != 1) - { - for (i = 0; i < j; i++) - lambda_matrix_col_mc (inv, n, i, diagonal); - for (i = j + 1; i < n; i++) - lambda_matrix_col_mc (inv, n, i, diagonal); - - row[j] = diagonal = 1; - } - - /* Sweep the lower triangle column wise. */ - for (i = j - 1; i >= 0; i--) - { - if (row[i]) - { - int factor = -row[i]; - lambda_matrix_col_add (temp, n, j, i, factor); - lambda_matrix_col_add (inv, n, j, i, factor); - } - - } - } - - return determinant; -} - -/* Decompose a N x N matrix MAT to a product of a lower triangular H - and a unimodular U matrix such that MAT = H.U. N is the size of - the rows of MAT. */ - -void -lambda_matrix_hermite (lambda_matrix mat, int n, - lambda_matrix H, lambda_matrix U) -{ - lambda_vector row; - int i, j, factor, minimum_col; - - lambda_matrix_copy (mat, H, n, n); - lambda_matrix_id (U, n); - - for (j = 0; j < n; j++) - { - row = H[j]; - - /* Make every element of H[j][j..n] positive. */ - for (i = j; i < n; i++) - { - if (row[i] < 0) - { - lambda_matrix_col_negate (H, n, i); - lambda_vector_negate (U[i], U[i], n); - } - } - - /* Stop when only the diagonal element is nonzero. */ - while (lambda_vector_first_nz (row, n, j + 1) < n) - { - minimum_col = lambda_vector_min_nz (row, n, j); - lambda_matrix_col_exchange (H, n, j, minimum_col); - lambda_matrix_row_exchange (U, j, minimum_col); - - for (i = j + 1; i < n; i++) - { - factor = row[i] / row[j]; - lambda_matrix_col_add (H, n, j, i, -1 * factor); - lambda_matrix_row_add (U, n, i, j, factor); - } - } - } -} - -/* Given an M x N integer matrix A, this function determines an M x - M unimodular matrix U, and an M x N echelon matrix S such that - "U.A = S". This decomposition is also known as "right Hermite". - - Ref: Algorithm 2.1 page 33 in "Loop Transformations for - Restructuring Compilers" Utpal Banerjee. */ - -void -lambda_matrix_right_hermite (lambda_matrix A, int m, int n, - lambda_matrix S, lambda_matrix U) -{ - int i, j, i0 = 0; - - lambda_matrix_copy (A, S, m, n); - lambda_matrix_id (U, m); - - for (j = 0; j < n; j++) - { - if (lambda_vector_first_nz (S[j], m, i0) < m) - { - ++i0; - for (i = m - 1; i >= i0; i--) - { - while (S[i][j] != 0) - { - int sigma, factor, a, b; - - a = S[i-1][j]; - b = S[i][j]; - sigma = (a * b < 0) ? -1: 1; - a = abs (a); - b = abs (b); - factor = sigma * (a / b); - - lambda_matrix_row_add (S, n, i, i-1, -factor); - lambda_matrix_row_exchange (S, i, i-1); - - lambda_matrix_row_add (U, m, i, i-1, -factor); - lambda_matrix_row_exchange (U, i, i-1); - } - } - } - } -} - -/* Given an M x N integer matrix A, this function determines an M x M - unimodular matrix V, and an M x N echelon matrix S such that "A = - V.S". This decomposition is also known as "left Hermite". - - Ref: Algorithm 2.2 page 36 in "Loop Transformations for - Restructuring Compilers" Utpal Banerjee. */ - -void -lambda_matrix_left_hermite (lambda_matrix A, int m, int n, - lambda_matrix S, lambda_matrix V) -{ - int i, j, i0 = 0; - - lambda_matrix_copy (A, S, m, n); - lambda_matrix_id (V, m); - - for (j = 0; j < n; j++) - { - if (lambda_vector_first_nz (S[j], m, i0) < m) - { - ++i0; - for (i = m - 1; i >= i0; i--) - { - while (S[i][j] != 0) - { - int sigma, factor, a, b; - - a = S[i-1][j]; - b = S[i][j]; - sigma = (a * b < 0) ? -1: 1; - a = abs (a); - b = abs (b); - factor = sigma * (a / b); - - lambda_matrix_row_add (S, n, i, i-1, -factor); - lambda_matrix_row_exchange (S, i, i-1); - - lambda_matrix_col_add (V, m, i-1, i, factor); - lambda_matrix_col_exchange (V, m, i, i-1); - } - } - } - } -} - -/* When it exists, return the first nonzero row in MAT after row - STARTROW. Otherwise return rowsize. */ - -int -lambda_matrix_first_nz_vec (lambda_matrix mat, int rowsize, int colsize, - int startrow) -{ - int j; - bool found = false; - - for (j = startrow; (j < rowsize) && !found; j++) - { - if ((mat[j] != NULL) - && (lambda_vector_first_nz (mat[j], colsize, startrow) < colsize)) - found = true; - } - - if (found) - return j - 1; - return rowsize; -} - -/* 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. */ - -void -lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n, - lambda_vector vec, lambda_vector dest) -{ - int i, j; - - lambda_vector_clear (dest, m); - for (i = 0; i < m; i++) - for (j = 0; j < n; j++) - dest[i] += matrix[i][j] * vec[j]; -} - -/* Print out an M x N matrix MAT to OUTFILE. */ - -void -print_lambda_matrix (FILE * outfile, lambda_matrix matrix, int m, int n) -{ - int i; - - for (i = 0; i < m; i++) - print_lambda_vector (outfile, matrix[i], n); - fprintf (outfile, "\n"); -} - |