1/* Back-propagation of usage information to definitions.
2 Copyright (C) 2015-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along 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 as INFO_MAP[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 INFO_MAP
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 (which at the moment would mean revisiting
68 statements at most once). First push all SSA names that used an
69 optimistic assumption about a backedge phi onto a worklist.
70 While the worklist is nonempty, pick off an SSA name X and recompute
71 INFO_MAP[X]. If the value changes, push all SSA names used in the
72 definition of X onto the worklist.
73
74 (3) Iterate over each SSA name X with info in INFO_MAP, in the
75 opposite order to (1), i.e. a forward reverse-post-order walk.
76 Try to optimize the definition of X using INFO_MAP[X] and fold
77 the result. (This ensures that we fold definitions before uses.)
78
79 (4) Iterate over each SSA name X with info in INFO_MAP, in the same
80 order as (1), and delete any statements that are now dead.
81 (This ensures that if a sequence of statements is dead,
82 we delete the last statement first.)
83
84 Note that this pass does not deal with direct redundancies,
85 such as cos(-x)->cos(x). match.pd handles those cases instead. */
86
87#include "config.h"
88#include "system.h"
89#include "coretypes.h"
90#include "backend.h"
91#include "tree.h"
92#include "gimple.h"
93#include "gimple-iterator.h"
94#include "ssa.h"
95#include "fold-const.h"
96#include "tree-pass.h"
97#include "cfganal.h"
98#include "gimple-pretty-print.h"
99#include "tree-cfg.h"
100#include "tree-ssa.h"
101#include "tree-ssa-propagate.h"
102#include "gimple-fold.h"
103#include "alloc-pool.h"
104#include "tree-hash-traits.h"
105#include "case-cfn-macros.h"
106
107namespace {
108
109/* Information about a group of uses of an SSA name. */
110class usage_info
111{
112public:
113 usage_info () : flag_word (0) {}
114 usage_info &operator &= (const usage_info &);
115 usage_info operator & (const usage_info &) const;
116 bool operator == (const usage_info &) const;
117 bool operator != (const usage_info &) const;
118 bool is_useful () const;
119
120 static usage_info intersection_identity ();
121
122 union
123 {
124 struct
125 {
126 /* True if the uses treat x and -x in the same way. */
127 unsigned int ignore_sign : 1;
128 } flags;
129 /* All the flag bits as a single int. */
130 unsigned int flag_word;
131 };
132};
133
134/* Return an X such that X & Y == Y for all Y. This is the most
135 optimistic assumption possible. */
136
137usage_info
138usage_info::intersection_identity ()
139{
140 usage_info ret;
141 ret.flag_word = -1;
142 return ret;
143}
144
145/* Intersect *THIS with OTHER, so that *THIS describes all uses covered
146 by the original *THIS and OTHER. */
147
148usage_info &
149usage_info::operator &= (const usage_info &other)
150{
151 flag_word &= other.flag_word;
152 return *this;
153}
154
155/* Return the intersection of *THIS and OTHER, i.e. a structure that
156 describes all uses covered by *THIS and OTHER. */
157
158usage_info
159usage_info::operator & (const usage_info &other) const
160{
161 usage_info info (*this);
162 info &= other;
163 return info;
164}
165
166bool
167usage_info::operator == (const usage_info &other) const
168{
169 return flag_word == other.flag_word;
170}
171
172bool
173usage_info::operator != (const usage_info &other) const
174{
175 return !operator == (other);
176}
177
178/* Return true if *THIS is not simply the default, safe assumption. */
179
180bool
181usage_info::is_useful () const
182{
183 return flag_word != 0;
184}
185
186/* Start a dump line about SSA name VAR. */
187
188static void
189dump_usage_prefix (FILE *file, tree var)
190{
191 fprintf (stream: file, format: " ");
192 print_generic_expr (file, var);
193 fprintf (stream: file, format: ": ");
194}
195
196/* Print INFO to FILE. */
197
198static void
199dump_usage_info (FILE *file, tree var, usage_info *info)
200{
201 if (info->flags.ignore_sign)
202 {
203 dump_usage_prefix (file, var);
204 fprintf (stream: file, format: "sign bit not important\n");
205 }
206}
207
208/* Represents one execution of the pass. */
209class backprop
210{
211public:
212 backprop (function *);
213 ~backprop ();
214
215 void execute ();
216
217private:
218 const usage_info *lookup_operand (tree);
219
220 void push_to_worklist (tree);
221 tree pop_from_worklist ();
222
223 void process_builtin_call_use (gcall *, tree, usage_info *);
224 void process_assign_use (gassign *, tree, usage_info *);
225 void process_phi_use (gphi *, usage_info *);
226 void process_use (gimple *, tree, usage_info *);
227 bool intersect_uses (tree, usage_info *);
228 void reprocess_inputs (gimple *);
229 void process_var (tree);
230 void process_block (basic_block);
231
232 void prepare_change (tree);
233 void complete_change (gimple *);
234 void optimize_builtin_call (gcall *, tree, const usage_info *);
235 void replace_assign_rhs (gassign *, tree, tree, tree, tree);
236 void optimize_assign (gassign *, tree, const usage_info *);
237 void optimize_phi (gphi *, tree, const usage_info *);
238
239 typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type;
240 typedef std::pair <tree, usage_info *> var_info_pair;
241
242 /* The function we're optimizing. */
243 function *m_fn;
244
245 /* Pool for allocating usage_info structures. */
246 object_allocator <usage_info> m_info_pool;
247
248 /* Maps an SSA name to a description of all uses of that SSA name.
249 All the usage_infos satisfy is_useful.
250
251 We use a hash_map because the map is expected to be sparse
252 (i.e. most SSA names won't have useful information attached to them).
253 We could move to a directly-indexed array if that situation changes. */
254 info_map_type m_info_map;
255
256 /* Post-ordered list of all potentially-interesting SSA names,
257 along with information that describes all uses. */
258 auto_vec <var_info_pair, 128> m_vars;
259
260 /* A bitmap of blocks that we have finished processing in the initial
261 post-order walk. */
262 auto_sbitmap m_visited_blocks;
263
264 /* A bitmap of phis that we have finished processing in the initial
265 post-order walk, excluding those from blocks mentioned in
266 M_VISITED_BLOCKS. */
267 auto_bitmap m_visited_phis;
268
269 /* A worklist of SSA names whose definitions need to be reconsidered. */
270 auto_vec <tree, 64> m_worklist;
271
272 /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION.
273 We use a bitmap rather than an sbitmap because most SSA names are
274 never added to the worklist. */
275 bitmap m_worklist_names;
276};
277
278backprop::backprop (function *fn)
279 : m_fn (fn),
280 m_info_pool ("usage_info"),
281 m_visited_blocks (last_basic_block_for_fn (m_fn)),
282 m_worklist_names (BITMAP_ALLOC (NULL))
283{
284 bitmap_clear (m_visited_blocks);
285}
286
287backprop::~backprop ()
288{
289 BITMAP_FREE (m_worklist_names);
290 m_info_pool.release ();
291}
292
293/* Return usage information for general operand OP, or null if none. */
294
295const usage_info *
296backprop::lookup_operand (tree op)
297{
298 if (op && TREE_CODE (op) == SSA_NAME)
299 {
300 usage_info **slot = m_info_map.get (k: op);
301 if (slot)
302 return *slot;
303 }
304 return NULL;
305}
306
307/* Add SSA name VAR to the worklist, if it isn't on the worklist already. */
308
309void
310backprop::push_to_worklist (tree var)
311{
312 if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var)))
313 return;
314 m_worklist.safe_push (obj: var);
315 if (dump_file && (dump_flags & TDF_DETAILS))
316 {
317 fprintf (stream: dump_file, format: "[WORKLIST] Pushing ");
318 print_generic_expr (dump_file, var);
319 fprintf (stream: dump_file, format: "\n");
320 }
321}
322
323/* Remove and return the next SSA name from the worklist. The worklist
324 is known to be nonempty. */
325
326tree
327backprop::pop_from_worklist ()
328{
329 tree var = m_worklist.pop ();
330 bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var));
331 if (dump_file && (dump_flags & TDF_DETAILS))
332 {
333 fprintf (stream: dump_file, format: "[WORKLIST] Popping ");
334 print_generic_expr (dump_file, var);
335 fprintf (stream: dump_file, format: "\n");
336 }
337 return var;
338}
339
340/* Make INFO describe all uses of RHS in CALL, which is a call to a
341 built-in function. */
342
343void
344backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
345{
346 combined_fn fn = gimple_call_combined_fn (call);
347 tree lhs = gimple_call_lhs (gs: call);
348 switch (fn)
349 {
350 case CFN_LAST:
351 break;
352
353 CASE_CFN_COS:
354 CASE_CFN_COS_FN:
355 CASE_CFN_COSH:
356 CASE_CFN_COSH_FN:
357 CASE_CFN_CCOS:
358 CASE_CFN_CCOS_FN:
359 CASE_CFN_CCOSH:
360 CASE_CFN_CCOSH_FN:
361 CASE_CFN_HYPOT:
362 CASE_CFN_HYPOT_FN:
363 /* The signs of all inputs are ignored. */
364 info->flags.ignore_sign = true;
365 break;
366
367 CASE_CFN_COPYSIGN:
368 CASE_CFN_COPYSIGN_FN:
369 /* The sign of the first input is ignored. */
370 if (rhs != gimple_call_arg (gs: call, index: 1))
371 info->flags.ignore_sign = true;
372 break;
373
374 CASE_CFN_POW:
375 CASE_CFN_POW_FN:
376 {
377 /* The sign of the first input is ignored as long as the second
378 input is an even real. */
379 tree power = gimple_call_arg (gs: call, index: 1);
380 HOST_WIDE_INT n;
381 if (TREE_CODE (power) == REAL_CST
382 && real_isinteger (&TREE_REAL_CST (power), &n)
383 && (n & 1) == 0)
384 info->flags.ignore_sign = true;
385 break;
386 }
387
388 CASE_CFN_FMA:
389 CASE_CFN_FMA_FN:
390 case CFN_FMS:
391 case CFN_FNMA:
392 case CFN_FNMS:
393 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
394 matter. */
395 if (gimple_call_arg (gs: call, index: 0) == rhs
396 && gimple_call_arg (gs: call, index: 1) == rhs
397 && gimple_call_arg (gs: call, index: 2) != rhs)
398 info->flags.ignore_sign = true;
399 break;
400
401 default:
402 if (negate_mathfn_p (fn))
403 {
404 /* The sign of the (single) input doesn't matter provided
405 that the sign of the output doesn't matter. */
406 const usage_info *lhs_info = lookup_operand (op: lhs);
407 if (lhs_info)
408 info->flags.ignore_sign = lhs_info->flags.ignore_sign;
409 }
410 break;
411 }
412}
413
414/* Make INFO describe all uses of RHS in ASSIGN. */
415
416void
417backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
418{
419 tree lhs = gimple_assign_lhs (gs: assign);
420 switch (gimple_assign_rhs_code (gs: assign))
421 {
422 case ABS_EXPR:
423 case ABSU_EXPR:
424 /* The sign of the input doesn't matter. */
425 info->flags.ignore_sign = true;
426 break;
427
428 case COND_EXPR:
429 /* For A = B ? C : D, propagate information about all uses of A
430 to C and D. */
431 if (rhs != gimple_assign_rhs1 (gs: assign))
432 {
433 const usage_info *lhs_info = lookup_operand (op: lhs);
434 if (lhs_info)
435 *info = *lhs_info;
436 }
437 break;
438
439 case MULT_EXPR:
440 /* In X * X, the sign of X doesn't matter. */
441 if (gimple_assign_rhs1 (gs: assign) == rhs
442 && gimple_assign_rhs2 (gs: assign) == rhs)
443 info->flags.ignore_sign = true;
444 /* Fall through. */
445
446 case NEGATE_EXPR:
447 case RDIV_EXPR:
448 /* If the sign of the result doesn't matter, the sign of the inputs
449 doesn't matter either. */
450 if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
451 {
452 const usage_info *lhs_info = lookup_operand (op: lhs);
453 if (lhs_info)
454 info->flags.ignore_sign = lhs_info->flags.ignore_sign;
455 }
456 break;
457
458 default:
459 break;
460 }
461}
462
463/* Make INFO describe the uses of PHI's result. */
464
465void
466backprop::process_phi_use (gphi *phi, usage_info *info)
467{
468 tree result = gimple_phi_result (gs: phi);
469 if (const usage_info *result_info = lookup_operand (op: result))
470 *info = *result_info;
471}
472
473/* Make INFO describe all uses of RHS in STMT. */
474
475void
476backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
477{
478 if (dump_file && (dump_flags & TDF_DETAILS))
479 {
480 fprintf (stream: dump_file, format: "[USE] ");
481 print_generic_expr (dump_file, rhs);
482 fprintf (stream: dump_file, format: " in ");
483 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
484 }
485
486 if (gcall *call = dyn_cast <gcall *> (p: stmt))
487 process_builtin_call_use (call, rhs, info);
488 else if (gassign *assign = dyn_cast <gassign *> (p: stmt))
489 process_assign_use (assign, rhs, info);
490 else if (gphi *phi = dyn_cast <gphi *> (p: stmt))
491 process_phi_use (phi, info);
492
493 if (dump_file && (dump_flags & TDF_DETAILS))
494 dump_usage_info (file: dump_file, var: rhs, info);
495}
496
497/* Make INFO describe all uses of VAR, returning true if the result
498 is useful. If the uses include phis that haven't been processed yet,
499 make the most optimistic assumption possible, so that we aim for
500 a maximum rather than a minimum fixed point. */
501
502bool
503backprop::intersect_uses (tree var, usage_info *info)
504{
505 imm_use_iterator iter;
506 use_operand_p use_p;
507 *info = usage_info::intersection_identity ();
508 FOR_EACH_IMM_USE_FAST (use_p, iter, var)
509 {
510 gimple *stmt = USE_STMT (use_p);
511 if (is_gimple_debug (gs: stmt))
512 continue;
513 gphi *phi = dyn_cast <gphi *> (p: stmt);
514 if (phi
515 && !bitmap_bit_p (map: m_visited_blocks, bitno: gimple_bb (g: phi)->index)
516 && !bitmap_bit_p (m_visited_phis,
517 SSA_NAME_VERSION (gimple_phi_result (phi))))
518 {
519 /* Skip unprocessed phis. */
520 if (dump_file && (dump_flags & TDF_DETAILS))
521 {
522 fprintf (stream: dump_file, format: "[BACKEDGE] ");
523 print_generic_expr (dump_file, var);
524 fprintf (stream: dump_file, format: " in ");
525 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
526 }
527 }
528 else
529 {
530 usage_info subinfo;
531 process_use (stmt, rhs: var, info: &subinfo);
532 *info &= subinfo;
533 if (!info->is_useful ())
534 return false;
535 }
536 }
537 return true;
538}
539
540/* Queue for reconsideration any input of STMT that has information
541 associated with it. This is used if that information might be
542 too optimistic. */
543
544void
545backprop::reprocess_inputs (gimple *stmt)
546{
547 use_operand_p use_p;
548 ssa_op_iter oi;
549 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
550 {
551 tree var = get_use_from_ptr (use: use_p);
552 if (lookup_operand (op: var))
553 push_to_worklist (var);
554 }
555}
556
557/* Say that we're recording INFO for SSA name VAR, or that we're deleting
558 existing information if INFO is null. INTRO describes the change. */
559
560static void
561dump_var_info (tree var, usage_info *info, const char *intro)
562{
563 fprintf (stream: dump_file, format: "[DEF] %s for ", intro);
564 print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
565 if (info)
566 dump_usage_info (file: dump_file, var, info);
567}
568
569/* Process all uses of VAR and record or update the result in
570 M_INFO_MAP and M_VARS. */
571
572void
573backprop::process_var (tree var)
574{
575 if (has_zero_uses (var))
576 return;
577
578 usage_info info;
579 intersect_uses (var, info: &info);
580
581 gimple *stmt = SSA_NAME_DEF_STMT (var);
582 if (info.is_useful ())
583 {
584 bool existed;
585 usage_info *&map_info = m_info_map.get_or_insert (k: var, existed: &existed);
586 if (!existed)
587 {
588 /* Recording information about VAR for the first time. */
589 map_info = m_info_pool.allocate ();
590 *map_info = info;
591 m_vars.safe_push (obj: var_info_pair (var, map_info));
592 if (dump_file && (dump_flags & TDF_DETAILS))
593 dump_var_info (var, info: map_info, intro: "Recording new information");
594
595 /* If STMT is a phi, reprocess any backedge uses. This is a
596 no-op for other uses, which won't have any information
597 associated with them. */
598 if (is_a <gphi *> (p: stmt))
599 reprocess_inputs (stmt);
600 }
601 else if (info != *map_info)
602 {
603 /* Recording information that is less optimistic than before. */
604 gcc_checking_assert ((info & *map_info) == info);
605 *map_info = info;
606 if (dump_file && (dump_flags & TDF_DETAILS))
607 dump_var_info (var, info: map_info, intro: "Updating information");
608 reprocess_inputs (stmt);
609 }
610 }
611 else
612 {
613 if (usage_info **slot = m_info_map.get (k: var))
614 {
615 /* Removing previously-recorded information. */
616 **slot = info;
617 m_info_map.remove (k: var);
618 if (dump_file && (dump_flags & TDF_DETAILS))
619 dump_var_info (var, NULL, intro: "Deleting information");
620 reprocess_inputs (stmt);
621 }
622 else
623 {
624 /* If STMT is a phi, remove any information recorded for
625 its arguments. */
626 if (is_a <gphi *> (p: stmt))
627 reprocess_inputs (stmt);
628 }
629 }
630}
631
632/* Process all statements and phis in BB, during the first post-order walk. */
633
634void
635backprop::process_block (basic_block bb)
636{
637 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (i: gsi);
638 gsi_prev (i: &gsi))
639 {
640 tree lhs = gimple_get_lhs (gsi_stmt (i: gsi));
641 if (lhs && TREE_CODE (lhs) == SSA_NAME)
642 process_var (var: lhs);
643 }
644 for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (i: gpi);
645 gsi_next (i: &gpi))
646 {
647 tree result = gimple_phi_result (gs: gpi.phi ());
648 process_var (var: result);
649 bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));
650 }
651 bitmap_clear (m_visited_phis);
652}
653
654/* Delete the definition of VAR, which has no uses. */
655
656static void
657remove_unused_var (tree var)
658{
659 gimple *stmt = SSA_NAME_DEF_STMT (var);
660 if (dump_file && (dump_flags & TDF_DETAILS))
661 {
662 fprintf (stream: dump_file, format: "Deleting ");
663 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
664 }
665 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
666 gsi_remove (&gsi, true);
667 release_defs (stmt);
668}
669
670/* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */
671
672static void
673note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
674{
675 fprintf (stream: dump_file, format: "Replacing use of ");
676 print_generic_expr (dump_file, old_rhs);
677 fprintf (stream: dump_file, format: " with ");
678 print_generic_expr (dump_file, new_rhs);
679 fprintf (stream: dump_file, format: " in ");
680 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
681}
682
683/* If RHS is an SSA name whose definition just changes the sign of a value,
684 return that other value, otherwise return null. */
685
686static tree
687strip_sign_op_1 (tree rhs)
688{
689 if (TREE_CODE (rhs) != SSA_NAME)
690 return NULL_TREE;
691
692 gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
693 if (gassign *assign = dyn_cast <gassign *> (p: def_stmt))
694 switch (gimple_assign_rhs_code (gs: assign))
695 {
696 case ABS_EXPR:
697 case NEGATE_EXPR:
698 return gimple_assign_rhs1 (gs: assign);
699
700 default:
701 break;
702 }
703 else if (gcall *call = dyn_cast <gcall *> (p: def_stmt))
704 switch (gimple_call_combined_fn (call))
705 {
706 CASE_CFN_COPYSIGN:
707 CASE_CFN_COPYSIGN_FN:
708 return gimple_call_arg (gs: call, index: 0);
709
710 default:
711 break;
712 }
713
714 return NULL_TREE;
715}
716
717/* If RHS is an SSA name whose definition just changes the sign of a value,
718 strip all such operations and return the ultimate input to them.
719 Return null otherwise.
720
721 Although this could in principle lead to quadratic searching,
722 in practice a long sequence of sign manipulations should already
723 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
724 for more than one operation in order to catch cases like -abs(x). */
725
726static tree
727strip_sign_op (tree rhs)
728{
729 tree new_rhs = strip_sign_op_1 (rhs);
730 if (!new_rhs)
731 return NULL_TREE;
732 while (tree next = strip_sign_op_1 (rhs: new_rhs))
733 new_rhs = next;
734 return new_rhs;
735}
736
737/* Start a change in the value of VAR that is suitable for all non-debug
738 uses of VAR. We need to make sure that debug statements continue to
739 use the original definition of VAR where possible, or are nullified
740 otherwise. */
741
742void
743backprop::prepare_change (tree var)
744{
745 if (MAY_HAVE_DEBUG_BIND_STMTS)
746 insert_debug_temp_for_var_def (NULL, var);
747 reset_flow_sensitive_info (var);
748}
749
750/* STMT has been changed. Give the fold machinery a chance to simplify
751 and canonicalize it (e.g. by ensuring that commutative operands have
752 the right order), then record the updates. */
753
754void
755backprop::complete_change (gimple *stmt)
756{
757 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
758 if (fold_stmt (&gsi))
759 {
760 if (dump_file && (dump_flags & TDF_DETAILS))
761 {
762 fprintf (stream: dump_file, format: " which folds to: ");
763 print_gimple_stmt (dump_file, gsi_stmt (i: gsi), 0, TDF_SLIM);
764 }
765 }
766 update_stmt (s: gsi_stmt (i: gsi));
767}
768
769/* Optimize CALL, a call to a built-in function with lhs LHS, on the
770 basis that INFO describes all uses of LHS. */
771
772void
773backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
774{
775 /* If we have an f such that -f(x) = f(-x), and if the sign of the result
776 doesn't matter, strip any sign operations from the input. */
777 if (info->flags.ignore_sign
778 && negate_mathfn_p (gimple_call_combined_fn (call)))
779 {
780 tree new_arg = strip_sign_op (rhs: gimple_call_arg (gs: call, index: 0));
781 if (new_arg)
782 {
783 prepare_change (var: lhs);
784 gimple_call_set_arg (gs: call, index: 0, arg: new_arg);
785 complete_change (stmt: call);
786 }
787 }
788}
789
790/* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
791 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */
792
793void
794backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
795 tree rhs2, tree rhs3)
796{
797 if (!rhs1 && !rhs2 && !rhs3)
798 return;
799
800 prepare_change (var: lhs);
801 if (rhs1)
802 gimple_assign_set_rhs1 (gs: assign, rhs: rhs1);
803 if (rhs2)
804 gimple_assign_set_rhs2 (gs: assign, rhs: rhs2);
805 if (rhs3)
806 gimple_assign_set_rhs3 (gs: assign, rhs: rhs3);
807 complete_change (stmt: assign);
808}
809
810/* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
811 describes all uses of LHS. */
812
813void
814backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
815{
816 switch (gimple_assign_rhs_code (gs: assign))
817 {
818 case MULT_EXPR:
819 case RDIV_EXPR:
820 /* If the sign of the result doesn't matter, strip sign operations
821 from both inputs. */
822 if (info->flags.ignore_sign)
823 replace_assign_rhs (assign, lhs,
824 rhs1: strip_sign_op (rhs: gimple_assign_rhs1 (gs: assign)),
825 rhs2: strip_sign_op (rhs: gimple_assign_rhs2 (gs: assign)),
826 NULL_TREE);
827 break;
828
829 case COND_EXPR:
830 /* If the sign of A ? B : C doesn't matter, strip sign operations
831 from both B and C. */
832 if (info->flags.ignore_sign)
833 replace_assign_rhs (assign, lhs,
834 NULL_TREE,
835 rhs2: strip_sign_op (rhs: gimple_assign_rhs2 (gs: assign)),
836 rhs3: strip_sign_op (rhs: gimple_assign_rhs3 (gs: assign)));
837 break;
838
839 default:
840 break;
841 }
842}
843
844/* Optimize PHI, which defines VAR, on the basis that INFO describes all
845 uses of the result. */
846
847void
848backprop::optimize_phi (gphi *phi, tree var, const usage_info *info)
849{
850 /* If the sign of the result doesn't matter, try to strip sign operations
851 from arguments. */
852 if (info->flags.ignore_sign)
853 {
854 basic_block bb = gimple_bb (g: phi);
855 use_operand_p use;
856 ssa_op_iter oi;
857 bool replaced = false;
858 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
859 {
860 /* Propagating along abnormal edges is delicate, punt for now. */
861 const int index = PHI_ARG_INDEX_FROM_USE (use);
862 if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL)
863 continue;
864
865 tree new_arg = strip_sign_op (USE_FROM_PTR (use));
866 if (new_arg)
867 {
868 if (!replaced)
869 prepare_change (var);
870 if (dump_file && (dump_flags & TDF_DETAILS))
871 note_replacement (stmt: phi, USE_FROM_PTR (use), new_rhs: new_arg);
872 replace_exp (use, new_arg);
873 replaced = true;
874 }
875 }
876 }
877}
878
879void
880backprop::execute ()
881{
882 /* Phase 1: Traverse the function, making optimistic assumptions
883 about any phi whose definition we haven't seen. */
884 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
885 unsigned int postorder_num = post_order_compute (postorder, false, false);
886 for (unsigned int i = 0; i < postorder_num; ++i)
887 {
888 process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
889 bitmap_set_bit (map: m_visited_blocks, bitno: postorder[i]);
890 }
891 XDELETEVEC (postorder);
892
893 /* Phase 2: Use the initial (perhaps overly optimistic) information
894 to create a maximal fixed point solution. */
895 while (!m_worklist.is_empty ())
896 process_var (var: pop_from_worklist ());
897
898 if (dump_file && (dump_flags & TDF_DETAILS))
899 fprintf (stream: dump_file, format: "\n");
900
901 /* Phase 3: Do a reverse post-order walk, using information about
902 the uses of SSA names to optimize their definitions. */
903 for (unsigned int i = m_vars.length (); i-- > 0;)
904 {
905 usage_info *info = m_vars[i].second;
906 if (info->is_useful ())
907 {
908 tree var = m_vars[i].first;
909 gimple *stmt = SSA_NAME_DEF_STMT (var);
910 if (gcall *call = dyn_cast <gcall *> (p: stmt))
911 optimize_builtin_call (call, lhs: var, info);
912 else if (gassign *assign = dyn_cast <gassign *> (p: stmt))
913 optimize_assign (assign, lhs: var, info);
914 else if (gphi *phi = dyn_cast <gphi *> (p: stmt))
915 optimize_phi (phi, var, info);
916 }
917 }
918
919 /* Phase 4: Do a post-order walk, deleting statements that are no
920 longer needed. */
921 for (unsigned int i = 0; i < m_vars.length (); ++i)
922 {
923 tree var = m_vars[i].first;
924 if (has_zero_uses (var))
925 remove_unused_var (var);
926 }
927
928 if (dump_file && (dump_flags & TDF_DETAILS))
929 fprintf (stream: dump_file, format: "\n");
930}
931
932const pass_data pass_data_backprop =
933{
934 .type: GIMPLE_PASS, /* type */
935 .name: "backprop", /* name */
936 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
937 .tv_id: TV_TREE_BACKPROP, /* tv_id */
938 .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
939 .properties_provided: 0, /* properties_provided */
940 .properties_destroyed: 0, /* properties_destroyed */
941 .todo_flags_start: 0, /* todo_flags_start */
942 .todo_flags_finish: 0, /* todo_flags_finish */
943};
944
945class pass_backprop : public gimple_opt_pass
946{
947public:
948 pass_backprop (gcc::context *ctxt)
949 : gimple_opt_pass (pass_data_backprop, ctxt)
950 {}
951
952 /* opt_pass methods: */
953 opt_pass * clone () final override { return new pass_backprop (m_ctxt); }
954 bool gate (function *) final override { return flag_ssa_backprop; }
955 unsigned int execute (function *) final override;
956
957}; // class pass_backprop
958
959unsigned int
960pass_backprop::execute (function *fn)
961{
962 backprop (fn).execute ();
963 return 0;
964}
965
966} // anon namespace
967
968gimple_opt_pass *
969make_pass_backprop (gcc::context *ctxt)
970{
971 return new pass_backprop (ctxt);
972}
973

source code of gcc/gimple-ssa-backprop.cc