libjava/classpath/lib/java/util/EnumMap$6.class

/*  Loop transformation code generation
    Copyright (C) 2003, 2004, 2005 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
    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 COPYING.  If not, write to the Free
    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
    02111-1307, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "target.h"
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "expr.h"
#include "optabs.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-pass.h"
#include "tree-scalar-evolution.h"
#include "vec.h"
#include "lambda.h"

/* This loop nest code generation is based on non-singular matrix
   math.
 
 A little terminology and a general sketch of the algorithm.  See "A singular
 loop transformation framework based on non-singular matrices" by Wei Li and
 Keshav Pingali for formal proofs that the various statements below are
 correct. 

 A loop iteration space represents the points traversed by the loop.  A point in the
 iteration space can be represented by a vector of size <loop depth>.  You can
 therefore represent the iteration space as an integral combinations of a set
 of basis vectors. 

 A loop iteration space is dense if every integer point between the loop
 bounds is a point in the iteration space.  Every loop with a step of 1
 therefore has a dense iteration space.

 for i = 1 to 3, step 1 is a dense iteration space.
   
 A loop iteration space is sparse if it is not dense.  That is, the iteration
 space skips integer points that are within the loop bounds.  

 for i = 1 to 3, step 2 is a sparse iteration space, because the integer point
 2 is skipped.

 Dense source spaces are easy to transform, because they don't skip any
 points to begin with.  Thus we can compute the exact bounds of the target
 space using min/max and floor/ceil.

 For a dense source space, we take the transformation matrix, decompose it
 into a lower triangular part (H) and a unimodular part (U). 
 We then compute the auxiliary space from the unimodular part (source loop
 nest . U = auxiliary space) , which has two important properties:
  1. It traverses the iterations in the same lexicographic order as the source
  space.
  2. It is a dense space when the source is a dense space (even if the target
  space is going to be sparse).
 
 Given the auxiliary space, we use the lower triangular part to compute the
 bounds in the target space by simple matrix multiplication.
 The gaps in the target space (IE the new loop step sizes) will be the
 diagonals of the H matrix.

 Sparse source spaces require another step, because you can't directly compute
 the exact bounds of the auxiliary and target space from the sparse space.
 Rather than try to come up with a separate algorithm to handle sparse source
 spaces directly, we just find a legal transformation matrix that gives you
 the sparse source space, from a dense space, and then transform the dense
 space.

 For a regular sparse space, you can represent the source space as an integer
 lattice, and the base space of that lattice will always be dense.  Thus, we
 effectively use the lattice to figure out the transformation from the lattice
 base space, to the sparse iteration space (IE what transform was applied to
 the dense space to make it sparse).  We then compose this transform with the
 transformation matrix specified by the user (since our matrix transformations
 are closed under composition, this is okay).  We can then use the base space
 (which is dense) plus the composed transformation matrix, to compute the rest
 of the transform using the dense space algorithm above.
 
 In other words, our sparse source space (B) is decomposed into a dense base
 space (A), and a matrix (L) that transforms A into B, such that A.L = B.
 We then compute the composition of L and the user transformation matrix (T),
 so that T is now a transform from A to the result, instead of from B to the
 result. 
 IE A.(LT) = result instead of B.T = result
 Since A is now a dense source space, we can use the dense source space
 algorithm above to compute the result of applying transform (LT) to A.

 Fourier-Motzkin elimination is used to compute the bounds of the base space
 of the lattice.  */

DEF_VEC_I(int);
DEF_VEC_ALLOC_I(int,heap);

static bool perfect_nestify (struct loops *, 
			     struct loop *, VEC(tree,heap) *, 
			     VEC(tree,heap) *, VEC(int,heap) *,
			     VEC(tree,heap) *);
/* Lattice stuff that is internal to the code generation algorithm.  */

typedef struct
{
  /* Lattice base matrix.  */
  lambda_matrix base;
  /* Lattice dimension.  */
  int dimension;
  /* Origin vector for the coefficients.  */
  lambda_vector origin;
  /* Origin matrix for the invariants.  */
  lambda_matrix origin_invariants;
  /* Number of invariants.  */
  int invariants;
} *lambda_lattice;

#define LATTICE_BASE(T) ((T)->base)
#define LATTICE_DIMENSION(T) ((T)->dimension)
#define LATTICE_ORIGIN(T) ((T)->origin)
#define LATTICE_ORIGIN_INVARIANTS(T) ((T)->origin_invariants)
#define LATTICE_INVARIANTS(T) ((T)->invariants)

static bool lle_equal (lambda_linear_expression, lambda_linear_expression,
		       int, int);
static lambda_lattice lambda_lattice_new (int, int);
static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);

static tree find_induction_var_from_exit_cond (struct loop *);

/* Create a new lambda body vector.  */

lambda_body_vector
lambda_body_vector_new (int size)
{
  lambda_body_vector ret;

  ret = ggc_alloc (sizeof (*ret));
  LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
  LBV_SIZE (ret) = size;
  LBV_DENOMINATOR (ret) = 1;
  return ret;
}

/* Compute the new coefficients for the vector based on the
  *inverse* of the transformation matrix.  */

lambda_body_vector
lambda_body_vector_compute_new (lambda_trans_matrix transform,
				lambda_body_vector vect)
{
  lambda_body_vector temp;
  int depth;

  /* Make sure the matrix is square.  */
  gcc_assert (LTM_ROWSIZE (transform) == LTM_COLSIZE (transform));

  depth = LTM_ROWSIZE (transform);

  temp = lambda_body_vector_new (depth);
  LBV_DENOMINATOR (temp) =
    LBV_DENOMINATOR (vect) * LTM_DENOMINATOR (transform);
  lambda_vector_matrix_mult (LBV_COEFFICIENTS (vect), depth,
			     LTM_MATRIX (transform), depth,
			     LBV_COEFFICIENTS (temp));
  LBV_SIZE (temp) = LBV_SIZE (vect);
  return temp;
}

/* Print out a lambda body vector.  */

void
print_lambda_body_vector (FILE * outfile, lambda_body_vector body)
{
  print_lambda_vector (outfile, LBV_COEFFICIENTS (body), LBV_SIZE (body));
}

/* Return TRUE if two linear expressions are equal.  */

static bool
lle_equal (lambda_linear_expression lle1, lambda_linear_expression lle2,
	   int depth, int invariants)
{
  int i;

  if (lle1 == NULL || lle2 == NULL)
    return false;
  if (LLE_CONSTANT (lle1) != LLE_CONSTANT (lle2))
    return false;
  if (LLE_DENOMINATOR (lle1) != LLE_DENOMINATOR (lle2))
    return false;
  for (i = 0; i < depth; i++)
    if (LLE_COEFFICIENTS (lle1)[i] != LLE_COEFFICIENTS (lle2)[i])
      return false;
  for (i = 0; i < invariants; i++)
    if (LLE_INVARIANT_COEFFICIENTS (lle1)[i] !=
	LLE_INVARIANT_COEFFICIENTS (lle2)[i])
      return false;
  return true;
}

/* Create a new linear expression with dimension DIM, and total number
   of invariants INVARIANTS.  */

lambda_linear_expression
lambda_linear_expression_new (int dim, int invariants)
{
  lambda_linear_expression ret;

  ret = ggc_alloc_cleared (sizeof (*ret));

  LLE_COEFFICIENTS (ret) = lambda_vector_new (dim);
  LLE_CONSTANT (ret) = 0;
  LLE_INVARIANT_COEFFICIENTS (ret) = lambda_vector_new (invariants);
  LLE_DENOMINATOR (ret) = 1;
  LLE_NEXT (ret) = NULL;

  return ret;
}

/* Print out a linear expression EXPR, with SIZE coefficients, to OUTFILE.
   The starting letter used for variable names is START.  */

