/* Linear Loop transforms
- Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>.
This file is part of GCC.
#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 "obstack.h"
scaling, skewing, and reversal. They are used to change the
iteration order of loop nests in order to optimize data locality of
traversals, or remove dependences that prevent
- parallelization/vectorization/etc.
+ parallelization/vectorization/etc.
TODO: Determine reuse vectors/matrix and use it to determine optimal
transform matrix for locality purposes.
considered. The first loop in the considered loop nest is
FIRST_LOOP, and consequently, the index of the considered loop is
obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
-
+
Initializes:
- DEPENDENCE_STEPS the sum of all the data dependence distances
carried by loop LOOP,
| A[{0, +, 1336}_1]
| endloop_1
- gather_interchange_stats (in loop_1) will return
+ gather_interchange_stats (in loop_1) will return
DEPENDENCE_STEPS = 3002
NB_DEPS_NOT_CARRIED_BY_LOOP = 5
ACCESS_STRIDES = 10694
- gather_interchange_stats (in loop_2) will return
+ gather_interchange_stats (in loop_2) will return
DEPENDENCE_STEPS = 3000
NB_DEPS_NOT_CARRIED_BY_LOOP = 7
ACCESS_STRIDES = 8010
*/
static void
-gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations,
- VEC (data_reference_p, heap) *datarefs,
- struct loop *loop,
- struct loop *first_loop,
- unsigned int *dependence_steps,
- unsigned int *nb_deps_not_carried_by_loop,
- double_int *access_strides)
+gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations ATTRIBUTE_UNUSED,
+ VEC (data_reference_p, heap) *datarefs ATTRIBUTE_UNUSED,
+ struct loop *loop ATTRIBUTE_UNUSED,
+ struct loop *first_loop ATTRIBUTE_UNUSED,
+ unsigned int *dependence_steps ATTRIBUTE_UNUSED,
+ unsigned int *nb_deps_not_carried_by_loop ATTRIBUTE_UNUSED,
+ double_int *access_strides ATTRIBUTE_UNUSED)
{
unsigned int i, j;
struct data_dependence_relation *ddr;
{
unsigned int it;
tree ref = DR_REF (dr);
- tree stmt = DR_STMT (dr);
+ gimple stmt = DR_STMT (dr);
struct loop *stmt_loop = loop_containing_stmt (stmt);
struct loop *inner_loop = first_loop->inner;
- if (inner_loop != stmt_loop
+ if (inner_loop != stmt_loop
&& !flow_loop_nested_p (inner_loop, stmt_loop))
continue;
- for (it = 0; it < DR_NUM_DIMENSIONS (dr);
+ for (it = 0; it < DR_NUM_DIMENSIONS (dr);
it++, ref = TREE_OPERAND (ref, 0))
{
- tree chrec = DR_ACCESS_FN (dr, it);
- tree tstride = evolution_part_in_loop_num (chrec, loop->num);
+ int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num);
+ int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num);
tree array_size = TYPE_SIZE (TREE_TYPE (ref));
double_int dstride;
- if (tstride == NULL_TREE
- || array_size == NULL_TREE
- || TREE_CODE (tstride) != INTEGER_CST
+ if (array_size == NULL_TREE
|| TREE_CODE (array_size) != INTEGER_CST)
continue;
- dstride = double_int_mul (tree_to_double_int (array_size),
- tree_to_double_int (tstride));
+ dstride = double_int_mul (tree_to_double_int (array_size),
+ shwi_to_double_int (istride));
(*access_strides) = double_int_add (*access_strides, dstride);
}
}
}
/* Attempt to apply interchange transformations to TRANS to maximize the
- spatial and temporal locality of the loop.
+ spatial and temporal locality of the loop.
Returns the new transform matrix. The smaller the reuse vector
distances in the inner loops, the fewer the cache misses.
FIRST_LOOP is the loop->num of the first loop in the analyzed loop
static lambda_trans_matrix
-try_interchange_loops (lambda_trans_matrix trans,
- unsigned int depth,
+try_interchange_loops (lambda_trans_matrix trans,
+ unsigned int depth,
VEC (ddr_p, heap) *dependence_relations,
VEC (data_reference_p, heap) *datarefs,
struct loop *first_loop)
l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
/* LOOP_I is always the outer loop. */
- for (loop_j = first_loop->inner;
- loop_j;
+ for (loop_j = first_loop->inner;
+ loop_j;
loop_j = loop_j->inner)
- for (loop_i = first_loop;
- loop_depth (loop_i) < loop_depth (loop_j);
+ for (loop_i = first_loop;
+ loop_depth (loop_i) < loop_depth (loop_j);
loop_i = loop_i->inner)
{
gather_interchange_stats (dependence_relations, datarefs,
loop_i, first_loop,
- &dependence_steps_i,
+ &dependence_steps_i,
&nb_deps_not_carried_by_i,
&access_strides_i);
gather_interchange_stats (dependence_relations, datarefs,
loop_j, first_loop,
- &dependence_steps_j,
- &nb_deps_not_carried_by_j,
+ &dependence_steps_j,
+ &nb_deps_not_carried_by_j,
&access_strides_j);
-
+
/* Heuristics for loop interchange profitability:
0. Don't transform if the smallest stride is larger than
res = cmp < 0 ?
estimated_loop_iterations (loop_j, false, &nb_iter):
estimated_loop_iterations (loop_i, false, &nb_iter);
- large = double_int_mul (large, nb_iter);
- if (res && double_int_ucmp (large, l1_cache_size) < 0)
+ if (res
+ && double_int_ucmp (double_int_mul (large, nb_iter),
+ l1_cache_size) < 0)
continue;
- if (dependence_steps_i < dependence_steps_j
+ if (dependence_steps_i < dependence_steps_j
|| nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
|| cmp < 0)
{
/* Validate the resulting matrix. When the transformation
is not valid, reverse to the previous transformation. */
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
- lambda_matrix_row_exchange (LTM_MATRIX (trans),
- loop_depth (loop_i) - loop_depth (first_loop),
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_depth (loop_i) - loop_depth (first_loop),
loop_depth (loop_j) - loop_depth (first_loop));
}
}
/* Return the number of nested loops in LOOP_NEST, or 0 if the loops
are not perfectly nested. */
-static unsigned int
+unsigned int
perfect_loop_nest_depth (struct loop *loop_nest)
{
struct loop *temp;
loop_iterator li;
VEC(tree,heap) *oldivs = NULL;
VEC(tree,heap) *invariants = NULL;
- VEC(tree,heap) *remove_ivs = VEC_alloc (tree, heap, 3);
+ VEC(tree,heap) *lambda_parameters = NULL;
+ VEC(gimple,heap) *remove_ivs = VEC_alloc (gimple, heap, 3);
struct loop *loop_nest;
- tree oldiv_stmt;
+ gimple oldiv_stmt;
unsigned i;
FOR_EACH_LOOP (li, loop_nest, 0)
unsigned int depth = 0;
VEC (ddr_p, heap) *dependence_relations;
VEC (data_reference_p, heap) *datarefs;
+
lambda_loopnest before, after;
lambda_trans_matrix trans;
struct obstack lambda_obstack;
- gcc_obstack_init (&lambda_obstack);
+ struct loop *loop;
+ VEC(loop_p,heap) *nest;
depth = perfect_loop_nest_depth (loop_nest);
if (depth == 0)
continue;
+ nest = VEC_alloc (loop_p, heap, 3);
+ for (loop = loop_nest; loop; loop = loop->inner)
+ VEC_safe_push (loop_p, heap, nest, loop);
+
+ gcc_obstack_init (&lambda_obstack);
VEC_truncate (tree, oldivs, 0);
VEC_truncate (tree, invariants, 0);
+ VEC_truncate (tree, lambda_parameters, 0);
datarefs = VEC_alloc (data_reference_p, heap, 10);
dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
- compute_data_dependences_for_loop (loop_nest, true, &datarefs,
- &dependence_relations);
+ if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs,
+ &dependence_relations))
+ goto free_and_continue;
+
+ lambda_collect_parameters (datarefs, &lambda_parameters);
+ if (!lambda_compute_access_matrices (datarefs, lambda_parameters,
+ nest, &lambda_obstack))
+ goto free_and_continue;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_ddrs (dump_file, dependence_relations);
/* Build the transformation matrix. */
- trans = lambda_trans_matrix_new (depth, depth);
+ trans = lambda_trans_matrix_new (depth, depth, &lambda_obstack);
lambda_matrix_id (LTM_MATRIX (trans), depth);
trans = try_interchange_loops (trans, depth, dependence_relations,
datarefs, loop_nest);
fprintf (dump_file, "Before:\n");
print_lambda_loopnest (dump_file, before, 'i');
}
-
+
after = lambda_loopnest_transform (before, trans, &lambda_obstack);
if (dump_file)
obstack_free (&lambda_obstack, NULL);
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
+ VEC_free (loop_p, heap, nest);
}
- for (i = 0; VEC_iterate (tree, remove_ivs, i, oldiv_stmt); i++)
+ for (i = 0; VEC_iterate (gimple, remove_ivs, i, oldiv_stmt); i++)
remove_iv (oldiv_stmt);
VEC_free (tree, heap, oldivs);
VEC_free (tree, heap, invariants);
- VEC_free (tree, heap, remove_ivs);
+ VEC_free (gimple, heap, remove_ivs);
scev_reset ();
if (modified)