Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-loop-linear.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* Linear Loop transforms
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dberlin@dberlin.org>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "target.h"
30
31 #include "rtl.h"
32 #include "basic-block.h"
33 #include "diagnostic.h"
34 #include "obstack.h"
35 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "timevar.h"
38 #include "cfgloop.h"
39 #include "expr.h"
40 #include "optabs.h"
41 #include "tree-chrec.h"
42 #include "tree-data-ref.h"
43 #include "tree-scalar-evolution.h"
44 #include "tree-pass.h"
45 #include "lambda.h"
46
47 /* Linear loop transforms include any composition of interchange,
48 scaling, skewing, and reversal. They are used to change the
49 iteration order of loop nests in order to optimize data locality of
50 traversals, or remove dependences that prevent
51 parallelization/vectorization/etc.
52
53 TODO: Determine reuse vectors/matrix and use it to determine optimal
54 transform matrix for locality purposes.
55 TODO: Completion of partial transforms. */
56
57 /* Gather statistics for loop interchange. LOOP is the loop being
58 considered. The first loop in the considered loop nest is
59 FIRST_LOOP, and consequently, the index of the considered loop is
60 obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
61
62 Initializes:
63 - DEPENDENCE_STEPS the sum of all the data dependence distances
64 carried by loop LOOP,
65
66 - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
67 for which the loop LOOP is not carrying any dependence,
68
69 - ACCESS_STRIDES the sum of all the strides in LOOP.
70
71 Example: for the following loop,
72
73 | loop_1 runs 1335 times
74 | loop_2 runs 1335 times
75 | A[{{0, +, 1}_1, +, 1335}_2]
76 | B[{{0, +, 1}_1, +, 1335}_2]
77 | endloop_2
78 | A[{0, +, 1336}_1]
79 | endloop_1
80
81 gather_interchange_stats (in loop_1) will return
82 DEPENDENCE_STEPS = 3002
83 NB_DEPS_NOT_CARRIED_BY_LOOP = 5
84 ACCESS_STRIDES = 10694
85
86 gather_interchange_stats (in loop_2) will return
87 DEPENDENCE_STEPS = 3000
88 NB_DEPS_NOT_CARRIED_BY_LOOP = 7
89 ACCESS_STRIDES = 8010
90 */
91
92 static void
93 gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations ATTRIBUTE_UNUSED,
94 VEC (data_reference_p, heap) *datarefs ATTRIBUTE_UNUSED,
95 struct loop *loop ATTRIBUTE_UNUSED,
96 struct loop *first_loop ATTRIBUTE_UNUSED,
97 unsigned int *dependence_steps ATTRIBUTE_UNUSED,
98 unsigned int *nb_deps_not_carried_by_loop ATTRIBUTE_UNUSED,
99 double_int *access_strides ATTRIBUTE_UNUSED)
100 {
101 unsigned int i, j;
102 struct data_dependence_relation *ddr;
103 struct data_reference *dr;
104
105 *dependence_steps = 0;
106 *nb_deps_not_carried_by_loop = 0;
107 *access_strides = double_int_zero;
108
109 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
110 {
111 /* If we don't know anything about this dependence, or the distance
112 vector is NULL, or there is no dependence, then there is no reuse of
113 data. */
114 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
115 || DDR_ARE_DEPENDENT (ddr) == chrec_known
116 || DDR_NUM_DIST_VECTS (ddr) == 0)
117 continue;
118
119 for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
120 {
121 int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];
122
123 if (dist == 0)
124 (*nb_deps_not_carried_by_loop) += 1;
125
126 else if (dist < 0)
127 (*dependence_steps) += -dist;
128
129 else
130 (*dependence_steps) += dist;
131 }
132 }
133
134 /* Compute the access strides. */
135 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
136 {
137 unsigned int it;
138 tree ref = DR_REF (dr);
139 gimple stmt = DR_STMT (dr);
140 struct loop *stmt_loop = loop_containing_stmt (stmt);
141 struct loop *inner_loop = first_loop->inner;
142
143 if (inner_loop != stmt_loop
144 && !flow_loop_nested_p (inner_loop, stmt_loop))
145 continue;
146
147 for (it = 0; it < DR_NUM_DIMENSIONS (dr);
148 it++, ref = TREE_OPERAND (ref, 0))
149 {
150 int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num);
151 int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num);
152 tree array_size = TYPE_SIZE (TREE_TYPE (ref));
153 double_int dstride;
154
155 if (array_size == NULL_TREE
156 || TREE_CODE (array_size) != INTEGER_CST)
157 continue;
158
159 dstride = double_int_mul (tree_to_double_int (array_size),
160 shwi_to_double_int (istride));
161 (*access_strides) = double_int_add (*access_strides, dstride);
162 }
163 }
164 }
165
166 /* Attempt to apply interchange transformations to TRANS to maximize the
167 spatial and temporal locality of the loop.
168 Returns the new transform matrix. The smaller the reuse vector
169 distances in the inner loops, the fewer the cache misses.
170 FIRST_LOOP is the loop->num of the first loop in the analyzed loop
171 nest. */
172
173
174 static lambda_trans_matrix
175 try_interchange_loops (lambda_trans_matrix trans,
176 unsigned int depth,
177 VEC (ddr_p, heap) *dependence_relations,
178 VEC (data_reference_p, heap) *datarefs,
179 struct loop *first_loop)
180 {
181 bool res;
182 struct loop *loop_i;
183 struct loop *loop_j;
184 unsigned int dependence_steps_i, dependence_steps_j;
185 double_int access_strides_i, access_strides_j;
186 double_int small, large, nb_iter;
187 double_int l1_cache_size, l2_cache_size;
188 int cmp;
189 unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
190 struct data_dependence_relation *ddr;
191
192 if (VEC_length (ddr_p, dependence_relations) == 0)
193 return trans;
194
195 /* When there is an unknown relation in the dependence_relations, we
196 know that it is no worth looking at this loop nest: give up. */
197 ddr = VEC_index (ddr_p, dependence_relations, 0);
198 if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
199 return trans;
200
201 l1_cache_size = uhwi_to_double_int (L1_CACHE_SIZE * 1024);
202 l2_cache_size = uhwi_to_double_int (L2_CACHE_SIZE * 1024);
203
204 /* LOOP_I is always the outer loop. */
205 for (loop_j = first_loop->inner;
206 loop_j;
207 loop_j = loop_j->inner)
208 for (loop_i = first_loop;
209 loop_depth (loop_i) < loop_depth (loop_j);
210 loop_i = loop_i->inner)
211 {
212 gather_interchange_stats (dependence_relations, datarefs,
213 loop_i, first_loop,
214 &dependence_steps_i,
215 &nb_deps_not_carried_by_i,
216 &access_strides_i);
217 gather_interchange_stats (dependence_relations, datarefs,
218 loop_j, first_loop,
219 &dependence_steps_j,
220 &nb_deps_not_carried_by_j,
221 &access_strides_j);
222
223 /* Heuristics for loop interchange profitability:
224
225 0. Don't transform if the smallest stride is larger than
226 the L2 cache, or if the largest stride multiplied by the
227 number of iterations is smaller than the L1 cache.
228
229 1. (spatial locality) Inner loops should have smallest
230 dependence steps.
231
232 2. (spatial locality) Inner loops should contain more
233 dependence relations not carried by the loop.
234
235 3. (temporal locality) Inner loops should have smallest
236 array access strides.
237 */
238
239 cmp = double_int_ucmp (access_strides_i, access_strides_j);
240 small = cmp < 0 ? access_strides_i : access_strides_j;
241 large = cmp < 0 ? access_strides_j : access_strides_i;
242
243 if (double_int_ucmp (small, l2_cache_size) > 0)
244 continue;
245
246 res = cmp < 0 ?
247 estimated_loop_iterations (loop_j, false, &nb_iter):
248 estimated_loop_iterations (loop_i, false, &nb_iter);
249 large = double_int_mul (large, nb_iter);
250
251 if (res && double_int_ucmp (large, l1_cache_size) < 0)
252 continue;
253
254 if (dependence_steps_i < dependence_steps_j
255 || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
256 || cmp < 0)
257 {
258 lambda_matrix_row_exchange (LTM_MATRIX (trans),
259 loop_depth (loop_i) - loop_depth (first_loop),
260 loop_depth (loop_j) - loop_depth (first_loop));
261 /* Validate the resulting matrix. When the transformation
262 is not valid, reverse to the previous transformation. */
263 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
264 lambda_matrix_row_exchange (LTM_MATRIX (trans),
265 loop_depth (loop_i) - loop_depth (first_loop),
266 loop_depth (loop_j) - loop_depth (first_loop));
267 }
268 }
269
270 return trans;
271 }
272
273 /* Return the number of nested loops in LOOP_NEST, or 0 if the loops
274 are not perfectly nested. */
275
276 unsigned int
277 perfect_loop_nest_depth (struct loop *loop_nest)
278 {
279 struct loop *temp;
280 unsigned int depth = 1;
281
282 /* If it's not a loop nest, we don't want it. We also don't handle
283 sibling loops properly, which are loops of the following form:
284
285 | for (i = 0; i < 50; i++)
286 | {
287 | for (j = 0; j < 50; j++)
288 | {
289 | ...
290 | }
291 | for (j = 0; j < 50; j++)
292 | {
293 | ...
294 | }
295 | }
296 */
297
298 if (!loop_nest->inner || !single_exit (loop_nest))
299 return 0;
300
301 for (temp = loop_nest->inner; temp; temp = temp->inner)
302 {
303 /* If we have a sibling loop or multiple exit edges, jump ship. */
304 if (temp->next || !single_exit (temp))
305 return 0;
306
307 depth++;
308 }
309
310 return depth;
311 }
312
313 /* Perform a set of linear transforms on loops. */
314
315 void
316 linear_transform_loops (void)
317 {
318 bool modified = false;
319 loop_iterator li;
320 VEC(tree,heap) *oldivs = NULL;
321 VEC(tree,heap) *invariants = NULL;
322 VEC(tree,heap) *lambda_parameters = NULL;
323 VEC(gimple,heap) *remove_ivs = VEC_alloc (gimple, heap, 3);
324 struct loop *loop_nest;
325 gimple oldiv_stmt;
326 unsigned i;
327
328 FOR_EACH_LOOP (li, loop_nest, 0)
329 {
330 unsigned int depth = 0;
331 VEC (ddr_p, heap) *dependence_relations;
332 VEC (data_reference_p, heap) *datarefs;
333
334 lambda_loopnest before, after;
335 lambda_trans_matrix trans;
336 struct obstack lambda_obstack;
337 struct loop *loop;
338 VEC(loop_p,heap) *nest;
339
340 depth = perfect_loop_nest_depth (loop_nest);
341 if (depth == 0)
342 continue;
343
344 nest = VEC_alloc (loop_p, heap, 3);
345 for (loop = loop_nest; loop; loop = loop->inner)
346 VEC_safe_push (loop_p, heap, nest, loop);
347
348 gcc_obstack_init (&lambda_obstack);
349 VEC_truncate (tree, oldivs, 0);
350 VEC_truncate (tree, invariants, 0);
351 VEC_truncate (tree, lambda_parameters, 0);
352
353 datarefs = VEC_alloc (data_reference_p, heap, 10);
354 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
355 if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs,
356 &dependence_relations))
357 goto free_and_continue;
358
359 lambda_collect_parameters (datarefs, &lambda_parameters);
360 if (!lambda_compute_access_matrices (datarefs, lambda_parameters, nest))
361 goto free_and_continue;
362
363 if (dump_file && (dump_flags & TDF_DETAILS))
364 dump_ddrs (dump_file, dependence_relations);
365
366 /* Build the transformation matrix. */
367 trans = lambda_trans_matrix_new (depth, depth);
368 lambda_matrix_id (LTM_MATRIX (trans), depth);
369 trans = try_interchange_loops (trans, depth, dependence_relations,
370 datarefs, loop_nest);
371
372 if (lambda_trans_matrix_id_p (trans))
373 {
374 if (dump_file)
375 fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
376 goto free_and_continue;
377 }
378
379 /* Check whether the transformation is legal. */
380 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
381 {
382 if (dump_file)
383 fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
384 goto free_and_continue;
385 }
386
387 before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs,
388 &invariants, &lambda_obstack);
389
390 if (!before)
391 goto free_and_continue;
392
393 if (dump_file)
394 {
395 fprintf (dump_file, "Before:\n");
396 print_lambda_loopnest (dump_file, before, 'i');
397 }
398
399 after = lambda_loopnest_transform (before, trans, &lambda_obstack);
400
401 if (dump_file)
402 {
403 fprintf (dump_file, "After:\n");
404 print_lambda_loopnest (dump_file, after, 'u');
405 }
406
407 lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
408 &remove_ivs,
409 after, trans, &lambda_obstack);
410 modified = true;
411
412 if (dump_file)
413 fprintf (dump_file, "Successfully transformed loop.\n");
414
415 free_and_continue:
416 obstack_free (&lambda_obstack, NULL);
417 free_dependence_relations (dependence_relations);
418 free_data_refs (datarefs);
419 VEC_free (loop_p, heap, nest);
420 }
421
422 for (i = 0; VEC_iterate (gimple, remove_ivs, i, oldiv_stmt); i++)
423 remove_iv (oldiv_stmt);
424
425 VEC_free (tree, heap, oldivs);
426 VEC_free (tree, heap, invariants);
427 VEC_free (gimple, heap, remove_ivs);
428 scev_reset ();
429
430 if (modified)
431 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
432 }