/* Integer matrix math routines
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2007, 2008 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 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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+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 "tm.h"
#include "ggc.h"
-#include "varray.h"
#include "tree.h"
+#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_alloc (m * sizeof (lambda_vector));
-
+ mat = (lambda_matrix) obstack_alloc (lambda_obstack,
+ sizeof (lambda_vector *) * m);
+
for (i = 0; i < m; i++)
mat[i] = lambda_vector_new (n);
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
}
}
-/* 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)
{
a = mat[0][0];
b = mat[1][0];
c = mat[0][1];
- d = mat[1][1];
+ d = mat[1][1];
inv[0][0] = d;
inv[0][1] = -c;
inv[1][0] = -b;
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);
row = temp[j];
diagonal = row[j];
- /* If the matrix is singular, abort. */
- if (diagonal == 0)
- abort ();
+ /* The matrix must not be singular. */
+ gcc_assert (diagonal);
determinant = determinant * diagonal;
}
}
- /* Stop when only the diagonal element is non-zero. */
+ /* 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);
/* 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. */
/* 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. */
}
}
-/* When it exists, return the first non-zero row in MAT after row
+/* When it exists, return the first nonzero row in MAT after row
STARTROW. Otherwise return rowsize. */
int
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. */
OSDN Git Service
