]>
Commit | Line | Data |
---|---|---|
c913f08a | 1 | /* High-level loop manipulation functions. |
6a6305e4 | 2 | Copyright (C) 2004, 2005 Free Software Foundation, Inc. |
c913f08a ZD |
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 | |
92d2b330 SP |
44 | INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and |
45 | AFTER can be computed using standard_iv_increment_position. The ssa versions | |
82b85a85 ZD |
46 | of the variable before and after increment will be stored in VAR_BEFORE and |
47 | VAR_AFTER (unless they are NULL). */ | |
48 | ||
49 | void | |
50 | create_iv (tree base, tree step, tree var, struct loop *loop, | |
51 | block_stmt_iterator *incr_pos, bool after, | |
52 | tree *var_before, tree *var_after) | |
53 | { | |
8b11a64c | 54 | tree stmt, initial, step1, stmts; |
82b85a85 ZD |
55 | tree vb, va; |
56 | enum tree_code incr_op = PLUS_EXPR; | |
57 | ||
58 | if (!var) | |
59 | { | |
60 | var = create_tmp_var (TREE_TYPE (base), "ivtmp"); | |
61 | add_referenced_tmp_var (var); | |
62 | } | |
63 | ||
64 | vb = make_ssa_name (var, NULL_TREE); | |
65 | if (var_before) | |
66 | *var_before = vb; | |
67 | va = make_ssa_name (var, NULL_TREE); | |
68 | if (var_after) | |
69 | *var_after = va; | |
70 | ||
71 | /* For easier readability of the created code, produce MINUS_EXPRs | |
72 | when suitable. */ | |
73 | if (TREE_CODE (step) == INTEGER_CST) | |
74 | { | |
75 | if (TYPE_UNSIGNED (TREE_TYPE (step))) | |
76 | { | |
77 | step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step)); | |
78 | if (tree_int_cst_lt (step1, step)) | |
79 | { | |
80 | incr_op = MINUS_EXPR; | |
81 | step = step1; | |
82 | } | |
83 | } | |
84 | else | |
85 | { | |
86 | if (!tree_expr_nonnegative_p (step) | |
87 | && may_negate_without_overflow_p (step)) | |
88 | { | |
89 | incr_op = MINUS_EXPR; | |
90 | step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step)); | |
91 | } | |
92 | } | |
93 | } | |
94 | ||
95 | stmt = build2 (MODIFY_EXPR, void_type_node, va, | |
96 | build2 (incr_op, TREE_TYPE (base), | |
97 | vb, step)); | |
98 | SSA_NAME_DEF_STMT (va) = stmt; | |
99 | if (after) | |
100 | bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT); | |
101 | else | |
102 | bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT); | |
103 | ||
8b11a64c ZD |
104 | initial = force_gimple_operand (base, &stmts, true, var); |
105 | if (stmts) | |
106 | { | |
107 | edge pe = loop_preheader_edge (loop); | |
108 | ||
109 | bsi_insert_on_edge_immediate_loop (pe, stmts); | |
110 | } | |
82b85a85 ZD |
111 | |
112 | stmt = create_phi_node (vb, loop->header); | |
113 | SSA_NAME_DEF_STMT (vb) = stmt; | |
d2e398df KH |
114 | add_phi_arg (stmt, initial, loop_preheader_edge (loop)); |
115 | add_phi_arg (stmt, va, loop_latch_edge (loop)); | |
82b85a85 ZD |
116 | } |
117 | ||
c913f08a ZD |
118 | /* Add exit phis for the USE on EXIT. */ |
119 | ||
120 | static void | |
121 | add_exit_phis_edge (basic_block exit, tree use) | |
122 | { | |
123 | tree phi, def_stmt = SSA_NAME_DEF_STMT (use); | |
124 | basic_block def_bb = bb_for_stmt (def_stmt); | |
125 | struct loop *def_loop; | |
126 | edge e; | |
628f6a4e | 127 | edge_iterator ei; |
c913f08a ZD |
128 | |
129 | /* Check that some of the edges entering the EXIT block exits a loop in | |
130 | that USE is defined. */ | |
628f6a4e | 131 | FOR_EACH_EDGE (e, ei, exit->preds) |
c913f08a ZD |
132 | { |
133 | def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); | |
134 | if (!flow_bb_inside_loop_p (def_loop, e->dest)) | |
135 | break; | |
136 | } | |
137 | ||
138 | if (!e) | |
139 | return; | |
140 | ||
141 | phi = create_phi_node (use, exit); | |
142 | ||
628f6a4e | 143 | FOR_EACH_EDGE (e, ei, exit->preds) |
d2e398df | 144 | add_phi_arg (phi, use, e); |
c913f08a ZD |
145 | |
146 | SSA_NAME_DEF_STMT (use) = def_stmt; | |
147 | } | |
148 | ||
149 | /* Add exit phis for VAR that is used in LIVEIN. | |
150 | Exits of the loops are stored in EXITS. */ | |
151 | ||
152 | static void | |
153 | add_exit_phis_var (tree var, bitmap livein, bitmap exits) | |
154 | { | |
155 | bitmap def; | |
3cd8c58a | 156 | unsigned index; |
c913f08a | 157 | basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); |
87c476a2 | 158 | bitmap_iterator bi; |
c913f08a | 159 | |
0bca51f0 DN |
160 | if (is_gimple_reg (var)) |
161 | bitmap_clear_bit (livein, def_bb->index); | |
162 | else | |
163 | bitmap_set_bit (livein, def_bb->index); | |
c913f08a | 164 | |
8bdbfff5 | 165 | def = BITMAP_ALLOC (NULL); |
c913f08a ZD |
166 | bitmap_set_bit (def, def_bb->index); |
167 | compute_global_livein (livein, def); | |
8bdbfff5 | 168 | BITMAP_FREE (def); |
c913f08a | 169 | |
87c476a2 ZD |
170 | EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) |
171 | { | |
172 | add_exit_phis_edge (BASIC_BLOCK (index), var); | |
173 | } | |
c913f08a ZD |
174 | } |
175 | ||
176 | /* Add exit phis for the names marked in NAMES_TO_RENAME. | |
177 | Exits of the loops are stored in EXITS. Sets of blocks where the ssa | |
178 | names are used are stored in USE_BLOCKS. */ | |
179 | ||
180 | static void | |
181 | add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) | |
182 | { | |
183 | unsigned i; | |
87c476a2 | 184 | bitmap_iterator bi; |
c913f08a | 185 | |
87c476a2 | 186 | EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) |
c913f08a ZD |
187 | { |
188 | add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); | |
87c476a2 | 189 | } |
c913f08a ZD |
190 | } |
191 | ||
192 | /* Returns a bitmap of all loop exit edge targets. */ | |
193 | ||
194 | static bitmap | |
195 | get_loops_exits (void) | |
196 | { | |
8bdbfff5 | 197 | bitmap exits = BITMAP_ALLOC (NULL); |
c913f08a ZD |
198 | basic_block bb; |
199 | edge e; | |
628f6a4e | 200 | edge_iterator ei; |
c913f08a ZD |
201 | |
202 | FOR_EACH_BB (bb) | |
203 | { | |
628f6a4e | 204 | FOR_EACH_EDGE (e, ei, bb->preds) |
c913f08a ZD |
205 | if (e->src != ENTRY_BLOCK_PTR |
206 | && !flow_bb_inside_loop_p (e->src->loop_father, bb)) | |
207 | { | |
208 | bitmap_set_bit (exits, bb->index); | |
209 | break; | |
210 | } | |
211 | } | |
212 | ||
213 | return exits; | |
214 | } | |
215 | ||
216 | /* For USE in BB, if it is used outside of the loop it is defined in, | |
217 | mark it for rewrite. Record basic block BB where it is used | |
218 | to USE_BLOCKS. */ | |
219 | ||
220 | static void | |
221 | find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) | |
222 | { | |
223 | unsigned ver; | |
224 | basic_block def_bb; | |
225 | struct loop *def_loop; | |
226 | ||
227 | if (TREE_CODE (use) != SSA_NAME) | |
228 | return; | |
229 | ||
230 | ver = SSA_NAME_VERSION (use); | |
231 | def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); | |
232 | if (!def_bb) | |
233 | return; | |
234 | def_loop = def_bb->loop_father; | |
235 | ||
236 | /* If the definition is not inside loop, it is not interesting. */ | |
237 | if (!def_loop->outer) | |
238 | return; | |
239 | ||
240 | if (!use_blocks[ver]) | |
8bdbfff5 | 241 | use_blocks[ver] = BITMAP_ALLOC (NULL); |
c913f08a ZD |
242 | bitmap_set_bit (use_blocks[ver], bb->index); |
243 | ||
244 | if (!flow_bb_inside_loop_p (def_loop, bb)) | |
245 | mark_for_rewrite (use); | |
246 | } | |
247 | ||
248 | /* For uses in STMT, mark names that are used outside of the loop they are | |
249 | defined to rewrite. Record the set of blocks in that the ssa | |
250 | names are defined to USE_BLOCKS. */ | |
251 | ||
252 | static void | |
253 | find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) | |
254 | { | |
4c124b4c AM |
255 | ssa_op_iter iter; |
256 | tree var; | |
c913f08a ZD |
257 | basic_block bb = bb_for_stmt (stmt); |
258 | ||
52328bf6 | 259 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) |
4c124b4c | 260 | find_uses_to_rename_use (bb, var, use_blocks); |
c913f08a ZD |
261 | } |
262 | ||
2b271002 ZD |
263 | /* Marks names that are used in BB and outside of the loop they are |
264 | defined in for rewrite. Records the set of blocks in that the ssa | |
c913f08a ZD |
265 | names are defined to USE_BLOCKS. */ |
266 | ||
267 | static void | |
2b271002 | 268 | find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks) |
c913f08a | 269 | { |
c913f08a | 270 | block_stmt_iterator bsi; |
2b271002 ZD |
271 | edge e; |
272 | edge_iterator ei; | |
c913f08a | 273 | tree phi; |
c913f08a | 274 | |
2b271002 ZD |
275 | FOR_EACH_EDGE (e, ei, bb->succs) |
276 | for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) | |
277 | find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), | |
278 | 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 | /* Marks names that are used outside of the loop they are defined in | |
285 | for rewrite. Records the set of blocks in that the ssa | |
286 | names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, | |
287 | scan only blocks in this set. */ | |
288 | ||
289 | static void | |
290 | find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks) | |
291 | { | |
292 | basic_block bb; | |
293 | unsigned index; | |
294 | bitmap_iterator bi; | |
c913f08a | 295 | |
2b271002 ZD |
296 | if (changed_bbs) |
297 | { | |
298 | EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) | |
299 | { | |
300 | find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks); | |
301 | } | |
302 | } | |
303 | else | |
304 | { | |
305 | FOR_EACH_BB (bb) | |
306 | { | |
307 | find_uses_to_rename_bb (bb, use_blocks); | |
308 | } | |
c913f08a ZD |
309 | } |
310 | } | |
311 | ||
312 | /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra | |
313 | phi nodes to ensure that no variable is used outside the loop it is | |
314 | defined in. | |
315 | ||
316 | This strengthening of the basic ssa form has several advantages: | |
317 | ||
318 | 1) Updating it during unrolling/peeling/versioning is trivial, since | |
319 | we do not need to care about the uses outside of the loop. | |
320 | 2) The behavior of all uses of an induction variable is the same. | |
321 | Without this, you need to distinguish the case when the variable | |
322 | is used outside of the loop it is defined in, for example | |
323 | ||
324 | for (i = 0; i < 100; i++) | |
325 | { | |
326 | for (j = 0; j < 100; j++) | |
327 | { | |
328 | k = i + j; | |
329 | use1 (k); | |
330 | } | |
331 | use2 (k); | |
332 | } | |
333 | ||
334 | Looking from the outer loop with the normal SSA form, the first use of k | |
335 | is not well-behaved, while the second one is an induction variable with | |
2b271002 ZD |
336 | base 99 and step 1. |
337 | ||
338 | If CHANGED_BBS is not NULL, we look for uses outside loops only in | |
339 | the basic blocks in this set. */ | |
c913f08a ZD |
340 | |
341 | void | |
2b271002 | 342 | rewrite_into_loop_closed_ssa (bitmap changed_bbs) |
c913f08a ZD |
343 | { |
344 | bitmap loop_exits = get_loops_exits (); | |
345 | bitmap *use_blocks; | |
346 | unsigned i; | |
347 | bitmap names_to_rename; | |
348 | ||
1e128c5f | 349 | gcc_assert (!any_marked_for_rewrite_p ()); |
c913f08a ZD |
350 | |
351 | use_blocks = xcalloc (num_ssa_names, sizeof (bitmap)); | |
352 | ||
353 | /* Find the uses outside loops. */ | |
2b271002 ZD |
354 | find_uses_to_rename (changed_bbs, use_blocks); |
355 | ||
356 | if (!any_marked_for_rewrite_p ()) | |
357 | { | |
358 | free (use_blocks); | |
359 | BITMAP_FREE (loop_exits); | |
360 | return; | |
361 | } | |
c913f08a ZD |
362 | |
363 | /* Add the phi nodes on exits of the loops for the names we need to | |
364 | rewrite. */ | |
365 | names_to_rename = marked_ssa_names (); | |
366 | add_exit_phis (names_to_rename, use_blocks, loop_exits); | |
367 | ||
368 | for (i = 0; i < num_ssa_names; i++) | |
8bdbfff5 | 369 | BITMAP_FREE (use_blocks[i]); |
c913f08a | 370 | free (use_blocks); |
8bdbfff5 NS |
371 | BITMAP_FREE (loop_exits); |
372 | BITMAP_FREE (names_to_rename); | |
c913f08a ZD |
373 | |
374 | /* Do the rewriting. */ | |
375 | rewrite_ssa_into_ssa (); | |
376 | } | |
377 | ||
378 | /* Check invariants of the loop closed ssa form for the USE in BB. */ | |
379 | ||
380 | static void | |
381 | check_loop_closed_ssa_use (basic_block bb, tree use) | |
382 | { | |
383 | tree def; | |
384 | basic_block def_bb; | |
385 | ||
386 | if (TREE_CODE (use) != SSA_NAME) | |
387 | return; | |
388 | ||
389 | def = SSA_NAME_DEF_STMT (use); | |
390 | def_bb = bb_for_stmt (def); | |
1e128c5f GB |
391 | gcc_assert (!def_bb |
392 | || flow_bb_inside_loop_p (def_bb->loop_father, bb)); | |
c913f08a ZD |
393 | } |
394 | ||
395 | /* Checks invariants of loop closed ssa form in statement STMT in BB. */ | |
396 | ||
397 | static void | |
398 | check_loop_closed_ssa_stmt (basic_block bb, tree stmt) | |
399 | { | |
4c124b4c AM |
400 | ssa_op_iter iter; |
401 | tree var; | |
c913f08a | 402 | |
4c124b4c AM |
403 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) |
404 | check_loop_closed_ssa_use (bb, var); | |
c913f08a ZD |
405 | } |
406 | ||
407 | /* Checks that invariants of the loop closed ssa form are preserved. */ | |
408 | ||
409 | void | |
410 | verify_loop_closed_ssa (void) | |
411 | { | |
412 | basic_block bb; | |
413 | block_stmt_iterator bsi; | |
414 | tree phi; | |
415 | unsigned i; | |
416 | ||
f430bae8 | 417 | verify_ssa (false); |
c913f08a ZD |
418 | |
419 | FOR_EACH_BB (bb) | |
420 | { | |
bb29d951 | 421 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
c913f08a ZD |
422 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) |
423 | check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, | |
424 | PHI_ARG_DEF (phi, i)); | |
425 | ||
426 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
427 | check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); | |
428 | } | |
429 | } | |
8b11a64c ZD |
430 | |
431 | /* Split loop exit edge EXIT. The things are a bit complicated by a need to | |
432 | preserve the loop closed ssa form. */ | |
433 | ||
434 | void | |
435 | split_loop_exit_edge (edge exit) | |
436 | { | |
437 | basic_block dest = exit->dest; | |
438 | basic_block bb = loop_split_edge_with (exit, NULL); | |
7fac6722 | 439 | tree phi, new_phi, new_name, name; |
8b11a64c ZD |
440 | use_operand_p op_p; |
441 | ||
bb29d951 | 442 | for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) |
8b11a64c | 443 | { |
c5cbcccf | 444 | op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); |
8b11a64c | 445 | |
7fac6722 ZD |
446 | name = USE_FROM_PTR (op_p); |
447 | ||
448 | /* If the argument of the phi node is a constant, we do not need | |
449 | to keep it inside loop. */ | |
450 | if (TREE_CODE (name) != SSA_NAME) | |
451 | continue; | |
452 | ||
453 | /* Otherwise create an auxiliary phi node that will copy the value | |
454 | of the ssa name out of the loop. */ | |
455 | new_name = duplicate_ssa_name (name, NULL); | |
8b11a64c ZD |
456 | new_phi = create_phi_node (new_name, bb); |
457 | SSA_NAME_DEF_STMT (new_name) = new_phi; | |
d2e398df | 458 | add_phi_arg (new_phi, name, exit); |
8b11a64c ZD |
459 | SET_USE (op_p, new_name); |
460 | } | |
461 | } | |
462 | ||
463 | /* Insert statement STMT to the edge E and update the loop structures. | |
464 | Returns the newly created block (if any). */ | |
465 | ||
466 | basic_block | |
467 | bsi_insert_on_edge_immediate_loop (edge e, tree stmt) | |
468 | { | |
469 | basic_block src, dest, new_bb; | |
470 | struct loop *loop_c; | |
471 | ||
472 | src = e->src; | |
473 | dest = e->dest; | |
474 | ||
475 | loop_c = find_common_loop (src->loop_father, dest->loop_father); | |
476 | ||
477 | new_bb = bsi_insert_on_edge_immediate (e, stmt); | |
478 | ||
479 | if (!new_bb) | |
480 | return NULL; | |
481 | ||
482 | add_bb_to_loop (new_bb, loop_c); | |
483 | if (dest->loop_father->latch == src) | |
484 | dest->loop_father->latch = new_bb; | |
485 | ||
486 | return new_bb; | |
487 | } | |
488 | ||
489 | /* Returns the basic block in that statements should be emitted for induction | |
490 | variables incremented at the end of the LOOP. */ | |
491 | ||
492 | basic_block | |
493 | ip_end_pos (struct loop *loop) | |
494 | { | |
495 | return loop->latch; | |
496 | } | |
497 | ||
498 | /* Returns the basic block in that statements should be emitted for induction | |
499 | variables incremented just before exit condition of a LOOP. */ | |
500 | ||
501 | basic_block | |
502 | ip_normal_pos (struct loop *loop) | |
503 | { | |
504 | tree last; | |
505 | basic_block bb; | |
506 | edge exit; | |
507 | ||
c5cbcccf | 508 | if (!single_pred_p (loop->latch)) |
8b11a64c ZD |
509 | return NULL; |
510 | ||
c5cbcccf | 511 | bb = single_pred (loop->latch); |
8b11a64c ZD |
512 | last = last_stmt (bb); |
513 | if (TREE_CODE (last) != COND_EXPR) | |
514 | return NULL; | |
515 | ||
628f6a4e | 516 | exit = EDGE_SUCC (bb, 0); |
8b11a64c | 517 | if (exit->dest == loop->latch) |
628f6a4e | 518 | exit = EDGE_SUCC (bb, 1); |
8b11a64c ZD |
519 | |
520 | if (flow_bb_inside_loop_p (loop, exit->dest)) | |
521 | return NULL; | |
522 | ||
523 | return bb; | |
524 | } | |
525 | ||
526 | /* Stores the standard position for induction variable increment in LOOP | |
527 | (just before the exit condition if it is available and latch block is empty, | |
528 | end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if | |
529 | the increment should be inserted after *BSI. */ | |
530 | ||
531 | void | |
532 | standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, | |
533 | bool *insert_after) | |
534 | { | |
535 | basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); | |
536 | tree last = last_stmt (latch); | |
537 | ||
538 | if (!bb | |
539 | || (last && TREE_CODE (last) != LABEL_EXPR)) | |
540 | { | |
541 | *bsi = bsi_last (latch); | |
542 | *insert_after = true; | |
543 | } | |
544 | else | |
545 | { | |
546 | *bsi = bsi_last (bb); | |
547 | *insert_after = false; | |
548 | } | |
549 | } | |
92fc4a2f ZD |
550 | |
551 | /* Copies phi node arguments for duplicated blocks. The index of the first | |
552 | duplicated block is FIRST_NEW_BLOCK. */ | |
553 | ||
554 | static void | |
555 | copy_phi_node_args (unsigned first_new_block) | |
556 | { | |
557 | unsigned i; | |
558 | ||
559 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
560 | BASIC_BLOCK (i)->rbi->duplicated = 1; | |
561 | ||
562 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
563 | add_phi_args_after_copy_bb (BASIC_BLOCK (i)); | |
564 | ||
565 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
566 | BASIC_BLOCK (i)->rbi->duplicated = 0; | |
567 | } | |
568 | ||
569 | /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge. | |
570 | FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is | |
571 | a bitmap of all ssa names defined inside the loop. */ | |
572 | ||
573 | static void | |
574 | rename_variables (unsigned first_new_block, bitmap definitions) | |
575 | { | |
576 | unsigned i, copy_number = 0; | |
577 | basic_block bb; | |
578 | htab_t ssa_name_map = NULL; | |
579 | ||
580 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
581 | { | |
582 | bb = BASIC_BLOCK (i); | |
583 | ||
584 | /* We assume that first come all blocks from the first copy, then all | |
585 | blocks from the second copy, etc. */ | |
586 | if (copy_number != (unsigned) bb->rbi->copy_number) | |
587 | { | |
588 | allocate_ssa_names (definitions, &ssa_name_map); | |
589 | copy_number = bb->rbi->copy_number; | |
590 | } | |
591 | ||
592 | rewrite_to_new_ssa_names_bb (bb, ssa_name_map); | |
593 | } | |
594 | ||
595 | htab_delete (ssa_name_map); | |
596 | } | |
597 | ||
598 | /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */ | |
599 | ||
600 | static void | |
601 | set_phi_def_stmts (basic_block bb) | |
602 | { | |
603 | tree phi; | |
604 | ||
bb29d951 | 605 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
92fc4a2f ZD |
606 | SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi; |
607 | } | |
608 | ||
1b33f1cc | 609 | /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates |
92fc4a2f ZD |
610 | ssa. In order to achieve this, only loops whose exits all lead to the same |
611 | location are handled. | |
612 | ||
613 | FIXME: we create some degenerate phi nodes that could be avoided by copy | |
614 | propagating them instead. Unfortunately this is not completely | |
615 | straightforward due to problems with constant folding. */ | |
616 | ||
617 | bool | |
618 | tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, | |
619 | struct loops *loops, | |
620 | unsigned int ndupl, sbitmap wont_exit, | |
621 | edge orig, edge *to_remove, | |
622 | unsigned int *n_to_remove, int flags) | |
623 | { | |
624 | unsigned first_new_block; | |
625 | basic_block bb; | |
626 | unsigned i; | |
92fc4a2f ZD |
627 | bitmap definitions; |
628 | ||
629 | if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) | |
630 | return false; | |
631 | if (!(loops->state & LOOPS_HAVE_PREHEADERS)) | |
632 | return false; | |
633 | ||
634 | #ifdef ENABLE_CHECKING | |
635 | verify_loop_closed_ssa (); | |
636 | #endif | |
637 | ||
638 | gcc_assert (!any_marked_for_rewrite_p ()); | |
639 | ||
640 | first_new_block = last_basic_block; | |
641 | if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, | |
642 | orig, to_remove, n_to_remove, flags)) | |
643 | return false; | |
644 | ||
645 | /* Readd the removed phi args for e. */ | |
71882046 | 646 | flush_pending_stmts (e); |
92fc4a2f ZD |
647 | |
648 | /* Copy the phi node arguments. */ | |
649 | copy_phi_node_args (first_new_block); | |
650 | ||
651 | /* Rename the variables. */ | |
652 | definitions = marked_ssa_names (); | |
653 | rename_variables (first_new_block, definitions); | |
654 | unmark_all_for_rewrite (); | |
8bdbfff5 | 655 | BITMAP_FREE (definitions); |
92fc4a2f ZD |
656 | |
657 | /* For some time we have the identical ssa names as results in multiple phi | |
658 | nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result | |
659 | to the new copy. This means that we cannot easily ensure that the ssa | |
660 | names defined in those phis are pointing to the right one -- so just | |
661 | recompute SSA_NAME_DEF_STMT for them. */ | |
662 | ||
663 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
664 | { | |
665 | bb = BASIC_BLOCK (i); | |
666 | set_phi_def_stmts (bb); | |
667 | if (bb->rbi->copy_number == 1) | |
668 | set_phi_def_stmts (bb->rbi->original); | |
669 | } | |
670 | ||
671 | scev_reset (); | |
672 | #ifdef ENABLE_CHECKING | |
673 | verify_loop_closed_ssa (); | |
674 | #endif | |
675 | ||
676 | return true; | |
677 | } | |
678 |