Line data Source code
1 : /* Loop header copying on trees.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it
7 : under the terms of the GNU General Public License as published by the
8 : Free Software Foundation; either version 3, or (at your option) any
9 : later version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "tree.h"
25 : #include "gimple.h"
26 : #include "cfghooks.h"
27 : #include "tree-pass.h"
28 : #include "gimple-ssa.h"
29 : #include "gimple-iterator.h"
30 : #include "tree-cfg.h"
31 : #include "tree-into-ssa.h"
32 : #include "cfgloop.h"
33 : #include "tree-inline.h"
34 : #include "tree-ssa-threadedge.h"
35 : #include "tree-ssa-sccvn.h"
36 : #include "tree-phinodes.h"
37 : #include "ssa-iterators.h"
38 : #include "value-range.h"
39 : #include "gimple-range.h"
40 : #include "gimple-range-path.h"
41 : #include "gimple-pretty-print.h"
42 : #include "cfganal.h"
43 : #include "tree-ssa-loop-manip.h"
44 : #include "tree-ssa-loop-niter.h"
45 : #include "tree-scalar-evolution.h"
46 :
47 : /* Return path query instance for testing ranges of statements
48 : in headers of LOOP contained in basic block BB.
49 : Use RANGER instance. */
50 :
51 : static path_range_query *
52 808983 : get_range_query (class loop *loop,
53 : basic_block bb,
54 : gimple_ranger &ranger)
55 : {
56 808983 : auto_vec<basic_block, 8> path;
57 1039720 : for (; bb != loop->header; bb = single_pred_edge (bb)->src)
58 230737 : path.safe_push (bb);
59 808983 : path.safe_push (loop->header);
60 808983 : path.safe_push (loop_preheader_edge (loop)->src);
61 808983 : return new path_range_query (ranger, path);
62 808983 : }
63 :
64 : /* Return edge that is true in the first iteration of the loop
65 : and NULL otherwise.
66 : Formulate corrent ranger query to RANGER. */
67 :
68 : static edge
69 765743 : static_loop_exit (class loop *l, basic_block bb, gimple_ranger &ranger,
70 : path_range_query *&query)
71 : {
72 1531486 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
73 765743 : edge ret_e;
74 :
75 765743 : if (!last)
76 : return NULL;
77 :
78 765743 : edge true_e, false_e;
79 765743 : extract_true_false_edges_from_block (bb, &true_e, &false_e);
80 :
81 : /* If neither edge is the exit edge, this is not a case we'd like to
82 : special-case. */
83 765743 : if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e))
84 : return NULL;
85 :
86 765743 : int_range<1> desired_static_range;
87 765743 : if (loop_exit_edge_p (l, true_e))
88 : {
89 247445 : desired_static_range = range_false ();
90 247445 : ret_e = true_e;
91 : }
92 : else
93 : {
94 518298 : desired_static_range = range_true ();
95 518298 : ret_e = false_e;
96 : }
97 :
98 765743 : if (!query)
99 95199 : query = get_range_query (l, gimple_bb (last), ranger);
100 :
101 765743 : int_range<2> r;
102 765743 : if (!query->range_of_stmt (r, last))
103 : return NULL;
104 765743 : return r == desired_static_range ? ret_e : NULL;
105 765743 : }
106 :
107 : /* Return true if STMT is static in LOOP. This means that its value
108 : is constant in the first iteration.
109 : Use RANGER and formulate query cached in QUERY. */
110 :
111 : static bool
112 1373530 : loop_static_stmt_p (class loop *loop,
113 : gimple_ranger &ranger,
114 : path_range_query *&query,
115 : gimple *stmt)
116 : {
117 1373530 : tree type = gimple_range_type (stmt);
118 1373530 : if (!type || !value_range::supports_type_p (type))
119 : return false;
120 :
121 1366418 : if (!query)
122 713784 : query = get_range_query (loop, gimple_bb (stmt), ranger);
123 :
124 1366418 : value_range r (gimple_range_type (stmt));
125 1366418 : if (!query->range_of_stmt (r, stmt))
126 : return false;
127 1366418 : return r.singleton_p ();
128 1366418 : }
129 :
130 : /* Return true if OP is invariant. */
131 :
132 : static bool
133 2175761 : loop_invariant_op_p (class loop *loop,
134 : tree op)
135 : {
136 2175761 : if (is_gimple_min_invariant (op))
137 : return true;
138 1700512 : if (SSA_NAME_IS_DEFAULT_DEF (op)
139 1700512 : || !flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (op))))
140 : return true;
141 1407563 : return gimple_uid (SSA_NAME_DEF_STMT (op)) & 1;
142 : }
143 :
144 : /* Return true if OP combines outcome of static and
145 : loop invariant conditional. */
146 :
147 : static bool
148 16987 : loop_static_op_p (class loop *loop, tree op)
149 : {
150 : /* Always check for invariant first. */
151 33974 : gcc_checking_assert (!is_gimple_min_invariant (op)
152 : && !SSA_NAME_IS_DEFAULT_DEF (op)
153 : && flow_bb_inside_loop_p (loop,
154 : gimple_bb (SSA_NAME_DEF_STMT (op))));
155 16987 : return gimple_uid (SSA_NAME_DEF_STMT (op)) & 2;
156 : }
157 :
158 :
159 : /* Return true if OP combines outcome of static and
160 : loop invariant conditional. */
161 :
162 : static bool
163 690594 : loop_combined_static_and_iv_p (class loop *loop,
164 : tree op)
165 : {
166 : /* Always check for invariant first. */
167 1381188 : gcc_checking_assert (!is_gimple_min_invariant (op)
168 : && !SSA_NAME_IS_DEFAULT_DEF (op)
169 : && flow_bb_inside_loop_p (loop,
170 : gimple_bb (SSA_NAME_DEF_STMT (op))));
171 690594 : return gimple_uid (SSA_NAME_DEF_STMT (op)) & 4;
172 : }
173 :
174 : /* Decision about possibility of copying a given header. */
175 :
176 : enum ch_decision
177 : {
178 : /* We do not want to copy this header. */
179 : ch_impossible,
180 : /* We can copy it if it enables wins. */
181 : ch_possible,
182 : /* We can "copy" it if it enables wins and doing
183 : so will introduce no new code. */
184 : ch_possible_zero_cost,
185 : /* We want to copy. */
186 : ch_win,
187 : /* We want to copy and we will eliminate loop exit. */
188 : ch_win_invariant_exit,
189 :
190 : };
191 :
192 : /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
193 : instructions should be duplicated, limit is decreased by the actual
194 : amount. In the case of *CANBE_NEVEREXECUTED, if there is a exit edge
195 : of the HEADER that is most likely never executed then consider that
196 : as invariant and continue. Set *CANBE_NEVEREXECUTED to false otherwise. */
197 :
198 : static ch_decision
199 1486917 : should_duplicate_loop_header_p (basic_block header, class loop *loop,
200 : gimple_ranger *ranger,
201 : int *limit,
202 : hash_set <edge> *invariant_exits,
203 : hash_set <edge> *static_exits,
204 : bool *canbe_neverexecuted)
205 : {
206 1486917 : gimple_stmt_iterator bsi;
207 :
208 1486917 : gcc_assert (!header->aux);
209 :
210 1486917 : gcc_assert (EDGE_COUNT (header->succs) > 0);
211 1486917 : if (single_succ_p (header))
212 : {
213 453664 : if (dump_file && (dump_flags & TDF_DETAILS))
214 19 : fprintf (dump_file,
215 : " Not duplicating bb %i: it is single succ.\n",
216 : header->index);
217 : return ch_impossible;
218 : }
219 :
220 1033253 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
221 1033253 : && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
222 : {
223 148047 : if (dump_file && (dump_flags & TDF_DETAILS))
224 2 : fprintf (dump_file,
225 : " Not duplicating bb %i: both successors are in loop.\n",
226 : loop->num);
227 : return ch_impossible;
228 : }
229 :
230 : /* If this is not the original loop header, we want it to have just
231 : one predecessor in order to match the && pattern. */
232 1079383 : if (header != loop->header && !single_pred_p (header))
233 : {
234 0 : if (dump_file && (dump_flags & TDF_DETAILS))
235 0 : fprintf (dump_file,
236 : " Not duplicating bb %i: it has multiple predecestors.\n",
237 : header->index);
238 : return ch_impossible;
239 : }
240 :
241 1770412 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
242 885206 : if (!last)
243 : {
244 50841 : if (dump_file && (dump_flags & TDF_DETAILS))
245 0 : fprintf (dump_file,
246 : " Not duplicating bb %i: it does not end by conditional.\n",
247 : header->index);
248 : return ch_impossible;
249 : }
250 :
251 834365 : path_range_query *query = NULL;
252 2174039 : for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
253 1339674 : gsi_next (&psi))
254 2679348 : if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
255 : {
256 1825580 : bool static_p = loop_static_stmt_p (loop, *ranger,
257 912790 : query, psi.phi ());
258 1825580 : gimple_set_uid (psi.phi (), static_p ? 2 : 0);
259 : }
260 834365 : bool code_size_cost = false;
261 :
262 : /* Count number of instructions and punt on calls.
263 : Populate stmts INV flag to later apply heuristics to the
264 : kind of conditions we want to copy. */
265 4167590 : for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
266 : {
267 3333225 : gimple *last = gsi_stmt (bsi);
268 :
269 3333225 : if (gimple_code (last) == GIMPLE_LABEL)
270 11785 : continue;
271 :
272 3321440 : if (is_gimple_debug (last))
273 1619666 : continue;
274 :
275 1701774 : if (gimple_code (last) == GIMPLE_COND)
276 : break;
277 :
278 935972 : if (dump_file && (dump_flags & TDF_DETAILS))
279 : {
280 52 : fprintf (dump_file, " Analyzing: ");
281 52 : print_gimple_stmt (dump_file, last, 0, TDF_SLIM);
282 : }
283 :
284 935972 : if (gimple_code (last) == GIMPLE_CALL
285 935972 : && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
286 : /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
287 : at current loop's header. Don't copy in this case. */
288 6082 : || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
289 : {
290 50125 : if (dump_file && (dump_flags & TDF_DETAILS))
291 0 : fprintf (dump_file,
292 : " Not duplicating bb %i: it contains call.\n",
293 : header->index);
294 50125 : if (query)
295 35096 : delete query;
296 : return ch_impossible;
297 : }
298 :
299 : /* Classify the stmt is invariant in the loop. */
300 885847 : gimple_set_uid (last, 0);
301 1364381 : if (!gimple_vuse (last)
302 478534 : && gimple_code (last) != GIMPLE_ASM
303 1364305 : && (gimple_code (last) != GIMPLE_CALL
304 546 : || gimple_call_flags (last) & ECF_CONST))
305 : {
306 478346 : bool inv = true, static_p = false;
307 478346 : ssa_op_iter i;
308 478346 : tree op;
309 1104674 : FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
310 626328 : if (!loop_invariant_op_p (loop, op))
311 525192 : inv = false;
312 : /* Assume that code is reasonably optimized and invariant
313 : constants are already identified. */
314 478346 : if (!inv)
315 460740 : static_p = loop_static_stmt_p (loop, *ranger, query, last);
316 893195 : gimple_set_uid (last, (inv ? 1 : 0) | (static_p ? 2 : 0));
317 478346 : if (dump_file && (dump_flags & TDF_DETAILS))
318 : {
319 35 : if (inv)
320 6 : fprintf (dump_file, " Stmt is loop invariant\n");
321 35 : if (static_p)
322 3 : fprintf (dump_file, " Stmt is static "
323 : "(constant in the first iteration)\n");
324 : }
325 : /* Loop invariants will be optimized out in loop body after
326 : duplication; do not account invariant computation in code
327 : size costs.
328 :
329 : Similarly static computations will be optimized out in the
330 : duplicated header. */
331 478346 : if (inv || static_p)
332 81187 : continue;
333 :
334 : /* Match the following:
335 : _1 = i_1 < 10 <- static condition
336 : _2 = n != 0 <- loop invariant condition
337 : _3 = _1 & _2 <- combined static and iv statement. */
338 397243 : tree_code code;
339 397243 : if (gimple_code (last) == GIMPLE_ASSIGN
340 397243 : && ((code = gimple_assign_rhs_code (last)) == BIT_AND_EXPR
341 384746 : || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR))
342 : {
343 15665 : tree op1 = gimple_assign_rhs1 (last);
344 15665 : tree op2 = gimple_assign_rhs2 (last);
345 :
346 15665 : if ((loop_invariant_op_p (loop, op1)
347 14864 : || loop_combined_static_and_iv_p (loop, op1)
348 14862 : || loop_static_op_p (loop, op1))
349 17028 : && (loop_invariant_op_p (loop, op2)
350 2125 : || loop_combined_static_and_iv_p (loop, op2)
351 2125 : || loop_static_op_p (loop, op2)))
352 : {
353 : /* Duplicating loop header with combned conditional will
354 : remove this statement in each copy. But we account for
355 : that later when seeing that condition.
356 :
357 : Note that this may be overly optimistic for bit operations
358 : where the static parameter may still result in non-trivial
359 : bit operation. */
360 84 : gimple_set_uid (last, 4);
361 84 : if (dump_file && (dump_flags & TDF_DETAILS))
362 1 : fprintf (dump_file,
363 : " Stmt combines static and invariant op\n");
364 84 : continue;
365 : }
366 : }
367 : }
368 :
369 804660 : int insns = estimate_num_insns (last, &eni_size_weights);
370 804660 : *limit -= insns;
371 804660 : if (insns)
372 687756 : code_size_cost = true;
373 804660 : if (dump_file && (dump_flags & TDF_DETAILS))
374 42 : fprintf (dump_file,
375 : " Accounting stmt as %i insns\n", insns);
376 804660 : if (*limit < 0)
377 : {
378 18438 : if (dump_file && (dump_flags & TDF_DETAILS))
379 0 : fprintf (dump_file,
380 : " Not duplicating bb %i contains too many insns.\n",
381 : header->index);
382 18438 : if (query)
383 8085 : delete query;
384 : return ch_impossible;
385 : }
386 : }
387 :
388 765802 : if (dump_file && (dump_flags & TDF_DETAILS))
389 : {
390 34 : fprintf (dump_file, " Analyzing: ");
391 34 : print_gimple_stmt (dump_file, last, 0, TDF_SLIM);
392 : }
393 :
394 : /* If the condition tests a non-IV loop variant we do not want to rotate
395 : the loop further. Unless this is the original loop header. */
396 765802 : tree lhs = gimple_cond_lhs (last);
397 765802 : tree rhs = gimple_cond_rhs (last);
398 765802 : bool lhs_invariant = loop_invariant_op_p (loop, lhs);
399 765802 : bool rhs_invariant = loop_invariant_op_p (loop, rhs);
400 :
401 : /* Combined conditional is a result of if combining:
402 :
403 : _1 = i_1 < 10 <- static condition
404 : _2 = n != 0 <- loop invariant condition
405 : _3 = _1 & _2 <- combined static and iv statement
406 : if (_3 != 0) <- combined conditional
407 :
408 : Combined conditionals will not be optimized out in either copy.
409 : However duplicaed header simplifies to:
410 :
411 : if (n < 10)
412 :
413 : while loop body to
414 :
415 : if (i_1 < 10)
416 :
417 : So effectively the resulting code sequence will be of same length as
418 : the original code.
419 :
420 : Combined conditionals are never static or invariant, so save some work
421 : below. */
422 765802 : if (lhs_invariant != rhs_invariant
423 673605 : && (lhs_invariant
424 571253 : || loop_combined_static_and_iv_p (loop, lhs))
425 868213 : && (rhs_invariant
426 102352 : || loop_combined_static_and_iv_p (loop, rhs)))
427 : {
428 59 : if (query)
429 59 : delete query;
430 59 : if (dump_file && (dump_flags & TDF_DETAILS))
431 1 : fprintf (dump_file,
432 : " Conditional combines static and invariant op.\n");
433 : return ch_win;
434 : }
435 :
436 765743 : edge static_exit = static_loop_exit (loop, header, *ranger, query);
437 765743 : if (query)
438 765743 : delete query;
439 :
440 765743 : if (static_exit && static_exits)
441 : {
442 330911 : static_exits->add (static_exit);
443 330911 : if (dump_file && (dump_flags & TDF_DETAILS))
444 5 : fprintf (dump_file,
445 : " Will eliminate peeled conditional in bb %d.\n",
446 5 : static_exit->src->index);
447 : /* Still look for invariant exits; exit may be both. */
448 : }
449 765743 : if (lhs_invariant && rhs_invariant)
450 : {
451 4656 : if (invariant_exits)
452 : {
453 4656 : edge e;
454 4656 : edge_iterator ei;
455 13968 : FOR_EACH_EDGE (e, ei, header->succs)
456 9312 : if (loop_exit_edge_p (loop, e))
457 : {
458 4656 : if (dump_file && (dump_flags & TDF_DETAILS))
459 4 : fprintf (dump_file,
460 : " Will eliminate invariant exit %i->%i\n",
461 4 : e->src->index, e->dest->index);
462 4656 : invariant_exits->add (e);
463 : }
464 : }
465 : return ch_win_invariant_exit;
466 : }
467 761087 : if (!static_exit && *canbe_neverexecuted)
468 : {
469 : /* See if one of the edges are an exit edge that is probable
470 : never executed.
471 : If so treat it as invariant exit win. */
472 291286 : edge e;
473 291286 : edge_iterator ei;
474 291286 : bool hasone = false;
475 873858 : FOR_EACH_EDGE (e, ei, header->succs)
476 582572 : if (loop_exit_edge_p (loop, e)
477 582572 : && probably_never_executed_edge_p (cfun, e))
478 : {
479 6579 : hasone = true;
480 6579 : if (dump_file && (dump_flags & TDF_DETAILS))
481 5 : fprintf (dump_file,
482 : " `never executed` exit %i->%i\n",
483 5 : e->src->index, e->dest->index);
484 : }
485 291286 : if (hasone)
486 6579 : return ch_win_invariant_exit;
487 : }
488 754508 : *canbe_neverexecuted = false;
489 :
490 : /* If the static exit fully optimize out, it is win to "duplicate"
491 : it.
492 :
493 : TODO: Even if duplication costs some size we may opt to do so in case
494 : exit probability is significant enough (do partial peeling). */
495 754508 : if (static_exit)
496 330543 : return !code_size_cost ? ch_possible_zero_cost : ch_possible;
497 :
498 : /* We was not able to prove that conditional will be eliminated. */
499 423965 : int insns = estimate_num_insns (last, &eni_size_weights);
500 423965 : *limit -= insns;
501 423965 : if (dump_file && (dump_flags & TDF_DETAILS))
502 19 : fprintf (dump_file,
503 : " Accounting stmt as %i insns\n", insns);
504 423965 : if (*limit < 0)
505 : {
506 11013 : if (dump_file && (dump_flags & TDF_DETAILS))
507 0 : fprintf (dump_file,
508 : " Not duplicating bb %i contains too many insns.\n",
509 : header->index);
510 : return ch_impossible;
511 : }
512 :
513 : return ch_possible;
514 : }
515 :
516 : /* Checks whether LOOP is a do-while style loop. */
517 :
518 : static bool
519 897970 : do_while_loop_p (class loop *loop)
520 : {
521 897970 : gimple *stmt = last_nondebug_stmt (loop->latch);
522 :
523 : /* If the latch of the loop is not empty, it is not a do-while loop. */
524 897970 : if (stmt
525 897970 : && gimple_code (stmt) != GIMPLE_LABEL)
526 : {
527 574776 : if (dump_file && (dump_flags & TDF_DETAILS))
528 10 : fprintf (dump_file,
529 : "Loop %i is not do-while loop: latch is not empty.\n",
530 : loop->num);
531 : return false;
532 : }
533 :
534 : /* If the latch does not have a single predecessor, it is not a
535 : do-while loop. */
536 323194 : if (!single_pred_p (loop->latch))
537 : {
538 23745 : if (dump_file && (dump_flags & TDF_DETAILS))
539 1 : fprintf (dump_file,
540 : "Loop %i is not do-while loop: latch has multiple "
541 : "predecessors.\n", loop->num);
542 : return false;
543 : }
544 299449 : basic_block pred = single_pred (loop->latch);
545 :
546 : /* If the latch predecessor doesn't exit the loop, it is not a
547 : do-while loop. */
548 299449 : if (!loop_exits_from_bb_p (loop, pred))
549 : {
550 6231 : if (dump_file && (dump_flags & TDF_DETAILS))
551 0 : fprintf (dump_file,
552 : "Loop %i is not do-while loop: latch predecessor "
553 : "does not exit loop.\n", loop->num);
554 : return false;
555 : }
556 586436 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
557 292318 : if (last
558 292318 : && (gimple_cond_lhs (last) == boolean_false_node
559 292318 : || gimple_cond_lhs (last) == boolean_true_node)
560 1 : && gimple_cond_rhs (last) == boolean_false_node)
561 : {
562 1 : if (dump_file && (dump_flags & TDF_DETAILS))
563 1 : fprintf (dump_file,
564 : "Loop %i is not do-while loop: latch predecessor "
565 : "contains exit we optimized out.\n", loop->num);
566 : return false;
567 : }
568 :
569 293217 : if (dump_file && (dump_flags & TDF_DETAILS))
570 19 : fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
571 :
572 : return true;
573 : }
574 :
575 : /* Update profile after header copying of LOOP.
576 : REGION is the original (in loop) sequence, REGION_COPY is the
577 : duplicated header (now outside of loop). N_REGION is number of
578 : bbs duplicated.
579 : ELIMINATED_EDGE is edge to be removed from duplicated sequence.
580 : INVARIANT_EXITS are edges in the loop body to be elimianted
581 : since they are loop invariants
582 :
583 : So We expect the following:
584 :
585 : // region_copy_start entry will be scaled to entry_count
586 : if (cond1) <- this condition will become false
587 : and we update probabilities
588 : goto loop_exit;
589 : if (cond2) <- this condition is loop invariant
590 : goto loop_exit;
591 : goto loop_header <- this will be redirected to loop.
592 : // region_copy_end
593 : loop:
594 : <body>
595 : // region start
596 : loop_header:
597 : if (cond1) <- we need to update probability here
598 : goto loop_exit;
599 : if (cond2) <- and determine scaling factor here.
600 : moreover cond2 is now always true
601 : goto loop_exit;
602 : else
603 : goto loop;
604 : // region end
605 :
606 : Adding support for more exits can be done similarly,
607 : but only consumer so far is tree-ssa-loop-ch and it uses only this
608 : to handle the common case of peeling headers which have
609 : conditionals known to be always true upon entry. */
610 :
611 : static void
612 577254 : update_profile_after_ch (class loop *loop,
613 : basic_block *region, basic_block *region_copy,
614 : unsigned n_region,
615 : hash_set <edge> *invariant_exits,
616 : hash_set <edge> *static_exits,
617 : profile_count entry_count)
618 : {
619 1164210 : for (unsigned int i = 0; i < n_region; i++)
620 : {
621 586956 : edge exit_e, exit_e_copy, e, e_copy;
622 586956 : if (EDGE_COUNT (region[i]->succs) == 1)
623 : {
624 0 : region_copy[i]->count = entry_count;
625 0 : region[i]->count -= entry_count;
626 0 : continue;
627 : }
628 :
629 586956 : gcc_checking_assert (EDGE_COUNT (region[i]->succs) == 2);
630 586956 : if (loop_exit_edge_p (loop,
631 586956 : EDGE_SUCC (region[i], 0)))
632 : {
633 139413 : exit_e = EDGE_SUCC (region[i], 0);
634 139413 : exit_e_copy = EDGE_SUCC (region_copy[i], 0);
635 139413 : e = EDGE_SUCC (region[i], 1);
636 139413 : e_copy = EDGE_SUCC (region_copy[i], 1);
637 : }
638 : else
639 : {
640 447543 : exit_e = EDGE_SUCC (region[i], 1);
641 447543 : exit_e_copy = EDGE_SUCC (region_copy[i], 1);
642 447543 : e = EDGE_SUCC (region[i], 0);
643 447543 : e_copy = EDGE_SUCC (region_copy[i], 0);
644 : }
645 586956 : gcc_assert (i == n_region - 1
646 : || (e->dest == region[i + 1]
647 : && e_copy->dest == region_copy[i + 1]));
648 586956 : region_copy[i]->count = entry_count;
649 586956 : profile_count exit_e_count = exit_e->count ();
650 586956 : bool was_static = false;
651 586956 : if (static_exits->contains (exit_e))
652 : {
653 : /* Update profile and the conditional.
654 : CFG update is done by caller. */
655 323402 : static_exits->remove (exit_e);
656 323402 : was_static = true;
657 323402 : e_copy->probability = profile_probability::always ();
658 323402 : exit_e_copy->probability = profile_probability::never ();
659 323402 : gcond *cond_stmt
660 646804 : = as_a <gcond *>(*gsi_last_bb (region_copy[i]));
661 323402 : if (e_copy->flags & EDGE_TRUE_VALUE)
662 232857 : gimple_cond_make_true (cond_stmt);
663 : else
664 90545 : gimple_cond_make_false (cond_stmt);
665 323402 : update_stmt (cond_stmt);
666 : /* Header copying is a special case of jump threading, so use
667 : common code to update loop body exit condition. */
668 323402 : update_bb_profile_for_threading (region[i], entry_count, e);
669 : }
670 : else
671 263554 : region[i]->count -= region_copy[i]->count;
672 586956 : if (invariant_exits->contains (exit_e))
673 : {
674 4652 : invariant_exits->remove (exit_e);
675 : /* All exits will happen in exit_e_copy which is out of the
676 : loop, so increase probability accordingly.
677 : If the edge is eliminated_edge we already corrected
678 : profile above. */
679 9255 : if (entry_count.nonzero_p () && !was_static)
680 4235 : set_edge_probability_and_rescale_others
681 4235 : (exit_e_copy, exit_e_count.probability_in
682 : (entry_count));
683 : /* Eliminate in-loop conditional. */
684 4652 : e->probability = profile_probability::always ();
685 4652 : exit_e->probability = profile_probability::never ();
686 9304 : gcond *cond_stmt = as_a <gcond *>(*gsi_last_bb (region[i]));
687 4652 : if (e->flags & EDGE_TRUE_VALUE)
688 2009 : gimple_cond_make_true (cond_stmt);
689 : else
690 2643 : gimple_cond_make_false (cond_stmt);
691 4652 : update_stmt (cond_stmt);
692 : }
693 586956 : entry_count = e_copy->count ();
694 : }
695 : /* Be sure that we seen all invariant exit edges we are supposed to update.
696 : We may have recorded some static exists we decided to not duplicate. */
697 577254 : gcc_checking_assert (invariant_exits->is_empty ());
698 577254 : }
699 :
700 : namespace {
701 :
702 : /* Common superclass for both header-copying phases. */
703 : class ch_base : public gimple_opt_pass
704 : {
705 : protected:
706 883761 : ch_base (pass_data data, gcc::context *ctxt)
707 1767522 : : gimple_opt_pass (data, ctxt)
708 : {}
709 :
710 : /* Copies headers of all loops in FUN for which process_loop_p is true. */
711 : unsigned int copy_headers (function *fun);
712 :
713 : /* Return true to copy headers of LOOP or false to skip. */
714 : virtual bool process_loop_p (class loop *loop) = 0;
715 : };
716 :
717 : const pass_data pass_data_ch =
718 : {
719 : GIMPLE_PASS, /* type */
720 : "ch", /* name */
721 : OPTGROUP_LOOP, /* optinfo_flags */
722 : TV_TREE_CH, /* tv_id */
723 : ( PROP_cfg | PROP_ssa ), /* properties_required */
724 : 0, /* properties_provided */
725 : 0, /* properties_destroyed */
726 : 0, /* todo_flags_start */
727 : 0, /* todo_flags_finish */
728 : };
729 :
730 : class pass_ch : public ch_base
731 : {
732 : public:
733 589174 : pass_ch (gcc::context *ctxt)
734 589174 : : ch_base (pass_data_ch, ctxt)
735 589174 : {}
736 :
737 : /* opt_pass methods: */
738 1063454 : bool gate (function *) final override { return flag_tree_ch != 0; }
739 :
740 : /* Initialize and finalize loop structures, copying headers in between. */
741 : unsigned int execute (function *) final override;
742 :
743 294587 : opt_pass * clone () final override { return new pass_ch (m_ctxt); }
744 :
745 : protected:
746 : /* ch_base method: */
747 : bool process_loop_p (class loop *loop) final override;
748 : }; // class pass_ch
749 :
750 : const pass_data pass_data_ch_vect =
751 : {
752 : GIMPLE_PASS, /* type */
753 : "ch_vect", /* name */
754 : OPTGROUP_LOOP, /* optinfo_flags */
755 : TV_TREE_CH, /* tv_id */
756 : ( PROP_cfg | PROP_ssa ), /* properties_required */
757 : 0, /* properties_provided */
758 : 0, /* properties_destroyed */
759 : 0, /* todo_flags_start */
760 : 0, /* todo_flags_finish */
761 : };
762 :
763 : /* This is a more aggressive version of the same pass, designed to run just
764 : before if-conversion and vectorization, to put more loops into the form
765 : required for those phases. */
766 : class pass_ch_vect : public ch_base
767 : {
768 : public:
769 294587 : pass_ch_vect (gcc::context *ctxt)
770 294587 : : ch_base (pass_data_ch_vect, ctxt)
771 294587 : {}
772 :
773 : /* opt_pass methods: */
774 245657 : bool gate (function *fun) final override
775 : {
776 245657 : return flag_tree_ch != 0
777 245657 : && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
778 : }
779 :
780 : /* Just copy headers, no initialization/finalization of loop structures. */
781 : unsigned int execute (function *) final override;
782 :
783 : protected:
784 : /* ch_base method: */
785 : bool process_loop_p (class loop *loop) final override;
786 : }; // class pass_ch_vect
787 :
788 : /* Sort comparator to order loops after the specified order. */
789 :
790 : static int
791 45726 : ch_order_loops (const void *a_, const void *b_, void *order_)
792 : {
793 45726 : int *order = (int *)order_;
794 45726 : const class loop *a = *(const class loop * const *)a_;
795 45726 : const class loop *b = *(const class loop * const *)b_;
796 45726 : if (a->num == b->num)
797 : return 0;
798 45726 : if (order[a->num] < order[b->num])
799 22227 : return -1;
800 : return 1;
801 : }
802 :
803 : /* For all loops, copy the condition at the end of the loop body in front
804 : of the loop. This is beneficial since it increases efficiency of
805 : code motion optimizations. It also saves one jump on entry to the loop. */
806 :
807 : unsigned int
808 1274926 : ch_base::copy_headers (function *fun)
809 : {
810 1274926 : basic_block *bbs, *copied_bbs;
811 1274926 : unsigned bbs_size;
812 1274926 : bool changed = false;
813 :
814 2549852 : if (number_of_loops (fun) <= 1)
815 : return 0;
816 :
817 456936 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
818 456936 : copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
819 456936 : bbs_size = n_basic_blocks_for_fn (fun);
820 :
821 456936 : struct candidate
822 : {
823 : class loop *loop;
824 : unsigned int nheaders;
825 : hash_set <edge> *invariant_exits, *static_exits;
826 : };
827 456936 : auto_vec<struct candidate> candidates;
828 456936 : auto_vec<std::pair<edge, loop_p> > copied;
829 456936 : auto_vec<class loop *> loops_to_unloop;
830 456936 : auto_vec<int> loops_to_unloop_nunroll;
831 :
832 456936 : mark_dfs_back_edges ();
833 456936 : gimple_ranger *ranger = new gimple_ranger;
834 2577244 : for (auto loop : loops_list (cfun, 0))
835 : {
836 1206436 : int initial_limit = optimize_loop_for_speed_p (loop)
837 1206436 : ? param_max_loop_header_insns : 0;
838 1206436 : int remaining_limit = initial_limit;
839 1206436 : if (dump_file && (dump_flags & TDF_DETAILS))
840 21 : fprintf (dump_file,
841 : "Analyzing loop %i\n", loop->num);
842 :
843 : /* If the loop is already a do-while style one (either because it was
844 : written as such, or because jump threading transformed it into one),
845 : we might be in fact peeling the first iteration of the loop. This
846 : in general is not a good idea. Also avoid touching infinite loops. */
847 1206436 : if (!loop_has_exit_edges (loop)
848 1206436 : || !process_loop_p (loop))
849 474308 : continue;
850 :
851 732177 : basic_block header = loop->header;
852 732177 : estimate_numbers_of_iterations (loop);
853 732177 : if (!get_max_loop_iterations_int (loop))
854 : {
855 49 : if (dump_file && (dump_flags & TDF_DETAILS))
856 0 : fprintf (dump_file, "Loop %d never loops.\n", loop->num);
857 49 : scale_loop_profile (loop, profile_probability::always (), 0);
858 49 : loops_to_unloop.safe_push (loop);
859 49 : loops_to_unloop_nunroll.safe_push (0);
860 49 : continue;
861 : }
862 :
863 : /* Iterate the header copying up to limit; this takes care of the cases
864 : like while (a && b) {...}, where we want to have both of the conditions
865 : copied. TODO -- handle while (a || b) - like cases, by not requiring
866 : the header to have just a single successor and copying up to
867 : postdominator. */
868 732128 : unsigned int nheaders = 0;
869 732128 : unsigned int last_win_nheaders = 0;
870 732128 : bool last_win_invariant_exit = false;
871 732128 : ch_decision ret;
872 732128 : auto_vec <ch_decision, 32> decision;
873 732128 : hash_set <edge> *invariant_exits = new hash_set <edge>;
874 732128 : hash_set <edge> *static_exits = new hash_set <edge>;
875 732128 : bool canbe_neverexecuted = true;
876 732128 : while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
877 : &remaining_limit,
878 : invariant_exits,
879 : static_exits,
880 : &canbe_neverexecuted))
881 1486917 : != ch_impossible)
882 : {
883 754789 : nheaders++;
884 754789 : decision.safe_push (ret);
885 754789 : if (ret >= ch_win)
886 : {
887 11294 : last_win_nheaders = nheaders;
888 11294 : last_win_invariant_exit = (ret == ch_win_invariant_exit);
889 11294 : if (dump_file && (dump_flags & TDF_DETAILS))
890 10 : fprintf (dump_file, " Duplicating bb %i is a win\n",
891 : header->index);
892 : }
893 : else
894 743495 : if (dump_file && (dump_flags & TDF_DETAILS))
895 24 : fprintf (dump_file, " May duplicate bb %i\n", header->index);
896 :
897 : /* Find a successor of header that is inside a loop; i.e. the new
898 : header after the condition is copied. */
899 754789 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
900 509643 : header = EDGE_SUCC (header, 0)->dest;
901 : else
902 245146 : header = EDGE_SUCC (header, 1)->dest;
903 : }
904 :
905 : /* Try to turn loop into do-while. This means ensuring that
906 : last duplicated header will not have loop invariant exit. */
907 732128 : if (last_win_nheaders && last_win_invariant_exit
908 9441 : && nheaders > last_win_nheaders)
909 : {
910 2828 : last_win_nheaders++;
911 2828 : if (dump_file && (dump_flags & TDF_DETAILS))
912 6 : fprintf (dump_file,
913 : " Duplicating additional BB to obtain do-while loop\n");
914 : }
915 729300 : else if (!last_win_nheaders && nheaders && !do_while_loop_p (loop))
916 : {
917 563157 : last_win_nheaders = 1;
918 563157 : if (dump_file && (dump_flags & TDF_DETAILS))
919 11 : fprintf (dump_file,
920 : " Duplicating header BB to obtain do-while loop\n");
921 : }
922 : /* "Duplicate" all BBs with zero cost following last basic blocks we
923 : decided to copy. */
924 1472204 : while (last_win_nheaders < decision.length ()
925 874659 : && decision[last_win_nheaders] == ch_possible_zero_cost)
926 : {
927 7948 : if (dump_file && (dump_flags & TDF_DETAILS))
928 0 : fprintf (dump_file,
929 : " Duplicating extra bb is a win; it has zero cost\n");
930 7948 : last_win_nheaders++;
931 : }
932 :
933 732128 : if (last_win_nheaders)
934 577373 : candidates.safe_push ({loop, last_win_nheaders,
935 : invariant_exits, static_exits});
936 : else
937 : {
938 154755 : delete invariant_exits;
939 154755 : delete static_exits;
940 : }
941 732128 : }
942 : /* Do not use ranger after we change the IL and not have updated SSA. */
943 456936 : delete ranger;
944 :
945 1406985 : for (auto candidate : candidates)
946 : {
947 577373 : class loop *loop = candidate.loop;
948 577373 : if (dump_file && (dump_flags & TDF_DETAILS))
949 20 : fprintf (dump_file,
950 : "Copying headers of loop %i\n", loop->num);
951 :
952 577373 : basic_block header = loop->header;
953 577373 : edge nonexit = NULL;
954 577373 : edge exit = NULL;
955 577373 : unsigned int n_bbs = 0;
956 577373 : int nexits = 0;
957 577373 : profile_count exit_count = profile_count::zero ();
958 577373 : profile_count entry_count = profile_count::zero ();
959 577373 : edge e;
960 577373 : edge_iterator ei;
961 :
962 1732119 : FOR_EACH_EDGE (e, ei, loop->header->preds)
963 1154746 : if (e->src != loop->latch)
964 577373 : entry_count += e->count ();
965 1164449 : while (n_bbs < candidate.nheaders)
966 : {
967 587076 : if (dump_file && (dump_flags & TDF_DETAILS))
968 30 : fprintf (dump_file, " Will duplicate bb %i\n", header->index);
969 : /* Find a successor of header that is inside a loop; i.e. the new
970 : header after the condition is copied. */
971 587076 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
972 : {
973 447623 : nonexit = EDGE_SUCC (header, 0);
974 447623 : exit = EDGE_SUCC (header, 1);
975 : }
976 : else
977 : {
978 139453 : nonexit = EDGE_SUCC (header, 1);
979 139453 : exit = EDGE_SUCC (header, 0);
980 : }
981 587076 : exit_count += exit->count ();
982 587076 : nexits++;
983 587076 : bbs[n_bbs++] = header;
984 587076 : gcc_assert (bbs_size > n_bbs);
985 587076 : header = nonexit->dest;
986 : }
987 :
988 577373 : if (dump_file && (dump_flags & TDF_DETAILS))
989 20 : fprintf (dump_file,
990 : "Duplicating header of the loop %d up to edge %d->%d\n",
991 20 : loop->num, exit->src->index, exit->dest->index);
992 :
993 : /* Ensure that the header will have just the latch as a predecessor
994 : inside the loop. */
995 577373 : if (!single_pred_p (nonexit->dest))
996 : {
997 17 : header = split_edge (nonexit);
998 17 : exit = single_pred_edge (header);
999 : }
1000 :
1001 577373 : edge entry = loop_preheader_edge (loop);
1002 :
1003 577373 : propagate_threaded_block_debug_into (nonexit->dest, entry->dest);
1004 577373 : if (!gimple_duplicate_seme_region (entry, exit, bbs, n_bbs, copied_bbs,
1005 : true))
1006 : {
1007 0 : delete candidate.static_exits;
1008 0 : delete candidate.invariant_exits;
1009 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1010 0 : fprintf (dump_file, "Duplication failed.\n");
1011 0 : continue;
1012 : }
1013 577373 : if (loop->header->count.initialized_p ())
1014 577254 : update_profile_after_ch (loop, bbs, copied_bbs, n_bbs,
1015 : candidate.invariant_exits,
1016 : candidate.static_exits,
1017 : entry_count);
1018 1154746 : delete candidate.static_exits;
1019 1154746 : delete candidate.invariant_exits;
1020 577373 : copied.safe_push (std::make_pair (entry, loop));
1021 :
1022 : /* Update header of the loop. */
1023 577373 : loop->header = header;
1024 : /* Find correct latch. We only duplicate chain of conditionals so
1025 : there should be precisely two edges to the new header. One entry
1026 : edge and one to latch. */
1027 577373 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1028 577373 : if (header != e->src)
1029 : {
1030 577373 : loop->latch = e->src;
1031 577373 : break;
1032 : }
1033 : /* Ensure that the latch is simple. */
1034 577373 : if (!single_succ_p (loop_latch_edge (loop)->src))
1035 577373 : split_edge (loop_latch_edge (loop));
1036 :
1037 577373 : if (dump_file && (dump_flags & TDF_DETAILS))
1038 : {
1039 20 : if (do_while_loop_p (loop))
1040 19 : fprintf (dump_file, "Loop %d is now do-while loop.\n", loop->num);
1041 : else
1042 1 : fprintf (dump_file, "Loop %d is still not do-while loop.\n",
1043 : loop->num);
1044 20 : fprintf (dump_file, "Exit count: ");
1045 20 : exit_count.dump (dump_file);
1046 20 : fprintf (dump_file, "\nEntry count: ");
1047 20 : entry_count.dump (dump_file);
1048 20 : fprintf (dump_file, "\n");
1049 : }
1050 :
1051 : /* We possibly decreased number of iterations by 1. */
1052 577373 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1053 577373 : bool precise = (nexits == (int) exits.length ());
1054 : /* Check that loop may not terminate in other way than via
1055 : basic blocks we duplicated. */
1056 577373 : if (precise)
1057 : {
1058 386034 : basic_block *bbs = get_loop_body (loop);
1059 2301053 : for (unsigned i = 0; i < loop->num_nodes && precise; ++i)
1060 : {
1061 1529017 : basic_block bb = bbs[i];
1062 1529017 : bool found_exit = false;
1063 3197764 : FOR_EACH_EDGE (e, ei, bb->succs)
1064 2007786 : if (!flow_bb_inside_loop_p (loop, e->dest))
1065 : {
1066 : found_exit = true;
1067 : break;
1068 : }
1069 : /* If BB has exit, it was duplicated. */
1070 1529017 : if (found_exit)
1071 339039 : continue;
1072 : /* Give up on irreducible loops. */
1073 1189978 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1074 : {
1075 : precise = false;
1076 : break;
1077 : }
1078 : /* Check that inner loops are finite. */
1079 1520913 : for (class loop *l = bb->loop_father; l != loop && precise;
1080 330967 : l = loop_outer (l))
1081 339819 : if (!l->finite_p)
1082 : {
1083 : precise = false;
1084 : break;
1085 : }
1086 : /* Verify that there is no statement that may be terminate
1087 : execution in a way not visible to CFG. */
1088 2379892 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
1089 8861104 : !gsi_end_p (bsi); gsi_next (&bsi))
1090 7671158 : if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
1091 116817 : precise = false;
1092 : }
1093 386034 : free (bbs);
1094 : }
1095 577373 : if (precise
1096 577373 : && get_max_loop_iterations_int (loop) == 1)
1097 : {
1098 2928 : if (dump_file && (dump_flags & TDF_DETAILS))
1099 0 : fprintf (dump_file, "Loop %d no longer loops.\n", loop->num);
1100 2928 : scale_loop_profile (loop, profile_probability::always (), 0);
1101 2928 : loops_to_unloop.safe_push (loop);
1102 2928 : loops_to_unloop_nunroll.safe_push (0);
1103 : }
1104 574445 : else if (precise)
1105 : {
1106 302688 : if (dump_file && (dump_flags & TDF_DETAILS))
1107 11 : fprintf (dump_file,
1108 : "Peeled all exits:"
1109 : " decreased number of iterations of loop %d by 1.\n",
1110 : loop->num);
1111 302688 : adjust_loop_info_after_peeling (loop, 1, true);
1112 : }
1113 271757 : else if (exit_count >= entry_count.apply_scale (9, 10))
1114 : {
1115 157408 : if (dump_file && (dump_flags & TDF_DETAILS))
1116 5 : fprintf (dump_file,
1117 : "Peeled likely exits: likely decreased number "
1118 : "of iterations of loop %d by 1.\n", loop->num);
1119 157408 : adjust_loop_info_after_peeling (loop, 1, false);
1120 : }
1121 114349 : else if (dump_file && (dump_flags & TDF_DETAILS))
1122 4 : fprintf (dump_file,
1123 : "Not decreased number"
1124 : " of iterations of loop %d; likely exits remains.\n",
1125 : loop->num);
1126 :
1127 577373 : changed = true;
1128 577373 : }
1129 :
1130 456936 : if (changed)
1131 : {
1132 186338 : update_ssa (TODO_update_ssa);
1133 : /* After updating SSA form perform CSE on the loop header
1134 : copies. This is esp. required for the pass before
1135 : vectorization since nothing cleans up copied exit tests
1136 : that can now be simplified. CSE from the entry of the
1137 : region we copied till all loop exit blocks but not
1138 : entering the loop itself. */
1139 950049 : for (unsigned i = 0; i < copied.length (); ++i)
1140 : {
1141 577373 : edge entry = copied[i].first;
1142 577373 : loop_p loop = copied[i].second;
1143 577373 : auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
1144 577373 : bitmap exit_bbs = BITMAP_ALLOC (NULL);
1145 2216452 : for (unsigned j = 0; j < exit_edges.length (); ++j)
1146 1061706 : bitmap_set_bit (exit_bbs, exit_edges[j]->dest->index);
1147 577373 : bitmap_set_bit (exit_bbs, loop->header->index);
1148 577373 : do_rpo_vn (cfun, entry, exit_bbs);
1149 577373 : BITMAP_FREE (exit_bbs);
1150 577373 : }
1151 : }
1152 456936 : if (!loops_to_unloop.is_empty ())
1153 : {
1154 : /* Make sure loops are ordered inner to outer for unlooping. */
1155 864 : if (loops_to_unloop.length () != 1)
1156 : {
1157 377 : auto_vec<int, 8> order;
1158 754 : order.safe_grow (number_of_loops (cfun), true);
1159 377 : int i = 0;
1160 10984 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1161 9853 : order[loop->num] = i++;
1162 1131 : loops_to_unloop.sort (ch_order_loops, order.address ());
1163 377 : }
1164 864 : bool irred_invalidated;
1165 864 : auto_bitmap lc_invalidated;
1166 864 : auto_vec<edge> edges_to_remove;
1167 864 : unloop_loops (loops_to_unloop, loops_to_unloop_nunroll, edges_to_remove,
1168 : lc_invalidated, &irred_invalidated);
1169 864 : if (loops_state_satisfies_p (fun, LOOP_CLOSED_SSA)
1170 864 : && !bitmap_empty_p (lc_invalidated))
1171 16 : rewrite_into_loop_closed_ssa (NULL, 0);
1172 864 : changed = true;
1173 864 : }
1174 456936 : free (bbs);
1175 456936 : free (copied_bbs);
1176 :
1177 456936 : return changed ? TODO_cleanup_cfg : 0;
1178 456936 : }
1179 :
1180 : /* Initialize the loop structures we need, and finalize after. */
1181 :
1182 : unsigned int
1183 1063211 : pass_ch::execute (function *fun)
1184 : {
1185 1063211 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1186 1063211 : scev_initialize ();
1187 :
1188 1063211 : unsigned int res = copy_headers (fun);
1189 :
1190 1063211 : scev_finalize ();
1191 1063211 : loop_optimizer_finalize ();
1192 1063211 : return res;
1193 : }
1194 :
1195 : /* Assume an earlier phase has already initialized all the loop structures that
1196 : we need here (and perhaps others too), and that these will be finalized by
1197 : a later phase. */
1198 :
1199 : unsigned int
1200 211715 : pass_ch_vect::execute (function *fun)
1201 : {
1202 211715 : return copy_headers (fun);
1203 : }
1204 :
1205 : /* Apply header copying according to a very simple test of do-while shape. */
1206 :
1207 : bool
1208 690582 : pass_ch::process_loop_p (class loop *)
1209 : {
1210 690582 : return true;
1211 : }
1212 :
1213 : /* Apply header-copying to loops where we might enable vectorization. */
1214 :
1215 : bool
1216 505912 : pass_ch_vect::process_loop_p (class loop *loop)
1217 : {
1218 505912 : if (!flag_tree_loop_vectorize && !loop->force_vectorize)
1219 : return false;
1220 :
1221 503144 : if (loop->dont_vectorize)
1222 : return false;
1223 :
1224 : /* The vectorizer won't handle anything with multiple exits, so skip. */
1225 498460 : edge exit = single_exit (loop);
1226 498460 : if (!exit)
1227 : return false;
1228 :
1229 301275 : if (!do_while_loop_p (loop))
1230 41595 : return true;
1231 :
1232 : return false;
1233 : }
1234 :
1235 : } // anon namespace
1236 :
1237 : gimple_opt_pass *
1238 294587 : make_pass_ch_vect (gcc::context *ctxt)
1239 : {
1240 294587 : return new pass_ch_vect (ctxt);
1241 : }
1242 :
1243 : gimple_opt_pass *
1244 294587 : make_pass_ch (gcc::context *ctxt)
1245 : {
1246 294587 : return new pass_ch (ctxt);
1247 : }
|
