1 /* Linear Loop transforms
2 Copyright (C) 2003, 2004 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_NUMBER is a relative
59 index in the considered loop nest. The first loop in the
60 considered loop nest is FIRST_LOOP, and consequently the index of
61 the considered loop is obtained by FIRST_LOOP + LOOP_NUMBER.
64 - DEPENDENCE_STEPS the sum of all the data dependence distances
65 carried by loop LOOP_NUMBER,
67 - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
68 for which the loop LOOP_NUMBER is not carrying any dependence,
70 - ACCESS_STRIDES the sum of all the strides in LOOP_NUMBER.
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,
96 unsigned int loop_number,
97 unsigned int 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 /* Compute the dependence strides. */
117 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
119 (*dependence_steps) += 0;
123 /* When we know that there is no dependence, we know that there
124 is no reuse of the data. */
125 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
127 (*dependence_steps) += 0;
130 dist = DDR_DIST_VECT (ddr)[loop_number];
132 (*nb_deps_not_carried_by_loop) += 1;
134 (*dependence_steps) += -dist;
136 (*dependence_steps) += dist;
139 /* Compute the access strides. */
140 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
143 struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
144 tree stmt = DR_STMT (dr);
145 struct loop *stmt_loop = loop_containing_stmt (stmt);
146 struct loop *inner_loop = current_loops->parray[first_loop + 1];
148 if (!flow_loop_nested_p (inner_loop, stmt_loop)
149 && inner_loop->num != stmt_loop->num)
152 for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
154 tree chrec = DR_ACCESS_FN (dr, it);
155 tree tstride = evolution_part_in_loop_num
156 (chrec, first_loop + loop_number);
158 if (tstride == NULL_TREE
159 || TREE_CODE (tstride) != INTEGER_CST)
162 (*access_strides) += int_cst_value (tstride);
167 /* Apply to TRANS any loop interchange that minimize inner loop steps.
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
174 static lambda_trans_matrix
175 try_interchange_loops (lambda_trans_matrix trans,
177 varray_type dependence_relations,
178 varray_type datarefs,
179 unsigned int first_loop)
181 unsigned int loop_i, loop_j;
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 /* When there is an unknown relation in the dependence_relations, we
188 know that it is no worth looking at this loop nest: give up. */
189 ddr = (struct data_dependence_relation *)
190 VARRAY_GENERIC_PTR (dependence_relations, 0);
191 if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
194 /* LOOP_I is always the outer loop. */
195 for (loop_j = 1; loop_j < depth; loop_j++)
196 for (loop_i = 0; loop_i < loop_j; loop_i++)
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), loop_i, loop_j);
225 /* Validate the resulting matrix. When the transformation
226 is not valid, reverse to the previous transformation. */
227 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
228 lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
235 /* Perform a set of linear transforms on LOOPS. */
238 linear_transform_loops (struct loops *loops)
242 compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
243 for (i = 1; i < loops->num; i++)
245 unsigned int depth = 0;
246 varray_type datarefs;
247 varray_type dependence_relations;
248 struct loop *loop_nest = loops->parray[i];
250 VEC (tree) *oldivs = NULL;
251 VEC (tree) *invariants = NULL;
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->inner)
273 for (temp = loop_nest->inner; temp; temp = temp->inner)
275 flow_loop_scan (temp, LOOP_ALL);
276 /* If we have a sibling loop or multiple exit edges, jump ship. */
277 if (temp->next || temp->num_exits != 1)
287 /* Analyze data references and dependence relations using scev. */
289 VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
290 VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
291 "dependence_relations");
294 compute_data_dependences_for_loop (depth, loop_nest,
295 &datarefs, &dependence_relations);
296 if (dump_file && (dump_flags & TDF_DETAILS))
299 for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
301 struct data_dependence_relation *ddr =
302 (struct data_dependence_relation *)
303 VARRAY_GENERIC_PTR (dependence_relations, j);
305 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
307 fprintf (dump_file, "DISTANCE_V (");
308 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr),
309 DDR_SIZE_VECT (ddr));
310 fprintf (dump_file, ")\n");
311 fprintf (dump_file, "DIRECTION_V (");
312 print_lambda_vector (dump_file, DDR_DIR_VECT (ddr),
313 DDR_SIZE_VECT (ddr));
314 fprintf (dump_file, ")\n");
317 fprintf (dump_file, "\n\n");
319 /* Build the transformation matrix. */
320 trans = lambda_trans_matrix_new (depth, depth);
321 lambda_matrix_id (LTM_MATRIX (trans), depth);
323 trans = try_interchange_loops (trans, depth, dependence_relations,
324 datarefs, loop_nest->num);
326 if (lambda_trans_matrix_id_p (trans))
329 fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
333 /* Check whether the transformation is legal. */
334 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
337 fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
340 if (!perfect_nest_p (loop_nest))
341 need_perfect_nest = true;
342 before = gcc_loopnest_to_lambda_loopnest (loops,
351 fprintf (dump_file, "Before:\n");
352 print_lambda_loopnest (dump_file, before, 'i');
355 after = lambda_loopnest_transform (before, trans);
358 fprintf (dump_file, "After:\n");
359 print_lambda_loopnest (dump_file, after, 'u');
361 lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
364 fprintf (dump_file, "Successfully transformed loop.\n");
367 free_dependence_relations (dependence_relations);
368 free_data_refs (datarefs);
372 rewrite_into_loop_closed_ssa ();
373 #ifdef ENABLE_CHECKING
374 verify_loop_closed_ssa ();