1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2021 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. */
226 tree rhs
= gimple_assign_rhs1 (def_stmt
);
227 tree rhs_type
= TREE_TYPE (rhs
);
228 if (INTEGRAL_TYPE_P (rhs_type
)
229 && (TYPE_PRECISION (TREE_TYPE (name
))
230 >= TYPE_PRECISION (rhs_type
))
231 && int_fits_type_p (value
, rhs_type
))
232 derive_equivalences (rhs
,
233 fold_convert (rhs_type
, value
),
234 recursion_limit
- 1);
238 /* We can invert the operation of these codes trivially if
239 one of the RHS operands is a constant to produce a known
240 value for the other RHS operand. */
241 case POINTER_PLUS_EXPR
:
244 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
245 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
247 /* If either argument is a constant, then we can compute
248 a constant value for the nonconstant argument. */
249 if (TREE_CODE (rhs1
) == INTEGER_CST
250 && TREE_CODE (rhs2
) == SSA_NAME
)
251 derive_equivalences (rhs2
,
252 fold_binary (MINUS_EXPR
, TREE_TYPE (rhs1
),
254 recursion_limit
- 1);
255 else if (TREE_CODE (rhs2
) == INTEGER_CST
256 && TREE_CODE (rhs1
) == SSA_NAME
)
257 derive_equivalences (rhs1
,
258 fold_binary (MINUS_EXPR
, TREE_TYPE (rhs1
),
260 recursion_limit
- 1);
264 /* If one of the operands is a constant, then we can compute
265 the value of the other operand. If both operands are
266 SSA_NAMEs, then they must be equal if the result is zero. */
269 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
270 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
272 /* If either argument is a constant, then we can compute
273 a constant value for the nonconstant argument. */
274 if (TREE_CODE (rhs1
) == INTEGER_CST
275 && TREE_CODE (rhs2
) == SSA_NAME
)
276 derive_equivalences (rhs2
,
277 fold_binary (MINUS_EXPR
, TREE_TYPE (rhs1
),
279 recursion_limit
- 1);
280 else if (TREE_CODE (rhs2
) == INTEGER_CST
281 && TREE_CODE (rhs1
) == SSA_NAME
)
282 derive_equivalences (rhs1
,
283 fold_binary (PLUS_EXPR
, TREE_TYPE (rhs1
),
285 recursion_limit
- 1);
286 else if (integer_zerop (value
))
288 tree cond
= build2 (EQ_EXPR
, boolean_type_node
,
289 gimple_assign_rhs1 (def_stmt
),
290 gimple_assign_rhs2 (def_stmt
));
291 tree inverted
= invert_truthvalue (cond
);
292 record_conditions (&this->cond_equivalences
, cond
, inverted
);
300 if ((code
== EQ_EXPR
&& integer_onep (value
))
301 || (code
== NE_EXPR
&& integer_zerop (value
)))
303 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
304 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
306 /* If either argument is a constant, then record the
307 other argument as being the same as that constant.
309 If neither operand is a constant, then we have a
310 conditional name == name equivalence. */
311 if (TREE_CODE (rhs1
) == INTEGER_CST
)
312 derive_equivalences (rhs2
, rhs1
, recursion_limit
- 1);
313 else if (TREE_CODE (rhs2
) == INTEGER_CST
)
314 derive_equivalences (rhs1
, rhs2
, recursion_limit
- 1);
318 tree cond
= build2 (code
, boolean_type_node
,
319 gimple_assign_rhs1 (def_stmt
),
320 gimple_assign_rhs2 (def_stmt
));
321 tree inverted
= invert_truthvalue (cond
);
322 if (integer_zerop (value
))
323 std::swap (cond
, inverted
);
324 record_conditions (&this->cond_equivalences
, cond
, inverted
);
329 /* For BIT_NOT and NEGATE, we can just apply the operation to the
330 VALUE to get the new equivalence. It will always be a constant
331 so we can recurse. */
335 tree rhs
= gimple_assign_rhs1 (def_stmt
);
337 /* If this is a NOT and the operand has a boolean range, then we
338 know its value must be zero or one. We are not supposed to
339 have a BIT_NOT_EXPR for boolean types with precision > 1 in
340 the general case, see e.g. the handling of TRUTH_NOT_EXPR in
341 the gimplifier, but it can be generated by match.pd out of
342 a BIT_XOR_EXPR wrapped in a BIT_AND_EXPR. Now the handling
343 of BIT_AND_EXPR above already forces a specific semantics for
344 boolean types with precision > 1 so we must do the same here,
345 otherwise we could change the semantics of TRUTH_NOT_EXPR for
346 boolean types with precision > 1. */
347 if (code
== BIT_NOT_EXPR
348 && TREE_CODE (rhs
) == SSA_NAME
349 && ssa_name_has_boolean_range (rhs
))
351 if ((TREE_INT_CST_LOW (value
) & 1) == 0)
352 res
= build_one_cst (TREE_TYPE (rhs
));
354 res
= build_zero_cst (TREE_TYPE (rhs
));
357 res
= fold_build1 (code
, TREE_TYPE (rhs
), value
);
358 derive_equivalences (rhs
, res
, recursion_limit
- 1);
364 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
366 tree cond
= build2 (code
, boolean_type_node
,
367 gimple_assign_rhs1 (def_stmt
),
368 gimple_assign_rhs2 (def_stmt
));
369 tree inverted
= invert_truthvalue (cond
);
370 if (integer_zerop (value
))
371 std::swap (cond
, inverted
);
372 record_conditions (&this->cond_equivalences
, cond
, inverted
);
382 edge_info::record_simple_equiv (tree lhs
, tree rhs
)
384 /* If the RHS is a constant, then we may be able to derive
385 further equivalences. Else just record the name = name
387 if (TREE_CODE (rhs
) == INTEGER_CST
)
388 derive_equivalences (lhs
, rhs
, 4);
390 simple_equivalences
.safe_push (equiv_pair (lhs
, rhs
));
393 /* Free the edge_info data attached to E, if it exists. */
396 free_dom_edge_info (edge e
)
398 class edge_info
*edge_info
= (class edge_info
*)e
->aux
;
404 /* Free all EDGE_INFO structures associated with edges in the CFG.
405 If a particular edge can be threaded, copy the redirection
406 target from the EDGE_INFO structure into the edge's AUX field
407 as required by code to update the CFG and SSA graph for
411 free_all_edge_infos (void)
417 FOR_EACH_BB_FN (bb
, cfun
)
419 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
421 free_dom_edge_info (e
);
427 /* We have finished optimizing BB, record any information implied by
428 taking a specific outgoing edge from BB. */
431 record_edge_info (basic_block bb
)
433 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
434 class edge_info
*edge_info
;
436 if (! gsi_end_p (gsi
))
438 gimple
*stmt
= gsi_stmt (gsi
);
439 location_t loc
= gimple_location (stmt
);
441 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
443 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
444 tree index
= gimple_switch_index (switch_stmt
);
446 if (TREE_CODE (index
) == SSA_NAME
)
449 int n_labels
= gimple_switch_num_labels (switch_stmt
);
450 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
454 for (i
= 0; i
< n_labels
; i
++)
456 tree label
= gimple_switch_label (switch_stmt
, i
);
457 basic_block target_bb
458 = label_to_block (cfun
, CASE_LABEL (label
));
459 if (CASE_HIGH (label
)
461 || info
[target_bb
->index
])
462 info
[target_bb
->index
] = error_mark_node
;
464 info
[target_bb
->index
] = label
;
467 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
469 basic_block target_bb
= e
->dest
;
470 tree label
= info
[target_bb
->index
];
472 if (label
!= NULL
&& label
!= error_mark_node
)
474 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
476 edge_info
= new class edge_info (e
);
477 edge_info
->record_simple_equiv (index
, x
);
484 /* A COND_EXPR may create equivalences too. */
485 if (gimple_code (stmt
) == GIMPLE_COND
)
490 tree op0
= gimple_cond_lhs (stmt
);
491 tree op1
= gimple_cond_rhs (stmt
);
492 enum tree_code code
= gimple_cond_code (stmt
);
494 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
496 /* Special case comparing booleans against a constant as we
497 know the value of OP0 on both arms of the branch. i.e., we
498 can record an equivalence for OP0 rather than COND.
500 However, don't do this if the constant isn't zero or one.
501 Such conditionals will get optimized more thoroughly during
503 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
504 && TREE_CODE (op0
) == SSA_NAME
505 && ssa_name_has_boolean_range (op0
)
506 && is_gimple_min_invariant (op1
)
507 && (integer_zerop (op1
) || integer_onep (op1
)))
509 tree true_val
= constant_boolean_node (true, TREE_TYPE (op0
));
510 tree false_val
= constant_boolean_node (false, TREE_TYPE (op0
));
514 edge_info
= new class edge_info (true_edge
);
515 edge_info
->record_simple_equiv (op0
,
517 ? false_val
: true_val
));
518 edge_info
= new class edge_info (false_edge
);
519 edge_info
->record_simple_equiv (op0
,
521 ? true_val
: false_val
));
525 edge_info
= new class edge_info (true_edge
);
526 edge_info
->record_simple_equiv (op0
,
528 ? true_val
: false_val
));
529 edge_info
= new class edge_info (false_edge
);
530 edge_info
->record_simple_equiv (op0
,
532 ? false_val
: true_val
));
535 /* This can show up in the IL as a result of copy propagation
536 it will eventually be canonicalized, but we have to cope
537 with this case within the pass. */
538 else if (is_gimple_min_invariant (op0
)
539 && TREE_CODE (op1
) == SSA_NAME
)
541 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
542 tree inverted
= invert_truthvalue_loc (loc
, cond
);
543 bool can_infer_simple_equiv
544 = !(HONOR_SIGNED_ZEROS (op0
)
545 && real_zerop (op0
));
546 class edge_info
*edge_info
;
548 edge_info
= new class edge_info (true_edge
);
549 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
551 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
552 edge_info
->record_simple_equiv (op1
, op0
);
554 edge_info
= new class edge_info (false_edge
);
555 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
557 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
558 edge_info
->record_simple_equiv (op1
, op0
);
561 else if (TREE_CODE (op0
) == SSA_NAME
562 && (TREE_CODE (op1
) == SSA_NAME
563 || is_gimple_min_invariant (op1
)))
565 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
566 tree inverted
= invert_truthvalue_loc (loc
, cond
);
567 bool can_infer_simple_equiv
568 = !(HONOR_SIGNED_ZEROS (op1
)
569 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
570 class edge_info
*edge_info
;
572 edge_info
= new class edge_info (true_edge
);
573 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
575 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
576 edge_info
->record_simple_equiv (op0
, op1
);
578 edge_info
= new class edge_info (false_edge
);
579 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
581 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
582 edge_info
->record_simple_equiv (op0
, op1
);
588 class dom_jump_threader_simplifier
: public jump_threader_simplifier
591 dom_jump_threader_simplifier (vr_values
*v
,
592 avail_exprs_stack
*avails
)
593 : jump_threader_simplifier (v
), m_avail_exprs_stack (avails
) { }
596 tree
simplify (gimple
*, gimple
*, basic_block
, jt_state
*) override
;
597 avail_exprs_stack
*m_avail_exprs_stack
;
601 dom_jump_threader_simplifier::simplify (gimple
*stmt
,
606 /* First see if the conditional is in the hash table. */
607 tree cached_lhs
= m_avail_exprs_stack
->lookup_avail_expr (stmt
,
612 return jump_threader_simplifier::simplify (stmt
, within_stmt
, bb
, state
);
615 class dom_opt_dom_walker
: public dom_walker
618 dom_opt_dom_walker (cdi_direction direction
,
619 jump_threader
*threader
,
621 evrp_range_analyzer
*analyzer
,
622 const_and_copies
*const_and_copies
,
623 avail_exprs_stack
*avail_exprs_stack
)
624 : dom_walker (direction
, REACHABLE_BLOCKS
)
626 m_evrp_range_analyzer
= analyzer
;
628 m_dummy_cond
= gimple_build_cond (NE_EXPR
, integer_zero_node
,
629 integer_zero_node
, NULL
, NULL
);
630 m_const_and_copies
= const_and_copies
;
631 m_avail_exprs_stack
= avail_exprs_stack
;
632 m_threader
= threader
;
635 virtual edge
before_dom_children (basic_block
);
636 virtual void after_dom_children (basic_block
);
640 /* Unwindable equivalences, both const/copy and expression varieties. */
641 class const_and_copies
*m_const_and_copies
;
642 class avail_exprs_stack
*m_avail_exprs_stack
;
644 /* Dummy condition to avoid creating lots of throw away statements. */
647 /* Optimize a single statement within a basic block using the
648 various tables mantained by DOM. Returns the taken edge if
649 the statement is a conditional with a statically determined
651 edge
optimize_stmt (basic_block
, gimple_stmt_iterator
*, bool *);
654 void test_for_singularity (gimple
*, avail_exprs_stack
*);
656 jump_threader
*m_threader
;
657 evrp_range_analyzer
*m_evrp_range_analyzer
;
661 /* Jump threading, redundancy elimination and const/copy propagation.
663 This pass may expose new symbols that need to be renamed into SSA. For
664 every new symbol exposed, its corresponding bit will be set in
669 const pass_data pass_data_dominator
=
671 GIMPLE_PASS
, /* type */
673 OPTGROUP_NONE
, /* optinfo_flags */
674 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
675 ( PROP_cfg
| PROP_ssa
), /* properties_required */
676 0, /* properties_provided */
677 0, /* properties_destroyed */
678 0, /* todo_flags_start */
679 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
682 class pass_dominator
: public gimple_opt_pass
685 pass_dominator (gcc::context
*ctxt
)
686 : gimple_opt_pass (pass_data_dominator
, ctxt
),
687 may_peel_loop_headers_p (false)
690 /* opt_pass methods: */
691 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
692 void set_pass_param (unsigned int n
, bool param
)
695 may_peel_loop_headers_p
= param
;
697 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
698 virtual unsigned int execute (function
*);
701 /* This flag is used to prevent loops from being peeled repeatedly in jump
702 threading; it will be removed once we preserve loop structures throughout
703 the compilation -- we will be able to mark the affected loops directly in
704 jump threading, and avoid peeling them next time. */
705 bool may_peel_loop_headers_p
;
706 }; // class pass_dominator
709 pass_dominator::execute (function
*fun
)
711 memset (&opt_stats
, 0, sizeof (opt_stats
));
713 /* Create our hash tables. */
714 hash_table
<expr_elt_hasher
> *avail_exprs
715 = new hash_table
<expr_elt_hasher
> (1024);
716 class avail_exprs_stack
*avail_exprs_stack
717 = new class avail_exprs_stack (avail_exprs
);
718 class const_and_copies
*const_and_copies
= new class const_and_copies ();
719 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
720 need_noreturn_fixup
.create (0);
722 calculate_dominance_info (CDI_DOMINATORS
);
725 /* We need to know loop structures in order to avoid destroying them
726 in jump threading. Note that we still can e.g. thread through loop
727 headers to an exit edge, or through loop header to the loop body, assuming
728 that we update the loop info.
730 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
731 to several overly conservative bail-outs in jump threading, case
732 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
733 missing. We should improve jump threading in future then
734 LOOPS_HAVE_PREHEADERS won't be needed here. */
735 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
736 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
738 /* We need accurate information regarding back edges in the CFG
739 for jump threading; this may include back edges that are not part of
741 mark_dfs_back_edges ();
743 /* We want to create the edge info structures before the dominator walk
744 so that they'll be in place for the jump threader, particularly when
745 threading through a join block.
747 The conditions will be lazily updated with global equivalences as
748 we reach them during the dominator walk. */
750 FOR_EACH_BB_FN (bb
, fun
)
751 record_edge_info (bb
);
753 /* Recursively walk the dominator tree optimizing statements. */
754 evrp_range_analyzer
analyzer (true);
755 dom_jump_threader_simplifier
simplifier (&analyzer
, avail_exprs_stack
);
756 jt_state
state (const_and_copies
, avail_exprs_stack
, &analyzer
);
757 jump_threader
threader (&simplifier
, &state
);
758 dom_opt_dom_walker
walker (CDI_DOMINATORS
,
764 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
766 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
767 edge. When found, remove jump threads which contain any outgoing
768 edge from the affected block. */
771 FOR_EACH_BB_FN (bb
, fun
)
776 /* First see if there are any edges without EDGE_EXECUTABLE
779 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
781 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
788 /* If there were any such edges found, then remove jump threads
789 containing any edge leaving BB. */
791 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
792 threader
.remove_jump_threads_including (e
);
797 gimple_stmt_iterator gsi
;
799 FOR_EACH_BB_FN (bb
, fun
)
801 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
802 update_stmt_if_modified (gsi_stmt (gsi
));
806 /* If we exposed any new variables, go ahead and put them into
807 SSA form now, before we handle jump threading. This simplifies
808 interactions between rewriting of _DECL nodes into SSA form
809 and rewriting SSA_NAME nodes into SSA form after block
810 duplication and CFG manipulation. */
811 update_ssa (TODO_update_ssa
);
813 free_all_edge_infos ();
815 /* Thread jumps, creating duplicate blocks as needed. */
816 cfg_altered
|= threader
.thread_through_all_blocks (may_peel_loop_headers_p
);
819 free_dominance_info (CDI_DOMINATORS
);
821 /* Removal of statements may make some EH edges dead. Purge
822 such edges from the CFG as needed. */
823 if (!bitmap_empty_p (need_eh_cleanup
))
828 /* Jump threading may have created forwarder blocks from blocks
829 needing EH cleanup; the new successor of these blocks, which
830 has inherited from the original block, needs the cleanup.
831 Don't clear bits in the bitmap, as that can break the bitmap
833 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
835 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
838 while (single_succ_p (bb
)
839 && (single_succ_edge (bb
)->flags
840 & (EDGE_EH
|EDGE_DFS_BACK
)) == 0)
841 bb
= single_succ (bb
);
842 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
844 if ((unsigned) bb
->index
!= i
)
845 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
848 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
849 bitmap_clear (need_eh_cleanup
);
852 /* Fixup stmts that became noreturn calls. This may require splitting
853 blocks and thus isn't possible during the dominator walk or before
854 jump threading finished. Do this in reverse order so we don't
855 inadvertedly remove a stmt we want to fixup by visiting a dominating
856 now noreturn call first. */
857 while (!need_noreturn_fixup
.is_empty ())
859 gimple
*stmt
= need_noreturn_fixup
.pop ();
860 if (dump_file
&& dump_flags
& TDF_DETAILS
)
862 fprintf (dump_file
, "Fixing up noreturn call ");
863 print_gimple_stmt (dump_file
, stmt
, 0);
864 fprintf (dump_file
, "\n");
866 fixup_noreturn_call (stmt
);
869 statistics_counter_event (fun
, "Redundant expressions eliminated",
871 statistics_counter_event (fun
, "Constants propagated",
872 opt_stats
.num_const_prop
);
873 statistics_counter_event (fun
, "Copies propagated",
874 opt_stats
.num_copy_prop
);
876 /* Debugging dumps. */
877 if (dump_file
&& (dump_flags
& TDF_STATS
))
878 dump_dominator_optimization_stats (dump_file
, avail_exprs
);
880 loop_optimizer_finalize ();
882 /* Delete our main hashtable. */
886 /* Free asserted bitmaps and stacks. */
887 BITMAP_FREE (need_eh_cleanup
);
888 need_noreturn_fixup
.release ();
889 delete avail_exprs_stack
;
890 delete const_and_copies
;
898 make_pass_dominator (gcc::context
*ctxt
)
900 return new pass_dominator (ctxt
);
903 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
906 dom_valueize (tree t
)
908 if (TREE_CODE (t
) == SSA_NAME
)
910 tree tem
= SSA_NAME_VALUE (t
);
917 /* We have just found an equivalence for LHS on an edge E.
918 Look backwards to other uses of LHS and see if we can derive
919 additional equivalences that are valid on edge E. */
921 back_propagate_equivalences (tree lhs
, edge e
,
922 class const_and_copies
*const_and_copies
)
925 imm_use_iterator iter
;
927 basic_block dest
= e
->dest
;
929 /* Iterate over the uses of LHS to see if any dominate E->dest.
930 If so, they may create useful equivalences too.
932 ??? If the code gets re-organized to a worklist to catch more
933 indirect opportunities and it is made to handle PHIs then this
934 should only consider use_stmts in basic-blocks we have already visited. */
935 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
937 gimple
*use_stmt
= USE_STMT (use_p
);
939 /* Often the use is in DEST, which we trivially know we can't use.
940 This is cheaper than the dominator set tests below. */
941 if (dest
== gimple_bb (use_stmt
))
944 /* Filter out statements that can never produce a useful
946 tree lhs2
= gimple_get_lhs (use_stmt
);
947 if (!lhs2
|| TREE_CODE (lhs2
) != SSA_NAME
)
950 /* Profiling has shown the domination tests here can be fairly
951 expensive. We get significant improvements by building the
952 set of blocks that dominate BB. We can then just test
953 for set membership below.
955 We also initialize the set lazily since often the only uses
956 are going to be in the same block as DEST. */
959 domby
= BITMAP_ALLOC (NULL
);
960 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
963 bitmap_set_bit (domby
, bb
->index
);
964 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
968 /* This tests if USE_STMT does not dominate DEST. */
969 if (!bitmap_bit_p (domby
, gimple_bb (use_stmt
)->index
))
972 /* At this point USE_STMT dominates DEST and may result in a
973 useful equivalence. Try to simplify its RHS to a constant
975 tree res
= gimple_fold_stmt_to_constant_1 (use_stmt
, dom_valueize
,
976 no_follow_ssa_edges
);
977 if (res
&& (TREE_CODE (res
) == SSA_NAME
|| is_gimple_min_invariant (res
)))
978 record_equality (lhs2
, res
, const_and_copies
);
985 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
986 by traversing edge E (which are cached in E->aux).
988 Callers are responsible for managing the unwinding markers. */
990 record_temporary_equivalences (edge e
,
991 class const_and_copies
*const_and_copies
,
992 class avail_exprs_stack
*avail_exprs_stack
)
995 class edge_info
*edge_info
= (class edge_info
*) e
->aux
;
997 /* If we have info associated with this edge, record it into
998 our equivalence tables. */
1001 cond_equivalence
*eq
;
1002 /* If we have 0 = COND or 1 = COND equivalences, record them
1003 into our expression hash tables. */
1004 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
1005 avail_exprs_stack
->record_cond (eq
);
1007 edge_info::equiv_pair
*seq
;
1008 for (i
= 0; edge_info
->simple_equivalences
.iterate (i
, &seq
); ++i
)
1010 tree lhs
= seq
->first
;
1011 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
)
1014 /* Record the simple NAME = VALUE equivalence. */
1015 tree rhs
= seq
->second
;
1017 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
1018 cheaper to compute than the other, then set up the equivalence
1019 such that we replace the expensive one with the cheap one.
1021 If they are the same cost to compute, then do not record
1023 if (TREE_CODE (lhs
) == SSA_NAME
&& TREE_CODE (rhs
) == SSA_NAME
)
1025 gimple
*rhs_def
= SSA_NAME_DEF_STMT (rhs
);
1026 int rhs_cost
= estimate_num_insns (rhs_def
, &eni_size_weights
);
1028 gimple
*lhs_def
= SSA_NAME_DEF_STMT (lhs
);
1029 int lhs_cost
= estimate_num_insns (lhs_def
, &eni_size_weights
);
1031 if (rhs_cost
> lhs_cost
)
1032 record_equality (rhs
, lhs
, const_and_copies
);
1033 else if (rhs_cost
< lhs_cost
)
1034 record_equality (lhs
, rhs
, const_and_copies
);
1037 record_equality (lhs
, rhs
, const_and_copies
);
1040 /* Any equivalence found for LHS may result in additional
1041 equivalences for other uses of LHS that we have already
1043 back_propagate_equivalences (lhs
, e
, const_and_copies
);
1048 /* PHI nodes can create equivalences too.
1050 Ignoring any alternatives which are the same as the result, if
1051 all the alternatives are equal, then the PHI node creates an
1055 record_equivalences_from_phis (basic_block bb
)
1059 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1061 gphi
*phi
= gsi
.phi ();
1063 /* We might eliminate the PHI, so advance GSI now. */
1066 tree lhs
= gimple_phi_result (phi
);
1070 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1072 tree t
= gimple_phi_arg_def (phi
, i
);
1074 /* Ignore alternatives which are the same as our LHS. Since
1075 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1076 can simply compare pointers. */
1080 /* If the associated edge is not marked as executable, then it
1082 if ((gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_EXECUTABLE
) == 0)
1085 t
= dom_valueize (t
);
1087 /* If T is an SSA_NAME and its associated edge is a backedge,
1088 then quit as we cannot utilize this equivalence. */
1089 if (TREE_CODE (t
) == SSA_NAME
1090 && (gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_DFS_BACK
))
1093 /* If we have not processed an alternative yet, then set
1094 RHS to this alternative. */
1097 /* If we have processed an alternative (stored in RHS), then
1098 see if it is equal to this one. If it isn't, then stop
1100 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1104 /* If we had no interesting alternatives, then all the RHS alternatives
1105 must have been the same as LHS. */
1109 /* If we managed to iterate through each PHI alternative without
1110 breaking out of the loop, then we have a PHI which may create
1111 a useful equivalence. We do not need to record unwind data for
1112 this, since this is a true assignment and not an equivalence
1113 inferred from a comparison. All uses of this ssa name are dominated
1114 by this assignment, so unwinding just costs time and space. */
1115 if (i
== gimple_phi_num_args (phi
))
1117 if (may_propagate_copy (lhs
, rhs
))
1118 set_ssa_name_value (lhs
, rhs
);
1119 else if (virtual_operand_p (lhs
))
1122 imm_use_iterator iter
;
1123 use_operand_p use_p
;
1124 /* For virtual operands we have to propagate into all uses as
1125 otherwise we will create overlapping life-ranges. */
1126 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
1127 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
1128 SET_USE (use_p
, rhs
);
1129 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1130 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
) = 1;
1131 gimple_stmt_iterator tmp_gsi
= gsi_for_stmt (phi
);
1132 remove_phi_node (&tmp_gsi
, true);
1138 /* Record any equivalences created by the incoming edge to BB into
1139 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
1140 incoming edge, then no equivalence is created. */
1143 record_equivalences_from_incoming_edge (basic_block bb
,
1144 class const_and_copies
*const_and_copies
,
1145 class avail_exprs_stack
*avail_exprs_stack
)
1150 /* If our parent block ended with a control statement, then we may be
1151 able to record some equivalences based on which outgoing edge from
1152 the parent was followed. */
1153 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1155 e
= single_pred_edge_ignoring_loop_edges (bb
, true);
1157 /* If we had a single incoming edge from our parent block, then enter
1158 any data associated with the edge into our tables. */
1159 if (e
&& e
->src
== parent
)
1160 record_temporary_equivalences (e
, const_and_copies
, avail_exprs_stack
);
1163 /* Dump statistics for the hash table HTAB. */
1166 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
1168 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1169 (long) htab
.size (),
1170 (long) htab
.elements (),
1171 htab
.collisions ());
1174 /* Dump SSA statistics on FILE. */
1177 dump_dominator_optimization_stats (FILE *file
,
1178 hash_table
<expr_elt_hasher
> *avail_exprs
)
1180 fprintf (file
, "Total number of statements: %6ld\n\n",
1181 opt_stats
.num_stmts
);
1182 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1183 opt_stats
.num_exprs_considered
);
1185 fprintf (file
, "\nHash table statistics:\n");
1187 fprintf (file
, " avail_exprs: ");
1188 htab_statistics (file
, *avail_exprs
);
1192 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1193 This constrains the cases in which we may treat this as assignment. */
1196 record_equality (tree x
, tree y
, class const_and_copies
*const_and_copies
)
1198 tree prev_x
= NULL
, prev_y
= NULL
;
1200 if (tree_swap_operands_p (x
, y
))
1203 /* Most of the time tree_swap_operands_p does what we want. But there
1204 are cases where we know one operand is better for copy propagation than
1205 the other. Given no other code cares about ordering of equality
1206 comparison operators for that purpose, we just handle the special cases
1208 if (TREE_CODE (x
) == SSA_NAME
&& TREE_CODE (y
) == SSA_NAME
)
1210 /* If one operand is a single use operand, then make it
1211 X. This will preserve its single use properly and if this
1212 conditional is eliminated, the computation of X can be
1213 eliminated as well. */
1214 if (has_single_use (y
) && ! has_single_use (x
))
1217 if (TREE_CODE (x
) == SSA_NAME
)
1218 prev_x
= SSA_NAME_VALUE (x
);
1219 if (TREE_CODE (y
) == SSA_NAME
)
1220 prev_y
= SSA_NAME_VALUE (y
);
1222 /* If one of the previous values is invariant, or invariant in more loops
1223 (by depth), then use that.
1224 Otherwise it doesn't matter which value we choose, just so
1225 long as we canonicalize on one value. */
1226 if (is_gimple_min_invariant (y
))
1228 else if (is_gimple_min_invariant (x
))
1229 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1230 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1231 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1235 /* After the swapping, we must have one SSA_NAME. */
1236 if (TREE_CODE (x
) != SSA_NAME
)
1239 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1240 variable compared against zero. If we're honoring signed zeros,
1241 then we cannot record this value unless we know that the value is
1243 if (HONOR_SIGNED_ZEROS (x
)
1244 && (TREE_CODE (y
) != REAL_CST
1245 || real_equal (&dconst0
, &TREE_REAL_CST (y
))))
1248 const_and_copies
->record_const_or_copy (x
, y
, prev_x
);
1251 /* Returns true when STMT is a simple iv increment. It detects the
1252 following situation:
1254 i_1 = phi (..., i_k)
1256 i_j = i_{j-1} for each j : 2 <= j <= k-1
1258 i_k = i_{k-1} +/- ... */
1261 simple_iv_increment_p (gimple
*stmt
)
1263 enum tree_code code
;
1268 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1271 lhs
= gimple_assign_lhs (stmt
);
1272 if (TREE_CODE (lhs
) != SSA_NAME
)
1275 code
= gimple_assign_rhs_code (stmt
);
1276 if (code
!= PLUS_EXPR
1277 && code
!= MINUS_EXPR
1278 && code
!= POINTER_PLUS_EXPR
)
1281 preinc
= gimple_assign_rhs1 (stmt
);
1282 if (TREE_CODE (preinc
) != SSA_NAME
)
1285 phi
= SSA_NAME_DEF_STMT (preinc
);
1286 while (gimple_code (phi
) != GIMPLE_PHI
)
1288 /* Follow trivial copies, but not the DEF used in a back edge,
1289 so that we don't prevent coalescing. */
1290 if (!gimple_assign_ssa_name_copy_p (phi
))
1292 preinc
= gimple_assign_rhs1 (phi
);
1293 phi
= SSA_NAME_DEF_STMT (preinc
);
1296 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1297 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1303 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1304 successors of BB. */
1307 cprop_into_successor_phis (basic_block bb
,
1308 class const_and_copies
*const_and_copies
)
1313 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1318 /* If this is an abnormal edge, then we do not want to copy propagate
1319 into the PHI alternative associated with this edge. */
1320 if (e
->flags
& EDGE_ABNORMAL
)
1323 gsi
= gsi_start_phis (e
->dest
);
1324 if (gsi_end_p (gsi
))
1327 /* We may have an equivalence associated with this edge. While
1328 we cannot propagate it into non-dominated blocks, we can
1329 propagate them into PHIs in non-dominated blocks. */
1331 /* Push the unwind marker so we can reset the const and copies
1332 table back to its original state after processing this edge. */
1333 const_and_copies
->push_marker ();
1335 /* Extract and record any simple NAME = VALUE equivalences.
1337 Don't bother with [01] = COND equivalences, they're not useful
1339 class edge_info
*edge_info
= (class edge_info
*) e
->aux
;
1343 edge_info::equiv_pair
*seq
;
1344 for (int i
= 0; edge_info
->simple_equivalences
.iterate (i
, &seq
); ++i
)
1346 tree lhs
= seq
->first
;
1347 tree rhs
= seq
->second
;
1349 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1350 const_and_copies
->record_const_or_copy (lhs
, rhs
);
1356 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1359 use_operand_p orig_p
;
1361 gphi
*phi
= gsi
.phi ();
1363 /* The alternative may be associated with a constant, so verify
1364 it is an SSA_NAME before doing anything with it. */
1365 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1366 orig_val
= get_use_from_ptr (orig_p
);
1367 if (TREE_CODE (orig_val
) != SSA_NAME
)
1370 /* If we have *ORIG_P in our constant/copy table, then replace
1371 ORIG_P with its value in our constant/copy table. */
1372 new_val
= SSA_NAME_VALUE (orig_val
);
1374 && new_val
!= orig_val
1375 && may_propagate_copy (orig_val
, new_val
))
1376 propagate_value (orig_p
, new_val
);
1379 const_and_copies
->pop_to_marker ();
1384 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1386 gimple_stmt_iterator gsi
;
1388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1389 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1391 m_evrp_range_analyzer
->enter (bb
);
1393 /* Push a marker on the stacks of local information so that we know how
1394 far to unwind when we finalize this block. */
1395 m_avail_exprs_stack
->push_marker ();
1396 m_const_and_copies
->push_marker ();
1398 record_equivalences_from_incoming_edge (bb
, m_const_and_copies
,
1399 m_avail_exprs_stack
);
1401 /* PHI nodes can create equivalences too. */
1402 record_equivalences_from_phis (bb
);
1404 /* Create equivalences from redundant PHIs. PHIs are only truly
1405 redundant when they exist in the same block, so push another
1406 marker and unwind right afterwards. */
1407 m_avail_exprs_stack
->push_marker ();
1408 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1409 eliminate_redundant_computations (&gsi
, m_const_and_copies
,
1410 m_avail_exprs_stack
);
1411 m_avail_exprs_stack
->pop_to_marker ();
1413 edge taken_edge
= NULL
;
1414 /* Initialize visited flag ahead of us, it has undefined state on
1416 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1417 gimple_set_visited (gsi_stmt (gsi
), false);
1418 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1420 /* Do not optimize a stmt twice, substitution might end up with
1421 _3 = _3 which is not valid. */
1422 if (gimple_visited_p (gsi_stmt (gsi
)))
1428 m_state
->record_ranges_from_stmt (gsi_stmt (gsi
), false);
1429 bool removed_p
= false;
1430 taken_edge
= this->optimize_stmt (bb
, &gsi
, &removed_p
);
1432 gimple_set_visited (gsi_stmt (gsi
), true);
1434 /* Go back and visit stmts inserted by folding after substituting
1435 into the stmt at gsi. */
1436 if (gsi_end_p (gsi
))
1438 gcc_checking_assert (removed_p
);
1439 gsi
= gsi_last_bb (bb
);
1440 while (!gsi_end_p (gsi
) && !gimple_visited_p (gsi_stmt (gsi
)))
1449 while (!gsi_end_p (gsi
) && !gimple_visited_p (gsi_stmt (gsi
)));
1451 if (gsi_end_p (gsi
))
1452 gsi
= gsi_start_bb (bb
);
1457 /* Now prepare to process dominated blocks. */
1458 record_edge_info (bb
);
1459 cprop_into_successor_phis (bb
, m_const_and_copies
);
1460 if (taken_edge
&& !dbg_cnt (dom_unreachable_edges
))
1466 /* We have finished processing the dominator children of BB, perform
1467 any finalization actions in preparation for leaving this node in
1468 the dominator tree. */
1471 dom_opt_dom_walker::after_dom_children (basic_block bb
)
1473 m_threader
->thread_outgoing_edges (bb
);
1474 m_avail_exprs_stack
->pop_to_marker ();
1475 m_const_and_copies
->pop_to_marker ();
1476 m_evrp_range_analyzer
->leave (bb
);
1479 /* Search for redundant computations in STMT. If any are found, then
1480 replace them with the variable holding the result of the computation.
1482 If safe, record this expression into AVAIL_EXPRS_STACK and
1483 CONST_AND_COPIES. */
1486 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
,
1487 class const_and_copies
*const_and_copies
,
1488 class avail_exprs_stack
*avail_exprs_stack
)
1494 bool assigns_var_p
= false;
1496 gimple
*stmt
= gsi_stmt (*gsi
);
1498 if (gimple_code (stmt
) == GIMPLE_PHI
)
1499 def
= gimple_phi_result (stmt
);
1501 def
= gimple_get_lhs (stmt
);
1503 /* Certain expressions on the RHS can be optimized away, but cannot
1504 themselves be entered into the hash tables. */
1506 || TREE_CODE (def
) != SSA_NAME
1507 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1508 || gimple_vdef (stmt
)
1509 /* Do not record equivalences for increments of ivs. This would create
1510 overlapping live ranges for a very questionable gain. */
1511 || simple_iv_increment_p (stmt
))
1514 /* Check if the expression has been computed before. */
1515 cached_lhs
= avail_exprs_stack
->lookup_avail_expr (stmt
, insert
, true);
1517 opt_stats
.num_exprs_considered
++;
1519 /* Get the type of the expression we are trying to optimize. */
1520 if (is_gimple_assign (stmt
))
1522 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1523 assigns_var_p
= true;
1525 else if (gimple_code (stmt
) == GIMPLE_COND
)
1526 expr_type
= boolean_type_node
;
1527 else if (is_gimple_call (stmt
))
1529 gcc_assert (gimple_call_lhs (stmt
));
1530 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1531 assigns_var_p
= true;
1533 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1534 expr_type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
1535 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1536 /* We can't propagate into a phi, so the logic below doesn't apply.
1537 Instead record an equivalence between the cached LHS and the
1538 PHI result of this statement, provided they are in the same block.
1539 This should be sufficient to kill the redundant phi. */
1541 if (def
&& cached_lhs
)
1542 const_and_copies
->record_const_or_copy (def
, cached_lhs
);
1551 /* It is safe to ignore types here since we have already done
1552 type checking in the hashing and equality routines. In fact
1553 type checking here merely gets in the way of constant
1554 propagation. Also, make sure that it is safe to propagate
1555 CACHED_LHS into the expression in STMT. */
1556 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1558 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1559 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1561 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1562 || is_gimple_min_invariant (cached_lhs
));
1564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1566 fprintf (dump_file
, " Replaced redundant expr '");
1567 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1568 fprintf (dump_file
, "' with '");
1569 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1570 fprintf (dump_file
, "'\n");
1576 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1577 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1579 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1581 /* Since it is always necessary to mark the result as modified,
1582 perhaps we should move this into propagate_tree_value_into_stmt
1584 gimple_set_modified (gsi_stmt (*gsi
), true);
1588 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1589 the available expressions table or the const_and_copies table.
1590 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1592 We handle only very simple copy equivalences here. The heavy
1593 lifing is done by eliminate_redundant_computations. */
1596 record_equivalences_from_stmt (gimple
*stmt
, int may_optimize_p
,
1597 class avail_exprs_stack
*avail_exprs_stack
)
1600 enum tree_code lhs_code
;
1602 gcc_assert (is_gimple_assign (stmt
));
1604 lhs
= gimple_assign_lhs (stmt
);
1605 lhs_code
= TREE_CODE (lhs
);
1607 if (lhs_code
== SSA_NAME
1608 && gimple_assign_single_p (stmt
))
1610 tree rhs
= gimple_assign_rhs1 (stmt
);
1612 /* If the RHS of the assignment is a constant or another variable that
1613 may be propagated, register it in the CONST_AND_COPIES table. We
1614 do not need to record unwind data for this, since this is a true
1615 assignment and not an equivalence inferred from a comparison. All
1616 uses of this ssa name are dominated by this assignment, so unwinding
1617 just costs time and space. */
1619 && (TREE_CODE (rhs
) == SSA_NAME
1620 || is_gimple_min_invariant (rhs
)))
1622 rhs
= dom_valueize (rhs
);
1624 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1626 fprintf (dump_file
, "==== ASGN ");
1627 print_generic_expr (dump_file
, lhs
);
1628 fprintf (dump_file
, " = ");
1629 print_generic_expr (dump_file
, rhs
);
1630 fprintf (dump_file
, "\n");
1633 set_ssa_name_value (lhs
, rhs
);
1637 /* Make sure we can propagate &x + CST. */
1638 if (lhs_code
== SSA_NAME
1639 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1640 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
1641 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
1643 tree op0
= gimple_assign_rhs1 (stmt
);
1644 tree op1
= gimple_assign_rhs2 (stmt
);
1646 = build1 (ADDR_EXPR
, TREE_TYPE (op0
),
1647 fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (op0
)),
1648 unshare_expr (op0
), fold_convert (ptr_type_node
,
1650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1652 fprintf (dump_file
, "==== ASGN ");
1653 print_generic_expr (dump_file
, lhs
);
1654 fprintf (dump_file
, " = ");
1655 print_generic_expr (dump_file
, new_rhs
);
1656 fprintf (dump_file
, "\n");
1659 set_ssa_name_value (lhs
, new_rhs
);
1662 /* A memory store, even an aliased store, creates a useful
1663 equivalence. By exchanging the LHS and RHS, creating suitable
1664 vops and recording the result in the available expression table,
1665 we may be able to expose more redundant loads. */
1666 if (!gimple_has_volatile_ops (stmt
)
1667 && gimple_references_memory_p (stmt
)
1668 && gimple_assign_single_p (stmt
)
1669 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1670 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1671 && !is_gimple_reg (lhs
))
1673 tree rhs
= gimple_assign_rhs1 (stmt
);
1676 /* Build a new statement with the RHS and LHS exchanged. */
1677 if (TREE_CODE (rhs
) == SSA_NAME
)
1679 /* NOTE tuples. The call to gimple_build_assign below replaced
1680 a call to build_gimple_modify_stmt, which did not set the
1681 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1682 may cause an SSA validation failure, as the LHS may be a
1683 default-initialized name and should have no definition. I'm
1684 a bit dubious of this, as the artificial statement that we
1685 generate here may in fact be ill-formed, but it is simply
1686 used as an internal device in this pass, and never becomes
1688 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1689 new_stmt
= gimple_build_assign (rhs
, lhs
);
1690 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1693 new_stmt
= gimple_build_assign (rhs
, lhs
);
1695 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
1697 /* Finally enter the statement into the available expression
1699 avail_exprs_stack
->lookup_avail_expr (new_stmt
, true, true);
1703 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1704 CONST_AND_COPIES. */
1707 cprop_operand (gimple
*stmt
, use_operand_p op_p
, vr_values
*vr_values
)
1710 tree op
= USE_FROM_PTR (op_p
);
1712 /* If the operand has a known constant value or it is known to be a
1713 copy of some other variable, use the value or copy stored in
1714 CONST_AND_COPIES. */
1715 val
= SSA_NAME_VALUE (op
);
1717 val
= vr_values
->op_with_constant_singleton_value_range (op
);
1719 if (val
&& val
!= op
)
1721 /* Do not replace hard register operands in asm statements. */
1722 if (gimple_code (stmt
) == GIMPLE_ASM
1723 && !may_propagate_copy_into_asm (op
))
1726 /* Certain operands are not allowed to be copy propagated due
1727 to their interaction with exception handling and some GCC
1729 if (!may_propagate_copy (op
, val
))
1732 /* Do not propagate copies into BIVs.
1733 See PR23821 and PR62217 for how this can disturb IV and
1734 number of iteration analysis. */
1735 if (TREE_CODE (val
) != INTEGER_CST
)
1737 gimple
*def
= SSA_NAME_DEF_STMT (op
);
1738 if (gimple_code (def
) == GIMPLE_PHI
1739 && gimple_bb (def
)->loop_father
->header
== gimple_bb (def
))
1744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1746 fprintf (dump_file
, " Replaced '");
1747 print_generic_expr (dump_file
, op
, dump_flags
);
1748 fprintf (dump_file
, "' with %s '",
1749 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1750 print_generic_expr (dump_file
, val
, dump_flags
);
1751 fprintf (dump_file
, "'\n");
1754 if (TREE_CODE (val
) != SSA_NAME
)
1755 opt_stats
.num_const_prop
++;
1757 opt_stats
.num_copy_prop
++;
1759 propagate_value (op_p
, val
);
1761 /* And note that we modified this statement. This is now
1762 safe, even if we changed virtual operands since we will
1763 rescan the statement and rewrite its operands again. */
1764 gimple_set_modified (stmt
, true);
1768 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1769 known value for that SSA_NAME (or NULL if no value is known).
1771 Propagate values from CONST_AND_COPIES into the uses, vuses and
1772 vdef_ops of STMT. */
1775 cprop_into_stmt (gimple
*stmt
, vr_values
*vr_values
)
1779 tree last_copy_propagated_op
= NULL
;
1781 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
1783 tree old_op
= USE_FROM_PTR (op_p
);
1785 /* If we have A = B and B = A in the copy propagation tables
1786 (due to an equality comparison), avoid substituting B for A
1787 then A for B in the trivially discovered cases. This allows
1788 optimization of statements were A and B appear as input
1790 if (old_op
!= last_copy_propagated_op
)
1792 cprop_operand (stmt
, op_p
, vr_values
);
1794 tree new_op
= USE_FROM_PTR (op_p
);
1795 if (new_op
!= old_op
&& TREE_CODE (new_op
) == SSA_NAME
)
1796 last_copy_propagated_op
= new_op
;
1801 /* If STMT contains a relational test, try to convert it into an
1802 equality test if there is only a single value which can ever
1805 For example, if the expression hash table contains:
1809 And we have a test within statement of i >= 1, then we can safely
1810 rewrite the test as i == 1 since there only a single value where
1813 This is similar to code in VRP. */
1816 dom_opt_dom_walker::test_for_singularity (gimple
*stmt
,
1817 avail_exprs_stack
*avail_exprs_stack
)
1819 /* We want to support gimple conditionals as well as assignments
1820 where the RHS contains a conditional. */
1821 if (is_gimple_assign (stmt
) || gimple_code (stmt
) == GIMPLE_COND
)
1823 enum tree_code code
= ERROR_MARK
;
1826 /* Extract the condition of interest from both forms we support. */
1827 if (is_gimple_assign (stmt
))
1829 code
= gimple_assign_rhs_code (stmt
);
1830 lhs
= gimple_assign_rhs1 (stmt
);
1831 rhs
= gimple_assign_rhs2 (stmt
);
1833 else if (gimple_code (stmt
) == GIMPLE_COND
)
1835 code
= gimple_cond_code (as_a
<gcond
*> (stmt
));
1836 lhs
= gimple_cond_lhs (as_a
<gcond
*> (stmt
));
1837 rhs
= gimple_cond_rhs (as_a
<gcond
*> (stmt
));
1840 /* We're looking for a relational test using LE/GE. Also note we can
1841 canonicalize LT/GT tests against constants into LE/GT tests. */
1842 if (code
== LE_EXPR
|| code
== GE_EXPR
1843 || ((code
== LT_EXPR
|| code
== GT_EXPR
)
1844 && TREE_CODE (rhs
) == INTEGER_CST
))
1846 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */
1847 if (code
== LT_EXPR
)
1848 rhs
= fold_build2 (MINUS_EXPR
, TREE_TYPE (rhs
),
1849 rhs
, build_int_cst (TREE_TYPE (rhs
), 1));
1851 if (code
== GT_EXPR
)
1852 rhs
= fold_build2 (PLUS_EXPR
, TREE_TYPE (rhs
),
1853 rhs
, build_int_cst (TREE_TYPE (rhs
), 1));
1855 /* Determine the code we want to check for in the hash table. */
1856 enum tree_code test_code
;
1857 if (code
== GE_EXPR
|| code
== GT_EXPR
)
1858 test_code
= LE_EXPR
;
1860 test_code
= GE_EXPR
;
1862 /* Update the dummy statement so we can query the hash tables. */
1863 gimple_cond_set_code (m_dummy_cond
, test_code
);
1864 gimple_cond_set_lhs (m_dummy_cond
, lhs
);
1865 gimple_cond_set_rhs (m_dummy_cond
, rhs
);
1867 = avail_exprs_stack
->lookup_avail_expr (m_dummy_cond
,
1870 /* If the lookup returned 1 (true), then the expression we
1871 queried was in the hash table. As a result there is only
1872 one value that makes the original conditional true. Update
1873 STMT accordingly. */
1874 if (cached_lhs
&& integer_onep (cached_lhs
))
1876 if (is_gimple_assign (stmt
))
1878 gimple_assign_set_rhs_code (stmt
, EQ_EXPR
);
1879 gimple_assign_set_rhs2 (stmt
, rhs
);
1880 gimple_set_modified (stmt
, true);
1884 gimple_set_modified (stmt
, true);
1885 gimple_cond_set_code (as_a
<gcond
*> (stmt
), EQ_EXPR
);
1886 gimple_cond_set_rhs (as_a
<gcond
*> (stmt
), rhs
);
1887 gimple_set_modified (stmt
, true);
1894 /* If STMT is a comparison of two uniform vectors reduce it to a comparison
1895 of scalar objects, otherwise leave STMT unchanged. */
1898 reduce_vector_comparison_to_scalar_comparison (gimple
*stmt
)
1900 if (gimple_code (stmt
) == GIMPLE_COND
)
1902 tree lhs
= gimple_cond_lhs (stmt
);
1903 tree rhs
= gimple_cond_rhs (stmt
);
1905 /* We may have a vector comparison where both arms are uniform
1906 vectors. If so, we can simplify the vector comparison down
1907 to a scalar comparison. */
1908 if (TREE_CODE (TREE_TYPE (lhs
)) == VECTOR_TYPE
1909 && TREE_CODE (TREE_TYPE (rhs
)) == VECTOR_TYPE
)
1911 /* If either operand is an SSA_NAME, then look back to its
1912 defining statement to try and get at a suitable source. */
1913 if (TREE_CODE (rhs
) == SSA_NAME
)
1915 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
);
1916 if (gimple_assign_single_p (def_stmt
))
1917 rhs
= gimple_assign_rhs1 (def_stmt
);
1920 if (TREE_CODE (lhs
) == SSA_NAME
)
1922 gimple
*def_stmt
= SSA_NAME_DEF_STMT (lhs
);
1923 if (gimple_assign_single_p (def_stmt
))
1924 lhs
= gimple_assign_rhs1 (def_stmt
);
1927 /* Now see if they are both uniform vectors and if so replace
1928 the vector comparison with a scalar comparison. */
1929 tree rhs_elem
= rhs
? uniform_vector_p (rhs
) : NULL_TREE
;
1930 tree lhs_elem
= lhs
? uniform_vector_p (lhs
) : NULL_TREE
;
1931 if (rhs_elem
&& lhs_elem
)
1933 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1935 fprintf (dump_file
, "Reducing vector comparison: ");
1936 print_gimple_stmt (dump_file
, stmt
, 0);
1939 gimple_cond_set_rhs (as_a
<gcond
*>(stmt
), rhs_elem
);
1940 gimple_cond_set_lhs (as_a
<gcond
*>(stmt
), lhs_elem
);
1941 gimple_set_modified (stmt
, true);
1943 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1945 fprintf (dump_file
, "To scalar equivalent: ");
1946 print_gimple_stmt (dump_file
, stmt
, 0);
1947 fprintf (dump_file
, "\n");
1954 /* Optimize the statement in block BB pointed to by iterator SI.
1956 We try to perform some simplistic global redundancy elimination and
1957 constant propagation:
1959 1- To detect global redundancy, we keep track of expressions that have
1960 been computed in this block and its dominators. If we find that the
1961 same expression is computed more than once, we eliminate repeated
1962 computations by using the target of the first one.
1964 2- Constant values and copy assignments. This is used to do very
1965 simplistic constant and copy propagation. When a constant or copy
1966 assignment is found, we map the value on the RHS of the assignment to
1967 the variable in the LHS in the CONST_AND_COPIES table.
1969 3- Very simple redundant store elimination is performed.
1971 4- We can simplify a condition to a constant or from a relational
1972 condition to an equality condition. */
1975 dom_opt_dom_walker::optimize_stmt (basic_block bb
, gimple_stmt_iterator
*si
,
1978 gimple
*stmt
, *old_stmt
;
1979 bool may_optimize_p
;
1980 bool modified_p
= false;
1984 old_stmt
= stmt
= gsi_stmt (*si
);
1985 was_noreturn
= is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
);
1987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1989 fprintf (dump_file
, "Optimizing statement ");
1990 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1993 update_stmt_if_modified (stmt
);
1994 opt_stats
.num_stmts
++;
1996 /* STMT may be a comparison of uniform vectors that we can simplify
1997 down to a comparison of scalars. Do that transformation first
1998 so that all the scalar optimizations from here onward apply. */
1999 reduce_vector_comparison_to_scalar_comparison (stmt
);
2001 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2002 cprop_into_stmt (stmt
, m_evrp_range_analyzer
);
2004 /* If the statement has been modified with constant replacements,
2005 fold its RHS before checking for redundant computations. */
2006 if (gimple_modified_p (stmt
))
2010 /* Try to fold the statement making sure that STMT is kept
2014 stmt
= gsi_stmt (*si
);
2015 gimple_set_modified (stmt
, true);
2017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2019 fprintf (dump_file
, " Folded to: ");
2020 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2024 /* We only need to consider cases that can yield a gimple operand. */
2025 if (gimple_assign_single_p (stmt
))
2026 rhs
= gimple_assign_rhs1 (stmt
);
2027 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
2028 rhs
= gimple_goto_dest (stmt
);
2029 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
2030 /* This should never be an ADDR_EXPR. */
2031 rhs
= gimple_switch_index (swtch_stmt
);
2033 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
2034 recompute_tree_invariant_for_addr_expr (rhs
);
2036 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2037 even if fold_stmt updated the stmt already and thus cleared
2038 gimple_modified_p flag on it. */
2042 /* Check for redundant computations. Do this optimization only
2043 for assignments that have no volatile ops and conditionals. */
2044 may_optimize_p
= (!gimple_has_side_effects (stmt
)
2045 && (is_gimple_assign (stmt
)
2046 || (is_gimple_call (stmt
)
2047 && gimple_call_lhs (stmt
) != NULL_TREE
)
2048 || gimple_code (stmt
) == GIMPLE_COND
2049 || gimple_code (stmt
) == GIMPLE_SWITCH
));
2053 if (gimple_code (stmt
) == GIMPLE_CALL
)
2055 /* Resolve __builtin_constant_p. If it hasn't been
2056 folded to integer_one_node by now, it's fairly
2057 certain that the value simply isn't constant. */
2058 tree callee
= gimple_call_fndecl (stmt
);
2060 && fndecl_built_in_p (callee
, BUILT_IN_CONSTANT_P
))
2062 propagate_tree_value_into_stmt (si
, integer_zero_node
);
2063 stmt
= gsi_stmt (*si
);
2067 if (gimple_code (stmt
) == GIMPLE_COND
)
2069 tree lhs
= gimple_cond_lhs (stmt
);
2070 tree rhs
= gimple_cond_rhs (stmt
);
2072 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
2073 then this conditional is computable at compile time. We can just
2074 shove either 0 or 1 into the LHS, mark the statement as modified
2075 and all the right things will just happen below.
2077 Note this would apply to any case where LHS has a range
2078 narrower than its type implies and RHS is outside that
2079 narrower range. Future work. */
2080 if (TREE_CODE (lhs
) == SSA_NAME
2081 && ssa_name_has_boolean_range (lhs
)
2082 && TREE_CODE (rhs
) == INTEGER_CST
2083 && ! (integer_zerop (rhs
) || integer_onep (rhs
)))
2085 gimple_cond_set_lhs (as_a
<gcond
*> (stmt
),
2086 fold_convert (TREE_TYPE (lhs
),
2087 integer_zero_node
));
2088 gimple_set_modified (stmt
, true);
2090 else if (TREE_CODE (lhs
) == SSA_NAME
)
2092 /* Exploiting EVRP data is not yet fully integrated into DOM
2093 but we need to do something for this case to avoid regressing
2094 udr4.f90 and new1.C which have unexecutable blocks with
2095 undefined behavior that get diagnosed if they're left in the
2096 IL because we've attached range information to new
2098 update_stmt_if_modified (stmt
);
2099 edge taken_edge
= NULL
;
2100 m_evrp_range_analyzer
->vrp_visit_cond_stmt
2101 (as_a
<gcond
*> (stmt
), &taken_edge
);
2104 if (taken_edge
->flags
& EDGE_TRUE_VALUE
)
2105 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
2106 else if (taken_edge
->flags
& EDGE_FALSE_VALUE
)
2107 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
2110 gimple_set_modified (stmt
, true);
2118 update_stmt_if_modified (stmt
);
2119 eliminate_redundant_computations (si
, m_const_and_copies
,
2120 m_avail_exprs_stack
);
2121 stmt
= gsi_stmt (*si
);
2123 /* Perform simple redundant store elimination. */
2124 if (gimple_assign_single_p (stmt
)
2125 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
2127 tree lhs
= gimple_assign_lhs (stmt
);
2128 tree rhs
= gimple_assign_rhs1 (stmt
);
2131 rhs
= dom_valueize (rhs
);
2132 /* Build a new statement with the RHS and LHS exchanged. */
2133 if (TREE_CODE (rhs
) == SSA_NAME
)
2135 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
2136 new_stmt
= gimple_build_assign (rhs
, lhs
);
2137 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
2140 new_stmt
= gimple_build_assign (rhs
, lhs
);
2141 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2142 expr_hash_elt
*elt
= NULL
;
2143 cached_lhs
= m_avail_exprs_stack
->lookup_avail_expr (new_stmt
, false,
2146 && operand_equal_p (rhs
, cached_lhs
, 0)
2147 && refs_same_for_tbaa_p (elt
->expr ()->kind
== EXPR_SINGLE
2148 ? elt
->expr ()->ops
.single
.rhs
2151 basic_block bb
= gimple_bb (stmt
);
2152 unlink_stmt_vdef (stmt
);
2153 if (gsi_remove (si
, true))
2155 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2156 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2157 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2159 release_defs (stmt
);
2165 /* If this statement was not redundant, we may still be able to simplify
2166 it, which may in turn allow other part of DOM or other passes to do
2168 test_for_singularity (stmt
, m_avail_exprs_stack
);
2171 /* Record any additional equivalences created by this statement. */
2172 if (is_gimple_assign (stmt
))
2173 record_equivalences_from_stmt (stmt
, may_optimize_p
, m_avail_exprs_stack
);
2175 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
2176 know where it goes. */
2177 if (gimple_modified_p (stmt
) || modified_p
)
2181 if (gimple_code (stmt
) == GIMPLE_COND
)
2182 val
= fold_binary_loc (gimple_location (stmt
),
2183 gimple_cond_code (stmt
), boolean_type_node
,
2184 gimple_cond_lhs (stmt
),
2185 gimple_cond_rhs (stmt
));
2186 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
2187 val
= gimple_switch_index (swtch_stmt
);
2189 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2191 retval
= find_taken_edge (bb
, val
);
2194 /* Fix the condition to be either true or false. */
2195 if (gimple_code (stmt
) == GIMPLE_COND
)
2197 if (integer_zerop (val
))
2198 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
2199 else if (integer_onep (val
))
2200 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
2204 gimple_set_modified (stmt
, true);
2207 /* Further simplifications may be possible. */
2212 update_stmt_if_modified (stmt
);
2214 /* If we simplified a statement in such a way as to be shown that it
2215 cannot trap, update the eh information and the cfg to match. */
2216 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
2218 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2220 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2224 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
2225 need_noreturn_fixup
.safe_push (stmt
);