static void
print_linear_expression (FILE * outfile, lambda_vector expr, int size,
			 char start)
{
  int i;
  bool first = true;
  for (i = 0; i < size; i++)
    {
      if (expr[i] != 0)
	{
	  if (first)
	    {
	      if (expr[i] < 0)
		fprintf (outfile, "-");
	      first = false;
	    }
	  else if (expr[i] > 0)
	    fprintf (outfile, " + ");
	  else
	    fprintf (outfile, " - ");
	  if (abs (expr[i]) == 1)
	    fprintf (outfile, "%c", start + i);
	  else
	    fprintf (outfile, "%d%c", abs (expr[i]), start + i);
	}
    }
}

/* Print out a lambda linear expression structure, EXPR, to OUTFILE. The
   depth/number of coefficients is given by DEPTH, the number of invariants is
   given by INVARIANTS, and the character to start variable names with is given
   by START.  */

void
print_lambda_linear_expression (FILE * outfile,
				lambda_linear_expression expr,
				int depth, int invariants, char start)
{
  fprintf (outfile, "\tLinear expression: ");
  print_linear_expression (outfile, LLE_COEFFICIENTS (expr), depth, start);
  fprintf (outfile, " constant: %d ", LLE_CONSTANT (expr));
  fprintf (outfile, "  invariants: ");
  print_linear_expression (outfile, LLE_INVARIANT_COEFFICIENTS (expr),
			   invariants, 'A');
  fprintf (outfile, "  denominator: %d\n", LLE_DENOMINATOR (expr));
}

/* Print a lambda loop structure LOOP to OUTFILE.  The depth/number of
   coefficients is given by DEPTH, the number of invariants is 
   given by INVARIANTS, and the character to start variable names with is given
   by START.  */

