1 /* Loop header copying on trees.
2 Copyright (C) 2004-2023 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"
43 /* Duplicates headers of loops if they are small enough, so that the statements
44 in the loop body are always executed when the loop is entered. This
45 increases effectiveness of code motion optimizations, and reduces the need
46 for loop preconditioning. */
48 /* Given a path through edge E, whose last statement is COND, return
49 the range of the solved conditional in R. */
52 edge_range_query (irange
&r
, edge e
, gcond
*cond
, gimple_ranger
&ranger
)
54 auto_vec
<basic_block
> path (2);
55 path
.safe_push (e
->dest
);
56 path
.safe_push (e
->src
);
57 path_range_query
query (ranger
, path
);
58 if (!query
.range_of_stmt (r
, cond
))
59 r
.set_varying (boolean_type_node
);
62 /* Return edge that is true in the first iteration of the loop
63 and NULL otherwise. */
66 static_loop_exit (class loop
*l
, gimple_ranger
*ranger
)
68 edge e
= loop_preheader_edge (l
);
69 gcond
*last
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (e
->dest
));
76 extract_true_false_edges_from_block (e
->dest
, &true_e
, &false_e
);
78 /* If neither edge is the exit edge, this is not a case we'd like to
80 if (!loop_exit_edge_p (l
, true_e
) && !loop_exit_edge_p (l
, false_e
))
83 int_range
<1> desired_static_range
;
84 if (loop_exit_edge_p (l
, true_e
))
86 desired_static_range
= range_false ();
91 desired_static_range
= range_true ();
96 edge_range_query (r
, e
, last
, *ranger
);
97 return r
== desired_static_range
? ret_e
: NULL
;
100 /* Return true if OP is invariant. */
103 loop_invariant_op_p (class loop
*loop
,
106 if (is_gimple_min_invariant (op
))
108 if (SSA_NAME_IS_DEFAULT_DEF (op
)
109 || !flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (op
))))
111 return gimple_uid (SSA_NAME_DEF_STMT (op
)) & 2;
114 /* Return true if OP looks like it is derived from IV. */
117 loop_iv_derived_p (class loop
*loop
,
120 /* Always check for invariant first. */
121 gcc_checking_assert (!is_gimple_min_invariant (op
)
122 && !SSA_NAME_IS_DEFAULT_DEF (op
)
123 && flow_bb_inside_loop_p (loop
,
124 gimple_bb (SSA_NAME_DEF_STMT (op
))));
125 return gimple_uid (SSA_NAME_DEF_STMT (op
)) & 1;
128 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
129 instructions should be duplicated, limit is decreased by the actual
133 should_duplicate_loop_header_p (basic_block header
, class loop
*loop
,
135 hash_set
<edge
> *invariant_exits
)
137 gimple_stmt_iterator bsi
;
139 gcc_assert (!header
->aux
);
141 gcc_assert (EDGE_COUNT (header
->succs
) > 0);
142 if (single_succ_p (header
))
144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
146 " Not duplicating bb %i: it is single succ.\n",
151 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
)
152 && flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 1)->dest
))
154 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
156 " Not duplicating bb %i: both successors are in loop.\n",
161 /* If this is not the original loop header, we want it to have just
162 one predecessor in order to match the && pattern. */
163 if (header
!= loop
->header
&& !single_pred_p (header
))
165 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
167 " Not duplicating bb %i: it has mutiple predecestors.\n",
172 gcond
*last
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (header
));
175 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
177 " Not duplicating bb %i: it does not end by conditional.\n",
182 for (gphi_iterator psi
= gsi_start_phis (header
); !gsi_end_p (psi
);
184 /* If this is actual loop header PHIs indicate that the SSA_NAME
185 may be IV. Otherwise just give up. */
186 if (header
== loop
->header
)
188 gphi
*phi
= psi
.phi ();
189 tree res
= gimple_phi_result (phi
);
190 if (INTEGRAL_TYPE_P (TREE_TYPE (res
))
191 || POINTER_TYPE_P (TREE_TYPE (res
)))
192 gimple_set_uid (phi
, 1 /* IV */);
194 gimple_set_uid (phi
, 0);
197 gimple_set_uid (psi
.phi (), 0);
199 /* Count number of instructions and punt on calls.
200 Populate stmts INV/IV flag to later apply heuristics to the
201 kind of conditions we want to copy. */
202 for (bsi
= gsi_start_bb (header
); !gsi_end_p (bsi
); gsi_next (&bsi
))
204 gimple
*last
= gsi_stmt (bsi
);
206 if (gimple_code (last
) == GIMPLE_LABEL
)
209 if (is_gimple_debug (last
))
212 if (gimple_code (last
) == GIMPLE_CALL
213 && (!gimple_inexpensive_call_p (as_a
<gcall
*> (last
))
214 /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
215 at current loop's header. Don't copy in this case. */
216 || gimple_call_internal_p (last
, IFN_LOOP_DIST_ALIAS
)))
218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
220 " Not duplicating bb %i: it contains call.\n",
225 *limit
-= estimate_num_insns (last
, &eni_size_weights
);
228 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
230 " Not duplicating bb %i contains too many insns.\n",
235 /* Classify the stmt based on whether its computation is based
236 on a IV or whether it is invariant in the loop. */
237 gimple_set_uid (last
, 0);
238 if (!gimple_vuse (last
)
239 && gimple_code (last
) != GIMPLE_ASM
240 && (gimple_code (last
) != GIMPLE_CALL
241 || gimple_call_flags (last
) & ECF_CONST
))
247 FOR_EACH_SSA_TREE_OPERAND (op
, last
, i
, SSA_OP_USE
)
248 if (!loop_invariant_op_p (loop
, op
))
250 if (!loop_iv_derived_p (loop
, op
))
259 gimple_set_uid (last
, (iv
? 1 : 0) | (inv
? 2 : 0));
263 /* If the condition tests a non-IV loop variant we do not want to rotate
264 the loop further. Unless this is the original loop header. */
265 tree lhs
= gimple_cond_lhs (last
);
266 tree rhs
= gimple_cond_rhs (last
);
267 bool lhs_invariant
= loop_invariant_op_p (loop
, lhs
);
268 bool rhs_invariant
= loop_invariant_op_p (loop
, rhs
);
269 if (lhs_invariant
&& rhs_invariant
)
275 FOR_EACH_EDGE (e
, ei
, header
->succs
)
276 if (loop_exit_edge_p (loop
, e
))
278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
280 " Will elliminate invariant exit %i->%i\n",
281 e
->src
->index
, e
->dest
->index
);
282 invariant_exits
->add (e
);
287 /* TODO: This is heuristics that claims that IV based ocnditionals will
288 likely be optimized out in duplicated header. We could use ranger
289 query instead to tell this more precisely. */
290 if (header
!= loop
->header
291 && ((!lhs_invariant
&& !loop_iv_derived_p (loop
, lhs
))
292 || (!rhs_invariant
&& !loop_iv_derived_p (loop
, rhs
))))
294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 " Not duplicating bb %i: condition based on non-IV loop"
297 " variant.\n", header
->index
);
304 /* Checks whether LOOP is a do-while style loop. */
307 do_while_loop_p (class loop
*loop
)
309 gimple
*stmt
= last_nondebug_stmt (loop
->latch
);
311 /* If the latch of the loop is not empty, it is not a do-while loop. */
313 && gimple_code (stmt
) != GIMPLE_LABEL
)
315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
317 "Loop %i is not do-while loop: latch is not empty.\n",
322 /* If the latch does not have a single predecessor, it is not a
324 if (!single_pred_p (loop
->latch
))
326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
328 "Loop %i is not do-while loop: latch has multiple "
329 "predecessors.\n", loop
->num
);
333 /* If the latch predecessor doesn't exit the loop, it is not a
335 if (!loop_exits_from_bb_p (loop
, single_pred (loop
->latch
)))
337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
339 "Loop %i is not do-while loop: latch predecessor "
340 "does not exit loop.\n", loop
->num
);
344 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
345 fprintf (dump_file
, "Loop %i is do-while loop\n", loop
->num
);
350 /* Update profile after header copying of LOOP.
351 REGION is the original (in loop) sequence, REGION_COPY is the
352 duplicated header (now outside of loop). N_REGION is number of
354 ELIMINATED_EDGE is edge to be removed from duplicated sequence.
355 INVARIANT_EXITS are edges in the loop body to be elimianted
356 since they are loop invariants
358 So We expect the following:
360 // region_copy_start entry will be scaled to entry_count
361 if (cond1) <- this condition will become false
362 and we update probabilities
364 if (cond2) <- this condition is loop invariant
366 goto loop_header <- this will be redirected to loop.
372 if (cond1) <- we need to update probabbility here
374 if (cond2) <- and determine scaling factor here.
375 moreover cond2 is now always true
381 Adding support for more exits can be done similarly,
382 but only consumer so far is tree-ssa-loop-ch and it uses only this
383 to handle the common case of peeling headers which have
384 conditionals known to be always true upon entry. */
387 update_profile_after_ch (class loop
*loop
,
388 basic_block
*region
, basic_block
*region_copy
,
389 unsigned n_region
, edge eliminated_edge
,
390 hash_set
<edge
> *invariant_exits
,
391 profile_count entry_count
)
393 for (unsigned int i
= 0; i
< n_region
; i
++)
395 edge exit_e
, exit_e_copy
, e
, e_copy
;
396 if (EDGE_COUNT (region
[i
]->succs
) == 1)
398 region_copy
[i
]->count
= entry_count
;
399 region
[i
]->count
-= entry_count
;
403 gcc_checking_assert (EDGE_COUNT (region
[i
]->succs
) == 2);
404 if (loop_exit_edge_p (loop
,
405 EDGE_SUCC (region
[i
], 0)))
407 exit_e
= EDGE_SUCC (region
[i
], 0);
408 exit_e_copy
= EDGE_SUCC (region_copy
[i
], 0);
409 e
= EDGE_SUCC (region
[i
], 1);
410 e_copy
= EDGE_SUCC (region_copy
[i
], 1);
414 exit_e
= EDGE_SUCC (region
[i
], 1);
415 exit_e_copy
= EDGE_SUCC (region_copy
[i
], 1);
416 e
= EDGE_SUCC (region
[i
], 0);
417 e_copy
= EDGE_SUCC (region_copy
[i
], 0);
419 gcc_assert (i
== n_region
- 1
420 || (e
->dest
== region
[i
+ 1]
421 && e_copy
->dest
== region_copy
[i
+ 1]));
422 region_copy
[i
]->count
= entry_count
;
423 profile_count exit_e_count
= exit_e
->count ();
424 if (eliminated_edge
== exit_e
)
426 /* Update profile and the conditional.
427 CFG update is done by caller. */
428 e_copy
->probability
= profile_probability::always ();
429 exit_e_copy
->probability
= profile_probability::never ();
431 = as_a
<gcond
*>(*gsi_last_bb (region_copy
[i
]));
432 if (e_copy
->flags
& EDGE_TRUE_VALUE
)
433 gimple_cond_make_true (cond_stmt
);
435 gimple_cond_make_false (cond_stmt
);
436 update_stmt (cond_stmt
);
437 /* Header copying is a special case of jump threading, so use
438 common code to update loop body exit condition. */
439 update_bb_profile_for_threading (region
[i
], entry_count
, e
);
440 eliminated_edge
= NULL
;
443 region
[i
]->count
-= region_copy
[i
]->count
;
444 if (invariant_exits
->contains (exit_e
))
446 invariant_exits
->remove (exit_e
);
447 /* All exits will happen in exit_e_copy which is out of the
448 loop, so increase probability accordingly.
449 If the edge is eliminated_edge we already corrected
451 if (entry_count
.nonzero_p () && eliminated_edge
!= exit_e
)
452 set_edge_probability_and_rescale_others
453 (exit_e_copy
, exit_e_count
.probability_in
455 /* Eliminate in-loop conditional. */
456 e
->probability
= profile_probability::always ();
457 exit_e
->probability
= profile_probability::never ();
458 gcond
*cond_stmt
= as_a
<gcond
*>(*gsi_last_bb (region
[i
]));
459 if (e
->flags
& EDGE_TRUE_VALUE
)
460 gimple_cond_make_true (cond_stmt
);
462 gimple_cond_make_false (cond_stmt
);
463 update_stmt (cond_stmt
);
465 entry_count
= e_copy
->count ();
467 /* Be sure that we seen all edges we are supposed to update. */
468 gcc_checking_assert (!eliminated_edge
469 && invariant_exits
->is_empty ());
474 /* Common superclass for both header-copying phases. */
475 class ch_base
: public gimple_opt_pass
478 ch_base (pass_data data
, gcc::context
*ctxt
)
479 : gimple_opt_pass (data
, ctxt
)
482 /* Copies headers of all loops in FUN for which process_loop_p is true. */
483 unsigned int copy_headers (function
*fun
);
485 /* Return true to copy headers of LOOP or false to skip. */
486 virtual bool process_loop_p (class loop
*loop
) = 0;
489 const pass_data pass_data_ch
=
491 GIMPLE_PASS
, /* type */
493 OPTGROUP_LOOP
, /* optinfo_flags */
494 TV_TREE_CH
, /* tv_id */
495 ( PROP_cfg
| PROP_ssa
), /* properties_required */
496 0, /* properties_provided */
497 0, /* properties_destroyed */
498 0, /* todo_flags_start */
499 0, /* todo_flags_finish */
502 class pass_ch
: public ch_base
505 pass_ch (gcc::context
*ctxt
)
506 : ch_base (pass_data_ch
, ctxt
)
509 /* opt_pass methods: */
510 bool gate (function
*) final override
{ return flag_tree_ch
!= 0; }
512 /* Initialize and finalize loop structures, copying headers inbetween. */
513 unsigned int execute (function
*) final override
;
515 opt_pass
* clone () final override
{ return new pass_ch (m_ctxt
); }
518 /* ch_base method: */
519 bool process_loop_p (class loop
*loop
) final override
;
522 const pass_data pass_data_ch_vect
=
524 GIMPLE_PASS
, /* type */
525 "ch_vect", /* name */
526 OPTGROUP_LOOP
, /* optinfo_flags */
527 TV_TREE_CH
, /* tv_id */
528 ( PROP_cfg
| PROP_ssa
), /* properties_required */
529 0, /* properties_provided */
530 0, /* properties_destroyed */
531 0, /* todo_flags_start */
532 0, /* todo_flags_finish */
535 /* This is a more aggressive version of the same pass, designed to run just
536 before if-conversion and vectorization, to put more loops into the form
537 required for those phases. */
538 class pass_ch_vect
: public ch_base
541 pass_ch_vect (gcc::context
*ctxt
)
542 : ch_base (pass_data_ch_vect
, ctxt
)
545 /* opt_pass methods: */
546 bool gate (function
*fun
) final override
548 return flag_tree_ch
!= 0
549 && (flag_tree_loop_vectorize
!= 0 || fun
->has_force_vectorize_loops
);
552 /* Just copy headers, no initialization/finalization of loop structures. */
553 unsigned int execute (function
*) final override
;
556 /* ch_base method: */
557 bool process_loop_p (class loop
*loop
) final override
;
558 }; // class pass_ch_vect
560 /* For all loops, copy the condition at the end of the loop body in front
561 of the loop. This is beneficial since it increases efficiency of
562 code motion optimizations. It also saves one jump on entry to the loop. */
565 ch_base::copy_headers (function
*fun
)
568 edge exit
, nonexit
, entry
;
569 basic_block
*bbs
, *copied_bbs
;
572 bool changed
= false;
574 if (number_of_loops (fun
) <= 1)
577 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
578 copied_bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
579 bbs_size
= n_basic_blocks_for_fn (fun
);
581 struct candidate
{class loop
*loop
; edge static_exit
;};
582 auto_vec
<struct candidate
> candidates
;
583 auto_vec
<std::pair
<edge
, loop_p
> > copied
;
584 auto_vec
<class loop
*> loops_to_unloop
;
585 auto_vec
<int> loops_to_unloop_nunroll
;
587 mark_dfs_back_edges ();
588 gimple_ranger
*ranger
= new gimple_ranger
;
589 for (auto loop
: loops_list (cfun
, 0))
591 int initial_limit
= param_max_loop_header_insns
;
592 int remaining_limit
= initial_limit
;
593 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
595 "Analyzing loop %i\n", loop
->num
);
597 header
= loop
->header
;
598 if (!get_max_loop_iterations_int (loop
))
600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
601 fprintf (dump_file
, "Loop %d never loops.\n", loop
->num
);
602 scale_loop_profile (loop
, profile_probability::always (), 0);
603 loops_to_unloop
.safe_push (loop
);
604 loops_to_unloop_nunroll
.safe_push (0);
608 /* If the loop is already a do-while style one (either because it was
609 written as such, or because jump threading transformed it into one),
610 we might be in fact peeling the first iteration of the loop. This
611 in general is not a good idea. Also avoid touching infinite loops. */
612 if (!loop_has_exit_edges (loop
)
613 || !process_loop_p (loop
))
616 edge static_exit
= static_loop_exit (loop
, ranger
);
618 /* Avoid loop header copying when optimizing for size unless we can
619 determine that the loop condition is static in the first
621 if (optimize_loop_for_size_p (loop
)
622 && !loop
->force_vectorize
625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
627 " Not duplicating bb %i: optimizing for size.\n",
632 if (should_duplicate_loop_header_p (header
, loop
, &remaining_limit
, NULL
))
633 candidates
.safe_push ({loop
, static_exit
});
635 /* Do not use ranger after we change the IL and not have updated SSA. */
638 for (auto candidate
: candidates
)
640 class loop
*loop
= candidate
.loop
;
641 int initial_limit
= param_max_loop_header_insns
;
642 int remaining_limit
= initial_limit
;
643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
645 "Copying headers of loop %i\n", loop
->num
);
647 header
= loop
->header
;
649 /* Iterate the header copying up to limit; this takes care of the cases
650 like while (a && b) {...}, where we want to have both of the conditions
651 copied. TODO -- handle while (a || b) - like cases, by not requiring
652 the header to have just a single successor and copying up to
658 profile_count exit_count
= profile_count::zero ();
659 profile_count entry_count
= profile_count::zero ();
662 hash_set
<edge
> invariant_exits
;
663 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
664 if (e
->src
!= loop
->latch
)
665 entry_count
+= e
->count ();
666 while (should_duplicate_loop_header_p (header
, loop
, &remaining_limit
,
669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
670 fprintf (dump_file
, " Will duplicate bb %i\n", header
->index
);
672 /* Find a successor of header that is inside a loop; i.e. the new
673 header after the condition is copied. */
674 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
))
676 nonexit
= EDGE_SUCC (header
, 0);
677 exit
= EDGE_SUCC (header
, 1);
681 nonexit
= EDGE_SUCC (header
, 1);
682 exit
= EDGE_SUCC (header
, 0);
684 exit_count
+= exit
->count ();
686 bbs
[n_bbs
++] = header
;
687 gcc_assert (bbs_size
> n_bbs
);
688 header
= nonexit
->dest
;
694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
697 "Duplicating header of the loop %d up to edge %d->%d,"
699 loop
->num
, exit
->src
->index
, exit
->dest
->index
,
700 initial_limit
- remaining_limit
);
701 if (candidate
.static_exit
)
703 " Will eliminate peeled conditional in bb %d.\n",
704 candidate
.static_exit
->src
->index
);
707 /* Ensure that the header will have just the latch as a predecessor
709 if (!single_pred_p (nonexit
->dest
))
711 header
= split_edge (nonexit
);
712 exit
= single_pred_edge (header
);
715 entry
= loop_preheader_edge (loop
);
717 propagate_threaded_block_debug_into (exit
->dest
, entry
->dest
);
718 if (!gimple_duplicate_seme_region (entry
, exit
, bbs
, n_bbs
, copied_bbs
,
721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
722 fprintf (dump_file
, "Duplication failed.\n");
725 if (loop
->header
->count
.initialized_p ())
726 update_profile_after_ch (loop
, bbs
, copied_bbs
, n_bbs
,
727 candidate
.static_exit
, &invariant_exits
,
729 copied
.safe_push (std::make_pair (entry
, loop
));
731 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
732 this copying can introduce a case where we rely on undefined
733 signed overflow to eliminate the preheader condition, because
734 we assume that "j < j + 10" is true. We don't want to warn
735 about that case for -Wstrict-overflow, because in general we
736 don't warn about overflow involving loops. Prevent the
737 warning by setting the no_warning flag in the condition. */
738 if (warn_strict_overflow
> 0)
742 for (i
= 0; i
< n_bbs
; ++i
)
744 gimple_stmt_iterator bsi
;
746 for (bsi
= gsi_start_bb (copied_bbs
[i
]);
750 gimple
*stmt
= gsi_stmt (bsi
);
751 if (gimple_code (stmt
) == GIMPLE_COND
)
753 tree lhs
= gimple_cond_lhs (stmt
);
754 if (gimple_cond_code (stmt
) != EQ_EXPR
755 && gimple_cond_code (stmt
) != NE_EXPR
756 && INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
757 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs
)))
758 suppress_warning (stmt
, OPT_Wstrict_overflow_
);
760 else if (is_gimple_assign (stmt
))
762 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
763 tree rhs1
= gimple_assign_rhs1 (stmt
);
764 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
765 && rhs_code
!= EQ_EXPR
766 && rhs_code
!= NE_EXPR
767 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
768 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
)))
769 suppress_warning (stmt
, OPT_Wstrict_overflow_
);
775 /* Update header of the loop. */
776 loop
->header
= header
;
777 /* Find correct latch. We only duplicate chain of conditionals so
778 there should be precisely two edges to the new header. One entry
779 edge and one to latch. */
780 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
781 if (header
!= e
->src
)
783 loop
->latch
= e
->src
;
786 /* Ensure that the latch is simple. */
787 if (!single_succ_p (loop_latch_edge (loop
)->src
))
788 split_edge (loop_latch_edge (loop
));
790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
792 if (do_while_loop_p (loop
))
793 fprintf (dump_file
, "Loop %d is now do-while loop.\n", loop
->num
);
795 fprintf (dump_file
, "Loop %d is still not do-while loop.\n",
797 fprintf (dump_file
, "Exit count: ");
798 exit_count
.dump (dump_file
);
799 fprintf (dump_file
, "\nEntry count: ");
800 entry_count
.dump (dump_file
);
801 fprintf (dump_file
, "\n");
804 /* We possibly decreased number of itrations by 1. */
805 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
806 bool precise
= (nexits
== (int) exits
.length ());
807 /* Check that loop may not terminate in other way than via
808 basic blocks we duplicated. */
811 basic_block
*bbs
= get_loop_body (loop
);
812 for (unsigned i
= 0; i
< loop
->num_nodes
&& precise
; ++i
)
814 basic_block bb
= bbs
[i
];
815 bool found_exit
= false;
816 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
817 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
822 /* If BB has exit, it was duplicated. */
825 /* Give up on irreducible loops. */
826 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
831 /* Check that inner loops are finite. */
832 for (class loop
*l
= bb
->loop_father
; l
!= loop
&& precise
;
839 /* Verify that there is no statement that may be terminate
840 execution in a way not visible to CFG. */
841 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
);
842 !gsi_end_p (bsi
); gsi_next (&bsi
))
843 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
849 && get_max_loop_iterations_int (loop
) == 1)
851 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
852 fprintf (dump_file
, "Loop %d no longer loops.\n", loop
->num
);
853 scale_loop_profile (loop
, profile_probability::always (), 0);
854 loops_to_unloop
.safe_push (loop
);
855 loops_to_unloop_nunroll
.safe_push (0);
859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
862 " decreased number of iterations of loop %d by 1.\n",
864 adjust_loop_info_after_peeling (loop
, 1, true);
866 else if (exit_count
>= entry_count
.apply_scale (9, 10))
868 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
870 "Peeled likely exits: likely decreased number "
871 "of iterations of loop %d by 1.\n", loop
->num
);
872 adjust_loop_info_after_peeling (loop
, 1, false);
874 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 "Not decreased number"
877 " of iterations of loop %d; likely exits remains.\n",
885 update_ssa (TODO_update_ssa
);
886 /* After updating SSA form perform CSE on the loop header
887 copies. This is esp. required for the pass before
888 vectorization since nothing cleans up copied exit tests
889 that can now be simplified. CSE from the entry of the
890 region we copied till all loop exit blocks but not
891 entering the loop itself. */
892 for (unsigned i
= 0; i
< copied
.length (); ++i
)
894 edge entry
= copied
[i
].first
;
895 loop_p loop
= copied
[i
].second
;
896 auto_vec
<edge
> exit_edges
= get_loop_exit_edges (loop
);
897 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
898 for (unsigned j
= 0; j
< exit_edges
.length (); ++j
)
899 bitmap_set_bit (exit_bbs
, exit_edges
[j
]->dest
->index
);
900 bitmap_set_bit (exit_bbs
, loop
->header
->index
);
901 do_rpo_vn (cfun
, entry
, exit_bbs
);
902 BITMAP_FREE (exit_bbs
);
905 if (!loops_to_unloop
.is_empty ())
907 bool irred_invalidated
;
908 unloop_loops (loops_to_unloop
, loops_to_unloop_nunroll
, NULL
, &irred_invalidated
);
914 return changed
? TODO_cleanup_cfg
: 0;
917 /* Initialize the loop structures we need, and finalize after. */
920 pass_ch::execute (function
*fun
)
922 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
923 | LOOPS_HAVE_SIMPLE_LATCHES
924 | LOOPS_HAVE_RECORDED_EXITS
);
926 unsigned int res
= copy_headers (fun
);
928 loop_optimizer_finalize ();
932 /* Assume an earlier phase has already initialized all the loop structures that
933 we need here (and perhaps others too), and that these will be finalized by
937 pass_ch_vect::execute (function
*fun
)
939 return copy_headers (fun
);
942 /* Apply header copying according to a very simple test of do-while shape. */
945 pass_ch::process_loop_p (class loop
*loop
)
947 return !do_while_loop_p (loop
);
950 /* Apply header-copying to loops where we might enable vectorization. */
953 pass_ch_vect::process_loop_p (class loop
*loop
)
955 if (!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
958 if (loop
->dont_vectorize
)
961 /* The vectorizer won't handle anything with multiple exits, so skip. */
962 edge exit
= single_exit (loop
);
966 if (!do_while_loop_p (loop
))
975 make_pass_ch_vect (gcc::context
*ctxt
)
977 return new pass_ch_vect (ctxt
);
981 make_pass_ch (gcc::context
*ctxt
)
983 return new pass_ch (ctxt
);