]>
Commit | Line | Data |
---|---|---|
f3d9a16c | 1 | /* Loop header copying on trees. |
d353bf18 | 2 | Copyright (C) 2004-2015 Free Software Foundation, Inc. |
48e1416a | 3 | |
f3d9a16c | 4 | This file is part of GCC. |
48e1416a | 5 | |
f3d9a16c | 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 | |
8c4c00c1 | 8 | Free Software Foundation; either version 3, or (at your option) any |
f3d9a16c | 9 | later version. |
48e1416a | 10 | |
f3d9a16c | 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. | |
48e1416a | 15 | |
f3d9a16c | 16 | You should have received a copy of the GNU General Public License |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
f3d9a16c | 19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
9ef16211 | 23 | #include "backend.h" |
d040a5b0 | 24 | #include "cfghooks.h" |
f3d9a16c | 25 | #include "tree.h" |
9ef16211 | 26 | #include "gimple.h" |
27 | #include "hard-reg-set.h" | |
28 | #include "alias.h" | |
b20a8bb4 | 29 | #include "fold-const.h" |
f3d9a16c | 30 | #include "tm_p.h" |
bc61cadb | 31 | #include "internal-fn.h" |
dcf1a1ec | 32 | #include "gimple-iterator.h" |
073c1fd5 | 33 | #include "gimple-ssa.h" |
34 | #include "tree-cfg.h" | |
35 | #include "tree-into-ssa.h" | |
f3d9a16c | 36 | #include "tree-pass.h" |
f3d9a16c | 37 | #include "cfgloop.h" |
38 | #include "tree-inline.h" | |
39 | #include "flags.h" | |
545372c5 | 40 | #include "tree-ssa-scopedtables.h" |
424a4a92 | 41 | #include "tree-ssa-threadedge.h" |
f3d9a16c | 42 | |
43 | /* Duplicates headers of loops if they are small enough, so that the statements | |
44 | in the loop body are always executed when the loop is entered. This | |
c26a6416 | 45 | increases effectiveness of code motion optimizations, and reduces the need |
f3d9a16c | 46 | for loop preconditioning. */ |
47 | ||
48 | /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT | |
49 | instructions should be duplicated, limit is decreased by the actual | |
50 | amount. */ | |
51 | ||
52 | static bool | |
53 | should_duplicate_loop_header_p (basic_block header, struct loop *loop, | |
54 | int *limit) | |
55 | { | |
75a70cf9 | 56 | gimple_stmt_iterator bsi; |
57 | gimple last; | |
f3d9a16c | 58 | |
59 | /* Do not copy one block more than once (we do not really want to do | |
60 | loop peeling here). */ | |
61 | if (header->aux) | |
62 | return false; | |
63 | ||
94ba1cf1 | 64 | /* Loop header copying usually increases size of the code. This used not to |
65 | be true, since quite often it is possible to verify that the condition is | |
66 | satisfied in the first iteration and therefore to eliminate it. Jump | |
67 | threading handles these cases now. */ | |
68 | if (optimize_loop_for_size_p (loop)) | |
69 | return false; | |
70 | ||
cd665a06 | 71 | gcc_assert (EDGE_COUNT (header->succs) > 0); |
ea091dfd | 72 | if (single_succ_p (header)) |
f3d9a16c | 73 | return false; |
cd665a06 | 74 | if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest) |
75 | && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest)) | |
f3d9a16c | 76 | return false; |
77 | ||
78 | /* If this is not the original loop header, we want it to have just | |
79 | one predecessor in order to match the && pattern. */ | |
ea091dfd | 80 | if (header != loop->header && !single_pred_p (header)) |
f3d9a16c | 81 | return false; |
82 | ||
83 | last = last_stmt (header); | |
75a70cf9 | 84 | if (gimple_code (last) != GIMPLE_COND) |
f3d9a16c | 85 | return false; |
86 | ||
87 | /* Approximately copy the conditions that used to be used in jump.c -- | |
88 | at most 20 insns and no calls. */ | |
75a70cf9 | 89 | for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi)) |
f3d9a16c | 90 | { |
75a70cf9 | 91 | last = gsi_stmt (bsi); |
f3d9a16c | 92 | |
75a70cf9 | 93 | if (gimple_code (last) == GIMPLE_LABEL) |
f3d9a16c | 94 | continue; |
95 | ||
9845d120 | 96 | if (is_gimple_debug (last)) |
97 | continue; | |
98 | ||
75a70cf9 | 99 | if (is_gimple_call (last)) |
f3d9a16c | 100 | return false; |
101 | ||
bc8bb825 | 102 | *limit -= estimate_num_insns (last, &eni_size_weights); |
f3d9a16c | 103 | if (*limit < 0) |
104 | return false; | |
105 | } | |
106 | ||
107 | return true; | |
108 | } | |
109 | ||
f3d9a16c | 110 | /* Checks whether LOOP is a do-while style loop. */ |
111 | ||
f86b328b | 112 | static bool |
f3d9a16c | 113 | do_while_loop_p (struct loop *loop) |
114 | { | |
75a70cf9 | 115 | gimple stmt = last_stmt (loop->latch); |
f3d9a16c | 116 | |
117 | /* If the latch of the loop is not empty, it is not a do-while loop. */ | |
118 | if (stmt | |
75a70cf9 | 119 | && gimple_code (stmt) != GIMPLE_LABEL) |
f3d9a16c | 120 | return false; |
121 | ||
122 | /* If the header contains just a condition, it is not a do-while loop. */ | |
123 | stmt = last_and_only_stmt (loop->header); | |
124 | if (stmt | |
75a70cf9 | 125 | && gimple_code (stmt) == GIMPLE_COND) |
f3d9a16c | 126 | return false; |
127 | ||
128 | return true; | |
129 | } | |
130 | ||
65b0537f | 131 | namespace { |
132 | ||
e7f9a223 | 133 | /* Common superclass for both header-copying phases. */ |
134 | class ch_base : public gimple_opt_pass | |
135 | { | |
136 | protected: | |
137 | ch_base (pass_data data, gcc::context *ctxt) | |
138 | : gimple_opt_pass (data, ctxt) | |
139 | {} | |
140 | ||
141 | /* Copies headers of all loops in FUN for which process_loop_p is true. */ | |
142 | unsigned int copy_headers (function *fun); | |
143 | ||
144 | /* Return true to copy headers of LOOP or false to skip. */ | |
145 | virtual bool process_loop_p (struct loop *loop) = 0; | |
146 | }; | |
147 | ||
65b0537f | 148 | const pass_data pass_data_ch = |
149 | { | |
150 | GIMPLE_PASS, /* type */ | |
151 | "ch", /* name */ | |
152 | OPTGROUP_LOOP, /* optinfo_flags */ | |
65b0537f | 153 | TV_TREE_CH, /* tv_id */ |
154 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
155 | 0, /* properties_provided */ | |
156 | 0, /* properties_destroyed */ | |
157 | 0, /* todo_flags_start */ | |
051d7389 | 158 | 0, /* todo_flags_finish */ |
65b0537f | 159 | }; |
160 | ||
e7f9a223 | 161 | class pass_ch : public ch_base |
65b0537f | 162 | { |
163 | public: | |
164 | pass_ch (gcc::context *ctxt) | |
e7f9a223 | 165 | : ch_base (pass_data_ch, ctxt) |
65b0537f | 166 | {} |
167 | ||
168 | /* opt_pass methods: */ | |
169 | virtual bool gate (function *) { return flag_tree_ch != 0; } | |
e7f9a223 | 170 | |
171 | /* Initialize and finalize loop structures, copying headers inbetween. */ | |
65b0537f | 172 | virtual unsigned int execute (function *); |
173 | ||
e7f9a223 | 174 | protected: |
175 | /* ch_base method: */ | |
176 | virtual bool process_loop_p (struct loop *loop); | |
65b0537f | 177 | }; // class pass_ch |
178 | ||
e7f9a223 | 179 | const pass_data pass_data_ch_vect = |
180 | { | |
181 | GIMPLE_PASS, /* type */ | |
182 | "ch_vect", /* name */ | |
183 | OPTGROUP_LOOP, /* optinfo_flags */ | |
184 | TV_TREE_CH, /* tv_id */ | |
185 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
186 | 0, /* properties_provided */ | |
187 | 0, /* properties_destroyed */ | |
188 | 0, /* todo_flags_start */ | |
189 | 0, /* todo_flags_finish */ | |
190 | }; | |
191 | ||
192 | /* This is a more aggressive version of the same pass, designed to run just | |
193 | before if-conversion and vectorization, to put more loops into the form | |
194 | required for those phases. */ | |
195 | class pass_ch_vect : public ch_base | |
196 | { | |
197 | public: | |
198 | pass_ch_vect (gcc::context *ctxt) | |
199 | : ch_base (pass_data_ch_vect, ctxt) | |
200 | {} | |
201 | ||
202 | /* opt_pass methods: */ | |
203 | virtual bool gate (function *fun) | |
204 | { | |
205 | return flag_tree_ch != 0 | |
206 | && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops); | |
207 | } | |
208 | ||
209 | /* Just copy headers, no initialization/finalization of loop structures. */ | |
210 | virtual unsigned int execute (function *); | |
211 | ||
212 | protected: | |
213 | /* ch_base method: */ | |
214 | virtual bool process_loop_p (struct loop *loop); | |
215 | }; // class pass_ch_vect | |
216 | ||
217 | /* For all loops, copy the condition at the end of the loop body in front | |
218 | of the loop. This is beneficial since it increases efficiency of | |
219 | code motion optimizations. It also saves one jump on entry to the loop. */ | |
220 | ||
65b0537f | 221 | unsigned int |
e7f9a223 | 222 | ch_base::copy_headers (function *fun) |
f3d9a16c | 223 | { |
f3d9a16c | 224 | struct loop *loop; |
225 | basic_block header; | |
4d6b11ab | 226 | edge exit, entry; |
227 | basic_block *bbs, *copied_bbs; | |
d8b5b4fe | 228 | unsigned n_bbs; |
4d6b11ab | 229 | unsigned bbs_size; |
051d7389 | 230 | bool changed = false; |
f3d9a16c | 231 | |
65b0537f | 232 | if (number_of_loops (fun) <= 1) |
7a3bf727 | 233 | return 0; |
f3d9a16c | 234 | |
65b0537f | 235 | bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); |
236 | copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); | |
237 | bbs_size = n_basic_blocks_for_fn (fun); | |
d8b5b4fe | 238 | |
f21d4d00 | 239 | FOR_EACH_LOOP (loop, 0) |
f3d9a16c | 240 | { |
241 | /* Copy at most 20 insns. */ | |
242 | int limit = 20; | |
243 | ||
d8b5b4fe | 244 | header = loop->header; |
f3d9a16c | 245 | |
246 | /* If the loop is already a do-while style one (either because it was | |
247 | written as such, or because jump threading transformed it into one), | |
248 | we might be in fact peeling the first iteration of the loop. This | |
249 | in general is not a good idea. */ | |
e7f9a223 | 250 | if (!process_loop_p (loop)) |
f3d9a16c | 251 | continue; |
252 | ||
253 | /* Iterate the header copying up to limit; this takes care of the cases | |
254 | like while (a && b) {...}, where we want to have both of the conditions | |
255 | copied. TODO -- handle while (a || b) - like cases, by not requiring | |
256 | the header to have just a single successor and copying up to | |
d8b5b4fe | 257 | postdominator. */ |
258 | ||
259 | exit = NULL; | |
260 | n_bbs = 0; | |
f3d9a16c | 261 | while (should_duplicate_loop_header_p (header, loop, &limit)) |
262 | { | |
f3d9a16c | 263 | /* Find a successor of header that is inside a loop; i.e. the new |
264 | header after the condition is copied. */ | |
cd665a06 | 265 | if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)) |
266 | exit = EDGE_SUCC (header, 0); | |
f3d9a16c | 267 | else |
cd665a06 | 268 | exit = EDGE_SUCC (header, 1); |
d8b5b4fe | 269 | bbs[n_bbs++] = header; |
4d6b11ab | 270 | gcc_assert (bbs_size > n_bbs); |
d8b5b4fe | 271 | header = exit->dest; |
f3d9a16c | 272 | } |
f3d9a16c | 273 | |
d8b5b4fe | 274 | if (!exit) |
275 | continue; | |
f3d9a16c | 276 | |
d8b5b4fe | 277 | if (dump_file && (dump_flags & TDF_DETAILS)) |
278 | fprintf (dump_file, | |
279 | "Duplicating header of the loop %d up to edge %d->%d.\n", | |
280 | loop->num, exit->src->index, exit->dest->index); | |
281 | ||
282 | /* Ensure that the header will have just the latch as a predecessor | |
283 | inside the loop. */ | |
ea091dfd | 284 | if (!single_pred_p (exit->dest)) |
88e6f696 | 285 | exit = single_pred_edge (split_edge (exit)); |
d8b5b4fe | 286 | |
4d6b11ab | 287 | entry = loop_preheader_edge (loop); |
4d6b11ab | 288 | |
80ed2d81 | 289 | propagate_threaded_block_debug_into (exit->dest, entry->dest); |
d99f53b2 | 290 | if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs, |
291 | true)) | |
d8b5b4fe | 292 | { |
293 | fprintf (dump_file, "Duplication failed.\n"); | |
294 | continue; | |
295 | } | |
296 | ||
c7addd8c | 297 | /* If the loop has the form "for (i = j; i < j + 10; i++)" then |
298 | this copying can introduce a case where we rely on undefined | |
299 | signed overflow to eliminate the preheader condition, because | |
300 | we assume that "j < j + 10" is true. We don't want to warn | |
301 | about that case for -Wstrict-overflow, because in general we | |
302 | don't warn about overflow involving loops. Prevent the | |
75a70cf9 | 303 | warning by setting the no_warning flag in the condition. */ |
c7addd8c | 304 | if (warn_strict_overflow > 0) |
305 | { | |
306 | unsigned int i; | |
307 | ||
308 | for (i = 0; i < n_bbs; ++i) | |
309 | { | |
75a70cf9 | 310 | gimple_stmt_iterator bsi; |
72c59a18 | 311 | |
75a70cf9 | 312 | for (bsi = gsi_start_bb (copied_bbs[i]); |
313 | !gsi_end_p (bsi); | |
314 | gsi_next (&bsi)) | |
72c59a18 | 315 | { |
75a70cf9 | 316 | gimple stmt = gsi_stmt (bsi); |
317 | if (gimple_code (stmt) == GIMPLE_COND) | |
318 | gimple_set_no_warning (stmt, true); | |
319 | else if (is_gimple_assign (stmt)) | |
72c59a18 | 320 | { |
75a70cf9 | 321 | enum tree_code rhs_code = gimple_assign_rhs_code (stmt); |
322 | if (TREE_CODE_CLASS (rhs_code) == tcc_comparison) | |
323 | gimple_set_no_warning (stmt, true); | |
72c59a18 | 324 | } |
325 | } | |
c7addd8c | 326 | } |
327 | } | |
328 | ||
d8b5b4fe | 329 | /* Ensure that the latch and the preheader is simple (we know that they |
330 | are not now, since there was the loop exit condition. */ | |
88e6f696 | 331 | split_edge (loop_preheader_edge (loop)); |
332 | split_edge (loop_latch_edge (loop)); | |
051d7389 | 333 | |
334 | changed = true; | |
f3d9a16c | 335 | } |
336 | ||
e7f9a223 | 337 | if (changed) |
338 | update_ssa (TODO_update_ssa); | |
d8b5b4fe | 339 | free (bbs); |
4d6b11ab | 340 | free (copied_bbs); |
d8b5b4fe | 341 | |
051d7389 | 342 | return changed ? TODO_cleanup_cfg : 0; |
f3d9a16c | 343 | } |
344 | ||
e7f9a223 | 345 | /* Initialize the loop structures we need, and finalize after. */ |
346 | ||
347 | unsigned int | |
348 | pass_ch::execute (function *fun) | |
349 | { | |
350 | loop_optimizer_init (LOOPS_HAVE_PREHEADERS | |
351 | | LOOPS_HAVE_SIMPLE_LATCHES); | |
352 | ||
353 | unsigned int res = copy_headers (fun); | |
354 | ||
355 | loop_optimizer_finalize (); | |
356 | return res; | |
357 | } | |
358 | ||
359 | /* Assume an earlier phase has already initialized all the loop structures that | |
360 | we need here (and perhaps others too), and that these will be finalized by | |
361 | a later phase. */ | |
362 | ||
363 | unsigned int | |
364 | pass_ch_vect::execute (function *fun) | |
365 | { | |
366 | return copy_headers (fun); | |
367 | } | |
368 | ||
369 | /* Apply header copying according to a very simple test of do-while shape. */ | |
370 | ||
371 | bool | |
372 | pass_ch::process_loop_p (struct loop *loop) | |
373 | { | |
374 | return !do_while_loop_p (loop); | |
375 | } | |
376 | ||
377 | /* Apply header-copying to loops where we might enable vectorization. */ | |
378 | ||
379 | bool | |
380 | pass_ch_vect::process_loop_p (struct loop *loop) | |
381 | { | |
382 | if (!flag_tree_vectorize && !loop->force_vectorize) | |
383 | return false; | |
384 | ||
385 | if (loop->dont_vectorize) | |
386 | return false; | |
387 | ||
388 | if (!do_while_loop_p (loop)) | |
389 | return true; | |
390 | ||
391 | /* The vectorizer won't handle anything with multiple exits, so skip. */ | |
392 | edge exit = single_exit (loop); | |
393 | if (!exit) | |
394 | return false; | |
395 | ||
396 | /* Copy headers iff there looks to be code in the loop after the exit block, | |
397 | i.e. the exit block has an edge to another block (besides the latch, | |
398 | which should be empty). */ | |
399 | edge_iterator ei; | |
400 | edge e; | |
401 | FOR_EACH_EDGE (e, ei, exit->src->succs) | |
402 | if (!loop_exit_edge_p (loop, e) | |
403 | && e->dest != loop->header | |
404 | && e->dest != loop->latch) | |
405 | return true; | |
406 | ||
407 | return false; | |
408 | } | |
409 | ||
cbe8bda8 | 410 | } // anon namespace |
411 | ||
e7f9a223 | 412 | gimple_opt_pass * |
413 | make_pass_ch_vect (gcc::context *ctxt) | |
414 | { | |
415 | return new pass_ch_vect (ctxt); | |
416 | } | |
417 | ||
cbe8bda8 | 418 | gimple_opt_pass * |
419 | make_pass_ch (gcc::context *ctxt) | |
420 | { | |
421 | return new pass_ch (ctxt); | |
422 | } |