1 /* Linear Loop transforms
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 #include "coretypes.h"
33 #include "basic-block.h"
34 #include "diagnostic.h"
35 #include "tree-flow.h"
36 #include "tree-dump.h"
41 #include "tree-chrec.h"
42 #include "tree-data-ref.h"
43 #include "tree-scalar-evolution.h"
44 #include "tree-pass.h"
48 /* Linear loop transforms include any composition of interchange,
49 scaling, skewing, and reversal. They are used to change the
50 iteration order of loop nests in order to optimize data locality of
51 traversals, or remove dependences that prevent
52 parallelization/vectorization/etc.
54 TODO: Determine reuse vectors/matrix and use it to determine optimal
55 transform matrix for locality purposes.
56 TODO: Completion of partial transforms. */
58 /* Gather statistics for loop interchange. LOOP is the loop being
59 considered. The first loop in the considered loop nest is
60 FIRST_LOOP, and consequently, the index of the considered loop is
61 obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
64 - DEPENDENCE_STEPS the sum of all the data dependence distances
67 - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
68 for which the loop LOOP is not carrying any dependence,
70 - ACCESS_STRIDES the sum of all the strides in LOOP.
72 Example: for the following loop,
74 | loop_1 runs 1335 times
75 | loop_2 runs 1335 times
76 | A[{{0, +, 1}_1, +, 1335}_2]
77 | B[{{0, +, 1}_1, +, 1335}_2]
82 gather_interchange_stats (in loop_1) will return
83 DEPENDENCE_STEPS = 3002
84 NB_DEPS_NOT_CARRIED_BY_LOOP = 5
85 ACCESS_STRIDES = 10694
87 gather_interchange_stats (in loop_2) will return
88 DEPENDENCE_STEPS = 3000
89 NB_DEPS_NOT_CARRIED_BY_LOOP = 7
94 gather_interchange_stats (varray_type dependence_relations
,
97 struct loop
*first_loop
,
98 unsigned int *dependence_steps
,
99 unsigned int *nb_deps_not_carried_by_loop
,
100 unsigned int *access_strides
)
104 *dependence_steps
= 0;
105 *nb_deps_not_carried_by_loop
= 0;
108 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
111 struct data_dependence_relation
*ddr
=
112 (struct data_dependence_relation
*)
113 VARRAY_GENERIC_PTR (dependence_relations
, i
);
115 /* If we don't know anything about this dependence, or the distance
116 vector is NULL, or there is no dependence, then there is no reuse of
119 if (DDR_DIST_VECT (ddr
) == NULL
120 || DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
121 || DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
126 dist
= DDR_DIST_VECT (ddr
)[loop
->depth
- first_loop
->depth
];
128 (*nb_deps_not_carried_by_loop
) += 1;
130 (*dependence_steps
) += -dist
;
132 (*dependence_steps
) += dist
;
135 /* Compute the access strides. */
136 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
139 struct data_reference
*dr
= VARRAY_GENERIC_PTR (datarefs
, i
);
140 tree stmt
= DR_STMT (dr
);
141 struct loop
*stmt_loop
= loop_containing_stmt (stmt
);
142 struct loop
*inner_loop
= first_loop
->inner
;
144 if (inner_loop
!= stmt_loop
145 && !flow_loop_nested_p (inner_loop
, stmt_loop
))
147 for (it
= 0; it
< DR_NUM_DIMENSIONS (dr
); it
++)
149 tree chrec
= DR_ACCESS_FN (dr
, it
);
150 tree tstride
= evolution_part_in_loop_num
153 if (tstride
== NULL_TREE
154 || TREE_CODE (tstride
) != INTEGER_CST
)
157 (*access_strides
) += int_cst_value (tstride
);
162 /* Attempt to apply interchange transformations to TRANS to maximize the
163 spatial and temporal locality of the loop.
164 Returns the new transform matrix. The smaller the reuse vector
165 distances in the inner loops, the fewer the cache misses.
166 FIRST_LOOP is the loop->num of the first loop in the analyzed loop
170 static lambda_trans_matrix
171 try_interchange_loops (lambda_trans_matrix trans
,
173 varray_type dependence_relations
,
174 varray_type datarefs
,
175 struct loop
*first_loop
)
179 unsigned int dependence_steps_i
, dependence_steps_j
;
180 unsigned int access_strides_i
, access_strides_j
;
181 unsigned int nb_deps_not_carried_by_i
, nb_deps_not_carried_by_j
;
182 struct data_dependence_relation
*ddr
;
184 /* When there is an unknown relation in the dependence_relations, we
185 know that it is no worth looking at this loop nest: give up. */
186 ddr
= (struct data_dependence_relation
*)
187 VARRAY_GENERIC_PTR (dependence_relations
, 0);
188 if (ddr
== NULL
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
191 /* LOOP_I is always the outer loop. */
192 for (loop_j
= first_loop
->inner
;
194 loop_j
= loop_j
->inner
)
195 for (loop_i
= first_loop
;
196 loop_i
->depth
< loop_j
->depth
;
197 loop_i
= loop_i
->inner
)
199 gather_interchange_stats (dependence_relations
, datarefs
,
202 &nb_deps_not_carried_by_i
,
204 gather_interchange_stats (dependence_relations
, datarefs
,
207 &nb_deps_not_carried_by_j
,
210 /* Heuristics for loop interchange profitability:
212 1. (spatial locality) Inner loops should have smallest
215 2. (spatial locality) Inner loops should contain more
216 dependence relations not carried by the loop.
218 3. (temporal locality) Inner loops should have smallest
219 array access strides.
221 if (dependence_steps_i
< dependence_steps_j
222 || nb_deps_not_carried_by_i
> nb_deps_not_carried_by_j
223 || access_strides_i
< access_strides_j
)
225 lambda_matrix_row_exchange (LTM_MATRIX (trans
),
226 loop_i
->depth
- first_loop
->depth
,
227 loop_j
->depth
- first_loop
->depth
);
228 /* Validate the resulting matrix. When the transformation
229 is not valid, reverse to the previous transformation. */
230 if (!lambda_transform_legal_p (trans
, depth
, dependence_relations
))
231 lambda_matrix_row_exchange (LTM_MATRIX (trans
),
232 loop_i
->depth
- first_loop
->depth
,
233 loop_j
->depth
- first_loop
->depth
);
240 /* Perform a set of linear transforms on LOOPS. */
243 linear_transform_loops (struct loops
*loops
)
246 VEC(tree
,gc
) *oldivs
= NULL
; /* FIXME:These should really be on the
247 heap. (nathan 2005/04/15)*/
248 VEC(tree
,gc
) *invariants
= NULL
; /* FIXME:Likewise. */
250 for (i
= 1; i
< loops
->num
; i
++)
252 unsigned int depth
= 0;
253 varray_type datarefs
;
254 varray_type dependence_relations
;
255 struct loop
*loop_nest
= loops
->parray
[i
];
257 lambda_loopnest before
, after
;
258 lambda_trans_matrix trans
;
259 bool problem
= false;
260 bool need_perfect_nest
= false;
261 /* If it's not a loop nest, we don't want it.
262 We also don't handle sibling loops properly,
263 which are loops of the following form:
264 for (i = 0; i < 50; i++)
266 for (j = 0; j < 50; j++)
270 for (j = 0; j < 50; j++)
275 if (!loop_nest
|| !loop_nest
->inner
)
277 VEC_truncate (tree
, oldivs
, 0);
278 VEC_truncate (tree
, invariants
, 0);
280 for (temp
= loop_nest
->inner
; temp
; temp
= temp
->inner
)
282 /* If we have a sibling loop or multiple exit edges, jump ship. */
283 if (temp
->next
|| !temp
->single_exit
)
293 /* Analyze data references and dependence relations using scev. */
295 VARRAY_GENERIC_PTR_INIT (datarefs
, 10, "datarefs");
296 VARRAY_GENERIC_PTR_INIT (dependence_relations
, 10,
297 "dependence_relations");
300 compute_data_dependences_for_loop (depth
, loop_nest
,
301 &datarefs
, &dependence_relations
);
302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
305 for (j
= 0; j
< VARRAY_ACTIVE_SIZE (dependence_relations
); j
++)
307 struct data_dependence_relation
*ddr
=
308 (struct data_dependence_relation
*)
309 VARRAY_GENERIC_PTR (dependence_relations
, j
);
311 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
313 fprintf (dump_file
, "DISTANCE_V (");
314 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
),
315 DDR_SIZE_VECT (ddr
));
316 fprintf (dump_file
, ")\n");
317 fprintf (dump_file
, "DIRECTION_V (");
318 print_lambda_vector (dump_file
, DDR_DIR_VECT (ddr
),
319 DDR_SIZE_VECT (ddr
));
320 fprintf (dump_file
, ")\n");
323 fprintf (dump_file
, "\n\n");
325 /* Build the transformation matrix. */
326 trans
= lambda_trans_matrix_new (depth
, depth
);
327 lambda_matrix_id (LTM_MATRIX (trans
), depth
);
329 trans
= try_interchange_loops (trans
, depth
, dependence_relations
,
330 datarefs
, loop_nest
);
332 if (lambda_trans_matrix_id_p (trans
))
335 fprintf (dump_file
, "Won't transform loop. Optimal transform is the identity transform\n");
339 /* Check whether the transformation is legal. */
340 if (!lambda_transform_legal_p (trans
, depth
, dependence_relations
))
343 fprintf (dump_file
, "Can't transform loop, transform is illegal:\n");
346 if (!perfect_nest_p (loop_nest
))
347 need_perfect_nest
= true;
348 before
= gcc_loopnest_to_lambda_loopnest (loops
,
357 fprintf (dump_file
, "Before:\n");
358 print_lambda_loopnest (dump_file
, before
, 'i');
361 after
= lambda_loopnest_transform (before
, trans
);
364 fprintf (dump_file
, "After:\n");
365 print_lambda_loopnest (dump_file
, after
, 'u');
367 lambda_loopnest_to_gcc_loopnest (loop_nest
, oldivs
, invariants
,
370 fprintf (dump_file
, "Successfully transformed loop.\n");
371 free_dependence_relations (dependence_relations
);
372 free_data_refs (datarefs
);
374 VEC_free (tree
, gc
, oldivs
);
375 VEC_free (tree
, gc
, invariants
);
377 update_ssa (TODO_update_ssa
);
378 rewrite_into_loop_closed_ssa (NULL
);