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 783919 : get_range_query (class loop *loop,
53 : basic_block bb,
54 : gimple_ranger &ranger)
55 : {
56 783919 : auto_vec<basic_block, 8> path;
57 992766 : for (; bb != loop->header; bb = single_pred_edge (bb)->src)
58 208847 : path.safe_push (bb);
59 783919 : path.safe_push (loop->header);
60 783919 : path.safe_push (loop_preheader_edge (loop)->src);
61 783919 : return new path_range_query (ranger, path);
62 783919 : }
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 741590 : static_loop_exit (class loop *l, basic_block bb, gimple_ranger &ranger,
70 : path_range_query *&query)
71 : {
72 1483180 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
73 741590 : edge ret_e;
74 :
75 741590 : if (!last)
76 : return NULL;
77 :
78 741590 : edge true_e, false_e;
79 741590 : 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 741590 : if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e))
84 : return NULL;
85 :
86 741590 : int_range<1> desired_static_range;
87 741590 : if (loop_exit_edge_p (l, true_e))
88 : {
89 239671 : desired_static_range = range_false ();
90 239671 : ret_e = true_e;
91 : }
92 : else
93 : {
94 501919 : desired_static_range = range_true ();
95 501919 : ret_e = false_e;
96 : }
97 :
98 741590 : if (!query)
99 87124 : query = get_range_query (l, gimple_bb (last), ranger);
100 :
101 741590 : int_range<2> r;
102 741590 : if (!query->range_of_stmt (r, last))
103 : return NULL;
104 741590 : return r == desired_static_range ? ret_e : NULL;
105 741590 : }
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 1352677 : loop_static_stmt_p (class loop *loop,
113 : gimple_ranger &ranger,
114 : path_range_query *&query,
115 : gimple *stmt)
116 : {
117 1352677 : tree type = gimple_range_type (stmt);
118 1352677 : if (!type || !value_range::supports_type_p (type))
119 6966 : return false;
120 :
121 1345711 : if (!query)
122 696795 : query = get_range_query (loop, gimple_bb (stmt), ranger);
123 :
124 1345711 : value_range r (gimple_range_type (stmt));
125 1345711 : if (!query->range_of_stmt (r, stmt))
126 : return false;
127 1345711 : return r.singleton_p ();
128 1345711 : }
129 :
130 : /* Return true if OP is invariant. */
131 :
132 : static bool
133 2111894 : loop_invariant_op_p (class loop *loop,
134 : tree op)
135 : {
136 2111894 : if (is_gimple_min_invariant (op))
137 : return true;
138 1648102 : if (SSA_NAME_IS_DEFAULT_DEF (op)
139 1648102 : || !flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (op))))
140 280411 : return true;
141 1367691 : 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 16666 : loop_static_op_p (class loop *loop, tree op)
149 : {
150 : /* Always check for invariant first. */
151 33332 : 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 16666 : 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 674673 : loop_combined_static_and_iv_p (class loop *loop,
164 : tree op)
165 : {
166 : /* Always check for invariant first. */
167 1349346 : 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 674673 : 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 1451039 : 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 1451039 : gimple_stmt_iterator bsi;
207 :
208 1451039 : gcc_assert (!header->aux);
209 :
210 1451039 : gcc_assert (EDGE_COUNT (header->succs) > 0);
211 1451039 : if (single_succ_p (header))
212 : {
213 441279 : 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 441279 : return ch_impossible;
218 : }
219 :
220 1009760 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
221 1009760 : && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
222 : {
223 150408 : 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 150408 : 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 1040473 : 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 1718704 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
242 859352 : if (!last)
243 : {
244 50487 : 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 50487 : return ch_impossible;
249 : }
250 :
251 808865 : path_range_query *query = NULL;
252 2124739 : for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
253 1315874 : gsi_next (&psi))
254 2631748 : if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
255 : {
256 1800742 : bool static_p = loop_static_stmt_p (loop, *ranger,
257 900371 : query, psi.phi ());
258 1800742 : gimple_set_uid (psi.phi (), static_p ? 2 : 0);
259 : }
260 808865 : 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 3987041 : for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
266 : {
267 3178176 : gimple *last = gsi_stmt (bsi);
268 :
269 3178176 : if (gimple_code (last) == GIMPLE_LABEL)
270 11245 : continue;
271 :
272 3166931 : if (is_gimple_debug (last))
273 1522376 : continue;
274 :
275 1644555 : if (gimple_code (last) == GIMPLE_COND)
276 : break;
277 :
278 902895 : 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 902895 : if (gimple_code (last) == GIMPLE_CALL
285 902895 : && (!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 5976 : || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
289 : {
290 49354 : 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 49354 : if (query)
295 34752 : delete query;
296 49354 : return ch_impossible;
297 : }
298 :
299 : /* Classify the stmt is invariant in the loop. */
300 853541 : gimple_set_uid (last, 0);
301 1323325 : if (!gimple_vuse (last)
302 469784 : && gimple_code (last) != GIMPLE_ASM
303 1323249 : && (gimple_code (last) != GIMPLE_CALL
304 525 : || gimple_call_flags (last) & ECF_CONST))
305 : {
306 469599 : bool inv = true, static_p = false;
307 469599 : ssa_op_iter i;
308 469599 : tree op;
309 1080689 : FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
310 611090 : if (!loop_invariant_op_p (loop, op))
311 518314 : inv = false;
312 : /* Assume that code is reasonably optimized and invariant
313 : constants are already identified. */
314 469599 : if (!inv)
315 452306 : static_p = loop_static_stmt_p (loop, *ranger, query, last);
316 875938 : gimple_set_uid (last, (inv ? 1 : 0) | (static_p ? 2 : 0));
317 469599 : 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 469599 : if (inv || static_p)
332 80648 : 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 389046 : tree_code code;
339 389046 : if (gimple_code (last) == GIMPLE_ASSIGN
340 389046 : && ((code = gimple_assign_rhs_code (last)) == BIT_AND_EXPR
341 376725 : || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR))
342 : {
343 15410 : tree op1 = gimple_assign_rhs1 (last);
344 15410 : tree op2 = gimple_assign_rhs2 (last);
345 :
346 15410 : if ((loop_invariant_op_p (loop, op1)
347 14644 : || loop_combined_static_and_iv_p (loop, op1)
348 14642 : || loop_static_op_p (loop, op1))
349 16718 : && (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 772893 : int insns = estimate_num_insns (last, &eni_size_weights);
370 772893 : *limit -= insns;
371 772893 : if (insns)
372 664511 : code_size_cost = true;
373 772893 : if (dump_file && (dump_flags & TDF_DETAILS))
374 42 : fprintf (dump_file,
375 : " Acconting stmt as %i insns\n", insns);
376 772893 : if (*limit < 0)
377 : {
378 17851 : 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 17851 : if (query)
383 7507 : delete query;
384 17851 : return ch_impossible;
385 : }
386 : }
387 :
388 741660 : 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 741660 : tree lhs = gimple_cond_lhs (last);
397 741660 : tree rhs = gimple_cond_rhs (last);
398 741660 : bool lhs_invariant = loop_invariant_op_p (loop, lhs);
399 741660 : 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 741660 : if (lhs_invariant != rhs_invariant
423 658005 : && (lhs_invariant
424 556697 : || loop_combined_static_and_iv_p (loop, lhs))
425 843038 : && (rhs_invariant
426 101308 : || 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 741590 : edge static_exit = static_loop_exit (loop, header, *ranger, query);
437 741590 : if (query)
438 741590 : delete query;
439 :
440 741590 : if (static_exit && static_exits)
441 : {
442 324405 : static_exits->add (static_exit);
443 324405 : 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 741590 : if (lhs_invariant && rhs_invariant)
450 : {
451 4550 : if (invariant_exits)
452 : {
453 4550 : edge e;
454 4550 : edge_iterator ei;
455 13650 : FOR_EACH_EDGE (e, ei, header->succs)
456 9100 : if (loop_exit_edge_p (loop, e))
457 : {
458 4550 : 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 4550 : invariant_exits->add (e);
463 : }
464 : }
465 4550 : return ch_win_invariant_exit;
466 : }
467 737040 : 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 285167 : edge e;
473 285167 : edge_iterator ei;
474 285167 : bool hasone = false;
475 855501 : FOR_EACH_EDGE (e, ei, header->succs)
476 570334 : if (loop_exit_edge_p (loop, e)
477 570334 : && probably_never_executed_edge_p (cfun, e))
478 : {
479 6264 : hasone = true;
480 6264 : 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 285167 : if (hasone)
486 6264 : return ch_win_invariant_exit;
487 : }
488 730776 : *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 730776 : if (static_exit)
496 640592 : return !code_size_cost ? ch_possible_zero_cost : ch_possible;
497 :
498 : /* We was not able to prove that conditional will be eliminated. */
499 406412 : int insns = estimate_num_insns (last, &eni_size_weights);
500 406412 : *limit -= insns;
501 406412 : if (dump_file && (dump_flags & TDF_DETAILS))
502 19 : fprintf (dump_file,
503 : " Acconting stmt as %i insns\n", insns);
504 406412 : if (*limit < 0)
505 : {
506 10579 : 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 10579 : 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 882190 : do_while_loop_p (class loop *loop)
520 : {
521 882190 : 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 882190 : if (stmt
525 882190 : && gimple_code (stmt) != GIMPLE_LABEL)
526 : {
527 562625 : 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 562625 : return false;
532 : }
533 :
534 : /* If the latch does not have a single predecessor, it is not a
535 : do-while loop. */
536 319565 : if (!single_pred_p (loop->latch))
537 : {
538 23309 : 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 23309 : return false;
543 : }
544 296256 : 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 296256 : if (!loop_exits_from_bb_p (loop, pred))
549 : {
550 8208 : 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 8208 : return false;
555 : }
556 576096 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
557 287158 : if (last
558 287158 : && (gimple_cond_lhs (last) == boolean_false_node
559 287158 : || 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 288047 : 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 565813 : 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 1141151 : for (unsigned int i = 0; i < n_region; i++)
620 : {
621 575338 : edge exit_e, exit_e_copy, e, e_copy;
622 575338 : 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 575338 : gcc_checking_assert (EDGE_COUNT (region[i]->succs) == 2);
630 575338 : if (loop_exit_edge_p (loop,
631 575338 : EDGE_SUCC (region[i], 0)))
632 : {
633 135688 : exit_e = EDGE_SUCC (region[i], 0);
634 135688 : exit_e_copy = EDGE_SUCC (region_copy[i], 0);
635 135688 : e = EDGE_SUCC (region[i], 1);
636 135688 : e_copy = EDGE_SUCC (region_copy[i], 1);
637 : }
638 : else
639 : {
640 439650 : exit_e = EDGE_SUCC (region[i], 1);
641 439650 : exit_e_copy = EDGE_SUCC (region_copy[i], 1);
642 439650 : e = EDGE_SUCC (region[i], 0);
643 439650 : e_copy = EDGE_SUCC (region_copy[i], 0);
644 : }
645 575338 : gcc_assert (i == n_region - 1
646 : || (e->dest == region[i + 1]
647 : && e_copy->dest == region_copy[i + 1]));
648 575338 : region_copy[i]->count = entry_count;
649 575338 : profile_count exit_e_count = exit_e->count ();
650 575338 : bool was_static = false;
651 575338 : if (static_exits->contains (exit_e))
652 : {
653 : /* Update profile and the conditional.
654 : CFG update is done by caller. */
655 316902 : static_exits->remove (exit_e);
656 316902 : was_static = true;
657 316902 : e_copy->probability = profile_probability::always ();
658 316902 : exit_e_copy->probability = profile_probability::never ();
659 316902 : gcond *cond_stmt
660 633804 : = as_a <gcond *>(*gsi_last_bb (region_copy[i]));
661 316902 : if (e_copy->flags & EDGE_TRUE_VALUE)
662 228529 : gimple_cond_make_true (cond_stmt);
663 : else
664 88373 : gimple_cond_make_false (cond_stmt);
665 316902 : 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 316902 : update_bb_profile_for_threading (region[i], entry_count, e);
669 : }
670 : else
671 258436 : region[i]->count -= region_copy[i]->count;
672 575338 : if (invariant_exits->contains (exit_e))
673 : {
674 4546 : 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 9041 : if (entry_count.nonzero_p () && !was_static)
680 4456 : set_edge_probability_and_rescale_others
681 4456 : (exit_e_copy, exit_e_count.probability_in
682 : (entry_count));
683 : /* Eliminate in-loop conditional. */
684 4546 : e->probability = profile_probability::always ();
685 4546 : exit_e->probability = profile_probability::never ();
686 9092 : gcond *cond_stmt = as_a <gcond *>(*gsi_last_bb (region[i]));
687 4546 : if (e->flags & EDGE_TRUE_VALUE)
688 1975 : gimple_cond_make_true (cond_stmt);
689 : else
690 2571 : gimple_cond_make_false (cond_stmt);
691 4546 : update_stmt (cond_stmt);
692 : }
693 575338 : 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 565813 : gcc_checking_assert (invariant_exits->is_empty ());
698 565813 : }
699 :
700 : namespace {
701 :
702 : /* Common superclass for both header-copying phases. */
703 : class ch_base : public gimple_opt_pass
704 : {
705 : protected:
706 866325 : ch_base (pass_data data, gcc::context *ctxt)
707 1732650 : : 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 577550 : pass_ch (gcc::context *ctxt)
734 577550 : : ch_base (pass_data_ch, ctxt)
735 577550 : {}
736 :
737 : /* opt_pass methods: */
738 1044403 : 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 288775 : 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 288775 : pass_ch_vect (gcc::context *ctxt)
770 288775 : : ch_base (pass_data_ch_vect, ctxt)
771 288775 : {}
772 :
773 : /* opt_pass methods: */
774 240526 : bool gate (function *fun) final override
775 : {
776 240526 : return flag_tree_ch != 0
777 240526 : && (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 45749 : ch_order_loops (const void *a_, const void *b_, void *order_)
792 : {
793 45749 : int *order = (int *)order_;
794 45749 : const class loop *a = *(const class loop * const *)a_;
795 45749 : const class loop *b = *(const class loop * const *)b_;
796 45749 : if (a->num == b->num)
797 : return 0;
798 45749 : if (order[a->num] < order[b->num])
799 22248 : 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 1251607 : ch_base::copy_headers (function *fun)
809 : {
810 1251607 : basic_block *bbs, *copied_bbs;
811 1251607 : unsigned bbs_size;
812 1251607 : bool changed = false;
813 :
814 2503214 : if (number_of_loops (fun) <= 1)
815 : return 0;
816 :
817 447610 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
818 447610 : copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
819 447610 : bbs_size = n_basic_blocks_for_fn (fun);
820 :
821 447610 : struct candidate
822 : {
823 : class loop *loop;
824 : unsigned int nheaders;
825 : hash_set <edge> *invariant_exits, *static_exits;
826 : };
827 447610 : auto_vec<struct candidate> candidates;
828 447610 : auto_vec<std::pair<edge, loop_p> > copied;
829 447610 : auto_vec<class loop *> loops_to_unloop;
830 447610 : auto_vec<int> loops_to_unloop_nunroll;
831 :
832 447610 : mark_dfs_back_edges ();
833 447610 : gimple_ranger *ranger = new gimple_ranger;
834 2526829 : for (auto loop : loops_list (cfun, 0))
835 : {
836 1183999 : int initial_limit = optimize_loop_for_speed_p (loop)
837 1183999 : ? param_max_loop_header_insns : 0;
838 1183999 : int remaining_limit = initial_limit;
839 1183999 : 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 1183999 : if (!loop_has_exit_edges (loop)
848 1183999 : || !process_loop_p (loop))
849 464041 : continue;
850 :
851 720004 : basic_block header = loop->header;
852 720004 : estimate_numbers_of_iterations (loop);
853 720004 : 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 719958 : unsigned int nheaders = 0;
869 719958 : unsigned int last_win_nheaders = 0;
870 719958 : bool last_win_invariant_exit = false;
871 719958 : ch_decision ret;
872 719958 : auto_vec <ch_decision, 32> decision;
873 719958 : hash_set <edge> *invariant_exits = new hash_set <edge>;
874 719958 : hash_set <edge> *static_exits = new hash_set <edge>;
875 719958 : bool canbe_neverexecuted = true;
876 719958 : while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
877 : &remaining_limit,
878 : invariant_exits,
879 : static_exits,
880 : &canbe_neverexecuted))
881 1451039 : != ch_impossible)
882 : {
883 731081 : nheaders++;
884 731081 : decision.safe_push (ret);
885 731081 : if (ret >= ch_win)
886 : {
887 10884 : last_win_nheaders = nheaders;
888 10884 : last_win_invariant_exit = (ret == ch_win_invariant_exit);
889 10884 : 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 720197 : 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 731081 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
900 495187 : header = EDGE_SUCC (header, 0)->dest;
901 : else
902 235894 : 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 719958 : if (last_win_nheaders && last_win_invariant_exit
908 9023 : && nheaders > last_win_nheaders)
909 : {
910 2727 : last_win_nheaders++;
911 2727 : if (dump_file && (dump_flags & TDF_DETAILS))
912 6 : fprintf (dump_file,
913 : " Duplicating additional BB to obtain do-while loop\n");
914 : }
915 717231 : else if (!last_win_nheaders && nheaders && !do_while_loop_p (loop))
916 : {
917 552143 : last_win_nheaders = 1;
918 552143 : 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 1447804 : while (last_win_nheaders < decision.length ()
925 856169 : && decision[last_win_nheaders] == ch_possible_zero_cost)
926 : {
927 7888 : 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 7888 : last_win_nheaders++;
931 : }
932 :
933 719958 : if (last_win_nheaders)
934 565931 : candidates.safe_push ({loop, last_win_nheaders,
935 : invariant_exits, static_exits});
936 : else
937 : {
938 154027 : delete invariant_exits;
939 154027 : delete static_exits;
940 : }
941 719958 : }
942 : /* Do not use ranger after we change the IL and not have updated SSA. */
943 447610 : delete ranger;
944 :
945 1378323 : for (auto candidate : candidates)
946 : {
947 565931 : class loop *loop = candidate.loop;
948 565931 : if (dump_file && (dump_flags & TDF_DETAILS))
949 20 : fprintf (dump_file,
950 : "Copying headers of loop %i\n", loop->num);
951 :
952 565931 : basic_block header = loop->header;
953 565931 : edge nonexit = NULL;
954 565931 : edge exit = NULL;
955 565931 : unsigned int n_bbs = 0;
956 565931 : int nexits = 0;
957 565931 : profile_count exit_count = profile_count::zero ();
958 565931 : profile_count entry_count = profile_count::zero ();
959 565931 : edge e;
960 565931 : edge_iterator ei;
961 :
962 1697793 : FOR_EACH_EDGE (e, ei, loop->header->preds)
963 1131862 : if (e->src != loop->latch)
964 565931 : entry_count += e->count ();
965 1141388 : while (n_bbs < candidate.nheaders)
966 : {
967 575457 : 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 575457 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
972 : {
973 439729 : nonexit = EDGE_SUCC (header, 0);
974 439729 : exit = EDGE_SUCC (header, 1);
975 : }
976 : else
977 : {
978 135728 : nonexit = EDGE_SUCC (header, 1);
979 135728 : exit = EDGE_SUCC (header, 0);
980 : }
981 575457 : exit_count += exit->count ();
982 575457 : nexits++;
983 575457 : bbs[n_bbs++] = header;
984 575457 : gcc_assert (bbs_size > n_bbs);
985 575457 : header = nonexit->dest;
986 : }
987 :
988 565931 : 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 565931 : if (!single_pred_p (nonexit->dest))
996 : {
997 12 : header = split_edge (nonexit);
998 12 : exit = single_pred_edge (header);
999 : }
1000 :
1001 565931 : edge entry = loop_preheader_edge (loop);
1002 :
1003 565931 : propagate_threaded_block_debug_into (nonexit->dest, entry->dest);
1004 565931 : 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 565931 : if (loop->header->count.initialized_p ())
1014 565813 : update_profile_after_ch (loop, bbs, copied_bbs, n_bbs,
1015 : candidate.invariant_exits,
1016 : candidate.static_exits,
1017 : entry_count);
1018 1131862 : delete candidate.static_exits;
1019 1131862 : delete candidate.invariant_exits;
1020 565931 : 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 565931 : if (warn_strict_overflow > 0)
1030 : {
1031 : unsigned int i;
1032 :
1033 116838 : for (i = 0; i < n_bbs; ++i)
1034 : {
1035 58504 : gimple_stmt_iterator bsi;
1036 :
1037 117008 : for (bsi = gsi_start_bb (copied_bbs[i]);
1038 292672 : !gsi_end_p (bsi);
1039 234168 : gsi_next (&bsi))
1040 : {
1041 234168 : gimple *stmt = gsi_stmt (bsi);
1042 234168 : if (gimple_code (stmt) == GIMPLE_COND)
1043 : {
1044 58504 : tree lhs = gimple_cond_lhs (stmt);
1045 58504 : if (gimple_cond_code (stmt) != EQ_EXPR
1046 54793 : && gimple_cond_code (stmt) != NE_EXPR
1047 32246 : && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1048 89902 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)))
1049 23359 : suppress_warning (stmt, OPT_Wstrict_overflow_);
1050 : }
1051 175664 : else if (is_gimple_assign (stmt))
1052 : {
1053 16402 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1054 16402 : tree rhs1 = gimple_assign_rhs1 (stmt);
1055 16402 : if (TREE_CODE_CLASS (rhs_code) == tcc_comparison
1056 : && rhs_code != EQ_EXPR
1057 589 : && rhs_code != NE_EXPR
1058 152 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1059 16546 : && 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 565931 : 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 565931 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1072 565931 : if (header != e->src)
1073 : {
1074 565931 : loop->latch = e->src;
1075 565931 : break;
1076 : }
1077 : /* Ensure that the latch is simple. */
1078 565931 : if (!single_succ_p (loop_latch_edge (loop)->src))
1079 565931 : split_edge (loop_latch_edge (loop));
1080 :
1081 565931 : 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 565931 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1097 565931 : bool precise = (nexits == (int) exits.length ());
1098 : /* Check that loop may not terminate in other way than via
1099 : basic blocks we duplicated. */
1100 565931 : if (precise)
1101 : {
1102 380372 : basic_block *bbs = get_loop_body (loop);
1103 1891229 : for (unsigned i = 0; i < loop->num_nodes && precise; ++i)
1104 : {
1105 1510889 : basic_block bb = bbs[i];
1106 1510889 : bool found_exit = false;
1107 3158938 : FOR_EACH_EDGE (e, ei, bb->succs)
1108 1981932 : 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 1510889 : if (found_exit)
1115 333883 : continue;
1116 : /* Give up on irreducible loops. */
1117 1177006 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1118 : {
1119 : precise = false;
1120 : break;
1121 : }
1122 : /* Check that inner loops are finite. */
1123 1508865 : for (class loop *l = bb->loop_father; l != loop && precise;
1124 331891 : l = loop_outer (l))
1125 342180 : 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 2353948 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
1133 8513127 : !gsi_end_p (bsi); gsi_next (&bsi))
1134 7336153 : if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
1135 115959 : precise = false;
1136 : }
1137 380372 : free (bbs);
1138 : }
1139 565931 : if (precise
1140 565931 : && get_max_loop_iterations_int (loop) == 1)
1141 : {
1142 2829 : if (dump_file && (dump_flags & TDF_DETAILS))
1143 0 : fprintf (dump_file, "Loop %d no longer loops.\n", loop->num);
1144 2829 : scale_loop_profile (loop, profile_probability::always (), 0);
1145 2829 : loops_to_unloop.safe_push (loop);
1146 2829 : loops_to_unloop_nunroll.safe_push (0);
1147 : }
1148 563102 : else if (precise)
1149 : {
1150 296241 : 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 296241 : adjust_loop_info_after_peeling (loop, 1, true);
1156 : }
1157 266861 : else if (exit_count >= entry_count.apply_scale (9, 10))
1158 : {
1159 154015 : 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 154015 : adjust_loop_info_after_peeling (loop, 1, false);
1164 : }
1165 112846 : 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 565931 : changed = true;
1172 565931 : }
1173 :
1174 447610 : if (changed)
1175 : {
1176 182391 : 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 748322 : for (unsigned i = 0; i < copied.length (); ++i)
1184 : {
1185 565931 : edge entry = copied[i].first;
1186 565931 : loop_p loop = copied[i].second;
1187 565931 : auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
1188 565931 : bitmap exit_bbs = BITMAP_ALLOC (NULL);
1189 1597561 : for (unsigned j = 0; j < exit_edges.length (); ++j)
1190 1031630 : bitmap_set_bit (exit_bbs, exit_edges[j]->dest->index);
1191 565931 : bitmap_set_bit (exit_bbs, loop->header->index);
1192 565931 : do_rpo_vn (cfun, entry, exit_bbs);
1193 565931 : BITMAP_FREE (exit_bbs);
1194 565931 : }
1195 : }
1196 447610 : if (!loops_to_unloop.is_empty ())
1197 : {
1198 : /* Make sure loops are ordered inner to outer for unlooping. */
1199 780 : if (loops_to_unloop.length () != 1)
1200 : {
1201 358 : auto_vec<int, 8> order;
1202 716 : order.safe_grow (number_of_loops (cfun), true);
1203 358 : int i = 0;
1204 10768 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1205 9694 : order[loop->num] = i++;
1206 1074 : loops_to_unloop.sort (ch_order_loops, order.address ());
1207 358 : }
1208 780 : bool irred_invalidated;
1209 780 : auto_bitmap lc_invalidated;
1210 780 : auto_vec<edge> edges_to_remove;
1211 780 : unloop_loops (loops_to_unloop, loops_to_unloop_nunroll, edges_to_remove,
1212 : lc_invalidated, &irred_invalidated);
1213 780 : if (loops_state_satisfies_p (fun, LOOP_CLOSED_SSA)
1214 780 : && !bitmap_empty_p (lc_invalidated))
1215 10 : rewrite_into_loop_closed_ssa (NULL, 0);
1216 780 : changed = true;
1217 780 : }
1218 447610 : free (bbs);
1219 447610 : free (copied_bbs);
1220 :
1221 447610 : return changed ? TODO_cleanup_cfg : 0;
1222 447610 : }
1223 :
1224 : /* Initialize the loop structures we need, and finalize after. */
1225 :
1226 : unsigned int
1227 1044184 : pass_ch::execute (function *fun)
1228 : {
1229 1044184 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1230 1044184 : scev_initialize ();
1231 :
1232 1044184 : unsigned int res = copy_headers (fun);
1233 :
1234 1044184 : scev_finalize ();
1235 1044184 : loop_optimizer_finalize ();
1236 1044184 : 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 207423 : pass_ch_vect::execute (function *fun)
1245 : {
1246 207423 : return copy_headers (fun);
1247 : }
1248 :
1249 : /* Apply header copying according to a very simple test of do-while shape. */
1250 :
1251 : bool
1252 678005 : pass_ch::process_loop_p (class loop *)
1253 : {
1254 678005 : return true;
1255 : }
1256 :
1257 : /* Apply header-copying to loops where we might enable vectorization. */
1258 :
1259 : bool
1260 496132 : pass_ch_vect::process_loop_p (class loop *loop)
1261 : {
1262 496132 : if (!flag_tree_loop_vectorize && !loop->force_vectorize)
1263 : return false;
1264 :
1265 493360 : if (loop->dont_vectorize)
1266 : return false;
1267 :
1268 : /* The vectorizer won't handle anything with multiple exits, so skip. */
1269 488755 : edge exit = single_exit (loop);
1270 488755 : if (!exit)
1271 : return false;
1272 :
1273 296813 : if (!do_while_loop_p (loop))
1274 : return true;
1275 :
1276 : return false;
1277 : }
1278 :
1279 : } // anon namespace
1280 :
1281 : gimple_opt_pass *
1282 288775 : make_pass_ch_vect (gcc::context *ctxt)
1283 : {
1284 288775 : return new pass_ch_vect (ctxt);
1285 : }
1286 :
1287 : gimple_opt_pass *
1288 288775 : make_pass_ch (gcc::context *ctxt)
1289 : {
1290 288775 : return new pass_ch (ctxt);
1291 : }
|
