1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2017 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"
43 #include "tree-ssa-scopedtables.h"
44 #include "tree-ssa-threadedge.h"
45 #include "tree-ssa-dom.h"
47 #include "tree-cfgcleanup.h"
50 /* This file implements optimizations on the dominator tree. */
52 /* Structure for recording edge equivalences.
54 Computing and storing the edge equivalences instead of creating
55 them on-demand can save significant amounts of time, particularly
56 for pathological cases involving switch statements.
58 These structures live for a single iteration of the dominator
59 optimizer in the edge's AUX field. At the end of an iteration we
60 free each of these structures. */
64 typedef std::pair
<tree
, tree
> equiv_pair
;
68 /* Record a simple LHS = RHS equivalence. This may trigger
69 calls to derive_equivalences. */
70 void record_simple_equiv (tree
, tree
);
72 /* If traversing this edge creates simple equivalences, we store
73 them as LHS/RHS pairs within this vector. */
74 vec
<equiv_pair
> simple_equivalences
;
76 /* Traversing an edge may also indicate one or more particular conditions
78 vec
<cond_equivalence
> cond_equivalences
;
81 /* Derive equivalences by walking the use-def chains. */
82 void derive_equivalences (tree
, tree
, int);
85 /* Track whether or not we have changed the control flow graph. */
86 static bool cfg_altered
;
88 /* Bitmap of blocks that have had EH statements cleaned. We should
89 remove their dead edges eventually. */
90 static bitmap need_eh_cleanup
;
91 static vec
<gimple
*> need_noreturn_fixup
;
93 /* Statistics for dominator optimizations. */
97 long num_exprs_considered
;
103 static struct opt_stats_d opt_stats
;
105 /* Local functions. */
106 static void record_equality (tree
, tree
, class const_and_copies
*);
107 static void record_equivalences_from_phis (basic_block
);
108 static void record_equivalences_from_incoming_edge (basic_block
,
109 class const_and_copies
*,
110 class avail_exprs_stack
*);
111 static void eliminate_redundant_computations (gimple_stmt_iterator
*,
112 class const_and_copies
*,
113 class avail_exprs_stack
*);
114 static void record_equivalences_from_stmt (gimple
*, int,
115 class avail_exprs_stack
*);
116 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
117 static void dump_dominator_optimization_stats (FILE *file
,
118 hash_table
<expr_elt_hasher
> *);
120 /* Constructor for EDGE_INFO. An EDGE_INFO instance is always
121 associated with an edge E. */
123 edge_info::edge_info (edge e
)
125 /* Free the old one associated with E, if it exists and
126 associate our new object with E. */
127 free_dom_edge_info (e
);
130 /* And initialize the embedded vectors. */
131 simple_equivalences
= vNULL
;
132 cond_equivalences
= vNULL
;
135 /* Destructor just needs to release the vectors. */
137 edge_info::~edge_info (void)
139 this->cond_equivalences
.release ();
140 this->simple_equivalences
.release ();
143 /* NAME is known to have the value VALUE, which must be a constant.
145 Walk through its use-def chain to see if there are other equivalences
146 we might be able to derive.
148 RECURSION_LIMIT controls how far back we recurse through the use-def
152 edge_info::derive_equivalences (tree name
, tree value
, int recursion_limit
)
154 if (TREE_CODE (name
) != SSA_NAME
|| TREE_CODE (value
) != INTEGER_CST
)
157 /* This records the equivalence for the toplevel object. Do
158 this before checking the recursion limit. */
159 simple_equivalences
.safe_push (equiv_pair (name
, value
));
161 /* Limit how far up the use-def chains we are willing to walk. */
162 if (recursion_limit
== 0)
165 /* We can walk up the use-def chains to potentially find more
167 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
168 if (is_gimple_assign (def_stmt
))
170 /* We know the result of DEF_STMT was zero. See if that allows
171 us to deduce anything about the SSA_NAMEs used on the RHS. */
172 enum tree_code code
= gimple_assign_rhs_code (def_stmt
);
176 if (integer_zerop (value
))
178 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
179 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
181 value
= build_zero_cst (TREE_TYPE (rhs1
));
182 derive_equivalences (rhs1
, value
, recursion_limit
- 1);
183 value
= build_zero_cst (TREE_TYPE (rhs2
));
184 derive_equivalences (rhs2
, value
, recursion_limit
- 1);
188 /* We know the result of DEF_STMT was one. See if that allows
189 us to deduce anything about the SSA_NAMEs used on the RHS. */
191 if (!integer_zerop (value
))
193 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
194 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
196 /* If either operand has a boolean range, then we
197 know its value must be one, otherwise we just know it
198 is nonzero. The former is clearly useful, I haven't
199 seen cases where the latter is helpful yet. */
200 if (TREE_CODE (rhs1
) == SSA_NAME
)
202 if (ssa_name_has_boolean_range (rhs1
))
204 value
= build_one_cst (TREE_TYPE (rhs1
));
205 derive_equivalences (rhs1
, value
, recursion_limit
- 1);
208 if (TREE_CODE (rhs2
) == SSA_NAME
)
210 if (ssa_name_has_boolean_range (rhs2
))
212 value
= build_one_cst (TREE_TYPE (rhs2
));
213 derive_equivalences (rhs2
, value
, recursion_limit
- 1);
219 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
220 set via a widening type conversion, then we may be able to record
221 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
);
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
);
336 tree res
= fold_build1 (code
, TREE_TYPE (rhs
), value
);
337 derive_equivalences (rhs
, res
, recursion_limit
- 1);
343 if (TREE_CODE_CLASS (code
) == tcc_comparison
)
345 tree cond
= build2 (code
, boolean_type_node
,
346 gimple_assign_rhs1 (def_stmt
),
347 gimple_assign_rhs2 (def_stmt
));
348 tree inverted
= invert_truthvalue (cond
);
349 if (integer_zerop (value
))
350 std::swap (cond
, inverted
);
351 record_conditions (&this->cond_equivalences
, cond
, inverted
);
361 edge_info::record_simple_equiv (tree lhs
, tree rhs
)
363 /* If the RHS is a constant, then we may be able to derive
364 further equivalences. Else just record the name = name
366 if (TREE_CODE (rhs
) == INTEGER_CST
)
367 derive_equivalences (lhs
, rhs
, 4);
369 simple_equivalences
.safe_push (equiv_pair (lhs
, rhs
));
372 /* Free the edge_info data attached to E, if it exists. */
375 free_dom_edge_info (edge e
)
377 class edge_info
*edge_info
= (struct edge_info
*)e
->aux
;
383 /* Free all EDGE_INFO structures associated with edges in the CFG.
384 If a particular edge can be threaded, copy the redirection
385 target from the EDGE_INFO structure into the edge's AUX field
386 as required by code to update the CFG and SSA graph for
390 free_all_edge_infos (void)
396 FOR_EACH_BB_FN (bb
, cfun
)
398 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
400 free_dom_edge_info (e
);
406 /* We have finished optimizing BB, record any information implied by
407 taking a specific outgoing edge from BB. */
410 record_edge_info (basic_block bb
)
412 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
413 class edge_info
*edge_info
;
415 if (! gsi_end_p (gsi
))
417 gimple
*stmt
= gsi_stmt (gsi
);
418 location_t loc
= gimple_location (stmt
);
420 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
422 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
423 tree index
= gimple_switch_index (switch_stmt
);
425 if (TREE_CODE (index
) == SSA_NAME
)
428 int n_labels
= gimple_switch_num_labels (switch_stmt
);
429 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
433 for (i
= 0; i
< n_labels
; i
++)
435 tree label
= gimple_switch_label (switch_stmt
, i
);
436 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
437 if (CASE_HIGH (label
)
439 || info
[target_bb
->index
])
440 info
[target_bb
->index
] = error_mark_node
;
442 info
[target_bb
->index
] = label
;
445 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
447 basic_block target_bb
= e
->dest
;
448 tree label
= info
[target_bb
->index
];
450 if (label
!= NULL
&& label
!= error_mark_node
)
452 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
454 edge_info
= new class edge_info (e
);
455 edge_info
->record_simple_equiv (index
, x
);
462 /* A COND_EXPR may create equivalences too. */
463 if (gimple_code (stmt
) == GIMPLE_COND
)
468 tree op0
= gimple_cond_lhs (stmt
);
469 tree op1
= gimple_cond_rhs (stmt
);
470 enum tree_code code
= gimple_cond_code (stmt
);
472 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
474 /* Special case comparing booleans against a constant as we
475 know the value of OP0 on both arms of the branch. i.e., we
476 can record an equivalence for OP0 rather than COND.
478 However, don't do this if the constant isn't zero or one.
479 Such conditionals will get optimized more thoroughly during
481 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
482 && TREE_CODE (op0
) == SSA_NAME
483 && ssa_name_has_boolean_range (op0
)
484 && is_gimple_min_invariant (op1
)
485 && (integer_zerop (op1
) || integer_onep (op1
)))
487 tree true_val
= constant_boolean_node (true, TREE_TYPE (op0
));
488 tree false_val
= constant_boolean_node (false, TREE_TYPE (op0
));
492 edge_info
= new class edge_info (true_edge
);
493 edge_info
->record_simple_equiv (op0
,
495 ? false_val
: true_val
));
496 edge_info
= new class edge_info (false_edge
);
497 edge_info
->record_simple_equiv (op0
,
499 ? true_val
: false_val
));
503 edge_info
= new class edge_info (true_edge
);
504 edge_info
->record_simple_equiv (op0
,
506 ? true_val
: false_val
));
507 edge_info
= new class edge_info (false_edge
);
508 edge_info
->record_simple_equiv (op0
,
510 ? false_val
: true_val
));
513 /* This can show up in the IL as a result of copy propagation
514 it will eventually be canonicalized, but we have to cope
515 with this case within the pass. */
516 else if (is_gimple_min_invariant (op0
)
517 && TREE_CODE (op1
) == SSA_NAME
)
519 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
520 tree inverted
= invert_truthvalue_loc (loc
, cond
);
521 bool can_infer_simple_equiv
522 = !(HONOR_SIGNED_ZEROS (op0
)
523 && real_zerop (op0
));
524 struct edge_info
*edge_info
;
526 edge_info
= new class edge_info (true_edge
);
527 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
529 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
530 edge_info
->record_simple_equiv (op1
, op0
);
532 edge_info
= new class edge_info (false_edge
);
533 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
535 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
536 edge_info
->record_simple_equiv (op1
, op0
);
539 else if (TREE_CODE (op0
) == SSA_NAME
540 && (TREE_CODE (op1
) == SSA_NAME
541 || is_gimple_min_invariant (op1
)))
543 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
544 tree inverted
= invert_truthvalue_loc (loc
, cond
);
545 bool can_infer_simple_equiv
546 = !(HONOR_SIGNED_ZEROS (op1
)
547 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
548 struct edge_info
*edge_info
;
550 edge_info
= new class edge_info (true_edge
);
551 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
553 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
554 edge_info
->record_simple_equiv (op0
, op1
);
556 edge_info
= new class edge_info (false_edge
);
557 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
559 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
560 edge_info
->record_simple_equiv (op0
, op1
);
567 class dom_opt_dom_walker
: public dom_walker
570 dom_opt_dom_walker (cdi_direction direction
,
571 class const_and_copies
*const_and_copies
,
572 class avail_exprs_stack
*avail_exprs_stack
,
574 : dom_walker (direction
, true),
575 m_const_and_copies (const_and_copies
),
576 m_avail_exprs_stack (avail_exprs_stack
),
577 m_dummy_cond (dummy_cond
) { }
579 virtual edge
before_dom_children (basic_block
);
580 virtual void after_dom_children (basic_block
);
584 /* Unwindable equivalences, both const/copy and expression varieties. */
585 class const_and_copies
*m_const_and_copies
;
586 class avail_exprs_stack
*m_avail_exprs_stack
;
588 /* Dummy condition to avoid creating lots of throw away statements. */
591 /* Optimize a single statement within a basic block using the
592 various tables mantained by DOM. Returns the taken edge if
593 the statement is a conditional with a statically determined
595 edge
optimize_stmt (basic_block
, gimple_stmt_iterator
);
598 /* Jump threading, redundancy elimination and const/copy propagation.
600 This pass may expose new symbols that need to be renamed into SSA. For
601 every new symbol exposed, its corresponding bit will be set in
606 const pass_data pass_data_dominator
=
608 GIMPLE_PASS
, /* type */
610 OPTGROUP_NONE
, /* optinfo_flags */
611 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
612 ( PROP_cfg
| PROP_ssa
), /* properties_required */
613 0, /* properties_provided */
614 0, /* properties_destroyed */
615 0, /* todo_flags_start */
616 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
619 class pass_dominator
: public gimple_opt_pass
622 pass_dominator (gcc::context
*ctxt
)
623 : gimple_opt_pass (pass_data_dominator
, ctxt
),
624 may_peel_loop_headers_p (false)
627 /* opt_pass methods: */
628 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
629 void set_pass_param (unsigned int n
, bool param
)
632 may_peel_loop_headers_p
= param
;
634 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
635 virtual unsigned int execute (function
*);
638 /* This flag is used to prevent loops from being peeled repeatedly in jump
639 threading; it will be removed once we preserve loop structures throughout
640 the compilation -- we will be able to mark the affected loops directly in
641 jump threading, and avoid peeling them next time. */
642 bool may_peel_loop_headers_p
;
643 }; // class pass_dominator
646 pass_dominator::execute (function
*fun
)
648 memset (&opt_stats
, 0, sizeof (opt_stats
));
650 /* Create our hash tables. */
651 hash_table
<expr_elt_hasher
> *avail_exprs
652 = new hash_table
<expr_elt_hasher
> (1024);
653 class avail_exprs_stack
*avail_exprs_stack
654 = new class avail_exprs_stack (avail_exprs
);
655 class const_and_copies
*const_and_copies
= new class const_and_copies ();
656 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
657 need_noreturn_fixup
.create (0);
659 calculate_dominance_info (CDI_DOMINATORS
);
662 /* We need to know loop structures in order to avoid destroying them
663 in jump threading. Note that we still can e.g. thread through loop
664 headers to an exit edge, or through loop header to the loop body, assuming
665 that we update the loop info.
667 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
668 to several overly conservative bail-outs in jump threading, case
669 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
670 missing. We should improve jump threading in future then
671 LOOPS_HAVE_PREHEADERS won't be needed here. */
672 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
674 /* Initialize the value-handle array. */
675 threadedge_initialize_values ();
677 /* We need accurate information regarding back edges in the CFG
678 for jump threading; this may include back edges that are not part of
680 mark_dfs_back_edges ();
682 /* We want to create the edge info structures before the dominator walk
683 so that they'll be in place for the jump threader, particularly when
684 threading through a join block.
686 The conditions will be lazily updated with global equivalences as
687 we reach them during the dominator walk. */
689 FOR_EACH_BB_FN (bb
, fun
)
690 record_edge_info (bb
);
692 gcond
*dummy_cond
= gimple_build_cond (NE_EXPR
, integer_zero_node
,
693 integer_zero_node
, NULL
, NULL
);
695 /* Recursively walk the dominator tree optimizing statements. */
696 dom_opt_dom_walker
walker (CDI_DOMINATORS
, const_and_copies
,
697 avail_exprs_stack
, dummy_cond
);
698 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
700 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
701 edge. When found, remove jump threads which contain any outgoing
702 edge from the affected block. */
705 FOR_EACH_BB_FN (bb
, fun
)
710 /* First see if there are any edges without EDGE_EXECUTABLE
713 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
715 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
722 /* If there were any such edges found, then remove jump threads
723 containing any edge leaving BB. */
725 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
726 remove_jump_threads_including (e
);
731 gimple_stmt_iterator gsi
;
733 FOR_EACH_BB_FN (bb
, fun
)
735 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
736 update_stmt_if_modified (gsi_stmt (gsi
));
740 /* If we exposed any new variables, go ahead and put them into
741 SSA form now, before we handle jump threading. This simplifies
742 interactions between rewriting of _DECL nodes into SSA form
743 and rewriting SSA_NAME nodes into SSA form after block
744 duplication and CFG manipulation. */
745 update_ssa (TODO_update_ssa
);
747 free_all_edge_infos ();
749 /* Thread jumps, creating duplicate blocks as needed. */
750 cfg_altered
|= thread_through_all_blocks (may_peel_loop_headers_p
);
753 free_dominance_info (CDI_DOMINATORS
);
755 /* Removal of statements may make some EH edges dead. Purge
756 such edges from the CFG as needed. */
757 if (!bitmap_empty_p (need_eh_cleanup
))
762 /* Jump threading may have created forwarder blocks from blocks
763 needing EH cleanup; the new successor of these blocks, which
764 has inherited from the original block, needs the cleanup.
765 Don't clear bits in the bitmap, as that can break the bitmap
767 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
769 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
772 while (single_succ_p (bb
)
773 && (single_succ_edge (bb
)->flags
& EDGE_EH
) == 0)
774 bb
= single_succ (bb
);
775 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
777 if ((unsigned) bb
->index
!= i
)
778 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
781 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
782 bitmap_clear (need_eh_cleanup
);
785 /* Fixup stmts that became noreturn calls. This may require splitting
786 blocks and thus isn't possible during the dominator walk or before
787 jump threading finished. Do this in reverse order so we don't
788 inadvertedly remove a stmt we want to fixup by visiting a dominating
789 now noreturn call first. */
790 while (!need_noreturn_fixup
.is_empty ())
792 gimple
*stmt
= need_noreturn_fixup
.pop ();
793 if (dump_file
&& dump_flags
& TDF_DETAILS
)
795 fprintf (dump_file
, "Fixing up noreturn call ");
796 print_gimple_stmt (dump_file
, stmt
, 0);
797 fprintf (dump_file
, "\n");
799 fixup_noreturn_call (stmt
);
802 statistics_counter_event (fun
, "Redundant expressions eliminated",
804 statistics_counter_event (fun
, "Constants propagated",
805 opt_stats
.num_const_prop
);
806 statistics_counter_event (fun
, "Copies propagated",
807 opt_stats
.num_copy_prop
);
809 /* Debugging dumps. */
810 if (dump_file
&& (dump_flags
& TDF_STATS
))
811 dump_dominator_optimization_stats (dump_file
, avail_exprs
);
813 loop_optimizer_finalize ();
815 /* Delete our main hashtable. */
819 /* Free asserted bitmaps and stacks. */
820 BITMAP_FREE (need_eh_cleanup
);
821 need_noreturn_fixup
.release ();
822 delete avail_exprs_stack
;
823 delete const_and_copies
;
825 /* Free the value-handle array. */
826 threadedge_finalize_values ();
834 make_pass_dominator (gcc::context
*ctxt
)
836 return new pass_dominator (ctxt
);
840 /* A trivial wrapper so that we can present the generic jump
841 threading code with a simple API for simplifying statements. */
843 simplify_stmt_for_jump_threading (gimple
*stmt
,
844 gimple
*within_stmt ATTRIBUTE_UNUSED
,
845 class avail_exprs_stack
*avail_exprs_stack
,
846 basic_block bb ATTRIBUTE_UNUSED
)
848 return avail_exprs_stack
->lookup_avail_expr (stmt
, false, true);
851 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
854 dom_valueize (tree t
)
856 if (TREE_CODE (t
) == SSA_NAME
)
858 tree tem
= SSA_NAME_VALUE (t
);
865 /* We have just found an equivalence for LHS on an edge E.
866 Look backwards to other uses of LHS and see if we can derive
867 additional equivalences that are valid on edge E. */
869 back_propagate_equivalences (tree lhs
, edge e
,
870 class const_and_copies
*const_and_copies
)
873 imm_use_iterator iter
;
875 basic_block dest
= e
->dest
;
877 /* Iterate over the uses of LHS to see if any dominate E->dest.
878 If so, they may create useful equivalences too.
880 ??? If the code gets re-organized to a worklist to catch more
881 indirect opportunities and it is made to handle PHIs then this
882 should only consider use_stmts in basic-blocks we have already visited. */
883 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
885 gimple
*use_stmt
= USE_STMT (use_p
);
887 /* Often the use is in DEST, which we trivially know we can't use.
888 This is cheaper than the dominator set tests below. */
889 if (dest
== gimple_bb (use_stmt
))
892 /* Filter out statements that can never produce a useful
894 tree lhs2
= gimple_get_lhs (use_stmt
);
895 if (!lhs2
|| TREE_CODE (lhs2
) != SSA_NAME
)
898 /* Profiling has shown the domination tests here can be fairly
899 expensive. We get significant improvements by building the
900 set of blocks that dominate BB. We can then just test
901 for set membership below.
903 We also initialize the set lazily since often the only uses
904 are going to be in the same block as DEST. */
907 domby
= BITMAP_ALLOC (NULL
);
908 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
911 bitmap_set_bit (domby
, bb
->index
);
912 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
916 /* This tests if USE_STMT does not dominate DEST. */
917 if (!bitmap_bit_p (domby
, gimple_bb (use_stmt
)->index
))
920 /* At this point USE_STMT dominates DEST and may result in a
921 useful equivalence. Try to simplify its RHS to a constant
923 tree res
= gimple_fold_stmt_to_constant_1 (use_stmt
, dom_valueize
,
924 no_follow_ssa_edges
);
925 if (res
&& (TREE_CODE (res
) == SSA_NAME
|| is_gimple_min_invariant (res
)))
926 record_equality (lhs2
, res
, const_and_copies
);
933 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
934 by traversing edge E (which are cached in E->aux).
936 Callers are responsible for managing the unwinding markers. */
938 record_temporary_equivalences (edge e
,
939 class const_and_copies
*const_and_copies
,
940 class avail_exprs_stack
*avail_exprs_stack
)
943 class edge_info
*edge_info
= (class edge_info
*) e
->aux
;
945 /* If we have info associated with this edge, record it into
946 our equivalence tables. */
949 cond_equivalence
*eq
;
950 /* If we have 0 = COND or 1 = COND equivalences, record them
951 into our expression hash tables. */
952 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
953 avail_exprs_stack
->record_cond (eq
);
955 edge_info::equiv_pair
*seq
;
956 for (i
= 0; edge_info
->simple_equivalences
.iterate (i
, &seq
); ++i
)
958 tree lhs
= seq
->first
;
959 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
)
962 /* Record the simple NAME = VALUE equivalence. */
963 tree rhs
= seq
->second
;
965 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
966 cheaper to compute than the other, then set up the equivalence
967 such that we replace the expensive one with the cheap one.
969 If they are the same cost to compute, then do not record
971 if (TREE_CODE (lhs
) == SSA_NAME
&& TREE_CODE (rhs
) == SSA_NAME
)
973 gimple
*rhs_def
= SSA_NAME_DEF_STMT (rhs
);
974 int rhs_cost
= estimate_num_insns (rhs_def
, &eni_size_weights
);
976 gimple
*lhs_def
= SSA_NAME_DEF_STMT (lhs
);
977 int lhs_cost
= estimate_num_insns (lhs_def
, &eni_size_weights
);
979 if (rhs_cost
> lhs_cost
)
980 record_equality (rhs
, lhs
, const_and_copies
);
981 else if (rhs_cost
< lhs_cost
)
982 record_equality (lhs
, rhs
, const_and_copies
);
985 record_equality (lhs
, rhs
, const_and_copies
);
988 /* Any equivalence found for LHS may result in additional
989 equivalences for other uses of LHS that we have already
991 back_propagate_equivalences (lhs
, e
, const_and_copies
);
996 /* PHI nodes can create equivalences too.
998 Ignoring any alternatives which are the same as the result, if
999 all the alternatives are equal, then the PHI node creates an
1003 record_equivalences_from_phis (basic_block bb
)
1007 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1009 gphi
*phi
= gsi
.phi ();
1011 tree lhs
= gimple_phi_result (phi
);
1015 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1017 tree t
= gimple_phi_arg_def (phi
, i
);
1019 /* Ignore alternatives which are the same as our LHS. Since
1020 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1021 can simply compare pointers. */
1025 /* If the associated edge is not marked as executable, then it
1027 if ((gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_EXECUTABLE
) == 0)
1030 t
= dom_valueize (t
);
1032 /* If we have not processed an alternative yet, then set
1033 RHS to this alternative. */
1036 /* If we have processed an alternative (stored in RHS), then
1037 see if it is equal to this one. If it isn't, then stop
1039 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1043 /* If we had no interesting alternatives, then all the RHS alternatives
1044 must have been the same as LHS. */
1048 /* If we managed to iterate through each PHI alternative without
1049 breaking out of the loop, then we have a PHI which may create
1050 a useful equivalence. We do not need to record unwind data for
1051 this, since this is a true assignment and not an equivalence
1052 inferred from a comparison. All uses of this ssa name are dominated
1053 by this assignment, so unwinding just costs time and space. */
1054 if (i
== gimple_phi_num_args (phi
)
1055 && may_propagate_copy (lhs
, rhs
))
1056 set_ssa_name_value (lhs
, rhs
);
1060 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1061 return that edge. Otherwise return NULL. */
1063 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1069 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1071 /* A loop back edge can be identified by the destination of
1072 the edge dominating the source of the edge. */
1073 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1076 /* We can safely ignore edges that are not executable. */
1077 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
1080 /* If we have already seen a non-loop edge, then we must have
1081 multiple incoming non-loop edges and thus we return NULL. */
1085 /* This is the first non-loop incoming edge we have found. Record
1093 /* Record any equivalences created by the incoming edge to BB into
1094 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
1095 incoming edge, then no equivalence is created. */
1098 record_equivalences_from_incoming_edge (basic_block bb
,
1099 class const_and_copies
*const_and_copies
,
1100 class avail_exprs_stack
*avail_exprs_stack
)
1105 /* If our parent block ended with a control statement, then we may be
1106 able to record some equivalences based on which outgoing edge from
1107 the parent was followed. */
1108 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1110 e
= single_incoming_edge_ignoring_loop_edges (bb
);
1112 /* If we had a single incoming edge from our parent block, then enter
1113 any data associated with the edge into our tables. */
1114 if (e
&& e
->src
== parent
)
1115 record_temporary_equivalences (e
, const_and_copies
, avail_exprs_stack
);
1118 /* Dump statistics for the hash table HTAB. */
1121 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
1123 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1124 (long) htab
.size (),
1125 (long) htab
.elements (),
1126 htab
.collisions ());
1129 /* Dump SSA statistics on FILE. */
1132 dump_dominator_optimization_stats (FILE *file
,
1133 hash_table
<expr_elt_hasher
> *avail_exprs
)
1135 fprintf (file
, "Total number of statements: %6ld\n\n",
1136 opt_stats
.num_stmts
);
1137 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1138 opt_stats
.num_exprs_considered
);
1140 fprintf (file
, "\nHash table statistics:\n");
1142 fprintf (file
, " avail_exprs: ");
1143 htab_statistics (file
, *avail_exprs
);
1147 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1148 This constrains the cases in which we may treat this as assignment. */
1151 record_equality (tree x
, tree y
, class const_and_copies
*const_and_copies
)
1153 tree prev_x
= NULL
, prev_y
= NULL
;
1155 if (tree_swap_operands_p (x
, y
))
1158 /* Most of the time tree_swap_operands_p does what we want. But there
1159 are cases where we know one operand is better for copy propagation than
1160 the other. Given no other code cares about ordering of equality
1161 comparison operators for that purpose, we just handle the special cases
1163 if (TREE_CODE (x
) == SSA_NAME
&& TREE_CODE (y
) == SSA_NAME
)
1165 /* If one operand is a single use operand, then make it
1166 X. This will preserve its single use properly and if this
1167 conditional is eliminated, the computation of X can be
1168 eliminated as well. */
1169 if (has_single_use (y
) && ! has_single_use (x
))
1172 if (TREE_CODE (x
) == SSA_NAME
)
1173 prev_x
= SSA_NAME_VALUE (x
);
1174 if (TREE_CODE (y
) == SSA_NAME
)
1175 prev_y
= SSA_NAME_VALUE (y
);
1177 /* If one of the previous values is invariant, or invariant in more loops
1178 (by depth), then use that.
1179 Otherwise it doesn't matter which value we choose, just so
1180 long as we canonicalize on one value. */
1181 if (is_gimple_min_invariant (y
))
1183 else if (is_gimple_min_invariant (x
))
1184 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1185 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1186 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1190 /* After the swapping, we must have one SSA_NAME. */
1191 if (TREE_CODE (x
) != SSA_NAME
)
1194 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1195 variable compared against zero. If we're honoring signed zeros,
1196 then we cannot record this value unless we know that the value is
1198 if (HONOR_SIGNED_ZEROS (x
)
1199 && (TREE_CODE (y
) != REAL_CST
1200 || real_equal (&dconst0
, &TREE_REAL_CST (y
))))
1203 const_and_copies
->record_const_or_copy (x
, y
, prev_x
);
1206 /* Returns true when STMT is a simple iv increment. It detects the
1207 following situation:
1209 i_1 = phi (..., i_2)
1210 i_2 = i_1 +/- ... */
1213 simple_iv_increment_p (gimple
*stmt
)
1215 enum tree_code code
;
1220 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1223 lhs
= gimple_assign_lhs (stmt
);
1224 if (TREE_CODE (lhs
) != SSA_NAME
)
1227 code
= gimple_assign_rhs_code (stmt
);
1228 if (code
!= PLUS_EXPR
1229 && code
!= MINUS_EXPR
1230 && code
!= POINTER_PLUS_EXPR
)
1233 preinc
= gimple_assign_rhs1 (stmt
);
1234 if (TREE_CODE (preinc
) != SSA_NAME
)
1237 phi
= SSA_NAME_DEF_STMT (preinc
);
1238 if (gimple_code (phi
) != GIMPLE_PHI
)
1241 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1242 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1248 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1249 successors of BB. */
1252 cprop_into_successor_phis (basic_block bb
,
1253 class const_and_copies
*const_and_copies
)
1258 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1263 /* If this is an abnormal edge, then we do not want to copy propagate
1264 into the PHI alternative associated with this edge. */
1265 if (e
->flags
& EDGE_ABNORMAL
)
1268 gsi
= gsi_start_phis (e
->dest
);
1269 if (gsi_end_p (gsi
))
1272 /* We may have an equivalence associated with this edge. While
1273 we can not propagate it into non-dominated blocks, we can
1274 propagate them into PHIs in non-dominated blocks. */
1276 /* Push the unwind marker so we can reset the const and copies
1277 table back to its original state after processing this edge. */
1278 const_and_copies
->push_marker ();
1280 /* Extract and record any simple NAME = VALUE equivalences.
1282 Don't bother with [01] = COND equivalences, they're not useful
1284 class edge_info
*edge_info
= (class edge_info
*) e
->aux
;
1288 edge_info::equiv_pair
*seq
;
1289 for (int i
= 0; edge_info
->simple_equivalences
.iterate (i
, &seq
); ++i
)
1291 tree lhs
= seq
->first
;
1292 tree rhs
= seq
->second
;
1294 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1295 const_and_copies
->record_const_or_copy (lhs
, rhs
);
1301 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1304 use_operand_p orig_p
;
1306 gphi
*phi
= gsi
.phi ();
1308 /* The alternative may be associated with a constant, so verify
1309 it is an SSA_NAME before doing anything with it. */
1310 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1311 orig_val
= get_use_from_ptr (orig_p
);
1312 if (TREE_CODE (orig_val
) != SSA_NAME
)
1315 /* If we have *ORIG_P in our constant/copy table, then replace
1316 ORIG_P with its value in our constant/copy table. */
1317 new_val
= SSA_NAME_VALUE (orig_val
);
1319 && new_val
!= orig_val
1320 && may_propagate_copy (orig_val
, new_val
))
1321 propagate_value (orig_p
, new_val
);
1324 const_and_copies
->pop_to_marker ();
1329 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1331 gimple_stmt_iterator gsi
;
1333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1334 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1336 /* Push a marker on the stacks of local information so that we know how
1337 far to unwind when we finalize this block. */
1338 m_avail_exprs_stack
->push_marker ();
1339 m_const_and_copies
->push_marker ();
1341 record_equivalences_from_incoming_edge (bb
, m_const_and_copies
,
1342 m_avail_exprs_stack
);
1344 /* PHI nodes can create equivalences too. */
1345 record_equivalences_from_phis (bb
);
1347 /* Create equivalences from redundant PHIs. PHIs are only truly
1348 redundant when they exist in the same block, so push another
1349 marker and unwind right afterwards. */
1350 m_avail_exprs_stack
->push_marker ();
1351 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1352 eliminate_redundant_computations (&gsi
, m_const_and_copies
,
1353 m_avail_exprs_stack
);
1354 m_avail_exprs_stack
->pop_to_marker ();
1356 edge taken_edge
= NULL
;
1357 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1358 taken_edge
= this->optimize_stmt (bb
, gsi
);
1360 /* Now prepare to process dominated blocks. */
1361 record_edge_info (bb
);
1362 cprop_into_successor_phis (bb
, m_const_and_copies
);
1363 if (taken_edge
&& !dbg_cnt (dom_unreachable_edges
))
1369 /* We have finished processing the dominator children of BB, perform
1370 any finalization actions in preparation for leaving this node in
1371 the dominator tree. */
1374 dom_opt_dom_walker::after_dom_children (basic_block bb
)
1376 thread_outgoing_edges (bb
, m_dummy_cond
, m_const_and_copies
,
1377 m_avail_exprs_stack
,
1378 simplify_stmt_for_jump_threading
);
1380 /* These remove expressions local to BB from the tables. */
1381 m_avail_exprs_stack
->pop_to_marker ();
1382 m_const_and_copies
->pop_to_marker ();
1385 /* Search for redundant computations in STMT. If any are found, then
1386 replace them with the variable holding the result of the computation.
1388 If safe, record this expression into AVAIL_EXPRS_STACK and
1389 CONST_AND_COPIES. */
1392 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
,
1393 class const_and_copies
*const_and_copies
,
1394 class avail_exprs_stack
*avail_exprs_stack
)
1400 bool assigns_var_p
= false;
1402 gimple
*stmt
= gsi_stmt (*gsi
);
1404 if (gimple_code (stmt
) == GIMPLE_PHI
)
1405 def
= gimple_phi_result (stmt
);
1407 def
= gimple_get_lhs (stmt
);
1409 /* Certain expressions on the RHS can be optimized away, but can not
1410 themselves be entered into the hash tables. */
1412 || TREE_CODE (def
) != SSA_NAME
1413 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1414 || gimple_vdef (stmt
)
1415 /* Do not record equivalences for increments of ivs. This would create
1416 overlapping live ranges for a very questionable gain. */
1417 || simple_iv_increment_p (stmt
))
1420 /* Check if the expression has been computed before. */
1421 cached_lhs
= avail_exprs_stack
->lookup_avail_expr (stmt
, insert
, true);
1423 opt_stats
.num_exprs_considered
++;
1425 /* Get the type of the expression we are trying to optimize. */
1426 if (is_gimple_assign (stmt
))
1428 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1429 assigns_var_p
= true;
1431 else if (gimple_code (stmt
) == GIMPLE_COND
)
1432 expr_type
= boolean_type_node
;
1433 else if (is_gimple_call (stmt
))
1435 gcc_assert (gimple_call_lhs (stmt
));
1436 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1437 assigns_var_p
= true;
1439 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1440 expr_type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
1441 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1442 /* We can't propagate into a phi, so the logic below doesn't apply.
1443 Instead record an equivalence between the cached LHS and the
1444 PHI result of this statement, provided they are in the same block.
1445 This should be sufficient to kill the redundant phi. */
1447 if (def
&& cached_lhs
)
1448 const_and_copies
->record_const_or_copy (def
, cached_lhs
);
1457 /* It is safe to ignore types here since we have already done
1458 type checking in the hashing and equality routines. In fact
1459 type checking here merely gets in the way of constant
1460 propagation. Also, make sure that it is safe to propagate
1461 CACHED_LHS into the expression in STMT. */
1462 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1464 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1465 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1467 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1468 || is_gimple_min_invariant (cached_lhs
));
1470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1472 fprintf (dump_file
, " Replaced redundant expr '");
1473 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1474 fprintf (dump_file
, "' with '");
1475 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1476 fprintf (dump_file
, "'\n");
1482 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1483 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1485 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1487 /* Since it is always necessary to mark the result as modified,
1488 perhaps we should move this into propagate_tree_value_into_stmt
1490 gimple_set_modified (gsi_stmt (*gsi
), true);
1494 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1495 the available expressions table or the const_and_copies table.
1496 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1498 We handle only very simple copy equivalences here. The heavy
1499 lifing is done by eliminate_redundant_computations. */
1502 record_equivalences_from_stmt (gimple
*stmt
, int may_optimize_p
,
1503 class avail_exprs_stack
*avail_exprs_stack
)
1506 enum tree_code lhs_code
;
1508 gcc_assert (is_gimple_assign (stmt
));
1510 lhs
= gimple_assign_lhs (stmt
);
1511 lhs_code
= TREE_CODE (lhs
);
1513 if (lhs_code
== SSA_NAME
1514 && gimple_assign_single_p (stmt
))
1516 tree rhs
= gimple_assign_rhs1 (stmt
);
1518 /* If the RHS of the assignment is a constant or another variable that
1519 may be propagated, register it in the CONST_AND_COPIES table. We
1520 do not need to record unwind data for this, since this is a true
1521 assignment and not an equivalence inferred from a comparison. All
1522 uses of this ssa name are dominated by this assignment, so unwinding
1523 just costs time and space. */
1525 && (TREE_CODE (rhs
) == SSA_NAME
1526 || is_gimple_min_invariant (rhs
)))
1528 rhs
= dom_valueize (rhs
);
1530 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1532 fprintf (dump_file
, "==== ASGN ");
1533 print_generic_expr (dump_file
, lhs
);
1534 fprintf (dump_file
, " = ");
1535 print_generic_expr (dump_file
, rhs
);
1536 fprintf (dump_file
, "\n");
1539 set_ssa_name_value (lhs
, rhs
);
1543 /* Make sure we can propagate &x + CST. */
1544 if (lhs_code
== SSA_NAME
1545 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1546 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
1547 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
1549 tree op0
= gimple_assign_rhs1 (stmt
);
1550 tree op1
= gimple_assign_rhs2 (stmt
);
1552 = build_fold_addr_expr (fold_build2 (MEM_REF
,
1553 TREE_TYPE (TREE_TYPE (op0
)),
1555 fold_convert (ptr_type_node
,
1557 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1559 fprintf (dump_file
, "==== ASGN ");
1560 print_generic_expr (dump_file
, lhs
);
1561 fprintf (dump_file
, " = ");
1562 print_generic_expr (dump_file
, new_rhs
);
1563 fprintf (dump_file
, "\n");
1566 set_ssa_name_value (lhs
, new_rhs
);
1569 /* A memory store, even an aliased store, creates a useful
1570 equivalence. By exchanging the LHS and RHS, creating suitable
1571 vops and recording the result in the available expression table,
1572 we may be able to expose more redundant loads. */
1573 if (!gimple_has_volatile_ops (stmt
)
1574 && gimple_references_memory_p (stmt
)
1575 && gimple_assign_single_p (stmt
)
1576 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1577 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1578 && !is_gimple_reg (lhs
))
1580 tree rhs
= gimple_assign_rhs1 (stmt
);
1583 /* Build a new statement with the RHS and LHS exchanged. */
1584 if (TREE_CODE (rhs
) == SSA_NAME
)
1586 /* NOTE tuples. The call to gimple_build_assign below replaced
1587 a call to build_gimple_modify_stmt, which did not set the
1588 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1589 may cause an SSA validation failure, as the LHS may be a
1590 default-initialized name and should have no definition. I'm
1591 a bit dubious of this, as the artificial statement that we
1592 generate here may in fact be ill-formed, but it is simply
1593 used as an internal device in this pass, and never becomes
1595 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1596 new_stmt
= gimple_build_assign (rhs
, lhs
);
1597 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1600 new_stmt
= gimple_build_assign (rhs
, lhs
);
1602 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
1604 /* Finally enter the statement into the available expression
1606 avail_exprs_stack
->lookup_avail_expr (new_stmt
, true, true);
1610 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1611 CONST_AND_COPIES. */
1614 cprop_operand (gimple
*stmt
, use_operand_p op_p
)
1617 tree op
= USE_FROM_PTR (op_p
);
1619 /* If the operand has a known constant value or it is known to be a
1620 copy of some other variable, use the value or copy stored in
1621 CONST_AND_COPIES. */
1622 val
= SSA_NAME_VALUE (op
);
1623 if (val
&& val
!= op
)
1625 /* Do not replace hard register operands in asm statements. */
1626 if (gimple_code (stmt
) == GIMPLE_ASM
1627 && !may_propagate_copy_into_asm (op
))
1630 /* Certain operands are not allowed to be copy propagated due
1631 to their interaction with exception handling and some GCC
1633 if (!may_propagate_copy (op
, val
))
1636 /* Do not propagate copies into BIVs.
1637 See PR23821 and PR62217 for how this can disturb IV and
1638 number of iteration analysis. */
1639 if (TREE_CODE (val
) != INTEGER_CST
)
1641 gimple
*def
= SSA_NAME_DEF_STMT (op
);
1642 if (gimple_code (def
) == GIMPLE_PHI
1643 && gimple_bb (def
)->loop_father
->header
== gimple_bb (def
))
1648 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1650 fprintf (dump_file
, " Replaced '");
1651 print_generic_expr (dump_file
, op
, dump_flags
);
1652 fprintf (dump_file
, "' with %s '",
1653 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1654 print_generic_expr (dump_file
, val
, dump_flags
);
1655 fprintf (dump_file
, "'\n");
1658 if (TREE_CODE (val
) != SSA_NAME
)
1659 opt_stats
.num_const_prop
++;
1661 opt_stats
.num_copy_prop
++;
1663 propagate_value (op_p
, val
);
1665 /* And note that we modified this statement. This is now
1666 safe, even if we changed virtual operands since we will
1667 rescan the statement and rewrite its operands again. */
1668 gimple_set_modified (stmt
, true);
1672 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1673 known value for that SSA_NAME (or NULL if no value is known).
1675 Propagate values from CONST_AND_COPIES into the uses, vuses and
1676 vdef_ops of STMT. */
1679 cprop_into_stmt (gimple
*stmt
)
1683 tree last_copy_propagated_op
= NULL
;
1685 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
1687 tree old_op
= USE_FROM_PTR (op_p
);
1689 /* If we have A = B and B = A in the copy propagation tables
1690 (due to an equality comparison), avoid substituting B for A
1691 then A for B in the trivially discovered cases. This allows
1692 optimization of statements were A and B appear as input
1694 if (old_op
!= last_copy_propagated_op
)
1696 cprop_operand (stmt
, op_p
);
1698 tree new_op
= USE_FROM_PTR (op_p
);
1699 if (new_op
!= old_op
&& TREE_CODE (new_op
) == SSA_NAME
)
1700 last_copy_propagated_op
= new_op
;
1705 /* If STMT contains a relational test, try to convert it into an
1706 equality test if there is only a single value which can ever
1709 For example, if the expression hash table contains:
1713 And we have a test within statement of i >= 1, then we can safely
1714 rewrite the test as i == 1 since there only a single value where
1717 This is similar to code in VRP. */
1720 test_for_singularity (gimple
*stmt
, gcond
*dummy_cond
,
1721 avail_exprs_stack
*avail_exprs_stack
)
1723 /* We want to support gimple conditionals as well as assignments
1724 where the RHS contains a conditional. */
1725 if (is_gimple_assign (stmt
) || gimple_code (stmt
) == GIMPLE_COND
)
1727 enum tree_code code
= ERROR_MARK
;
1730 /* Extract the condition of interest from both forms we support. */
1731 if (is_gimple_assign (stmt
))
1733 code
= gimple_assign_rhs_code (stmt
);
1734 lhs
= gimple_assign_rhs1 (stmt
);
1735 rhs
= gimple_assign_rhs2 (stmt
);
1737 else if (gimple_code (stmt
) == GIMPLE_COND
)
1739 code
= gimple_cond_code (as_a
<gcond
*> (stmt
));
1740 lhs
= gimple_cond_lhs (as_a
<gcond
*> (stmt
));
1741 rhs
= gimple_cond_rhs (as_a
<gcond
*> (stmt
));
1744 /* We're looking for a relational test using LE/GE. Also note we can
1745 canonicalize LT/GT tests against constants into LE/GT tests. */
1746 if (code
== LE_EXPR
|| code
== GE_EXPR
1747 || ((code
== LT_EXPR
|| code
== GT_EXPR
)
1748 && TREE_CODE (rhs
) == INTEGER_CST
))
1750 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */
1751 if (code
== LT_EXPR
)
1752 rhs
= fold_build2 (MINUS_EXPR
, TREE_TYPE (rhs
),
1753 rhs
, build_int_cst (TREE_TYPE (rhs
), 1));
1755 if (code
== GT_EXPR
)
1756 rhs
= fold_build2 (PLUS_EXPR
, TREE_TYPE (rhs
),
1757 rhs
, build_int_cst (TREE_TYPE (rhs
), 1));
1759 /* Determine the code we want to check for in the hash table. */
1760 enum tree_code test_code
;
1761 if (code
== GE_EXPR
|| code
== GT_EXPR
)
1762 test_code
= LE_EXPR
;
1764 test_code
= GE_EXPR
;
1766 /* Update the dummy statement so we can query the hash tables. */
1767 gimple_cond_set_code (dummy_cond
, test_code
);
1768 gimple_cond_set_lhs (dummy_cond
, lhs
);
1769 gimple_cond_set_rhs (dummy_cond
, rhs
);
1771 = avail_exprs_stack
->lookup_avail_expr (dummy_cond
, false, false);
1773 /* If the lookup returned 1 (true), then the expression we
1774 queried was in the hash table. As a result there is only
1775 one value that makes the original conditional true. Update
1776 STMT accordingly. */
1777 if (cached_lhs
&& integer_onep (cached_lhs
))
1779 if (is_gimple_assign (stmt
))
1781 gimple_assign_set_rhs_code (stmt
, EQ_EXPR
);
1782 gimple_assign_set_rhs2 (stmt
, rhs
);
1783 gimple_set_modified (stmt
, true);
1787 gimple_set_modified (stmt
, true);
1788 gimple_cond_set_code (as_a
<gcond
*> (stmt
), EQ_EXPR
);
1789 gimple_cond_set_rhs (as_a
<gcond
*> (stmt
), rhs
);
1790 gimple_set_modified (stmt
, true);
1797 /* Optimize the statement in block BB pointed to by iterator SI.
1799 We try to perform some simplistic global redundancy elimination and
1800 constant propagation:
1802 1- To detect global redundancy, we keep track of expressions that have
1803 been computed in this block and its dominators. If we find that the
1804 same expression is computed more than once, we eliminate repeated
1805 computations by using the target of the first one.
1807 2- Constant values and copy assignments. This is used to do very
1808 simplistic constant and copy propagation. When a constant or copy
1809 assignment is found, we map the value on the RHS of the assignment to
1810 the variable in the LHS in the CONST_AND_COPIES table.
1812 3- Very simple redundant store elimination is performed.
1814 4- We can simpify a condition to a constant or from a relational
1815 condition to an equality condition. */
1818 dom_opt_dom_walker::optimize_stmt (basic_block bb
, gimple_stmt_iterator si
)
1820 gimple
*stmt
, *old_stmt
;
1821 bool may_optimize_p
;
1822 bool modified_p
= false;
1826 old_stmt
= stmt
= gsi_stmt (si
);
1827 was_noreturn
= is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
);
1829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1831 fprintf (dump_file
, "Optimizing statement ");
1832 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1835 update_stmt_if_modified (stmt
);
1836 opt_stats
.num_stmts
++;
1838 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1839 cprop_into_stmt (stmt
);
1841 /* If the statement has been modified with constant replacements,
1842 fold its RHS before checking for redundant computations. */
1843 if (gimple_modified_p (stmt
))
1847 /* Try to fold the statement making sure that STMT is kept
1849 if (fold_stmt (&si
))
1851 stmt
= gsi_stmt (si
);
1852 gimple_set_modified (stmt
, true);
1854 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1856 fprintf (dump_file
, " Folded to: ");
1857 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1861 /* We only need to consider cases that can yield a gimple operand. */
1862 if (gimple_assign_single_p (stmt
))
1863 rhs
= gimple_assign_rhs1 (stmt
);
1864 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
1865 rhs
= gimple_goto_dest (stmt
);
1866 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1867 /* This should never be an ADDR_EXPR. */
1868 rhs
= gimple_switch_index (swtch_stmt
);
1870 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
1871 recompute_tree_invariant_for_addr_expr (rhs
);
1873 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1874 even if fold_stmt updated the stmt already and thus cleared
1875 gimple_modified_p flag on it. */
1879 /* Check for redundant computations. Do this optimization only
1880 for assignments that have no volatile ops and conditionals. */
1881 may_optimize_p
= (!gimple_has_side_effects (stmt
)
1882 && (is_gimple_assign (stmt
)
1883 || (is_gimple_call (stmt
)
1884 && gimple_call_lhs (stmt
) != NULL_TREE
)
1885 || gimple_code (stmt
) == GIMPLE_COND
1886 || gimple_code (stmt
) == GIMPLE_SWITCH
));
1890 if (gimple_code (stmt
) == GIMPLE_CALL
)
1892 /* Resolve __builtin_constant_p. If it hasn't been
1893 folded to integer_one_node by now, it's fairly
1894 certain that the value simply isn't constant. */
1895 tree callee
= gimple_call_fndecl (stmt
);
1897 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
1898 && DECL_FUNCTION_CODE (callee
) == BUILT_IN_CONSTANT_P
)
1900 propagate_tree_value_into_stmt (&si
, integer_zero_node
);
1901 stmt
= gsi_stmt (si
);
1905 if (gimple_code (stmt
) == GIMPLE_COND
)
1907 tree lhs
= gimple_cond_lhs (stmt
);
1908 tree rhs
= gimple_cond_rhs (stmt
);
1910 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
1911 then this conditional is computable at compile time. We can just
1912 shove either 0 or 1 into the LHS, mark the statement as modified
1913 and all the right things will just happen below.
1915 Note this would apply to any case where LHS has a range
1916 narrower than its type implies and RHS is outside that
1917 narrower range. Future work. */
1918 if (TREE_CODE (lhs
) == SSA_NAME
1919 && ssa_name_has_boolean_range (lhs
)
1920 && TREE_CODE (rhs
) == INTEGER_CST
1921 && ! (integer_zerop (rhs
) || integer_onep (rhs
)))
1923 gimple_cond_set_lhs (as_a
<gcond
*> (stmt
),
1924 fold_convert (TREE_TYPE (lhs
),
1925 integer_zero_node
));
1926 gimple_set_modified (stmt
, true);
1930 update_stmt_if_modified (stmt
);
1931 eliminate_redundant_computations (&si
, m_const_and_copies
,
1932 m_avail_exprs_stack
);
1933 stmt
= gsi_stmt (si
);
1935 /* Perform simple redundant store elimination. */
1936 if (gimple_assign_single_p (stmt
)
1937 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
1939 tree lhs
= gimple_assign_lhs (stmt
);
1940 tree rhs
= gimple_assign_rhs1 (stmt
);
1943 rhs
= dom_valueize (rhs
);
1944 /* Build a new statement with the RHS and LHS exchanged. */
1945 if (TREE_CODE (rhs
) == SSA_NAME
)
1947 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1948 new_stmt
= gimple_build_assign (rhs
, lhs
);
1949 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1952 new_stmt
= gimple_build_assign (rhs
, lhs
);
1953 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
1954 cached_lhs
= m_avail_exprs_stack
->lookup_avail_expr (new_stmt
, false,
1956 if (cached_lhs
&& operand_equal_p (rhs
, cached_lhs
, 0))
1958 basic_block bb
= gimple_bb (stmt
);
1959 unlink_stmt_vdef (stmt
);
1960 if (gsi_remove (&si
, true))
1962 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1964 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1966 release_defs (stmt
);
1971 /* If this statement was not redundant, we may still be able to simplify
1972 it, which may in turn allow other part of DOM or other passes to do
1974 test_for_singularity (stmt
, m_dummy_cond
, m_avail_exprs_stack
);
1977 /* Record any additional equivalences created by this statement. */
1978 if (is_gimple_assign (stmt
))
1979 record_equivalences_from_stmt (stmt
, may_optimize_p
, m_avail_exprs_stack
);
1981 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
1982 know where it goes. */
1983 if (gimple_modified_p (stmt
) || modified_p
)
1987 if (gimple_code (stmt
) == GIMPLE_COND
)
1988 val
= fold_binary_loc (gimple_location (stmt
),
1989 gimple_cond_code (stmt
), boolean_type_node
,
1990 gimple_cond_lhs (stmt
),
1991 gimple_cond_rhs (stmt
));
1992 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1993 val
= gimple_switch_index (swtch_stmt
);
1995 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1997 retval
= find_taken_edge (bb
, val
);
2000 /* Fix the condition to be either true or false. */
2001 if (gimple_code (stmt
) == GIMPLE_COND
)
2003 if (integer_zerop (val
))
2004 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
2005 else if (integer_onep (val
))
2006 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
2010 gimple_set_modified (stmt
, true);
2013 /* Further simplifications may be possible. */
2018 update_stmt_if_modified (stmt
);
2020 /* If we simplified a statement in such a way as to be shown that it
2021 cannot trap, update the eh information and the cfg to match. */
2022 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
2024 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2026 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2030 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
2031 need_noreturn_fixup
.safe_push (stmt
);