]>
Commit | Line | Data |
---|---|---|
28df8730 | 1 | /* Loop splitting. |
99dee823 | 2 | Copyright (C) 2015-2021 Free Software Foundation, Inc. |
28df8730 MM |
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" | |
095f78c6 FX |
35 | #include "tree-inline.h" |
36 | #include "tree-cfgcleanup.h" | |
28df8730 MM |
37 | #include "cfgloop.h" |
38 | #include "tree-scalar-evolution.h" | |
39 | #include "gimple-iterator.h" | |
40 | #include "gimple-pretty-print.h" | |
41 | #include "cfghooks.h" | |
42 | #include "gimple-fold.h" | |
43 | #include "gimplify-me.h" | |
44 | ||
095f78c6 FX |
45 | /* This file implements two kinds of loop splitting. |
46 | ||
47 | One transformation of loops like: | |
28df8730 MM |
48 | |
49 | for (i = 0; i < 100; i++) | |
50 | { | |
51 | if (i < 50) | |
52 | A; | |
53 | else | |
54 | B; | |
55 | } | |
56 | ||
57 | into: | |
58 | ||
59 | for (i = 0; i < 50; i++) | |
60 | { | |
61 | A; | |
62 | } | |
63 | for (; i < 100; i++) | |
64 | { | |
65 | B; | |
66 | } | |
67 | ||
68 | */ | |
69 | ||
70 | /* Return true when BB inside LOOP is a potential iteration space | |
71 | split point, i.e. ends with a condition like "IV < comp", which | |
72 | is true on one side of the iteration space and false on the other, | |
73 | and the split point can be computed. If so, also return the border | |
74 | point in *BORDER and the comparison induction variable in IV. */ | |
75 | ||
76 | static tree | |
99b1c316 | 77 | split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv) |
28df8730 MM |
78 | { |
79 | gimple *last; | |
80 | gcond *stmt; | |
81 | affine_iv iv2; | |
82 | ||
83 | /* BB must end in a simple conditional jump. */ | |
84 | last = last_stmt (bb); | |
85 | if (!last || gimple_code (last) != GIMPLE_COND) | |
86 | return NULL_TREE; | |
87 | stmt = as_a <gcond *> (last); | |
88 | ||
89 | enum tree_code code = gimple_cond_code (stmt); | |
90 | ||
91 | /* Only handle relational comparisons, for equality and non-equality | |
92 | we'd have to split the loop into two loops and a middle statement. */ | |
93 | switch (code) | |
94 | { | |
95 | case LT_EXPR: | |
96 | case LE_EXPR: | |
97 | case GT_EXPR: | |
98 | case GE_EXPR: | |
99 | break; | |
100 | default: | |
101 | return NULL_TREE; | |
102 | } | |
103 | ||
104 | if (loop_exits_from_bb_p (loop, bb)) | |
105 | return NULL_TREE; | |
106 | ||
107 | tree op0 = gimple_cond_lhs (stmt); | |
108 | tree op1 = gimple_cond_rhs (stmt); | |
99b1c316 | 109 | class loop *useloop = loop_containing_stmt (stmt); |
28df8730 | 110 | |
9042295c | 111 | if (!simple_iv (loop, useloop, op0, iv, false)) |
28df8730 | 112 | return NULL_TREE; |
9042295c | 113 | if (!simple_iv (loop, useloop, op1, &iv2, false)) |
28df8730 MM |
114 | return NULL_TREE; |
115 | ||
116 | /* Make it so that the first argument of the condition is | |
117 | the looping one. */ | |
118 | if (!integer_zerop (iv2.step)) | |
119 | { | |
120 | std::swap (op0, op1); | |
121 | std::swap (*iv, iv2); | |
122 | code = swap_tree_comparison (code); | |
123 | gimple_cond_set_condition (stmt, code, op0, op1); | |
124 | update_stmt (stmt); | |
125 | } | |
126 | else if (integer_zerop (iv->step)) | |
127 | return NULL_TREE; | |
128 | if (!integer_zerop (iv2.step)) | |
129 | return NULL_TREE; | |
9042295c MM |
130 | if (!iv->no_overflow) |
131 | return NULL_TREE; | |
28df8730 MM |
132 | |
133 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
134 | { | |
135 | fprintf (dump_file, "Found potential split point: "); | |
136 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
137 | fprintf (dump_file, " { "); | |
138 | print_generic_expr (dump_file, iv->base, TDF_SLIM); | |
139 | fprintf (dump_file, " + I*"); | |
140 | print_generic_expr (dump_file, iv->step, TDF_SLIM); | |
141 | fprintf (dump_file, " } %s ", get_tree_code_name (code)); | |
142 | print_generic_expr (dump_file, iv2.base, TDF_SLIM); | |
143 | fprintf (dump_file, "\n"); | |
144 | } | |
145 | ||
146 | *border = iv2.base; | |
147 | return op0; | |
148 | } | |
149 | ||
150 | /* Given a GUARD conditional stmt inside LOOP, which we want to make always | |
151 | true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL | |
152 | (a post-increment IV) and NEWBOUND (the comparator) adjust the loop | |
153 | exit test statement to loop back only if the GUARD statement will | |
154 | also be true/false in the next iteration. */ | |
155 | ||
156 | static void | |
99b1c316 | 157 | patch_loop_exit (class loop *loop, gcond *guard, tree nextval, tree newbound, |
28df8730 MM |
158 | bool initial_true) |
159 | { | |
160 | edge exit = single_exit (loop); | |
161 | gcond *stmt = as_a <gcond *> (last_stmt (exit->src)); | |
162 | gimple_cond_set_condition (stmt, gimple_cond_code (guard), | |
163 | nextval, newbound); | |
164 | update_stmt (stmt); | |
165 | ||
d886761f | 166 | edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit); |
28df8730 MM |
167 | |
168 | exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
169 | stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
170 | ||
171 | if (initial_true) | |
172 | { | |
173 | exit->flags |= EDGE_FALSE_VALUE; | |
174 | stay->flags |= EDGE_TRUE_VALUE; | |
175 | } | |
176 | else | |
177 | { | |
178 | exit->flags |= EDGE_TRUE_VALUE; | |
179 | stay->flags |= EDGE_FALSE_VALUE; | |
180 | } | |
181 | } | |
182 | ||
183 | /* Give an induction variable GUARD_IV, and its affine descriptor IV, | |
184 | find the loop phi node in LOOP defining it directly, or create | |
185 | such phi node. Return that phi node. */ | |
186 | ||
187 | static gphi * | |
99b1c316 | 188 | find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/) |
28df8730 MM |
189 | { |
190 | gimple *def = SSA_NAME_DEF_STMT (guard_iv); | |
191 | gphi *phi; | |
192 | if ((phi = dyn_cast <gphi *> (def)) | |
193 | && gimple_bb (phi) == loop->header) | |
194 | return phi; | |
195 | ||
196 | /* XXX Create the PHI instead. */ | |
197 | return NULL; | |
198 | } | |
199 | ||
09844a5f MM |
200 | /* Returns true if the exit values of all loop phi nodes can be |
201 | determined easily (i.e. that connect_loop_phis can determine them). */ | |
202 | ||
203 | static bool | |
99b1c316 | 204 | easy_exit_values (class loop *loop) |
09844a5f MM |
205 | { |
206 | edge exit = single_exit (loop); | |
207 | edge latch = loop_latch_edge (loop); | |
208 | gphi_iterator psi; | |
209 | ||
210 | /* Currently we regard the exit values as easy if they are the same | |
211 | as the value over the backedge. Which is the case if the definition | |
212 | of the backedge value dominates the exit edge. */ | |
213 | for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) | |
214 | { | |
215 | gphi *phi = psi.phi (); | |
216 | tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch); | |
217 | basic_block bb; | |
218 | if (TREE_CODE (next) == SSA_NAME | |
219 | && (bb = gimple_bb (SSA_NAME_DEF_STMT (next))) | |
220 | && !dominated_by_p (CDI_DOMINATORS, exit->src, bb)) | |
221 | return false; | |
222 | } | |
223 | ||
224 | return true; | |
225 | } | |
226 | ||
28df8730 MM |
227 | /* This function updates the SSA form after connect_loops made a new |
228 | edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate | |
229 | conditional). I.e. the second loop can now be entered either | |
230 | via the original entry or via NEW_E, so the entry values of LOOP2 | |
231 | phi nodes are either the original ones or those at the exit | |
232 | of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting | |
09844a5f | 233 | this. The loops need to fulfill easy_exit_values(). */ |
28df8730 MM |
234 | |
235 | static void | |
99b1c316 | 236 | connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e) |
28df8730 MM |
237 | { |
238 | basic_block rest = loop_preheader_edge (loop2)->src; | |
239 | gcc_assert (new_e->dest == rest); | |
240 | edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e); | |
241 | ||
242 | edge firste = loop_preheader_edge (loop1); | |
243 | edge seconde = loop_preheader_edge (loop2); | |
244 | edge firstn = loop_latch_edge (loop1); | |
245 | gphi_iterator psi_first, psi_second; | |
246 | for (psi_first = gsi_start_phis (loop1->header), | |
247 | psi_second = gsi_start_phis (loop2->header); | |
248 | !gsi_end_p (psi_first); | |
249 | gsi_next (&psi_first), gsi_next (&psi_second)) | |
250 | { | |
251 | tree init, next, new_init; | |
252 | use_operand_p op; | |
253 | gphi *phi_first = psi_first.phi (); | |
254 | gphi *phi_second = psi_second.phi (); | |
255 | ||
256 | init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste); | |
257 | next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn); | |
258 | op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde); | |
259 | gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); | |
260 | ||
261 | /* Prefer using original variable as a base for the new ssa name. | |
262 | This is necessary for virtual ops, and useful in order to avoid | |
263 | losing debug info for real ops. */ | |
264 | if (TREE_CODE (next) == SSA_NAME | |
265 | && useless_type_conversion_p (TREE_TYPE (next), | |
266 | TREE_TYPE (init))) | |
267 | new_init = copy_ssa_name (next); | |
268 | else if (TREE_CODE (init) == SSA_NAME | |
269 | && useless_type_conversion_p (TREE_TYPE (init), | |
270 | TREE_TYPE (next))) | |
271 | new_init = copy_ssa_name (init); | |
272 | else if (useless_type_conversion_p (TREE_TYPE (next), | |
273 | TREE_TYPE (init))) | |
274 | new_init = make_temp_ssa_name (TREE_TYPE (next), NULL, | |
275 | "unrinittmp"); | |
276 | else | |
277 | new_init = make_temp_ssa_name (TREE_TYPE (init), NULL, | |
278 | "unrinittmp"); | |
279 | ||
280 | gphi * newphi = create_phi_node (new_init, rest); | |
281 | add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION); | |
282 | add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION); | |
283 | SET_USE (op, new_init); | |
284 | } | |
285 | } | |
286 | ||
287 | /* The two loops LOOP1 and LOOP2 were just created by loop versioning, | |
288 | they are still equivalent and placed in two arms of a diamond, like so: | |
289 | ||
290 | .------if (cond)------. | |
291 | v v | |
292 | pre1 pre2 | |
293 | | | | |
294 | .--->h1 h2<----. | |
295 | | | | | | |
296 | | ex1---. .---ex2 | | |
297 | | / | | \ | | |
298 | '---l1 X | l2---' | |
299 | | | | |
300 | | | | |
301 | '--->join<---' | |
302 | ||
303 | This function transforms the program such that LOOP1 is conditionally | |
304 | falling through to LOOP2, or skipping it. This is done by splitting | |
305 | the ex1->join edge at X in the diagram above, and inserting a condition | |
306 | whose one arm goes to pre2, resulting in this situation: | |
1c0a8806 | 307 | |
28df8730 MM |
308 | .------if (cond)------. |
309 | v v | |
310 | pre1 .---------->pre2 | |
311 | | | | | |
312 | .--->h1 | h2<----. | |
313 | | | | | | | |
314 | | ex1---. | .---ex2 | | |
315 | | / v | | \ | | |
316 | '---l1 skip---' | l2---' | |
317 | | | | |
318 | | | | |
319 | '--->join<---' | |
320 | ||
1c0a8806 | 321 | |
28df8730 MM |
322 | The condition used is the exit condition of LOOP1, which effectively means |
323 | that when the first loop exits (for whatever reason) but the real original | |
324 | exit expression is still false the second loop will be entered. | |
325 | The function returns the new edge cond->pre2. | |
1c0a8806 | 326 | |
28df8730 MM |
327 | This doesn't update the SSA form, see connect_loop_phis for that. */ |
328 | ||
329 | static edge | |
99b1c316 | 330 | connect_loops (class loop *loop1, class loop *loop2) |
28df8730 MM |
331 | { |
332 | edge exit = single_exit (loop1); | |
333 | basic_block skip_bb = split_edge (exit); | |
334 | gcond *skip_stmt; | |
335 | gimple_stmt_iterator gsi; | |
336 | edge new_e, skip_e; | |
337 | ||
338 | gimple *stmt = last_stmt (exit->src); | |
339 | skip_stmt = gimple_build_cond (gimple_cond_code (stmt), | |
340 | gimple_cond_lhs (stmt), | |
341 | gimple_cond_rhs (stmt), | |
342 | NULL_TREE, NULL_TREE); | |
343 | gsi = gsi_last_bb (skip_bb); | |
344 | gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT); | |
345 | ||
346 | skip_e = EDGE_SUCC (skip_bb, 0); | |
347 | skip_e->flags &= ~EDGE_FALLTHRU; | |
348 | new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0); | |
349 | if (exit->flags & EDGE_TRUE_VALUE) | |
350 | { | |
351 | skip_e->flags |= EDGE_TRUE_VALUE; | |
352 | new_e->flags |= EDGE_FALSE_VALUE; | |
353 | } | |
354 | else | |
355 | { | |
356 | skip_e->flags |= EDGE_FALSE_VALUE; | |
357 | new_e->flags |= EDGE_TRUE_VALUE; | |
358 | } | |
359 | ||
357067f2 | 360 | new_e->probability = profile_probability::likely (); |
ef30ab83 | 361 | skip_e->probability = new_e->probability.invert (); |
28df8730 MM |
362 | |
363 | return new_e; | |
364 | } | |
365 | ||
366 | /* This returns the new bound for iterations given the original iteration | |
367 | space in NITER, an arbitrary new bound BORDER, assumed to be some | |
368 | comparison value with a different IV, the initial value GUARD_INIT of | |
369 | that other IV, and the comparison code GUARD_CODE that compares | |
370 | that other IV with BORDER. We return an SSA name, and place any | |
371 | necessary statements for that computation into *STMTS. | |
372 | ||
373 | For example for such a loop: | |
374 | ||
375 | for (i = beg, j = guard_init; i < end; i++, j++) | |
376 | if (j < border) // this is supposed to be true/false | |
377 | ... | |
378 | ||
379 | we want to return a new bound (on j) that makes the loop iterate | |
380 | as long as the condition j < border stays true. We also don't want | |
381 | to iterate more often than the original loop, so we have to introduce | |
382 | some cut-off as well (via min/max), effectively resulting in: | |
383 | ||
384 | newend = min (end+guard_init-beg, border) | |
385 | for (i = beg; j = guard_init; j < newend; i++, j++) | |
386 | if (j < c) | |
387 | ... | |
388 | ||
389 | Depending on the direction of the IVs and if the exit tests | |
390 | are strict or non-strict we need to use MIN or MAX, | |
391 | and add or subtract 1. This routine computes newend above. */ | |
392 | ||
393 | static tree | |
99b1c316 | 394 | compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter, |
28df8730 MM |
395 | tree border, |
396 | enum tree_code guard_code, tree guard_init) | |
397 | { | |
398 | /* The niter structure contains the after-increment IV, we need | |
399 | the loop-enter base, so subtract STEP once. */ | |
400 | tree controlbase = force_gimple_operand (niter->control.base, | |
401 | stmts, true, NULL_TREE); | |
402 | tree controlstep = niter->control.step; | |
403 | tree enddiff; | |
404 | if (POINTER_TYPE_P (TREE_TYPE (controlbase))) | |
405 | { | |
406 | controlstep = gimple_build (stmts, NEGATE_EXPR, | |
407 | TREE_TYPE (controlstep), controlstep); | |
408 | enddiff = gimple_build (stmts, POINTER_PLUS_EXPR, | |
409 | TREE_TYPE (controlbase), | |
410 | controlbase, controlstep); | |
411 | } | |
412 | else | |
413 | enddiff = gimple_build (stmts, MINUS_EXPR, | |
414 | TREE_TYPE (controlbase), | |
415 | controlbase, controlstep); | |
416 | ||
09844a5f MM |
417 | /* Compute end-beg. */ |
418 | gimple_seq stmts2; | |
419 | tree end = force_gimple_operand (niter->bound, &stmts2, | |
420 | true, NULL_TREE); | |
421 | gimple_seq_add_seq_without_update (stmts, stmts2); | |
28df8730 MM |
422 | if (POINTER_TYPE_P (TREE_TYPE (enddiff))) |
423 | { | |
09844a5f | 424 | tree tem = gimple_convert (stmts, sizetype, enddiff); |
28df8730 MM |
425 | tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem); |
426 | enddiff = gimple_build (stmts, POINTER_PLUS_EXPR, | |
427 | TREE_TYPE (enddiff), | |
09844a5f | 428 | end, tem); |
28df8730 MM |
429 | } |
430 | else | |
431 | enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff), | |
09844a5f | 432 | end, enddiff); |
28df8730 | 433 | |
09844a5f MM |
434 | /* Compute guard_init + (end-beg). */ |
435 | tree newbound; | |
436 | enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff); | |
437 | if (POINTER_TYPE_P (TREE_TYPE (guard_init))) | |
28df8730 MM |
438 | { |
439 | enddiff = gimple_convert (stmts, sizetype, enddiff); | |
28df8730 | 440 | newbound = gimple_build (stmts, POINTER_PLUS_EXPR, |
09844a5f MM |
441 | TREE_TYPE (guard_init), |
442 | guard_init, enddiff); | |
28df8730 MM |
443 | } |
444 | else | |
09844a5f MM |
445 | newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init), |
446 | guard_init, enddiff); | |
28df8730 MM |
447 | |
448 | /* Depending on the direction of the IVs the new bound for the first | |
449 | loop is the minimum or maximum of old bound and border. | |
450 | Also, if the guard condition isn't strictly less or greater, | |
451 | we need to adjust the bound. */ | |
452 | int addbound = 0; | |
453 | enum tree_code minmax; | |
454 | if (niter->cmp == LT_EXPR) | |
455 | { | |
456 | /* GT and LE are the same, inverted. */ | |
457 | if (guard_code == GT_EXPR || guard_code == LE_EXPR) | |
458 | addbound = -1; | |
459 | minmax = MIN_EXPR; | |
460 | } | |
461 | else | |
462 | { | |
463 | gcc_assert (niter->cmp == GT_EXPR); | |
464 | if (guard_code == GE_EXPR || guard_code == LT_EXPR) | |
465 | addbound = 1; | |
466 | minmax = MAX_EXPR; | |
467 | } | |
468 | ||
469 | if (addbound) | |
470 | { | |
471 | tree type2 = TREE_TYPE (newbound); | |
472 | if (POINTER_TYPE_P (type2)) | |
473 | type2 = sizetype; | |
474 | newbound = gimple_build (stmts, | |
475 | POINTER_TYPE_P (TREE_TYPE (newbound)) | |
476 | ? POINTER_PLUS_EXPR : PLUS_EXPR, | |
477 | TREE_TYPE (newbound), | |
478 | newbound, | |
479 | build_int_cst (type2, addbound)); | |
480 | } | |
481 | ||
28df8730 MM |
482 | tree newend = gimple_build (stmts, minmax, TREE_TYPE (border), |
483 | border, newbound); | |
484 | return newend; | |
485 | } | |
486 | ||
487 | /* Checks if LOOP contains an conditional block whose condition | |
488 | depends on which side in the iteration space it is, and if so | |
489 | splits the iteration space into two loops. Returns true if the | |
490 | loop was split. NITER must contain the iteration descriptor for the | |
491 | single exit of LOOP. */ | |
492 | ||
493 | static bool | |
095f78c6 | 494 | split_loop (class loop *loop1) |
28df8730 | 495 | { |
095f78c6 | 496 | class tree_niter_desc niter; |
28df8730 MM |
497 | basic_block *bbs; |
498 | unsigned i; | |
499 | bool changed = false; | |
500 | tree guard_iv; | |
d61d5fcd | 501 | tree border = NULL_TREE; |
28df8730 MM |
502 | affine_iv iv; |
503 | ||
095f78c6 FX |
504 | if (!single_exit (loop1) |
505 | /* ??? We could handle non-empty latches when we split the latch edge | |
506 | (not the exit edge), and put the new exit condition in the new block. | |
507 | OTOH this executes some code unconditionally that might have been | |
508 | skipped by the original exit before. */ | |
509 | || !empty_block_p (loop1->latch) | |
510 | || !easy_exit_values (loop1) | |
511 | || !number_of_iterations_exit (loop1, single_exit (loop1), &niter, | |
512 | false, true) | |
513 | || niter.cmp == ERROR_MARK | |
514 | /* We can't yet handle loops controlled by a != predicate. */ | |
515 | || niter.cmp == NE_EXPR) | |
516 | return false; | |
517 | ||
28df8730 MM |
518 | bbs = get_loop_body (loop1); |
519 | ||
095f78c6 FX |
520 | if (!can_copy_bbs_p (bbs, loop1->num_nodes)) |
521 | { | |
522 | free (bbs); | |
523 | return false; | |
524 | } | |
525 | ||
28df8730 MM |
526 | /* Find a splitting opportunity. */ |
527 | for (i = 0; i < loop1->num_nodes; i++) | |
528 | if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv))) | |
529 | { | |
530 | /* Handling opposite steps is not implemented yet. Neither | |
531 | is handling different step sizes. */ | |
532 | if ((tree_int_cst_sign_bit (iv.step) | |
095f78c6 FX |
533 | != tree_int_cst_sign_bit (niter.control.step)) |
534 | || !tree_int_cst_equal (iv.step, niter.control.step)) | |
28df8730 MM |
535 | continue; |
536 | ||
537 | /* Find a loop PHI node that defines guard_iv directly, | |
538 | or create one doing that. */ | |
539 | gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv); | |
540 | if (!phi) | |
541 | continue; | |
542 | gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i])); | |
543 | tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi, | |
544 | loop_preheader_edge (loop1)); | |
545 | enum tree_code guard_code = gimple_cond_code (guard_stmt); | |
546 | ||
547 | /* Loop splitting is implemented by versioning the loop, placing | |
548 | the new loop after the old loop, make the first loop iterate | |
549 | as long as the conditional stays true (or false) and let the | |
550 | second (new) loop handle the rest of the iterations. | |
551 | ||
552 | First we need to determine if the condition will start being true | |
553 | or false in the first loop. */ | |
554 | bool initial_true; | |
555 | switch (guard_code) | |
556 | { | |
557 | case LT_EXPR: | |
558 | case LE_EXPR: | |
559 | initial_true = !tree_int_cst_sign_bit (iv.step); | |
560 | break; | |
561 | case GT_EXPR: | |
562 | case GE_EXPR: | |
563 | initial_true = tree_int_cst_sign_bit (iv.step); | |
564 | break; | |
565 | default: | |
566 | gcc_unreachable (); | |
567 | } | |
568 | ||
569 | /* Build a condition that will skip the first loop when the | |
570 | guard condition won't ever be true (or false). */ | |
571 | gimple_seq stmts2; | |
572 | border = force_gimple_operand (border, &stmts2, true, NULL_TREE); | |
573 | if (stmts2) | |
574 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), | |
575 | stmts2); | |
576 | tree cond = build2 (guard_code, boolean_type_node, guard_init, border); | |
577 | if (!initial_true) | |
578 | cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); | |
579 | ||
580 | /* Now version the loop, placing loop2 after loop1 connecting | |
581 | them, and fix up SSA form for that. */ | |
582 | initialize_original_copy_tables (); | |
583 | basic_block cond_bb; | |
357067f2 | 584 | |
99b1c316 | 585 | class loop *loop2 = loop_version (loop1, cond, &cond_bb, |
357067f2 JH |
586 | profile_probability::always (), |
587 | profile_probability::always (), | |
af2bbc51 JH |
588 | profile_probability::always (), |
589 | profile_probability::always (), | |
5d3ebb71 | 590 | true); |
28df8730 | 591 | gcc_assert (loop2); |
28df8730 MM |
592 | |
593 | edge new_e = connect_loops (loop1, loop2); | |
594 | connect_loop_phis (loop1, loop2, new_e); | |
595 | ||
596 | /* The iterations of the second loop is now already | |
597 | exactly those that the first loop didn't do, but the | |
598 | iteration space of the first loop is still the original one. | |
599 | Compute the new bound for the guarding IV and patch the | |
600 | loop exit to use it instead of original IV and bound. */ | |
601 | gimple_seq stmts = NULL; | |
095f78c6 | 602 | tree newend = compute_new_first_bound (&stmts, &niter, border, |
28df8730 MM |
603 | guard_code, guard_init); |
604 | if (stmts) | |
605 | gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), | |
606 | stmts); | |
607 | tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); | |
608 | patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true); | |
609 | ||
610 | /* Finally patch out the two copies of the condition to be always | |
611 | true/false (or opposite). */ | |
612 | gcond *force_true = as_a<gcond *> (last_stmt (bbs[i])); | |
613 | gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i]))); | |
614 | if (!initial_true) | |
615 | std::swap (force_true, force_false); | |
616 | gimple_cond_make_true (force_true); | |
617 | gimple_cond_make_false (force_false); | |
618 | update_stmt (force_true); | |
619 | update_stmt (force_false); | |
620 | ||
621 | free_original_copy_tables (); | |
622 | ||
28df8730 MM |
623 | changed = true; |
624 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
625 | fprintf (dump_file, ";; Loop split.\n"); | |
626 | ||
a1ac9ffb RB |
627 | if (dump_enabled_p ()) |
628 | dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, guard_stmt, "loop split\n"); | |
629 | ||
28df8730 MM |
630 | /* Only deal with the first opportunity. */ |
631 | break; | |
632 | } | |
633 | ||
634 | free (bbs); | |
635 | return changed; | |
636 | } | |
637 | ||
095f78c6 FX |
638 | /* Another transformation of loops like: |
639 | ||
640 | for (i = INIT (); CHECK (i); i = NEXT ()) | |
641 | { | |
642 | if (expr (a_1, a_2, ..., a_n)) // expr is pure | |
643 | a_j = ...; // change at least one a_j | |
644 | else | |
645 | S; // not change any a_j | |
646 | } | |
647 | ||
648 | into: | |
649 | ||
650 | for (i = INIT (); CHECK (i); i = NEXT ()) | |
651 | { | |
652 | if (expr (a_1, a_2, ..., a_n)) | |
653 | a_j = ...; | |
654 | else | |
655 | { | |
656 | S; | |
657 | i = NEXT (); | |
658 | break; | |
659 | } | |
660 | } | |
661 | ||
662 | for (; CHECK (i); i = NEXT ()) | |
663 | { | |
664 | S; | |
665 | } | |
666 | ||
667 | */ | |
668 | ||
669 | /* Data structure to hold temporary information during loop split upon | |
670 | semi-invariant conditional statement. */ | |
671 | class split_info { | |
672 | public: | |
673 | /* Array of all basic blocks in a loop, returned by get_loop_body(). */ | |
674 | basic_block *bbs; | |
675 | ||
676 | /* All memory store/clobber statements in a loop. */ | |
677 | auto_vec<gimple *> memory_stores; | |
678 | ||
679 | /* Whether above memory stores vector has been filled. */ | |
680 | int need_init; | |
681 | ||
682 | /* Control dependencies of basic blocks in a loop. */ | |
683 | auto_vec<hash_set<basic_block> *> control_deps; | |
684 | ||
685 | split_info () : bbs (NULL), need_init (true) { } | |
686 | ||
687 | ~split_info () | |
688 | { | |
689 | if (bbs) | |
690 | free (bbs); | |
691 | ||
692 | for (unsigned i = 0; i < control_deps.length (); i++) | |
693 | delete control_deps[i]; | |
694 | } | |
695 | }; | |
696 | ||
697 | /* Find all statements with memory-write effect in LOOP, including memory | |
698 | store and non-pure function call, and keep those in a vector. This work | |
699 | is only done one time, for the vector should be constant during analysis | |
700 | stage of semi-invariant condition. */ | |
701 | ||
702 | static void | |
703 | find_vdef_in_loop (struct loop *loop) | |
704 | { | |
705 | split_info *info = (split_info *) loop->aux; | |
706 | gphi *vphi = get_virtual_phi (loop->header); | |
707 | ||
708 | /* Indicate memory store vector has been filled. */ | |
709 | info->need_init = false; | |
710 | ||
711 | /* If loop contains memory operation, there must be a virtual PHI node in | |
712 | loop header basic block. */ | |
713 | if (vphi == NULL) | |
714 | return; | |
715 | ||
716 | /* All virtual SSA names inside the loop are connected to be a cyclic | |
717 | graph via virtual PHI nodes. The virtual PHI node in loop header just | |
718 | links the first and the last virtual SSA names, by using the last as | |
719 | PHI operand to define the first. */ | |
720 | const edge latch = loop_latch_edge (loop); | |
721 | const tree first = gimple_phi_result (vphi); | |
722 | const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch); | |
723 | ||
724 | /* The virtual SSA cyclic graph might consist of only one SSA name, who | |
725 | is defined by itself. | |
726 | ||
727 | .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)> | |
728 | ||
729 | This means the loop contains only memory loads, so we can skip it. */ | |
730 | if (first == last) | |
731 | return; | |
732 | ||
733 | auto_vec<gimple *> other_stores; | |
734 | auto_vec<tree> worklist; | |
735 | auto_bitmap visited; | |
736 | ||
737 | bitmap_set_bit (visited, SSA_NAME_VERSION (first)); | |
738 | bitmap_set_bit (visited, SSA_NAME_VERSION (last)); | |
739 | worklist.safe_push (last); | |
740 | ||
741 | do | |
742 | { | |
743 | tree vuse = worklist.pop (); | |
744 | gimple *stmt = SSA_NAME_DEF_STMT (vuse); | |
745 | ||
746 | /* We mark the first and last SSA names as visited at the beginning, | |
747 | and reversely start the process from the last SSA name towards the | |
748 | first, which ensures that this do-while will not touch SSA names | |
749 | defined outside the loop. */ | |
750 | gcc_assert (gimple_bb (stmt) | |
751 | && flow_bb_inside_loop_p (loop, gimple_bb (stmt))); | |
752 | ||
753 | if (gimple_code (stmt) == GIMPLE_PHI) | |
754 | { | |
755 | gphi *phi = as_a <gphi *> (stmt); | |
756 | ||
757 | for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
758 | { | |
759 | tree arg = gimple_phi_arg_def (stmt, i); | |
760 | ||
761 | if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg))) | |
762 | worklist.safe_push (arg); | |
763 | } | |
764 | } | |
765 | else | |
766 | { | |
767 | tree prev = gimple_vuse (stmt); | |
768 | ||
769 | /* Non-pure call statement is conservatively assumed to impact all | |
770 | memory locations. So place call statements ahead of other memory | |
700d4cb0 | 771 | stores in the vector with an idea of using them as shortcut |
095f78c6 FX |
772 | terminators to memory alias analysis. */ |
773 | if (gimple_code (stmt) == GIMPLE_CALL) | |
774 | info->memory_stores.safe_push (stmt); | |
775 | else | |
776 | other_stores.safe_push (stmt); | |
777 | ||
778 | if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev))) | |
779 | worklist.safe_push (prev); | |
780 | } | |
781 | } while (!worklist.is_empty ()); | |
782 | ||
783 | info->memory_stores.safe_splice (other_stores); | |
784 | } | |
785 | ||
786 | /* Two basic blocks have equivalent control dependency if one dominates to | |
787 | the other, and it is post-dominated by the latter. Given a basic block | |
788 | BB in LOOP, find farest equivalent dominating basic block. For BB, there | |
789 | is a constraint that BB does not post-dominate loop header of LOOP, this | |
790 | means BB is control-dependent on at least one basic block in LOOP. */ | |
791 | ||
792 | static basic_block | |
793 | get_control_equiv_head_block (struct loop *loop, basic_block bb) | |
794 | { | |
795 | while (!bb->aux) | |
796 | { | |
797 | basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); | |
798 | ||
799 | gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb)); | |
800 | ||
801 | if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb)) | |
802 | break; | |
803 | ||
804 | bb = dom_bb; | |
805 | } | |
806 | return bb; | |
807 | } | |
808 | ||
809 | /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control- | |
810 | dependent on. */ | |
811 | ||
812 | static hash_set<basic_block> * | |
813 | find_control_dep_blocks (struct loop *loop, basic_block bb) | |
814 | { | |
815 | /* BB has same control dependency as loop header, then it is not control- | |
816 | dependent on any basic block in LOOP. */ | |
817 | if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb)) | |
818 | return NULL; | |
819 | ||
820 | basic_block equiv_head = get_control_equiv_head_block (loop, bb); | |
821 | ||
822 | if (equiv_head->aux) | |
823 | { | |
824 | /* There is a basic block containing control dependency equivalent | |
825 | to BB. No need to recompute that, and also set this information | |
826 | to other equivalent basic blocks. */ | |
827 | for (; bb != equiv_head; | |
828 | bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
829 | bb->aux = equiv_head->aux; | |
830 | return (hash_set<basic_block> *) equiv_head->aux; | |
831 | } | |
832 | ||
833 | /* A basic block X is control-dependent on another Y iff there exists | |
834 | a path from X to Y, in which every basic block other than X and Y | |
835 | is post-dominated by Y, but X is not post-dominated by Y. | |
836 | ||
837 | According to this rule, traverse basic blocks in the loop backwards | |
838 | starting from BB, if a basic block is post-dominated by BB, extend | |
839 | current post-dominating path to this block, otherwise it is another | |
840 | one that BB is control-dependent on. */ | |
841 | ||
842 | auto_vec<basic_block> pdom_worklist; | |
843 | hash_set<basic_block> pdom_visited; | |
844 | hash_set<basic_block> *dep_bbs = new hash_set<basic_block>; | |
845 | ||
846 | pdom_worklist.safe_push (equiv_head); | |
847 | ||
848 | do | |
849 | { | |
850 | basic_block pdom_bb = pdom_worklist.pop (); | |
851 | edge_iterator ei; | |
852 | edge e; | |
853 | ||
854 | if (pdom_visited.add (pdom_bb)) | |
855 | continue; | |
856 | ||
857 | FOR_EACH_EDGE (e, ei, pdom_bb->preds) | |
858 | { | |
859 | basic_block pred_bb = e->src; | |
860 | ||
861 | if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb)) | |
862 | { | |
863 | dep_bbs->add (pred_bb); | |
864 | continue; | |
865 | } | |
866 | ||
867 | pred_bb = get_control_equiv_head_block (loop, pred_bb); | |
868 | ||
869 | if (pdom_visited.contains (pred_bb)) | |
870 | continue; | |
871 | ||
872 | if (!pred_bb->aux) | |
873 | { | |
874 | pdom_worklist.safe_push (pred_bb); | |
875 | continue; | |
876 | } | |
877 | ||
878 | /* If control dependency of basic block is available, fast extend | |
879 | post-dominating path using the information instead of advancing | |
880 | forward step-by-step. */ | |
881 | hash_set<basic_block> *pred_dep_bbs | |
882 | = (hash_set<basic_block> *) pred_bb->aux; | |
883 | ||
884 | for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin (); | |
885 | iter != pred_dep_bbs->end (); ++iter) | |
886 | { | |
887 | basic_block pred_dep_bb = *iter; | |
888 | ||
889 | /* Basic blocks can either be in control dependency of BB, or | |
890 | must be post-dominated by BB, if so, extend the path from | |
891 | these basic blocks. */ | |
892 | if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb)) | |
893 | dep_bbs->add (pred_dep_bb); | |
894 | else if (!pdom_visited.contains (pred_dep_bb)) | |
895 | pdom_worklist.safe_push (pred_dep_bb); | |
896 | } | |
897 | } | |
898 | } while (!pdom_worklist.is_empty ()); | |
899 | ||
900 | /* Record computed control dependencies in loop so that we can reach them | |
901 | when reclaiming resources. */ | |
902 | ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs); | |
903 | ||
904 | /* Associate control dependence with related equivalent basic blocks. */ | |
905 | for (equiv_head->aux = dep_bbs; bb != equiv_head; | |
906 | bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
907 | bb->aux = dep_bbs; | |
908 | ||
909 | return dep_bbs; | |
910 | } | |
911 | ||
912 | /* Forward declaration */ | |
913 | ||
914 | static bool | |
915 | stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt, | |
916 | const_basic_block skip_head, | |
917 | hash_map<gimple *, bool> &stmt_stat); | |
918 | ||
919 | /* Given STMT, memory load or pure call statement, check whether it is impacted | |
920 | by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the | |
921 | trace is composed of SKIP_HEAD and those basic block dominated by it, always | |
922 | corresponds to one branch of a conditional statement). If SKIP_HEAD is | |
923 | NULL, all basic blocks of LOOP are checked. */ | |
924 | ||
925 | static bool | |
926 | vuse_semi_invariant_p (struct loop *loop, gimple *stmt, | |
927 | const_basic_block skip_head) | |
928 | { | |
929 | split_info *info = (split_info *) loop->aux; | |
930 | tree rhs = NULL_TREE; | |
931 | ao_ref ref; | |
932 | gimple *store; | |
933 | unsigned i; | |
934 | ||
935 | /* Collect memory store/clobber statements if haven't done that. */ | |
936 | if (info->need_init) | |
937 | find_vdef_in_loop (loop); | |
938 | ||
939 | if (is_gimple_assign (stmt)) | |
940 | rhs = gimple_assign_rhs1 (stmt); | |
941 | ||
942 | ao_ref_init (&ref, rhs); | |
943 | ||
944 | FOR_EACH_VEC_ELT (info->memory_stores, i, store) | |
945 | { | |
946 | /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */ | |
947 | if (skip_head | |
948 | && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head)) | |
949 | continue; | |
950 | ||
951 | if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref)) | |
952 | return false; | |
953 | } | |
954 | ||
955 | return true; | |
956 | } | |
957 | ||
958 | /* Suppose one condition branch, led by SKIP_HEAD, is not executed since | |
959 | certain iteration of LOOP, check whether an SSA name (NAME) remains | |
960 | unchanged in next iteration. We call this characteristic semi- | |
961 | invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic | |
962 | blocks and control flows in the loop will be considered. Semi-invariant | |
963 | state of checked statement is cached in hash map STMT_STAT to avoid | |
964 | redundant computation in possible following re-check. */ | |
965 | ||
966 | static inline bool | |
967 | ssa_semi_invariant_p (struct loop *loop, tree name, | |
968 | const_basic_block skip_head, | |
969 | hash_map<gimple *, bool> &stmt_stat) | |
970 | { | |
971 | gimple *def = SSA_NAME_DEF_STMT (name); | |
972 | const_basic_block def_bb = gimple_bb (def); | |
973 | ||
974 | /* An SSA name defined outside loop is definitely semi-invariant. */ | |
975 | if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb)) | |
976 | return true; | |
977 | ||
5b2cc633 RB |
978 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) |
979 | return false; | |
980 | ||
095f78c6 FX |
981 | return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat); |
982 | } | |
983 | ||
984 | /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is | |
985 | semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), | |
986 | are excluded from LOOP. */ | |
987 | ||
988 | static bool | |
989 | loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi, | |
990 | const_basic_block skip_head) | |
991 | { | |
992 | const_edge latch = loop_latch_edge (loop); | |
993 | tree name = gimple_phi_result (loop_phi); | |
994 | tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch); | |
995 | ||
996 | gcc_checking_assert (from); | |
997 | ||
998 | /* Loop iteration PHI node locates in loop header, and it has two source | |
999 | operands, one is an initial value coming from outside the loop, the other | |
1000 | is a value through latch of the loop, which is derived in last iteration, | |
1001 | we call the latter latch value. From the PHI node to definition of latch | |
1002 | value, if excluding branch trace starting from SKIP_HEAD, except copy- | |
1003 | assignment or likewise, there is no other kind of value redefinition, SSA | |
1004 | name defined by the PHI node is semi-invariant. | |
1005 | ||
1006 | loop entry | |
1007 | | .--- latch ---. | |
1008 | | | | | |
1009 | v v | | |
1010 | x_1 = PHI <x_0, x_3> | | |
1011 | | | | |
1012 | v | | |
1013 | .------- if (cond) -------. | | |
1014 | | | | | |
1015 | | [ SKIP ] | | |
1016 | | | | | |
1017 | | x_2 = ... | | |
1018 | | | | | |
1019 | '---- T ---->.<---- F ----' | | |
1020 | | | | |
1021 | v | | |
1022 | x_3 = PHI <x_1, x_2> | | |
1023 | | | | |
1024 | '----------------------' | |
1025 | ||
1026 | Suppose in certain iteration, execution flow in above graph goes through | |
1027 | true branch, which means that one source value to define x_3 in false | |
1028 | branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next | |
1029 | iterations is defined by x_3, we know that x_1 will never changed if COND | |
1030 | always chooses true branch from then on. */ | |
1031 | ||
1032 | while (from != name) | |
1033 | { | |
1034 | /* A new value comes from a CONSTANT. */ | |
1035 | if (TREE_CODE (from) != SSA_NAME) | |
1036 | return false; | |
1037 | ||
1038 | gimple *stmt = SSA_NAME_DEF_STMT (from); | |
1039 | const_basic_block bb = gimple_bb (stmt); | |
1040 | ||
1041 | /* A new value comes from outside the loop. */ | |
1042 | if (!bb || !flow_bb_inside_loop_p (loop, bb)) | |
1043 | return false; | |
1044 | ||
1045 | from = NULL_TREE; | |
1046 | ||
1047 | if (gimple_code (stmt) == GIMPLE_PHI) | |
1048 | { | |
1049 | gphi *phi = as_a <gphi *> (stmt); | |
1050 | ||
1051 | for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
1052 | { | |
1053 | if (skip_head) | |
1054 | { | |
1055 | const_edge e = gimple_phi_arg_edge (phi, i); | |
1056 | ||
1057 | /* Don't consider redefinitions in excluded basic blocks. */ | |
1058 | if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head)) | |
1059 | continue; | |
1060 | } | |
1061 | ||
1062 | tree arg = gimple_phi_arg_def (phi, i); | |
1063 | ||
1064 | if (!from) | |
1065 | from = arg; | |
1066 | else if (!operand_equal_p (from, arg, 0)) | |
1067 | /* There are more than one source operands that provide | |
1068 | different values to the SSA name, it is variant. */ | |
1069 | return false; | |
1070 | } | |
1071 | } | |
1072 | else if (gimple_code (stmt) == GIMPLE_ASSIGN) | |
1073 | { | |
1074 | /* For simple value copy, check its rhs instead. */ | |
1075 | if (gimple_assign_ssa_name_copy_p (stmt)) | |
1076 | from = gimple_assign_rhs1 (stmt); | |
1077 | } | |
1078 | ||
1079 | /* Any other kind of definition is deemed to introduce a new value | |
1080 | to the SSA name. */ | |
1081 | if (!from) | |
1082 | return false; | |
1083 | } | |
1084 | return true; | |
1085 | } | |
1086 | ||
1087 | /* Check whether conditional predicates that BB is control-dependent on, are | |
1088 | semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), | |
1089 | are excluded from LOOP. Semi-invariant state of checked statement is cached | |
1090 | in hash map STMT_STAT. */ | |
1091 | ||
1092 | static bool | |
1093 | control_dep_semi_invariant_p (struct loop *loop, basic_block bb, | |
1094 | const_basic_block skip_head, | |
1095 | hash_map<gimple *, bool> &stmt_stat) | |
1096 | { | |
1097 | hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb); | |
1098 | ||
1099 | if (!dep_bbs) | |
1100 | return true; | |
1101 | ||
1102 | for (hash_set<basic_block>::iterator iter = dep_bbs->begin (); | |
1103 | iter != dep_bbs->end (); ++iter) | |
1104 | { | |
1105 | gimple *last = last_stmt (*iter); | |
1106 | ||
1107 | if (!last) | |
1108 | return false; | |
1109 | ||
1110 | /* Only check condition predicates. */ | |
1111 | if (gimple_code (last) != GIMPLE_COND | |
1112 | && gimple_code (last) != GIMPLE_SWITCH) | |
1113 | return false; | |
1114 | ||
1115 | if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat)) | |
1116 | return false; | |
1117 | } | |
1118 | ||
1119 | return true; | |
1120 | } | |
1121 | ||
1122 | /* Check whether STMT is semi-invariant in LOOP, iff all its operands are | |
1123 | semi-invariant, consequently, all its defined values are semi-invariant. | |
1124 | Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. | |
1125 | Semi-invariant state of checked statement is cached in hash map | |
1126 | STMT_STAT. */ | |
1127 | ||
1128 | static bool | |
1129 | stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt, | |
1130 | const_basic_block skip_head, | |
1131 | hash_map<gimple *, bool> &stmt_stat) | |
1132 | { | |
1133 | bool existed; | |
1134 | bool &invar = stmt_stat.get_or_insert (stmt, &existed); | |
1135 | ||
1136 | if (existed) | |
1137 | return invar; | |
1138 | ||
1139 | /* A statement might depend on itself, which is treated as variant. So set | |
1140 | state of statement under check to be variant to ensure that. */ | |
1141 | invar = false; | |
1142 | ||
1143 | if (gimple_code (stmt) == GIMPLE_PHI) | |
1144 | { | |
1145 | gphi *phi = as_a <gphi *> (stmt); | |
1146 | ||
1147 | if (gimple_bb (stmt) == loop->header) | |
1148 | { | |
2b2f3867 RB |
1149 | /* If the entry value is subject to abnormal coalescing |
1150 | avoid the transform since we're going to duplicate the | |
1151 | loop header and thus likely introduce overlapping life-ranges | |
1152 | between the PHI def and the entry on the path when the | |
1153 | first loop is skipped. */ | |
1154 | tree entry_def | |
1155 | = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |
1156 | if (TREE_CODE (entry_def) == SSA_NAME | |
1157 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (entry_def)) | |
1158 | return false; | |
095f78c6 FX |
1159 | invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head); |
1160 | return invar; | |
1161 | } | |
1162 | ||
1163 | /* For a loop PHI node that does not locate in loop header, it is semi- | |
1164 | invariant only if two conditions are met. The first is its source | |
1165 | values are derived from CONSTANT (including loop-invariant value), or | |
1166 | from SSA name defined by semi-invariant loop iteration PHI node. The | |
1167 | second is its source incoming edges are control-dependent on semi- | |
1168 | invariant conditional predicates. */ | |
1169 | for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
1170 | { | |
1171 | const_edge e = gimple_phi_arg_edge (phi, i); | |
1172 | tree arg = gimple_phi_arg_def (phi, i); | |
1173 | ||
1174 | if (TREE_CODE (arg) == SSA_NAME) | |
1175 | { | |
1176 | if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat)) | |
1177 | return false; | |
1178 | ||
1179 | /* If source value is defined in location from where the source | |
1180 | edge comes in, no need to check control dependency again | |
1181 | since this has been done in above SSA name check stage. */ | |
1182 | if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg))) | |
1183 | continue; | |
1184 | } | |
1185 | ||
1186 | if (!control_dep_semi_invariant_p (loop, e->src, skip_head, | |
1187 | stmt_stat)) | |
1188 | return false; | |
1189 | } | |
1190 | } | |
1191 | else | |
1192 | { | |
1193 | ssa_op_iter iter; | |
1194 | tree use; | |
1195 | ||
1196 | /* Volatile memory load or return of normal (non-const/non-pure) call | |
1197 | should not be treated as constant in each iteration of loop. */ | |
1198 | if (gimple_has_side_effects (stmt)) | |
1199 | return false; | |
1200 | ||
1201 | /* Check if any memory store may kill memory load at this place. */ | |
1202 | if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head)) | |
1203 | return false; | |
1204 | ||
1205 | /* Although operand of a statement might be SSA name, CONSTANT or | |
1206 | VARDECL, here we only need to check SSA name operands. This is | |
1207 | because check on VARDECL operands, which involve memory loads, | |
1208 | must have been done prior to invocation of this function in | |
1209 | vuse_semi_invariant_p. */ | |
1210 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
1211 | if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat)) | |
1212 | return false; | |
1213 | } | |
1214 | ||
1215 | if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head, | |
1216 | stmt_stat)) | |
1217 | return false; | |
1218 | ||
1219 | /* Here we SHOULD NOT use invar = true, since hash map might be changed due | |
1220 | to new insertion, and thus invar may point to invalid memory. */ | |
1221 | stmt_stat.put (stmt, true); | |
1222 | return true; | |
1223 | } | |
1224 | ||
1225 | /* A helper function to check whether STMT is semi-invariant in LOOP. Basic | |
1226 | blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */ | |
1227 | ||
1228 | static bool | |
1229 | stmt_semi_invariant_p (struct loop *loop, gimple *stmt, | |
1230 | const_basic_block skip_head) | |
1231 | { | |
1232 | hash_map<gimple *, bool> stmt_stat; | |
1233 | return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat); | |
1234 | } | |
1235 | ||
1236 | /* Determine when conditional statement never transfers execution to one of its | |
1237 | branch, whether we can remove the branch's leading basic block (BRANCH_BB) | |
1238 | and those basic blocks dominated by BRANCH_BB. */ | |
1239 | ||
1240 | static bool | |
1241 | branch_removable_p (basic_block branch_bb) | |
1242 | { | |
1243 | edge_iterator ei; | |
1244 | edge e; | |
1245 | ||
1246 | if (single_pred_p (branch_bb)) | |
1247 | return true; | |
1248 | ||
1249 | FOR_EACH_EDGE (e, ei, branch_bb->preds) | |
1250 | { | |
1251 | if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb)) | |
1252 | continue; | |
1253 | ||
1254 | if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src)) | |
1255 | continue; | |
1256 | ||
1257 | /* The branch can be reached from opposite branch, or from some | |
1258 | statement not dominated by the conditional statement. */ | |
1259 | return false; | |
1260 | } | |
1261 | ||
1262 | return true; | |
1263 | } | |
1264 | ||
1265 | /* Find out which branch of a conditional statement (COND) is invariant in the | |
1266 | execution context of LOOP. That is: once the branch is selected in certain | |
1267 | iteration of the loop, any operand that contributes to computation of the | |
1268 | conditional statement remains unchanged in all following iterations. */ | |
1269 | ||
1270 | static edge | |
1271 | get_cond_invariant_branch (struct loop *loop, gcond *cond) | |
1272 | { | |
1273 | basic_block cond_bb = gimple_bb (cond); | |
1274 | basic_block targ_bb[2]; | |
1275 | bool invar[2]; | |
1276 | unsigned invar_checks = 0; | |
1277 | ||
1278 | for (unsigned i = 0; i < 2; i++) | |
1279 | { | |
1280 | targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest; | |
1281 | ||
1282 | /* One branch directs to loop exit, no need to perform loop split upon | |
1283 | this conditional statement. Firstly, it is trivial if the exit branch | |
1284 | is semi-invariant, for the statement is just to break loop. Secondly, | |
1285 | if the opposite branch is semi-invariant, it means that the statement | |
1286 | is real loop-invariant, which is covered by loop unswitch. */ | |
1287 | if (!flow_bb_inside_loop_p (loop, targ_bb[i])) | |
1288 | return NULL; | |
1289 | } | |
1290 | ||
1291 | for (unsigned i = 0; i < 2; i++) | |
1292 | { | |
1293 | invar[!i] = false; | |
1294 | ||
1295 | if (!branch_removable_p (targ_bb[i])) | |
1296 | continue; | |
1297 | ||
1298 | /* Given a semi-invariant branch, if its opposite branch dominates | |
1299 | loop latch, it and its following trace will only be executed in | |
1300 | final iteration of loop, namely it is not part of repeated body | |
1301 | of the loop. Similar to the above case that the branch is loop | |
1302 | exit, no need to split loop. */ | |
1303 | if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i])) | |
1304 | continue; | |
1305 | ||
1306 | invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]); | |
1307 | invar_checks++; | |
1308 | } | |
1309 | ||
1310 | /* With both branches being invariant (handled by loop unswitch) or | |
1311 | variant is not what we want. */ | |
1312 | if (invar[0] ^ !invar[1]) | |
1313 | return NULL; | |
1314 | ||
1315 | /* Found a real loop-invariant condition, do nothing. */ | |
1316 | if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL)) | |
1317 | return NULL; | |
1318 | ||
1319 | return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1); | |
1320 | } | |
1321 | ||
1322 | /* Calculate increased code size measured by estimated insn number if applying | |
1323 | loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */ | |
1324 | ||
1325 | static int | |
1326 | compute_added_num_insns (struct loop *loop, const_edge branch_edge) | |
1327 | { | |
1328 | basic_block cond_bb = branch_edge->src; | |
1329 | unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge; | |
1330 | basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest; | |
1331 | basic_block *bbs = ((split_info *) loop->aux)->bbs; | |
1332 | int num = 0; | |
1333 | ||
1334 | for (unsigned i = 0; i < loop->num_nodes; i++) | |
1335 | { | |
1336 | /* Do no count basic blocks only in opposite branch. */ | |
1337 | if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb)) | |
1338 | continue; | |
1339 | ||
1340 | num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights); | |
1341 | } | |
1342 | ||
1343 | /* It is unnecessary to evaluate expression of the conditional statement | |
1344 | in new loop that contains only invariant branch. This expression should | |
1345 | be constant value (either true or false). Exclude code size of insns | |
1346 | that contribute to computation of the expression. */ | |
1347 | ||
1348 | auto_vec<gimple *> worklist; | |
1349 | hash_set<gimple *> removed; | |
1350 | gimple *stmt = last_stmt (cond_bb); | |
1351 | ||
1352 | worklist.safe_push (stmt); | |
1353 | removed.add (stmt); | |
1354 | num -= estimate_num_insns (stmt, &eni_size_weights); | |
1355 | ||
1356 | do | |
1357 | { | |
1358 | ssa_op_iter opnd_iter; | |
1359 | use_operand_p opnd_p; | |
1360 | ||
1361 | stmt = worklist.pop (); | |
1362 | FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE) | |
1363 | { | |
1364 | tree opnd = USE_FROM_PTR (opnd_p); | |
1365 | ||
1366 | if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd)) | |
1367 | continue; | |
1368 | ||
1369 | gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd); | |
1370 | use_operand_p use_p; | |
1371 | imm_use_iterator use_iter; | |
1372 | ||
1373 | if (removed.contains (opnd_stmt) | |
1374 | || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt))) | |
1375 | continue; | |
1376 | ||
1377 | FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd) | |
1378 | { | |
1379 | gimple *use_stmt = USE_STMT (use_p); | |
1380 | ||
1381 | if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt)) | |
1382 | { | |
1383 | opnd_stmt = NULL; | |
1384 | break; | |
1385 | } | |
1386 | } | |
1387 | ||
1388 | if (opnd_stmt) | |
1389 | { | |
1390 | worklist.safe_push (opnd_stmt); | |
1391 | removed.add (opnd_stmt); | |
1392 | num -= estimate_num_insns (opnd_stmt, &eni_size_weights); | |
1393 | } | |
1394 | } | |
1395 | } while (!worklist.is_empty ()); | |
1396 | ||
1397 | gcc_assert (num >= 0); | |
1398 | return num; | |
1399 | } | |
1400 | ||
1401 | /* Find out loop-invariant branch of a conditional statement (COND) if it has, | |
1402 | and check whether it is eligible and profitable to perform loop split upon | |
1403 | this branch in LOOP. */ | |
1404 | ||
1405 | static edge | |
1406 | get_cond_branch_to_split_loop (struct loop *loop, gcond *cond) | |
1407 | { | |
1408 | edge invar_branch = get_cond_invariant_branch (loop, cond); | |
1409 | if (!invar_branch) | |
1410 | return NULL; | |
1411 | ||
1412 | /* When accurate profile information is available, and execution | |
1413 | frequency of the branch is too low, just let it go. */ | |
1414 | profile_probability prob = invar_branch->probability; | |
1415 | if (prob.reliable_p ()) | |
1416 | { | |
028d4092 | 1417 | int thres = param_min_loop_cond_split_prob; |
095f78c6 FX |
1418 | |
1419 | if (prob < profile_probability::always ().apply_scale (thres, 100)) | |
1420 | return NULL; | |
1421 | } | |
1422 | ||
1423 | /* Add a threshold for increased code size to disable loop split. */ | |
028d4092 | 1424 | if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns) |
095f78c6 FX |
1425 | return NULL; |
1426 | ||
1427 | return invar_branch; | |
1428 | } | |
1429 | ||
1430 | /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some | |
1431 | conditional statement, perform loop split transformation illustrated | |
1432 | as the following graph. | |
1433 | ||
1434 | .-------T------ if (true) ------F------. | |
1435 | | .---------------. | | |
1436 | | | | | | |
1437 | v | v v | |
1438 | pre-header | pre-header | |
1439 | | .------------. | | .------------. | |
1440 | | | | | | | | | |
1441 | | v | | | v | | |
1442 | header | | header | | |
1443 | | | | | | | |
1444 | .--- if (cond) ---. | | .--- if (true) ---. | | |
1445 | | | | | | | | | |
1446 | invariant | | | invariant | | | |
1447 | | | | | | | | | |
1448 | '---T--->.<---F---' | | '---T--->.<---F---' | | |
1449 | | | / | | | |
1450 | stmts | / stmts | | |
1451 | | F T | | | |
1452 | / \ | / / \ | | |
1453 | .-------* * [ if (cond) ] .-------* * | | |
1454 | | | | | | | | |
1455 | | latch | | latch | | |
1456 | | | | | | | | |
1457 | | '------------' | '------------' | |
1458 | '------------------------. .-----------' | |
1459 | loop1 | | loop2 | |
1460 | v v | |
1461 | exits | |
1462 | ||
1463 | In the graph, loop1 represents the part derived from original one, and | |
1464 | loop2 is duplicated using loop_version (), which corresponds to the part | |
1465 | of original one being splitted out. In original latch edge of loop1, we | |
1466 | insert a new conditional statement duplicated from the semi-invariant cond, | |
1467 | and one of its branch goes back to loop1 header as a latch edge, and the | |
1468 | other branch goes to loop2 pre-header as an entry edge. And also in loop2, | |
1469 | we abandon the variant branch of the conditional statement by setting a | |
1470 | constant bool condition, based on which branch is semi-invariant. */ | |
1471 | ||
1472 | static bool | |
1473 | do_split_loop_on_cond (struct loop *loop1, edge invar_branch) | |
1474 | { | |
1475 | basic_block cond_bb = invar_branch->src; | |
1476 | bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE); | |
1477 | gcond *cond = as_a <gcond *> (last_stmt (cond_bb)); | |
1478 | ||
1479 | gcc_assert (cond_bb->loop_father == loop1); | |
1480 | ||
1481 | if (dump_enabled_p ()) | |
1482 | dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond, | |
1483 | "loop split on semi-invariant condition at %s branch\n", | |
1484 | true_invar ? "true" : "false"); | |
1485 | ||
1486 | initialize_original_copy_tables (); | |
1487 | ||
1488 | struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL, | |
1489 | profile_probability::always (), | |
1490 | profile_probability::never (), | |
1491 | profile_probability::always (), | |
1492 | profile_probability::always (), | |
1493 | true); | |
1494 | if (!loop2) | |
1495 | { | |
1496 | free_original_copy_tables (); | |
1497 | return false; | |
1498 | } | |
1499 | ||
1500 | basic_block cond_bb_copy = get_bb_copy (cond_bb); | |
1501 | gcond *cond_copy = as_a<gcond *> (last_stmt (cond_bb_copy)); | |
1502 | ||
1503 | /* Replace the condition in loop2 with a bool constant to let PassManager | |
1504 | remove the variant branch after current pass completes. */ | |
1505 | if (true_invar) | |
1506 | gimple_cond_make_true (cond_copy); | |
1507 | else | |
1508 | gimple_cond_make_false (cond_copy); | |
1509 | ||
1510 | update_stmt (cond_copy); | |
1511 | ||
1512 | /* Insert a new conditional statement on latch edge of loop1, its condition | |
1513 | is duplicated from the semi-invariant. This statement acts as a switch | |
1514 | to transfer execution from loop1 to loop2, when loop1 enters into | |
1515 | invariant state. */ | |
1516 | basic_block latch_bb = split_edge (loop_latch_edge (loop1)); | |
1517 | basic_block break_bb = split_edge (single_pred_edge (latch_bb)); | |
1518 | gimple *break_cond = gimple_build_cond (gimple_cond_code(cond), | |
1519 | gimple_cond_lhs (cond), | |
1520 | gimple_cond_rhs (cond), | |
1521 | NULL_TREE, NULL_TREE); | |
1522 | ||
1523 | gimple_stmt_iterator gsi = gsi_last_bb (break_bb); | |
1524 | gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT); | |
1525 | ||
1526 | edge to_loop1 = single_succ_edge (break_bb); | |
1527 | edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0); | |
1528 | ||
1529 | to_loop1->flags &= ~EDGE_FALLTHRU; | |
1530 | to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE; | |
1531 | to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE; | |
1532 | ||
095f78c6 FX |
1533 | /* Due to introduction of a control flow edge from loop1 latch to loop2 |
1534 | pre-header, we should update PHIs in loop2 to reflect this connection | |
1535 | between loop1 and loop2. */ | |
1536 | connect_loop_phis (loop1, loop2, to_loop2); | |
1537 | ||
1538 | free_original_copy_tables (); | |
1539 | ||
095f78c6 FX |
1540 | return true; |
1541 | } | |
1542 | ||
1543 | /* Traverse all conditional statements in LOOP, to find out a good candidate | |
1544 | upon which we can do loop split. */ | |
1545 | ||
1546 | static bool | |
1547 | split_loop_on_cond (struct loop *loop) | |
1548 | { | |
1549 | split_info *info = new split_info (); | |
1550 | basic_block *bbs = info->bbs = get_loop_body (loop); | |
1551 | bool do_split = false; | |
1552 | ||
1553 | /* Allocate an area to keep temporary info, and associate its address | |
1554 | with loop aux field. */ | |
1555 | loop->aux = info; | |
1556 | ||
1557 | for (unsigned i = 0; i < loop->num_nodes; i++) | |
1558 | bbs[i]->aux = NULL; | |
1559 | ||
1560 | for (unsigned i = 0; i < loop->num_nodes; i++) | |
1561 | { | |
1562 | basic_block bb = bbs[i]; | |
1563 | ||
1564 | /* We only consider conditional statement, which be executed at most once | |
1565 | in each iteration of the loop. So skip statements in inner loops. */ | |
1566 | if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP)) | |
1567 | continue; | |
1568 | ||
1569 | /* Actually this check is not a must constraint. With it, we can ensure | |
1570 | conditional statement will always be executed in each iteration. */ | |
1571 | if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) | |
1572 | continue; | |
1573 | ||
1574 | gimple *last = last_stmt (bb); | |
1575 | ||
1576 | if (!last || gimple_code (last) != GIMPLE_COND) | |
1577 | continue; | |
1578 | ||
1579 | gcond *cond = as_a <gcond *> (last); | |
1580 | edge branch_edge = get_cond_branch_to_split_loop (loop, cond); | |
1581 | ||
1582 | if (branch_edge) | |
1583 | { | |
1584 | do_split_loop_on_cond (loop, branch_edge); | |
1585 | do_split = true; | |
1586 | break; | |
1587 | } | |
1588 | } | |
1589 | ||
1590 | delete info; | |
1591 | loop->aux = NULL; | |
1592 | ||
1593 | return do_split; | |
1594 | } | |
1595 | ||
28df8730 MM |
1596 | /* Main entry point. Perform loop splitting on all suitable loops. */ |
1597 | ||
1598 | static unsigned int | |
1599 | tree_ssa_split_loops (void) | |
1600 | { | |
28df8730 MM |
1601 | bool changed = false; |
1602 | ||
1603 | gcc_assert (scev_initialized_p ()); | |
095f78c6 FX |
1604 | |
1605 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
1606 | ||
e41ba804 | 1607 | for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT)) |
28df8730 MM |
1608 | loop->aux = NULL; |
1609 | ||
1610 | /* Go through all loops starting from innermost. */ | |
e41ba804 | 1611 | for (auto loop : loops_list (cfun, LI_FROM_INNERMOST)) |
28df8730 | 1612 | { |
28df8730 MM |
1613 | if (loop->aux) |
1614 | { | |
1615 | /* If any of our inner loops was split, don't split us, | |
1616 | and mark our containing loop as having had splits as well. */ | |
1617 | loop_outer (loop)->aux = loop; | |
1618 | continue; | |
1619 | } | |
1620 | ||
095f78c6 FX |
1621 | if (optimize_loop_for_size_p (loop)) |
1622 | continue; | |
1623 | ||
1624 | if (split_loop (loop) || split_loop_on_cond (loop)) | |
28df8730 | 1625 | { |
095f78c6 FX |
1626 | /* Mark our containing loop as having had some split inner loops. */ |
1627 | loop_outer (loop)->aux = loop; | |
1628 | changed = true; | |
28df8730 MM |
1629 | } |
1630 | } | |
1631 | ||
e41ba804 | 1632 | for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT)) |
28df8730 MM |
1633 | loop->aux = NULL; |
1634 | ||
095f78c6 FX |
1635 | clear_aux_for_blocks (); |
1636 | ||
1637 | free_dominance_info (CDI_POST_DOMINATORS); | |
1638 | ||
28df8730 | 1639 | if (changed) |
a1ac9ffb RB |
1640 | { |
1641 | rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); | |
1642 | return TODO_cleanup_cfg; | |
1643 | } | |
28df8730 MM |
1644 | return 0; |
1645 | } | |
1646 | ||
1647 | /* Loop splitting pass. */ | |
1648 | ||
1649 | namespace { | |
1650 | ||
1651 | const pass_data pass_data_loop_split = | |
1652 | { | |
1653 | GIMPLE_PASS, /* type */ | |
1654 | "lsplit", /* name */ | |
1655 | OPTGROUP_LOOP, /* optinfo_flags */ | |
1656 | TV_LOOP_SPLIT, /* tv_id */ | |
1657 | PROP_cfg, /* properties_required */ | |
1658 | 0, /* properties_provided */ | |
1659 | 0, /* properties_destroyed */ | |
1660 | 0, /* todo_flags_start */ | |
1661 | 0, /* todo_flags_finish */ | |
1662 | }; | |
1663 | ||
1664 | class pass_loop_split : public gimple_opt_pass | |
1665 | { | |
1666 | public: | |
1667 | pass_loop_split (gcc::context *ctxt) | |
1668 | : gimple_opt_pass (pass_data_loop_split, ctxt) | |
1669 | {} | |
1670 | ||
1671 | /* opt_pass methods: */ | |
1672 | virtual bool gate (function *) { return flag_split_loops != 0; } | |
1673 | virtual unsigned int execute (function *); | |
1674 | ||
1675 | }; // class pass_loop_split | |
1676 | ||
1677 | unsigned int | |
1678 | pass_loop_split::execute (function *fun) | |
1679 | { | |
1680 | if (number_of_loops (fun) <= 1) | |
1681 | return 0; | |
1682 | ||
1683 | return tree_ssa_split_loops (); | |
1684 | } | |
1685 | ||
1686 | } // anon namespace | |
1687 | ||
1688 | gimple_opt_pass * | |
1689 | make_pass_loop_split (gcc::context *ctxt) | |
1690 | { | |
1691 | return new pass_loop_split (ctxt); | |
1692 | } |