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 V_MAY_DEF'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
) == MODIFY_EXPR
);
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;
158 # x_4 = V_MAY_DEF <x_3>
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
= TREE_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
))
193 tree ptr
= TREE_OPERAND (lhs
, 0);
194 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
195 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
196 tree smt
= var_ann (SSA_NAME_VAR (ptr
))->symbol_mem_tag
;
198 /* If either the name tag or the symbol tag for PTR is a
199 global variable, then the store is necessary. */
200 if ((nmt
&& is_global_var (nmt
))
201 || (smt
&& is_global_var (smt
)))
212 /* Find the nearest common dominator of all of the immediate uses in IMM. */
215 nearest_common_dominator_of_uses (tree stmt
)
217 bitmap blocks
= BITMAP_ALLOC (NULL
);
218 basic_block commondom
;
222 imm_use_iterator imm_iter
;
226 bitmap_clear (blocks
);
227 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
229 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
231 tree usestmt
= USE_STMT (use_p
);
232 basic_block useblock
;
234 if (TREE_CODE (usestmt
) == PHI_NODE
)
236 int idx
= PHI_ARG_INDEX_FROM_USE (use_p
);
238 useblock
= PHI_ARG_EDGE (usestmt
, idx
)->src
;
242 useblock
= bb_for_stmt (usestmt
);
245 /* Short circuit. Nothing dominates the entry block. */
246 if (useblock
== ENTRY_BLOCK_PTR
)
248 BITMAP_FREE (blocks
);
251 bitmap_set_bit (blocks
, useblock
->index
);
254 commondom
= BASIC_BLOCK (bitmap_first_set_bit (blocks
));
255 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, j
, bi
)
256 commondom
= nearest_common_dominator (CDI_DOMINATORS
, commondom
,
258 BITMAP_FREE (blocks
);
262 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
263 determine the location to sink the statement to, if any.
264 Return the basic block to sink it to, or NULL if we should not sink
268 statement_sink_location (tree stmt
, basic_block frombb
)
271 use_operand_p one_use
= NULL_USE_OPERAND_P
;
278 imm_use_iterator imm_iter
;
280 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
282 FOR_EACH_IMM_USE_FAST (one_use
, imm_iter
, def
)
286 if (one_use
!= NULL_USE_OPERAND_P
)
290 /* Return if there are no immediate uses of this stmt. */
291 if (one_use
== NULL_USE_OPERAND_P
)
294 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
296 rhs
= TREE_OPERAND (stmt
, 1);
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
318 ann
= stmt_ann (stmt
);
319 if (stmt_ends_bb_p (stmt
)
320 || TREE_SIDE_EFFECTS (rhs
)
321 || TREE_CODE (rhs
) == EXC_PTR_EXPR
322 || TREE_CODE (rhs
) == FILTER_EXPR
323 || is_hidden_global_store (stmt
)
324 || ann
->has_volatile_ops
325 || !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VUSE
))
328 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
330 tree def
= DEF_FROM_PTR (def_p
);
331 if (is_global_var (SSA_NAME_VAR (def
))
332 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
))
336 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
338 tree use
= USE_FROM_PTR (use_p
);
339 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use
))
343 /* If all the immediate uses are not in the same place, find the nearest
344 common dominator of all the immediate uses. For PHI nodes, we have to
345 find the nearest common dominator of all of the predecessor blocks, since
346 that is where insertion would have to take place. */
347 if (!all_immediate_uses_same_place (stmt
))
349 basic_block commondom
= nearest_common_dominator_of_uses (stmt
);
351 if (commondom
== frombb
)
354 /* Our common dominator has to be dominated by frombb in order to be a
355 trivially safe place to put this statement, since it has multiple
357 if (!dominated_by_p (CDI_DOMINATORS
, commondom
, frombb
))
360 /* It doesn't make sense to move to a dominator that post-dominates
361 frombb, because it means we've just moved it into a path that always
362 executes if frombb executes, instead of reducing the number of
364 if (dominated_by_p (CDI_POST_DOMINATORS
, frombb
, commondom
))
366 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
367 fprintf (dump_file
, "Not moving store, common dominator post-dominates from block.\n");
371 if (commondom
== frombb
|| commondom
->loop_depth
> frombb
->loop_depth
)
373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
375 fprintf (dump_file
, "Common dominator of all uses is %d\n",
378 return first_stmt (commondom
);
381 use
= USE_STMT (one_use
);
382 if (TREE_CODE (use
) != PHI_NODE
)
384 sinkbb
= bb_for_stmt (use
);
385 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
386 || sinkbb
->loop_father
!= frombb
->loop_father
)
391 /* Note that at this point, all uses must be in the same statement, so it
392 doesn't matter which def op we choose, pick the first one. */
393 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
397 sinkbb
= find_bb_for_arg (use
, def
);
401 /* This will happen when you have
402 a_3 = PHI <a_13, a_26>
404 a_26 = V_MAY_DEF <a_3>
406 If the use is a phi, and is in the same bb as the def,
409 if (bb_for_stmt (use
) == frombb
)
411 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
412 || sinkbb
->loop_father
!= frombb
->loop_father
)
415 return first_stmt (sinkbb
);
418 /* Perform code sinking on BB */
421 sink_code_in_bb (basic_block bb
)
424 block_stmt_iterator bsi
;
428 /* If this block doesn't dominate anything, there can't be any place to sink
429 the statements to. */
430 if (first_dom_son (CDI_DOMINATORS
, bb
) == NULL
)
433 /* We can't move things across abnormal edges, so don't try. */
434 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
435 if (e
->flags
& EDGE_ABNORMAL
)
438 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
);)
440 tree stmt
= bsi_stmt (bsi
);
441 block_stmt_iterator tobsi
;
444 sinkstmt
= statement_sink_location (stmt
, bb
);
447 if (!bsi_end_p (bsi
))
453 fprintf (dump_file
, "Sinking ");
454 print_generic_expr (dump_file
, stmt
, TDF_VOPS
);
455 fprintf (dump_file
, " from bb %d to bb %d\n",
456 bb
->index
, bb_for_stmt (sinkstmt
)->index
);
458 tobsi
= bsi_for_stmt (sinkstmt
);
459 /* Find the first non-label. */
460 while (!bsi_end_p (tobsi
)
461 && TREE_CODE (bsi_stmt (tobsi
)) == LABEL_EXPR
)
464 /* If this is the end of the basic block, we need to insert at the end
465 of the basic block. */
466 if (bsi_end_p (tobsi
))
467 bsi_move_to_bb_end (&bsi
, bb_for_stmt (sinkstmt
));
469 bsi_move_before (&bsi
, &tobsi
);
472 if (!bsi_end_p (bsi
))
477 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
479 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
481 sink_code_in_bb (son
);
485 /* Perform code sinking.
486 This moves code down the flowgraph when we know it would be
487 profitable to do so, or it wouldn't increase the number of
488 executions of the statement.
501 a_6 = PHI (a_5, a_1);
504 we'll transform this into:
515 a_6 = PHI (a_5, a_1);
518 Note that this reduces the number of computations of a = b + c to 1
519 when we take the else edge, instead of 2.
522 execute_sink_code (void)
524 struct loops
*loops
= loop_optimizer_init (LOOPS_NORMAL
);
526 connect_infinite_loops_to_exit ();
527 memset (&sink_stats
, 0, sizeof (sink_stats
));
528 calculate_dominance_info (CDI_DOMINATORS
| CDI_POST_DOMINATORS
);
529 sink_code_in_bb (EXIT_BLOCK_PTR
);
530 if (dump_file
&& (dump_flags
& TDF_STATS
))
531 fprintf (dump_file
, "Sunk statements:%d\n", sink_stats
.sunk
);
532 free_dominance_info (CDI_POST_DOMINATORS
);
533 remove_fake_exit_edges ();
534 loop_optimizer_finalize (loops
);
537 /* Gate and execute functions for PRE. */
542 execute_sink_code ();
549 return flag_tree_sink
!= 0;
552 struct tree_opt_pass pass_sink_code
=
555 gate_sink
, /* gate */
556 do_sink
, /* execute */
559 0, /* static_pass_number */
560 TV_TREE_SINK
, /* tv_id */
561 PROP_no_crit_edges
| PROP_cfg
562 | PROP_ssa
| PROP_alias
, /* properties_required */
563 0, /* properties_provided */
564 0, /* properties_destroyed */
565 0, /* todo_flags_start */
569 | TODO_verify_ssa
, /* todo_flags_finish */