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