1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2015 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"
28 #include "fold-const.h"
31 #include "gimple-pretty-print.h"
32 #include "gimple-fold.h"
34 #include "gimple-iterator.h"
36 #include "tree-into-ssa.h"
38 #include "tree-pass.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"
48 /* This file implements optimizations on the dominator tree. */
50 /* Structure for recording known values of a conditional expression
51 at the exits from its block. */
53 struct cond_equivalence
55 struct hashable_expr cond
;
59 /* Structure for recording edge equivalences.
61 Computing and storing the edge equivalences instead of creating
62 them on-demand can save significant amounts of time, particularly
63 for pathological cases involving switch statements.
65 These structures live for a single iteration of the dominator
66 optimizer in the edge's AUX field. At the end of an iteration we
67 free each of these structures. */
71 /* If this edge creates a simple equivalence, the LHS and RHS of
72 the equivalence will be stored here. */
76 /* Traversing an edge may also indicate one or more particular conditions
78 vec
<cond_equivalence
> cond_equivalences
;
81 /* Hash table with expressions made available during the renaming process.
82 When an assignment of the form X_i = EXPR is found, the statement is
83 stored in this table. If the same expression EXPR is later found on the
84 RHS of another statement, it is replaced with X_i (thus performing
85 global redundancy elimination). Similarly as we pass through conditionals
86 we record the conditional itself as having either a true or false value
88 static hash_table
<expr_elt_hasher
> *avail_exprs
;
90 /* Unwindable equivalences, both const/copy and expression varieties. */
91 static const_and_copies
*const_and_copies
;
92 static avail_exprs_stack
*avail_exprs_stack
;
94 /* Track whether or not we have changed the control flow graph. */
95 static bool cfg_altered
;
97 /* Bitmap of blocks that have had EH statements cleaned. We should
98 remove their dead edges eventually. */
99 static bitmap need_eh_cleanup
;
100 static vec
<gimple
> need_noreturn_fixup
;
102 /* Statistics for dominator optimizations. */
106 long num_exprs_considered
;
112 static struct opt_stats_d opt_stats
;
114 /* Local functions. */
115 static void optimize_stmt (basic_block
, gimple_stmt_iterator
);
116 static tree
lookup_avail_expr (gimple
, bool);
117 static void htab_statistics (FILE *,
118 const hash_table
<expr_elt_hasher
> &);
119 static void record_cond (cond_equivalence
*);
120 static void record_equality (tree
, tree
);
121 static void record_equivalences_from_phis (basic_block
);
122 static void record_equivalences_from_incoming_edge (basic_block
);
123 static void eliminate_redundant_computations (gimple_stmt_iterator
*);
124 static void record_equivalences_from_stmt (gimple
, int);
125 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
127 /* Free the edge_info data attached to E, if it exists. */
130 free_edge_info (edge e
)
132 struct edge_info
*edge_info
= (struct edge_info
*)e
->aux
;
136 edge_info
->cond_equivalences
.release ();
141 /* Allocate an EDGE_INFO for edge E and attach it to E.
142 Return the new EDGE_INFO structure. */
144 static struct edge_info
*
145 allocate_edge_info (edge e
)
147 struct edge_info
*edge_info
;
149 /* Free the old one, if it exists. */
152 edge_info
= XCNEW (struct edge_info
);
158 /* Free all EDGE_INFO structures associated with edges in the CFG.
159 If a particular edge can be threaded, copy the redirection
160 target from the EDGE_INFO structure into the edge's AUX field
161 as required by code to update the CFG and SSA graph for
165 free_all_edge_infos (void)
171 FOR_EACH_BB_FN (bb
, cfun
)
173 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
181 /* Build a cond_equivalence record indicating that the comparison
182 CODE holds between operands OP0 and OP1 and push it to **P. */
185 build_and_record_new_cond (enum tree_code code
,
187 vec
<cond_equivalence
> *p
,
191 struct hashable_expr
*cond
= &c
.cond
;
193 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
195 cond
->type
= boolean_type_node
;
196 cond
->kind
= EXPR_BINARY
;
197 cond
->ops
.binary
.op
= code
;
198 cond
->ops
.binary
.opnd0
= op0
;
199 cond
->ops
.binary
.opnd1
= op1
;
201 c
.value
= val
? boolean_true_node
: boolean_false_node
;
205 /* Record that COND is true and INVERTED is false into the edge information
206 structure. Also record that any conditions dominated by COND are true
209 For example, if a < b is true, then a <= b must also be true. */
212 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
217 if (!COMPARISON_CLASS_P (cond
))
220 op0
= TREE_OPERAND (cond
, 0);
221 op1
= TREE_OPERAND (cond
, 1);
223 switch (TREE_CODE (cond
))
227 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
229 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
230 &edge_info
->cond_equivalences
);
231 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
232 &edge_info
->cond_equivalences
);
235 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
236 ? LE_EXPR
: GE_EXPR
),
237 op0
, op1
, &edge_info
->cond_equivalences
);
238 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
239 &edge_info
->cond_equivalences
);
240 build_and_record_new_cond (EQ_EXPR
, op0
, op1
,
241 &edge_info
->cond_equivalences
, false);
246 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
248 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
249 &edge_info
->cond_equivalences
);
254 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
256 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
257 &edge_info
->cond_equivalences
);
259 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
260 &edge_info
->cond_equivalences
);
261 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
262 &edge_info
->cond_equivalences
);
266 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
267 &edge_info
->cond_equivalences
);
268 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
269 &edge_info
->cond_equivalences
);
270 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
271 &edge_info
->cond_equivalences
);
272 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
273 &edge_info
->cond_equivalences
);
274 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
275 &edge_info
->cond_equivalences
);
276 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
277 &edge_info
->cond_equivalences
);
282 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
283 ? UNLE_EXPR
: UNGE_EXPR
),
284 op0
, op1
, &edge_info
->cond_equivalences
);
285 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
286 &edge_info
->cond_equivalences
);
290 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
291 &edge_info
->cond_equivalences
);
292 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
293 &edge_info
->cond_equivalences
);
297 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
298 &edge_info
->cond_equivalences
);
299 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
300 &edge_info
->cond_equivalences
);
307 /* Now store the original true and false conditions into the first
309 initialize_expr_from_cond (cond
, &c
.cond
);
310 c
.value
= boolean_true_node
;
311 edge_info
->cond_equivalences
.safe_push (c
);
313 /* It is possible for INVERTED to be the negation of a comparison,
314 and not a valid RHS or GIMPLE_COND condition. This happens because
315 invert_truthvalue may return such an expression when asked to invert
316 a floating-point comparison. These comparisons are not assumed to
317 obey the trichotomy law. */
318 initialize_expr_from_cond (inverted
, &c
.cond
);
319 c
.value
= boolean_false_node
;
320 edge_info
->cond_equivalences
.safe_push (c
);
323 /* We have finished optimizing BB, record any information implied by
324 taking a specific outgoing edge from BB. */
327 record_edge_info (basic_block bb
)
329 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
330 struct edge_info
*edge_info
;
332 if (! gsi_end_p (gsi
))
334 gimple stmt
= gsi_stmt (gsi
);
335 location_t loc
= gimple_location (stmt
);
337 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
339 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
340 tree index
= gimple_switch_index (switch_stmt
);
342 if (TREE_CODE (index
) == SSA_NAME
)
345 int n_labels
= gimple_switch_num_labels (switch_stmt
);
346 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
350 for (i
= 0; i
< n_labels
; i
++)
352 tree label
= gimple_switch_label (switch_stmt
, i
);
353 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
354 if (CASE_HIGH (label
)
356 || info
[target_bb
->index
])
357 info
[target_bb
->index
] = error_mark_node
;
359 info
[target_bb
->index
] = label
;
362 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
364 basic_block target_bb
= e
->dest
;
365 tree label
= info
[target_bb
->index
];
367 if (label
!= NULL
&& label
!= error_mark_node
)
369 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
371 edge_info
= allocate_edge_info (e
);
372 edge_info
->lhs
= index
;
380 /* A COND_EXPR may create equivalences too. */
381 if (gimple_code (stmt
) == GIMPLE_COND
)
386 tree op0
= gimple_cond_lhs (stmt
);
387 tree op1
= gimple_cond_rhs (stmt
);
388 enum tree_code code
= gimple_cond_code (stmt
);
390 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
392 /* Special case comparing booleans against a constant as we
393 know the value of OP0 on both arms of the branch. i.e., we
394 can record an equivalence for OP0 rather than COND. */
395 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
396 && TREE_CODE (op0
) == SSA_NAME
397 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
398 && is_gimple_min_invariant (op1
))
402 edge_info
= allocate_edge_info (true_edge
);
403 edge_info
->lhs
= op0
;
404 edge_info
->rhs
= (integer_zerop (op1
)
406 : boolean_true_node
);
408 edge_info
= allocate_edge_info (false_edge
);
409 edge_info
->lhs
= op0
;
410 edge_info
->rhs
= (integer_zerop (op1
)
412 : boolean_false_node
);
416 edge_info
= allocate_edge_info (true_edge
);
417 edge_info
->lhs
= op0
;
418 edge_info
->rhs
= (integer_zerop (op1
)
420 : boolean_false_node
);
422 edge_info
= allocate_edge_info (false_edge
);
423 edge_info
->lhs
= op0
;
424 edge_info
->rhs
= (integer_zerop (op1
)
426 : boolean_true_node
);
429 else if (is_gimple_min_invariant (op0
)
430 && (TREE_CODE (op1
) == SSA_NAME
431 || is_gimple_min_invariant (op1
)))
433 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
434 tree inverted
= invert_truthvalue_loc (loc
, cond
);
435 bool can_infer_simple_equiv
436 = !(HONOR_SIGNED_ZEROS (op0
)
437 && real_zerop (op0
));
438 struct edge_info
*edge_info
;
440 edge_info
= allocate_edge_info (true_edge
);
441 record_conditions (edge_info
, cond
, inverted
);
443 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
445 edge_info
->lhs
= op1
;
446 edge_info
->rhs
= op0
;
449 edge_info
= allocate_edge_info (false_edge
);
450 record_conditions (edge_info
, inverted
, cond
);
452 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
454 edge_info
->lhs
= op1
;
455 edge_info
->rhs
= op0
;
459 else if (TREE_CODE (op0
) == SSA_NAME
460 && (TREE_CODE (op1
) == SSA_NAME
461 || is_gimple_min_invariant (op1
)))
463 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
464 tree inverted
= invert_truthvalue_loc (loc
, cond
);
465 bool can_infer_simple_equiv
466 = !(HONOR_SIGNED_ZEROS (op1
)
467 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
468 struct edge_info
*edge_info
;
470 edge_info
= allocate_edge_info (true_edge
);
471 record_conditions (edge_info
, cond
, inverted
);
473 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
475 edge_info
->lhs
= op0
;
476 edge_info
->rhs
= op1
;
479 edge_info
= allocate_edge_info (false_edge
);
480 record_conditions (edge_info
, inverted
, cond
);
482 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
484 edge_info
->lhs
= op0
;
485 edge_info
->rhs
= op1
;
490 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
495 class dom_opt_dom_walker
: public dom_walker
498 dom_opt_dom_walker (cdi_direction direction
)
499 : dom_walker (direction
), m_dummy_cond (NULL
) {}
501 virtual void before_dom_children (basic_block
);
502 virtual void after_dom_children (basic_block
);
505 void thread_across_edge (edge
);
510 /* Jump threading, redundancy elimination and const/copy propagation.
512 This pass may expose new symbols that need to be renamed into SSA. For
513 every new symbol exposed, its corresponding bit will be set in
518 const pass_data pass_data_dominator
=
520 GIMPLE_PASS
, /* type */
522 OPTGROUP_NONE
, /* optinfo_flags */
523 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
524 ( PROP_cfg
| PROP_ssa
), /* properties_required */
525 0, /* properties_provided */
526 0, /* properties_destroyed */
527 0, /* todo_flags_start */
528 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
531 class pass_dominator
: public gimple_opt_pass
534 pass_dominator (gcc::context
*ctxt
)
535 : gimple_opt_pass (pass_data_dominator
, ctxt
)
538 /* opt_pass methods: */
539 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
540 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
541 virtual unsigned int execute (function
*);
543 }; // class pass_dominator
546 pass_dominator::execute (function
*fun
)
548 memset (&opt_stats
, 0, sizeof (opt_stats
));
550 /* Create our hash tables. */
551 avail_exprs
= new hash_table
<expr_elt_hasher
> (1024);
552 avail_exprs_stack
= new class avail_exprs_stack (avail_exprs
);
553 const_and_copies
= new class const_and_copies ();
554 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
555 need_noreturn_fixup
.create (0);
557 calculate_dominance_info (CDI_DOMINATORS
);
560 /* We need to know loop structures in order to avoid destroying them
561 in jump threading. Note that we still can e.g. thread through loop
562 headers to an exit edge, or through loop header to the loop body, assuming
563 that we update the loop info.
565 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
566 to several overly conservative bail-outs in jump threading, case
567 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
568 missing. We should improve jump threading in future then
569 LOOPS_HAVE_PREHEADERS won't be needed here. */
570 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
572 /* Initialize the value-handle array. */
573 threadedge_initialize_values ();
575 /* We need accurate information regarding back edges in the CFG
576 for jump threading; this may include back edges that are not part of
578 mark_dfs_back_edges ();
580 /* We want to create the edge info structures before the dominator walk
581 so that they'll be in place for the jump threader, particularly when
582 threading through a join block.
584 The conditions will be lazily updated with global equivalences as
585 we reach them during the dominator walk. */
587 FOR_EACH_BB_FN (bb
, fun
)
588 record_edge_info (bb
);
590 /* Recursively walk the dominator tree optimizing statements. */
591 dom_opt_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
594 gimple_stmt_iterator gsi
;
596 FOR_EACH_BB_FN (bb
, fun
)
598 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
599 update_stmt_if_modified (gsi_stmt (gsi
));
603 /* If we exposed any new variables, go ahead and put them into
604 SSA form now, before we handle jump threading. This simplifies
605 interactions between rewriting of _DECL nodes into SSA form
606 and rewriting SSA_NAME nodes into SSA form after block
607 duplication and CFG manipulation. */
608 update_ssa (TODO_update_ssa
);
610 free_all_edge_infos ();
612 /* Thread jumps, creating duplicate blocks as needed. */
613 cfg_altered
|= thread_through_all_blocks (first_pass_instance
);
616 free_dominance_info (CDI_DOMINATORS
);
618 /* Removal of statements may make some EH edges dead. Purge
619 such edges from the CFG as needed. */
620 if (!bitmap_empty_p (need_eh_cleanup
))
625 /* Jump threading may have created forwarder blocks from blocks
626 needing EH cleanup; the new successor of these blocks, which
627 has inherited from the original block, needs the cleanup.
628 Don't clear bits in the bitmap, as that can break the bitmap
630 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
632 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
635 while (single_succ_p (bb
)
636 && (single_succ_edge (bb
)->flags
& EDGE_EH
) == 0)
637 bb
= single_succ (bb
);
638 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
640 if ((unsigned) bb
->index
!= i
)
641 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
644 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
645 bitmap_clear (need_eh_cleanup
);
648 /* Fixup stmts that became noreturn calls. This may require splitting
649 blocks and thus isn't possible during the dominator walk or before
650 jump threading finished. Do this in reverse order so we don't
651 inadvertedly remove a stmt we want to fixup by visiting a dominating
652 now noreturn call first. */
653 while (!need_noreturn_fixup
.is_empty ())
655 gimple stmt
= need_noreturn_fixup
.pop ();
656 if (dump_file
&& dump_flags
& TDF_DETAILS
)
658 fprintf (dump_file
, "Fixing up noreturn call ");
659 print_gimple_stmt (dump_file
, stmt
, 0, 0);
660 fprintf (dump_file
, "\n");
662 fixup_noreturn_call (stmt
);
665 statistics_counter_event (fun
, "Redundant expressions eliminated",
667 statistics_counter_event (fun
, "Constants propagated",
668 opt_stats
.num_const_prop
);
669 statistics_counter_event (fun
, "Copies propagated",
670 opt_stats
.num_copy_prop
);
672 /* Debugging dumps. */
673 if (dump_file
&& (dump_flags
& TDF_STATS
))
674 dump_dominator_optimization_stats (dump_file
);
676 loop_optimizer_finalize ();
678 /* Delete our main hashtable. */
682 /* Free asserted bitmaps and stacks. */
683 BITMAP_FREE (need_eh_cleanup
);
684 need_noreturn_fixup
.release ();
685 delete avail_exprs_stack
;
686 delete const_and_copies
;
688 /* Free the value-handle array. */
689 threadedge_finalize_values ();
697 make_pass_dominator (gcc::context
*ctxt
)
699 return new pass_dominator (ctxt
);
703 /* Given a conditional statement CONDSTMT, convert the
704 condition to a canonical form. */
707 canonicalize_comparison (gcond
*condstmt
)
713 gcc_assert (gimple_code (condstmt
) == GIMPLE_COND
);
715 op0
= gimple_cond_lhs (condstmt
);
716 op1
= gimple_cond_rhs (condstmt
);
718 code
= gimple_cond_code (condstmt
);
720 /* If it would be profitable to swap the operands, then do so to
721 canonicalize the statement, enabling better optimization.
723 By placing canonicalization of such expressions here we
724 transparently keep statements in canonical form, even
725 when the statement is modified. */
726 if (tree_swap_operands_p (op0
, op1
, false))
728 /* For relationals we need to swap the operands
729 and change the code. */
735 code
= swap_tree_comparison (code
);
737 gimple_cond_set_code (condstmt
, code
);
738 gimple_cond_set_lhs (condstmt
, op1
);
739 gimple_cond_set_rhs (condstmt
, op0
);
741 update_stmt (condstmt
);
746 /* A trivial wrapper so that we can present the generic jump
747 threading code with a simple API for simplifying statements. */
749 simplify_stmt_for_jump_threading (gimple stmt
,
750 gimple within_stmt ATTRIBUTE_UNUSED
)
752 return lookup_avail_expr (stmt
, false);
755 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
758 dom_valueize (tree t
)
760 if (TREE_CODE (t
) == SSA_NAME
)
762 tree tem
= SSA_NAME_VALUE (t
);
769 /* Record into the equivalence tables any equivalences implied by
770 traversing edge E (which are cached in E->aux).
772 Callers are responsible for managing the unwinding markers. */
774 record_temporary_equivalences (edge e
)
777 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
779 /* If we have info associated with this edge, record it into
780 our equivalence tables. */
783 cond_equivalence
*eq
;
784 tree lhs
= edge_info
->lhs
;
785 tree rhs
= edge_info
->rhs
;
787 /* If we have a simple NAME = VALUE equivalence, record it. */
789 record_equality (lhs
, rhs
);
791 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
792 set via a widening type conversion, then we may be able to record
793 additional equivalences. */
795 && TREE_CODE (lhs
) == SSA_NAME
796 && TREE_CODE (rhs
) == INTEGER_CST
)
798 gimple defstmt
= SSA_NAME_DEF_STMT (lhs
);
801 && is_gimple_assign (defstmt
)
802 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt
)))
804 tree old_rhs
= gimple_assign_rhs1 (defstmt
);
806 /* If the conversion widens the original value and
807 the constant is in the range of the type of OLD_RHS,
808 then convert the constant and record the equivalence.
810 Note that int_fits_type_p does not check the precision
811 if the upper and lower bounds are OK. */
812 if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs
))
813 && (TYPE_PRECISION (TREE_TYPE (lhs
))
814 > TYPE_PRECISION (TREE_TYPE (old_rhs
)))
815 && int_fits_type_p (rhs
, TREE_TYPE (old_rhs
)))
817 tree newval
= fold_convert (TREE_TYPE (old_rhs
), rhs
);
818 record_equality (old_rhs
, newval
);
823 /* If LHS is an SSA_NAME with a new equivalency then try if
824 stmts with uses of that LHS that dominate the edge destination
825 simplify and allow further equivalences to be recorded. */
826 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
829 imm_use_iterator iter
;
830 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
832 gimple use_stmt
= USE_STMT (use_p
);
834 /* Only bother to record more equivalences for lhs that
835 can be directly used by e->dest.
836 ??? If the code gets re-organized to a worklist to
837 catch more indirect opportunities and it is made to
838 handle PHIs then this should only consider use_stmts
839 in basic-blocks we have already visited. */
840 if (e
->dest
== gimple_bb (use_stmt
)
841 || !dominated_by_p (CDI_DOMINATORS
,
842 e
->dest
, gimple_bb (use_stmt
)))
844 tree lhs2
= gimple_get_lhs (use_stmt
);
845 if (lhs2
&& TREE_CODE (lhs2
) == SSA_NAME
)
848 = gimple_fold_stmt_to_constant_1 (use_stmt
, dom_valueize
,
849 no_follow_ssa_edges
);
851 && (TREE_CODE (res
) == SSA_NAME
852 || is_gimple_min_invariant (res
)))
853 record_equality (lhs2
, res
);
858 /* If we have 0 = COND or 1 = COND equivalences, record them
859 into our expression hash tables. */
860 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
865 /* Wrapper for common code to attempt to thread an edge. For example,
866 it handles lazily building the dummy condition and the bookkeeping
867 when jump threading is successful. */
870 dom_opt_dom_walker::thread_across_edge (edge e
)
874 gimple_build_cond (NE_EXPR
,
875 integer_zero_node
, integer_zero_node
,
878 /* Push a marker on both stacks so we can unwind the tables back to their
880 avail_exprs_stack
->push_marker ();
881 const_and_copies
->push_marker ();
883 /* Traversing E may result in equivalences we can utilize. */
884 record_temporary_equivalences (e
);
886 /* With all the edge equivalences in the tables, go ahead and attempt
887 to thread through E->dest. */
888 ::thread_across_edge (m_dummy_cond
, e
, false,
889 const_and_copies
, avail_exprs_stack
,
890 simplify_stmt_for_jump_threading
);
892 /* And restore the various tables to their state before
893 we threaded this edge.
895 XXX The code in tree-ssa-threadedge.c will restore the state of
896 the const_and_copies table. We we just have to restore the expression
898 avail_exprs_stack
->pop_to_marker ();
901 /* PHI nodes can create equivalences too.
903 Ignoring any alternatives which are the same as the result, if
904 all the alternatives are equal, then the PHI node creates an
908 record_equivalences_from_phis (basic_block bb
)
912 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
914 gphi
*phi
= gsi
.phi ();
916 tree lhs
= gimple_phi_result (phi
);
920 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
922 tree t
= gimple_phi_arg_def (phi
, i
);
924 /* Ignore alternatives which are the same as our LHS. Since
925 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
926 can simply compare pointers. */
930 t
= dom_valueize (t
);
932 /* If we have not processed an alternative yet, then set
933 RHS to this alternative. */
936 /* If we have processed an alternative (stored in RHS), then
937 see if it is equal to this one. If it isn't, then stop
939 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
943 /* If we had no interesting alternatives, then all the RHS alternatives
944 must have been the same as LHS. */
948 /* If we managed to iterate through each PHI alternative without
949 breaking out of the loop, then we have a PHI which may create
950 a useful equivalence. We do not need to record unwind data for
951 this, since this is a true assignment and not an equivalence
952 inferred from a comparison. All uses of this ssa name are dominated
953 by this assignment, so unwinding just costs time and space. */
954 if (i
== gimple_phi_num_args (phi
)
955 && may_propagate_copy (lhs
, rhs
))
956 set_ssa_name_value (lhs
, rhs
);
960 /* Ignoring loop backedges, if BB has precisely one incoming edge then
961 return that edge. Otherwise return NULL. */
963 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
969 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
971 /* A loop back edge can be identified by the destination of
972 the edge dominating the source of the edge. */
973 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
976 /* If we have already seen a non-loop edge, then we must have
977 multiple incoming non-loop edges and thus we return NULL. */
981 /* This is the first non-loop incoming edge we have found. Record
989 /* Record any equivalences created by the incoming edge to BB. If BB
990 has more than one incoming edge, then no equivalence is created. */
993 record_equivalences_from_incoming_edge (basic_block bb
)
998 /* If our parent block ended with a control statement, then we may be
999 able to record some equivalences based on which outgoing edge from
1000 the parent was followed. */
1001 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1003 e
= single_incoming_edge_ignoring_loop_edges (bb
);
1005 /* If we had a single incoming edge from our parent block, then enter
1006 any data associated with the edge into our tables. */
1007 if (e
&& e
->src
== parent
)
1008 record_temporary_equivalences (e
);
1011 /* Dump SSA statistics on FILE. */
1014 dump_dominator_optimization_stats (FILE *file
)
1016 fprintf (file
, "Total number of statements: %6ld\n\n",
1017 opt_stats
.num_stmts
);
1018 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1019 opt_stats
.num_exprs_considered
);
1021 fprintf (file
, "\nHash table statistics:\n");
1023 fprintf (file
, " avail_exprs: ");
1024 htab_statistics (file
, *avail_exprs
);
1028 /* Dump SSA statistics on stderr. */
1031 debug_dominator_optimization_stats (void)
1033 dump_dominator_optimization_stats (stderr
);
1037 /* Dump statistics for the hash table HTAB. */
1040 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
1042 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1043 (long) htab
.size (),
1044 (long) htab
.elements (),
1045 htab
.collisions ());
1049 /* Enter condition equivalence into the expression hash table.
1050 This indicates that a conditional expression has a known
1054 record_cond (cond_equivalence
*p
)
1056 class expr_hash_elt
*element
= new expr_hash_elt (&p
->cond
, p
->value
);
1057 expr_hash_elt
**slot
;
1059 slot
= avail_exprs
->find_slot_with_hash (element
, element
->hash (), INSERT
);
1064 avail_exprs_stack
->record_expr (element
, NULL
, '1');
1070 /* Return the loop depth of the basic block of the defining statement of X.
1071 This number should not be treated as absolutely correct because the loop
1072 information may not be completely up-to-date when dom runs. However, it
1073 will be relatively correct, and as more passes are taught to keep loop info
1074 up to date, the result will become more and more accurate. */
1077 loop_depth_of_name (tree x
)
1082 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1083 if (TREE_CODE (x
) != SSA_NAME
)
1086 /* Otherwise return the loop depth of the defining statement's bb.
1087 Note that there may not actually be a bb for this statement, if the
1088 ssa_name is live on entry. */
1089 defstmt
= SSA_NAME_DEF_STMT (x
);
1090 defbb
= gimple_bb (defstmt
);
1094 return bb_loop_depth (defbb
);
1097 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1098 This constrains the cases in which we may treat this as assignment. */
1101 record_equality (tree x
, tree y
)
1103 tree prev_x
= NULL
, prev_y
= NULL
;
1105 if (tree_swap_operands_p (x
, y
, false))
1108 /* Most of the time tree_swap_operands_p does what we want. But there
1109 are cases where we know one operand is better for copy propagation than
1110 the other. Given no other code cares about ordering of equality
1111 comparison operators for that purpose, we just handle the special cases
1113 if (TREE_CODE (x
) == SSA_NAME
&& TREE_CODE (y
) == SSA_NAME
)
1115 /* If one operand is a single use operand, then make it
1116 X. This will preserve its single use properly and if this
1117 conditional is eliminated, the computation of X can be
1118 eliminated as well. */
1119 if (has_single_use (y
) && ! has_single_use (x
))
1122 if (TREE_CODE (x
) == SSA_NAME
)
1123 prev_x
= SSA_NAME_VALUE (x
);
1124 if (TREE_CODE (y
) == SSA_NAME
)
1125 prev_y
= SSA_NAME_VALUE (y
);
1127 /* If one of the previous values is invariant, or invariant in more loops
1128 (by depth), then use that.
1129 Otherwise it doesn't matter which value we choose, just so
1130 long as we canonicalize on one value. */
1131 if (is_gimple_min_invariant (y
))
1133 else if (is_gimple_min_invariant (x
)
1134 /* ??? When threading over backedges the following is important
1135 for correctness. See PR61757. */
1136 || (loop_depth_of_name (x
) < loop_depth_of_name (y
)))
1137 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1138 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1139 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1143 /* After the swapping, we must have one SSA_NAME. */
1144 if (TREE_CODE (x
) != SSA_NAME
)
1147 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1148 variable compared against zero. If we're honoring signed zeros,
1149 then we cannot record this value unless we know that the value is
1151 if (HONOR_SIGNED_ZEROS (x
)
1152 && (TREE_CODE (y
) != REAL_CST
1153 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1156 const_and_copies
->record_const_or_copy (x
, y
, prev_x
);
1159 /* Returns true when STMT is a simple iv increment. It detects the
1160 following situation:
1162 i_1 = phi (..., i_2)
1163 i_2 = i_1 +/- ... */
1166 simple_iv_increment_p (gimple stmt
)
1168 enum tree_code code
;
1173 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1176 lhs
= gimple_assign_lhs (stmt
);
1177 if (TREE_CODE (lhs
) != SSA_NAME
)
1180 code
= gimple_assign_rhs_code (stmt
);
1181 if (code
!= PLUS_EXPR
1182 && code
!= MINUS_EXPR
1183 && code
!= POINTER_PLUS_EXPR
)
1186 preinc
= gimple_assign_rhs1 (stmt
);
1187 if (TREE_CODE (preinc
) != SSA_NAME
)
1190 phi
= SSA_NAME_DEF_STMT (preinc
);
1191 if (gimple_code (phi
) != GIMPLE_PHI
)
1194 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1195 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1201 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1202 known value for that SSA_NAME (or NULL if no value is known).
1204 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1205 successors of BB. */
1208 cprop_into_successor_phis (basic_block bb
)
1213 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1218 /* If this is an abnormal edge, then we do not want to copy propagate
1219 into the PHI alternative associated with this edge. */
1220 if (e
->flags
& EDGE_ABNORMAL
)
1223 gsi
= gsi_start_phis (e
->dest
);
1224 if (gsi_end_p (gsi
))
1227 /* We may have an equivalence associated with this edge. While
1228 we can not propagate it into non-dominated blocks, we can
1229 propagate them into PHIs in non-dominated blocks. */
1231 /* Push the unwind marker so we can reset the const and copies
1232 table back to its original state after processing this edge. */
1233 const_and_copies
->push_marker ();
1235 /* Extract and record any simple NAME = VALUE equivalences.
1237 Don't bother with [01] = COND equivalences, they're not useful
1239 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
1242 tree lhs
= edge_info
->lhs
;
1243 tree rhs
= edge_info
->rhs
;
1245 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1246 const_and_copies
->record_const_or_copy (lhs
, rhs
);
1250 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1253 use_operand_p orig_p
;
1255 gphi
*phi
= gsi
.phi ();
1257 /* The alternative may be associated with a constant, so verify
1258 it is an SSA_NAME before doing anything with it. */
1259 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1260 orig_val
= get_use_from_ptr (orig_p
);
1261 if (TREE_CODE (orig_val
) != SSA_NAME
)
1264 /* If we have *ORIG_P in our constant/copy table, then replace
1265 ORIG_P with its value in our constant/copy table. */
1266 new_val
= SSA_NAME_VALUE (orig_val
);
1268 && new_val
!= orig_val
1269 && (TREE_CODE (new_val
) == SSA_NAME
1270 || is_gimple_min_invariant (new_val
))
1271 && may_propagate_copy (orig_val
, new_val
))
1272 propagate_value (orig_p
, new_val
);
1275 const_and_copies
->pop_to_marker ();
1280 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1282 gimple_stmt_iterator gsi
;
1284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1285 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1287 /* Push a marker on the stacks of local information so that we know how
1288 far to unwind when we finalize this block. */
1289 avail_exprs_stack
->push_marker ();
1290 const_and_copies
->push_marker ();
1292 record_equivalences_from_incoming_edge (bb
);
1294 /* PHI nodes can create equivalences too. */
1295 record_equivalences_from_phis (bb
);
1297 /* Create equivalences from redundant PHIs. PHIs are only truly
1298 redundant when they exist in the same block, so push another
1299 marker and unwind right afterwards. */
1300 avail_exprs_stack
->push_marker ();
1301 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1302 eliminate_redundant_computations (&gsi
);
1303 avail_exprs_stack
->pop_to_marker ();
1305 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1306 optimize_stmt (bb
, gsi
);
1308 /* Now prepare to process dominated blocks. */
1309 record_edge_info (bb
);
1310 cprop_into_successor_phis (bb
);
1313 /* We have finished processing the dominator children of BB, perform
1314 any finalization actions in preparation for leaving this node in
1315 the dominator tree. */
1318 dom_opt_dom_walker::after_dom_children (basic_block bb
)
1322 /* If we have an outgoing edge to a block with multiple incoming and
1323 outgoing edges, then we may be able to thread the edge, i.e., we
1324 may be able to statically determine which of the outgoing edges
1325 will be traversed when the incoming edge from BB is traversed. */
1326 if (single_succ_p (bb
)
1327 && (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
) == 0
1328 && potentially_threadable_block (single_succ (bb
)))
1330 thread_across_edge (single_succ_edge (bb
));
1332 else if ((last
= last_stmt (bb
))
1333 && gimple_code (last
) == GIMPLE_COND
1334 && EDGE_COUNT (bb
->succs
) == 2
1335 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
1336 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
1338 edge true_edge
, false_edge
;
1340 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1342 /* Only try to thread the edge if it reaches a target block with
1343 more than one predecessor and more than one successor. */
1344 if (potentially_threadable_block (true_edge
->dest
))
1345 thread_across_edge (true_edge
);
1347 /* Similarly for the ELSE arm. */
1348 if (potentially_threadable_block (false_edge
->dest
))
1349 thread_across_edge (false_edge
);
1353 /* These remove expressions local to BB from the tables. */
1354 avail_exprs_stack
->pop_to_marker ();
1355 const_and_copies
->pop_to_marker ();
1358 /* Search for redundant computations in STMT. If any are found, then
1359 replace them with the variable holding the result of the computation.
1361 If safe, record this expression into the available expression hash
1365 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
)
1371 bool assigns_var_p
= false;
1373 gimple stmt
= gsi_stmt (*gsi
);
1375 if (gimple_code (stmt
) == GIMPLE_PHI
)
1376 def
= gimple_phi_result (stmt
);
1378 def
= gimple_get_lhs (stmt
);
1380 /* Certain expressions on the RHS can be optimized away, but can not
1381 themselves be entered into the hash tables. */
1383 || TREE_CODE (def
) != SSA_NAME
1384 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1385 || gimple_vdef (stmt
)
1386 /* Do not record equivalences for increments of ivs. This would create
1387 overlapping live ranges for a very questionable gain. */
1388 || simple_iv_increment_p (stmt
))
1391 /* Check if the expression has been computed before. */
1392 cached_lhs
= lookup_avail_expr (stmt
, insert
);
1394 opt_stats
.num_exprs_considered
++;
1396 /* Get the type of the expression we are trying to optimize. */
1397 if (is_gimple_assign (stmt
))
1399 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1400 assigns_var_p
= true;
1402 else if (gimple_code (stmt
) == GIMPLE_COND
)
1403 expr_type
= boolean_type_node
;
1404 else if (is_gimple_call (stmt
))
1406 gcc_assert (gimple_call_lhs (stmt
));
1407 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1408 assigns_var_p
= true;
1410 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1411 expr_type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
1412 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1413 /* We can't propagate into a phi, so the logic below doesn't apply.
1414 Instead record an equivalence between the cached LHS and the
1415 PHI result of this statement, provided they are in the same block.
1416 This should be sufficient to kill the redundant phi. */
1418 if (def
&& cached_lhs
)
1419 const_and_copies
->record_const_or_copy (def
, cached_lhs
);
1428 /* It is safe to ignore types here since we have already done
1429 type checking in the hashing and equality routines. In fact
1430 type checking here merely gets in the way of constant
1431 propagation. Also, make sure that it is safe to propagate
1432 CACHED_LHS into the expression in STMT. */
1433 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1435 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1436 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1438 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1439 || is_gimple_min_invariant (cached_lhs
));
1441 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1443 fprintf (dump_file
, " Replaced redundant expr '");
1444 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1445 fprintf (dump_file
, "' with '");
1446 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1447 fprintf (dump_file
, "'\n");
1453 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1454 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1456 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1458 /* Since it is always necessary to mark the result as modified,
1459 perhaps we should move this into propagate_tree_value_into_stmt
1461 gimple_set_modified (gsi_stmt (*gsi
), true);
1465 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1466 the available expressions table or the const_and_copies table.
1467 Detect and record those equivalences. */
1468 /* We handle only very simple copy equivalences here. The heavy
1469 lifing is done by eliminate_redundant_computations. */
1472 record_equivalences_from_stmt (gimple stmt
, int may_optimize_p
)
1475 enum tree_code lhs_code
;
1477 gcc_assert (is_gimple_assign (stmt
));
1479 lhs
= gimple_assign_lhs (stmt
);
1480 lhs_code
= TREE_CODE (lhs
);
1482 if (lhs_code
== SSA_NAME
1483 && gimple_assign_single_p (stmt
))
1485 tree rhs
= gimple_assign_rhs1 (stmt
);
1487 /* If the RHS of the assignment is a constant or another variable that
1488 may be propagated, register it in the CONST_AND_COPIES table. We
1489 do not need to record unwind data for this, since this is a true
1490 assignment and not an equivalence inferred from a comparison. All
1491 uses of this ssa name are dominated by this assignment, so unwinding
1492 just costs time and space. */
1494 && (TREE_CODE (rhs
) == SSA_NAME
1495 || is_gimple_min_invariant (rhs
)))
1497 rhs
= dom_valueize (rhs
);
1499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1501 fprintf (dump_file
, "==== ASGN ");
1502 print_generic_expr (dump_file
, lhs
, 0);
1503 fprintf (dump_file
, " = ");
1504 print_generic_expr (dump_file
, rhs
, 0);
1505 fprintf (dump_file
, "\n");
1508 set_ssa_name_value (lhs
, rhs
);
1512 /* Make sure we can propagate &x + CST. */
1513 if (lhs_code
== SSA_NAME
1514 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1515 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
1516 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
1518 tree op0
= gimple_assign_rhs1 (stmt
);
1519 tree op1
= gimple_assign_rhs2 (stmt
);
1521 = build_fold_addr_expr (fold_build2 (MEM_REF
,
1522 TREE_TYPE (TREE_TYPE (op0
)),
1524 fold_convert (ptr_type_node
,
1526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1528 fprintf (dump_file
, "==== ASGN ");
1529 print_generic_expr (dump_file
, lhs
, 0);
1530 fprintf (dump_file
, " = ");
1531 print_generic_expr (dump_file
, new_rhs
, 0);
1532 fprintf (dump_file
, "\n");
1535 set_ssa_name_value (lhs
, new_rhs
);
1538 /* A memory store, even an aliased store, creates a useful
1539 equivalence. By exchanging the LHS and RHS, creating suitable
1540 vops and recording the result in the available expression table,
1541 we may be able to expose more redundant loads. */
1542 if (!gimple_has_volatile_ops (stmt
)
1543 && gimple_references_memory_p (stmt
)
1544 && gimple_assign_single_p (stmt
)
1545 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1546 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1547 && !is_gimple_reg (lhs
))
1549 tree rhs
= gimple_assign_rhs1 (stmt
);
1552 /* Build a new statement with the RHS and LHS exchanged. */
1553 if (TREE_CODE (rhs
) == SSA_NAME
)
1555 /* NOTE tuples. The call to gimple_build_assign below replaced
1556 a call to build_gimple_modify_stmt, which did not set the
1557 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1558 may cause an SSA validation failure, as the LHS may be a
1559 default-initialized name and should have no definition. I'm
1560 a bit dubious of this, as the artificial statement that we
1561 generate here may in fact be ill-formed, but it is simply
1562 used as an internal device in this pass, and never becomes
1564 gimple defstmt
= SSA_NAME_DEF_STMT (rhs
);
1565 new_stmt
= gimple_build_assign (rhs
, lhs
);
1566 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1569 new_stmt
= gimple_build_assign (rhs
, lhs
);
1571 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
1573 /* Finally enter the statement into the available expression
1575 lookup_avail_expr (new_stmt
, true);
1579 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1580 CONST_AND_COPIES. */
1583 cprop_operand (gimple stmt
, use_operand_p op_p
)
1586 tree op
= USE_FROM_PTR (op_p
);
1588 /* If the operand has a known constant value or it is known to be a
1589 copy of some other variable, use the value or copy stored in
1590 CONST_AND_COPIES. */
1591 val
= SSA_NAME_VALUE (op
);
1592 if (val
&& val
!= op
)
1594 /* Do not replace hard register operands in asm statements. */
1595 if (gimple_code (stmt
) == GIMPLE_ASM
1596 && !may_propagate_copy_into_asm (op
))
1599 /* Certain operands are not allowed to be copy propagated due
1600 to their interaction with exception handling and some GCC
1602 if (!may_propagate_copy (op
, val
))
1605 /* Do not propagate copies into BIVs.
1606 See PR23821 and PR62217 for how this can disturb IV and
1607 number of iteration analysis. */
1608 if (TREE_CODE (val
) != INTEGER_CST
)
1610 gimple def
= SSA_NAME_DEF_STMT (op
);
1611 if (gimple_code (def
) == GIMPLE_PHI
1612 && gimple_bb (def
)->loop_father
->header
== gimple_bb (def
))
1617 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 fprintf (dump_file
, " Replaced '");
1620 print_generic_expr (dump_file
, op
, dump_flags
);
1621 fprintf (dump_file
, "' with %s '",
1622 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1623 print_generic_expr (dump_file
, val
, dump_flags
);
1624 fprintf (dump_file
, "'\n");
1627 if (TREE_CODE (val
) != SSA_NAME
)
1628 opt_stats
.num_const_prop
++;
1630 opt_stats
.num_copy_prop
++;
1632 propagate_value (op_p
, val
);
1634 /* And note that we modified this statement. This is now
1635 safe, even if we changed virtual operands since we will
1636 rescan the statement and rewrite its operands again. */
1637 gimple_set_modified (stmt
, true);
1641 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1642 known value for that SSA_NAME (or NULL if no value is known).
1644 Propagate values from CONST_AND_COPIES into the uses, vuses and
1645 vdef_ops of STMT. */
1648 cprop_into_stmt (gimple stmt
)
1653 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
1654 cprop_operand (stmt
, op_p
);
1657 /* Optimize the statement pointed to by iterator SI.
1659 We try to perform some simplistic global redundancy elimination and
1660 constant propagation:
1662 1- To detect global redundancy, we keep track of expressions that have
1663 been computed in this block and its dominators. If we find that the
1664 same expression is computed more than once, we eliminate repeated
1665 computations by using the target of the first one.
1667 2- Constant values and copy assignments. This is used to do very
1668 simplistic constant and copy propagation. When a constant or copy
1669 assignment is found, we map the value on the RHS of the assignment to
1670 the variable in the LHS in the CONST_AND_COPIES table. */
1673 optimize_stmt (basic_block bb
, gimple_stmt_iterator si
)
1675 gimple stmt
, old_stmt
;
1676 bool may_optimize_p
;
1677 bool modified_p
= false;
1680 old_stmt
= stmt
= gsi_stmt (si
);
1681 was_noreturn
= is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
);
1683 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1685 fprintf (dump_file
, "Optimizing statement ");
1686 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1689 if (gimple_code (stmt
) == GIMPLE_COND
)
1690 canonicalize_comparison (as_a
<gcond
*> (stmt
));
1692 update_stmt_if_modified (stmt
);
1693 opt_stats
.num_stmts
++;
1695 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1696 cprop_into_stmt (stmt
);
1698 /* If the statement has been modified with constant replacements,
1699 fold its RHS before checking for redundant computations. */
1700 if (gimple_modified_p (stmt
))
1704 /* Try to fold the statement making sure that STMT is kept
1706 if (fold_stmt (&si
))
1708 stmt
= gsi_stmt (si
);
1709 gimple_set_modified (stmt
, true);
1711 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1713 fprintf (dump_file
, " Folded to: ");
1714 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1718 /* We only need to consider cases that can yield a gimple operand. */
1719 if (gimple_assign_single_p (stmt
))
1720 rhs
= gimple_assign_rhs1 (stmt
);
1721 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
1722 rhs
= gimple_goto_dest (stmt
);
1723 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1724 /* This should never be an ADDR_EXPR. */
1725 rhs
= gimple_switch_index (swtch_stmt
);
1727 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
1728 recompute_tree_invariant_for_addr_expr (rhs
);
1730 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1731 even if fold_stmt updated the stmt already and thus cleared
1732 gimple_modified_p flag on it. */
1736 /* Check for redundant computations. Do this optimization only
1737 for assignments that have no volatile ops and conditionals. */
1738 may_optimize_p
= (!gimple_has_side_effects (stmt
)
1739 && (is_gimple_assign (stmt
)
1740 || (is_gimple_call (stmt
)
1741 && gimple_call_lhs (stmt
) != NULL_TREE
)
1742 || gimple_code (stmt
) == GIMPLE_COND
1743 || gimple_code (stmt
) == GIMPLE_SWITCH
));
1747 if (gimple_code (stmt
) == GIMPLE_CALL
)
1749 /* Resolve __builtin_constant_p. If it hasn't been
1750 folded to integer_one_node by now, it's fairly
1751 certain that the value simply isn't constant. */
1752 tree callee
= gimple_call_fndecl (stmt
);
1754 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
1755 && DECL_FUNCTION_CODE (callee
) == BUILT_IN_CONSTANT_P
)
1757 propagate_tree_value_into_stmt (&si
, integer_zero_node
);
1758 stmt
= gsi_stmt (si
);
1762 update_stmt_if_modified (stmt
);
1763 eliminate_redundant_computations (&si
);
1764 stmt
= gsi_stmt (si
);
1766 /* Perform simple redundant store elimination. */
1767 if (gimple_assign_single_p (stmt
)
1768 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
1770 tree lhs
= gimple_assign_lhs (stmt
);
1771 tree rhs
= gimple_assign_rhs1 (stmt
);
1774 rhs
= dom_valueize (rhs
);
1775 /* Build a new statement with the RHS and LHS exchanged. */
1776 if (TREE_CODE (rhs
) == SSA_NAME
)
1778 gimple defstmt
= SSA_NAME_DEF_STMT (rhs
);
1779 new_stmt
= gimple_build_assign (rhs
, lhs
);
1780 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1783 new_stmt
= gimple_build_assign (rhs
, lhs
);
1784 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
1785 cached_lhs
= lookup_avail_expr (new_stmt
, false);
1787 && rhs
== cached_lhs
)
1789 basic_block bb
= gimple_bb (stmt
);
1790 unlink_stmt_vdef (stmt
);
1791 if (gsi_remove (&si
, true))
1793 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1795 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1797 release_defs (stmt
);
1803 /* Record any additional equivalences created by this statement. */
1804 if (is_gimple_assign (stmt
))
1805 record_equivalences_from_stmt (stmt
, may_optimize_p
);
1807 /* If STMT is a COND_EXPR and it was modified, then we may know
1808 where it goes. If that is the case, then mark the CFG as altered.
1810 This will cause us to later call remove_unreachable_blocks and
1811 cleanup_tree_cfg when it is safe to do so. It is not safe to
1812 clean things up here since removal of edges and such can trigger
1813 the removal of PHI nodes, which in turn can release SSA_NAMEs to
1816 That's all fine and good, except that once SSA_NAMEs are released
1817 to the manager, we must not call create_ssa_name until all references
1818 to released SSA_NAMEs have been eliminated.
1820 All references to the deleted SSA_NAMEs can not be eliminated until
1821 we remove unreachable blocks.
1823 We can not remove unreachable blocks until after we have completed
1824 any queued jump threading.
1826 We can not complete any queued jump threads until we have taken
1827 appropriate variables out of SSA form. Taking variables out of
1828 SSA form can call create_ssa_name and thus we lose.
1830 Ultimately I suspect we're going to need to change the interface
1831 into the SSA_NAME manager. */
1832 if (gimple_modified_p (stmt
) || modified_p
)
1836 update_stmt_if_modified (stmt
);
1838 if (gimple_code (stmt
) == GIMPLE_COND
)
1839 val
= fold_binary_loc (gimple_location (stmt
),
1840 gimple_cond_code (stmt
), boolean_type_node
,
1841 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
1842 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1843 val
= gimple_switch_index (swtch_stmt
);
1845 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
1848 /* If we simplified a statement in such a way as to be shown that it
1849 cannot trap, update the eh information and the cfg to match. */
1850 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1852 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1854 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1858 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
1859 need_noreturn_fixup
.safe_push (stmt
);
1863 /* Helper for walk_non_aliased_vuses. Determine if we arrived at
1864 the desired memory state. */
1867 vuse_eq (ao_ref
*, tree vuse1
, unsigned int cnt
, void *data
)
1869 tree vuse2
= (tree
) data
;
1873 /* This bounds the stmt walks we perform on reference lookups
1874 to O(1) instead of O(N) where N is the number of dominating
1875 stores leading to a candidate. We re-use the SCCVN param
1876 for this as it is basically the same complexity. */
1877 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1883 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
1884 If found, return its LHS. Otherwise insert STMT in the table and
1887 Also, when an expression is first inserted in the table, it is also
1888 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
1889 we finish processing this block and its children. */
1892 lookup_avail_expr (gimple stmt
, bool insert
)
1894 expr_hash_elt
**slot
;
1897 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
1898 if (gimple_code (stmt
) == GIMPLE_PHI
)
1899 lhs
= gimple_phi_result (stmt
);
1901 lhs
= gimple_get_lhs (stmt
);
1903 class expr_hash_elt
element (stmt
, lhs
);
1905 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1907 fprintf (dump_file
, "LKUP ");
1908 element
.print (dump_file
);
1911 /* Don't bother remembering constant assignments and copy operations.
1912 Constants and copy operations are handled by the constant/copy propagator
1913 in optimize_stmt. */
1914 if (element
.expr()->kind
== EXPR_SINGLE
1915 && (TREE_CODE (element
.expr()->ops
.single
.rhs
) == SSA_NAME
1916 || is_gimple_min_invariant (element
.expr()->ops
.single
.rhs
)))
1919 /* Finally try to find the expression in the main expression hash table. */
1920 slot
= avail_exprs
->find_slot (&element
, (insert
? INSERT
: NO_INSERT
));
1925 else if (*slot
== NULL
)
1927 class expr_hash_elt
*element2
= new expr_hash_elt (element
);
1930 avail_exprs_stack
->record_expr (element2
, NULL
, '2');
1934 /* If we found a redundant memory operation do an alias walk to
1935 check if we can re-use it. */
1936 if (gimple_vuse (stmt
) != (*slot
)->vop ())
1938 tree vuse1
= (*slot
)->vop ();
1939 tree vuse2
= gimple_vuse (stmt
);
1940 /* If we have a load of a register and a candidate in the
1941 hash with vuse1 then try to reach its stmt by walking
1942 up the virtual use-def chain using walk_non_aliased_vuses.
1943 But don't do this when removing expressions from the hash. */
1945 if (!(vuse1
&& vuse2
1946 && gimple_assign_single_p (stmt
)
1947 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
1948 && (ao_ref_init (&ref
, gimple_assign_rhs1 (stmt
)), true)
1949 && walk_non_aliased_vuses (&ref
, vuse2
,
1950 vuse_eq
, NULL
, NULL
, vuse1
) != NULL
))
1954 class expr_hash_elt
*element2
= new expr_hash_elt (element
);
1956 /* Insert the expr into the hash by replacing the current
1957 entry and recording the value to restore in the
1958 avail_exprs_stack. */
1959 avail_exprs_stack
->record_expr (element2
, *slot
, '2');
1966 /* Extract the LHS of the assignment so that it can be used as the current
1967 definition of another variable. */
1968 lhs
= (*slot
)->lhs ();
1970 lhs
= dom_valueize (lhs
);
1972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1974 fprintf (dump_file
, "FIND: ");
1975 print_generic_expr (dump_file
, lhs
, 0);
1976 fprintf (dump_file
, "\n");