1 /* Loop header copying on trees.
2 Copyright (C) 2004-2018 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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"
37
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. */
42
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. */
46
47 static bool
should_duplicate_loop_header_p(basic_block header,struct loop * loop,int * limit)48 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
49 int *limit)
50 {
51 gimple_stmt_iterator bsi;
52 gimple *last;
53
54 gcc_assert (!header->aux);
55
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)
62 {
63 if (dump_file && (dump_flags & TDF_DETAILS))
64 fprintf (dump_file,
65 " Not duplicating bb %i: optimizing for size.\n",
66 header->index);
67 return false;
68 }
69
70 gcc_assert (EDGE_COUNT (header->succs) > 0);
71 if (single_succ_p (header))
72 {
73 if (dump_file && (dump_flags & TDF_DETAILS))
74 fprintf (dump_file,
75 " Not duplicating bb %i: it is single succ.\n",
76 header->index);
77 return false;
78 }
79
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))
82 {
83 if (dump_file && (dump_flags & TDF_DETAILS))
84 fprintf (dump_file,
85 " Not duplicating bb %i: both sucessors are in loop.\n",
86 loop->num);
87 return false;
88 }
89
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))
93 {
94 if (dump_file && (dump_flags & TDF_DETAILS))
95 fprintf (dump_file,
96 " Not duplicating bb %i: it has mutiple predecestors.\n",
97 header->index);
98 return false;
99 }
100
101 last = last_stmt (header);
102 if (gimple_code (last) != GIMPLE_COND)
103 {
104 if (dump_file && (dump_flags & TDF_DETAILS))
105 fprintf (dump_file,
106 " Not duplicating bb %i: it does not end by conditional.\n",
107 header->index);
108 return false;
109 }
110
111 /* Count number of instructions and punt on calls. */
112 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
113 {
114 last = gsi_stmt (bsi);
115
116 if (gimple_code (last) == GIMPLE_LABEL)
117 continue;
118
119 if (is_gimple_debug (last))
120 continue;
121
122 if (gimple_code (last) == GIMPLE_CALL
123 && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
124 /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
125 at current loop's header. Don't copy in this case. */
126 || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
127 {
128 if (dump_file && (dump_flags & TDF_DETAILS))
129 fprintf (dump_file,
130 " Not duplicating bb %i: it contains call.\n",
131 header->index);
132 return false;
133 }
134
135 *limit -= estimate_num_insns (last, &eni_size_weights);
136 if (*limit < 0)
137 {
138 if (dump_file && (dump_flags & TDF_DETAILS))
139 fprintf (dump_file,
140 " Not duplicating bb %i contains too many insns.\n",
141 header->index);
142 return false;
143 }
144 }
145 if (dump_file && (dump_flags & TDF_DETAILS))
146 fprintf (dump_file, " Will duplicate bb %i\n", header->index);
147 return true;
148 }
149
150 /* Checks whether LOOP is a do-while style loop. */
151
152 static bool
do_while_loop_p(struct loop * loop)153 do_while_loop_p (struct loop *loop)
154 {
155 gimple *stmt = last_stmt (loop->latch);
156
157 /* If the latch of the loop is not empty, it is not a do-while loop. */
158 if (stmt
159 && gimple_code (stmt) != GIMPLE_LABEL)
160 {
161 if (dump_file && (dump_flags & TDF_DETAILS))
162 fprintf (dump_file,
163 "Loop %i is not do-while loop: latch is not empty.\n",
164 loop->num);
165 return false;
166 }
167
168 /* If the header contains just a condition, it is not a do-while loop. */
169 stmt = last_and_only_stmt (loop->header);
170 if (stmt
171 && gimple_code (stmt) == GIMPLE_COND)
172 {
173 if (dump_file && (dump_flags & TDF_DETAILS))
174 fprintf (dump_file,
175 "Loop %i is not do-while loop: "
176 "header contains just condition.\n", loop->num);
177 return false;
178 }
179 if (dump_file && (dump_flags & TDF_DETAILS))
180 fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
181
182 return true;
183 }
184
185 namespace {
186
187 /* Common superclass for both header-copying phases. */
188 class ch_base : public gimple_opt_pass
189 {
190 protected:
ch_base(pass_data data,gcc::context * ctxt)191 ch_base (pass_data data, gcc::context *ctxt)
192 : gimple_opt_pass (data, ctxt)
193 {}
194
195 /* Copies headers of all loops in FUN for which process_loop_p is true. */
196 unsigned int copy_headers (function *fun);
197
198 /* Return true to copy headers of LOOP or false to skip. */
199 virtual bool process_loop_p (struct loop *loop) = 0;
200 };
201
202 const pass_data pass_data_ch =
203 {
204 GIMPLE_PASS, /* type */
205 "ch", /* name */
206 OPTGROUP_LOOP, /* optinfo_flags */
207 TV_TREE_CH, /* tv_id */
208 ( PROP_cfg | PROP_ssa ), /* properties_required */
209 0, /* properties_provided */
210 0, /* properties_destroyed */
211 0, /* todo_flags_start */
212 0, /* todo_flags_finish */
213 };
214
215 class pass_ch : public ch_base
216 {
217 public:
pass_ch(gcc::context * ctxt)218 pass_ch (gcc::context *ctxt)
219 : ch_base (pass_data_ch, ctxt)
220 {}
221
222 /* opt_pass methods: */
gate(function *)223 virtual bool gate (function *) { return flag_tree_ch != 0; }
224
225 /* Initialize and finalize loop structures, copying headers inbetween. */
226 virtual unsigned int execute (function *);
227
clone()228 opt_pass * clone () { return new pass_ch (m_ctxt); }
229
230 protected:
231 /* ch_base method: */
232 virtual bool process_loop_p (struct loop *loop);
233 }; // class pass_ch
234
235 const pass_data pass_data_ch_vect =
236 {
237 GIMPLE_PASS, /* type */
238 "ch_vect", /* name */
239 OPTGROUP_LOOP, /* optinfo_flags */
240 TV_TREE_CH, /* tv_id */
241 ( PROP_cfg | PROP_ssa ), /* properties_required */
242 0, /* properties_provided */
243 0, /* properties_destroyed */
244 0, /* todo_flags_start */
245 0, /* todo_flags_finish */
246 };
247
248 /* This is a more aggressive version of the same pass, designed to run just
249 before if-conversion and vectorization, to put more loops into the form
250 required for those phases. */
251 class pass_ch_vect : public ch_base
252 {
253 public:
pass_ch_vect(gcc::context * ctxt)254 pass_ch_vect (gcc::context *ctxt)
255 : ch_base (pass_data_ch_vect, ctxt)
256 {}
257
258 /* opt_pass methods: */
gate(function * fun)259 virtual bool gate (function *fun)
260 {
261 return flag_tree_ch != 0
262 && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
263 }
264
265 /* Just copy headers, no initialization/finalization of loop structures. */
266 virtual unsigned int execute (function *);
267
268 protected:
269 /* ch_base method: */
270 virtual bool process_loop_p (struct loop *loop);
271 }; // class pass_ch_vect
272
273 /* For all loops, copy the condition at the end of the loop body in front
274 of the loop. This is beneficial since it increases efficiency of
275 code motion optimizations. It also saves one jump on entry to the loop. */
276
277 unsigned int
copy_headers(function * fun)278 ch_base::copy_headers (function *fun)
279 {
280 struct loop *loop;
281 basic_block header;
282 edge exit, entry;
283 basic_block *bbs, *copied_bbs;
284 unsigned n_bbs;
285 unsigned bbs_size;
286 bool changed = false;
287
288 if (number_of_loops (fun) <= 1)
289 return 0;
290
291 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
292 copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
293 bbs_size = n_basic_blocks_for_fn (fun);
294
295 FOR_EACH_LOOP (loop, 0)
296 {
297 int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS);
298 int remaining_limit = initial_limit;
299 if (dump_file && (dump_flags & TDF_DETAILS))
300 fprintf (dump_file,
301 "Analyzing loop %i\n", loop->num);
302
303 header = loop->header;
304
305 /* If the loop is already a do-while style one (either because it was
306 written as such, or because jump threading transformed it into one),
307 we might be in fact peeling the first iteration of the loop. This
308 in general is not a good idea. */
309 if (!process_loop_p (loop))
310 continue;
311
312 /* Iterate the header copying up to limit; this takes care of the cases
313 like while (a && b) {...}, where we want to have both of the conditions
314 copied. TODO -- handle while (a || b) - like cases, by not requiring
315 the header to have just a single successor and copying up to
316 postdominator. */
317
318 exit = NULL;
319 n_bbs = 0;
320 while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
321 {
322 /* Find a successor of header that is inside a loop; i.e. the new
323 header after the condition is copied. */
324 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
325 exit = EDGE_SUCC (header, 0);
326 else
327 exit = EDGE_SUCC (header, 1);
328 bbs[n_bbs++] = header;
329 gcc_assert (bbs_size > n_bbs);
330 header = exit->dest;
331 }
332
333 if (!exit)
334 continue;
335
336 if (dump_file && (dump_flags & TDF_DETAILS))
337 fprintf (dump_file,
338 "Duplicating header of the loop %d up to edge %d->%d,"
339 " %i insns.\n",
340 loop->num, exit->src->index, exit->dest->index,
341 initial_limit - remaining_limit);
342
343 /* Ensure that the header will have just the latch as a predecessor
344 inside the loop. */
345 if (!single_pred_p (exit->dest))
346 exit = single_pred_edge (split_edge (exit));
347
348 entry = loop_preheader_edge (loop);
349
350 propagate_threaded_block_debug_into (exit->dest, entry->dest);
351 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
352 true))
353 {
354 fprintf (dump_file, "Duplication failed.\n");
355 continue;
356 }
357
358 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
359 this copying can introduce a case where we rely on undefined
360 signed overflow to eliminate the preheader condition, because
361 we assume that "j < j + 10" is true. We don't want to warn
362 about that case for -Wstrict-overflow, because in general we
363 don't warn about overflow involving loops. Prevent the
364 warning by setting the no_warning flag in the condition. */
365 if (warn_strict_overflow > 0)
366 {
367 unsigned int i;
368
369 for (i = 0; i < n_bbs; ++i)
370 {
371 gimple_stmt_iterator bsi;
372
373 for (bsi = gsi_start_bb (copied_bbs[i]);
374 !gsi_end_p (bsi);
375 gsi_next (&bsi))
376 {
377 gimple *stmt = gsi_stmt (bsi);
378 if (gimple_code (stmt) == GIMPLE_COND)
379 {
380 tree lhs = gimple_cond_lhs (stmt);
381 if (gimple_cond_code (stmt) != EQ_EXPR
382 && gimple_cond_code (stmt) != NE_EXPR
383 && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
384 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)))
385 gimple_set_no_warning (stmt, true);
386 }
387 else if (is_gimple_assign (stmt))
388 {
389 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
390 tree rhs1 = gimple_assign_rhs1 (stmt);
391 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison
392 && rhs_code != EQ_EXPR
393 && rhs_code != NE_EXPR
394 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
395 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1)))
396 gimple_set_no_warning (stmt, true);
397 }
398 }
399 }
400 }
401
402 /* Ensure that the latch and the preheader is simple (we know that they
403 are not now, since there was the loop exit condition. */
404 split_edge (loop_preheader_edge (loop));
405 split_edge (loop_latch_edge (loop));
406
407 changed = true;
408 }
409
410 if (changed)
411 update_ssa (TODO_update_ssa);
412 free (bbs);
413 free (copied_bbs);
414
415 return changed ? TODO_cleanup_cfg : 0;
416 }
417
418 /* Initialize the loop structures we need, and finalize after. */
419
420 unsigned int
execute(function * fun)421 pass_ch::execute (function *fun)
422 {
423 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
424 | LOOPS_HAVE_SIMPLE_LATCHES);
425
426 unsigned int res = copy_headers (fun);
427
428 loop_optimizer_finalize ();
429 return res;
430 }
431
432 /* Assume an earlier phase has already initialized all the loop structures that
433 we need here (and perhaps others too), and that these will be finalized by
434 a later phase. */
435
436 unsigned int
execute(function * fun)437 pass_ch_vect::execute (function *fun)
438 {
439 return copy_headers (fun);
440 }
441
442 /* Apply header copying according to a very simple test of do-while shape. */
443
444 bool
process_loop_p(struct loop * loop)445 pass_ch::process_loop_p (struct loop *loop)
446 {
447 return !do_while_loop_p (loop);
448 }
449
450 /* Apply header-copying to loops where we might enable vectorization. */
451
452 bool
process_loop_p(struct loop * loop)453 pass_ch_vect::process_loop_p (struct loop *loop)
454 {
455 if (!flag_tree_loop_vectorize && !loop->force_vectorize)
456 return false;
457
458 if (loop->dont_vectorize)
459 return false;
460
461 if (!do_while_loop_p (loop))
462 return true;
463
464 /* The vectorizer won't handle anything with multiple exits, so skip. */
465 edge exit = single_exit (loop);
466 if (!exit)
467 return false;
468
469 /* Copy headers iff there looks to be code in the loop after the exit block,
470 i.e. the exit block has an edge to another block (besides the latch,
471 which should be empty). */
472 edge_iterator ei;
473 edge e;
474 FOR_EACH_EDGE (e, ei, exit->src->succs)
475 if (!loop_exit_edge_p (loop, e)
476 && e->dest != loop->header
477 && e->dest != loop->latch)
478 return true;
479
480 return false;
481 }
482
483 } // anon namespace
484
485 gimple_opt_pass *
make_pass_ch_vect(gcc::context * ctxt)486 make_pass_ch_vect (gcc::context *ctxt)
487 {
488 return new pass_ch_vect (ctxt);
489 }
490
491 gimple_opt_pass *
make_pass_ch(gcc::context * ctxt)492 make_pass_ch (gcc::context *ctxt)
493 {
494 return new pass_ch (ctxt);
495 }
496