void
print_lambda_loop (FILE * outfile, lambda_loop loop, int depth,
		   int invariants, char start)
{
  int step;
  lambda_linear_expression expr;

  gcc_assert (loop);

  expr = LL_LINEAR_OFFSET (loop);
  step = LL_STEP (loop);
  fprintf (outfile, "  step size = %d \n", step);

  if (expr)
    {
      fprintf (outfile, "  linear offset: \n");
      print_lambda_linear_expression (outfile, expr, depth, invariants,
				      start);
    }

  fprintf (outfile, "  lower bound: \n");
  for (expr = LL_LOWER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
    print_lambda_linear_expression (outfile, expr, depth, invariants, start);
  fprintf (outfile, "  upper bound: \n");
  for (expr = LL_UPPER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
    print_lambda_linear_expression (outfile, expr, depth, invariants, start);
}

/* Create a new loop nest structure with DEPTH loops, and INVARIANTS as the
   number of invariants.  */

lambda_loopnest
lambda_loopnest_new (int depth, int invariants)
{
  lambda_loopnest ret;
  ret = ggc_alloc (sizeof (*ret));

  LN_LOOPS (ret) = ggc_alloc_cleared (depth * sizeof (lambda_loop));
  LN_DEPTH (ret) = depth;
  LN_INVARIANTS (ret) = invariants;

  return ret;
}

/* Print a lambda loopnest structure, NEST, to OUTFILE.  The starting
   character to use for loop names is given by START.  */

void
print_lambda_loopnest (FILE * outfile, lambda_loopnest nest, char start)
{
  int i;
  for (i = 0; i < LN_DEPTH (nest); i++)
    {
      fprintf (outfile, "Loop %c\n", start + i);
      print_lambda_loop (outfile, LN_LOOPS (nest)[i], LN_DEPTH (nest),
			 LN_INVARIANTS (nest), 'i');
      fprintf (outfile, "\n");
    }
}

/* Allocate a new lattice structure of DEPTH x DEPTH, with INVARIANTS number
   of invariants.  */

static lambda_lattice
lambda_lattice_new (int depth, int invariants)
{
  lambda_lattice ret;
  ret = ggc_alloc (sizeof (*ret));
  LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
  LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
  LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
  LATTICE_DIMENSION (ret) = depth;
  LATTICE_INVARIANTS (ret) = invariants;
  return ret;
}

/* Compute the lattice base for NEST.  The lattice base is essentially a
   non-singular transform from a dense base space to a sparse iteration space.
   We use it so that we don't have to specially handle the case of a sparse
   iteration space in other parts of the algorithm.  As a result, this routine
   only does something interesting (IE produce a matrix that isn't the
   identity matrix) if NEST is a sparse space.  */

static lambda_lattice
lambda_lattice_compute_base (lambda_loopnest nest)
{
  lambda_lattice ret;
  int depth, invariants;
  lambda_matrix base;

  int i, j, step;
  lambda_loop loop;
  lambda_linear_expression expression;

  depth = LN_DEPTH (nest);
  invariants = LN_INVARIANTS (nest);

  ret = lambda_lattice_new (depth, invariants);
  base = LATTICE_BASE (ret);
  for (i = 0; i < depth; i++)
    {
      loop = LN_LOOPS (nest)[i];
      gcc_assert (loop);
      step = LL_STEP (loop);
      /* If we have a step of 1, then the base is one, and the
         origin and invariant coefficients are 0.  */
      if (step == 1)
	{
	  for (j = 0; j < depth; j++)
	    base[i][j] = 0;
	  base[i][i] = 1;
	  LATTICE_ORIGIN (ret)[i] = 0;
	  for (j = 0; j < invariants; j++)
	    LATTICE_ORIGIN_INVARIANTS (ret)[i][j] = 0;
	}
      else
	{
	  /* Otherwise, we need the lower bound expression (which must
	     be an affine function)  to determine the base.  */
	  expression = LL_LOWER_BOUND (loop);
	  gcc_assert (expression && !LLE_NEXT (expression) 
		      && LLE_DENOMINATOR (expression) == 1);

	  /* The lower triangular portion of the base is going to be the
	     coefficient times the step */
	  for (j = 0; j < i; j++)
	    base[i][j] = LLE_COEFFICIENTS (expression)[j]
	      * LL_STEP (LN_LOOPS (nest)[j]);
	  base[i][i] = step;
	  for (j = i + 1; j < depth; j++)
	    base[i][j] = 0;

	  /* Origin for this loop is the constant of the lower bound
	     expression.  */
	  LATTICE_ORIGIN (ret)[i] = LLE_CONSTANT (expression);

	  /* Coefficient for the invariants are equal to the invariant
	     coefficients in the expression.  */
	  for (j = 0; j < invariants; j++)
	    LATTICE_ORIGIN_INVARIANTS (ret)[i][j] =
	      LLE_INVARIANT_COEFFICIENTS (expression)[j];
	}
    }
  return ret;
}

/* Compute the greatest common denominator of two numbers (A and B) using
   Euclid's algorithm.  */

static int
gcd (int a, int b)
{

  int x, y, z;

  x = abs (a);
  y = abs (b);

  while (x > 0)
    {
      z = y % x;
      y = x;
      x = z;
    }

  return (y);
}

/* Compute the greatest common denominator of a VECTOR of SIZE numbers.  */

static int
gcd_vector (lambda_vector vector, int size)
{
  int i;
  int gcd1 = 0;

  if (size > 0)
    {
      gcd1 = vector[0];
      for (i = 1; i < size; i++)
	gcd1 = gcd (gcd1, vector[i]);
    }
  return gcd1;
}

/* Compute the least common multiple of two numbers A and B .  */

static int
lcm (int a, int b)
{
  return (abs (a) * abs (b) / gcd (a, b));
}

/* Perform Fourier-Motzkin elimination to calculate the bounds of the
   auxiliary nest.
   Fourier-Motzkin is a way of reducing systems of linear inequalities so that
   it is easy to calculate the answer and bounds.
   A sketch of how it works:
   Given a system of linear inequalities, ai * xj >= bk, you can always
   rewrite the constraints so they are all of the form
   a <= x, or x <= b, or x >= constant for some x in x1 ... xj (and some b
   in b1 ... bk, and some a in a1...ai)
   You can then eliminate this x from the non-constant inequalities by
   rewriting these as a <= b, x >= constant, and delete the x variable.
   You can then repeat this for any remaining x variables, and then we have
   an easy to use variable <= constant (or no variables at all) form that we
   can construct our bounds from. 
   
   In our case, each time we eliminate, we construct part of the bound from
   the ith variable, then delete the ith variable. 
   
   Remember the constant are in our vector a, our coefficient matrix is A,
   and our invariant coefficient matrix is B.
   
   SIZE is the size of the matrices being passed.
   DEPTH is the loop nest depth.
   INVARIANTS is the number of loop invariants.
   A, B, and a are the coefficient matrix, invariant coefficient, and a
   vector of constants, respectively.  */

static lambda_loopnest 
compute_nest_using_fourier_motzkin (int size,
				    int depth, 
				    int invariants,
				    lambda_matrix A,
				    lambda_matrix B,
				    lambda_vector a)
{

  int multiple, f1, f2;
  int i, j, k;
  lambda_linear_expression expression;
  lambda_loop loop;
  lambda_loopnest auxillary_nest;
  lambda_matrix swapmatrix, A1, B1;
  lambda_vector swapvector, a1;
  int newsize;

  A1 = lambda_matrix_new (128, depth);
  B1 = lambda_matrix_new (128, invariants);
  a1 = lambda_vector_new (128);

  auxillary_nest = lambda_loopnest_new (depth, invariants);

  for (i = depth - 1; i >= 0; i--)
    {
      loop = lambda_loop_new ();
      LN_LOOPS (auxillary_nest)[i] = loop;
      LL_STEP (loop) = 1;

      for (j = 0; j < size; j++)
	{
	  if (A[j][i] < 0)
	    {
	      /* Any linear expression in the matrix with a coefficient less
		 than 0 becomes part of the new lower bound.  */ 
	      expression = lambda_linear_expression_new (depth, invariants);

	      for (k = 0; k < i; k++)
		LLE_COEFFICIENTS (expression)[k] = A[j][k];

	      for (k = 0; k < invariants; k++)
		LLE_INVARIANT_COEFFICIENTS (expression)[k] = -1 * B[j][k];

	      LLE_DENOMINATOR (expression) = -1 * A[j][i];
	      LLE_CONSTANT (expression) = -1 * a[j];

	      /* Ignore if identical to the existing lower bound.  */
	      if (!lle_equal (LL_LOWER_BOUND (loop),
			      expression, depth, invariants))
		{
		  LLE_NEXT (expression) = LL_LOWER_BOUND (loop);
		  LL_LOWER_BOUND (loop) = expression;
		}

	    }
	  else if (A[j][i] > 0)
	    {
	      /* Any linear expression with a coefficient greater than 0
		 becomes part of the new upper bound.  */ 
	      expression = lambda_linear_expression_new (depth, invariants);
	      for (k = 0; k < i; k++)
		LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k];

	      for (k = 0; k < invariants; k++)
		LLE_INVARIANT_COEFFICIENTS (expression)[k] = B[j][k];

	      LLE_DENOMINATOR (expression) = A[j][i];
	      LLE_CONSTANT (expression) = a[j];

	      /* Ignore if identical to the existing upper bound.  */
	      if (!lle_equal (LL_UPPER_BOUND (loop),
			      expression, depth, invariants))
		{
		  LLE_NEXT (expression) = LL_UPPER_BOUND (loop);
		  LL_UPPER_BOUND (loop) = expression;
		}

	    }
	}

      /* This portion creates a new system of linear inequalities by deleting
	 the i'th variable, reducing the system by one variable.  */
      newsize = 0;
      for (j = 0; j < size; j++)
	{
	  /* If the coefficient for the i'th variable is 0, then we can just
	     eliminate the variable straightaway.  Otherwise, we have to
	     multiply through by the coefficients we are eliminating.  */
	  if (A[j][i] == 0)
	    {
	      lambda_vector_copy (A[j], A1[newsize], depth);
	      lambda_vector_copy (B[j], B1[newsize], invariants);
	      a1[newsize] = a[j];
	      newsize++;
	    }
	  else if (A[j][i] > 0)
	    {
	      for (k = 0; k < size; k++)
		{
		  if (A[k][i] < 0)
		    {
		      multiple = lcm (A[j][i], A[k][i]);
		      f1 = multiple / A[j][i];
		      f2 = -1 * multiple / A[k][i];

		      lambda_vector_add_mc (A[j], f1, A[k], f2,
					    A1[newsize], depth);
		      lambda_vector_add_mc (B[j], f1, B[k], f2,
					    B1[newsize], invariants);
		      a1[newsize] = f1 * a[j] + f2 * a[k];
		      newsize++;
		    }
		}
	    }
	}

      swapmatrix = A;
      A = A1;
      A1 = swapmatrix;

      swapmatrix = B;
      B = B1;
      B1 = swapmatrix;

      swapvector = a;
      a = a1;
      a1 = swapvector;

      size = newsize;
    }

  return auxillary_nest;
}

/* Compute the loop bounds for the auxiliary space NEST.
   Input system used is Ax <= b.  TRANS is the unimodular transformation.  
   Given the original nest, this function will 
   1. Convert the nest into matrix form, which consists of a matrix for the
   coefficients, a matrix for the 
   invariant coefficients, and a vector for the constants.  
   2. Use the matrix form to calculate the lattice base for the nest (which is
   a dense space) 
   3. Compose the dense space transform with the user specified transform, to 
   get a transform we can easily calculate transformed bounds for.
   4. Multiply the composed transformation matrix times the matrix form of the
   loop.
   5. Transform the newly created matrix (from step 4) back into a loop nest
   using fourier motzkin elimination to figure out the bounds.  */

static lambda_loopnest
lambda_compute_auxillary_space (lambda_loopnest nest,
				lambda_trans_matrix trans)
{
  lambda_matrix A, B, A1, B1;
  lambda_vector a, a1;
  lambda_matrix invertedtrans;
  int depth, invariants, size;
  int i, j;
  lambda_loop loop;
  lambda_linear_expression expression;
  lambda_lattice lattice;

  depth = LN_DEPTH (nest);
  invariants = LN_INVARIANTS (nest);

  /* 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_vector_new (128);

  A1 = lambda_matrix_new (128, depth);
  B1 = lambda_matrix_new (128, invariants);
  a1 = lambda_vector_new (128);

  /* Store the bounds in the equation matrix A, constant vector a, and
     invariant matrix B, so that we have Ax <= a + B.
     This requires a little equation rearranging so that everything is on the
     correct side of the inequality.  */
  size = 0;
  for (i = 0; i < depth; i++)
    {
      loop = LN_LOOPS (nest)[i];

      /* First we do the lower bound.  */
      if (LL_STEP (loop) > 0)
	expression = LL_LOWER_BOUND (loop);
      else
	expression = LL_UPPER_BOUND (loop);

      for (; expression != NULL; expression = LLE_NEXT (expression))
	{
	  /* Fill in the coefficient.  */
	  for (j = 0; j < i; j++)
	    A[size][j] = LLE_COEFFICIENTS (expression)[j];

	  /* And the invariant coefficient.  */
	  for (j = 0; j < invariants; j++)
	    B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];

	  /* And the constant.  */
	  a[size] = LLE_CONSTANT (expression);

	  /* Convert (2x+3y+2+b)/4 <= z to 2x+3y-4z <= -2-b.  IE put all
	     constants and single variables on   */
	  A[size][i] = -1 * LLE_DENOMINATOR (expression);
	  a[size] *= -1;
	  for (j = 0; j < invariants; j++)
	    B[size][j] *= -1;

	  size++;
	  /* Need to increase matrix sizes above.  */
	  gcc_assert (size <= 127);
	  
	}

      /* Then do the exact same thing for the upper bounds.  */
      if (LL_STEP (loop) > 0)
	expression = LL_UPPER_BOUND (loop);
      else
	expression = LL_LOWER_BOUND (loop);

      for (; expression != NULL; expression = LLE_NEXT (expression))
	{
	  /* Fill in the coefficient.  */
	  for (j = 0; j < i; j++)
	    A[size][j] = LLE_COEFFICIENTS (expression)[j];

	  /* And the invariant coefficient.  */
	  for (j = 0; j < invariants; j++)
	    B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];

	  /* And the constant.  */
	  a[size] = LLE_CONSTANT (expression);

	  /* Convert z <= (2x+3y+2+b)/4 to -2x-3y+4z <= 2+b.  */
	  for (j = 0; j < i; j++)
	    A[size][j] *= -1;
	  A[size][i] = LLE_DENOMINATOR (expression);
	  size++;
	  /* Need to increase matrix sizes above.  */
	  gcc_assert (size <= 127);

	}
    }

  /* Compute the lattice base x = base * y + origin, where y is the
     base space.  */
  lattice = lambda_lattice_compute_base (nest);

  /* Ax <= a + B then becomes ALy <= a+B - A*origin.  L is the lattice base  */

  /* A1 = A * L */
  lambda_matrix_mult (A, LATTICE_BASE (lattice), A1, size, depth, depth);

  /* a1 = a - A * origin constant.  */
  lambda_matrix_vector_mult (A, size, depth, LATTICE_ORIGIN (lattice), a1);
  lambda_vector_add_mc (a, 1, a1, -1, a1, size);

  /* B1 = B - A * origin invariant.  */
  lambda_matrix_mult (A, LATTICE_ORIGIN_INVARIANTS (lattice), B1, size, depth,
		      invariants);
  lambda_matrix_add_mc (B, 1, B1, -1, B1, size, invariants);

  /* Now compute the auxiliary space bounds by first inverting U, multiplying
     it by A1, then performing fourier motzkin.  */

  invertedtrans = lambda_matrix_new (depth, depth);

  /* Compute the inverse of U.  */
  lambda_matrix_inverse (LTM_MATRIX (trans),
			 invertedtrans, depth);

  /* A = A1 inv(U).  */
  lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);

  return compute_nest_using_fourier_motzkin (size, depth, invariants,
					     A, B1, a1);
}

