/* Loop transformation code generation
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
#include "tree-scalar-evolution.h"
#include "vec.h"
#include "lambda.h"
+#include "vecprim.h"
/* This loop nest code generation is based on non-singular matrix
math.
Fourier-Motzkin elimination is used to compute the bounds of the base space
of the lattice. */
-DEF_VEC_I(int);
-DEF_VEC_ALLOC_I(int,heap);
-
static bool perfect_nestify (struct loops *,
struct loop *, VEC(tree,heap) *,
VEC(tree,heap) *, VEC(int,heap) *,
return ret;
}
-/* Compute the greatest common denominator of two numbers (A and B) using
- Euclid's algorithm. */
-
-static int
-gcd (int a, int b)
-{
-
- int x, y, z;
-
- x = abs (a);
- y = abs (b);
-
- while (x > 0)
- {
- z = y % x;
- y = x;
- x = z;
- }
-
- return (y);
-}
-
-/* Compute the greatest common denominator of a VECTOR of SIZE numbers. */
-
-static int
-gcd_vector (lambda_vector vector, int size)
-{
- int i;
- int gcd1 = 0;
-
- if (size > 0)
- {
- gcd1 = vector[0];
- for (i = 1; i < size; i++)
- gcd1 = gcd (gcd1, vector[i]);
- }
- return gcd1;
-}
-
/* Compute the least common multiple of two numbers A and B . */
static int
LN_LOOPS (target_nest)[i] = target_loop;
/* Computes the gcd of the coefficients of the linear part. */
- gcd1 = gcd_vector (target[i], i);
+ gcd1 = lambda_vector_gcd (target[i], i);
/* Include the denominator in the GCD. */
gcd1 = gcd (gcd1, 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 = 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));
}
/* 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 = 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));
if (stmt_uses_op (stmt, iv))
goto fail;
- /* If this is a simple operation like a cast that is
- invariant in the inner loop, or after the inner loop,
- then see if we can place it back where it came from.
- This means that we will propagate casts and other
- cheap invariant operations *back* into or after
- the inner loop if we can interchange the loop, on the
- theory that we are going to gain a lot more by
- interchanging the loop than we are by leaving some
- invariant code there for some other pass to clean
- up. */
+ /* If this is a scalar operation that can be put back
+ into the inner loop, or after the inner loop, through
+ copying, then do so. This works on the theory that
+ any amount of scalar code we have to reduplicate
+ into or after the loops is less expensive that the
+ win we get from rearranging the memory walk
+ the loop is doing so that it has better
+ cache behavior. */
if (TREE_CODE (stmt) == MODIFY_EXPR
- && is_gimple_cast (TREE_OPERAND (stmt, 1))
&& (can_put_in_inner_loop (loop->inner, stmt)
|| can_put_after_inner_loop (loop, stmt)))
continue;
newname = make_ssa_name (newname, newstmt);
TREE_OPERAND (newstmt, 0) = newname;
SET_USE (use_p, TREE_OPERAND (newstmt, 0));
- bsi_insert_after (&tobsi, newstmt, BSI_SAME_STMT);
+ bsi_insert_before (&tobsi, newstmt, BSI_SAME_STMT);
update_stmt (newstmt);
update_stmt (imm_stmt);
}
bool
lambda_transform_legal_p (lambda_trans_matrix trans,
int nb_loops,
- varray_type dependence_relations)
+ VEC (ddr_p, heap) *dependence_relations)
{
unsigned int i, j;
lambda_vector distres;
/* When there is an unknown relation in the dependence_relations, we
know that it is no worth looking at this loop nest: give up. */
- ddr = (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, 0);
+ ddr = VEC_index (ddr_p, dependence_relations, 0);
if (ddr == NULL)
return true;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
distres = lambda_vector_new (nb_loops);
/* For each distance vector in the dependence graph. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
- ddr = (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, i);
-
/* Don't care about relations for which we know that there is no
dependence, nor about read-read (aka. output-dependences):
these data accesses can happen in any order. */
OSDN Git Service
