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 ref = DR_REF (dr);
138 tree stmt = DR_STMT (dr);
139 struct loop *stmt_loop = loop_containing_stmt (stmt);
140 struct loop *inner_loop = first_loop->inner;
142 if (inner_loop != stmt_loop
143 && !flow_loop_nested_p (inner_loop, stmt_loop))
146 for (it = 0; it < DR_NUM_DIMENSIONS (dr);
147 it++, ref = TREE_OPERAND (ref, 0))
149 tree chrec = DR_ACCESS_FN (dr, it);
150 tree tstride = evolution_part_in_loop_num (chrec, loop->num);
151 tree array_size = TYPE_SIZE (TREE_TYPE (ref));
153 if (tstride == NULL_TREE
154 || array_size == NULL_TREE
155 || TREE_CODE (tstride) != INTEGER_CST
156 || TREE_CODE (array_size) != INTEGER_CST)
160 int_cst_value (array_size) * int_cst_value (tstride);
165 /* Attempt to apply interchange transformations to TRANS to maximize the
166 spatial and temporal locality of the loop.
167 Returns the new transform matrix. The smaller the reuse vector
168 distances in the inner loops, the fewer the cache misses.
169 FIRST_LOOP is the loop->num of the first loop in the analyzed loop
173 static lambda_trans_matrix
174 try_interchange_loops (lambda_trans_matrix trans,
176 VEC (ddr_p, heap) *dependence_relations,
177 VEC (data_reference_p, heap) *datarefs,
178 struct loop *first_loop)
182 unsigned int dependence_steps_i, dependence_steps_j;
183 unsigned int access_strides_i, access_strides_j;
184 unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
185 struct data_dependence_relation *ddr;
187 if (VEC_length (ddr_p, dependence_relations) == 0)
190 /* When there is an unknown relation in the dependence_relations, we
191 know that it is no worth looking at this loop nest: give up. */
192 ddr = VEC_index (ddr_p, dependence_relations, 0);
193 if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
196 /* LOOP_I is always the outer loop. */
197 for (loop_j = first_loop->inner;
199 loop_j = loop_j->inner)
200 for (loop_i = first_loop;
201 loop_i->depth < loop_j->depth;
202 loop_i = loop_i->inner)
204 gather_interchange_stats (dependence_relations, datarefs,
207 &nb_deps_not_carried_by_i,
209 gather_interchange_stats (dependence_relations, datarefs,
212 &nb_deps_not_carried_by_j,
215 /* Heuristics for loop interchange profitability:
217 1. (spatial locality) Inner loops should have smallest
220 2. (spatial locality) Inner loops should contain more
221 dependence relations not carried by the loop.
223 3. (temporal locality) Inner loops should have smallest
224 array access strides.
226 if (dependence_steps_i < dependence_steps_j
227 || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
228 || access_strides_i < access_strides_j)
230 lambda_matrix_row_exchange (LTM_MATRIX (trans),
231 loop_i->depth - first_loop->depth,
232 loop_j->depth - first_loop->depth);
233 /* Validate the resulting matrix. When the transformation
234 is not valid, reverse to the previous transformation. */
235 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
236 lambda_matrix_row_exchange (LTM_MATRIX (trans),
237 loop_i->depth - first_loop->depth,
238 loop_j->depth - first_loop->depth);
245 /* Perform a set of linear transforms on loops. */
248 linear_transform_loops (void)
250 bool modified = false;
252 VEC(tree,heap) *oldivs = NULL;
253 VEC(tree,heap) *invariants = NULL;
254 struct loop *loop_nest;
256 FOR_EACH_LOOP (li, loop_nest, 0)
258 unsigned int depth = 0;
259 VEC (ddr_p, heap) *dependence_relations;
260 VEC (data_reference_p, heap) *datarefs;
262 lambda_loopnest before, after;
263 lambda_trans_matrix trans;
264 bool problem = false;
265 /* If it's not a loop nest, we don't want it.
266 We also don't handle sibling loops properly,
267 which are loops of the following form:
268 for (i = 0; i < 50; i++)
270 for (j = 0; j < 50; j++)
274 for (j = 0; j < 50; j++)
279 if (!loop_nest->inner || !single_exit (loop_nest))
281 VEC_truncate (tree, oldivs, 0);
282 VEC_truncate (tree, invariants, 0);
284 for (temp = loop_nest->inner; temp; temp = temp->inner)
286 /* If we have a sibling loop or multiple exit edges, jump ship. */
287 if (temp->next || !single_exit (temp))
297 /* Analyze data references and dependence relations using scev. */
299 datarefs = VEC_alloc (data_reference_p, heap, 10);
300 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
301 compute_data_dependences_for_loop (loop_nest, true, &datarefs,
302 &dependence_relations);
304 if (dump_file && (dump_flags & TDF_DETAILS))
305 dump_ddrs (dump_file, dependence_relations);
307 /* Build the transformation matrix. */
308 trans = lambda_trans_matrix_new (depth, depth);
309 lambda_matrix_id (LTM_MATRIX (trans), depth);
310 trans = try_interchange_loops (trans, depth, dependence_relations,
311 datarefs, loop_nest);
313 if (lambda_trans_matrix_id_p (trans))
316 fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
317 goto free_and_continue;
320 /* Check whether the transformation is legal. */
321 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
324 fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
325 goto free_and_continue;
328 before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
332 goto free_and_continue;
336 fprintf (dump_file, "Before:\n");
337 print_lambda_loopnest (dump_file, before, 'i');
340 after = lambda_loopnest_transform (before, trans);
344 fprintf (dump_file, "After:\n");
345 print_lambda_loopnest (dump_file, after, 'u');
348 lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
353 fprintf (dump_file, "Successfully transformed loop.\n");
356 free_dependence_relations (dependence_relations);
357 free_data_refs (datarefs);
360 VEC_free (tree, heap, oldivs);
361 VEC_free (tree, heap, invariants);
365 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);