/* Compute the loop bounds for the target space, using the bounds of
   the auxiliary nest AUXILLARY_NEST, and the triangular matrix H.  
   The target space loop bounds are computed by multiplying the triangular
   matrix H by the auxiliary nest, to get the new loop bounds.  The sign of
   the loop steps (positive or negative) is then used to swap the bounds if
   the loop counts downwards.
   Return the target loopnest.  */

static lambda_loopnest
lambda_compute_target_space (lambda_loopnest auxillary_nest,
			     lambda_trans_matrix H, lambda_vector stepsigns)
{
  lambda_matrix inverse, H1;
  int determinant, i, j;
  int gcd1, gcd2;
  int factor;

  lambda_loopnest target_nest;
  int depth, invariants;
  lambda_matrix target;

  lambda_loop auxillary_loop, target_loop;
  lambda_linear_expression expression, auxillary_expr, target_expr, tmp_expr;

  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);

  /* H1 is H excluding its diagonal.  */
  H1 = lambda_matrix_new (depth, depth);
  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);
  lambda_matrix_mult (H1, inverse, target, depth, depth, depth);

  target_nest = lambda_loopnest_new (depth, invariants);

  for (i = 0; i < depth; i++)
    {

      /* Get a new loop structure.  */
      target_loop = lambda_loop_new ();
      LN_LOOPS (target_nest)[i] = target_loop;

      /* Computes the gcd of the coefficients of the linear part.  */
      gcd1 = gcd_vector (target[i], i);

      /* Include the denominator in the GCD.  */
      gcd1 = gcd (gcd1, determinant);

      /* Now divide through by the gcd.  */
      for (j = 0; j < i; j++)
	target[i][j] = target[i][j] / gcd1;

      expression = lambda_linear_expression_new (depth, invariants);
      lambda_vector_copy (target[i], LLE_COEFFICIENTS (expression), depth);
      LLE_DENOMINATOR (expression) = determinant / gcd1;
      LLE_CONSTANT (expression) = 0;
      lambda_vector_clear (LLE_INVARIANT_COEFFICIENTS (expression),
			   invariants);
      LL_LINEAR_OFFSET (target_loop) = expression;
    }

  /* For each loop, compute the new bounds from H.  */
  for (i = 0; i < depth; i++)
    {
      auxillary_loop = LN_LOOPS (auxillary_nest)[i];
      target_loop = LN_LOOPS (target_nest)[i];
      LL_STEP (target_loop) = LTM_MATRIX (H)[i][i];
      factor = LTM_MATRIX (H)[i][i];

      /* First we do the lower bound.  */
      auxillary_expr = LL_LOWER_BOUND (auxillary_loop);

      for (; auxillary_expr != NULL;
	   auxillary_expr = LLE_NEXT (auxillary_expr))
	{
	  target_expr = lambda_linear_expression_new (depth, invariants);
	  lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
				     depth, inverse, depth,
				     LLE_COEFFICIENTS (target_expr));
	  lambda_vector_mult_const (LLE_COEFFICIENTS (target_expr),
				    LLE_COEFFICIENTS (target_expr), depth,
				    factor);

	  LLE_CONSTANT (target_expr) = LLE_CONSTANT (auxillary_expr) * factor;
	  lambda_vector_copy (LLE_INVARIANT_COEFFICIENTS (auxillary_expr),
			      LLE_INVARIANT_COEFFICIENTS (target_expr),
			      invariants);
	  lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr),
				    LLE_INVARIANT_COEFFICIENTS (target_expr),
				    invariants, factor);
	  LLE_DENOMINATOR (target_expr) = LLE_DENOMINATOR (auxillary_expr);

	  if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr), depth))
	    {
	      LLE_CONSTANT (target_expr) = LLE_CONSTANT (target_expr)
		* determinant;
	      lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
					(target_expr),
					LLE_INVARIANT_COEFFICIENTS
					(target_expr), invariants,
					determinant);
	      LLE_DENOMINATOR (target_expr) =
		LLE_DENOMINATOR (target_expr) * determinant;
	    }
	  /* Find the gcd and divide by it here, rather than doing it
	     at the tree level.  */
	  gcd1 = gcd_vector (LLE_COEFFICIENTS (target_expr), depth);
	  gcd2 = gcd_vector (LLE_INVARIANT_COEFFICIENTS (target_expr),
			     invariants);
	  gcd1 = gcd (gcd1, gcd2);
	  gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
	  gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
	  for (j = 0; j < depth; j++)
	    LLE_COEFFICIENTS (target_expr)[j] /= gcd1;
	  for (j = 0; j < invariants; j++)
	    LLE_INVARIANT_COEFFICIENTS (target_expr)[j] /= gcd1;
	  LLE_CONSTANT (target_expr) /= gcd1;
	  LLE_DENOMINATOR (target_expr) /= gcd1;
	  /* Ignore if identical to existing bound.  */
	  if (!lle_equal (LL_LOWER_BOUND (target_loop), target_expr, depth,
			  invariants))
	    {
	      LLE_NEXT (target_expr) = LL_LOWER_BOUND (target_loop);
	      LL_LOWER_BOUND (target_loop) = target_expr;
	    }
	}
      /* Now do the upper bound.  */
      auxillary_expr = LL_UPPER_BOUND (auxillary_loop);

      for (; auxillary_expr != NULL;
	   auxillary_expr = LLE_NEXT (auxillary_expr))
	{
	  target_expr = lambda_linear_expression_new (depth, invariants);
	  lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
				     depth, inverse, depth,
				     LLE_COEFFICIENTS (target_expr));
	  lambda_vector_mult_const (LLE_COEFFICIENTS (target_expr),
				    LLE_COEFFICIENTS (target_expr), depth,
				    factor);
	  LLE_CONSTANT (target_expr) = LLE_CONSTANT (auxillary_expr) * factor;
	  lambda_vector_copy (LLE_INVARIANT_COEFFICIENTS (auxillary_expr),
			      LLE_INVARIANT_COEFFICIENTS (target_expr),
			      invariants);
	  lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr),
				    LLE_INVARIANT_COEFFICIENTS (target_expr),
				    invariants, factor);
	  LLE_DENOMINATOR (target_expr) = LLE_DENOMINATOR (auxillary_expr);

	  if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr), depth))
	    {
	      LLE_CONSTANT (target_expr) = LLE_CONSTANT (target_expr)
		* determinant;
	      lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
					(target_expr),
					LLE_INVARIANT_COEFFICIENTS
					(target_expr), invariants,
					determinant);
	      LLE_DENOMINATOR (target_expr) =
		LLE_DENOMINATOR (target_expr) * determinant;
	    }
	  /* Find the gcd and divide by it here, instead of at the
	     tree level.  */
	  gcd1 = gcd_vector (LLE_COEFFICIENTS (target_expr), depth);
	  gcd2 = gcd_vector (LLE_INVARIANT_COEFFICIENTS (target_expr),
			     invariants);
	  gcd1 = gcd (gcd1, gcd2);
	  gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
	  gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
	  for (j = 0; j < depth; j++)
	    LLE_COEFFICIENTS (target_expr)[j] /= gcd1;
	  for (j = 0; j < invariants; j++)
	    LLE_INVARIANT_COEFFICIENTS (target_expr)[j] /= gcd1;
	  LLE_CONSTANT (target_expr) /= gcd1;
	  LLE_DENOMINATOR (target_expr) /= gcd1;
	  /* Ignore if equal to existing bound.  */
	  if (!lle_equal (LL_UPPER_BOUND (target_loop), target_expr, depth,
			  invariants))
	    {
	      LLE_NEXT (target_expr) = LL_UPPER_BOUND (target_loop);
	      LL_UPPER_BOUND (target_loop) = target_expr;
	    }
	}
    }
  for (i = 0; i < depth; i++)
    {
      target_loop = LN_LOOPS (target_nest)[i];
      /* If necessary, exchange the upper and lower bounds and negate
         the step size.  */
      if (stepsigns[i] < 0)
	{
	  LL_STEP (target_loop) *= -1;
	  tmp_expr = LL_LOWER_BOUND (target_loop);
	  LL_LOWER_BOUND (target_loop) = LL_UPPER_BOUND (target_loop);
	  LL_UPPER_BOUND (target_loop) = tmp_expr;
	}
    }
  return target_nest;
}

