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 insteance 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 789307 : get_range_query (class loop *loop,
53 : basic_block bb,
54 : gimple_ranger &ranger)
55 : {
56 789307 : auto_vec<basic_block, 8> path;
57 1001309 : for (; bb != loop->header; bb = single_pred_edge (bb)->src)
58 212002 : path.safe_push (bb);
59 789307 : path.safe_push (loop->header);
60 789307 : path.safe_push (loop_preheader_edge (loop)->src);
61 789307 : return new path_range_query (ranger, path);
62 789307 : }
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 747272 : static_loop_exit (class loop *l, basic_block bb, gimple_ranger &ranger,
70 : path_range_query *&query)
71 : {
72 1494544 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
73 747272 : edge ret_e;
74 :
75 747272 : if (!last)
76 : return NULL;
77 :
78 747272 : edge true_e, false_e;
79 747272 : 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 747272 : if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e))
84 : return NULL;
85 :
86 747272 : int_range<1> desired_static_range;
87 747272 : if (loop_exit_edge_p (l, true_e))
88 : {
89 241126 : desired_static_range = range_false ();
90 241126 : ret_e = true_e;
91 : }
92 : else
93 : {
94 506146 : desired_static_range = range_true ();
95 506146 : ret_e = false_e;
96 : }
97 :
98 747272 : if (!query)
99 89008 : query = get_range_query (l, gimple_bb (last), ranger);
100 :
101 747272 : int_range<2> r;
102 747272 : if (!query->range_of_stmt (r, last))
103 : return NULL;
104 747272 : return r == desired_static_range ? ret_e : NULL;
105 747272 : }
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 1359913 : loop_static_stmt_p (class loop *loop,
113 : gimple_ranger &ranger,
114 : path_range_query *&query,
115 : gimple *stmt)
116 : {
117 1359913 : tree type = gimple_range_type (stmt);
118 1359913 : if (!type || !value_range::supports_type_p (type))
119 6946 : return false;
120 :
121 1352967 : if (!query)
122 700299 : query = get_range_query (loop, gimple_bb (stmt), ranger);
123 :
124 1352967 : value_range r (gimple_range_type (stmt));
125 1352967 : if (!query->range_of_stmt (r, stmt))
126 : return false;
127 1352967 : return r.singleton_p ();
128 1352967 : }
129 :
130 : /* Return true if OP is invariant. */
131 :
132 : static bool
133 2123467 : loop_invariant_op_p (class loop *loop,
134 : tree op)
135 : {
136 2123467 : if (is_gimple_min_invariant (op))
137 : return true;
138 1656412 : if (SSA_NAME_IS_DEFAULT_DEF (op)
139 1656412 : || !flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (op))))
140 281513 : return true;
141 1374899 : 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 16765 : loop_static_op_p (class loop *loop, tree op)
149 : {
150 : /* Always check for invariant first. */
151 33530 : 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 16765 : 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 678902 : loop_combined_static_and_iv_p (class loop *loop,
164 : tree op)
165 : {
166 : /* Always check for invariant first. */
167 1357804 : 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 678902 : return gimple_uid (SSA_NAME_DEF_STMT (op)) & 4;
172 : }
173 :
174 : /* Decision about posibility 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 1460571 : 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 1460571 : gimple_stmt_iterator bsi;
207 :
208 1460571 : gcc_assert (!header->aux);
209 :
210 1460571 : gcc_assert (EDGE_COUNT (header->succs) > 0);
211 1460571 : if (single_succ_p (header))
212 : {
213 444245 : 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 444245 : return ch_impossible;
218 : }
219 :
220 1016326 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
221 1016326 : && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
222 : {
223 151925 : 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 151925 : 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 1046950 : 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 mutiple predecestors.\n",
237 : header->index);
238 0 : return ch_impossible;
239 : }
240 :
241 1728802 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
242 864401 : if (!last)
243 : {
244 50193 : 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 50193 : return ch_impossible;
249 : }
250 :
251 814208 : path_range_query *query = NULL;
252 2140581 : for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
253 1326373 : gsi_next (&psi))
254 2652746 : if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
255 : {
256 1815394 : bool static_p = loop_static_stmt_p (loop, *ranger,
257 907697 : query, psi.phi ());
258 1815394 : gimple_set_uid (psi.phi (), static_p ? 2 : 0);
259 : }
260 814208 : 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 4004709 : for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
266 : {
267 3190501 : gimple *last = gsi_stmt (bsi);
268 :
269 3190501 : if (gimple_code (last) == GIMPLE_LABEL)
270 11232 : continue;
271 :
272 3179269 : if (is_gimple_debug (last))
273 1528938 : continue;
274 :
275 1650331 : if (gimple_code (last) == GIMPLE_COND)
276 : break;
277 :
278 902989 : 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 902989 : if (gimple_code (last) == GIMPLE_CALL
285 902989 : && (!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 5969 : || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
289 : {
290 49044 : 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 49044 : if (query)
295 34481 : delete query;
296 49044 : return ch_impossible;
297 : }
298 :
299 : /* Classify the stmt is invariant in the loop. */
300 853945 : gimple_set_uid (last, 0);
301 1323539 : if (!gimple_vuse (last)
302 469594 : && gimple_code (last) != GIMPLE_ASM
303 1323463 : && (gimple_code (last) != GIMPLE_CALL
304 525 : || gimple_call_flags (last) & ECF_CONST))
305 : {
306 469409 : bool inv = true, static_p = false;
307 469409 : ssa_op_iter i;
308 469409 : tree op;
309 1080609 : FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
310 611200 : if (!loop_invariant_op_p (loop, op))
311 518159 : inv = false;
312 : /* Assume that code is reasonably optimized and invariant
313 : constants are already identified. */
314 469409 : if (!inv)
315 452216 : static_p = loop_static_stmt_p (loop, *ranger, query, last);
316 875677 : gimple_set_uid (last, (inv ? 1 : 0) | (static_p ? 2 : 0));
317 469409 : 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 : duplicatd header. */
331 469409 : if (inv || static_p)
332 80429 : continue;
333 :
334 : /* Match the following:
335 : _1 = i_1 < 10 <- static condtion
336 : _2 = n != 0 <- loop invariant condition
337 : _3 = _1 & _2 <- combined static and iv statement. */
338 389075 : tree_code code;
339 389075 : if (gimple_code (last) == GIMPLE_ASSIGN
340 389075 : && ((code = gimple_assign_rhs_code (last)) == BIT_AND_EXPR
341 376632 : || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR))
342 : {
343 15509 : tree op1 = gimple_assign_rhs1 (last);
344 15509 : tree op2 = gimple_assign_rhs2 (last);
345 :
346 15509 : if ((loop_invariant_op_p (loop, op1)
347 14743 : || loop_combined_static_and_iv_p (loop, op1)
348 14741 : || loop_static_op_p (loop, op1))
349 16817 : && (loop_invariant_op_p (loop, op2)
350 2024 : || loop_combined_static_and_iv_p (loop, op2)
351 2024 : || 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 95 : gimple_set_uid (last, 4);
361 95 : if (dump_file && (dump_flags & TDF_DETAILS))
362 1 : fprintf (dump_file,
363 : " Stmt combines static and invariant op\n");
364 95 : continue;
365 : }
366 : }
367 : }
368 :
369 773516 : int insns = estimate_num_insns (last, &eni_size_weights);
370 773516 : *limit -= insns;
371 773516 : if (insns)
372 665078 : code_size_cost = true;
373 773516 : if (dump_file && (dump_flags & TDF_DETAILS))
374 42 : fprintf (dump_file,
375 : " Acconting stmt as %i insns\n", insns);
376 773516 : if (*limit < 0)
377 : {
378 17822 : 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 17822 : if (query)
383 7484 : delete query;
384 17822 : return ch_impossible;
385 : }
386 : }
387 :
388 747342 : 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 747342 : tree lhs = gimple_cond_lhs (last);
397 747342 : tree rhs = gimple_cond_rhs (last);
398 747342 : bool lhs_invariant = loop_invariant_op_p (loop, lhs);
399 747342 : 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 condtion
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 747342 : if (lhs_invariant != rhs_invariant
423 662135 : && (lhs_invariant
424 560077 : || loop_combined_static_and_iv_p (loop, lhs))
425 849470 : && (rhs_invariant
426 102058 : || loop_combined_static_and_iv_p (loop, rhs)))
427 : {
428 70 : if (query)
429 70 : delete query;
430 70 : if (dump_file && (dump_flags & TDF_DETAILS))
431 1 : fprintf (dump_file,
432 : " Conditional combines static and invariant op.\n");
433 70 : return ch_win;
434 : }
435 :
436 747272 : edge static_exit = static_loop_exit (loop, header, *ranger, query);
437 747272 : if (query)
438 747272 : delete query;
439 :
440 747272 : if (static_exit && static_exits)
441 : {
442 323824 : static_exits->add (static_exit);
443 323824 : 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 747272 : if (lhs_invariant && rhs_invariant)
450 : {
451 4533 : if (invariant_exits)
452 : {
453 4533 : edge e;
454 4533 : edge_iterator ei;
455 13599 : FOR_EACH_EDGE (e, ei, header->succs)
456 9066 : if (loop_exit_edge_p (loop, e))
457 : {
458 4533 : if (dump_file && (dump_flags & TDF_DETAILS))
459 4 : fprintf (dump_file,
460 : " Will elliminate invariant exit %i->%i\n",
461 4 : e->src->index, e->dest->index);
462 4533 : invariant_exits->add (e);
463 : }
464 : }
465 4533 : return ch_win_invariant_exit;
466 : }
467 742739 : 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 289407 : edge e;
473 289407 : edge_iterator ei;
474 289407 : bool hasone = false;
475 868221 : FOR_EACH_EDGE (e, ei, header->succs)
476 578814 : if (loop_exit_edge_p (loop, e)
477 578814 : && probably_never_executed_edge_p (cfun, e))
478 : {
479 6133 : hasone = true;
480 6133 : 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 289407 : if (hasone)
486 6133 : return ch_win_invariant_exit;
487 : }
488 736606 : *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 736606 : if (static_exit)
496 639521 : return !code_size_cost ? ch_possible_zero_cost : ch_possible;
497 :
498 : /* We was not able to prove that conditional will be eliminated. */
499 412823 : int insns = estimate_num_insns (last, &eni_size_weights);
500 412823 : *limit -= insns;
501 412823 : if (dump_file && (dump_flags & TDF_DETAILS))
502 19 : fprintf (dump_file,
503 : " Acconting stmt as %i insns\n", insns);
504 412823 : if (*limit < 0)
505 : {
506 10526 : 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 10526 : 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 889189 : do_while_loop_p (class loop *loop)
520 : {
521 889189 : 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 889189 : if (stmt
525 889189 : && gimple_code (stmt) != GIMPLE_LABEL)
526 : {
527 565517 : 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 565517 : return false;
532 : }
533 :
534 : /* If the latch does not have a single predecessor, it is not a
535 : do-while loop. */
536 323672 : if (!single_pred_p (loop->latch))
537 : {
538 24018 : 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 24018 : return false;
543 : }
544 299654 : 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 299654 : if (!loop_exits_from_bb_p (loop, pred))
549 : {
550 8320 : 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 8320 : return false;
555 : }
556 582668 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
557 290444 : if (last
558 290444 : && (gimple_cond_lhs (last) == boolean_false_node
559 290444 : || 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 1 : return false;
567 : }
568 :
569 291333 : 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 569509 : 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 1148527 : for (unsigned int i = 0; i < n_region; i++)
620 : {
621 579018 : edge exit_e, exit_e_copy, e, e_copy;
622 579018 : 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 579018 : gcc_checking_assert (EDGE_COUNT (region[i]->succs) == 2);
630 579018 : if (loop_exit_edge_p (loop,
631 579018 : EDGE_SUCC (region[i], 0)))
632 : {
633 135604 : exit_e = EDGE_SUCC (region[i], 0);
634 135604 : exit_e_copy = EDGE_SUCC (region_copy[i], 0);
635 135604 : e = EDGE_SUCC (region[i], 1);
636 135604 : e_copy = EDGE_SUCC (region_copy[i], 1);
637 : }
638 : else
639 : {
640 443414 : exit_e = EDGE_SUCC (region[i], 1);
641 443414 : exit_e_copy = EDGE_SUCC (region_copy[i], 1);
642 443414 : e = EDGE_SUCC (region[i], 0);
643 443414 : e_copy = EDGE_SUCC (region_copy[i], 0);
644 : }
645 579018 : gcc_assert (i == n_region - 1
646 : || (e->dest == region[i + 1]
647 : && e_copy->dest == region_copy[i + 1]));
648 579018 : region_copy[i]->count = entry_count;
649 579018 : profile_count exit_e_count = exit_e->count ();
650 579018 : bool was_static = false;
651 579018 : if (static_exits->contains (exit_e))
652 : {
653 : /* Update profile and the conditional.
654 : CFG update is done by caller. */
655 316373 : static_exits->remove (exit_e);
656 316373 : was_static = true;
657 316373 : e_copy->probability = profile_probability::always ();
658 316373 : exit_e_copy->probability = profile_probability::never ();
659 316373 : gcond *cond_stmt
660 632746 : = as_a <gcond *>(*gsi_last_bb (region_copy[i]));
661 316373 : if (e_copy->flags & EDGE_TRUE_VALUE)
662 228452 : gimple_cond_make_true (cond_stmt);
663 : else
664 87921 : gimple_cond_make_false (cond_stmt);
665 316373 : 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 316373 : update_bb_profile_for_threading (region[i], entry_count, e);
669 : }
670 : else
671 262645 : region[i]->count -= region_copy[i]->count;
672 579018 : if (invariant_exits->contains (exit_e))
673 : {
674 4529 : 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 9007 : if (entry_count.nonzero_p () && !was_static)
680 4439 : set_edge_probability_and_rescale_others
681 4439 : (exit_e_copy, exit_e_count.probability_in
682 : (entry_count));
683 : /* Eliminate in-loop conditional. */
684 4529 : e->probability = profile_probability::always ();
685 4529 : exit_e->probability = profile_probability::never ();
686 9058 : gcond *cond_stmt = as_a <gcond *>(*gsi_last_bb (region[i]));
687 4529 : if (e->flags & EDGE_TRUE_VALUE)
688 1964 : gimple_cond_make_true (cond_stmt);
689 : else
690 2565 : gimple_cond_make_false (cond_stmt);
691 4529 : update_stmt (cond_stmt);
692 : }
693 579018 : 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 569509 : gcc_checking_assert (invariant_exits->is_empty ());
698 569509 : }
699 :
700 : namespace {
701 :
702 : /* Common superclass for both header-copying phases. */
703 : class ch_base : public gimple_opt_pass
704 : {
705 : protected:
706 857166 : ch_base (pass_data data, gcc::context *ctxt)
707 1714332 : : 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 571444 : pass_ch (gcc::context *ctxt)
734 571444 : : ch_base (pass_data_ch, ctxt)
735 571444 : {}
736 :
737 : /* opt_pass methods: */
738 1042522 : bool gate (function *) final override { return flag_tree_ch != 0; }
739 :
740 : /* Initialize and finalize loop structures, copying headers inbetween. */
741 : unsigned int execute (function *) final override;
742 :
743 285722 : 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 285722 : pass_ch_vect (gcc::context *ctxt)
770 285722 : : ch_base (pass_data_ch_vect, ctxt)
771 285722 : {}
772 :
773 : /* opt_pass methods: */
774 241458 : bool gate (function *fun) final override
775 : {
776 241458 : return flag_tree_ch != 0
777 241458 : && (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 45732 : ch_order_loops (const void *a_, const void *b_, void *order_)
792 : {
793 45732 : int *order = (int *)order_;
794 45732 : const class loop *a = *(const class loop * const *)a_;
795 45732 : const class loop *b = *(const class loop * const *)b_;
796 45732 : if (a->num == b->num)
797 : return 0;
798 45732 : if (order[a->num] < order[b->num])
799 22239 : 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 1250782 : ch_base::copy_headers (function *fun)
809 : {
810 1250782 : basic_block *bbs, *copied_bbs;
811 1250782 : unsigned bbs_size;
812 1250782 : bool changed = false;
813 :
814 2501564 : if (number_of_loops (fun) <= 1)
815 : return 0;
816 :
817 449599 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
818 449599 : copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
819 449599 : bbs_size = n_basic_blocks_for_fn (fun);
820 :
821 449599 : struct candidate
822 : {
823 : class loop *loop;
824 : unsigned int nheaders;
825 : hash_set <edge> *invariant_exits, *static_exits;
826 : };
827 449599 : auto_vec<struct candidate> candidates;
828 449599 : auto_vec<std::pair<edge, loop_p> > copied;
829 449599 : auto_vec<class loop *> loops_to_unloop;
830 449599 : auto_vec<int> loops_to_unloop_nunroll;
831 :
832 449599 : mark_dfs_back_edges ();
833 449599 : gimple_ranger *ranger = new gimple_ranger;
834 2540765 : for (auto loop : loops_list (cfun, 0))
835 : {
836 1191968 : int initial_limit = optimize_loop_for_speed_p (loop)
837 1191968 : ? param_max_loop_header_insns : 0;
838 1191968 : int remaining_limit = initial_limit;
839 1191968 : 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 1191968 : if (!loop_has_exit_edges (loop)
848 1191968 : || !process_loop_p (loop))
849 468213 : continue;
850 :
851 723801 : basic_block header = loop->header;
852 723801 : estimate_numbers_of_iterations (loop);
853 723801 : if (!get_max_loop_iterations_int (loop))
854 : {
855 46 : if (dump_file && (dump_flags & TDF_DETAILS))
856 0 : fprintf (dump_file, "Loop %d never loops.\n", loop->num);
857 46 : scale_loop_profile (loop, profile_probability::always (), 0);
858 46 : loops_to_unloop.safe_push (loop);
859 46 : loops_to_unloop_nunroll.safe_push (0);
860 46 : 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 723755 : unsigned int nheaders = 0;
869 723755 : unsigned int last_win_nheaders = 0;
870 723755 : bool last_win_invariant_exit = false;
871 723755 : ch_decision ret;
872 723755 : auto_vec <ch_decision, 32> decision;
873 723755 : hash_set <edge> *invariant_exits = new hash_set <edge>;
874 723755 : hash_set <edge> *static_exits = new hash_set <edge>;
875 723755 : bool canbe_neverexecuted = true;
876 723755 : while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
877 : &remaining_limit,
878 : invariant_exits,
879 : static_exits,
880 : &canbe_neverexecuted))
881 1460571 : != ch_impossible)
882 : {
883 736816 : nheaders++;
884 736816 : decision.safe_push (ret);
885 736816 : if (ret >= ch_win)
886 : {
887 10736 : last_win_nheaders = nheaders;
888 10736 : last_win_invariant_exit = (ret == ch_win_invariant_exit);
889 10736 : 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 726080 : 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 736816 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
900 499392 : header = EDGE_SUCC (header, 0)->dest;
901 : else
902 237424 : 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 723755 : if (last_win_nheaders && last_win_invariant_exit
908 8881 : && nheaders > last_win_nheaders)
909 : {
910 2709 : last_win_nheaders++;
911 2709 : if (dump_file && (dump_flags & TDF_DETAILS))
912 6 : fprintf (dump_file,
913 : " Duplicating additional BB to obtain do-while loop\n");
914 : }
915 721046 : else if (!last_win_nheaders && nheaders && !do_while_loop_p (loop))
916 : {
917 555991 : last_win_nheaders = 1;
918 555991 : 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 1455396 : while (last_win_nheaders < decision.length ()
925 860953 : && decision[last_win_nheaders] == ch_possible_zero_cost)
926 : {
927 7886 : 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 7886 : last_win_nheaders++;
931 : }
932 :
933 723755 : if (last_win_nheaders)
934 569627 : candidates.safe_push ({loop, last_win_nheaders,
935 : invariant_exits, static_exits});
936 : else
937 : {
938 154128 : delete invariant_exits;
939 154128 : delete static_exits;
940 : }
941 723755 : }
942 : /* Do not use ranger after we change the IL and not have updated SSA. */
943 449599 : delete ranger;
944 :
945 1386316 : for (auto candidate : candidates)
946 : {
947 569627 : class loop *loop = candidate.loop;
948 569627 : if (dump_file && (dump_flags & TDF_DETAILS))
949 20 : fprintf (dump_file,
950 : "Copying headers of loop %i\n", loop->num);
951 :
952 569627 : basic_block header = loop->header;
953 569627 : edge nonexit = NULL;
954 569627 : edge exit = NULL;
955 569627 : unsigned int n_bbs = 0;
956 569627 : int nexits = 0;
957 569627 : profile_count exit_count = profile_count::zero ();
958 569627 : profile_count entry_count = profile_count::zero ();
959 569627 : edge e;
960 569627 : edge_iterator ei;
961 :
962 1708881 : FOR_EACH_EDGE (e, ei, loop->header->preds)
963 1139254 : if (e->src != loop->latch)
964 569627 : entry_count += e->count ();
965 1148764 : while (n_bbs < candidate.nheaders)
966 : {
967 579137 : 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 579137 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
972 : {
973 443493 : nonexit = EDGE_SUCC (header, 0);
974 443493 : exit = EDGE_SUCC (header, 1);
975 : }
976 : else
977 : {
978 135644 : nonexit = EDGE_SUCC (header, 1);
979 135644 : exit = EDGE_SUCC (header, 0);
980 : }
981 579137 : exit_count += exit->count ();
982 579137 : nexits++;
983 579137 : bbs[n_bbs++] = header;
984 579137 : gcc_assert (bbs_size > n_bbs);
985 579137 : header = nonexit->dest;
986 : }
987 :
988 569627 : 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 569627 : if (!single_pred_p (nonexit->dest))
996 : {
997 12 : header = split_edge (nonexit);
998 12 : exit = single_pred_edge (header);
999 : }
1000 :
1001 569627 : edge entry = loop_preheader_edge (loop);
1002 :
1003 569627 : propagate_threaded_block_debug_into (nonexit->dest, entry->dest);
1004 569627 : 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 569627 : if (loop->header->count.initialized_p ())
1014 569509 : update_profile_after_ch (loop, bbs, copied_bbs, n_bbs,
1015 : candidate.invariant_exits,
1016 : candidate.static_exits,
1017 : entry_count);
1018 1139254 : delete candidate.static_exits;
1019 1139254 : delete candidate.invariant_exits;
1020 569627 : copied.safe_push (std::make_pair (entry, loop));
1021 :
1022 : /* If the loop has the form "for (i = j; i < j + 10; i++)" then
1023 : this copying can introduce a case where we rely on undefined
1024 : signed overflow to eliminate the preheader condition, because
1025 : we assume that "j < j + 10" is true. We don't want to warn
1026 : about that case for -Wstrict-overflow, because in general we
1027 : don't warn about overflow involving loops. Prevent the
1028 : warning by setting the no_warning flag in the condition. */
1029 569627 : if (warn_strict_overflow > 0)
1030 : {
1031 : unsigned int i;
1032 :
1033 115594 : for (i = 0; i < n_bbs; ++i)
1034 : {
1035 57878 : gimple_stmt_iterator bsi;
1036 :
1037 115756 : for (bsi = gsi_start_bb (copied_bbs[i]);
1038 289126 : !gsi_end_p (bsi);
1039 231248 : gsi_next (&bsi))
1040 : {
1041 231248 : gimple *stmt = gsi_stmt (bsi);
1042 231248 : if (gimple_code (stmt) == GIMPLE_COND)
1043 : {
1044 57878 : tree lhs = gimple_cond_lhs (stmt);
1045 57878 : if (gimple_cond_code (stmt) != EQ_EXPR
1046 54167 : && gimple_cond_code (stmt) != NE_EXPR
1047 31956 : && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1048 88986 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)))
1049 23326 : suppress_warning (stmt, OPT_Wstrict_overflow_);
1050 : }
1051 173370 : else if (is_gimple_assign (stmt))
1052 : {
1053 16095 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1054 16095 : tree rhs1 = gimple_assign_rhs1 (stmt);
1055 16095 : if (TREE_CODE_CLASS (rhs_code) == tcc_comparison
1056 : && rhs_code != EQ_EXPR
1057 541 : && rhs_code != NE_EXPR
1058 152 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1059 16239 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1)))
1060 38 : suppress_warning (stmt, OPT_Wstrict_overflow_);
1061 : }
1062 : }
1063 : }
1064 : }
1065 :
1066 : /* Update header of the loop. */
1067 569627 : loop->header = header;
1068 : /* Find correct latch. We only duplicate chain of conditionals so
1069 : there should be precisely two edges to the new header. One entry
1070 : edge and one to latch. */
1071 569627 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1072 569627 : if (header != e->src)
1073 : {
1074 569627 : loop->latch = e->src;
1075 569627 : break;
1076 : }
1077 : /* Ensure that the latch is simple. */
1078 569627 : if (!single_succ_p (loop_latch_edge (loop)->src))
1079 569627 : split_edge (loop_latch_edge (loop));
1080 :
1081 569627 : if (dump_file && (dump_flags & TDF_DETAILS))
1082 : {
1083 20 : if (do_while_loop_p (loop))
1084 19 : fprintf (dump_file, "Loop %d is now do-while loop.\n", loop->num);
1085 : else
1086 1 : fprintf (dump_file, "Loop %d is still not do-while loop.\n",
1087 : loop->num);
1088 20 : fprintf (dump_file, "Exit count: ");
1089 20 : exit_count.dump (dump_file);
1090 20 : fprintf (dump_file, "\nEntry count: ");
1091 20 : entry_count.dump (dump_file);
1092 20 : fprintf (dump_file, "\n");
1093 : }
1094 :
1095 : /* We possibly decreased number of iterations by 1. */
1096 569627 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1097 569627 : bool precise = (nexits == (int) exits.length ());
1098 : /* Check that loop may not terminate in other way than via
1099 : basic blocks we duplicated. */
1100 569627 : if (precise)
1101 : {
1102 383339 : basic_block *bbs = get_loop_body (loop);
1103 1905385 : for (unsigned i = 0; i < loop->num_nodes && precise; ++i)
1104 : {
1105 1522078 : basic_block bb = bbs[i];
1106 1522078 : bool found_exit = false;
1107 3183373 : FOR_EACH_EDGE (e, ei, bb->succs)
1108 1998341 : if (!flow_bb_inside_loop_p (loop, e->dest))
1109 : {
1110 : found_exit = true;
1111 : break;
1112 : }
1113 : /* If BB has exit, it was duplicated. */
1114 1522078 : if (found_exit)
1115 337046 : continue;
1116 : /* Give up on irreducible loops. */
1117 1185032 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1118 : {
1119 : precise = false;
1120 : break;
1121 : }
1122 : /* Check that inner loops are finite. */
1123 1517192 : for (class loop *l = bb->loop_father; l != loop && precise;
1124 332192 : l = loop_outer (l))
1125 342477 : if (!l->finite_p)
1126 : {
1127 : precise = false;
1128 : break;
1129 : }
1130 : /* Verify that there is no statement that may be terminate
1131 : execution in a way not visible to CFG. */
1132 2370000 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
1133 8688126 : !gsi_end_p (bsi); gsi_next (&bsi))
1134 7503126 : if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
1135 116461 : precise = false;
1136 : }
1137 383339 : free (bbs);
1138 : }
1139 569627 : if (precise
1140 569627 : && get_max_loop_iterations_int (loop) == 1)
1141 : {
1142 2810 : if (dump_file && (dump_flags & TDF_DETAILS))
1143 0 : fprintf (dump_file, "Loop %d no longer loops.\n", loop->num);
1144 2810 : scale_loop_profile (loop, profile_probability::always (), 0);
1145 2810 : loops_to_unloop.safe_push (loop);
1146 2810 : loops_to_unloop_nunroll.safe_push (0);
1147 : }
1148 566817 : else if (precise)
1149 : {
1150 298597 : if (dump_file && (dump_flags & TDF_DETAILS))
1151 11 : fprintf (dump_file,
1152 : "Peeled all exits:"
1153 : " decreased number of iterations of loop %d by 1.\n",
1154 : loop->num);
1155 298597 : adjust_loop_info_after_peeling (loop, 1, true);
1156 : }
1157 268220 : else if (exit_count >= entry_count.apply_scale (9, 10))
1158 : {
1159 154447 : if (dump_file && (dump_flags & TDF_DETAILS))
1160 5 : fprintf (dump_file,
1161 : "Peeled likely exits: likely decreased number "
1162 : "of iterations of loop %d by 1.\n", loop->num);
1163 154447 : adjust_loop_info_after_peeling (loop, 1, false);
1164 : }
1165 113773 : else if (dump_file && (dump_flags & TDF_DETAILS))
1166 4 : fprintf (dump_file,
1167 : "Not decreased number"
1168 : " of iterations of loop %d; likely exits remains.\n",
1169 : loop->num);
1170 :
1171 569627 : changed = true;
1172 569627 : }
1173 :
1174 449599 : if (changed)
1175 : {
1176 183545 : update_ssa (TODO_update_ssa);
1177 : /* After updating SSA form perform CSE on the loop header
1178 : copies. This is esp. required for the pass before
1179 : vectorization since nothing cleans up copied exit tests
1180 : that can now be simplified. CSE from the entry of the
1181 : region we copied till all loop exit blocks but not
1182 : entering the loop itself. */
1183 753172 : for (unsigned i = 0; i < copied.length (); ++i)
1184 : {
1185 569627 : edge entry = copied[i].first;
1186 569627 : loop_p loop = copied[i].second;
1187 569627 : auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
1188 569627 : bitmap exit_bbs = BITMAP_ALLOC (NULL);
1189 1599135 : for (unsigned j = 0; j < exit_edges.length (); ++j)
1190 1029508 : bitmap_set_bit (exit_bbs, exit_edges[j]->dest->index);
1191 569627 : bitmap_set_bit (exit_bbs, loop->header->index);
1192 569627 : do_rpo_vn (cfun, entry, exit_bbs);
1193 569627 : BITMAP_FREE (exit_bbs);
1194 569627 : }
1195 : }
1196 449599 : if (!loops_to_unloop.is_empty ())
1197 : {
1198 : /* Make sure loops are ordered inner to outer for unlooping. */
1199 766 : if (loops_to_unloop.length () != 1)
1200 : {
1201 352 : auto_vec<int, 8> order;
1202 704 : order.safe_grow (number_of_loops (cfun), true);
1203 352 : int i = 0;
1204 10741 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1205 9685 : order[loop->num] = i++;
1206 1056 : loops_to_unloop.sort (ch_order_loops, order.address ());
1207 352 : }
1208 766 : bool irred_invalidated;
1209 766 : auto_bitmap lc_invalidated;
1210 766 : auto_vec<edge> edges_to_remove;
1211 766 : unloop_loops (loops_to_unloop, loops_to_unloop_nunroll, edges_to_remove,
1212 : lc_invalidated, &irred_invalidated);
1213 766 : if (loops_state_satisfies_p (fun, LOOP_CLOSED_SSA)
1214 766 : && !bitmap_empty_p (lc_invalidated))
1215 10 : rewrite_into_loop_closed_ssa (NULL, 0);
1216 766 : changed = true;
1217 766 : }
1218 449599 : free (bbs);
1219 449599 : free (copied_bbs);
1220 :
1221 449599 : return changed ? TODO_cleanup_cfg : 0;
1222 449599 : }
1223 :
1224 : /* Initialize the loop structures we need, and finalize after. */
1225 :
1226 : unsigned int
1227 1042315 : pass_ch::execute (function *fun)
1228 : {
1229 1042315 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1230 1042315 : scev_initialize ();
1231 :
1232 1042315 : unsigned int res = copy_headers (fun);
1233 :
1234 1042315 : scev_finalize ();
1235 1042315 : loop_optimizer_finalize ();
1236 1042315 : return res;
1237 : }
1238 :
1239 : /* Assume an earlier phase has already initialized all the loop structures that
1240 : we need here (and perhaps others too), and that these will be finalized by
1241 : a later phase. */
1242 :
1243 : unsigned int
1244 208467 : pass_ch_vect::execute (function *fun)
1245 : {
1246 208467 : return copy_headers (fun);
1247 : }
1248 :
1249 : /* Apply header copying according to a very simple test of do-while shape. */
1250 :
1251 : bool
1252 681937 : pass_ch::process_loop_p (class loop *)
1253 : {
1254 681937 : return true;
1255 : }
1256 :
1257 : /* Apply header-copying to loops where we might enable vectorization. */
1258 :
1259 : bool
1260 500199 : pass_ch_vect::process_loop_p (class loop *loop)
1261 : {
1262 500199 : if (!flag_tree_loop_vectorize && !loop->force_vectorize)
1263 : return false;
1264 :
1265 497427 : if (loop->dont_vectorize)
1266 : return false;
1267 :
1268 : /* The vectorizer won't handle anything with multiple exits, so skip. */
1269 492823 : edge exit = single_exit (loop);
1270 492823 : if (!exit)
1271 : return false;
1272 :
1273 299937 : if (!do_while_loop_p (loop))
1274 : return true;
1275 :
1276 : return false;
1277 : }
1278 :
1279 : } // anon namespace
1280 :
1281 : gimple_opt_pass *
1282 285722 : make_pass_ch_vect (gcc::context *ctxt)
1283 : {
1284 285722 : return new pass_ch_vect (ctxt);
1285 : }
1286 :
1287 : gimple_opt_pass *
1288 285722 : make_pass_ch (gcc::context *ctxt)
1289 : {
1290 285722 : return new pass_ch (ctxt);
1291 : }
|
