Branch data Line data Source code
1 : : /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
2 : : Copyright (C) 2003-2024 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 : 998644 : new_temp_expr_table (var_map map)
189 : : {
190 : 998644 : temp_expr_table *t = XNEW (struct temp_expr_table);
191 : 998644 : t->map = map;
192 : :
193 : 1997288 : t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
194 : 1997288 : t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
195 : 998644 : t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
196 : :
197 : 998644 : t->partition_in_use = BITMAP_ALLOC (&ter_bitmap_obstack);
198 : :
199 : 998644 : t->virtual_partition = num_var_partitions (map);
200 : 998644 : t->new_replaceable_dependencies = BITMAP_ALLOC (&ter_bitmap_obstack);
201 : :
202 : 998644 : t->replaceable_expressions = NULL;
203 : 998644 : t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
204 : :
205 : 998644 : unsigned x;
206 : 998644 : tree name;
207 : :
208 : 53927543 : FOR_EACH_SSA_NAME (x, name, cfun)
209 : : {
210 : 33898478 : int p;
211 : 33898478 : p = var_to_partition (map, name);
212 : 33898478 : if (p != NO_PARTITION)
213 : 21527972 : t->num_in_part[p]++;
214 : : }
215 : 998644 : t->call_cnt = XCNEWVEC (int, num_ssa_names + 1);
216 : 1997288 : t->reg_vars_cnt = XCNEWVEC (int, num_ssa_names + 1);
217 : :
218 : 998644 : 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 : 998644 : free_temp_expr_table (temp_expr_table *t)
227 : : {
228 : 998644 : bitmap ret = NULL;
229 : :
230 : 998644 : if (flag_checking)
231 : : {
232 : 19621564 : for (unsigned x = 0; x <= num_var_partitions (t->map); x++)
233 : 18622938 : gcc_assert (!t->kill_list[x]);
234 : 54925837 : for (unsigned x = 0; x < num_ssa_names; x++)
235 : : {
236 : 53927211 : gcc_assert (t->expr_decl_uids[x] == NULL);
237 : 53927211 : gcc_assert (t->partition_dependencies[x] == NULL);
238 : : }
239 : : }
240 : :
241 : 998644 : BITMAP_FREE (t->partition_in_use);
242 : 998644 : BITMAP_FREE (t->new_replaceable_dependencies);
243 : :
244 : 998644 : free (t->expr_decl_uids);
245 : 998644 : free (t->kill_list);
246 : 998644 : free (t->partition_dependencies);
247 : 998644 : free (t->num_in_part);
248 : 998644 : free (t->call_cnt);
249 : 998644 : free (t->reg_vars_cnt);
250 : :
251 : 998644 : if (t->replaceable_expressions)
252 : : ret = t->replaceable_expressions;
253 : :
254 : 998644 : free (t);
255 : 998644 : 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 : 9158088 : version_to_be_replaced_p (temp_expr_table *tab, int version)
263 : : {
264 : 9158088 : if (!tab->replaceable_expressions)
265 : : return false;
266 : 8402129 : 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 : 4115834 : make_dependent_on_partition (temp_expr_table *tab, int version, int p)
275 : : {
276 : 4115834 : if (!tab->partition_dependencies[version])
277 : 3528220 : tab->partition_dependencies[version] = BITMAP_ALLOC (&ter_bitmap_obstack);
278 : :
279 : 4115834 : bitmap_set_bit (tab->partition_dependencies[version], p);
280 : 4115834 : }
281 : :
282 : :
283 : : /* Add VER to the kill list for P. TAB is the expression table */
284 : :
285 : : static inline void
286 : 6143698 : add_to_partition_kill_list (temp_expr_table *tab, int p, int ver)
287 : : {
288 : 6143698 : if (!tab->kill_list[p])
289 : : {
290 : 5201586 : tab->kill_list[p] = BITMAP_ALLOC (&ter_bitmap_obstack);
291 : 5201586 : bitmap_set_bit (tab->partition_in_use, p);
292 : : }
293 : 6143698 : bitmap_set_bit (tab->kill_list[p], ver);
294 : 6143698 : }
295 : :
296 : :
297 : : /* Remove VER from the partition kill list for P. TAB is the expression
298 : : table. */
299 : :
300 : : static inline void
301 : 6024003 : remove_from_partition_kill_list (temp_expr_table *tab, int p, int version)
302 : : {
303 : 6024003 : gcc_checking_assert (tab->kill_list[p]);
304 : 6024003 : bitmap_clear_bit (tab->kill_list[p], version);
305 : 6024003 : if (bitmap_empty_p (tab->kill_list[p]))
306 : : {
307 : 5201586 : bitmap_clear_bit (tab->partition_in_use, p);
308 : 5201586 : BITMAP_FREE (tab->kill_list[p]);
309 : : }
310 : 6024003 : }
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 : 9158088 : add_dependence (temp_expr_table *tab, int version, tree var)
320 : : {
321 : 9158088 : int i;
322 : 9158088 : bitmap_iterator bi;
323 : 9158088 : unsigned x;
324 : :
325 : 9158088 : i = SSA_NAME_VERSION (var);
326 : 17560217 : if (version_to_be_replaced_p (tab, i))
327 : : {
328 : 3549847 : 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 : 3710114 : EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
333 : 2027864 : 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 : 1682250 : if (!tab->partition_dependencies[version])
338 : 1649978 : tab->partition_dependencies[version] =
339 : 1649978 : BITMAP_ALLOC (&ter_bitmap_obstack);
340 : 1682250 : bitmap_ior_into (tab->partition_dependencies[version],
341 : 1682250 : tab->new_replaceable_dependencies);
342 : 1682250 : bitmap_ior_into (tab->partition_in_use,
343 : 1682250 : tab->new_replaceable_dependencies);
344 : : /* It is only necessary to add these once. */
345 : 1682250 : bitmap_clear (tab->new_replaceable_dependencies);
346 : : }
347 : : }
348 : : else
349 : : {
350 : 5608241 : i = var_to_partition (tab->map, var);
351 : 5608241 : gcc_checking_assert (i != NO_PARTITION);
352 : 5608241 : 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 : 5608241 : if (tab->num_in_part[i] > 1)
357 : : {
358 : 1324332 : add_to_partition_kill_list (tab, i, version);
359 : 1324332 : make_dependent_on_partition (tab, version, i);
360 : : }
361 : : }
362 : 9158088 : }
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 : 8758016 : finished_with_expr (temp_expr_table *tab, int version, bool free_expr)
371 : : {
372 : 8758016 : unsigned i;
373 : 8758016 : 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 : 8758016 : if (tab->partition_dependencies[version])
378 : : {
379 : 11202201 : EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
380 : 6024003 : remove_from_partition_kill_list (tab, i, version);
381 : 5178198 : BITMAP_FREE (tab->partition_dependencies[version]);
382 : : }
383 : 8758016 : if (free_expr)
384 : 5208169 : BITMAP_FREE (tab->expr_decl_uids[version]);
385 : 8758016 : }
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 : 40499198 : ter_is_replaceable_p (gimple *stmt)
395 : : {
396 : :
397 : 40499198 : if (ssa_is_replaceable_p (stmt))
398 : : {
399 : 17918654 : use_operand_p use_p;
400 : 17918654 : tree def;
401 : 17918654 : gimple *use_stmt;
402 : 17918654 : location_t locus1, locus2;
403 : 17918654 : 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 : 17918654 : def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
409 : 17918654 : 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 : 17918654 : if (gimple_bb (use_stmt) != gimple_bb (stmt))
414 : : return false;
415 : :
416 : 17521071 : locus1 = gimple_location (stmt);
417 : 17521071 : block1 = LOCATION_BLOCK (locus1);
418 : 13856199 : locus1 = LOCATION_LOCUS (locus1);
419 : :
420 : 17521071 : 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 : 17521071 : locus2 = gimple_location (use_stmt);
425 : 17521071 : block2 = LOCATION_BLOCK (locus2);
426 : 14806623 : locus2 = LOCATION_LOCUS (locus2);
427 : :
428 : 17521071 : if ((!optimize || optimize_debug)
429 : 18169 : && ((locus1 != UNKNOWN_LOCATION && locus1 != locus2)
430 : 13130 : || (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 : 8758016 : process_replaceable (temp_expr_table *tab, gimple *stmt, int call_cnt,
443 : : int reg_vars_cnt)
444 : : {
445 : 8758016 : tree var, def, basevar;
446 : 8758016 : int version;
447 : 8758016 : ssa_op_iter iter;
448 : 8758016 : bitmap def_vars, use_vars;
449 : :
450 : 8758016 : gcc_checking_assert (ter_is_replaceable_p (stmt));
451 : :
452 : 8758016 : def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
453 : 8758016 : version = SSA_NAME_VERSION (def);
454 : 8758016 : def_vars = BITMAP_ALLOC (&ter_bitmap_obstack);
455 : :
456 : 8758016 : basevar = SSA_NAME_VAR (def);
457 : 788531 : if (basevar)
458 : 788531 : bitmap_set_bit (def_vars, DECL_UID (basevar));
459 : :
460 : : /* Add this expression to the dependency list for each use partition. */
461 : 17916104 : FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
462 : : {
463 : 9158088 : int var_version = SSA_NAME_VERSION (var);
464 : :
465 : 9158088 : use_vars = tab->expr_decl_uids[var_version];
466 : 9158088 : add_dependence (tab, version, var);
467 : 9158088 : if (use_vars)
468 : : {
469 : 3549847 : bitmap_ior_into (def_vars, use_vars);
470 : 3549847 : BITMAP_FREE (tab->expr_decl_uids[var_version]);
471 : : }
472 : 5608241 : else if (SSA_NAME_VAR (var))
473 : 3061075 : bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
474 : : }
475 : 8758016 : tab->expr_decl_uids[version] = def_vars;
476 : :
477 : : /* If there are VUSES, add a dependence on virtual defs. */
478 : 17516032 : if (gimple_vuse (stmt))
479 : : {
480 : 2791502 : make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
481 : 2791502 : add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
482 : : }
483 : :
484 : 8758016 : tab->call_cnt[version] = call_cnt;
485 : 8758016 : tab->reg_vars_cnt[version] = reg_vars_cnt;
486 : 8758016 : }
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 : 11079367 : kill_expr (temp_expr_table *tab, int partition)
494 : : {
495 : 11079367 : 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 : 11312368 : while (tab->kill_list[partition])
500 : : {
501 : 233001 : version = bitmap_first_set_bit (tab->kill_list[partition]);
502 : 233001 : finished_with_expr (tab, version, true);
503 : : }
504 : :
505 : 11079367 : gcc_checking_assert (!tab->kill_list[partition]);
506 : 11079367 : }
507 : :
508 : :
509 : : /* This function kills all expressions in TAB which are dependent on virtual
510 : : partitions. */
511 : :
512 : : static inline void
513 : 11051678 : kill_virtual_exprs (temp_expr_table *tab)
514 : : {
515 : 11051678 : kill_expr (tab, VIRTUAL_PARTITION (tab));
516 : 11051678 : }
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 : 8300549 : mark_replaceable (temp_expr_table *tab, tree var, bool more_replacing)
525 : : {
526 : 8300549 : int version = SSA_NAME_VERSION (var);
527 : :
528 : : /* Move the dependence list to the pending listpending. */
529 : 8300549 : if (more_replacing && tab->partition_dependencies[version])
530 : 1898786 : bitmap_ior_into (tab->new_replaceable_dependencies,
531 : : tab->partition_dependencies[version]);
532 : :
533 : 8300549 : 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 : 8300549 : if (!tab->replaceable_expressions)
539 : 649394 : tab->replaceable_expressions = BITMAP_ALLOC (NULL);
540 : 8300549 : bitmap_set_bit (tab->replaceable_expressions, version);
541 : 8300549 : }
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 : 26220 : find_ssaname (tree *tp, int *walk_subtrees, void *data)
549 : : {
550 : 26220 : tree var = (tree) data;
551 : 26220 : if (*tp == var)
552 : : return var;
553 : 26179 : else if (IS_TYPE_OR_DECL_P (*tp))
554 : 20473 : *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 : 21411 : find_ssaname_in_store (gimple *, tree, tree t, void *data)
564 : : {
565 : 21411 : 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 : 8615737 : find_replaceable_in_bb (temp_expr_table *tab, basic_block bb)
573 : : {
574 : 8615737 : gimple_stmt_iterator bsi;
575 : 8615737 : gimple *stmt;
576 : 8615737 : tree def, use, fndecl;
577 : 8615737 : int partition;
578 : 8615737 : var_map map = tab->map;
579 : 8615737 : ssa_op_iter iter;
580 : 8615737 : bool stmt_replaceable;
581 : 8615737 : int cur_call_cnt = 0;
582 : 8615737 : int cur_reg_vars_cnt = 0;
583 : :
584 : 89165043 : for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
585 : : {
586 : 71933569 : stmt = gsi_stmt (bsi);
587 : :
588 : 71933569 : if (is_gimple_debug (stmt))
589 : 40192387 : continue;
590 : :
591 : 31741182 : stmt_replaceable = ter_is_replaceable_p (stmt);
592 : :
593 : : /* Determine if this stmt finishes an existing expression. */
594 : 60029220 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
595 : : {
596 : 28288038 : unsigned ver = SSA_NAME_VERSION (use);
597 : :
598 : : /* If this use is a potential replacement variable, process it. */
599 : 28288038 : if (tab->expr_decl_uids[ver])
600 : : {
601 : 8525015 : bool same_root_var = false;
602 : 8525015 : ssa_op_iter iter2;
603 : 8525015 : 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 : 8525015 : if (!bitmap_empty_p (vars))
609 : 7364816 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
610 : : {
611 : 2980563 : if (SSA_NAME_VAR (def)
612 : 671022 : && 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 : 15773245 : if (gimple_vdef (stmt))
623 : : {
624 : 2052652 : gimple *def_stmt = SSA_NAME_DEF_STMT (use);
625 : 2052868 : while (is_gimple_assign (def_stmt)
626 : 2052868 : && gimple_assign_rhs_code (def_stmt) == SSA_NAME)
627 : 216 : def_stmt
628 : 216 : = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
629 : 10577667 : if (gimple_vuse (def_stmt)
630 : 677755 : && gimple_assign_single_p (def_stmt)
631 : 2730046 : && 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 : 389874 : if (is_gimple_call (stmt)
645 : 389874 : || gimple_code (stmt) == GIMPLE_ASM)
646 : : {
647 : 322360 : if (walk_stmt_load_store_ops (stmt, use, NULL,
648 : : find_ssaname_in_store))
649 : 67555 : 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 : 15720938 : if (gimple_has_volatile_ops (stmt) || same_root_var
665 : 8353621 : || (tab->call_cnt[ver] != cur_call_cnt
666 : 85484 : && (SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use),
667 : : SSA_OP_USE)
668 : : == NULL_USE_OPERAND_P
669 : 34902 : || gimple_could_trap_p (SSA_NAME_DEF_STMT (use))))
670 : 15548792 : || tab->reg_vars_cnt[ver] != cur_reg_vars_cnt)
671 : 224466 : finished_with_expr (tab, ver, true);
672 : : else
673 : 8300549 : mark_replaceable (tab, use, stmt_replaceable);
674 : : }
675 : : }
676 : :
677 : : /* Next, see if this stmt kills off an active expression. */
678 : 48161599 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
679 : : {
680 : 16420417 : partition = var_to_partition (map, def);
681 : 16420417 : if (partition != NO_PARTITION && tab->kill_list[partition])
682 : 27689 : 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 : 31741182 : if (is_gimple_call (stmt)
689 : 36510798 : && !((fndecl = gimple_call_fndecl (stmt))
690 : 4769616 : && fndecl_built_in_p (fndecl)))
691 : 3630681 : cur_call_cnt++;
692 : :
693 : : /* Increment counter if this statement sets a local
694 : : register variable. */
695 : 31741182 : if (gimple_assign_single_p (stmt)
696 : 31741182 : && (VAR_P (gimple_assign_lhs (stmt))
697 : 1610400 : && DECL_HARD_REGISTER (gimple_assign_lhs (stmt))))
698 : 1004 : cur_reg_vars_cnt++;
699 : :
700 : : /* Now see if we are creating a new expression or not. */
701 : 31741182 : if (stmt_replaceable)
702 : 8758016 : process_replaceable (tab, stmt, cur_call_cnt, cur_reg_vars_cnt);
703 : :
704 : : /* Free any unused dependency lists. */
705 : 31741182 : 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 : 131107674 : if (gimple_vdef (stmt))
710 : 11051678 : kill_virtual_exprs (tab);
711 : : }
712 : 8615737 : }
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 : 998644 : find_replaceable_exprs (var_map map)
725 : : {
726 : 998644 : basic_block bb;
727 : 998644 : temp_expr_table *table;
728 : 998644 : bitmap ret;
729 : :
730 : 998644 : bitmap_obstack_initialize (&ter_bitmap_obstack);
731 : 998644 : table = new_temp_expr_table (map);
732 : 9614381 : FOR_EACH_BB_FN (bb, cfun)
733 : : {
734 : 8615737 : find_replaceable_in_bb (table, bb);
735 : 8615737 : gcc_checking_assert (bitmap_empty_p (table->partition_in_use));
736 : : }
737 : 998644 : ret = free_temp_expr_table (table);
738 : 998644 : bitmap_obstack_release (&ter_bitmap_obstack);
739 : 998644 : 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 : }
|
