comparison gcc/tree-ssa-loop-ch.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Loop header copying on trees. 1 /* Loop header copying on trees.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 3
5 This file is part of GCC. 4 This file is part of GCC.
6 5
7 GCC is free software; you can redistribute it and/or modify it 6 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the 7 under the terms of the GNU General Public License as published by the
19 <http://www.gnu.org/licenses/>. */ 18 <http://www.gnu.org/licenses/>. */
20 19
21 #include "config.h" 20 #include "config.h"
22 #include "system.h" 21 #include "system.h"
23 #include "coretypes.h" 22 #include "coretypes.h"
24 #include "tm.h" 23 #include "backend.h"
25 #include "tree.h" 24 #include "tree.h"
26 #include "tm_p.h" 25 #include "gimple.h"
27 #include "basic-block.h" 26 #include "cfghooks.h"
28 #include "output.h"
29 #include "tree-flow.h"
30 #include "tree-dump.h"
31 #include "tree-pass.h" 27 #include "tree-pass.h"
32 #include "timevar.h" 28 #include "gimple-ssa.h"
29 #include "gimple-iterator.h"
30 #include "tree-cfg.h"
31 #include "tree-into-ssa.h"
33 #include "cfgloop.h" 32 #include "cfgloop.h"
34 #include "tree-inline.h" 33 #include "tree-inline.h"
35 #include "flags.h" 34 #include "tree-ssa-scopedtables.h"
36 #include "tree-inline.h" 35 #include "tree-ssa-threadedge.h"
36 #include "params.h"
37 37
38 /* Duplicates headers of loops if they are small enough, so that the statements 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 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 40 increases effectiveness of code motion optimizations, and reduces the need
41 for loop preconditioning. */ 41 for loop preconditioning. */
47 static bool 47 static bool
48 should_duplicate_loop_header_p (basic_block header, struct loop *loop, 48 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
49 int *limit) 49 int *limit)
50 { 50 {
51 gimple_stmt_iterator bsi; 51 gimple_stmt_iterator bsi;
52 gimple last; 52 gimple *last;
53 53
54 /* Do not copy one block more than once (we do not really want to do 54 gcc_assert (!header->aux);
55 loop peeling here). */
56 if (header->aux)
57 return false;
58 55
59 /* Loop header copying usually increases size of the code. This used not to 56 /* Loop header copying usually increases size of the code. This used not to
60 be true, since quite often it is possible to verify that the condition is 57 be true, since quite often it is possible to verify that the condition is
61 satisfied in the first iteration and therefore to eliminate it. Jump 58 satisfied in the first iteration and therefore to eliminate it. Jump
62 threading handles these cases now. */ 59 threading handles these cases now. */
63 if (optimize_loop_for_size_p (loop)) 60 if (optimize_loop_for_size_p (loop))
64 return false; 61 {
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;
67 }
65 68
66 gcc_assert (EDGE_COUNT (header->succs) > 0); 69 gcc_assert (EDGE_COUNT (header->succs) > 0);
67 if (single_succ_p (header)) 70 if (single_succ_p (header))
68 return false; 71 {
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;
77 }
78
69 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest) 79 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
70 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest)) 80 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
71 return false; 81 {
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;
87 }
72 88
73 /* If this is not the original loop header, we want it to have just 89 /* If this is not the original loop header, we want it to have just
74 one predecessor in order to match the && pattern. */ 90 one predecessor in order to match the && pattern. */
75 if (header != loop->header && !single_pred_p (header)) 91 if (header != loop->header && !single_pred_p (header))
76 return false; 92 {
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;
98 }
77 99
78 last = last_stmt (header); 100 last = last_stmt (header);
79 if (gimple_code (last) != GIMPLE_COND) 101 if (gimple_code (last) != GIMPLE_COND)
80 return false; 102 {
81 103 if (dump_file && (dump_flags & TDF_DETAILS))
82 /* Approximately copy the conditions that used to be used in jump.c -- 104 fprintf (dump_file,
83 at most 20 insns and no calls. */ 105 " Not duplicating bb %i: it does not end by conditional.\n",
106 header->index);
107 return false;
108 }
109
110 /* Count number of instructions and punt on calls. */
84 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi)) 111 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
85 { 112 {
86 last = gsi_stmt (bsi); 113 last = gsi_stmt (bsi);
87 114
88 if (gimple_code (last) == GIMPLE_LABEL) 115 if (gimple_code (last) == GIMPLE_LABEL)
89 continue; 116 continue;
90 117
91 if (is_gimple_debug (last)) 118 if (is_gimple_debug (last))
92 continue; 119 continue;
93 120
94 if (is_gimple_call (last)) 121 if (gimple_code (last) == GIMPLE_CALL
95 return false; 122 && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
123 /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
124 at current loop's header. Don't copy in this case. */
125 || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
126 {
127 if (dump_file && (dump_flags & TDF_DETAILS))
128 fprintf (dump_file,
129 " Not duplicating bb %i: it contains call.\n",
130 header->index);
131 return false;
132 }
96 133
97 *limit -= estimate_num_insns (last, &eni_size_weights); 134 *limit -= estimate_num_insns (last, &eni_size_weights);
98 if (*limit < 0) 135 if (*limit < 0)
99 return false; 136 {
100 } 137 if (dump_file && (dump_flags & TDF_DETAILS))
101 138 fprintf (dump_file,
139 " Not duplicating bb %i contains too many insns.\n",
140 header->index);
141 return false;
142 }
143 }
144 if (dump_file && (dump_flags & TDF_DETAILS))
145 fprintf (dump_file, " Will duplicate bb %i\n", header->index);
102 return true; 146 return true;
103 } 147 }
104 148
105 /* Checks whether LOOP is a do-while style loop. */ 149 /* Checks whether LOOP is a do-while style loop. */
106 150
107 static bool 151 static bool
108 do_while_loop_p (struct loop *loop) 152 do_while_loop_p (struct loop *loop)
109 { 153 {
110 gimple stmt = last_stmt (loop->latch); 154 gimple *stmt = last_stmt (loop->latch);
111 155
112 /* If the latch of the loop is not empty, it is not a do-while loop. */ 156 /* If the latch of the loop is not empty, it is not a do-while loop. */
113 if (stmt 157 if (stmt
114 && gimple_code (stmt) != GIMPLE_LABEL) 158 && gimple_code (stmt) != GIMPLE_LABEL)
115 return false; 159 {
160 if (dump_file && (dump_flags & TDF_DETAILS))
161 fprintf (dump_file,
162 "Loop %i is not do-while loop: latch is not empty.\n",
163 loop->num);
164 return false;
165 }
116 166
117 /* If the header contains just a condition, it is not a do-while loop. */ 167 /* If the header contains just a condition, it is not a do-while loop. */
118 stmt = last_and_only_stmt (loop->header); 168 stmt = last_and_only_stmt (loop->header);
119 if (stmt 169 if (stmt
120 && gimple_code (stmt) == GIMPLE_COND) 170 && gimple_code (stmt) == GIMPLE_COND)
121 return false; 171 {
172 if (dump_file && (dump_flags & TDF_DETAILS))
173 fprintf (dump_file,
174 "Loop %i is not do-while loop: "
175 "header contains just condition.\n", loop->num);
176 return false;
177 }
178 if (dump_file && (dump_flags & TDF_DETAILS))
179 fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
122 180
123 return true; 181 return true;
124 } 182 }
183
184 namespace {
185
186 /* Common superclass for both header-copying phases. */
187 class ch_base : public gimple_opt_pass
188 {
189 protected:
190 ch_base (pass_data data, gcc::context *ctxt)
191 : gimple_opt_pass (data, ctxt)
192 {}
193
194 /* Copies headers of all loops in FUN for which process_loop_p is true. */
195 unsigned int copy_headers (function *fun);
196
197 /* Return true to copy headers of LOOP or false to skip. */
198 virtual bool process_loop_p (struct loop *loop) = 0;
199 };
200
201 const pass_data pass_data_ch =
202 {
203 GIMPLE_PASS, /* type */
204 "ch", /* name */
205 OPTGROUP_LOOP, /* optinfo_flags */
206 TV_TREE_CH, /* tv_id */
207 ( PROP_cfg | PROP_ssa ), /* properties_required */
208 0, /* properties_provided */
209 0, /* properties_destroyed */
210 0, /* todo_flags_start */
211 0, /* todo_flags_finish */
212 };
213
214 class pass_ch : public ch_base
215 {
216 public:
217 pass_ch (gcc::context *ctxt)
218 : ch_base (pass_data_ch, ctxt)
219 {}
220
221 /* opt_pass methods: */
222 virtual bool gate (function *) { return flag_tree_ch != 0; }
223
224 /* Initialize and finalize loop structures, copying headers inbetween. */
225 virtual unsigned int execute (function *);
226
227 opt_pass * clone () { return new pass_ch (m_ctxt); }
228
229 protected:
230 /* ch_base method: */
231 virtual bool process_loop_p (struct loop *loop);
232 }; // class pass_ch
233
234 const pass_data pass_data_ch_vect =
235 {
236 GIMPLE_PASS, /* type */
237 "ch_vect", /* name */
238 OPTGROUP_LOOP, /* optinfo_flags */
239 TV_TREE_CH, /* tv_id */
240 ( PROP_cfg | PROP_ssa ), /* properties_required */
241 0, /* properties_provided */
242 0, /* properties_destroyed */
243 0, /* todo_flags_start */
244 0, /* todo_flags_finish */
245 };
246
247 /* This is a more aggressive version of the same pass, designed to run just
248 before if-conversion and vectorization, to put more loops into the form
249 required for those phases. */
250 class pass_ch_vect : public ch_base
251 {
252 public:
253 pass_ch_vect (gcc::context *ctxt)
254 : ch_base (pass_data_ch_vect, ctxt)
255 {}
256
257 /* opt_pass methods: */
258 virtual bool gate (function *fun)
259 {
260 return flag_tree_ch != 0
261 && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
262 }
263
264 /* Just copy headers, no initialization/finalization of loop structures. */
265 virtual unsigned int execute (function *);
266
267 protected:
268 /* ch_base method: */
269 virtual bool process_loop_p (struct loop *loop);
270 }; // class pass_ch_vect
125 271
126 /* For all loops, copy the condition at the end of the loop body in front 272 /* For all loops, copy the condition at the end of the loop body in front
127 of the loop. This is beneficial since it increases efficiency of 273 of the loop. This is beneficial since it increases efficiency of
128 code motion optimizations. It also saves one jump on entry to the loop. */ 274 code motion optimizations. It also saves one jump on entry to the loop. */
129 275
130 static unsigned int 276 unsigned int
131 copy_loop_headers (void) 277 ch_base::copy_headers (function *fun)
132 { 278 {
133 loop_iterator li;
134 struct loop *loop; 279 struct loop *loop;
135 basic_block header; 280 basic_block header;
136 edge exit, entry; 281 edge exit, entry;
137 basic_block *bbs, *copied_bbs; 282 basic_block *bbs, *copied_bbs;
138 unsigned n_bbs; 283 unsigned n_bbs;
139 unsigned bbs_size; 284 unsigned bbs_size;
140 285 bool changed = false;
141 loop_optimizer_init (LOOPS_HAVE_PREHEADERS 286
142 | LOOPS_HAVE_SIMPLE_LATCHES); 287 if (number_of_loops (fun) <= 1)
143 if (number_of_loops () <= 1)
144 {
145 loop_optimizer_finalize ();
146 return 0; 288 return 0;
147 } 289
148 290 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
149 #ifdef ENABLE_CHECKING 291 copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
150 verify_loop_structure (); 292 bbs_size = n_basic_blocks_for_fn (fun);
151 #endif 293
152 294 FOR_EACH_LOOP (loop, 0)
153 bbs = XNEWVEC (basic_block, n_basic_blocks); 295 {
154 copied_bbs = XNEWVEC (basic_block, n_basic_blocks); 296 int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS);
155 bbs_size = n_basic_blocks; 297 int remaining_limit = initial_limit;
156 298 if (dump_file && (dump_flags & TDF_DETAILS))
157 FOR_EACH_LOOP (li, loop, 0) 299 fprintf (dump_file,
158 { 300 "Analyzing loop %i\n", loop->num);
159 /* Copy at most 20 insns. */
160 int limit = 20;
161 301
162 header = loop->header; 302 header = loop->header;
163 303
164 /* If the loop is already a do-while style one (either because it was 304 /* If the loop is already a do-while style one (either because it was
165 written as such, or because jump threading transformed it into one), 305 written as such, or because jump threading transformed it into one),
166 we might be in fact peeling the first iteration of the loop. This 306 we might be in fact peeling the first iteration of the loop. This
167 in general is not a good idea. */ 307 in general is not a good idea. */
168 if (do_while_loop_p (loop)) 308 if (!process_loop_p (loop))
169 continue; 309 continue;
170 310
171 /* Iterate the header copying up to limit; this takes care of the cases 311 /* Iterate the header copying up to limit; this takes care of the cases
172 like while (a && b) {...}, where we want to have both of the conditions 312 like while (a && b) {...}, where we want to have both of the conditions
173 copied. TODO -- handle while (a || b) - like cases, by not requiring 313 copied. TODO -- handle while (a || b) - like cases, by not requiring
174 the header to have just a single successor and copying up to 314 the header to have just a single successor and copying up to
175 postdominator. */ 315 postdominator. */
176 316
177 exit = NULL; 317 exit = NULL;
178 n_bbs = 0; 318 n_bbs = 0;
179 while (should_duplicate_loop_header_p (header, loop, &limit)) 319 while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
180 { 320 {
181 /* Find a successor of header that is inside a loop; i.e. the new 321 /* Find a successor of header that is inside a loop; i.e. the new
182 header after the condition is copied. */ 322 header after the condition is copied. */
183 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)) 323 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
184 exit = EDGE_SUCC (header, 0); 324 exit = EDGE_SUCC (header, 0);
192 if (!exit) 332 if (!exit)
193 continue; 333 continue;
194 334
195 if (dump_file && (dump_flags & TDF_DETAILS)) 335 if (dump_file && (dump_flags & TDF_DETAILS))
196 fprintf (dump_file, 336 fprintf (dump_file,
197 "Duplicating header of the loop %d up to edge %d->%d.\n", 337 "Duplicating header of the loop %d up to edge %d->%d,"
198 loop->num, exit->src->index, exit->dest->index); 338 " %i insns.\n",
339 loop->num, exit->src->index, exit->dest->index,
340 initial_limit - remaining_limit);
199 341
200 /* Ensure that the header will have just the latch as a predecessor 342 /* Ensure that the header will have just the latch as a predecessor
201 inside the loop. */ 343 inside the loop. */
202 if (!single_pred_p (exit->dest)) 344 if (!single_pred_p (exit->dest))
203 exit = single_pred_edge (split_edge (exit)); 345 exit = single_pred_edge (split_edge (exit));
204 346
205 entry = loop_preheader_edge (loop); 347 entry = loop_preheader_edge (loop);
206 348
207 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs)) 349 propagate_threaded_block_debug_into (exit->dest, entry->dest);
350 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
351 true))
208 { 352 {
209 fprintf (dump_file, "Duplication failed.\n"); 353 fprintf (dump_file, "Duplication failed.\n");
210 continue; 354 continue;
211 } 355 }
212 356
227 371
228 for (bsi = gsi_start_bb (copied_bbs[i]); 372 for (bsi = gsi_start_bb (copied_bbs[i]);
229 !gsi_end_p (bsi); 373 !gsi_end_p (bsi);
230 gsi_next (&bsi)) 374 gsi_next (&bsi))
231 { 375 {
232 gimple stmt = gsi_stmt (bsi); 376 gimple *stmt = gsi_stmt (bsi);
233 if (gimple_code (stmt) == GIMPLE_COND) 377 if (gimple_code (stmt) == GIMPLE_COND)
234 gimple_set_no_warning (stmt, true); 378 gimple_set_no_warning (stmt, true);
235 else if (is_gimple_assign (stmt)) 379 else if (is_gimple_assign (stmt))
236 { 380 {
237 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 381 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
244 388
245 /* Ensure that the latch and the preheader is simple (we know that they 389 /* Ensure that the latch and the preheader is simple (we know that they
246 are not now, since there was the loop exit condition. */ 390 are not now, since there was the loop exit condition. */
247 split_edge (loop_preheader_edge (loop)); 391 split_edge (loop_preheader_edge (loop));
248 split_edge (loop_latch_edge (loop)); 392 split_edge (loop_latch_edge (loop));
249 } 393
250 394 changed = true;
395 }
396
397 if (changed)
398 update_ssa (TODO_update_ssa);
251 free (bbs); 399 free (bbs);
252 free (copied_bbs); 400 free (copied_bbs);
253 401
402 return changed ? TODO_cleanup_cfg : 0;
403 }
404
405 /* Initialize the loop structures we need, and finalize after. */
406
407 unsigned int
408 pass_ch::execute (function *fun)
409 {
410 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
411 | LOOPS_HAVE_SIMPLE_LATCHES);
412
413 unsigned int res = copy_headers (fun);
414
254 loop_optimizer_finalize (); 415 loop_optimizer_finalize ();
255 return 0; 416 return res;
256 } 417 }
257 418
258 static bool 419 /* Assume an earlier phase has already initialized all the loop structures that
259 gate_ch (void) 420 we need here (and perhaps others too), and that these will be finalized by
260 { 421 a later phase. */
261 return flag_tree_ch != 0; 422
262 } 423 unsigned int
263 424 pass_ch_vect::execute (function *fun)
264 struct gimple_opt_pass pass_ch = 425 {
265 { 426 return copy_headers (fun);
266 { 427 }
267 GIMPLE_PASS, 428
268 "ch", /* name */ 429 /* Apply header copying according to a very simple test of do-while shape. */
269 gate_ch, /* gate */ 430
270 copy_loop_headers, /* execute */ 431 bool
271 NULL, /* sub */ 432 pass_ch::process_loop_p (struct loop *loop)
272 NULL, /* next */ 433 {
273 0, /* static_pass_number */ 434 return !do_while_loop_p (loop);
274 TV_TREE_CH, /* tv_id */ 435 }
275 PROP_cfg | PROP_ssa, /* properties_required */ 436
276 0, /* properties_provided */ 437 /* Apply header-copying to loops where we might enable vectorization. */
277 0, /* properties_destroyed */ 438
278 0, /* todo_flags_start */ 439 bool
279 TODO_cleanup_cfg 440 pass_ch_vect::process_loop_p (struct loop *loop)
280 | TODO_verify_ssa 441 {
281 | TODO_verify_flow 442 if (!flag_tree_loop_vectorize && !loop->force_vectorize)
282 | TODO_dump_func /* todo_flags_finish */ 443 return false;
283 } 444
284 }; 445 if (loop->dont_vectorize)
446 return false;
447
448 if (!do_while_loop_p (loop))
449 return true;
450
451 /* The vectorizer won't handle anything with multiple exits, so skip. */
452 edge exit = single_exit (loop);
453 if (!exit)
454 return false;
455
456 /* Copy headers iff there looks to be code in the loop after the exit block,
457 i.e. the exit block has an edge to another block (besides the latch,
458 which should be empty). */
459 edge_iterator ei;
460 edge e;
461 FOR_EACH_EDGE (e, ei, exit->src->succs)
462 if (!loop_exit_edge_p (loop, e)
463 && e->dest != loop->header
464 && e->dest != loop->latch)
465 return true;
466
467 return false;
468 }
469
470 } // anon namespace
471
472 gimple_opt_pass *
473 make_pass_ch_vect (gcc::context *ctxt)
474 {
475 return new pass_ch_vect (ctxt);
476 }
477
478 gimple_opt_pass *
479 make_pass_ch (gcc::context *ctxt)
480 {
481 return new pass_ch (ctxt);
482 }