1 /* Code sinking for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2007, 2008, 2009, 2010
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"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "tree-inline.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
36 #include "tree-iterator.h"
37 #include "alloc-pool.h"
38 #include "tree-pass.h"
41 #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 (is_gimple_debug (USE_STMT (use_p
)))
124 if (firstuse
== NULL
)
125 firstuse
= USE_STMT (use_p
);
127 if (firstuse
!= USE_STMT (use_p
))
135 /* Some global stores don't necessarily have VDEF's of global variables,
136 but we still must avoid moving them around. */
139 is_hidden_global_store (gimple stmt
)
141 /* Check virtual definitions. If we get here, the only virtual
142 definitions we should see are those generated by assignment or call
144 if (gimple_vdef (stmt
))
148 gcc_assert (is_gimple_assign (stmt
) || is_gimple_call (stmt
));
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;
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 symbol tag is
173 a global variable. Otherwise, we check if the base variable
175 lhs
= gimple_get_lhs (stmt
);
177 if (REFERENCE_CLASS_P (lhs
))
178 lhs
= get_base_address (lhs
);
180 if (lhs
== NULL_TREE
)
182 /* If LHS is NULL, it means that we couldn't get the base
183 address of the reference. In which case, we should not
187 else if (DECL_P (lhs
))
189 /* If the store is to a global symbol, we need to keep it. */
190 if (is_global_var (lhs
))
194 else if (INDIRECT_REF_P (lhs
)
195 || TREE_CODE (lhs
) == MEM_REF
196 || TREE_CODE (lhs
) == TARGET_MEM_REF
)
197 return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs
, 0));
198 else if (CONSTANT_CLASS_P (lhs
))
207 /* Find the nearest common dominator of all of the immediate uses in IMM. */
210 nearest_common_dominator_of_uses (gimple stmt
, bool *debug_stmts
)
212 bitmap blocks
= BITMAP_ALLOC (NULL
);
213 basic_block commondom
;
217 imm_use_iterator imm_iter
;
221 bitmap_clear (blocks
);
222 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
224 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
226 gimple usestmt
= USE_STMT (use_p
);
227 basic_block useblock
;
229 if (gimple_code (usestmt
) == GIMPLE_PHI
)
231 int idx
= PHI_ARG_INDEX_FROM_USE (use_p
);
233 useblock
= gimple_phi_arg_edge (usestmt
, idx
)->src
;
235 else if (is_gimple_debug (usestmt
))
242 useblock
= gimple_bb (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 EARLY_BB and LATE_BB, two blocks in a path through the dominator
263 tree, return the best basic block between them (inclusive) to place
266 We want the most control dependent block in the shallowest loop nest.
268 If the resulting block is in a shallower loop nest, then use it. Else
269 only use the resulting block if it has significantly lower execution
270 frequency than EARLY_BB to avoid gratutious statement movement. We
271 consider statements with VOPS more desirable to move.
273 This pass would obviously benefit from PDO as it utilizes block
274 frequencies. It would also benefit from recomputing frequencies
275 if profile data is not available since frequencies often get out
276 of sync with reality. */
279 select_best_block (basic_block early_bb
,
283 basic_block best_bb
= late_bb
;
284 basic_block temp_bb
= late_bb
;
287 while (temp_bb
!= early_bb
)
289 /* If we've moved into a lower loop nest, then that becomes
291 if (temp_bb
->loop_depth
< best_bb
->loop_depth
)
294 /* Walk up the dominator tree, hopefully we'll find a shallower
296 temp_bb
= get_immediate_dominator (CDI_DOMINATORS
, temp_bb
);
299 /* If we found a shallower loop nest, then we always consider that
300 a win. This will always give us the most control dependent block
301 within that loop nest. */
302 if (best_bb
->loop_depth
< early_bb
->loop_depth
)
305 /* Get the sinking threshold. If the statement to be moved has memory
306 operands, then increase the threshold by 7% as those are even more
307 profitable to avoid, clamping at 100%. */
308 threshold
= PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD
);
309 if (gimple_vuse (stmt
) || gimple_vdef (stmt
))
316 /* If BEST_BB is at the same nesting level, then require it to have
317 significantly lower execution frequency to avoid gratutious movement. */
318 if (best_bb
->loop_depth
== early_bb
->loop_depth
319 && best_bb
->frequency
< (early_bb
->frequency
* threshold
/ 100.0))
322 /* No better block found, so return EARLY_BB, which happens to be the
323 statement's original block. */
327 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
328 determine the location to sink the statement to, if any.
329 Returns true if there is such location; in that case, TOGSI points to the
330 statement before that STMT should be moved. */
333 statement_sink_location (gimple stmt
, basic_block frombb
,
334 gimple_stmt_iterator
*togsi
)
337 use_operand_p one_use
= NULL_USE_OPERAND_P
;
342 imm_use_iterator imm_iter
;
344 /* We only can sink assignments. */
345 if (!is_gimple_assign (stmt
))
348 /* We only can sink stmts with a single definition. */
349 def_p
= single_ssa_def_operand (stmt
, SSA_OP_ALL_DEFS
);
350 if (def_p
== NULL_DEF_OPERAND_P
)
353 /* Return if there are no immediate uses of this stmt. */
354 if (has_zero_uses (DEF_FROM_PTR (def_p
)))
357 /* There are a few classes of things we can't or don't move, some because we
358 don't have code to handle it, some because it's not profitable and some
359 because it's not legal.
361 We can't sink things that may be global stores, at least not without
362 calculating a lot more information, because we may cause it to no longer
363 be seen by an external routine that needs it depending on where it gets
366 We don't want to sink loads from memory.
368 We can't sink statements that end basic blocks without splitting the
369 incoming edge for the sink location to place it there.
371 We can't sink statements that have volatile operands.
373 We don't want to sink dead code, so anything with 0 immediate uses is not
376 Don't sink BLKmode assignments if current function has any local explicit
377 register variables, as BLKmode assignments may involve memcpy or memset
378 calls or, on some targets, inline expansion thereof that sometimes need
379 to use specific hard registers.
382 if (stmt_ends_bb_p (stmt
)
383 || gimple_has_side_effects (stmt
)
384 || gimple_has_volatile_ops (stmt
)
385 || (gimple_vuse (stmt
) && !gimple_vdef (stmt
))
386 || (cfun
->has_local_explicit_reg_vars
387 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt
))) == BLKmode
))
390 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p
)))
393 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
395 tree use
= USE_FROM_PTR (use_p
);
396 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use
))
402 /* If stmt is a store the one and only use needs to be the VOP
404 if (gimple_vdef (stmt
))
406 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, DEF_FROM_PTR (def_p
))
408 gimple use_stmt
= USE_STMT (use_p
);
410 /* A killing definition is not a use. */
411 if (gimple_assign_single_p (use_stmt
)
412 && gimple_vdef (use_stmt
)
413 && operand_equal_p (gimple_assign_lhs (stmt
),
414 gimple_assign_lhs (use_stmt
), 0))
416 /* If use_stmt is or might be a nop assignment then USE_STMT
417 acts as a use as well as definition. */
419 && ref_maybe_used_by_stmt_p (use_stmt
,
420 gimple_assign_lhs (stmt
)))
425 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
437 /* If all the immediate uses are not in the same place, find the nearest
438 common dominator of all the immediate uses. For PHI nodes, we have to
439 find the nearest common dominator of all of the predecessor blocks, since
440 that is where insertion would have to take place. */
441 else if (!all_immediate_uses_same_place (stmt
))
443 bool debug_stmts
= false;
444 basic_block commondom
= nearest_common_dominator_of_uses (stmt
,
447 if (commondom
== frombb
)
450 /* Our common dominator has to be dominated by frombb in order to be a
451 trivially safe place to put this statement, since it has multiple
453 if (!dominated_by_p (CDI_DOMINATORS
, commondom
, frombb
))
456 commondom
= select_best_block (frombb
, commondom
, stmt
);
458 if (commondom
== frombb
)
461 *togsi
= gsi_after_labels (commondom
);
467 FOR_EACH_IMM_USE_FAST (one_use
, imm_iter
, DEF_FROM_PTR (def_p
))
469 if (is_gimple_debug (USE_STMT (one_use
)))
473 use
= USE_STMT (one_use
);
475 if (gimple_code (use
) != GIMPLE_PHI
)
477 sinkbb
= gimple_bb (use
);
478 sinkbb
= select_best_block (frombb
, gimple_bb (use
), stmt
);
480 if (sinkbb
== frombb
)
483 *togsi
= gsi_for_stmt (use
);
489 sinkbb
= find_bb_for_arg (use
, DEF_FROM_PTR (def_p
));
491 /* This can happen if there are multiple uses in a PHI. */
495 sinkbb
= select_best_block (frombb
, sinkbb
, stmt
);
496 if (!sinkbb
|| sinkbb
== frombb
)
499 /* If the latch block is empty, don't make it non-empty by sinking
500 something into it. */
501 if (sinkbb
== frombb
->loop_father
->latch
502 && empty_block_p (sinkbb
))
505 *togsi
= gsi_after_labels (sinkbb
);
510 /* Perform code sinking on BB */
513 sink_code_in_bb (basic_block bb
)
516 gimple_stmt_iterator gsi
;
521 /* If this block doesn't dominate anything, there can't be any place to sink
522 the statements to. */
523 if (first_dom_son (CDI_DOMINATORS
, bb
) == NULL
)
526 /* We can't move things across abnormal edges, so don't try. */
527 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
528 if (e
->flags
& EDGE_ABNORMAL
)
531 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
533 gimple stmt
= gsi_stmt (gsi
);
534 gimple_stmt_iterator togsi
;
536 if (!statement_sink_location (stmt
, bb
, &togsi
))
538 if (!gsi_end_p (gsi
))
545 fprintf (dump_file
, "Sinking ");
546 print_gimple_stmt (dump_file
, stmt
, 0, TDF_VOPS
);
547 fprintf (dump_file
, " from bb %d to bb %d\n",
548 bb
->index
, (gsi_bb (togsi
))->index
);
551 /* Update virtual operands of statements in the path we
553 if (gimple_vdef (stmt
))
555 imm_use_iterator iter
;
559 FOR_EACH_IMM_USE_STMT (vuse_stmt
, iter
, gimple_vdef (stmt
))
560 if (gimple_code (vuse_stmt
) != GIMPLE_PHI
)
561 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
562 SET_USE (use_p
, gimple_vuse (stmt
));
565 /* If this is the end of the basic block, we need to insert at the end
566 of the basic block. */
567 if (gsi_end_p (togsi
))
568 gsi_move_to_bb_end (&gsi
, gsi_bb (togsi
));
570 gsi_move_before (&gsi
, &togsi
);
574 /* If we've just removed the last statement of the BB, the
575 gsi_end_p() test below would fail, but gsi_prev() would have
576 succeeded, and we want it to succeed. So we keep track of
577 whether we're at the last statement and pick up the new last
581 gsi
= gsi_last_bb (bb
);
586 if (!gsi_end_p (gsi
))
591 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
593 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
595 sink_code_in_bb (son
);
599 /* Perform code sinking.
600 This moves code down the flowgraph when we know it would be
601 profitable to do so, or it wouldn't increase the number of
602 executions of the statement.
615 a_6 = PHI (a_5, a_1);
618 we'll transform this into:
629 a_6 = PHI (a_5, a_1);
632 Note that this reduces the number of computations of a = b + c to 1
633 when we take the else edge, instead of 2.
636 execute_sink_code (void)
638 loop_optimizer_init (LOOPS_NORMAL
);
639 split_critical_edges ();
640 connect_infinite_loops_to_exit ();
641 memset (&sink_stats
, 0, sizeof (sink_stats
));
642 calculate_dominance_info (CDI_DOMINATORS
);
643 calculate_dominance_info (CDI_POST_DOMINATORS
);
644 sink_code_in_bb (EXIT_BLOCK_PTR
);
645 statistics_counter_event (cfun
, "Sunk statements", sink_stats
.sunk
);
646 free_dominance_info (CDI_POST_DOMINATORS
);
647 remove_fake_exit_edges ();
648 loop_optimizer_finalize ();
651 /* Gate and execute functions for PRE. */
656 execute_sink_code ();
663 return flag_tree_sink
!= 0;
666 struct gimple_opt_pass pass_sink_code
=
671 gate_sink
, /* gate */
672 do_sink
, /* execute */
675 0, /* static_pass_number */
676 TV_TREE_SINK
, /* tv_id */
677 PROP_no_crit_edges
| PROP_cfg
678 | PROP_ssa
, /* properties_required */
679 0, /* properties_provided */
680 0, /* properties_destroyed */
681 0, /* todo_flags_start */
685 | TODO_ggc_collect
/* todo_flags_finish */