1 /* Back-propagation of usage information to definitions.
2 Copyright (C) 2015-2018 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)
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
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:
34 f (double *a, int n, double start)
36 double x = fabs (start);
37 for (int i = 0; i < n; ++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.
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
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. */
89 #include "coretypes.h"
93 #include "gimple-iterator.h"
95 #include "fold-const.h"
96 #include "tree-pass.h"
98 #include "gimple-pretty-print.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"
109 /* Information about a group of uses of an SSA name. */
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 ();
125 /* True if the uses treat x and -x in the same way. */
126 unsigned int ignore_sign
: 1;
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. */
137 usage_info::intersection_identity ()
144 /* Intersect *THIS with OTHER, so that *THIS describes all uses covered
145 by the original *THIS and OTHER. */
148 usage_info::operator &= (const usage_info
&other
)
150 flag_word
&= other
.flag_word
;
154 /* Return the intersection of *THIS and OTHER, i.e. a structure that
155 describes all uses covered by *THIS and OTHER. */
158 usage_info::operator & (const usage_info
&other
) const
160 usage_info
info (*this);
166 usage_info::operator == (const usage_info
&other
) const
168 return flag_word
== other
.flag_word
;
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. */
180 usage_info::is_useful () const
182 return flag_word
!= 0;
185 /* Start a dump line about SSA name VAR. */
188 dump_usage_prefix (FILE *file
, tree var
)
191 print_generic_expr (file
, var
);
192 fprintf (file
, ": ");
195 /* Print INFO to FILE. */
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. */
211 backprop (function
*);
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. */
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
261 auto_sbitmap m_visited_blocks
;
263 /* A bitmap of phis that we have finished processing in the initial
264 post-order walk, excluding those from blocks mentioned in
266 auto_bitmap m_visited_phis
;
268 /* A worklist of SSA names whose definitions need to be reconsidered. */
269 auto_vec
<tree
, 64> m_worklist
;
271 /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION.
272 We use a bitmap rather than an sbitmap because most SSA names are
273 never added to the worklist. */
274 bitmap m_worklist_names
;
277 backprop::backprop (function
*fn
)
279 m_info_pool ("usage_info"),
280 m_visited_blocks (last_basic_block_for_fn (m_fn
)),
281 m_worklist_names (BITMAP_ALLOC (NULL
))
283 bitmap_clear (m_visited_blocks
);
286 backprop::~backprop ()
288 BITMAP_FREE (m_worklist_names
);
289 m_info_pool
.release ();
292 /* Return usage information for general operand OP, or null if none. */
295 backprop::lookup_operand (tree op
)
297 if (op
&& TREE_CODE (op
) == SSA_NAME
)
299 usage_info
**slot
= m_info_map
.get (op
);
306 /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */
309 backprop::push_to_worklist (tree var
)
311 if (!bitmap_set_bit (m_worklist_names
, SSA_NAME_VERSION (var
)))
313 m_worklist
.safe_push (var
);
314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
316 fprintf (dump_file
, "[WORKLIST] Pushing ");
317 print_generic_expr (dump_file
, var
);
318 fprintf (dump_file
, "\n");
322 /* Remove and return the next SSA name from the worklist. The worklist
323 is known to be nonempty. */
326 backprop::pop_from_worklist ()
328 tree var
= m_worklist
.pop ();
329 bitmap_clear_bit (m_worklist_names
, SSA_NAME_VERSION (var
));
330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
332 fprintf (dump_file
, "[WORKLIST] Popping ");
333 print_generic_expr (dump_file
, var
);
334 fprintf (dump_file
, "\n");
339 /* Make INFO describe all uses of RHS in CALL, which is a call to a
340 built-in function. */
343 backprop::process_builtin_call_use (gcall
*call
, tree rhs
, usage_info
*info
)
345 combined_fn fn
= gimple_call_combined_fn (call
);
346 tree lhs
= gimple_call_lhs (call
);
357 /* The signs of all inputs are ignored. */
358 info
->flags
.ignore_sign
= true;
362 CASE_CFN_COPYSIGN_FN
:
363 /* The sign of the first input is ignored. */
364 if (rhs
!= gimple_call_arg (call
, 1))
365 info
->flags
.ignore_sign
= true;
370 /* The sign of the first input is ignored as long as the second
371 input is an even real. */
372 tree power
= gimple_call_arg (call
, 1);
374 if (TREE_CODE (power
) == REAL_CST
375 && real_isinteger (&TREE_REAL_CST (power
), &n
)
377 info
->flags
.ignore_sign
= true;
386 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
388 if (gimple_call_arg (call
, 0) == rhs
389 && gimple_call_arg (call
, 1) == rhs
390 && gimple_call_arg (call
, 2) != rhs
)
391 info
->flags
.ignore_sign
= true;
395 if (negate_mathfn_p (fn
))
397 /* The sign of the (single) input doesn't matter provided
398 that the sign of the output doesn't matter. */
399 const usage_info
*lhs_info
= lookup_operand (lhs
);
401 info
->flags
.ignore_sign
= lhs_info
->flags
.ignore_sign
;
407 /* Make INFO describe all uses of RHS in ASSIGN. */
410 backprop::process_assign_use (gassign
*assign
, tree rhs
, usage_info
*info
)
412 tree lhs
= gimple_assign_lhs (assign
);
413 switch (gimple_assign_rhs_code (assign
))
416 /* The sign of the input doesn't matter. */
417 info
->flags
.ignore_sign
= true;
421 /* For A = B ? C : D, propagate information about all uses of A
423 if (rhs
!= gimple_assign_rhs1 (assign
))
425 const usage_info
*lhs_info
= lookup_operand (lhs
);
432 /* In X * X, the sign of X doesn't matter. */
433 if (gimple_assign_rhs1 (assign
) == rhs
434 && gimple_assign_rhs2 (assign
) == rhs
)
435 info
->flags
.ignore_sign
= true;
440 /* If the sign of the result doesn't matter, the sign of the inputs
441 doesn't matter either. */
442 if (FLOAT_TYPE_P (TREE_TYPE (rhs
)))
444 const usage_info
*lhs_info
= lookup_operand (lhs
);
446 info
->flags
.ignore_sign
= lhs_info
->flags
.ignore_sign
;
455 /* Make INFO describe the uses of PHI's result. */
458 backprop::process_phi_use (gphi
*phi
, usage_info
*info
)
460 tree result
= gimple_phi_result (phi
);
461 if (const usage_info
*result_info
= lookup_operand (result
))
462 *info
= *result_info
;
465 /* Make INFO describe all uses of RHS in STMT. */
468 backprop::process_use (gimple
*stmt
, tree rhs
, usage_info
*info
)
470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
472 fprintf (dump_file
, "[USE] ");
473 print_generic_expr (dump_file
, rhs
);
474 fprintf (dump_file
, " in ");
475 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
478 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
479 process_builtin_call_use (call
, rhs
, info
);
480 else if (gassign
*assign
= dyn_cast
<gassign
*> (stmt
))
481 process_assign_use (assign
, rhs
, info
);
482 else if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
483 process_phi_use (phi
, info
);
485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
486 dump_usage_info (dump_file
, rhs
, info
);
489 /* Make INFO describe all uses of VAR, returning true if the result
490 is useful. If the uses include phis that haven't been processed yet,
491 make the most optimistic assumption possible, so that we aim for
492 a maximum rather than a minimum fixed point. */
495 backprop::intersect_uses (tree var
, usage_info
*info
)
497 imm_use_iterator iter
;
499 *info
= usage_info::intersection_identity ();
500 FOR_EACH_IMM_USE_STMT (stmt
, iter
, var
)
502 if (is_gimple_debug (stmt
))
504 gphi
*phi
= dyn_cast
<gphi
*> (stmt
);
506 && !bitmap_bit_p (m_visited_blocks
, gimple_bb (phi
)->index
)
507 && !bitmap_bit_p (m_visited_phis
,
508 SSA_NAME_VERSION (gimple_phi_result (phi
))))
510 /* Skip unprocessed phis. */
511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
513 fprintf (dump_file
, "[BACKEDGE] ");
514 print_generic_expr (dump_file
, var
);
515 fprintf (dump_file
, " in ");
516 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
522 process_use (stmt
, var
, &subinfo
);
524 if (!info
->is_useful ())
526 BREAK_FROM_IMM_USE_STMT (iter
);
534 /* Queue for reconsideration any input of STMT that has information
535 associated with it. This is used if that information might be
539 backprop::reprocess_inputs (gimple
*stmt
)
543 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
545 tree var
= get_use_from_ptr (use_p
);
546 if (lookup_operand (var
))
547 push_to_worklist (var
);
551 /* Say that we're recording INFO for SSA name VAR, or that we're deleting
552 existing information if INFO is null. INTRO describes the change. */
555 dump_var_info (tree var
, usage_info
*info
, const char *intro
)
557 fprintf (dump_file
, "[DEF] %s for ", intro
);
558 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (var
), 0, TDF_SLIM
);
560 dump_usage_info (dump_file
, var
, info
);
563 /* Process all uses of VAR and record or update the result in
564 M_INFO_MAP and M_VARS. */
567 backprop::process_var (tree var
)
569 if (has_zero_uses (var
))
573 intersect_uses (var
, &info
);
575 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
576 if (info
.is_useful ())
579 usage_info
*&map_info
= m_info_map
.get_or_insert (var
, &existed
);
582 /* Recording information about VAR for the first time. */
583 map_info
= m_info_pool
.allocate ();
585 m_vars
.safe_push (var_info_pair (var
, map_info
));
586 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
587 dump_var_info (var
, map_info
, "Recording new information");
589 /* If STMT is a phi, reprocess any backedge uses. This is a
590 no-op for other uses, which won't have any information
591 associated with them. */
592 if (is_a
<gphi
*> (stmt
))
593 reprocess_inputs (stmt
);
595 else if (info
!= *map_info
)
597 /* Recording information that is less optimistic than before. */
598 gcc_checking_assert ((info
& *map_info
) == info
);
600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
601 dump_var_info (var
, map_info
, "Updating information");
602 reprocess_inputs (stmt
);
607 if (usage_info
**slot
= m_info_map
.get (var
))
609 /* Removing previously-recorded information. */
611 m_info_map
.remove (var
);
612 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
613 dump_var_info (var
, NULL
, "Deleting information");
614 reprocess_inputs (stmt
);
618 /* If STMT is a phi, remove any information recorded for
620 if (is_a
<gphi
*> (stmt
))
621 reprocess_inputs (stmt
);
626 /* Process all statements and phis in BB, during the first post-order walk. */
629 backprop::process_block (basic_block bb
)
631 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
634 tree lhs
= gimple_get_lhs (gsi_stmt (gsi
));
635 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
638 for (gphi_iterator gpi
= gsi_start_phis (bb
); !gsi_end_p (gpi
);
641 tree result
= gimple_phi_result (gpi
.phi ());
642 process_var (result
);
643 bitmap_set_bit (m_visited_phis
, SSA_NAME_VERSION (result
));
645 bitmap_clear (m_visited_phis
);
648 /* Delete the definition of VAR, which has no uses. */
651 remove_unused_var (tree var
)
653 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
656 fprintf (dump_file
, "Deleting ");
657 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
659 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
660 gsi_remove (&gsi
, true);
664 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */
667 note_replacement (gimple
*stmt
, tree old_rhs
, tree new_rhs
)
669 fprintf (dump_file
, "Replacing use of ");
670 print_generic_expr (dump_file
, old_rhs
);
671 fprintf (dump_file
, " with ");
672 print_generic_expr (dump_file
, new_rhs
);
673 fprintf (dump_file
, " in ");
674 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
677 /* If RHS is an SSA name whose definition just changes the sign of a value,
678 return that other value, otherwise return null. */
681 strip_sign_op_1 (tree rhs
)
683 if (TREE_CODE (rhs
) != SSA_NAME
)
686 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
);
687 if (gassign
*assign
= dyn_cast
<gassign
*> (def_stmt
))
688 switch (gimple_assign_rhs_code (assign
))
692 return gimple_assign_rhs1 (assign
);
697 else if (gcall
*call
= dyn_cast
<gcall
*> (def_stmt
))
698 switch (gimple_call_combined_fn (call
))
701 CASE_CFN_COPYSIGN_FN
:
702 return gimple_call_arg (call
, 0);
711 /* If RHS is an SSA name whose definition just changes the sign of a value,
712 strip all such operations and return the ultimate input to them.
713 Return null otherwise.
715 Although this could in principle lead to quadratic searching,
716 in practice a long sequence of sign manipulations should already
717 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
718 for more than one operation in order to catch cases like -abs(x). */
721 strip_sign_op (tree rhs
)
723 tree new_rhs
= strip_sign_op_1 (rhs
);
726 while (tree next
= strip_sign_op_1 (new_rhs
))
731 /* Start a change in the value of VAR that is suitable for all non-debug
732 uses of VAR. We need to make sure that debug statements continue to
733 use the original definition of VAR where possible, or are nullified
737 backprop::prepare_change (tree var
)
739 if (MAY_HAVE_DEBUG_BIND_STMTS
)
740 insert_debug_temp_for_var_def (NULL
, var
);
741 reset_flow_sensitive_info (var
);
744 /* STMT has been changed. Give the fold machinery a chance to simplify
745 and canonicalize it (e.g. by ensuring that commutative operands have
746 the right order), then record the updates. */
749 backprop::complete_change (gimple
*stmt
)
751 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
752 if (fold_stmt (&gsi
))
754 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
756 fprintf (dump_file
, " which folds to: ");
757 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, TDF_SLIM
);
760 update_stmt (gsi_stmt (gsi
));
763 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
764 basis that INFO describes all uses of LHS. */
767 backprop::optimize_builtin_call (gcall
*call
, tree lhs
, const usage_info
*info
)
769 /* If we have an f such that -f(x) = f(-x), and if the sign of the result
770 doesn't matter, strip any sign operations from the input. */
771 if (info
->flags
.ignore_sign
772 && negate_mathfn_p (gimple_call_combined_fn (call
)))
774 tree new_arg
= strip_sign_op (gimple_call_arg (call
, 0));
777 prepare_change (lhs
);
778 gimple_call_set_arg (call
, 0, new_arg
);
779 complete_change (call
);
784 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
785 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */
788 backprop::replace_assign_rhs (gassign
*assign
, tree lhs
, tree rhs1
,
789 tree rhs2
, tree rhs3
)
791 if (!rhs1
&& !rhs2
&& !rhs3
)
794 prepare_change (lhs
);
796 gimple_assign_set_rhs1 (assign
, rhs1
);
798 gimple_assign_set_rhs2 (assign
, rhs2
);
800 gimple_assign_set_rhs3 (assign
, rhs3
);
801 complete_change (assign
);
804 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
805 describes all uses of LHS. */
808 backprop::optimize_assign (gassign
*assign
, tree lhs
, const usage_info
*info
)
810 switch (gimple_assign_rhs_code (assign
))
814 /* If the sign of the result doesn't matter, strip sign operations
816 if (info
->flags
.ignore_sign
)
817 replace_assign_rhs (assign
, lhs
,
818 strip_sign_op (gimple_assign_rhs1 (assign
)),
819 strip_sign_op (gimple_assign_rhs2 (assign
)),
824 /* If the sign of A ? B : C doesn't matter, strip sign operations
825 from both B and C. */
826 if (info
->flags
.ignore_sign
)
827 replace_assign_rhs (assign
, lhs
,
829 strip_sign_op (gimple_assign_rhs2 (assign
)),
830 strip_sign_op (gimple_assign_rhs3 (assign
)));
838 /* Optimize PHI, which defines VAR, on the basis that INFO describes all
839 uses of the result. */
842 backprop::optimize_phi (gphi
*phi
, tree var
, const usage_info
*info
)
844 /* If the sign of the result doesn't matter, try to strip sign operations
846 if (info
->flags
.ignore_sign
)
848 basic_block bb
= gimple_bb (phi
);
851 bool replaced
= false;
852 FOR_EACH_PHI_ARG (use
, phi
, oi
, SSA_OP_USE
)
854 /* Propagating along abnormal edges is delicate, punt for now. */
855 const int index
= PHI_ARG_INDEX_FROM_USE (use
);
856 if (EDGE_PRED (bb
, index
)->flags
& EDGE_ABNORMAL
)
859 tree new_arg
= strip_sign_op (USE_FROM_PTR (use
));
863 prepare_change (var
);
864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
865 note_replacement (phi
, USE_FROM_PTR (use
), new_arg
);
866 replace_exp (use
, new_arg
);
876 /* Phase 1: Traverse the function, making optimistic assumptions
877 about any phi whose definition we haven't seen. */
878 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (m_fn
));
879 unsigned int postorder_num
= post_order_compute (postorder
, false, false);
880 for (unsigned int i
= 0; i
< postorder_num
; ++i
)
882 process_block (BASIC_BLOCK_FOR_FN (m_fn
, postorder
[i
]));
883 bitmap_set_bit (m_visited_blocks
, postorder
[i
]);
885 XDELETEVEC (postorder
);
887 /* Phase 2: Use the initial (perhaps overly optimistic) information
888 to create a maximal fixed point solution. */
889 while (!m_worklist
.is_empty ())
890 process_var (pop_from_worklist ());
892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
893 fprintf (dump_file
, "\n");
895 /* Phase 3: Do a reverse post-order walk, using information about
896 the uses of SSA names to optimize their definitions. */
897 for (unsigned int i
= m_vars
.length (); i
-- > 0;)
899 usage_info
*info
= m_vars
[i
].second
;
900 if (info
->is_useful ())
902 tree var
= m_vars
[i
].first
;
903 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
904 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
905 optimize_builtin_call (call
, var
, info
);
906 else if (gassign
*assign
= dyn_cast
<gassign
*> (stmt
))
907 optimize_assign (assign
, var
, info
);
908 else if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
909 optimize_phi (phi
, var
, info
);
913 /* Phase 4: Do a post-order walk, deleting statements that are no
915 for (unsigned int i
= 0; i
< m_vars
.length (); ++i
)
917 tree var
= m_vars
[i
].first
;
918 if (has_zero_uses (var
))
919 remove_unused_var (var
);
922 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
923 fprintf (dump_file
, "\n");
926 const pass_data pass_data_backprop
=
928 GIMPLE_PASS
, /* type */
929 "backprop", /* name */
930 OPTGROUP_NONE
, /* optinfo_flags */
931 TV_TREE_BACKPROP
, /* tv_id */
932 ( PROP_cfg
| PROP_ssa
), /* properties_required */
933 0, /* properties_provided */
934 0, /* properties_destroyed */
935 0, /* todo_flags_start */
936 0, /* todo_flags_finish */
939 class pass_backprop
: public gimple_opt_pass
942 pass_backprop (gcc::context
*ctxt
)
943 : gimple_opt_pass (pass_data_backprop
, ctxt
)
946 /* opt_pass methods: */
947 opt_pass
* clone () { return new pass_backprop (m_ctxt
); }
948 virtual bool gate (function
*) { return flag_ssa_backprop
; }
949 virtual unsigned int execute (function
*);
951 }; // class pass_backprop
954 pass_backprop::execute (function
*fn
)
956 backprop (fn
).execute ();
963 make_pass_backprop (gcc::context
*ctxt
)
965 return new pass_backprop (ctxt
);