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