]>
Commit | Line | Data |
---|---|---|
28df8730 MM |
1 | /* Loop splitting. |
2 | Copyright (C) 2015 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 3, 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 COPYING3. If not see | |
18 | <http://www.gnu.org/licenses/>. */ | |
19 | ||
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "backend.h" | |
24 | #include "tree.h" | |
25 | #include "gimple.h" | |
26 | #include "tree-pass.h" | |
27 | #include "ssa.h" | |
28 | #include "fold-const.h" | |
29 | #include "tree-cfg.h" | |
30 | #include "tree-ssa.h" | |
31 | #include "tree-ssa-loop-niter.h" | |
32 | #include "tree-ssa-loop.h" | |
33 | #include "tree-ssa-loop-manip.h" | |
34 | #include "tree-into-ssa.h" | |
35 | #include "cfgloop.h" | |
36 | #include "tree-scalar-evolution.h" | |
37 | #include "gimple-iterator.h" | |
38 | #include "gimple-pretty-print.h" | |
39 | #include "cfghooks.h" | |
40 | #include "gimple-fold.h" | |
41 | #include "gimplify-me.h" | |
42 | ||
43 | /* This file implements loop splitting, i.e. transformation of loops like | |
44 | ||
45 | for (i = 0; i < 100; i++) | |
46 | { | |
47 | if (i < 50) | |
48 | A; | |
49 | else | |
50 | B; | |
51 | } | |
52 | ||
53 | into: | |
54 | ||
55 | for (i = 0; i < 50; i++) | |
56 | { | |
57 | A; | |
58 | } | |
59 | for (; i < 100; i++) | |
60 | { | |
61 | B; | |
62 | } | |
63 | ||
64 | */ | |
65 | ||
66 | /* Return true when BB inside LOOP is a potential iteration space | |
67 | split point, i.e. ends with a condition like "IV < comp", which | |
68 | is true on one side of the iteration space and false on the other, | |
69 | and the split point can be computed. If so, also return the border | |
70 | point in *BORDER and the comparison induction variable in IV. */ | |
71 | ||
72 | static tree | |
73 | split_at_bb_p (struct loop *loop, basic_block bb, tree *border, affine_iv *iv) | |
74 | { | |
75 | gimple *last; | |
76 | gcond *stmt; | |
77 | affine_iv iv2; | |
78 | ||
79 | /* BB must end in a simple conditional jump. */ | |
80 | last = last_stmt (bb); | |
81 | if (!last || gimple_code (last) != GIMPLE_COND) | |
82 | return NULL_TREE; | |
83 | stmt = as_a <gcond *> (last); | |
84 | ||
85 | enum tree_code code = gimple_cond_code (stmt); | |
86 | ||
87 | /* Only handle relational comparisons, for equality and non-equality | |
88 | we'd have to split the loop into two loops and a middle statement. */ | |
89 | switch (code) | |
90 | { | |
91 | case LT_EXPR: | |
92 | case LE_EXPR: | |
93 | case GT_EXPR: | |
94 | case GE_EXPR: | |
95 | break; | |
96 | default: | |
97 | return NULL_TREE; | |
98 | } | |
99 | ||
100 | if (loop_exits_from_bb_p (loop, bb)) | |
101 | return NULL_TREE; | |
102 | ||
103 | tree op0 = gimple_cond_lhs (stmt); | |
104 | tree op1 = gimple_cond_rhs (stmt); | |
105 | ||
106 | if (!simple_iv (loop, loop, op0, iv, false)) | |
107 | return NULL_TREE; | |
108 | if (!simple_iv (loop, loop, op1, &iv2, false)) | |
109 | return NULL_TREE; | |
110 | ||
111 | /* Make it so that the first argument of the condition is | |
112 | the looping one. */ | |
113 | if (!integer_zerop (iv2.step)) | |
114 | { | |
115 | std::swap (op0, op1); | |
116 | std::swap (*iv, iv2); | |
117 | code = swap_tree_comparison (code); | |
118 | gimple_cond_set_condition (stmt, code, op0, op1); | |
119 | update_stmt (stmt); | |
120 | } | |
121 | else if (integer_zerop (iv->step)) | |
122 | return NULL_TREE; | |
123 | if (!integer_zerop (iv2.step)) | |
124 | return NULL_TREE; | |
125 | ||
126 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
127 | { | |
128 | fprintf (dump_file, "Found potential split point: "); | |
129 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
130 | fprintf (dump_file, " { "); | |
131 | print_generic_expr (dump_file, iv->base, TDF_SLIM); | |
132 | fprintf (dump_file, " + I*"); | |
133 | print_generic_expr (dump_file, iv->step, TDF_SLIM); | |
134 | fprintf (dump_file, " } %s ", get_tree_code_name (code)); | |
135 | print_generic_expr (dump_file, iv2.base, TDF_SLIM); | |
136 | fprintf (dump_file, "\n"); | |
137 | } | |
138 | ||
139 | *border = iv2.base; | |
140 | return op0; | |
141 | } | |
142 | ||
143 | /* Given a GUARD conditional stmt inside LOOP, which we want to make always | |
144 | true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL | |
145 | (a post-increment IV) and NEWBOUND (the comparator) adjust the loop | |
146 | exit test statement to loop back only if the GUARD statement will | |
147 | also be true/false in the next iteration. */ | |
148 | ||
149 | static void | |
150 | patch_loop_exit (struct loop *loop, gcond *guard, tree nextval, tree newbound, | |
151 | bool initial_true) | |
152 | { | |
153 | edge exit = single_exit (loop); | |
154 | gcond *stmt = as_a <gcond *> (last_stmt (exit->src)); | |
155 | gimple_cond_set_condition (stmt, gimple_cond_code (guard), | |
156 | nextval, newbound); | |
157 | update_stmt (stmt); | |
158 | ||
159 | edge stay = single_pred_edge (loop->latch); | |
160 | ||
161 | exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
162 | stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
163 | ||
164 | if (initial_true) | |
165 | { | |
166 | exit->flags |= EDGE_FALSE_VALUE; | |
167 | stay->flags |= EDGE_TRUE_VALUE; | |
168 | } | |
169 | else | |
170 | { | |
171 | exit->flags |= EDGE_TRUE_VALUE; | |
172 | stay->flags |= EDGE_FALSE_VALUE; | |
173 | } | |
174 | } | |
175 | ||
176 | /* Give an induction variable GUARD_IV, and its affine descriptor IV, | |
177 | find the loop phi node in LOOP defining it directly, or create | |
178 | such phi node. Return that phi node. */ | |
179 | ||
180 | static gphi * | |
181 | find_or_create_guard_phi (struct loop *loop, tree guard_iv, affine_iv * /*iv*/) | |
182 | { | |
183 | gimple *def = SSA_NAME_DEF_STMT (guard_iv); | |
184 | gphi *phi; | |
185 | if ((phi = dyn_cast <gphi *> (def)) | |
186 | && gimple_bb (phi) == loop->header) | |
187 | return phi; | |
188 | ||
189 | /* XXX Create the PHI instead. */ | |
190 | return NULL; | |
191 | } | |
192 | ||
193 | /* This function updates the SSA form after connect_loops made a new | |
194 | edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate | |
195 | conditional). I.e. the second loop can now be entered either | |
196 | via the original entry or via NEW_E, so the entry values of LOOP2 | |
197 | phi nodes are either the original ones or those at the exit | |
198 | of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting | |
199 | this. */ | |
200 | ||
201 | static void | |
202 | connect_loop_phis (struct loop *loop1, struct loop *loop2, edge new_e) | |
203 | { | |
204 | basic_block rest = loop_preheader_edge (loop2)->src; | |
205 | gcc_assert (new_e->dest == rest); | |
206 | edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e); | |
207 | ||
208 | edge firste = loop_preheader_edge (loop1); | |
209 | edge seconde = loop_preheader_edge (loop2); | |
210 | edge firstn = loop_latch_edge (loop1); | |
211 | gphi_iterator psi_first, psi_second; | |
212 | for (psi_first = gsi_start_phis (loop1->header), | |
213 | psi_second = gsi_start_phis (loop2->header); | |
214 | !gsi_end_p (psi_first); | |
215 | gsi_next (&psi_first), gsi_next (&psi_second)) | |
216 | { | |
217 | tree init, next, new_init; | |
218 | use_operand_p op; | |
219 | gphi *phi_first = psi_first.phi (); | |
220 | gphi *phi_second = psi_second.phi (); | |
221 | ||
222 | init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste); | |
223 | next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn); | |
224 | op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde); | |
225 | gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); | |
226 | ||
227 | /* Prefer using original variable as a base for the new ssa name. | |
228 | This is necessary for virtual ops, and useful in order to avoid | |
229 | losing debug info for real ops. */ | |
230 | if (TREE_CODE (next) == SSA_NAME | |
231 | && useless_type_conversion_p (TREE_TYPE (next), | |
232 | TREE_TYPE (init))) | |
233 | new_init = copy_ssa_name (next); | |
234 | else if (TREE_CODE (init) == SSA_NAME | |
235 | && useless_type_conversion_p (TREE_TYPE (init), | |
236 | TREE_TYPE (next))) | |
237 | new_init = copy_ssa_name (init); | |
238 | else if (useless_type_conversion_p (TREE_TYPE (next), | |
239 | TREE_TYPE (init))) | |
240 | new_init = make_temp_ssa_name (TREE_TYPE (next), NULL, | |
241 | "unrinittmp"); | |
242 | else | |
243 | new_init = make_temp_ssa_name (TREE_TYPE (init), NULL, | |
244 | "unrinittmp"); | |
245 | ||
246 | gphi * newphi = create_phi_node (new_init, rest); | |
247 | add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION); | |
248 | add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION); | |
249 | SET_USE (op, new_init); | |
250 | } | |
251 | } | |
252 | ||
253 | /* The two loops LOOP1 and LOOP2 were just created by loop versioning, | |
254 | they are still equivalent and placed in two arms of a diamond, like so: | |
255 | ||
256 | .------if (cond)------. | |
257 | v v | |
258 | pre1 pre2 | |
259 | | | | |
260 | .--->h1 h2<----. | |
261 | | | | | | |
262 | | ex1---. .---ex2 | | |
263 | | / | | \ | | |
264 | '---l1 X | l2---' | |
265 | | | | |
266 | | | | |
267 | '--->join<---' | |
268 | ||
269 | This function transforms the program such that LOOP1 is conditionally | |
270 | falling through to LOOP2, or skipping it. This is done by splitting | |
271 | the ex1->join edge at X in the diagram above, and inserting a condition | |
272 | whose one arm goes to pre2, resulting in this situation: | |
1c0a8806 | 273 | |
28df8730 MM |
274 | .------if (cond)------. |
275 | v v | |
276 | pre1 .---------->pre2 | |
277 | | | | | |
278 | .--->h1 | h2<----. | |
279 | | | | | | | |
280 | | ex1---. | .---ex2 | | |
281 | | / v | | \ | | |
282 | '---l1 skip---' | l2---' | |
283 | | | | |
284 | | | | |
285 | '--->join<---' | |
286 | ||
1c0a8806 | 287 | |
28df8730 MM |
288 | The condition used is the exit condition of LOOP1, which effectively means |
289 | that when the first loop exits (for whatever reason) but the real original | |
290 | exit expression is still false the second loop will be entered. | |
291 | The function returns the new edge cond->pre2. | |
1c0a8806 | 292 | |
28df8730 MM |
293 | This doesn't update the SSA form, see connect_loop_phis for that. */ |
294 | ||
295 | static edge | |
296 | connect_loops (struct loop *loop1, struct loop *loop2) | |
297 | { | |
298 | edge exit = single_exit (loop1); | |
299 | basic_block skip_bb = split_edge (exit); | |
300 | gcond *skip_stmt; | |
301 | gimple_stmt_iterator gsi; | |
302 | edge new_e, skip_e; | |
303 | ||
304 | gimple *stmt = last_stmt (exit->src); | |
305 | skip_stmt = gimple_build_cond (gimple_cond_code (stmt), | |
306 | gimple_cond_lhs (stmt), | |
307 | gimple_cond_rhs (stmt), | |
308 | NULL_TREE, NULL_TREE); | |
309 | gsi = gsi_last_bb (skip_bb); | |
310 | gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT); | |
311 | ||
312 | skip_e = EDGE_SUCC (skip_bb, 0); | |
313 | skip_e->flags &= ~EDGE_FALLTHRU; | |
314 | new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0); | |
315 | if (exit->flags & EDGE_TRUE_VALUE) | |
316 | { | |
317 | skip_e->flags |= EDGE_TRUE_VALUE; | |
318 | new_e->flags |= EDGE_FALSE_VALUE; | |
319 | } | |
320 | else | |
321 | { | |
322 | skip_e->flags |= EDGE_FALSE_VALUE; | |
323 | new_e->flags |= EDGE_TRUE_VALUE; | |
324 | } | |
325 | ||
326 | new_e->count = skip_bb->count; | |
327 | new_e->probability = PROB_LIKELY; | |
328 | new_e->count = apply_probability (skip_e->count, PROB_LIKELY); | |
329 | skip_e->count -= new_e->count; | |
330 | skip_e->probability = inverse_probability (PROB_LIKELY); | |
331 | ||
332 | return new_e; | |
333 | } | |
334 | ||
335 | /* This returns the new bound for iterations given the original iteration | |
336 | space in NITER, an arbitrary new bound BORDER, assumed to be some | |
337 | comparison value with a different IV, the initial value GUARD_INIT of | |
338 | that other IV, and the comparison code GUARD_CODE that compares | |
339 | that other IV with BORDER. We return an SSA name, and place any | |
340 | necessary statements for that computation into *STMTS. | |
341 | ||
342 | For example for such a loop: | |
343 | ||
344 | for (i = beg, j = guard_init; i < end; i++, j++) | |
345 | if (j < border) // this is supposed to be true/false | |
346 | ... | |
347 | ||
348 | we want to return a new bound (on j) that makes the loop iterate | |
349 | as long as the condition j < border stays true. We also don't want | |
350 | to iterate more often than the original loop, so we have to introduce | |
351 | some cut-off as well (via min/max), effectively resulting in: | |
352 | ||
353 | newend = min (end+guard_init-beg, border) | |
354 | for (i = beg; j = guard_init; j < newend; i++, j++) | |
355 | if (j < c) | |
356 | ... | |
357 | ||
358 | Depending on the direction of the IVs and if the exit tests | |
359 | are strict or non-strict we need to use MIN or MAX, | |
360 | and add or subtract 1. This routine computes newend above. */ | |
361 | ||
362 | static tree | |
363 | compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter, | |
364 | tree border, | |
365 | enum tree_code guard_code, tree guard_init) | |
366 | { | |
367 | /* The niter structure contains the after-increment IV, we need | |
368 | the loop-enter base, so subtract STEP once. */ | |
369 | tree controlbase = force_gimple_operand (niter->control.base, | |
370 | stmts, true, NULL_TREE); | |
371 | tree controlstep = niter->control.step; | |
372 | tree enddiff; | |
373 | if (POINTER_TYPE_P (TREE_TYPE (controlbase))) | |
374 | { | |
375 | controlstep = gimple_build (stmts, NEGATE_EXPR, | |
376 | TREE_TYPE (controlstep), controlstep); | |
377 | enddiff = gimple_build (stmts, POINTER_PLUS_EXPR, | |
378 | TREE_TYPE (controlbase), | |
379 | controlbase, controlstep); | |
380 | } | |
381 | else | |
382 | enddiff = gimple_build (stmts, MINUS_EXPR, | |
383 | TREE_TYPE (controlbase), | |
384 | controlbase, controlstep); | |
385 | ||
386 | /* Compute beg-guard_init. */ | |
387 | if (POINTER_TYPE_P (TREE_TYPE (enddiff))) | |
388 | { | |
389 | tree tem = gimple_convert (stmts, sizetype, guard_init); | |
390 | tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem); | |
391 | enddiff = gimple_build (stmts, POINTER_PLUS_EXPR, | |
392 | TREE_TYPE (enddiff), | |
393 | enddiff, tem); | |
394 | } | |
395 | else | |
396 | enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff), | |
397 | enddiff, guard_init); | |
398 | ||
399 | /* Compute end-(beg-guard_init). */ | |
400 | gimple_seq stmts2; | |
401 | tree newbound = force_gimple_operand (niter->bound, &stmts2, | |
402 | true, NULL_TREE); | |
403 | gimple_seq_add_seq_without_update (stmts, stmts2); | |
404 | ||
405 | if (POINTER_TYPE_P (TREE_TYPE (enddiff)) | |
406 | || POINTER_TYPE_P (TREE_TYPE (newbound))) | |
407 | { | |
408 | enddiff = gimple_convert (stmts, sizetype, enddiff); | |
409 | enddiff = gimple_build (stmts, NEGATE_EXPR, sizetype, enddiff); | |
410 | newbound = gimple_build (stmts, POINTER_PLUS_EXPR, | |
411 | TREE_TYPE (newbound), | |
412 | newbound, enddiff); | |
413 | } | |
414 | else | |
415 | newbound = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff), | |
416 | newbound, enddiff); | |
417 | ||
418 | /* Depending on the direction of the IVs the new bound for the first | |
419 | loop is the minimum or maximum of old bound and border. | |
420 | Also, if the guard condition isn't strictly less or greater, | |
421 | we need to adjust the bound. */ | |
422 | int addbound = 0; | |
423 | enum tree_code minmax; | |
424 | if (niter->cmp == LT_EXPR) | |
425 | { | |
426 | /* GT and LE are the same, inverted. */ | |
427 | if (guard_code == GT_EXPR || guard_code == LE_EXPR) | |
428 | addbound = -1; | |
429 | minmax = MIN_EXPR; | |
430 | } | |
431 | else | |
432 | { | |
433 | gcc_assert (niter->cmp == GT_EXPR); | |
434 | if (guard_code == GE_EXPR || guard_code == LT_EXPR) | |
435 | addbound = 1; | |
436 | minmax = MAX_EXPR; | |
437 | } | |
438 | ||
439 | if (addbound) | |
440 | { | |
441 | tree type2 = TREE_TYPE (newbound); | |
442 | if (POINTER_TYPE_P (type2)) | |
443 | type2 = sizetype; | |
444 | newbound = gimple_build (stmts, | |
445 | POINTER_TYPE_P (TREE_TYPE (newbound)) | |
446 | ? POINTER_PLUS_EXPR : PLUS_EXPR, | |
447 | TREE_TYPE (newbound), | |
448 | newbound, | |
449 | build_int_cst (type2, addbound)); | |
450 | } | |
451 | ||
452 | newbound = gimple_convert (stmts, TREE_TYPE (border), newbound); | |
453 | tree newend = gimple_build (stmts, minmax, TREE_TYPE (border), | |
454 | border, newbound); | |
455 | return newend; | |
456 | } | |
457 | ||
458 | /* Checks if LOOP contains an conditional block whose condition | |
459 | depends on which side in the iteration space it is, and if so | |
460 | splits the iteration space into two loops. Returns true if the | |
461 | loop was split. NITER must contain the iteration descriptor for the | |
462 | single exit of LOOP. */ | |
463 | ||
464 | static bool | |
465 | split_loop (struct loop *loop1, struct tree_niter_desc *niter) | |
466 | { | |
467 | basic_block *bbs; | |
468 | unsigned i; | |
469 | bool changed = false; | |
470 | tree guard_iv; | |
471 | tree border; | |
472 | affine_iv iv; | |
473 | ||
474 | bbs = get_loop_body (loop1); | |
475 | ||
476 | /* Find a splitting opportunity. */ | |
477 | for (i = 0; i < loop1->num_nodes; i++) | |
478 | if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv))) | |
479 | { | |
480 | /* Handling opposite steps is not implemented yet. Neither | |
481 | is handling different step sizes. */ | |
482 | if ((tree_int_cst_sign_bit (iv.step) | |
483 | != tree_int_cst_sign_bit (niter->control.step)) | |
484 | || !tree_int_cst_equal (iv.step, niter->control.step)) | |
485 | continue; | |
486 | ||
487 | /* Find a loop PHI node that defines guard_iv directly, | |
488 | or create one doing that. */ | |
489 | gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv); | |
490 | if (!phi) | |
491 | continue; | |
492 | gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i])); | |
493 | tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi, | |
494 | loop_preheader_edge (loop1)); | |
495 | enum tree_code guard_code = gimple_cond_code (guard_stmt); | |
496 | ||
497 | /* Loop splitting is implemented by versioning the loop, placing | |
498 | the new loop after the old loop, make the first loop iterate | |
499 | as long as the conditional stays true (or false) and let the | |
500 | second (new) loop handle the rest of the iterations. | |
501 | ||
502 | First we need to determine if the condition will start being true | |
503 | or false in the first loop. */ | |
504 | bool initial_true; | |
505 | switch (guard_code) | |
506 | { | |
507 | case LT_EXPR: | |
508 | case LE_EXPR: | |
509 | initial_true = !tree_int_cst_sign_bit (iv.step); | |
510 | break; | |
511 | case GT_EXPR: | |
512 | case GE_EXPR: | |
513 | initial_true = tree_int_cst_sign_bit (iv.step); | |
514 | break; | |
515 | default: | |
516 | gcc_unreachable (); | |
517 | } | |
518 | ||
519 | /* Build a condition that will skip the first loop when the | |
520 | guard condition won't ever be true (or false). */ | |
521 | gimple_seq stmts2; | |
522 | border = force_gimple_operand (border, &stmts2, true, NULL_TREE); | |
523 | if (stmts2) | |
524 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), | |
525 | stmts2); | |
526 | tree cond = build2 (guard_code, boolean_type_node, guard_init, border); | |
527 | if (!initial_true) | |
528 | cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); | |
529 | ||
530 | /* Now version the loop, placing loop2 after loop1 connecting | |
531 | them, and fix up SSA form for that. */ | |
532 | initialize_original_copy_tables (); | |
533 | basic_block cond_bb; | |
534 | struct loop *loop2 = loop_version (loop1, cond, &cond_bb, | |
535 | REG_BR_PROB_BASE, REG_BR_PROB_BASE, | |
536 | REG_BR_PROB_BASE, true); | |
537 | gcc_assert (loop2); | |
538 | update_ssa (TODO_update_ssa); | |
539 | ||
540 | edge new_e = connect_loops (loop1, loop2); | |
541 | connect_loop_phis (loop1, loop2, new_e); | |
542 | ||
543 | /* The iterations of the second loop is now already | |
544 | exactly those that the first loop didn't do, but the | |
545 | iteration space of the first loop is still the original one. | |
546 | Compute the new bound for the guarding IV and patch the | |
547 | loop exit to use it instead of original IV and bound. */ | |
548 | gimple_seq stmts = NULL; | |
549 | tree newend = compute_new_first_bound (&stmts, niter, border, | |
550 | guard_code, guard_init); | |
551 | if (stmts) | |
552 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), | |
553 | stmts); | |
554 | tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); | |
555 | patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true); | |
556 | ||
557 | /* Finally patch out the two copies of the condition to be always | |
558 | true/false (or opposite). */ | |
559 | gcond *force_true = as_a<gcond *> (last_stmt (bbs[i])); | |
560 | gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i]))); | |
561 | if (!initial_true) | |
562 | std::swap (force_true, force_false); | |
563 | gimple_cond_make_true (force_true); | |
564 | gimple_cond_make_false (force_false); | |
565 | update_stmt (force_true); | |
566 | update_stmt (force_false); | |
567 | ||
568 | free_original_copy_tables (); | |
569 | ||
570 | /* We destroyed LCSSA form above. Eventually we might be able | |
571 | to fix it on the fly, for now simply punt and use the helper. */ | |
572 | rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1); | |
573 | ||
574 | changed = true; | |
575 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
576 | fprintf (dump_file, ";; Loop split.\n"); | |
577 | ||
578 | /* Only deal with the first opportunity. */ | |
579 | break; | |
580 | } | |
581 | ||
582 | free (bbs); | |
583 | return changed; | |
584 | } | |
585 | ||
586 | /* Main entry point. Perform loop splitting on all suitable loops. */ | |
587 | ||
588 | static unsigned int | |
589 | tree_ssa_split_loops (void) | |
590 | { | |
591 | struct loop *loop; | |
592 | bool changed = false; | |
593 | ||
594 | gcc_assert (scev_initialized_p ()); | |
595 | FOR_EACH_LOOP (loop, 0) | |
596 | loop->aux = NULL; | |
597 | ||
598 | /* Go through all loops starting from innermost. */ | |
599 | FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | |
600 | { | |
601 | struct tree_niter_desc niter; | |
602 | if (loop->aux) | |
603 | { | |
604 | /* If any of our inner loops was split, don't split us, | |
605 | and mark our containing loop as having had splits as well. */ | |
606 | loop_outer (loop)->aux = loop; | |
607 | continue; | |
608 | } | |
609 | ||
610 | if (single_exit (loop) | |
611 | /* ??? We could handle non-empty latches when we split | |
612 | the latch edge (not the exit edge), and put the new | |
613 | exit condition in the new block. OTOH this executes some | |
614 | code unconditionally that might have been skipped by the | |
615 | original exit before. */ | |
616 | && empty_block_p (loop->latch) | |
617 | && !optimize_loop_for_size_p (loop) | |
618 | && number_of_iterations_exit (loop, single_exit (loop), &niter, | |
619 | false, true) | |
620 | && niter.cmp != ERROR_MARK | |
621 | /* We can't yet handle loops controlled by a != predicate. */ | |
622 | && niter.cmp != NE_EXPR) | |
623 | { | |
624 | if (split_loop (loop, &niter)) | |
625 | { | |
626 | /* Mark our containing loop as having had some split inner | |
627 | loops. */ | |
628 | loop_outer (loop)->aux = loop; | |
629 | changed = true; | |
630 | } | |
631 | } | |
632 | } | |
633 | ||
634 | FOR_EACH_LOOP (loop, 0) | |
635 | loop->aux = NULL; | |
636 | ||
637 | if (changed) | |
638 | return TODO_cleanup_cfg; | |
639 | return 0; | |
640 | } | |
641 | ||
642 | /* Loop splitting pass. */ | |
643 | ||
644 | namespace { | |
645 | ||
646 | const pass_data pass_data_loop_split = | |
647 | { | |
648 | GIMPLE_PASS, /* type */ | |
649 | "lsplit", /* name */ | |
650 | OPTGROUP_LOOP, /* optinfo_flags */ | |
651 | TV_LOOP_SPLIT, /* tv_id */ | |
652 | PROP_cfg, /* properties_required */ | |
653 | 0, /* properties_provided */ | |
654 | 0, /* properties_destroyed */ | |
655 | 0, /* todo_flags_start */ | |
656 | 0, /* todo_flags_finish */ | |
657 | }; | |
658 | ||
659 | class pass_loop_split : public gimple_opt_pass | |
660 | { | |
661 | public: | |
662 | pass_loop_split (gcc::context *ctxt) | |
663 | : gimple_opt_pass (pass_data_loop_split, ctxt) | |
664 | {} | |
665 | ||
666 | /* opt_pass methods: */ | |
667 | virtual bool gate (function *) { return flag_split_loops != 0; } | |
668 | virtual unsigned int execute (function *); | |
669 | ||
670 | }; // class pass_loop_split | |
671 | ||
672 | unsigned int | |
673 | pass_loop_split::execute (function *fun) | |
674 | { | |
675 | if (number_of_loops (fun) <= 1) | |
676 | return 0; | |
677 | ||
678 | return tree_ssa_split_loops (); | |
679 | } | |
680 | ||
681 | } // anon namespace | |
682 | ||
683 | gimple_opt_pass * | |
684 | make_pass_loop_split (gcc::context *ctxt) | |
685 | { | |
686 | return new pass_loop_split (ctxt); | |
687 | } |