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 "gimple-iterator.h"
37 #include "tree-into-ssa.h"
39 #include "tree-ssa-propagate.h"
40 #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"
49 /* This file implements optimizations on the dominator tree. */
51 /* Structure for recording edge equivalences.
53 Computing and storing the edge equivalences instead of creating
54 them on-demand can save significant amounts of time, particularly
55 for pathological cases involving switch statements.
57 These structures live for a single iteration of the dominator
58 optimizer in the edge's AUX field. At the end of an iteration we
59 free each of these structures. */
63 /* If this edge creates a simple equivalence, the LHS and RHS of
64 the equivalence will be stored here. */
68 /* Traversing an edge may also indicate one or more particular conditions
70 vec
<cond_equivalence
> cond_equivalences
;
73 /* Track whether or not we have changed the control flow graph. */
74 static bool cfg_altered
;
76 /* Bitmap of blocks that have had EH statements cleaned. We should
77 remove their dead edges eventually. */
78 static bitmap need_eh_cleanup
;
79 static vec
<gimple
*> need_noreturn_fixup
;
81 /* Statistics for dominator optimizations. */
85 long num_exprs_considered
;
91 static struct opt_stats_d opt_stats
;
93 /* Local functions. */
94 static edge
optimize_stmt (basic_block
, gimple_stmt_iterator
,
95 class const_and_copies
*,
96 class avail_exprs_stack
*);
97 static void record_equality (tree
, tree
, class const_and_copies
*);
98 static void record_equivalences_from_phis (basic_block
);
99 static void record_equivalences_from_incoming_edge (basic_block
,
100 class const_and_copies
*,
101 class avail_exprs_stack
*);
102 static void eliminate_redundant_computations (gimple_stmt_iterator
*,
103 class const_and_copies
*,
104 class avail_exprs_stack
*);
105 static void record_equivalences_from_stmt (gimple
*, int,
106 class avail_exprs_stack
*);
107 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
108 static void dump_dominator_optimization_stats (FILE *file
,
109 hash_table
<expr_elt_hasher
> *);
112 /* Free the edge_info data attached to E, if it exists. */
115 free_dom_edge_info (edge e
)
117 struct edge_info
*edge_info
= (struct edge_info
*)e
->aux
;
121 edge_info
->cond_equivalences
.release ();
126 /* Allocate an EDGE_INFO for edge E and attach it to E.
127 Return the new EDGE_INFO structure. */
129 static struct edge_info
*
130 allocate_edge_info (edge e
)
132 struct edge_info
*edge_info
;
134 /* Free the old one, if it exists. */
135 free_dom_edge_info (e
);
137 edge_info
= XCNEW (struct edge_info
);
143 /* Free all EDGE_INFO structures associated with edges in the CFG.
144 If a particular edge can be threaded, copy the redirection
145 target from the EDGE_INFO structure into the edge's AUX field
146 as required by code to update the CFG and SSA graph for
150 free_all_edge_infos (void)
156 FOR_EACH_BB_FN (bb
, cfun
)
158 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
160 free_dom_edge_info (e
);
166 /* We have finished optimizing BB, record any information implied by
167 taking a specific outgoing edge from BB. */
170 record_edge_info (basic_block bb
)
172 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
173 struct edge_info
*edge_info
;
175 if (! gsi_end_p (gsi
))
177 gimple
*stmt
= gsi_stmt (gsi
);
178 location_t loc
= gimple_location (stmt
);
180 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
182 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
183 tree index
= gimple_switch_index (switch_stmt
);
185 if (TREE_CODE (index
) == SSA_NAME
)
188 int n_labels
= gimple_switch_num_labels (switch_stmt
);
189 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
193 for (i
= 0; i
< n_labels
; i
++)
195 tree label
= gimple_switch_label (switch_stmt
, i
);
196 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
197 if (CASE_HIGH (label
)
199 || info
[target_bb
->index
])
200 info
[target_bb
->index
] = error_mark_node
;
202 info
[target_bb
->index
] = label
;
205 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
207 basic_block target_bb
= e
->dest
;
208 tree label
= info
[target_bb
->index
];
210 if (label
!= NULL
&& label
!= error_mark_node
)
212 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
214 edge_info
= allocate_edge_info (e
);
215 edge_info
->lhs
= index
;
223 /* A COND_EXPR may create equivalences too. */
224 if (gimple_code (stmt
) == GIMPLE_COND
)
229 tree op0
= gimple_cond_lhs (stmt
);
230 tree op1
= gimple_cond_rhs (stmt
);
231 enum tree_code code
= gimple_cond_code (stmt
);
233 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
235 /* Special case comparing booleans against a constant as we
236 know the value of OP0 on both arms of the branch. i.e., we
237 can record an equivalence for OP0 rather than COND.
239 However, don't do this if the constant isn't zero or one.
240 Such conditionals will get optimized more thoroughly during
242 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
243 && TREE_CODE (op0
) == SSA_NAME
244 && ssa_name_has_boolean_range (op0
)
245 && is_gimple_min_invariant (op1
)
246 && (integer_zerop (op1
) || integer_onep (op1
)))
248 tree true_val
= constant_boolean_node (true, TREE_TYPE (op0
));
249 tree false_val
= constant_boolean_node (false, TREE_TYPE (op0
));
253 edge_info
= allocate_edge_info (true_edge
);
254 edge_info
->lhs
= op0
;
255 edge_info
->rhs
= (integer_zerop (op1
) ? false_val
: true_val
);
257 edge_info
= allocate_edge_info (false_edge
);
258 edge_info
->lhs
= op0
;
259 edge_info
->rhs
= (integer_zerop (op1
) ? true_val
: false_val
);
263 edge_info
= allocate_edge_info (true_edge
);
264 edge_info
->lhs
= op0
;
265 edge_info
->rhs
= (integer_zerop (op1
) ? true_val
: false_val
);
267 edge_info
= allocate_edge_info (false_edge
);
268 edge_info
->lhs
= op0
;
269 edge_info
->rhs
= (integer_zerop (op1
) ? false_val
: true_val
);
272 else if (is_gimple_min_invariant (op0
)
273 && (TREE_CODE (op1
) == SSA_NAME
274 || is_gimple_min_invariant (op1
)))
276 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
277 tree inverted
= invert_truthvalue_loc (loc
, cond
);
278 bool can_infer_simple_equiv
279 = !(HONOR_SIGNED_ZEROS (op0
)
280 && real_zerop (op0
));
281 struct edge_info
*edge_info
;
283 edge_info
= allocate_edge_info (true_edge
);
284 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
286 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
288 edge_info
->lhs
= op1
;
289 edge_info
->rhs
= op0
;
292 edge_info
= allocate_edge_info (false_edge
);
293 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
295 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
297 edge_info
->lhs
= op1
;
298 edge_info
->rhs
= op0
;
302 else if (TREE_CODE (op0
) == SSA_NAME
303 && (TREE_CODE (op1
) == SSA_NAME
304 || is_gimple_min_invariant (op1
)))
306 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
307 tree inverted
= invert_truthvalue_loc (loc
, cond
);
308 bool can_infer_simple_equiv
309 = !(HONOR_SIGNED_ZEROS (op1
)
310 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
311 struct edge_info
*edge_info
;
313 edge_info
= allocate_edge_info (true_edge
);
314 record_conditions (&edge_info
->cond_equivalences
, cond
, inverted
);
316 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
318 edge_info
->lhs
= op0
;
319 edge_info
->rhs
= op1
;
322 edge_info
= allocate_edge_info (false_edge
);
323 record_conditions (&edge_info
->cond_equivalences
, inverted
, cond
);
325 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
327 edge_info
->lhs
= op0
;
328 edge_info
->rhs
= op1
;
333 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
338 class dom_opt_dom_walker
: public dom_walker
341 dom_opt_dom_walker (cdi_direction direction
,
342 class const_and_copies
*const_and_copies
,
343 class avail_exprs_stack
*avail_exprs_stack
)
344 : dom_walker (direction
, true),
345 m_const_and_copies (const_and_copies
),
346 m_avail_exprs_stack (avail_exprs_stack
),
347 m_dummy_cond (NULL
) {}
349 virtual edge
before_dom_children (basic_block
);
350 virtual void after_dom_children (basic_block
);
354 /* Unwindable equivalences, both const/copy and expression varieties. */
355 class const_and_copies
*m_const_and_copies
;
356 class avail_exprs_stack
*m_avail_exprs_stack
;
361 /* Jump threading, redundancy elimination and const/copy propagation.
363 This pass may expose new symbols that need to be renamed into SSA. For
364 every new symbol exposed, its corresponding bit will be set in
369 const pass_data pass_data_dominator
=
371 GIMPLE_PASS
, /* type */
373 OPTGROUP_NONE
, /* optinfo_flags */
374 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
375 ( PROP_cfg
| PROP_ssa
), /* properties_required */
376 0, /* properties_provided */
377 0, /* properties_destroyed */
378 0, /* todo_flags_start */
379 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
382 class pass_dominator
: public gimple_opt_pass
385 pass_dominator (gcc::context
*ctxt
)
386 : gimple_opt_pass (pass_data_dominator
, ctxt
),
387 may_peel_loop_headers_p (false)
390 /* opt_pass methods: */
391 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
392 void set_pass_param (unsigned int n
, bool param
)
395 may_peel_loop_headers_p
= param
;
397 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
398 virtual unsigned int execute (function
*);
401 /* This flag is used to prevent loops from being peeled repeatedly in jump
402 threading; it will be removed once we preserve loop structures throughout
403 the compilation -- we will be able to mark the affected loops directly in
404 jump threading, and avoid peeling them next time. */
405 bool may_peel_loop_headers_p
;
406 }; // class pass_dominator
409 pass_dominator::execute (function
*fun
)
411 memset (&opt_stats
, 0, sizeof (opt_stats
));
413 /* Create our hash tables. */
414 hash_table
<expr_elt_hasher
> *avail_exprs
415 = new hash_table
<expr_elt_hasher
> (1024);
416 class avail_exprs_stack
*avail_exprs_stack
417 = new class avail_exprs_stack (avail_exprs
);
418 class const_and_copies
*const_and_copies
= new class const_and_copies ();
419 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
420 need_noreturn_fixup
.create (0);
422 calculate_dominance_info (CDI_DOMINATORS
);
425 /* We need to know loop structures in order to avoid destroying them
426 in jump threading. Note that we still can e.g. thread through loop
427 headers to an exit edge, or through loop header to the loop body, assuming
428 that we update the loop info.
430 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
431 to several overly conservative bail-outs in jump threading, case
432 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
433 missing. We should improve jump threading in future then
434 LOOPS_HAVE_PREHEADERS won't be needed here. */
435 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
437 /* Initialize the value-handle array. */
438 threadedge_initialize_values ();
440 /* We need accurate information regarding back edges in the CFG
441 for jump threading; this may include back edges that are not part of
443 mark_dfs_back_edges ();
445 /* We want to create the edge info structures before the dominator walk
446 so that they'll be in place for the jump threader, particularly when
447 threading through a join block.
449 The conditions will be lazily updated with global equivalences as
450 we reach them during the dominator walk. */
452 FOR_EACH_BB_FN (bb
, fun
)
453 record_edge_info (bb
);
455 /* Recursively walk the dominator tree optimizing statements. */
456 dom_opt_dom_walker
walker (CDI_DOMINATORS
,
459 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
461 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
462 edge. When found, remove jump threads which contain any outgoing
463 edge from the affected block. */
466 FOR_EACH_BB_FN (bb
, fun
)
471 /* First see if there are any edges without EDGE_EXECUTABLE
474 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
476 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
483 /* If there were any such edges found, then remove jump threads
484 containing any edge leaving BB. */
486 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
487 remove_jump_threads_including (e
);
492 gimple_stmt_iterator gsi
;
494 FOR_EACH_BB_FN (bb
, fun
)
496 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
497 update_stmt_if_modified (gsi_stmt (gsi
));
501 /* If we exposed any new variables, go ahead and put them into
502 SSA form now, before we handle jump threading. This simplifies
503 interactions between rewriting of _DECL nodes into SSA form
504 and rewriting SSA_NAME nodes into SSA form after block
505 duplication and CFG manipulation. */
506 update_ssa (TODO_update_ssa
);
508 free_all_edge_infos ();
510 /* Thread jumps, creating duplicate blocks as needed. */
511 cfg_altered
|= thread_through_all_blocks (may_peel_loop_headers_p
);
514 free_dominance_info (CDI_DOMINATORS
);
516 /* Removal of statements may make some EH edges dead. Purge
517 such edges from the CFG as needed. */
518 if (!bitmap_empty_p (need_eh_cleanup
))
523 /* Jump threading may have created forwarder blocks from blocks
524 needing EH cleanup; the new successor of these blocks, which
525 has inherited from the original block, needs the cleanup.
526 Don't clear bits in the bitmap, as that can break the bitmap
528 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
530 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
533 while (single_succ_p (bb
)
534 && (single_succ_edge (bb
)->flags
& EDGE_EH
) == 0)
535 bb
= single_succ (bb
);
536 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
538 if ((unsigned) bb
->index
!= i
)
539 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
542 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
543 bitmap_clear (need_eh_cleanup
);
546 /* Fixup stmts that became noreturn calls. This may require splitting
547 blocks and thus isn't possible during the dominator walk or before
548 jump threading finished. Do this in reverse order so we don't
549 inadvertedly remove a stmt we want to fixup by visiting a dominating
550 now noreturn call first. */
551 while (!need_noreturn_fixup
.is_empty ())
553 gimple
*stmt
= need_noreturn_fixup
.pop ();
554 if (dump_file
&& dump_flags
& TDF_DETAILS
)
556 fprintf (dump_file
, "Fixing up noreturn call ");
557 print_gimple_stmt (dump_file
, stmt
, 0, 0);
558 fprintf (dump_file
, "\n");
560 fixup_noreturn_call (stmt
);
563 statistics_counter_event (fun
, "Redundant expressions eliminated",
565 statistics_counter_event (fun
, "Constants propagated",
566 opt_stats
.num_const_prop
);
567 statistics_counter_event (fun
, "Copies propagated",
568 opt_stats
.num_copy_prop
);
570 /* Debugging dumps. */
571 if (dump_file
&& (dump_flags
& TDF_STATS
))
572 dump_dominator_optimization_stats (dump_file
, avail_exprs
);
574 loop_optimizer_finalize ();
576 /* Delete our main hashtable. */
580 /* Free asserted bitmaps and stacks. */
581 BITMAP_FREE (need_eh_cleanup
);
582 need_noreturn_fixup
.release ();
583 delete avail_exprs_stack
;
584 delete const_and_copies
;
586 /* Free the value-handle array. */
587 threadedge_finalize_values ();
595 make_pass_dominator (gcc::context
*ctxt
)
597 return new pass_dominator (ctxt
);
601 /* A trivial wrapper so that we can present the generic jump
602 threading code with a simple API for simplifying statements. */
604 simplify_stmt_for_jump_threading (gimple
*stmt
,
605 gimple
*within_stmt ATTRIBUTE_UNUSED
,
606 class avail_exprs_stack
*avail_exprs_stack
,
607 basic_block bb ATTRIBUTE_UNUSED
)
609 return avail_exprs_stack
->lookup_avail_expr (stmt
, false, true);
612 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
615 dom_valueize (tree t
)
617 if (TREE_CODE (t
) == SSA_NAME
)
619 tree tem
= SSA_NAME_VALUE (t
);
626 /* We have just found an equivalence for LHS on an edge E.
627 Look backwards to other uses of LHS and see if we can derive
628 additional equivalences that are valid on edge E. */
630 back_propagate_equivalences (tree lhs
, edge e
,
631 class const_and_copies
*const_and_copies
)
634 imm_use_iterator iter
;
636 basic_block dest
= e
->dest
;
638 /* Iterate over the uses of LHS to see if any dominate E->dest.
639 If so, they may create useful equivalences too.
641 ??? If the code gets re-organized to a worklist to catch more
642 indirect opportunities and it is made to handle PHIs then this
643 should only consider use_stmts in basic-blocks we have already visited. */
644 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
646 gimple
*use_stmt
= USE_STMT (use_p
);
648 /* Often the use is in DEST, which we trivially know we can't use.
649 This is cheaper than the dominator set tests below. */
650 if (dest
== gimple_bb (use_stmt
))
653 /* Filter out statements that can never produce a useful
655 tree lhs2
= gimple_get_lhs (use_stmt
);
656 if (!lhs2
|| TREE_CODE (lhs2
) != SSA_NAME
)
659 /* Profiling has shown the domination tests here can be fairly
660 expensive. We get significant improvements by building the
661 set of blocks that dominate BB. We can then just test
662 for set membership below.
664 We also initialize the set lazily since often the only uses
665 are going to be in the same block as DEST. */
668 domby
= BITMAP_ALLOC (NULL
);
669 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
672 bitmap_set_bit (domby
, bb
->index
);
673 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
677 /* This tests if USE_STMT does not dominate DEST. */
678 if (!bitmap_bit_p (domby
, gimple_bb (use_stmt
)->index
))
681 /* At this point USE_STMT dominates DEST and may result in a
682 useful equivalence. Try to simplify its RHS to a constant
684 tree res
= gimple_fold_stmt_to_constant_1 (use_stmt
, dom_valueize
,
685 no_follow_ssa_edges
);
686 if (res
&& (TREE_CODE (res
) == SSA_NAME
|| is_gimple_min_invariant (res
)))
687 record_equality (lhs2
, res
, const_and_copies
);
694 /* Record NAME has the value zero and if NAME was set from a BIT_IOR_EXPR
695 recurse into both operands recording their values as zero too. */
698 derive_equivalencs_from_bit_ior (tree name
, const_and_copies
*const_and_copies
)
700 if (TREE_CODE (name
) == SSA_NAME
)
702 tree value
= fold_convert (TREE_TYPE (name
), integer_zero_node
);
704 /* This records the equivalence for the toplevel object. */
705 record_equality (name
, value
, const_and_copies
);
707 /* And we can recurse into each operand to potentially find more
709 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
710 if (is_gimple_assign (def_stmt
)
711 && gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
713 derive_equivalencs_from_bit_ior (gimple_assign_rhs1 (def_stmt
),
715 derive_equivalencs_from_bit_ior (gimple_assign_rhs2 (def_stmt
),
721 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
722 by traversing edge E (which are cached in E->aux).
724 Callers are responsible for managing the unwinding markers. */
726 record_temporary_equivalences (edge e
,
727 class const_and_copies
*const_and_copies
,
728 class avail_exprs_stack
*avail_exprs_stack
)
731 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
733 /* If we have info associated with this edge, record it into
734 our equivalence tables. */
737 cond_equivalence
*eq
;
738 /* If we have 0 = COND or 1 = COND equivalences, record them
739 into our expression hash tables. */
740 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
742 avail_exprs_stack
->record_cond (eq
);
744 /* If the condition is testing that X == 0 is true or X != 0 is false
745 and X is set from a BIT_IOR_EXPR, then we can record equivalences
746 for the operands of the BIT_IOR_EXPR (and recurse on those). */
747 tree op0
= eq
->cond
.ops
.binary
.opnd0
;
748 tree op1
= eq
->cond
.ops
.binary
.opnd1
;
749 if (TREE_CODE (op0
) == SSA_NAME
&& integer_zerop (op1
))
751 enum tree_code code
= eq
->cond
.ops
.binary
.op
;
752 if ((code
== EQ_EXPR
&& eq
->value
== boolean_true_node
)
753 || (code
== NE_EXPR
&& eq
->value
== boolean_false_node
))
754 derive_equivalencs_from_bit_ior (op0
, const_and_copies
);
756 /* TODO: We could handle BIT_AND_EXPR in a similar fashion
757 recording that the operands have a nonzero value. */
759 /* TODO: We can handle more cases here, particularly when OP0 is
760 known to have a boolean range. */
764 tree lhs
= edge_info
->lhs
;
765 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
)
768 /* Record the simple NAME = VALUE equivalence. */
769 tree rhs
= edge_info
->rhs
;
770 record_equality (lhs
, rhs
, const_and_copies
);
772 /* We already recorded that LHS = RHS, with canonicalization,
773 value chain following, etc.
775 We also want to record RHS = LHS, but without any canonicalization
776 or value chain following. */
777 if (TREE_CODE (rhs
) == SSA_NAME
)
778 const_and_copies
->record_const_or_copy_raw (rhs
, lhs
,
779 SSA_NAME_VALUE (rhs
));
781 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
782 set via a widening type conversion, then we may be able to record
783 additional equivalences. */
784 if (TREE_CODE (rhs
) == INTEGER_CST
)
786 gimple
*defstmt
= SSA_NAME_DEF_STMT (lhs
);
789 && is_gimple_assign (defstmt
)
790 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt
)))
792 tree old_rhs
= gimple_assign_rhs1 (defstmt
);
794 /* If the conversion widens the original value and
795 the constant is in the range of the type of OLD_RHS,
796 then convert the constant and record the equivalence.
798 Note that int_fits_type_p does not check the precision
799 if the upper and lower bounds are OK. */
800 if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs
))
801 && (TYPE_PRECISION (TREE_TYPE (lhs
))
802 > TYPE_PRECISION (TREE_TYPE (old_rhs
)))
803 && int_fits_type_p (rhs
, TREE_TYPE (old_rhs
)))
805 tree newval
= fold_convert (TREE_TYPE (old_rhs
), rhs
);
806 record_equality (old_rhs
, newval
, const_and_copies
);
811 /* Any equivalence found for LHS may result in additional
812 equivalences for other uses of LHS that we have already
814 back_propagate_equivalences (lhs
, e
, const_and_copies
);
818 /* PHI nodes can create equivalences too.
820 Ignoring any alternatives which are the same as the result, if
821 all the alternatives are equal, then the PHI node creates an
825 record_equivalences_from_phis (basic_block bb
)
829 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
831 gphi
*phi
= gsi
.phi ();
833 tree lhs
= gimple_phi_result (phi
);
837 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
839 tree t
= gimple_phi_arg_def (phi
, i
);
841 /* Ignore alternatives which are the same as our LHS. Since
842 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
843 can simply compare pointers. */
847 /* If the associated edge is not marked as executable, then it
849 if ((gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_EXECUTABLE
) == 0)
852 t
= dom_valueize (t
);
854 /* If we have not processed an alternative yet, then set
855 RHS to this alternative. */
858 /* If we have processed an alternative (stored in RHS), then
859 see if it is equal to this one. If it isn't, then stop
861 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
865 /* If we had no interesting alternatives, then all the RHS alternatives
866 must have been the same as LHS. */
870 /* If we managed to iterate through each PHI alternative without
871 breaking out of the loop, then we have a PHI which may create
872 a useful equivalence. We do not need to record unwind data for
873 this, since this is a true assignment and not an equivalence
874 inferred from a comparison. All uses of this ssa name are dominated
875 by this assignment, so unwinding just costs time and space. */
876 if (i
== gimple_phi_num_args (phi
)
877 && may_propagate_copy (lhs
, rhs
))
878 set_ssa_name_value (lhs
, rhs
);
882 /* Ignoring loop backedges, if BB has precisely one incoming edge then
883 return that edge. Otherwise return NULL. */
885 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
891 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
893 /* A loop back edge can be identified by the destination of
894 the edge dominating the source of the edge. */
895 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
898 /* We can safely ignore edges that are not executable. */
899 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
902 /* If we have already seen a non-loop edge, then we must have
903 multiple incoming non-loop edges and thus we return NULL. */
907 /* This is the first non-loop incoming edge we have found. Record
915 /* Record any equivalences created by the incoming edge to BB into
916 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
917 incoming edge, then no equivalence is created. */
920 record_equivalences_from_incoming_edge (basic_block bb
,
921 class const_and_copies
*const_and_copies
,
922 class avail_exprs_stack
*avail_exprs_stack
)
927 /* If our parent block ended with a control statement, then we may be
928 able to record some equivalences based on which outgoing edge from
929 the parent was followed. */
930 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
932 e
= single_incoming_edge_ignoring_loop_edges (bb
);
934 /* If we had a single incoming edge from our parent block, then enter
935 any data associated with the edge into our tables. */
936 if (e
&& e
->src
== parent
)
937 record_temporary_equivalences (e
, const_and_copies
, avail_exprs_stack
);
940 /* Dump statistics for the hash table HTAB. */
943 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
945 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
947 (long) htab
.elements (),
951 /* Dump SSA statistics on FILE. */
954 dump_dominator_optimization_stats (FILE *file
,
955 hash_table
<expr_elt_hasher
> *avail_exprs
)
957 fprintf (file
, "Total number of statements: %6ld\n\n",
958 opt_stats
.num_stmts
);
959 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
960 opt_stats
.num_exprs_considered
);
962 fprintf (file
, "\nHash table statistics:\n");
964 fprintf (file
, " avail_exprs: ");
965 htab_statistics (file
, *avail_exprs
);
969 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
970 This constrains the cases in which we may treat this as assignment. */
973 record_equality (tree x
, tree y
, class const_and_copies
*const_and_copies
)
975 tree prev_x
= NULL
, prev_y
= NULL
;
977 if (tree_swap_operands_p (x
, y
))
980 /* Most of the time tree_swap_operands_p does what we want. But there
981 are cases where we know one operand is better for copy propagation than
982 the other. Given no other code cares about ordering of equality
983 comparison operators for that purpose, we just handle the special cases
985 if (TREE_CODE (x
) == SSA_NAME
&& TREE_CODE (y
) == SSA_NAME
)
987 /* If one operand is a single use operand, then make it
988 X. This will preserve its single use properly and if this
989 conditional is eliminated, the computation of X can be
990 eliminated as well. */
991 if (has_single_use (y
) && ! has_single_use (x
))
994 if (TREE_CODE (x
) == SSA_NAME
)
995 prev_x
= SSA_NAME_VALUE (x
);
996 if (TREE_CODE (y
) == SSA_NAME
)
997 prev_y
= SSA_NAME_VALUE (y
);
999 /* If one of the previous values is invariant, or invariant in more loops
1000 (by depth), then use that.
1001 Otherwise it doesn't matter which value we choose, just so
1002 long as we canonicalize on one value. */
1003 if (is_gimple_min_invariant (y
))
1005 else if (is_gimple_min_invariant (x
))
1006 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1007 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1008 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1012 /* After the swapping, we must have one SSA_NAME. */
1013 if (TREE_CODE (x
) != SSA_NAME
)
1016 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1017 variable compared against zero. If we're honoring signed zeros,
1018 then we cannot record this value unless we know that the value is
1020 if (HONOR_SIGNED_ZEROS (x
)
1021 && (TREE_CODE (y
) != REAL_CST
1022 || real_equal (&dconst0
, &TREE_REAL_CST (y
))))
1025 const_and_copies
->record_const_or_copy (x
, y
, prev_x
);
1028 /* Returns true when STMT is a simple iv increment. It detects the
1029 following situation:
1031 i_1 = phi (..., i_2)
1032 i_2 = i_1 +/- ... */
1035 simple_iv_increment_p (gimple
*stmt
)
1037 enum tree_code code
;
1042 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1045 lhs
= gimple_assign_lhs (stmt
);
1046 if (TREE_CODE (lhs
) != SSA_NAME
)
1049 code
= gimple_assign_rhs_code (stmt
);
1050 if (code
!= PLUS_EXPR
1051 && code
!= MINUS_EXPR
1052 && code
!= POINTER_PLUS_EXPR
)
1055 preinc
= gimple_assign_rhs1 (stmt
);
1056 if (TREE_CODE (preinc
) != SSA_NAME
)
1059 phi
= SSA_NAME_DEF_STMT (preinc
);
1060 if (gimple_code (phi
) != GIMPLE_PHI
)
1063 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1064 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1070 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1071 successors of BB. */
1074 cprop_into_successor_phis (basic_block bb
,
1075 class const_and_copies
*const_and_copies
)
1080 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1085 /* If this is an abnormal edge, then we do not want to copy propagate
1086 into the PHI alternative associated with this edge. */
1087 if (e
->flags
& EDGE_ABNORMAL
)
1090 gsi
= gsi_start_phis (e
->dest
);
1091 if (gsi_end_p (gsi
))
1094 /* We may have an equivalence associated with this edge. While
1095 we can not propagate it into non-dominated blocks, we can
1096 propagate them into PHIs in non-dominated blocks. */
1098 /* Push the unwind marker so we can reset the const and copies
1099 table back to its original state after processing this edge. */
1100 const_and_copies
->push_marker ();
1102 /* Extract and record any simple NAME = VALUE equivalences.
1104 Don't bother with [01] = COND equivalences, they're not useful
1106 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
1109 tree lhs
= edge_info
->lhs
;
1110 tree rhs
= edge_info
->rhs
;
1112 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1113 const_and_copies
->record_const_or_copy (lhs
, rhs
);
1117 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1120 use_operand_p orig_p
;
1122 gphi
*phi
= gsi
.phi ();
1124 /* The alternative may be associated with a constant, so verify
1125 it is an SSA_NAME before doing anything with it. */
1126 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1127 orig_val
= get_use_from_ptr (orig_p
);
1128 if (TREE_CODE (orig_val
) != SSA_NAME
)
1131 /* If we have *ORIG_P in our constant/copy table, then replace
1132 ORIG_P with its value in our constant/copy table. */
1133 new_val
= SSA_NAME_VALUE (orig_val
);
1135 && new_val
!= orig_val
1136 && may_propagate_copy (orig_val
, new_val
))
1137 propagate_value (orig_p
, new_val
);
1140 const_and_copies
->pop_to_marker ();
1145 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1147 gimple_stmt_iterator gsi
;
1149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1150 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1152 /* Push a marker on the stacks of local information so that we know how
1153 far to unwind when we finalize this block. */
1154 m_avail_exprs_stack
->push_marker ();
1155 m_const_and_copies
->push_marker ();
1157 record_equivalences_from_incoming_edge (bb
, m_const_and_copies
,
1158 m_avail_exprs_stack
);
1160 /* PHI nodes can create equivalences too. */
1161 record_equivalences_from_phis (bb
);
1163 /* Create equivalences from redundant PHIs. PHIs are only truly
1164 redundant when they exist in the same block, so push another
1165 marker and unwind right afterwards. */
1166 m_avail_exprs_stack
->push_marker ();
1167 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1168 eliminate_redundant_computations (&gsi
, m_const_and_copies
,
1169 m_avail_exprs_stack
);
1170 m_avail_exprs_stack
->pop_to_marker ();
1172 edge taken_edge
= NULL
;
1173 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1175 = optimize_stmt (bb
, gsi
, m_const_and_copies
, m_avail_exprs_stack
);
1177 /* Now prepare to process dominated blocks. */
1178 record_edge_info (bb
);
1179 cprop_into_successor_phis (bb
, m_const_and_copies
);
1180 if (taken_edge
&& !dbg_cnt (dom_unreachable_edges
))
1186 /* We have finished processing the dominator children of BB, perform
1187 any finalization actions in preparation for leaving this node in
1188 the dominator tree. */
1191 dom_opt_dom_walker::after_dom_children (basic_block bb
)
1194 m_dummy_cond
= gimple_build_cond (NE_EXPR
, integer_zero_node
,
1195 integer_zero_node
, NULL
, NULL
);
1197 thread_outgoing_edges (bb
, m_dummy_cond
, m_const_and_copies
,
1198 m_avail_exprs_stack
,
1199 simplify_stmt_for_jump_threading
);
1201 /* These remove expressions local to BB from the tables. */
1202 m_avail_exprs_stack
->pop_to_marker ();
1203 m_const_and_copies
->pop_to_marker ();
1206 /* Search for redundant computations in STMT. If any are found, then
1207 replace them with the variable holding the result of the computation.
1209 If safe, record this expression into AVAIL_EXPRS_STACK and
1210 CONST_AND_COPIES. */
1213 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
,
1214 class const_and_copies
*const_and_copies
,
1215 class avail_exprs_stack
*avail_exprs_stack
)
1221 bool assigns_var_p
= false;
1223 gimple
*stmt
= gsi_stmt (*gsi
);
1225 if (gimple_code (stmt
) == GIMPLE_PHI
)
1226 def
= gimple_phi_result (stmt
);
1228 def
= gimple_get_lhs (stmt
);
1230 /* Certain expressions on the RHS can be optimized away, but can not
1231 themselves be entered into the hash tables. */
1233 || TREE_CODE (def
) != SSA_NAME
1234 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1235 || gimple_vdef (stmt
)
1236 /* Do not record equivalences for increments of ivs. This would create
1237 overlapping live ranges for a very questionable gain. */
1238 || simple_iv_increment_p (stmt
))
1241 /* Check if the expression has been computed before. */
1242 cached_lhs
= avail_exprs_stack
->lookup_avail_expr (stmt
, insert
, true);
1244 opt_stats
.num_exprs_considered
++;
1246 /* Get the type of the expression we are trying to optimize. */
1247 if (is_gimple_assign (stmt
))
1249 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1250 assigns_var_p
= true;
1252 else if (gimple_code (stmt
) == GIMPLE_COND
)
1253 expr_type
= boolean_type_node
;
1254 else if (is_gimple_call (stmt
))
1256 gcc_assert (gimple_call_lhs (stmt
));
1257 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1258 assigns_var_p
= true;
1260 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1261 expr_type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
1262 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1263 /* We can't propagate into a phi, so the logic below doesn't apply.
1264 Instead record an equivalence between the cached LHS and the
1265 PHI result of this statement, provided they are in the same block.
1266 This should be sufficient to kill the redundant phi. */
1268 if (def
&& cached_lhs
)
1269 const_and_copies
->record_const_or_copy (def
, cached_lhs
);
1278 /* It is safe to ignore types here since we have already done
1279 type checking in the hashing and equality routines. In fact
1280 type checking here merely gets in the way of constant
1281 propagation. Also, make sure that it is safe to propagate
1282 CACHED_LHS into the expression in STMT. */
1283 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1285 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1286 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1288 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1289 || is_gimple_min_invariant (cached_lhs
));
1291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1293 fprintf (dump_file
, " Replaced redundant expr '");
1294 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1295 fprintf (dump_file
, "' with '");
1296 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1297 fprintf (dump_file
, "'\n");
1303 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1304 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1306 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1308 /* Since it is always necessary to mark the result as modified,
1309 perhaps we should move this into propagate_tree_value_into_stmt
1311 gimple_set_modified (gsi_stmt (*gsi
), true);
1315 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1316 the available expressions table or the const_and_copies table.
1317 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1319 We handle only very simple copy equivalences here. The heavy
1320 lifing is done by eliminate_redundant_computations. */
1323 record_equivalences_from_stmt (gimple
*stmt
, int may_optimize_p
,
1324 class avail_exprs_stack
*avail_exprs_stack
)
1327 enum tree_code lhs_code
;
1329 gcc_assert (is_gimple_assign (stmt
));
1331 lhs
= gimple_assign_lhs (stmt
);
1332 lhs_code
= TREE_CODE (lhs
);
1334 if (lhs_code
== SSA_NAME
1335 && gimple_assign_single_p (stmt
))
1337 tree rhs
= gimple_assign_rhs1 (stmt
);
1339 /* If the RHS of the assignment is a constant or another variable that
1340 may be propagated, register it in the CONST_AND_COPIES table. We
1341 do not need to record unwind data for this, since this is a true
1342 assignment and not an equivalence inferred from a comparison. All
1343 uses of this ssa name are dominated by this assignment, so unwinding
1344 just costs time and space. */
1346 && (TREE_CODE (rhs
) == SSA_NAME
1347 || is_gimple_min_invariant (rhs
)))
1349 rhs
= dom_valueize (rhs
);
1351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1353 fprintf (dump_file
, "==== ASGN ");
1354 print_generic_expr (dump_file
, lhs
, 0);
1355 fprintf (dump_file
, " = ");
1356 print_generic_expr (dump_file
, rhs
, 0);
1357 fprintf (dump_file
, "\n");
1360 set_ssa_name_value (lhs
, rhs
);
1364 /* Make sure we can propagate &x + CST. */
1365 if (lhs_code
== SSA_NAME
1366 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1367 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
1368 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
1370 tree op0
= gimple_assign_rhs1 (stmt
);
1371 tree op1
= gimple_assign_rhs2 (stmt
);
1373 = build_fold_addr_expr (fold_build2 (MEM_REF
,
1374 TREE_TYPE (TREE_TYPE (op0
)),
1376 fold_convert (ptr_type_node
,
1378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1380 fprintf (dump_file
, "==== ASGN ");
1381 print_generic_expr (dump_file
, lhs
, 0);
1382 fprintf (dump_file
, " = ");
1383 print_generic_expr (dump_file
, new_rhs
, 0);
1384 fprintf (dump_file
, "\n");
1387 set_ssa_name_value (lhs
, new_rhs
);
1390 /* A memory store, even an aliased store, creates a useful
1391 equivalence. By exchanging the LHS and RHS, creating suitable
1392 vops and recording the result in the available expression table,
1393 we may be able to expose more redundant loads. */
1394 if (!gimple_has_volatile_ops (stmt
)
1395 && gimple_references_memory_p (stmt
)
1396 && gimple_assign_single_p (stmt
)
1397 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1398 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1399 && !is_gimple_reg (lhs
))
1401 tree rhs
= gimple_assign_rhs1 (stmt
);
1404 /* Build a new statement with the RHS and LHS exchanged. */
1405 if (TREE_CODE (rhs
) == SSA_NAME
)
1407 /* NOTE tuples. The call to gimple_build_assign below replaced
1408 a call to build_gimple_modify_stmt, which did not set the
1409 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1410 may cause an SSA validation failure, as the LHS may be a
1411 default-initialized name and should have no definition. I'm
1412 a bit dubious of this, as the artificial statement that we
1413 generate here may in fact be ill-formed, but it is simply
1414 used as an internal device in this pass, and never becomes
1416 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1417 new_stmt
= gimple_build_assign (rhs
, lhs
);
1418 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1421 new_stmt
= gimple_build_assign (rhs
, lhs
);
1423 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
1425 /* Finally enter the statement into the available expression
1427 avail_exprs_stack
->lookup_avail_expr (new_stmt
, true, true);
1431 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1432 CONST_AND_COPIES. */
1435 cprop_operand (gimple
*stmt
, use_operand_p op_p
)
1438 tree op
= USE_FROM_PTR (op_p
);
1440 /* If the operand has a known constant value or it is known to be a
1441 copy of some other variable, use the value or copy stored in
1442 CONST_AND_COPIES. */
1443 val
= SSA_NAME_VALUE (op
);
1444 if (val
&& val
!= op
)
1446 /* Do not replace hard register operands in asm statements. */
1447 if (gimple_code (stmt
) == GIMPLE_ASM
1448 && !may_propagate_copy_into_asm (op
))
1451 /* Certain operands are not allowed to be copy propagated due
1452 to their interaction with exception handling and some GCC
1454 if (!may_propagate_copy (op
, val
))
1457 /* Do not propagate copies into BIVs.
1458 See PR23821 and PR62217 for how this can disturb IV and
1459 number of iteration analysis. */
1460 if (TREE_CODE (val
) != INTEGER_CST
)
1462 gimple
*def
= SSA_NAME_DEF_STMT (op
);
1463 if (gimple_code (def
) == GIMPLE_PHI
1464 && gimple_bb (def
)->loop_father
->header
== gimple_bb (def
))
1469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1471 fprintf (dump_file
, " Replaced '");
1472 print_generic_expr (dump_file
, op
, dump_flags
);
1473 fprintf (dump_file
, "' with %s '",
1474 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1475 print_generic_expr (dump_file
, val
, dump_flags
);
1476 fprintf (dump_file
, "'\n");
1479 if (TREE_CODE (val
) != SSA_NAME
)
1480 opt_stats
.num_const_prop
++;
1482 opt_stats
.num_copy_prop
++;
1484 propagate_value (op_p
, val
);
1486 /* And note that we modified this statement. This is now
1487 safe, even if we changed virtual operands since we will
1488 rescan the statement and rewrite its operands again. */
1489 gimple_set_modified (stmt
, true);
1493 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1494 known value for that SSA_NAME (or NULL if no value is known).
1496 Propagate values from CONST_AND_COPIES into the uses, vuses and
1497 vdef_ops of STMT. */
1500 cprop_into_stmt (gimple
*stmt
)
1504 tree last_copy_propagated_op
= NULL
;
1506 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
1508 tree old_op
= USE_FROM_PTR (op_p
);
1510 /* If we have A = B and B = A in the copy propagation tables
1511 (due to an equality comparison), avoid substituting B for A
1512 then A for B in the trivially discovered cases. This allows
1513 optimization of statements were A and B appear as input
1515 if (old_op
!= last_copy_propagated_op
)
1517 cprop_operand (stmt
, op_p
);
1519 tree new_op
= USE_FROM_PTR (op_p
);
1520 if (new_op
!= old_op
&& TREE_CODE (new_op
) == SSA_NAME
)
1521 last_copy_propagated_op
= new_op
;
1526 /* Optimize the statement in block BB pointed to by iterator SI
1527 using equivalences from CONST_AND_COPIES and AVAIL_EXPRS_STACK.
1529 We try to perform some simplistic global redundancy elimination and
1530 constant propagation:
1532 1- To detect global redundancy, we keep track of expressions that have
1533 been computed in this block and its dominators. If we find that the
1534 same expression is computed more than once, we eliminate repeated
1535 computations by using the target of the first one.
1537 2- Constant values and copy assignments. This is used to do very
1538 simplistic constant and copy propagation. When a constant or copy
1539 assignment is found, we map the value on the RHS of the assignment to
1540 the variable in the LHS in the CONST_AND_COPIES table. */
1543 optimize_stmt (basic_block bb
, gimple_stmt_iterator si
,
1544 class const_and_copies
*const_and_copies
,
1545 class avail_exprs_stack
*avail_exprs_stack
)
1547 gimple
*stmt
, *old_stmt
;
1548 bool may_optimize_p
;
1549 bool modified_p
= false;
1553 old_stmt
= stmt
= gsi_stmt (si
);
1554 was_noreturn
= is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
);
1556 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1558 fprintf (dump_file
, "Optimizing statement ");
1559 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1562 update_stmt_if_modified (stmt
);
1563 opt_stats
.num_stmts
++;
1565 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1566 cprop_into_stmt (stmt
);
1568 /* If the statement has been modified with constant replacements,
1569 fold its RHS before checking for redundant computations. */
1570 if (gimple_modified_p (stmt
))
1574 /* Try to fold the statement making sure that STMT is kept
1576 if (fold_stmt (&si
))
1578 stmt
= gsi_stmt (si
);
1579 gimple_set_modified (stmt
, true);
1581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1583 fprintf (dump_file
, " Folded to: ");
1584 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1588 /* We only need to consider cases that can yield a gimple operand. */
1589 if (gimple_assign_single_p (stmt
))
1590 rhs
= gimple_assign_rhs1 (stmt
);
1591 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
1592 rhs
= gimple_goto_dest (stmt
);
1593 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1594 /* This should never be an ADDR_EXPR. */
1595 rhs
= gimple_switch_index (swtch_stmt
);
1597 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
1598 recompute_tree_invariant_for_addr_expr (rhs
);
1600 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1601 even if fold_stmt updated the stmt already and thus cleared
1602 gimple_modified_p flag on it. */
1606 /* Check for redundant computations. Do this optimization only
1607 for assignments that have no volatile ops and conditionals. */
1608 may_optimize_p
= (!gimple_has_side_effects (stmt
)
1609 && (is_gimple_assign (stmt
)
1610 || (is_gimple_call (stmt
)
1611 && gimple_call_lhs (stmt
) != NULL_TREE
)
1612 || gimple_code (stmt
) == GIMPLE_COND
1613 || gimple_code (stmt
) == GIMPLE_SWITCH
));
1617 if (gimple_code (stmt
) == GIMPLE_CALL
)
1619 /* Resolve __builtin_constant_p. If it hasn't been
1620 folded to integer_one_node by now, it's fairly
1621 certain that the value simply isn't constant. */
1622 tree callee
= gimple_call_fndecl (stmt
);
1624 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
1625 && DECL_FUNCTION_CODE (callee
) == BUILT_IN_CONSTANT_P
)
1627 propagate_tree_value_into_stmt (&si
, integer_zero_node
);
1628 stmt
= gsi_stmt (si
);
1632 if (gimple_code (stmt
) == GIMPLE_COND
)
1634 tree lhs
= gimple_cond_lhs (stmt
);
1635 tree rhs
= gimple_cond_rhs (stmt
);
1637 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
1638 then this conditional is computable at compile time. We can just
1639 shove either 0 or 1 into the LHS, mark the statement as modified
1640 and all the right things will just happen below.
1642 Note this would apply to any case where LHS has a range
1643 narrower than its type implies and RHS is outside that
1644 narrower range. Future work. */
1645 if (TREE_CODE (lhs
) == SSA_NAME
1646 && ssa_name_has_boolean_range (lhs
)
1647 && TREE_CODE (rhs
) == INTEGER_CST
1648 && ! (integer_zerop (rhs
) || integer_onep (rhs
)))
1650 gimple_cond_set_lhs (as_a
<gcond
*> (stmt
),
1651 fold_convert (TREE_TYPE (lhs
),
1652 integer_zero_node
));
1653 gimple_set_modified (stmt
, true);
1657 update_stmt_if_modified (stmt
);
1658 eliminate_redundant_computations (&si
, const_and_copies
,
1660 stmt
= gsi_stmt (si
);
1662 /* Perform simple redundant store elimination. */
1663 if (gimple_assign_single_p (stmt
)
1664 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
1666 tree lhs
= gimple_assign_lhs (stmt
);
1667 tree rhs
= gimple_assign_rhs1 (stmt
);
1670 rhs
= dom_valueize (rhs
);
1671 /* Build a new statement with the RHS and LHS exchanged. */
1672 if (TREE_CODE (rhs
) == SSA_NAME
)
1674 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1675 new_stmt
= gimple_build_assign (rhs
, lhs
);
1676 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1679 new_stmt
= gimple_build_assign (rhs
, lhs
);
1680 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
1681 cached_lhs
= avail_exprs_stack
->lookup_avail_expr (new_stmt
, false,
1684 && rhs
== cached_lhs
)
1686 basic_block bb
= gimple_bb (stmt
);
1687 unlink_stmt_vdef (stmt
);
1688 if (gsi_remove (&si
, true))
1690 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1691 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1692 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1694 release_defs (stmt
);
1700 /* Record any additional equivalences created by this statement. */
1701 if (is_gimple_assign (stmt
))
1702 record_equivalences_from_stmt (stmt
, may_optimize_p
, avail_exprs_stack
);
1704 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
1705 know where it goes. */
1706 if (gimple_modified_p (stmt
) || modified_p
)
1710 if (gimple_code (stmt
) == GIMPLE_COND
)
1711 val
= fold_binary_loc (gimple_location (stmt
),
1712 gimple_cond_code (stmt
), boolean_type_node
,
1713 gimple_cond_lhs (stmt
),
1714 gimple_cond_rhs (stmt
));
1715 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1716 val
= gimple_switch_index (swtch_stmt
);
1718 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1720 retval
= find_taken_edge (bb
, val
);
1723 /* Fix the condition to be either true or false. */
1724 if (gimple_code (stmt
) == GIMPLE_COND
)
1726 if (integer_zerop (val
))
1727 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
1728 else if (integer_onep (val
))
1729 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
1733 gimple_set_modified (stmt
, true);
1736 /* Further simplifications may be possible. */
1741 update_stmt_if_modified (stmt
);
1743 /* If we simplified a statement in such a way as to be shown that it
1744 cannot trap, update the eh information and the cfg to match. */
1745 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1747 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1749 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1753 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
1754 need_noreturn_fixup
.safe_push (stmt
);