Daily bump.
[official-gcc.git] / gcc / tree-ssa-ter.c
blob09dc3138a53d4ec5c863a11c4f83794853ffb129
1 /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
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/>. */
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 "basic-block.h"
30 #include "tree-ssa-alias.h"
31 #include "internal-fn.h"
32 #include "gimple-expr.h"
33 #include "is-a.h"
34 #include "gimple.h"
35 #include "gimple-iterator.h"
36 #include "gimple-ssa.h"
37 #include "tree-phinodes.h"
38 #include "ssa-iterators.h"
39 #include "stringpool.h"
40 #include "tree-ssanames.h"
41 #include "dumpfile.h"
42 #include "tree-ssa-live.h"
43 #include "tree-ssa-ter.h"
44 #include "tree-outof-ssa.h"
45 #include "flags.h"
46 #include "gimple-walk.h"
49 /* Temporary Expression Replacement (TER)
51 Replace SSA version variables during out-of-ssa with their defining
52 expression if there is only one use of the variable.
54 This pass is required in order for the RTL expansion pass to see larger
55 chunks of code. This allows it to make better choices on RTL pattern
56 selection. When expand is rewritten and merged with out-of-ssa, and
57 understands SSA, this should be eliminated.
59 A pass is made through the function, one block at a time. No cross block
60 information is tracked.
62 Variables which only have one use, and whose defining stmt is considered
63 a replaceable expression (see ssa_is_replaceable_p) are tracked to see whether
64 they can be replaced at their use location.
66 n_12 = C * 10
67 a_2 = b_5 + 6
68 v_9 = a_2 * n_12
70 if there are the only use of n_12 and a_2, TER will substitute in their
71 expressions in v_9, and end up with:
73 v_9 = (b_5 + 6) * (C * 10)
75 which will then have the ssa_name assigned to regular variables, and the
76 resulting code which will be passed to the expander looks something like:
78 v = (b + 6) * (C * 10)
81 This requires ensuring that none of the variables used by the expression
82 change between the def point and where it is used. Furthermore, if any
83 of the ssa_names used in this expression are themselves replaceable, we
84 have to ensure none of that expressions' arguments change either.
85 Although SSA_NAMES themselves don't change, this pass is performed after
86 coalescing has coalesced different SSA_NAMES together, so there could be a
87 definition of an SSA_NAME which is coalesced with a use that causes a
88 problem, i.e.,
90 PHI b_5 = <b_8(2), b_14(1)>
91 <...>
92 a_2 = b_5 + 6
93 b_8 = c_4 + 4
94 v_9 = a_2 * n_12
95 <...>
97 If b_5, b_8 and b_14 are all coalesced together...
98 The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
99 because b_8 is in fact killing the value of b_5 since they share a partition
100 and will be assigned the same memory or register location.
102 TER implements this but stepping through the instructions in a block and
103 tracking potential expressions for replacement, and the partitions they are
104 dependent on. Expressions are represented by the SSA_NAME_VERSION of the
105 DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS.
107 When a stmt is determined to be a possible replacement expression, the
108 following steps are taken:
110 EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
111 def and any uses in the expression. non-NULL means the expression is being
112 tracked. The UID's themselves are used to prevent TER substitution into
113 accumulating sequences, i.e.,
115 x = x + y
116 x = x + z
117 x = x + w
118 etc.
119 this can result in very large expressions which don't accomplish anything
120 see PR tree-optimization/17549.
122 PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
123 partition which is used in the expression. This is primarily used to remove
124 an expression from the partition kill lists when a decision is made whether
125 to replace it or not. This is indexed by ssa version number as well, and
126 indicates a partition number. virtual operands are not tracked individually,
127 but they are summarized by an artificial partition called VIRTUAL_PARTITION.
128 This means a MAY or MUST def will kill *ALL* expressions that are dependent
129 on a virtual operand.
130 Note that the EXPR_DECL_UID and this bitmap represent very similar
131 information, but the info in one is not easy to obtain from the other.
133 KILL_LIST is yet another bitmap array, this time it is indexed by partition
134 number, and represents a list of active expressions which will will no
135 longer be valid if a definition into this partition takes place.
137 PARTITION_IN_USE is simply a bitmap which is used to track which partitions
138 currently have something in their kill list. This is used at the end of
139 a block to clear out the KILL_LIST bitmaps at the end of each block.
141 NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
142 dependencies which will be reused by the current definition. All the uses
143 on an expression are processed before anything else is done. If a use is
144 determined to be a replaceable expression AND the current stmt is also going
145 to be replaceable, all the dependencies of this replaceable use will be
146 picked up by the current stmt's expression. Rather than recreate them, they
147 are simply copied here and then copied into the new expression when it is
148 processed.
150 a_2 = b_5 + 6
151 v_8 = a_2 + c_4
153 a_2's expression 'b_5 + 6' is determined to be replaceable at the use
154 location. It is dependent on the partition 'b_5' is in. This is cached into
155 the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
156 replaceability, it is a candidate, and it is dependent on the partition
157 b_5 is in *NOT* a_2, as well as c_4's partition.
159 if v_8 is also replaceable:
161 x_9 = v_8 * 5
163 x_9 is dependent on partitions b_5, and c_4
165 if a statement is found which has either of those partitions written to
166 before x_9 is used, then x_9 itself is NOT replaceable. */
169 /* Temporary Expression Replacement (TER) table information. */
171 typedef struct temp_expr_table_d
173 var_map map;
174 bitmap *partition_dependencies; /* Partitions expr is dependent on. */
175 bitmap replaceable_expressions; /* Replacement expression table. */
176 bitmap *expr_decl_uids; /* Base uids of exprs. */
177 bitmap *kill_list; /* Expr's killed by a partition. */
178 int virtual_partition; /* Pseudo partition for virtual ops. */
179 bitmap partition_in_use; /* Partitions with kill entries. */
180 bitmap new_replaceable_dependencies; /* Holding place for pending dep's. */
181 int *num_in_part; /* # of ssa_names in a partition. */
182 int *call_cnt; /* Call count at definition. */
183 } *temp_expr_table_p;
185 /* Used to indicate a dependency on VDEFs. */
186 #define VIRTUAL_PARTITION(table) (table->virtual_partition)
188 /* A place for the many, many bitmaps we create. */
189 static bitmap_obstack ter_bitmap_obstack;
191 #ifdef ENABLE_CHECKING
192 extern void debug_ter (FILE *, temp_expr_table_p);
193 #endif
196 /* Create a new TER table for MAP. */
198 static temp_expr_table_p
199 new_temp_expr_table (var_map map)
201 temp_expr_table_p t;
202 unsigned x;
204 t = XNEW (struct temp_expr_table_d);
205 t->map = map;
207 t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
208 t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
209 t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
211 t->partition_in_use = BITMAP_ALLOC (&ter_bitmap_obstack);
213 t->virtual_partition = num_var_partitions (map);
214 t->new_replaceable_dependencies = BITMAP_ALLOC (&ter_bitmap_obstack);
216 t->replaceable_expressions = NULL;
217 t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
218 for (x = 1; x < num_ssa_names; x++)
220 int p;
221 tree name = ssa_name (x);
222 if (!name)
223 continue;
224 p = var_to_partition (map, name);
225 if (p != NO_PARTITION)
226 t->num_in_part[p]++;
228 t->call_cnt = XCNEWVEC (int, num_ssa_names + 1);
230 return t;
234 /* Free TER table T. If there are valid replacements, return the expression
235 vector. */
237 static bitmap
238 free_temp_expr_table (temp_expr_table_p t)
240 bitmap ret = NULL;
242 #ifdef ENABLE_CHECKING
243 unsigned x;
244 for (x = 0; x <= num_var_partitions (t->map); x++)
245 gcc_assert (!t->kill_list[x]);
246 for (x = 0; x < num_ssa_names; x++)
248 gcc_assert (t->expr_decl_uids[x] == NULL);
249 gcc_assert (t->partition_dependencies[x] == NULL);
251 #endif
253 BITMAP_FREE (t->partition_in_use);
254 BITMAP_FREE (t->new_replaceable_dependencies);
256 free (t->expr_decl_uids);
257 free (t->kill_list);
258 free (t->partition_dependencies);
259 free (t->num_in_part);
260 free (t->call_cnt);
262 if (t->replaceable_expressions)
263 ret = t->replaceable_expressions;
265 free (t);
266 return ret;
270 /* Return TRUE if VERSION is to be replaced by an expression in TAB. */
272 static inline bool
273 version_to_be_replaced_p (temp_expr_table_p tab, int version)
275 if (!tab->replaceable_expressions)
276 return false;
277 return bitmap_bit_p (tab->replaceable_expressions, version);
281 /* Add partition P to the list if partitions VERSION is dependent on. TAB is
282 the expression table */
284 static inline void
285 make_dependent_on_partition (temp_expr_table_p tab, int version, int p)
287 if (!tab->partition_dependencies[version])
288 tab->partition_dependencies[version] = BITMAP_ALLOC (&ter_bitmap_obstack);
290 bitmap_set_bit (tab->partition_dependencies[version], p);
294 /* Add VER to the kill list for P. TAB is the expression table */
296 static inline void
297 add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver)
299 if (!tab->kill_list[p])
301 tab->kill_list[p] = BITMAP_ALLOC (&ter_bitmap_obstack);
302 bitmap_set_bit (tab->partition_in_use, p);
304 bitmap_set_bit (tab->kill_list[p], ver);
308 /* Remove VER from the partition kill list for P. TAB is the expression
309 table. */
311 static inline void
312 remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version)
314 gcc_checking_assert (tab->kill_list[p]);
315 bitmap_clear_bit (tab->kill_list[p], version);
316 if (bitmap_empty_p (tab->kill_list[p]))
318 bitmap_clear_bit (tab->partition_in_use, p);
319 BITMAP_FREE (tab->kill_list[p]);
324 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is
325 replaceable by an expression, add a dependence each of the elements of the
326 expression. These are contained in the new_replaceable list. TAB is the
327 expression table. */
329 static void
330 add_dependence (temp_expr_table_p tab, int version, tree var)
332 int i;
333 bitmap_iterator bi;
334 unsigned x;
336 i = SSA_NAME_VERSION (var);
337 if (version_to_be_replaced_p (tab, i))
339 if (!bitmap_empty_p (tab->new_replaceable_dependencies))
341 /* Version will now be killed by a write to any partition the
342 substituted expression would have been killed by. */
343 EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
344 add_to_partition_kill_list (tab, x, version);
346 /* Rather than set partition_dependencies and in_use lists bit by
347 bit, simply OR in the new_replaceable_dependencies bits. */
348 if (!tab->partition_dependencies[version])
349 tab->partition_dependencies[version] =
350 BITMAP_ALLOC (&ter_bitmap_obstack);
351 bitmap_ior_into (tab->partition_dependencies[version],
352 tab->new_replaceable_dependencies);
353 bitmap_ior_into (tab->partition_in_use,
354 tab->new_replaceable_dependencies);
355 /* It is only necessary to add these once. */
356 bitmap_clear (tab->new_replaceable_dependencies);
359 else
361 i = var_to_partition (tab->map, var);
362 gcc_checking_assert (i != NO_PARTITION);
363 gcc_checking_assert (tab->num_in_part[i] != 0);
364 /* Only dependencies on ssa_names which are coalesced with something need
365 to be tracked. Partitions with containing only a single SSA_NAME
366 *cannot* have their value changed. */
367 if (tab->num_in_part[i] > 1)
369 add_to_partition_kill_list (tab, i, version);
370 make_dependent_on_partition (tab, version, i);
376 /* This function will remove the expression for VERSION from replacement
377 consideration in table TAB. If FREE_EXPR is true, then remove the
378 expression from consideration as well by freeing the decl uid bitmap. */
380 static void
381 finished_with_expr (temp_expr_table_p tab, int version, bool free_expr)
383 unsigned i;
384 bitmap_iterator bi;
386 /* Remove this expression from its dependent lists. The partition dependence
387 list is retained and transferred later to whomever uses this version. */
388 if (tab->partition_dependencies[version])
390 EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
391 remove_from_partition_kill_list (tab, i, version);
392 BITMAP_FREE (tab->partition_dependencies[version]);
394 if (free_expr)
395 BITMAP_FREE (tab->expr_decl_uids[version]);
399 /* Return TRUE if expression STMT is suitable for replacement.
400 In addition to ssa_is_replaceable_p, require the same bb, and for -O0
401 same locus and same BLOCK), Considers memory loads as replaceable if aliasing
402 is available. */
404 static inline bool
405 ter_is_replaceable_p (gimple stmt)
408 if (ssa_is_replaceable_p (stmt))
410 use_operand_p use_p;
411 tree def;
412 gimple use_stmt;
413 location_t locus1, locus2;
414 tree block1, block2;
416 /* Only consider definitions which have a single use. ssa_is_replaceable_p
417 already performed this check, but the use stmt pointer is required for
418 further checks. */
419 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
420 if (!single_imm_use (def, &use_p, &use_stmt))
421 return false;
423 /* If the use isn't in this block, it wont be replaced either. */
424 if (gimple_bb (use_stmt) != gimple_bb (stmt))
425 return false;
427 locus1 = gimple_location (stmt);
428 block1 = LOCATION_BLOCK (locus1);
429 locus1 = LOCATION_LOCUS (locus1);
431 if (gimple_code (use_stmt) == GIMPLE_PHI)
432 locus2 = gimple_phi_arg_location (use_stmt,
433 PHI_ARG_INDEX_FROM_USE (use_p));
434 else
435 locus2 = gimple_location (use_stmt);
436 block2 = LOCATION_BLOCK (locus2);
437 locus2 = LOCATION_LOCUS (locus2);
439 if ((!optimize || optimize_debug)
440 && ((locus1 != UNKNOWN_LOCATION && locus1 != locus2)
441 || (block1 != NULL_TREE && block1 != block2)))
442 return false;
444 /* Without alias info we can't move around loads. */
445 if (!optimize && gimple_assign_single_p (stmt)
446 && !is_gimple_val (gimple_assign_rhs1 (stmt)))
447 return false;
449 return true;
451 return false;
455 /* Create an expression entry for a replaceable expression. */
457 static void
458 process_replaceable (temp_expr_table_p tab, gimple stmt, int call_cnt)
460 tree var, def, basevar;
461 int version;
462 ssa_op_iter iter;
463 bitmap def_vars, use_vars;
465 gcc_checking_assert (ter_is_replaceable_p (stmt));
467 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
468 version = SSA_NAME_VERSION (def);
469 def_vars = BITMAP_ALLOC (&ter_bitmap_obstack);
471 basevar = SSA_NAME_VAR (def);
472 if (basevar)
473 bitmap_set_bit (def_vars, DECL_UID (basevar));
475 /* Add this expression to the dependency list for each use partition. */
476 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
478 int var_version = SSA_NAME_VERSION (var);
480 use_vars = tab->expr_decl_uids[var_version];
481 add_dependence (tab, version, var);
482 if (use_vars)
484 bitmap_ior_into (def_vars, use_vars);
485 BITMAP_FREE (tab->expr_decl_uids[var_version]);
487 else if (SSA_NAME_VAR (var))
488 bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
490 tab->expr_decl_uids[version] = def_vars;
492 /* If there are VUSES, add a dependence on virtual defs. */
493 if (gimple_vuse (stmt))
495 make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
496 add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
499 tab->call_cnt[version] = call_cnt;
503 /* This function removes any expression in TAB which is dependent on PARTITION
504 from consideration, making it not replaceable. */
506 static inline void
507 kill_expr (temp_expr_table_p tab, int partition)
509 unsigned version;
511 /* Mark every active expr dependent on this var as not replaceable.
512 finished_with_expr can modify the bitmap, so we can't execute over it. */
513 while (tab->kill_list[partition])
515 version = bitmap_first_set_bit (tab->kill_list[partition]);
516 finished_with_expr (tab, version, true);
519 gcc_checking_assert (!tab->kill_list[partition]);
523 /* This function kills all expressions in TAB which are dependent on virtual
524 partitions. */
526 static inline void
527 kill_virtual_exprs (temp_expr_table_p tab)
529 kill_expr (tab, VIRTUAL_PARTITION (tab));
533 /* Mark the expression associated with VAR as replaceable, and enter
534 the defining stmt into the partition_dependencies table TAB. If
535 MORE_REPLACING is true, accumulate the pending partition dependencies. */
537 static void
538 mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing)
540 int version = SSA_NAME_VERSION (var);
542 /* Move the dependence list to the pending listpending. */
543 if (more_replacing && tab->partition_dependencies[version])
544 bitmap_ior_into (tab->new_replaceable_dependencies,
545 tab->partition_dependencies[version]);
547 finished_with_expr (tab, version, !more_replacing);
549 /* Set the replaceable expression.
550 The bitmap for this "escapes" from this file so it's allocated
551 on the default obstack. */
552 if (!tab->replaceable_expressions)
553 tab->replaceable_expressions = BITMAP_ALLOC (NULL);
554 bitmap_set_bit (tab->replaceable_expressions, version);
558 /* Helper function for find_ssaname_in_stores. Called via walk_tree to
559 find a SSA_NAME DATA somewhere in *TP. */
561 static tree
562 find_ssaname (tree *tp, int *walk_subtrees, void *data)
564 tree var = (tree) data;
565 if (*tp == var)
566 return var;
567 else if (IS_TYPE_OR_DECL_P (*tp))
568 *walk_subtrees = 0;
569 return NULL_TREE;
572 /* Helper function for find_replaceable_in_bb. Return true if SSA_NAME DATA
573 is used somewhere in T, which is a store in the statement. Called via
574 walk_stmt_load_store_addr_ops. */
576 static bool
577 find_ssaname_in_store (gimple, tree, tree t, void *data)
579 return walk_tree (&t, find_ssaname, data, NULL) != NULL_TREE;
582 /* This function processes basic block BB, and looks for variables which can
583 be replaced by their expressions. Results are stored in the table TAB. */
585 static void
586 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
588 gimple_stmt_iterator bsi;
589 gimple stmt;
590 tree def, use, fndecl;
591 int partition;
592 var_map map = tab->map;
593 ssa_op_iter iter;
594 bool stmt_replaceable;
595 int cur_call_cnt = 0;
597 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
599 stmt = gsi_stmt (bsi);
601 if (is_gimple_debug (stmt))
602 continue;
604 stmt_replaceable = ter_is_replaceable_p (stmt);
606 /* Determine if this stmt finishes an existing expression. */
607 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
609 unsigned ver = SSA_NAME_VERSION (use);
611 /* If this use is a potential replacement variable, process it. */
612 if (tab->expr_decl_uids[ver])
614 bool same_root_var = false;
615 ssa_op_iter iter2;
616 bitmap vars = tab->expr_decl_uids[ver];
618 /* See if the root variables are the same. If they are, we
619 do not want to do the replacement to avoid problems with
620 code size, see PR tree-optimization/17549. */
621 if (!bitmap_empty_p (vars))
622 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
624 if (SSA_NAME_VAR (def)
625 && bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
627 same_root_var = true;
628 break;
632 /* If the stmt does a memory store and the replacement
633 is a load aliasing it avoid creating overlapping
634 assignments which we cannot expand correctly. */
635 if (gimple_vdef (stmt))
637 gimple def_stmt = SSA_NAME_DEF_STMT (use);
638 while (is_gimple_assign (def_stmt)
639 && gimple_assign_rhs_code (def_stmt) == SSA_NAME)
640 def_stmt
641 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
642 if (gimple_vuse (def_stmt)
643 && gimple_assign_single_p (def_stmt)
644 && stmt_may_clobber_ref_p (stmt,
645 gimple_assign_rhs1 (def_stmt)))
647 /* For calls, it is not a problem if USE is among
648 call's arguments or say OBJ_TYPE_REF argument,
649 all those necessarily need to be evaluated before
650 the call that may clobber the memory. But if
651 LHS of the call refers to USE, expansion might
652 evaluate it after the call, prevent TER in that
653 case.
654 For inline asm, allow TER of loads into input
655 arguments, but disallow TER for USEs that occur
656 somewhere in outputs. */
657 if (is_gimple_call (stmt)
658 || gimple_code (stmt) == GIMPLE_ASM)
660 if (walk_stmt_load_store_ops (stmt, use, NULL,
661 find_ssaname_in_store))
662 same_root_var = true;
664 else
665 same_root_var = true;
669 /* Mark expression as replaceable unless stmt is volatile, or the
670 def variable has the same root variable as something in the
671 substitution list, or the def and use span a call such that
672 we'll expand lifetimes across a call. */
673 if (gimple_has_volatile_ops (stmt) || same_root_var
674 || (tab->call_cnt[ver] != cur_call_cnt
675 && SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use), SSA_OP_USE)
676 == NULL_USE_OPERAND_P))
677 finished_with_expr (tab, ver, true);
678 else
679 mark_replaceable (tab, use, stmt_replaceable);
683 /* Next, see if this stmt kills off an active expression. */
684 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
686 partition = var_to_partition (map, def);
687 if (partition != NO_PARTITION && tab->kill_list[partition])
688 kill_expr (tab, partition);
691 /* Increment counter if this is a non BUILT_IN call. We allow
692 replacement over BUILT_IN calls since many will expand to inline
693 insns instead of a true call. */
694 if (is_gimple_call (stmt)
695 && !((fndecl = gimple_call_fndecl (stmt))
696 && DECL_BUILT_IN (fndecl)))
697 cur_call_cnt++;
699 /* Now see if we are creating a new expression or not. */
700 if (stmt_replaceable)
701 process_replaceable (tab, stmt, cur_call_cnt);
703 /* Free any unused dependency lists. */
704 bitmap_clear (tab->new_replaceable_dependencies);
706 /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
707 including the current stmt. */
708 if (gimple_vdef (stmt))
709 kill_virtual_exprs (tab);
714 /* This function is the driver routine for replacement of temporary expressions
715 in the SSA->normal phase, operating on MAP. If there are replaceable
716 expressions, a table is returned which maps SSA versions to the
717 expressions they should be replaced with. A NULL_TREE indicates no
718 replacement should take place. If there are no replacements at all,
719 NULL is returned by the function, otherwise an expression vector indexed
720 by SSA_NAME version numbers. */
722 bitmap
723 find_replaceable_exprs (var_map map)
725 basic_block bb;
726 temp_expr_table_p table;
727 bitmap ret;
729 bitmap_obstack_initialize (&ter_bitmap_obstack);
730 table = new_temp_expr_table (map);
731 FOR_EACH_BB_FN (bb, cfun)
733 find_replaceable_in_bb (table, bb);
734 gcc_checking_assert (bitmap_empty_p (table->partition_in_use));
736 ret = free_temp_expr_table (table);
737 bitmap_obstack_release (&ter_bitmap_obstack);
738 return ret;
741 /* Dump TER expression table EXPR to file F. */
743 void
744 dump_replaceable_exprs (FILE *f, bitmap expr)
746 tree var;
747 unsigned x;
749 fprintf (f, "\nReplacing Expressions\n");
750 for (x = 0; x < num_ssa_names; x++)
751 if (bitmap_bit_p (expr, x))
753 var = ssa_name (x);
754 print_generic_expr (f, var, TDF_SLIM);
755 fprintf (f, " replace with --> ");
756 print_gimple_stmt (f, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
757 fprintf (f, "\n");
759 fprintf (f, "\n");
763 #ifdef ENABLE_CHECKING
764 /* Dump the status of the various tables in the expression table. This is used
765 exclusively to debug TER. F is the place to send debug info and T is the
766 table being debugged. */
768 DEBUG_FUNCTION void
769 debug_ter (FILE *f, temp_expr_table_p t)
771 unsigned x, y;
772 bitmap_iterator bi;
774 fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
775 VIRTUAL_PARTITION (t));
776 if (t->replaceable_expressions)
777 dump_replaceable_exprs (f, t->replaceable_expressions);
778 fprintf (f, "Currently tracking the following expressions:\n");
780 for (x = 1; x < num_ssa_names; x++)
781 if (t->expr_decl_uids[x])
783 print_generic_expr (f, ssa_name (x), TDF_SLIM);
784 fprintf (f, " dep-parts : ");
785 if (t->partition_dependencies[x]
786 && !bitmap_empty_p (t->partition_dependencies[x]))
788 EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
789 fprintf (f, "P%d ",y);
791 fprintf (f, " basedecls: ");
792 EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
793 fprintf (f, "%d ",y);
794 fprintf (f, " call_cnt : %d",t->call_cnt[x]);
795 fprintf (f, "\n");
798 bitmap_print (f, t->partition_in_use, "Partitions in use ",
799 "\npartition KILL lists:\n");
801 for (x = 0; x <= num_var_partitions (t->map); x++)
802 if (t->kill_list[x])
804 fprintf (f, "Partition %d : ", x);
805 EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
806 fprintf (f, "_%d ",y);
809 fprintf (f, "\n----------\n");
811 #endif