1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2022 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
33 #include "gimple-fold.h"
35 #include "tree-inline.h"
36 #include "gimple-iterator.h"
38 #include "tree-into-ssa.h"
40 #include "tree-ssa-propagate.h"
41 #include "tree-ssa-threadupdate.h"
42 #include "tree-ssa-scopedtables.h"
43 #include "tree-ssa-threadedge.h"
44 #include "tree-ssa-dom.h"
46 #include "tree-cfgcleanup.h"
48 #include "alloc-pool.h"
50 #include "vr-values.h"
51 #include "gimple-ssa-evrp-analyze.h"
54 /* This file implements optimizations on the dominator tree. */
56 /* Structure for recording edge equivalences.
58 Computing and storing the edge equivalences instead of creating
59 them on-demand can save significant amounts of time, particularly
60 for pathological cases involving switch statements.
62 These structures live for a single iteration of the dominator
63 optimizer in the edge's AUX field. At the end of an iteration we
64 free each of these structures. */
68 typedef std::pair
<tree
, tree
> equiv_pair
;
72 /* Record a simple LHS = RHS equivalence. This may trigger
73 calls to derive_equivalences. */
74 void record_simple_equiv (tree
, tree
);
76 /* If traversing this edge creates simple equivalences, we store
77 them as LHS/RHS pairs within this vector. */
78 vec
<equiv_pair
> simple_equivalences
;
80 /* Traversing an edge may also indicate one or more particular conditions
82 vec
<cond_equivalence
> cond_equivalences
;
85 /* Derive equivalences by walking the use-def chains. */
86 void derive_equivalences (tree
, tree
, int);
89 /* Track whether or not we have changed the control flow graph. */
90 static bool cfg_altered
;
92 /* Bitmap of blocks that have had EH statements cleaned. We should
93 remove their dead edges eventually. */
94 static bitmap need_eh_cleanup
;
95 static vec
<gimple
*> need_noreturn_fixup
;
97 /* Statistics for dominator optimizations. */
101 long num_exprs_considered
;
107 static struct opt_stats_d opt_stats
;
109 /* Local functions. */
110 static void record_equality (tree
, tree
, class const_and_copies
*);
111 static void record_equivalences_from_phis (basic_block
);
112 static void record_equivalences_from_incoming_edge (basic_block
,
113 class const_and_copies
*,
114 class avail_exprs_stack
*);
115 static void eliminate_redundant_computations (gimple_stmt_iterator
*,
116 class const_and_copies
*,
117 class avail_exprs_stack
*);
118 static void record_equivalences_from_stmt (gimple
*, int,
119 class avail_exprs_stack
*);
120 static void dump_dominator_optimization_stats (FILE *file
,
121 hash_table
<expr_elt_hasher
> *);
123 /* Constructor for EDGE_INFO. An EDGE_INFO instance is always
124 associated with an edge E. */
126 edge_info::edge_info (edge e
)
128 /* Free the old one associated with E, if it exists and
129 associate our new object with E. */
130 free_dom_edge_info (e
);
133 /* And initialize the embedded vectors. */
134 simple_equivalences
= vNULL
;
135 cond_equivalences
= vNULL
;
138 /* Destructor just needs to release the vectors. */
140 edge_info::~edge_info (void)
142 this->cond_equivalences
.release ();
143 this->simple_equivalences
.release ();
146 /* NAME is known to have the value VALUE, which must be a constant.
148 Walk through its use-def chain to see if there are other equivalences
149 we might be able to derive.
151 RECURSION_LIMIT controls how far back we recurse through the use-def
155 edge_info::derive_equivalences (tree name
, tree value
, int recursion_limit
)
157 if (TREE_CODE (name
) != SSA_NAME
|| TREE_CODE (value
) != INTEGER_CST
)
160 /* This records the equivalence for the toplevel object. Do
161 this before checking the recursion limit. */
162 simple_equivalences
.safe_push (equiv_pair (name
, value
));
164 /* Limit how far up the use-def chains we are willing to walk. */
165 if (recursion_limit
== 0)
168 /* We can walk up the use-def chains to potentially find more
170 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
171 if (is_gimple_assign (def_stmt
))
173 enum tree_code code
= gimple_assign_rhs_code (def_stmt
);
176 /* If the result of an OR is zero, then its operands are, too. */
178 if (integer_zerop (value
))
180 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
181 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
183 value
= build_zero_cst (TREE_TYPE (rhs1
));
184 derive_equivalences (rhs1
, value
, recursion_limit
- 1);
185 value
= build_zero_cst (TREE_TYPE (rhs2
));
186 derive_equivalences (rhs2
, value
, recursion_limit
- 1);
190 /* If the result of an AND is nonzero, then its operands are, too. */
192 if (!integer_zerop (value
))
194 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
195 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
197 /* If either operand has a boolean range, then we
198 know its value must be one, otherwise we just know it
199 is nonzero. The former is clearly useful, I haven't
200 seen cases where the latter is helpful yet. */
201 if (TREE_CODE (rhs1
) == SSA_NAME
)
203 if (ssa_name_has_boolean_range (rhs1
))
205 value
= build_one_cst (TREE_TYPE (rhs1
));
206 derive_equivalences (rhs1
, value
, recursion_limit
- 1);
209 if (TREE_CODE (rhs2
) == SSA_NAME
)
211 if (ssa_name_has_boolean_range (rhs2
))
213 value
= build_one_cst (TREE_TYPE (rhs2
));
214 derive_equivalences (rhs2
, value
, recursion_limit
- 1);
220 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
221 set via a widening type conversion, then we may be able to record
222 additional equivalences. */
225 tree rhs
= gimple_assign_rhs1 (def_stmt
);
226 tree rhs_type
= TREE_TYPE (rhs
);
227 if (INTEGRAL_TYPE_P (rhs_type
)
228 && (TYPE_PRECISION (TREE_TYPE (name
))
229 >= TYPE_PRECISION (rhs_type
))
230 && int_fits_type_p (value
, rhs_type
))
231 derive_equivalences (rhs
,
232 fold_convert (rhs_type
, value
),
233 recursion_limit
- 1);
237 /* We can invert the operation of these codes trivially if
238 one of the RHS operands is a constant to produce a known
239 value for the other RHS operand. */
240 case POINTER_PLUS_EXPR
:
243 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
244 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
246 /* If either argument is a constant, then we can compute
247 a constant value for the nonconstant argument. */
248 if (TREE_CODE (rhs1
) == INTEGER_CST
249 && TREE_CODE (rhs2
) == SSA_NAME
)
250 derive_equivalences (rhs2
,
251 fold_binary (MINUS_EXPR
, TREE_TYPE (rhs1
),
253 recursion_limit
- 1);
254 else if (TREE_CODE (rhs2
) == INTEGER_CST
255 && TREE_CODE (rhs1
) == SSA_NAME
)
256 derive_equivalences (rhs1
,
257 fold_binary (MINUS_EXPR
, TREE_TYPE (rhs1
),
259 recursion_limit
- 1);
263 /* If one of the operands is a constant, then we can compute
264 the value of the other operand. If both operands are
265 SSA_NAMEs, then they must be equal if the result is zero. */
268 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
269 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
271 /* If either argument is a constant, then we can compute
272 a constant value for the nonconstant argument. */
273 if (TREE_CODE (rhs1
) == INTEGER_CST
274 && TREE_CODE (rhs2
) == SSA_NAME
)
275 derive_equivalences (rhs2
,
276 fold_binary (MINUS_EXPR
, TREE_TYPE (rhs1
),
278 recursion_limit
- 1);
279 else if (TREE_CODE (rhs2
) == INTEGER_CST
280 && TREE_CODE (rhs1
) == SSA_NAME
)
281 derive_equivalences (rhs1
,
282 fold_binary (PLUS_EXPR
, TREE_TYPE (rhs1
),
284 recursion_limit
- 1);
285 else if (integer_zerop (value
))
287 tree cond
= build2 (EQ_EXPR
, boolean_type_node
,
288 gimple_assign_rhs1 (def_stmt
),
289 gimple_assign_rhs2 (def_stmt
));
290 tree inverted
= invert_truthvalue (cond
);
291 record_conditions (&this->cond_equivalences
, cond
, inverted
);
299 if ((code
== EQ_EXPR
&& integer_onep (value
))
300 || (code
== NE_EXPR
&& integer_zerop (value
)))
302 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
303 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
305 /* If either argument is a constant, then record the
306 other argument as being the same as that constant.
308 If neither operand is a constant, then we have a
309 conditional name == name equivalence. */
310 if (TREE_CODE (rhs1
) == INTEGER_CST
)
311 derive_equivalences (rhs2
, rhs1
, recursion_limit
- 1);
312 else if (TREE_CODE (rhs2
) == INTEGER_CST
)
313 derive_equivalences (rhs1
, rhs2
, recursion_limit
- 1);
317 tree cond
= build2 (code
, boolean_type_node
,
318 gimple_assign_rhs1 (def_stmt
),
319 gimple_assign_rhs2 (def_stmt
));
320 tree inverted
= invert_truthvalue (cond
);
321 if (integer_zerop (value
))
322 std::swap (cond
, inverted
);
323 record_conditions (&this->cond_equivalences
, cond
, inverted
);
328 /* For BIT_NOT and NEGATE, we can just apply the operation to the
329 VALUE to get the new equivalence. It will always be a constant
330 so we can recurse. */
334 tree rhs
= gimple_assign_rhs1 (def_stmt
);
336 /* If this is a NOT and the operand has a boolean range, then we
337 know its value must be zero or one. We are not supposed to
338 have a BIT_NOT_EXPR for boolean types with precision > 1 in
339 the general case, see e.g. the handling of TRUTH_NOT_EXPR in
340 the gimplifier, but it can be generated by match.pd out of
341 a BIT_XOR_EXPR wrapped in a BIT_AND_EXPR. Now the handling
342 of BIT_AND_EXPR above already forces a specific semantics for
343 boolean types with precision > 1 so we must do the same here,
344 otherwise we could change the semantics of TRUTH_NOT_EXPR for
345 boolean types with precision > 1. */
346 if (code
== BIT_NOT_EXPR
347 && TREE_CODE (rhs
) == SSA_NAME
348 && ssa_name_has_boolean_range (rhs
))
350 if ((TREE_INT_CST_LOW (value
) & 1) == 0)
351 res
= build_one_cst (TREE_TYPE (rhs
));
353 res
= build_zero_cst (TREE_TYPE (rhs
));
356 res
= fold_build1 (code
, TREE_TYPE (rhs
), value
);
357 derive_equivalences (rhs
, res
, recursion_limit
- 1);
363 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
365 tree cond
= build2 (code
, boolean_type_node
,
366 gimple_assign_rhs1 (def_stmt
),
367 gimple_assign_rhs2 (def_stmt
));
368 tree inverted
= invert_truthvalue (cond
);
369 if (integer_zerop (value
))
370 std::swap (cond
, inverted
);
371 record_conditions (&this->cond_equivalences
, cond
, inverted
);
381 edge_info::record_simple_equiv (tree lhs
, tree rhs
)
383 /* If the RHS is a constant, then we may be able to derive
384 further equivalences. Else just record the name = name
386 if (TREE_CODE (rhs
) == INTEGER_CST
)
387 derive_equivalences (lhs
, rhs
, 4);
389 simple_equivalences
.safe_push (equiv_pair (lhs
, rhs
));
392 /* Free the edge_info data attached to E, if it exists. */
395 free_dom_edge_info (edge e
)
397 class edge_info
*edge_info
= (class edge_info
*)e
->aux
;
403 /* Free all EDGE_INFO structures associated with edges in the CFG.
404 If a particular edge can be threaded, copy the redirection
405 target from the EDGE_INFO structure into the edge's AUX field
406 as required by code to update the CFG and SSA graph for
410 free_all_edge_infos (void)
416 FOR_EACH_BB_FN (bb
, cfun
)
418 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
420 free_dom_edge_info (e
);
426 /* We have finished optimizing BB, record any information implied by
427 taking a specific outgoing edge from BB. */
430 record_edge_info (basic_block bb
)
432 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
433 class edge_info
*edge_info
;
435 if (! gsi_end_p (gsi
))
437 gimple
*stmt
= gsi_stmt (gsi
);
438 location_t loc
= gimple_location (stmt
);
440 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
442 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
443 tree index
= gimple_switch_index (switch_stmt
);
445 if (TREE_CODE (index
) == SSA_NAME
)
448 int n_labels
= gimple_switch_num_labels (switch_stmt
);
449 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
453 for (i
= 0; i
< n_labels
; i
++)
455 tree label
= gimple_switch_label (switch_stmt
, i
);
456 basic_block target_bb
457 = label_to_block (cfun
, CASE_LABEL (label
));
458 if (CASE_HIGH (label
)
460 || info
[target_bb
->index
])
461 info
[target_bb
->index
] = error_mark_node
;
463 info
[target_bb
->index
] = label
;
466 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
468 basic_block target_bb
= e
->dest
;
469 tree label
= info
[target_bb
->index
];
471 if (label
!= NULL
&& label
!= error_mark_node
)
473 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
475 edge_info
= new class edge_info (e
);
476 edge_info
->record_simple_equiv (index
, x
);
483 /* A COND_EXPR may create equivalences too. */
484 if (gimple_code (stmt
) == GIMPLE_COND
)
489 tree op0
= gimple_cond_lhs (stmt
);
490 tree op1
= gimple_cond_rhs (stmt
);
491 enum tree_code code
= gimple_cond_code (stmt
);
493 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
495 /* Special case comparing booleans against a constant as we
496 know the value of OP0 on both arms of the branch. i.e., we
497 can record an equivalence for OP0 rather than COND.
499 However, don't do this if the constant isn't zero or one.
500 Such conditionals will get optimized more thoroughly during
502 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
503 && TREE_CODE (op0
) == SSA_NAME
504 && ssa_name_has_boolean_range (op0
)
505 && is_gimple_min_invariant (op1
)
506 && (integer_zerop (op1
) || integer_onep (op1
)))
508 tree true_val
= constant_boolean_node (true, TREE_TYPE (op0
));
509 tree false_val
= constant_boolean_node (false, TREE_TYPE (op0
));
513 edge_info
= new class edge_info (true_edge
);
514 edge_info
->record_simple_equiv (op0
,
516 ? false_val
: true_val
));
517 edge_info
= new class edge_info (false_edge
);
518 edge_info
->record_simple_equiv (op0
,
520 ? true_val
: false_val
));
524 edge_info
= new class edge_info (true_edge
);
525 edge_info
->record_simple_equiv (op0
,
527 ? true_val
: false_val
));
528 edge_info
= new class edge_info (false_edge
);
529 edge_info
->record_simple_equiv (op0
,
531 ? false_val
: true_val
));
534 /* This can show up in the IL as a result of copy propagation
535 it will eventually be canonicalized, but we have to cope
536 with this case within the pass. */
537 else if (is_gimple_min_invariant (op0
)
538 && TREE_CODE (op1
) == SSA_NAME
)
540 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
541 tree inverted
= invert_truthvalue_loc (loc
, cond
);
542 bool can_infer_simple_equiv
543 = !(HONOR_SIGNED_ZEROS (op0
)
544 && real_zerop (op0
));
545 class edge_info
*edge_info
;
547 edge_info
= new class edge_info (true_edge
);
548 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
550 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
551 edge_info
->record_simple_equiv (op1
, op0
);
553 edge_info
= new class edge_info (false_edge
);
554 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
556 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
557 edge_info
->record_simple_equiv (op1
, op0
);
560 else if (TREE_CODE (op0
) == SSA_NAME
561 && (TREE_CODE (op1
) == SSA_NAME
562 || is_gimple_min_invariant (op1
)))
564 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
565 tree inverted
= invert_truthvalue_loc (loc
, cond
);
566 bool can_infer_simple_equiv
567 = !(HONOR_SIGNED_ZEROS (op1
)
568 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
569 class edge_info
*edge_info
;
571 edge_info
= new class edge_info (true_edge
);
572 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
574 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
575 edge_info
->record_simple_equiv (op0
, op1
);
577 edge_info
= new class edge_info (false_edge
);
578 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
580 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
581 edge_info
->record_simple_equiv (op0
, op1
);
587 class dom_jt_state
: public jt_state
590 dom_jt_state (const_and_copies
*copies
, avail_exprs_stack
*avails
,
591 evrp_range_analyzer
*evrp
)
592 : m_copies (copies
), m_avails (avails
), m_evrp (evrp
)
595 void push (edge e
) override
597 m_copies
->push_marker ();
598 m_avails
->push_marker ();
599 m_evrp
->push_marker ();
604 m_copies
->pop_to_marker ();
605 m_avails
->pop_to_marker ();
606 m_evrp
->pop_to_marker ();
609 void register_equivs_edge (edge e
) override
611 record_temporary_equivalences (e
, m_copies
, m_avails
);
613 void record_ranges_from_stmt (gimple
*stmt
, bool temporary
) override
615 m_evrp
->record_ranges_from_stmt (stmt
, temporary
);
617 void register_equiv (tree dest
, tree src
, bool update
) override
;
619 const_and_copies
*m_copies
;
620 avail_exprs_stack
*m_avails
;
621 evrp_range_analyzer
*m_evrp
;
625 dom_jt_state::register_equiv (tree dest
, tree src
, bool update
)
627 m_copies
->record_const_or_copy (dest
, src
);
629 /* If requested, update the value range associated with DST, using
630 the range from SRC. */
633 /* Get new VR we can pass to push_value_range. */
634 value_range_equiv
*new_vr
= m_evrp
->allocate_value_range_equiv ();
635 new (new_vr
) value_range_equiv ();
637 /* There are three cases to consider:
639 First if SRC is an SSA_NAME, then we can copy the value range
640 from SRC into NEW_VR.
642 Second if SRC is an INTEGER_CST, then we can just set NEW_VR
643 to a singleton range. Note that even if SRC is a constant we
644 need to set a suitable output range so that VR_UNDEFINED
645 ranges do not leak through.
647 Otherwise set NEW_VR to varying. This may be overly
649 if (TREE_CODE (src
) == SSA_NAME
)
650 new_vr
->deep_copy (m_evrp
->get_value_range (src
));
651 else if (TREE_CODE (src
) == INTEGER_CST
)
654 new_vr
->set_varying (TREE_TYPE (src
));
656 /* This is a temporary range for DST, so push it. */
657 m_evrp
->push_value_range (dest
, new_vr
);
661 class dom_jt_simplifier
: public jt_simplifier
664 dom_jt_simplifier (vr_values
*v
, avail_exprs_stack
*avails
)
665 : m_vr_values (v
), m_avails (avails
) { }
668 tree
simplify (gimple
*, gimple
*, basic_block
, jt_state
*) override
;
669 vr_values
*m_vr_values
;
670 avail_exprs_stack
*m_avails
;
674 dom_jt_simplifier::simplify (gimple
*stmt
, gimple
*within_stmt
,
675 basic_block
, jt_state
*)
677 /* First see if the conditional is in the hash table. */
678 tree cached_lhs
= m_avails
->lookup_avail_expr (stmt
, false, true);
682 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
684 simplify_using_ranges
simplifier (m_vr_values
);
685 return simplifier
.vrp_evaluate_conditional (gimple_cond_code (cond_stmt
),
686 gimple_cond_lhs (cond_stmt
),
687 gimple_cond_rhs (cond_stmt
),
690 if (gswitch
*switch_stmt
= dyn_cast
<gswitch
*> (stmt
))
692 tree op
= gimple_switch_index (switch_stmt
);
693 if (TREE_CODE (op
) != SSA_NAME
)
696 const value_range
*vr
= m_vr_values
->get_value_range (op
);
697 return find_case_label_range (switch_stmt
, vr
);
699 if (gassign
*assign_stmt
= dyn_cast
<gassign
*> (stmt
))
701 tree lhs
= gimple_assign_lhs (assign_stmt
);
702 if (TREE_CODE (lhs
) == SSA_NAME
703 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
704 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
705 && stmt_interesting_for_vrp (stmt
))
709 value_range_equiv new_vr
;
710 m_vr_values
->extract_range_from_stmt (stmt
, &dummy_e
, &dummy_tree
,
713 if (new_vr
.singleton_p (&singleton
))
720 class dom_opt_dom_walker
: public dom_walker
723 dom_opt_dom_walker (cdi_direction direction
,
724 jump_threader
*threader
,
726 evrp_range_analyzer
*analyzer
,
727 const_and_copies
*const_and_copies
,
728 avail_exprs_stack
*avail_exprs_stack
)
729 : dom_walker (direction
, REACHABLE_BLOCKS
)
731 m_evrp_range_analyzer
= analyzer
;
733 m_dummy_cond
= gimple_build_cond (NE_EXPR
, integer_zero_node
,
734 integer_zero_node
, NULL
, NULL
);
735 m_const_and_copies
= const_and_copies
;
736 m_avail_exprs_stack
= avail_exprs_stack
;
737 m_threader
= threader
;
740 virtual edge
before_dom_children (basic_block
);
741 virtual void after_dom_children (basic_block
);
745 /* Unwindable equivalences, both const/copy and expression varieties. */
746 class const_and_copies
*m_const_and_copies
;
747 class avail_exprs_stack
*m_avail_exprs_stack
;
749 /* Dummy condition to avoid creating lots of throw away statements. */
752 /* Optimize a single statement within a basic block using the
753 various tables mantained by DOM. Returns the taken edge if
754 the statement is a conditional with a statically determined
756 edge
optimize_stmt (basic_block
, gimple_stmt_iterator
*, bool *);
759 void test_for_singularity (gimple
*, avail_exprs_stack
*);
761 jump_threader
*m_threader
;
762 evrp_range_analyzer
*m_evrp_range_analyzer
;
766 /* Jump threading, redundancy elimination and const/copy propagation.
768 This pass may expose new symbols that need to be renamed into SSA. For
769 every new symbol exposed, its corresponding bit will be set in
774 const pass_data pass_data_dominator
=
776 GIMPLE_PASS
, /* type */
778 OPTGROUP_NONE
, /* optinfo_flags */
779 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
780 ( PROP_cfg
| PROP_ssa
), /* properties_required */
781 0, /* properties_provided */
782 0, /* properties_destroyed */
783 0, /* todo_flags_start */
784 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
787 class pass_dominator
: public gimple_opt_pass
790 pass_dominator (gcc::context
*ctxt
)
791 : gimple_opt_pass (pass_data_dominator
, ctxt
),
792 may_peel_loop_headers_p (false)
795 /* opt_pass methods: */
796 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
797 void set_pass_param (unsigned int n
, bool param
)
800 may_peel_loop_headers_p
= param
;
802 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
803 virtual unsigned int execute (function
*);
806 /* This flag is used to prevent loops from being peeled repeatedly in jump
807 threading; it will be removed once we preserve loop structures throughout
808 the compilation -- we will be able to mark the affected loops directly in
809 jump threading, and avoid peeling them next time. */
810 bool may_peel_loop_headers_p
;
811 }; // class pass_dominator
814 pass_dominator::execute (function
*fun
)
816 memset (&opt_stats
, 0, sizeof (opt_stats
));
818 /* Create our hash tables. */
819 hash_table
<expr_elt_hasher
> *avail_exprs
820 = new hash_table
<expr_elt_hasher
> (1024);
821 class avail_exprs_stack
*avail_exprs_stack
822 = new class avail_exprs_stack (avail_exprs
);
823 class const_and_copies
*const_and_copies
= new class const_and_copies ();
824 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
825 need_noreturn_fixup
.create (0);
827 calculate_dominance_info (CDI_DOMINATORS
);
830 /* We need to know loop structures in order to avoid destroying them
831 in jump threading. Note that we still can e.g. thread through loop
832 headers to an exit edge, or through loop header to the loop body, assuming
833 that we update the loop info.
835 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
836 to several overly conservative bail-outs in jump threading, case
837 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
838 missing. We should improve jump threading in future then
839 LOOPS_HAVE_PREHEADERS won't be needed here. */
840 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
841 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
843 /* We need accurate information regarding back edges in the CFG
844 for jump threading; this may include back edges that are not part of
846 mark_dfs_back_edges ();
848 /* We want to create the edge info structures before the dominator walk
849 so that they'll be in place for the jump threader, particularly when
850 threading through a join block.
852 The conditions will be lazily updated with global equivalences as
853 we reach them during the dominator walk. */
855 FOR_EACH_BB_FN (bb
, fun
)
856 record_edge_info (bb
);
858 /* Recursively walk the dominator tree optimizing statements. */
859 evrp_range_analyzer
analyzer (true);
860 dom_jt_simplifier
simplifier (&analyzer
, avail_exprs_stack
);
861 dom_jt_state
state (const_and_copies
, avail_exprs_stack
, &analyzer
);
862 jump_threader
threader (&simplifier
, &state
);
863 dom_opt_dom_walker
walker (CDI_DOMINATORS
,
869 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
871 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
872 edge. When found, remove jump threads which contain any outgoing
873 edge from the affected block. */
876 FOR_EACH_BB_FN (bb
, fun
)
881 /* First see if there are any edges without EDGE_EXECUTABLE
884 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
886 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
893 /* If there were any such edges found, then remove jump threads
894 containing any edge leaving BB. */
896 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
897 threader
.remove_jump_threads_including (e
);
902 gimple_stmt_iterator gsi
;
904 FOR_EACH_BB_FN (bb
, fun
)
906 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
907 update_stmt_if_modified (gsi_stmt (gsi
));
911 /* If we exposed any new variables, go ahead and put them into
912 SSA form now, before we handle jump threading. This simplifies
913 interactions between rewriting of _DECL nodes into SSA form
914 and rewriting SSA_NAME nodes into SSA form after block
915 duplication and CFG manipulation. */
916 update_ssa (TODO_update_ssa
);
918 free_all_edge_infos ();
920 /* Thread jumps, creating duplicate blocks as needed. */
921 cfg_altered
|= threader
.thread_through_all_blocks (may_peel_loop_headers_p
);
924 free_dominance_info (CDI_DOMINATORS
);
926 /* Removal of statements may make some EH edges dead. Purge
927 such edges from the CFG as needed. */
928 if (!bitmap_empty_p (need_eh_cleanup
))
933 /* Jump threading may have created forwarder blocks from blocks
934 needing EH cleanup; the new successor of these blocks, which
935 has inherited from the original block, needs the cleanup.
936 Don't clear bits in the bitmap, as that can break the bitmap
938 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
940 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
943 while (single_succ_p (bb
)
944 && (single_succ_edge (bb
)->flags
945 & (EDGE_EH
|EDGE_DFS_BACK
)) == 0)
946 bb
= single_succ (bb
);
947 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
949 if ((unsigned) bb
->index
!= i
)
950 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
953 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
954 bitmap_clear (need_eh_cleanup
);
957 /* Fixup stmts that became noreturn calls. This may require splitting
958 blocks and thus isn't possible during the dominator walk or before
959 jump threading finished. Do this in reverse order so we don't
960 inadvertedly remove a stmt we want to fixup by visiting a dominating
961 now noreturn call first. */
962 while (!need_noreturn_fixup
.is_empty ())
964 gimple
*stmt
= need_noreturn_fixup
.pop ();
965 if (dump_file
&& dump_flags
& TDF_DETAILS
)
967 fprintf (dump_file
, "Fixing up noreturn call ");
968 print_gimple_stmt (dump_file
, stmt
, 0);
969 fprintf (dump_file
, "\n");
971 fixup_noreturn_call (stmt
);
974 statistics_counter_event (fun
, "Redundant expressions eliminated",
976 statistics_counter_event (fun
, "Constants propagated",
977 opt_stats
.num_const_prop
);
978 statistics_counter_event (fun
, "Copies propagated",
979 opt_stats
.num_copy_prop
);
981 /* Debugging dumps. */
982 if (dump_file
&& (dump_flags
& TDF_STATS
))
983 dump_dominator_optimization_stats (dump_file
, avail_exprs
);
985 loop_optimizer_finalize ();
987 /* Delete our main hashtable. */
991 /* Free asserted bitmaps and stacks. */
992 BITMAP_FREE (need_eh_cleanup
);
993 need_noreturn_fixup
.release ();
994 delete avail_exprs_stack
;
995 delete const_and_copies
;
1003 make_pass_dominator (gcc::context
*ctxt
)
1005 return new pass_dominator (ctxt
);
1008 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
1011 dom_valueize (tree t
)
1013 if (TREE_CODE (t
) == SSA_NAME
)
1015 tree tem
= SSA_NAME_VALUE (t
);
1022 /* We have just found an equivalence for LHS on an edge E.
1023 Look backwards to other uses of LHS and see if we can derive
1024 additional equivalences that are valid on edge E. */
1026 back_propagate_equivalences (tree lhs
, edge e
,
1027 class const_and_copies
*const_and_copies
,
1030 use_operand_p use_p
;
1031 imm_use_iterator iter
;
1032 basic_block dest
= e
->dest
;
1033 bool domok
= (dom_info_state (CDI_DOMINATORS
) == DOM_OK
);
1035 /* Iterate over the uses of LHS to see if any dominate E->dest.
1036 If so, they may create useful equivalences too.
1038 ??? If the code gets re-organized to a worklist to catch more
1039 indirect opportunities and it is made to handle PHIs then this
1040 should only consider use_stmts in basic-blocks we have already visited. */
1041 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
1043 gimple
*use_stmt
= USE_STMT (use_p
);
1045 /* Often the use is in DEST, which we trivially know we can't use.
1046 This is cheaper than the dominator set tests below. */
1047 if (dest
== gimple_bb (use_stmt
))
1050 /* Filter out statements that can never produce a useful
1052 tree lhs2
= gimple_get_lhs (use_stmt
);
1053 if (!lhs2
|| TREE_CODE (lhs2
) != SSA_NAME
)
1058 if (!dominated_by_p (CDI_DOMINATORS
, dest
, gimple_bb (use_stmt
)))
1063 /* Profiling has shown the domination tests here can be fairly
1064 expensive when the fast indexes are not computed.
1065 We get significant improvements by building the
1066 set of blocks that dominate BB. We can then just test
1067 for set membership below.
1069 We also initialize the set lazily since often the only uses
1070 are going to be in the same block as DEST. */
1074 *domby
= BITMAP_ALLOC (NULL
);
1075 bitmap_tree_view (*domby
);
1076 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
1079 bitmap_set_bit (*domby
, bb
->index
);
1080 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1084 /* This tests if USE_STMT does not dominate DEST. */
1085 if (!bitmap_bit_p (*domby
, gimple_bb (use_stmt
)->index
))
1089 /* At this point USE_STMT dominates DEST and may result in a
1090 useful equivalence. Try to simplify its RHS to a constant
1092 tree res
= gimple_fold_stmt_to_constant_1 (use_stmt
, dom_valueize
,
1093 no_follow_ssa_edges
);
1094 if (res
&& (TREE_CODE (res
) == SSA_NAME
|| is_gimple_min_invariant (res
)))
1095 record_equality (lhs2
, res
, const_and_copies
);
1099 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
1100 by traversing edge E (which are cached in E->aux).
1102 Callers are responsible for managing the unwinding markers. */
1104 record_temporary_equivalences (edge e
,
1105 class const_and_copies
*const_and_copies
,
1106 class avail_exprs_stack
*avail_exprs_stack
)
1109 class edge_info
*edge_info
= (class edge_info
*) e
->aux
;
1111 /* If we have info associated with this edge, record it into
1112 our equivalence tables. */
1115 cond_equivalence
*eq
;
1116 /* If we have 0 = COND or 1 = COND equivalences, record them
1117 into our expression hash tables. */
1118 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
1119 avail_exprs_stack
->record_cond (eq
);
1121 bitmap domby
= NULL
;
1122 edge_info::equiv_pair
*seq
;
1123 for (i
= 0; edge_info
->simple_equivalences
.iterate (i
, &seq
); ++i
)
1125 tree lhs
= seq
->first
;
1126 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
)
1129 /* Record the simple NAME = VALUE equivalence. */
1130 tree rhs
= seq
->second
;
1132 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
1133 cheaper to compute than the other, then set up the equivalence
1134 such that we replace the expensive one with the cheap one.
1136 If they are the same cost to compute, then do not record
1138 if (TREE_CODE (lhs
) == SSA_NAME
&& TREE_CODE (rhs
) == SSA_NAME
)
1140 gimple
*rhs_def
= SSA_NAME_DEF_STMT (rhs
);
1141 int rhs_cost
= estimate_num_insns (rhs_def
, &eni_size_weights
);
1143 gimple
*lhs_def
= SSA_NAME_DEF_STMT (lhs
);
1144 int lhs_cost
= estimate_num_insns (lhs_def
, &eni_size_weights
);
1146 if (rhs_cost
> lhs_cost
)
1147 record_equality (rhs
, lhs
, const_and_copies
);
1148 else if (rhs_cost
< lhs_cost
)
1149 record_equality (lhs
, rhs
, const_and_copies
);
1152 record_equality (lhs
, rhs
, const_and_copies
);
1155 /* Any equivalence found for LHS may result in additional
1156 equivalences for other uses of LHS that we have already
1158 back_propagate_equivalences (lhs
, e
, const_and_copies
, &domby
);
1161 BITMAP_FREE (domby
);
1165 /* PHI nodes can create equivalences too.
1167 Ignoring any alternatives which are the same as the result, if
1168 all the alternatives are equal, then the PHI node creates an
1172 record_equivalences_from_phis (basic_block bb
)
1176 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1178 gphi
*phi
= gsi
.phi ();
1180 /* We might eliminate the PHI, so advance GSI now. */
1183 tree lhs
= gimple_phi_result (phi
);
1187 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1189 tree t
= gimple_phi_arg_def (phi
, i
);
1191 /* Ignore alternatives which are the same as our LHS. Since
1192 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1193 can simply compare pointers. */
1197 /* If the associated edge is not marked as executable, then it
1199 if ((gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_EXECUTABLE
) == 0)
1202 t
= dom_valueize (t
);
1204 /* If T is an SSA_NAME and its associated edge is a backedge,
1205 then quit as we cannot utilize this equivalence. */
1206 if (TREE_CODE (t
) == SSA_NAME
1207 && (gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_DFS_BACK
))
1210 /* If we have not processed an alternative yet, then set
1211 RHS to this alternative. */
1214 /* If we have processed an alternative (stored in RHS), then
1215 see if it is equal to this one. If it isn't, then stop
1217 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1221 /* If we had no interesting alternatives, then all the RHS alternatives
1222 must have been the same as LHS. */
1226 /* If we managed to iterate through each PHI alternative without
1227 breaking out of the loop, then we have a PHI which may create
1228 a useful equivalence. We do not need to record unwind data for
1229 this, since this is a true assignment and not an equivalence
1230 inferred from a comparison. All uses of this ssa name are dominated
1231 by this assignment, so unwinding just costs time and space. */
1232 if (i
== gimple_phi_num_args (phi
))
1234 if (may_propagate_copy (lhs
, rhs
))
1235 set_ssa_name_value (lhs
, rhs
);
1236 else if (virtual_operand_p (lhs
))
1239 imm_use_iterator iter
;
1240 use_operand_p use_p
;
1241 /* For virtual operands we have to propagate into all uses as
1242 otherwise we will create overlapping life-ranges. */
1243 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
1244 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
1245 SET_USE (use_p
, rhs
);
1246 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1247 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
) = 1;
1248 gimple_stmt_iterator tmp_gsi
= gsi_for_stmt (phi
);
1249 remove_phi_node (&tmp_gsi
, true);
1255 /* Record any equivalences created by the incoming edge to BB into
1256 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
1257 incoming edge, then no equivalence is created. */
1260 record_equivalences_from_incoming_edge (basic_block bb
,
1261 class const_and_copies
*const_and_copies
,
1262 class avail_exprs_stack
*avail_exprs_stack
)
1267 /* If our parent block ended with a control statement, then we may be
1268 able to record some equivalences based on which outgoing edge from
1269 the parent was followed. */
1270 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1272 e
= single_pred_edge_ignoring_loop_edges (bb
, true);
1274 /* If we had a single incoming edge from our parent block, then enter
1275 any data associated with the edge into our tables. */
1276 if (e
&& e
->src
== parent
)
1277 record_temporary_equivalences (e
, const_and_copies
, avail_exprs_stack
);
1280 /* Dump statistics for the hash table HTAB. */
1283 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
1285 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1286 (long) htab
.size (),
1287 (long) htab
.elements (),
1288 htab
.collisions ());
1291 /* Dump SSA statistics on FILE. */
1294 dump_dominator_optimization_stats (FILE *file
,
1295 hash_table
<expr_elt_hasher
> *avail_exprs
)
1297 fprintf (file
, "Total number of statements: %6ld\n\n",
1298 opt_stats
.num_stmts
);
1299 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1300 opt_stats
.num_exprs_considered
);
1302 fprintf (file
, "\nHash table statistics:\n");
1304 fprintf (file
, " avail_exprs: ");
1305 htab_statistics (file
, *avail_exprs
);
1309 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1310 This constrains the cases in which we may treat this as assignment. */
1313 record_equality (tree x
, tree y
, class const_and_copies
*const_and_copies
)
1315 tree prev_x
= NULL
, prev_y
= NULL
;
1317 if (tree_swap_operands_p (x
, y
))
1320 /* Most of the time tree_swap_operands_p does what we want. But there
1321 are cases where we know one operand is better for copy propagation than
1322 the other. Given no other code cares about ordering of equality
1323 comparison operators for that purpose, we just handle the special cases
1325 if (TREE_CODE (x
) == SSA_NAME
&& TREE_CODE (y
) == SSA_NAME
)
1327 /* If one operand is a single use operand, then make it
1328 X. This will preserve its single use properly and if this
1329 conditional is eliminated, the computation of X can be
1330 eliminated as well. */
1331 if (has_single_use (y
) && ! has_single_use (x
))
1334 if (TREE_CODE (x
) == SSA_NAME
)
1335 prev_x
= SSA_NAME_VALUE (x
);
1336 if (TREE_CODE (y
) == SSA_NAME
)
1337 prev_y
= SSA_NAME_VALUE (y
);
1339 /* If one of the previous values is invariant, or invariant in more loops
1340 (by depth), then use that.
1341 Otherwise it doesn't matter which value we choose, just so
1342 long as we canonicalize on one value. */
1343 if (is_gimple_min_invariant (y
))
1345 else if (is_gimple_min_invariant (x
))
1346 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1347 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1348 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1352 /* After the swapping, we must have one SSA_NAME. */
1353 if (TREE_CODE (x
) != SSA_NAME
)
1356 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1357 variable compared against zero. If we're honoring signed zeros,
1358 then we cannot record this value unless we know that the value is
1360 if (HONOR_SIGNED_ZEROS (x
)
1361 && (TREE_CODE (y
) != REAL_CST
1362 || real_equal (&dconst0
, &TREE_REAL_CST (y
))))
1365 const_and_copies
->record_const_or_copy (x
, y
, prev_x
);
1368 /* Returns true when STMT is a simple iv increment. It detects the
1369 following situation:
1371 i_1 = phi (..., i_k)
1373 i_j = i_{j-1} for each j : 2 <= j <= k-1
1375 i_k = i_{k-1} +/- ... */
1378 simple_iv_increment_p (gimple
*stmt
)
1380 enum tree_code code
;
1385 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1388 lhs
= gimple_assign_lhs (stmt
);
1389 if (TREE_CODE (lhs
) != SSA_NAME
)
1392 code
= gimple_assign_rhs_code (stmt
);
1393 if (code
!= PLUS_EXPR
1394 && code
!= MINUS_EXPR
1395 && code
!= POINTER_PLUS_EXPR
)
1398 preinc
= gimple_assign_rhs1 (stmt
);
1399 if (TREE_CODE (preinc
) != SSA_NAME
)
1402 phi
= SSA_NAME_DEF_STMT (preinc
);
1403 while (gimple_code (phi
) != GIMPLE_PHI
)
1405 /* Follow trivial copies, but not the DEF used in a back edge,
1406 so that we don't prevent coalescing. */
1407 if (!gimple_assign_ssa_name_copy_p (phi
))
1409 preinc
= gimple_assign_rhs1 (phi
);
1410 phi
= SSA_NAME_DEF_STMT (preinc
);
1413 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1414 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1420 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1421 successors of BB. */
1424 cprop_into_successor_phis (basic_block bb
,
1425 class const_and_copies
*const_and_copies
)
1430 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1435 /* If this is an abnormal edge, then we do not want to copy propagate
1436 into the PHI alternative associated with this edge. */
1437 if (e
->flags
& EDGE_ABNORMAL
)
1440 gsi
= gsi_start_phis (e
->dest
);
1441 if (gsi_end_p (gsi
))
1444 /* We may have an equivalence associated with this edge. While
1445 we cannot propagate it into non-dominated blocks, we can
1446 propagate them into PHIs in non-dominated blocks. */
1448 /* Push the unwind marker so we can reset the const and copies
1449 table back to its original state after processing this edge. */
1450 const_and_copies
->push_marker ();
1452 /* Extract and record any simple NAME = VALUE equivalences.
1454 Don't bother with [01] = COND equivalences, they're not useful
1456 class edge_info
*edge_info
= (class edge_info
*) e
->aux
;
1460 edge_info::equiv_pair
*seq
;
1461 for (int i
= 0; edge_info
->simple_equivalences
.iterate (i
, &seq
); ++i
)
1463 tree lhs
= seq
->first
;
1464 tree rhs
= seq
->second
;
1466 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1467 const_and_copies
->record_const_or_copy (lhs
, rhs
);
1473 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1476 use_operand_p orig_p
;
1478 gphi
*phi
= gsi
.phi ();
1480 /* The alternative may be associated with a constant, so verify
1481 it is an SSA_NAME before doing anything with it. */
1482 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1483 orig_val
= get_use_from_ptr (orig_p
);
1484 if (TREE_CODE (orig_val
) != SSA_NAME
)
1487 /* If we have *ORIG_P in our constant/copy table, then replace
1488 ORIG_P with its value in our constant/copy table. */
1489 new_val
= SSA_NAME_VALUE (orig_val
);
1491 && new_val
!= orig_val
1492 && may_propagate_copy (orig_val
, new_val
))
1493 propagate_value (orig_p
, new_val
);
1496 const_and_copies
->pop_to_marker ();
1501 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1503 gimple_stmt_iterator gsi
;
1505 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1506 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1508 m_evrp_range_analyzer
->enter (bb
);
1510 /* Push a marker on the stacks of local information so that we know how
1511 far to unwind when we finalize this block. */
1512 m_avail_exprs_stack
->push_marker ();
1513 m_const_and_copies
->push_marker ();
1515 record_equivalences_from_incoming_edge (bb
, m_const_and_copies
,
1516 m_avail_exprs_stack
);
1518 /* PHI nodes can create equivalences too. */
1519 record_equivalences_from_phis (bb
);
1521 /* Create equivalences from redundant PHIs. PHIs are only truly
1522 redundant when they exist in the same block, so push another
1523 marker and unwind right afterwards. */
1524 m_avail_exprs_stack
->push_marker ();
1525 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1526 eliminate_redundant_computations (&gsi
, m_const_and_copies
,
1527 m_avail_exprs_stack
);
1528 m_avail_exprs_stack
->pop_to_marker ();
1530 edge taken_edge
= NULL
;
1531 /* Initialize visited flag ahead of us, it has undefined state on
1533 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1534 gimple_set_visited (gsi_stmt (gsi
), false);
1535 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1537 /* Do not optimize a stmt twice, substitution might end up with
1538 _3 = _3 which is not valid. */
1539 if (gimple_visited_p (gsi_stmt (gsi
)))
1545 m_state
->record_ranges_from_stmt (gsi_stmt (gsi
), false);
1546 bool removed_p
= false;
1547 taken_edge
= this->optimize_stmt (bb
, &gsi
, &removed_p
);
1549 gimple_set_visited (gsi_stmt (gsi
), true);
1551 /* Go back and visit stmts inserted by folding after substituting
1552 into the stmt at gsi. */
1553 if (gsi_end_p (gsi
))
1555 gcc_checking_assert (removed_p
);
1556 gsi
= gsi_last_bb (bb
);
1557 while (!gsi_end_p (gsi
) && !gimple_visited_p (gsi_stmt (gsi
)))
1566 while (!gsi_end_p (gsi
) && !gimple_visited_p (gsi_stmt (gsi
)));
1568 if (gsi_end_p (gsi
))
1569 gsi
= gsi_start_bb (bb
);
1574 /* Now prepare to process dominated blocks. */
1575 record_edge_info (bb
);
1576 cprop_into_successor_phis (bb
, m_const_and_copies
);
1577 if (taken_edge
&& !dbg_cnt (dom_unreachable_edges
))
1583 /* We have finished processing the dominator children of BB, perform
1584 any finalization actions in preparation for leaving this node in
1585 the dominator tree. */
1588 dom_opt_dom_walker::after_dom_children (basic_block bb
)
1590 m_threader
->thread_outgoing_edges (bb
);
1591 m_avail_exprs_stack
->pop_to_marker ();
1592 m_const_and_copies
->pop_to_marker ();
1593 m_evrp_range_analyzer
->leave (bb
);
1596 /* Search for redundant computations in STMT. If any are found, then
1597 replace them with the variable holding the result of the computation.
1599 If safe, record this expression into AVAIL_EXPRS_STACK and
1600 CONST_AND_COPIES. */
1603 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
,
1604 class const_and_copies
*const_and_copies
,
1605 class avail_exprs_stack
*avail_exprs_stack
)
1611 bool assigns_var_p
= false;
1613 gimple
*stmt
= gsi_stmt (*gsi
);
1615 if (gimple_code (stmt
) == GIMPLE_PHI
)
1616 def
= gimple_phi_result (stmt
);
1618 def
= gimple_get_lhs (stmt
);
1620 /* Certain expressions on the RHS can be optimized away, but cannot
1621 themselves be entered into the hash tables. */
1623 || TREE_CODE (def
) != SSA_NAME
1624 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1625 || gimple_vdef (stmt
)
1626 /* Do not record equivalences for increments of ivs. This would create
1627 overlapping live ranges for a very questionable gain. */
1628 || simple_iv_increment_p (stmt
))
1631 /* Check if the expression has been computed before. */
1632 cached_lhs
= avail_exprs_stack
->lookup_avail_expr (stmt
, insert
, true);
1634 opt_stats
.num_exprs_considered
++;
1636 /* Get the type of the expression we are trying to optimize. */
1637 if (is_gimple_assign (stmt
))
1639 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1640 assigns_var_p
= true;
1642 else if (gimple_code (stmt
) == GIMPLE_COND
)
1643 expr_type
= boolean_type_node
;
1644 else if (is_gimple_call (stmt
))
1646 gcc_assert (gimple_call_lhs (stmt
));
1647 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1648 assigns_var_p
= true;
1650 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1651 expr_type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
1652 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1653 /* We can't propagate into a phi, so the logic below doesn't apply.
1654 Instead record an equivalence between the cached LHS and the
1655 PHI result of this statement, provided they are in the same block.
1656 This should be sufficient to kill the redundant phi. */
1658 if (def
&& cached_lhs
)
1659 const_and_copies
->record_const_or_copy (def
, cached_lhs
);
1668 /* It is safe to ignore types here since we have already done
1669 type checking in the hashing and equality routines. In fact
1670 type checking here merely gets in the way of constant
1671 propagation. Also, make sure that it is safe to propagate
1672 CACHED_LHS into the expression in STMT. */
1673 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1675 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1676 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1678 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1679 || is_gimple_min_invariant (cached_lhs
));
1681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1683 fprintf (dump_file
, " Replaced redundant expr '");
1684 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1685 fprintf (dump_file
, "' with '");
1686 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1687 fprintf (dump_file
, "'\n");
1693 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1694 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1696 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1698 /* Since it is always necessary to mark the result as modified,
1699 perhaps we should move this into propagate_tree_value_into_stmt
1701 gimple_set_modified (gsi_stmt (*gsi
), true);
1705 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1706 the available expressions table or the const_and_copies table.
1707 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1709 We handle only very simple copy equivalences here. The heavy
1710 lifing is done by eliminate_redundant_computations. */
1713 record_equivalences_from_stmt (gimple
*stmt
, int may_optimize_p
,
1714 class avail_exprs_stack
*avail_exprs_stack
)
1717 enum tree_code lhs_code
;
1719 gcc_assert (is_gimple_assign (stmt
));
1721 lhs
= gimple_assign_lhs (stmt
);
1722 lhs_code
= TREE_CODE (lhs
);
1724 if (lhs_code
== SSA_NAME
1725 && gimple_assign_single_p (stmt
))
1727 tree rhs
= gimple_assign_rhs1 (stmt
);
1729 /* If the RHS of the assignment is a constant or another variable that
1730 may be propagated, register it in the CONST_AND_COPIES table. We
1731 do not need to record unwind data for this, since this is a true
1732 assignment and not an equivalence inferred from a comparison. All
1733 uses of this ssa name are dominated by this assignment, so unwinding
1734 just costs time and space. */
1736 && (TREE_CODE (rhs
) == SSA_NAME
1737 || is_gimple_min_invariant (rhs
)))
1739 rhs
= dom_valueize (rhs
);
1741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1743 fprintf (dump_file
, "==== ASGN ");
1744 print_generic_expr (dump_file
, lhs
);
1745 fprintf (dump_file
, " = ");
1746 print_generic_expr (dump_file
, rhs
);
1747 fprintf (dump_file
, "\n");
1750 set_ssa_name_value (lhs
, rhs
);
1754 /* Make sure we can propagate &x + CST. */
1755 if (lhs_code
== SSA_NAME
1756 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1757 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
1758 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
1760 tree op0
= gimple_assign_rhs1 (stmt
);
1761 tree op1
= gimple_assign_rhs2 (stmt
);
1763 = build1 (ADDR_EXPR
, TREE_TYPE (op0
),
1764 fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (op0
)),
1765 unshare_expr (op0
), fold_convert (ptr_type_node
,
1767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1769 fprintf (dump_file
, "==== ASGN ");
1770 print_generic_expr (dump_file
, lhs
);
1771 fprintf (dump_file
, " = ");
1772 print_generic_expr (dump_file
, new_rhs
);
1773 fprintf (dump_file
, "\n");
1776 set_ssa_name_value (lhs
, new_rhs
);
1779 /* A memory store, even an aliased store, creates a useful
1780 equivalence. By exchanging the LHS and RHS, creating suitable
1781 vops and recording the result in the available expression table,
1782 we may be able to expose more redundant loads. */
1783 if (!gimple_has_volatile_ops (stmt
)
1784 && gimple_references_memory_p (stmt
)
1785 && gimple_assign_single_p (stmt
)
1786 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1787 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1788 && !is_gimple_reg (lhs
))
1790 tree rhs
= gimple_assign_rhs1 (stmt
);
1793 /* Build a new statement with the RHS and LHS exchanged. */
1794 if (TREE_CODE (rhs
) == SSA_NAME
)
1796 /* NOTE tuples. The call to gimple_build_assign below replaced
1797 a call to build_gimple_modify_stmt, which did not set the
1798 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1799 may cause an SSA validation failure, as the LHS may be a
1800 default-initialized name and should have no definition. I'm
1801 a bit dubious of this, as the artificial statement that we
1802 generate here may in fact be ill-formed, but it is simply
1803 used as an internal device in this pass, and never becomes
1805 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1806 new_stmt
= gimple_build_assign (rhs
, lhs
);
1807 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1810 new_stmt
= gimple_build_assign (rhs
, lhs
);
1812 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
1814 /* Finally enter the statement into the available expression
1816 avail_exprs_stack
->lookup_avail_expr (new_stmt
, true, true);
1820 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1821 CONST_AND_COPIES. */
1824 cprop_operand (gimple
*stmt
, use_operand_p op_p
, range_query
*query
)
1827 tree op
= USE_FROM_PTR (op_p
);
1829 /* If the operand has a known constant value or it is known to be a
1830 copy of some other variable, use the value or copy stored in
1831 CONST_AND_COPIES. */
1832 val
= SSA_NAME_VALUE (op
);
1837 if (query
->range_of_expr (r
, op
, stmt
) && r
.singleton_p (&single
))
1841 if (val
&& val
!= op
)
1843 /* Do not replace hard register operands in asm statements. */
1844 if (gimple_code (stmt
) == GIMPLE_ASM
1845 && !may_propagate_copy_into_asm (op
))
1848 /* Certain operands are not allowed to be copy propagated due
1849 to their interaction with exception handling and some GCC
1851 if (!may_propagate_copy (op
, val
))
1854 /* Do not propagate copies into BIVs.
1855 See PR23821 and PR62217 for how this can disturb IV and
1856 number of iteration analysis. */
1857 if (TREE_CODE (val
) != INTEGER_CST
)
1859 gimple
*def
= SSA_NAME_DEF_STMT (op
);
1860 if (gimple_code (def
) == GIMPLE_PHI
1861 && gimple_bb (def
)->loop_father
->header
== gimple_bb (def
))
1866 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1868 fprintf (dump_file
, " Replaced '");
1869 print_generic_expr (dump_file
, op
, dump_flags
);
1870 fprintf (dump_file
, "' with %s '",
1871 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1872 print_generic_expr (dump_file
, val
, dump_flags
);
1873 fprintf (dump_file
, "'\n");
1876 if (TREE_CODE (val
) != SSA_NAME
)
1877 opt_stats
.num_const_prop
++;
1879 opt_stats
.num_copy_prop
++;
1881 propagate_value (op_p
, val
);
1883 /* And note that we modified this statement. This is now
1884 safe, even if we changed virtual operands since we will
1885 rescan the statement and rewrite its operands again. */
1886 gimple_set_modified (stmt
, true);
1890 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1891 known value for that SSA_NAME (or NULL if no value is known).
1893 Propagate values from CONST_AND_COPIES into the uses, vuses and
1894 vdef_ops of STMT. */
1897 cprop_into_stmt (gimple
*stmt
, range_query
*query
)
1901 tree last_copy_propagated_op
= NULL
;
1903 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
1905 tree old_op
= USE_FROM_PTR (op_p
);
1907 /* If we have A = B and B = A in the copy propagation tables
1908 (due to an equality comparison), avoid substituting B for A
1909 then A for B in the trivially discovered cases. This allows
1910 optimization of statements were A and B appear as input
1912 if (old_op
!= last_copy_propagated_op
)
1914 cprop_operand (stmt
, op_p
, query
);
1916 tree new_op
= USE_FROM_PTR (op_p
);
1917 if (new_op
!= old_op
&& TREE_CODE (new_op
) == SSA_NAME
)
1918 last_copy_propagated_op
= new_op
;
1923 /* If STMT contains a relational test, try to convert it into an
1924 equality test if there is only a single value which can ever
1927 For example, if the expression hash table contains:
1931 And we have a test within statement of i >= 1, then we can safely
1932 rewrite the test as i == 1 since there only a single value where
1935 This is similar to code in VRP. */
1938 dom_opt_dom_walker::test_for_singularity (gimple
*stmt
,
1939 avail_exprs_stack
*avail_exprs_stack
)
1941 /* We want to support gimple conditionals as well as assignments
1942 where the RHS contains a conditional. */
1943 if (is_gimple_assign (stmt
) || gimple_code (stmt
) == GIMPLE_COND
)
1945 enum tree_code code
= ERROR_MARK
;
1948 /* Extract the condition of interest from both forms we support. */
1949 if (is_gimple_assign (stmt
))
1951 code
= gimple_assign_rhs_code (stmt
);
1952 lhs
= gimple_assign_rhs1 (stmt
);
1953 rhs
= gimple_assign_rhs2 (stmt
);
1955 else if (gimple_code (stmt
) == GIMPLE_COND
)
1957 code
= gimple_cond_code (as_a
<gcond
*> (stmt
));
1958 lhs
= gimple_cond_lhs (as_a
<gcond
*> (stmt
));
1959 rhs
= gimple_cond_rhs (as_a
<gcond
*> (stmt
));
1962 /* We're looking for a relational test using LE/GE. Also note we can
1963 canonicalize LT/GT tests against constants into LE/GT tests. */
1964 if (code
== LE_EXPR
|| code
== GE_EXPR
1965 || ((code
== LT_EXPR
|| code
== GT_EXPR
)
1966 && TREE_CODE (rhs
) == INTEGER_CST
))
1968 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */
1969 if (code
== LT_EXPR
)
1970 rhs
= fold_build2 (MINUS_EXPR
, TREE_TYPE (rhs
),
1971 rhs
, build_int_cst (TREE_TYPE (rhs
), 1));
1973 if (code
== GT_EXPR
)
1974 rhs
= fold_build2 (PLUS_EXPR
, TREE_TYPE (rhs
),
1975 rhs
, build_int_cst (TREE_TYPE (rhs
), 1));
1977 /* Determine the code we want to check for in the hash table. */
1978 enum tree_code test_code
;
1979 if (code
== GE_EXPR
|| code
== GT_EXPR
)
1980 test_code
= LE_EXPR
;
1982 test_code
= GE_EXPR
;
1984 /* Update the dummy statement so we can query the hash tables. */
1985 gimple_cond_set_code (m_dummy_cond
, test_code
);
1986 gimple_cond_set_lhs (m_dummy_cond
, lhs
);
1987 gimple_cond_set_rhs (m_dummy_cond
, rhs
);
1989 = avail_exprs_stack
->lookup_avail_expr (m_dummy_cond
,
1992 /* If the lookup returned 1 (true), then the expression we
1993 queried was in the hash table. As a result there is only
1994 one value that makes the original conditional true. Update
1995 STMT accordingly. */
1996 if (cached_lhs
&& integer_onep (cached_lhs
))
1998 if (is_gimple_assign (stmt
))
2000 gimple_assign_set_rhs_code (stmt
, EQ_EXPR
);
2001 gimple_assign_set_rhs2 (stmt
, rhs
);
2002 gimple_set_modified (stmt
, true);
2006 gimple_set_modified (stmt
, true);
2007 gimple_cond_set_code (as_a
<gcond
*> (stmt
), EQ_EXPR
);
2008 gimple_cond_set_rhs (as_a
<gcond
*> (stmt
), rhs
);
2009 gimple_set_modified (stmt
, true);
2016 /* If STMT is a comparison of two uniform vectors reduce it to a comparison
2017 of scalar objects, otherwise leave STMT unchanged. */
2020 reduce_vector_comparison_to_scalar_comparison (gimple
*stmt
)
2022 if (gimple_code (stmt
) == GIMPLE_COND
)
2024 tree lhs
= gimple_cond_lhs (stmt
);
2025 tree rhs
= gimple_cond_rhs (stmt
);
2027 /* We may have a vector comparison where both arms are uniform
2028 vectors. If so, we can simplify the vector comparison down
2029 to a scalar comparison. */
2030 if (TREE_CODE (TREE_TYPE (lhs
)) == VECTOR_TYPE
2031 && TREE_CODE (TREE_TYPE (rhs
)) == VECTOR_TYPE
)
2033 /* If either operand is an SSA_NAME, then look back to its
2034 defining statement to try and get at a suitable source. */
2035 if (TREE_CODE (rhs
) == SSA_NAME
)
2037 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
);
2038 if (gimple_assign_single_p (def_stmt
))
2039 rhs
= gimple_assign_rhs1 (def_stmt
);
2042 if (TREE_CODE (lhs
) == SSA_NAME
)
2044 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
2045 if (gimple_assign_single_p (def_stmt
))
2046 lhs
= gimple_assign_rhs1 (def_stmt
);
2049 /* Now see if they are both uniform vectors and if so replace
2050 the vector comparison with a scalar comparison. */
2051 tree rhs_elem
= rhs
? uniform_vector_p (rhs
) : NULL_TREE
;
2052 tree lhs_elem
= lhs
? uniform_vector_p (lhs
) : NULL_TREE
;
2053 if (rhs_elem
&& lhs_elem
)
2055 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2057 fprintf (dump_file
, "Reducing vector comparison: ");
2058 print_gimple_stmt (dump_file
, stmt
, 0);
2061 gimple_cond_set_rhs (as_a
<gcond
*>(stmt
), rhs_elem
);
2062 gimple_cond_set_lhs (as_a
<gcond
*>(stmt
), lhs_elem
);
2063 gimple_set_modified (stmt
, true);
2065 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2067 fprintf (dump_file
, "To scalar equivalent: ");
2068 print_gimple_stmt (dump_file
, stmt
, 0);
2069 fprintf (dump_file
, "\n");
2076 /* Optimize the statement in block BB pointed to by iterator SI.
2078 We try to perform some simplistic global redundancy elimination and
2079 constant propagation:
2081 1- To detect global redundancy, we keep track of expressions that have
2082 been computed in this block and its dominators. If we find that the
2083 same expression is computed more than once, we eliminate repeated
2084 computations by using the target of the first one.
2086 2- Constant values and copy assignments. This is used to do very
2087 simplistic constant and copy propagation. When a constant or copy
2088 assignment is found, we map the value on the RHS of the assignment to
2089 the variable in the LHS in the CONST_AND_COPIES table.
2091 3- Very simple redundant store elimination is performed.
2093 4- We can simplify a condition to a constant or from a relational
2094 condition to an equality condition. */
2097 dom_opt_dom_walker::optimize_stmt (basic_block bb
, gimple_stmt_iterator
*si
,
2100 gimple
*stmt
, *old_stmt
;
2101 bool may_optimize_p
;
2102 bool modified_p
= false;
2106 old_stmt
= stmt
= gsi_stmt (*si
);
2107 was_noreturn
= is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
);
2109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2111 fprintf (dump_file
, "Optimizing statement ");
2112 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2115 /* STMT may be a comparison of uniform vectors that we can simplify
2116 down to a comparison of scalars. Do that transformation first
2117 so that all the scalar optimizations from here onward apply. */
2118 reduce_vector_comparison_to_scalar_comparison (stmt
);
2120 update_stmt_if_modified (stmt
);
2121 opt_stats
.num_stmts
++;
2123 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2124 cprop_into_stmt (stmt
, m_evrp_range_analyzer
);
2126 /* If the statement has been modified with constant replacements,
2127 fold its RHS before checking for redundant computations. */
2128 if (gimple_modified_p (stmt
))
2132 /* Try to fold the statement making sure that STMT is kept
2136 stmt
= gsi_stmt (*si
);
2137 gimple_set_modified (stmt
, true);
2139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2141 fprintf (dump_file
, " Folded to: ");
2142 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2146 /* We only need to consider cases that can yield a gimple operand. */
2147 if (gimple_assign_single_p (stmt
))
2148 rhs
= gimple_assign_rhs1 (stmt
);
2149 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
2150 rhs
= gimple_goto_dest (stmt
);
2151 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
2152 /* This should never be an ADDR_EXPR. */
2153 rhs
= gimple_switch_index (swtch_stmt
);
2155 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
2156 recompute_tree_invariant_for_addr_expr (rhs
);
2158 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2159 even if fold_stmt updated the stmt already and thus cleared
2160 gimple_modified_p flag on it. */
2164 /* Check for redundant computations. Do this optimization only
2165 for assignments that have no volatile ops and conditionals. */
2166 may_optimize_p
= (!gimple_has_side_effects (stmt
)
2167 && (is_gimple_assign (stmt
)
2168 || (is_gimple_call (stmt
)
2169 && gimple_call_lhs (stmt
) != NULL_TREE
)
2170 || gimple_code (stmt
) == GIMPLE_COND
2171 || gimple_code (stmt
) == GIMPLE_SWITCH
));
2175 if (gimple_code (stmt
) == GIMPLE_CALL
)
2177 /* Resolve __builtin_constant_p. If it hasn't been
2178 folded to integer_one_node by now, it's fairly
2179 certain that the value simply isn't constant. */
2180 tree callee
= gimple_call_fndecl (stmt
);
2182 && fndecl_built_in_p (callee
, BUILT_IN_CONSTANT_P
))
2184 propagate_tree_value_into_stmt (si
, integer_zero_node
);
2185 stmt
= gsi_stmt (*si
);
2189 if (gimple_code (stmt
) == GIMPLE_COND
)
2191 tree lhs
= gimple_cond_lhs (stmt
);
2192 tree rhs
= gimple_cond_rhs (stmt
);
2194 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
2195 then this conditional is computable at compile time. We can just
2196 shove either 0 or 1 into the LHS, mark the statement as modified
2197 and all the right things will just happen below.
2199 Note this would apply to any case where LHS has a range
2200 narrower than its type implies and RHS is outside that
2201 narrower range. Future work. */
2202 if (TREE_CODE (lhs
) == SSA_NAME
2203 && ssa_name_has_boolean_range (lhs
)
2204 && TREE_CODE (rhs
) == INTEGER_CST
2205 && ! (integer_zerop (rhs
) || integer_onep (rhs
)))
2207 gimple_cond_set_lhs (as_a
<gcond
*> (stmt
),
2208 fold_convert (TREE_TYPE (lhs
),
2209 integer_zero_node
));
2210 gimple_set_modified (stmt
, true);
2212 else if (TREE_CODE (lhs
) == SSA_NAME
)
2214 /* Exploiting EVRP data is not yet fully integrated into DOM
2215 but we need to do something for this case to avoid regressing
2216 udr4.f90 and new1.C which have unexecutable blocks with
2217 undefined behavior that get diagnosed if they're left in the
2218 IL because we've attached range information to new
2220 update_stmt_if_modified (stmt
);
2221 edge taken_edge
= NULL
;
2222 simplify_using_ranges
simpl (m_evrp_range_analyzer
);
2223 simpl
.vrp_visit_cond_stmt (as_a
<gcond
*> (stmt
), &taken_edge
);
2226 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
2227 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
2228 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
2229 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
2232 gimple_set_modified (stmt
, true);
2240 update_stmt_if_modified (stmt
);
2241 eliminate_redundant_computations (si
, m_const_and_copies
,
2242 m_avail_exprs_stack
);
2243 stmt
= gsi_stmt (*si
);
2245 /* Perform simple redundant store elimination. */
2246 if (gimple_assign_single_p (stmt
)
2247 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
2249 tree lhs
= gimple_assign_lhs (stmt
);
2250 tree rhs
= gimple_assign_rhs1 (stmt
);
2253 rhs
= dom_valueize (rhs
);
2254 /* Build a new statement with the RHS and LHS exchanged. */
2255 if (TREE_CODE (rhs
) == SSA_NAME
)
2257 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
2258 new_stmt
= gimple_build_assign (rhs
, lhs
);
2259 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
2262 new_stmt
= gimple_build_assign (rhs
, lhs
);
2263 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2264 expr_hash_elt
*elt
= NULL
;
2265 cached_lhs
= m_avail_exprs_stack
->lookup_avail_expr (new_stmt
, false,
2268 && operand_equal_p (rhs
, cached_lhs
, 0)
2269 && refs_same_for_tbaa_p (elt
->expr ()->kind
== EXPR_SINGLE
2270 ? elt
->expr ()->ops
.single
.rhs
2273 basic_block bb
= gimple_bb (stmt
);
2274 unlink_stmt_vdef (stmt
);
2275 if (gsi_remove (si
, true))
2277 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2279 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2281 release_defs (stmt
);
2287 /* If this statement was not redundant, we may still be able to simplify
2288 it, which may in turn allow other part of DOM or other passes to do
2290 test_for_singularity (stmt
, m_avail_exprs_stack
);
2293 /* Record any additional equivalences created by this statement. */
2294 if (is_gimple_assign (stmt
))
2295 record_equivalences_from_stmt (stmt
, may_optimize_p
, m_avail_exprs_stack
);
2297 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
2298 know where it goes. */
2299 if (gimple_modified_p (stmt
) || modified_p
)
2303 if (gimple_code (stmt
) == GIMPLE_COND
)
2304 val
= fold_binary_loc (gimple_location (stmt
),
2305 gimple_cond_code (stmt
), boolean_type_node
,
2306 gimple_cond_lhs (stmt
),
2307 gimple_cond_rhs (stmt
));
2308 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
2309 val
= gimple_switch_index (swtch_stmt
);
2311 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2313 retval
= find_taken_edge (bb
, val
);
2316 /* Fix the condition to be either true or false. */
2317 if (gimple_code (stmt
) == GIMPLE_COND
)
2319 if (integer_zerop (val
))
2320 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
2321 else if (integer_onep (val
))
2322 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
2326 gimple_set_modified (stmt
, true);
2329 /* Further simplifications may be possible. */
2334 update_stmt_if_modified (stmt
);
2336 /* If we simplified a statement in such a way as to be shown that it
2337 cannot trap, update the eh information and the cfg to match. */
2338 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
2340 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2342 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2346 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
2347 need_noreturn_fixup
.safe_push (stmt
);