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"
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 (gimple phi
, tree def
)
88 bool foundone
= false;
89 basic_block result
= NULL
;
90 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
91 if (PHI_ARG_DEF (phi
, i
) == def
)
96 result
= gimple_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 (gimple stmt
)
112 gimple firstuse
= NULL
;
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
)
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 (gimple stmt
)
139 /* Check virtual definitions. If we get here, the only virtual
140 definitions we should see are those generated by assignment or call
142 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
146 gcc_assert (is_gimple_assign (stmt
) || is_gimple_call (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_get_lhs (stmt
);
175 if (REFERENCE_CLASS_P (lhs
))
176 lhs
= get_base_address (lhs
);
178 if (lhs
== NULL_TREE
)
180 /* If LHS is NULL, it means that we couldn't get the base
181 address of the reference. In which case, we should not
185 else if (DECL_P (lhs
))
187 /* If the store is to a global symbol, we need to keep it. */
188 if (is_global_var (lhs
))
192 else if (INDIRECT_REF_P (lhs
))
193 return may_point_to_global_var (TREE_OPERAND (lhs
, 0));
201 /* Find the nearest common dominator of all of the immediate uses in IMM. */
204 nearest_common_dominator_of_uses (gimple stmt
)
206 bitmap blocks
= BITMAP_ALLOC (NULL
);
207 basic_block commondom
;
211 imm_use_iterator imm_iter
;
215 bitmap_clear (blocks
);
216 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
218 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
220 gimple usestmt
= USE_STMT (use_p
);
221 basic_block useblock
;
223 if (gimple_code (usestmt
) == GIMPLE_PHI
)
225 int idx
= PHI_ARG_INDEX_FROM_USE (use_p
);
227 useblock
= gimple_phi_arg_edge (usestmt
, idx
)->src
;
231 useblock
= gimple_bb (usestmt
);
234 /* Short circuit. Nothing dominates the entry block. */
235 if (useblock
== ENTRY_BLOCK_PTR
)
237 BITMAP_FREE (blocks
);
240 bitmap_set_bit (blocks
, useblock
->index
);
243 commondom
= BASIC_BLOCK (bitmap_first_set_bit (blocks
));
244 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, j
, bi
)
245 commondom
= nearest_common_dominator (CDI_DOMINATORS
, commondom
,
247 BITMAP_FREE (blocks
);
251 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
252 determine the location to sink the statement to, if any.
253 Returns true if there is such location; in that case, TOGSI points to the
254 statement before that STMT should be moved. */
257 statement_sink_location (gimple stmt
, basic_block frombb
,
258 gimple_stmt_iterator
*togsi
)
262 use_operand_p one_use
= NULL_USE_OPERAND_P
;
267 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 (gimple_code (stmt
) != GIMPLE_ASSIGN
)
287 /* There are a few classes of things we can't or don't move, some because we
288 don't have code to handle it, some because it's not profitable and some
289 because it's not legal.
291 We can't sink things that may be global stores, at least not without
292 calculating a lot more information, because we may cause it to no longer
293 be seen by an external routine that needs it depending on where it gets
296 We don't want to sink loads from memory.
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
307 code
= gimple_assign_rhs_code (stmt
);
308 if (stmt_ends_bb_p (stmt
)
309 || gimple_has_side_effects (stmt
)
310 || code
== EXC_PTR_EXPR
311 || code
== FILTER_EXPR
312 || is_hidden_global_store (stmt
)
313 || gimple_has_volatile_ops (stmt
)
314 || !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VUSE
))
317 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
319 tree def
= DEF_FROM_PTR (def_p
);
320 if (is_global_var (SSA_NAME_VAR (def
))
321 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
))
325 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
327 tree use
= USE_FROM_PTR (use_p
);
328 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use
))
332 /* If all the immediate uses are not in the same place, find the nearest
333 common dominator of all the immediate uses. For PHI nodes, we have to
334 find the nearest common dominator of all of the predecessor blocks, since
335 that is where insertion would have to take place. */
336 if (!all_immediate_uses_same_place (stmt
))
338 basic_block commondom
= nearest_common_dominator_of_uses (stmt
);
340 if (commondom
== frombb
)
343 /* Our common dominator has to be dominated by frombb in order to be a
344 trivially safe place to put this statement, since it has multiple
346 if (!dominated_by_p (CDI_DOMINATORS
, commondom
, frombb
))
349 /* It doesn't make sense to move to a dominator that post-dominates
350 frombb, because it means we've just moved it into a path that always
351 executes if frombb executes, instead of reducing the number of
353 if (dominated_by_p (CDI_POST_DOMINATORS
, frombb
, commondom
))
355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
356 fprintf (dump_file
, "Not moving store, common dominator post-dominates from block.\n");
360 if (commondom
== frombb
|| commondom
->loop_depth
> frombb
->loop_depth
)
362 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
364 fprintf (dump_file
, "Common dominator of all uses is %d\n",
367 *togsi
= gsi_after_labels (commondom
);
371 use
= USE_STMT (one_use
);
372 if (gimple_code (use
) != GIMPLE_PHI
)
374 sinkbb
= gimple_bb (use
);
375 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
376 || sinkbb
->loop_father
!= frombb
->loop_father
)
379 *togsi
= gsi_for_stmt (use
);
383 /* Note that at this point, all uses must be in the same statement, so it
384 doesn't matter which def op we choose, pick the first one. */
385 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
388 sinkbb
= find_bb_for_arg (use
, def
);
392 /* This will happen when you have
393 a_3 = PHI <a_13, a_26>
397 If the use is a phi, and is in the same bb as the def,
400 if (gimple_bb (use
) == frombb
)
402 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
403 || sinkbb
->loop_father
!= frombb
->loop_father
)
406 *togsi
= gsi_after_labels (sinkbb
);
411 /* Perform code sinking on BB */
414 sink_code_in_bb (basic_block bb
)
417 gimple_stmt_iterator gsi
;
422 /* If this block doesn't dominate anything, there can't be any place to sink
423 the statements to. */
424 if (first_dom_son (CDI_DOMINATORS
, bb
) == NULL
)
427 /* We can't move things across abnormal edges, so don't try. */
428 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
429 if (e
->flags
& EDGE_ABNORMAL
)
432 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
434 gimple stmt
= gsi_stmt (gsi
);
435 gimple_stmt_iterator togsi
;
437 if (!statement_sink_location (stmt
, bb
, &togsi
))
439 if (!gsi_end_p (gsi
))
446 fprintf (dump_file
, "Sinking ");
447 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
);
448 fprintf (dump_file
, " from bb %d to bb %d\n",
449 bb
->index
, (gsi_bb (togsi
))->index
);
452 /* If this is the end of the basic block, we need to insert at the end
453 of the basic block. */
454 if (gsi_end_p (togsi
))
455 gsi_move_to_bb_end (&gsi
, gsi_bb (togsi
));
457 gsi_move_before (&gsi
, &togsi
);
461 /* If we've just removed the last statement of the BB, the
462 gsi_end_p() test below would fail, but gsi_prev() would have
463 succeeded, and we want it to succeed. So we keep track of
464 whether we're at the last statement and pick up the new last
468 gsi
= gsi_last_bb (bb
);
473 if (!gsi_end_p (gsi
))
478 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
480 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
482 sink_code_in_bb (son
);
486 /* Perform code sinking.
487 This moves code down the flowgraph when we know it would be
488 profitable to do so, or it wouldn't increase the number of
489 executions of the statement.
502 a_6 = PHI (a_5, a_1);
505 we'll transform this into:
516 a_6 = PHI (a_5, a_1);
519 Note that this reduces the number of computations of a = b + c to 1
520 when we take the else edge, instead of 2.
523 execute_sink_code (void)
525 loop_optimizer_init (LOOPS_NORMAL
);
527 connect_infinite_loops_to_exit ();
528 memset (&sink_stats
, 0, sizeof (sink_stats
));
529 calculate_dominance_info (CDI_DOMINATORS
);
530 calculate_dominance_info (CDI_POST_DOMINATORS
);
531 sink_code_in_bb (EXIT_BLOCK_PTR
);
532 statistics_counter_event (cfun
, "Sunk statements", sink_stats
.sunk
);
533 free_dominance_info (CDI_POST_DOMINATORS
);
534 remove_fake_exit_edges ();
535 loop_optimizer_finalize ();
538 /* Gate and execute functions for PRE. */
543 execute_sink_code ();
550 return flag_tree_sink
!= 0;
553 struct gimple_opt_pass pass_sink_code
=
558 gate_sink
, /* gate */
559 do_sink
, /* execute */
562 0, /* static_pass_number */
563 TV_TREE_SINK
, /* tv_id */
564 PROP_no_crit_edges
| PROP_cfg
565 | PROP_ssa
| PROP_alias
, /* properties_required */
566 0, /* properties_provided */
567 0, /* properties_destroyed */
568 0, /* todo_flags_start */
572 | TODO_verify_ssa
/* todo_flags_finish */