Branch data Line data Source code
1 : : /* Loop header copying on trees.
2 : : Copyright (C) 2004-2025 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 : 713328 : get_range_query (class loop *loop,
53 : : basic_block bb,
54 : : gimple_ranger &ranger)
55 : : {
56 : 713328 : auto_vec<basic_block, 8> path;
57 : 892168 : for (; bb != loop->header; bb = single_pred_edge (bb)->src)
58 : 178840 : path.safe_push (bb);
59 : 713328 : path.safe_push (loop->header);
60 : 713328 : path.safe_push (loop_preheader_edge (loop)->src);
61 : 713328 : return new path_range_query (ranger, path);
62 : 713328 : }
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 : 673422 : static_loop_exit (class loop *l, basic_block bb, gimple_ranger &ranger,
70 : : path_range_query *&query)
71 : : {
72 : 1346844 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
73 : 673422 : edge ret_e;
74 : :
75 : 673422 : if (!last)
76 : 0 : return NULL;
77 : :
78 : 673422 : edge true_e, false_e;
79 : 673422 : 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 : 673422 : if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e))
84 : : return NULL;
85 : :
86 : 673422 : int_range<1> desired_static_range;
87 : 673422 : if (loop_exit_edge_p (l, true_e))
88 : : {
89 : 222919 : desired_static_range = range_false ();
90 : 222919 : ret_e = true_e;
91 : : }
92 : : else
93 : : {
94 : 450503 : desired_static_range = range_true ();
95 : 450503 : ret_e = false_e;
96 : : }
97 : :
98 : 673422 : if (!query)
99 : 72021 : query = get_range_query (l, gimple_bb (last), ranger);
100 : :
101 : 673422 : int_range<2> r;
102 : 673422 : if (!query->range_of_stmt (r, last))
103 : : return NULL;
104 : 673422 : return r == desired_static_range ? ret_e : NULL;
105 : 673422 : }
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 : 1270732 : loop_static_stmt_p (class loop *loop,
113 : : gimple_ranger &ranger,
114 : : path_range_query *&query,
115 : : gimple *stmt)
116 : : {
117 : 1270732 : tree type = gimple_range_type (stmt);
118 : 1270732 : if (!type || !value_range::supports_type_p (type))
119 : 6943 : return false;
120 : :
121 : 1263789 : if (!query)
122 : 641307 : query = get_range_query (loop, gimple_bb (stmt), ranger);
123 : :
124 : 1263789 : value_range r (gimple_range_type (stmt));
125 : 1263789 : if (!query->range_of_stmt (r, stmt))
126 : : return false;
127 : 1263789 : return r.singleton_p ();
128 : 1263789 : }
129 : :
130 : : /* Return true if OP is invariant. */
131 : :
132 : : static bool
133 : 1959473 : loop_invariant_op_p (class loop *loop,
134 : : tree op)
135 : : {
136 : 1959473 : if (is_gimple_min_invariant (op))
137 : : return true;
138 : 1533524 : if (SSA_NAME_IS_DEFAULT_DEF (op)
139 : 1533524 : || !flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (op))))
140 : 257893 : return true;
141 : 1275631 : 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 : 19352 : loop_static_op_p (class loop *loop, tree op)
149 : : {
150 : : /* Always check for invariant first. */
151 : 38704 : 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 : 19352 : 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 : 620626 : loop_combined_static_and_iv_p (class loop *loop,
164 : : tree op)
165 : : {
166 : : /* Always check for invariant first. */
167 : 1241252 : 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 : 620626 : 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 : : /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
192 : : instructions should be duplicated, limit is decreased by the actual
193 : : amount. */
194 : :
195 : : static ch_decision
196 : 1332944 : should_duplicate_loop_header_p (basic_block header, class loop *loop,
197 : : gimple_ranger *ranger,
198 : : int *limit,
199 : : hash_set <edge> *invariant_exits,
200 : : hash_set <edge> *static_exits)
201 : : {
202 : 1332944 : gimple_stmt_iterator bsi;
203 : :
204 : 1332944 : gcc_assert (!header->aux);
205 : :
206 : 1332944 : gcc_assert (EDGE_COUNT (header->succs) > 0);
207 : 1332944 : if (single_succ_p (header))
208 : : {
209 : 412475 : if (dump_file && (dump_flags & TDF_DETAILS))
210 : 15 : fprintf (dump_file,
211 : : " Not duplicating bb %i: it is single succ.\n",
212 : : header->index);
213 : 412475 : return ch_impossible;
214 : : }
215 : :
216 : 920469 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
217 : 920469 : && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
218 : : {
219 : 130762 : if (dump_file && (dump_flags & TDF_DETAILS))
220 : 2 : fprintf (dump_file,
221 : : " Not duplicating bb %i: both successors are in loop.\n",
222 : : loop->num);
223 : 130762 : return ch_impossible;
224 : : }
225 : :
226 : : /* If this is not the original loop header, we want it to have just
227 : : one predecessor in order to match the && pattern. */
228 : 952293 : if (header != loop->header && !single_pred_p (header))
229 : : {
230 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
231 : 0 : fprintf (dump_file,
232 : : " Not duplicating bb %i: it has mutiple predecestors.\n",
233 : : header->index);
234 : 0 : return ch_impossible;
235 : : }
236 : :
237 : 1579414 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
238 : 789707 : if (!last)
239 : : {
240 : 53574 : if (dump_file && (dump_flags & TDF_DETAILS))
241 : 0 : fprintf (dump_file,
242 : : " Not duplicating bb %i: it does not end by conditional.\n",
243 : : header->index);
244 : 53574 : return ch_impossible;
245 : : }
246 : :
247 : 736133 : path_range_query *query = NULL;
248 : 1954937 : for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
249 : 1218804 : gsi_next (&psi))
250 : 2437608 : if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
251 : : {
252 : 1669884 : bool static_p = loop_static_stmt_p (loop, *ranger,
253 : 834942 : query, psi.phi ());
254 : 1669884 : gimple_set_uid (psi.phi (), static_p ? 2 : 0);
255 : : }
256 : 736133 : bool code_size_cost = false;
257 : :
258 : : /* Count number of instructions and punt on calls.
259 : : Populate stmts INV flag to later apply heuristics to the
260 : : kind of conditions we want to copy. */
261 : 3527585 : for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
262 : : {
263 : 2791452 : gimple *last = gsi_stmt (bsi);
264 : :
265 : 2791452 : if (gimple_code (last) == GIMPLE_LABEL)
266 : 8920 : continue;
267 : :
268 : 2782532 : if (is_gimple_debug (last))
269 : 1258640 : continue;
270 : :
271 : 1523892 : if (gimple_code (last) == GIMPLE_COND)
272 : : break;
273 : :
274 : 850401 : if (dump_file && (dump_flags & TDF_DETAILS))
275 : : {
276 : 44 : fprintf (dump_file, " Analyzing: ");
277 : 44 : print_gimple_stmt (dump_file, last, 0, TDF_SLIM);
278 : : }
279 : :
280 : 850401 : if (gimple_code (last) == GIMPLE_CALL
281 : 850401 : && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
282 : : /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
283 : : at current loop's header. Don't copy in this case. */
284 : 5502 : || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
285 : : {
286 : 45737 : if (dump_file && (dump_flags & TDF_DETAILS))
287 : 0 : fprintf (dump_file,
288 : : " Not duplicating bb %i: it contains call.\n",
289 : : header->index);
290 : 45737 : if (query)
291 : 32530 : delete query;
292 : 45737 : return ch_impossible;
293 : : }
294 : :
295 : : /* Classify the stmt is invariant in the loop. */
296 : 804664 : gimple_set_uid (last, 0);
297 : 1256973 : if (!gimple_vuse (last)
298 : 452309 : && gimple_code (last) != GIMPLE_ASM
299 : 1256897 : && (gimple_code (last) != GIMPLE_CALL
300 : 468 : || gimple_call_flags (last) & ECF_CONST))
301 : : {
302 : 452126 : bool inv = true, static_p = false;
303 : 452126 : ssa_op_iter i;
304 : 452126 : tree op;
305 : 1044419 : FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
306 : 592293 : if (!loop_invariant_op_p (loop, op))
307 : 503611 : inv = false;
308 : : /* Assume that code is reasonably optimized and invariant
309 : : constants are already identified. */
310 : 452126 : if (!inv)
311 : 435790 : static_p = loop_static_stmt_p (loop, *ranger, query, last);
312 : 849804 : gimple_set_uid (last, (inv ? 1 : 0) | (static_p ? 2 : 0));
313 : 452126 : if (dump_file && (dump_flags & TDF_DETAILS))
314 : : {
315 : 32 : if (inv)
316 : 6 : fprintf (dump_file, " Stmt is loop invariant\n");
317 : 32 : if (static_p)
318 : 3 : fprintf (dump_file, " Stmt is static "
319 : : "(constant in the first iteration)\n");
320 : : }
321 : : /* Loop invariants will be optimized out in loop body after
322 : : duplication; do not account invariant computation in code
323 : : size costs.
324 : :
325 : : Similarly static computations will be optimized out in the
326 : : duplicatd header. */
327 : 452126 : if (inv || static_p)
328 : 70898 : continue;
329 : :
330 : : /* Match the following:
331 : : _1 = i_1 < 10 <- static condtion
332 : : _2 = n != 0 <- loop invariant condition
333 : : _3 = _1 & _2 <- combined static and iv statement. */
334 : 381342 : tree_code code;
335 : 381342 : if (gimple_code (last) == GIMPLE_ASSIGN
336 : 381342 : && ((code = gimple_assign_rhs_code (last)) == BIT_AND_EXPR
337 : 367537 : || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR))
338 : : {
339 : 18010 : tree op1 = gimple_assign_rhs1 (last);
340 : 18010 : tree op2 = gimple_assign_rhs2 (last);
341 : :
342 : 18010 : if ((loop_invariant_op_p (loop, op1)
343 : 17233 : || loop_combined_static_and_iv_p (loop, op1)
344 : 17228 : || loop_static_op_p (loop, op1))
345 : 19421 : && (loop_invariant_op_p (loop, op2)
346 : 2124 : || loop_combined_static_and_iv_p (loop, op2)
347 : 2124 : || loop_static_op_p (loop, op2)))
348 : : {
349 : : /* Duplicating loop header with combned conditional will
350 : : remove this statement in each copy. But we account for
351 : : that later when seeing that condition.
352 : :
353 : : Note that this may be overly optimistic for bit operations
354 : : where the static parameter may still result in non-trivial
355 : : bit operation. */
356 : 114 : gimple_set_uid (last, 4);
357 : 114 : if (dump_file && (dump_flags & TDF_DETAILS))
358 : 1 : fprintf (dump_file,
359 : : " Stmt combines static and invariant op\n");
360 : 114 : continue;
361 : : }
362 : : }
363 : : }
364 : :
365 : 733766 : int insns = estimate_num_insns (last, &eni_size_weights);
366 : 733766 : *limit -= insns;
367 : 733766 : if (insns)
368 : 624986 : code_size_cost = true;
369 : 733766 : if (dump_file && (dump_flags & TDF_DETAILS))
370 : 34 : fprintf (dump_file,
371 : : " Acconting stmt as %i insns\n", insns);
372 : 733766 : if (*limit < 0)
373 : : {
374 : 16905 : if (dump_file && (dump_flags & TDF_DETAILS))
375 : 0 : fprintf (dump_file,
376 : : " Not duplicating bb %i contains too many insns.\n",
377 : : header->index);
378 : 16905 : if (query)
379 : 7307 : delete query;
380 : 16905 : return ch_impossible;
381 : : }
382 : : }
383 : :
384 : 673491 : if (dump_file && (dump_flags & TDF_DETAILS))
385 : : {
386 : 25 : fprintf (dump_file, " Analyzing: ");
387 : 25 : print_gimple_stmt (dump_file, last, 0, TDF_SLIM);
388 : : }
389 : :
390 : : /* If the condition tests a non-IV loop variant we do not want to rotate
391 : : the loop further. Unless this is the original loop header. */
392 : 673491 : tree lhs = gimple_cond_lhs (last);
393 : 673491 : tree rhs = gimple_cond_rhs (last);
394 : 673491 : bool lhs_invariant = loop_invariant_op_p (loop, lhs);
395 : 673491 : bool rhs_invariant = loop_invariant_op_p (loop, rhs);
396 : :
397 : : /* Combined conditional is a result of if combining:
398 : :
399 : : _1 = i_1 < 10 <- static condtion
400 : : _2 = n != 0 <- loop invariant condition
401 : : _3 = _1 & _2 <- combined static and iv statement
402 : : if (_3 != 0) <- combined conditional
403 : :
404 : : Combined conditionals will not be optimized out in either copy.
405 : : However duplicaed header simplifies to:
406 : :
407 : : if (n < 10)
408 : :
409 : : while loop body to
410 : :
411 : : if (i_1 < 10)
412 : :
413 : : So effectively the resulting code sequence will be of same length as
414 : : the original code.
415 : :
416 : : Combined conditionals are never static or invariant, so save some work
417 : : below. */
418 : 673491 : if (lhs_invariant != rhs_invariant
419 : 601269 : && (lhs_invariant
420 : 505950 : || loop_combined_static_and_iv_p (loop, lhs))
421 : 768879 : && (rhs_invariant
422 : 95319 : || loop_combined_static_and_iv_p (loop, rhs)))
423 : : {
424 : 69 : if (query)
425 : 69 : delete query;
426 : 69 : if (dump_file && (dump_flags & TDF_DETAILS))
427 : 1 : fprintf (dump_file,
428 : : " Conditional combines static and invariant op.\n");
429 : 69 : return ch_win;
430 : : }
431 : :
432 : 673422 : edge static_exit = static_loop_exit (loop, header, *ranger, query);
433 : 673422 : if (query)
434 : 673422 : delete query;
435 : :
436 : 673422 : if (static_exit && static_exits)
437 : : {
438 : 296158 : static_exits->add (static_exit);
439 : 296158 : if (dump_file && (dump_flags & TDF_DETAILS))
440 : 5 : fprintf (dump_file,
441 : : " Will eliminate peeled conditional in bb %d.\n",
442 : 5 : static_exit->src->index);
443 : : /* Still look for invariant exits; exit may be both. */
444 : : }
445 : 673422 : if (lhs_invariant && rhs_invariant)
446 : : {
447 : 4278 : if (invariant_exits)
448 : : {
449 : 4278 : edge e;
450 : 4278 : edge_iterator ei;
451 : 12834 : FOR_EACH_EDGE (e, ei, header->succs)
452 : 8556 : if (loop_exit_edge_p (loop, e))
453 : : {
454 : 4278 : if (dump_file && (dump_flags & TDF_DETAILS))
455 : 4 : fprintf (dump_file,
456 : : " Will elliminate invariant exit %i->%i\n",
457 : 4 : e->src->index, e->dest->index);
458 : 4278 : invariant_exits->add (e);
459 : : }
460 : : }
461 : 4278 : return ch_win_invariant_exit;
462 : : }
463 : :
464 : : /* If the static exit fully optimize out, it is win to "duplicate"
465 : : it.
466 : :
467 : : TODO: Even if duplication costs some size we may opt to do so in case
468 : : exit probability is significant enough (do partial peeling). */
469 : 669144 : if (static_exit)
470 : 585144 : return !code_size_cost ? ch_possible_zero_cost : ch_possible;
471 : :
472 : : /* We was not able to prove that conditional will be eliminated. */
473 : 373012 : int insns = estimate_num_insns (last, &eni_size_weights);
474 : 373012 : *limit -= insns;
475 : 373012 : if (dump_file && (dump_flags & TDF_DETAILS))
476 : 15 : fprintf (dump_file,
477 : : " Acconting stmt as %i insns\n", insns);
478 : 373012 : if (*limit < 0)
479 : : {
480 : 13722 : if (dump_file && (dump_flags & TDF_DETAILS))
481 : 0 : fprintf (dump_file,
482 : : " Not duplicating bb %i contains too many insns.\n",
483 : : header->index);
484 : 13722 : return ch_impossible;
485 : : }
486 : :
487 : : return ch_possible;
488 : : }
489 : :
490 : : /* Checks whether LOOP is a do-while style loop. */
491 : :
492 : : static bool
493 : 812411 : do_while_loop_p (class loop *loop)
494 : : {
495 : 812411 : gimple *stmt = last_nondebug_stmt (loop->latch);
496 : :
497 : : /* If the latch of the loop is not empty, it is not a do-while loop. */
498 : 812411 : if (stmt
499 : 812411 : && gimple_code (stmt) != GIMPLE_LABEL)
500 : : {
501 : 520783 : if (dump_file && (dump_flags & TDF_DETAILS))
502 : 10 : fprintf (dump_file,
503 : : "Loop %i is not do-while loop: latch is not empty.\n",
504 : : loop->num);
505 : 520783 : return false;
506 : : }
507 : :
508 : : /* If the latch does not have a single predecessor, it is not a
509 : : do-while loop. */
510 : 291628 : if (!single_pred_p (loop->latch))
511 : : {
512 : 17810 : if (dump_file && (dump_flags & TDF_DETAILS))
513 : 1 : fprintf (dump_file,
514 : : "Loop %i is not do-while loop: latch has multiple "
515 : : "predecessors.\n", loop->num);
516 : 17810 : return false;
517 : : }
518 : 273818 : basic_block pred = single_pred (loop->latch);
519 : :
520 : : /* If the latch predecessor doesn't exit the loop, it is not a
521 : : do-while loop. */
522 : 273818 : if (!loop_exits_from_bb_p (loop, pred))
523 : : {
524 : 8204 : if (dump_file && (dump_flags & TDF_DETAILS))
525 : 0 : fprintf (dump_file,
526 : : "Loop %i is not do-while loop: latch predecessor "
527 : : "does not exit loop.\n", loop->num);
528 : 8204 : return false;
529 : : }
530 : 531228 : gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (pred));
531 : 264580 : if (last
532 : 264580 : && (gimple_cond_lhs (last) == boolean_false_node
533 : 264580 : || gimple_cond_lhs (last) == boolean_true_node)
534 : 1 : && gimple_cond_rhs (last) == boolean_false_node)
535 : : {
536 : 1 : if (dump_file && (dump_flags & TDF_DETAILS))
537 : 1 : fprintf (dump_file,
538 : : "Loop %i is not do-while loop: latch predecessor "
539 : : "contains exit we optimized out.\n", loop->num);
540 : 1 : return false;
541 : : }
542 : :
543 : 265613 : if (dump_file && (dump_flags & TDF_DETAILS))
544 : 15 : fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
545 : :
546 : : return true;
547 : : }
548 : :
549 : : /* Update profile after header copying of LOOP.
550 : : REGION is the original (in loop) sequence, REGION_COPY is the
551 : : duplicated header (now outside of loop). N_REGION is number of
552 : : bbs duplicated.
553 : : ELIMINATED_EDGE is edge to be removed from duplicated sequence.
554 : : INVARIANT_EXITS are edges in the loop body to be elimianted
555 : : since they are loop invariants
556 : :
557 : : So We expect the following:
558 : :
559 : : // region_copy_start entry will be scaled to entry_count
560 : : if (cond1) <- this condition will become false
561 : : and we update probabilities
562 : : goto loop_exit;
563 : : if (cond2) <- this condition is loop invariant
564 : : goto loop_exit;
565 : : goto loop_header <- this will be redirected to loop.
566 : : // region_copy_end
567 : : loop:
568 : : <body>
569 : : // region start
570 : : loop_header:
571 : : if (cond1) <- we need to update probability here
572 : : goto loop_exit;
573 : : if (cond2) <- and determine scaling factor here.
574 : : moreover cond2 is now always true
575 : : goto loop_exit;
576 : : else
577 : : goto loop;
578 : : // region end
579 : :
580 : : Adding support for more exits can be done similarly,
581 : : but only consumer so far is tree-ssa-loop-ch and it uses only this
582 : : to handle the common case of peeling headers which have
583 : : conditionals known to be always true upon entry. */
584 : :
585 : : static void
586 : 510710 : update_profile_after_ch (class loop *loop,
587 : : basic_block *region, basic_block *region_copy,
588 : : unsigned n_region,
589 : : hash_set <edge> *invariant_exits,
590 : : hash_set <edge> *static_exits,
591 : : profile_count entry_count)
592 : : {
593 : 1027528 : for (unsigned int i = 0; i < n_region; i++)
594 : : {
595 : 516818 : edge exit_e, exit_e_copy, e, e_copy;
596 : 516818 : if (EDGE_COUNT (region[i]->succs) == 1)
597 : : {
598 : 0 : region_copy[i]->count = entry_count;
599 : 0 : region[i]->count -= entry_count;
600 : 0 : continue;
601 : : }
602 : :
603 : 516818 : gcc_checking_assert (EDGE_COUNT (region[i]->succs) == 2);
604 : 516818 : if (loop_exit_edge_p (loop,
605 : 516818 : EDGE_SUCC (region[i], 0)))
606 : : {
607 : 118240 : exit_e = EDGE_SUCC (region[i], 0);
608 : 118240 : exit_e_copy = EDGE_SUCC (region_copy[i], 0);
609 : 118240 : e = EDGE_SUCC (region[i], 1);
610 : 118240 : e_copy = EDGE_SUCC (region_copy[i], 1);
611 : : }
612 : : else
613 : : {
614 : 398578 : exit_e = EDGE_SUCC (region[i], 1);
615 : 398578 : exit_e_copy = EDGE_SUCC (region_copy[i], 1);
616 : 398578 : e = EDGE_SUCC (region[i], 0);
617 : 398578 : e_copy = EDGE_SUCC (region_copy[i], 0);
618 : : }
619 : 516818 : gcc_assert (i == n_region - 1
620 : : || (e->dest == region[i + 1]
621 : : && e_copy->dest == region_copy[i + 1]));
622 : 516818 : region_copy[i]->count = entry_count;
623 : 516818 : profile_count exit_e_count = exit_e->count ();
624 : 516818 : bool was_static = false;
625 : 516818 : if (static_exits->contains (exit_e))
626 : : {
627 : : /* Update profile and the conditional.
628 : : CFG update is done by caller. */
629 : 289221 : static_exits->remove (exit_e);
630 : 289221 : was_static = true;
631 : 289221 : e_copy->probability = profile_probability::always ();
632 : 289221 : exit_e_copy->probability = profile_probability::never ();
633 : 289221 : gcond *cond_stmt
634 : 578442 : = as_a <gcond *>(*gsi_last_bb (region_copy[i]));
635 : 289221 : if (e_copy->flags & EDGE_TRUE_VALUE)
636 : 211182 : gimple_cond_make_true (cond_stmt);
637 : : else
638 : 78039 : gimple_cond_make_false (cond_stmt);
639 : 289221 : update_stmt (cond_stmt);
640 : : /* Header copying is a special case of jump threading, so use
641 : : common code to update loop body exit condition. */
642 : 289221 : update_bb_profile_for_threading (region[i], entry_count, e);
643 : : }
644 : : else
645 : 227597 : region[i]->count -= region_copy[i]->count;
646 : 516818 : if (invariant_exits->contains (exit_e))
647 : : {
648 : 4274 : invariant_exits->remove (exit_e);
649 : : /* All exits will happen in exit_e_copy which is out of the
650 : : loop, so increase probability accordingly.
651 : : If the edge is eliminated_edge we already corrected
652 : : profile above. */
653 : 8527 : if (entry_count.nonzero_p () && !was_static)
654 : 4227 : set_edge_probability_and_rescale_others
655 : 4227 : (exit_e_copy, exit_e_count.probability_in
656 : : (entry_count));
657 : : /* Eliminate in-loop conditional. */
658 : 4274 : e->probability = profile_probability::always ();
659 : 4274 : exit_e->probability = profile_probability::never ();
660 : 8548 : gcond *cond_stmt = as_a <gcond *>(*gsi_last_bb (region[i]));
661 : 4274 : if (e->flags & EDGE_TRUE_VALUE)
662 : 1537 : gimple_cond_make_true (cond_stmt);
663 : : else
664 : 2737 : gimple_cond_make_false (cond_stmt);
665 : 4274 : update_stmt (cond_stmt);
666 : : }
667 : 516818 : entry_count = e_copy->count ();
668 : : }
669 : : /* Be sure that we seen all invariant exit edges we are supposed to update.
670 : : We may have recorded some static exists we decided to not duplicate. */
671 : 510710 : gcc_checking_assert (invariant_exits->is_empty ());
672 : 510710 : }
673 : :
674 : : namespace {
675 : :
676 : : /* Common superclass for both header-copying phases. */
677 : : class ch_base : public gimple_opt_pass
678 : : {
679 : : protected:
680 : 848598 : ch_base (pass_data data, gcc::context *ctxt)
681 : 1697196 : : gimple_opt_pass (data, ctxt)
682 : : {}
683 : :
684 : : /* Copies headers of all loops in FUN for which process_loop_p is true. */
685 : : unsigned int copy_headers (function *fun);
686 : :
687 : : /* Return true to copy headers of LOOP or false to skip. */
688 : : virtual bool process_loop_p (class loop *loop) = 0;
689 : : };
690 : :
691 : : const pass_data pass_data_ch =
692 : : {
693 : : GIMPLE_PASS, /* type */
694 : : "ch", /* name */
695 : : OPTGROUP_LOOP, /* optinfo_flags */
696 : : TV_TREE_CH, /* tv_id */
697 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
698 : : 0, /* properties_provided */
699 : : 0, /* properties_destroyed */
700 : : 0, /* todo_flags_start */
701 : : 0, /* todo_flags_finish */
702 : : };
703 : :
704 : : class pass_ch : public ch_base
705 : : {
706 : : public:
707 : 565732 : pass_ch (gcc::context *ctxt)
708 : 565732 : : ch_base (pass_data_ch, ctxt)
709 : 565732 : {}
710 : :
711 : : /* opt_pass methods: */
712 : 1002024 : bool gate (function *) final override { return flag_tree_ch != 0; }
713 : :
714 : : /* Initialize and finalize loop structures, copying headers inbetween. */
715 : : unsigned int execute (function *) final override;
716 : :
717 : 282866 : opt_pass * clone () final override { return new pass_ch (m_ctxt); }
718 : :
719 : : protected:
720 : : /* ch_base method: */
721 : : bool process_loop_p (class loop *loop) final override;
722 : : }; // class pass_ch
723 : :
724 : : const pass_data pass_data_ch_vect =
725 : : {
726 : : GIMPLE_PASS, /* type */
727 : : "ch_vect", /* name */
728 : : OPTGROUP_LOOP, /* optinfo_flags */
729 : : TV_TREE_CH, /* tv_id */
730 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
731 : : 0, /* properties_provided */
732 : : 0, /* properties_destroyed */
733 : : 0, /* todo_flags_start */
734 : : 0, /* todo_flags_finish */
735 : : };
736 : :
737 : : /* This is a more aggressive version of the same pass, designed to run just
738 : : before if-conversion and vectorization, to put more loops into the form
739 : : required for those phases. */
740 : : class pass_ch_vect : public ch_base
741 : : {
742 : : public:
743 : 282866 : pass_ch_vect (gcc::context *ctxt)
744 : 282866 : : ch_base (pass_data_ch_vect, ctxt)
745 : 282866 : {}
746 : :
747 : : /* opt_pass methods: */
748 : 227899 : bool gate (function *fun) final override
749 : : {
750 : 227899 : return flag_tree_ch != 0
751 : 227899 : && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
752 : : }
753 : :
754 : : /* Just copy headers, no initialization/finalization of loop structures. */
755 : : unsigned int execute (function *) final override;
756 : :
757 : : protected:
758 : : /* ch_base method: */
759 : : bool process_loop_p (class loop *loop) final override;
760 : : }; // class pass_ch_vect
761 : :
762 : : /* Sort comparator to order loops after the specified order. */
763 : :
764 : : static int
765 : 37681 : ch_order_loops (const void *a_, const void *b_, void *order_)
766 : : {
767 : 37681 : int *order = (int *)order_;
768 : 37681 : const class loop *a = *(const class loop * const *)a_;
769 : 37681 : const class loop *b = *(const class loop * const *)b_;
770 : 37681 : if (a->num == b->num)
771 : : return 0;
772 : 37681 : if (order[a->num] < order[b->num])
773 : 18305 : return -1;
774 : : return 1;
775 : : }
776 : :
777 : : /* For all loops, copy the condition at the end of the loop body in front
778 : : of the loop. This is beneficial since it increases efficiency of
779 : : code motion optimizations. It also saves one jump on entry to the loop. */
780 : :
781 : : unsigned int
782 : 1198516 : ch_base::copy_headers (function *fun)
783 : : {
784 : 1198516 : basic_block *bbs, *copied_bbs;
785 : 1198516 : unsigned bbs_size;
786 : 1198516 : bool changed = false;
787 : :
788 : 2397032 : if (number_of_loops (fun) <= 1)
789 : : return 0;
790 : :
791 : 424363 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
792 : 424363 : copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
793 : 424363 : bbs_size = n_basic_blocks_for_fn (fun);
794 : :
795 : 424363 : struct candidate
796 : : {
797 : : class loop *loop;
798 : : unsigned int nheaders;
799 : : hash_set <edge> *invariant_exits, *static_exits;
800 : : };
801 : 424363 : auto_vec<struct candidate> candidates;
802 : 424363 : auto_vec<std::pair<edge, loop_p> > copied;
803 : 424363 : auto_vec<class loop *> loops_to_unloop;
804 : 424363 : auto_vec<int> loops_to_unloop_nunroll;
805 : :
806 : 424363 : mark_dfs_back_edges ();
807 : 424363 : gimple_ranger *ranger = new gimple_ranger;
808 : 2372970 : for (auto loop : loops_list (cfun, 0))
809 : : {
810 : 1099881 : int initial_limit = optimize_loop_for_speed_p (loop)
811 : 1099881 : ? param_max_loop_header_insns : 0;
812 : 1099881 : int remaining_limit = initial_limit;
813 : 1099881 : if (dump_file && (dump_flags & TDF_DETAILS))
814 : 17 : fprintf (dump_file,
815 : : "Analyzing loop %i\n", loop->num);
816 : :
817 : : /* If the loop is already a do-while style one (either because it was
818 : : written as such, or because jump threading transformed it into one),
819 : : we might be in fact peeling the first iteration of the loop. This
820 : : in general is not a good idea. Also avoid touching infinite loops. */
821 : 1099881 : if (!loop_has_exit_edges (loop)
822 : 1099881 : || !process_loop_p (loop))
823 : 426706 : continue;
824 : :
825 : 673221 : basic_block header = loop->header;
826 : 673221 : estimate_numbers_of_iterations (loop);
827 : 673221 : if (!get_max_loop_iterations_int (loop))
828 : : {
829 : 46 : if (dump_file && (dump_flags & TDF_DETAILS))
830 : 0 : fprintf (dump_file, "Loop %d never loops.\n", loop->num);
831 : 46 : scale_loop_profile (loop, profile_probability::always (), 0);
832 : 46 : loops_to_unloop.safe_push (loop);
833 : 46 : loops_to_unloop_nunroll.safe_push (0);
834 : 46 : continue;
835 : : }
836 : :
837 : : /* Iterate the header copying up to limit; this takes care of the cases
838 : : like while (a && b) {...}, where we want to have both of the conditions
839 : : copied. TODO -- handle while (a || b) - like cases, by not requiring
840 : : the header to have just a single successor and copying up to
841 : : postdominator. */
842 : 673175 : unsigned int nheaders = 0;
843 : 673175 : unsigned int last_win_nheaders = 0;
844 : 673175 : bool last_win_invariant_exit = false;
845 : 673175 : ch_decision ret;
846 : 673175 : auto_vec <ch_decision, 32> decision;
847 : 673175 : hash_set <edge> *invariant_exits = new hash_set <edge>;
848 : 673175 : hash_set <edge> *static_exits = new hash_set <edge>;
849 : 673175 : while ((ret = should_duplicate_loop_header_p (header, loop, ranger,
850 : : &remaining_limit,
851 : : invariant_exits,
852 : : static_exits))
853 : 1332944 : != ch_impossible)
854 : : {
855 : 659769 : nheaders++;
856 : 659769 : decision.safe_push (ret);
857 : 659769 : if (ret >= ch_win)
858 : : {
859 : 4347 : last_win_nheaders = nheaders;
860 : 4347 : last_win_invariant_exit = (ret == ch_win_invariant_exit);
861 : 4347 : if (dump_file && (dump_flags & TDF_DETAILS))
862 : 5 : fprintf (dump_file, " Duplicating bb %i is a win\n",
863 : : header->index);
864 : : }
865 : : else
866 : 655422 : if (dump_file && (dump_flags & TDF_DETAILS))
867 : 20 : fprintf (dump_file, " May duplicate bb %i\n", header->index);
868 : :
869 : : /* Find a successor of header that is inside a loop; i.e. the new
870 : : header after the condition is copied. */
871 : 659769 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
872 : 440336 : header = EDGE_SUCC (header, 0)->dest;
873 : : else
874 : 219433 : header = EDGE_SUCC (header, 1)->dest;
875 : : }
876 : :
877 : : /* Try to turn loop into do-while. This means ensuring that
878 : : last duplicated header will not have loop invariant exit. */
879 : 673175 : if (last_win_nheaders && last_win_invariant_exit
880 : 3847 : && nheaders > last_win_nheaders)
881 : : {
882 : 1290 : last_win_nheaders++;
883 : 1290 : if (dump_file && (dump_flags & TDF_DETAILS))
884 : 2 : fprintf (dump_file,
885 : : " Duplicating additional BB to obtain do-while loop\n");
886 : : }
887 : 671885 : else if (!last_win_nheaders && nheaders && !do_while_loop_p (loop))
888 : : {
889 : 502454 : last_win_nheaders = 1;
890 : 502454 : if (dump_file && (dump_flags & TDF_DETAILS))
891 : 11 : fprintf (dump_file,
892 : : " Duplicating header BB to obtain do-while loop\n");
893 : : }
894 : : /* "Duplicate" all BBs with zero cost following last basic blocks we
895 : : decided to copy. */
896 : 1353335 : while (last_win_nheaders < decision.length ()
897 : 797639 : && decision[last_win_nheaders] == ch_possible_zero_cost)
898 : : {
899 : 6985 : if (dump_file && (dump_flags & TDF_DETAILS))
900 : 0 : fprintf (dump_file,
901 : : " Duplicating extra bb is a win; it has zero cost\n");
902 : 6985 : last_win_nheaders++;
903 : : }
904 : :
905 : 673175 : if (last_win_nheaders)
906 : 510824 : candidates.safe_push ({loop, last_win_nheaders,
907 : : invariant_exits, static_exits});
908 : : else
909 : : {
910 : 162351 : delete invariant_exits;
911 : 162351 : delete static_exits;
912 : : }
913 : 673175 : }
914 : : /* Do not use ranger after we change the IL and not have updated SSA. */
915 : 424363 : delete ranger;
916 : :
917 : 1276047 : for (auto candidate : candidates)
918 : : {
919 : 510824 : class loop *loop = candidate.loop;
920 : 510824 : if (dump_file && (dump_flags & TDF_DETAILS))
921 : 16 : fprintf (dump_file,
922 : : "Copying headers of loop %i\n", loop->num);
923 : :
924 : 510824 : basic_block header = loop->header;
925 : 510824 : edge nonexit = NULL;
926 : 510824 : edge exit = NULL;
927 : 510824 : unsigned int n_bbs = 0;
928 : 510824 : int nexits = 0;
929 : 510824 : profile_count exit_count = profile_count::zero ();
930 : 510824 : profile_count entry_count = profile_count::zero ();
931 : 510824 : edge e;
932 : 510824 : edge_iterator ei;
933 : :
934 : 1532472 : FOR_EACH_EDGE (e, ei, loop->header->preds)
935 : 1021648 : if (e->src != loop->latch)
936 : 510824 : entry_count += e->count ();
937 : 1027757 : while (n_bbs < candidate.nheaders)
938 : : {
939 : 516933 : if (dump_file && (dump_flags & TDF_DETAILS))
940 : 21 : fprintf (dump_file, " Will duplicate bb %i\n", header->index);
941 : : /* Find a successor of header that is inside a loop; i.e. the new
942 : : header after the condition is copied. */
943 : 516933 : if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
944 : : {
945 : 398653 : nonexit = EDGE_SUCC (header, 0);
946 : 398653 : exit = EDGE_SUCC (header, 1);
947 : : }
948 : : else
949 : : {
950 : 118280 : nonexit = EDGE_SUCC (header, 1);
951 : 118280 : exit = EDGE_SUCC (header, 0);
952 : : }
953 : 516933 : exit_count += exit->count ();
954 : 516933 : nexits++;
955 : 516933 : bbs[n_bbs++] = header;
956 : 516933 : gcc_assert (bbs_size > n_bbs);
957 : 516933 : header = nonexit->dest;
958 : : }
959 : :
960 : 510824 : if (dump_file && (dump_flags & TDF_DETAILS))
961 : 16 : fprintf (dump_file,
962 : : "Duplicating header of the loop %d up to edge %d->%d\n",
963 : 16 : loop->num, exit->src->index, exit->dest->index);
964 : :
965 : : /* Ensure that the header will have just the latch as a predecessor
966 : : inside the loop. */
967 : 510824 : if (!single_pred_p (nonexit->dest))
968 : : {
969 : 13 : header = split_edge (nonexit);
970 : 13 : exit = single_pred_edge (header);
971 : : }
972 : :
973 : 510824 : edge entry = loop_preheader_edge (loop);
974 : :
975 : 510824 : propagate_threaded_block_debug_into (nonexit->dest, entry->dest);
976 : 510824 : if (!gimple_duplicate_seme_region (entry, exit, bbs, n_bbs, copied_bbs,
977 : : true))
978 : : {
979 : 0 : delete candidate.static_exits;
980 : 0 : delete candidate.invariant_exits;
981 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
982 : 0 : fprintf (dump_file, "Duplication failed.\n");
983 : 0 : continue;
984 : : }
985 : 510824 : if (loop->header->count.initialized_p ())
986 : 510710 : update_profile_after_ch (loop, bbs, copied_bbs, n_bbs,
987 : : candidate.invariant_exits,
988 : : candidate.static_exits,
989 : : entry_count);
990 : 1021648 : delete candidate.static_exits;
991 : 1021648 : delete candidate.invariant_exits;
992 : 510824 : copied.safe_push (std::make_pair (entry, loop));
993 : :
994 : : /* If the loop has the form "for (i = j; i < j + 10; i++)" then
995 : : this copying can introduce a case where we rely on undefined
996 : : signed overflow to eliminate the preheader condition, because
997 : : we assume that "j < j + 10" is true. We don't want to warn
998 : : about that case for -Wstrict-overflow, because in general we
999 : : don't warn about overflow involving loops. Prevent the
1000 : : warning by setting the no_warning flag in the condition. */
1001 : 510824 : if (warn_strict_overflow > 0)
1002 : : {
1003 : : unsigned int i;
1004 : :
1005 : 113027 : for (i = 0; i < n_bbs; ++i)
1006 : : {
1007 : 56557 : gimple_stmt_iterator bsi;
1008 : :
1009 : 113114 : for (bsi = gsi_start_bb (copied_bbs[i]);
1010 : 285426 : !gsi_end_p (bsi);
1011 : 228869 : gsi_next (&bsi))
1012 : : {
1013 : 228869 : gimple *stmt = gsi_stmt (bsi);
1014 : 228869 : if (gimple_code (stmt) == GIMPLE_COND)
1015 : : {
1016 : 56557 : tree lhs = gimple_cond_lhs (stmt);
1017 : 56557 : if (gimple_cond_code (stmt) != EQ_EXPR
1018 : 53016 : && gimple_cond_code (stmt) != NE_EXPR
1019 : 31240 : && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1020 : 87018 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)))
1021 : 22955 : suppress_warning (stmt, OPT_Wstrict_overflow_);
1022 : : }
1023 : 172312 : else if (is_gimple_assign (stmt))
1024 : : {
1025 : 15859 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1026 : 15859 : tree rhs1 = gimple_assign_rhs1 (stmt);
1027 : 15859 : if (TREE_CODE_CLASS (rhs_code) == tcc_comparison
1028 : : && rhs_code != EQ_EXPR
1029 : 627 : && rhs_code != NE_EXPR
1030 : 191 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1031 : 16028 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1)))
1032 : 48 : suppress_warning (stmt, OPT_Wstrict_overflow_);
1033 : : }
1034 : : }
1035 : : }
1036 : : }
1037 : :
1038 : : /* Update header of the loop. */
1039 : 510824 : loop->header = header;
1040 : : /* Find correct latch. We only duplicate chain of conditionals so
1041 : : there should be precisely two edges to the new header. One entry
1042 : : edge and one to latch. */
1043 : 510824 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1044 : 510824 : if (header != e->src)
1045 : : {
1046 : 510824 : loop->latch = e->src;
1047 : 510824 : break;
1048 : : }
1049 : : /* Ensure that the latch is simple. */
1050 : 510824 : if (!single_succ_p (loop_latch_edge (loop)->src))
1051 : 510824 : split_edge (loop_latch_edge (loop));
1052 : :
1053 : 510824 : if (dump_file && (dump_flags & TDF_DETAILS))
1054 : : {
1055 : 16 : if (do_while_loop_p (loop))
1056 : 15 : fprintf (dump_file, "Loop %d is now do-while loop.\n", loop->num);
1057 : : else
1058 : 1 : fprintf (dump_file, "Loop %d is still not do-while loop.\n",
1059 : : loop->num);
1060 : 16 : fprintf (dump_file, "Exit count: ");
1061 : 16 : exit_count.dump (dump_file);
1062 : 16 : fprintf (dump_file, "\nEntry count: ");
1063 : 16 : entry_count.dump (dump_file);
1064 : 16 : fprintf (dump_file, "\n");
1065 : : }
1066 : :
1067 : : /* We possibly decreased number of iterations by 1. */
1068 : 510824 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1069 : 510824 : bool precise = (nexits == (int) exits.length ());
1070 : : /* Check that loop may not terminate in other way than via
1071 : : basic blocks we duplicated. */
1072 : 510824 : if (precise)
1073 : : {
1074 : 344754 : basic_block *bbs = get_loop_body (loop);
1075 : 1711698 : for (unsigned i = 0; i < loop->num_nodes && precise; ++i)
1076 : : {
1077 : 1366976 : basic_block bb = bbs[i];
1078 : 1366976 : bool found_exit = false;
1079 : 2858860 : FOR_EACH_EDGE (e, ei, bb->succs)
1080 : 1793859 : if (!flow_bb_inside_loop_p (loop, e->dest))
1081 : : {
1082 : : found_exit = true;
1083 : : break;
1084 : : }
1085 : : /* If BB has exit, it was duplicated. */
1086 : 1366976 : if (found_exit)
1087 : 301975 : continue;
1088 : : /* Give up on irreducible loops. */
1089 : 1065001 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1090 : : {
1091 : : precise = false;
1092 : : break;
1093 : : }
1094 : : /* Check that inner loops are finite. */
1095 : 1382249 : for (class loop *l = bb->loop_father; l != loop && precise;
1096 : 317280 : l = loop_outer (l))
1097 : 326819 : if (!l->finite_p)
1098 : : {
1099 : : precise = false;
1100 : : break;
1101 : : }
1102 : : /* Verify that there is no statement that may be terminate
1103 : : execution in a way not visible to CFG. */
1104 : 2129938 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
1105 : 7384073 : !gsi_end_p (bsi); gsi_next (&bsi))
1106 : 6319104 : if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
1107 : 103283 : precise = false;
1108 : : }
1109 : 344754 : free (bbs);
1110 : : }
1111 : 510824 : if (precise
1112 : 510824 : && get_max_loop_iterations_int (loop) == 1)
1113 : : {
1114 : 2351 : if (dump_file && (dump_flags & TDF_DETAILS))
1115 : 0 : fprintf (dump_file, "Loop %d no longer loops.\n", loop->num);
1116 : 2351 : scale_loop_profile (loop, profile_probability::always (), 0);
1117 : 2351 : loops_to_unloop.safe_push (loop);
1118 : 2351 : loops_to_unloop_nunroll.safe_push (0);
1119 : : }
1120 : 508473 : else if (precise)
1121 : : {
1122 : 268754 : if (dump_file && (dump_flags & TDF_DETAILS))
1123 : 7 : fprintf (dump_file,
1124 : : "Peeled all exits:"
1125 : : " decreased number of iterations of loop %d by 1.\n",
1126 : : loop->num);
1127 : 268754 : adjust_loop_info_after_peeling (loop, 1, true);
1128 : : }
1129 : 239719 : else if (exit_count >= entry_count.apply_scale (9, 10))
1130 : : {
1131 : 139666 : if (dump_file && (dump_flags & TDF_DETAILS))
1132 : 5 : fprintf (dump_file,
1133 : : "Peeled likely exits: likely decreased number "
1134 : : "of iterations of loop %d by 1.\n", loop->num);
1135 : 139666 : adjust_loop_info_after_peeling (loop, 1, false);
1136 : : }
1137 : 100053 : else if (dump_file && (dump_flags & TDF_DETAILS))
1138 : 4 : fprintf (dump_file,
1139 : : "Not decreased number"
1140 : : " of iterations of loop %d; likely exits remains.\n",
1141 : : loop->num);
1142 : :
1143 : 510824 : changed = true;
1144 : 510824 : }
1145 : :
1146 : 424363 : if (changed)
1147 : : {
1148 : 170430 : update_ssa (TODO_update_ssa);
1149 : : /* After updating SSA form perform CSE on the loop header
1150 : : copies. This is esp. required for the pass before
1151 : : vectorization since nothing cleans up copied exit tests
1152 : : that can now be simplified. CSE from the entry of the
1153 : : region we copied till all loop exit blocks but not
1154 : : entering the loop itself. */
1155 : 681254 : for (unsigned i = 0; i < copied.length (); ++i)
1156 : : {
1157 : 510824 : edge entry = copied[i].first;
1158 : 510824 : loop_p loop = copied[i].second;
1159 : 510824 : auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
1160 : 510824 : bitmap exit_bbs = BITMAP_ALLOC (NULL);
1161 : 1482446 : for (unsigned j = 0; j < exit_edges.length (); ++j)
1162 : 971622 : bitmap_set_bit (exit_bbs, exit_edges[j]->dest->index);
1163 : 510824 : bitmap_set_bit (exit_bbs, loop->header->index);
1164 : 510824 : do_rpo_vn (cfun, entry, exit_bbs);
1165 : 510824 : BITMAP_FREE (exit_bbs);
1166 : 510824 : }
1167 : : }
1168 : 424363 : if (!loops_to_unloop.is_empty ())
1169 : : {
1170 : : /* Make sure loops are ordered inner to outer for unlooping. */
1171 : 635 : if (loops_to_unloop.length () != 1)
1172 : : {
1173 : 291 : auto_vec<int, 8> order;
1174 : 582 : order.safe_grow (number_of_loops (cfun), true);
1175 : 291 : int i = 0;
1176 : 7648 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1177 : 6775 : order[loop->num] = i++;
1178 : 873 : loops_to_unloop.sort (ch_order_loops, order.address ());
1179 : 291 : }
1180 : 635 : bool irred_invalidated;
1181 : 635 : auto_bitmap lc_invalidated;
1182 : 635 : auto_vec<edge> edges_to_remove;
1183 : 635 : unloop_loops (loops_to_unloop, loops_to_unloop_nunroll, edges_to_remove,
1184 : : lc_invalidated, &irred_invalidated);
1185 : 635 : if (loops_state_satisfies_p (fun, LOOP_CLOSED_SSA)
1186 : 635 : && !bitmap_empty_p (lc_invalidated))
1187 : 4 : rewrite_into_loop_closed_ssa (NULL, 0);
1188 : 635 : changed = true;
1189 : 635 : }
1190 : 424363 : free (bbs);
1191 : 424363 : free (copied_bbs);
1192 : :
1193 : 678289 : return changed ? TODO_cleanup_cfg : 0;
1194 : 424363 : }
1195 : :
1196 : : /* Initialize the loop structures we need, and finalize after. */
1197 : :
1198 : : unsigned int
1199 : 1001829 : pass_ch::execute (function *fun)
1200 : : {
1201 : 1001829 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1202 : 1001829 : scev_initialize ();
1203 : :
1204 : 1001829 : unsigned int res = copy_headers (fun);
1205 : :
1206 : 1001829 : scev_finalize ();
1207 : 1001829 : loop_optimizer_finalize ();
1208 : 1001829 : return res;
1209 : : }
1210 : :
1211 : : /* Assume an earlier phase has already initialized all the loop structures that
1212 : : we need here (and perhaps others too), and that these will be finalized by
1213 : : a later phase. */
1214 : :
1215 : : unsigned int
1216 : 196687 : pass_ch_vect::execute (function *fun)
1217 : : {
1218 : 196687 : return copy_headers (fun);
1219 : : }
1220 : :
1221 : : /* Apply header copying according to a very simple test of do-while shape. */
1222 : :
1223 : : bool
1224 : 628878 : pass_ch::process_loop_p (class loop *)
1225 : : {
1226 : 628878 : return true;
1227 : : }
1228 : :
1229 : : /* Apply header-copying to loops where we might enable vectorization. */
1230 : :
1231 : : bool
1232 : 461478 : pass_ch_vect::process_loop_p (class loop *loop)
1233 : : {
1234 : 461478 : if (!flag_tree_loop_vectorize && !loop->force_vectorize)
1235 : : return false;
1236 : :
1237 : 458653 : if (loop->dont_vectorize)
1238 : : return false;
1239 : :
1240 : : /* The vectorizer won't handle anything with multiple exits, so skip. */
1241 : 454827 : edge exit = single_exit (loop);
1242 : 454827 : if (!exit)
1243 : : return false;
1244 : :
1245 : 275205 : if (!do_while_loop_p (loop))
1246 : : return true;
1247 : :
1248 : : return false;
1249 : : }
1250 : :
1251 : : } // anon namespace
1252 : :
1253 : : gimple_opt_pass *
1254 : 282866 : make_pass_ch_vect (gcc::context *ctxt)
1255 : : {
1256 : 282866 : return new pass_ch_vect (ctxt);
1257 : : }
1258 : :
1259 : : gimple_opt_pass *
1260 : 282866 : make_pass_ch (gcc::context *ctxt)
1261 : : {
1262 : 282866 : return new pass_ch (ctxt);
1263 : : }
|
