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 "fold-const.h"
30 #include "hard-reg-set.h"
32 #include "dominance.h"
34 #include "basic-block.h"
35 #include "tree-ssa-alias.h"
36 #include "internal-fn.h"
37 #include "gimple-expr.h"
39 #include "gimple-iterator.h"
40 #include "gimple-ssa.h"
42 #include "tree-into-ssa.h"
43 #include "tree-pass.h"
45 #include "tree-inline.h"
47 #include "tree-ssa-scopedtables.h"
48 #include "tree-ssa-threadedge.h"
50 /* Duplicates headers of loops if they are small enough, so that the statements
51 in the loop body are always executed when the loop is entered. This
52 increases effectiveness of code motion optimizations, and reduces the need
53 for loop preconditioning. */
55 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
56 instructions should be duplicated, limit is decreased by the actual
60 should_duplicate_loop_header_p (basic_block header
, struct loop
*loop
,
63 gimple_stmt_iterator bsi
;
66 /* Do not copy one block more than once (we do not really want to do
67 loop peeling here). */
71 /* Loop header copying usually increases size of the code. This used not to
72 be true, since quite often it is possible to verify that the condition is
73 satisfied in the first iteration and therefore to eliminate it. Jump
74 threading handles these cases now. */
75 if (optimize_loop_for_size_p (loop
))
78 gcc_assert (EDGE_COUNT (header
->succs
) > 0);
79 if (single_succ_p (header
))
81 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
)
82 && flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 1)->dest
))
85 /* If this is not the original loop header, we want it to have just
86 one predecessor in order to match the && pattern. */
87 if (header
!= loop
->header
&& !single_pred_p (header
))
90 last
= last_stmt (header
);
91 if (gimple_code (last
) != GIMPLE_COND
)
94 /* Approximately copy the conditions that used to be used in jump.c --
95 at most 20 insns and no calls. */
96 for (bsi
= gsi_start_bb (header
); !gsi_end_p (bsi
); gsi_next (&bsi
))
98 last
= gsi_stmt (bsi
);
100 if (gimple_code (last
) == GIMPLE_LABEL
)
103 if (is_gimple_debug (last
))
106 if (is_gimple_call (last
))
109 *limit
-= estimate_num_insns (last
, &eni_size_weights
);
117 /* Checks whether LOOP is a do-while style loop. */
120 do_while_loop_p (struct loop
*loop
)
122 gimple stmt
= last_stmt (loop
->latch
);
124 /* If the latch of the loop is not empty, it is not a do-while loop. */
126 && gimple_code (stmt
) != GIMPLE_LABEL
)
129 /* If the header contains just a condition, it is not a do-while loop. */
130 stmt
= last_and_only_stmt (loop
->header
);
132 && gimple_code (stmt
) == GIMPLE_COND
)
140 /* Common superclass for both header-copying phases. */
141 class ch_base
: public gimple_opt_pass
144 ch_base (pass_data data
, gcc::context
*ctxt
)
145 : gimple_opt_pass (data
, ctxt
)
148 /* Copies headers of all loops in FUN for which process_loop_p is true. */
149 unsigned int copy_headers (function
*fun
);
151 /* Return true to copy headers of LOOP or false to skip. */
152 virtual bool process_loop_p (struct loop
*loop
) = 0;
155 const pass_data pass_data_ch
=
157 GIMPLE_PASS
, /* type */
159 OPTGROUP_LOOP
, /* optinfo_flags */
160 TV_TREE_CH
, /* tv_id */
161 ( PROP_cfg
| PROP_ssa
), /* properties_required */
162 0, /* properties_provided */
163 0, /* properties_destroyed */
164 0, /* todo_flags_start */
165 0, /* todo_flags_finish */
168 class pass_ch
: public ch_base
171 pass_ch (gcc::context
*ctxt
)
172 : ch_base (pass_data_ch
, ctxt
)
175 /* opt_pass methods: */
176 virtual bool gate (function
*) { return flag_tree_ch
!= 0; }
178 /* Initialize and finalize loop structures, copying headers inbetween. */
179 virtual unsigned int execute (function
*);
182 /* ch_base method: */
183 virtual bool process_loop_p (struct loop
*loop
);
186 const pass_data pass_data_ch_vect
=
188 GIMPLE_PASS
, /* type */
189 "ch_vect", /* name */
190 OPTGROUP_LOOP
, /* optinfo_flags */
191 TV_TREE_CH
, /* tv_id */
192 ( PROP_cfg
| PROP_ssa
), /* properties_required */
193 0, /* properties_provided */
194 0, /* properties_destroyed */
195 0, /* todo_flags_start */
196 0, /* todo_flags_finish */
199 /* This is a more aggressive version of the same pass, designed to run just
200 before if-conversion and vectorization, to put more loops into the form
201 required for those phases. */
202 class pass_ch_vect
: public ch_base
205 pass_ch_vect (gcc::context
*ctxt
)
206 : ch_base (pass_data_ch_vect
, ctxt
)
209 /* opt_pass methods: */
210 virtual bool gate (function
*fun
)
212 return flag_tree_ch
!= 0
213 && (flag_tree_loop_vectorize
!= 0 || fun
->has_force_vectorize_loops
);
216 /* Just copy headers, no initialization/finalization of loop structures. */
217 virtual unsigned int execute (function
*);
220 /* ch_base method: */
221 virtual bool process_loop_p (struct loop
*loop
);
222 }; // class pass_ch_vect
224 /* For all loops, copy the condition at the end of the loop body in front
225 of the loop. This is beneficial since it increases efficiency of
226 code motion optimizations. It also saves one jump on entry to the loop. */
229 ch_base::copy_headers (function
*fun
)
234 basic_block
*bbs
, *copied_bbs
;
237 bool changed
= false;
239 if (number_of_loops (fun
) <= 1)
242 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
243 copied_bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
244 bbs_size
= n_basic_blocks_for_fn (fun
);
246 FOR_EACH_LOOP (loop
, 0)
248 /* Copy at most 20 insns. */
251 header
= loop
->header
;
253 /* If the loop is already a do-while style one (either because it was
254 written as such, or because jump threading transformed it into one),
255 we might be in fact peeling the first iteration of the loop. This
256 in general is not a good idea. */
257 if (!process_loop_p (loop
))
260 /* Iterate the header copying up to limit; this takes care of the cases
261 like while (a && b) {...}, where we want to have both of the conditions
262 copied. TODO -- handle while (a || b) - like cases, by not requiring
263 the header to have just a single successor and copying up to
268 while (should_duplicate_loop_header_p (header
, loop
, &limit
))
270 /* Find a successor of header that is inside a loop; i.e. the new
271 header after the condition is copied. */
272 if (flow_bb_inside_loop_p (loop
, EDGE_SUCC (header
, 0)->dest
))
273 exit
= EDGE_SUCC (header
, 0);
275 exit
= EDGE_SUCC (header
, 1);
276 bbs
[n_bbs
++] = header
;
277 gcc_assert (bbs_size
> n_bbs
);
284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
286 "Duplicating header of the loop %d up to edge %d->%d.\n",
287 loop
->num
, exit
->src
->index
, exit
->dest
->index
);
289 /* Ensure that the header will have just the latch as a predecessor
291 if (!single_pred_p (exit
->dest
))
292 exit
= single_pred_edge (split_edge (exit
));
294 entry
= loop_preheader_edge (loop
);
296 propagate_threaded_block_debug_into (exit
->dest
, entry
->dest
);
297 if (!gimple_duplicate_sese_region (entry
, exit
, bbs
, n_bbs
, copied_bbs
,
300 fprintf (dump_file
, "Duplication failed.\n");
304 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
305 this copying can introduce a case where we rely on undefined
306 signed overflow to eliminate the preheader condition, because
307 we assume that "j < j + 10" is true. We don't want to warn
308 about that case for -Wstrict-overflow, because in general we
309 don't warn about overflow involving loops. Prevent the
310 warning by setting the no_warning flag in the condition. */
311 if (warn_strict_overflow
> 0)
315 for (i
= 0; i
< n_bbs
; ++i
)
317 gimple_stmt_iterator bsi
;
319 for (bsi
= gsi_start_bb (copied_bbs
[i
]);
323 gimple stmt
= gsi_stmt (bsi
);
324 if (gimple_code (stmt
) == GIMPLE_COND
)
325 gimple_set_no_warning (stmt
, true);
326 else if (is_gimple_assign (stmt
))
328 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
329 if (TREE_CODE_CLASS (rhs_code
) == tcc_comparison
)
330 gimple_set_no_warning (stmt
, true);
336 /* Ensure that the latch and the preheader is simple (we know that they
337 are not now, since there was the loop exit condition. */
338 split_edge (loop_preheader_edge (loop
));
339 split_edge (loop_latch_edge (loop
));
345 update_ssa (TODO_update_ssa
);
349 return changed
? TODO_cleanup_cfg
: 0;
352 /* Initialize the loop structures we need, and finalize after. */
355 pass_ch::execute (function
*fun
)
357 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
358 | LOOPS_HAVE_SIMPLE_LATCHES
);
360 unsigned int res
= copy_headers (fun
);
362 loop_optimizer_finalize ();
366 /* Assume an earlier phase has already initialized all the loop structures that
367 we need here (and perhaps others too), and that these will be finalized by
371 pass_ch_vect::execute (function
*fun
)
373 return copy_headers (fun
);
376 /* Apply header copying according to a very simple test of do-while shape. */
379 pass_ch::process_loop_p (struct loop
*loop
)
381 return !do_while_loop_p (loop
);
384 /* Apply header-copying to loops where we might enable vectorization. */
387 pass_ch_vect::process_loop_p (struct loop
*loop
)
389 if (!flag_tree_vectorize
&& !loop
->force_vectorize
)
392 if (loop
->dont_vectorize
)
395 if (!do_while_loop_p (loop
))
398 /* The vectorizer won't handle anything with multiple exits, so skip. */
399 edge exit
= single_exit (loop
);
403 /* Copy headers iff there looks to be code in the loop after the exit block,
404 i.e. the exit block has an edge to another block (besides the latch,
405 which should be empty). */
408 FOR_EACH_EDGE (e
, ei
, exit
->src
->succs
)
409 if (!loop_exit_edge_p (loop
, e
)
410 && e
->dest
!= loop
->header
411 && e
->dest
!= loop
->latch
)
420 make_pass_ch_vect (gcc::context
*ctxt
)
422 return new pass_ch_vect (ctxt
);
426 make_pass_ch (gcc::context
*ctxt
)
428 return new pass_ch (ctxt
);