1 /* Code sinking for trees
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
4
5 This file is part of GCC.
6
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.
11
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.
16
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. */
21
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"
45
46 /* TODO:
47 1. Sinking store only using scalar promotion (IE without moving the RHS):
48
49 *q = p;
50 p = p + 1;
51 if (something)
52 *q = <not p>;
53 else
54 y = *q;
55
56
57 should become
58 sinktemp = p;
59 p = p + 1;
60 if (something)
61 *q = <not p>;
62 else
63 {
64 *q = sinktemp;
65 y = *q
66 }
67 Store copy propagation will take care of the store elimination above.
68
69
70 2. Sinking using Partial Dead Code Elimination. */
71
72
73 static struct
74 {
75 /* The number of statements sunk down the flowgraph by code sinking. */
76 int sunk;
77
78 } sink_stats;
79
80
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. */
84
85 static basic_block
find_bb_for_arg(tree phi,tree def)86 find_bb_for_arg (tree phi, tree def)
87 {
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)
93 {
94 if (foundone)
95 return NULL;
96 foundone = true;
97 result = PHI_ARG_EDGE (phi, i)->src;
98 }
99 return result;
100 }
101
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. */
109
110 static bool
all_immediate_uses_same_place(tree stmt)111 all_immediate_uses_same_place (tree stmt)
112 {
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;
118
119 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
120 {
121 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
122 {
123 if (firstuse == NULL_TREE)
124 firstuse = USE_STMT (use_p);
125 else
126 if (firstuse != USE_STMT (use_p))
127 return false;
128 }
129 }
130
131 return true;
132 }
133
134 /* Some global stores don't necessarily have V_MAY_DEF's of global variables,
135 but we still must avoid moving them around. */
136
137 bool
is_hidden_global_store(tree stmt)138 is_hidden_global_store (tree stmt)
139 {
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))
144 {
145 tree lhs;
146
147 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
148
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):
153
154 foo (int *p, int i)
155 {
156 int x;
157 p_1 = (i_2 > 3) ? &x : p;
158
159 # x_4 = V_MAY_DEF <x_3>
160 *p_1 = 5;
161
162 return 2;
163 }
164
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.
169
170 Therefore, we check the base address of the LHS. If the
171 address is a pointer, we check if its name tag or type tag is
172 a global variable. Otherwise, we check if the base variable
173 is a global. */
174 lhs = TREE_OPERAND (stmt, 0);
175 if (REFERENCE_CLASS_P (lhs))
176 lhs = get_base_address (lhs);
177
178 if (lhs == NULL_TREE)
179 {
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;
184 }
185 else if (DECL_P (lhs))
186 {
187 /* If the store is to a global symbol, we need to keep it. */
188 if (is_global_var (lhs))
189 return true;
190
191 }
192 else if (INDIRECT_REF_P (lhs))
193 {
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 tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
198
199 /* If either the name tag or the type tag for PTR is a
200 global variable, then the store is necessary. */
201 if ((nmt && is_global_var (nmt))
202 || (tmt && is_global_var (tmt)))
203 {
204 return true;
205 }
206 }
207 else
208 gcc_unreachable ();
209 }
210 return false;
211 }
212
213 /* Find the nearest common dominator of all of the immediate uses in IMM. */
214
215 static basic_block
nearest_common_dominator_of_uses(tree stmt)216 nearest_common_dominator_of_uses (tree stmt)
217 {
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;
226
227 bitmap_clear (blocks);
228 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
229 {
230 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
231 {
232 tree usestmt = USE_STMT (use_p);
233 basic_block useblock;
234
235 if (TREE_CODE (usestmt) == PHI_NODE)
236 {
237 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
238
239 useblock = PHI_ARG_EDGE (usestmt, idx)->src;
240 }
241 else
242 {
243 useblock = bb_for_stmt (usestmt);
244 }
245
246 /* Short circuit. Nothing dominates the entry block. */
247 if (useblock == ENTRY_BLOCK_PTR)
248 {
249 BITMAP_FREE (blocks);
250 return NULL;
251 }
252 bitmap_set_bit (blocks, useblock->index);
253 }
254 }
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;
261 }
262
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 Return the basic block to sink it to, or NULL if we should not sink
266 it. */
267
268 static tree
statement_sink_location(tree stmt,basic_block frombb)269 statement_sink_location (tree stmt, basic_block frombb)
270 {
271 tree use, def;
272 use_operand_p one_use = NULL_USE_OPERAND_P;
273 basic_block sinkbb;
274 use_operand_p use_p;
275 def_operand_p def_p;
276 ssa_op_iter iter;
277 stmt_ann_t ann;
278 tree rhs;
279 imm_use_iterator imm_iter;
280
281 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
282 {
283 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
284 {
285 break;
286 }
287 if (one_use != NULL_USE_OPERAND_P)
288 break;
289 }
290
291 /* Return if there are no immediate uses of this stmt. */
292 if (one_use == NULL_USE_OPERAND_P)
293 return NULL;
294
295 if (TREE_CODE (stmt) != MODIFY_EXPR)
296 return NULL;
297 rhs = TREE_OPERAND (stmt, 1);
298
299 /* There are a few classes of things we can't or don't move, some because we
300 don't have code to handle it, some because it's not profitable and some
301 because it's not legal.
302
303 We can't sink things that may be global stores, at least not without
304 calculating a lot more information, because we may cause it to no longer
305 be seen by an external routine that needs it depending on where it gets
306 moved to.
307
308 We don't want to sink loads from memory.
309
310 We can't sink statements that end basic blocks without splitting the
311 incoming edge for the sink location to place it there.
312
313 We can't sink statements that have volatile operands.
314
315 We don't want to sink dead code, so anything with 0 immediate uses is not
316 sunk.
317
318 */
319 ann = stmt_ann (stmt);
320 if (stmt_ends_bb_p (stmt)
321 || TREE_SIDE_EFFECTS (rhs)
322 || TREE_CODE (rhs) == EXC_PTR_EXPR
323 || TREE_CODE (rhs) == FILTER_EXPR
324 || is_hidden_global_store (stmt)
325 || ann->has_volatile_ops
326 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
327 return NULL;
328
329 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
330 {
331 tree def = DEF_FROM_PTR (def_p);
332 if (is_global_var (SSA_NAME_VAR (def))
333 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
334 return NULL;
335 }
336
337 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
338 {
339 tree use = USE_FROM_PTR (use_p);
340 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
341 return NULL;
342 }
343
344 /* If all the immediate uses are not in the same place, find the nearest
345 common dominator of all the immediate uses. For PHI nodes, we have to
346 find the nearest common dominator of all of the predecessor blocks, since
347 that is where insertion would have to take place. */
348 if (!all_immediate_uses_same_place (stmt))
349 {
350 basic_block commondom = nearest_common_dominator_of_uses (stmt);
351
352 if (commondom == frombb)
353 return NULL;
354
355 /* Our common dominator has to be dominated by frombb in order to be a
356 trivially safe place to put this statement, since it has multiple
357 uses. */
358 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
359 return NULL;
360
361 /* It doesn't make sense to move to a dominator that post-dominates
362 frombb, because it means we've just moved it into a path that always
363 executes if frombb executes, instead of reducing the number of
364 executions . */
365 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
366 {
367 if (dump_file && (dump_flags & TDF_DETAILS))
368 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
369 return NULL;
370 }
371
372 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
373 return NULL;
374 if (dump_file && (dump_flags & TDF_DETAILS))
375 {
376 fprintf (dump_file, "Common dominator of all uses is %d\n",
377 commondom->index);
378 }
379 return first_stmt (commondom);
380 }
381
382 use = USE_STMT (one_use);
383 if (TREE_CODE (use) != PHI_NODE)
384 {
385 sinkbb = bb_for_stmt (use);
386 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
387 || sinkbb->loop_father != frombb->loop_father)
388 return NULL;
389 return use;
390 }
391
392 /* Note that at this point, all uses must be in the same statement, so it
393 doesn't matter which def op we choose, pick the first one. */
394 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
395 break;
396
397
398 sinkbb = find_bb_for_arg (use, def);
399 if (!sinkbb)
400 return NULL;
401
402 /* This will happen when you have
403 a_3 = PHI <a_13, a_26>
404
405 a_26 = V_MAY_DEF <a_3>
406
407 If the use is a phi, and is in the same bb as the def,
408 we can't sink it. */
409
410 if (bb_for_stmt (use) == frombb)
411 return NULL;
412 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
413 || sinkbb->loop_father != frombb->loop_father)
414 return NULL;
415
416 return first_stmt (sinkbb);
417 }
418
419 /* Perform code sinking on BB */
420
421 static void
sink_code_in_bb(basic_block bb)422 sink_code_in_bb (basic_block bb)
423 {
424 basic_block son;
425 block_stmt_iterator bsi;
426 edge_iterator ei;
427 edge e;
428
429 /* If this block doesn't dominate anything, there can't be any place to sink
430 the statements to. */
431 if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
432 goto earlyout;
433
434 /* We can't move things across abnormal edges, so don't try. */
435 FOR_EACH_EDGE (e, ei, bb->succs)
436 if (e->flags & EDGE_ABNORMAL)
437 goto earlyout;
438
439 for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
440 {
441 tree stmt = bsi_stmt (bsi);
442 block_stmt_iterator tobsi;
443 tree sinkstmt;
444
445 sinkstmt = statement_sink_location (stmt, bb);
446 if (!sinkstmt)
447 {
448 if (!bsi_end_p (bsi))
449 bsi_prev (&bsi);
450 continue;
451 }
452 if (dump_file)
453 {
454 fprintf (dump_file, "Sinking ");
455 print_generic_expr (dump_file, stmt, TDF_VOPS);
456 fprintf (dump_file, " from bb %d to bb %d\n",
457 bb->index, bb_for_stmt (sinkstmt)->index);
458 }
459 tobsi = bsi_for_stmt (sinkstmt);
460 /* Find the first non-label. */
461 while (!bsi_end_p (tobsi)
462 && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
463 bsi_next (&tobsi);
464
465 /* If this is the end of the basic block, we need to insert at the end
466 of the basic block. */
467 if (bsi_end_p (tobsi))
468 bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
469 else
470 bsi_move_before (&bsi, &tobsi);
471
472 sink_stats.sunk++;
473 if (!bsi_end_p (bsi))
474 bsi_prev (&bsi);
475
476 }
477 earlyout:
478 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
479 son;
480 son = next_dom_son (CDI_POST_DOMINATORS, son))
481 {
482 sink_code_in_bb (son);
483 }
484 }
485
486 /* Perform code sinking.
487 This moves code down the flowgraph when we know it would be
488 profitable to do so, or it wouldn't increase the number of
489 executions of the statement.
490
491 IE given
492
493 a_1 = b + c;
494 if (<something>)
495 {
496 }
497 else
498 {
499 foo (&b, &c);
500 a_5 = b + c;
501 }
502 a_6 = PHI (a_5, a_1);
503 USE a_6.
504
505 we'll transform this into:
506
507 if (<something>)
508 {
509 a_1 = b + c;
510 }
511 else
512 {
513 foo (&b, &c);
514 a_5 = b + c;
515 }
516 a_6 = PHI (a_5, a_1);
517 USE a_6.
518
519 Note that this reduces the number of computations of a = b + c to 1
520 when we take the else edge, instead of 2.
521 */
522 static void
execute_sink_code(void)523 execute_sink_code (void)
524 {
525 struct loops *loops = loop_optimizer_init (dump_file);
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, dump_file);
535 }
536
537 /* Gate and execute functions for PRE. */
538
539 static void
do_sink(void)540 do_sink (void)
541 {
542 execute_sink_code ();
543 }
544
545 static bool
gate_sink(void)546 gate_sink (void)
547 {
548 return flag_tree_sink != 0;
549 }
550
551 struct tree_opt_pass pass_sink_code =
552 {
553 "sink", /* name */
554 gate_sink, /* gate */
555 do_sink, /* execute */
556 NULL, /* sub */
557 NULL, /* next */
558 0, /* static_pass_number */
559 TV_TREE_SINK, /* tv_id */
560 PROP_no_crit_edges | PROP_cfg
561 | PROP_ssa | PROP_alias, /* properties_required */
562 0, /* properties_provided */
563 0, /* properties_destroyed */
564 0, /* todo_flags_start */
565 TODO_update_ssa
566 | TODO_dump_func
567 | TODO_ggc_collect
568 | TODO_verify_ssa, /* todo_flags_finish */
569 0 /* letter */
570 };
571