]>
Commit | Line | Data |
---|---|---|
c19ca6f9 PS |
1 | Index: tree-loop-linear.c |
2 | =================================================================== | |
3 | *** tree-loop-linear.c (revision 113884) | |
4 | --- tree-loop-linear.c (working copy) | |
5 | *************** | |
6 | *** 1,5 **** | |
7 | /* Linear Loop transforms | |
8 | ! Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. | |
9 | Contributed by Daniel Berlin <dberlin@dberlin.org>. | |
10 | ||
11 | This file is part of GCC. | |
12 | --- 1,5 ---- | |
13 | /* Linear Loop transforms | |
14 | ! Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. | |
15 | Contributed by Daniel Berlin <dberlin@dberlin.org>. | |
16 | ||
17 | This file is part of GCC. | |
18 | *************** try_interchange_loops (lambda_trans_matr | |
19 | *** 243,248 **** | |
20 | --- 243,249 ---- | |
21 | void | |
22 | linear_transform_loops (struct loops *loops) | |
23 | { | |
24 | + bool modified = false; | |
25 | unsigned int i; | |
26 | VEC(tree,heap) *oldivs = NULL; | |
27 | VEC(tree,heap) *invariants = NULL; | |
28 | *************** linear_transform_loops (struct loops *lo | |
29 | *** 257,263 **** | |
30 | lambda_loopnest before, after; | |
31 | lambda_trans_matrix trans; | |
32 | bool problem = false; | |
33 | - bool need_perfect_nest = false; | |
34 | /* If it's not a loop nest, we don't want it. | |
35 | We also don't handle sibling loops properly, | |
36 | which are loops of the following form: | |
37 | --- 258,263 ---- | |
38 | *************** linear_transform_loops (struct loops *lo | |
39 | *** 334,345 **** | |
40 | fprintf (dump_file, "Can't transform loop, transform is illegal:\n"); | |
41 | continue; | |
42 | } | |
43 | ! if (!perfect_nest_p (loop_nest)) | |
44 | ! need_perfect_nest = true; | |
45 | ! before = gcc_loopnest_to_lambda_loopnest (loops, | |
46 | ! loop_nest, &oldivs, | |
47 | ! &invariants, | |
48 | ! need_perfect_nest); | |
49 | if (!before) | |
50 | continue; | |
51 | ||
52 | --- 334,342 ---- | |
53 | fprintf (dump_file, "Can't transform loop, transform is illegal:\n"); | |
54 | continue; | |
55 | } | |
56 | ! | |
57 | ! before = gcc_loopnest_to_lambda_loopnest (loops, loop_nest, &oldivs, | |
58 | ! &invariants); | |
59 | if (!before) | |
60 | continue; | |
61 | ||
62 | *************** linear_transform_loops (struct loops *lo | |
63 | *** 357,362 **** | |
64 | --- 354,361 ---- | |
65 | } | |
66 | lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants, | |
67 | after, trans); | |
68 | + modified = true; | |
69 | + | |
70 | if (dump_file) | |
71 | fprintf (dump_file, "Successfully transformed loop.\n"); | |
72 | free_dependence_relations (dependence_relations); | |
73 | *************** linear_transform_loops (struct loops *lo | |
74 | *** 365,369 **** | |
75 | VEC_free (tree, heap, oldivs); | |
76 | VEC_free (tree, heap, invariants); | |
77 | scev_reset (); | |
78 | ! rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi); | |
79 | } | |
80 | --- 364,370 ---- | |
81 | VEC_free (tree, heap, oldivs); | |
82 | VEC_free (tree, heap, invariants); | |
83 | scev_reset (); | |
84 | ! | |
85 | ! if (modified) | |
86 | ! rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi); | |
87 | } | |
88 | Index: lambda.h | |
89 | =================================================================== | |
90 | *** lambda.h (revision 113884) | |
91 | --- lambda.h (working copy) | |
92 | *************** | |
93 | *** 1,5 **** | |
94 | /* Lambda matrix and vector interface. | |
95 | ! Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. | |
96 | Contributed by Daniel Berlin <dberlin@dberlin.org> | |
97 | ||
98 | This file is part of GCC. | |
99 | --- 1,5 ---- | |
100 | /* Lambda matrix and vector interface. | |
101 | ! Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. | |
102 | Contributed by Daniel Berlin <dberlin@dberlin.org> | |
103 | ||
104 | This file is part of GCC. | |
105 | *************** void print_lambda_body_vector (FILE *, l | |
106 | *** 200,207 **** | |
107 | lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *, | |
108 | struct loop *, | |
109 | VEC(tree,heap) **, | |
110 | ! VEC(tree,heap) **, | |
111 | ! bool); | |
112 | void lambda_loopnest_to_gcc_loopnest (struct loop *, | |
113 | VEC(tree,heap) *, VEC(tree,heap) *, | |
114 | lambda_loopnest, lambda_trans_matrix); | |
115 | --- 200,206 ---- | |
116 | lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *, | |
117 | struct loop *, | |
118 | VEC(tree,heap) **, | |
119 | ! VEC(tree,heap) **); | |
120 | void lambda_loopnest_to_gcc_loopnest (struct loop *, | |
121 | VEC(tree,heap) *, VEC(tree,heap) *, | |
122 | lambda_loopnest, lambda_trans_matrix); | |
123 | Index: lambda-code.c | |
124 | =================================================================== | |
125 | *** lambda-code.c (revision 113884) | |
126 | --- lambda-code.c (working copy) | |
127 | *************** | |
128 | *** 1,5 **** | |
129 | /* Loop transformation code generation | |
130 | ! Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. | |
131 | Contributed by Daniel Berlin <dberlin@dberlin.org> | |
132 | ||
133 | This file is part of GCC. | |
134 | --- 1,5 ---- | |
135 | /* Loop transformation code generation | |
136 | ! Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. | |
137 | Contributed by Daniel Berlin <dberlin@dberlin.org> | |
138 | ||
139 | This file is part of GCC. | |
140 | *************** static lambda_lattice lambda_lattice_new | |
141 | *** 149,154 **** | |
142 | --- 149,155 ---- | |
143 | static lambda_lattice lambda_lattice_compute_base (lambda_loopnest); | |
144 | ||
145 | static tree find_induction_var_from_exit_cond (struct loop *); | |
146 | + static bool can_convert_to_perfect_nest (struct loop *); | |
147 | ||
148 | /* Create a new lambda body vector. */ | |
149 | ||
150 | *************** DEF_VEC_ALLOC_P(lambda_loop,heap); | |
151 | *** 1498,1511 **** | |
152 | ||
153 | lambda_loopnest | |
154 | gcc_loopnest_to_lambda_loopnest (struct loops *currloops, | |
155 | ! struct loop * loop_nest, | |
156 | VEC(tree,heap) **inductionvars, | |
157 | ! VEC(tree,heap) **invariants, | |
158 | ! bool need_perfect_nest) | |
159 | { | |
160 | lambda_loopnest ret = NULL; | |
161 | ! struct loop *temp; | |
162 | ! int depth = 0; | |
163 | size_t i; | |
164 | VEC(lambda_loop,heap) *loops = NULL; | |
165 | VEC(tree,heap) *uboundvars = NULL; | |
166 | --- 1499,1511 ---- | |
167 | ||
168 | lambda_loopnest | |
169 | gcc_loopnest_to_lambda_loopnest (struct loops *currloops, | |
170 | ! struct loop *loop_nest, | |
171 | VEC(tree,heap) **inductionvars, | |
172 | ! VEC(tree,heap) **invariants) | |
173 | { | |
174 | lambda_loopnest ret = NULL; | |
175 | ! struct loop *temp = loop_nest; | |
176 | ! int depth = depth_of_nest (loop_nest); | |
177 | size_t i; | |
178 | VEC(lambda_loop,heap) *loops = NULL; | |
179 | VEC(tree,heap) *uboundvars = NULL; | |
180 | *************** gcc_loopnest_to_lambda_loopnest (struct | |
181 | *** 1513,1521 **** | |
182 | VEC(int,heap) *steps = NULL; | |
183 | lambda_loop newloop; | |
184 | tree inductionvar = NULL; | |
185 | ! | |
186 | ! depth = depth_of_nest (loop_nest); | |
187 | ! temp = loop_nest; | |
188 | while (temp) | |
189 | { | |
190 | newloop = gcc_loop_to_lambda_loop (temp, depth, invariants, | |
191 | --- 1513,1523 ---- | |
192 | VEC(int,heap) *steps = NULL; | |
193 | lambda_loop newloop; | |
194 | tree inductionvar = NULL; | |
195 | ! bool perfect_nest = perfect_nest_p (loop_nest); | |
196 | ! | |
197 | ! if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest)) | |
198 | ! goto fail; | |
199 | ! | |
200 | while (temp) | |
201 | { | |
202 | newloop = gcc_loop_to_lambda_loop (temp, depth, invariants, | |
203 | *************** gcc_loopnest_to_lambda_loopnest (struct | |
204 | *** 1523,1534 **** | |
205 | &lboundvars, &uboundvars, | |
206 | &steps); | |
207 | if (!newloop) | |
208 | ! return NULL; | |
209 | VEC_safe_push (tree, heap, *inductionvars, inductionvar); | |
210 | VEC_safe_push (lambda_loop, heap, loops, newloop); | |
211 | temp = temp->inner; | |
212 | } | |
213 | ! if (need_perfect_nest) | |
214 | { | |
215 | if (!perfect_nestify (currloops, loop_nest, | |
216 | lboundvars, uboundvars, steps, *inductionvars)) | |
217 | --- 1525,1538 ---- | |
218 | &lboundvars, &uboundvars, | |
219 | &steps); | |
220 | if (!newloop) | |
221 | ! goto fail; | |
222 | ! | |
223 | VEC_safe_push (tree, heap, *inductionvars, inductionvar); | |
224 | VEC_safe_push (lambda_loop, heap, loops, newloop); | |
225 | temp = temp->inner; | |
226 | } | |
227 | ! | |
228 | ! if (!perfect_nest) | |
229 | { | |
230 | if (!perfect_nestify (currloops, loop_nest, | |
231 | lboundvars, uboundvars, steps, *inductionvars)) | |
232 | *************** gcc_loopnest_to_lambda_loopnest (struct | |
233 | *** 1542,1550 **** | |
234 | --- 1546,1557 ---- | |
235 | fprintf (dump_file, | |
236 | "Successfully converted loop nest to perfect loop nest.\n"); | |
237 | } | |
238 | + | |
239 | ret = lambda_loopnest_new (depth, 2 * depth); | |
240 | + | |
241 | for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++) | |
242 | LN_LOOPS (ret)[i] = newloop; | |
243 | + | |
244 | fail: | |
245 | VEC_free (lambda_loop, heap, loops); | |
246 | VEC_free (tree, heap, uboundvars); | |
247 | *************** replace_uses_equiv_to_x_with_y (struct l | |
248 | *** 2156,2168 **** | |
249 | { | |
250 | tree use = USE_FROM_PTR (use_p); | |
251 | tree step = NULL_TREE; | |
252 | ! tree access_fn = NULL_TREE; | |
253 | ! | |
254 | ! | |
255 | ! access_fn = instantiate_parameters | |
256 | ! (loop, analyze_scalar_evolution (loop, use)); | |
257 | ! if (access_fn != NULL_TREE && access_fn != chrec_dont_know) | |
258 | ! step = evolution_part_in_loop_num (access_fn, loop->num); | |
259 | if ((step && step != chrec_dont_know | |
260 | && TREE_CODE (step) == INTEGER_CST | |
261 | && int_cst_value (step) == xstep) | |
262 | --- 2163,2174 ---- | |
263 | { | |
264 | tree use = USE_FROM_PTR (use_p); | |
265 | tree step = NULL_TREE; | |
266 | ! tree scev = instantiate_parameters (loop, | |
267 | ! analyze_scalar_evolution (loop, use)); | |
268 | ! | |
269 | ! if (scev != NULL_TREE && scev != chrec_dont_know) | |
270 | ! step = evolution_part_in_loop_num (scev, loop->num); | |
271 | ! | |
272 | if ((step && step != chrec_dont_know | |
273 | && TREE_CODE (step) == INTEGER_CST | |
274 | && int_cst_value (step) == xstep) | |
275 | *************** replace_uses_equiv_to_x_with_y (struct l | |
276 | *** 2171,2192 **** | |
277 | } | |
278 | } | |
279 | ||
280 | - /* Return TRUE if STMT uses tree OP in it's uses. */ | |
281 | - | |
282 | - static bool | |
283 | - stmt_uses_op (tree stmt, tree op) | |
284 | - { | |
285 | - ssa_op_iter iter; | |
286 | - tree use; | |
287 | - | |
288 | - FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
289 | - { | |
290 | - if (use == op) | |
291 | - return true; | |
292 | - } | |
293 | - return false; | |
294 | - } | |
295 | - | |
296 | /* Return true if STMT is an exit PHI for LOOP */ | |
297 | ||
298 | static bool | |
299 | --- 2177,2182 ---- | |
300 | *************** can_put_in_inner_loop (struct loop *inne | |
301 | *** 2236,2250 **** | |
302 | ||
303 | } | |
304 | ||
305 | ||
306 | ! /* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect | |
307 | ! one. LOOPIVS is a vector of induction variables, one per loop. | |
308 | ! ATM, we only handle imperfect nests of depth 2, where all of the statements | |
309 | ! occur after the inner loop. */ | |
310 | ||
311 | static bool | |
312 | ! can_convert_to_perfect_nest (struct loop *loop, | |
313 | ! VEC(tree,heap) *loopivs) | |
314 | { | |
315 | basic_block *bbs; | |
316 | tree exit_condition, phi; | |
317 | --- 2226,2264 ---- | |
318 | ||
319 | } | |
320 | ||
321 | + /* Return true if STMT can be put *after* the inner loop of LOOP. */ | |
322 | + | |
323 | + static bool | |
324 | + can_put_after_inner_loop (struct loop *loop, tree stmt) | |
325 | + { | |
326 | + imm_use_iterator imm_iter; | |
327 | + use_operand_p use_p; | |
328 | + | |
329 | + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) | |
330 | + return false; | |
331 | + | |
332 | + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0)) | |
333 | + { | |
334 | + if (!exit_phi_for_loop_p (loop, USE_STMT (use_p))) | |
335 | + { | |
336 | + basic_block immbb = bb_for_stmt (USE_STMT (use_p)); | |
337 | + | |
338 | + if (!dominated_by_p (CDI_DOMINATORS, | |
339 | + immbb, | |
340 | + loop->inner->header) | |
341 | + && !can_put_in_inner_loop (loop->inner, stmt)) | |
342 | + return false; | |
343 | + } | |
344 | + } | |
345 | + return true; | |
346 | + } | |
347 | ||
348 | ! /* Return TRUE if LOOP is an imperfect nest that we can convert to a | |
349 | ! perfect one. At the moment, we only handle imperfect nests of | |
350 | ! depth 2, where all of the statements occur after the inner loop. */ | |
351 | ||
352 | static bool | |
353 | ! can_convert_to_perfect_nest (struct loop *loop) | |
354 | { | |
355 | basic_block *bbs; | |
356 | tree exit_condition, phi; | |
357 | *************** can_convert_to_perfect_nest (struct loop | |
358 | *** 2264,2282 **** | |
359 | { | |
360 | for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi)) | |
361 | { | |
362 | - size_t j; | |
363 | tree stmt = bsi_stmt (bsi); | |
364 | ! tree iv; | |
365 | ! | |
366 | if (stmt == exit_condition | |
367 | || not_interesting_stmt (stmt) | |
368 | || stmt_is_bumper_for_loop (loop, stmt)) | |
369 | continue; | |
370 | ! /* If the statement uses inner loop ivs, we == screwed. */ | |
371 | ! for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++) | |
372 | ! if (stmt_uses_op (stmt, iv)) | |
373 | ! goto fail; | |
374 | ! | |
375 | /* If this is a simple operation like a cast that is invariant | |
376 | in the inner loop, only used there, and we can place it | |
377 | there, then it's not going to hurt us. | |
378 | --- 2278,2290 ---- | |
379 | { | |
380 | for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi)) | |
381 | { | |
382 | tree stmt = bsi_stmt (bsi); | |
383 | ! | |
384 | if (stmt == exit_condition | |
385 | || not_interesting_stmt (stmt) | |
386 | || stmt_is_bumper_for_loop (loop, stmt)) | |
387 | continue; | |
388 | ! | |
389 | /* If this is a simple operation like a cast that is invariant | |
390 | in the inner loop, only used there, and we can place it | |
391 | there, then it's not going to hurt us. | |
392 | *************** can_convert_to_perfect_nest (struct loop | |
393 | *** 2286,2295 **** | |
394 | theory that we are going to gain a lot more by interchanging | |
395 | the loop than we are by leaving some invariant code there for | |
396 | some other pass to clean up. */ | |
397 | ! if (TREE_CODE (stmt) == MODIFY_EXPR | |
398 | ! && is_gimple_cast (TREE_OPERAND (stmt, 1)) | |
399 | ! && can_put_in_inner_loop (loop->inner, stmt)) | |
400 | ! continue; | |
401 | ||
402 | /* Otherwise, if the bb of a statement we care about isn't | |
403 | dominated by the header of the inner loop, then we can't | |
404 | --- 2294,2358 ---- | |
405 | theory that we are going to gain a lot more by interchanging | |
406 | the loop than we are by leaving some invariant code there for | |
407 | some other pass to clean up. */ | |
408 | ! if (TREE_CODE (stmt) == MODIFY_EXPR) | |
409 | ! { | |
410 | ! use_operand_p use_a, use_b; | |
411 | ! imm_use_iterator imm_iter; | |
412 | ! ssa_op_iter op_iter, op_iter1; | |
413 | ! tree op0 = TREE_OPERAND (stmt, 0); | |
414 | ! tree scev = instantiate_parameters | |
415 | ! (loop, analyze_scalar_evolution (loop, op0)); | |
416 | ! | |
417 | ! /* If the IV is simple, it can be duplicated. */ | |
418 | ! if (!automatically_generated_chrec_p (scev)) | |
419 | ! { | |
420 | ! tree step = evolution_part_in_loop_num (scev, loop->num); | |
421 | ! if (step && step != chrec_dont_know | |
422 | ! && TREE_CODE (step) == INTEGER_CST) | |
423 | ! continue; | |
424 | ! } | |
425 | ! | |
426 | ! /* The statement should not define a variable used | |
427 | ! in the inner loop. */ | |
428 | ! if (TREE_CODE (op0) == SSA_NAME) | |
429 | ! FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0) | |
430 | ! if (bb_for_stmt (USE_STMT (use_a))->loop_father | |
431 | ! == loop->inner) | |
432 | ! goto fail; | |
433 | ! | |
434 | ! FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE) | |
435 | ! { | |
436 | ! tree node, op = USE_FROM_PTR (use_a); | |
437 | ! | |
438 | ! /* The variables should not be used in both loops. */ | |
439 | ! FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op) | |
440 | ! if (bb_for_stmt (USE_STMT (use_b))->loop_father | |
441 | ! == loop->inner) | |
442 | ! goto fail; | |
443 | ! | |
444 | ! /* The statement should not use the value of a | |
445 | ! scalar that was modified in the loop. */ | |
446 | ! node = SSA_NAME_DEF_STMT (op); | |
447 | ! if (TREE_CODE (node) == PHI_NODE) | |
448 | ! FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE) | |
449 | ! { | |
450 | ! tree arg = USE_FROM_PTR (use_b); | |
451 | ! | |
452 | ! if (TREE_CODE (arg) == SSA_NAME) | |
453 | ! { | |
454 | ! tree arg_stmt = SSA_NAME_DEF_STMT (arg); | |
455 | ! | |
456 | ! if (bb_for_stmt (arg_stmt)->loop_father | |
457 | ! == loop->inner) | |
458 | ! goto fail; | |
459 | ! } | |
460 | ! } | |
461 | ! } | |
462 | ! | |
463 | ! if (can_put_in_inner_loop (loop->inner, stmt) | |
464 | ! || can_put_after_inner_loop (loop, stmt)) | |
465 | ! continue; | |
466 | ! } | |
467 | ||
468 | /* Otherwise, if the bb of a statement we care about isn't | |
469 | dominated by the header of the inner loop, then we can't | |
470 | *************** perfect_nestify (struct loops *loops, | |
471 | *** 2379,2392 **** | |
472 | tree stmt; | |
473 | tree oldivvar, ivvar, ivvarinced; | |
474 | VEC(tree,heap) *phis = NULL; | |
475 | ! | |
476 | ! if (!can_convert_to_perfect_nest (loop, loopivs)) | |
477 | ! return false; | |
478 | ! | |
479 | ! /* Create the new loop */ | |
480 | ! | |
481 | olddest = loop->single_exit->dest; | |
482 | ! preheaderbb = loop_split_edge_with (loop->single_exit, NULL); | |
483 | headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); | |
484 | ||
485 | /* Push the exit phi nodes that we are moving. */ | |
486 | --- 2442,2451 ---- | |
487 | tree stmt; | |
488 | tree oldivvar, ivvar, ivvarinced; | |
489 | VEC(tree,heap) *phis = NULL; | |
490 | ! | |
491 | ! /* Create the new loop. */ | |
492 | olddest = loop->single_exit->dest; | |
493 | ! preheaderbb = loop_split_edge_with (loop->single_exit, NULL); | |
494 | headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); | |
495 | ||
496 | /* Push the exit phi nodes that we are moving. */ | |
497 | *************** perfect_nestify (struct loops *loops, | |
498 | *** 2552,2561 **** | |
499 | continue; | |
500 | } | |
501 | ||
502 | ! replace_uses_equiv_to_x_with_y (loop, stmt, | |
503 | ! oldivvar, | |
504 | ! VEC_index (int, steps, 0), | |
505 | ! ivvar); | |
506 | bsi_move_before (&bsi, &tobsi); | |
507 | ||
508 | /* If the statement has any virtual operands, they may | |
509 | --- 2611,2619 ---- | |
510 | continue; | |
511 | } | |
512 | ||
513 | ! replace_uses_equiv_to_x_with_y | |
514 | ! (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar); | |
515 | ! | |
516 | bsi_move_before (&bsi, &tobsi); | |
517 | ||
518 | /* If the statement has any virtual operands, they may | |
519 |