1 /* Loop header copying on trees.
2 Copyright (C) 2004-2015 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-scopedtables.h"
35 #include "tree-ssa-threadedge.h"
37 /* Duplicates headers of loops if they are small enough, so that the statements
38 in the loop body are always executed when the loop is entered. This
39 increases effectiveness of code motion optimizations, and reduces the need
40 for loop preconditioning. */
42 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
43 instructions should be duplicated, limit is decreased by the actual
47 should_duplicate_loop_header_p (basic_block header
, struct loop
*loop
,
50 gimple_stmt_iterator bsi
;
53 /* Do not copy one block more than once (we do not really want to do
54 loop peeling here). */
58 /* Loop header copying usually increases size of the code. This used not to
59 be true, since quite often it is possible to verify that the condition is
60 satisfied in the first iteration and therefore to eliminate it. Jump
61 threading handles these cases now. */
62 if (optimize_loop_for_size_p (loop
))
65 gcc_assert (EDGE_COUNT (header
->succs
) > 0);
66 if (single_succ_p (header
))
68 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
)
69 && flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 1)->dest
))
72 /* If this is not the original loop header, we want it to have just
73 one predecessor in order to match the && pattern. */
74 if (header
!= loop
->header
&& !single_pred_p (header
))
77 last
= last_stmt (header
);
78 if (gimple_code (last
) != GIMPLE_COND
)
81 /* Approximately copy the conditions that used to be used in jump.c --
82 at most 20 insns and no calls. */
83 for (bsi
= gsi_start_bb (header
); !gsi_end_p (bsi
); gsi_next (&bsi
))
85 last
= gsi_stmt (bsi
);
87 if (gimple_code (last
) == GIMPLE_LABEL
)
90 if (is_gimple_debug (last
))
93 if (is_gimple_call (last
))
96 *limit
-= estimate_num_insns (last
, &eni_size_weights
);
104 /* Checks whether LOOP is a do-while style loop. */
107 do_while_loop_p (struct loop
*loop
)
109 gimple
*stmt
= last_stmt (loop
->latch
);
111 /* If the latch of the loop is not empty, it is not a do-while loop. */
113 && gimple_code (stmt
) != GIMPLE_LABEL
)
116 /* If the header contains just a condition, it is not a do-while loop. */
117 stmt
= last_and_only_stmt (loop
->header
);
119 && gimple_code (stmt
) == GIMPLE_COND
)
127 /* Common superclass for both header-copying phases. */
128 class ch_base
: public gimple_opt_pass
131 ch_base (pass_data data
, gcc::context
*ctxt
)
132 : gimple_opt_pass (data
, ctxt
)
135 /* Copies headers of all loops in FUN for which process_loop_p is true. */
136 unsigned int copy_headers (function
*fun
);
138 /* Return true to copy headers of LOOP or false to skip. */
139 virtual bool process_loop_p (struct loop
*loop
) = 0;
142 const pass_data pass_data_ch
=
144 GIMPLE_PASS
, /* type */
146 OPTGROUP_LOOP
, /* optinfo_flags */
147 TV_TREE_CH
, /* tv_id */
148 ( PROP_cfg
| PROP_ssa
), /* properties_required */
149 0, /* properties_provided */
150 0, /* properties_destroyed */
151 0, /* todo_flags_start */
152 0, /* todo_flags_finish */
155 class pass_ch
: public ch_base
158 pass_ch (gcc::context
*ctxt
)
159 : ch_base (pass_data_ch
, ctxt
)
162 /* opt_pass methods: */
163 virtual bool gate (function
*) { return flag_tree_ch
!= 0; }
165 /* Initialize and finalize loop structures, copying headers inbetween. */
166 virtual unsigned int execute (function
*);
169 /* ch_base method: */
170 virtual bool process_loop_p (struct loop
*loop
);
173 const pass_data pass_data_ch_vect
=
175 GIMPLE_PASS
, /* type */
176 "ch_vect", /* name */
177 OPTGROUP_LOOP
, /* optinfo_flags */
178 TV_TREE_CH
, /* tv_id */
179 ( PROP_cfg
| PROP_ssa
), /* properties_required */
180 0, /* properties_provided */
181 0, /* properties_destroyed */
182 0, /* todo_flags_start */
183 0, /* todo_flags_finish */
186 /* This is a more aggressive version of the same pass, designed to run just
187 before if-conversion and vectorization, to put more loops into the form
188 required for those phases. */
189 class pass_ch_vect
: public ch_base
192 pass_ch_vect (gcc::context
*ctxt
)
193 : ch_base (pass_data_ch_vect
, ctxt
)
196 /* opt_pass methods: */
197 virtual bool gate (function
*fun
)
199 return flag_tree_ch
!= 0
200 && (flag_tree_loop_vectorize
!= 0 || fun
->has_force_vectorize_loops
);
203 /* Just copy headers, no initialization/finalization of loop structures. */
204 virtual unsigned int execute (function
*);
207 /* ch_base method: */
208 virtual bool process_loop_p (struct loop
*loop
);
209 }; // class pass_ch_vect
211 /* For all loops, copy the condition at the end of the loop body in front
212 of the loop. This is beneficial since it increases efficiency of
213 code motion optimizations. It also saves one jump on entry to the loop. */
216 ch_base::copy_headers (function
*fun
)
221 basic_block
*bbs
, *copied_bbs
;
224 bool changed
= false;
226 if (number_of_loops (fun
) <= 1)
229 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
230 copied_bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
231 bbs_size
= n_basic_blocks_for_fn (fun
);
233 FOR_EACH_LOOP (loop
, 0)
235 /* Copy at most 20 insns. */
238 header
= loop
->header
;
240 /* If the loop is already a do-while style one (either because it was
241 written as such, or because jump threading transformed it into one),
242 we might be in fact peeling the first iteration of the loop. This
243 in general is not a good idea. */
244 if (!process_loop_p (loop
))
247 /* Iterate the header copying up to limit; this takes care of the cases
248 like while (a && b) {...}, where we want to have both of the conditions
249 copied. TODO -- handle while (a || b) - like cases, by not requiring
250 the header to have just a single successor and copying up to
255 while (should_duplicate_loop_header_p (header
, loop
, &limit
))
257 /* Find a successor of header that is inside a loop; i.e. the new
258 header after the condition is copied. */
259 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
))
260 exit
= EDGE_SUCC (header
, 0);
262 exit
= EDGE_SUCC (header
, 1);
263 bbs
[n_bbs
++] = header
;
264 gcc_assert (bbs_size
> n_bbs
);
271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 "Duplicating header of the loop %d up to edge %d->%d.\n",
274 loop
->num
, exit
->src
->index
, exit
->dest
->index
);
276 /* Ensure that the header will have just the latch as a predecessor
278 if (!single_pred_p (exit
->dest
))
279 exit
= single_pred_edge (split_edge (exit
));
281 entry
= loop_preheader_edge (loop
);
283 propagate_threaded_block_debug_into (exit
->dest
, entry
->dest
);
284 if (!gimple_duplicate_sese_region (entry
, exit
, bbs
, n_bbs
, copied_bbs
,
287 fprintf (dump_file
, "Duplication failed.\n");
291 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
292 this copying can introduce a case where we rely on undefined
293 signed overflow to eliminate the preheader condition, because
294 we assume that "j < j + 10" is true. We don't want to warn
295 about that case for -Wstrict-overflow, because in general we
296 don't warn about overflow involving loops. Prevent the
297 warning by setting the no_warning flag in the condition. */
298 if (warn_strict_overflow
> 0)
302 for (i
= 0; i
< n_bbs
; ++i
)
304 gimple_stmt_iterator bsi
;
306 for (bsi
= gsi_start_bb (copied_bbs
[i
]);
310 gimple
*stmt
= gsi_stmt (bsi
);
311 if (gimple_code (stmt
) == GIMPLE_COND
)
312 gimple_set_no_warning (stmt
, true);
313 else if (is_gimple_assign (stmt
))
315 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
316 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
317 gimple_set_no_warning (stmt
, true);
323 /* Ensure that the latch and the preheader is simple (we know that they
324 are not now, since there was the loop exit condition. */
325 split_edge (loop_preheader_edge (loop
));
326 split_edge (loop_latch_edge (loop
));
332 update_ssa (TODO_update_ssa
);
336 return changed
? TODO_cleanup_cfg
: 0;
339 /* Initialize the loop structures we need, and finalize after. */
342 pass_ch::execute (function
*fun
)
344 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
345 | LOOPS_HAVE_SIMPLE_LATCHES
);
347 unsigned int res
= copy_headers (fun
);
349 loop_optimizer_finalize ();
353 /* Assume an earlier phase has already initialized all the loop structures that
354 we need here (and perhaps others too), and that these will be finalized by
358 pass_ch_vect::execute (function
*fun
)
360 return copy_headers (fun
);
363 /* Apply header copying according to a very simple test of do-while shape. */
366 pass_ch::process_loop_p (struct loop
*loop
)
368 return !do_while_loop_p (loop
);
371 /* Apply header-copying to loops where we might enable vectorization. */
374 pass_ch_vect::process_loop_p (struct loop
*loop
)
376 if (!flag_tree_vectorize
&& !loop
->force_vectorize
)
379 if (loop
->dont_vectorize
)
382 if (!do_while_loop_p (loop
))
385 /* The vectorizer won't handle anything with multiple exits, so skip. */
386 edge exit
= single_exit (loop
);
390 /* Copy headers iff there looks to be code in the loop after the exit block,
391 i.e. the exit block has an edge to another block (besides the latch,
392 which should be empty). */
395 FOR_EACH_EDGE (e
, ei
, exit
->src
->succs
)
396 if (!loop_exit_edge_p (loop
, e
)
397 && e
->dest
!= loop
->header
398 && e
->dest
!= loop
->latch
)
407 make_pass_ch_vect (gcc::context
*ctxt
)
409 return new pass_ch_vect (ctxt
);
413 make_pass_ch (gcc::context
*ctxt
)
415 return new pass_ch (ctxt
);