]>
Commit | Line | Data |
---|---|---|
c913f08a ZD |
1 | /* High-level loop manipulation functions. |
2 | Copyright (C) 2004 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it | |
7 | under the terms of the GNU General Public License as published by the | |
8 | Free Software Foundation; either version 2, or (at your option) any | |
9 | later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT | |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "hard-reg-set.h" | |
29 | #include "basic-block.h" | |
30 | #include "output.h" | |
31 | #include "diagnostic.h" | |
32 | #include "tree-flow.h" | |
33 | #include "tree-dump.h" | |
34 | #include "timevar.h" | |
35 | #include "cfgloop.h" | |
36 | #include "tree-pass.h" | |
37 | #include "cfglayout.h" | |
38 | #include "tree-scalar-evolution.h" | |
39 | ||
82b85a85 ZD |
40 | /* Creates an induction variable with value BASE + STEP * iteration in LOOP. |
41 | It is expected that neither BASE nor STEP are shared with other expressions | |
42 | (unless the sharing rules allow this). Use VAR as a base var_decl for it | |
43 | (if NULL, a new temporary will be created). The increment will occur at | |
44 | INCR_POS (after it if AFTER is true, before it otherwise). The ssa versions | |
45 | of the variable before and after increment will be stored in VAR_BEFORE and | |
46 | VAR_AFTER (unless they are NULL). */ | |
47 | ||
48 | void | |
49 | create_iv (tree base, tree step, tree var, struct loop *loop, | |
50 | block_stmt_iterator *incr_pos, bool after, | |
51 | tree *var_before, tree *var_after) | |
52 | { | |
8b11a64c | 53 | tree stmt, initial, step1, stmts; |
82b85a85 ZD |
54 | tree vb, va; |
55 | enum tree_code incr_op = PLUS_EXPR; | |
56 | ||
57 | if (!var) | |
58 | { | |
59 | var = create_tmp_var (TREE_TYPE (base), "ivtmp"); | |
60 | add_referenced_tmp_var (var); | |
61 | } | |
62 | ||
63 | vb = make_ssa_name (var, NULL_TREE); | |
64 | if (var_before) | |
65 | *var_before = vb; | |
66 | va = make_ssa_name (var, NULL_TREE); | |
67 | if (var_after) | |
68 | *var_after = va; | |
69 | ||
70 | /* For easier readability of the created code, produce MINUS_EXPRs | |
71 | when suitable. */ | |
72 | if (TREE_CODE (step) == INTEGER_CST) | |
73 | { | |
74 | if (TYPE_UNSIGNED (TREE_TYPE (step))) | |
75 | { | |
76 | step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step)); | |
77 | if (tree_int_cst_lt (step1, step)) | |
78 | { | |
79 | incr_op = MINUS_EXPR; | |
80 | step = step1; | |
81 | } | |
82 | } | |
83 | else | |
84 | { | |
85 | if (!tree_expr_nonnegative_p (step) | |
86 | && may_negate_without_overflow_p (step)) | |
87 | { | |
88 | incr_op = MINUS_EXPR; | |
89 | step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step)); | |
90 | } | |
91 | } | |
92 | } | |
93 | ||
94 | stmt = build2 (MODIFY_EXPR, void_type_node, va, | |
95 | build2 (incr_op, TREE_TYPE (base), | |
96 | vb, step)); | |
97 | SSA_NAME_DEF_STMT (va) = stmt; | |
98 | if (after) | |
99 | bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT); | |
100 | else | |
101 | bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT); | |
102 | ||
8b11a64c ZD |
103 | initial = force_gimple_operand (base, &stmts, true, var); |
104 | if (stmts) | |
105 | { | |
106 | edge pe = loop_preheader_edge (loop); | |
107 | ||
108 | bsi_insert_on_edge_immediate_loop (pe, stmts); | |
109 | } | |
82b85a85 ZD |
110 | |
111 | stmt = create_phi_node (vb, loop->header); | |
112 | SSA_NAME_DEF_STMT (vb) = stmt; | |
113 | add_phi_arg (&stmt, initial, loop_preheader_edge (loop)); | |
114 | add_phi_arg (&stmt, va, loop_latch_edge (loop)); | |
115 | } | |
116 | ||
c913f08a ZD |
117 | /* Add exit phis for the USE on EXIT. */ |
118 | ||
119 | static void | |
120 | add_exit_phis_edge (basic_block exit, tree use) | |
121 | { | |
122 | tree phi, def_stmt = SSA_NAME_DEF_STMT (use); | |
123 | basic_block def_bb = bb_for_stmt (def_stmt); | |
124 | struct loop *def_loop; | |
125 | edge e; | |
628f6a4e | 126 | edge_iterator ei; |
c913f08a ZD |
127 | |
128 | /* Check that some of the edges entering the EXIT block exits a loop in | |
129 | that USE is defined. */ | |
628f6a4e | 130 | FOR_EACH_EDGE (e, ei, exit->preds) |
c913f08a ZD |
131 | { |
132 | def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); | |
133 | if (!flow_bb_inside_loop_p (def_loop, e->dest)) | |
134 | break; | |
135 | } | |
136 | ||
137 | if (!e) | |
138 | return; | |
139 | ||
140 | phi = create_phi_node (use, exit); | |
141 | ||
628f6a4e | 142 | FOR_EACH_EDGE (e, ei, exit->preds) |
c913f08a ZD |
143 | add_phi_arg (&phi, use, e); |
144 | ||
145 | SSA_NAME_DEF_STMT (use) = def_stmt; | |
146 | } | |
147 | ||
148 | /* Add exit phis for VAR that is used in LIVEIN. | |
149 | Exits of the loops are stored in EXITS. */ | |
150 | ||
151 | static void | |
152 | add_exit_phis_var (tree var, bitmap livein, bitmap exits) | |
153 | { | |
154 | bitmap def; | |
155 | int index; | |
156 | basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); | |
87c476a2 | 157 | bitmap_iterator bi; |
c913f08a ZD |
158 | |
159 | bitmap_clear_bit (livein, def_bb->index); | |
160 | ||
161 | def = BITMAP_XMALLOC (); | |
162 | bitmap_set_bit (def, def_bb->index); | |
163 | compute_global_livein (livein, def); | |
164 | BITMAP_XFREE (def); | |
165 | ||
87c476a2 ZD |
166 | EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) |
167 | { | |
168 | add_exit_phis_edge (BASIC_BLOCK (index), var); | |
169 | } | |
c913f08a ZD |
170 | } |
171 | ||
172 | /* Add exit phis for the names marked in NAMES_TO_RENAME. | |
173 | Exits of the loops are stored in EXITS. Sets of blocks where the ssa | |
174 | names are used are stored in USE_BLOCKS. */ | |
175 | ||
176 | static void | |
177 | add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) | |
178 | { | |
179 | unsigned i; | |
87c476a2 | 180 | bitmap_iterator bi; |
c913f08a | 181 | |
87c476a2 | 182 | EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) |
c913f08a ZD |
183 | { |
184 | add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); | |
87c476a2 | 185 | } |
c913f08a ZD |
186 | } |
187 | ||
188 | /* Returns a bitmap of all loop exit edge targets. */ | |
189 | ||
190 | static bitmap | |
191 | get_loops_exits (void) | |
192 | { | |
193 | bitmap exits = BITMAP_XMALLOC (); | |
194 | basic_block bb; | |
195 | edge e; | |
628f6a4e | 196 | edge_iterator ei; |
c913f08a ZD |
197 | |
198 | FOR_EACH_BB (bb) | |
199 | { | |
628f6a4e | 200 | FOR_EACH_EDGE (e, ei, bb->preds) |
c913f08a ZD |
201 | if (e->src != ENTRY_BLOCK_PTR |
202 | && !flow_bb_inside_loop_p (e->src->loop_father, bb)) | |
203 | { | |
204 | bitmap_set_bit (exits, bb->index); | |
205 | break; | |
206 | } | |
207 | } | |
208 | ||
209 | return exits; | |
210 | } | |
211 | ||
212 | /* For USE in BB, if it is used outside of the loop it is defined in, | |
213 | mark it for rewrite. Record basic block BB where it is used | |
214 | to USE_BLOCKS. */ | |
215 | ||
216 | static void | |
217 | find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) | |
218 | { | |
219 | unsigned ver; | |
220 | basic_block def_bb; | |
221 | struct loop *def_loop; | |
222 | ||
223 | if (TREE_CODE (use) != SSA_NAME) | |
224 | return; | |
225 | ||
226 | ver = SSA_NAME_VERSION (use); | |
227 | def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); | |
228 | if (!def_bb) | |
229 | return; | |
230 | def_loop = def_bb->loop_father; | |
231 | ||
232 | /* If the definition is not inside loop, it is not interesting. */ | |
233 | if (!def_loop->outer) | |
234 | return; | |
235 | ||
236 | if (!use_blocks[ver]) | |
237 | use_blocks[ver] = BITMAP_XMALLOC (); | |
238 | bitmap_set_bit (use_blocks[ver], bb->index); | |
239 | ||
240 | if (!flow_bb_inside_loop_p (def_loop, bb)) | |
241 | mark_for_rewrite (use); | |
242 | } | |
243 | ||
244 | /* For uses in STMT, mark names that are used outside of the loop they are | |
245 | defined to rewrite. Record the set of blocks in that the ssa | |
246 | names are defined to USE_BLOCKS. */ | |
247 | ||
248 | static void | |
249 | find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) | |
250 | { | |
4c124b4c AM |
251 | ssa_op_iter iter; |
252 | tree var; | |
c913f08a ZD |
253 | basic_block bb = bb_for_stmt (stmt); |
254 | ||
255 | get_stmt_operands (stmt); | |
c913f08a | 256 | |
4c124b4c AM |
257 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) |
258 | find_uses_to_rename_use (bb, var, use_blocks); | |
c913f08a ZD |
259 | } |
260 | ||
261 | /* Marks names that are used outside of the loop they are defined in | |
262 | for rewrite. Records the set of blocks in that the ssa | |
263 | names are defined to USE_BLOCKS. */ | |
264 | ||
265 | static void | |
266 | find_uses_to_rename (bitmap *use_blocks) | |
267 | { | |
268 | basic_block bb; | |
269 | block_stmt_iterator bsi; | |
270 | tree phi; | |
271 | unsigned i; | |
272 | ||
273 | FOR_EACH_BB (bb) | |
274 | { | |
275 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
276 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) | |
277 | find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src, | |
278 | PHI_ARG_DEF (phi, i), use_blocks); | |
279 | ||
280 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
281 | find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks); | |
282 | } | |
283 | } | |
284 | ||
285 | /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra | |
286 | phi nodes to ensure that no variable is used outside the loop it is | |
287 | defined in. | |
288 | ||
289 | This strengthening of the basic ssa form has several advantages: | |
290 | ||
291 | 1) Updating it during unrolling/peeling/versioning is trivial, since | |
292 | we do not need to care about the uses outside of the loop. | |
293 | 2) The behavior of all uses of an induction variable is the same. | |
294 | Without this, you need to distinguish the case when the variable | |
295 | is used outside of the loop it is defined in, for example | |
296 | ||
297 | for (i = 0; i < 100; i++) | |
298 | { | |
299 | for (j = 0; j < 100; j++) | |
300 | { | |
301 | k = i + j; | |
302 | use1 (k); | |
303 | } | |
304 | use2 (k); | |
305 | } | |
306 | ||
307 | Looking from the outer loop with the normal SSA form, the first use of k | |
308 | is not well-behaved, while the second one is an induction variable with | |
309 | base 99 and step 1. */ | |
310 | ||
311 | void | |
312 | rewrite_into_loop_closed_ssa (void) | |
313 | { | |
314 | bitmap loop_exits = get_loops_exits (); | |
315 | bitmap *use_blocks; | |
316 | unsigned i; | |
317 | bitmap names_to_rename; | |
318 | ||
1e128c5f | 319 | gcc_assert (!any_marked_for_rewrite_p ()); |
c913f08a ZD |
320 | |
321 | use_blocks = xcalloc (num_ssa_names, sizeof (bitmap)); | |
322 | ||
323 | /* Find the uses outside loops. */ | |
324 | find_uses_to_rename (use_blocks); | |
325 | ||
326 | /* Add the phi nodes on exits of the loops for the names we need to | |
327 | rewrite. */ | |
328 | names_to_rename = marked_ssa_names (); | |
329 | add_exit_phis (names_to_rename, use_blocks, loop_exits); | |
330 | ||
331 | for (i = 0; i < num_ssa_names; i++) | |
332 | BITMAP_XFREE (use_blocks[i]); | |
333 | free (use_blocks); | |
334 | BITMAP_XFREE (loop_exits); | |
335 | BITMAP_XFREE (names_to_rename); | |
336 | ||
337 | /* Do the rewriting. */ | |
338 | rewrite_ssa_into_ssa (); | |
339 | } | |
340 | ||
341 | /* Check invariants of the loop closed ssa form for the USE in BB. */ | |
342 | ||
343 | static void | |
344 | check_loop_closed_ssa_use (basic_block bb, tree use) | |
345 | { | |
346 | tree def; | |
347 | basic_block def_bb; | |
348 | ||
349 | if (TREE_CODE (use) != SSA_NAME) | |
350 | return; | |
351 | ||
352 | def = SSA_NAME_DEF_STMT (use); | |
353 | def_bb = bb_for_stmt (def); | |
1e128c5f GB |
354 | gcc_assert (!def_bb |
355 | || flow_bb_inside_loop_p (def_bb->loop_father, bb)); | |
c913f08a ZD |
356 | } |
357 | ||
358 | /* Checks invariants of loop closed ssa form in statement STMT in BB. */ | |
359 | ||
360 | static void | |
361 | check_loop_closed_ssa_stmt (basic_block bb, tree stmt) | |
362 | { | |
4c124b4c AM |
363 | ssa_op_iter iter; |
364 | tree var; | |
c913f08a ZD |
365 | |
366 | get_stmt_operands (stmt); | |
c913f08a | 367 | |
4c124b4c AM |
368 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) |
369 | check_loop_closed_ssa_use (bb, var); | |
c913f08a ZD |
370 | } |
371 | ||
372 | /* Checks that invariants of the loop closed ssa form are preserved. */ | |
373 | ||
374 | void | |
375 | verify_loop_closed_ssa (void) | |
376 | { | |
377 | basic_block bb; | |
378 | block_stmt_iterator bsi; | |
379 | tree phi; | |
380 | unsigned i; | |
381 | ||
382 | verify_ssa (); | |
383 | ||
384 | FOR_EACH_BB (bb) | |
385 | { | |
386 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
387 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) | |
388 | check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, | |
389 | PHI_ARG_DEF (phi, i)); | |
390 | ||
391 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
392 | check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); | |
393 | } | |
394 | } | |
8b11a64c ZD |
395 | |
396 | /* Split loop exit edge EXIT. The things are a bit complicated by a need to | |
397 | preserve the loop closed ssa form. */ | |
398 | ||
399 | void | |
400 | split_loop_exit_edge (edge exit) | |
401 | { | |
402 | basic_block dest = exit->dest; | |
403 | basic_block bb = loop_split_edge_with (exit, NULL); | |
7fac6722 | 404 | tree phi, new_phi, new_name, name; |
8b11a64c ZD |
405 | use_operand_p op_p; |
406 | ||
407 | for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi)) | |
408 | { | |
628f6a4e | 409 | op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0)); |
8b11a64c | 410 | |
7fac6722 ZD |
411 | name = USE_FROM_PTR (op_p); |
412 | ||
413 | /* If the argument of the phi node is a constant, we do not need | |
414 | to keep it inside loop. */ | |
415 | if (TREE_CODE (name) != SSA_NAME) | |
416 | continue; | |
417 | ||
418 | /* Otherwise create an auxiliary phi node that will copy the value | |
419 | of the ssa name out of the loop. */ | |
420 | new_name = duplicate_ssa_name (name, NULL); | |
8b11a64c ZD |
421 | new_phi = create_phi_node (new_name, bb); |
422 | SSA_NAME_DEF_STMT (new_name) = new_phi; | |
7fac6722 | 423 | add_phi_arg (&new_phi, name, exit); |
8b11a64c ZD |
424 | SET_USE (op_p, new_name); |
425 | } | |
426 | } | |
427 | ||
428 | /* Insert statement STMT to the edge E and update the loop structures. | |
429 | Returns the newly created block (if any). */ | |
430 | ||
431 | basic_block | |
432 | bsi_insert_on_edge_immediate_loop (edge e, tree stmt) | |
433 | { | |
434 | basic_block src, dest, new_bb; | |
435 | struct loop *loop_c; | |
436 | ||
437 | src = e->src; | |
438 | dest = e->dest; | |
439 | ||
440 | loop_c = find_common_loop (src->loop_father, dest->loop_father); | |
441 | ||
442 | new_bb = bsi_insert_on_edge_immediate (e, stmt); | |
443 | ||
444 | if (!new_bb) | |
445 | return NULL; | |
446 | ||
447 | add_bb_to_loop (new_bb, loop_c); | |
448 | if (dest->loop_father->latch == src) | |
449 | dest->loop_father->latch = new_bb; | |
450 | ||
451 | return new_bb; | |
452 | } | |
453 | ||
454 | /* Returns the basic block in that statements should be emitted for induction | |
455 | variables incremented at the end of the LOOP. */ | |
456 | ||
457 | basic_block | |
458 | ip_end_pos (struct loop *loop) | |
459 | { | |
460 | return loop->latch; | |
461 | } | |
462 | ||
463 | /* Returns the basic block in that statements should be emitted for induction | |
464 | variables incremented just before exit condition of a LOOP. */ | |
465 | ||
466 | basic_block | |
467 | ip_normal_pos (struct loop *loop) | |
468 | { | |
469 | tree last; | |
470 | basic_block bb; | |
471 | edge exit; | |
472 | ||
628f6a4e | 473 | if (EDGE_COUNT (loop->latch->preds) > 1) |
8b11a64c ZD |
474 | return NULL; |
475 | ||
628f6a4e | 476 | bb = EDGE_PRED (loop->latch, 0)->src; |
8b11a64c ZD |
477 | last = last_stmt (bb); |
478 | if (TREE_CODE (last) != COND_EXPR) | |
479 | return NULL; | |
480 | ||
628f6a4e | 481 | exit = EDGE_SUCC (bb, 0); |
8b11a64c | 482 | if (exit->dest == loop->latch) |
628f6a4e | 483 | exit = EDGE_SUCC (bb, 1); |
8b11a64c ZD |
484 | |
485 | if (flow_bb_inside_loop_p (loop, exit->dest)) | |
486 | return NULL; | |
487 | ||
488 | return bb; | |
489 | } | |
490 | ||
491 | /* Stores the standard position for induction variable increment in LOOP | |
492 | (just before the exit condition if it is available and latch block is empty, | |
493 | end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if | |
494 | the increment should be inserted after *BSI. */ | |
495 | ||
496 | void | |
497 | standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, | |
498 | bool *insert_after) | |
499 | { | |
500 | basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); | |
501 | tree last = last_stmt (latch); | |
502 | ||
503 | if (!bb | |
504 | || (last && TREE_CODE (last) != LABEL_EXPR)) | |
505 | { | |
506 | *bsi = bsi_last (latch); | |
507 | *insert_after = true; | |
508 | } | |
509 | else | |
510 | { | |
511 | *bsi = bsi_last (bb); | |
512 | *insert_after = false; | |
513 | } | |
514 | } | |
92fc4a2f ZD |
515 | |
516 | /* Copies phi node arguments for duplicated blocks. The index of the first | |
517 | duplicated block is FIRST_NEW_BLOCK. */ | |
518 | ||
519 | static void | |
520 | copy_phi_node_args (unsigned first_new_block) | |
521 | { | |
522 | unsigned i; | |
523 | ||
524 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
525 | BASIC_BLOCK (i)->rbi->duplicated = 1; | |
526 | ||
527 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
528 | add_phi_args_after_copy_bb (BASIC_BLOCK (i)); | |
529 | ||
530 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
531 | BASIC_BLOCK (i)->rbi->duplicated = 0; | |
532 | } | |
533 | ||
534 | /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge. | |
535 | FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is | |
536 | a bitmap of all ssa names defined inside the loop. */ | |
537 | ||
538 | static void | |
539 | rename_variables (unsigned first_new_block, bitmap definitions) | |
540 | { | |
541 | unsigned i, copy_number = 0; | |
542 | basic_block bb; | |
543 | htab_t ssa_name_map = NULL; | |
544 | ||
545 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
546 | { | |
547 | bb = BASIC_BLOCK (i); | |
548 | ||
549 | /* We assume that first come all blocks from the first copy, then all | |
550 | blocks from the second copy, etc. */ | |
551 | if (copy_number != (unsigned) bb->rbi->copy_number) | |
552 | { | |
553 | allocate_ssa_names (definitions, &ssa_name_map); | |
554 | copy_number = bb->rbi->copy_number; | |
555 | } | |
556 | ||
557 | rewrite_to_new_ssa_names_bb (bb, ssa_name_map); | |
558 | } | |
559 | ||
560 | htab_delete (ssa_name_map); | |
561 | } | |
562 | ||
563 | /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */ | |
564 | ||
565 | static void | |
566 | set_phi_def_stmts (basic_block bb) | |
567 | { | |
568 | tree phi; | |
569 | ||
570 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
571 | SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi; | |
572 | } | |
573 | ||
574 | /* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates | |
575 | ssa. In order to achieve this, only loops whose exits all lead to the same | |
576 | location are handled. | |
577 | ||
578 | FIXME: we create some degenerate phi nodes that could be avoided by copy | |
579 | propagating them instead. Unfortunately this is not completely | |
580 | straightforward due to problems with constant folding. */ | |
581 | ||
582 | bool | |
583 | tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, | |
584 | struct loops *loops, | |
585 | unsigned int ndupl, sbitmap wont_exit, | |
586 | edge orig, edge *to_remove, | |
587 | unsigned int *n_to_remove, int flags) | |
588 | { | |
589 | unsigned first_new_block; | |
590 | basic_block bb; | |
591 | unsigned i; | |
592 | tree phi, arg, map, def; | |
593 | bitmap definitions; | |
594 | ||
595 | if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) | |
596 | return false; | |
597 | if (!(loops->state & LOOPS_HAVE_PREHEADERS)) | |
598 | return false; | |
599 | ||
600 | #ifdef ENABLE_CHECKING | |
601 | verify_loop_closed_ssa (); | |
602 | #endif | |
603 | ||
604 | gcc_assert (!any_marked_for_rewrite_p ()); | |
605 | ||
606 | first_new_block = last_basic_block; | |
607 | if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, | |
608 | orig, to_remove, n_to_remove, flags)) | |
609 | return false; | |
610 | ||
611 | /* Readd the removed phi args for e. */ | |
612 | map = PENDING_STMT (e); | |
613 | PENDING_STMT (e) = NULL; | |
614 | ||
615 | for (phi = phi_nodes (e->dest), arg = map; | |
616 | phi; | |
617 | phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg)) | |
618 | { | |
619 | def = TREE_VALUE (arg); | |
620 | add_phi_arg (&phi, def, e); | |
621 | } | |
622 | gcc_assert (arg == NULL); | |
623 | ||
624 | /* Copy the phi node arguments. */ | |
625 | copy_phi_node_args (first_new_block); | |
626 | ||
627 | /* Rename the variables. */ | |
628 | definitions = marked_ssa_names (); | |
629 | rename_variables (first_new_block, definitions); | |
630 | unmark_all_for_rewrite (); | |
631 | BITMAP_XFREE (definitions); | |
632 | ||
633 | /* For some time we have the identical ssa names as results in multiple phi | |
634 | nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result | |
635 | to the new copy. This means that we cannot easily ensure that the ssa | |
636 | names defined in those phis are pointing to the right one -- so just | |
637 | recompute SSA_NAME_DEF_STMT for them. */ | |
638 | ||
639 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
640 | { | |
641 | bb = BASIC_BLOCK (i); | |
642 | set_phi_def_stmts (bb); | |
643 | if (bb->rbi->copy_number == 1) | |
644 | set_phi_def_stmts (bb->rbi->original); | |
645 | } | |
646 | ||
647 | scev_reset (); | |
648 | #ifdef ENABLE_CHECKING | |
649 | verify_loop_closed_ssa (); | |
650 | #endif | |
651 | ||
652 | return true; | |
653 | } | |
654 | ||
655 | /*--------------------------------------------------------------------------- | |
656 | Loop versioning | |
657 | ---------------------------------------------------------------------------*/ | |
658 | ||
659 | /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy | |
660 | of 'first'. Both of them are dominated by 'new_head' basic block. When | |
661 | 'new_head' was created by 'second's incoming edge it received phi arguments | |
662 | on the edge by split_edge(). Later, additional edge 'e' was created to | |
663 | connect 'new_head' and 'first'. Now this routine adds phi args on this | |
664 | additional edge 'e' that new_head to second edge received as part of edge | |
665 | splitting. | |
666 | */ | |
667 | ||
668 | static void | |
669 | lv_adjust_loop_header_phi (basic_block first, basic_block second, | |
670 | basic_block new_head, edge e) | |
671 | { | |
672 | tree phi1, phi2; | |
673 | ||
674 | /* Browse all 'second' basic block phi nodes and add phi args to | |
675 | edge 'e' for 'first' head. PHI args are always in correct order. */ | |
676 | ||
677 | for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); | |
678 | phi2 && phi1; | |
679 | phi2 = TREE_CHAIN (phi2), phi1 = TREE_CHAIN (phi1)) | |
680 | { | |
681 | int i; | |
682 | for (i = 0; i < PHI_NUM_ARGS (phi2); i++) | |
683 | { | |
684 | if (PHI_ARG_EDGE (phi2, i)->src == new_head) | |
685 | { | |
686 | tree def = PHI_ARG_DEF (phi2, i); | |
687 | add_phi_arg (&phi1, def, e); | |
688 | } | |
689 | } | |
690 | } | |
691 | } | |
692 | ||
693 | /* Adjust entry edge for lv. | |
694 | ||
695 | e is a incoming edge. | |
696 | ||
697 | --- edge e ---- > [second_head] | |
698 | ||
699 | Split it and insert new conditional expression and adjust edges. | |
700 | ||
701 | --- edge e ---> [cond expr] ---> [first_head] | |
702 | | | |
703 | +---------> [second_head] | |
704 | ||
705 | */ | |
706 | ||
707 | static basic_block | |
708 | lv_adjust_loop_entry_edge (basic_block first_head, | |
709 | basic_block second_head, | |
710 | edge e, | |
711 | tree cond_expr) | |
712 | { | |
713 | block_stmt_iterator bsi; | |
714 | basic_block new_head = NULL; | |
715 | tree goto1 = NULL_TREE; | |
716 | tree goto2 = NULL_TREE; | |
717 | tree new_cond_expr = NULL_TREE; | |
718 | edge e0, e1; | |
719 | ||
720 | gcc_assert (e->dest == second_head); | |
721 | ||
722 | /* Split edge 'e'. This will create a new basic block, where we can | |
723 | insert conditional expr. */ | |
724 | new_head = split_edge (e); | |
725 | ||
726 | /* Build new conditional expr */ | |
727 | goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head)); | |
728 | goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head)); | |
729 | new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2); | |
730 | ||
731 | /* Add new cond. in new head. */ | |
732 | bsi = bsi_start (new_head); | |
733 | bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT); | |
734 | ||
735 | /* Adjust edges appropriately to connect new head with first head | |
736 | as well as second head. */ | |
628f6a4e | 737 | e0 = EDGE_SUCC (new_head, 0); |
92fc4a2f ZD |
738 | e0->flags &= ~EDGE_FALLTHRU; |
739 | e0->flags |= EDGE_FALSE_VALUE; | |
740 | e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE); | |
741 | set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); | |
742 | set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); | |
743 | ||
744 | /* Adjust loop header phi nodes. */ | |
745 | lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); | |
746 | ||
747 | return new_head; | |
748 | } | |
749 | ||
750 | /* Add phi args using PENDINT_STMT list. */ | |
751 | ||
752 | static void | |
753 | lv_update_pending_stmts (edge e) | |
754 | { | |
755 | basic_block dest; | |
756 | tree phi, arg, def; | |
757 | ||
758 | if (!PENDING_STMT (e)) | |
759 | return; | |
760 | ||
761 | dest = e->dest; | |
762 | ||
763 | for (phi = phi_nodes (dest), arg = PENDING_STMT (e); | |
764 | phi; | |
765 | phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg)) | |
766 | { | |
767 | def = TREE_VALUE (arg); | |
768 | add_phi_arg (&phi, def, e); | |
769 | } | |
770 | ||
771 | PENDING_STMT (e) = NULL; | |
772 | } | |
773 | ||
774 | ||
775 | /* Main entry point for Loop Versioning transformation. | |
776 | ||
777 | This transformation given a condition and a loop, creates | |
778 | -if (condition) { loop_copy1 } else { loop_copy2 }, | |
779 | where loop_copy1 is the loop transformed in one way, and loop_copy2 | |
780 | is the loop transformed in another way (or unchanged). 'condition' | |
781 | may be a run time test for things that were not resolved by static | |
782 | analysis (overlapping ranges (anti-aliasing), alignment, etc.). */ | |
783 | ||
784 | struct loop * | |
785 | tree_ssa_loop_version (struct loops *loops, struct loop * loop, | |
786 | tree cond_expr, basic_block *condition_bb) | |
787 | { | |
788 | edge entry, latch_edge, exit; | |
789 | basic_block first_head, second_head; | |
790 | int irred_flag; | |
791 | struct loop *nloop; | |
792 | ||
793 | /* CHECKME: Loop versioning does not handle nested loop at this point. */ | |
794 | if (loop->inner) | |
795 | return NULL; | |
796 | ||
797 | /* Record entry and latch edges for the loop */ | |
798 | entry = loop_preheader_edge (loop); | |
799 | ||
800 | /* Note down head of loop as first_head. */ | |
801 | first_head = entry->dest; | |
802 | ||
803 | /* Duplicate loop. */ | |
804 | irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; | |
805 | entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; | |
806 | if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1, | |
807 | NULL, NULL, NULL, NULL, 0)) | |
808 | { | |
809 | entry->flags |= irred_flag; | |
810 | return NULL; | |
811 | } | |
812 | ||
813 | /* After duplication entry edge now points to new loop head block. | |
814 | Note down new head as second_head. */ | |
815 | second_head = entry->dest; | |
816 | ||
817 | /* Split loop entry edge and insert new block with cond expr. */ | |
818 | *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, | |
819 | cond_expr); | |
820 | ||
628f6a4e | 821 | latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0); |
92fc4a2f ZD |
822 | nloop = loopify (loops, |
823 | latch_edge, | |
628f6a4e | 824 | EDGE_PRED (loop->header->rbi->copy, 0), |
92fc4a2f ZD |
825 | *condition_bb, |
826 | false /* Do not redirect all edges. */); | |
827 | ||
828 | exit = loop->single_exit; | |
829 | if (exit) | |
830 | nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest); | |
831 | ||
832 | /* loopify redirected latch_edge. Update its PENDING_STMTS. */ | |
833 | lv_update_pending_stmts (latch_edge); | |
834 | ||
835 | /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ | |
836 | lv_update_pending_stmts (FALLTHRU_EDGE (*condition_bb)); | |
837 | ||
838 | /* Adjust irreducible flag. */ | |
839 | if (irred_flag) | |
840 | { | |
841 | (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP; | |
842 | loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; | |
843 | loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; | |
628f6a4e | 844 | EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP; |
92fc4a2f ZD |
845 | } |
846 | ||
847 | /* At this point condition_bb is loop predheader with two successors, | |
848 | first_head and second_head. Make sure that loop predheader has only | |
849 | one successor. */ | |
850 | loop_split_edge_with (loop_preheader_edge (loop), NULL); | |
851 | loop_split_edge_with (loop_preheader_edge (nloop), NULL); | |
852 | ||
853 | return nloop; | |
854 | } |