]>
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 ZD |
159 | |
160 | bitmap_clear_bit (livein, def_bb->index); | |
161 | ||
8bdbfff5 | 162 | def = BITMAP_ALLOC (NULL); |
c913f08a ZD |
163 | bitmap_set_bit (def, def_bb->index); |
164 | compute_global_livein (livein, def); | |
8bdbfff5 | 165 | BITMAP_FREE (def); |
c913f08a | 166 | |
87c476a2 ZD |
167 | EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) |
168 | { | |
169 | add_exit_phis_edge (BASIC_BLOCK (index), var); | |
170 | } | |
c913f08a ZD |
171 | } |
172 | ||
173 | /* Add exit phis for the names marked in NAMES_TO_RENAME. | |
174 | Exits of the loops are stored in EXITS. Sets of blocks where the ssa | |
175 | names are used are stored in USE_BLOCKS. */ | |
176 | ||
177 | static void | |
178 | add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) | |
179 | { | |
180 | unsigned i; | |
87c476a2 | 181 | bitmap_iterator bi; |
c913f08a | 182 | |
87c476a2 | 183 | EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) |
c913f08a ZD |
184 | { |
185 | add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); | |
87c476a2 | 186 | } |
c913f08a ZD |
187 | } |
188 | ||
189 | /* Returns a bitmap of all loop exit edge targets. */ | |
190 | ||
191 | static bitmap | |
192 | get_loops_exits (void) | |
193 | { | |
8bdbfff5 | 194 | bitmap exits = BITMAP_ALLOC (NULL); |
c913f08a ZD |
195 | basic_block bb; |
196 | edge e; | |
628f6a4e | 197 | edge_iterator ei; |
c913f08a ZD |
198 | |
199 | FOR_EACH_BB (bb) | |
200 | { | |
628f6a4e | 201 | FOR_EACH_EDGE (e, ei, bb->preds) |
c913f08a ZD |
202 | if (e->src != ENTRY_BLOCK_PTR |
203 | && !flow_bb_inside_loop_p (e->src->loop_father, bb)) | |
204 | { | |
205 | bitmap_set_bit (exits, bb->index); | |
206 | break; | |
207 | } | |
208 | } | |
209 | ||
210 | return exits; | |
211 | } | |
212 | ||
213 | /* For USE in BB, if it is used outside of the loop it is defined in, | |
214 | mark it for rewrite. Record basic block BB where it is used | |
215 | to USE_BLOCKS. */ | |
216 | ||
217 | static void | |
218 | find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) | |
219 | { | |
220 | unsigned ver; | |
221 | basic_block def_bb; | |
222 | struct loop *def_loop; | |
223 | ||
224 | if (TREE_CODE (use) != SSA_NAME) | |
225 | return; | |
226 | ||
227 | ver = SSA_NAME_VERSION (use); | |
228 | def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); | |
229 | if (!def_bb) | |
230 | return; | |
231 | def_loop = def_bb->loop_father; | |
232 | ||
233 | /* If the definition is not inside loop, it is not interesting. */ | |
234 | if (!def_loop->outer) | |
235 | return; | |
236 | ||
237 | if (!use_blocks[ver]) | |
8bdbfff5 | 238 | use_blocks[ver] = BITMAP_ALLOC (NULL); |
c913f08a ZD |
239 | bitmap_set_bit (use_blocks[ver], bb->index); |
240 | ||
241 | if (!flow_bb_inside_loop_p (def_loop, bb)) | |
242 | mark_for_rewrite (use); | |
243 | } | |
244 | ||
245 | /* For uses in STMT, mark names that are used outside of the loop they are | |
246 | defined to rewrite. Record the set of blocks in that the ssa | |
247 | names are defined to USE_BLOCKS. */ | |
248 | ||
249 | static void | |
250 | find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) | |
251 | { | |
4c124b4c AM |
252 | ssa_op_iter iter; |
253 | tree var; | |
c913f08a ZD |
254 | basic_block bb = bb_for_stmt (stmt); |
255 | ||
256 | get_stmt_operands (stmt); | |
c913f08a | 257 | |
52328bf6 | 258 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) |
4c124b4c | 259 | find_uses_to_rename_use (bb, var, use_blocks); |
c913f08a ZD |
260 | } |
261 | ||
2b271002 ZD |
262 | /* Marks names that are used in BB and outside of the loop they are |
263 | defined in for rewrite. Records the set of blocks in that the ssa | |
c913f08a ZD |
264 | names are defined to USE_BLOCKS. */ |
265 | ||
266 | static void | |
2b271002 | 267 | find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks) |
c913f08a | 268 | { |
c913f08a | 269 | block_stmt_iterator bsi; |
2b271002 ZD |
270 | edge e; |
271 | edge_iterator ei; | |
c913f08a | 272 | tree phi; |
c913f08a | 273 | |
2b271002 ZD |
274 | FOR_EACH_EDGE (e, ei, bb->succs) |
275 | for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) | |
276 | find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), | |
277 | use_blocks); | |
278 | ||
279 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
280 | find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks); | |
281 | } | |
282 | ||
283 | /* Marks names that are used outside of the loop they are defined in | |
284 | for rewrite. Records the set of blocks in that the ssa | |
285 | names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, | |
286 | scan only blocks in this set. */ | |
287 | ||
288 | static void | |
289 | find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks) | |
290 | { | |
291 | basic_block bb; | |
292 | unsigned index; | |
293 | bitmap_iterator bi; | |
c913f08a | 294 | |
2b271002 ZD |
295 | if (changed_bbs) |
296 | { | |
297 | EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) | |
298 | { | |
299 | find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks); | |
300 | } | |
301 | } | |
302 | else | |
303 | { | |
304 | FOR_EACH_BB (bb) | |
305 | { | |
306 | find_uses_to_rename_bb (bb, use_blocks); | |
307 | } | |
c913f08a ZD |
308 | } |
309 | } | |
310 | ||
311 | /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra | |
312 | phi nodes to ensure that no variable is used outside the loop it is | |
313 | defined in. | |
314 | ||
315 | This strengthening of the basic ssa form has several advantages: | |
316 | ||
317 | 1) Updating it during unrolling/peeling/versioning is trivial, since | |
318 | we do not need to care about the uses outside of the loop. | |
319 | 2) The behavior of all uses of an induction variable is the same. | |
320 | Without this, you need to distinguish the case when the variable | |
321 | is used outside of the loop it is defined in, for example | |
322 | ||
323 | for (i = 0; i < 100; i++) | |
324 | { | |
325 | for (j = 0; j < 100; j++) | |
326 | { | |
327 | k = i + j; | |
328 | use1 (k); | |
329 | } | |
330 | use2 (k); | |
331 | } | |
332 | ||
333 | Looking from the outer loop with the normal SSA form, the first use of k | |
334 | is not well-behaved, while the second one is an induction variable with | |
2b271002 ZD |
335 | base 99 and step 1. |
336 | ||
337 | If CHANGED_BBS is not NULL, we look for uses outside loops only in | |
338 | the basic blocks in this set. */ | |
c913f08a ZD |
339 | |
340 | void | |
2b271002 | 341 | rewrite_into_loop_closed_ssa (bitmap changed_bbs) |
c913f08a ZD |
342 | { |
343 | bitmap loop_exits = get_loops_exits (); | |
344 | bitmap *use_blocks; | |
345 | unsigned i; | |
346 | bitmap names_to_rename; | |
347 | ||
1e128c5f | 348 | gcc_assert (!any_marked_for_rewrite_p ()); |
c913f08a ZD |
349 | |
350 | use_blocks = xcalloc (num_ssa_names, sizeof (bitmap)); | |
351 | ||
352 | /* Find the uses outside loops. */ | |
2b271002 ZD |
353 | find_uses_to_rename (changed_bbs, use_blocks); |
354 | ||
355 | if (!any_marked_for_rewrite_p ()) | |
356 | { | |
357 | free (use_blocks); | |
358 | BITMAP_FREE (loop_exits); | |
359 | return; | |
360 | } | |
c913f08a ZD |
361 | |
362 | /* Add the phi nodes on exits of the loops for the names we need to | |
363 | rewrite. */ | |
364 | names_to_rename = marked_ssa_names (); | |
365 | add_exit_phis (names_to_rename, use_blocks, loop_exits); | |
366 | ||
367 | for (i = 0; i < num_ssa_names; i++) | |
8bdbfff5 | 368 | BITMAP_FREE (use_blocks[i]); |
c913f08a | 369 | free (use_blocks); |
8bdbfff5 NS |
370 | BITMAP_FREE (loop_exits); |
371 | BITMAP_FREE (names_to_rename); | |
c913f08a ZD |
372 | |
373 | /* Do the rewriting. */ | |
374 | rewrite_ssa_into_ssa (); | |
375 | } | |
376 | ||
377 | /* Check invariants of the loop closed ssa form for the USE in BB. */ | |
378 | ||
379 | static void | |
380 | check_loop_closed_ssa_use (basic_block bb, tree use) | |
381 | { | |
382 | tree def; | |
383 | basic_block def_bb; | |
384 | ||
385 | if (TREE_CODE (use) != SSA_NAME) | |
386 | return; | |
387 | ||
388 | def = SSA_NAME_DEF_STMT (use); | |
389 | def_bb = bb_for_stmt (def); | |
1e128c5f GB |
390 | gcc_assert (!def_bb |
391 | || flow_bb_inside_loop_p (def_bb->loop_father, bb)); | |
c913f08a ZD |
392 | } |
393 | ||
394 | /* Checks invariants of loop closed ssa form in statement STMT in BB. */ | |
395 | ||
396 | static void | |
397 | check_loop_closed_ssa_stmt (basic_block bb, tree stmt) | |
398 | { | |
4c124b4c AM |
399 | ssa_op_iter iter; |
400 | tree var; | |
c913f08a ZD |
401 | |
402 | get_stmt_operands (stmt); | |
c913f08a | 403 | |
4c124b4c AM |
404 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) |
405 | check_loop_closed_ssa_use (bb, var); | |
c913f08a ZD |
406 | } |
407 | ||
408 | /* Checks that invariants of the loop closed ssa form are preserved. */ | |
409 | ||
410 | void | |
411 | verify_loop_closed_ssa (void) | |
412 | { | |
413 | basic_block bb; | |
414 | block_stmt_iterator bsi; | |
415 | tree phi; | |
416 | unsigned i; | |
417 | ||
418 | verify_ssa (); | |
419 | ||
420 | FOR_EACH_BB (bb) | |
421 | { | |
bb29d951 | 422 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
c913f08a ZD |
423 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) |
424 | check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, | |
425 | PHI_ARG_DEF (phi, i)); | |
426 | ||
427 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
428 | check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); | |
429 | } | |
430 | } | |
8b11a64c ZD |
431 | |
432 | /* Split loop exit edge EXIT. The things are a bit complicated by a need to | |
433 | preserve the loop closed ssa form. */ | |
434 | ||
435 | void | |
436 | split_loop_exit_edge (edge exit) | |
437 | { | |
438 | basic_block dest = exit->dest; | |
439 | basic_block bb = loop_split_edge_with (exit, NULL); | |
7fac6722 | 440 | tree phi, new_phi, new_name, name; |
8b11a64c ZD |
441 | use_operand_p op_p; |
442 | ||
bb29d951 | 443 | for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) |
8b11a64c | 444 | { |
c5cbcccf | 445 | op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); |
8b11a64c | 446 | |
7fac6722 ZD |
447 | name = USE_FROM_PTR (op_p); |
448 | ||
449 | /* If the argument of the phi node is a constant, we do not need | |
450 | to keep it inside loop. */ | |
451 | if (TREE_CODE (name) != SSA_NAME) | |
452 | continue; | |
453 | ||
454 | /* Otherwise create an auxiliary phi node that will copy the value | |
455 | of the ssa name out of the loop. */ | |
456 | new_name = duplicate_ssa_name (name, NULL); | |
8b11a64c ZD |
457 | new_phi = create_phi_node (new_name, bb); |
458 | SSA_NAME_DEF_STMT (new_name) = new_phi; | |
d2e398df | 459 | add_phi_arg (new_phi, name, exit); |
8b11a64c ZD |
460 | SET_USE (op_p, new_name); |
461 | } | |
462 | } | |
463 | ||
464 | /* Insert statement STMT to the edge E and update the loop structures. | |
465 | Returns the newly created block (if any). */ | |
466 | ||
467 | basic_block | |
468 | bsi_insert_on_edge_immediate_loop (edge e, tree stmt) | |
469 | { | |
470 | basic_block src, dest, new_bb; | |
471 | struct loop *loop_c; | |
472 | ||
473 | src = e->src; | |
474 | dest = e->dest; | |
475 | ||
476 | loop_c = find_common_loop (src->loop_father, dest->loop_father); | |
477 | ||
478 | new_bb = bsi_insert_on_edge_immediate (e, stmt); | |
479 | ||
480 | if (!new_bb) | |
481 | return NULL; | |
482 | ||
483 | add_bb_to_loop (new_bb, loop_c); | |
484 | if (dest->loop_father->latch == src) | |
485 | dest->loop_father->latch = new_bb; | |
486 | ||
487 | return new_bb; | |
488 | } | |
489 | ||
490 | /* Returns the basic block in that statements should be emitted for induction | |
491 | variables incremented at the end of the LOOP. */ | |
492 | ||
493 | basic_block | |
494 | ip_end_pos (struct loop *loop) | |
495 | { | |
496 | return loop->latch; | |
497 | } | |
498 | ||
499 | /* Returns the basic block in that statements should be emitted for induction | |
500 | variables incremented just before exit condition of a LOOP. */ | |
501 | ||
502 | basic_block | |
503 | ip_normal_pos (struct loop *loop) | |
504 | { | |
505 | tree last; | |
506 | basic_block bb; | |
507 | edge exit; | |
508 | ||
c5cbcccf | 509 | if (!single_pred_p (loop->latch)) |
8b11a64c ZD |
510 | return NULL; |
511 | ||
c5cbcccf | 512 | bb = single_pred (loop->latch); |
8b11a64c ZD |
513 | last = last_stmt (bb); |
514 | if (TREE_CODE (last) != COND_EXPR) | |
515 | return NULL; | |
516 | ||
628f6a4e | 517 | exit = EDGE_SUCC (bb, 0); |
8b11a64c | 518 | if (exit->dest == loop->latch) |
628f6a4e | 519 | exit = EDGE_SUCC (bb, 1); |
8b11a64c ZD |
520 | |
521 | if (flow_bb_inside_loop_p (loop, exit->dest)) | |
522 | return NULL; | |
523 | ||
524 | return bb; | |
525 | } | |
526 | ||
527 | /* Stores the standard position for induction variable increment in LOOP | |
528 | (just before the exit condition if it is available and latch block is empty, | |
529 | end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if | |
530 | the increment should be inserted after *BSI. */ | |
531 | ||
532 | void | |
533 | standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, | |
534 | bool *insert_after) | |
535 | { | |
536 | basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); | |
537 | tree last = last_stmt (latch); | |
538 | ||
539 | if (!bb | |
540 | || (last && TREE_CODE (last) != LABEL_EXPR)) | |
541 | { | |
542 | *bsi = bsi_last (latch); | |
543 | *insert_after = true; | |
544 | } | |
545 | else | |
546 | { | |
547 | *bsi = bsi_last (bb); | |
548 | *insert_after = false; | |
549 | } | |
550 | } | |
92fc4a2f ZD |
551 | |
552 | /* Copies phi node arguments for duplicated blocks. The index of the first | |
553 | duplicated block is FIRST_NEW_BLOCK. */ | |
554 | ||
555 | static void | |
556 | copy_phi_node_args (unsigned first_new_block) | |
557 | { | |
558 | unsigned i; | |
559 | ||
560 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
561 | BASIC_BLOCK (i)->rbi->duplicated = 1; | |
562 | ||
563 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
564 | add_phi_args_after_copy_bb (BASIC_BLOCK (i)); | |
565 | ||
566 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
567 | BASIC_BLOCK (i)->rbi->duplicated = 0; | |
568 | } | |
569 | ||
570 | /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge. | |
571 | FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is | |
572 | a bitmap of all ssa names defined inside the loop. */ | |
573 | ||
574 | static void | |
575 | rename_variables (unsigned first_new_block, bitmap definitions) | |
576 | { | |
577 | unsigned i, copy_number = 0; | |
578 | basic_block bb; | |
579 | htab_t ssa_name_map = NULL; | |
580 | ||
581 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
582 | { | |
583 | bb = BASIC_BLOCK (i); | |
584 | ||
585 | /* We assume that first come all blocks from the first copy, then all | |
586 | blocks from the second copy, etc. */ | |
587 | if (copy_number != (unsigned) bb->rbi->copy_number) | |
588 | { | |
589 | allocate_ssa_names (definitions, &ssa_name_map); | |
590 | copy_number = bb->rbi->copy_number; | |
591 | } | |
592 | ||
593 | rewrite_to_new_ssa_names_bb (bb, ssa_name_map); | |
594 | } | |
595 | ||
596 | htab_delete (ssa_name_map); | |
597 | } | |
598 | ||
599 | /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */ | |
600 | ||
601 | static void | |
602 | set_phi_def_stmts (basic_block bb) | |
603 | { | |
604 | tree phi; | |
605 | ||
bb29d951 | 606 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
92fc4a2f ZD |
607 | SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi; |
608 | } | |
609 | ||
1b33f1cc | 610 | /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates |
92fc4a2f ZD |
611 | ssa. In order to achieve this, only loops whose exits all lead to the same |
612 | location are handled. | |
613 | ||
614 | FIXME: we create some degenerate phi nodes that could be avoided by copy | |
615 | propagating them instead. Unfortunately this is not completely | |
616 | straightforward due to problems with constant folding. */ | |
617 | ||
618 | bool | |
619 | tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, | |
620 | struct loops *loops, | |
621 | unsigned int ndupl, sbitmap wont_exit, | |
622 | edge orig, edge *to_remove, | |
623 | unsigned int *n_to_remove, int flags) | |
624 | { | |
625 | unsigned first_new_block; | |
626 | basic_block bb; | |
627 | unsigned i; | |
92fc4a2f ZD |
628 | bitmap definitions; |
629 | ||
630 | if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) | |
631 | return false; | |
632 | if (!(loops->state & LOOPS_HAVE_PREHEADERS)) | |
633 | return false; | |
634 | ||
635 | #ifdef ENABLE_CHECKING | |
636 | verify_loop_closed_ssa (); | |
637 | #endif | |
638 | ||
639 | gcc_assert (!any_marked_for_rewrite_p ()); | |
640 | ||
641 | first_new_block = last_basic_block; | |
642 | if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, | |
643 | orig, to_remove, n_to_remove, flags)) | |
644 | return false; | |
645 | ||
646 | /* Readd the removed phi args for e. */ | |
71882046 | 647 | flush_pending_stmts (e); |
92fc4a2f ZD |
648 | |
649 | /* Copy the phi node arguments. */ | |
650 | copy_phi_node_args (first_new_block); | |
651 | ||
652 | /* Rename the variables. */ | |
653 | definitions = marked_ssa_names (); | |
654 | rename_variables (first_new_block, definitions); | |
655 | unmark_all_for_rewrite (); | |
8bdbfff5 | 656 | BITMAP_FREE (definitions); |
92fc4a2f ZD |
657 | |
658 | /* For some time we have the identical ssa names as results in multiple phi | |
659 | nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result | |
660 | to the new copy. This means that we cannot easily ensure that the ssa | |
661 | names defined in those phis are pointing to the right one -- so just | |
662 | recompute SSA_NAME_DEF_STMT for them. */ | |
663 | ||
664 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
665 | { | |
666 | bb = BASIC_BLOCK (i); | |
667 | set_phi_def_stmts (bb); | |
668 | if (bb->rbi->copy_number == 1) | |
669 | set_phi_def_stmts (bb->rbi->original); | |
670 | } | |
671 | ||
672 | scev_reset (); | |
673 | #ifdef ENABLE_CHECKING | |
674 | verify_loop_closed_ssa (); | |
675 | #endif | |
676 | ||
677 | return true; | |
678 | } | |
679 | ||
680 | /*--------------------------------------------------------------------------- | |
681 | Loop versioning | |
682 | ---------------------------------------------------------------------------*/ | |
683 | ||
684 | /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy | |
685 | of 'first'. Both of them are dominated by 'new_head' basic block. When | |
686 | 'new_head' was created by 'second's incoming edge it received phi arguments | |
687 | on the edge by split_edge(). Later, additional edge 'e' was created to | |
688 | connect 'new_head' and 'first'. Now this routine adds phi args on this | |
689 | additional edge 'e' that new_head to second edge received as part of edge | |
690 | splitting. | |
691 | */ | |
692 | ||
693 | static void | |
694 | lv_adjust_loop_header_phi (basic_block first, basic_block second, | |
695 | basic_block new_head, edge e) | |
696 | { | |
697 | tree phi1, phi2; | |
698 | ||
699 | /* Browse all 'second' basic block phi nodes and add phi args to | |
700 | edge 'e' for 'first' head. PHI args are always in correct order. */ | |
701 | ||
702 | for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); | |
703 | phi2 && phi1; | |
eaf0dc02 | 704 | phi2 = PHI_CHAIN (phi2), phi1 = PHI_CHAIN (phi1)) |
92fc4a2f | 705 | { |
ac57c407 KH |
706 | edge e2 = find_edge (new_head, second); |
707 | ||
708 | if (e2) | |
92fc4a2f | 709 | { |
ac57c407 | 710 | tree def = PHI_ARG_DEF (phi2, e2->dest_idx); |
d2e398df | 711 | add_phi_arg (phi1, def, e); |
92fc4a2f ZD |
712 | } |
713 | } | |
714 | } | |
715 | ||
716 | /* Adjust entry edge for lv. | |
717 | ||
1f838355 | 718 | e is an incoming edge. |
92fc4a2f ZD |
719 | |
720 | --- edge e ---- > [second_head] | |
721 | ||
722 | Split it and insert new conditional expression and adjust edges. | |
723 | ||
724 | --- edge e ---> [cond expr] ---> [first_head] | |
725 | | | |
726 | +---------> [second_head] | |
727 | ||
728 | */ | |
729 | ||
730 | static basic_block | |
731 | lv_adjust_loop_entry_edge (basic_block first_head, | |
732 | basic_block second_head, | |
733 | edge e, | |
734 | tree cond_expr) | |
735 | { | |
736 | block_stmt_iterator bsi; | |
737 | basic_block new_head = NULL; | |
738 | tree goto1 = NULL_TREE; | |
739 | tree goto2 = NULL_TREE; | |
740 | tree new_cond_expr = NULL_TREE; | |
741 | edge e0, e1; | |
742 | ||
743 | gcc_assert (e->dest == second_head); | |
744 | ||
745 | /* Split edge 'e'. This will create a new basic block, where we can | |
746 | insert conditional expr. */ | |
747 | new_head = split_edge (e); | |
748 | ||
749 | /* Build new conditional expr */ | |
750 | goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head)); | |
751 | goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head)); | |
752 | new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2); | |
753 | ||
754 | /* Add new cond. in new head. */ | |
755 | bsi = bsi_start (new_head); | |
756 | bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT); | |
757 | ||
758 | /* Adjust edges appropriately to connect new head with first head | |
759 | as well as second head. */ | |
c5cbcccf | 760 | e0 = single_succ_edge (new_head); |
92fc4a2f ZD |
761 | e0->flags &= ~EDGE_FALLTHRU; |
762 | e0->flags |= EDGE_FALSE_VALUE; | |
763 | e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE); | |
764 | set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); | |
765 | set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); | |
766 | ||
767 | /* Adjust loop header phi nodes. */ | |
768 | lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); | |
769 | ||
770 | return new_head; | |
771 | } | |
772 | ||
92fc4a2f ZD |
773 | /* Main entry point for Loop Versioning transformation. |
774 | ||
775 | This transformation given a condition and a loop, creates | |
776 | -if (condition) { loop_copy1 } else { loop_copy2 }, | |
777 | where loop_copy1 is the loop transformed in one way, and loop_copy2 | |
778 | is the loop transformed in another way (or unchanged). 'condition' | |
779 | may be a run time test for things that were not resolved by static | |
780 | analysis (overlapping ranges (anti-aliasing), alignment, etc.). */ | |
781 | ||
782 | struct loop * | |
783 | tree_ssa_loop_version (struct loops *loops, struct loop * loop, | |
784 | tree cond_expr, basic_block *condition_bb) | |
785 | { | |
5132abc2 | 786 | edge entry, latch_edge, exit, true_edge, false_edge; |
92fc4a2f ZD |
787 | basic_block first_head, second_head; |
788 | int irred_flag; | |
789 | struct loop *nloop; | |
790 | ||
791 | /* CHECKME: Loop versioning does not handle nested loop at this point. */ | |
792 | if (loop->inner) | |
793 | return NULL; | |
794 | ||
795 | /* Record entry and latch edges for the loop */ | |
796 | entry = loop_preheader_edge (loop); | |
797 | ||
798 | /* Note down head of loop as first_head. */ | |
799 | first_head = entry->dest; | |
800 | ||
801 | /* Duplicate loop. */ | |
802 | irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; | |
803 | entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; | |
804 | if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1, | |
805 | NULL, NULL, NULL, NULL, 0)) | |
806 | { | |
807 | entry->flags |= irred_flag; | |
808 | return NULL; | |
809 | } | |
810 | ||
811 | /* After duplication entry edge now points to new loop head block. | |
812 | Note down new head as second_head. */ | |
813 | second_head = entry->dest; | |
814 | ||
815 | /* Split loop entry edge and insert new block with cond expr. */ | |
816 | *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, | |
817 | cond_expr); | |
818 | ||
c5cbcccf | 819 | latch_edge = single_succ_edge (loop->latch->rbi->copy); |
5132abc2 KH |
820 | |
821 | extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge); | |
92fc4a2f ZD |
822 | nloop = loopify (loops, |
823 | latch_edge, | |
c5cbcccf | 824 | single_pred_edge (loop->header->rbi->copy), |
5132abc2 | 825 | *condition_bb, true_edge, false_edge, |
92fc4a2f ZD |
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. */ | |
71882046 | 833 | flush_pending_stmts (latch_edge); |
92fc4a2f ZD |
834 | |
835 | /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ | |
5132abc2 | 836 | extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge); |
71882046 | 837 | flush_pending_stmts (false_edge); |
92fc4a2f ZD |
838 | |
839 | /* Adjust irreducible flag. */ | |
840 | if (irred_flag) | |
841 | { | |
842 | (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP; | |
843 | loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; | |
844 | loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; | |
c5cbcccf | 845 | single_pred_edge ((*condition_bb))->flags |= EDGE_IRREDUCIBLE_LOOP; |
92fc4a2f ZD |
846 | } |
847 | ||
848 | /* At this point condition_bb is loop predheader with two successors, | |
849 | first_head and second_head. Make sure that loop predheader has only | |
471854f8 | 850 | one successor. */ |
92fc4a2f ZD |
851 | loop_split_edge_with (loop_preheader_edge (loop), NULL); |
852 | loop_split_edge_with (loop_preheader_edge (nloop), NULL); | |
853 | ||
854 | return nloop; | |
855 | } |