1 /* Code sinking for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
37 #include "tree-iterator.h"
39 #include "alloc-pool.h"
40 #include "tree-pass.h"
43 #include "langhooks.h"
47 1. Sinking store only using scalar promotion (IE without moving the RHS):
67 Store copy propagation will take care of the store elimination above.
70 2. Sinking using Partial Dead Code Elimination. */
75 /* The number of statements sunk down the flowgraph by code sinking. */
81 /* Given a PHI, and one of its arguments (DEF), find the edge for
82 that argument and return it. If the argument occurs twice in the PHI node,
86 find_bb_for_arg (gimple phi
, tree def
)
89 bool foundone
= false;
90 basic_block result
= NULL
;
91 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
92 if (PHI_ARG_DEF (phi
, i
) == def
)
97 result
= gimple_phi_arg_edge (phi
, i
)->src
;
102 /* When the first immediate use is in a statement, then return true if all
103 immediate uses in IMM are in the same statement.
104 We could also do the case where the first immediate use is in a phi node,
105 and all the other uses are in phis in the same basic block, but this
106 requires some expensive checking later (you have to make sure no def/vdef
107 in the statement occurs for multiple edges in the various phi nodes it's
108 used in, so that you only have one place you can sink it to. */
111 all_immediate_uses_same_place (gimple stmt
)
113 gimple firstuse
= NULL
;
115 imm_use_iterator imm_iter
;
119 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
121 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
123 if (is_gimple_debug (USE_STMT (use_p
)))
125 if (firstuse
== NULL
)
126 firstuse
= USE_STMT (use_p
);
128 if (firstuse
!= USE_STMT (use_p
))
136 /* Some global stores don't necessarily have VDEF's of global variables,
137 but we still must avoid moving them around. */
140 is_hidden_global_store (gimple stmt
)
142 /* Check virtual definitions. If we get here, the only virtual
143 definitions we should see are those generated by assignment or call
145 if (gimple_vdef (stmt
))
149 gcc_assert (is_gimple_assign (stmt
) || is_gimple_call (stmt
));
151 /* Note that we must not check the individual virtual operands
152 here. In particular, if this is an aliased store, we could
153 end up with something like the following (SSA notation
154 redacted for brevity):
159 p_1 = (i_2 > 3) ? &x : p;
167 Notice that the store to '*p_1' should be preserved, if we
168 were to check the virtual definitions in that store, we would
169 not mark it needed. This is because 'x' is not a global
172 Therefore, we check the base address of the LHS. If the
173 address is a pointer, we check if its name tag or symbol tag is
174 a global variable. Otherwise, we check if the base variable
176 lhs
= gimple_get_lhs (stmt
);
178 if (REFERENCE_CLASS_P (lhs
))
179 lhs
= get_base_address (lhs
);
181 if (lhs
== NULL_TREE
)
183 /* If LHS is NULL, it means that we couldn't get the base
184 address of the reference. In which case, we should not
188 else if (DECL_P (lhs
))
190 /* If the store is to a global symbol, we need to keep it. */
191 if (is_global_var (lhs
))
195 else if (INDIRECT_REF_P (lhs
))
196 return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs
, 0));
204 /* Find the nearest common dominator of all of the immediate uses in IMM. */
207 nearest_common_dominator_of_uses (gimple stmt
, bool *debug_stmts
)
209 bitmap blocks
= BITMAP_ALLOC (NULL
);
210 basic_block commondom
;
214 imm_use_iterator imm_iter
;
218 bitmap_clear (blocks
);
219 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
221 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
223 gimple usestmt
= USE_STMT (use_p
);
224 basic_block useblock
;
226 if (gimple_code (usestmt
) == GIMPLE_PHI
)
228 int idx
= PHI_ARG_INDEX_FROM_USE (use_p
);
230 useblock
= gimple_phi_arg_edge (usestmt
, idx
)->src
;
232 else if (is_gimple_debug (usestmt
))
239 useblock
= gimple_bb (usestmt
);
242 /* Short circuit. Nothing dominates the entry block. */
243 if (useblock
== ENTRY_BLOCK_PTR
)
245 BITMAP_FREE (blocks
);
248 bitmap_set_bit (blocks
, useblock
->index
);
251 commondom
= BASIC_BLOCK (bitmap_first_set_bit (blocks
));
252 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, j
, bi
)
253 commondom
= nearest_common_dominator (CDI_DOMINATORS
, commondom
,
255 BITMAP_FREE (blocks
);
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. */
265 statement_sink_location (gimple stmt
, basic_block frombb
,
266 gimple_stmt_iterator
*togsi
)
270 use_operand_p one_use
= NULL_USE_OPERAND_P
;
275 imm_use_iterator imm_iter
;
278 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
280 FOR_EACH_IMM_USE_FAST (one_use
, imm_iter
, def
)
282 if (is_gimple_debug (USE_STMT (one_use
)))
287 if (one_use
!= NULL_USE_OPERAND_P
)
291 /* Return if there are no immediate uses of this stmt. */
292 if (one_use
== NULL_USE_OPERAND_P
)
295 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
298 /* There are a few classes of things we can't or don't move, some because we
299 don't have code to handle it, some because it's not profitable and some
300 because it's not legal.
302 We can't sink things that may be global stores, at least not without
303 calculating a lot more information, because we may cause it to no longer
304 be seen by an external routine that needs it depending on where it gets
307 We don't want to sink loads from memory.
309 We can't sink statements that end basic blocks without splitting the
310 incoming edge for the sink location to place it there.
312 We can't sink statements that have volatile operands.
314 We don't want to sink dead code, so anything with 0 immediate uses is not
317 Don't sink BLKmode assignments if current function has any local explicit
318 register variables, as BLKmode assignments may involve memcpy or memset
319 calls or, on some targets, inline expansion thereof that sometimes need
320 to use specific hard registers.
323 code
= gimple_assign_rhs_code (stmt
);
324 if (stmt_ends_bb_p (stmt
)
325 || gimple_has_side_effects (stmt
)
326 || code
== EXC_PTR_EXPR
327 || code
== FILTER_EXPR
328 || is_hidden_global_store (stmt
)
329 || gimple_has_volatile_ops (stmt
)
330 || gimple_vuse (stmt
)
331 || (cfun
->has_local_explicit_reg_vars
332 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
))) == BLKmode
))
335 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
337 tree def
= DEF_FROM_PTR (def_p
);
338 if (is_global_var (SSA_NAME_VAR (def
))
339 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
))
343 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
345 tree use
= USE_FROM_PTR (use_p
);
346 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use
))
350 /* If all the immediate uses are not in the same place, find the nearest
351 common dominator of all the immediate uses. For PHI nodes, we have to
352 find the nearest common dominator of all of the predecessor blocks, since
353 that is where insertion would have to take place. */
354 if (!all_immediate_uses_same_place (stmt
))
356 bool debug_stmts
= false;
357 basic_block commondom
= nearest_common_dominator_of_uses (stmt
,
360 if (commondom
== frombb
)
363 /* Our common dominator has to be dominated by frombb in order to be a
364 trivially safe place to put this statement, since it has multiple
366 if (!dominated_by_p (CDI_DOMINATORS
, commondom
, frombb
))
369 /* It doesn't make sense to move to a dominator that post-dominates
370 frombb, because it means we've just moved it into a path that always
371 executes if frombb executes, instead of reducing the number of
373 if (dominated_by_p (CDI_POST_DOMINATORS
, frombb
, commondom
))
375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
376 fprintf (dump_file
, "Not moving store, common dominator post-dominates from block.\n");
380 if (commondom
== frombb
|| commondom
->loop_depth
> frombb
->loop_depth
)
382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
384 fprintf (dump_file
, "Common dominator of all uses is %d\n",
388 *togsi
= gsi_after_labels (commondom
);
391 propagate_defs_into_debug_stmts (stmt
, commondom
, togsi
);
396 use
= USE_STMT (one_use
);
397 if (gimple_code (use
) != GIMPLE_PHI
)
399 sinkbb
= gimple_bb (use
);
400 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
401 || sinkbb
->loop_father
!= frombb
->loop_father
)
404 /* Move the expression to a post dominator can't reduce the number of
406 if (dominated_by_p (CDI_POST_DOMINATORS
, frombb
, sinkbb
))
409 *togsi
= gsi_for_stmt (use
);
411 propagate_defs_into_debug_stmts (stmt
, sinkbb
, togsi
);
416 /* Note that at this point, all uses must be in the same statement, so it
417 doesn't matter which def op we choose, pick the first one. */
418 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
421 sinkbb
= find_bb_for_arg (use
, def
);
425 /* This will happen when you have
426 a_3 = PHI <a_13, a_26>
430 If the use is a phi, and is in the same bb as the def,
433 if (gimple_bb (use
) == frombb
)
435 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
436 || sinkbb
->loop_father
!= frombb
->loop_father
)
439 /* Move the expression to a post dominator can't reduce the number of
441 if (dominated_by_p (CDI_POST_DOMINATORS
, frombb
, sinkbb
))
444 *togsi
= gsi_after_labels (sinkbb
);
446 propagate_defs_into_debug_stmts (stmt
, sinkbb
, togsi
);
451 /* Perform code sinking on BB */
454 sink_code_in_bb (basic_block bb
)
457 gimple_stmt_iterator gsi
;
462 /* If this block doesn't dominate anything, there can't be any place to sink
463 the statements to. */
464 if (first_dom_son (CDI_DOMINATORS
, bb
) == NULL
)
467 /* We can't move things across abnormal edges, so don't try. */
468 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
469 if (e
->flags
& EDGE_ABNORMAL
)
472 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
474 gimple stmt
= gsi_stmt (gsi
);
475 gimple_stmt_iterator togsi
;
477 if (!statement_sink_location (stmt
, bb
, &togsi
))
479 if (!gsi_end_p (gsi
))
486 fprintf (dump_file
, "Sinking ");
487 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
);
488 fprintf (dump_file
, " from bb %d to bb %d\n",
489 bb
->index
, (gsi_bb (togsi
))->index
);
492 /* If this is the end of the basic block, we need to insert at the end
493 of the basic block. */
494 if (gsi_end_p (togsi
))
495 gsi_move_to_bb_end (&gsi
, gsi_bb (togsi
));
497 gsi_move_before (&gsi
, &togsi
);
501 /* If we've just removed the last statement of the BB, the
502 gsi_end_p() test below would fail, but gsi_prev() would have
503 succeeded, and we want it to succeed. So we keep track of
504 whether we're at the last statement and pick up the new last
508 gsi
= gsi_last_bb (bb
);
513 if (!gsi_end_p (gsi
))
518 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
520 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
522 sink_code_in_bb (son
);
526 /* Perform code sinking.
527 This moves code down the flowgraph when we know it would be
528 profitable to do so, or it wouldn't increase the number of
529 executions of the statement.
542 a_6 = PHI (a_5, a_1);
545 we'll transform this into:
556 a_6 = PHI (a_5, a_1);
559 Note that this reduces the number of computations of a = b + c to 1
560 when we take the else edge, instead of 2.
563 execute_sink_code (void)
565 loop_optimizer_init (LOOPS_NORMAL
);
567 connect_infinite_loops_to_exit ();
568 memset (&sink_stats
, 0, sizeof (sink_stats
));
569 calculate_dominance_info (CDI_DOMINATORS
);
570 calculate_dominance_info (CDI_POST_DOMINATORS
);
571 sink_code_in_bb (EXIT_BLOCK_PTR
);
572 statistics_counter_event (cfun
, "Sunk statements", sink_stats
.sunk
);
573 free_dominance_info (CDI_POST_DOMINATORS
);
574 remove_fake_exit_edges ();
575 loop_optimizer_finalize ();
578 /* Gate and execute functions for PRE. */
583 execute_sink_code ();
590 return flag_tree_sink
!= 0;
593 struct gimple_opt_pass pass_sink_code
=
598 gate_sink
, /* gate */
599 do_sink
, /* execute */
602 0, /* static_pass_number */
603 TV_TREE_SINK
, /* tv_id */
604 PROP_no_crit_edges
| PROP_cfg
605 | PROP_ssa
, /* properties_required */
606 0, /* properties_provided */
607 0, /* properties_destroyed */
608 0, /* todo_flags_start */
612 | TODO_verify_ssa
/* todo_flags_finish */