/* Compute the step signs of TRANS, using TRANS and stepsigns.  Return the new
   result.  */

static lambda_vector
lambda_compute_step_signs (lambda_trans_matrix trans, lambda_vector stepsigns)
{
  lambda_matrix matrix, H;
  int size;
  lambda_vector newsteps;
  int i, j, factor, minimum_column;
  int temp;

  matrix = LTM_MATRIX (trans);
  size = LTM_ROWSIZE (trans);
  H = lambda_matrix_new (size, size);

  newsteps = lambda_vector_new (size);
  lambda_vector_copy (stepsigns, newsteps, size);

  lambda_matrix_copy (matrix, H, size, size);

  for (j = 0; j < size; j++)
    {
      lambda_vector row;
      row = H[j];
      for (i = j; i < size; i++)
	if (row[i] < 0)
	  lambda_matrix_col_negate (H, size, i);
      while (lambda_vector_first_nz (row, size, j + 1) < size)
	{
	  minimum_column = lambda_vector_min_nz (row, size, j);
	  lambda_matrix_col_exchange (H, size, j, minimum_column);

	  temp = newsteps[j];
	  newsteps[j] = newsteps[minimum_column];
	  newsteps[minimum_column] = temp;

	  for (i = j + 1; i < size; i++)
	    {
	      factor = row[i] / row[j];
	      lambda_matrix_col_add (H, size, j, i, -1 * factor);
	    }
	}
    }
  return newsteps;
}

/* Transform NEST according to TRANS, and return the new loopnest.
   This involves
   1. Computing a lattice base for the transformation
   2. Composing the dense base with the specified transformation (TRANS)
   3. Decomposing the combined transformation into a lower triangular portion,
   and a unimodular portion. 
   4. Computing the auxiliary nest using the unimodular portion.
   5. Computing the target nest using the auxiliary nest and the lower
   triangular portion.  */ 

lambda_loopnest
lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans)
{
  lambda_loopnest auxillary_nest, target_nest;

  int depth, invariants;
  int i, j;
  lambda_lattice lattice;
  lambda_trans_matrix trans1, H, U;
  lambda_loop loop;
  lambda_linear_expression expression;
  lambda_vector origin;
  lambda_matrix origin_invariants;
  lambda_vector stepsigns;
  int f;

  depth = LN_DEPTH (nest);
  invariants = LN_INVARIANTS (nest);

  /* Keep track of the signs of the loop steps.  */
  stepsigns = lambda_vector_new (depth);
  for (i = 0; i < depth; i++)
    {
      if (LL_STEP (LN_LOOPS (nest)[i]) > 0)
	stepsigns[i] = 1;
      else
	stepsigns[i] = -1;
    }

  /* Compute the lattice base.  */
  lattice = lambda_lattice_compute_base (nest);
  trans1 = lambda_trans_matrix_new (depth, depth);

  /* Multiply the transformation matrix by the lattice base.  */

  lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_BASE (lattice),
		      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);
  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);

  /* Compute the loop step signs from the old step signs and the
     transformation matrix.  */
  stepsigns = lambda_compute_step_signs (trans1, stepsigns);

  /* 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);
  origin = lambda_vector_new (depth);
  origin_invariants = lambda_matrix_new (depth, invariants);
  lambda_matrix_vector_mult (LTM_MATRIX (trans), depth, depth,
			     LATTICE_ORIGIN (lattice), origin);
  lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_ORIGIN_INVARIANTS (lattice),
		      origin_invariants, depth, depth, invariants);

  for (i = 0; i < depth; i++)
    {
      loop = LN_LOOPS (target_nest)[i];
      expression = LL_LINEAR_OFFSET (loop);
      if (lambda_vector_zerop (LLE_COEFFICIENTS (expression), depth))
	f = 1;
      else
	f = LLE_DENOMINATOR (expression);

      LLE_CONSTANT (expression) += f * origin[i];

      for (j = 0; j < invariants; j++)
	LLE_INVARIANT_COEFFICIENTS (expression)[j] +=
	  f * origin_invariants[i][j];
    }

  return target_nest;

}

/* Convert a gcc tree expression EXPR to a lambda linear expression, and
   return the new expression.  DEPTH is the depth of the loopnest.
   OUTERINDUCTIONVARS is an array of the induction variables for outer loops
   in this nest.  INVARIANTS is the array of invariants for the loop.  EXTRA
   is the amount we have to add/subtract from the expression because of the
   type of comparison it is used in.  */

