1 /* Code sinking for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2007 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)
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/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "diagnostic.h"
29 #include "tree-inline.h"
30 #include "tree-flow.h"
31 #include "tree-gimple.h"
32 #include "tree-dump.h"
36 #include "tree-iterator.h"
38 #include "alloc-pool.h"
39 #include "tree-pass.h"
42 #include "langhooks.h"
46 1. Sinking store only using scalar promotion (IE without moving the RHS):
66 Store copy propagation will take care of the store elimination above.
69 2. Sinking using Partial Dead Code Elimination. */
74 /* The number of statements sunk down the flowgraph by code sinking. */
80 /* Given a PHI, and one of its arguments (DEF), find the edge for
81 that argument and return it. If the argument occurs twice in the PHI node,
85 find_bb_for_arg (tree phi, tree def)
88 bool foundone = false;
89 basic_block result = NULL;
90 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
91 if (PHI_ARG_DEF (phi, i) == def)
96 result = PHI_ARG_EDGE (phi, i)->src;
101 /* When the first immediate use is in a statement, then return true if all
102 immediate uses in IMM are in the same statement.
103 We could also do the case where the first immediate use is in a phi node,
104 and all the other uses are in phis in the same basic block, but this
105 requires some expensive checking later (you have to make sure no def/vdef
106 in the statement occurs for multiple edges in the various phi nodes it's
107 used in, so that you only have one place you can sink it to. */
110 all_immediate_uses_same_place (tree stmt)
112 tree firstuse = NULL_TREE;
114 imm_use_iterator imm_iter;
118 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
120 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
122 if (firstuse == NULL_TREE)
123 firstuse = USE_STMT (use_p);
125 if (firstuse != USE_STMT (use_p))
133 /* Some global stores don't necessarily have VDEF's of global variables,
134 but we still must avoid moving them around. */
137 is_hidden_global_store (tree stmt)
139 /* Check virtual definitions. If we get here, the only virtual
140 definitions we should see are those generated by assignment
142 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
146 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
148 /* Note that we must not check the individual virtual operands
149 here. In particular, if this is an aliased store, we could
150 end up with something like the following (SSA notation
151 redacted for brevity):
156 p_1 = (i_2 > 3) ? &x : p;
164 Notice that the store to '*p_1' should be preserved, if we
165 were to check the virtual definitions in that store, we would
166 not mark it needed. This is because 'x' is not a global
169 Therefore, we check the base address of the LHS. If the
170 address is a pointer, we check if its name tag or symbol tag is
171 a global variable. Otherwise, we check if the base variable
173 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
174 if (REFERENCE_CLASS_P (lhs))
175 lhs = get_base_address (lhs);
177 if (lhs == NULL_TREE)
179 /* If LHS is NULL, it means that we couldn't get the base
180 address of the reference. In which case, we should not
184 else if (DECL_P (lhs))
186 /* If the store is to a global symbol, we need to keep it. */
187 if (is_global_var (lhs))
191 else if (INDIRECT_REF_P (lhs))
192 return may_point_to_global_var (TREE_OPERAND (lhs, 0));
200 /* Find the nearest common dominator of all of the immediate uses in IMM. */
203 nearest_common_dominator_of_uses (tree stmt)
205 bitmap blocks = BITMAP_ALLOC (NULL);
206 basic_block commondom;
210 imm_use_iterator imm_iter;
214 bitmap_clear (blocks);
215 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
217 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
219 tree usestmt = USE_STMT (use_p);
220 basic_block useblock;
222 if (TREE_CODE (usestmt) == PHI_NODE)
224 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
226 useblock = PHI_ARG_EDGE (usestmt, idx)->src;
230 useblock = bb_for_stmt (usestmt);
233 /* Short circuit. Nothing dominates the entry block. */
234 if (useblock == ENTRY_BLOCK_PTR)
236 BITMAP_FREE (blocks);
239 bitmap_set_bit (blocks, useblock->index);
242 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
243 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
244 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
246 BITMAP_FREE (blocks);
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, TOBB is set to the
253 basic block of the location, and TOBSI points to the statement before
254 that STMT should be moved. */
257 statement_sink_location (tree stmt, basic_block frombb, basic_block *tobb,
258 block_stmt_iterator *tobsi)
261 use_operand_p one_use = NULL_USE_OPERAND_P;
268 imm_use_iterator imm_iter;
270 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
272 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
276 if (one_use != NULL_USE_OPERAND_P)
280 /* Return if there are no immediate uses of this stmt. */
281 if (one_use == NULL_USE_OPERAND_P)
284 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
286 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
288 /* There are a few classes of things we can't or don't move, some because we
289 don't have code to handle it, some because it's not profitable and some
290 because it's not legal.
292 We can't sink things that may be global stores, at least not without
293 calculating a lot more information, because we may cause it to no longer
294 be seen by an external routine that needs it depending on where it gets
297 We don't want to sink loads from memory.
299 We can't sink statements that end basic blocks without splitting the
300 incoming edge for the sink location to place it there.
302 We can't sink statements that have volatile operands.
304 We don't want to sink dead code, so anything with 0 immediate uses is not
308 ann = stmt_ann (stmt);
309 if (stmt_ends_bb_p (stmt)
310 || TREE_SIDE_EFFECTS (rhs)
311 || TREE_CODE (rhs) == EXC_PTR_EXPR
312 || TREE_CODE (rhs) == FILTER_EXPR
313 || is_hidden_global_store (stmt)
314 || ann->has_volatile_ops
315 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
318 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
320 tree def = DEF_FROM_PTR (def_p);
321 if (is_global_var (SSA_NAME_VAR (def))
322 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
326 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
328 tree use = USE_FROM_PTR (use_p);
329 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
333 /* If all the immediate uses are not in the same place, find the nearest
334 common dominator of all the immediate uses. For PHI nodes, we have to
335 find the nearest common dominator of all of the predecessor blocks, since
336 that is where insertion would have to take place. */
337 if (!all_immediate_uses_same_place (stmt))
339 basic_block commondom = nearest_common_dominator_of_uses (stmt);
341 if (commondom == frombb)
344 /* Our common dominator has to be dominated by frombb in order to be a
345 trivially safe place to put this statement, since it has multiple
347 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
350 /* It doesn't make sense to move to a dominator that post-dominates
351 frombb, because it means we've just moved it into a path that always
352 executes if frombb executes, instead of reducing the number of
354 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
356 if (dump_file && (dump_flags & TDF_DETAILS))
357 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
361 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
363 if (dump_file && (dump_flags & TDF_DETAILS))
365 fprintf (dump_file, "Common dominator of all uses is %d\n",
369 *tobsi = bsi_after_labels (commondom);
373 use = USE_STMT (one_use);
374 if (TREE_CODE (use) != PHI_NODE)
376 sinkbb = bb_for_stmt (use);
377 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
378 || sinkbb->loop_father != frombb->loop_father)
381 *tobsi = bsi_for_stmt (use);
385 /* Note that at this point, all uses must be in the same statement, so it
386 doesn't matter which def op we choose, pick the first one. */
387 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
390 sinkbb = find_bb_for_arg (use, def);
394 /* This will happen when you have
395 a_3 = PHI <a_13, a_26>
399 If the use is a phi, and is in the same bb as the def,
402 if (bb_for_stmt (use) == frombb)
404 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
405 || sinkbb->loop_father != frombb->loop_father)
409 *tobsi = bsi_after_labels (sinkbb);
414 /* Perform code sinking on BB */
417 sink_code_in_bb (basic_block bb)
420 block_stmt_iterator bsi;
425 /* If this block doesn't dominate anything, there can't be any place to sink
426 the statements to. */
427 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
430 /* We can't move things across abnormal edges, so don't try. */
431 FOR_EACH_EDGE (e, ei, bb->succs)
432 if (e->flags & EDGE_ABNORMAL)
435 for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
437 tree stmt = bsi_stmt (bsi);
438 block_stmt_iterator tobsi;
441 if (!statement_sink_location (stmt, bb, &tobb, &tobsi))
443 if (!bsi_end_p (bsi))
450 fprintf (dump_file, "Sinking ");
451 print_generic_expr (dump_file, stmt, TDF_VOPS);
452 fprintf (dump_file, " from bb %d to bb %d\n",
453 bb->index, tobb->index);
456 /* If this is the end of the basic block, we need to insert at the end
457 of the basic block. */
458 if (bsi_end_p (tobsi))
459 bsi_move_to_bb_end (&bsi, tobb);
461 bsi_move_before (&bsi, &tobsi);
465 /* If we've just removed the last statement of the BB, the
466 bsi_end_p() test below would fail, but bsi_prev() would have
467 succeeded, and we want it to succeed. So we keep track of
468 whether we're at the last statement and pick up the new last
477 if (!bsi_end_p (bsi))
482 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
484 son = next_dom_son (CDI_POST_DOMINATORS, son))
486 sink_code_in_bb (son);
490 /* Perform code sinking.
491 This moves code down the flowgraph when we know it would be
492 profitable to do so, or it wouldn't increase the number of
493 executions of the statement.
506 a_6 = PHI (a_5, a_1);
509 we'll transform this into:
520 a_6 = PHI (a_5, a_1);
523 Note that this reduces the number of computations of a = b + c to 1
524 when we take the else edge, instead of 2.
527 execute_sink_code (void)
529 loop_optimizer_init (LOOPS_NORMAL);
531 connect_infinite_loops_to_exit ();
532 memset (&sink_stats, 0, sizeof (sink_stats));
533 calculate_dominance_info (CDI_DOMINATORS);
534 calculate_dominance_info (CDI_POST_DOMINATORS);
535 sink_code_in_bb (EXIT_BLOCK_PTR);
536 statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
537 free_dominance_info (CDI_POST_DOMINATORS);
538 remove_fake_exit_edges ();
539 loop_optimizer_finalize ();
542 /* Gate and execute functions for PRE. */
547 execute_sink_code ();
554 return flag_tree_sink != 0;
557 struct gimple_opt_pass pass_sink_code =
562 gate_sink, /* gate */
563 do_sink, /* execute */
566 0, /* static_pass_number */
567 TV_TREE_SINK, /* tv_id */
568 PROP_no_crit_edges | PROP_cfg
569 | PROP_ssa | PROP_alias, /* properties_required */
570 0, /* properties_provided */
571 0, /* properties_destroyed */
572 0, /* todo_flags_start */
576 | TODO_verify_ssa /* todo_flags_finish */