]>
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); | |
84d65814 | 142 | create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi)); |
628f6a4e | 143 | FOR_EACH_EDGE (e, ei, exit->preds) |
d2e398df | 144 | add_phi_arg (phi, use, e); |
c913f08a ZD |
145 | } |
146 | ||
147 | /* Add exit phis for VAR that is used in LIVEIN. | |
148 | Exits of the loops are stored in EXITS. */ | |
149 | ||
150 | static void | |
151 | add_exit_phis_var (tree var, bitmap livein, bitmap exits) | |
152 | { | |
153 | bitmap def; | |
3cd8c58a | 154 | unsigned index; |
c913f08a | 155 | basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); |
87c476a2 | 156 | bitmap_iterator bi; |
c913f08a | 157 | |
0bca51f0 DN |
158 | if (is_gimple_reg (var)) |
159 | bitmap_clear_bit (livein, def_bb->index); | |
160 | else | |
161 | bitmap_set_bit (livein, def_bb->index); | |
c913f08a | 162 | |
8bdbfff5 | 163 | def = BITMAP_ALLOC (NULL); |
c913f08a ZD |
164 | bitmap_set_bit (def, def_bb->index); |
165 | compute_global_livein (livein, def); | |
8bdbfff5 | 166 | BITMAP_FREE (def); |
c913f08a | 167 | |
87c476a2 ZD |
168 | EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) |
169 | { | |
170 | add_exit_phis_edge (BASIC_BLOCK (index), var); | |
171 | } | |
c913f08a ZD |
172 | } |
173 | ||
174 | /* Add exit phis for the names marked in NAMES_TO_RENAME. | |
175 | Exits of the loops are stored in EXITS. Sets of blocks where the ssa | |
176 | names are used are stored in USE_BLOCKS. */ | |
177 | ||
178 | static void | |
179 | add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) | |
180 | { | |
181 | unsigned i; | |
87c476a2 | 182 | bitmap_iterator bi; |
c913f08a | 183 | |
87c476a2 | 184 | EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) |
c913f08a ZD |
185 | { |
186 | add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); | |
87c476a2 | 187 | } |
c913f08a ZD |
188 | } |
189 | ||
190 | /* Returns a bitmap of all loop exit edge targets. */ | |
191 | ||
192 | static bitmap | |
193 | get_loops_exits (void) | |
194 | { | |
8bdbfff5 | 195 | bitmap exits = BITMAP_ALLOC (NULL); |
c913f08a ZD |
196 | basic_block bb; |
197 | edge e; | |
628f6a4e | 198 | edge_iterator ei; |
c913f08a ZD |
199 | |
200 | FOR_EACH_BB (bb) | |
201 | { | |
628f6a4e | 202 | FOR_EACH_EDGE (e, ei, bb->preds) |
c913f08a ZD |
203 | if (e->src != ENTRY_BLOCK_PTR |
204 | && !flow_bb_inside_loop_p (e->src->loop_father, bb)) | |
205 | { | |
206 | bitmap_set_bit (exits, bb->index); | |
207 | break; | |
208 | } | |
209 | } | |
210 | ||
211 | return exits; | |
212 | } | |
213 | ||
214 | /* For USE in BB, if it is used outside of the loop it is defined in, | |
215 | mark it for rewrite. Record basic block BB where it is used | |
84d65814 | 216 | to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ |
c913f08a ZD |
217 | |
218 | static void | |
84d65814 DN |
219 | find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, |
220 | bitmap need_phis) | |
c913f08a ZD |
221 | { |
222 | unsigned ver; | |
223 | basic_block def_bb; | |
224 | struct loop *def_loop; | |
225 | ||
226 | if (TREE_CODE (use) != SSA_NAME) | |
227 | return; | |
228 | ||
84d65814 DN |
229 | /* We don't need to keep virtual operands in loop-closed form. */ |
230 | if (!is_gimple_reg (use)) | |
231 | return; | |
232 | ||
c913f08a ZD |
233 | ver = SSA_NAME_VERSION (use); |
234 | def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); | |
235 | if (!def_bb) | |
236 | return; | |
237 | def_loop = def_bb->loop_father; | |
238 | ||
239 | /* If the definition is not inside loop, it is not interesting. */ | |
240 | if (!def_loop->outer) | |
241 | return; | |
242 | ||
243 | if (!use_blocks[ver]) | |
8bdbfff5 | 244 | use_blocks[ver] = BITMAP_ALLOC (NULL); |
c913f08a ZD |
245 | bitmap_set_bit (use_blocks[ver], bb->index); |
246 | ||
84d65814 | 247 | bitmap_set_bit (need_phis, ver); |
c913f08a ZD |
248 | } |
249 | ||
250 | /* For uses in STMT, mark names that are used outside of the loop they are | |
251 | defined to rewrite. Record the set of blocks in that the ssa | |
84d65814 DN |
252 | names are defined to USE_BLOCKS and the ssa names themselves to |
253 | NEED_PHIS. */ | |
c913f08a ZD |
254 | |
255 | static void | |
84d65814 | 256 | find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis) |
c913f08a | 257 | { |
4c124b4c AM |
258 | ssa_op_iter iter; |
259 | tree var; | |
c913f08a ZD |
260 | basic_block bb = bb_for_stmt (stmt); |
261 | ||
52328bf6 | 262 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) |
84d65814 | 263 | find_uses_to_rename_use (bb, var, use_blocks, need_phis); |
c913f08a ZD |
264 | } |
265 | ||
2b271002 ZD |
266 | /* Marks names that are used in BB and outside of the loop they are |
267 | defined in for rewrite. Records the set of blocks in that the ssa | |
84d65814 DN |
268 | names are defined to USE_BLOCKS. Record the SSA names that will |
269 | need exit PHIs in NEED_PHIS. */ | |
c913f08a ZD |
270 | |
271 | static void | |
84d65814 | 272 | find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) |
c913f08a | 273 | { |
c913f08a | 274 | block_stmt_iterator bsi; |
2b271002 ZD |
275 | edge e; |
276 | edge_iterator ei; | |
c913f08a | 277 | tree phi; |
c913f08a | 278 | |
2b271002 ZD |
279 | FOR_EACH_EDGE (e, ei, bb->succs) |
280 | for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) | |
281 | find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), | |
84d65814 | 282 | use_blocks, need_phis); |
2b271002 ZD |
283 | |
284 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
84d65814 | 285 | find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis); |
2b271002 ZD |
286 | } |
287 | ||
288 | /* Marks names that are used outside of the loop they are defined in | |
289 | for rewrite. Records the set of blocks in that the ssa | |
290 | names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, | |
291 | scan only blocks in this set. */ | |
292 | ||
293 | static void | |
84d65814 | 294 | find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) |
2b271002 ZD |
295 | { |
296 | basic_block bb; | |
297 | unsigned index; | |
298 | bitmap_iterator bi; | |
c913f08a | 299 | |
84d65814 | 300 | if (changed_bbs && !bitmap_empty_p (changed_bbs)) |
2b271002 ZD |
301 | { |
302 | EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) | |
303 | { | |
84d65814 | 304 | find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis); |
2b271002 ZD |
305 | } |
306 | } | |
307 | else | |
308 | { | |
309 | FOR_EACH_BB (bb) | |
310 | { | |
84d65814 | 311 | find_uses_to_rename_bb (bb, use_blocks, need_phis); |
2b271002 | 312 | } |
c913f08a ZD |
313 | } |
314 | } | |
315 | ||
316 | /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra | |
317 | phi nodes to ensure that no variable is used outside the loop it is | |
318 | defined in. | |
319 | ||
320 | This strengthening of the basic ssa form has several advantages: | |
321 | ||
322 | 1) Updating it during unrolling/peeling/versioning is trivial, since | |
323 | we do not need to care about the uses outside of the loop. | |
324 | 2) The behavior of all uses of an induction variable is the same. | |
325 | Without this, you need to distinguish the case when the variable | |
326 | is used outside of the loop it is defined in, for example | |
327 | ||
328 | for (i = 0; i < 100; i++) | |
329 | { | |
330 | for (j = 0; j < 100; j++) | |
331 | { | |
332 | k = i + j; | |
333 | use1 (k); | |
334 | } | |
335 | use2 (k); | |
336 | } | |
337 | ||
338 | Looking from the outer loop with the normal SSA form, the first use of k | |
339 | is not well-behaved, while the second one is an induction variable with | |
2b271002 ZD |
340 | base 99 and step 1. |
341 | ||
342 | If CHANGED_BBS is not NULL, we look for uses outside loops only in | |
84d65814 DN |
343 | the basic blocks in this set. |
344 | ||
345 | UPDATE_FLAG is used in the call to update_ssa. See | |
346 | TODO_update_ssa* for documentation. */ | |
c913f08a ZD |
347 | |
348 | void | |
84d65814 | 349 | rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) |
c913f08a ZD |
350 | { |
351 | bitmap loop_exits = get_loops_exits (); | |
352 | bitmap *use_blocks; | |
84d65814 DN |
353 | unsigned i, old_num_ssa_names; |
354 | bitmap names_to_rename = BITMAP_ALLOC (NULL); | |
c913f08a | 355 | |
84d65814 DN |
356 | /* If the pass has caused the SSA form to be out-of-date, update it |
357 | now. */ | |
358 | update_ssa (update_flag); | |
c913f08a | 359 | |
84d65814 DN |
360 | old_num_ssa_names = num_ssa_names; |
361 | use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap)); | |
c913f08a ZD |
362 | |
363 | /* Find the uses outside loops. */ | |
84d65814 | 364 | find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); |
2b271002 | 365 | |
84d65814 | 366 | /* Add the PHI nodes on exits of the loops for the names we need to |
c913f08a | 367 | rewrite. */ |
c913f08a ZD |
368 | add_exit_phis (names_to_rename, use_blocks, loop_exits); |
369 | ||
84d65814 | 370 | for (i = 0; i < old_num_ssa_names; i++) |
8bdbfff5 | 371 | BITMAP_FREE (use_blocks[i]); |
c913f08a | 372 | free (use_blocks); |
8bdbfff5 NS |
373 | BITMAP_FREE (loop_exits); |
374 | BITMAP_FREE (names_to_rename); | |
c913f08a | 375 | |
84d65814 DN |
376 | /* Fix up all the names found to be used outside their original |
377 | loops. */ | |
378 | update_ssa (TODO_update_ssa); | |
c913f08a ZD |
379 | } |
380 | ||
381 | /* Check invariants of the loop closed ssa form for the USE in BB. */ | |
382 | ||
383 | static void | |
384 | check_loop_closed_ssa_use (basic_block bb, tree use) | |
385 | { | |
386 | tree def; | |
387 | basic_block def_bb; | |
388 | ||
84d65814 | 389 | if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) |
c913f08a ZD |
390 | return; |
391 | ||
392 | def = SSA_NAME_DEF_STMT (use); | |
393 | def_bb = bb_for_stmt (def); | |
1e128c5f GB |
394 | gcc_assert (!def_bb |
395 | || flow_bb_inside_loop_p (def_bb->loop_father, bb)); | |
c913f08a ZD |
396 | } |
397 | ||
398 | /* Checks invariants of loop closed ssa form in statement STMT in BB. */ | |
399 | ||
400 | static void | |
401 | check_loop_closed_ssa_stmt (basic_block bb, tree stmt) | |
402 | { | |
4c124b4c AM |
403 | ssa_op_iter iter; |
404 | tree var; | |
c913f08a | 405 | |
84d65814 | 406 | FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) |
4c124b4c | 407 | check_loop_closed_ssa_use (bb, var); |
c913f08a ZD |
408 | } |
409 | ||
410 | /* Checks that invariants of the loop closed ssa form are preserved. */ | |
411 | ||
412 | void | |
413 | verify_loop_closed_ssa (void) | |
414 | { | |
415 | basic_block bb; | |
416 | block_stmt_iterator bsi; | |
417 | tree phi; | |
418 | unsigned i; | |
419 | ||
84d65814 DN |
420 | if (current_loops == NULL) |
421 | return; | |
422 | ||
f430bae8 | 423 | verify_ssa (false); |
c913f08a ZD |
424 | |
425 | FOR_EACH_BB (bb) | |
426 | { | |
bb29d951 | 427 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
c913f08a ZD |
428 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) |
429 | check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, | |
430 | PHI_ARG_DEF (phi, i)); | |
431 | ||
432 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
433 | check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); | |
434 | } | |
435 | } | |
8b11a64c ZD |
436 | |
437 | /* Split loop exit edge EXIT. The things are a bit complicated by a need to | |
438 | preserve the loop closed ssa form. */ | |
439 | ||
440 | void | |
441 | split_loop_exit_edge (edge exit) | |
442 | { | |
443 | basic_block dest = exit->dest; | |
444 | basic_block bb = loop_split_edge_with (exit, NULL); | |
7fac6722 | 445 | tree phi, new_phi, new_name, name; |
8b11a64c ZD |
446 | use_operand_p op_p; |
447 | ||
bb29d951 | 448 | for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) |
8b11a64c | 449 | { |
c5cbcccf | 450 | op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); |
8b11a64c | 451 | |
7fac6722 ZD |
452 | name = USE_FROM_PTR (op_p); |
453 | ||
454 | /* If the argument of the phi node is a constant, we do not need | |
455 | to keep it inside loop. */ | |
456 | if (TREE_CODE (name) != SSA_NAME) | |
457 | continue; | |
458 | ||
459 | /* Otherwise create an auxiliary phi node that will copy the value | |
460 | of the ssa name out of the loop. */ | |
461 | new_name = duplicate_ssa_name (name, NULL); | |
8b11a64c ZD |
462 | new_phi = create_phi_node (new_name, bb); |
463 | SSA_NAME_DEF_STMT (new_name) = new_phi; | |
d2e398df | 464 | add_phi_arg (new_phi, name, exit); |
8b11a64c ZD |
465 | SET_USE (op_p, new_name); |
466 | } | |
467 | } | |
468 | ||
469 | /* Insert statement STMT to the edge E and update the loop structures. | |
470 | Returns the newly created block (if any). */ | |
471 | ||
472 | basic_block | |
473 | bsi_insert_on_edge_immediate_loop (edge e, tree stmt) | |
474 | { | |
475 | basic_block src, dest, new_bb; | |
476 | struct loop *loop_c; | |
477 | ||
478 | src = e->src; | |
479 | dest = e->dest; | |
480 | ||
481 | loop_c = find_common_loop (src->loop_father, dest->loop_father); | |
482 | ||
483 | new_bb = bsi_insert_on_edge_immediate (e, stmt); | |
484 | ||
485 | if (!new_bb) | |
486 | return NULL; | |
487 | ||
488 | add_bb_to_loop (new_bb, loop_c); | |
489 | if (dest->loop_father->latch == src) | |
490 | dest->loop_father->latch = new_bb; | |
491 | ||
492 | return new_bb; | |
493 | } | |
494 | ||
495 | /* Returns the basic block in that statements should be emitted for induction | |
496 | variables incremented at the end of the LOOP. */ | |
497 | ||
498 | basic_block | |
499 | ip_end_pos (struct loop *loop) | |
500 | { | |
501 | return loop->latch; | |
502 | } | |
503 | ||
504 | /* Returns the basic block in that statements should be emitted for induction | |
505 | variables incremented just before exit condition of a LOOP. */ | |
506 | ||
507 | basic_block | |
508 | ip_normal_pos (struct loop *loop) | |
509 | { | |
510 | tree last; | |
511 | basic_block bb; | |
512 | edge exit; | |
513 | ||
c5cbcccf | 514 | if (!single_pred_p (loop->latch)) |
8b11a64c ZD |
515 | return NULL; |
516 | ||
c5cbcccf | 517 | bb = single_pred (loop->latch); |
8b11a64c ZD |
518 | last = last_stmt (bb); |
519 | if (TREE_CODE (last) != COND_EXPR) | |
520 | return NULL; | |
521 | ||
628f6a4e | 522 | exit = EDGE_SUCC (bb, 0); |
8b11a64c | 523 | if (exit->dest == loop->latch) |
628f6a4e | 524 | exit = EDGE_SUCC (bb, 1); |
8b11a64c ZD |
525 | |
526 | if (flow_bb_inside_loop_p (loop, exit->dest)) | |
527 | return NULL; | |
528 | ||
529 | return bb; | |
530 | } | |
531 | ||
532 | /* Stores the standard position for induction variable increment in LOOP | |
533 | (just before the exit condition if it is available and latch block is empty, | |
534 | end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if | |
535 | the increment should be inserted after *BSI. */ | |
536 | ||
537 | void | |
538 | standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, | |
539 | bool *insert_after) | |
540 | { | |
541 | basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); | |
542 | tree last = last_stmt (latch); | |
543 | ||
544 | if (!bb | |
545 | || (last && TREE_CODE (last) != LABEL_EXPR)) | |
546 | { | |
547 | *bsi = bsi_last (latch); | |
548 | *insert_after = true; | |
549 | } | |
550 | else | |
551 | { | |
552 | *bsi = bsi_last (bb); | |
553 | *insert_after = false; | |
554 | } | |
555 | } | |
92fc4a2f ZD |
556 | |
557 | /* Copies phi node arguments for duplicated blocks. The index of the first | |
558 | duplicated block is FIRST_NEW_BLOCK. */ | |
559 | ||
560 | static void | |
561 | copy_phi_node_args (unsigned first_new_block) | |
562 | { | |
563 | unsigned i; | |
564 | ||
565 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
566 | BASIC_BLOCK (i)->rbi->duplicated = 1; | |
567 | ||
568 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
569 | add_phi_args_after_copy_bb (BASIC_BLOCK (i)); | |
570 | ||
571 | for (i = first_new_block; i < (unsigned) last_basic_block; i++) | |
572 | BASIC_BLOCK (i)->rbi->duplicated = 0; | |
573 | } | |
574 | ||
92fc4a2f | 575 | |
84d65814 DN |
576 | /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also |
577 | updates the PHI nodes at start of the copied region. In order to | |
578 | achieve this, only loops whose exits all lead to the same location | |
579 | are handled. | |
92fc4a2f | 580 | |
84d65814 DN |
581 | Notice that we do not completely update the SSA web after |
582 | duplication. The caller is responsible for calling update_ssa | |
583 | after the loop has been duplicated. */ | |
92fc4a2f ZD |
584 | |
585 | bool | |
586 | tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, | |
587 | struct loops *loops, | |
588 | unsigned int ndupl, sbitmap wont_exit, | |
589 | edge orig, edge *to_remove, | |
590 | unsigned int *n_to_remove, int flags) | |
591 | { | |
592 | unsigned first_new_block; | |
92fc4a2f ZD |
593 | |
594 | if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) | |
595 | return false; | |
596 | if (!(loops->state & LOOPS_HAVE_PREHEADERS)) | |
597 | return false; | |
598 | ||
599 | #ifdef ENABLE_CHECKING | |
600 | verify_loop_closed_ssa (); | |
601 | #endif | |
602 | ||
92fc4a2f ZD |
603 | first_new_block = last_basic_block; |
604 | if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, | |
605 | orig, to_remove, n_to_remove, flags)) | |
606 | return false; | |
607 | ||
608 | /* Readd the removed phi args for e. */ | |
71882046 | 609 | flush_pending_stmts (e); |
92fc4a2f ZD |
610 | |
611 | /* Copy the phi node arguments. */ | |
612 | copy_phi_node_args (first_new_block); | |
613 | ||
92fc4a2f | 614 | scev_reset (); |
92fc4a2f ZD |
615 | |
616 | return true; | |
617 | } |