1 /* Code sinking for trees
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
28 #include "tree-inline.h"
29 #include "tree-flow.h"
30 #include "gimple.h"
31 #include "hashtab.h"
32 #include "tree-iterator.h"
33 #include "alloc-pool.h"
34 #include "tree-pass.h"
35 #include "flags.h"
36 #include "bitmap.h"
37 #include "cfgloop.h"
38 #include "params.h"
39
40 /* TODO:
41 1. Sinking store only using scalar promotion (IE without moving the RHS):
42
43 *q = p;
44 p = p + 1;
45 if (something)
46 *q = <not p>;
47 else
48 y = *q;
49
50
51 should become
52 sinktemp = p;
53 p = p + 1;
54 if (something)
55 *q = <not p>;
56 else
57 {
58 *q = sinktemp;
59 y = *q
60 }
61 Store copy propagation will take care of the store elimination above.
62
63
64 2. Sinking using Partial Dead Code Elimination. */
65
66
67 static struct
68 {
69 /* The number of statements sunk down the flowgraph by code sinking. */
70 int sunk;
71
72 } sink_stats;
73
74
75 /* Given a PHI, and one of its arguments (DEF), find the edge for
76 that argument and return it. If the argument occurs twice in the PHI node,
77 we return NULL. */
78
79 static basic_block
find_bb_for_arg(gimple phi,tree def)80 find_bb_for_arg (gimple phi, tree def)
81 {
82 size_t i;
83 bool foundone = false;
84 basic_block result = NULL;
85 for (i = 0; i < gimple_phi_num_args (phi); i++)
86 if (PHI_ARG_DEF (phi, i) == def)
87 {
88 if (foundone)
89 return NULL;
90 foundone = true;
91 result = gimple_phi_arg_edge (phi, i)->src;
92 }
93 return result;
94 }
95
96 /* When the first immediate use is in a statement, then return true if all
97 immediate uses in IMM are in the same statement.
98 We could also do the case where the first immediate use is in a phi node,
99 and all the other uses are in phis in the same basic block, but this
100 requires some expensive checking later (you have to make sure no def/vdef
101 in the statement occurs for multiple edges in the various phi nodes it's
102 used in, so that you only have one place you can sink it to. */
103
104 static bool
all_immediate_uses_same_place(gimple stmt)105 all_immediate_uses_same_place (gimple stmt)
106 {
107 gimple firstuse = NULL;
108 ssa_op_iter op_iter;
109 imm_use_iterator imm_iter;
110 use_operand_p use_p;
111 tree var;
112
113 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
114 {
115 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
116 {
117 if (is_gimple_debug (USE_STMT (use_p)))
118 continue;
119 if (firstuse == NULL)
120 firstuse = USE_STMT (use_p);
121 else
122 if (firstuse != USE_STMT (use_p))
123 return false;
124 }
125 }
126
127 return true;
128 }
129
130 /* Find the nearest common dominator of all of the immediate uses in IMM. */
131
132 static basic_block
nearest_common_dominator_of_uses(gimple stmt,bool * debug_stmts)133 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts)
134 {
135 bitmap blocks = BITMAP_ALLOC (NULL);
136 basic_block commondom;
137 unsigned int j;
138 bitmap_iterator bi;
139 ssa_op_iter op_iter;
140 imm_use_iterator imm_iter;
141 use_operand_p use_p;
142 tree var;
143
144 bitmap_clear (blocks);
145 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
146 {
147 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
148 {
149 gimple usestmt = USE_STMT (use_p);
150 basic_block useblock;
151
152 if (gimple_code (usestmt) == GIMPLE_PHI)
153 {
154 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
155
156 useblock = gimple_phi_arg_edge (usestmt, idx)->src;
157 }
158 else if (is_gimple_debug (usestmt))
159 {
160 *debug_stmts = true;
161 continue;
162 }
163 else
164 {
165 useblock = gimple_bb (usestmt);
166 }
167
168 /* Short circuit. Nothing dominates the entry block. */
169 if (useblock == ENTRY_BLOCK_PTR)
170 {
171 BITMAP_FREE (blocks);
172 return NULL;
173 }
174 bitmap_set_bit (blocks, useblock->index);
175 }
176 }
177 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
178 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
179 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
180 BASIC_BLOCK (j));
181 BITMAP_FREE (blocks);
182 return commondom;
183 }
184
185 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
186 tree, return the best basic block between them (inclusive) to place
187 statements.
188
189 We want the most control dependent block in the shallowest loop nest.
190
191 If the resulting block is in a shallower loop nest, then use it. Else
192 only use the resulting block if it has significantly lower execution
193 frequency than EARLY_BB to avoid gratutious statement movement. We
194 consider statements with VOPS more desirable to move.
195
196 This pass would obviously benefit from PDO as it utilizes block
197 frequencies. It would also benefit from recomputing frequencies
198 if profile data is not available since frequencies often get out
199 of sync with reality. */
200
201 static basic_block
select_best_block(basic_block early_bb,basic_block late_bb,gimple stmt)202 select_best_block (basic_block early_bb,
203 basic_block late_bb,
204 gimple stmt)
205 {
206 basic_block best_bb = late_bb;
207 basic_block temp_bb = late_bb;
208 int threshold;
209
210 while (temp_bb != early_bb)
211 {
212 /* If we've moved into a lower loop nest, then that becomes
213 our best block. */
214 if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
215 best_bb = temp_bb;
216
217 /* Walk up the dominator tree, hopefully we'll find a shallower
218 loop nest. */
219 temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
220 }
221
222 /* If we found a shallower loop nest, then we always consider that
223 a win. This will always give us the most control dependent block
224 within that loop nest. */
225 if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
226 return best_bb;
227
228 /* Get the sinking threshold. If the statement to be moved has memory
229 operands, then increase the threshold by 7% as those are even more
230 profitable to avoid, clamping at 100%. */
231 threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
232 if (gimple_vuse (stmt) || gimple_vdef (stmt))
233 {
234 threshold += 7;
235 if (threshold > 100)
236 threshold = 100;
237 }
238
239 /* If BEST_BB is at the same nesting level, then require it to have
240 significantly lower execution frequency to avoid gratutious movement. */
241 if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
242 && best_bb->frequency < (early_bb->frequency * threshold / 100.0))
243 return best_bb;
244
245 /* No better block found, so return EARLY_BB, which happens to be the
246 statement's original block. */
247 return early_bb;
248 }
249
250 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
251 determine the location to sink the statement to, if any.
252 Returns true if there is such location; in that case, TOGSI points to the
253 statement before that STMT should be moved. */
254
255 static bool
statement_sink_location(gimple stmt,basic_block frombb,gimple_stmt_iterator * togsi)256 statement_sink_location (gimple stmt, basic_block frombb,
257 gimple_stmt_iterator *togsi)
258 {
259 gimple use;
260 use_operand_p one_use = NULL_USE_OPERAND_P;
261 basic_block sinkbb;
262 use_operand_p use_p;
263 def_operand_p def_p;
264 ssa_op_iter iter;
265 imm_use_iterator imm_iter;
266
267 /* We only can sink assignments. */
268 if (!is_gimple_assign (stmt))
269 return false;
270
271 /* We only can sink stmts with a single definition. */
272 def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
273 if (def_p == NULL_DEF_OPERAND_P)
274 return false;
275
276 /* Return if there are no immediate uses of this stmt. */
277 if (has_zero_uses (DEF_FROM_PTR (def_p)))
278 return false;
279
280 /* There are a few classes of things we can't or don't move, some because we
281 don't have code to handle it, some because it's not profitable and some
282 because it's not legal.
283
284 We can't sink things that may be global stores, at least not without
285 calculating a lot more information, because we may cause it to no longer
286 be seen by an external routine that needs it depending on where it gets
287 moved to.
288
289 We don't want to sink loads from memory.
290
291 We can't sink statements that end basic blocks without splitting the
292 incoming edge for the sink location to place it there.
293
294 We can't sink statements that have volatile operands.
295
296 We don't want to sink dead code, so anything with 0 immediate uses is not
297 sunk.
298
299 Don't sink BLKmode assignments if current function has any local explicit
300 register variables, as BLKmode assignments may involve memcpy or memset
301 calls or, on some targets, inline expansion thereof that sometimes need
302 to use specific hard registers.
303
304 */
305 if (stmt_ends_bb_p (stmt)
306 || gimple_has_side_effects (stmt)
307 || gimple_has_volatile_ops (stmt)
308 || (gimple_vuse (stmt) && !gimple_vdef (stmt))
309 || (cfun->has_local_explicit_reg_vars
310 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
311 return false;
312
313 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
314 return false;
315
316 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
317 {
318 tree use = USE_FROM_PTR (use_p);
319 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
320 return false;
321 }
322
323 use = NULL;
324
325 /* If stmt is a store the one and only use needs to be the VOP
326 merging PHI node. */
327 if (gimple_vdef (stmt))
328 {
329 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
330 {
331 gimple use_stmt = USE_STMT (use_p);
332
333 /* A killing definition is not a use. */
334 if (gimple_assign_single_p (use_stmt)
335 && gimple_vdef (use_stmt)
336 && operand_equal_p (gimple_assign_lhs (stmt),
337 gimple_assign_lhs (use_stmt), 0))
338 {
339 /* If use_stmt is or might be a nop assignment then USE_STMT
340 acts as a use as well as definition. */
341 if (stmt != use_stmt
342 && ref_maybe_used_by_stmt_p (use_stmt,
343 gimple_assign_lhs (stmt)))
344 return false;
345 continue;
346 }
347
348 if (gimple_code (use_stmt) != GIMPLE_PHI)
349 return false;
350
351 if (use
352 && use != use_stmt)
353 return false;
354
355 use = use_stmt;
356 }
357 if (!use)
358 return false;
359 }
360 /* If all the immediate uses are not in the same place, find the nearest
361 common dominator of all the immediate uses. For PHI nodes, we have to
362 find the nearest common dominator of all of the predecessor blocks, since
363 that is where insertion would have to take place. */
364 else if (!all_immediate_uses_same_place (stmt))
365 {
366 bool debug_stmts = false;
367 basic_block commondom = nearest_common_dominator_of_uses (stmt,
368 &debug_stmts);
369
370 if (commondom == frombb)
371 return false;
372
373 /* Our common dominator has to be dominated by frombb in order to be a
374 trivially safe place to put this statement, since it has multiple
375 uses. */
376 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
377 return false;
378
379 commondom = select_best_block (frombb, commondom, stmt);
380
381 if (commondom == frombb)
382 return false;
383
384 *togsi = gsi_after_labels (commondom);
385
386 return true;
387 }
388 else
389 {
390 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
391 {
392 if (is_gimple_debug (USE_STMT (one_use)))
393 continue;
394 break;
395 }
396 use = USE_STMT (one_use);
397
398 if (gimple_code (use) != GIMPLE_PHI)
399 {
400 sinkbb = gimple_bb (use);
401 sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
402
403 if (sinkbb == frombb)
404 return false;
405
406 *togsi = gsi_for_stmt (use);
407
408 return true;
409 }
410 }
411
412 sinkbb = find_bb_for_arg (use, DEF_FROM_PTR (def_p));
413
414 /* This can happen if there are multiple uses in a PHI. */
415 if (!sinkbb)
416 return false;
417
418 sinkbb = select_best_block (frombb, sinkbb, stmt);
419 if (!sinkbb || sinkbb == frombb)
420 return false;
421
422 /* If the latch block is empty, don't make it non-empty by sinking
423 something into it. */
424 if (sinkbb == frombb->loop_father->latch
425 && empty_block_p (sinkbb))
426 return false;
427
428 *togsi = gsi_after_labels (sinkbb);
429
430 return true;
431 }
432
433 /* Perform code sinking on BB */
434
435 static void
sink_code_in_bb(basic_block bb)436 sink_code_in_bb (basic_block bb)
437 {
438 basic_block son;
439 gimple_stmt_iterator gsi;
440 edge_iterator ei;
441 edge e;
442 bool last = true;
443
444 /* If this block doesn't dominate anything, there can't be any place to sink
445 the statements to. */
446 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
447 goto earlyout;
448
449 /* We can't move things across abnormal edges, so don't try. */
450 FOR_EACH_EDGE (e, ei, bb->succs)
451 if (e->flags & EDGE_ABNORMAL)
452 goto earlyout;
453
454 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
455 {
456 gimple stmt = gsi_stmt (gsi);
457 gimple_stmt_iterator togsi;
458
459 if (!statement_sink_location (stmt, bb, &togsi))
460 {
461 if (!gsi_end_p (gsi))
462 gsi_prev (&gsi);
463 last = false;
464 continue;
465 }
466 if (dump_file)
467 {
468 fprintf (dump_file, "Sinking ");
469 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
470 fprintf (dump_file, " from bb %d to bb %d\n",
471 bb->index, (gsi_bb (togsi))->index);
472 }
473
474 /* Update virtual operands of statements in the path we
475 do not sink to. */
476 if (gimple_vdef (stmt))
477 {
478 imm_use_iterator iter;
479 use_operand_p use_p;
480 gimple vuse_stmt;
481
482 FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
483 if (gimple_code (vuse_stmt) != GIMPLE_PHI)
484 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
485 SET_USE (use_p, gimple_vuse (stmt));
486 }
487
488 /* If this is the end of the basic block, we need to insert at the end
489 of the basic block. */
490 if (gsi_end_p (togsi))
491 gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
492 else
493 gsi_move_before (&gsi, &togsi);
494
495 sink_stats.sunk++;
496
497 /* If we've just removed the last statement of the BB, the
498 gsi_end_p() test below would fail, but gsi_prev() would have
499 succeeded, and we want it to succeed. So we keep track of
500 whether we're at the last statement and pick up the new last
501 statement. */
502 if (last)
503 {
504 gsi = gsi_last_bb (bb);
505 continue;
506 }
507
508 last = false;
509 if (!gsi_end_p (gsi))
510 gsi_prev (&gsi);
511
512 }
513 earlyout:
514 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
515 son;
516 son = next_dom_son (CDI_POST_DOMINATORS, son))
517 {
518 sink_code_in_bb (son);
519 }
520 }
521
522 /* Perform code sinking.
523 This moves code down the flowgraph when we know it would be
524 profitable to do so, or it wouldn't increase the number of
525 executions of the statement.
526
527 IE given
528
529 a_1 = b + c;
530 if (<something>)
531 {
532 }
533 else
534 {
535 foo (&b, &c);
536 a_5 = b + c;
537 }
538 a_6 = PHI (a_5, a_1);
539 USE a_6.
540
541 we'll transform this into:
542
543 if (<something>)
544 {
545 a_1 = b + c;
546 }
547 else
548 {
549 foo (&b, &c);
550 a_5 = b + c;
551 }
552 a_6 = PHI (a_5, a_1);
553 USE a_6.
554
555 Note that this reduces the number of computations of a = b + c to 1
556 when we take the else edge, instead of 2.
557 */
558 static void
execute_sink_code(void)559 execute_sink_code (void)
560 {
561 loop_optimizer_init (LOOPS_NORMAL);
562 split_critical_edges ();
563 connect_infinite_loops_to_exit ();
564 memset (&sink_stats, 0, sizeof (sink_stats));
565 calculate_dominance_info (CDI_DOMINATORS);
566 calculate_dominance_info (CDI_POST_DOMINATORS);
567 sink_code_in_bb (EXIT_BLOCK_PTR);
568 statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
569 free_dominance_info (CDI_POST_DOMINATORS);
570 remove_fake_exit_edges ();
571 loop_optimizer_finalize ();
572 }
573
574 /* Gate and execute functions for PRE. */
575
576 static unsigned int
do_sink(void)577 do_sink (void)
578 {
579 execute_sink_code ();
580 return 0;
581 }
582
583 static bool
gate_sink(void)584 gate_sink (void)
585 {
586 return flag_tree_sink != 0;
587 }
588
589 struct gimple_opt_pass pass_sink_code =
590 {
591 {
592 GIMPLE_PASS,
593 "sink", /* name */
594 OPTGROUP_NONE, /* optinfo_flags */
595 gate_sink, /* gate */
596 do_sink, /* execute */
597 NULL, /* sub */
598 NULL, /* next */
599 0, /* static_pass_number */
600 TV_TREE_SINK, /* tv_id */
601 PROP_no_crit_edges | PROP_cfg
602 | PROP_ssa, /* properties_required */
603 0, /* properties_provided */
604 0, /* properties_destroyed */
605 0, /* todo_flags_start */
606 TODO_update_ssa
607 | TODO_verify_ssa
608 | TODO_verify_flow
609 | TODO_ggc_collect /* todo_flags_finish */
610 }
611 };
612