static lambda_linear_expression
gcc_tree_to_linear_expression (int depth, tree expr,
			       VEC(tree,heap) *outerinductionvars,
			       VEC(tree,heap) *invariants, int extra)
{
  lambda_linear_expression lle = NULL;
  switch (TREE_CODE (expr))
    {
    case INTEGER_CST:
      {
	lle = lambda_linear_expression_new (depth, 2 * depth);
	LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr);
	if (extra != 0)
	  LLE_CONSTANT (lle) += extra;

	LLE_DENOMINATOR (lle) = 1;
      }
      break;
    case SSA_NAME:
      {
	tree iv, invar;
	size_t i;
	for (i = 0; VEC_iterate (tree, outerinductionvars, i, iv); i++)
	  if (iv != NULL)
	    {
	      if (SSA_NAME_VAR (iv) == SSA_NAME_VAR (expr))
		{
		  lle = lambda_linear_expression_new (depth, 2 * depth);
		  LLE_COEFFICIENTS (lle)[i] = 1;
		  if (extra != 0)
		    LLE_CONSTANT (lle) = extra;

		  LLE_DENOMINATOR (lle) = 1;
		}
	    }
	for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
	  if (invar != NULL)
	    {
	      if (SSA_NAME_VAR (invar) == SSA_NAME_VAR (expr))
		{
		  lle = lambda_linear_expression_new (depth, 2 * depth);
		  LLE_INVARIANT_COEFFICIENTS (lle)[i] = 1;
		  if (extra != 0)
		    LLE_CONSTANT (lle) = extra;
		  LLE_DENOMINATOR (lle) = 1;
		}
	    }
      }
      break;
    default:
      return NULL;
    }

  return lle;
}

/* Return the depth of the loopnest NEST */

static int 
depth_of_nest (struct loop *nest)
{
  size_t depth = 0;
  while (nest)
    {
      depth++;
      nest = nest->inner;
    }
  return depth;
}


/* Return true if OP is invariant in LOOP and all outer loops.  */

static bool
invariant_in_loop_and_outer_loops (struct loop *loop, tree op)
{
  if (is_gimple_min_invariant (op))
    return true;
  if (loop->depth == 0)
    return true;
  if (!expr_invariant_in_loop_p (loop, op))
    return false;
  if (loop->outer 
      && !invariant_in_loop_and_outer_loops (loop->outer, op))
    return false;
  return true;
}

/* Generate a lambda loop from a gcc loop LOOP.  Return the new lambda loop,
   or NULL if it could not be converted.
   DEPTH is the depth of the loop.
   INVARIANTS is a pointer to the array of loop invariants.
   The induction variable for this loop should be stored in the parameter
   OURINDUCTIONVAR.
   OUTERINDUCTIONVARS is an array of induction variables for outer loops.  */

static lambda_loop
gcc_loop_to_lambda_loop (struct loop *loop, int depth,
			 VEC(tree,heap) ** invariants,
			 tree * ourinductionvar,
			 VEC(tree,heap) * outerinductionvars,
			 VEC(tree,heap) ** lboundvars,
			 VEC(tree,heap) ** uboundvars,
			 VEC(int,heap) ** steps)
{
  tree phi;
  tree exit_cond;
  tree access_fn, inductionvar;
  tree step;
  lambda_loop lloop = NULL;
  lambda_linear_expression lbound, ubound;
  tree test;
  int stepint;
  int extra = 0;
  tree lboundvar, uboundvar, uboundresult;

  /* Find out induction var and exit condition.  */
  inductionvar = find_induction_var_from_exit_cond (loop);
  exit_cond = get_loop_exit_condition (loop);

  if (inductionvar == NULL || exit_cond == NULL)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Cannot determine exit condition or induction variable for loop.\n");
      return NULL;
    }

  test = TREE_OPERAND (exit_cond, 0);

  if (SSA_NAME_DEF_STMT (inductionvar) == NULL_TREE)
    {

      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Cannot find PHI node for induction variable\n");

      return NULL;
    }

  phi = SSA_NAME_DEF_STMT (inductionvar);
  if (TREE_CODE (phi) != PHI_NODE)
    {
      phi = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE);
      if (!phi)
	{

	  if (dump_file && (dump_flags & TDF_DETAILS))
	    fprintf (dump_file,
		     "Unable to convert loop: Cannot find PHI node for induction variable\n");

	  return NULL;
	}

      phi = SSA_NAME_DEF_STMT (phi);
      if (TREE_CODE (phi) != PHI_NODE)
	{

	  if (dump_file && (dump_flags & TDF_DETAILS))
	    fprintf (dump_file,
		     "Unable to convert loop: Cannot find PHI node for induction variable\n");
	  return NULL;
	}

    }

  /* The induction variable name/version we want to put in the array is the
     result of the induction variable phi node.  */
  *ourinductionvar = PHI_RESULT (phi);
  access_fn = instantiate_parameters
    (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
  if (access_fn == chrec_dont_know)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Access function for induction variable phi is unknown\n");

      return NULL;
    }

  step = evolution_part_in_loop_num (access_fn, loop->num);
  if (!step || step == chrec_dont_know)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Cannot determine step of loop.\n");

      return NULL;
    }
  if (TREE_CODE (step) != INTEGER_CST)
    {

      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Step of loop is not integer.\n");
      return NULL;
    }

  stepint = TREE_INT_CST_LOW (step);

  /* Only want phis for induction vars, which will have two
     arguments.  */
  if (PHI_NUM_ARGS (phi) != 2)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: PHI node for induction variable has >2 arguments\n");
      return NULL;
    }

  /* Another induction variable check. One argument's source should be
     in the loop, one outside the loop.  */
  if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src)
      && flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 1)->src))
    {

      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: PHI edges both inside loop, or both outside loop.\n");

      return NULL;
    }

  if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src))
    {
      lboundvar = PHI_ARG_DEF (phi, 1);
      lbound = gcc_tree_to_linear_expression (depth, lboundvar,
					      outerinductionvars, *invariants,
					      0);
    }
  else
    {
      lboundvar = PHI_ARG_DEF (phi, 0);
      lbound = gcc_tree_to_linear_expression (depth, lboundvar,
					      outerinductionvars, *invariants,
					      0);
    }
  
  if (!lbound)
    {

      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Cannot convert lower bound to linear expression\n");

      return NULL;
    }
  /* One part of the test may be a loop invariant tree.  */
  VEC_reserve (tree, heap, *invariants, 1);
  if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME
      && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 1)))
    VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 1));
  else if (TREE_CODE (TREE_OPERAND (test, 0)) == SSA_NAME
	   && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 0)))
    VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 0));
  
  /* The non-induction variable part of the test is the upper bound variable.
   */
  if (TREE_OPERAND (test, 0) == inductionvar)
    uboundvar = TREE_OPERAND (test, 1);
  else
    uboundvar = TREE_OPERAND (test, 0);
    

  /* We only size the vectors assuming we have, at max, 2 times as many
     invariants as we do loops (one for each bound).
     This is just an arbitrary number, but it has to be matched against the
     code below.  */
  gcc_assert (VEC_length (tree, *invariants) <= (unsigned int) (2 * depth));
  

  /* We might have some leftover.  */
  if (TREE_CODE (test) == LT_EXPR)
    extra = -1 * stepint;
  else if (TREE_CODE (test) == NE_EXPR)
    extra = -1 * stepint;
  else if (TREE_CODE (test) == GT_EXPR)
    extra = -1 * stepint;
  else if (TREE_CODE (test) == EQ_EXPR)
    extra = 1 * stepint;
  
  ubound = gcc_tree_to_linear_expression (depth, uboundvar,
					  outerinductionvars,
					  *invariants, extra);
  uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
			build_int_cst (TREE_TYPE (uboundvar), extra));
  VEC_safe_push (tree, heap, *uboundvars, uboundresult);
  VEC_safe_push (tree, heap, *lboundvars, lboundvar);
  VEC_safe_push (int, heap, *steps, stepint);
  if (!ubound)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Unable to convert loop: Cannot convert upper bound to linear expression\n");
      return NULL;
    }

  lloop = lambda_loop_new ();
  LL_STEP (lloop) = stepint;
  LL_LOWER_BOUND (lloop) = lbound;
  LL_UPPER_BOUND (lloop) = ubound;
  return lloop;
}

