PR middle-end/46844

[pf3gnuchains/gcc-fork.git] / gcc / lambda-mat.c

diff --git a/gcc/lambda-mat.c b/gcc/lambda-mat.c
index 39b75e6..50fdb69 100644 (file)
--- a/gcc/lambda-mat.c
+++ b/gcc/lambda-mat.c
@@ -1,12 +1,12 @@
 /* Integer matrix math routines
 /* Integer matrix math routines

-   Copyright (C) 2003, 2004, 2005 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
    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
 version.
 
 GCC is distributed in the hope that it will be useful, but WITHOUT ANY


@@ -15,30 +15,29 @@ 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
 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 "coretypes.h"
 #include "tm.h"
 #include "ggc.h"
 #include "tree.h"
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
 #include "ggc.h"
 #include "tree.h"

+#include "tree-flow.h"

 #include "lambda.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
 /* 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;
 
 {
   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);
 
   for (i = 0; i < m; i++)
     mat[i] = lambda_vector_new (n);
 


@@ -164,19 +163,6 @@ lambda_matrix_mult (lambda_matrix mat1, lambda_matrix mat2,
     }
 }
 
     }
 }
 

-/* 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
 /* Delete rows r1 to r2 (not including r2).  */
 
 void


@@ -306,10 +292,12 @@ lambda_matrix_col_mc (lambda_matrix mat, int m, int c1, int const1)
    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.  */
 
    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
 
 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)
     {
 {
   if (n == 2)
     {


@@ -317,7 +305,7 @@ lambda_matrix_inverse (lambda_matrix mat, lambda_matrix inv, int n)
       a = mat[0][0];
       b = mat[1][0];
       c = mat[0][1];
       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;
       inv[0][0] =  d;
       inv[0][1] = -c;
       inv[1][0] = -b;


@@ -334,20 +322,21 @@ lambda_matrix_inverse (lambda_matrix mat, lambda_matrix inv, int n)
       return det;
     }
   else
       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
 }
 
 /* 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;
 
 {
   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);
 
   lambda_matrix_copy (mat, temp, n, n);
   lambda_matrix_id (inv, n);
 


@@ -482,7 +471,7 @@ lambda_matrix_hermite (lambda_matrix mat, int n,
 /* 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".
 /* 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.  */
 
    Ref: Algorithm 2.1 page 33 in "Loop Transformations for
    Restructuring Compilers" Utpal Banerjee.  */
 


@@ -527,7 +516,7 @@ lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
 /* 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".
 /* 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.  */
 
    Ref: Algorithm 2.2 page 36 in "Loop Transformations for
    Restructuring Compilers" Utpal Banerjee.  */
 


@@ -591,45 +580,6 @@ lambda_matrix_first_nz_vec (lambda_matrix mat, int rowsize, int colsize,
   return rowsize;
 }
 
   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.  */
 /* 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.  */