Line data Source code
1 : /* Back-propagation of usage information to definitions.
2 : Copyright (C) 2015-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3, or (at your option)
9 : any later version.
10 :
11 : GCC is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : /* This pass propagates information that is common to all uses of an SSA
21 : name back up through the sequence of statements that generate it,
22 : simplifying the statements where possible. Sometimes this can expose
23 : fully or partially dead code, but the main focus is simplifying
24 : computations.
25 :
26 : At the moment the pass only handles one piece of information: whether the
27 : sign of a value matters, and therefore whether sign-changing operations
28 : can be skipped. The pass could be extended to more interesting
29 : information in future, such as which bits of an integer are significant.
30 :
31 : For example, take the function:
32 :
33 : double
34 : f (double *a, int n, double start)
35 : {
36 : double x = fabs (start);
37 : for (int i = 0; i < n; ++i)
38 : x *= a[i];
39 : return __builtin_cos (x);
40 : }
41 :
42 : cos(x) == cos(-x), so the sign of the final x doesn't matter.
43 : That x is the result of a series of multiplications, and if
44 : the sign of the result of a multiplication doesn't matter,
45 : the signs of the inputs don't matter either.
46 :
47 : The pass would replace the incoming value of x (i.e. fabs(start))
48 : with start. Since there are no other uses of the fabs result,
49 : the call would get deleted as dead.
50 :
51 : The algorithm is:
52 :
53 : (1) Do a post-order traversal of the blocks in the function, walking
54 : each block backwards. For each potentially-simplifiable statement
55 : that defines an SSA name X, examine all uses of X to see what
56 : information is actually significant. Record this in VAR_TABLE[X].
57 : Optimistically ignore for now any back-edge references to
58 : unprocessed phis.
59 :
60 : (An alternative would be to record each use when we visit its
61 : statement and take the intersection as we go along. However,
62 : this would lead to more SSA names being entered into VAR_TABLE
63 : unnecessarily, only to be taken out again later. At the moment
64 : very few SSA names end up with useful information.)
65 :
66 : (2) Iteratively reduce the optimistic result of (1) until we reach
67 : a maximal fixed point. First push all SSA names that used an
68 : optimistic assumption about a backedge phi onto a worklist.
69 : While the worklist is nonempty, pick off an SSA name X and recompute
70 : the usage information in VAR_TABLE[X]. If the value changes, push all
71 : SSA names used in the definition of X onto the worklist.
72 :
73 : (3) Iterate over each SSA name X with info in VAR_TABLE, in the
74 : opposite order to (1), i.e. a forward reverse-post-order walk.
75 : Try to use the information in VAR_TABLE[X] to replace the definition
76 : of X with a simpler calculation that may yield a different result.
77 : When deciding to do such a replacement, record that each entry in
78 : VAR_TABLE that directly or indirectly depends on X will then also
79 : need to be replaced with a different calculation. (The information
80 : in VAR_TABLE guarantees that other uses of X are unaffected.)
81 :
82 : (4) Iterate over each SSA name X with info in VAR_TABLE, in the same
83 : order as (1). Carry out any scheduled replacement of X with a
84 : different value, ensuring that debug uses either keep their current
85 : value or are reset. (This traversal order ensures that, if a chain
86 : of values is being replaced, a debug bind is created for the last
87 : value first, exposing a new debug use of the preceding value in
88 : the chain.)
89 :
90 : (5) Iterate over each SSA name X with info in VAR_TABLE, in the same order
91 : as (1). Delete any statements that are now dead. (This traversal order
92 : ensures that if a sequence of statements is dead, we delete the last
93 : statement first. It is not safe to do this on-the-fly during (4)
94 : because multiple SSA names might be replaced with the same value.)
95 :
96 : Note that this pass does not deal with direct redundancies,
97 : such as cos(-x)->cos(x). match.pd handles those cases instead. */
98 :
99 : #include "config.h"
100 : #include "system.h"
101 : #include "coretypes.h"
102 : #include "backend.h"
103 : #include "tree.h"
104 : #include "gimple.h"
105 : #include "gimple-iterator.h"
106 : #include "ssa.h"
107 : #include "fold-const.h"
108 : #include "tree-pass.h"
109 : #include "cfganal.h"
110 : #include "gimple-pretty-print.h"
111 : #include "tree-cfg.h"
112 : #include "tree-ssa.h"
113 : #include "tree-ssa-propagate.h"
114 : #include "gimple-fold.h"
115 : #include "alloc-pool.h"
116 : #include "tree-hash-traits.h"
117 : #include "case-cfn-macros.h"
118 :
119 : namespace {
120 :
121 : /* Information about a group of uses of an SSA name. */
122 : class usage_info
123 : {
124 : public:
125 66808571 : usage_info () : flag_word (0) {}
126 : usage_info &operator &= (const usage_info &);
127 : usage_info operator & (const usage_info &) const;
128 : bool operator == (const usage_info &) const;
129 : bool operator != (const usage_info &) const;
130 : bool is_useful () const;
131 :
132 : static usage_info intersection_identity ();
133 :
134 : union
135 : {
136 : struct
137 : {
138 : /* True if the uses treat x and -x in the same way. */
139 : unsigned int ignore_sign : 1;
140 : } flags;
141 : /* All the flag bits as a single int. */
142 : unsigned int flag_word;
143 : };
144 : };
145 :
146 : /* Return an X such that X & Y == Y for all Y. This is the most
147 : optimistic assumption possible. */
148 :
149 : usage_info
150 22500420 : usage_info::intersection_identity ()
151 : {
152 22500420 : usage_info ret;
153 22500420 : ret.flag_word = -1;
154 22500420 : return ret;
155 : }
156 :
157 : /* Intersect *THIS with OTHER, so that *THIS describes all uses covered
158 : by the original *THIS and OTHER. */
159 :
160 : usage_info &
161 21801963 : usage_info::operator &= (const usage_info &other)
162 : {
163 21801963 : flag_word &= other.flag_word;
164 21801963 : return *this;
165 : }
166 :
167 : /* Return the intersection of *THIS and OTHER, i.e. a structure that
168 : describes all uses covered by *THIS and OTHER. */
169 :
170 : usage_info
171 63 : usage_info::operator & (const usage_info &other) const
172 : {
173 63 : usage_info info (*this);
174 63 : info &= other;
175 63 : return info;
176 : }
177 :
178 : bool
179 5262 : usage_info::operator == (const usage_info &other) const
180 : {
181 5262 : return flag_word == other.flag_word;
182 : }
183 :
184 : bool
185 5262 : usage_info::operator != (const usage_info &other) const
186 : {
187 5262 : return !operator == (other);
188 : }
189 :
190 : /* Return true if *THIS is not simply the default, safe assumption. */
191 :
192 : bool
193 22506251 : usage_info::is_useful () const
194 : {
195 22506251 : return flag_word != 0;
196 : }
197 :
198 : /* Start a dump line about SSA name VAR. */
199 :
200 : static void
201 200 : dump_usage_prefix (FILE *file, tree var)
202 : {
203 200 : fprintf (file, " ");
204 200 : print_generic_expr (file, var);
205 200 : fprintf (file, ": ");
206 200 : }
207 :
208 : /* Print INFO to FILE. */
209 :
210 : static void
211 332 : dump_usage_info (FILE *file, tree var, usage_info *info)
212 : {
213 332 : if (info->flags.ignore_sign)
214 : {
215 200 : dump_usage_prefix (file, var);
216 200 : fprintf (file, "sign bit not important\n");
217 : }
218 332 : }
219 :
220 : /* Information about an SSA name that we might want to optimize. */
221 : struct var_info
222 : {
223 956026 : var_info (tree var, unsigned int index, const usage_info &info)
224 956026 : : var (var), new_value (var), seq (nullptr), index (index), info (info)
225 : {}
226 :
227 : /* The SSA name itself. */
228 : tree var;
229 :
230 : /* The value that VAR will be replaced with, or VAR itself if no
231 : replacement is scheduled. */
232 : tree new_value;
233 :
234 : /* If NEW_VALUE != VAR, the definition of VAR will be replaced by this
235 : sequence, with an empty sequence meaning that the definition of VAR
236 : should simply be deleted. */
237 : gimple_seq seq;
238 :
239 : /* The index of this entry in the M_VARS array. */
240 : unsigned int index;
241 :
242 : /* Information about all uses of the SSA name. */
243 : usage_info info;
244 : };
245 :
246 : /* Hash var_info based on the SSA name. */
247 : struct var_info_hasher : nofree_ptr_hash<var_info>
248 : {
249 : using compare_type = const_tree;
250 :
251 : static inline hashval_t hash (const var_info *);
252 : static inline bool equal (const var_info *, const_tree);
253 : };
254 :
255 : hashval_t
256 8171818 : var_info_hasher::hash (const var_info *v)
257 : {
258 8171818 : return SSA_NAME_VERSION (v->var);
259 : }
260 :
261 : bool
262 10974973 : var_info_hasher::equal (const var_info *v, const_tree var)
263 : {
264 10974973 : return v->var == var;
265 : }
266 :
267 : /* Represents one execution of the pass. */
268 : class backprop
269 : {
270 : public:
271 : backprop (function *);
272 : ~backprop ();
273 :
274 : void execute ();
275 :
276 : private:
277 : var_info *lookup_operand (tree);
278 :
279 : void push_to_worklist (var_info *);
280 : var_info *pop_from_worklist ();
281 :
282 : void process_builtin_call_use (gcall *, tree, usage_info *);
283 : void process_assign_use (gassign *, tree, usage_info *);
284 : void process_phi_use (gphi *, usage_info *);
285 : void process_use (gimple *, tree, usage_info *);
286 : bool intersect_uses (tree, usage_info *);
287 : void reprocess_inputs (gimple *);
288 : void process_var (tree, var_info *);
289 : void process_block (basic_block);
290 :
291 : void set_new_value (var_info *, tree);
292 : tree subst_operand (tree);
293 : gimple *copy_and_subst (var_info *);
294 : void finish_stmt (var_info *, gimple *);
295 : void optimize_builtin_call (gcall *, var_info *);
296 : void replace_assign_rhs (var_info *, tree, tree, tree);
297 : void optimize_assign (gassign *, var_info *);
298 : void optimize_phi (gphi *, var_info *);
299 :
300 : void propagate_change (var_info *);
301 : void commit_replacement (var_info *);
302 :
303 : /* The function we're optimizing. */
304 : function *m_fn;
305 :
306 : /* Pool for allocating var_info structures. */
307 : object_allocator<var_info> m_var_pool;
308 :
309 : /* All extant var_infos, hashed by SSA name. All the usage_infos satisfy
310 : is_useful.
311 :
312 : We use a hash_table because the table is expected to be sparse
313 : (i.e. most SSA names won't have useful information attached to them).
314 : We could move to a directly-indexed array if that situation changes. */
315 : hash_table<var_info_hasher> m_var_table;
316 :
317 : /* A post-ordered list of the contents of M_VAR_TABLE. Entries might
318 : be null if we initially created a var_info and then withdrew it. */
319 : auto_vec<var_info *, 128> m_vars;
320 :
321 : /* A bitmap of blocks that we have finished processing in the initial
322 : post-order walk. */
323 : auto_sbitmap m_visited_blocks;
324 :
325 : /* A bitmap of phis that we have finished processing in the initial
326 : post-order walk, excluding those from blocks mentioned in
327 : M_VISITED_BLOCKS. */
328 : auto_bitmap m_visited_phis;
329 :
330 : /* Two bitmaps that can be used for worklists. The elements represent
331 : indices into M_VARS. */
332 : auto_bitmap m_worklist1, m_worklist2;
333 :
334 : /* Used to perform a double-worklist update. M_THIS_WORKLIST contains
335 : the elements of M_VARS that should be processed in the current pass,
336 : whereas M_NEXT_WORKLIST contains the elements of M_VARS that should
337 : be processed in the next pass.
338 :
339 : In a post-order traversal, any member of M_VARS beyond index
340 : M_WORKLIST_THRESHOLD can be added to M_THIS_WORKLIST whereas others
341 : should be added to M_NEXT_WORKLIST. */
342 : bitmap m_this_worklist, m_next_worklist;
343 : unsigned int m_worklist_threshold;
344 : };
345 :
346 1039731 : backprop::backprop (function *fn)
347 1039731 : : m_fn (fn),
348 1039731 : m_var_pool ("var_info"),
349 1039731 : m_var_table (64),
350 1039731 : m_visited_blocks (last_basic_block_for_fn (m_fn)),
351 1039731 : m_this_worklist (m_worklist1),
352 1039731 : m_next_worklist (m_worklist2),
353 1039731 : m_worklist_threshold (UINT_MAX)
354 : {
355 1039731 : bitmap_clear (m_visited_blocks);
356 1039731 : bitmap_tree_view (m_worklist1);
357 1039731 : bitmap_tree_view (m_worklist2);
358 1039731 : }
359 :
360 1039731 : backprop::~backprop ()
361 : {
362 1039731 : m_var_pool.release ();
363 1039731 : }
364 :
365 : /* Return the var_info for general operand OP, or null if none. */
366 :
367 : var_info *
368 8367551 : backprop::lookup_operand (tree op)
369 : {
370 8367551 : if (op && TREE_CODE (op) == SSA_NAME)
371 6616781 : return m_var_table.find_with_hash (op, SSA_NAME_VERSION (op));
372 : return NULL;
373 : }
374 :
375 : /* Add V to the worklist, if it isn't on the worklist already. */
376 :
377 : void
378 898486 : backprop::push_to_worklist (var_info *v)
379 : {
380 898486 : bitmap worklist = (v->index > m_worklist_threshold
381 898486 : ? m_this_worklist
382 : : m_next_worklist);
383 898486 : if (bitmap_set_bit (worklist, v->index)
384 898486 : && (dump_file && (dump_flags & TDF_DETAILS)))
385 : {
386 36 : fprintf (dump_file, "[WORKLIST] Pushing ");
387 36 : print_generic_expr (dump_file, v->var);
388 36 : fprintf (dump_file, "\n");
389 : }
390 898486 : }
391 :
392 : /* Remove and return the next var_info from the worklist. The worklist
393 : is known to be nonempty. */
394 :
395 : var_info *
396 886313 : backprop::pop_from_worklist ()
397 : {
398 886313 : m_worklist_threshold = bitmap_clear_first_set_bit (m_this_worklist);
399 886313 : var_info *v = m_vars[m_worklist_threshold];
400 886313 : if (dump_file && (dump_flags & TDF_DETAILS))
401 : {
402 36 : fprintf (dump_file, "[WORKLIST] Popping ");
403 36 : print_generic_expr (dump_file, v->var);
404 36 : fprintf (dump_file, "\n");
405 : }
406 886313 : return v;
407 : }
408 :
409 : /* Make INFO describe all uses of RHS in CALL, which is a call to a
410 : built-in function. */
411 :
412 : void
413 2820475 : backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
414 : {
415 2820475 : combined_fn fn = gimple_call_combined_fn (call);
416 2820475 : tree lhs = gimple_call_lhs (call);
417 2820475 : switch (fn)
418 : {
419 : case CFN_LAST:
420 : break;
421 :
422 571 : CASE_CFN_COS:
423 571 : CASE_CFN_COS_FN:
424 571 : CASE_CFN_COSH:
425 571 : CASE_CFN_COSH_FN:
426 571 : CASE_CFN_CCOS:
427 571 : CASE_CFN_CCOS_FN:
428 571 : CASE_CFN_CCOSH:
429 571 : CASE_CFN_CCOSH_FN:
430 571 : CASE_CFN_HYPOT:
431 571 : CASE_CFN_HYPOT_FN:
432 : /* The signs of all inputs are ignored. */
433 571 : info->flags.ignore_sign = true;
434 571 : break;
435 :
436 28172 : CASE_CFN_COPYSIGN:
437 28172 : CASE_CFN_COPYSIGN_FN:
438 : /* The sign of the first input is ignored. */
439 28172 : if (rhs != gimple_call_arg (call, 1))
440 591 : info->flags.ignore_sign = true;
441 : break;
442 :
443 564 : CASE_CFN_POW:
444 564 : CASE_CFN_POW_FN:
445 564 : {
446 : /* The sign of the first input is ignored as long as the second
447 : input is an even real. */
448 564 : tree power = gimple_call_arg (call, 1);
449 564 : HOST_WIDE_INT n;
450 564 : if (TREE_CODE (power) == REAL_CST
451 63 : && real_isinteger (&TREE_REAL_CST (power), &n)
452 597 : && (n & 1) == 0)
453 31 : info->flags.ignore_sign = true;
454 564 : break;
455 : }
456 :
457 742 : CASE_CFN_FMA:
458 742 : CASE_CFN_FMA_FN:
459 742 : case CFN_FMS:
460 742 : case CFN_FNMA:
461 742 : case CFN_FNMS:
462 : /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
463 : matter. */
464 742 : if (gimple_call_arg (call, 0) == rhs
465 307 : && gimple_call_arg (call, 1) == rhs
466 796 : && gimple_call_arg (call, 2) != rhs)
467 54 : info->flags.ignore_sign = true;
468 : break;
469 :
470 737083 : default:
471 737083 : if (negate_mathfn_p (fn))
472 : /* The sign of the (single) input doesn't matter provided
473 : that the sign of the output doesn't matter. */
474 2577 : if (var_info *lhsv = lookup_operand (lhs))
475 46 : info->flags.ignore_sign = lhsv->info.flags.ignore_sign;
476 : break;
477 : }
478 2820475 : }
479 :
480 : /* Make INFO describe all uses of RHS in ASSIGN. */
481 :
482 : void
483 12211300 : backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
484 : {
485 12211300 : tree lhs = gimple_assign_lhs (assign);
486 17660857 : switch (gimple_assign_rhs_code (assign))
487 : {
488 13724 : case ABS_EXPR:
489 13724 : case ABSU_EXPR:
490 : /* The sign of the input doesn't matter. */
491 13724 : info->flags.ignore_sign = true;
492 13724 : break;
493 :
494 7677 : case COND_EXPR:
495 : /* For A = B ? C : D, propagate information about all uses of A
496 : to C and D. */
497 7677 : if (rhs != gimple_assign_rhs1 (assign))
498 3803 : if (var_info *lhsv = lookup_operand (lhs))
499 941 : *info = lhsv->info;
500 : break;
501 :
502 854910 : case MULT_EXPR:
503 : /* In X * X, the sign of X doesn't matter. */
504 854910 : if (gimple_assign_rhs1 (assign) == rhs
505 1559532 : && gimple_assign_rhs2 (assign) == rhs)
506 15110 : info->flags.ignore_sign = true;
507 : /* Fall through. */
508 :
509 907062 : case NEGATE_EXPR:
510 907062 : case RDIV_EXPR:
511 : /* If the sign of the result doesn't matter, the sign of the inputs
512 : doesn't matter either. */
513 907062 : if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
514 139710 : if (var_info *lhsv = lookup_operand (lhs))
515 2992 : info->flags.ignore_sign = lhsv->info.flags.ignore_sign;
516 : break;
517 :
518 : default:
519 : break;
520 : }
521 12211300 : }
522 :
523 : /* Make INFO describe the uses of PHI's result. */
524 :
525 : void
526 2496883 : backprop::process_phi_use (gphi *phi, usage_info *info)
527 : {
528 2496883 : tree result = gimple_phi_result (phi);
529 2496883 : if (var_info *resultv = lookup_operand (result))
530 228892 : *info = resultv->info;
531 2496883 : }
532 :
533 : /* Make INFO describe all uses of RHS in STMT. */
534 :
535 : void
536 21801900 : backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
537 : {
538 21801900 : if (dump_file && (dump_flags & TDF_DETAILS))
539 : {
540 244 : fprintf (dump_file, "[USE] ");
541 244 : print_generic_expr (dump_file, rhs);
542 244 : fprintf (dump_file, " in ");
543 244 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
544 : }
545 :
546 21801900 : if (gcall *call = dyn_cast <gcall *> (stmt))
547 2820475 : process_builtin_call_use (call, rhs, info);
548 18981425 : else if (gassign *assign = dyn_cast <gassign *> (stmt))
549 12211300 : process_assign_use (assign, rhs, info);
550 6770125 : else if (gphi *phi = dyn_cast <gphi *> (stmt))
551 2496883 : process_phi_use (phi, info);
552 :
553 21801900 : if (dump_file && (dump_flags & TDF_DETAILS))
554 244 : dump_usage_info (dump_file, rhs, info);
555 21801900 : }
556 :
557 : /* Make INFO describe all uses of VAR, returning true if the result
558 : is useful. If the uses include phis that haven't been processed yet,
559 : make the most optimistic assumption possible, so that we aim for
560 : a maximum rather than a minimum fixed point. */
561 :
562 : bool
563 22500420 : backprop::intersect_uses (tree var, usage_info *info)
564 : {
565 22500420 : imm_use_iterator iter;
566 22500420 : use_operand_p use_p;
567 22500420 : *info = usage_info::intersection_identity ();
568 49807154 : FOR_EACH_IMM_USE_FAST (use_p, iter, var)
569 : {
570 26345446 : gimple *stmt = USE_STMT (use_p);
571 26345446 : if (is_gimple_debug (stmt))
572 3548620 : continue;
573 22796826 : gphi *phi = dyn_cast <gphi *> (stmt);
574 3491809 : if (phi
575 3491809 : && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index)
576 998816 : && !bitmap_bit_p (m_visited_phis,
577 998816 : SSA_NAME_VERSION (gimple_phi_result (phi))))
578 : {
579 : /* Skip unprocessed phis. */
580 994926 : if (dump_file && (dump_flags & TDF_DETAILS))
581 : {
582 18 : fprintf (dump_file, "[BACKEDGE] ");
583 18 : print_generic_expr (dump_file, var);
584 18 : fprintf (dump_file, " in ");
585 18 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
586 : }
587 : }
588 : else
589 : {
590 21801900 : usage_info subinfo;
591 21801900 : process_use (stmt, var, &subinfo);
592 21801900 : *info &= subinfo;
593 21801900 : if (!info->is_useful ())
594 21539132 : return false;
595 : }
596 21539132 : }
597 961288 : return true;
598 : }
599 :
600 : /* Queue for reconsideration any input of STMT that has information
601 : associated with it. This is used if that information might be
602 : too optimistic. */
603 :
604 : void
605 4523806 : backprop::reprocess_inputs (gimple *stmt)
606 : {
607 4523806 : use_operand_p use_p;
608 4523806 : ssa_op_iter oi;
609 14770026 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
610 5722414 : if (var_info *v = lookup_operand (get_use_from_ptr (use_p)))
611 898486 : push_to_worklist (v);
612 4523806 : }
613 :
614 : /* Say that we're recording INFO for SSA name VAR, or that we're deleting
615 : existing information if INFO is null. INTRO describes the change. */
616 :
617 : static void
618 106 : dump_var_info (tree var, usage_info *info, const char *intro)
619 : {
620 106 : fprintf (dump_file, "[DEF] %s for ", intro);
621 106 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
622 106 : if (info)
623 88 : dump_usage_info (dump_file, var, info);
624 106 : }
625 :
626 : /* Process all uses of VAR and record or update the result in
627 : M_VAR_TABLE and M_VARS. V is the current entry for VAR, or null
628 : if we are looking at it for the first time. */
629 :
630 : void
631 22660573 : backprop::process_var (tree var, var_info *v)
632 : {
633 22660573 : if (has_zero_uses (var))
634 154322 : return;
635 :
636 22506251 : usage_info info;
637 :
638 : /* Propagating along abnormal edges is delicate, punt for now. */
639 22506251 : if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (var))
640 22500420 : intersect_uses (var, &info);
641 :
642 22506251 : gimple *stmt = SSA_NAME_DEF_STMT (var);
643 22506251 : auto hash = SSA_NAME_VERSION (var);
644 22506251 : if (info.is_useful ())
645 : {
646 961288 : if (!v)
647 : {
648 : /* Recording information about VAR for the first time. */
649 1912052 : v = m_var_pool.allocate (var, m_vars.length (), info);
650 956026 : m_vars.safe_push (v);
651 956026 : *m_var_table.find_slot_with_hash (var, hash, INSERT) = v;
652 :
653 956026 : if (dump_file && (dump_flags & TDF_DETAILS))
654 82 : dump_var_info (var, &v->info, "Recording new information");
655 :
656 : /* If STMT is a phi, reprocess any backedge uses. This is a
657 : no-op for other uses, which won't have any information
658 : associated with them. */
659 956026 : if (is_a <gphi *> (stmt))
660 180713 : reprocess_inputs (stmt);
661 : }
662 5262 : else if (info != v->info)
663 : {
664 : /* Recording information that is less optimistic than before. */
665 63 : gcc_checking_assert ((info & v->info) == info);
666 63 : v->info = info;
667 63 : if (dump_file && (dump_flags & TDF_DETAILS))
668 6 : dump_var_info (var, &v->info, "Updating information");
669 63 : reprocess_inputs (stmt);
670 : }
671 : }
672 : else
673 : {
674 21544963 : if (v)
675 : {
676 : /* Removing previously-recorded information. */
677 881051 : m_var_table.remove_elt_with_hash (var, hash);
678 881051 : m_vars[v->index] = nullptr;
679 881051 : m_var_pool.remove (v);
680 :
681 881051 : if (dump_file && (dump_flags & TDF_DETAILS))
682 18 : dump_var_info (var, NULL, "Deleting information");
683 881051 : reprocess_inputs (stmt);
684 : }
685 : else
686 : {
687 : /* If STMT is a phi, remove any information recorded for
688 : its arguments. */
689 20663912 : if (is_a <gphi *> (stmt))
690 3461979 : reprocess_inputs (stmt);
691 : }
692 : }
693 : }
694 :
695 : /* Process all statements and phis in BB, during the first post-order walk. */
696 :
697 : void
698 11381393 : backprop::process_block (basic_block bb)
699 : {
700 11381393 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
701 183566461 : gsi_prev (&gsi))
702 : {
703 86092534 : tree lhs = gimple_get_lhs (gsi_stmt (gsi));
704 86092534 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
705 18119876 : process_var (lhs, nullptr);
706 : }
707 15035777 : for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
708 3654384 : gsi_next (&gpi))
709 : {
710 3654384 : tree result = gimple_phi_result (gpi.phi ());
711 3654384 : process_var (result, nullptr);
712 3654384 : bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));
713 : }
714 11381393 : bitmap_clear (m_visited_phis);
715 11381393 : }
716 :
717 : /* Delete the statement at GSI, which is now dead. Note the deletion in the
718 : dump file unless QUIET is true. */
719 :
720 : static void
721 191 : remove_dead_stmt (gimple_stmt_iterator *gsi, bool quiet = false)
722 : {
723 191 : gimple *stmt = gsi_stmt (*gsi);
724 191 : if (!quiet && dump_file && (dump_flags & TDF_DETAILS))
725 : {
726 28 : fprintf (dump_file, "Deleting ");
727 28 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
728 : }
729 191 : if (gimple_code (stmt) == GIMPLE_PHI)
730 97 : remove_phi_node (gsi, true);
731 : else
732 : {
733 94 : unlink_stmt_vdef (stmt);
734 94 : gsi_remove (gsi, true);
735 94 : release_defs (stmt);
736 : }
737 191 : }
738 :
739 : /* If RHS is an SSA name whose definition just changes the sign of a value,
740 : return that other value, otherwise return null. */
741 :
742 : static tree
743 152179 : strip_sign_op_1 (tree rhs)
744 : {
745 152179 : if (TREE_CODE (rhs) != SSA_NAME)
746 : return NULL_TREE;
747 :
748 151667 : gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
749 151667 : if (gassign *assign = dyn_cast <gassign *> (def_stmt))
750 144219 : switch (gimple_assign_rhs_code (assign))
751 : {
752 280 : case ABS_EXPR:
753 280 : case NEGATE_EXPR:
754 280 : return gimple_assign_rhs1 (assign);
755 :
756 : default:
757 : break;
758 : }
759 78901 : else if (gcall *call = dyn_cast <gcall *> (def_stmt))
760 39099 : switch (gimple_call_combined_fn (call))
761 : {
762 13 : CASE_CFN_COPYSIGN:
763 13 : CASE_CFN_COPYSIGN_FN:
764 13 : return gimple_call_arg (call, 0);
765 :
766 : default:
767 : break;
768 : }
769 :
770 : return NULL_TREE;
771 : }
772 :
773 : /* If RHS is an SSA name whose definition just changes the sign of a value,
774 : strip all such operations and return the ultimate input to them.
775 : Return null otherwise.
776 :
777 : Although this could in principle lead to quadratic searching,
778 : in practice a long sequence of sign manipulations should already
779 : have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
780 : for more than one operation in order to catch cases like -abs(x). */
781 :
782 : static tree
783 151886 : strip_sign_op (tree rhs)
784 : {
785 151886 : tree new_rhs = strip_sign_op_1 (rhs);
786 151886 : if (!new_rhs)
787 : return NULL_TREE;
788 293 : while (tree next = strip_sign_op_1 (new_rhs))
789 : new_rhs = next;
790 : return new_rhs;
791 : }
792 :
793 : /* Note that V's SSA name will be replaced with NEW_VALUE. */
794 :
795 : void
796 362 : backprop::set_new_value (var_info *v, tree new_value)
797 : {
798 362 : if (dump_file && (dump_flags & TDF_DETAILS))
799 : {
800 33 : if (v->var == v->new_value)
801 30 : fprintf (dump_file, "\n");
802 33 : fprintf (dump_file, "Uses of ");
803 33 : print_generic_expr (dump_file, v->var);
804 33 : fprintf (dump_file, " will be replaced by ");
805 33 : print_generic_expr (dump_file, new_value);
806 33 : fprintf (dump_file, "\n");
807 : }
808 362 : v->new_value = new_value;
809 362 : }
810 :
811 : /* Apply all current substitutions to gimple operand VALUE. */
812 :
813 : tree
814 1216 : backprop::subst_operand (tree value)
815 : {
816 1216 : if (const var_info *v = lookup_operand (value))
817 509 : return v->new_value;
818 :
819 : return value;
820 : }
821 :
822 : /* Assuming that V's SSA name occurs as "lhs" in a statement of the form:
823 :
824 : S: lhs = op (rhs1, rhs2, ...)
825 :
826 : create and insert a new statement:
827 :
828 : S': lhs'= op (rhs1', rhs2', ...)
829 :
830 : where:
831 :
832 : lhs' is a new SSA name
833 : rhsN' = subst_operand (rhsN)
834 :
835 : Arrange for lhs to be replaced with lhs'.
836 :
837 : Return S'. After making any required changes to S', the caller should
838 : call finish_stmt (V, S') to finish scheduling the replacement. */
839 :
840 : gimple *
841 330 : backprop::copy_and_subst (var_info *v)
842 : {
843 330 : gcc_assert (v->new_value == v->var);
844 330 : gimple *stmt = SSA_NAME_DEF_STMT (v->var);
845 330 : set_new_value (v, copy_ssa_name_fn (m_fn, v->var, stmt));
846 330 : if (auto *phi = dyn_cast<gphi *> (stmt))
847 : {
848 70 : gphi *new_phi = create_phi_node (v->new_value, gimple_bb (phi));
849 70 : gimple_set_location (new_phi, gimple_location (phi));
850 210 : for (unsigned int i = 0; i < gimple_phi_num_args (phi); ++i)
851 : {
852 140 : tree arg_def = subst_operand (gimple_phi_arg_def (phi, i));
853 140 : SET_USE (gimple_phi_arg_imm_use_ptr (new_phi, i), arg_def);
854 : }
855 : return new_phi;
856 : }
857 : else
858 : {
859 260 : gimple *new_stmt = gimple_copy (stmt);
860 1048 : for (unsigned int i = 0; i < gimple_num_ops (new_stmt); ++i)
861 : {
862 788 : tree *op_ptr = gimple_op_ptr (new_stmt, i);
863 1576 : *op_ptr = subst_operand (*op_ptr);
864 : }
865 260 : SSA_NAME_DEF_STMT (v->new_value) = new_stmt;
866 260 : gimple_seq_add_stmt (&v->seq, new_stmt);
867 260 : return new_stmt;
868 : }
869 : }
870 :
871 : /* Finalize STMT, whose lhs will replace V's SSA name. */
872 :
873 : void
874 330 : backprop::finish_stmt (var_info *v, gimple *stmt)
875 : {
876 330 : if (dump_file && (dump_flags & TDF_DETAILS))
877 : {
878 30 : fprintf (dump_file, "Replacing ");
879 30 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (v->var), TDF_SLIM);
880 30 : fprintf (dump_file, " with ");
881 30 : print_gimple_stmt (dump_file, stmt, TDF_SLIM);
882 : }
883 330 : tree new_value = v->new_value;
884 330 : gimple_stmt_iterator gsi;
885 330 : if (auto *phi = dyn_cast<gphi *> (stmt))
886 : {
887 70 : gsi = gsi_for_stmt (phi);
888 70 : new_value = degenerate_phi_result (phi);
889 : }
890 : else
891 : {
892 260 : gsi = gsi_for_stmt (stmt, &v->seq);
893 260 : fold_stmt (&gsi);
894 260 : stmt = gsi_stmt (gsi);
895 260 : if (gimple_assign_single_p (stmt))
896 4 : new_value = gimple_assign_rhs1 (stmt);
897 : }
898 330 : update_stmt (stmt);
899 330 : if (new_value && new_value != v->new_value && is_gimple_val (new_value))
900 : {
901 26 : remove_dead_stmt (&gsi);
902 26 : set_new_value (v, new_value);
903 : }
904 330 : }
905 :
906 : /* Optimize CALL, a call to a built-in function, given that V describes
907 : its lhs. */
908 :
909 : void
910 327 : backprop::optimize_builtin_call (gcall *call, var_info *v)
911 : {
912 : /* If we have an f such that -f(x) = f(-x), and if the sign of the result
913 : doesn't matter, strip any sign operations from the input. */
914 327 : if (v->info.flags.ignore_sign
915 327 : && negate_mathfn_p (gimple_call_combined_fn (call)))
916 : {
917 61 : tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
918 61 : if (new_arg)
919 : {
920 24 : call = as_a<gcall *> (copy_and_subst (v));
921 48 : gimple_call_set_arg (call, 0, subst_operand (new_arg));
922 24 : finish_stmt (v, call);
923 : }
924 : }
925 327 : }
926 :
927 : /* Optimize V by replacing rhs operand N with RHS<N>, if RHS<N> is nonnull. */
928 :
929 : void
930 951 : backprop::replace_assign_rhs (var_info *v, tree rhs1, tree rhs2, tree rhs3)
931 : {
932 951 : if (!rhs1 && !rhs2 && !rhs3)
933 : return;
934 :
935 198 : auto *assign = as_a<gassign *> (copy_and_subst (v));
936 198 : if (rhs1)
937 260 : gimple_assign_set_rhs1 (assign, subst_operand (rhs1));
938 198 : if (rhs2)
939 136 : gimple_assign_set_rhs2 (assign, subst_operand (rhs2));
940 198 : if (rhs3)
941 0 : gimple_assign_set_rhs3 (assign, subst_operand (rhs3));
942 198 : finish_stmt (v, assign);
943 : }
944 :
945 : /* Optimize ASSIGN given that V describes its lhs. */
946 :
947 : void
948 15267 : backprop::optimize_assign (gassign *assign, var_info *v)
949 : {
950 20157 : switch (gimple_assign_rhs_code (assign))
951 : {
952 951 : case MULT_EXPR:
953 951 : case RDIV_EXPR:
954 : /* If the sign of the result doesn't matter, strip sign operations
955 : from both inputs. */
956 951 : if (v->info.flags.ignore_sign)
957 1902 : replace_assign_rhs (v, strip_sign_op (gimple_assign_rhs1 (assign)),
958 : strip_sign_op (gimple_assign_rhs2 (assign)),
959 : NULL_TREE);
960 : break;
961 :
962 0 : case COND_EXPR:
963 : /* If the sign of A ? B : C doesn't matter, strip sign operations
964 : from both B and C. */
965 0 : if (v->info.flags.ignore_sign)
966 0 : replace_assign_rhs (v, NULL_TREE,
967 : strip_sign_op (gimple_assign_rhs2 (assign)),
968 : strip_sign_op (gimple_assign_rhs3 (assign)));
969 : break;
970 :
971 : default:
972 : break;
973 : }
974 15267 : }
975 :
976 : /* Optimize PHI given that V describes its result. */
977 :
978 : void
979 59381 : backprop::optimize_phi (gphi *phi, var_info *v)
980 : {
981 : /* If the sign of the result doesn't matter, strip sign operations
982 : from all arguments. */
983 59381 : if (v->info.flags.ignore_sign)
984 : {
985 : gphi *replacement = nullptr;
986 209304 : for (unsigned int i = 0; i < gimple_phi_num_args (phi); ++i)
987 : {
988 149923 : tree arg = gimple_phi_arg_def (phi, i);
989 149923 : tree new_arg = strip_sign_op (arg);
990 149923 : if (new_arg)
991 : {
992 66 : if (!replacement)
993 56 : replacement = as_a<gphi *> (copy_and_subst (v));
994 132 : SET_USE (gimple_phi_arg_imm_use_ptr (replacement, i),
995 : subst_operand (new_arg));
996 : }
997 : }
998 59381 : if (replacement)
999 56 : finish_stmt (v, replacement);
1000 : }
1001 59381 : }
1002 :
1003 : /* V is being replaced with something that may have a different value.
1004 : If that would change the result of any dependent statement,
1005 : make sure that that dependent statement will also be replaced. */
1006 :
1007 : void
1008 330 : backprop::propagate_change (var_info *v)
1009 : {
1010 330 : use_operand_p use_p;
1011 330 : imm_use_iterator use_iter;
1012 1278 : FOR_EACH_IMM_USE_FAST (use_p, use_iter, v->var)
1013 : {
1014 618 : tree lhs = gimple_get_lhs (USE_STMT (use_p));
1015 618 : if (const var_info *lhsv = lookup_operand (lhs))
1016 106 : if (lhsv->new_value == lhsv->var)
1017 73 : bitmap_set_bit (m_this_worklist, lhsv->index);
1018 330 : }
1019 330 : }
1020 :
1021 : /* Implement the scheduled replacement for V. */
1022 :
1023 : void
1024 330 : backprop::commit_replacement (var_info *v)
1025 : {
1026 330 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1027 106 : insert_debug_temp_for_var_def (NULL, v->var);
1028 :
1029 330 : gimple *stmt = SSA_NAME_DEF_STMT (v->var);
1030 330 : use_operand_p use_p;
1031 330 : imm_use_iterator iterator;
1032 968 : FOR_EACH_IMM_USE_STMT (stmt, iterator, v->var)
1033 : {
1034 1584 : FOR_EACH_IMM_USE_ON_STMT (use_p, iterator)
1035 484 : SET_USE (use_p, v->new_value);
1036 308 : update_stmt (stmt);
1037 330 : }
1038 :
1039 330 : gimple_stmt_iterator gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (v->var));
1040 330 : if (v->seq)
1041 256 : gsi_replace_with_seq_vops (&gsi, v->seq);
1042 : else
1043 74 : remove_dead_stmt (&gsi, true);
1044 330 : }
1045 :
1046 : void
1047 1039731 : backprop::execute ()
1048 : {
1049 : /* Phase 1: Traverse the function, making optimistic assumptions
1050 : about any phi whose definition we haven't seen. Add any variables
1051 : that need to be reconsidered to M_NEXT_WORKLIST. */
1052 1039731 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
1053 1039731 : unsigned int postorder_num = post_order_compute (postorder, false, false);
1054 12421124 : for (unsigned int i = 0; i < postorder_num; ++i)
1055 : {
1056 11381393 : process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
1057 11381393 : bitmap_set_bit (m_visited_blocks, postorder[i]);
1058 : }
1059 1039731 : XDELETEVEC (postorder);
1060 :
1061 : /* Phase 2: Use the initial (perhaps overly optimistic) information
1062 : to create a maximal fixed point solution. Each pass uses a post-order
1063 : walk to reduce the number of repeat visits. */
1064 1219752 : while (!bitmap_empty_p (m_next_worklist))
1065 : {
1066 180021 : std::swap (m_this_worklist, m_next_worklist);
1067 180021 : bitmap_clear (m_next_worklist);
1068 886313 : do
1069 : {
1070 886313 : var_info *v = pop_from_worklist ();
1071 886313 : process_var (v->var, v);
1072 : }
1073 886313 : while (!bitmap_empty_p (m_this_worklist));
1074 : }
1075 :
1076 : /* Phase 3: Do a reverse post-order walk, using information about the uses of
1077 : SSA names to see whether computing a different value would be simpler and
1078 : would have the same effect. Start to compute the transitive closure of
1079 : SSA names whose definitions are due to be replaced with new
1080 : calculations. */
1081 1039731 : bitmap_clear (m_this_worklist);
1082 3035488 : for (unsigned int i = m_vars.length (); i-- > 0;)
1083 956026 : if (var_info *v = m_vars[i])
1084 : {
1085 74975 : gimple *stmt = SSA_NAME_DEF_STMT (v->var);
1086 74975 : if (gcall *call = dyn_cast <gcall *> (stmt))
1087 327 : optimize_builtin_call (call, v);
1088 74648 : else if (gassign *assign = dyn_cast <gassign *> (stmt))
1089 15267 : optimize_assign (assign, v);
1090 59381 : else if (gphi *phi = dyn_cast <gphi *> (stmt))
1091 59381 : optimize_phi (phi, v);
1092 :
1093 74975 : if (bitmap_clear_bit (m_this_worklist, v->index))
1094 50 : if (v->new_value == v->var)
1095 32 : finish_stmt (v, copy_and_subst (v));
1096 :
1097 74975 : if (v->new_value != v->var)
1098 310 : propagate_change (v);
1099 : }
1100 :
1101 : /* Complete the transitive closure started by the previous loop. */
1102 1039751 : while (!bitmap_empty_p (m_this_worklist))
1103 : {
1104 20 : var_info *v = m_vars[bitmap_clear_last_set_bit (m_this_worklist)];
1105 20 : finish_stmt (v, copy_and_subst (v));
1106 20 : propagate_change (v);
1107 : }
1108 :
1109 : /* Now that we have a complete set of values that need to change,
1110 : calculate the transitive closure of replacement values. */
1111 1039731 : bool changed = false;
1112 3035488 : for (unsigned int i = m_vars.length (); i-- > 0;)
1113 956026 : if (var_info *v = m_vars[i])
1114 74975 : if (v->var != v->new_value)
1115 330 : if (var_info *newv = lookup_operand (v->new_value))
1116 : {
1117 6 : gcc_assert (newv->index > i);
1118 6 : if (!changed && dump_file && (dump_flags & TDF_DETAILS))
1119 0 : fprintf (dump_file, "\n");
1120 6 : set_new_value (v, newv->new_value);
1121 6 : changed = true;
1122 : }
1123 :
1124 1039731 : if (dump_file && (dump_flags & TDF_DETAILS))
1125 21 : fprintf (dump_file, "\n");
1126 :
1127 : /* Phase 4: Do a post-order walk, creating debug bind expressions for
1128 : SSA names that are about to disappear. Replace all non-debug uses
1129 : of old SSA names with uses of whatever calculation is replacing them. */
1130 1995757 : for (unsigned int i = 0; i < m_vars.length (); ++i)
1131 956026 : if (var_info *v = m_vars[i])
1132 74975 : if (v->var != v->new_value)
1133 330 : commit_replacement (v);
1134 :
1135 : /* Phase 5: Remove any statements that might have become dead. */
1136 1039731 : auto_bitmap deleted_vars;
1137 1995757 : for (unsigned int i = 0; i < m_vars.length (); ++i)
1138 956026 : if (var_info *v = m_vars[i])
1139 74975 : if (TREE_CODE (v->new_value) == SSA_NAME
1140 74971 : && !SSA_NAME_IS_DEFAULT_DEF (v->new_value)
1141 74956 : && has_zero_uses (v->new_value)
1142 75067 : && bitmap_set_bit (deleted_vars, SSA_NAME_VERSION (v->new_value)))
1143 : {
1144 91 : gimple *stmt = SSA_NAME_DEF_STMT (v->new_value);
1145 91 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1146 91 : remove_dead_stmt (&gsi);
1147 : }
1148 :
1149 1039731 : if (dump_file && (dump_flags & TDF_DETAILS))
1150 21 : fprintf (dump_file, "\n");
1151 1039731 : }
1152 :
1153 : const pass_data pass_data_backprop =
1154 : {
1155 : GIMPLE_PASS, /* type */
1156 : "backprop", /* name */
1157 : OPTGROUP_NONE, /* optinfo_flags */
1158 : TV_TREE_BACKPROP, /* tv_id */
1159 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1160 : 0, /* properties_provided */
1161 : 0, /* properties_destroyed */
1162 : 0, /* todo_flags_start */
1163 : 0, /* todo_flags_finish */
1164 : };
1165 :
1166 : class pass_backprop : public gimple_opt_pass
1167 : {
1168 : public:
1169 298828 : pass_backprop (gcc::context *ctxt)
1170 597656 : : gimple_opt_pass (pass_data_backprop, ctxt)
1171 : {}
1172 :
1173 : /* opt_pass methods: */
1174 0 : opt_pass * clone () final override { return new pass_backprop (m_ctxt); }
1175 1039819 : bool gate (function *) final override { return flag_ssa_backprop; }
1176 : unsigned int execute (function *) final override;
1177 :
1178 : }; // class pass_backprop
1179 :
1180 : unsigned int
1181 1039731 : pass_backprop::execute (function *fn)
1182 : {
1183 1039731 : backprop (fn).execute ();
1184 1039731 : return 0;
1185 : }
1186 :
1187 : } // anon namespace
1188 :
1189 : gimple_opt_pass *
1190 298828 : make_pass_backprop (gcc::context *ctxt)
1191 : {
1192 298828 : return new pass_backprop (ctxt);
1193 : }
|
