#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"
#include "vecprim.h"
static bool perfect_nestify (struct loops *,
struct loop *, VEC(tree,heap) *,
VEC(tree,heap) *, VEC(int,heap) *,
VEC(tree,heap) *);
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 *);
static bool can_convert_to_perfect_nest (struct loop *);
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;
}
lambda_body_vector
lambda_body_vector_compute_new (lambda_trans_matrix transform,
lambda_body_vector vect)
{
lambda_body_vector temp;
int depth;
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;
}
void
print_lambda_body_vector (FILE * outfile, lambda_body_vector body)
{
print_lambda_vector (outfile, LBV_COEFFICIENTS (body), LBV_SIZE (body));
}
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;
}
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 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);
}
}
}
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));
}
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);
}
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;
}
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");
}
}
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;
}
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 (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
{
expression = LL_LOWER_BOUND (loop);
gcc_assert (expression && !LLE_NEXT (expression)
&& LLE_DENOMINATOR (expression) == 1);
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;
LATTICE_ORIGIN (ret)[i] = LLE_CONSTANT (expression);
for (j = 0; j < invariants; j++)
LATTICE_ORIGIN_INVARIANTS (ret)[i][j] =
LLE_INVARIANT_COEFFICIENTS (expression)[j];
}
}
return ret;
}
static int
lcm (int a, int b)
{
return (abs (a) * abs (b) / gcd (a, b));
}
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)
{
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];
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)
{
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];
if (!lle_equal (LL_UPPER_BOUND (loop),
expression, depth, invariants))
{
LLE_NEXT (expression) = LL_UPPER_BOUND (loop);
LL_UPPER_BOUND (loop) = expression;
}
}
}
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++;
}
}
}
}
swapmatrix = A;
A = A1;
A1 = swapmatrix;
swapmatrix = B;
B = B1;
B1 = swapmatrix;
swapvector = a;
a = a1;
a1 = swapvector;
size = newsize;
}
return auxillary_nest;
}
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);
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);
size = 0;
for (i = 0; i < depth; i++)
{
loop = LN_LOOPS (nest)[i];
if (LL_STEP (loop) > 0)
expression = LL_LOWER_BOUND (loop);
else
expression = LL_UPPER_BOUND (loop);
for (; expression != NULL; expression = LLE_NEXT (expression))
{
for (j = 0; j < i; j++)
A[size][j] = LLE_COEFFICIENTS (expression)[j];
for (j = 0; j < invariants; j++)
B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];
a[size] = LLE_CONSTANT (expression);
A[size][i] = -1 * LLE_DENOMINATOR (expression);
a[size] *= -1;
for (j = 0; j < invariants; j++)
B[size][j] *= -1;
size++;
gcc_assert (size <= 127);
}
if (LL_STEP (loop) > 0)
expression = LL_UPPER_BOUND (loop);
else
expression = LL_LOWER_BOUND (loop);
for (; expression != NULL; expression = LLE_NEXT (expression))
{
for (j = 0; j < i; j++)
A[size][j] = LLE_COEFFICIENTS (expression)[j];
for (j = 0; j < invariants; j++)
B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];
a[size] = LLE_CONSTANT (expression);
for (j = 0; j < i; j++)
A[size][j] *= -1;
A[size][i] = LLE_DENOMINATOR (expression);
size++;
gcc_assert (size <= 127);
}
}
lattice = lambda_lattice_compute_base (nest);
lambda_matrix_mult (A, LATTICE_BASE (lattice), A1, size, depth, depth);
lambda_matrix_vector_mult (A, size, depth, LATTICE_ORIGIN (lattice), a1);
lambda_vector_add_mc (a, 1, a1, -1, a1, size);
lambda_matrix_mult (A, LATTICE_ORIGIN_INVARIANTS (lattice), B1, size, depth,
invariants);
lambda_matrix_add_mc (B, 1, B1, -1, B1, size, invariants);
invertedtrans = lambda_matrix_new (depth, depth);
lambda_matrix_inverse (LTM_MATRIX (trans),
invertedtrans, depth);
lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
return compute_nest_using_fourier_motzkin (size, depth, invariants,
A, B1, a1);
}
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 = lambda_matrix_new (depth, depth);
lambda_matrix_copy (LTM_MATRIX (H), H1, depth, depth);
for (i = 0; i < depth; i++)
H1[i][i] = 0;
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++)
{
target_loop = lambda_loop_new ();
LN_LOOPS (target_nest)[i] = target_loop;
gcd1 = lambda_vector_gcd (target[i], i);
gcd1 = gcd (gcd1, determinant);
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 (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];
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;
}
gcd1 = lambda_vector_gcd (LLE_COEFFICIENTS (target_expr), depth);
gcd2 = lambda_vector_gcd (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;
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;
}
}
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;
}
gcd1 = lambda_vector_gcd (LLE_COEFFICIENTS (target_expr), depth);
gcd2 = lambda_vector_gcd (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;
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 (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;
}
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;
}
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);
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;
}
lattice = lambda_lattice_compute_base (nest);
trans1 = lambda_trans_matrix_new (depth, depth);
lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_BASE (lattice),
LTM_MATRIX (trans1), depth, depth, depth);
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));
auxillary_nest = lambda_compute_auxillary_space (nest, U);
stepsigns = lambda_compute_step_signs (trans1, stepsigns);
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;
}
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;
}
static int
depth_of_nest (struct loop *nest)
{
size_t depth = 0;
while (nest)
{
depth++;
nest = nest->inner;
}
return depth;
}
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;
}
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;
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;
}
}
*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);
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;
}
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;
}
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));
if (TREE_OPERAND (test, 0) == inductionvar)
uboundvar = TREE_OPERAND (test, 1);
else
uboundvar = TREE_OPERAND (test, 0);
gcc_assert (VEC_length (tree, *invariants) <= (unsigned int) (2 * depth));
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 = build2 (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;
}
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;
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);
lambda_loopnest
gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
struct loop *loop_nest,
VEC(tree,heap) **inductionvars,
VEC(tree,heap) **invariants)
{
lambda_loopnest ret = NULL;
struct loop *temp = loop_nest;
int depth = depth_of_nest (loop_nest);
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;
bool perfect_nest = perfect_nest_p (loop_nest);
if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
goto fail;
while (temp)
{
newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
&inductionvar, *inductionvars,
&lboundvars, &uboundvars,
&steps);
if (!newloop)
goto fail;
VEC_safe_push (tree, heap, *inductionvars, inductionvar);
VEC_safe_push (lambda_loop, heap, loops, newloop);
temp = temp->inner;
}
if (!perfect_nest)
{
if (!perfect_nestify (currloops, loop_nest,
lboundvars, uboundvars, steps, *inductionvars))
{
if (dump_file)
fprintf (dump_file,
"Not a perfect loop nest and couldn't convert to one.\n");
goto fail;
}
else if (dump_file)
fprintf (dump_file,
"Successfully converted loop nest to perfect loop nest.\n");
}
ret = lambda_loopnest_new (depth, 2 * depth);
for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
LN_LOOPS (ret)[i] = newloop;
fail:
VEC_free (lambda_loop, heap, loops);
VEC_free (tree, heap, uboundvars);
VEC_free (tree, heap, lboundvars);
VEC_free (int, heap, steps);
return ret;
}
static tree
lbv_to_gcc_expression (lambda_body_vector lbv,
tree type, VEC(tree,heap) *induction_vars,
tree *stmts_to_insert)
{
tree stmts, stmt, resvar, name;
tree iv;
size_t i;
tree_stmt_iterator tsi;
stmts = alloc_stmt_list ();
resvar = create_tmp_var (type, "lbvtmp");
add_referenced_var (resvar);
stmt = build2 (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; VEC_iterate (tree, induction_vars, i, iv); i++)
{
if (LBV_COEFFICIENTS (lbv)[i] != 0)
{
tree newname;
tree coeffmult;
coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
fold_build2 (MULT_EXPR, type, iv, coeffmult));
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
}
if (LBV_DENOMINATOR (lbv) != 1)
{
tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (CEIL_DIV_EXPR, type, name, denominator));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
*stmts_to_insert = stmts;
return name;
}
static tree
lle_to_gcc_expression (lambda_linear_expression lle,
lambda_linear_expression offset,
tree type,
VEC(tree,heap) *induction_vars,
VEC(tree,heap) *invariants,
enum tree_code wrap, tree *stmts_to_insert)
{
tree stmts, stmt, resvar, name;
size_t i;
tree_stmt_iterator tsi;
tree iv, invar;
VEC(tree,heap) *results = NULL;
gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR);
name = NULL_TREE;
stmts = alloc_stmt_list ();
resvar = create_tmp_var (type, "lletmp");
add_referenced_var (resvar);
for (; lle != NULL; lle = LLE_NEXT (lle))
{
stmt = build2 (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
{
if (LLE_COEFFICIENTS (lle)[i] != 0)
{
tree newname;
tree mult;
tree coeff;
if (LLE_COEFFICIENTS (lle)[i] == 1)
{
mult = VEC_index (tree, induction_vars, i);
}
else
{
coeff = build_int_cst (type,
LLE_COEFFICIENTS (lle)[i]);
mult = fold_build2 (MULT_EXPR, type, iv, coeff);
}
stmt = build2 (MODIFY_EXPR, void_type_node, resvar, mult);
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
}
for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
{
if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
{
tree newname;
tree mult;
tree coeff;
int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
if (invcoeff == 1)
{
mult = invar;
}
else
{
coeff = build_int_cst (type, invcoeff);
mult = fold_build2 (MULT_EXPR, type, invar, coeff);
}
stmt = build2 (MODIFY_EXPR, void_type_node, resvar, mult);
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
}
if (LLE_CONSTANT (lle) != 0)
{
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (PLUS_EXPR, type, name,
build_int_cst (type, LLE_CONSTANT (lle))));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
if (LLE_CONSTANT (offset) != 0)
{
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (PLUS_EXPR, type, name,
build_int_cst (type, LLE_CONSTANT (offset))));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
if (LLE_DENOMINATOR (lle) != 1)
{
stmt = build_int_cst (type, LLE_DENOMINATOR (lle));
stmt = build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
type, name, stmt);
stmt = build2 (MODIFY_EXPR, void_type_node, resvar, stmt);
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
VEC_safe_push (tree, heap, results, name);
}
gcc_assert (VEC_length (tree, results) <= 2);
if (VEC_length (tree, results) > 1)
{
tree op1 = VEC_index (tree, results, 0);
tree op2 = VEC_index (tree, results, 1);
stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
build2 (wrap, type, 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);
}
VEC_free (tree, heap, results);
*stmts_to_insert = stmts;
return name;
}
void
lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
VEC(tree,heap) *old_ivs,
VEC(tree,heap) *invariants,
lambda_loopnest new_loopnest,
lambda_trans_matrix transform)
{
struct loop *temp;
size_t i = 0;
size_t depth = 0;
VEC(tree,heap) *new_ivs = NULL;
tree oldiv;
block_stmt_iterator bsi;
if (dump_file)
{
transform = lambda_trans_matrix_inverse (transform);
fprintf (dump_file, "Inverse of transformation matrix:\n");
print_lambda_trans_matrix (dump_file, transform);
}
depth = depth_of_nest (old_loopnest);
temp = old_loopnest;
while (temp)
{
lambda_loop newloop;
basic_block bb;
edge exit;
tree ivvar, ivvarinced, exitcond, stmts;
enum tree_code testtype;
tree newupperbound, newlowerbound;
lambda_linear_expression offset;
tree type;
bool insert_after;
tree inc_stmt;
oldiv = VEC_index (tree, old_ivs, i);
type = TREE_TYPE (oldiv);
ivvar = create_tmp_var (type, "lnivtmp");
add_referenced_var (ivvar);
VEC_safe_push (tree, heap, new_ivs, ivvar);
newloop = LN_LOOPS (new_loopnest)[i];
offset = LL_LINEAR_OFFSET (newloop);
gcc_assert (LLE_DENOMINATOR (offset) == 1 &&
lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth));
newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
type,
new_ivs,
invariants, MAX_EXPR, &stmts);
bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
bsi_commit_edge_inserts ();
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
type,
new_ivs,
invariants, MIN_EXPR, &stmts);
exit = temp->single_exit;
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
bsi = bsi_start (bb);
bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
standard_iv_increment_position (temp, &bsi, &insert_after);
create_iv (newlowerbound,
build_int_cst (type, LL_STEP (newloop)),
ivvar, temp, &bsi, insert_after, &ivvar,
NULL);
inc_stmt = build2 (PLUS_EXPR, type,
ivvar, build_int_cst (type, LL_STEP (newloop)));
inc_stmt = build2 (MODIFY_EXPR, void_type_node, SSA_NAME_VAR (ivvar),
inc_stmt);
ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
TREE_OPERAND (inc_stmt, 0) = ivvarinced;
bsi = bsi_for_stmt (exitcond);
bsi_insert_before (&bsi, inc_stmt, BSI_SAME_STMT);
testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR;
if (exit->flags & EDGE_FALSE_VALUE)
testtype = swap_tree_comparison (testtype);
COND_EXPR_COND (exitcond) = build2 (testtype,
boolean_type_node,
newupperbound, ivvarinced);
update_stmt (exitcond);
VEC_replace (tree, new_ivs, i, ivvar);
i++;
temp = temp->inner;
}
for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
{
imm_use_iterator imm_iter;
use_operand_p use_p;
tree oldiv_def;
tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
tree stmt;
if (TREE_CODE (oldiv_stmt) == PHI_NODE)
oldiv_def = PHI_RESULT (oldiv_stmt);
else
oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF);
gcc_assert (oldiv_def != NULL_TREE);
FOR_EACH_IMM_USE_STMT (stmt, imm_iter, oldiv_def)
{
tree newiv, stmts;
lambda_body_vector lbv, newlbv;
gcc_assert (TREE_CODE (stmt) != PHI_NODE);
depth = VEC_length (tree, new_ivs);
lbv = lambda_body_vector_new (depth);
LBV_COEFFICIENTS (lbv)[i] = 1;
newlbv = lambda_body_vector_compute_new (transform, lbv);
newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
new_ivs, &stmts);
bsi = bsi_for_stmt (stmt);
bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
propagate_value (use_p, newiv);
update_stmt (stmt);
}
}
VEC_free (tree, heap, new_ivs);
}
static bool
not_interesting_stmt (tree stmt)
{
if (TREE_CODE (stmt) == LABEL_EXPR
|| TREE_CODE (stmt) == GOTO_EXPR
|| TREE_CODE (stmt) == COND_EXPR)
return true;
return false;
}
static bool
phi_loop_edge_uses_def (struct loop *loop, tree phi, tree def)
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, i)->src))
if (PHI_ARG_DEF (phi, i) == def)
return true;
return false;
}
static bool
stmt_uses_phi_result (tree stmt, tree phi_result)
{
tree use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
return (use == phi_result);
}
static bool
stmt_is_bumper_for_loop (struct loop *loop, tree stmt)
{
tree use;
tree def;
imm_use_iterator iter;
use_operand_p use_p;
def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
if (!def)
return false;
FOR_EACH_IMM_USE_FAST (use_p, iter, def)
{
use = USE_STMT (use_p);
if (TREE_CODE (use) == PHI_NODE)
{
if (phi_loop_edge_uses_def (loop, use, def))
if (stmt_uses_phi_result (stmt, PHI_RESULT (use)))
return true;
}
}
return false;
}
bool
perfect_nest_p (struct loop *loop)
{
basic_block *bbs;
size_t i;
tree exit_cond;
if (!loop->inner)
return true;
bbs = get_loop_body (loop);
exit_cond = get_loop_exit_condition (loop);
for (i = 0; i < loop->num_nodes; i++)
{
if (bbs[i]->loop_father == loop)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (stmt == exit_cond
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
continue;
free (bbs);
return false;
}
}
}
free (bbs);
if (loop->inner)
return perfect_nest_p (loop->inner);
return true;
}
static void
replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
int xstep, tree y, tree yinit,
htab_t replacements,
block_stmt_iterator *firstbsi)
{
ssa_op_iter iter;
use_operand_p use_p;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
tree use = USE_FROM_PTR (use_p);
tree step = NULL_TREE;
tree scev, init, val, var, setstmt;
struct tree_map *h, in;
void **loc;
if (use == x)
{
SET_USE (use_p, y);
continue;
}
scev = instantiate_parameters (loop,
analyze_scalar_evolution (loop, use));
if (scev == NULL || scev == chrec_dont_know)
continue;
step = evolution_part_in_loop_num (scev, loop->num);
if (step == NULL
|| step == chrec_dont_know
|| TREE_CODE (step) != INTEGER_CST
|| int_cst_value (step) != xstep)
continue;
in.hash = htab_hash_pointer (use);
in.from = use;
h = htab_find_with_hash (replacements, &in, in.hash);
if (h != NULL)
{
SET_USE (use_p, h->to);
continue;
}
init = initial_condition_in_loop_num (scev, loop->num);
gcc_assert (init != NULL && init != chrec_dont_know);
if (TREE_TYPE (use) == TREE_TYPE (y))
{
val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), init, yinit);
val = fold_build2 (PLUS_EXPR, TREE_TYPE (y), y, val);
if (val == y)
{
SET_USE (use_p, y);
continue;
}
}
else
{
val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), y, yinit);
val = fold_convert (TREE_TYPE (use), val);
val = fold_build2 (PLUS_EXPR, TREE_TYPE (use), val, init);
}
var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
add_referenced_var (var);
val = force_gimple_operand_bsi (firstbsi, val, false, NULL);
setstmt = build2 (MODIFY_EXPR, void_type_node, var, val);
var = make_ssa_name (var, setstmt);
TREE_OPERAND (setstmt, 0) = var;
bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
update_stmt (setstmt);
SET_USE (use_p, var);
h = ggc_alloc (sizeof (struct tree_map));
h->hash = in.hash;
h->from = use;
h->to = var;
loc = htab_find_slot_with_hash (replacements, h, in.hash, INSERT);
gcc_assert ((*(struct tree_map **)loc) == NULL);
*(struct tree_map **) loc = h;
}
}
static bool
exit_phi_for_loop_p (struct loop *loop, tree stmt)
{
if (TREE_CODE (stmt) != PHI_NODE
|| PHI_NUM_ARGS (stmt) != 1
|| bb_for_stmt (stmt) != loop->single_exit->dest)
return false;
return true;
}
static bool
can_put_in_inner_loop (struct loop *inner, tree stmt)
{
imm_use_iterator imm_iter;
use_operand_p use_p;
gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)
|| !expr_invariant_in_loop_p (inner, TREE_OPERAND (stmt, 1)))
return false;
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
{
if (!exit_phi_for_loop_p (inner, USE_STMT (use_p)))
{
basic_block immbb = bb_for_stmt (USE_STMT (use_p));
if (!flow_bb_inside_loop_p (inner, immbb))
return false;
}
}
return true;
}
static bool
can_put_after_inner_loop (struct loop *loop, tree stmt)
{
imm_use_iterator imm_iter;
use_operand_p use_p;
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return false;
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
{
if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
{
basic_block immbb = bb_for_stmt (USE_STMT (use_p));
if (!dominated_by_p (CDI_DOMINATORS,
immbb,
loop->inner->header)
&& !can_put_in_inner_loop (loop->inner, stmt))
return false;
}
}
return true;
}
static bool
can_convert_to_perfect_nest (struct loop *loop)
{
basic_block *bbs;
tree exit_condition, phi;
size_t i;
block_stmt_iterator bsi;
basic_block exitdest;
if (!loop->inner || loop->inner->inner)
return false;
bbs = get_loop_body (loop);
exit_condition = get_loop_exit_condition (loop);
for (i = 0; i < loop->num_nodes; i++)
{
if (bbs[i]->loop_father == loop)
{
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
continue;
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
use_operand_p use_a, use_b;
imm_use_iterator imm_iter;
ssa_op_iter op_iter, op_iter1;
tree op0 = TREE_OPERAND (stmt, 0);
tree scev = instantiate_parameters
(loop, analyze_scalar_evolution (loop, op0));
if (!automatically_generated_chrec_p (scev))
{
tree step = evolution_part_in_loop_num (scev, loop->num);
if (step && step != chrec_dont_know
&& TREE_CODE (step) == INTEGER_CST)
continue;
}
if (TREE_CODE (op0) == SSA_NAME)
FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
if (bb_for_stmt (USE_STMT (use_a))->loop_father
== loop->inner)
goto fail;
FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
{
tree node, op = USE_FROM_PTR (use_a);
FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
if (bb_for_stmt (USE_STMT (use_b))->loop_father
== loop->inner)
goto fail;
node = SSA_NAME_DEF_STMT (op);
if (TREE_CODE (node) == PHI_NODE)
FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
{
tree arg = USE_FROM_PTR (use_b);
if (TREE_CODE (arg) == SSA_NAME)
{
tree arg_stmt = SSA_NAME_DEF_STMT (arg);
if (bb_for_stmt (arg_stmt)->loop_father
== loop->inner)
goto fail;
}
}
}
if (can_put_in_inner_loop (loop->inner, stmt)
|| can_put_after_inner_loop (loop, stmt))
continue;
}
if (!dominated_by_p (CDI_DOMINATORS,
bb_for_stmt (stmt),
loop->inner->header))
goto fail;
}
}
}
exitdest = loop->single_exit->dest;
for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
if (PHI_NUM_ARGS (phi) != 1)
goto fail;
free (bbs);
return true;
fail:
free (bbs);
return false;
}
static bool
perfect_nestify (struct loops *loops,
struct loop *loop,
VEC(tree,heap) *lbounds,
VEC(tree,heap) *ubounds,
VEC(int,heap) *steps,
VEC(tree,heap) *loopivs)
{
basic_block *bbs;
tree exit_condition;
tree then_label, else_label, cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
int i;
block_stmt_iterator bsi, firstbsi;
bool insert_after;
edge e;
struct loop *newloop;
tree phi;
tree uboundvar;
tree stmt;
tree oldivvar, ivvar, ivvarinced;
VEC(tree,heap) *phis = NULL;
htab_t replacements = NULL;
olddest = loop->single_exit->dest;
preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi))
{
VEC_reserve (tree, heap, phis, 2);
VEC_quick_push (tree, phis, PHI_RESULT (phi));
VEC_quick_push (tree, phis, PHI_ARG_DEF (phi, 0));
}
e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
while (phi_nodes (olddest) != NULL)
{
SET_PHI_RESULT (phi_nodes (olddest), NULL);
remove_phi_node (phi_nodes (olddest), NULL);
}
while (VEC_length (tree, phis) != 0)
{
tree def;
tree phiname;
def = VEC_pop (tree, phis);
phiname = VEC_pop (tree, phis);
phi = create_phi_node (phiname, preheaderbb);
add_phi_arg (phi, def, single_pred_edge (preheaderbb));
}
flush_pending_stmts (e);
VEC_free (tree, heap, phis);
bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
make_edge (headerbb, bodybb, EDGE_FALLTHRU);
then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (latchbb));
else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (olddest));
cond_stmt = build3 (COND_EXPR, void_type_node,
build2 (NE_EXPR, boolean_type_node,
integer_one_node,
integer_zero_node),
then_label, else_label);
bsi = bsi_start (bodybb);
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
make_edge (latchbb, headerbb, EDGE_FALLTHRU);
newloop = duplicate_loop (loops, loop, olddest->loop_father);
newloop->header = headerbb;
newloop->latch = latchbb;
newloop->single_exit = e;
add_bb_to_loop (latchbb, newloop);
add_bb_to_loop (bodybb, newloop);
add_bb_to_loop (headerbb, newloop);
set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb);
set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb);
set_immediate_dominator (CDI_DOMINATORS, preheaderbb,
loop->single_exit->src);
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
oldivvar = VEC_index (tree, loopivs, 0);
ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
add_referenced_var (ivvar);
standard_iv_increment_position (newloop, &bsi, &insert_after);
create_iv (VEC_index (tree, lbounds, 0),
build_int_cst (TREE_TYPE (oldivvar), VEC_index (int, steps, 0)),
ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced);
exit_condition = get_loop_exit_condition (newloop);
uboundvar = create_tmp_var (integer_type_node, "uboundvar");
add_referenced_var (uboundvar);
stmt = build2 (MODIFY_EXPR, void_type_node, uboundvar,
VEC_index (tree, ubounds, 0));
uboundvar = make_ssa_name (uboundvar, stmt);
TREE_OPERAND (stmt, 0) = uboundvar;
if (insert_after)
bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
update_stmt (stmt);
COND_EXPR_COND (exit_condition) = build2 (GE_EXPR,
boolean_type_node,
uboundvar,
ivvarinced);
update_stmt (exit_condition);
replacements = htab_create_ggc (20, tree_map_hash,
tree_map_eq, NULL);
bbs = get_loop_body_in_dom_order (loop);
oldivvar = VEC_index (tree, loopivs, 0);
firstbsi = bsi_start (bodybb);
for (i = loop->num_nodes - 1; i >= 0 ; i--)
{
block_stmt_iterator tobsi = bsi_last (bodybb);
if (bbs[i]->loop_father == loop)
{
if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
{
block_stmt_iterator header_bsi
= bsi_after_labels (loop->inner->header);
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
{
tree stmt = bsi_stmt (bsi);
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
{
bsi_next (&bsi);
continue;
}
bsi_move_before (&bsi, &header_bsi);
}
}
else
{
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
{
ssa_op_iter i;
tree n, stmt = bsi_stmt (bsi);
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
{
bsi_next (&bsi);
continue;
}
replace_uses_equiv_to_x_with_y
(loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar,
VEC_index (tree, lbounds, 0), replacements, &firstbsi);
bsi_move_before (&bsi, &tobsi);
FOR_EACH_SSA_TREE_OPERAND (n, stmt, i, SSA_OP_ALL_VIRTUALS)
mark_sym_for_renaming (SSA_NAME_VAR (n));
}
}
}
}
free (bbs);
htab_delete (replacements);
return perfect_nest_p (loop);
}
bool
lambda_transform_legal_p (lambda_trans_matrix trans,
int nb_loops,
VEC (ddr_p, heap) *dependence_relations)
{
unsigned int i, j;
lambda_vector distres;
struct data_dependence_relation *ddr;
gcc_assert (LTM_COLSIZE (trans) == nb_loops
&& LTM_ROWSIZE (trans) == nb_loops);
ddr = VEC_index (ddr_p, dependence_relations, 0);
if (ddr == NULL)
return true;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
return false;
distres = lambda_vector_new (nb_loops);
for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
if (DDR_ARE_DEPENDENT (ddr) == chrec_known
|| (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
continue;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
return false;
if (DDR_NUM_DIST_VECTS (ddr) == 0)
return false;
for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
{
lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
DDR_DIST_VECT (ddr, j), distres);
if (!lambda_vector_lexico_pos (distres, nb_loops))
return false;
}
}
return true;
}