1 /* Loop header copying on trees.
2 Copyright (C) 2004-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
27 #include "tree-pass.h"
28 #include "gimple-ssa.h"
29 #include "gimple-iterator.h"
31 #include "tree-into-ssa.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"
42 /* Duplicates headers of loops if they are small enough, so that the statements
43 in the loop body are always executed when the loop is entered. This
44 increases effectiveness of code motion optimizations, and reduces the need
45 for loop preconditioning. */
47 /* Return true if the condition on the first iteration of the loop can
48 be statically determined. */
51 entry_loop_condition_is_static (class loop
*l
, path_range_query
*query
)
53 edge e
= loop_preheader_edge (l
);
54 gcond
*last
= safe_dyn_cast
<gcond
*> (last_stmt (e
->dest
));
57 || !irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (last
))))
61 extract_true_false_edges_from_block (e
->dest
, &true_e
, &false_e
);
63 /* If neither edge is the exit edge, this is not a case we'd like to
65 if (!loop_exit_edge_p (l
, true_e
) && !loop_exit_edge_p (l
, false_e
))
68 tree desired_static_value
;
69 if (loop_exit_edge_p (l
, true_e
))
70 desired_static_value
= boolean_false_node
;
72 desired_static_value
= boolean_true_node
;
75 query
->compute_ranges (e
);
76 query
->range_of_stmt (r
, last
);
77 return r
== int_range
<2> (desired_static_value
, desired_static_value
);
80 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
81 instructions should be duplicated, limit is decreased by the actual
85 should_duplicate_loop_header_p (basic_block header
, class loop
*loop
,
88 gimple_stmt_iterator bsi
;
90 gcc_assert (!header
->aux
);
92 gcc_assert (EDGE_COUNT (header
->succs
) > 0);
93 if (single_succ_p (header
))
95 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
97 " Not duplicating bb %i: it is single succ.\n",
102 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
)
103 && flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 1)->dest
))
105 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
107 " Not duplicating bb %i: both successors are in loop.\n",
112 /* If this is not the original loop header, we want it to have just
113 one predecessor in order to match the && pattern. */
114 if (header
!= loop
->header
&& !single_pred_p (header
))
116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
118 " Not duplicating bb %i: it has mutiple predecestors.\n",
123 gcond
*last
= safe_dyn_cast
<gcond
*> (last_stmt (header
));
126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
128 " Not duplicating bb %i: it does not end by conditional.\n",
133 for (gphi_iterator psi
= gsi_start_phis (header
); !gsi_end_p (psi
);
136 gphi
*phi
= psi
.phi ();
137 tree res
= gimple_phi_result (phi
);
138 if (INTEGRAL_TYPE_P (TREE_TYPE (res
))
139 || POINTER_TYPE_P (TREE_TYPE (res
)))
140 gimple_set_uid (phi
, 1 /* IV */);
142 gimple_set_uid (phi
, 0);
145 /* Count number of instructions and punt on calls.
146 Populate stmts INV/IV flag to later apply heuristics to the
147 kind of conditions we want to copy. */
148 for (bsi
= gsi_start_bb (header
); !gsi_end_p (bsi
); gsi_next (&bsi
))
150 gimple
*last
= gsi_stmt (bsi
);
152 if (gimple_code (last
) == GIMPLE_LABEL
)
155 if (is_gimple_debug (last
))
158 if (gimple_code (last
) == GIMPLE_CALL
159 && (!gimple_inexpensive_call_p (as_a
<gcall
*> (last
))
160 /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
161 at current loop's header. Don't copy in this case. */
162 || gimple_call_internal_p (last
, IFN_LOOP_DIST_ALIAS
)))
164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
166 " Not duplicating bb %i: it contains call.\n",
171 *limit
-= estimate_num_insns (last
, &eni_size_weights
);
174 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
176 " Not duplicating bb %i contains too many insns.\n",
181 /* Classify the stmt based on whether its computation is based
182 on a IV or whether it is invariant in the loop. */
183 gimple_set_uid (last
, 0);
184 if (!gimple_vuse (last
))
190 FOR_EACH_SSA_TREE_OPERAND (op
, last
, i
, SSA_OP_USE
)
191 if (!SSA_NAME_IS_DEFAULT_DEF (op
)
192 && flow_bb_inside_loop_p (loop
,
193 gimple_bb (SSA_NAME_DEF_STMT (op
))))
195 if (!(gimple_uid (SSA_NAME_DEF_STMT (op
)) & 2 /* INV */))
197 if (gimple_uid (SSA_NAME_DEF_STMT (op
)) & 1 /* IV */)
200 gimple_set_uid (last
, (iv
? 1 : 0) | (inv
? 2 : 0));
204 /* If the condition tests a non-IV loop variant we do not want to rotate
205 the loop further. Unless this is the original loop header. */
206 tree lhs
= gimple_cond_lhs (last
);
207 tree rhs
= gimple_cond_rhs (last
);
208 if (header
!= loop
->header
209 && ((TREE_CODE (lhs
) == SSA_NAME
210 && !SSA_NAME_IS_DEFAULT_DEF (lhs
)
211 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (lhs
)))
212 && gimple_uid (SSA_NAME_DEF_STMT (lhs
)) == 0)
213 || (TREE_CODE (rhs
) == SSA_NAME
214 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
215 && flow_bb_inside_loop_p (loop
,
216 gimple_bb (SSA_NAME_DEF_STMT (rhs
)))
217 && gimple_uid (SSA_NAME_DEF_STMT (rhs
)) == 0)))
219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
221 " Not duplicating bb %i: condition based on non-IV loop"
222 " variant.\n", header
->index
);
229 /* Checks whether LOOP is a do-while style loop. */
232 do_while_loop_p (class loop
*loop
)
234 gimple
*stmt
= last_stmt (loop
->latch
);
236 /* If the latch of the loop is not empty, it is not a do-while loop. */
238 && gimple_code (stmt
) != GIMPLE_LABEL
)
240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
242 "Loop %i is not do-while loop: latch is not empty.\n",
247 /* If the latch does not have a single predecessor, it is not a
249 if (!single_pred_p (loop
->latch
))
251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
253 "Loop %i is not do-while loop: latch has multiple "
254 "predecessors.\n", loop
->num
);
258 /* If the latch predecessor doesn't exit the loop, it is not a
260 if (!loop_exits_from_bb_p (loop
, single_pred (loop
->latch
)))
262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
264 "Loop %i is not do-while loop: latch predecessor "
265 "does not exit loop.\n", loop
->num
);
269 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
270 fprintf (dump_file
, "Loop %i is do-while loop\n", loop
->num
);
277 /* Common superclass for both header-copying phases. */
278 class ch_base
: public gimple_opt_pass
281 ch_base (pass_data data
, gcc::context
*ctxt
)
282 : gimple_opt_pass (data
, ctxt
)
285 /* Copies headers of all loops in FUN for which process_loop_p is true. */
286 unsigned int copy_headers (function
*fun
);
288 /* Return true to copy headers of LOOP or false to skip. */
289 virtual bool process_loop_p (class loop
*loop
) = 0;
292 const pass_data pass_data_ch
=
294 GIMPLE_PASS
, /* type */
296 OPTGROUP_LOOP
, /* optinfo_flags */
297 TV_TREE_CH
, /* tv_id */
298 ( PROP_cfg
| PROP_ssa
), /* properties_required */
299 0, /* properties_provided */
300 0, /* properties_destroyed */
301 0, /* todo_flags_start */
302 0, /* todo_flags_finish */
305 class pass_ch
: public ch_base
308 pass_ch (gcc::context
*ctxt
)
309 : ch_base (pass_data_ch
, ctxt
)
312 /* opt_pass methods: */
313 virtual bool gate (function
*) { return flag_tree_ch
!= 0; }
315 /* Initialize and finalize loop structures, copying headers inbetween. */
316 virtual unsigned int execute (function
*);
318 opt_pass
* clone () { return new pass_ch (m_ctxt
); }
321 /* ch_base method: */
322 virtual bool process_loop_p (class loop
*loop
);
325 const pass_data pass_data_ch_vect
=
327 GIMPLE_PASS
, /* type */
328 "ch_vect", /* name */
329 OPTGROUP_LOOP
, /* optinfo_flags */
330 TV_TREE_CH
, /* tv_id */
331 ( PROP_cfg
| PROP_ssa
), /* properties_required */
332 0, /* properties_provided */
333 0, /* properties_destroyed */
334 0, /* todo_flags_start */
335 0, /* todo_flags_finish */
338 /* This is a more aggressive version of the same pass, designed to run just
339 before if-conversion and vectorization, to put more loops into the form
340 required for those phases. */
341 class pass_ch_vect
: public ch_base
344 pass_ch_vect (gcc::context
*ctxt
)
345 : ch_base (pass_data_ch_vect
, ctxt
)
348 /* opt_pass methods: */
349 virtual bool gate (function
*fun
)
351 return flag_tree_ch
!= 0
352 && (flag_tree_loop_vectorize
!= 0 || fun
->has_force_vectorize_loops
);
355 /* Just copy headers, no initialization/finalization of loop structures. */
356 virtual unsigned int execute (function
*);
359 /* ch_base method: */
360 virtual bool process_loop_p (class loop
*loop
);
361 }; // class pass_ch_vect
363 /* For all loops, copy the condition at the end of the loop body in front
364 of the loop. This is beneficial since it increases efficiency of
365 code motion optimizations. It also saves one jump on entry to the loop. */
368 ch_base::copy_headers (function
*fun
)
372 basic_block
*bbs
, *copied_bbs
;
375 bool changed
= false;
377 if (number_of_loops (fun
) <= 1)
380 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
381 copied_bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
382 bbs_size
= n_basic_blocks_for_fn (fun
);
384 auto_vec
<loop_p
> candidates
;
385 auto_vec
<std::pair
<edge
, loop_p
> > copied
;
387 path_range_query
*query
= new path_range_query
;
388 for (auto loop
: loops_list (cfun
, 0))
390 int initial_limit
= param_max_loop_header_insns
;
391 int remaining_limit
= initial_limit
;
392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
394 "Analyzing loop %i\n", loop
->num
);
396 header
= loop
->header
;
398 /* If the loop is already a do-while style one (either because it was
399 written as such, or because jump threading transformed it into one),
400 we might be in fact peeling the first iteration of the loop. This
401 in general is not a good idea. Also avoid touching infinite loops. */
402 if (!loop_has_exit_edges (loop
)
403 || !process_loop_p (loop
))
406 /* Avoid loop header copying when optimizing for size unless we can
407 determine that the loop condition is static in the first
409 if (optimize_loop_for_size_p (loop
)
410 && !loop
->force_vectorize
411 && !entry_loop_condition_is_static (loop
, query
))
413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
415 " Not duplicating bb %i: optimizing for size.\n",
420 if (should_duplicate_loop_header_p (header
, loop
, &remaining_limit
))
421 candidates
.safe_push (loop
);
423 /* Do not use ranger after we change the IL and not have updated SSA. */
426 for (auto loop
: candidates
)
428 int initial_limit
= param_max_loop_header_insns
;
429 int remaining_limit
= initial_limit
;
430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
432 "Copying headers of loop %i\n", loop
->num
);
434 header
= loop
->header
;
436 /* Iterate the header copying up to limit; this takes care of the cases
437 like while (a && b) {...}, where we want to have both of the conditions
438 copied. TODO -- handle while (a || b) - like cases, by not requiring
439 the header to have just a single successor and copying up to
444 while (should_duplicate_loop_header_p (header
, loop
, &remaining_limit
))
446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
447 fprintf (dump_file
, " Will duplicate bb %i\n", header
->index
);
449 /* Find a successor of header that is inside a loop; i.e. the new
450 header after the condition is copied. */
451 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
))
452 exit
= EDGE_SUCC (header
, 0);
454 exit
= EDGE_SUCC (header
, 1);
455 bbs
[n_bbs
++] = header
;
456 gcc_assert (bbs_size
> n_bbs
);
463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
465 "Duplicating header of the loop %d up to edge %d->%d,"
467 loop
->num
, exit
->src
->index
, exit
->dest
->index
,
468 initial_limit
- remaining_limit
);
470 /* Ensure that the header will have just the latch as a predecessor
472 if (!single_pred_p (exit
->dest
))
473 exit
= single_pred_edge (split_edge (exit
));
475 entry
= loop_preheader_edge (loop
);
477 propagate_threaded_block_debug_into (exit
->dest
, entry
->dest
);
478 if (!gimple_duplicate_sese_region (entry
, exit
, bbs
, n_bbs
, copied_bbs
,
481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
482 fprintf (dump_file
, "Duplication failed.\n");
485 copied
.safe_push (std::make_pair (entry
, loop
));
487 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
488 this copying can introduce a case where we rely on undefined
489 signed overflow to eliminate the preheader condition, because
490 we assume that "j < j + 10" is true. We don't want to warn
491 about that case for -Wstrict-overflow, because in general we
492 don't warn about overflow involving loops. Prevent the
493 warning by setting the no_warning flag in the condition. */
494 if (warn_strict_overflow
> 0)
498 for (i
= 0; i
< n_bbs
; ++i
)
500 gimple_stmt_iterator bsi
;
502 for (bsi
= gsi_start_bb (copied_bbs
[i
]);
506 gimple
*stmt
= gsi_stmt (bsi
);
507 if (gimple_code (stmt
) == GIMPLE_COND
)
509 tree lhs
= gimple_cond_lhs (stmt
);
510 if (gimple_cond_code (stmt
) != EQ_EXPR
511 && gimple_cond_code (stmt
) != NE_EXPR
512 && INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
513 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs
)))
514 suppress_warning (stmt
, OPT_Wstrict_overflow_
);
516 else if (is_gimple_assign (stmt
))
518 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
519 tree rhs1
= gimple_assign_rhs1 (stmt
);
520 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
521 && rhs_code
!= EQ_EXPR
522 && rhs_code
!= NE_EXPR
523 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
524 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
)))
525 suppress_warning (stmt
, OPT_Wstrict_overflow_
);
531 /* Ensure that the latch and the preheader is simple (we know that they
532 are not now, since there was the loop exit condition. */
533 split_edge (loop_preheader_edge (loop
));
534 split_edge (loop_latch_edge (loop
));
536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
538 if (do_while_loop_p (loop
))
539 fprintf (dump_file
, "Loop %d is now do-while loop.\n", loop
->num
);
541 fprintf (dump_file
, "Loop %d is still not do-while loop.\n",
550 update_ssa (TODO_update_ssa
);
551 /* After updating SSA form perform CSE on the loop header
552 copies. This is esp. required for the pass before
553 vectorization since nothing cleans up copied exit tests
554 that can now be simplified. CSE from the entry of the
555 region we copied till all loop exit blocks but not
556 entering the loop itself. */
557 for (unsigned i
= 0; i
< copied
.length (); ++i
)
559 edge entry
= copied
[i
].first
;
560 loop_p loop
= copied
[i
].second
;
561 auto_vec
<edge
> exit_edges
= get_loop_exit_edges (loop
);
562 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
563 for (unsigned j
= 0; j
< exit_edges
.length (); ++j
)
564 bitmap_set_bit (exit_bbs
, exit_edges
[j
]->dest
->index
);
565 bitmap_set_bit (exit_bbs
, loop
->header
->index
);
566 do_rpo_vn (cfun
, entry
, exit_bbs
);
567 BITMAP_FREE (exit_bbs
);
573 return changed
? TODO_cleanup_cfg
: 0;
576 /* Initialize the loop structures we need, and finalize after. */
579 pass_ch::execute (function
*fun
)
581 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
582 | LOOPS_HAVE_SIMPLE_LATCHES
583 | LOOPS_HAVE_RECORDED_EXITS
);
585 unsigned int res
= copy_headers (fun
);
587 loop_optimizer_finalize ();
591 /* Assume an earlier phase has already initialized all the loop structures that
592 we need here (and perhaps others too), and that these will be finalized by
596 pass_ch_vect::execute (function
*fun
)
598 return copy_headers (fun
);
601 /* Apply header copying according to a very simple test of do-while shape. */
604 pass_ch::process_loop_p (class loop
*loop
)
606 return !do_while_loop_p (loop
);
609 /* Apply header-copying to loops where we might enable vectorization. */
612 pass_ch_vect::process_loop_p (class loop
*loop
)
614 if (!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
617 if (loop
->dont_vectorize
)
620 /* The vectorizer won't handle anything with multiple exits, so skip. */
621 edge exit
= single_exit (loop
);
625 if (!do_while_loop_p (loop
))
634 make_pass_ch_vect (gcc::context
*ctxt
)
636 return new pass_ch_vect (ctxt
);
640 make_pass_ch (gcc::context
*ctxt
)
642 return new pass_ch (ctxt
);