1 /* Code sinking for trees
2 Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-dump.h"
38 #include "tree-iterator.h"
40 #include "alloc-pool.h"
41 #include "tree-pass.h"
44 #include "langhooks.h"
48 1. Sinking store only using scalar promotion (IE without moving the RHS):
68 Store copy propagation will take care of the store elimination above.
71 2. Sinking using Partial Dead Code Elimination. */
76 /* The number of statements sunk down the flowgraph by code sinking. */
82 /* Given a PHI, and one of its arguments (DEF), find the edge for
83 that argument and return it. If the argument occurs twice in the PHI node,
87 find_bb_for_arg (tree phi, tree def)
90 bool foundone = false;
91 basic_block result = NULL;
92 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
93 if (PHI_ARG_DEF (phi, i) == def)
98 result = PHI_ARG_EDGE (phi, i)->src;
103 /* When the first immediate use is in a statement, then return true if all
104 immediate uses in IMM are in the same statement.
105 We could also do the case where the first immediate use is in a phi node,
106 and all the other uses are in phis in the same basic block, but this
107 requires some expensive checking later (you have to make sure no def/vdef
108 in the statement occurs for multiple edges in the various phi nodes it's
109 used in, so that you only have one place you can sink it to. */
112 all_immediate_uses_same_place (tree stmt)
114 tree firstuse = NULL_TREE;
116 imm_use_iterator imm_iter;
120 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
122 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
124 if (firstuse == NULL_TREE)
125 firstuse = USE_STMT (use_p);
127 if (firstuse != USE_STMT (use_p))
135 /* Some global stores don't necessarily have V_MAY_DEF's of global variables,
136 but we still must avoid moving them around. */
139 is_hidden_global_store (tree stmt)
141 stmt_ann_t ann = stmt_ann (stmt);
142 v_may_def_optype v_may_defs;
143 v_must_def_optype v_must_defs;
145 /* Check virtual definitions. If we get here, the only virtual
146 definitions we should see are those generated by assignment
148 v_may_defs = V_MAY_DEF_OPS (ann);
149 v_must_defs = V_MUST_DEF_OPS (ann);
150 if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0)
154 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
156 /* Note that we must not check the individual virtual operands
157 here. In particular, if this is an aliased store, we could
158 end up with something like the following (SSA notation
159 redacted for brevity):
164 p_1 = (i_2 > 3) ? &x : p;
166 # x_4 = V_MAY_DEF <x_3>
172 Notice that the store to '*p_1' should be preserved, if we
173 were to check the virtual definitions in that store, we would
174 not mark it needed. This is because 'x' is not a global
177 Therefore, we check the base address of the LHS. If the
178 address is a pointer, we check if its name tag or type tag is
179 a global variable. Otherwise, we check if the base variable
181 lhs = TREE_OPERAND (stmt, 0);
182 if (REFERENCE_CLASS_P (lhs))
183 lhs = get_base_address (lhs);
185 if (lhs == NULL_TREE)
187 /* If LHS is NULL, it means that we couldn't get the base
188 address of the reference. In which case, we should not
192 else if (DECL_P (lhs))
194 /* If the store is to a global symbol, we need to keep it. */
195 if (is_global_var (lhs))
199 else if (INDIRECT_REF_P (lhs))
201 tree ptr = TREE_OPERAND (lhs, 0);
202 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
203 tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
204 tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
206 /* If either the name tag or the type tag for PTR is a
207 global variable, then the store is necessary. */
208 if ((nmt && is_global_var (nmt))
209 || (tmt && is_global_var (tmt)))
220 /* Find the nearest common dominator of all of the immediate uses in IMM. */
223 nearest_common_dominator_of_uses (tree stmt)
225 bitmap blocks = BITMAP_ALLOC (NULL);
226 basic_block commondom;
230 imm_use_iterator imm_iter;
234 bitmap_clear (blocks);
235 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
237 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
239 tree usestmt = USE_STMT (use_p);
240 basic_block useblock;
241 if (TREE_CODE (usestmt) == PHI_NODE)
244 for (j = 0; j < PHI_NUM_ARGS (usestmt); j++)
246 useblock = PHI_ARG_EDGE (usestmt, j)->src;
247 /* Short circuit. Nothing dominates the entry block. */
248 if (useblock == ENTRY_BLOCK_PTR)
250 BITMAP_FREE (blocks);
253 bitmap_set_bit (blocks, useblock->index);
258 useblock = bb_for_stmt (usestmt);
260 /* Short circuit. Nothing dominates the entry block. */
261 if (useblock == ENTRY_BLOCK_PTR)
263 BITMAP_FREE (blocks);
266 bitmap_set_bit (blocks, useblock->index);
270 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
271 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
272 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
274 BITMAP_FREE (blocks);
278 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
279 determine the location to sink the statement to, if any.
280 Return the basic block to sink it to, or NULL if we should not sink
284 statement_sink_location (tree stmt, basic_block frombb)
287 use_operand_p one_use = NULL_USE_OPERAND_P;
294 imm_use_iterator imm_iter;
296 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
298 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
302 if (one_use != NULL_USE_OPERAND_P)
306 /* Return if there are no immediate uses of this stmt. */
307 if (one_use == NULL_USE_OPERAND_P)
310 if (TREE_CODE (stmt) != MODIFY_EXPR)
312 rhs = TREE_OPERAND (stmt, 1);
314 /* There are a few classes of things we can't or don't move, some because we
315 don't have code to handle it, some because it's not profitable and some
316 because it's not legal.
318 We can't sink things that may be global stores, at least not without
319 calculating a lot more information, because we may cause it to no longer
320 be seen by an external routine that needs it depending on where it gets
323 We don't want to sink loads from memory.
325 We can't sink statements that end basic blocks without splitting the
326 incoming edge for the sink location to place it there.
328 We can't sink statements that have volatile operands.
330 We don't want to sink dead code, so anything with 0 immediate uses is not
334 ann = stmt_ann (stmt);
335 if (NUM_VUSES (STMT_VUSE_OPS (stmt)) != 0
336 || stmt_ends_bb_p (stmt)
337 || TREE_SIDE_EFFECTS (rhs)
338 || TREE_CODE (rhs) == EXC_PTR_EXPR
339 || TREE_CODE (rhs) == FILTER_EXPR
340 || is_hidden_global_store (stmt)
341 || ann->has_volatile_ops)
344 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
346 tree def = DEF_FROM_PTR (def_p);
347 if (is_global_var (SSA_NAME_VAR (def))
348 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
352 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
354 tree use = USE_FROM_PTR (use_p);
355 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
359 /* If all the immediate uses are not in the same place, find the nearest
360 common dominator of all the immediate uses. For PHI nodes, we have to
361 find the nearest common dominator of all of the predecessor blocks, since
362 that is where insertion would have to take place. */
363 if (!all_immediate_uses_same_place (stmt))
365 basic_block commondom = nearest_common_dominator_of_uses (stmt);
367 if (commondom == frombb)
370 /* Our common dominator has to be dominated by frombb in order to be a
371 trivially safe place to put this statement, since it has multiple
373 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
376 /* It doesn't make sense to move to a dominator that post-dominates
377 frombb, because it means we've just moved it into a path that always
378 executes if frombb executes, instead of reducing the number of
380 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
382 if (dump_file && (dump_flags & TDF_DETAILS))
383 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
387 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
389 if (dump_file && (dump_flags & TDF_DETAILS))
391 fprintf (dump_file, "Common dominator of all uses is %d\n",
394 return first_stmt (commondom);
397 use = USE_STMT (one_use);
398 if (TREE_CODE (use) != PHI_NODE)
400 sinkbb = bb_for_stmt (use);
401 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
402 || sinkbb->loop_father != frombb->loop_father)
407 /* Note that at this point, all uses must be in the same statement, so it
408 doesn't matter which def op we choose. */
409 if (STMT_DEF_OPS (stmt) == NULL)
411 if (STMT_V_MAY_DEF_OPS (stmt) != NULL)
412 def = V_MAY_DEF_RESULT (STMT_V_MAY_DEF_OPS (stmt), 0);
413 else if (STMT_V_MUST_DEF_OPS (stmt) != NULL)
414 def = V_MUST_DEF_RESULT (STMT_V_MUST_DEF_OPS (stmt), 0);
419 def = DEF_OP (STMT_DEF_OPS (stmt), 0);
421 sinkbb = find_bb_for_arg (use, def);
425 /* This will happen when you have
426 a_3 = PHI <a_13, a_26>
428 a_26 = V_MAY_DEF <a_3>
430 If the use is a phi, and is in the same bb as the def,
433 if (bb_for_stmt (use) == frombb)
435 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
436 || sinkbb->loop_father != frombb->loop_father)
439 return first_stmt (sinkbb);
442 /* Perform code sinking on BB */
445 sink_code_in_bb (basic_block bb)
448 block_stmt_iterator bsi;
452 /* If this block doesn't dominate anything, there can't be any place to sink
453 the statements to. */
454 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
457 /* We can't move things across abnormal edges, so don't try. */
458 FOR_EACH_EDGE (e, ei, bb->succs)
459 if (e->flags & EDGE_ABNORMAL)
462 for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
464 tree stmt = bsi_stmt (bsi);
465 block_stmt_iterator tobsi;
467 get_stmt_operands (stmt);
469 sinkstmt = statement_sink_location (stmt, bb);
472 if (!bsi_end_p (bsi))
478 fprintf (dump_file, "Sinking ");
479 print_generic_expr (dump_file, stmt, TDF_VOPS);
480 fprintf (dump_file, " from bb %d to bb %d\n",
481 bb->index, bb_for_stmt (sinkstmt)->index);
483 tobsi = bsi_for_stmt (sinkstmt);
484 /* Find the first non-label. */
485 while (!bsi_end_p (tobsi)
486 && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
489 /* If this is the end of the basic block, we need to insert at the end
490 of the basic block. */
491 if (bsi_end_p (tobsi))
492 bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
494 bsi_move_before (&bsi, &tobsi);
497 if (!bsi_end_p (bsi))
502 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
504 son = next_dom_son (CDI_POST_DOMINATORS, son))
506 sink_code_in_bb (son);
510 /* Perform code sinking.
511 This moves code down the flowgraph when we know it would be
512 profitable to do so, or it wouldn't increase the number of
513 executions of the statement.
526 a_6 = PHI (a_5, a_1);
529 we'll transform this into:
540 a_6 = PHI (a_5, a_1);
543 Note that this reduces the number of computations of a = b + c to 1
544 when we take the else edge, instead of 2.
547 execute_sink_code (void)
549 struct loops *loops = loop_optimizer_init (dump_file);
550 connect_infinite_loops_to_exit ();
551 memset (&sink_stats, 0, sizeof (sink_stats));
552 calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
553 sink_code_in_bb (EXIT_BLOCK_PTR);
554 if (dump_file && (dump_flags & TDF_STATS))
555 fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
556 free_dominance_info (CDI_POST_DOMINATORS);
557 remove_fake_exit_edges ();
558 loop_optimizer_finalize (loops, dump_file);
561 /* Gate and execute functions for PRE. */
566 execute_sink_code ();
572 return flag_tree_sink != 0;
575 struct tree_opt_pass pass_sink_code =
578 gate_sink, /* gate */
579 do_sink, /* execute */
582 0, /* static_pass_number */
583 TV_TREE_SINK, /* tv_id */
584 PROP_no_crit_edges | PROP_cfg
585 | PROP_ssa | PROP_alias, /* properties_required */
586 0, /* properties_provided */
587 0, /* properties_destroyed */
588 0, /* todo_flags_start */
589 TODO_rename_vars | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */