1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2016 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 known values of a conditional expression
52 at the exits from its block. */
54 struct cond_equivalence
56 struct hashable_expr cond
;
60 /* Structure for recording edge equivalences.
62 Computing and storing the edge equivalences instead of creating
63 them on-demand can save significant amounts of time, particularly
64 for pathological cases involving switch statements.
66 These structures live for a single iteration of the dominator
67 optimizer in the edge's AUX field. At the end of an iteration we
68 free each of these structures. */
72 /* If this edge creates a simple equivalence, the LHS and RHS of
73 the equivalence will be stored here. */
77 /* Traversing an edge may also indicate one or more particular conditions
79 vec
<cond_equivalence
> cond_equivalences
;
82 /* Track whether or not we have changed the control flow graph. */
83 static bool cfg_altered
;
85 /* Bitmap of blocks that have had EH statements cleaned. We should
86 remove their dead edges eventually. */
87 static bitmap need_eh_cleanup
;
88 static vec
<gimple
*> need_noreturn_fixup
;
90 /* Statistics for dominator optimizations. */
94 long num_exprs_considered
;
100 static struct opt_stats_d opt_stats
;
102 /* Local functions. */
103 static edge
optimize_stmt (basic_block
, gimple_stmt_iterator
,
104 class const_and_copies
*,
105 class avail_exprs_stack
*);
106 static tree
lookup_avail_expr (gimple
*, bool, class avail_exprs_stack
*);
107 static void record_cond (cond_equivalence
*, class avail_exprs_stack
*);
108 static void record_equality (tree
, tree
, class const_and_copies
*);
109 static void record_equivalences_from_phis (basic_block
);
110 static void record_equivalences_from_incoming_edge (basic_block
,
111 class const_and_copies
*,
112 class avail_exprs_stack
*);
113 static void eliminate_redundant_computations (gimple_stmt_iterator
*,
114 class const_and_copies
*,
115 class avail_exprs_stack
*);
116 static void record_equivalences_from_stmt (gimple
*, int,
117 class avail_exprs_stack
*);
118 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
119 static void dump_dominator_optimization_stats (FILE *file
,
120 hash_table
<expr_elt_hasher
> *);
123 /* Free the edge_info data attached to E, if it exists. */
126 free_dom_edge_info (edge e
)
128 struct edge_info
*edge_info
= (struct edge_info
*)e
->aux
;
132 edge_info
->cond_equivalences
.release ();
137 /* Allocate an EDGE_INFO for edge E and attach it to E.
138 Return the new EDGE_INFO structure. */
140 static struct edge_info
*
141 allocate_edge_info (edge e
)
143 struct edge_info
*edge_info
;
145 /* Free the old one, if it exists. */
146 free_dom_edge_info (e
);
148 edge_info
= XCNEW (struct edge_info
);
154 /* Free all EDGE_INFO structures associated with edges in the CFG.
155 If a particular edge can be threaded, copy the redirection
156 target from the EDGE_INFO structure into the edge's AUX field
157 as required by code to update the CFG and SSA graph for
161 free_all_edge_infos (void)
167 FOR_EACH_BB_FN (bb
, cfun
)
169 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
171 free_dom_edge_info (e
);
177 /* Build a cond_equivalence record indicating that the comparison
178 CODE holds between operands OP0 and OP1 and push it to **P. */
181 build_and_record_new_cond (enum tree_code code
,
183 vec
<cond_equivalence
> *p
,
187 struct hashable_expr
*cond
= &c
.cond
;
189 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
191 cond
->type
= boolean_type_node
;
192 cond
->kind
= EXPR_BINARY
;
193 cond
->ops
.binary
.op
= code
;
194 cond
->ops
.binary
.opnd0
= op0
;
195 cond
->ops
.binary
.opnd1
= op1
;
197 c
.value
= val
? boolean_true_node
: boolean_false_node
;
201 /* Record that COND is true and INVERTED is false into the edge information
202 structure. Also record that any conditions dominated by COND are true
205 For example, if a < b is true, then a <= b must also be true. */
208 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
213 if (!COMPARISON_CLASS_P (cond
))
216 op0
= TREE_OPERAND (cond
, 0);
217 op1
= TREE_OPERAND (cond
, 1);
219 switch (TREE_CODE (cond
))
223 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
225 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
226 &edge_info
->cond_equivalences
);
227 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
228 &edge_info
->cond_equivalences
);
231 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
232 ? LE_EXPR
: GE_EXPR
),
233 op0
, op1
, &edge_info
->cond_equivalences
);
234 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
235 &edge_info
->cond_equivalences
);
236 build_and_record_new_cond (EQ_EXPR
, op0
, op1
,
237 &edge_info
->cond_equivalences
, false);
242 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
244 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
245 &edge_info
->cond_equivalences
);
250 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
252 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
253 &edge_info
->cond_equivalences
);
255 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
256 &edge_info
->cond_equivalences
);
257 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
258 &edge_info
->cond_equivalences
);
262 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
263 &edge_info
->cond_equivalences
);
264 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
265 &edge_info
->cond_equivalences
);
266 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
267 &edge_info
->cond_equivalences
);
268 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
269 &edge_info
->cond_equivalences
);
270 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
271 &edge_info
->cond_equivalences
);
272 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
273 &edge_info
->cond_equivalences
);
278 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
279 ? UNLE_EXPR
: UNGE_EXPR
),
280 op0
, op1
, &edge_info
->cond_equivalences
);
281 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
282 &edge_info
->cond_equivalences
);
286 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
287 &edge_info
->cond_equivalences
);
288 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
289 &edge_info
->cond_equivalences
);
293 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
294 &edge_info
->cond_equivalences
);
295 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
296 &edge_info
->cond_equivalences
);
303 /* Now store the original true and false conditions into the first
305 initialize_expr_from_cond (cond
, &c
.cond
);
306 c
.value
= boolean_true_node
;
307 edge_info
->cond_equivalences
.safe_push (c
);
309 /* It is possible for INVERTED to be the negation of a comparison,
310 and not a valid RHS or GIMPLE_COND condition. This happens because
311 invert_truthvalue may return such an expression when asked to invert
312 a floating-point comparison. These comparisons are not assumed to
313 obey the trichotomy law. */
314 initialize_expr_from_cond (inverted
, &c
.cond
);
315 c
.value
= boolean_false_node
;
316 edge_info
->cond_equivalences
.safe_push (c
);
319 /* We have finished optimizing BB, record any information implied by
320 taking a specific outgoing edge from BB. */
323 record_edge_info (basic_block bb
)
325 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
326 struct edge_info
*edge_info
;
328 if (! gsi_end_p (gsi
))
330 gimple
*stmt
= gsi_stmt (gsi
);
331 location_t loc
= gimple_location (stmt
);
333 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
335 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
336 tree index
= gimple_switch_index (switch_stmt
);
338 if (TREE_CODE (index
) == SSA_NAME
)
341 int n_labels
= gimple_switch_num_labels (switch_stmt
);
342 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
346 for (i
= 0; i
< n_labels
; i
++)
348 tree label
= gimple_switch_label (switch_stmt
, i
);
349 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
350 if (CASE_HIGH (label
)
352 || info
[target_bb
->index
])
353 info
[target_bb
->index
] = error_mark_node
;
355 info
[target_bb
->index
] = label
;
358 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
360 basic_block target_bb
= e
->dest
;
361 tree label
= info
[target_bb
->index
];
363 if (label
!= NULL
&& label
!= error_mark_node
)
365 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
367 edge_info
= allocate_edge_info (e
);
368 edge_info
->lhs
= index
;
376 /* A COND_EXPR may create equivalences too. */
377 if (gimple_code (stmt
) == GIMPLE_COND
)
382 tree op0
= gimple_cond_lhs (stmt
);
383 tree op1
= gimple_cond_rhs (stmt
);
384 enum tree_code code
= gimple_cond_code (stmt
);
386 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
388 /* Special case comparing booleans against a constant as we
389 know the value of OP0 on both arms of the branch. i.e., we
390 can record an equivalence for OP0 rather than COND.
392 However, don't do this if the constant isn't zero or one.
393 Such conditionals will get optimized more thoroughly during
395 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
396 && TREE_CODE (op0
) == SSA_NAME
397 && ssa_name_has_boolean_range (op0
)
398 && is_gimple_min_invariant (op1
)
399 && (integer_zerop (op1
) || integer_onep (op1
)))
401 tree true_val
= constant_boolean_node (true, TREE_TYPE (op0
));
402 tree false_val
= constant_boolean_node (false, TREE_TYPE (op0
));
406 edge_info
= allocate_edge_info (true_edge
);
407 edge_info
->lhs
= op0
;
408 edge_info
->rhs
= (integer_zerop (op1
) ? false_val
: true_val
);
410 edge_info
= allocate_edge_info (false_edge
);
411 edge_info
->lhs
= op0
;
412 edge_info
->rhs
= (integer_zerop (op1
) ? true_val
: false_val
);
416 edge_info
= allocate_edge_info (true_edge
);
417 edge_info
->lhs
= op0
;
418 edge_info
->rhs
= (integer_zerop (op1
) ? true_val
: false_val
);
420 edge_info
= allocate_edge_info (false_edge
);
421 edge_info
->lhs
= op0
;
422 edge_info
->rhs
= (integer_zerop (op1
) ? false_val
: true_val
);
425 else if (is_gimple_min_invariant (op0
)
426 && (TREE_CODE (op1
) == SSA_NAME
427 || is_gimple_min_invariant (op1
)))
429 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
430 tree inverted
= invert_truthvalue_loc (loc
, cond
);
431 bool can_infer_simple_equiv
432 = !(HONOR_SIGNED_ZEROS (op0
)
433 && real_zerop (op0
));
434 struct edge_info
*edge_info
;
436 edge_info
= allocate_edge_info (true_edge
);
437 record_conditions (edge_info
, cond
, inverted
);
439 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
441 edge_info
->lhs
= op1
;
442 edge_info
->rhs
= op0
;
445 edge_info
= allocate_edge_info (false_edge
);
446 record_conditions (edge_info
, inverted
, cond
);
448 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
450 edge_info
->lhs
= op1
;
451 edge_info
->rhs
= op0
;
455 else if (TREE_CODE (op0
) == SSA_NAME
456 && (TREE_CODE (op1
) == SSA_NAME
457 || is_gimple_min_invariant (op1
)))
459 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
460 tree inverted
= invert_truthvalue_loc (loc
, cond
);
461 bool can_infer_simple_equiv
462 = !(HONOR_SIGNED_ZEROS (op1
)
463 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
464 struct edge_info
*edge_info
;
466 edge_info
= allocate_edge_info (true_edge
);
467 record_conditions (edge_info
, cond
, inverted
);
469 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
471 edge_info
->lhs
= op0
;
472 edge_info
->rhs
= op1
;
475 edge_info
= allocate_edge_info (false_edge
);
476 record_conditions (edge_info
, inverted
, cond
);
478 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
480 edge_info
->lhs
= op0
;
481 edge_info
->rhs
= op1
;
486 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
491 class dom_opt_dom_walker
: public dom_walker
494 dom_opt_dom_walker (cdi_direction direction
,
495 class const_and_copies
*const_and_copies
,
496 class avail_exprs_stack
*avail_exprs_stack
)
497 : dom_walker (direction
, true),
498 m_const_and_copies (const_and_copies
),
499 m_avail_exprs_stack (avail_exprs_stack
),
500 m_dummy_cond (NULL
) {}
502 virtual edge
before_dom_children (basic_block
);
503 virtual void after_dom_children (basic_block
);
506 void thread_across_edge (edge
);
508 /* Unwindable equivalences, both const/copy and expression varieties. */
509 class const_and_copies
*m_const_and_copies
;
510 class avail_exprs_stack
*m_avail_exprs_stack
;
515 /* Jump threading, redundancy elimination and const/copy propagation.
517 This pass may expose new symbols that need to be renamed into SSA. For
518 every new symbol exposed, its corresponding bit will be set in
523 const pass_data pass_data_dominator
=
525 GIMPLE_PASS
, /* type */
527 OPTGROUP_NONE
, /* optinfo_flags */
528 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
529 ( PROP_cfg
| PROP_ssa
), /* properties_required */
530 0, /* properties_provided */
531 0, /* properties_destroyed */
532 0, /* todo_flags_start */
533 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
536 class pass_dominator
: public gimple_opt_pass
539 pass_dominator (gcc::context
*ctxt
)
540 : gimple_opt_pass (pass_data_dominator
, ctxt
),
541 may_peel_loop_headers_p (false)
544 /* opt_pass methods: */
545 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
546 void set_pass_param (unsigned int n
, bool param
)
549 may_peel_loop_headers_p
= param
;
551 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
552 virtual unsigned int execute (function
*);
555 /* This flag is used to prevent loops from being peeled repeatedly in jump
556 threading; it will be removed once we preserve loop structures throughout
557 the compilation -- we will be able to mark the affected loops directly in
558 jump threading, and avoid peeling them next time. */
559 bool may_peel_loop_headers_p
;
560 }; // class pass_dominator
563 pass_dominator::execute (function
*fun
)
565 memset (&opt_stats
, 0, sizeof (opt_stats
));
567 /* Create our hash tables. */
568 hash_table
<expr_elt_hasher
> *avail_exprs
569 = new hash_table
<expr_elt_hasher
> (1024);
570 class avail_exprs_stack
*avail_exprs_stack
571 = new class avail_exprs_stack (avail_exprs
);
572 class const_and_copies
*const_and_copies
= new class const_and_copies ();
573 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
574 need_noreturn_fixup
.create (0);
576 calculate_dominance_info (CDI_DOMINATORS
);
579 /* We need to know loop structures in order to avoid destroying them
580 in jump threading. Note that we still can e.g. thread through loop
581 headers to an exit edge, or through loop header to the loop body, assuming
582 that we update the loop info.
584 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
585 to several overly conservative bail-outs in jump threading, case
586 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
587 missing. We should improve jump threading in future then
588 LOOPS_HAVE_PREHEADERS won't be needed here. */
589 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
591 /* Initialize the value-handle array. */
592 threadedge_initialize_values ();
594 /* We need accurate information regarding back edges in the CFG
595 for jump threading; this may include back edges that are not part of
597 mark_dfs_back_edges ();
599 /* We want to create the edge info structures before the dominator walk
600 so that they'll be in place for the jump threader, particularly when
601 threading through a join block.
603 The conditions will be lazily updated with global equivalences as
604 we reach them during the dominator walk. */
606 FOR_EACH_BB_FN (bb
, fun
)
607 record_edge_info (bb
);
609 /* Recursively walk the dominator tree optimizing statements. */
610 dom_opt_dom_walker
walker (CDI_DOMINATORS
,
613 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
615 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
616 edge. When found, remove jump threads which contain any outgoing
617 edge from the affected block. */
620 FOR_EACH_BB_FN (bb
, fun
)
625 /* First see if there are any edges without EDGE_EXECUTABLE
628 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
630 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
637 /* If there were any such edges found, then remove jump threads
638 containing any edge leaving BB. */
640 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
641 remove_jump_threads_including (e
);
646 gimple_stmt_iterator gsi
;
648 FOR_EACH_BB_FN (bb
, fun
)
650 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
651 update_stmt_if_modified (gsi_stmt (gsi
));
655 /* If we exposed any new variables, go ahead and put them into
656 SSA form now, before we handle jump threading. This simplifies
657 interactions between rewriting of _DECL nodes into SSA form
658 and rewriting SSA_NAME nodes into SSA form after block
659 duplication and CFG manipulation. */
660 update_ssa (TODO_update_ssa
);
662 free_all_edge_infos ();
664 /* Thread jumps, creating duplicate blocks as needed. */
665 cfg_altered
|= thread_through_all_blocks (may_peel_loop_headers_p
);
668 free_dominance_info (CDI_DOMINATORS
);
670 /* Removal of statements may make some EH edges dead. Purge
671 such edges from the CFG as needed. */
672 if (!bitmap_empty_p (need_eh_cleanup
))
677 /* Jump threading may have created forwarder blocks from blocks
678 needing EH cleanup; the new successor of these blocks, which
679 has inherited from the original block, needs the cleanup.
680 Don't clear bits in the bitmap, as that can break the bitmap
682 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
684 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
687 while (single_succ_p (bb
)
688 && (single_succ_edge (bb
)->flags
& EDGE_EH
) == 0)
689 bb
= single_succ (bb
);
690 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
692 if ((unsigned) bb
->index
!= i
)
693 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
696 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
697 bitmap_clear (need_eh_cleanup
);
700 /* Fixup stmts that became noreturn calls. This may require splitting
701 blocks and thus isn't possible during the dominator walk or before
702 jump threading finished. Do this in reverse order so we don't
703 inadvertedly remove a stmt we want to fixup by visiting a dominating
704 now noreturn call first. */
705 while (!need_noreturn_fixup
.is_empty ())
707 gimple
*stmt
= need_noreturn_fixup
.pop ();
708 if (dump_file
&& dump_flags
& TDF_DETAILS
)
710 fprintf (dump_file
, "Fixing up noreturn call ");
711 print_gimple_stmt (dump_file
, stmt
, 0, 0);
712 fprintf (dump_file
, "\n");
714 fixup_noreturn_call (stmt
);
717 statistics_counter_event (fun
, "Redundant expressions eliminated",
719 statistics_counter_event (fun
, "Constants propagated",
720 opt_stats
.num_const_prop
);
721 statistics_counter_event (fun
, "Copies propagated",
722 opt_stats
.num_copy_prop
);
724 /* Debugging dumps. */
725 if (dump_file
&& (dump_flags
& TDF_STATS
))
726 dump_dominator_optimization_stats (dump_file
, avail_exprs
);
728 loop_optimizer_finalize ();
730 /* Delete our main hashtable. */
734 /* Free asserted bitmaps and stacks. */
735 BITMAP_FREE (need_eh_cleanup
);
736 need_noreturn_fixup
.release ();
737 delete avail_exprs_stack
;
738 delete const_and_copies
;
740 /* Free the value-handle array. */
741 threadedge_finalize_values ();
749 make_pass_dominator (gcc::context
*ctxt
)
751 return new pass_dominator (ctxt
);
755 /* Given a conditional statement CONDSTMT, convert the
756 condition to a canonical form. */
759 canonicalize_comparison (gcond
*condstmt
)
765 gcc_assert (gimple_code (condstmt
) == GIMPLE_COND
);
767 op0
= gimple_cond_lhs (condstmt
);
768 op1
= gimple_cond_rhs (condstmt
);
770 code
= gimple_cond_code (condstmt
);
772 /* If it would be profitable to swap the operands, then do so to
773 canonicalize the statement, enabling better optimization.
775 By placing canonicalization of such expressions here we
776 transparently keep statements in canonical form, even
777 when the statement is modified. */
778 if (tree_swap_operands_p (op0
, op1
, false))
780 /* For relationals we need to swap the operands
781 and change the code. */
787 code
= swap_tree_comparison (code
);
789 gimple_cond_set_code (condstmt
, code
);
790 gimple_cond_set_lhs (condstmt
, op1
);
791 gimple_cond_set_rhs (condstmt
, op0
);
793 update_stmt (condstmt
);
798 /* A trivial wrapper so that we can present the generic jump
799 threading code with a simple API for simplifying statements. */
801 simplify_stmt_for_jump_threading (gimple
*stmt
,
802 gimple
*within_stmt ATTRIBUTE_UNUSED
,
803 class avail_exprs_stack
*avail_exprs_stack
)
805 return lookup_avail_expr (stmt
, false, avail_exprs_stack
);
808 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
811 dom_valueize (tree t
)
813 if (TREE_CODE (t
) == SSA_NAME
)
815 tree tem
= SSA_NAME_VALUE (t
);
822 /* We have just found an equivalence for LHS on an edge E.
823 Look backwards to other uses of LHS and see if we can derive
824 additional equivalences that are valid on edge E. */
826 back_propagate_equivalences (tree lhs
, edge e
,
827 class const_and_copies
*const_and_copies
)
830 imm_use_iterator iter
;
832 basic_block dest
= e
->dest
;
834 /* Iterate over the uses of LHS to see if any dominate E->dest.
835 If so, they may create useful equivalences too.
837 ??? If the code gets re-organized to a worklist to catch more
838 indirect opportunities and it is made to handle PHIs then this
839 should only consider use_stmts in basic-blocks we have already visited. */
840 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
842 gimple
*use_stmt
= USE_STMT (use_p
);
844 /* Often the use is in DEST, which we trivially know we can't use.
845 This is cheaper than the dominator set tests below. */
846 if (dest
== gimple_bb (use_stmt
))
849 /* Filter out statements that can never produce a useful
851 tree lhs2
= gimple_get_lhs (use_stmt
);
852 if (!lhs2
|| TREE_CODE (lhs2
) != SSA_NAME
)
855 /* Profiling has shown the domination tests here can be fairly
856 expensive. We get significant improvements by building the
857 set of blocks that dominate BB. We can then just test
858 for set membership below.
860 We also initialize the set lazily since often the only uses
861 are going to be in the same block as DEST. */
864 domby
= BITMAP_ALLOC (NULL
);
865 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
868 bitmap_set_bit (domby
, bb
->index
);
869 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
873 /* This tests if USE_STMT does not dominate DEST. */
874 if (!bitmap_bit_p (domby
, gimple_bb (use_stmt
)->index
))
877 /* At this point USE_STMT dominates DEST and may result in a
878 useful equivalence. Try to simplify its RHS to a constant
880 tree res
= gimple_fold_stmt_to_constant_1 (use_stmt
, dom_valueize
,
881 no_follow_ssa_edges
);
882 if (res
&& (TREE_CODE (res
) == SSA_NAME
|| is_gimple_min_invariant (res
)))
883 record_equality (lhs2
, res
, const_and_copies
);
890 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
891 by traversing edge E (which are cached in E->aux).
893 Callers are responsible for managing the unwinding markers. */
895 record_temporary_equivalences (edge e
,
896 class const_and_copies
*const_and_copies
,
897 class avail_exprs_stack
*avail_exprs_stack
)
900 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
902 /* If we have info associated with this edge, record it into
903 our equivalence tables. */
906 cond_equivalence
*eq
;
907 /* If we have 0 = COND or 1 = COND equivalences, record them
908 into our expression hash tables. */
909 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
910 record_cond (eq
, avail_exprs_stack
);
912 tree lhs
= edge_info
->lhs
;
913 if (!lhs
|| TREE_CODE (lhs
) != SSA_NAME
)
916 /* Record the simple NAME = VALUE equivalence. */
917 tree rhs
= edge_info
->rhs
;
918 record_equality (lhs
, rhs
, const_and_copies
);
920 /* We already recorded that LHS = RHS, with canonicalization,
921 value chain following, etc.
923 We also want to return RHS = LHS, but without any canonicalization
924 or value chain following. */
925 if (TREE_CODE (rhs
) == SSA_NAME
)
926 const_and_copies
->record_const_or_copy_raw (rhs
, lhs
,
927 SSA_NAME_VALUE (rhs
));
929 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
930 set via a widening type conversion, then we may be able to record
931 additional equivalences. */
932 if (TREE_CODE (rhs
) == INTEGER_CST
)
934 gimple
*defstmt
= SSA_NAME_DEF_STMT (lhs
);
937 && is_gimple_assign (defstmt
)
938 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt
)))
940 tree old_rhs
= gimple_assign_rhs1 (defstmt
);
942 /* If the conversion widens the original value and
943 the constant is in the range of the type of OLD_RHS,
944 then convert the constant and record the equivalence.
946 Note that int_fits_type_p does not check the precision
947 if the upper and lower bounds are OK. */
948 if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs
))
949 && (TYPE_PRECISION (TREE_TYPE (lhs
))
950 > TYPE_PRECISION (TREE_TYPE (old_rhs
)))
951 && int_fits_type_p (rhs
, TREE_TYPE (old_rhs
)))
953 tree newval
= fold_convert (TREE_TYPE (old_rhs
), rhs
);
954 record_equality (old_rhs
, newval
, const_and_copies
);
959 /* Any equivalence found for LHS may result in additional
960 equivalences for other uses of LHS that we have already
962 back_propagate_equivalences (lhs
, e
, const_and_copies
);
966 /* Wrapper for common code to attempt to thread an edge. For example,
967 it handles lazily building the dummy condition and the bookkeeping
968 when jump threading is successful. */
971 dom_opt_dom_walker::thread_across_edge (edge e
)
975 gimple_build_cond (NE_EXPR
,
976 integer_zero_node
, integer_zero_node
,
979 /* Push a marker on both stacks so we can unwind the tables back to their
981 m_avail_exprs_stack
->push_marker ();
982 m_const_and_copies
->push_marker ();
984 /* With all the edge equivalences in the tables, go ahead and attempt
985 to thread through E->dest. */
986 ::thread_across_edge (m_dummy_cond
, e
, false,
987 m_const_and_copies
, m_avail_exprs_stack
,
988 simplify_stmt_for_jump_threading
);
990 /* And restore the various tables to their state before
991 we threaded this edge.
993 XXX The code in tree-ssa-threadedge.c will restore the state of
994 the const_and_copies table. We we just have to restore the expression
996 m_avail_exprs_stack
->pop_to_marker ();
999 /* PHI nodes can create equivalences too.
1001 Ignoring any alternatives which are the same as the result, if
1002 all the alternatives are equal, then the PHI node creates an
1006 record_equivalences_from_phis (basic_block bb
)
1010 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1012 gphi
*phi
= gsi
.phi ();
1014 tree lhs
= gimple_phi_result (phi
);
1018 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1020 tree t
= gimple_phi_arg_def (phi
, i
);
1022 /* Ignore alternatives which are the same as our LHS. Since
1023 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1024 can simply compare pointers. */
1028 /* If the associated edge is not marked as executable, then it
1030 if ((gimple_phi_arg_edge (phi
, i
)->flags
& EDGE_EXECUTABLE
) == 0)
1033 t
= dom_valueize (t
);
1035 /* If we have not processed an alternative yet, then set
1036 RHS to this alternative. */
1039 /* If we have processed an alternative (stored in RHS), then
1040 see if it is equal to this one. If it isn't, then stop
1042 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1046 /* If we had no interesting alternatives, then all the RHS alternatives
1047 must have been the same as LHS. */
1051 /* If we managed to iterate through each PHI alternative without
1052 breaking out of the loop, then we have a PHI which may create
1053 a useful equivalence. We do not need to record unwind data for
1054 this, since this is a true assignment and not an equivalence
1055 inferred from a comparison. All uses of this ssa name are dominated
1056 by this assignment, so unwinding just costs time and space. */
1057 if (i
== gimple_phi_num_args (phi
)
1058 && may_propagate_copy (lhs
, rhs
))
1059 set_ssa_name_value (lhs
, rhs
);
1063 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1064 return that edge. Otherwise return NULL. */
1066 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1072 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1074 /* A loop back edge can be identified by the destination of
1075 the edge dominating the source of the edge. */
1076 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1079 /* We can safely ignore edges that are not executable. */
1080 if ((e
->flags
& EDGE_EXECUTABLE
) == 0)
1083 /* If we have already seen a non-loop edge, then we must have
1084 multiple incoming non-loop edges and thus we return NULL. */
1088 /* This is the first non-loop incoming edge we have found. Record
1096 /* Record any equivalences created by the incoming edge to BB into
1097 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
1098 incoming edge, then no equivalence is created. */
1101 record_equivalences_from_incoming_edge (basic_block bb
,
1102 class const_and_copies
*const_and_copies
,
1103 class avail_exprs_stack
*avail_exprs_stack
)
1108 /* If our parent block ended with a control statement, then we may be
1109 able to record some equivalences based on which outgoing edge from
1110 the parent was followed. */
1111 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1113 e
= single_incoming_edge_ignoring_loop_edges (bb
);
1115 /* If we had a single incoming edge from our parent block, then enter
1116 any data associated with the edge into our tables. */
1117 if (e
&& e
->src
== parent
)
1118 record_temporary_equivalences (e
, const_and_copies
, avail_exprs_stack
);
1121 /* Dump statistics for the hash table HTAB. */
1124 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
1126 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1127 (long) htab
.size (),
1128 (long) htab
.elements (),
1129 htab
.collisions ());
1132 /* Dump SSA statistics on FILE. */
1135 dump_dominator_optimization_stats (FILE *file
,
1136 hash_table
<expr_elt_hasher
> *avail_exprs
)
1138 fprintf (file
, "Total number of statements: %6ld\n\n",
1139 opt_stats
.num_stmts
);
1140 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1141 opt_stats
.num_exprs_considered
);
1143 fprintf (file
, "\nHash table statistics:\n");
1145 fprintf (file
, " avail_exprs: ");
1146 htab_statistics (file
, *avail_exprs
);
1150 /* Enter condition equivalence P into AVAIL_EXPRS_HASH.
1152 This indicates that a conditional expression has a known
1156 record_cond (cond_equivalence
*p
,
1157 class avail_exprs_stack
*avail_exprs_stack
)
1159 class expr_hash_elt
*element
= new expr_hash_elt (&p
->cond
, p
->value
);
1160 expr_hash_elt
**slot
;
1162 hash_table
<expr_elt_hasher
> *avail_exprs
= avail_exprs_stack
->avail_exprs ();
1163 slot
= avail_exprs
->find_slot_with_hash (element
, element
->hash (), INSERT
);
1167 avail_exprs_stack
->record_expr (element
, NULL
, '1');
1173 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1174 This constrains the cases in which we may treat this as assignment. */
1177 record_equality (tree x
, tree y
, class const_and_copies
*const_and_copies
)
1179 tree prev_x
= NULL
, prev_y
= NULL
;
1181 if (tree_swap_operands_p (x
, y
, false))
1184 /* Most of the time tree_swap_operands_p does what we want. But there
1185 are cases where we know one operand is better for copy propagation than
1186 the other. Given no other code cares about ordering of equality
1187 comparison operators for that purpose, we just handle the special cases
1189 if (TREE_CODE (x
) == SSA_NAME
&& TREE_CODE (y
) == SSA_NAME
)
1191 /* If one operand is a single use operand, then make it
1192 X. This will preserve its single use properly and if this
1193 conditional is eliminated, the computation of X can be
1194 eliminated as well. */
1195 if (has_single_use (y
) && ! has_single_use (x
))
1198 if (TREE_CODE (x
) == SSA_NAME
)
1199 prev_x
= SSA_NAME_VALUE (x
);
1200 if (TREE_CODE (y
) == SSA_NAME
)
1201 prev_y
= SSA_NAME_VALUE (y
);
1203 /* If one of the previous values is invariant, or invariant in more loops
1204 (by depth), then use that.
1205 Otherwise it doesn't matter which value we choose, just so
1206 long as we canonicalize on one value. */
1207 if (is_gimple_min_invariant (y
))
1209 else if (is_gimple_min_invariant (x
))
1210 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1211 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1212 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1216 /* After the swapping, we must have one SSA_NAME. */
1217 if (TREE_CODE (x
) != SSA_NAME
)
1220 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1221 variable compared against zero. If we're honoring signed zeros,
1222 then we cannot record this value unless we know that the value is
1224 if (HONOR_SIGNED_ZEROS (x
)
1225 && (TREE_CODE (y
) != REAL_CST
1226 || real_equal (&dconst0
, &TREE_REAL_CST (y
))))
1229 const_and_copies
->record_const_or_copy (x
, y
, prev_x
);
1232 /* Returns true when STMT is a simple iv increment. It detects the
1233 following situation:
1235 i_1 = phi (..., i_2)
1236 i_2 = i_1 +/- ... */
1239 simple_iv_increment_p (gimple
*stmt
)
1241 enum tree_code code
;
1246 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1249 lhs
= gimple_assign_lhs (stmt
);
1250 if (TREE_CODE (lhs
) != SSA_NAME
)
1253 code
= gimple_assign_rhs_code (stmt
);
1254 if (code
!= PLUS_EXPR
1255 && code
!= MINUS_EXPR
1256 && code
!= POINTER_PLUS_EXPR
)
1259 preinc
= gimple_assign_rhs1 (stmt
);
1260 if (TREE_CODE (preinc
) != SSA_NAME
)
1263 phi
= SSA_NAME_DEF_STMT (preinc
);
1264 if (gimple_code (phi
) != GIMPLE_PHI
)
1267 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1268 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1274 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1275 successors of BB. */
1278 cprop_into_successor_phis (basic_block bb
,
1279 class const_and_copies
*const_and_copies
)
1284 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1289 /* If this is an abnormal edge, then we do not want to copy propagate
1290 into the PHI alternative associated with this edge. */
1291 if (e
->flags
& EDGE_ABNORMAL
)
1294 gsi
= gsi_start_phis (e
->dest
);
1295 if (gsi_end_p (gsi
))
1298 /* We may have an equivalence associated with this edge. While
1299 we can not propagate it into non-dominated blocks, we can
1300 propagate them into PHIs in non-dominated blocks. */
1302 /* Push the unwind marker so we can reset the const and copies
1303 table back to its original state after processing this edge. */
1304 const_and_copies
->push_marker ();
1306 /* Extract and record any simple NAME = VALUE equivalences.
1308 Don't bother with [01] = COND equivalences, they're not useful
1310 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
1313 tree lhs
= edge_info
->lhs
;
1314 tree rhs
= edge_info
->rhs
;
1316 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1317 const_and_copies
->record_const_or_copy (lhs
, rhs
);
1321 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1324 use_operand_p orig_p
;
1326 gphi
*phi
= gsi
.phi ();
1328 /* The alternative may be associated with a constant, so verify
1329 it is an SSA_NAME before doing anything with it. */
1330 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1331 orig_val
= get_use_from_ptr (orig_p
);
1332 if (TREE_CODE (orig_val
) != SSA_NAME
)
1335 /* If we have *ORIG_P in our constant/copy table, then replace
1336 ORIG_P with its value in our constant/copy table. */
1337 new_val
= SSA_NAME_VALUE (orig_val
);
1339 && new_val
!= orig_val
1340 && may_propagate_copy (orig_val
, new_val
))
1341 propagate_value (orig_p
, new_val
);
1344 const_and_copies
->pop_to_marker ();
1349 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1351 gimple_stmt_iterator gsi
;
1353 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1354 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1356 /* Push a marker on the stacks of local information so that we know how
1357 far to unwind when we finalize this block. */
1358 m_avail_exprs_stack
->push_marker ();
1359 m_const_and_copies
->push_marker ();
1361 record_equivalences_from_incoming_edge (bb
, m_const_and_copies
,
1362 m_avail_exprs_stack
);
1364 /* PHI nodes can create equivalences too. */
1365 record_equivalences_from_phis (bb
);
1367 /* Create equivalences from redundant PHIs. PHIs are only truly
1368 redundant when they exist in the same block, so push another
1369 marker and unwind right afterwards. */
1370 m_avail_exprs_stack
->push_marker ();
1371 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1372 eliminate_redundant_computations (&gsi
, m_const_and_copies
,
1373 m_avail_exprs_stack
);
1374 m_avail_exprs_stack
->pop_to_marker ();
1376 edge taken_edge
= NULL
;
1377 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1379 = optimize_stmt (bb
, gsi
, m_const_and_copies
, m_avail_exprs_stack
);
1381 /* Now prepare to process dominated blocks. */
1382 record_edge_info (bb
);
1383 cprop_into_successor_phis (bb
, m_const_and_copies
);
1384 if (taken_edge
&& !dbg_cnt (dom_unreachable_edges
))
1390 /* We have finished processing the dominator children of BB, perform
1391 any finalization actions in preparation for leaving this node in
1392 the dominator tree. */
1395 dom_opt_dom_walker::after_dom_children (basic_block bb
)
1399 /* If we have an outgoing edge to a block with multiple incoming and
1400 outgoing edges, then we may be able to thread the edge, i.e., we
1401 may be able to statically determine which of the outgoing edges
1402 will be traversed when the incoming edge from BB is traversed. */
1403 if (single_succ_p (bb
)
1404 && (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
) == 0
1405 && potentially_threadable_block (single_succ (bb
)))
1407 thread_across_edge (single_succ_edge (bb
));
1409 else if ((last
= last_stmt (bb
))
1410 && gimple_code (last
) == GIMPLE_COND
1411 && EDGE_COUNT (bb
->succs
) == 2
1412 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
1413 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
1415 edge true_edge
, false_edge
;
1417 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1419 /* Only try to thread the edge if it reaches a target block with
1420 more than one predecessor and more than one successor. */
1421 if (potentially_threadable_block (true_edge
->dest
))
1422 thread_across_edge (true_edge
);
1424 /* Similarly for the ELSE arm. */
1425 if (potentially_threadable_block (false_edge
->dest
))
1426 thread_across_edge (false_edge
);
1430 /* These remove expressions local to BB from the tables. */
1431 m_avail_exprs_stack
->pop_to_marker ();
1432 m_const_and_copies
->pop_to_marker ();
1435 /* Search for redundant computations in STMT. If any are found, then
1436 replace them with the variable holding the result of the computation.
1438 If safe, record this expression into AVAIL_EXPRS_STACK and
1439 CONST_AND_COPIES. */
1442 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
,
1443 class const_and_copies
*const_and_copies
,
1444 class avail_exprs_stack
*avail_exprs_stack
)
1450 bool assigns_var_p
= false;
1452 gimple
*stmt
= gsi_stmt (*gsi
);
1454 if (gimple_code (stmt
) == GIMPLE_PHI
)
1455 def
= gimple_phi_result (stmt
);
1457 def
= gimple_get_lhs (stmt
);
1459 /* Certain expressions on the RHS can be optimized away, but can not
1460 themselves be entered into the hash tables. */
1462 || TREE_CODE (def
) != SSA_NAME
1463 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1464 || gimple_vdef (stmt
)
1465 /* Do not record equivalences for increments of ivs. This would create
1466 overlapping live ranges for a very questionable gain. */
1467 || simple_iv_increment_p (stmt
))
1470 /* Check if the expression has been computed before. */
1471 cached_lhs
= lookup_avail_expr (stmt
, insert
, avail_exprs_stack
);
1473 opt_stats
.num_exprs_considered
++;
1475 /* Get the type of the expression we are trying to optimize. */
1476 if (is_gimple_assign (stmt
))
1478 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1479 assigns_var_p
= true;
1481 else if (gimple_code (stmt
) == GIMPLE_COND
)
1482 expr_type
= boolean_type_node
;
1483 else if (is_gimple_call (stmt
))
1485 gcc_assert (gimple_call_lhs (stmt
));
1486 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1487 assigns_var_p
= true;
1489 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1490 expr_type
= TREE_TYPE (gimple_switch_index (swtch_stmt
));
1491 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1492 /* We can't propagate into a phi, so the logic below doesn't apply.
1493 Instead record an equivalence between the cached LHS and the
1494 PHI result of this statement, provided they are in the same block.
1495 This should be sufficient to kill the redundant phi. */
1497 if (def
&& cached_lhs
)
1498 const_and_copies
->record_const_or_copy (def
, cached_lhs
);
1507 /* It is safe to ignore types here since we have already done
1508 type checking in the hashing and equality routines. In fact
1509 type checking here merely gets in the way of constant
1510 propagation. Also, make sure that it is safe to propagate
1511 CACHED_LHS into the expression in STMT. */
1512 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1514 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1515 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1517 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1518 || is_gimple_min_invariant (cached_lhs
));
1520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1522 fprintf (dump_file
, " Replaced redundant expr '");
1523 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1524 fprintf (dump_file
, "' with '");
1525 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1526 fprintf (dump_file
, "'\n");
1532 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1533 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1535 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1537 /* Since it is always necessary to mark the result as modified,
1538 perhaps we should move this into propagate_tree_value_into_stmt
1540 gimple_set_modified (gsi_stmt (*gsi
), true);
1544 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1545 the available expressions table or the const_and_copies table.
1546 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1548 We handle only very simple copy equivalences here. The heavy
1549 lifing is done by eliminate_redundant_computations. */
1552 record_equivalences_from_stmt (gimple
*stmt
, int may_optimize_p
,
1553 class avail_exprs_stack
*avail_exprs_stack
)
1556 enum tree_code lhs_code
;
1558 gcc_assert (is_gimple_assign (stmt
));
1560 lhs
= gimple_assign_lhs (stmt
);
1561 lhs_code
= TREE_CODE (lhs
);
1563 if (lhs_code
== SSA_NAME
1564 && gimple_assign_single_p (stmt
))
1566 tree rhs
= gimple_assign_rhs1 (stmt
);
1568 /* If the RHS of the assignment is a constant or another variable that
1569 may be propagated, register it in the CONST_AND_COPIES table. We
1570 do not need to record unwind data for this, since this is a true
1571 assignment and not an equivalence inferred from a comparison. All
1572 uses of this ssa name are dominated by this assignment, so unwinding
1573 just costs time and space. */
1575 && (TREE_CODE (rhs
) == SSA_NAME
1576 || is_gimple_min_invariant (rhs
)))
1578 rhs
= dom_valueize (rhs
);
1580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1582 fprintf (dump_file
, "==== ASGN ");
1583 print_generic_expr (dump_file
, lhs
, 0);
1584 fprintf (dump_file
, " = ");
1585 print_generic_expr (dump_file
, rhs
, 0);
1586 fprintf (dump_file
, "\n");
1589 set_ssa_name_value (lhs
, rhs
);
1593 /* Make sure we can propagate &x + CST. */
1594 if (lhs_code
== SSA_NAME
1595 && gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
1596 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
1597 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == INTEGER_CST
)
1599 tree op0
= gimple_assign_rhs1 (stmt
);
1600 tree op1
= gimple_assign_rhs2 (stmt
);
1602 = build_fold_addr_expr (fold_build2 (MEM_REF
,
1603 TREE_TYPE (TREE_TYPE (op0
)),
1605 fold_convert (ptr_type_node
,
1607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1609 fprintf (dump_file
, "==== ASGN ");
1610 print_generic_expr (dump_file
, lhs
, 0);
1611 fprintf (dump_file
, " = ");
1612 print_generic_expr (dump_file
, new_rhs
, 0);
1613 fprintf (dump_file
, "\n");
1616 set_ssa_name_value (lhs
, new_rhs
);
1619 /* A memory store, even an aliased store, creates a useful
1620 equivalence. By exchanging the LHS and RHS, creating suitable
1621 vops and recording the result in the available expression table,
1622 we may be able to expose more redundant loads. */
1623 if (!gimple_has_volatile_ops (stmt
)
1624 && gimple_references_memory_p (stmt
)
1625 && gimple_assign_single_p (stmt
)
1626 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1627 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
1628 && !is_gimple_reg (lhs
))
1630 tree rhs
= gimple_assign_rhs1 (stmt
);
1633 /* Build a new statement with the RHS and LHS exchanged. */
1634 if (TREE_CODE (rhs
) == SSA_NAME
)
1636 /* NOTE tuples. The call to gimple_build_assign below replaced
1637 a call to build_gimple_modify_stmt, which did not set the
1638 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1639 may cause an SSA validation failure, as the LHS may be a
1640 default-initialized name and should have no definition. I'm
1641 a bit dubious of this, as the artificial statement that we
1642 generate here may in fact be ill-formed, but it is simply
1643 used as an internal device in this pass, and never becomes
1645 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1646 new_stmt
= gimple_build_assign (rhs
, lhs
);
1647 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1650 new_stmt
= gimple_build_assign (rhs
, lhs
);
1652 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
1654 /* Finally enter the statement into the available expression
1656 lookup_avail_expr (new_stmt
, true, avail_exprs_stack
);
1660 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1661 CONST_AND_COPIES. */
1664 cprop_operand (gimple
*stmt
, use_operand_p op_p
)
1667 tree op
= USE_FROM_PTR (op_p
);
1669 /* If the operand has a known constant value or it is known to be a
1670 copy of some other variable, use the value or copy stored in
1671 CONST_AND_COPIES. */
1672 val
= SSA_NAME_VALUE (op
);
1673 if (val
&& val
!= op
)
1675 /* Do not replace hard register operands in asm statements. */
1676 if (gimple_code (stmt
) == GIMPLE_ASM
1677 && !may_propagate_copy_into_asm (op
))
1680 /* Certain operands are not allowed to be copy propagated due
1681 to their interaction with exception handling and some GCC
1683 if (!may_propagate_copy (op
, val
))
1686 /* Do not propagate copies into BIVs.
1687 See PR23821 and PR62217 for how this can disturb IV and
1688 number of iteration analysis. */
1689 if (TREE_CODE (val
) != INTEGER_CST
)
1691 gimple
*def
= SSA_NAME_DEF_STMT (op
);
1692 if (gimple_code (def
) == GIMPLE_PHI
1693 && gimple_bb (def
)->loop_father
->header
== gimple_bb (def
))
1698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1700 fprintf (dump_file
, " Replaced '");
1701 print_generic_expr (dump_file
, op
, dump_flags
);
1702 fprintf (dump_file
, "' with %s '",
1703 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1704 print_generic_expr (dump_file
, val
, dump_flags
);
1705 fprintf (dump_file
, "'\n");
1708 if (TREE_CODE (val
) != SSA_NAME
)
1709 opt_stats
.num_const_prop
++;
1711 opt_stats
.num_copy_prop
++;
1713 propagate_value (op_p
, val
);
1715 /* And note that we modified this statement. This is now
1716 safe, even if we changed virtual operands since we will
1717 rescan the statement and rewrite its operands again. */
1718 gimple_set_modified (stmt
, true);
1722 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1723 known value for that SSA_NAME (or NULL if no value is known).
1725 Propagate values from CONST_AND_COPIES into the uses, vuses and
1726 vdef_ops of STMT. */
1729 cprop_into_stmt (gimple
*stmt
)
1734 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
1735 cprop_operand (stmt
, op_p
);
1738 /* Optimize the statement in block BB pointed to by iterator SI
1739 using equivalences from CONST_AND_COPIES and AVAIL_EXPRS_STACK.
1741 We try to perform some simplistic global redundancy elimination and
1742 constant propagation:
1744 1- To detect global redundancy, we keep track of expressions that have
1745 been computed in this block and its dominators. If we find that the
1746 same expression is computed more than once, we eliminate repeated
1747 computations by using the target of the first one.
1749 2- Constant values and copy assignments. This is used to do very
1750 simplistic constant and copy propagation. When a constant or copy
1751 assignment is found, we map the value on the RHS of the assignment to
1752 the variable in the LHS in the CONST_AND_COPIES table. */
1755 optimize_stmt (basic_block bb
, gimple_stmt_iterator si
,
1756 class const_and_copies
*const_and_copies
,
1757 class avail_exprs_stack
*avail_exprs_stack
)
1759 gimple
*stmt
, *old_stmt
;
1760 bool may_optimize_p
;
1761 bool modified_p
= false;
1765 old_stmt
= stmt
= gsi_stmt (si
);
1766 was_noreturn
= is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
);
1768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1770 fprintf (dump_file
, "Optimizing statement ");
1771 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1774 if (gimple_code (stmt
) == GIMPLE_COND
)
1775 canonicalize_comparison (as_a
<gcond
*> (stmt
));
1777 update_stmt_if_modified (stmt
);
1778 opt_stats
.num_stmts
++;
1780 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1781 cprop_into_stmt (stmt
);
1783 /* If the statement has been modified with constant replacements,
1784 fold its RHS before checking for redundant computations. */
1785 if (gimple_modified_p (stmt
))
1789 /* Try to fold the statement making sure that STMT is kept
1791 if (fold_stmt (&si
))
1793 stmt
= gsi_stmt (si
);
1794 gimple_set_modified (stmt
, true);
1796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1798 fprintf (dump_file
, " Folded to: ");
1799 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1803 /* We only need to consider cases that can yield a gimple operand. */
1804 if (gimple_assign_single_p (stmt
))
1805 rhs
= gimple_assign_rhs1 (stmt
);
1806 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
1807 rhs
= gimple_goto_dest (stmt
);
1808 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1809 /* This should never be an ADDR_EXPR. */
1810 rhs
= gimple_switch_index (swtch_stmt
);
1812 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
1813 recompute_tree_invariant_for_addr_expr (rhs
);
1815 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1816 even if fold_stmt updated the stmt already and thus cleared
1817 gimple_modified_p flag on it. */
1821 /* Check for redundant computations. Do this optimization only
1822 for assignments that have no volatile ops and conditionals. */
1823 may_optimize_p
= (!gimple_has_side_effects (stmt
)
1824 && (is_gimple_assign (stmt
)
1825 || (is_gimple_call (stmt
)
1826 && gimple_call_lhs (stmt
) != NULL_TREE
)
1827 || gimple_code (stmt
) == GIMPLE_COND
1828 || gimple_code (stmt
) == GIMPLE_SWITCH
));
1832 if (gimple_code (stmt
) == GIMPLE_CALL
)
1834 /* Resolve __builtin_constant_p. If it hasn't been
1835 folded to integer_one_node by now, it's fairly
1836 certain that the value simply isn't constant. */
1837 tree callee
= gimple_call_fndecl (stmt
);
1839 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
1840 && DECL_FUNCTION_CODE (callee
) == BUILT_IN_CONSTANT_P
)
1842 propagate_tree_value_into_stmt (&si
, integer_zero_node
);
1843 stmt
= gsi_stmt (si
);
1847 if (gimple_code (stmt
) == GIMPLE_COND
)
1849 tree lhs
= gimple_cond_lhs (stmt
);
1850 tree rhs
= gimple_cond_rhs (stmt
);
1852 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
1853 then this conditional is computable at compile time. We can just
1854 shove either 0 or 1 into the LHS, mark the statement as modified
1855 and all the right things will just happen below.
1857 Note this would apply to any case where LHS has a range
1858 narrower than its type implies and RHS is outside that
1859 narrower range. Future work. */
1860 if (TREE_CODE (lhs
) == SSA_NAME
1861 && ssa_name_has_boolean_range (lhs
)
1862 && TREE_CODE (rhs
) == INTEGER_CST
1863 && ! (integer_zerop (rhs
) || integer_onep (rhs
)))
1865 gimple_cond_set_lhs (as_a
<gcond
*> (stmt
),
1866 fold_convert (TREE_TYPE (lhs
),
1867 integer_zero_node
));
1868 gimple_set_modified (stmt
, true);
1872 update_stmt_if_modified (stmt
);
1873 eliminate_redundant_computations (&si
, const_and_copies
,
1875 stmt
= gsi_stmt (si
);
1877 /* Perform simple redundant store elimination. */
1878 if (gimple_assign_single_p (stmt
)
1879 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
1881 tree lhs
= gimple_assign_lhs (stmt
);
1882 tree rhs
= gimple_assign_rhs1 (stmt
);
1885 rhs
= dom_valueize (rhs
);
1886 /* Build a new statement with the RHS and LHS exchanged. */
1887 if (TREE_CODE (rhs
) == SSA_NAME
)
1889 gimple
*defstmt
= SSA_NAME_DEF_STMT (rhs
);
1890 new_stmt
= gimple_build_assign (rhs
, lhs
);
1891 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
1894 new_stmt
= gimple_build_assign (rhs
, lhs
);
1895 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
1896 cached_lhs
= lookup_avail_expr (new_stmt
, false, avail_exprs_stack
);
1898 && rhs
== cached_lhs
)
1900 basic_block bb
= gimple_bb (stmt
);
1901 unlink_stmt_vdef (stmt
);
1902 if (gsi_remove (&si
, true))
1904 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1905 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1906 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1908 release_defs (stmt
);
1914 /* Record any additional equivalences created by this statement. */
1915 if (is_gimple_assign (stmt
))
1916 record_equivalences_from_stmt (stmt
, may_optimize_p
, avail_exprs_stack
);
1918 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
1919 know where it goes. */
1920 if (gimple_modified_p (stmt
) || modified_p
)
1924 update_stmt_if_modified (stmt
);
1926 if (gimple_code (stmt
) == GIMPLE_COND
)
1927 val
= fold_binary_loc (gimple_location (stmt
),
1928 gimple_cond_code (stmt
), boolean_type_node
,
1929 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
1930 else if (gswitch
*swtch_stmt
= dyn_cast
<gswitch
*> (stmt
))
1931 val
= gimple_switch_index (swtch_stmt
);
1933 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1935 retval
= find_taken_edge (bb
, val
);
1938 /* Fix the condition to be either true or false. */
1939 if (gimple_code (stmt
) == GIMPLE_COND
)
1941 if (integer_zerop (val
))
1942 gimple_cond_make_false (as_a
<gcond
*> (stmt
));
1943 else if (integer_onep (val
))
1944 gimple_cond_make_true (as_a
<gcond
*> (stmt
));
1949 /* Further simplifications may be possible. */
1954 /* If we simplified a statement in such a way as to be shown that it
1955 cannot trap, update the eh information and the cfg to match. */
1956 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1958 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1960 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1964 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
1965 need_noreturn_fixup
.safe_push (stmt
);
1970 /* Helper for walk_non_aliased_vuses. Determine if we arrived at
1971 the desired memory state. */
1974 vuse_eq (ao_ref
*, tree vuse1
, unsigned int cnt
, void *data
)
1976 tree vuse2
= (tree
) data
;
1980 /* This bounds the stmt walks we perform on reference lookups
1981 to O(1) instead of O(N) where N is the number of dominating
1982 stores leading to a candidate. We re-use the SCCVN param
1983 for this as it is basically the same complexity. */
1984 if (cnt
> (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS
))
1990 /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
1991 If found, return its LHS. Otherwise insert STMT in the table and
1994 Also, when an expression is first inserted in the table, it is also
1995 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
1996 we finish processing this block and its children. */
1999 lookup_avail_expr (gimple
*stmt
, bool insert
,
2000 class avail_exprs_stack
*avail_exprs_stack
)
2002 expr_hash_elt
**slot
;
2005 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
2006 if (gimple_code (stmt
) == GIMPLE_PHI
)
2007 lhs
= gimple_phi_result (stmt
);
2009 lhs
= gimple_get_lhs (stmt
);
2011 class expr_hash_elt
element (stmt
, lhs
);
2013 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2015 fprintf (dump_file
, "LKUP ");
2016 element
.print (dump_file
);
2019 /* Don't bother remembering constant assignments and copy operations.
2020 Constants and copy operations are handled by the constant/copy propagator
2021 in optimize_stmt. */
2022 if (element
.expr()->kind
== EXPR_SINGLE
2023 && (TREE_CODE (element
.expr()->ops
.single
.rhs
) == SSA_NAME
2024 || is_gimple_min_invariant (element
.expr()->ops
.single
.rhs
)))
2027 /* Finally try to find the expression in the main expression hash table. */
2028 hash_table
<expr_elt_hasher
> *avail_exprs
= avail_exprs_stack
->avail_exprs ();
2029 slot
= avail_exprs
->find_slot (&element
, (insert
? INSERT
: NO_INSERT
));
2034 else if (*slot
== NULL
)
2036 class expr_hash_elt
*element2
= new expr_hash_elt (element
);
2039 avail_exprs_stack
->record_expr (element2
, NULL
, '2');
2043 /* If we found a redundant memory operation do an alias walk to
2044 check if we can re-use it. */
2045 if (gimple_vuse (stmt
) != (*slot
)->vop ())
2047 tree vuse1
= (*slot
)->vop ();
2048 tree vuse2
= gimple_vuse (stmt
);
2049 /* If we have a load of a register and a candidate in the
2050 hash with vuse1 then try to reach its stmt by walking
2051 up the virtual use-def chain using walk_non_aliased_vuses.
2052 But don't do this when removing expressions from the hash. */
2054 if (!(vuse1
&& vuse2
2055 && gimple_assign_single_p (stmt
)
2056 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
2057 && (ao_ref_init (&ref
, gimple_assign_rhs1 (stmt
)), true)
2058 && walk_non_aliased_vuses (&ref
, vuse2
,
2059 vuse_eq
, NULL
, NULL
, vuse1
) != NULL
))
2063 class expr_hash_elt
*element2
= new expr_hash_elt (element
);
2065 /* Insert the expr into the hash by replacing the current
2066 entry and recording the value to restore in the
2067 avail_exprs_stack. */
2068 avail_exprs_stack
->record_expr (element2
, *slot
, '2');
2075 /* Extract the LHS of the assignment so that it can be used as the current
2076 definition of another variable. */
2077 lhs
= (*slot
)->lhs ();
2079 lhs
= dom_valueize (lhs
);
2081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2083 fprintf (dump_file
, "FIND: ");
2084 print_generic_expr (dump_file
, lhs
, 0);
2085 fprintf (dump_file
, "\n");