/* 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
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,
+ 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 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))
{
int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num);
tree array_size = TYPE_SIZE (TREE_TYPE (ref));
double_int dstride;
- if (array_size == NULL_TREE
+ if (array_size == NULL_TREE
|| TREE_CODE (array_size) != INTEGER_CST)
continue;
- dstride = double_int_mul (tree_to_double_int (array_size),
+ 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));
}
}
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;
+ 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);
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,
- loop_nest->num))
+ 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 (gimple, remove_ivs, i, oldiv_stmt); i++)