Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop-ch.c
blob86be34a1ac7159ae234bf9f6ffcbc87158983c7c
1 /* Loop header copying on trees.
2 Copyright (C) 2004-2017 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
9 later version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "cfghooks.h"
27 #include "tree-pass.h"
28 #include "gimple-ssa.h"
29 #include "gimple-iterator.h"
30 #include "tree-cfg.h"
31 #include "tree-into-ssa.h"
32 #include "cfgloop.h"
33 #include "tree-inline.h"
34 #include "tree-ssa-scopedtables.h"
35 #include "tree-ssa-threadedge.h"
36 #include "params.h"
38 /* Duplicates headers of loops if they are small enough, so that the statements
39 in the loop body are always executed when the loop is entered. This
40 increases effectiveness of code motion optimizations, and reduces the need
41 for loop preconditioning. */
43 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
44 instructions should be duplicated, limit is decreased by the actual
45 amount. */
47 static bool
48 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
49 int *limit)
51 gimple_stmt_iterator bsi;
52 gimple *last;
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))
62 if (dump_file && (dump_flags & TDF_DETAILS))
63 fprintf (dump_file,
64 " Not duplicating bb %i: optimizing for size.\n",
65 header->index);
66 return false;
69 gcc_assert (EDGE_COUNT (header->succs) > 0);
70 if (single_succ_p (header))
72 if (dump_file && (dump_flags & TDF_DETAILS))
73 fprintf (dump_file,
74 " Not duplicating bb %i: it is single succ.\n",
75 header->index);
76 return false;
79 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
80 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
82 if (dump_file && (dump_flags & TDF_DETAILS))
83 fprintf (dump_file,
84 " Not duplicating bb %i: both sucessors are in loop.\n",
85 loop->num);
86 return false;
89 /* If this is not the original loop header, we want it to have just
90 one predecessor in order to match the && pattern. */
91 if (header != loop->header && !single_pred_p (header))
93 if (dump_file && (dump_flags & TDF_DETAILS))
94 fprintf (dump_file,
95 " Not duplicating bb %i: it has mutiple predecestors.\n",
96 header->index);
97 return false;
100 last = last_stmt (header);
101 if (gimple_code (last) != GIMPLE_COND)
103 if (dump_file && (dump_flags & TDF_DETAILS))
104 fprintf (dump_file,
105 " Not duplicating bb %i: it does not end by conditional.\n",
106 header->index);
107 return false;
110 /* Count number of instructions and punt on calls. */
111 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
113 last = gsi_stmt (bsi);
115 if (gimple_code (last) == GIMPLE_LABEL)
116 continue;
118 if (is_gimple_debug (last))
119 continue;
121 if (gimple_code (last) == GIMPLE_CALL
122 && !gimple_inexpensive_call_p (as_a <gcall *> (last)))
124 if (dump_file && (dump_flags & TDF_DETAILS))
125 fprintf (dump_file,
126 " Not duplicating bb %i: it contains call.\n",
127 header->index);
128 return false;
131 *limit -= estimate_num_insns (last, &eni_size_weights);
132 if (*limit < 0)
134 if (dump_file && (dump_flags & TDF_DETAILS))
135 fprintf (dump_file,
136 " Not duplicating bb %i contains too many insns.\n",
137 header->index);
138 return false;
141 if (dump_file && (dump_flags & TDF_DETAILS))
142 fprintf (dump_file, " Will duplicate bb %i\n", header->index);
143 return true;
146 /* Checks whether LOOP is a do-while style loop. */
148 static bool
149 do_while_loop_p (struct loop *loop)
151 gimple *stmt = last_stmt (loop->latch);
153 /* If the latch of the loop is not empty, it is not a do-while loop. */
154 if (stmt
155 && gimple_code (stmt) != GIMPLE_LABEL)
157 if (dump_file && (dump_flags & TDF_DETAILS))
158 fprintf (dump_file,
159 "Loop %i is not do-while loop: latch is not empty.\n",
160 loop->num);
161 return false;
164 /* If the header contains just a condition, it is not a do-while loop. */
165 stmt = last_and_only_stmt (loop->header);
166 if (stmt
167 && gimple_code (stmt) == GIMPLE_COND)
169 if (dump_file && (dump_flags & TDF_DETAILS))
170 fprintf (dump_file,
171 "Loop %i is not do-while loop: "
172 "header contains just condition.\n", loop->num);
173 return false;
175 if (dump_file && (dump_flags & TDF_DETAILS))
176 fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
178 return true;
181 namespace {
183 /* Common superclass for both header-copying phases. */
184 class ch_base : public gimple_opt_pass
186 protected:
187 ch_base (pass_data data, gcc::context *ctxt)
188 : gimple_opt_pass (data, ctxt)
191 /* Copies headers of all loops in FUN for which process_loop_p is true. */
192 unsigned int copy_headers (function *fun);
194 /* Return true to copy headers of LOOP or false to skip. */
195 virtual bool process_loop_p (struct loop *loop) = 0;
198 const pass_data pass_data_ch =
200 GIMPLE_PASS, /* type */
201 "ch", /* name */
202 OPTGROUP_LOOP, /* optinfo_flags */
203 TV_TREE_CH, /* tv_id */
204 ( PROP_cfg | PROP_ssa ), /* properties_required */
205 0, /* properties_provided */
206 0, /* properties_destroyed */
207 0, /* todo_flags_start */
208 0, /* todo_flags_finish */
211 class pass_ch : public ch_base
213 public:
214 pass_ch (gcc::context *ctxt)
215 : ch_base (pass_data_ch, ctxt)
218 /* opt_pass methods: */
219 virtual bool gate (function *) { return flag_tree_ch != 0; }
221 /* Initialize and finalize loop structures, copying headers inbetween. */
222 virtual unsigned int execute (function *);
224 opt_pass * clone () { return new pass_ch (m_ctxt); }
226 protected:
227 /* ch_base method: */
228 virtual bool process_loop_p (struct loop *loop);
229 }; // class pass_ch
231 const pass_data pass_data_ch_vect =
233 GIMPLE_PASS, /* type */
234 "ch_vect", /* name */
235 OPTGROUP_LOOP, /* optinfo_flags */
236 TV_TREE_CH, /* tv_id */
237 ( PROP_cfg | PROP_ssa ), /* properties_required */
238 0, /* properties_provided */
239 0, /* properties_destroyed */
240 0, /* todo_flags_start */
241 0, /* todo_flags_finish */
244 /* This is a more aggressive version of the same pass, designed to run just
245 before if-conversion and vectorization, to put more loops into the form
246 required for those phases. */
247 class pass_ch_vect : public ch_base
249 public:
250 pass_ch_vect (gcc::context *ctxt)
251 : ch_base (pass_data_ch_vect, ctxt)
254 /* opt_pass methods: */
255 virtual bool gate (function *fun)
257 return flag_tree_ch != 0
258 && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
261 /* Just copy headers, no initialization/finalization of loop structures. */
262 virtual unsigned int execute (function *);
264 protected:
265 /* ch_base method: */
266 virtual bool process_loop_p (struct loop *loop);
267 }; // class pass_ch_vect
269 /* For all loops, copy the condition at the end of the loop body in front
270 of the loop. This is beneficial since it increases efficiency of
271 code motion optimizations. It also saves one jump on entry to the loop. */
273 unsigned int
274 ch_base::copy_headers (function *fun)
276 struct loop *loop;
277 basic_block header;
278 edge exit, entry;
279 basic_block *bbs, *copied_bbs;
280 unsigned n_bbs;
281 unsigned bbs_size;
282 bool changed = false;
284 if (number_of_loops (fun) <= 1)
285 return 0;
287 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
288 copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
289 bbs_size = n_basic_blocks_for_fn (fun);
291 FOR_EACH_LOOP (loop, 0)
293 int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS);
294 int remaining_limit = initial_limit;
295 if (dump_file && (dump_flags & TDF_DETAILS))
296 fprintf (dump_file,
297 "Analyzing loop %i\n", loop->num);
299 header = loop->header;
301 /* If the loop is already a do-while style one (either because it was
302 written as such, or because jump threading transformed it into one),
303 we might be in fact peeling the first iteration of the loop. This
304 in general is not a good idea. */
305 if (!process_loop_p (loop))
306 continue;
308 /* Iterate the header copying up to limit; this takes care of the cases
309 like while (a && b) {...}, where we want to have both of the conditions
310 copied. TODO -- handle while (a || b) - like cases, by not requiring
311 the header to have just a single successor and copying up to
312 postdominator. */
314 exit = NULL;
315 n_bbs = 0;
316 while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
318 /* Find a successor of header that is inside a loop; i.e. the new
319 header after the condition is copied. */
320 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
321 exit = EDGE_SUCC (header, 0);
322 else
323 exit = EDGE_SUCC (header, 1);
324 bbs[n_bbs++] = header;
325 gcc_assert (bbs_size > n_bbs);
326 header = exit->dest;
329 if (!exit)
330 continue;
332 if (dump_file && (dump_flags & TDF_DETAILS))
333 fprintf (dump_file,
334 "Duplicating header of the loop %d up to edge %d->%d,"
335 " %i insns.\n",
336 loop->num, exit->src->index, exit->dest->index,
337 initial_limit - remaining_limit);
339 /* Ensure that the header will have just the latch as a predecessor
340 inside the loop. */
341 if (!single_pred_p (exit->dest))
342 exit = single_pred_edge (split_edge (exit));
344 entry = loop_preheader_edge (loop);
346 propagate_threaded_block_debug_into (exit->dest, entry->dest);
347 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
348 true))
350 fprintf (dump_file, "Duplication failed.\n");
351 continue;
354 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
355 this copying can introduce a case where we rely on undefined
356 signed overflow to eliminate the preheader condition, because
357 we assume that "j < j + 10" is true. We don't want to warn
358 about that case for -Wstrict-overflow, because in general we
359 don't warn about overflow involving loops. Prevent the
360 warning by setting the no_warning flag in the condition. */
361 if (warn_strict_overflow > 0)
363 unsigned int i;
365 for (i = 0; i < n_bbs; ++i)
367 gimple_stmt_iterator bsi;
369 for (bsi = gsi_start_bb (copied_bbs[i]);
370 !gsi_end_p (bsi);
371 gsi_next (&bsi))
373 gimple *stmt = gsi_stmt (bsi);
374 if (gimple_code (stmt) == GIMPLE_COND)
375 gimple_set_no_warning (stmt, true);
376 else if (is_gimple_assign (stmt))
378 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
379 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
380 gimple_set_no_warning (stmt, true);
386 /* Ensure that the latch and the preheader is simple (we know that they
387 are not now, since there was the loop exit condition. */
388 split_edge (loop_preheader_edge (loop));
389 split_edge (loop_latch_edge (loop));
391 changed = true;
394 if (changed)
395 update_ssa (TODO_update_ssa);
396 free (bbs);
397 free (copied_bbs);
399 return changed ? TODO_cleanup_cfg : 0;
402 /* Initialize the loop structures we need, and finalize after. */
404 unsigned int
405 pass_ch::execute (function *fun)
407 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
408 | LOOPS_HAVE_SIMPLE_LATCHES);
410 unsigned int res = copy_headers (fun);
412 loop_optimizer_finalize ();
413 return res;
416 /* Assume an earlier phase has already initialized all the loop structures that
417 we need here (and perhaps others too), and that these will be finalized by
418 a later phase. */
420 unsigned int
421 pass_ch_vect::execute (function *fun)
423 return copy_headers (fun);
426 /* Apply header copying according to a very simple test of do-while shape. */
428 bool
429 pass_ch::process_loop_p (struct loop *loop)
431 return !do_while_loop_p (loop);
434 /* Apply header-copying to loops where we might enable vectorization. */
436 bool
437 pass_ch_vect::process_loop_p (struct loop *loop)
439 if (!flag_tree_vectorize && !loop->force_vectorize)
440 return false;
442 if (loop->dont_vectorize)
443 return false;
445 if (!do_while_loop_p (loop))
446 return true;
448 /* The vectorizer won't handle anything with multiple exits, so skip. */
449 edge exit = single_exit (loop);
450 if (!exit)
451 return false;
453 /* Copy headers iff there looks to be code in the loop after the exit block,
454 i.e. the exit block has an edge to another block (besides the latch,
455 which should be empty). */
456 edge_iterator ei;
457 edge e;
458 FOR_EACH_EDGE (e, ei, exit->src->succs)
459 if (!loop_exit_edge_p (loop, e)
460 && e->dest != loop->header
461 && e->dest != loop->latch)
462 return true;
464 return false;
467 } // anon namespace
469 gimple_opt_pass *
470 make_pass_ch_vect (gcc::context *ctxt)
472 return new pass_ch_vect (ctxt);
475 gimple_opt_pass *
476 make_pass_ch (gcc::context *ctxt)
478 return new pass_ch (ctxt);