/* Loop transformation code generation Copyright (C) 2003, 2004 Free Software Foundation, Inc. Contributed by Daniel Berlin 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 "errors.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 "tree-fold-const.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 "varray.h" #include "lambda.h" /* This loop nest code generation is based on non-singular matrix math. */ /* Lattice stuff that is internal to the code generation algorithm. */ typedef struct { lambda_matrix base; int dimension; lambda_vector origin; lambda_matrix origin_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. */ if (LTM_ROWSIZE (transform) != LTM_COLSIZE (transform)) abort (); 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; } static void print_linear_expression (FILE *outfile, lambda_vector expr, int size, char start) { int i; bool starting = true; for (i = 0; i < size; i++) { if (expr[i] != 0) { if (starting) { if (expr[i] < 0) fprintf (outfile, "-"); starting = false; } else if (expr[i] > 0) fprintf (outfile, " + "); else fprintf (outfile, " - "); if (expr[i] == 1 || expr [i] == -1) fprintf (outfile, "%c", start + i); else fprintf (outfile, "%d%c", abs(expr[i]), start + i); } } } 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 loop. */ void print_lambda_loop (FILE *outfile, lambda_loop loop, int depth, int invariants, char start) { int step; lambda_linear_expression expr; if (!loop) abort (); 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"); expr = LL_LOWER_BOUND (loop); for (; expr != NULL; expr = LLE_NEXT (expr)) print_lambda_linear_expression (outfile, expr, depth, invariants, start); fprintf (outfile, " upper bound: \n"); expr = LL_UPPER_BOUND (loop); for (; expr != NULL; expr = LLE_NEXT (expr)) print_lambda_linear_expression (outfile, expr, depth, invariants, start); } /* Create a new loop nest structure. */ 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. */ 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. */ 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 a loopnest. */ 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]; if (!loop) abort (); 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); if (!expression || LLE_NEXT (expression) || LLE_DENOMINATOR (expression) != 1) abort (); 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 using euclid's algorithm. */ static int gcd (int a, int b) { int x, y, z; x = (a > 0) ? a : -1 * a; y = (b > 0) ? b : -1 * b; while (x>0) { z = y % x; y = x; x = z; } return (y); } /* Compute the greatest common denominator of a vector of 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. */ static int lcm (int a, int b) { return (abs (a) * abs (b) / gcd (a, b) ); } /* Compute the loop bounds for the auxillary space. Input system is Ax <= b. TRANS is the unimodular transformation matrix. Comments are transcribed from the equations in the paper. */ static lambda_loopnest lambda_compute_auxillary_space (lambda_loopnest nest, lambda_trans_matrix trans) { lambda_matrix A, B, A1, B1, temp0; lambda_vector a, a1, temp1; lambda_matrix invertedtrans; int determinant, depth, invariants, size, newsize; int i, j, k; lambda_loopnest auxillary_nest; lambda_loop loop; lambda_linear_expression expression; lambda_lattice lattice; int multiple, f1, f2; depth = LN_DEPTH (nest); invariants = LN_INVARIANTS (nest); 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 matrix A, vector a, and invariant matrix B, so that we have Ax <= a + B. */ 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. */ A[size][i] = -1 * LLE_DENOMINATOR (expression); a[size] *= -1; for (j = 0; j < invariants; j++) B[size][j] *= -1; size++; } /* 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++; } } /* Compute the lattice base x = base * y + origin, where y is the base space. */ lattice = lambda_lattice_compute_base (nest); /* Ax <= a + B becomes ALy <= a+B - A*origin. L is the lattice base */ /* A1 = AL */ 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); /* Compute the auxillary space. Equations: given A1 * y <= b1 + B1 Compute the auxillary space for z1=HUy A1 * y <= a1 + B1. Let z be the target space. z = Tx = T(Ly+origin) = TLy + T*origin z1 = z-T*origin = TLy = HUy. */ invertedtrans = lambda_matrix_new (depth, depth); /* Compute the inverse of U. */ determinant = lambda_matrix_inverse (LTM_MATRIX (trans), invertedtrans, depth); /* A = A1 inv(U). */ lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth); /* Perform Fourier-Motzkin on Ax <= a + B. */ temp0 = B1; B1 = B; B = temp0; temp1 = a1; a1 = a; a = temp1; 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) { /* 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) { /* Upper bound. */ expression = lambda_linear_expression_new (depth, invariants); for (k = 0; k < i; k++) LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k]; LLE_CONSTANT (expression) = a[j]; for (k = 0; k < invariants; k++) LLE_INVARIANT_COEFFICIENTS (expression)[k] = B[j][k]; LLE_DENOMINATOR (expression) = A[j][i]; /* 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; } } } /* creates a new system by deleting the i'th variable. */ newsize = 0; for (j = 0; j < size; j++) { 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++; } } } } temp0 = A; A = A1; A1 = temp0; temp0 = B; B = B1; B1 = temp0; temp1 = a; a = a1; a1 = temp1; size = newsize; } return auxillary_nest; } /* Compute the loop bounds for the target space, using the bounds of the auxillary nest. Output a new set of linear bounds and linear offsets. */ 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. */ 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. */ 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 loop nest. */ 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 auxillary 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 auxillary 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 to a linear expression. This is a trivial implementation. */ static lambda_linear_expression gcc_tree_to_linear_expression (int depth, tree expr, varray_type outerinductionvars, varray_type 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: { size_t i; for (i = 0; i < VARRAY_ACTIVE_SIZE (outerinductionvars); i++) if (VARRAY_TREE (outerinductionvars, i) != NULL) { tree iv = VARRAY_TREE (outerinductionvars, i); 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; i < VARRAY_ACTIVE_SIZE (invariants); i++) if (VARRAY_TREE (invariants, i) != NULL) { tree invar = VARRAY_TREE (invariants, i); 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 true if OP is invariant in LOOP. */ static bool invariant_in_loop (struct loop *loop, tree op) { if (TREE_CODE (op) == SSA_NAME) { if (TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op))) return true; if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op))) return false; return !flow_bb_inside_loop_p (loop, bb_for_stmt (SSA_NAME_DEF_STMT (op))); } return false; } /* Generate a lambda loop from a gcc loop. */ static lambda_loop gcc_loop_to_lambda_loop (struct loop *loop, int depth, varray_type *invariants, tree *ourinductionvar, varray_type outerinductionvars) { 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; #if 0 tree ev; tree nb_iter; tree base; tree final; #endif use_optype uses; /* Find out induction var and set the pointer so that the caller can append it to the outerinductionvars array later. */ inductionvar = find_induction_var_from_exit_cond (loop); *ourinductionvar = inductionvar; 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 (TREE_CODE (test) != LE_EXPR && TREE_CODE (test) != LT_EXPR && TREE_CODE (test) != NE_EXPR) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Unable to convert loop: Loop exit test uses unhandled test condition:"); print_generic_stmt (dump_file, test, 0); fprintf (dump_file, "\n"); } return NULL; } #if 0 ev = analyze_scalar_evolution (loop, inductionvar); if (!evolution_function_is_affine_or_constant_p (ev)) return NULL; nb_iter = number_of_iterations_in_loop (loop); nb_iter = chrec_fold_minus (chrec_type (nb_iter), nb_iter, convert (chrec_type (nb_iter), integer_one_node)); base = CHREC_LEFT (ev); step = CHREC_RIGHT (ev); final = chrec_apply (loop->num, ev, nb_iter); #endif /* XXX - MUST BE BETTER WAY TO GET PHI NODE FOR INDUCTION VARIABLES. */ 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) { get_stmt_operands (phi); uses = STMT_USE_OPS (phi); if (!uses) { 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 = USE_OP (uses, 0); 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; } } access_fn = instantiate_parameters (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); if (!access_fn) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Unable to convert loop: Access function for induction variable phi is NULL\n"); return NULL; } step = evolution_part_in_loop_num (access_fn, loop_num (loop)); if (!step) { 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)) lbound = gcc_tree_to_linear_expression (depth, PHI_ARG_DEF (phi, 1), outerinductionvars, *invariants, 0); else lbound = gcc_tree_to_linear_expression (depth, PHI_ARG_DEF (phi, 0), 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; } if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME) if (invariant_in_loop (loop, TREE_OPERAND (test, 1))) VARRAY_PUSH_TREE (*invariants, TREE_OPERAND (test, 1)); /* We only size the vectors assuming we have, at max, 2 times as many invariants as we do loops (one for each bound). */ if (VARRAY_ACTIVE_SIZE (*invariants) > (unsigned int)(2 * depth)) abort (); /* We might have some leftover. */ if (TREE_CODE (test) == LT_EXPR) extra = -1 * stepint; else if (TREE_CODE (test) == NE_EXPR) extra = -1 * stepint; ubound = gcc_tree_to_linear_expression (depth, TREE_OPERAND (test, 1), outerinductionvars, *invariants, extra); 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 an exit condition, find the induction variable it is testing against. */ static tree find_induction_var_from_exit_cond (struct loop *loop) { tree expr = get_loop_exit_condition (loop); tree test; if (expr == NULL_TREE) return NULL_TREE; if (TREE_CODE (expr) != COND_EXPR) return NULL_TREE; test = TREE_OPERAND (expr, 0); if (TREE_CODE_CLASS (TREE_CODE (test)) != '<') return NULL_TREE; if (TREE_CODE (TREE_OPERAND (test, 0)) != SSA_NAME) return NULL_TREE; return TREE_OPERAND (test, 0); } /* Generate a lambda loopnest from a gcc loopnest. */ lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loop *loop_nest, varray_type *inductionvars, varray_type *invariants) { lambda_loopnest ret; struct loop *temp; int depth = 0; size_t i; varray_type loops; lambda_loop newloop; tree inductionvar = NULL; temp = loop_nest; while (temp) { depth++; temp = temp->inner; } VARRAY_GENERIC_PTR_INIT (loops, 1, "Loop nest"); VARRAY_GENERIC_PTR_INIT (*inductionvars, 1, "induction vars"); VARRAY_GENERIC_PTR_INIT (*invariants, 1, "Invariants"); temp = loop_nest; while (temp) { newloop = gcc_loop_to_lambda_loop (temp, depth, invariants, &inductionvar, *inductionvars); if (!newloop) return NULL; VARRAY_PUSH_GENERIC_PTR (*inductionvars, inductionvar); VARRAY_PUSH_GENERIC_PTR (loops, newloop); temp = temp->inner; } ret = lambda_loopnest_new (depth, 2 * depth); for (i = 0; i < VARRAY_ACTIVE_SIZE (loops); i++) LN_LOOPS(ret)[i] = VARRAY_GENERIC_PTR (loops, i); return ret; } static tree build_int_cst (tree type, unsigned HOST_WIDE_INT val); /* Builds integer constant of type TYPE and value VAL. Borrowed from tree-ssa-loop-ivopts.c XXX: Move this into tree.c and remove from both files. */ static tree build_int_cst (tree type, unsigned HOST_WIDE_INT val) { unsigned bits = TYPE_PRECISION (type); bool signed_p = !TREE_UNSIGNED (type); bool negative = ((val >> (bits - 1)) & 1) != 0; tree ival; if (signed_p && negative) { val = val | (~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1); ival = build_int_2 (val, -1); } else { val = val & ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1); ival = build_int_2 (val, 0); } return convert (type, ival); } /* Convert a lambda body vector to a gcc tree. */ static tree lbv_to_gcc_expression (lambda_body_vector lbv, varray_type induction_vars, tree *stmts_to_insert) { tree stmts, stmt, resvar, name; size_t i; tree_stmt_iterator tsi; /* Create a statement list and a linear expression temporary. */ stmts = alloc_stmt_list (); resvar = create_tmp_var (integer_type_node, "lletmp"); add_referenced_tmp_var (resvar); /* Start at 0. */ stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); for (i = 0; i < VARRAY_ACTIVE_SIZE (induction_vars); i++) { if (LBV_COEFFICIENTS (lbv)[i] != 0) { tree newname; /* newname = coefficient * induction_variable */ stmt = build (MODIFY_EXPR, void_type_node, resvar, fold (build (MULT_EXPR, integer_type_node, VARRAY_TREE (induction_vars, i), build_int_cst (integer_type_node, LBV_COEFFICIENTS (lbv)[i])))); newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); /* name = name + newname */ stmt = build (MODIFY_EXPR, void_type_node, resvar, build (PLUS_EXPR, integer_type_node, name, newname)); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } } /* Handle any denominator that occurs. */ if (LBV_DENOMINATOR (lbv) != 1) { #if 0 if (wrap == MAX_EXPR) #endif stmt = build (MODIFY_EXPR, void_type_node, resvar, build (CEIL_DIV_EXPR, integer_type_node, name, build_int_cst (integer_type_node, LBV_DENOMINATOR (lbv)))); #if 0 else if (wrap == MIN_EXPR) stmt = build (MODIFY_EXPR, void_type_node, resvar, build (FLOOR_DIV_EXPR, integer_type_node, name, build_int_cst (integer_type_node, LBV_DENOMINATOR (lbv)))); else abort (); #endif name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } *stmts_to_insert = stmts; return name; } /* Convert a linear expression from coefficient and constant form to a gcc tree. This will likely generate trees that are badly in need of constant and copy propagation. */ static tree lle_to_gcc_expression (lambda_linear_expression lle, lambda_linear_expression offset, varray_type induction_vars, varray_type invariants, enum tree_code wrap, tree *stmts_to_insert) { tree stmts, stmt, resvar, name; size_t i; tree_stmt_iterator tsi; varray_type results; name = NULL_TREE; /* Create a statement list and a linear expression temporary. */ stmts = alloc_stmt_list (); resvar = create_tmp_var (integer_type_node, "lletmp"); add_referenced_tmp_var (resvar); VARRAY_TREE_INIT (results, 1, "Results"); for (; lle != NULL; lle = LLE_NEXT (lle)) { /* Start at 0. */ stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); /* First do the induction variables. name = name + (coeff * induction variable) */ for (i = 0; i < VARRAY_ACTIVE_SIZE (induction_vars); i++) { if (LLE_COEFFICIENTS (lle)[i] != 0) { tree newname; tree mult; tree coeff; coeff = build_int_cst (integer_type_node, LLE_COEFFICIENTS (lle)[i]); mult = fold (build (MULT_EXPR, integer_type_node, VARRAY_TREE (induction_vars, i), coeff)); /* newname = coefficient * induction_variable */ stmt = build (MODIFY_EXPR, void_type_node, resvar, mult); newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); /* name = name + newname */ stmt = build (MODIFY_EXPR, void_type_node, resvar, build (PLUS_EXPR, integer_type_node, name, newname)); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } } /* Handle our invariants. name = name + (coeff * invariant). */ for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++) { if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0) { tree newname; tree mult; tree coeff; coeff = build_int_cst (integer_type_node, LLE_INVARIANT_COEFFICIENTS (lle)[i]); mult = fold (build (MULT_EXPR, integer_type_node, VARRAY_TREE (invariants, i), coeff)); /* newname = coefficient * invariant */ stmt = build (MODIFY_EXPR, void_type_node, resvar, mult); newname = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = newname; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); /* name = name + newname */ stmt = build (MODIFY_EXPR, void_type_node, resvar, build (PLUS_EXPR, integer_type_node, name, newname)); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } } /* Now handle the constant. name = name + constant. */ if (LLE_CONSTANT (lle) != 0) { stmt = build (MODIFY_EXPR, void_type_node, resvar, build (PLUS_EXPR, integer_type_node, name, build_int_cst (integer_type_node, LLE_CONSTANT (lle)))); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } /* Now handle the offset. name = name + linear offset. */ if (LLE_CONSTANT (offset) != 0) { stmt = build (MODIFY_EXPR, void_type_node, resvar, build (PLUS_EXPR, integer_type_node, name, build_int_cst (integer_type_node, LLE_CONSTANT (offset)))); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } /* Handle any denominator that occurs. */ if (LLE_DENOMINATOR (lle) != 1) { if (wrap == MAX_EXPR) stmt = build (MODIFY_EXPR, void_type_node, resvar, build (CEIL_DIV_EXPR, integer_type_node, name, build_int_cst (integer_type_node, LLE_DENOMINATOR (lle)))); else if (wrap == MIN_EXPR) stmt = build (MODIFY_EXPR, void_type_node, resvar, build (FLOOR_DIV_EXPR, integer_type_node, name, build_int_cst (integer_type_node, LLE_DENOMINATOR (lle)))); else abort (); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } VARRAY_PUSH_TREE (results, name); } /* Again, out of laziness, we don't handle this case yet. It's not hard, it just hasn't occurred. */ if (VARRAY_ACTIVE_SIZE (results) > 2) abort (); /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */ if (VARRAY_ACTIVE_SIZE (results) > 1) { tree op1 = VARRAY_TREE (results, 0); tree op2 = VARRAY_TREE (results, 1); stmt = build (MODIFY_EXPR, void_type_node, resvar, build (wrap, integer_type_node, op1, op2)); name = make_ssa_name (resvar, stmt); TREE_OPERAND (stmt, 0) = name; tsi = tsi_last (stmts); tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING); } *stmts_to_insert = stmts; return name; } /* Transform a lambda loopnest back into code. This changes the loops, their induction variables, and their bodies, so that they match the transformed loopnest. */ void lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest, varray_type old_ivs, varray_type invariants, lambda_loopnest new_loopnest, lambda_trans_matrix transform) { struct loop *temp; size_t i = 0; size_t depth = 0; varray_type new_ivs; block_stmt_iterator bsi; basic_block *bbs; if (dump_file) { transform = lambda_trans_matrix_inverse (transform); fprintf (dump_file, "Inverse of transformation matrix:\n"); print_lambda_trans_matrix (dump_file, transform); } temp = old_loopnest; VARRAY_GENERIC_PTR_INIT (new_ivs, 1, "New induction variables"); while (temp) { temp = temp->inner; depth++; } temp = old_loopnest; while (temp) { lambda_loop newloop; basic_block bb; tree ivvar, ivvarinced, exitcond, stmts; enum tree_code testtype; tree newupperbound, newlowerbound; lambda_linear_expression offset; /* First, build the new induction variable temporary */ ivvar = create_tmp_var (integer_type_node, "lnivtmp"); add_referenced_tmp_var (ivvar); VARRAY_PUSH_GENERIC_PTR (new_ivs, ivvar); newloop = LN_LOOPS (new_loopnest)[i]; /* Linear offset is a bit tricky to handle. */ offset = LL_LINEAR_OFFSET (newloop); if (LLE_DENOMINATOR (offset) != 1 || !lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth)) abort (); /* Now build the new lower bounds, and insert the statements necessary to generate it on the loop preheader. */ newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop), LL_LINEAR_OFFSET (newloop), new_ivs, invariants, MAX_EXPR, &stmts); bsi_insert_on_edge_immediate (loop_preheader_edge (temp), stmts); /* Build the new upper bound and insert its statements in the basic block of the exit condition */ newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop), LL_LINEAR_OFFSET (newloop), new_ivs, invariants, MIN_EXPR, &stmts); /* XXX Is this right, or do we want before the first statement? */ exitcond = get_loop_exit_condition (temp); bb = bb_for_stmt (exitcond); bsi = bsi_start (bb); bsi_insert_after (&bsi, stmts, BSI_NEW_STMT); /* Create the new iv, and insert it's increment on the latch block. */ bb = temp->latch->pred->src; bsi = bsi_last (bb); create_iv (newlowerbound, build_int_cst (integer_type_node, LL_STEP (newloop)), ivvar, temp, &bsi, false, &ivvar, &ivvarinced); /* Replace the exit condition with the new upper bound comparison. */ testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR; COND_EXPR_COND (exitcond) = build (testtype, boolean_type_node, ivvarinced, newupperbound); modify_stmt (exitcond); VARRAY_GENERIC_PTR (new_ivs, i) = ivvar; i++; temp = temp->inner; } /* Go through the loop and make iv replacements. */ bbs = get_loop_body (old_loopnest); for (i = 0; i < old_loopnest->num_nodes; i++) for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi)) { tree stmt = bsi_stmt (bsi); use_optype uses; size_t j; get_stmt_operands (stmt); uses = STMT_USE_OPS (stmt); for (j = 0; j < NUM_USES (uses); j++) { size_t k; tree *use = USE_OP_PTR (uses, j); for (k = 0; k < VARRAY_ACTIVE_SIZE (old_ivs); k++) { tree oldiv = VARRAY_TREE (old_ivs, k); if (SSA_NAME_VAR (*use) == SSA_NAME_VAR (oldiv)) { tree newiv, stmts; lambda_body_vector lbv; /* Compute the new expression for the induction variable. */ depth = VARRAY_ACTIVE_SIZE (new_ivs); lbv = lambda_body_vector_new (depth); LBV_COEFFICIENTS (lbv)[k] = 1; lbv = lambda_body_vector_compute_new (transform, lbv); newiv = lbv_to_gcc_expression (lbv, new_ivs, &stmts); /* Insert the statements to build that expression. */ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT); /* Replace the use with the result of that expression. */ if (dump_file) { fprintf (dump_file, "Replacing induction variable use of "); print_generic_stmt (dump_file, *use, 0); fprintf (dump_file, " with "); print_generic_stmt (dump_file, newiv, 0); fprintf (dump_file, "\n"); } *use = newiv; } } } } }