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 /* When there is an unknown relation in the dependence_relations, we
182 know that it is no worth looking at this loop nest: give up. */
183 ddr
= VEC_index (ddr_p
, dependence_relations
, 0);
184 if (ddr
== NULL
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
187 /* LOOP_I is always the outer loop. */
188 for (loop_j
= first_loop
->inner
;
190 loop_j
= loop_j
->inner
)
191 for (loop_i
= first_loop
;
192 loop_i
->depth
< loop_j
->depth
;
193 loop_i
= loop_i
->inner
)
195 gather_interchange_stats (dependence_relations
, datarefs
,
198 &nb_deps_not_carried_by_i
,
200 gather_interchange_stats (dependence_relations
, datarefs
,
203 &nb_deps_not_carried_by_j
,
206 /* Heuristics for loop interchange profitability:
208 1. (spatial locality) Inner loops should have smallest
211 2. (spatial locality) Inner loops should contain more
212 dependence relations not carried by the loop.
214 3. (temporal locality) Inner loops should have smallest
215 array access strides.
217 if (dependence_steps_i
< dependence_steps_j
218 || nb_deps_not_carried_by_i
> nb_deps_not_carried_by_j
219 || access_strides_i
< access_strides_j
)
221 lambda_matrix_row_exchange (LTM_MATRIX (trans
),
222 loop_i
->depth
- first_loop
->depth
,
223 loop_j
->depth
- first_loop
->depth
);
224 /* Validate the resulting matrix. When the transformation
225 is not valid, reverse to the previous transformation. */
226 if (!lambda_transform_legal_p (trans
, depth
, dependence_relations
))
227 lambda_matrix_row_exchange (LTM_MATRIX (trans
),
228 loop_i
->depth
- first_loop
->depth
,
229 loop_j
->depth
- first_loop
->depth
);
236 /* Perform a set of linear transforms on LOOPS. */
239 linear_transform_loops (struct loops
*loops
)
242 VEC(tree
,heap
) *oldivs
= NULL
;
243 VEC(tree
,heap
) *invariants
= NULL
;
245 for (i
= 1; i
< loops
->num
; i
++)
247 unsigned int depth
= 0;
248 VEC (ddr_p
, heap
) *dependence_relations
;
249 VEC (data_reference_p
, heap
) *datarefs
;
250 struct loop
*loop_nest
= loops
->parray
[i
];
252 lambda_loopnest before
, after
;
253 lambda_trans_matrix trans
;
254 bool problem
= false;
255 bool need_perfect_nest
= false;
256 /* If it's not a loop nest, we don't want it.
257 We also don't handle sibling loops properly,
258 which are loops of the following form:
259 for (i = 0; i < 50; i++)
261 for (j = 0; j < 50; j++)
265 for (j = 0; j < 50; j++)
270 if (!loop_nest
|| !loop_nest
->inner
)
272 VEC_truncate (tree
, oldivs
, 0);
273 VEC_truncate (tree
, invariants
, 0);
275 for (temp
= loop_nest
->inner
; temp
; temp
= temp
->inner
)
277 /* If we have a sibling loop or multiple exit edges, jump ship. */
278 if (temp
->next
|| !temp
->single_exit
)
288 /* Analyze data references and dependence relations using scev. */
290 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
291 dependence_relations
= VEC_alloc (ddr_p
, heap
, 10 * 10);
292 compute_data_dependences_for_loop (loop_nest
, true, datarefs
,
293 dependence_relations
);
295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 dump_ddrs (dump_file
, dependence_relations
);
298 /* Build the transformation matrix. */
299 trans
= lambda_trans_matrix_new (depth
, depth
);
300 lambda_matrix_id (LTM_MATRIX (trans
), depth
);
301 trans
= try_interchange_loops (trans
, depth
, dependence_relations
,
302 datarefs
, loop_nest
);
304 if (lambda_trans_matrix_id_p (trans
))
307 fprintf (dump_file
, "Won't transform loop. Optimal transform is the identity transform\n");
311 /* Check whether the transformation is legal. */
312 if (!lambda_transform_legal_p (trans
, depth
, dependence_relations
))
315 fprintf (dump_file
, "Can't transform loop, transform is illegal:\n");
319 if (!perfect_nest_p (loop_nest
))
320 need_perfect_nest
= true;
322 before
= gcc_loopnest_to_lambda_loopnest (loops
,
331 fprintf (dump_file
, "Before:\n");
332 print_lambda_loopnest (dump_file
, before
, 'i');
335 after
= lambda_loopnest_transform (before
, trans
);
339 fprintf (dump_file
, "After:\n");
340 print_lambda_loopnest (dump_file
, after
, 'u');
343 lambda_loopnest_to_gcc_loopnest (loop_nest
, oldivs
, invariants
,
347 fprintf (dump_file
, "Successfully transformed loop.\n");
349 free_dependence_relations (dependence_relations
);
350 free_data_refs (datarefs
);
353 VEC_free (tree
, heap
, oldivs
);
354 VEC_free (tree
, heap
, invariants
);
356 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_full_phi
);