Daily bump.
[official-gcc.git] / gcc / tree-ssa-sink.c
blobcd57baa0d99b8c03113df3bb2e7f33ee1e23a252
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)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.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"
33 #include "timevar.h"
34 #include "fibheap.h"
35 #include "hashtab.h"
36 #include "tree-iterator.h"
37 #include "real.h"
38 #include "alloc-pool.h"
39 #include "tree-pass.h"
40 #include "flags.h"
41 #include "bitmap.h"
42 #include "langhooks.h"
43 #include "cfgloop.h"
45 /* TODO:
46 1. Sinking store only using scalar promotion (IE without moving the RHS):
48 *q = p;
49 p = p + 1;
50 if (something)
51 *q = <not p>;
52 else
53 y = *q;
56 should become
57 sinktemp = p;
58 p = p + 1;
59 if (something)
60 *q = <not p>;
61 else
63 *q = sinktemp;
64 y = *q
66 Store copy propagation will take care of the store elimination above.
69 2. Sinking using Partial Dead Code Elimination. */
72 static struct
74 /* The number of statements sunk down the flowgraph by code sinking. */
75 int sunk;
77 } sink_stats;
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,
82 we return NULL. */
84 static basic_block
85 find_bb_for_arg (tree phi, tree def)
87 int i;
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)
93 if (foundone)
94 return NULL;
95 foundone = true;
96 result = PHI_ARG_EDGE (phi, i)->src;
98 return result;
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. */
109 static bool
110 all_immediate_uses_same_place (tree stmt)
112 tree firstuse = NULL_TREE;
113 ssa_op_iter op_iter;
114 imm_use_iterator imm_iter;
115 use_operand_p use_p;
116 tree var;
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);
124 else
125 if (firstuse != USE_STMT (use_p))
126 return false;
130 return true;
133 /* Some global stores don't necessarily have VDEF's of global variables,
134 but we still must avoid moving them around. */
136 bool
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
141 statements. */
142 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
144 tree lhs;
146 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_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):
153 foo (int *p, int i)
155 int x;
156 p_1 = (i_2 > 3) ? &x : p;
158 # x_4 = VDEF <x_3>
159 *p_1 = 5;
161 return 2;
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
167 variable.
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
172 is a global. */
173 lhs = GIMPLE_STMT_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
181 move this store. */
182 return true;
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))
188 return true;
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 = symbol_mem_tag (SSA_NAME_VAR (ptr));
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)))
203 return true;
206 else
207 gcc_unreachable ();
210 return false;
213 /* Find the nearest common dominator of all of the immediate uses in IMM. */
215 static basic_block
216 nearest_common_dominator_of_uses (tree stmt)
218 bitmap blocks = BITMAP_ALLOC (NULL);
219 basic_block commondom;
220 unsigned int j;
221 bitmap_iterator bi;
222 ssa_op_iter op_iter;
223 imm_use_iterator imm_iter;
224 use_operand_p use_p;
225 tree var;
227 bitmap_clear (blocks);
228 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
230 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
232 tree usestmt = USE_STMT (use_p);
233 basic_block useblock;
235 if (TREE_CODE (usestmt) == PHI_NODE)
237 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
239 useblock = PHI_ARG_EDGE (usestmt, idx)->src;
241 else
243 useblock = bb_for_stmt (usestmt);
246 /* Short circuit. Nothing dominates the entry block. */
247 if (useblock == ENTRY_BLOCK_PTR)
249 BITMAP_FREE (blocks);
250 return NULL;
252 bitmap_set_bit (blocks, useblock->index);
255 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
256 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
257 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
258 BASIC_BLOCK (j));
259 BITMAP_FREE (blocks);
260 return commondom;
263 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
264 determine the location to sink the statement to, if any.
265 Returns true if there is such location; in that case, TOBB is set to the
266 basic block of the location, and TOBSI points to the statement before
267 that STMT should be moved. */
269 static bool
270 statement_sink_location (tree stmt, basic_block frombb, basic_block *tobb,
271 block_stmt_iterator *tobsi)
273 tree use, def;
274 use_operand_p one_use = NULL_USE_OPERAND_P;
275 basic_block sinkbb;
276 use_operand_p use_p;
277 def_operand_p def_p;
278 ssa_op_iter iter;
279 stmt_ann_t ann;
280 tree rhs;
281 imm_use_iterator imm_iter;
283 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
285 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
287 break;
289 if (one_use != NULL_USE_OPERAND_P)
290 break;
293 /* Return if there are no immediate uses of this stmt. */
294 if (one_use == NULL_USE_OPERAND_P)
295 return false;
297 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
298 return false;
299 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
301 /* There are a few classes of things we can't or don't move, some because we
302 don't have code to handle it, some because it's not profitable and some
303 because it's not legal.
305 We can't sink things that may be global stores, at least not without
306 calculating a lot more information, because we may cause it to no longer
307 be seen by an external routine that needs it depending on where it gets
308 moved to.
310 We don't want to sink loads from memory.
312 We can't sink statements that end basic blocks without splitting the
313 incoming edge for the sink location to place it there.
315 We can't sink statements that have volatile operands.
317 We don't want to sink dead code, so anything with 0 immediate uses is not
318 sunk.
321 ann = stmt_ann (stmt);
322 if (stmt_ends_bb_p (stmt)
323 || TREE_SIDE_EFFECTS (rhs)
324 || TREE_CODE (rhs) == EXC_PTR_EXPR
325 || TREE_CODE (rhs) == FILTER_EXPR
326 || is_hidden_global_store (stmt)
327 || ann->has_volatile_ops
328 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
329 return false;
331 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
333 tree def = DEF_FROM_PTR (def_p);
334 if (is_global_var (SSA_NAME_VAR (def))
335 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
336 return false;
339 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
341 tree use = USE_FROM_PTR (use_p);
342 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
343 return false;
346 /* If all the immediate uses are not in the same place, find the nearest
347 common dominator of all the immediate uses. For PHI nodes, we have to
348 find the nearest common dominator of all of the predecessor blocks, since
349 that is where insertion would have to take place. */
350 if (!all_immediate_uses_same_place (stmt))
352 basic_block commondom = nearest_common_dominator_of_uses (stmt);
354 if (commondom == frombb)
355 return false;
357 /* Our common dominator has to be dominated by frombb in order to be a
358 trivially safe place to put this statement, since it has multiple
359 uses. */
360 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
361 return false;
363 /* It doesn't make sense to move to a dominator that post-dominates
364 frombb, because it means we've just moved it into a path that always
365 executes if frombb executes, instead of reducing the number of
366 executions . */
367 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
369 if (dump_file && (dump_flags & TDF_DETAILS))
370 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
371 return false;
374 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
375 return false;
376 if (dump_file && (dump_flags & TDF_DETAILS))
378 fprintf (dump_file, "Common dominator of all uses is %d\n",
379 commondom->index);
381 *tobb = commondom;
382 *tobsi = bsi_after_labels (commondom);
383 return true;
386 use = USE_STMT (one_use);
387 if (TREE_CODE (use) != PHI_NODE)
389 sinkbb = bb_for_stmt (use);
390 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
391 || sinkbb->loop_father != frombb->loop_father)
392 return false;
393 *tobb = sinkbb;
394 *tobsi = bsi_for_stmt (use);
395 return true;
398 /* Note that at this point, all uses must be in the same statement, so it
399 doesn't matter which def op we choose, pick the first one. */
400 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
401 break;
403 sinkbb = find_bb_for_arg (use, def);
404 if (!sinkbb)
405 return false;
407 /* This will happen when you have
408 a_3 = PHI <a_13, a_26>
410 a_26 = VDEF <a_3>
412 If the use is a phi, and is in the same bb as the def,
413 we can't sink it. */
415 if (bb_for_stmt (use) == frombb)
416 return false;
417 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
418 || sinkbb->loop_father != frombb->loop_father)
419 return false;
421 *tobb = sinkbb;
422 *tobsi = bsi_after_labels (sinkbb);
424 return true;
427 /* Perform code sinking on BB */
429 static void
430 sink_code_in_bb (basic_block bb)
432 basic_block son;
433 block_stmt_iterator bsi;
434 edge_iterator ei;
435 edge e;
436 bool last = true;
438 /* If this block doesn't dominate anything, there can't be any place to sink
439 the statements to. */
440 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
441 goto earlyout;
443 /* We can't move things across abnormal edges, so don't try. */
444 FOR_EACH_EDGE (e, ei, bb->succs)
445 if (e->flags & EDGE_ABNORMAL)
446 goto earlyout;
448 for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
450 tree stmt = bsi_stmt (bsi);
451 block_stmt_iterator tobsi;
452 basic_block tobb;
454 if (!statement_sink_location (stmt, bb, &tobb, &tobsi))
456 if (!bsi_end_p (bsi))
457 bsi_prev (&bsi);
458 last = false;
459 continue;
461 if (dump_file)
463 fprintf (dump_file, "Sinking ");
464 print_generic_expr (dump_file, stmt, TDF_VOPS);
465 fprintf (dump_file, " from bb %d to bb %d\n",
466 bb->index, tobb->index);
469 /* If this is the end of the basic block, we need to insert at the end
470 of the basic block. */
471 if (bsi_end_p (tobsi))
472 bsi_move_to_bb_end (&bsi, tobb);
473 else
474 bsi_move_before (&bsi, &tobsi);
476 sink_stats.sunk++;
478 /* If we've just removed the last statement of the BB, the
479 bsi_end_p() test below would fail, but bsi_prev() would have
480 succeeded, and we want it to succeed. So we keep track of
481 whether we're at the last statement and pick up the new last
482 statement. */
483 if (last)
485 bsi = bsi_last (bb);
486 continue;
489 last = false;
490 if (!bsi_end_p (bsi))
491 bsi_prev (&bsi);
494 earlyout:
495 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
496 son;
497 son = next_dom_son (CDI_POST_DOMINATORS, son))
499 sink_code_in_bb (son);
503 /* Perform code sinking.
504 This moves code down the flowgraph when we know it would be
505 profitable to do so, or it wouldn't increase the number of
506 executions of the statement.
508 IE given
510 a_1 = b + c;
511 if (<something>)
514 else
516 foo (&b, &c);
517 a_5 = b + c;
519 a_6 = PHI (a_5, a_1);
520 USE a_6.
522 we'll transform this into:
524 if (<something>)
526 a_1 = b + c;
528 else
530 foo (&b, &c);
531 a_5 = b + c;
533 a_6 = PHI (a_5, a_1);
534 USE a_6.
536 Note that this reduces the number of computations of a = b + c to 1
537 when we take the else edge, instead of 2.
539 static void
540 execute_sink_code (void)
542 loop_optimizer_init (LOOPS_NORMAL);
544 connect_infinite_loops_to_exit ();
545 memset (&sink_stats, 0, sizeof (sink_stats));
546 calculate_dominance_info (CDI_DOMINATORS);
547 calculate_dominance_info (CDI_POST_DOMINATORS);
548 sink_code_in_bb (EXIT_BLOCK_PTR);
549 if (dump_file && (dump_flags & TDF_STATS))
550 fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
551 free_dominance_info (CDI_POST_DOMINATORS);
552 remove_fake_exit_edges ();
553 loop_optimizer_finalize ();
556 /* Gate and execute functions for PRE. */
558 static unsigned int
559 do_sink (void)
561 execute_sink_code ();
562 return 0;
565 static bool
566 gate_sink (void)
568 return flag_tree_sink != 0;
571 struct tree_opt_pass pass_sink_code =
573 "sink", /* name */
574 gate_sink, /* gate */
575 do_sink, /* execute */
576 NULL, /* sub */
577 NULL, /* next */
578 0, /* static_pass_number */
579 TV_TREE_SINK, /* tv_id */
580 PROP_no_crit_edges | PROP_cfg
581 | PROP_ssa | PROP_alias, /* properties_required */
582 0, /* properties_provided */
583 0, /* properties_destroyed */
584 0, /* todo_flags_start */
585 TODO_update_ssa
586 | TODO_dump_func
587 | TODO_ggc_collect
588 | TODO_verify_ssa, /* todo_flags_finish */
589 0 /* letter */