/* Linear Loop transforms
|
/* Linear Loop transforms
|
Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
|
Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
Contributed by Daniel Berlin <dberlin@dberlin.org>.
|
Contributed by Daniel Berlin <dberlin@dberlin.org>.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "target.h"
|
#include "target.h"
|
|
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "optabs.h"
|
#include "optabs.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "lambda.h"
|
#include "lambda.h"
|
|
|
/* Linear loop transforms include any composition of interchange,
|
/* Linear loop transforms include any composition of interchange,
|
scaling, skewing, and reversal. They are used to change the
|
scaling, skewing, and reversal. They are used to change the
|
iteration order of loop nests in order to optimize data locality of
|
iteration order of loop nests in order to optimize data locality of
|
traversals, or remove dependences that prevent
|
traversals, or remove dependences that prevent
|
parallelization/vectorization/etc.
|
parallelization/vectorization/etc.
|
|
|
TODO: Determine reuse vectors/matrix and use it to determine optimal
|
TODO: Determine reuse vectors/matrix and use it to determine optimal
|
transform matrix for locality purposes.
|
transform matrix for locality purposes.
|
TODO: Completion of partial transforms. */
|
TODO: Completion of partial transforms. */
|
|
|
/* Gather statistics for loop interchange. LOOP is the loop being
|
/* Gather statistics for loop interchange. LOOP is the loop being
|
considered. The first loop in the considered loop nest is
|
considered. The first loop in the considered loop nest is
|
FIRST_LOOP, and consequently, the index of the considered loop is
|
FIRST_LOOP, and consequently, the index of the considered loop is
|
obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
|
obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
|
|
|
Initializes:
|
Initializes:
|
- DEPENDENCE_STEPS the sum of all the data dependence distances
|
- DEPENDENCE_STEPS the sum of all the data dependence distances
|
carried by loop LOOP,
|
carried by loop LOOP,
|
|
|
- NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
|
- NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
|
for which the loop LOOP is not carrying any dependence,
|
for which the loop LOOP is not carrying any dependence,
|
|
|
- ACCESS_STRIDES the sum of all the strides in LOOP.
|
- ACCESS_STRIDES the sum of all the strides in LOOP.
|
|
|
Example: for the following loop,
|
Example: for the following loop,
|
|
|
| loop_1 runs 1335 times
|
| loop_1 runs 1335 times
|
| loop_2 runs 1335 times
|
| loop_2 runs 1335 times
|
| A[{{0, +, 1}_1, +, 1335}_2]
|
| A[{{0, +, 1}_1, +, 1335}_2]
|
| B[{{0, +, 1}_1, +, 1335}_2]
|
| B[{{0, +, 1}_1, +, 1335}_2]
|
| endloop_2
|
| endloop_2
|
| A[{0, +, 1336}_1]
|
| A[{0, +, 1336}_1]
|
| endloop_1
|
| endloop_1
|
|
|
gather_interchange_stats (in loop_1) will return
|
gather_interchange_stats (in loop_1) will return
|
DEPENDENCE_STEPS = 3002
|
DEPENDENCE_STEPS = 3002
|
NB_DEPS_NOT_CARRIED_BY_LOOP = 5
|
NB_DEPS_NOT_CARRIED_BY_LOOP = 5
|
ACCESS_STRIDES = 10694
|
ACCESS_STRIDES = 10694
|
|
|
gather_interchange_stats (in loop_2) will return
|
gather_interchange_stats (in loop_2) will return
|
DEPENDENCE_STEPS = 3000
|
DEPENDENCE_STEPS = 3000
|
NB_DEPS_NOT_CARRIED_BY_LOOP = 7
|
NB_DEPS_NOT_CARRIED_BY_LOOP = 7
|
ACCESS_STRIDES = 8010
|
ACCESS_STRIDES = 8010
|
*/
|
*/
|
|
|
static void
|
static void
|
gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations ATTRIBUTE_UNUSED,
|
gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations ATTRIBUTE_UNUSED,
|
VEC (data_reference_p, heap) *datarefs ATTRIBUTE_UNUSED,
|
VEC (data_reference_p, heap) *datarefs ATTRIBUTE_UNUSED,
|
struct loop *loop ATTRIBUTE_UNUSED,
|
struct loop *loop ATTRIBUTE_UNUSED,
|
struct loop *first_loop ATTRIBUTE_UNUSED,
|
struct loop *first_loop ATTRIBUTE_UNUSED,
|
unsigned int *dependence_steps ATTRIBUTE_UNUSED,
|
unsigned int *dependence_steps ATTRIBUTE_UNUSED,
|
unsigned int *nb_deps_not_carried_by_loop ATTRIBUTE_UNUSED,
|
unsigned int *nb_deps_not_carried_by_loop ATTRIBUTE_UNUSED,
|
double_int *access_strides ATTRIBUTE_UNUSED)
|
double_int *access_strides ATTRIBUTE_UNUSED)
|
{
|
{
|
unsigned int i, j;
|
unsigned int i, j;
|
struct data_dependence_relation *ddr;
|
struct data_dependence_relation *ddr;
|
struct data_reference *dr;
|
struct data_reference *dr;
|
|
|
*dependence_steps = 0;
|
*dependence_steps = 0;
|
*nb_deps_not_carried_by_loop = 0;
|
*nb_deps_not_carried_by_loop = 0;
|
*access_strides = double_int_zero;
|
*access_strides = double_int_zero;
|
|
|
for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
|
for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
|
{
|
{
|
/* If we don't know anything about this dependence, or the distance
|
/* If we don't know anything about this dependence, or the distance
|
vector is NULL, or there is no dependence, then there is no reuse of
|
vector is NULL, or there is no dependence, then there is no reuse of
|
data. */
|
data. */
|
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
|
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
|
|| DDR_ARE_DEPENDENT (ddr) == chrec_known
|
|| DDR_ARE_DEPENDENT (ddr) == chrec_known
|
|| DDR_NUM_DIST_VECTS (ddr) == 0)
|
|| DDR_NUM_DIST_VECTS (ddr) == 0)
|
continue;
|
continue;
|
|
|
for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
|
for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
|
{
|
{
|
int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];
|
int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];
|
|
|
if (dist == 0)
|
if (dist == 0)
|
(*nb_deps_not_carried_by_loop) += 1;
|
(*nb_deps_not_carried_by_loop) += 1;
|
|
|
else if (dist < 0)
|
else if (dist < 0)
|
(*dependence_steps) += -dist;
|
(*dependence_steps) += -dist;
|
|
|
else
|
else
|
(*dependence_steps) += dist;
|
(*dependence_steps) += dist;
|
}
|
}
|
}
|
}
|
|
|
/* Compute the access strides. */
|
/* Compute the access strides. */
|
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
{
|
{
|
unsigned int it;
|
unsigned int it;
|
tree ref = DR_REF (dr);
|
tree ref = DR_REF (dr);
|
gimple stmt = DR_STMT (dr);
|
gimple stmt = DR_STMT (dr);
|
struct loop *stmt_loop = loop_containing_stmt (stmt);
|
struct loop *stmt_loop = loop_containing_stmt (stmt);
|
struct loop *inner_loop = first_loop->inner;
|
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))
|
&& !flow_loop_nested_p (inner_loop, stmt_loop))
|
continue;
|
continue;
|
|
|
for (it = 0; it < DR_NUM_DIMENSIONS (dr);
|
for (it = 0; it < DR_NUM_DIMENSIONS (dr);
|
it++, ref = TREE_OPERAND (ref, 0))
|
it++, ref = TREE_OPERAND (ref, 0))
|
{
|
{
|
int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), 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);
|
int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num);
|
tree array_size = TYPE_SIZE (TREE_TYPE (ref));
|
tree array_size = TYPE_SIZE (TREE_TYPE (ref));
|
double_int dstride;
|
double_int dstride;
|
|
|
if (array_size == NULL_TREE
|
if (array_size == NULL_TREE
|
|| TREE_CODE (array_size) != INTEGER_CST)
|
|| TREE_CODE (array_size) != INTEGER_CST)
|
continue;
|
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));
|
shwi_to_double_int (istride));
|
(*access_strides) = double_int_add (*access_strides, dstride);
|
(*access_strides) = double_int_add (*access_strides, dstride);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Attempt to apply interchange transformations to TRANS to maximize the
|
/* 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
|
Returns the new transform matrix. The smaller the reuse vector
|
distances in the inner loops, the fewer the cache misses.
|
distances in the inner loops, the fewer the cache misses.
|
FIRST_LOOP is the loop->num of the first loop in the analyzed loop
|
FIRST_LOOP is the loop->num of the first loop in the analyzed loop
|
nest. */
|
nest. */
|
|
|
|
|
static lambda_trans_matrix
|
static lambda_trans_matrix
|
try_interchange_loops (lambda_trans_matrix trans,
|
try_interchange_loops (lambda_trans_matrix trans,
|
unsigned int depth,
|
unsigned int depth,
|
VEC (ddr_p, heap) *dependence_relations,
|
VEC (ddr_p, heap) *dependence_relations,
|
VEC (data_reference_p, heap) *datarefs,
|
VEC (data_reference_p, heap) *datarefs,
|
struct loop *first_loop)
|
struct loop *first_loop)
|
{
|
{
|
bool res;
|
bool res;
|
struct loop *loop_i;
|
struct loop *loop_i;
|
struct loop *loop_j;
|
struct loop *loop_j;
|
unsigned int dependence_steps_i, dependence_steps_j;
|
unsigned int dependence_steps_i, dependence_steps_j;
|
double_int access_strides_i, access_strides_j;
|
double_int access_strides_i, access_strides_j;
|
double_int small, large, nb_iter;
|
double_int small, large, nb_iter;
|
double_int l1_cache_size, l2_cache_size;
|
double_int l1_cache_size, l2_cache_size;
|
int cmp;
|
int cmp;
|
unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
|
unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
|
struct data_dependence_relation *ddr;
|
struct data_dependence_relation *ddr;
|
|
|
if (VEC_length (ddr_p, dependence_relations) == 0)
|
if (VEC_length (ddr_p, dependence_relations) == 0)
|
return trans;
|
return trans;
|
|
|
/* When there is an unknown relation in the dependence_relations, we
|
/* When there is an unknown relation in the dependence_relations, we
|
know that it is no worth looking at this loop nest: give up. */
|
know that it is no worth looking at this loop nest: give up. */
|
ddr = VEC_index (ddr_p, dependence_relations, 0);
|
ddr = VEC_index (ddr_p, dependence_relations, 0);
|
if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
|
if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
|
return trans;
|
return trans;
|
|
|
l1_cache_size = uhwi_to_double_int (L1_CACHE_SIZE * 1024);
|
l1_cache_size = uhwi_to_double_int (L1_CACHE_SIZE * 1024);
|
l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
|
l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
|
|
|
/* LOOP_I is always the outer loop. */
|
/* LOOP_I is always the outer loop. */
|
for (loop_j = first_loop->inner;
|
for (loop_j = first_loop->inner;
|
loop_j;
|
loop_j;
|
loop_j = loop_j->inner)
|
loop_j = loop_j->inner)
|
for (loop_i = first_loop;
|
for (loop_i = first_loop;
|
loop_depth (loop_i) < loop_depth (loop_j);
|
loop_depth (loop_i) < loop_depth (loop_j);
|
loop_i = loop_i->inner)
|
loop_i = loop_i->inner)
|
{
|
{
|
gather_interchange_stats (dependence_relations, datarefs,
|
gather_interchange_stats (dependence_relations, datarefs,
|
loop_i, first_loop,
|
loop_i, first_loop,
|
&dependence_steps_i,
|
&dependence_steps_i,
|
&nb_deps_not_carried_by_i,
|
&nb_deps_not_carried_by_i,
|
&access_strides_i);
|
&access_strides_i);
|
gather_interchange_stats (dependence_relations, datarefs,
|
gather_interchange_stats (dependence_relations, datarefs,
|
loop_j, first_loop,
|
loop_j, first_loop,
|
&dependence_steps_j,
|
&dependence_steps_j,
|
&nb_deps_not_carried_by_j,
|
&nb_deps_not_carried_by_j,
|
&access_strides_j);
|
&access_strides_j);
|
|
|
/* Heuristics for loop interchange profitability:
|
/* Heuristics for loop interchange profitability:
|
|
|
0. Don't transform if the smallest stride is larger than
|
0. Don't transform if the smallest stride is larger than
|
the L2 cache, or if the largest stride multiplied by the
|
the L2 cache, or if the largest stride multiplied by the
|
number of iterations is smaller than the L1 cache.
|
number of iterations is smaller than the L1 cache.
|
|
|
1. (spatial locality) Inner loops should have smallest
|
1. (spatial locality) Inner loops should have smallest
|
dependence steps.
|
dependence steps.
|
|
|
2. (spatial locality) Inner loops should contain more
|
2. (spatial locality) Inner loops should contain more
|
dependence relations not carried by the loop.
|
dependence relations not carried by the loop.
|
|
|
3. (temporal locality) Inner loops should have smallest
|
3. (temporal locality) Inner loops should have smallest
|
array access strides.
|
array access strides.
|
*/
|
*/
|
|
|
cmp = double_int_ucmp (access_strides_i, access_strides_j);
|
cmp = double_int_ucmp (access_strides_i, access_strides_j);
|
small = cmp < 0 ? access_strides_i : access_strides_j;
|
small = cmp < 0 ? access_strides_i : access_strides_j;
|
large = cmp < 0 ? access_strides_j : access_strides_i;
|
large = cmp < 0 ? access_strides_j : access_strides_i;
|
|
|
if (double_int_ucmp (small, l2_cache_size) > 0)
|
if (double_int_ucmp (small, l2_cache_size) > 0)
|
continue;
|
continue;
|
|
|
res = cmp < 0 ?
|
res = cmp < 0 ?
|
estimated_loop_iterations (loop_j, false, &nb_iter):
|
estimated_loop_iterations (loop_j, false, &nb_iter):
|
estimated_loop_iterations (loop_i, false, &nb_iter);
|
estimated_loop_iterations (loop_i, false, &nb_iter);
|
|
|
if (res
|
if (res
|
&& double_int_ucmp (double_int_mul (large, nb_iter),
|
&& double_int_ucmp (double_int_mul (large, nb_iter),
|
l1_cache_size) < 0)
|
l1_cache_size) < 0)
|
continue;
|
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
|
|| nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
|
|| cmp < 0)
|
|| cmp < 0)
|
{
|
{
|
lambda_matrix_row_exchange (LTM_MATRIX (trans),
|
lambda_matrix_row_exchange (LTM_MATRIX (trans),
|
loop_depth (loop_i) - loop_depth (first_loop),
|
loop_depth (loop_i) - loop_depth (first_loop),
|
loop_depth (loop_j) - loop_depth (first_loop));
|
loop_depth (loop_j) - loop_depth (first_loop));
|
/* Validate the resulting matrix. When the transformation
|
/* Validate the resulting matrix. When the transformation
|
is not valid, reverse to the previous transformation. */
|
is not valid, reverse to the previous transformation. */
|
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
|
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
|
lambda_matrix_row_exchange (LTM_MATRIX (trans),
|
lambda_matrix_row_exchange (LTM_MATRIX (trans),
|
loop_depth (loop_i) - loop_depth (first_loop),
|
loop_depth (loop_i) - loop_depth (first_loop),
|
loop_depth (loop_j) - loop_depth (first_loop));
|
loop_depth (loop_j) - loop_depth (first_loop));
|
}
|
}
|
}
|
}
|
|
|
return trans;
|
return trans;
|
}
|
}
|
|
|
/* Return the number of nested loops in LOOP_NEST, or 0 if the loops
|
/* Return the number of nested loops in LOOP_NEST, or 0 if the loops
|
are not perfectly nested. */
|
are not perfectly nested. */
|
|
|
unsigned int
|
unsigned int
|
perfect_loop_nest_depth (struct loop *loop_nest)
|
perfect_loop_nest_depth (struct loop *loop_nest)
|
{
|
{
|
struct loop *temp;
|
struct loop *temp;
|
unsigned int depth = 1;
|
unsigned int depth = 1;
|
|
|
/* If it's not a loop nest, we don't want it. We also don't handle
|
/* If it's not a loop nest, we don't want it. We also don't handle
|
sibling loops properly, which are loops of the following form:
|
sibling loops properly, which are loops of the following form:
|
|
|
| for (i = 0; i < 50; i++)
|
| for (i = 0; i < 50; i++)
|
| {
|
| {
|
| for (j = 0; j < 50; j++)
|
| for (j = 0; j < 50; j++)
|
| {
|
| {
|
| ...
|
| ...
|
| }
|
| }
|
| for (j = 0; j < 50; j++)
|
| for (j = 0; j < 50; j++)
|
| {
|
| {
|
| ...
|
| ...
|
| }
|
| }
|
| }
|
| }
|
*/
|
*/
|
|
|
if (!loop_nest->inner || !single_exit (loop_nest))
|
if (!loop_nest->inner || !single_exit (loop_nest))
|
return 0;
|
return 0;
|
|
|
for (temp = loop_nest->inner; temp; temp = temp->inner)
|
for (temp = loop_nest->inner; temp; temp = temp->inner)
|
{
|
{
|
/* If we have a sibling loop or multiple exit edges, jump ship. */
|
/* If we have a sibling loop or multiple exit edges, jump ship. */
|
if (temp->next || !single_exit (temp))
|
if (temp->next || !single_exit (temp))
|
return 0;
|
return 0;
|
|
|
depth++;
|
depth++;
|
}
|
}
|
|
|
return depth;
|
return depth;
|
}
|
}
|
|
|
/* Perform a set of linear transforms on loops. */
|
/* Perform a set of linear transforms on loops. */
|
|
|
void
|
void
|
linear_transform_loops (void)
|
linear_transform_loops (void)
|
{
|
{
|
bool modified = false;
|
bool modified = false;
|
loop_iterator li;
|
loop_iterator li;
|
VEC(tree,heap) *oldivs = NULL;
|
VEC(tree,heap) *oldivs = NULL;
|
VEC(tree,heap) *invariants = NULL;
|
VEC(tree,heap) *invariants = NULL;
|
VEC(tree,heap) *lambda_parameters = NULL;
|
VEC(tree,heap) *lambda_parameters = NULL;
|
VEC(gimple,heap) *remove_ivs = VEC_alloc (gimple, heap, 3);
|
VEC(gimple,heap) *remove_ivs = VEC_alloc (gimple, heap, 3);
|
struct loop *loop_nest;
|
struct loop *loop_nest;
|
gimple oldiv_stmt;
|
gimple oldiv_stmt;
|
unsigned i;
|
unsigned i;
|
|
|
FOR_EACH_LOOP (li, loop_nest, 0)
|
FOR_EACH_LOOP (li, loop_nest, 0)
|
{
|
{
|
unsigned int depth = 0;
|
unsigned int depth = 0;
|
VEC (ddr_p, heap) *dependence_relations;
|
VEC (ddr_p, heap) *dependence_relations;
|
VEC (data_reference_p, heap) *datarefs;
|
VEC (data_reference_p, heap) *datarefs;
|
|
|
lambda_loopnest before, after;
|
lambda_loopnest before, after;
|
lambda_trans_matrix trans;
|
lambda_trans_matrix trans;
|
struct obstack lambda_obstack;
|
struct obstack lambda_obstack;
|
struct loop *loop;
|
struct loop *loop;
|
VEC(loop_p,heap) *nest;
|
VEC(loop_p,heap) *nest;
|
|
|
depth = perfect_loop_nest_depth (loop_nest);
|
depth = perfect_loop_nest_depth (loop_nest);
|
if (depth == 0)
|
if (depth == 0)
|
continue;
|
continue;
|
|
|
nest = VEC_alloc (loop_p, heap, 3);
|
nest = VEC_alloc (loop_p, heap, 3);
|
for (loop = loop_nest; loop; loop = loop->inner)
|
for (loop = loop_nest; loop; loop = loop->inner)
|
VEC_safe_push (loop_p, heap, nest, loop);
|
VEC_safe_push (loop_p, heap, nest, loop);
|
|
|
gcc_obstack_init (&lambda_obstack);
|
gcc_obstack_init (&lambda_obstack);
|
VEC_truncate (tree, oldivs, 0);
|
VEC_truncate (tree, oldivs, 0);
|
VEC_truncate (tree, invariants, 0);
|
VEC_truncate (tree, invariants, 0);
|
VEC_truncate (tree, lambda_parameters, 0);
|
VEC_truncate (tree, lambda_parameters, 0);
|
|
|
datarefs = VEC_alloc (data_reference_p, heap, 10);
|
datarefs = VEC_alloc (data_reference_p, heap, 10);
|
dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
|
dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
|
if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs,
|
if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs,
|
&dependence_relations))
|
&dependence_relations))
|
goto free_and_continue;
|
goto free_and_continue;
|
|
|
lambda_collect_parameters (datarefs, &lambda_parameters);
|
lambda_collect_parameters (datarefs, &lambda_parameters);
|
if (!lambda_compute_access_matrices (datarefs, lambda_parameters, nest))
|
if (!lambda_compute_access_matrices (datarefs, lambda_parameters, nest))
|
goto free_and_continue;
|
goto free_and_continue;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
dump_ddrs (dump_file, dependence_relations);
|
dump_ddrs (dump_file, dependence_relations);
|
|
|
/* Build the transformation matrix. */
|
/* Build the transformation matrix. */
|
trans = lambda_trans_matrix_new (depth, depth);
|
trans = lambda_trans_matrix_new (depth, depth);
|
lambda_matrix_id (LTM_MATRIX (trans), depth);
|
lambda_matrix_id (LTM_MATRIX (trans), depth);
|
trans = try_interchange_loops (trans, depth, dependence_relations,
|
trans = try_interchange_loops (trans, depth, dependence_relations,
|
datarefs, loop_nest);
|
datarefs, loop_nest);
|
|
|
if (lambda_trans_matrix_id_p (trans))
|
if (lambda_trans_matrix_id_p (trans))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
|
fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
|
goto free_and_continue;
|
goto free_and_continue;
|
}
|
}
|
|
|
/* Check whether the transformation is legal. */
|
/* Check whether the transformation is legal. */
|
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
|
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
|
fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
|
goto free_and_continue;
|
goto free_and_continue;
|
}
|
}
|
|
|
before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
|
before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
|
&invariants, &lambda_obstack);
|
&invariants, &lambda_obstack);
|
|
|
if (!before)
|
if (!before)
|
goto free_and_continue;
|
goto free_and_continue;
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Before:\n");
|
fprintf (dump_file, "Before:\n");
|
print_lambda_loopnest (dump_file, before, 'i');
|
print_lambda_loopnest (dump_file, before, 'i');
|
}
|
}
|
|
|
after = lambda_loopnest_transform (before, trans, &lambda_obstack);
|
after = lambda_loopnest_transform (before, trans, &lambda_obstack);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "After:\n");
|
fprintf (dump_file, "After:\n");
|
print_lambda_loopnest (dump_file, after, 'u');
|
print_lambda_loopnest (dump_file, after, 'u');
|
}
|
}
|
|
|
lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
|
lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
|
&remove_ivs,
|
&remove_ivs,
|
after, trans, &lambda_obstack);
|
after, trans, &lambda_obstack);
|
modified = true;
|
modified = true;
|
|
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "Successfully transformed loop.\n");
|
fprintf (dump_file, "Successfully transformed loop.\n");
|
|
|
free_and_continue:
|
free_and_continue:
|
obstack_free (&lambda_obstack, NULL);
|
obstack_free (&lambda_obstack, NULL);
|
free_dependence_relations (dependence_relations);
|
free_dependence_relations (dependence_relations);
|
free_data_refs (datarefs);
|
free_data_refs (datarefs);
|
VEC_free (loop_p, heap, nest);
|
VEC_free (loop_p, heap, nest);
|
}
|
}
|
|
|
for (i = 0; VEC_iterate (gimple, remove_ivs, i, oldiv_stmt); i++)
|
for (i = 0; VEC_iterate (gimple, remove_ivs, i, oldiv_stmt); i++)
|
remove_iv (oldiv_stmt);
|
remove_iv (oldiv_stmt);
|
|
|
VEC_free (tree, heap, oldivs);
|
VEC_free (tree, heap, oldivs);
|
VEC_free (tree, heap, invariants);
|
VEC_free (tree, heap, invariants);
|
VEC_free (gimple, heap, remove_ivs);
|
VEC_free (gimple, heap, remove_ivs);
|
scev_reset ();
|
scev_reset ();
|
|
|
if (modified)
|
if (modified)
|
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
|
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
|
}
|
}
|
|
|
