Daily bump.
[official-gcc.git] / gcc / gimple-ssa-backprop.c
blob3acf3d604eabac75b5dfbd951ff64074ece4bdfc
1 /* Back-propagation of usage information to definitions.
2 Copyright (C) 2015-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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.
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.
31 For example, take the function:
33 double
34 f (double *a, int n, double start)
36 double x = fabs (start);
37 for (int i = 0; i < n; ++i)
38 x *= a[i];
39 return __builtin_cos (x);
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.
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.
51 The algorithm is:
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.
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.)
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.
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.)
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.)
84 Note that this pass does not deal with direct redundancies,
85 such as cos(-x)->cos(x). match.pd handles those cases instead. */
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"
107 namespace {
109 /* Information about a group of uses of an SSA name. */
110 struct usage_info
112 usage_info () : flag_word (0) {}
113 usage_info &operator &= (const usage_info &);
114 usage_info operator & (const usage_info &) const;
115 bool operator == (const usage_info &) const;
116 bool operator != (const usage_info &) const;
117 bool is_useful () const;
119 static usage_info intersection_identity ();
121 union
123 struct
125 /* True if the uses treat x and -x in the same way. */
126 unsigned int ignore_sign : 1;
127 } flags;
128 /* All the flag bits as a single int. */
129 unsigned int flag_word;
133 /* Return an X such that X & Y == Y for all Y. This is the most
134 optimistic assumption possible. */
136 usage_info
137 usage_info::intersection_identity ()
139 usage_info ret;
140 ret.flag_word = -1;
141 return ret;
144 /* Intersect *THIS with OTHER, so that *THIS describes all uses covered
145 by the original *THIS and OTHER. */
147 usage_info &
148 usage_info::operator &= (const usage_info &other)
150 flag_word &= other.flag_word;
151 return *this;
154 /* Return the intersection of *THIS and OTHER, i.e. a structure that
155 describes all uses covered by *THIS and OTHER. */
157 usage_info
158 usage_info::operator & (const usage_info &other) const
160 usage_info info (*this);
161 info &= other;
162 return info;
165 bool
166 usage_info::operator == (const usage_info &other) const
168 return flag_word == other.flag_word;
171 bool
172 usage_info::operator != (const usage_info &other) const
174 return !operator == (other);
177 /* Return true if *THIS is not simply the default, safe assumption. */
179 bool
180 usage_info::is_useful () const
182 return flag_word != 0;
185 /* Start a dump line about SSA name VAR. */
187 static void
188 dump_usage_prefix (FILE *file, tree var)
190 fprintf (file, " ");
191 print_generic_expr (file, var, 0);
192 fprintf (file, ": ");
195 /* Print INFO to FILE. */
197 static void
198 dump_usage_info (FILE *file, tree var, usage_info *info)
200 if (info->flags.ignore_sign)
202 dump_usage_prefix (file, var);
203 fprintf (file, "sign bit not important\n");
207 /* Represents one execution of the pass. */
208 class backprop
210 public:
211 backprop (function *);
212 ~backprop ();
214 void execute ();
216 private:
217 const usage_info *lookup_operand (tree);
219 void push_to_worklist (tree);
220 tree pop_from_worklist ();
222 void process_builtin_call_use (gcall *, tree, usage_info *);
223 void process_assign_use (gassign *, tree, usage_info *);
224 void process_phi_use (gphi *, usage_info *);
225 void process_use (gimple *, tree, usage_info *);
226 bool intersect_uses (tree, usage_info *);
227 void reprocess_inputs (gimple *);
228 void process_var (tree);
229 void process_block (basic_block);
231 void prepare_change (tree);
232 void complete_change (gimple *);
233 void optimize_builtin_call (gcall *, tree, const usage_info *);
234 void replace_assign_rhs (gassign *, tree, tree, tree, tree);
235 void optimize_assign (gassign *, tree, const usage_info *);
236 void optimize_phi (gphi *, tree, const usage_info *);
238 typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type;
239 typedef std::pair <tree, usage_info *> var_info_pair;
241 /* The function we're optimizing. */
242 function *m_fn;
244 /* Pool for allocating usage_info structures. */
245 object_allocator <usage_info> m_info_pool;
247 /* Maps an SSA name to a description of all uses of that SSA name.
248 All the usage_infos satisfy is_useful.
250 We use a hash_map because the map is expected to be sparse
251 (i.e. most SSA names won't have useful information attached to them).
252 We could move to a directly-indexed array if that situation changes. */
253 info_map_type m_info_map;
255 /* Post-ordered list of all potentially-interesting SSA names,
256 along with information that describes all uses. */
257 auto_vec <var_info_pair, 128> m_vars;
259 /* A bitmap of blocks that we have finished processing in the initial
260 post-order walk. */
261 auto_sbitmap m_visited_blocks;
263 /* A worklist of SSA names whose definitions need to be reconsidered. */
264 auto_vec <tree, 64> m_worklist;
266 /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION.
267 We use a bitmap rather than an sbitmap because most SSA names are
268 never added to the worklist. */
269 bitmap m_worklist_names;
272 backprop::backprop (function *fn)
273 : m_fn (fn),
274 m_info_pool ("usage_info"),
275 m_visited_blocks (last_basic_block_for_fn (m_fn)),
276 m_worklist_names (BITMAP_ALLOC (NULL))
278 bitmap_clear (m_visited_blocks);
281 backprop::~backprop ()
283 BITMAP_FREE (m_worklist_names);
284 m_info_pool.release ();
287 /* Return usage information for general operand OP, or null if none. */
289 const usage_info *
290 backprop::lookup_operand (tree op)
292 if (op && TREE_CODE (op) == SSA_NAME)
294 usage_info **slot = m_info_map.get (op);
295 if (slot)
296 return *slot;
298 return NULL;
301 /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */
303 void
304 backprop::push_to_worklist (tree var)
306 if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var)))
307 return;
308 m_worklist.safe_push (var);
309 if (dump_file && (dump_flags & TDF_DETAILS))
311 fprintf (dump_file, "[WORKLIST] Pushing ");
312 print_generic_expr (dump_file, var, 0);
313 fprintf (dump_file, "\n");
317 /* Remove and return the next SSA name from the worklist. The worklist
318 is known to be nonempty. */
320 tree
321 backprop::pop_from_worklist ()
323 tree var = m_worklist.pop ();
324 bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var));
325 if (dump_file && (dump_flags & TDF_DETAILS))
327 fprintf (dump_file, "[WORKLIST] Popping ");
328 print_generic_expr (dump_file, var, 0);
329 fprintf (dump_file, "\n");
331 return var;
334 /* Make INFO describe all uses of RHS in CALL, which is a call to a
335 built-in function. */
337 void
338 backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
340 combined_fn fn = gimple_call_combined_fn (call);
341 tree lhs = gimple_call_lhs (call);
342 switch (fn)
344 case CFN_LAST:
345 break;
347 CASE_CFN_COS:
348 CASE_CFN_COSH:
349 CASE_CFN_CCOS:
350 CASE_CFN_CCOSH:
351 CASE_CFN_HYPOT:
352 /* The signs of all inputs are ignored. */
353 info->flags.ignore_sign = true;
354 break;
356 CASE_CFN_COPYSIGN:
357 /* The sign of the first input is ignored. */
358 if (rhs != gimple_call_arg (call, 1))
359 info->flags.ignore_sign = true;
360 break;
362 CASE_CFN_POW:
364 /* The sign of the first input is ignored as long as the second
365 input is an even real. */
366 tree power = gimple_call_arg (call, 1);
367 HOST_WIDE_INT n;
368 if (TREE_CODE (power) == REAL_CST
369 && real_isinteger (&TREE_REAL_CST (power), &n)
370 && (n & 1) == 0)
371 info->flags.ignore_sign = true;
372 break;
375 CASE_CFN_FMA:
376 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
377 matter. */
378 if (gimple_call_arg (call, 0) == rhs
379 && gimple_call_arg (call, 1) == rhs
380 && gimple_call_arg (call, 2) != rhs)
381 info->flags.ignore_sign = true;
382 break;
384 default:
385 if (negate_mathfn_p (fn))
387 /* The sign of the (single) input doesn't matter provided
388 that the sign of the output doesn't matter. */
389 const usage_info *lhs_info = lookup_operand (lhs);
390 if (lhs_info)
391 info->flags.ignore_sign = lhs_info->flags.ignore_sign;
393 break;
397 /* Make INFO describe all uses of RHS in ASSIGN. */
399 void
400 backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
402 tree lhs = gimple_assign_lhs (assign);
403 switch (gimple_assign_rhs_code (assign))
405 case ABS_EXPR:
406 /* The sign of the input doesn't matter. */
407 info->flags.ignore_sign = true;
408 break;
410 case COND_EXPR:
411 /* For A = B ? C : D, propagate information about all uses of A
412 to C and D. */
413 if (rhs != gimple_assign_rhs1 (assign))
415 const usage_info *lhs_info = lookup_operand (lhs);
416 if (lhs_info)
417 *info = *lhs_info;
419 break;
421 case FMA_EXPR:
422 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
423 matter. */
424 if (gimple_assign_rhs1 (assign) == rhs
425 && gimple_assign_rhs2 (assign) == rhs
426 && gimple_assign_rhs3 (assign) != rhs)
427 info->flags.ignore_sign = true;
428 break;
430 case MULT_EXPR:
431 /* In X * X, the sign of X doesn't matter. */
432 if (gimple_assign_rhs1 (assign) == rhs
433 && gimple_assign_rhs2 (assign) == rhs)
434 info->flags.ignore_sign = true;
435 /* Fall through. */
437 case NEGATE_EXPR:
438 case RDIV_EXPR:
439 /* If the sign of the result doesn't matter, the sign of the inputs
440 doesn't matter either. */
441 if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
443 const usage_info *lhs_info = lookup_operand (lhs);
444 if (lhs_info)
445 info->flags.ignore_sign = lhs_info->flags.ignore_sign;
447 break;
449 default:
450 break;
454 /* Make INFO describe the uses of PHI's result. */
456 void
457 backprop::process_phi_use (gphi *phi, usage_info *info)
459 tree result = gimple_phi_result (phi);
460 if (const usage_info *result_info = lookup_operand (result))
461 *info = *result_info;
464 /* Make INFO describe all uses of RHS in STMT. */
466 void
467 backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
469 if (dump_file && (dump_flags & TDF_DETAILS))
471 fprintf (dump_file, "[USE] ");
472 print_generic_expr (dump_file, rhs, 0);
473 fprintf (dump_file, " in ");
474 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
477 if (gcall *call = dyn_cast <gcall *> (stmt))
478 process_builtin_call_use (call, rhs, info);
479 else if (gassign *assign = dyn_cast <gassign *> (stmt))
480 process_assign_use (assign, rhs, info);
481 else if (gphi *phi = dyn_cast <gphi *> (stmt))
482 process_phi_use (phi, info);
484 if (dump_file && (dump_flags & TDF_DETAILS))
485 dump_usage_info (dump_file, rhs, info);
488 /* Make INFO describe all uses of VAR, returning true if the result
489 is useful. If the uses include phis that haven't been processed yet,
490 make the most optimistic assumption possible, so that we aim for
491 a maximum rather than a minimum fixed point. */
493 bool
494 backprop::intersect_uses (tree var, usage_info *info)
496 imm_use_iterator iter;
497 gimple *stmt;
498 *info = usage_info::intersection_identity ();
499 FOR_EACH_IMM_USE_STMT (stmt, iter, var)
501 if (is_gimple_debug (stmt))
502 continue;
503 if (is_a <gphi *> (stmt)
504 && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))
506 /* Skip unprocessed phis. */
507 if (dump_file && (dump_flags & TDF_DETAILS))
509 fprintf (dump_file, "[BACKEDGE] ");
510 print_generic_expr (dump_file, var, 0);
511 fprintf (dump_file, " in ");
512 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
515 else
517 usage_info subinfo;
518 process_use (stmt, var, &subinfo);
519 *info &= subinfo;
520 if (!info->is_useful ())
522 BREAK_FROM_IMM_USE_STMT (iter);
523 return false;
527 return true;
530 /* Queue for reconsideration any input of STMT that has information
531 associated with it. This is used if that information might be
532 too optimistic. */
534 void
535 backprop::reprocess_inputs (gimple *stmt)
537 use_operand_p use_p;
538 ssa_op_iter oi;
539 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
541 tree var = get_use_from_ptr (use_p);
542 if (lookup_operand (var))
543 push_to_worklist (var);
547 /* Say that we're recording INFO for SSA name VAR, or that we're deleting
548 existing information if INFO is null. INTRO describes the change. */
550 static void
551 dump_var_info (tree var, usage_info *info, const char *intro)
553 fprintf (dump_file, "[DEF] %s for ", intro);
554 print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
555 if (info)
556 dump_usage_info (dump_file, var, info);
559 /* Process all uses of VAR and record or update the result in
560 M_INFO_MAP and M_VARS. */
562 void
563 backprop::process_var (tree var)
565 if (has_zero_uses (var))
566 return;
568 usage_info info;
569 intersect_uses (var, &info);
571 gimple *stmt = SSA_NAME_DEF_STMT (var);
572 if (info.is_useful ())
574 bool existed;
575 usage_info *&map_info = m_info_map.get_or_insert (var, &existed);
576 if (!existed)
578 /* Recording information about VAR for the first time. */
579 map_info = m_info_pool.allocate ();
580 *map_info = info;
581 m_vars.safe_push (var_info_pair (var, map_info));
582 if (dump_file && (dump_flags & TDF_DETAILS))
583 dump_var_info (var, map_info, "Recording new information");
585 /* If STMT is a phi, reprocess any backedge uses. This is a
586 no-op for other uses, which won't have any information
587 associated with them. */
588 if (is_a <gphi *> (stmt))
589 reprocess_inputs (stmt);
591 else if (info != *map_info)
593 /* Recording information that is less optimistic than before. */
594 gcc_checking_assert ((info & *map_info) == info);
595 *map_info = info;
596 if (dump_file && (dump_flags & TDF_DETAILS))
597 dump_var_info (var, map_info, "Updating information");
598 reprocess_inputs (stmt);
601 else
603 if (usage_info **slot = m_info_map.get (var))
605 /* Removing previously-recorded information. */
606 **slot = info;
607 m_info_map.remove (var);
608 if (dump_file && (dump_flags & TDF_DETAILS))
609 dump_var_info (var, NULL, "Deleting information");
610 reprocess_inputs (stmt);
612 else
614 /* If STMT is a phi, remove any information recorded for
615 its arguments. */
616 if (is_a <gphi *> (stmt))
617 reprocess_inputs (stmt);
622 /* Process all statements and phis in BB, during the first post-order walk. */
624 void
625 backprop::process_block (basic_block bb)
627 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
628 gsi_prev (&gsi))
630 tree lhs = gimple_get_lhs (gsi_stmt (gsi));
631 if (lhs && TREE_CODE (lhs) == SSA_NAME)
632 process_var (lhs);
634 for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
635 gsi_next (&gpi))
636 process_var (gimple_phi_result (gpi.phi ()));
639 /* Delete the definition of VAR, which has no uses. */
641 static void
642 remove_unused_var (tree var)
644 gimple *stmt = SSA_NAME_DEF_STMT (var);
645 if (dump_file && (dump_flags & TDF_DETAILS))
647 fprintf (dump_file, "Deleting ");
648 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
650 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
651 gsi_remove (&gsi, true);
652 release_defs (stmt);
655 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */
657 static void
658 note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
660 fprintf (dump_file, "Replacing use of ");
661 print_generic_expr (dump_file, old_rhs, 0);
662 fprintf (dump_file, " with ");
663 print_generic_expr (dump_file, new_rhs, 0);
664 fprintf (dump_file, " in ");
665 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
668 /* If RHS is an SSA name whose definition just changes the sign of a value,
669 return that other value, otherwise return null. */
671 static tree
672 strip_sign_op_1 (tree rhs)
674 if (TREE_CODE (rhs) != SSA_NAME)
675 return NULL_TREE;
677 gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
678 if (gassign *assign = dyn_cast <gassign *> (def_stmt))
679 switch (gimple_assign_rhs_code (assign))
681 case ABS_EXPR:
682 case NEGATE_EXPR:
683 return gimple_assign_rhs1 (assign);
685 default:
686 break;
688 else if (gcall *call = dyn_cast <gcall *> (def_stmt))
689 switch (gimple_call_combined_fn (call))
691 CASE_CFN_COPYSIGN:
692 return gimple_call_arg (call, 0);
694 default:
695 break;
698 return NULL_TREE;
701 /* If RHS is an SSA name whose definition just changes the sign of a value,
702 strip all such operations and return the ultimate input to them.
703 Return null otherwise.
705 Although this could in principle lead to quadratic searching,
706 in practice a long sequence of sign manipulations should already
707 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
708 for more than one operation in order to catch cases like -abs(x). */
710 static tree
711 strip_sign_op (tree rhs)
713 tree new_rhs = strip_sign_op_1 (rhs);
714 if (!new_rhs)
715 return NULL_TREE;
716 while (tree next = strip_sign_op_1 (new_rhs))
717 new_rhs = next;
718 return new_rhs;
721 /* Start a change in the value of VAR that is suitable for all non-debug
722 uses of VAR. We need to make sure that debug statements continue to
723 use the original definition of VAR where possible, or are nullified
724 otherwise. */
726 void
727 backprop::prepare_change (tree var)
729 if (MAY_HAVE_DEBUG_STMTS)
730 insert_debug_temp_for_var_def (NULL, var);
731 reset_flow_sensitive_info (var);
734 /* STMT has been changed. Give the fold machinery a chance to simplify
735 and canonicalize it (e.g. by ensuring that commutative operands have
736 the right order), then record the updates. */
738 void
739 backprop::complete_change (gimple *stmt)
741 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
742 if (fold_stmt (&gsi))
744 if (dump_file && (dump_flags & TDF_DETAILS))
746 fprintf (dump_file, " which folds to: ");
747 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
750 update_stmt (gsi_stmt (gsi));
753 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
754 basis that INFO describes all uses of LHS. */
756 void
757 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
759 /* If we have an f such that -f(x) = f(-x), and if the sign of the result
760 doesn't matter, strip any sign operations from the input. */
761 if (info->flags.ignore_sign
762 && negate_mathfn_p (gimple_call_combined_fn (call)))
764 tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
765 if (new_arg)
767 prepare_change (lhs);
768 gimple_call_set_arg (call, 0, new_arg);
769 complete_change (call);
774 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
775 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */
777 void
778 backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
779 tree rhs2, tree rhs3)
781 if (!rhs1 && !rhs2 && !rhs3)
782 return;
784 prepare_change (lhs);
785 if (rhs1)
786 gimple_assign_set_rhs1 (assign, rhs1);
787 if (rhs2)
788 gimple_assign_set_rhs2 (assign, rhs2);
789 if (rhs3)
790 gimple_assign_set_rhs3 (assign, rhs3);
791 complete_change (assign);
794 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
795 describes all uses of LHS. */
797 void
798 backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
800 switch (gimple_assign_rhs_code (assign))
802 case MULT_EXPR:
803 case RDIV_EXPR:
804 /* If the sign of the result doesn't matter, strip sign operations
805 from both inputs. */
806 if (info->flags.ignore_sign)
807 replace_assign_rhs (assign, lhs,
808 strip_sign_op (gimple_assign_rhs1 (assign)),
809 strip_sign_op (gimple_assign_rhs2 (assign)),
810 NULL_TREE);
811 break;
813 case COND_EXPR:
814 /* If the sign of A ? B : C doesn't matter, strip sign operations
815 from both B and C. */
816 if (info->flags.ignore_sign)
817 replace_assign_rhs (assign, lhs,
818 NULL_TREE,
819 strip_sign_op (gimple_assign_rhs2 (assign)),
820 strip_sign_op (gimple_assign_rhs3 (assign)));
821 break;
823 default:
824 break;
828 /* Optimize PHI, which defines VAR, on the basis that INFO describes all
829 uses of the result. */
831 void
832 backprop::optimize_phi (gphi *phi, tree var, const usage_info *info)
834 /* If the sign of the result doesn't matter, try to strip sign operations
835 from arguments. */
836 if (info->flags.ignore_sign)
838 basic_block bb = gimple_bb (phi);
839 use_operand_p use;
840 ssa_op_iter oi;
841 bool replaced = false;
842 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
844 /* Propagating along abnormal edges is delicate, punt for now. */
845 const int index = PHI_ARG_INDEX_FROM_USE (use);
846 if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL)
847 continue;
849 tree new_arg = strip_sign_op (USE_FROM_PTR (use));
850 if (new_arg)
852 if (!replaced)
853 prepare_change (var);
854 if (dump_file && (dump_flags & TDF_DETAILS))
855 note_replacement (phi, USE_FROM_PTR (use), new_arg);
856 replace_exp (use, new_arg);
857 replaced = true;
863 void
864 backprop::execute ()
866 /* Phase 1: Traverse the function, making optimistic assumptions
867 about any phi whose definition we haven't seen. */
868 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
869 unsigned int postorder_num = post_order_compute (postorder, false, false);
870 for (unsigned int i = 0; i < postorder_num; ++i)
872 process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
873 bitmap_set_bit (m_visited_blocks, postorder[i]);
875 XDELETEVEC (postorder);
877 /* Phase 2: Use the initial (perhaps overly optimistic) information
878 to create a maximal fixed point solution. */
879 while (!m_worklist.is_empty ())
880 process_var (pop_from_worklist ());
882 if (dump_file && (dump_flags & TDF_DETAILS))
883 fprintf (dump_file, "\n");
885 /* Phase 3: Do a reverse post-order walk, using information about
886 the uses of SSA names to optimize their definitions. */
887 for (unsigned int i = m_vars.length (); i-- > 0;)
889 usage_info *info = m_vars[i].second;
890 if (info->is_useful ())
892 tree var = m_vars[i].first;
893 gimple *stmt = SSA_NAME_DEF_STMT (var);
894 if (gcall *call = dyn_cast <gcall *> (stmt))
895 optimize_builtin_call (call, var, info);
896 else if (gassign *assign = dyn_cast <gassign *> (stmt))
897 optimize_assign (assign, var, info);
898 else if (gphi *phi = dyn_cast <gphi *> (stmt))
899 optimize_phi (phi, var, info);
903 /* Phase 4: Do a post-order walk, deleting statements that are no
904 longer needed. */
905 for (unsigned int i = 0; i < m_vars.length (); ++i)
907 tree var = m_vars[i].first;
908 if (has_zero_uses (var))
909 remove_unused_var (var);
912 if (dump_file && (dump_flags & TDF_DETAILS))
913 fprintf (dump_file, "\n");
916 const pass_data pass_data_backprop =
918 GIMPLE_PASS, /* type */
919 "backprop", /* name */
920 OPTGROUP_NONE, /* optinfo_flags */
921 TV_TREE_BACKPROP, /* tv_id */
922 ( PROP_cfg | PROP_ssa ), /* properties_required */
923 0, /* properties_provided */
924 0, /* properties_destroyed */
925 0, /* todo_flags_start */
926 0, /* todo_flags_finish */
929 class pass_backprop : public gimple_opt_pass
931 public:
932 pass_backprop (gcc::context *ctxt)
933 : gimple_opt_pass (pass_data_backprop, ctxt)
936 /* opt_pass methods: */
937 opt_pass * clone () { return new pass_backprop (m_ctxt); }
938 virtual bool gate (function *) { return flag_ssa_backprop; }
939 virtual unsigned int execute (function *);
941 }; // class pass_backprop
943 unsigned int
944 pass_backprop::execute (function *fn)
946 backprop (fn).execute ();
947 return 0;
950 } // anon namespace
952 gimple_opt_pass *
953 make_pass_backprop (gcc::context *ctxt)
955 return new pass_backprop (ctxt);