1 /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "gimple-pretty-print.h"
28 #include "bitmap.h"
29 #include "tree-flow.h"
30 #include "dumpfile.h"
31 #include "tree-ssa-live.h"
32 #include "flags.h"
33
34
35 /* Temporary Expression Replacement (TER)
36
37 Replace SSA version variables during out-of-ssa with their defining
38 expression if there is only one use of the variable.
39
40 This pass is required in order for the RTL expansion pass to see larger
41 chunks of code. This allows it to make better choices on RTL pattern
42 selection. When expand is rewritten and merged with out-of-ssa, and
43 understands SSA, this should be eliminated.
44
45 A pass is made through the function, one block at a time. No cross block
46 information is tracked.
47
48 Variables which only have one use, and whose defining stmt is considered
49 a replaceable expression (see is_replaceable_p) are tracked to see whether
50 they can be replaced at their use location.
51
52 n_12 = C * 10
53 a_2 = b_5 + 6
54 v_9 = a_2 * n_12
55
56 if there are the only use of n_12 and a_2, TER will substitute in their
57 expressions in v_9, and end up with:
58
59 v_9 = (b_5 + 6) * (C * 10)
60
61 which will then have the ssa_name assigned to regular variables, and the
62 resulting code which will be passed to the expander looks something like:
63
64 v = (b + 6) * (C * 10)
65
66
67 This requires ensuring that none of the variables used by the expression
68 change between the def point and where it is used. Furthermore, if any
69 of the ssa_names used in this expression are themselves replaceable, we
70 have to ensure none of that expressions' arguments change either.
71 Although SSA_NAMES themselves don't change, this pass is performed after
72 coalescing has coalesced different SSA_NAMES together, so there could be a
73 definition of an SSA_NAME which is coalesced with a use that causes a
74 problem, i.e.,
75
76 PHI b_5 = <b_8(2), b_14(1)>
77 <...>
78 a_2 = b_5 + 6
79 b_8 = c_4 + 4
80 v_9 = a_2 * n_12
81 <...>
82
83 If b_5, b_8 and b_14 are all coalesced together...
84 The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
85 because b_8 is in fact killing the value of b_5 since they share a partition
86 and will be assigned the same memory or register location.
87
88 TER implements this but stepping through the instructions in a block and
89 tracking potential expressions for replacement, and the partitions they are
90 dependent on. Expressions are represented by the SSA_NAME_VERSION of the
91 DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS.
92
93 When a stmt is determined to be a possible replacement expression, the
94 following steps are taken:
95
96 EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
97 def and any uses in the expression. non-NULL means the expression is being
98 tracked. The UID's themselves are used to prevent TER substitution into
99 accumulating sequences, i.e.,
100
101 x = x + y
102 x = x + z
103 x = x + w
104 etc.
105 this can result in very large expressions which don't accomplish anything
106 see PR tree-optimization/17549.
107
108 PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
109 partition which is used in the expression. This is primarily used to remove
110 an expression from the partition kill lists when a decision is made whether
111 to replace it or not. This is indexed by ssa version number as well, and
112 indicates a partition number. virtual operands are not tracked individually,
113 but they are summarized by an artificial partition called VIRTUAL_PARTITION.
114 This means a MAY or MUST def will kill *ALL* expressions that are dependent
115 on a virtual operand.
116 Note that the EXPR_DECL_UID and this bitmap represent very similar
117 information, but the info in one is not easy to obtain from the other.
118
119 KILL_LIST is yet another bitmap array, this time it is indexed by partition
120 number, and represents a list of active expressions which will will no
121 longer be valid if a definition into this partition takes place.
122
123 PARTITION_IN_USE is simply a bitmap which is used to track which partitions
124 currently have something in their kill list. This is used at the end of
125 a block to clear out the KILL_LIST bitmaps at the end of each block.
126
127 NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
128 dependencies which will be reused by the current definition. All the uses
129 on an expression are processed before anything else is done. If a use is
130 determined to be a replaceable expression AND the current stmt is also going
131 to be replaceable, all the dependencies of this replaceable use will be
132 picked up by the current stmt's expression. Rather than recreate them, they
133 are simply copied here and then copied into the new expression when it is
134 processed.
135
136 a_2 = b_5 + 6
137 v_8 = a_2 + c_4
138
139 a_2's expression 'b_5 + 6' is determined to be replaceable at the use
140 location. It is dependent on the partition 'b_5' is in. This is cached into
141 the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
142 replaceability, it is a candidate, and it is dependent on the partition
143 b_5 is in *NOT* a_2, as well as c_4's partition.
144
145 if v_8 is also replaceable:
146
147 x_9 = v_8 * 5
148
149 x_9 is dependent on partitions b_5, and c_4
150
151 if a statement is found which has either of those partitions written to
152 before x_9 is used, then x_9 itself is NOT replaceable. */
153
154
155 /* Temporary Expression Replacement (TER) table information. */
156
157 typedef struct temp_expr_table_d
158 {
159 var_map map;
160 bitmap *partition_dependencies; /* Partitions expr is dependent on. */
161 bitmap replaceable_expressions; /* Replacement expression table. */
162 bitmap *expr_decl_uids; /* Base uids of exprs. */
163 bitmap *kill_list; /* Expr's killed by a partition. */
164 int virtual_partition; /* Pseudo partition for virtual ops. */
165 bitmap partition_in_use; /* Partitions with kill entries. */
166 bitmap new_replaceable_dependencies; /* Holding place for pending dep's. */
167 int *num_in_part; /* # of ssa_names in a partition. */
168 int *call_cnt; /* Call count at definition. */
169 } *temp_expr_table_p;
170
171 /* Used to indicate a dependency on VDEFs. */
172 #define VIRTUAL_PARTITION(table) (table->virtual_partition)
173
174 /* A place for the many, many bitmaps we create. */
175 static bitmap_obstack ter_bitmap_obstack;
176
177 #ifdef ENABLE_CHECKING
178 extern void debug_ter (FILE *, temp_expr_table_p);
179 #endif
180
181
182 /* Create a new TER table for MAP. */
183
184 static temp_expr_table_p
new_temp_expr_table(var_map map)185 new_temp_expr_table (var_map map)
186 {
187 temp_expr_table_p t;
188 unsigned x;
189
190 t = XNEW (struct temp_expr_table_d);
191 t->map = map;
192
193 t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
194 t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
195 t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
196
197 t->partition_in_use = BITMAP_ALLOC (&ter_bitmap_obstack);
198
199 t->virtual_partition = num_var_partitions (map);
200 t->new_replaceable_dependencies = BITMAP_ALLOC (&ter_bitmap_obstack);
201
202 t->replaceable_expressions = NULL;
203 t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
204 for (x = 1; x < num_ssa_names; x++)
205 {
206 int p;
207 tree name = ssa_name (x);
208 if (!name)
209 continue;
210 p = var_to_partition (map, name);
211 if (p != NO_PARTITION)
212 t->num_in_part[p]++;
213 }
214 t->call_cnt = XCNEWVEC (int, num_ssa_names + 1);
215
216 return t;
217 }
218
219
220 /* Free TER table T. If there are valid replacements, return the expression
221 vector. */
222
223 static bitmap
free_temp_expr_table(temp_expr_table_p t)224 free_temp_expr_table (temp_expr_table_p t)
225 {
226 bitmap ret = NULL;
227
228 #ifdef ENABLE_CHECKING
229 unsigned x;
230 for (x = 0; x <= num_var_partitions (t->map); x++)
231 gcc_assert (!t->kill_list[x]);
232 for (x = 0; x < num_ssa_names; x++)
233 {
234 gcc_assert (t->expr_decl_uids[x] == NULL);
235 gcc_assert (t->partition_dependencies[x] == NULL);
236 }
237 #endif
238
239 BITMAP_FREE (t->partition_in_use);
240 BITMAP_FREE (t->new_replaceable_dependencies);
241
242 free (t->expr_decl_uids);
243 free (t->kill_list);
244 free (t->partition_dependencies);
245 free (t->num_in_part);
246 free (t->call_cnt);
247
248 if (t->replaceable_expressions)
249 ret = t->replaceable_expressions;
250
251 free (t);
252 return ret;
253 }
254
255
256 /* Return TRUE if VERSION is to be replaced by an expression in TAB. */
257
258 static inline bool
version_to_be_replaced_p(temp_expr_table_p tab,int version)259 version_to_be_replaced_p (temp_expr_table_p tab, int version)
260 {
261 if (!tab->replaceable_expressions)
262 return false;
263 return bitmap_bit_p (tab->replaceable_expressions, version);
264 }
265
266
267 /* Add partition P to the list if partitions VERSION is dependent on. TAB is
268 the expression table */
269
270 static inline void
make_dependent_on_partition(temp_expr_table_p tab,int version,int p)271 make_dependent_on_partition (temp_expr_table_p tab, int version, int p)
272 {
273 if (!tab->partition_dependencies[version])
274 tab->partition_dependencies[version] = BITMAP_ALLOC (&ter_bitmap_obstack);
275
276 bitmap_set_bit (tab->partition_dependencies[version], p);
277 }
278
279
280 /* Add VER to the kill list for P. TAB is the expression table */
281
282 static inline void
add_to_partition_kill_list(temp_expr_table_p tab,int p,int ver)283 add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver)
284 {
285 if (!tab->kill_list[p])
286 {
287 tab->kill_list[p] = BITMAP_ALLOC (&ter_bitmap_obstack);
288 bitmap_set_bit (tab->partition_in_use, p);
289 }
290 bitmap_set_bit (tab->kill_list[p], ver);
291 }
292
293
294 /* Remove VER from the partition kill list for P. TAB is the expression
295 table. */
296
297 static inline void
remove_from_partition_kill_list(temp_expr_table_p tab,int p,int version)298 remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version)
299 {
300 gcc_checking_assert (tab->kill_list[p]);
301 bitmap_clear_bit (tab->kill_list[p], version);
302 if (bitmap_empty_p (tab->kill_list[p]))
303 {
304 bitmap_clear_bit (tab->partition_in_use, p);
305 BITMAP_FREE (tab->kill_list[p]);
306 }
307 }
308
309
310 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is
311 replaceable by an expression, add a dependence each of the elements of the
312 expression. These are contained in the new_replaceable list. TAB is the
313 expression table. */
314
315 static void
add_dependence(temp_expr_table_p tab,int version,tree var)316 add_dependence (temp_expr_table_p tab, int version, tree var)
317 {
318 int i;
319 bitmap_iterator bi;
320 unsigned x;
321
322 i = SSA_NAME_VERSION (var);
323 if (version_to_be_replaced_p (tab, i))
324 {
325 if (!bitmap_empty_p (tab->new_replaceable_dependencies))
326 {
327 /* Version will now be killed by a write to any partition the
328 substituted expression would have been killed by. */
329 EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
330 add_to_partition_kill_list (tab, x, version);
331
332 /* Rather than set partition_dependencies and in_use lists bit by
333 bit, simply OR in the new_replaceable_dependencies bits. */
334 if (!tab->partition_dependencies[version])
335 tab->partition_dependencies[version] =
336 BITMAP_ALLOC (&ter_bitmap_obstack);
337 bitmap_ior_into (tab->partition_dependencies[version],
338 tab->new_replaceable_dependencies);
339 bitmap_ior_into (tab->partition_in_use,
340 tab->new_replaceable_dependencies);
341 /* It is only necessary to add these once. */
342 bitmap_clear (tab->new_replaceable_dependencies);
343 }
344 }
345 else
346 {
347 i = var_to_partition (tab->map, var);
348 gcc_checking_assert (i != NO_PARTITION);
349 gcc_checking_assert (tab->num_in_part[i] != 0);
350 /* Only dependencies on ssa_names which are coalesced with something need
351 to be tracked. Partitions with containing only a single SSA_NAME
352 *cannot* have their value changed. */
353 if (tab->num_in_part[i] > 1)
354 {
355 add_to_partition_kill_list (tab, i, version);
356 make_dependent_on_partition (tab, version, i);
357 }
358 }
359 }
360
361
362 /* Return TRUE if expression STMT is suitable for replacement.
363 TER is true if is_replaceable_p is called from within TER, false
364 when used from within stmt_is_replaceable_p, i.e. EXPAND_INITIALIZER
365 expansion. The differences are that with !TER some tests are skipped
366 to make it more aggressive (doesn't require the same bb, or for -O0
367 same locus and same BLOCK), on the other side never considers memory
368 loads as replaceable, because those don't ever lead into constant
369 expressions. */
370
371 static inline bool
is_replaceable_p(gimple stmt,bool ter)372 is_replaceable_p (gimple stmt, bool ter)
373 {
374 use_operand_p use_p;
375 tree def;
376 gimple use_stmt;
377 location_t locus1, locus2;
378 tree block1, block2;
379
380 /* Only consider modify stmts. */
381 if (!is_gimple_assign (stmt))
382 return false;
383
384 /* If the statement may throw an exception, it cannot be replaced. */
385 if (stmt_could_throw_p (stmt))
386 return false;
387
388 /* Punt if there is more than 1 def. */
389 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
390 if (!def)
391 return false;
392
393 /* Only consider definitions which have a single use. */
394 if (!single_imm_use (def, &use_p, &use_stmt))
395 return false;
396
397 /* If the use isn't in this block, it wont be replaced either. */
398 if (ter && gimple_bb (use_stmt) != gimple_bb (stmt))
399 return false;
400
401 locus1 = gimple_location (stmt);
402 block1 = LOCATION_BLOCK (locus1);
403 locus1 = LOCATION_LOCUS (locus1);
404
405 if (gimple_code (use_stmt) == GIMPLE_PHI)
406 locus2 = gimple_phi_arg_location (use_stmt, PHI_ARG_INDEX_FROM_USE (use_p));
407 else
408 locus2 = gimple_location (use_stmt);
409 block2 = LOCATION_BLOCK (locus2);
410 locus2 = LOCATION_LOCUS (locus2);
411
412 if ((!optimize || optimize_debug)
413 && ter
414 && ((locus1 != UNKNOWN_LOCATION
415 && locus1 != locus2)
416 || (block1 != NULL_TREE
417 && block1 != block2)))
418 return false;
419
420 /* Used in this block, but at the TOP of the block, not the end. */
421 if (gimple_code (use_stmt) == GIMPLE_PHI)
422 return false;
423
424 /* There must be no VDEFs. */
425 if (gimple_vdef (stmt))
426 return false;
427
428 /* Without alias info we can't move around loads. */
429 if ((!optimize || !ter)
430 && gimple_assign_single_p (stmt)
431 && !is_gimple_val (gimple_assign_rhs1 (stmt)))
432 return false;
433
434 /* Float expressions must go through memory if float-store is on. */
435 if (flag_float_store
436 && FLOAT_TYPE_P (gimple_expr_type (stmt)))
437 return false;
438
439 /* An assignment with a register variable on the RHS is not
440 replaceable. */
441 if (gimple_assign_rhs_code (stmt) == VAR_DECL
442 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
443 return false;
444
445 /* No function calls can be replaced. */
446 if (is_gimple_call (stmt))
447 return false;
448
449 /* Leave any stmt with volatile operands alone as well. */
450 if (gimple_has_volatile_ops (stmt))
451 return false;
452
453 return true;
454 }
455
456
457 /* Variant of is_replaceable_p test for use in EXPAND_INITIALIZER
458 expansion. */
459
460 bool
stmt_is_replaceable_p(gimple stmt)461 stmt_is_replaceable_p (gimple stmt)
462 {
463 return is_replaceable_p (stmt, false);
464 }
465
466
467 /* This function will remove the expression for VERSION from replacement
468 consideration in table TAB. If FREE_EXPR is true, then remove the
469 expression from consideration as well by freeing the decl uid bitmap. */
470
471 static void
finished_with_expr(temp_expr_table_p tab,int version,bool free_expr)472 finished_with_expr (temp_expr_table_p tab, int version, bool free_expr)
473 {
474 unsigned i;
475 bitmap_iterator bi;
476
477 /* Remove this expression from its dependent lists. The partition dependence
478 list is retained and transferred later to whomever uses this version. */
479 if (tab->partition_dependencies[version])
480 {
481 EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
482 remove_from_partition_kill_list (tab, i, version);
483 BITMAP_FREE (tab->partition_dependencies[version]);
484 }
485 if (free_expr)
486 BITMAP_FREE (tab->expr_decl_uids[version]);
487 }
488
489
490 /* Create an expression entry for a replaceable expression. */
491
492 static void
process_replaceable(temp_expr_table_p tab,gimple stmt,int call_cnt)493 process_replaceable (temp_expr_table_p tab, gimple stmt, int call_cnt)
494 {
495 tree var, def, basevar;
496 int version;
497 ssa_op_iter iter;
498 bitmap def_vars, use_vars;
499
500 gcc_checking_assert (is_replaceable_p (stmt, true));
501
502 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
503 version = SSA_NAME_VERSION (def);
504 def_vars = BITMAP_ALLOC (&ter_bitmap_obstack);
505
506 basevar = SSA_NAME_VAR (def);
507 if (basevar)
508 bitmap_set_bit (def_vars, DECL_UID (basevar));
509
510 /* Add this expression to the dependency list for each use partition. */
511 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
512 {
513 int var_version = SSA_NAME_VERSION (var);
514
515 use_vars = tab->expr_decl_uids[var_version];
516 add_dependence (tab, version, var);
517 if (use_vars)
518 {
519 bitmap_ior_into (def_vars, use_vars);
520 BITMAP_FREE (tab->expr_decl_uids[var_version]);
521 }
522 else if (SSA_NAME_VAR (var))
523 bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
524 }
525 tab->expr_decl_uids[version] = def_vars;
526
527 /* If there are VUSES, add a dependence on virtual defs. */
528 if (gimple_vuse (stmt))
529 {
530 make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
531 add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
532 }
533
534 tab->call_cnt[version] = call_cnt;
535 }
536
537
538 /* This function removes any expression in TAB which is dependent on PARTITION
539 from consideration, making it not replaceable. */
540
541 static inline void
kill_expr(temp_expr_table_p tab,int partition)542 kill_expr (temp_expr_table_p tab, int partition)
543 {
544 unsigned version;
545
546 /* Mark every active expr dependent on this var as not replaceable.
547 finished_with_expr can modify the bitmap, so we can't execute over it. */
548 while (tab->kill_list[partition])
549 {
550 version = bitmap_first_set_bit (tab->kill_list[partition]);
551 finished_with_expr (tab, version, true);
552 }
553
554 gcc_checking_assert (!tab->kill_list[partition]);
555 }
556
557
558 /* This function kills all expressions in TAB which are dependent on virtual
559 partitions. */
560
561 static inline void
kill_virtual_exprs(temp_expr_table_p tab)562 kill_virtual_exprs (temp_expr_table_p tab)
563 {
564 kill_expr (tab, VIRTUAL_PARTITION (tab));
565 }
566
567
568 /* Mark the expression associated with VAR as replaceable, and enter
569 the defining stmt into the partition_dependencies table TAB. If
570 MORE_REPLACING is true, accumulate the pending partition dependencies. */
571
572 static void
mark_replaceable(temp_expr_table_p tab,tree var,bool more_replacing)573 mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing)
574 {
575 int version = SSA_NAME_VERSION (var);
576
577 /* Move the dependence list to the pending listpending. */
578 if (more_replacing && tab->partition_dependencies[version])
579 bitmap_ior_into (tab->new_replaceable_dependencies,
580 tab->partition_dependencies[version]);
581
582 finished_with_expr (tab, version, !more_replacing);
583
584 /* Set the replaceable expression.
585 The bitmap for this "escapes" from this file so it's allocated
586 on the default obstack. */
587 if (!tab->replaceable_expressions)
588 tab->replaceable_expressions = BITMAP_ALLOC (NULL);
589 bitmap_set_bit (tab->replaceable_expressions, version);
590 }
591
592
593 /* Helper function for find_ssaname_in_stores. Called via walk_tree to
594 find a SSA_NAME DATA somewhere in *TP. */
595
596 static tree
find_ssaname(tree * tp,int * walk_subtrees,void * data)597 find_ssaname (tree *tp, int *walk_subtrees, void *data)
598 {
599 tree var = (tree) data;
600 if (*tp == var)
601 return var;
602 else if (IS_TYPE_OR_DECL_P (*tp))
603 *walk_subtrees = 0;
604 return NULL_TREE;
605 }
606
607 /* Helper function for find_replaceable_in_bb. Return true if SSA_NAME DATA
608 is used somewhere in T, which is a store in the statement. Called via
609 walk_stmt_load_store_addr_ops. */
610
611 static bool
find_ssaname_in_store(gimple,tree,tree t,void * data)612 find_ssaname_in_store (gimple, tree, tree t, void *data)
613 {
614 return walk_tree (&t, find_ssaname, data, NULL) != NULL_TREE;
615 }
616
617 /* This function processes basic block BB, and looks for variables which can
618 be replaced by their expressions. Results are stored in the table TAB. */
619
620 static void
find_replaceable_in_bb(temp_expr_table_p tab,basic_block bb)621 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
622 {
623 gimple_stmt_iterator bsi;
624 gimple stmt;
625 tree def, use, fndecl;
626 int partition;
627 var_map map = tab->map;
628 ssa_op_iter iter;
629 bool stmt_replaceable;
630 int cur_call_cnt = 0;
631
632 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
633 {
634 stmt = gsi_stmt (bsi);
635
636 if (is_gimple_debug (stmt))
637 continue;
638
639 stmt_replaceable = is_replaceable_p (stmt, true);
640
641 /* Determine if this stmt finishes an existing expression. */
642 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
643 {
644 unsigned ver = SSA_NAME_VERSION (use);
645
646 /* If this use is a potential replacement variable, process it. */
647 if (tab->expr_decl_uids[ver])
648 {
649 bool same_root_var = false;
650 ssa_op_iter iter2;
651 bitmap vars = tab->expr_decl_uids[ver];
652
653 /* See if the root variables are the same. If they are, we
654 do not want to do the replacement to avoid problems with
655 code size, see PR tree-optimization/17549. */
656 if (!bitmap_empty_p (vars))
657 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
658 {
659 if (SSA_NAME_VAR (def)
660 && bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
661 {
662 same_root_var = true;
663 break;
664 }
665 }
666
667 /* If the stmt does a memory store and the replacement
668 is a load aliasing it avoid creating overlapping
669 assignments which we cannot expand correctly. */
670 if (gimple_vdef (stmt))
671 {
672 gimple def_stmt = SSA_NAME_DEF_STMT (use);
673 while (is_gimple_assign (def_stmt)
674 && gimple_assign_rhs_code (def_stmt) == SSA_NAME)
675 def_stmt
676 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
677 if (gimple_vuse (def_stmt)
678 && gimple_assign_single_p (def_stmt)
679 && stmt_may_clobber_ref_p (stmt,
680 gimple_assign_rhs1 (def_stmt)))
681 {
682 /* For calls, it is not a problem if USE is among
683 call's arguments or say OBJ_TYPE_REF argument,
684 all those necessarily need to be evaluated before
685 the call that may clobber the memory. But if
686 LHS of the call refers to USE, expansion might
687 evaluate it after the call, prevent TER in that
688 case.
689 For inline asm, allow TER of loads into input
690 arguments, but disallow TER for USEs that occur
691 somewhere in outputs. */
692 if (is_gimple_call (stmt)
693 || gimple_code (stmt) == GIMPLE_ASM)
694 {
695 if (walk_stmt_load_store_ops (stmt, use, NULL,
696 find_ssaname_in_store))
697 same_root_var = true;
698 }
699 else
700 same_root_var = true;
701 }
702 }
703
704 /* Mark expression as replaceable unless stmt is volatile, or the
705 def variable has the same root variable as something in the
706 substitution list, or the def and use span a call such that
707 we'll expand lifetimes across a call. */
708 if (gimple_has_volatile_ops (stmt) || same_root_var
709 || (tab->call_cnt[ver] != cur_call_cnt
710 && SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use), SSA_OP_USE)
711 == NULL_USE_OPERAND_P))
712 finished_with_expr (tab, ver, true);
713 else
714 mark_replaceable (tab, use, stmt_replaceable);
715 }
716 }
717
718 /* Next, see if this stmt kills off an active expression. */
719 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
720 {
721 partition = var_to_partition (map, def);
722 if (partition != NO_PARTITION && tab->kill_list[partition])
723 kill_expr (tab, partition);
724 }
725
726 /* Increment counter if this is a non BUILT_IN call. We allow
727 replacement over BUILT_IN calls since many will expand to inline
728 insns instead of a true call. */
729 if (is_gimple_call (stmt)
730 && !((fndecl = gimple_call_fndecl (stmt))
731 && DECL_BUILT_IN (fndecl)))
732 cur_call_cnt++;
733
734 /* Now see if we are creating a new expression or not. */
735 if (stmt_replaceable)
736 process_replaceable (tab, stmt, cur_call_cnt);
737
738 /* Free any unused dependency lists. */
739 bitmap_clear (tab->new_replaceable_dependencies);
740
741 /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
742 including the current stmt. */
743 if (gimple_vdef (stmt))
744 kill_virtual_exprs (tab);
745 }
746 }
747
748
749 /* This function is the driver routine for replacement of temporary expressions
750 in the SSA->normal phase, operating on MAP. If there are replaceable
751 expressions, a table is returned which maps SSA versions to the
752 expressions they should be replaced with. A NULL_TREE indicates no
753 replacement should take place. If there are no replacements at all,
754 NULL is returned by the function, otherwise an expression vector indexed
755 by SSA_NAME version numbers. */
756
757 bitmap
find_replaceable_exprs(var_map map)758 find_replaceable_exprs (var_map map)
759 {
760 basic_block bb;
761 temp_expr_table_p table;
762 bitmap ret;
763
764 bitmap_obstack_initialize (&ter_bitmap_obstack);
765 table = new_temp_expr_table (map);
766 FOR_EACH_BB (bb)
767 {
768 find_replaceable_in_bb (table, bb);
769 gcc_checking_assert (bitmap_empty_p (table->partition_in_use));
770 }
771 ret = free_temp_expr_table (table);
772 bitmap_obstack_release (&ter_bitmap_obstack);
773 return ret;
774 }
775
776 /* Dump TER expression table EXPR to file F. */
777
778 void
dump_replaceable_exprs(FILE * f,bitmap expr)779 dump_replaceable_exprs (FILE *f, bitmap expr)
780 {
781 tree var;
782 unsigned x;
783
784 fprintf (f, "\nReplacing Expressions\n");
785 for (x = 0; x < num_ssa_names; x++)
786 if (bitmap_bit_p (expr, x))
787 {
788 var = ssa_name (x);
789 print_generic_expr (f, var, TDF_SLIM);
790 fprintf (f, " replace with --> ");
791 print_gimple_stmt (f, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
792 fprintf (f, "\n");
793 }
794 fprintf (f, "\n");
795 }
796
797
798 #ifdef ENABLE_CHECKING
799 /* Dump the status of the various tables in the expression table. This is used
800 exclusively to debug TER. F is the place to send debug info and T is the
801 table being debugged. */
802
803 DEBUG_FUNCTION void
debug_ter(FILE * f,temp_expr_table_p t)804 debug_ter (FILE *f, temp_expr_table_p t)
805 {
806 unsigned x, y;
807 bitmap_iterator bi;
808
809 fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
810 VIRTUAL_PARTITION (t));
811 if (t->replaceable_expressions)
812 dump_replaceable_exprs (f, t->replaceable_expressions);
813 fprintf (f, "Currently tracking the following expressions:\n");
814
815 for (x = 1; x < num_ssa_names; x++)
816 if (t->expr_decl_uids[x])
817 {
818 print_generic_expr (f, ssa_name (x), TDF_SLIM);
819 fprintf (f, " dep-parts : ");
820 if (t->partition_dependencies[x]
821 && !bitmap_empty_p (t->partition_dependencies[x]))
822 {
823 EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
824 fprintf (f, "P%d ",y);
825 }
826 fprintf (f, " basedecls: ");
827 EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
828 fprintf (f, "%d ",y);
829 fprintf (f, " call_cnt : %d",t->call_cnt[x]);
830 fprintf (f, "\n");
831 }
832
833 bitmap_print (f, t->partition_in_use, "Partitions in use ",
834 "\npartition KILL lists:\n");
835
836 for (x = 0; x <= num_var_partitions (t->map); x++)
837 if (t->kill_list[x])
838 {
839 fprintf (f, "Partition %d : ", x);
840 EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
841 fprintf (f, "_%d ",y);
842 }
843
844 fprintf (f, "\n----------\n");
845 }
846 #endif
847