Daily bump.
[official-gcc.git] / gcc / tree-ssa-sink.c
blob1ed8a0e367a445456b0c3ca60a86d52d21f3c998
1 /* Code sinking for trees
2 Copyright (C) 2001-2015 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "fold-const.h"
36 #include "stor-layout.h"
37 #include "predict.h"
38 #include "hard-reg-set.h"
39 #include "input.h"
40 #include "function.h"
41 #include "dominance.h"
42 #include "cfg.h"
43 #include "cfganal.h"
44 #include "basic-block.h"
45 #include "gimple-pretty-print.h"
46 #include "tree-inline.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-expr.h"
50 #include "is-a.h"
51 #include "gimple.h"
52 #include "gimple-iterator.h"
53 #include "gimple-ssa.h"
54 #include "tree-cfg.h"
55 #include "tree-phinodes.h"
56 #include "ssa-iterators.h"
57 #include "tree-iterator.h"
58 #include "alloc-pool.h"
59 #include "tree-pass.h"
60 #include "flags.h"
61 #include "cfgloop.h"
62 #include "params.h"
64 /* TODO:
65 1. Sinking store only using scalar promotion (IE without moving the RHS):
67 *q = p;
68 p = p + 1;
69 if (something)
70 *q = <not p>;
71 else
72 y = *q;
75 should become
76 sinktemp = p;
77 p = p + 1;
78 if (something)
79 *q = <not p>;
80 else
82 *q = sinktemp;
83 y = *q
85 Store copy propagation will take care of the store elimination above.
88 2. Sinking using Partial Dead Code Elimination. */
91 static struct
93 /* The number of statements sunk down the flowgraph by code sinking. */
94 int sunk;
96 } sink_stats;
99 /* Given a PHI, and one of its arguments (DEF), find the edge for
100 that argument and return it. If the argument occurs twice in the PHI node,
101 we return NULL. */
103 static basic_block
104 find_bb_for_arg (gphi *phi, tree def)
106 size_t i;
107 bool foundone = false;
108 basic_block result = NULL;
109 for (i = 0; i < gimple_phi_num_args (phi); i++)
110 if (PHI_ARG_DEF (phi, i) == def)
112 if (foundone)
113 return NULL;
114 foundone = true;
115 result = gimple_phi_arg_edge (phi, i)->src;
117 return result;
120 /* When the first immediate use is in a statement, then return true if all
121 immediate uses in IMM are in the same statement.
122 We could also do the case where the first immediate use is in a phi node,
123 and all the other uses are in phis in the same basic block, but this
124 requires some expensive checking later (you have to make sure no def/vdef
125 in the statement occurs for multiple edges in the various phi nodes it's
126 used in, so that you only have one place you can sink it to. */
128 static bool
129 all_immediate_uses_same_place (def_operand_p def_p)
131 tree var = DEF_FROM_PTR (def_p);
132 imm_use_iterator imm_iter;
133 use_operand_p use_p;
135 gimple firstuse = NULL;
136 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
138 if (is_gimple_debug (USE_STMT (use_p)))
139 continue;
140 if (firstuse == NULL)
141 firstuse = USE_STMT (use_p);
142 else
143 if (firstuse != USE_STMT (use_p))
144 return false;
147 return true;
150 /* Find the nearest common dominator of all of the immediate uses in IMM. */
152 static basic_block
153 nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
155 tree var = DEF_FROM_PTR (def_p);
156 bitmap blocks = BITMAP_ALLOC (NULL);
157 basic_block commondom;
158 unsigned int j;
159 bitmap_iterator bi;
160 imm_use_iterator imm_iter;
161 use_operand_p use_p;
163 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
165 gimple usestmt = USE_STMT (use_p);
166 basic_block useblock;
168 if (gphi *phi = dyn_cast <gphi *> (usestmt))
170 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
172 useblock = gimple_phi_arg_edge (phi, idx)->src;
174 else if (is_gimple_debug (usestmt))
176 *debug_stmts = true;
177 continue;
179 else
181 useblock = gimple_bb (usestmt);
184 /* Short circuit. Nothing dominates the entry block. */
185 if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
187 BITMAP_FREE (blocks);
188 return NULL;
190 bitmap_set_bit (blocks, useblock->index);
192 commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
193 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
194 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
195 BASIC_BLOCK_FOR_FN (cfun, j));
196 BITMAP_FREE (blocks);
197 return commondom;
200 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
201 tree, return the best basic block between them (inclusive) to place
202 statements.
204 We want the most control dependent block in the shallowest loop nest.
206 If the resulting block is in a shallower loop nest, then use it. Else
207 only use the resulting block if it has significantly lower execution
208 frequency than EARLY_BB to avoid gratutious statement movement. We
209 consider statements with VOPS more desirable to move.
211 This pass would obviously benefit from PDO as it utilizes block
212 frequencies. It would also benefit from recomputing frequencies
213 if profile data is not available since frequencies often get out
214 of sync with reality. */
216 static basic_block
217 select_best_block (basic_block early_bb,
218 basic_block late_bb,
219 gimple stmt)
221 basic_block best_bb = late_bb;
222 basic_block temp_bb = late_bb;
223 int threshold;
225 while (temp_bb != early_bb)
227 /* If we've moved into a lower loop nest, then that becomes
228 our best block. */
229 if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
230 best_bb = temp_bb;
232 /* Walk up the dominator tree, hopefully we'll find a shallower
233 loop nest. */
234 temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
237 /* If we found a shallower loop nest, then we always consider that
238 a win. This will always give us the most control dependent block
239 within that loop nest. */
240 if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
241 return best_bb;
243 /* Get the sinking threshold. If the statement to be moved has memory
244 operands, then increase the threshold by 7% as those are even more
245 profitable to avoid, clamping at 100%. */
246 threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
247 if (gimple_vuse (stmt) || gimple_vdef (stmt))
249 threshold += 7;
250 if (threshold > 100)
251 threshold = 100;
254 /* If BEST_BB is at the same nesting level, then require it to have
255 significantly lower execution frequency to avoid gratutious movement. */
256 if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
257 && best_bb->frequency < (early_bb->frequency * threshold / 100.0))
258 return best_bb;
260 /* No better block found, so return EARLY_BB, which happens to be the
261 statement's original block. */
262 return early_bb;
265 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
266 determine the location to sink the statement to, if any.
267 Returns true if there is such location; in that case, TOGSI points to the
268 statement before that STMT should be moved. */
270 static bool
271 statement_sink_location (gimple stmt, basic_block frombb,
272 gimple_stmt_iterator *togsi)
274 gimple use;
275 use_operand_p one_use = NULL_USE_OPERAND_P;
276 basic_block sinkbb;
277 use_operand_p use_p;
278 def_operand_p def_p;
279 ssa_op_iter iter;
280 imm_use_iterator imm_iter;
282 /* We only can sink assignments. */
283 if (!is_gimple_assign (stmt))
284 return false;
286 /* We only can sink stmts with a single definition. */
287 def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
288 if (def_p == NULL_DEF_OPERAND_P)
289 return false;
291 /* Return if there are no immediate uses of this stmt. */
292 if (has_zero_uses (DEF_FROM_PTR (def_p)))
293 return false;
295 /* There are a few classes of things we can't or don't move, some because we
296 don't have code to handle it, some because it's not profitable and some
297 because it's not legal.
299 We can't sink things that may be global stores, at least not without
300 calculating a lot more information, because we may cause it to no longer
301 be seen by an external routine that needs it depending on where it gets
302 moved to.
304 We can't sink statements that end basic blocks without splitting the
305 incoming edge for the sink location to place it there.
307 We can't sink statements that have volatile operands.
309 We don't want to sink dead code, so anything with 0 immediate uses is not
310 sunk.
312 Don't sink BLKmode assignments if current function has any local explicit
313 register variables, as BLKmode assignments may involve memcpy or memset
314 calls or, on some targets, inline expansion thereof that sometimes need
315 to use specific hard registers.
318 if (stmt_ends_bb_p (stmt)
319 || gimple_has_side_effects (stmt)
320 || gimple_has_volatile_ops (stmt)
321 || (cfun->has_local_explicit_reg_vars
322 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
323 return false;
325 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
326 return false;
328 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
330 tree use = USE_FROM_PTR (use_p);
331 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
332 return false;
335 use = NULL;
337 /* If stmt is a store the one and only use needs to be the VOP
338 merging PHI node. */
339 if (virtual_operand_p (DEF_FROM_PTR (def_p)))
341 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
343 gimple use_stmt = USE_STMT (use_p);
345 /* A killing definition is not a use. */
346 if ((gimple_has_lhs (use_stmt)
347 && operand_equal_p (gimple_assign_lhs (stmt),
348 gimple_get_lhs (use_stmt), 0))
349 || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt)))
351 /* If use_stmt is or might be a nop assignment then USE_STMT
352 acts as a use as well as definition. */
353 if (stmt != use_stmt
354 && ref_maybe_used_by_stmt_p (use_stmt,
355 gimple_assign_lhs (stmt)))
356 return false;
357 continue;
360 if (gimple_code (use_stmt) != GIMPLE_PHI)
361 return false;
363 if (use
364 && use != use_stmt)
365 return false;
367 use = use_stmt;
369 if (!use)
370 return false;
372 /* If all the immediate uses are not in the same place, find the nearest
373 common dominator of all the immediate uses. For PHI nodes, we have to
374 find the nearest common dominator of all of the predecessor blocks, since
375 that is where insertion would have to take place. */
376 else if (gimple_vuse (stmt)
377 || !all_immediate_uses_same_place (def_p))
379 bool debug_stmts = false;
380 basic_block commondom = nearest_common_dominator_of_uses (def_p,
381 &debug_stmts);
383 if (commondom == frombb)
384 return false;
386 /* If this is a load then do not sink past any stores.
387 ??? This is overly simple but cheap. We basically look
388 for an existing load with the same VUSE in the path to one
389 of the sink candidate blocks and we adjust commondom to the
390 nearest to commondom. */
391 if (gimple_vuse (stmt))
393 /* Do not sink loads from hard registers. */
394 if (gimple_assign_single_p (stmt)
395 && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
396 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
397 return false;
399 imm_use_iterator imm_iter;
400 use_operand_p use_p;
401 basic_block found = NULL;
402 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt))
404 gimple use_stmt = USE_STMT (use_p);
405 basic_block bb = gimple_bb (use_stmt);
406 /* For PHI nodes the block we know sth about
407 is the incoming block with the use. */
408 if (gimple_code (use_stmt) == GIMPLE_PHI)
409 bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
410 /* Any dominator of commondom would be ok with
411 adjusting commondom to that block. */
412 bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom);
413 if (!found)
414 found = bb;
415 else if (dominated_by_p (CDI_DOMINATORS, bb, found))
416 found = bb;
417 /* If we can't improve, stop. */
418 if (found == commondom)
419 break;
421 commondom = found;
422 if (commondom == frombb)
423 return false;
426 /* Our common dominator has to be dominated by frombb in order to be a
427 trivially safe place to put this statement, since it has multiple
428 uses. */
429 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
430 return false;
432 commondom = select_best_block (frombb, commondom, stmt);
434 if (commondom == frombb)
435 return false;
437 *togsi = gsi_after_labels (commondom);
439 return true;
441 else
443 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
445 if (is_gimple_debug (USE_STMT (one_use)))
446 continue;
447 break;
449 use = USE_STMT (one_use);
451 if (gimple_code (use) != GIMPLE_PHI)
453 sinkbb = gimple_bb (use);
454 sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
456 if (sinkbb == frombb)
457 return false;
459 *togsi = gsi_for_stmt (use);
461 return true;
465 sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
467 /* This can happen if there are multiple uses in a PHI. */
468 if (!sinkbb)
469 return false;
471 sinkbb = select_best_block (frombb, sinkbb, stmt);
472 if (!sinkbb || sinkbb == frombb)
473 return false;
475 /* If the latch block is empty, don't make it non-empty by sinking
476 something into it. */
477 if (sinkbb == frombb->loop_father->latch
478 && empty_block_p (sinkbb))
479 return false;
481 *togsi = gsi_after_labels (sinkbb);
483 return true;
486 /* Perform code sinking on BB */
488 static void
489 sink_code_in_bb (basic_block bb)
491 basic_block son;
492 gimple_stmt_iterator gsi;
493 edge_iterator ei;
494 edge e;
495 bool last = true;
497 /* If this block doesn't dominate anything, there can't be any place to sink
498 the statements to. */
499 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
500 goto earlyout;
502 /* We can't move things across abnormal edges, so don't try. */
503 FOR_EACH_EDGE (e, ei, bb->succs)
504 if (e->flags & EDGE_ABNORMAL)
505 goto earlyout;
507 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
509 gimple stmt = gsi_stmt (gsi);
510 gimple_stmt_iterator togsi;
512 if (!statement_sink_location (stmt, bb, &togsi))
514 if (!gsi_end_p (gsi))
515 gsi_prev (&gsi);
516 last = false;
517 continue;
519 if (dump_file)
521 fprintf (dump_file, "Sinking ");
522 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
523 fprintf (dump_file, " from bb %d to bb %d\n",
524 bb->index, (gsi_bb (togsi))->index);
527 /* Update virtual operands of statements in the path we
528 do not sink to. */
529 if (gimple_vdef (stmt))
531 imm_use_iterator iter;
532 use_operand_p use_p;
533 gimple vuse_stmt;
535 FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
536 if (gimple_code (vuse_stmt) != GIMPLE_PHI)
537 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
538 SET_USE (use_p, gimple_vuse (stmt));
541 /* If this is the end of the basic block, we need to insert at the end
542 of the basic block. */
543 if (gsi_end_p (togsi))
544 gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
545 else
546 gsi_move_before (&gsi, &togsi);
548 sink_stats.sunk++;
550 /* If we've just removed the last statement of the BB, the
551 gsi_end_p() test below would fail, but gsi_prev() would have
552 succeeded, and we want it to succeed. So we keep track of
553 whether we're at the last statement and pick up the new last
554 statement. */
555 if (last)
557 gsi = gsi_last_bb (bb);
558 continue;
561 last = false;
562 if (!gsi_end_p (gsi))
563 gsi_prev (&gsi);
566 earlyout:
567 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
568 son;
569 son = next_dom_son (CDI_POST_DOMINATORS, son))
571 sink_code_in_bb (son);
575 /* Perform code sinking.
576 This moves code down the flowgraph when we know it would be
577 profitable to do so, or it wouldn't increase the number of
578 executions of the statement.
580 IE given
582 a_1 = b + c;
583 if (<something>)
586 else
588 foo (&b, &c);
589 a_5 = b + c;
591 a_6 = PHI (a_5, a_1);
592 USE a_6.
594 we'll transform this into:
596 if (<something>)
598 a_1 = b + c;
600 else
602 foo (&b, &c);
603 a_5 = b + c;
605 a_6 = PHI (a_5, a_1);
606 USE a_6.
608 Note that this reduces the number of computations of a = b + c to 1
609 when we take the else edge, instead of 2.
611 namespace {
613 const pass_data pass_data_sink_code =
615 GIMPLE_PASS, /* type */
616 "sink", /* name */
617 OPTGROUP_NONE, /* optinfo_flags */
618 TV_TREE_SINK, /* tv_id */
619 /* PROP_no_crit_edges is ensured by running split_critical_edges in
620 pass_data_sink_code::execute (). */
621 ( PROP_cfg | PROP_ssa ), /* properties_required */
622 0, /* properties_provided */
623 0, /* properties_destroyed */
624 0, /* todo_flags_start */
625 TODO_update_ssa, /* todo_flags_finish */
628 class pass_sink_code : public gimple_opt_pass
630 public:
631 pass_sink_code (gcc::context *ctxt)
632 : gimple_opt_pass (pass_data_sink_code, ctxt)
635 /* opt_pass methods: */
636 virtual bool gate (function *) { return flag_tree_sink != 0; }
637 virtual unsigned int execute (function *);
639 }; // class pass_sink_code
641 unsigned int
642 pass_sink_code::execute (function *fun)
644 loop_optimizer_init (LOOPS_NORMAL);
645 split_critical_edges ();
646 connect_infinite_loops_to_exit ();
647 memset (&sink_stats, 0, sizeof (sink_stats));
648 calculate_dominance_info (CDI_DOMINATORS);
649 calculate_dominance_info (CDI_POST_DOMINATORS);
650 sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
651 statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
652 free_dominance_info (CDI_POST_DOMINATORS);
653 remove_fake_exit_edges ();
654 loop_optimizer_finalize ();
656 return 0;
659 } // anon namespace
661 gimple_opt_pass *
662 make_pass_sink_code (gcc::context *ctxt)
664 return new pass_sink_code (ctxt);