Daily bump.
[official-gcc.git] / gcc / tree-ssa-sink.c
blobc6d871209bea4b3ae13cec202eff4ed93b2a3345
1 /* Code sinking for trees
2 Copyright (C) 2001-2014 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 "tree.h"
26 #include "stor-layout.h"
27 #include "predict.h"
28 #include "vec.h"
29 #include "hashtab.h"
30 #include "hash-set.h"
31 #include "machmode.h"
32 #include "hard-reg-set.h"
33 #include "input.h"
34 #include "function.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "cfganal.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
40 #include "tree-inline.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-expr.h"
44 #include "is-a.h"
45 #include "gimple.h"
46 #include "gimple-iterator.h"
47 #include "gimple-ssa.h"
48 #include "tree-cfg.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "tree-iterator.h"
52 #include "alloc-pool.h"
53 #include "tree-pass.h"
54 #include "flags.h"
55 #include "cfgloop.h"
56 #include "params.h"
58 /* TODO:
59 1. Sinking store only using scalar promotion (IE without moving the RHS):
61 *q = p;
62 p = p + 1;
63 if (something)
64 *q = <not p>;
65 else
66 y = *q;
69 should become
70 sinktemp = p;
71 p = p + 1;
72 if (something)
73 *q = <not p>;
74 else
76 *q = sinktemp;
77 y = *q
79 Store copy propagation will take care of the store elimination above.
82 2. Sinking using Partial Dead Code Elimination. */
85 static struct
87 /* The number of statements sunk down the flowgraph by code sinking. */
88 int sunk;
90 } sink_stats;
93 /* Given a PHI, and one of its arguments (DEF), find the edge for
94 that argument and return it. If the argument occurs twice in the PHI node,
95 we return NULL. */
97 static basic_block
98 find_bb_for_arg (gphi *phi, tree def)
100 size_t i;
101 bool foundone = false;
102 basic_block result = NULL;
103 for (i = 0; i < gimple_phi_num_args (phi); i++)
104 if (PHI_ARG_DEF (phi, i) == def)
106 if (foundone)
107 return NULL;
108 foundone = true;
109 result = gimple_phi_arg_edge (phi, i)->src;
111 return result;
114 /* When the first immediate use is in a statement, then return true if all
115 immediate uses in IMM are in the same statement.
116 We could also do the case where the first immediate use is in a phi node,
117 and all the other uses are in phis in the same basic block, but this
118 requires some expensive checking later (you have to make sure no def/vdef
119 in the statement occurs for multiple edges in the various phi nodes it's
120 used in, so that you only have one place you can sink it to. */
122 static bool
123 all_immediate_uses_same_place (def_operand_p def_p)
125 tree var = DEF_FROM_PTR (def_p);
126 imm_use_iterator imm_iter;
127 use_operand_p use_p;
129 gimple firstuse = NULL;
130 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
132 if (is_gimple_debug (USE_STMT (use_p)))
133 continue;
134 if (firstuse == NULL)
135 firstuse = USE_STMT (use_p);
136 else
137 if (firstuse != USE_STMT (use_p))
138 return false;
141 return true;
144 /* Find the nearest common dominator of all of the immediate uses in IMM. */
146 static basic_block
147 nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
149 tree var = DEF_FROM_PTR (def_p);
150 bitmap blocks = BITMAP_ALLOC (NULL);
151 basic_block commondom;
152 unsigned int j;
153 bitmap_iterator bi;
154 imm_use_iterator imm_iter;
155 use_operand_p use_p;
157 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
159 gimple usestmt = USE_STMT (use_p);
160 basic_block useblock;
162 if (gphi *phi = dyn_cast <gphi *> (usestmt))
164 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
166 useblock = gimple_phi_arg_edge (phi, idx)->src;
168 else if (is_gimple_debug (usestmt))
170 *debug_stmts = true;
171 continue;
173 else
175 useblock = gimple_bb (usestmt);
178 /* Short circuit. Nothing dominates the entry block. */
179 if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
181 BITMAP_FREE (blocks);
182 return NULL;
184 bitmap_set_bit (blocks, useblock->index);
186 commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
187 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
188 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
189 BASIC_BLOCK_FOR_FN (cfun, j));
190 BITMAP_FREE (blocks);
191 return commondom;
194 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
195 tree, return the best basic block between them (inclusive) to place
196 statements.
198 We want the most control dependent block in the shallowest loop nest.
200 If the resulting block is in a shallower loop nest, then use it. Else
201 only use the resulting block if it has significantly lower execution
202 frequency than EARLY_BB to avoid gratutious statement movement. We
203 consider statements with VOPS more desirable to move.
205 This pass would obviously benefit from PDO as it utilizes block
206 frequencies. It would also benefit from recomputing frequencies
207 if profile data is not available since frequencies often get out
208 of sync with reality. */
210 static basic_block
211 select_best_block (basic_block early_bb,
212 basic_block late_bb,
213 gimple stmt)
215 basic_block best_bb = late_bb;
216 basic_block temp_bb = late_bb;
217 int threshold;
219 while (temp_bb != early_bb)
221 /* If we've moved into a lower loop nest, then that becomes
222 our best block. */
223 if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
224 best_bb = temp_bb;
226 /* Walk up the dominator tree, hopefully we'll find a shallower
227 loop nest. */
228 temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
231 /* If we found a shallower loop nest, then we always consider that
232 a win. This will always give us the most control dependent block
233 within that loop nest. */
234 if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
235 return best_bb;
237 /* Get the sinking threshold. If the statement to be moved has memory
238 operands, then increase the threshold by 7% as those are even more
239 profitable to avoid, clamping at 100%. */
240 threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
241 if (gimple_vuse (stmt) || gimple_vdef (stmt))
243 threshold += 7;
244 if (threshold > 100)
245 threshold = 100;
248 /* If BEST_BB is at the same nesting level, then require it to have
249 significantly lower execution frequency to avoid gratutious movement. */
250 if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
251 && best_bb->frequency < (early_bb->frequency * threshold / 100.0))
252 return best_bb;
254 /* No better block found, so return EARLY_BB, which happens to be the
255 statement's original block. */
256 return early_bb;
259 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
260 determine the location to sink the statement to, if any.
261 Returns true if there is such location; in that case, TOGSI points to the
262 statement before that STMT should be moved. */
264 static bool
265 statement_sink_location (gimple stmt, basic_block frombb,
266 gimple_stmt_iterator *togsi)
268 gimple use;
269 use_operand_p one_use = NULL_USE_OPERAND_P;
270 basic_block sinkbb;
271 use_operand_p use_p;
272 def_operand_p def_p;
273 ssa_op_iter iter;
274 imm_use_iterator imm_iter;
276 /* We only can sink assignments. */
277 if (!is_gimple_assign (stmt))
278 return false;
280 /* We only can sink stmts with a single definition. */
281 def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
282 if (def_p == NULL_DEF_OPERAND_P)
283 return false;
285 /* Return if there are no immediate uses of this stmt. */
286 if (has_zero_uses (DEF_FROM_PTR (def_p)))
287 return false;
289 /* There are a few classes of things we can't or don't move, some because we
290 don't have code to handle it, some because it's not profitable and some
291 because it's not legal.
293 We can't sink things that may be global stores, at least not without
294 calculating a lot more information, because we may cause it to no longer
295 be seen by an external routine that needs it depending on where it gets
296 moved to.
298 We can't sink statements that end basic blocks without splitting the
299 incoming edge for the sink location to place it there.
301 We can't sink statements that have volatile operands.
303 We don't want to sink dead code, so anything with 0 immediate uses is not
304 sunk.
306 Don't sink BLKmode assignments if current function has any local explicit
307 register variables, as BLKmode assignments may involve memcpy or memset
308 calls or, on some targets, inline expansion thereof that sometimes need
309 to use specific hard registers.
312 if (stmt_ends_bb_p (stmt)
313 || gimple_has_side_effects (stmt)
314 || gimple_has_volatile_ops (stmt)
315 || (cfun->has_local_explicit_reg_vars
316 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
317 return false;
319 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
320 return false;
322 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
324 tree use = USE_FROM_PTR (use_p);
325 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
326 return false;
329 use = NULL;
331 /* If stmt is a store the one and only use needs to be the VOP
332 merging PHI node. */
333 if (virtual_operand_p (DEF_FROM_PTR (def_p)))
335 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
337 gimple use_stmt = USE_STMT (use_p);
339 /* A killing definition is not a use. */
340 if ((gimple_has_lhs (use_stmt)
341 && operand_equal_p (gimple_assign_lhs (stmt),
342 gimple_get_lhs (use_stmt), 0))
343 || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt)))
345 /* If use_stmt is or might be a nop assignment then USE_STMT
346 acts as a use as well as definition. */
347 if (stmt != use_stmt
348 && ref_maybe_used_by_stmt_p (use_stmt,
349 gimple_assign_lhs (stmt)))
350 return false;
351 continue;
354 if (gimple_code (use_stmt) != GIMPLE_PHI)
355 return false;
357 if (use
358 && use != use_stmt)
359 return false;
361 use = use_stmt;
363 if (!use)
364 return false;
366 /* If all the immediate uses are not in the same place, find the nearest
367 common dominator of all the immediate uses. For PHI nodes, we have to
368 find the nearest common dominator of all of the predecessor blocks, since
369 that is where insertion would have to take place. */
370 else if (gimple_vuse (stmt)
371 || !all_immediate_uses_same_place (def_p))
373 bool debug_stmts = false;
374 basic_block commondom = nearest_common_dominator_of_uses (def_p,
375 &debug_stmts);
377 if (commondom == frombb)
378 return false;
380 /* If this is a load then do not sink past any stores.
381 ??? This is overly simple but cheap. We basically look
382 for an existing load with the same VUSE in the path to one
383 of the sink candidate blocks and we adjust commondom to the
384 nearest to commondom. */
385 if (gimple_vuse (stmt))
387 /* Do not sink loads from hard registers. */
388 if (gimple_assign_single_p (stmt)
389 && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
390 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
391 return false;
393 imm_use_iterator imm_iter;
394 use_operand_p use_p;
395 basic_block found = NULL;
396 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt))
398 gimple use_stmt = USE_STMT (use_p);
399 basic_block bb = gimple_bb (use_stmt);
400 /* For PHI nodes the block we know sth about
401 is the incoming block with the use. */
402 if (gimple_code (use_stmt) == GIMPLE_PHI)
403 bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
404 /* Any dominator of commondom would be ok with
405 adjusting commondom to that block. */
406 bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom);
407 if (!found)
408 found = bb;
409 else if (dominated_by_p (CDI_DOMINATORS, bb, found))
410 found = bb;
411 /* If we can't improve, stop. */
412 if (found == commondom)
413 break;
415 commondom = found;
416 if (commondom == frombb)
417 return false;
420 /* Our common dominator has to be dominated by frombb in order to be a
421 trivially safe place to put this statement, since it has multiple
422 uses. */
423 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
424 return false;
426 commondom = select_best_block (frombb, commondom, stmt);
428 if (commondom == frombb)
429 return false;
431 *togsi = gsi_after_labels (commondom);
433 return true;
435 else
437 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
439 if (is_gimple_debug (USE_STMT (one_use)))
440 continue;
441 break;
443 use = USE_STMT (one_use);
445 if (gimple_code (use) != GIMPLE_PHI)
447 sinkbb = gimple_bb (use);
448 sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
450 if (sinkbb == frombb)
451 return false;
453 *togsi = gsi_for_stmt (use);
455 return true;
459 sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
461 /* This can happen if there are multiple uses in a PHI. */
462 if (!sinkbb)
463 return false;
465 sinkbb = select_best_block (frombb, sinkbb, stmt);
466 if (!sinkbb || sinkbb == frombb)
467 return false;
469 /* If the latch block is empty, don't make it non-empty by sinking
470 something into it. */
471 if (sinkbb == frombb->loop_father->latch
472 && empty_block_p (sinkbb))
473 return false;
475 *togsi = gsi_after_labels (sinkbb);
477 return true;
480 /* Perform code sinking on BB */
482 static void
483 sink_code_in_bb (basic_block bb)
485 basic_block son;
486 gimple_stmt_iterator gsi;
487 edge_iterator ei;
488 edge e;
489 bool last = true;
491 /* If this block doesn't dominate anything, there can't be any place to sink
492 the statements to. */
493 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
494 goto earlyout;
496 /* We can't move things across abnormal edges, so don't try. */
497 FOR_EACH_EDGE (e, ei, bb->succs)
498 if (e->flags & EDGE_ABNORMAL)
499 goto earlyout;
501 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
503 gimple stmt = gsi_stmt (gsi);
504 gimple_stmt_iterator togsi;
506 if (!statement_sink_location (stmt, bb, &togsi))
508 if (!gsi_end_p (gsi))
509 gsi_prev (&gsi);
510 last = false;
511 continue;
513 if (dump_file)
515 fprintf (dump_file, "Sinking ");
516 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
517 fprintf (dump_file, " from bb %d to bb %d\n",
518 bb->index, (gsi_bb (togsi))->index);
521 /* Update virtual operands of statements in the path we
522 do not sink to. */
523 if (gimple_vdef (stmt))
525 imm_use_iterator iter;
526 use_operand_p use_p;
527 gimple vuse_stmt;
529 FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
530 if (gimple_code (vuse_stmt) != GIMPLE_PHI)
531 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
532 SET_USE (use_p, gimple_vuse (stmt));
535 /* If this is the end of the basic block, we need to insert at the end
536 of the basic block. */
537 if (gsi_end_p (togsi))
538 gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
539 else
540 gsi_move_before (&gsi, &togsi);
542 sink_stats.sunk++;
544 /* If we've just removed the last statement of the BB, the
545 gsi_end_p() test below would fail, but gsi_prev() would have
546 succeeded, and we want it to succeed. So we keep track of
547 whether we're at the last statement and pick up the new last
548 statement. */
549 if (last)
551 gsi = gsi_last_bb (bb);
552 continue;
555 last = false;
556 if (!gsi_end_p (gsi))
557 gsi_prev (&gsi);
560 earlyout:
561 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
562 son;
563 son = next_dom_son (CDI_POST_DOMINATORS, son))
565 sink_code_in_bb (son);
569 /* Perform code sinking.
570 This moves code down the flowgraph when we know it would be
571 profitable to do so, or it wouldn't increase the number of
572 executions of the statement.
574 IE given
576 a_1 = b + c;
577 if (<something>)
580 else
582 foo (&b, &c);
583 a_5 = b + c;
585 a_6 = PHI (a_5, a_1);
586 USE a_6.
588 we'll transform this into:
590 if (<something>)
592 a_1 = b + c;
594 else
596 foo (&b, &c);
597 a_5 = b + c;
599 a_6 = PHI (a_5, a_1);
600 USE a_6.
602 Note that this reduces the number of computations of a = b + c to 1
603 when we take the else edge, instead of 2.
605 namespace {
607 const pass_data pass_data_sink_code =
609 GIMPLE_PASS, /* type */
610 "sink", /* name */
611 OPTGROUP_NONE, /* optinfo_flags */
612 TV_TREE_SINK, /* tv_id */
613 /* PROP_no_crit_edges is ensured by running split_critical_edges in
614 pass_data_sink_code::execute (). */
615 ( PROP_cfg | PROP_ssa ), /* properties_required */
616 0, /* properties_provided */
617 0, /* properties_destroyed */
618 0, /* todo_flags_start */
619 TODO_update_ssa, /* todo_flags_finish */
622 class pass_sink_code : public gimple_opt_pass
624 public:
625 pass_sink_code (gcc::context *ctxt)
626 : gimple_opt_pass (pass_data_sink_code, ctxt)
629 /* opt_pass methods: */
630 virtual bool gate (function *) { return flag_tree_sink != 0; }
631 virtual unsigned int execute (function *);
633 }; // class pass_sink_code
635 unsigned int
636 pass_sink_code::execute (function *fun)
638 loop_optimizer_init (LOOPS_NORMAL);
639 split_critical_edges ();
640 connect_infinite_loops_to_exit ();
641 memset (&sink_stats, 0, sizeof (sink_stats));
642 calculate_dominance_info (CDI_DOMINATORS);
643 calculate_dominance_info (CDI_POST_DOMINATORS);
644 sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
645 statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
646 free_dominance_info (CDI_POST_DOMINATORS);
647 remove_fake_exit_edges ();
648 loop_optimizer_finalize ();
650 return 0;
653 } // anon namespace
655 gimple_opt_pass *
656 make_pass_sink_code (gcc::context *ctxt)
658 return new pass_sink_code (ctxt);