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 /* Check virtual definitions. If we get here, the only virtual
142 definitions we should see are those generated by assignment
144 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
148 gcc_assert (TREE_CODE (stmt
) == MODIFY_EXPR
);
150 /* Note that we must not check the individual virtual operands
151 here. In particular, if this is an aliased store, we could
152 end up with something like the following (SSA notation
153 redacted for brevity):
158 p_1 = (i_2 > 3) ? &x : p;
160 # x_4 = V_MAY_DEF <x_3>
166 Notice that the store to '*p_1' should be preserved, if we
167 were to check the virtual definitions in that store, we would
168 not mark it needed. This is because 'x' is not a global
171 Therefore, we check the base address of the LHS. If the
172 address is a pointer, we check if its name tag or type tag is
173 a global variable. Otherwise, we check if the base variable
175 lhs
= TREE_OPERAND (stmt
, 0);
176 if (REFERENCE_CLASS_P (lhs
))
177 lhs
= get_base_address (lhs
);
179 if (lhs
== NULL_TREE
)
181 /* If LHS is NULL, it means that we couldn't get the base
182 address of the reference. In which case, we should not
186 else if (DECL_P (lhs
))
188 /* If the store is to a global symbol, we need to keep it. */
189 if (is_global_var (lhs
))
193 else if (INDIRECT_REF_P (lhs
))
195 tree ptr
= TREE_OPERAND (lhs
, 0);
196 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
197 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
198 tree tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
200 /* If either the name tag or the type tag for PTR is a
201 global variable, then the store is necessary. */
202 if ((nmt
&& is_global_var (nmt
))
203 || (tmt
&& is_global_var (tmt
)))
214 /* Find the nearest common dominator of all of the immediate uses in IMM. */
217 nearest_common_dominator_of_uses (tree stmt
)
219 bitmap blocks
= BITMAP_ALLOC (NULL
);
220 basic_block commondom
;
224 imm_use_iterator imm_iter
;
228 bitmap_clear (blocks
);
229 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
231 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
233 tree usestmt
= USE_STMT (use_p
);
234 basic_block useblock
;
236 if (TREE_CODE (usestmt
) == PHI_NODE
)
238 int idx
= PHI_ARG_INDEX_FROM_USE (use_p
);
240 useblock
= PHI_ARG_EDGE (usestmt
, idx
)->src
;
244 useblock
= bb_for_stmt (usestmt
);
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
);
256 commondom
= BASIC_BLOCK (bitmap_first_set_bit (blocks
));
257 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, j
, bi
)
258 commondom
= nearest_common_dominator (CDI_DOMINATORS
, commondom
,
260 BITMAP_FREE (blocks
);
264 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
265 determine the location to sink the statement to, if any.
266 Return the basic block to sink it to, or NULL if we should not sink
270 statement_sink_location (tree stmt
, basic_block frombb
)
273 use_operand_p one_use
= NULL_USE_OPERAND_P
;
280 imm_use_iterator imm_iter
;
282 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
284 FOR_EACH_IMM_USE_FAST (one_use
, imm_iter
, def
)
288 if (one_use
!= NULL_USE_OPERAND_P
)
292 /* Return if there are no immediate uses of this stmt. */
293 if (one_use
== NULL_USE_OPERAND_P
)
296 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
298 rhs
= TREE_OPERAND (stmt
, 1);
300 /* There are a few classes of things we can't or don't move, some because we
301 don't have code to handle it, some because it's not profitable and some
302 because it's not legal.
304 We can't sink things that may be global stores, at least not without
305 calculating a lot more information, because we may cause it to no longer
306 be seen by an external routine that needs it depending on where it gets
309 We don't want to sink loads from memory.
311 We can't sink statements that end basic blocks without splitting the
312 incoming edge for the sink location to place it there.
314 We can't sink statements that have volatile operands.
316 We don't want to sink dead code, so anything with 0 immediate uses is not
320 ann
= stmt_ann (stmt
);
321 if (stmt_ends_bb_p (stmt
)
322 || TREE_SIDE_EFFECTS (rhs
)
323 || TREE_CODE (rhs
) == EXC_PTR_EXPR
324 || TREE_CODE (rhs
) == FILTER_EXPR
325 || is_hidden_global_store (stmt
)
326 || ann
->has_volatile_ops
327 || !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VUSE
))
330 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, iter
, SSA_OP_ALL_DEFS
)
332 tree def
= DEF_FROM_PTR (def_p
);
333 if (is_global_var (SSA_NAME_VAR (def
))
334 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
))
338 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
340 tree use
= USE_FROM_PTR (use_p
);
341 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use
))
345 /* If all the immediate uses are not in the same place, find the nearest
346 common dominator of all the immediate uses. For PHI nodes, we have to
347 find the nearest common dominator of all of the predecessor blocks, since
348 that is where insertion would have to take place. */
349 if (!all_immediate_uses_same_place (stmt
))
351 basic_block commondom
= nearest_common_dominator_of_uses (stmt
);
353 if (commondom
== frombb
)
356 /* Our common dominator has to be dominated by frombb in order to be a
357 trivially safe place to put this statement, since it has multiple
359 if (!dominated_by_p (CDI_DOMINATORS
, commondom
, frombb
))
362 /* It doesn't make sense to move to a dominator that post-dominates
363 frombb, because it means we've just moved it into a path that always
364 executes if frombb executes, instead of reducing the number of
366 if (dominated_by_p (CDI_POST_DOMINATORS
, frombb
, commondom
))
368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
369 fprintf (dump_file
, "Not moving store, common dominator post-dominates from block.\n");
373 if (commondom
== frombb
|| commondom
->loop_depth
> frombb
->loop_depth
)
375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
377 fprintf (dump_file
, "Common dominator of all uses is %d\n",
380 return first_stmt (commondom
);
383 use
= USE_STMT (one_use
);
384 if (TREE_CODE (use
) != PHI_NODE
)
386 sinkbb
= bb_for_stmt (use
);
387 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
388 || sinkbb
->loop_father
!= frombb
->loop_father
)
393 /* Note that at this point, all uses must be in the same statement, so it
394 doesn't matter which def op we choose, pick the first one. */
395 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
399 sinkbb
= find_bb_for_arg (use
, def
);
403 /* This will happen when you have
404 a_3 = PHI <a_13, a_26>
406 a_26 = V_MAY_DEF <a_3>
408 If the use is a phi, and is in the same bb as the def,
411 if (bb_for_stmt (use
) == frombb
)
413 if (sinkbb
== frombb
|| sinkbb
->loop_depth
> frombb
->loop_depth
414 || sinkbb
->loop_father
!= frombb
->loop_father
)
417 return first_stmt (sinkbb
);
420 /* Perform code sinking on BB */
423 sink_code_in_bb (basic_block bb
)
426 block_stmt_iterator bsi
;
430 /* If this block doesn't dominate anything, there can't be any place to sink
431 the statements to. */
432 if (first_dom_son (CDI_DOMINATORS
, bb
) == NULL
)
435 /* We can't move things across abnormal edges, so don't try. */
436 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
437 if (e
->flags
& EDGE_ABNORMAL
)
440 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
);)
442 tree stmt
= bsi_stmt (bsi
);
443 block_stmt_iterator tobsi
;
446 sinkstmt
= statement_sink_location (stmt
, bb
);
449 if (!bsi_end_p (bsi
))
455 fprintf (dump_file
, "Sinking ");
456 print_generic_expr (dump_file
, stmt
, TDF_VOPS
);
457 fprintf (dump_file
, " from bb %d to bb %d\n",
458 bb
->index
, bb_for_stmt (sinkstmt
)->index
);
460 tobsi
= bsi_for_stmt (sinkstmt
);
461 /* Find the first non-label. */
462 while (!bsi_end_p (tobsi
)
463 && TREE_CODE (bsi_stmt (tobsi
)) == LABEL_EXPR
)
466 /* If this is the end of the basic block, we need to insert at the end
467 of the basic block. */
468 if (bsi_end_p (tobsi
))
469 bsi_move_to_bb_end (&bsi
, bb_for_stmt (sinkstmt
));
471 bsi_move_before (&bsi
, &tobsi
);
474 if (!bsi_end_p (bsi
))
479 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
481 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
483 sink_code_in_bb (son
);
487 /* Perform code sinking.
488 This moves code down the flowgraph when we know it would be
489 profitable to do so, or it wouldn't increase the number of
490 executions of the statement.
503 a_6 = PHI (a_5, a_1);
506 we'll transform this into:
517 a_6 = PHI (a_5, a_1);
520 Note that this reduces the number of computations of a = b + c to 1
521 when we take the else edge, instead of 2.
524 execute_sink_code (void)
526 struct loops
*loops
= loop_optimizer_init (dump_file
);
527 connect_infinite_loops_to_exit ();
528 memset (&sink_stats
, 0, sizeof (sink_stats
));
529 calculate_dominance_info (CDI_DOMINATORS
| CDI_POST_DOMINATORS
);
530 sink_code_in_bb (EXIT_BLOCK_PTR
);
531 if (dump_file
&& (dump_flags
& TDF_STATS
))
532 fprintf (dump_file
, "Sunk statements:%d\n", sink_stats
.sunk
);
533 free_dominance_info (CDI_POST_DOMINATORS
);
534 remove_fake_exit_edges ();
535 loop_optimizer_finalize (loops
, dump_file
);
538 /* Gate and execute functions for PRE. */
543 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 */