/* Given a LOOP, find the induction variable it is testing against in the exit
   condition.  Return the induction variable if found, NULL otherwise.  */

static tree
find_induction_var_from_exit_cond (struct loop *loop)
{
  tree expr = get_loop_exit_condition (loop);
  tree ivarop;
  tree test;
  if (expr == NULL_TREE)
    return NULL_TREE;
  if (TREE_CODE (expr) != COND_EXPR)
    return NULL_TREE;
  test = TREE_OPERAND (expr, 0);
  if (!COMPARISON_CLASS_P (test))
    return NULL_TREE;

  /* Find the side that is invariant in this loop. The ivar must be the other
     side.  */
  
  if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 0)))
      ivarop = TREE_OPERAND (test, 1);
  else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1)))
      ivarop = TREE_OPERAND (test, 0);
  else
    return NULL_TREE;

  if (TREE_CODE (ivarop) != SSA_NAME)
    return NULL_TREE;
  return ivarop;
}

DEF_VEC_P(lambda_loop);
DEF_VEC_ALLOC_P(lambda_loop,heap);

/* Generate a lambda loopnest from a gcc loopnest LOOP_NEST.
   Return the new loop nest.  
   INDUCTIONVARS is a pointer to an array of induction variables for the
   loopnest that will be filled in during this process.
   INVARIANTS is a pointer to an array of invariants that will be filled in
   during this process.  */

