/* Linear Loop transforms
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "target.h"
transform matrix for locality purposes.
TODO: Completion of partial transforms. */
-/* Gather statistics for loop interchange. LOOP_NUMBER is a relative
- index in the considered loop nest. The first loop in the
- considered loop nest is FIRST_LOOP, and consequently the index of
- the considered loop is obtained by FIRST_LOOP + LOOP_NUMBER.
+/* Gather statistics for loop interchange. LOOP is the loop being
+ 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_NUMBER,
+ carried by loop LOOP,
- NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
- for which the loop LOOP_NUMBER 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_NUMBER.
+ - ACCESS_STRIDES the sum of all the strides in LOOP.
Example: for the following loop,
DEPENDENCE_STEPS = 3000
NB_DEPS_NOT_CARRIED_BY_LOOP = 7
ACCESS_STRIDES = 8010
- */
+*/
static void
gather_interchange_stats (varray_type dependence_relations,
varray_type datarefs,
- unsigned int loop_number,
- unsigned int first_loop,
+ struct loop *loop,
+ struct loop *first_loop,
unsigned int *dependence_steps,
unsigned int *nb_deps_not_carried_by_loop,
unsigned int *access_strides)
(struct data_dependence_relation *)
VARRAY_GENERIC_PTR (dependence_relations, i);
- /* Compute the dependence strides. */
+ /* 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
+ data. */
- if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- {
- (*dependence_steps) += 0;
- continue;
- }
+ if (DDR_DIST_VECT (ddr) == NULL
+ || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
+ || DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ continue;
+
- /* When we know that there is no dependence, we know that there
- is no reuse of the data. */
- if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- {
- (*dependence_steps) += 0;
- continue;
- }
- dist = DDR_DIST_VECT (ddr)[loop_number];
+
+ dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth];
if (dist == 0)
(*nb_deps_not_carried_by_loop) += 1;
else if (dist < 0)
struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
tree stmt = DR_STMT (dr);
struct loop *stmt_loop = loop_containing_stmt (stmt);
- struct loop *inner_loop = current_loops->parray[first_loop + 1];
-
- if (!flow_loop_nested_p (inner_loop, stmt_loop)
- && inner_loop->num != stmt_loop->num)
+ struct loop *inner_loop = first_loop->inner;
+
+ if (inner_loop != stmt_loop
+ && !flow_loop_nested_p (inner_loop, stmt_loop))
continue;
-
for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
{
tree chrec = DR_ACCESS_FN (dr, it);
tree tstride = evolution_part_in_loop_num
- (chrec, first_loop + loop_number);
+ (chrec, loop->num);
if (tstride == NULL_TREE
|| TREE_CODE (tstride) != INTEGER_CST)
}
}
-/* Apply to TRANS any loop interchange that minimize inner loop steps.
+/* Attempt to apply interchange transformations to TRANS to maximize the
+ 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
unsigned int depth,
varray_type dependence_relations,
varray_type datarefs,
- unsigned int first_loop)
+ struct loop *first_loop)
{
- unsigned int loop_i, loop_j;
+ struct loop *loop_i;
+ struct loop *loop_j;
unsigned int dependence_steps_i, dependence_steps_j;
unsigned int access_strides_i, access_strides_j;
unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
return trans;
/* LOOP_I is always the outer loop. */
- for (loop_j = 1; loop_j < depth; loop_j++)
- for (loop_i = 0; loop_i < loop_j; loop_i++)
+ for (loop_j = first_loop->inner;
+ loop_j;
+ loop_j = loop_j->inner)
+ for (loop_i = first_loop;
+ loop_i->depth < loop_j->depth;
+ loop_i = loop_i->inner)
{
gather_interchange_stats (dependence_relations, datarefs,
loop_i, first_loop,
|| nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
|| access_strides_i < access_strides_j)
{
- lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_i->depth - first_loop->depth,
+ loop_j->depth - first_loop->depth);
/* 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_i, loop_j);
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_i->depth - first_loop->depth,
+ loop_j->depth - first_loop->depth);
}
}
linear_transform_loops (struct loops *loops)
{
unsigned int i;
-
- compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
+ VEC(tree,heap) *oldivs = NULL;
+ VEC(tree,heap) *invariants = NULL;
+
for (i = 1; i < loops->num; i++)
{
unsigned int depth = 0;
varray_type dependence_relations;
struct loop *loop_nest = loops->parray[i];
struct loop *temp;
- VEC (tree) *oldivs = NULL;
- VEC (tree) *invariants = NULL;
lambda_loopnest before, after;
lambda_trans_matrix trans;
bool problem = false;
...
}
} */
- if (!loop_nest->inner)
+ if (!loop_nest || !loop_nest->inner)
continue;
+ VEC_truncate (tree, oldivs, 0);
+ VEC_truncate (tree, invariants, 0);
depth = 1;
for (temp = loop_nest->inner; temp; temp = temp->inner)
{
- flow_loop_scan (temp, LOOP_ALL);
/* If we have a sibling loop or multiple exit edges, jump ship. */
- if (temp->next || temp->num_exits != 1)
+ if (temp->next || !temp->single_exit)
{
problem = true;
break;
"dependence_relations");
- compute_data_dependences_for_loop (depth, loop_nest,
+ compute_data_dependences_for_loop (loop_nest, true,
&datarefs, &dependence_relations);
if (dump_file && (dump_flags & TDF_DETAILS))
{
lambda_matrix_id (LTM_MATRIX (trans), depth);
trans = try_interchange_loops (trans, depth, dependence_relations,
- datarefs, loop_nest->num);
+ datarefs, loop_nest);
if (lambda_trans_matrix_id_p (trans))
{
after, trans);
if (dump_file)
fprintf (dump_file, "Successfully transformed loop.\n");
- oldivs = NULL;
- invariants = NULL;
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
}
- free_df ();
+ VEC_free (tree, heap, oldivs);
+ VEC_free (tree, heap, invariants);
scev_reset ();
- rewrite_into_loop_closed_ssa ();
-#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
-#endif
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
}
OSDN Git Service
