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 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
)
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. */
290 backprop::lookup_operand (tree op
)
292 if (op
&& TREE_CODE (op
) == SSA_NAME
)
294 usage_info
**slot
= m_info_map
.get (op
);
301 /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */
304 backprop::push_to_worklist (tree var
)
306 if (!bitmap_set_bit (m_worklist_names
, SSA_NAME_VERSION (var
)))
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
);
313 fprintf (dump_file
, "\n");
317 /* Remove and return the next SSA name from the worklist. The worklist
318 is known to be nonempty. */
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
);
329 fprintf (dump_file
, "\n");
334 /* Make INFO describe all uses of RHS in CALL, which is a call to a
335 built-in function. */
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
);
352 /* The signs of all inputs are ignored. */
353 info
->flags
.ignore_sign
= true;
357 CASE_CFN_COPYSIGN_FN
:
358 /* The sign of the first input is ignored. */
359 if (rhs
!= gimple_call_arg (call
, 1))
360 info
->flags
.ignore_sign
= true;
365 /* The sign of the first input is ignored as long as the second
366 input is an even real. */
367 tree power
= gimple_call_arg (call
, 1);
369 if (TREE_CODE (power
) == REAL_CST
370 && real_isinteger (&TREE_REAL_CST (power
), &n
)
372 info
->flags
.ignore_sign
= true;
381 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
383 if (gimple_call_arg (call
, 0) == rhs
384 && gimple_call_arg (call
, 1) == rhs
385 && gimple_call_arg (call
, 2) != rhs
)
386 info
->flags
.ignore_sign
= true;
390 if (negate_mathfn_p (fn
))
392 /* The sign of the (single) input doesn't matter provided
393 that the sign of the output doesn't matter. */
394 const usage_info
*lhs_info
= lookup_operand (lhs
);
396 info
->flags
.ignore_sign
= lhs_info
->flags
.ignore_sign
;
402 /* Make INFO describe all uses of RHS in ASSIGN. */
405 backprop::process_assign_use (gassign
*assign
, tree rhs
, usage_info
*info
)
407 tree lhs
= gimple_assign_lhs (assign
);
408 switch (gimple_assign_rhs_code (assign
))
411 /* The sign of the input doesn't matter. */
412 info
->flags
.ignore_sign
= true;
416 /* For A = B ? C : D, propagate information about all uses of A
418 if (rhs
!= gimple_assign_rhs1 (assign
))
420 const usage_info
*lhs_info
= lookup_operand (lhs
);
427 /* In X * X, the sign of X doesn't matter. */
428 if (gimple_assign_rhs1 (assign
) == rhs
429 && gimple_assign_rhs2 (assign
) == rhs
)
430 info
->flags
.ignore_sign
= true;
435 /* If the sign of the result doesn't matter, the sign of the inputs
436 doesn't matter either. */
437 if (FLOAT_TYPE_P (TREE_TYPE (rhs
)))
439 const usage_info
*lhs_info
= lookup_operand (lhs
);
441 info
->flags
.ignore_sign
= lhs_info
->flags
.ignore_sign
;
450 /* Make INFO describe the uses of PHI's result. */
453 backprop::process_phi_use (gphi
*phi
, usage_info
*info
)
455 tree result
= gimple_phi_result (phi
);
456 if (const usage_info
*result_info
= lookup_operand (result
))
457 *info
= *result_info
;
460 /* Make INFO describe all uses of RHS in STMT. */
463 backprop::process_use (gimple
*stmt
, tree rhs
, usage_info
*info
)
465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
467 fprintf (dump_file
, "[USE] ");
468 print_generic_expr (dump_file
, rhs
);
469 fprintf (dump_file
, " in ");
470 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
473 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
474 process_builtin_call_use (call
, rhs
, info
);
475 else if (gassign
*assign
= dyn_cast
<gassign
*> (stmt
))
476 process_assign_use (assign
, rhs
, info
);
477 else if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
478 process_phi_use (phi
, info
);
480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
481 dump_usage_info (dump_file
, rhs
, info
);
484 /* Make INFO describe all uses of VAR, returning true if the result
485 is useful. If the uses include phis that haven't been processed yet,
486 make the most optimistic assumption possible, so that we aim for
487 a maximum rather than a minimum fixed point. */
490 backprop::intersect_uses (tree var
, usage_info
*info
)
492 imm_use_iterator iter
;
494 *info
= usage_info::intersection_identity ();
495 FOR_EACH_IMM_USE_STMT (stmt
, iter
, var
)
497 if (is_gimple_debug (stmt
))
499 if (is_a
<gphi
*> (stmt
)
500 && !bitmap_bit_p (m_visited_blocks
, gimple_bb (stmt
)->index
))
502 /* Skip unprocessed phis. */
503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
505 fprintf (dump_file
, "[BACKEDGE] ");
506 print_generic_expr (dump_file
, var
);
507 fprintf (dump_file
, " in ");
508 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
514 process_use (stmt
, var
, &subinfo
);
516 if (!info
->is_useful ())
518 BREAK_FROM_IMM_USE_STMT (iter
);
526 /* Queue for reconsideration any input of STMT that has information
527 associated with it. This is used if that information might be
531 backprop::reprocess_inputs (gimple
*stmt
)
535 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, oi
, SSA_OP_USE
)
537 tree var
= get_use_from_ptr (use_p
);
538 if (lookup_operand (var
))
539 push_to_worklist (var
);
543 /* Say that we're recording INFO for SSA name VAR, or that we're deleting
544 existing information if INFO is null. INTRO describes the change. */
547 dump_var_info (tree var
, usage_info
*info
, const char *intro
)
549 fprintf (dump_file
, "[DEF] %s for ", intro
);
550 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (var
), 0, TDF_SLIM
);
552 dump_usage_info (dump_file
, var
, info
);
555 /* Process all uses of VAR and record or update the result in
556 M_INFO_MAP and M_VARS. */
559 backprop::process_var (tree var
)
561 if (has_zero_uses (var
))
565 intersect_uses (var
, &info
);
567 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
568 if (info
.is_useful ())
571 usage_info
*&map_info
= m_info_map
.get_or_insert (var
, &existed
);
574 /* Recording information about VAR for the first time. */
575 map_info
= m_info_pool
.allocate ();
577 m_vars
.safe_push (var_info_pair (var
, map_info
));
578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
579 dump_var_info (var
, map_info
, "Recording new information");
581 /* If STMT is a phi, reprocess any backedge uses. This is a
582 no-op for other uses, which won't have any information
583 associated with them. */
584 if (is_a
<gphi
*> (stmt
))
585 reprocess_inputs (stmt
);
587 else if (info
!= *map_info
)
589 /* Recording information that is less optimistic than before. */
590 gcc_checking_assert ((info
& *map_info
) == info
);
592 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
593 dump_var_info (var
, map_info
, "Updating information");
594 reprocess_inputs (stmt
);
599 if (usage_info
**slot
= m_info_map
.get (var
))
601 /* Removing previously-recorded information. */
603 m_info_map
.remove (var
);
604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
605 dump_var_info (var
, NULL
, "Deleting information");
606 reprocess_inputs (stmt
);
610 /* If STMT is a phi, remove any information recorded for
612 if (is_a
<gphi
*> (stmt
))
613 reprocess_inputs (stmt
);
618 /* Process all statements and phis in BB, during the first post-order walk. */
621 backprop::process_block (basic_block bb
)
623 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
626 tree lhs
= gimple_get_lhs (gsi_stmt (gsi
));
627 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
630 for (gphi_iterator gpi
= gsi_start_phis (bb
); !gsi_end_p (gpi
);
632 process_var (gimple_phi_result (gpi
.phi ()));
635 /* Delete the definition of VAR, which has no uses. */
638 remove_unused_var (tree var
)
640 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 fprintf (dump_file
, "Deleting ");
644 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
646 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
647 gsi_remove (&gsi
, true);
651 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */
654 note_replacement (gimple
*stmt
, tree old_rhs
, tree new_rhs
)
656 fprintf (dump_file
, "Replacing use of ");
657 print_generic_expr (dump_file
, old_rhs
);
658 fprintf (dump_file
, " with ");
659 print_generic_expr (dump_file
, new_rhs
);
660 fprintf (dump_file
, " in ");
661 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
664 /* If RHS is an SSA name whose definition just changes the sign of a value,
665 return that other value, otherwise return null. */
668 strip_sign_op_1 (tree rhs
)
670 if (TREE_CODE (rhs
) != SSA_NAME
)
673 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
);
674 if (gassign
*assign
= dyn_cast
<gassign
*> (def_stmt
))
675 switch (gimple_assign_rhs_code (assign
))
679 return gimple_assign_rhs1 (assign
);
684 else if (gcall
*call
= dyn_cast
<gcall
*> (def_stmt
))
685 switch (gimple_call_combined_fn (call
))
688 CASE_CFN_COPYSIGN_FN
:
689 return gimple_call_arg (call
, 0);
698 /* If RHS is an SSA name whose definition just changes the sign of a value,
699 strip all such operations and return the ultimate input to them.
700 Return null otherwise.
702 Although this could in principle lead to quadratic searching,
703 in practice a long sequence of sign manipulations should already
704 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
705 for more than one operation in order to catch cases like -abs(x). */
708 strip_sign_op (tree rhs
)
710 tree new_rhs
= strip_sign_op_1 (rhs
);
713 while (tree next
= strip_sign_op_1 (new_rhs
))
718 /* Start a change in the value of VAR that is suitable for all non-debug
719 uses of VAR. We need to make sure that debug statements continue to
720 use the original definition of VAR where possible, or are nullified
724 backprop::prepare_change (tree var
)
726 if (MAY_HAVE_DEBUG_BIND_STMTS
)
727 insert_debug_temp_for_var_def (NULL
, var
);
728 reset_flow_sensitive_info (var
);
731 /* STMT has been changed. Give the fold machinery a chance to simplify
732 and canonicalize it (e.g. by ensuring that commutative operands have
733 the right order), then record the updates. */
736 backprop::complete_change (gimple
*stmt
)
738 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
739 if (fold_stmt (&gsi
))
741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
743 fprintf (dump_file
, " which folds to: ");
744 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, TDF_SLIM
);
747 update_stmt (gsi_stmt (gsi
));
750 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
751 basis that INFO describes all uses of LHS. */
754 backprop::optimize_builtin_call (gcall
*call
, tree lhs
, const usage_info
*info
)
756 /* If we have an f such that -f(x) = f(-x), and if the sign of the result
757 doesn't matter, strip any sign operations from the input. */
758 if (info
->flags
.ignore_sign
759 && negate_mathfn_p (gimple_call_combined_fn (call
)))
761 tree new_arg
= strip_sign_op (gimple_call_arg (call
, 0));
764 prepare_change (lhs
);
765 gimple_call_set_arg (call
, 0, new_arg
);
766 complete_change (call
);
771 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
772 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */
775 backprop::replace_assign_rhs (gassign
*assign
, tree lhs
, tree rhs1
,
776 tree rhs2
, tree rhs3
)
778 if (!rhs1
&& !rhs2
&& !rhs3
)
781 prepare_change (lhs
);
783 gimple_assign_set_rhs1 (assign
, rhs1
);
785 gimple_assign_set_rhs2 (assign
, rhs2
);
787 gimple_assign_set_rhs3 (assign
, rhs3
);
788 complete_change (assign
);
791 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
792 describes all uses of LHS. */
795 backprop::optimize_assign (gassign
*assign
, tree lhs
, const usage_info
*info
)
797 switch (gimple_assign_rhs_code (assign
))
801 /* If the sign of the result doesn't matter, strip sign operations
803 if (info
->flags
.ignore_sign
)
804 replace_assign_rhs (assign
, lhs
,
805 strip_sign_op (gimple_assign_rhs1 (assign
)),
806 strip_sign_op (gimple_assign_rhs2 (assign
)),
811 /* If the sign of A ? B : C doesn't matter, strip sign operations
812 from both B and C. */
813 if (info
->flags
.ignore_sign
)
814 replace_assign_rhs (assign
, lhs
,
816 strip_sign_op (gimple_assign_rhs2 (assign
)),
817 strip_sign_op (gimple_assign_rhs3 (assign
)));
825 /* Optimize PHI, which defines VAR, on the basis that INFO describes all
826 uses of the result. */
829 backprop::optimize_phi (gphi
*phi
, tree var
, const usage_info
*info
)
831 /* If the sign of the result doesn't matter, try to strip sign operations
833 if (info
->flags
.ignore_sign
)
835 basic_block bb
= gimple_bb (phi
);
838 bool replaced
= false;
839 FOR_EACH_PHI_ARG (use
, phi
, oi
, SSA_OP_USE
)
841 /* Propagating along abnormal edges is delicate, punt for now. */
842 const int index
= PHI_ARG_INDEX_FROM_USE (use
);
843 if (EDGE_PRED (bb
, index
)->flags
& EDGE_ABNORMAL
)
846 tree new_arg
= strip_sign_op (USE_FROM_PTR (use
));
850 prepare_change (var
);
851 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
852 note_replacement (phi
, USE_FROM_PTR (use
), new_arg
);
853 replace_exp (use
, new_arg
);
863 /* Phase 1: Traverse the function, making optimistic assumptions
864 about any phi whose definition we haven't seen. */
865 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (m_fn
));
866 unsigned int postorder_num
= post_order_compute (postorder
, false, false);
867 for (unsigned int i
= 0; i
< postorder_num
; ++i
)
869 process_block (BASIC_BLOCK_FOR_FN (m_fn
, postorder
[i
]));
870 bitmap_set_bit (m_visited_blocks
, postorder
[i
]);
872 XDELETEVEC (postorder
);
874 /* Phase 2: Use the initial (perhaps overly optimistic) information
875 to create a maximal fixed point solution. */
876 while (!m_worklist
.is_empty ())
877 process_var (pop_from_worklist ());
879 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
880 fprintf (dump_file
, "\n");
882 /* Phase 3: Do a reverse post-order walk, using information about
883 the uses of SSA names to optimize their definitions. */
884 for (unsigned int i
= m_vars
.length (); i
-- > 0;)
886 usage_info
*info
= m_vars
[i
].second
;
887 if (info
->is_useful ())
889 tree var
= m_vars
[i
].first
;
890 gimple
*stmt
= SSA_NAME_DEF_STMT (var
);
891 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
892 optimize_builtin_call (call
, var
, info
);
893 else if (gassign
*assign
= dyn_cast
<gassign
*> (stmt
))
894 optimize_assign (assign
, var
, info
);
895 else if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
896 optimize_phi (phi
, var
, info
);
900 /* Phase 4: Do a post-order walk, deleting statements that are no
902 for (unsigned int i
= 0; i
< m_vars
.length (); ++i
)
904 tree var
= m_vars
[i
].first
;
905 if (has_zero_uses (var
))
906 remove_unused_var (var
);
909 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
910 fprintf (dump_file
, "\n");
913 const pass_data pass_data_backprop
=
915 GIMPLE_PASS
, /* type */
916 "backprop", /* name */
917 OPTGROUP_NONE
, /* optinfo_flags */
918 TV_TREE_BACKPROP
, /* tv_id */
919 ( PROP_cfg
| PROP_ssa
), /* properties_required */
920 0, /* properties_provided */
921 0, /* properties_destroyed */
922 0, /* todo_flags_start */
923 0, /* todo_flags_finish */
926 class pass_backprop
: public gimple_opt_pass
929 pass_backprop (gcc::context
*ctxt
)
930 : gimple_opt_pass (pass_data_backprop
, ctxt
)
933 /* opt_pass methods: */
934 opt_pass
* clone () { return new pass_backprop (m_ctxt
); }
935 virtual bool gate (function
*) { return flag_ssa_backprop
; }
936 virtual unsigned int execute (function
*);
938 }; // class pass_backprop
941 pass_backprop::execute (function
*fn
)
943 backprop (fn
).execute ();
950 make_pass_backprop (gcc::context
*ctxt
)
952 return new pass_backprop (ctxt
);