Makefile.am: Add install-pdf target as copied from automake v1.10 rules.
[official-gcc.git] / gcc / tree-ssa-sink.c
blobb30c23d65f8c6e224efbfa61e33b544515f8f8e1
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)
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 COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
32 #include "tree-gimple.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "fibheap.h"
36 #include "hashtab.h"
37 #include "tree-iterator.h"
38 #include "real.h"
39 #include "alloc-pool.h"
40 #include "tree-pass.h"
41 #include "flags.h"
42 #include "bitmap.h"
43 #include "langhooks.h"
44 #include "cfgloop.h"
46 /* TODO:
47 1. Sinking store only using scalar promotion (IE without moving the RHS):
49 *q = p;
50 p = p + 1;
51 if (something)
52 *q = <not p>;
53 else
54 y = *q;
57 should become
58 sinktemp = p;
59 p = p + 1;
60 if (something)
61 *q = <not p>;
62 else
64 *q = sinktemp;
65 y = *q
67 Store copy propagation will take care of the store elimination above.
70 2. Sinking using Partial Dead Code Elimination. */
73 static struct
75 /* The number of statements sunk down the flowgraph by code sinking. */
76 int sunk;
78 } sink_stats;
81 /* Given a PHI, and one of its arguments (DEF), find the edge for
82 that argument and return it. If the argument occurs twice in the PHI node,
83 we return NULL. */
85 static basic_block
86 find_bb_for_arg (tree phi, tree def)
88 int i;
89 bool foundone = false;
90 basic_block result = NULL;
91 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
92 if (PHI_ARG_DEF (phi, i) == def)
94 if (foundone)
95 return NULL;
96 foundone = true;
97 result = PHI_ARG_EDGE (phi, i)->src;
99 return result;
102 /* When the first immediate use is in a statement, then return true if all
103 immediate uses in IMM are in the same statement.
104 We could also do the case where the first immediate use is in a phi node,
105 and all the other uses are in phis in the same basic block, but this
106 requires some expensive checking later (you have to make sure no def/vdef
107 in the statement occurs for multiple edges in the various phi nodes it's
108 used in, so that you only have one place you can sink it to. */
110 static bool
111 all_immediate_uses_same_place (tree stmt)
113 tree firstuse = NULL_TREE;
114 ssa_op_iter op_iter;
115 imm_use_iterator imm_iter;
116 use_operand_p use_p;
117 tree var;
119 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
121 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
123 if (firstuse == NULL_TREE)
124 firstuse = USE_STMT (use_p);
125 else
126 if (firstuse != USE_STMT (use_p))
127 return false;
131 return true;
134 /* Some global stores don't necessarily have VDEF's of global variables,
135 but we still must avoid moving them around. */
137 bool
138 is_hidden_global_store (tree stmt)
140 /* Check virtual definitions. If we get here, the only virtual
141 definitions we should see are those generated by assignment
142 statements. */
143 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
145 tree lhs;
147 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
149 /* Note that we must not check the individual virtual operands
150 here. In particular, if this is an aliased store, we could
151 end up with something like the following (SSA notation
152 redacted for brevity):
154 foo (int *p, int i)
156 int x;
157 p_1 = (i_2 > 3) ? &x : p;
159 # x_4 = VDEF <x_3>
160 *p_1 = 5;
162 return 2;
165 Notice that the store to '*p_1' should be preserved, if we
166 were to check the virtual definitions in that store, we would
167 not mark it needed. This is because 'x' is not a global
168 variable.
170 Therefore, we check the base address of the LHS. If the
171 address is a pointer, we check if its name tag or symbol tag is
172 a global variable. Otherwise, we check if the base variable
173 is a global. */
174 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
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
182 move this store. */
183 return true;
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))
189 return true;
192 else if (INDIRECT_REF_P (lhs))
194 tree ptr = TREE_OPERAND (lhs, 0);
195 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
196 tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
197 tree smt = symbol_mem_tag (SSA_NAME_VAR (ptr));
199 /* If either the name tag or the symbol tag for PTR is a
200 global variable, then the store is necessary. */
201 if ((nmt && is_global_var (nmt))
202 || (smt && is_global_var (smt)))
204 return true;
207 else
208 gcc_unreachable ();
211 return false;
214 /* Find the nearest common dominator of all of the immediate uses in IMM. */
216 static basic_block
217 nearest_common_dominator_of_uses (tree stmt)
219 bitmap blocks = BITMAP_ALLOC (NULL);
220 basic_block commondom;
221 unsigned int j;
222 bitmap_iterator bi;
223 ssa_op_iter op_iter;
224 imm_use_iterator imm_iter;
225 use_operand_p use_p;
226 tree var;
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;
242 else
244 useblock = bb_for_stmt (usestmt);
247 /* Short circuit. Nothing dominates the entry block. */
248 if (useblock == ENTRY_BLOCK_PTR)
250 BITMAP_FREE (blocks);
251 return NULL;
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,
259 BASIC_BLOCK (j));
260 BITMAP_FREE (blocks);
261 return commondom;
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
267 it. */
269 static tree
270 statement_sink_location (tree stmt, basic_block frombb)
272 tree use, def;
273 use_operand_p one_use = NULL_USE_OPERAND_P;
274 basic_block sinkbb;
275 use_operand_p use_p;
276 def_operand_p def_p;
277 ssa_op_iter iter;
278 stmt_ann_t ann;
279 tree rhs;
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)
286 break;
288 if (one_use != NULL_USE_OPERAND_P)
289 break;
292 /* Return if there are no immediate uses of this stmt. */
293 if (one_use == NULL_USE_OPERAND_P)
294 return NULL;
296 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
297 return NULL;
298 rhs = GIMPLE_STMT_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
307 moved to.
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
317 sunk.
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))
328 return NULL;
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))
335 return NULL;
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))
342 return NULL;
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)
354 return NULL;
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
358 uses. */
359 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
360 return NULL;
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
365 executions . */
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");
370 return NULL;
373 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
374 return NULL;
375 if (dump_file && (dump_flags & TDF_DETAILS))
377 fprintf (dump_file, "Common dominator of all uses is %d\n",
378 commondom->index);
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)
389 return NULL;
390 return use;
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)
396 break;
399 sinkbb = find_bb_for_arg (use, def);
400 if (!sinkbb)
401 return NULL;
403 /* This will happen when you have
404 a_3 = PHI <a_13, a_26>
406 a_26 = VDEF <a_3>
408 If the use is a phi, and is in the same bb as the def,
409 we can't sink it. */
411 if (bb_for_stmt (use) == frombb)
412 return NULL;
413 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
414 || sinkbb->loop_father != frombb->loop_father)
415 return NULL;
417 return first_stmt (sinkbb);
420 /* Perform code sinking on BB */
422 static void
423 sink_code_in_bb (basic_block bb)
425 basic_block son;
426 block_stmt_iterator bsi;
427 edge_iterator ei;
428 edge e;
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)
433 goto earlyout;
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)
438 goto earlyout;
440 for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
442 tree stmt = bsi_stmt (bsi);
443 block_stmt_iterator tobsi;
444 tree sinkstmt;
446 sinkstmt = statement_sink_location (stmt, bb);
447 if (!sinkstmt)
449 if (!bsi_end_p (bsi))
450 bsi_prev (&bsi);
451 continue;
453 if (dump_file)
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)
464 bsi_next (&tobsi);
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));
470 else
471 bsi_move_before (&bsi, &tobsi);
473 sink_stats.sunk++;
474 if (!bsi_end_p (bsi))
475 bsi_prev (&bsi);
478 earlyout:
479 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
480 son;
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.
492 IE given
494 a_1 = b + c;
495 if (<something>)
498 else
500 foo (&b, &c);
501 a_5 = b + c;
503 a_6 = PHI (a_5, a_1);
504 USE a_6.
506 we'll transform this into:
508 if (<something>)
510 a_1 = b + c;
512 else
514 foo (&b, &c);
515 a_5 = b + c;
517 a_6 = PHI (a_5, a_1);
518 USE a_6.
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.
523 static void
524 execute_sink_code (void)
526 loop_optimizer_init (LOOPS_NORMAL);
528 connect_infinite_loops_to_exit ();
529 memset (&sink_stats, 0, sizeof (sink_stats));
530 calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
531 sink_code_in_bb (EXIT_BLOCK_PTR);
532 if (dump_file && (dump_flags & TDF_STATS))
533 fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
534 free_dominance_info (CDI_POST_DOMINATORS);
535 remove_fake_exit_edges ();
536 loop_optimizer_finalize ();
539 /* Gate and execute functions for PRE. */
541 static unsigned int
542 do_sink (void)
544 execute_sink_code ();
545 return 0;
548 static bool
549 gate_sink (void)
551 return flag_tree_sink != 0;
554 struct tree_opt_pass pass_sink_code =
556 "sink", /* name */
557 gate_sink, /* gate */
558 do_sink, /* execute */
559 NULL, /* sub */
560 NULL, /* next */
561 0, /* static_pass_number */
562 TV_TREE_SINK, /* tv_id */
563 PROP_no_crit_edges | PROP_cfg
564 | PROP_ssa | PROP_alias, /* properties_required */
565 0, /* properties_provided */
566 0, /* properties_destroyed */
567 0, /* todo_flags_start */
568 TODO_update_ssa
569 | TODO_dump_func
570 | TODO_ggc_collect
571 | TODO_verify_ssa, /* todo_flags_finish */
572 0 /* letter */