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"
39 /* Duplicates headers of loops if they are small enough, so that the statements
40 in the loop body are always executed when the loop is entered. This
41 increases effectiveness of code motion optimizations, and reduces the need
42 for loop preconditioning. */
44 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
45 instructions should be duplicated, limit is decreased by the actual
49 should_duplicate_loop_header_p (basic_block header
, class loop
*loop
,
52 gimple_stmt_iterator bsi
;
54 gcc_assert (!header
->aux
);
56 /* Loop header copying usually increases size of the code. This used not to
57 be true, since quite often it is possible to verify that the condition is
58 satisfied in the first iteration and therefore to eliminate it. Jump
59 threading handles these cases now. */
60 if (optimize_loop_for_size_p (loop
)
61 && !loop
->force_vectorize
)
63 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
65 " Not duplicating bb %i: optimizing for size.\n",
70 gcc_assert (EDGE_COUNT (header
->succs
) > 0);
71 if (single_succ_p (header
))
73 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
75 " Not duplicating bb %i: it is single succ.\n",
80 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
)
81 && flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 1)->dest
))
83 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
85 " Not duplicating bb %i: both successors are in loop.\n",
90 /* If this is not the original loop header, we want it to have just
91 one predecessor in order to match the && pattern. */
92 if (header
!= loop
->header
&& !single_pred_p (header
))
94 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
96 " Not duplicating bb %i: it has mutiple predecestors.\n",
101 gcond
*last
= safe_dyn_cast
<gcond
*> (last_stmt (header
));
104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
106 " Not duplicating bb %i: it does not end by conditional.\n",
111 for (gphi_iterator psi
= gsi_start_phis (header
); !gsi_end_p (psi
);
114 gphi
*phi
= psi
.phi ();
115 tree res
= gimple_phi_result (phi
);
116 if (INTEGRAL_TYPE_P (TREE_TYPE (res
))
117 || POINTER_TYPE_P (TREE_TYPE (res
)))
118 gimple_set_uid (phi
, 1 /* IV */);
120 gimple_set_uid (phi
, 0);
123 /* Count number of instructions and punt on calls.
124 Populate stmts INV/IV flag to later apply heuristics to the
125 kind of conditions we want to copy. */
126 for (bsi
= gsi_start_bb (header
); !gsi_end_p (bsi
); gsi_next (&bsi
))
128 gimple
*last
= gsi_stmt (bsi
);
130 if (gimple_code (last
) == GIMPLE_LABEL
)
133 if (is_gimple_debug (last
))
136 if (gimple_code (last
) == GIMPLE_CALL
137 && (!gimple_inexpensive_call_p (as_a
<gcall
*> (last
))
138 /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
139 at current loop's header. Don't copy in this case. */
140 || gimple_call_internal_p (last
, IFN_LOOP_DIST_ALIAS
)))
142 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
144 " Not duplicating bb %i: it contains call.\n",
149 *limit
-= estimate_num_insns (last
, &eni_size_weights
);
152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
154 " Not duplicating bb %i contains too many insns.\n",
159 /* Classify the stmt based on whether its computation is based
160 on a IV or whether it is invariant in the loop. */
161 gimple_set_uid (last
, 0);
162 if (!gimple_vuse (last
))
168 FOR_EACH_SSA_TREE_OPERAND (op
, last
, i
, SSA_OP_USE
)
169 if (!SSA_NAME_IS_DEFAULT_DEF (op
)
170 && flow_bb_inside_loop_p (loop
,
171 gimple_bb (SSA_NAME_DEF_STMT (op
))))
173 if (!(gimple_uid (SSA_NAME_DEF_STMT (op
)) & 2 /* INV */))
175 if (gimple_uid (SSA_NAME_DEF_STMT (op
)) & 1 /* IV */)
178 gimple_set_uid (last
, (iv
? 1 : 0) | (inv
? 2 : 0));
182 /* If the condition tests a non-IV loop variant we do not want to rotate
183 the loop further. Unless this is the original loop header. */
184 tree lhs
= gimple_cond_lhs (last
);
185 tree rhs
= gimple_cond_rhs (last
);
186 if (header
!= loop
->header
187 && ((TREE_CODE (lhs
) == SSA_NAME
188 && !SSA_NAME_IS_DEFAULT_DEF (lhs
)
189 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (lhs
)))
190 && gimple_uid (SSA_NAME_DEF_STMT (lhs
)) == 0)
191 || (TREE_CODE (rhs
) == SSA_NAME
192 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
193 && flow_bb_inside_loop_p (loop
,
194 gimple_bb (SSA_NAME_DEF_STMT (rhs
)))
195 && gimple_uid (SSA_NAME_DEF_STMT (rhs
)) == 0)))
197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
199 " Not duplicating bb %i: condition based on non-IV loop"
200 " variant.\n", header
->index
);
204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
205 fprintf (dump_file
, " Will duplicate bb %i\n", header
->index
);
209 /* Checks whether LOOP is a do-while style loop. */
212 do_while_loop_p (class loop
*loop
)
214 gimple
*stmt
= last_stmt (loop
->latch
);
216 /* If the latch of the loop is not empty, it is not a do-while loop. */
218 && gimple_code (stmt
) != GIMPLE_LABEL
)
220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
222 "Loop %i is not do-while loop: latch is not empty.\n",
227 /* If the latch does not have a single predecessor, it is not a
229 if (!single_pred_p (loop
->latch
))
231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
233 "Loop %i is not do-while loop: latch has multiple "
234 "predecessors.\n", loop
->num
);
238 /* If the latch predecessor doesn't exit the loop, it is not a
240 if (!loop_exits_from_bb_p (loop
, single_pred (loop
->latch
)))
242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
244 "Loop %i is not do-while loop: latch predecessor "
245 "does not exit loop.\n", loop
->num
);
249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
250 fprintf (dump_file
, "Loop %i is do-while loop\n", loop
->num
);
257 /* Common superclass for both header-copying phases. */
258 class ch_base
: public gimple_opt_pass
261 ch_base (pass_data data
, gcc::context
*ctxt
)
262 : gimple_opt_pass (data
, ctxt
)
265 /* Copies headers of all loops in FUN for which process_loop_p is true. */
266 unsigned int copy_headers (function
*fun
);
268 /* Return true to copy headers of LOOP or false to skip. */
269 virtual bool process_loop_p (class loop
*loop
) = 0;
272 const pass_data pass_data_ch
=
274 GIMPLE_PASS
, /* type */
276 OPTGROUP_LOOP
, /* optinfo_flags */
277 TV_TREE_CH
, /* tv_id */
278 ( PROP_cfg
| PROP_ssa
), /* properties_required */
279 0, /* properties_provided */
280 0, /* properties_destroyed */
281 0, /* todo_flags_start */
282 0, /* todo_flags_finish */
285 class pass_ch
: public ch_base
288 pass_ch (gcc::context
*ctxt
)
289 : ch_base (pass_data_ch
, ctxt
)
292 /* opt_pass methods: */
293 virtual bool gate (function
*) { return flag_tree_ch
!= 0; }
295 /* Initialize and finalize loop structures, copying headers inbetween. */
296 virtual unsigned int execute (function
*);
298 opt_pass
* clone () { return new pass_ch (m_ctxt
); }
301 /* ch_base method: */
302 virtual bool process_loop_p (class loop
*loop
);
305 const pass_data pass_data_ch_vect
=
307 GIMPLE_PASS
, /* type */
308 "ch_vect", /* name */
309 OPTGROUP_LOOP
, /* optinfo_flags */
310 TV_TREE_CH
, /* tv_id */
311 ( PROP_cfg
| PROP_ssa
), /* properties_required */
312 0, /* properties_provided */
313 0, /* properties_destroyed */
314 0, /* todo_flags_start */
315 0, /* todo_flags_finish */
318 /* This is a more aggressive version of the same pass, designed to run just
319 before if-conversion and vectorization, to put more loops into the form
320 required for those phases. */
321 class pass_ch_vect
: public ch_base
324 pass_ch_vect (gcc::context
*ctxt
)
325 : ch_base (pass_data_ch_vect
, ctxt
)
328 /* opt_pass methods: */
329 virtual bool gate (function
*fun
)
331 return flag_tree_ch
!= 0
332 && (flag_tree_loop_vectorize
!= 0 || fun
->has_force_vectorize_loops
);
335 /* Just copy headers, no initialization/finalization of loop structures. */
336 virtual unsigned int execute (function
*);
339 /* ch_base method: */
340 virtual bool process_loop_p (class loop
*loop
);
341 }; // class pass_ch_vect
343 /* For all loops, copy the condition at the end of the loop body in front
344 of the loop. This is beneficial since it increases efficiency of
345 code motion optimizations. It also saves one jump on entry to the loop. */
348 ch_base::copy_headers (function
*fun
)
352 basic_block
*bbs
, *copied_bbs
;
355 bool changed
= false;
357 if (number_of_loops (fun
) <= 1)
360 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
361 copied_bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
362 bbs_size
= n_basic_blocks_for_fn (fun
);
364 auto_vec
<std::pair
<edge
, loop_p
> > copied
;
366 for (auto loop
: loops_list (cfun
, 0))
368 int initial_limit
= param_max_loop_header_insns
;
369 int remaining_limit
= initial_limit
;
370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 "Analyzing loop %i\n", loop
->num
);
374 header
= loop
->header
;
376 /* If the loop is already a do-while style one (either because it was
377 written as such, or because jump threading transformed it into one),
378 we might be in fact peeling the first iteration of the loop. This
379 in general is not a good idea. Also avoid touching infinite loops. */
380 if (!loop_has_exit_edges (loop
)
381 || !process_loop_p (loop
))
384 /* Iterate the header copying up to limit; this takes care of the cases
385 like while (a && b) {...}, where we want to have both of the conditions
386 copied. TODO -- handle while (a || b) - like cases, by not requiring
387 the header to have just a single successor and copying up to
392 while (should_duplicate_loop_header_p (header
, loop
, &remaining_limit
))
394 /* Find a successor of header that is inside a loop; i.e. the new
395 header after the condition is copied. */
396 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
))
397 exit
= EDGE_SUCC (header
, 0);
399 exit
= EDGE_SUCC (header
, 1);
400 bbs
[n_bbs
++] = header
;
401 gcc_assert (bbs_size
> n_bbs
);
408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
410 "Duplicating header of the loop %d up to edge %d->%d,"
412 loop
->num
, exit
->src
->index
, exit
->dest
->index
,
413 initial_limit
- remaining_limit
);
415 /* Ensure that the header will have just the latch as a predecessor
417 if (!single_pred_p (exit
->dest
))
418 exit
= single_pred_edge (split_edge (exit
));
420 entry
= loop_preheader_edge (loop
);
422 propagate_threaded_block_debug_into (exit
->dest
, entry
->dest
);
423 if (!gimple_duplicate_sese_region (entry
, exit
, bbs
, n_bbs
, copied_bbs
,
426 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
427 fprintf (dump_file
, "Duplication failed.\n");
430 copied
.safe_push (std::make_pair (entry
, loop
));
432 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
433 this copying can introduce a case where we rely on undefined
434 signed overflow to eliminate the preheader condition, because
435 we assume that "j < j + 10" is true. We don't want to warn
436 about that case for -Wstrict-overflow, because in general we
437 don't warn about overflow involving loops. Prevent the
438 warning by setting the no_warning flag in the condition. */
439 if (warn_strict_overflow
> 0)
443 for (i
= 0; i
< n_bbs
; ++i
)
445 gimple_stmt_iterator bsi
;
447 for (bsi
= gsi_start_bb (copied_bbs
[i
]);
451 gimple
*stmt
= gsi_stmt (bsi
);
452 if (gimple_code (stmt
) == GIMPLE_COND
)
454 tree lhs
= gimple_cond_lhs (stmt
);
455 if (gimple_cond_code (stmt
) != EQ_EXPR
456 && gimple_cond_code (stmt
) != NE_EXPR
457 && INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
458 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs
)))
459 suppress_warning (stmt
, OPT_Wstrict_overflow_
);
461 else if (is_gimple_assign (stmt
))
463 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
464 tree rhs1
= gimple_assign_rhs1 (stmt
);
465 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
466 && rhs_code
!= EQ_EXPR
467 && rhs_code
!= NE_EXPR
468 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
469 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1
)))
470 suppress_warning (stmt
, OPT_Wstrict_overflow_
);
476 /* Ensure that the latch and the preheader is simple (we know that they
477 are not now, since there was the loop exit condition. */
478 split_edge (loop_preheader_edge (loop
));
479 split_edge (loop_latch_edge (loop
));
481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
483 if (do_while_loop_p (loop
))
484 fprintf (dump_file
, "Loop %d is now do-while loop.\n", loop
->num
);
486 fprintf (dump_file
, "Loop %d is still not do-while loop.\n",
495 update_ssa (TODO_update_ssa
);
496 /* After updating SSA form perform CSE on the loop header
497 copies. This is esp. required for the pass before
498 vectorization since nothing cleans up copied exit tests
499 that can now be simplified. CSE from the entry of the
500 region we copied till all loop exit blocks but not
501 entering the loop itself. */
502 for (unsigned i
= 0; i
< copied
.length (); ++i
)
504 edge entry
= copied
[i
].first
;
505 loop_p loop
= copied
[i
].second
;
506 auto_vec
<edge
> exit_edges
= get_loop_exit_edges (loop
);
507 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
508 for (unsigned j
= 0; j
< exit_edges
.length (); ++j
)
509 bitmap_set_bit (exit_bbs
, exit_edges
[j
]->dest
->index
);
510 bitmap_set_bit (exit_bbs
, loop
->header
->index
);
511 do_rpo_vn (cfun
, entry
, exit_bbs
);
512 BITMAP_FREE (exit_bbs
);
518 return changed
? TODO_cleanup_cfg
: 0;
521 /* Initialize the loop structures we need, and finalize after. */
524 pass_ch::execute (function
*fun
)
526 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
527 | LOOPS_HAVE_SIMPLE_LATCHES
528 | LOOPS_HAVE_RECORDED_EXITS
);
530 unsigned int res
= copy_headers (fun
);
532 loop_optimizer_finalize ();
536 /* Assume an earlier phase has already initialized all the loop structures that
537 we need here (and perhaps others too), and that these will be finalized by
541 pass_ch_vect::execute (function
*fun
)
543 return copy_headers (fun
);
546 /* Apply header copying according to a very simple test of do-while shape. */
549 pass_ch::process_loop_p (class loop
*loop
)
551 return !do_while_loop_p (loop
);
554 /* Apply header-copying to loops where we might enable vectorization. */
557 pass_ch_vect::process_loop_p (class loop
*loop
)
559 if (!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
562 if (loop
->dont_vectorize
)
565 /* The vectorizer won't handle anything with multiple exits, so skip. */
566 edge exit
= single_exit (loop
);
570 if (!do_while_loop_p (loop
))
579 make_pass_ch_vect (gcc::context
*ctxt
)
581 return new pass_ch_vect (ctxt
);
585 make_pass_ch (gcc::context
*ctxt
)
587 return new pass_ch (ctxt
);