2017-06-02 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-ssa-dom.c
blob494b472e121cfcef37019295f5f7a5733f2245cd
1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "tree-pass.h"
28 #include "ssa.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
31 #include "cfganal.h"
32 #include "cfgloop.h"
33 #include "gimple-fold.h"
34 #include "tree-eh.h"
35 #include "gimple-iterator.h"
36 #include "tree-cfg.h"
37 #include "tree-into-ssa.h"
38 #include "domwalk.h"
39 #include "tree-ssa-propagate.h"
40 #include "tree-ssa-threadupdate.h"
41 #include "params.h"
42 #include "tree-ssa-scopedtables.h"
43 #include "tree-ssa-threadedge.h"
44 #include "tree-ssa-dom.h"
45 #include "gimplify.h"
46 #include "tree-cfgcleanup.h"
47 #include "dbgcnt.h"
49 /* This file implements optimizations on the dominator tree. */
51 /* Structure for recording edge equivalences.
53 Computing and storing the edge equivalences instead of creating
54 them on-demand can save significant amounts of time, particularly
55 for pathological cases involving switch statements.
57 These structures live for a single iteration of the dominator
58 optimizer in the edge's AUX field. At the end of an iteration we
59 free each of these structures. */
61 struct edge_info
63 /* If this edge creates a simple equivalence, the LHS and RHS of
64 the equivalence will be stored here. */
65 tree lhs;
66 tree rhs;
68 /* Traversing an edge may also indicate one or more particular conditions
69 are true or false. */
70 vec<cond_equivalence> cond_equivalences;
73 /* Track whether or not we have changed the control flow graph. */
74 static bool cfg_altered;
76 /* Bitmap of blocks that have had EH statements cleaned. We should
77 remove their dead edges eventually. */
78 static bitmap need_eh_cleanup;
79 static vec<gimple *> need_noreturn_fixup;
81 /* Statistics for dominator optimizations. */
82 struct opt_stats_d
84 long num_stmts;
85 long num_exprs_considered;
86 long num_re;
87 long num_const_prop;
88 long num_copy_prop;
91 static struct opt_stats_d opt_stats;
93 /* Local functions. */
94 static edge optimize_stmt (basic_block, gimple_stmt_iterator,
95 class const_and_copies *,
96 class avail_exprs_stack *);
97 static void record_equality (tree, tree, class const_and_copies *);
98 static void record_equivalences_from_phis (basic_block);
99 static void record_equivalences_from_incoming_edge (basic_block,
100 class const_and_copies *,
101 class avail_exprs_stack *);
102 static void eliminate_redundant_computations (gimple_stmt_iterator *,
103 class const_and_copies *,
104 class avail_exprs_stack *);
105 static void record_equivalences_from_stmt (gimple *, int,
106 class avail_exprs_stack *);
107 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
108 static void dump_dominator_optimization_stats (FILE *file,
109 hash_table<expr_elt_hasher> *);
112 /* Free the edge_info data attached to E, if it exists. */
114 void
115 free_dom_edge_info (edge e)
117 struct edge_info *edge_info = (struct edge_info *)e->aux;
119 if (edge_info)
121 edge_info->cond_equivalences.release ();
122 free (edge_info);
126 /* Allocate an EDGE_INFO for edge E and attach it to E.
127 Return the new EDGE_INFO structure. */
129 static struct edge_info *
130 allocate_edge_info (edge e)
132 struct edge_info *edge_info;
134 /* Free the old one, if it exists. */
135 free_dom_edge_info (e);
137 edge_info = XCNEW (struct edge_info);
139 e->aux = edge_info;
140 return edge_info;
143 /* Free all EDGE_INFO structures associated with edges in the CFG.
144 If a particular edge can be threaded, copy the redirection
145 target from the EDGE_INFO structure into the edge's AUX field
146 as required by code to update the CFG and SSA graph for
147 jump threading. */
149 static void
150 free_all_edge_infos (void)
152 basic_block bb;
153 edge_iterator ei;
154 edge e;
156 FOR_EACH_BB_FN (bb, cfun)
158 FOR_EACH_EDGE (e, ei, bb->preds)
160 free_dom_edge_info (e);
161 e->aux = NULL;
166 /* We have finished optimizing BB, record any information implied by
167 taking a specific outgoing edge from BB. */
169 static void
170 record_edge_info (basic_block bb)
172 gimple_stmt_iterator gsi = gsi_last_bb (bb);
173 struct edge_info *edge_info;
175 if (! gsi_end_p (gsi))
177 gimple *stmt = gsi_stmt (gsi);
178 location_t loc = gimple_location (stmt);
180 if (gimple_code (stmt) == GIMPLE_SWITCH)
182 gswitch *switch_stmt = as_a <gswitch *> (stmt);
183 tree index = gimple_switch_index (switch_stmt);
185 if (TREE_CODE (index) == SSA_NAME)
187 int i;
188 int n_labels = gimple_switch_num_labels (switch_stmt);
189 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
190 edge e;
191 edge_iterator ei;
193 for (i = 0; i < n_labels; i++)
195 tree label = gimple_switch_label (switch_stmt, i);
196 basic_block target_bb = label_to_block (CASE_LABEL (label));
197 if (CASE_HIGH (label)
198 || !CASE_LOW (label)
199 || info[target_bb->index])
200 info[target_bb->index] = error_mark_node;
201 else
202 info[target_bb->index] = label;
205 FOR_EACH_EDGE (e, ei, bb->succs)
207 basic_block target_bb = e->dest;
208 tree label = info[target_bb->index];
210 if (label != NULL && label != error_mark_node)
212 tree x = fold_convert_loc (loc, TREE_TYPE (index),
213 CASE_LOW (label));
214 edge_info = allocate_edge_info (e);
215 edge_info->lhs = index;
216 edge_info->rhs = x;
219 free (info);
223 /* A COND_EXPR may create equivalences too. */
224 if (gimple_code (stmt) == GIMPLE_COND)
226 edge true_edge;
227 edge false_edge;
229 tree op0 = gimple_cond_lhs (stmt);
230 tree op1 = gimple_cond_rhs (stmt);
231 enum tree_code code = gimple_cond_code (stmt);
233 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
235 /* Special case comparing booleans against a constant as we
236 know the value of OP0 on both arms of the branch. i.e., we
237 can record an equivalence for OP0 rather than COND.
239 However, don't do this if the constant isn't zero or one.
240 Such conditionals will get optimized more thoroughly during
241 the domwalk. */
242 if ((code == EQ_EXPR || code == NE_EXPR)
243 && TREE_CODE (op0) == SSA_NAME
244 && ssa_name_has_boolean_range (op0)
245 && is_gimple_min_invariant (op1)
246 && (integer_zerop (op1) || integer_onep (op1)))
248 tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
249 tree false_val = constant_boolean_node (false, TREE_TYPE (op0));
251 if (code == EQ_EXPR)
253 edge_info = allocate_edge_info (true_edge);
254 edge_info->lhs = op0;
255 edge_info->rhs = (integer_zerop (op1) ? false_val : true_val);
257 edge_info = allocate_edge_info (false_edge);
258 edge_info->lhs = op0;
259 edge_info->rhs = (integer_zerop (op1) ? true_val : false_val);
261 else
263 edge_info = allocate_edge_info (true_edge);
264 edge_info->lhs = op0;
265 edge_info->rhs = (integer_zerop (op1) ? true_val : false_val);
267 edge_info = allocate_edge_info (false_edge);
268 edge_info->lhs = op0;
269 edge_info->rhs = (integer_zerop (op1) ? false_val : true_val);
272 else if (is_gimple_min_invariant (op0)
273 && (TREE_CODE (op1) == SSA_NAME
274 || is_gimple_min_invariant (op1)))
276 tree cond = build2 (code, boolean_type_node, op0, op1);
277 tree inverted = invert_truthvalue_loc (loc, cond);
278 bool can_infer_simple_equiv
279 = !(HONOR_SIGNED_ZEROS (op0)
280 && real_zerop (op0));
281 struct edge_info *edge_info;
283 edge_info = allocate_edge_info (true_edge);
284 record_conditions (&edge_info->cond_equivalences, cond, inverted);
286 if (can_infer_simple_equiv && code == EQ_EXPR)
288 edge_info->lhs = op1;
289 edge_info->rhs = op0;
292 edge_info = allocate_edge_info (false_edge);
293 record_conditions (&edge_info->cond_equivalences, inverted, cond);
295 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
297 edge_info->lhs = op1;
298 edge_info->rhs = op0;
302 else if (TREE_CODE (op0) == SSA_NAME
303 && (TREE_CODE (op1) == SSA_NAME
304 || is_gimple_min_invariant (op1)))
306 tree cond = build2 (code, boolean_type_node, op0, op1);
307 tree inverted = invert_truthvalue_loc (loc, cond);
308 bool can_infer_simple_equiv
309 = !(HONOR_SIGNED_ZEROS (op1)
310 && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
311 struct edge_info *edge_info;
313 edge_info = allocate_edge_info (true_edge);
314 record_conditions (&edge_info->cond_equivalences, cond, inverted);
316 if (can_infer_simple_equiv && code == EQ_EXPR)
318 edge_info->lhs = op0;
319 edge_info->rhs = op1;
322 edge_info = allocate_edge_info (false_edge);
323 record_conditions (&edge_info->cond_equivalences, inverted, cond);
325 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
327 edge_info->lhs = op0;
328 edge_info->rhs = op1;
333 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
338 class dom_opt_dom_walker : public dom_walker
340 public:
341 dom_opt_dom_walker (cdi_direction direction,
342 class const_and_copies *const_and_copies,
343 class avail_exprs_stack *avail_exprs_stack)
344 : dom_walker (direction, true),
345 m_const_and_copies (const_and_copies),
346 m_avail_exprs_stack (avail_exprs_stack),
347 m_dummy_cond (NULL) {}
349 virtual edge before_dom_children (basic_block);
350 virtual void after_dom_children (basic_block);
352 private:
354 /* Unwindable equivalences, both const/copy and expression varieties. */
355 class const_and_copies *m_const_and_copies;
356 class avail_exprs_stack *m_avail_exprs_stack;
358 gcond *m_dummy_cond;
361 /* Jump threading, redundancy elimination and const/copy propagation.
363 This pass may expose new symbols that need to be renamed into SSA. For
364 every new symbol exposed, its corresponding bit will be set in
365 VARS_TO_RENAME. */
367 namespace {
369 const pass_data pass_data_dominator =
371 GIMPLE_PASS, /* type */
372 "dom", /* name */
373 OPTGROUP_NONE, /* optinfo_flags */
374 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
375 ( PROP_cfg | PROP_ssa ), /* properties_required */
376 0, /* properties_provided */
377 0, /* properties_destroyed */
378 0, /* todo_flags_start */
379 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
382 class pass_dominator : public gimple_opt_pass
384 public:
385 pass_dominator (gcc::context *ctxt)
386 : gimple_opt_pass (pass_data_dominator, ctxt),
387 may_peel_loop_headers_p (false)
390 /* opt_pass methods: */
391 opt_pass * clone () { return new pass_dominator (m_ctxt); }
392 void set_pass_param (unsigned int n, bool param)
394 gcc_assert (n == 0);
395 may_peel_loop_headers_p = param;
397 virtual bool gate (function *) { return flag_tree_dom != 0; }
398 virtual unsigned int execute (function *);
400 private:
401 /* This flag is used to prevent loops from being peeled repeatedly in jump
402 threading; it will be removed once we preserve loop structures throughout
403 the compilation -- we will be able to mark the affected loops directly in
404 jump threading, and avoid peeling them next time. */
405 bool may_peel_loop_headers_p;
406 }; // class pass_dominator
408 unsigned int
409 pass_dominator::execute (function *fun)
411 memset (&opt_stats, 0, sizeof (opt_stats));
413 /* Create our hash tables. */
414 hash_table<expr_elt_hasher> *avail_exprs
415 = new hash_table<expr_elt_hasher> (1024);
416 class avail_exprs_stack *avail_exprs_stack
417 = new class avail_exprs_stack (avail_exprs);
418 class const_and_copies *const_and_copies = new class const_and_copies ();
419 need_eh_cleanup = BITMAP_ALLOC (NULL);
420 need_noreturn_fixup.create (0);
422 calculate_dominance_info (CDI_DOMINATORS);
423 cfg_altered = false;
425 /* We need to know loop structures in order to avoid destroying them
426 in jump threading. Note that we still can e.g. thread through loop
427 headers to an exit edge, or through loop header to the loop body, assuming
428 that we update the loop info.
430 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
431 to several overly conservative bail-outs in jump threading, case
432 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
433 missing. We should improve jump threading in future then
434 LOOPS_HAVE_PREHEADERS won't be needed here. */
435 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
437 /* Initialize the value-handle array. */
438 threadedge_initialize_values ();
440 /* We need accurate information regarding back edges in the CFG
441 for jump threading; this may include back edges that are not part of
442 a single loop. */
443 mark_dfs_back_edges ();
445 /* We want to create the edge info structures before the dominator walk
446 so that they'll be in place for the jump threader, particularly when
447 threading through a join block.
449 The conditions will be lazily updated with global equivalences as
450 we reach them during the dominator walk. */
451 basic_block bb;
452 FOR_EACH_BB_FN (bb, fun)
453 record_edge_info (bb);
455 /* Recursively walk the dominator tree optimizing statements. */
456 dom_opt_dom_walker walker (CDI_DOMINATORS,
457 const_and_copies,
458 avail_exprs_stack);
459 walker.walk (fun->cfg->x_entry_block_ptr);
461 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
462 edge. When found, remove jump threads which contain any outgoing
463 edge from the affected block. */
464 if (cfg_altered)
466 FOR_EACH_BB_FN (bb, fun)
468 edge_iterator ei;
469 edge e;
471 /* First see if there are any edges without EDGE_EXECUTABLE
472 set. */
473 bool found = false;
474 FOR_EACH_EDGE (e, ei, bb->succs)
476 if ((e->flags & EDGE_EXECUTABLE) == 0)
478 found = true;
479 break;
483 /* If there were any such edges found, then remove jump threads
484 containing any edge leaving BB. */
485 if (found)
486 FOR_EACH_EDGE (e, ei, bb->succs)
487 remove_jump_threads_including (e);
492 gimple_stmt_iterator gsi;
493 basic_block bb;
494 FOR_EACH_BB_FN (bb, fun)
496 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
497 update_stmt_if_modified (gsi_stmt (gsi));
501 /* If we exposed any new variables, go ahead and put them into
502 SSA form now, before we handle jump threading. This simplifies
503 interactions between rewriting of _DECL nodes into SSA form
504 and rewriting SSA_NAME nodes into SSA form after block
505 duplication and CFG manipulation. */
506 update_ssa (TODO_update_ssa);
508 free_all_edge_infos ();
510 /* Thread jumps, creating duplicate blocks as needed. */
511 cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p);
513 if (cfg_altered)
514 free_dominance_info (CDI_DOMINATORS);
516 /* Removal of statements may make some EH edges dead. Purge
517 such edges from the CFG as needed. */
518 if (!bitmap_empty_p (need_eh_cleanup))
520 unsigned i;
521 bitmap_iterator bi;
523 /* Jump threading may have created forwarder blocks from blocks
524 needing EH cleanup; the new successor of these blocks, which
525 has inherited from the original block, needs the cleanup.
526 Don't clear bits in the bitmap, as that can break the bitmap
527 iterator. */
528 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
530 basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
531 if (bb == NULL)
532 continue;
533 while (single_succ_p (bb)
534 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
535 bb = single_succ (bb);
536 if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
537 continue;
538 if ((unsigned) bb->index != i)
539 bitmap_set_bit (need_eh_cleanup, bb->index);
542 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
543 bitmap_clear (need_eh_cleanup);
546 /* Fixup stmts that became noreturn calls. This may require splitting
547 blocks and thus isn't possible during the dominator walk or before
548 jump threading finished. Do this in reverse order so we don't
549 inadvertedly remove a stmt we want to fixup by visiting a dominating
550 now noreturn call first. */
551 while (!need_noreturn_fixup.is_empty ())
553 gimple *stmt = need_noreturn_fixup.pop ();
554 if (dump_file && dump_flags & TDF_DETAILS)
556 fprintf (dump_file, "Fixing up noreturn call ");
557 print_gimple_stmt (dump_file, stmt, 0);
558 fprintf (dump_file, "\n");
560 fixup_noreturn_call (stmt);
563 statistics_counter_event (fun, "Redundant expressions eliminated",
564 opt_stats.num_re);
565 statistics_counter_event (fun, "Constants propagated",
566 opt_stats.num_const_prop);
567 statistics_counter_event (fun, "Copies propagated",
568 opt_stats.num_copy_prop);
570 /* Debugging dumps. */
571 if (dump_file && (dump_flags & TDF_STATS))
572 dump_dominator_optimization_stats (dump_file, avail_exprs);
574 loop_optimizer_finalize ();
576 /* Delete our main hashtable. */
577 delete avail_exprs;
578 avail_exprs = NULL;
580 /* Free asserted bitmaps and stacks. */
581 BITMAP_FREE (need_eh_cleanup);
582 need_noreturn_fixup.release ();
583 delete avail_exprs_stack;
584 delete const_and_copies;
586 /* Free the value-handle array. */
587 threadedge_finalize_values ();
589 return 0;
592 } // anon namespace
594 gimple_opt_pass *
595 make_pass_dominator (gcc::context *ctxt)
597 return new pass_dominator (ctxt);
601 /* A trivial wrapper so that we can present the generic jump
602 threading code with a simple API for simplifying statements. */
603 static tree
604 simplify_stmt_for_jump_threading (gimple *stmt,
605 gimple *within_stmt ATTRIBUTE_UNUSED,
606 class avail_exprs_stack *avail_exprs_stack,
607 basic_block bb ATTRIBUTE_UNUSED)
609 return avail_exprs_stack->lookup_avail_expr (stmt, false, true);
612 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
614 static tree
615 dom_valueize (tree t)
617 if (TREE_CODE (t) == SSA_NAME)
619 tree tem = SSA_NAME_VALUE (t);
620 if (tem)
621 return tem;
623 return t;
626 /* We have just found an equivalence for LHS on an edge E.
627 Look backwards to other uses of LHS and see if we can derive
628 additional equivalences that are valid on edge E. */
629 static void
630 back_propagate_equivalences (tree lhs, edge e,
631 class const_and_copies *const_and_copies)
633 use_operand_p use_p;
634 imm_use_iterator iter;
635 bitmap domby = NULL;
636 basic_block dest = e->dest;
638 /* Iterate over the uses of LHS to see if any dominate E->dest.
639 If so, they may create useful equivalences too.
641 ??? If the code gets re-organized to a worklist to catch more
642 indirect opportunities and it is made to handle PHIs then this
643 should only consider use_stmts in basic-blocks we have already visited. */
644 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
646 gimple *use_stmt = USE_STMT (use_p);
648 /* Often the use is in DEST, which we trivially know we can't use.
649 This is cheaper than the dominator set tests below. */
650 if (dest == gimple_bb (use_stmt))
651 continue;
653 /* Filter out statements that can never produce a useful
654 equivalence. */
655 tree lhs2 = gimple_get_lhs (use_stmt);
656 if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME)
657 continue;
659 /* Profiling has shown the domination tests here can be fairly
660 expensive. We get significant improvements by building the
661 set of blocks that dominate BB. We can then just test
662 for set membership below.
664 We also initialize the set lazily since often the only uses
665 are going to be in the same block as DEST. */
666 if (!domby)
668 domby = BITMAP_ALLOC (NULL);
669 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest);
670 while (bb)
672 bitmap_set_bit (domby, bb->index);
673 bb = get_immediate_dominator (CDI_DOMINATORS, bb);
677 /* This tests if USE_STMT does not dominate DEST. */
678 if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index))
679 continue;
681 /* At this point USE_STMT dominates DEST and may result in a
682 useful equivalence. Try to simplify its RHS to a constant
683 or SSA_NAME. */
684 tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize,
685 no_follow_ssa_edges);
686 if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res)))
687 record_equality (lhs2, res, const_and_copies);
690 if (domby)
691 BITMAP_FREE (domby);
694 /* Record NAME has the value zero and if NAME was set from a BIT_IOR_EXPR
695 recurse into both operands recording their values as zero too.
696 RECURSION_DEPTH controls how far back we recurse through the operands
697 of the BIT_IOR_EXPR. */
699 static void
700 derive_equivalences_from_bit_ior (tree name,
701 const_and_copies *const_and_copies,
702 int recursion_limit)
704 if (recursion_limit == 0)
705 return;
707 if (TREE_CODE (name) == SSA_NAME)
709 tree value = build_zero_cst (TREE_TYPE (name));
711 /* This records the equivalence for the toplevel object. */
712 record_equality (name, value, const_and_copies);
714 /* And we can recurse into each operand to potentially find more
715 equivalences. */
716 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
717 if (is_gimple_assign (def_stmt)
718 && gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
720 derive_equivalences_from_bit_ior (gimple_assign_rhs1 (def_stmt),
721 const_and_copies,
722 recursion_limit - 1);
723 derive_equivalences_from_bit_ior (gimple_assign_rhs2 (def_stmt),
724 const_and_copies,
725 recursion_limit - 1);
730 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
731 by traversing edge E (which are cached in E->aux).
733 Callers are responsible for managing the unwinding markers. */
734 void
735 record_temporary_equivalences (edge e,
736 class const_and_copies *const_and_copies,
737 class avail_exprs_stack *avail_exprs_stack)
739 int i;
740 struct edge_info *edge_info = (struct edge_info *) e->aux;
742 /* If we have info associated with this edge, record it into
743 our equivalence tables. */
744 if (edge_info)
746 cond_equivalence *eq;
747 /* If we have 0 = COND or 1 = COND equivalences, record them
748 into our expression hash tables. */
749 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
751 avail_exprs_stack->record_cond (eq);
753 /* If the condition is testing that X == 0 is true or X != 0 is false
754 and X is set from a BIT_IOR_EXPR, then we can record equivalences
755 for the operands of the BIT_IOR_EXPR (and recurse on those). */
756 tree op0 = eq->cond.ops.binary.opnd0;
757 tree op1 = eq->cond.ops.binary.opnd1;
758 if (TREE_CODE (op0) == SSA_NAME && integer_zerop (op1))
760 enum tree_code code = eq->cond.ops.binary.op;
761 if ((code == EQ_EXPR && eq->value == boolean_true_node)
762 || (code == NE_EXPR && eq->value == boolean_false_node))
763 derive_equivalences_from_bit_ior (op0, const_and_copies, 4);
765 /* TODO: We could handle BIT_AND_EXPR in a similar fashion
766 recording that the operands have a nonzero value. */
768 /* TODO: We can handle more cases here, particularly when OP0 is
769 known to have a boolean range. */
773 tree lhs = edge_info->lhs;
774 if (!lhs || TREE_CODE (lhs) != SSA_NAME)
775 return;
777 /* Record the simple NAME = VALUE equivalence. */
778 tree rhs = edge_info->rhs;
779 record_equality (lhs, rhs, const_and_copies);
781 /* We already recorded that LHS = RHS, with canonicalization,
782 value chain following, etc.
784 We also want to record RHS = LHS, but without any canonicalization
785 or value chain following. */
786 if (TREE_CODE (rhs) == SSA_NAME)
787 const_and_copies->record_const_or_copy_raw (rhs, lhs,
788 SSA_NAME_VALUE (rhs));
790 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
791 set via a widening type conversion, then we may be able to record
792 additional equivalences. */
793 if (TREE_CODE (rhs) == INTEGER_CST)
795 gimple *defstmt = SSA_NAME_DEF_STMT (lhs);
797 if (defstmt
798 && is_gimple_assign (defstmt)
799 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt)))
801 tree old_rhs = gimple_assign_rhs1 (defstmt);
803 /* If the conversion widens the original value and
804 the constant is in the range of the type of OLD_RHS,
805 then convert the constant and record the equivalence.
807 Note that int_fits_type_p does not check the precision
808 if the upper and lower bounds are OK. */
809 if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs))
810 && (TYPE_PRECISION (TREE_TYPE (lhs))
811 > TYPE_PRECISION (TREE_TYPE (old_rhs)))
812 && int_fits_type_p (rhs, TREE_TYPE (old_rhs)))
814 tree newval = fold_convert (TREE_TYPE (old_rhs), rhs);
815 record_equality (old_rhs, newval, const_and_copies);
820 /* Any equivalence found for LHS may result in additional
821 equivalences for other uses of LHS that we have already
822 processed. */
823 back_propagate_equivalences (lhs, e, const_and_copies);
827 /* PHI nodes can create equivalences too.
829 Ignoring any alternatives which are the same as the result, if
830 all the alternatives are equal, then the PHI node creates an
831 equivalence. */
833 static void
834 record_equivalences_from_phis (basic_block bb)
836 gphi_iterator gsi;
838 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
840 gphi *phi = gsi.phi ();
842 tree lhs = gimple_phi_result (phi);
843 tree rhs = NULL;
844 size_t i;
846 for (i = 0; i < gimple_phi_num_args (phi); i++)
848 tree t = gimple_phi_arg_def (phi, i);
850 /* Ignore alternatives which are the same as our LHS. Since
851 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
852 can simply compare pointers. */
853 if (lhs == t)
854 continue;
856 /* If the associated edge is not marked as executable, then it
857 can be ignored. */
858 if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0)
859 continue;
861 t = dom_valueize (t);
863 /* If we have not processed an alternative yet, then set
864 RHS to this alternative. */
865 if (rhs == NULL)
866 rhs = t;
867 /* If we have processed an alternative (stored in RHS), then
868 see if it is equal to this one. If it isn't, then stop
869 the search. */
870 else if (! operand_equal_for_phi_arg_p (rhs, t))
871 break;
874 /* If we had no interesting alternatives, then all the RHS alternatives
875 must have been the same as LHS. */
876 if (!rhs)
877 rhs = lhs;
879 /* If we managed to iterate through each PHI alternative without
880 breaking out of the loop, then we have a PHI which may create
881 a useful equivalence. We do not need to record unwind data for
882 this, since this is a true assignment and not an equivalence
883 inferred from a comparison. All uses of this ssa name are dominated
884 by this assignment, so unwinding just costs time and space. */
885 if (i == gimple_phi_num_args (phi)
886 && may_propagate_copy (lhs, rhs))
887 set_ssa_name_value (lhs, rhs);
891 /* Ignoring loop backedges, if BB has precisely one incoming edge then
892 return that edge. Otherwise return NULL. */
893 static edge
894 single_incoming_edge_ignoring_loop_edges (basic_block bb)
896 edge retval = NULL;
897 edge e;
898 edge_iterator ei;
900 FOR_EACH_EDGE (e, ei, bb->preds)
902 /* A loop back edge can be identified by the destination of
903 the edge dominating the source of the edge. */
904 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
905 continue;
907 /* We can safely ignore edges that are not executable. */
908 if ((e->flags & EDGE_EXECUTABLE) == 0)
909 continue;
911 /* If we have already seen a non-loop edge, then we must have
912 multiple incoming non-loop edges and thus we return NULL. */
913 if (retval)
914 return NULL;
916 /* This is the first non-loop incoming edge we have found. Record
917 it. */
918 retval = e;
921 return retval;
924 /* Record any equivalences created by the incoming edge to BB into
925 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
926 incoming edge, then no equivalence is created. */
928 static void
929 record_equivalences_from_incoming_edge (basic_block bb,
930 class const_and_copies *const_and_copies,
931 class avail_exprs_stack *avail_exprs_stack)
933 edge e;
934 basic_block parent;
936 /* If our parent block ended with a control statement, then we may be
937 able to record some equivalences based on which outgoing edge from
938 the parent was followed. */
939 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
941 e = single_incoming_edge_ignoring_loop_edges (bb);
943 /* If we had a single incoming edge from our parent block, then enter
944 any data associated with the edge into our tables. */
945 if (e && e->src == parent)
946 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
949 /* Dump statistics for the hash table HTAB. */
951 static void
952 htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab)
954 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
955 (long) htab.size (),
956 (long) htab.elements (),
957 htab.collisions ());
960 /* Dump SSA statistics on FILE. */
962 static void
963 dump_dominator_optimization_stats (FILE *file,
964 hash_table<expr_elt_hasher> *avail_exprs)
966 fprintf (file, "Total number of statements: %6ld\n\n",
967 opt_stats.num_stmts);
968 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
969 opt_stats.num_exprs_considered);
971 fprintf (file, "\nHash table statistics:\n");
973 fprintf (file, " avail_exprs: ");
974 htab_statistics (file, *avail_exprs);
978 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
979 This constrains the cases in which we may treat this as assignment. */
981 static void
982 record_equality (tree x, tree y, class const_and_copies *const_and_copies)
984 tree prev_x = NULL, prev_y = NULL;
986 if (tree_swap_operands_p (x, y))
987 std::swap (x, y);
989 /* Most of the time tree_swap_operands_p does what we want. But there
990 are cases where we know one operand is better for copy propagation than
991 the other. Given no other code cares about ordering of equality
992 comparison operators for that purpose, we just handle the special cases
993 here. */
994 if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME)
996 /* If one operand is a single use operand, then make it
997 X. This will preserve its single use properly and if this
998 conditional is eliminated, the computation of X can be
999 eliminated as well. */
1000 if (has_single_use (y) && ! has_single_use (x))
1001 std::swap (x, y);
1003 if (TREE_CODE (x) == SSA_NAME)
1004 prev_x = SSA_NAME_VALUE (x);
1005 if (TREE_CODE (y) == SSA_NAME)
1006 prev_y = SSA_NAME_VALUE (y);
1008 /* If one of the previous values is invariant, or invariant in more loops
1009 (by depth), then use that.
1010 Otherwise it doesn't matter which value we choose, just so
1011 long as we canonicalize on one value. */
1012 if (is_gimple_min_invariant (y))
1014 else if (is_gimple_min_invariant (x))
1015 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1016 else if (prev_x && is_gimple_min_invariant (prev_x))
1017 x = y, y = prev_x, prev_x = prev_y;
1018 else if (prev_y)
1019 y = prev_y;
1021 /* After the swapping, we must have one SSA_NAME. */
1022 if (TREE_CODE (x) != SSA_NAME)
1023 return;
1025 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1026 variable compared against zero. If we're honoring signed zeros,
1027 then we cannot record this value unless we know that the value is
1028 nonzero. */
1029 if (HONOR_SIGNED_ZEROS (x)
1030 && (TREE_CODE (y) != REAL_CST
1031 || real_equal (&dconst0, &TREE_REAL_CST (y))))
1032 return;
1034 const_and_copies->record_const_or_copy (x, y, prev_x);
1037 /* Returns true when STMT is a simple iv increment. It detects the
1038 following situation:
1040 i_1 = phi (..., i_2)
1041 i_2 = i_1 +/- ... */
1043 bool
1044 simple_iv_increment_p (gimple *stmt)
1046 enum tree_code code;
1047 tree lhs, preinc;
1048 gimple *phi;
1049 size_t i;
1051 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1052 return false;
1054 lhs = gimple_assign_lhs (stmt);
1055 if (TREE_CODE (lhs) != SSA_NAME)
1056 return false;
1058 code = gimple_assign_rhs_code (stmt);
1059 if (code != PLUS_EXPR
1060 && code != MINUS_EXPR
1061 && code != POINTER_PLUS_EXPR)
1062 return false;
1064 preinc = gimple_assign_rhs1 (stmt);
1065 if (TREE_CODE (preinc) != SSA_NAME)
1066 return false;
1068 phi = SSA_NAME_DEF_STMT (preinc);
1069 if (gimple_code (phi) != GIMPLE_PHI)
1070 return false;
1072 for (i = 0; i < gimple_phi_num_args (phi); i++)
1073 if (gimple_phi_arg_def (phi, i) == lhs)
1074 return true;
1076 return false;
1079 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1080 successors of BB. */
1082 static void
1083 cprop_into_successor_phis (basic_block bb,
1084 class const_and_copies *const_and_copies)
1086 edge e;
1087 edge_iterator ei;
1089 FOR_EACH_EDGE (e, ei, bb->succs)
1091 int indx;
1092 gphi_iterator gsi;
1094 /* If this is an abnormal edge, then we do not want to copy propagate
1095 into the PHI alternative associated with this edge. */
1096 if (e->flags & EDGE_ABNORMAL)
1097 continue;
1099 gsi = gsi_start_phis (e->dest);
1100 if (gsi_end_p (gsi))
1101 continue;
1103 /* We may have an equivalence associated with this edge. While
1104 we can not propagate it into non-dominated blocks, we can
1105 propagate them into PHIs in non-dominated blocks. */
1107 /* Push the unwind marker so we can reset the const and copies
1108 table back to its original state after processing this edge. */
1109 const_and_copies->push_marker ();
1111 /* Extract and record any simple NAME = VALUE equivalences.
1113 Don't bother with [01] = COND equivalences, they're not useful
1114 here. */
1115 struct edge_info *edge_info = (struct edge_info *) e->aux;
1116 if (edge_info)
1118 tree lhs = edge_info->lhs;
1119 tree rhs = edge_info->rhs;
1121 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1122 const_and_copies->record_const_or_copy (lhs, rhs);
1125 indx = e->dest_idx;
1126 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1128 tree new_val;
1129 use_operand_p orig_p;
1130 tree orig_val;
1131 gphi *phi = gsi.phi ();
1133 /* The alternative may be associated with a constant, so verify
1134 it is an SSA_NAME before doing anything with it. */
1135 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1136 orig_val = get_use_from_ptr (orig_p);
1137 if (TREE_CODE (orig_val) != SSA_NAME)
1138 continue;
1140 /* If we have *ORIG_P in our constant/copy table, then replace
1141 ORIG_P with its value in our constant/copy table. */
1142 new_val = SSA_NAME_VALUE (orig_val);
1143 if (new_val
1144 && new_val != orig_val
1145 && may_propagate_copy (orig_val, new_val))
1146 propagate_value (orig_p, new_val);
1149 const_and_copies->pop_to_marker ();
1153 edge
1154 dom_opt_dom_walker::before_dom_children (basic_block bb)
1156 gimple_stmt_iterator gsi;
1158 if (dump_file && (dump_flags & TDF_DETAILS))
1159 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
1161 /* Push a marker on the stacks of local information so that we know how
1162 far to unwind when we finalize this block. */
1163 m_avail_exprs_stack->push_marker ();
1164 m_const_and_copies->push_marker ();
1166 record_equivalences_from_incoming_edge (bb, m_const_and_copies,
1167 m_avail_exprs_stack);
1169 /* PHI nodes can create equivalences too. */
1170 record_equivalences_from_phis (bb);
1172 /* Create equivalences from redundant PHIs. PHIs are only truly
1173 redundant when they exist in the same block, so push another
1174 marker and unwind right afterwards. */
1175 m_avail_exprs_stack->push_marker ();
1176 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1177 eliminate_redundant_computations (&gsi, m_const_and_copies,
1178 m_avail_exprs_stack);
1179 m_avail_exprs_stack->pop_to_marker ();
1181 edge taken_edge = NULL;
1182 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1183 taken_edge
1184 = optimize_stmt (bb, gsi, m_const_and_copies, m_avail_exprs_stack);
1186 /* Now prepare to process dominated blocks. */
1187 record_edge_info (bb);
1188 cprop_into_successor_phis (bb, m_const_and_copies);
1189 if (taken_edge && !dbg_cnt (dom_unreachable_edges))
1190 return NULL;
1192 return taken_edge;
1195 /* We have finished processing the dominator children of BB, perform
1196 any finalization actions in preparation for leaving this node in
1197 the dominator tree. */
1199 void
1200 dom_opt_dom_walker::after_dom_children (basic_block bb)
1202 if (! m_dummy_cond)
1203 m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
1204 integer_zero_node, NULL, NULL);
1206 thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
1207 m_avail_exprs_stack,
1208 simplify_stmt_for_jump_threading);
1210 /* These remove expressions local to BB from the tables. */
1211 m_avail_exprs_stack->pop_to_marker ();
1212 m_const_and_copies->pop_to_marker ();
1215 /* Search for redundant computations in STMT. If any are found, then
1216 replace them with the variable holding the result of the computation.
1218 If safe, record this expression into AVAIL_EXPRS_STACK and
1219 CONST_AND_COPIES. */
1221 static void
1222 eliminate_redundant_computations (gimple_stmt_iterator* gsi,
1223 class const_and_copies *const_and_copies,
1224 class avail_exprs_stack *avail_exprs_stack)
1226 tree expr_type;
1227 tree cached_lhs;
1228 tree def;
1229 bool insert = true;
1230 bool assigns_var_p = false;
1232 gimple *stmt = gsi_stmt (*gsi);
1234 if (gimple_code (stmt) == GIMPLE_PHI)
1235 def = gimple_phi_result (stmt);
1236 else
1237 def = gimple_get_lhs (stmt);
1239 /* Certain expressions on the RHS can be optimized away, but can not
1240 themselves be entered into the hash tables. */
1241 if (! def
1242 || TREE_CODE (def) != SSA_NAME
1243 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1244 || gimple_vdef (stmt)
1245 /* Do not record equivalences for increments of ivs. This would create
1246 overlapping live ranges for a very questionable gain. */
1247 || simple_iv_increment_p (stmt))
1248 insert = false;
1250 /* Check if the expression has been computed before. */
1251 cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, insert, true);
1253 opt_stats.num_exprs_considered++;
1255 /* Get the type of the expression we are trying to optimize. */
1256 if (is_gimple_assign (stmt))
1258 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1259 assigns_var_p = true;
1261 else if (gimple_code (stmt) == GIMPLE_COND)
1262 expr_type = boolean_type_node;
1263 else if (is_gimple_call (stmt))
1265 gcc_assert (gimple_call_lhs (stmt));
1266 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1267 assigns_var_p = true;
1269 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1270 expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt));
1271 else if (gimple_code (stmt) == GIMPLE_PHI)
1272 /* We can't propagate into a phi, so the logic below doesn't apply.
1273 Instead record an equivalence between the cached LHS and the
1274 PHI result of this statement, provided they are in the same block.
1275 This should be sufficient to kill the redundant phi. */
1277 if (def && cached_lhs)
1278 const_and_copies->record_const_or_copy (def, cached_lhs);
1279 return;
1281 else
1282 gcc_unreachable ();
1284 if (!cached_lhs)
1285 return;
1287 /* It is safe to ignore types here since we have already done
1288 type checking in the hashing and equality routines. In fact
1289 type checking here merely gets in the way of constant
1290 propagation. Also, make sure that it is safe to propagate
1291 CACHED_LHS into the expression in STMT. */
1292 if ((TREE_CODE (cached_lhs) != SSA_NAME
1293 && (assigns_var_p
1294 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1295 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1297 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
1298 || is_gimple_min_invariant (cached_lhs));
1300 if (dump_file && (dump_flags & TDF_DETAILS))
1302 fprintf (dump_file, " Replaced redundant expr '");
1303 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1304 fprintf (dump_file, "' with '");
1305 print_generic_expr (dump_file, cached_lhs, dump_flags);
1306 fprintf (dump_file, "'\n");
1309 opt_stats.num_re++;
1311 if (assigns_var_p
1312 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1313 cached_lhs = fold_convert (expr_type, cached_lhs);
1315 propagate_tree_value_into_stmt (gsi, cached_lhs);
1317 /* Since it is always necessary to mark the result as modified,
1318 perhaps we should move this into propagate_tree_value_into_stmt
1319 itself. */
1320 gimple_set_modified (gsi_stmt (*gsi), true);
1324 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1325 the available expressions table or the const_and_copies table.
1326 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1328 We handle only very simple copy equivalences here. The heavy
1329 lifing is done by eliminate_redundant_computations. */
1331 static void
1332 record_equivalences_from_stmt (gimple *stmt, int may_optimize_p,
1333 class avail_exprs_stack *avail_exprs_stack)
1335 tree lhs;
1336 enum tree_code lhs_code;
1338 gcc_assert (is_gimple_assign (stmt));
1340 lhs = gimple_assign_lhs (stmt);
1341 lhs_code = TREE_CODE (lhs);
1343 if (lhs_code == SSA_NAME
1344 && gimple_assign_single_p (stmt))
1346 tree rhs = gimple_assign_rhs1 (stmt);
1348 /* If the RHS of the assignment is a constant or another variable that
1349 may be propagated, register it in the CONST_AND_COPIES table. We
1350 do not need to record unwind data for this, since this is a true
1351 assignment and not an equivalence inferred from a comparison. All
1352 uses of this ssa name are dominated by this assignment, so unwinding
1353 just costs time and space. */
1354 if (may_optimize_p
1355 && (TREE_CODE (rhs) == SSA_NAME
1356 || is_gimple_min_invariant (rhs)))
1358 rhs = dom_valueize (rhs);
1360 if (dump_file && (dump_flags & TDF_DETAILS))
1362 fprintf (dump_file, "==== ASGN ");
1363 print_generic_expr (dump_file, lhs);
1364 fprintf (dump_file, " = ");
1365 print_generic_expr (dump_file, rhs);
1366 fprintf (dump_file, "\n");
1369 set_ssa_name_value (lhs, rhs);
1373 /* Make sure we can propagate &x + CST. */
1374 if (lhs_code == SSA_NAME
1375 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
1376 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR
1377 && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
1379 tree op0 = gimple_assign_rhs1 (stmt);
1380 tree op1 = gimple_assign_rhs2 (stmt);
1381 tree new_rhs
1382 = build_fold_addr_expr (fold_build2 (MEM_REF,
1383 TREE_TYPE (TREE_TYPE (op0)),
1384 unshare_expr (op0),
1385 fold_convert (ptr_type_node,
1386 op1)));
1387 if (dump_file && (dump_flags & TDF_DETAILS))
1389 fprintf (dump_file, "==== ASGN ");
1390 print_generic_expr (dump_file, lhs);
1391 fprintf (dump_file, " = ");
1392 print_generic_expr (dump_file, new_rhs);
1393 fprintf (dump_file, "\n");
1396 set_ssa_name_value (lhs, new_rhs);
1399 /* A memory store, even an aliased store, creates a useful
1400 equivalence. By exchanging the LHS and RHS, creating suitable
1401 vops and recording the result in the available expression table,
1402 we may be able to expose more redundant loads. */
1403 if (!gimple_has_volatile_ops (stmt)
1404 && gimple_references_memory_p (stmt)
1405 && gimple_assign_single_p (stmt)
1406 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1407 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1408 && !is_gimple_reg (lhs))
1410 tree rhs = gimple_assign_rhs1 (stmt);
1411 gassign *new_stmt;
1413 /* Build a new statement with the RHS and LHS exchanged. */
1414 if (TREE_CODE (rhs) == SSA_NAME)
1416 /* NOTE tuples. The call to gimple_build_assign below replaced
1417 a call to build_gimple_modify_stmt, which did not set the
1418 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1419 may cause an SSA validation failure, as the LHS may be a
1420 default-initialized name and should have no definition. I'm
1421 a bit dubious of this, as the artificial statement that we
1422 generate here may in fact be ill-formed, but it is simply
1423 used as an internal device in this pass, and never becomes
1424 part of the CFG. */
1425 gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
1426 new_stmt = gimple_build_assign (rhs, lhs);
1427 SSA_NAME_DEF_STMT (rhs) = defstmt;
1429 else
1430 new_stmt = gimple_build_assign (rhs, lhs);
1432 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1434 /* Finally enter the statement into the available expression
1435 table. */
1436 avail_exprs_stack->lookup_avail_expr (new_stmt, true, true);
1440 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1441 CONST_AND_COPIES. */
1443 static void
1444 cprop_operand (gimple *stmt, use_operand_p op_p)
1446 tree val;
1447 tree op = USE_FROM_PTR (op_p);
1449 /* If the operand has a known constant value or it is known to be a
1450 copy of some other variable, use the value or copy stored in
1451 CONST_AND_COPIES. */
1452 val = SSA_NAME_VALUE (op);
1453 if (val && val != op)
1455 /* Do not replace hard register operands in asm statements. */
1456 if (gimple_code (stmt) == GIMPLE_ASM
1457 && !may_propagate_copy_into_asm (op))
1458 return;
1460 /* Certain operands are not allowed to be copy propagated due
1461 to their interaction with exception handling and some GCC
1462 extensions. */
1463 if (!may_propagate_copy (op, val))
1464 return;
1466 /* Do not propagate copies into BIVs.
1467 See PR23821 and PR62217 for how this can disturb IV and
1468 number of iteration analysis. */
1469 if (TREE_CODE (val) != INTEGER_CST)
1471 gimple *def = SSA_NAME_DEF_STMT (op);
1472 if (gimple_code (def) == GIMPLE_PHI
1473 && gimple_bb (def)->loop_father->header == gimple_bb (def))
1474 return;
1477 /* Dump details. */
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1480 fprintf (dump_file, " Replaced '");
1481 print_generic_expr (dump_file, op, dump_flags);
1482 fprintf (dump_file, "' with %s '",
1483 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
1484 print_generic_expr (dump_file, val, dump_flags);
1485 fprintf (dump_file, "'\n");
1488 if (TREE_CODE (val) != SSA_NAME)
1489 opt_stats.num_const_prop++;
1490 else
1491 opt_stats.num_copy_prop++;
1493 propagate_value (op_p, val);
1495 /* And note that we modified this statement. This is now
1496 safe, even if we changed virtual operands since we will
1497 rescan the statement and rewrite its operands again. */
1498 gimple_set_modified (stmt, true);
1502 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1503 known value for that SSA_NAME (or NULL if no value is known).
1505 Propagate values from CONST_AND_COPIES into the uses, vuses and
1506 vdef_ops of STMT. */
1508 static void
1509 cprop_into_stmt (gimple *stmt)
1511 use_operand_p op_p;
1512 ssa_op_iter iter;
1513 tree last_copy_propagated_op = NULL;
1515 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
1517 tree old_op = USE_FROM_PTR (op_p);
1519 /* If we have A = B and B = A in the copy propagation tables
1520 (due to an equality comparison), avoid substituting B for A
1521 then A for B in the trivially discovered cases. This allows
1522 optimization of statements were A and B appear as input
1523 operands. */
1524 if (old_op != last_copy_propagated_op)
1526 cprop_operand (stmt, op_p);
1528 tree new_op = USE_FROM_PTR (op_p);
1529 if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME)
1530 last_copy_propagated_op = new_op;
1535 /* Optimize the statement in block BB pointed to by iterator SI
1536 using equivalences from CONST_AND_COPIES and AVAIL_EXPRS_STACK.
1538 We try to perform some simplistic global redundancy elimination and
1539 constant propagation:
1541 1- To detect global redundancy, we keep track of expressions that have
1542 been computed in this block and its dominators. If we find that the
1543 same expression is computed more than once, we eliminate repeated
1544 computations by using the target of the first one.
1546 2- Constant values and copy assignments. This is used to do very
1547 simplistic constant and copy propagation. When a constant or copy
1548 assignment is found, we map the value on the RHS of the assignment to
1549 the variable in the LHS in the CONST_AND_COPIES table. */
1551 static edge
1552 optimize_stmt (basic_block bb, gimple_stmt_iterator si,
1553 class const_and_copies *const_and_copies,
1554 class avail_exprs_stack *avail_exprs_stack)
1556 gimple *stmt, *old_stmt;
1557 bool may_optimize_p;
1558 bool modified_p = false;
1559 bool was_noreturn;
1560 edge retval = NULL;
1562 old_stmt = stmt = gsi_stmt (si);
1563 was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
1565 if (dump_file && (dump_flags & TDF_DETAILS))
1567 fprintf (dump_file, "Optimizing statement ");
1568 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1571 update_stmt_if_modified (stmt);
1572 opt_stats.num_stmts++;
1574 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1575 cprop_into_stmt (stmt);
1577 /* If the statement has been modified with constant replacements,
1578 fold its RHS before checking for redundant computations. */
1579 if (gimple_modified_p (stmt))
1581 tree rhs = NULL;
1583 /* Try to fold the statement making sure that STMT is kept
1584 up to date. */
1585 if (fold_stmt (&si))
1587 stmt = gsi_stmt (si);
1588 gimple_set_modified (stmt, true);
1590 if (dump_file && (dump_flags & TDF_DETAILS))
1592 fprintf (dump_file, " Folded to: ");
1593 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1597 /* We only need to consider cases that can yield a gimple operand. */
1598 if (gimple_assign_single_p (stmt))
1599 rhs = gimple_assign_rhs1 (stmt);
1600 else if (gimple_code (stmt) == GIMPLE_GOTO)
1601 rhs = gimple_goto_dest (stmt);
1602 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1603 /* This should never be an ADDR_EXPR. */
1604 rhs = gimple_switch_index (swtch_stmt);
1606 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
1607 recompute_tree_invariant_for_addr_expr (rhs);
1609 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1610 even if fold_stmt updated the stmt already and thus cleared
1611 gimple_modified_p flag on it. */
1612 modified_p = true;
1615 /* Check for redundant computations. Do this optimization only
1616 for assignments that have no volatile ops and conditionals. */
1617 may_optimize_p = (!gimple_has_side_effects (stmt)
1618 && (is_gimple_assign (stmt)
1619 || (is_gimple_call (stmt)
1620 && gimple_call_lhs (stmt) != NULL_TREE)
1621 || gimple_code (stmt) == GIMPLE_COND
1622 || gimple_code (stmt) == GIMPLE_SWITCH));
1624 if (may_optimize_p)
1626 if (gimple_code (stmt) == GIMPLE_CALL)
1628 /* Resolve __builtin_constant_p. If it hasn't been
1629 folded to integer_one_node by now, it's fairly
1630 certain that the value simply isn't constant. */
1631 tree callee = gimple_call_fndecl (stmt);
1632 if (callee
1633 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
1634 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P)
1636 propagate_tree_value_into_stmt (&si, integer_zero_node);
1637 stmt = gsi_stmt (si);
1641 if (gimple_code (stmt) == GIMPLE_COND)
1643 tree lhs = gimple_cond_lhs (stmt);
1644 tree rhs = gimple_cond_rhs (stmt);
1646 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
1647 then this conditional is computable at compile time. We can just
1648 shove either 0 or 1 into the LHS, mark the statement as modified
1649 and all the right things will just happen below.
1651 Note this would apply to any case where LHS has a range
1652 narrower than its type implies and RHS is outside that
1653 narrower range. Future work. */
1654 if (TREE_CODE (lhs) == SSA_NAME
1655 && ssa_name_has_boolean_range (lhs)
1656 && TREE_CODE (rhs) == INTEGER_CST
1657 && ! (integer_zerop (rhs) || integer_onep (rhs)))
1659 gimple_cond_set_lhs (as_a <gcond *> (stmt),
1660 fold_convert (TREE_TYPE (lhs),
1661 integer_zero_node));
1662 gimple_set_modified (stmt, true);
1666 update_stmt_if_modified (stmt);
1667 eliminate_redundant_computations (&si, const_and_copies,
1668 avail_exprs_stack);
1669 stmt = gsi_stmt (si);
1671 /* Perform simple redundant store elimination. */
1672 if (gimple_assign_single_p (stmt)
1673 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
1675 tree lhs = gimple_assign_lhs (stmt);
1676 tree rhs = gimple_assign_rhs1 (stmt);
1677 tree cached_lhs;
1678 gassign *new_stmt;
1679 rhs = dom_valueize (rhs);
1680 /* Build a new statement with the RHS and LHS exchanged. */
1681 if (TREE_CODE (rhs) == SSA_NAME)
1683 gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
1684 new_stmt = gimple_build_assign (rhs, lhs);
1685 SSA_NAME_DEF_STMT (rhs) = defstmt;
1687 else
1688 new_stmt = gimple_build_assign (rhs, lhs);
1689 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
1690 cached_lhs = avail_exprs_stack->lookup_avail_expr (new_stmt, false,
1691 false);
1692 if (cached_lhs
1693 && rhs == cached_lhs)
1695 basic_block bb = gimple_bb (stmt);
1696 unlink_stmt_vdef (stmt);
1697 if (gsi_remove (&si, true))
1699 bitmap_set_bit (need_eh_cleanup, bb->index);
1700 if (dump_file && (dump_flags & TDF_DETAILS))
1701 fprintf (dump_file, " Flagged to clear EH edges.\n");
1703 release_defs (stmt);
1704 return retval;
1709 /* Record any additional equivalences created by this statement. */
1710 if (is_gimple_assign (stmt))
1711 record_equivalences_from_stmt (stmt, may_optimize_p, avail_exprs_stack);
1713 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
1714 know where it goes. */
1715 if (gimple_modified_p (stmt) || modified_p)
1717 tree val = NULL;
1719 if (gimple_code (stmt) == GIMPLE_COND)
1720 val = fold_binary_loc (gimple_location (stmt),
1721 gimple_cond_code (stmt), boolean_type_node,
1722 gimple_cond_lhs (stmt),
1723 gimple_cond_rhs (stmt));
1724 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1725 val = gimple_switch_index (swtch_stmt);
1727 if (val && TREE_CODE (val) == INTEGER_CST)
1729 retval = find_taken_edge (bb, val);
1730 if (retval)
1732 /* Fix the condition to be either true or false. */
1733 if (gimple_code (stmt) == GIMPLE_COND)
1735 if (integer_zerop (val))
1736 gimple_cond_make_false (as_a <gcond *> (stmt));
1737 else if (integer_onep (val))
1738 gimple_cond_make_true (as_a <gcond *> (stmt));
1739 else
1740 gcc_unreachable ();
1742 gimple_set_modified (stmt, true);
1745 /* Further simplifications may be possible. */
1746 cfg_altered = true;
1750 update_stmt_if_modified (stmt);
1752 /* If we simplified a statement in such a way as to be shown that it
1753 cannot trap, update the eh information and the cfg to match. */
1754 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1756 bitmap_set_bit (need_eh_cleanup, bb->index);
1757 if (dump_file && (dump_flags & TDF_DETAILS))
1758 fprintf (dump_file, " Flagged to clear EH edges.\n");
1761 if (!was_noreturn
1762 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
1763 need_noreturn_fixup.safe_push (stmt);
1765 return retval;