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, 51 Franklin Street, Fifth Floor, Boston, MA
25 #include "coretypes.h"
32 #include "basic-block.h"
33 #include "diagnostic.h"
34 #include "tree-flow.h"
35 #include "tree-dump.h"
40 #include "tree-chrec.h"
41 #include "tree-data-ref.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-pass.h"
46 /* Linear loop transforms include any composition of interchange,
47 scaling, skewing, and reversal. They are used to change the
48 iteration order of loop nests in order to optimize data locality of
49 traversals, or remove dependences that prevent
50 parallelization/vectorization/etc.
52 TODO: Determine reuse vectors/matrix and use it to determine optimal
53 transform matrix for locality purposes.
54 TODO: Completion of partial transforms. */
56 /* Gather statistics for loop interchange. LOOP is the loop being
57 considered. The first loop in the considered loop nest is
58 FIRST_LOOP, and consequently, the index of the considered loop is
59 obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
62 - DEPENDENCE_STEPS the sum of all the data dependence distances
65 - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
66 for which the loop LOOP is not carrying any dependence,
68 - ACCESS_STRIDES the sum of all the strides in LOOP.
70 Example: for the following loop,
72 | loop_1 runs 1335 times
73 | loop_2 runs 1335 times
74 | A[{{0, +, 1}_1, +, 1335}_2]
75 | B[{{0, +, 1}_1, +, 1335}_2]
80 gather_interchange_stats (in loop_1) will return
81 DEPENDENCE_STEPS = 3002
82 NB_DEPS_NOT_CARRIED_BY_LOOP = 5
83 ACCESS_STRIDES = 10694
85 gather_interchange_stats (in loop_2) will return
86 DEPENDENCE_STEPS = 3000
87 NB_DEPS_NOT_CARRIED_BY_LOOP = 7
92 gather_interchange_stats (VEC (ddr_p
, heap
) *dependence_relations
,
93 VEC (data_reference_p
, heap
) *datarefs
,
95 struct loop
*first_loop
,
96 unsigned int *dependence_steps
,
97 unsigned int *nb_deps_not_carried_by_loop
,
98 unsigned int *access_strides
)
101 struct data_dependence_relation
*ddr
;
102 struct data_reference
*dr
;
104 *dependence_steps
= 0;
105 *nb_deps_not_carried_by_loop
= 0;
108 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
110 /* If we don't know anything about this dependence, or the distance
111 vector is NULL, or there is no dependence, then there is no reuse of
113 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
114 || DDR_ARE_DEPENDENT (ddr
) == chrec_known
115 || DDR_NUM_DIST_VECTS (ddr
) == 0)
118 for (j
= 0; j
< DDR_NUM_DIST_VECTS (ddr
); j
++)
120 int dist
= DDR_DIST_VECT (ddr
, j
)[loop
->depth
- first_loop
->depth
];
123 (*nb_deps_not_carried_by_loop
) += 1;
126 (*dependence_steps
) += -dist
;
129 (*dependence_steps
) += dist
;
133 /* Compute the access strides. */
134 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
137 tree stmt
= DR_STMT (dr
);
138 struct loop
*stmt_loop
= loop_containing_stmt (stmt
);
139 struct loop
*inner_loop
= first_loop
->inner
;
141 if (inner_loop
!= stmt_loop
142 && !flow_loop_nested_p (inner_loop
, stmt_loop
))
144 for (it
= 0; it
< DR_NUM_DIMENSIONS (dr
); it
++)
146 tree chrec
= DR_ACCESS_FN (dr
, it
);
147 tree tstride
= evolution_part_in_loop_num
150 if (tstride
== NULL_TREE
151 || TREE_CODE (tstride
) != INTEGER_CST
)
154 (*access_strides
) += int_cst_value (tstride
);
159 /* Attempt to apply interchange transformations to TRANS to maximize the
160 spatial and temporal locality of the loop.
161 Returns the new transform matrix. The smaller the reuse vector
162 distances in the inner loops, the fewer the cache misses.
163 FIRST_LOOP is the loop->num of the first loop in the analyzed loop
167 static lambda_trans_matrix
168 try_interchange_loops (lambda_trans_matrix trans
,
170 VEC (ddr_p
, heap
) *dependence_relations
,
171 VEC (data_reference_p
, heap
) *datarefs
,
172 struct loop
*first_loop
)
176 unsigned int dependence_steps_i
, dependence_steps_j
;
177 unsigned int access_strides_i
, access_strides_j
;
178 unsigned int nb_deps_not_carried_by_i
, nb_deps_not_carried_by_j
;
179 struct data_dependence_relation
*ddr
;
181 if (VEC_length (ddr_p
, dependence_relations
) == 0)
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
= VEC_index (ddr_p
, dependence_relations
, 0);
187 if (ddr
== NULL
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
190 /* LOOP_I is always the outer loop. */
191 for (loop_j
= first_loop
->inner
;
193 loop_j
= loop_j
->inner
)
194 for (loop_i
= first_loop
;
195 loop_i
->depth
< loop_j
->depth
;
196 loop_i
= loop_i
->inner
)
198 gather_interchange_stats (dependence_relations
, datarefs
,
201 &nb_deps_not_carried_by_i
,
203 gather_interchange_stats (dependence_relations
, datarefs
,
206 &nb_deps_not_carried_by_j
,
209 /* Heuristics for loop interchange profitability:
211 1. (spatial locality) Inner loops should have smallest
214 2. (spatial locality) Inner loops should contain more
215 dependence relations not carried by the loop.
217 3. (temporal locality) Inner loops should have smallest
218 array access strides.
220 if (dependence_steps_i
< dependence_steps_j
221 || nb_deps_not_carried_by_i
> nb_deps_not_carried_by_j
222 || access_strides_i
< access_strides_j
)
224 lambda_matrix_row_exchange (LTM_MATRIX (trans
),
225 loop_i
->depth
- first_loop
->depth
,
226 loop_j
->depth
- first_loop
->depth
);
227 /* Validate the resulting matrix. When the transformation
228 is not valid, reverse to the previous transformation. */
229 if (!lambda_transform_legal_p (trans
, depth
, dependence_relations
))
230 lambda_matrix_row_exchange (LTM_MATRIX (trans
),
231 loop_i
->depth
- first_loop
->depth
,
232 loop_j
->depth
- first_loop
->depth
);
239 /* Perform a set of linear transforms on LOOPS. */
242 linear_transform_loops (struct loops
*loops
)
245 VEC(tree
,heap
) *oldivs
= NULL
;
246 VEC(tree
,heap
) *invariants
= NULL
;
248 for (i
= 1; i
< loops
->num
; i
++)
250 unsigned int depth
= 0;
251 VEC (ddr_p
, heap
) *dependence_relations
;
252 VEC (data_reference_p
, heap
) *datarefs
;
253 struct loop
*loop_nest
= loops
->parray
[i
];
255 lambda_loopnest before
, after
;
256 lambda_trans_matrix trans
;
257 bool problem
= false;
258 bool need_perfect_nest
= false;
259 /* If it's not a loop nest, we don't want it.
260 We also don't handle sibling loops properly,
261 which are loops of the following form:
262 for (i = 0; i < 50; i++)
264 for (j = 0; j < 50; j++)
268 for (j = 0; j < 50; j++)
273 if (!loop_nest
|| !loop_nest
->inner
)
275 VEC_truncate (tree
, oldivs
, 0);
276 VEC_truncate (tree
, invariants
, 0);
278 for (temp
= loop_nest
->inner
; temp
; temp
= temp
->inner
)
280 /* If we have a sibling loop or multiple exit edges, jump ship. */
281 if (temp
->next
|| !temp
->single_exit
)
291 /* Analyze data references and dependence relations using scev. */
293 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
294 dependence_relations
= VEC_alloc (ddr_p
, heap
, 10 * 10);
295 compute_data_dependences_for_loop (loop_nest
, true, &datarefs
,
296 &dependence_relations
);
298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
299 dump_ddrs (dump_file
, dependence_relations
);
301 /* Build the transformation matrix. */
302 trans
= lambda_trans_matrix_new (depth
, depth
);
303 lambda_matrix_id (LTM_MATRIX (trans
), depth
);
304 trans
= try_interchange_loops (trans
, depth
, dependence_relations
,
305 datarefs
, loop_nest
);
307 if (lambda_trans_matrix_id_p (trans
))
310 fprintf (dump_file
, "Won't transform loop. Optimal transform is the identity transform\n");
314 /* Check whether the transformation is legal. */
315 if (!lambda_transform_legal_p (trans
, depth
, dependence_relations
))
318 fprintf (dump_file
, "Can't transform loop, transform is illegal:\n");
322 if (!perfect_nest_p (loop_nest
))
323 need_perfect_nest
= true;
325 before
= gcc_loopnest_to_lambda_loopnest (loops
,
334 fprintf (dump_file
, "Before:\n");
335 print_lambda_loopnest (dump_file
, before
, 'i');
338 after
= lambda_loopnest_transform (before
, trans
);
342 fprintf (dump_file
, "After:\n");
343 print_lambda_loopnest (dump_file
, after
, 'u');
346 lambda_loopnest_to_gcc_loopnest (loop_nest
, oldivs
, invariants
,
350 fprintf (dump_file
, "Successfully transformed loop.\n");
352 free_dependence_relations (dependence_relations
);
353 free_data_refs (datarefs
);
356 VEC_free (tree
, heap
, oldivs
);
357 VEC_free (tree
, heap
, invariants
);
359 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_full_phi
);