lambda_loopnest
gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
				 struct loop * loop_nest,
				 VEC(tree,heap) **inductionvars,
				 VEC(tree,heap) **invariants,
				 bool need_perfect_nest)
{
  lambda_loopnest ret = NULL;
  struct loop *temp;
  int depth = 0;
  size_t i;
  VEC(lambda_loop,heap) *loops = NULL;
  VEC(tree,heap) *uboundvars = NULL;
  VEC(tree,heap) *lboundvars  = NULL;
  VEC(int,heap) *steps = NULL;
  lambda_loop newloop;
  tree inductionvar = NULL;
  
  depth = depth_of_nest (loop_nest);
  temp = loop_nest;
  while (temp)
    {
      newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
					 &inductionvar, *inductionvars,
					 &lboundvars, &uboundvars,
					 &steps);
      if (!newloop)
	return NULL;
      VEC_safe_push (tree, heap, *inductionvars, inductionvar);
      VEC_safe_push (lambda_loop, heap, loops, newloop);
      temp = temp->inner;
    }
  if (need_perfect_nest)
    {
      if (!perfect_nestify (currloops, loop_nest,
ofs	hex dump	ascii
0000	ca fe ba be 00 00 00 31 00 59 07 00 02 01 00 13 6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d 61	.......1.Y......java/util/EnumMa
0020	70 24 36 07 00 04 01 00 10 6a 61 76 61 2f 6c 61 6e 67 2f 4f 62 6a 65 63 74 07 00 06 01 00 12 6a	p$6......java/lang/Object......j
0040	61 76 61 2f 75 74 69 6c 2f 49 74 65 72 61 74 6f 72 01 00 05 63 6f 75 6e 74 01 00 01 49 01 00 05	ava/util/Iterator...count...I...
0060	69 6e 64 65 78 01 00 06 74 68 69 73 24 31 01 00 15 4c 6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d	index...this$1...Ljava/util/Enum
0080	4d 61 70 24 35 3b 01 00 06 3c 69 6e 69 74 3e 01 00 18 28 4c 6a 61 76 61 2f 75 74 69 6c 2f 45 6e	Map$5;...<init>...(Ljava/util/En
00a0	75 6d 4d 61 70 24 35 3b 29 56 01 00 04 43 6f 64 65 09 00 01 00 10 0c 00 0a 00 0b 0a 00 03 00 12	umMap$5;)V...Code...............
00c0	0c 00 0c 00 13 01 00 03 28 29 56 09 00 01 00 15 0c 00 07 00 08 09 00 01 00 17 0c 00 09 00 08 01	........()V.....................
00e0	00 0f 4c 69 6e 65 4e 75 6d 62 65 72 54 61 62 6c 65 01 00 12 4c 6f 63 61 6c 56 61 72 69 61 62 6c	..LineNumberTable...LocalVariabl
0100	65 54 61 62 6c 65 01 00 04 74 68 69 73 01 00 15 4c 6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d	eTable...this...Ljava/util/EnumM
0120	61 70 24 36 3b 01 00 07 68 61 73 4e 65 78 74 01 00 03 28 29 5a 0a 00 1f 00 21 07 00 20 01 00 13	ap$6;...hasNext...()Z....!......
0140	6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d 61 70 24 35 0c 00 22 00 23 01 00 08 61 63 63 65 73	java/util/EnumMap$5..".#...acces
0160	73 24 30 01 00 2a 28 4c 6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d 61 70 24 35 3b 29 4c 6a 61	s$0..*(Ljava/util/EnumMap$5;)Lja
0180	76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d 61 70 3b 09 00 25 00 27 07 00 26 01 00 11 6a 61 76 61 2f	va/util/EnumMap;..%.'..&...java/
01a0	75 74 69 6c 2f 45 6e 75 6d 4d 61 70 0c 00 28 00 08 01 00 0b 63 61 72 64 69 6e 61 6c 69 74 79 01	util/EnumMap..(.....cardinality.
01c0	00 04 6e 65 78 74 01 00 17 28 29 4c 6a 61 76 61 2f 75 74 69 6c 2f 4d 61 70 24 45 6e 74 72 79 3b	..next...()Ljava/util/Map$Entry;
01e0	01 00 09 53 69 67 6e 61 74 75 72 65 01 00 1f 28 29 4c 6a 61 76 61 2f 75 74 69 6c 2f 4d 61 70 24	...Signature...()Ljava/util/Map$
0200	45 6e 74 72 79 3c 54 4b 3b 54 56 3b 3e 3b 09 00 25 00 2e 0c 00 2f 00 30 01 00 05 73 74 6f 72 65	Entry<TK;TV;>;..%..../.0...store
0220	01 00 13 5b 4c 6a 61 76 61 2f 6c 61 6e 67 2f 4f 62 6a 65 63 74 3b 09 00 25 00 32 0c 00 33 00 34	...[Ljava/lang/Object;..%.2..3.4
0240	01 00 09 65 6d 70 74 79 53 6c 6f 74 01 00 12 4c 6a 61 76 61 2f 6c 61 6e 67 2f 4f 62 6a 65 63 74	...emptySlot...Ljava/lang/Object
0260	3b 07 00 36 01 00 13 6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d 61 70 24 37 09 00 25 00 38 0c	;..6...java/util/EnumMap$7..%.8.
0280	00 39 00 3a 01 00 09 65 6e 75 6d 43 6c 61 73 73 01 00 11 4c 6a 61 76 61 2f 6c 61 6e 67 2f 43 6c	.9.:...enumClass...Ljava/lang/Cl
02a0	61 73 73 3b 0a 00 3c 00 3e 07 00 3d 01 00 0f 6a 61 76 61 2f 6c 61 6e 67 2f 43 6c 61 73 73 0c 00	ass;..<.>..=...java/lang/Class..
02c0	3f 00 40 01 00 10 67 65 74 45 6e 75 6d 43 6f 6e 73 74 61 6e 74 73 01 00 15 28 29 5b 4c 6a 61 76	?.@...getEnumConstants...()[Ljav
02e0	61 2f 6c 61 6e 67 2f 4f 62 6a 65 63 74 3b 07 00 42 01 00 11 5b 4c 6a 61 76 61 2f 6c 61 6e 67 2f	a/lang/Object;..B...[Ljava/lang/
0300	45 6e 75 6d 3b 0a 00 35 00 44 0c 00 0c 00 45 01 00 3a 28 4c 6a 61 76 61 2f 75 74 69 6c 2f 45 6e	Enum;..5.D....E..:(Ljava/util/En
0320	75 6d 4d 61 70 24 36 3b 4c 6a 61 76 61 2f 6c 61 6e 67 2f 45 6e 75 6d 3b 4c 6a 61 76 61 2f 6c 61	umMap$6;Ljava/lang/Enum;Ljava/la
0340	6e 67 2f 4f 62 6a 65 63 74 3b 29 56 01 00 06 72 65 6d 6f 76 65 01 00 14 28 29 4c 6a 61 76 61 2f	ng/Object;)V...remove...()Ljava/
0360	6c 61 6e 67 2f 4f 62 6a 65 63 74 3b 0a 00 01 00 49 0c 00 29 00 2a 01 00 08 61 63 63 65 73 73 24	lang/Object;....I..).*...access$
0380	31 01 00 2c 28 4c 6a 61 76 61 2f 75 74 69 6c 2f 45 6e 75 6d 4d 61 70 24 36 3b 29 4c 6a 61 76 61	1..,(Ljava/util/EnumMap$6;)Ljava
03a0	2f 75 74 69 6c 2f 45 6e 75 6d 4d 61 70 24 35 3b 01 00 0a 53 6f 75 72 63 65 46 69 6c 65 01 00 0c	/util/EnumMap$5;...SourceFile...
03c0	45 6e 75 6d 4d 61 70 2e 6a 61 76 61 01 00 45 4c 6a 61 76 61 2f 6c 61 6e 67 2f 4f 62 6a 65 63 74	EnumMap.java..ELjava/lang/Object
03e0	3b 4c 6a 61 76 61 2f 75 74 69 6c 2f 49 74 65 72 61 74 6f 72 3c 4c 6a 61 76 61 2f 75 74 69 6c 2f	;Ljava/util/Iterator<Ljava/util/
0400	4d 61 70 24 45 6e 74 72 79 3c 54 4b 3b 54 56 3b 3e 3b 3e 3b 01 00 0f 45 6e 63 6c 6f 73 69 6e 67	Map$Entry<TK;TV;>;>;...Enclosing
0420	4d 65 74 68 6f 64 0c 00 51 00 52 01 00 08 69 74 65 72 61 74 6f 72 01 00 16 28 29 4c 6a 61 76 61	Method..Q.R...iterator...()Ljava
0440	2f 75 74 69 6c 2f 49 74 65 72 61 74 6f 72 3b 01 00 0c 49 6e 6e 65 72 43 6c 61 73 73 65 73 07 00	/util/Iterator;...InnerClasses..
0460	55 01 00 13 6a 61 76 61 2f 75 74 69 6c 2f 4d 61 70 24 45 6e 74 72 79 07 00 57 01 00 0d 6a 61 76	U...java/util/Map$Entry..W...jav
0480	61 2f 75 74 69 6c 2f 4d 61 70 01 00 05 45 6e 74 72 79 00 20 00 01 00 03 00 01 00 05 00 03 00 00	a/util/Map...Entry..............
04a0	00 07 00 08 00 00 00 00 00 09 00 08 00 00 10 10 00 0a 00 0b 00 00 00 06 00 00 00 0c 00 0d 00 01	................................
04c0	00 0e 00 00 00 4a 00 02 00 02 00 00 00 14 2a 2b b5 00 0f 2a b7 00 11 2a 03 b5 00 14 2a 02 b5 00	.....J........+.............
04e0	16 b1 00 00 00 02 00 18 00 00 00 12 00 04 00 00 00 01 00 05 01 3c 00 09 01 3e 00 0e 01 3f 00 19	.....................<...>...?..
0500	00 00 00 0c 00 01 00 00 00 14 00 1a 00 1b 00 00 00 01 00 1c 00 1d 00 01 00 0e 00 00 00 3f 00 02	.............................?..
0520	00 01 00 00 00 15 2a b4 00 14 2a b4 00 0f b8 00 1e b4 00 24 a2 00 05 04 ac 03 ac 00 00 00 02 00	.................$............
0540	18 00 00 00 06 00 01 00 00 01 43 00 19 00 00 00 0c 00 01 00 00 00 15 00 1a 00 1b 00 00 00 01 00	..........C.....................
0560	29 00 2a 00 02 00 2b 00 00 00 02 00 2c 00 0e 00 00 00 9d 00 06 00 01 00 00 00 63 2a 59 b4 00 14	)....+.....,.............cY...
0580	04 60 b5 00 14 2a 59 b4 00 16 04 60 b5 00 16 a7 00 0d 2a 59 b4 00 16 04 60 b5 00 16 2a b4 00 0f	.`...Y....`......Y....`...*...
05a0	b8 00 1e b4 00 2d 2a b4 00 16 32 b2 00 31 a5 ff e4 bb 00 35 59 2a 2a b4 00 0f b8 00 1e b4 00 37	.....-...2..1.....5Y*........7
05c0	b6 00 3b c0 00 41 2a b4 00 16 32 2a b4 00 0f b8 00 1e b4 00 2d 2a b4 00 16 32 b7 00 43 b0 00 00	..;..A...2........-*...2..C...
05e0	00 02 00 18 00 00 00 16 00 05 00 00 01 48 00 0a 01 49 00 36 01 4d 00 50 01 4e 00 5f 01 4d 00 19	.............H...I.6.M.P.N._.M..
0600	00 00 00 0c 00 01 00 00 00 63 00 1a 00 1b 00 00 00 01 00 46 00 13 00 01 00 0e 00 00 00 55 00 03	.........c.........F.........U..
0620	00 01 00 00 00 23 2a b4 00 0f b8 00 1e 59 b4 00 24 04 64 b5 00 24 2a b4 00 0f b8 00 1e b4 00 2d	.....#......Y..$.d..$........-
0640	2a b4 00 16 b2 00 31 53 b1 00 00 00 02 00 18 00 00 00 0e 00 03 00 00 01 5a 00 10 01 5b 00 22 01	*.....1S................Z...[.".
0660	5c 00 19 00 00 00 0c 00 01 00 00 00 23 00 1a 00 1b 00 00 10 41 00 29 00 47 00 01 00 0e 00 00 00	\...........#.......A.).G.......
0680	25 00 01 00 01 00 00 00 05 2a b6 00 48 b0 00 00 00 02 00 18 00 00 00 06 00 01 00 00 00 01 00 19	%........*..H...................
06a0	00 00 00 02 00 00 10 08 00 4a 00 4b 00 01 00 0e 00 00 00 25 00 01 00 01 00 00 00 05 2a b4 00 0f	.........J.K.......%........*...
06c0	b0 00 00 00 02 00 18 00 00 00 06 00 01 00 00 01 3c 00 19 00 00 00 02 00 00 00 04 00 4c 00 00 00	................<...........L...
06e0	02 00 4d 00 2b 00 00 00 02 00 4e 00 4f 00 00 00 04 00 1f 00 50 00 53 00 00 00 22 00 04 00 1f 00	..M.+.....N.O.......P.S...".....
0700	00 00 00 00 00 00 01 00 00 00 00 00 00 00 35 00 00 00 00 00 00 00 54 00 56 00 58 06 09	..............5.......T.V.X..