/* 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,
+static void lambda_matrix_get_column (lambda_matrix, int, int,
lambda_vector);
/* Allocate a matrix of M rows x N cols. */
lambda_matrix mat;
int i;
- mat = ggc_alloc (m * sizeof (lambda_vector));
-
+ mat = GGC_NEWVEC (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
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;
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
lambda_matrix M1, M2, M3, I;
int determinant;
- /* compute c(I-B^T inv(B B^T) B) e sub k */
+ /* Compute c(I-B^T inv(B B^T) B) e sub k. */
- /* M1 is the transpose of B */
+ /* M1 is the transpose of B. */
M1 = lambda_matrix_new (colsize, colsize);
lambda_matrix_transpose (B, M1, rowsize, colsize);