gcc/
[official-gcc.git] / gcc / tree-ssa-dom.c
blob8bf5b3c9ffed19d19850c31482a9c38f1fd6f0f8
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)
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 known values of a conditional expression
52 at the exits from its block. */
54 struct cond_equivalence
56 struct hashable_expr cond;
57 tree value;
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. */
70 struct edge_info
72 /* If this edge creates a simple equivalence, the LHS and RHS of
73 the equivalence will be stored here. */
74 tree lhs;
75 tree rhs;
77 /* Traversing an edge may also indicate one or more particular conditions
78 are true or false. */
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. */
91 struct opt_stats_d
93 long num_stmts;
94 long num_exprs_considered;
95 long num_re;
96 long num_const_prop;
97 long num_copy_prop;
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 bool = true);
108 static void record_cond (cond_equivalence *, class avail_exprs_stack *);
109 static void record_equality (tree, tree, class const_and_copies *);
110 static void record_equivalences_from_phis (basic_block);
111 static void record_equivalences_from_incoming_edge (basic_block,
112 class const_and_copies *,
113 class avail_exprs_stack *);
114 static void eliminate_redundant_computations (gimple_stmt_iterator *,
115 class const_and_copies *,
116 class avail_exprs_stack *);
117 static void record_equivalences_from_stmt (gimple *, int,
118 class avail_exprs_stack *);
119 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
120 static void dump_dominator_optimization_stats (FILE *file,
121 hash_table<expr_elt_hasher> *);
124 /* Free the edge_info data attached to E, if it exists. */
126 void
127 free_dom_edge_info (edge e)
129 struct edge_info *edge_info = (struct edge_info *)e->aux;
131 if (edge_info)
133 edge_info->cond_equivalences.release ();
134 free (edge_info);
138 /* Allocate an EDGE_INFO for edge E and attach it to E.
139 Return the new EDGE_INFO structure. */
141 static struct edge_info *
142 allocate_edge_info (edge e)
144 struct edge_info *edge_info;
146 /* Free the old one, if it exists. */
147 free_dom_edge_info (e);
149 edge_info = XCNEW (struct edge_info);
151 e->aux = edge_info;
152 return edge_info;
155 /* Free all EDGE_INFO structures associated with edges in the CFG.
156 If a particular edge can be threaded, copy the redirection
157 target from the EDGE_INFO structure into the edge's AUX field
158 as required by code to update the CFG and SSA graph for
159 jump threading. */
161 static void
162 free_all_edge_infos (void)
164 basic_block bb;
165 edge_iterator ei;
166 edge e;
168 FOR_EACH_BB_FN (bb, cfun)
170 FOR_EACH_EDGE (e, ei, bb->preds)
172 free_dom_edge_info (e);
173 e->aux = NULL;
178 /* Build a cond_equivalence record indicating that the comparison
179 CODE holds between operands OP0 and OP1 and push it to **P. */
181 static void
182 build_and_record_new_cond (enum tree_code code,
183 tree op0, tree op1,
184 vec<cond_equivalence> *p,
185 bool val = true)
187 cond_equivalence c;
188 struct hashable_expr *cond = &c.cond;
190 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
192 cond->type = boolean_type_node;
193 cond->kind = EXPR_BINARY;
194 cond->ops.binary.op = code;
195 cond->ops.binary.opnd0 = op0;
196 cond->ops.binary.opnd1 = op1;
198 c.value = val ? boolean_true_node : boolean_false_node;
199 p->safe_push (c);
202 /* Record that COND is true and INVERTED is false into the edge information
203 structure. Also record that any conditions dominated by COND are true
204 as well.
206 For example, if a < b is true, then a <= b must also be true. */
208 static void
209 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
211 tree op0, op1;
212 cond_equivalence c;
214 if (!COMPARISON_CLASS_P (cond))
215 return;
217 op0 = TREE_OPERAND (cond, 0);
218 op1 = TREE_OPERAND (cond, 1);
220 switch (TREE_CODE (cond))
222 case LT_EXPR:
223 case GT_EXPR:
224 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
226 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
227 &edge_info->cond_equivalences);
228 build_and_record_new_cond (LTGT_EXPR, op0, op1,
229 &edge_info->cond_equivalences);
232 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
233 ? LE_EXPR : GE_EXPR),
234 op0, op1, &edge_info->cond_equivalences);
235 build_and_record_new_cond (NE_EXPR, op0, op1,
236 &edge_info->cond_equivalences);
237 build_and_record_new_cond (EQ_EXPR, op0, op1,
238 &edge_info->cond_equivalences, false);
239 break;
241 case GE_EXPR:
242 case LE_EXPR:
243 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
245 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
246 &edge_info->cond_equivalences);
248 break;
250 case EQ_EXPR:
251 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
253 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
254 &edge_info->cond_equivalences);
256 build_and_record_new_cond (LE_EXPR, op0, op1,
257 &edge_info->cond_equivalences);
258 build_and_record_new_cond (GE_EXPR, op0, op1,
259 &edge_info->cond_equivalences);
260 break;
262 case UNORDERED_EXPR:
263 build_and_record_new_cond (NE_EXPR, op0, op1,
264 &edge_info->cond_equivalences);
265 build_and_record_new_cond (UNLE_EXPR, op0, op1,
266 &edge_info->cond_equivalences);
267 build_and_record_new_cond (UNGE_EXPR, op0, op1,
268 &edge_info->cond_equivalences);
269 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
270 &edge_info->cond_equivalences);
271 build_and_record_new_cond (UNLT_EXPR, op0, op1,
272 &edge_info->cond_equivalences);
273 build_and_record_new_cond (UNGT_EXPR, op0, op1,
274 &edge_info->cond_equivalences);
275 break;
277 case UNLT_EXPR:
278 case UNGT_EXPR:
279 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
280 ? UNLE_EXPR : UNGE_EXPR),
281 op0, op1, &edge_info->cond_equivalences);
282 build_and_record_new_cond (NE_EXPR, op0, op1,
283 &edge_info->cond_equivalences);
284 break;
286 case UNEQ_EXPR:
287 build_and_record_new_cond (UNLE_EXPR, op0, op1,
288 &edge_info->cond_equivalences);
289 build_and_record_new_cond (UNGE_EXPR, op0, op1,
290 &edge_info->cond_equivalences);
291 break;
293 case LTGT_EXPR:
294 build_and_record_new_cond (NE_EXPR, op0, op1,
295 &edge_info->cond_equivalences);
296 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
297 &edge_info->cond_equivalences);
298 break;
300 default:
301 break;
304 /* Now store the original true and false conditions into the first
305 two slots. */
306 initialize_expr_from_cond (cond, &c.cond);
307 c.value = boolean_true_node;
308 edge_info->cond_equivalences.safe_push (c);
310 /* It is possible for INVERTED to be the negation of a comparison,
311 and not a valid RHS or GIMPLE_COND condition. This happens because
312 invert_truthvalue may return such an expression when asked to invert
313 a floating-point comparison. These comparisons are not assumed to
314 obey the trichotomy law. */
315 initialize_expr_from_cond (inverted, &c.cond);
316 c.value = boolean_false_node;
317 edge_info->cond_equivalences.safe_push (c);
320 /* We have finished optimizing BB, record any information implied by
321 taking a specific outgoing edge from BB. */
323 static void
324 record_edge_info (basic_block bb)
326 gimple_stmt_iterator gsi = gsi_last_bb (bb);
327 struct edge_info *edge_info;
329 if (! gsi_end_p (gsi))
331 gimple *stmt = gsi_stmt (gsi);
332 location_t loc = gimple_location (stmt);
334 if (gimple_code (stmt) == GIMPLE_SWITCH)
336 gswitch *switch_stmt = as_a <gswitch *> (stmt);
337 tree index = gimple_switch_index (switch_stmt);
339 if (TREE_CODE (index) == SSA_NAME)
341 int i;
342 int n_labels = gimple_switch_num_labels (switch_stmt);
343 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
344 edge e;
345 edge_iterator ei;
347 for (i = 0; i < n_labels; i++)
349 tree label = gimple_switch_label (switch_stmt, i);
350 basic_block target_bb = label_to_block (CASE_LABEL (label));
351 if (CASE_HIGH (label)
352 || !CASE_LOW (label)
353 || info[target_bb->index])
354 info[target_bb->index] = error_mark_node;
355 else
356 info[target_bb->index] = label;
359 FOR_EACH_EDGE (e, ei, bb->succs)
361 basic_block target_bb = e->dest;
362 tree label = info[target_bb->index];
364 if (label != NULL && label != error_mark_node)
366 tree x = fold_convert_loc (loc, TREE_TYPE (index),
367 CASE_LOW (label));
368 edge_info = allocate_edge_info (e);
369 edge_info->lhs = index;
370 edge_info->rhs = x;
373 free (info);
377 /* A COND_EXPR may create equivalences too. */
378 if (gimple_code (stmt) == GIMPLE_COND)
380 edge true_edge;
381 edge false_edge;
383 tree op0 = gimple_cond_lhs (stmt);
384 tree op1 = gimple_cond_rhs (stmt);
385 enum tree_code code = gimple_cond_code (stmt);
387 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
389 /* Special case comparing booleans against a constant as we
390 know the value of OP0 on both arms of the branch. i.e., we
391 can record an equivalence for OP0 rather than COND.
393 However, don't do this if the constant isn't zero or one.
394 Such conditionals will get optimized more thoroughly during
395 the domwalk. */
396 if ((code == EQ_EXPR || code == NE_EXPR)
397 && TREE_CODE (op0) == SSA_NAME
398 && ssa_name_has_boolean_range (op0)
399 && is_gimple_min_invariant (op1)
400 && (integer_zerop (op1) || integer_onep (op1)))
402 tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
403 tree false_val = constant_boolean_node (false, TREE_TYPE (op0));
405 if (code == EQ_EXPR)
407 edge_info = allocate_edge_info (true_edge);
408 edge_info->lhs = op0;
409 edge_info->rhs = (integer_zerop (op1) ? false_val : true_val);
411 edge_info = allocate_edge_info (false_edge);
412 edge_info->lhs = op0;
413 edge_info->rhs = (integer_zerop (op1) ? true_val : false_val);
415 else
417 edge_info = allocate_edge_info (true_edge);
418 edge_info->lhs = op0;
419 edge_info->rhs = (integer_zerop (op1) ? true_val : false_val);
421 edge_info = allocate_edge_info (false_edge);
422 edge_info->lhs = op0;
423 edge_info->rhs = (integer_zerop (op1) ? false_val : true_val);
426 else if (is_gimple_min_invariant (op0)
427 && (TREE_CODE (op1) == SSA_NAME
428 || is_gimple_min_invariant (op1)))
430 tree cond = build2 (code, boolean_type_node, op0, op1);
431 tree inverted = invert_truthvalue_loc (loc, cond);
432 bool can_infer_simple_equiv
433 = !(HONOR_SIGNED_ZEROS (op0)
434 && real_zerop (op0));
435 struct edge_info *edge_info;
437 edge_info = allocate_edge_info (true_edge);
438 record_conditions (edge_info, cond, inverted);
440 if (can_infer_simple_equiv && code == EQ_EXPR)
442 edge_info->lhs = op1;
443 edge_info->rhs = op0;
446 edge_info = allocate_edge_info (false_edge);
447 record_conditions (edge_info, inverted, cond);
449 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
451 edge_info->lhs = op1;
452 edge_info->rhs = op0;
456 else if (TREE_CODE (op0) == SSA_NAME
457 && (TREE_CODE (op1) == SSA_NAME
458 || is_gimple_min_invariant (op1)))
460 tree cond = build2 (code, boolean_type_node, op0, op1);
461 tree inverted = invert_truthvalue_loc (loc, cond);
462 bool can_infer_simple_equiv
463 = !(HONOR_SIGNED_ZEROS (op1)
464 && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
465 struct edge_info *edge_info;
467 edge_info = allocate_edge_info (true_edge);
468 record_conditions (edge_info, cond, inverted);
470 if (can_infer_simple_equiv && code == EQ_EXPR)
472 edge_info->lhs = op0;
473 edge_info->rhs = op1;
476 edge_info = allocate_edge_info (false_edge);
477 record_conditions (edge_info, inverted, cond);
479 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
481 edge_info->lhs = op0;
482 edge_info->rhs = op1;
487 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
492 class dom_opt_dom_walker : public dom_walker
494 public:
495 dom_opt_dom_walker (cdi_direction direction,
496 class const_and_copies *const_and_copies,
497 class avail_exprs_stack *avail_exprs_stack)
498 : dom_walker (direction, true),
499 m_const_and_copies (const_and_copies),
500 m_avail_exprs_stack (avail_exprs_stack),
501 m_dummy_cond (NULL) {}
503 virtual edge before_dom_children (basic_block);
504 virtual void after_dom_children (basic_block);
506 private:
507 void thread_across_edge (edge);
509 /* Unwindable equivalences, both const/copy and expression varieties. */
510 class const_and_copies *m_const_and_copies;
511 class avail_exprs_stack *m_avail_exprs_stack;
513 gcond *m_dummy_cond;
516 /* Jump threading, redundancy elimination and const/copy propagation.
518 This pass may expose new symbols that need to be renamed into SSA. For
519 every new symbol exposed, its corresponding bit will be set in
520 VARS_TO_RENAME. */
522 namespace {
524 const pass_data pass_data_dominator =
526 GIMPLE_PASS, /* type */
527 "dom", /* name */
528 OPTGROUP_NONE, /* optinfo_flags */
529 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
530 ( PROP_cfg | PROP_ssa ), /* properties_required */
531 0, /* properties_provided */
532 0, /* properties_destroyed */
533 0, /* todo_flags_start */
534 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
537 class pass_dominator : public gimple_opt_pass
539 public:
540 pass_dominator (gcc::context *ctxt)
541 : gimple_opt_pass (pass_data_dominator, ctxt),
542 may_peel_loop_headers_p (false)
545 /* opt_pass methods: */
546 opt_pass * clone () { return new pass_dominator (m_ctxt); }
547 void set_pass_param (unsigned int n, bool param)
549 gcc_assert (n == 0);
550 may_peel_loop_headers_p = param;
552 virtual bool gate (function *) { return flag_tree_dom != 0; }
553 virtual unsigned int execute (function *);
555 private:
556 /* This flag is used to prevent loops from being peeled repeatedly in jump
557 threading; it will be removed once we preserve loop structures throughout
558 the compilation -- we will be able to mark the affected loops directly in
559 jump threading, and avoid peeling them next time. */
560 bool may_peel_loop_headers_p;
561 }; // class pass_dominator
563 unsigned int
564 pass_dominator::execute (function *fun)
566 memset (&opt_stats, 0, sizeof (opt_stats));
568 /* Create our hash tables. */
569 hash_table<expr_elt_hasher> *avail_exprs
570 = new hash_table<expr_elt_hasher> (1024);
571 class avail_exprs_stack *avail_exprs_stack
572 = new class avail_exprs_stack (avail_exprs);
573 class const_and_copies *const_and_copies = new class const_and_copies ();
574 need_eh_cleanup = BITMAP_ALLOC (NULL);
575 need_noreturn_fixup.create (0);
577 calculate_dominance_info (CDI_DOMINATORS);
578 cfg_altered = false;
580 /* We need to know loop structures in order to avoid destroying them
581 in jump threading. Note that we still can e.g. thread through loop
582 headers to an exit edge, or through loop header to the loop body, assuming
583 that we update the loop info.
585 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
586 to several overly conservative bail-outs in jump threading, case
587 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
588 missing. We should improve jump threading in future then
589 LOOPS_HAVE_PREHEADERS won't be needed here. */
590 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
592 /* Initialize the value-handle array. */
593 threadedge_initialize_values ();
595 /* We need accurate information regarding back edges in the CFG
596 for jump threading; this may include back edges that are not part of
597 a single loop. */
598 mark_dfs_back_edges ();
600 /* We want to create the edge info structures before the dominator walk
601 so that they'll be in place for the jump threader, particularly when
602 threading through a join block.
604 The conditions will be lazily updated with global equivalences as
605 we reach them during the dominator walk. */
606 basic_block bb;
607 FOR_EACH_BB_FN (bb, fun)
608 record_edge_info (bb);
610 /* Recursively walk the dominator tree optimizing statements. */
611 dom_opt_dom_walker walker (CDI_DOMINATORS,
612 const_and_copies,
613 avail_exprs_stack);
614 walker.walk (fun->cfg->x_entry_block_ptr);
616 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
617 edge. When found, remove jump threads which contain any outgoing
618 edge from the affected block. */
619 if (cfg_altered)
621 FOR_EACH_BB_FN (bb, fun)
623 edge_iterator ei;
624 edge e;
626 /* First see if there are any edges without EDGE_EXECUTABLE
627 set. */
628 bool found = false;
629 FOR_EACH_EDGE (e, ei, bb->succs)
631 if ((e->flags & EDGE_EXECUTABLE) == 0)
633 found = true;
634 break;
638 /* If there were any such edges found, then remove jump threads
639 containing any edge leaving BB. */
640 if (found)
641 FOR_EACH_EDGE (e, ei, bb->succs)
642 remove_jump_threads_including (e);
647 gimple_stmt_iterator gsi;
648 basic_block bb;
649 FOR_EACH_BB_FN (bb, fun)
651 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
652 update_stmt_if_modified (gsi_stmt (gsi));
656 /* If we exposed any new variables, go ahead and put them into
657 SSA form now, before we handle jump threading. This simplifies
658 interactions between rewriting of _DECL nodes into SSA form
659 and rewriting SSA_NAME nodes into SSA form after block
660 duplication and CFG manipulation. */
661 update_ssa (TODO_update_ssa);
663 free_all_edge_infos ();
665 /* Thread jumps, creating duplicate blocks as needed. */
666 cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p);
668 if (cfg_altered)
669 free_dominance_info (CDI_DOMINATORS);
671 /* Removal of statements may make some EH edges dead. Purge
672 such edges from the CFG as needed. */
673 if (!bitmap_empty_p (need_eh_cleanup))
675 unsigned i;
676 bitmap_iterator bi;
678 /* Jump threading may have created forwarder blocks from blocks
679 needing EH cleanup; the new successor of these blocks, which
680 has inherited from the original block, needs the cleanup.
681 Don't clear bits in the bitmap, as that can break the bitmap
682 iterator. */
683 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
685 basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
686 if (bb == NULL)
687 continue;
688 while (single_succ_p (bb)
689 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
690 bb = single_succ (bb);
691 if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
692 continue;
693 if ((unsigned) bb->index != i)
694 bitmap_set_bit (need_eh_cleanup, bb->index);
697 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
698 bitmap_clear (need_eh_cleanup);
701 /* Fixup stmts that became noreturn calls. This may require splitting
702 blocks and thus isn't possible during the dominator walk or before
703 jump threading finished. Do this in reverse order so we don't
704 inadvertedly remove a stmt we want to fixup by visiting a dominating
705 now noreturn call first. */
706 while (!need_noreturn_fixup.is_empty ())
708 gimple *stmt = need_noreturn_fixup.pop ();
709 if (dump_file && dump_flags & TDF_DETAILS)
711 fprintf (dump_file, "Fixing up noreturn call ");
712 print_gimple_stmt (dump_file, stmt, 0, 0);
713 fprintf (dump_file, "\n");
715 fixup_noreturn_call (stmt);
718 statistics_counter_event (fun, "Redundant expressions eliminated",
719 opt_stats.num_re);
720 statistics_counter_event (fun, "Constants propagated",
721 opt_stats.num_const_prop);
722 statistics_counter_event (fun, "Copies propagated",
723 opt_stats.num_copy_prop);
725 /* Debugging dumps. */
726 if (dump_file && (dump_flags & TDF_STATS))
727 dump_dominator_optimization_stats (dump_file, avail_exprs);
729 loop_optimizer_finalize ();
731 /* Delete our main hashtable. */
732 delete avail_exprs;
733 avail_exprs = NULL;
735 /* Free asserted bitmaps and stacks. */
736 BITMAP_FREE (need_eh_cleanup);
737 need_noreturn_fixup.release ();
738 delete avail_exprs_stack;
739 delete const_and_copies;
741 /* Free the value-handle array. */
742 threadedge_finalize_values ();
744 return 0;
747 } // anon namespace
749 gimple_opt_pass *
750 make_pass_dominator (gcc::context *ctxt)
752 return new pass_dominator (ctxt);
756 /* Given a conditional statement CONDSTMT, convert the
757 condition to a canonical form. */
759 static void
760 canonicalize_comparison (gcond *condstmt)
762 tree op0;
763 tree op1;
764 enum tree_code code;
766 gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
768 op0 = gimple_cond_lhs (condstmt);
769 op1 = gimple_cond_rhs (condstmt);
771 code = gimple_cond_code (condstmt);
773 /* If it would be profitable to swap the operands, then do so to
774 canonicalize the statement, enabling better optimization.
776 By placing canonicalization of such expressions here we
777 transparently keep statements in canonical form, even
778 when the statement is modified. */
779 if (tree_swap_operands_p (op0, op1, false))
781 /* For relationals we need to swap the operands
782 and change the code. */
783 if (code == LT_EXPR
784 || code == GT_EXPR
785 || code == LE_EXPR
786 || code == GE_EXPR)
788 code = swap_tree_comparison (code);
790 gimple_cond_set_code (condstmt, code);
791 gimple_cond_set_lhs (condstmt, op1);
792 gimple_cond_set_rhs (condstmt, op0);
794 update_stmt (condstmt);
799 /* A trivial wrapper so that we can present the generic jump
800 threading code with a simple API for simplifying statements. */
801 static tree
802 simplify_stmt_for_jump_threading (gimple *stmt,
803 gimple *within_stmt ATTRIBUTE_UNUSED,
804 class avail_exprs_stack *avail_exprs_stack)
806 return lookup_avail_expr (stmt, false, avail_exprs_stack);
809 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
811 static tree
812 dom_valueize (tree t)
814 if (TREE_CODE (t) == SSA_NAME)
816 tree tem = SSA_NAME_VALUE (t);
817 if (tem)
818 return tem;
820 return t;
823 /* We have just found an equivalence for LHS on an edge E.
824 Look backwards to other uses of LHS and see if we can derive
825 additional equivalences that are valid on edge E. */
826 static void
827 back_propagate_equivalences (tree lhs, edge e,
828 class const_and_copies *const_and_copies)
830 use_operand_p use_p;
831 imm_use_iterator iter;
832 bitmap domby = NULL;
833 basic_block dest = e->dest;
835 /* Iterate over the uses of LHS to see if any dominate E->dest.
836 If so, they may create useful equivalences too.
838 ??? If the code gets re-organized to a worklist to catch more
839 indirect opportunities and it is made to handle PHIs then this
840 should only consider use_stmts in basic-blocks we have already visited. */
841 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
843 gimple *use_stmt = USE_STMT (use_p);
845 /* Often the use is in DEST, which we trivially know we can't use.
846 This is cheaper than the dominator set tests below. */
847 if (dest == gimple_bb (use_stmt))
848 continue;
850 /* Filter out statements that can never produce a useful
851 equivalence. */
852 tree lhs2 = gimple_get_lhs (use_stmt);
853 if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME)
854 continue;
856 /* Profiling has shown the domination tests here can be fairly
857 expensive. We get significant improvements by building the
858 set of blocks that dominate BB. We can then just test
859 for set membership below.
861 We also initialize the set lazily since often the only uses
862 are going to be in the same block as DEST. */
863 if (!domby)
865 domby = BITMAP_ALLOC (NULL);
866 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest);
867 while (bb)
869 bitmap_set_bit (domby, bb->index);
870 bb = get_immediate_dominator (CDI_DOMINATORS, bb);
874 /* This tests if USE_STMT does not dominate DEST. */
875 if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index))
876 continue;
878 /* At this point USE_STMT dominates DEST and may result in a
879 useful equivalence. Try to simplify its RHS to a constant
880 or SSA_NAME. */
881 tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize,
882 no_follow_ssa_edges);
883 if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res)))
884 record_equality (lhs2, res, const_and_copies);
887 if (domby)
888 BITMAP_FREE (domby);
891 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
892 by traversing edge E (which are cached in E->aux).
894 Callers are responsible for managing the unwinding markers. */
895 void
896 record_temporary_equivalences (edge e,
897 class const_and_copies *const_and_copies,
898 class avail_exprs_stack *avail_exprs_stack)
900 int i;
901 struct edge_info *edge_info = (struct edge_info *) e->aux;
903 /* If we have info associated with this edge, record it into
904 our equivalence tables. */
905 if (edge_info)
907 cond_equivalence *eq;
908 /* If we have 0 = COND or 1 = COND equivalences, record them
909 into our expression hash tables. */
910 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
911 record_cond (eq, avail_exprs_stack);
913 tree lhs = edge_info->lhs;
914 if (!lhs || TREE_CODE (lhs) != SSA_NAME)
915 return;
917 /* Record the simple NAME = VALUE equivalence. */
918 tree rhs = edge_info->rhs;
919 record_equality (lhs, rhs, const_and_copies);
921 /* We already recorded that LHS = RHS, with canonicalization,
922 value chain following, etc.
924 We also want to record RHS = LHS, but without any canonicalization
925 or value chain following. */
926 if (TREE_CODE (rhs) == SSA_NAME)
927 const_and_copies->record_const_or_copy_raw (rhs, lhs,
928 SSA_NAME_VALUE (rhs));
930 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
931 set via a widening type conversion, then we may be able to record
932 additional equivalences. */
933 if (TREE_CODE (rhs) == INTEGER_CST)
935 gimple *defstmt = SSA_NAME_DEF_STMT (lhs);
937 if (defstmt
938 && is_gimple_assign (defstmt)
939 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt)))
941 tree old_rhs = gimple_assign_rhs1 (defstmt);
943 /* If the conversion widens the original value and
944 the constant is in the range of the type of OLD_RHS,
945 then convert the constant and record the equivalence.
947 Note that int_fits_type_p does not check the precision
948 if the upper and lower bounds are OK. */
949 if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs))
950 && (TYPE_PRECISION (TREE_TYPE (lhs))
951 > TYPE_PRECISION (TREE_TYPE (old_rhs)))
952 && int_fits_type_p (rhs, TREE_TYPE (old_rhs)))
954 tree newval = fold_convert (TREE_TYPE (old_rhs), rhs);
955 record_equality (old_rhs, newval, const_and_copies);
960 /* Any equivalence found for LHS may result in additional
961 equivalences for other uses of LHS that we have already
962 processed. */
963 back_propagate_equivalences (lhs, e, const_and_copies);
967 /* Wrapper for common code to attempt to thread an edge. For example,
968 it handles lazily building the dummy condition and the bookkeeping
969 when jump threading is successful. */
971 void
972 dom_opt_dom_walker::thread_across_edge (edge e)
974 if (! m_dummy_cond)
975 m_dummy_cond =
976 gimple_build_cond (NE_EXPR,
977 integer_zero_node, integer_zero_node,
978 NULL, NULL);
980 /* Push a marker on both stacks so we can unwind the tables back to their
981 current state. */
982 m_avail_exprs_stack->push_marker ();
983 m_const_and_copies->push_marker ();
985 /* With all the edge equivalences in the tables, go ahead and attempt
986 to thread through E->dest. */
987 ::thread_across_edge (m_dummy_cond, e, false,
988 m_const_and_copies, m_avail_exprs_stack,
989 simplify_stmt_for_jump_threading);
991 /* And restore the various tables to their state before
992 we threaded this edge.
994 XXX The code in tree-ssa-threadedge.c will restore the state of
995 the const_and_copies table. We we just have to restore the expression
996 table. */
997 m_avail_exprs_stack->pop_to_marker ();
1000 /* PHI nodes can create equivalences too.
1002 Ignoring any alternatives which are the same as the result, if
1003 all the alternatives are equal, then the PHI node creates an
1004 equivalence. */
1006 static void
1007 record_equivalences_from_phis (basic_block bb)
1009 gphi_iterator gsi;
1011 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1013 gphi *phi = gsi.phi ();
1015 tree lhs = gimple_phi_result (phi);
1016 tree rhs = NULL;
1017 size_t i;
1019 for (i = 0; i < gimple_phi_num_args (phi); i++)
1021 tree t = gimple_phi_arg_def (phi, i);
1023 /* Ignore alternatives which are the same as our LHS. Since
1024 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1025 can simply compare pointers. */
1026 if (lhs == t)
1027 continue;
1029 /* If the associated edge is not marked as executable, then it
1030 can be ignored. */
1031 if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0)
1032 continue;
1034 t = dom_valueize (t);
1036 /* If we have not processed an alternative yet, then set
1037 RHS to this alternative. */
1038 if (rhs == NULL)
1039 rhs = t;
1040 /* If we have processed an alternative (stored in RHS), then
1041 see if it is equal to this one. If it isn't, then stop
1042 the search. */
1043 else if (! operand_equal_for_phi_arg_p (rhs, t))
1044 break;
1047 /* If we had no interesting alternatives, then all the RHS alternatives
1048 must have been the same as LHS. */
1049 if (!rhs)
1050 rhs = lhs;
1052 /* If we managed to iterate through each PHI alternative without
1053 breaking out of the loop, then we have a PHI which may create
1054 a useful equivalence. We do not need to record unwind data for
1055 this, since this is a true assignment and not an equivalence
1056 inferred from a comparison. All uses of this ssa name are dominated
1057 by this assignment, so unwinding just costs time and space. */
1058 if (i == gimple_phi_num_args (phi)
1059 && may_propagate_copy (lhs, rhs))
1060 set_ssa_name_value (lhs, rhs);
1064 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1065 return that edge. Otherwise return NULL. */
1066 static edge
1067 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1069 edge retval = NULL;
1070 edge e;
1071 edge_iterator ei;
1073 FOR_EACH_EDGE (e, ei, bb->preds)
1075 /* A loop back edge can be identified by the destination of
1076 the edge dominating the source of the edge. */
1077 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1078 continue;
1080 /* We can safely ignore edges that are not executable. */
1081 if ((e->flags & EDGE_EXECUTABLE) == 0)
1082 continue;
1084 /* If we have already seen a non-loop edge, then we must have
1085 multiple incoming non-loop edges and thus we return NULL. */
1086 if (retval)
1087 return NULL;
1089 /* This is the first non-loop incoming edge we have found. Record
1090 it. */
1091 retval = e;
1094 return retval;
1097 /* Record any equivalences created by the incoming edge to BB into
1098 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
1099 incoming edge, then no equivalence is created. */
1101 static void
1102 record_equivalences_from_incoming_edge (basic_block bb,
1103 class const_and_copies *const_and_copies,
1104 class avail_exprs_stack *avail_exprs_stack)
1106 edge e;
1107 basic_block parent;
1109 /* If our parent block ended with a control statement, then we may be
1110 able to record some equivalences based on which outgoing edge from
1111 the parent was followed. */
1112 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1114 e = single_incoming_edge_ignoring_loop_edges (bb);
1116 /* If we had a single incoming edge from our parent block, then enter
1117 any data associated with the edge into our tables. */
1118 if (e && e->src == parent)
1119 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
1122 /* Dump statistics for the hash table HTAB. */
1124 static void
1125 htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab)
1127 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1128 (long) htab.size (),
1129 (long) htab.elements (),
1130 htab.collisions ());
1133 /* Dump SSA statistics on FILE. */
1135 static void
1136 dump_dominator_optimization_stats (FILE *file,
1137 hash_table<expr_elt_hasher> *avail_exprs)
1139 fprintf (file, "Total number of statements: %6ld\n\n",
1140 opt_stats.num_stmts);
1141 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1142 opt_stats.num_exprs_considered);
1144 fprintf (file, "\nHash table statistics:\n");
1146 fprintf (file, " avail_exprs: ");
1147 htab_statistics (file, *avail_exprs);
1151 /* Enter condition equivalence P into AVAIL_EXPRS_HASH.
1153 This indicates that a conditional expression has a known
1154 boolean value. */
1156 static void
1157 record_cond (cond_equivalence *p,
1158 class avail_exprs_stack *avail_exprs_stack)
1160 class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value);
1161 expr_hash_elt **slot;
1163 hash_table<expr_elt_hasher> *avail_exprs = avail_exprs_stack->avail_exprs ();
1164 slot = avail_exprs->find_slot_with_hash (element, element->hash (), INSERT);
1165 if (*slot == NULL)
1167 *slot = element;
1168 avail_exprs_stack->record_expr (element, NULL, '1');
1170 else
1171 delete element;
1174 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1175 This constrains the cases in which we may treat this as assignment. */
1177 static void
1178 record_equality (tree x, tree y, class const_and_copies *const_and_copies)
1180 tree prev_x = NULL, prev_y = NULL;
1182 if (tree_swap_operands_p (x, y, false))
1183 std::swap (x, y);
1185 /* Most of the time tree_swap_operands_p does what we want. But there
1186 are cases where we know one operand is better for copy propagation than
1187 the other. Given no other code cares about ordering of equality
1188 comparison operators for that purpose, we just handle the special cases
1189 here. */
1190 if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME)
1192 /* If one operand is a single use operand, then make it
1193 X. This will preserve its single use properly and if this
1194 conditional is eliminated, the computation of X can be
1195 eliminated as well. */
1196 if (has_single_use (y) && ! has_single_use (x))
1197 std::swap (x, y);
1199 if (TREE_CODE (x) == SSA_NAME)
1200 prev_x = SSA_NAME_VALUE (x);
1201 if (TREE_CODE (y) == SSA_NAME)
1202 prev_y = SSA_NAME_VALUE (y);
1204 /* If one of the previous values is invariant, or invariant in more loops
1205 (by depth), then use that.
1206 Otherwise it doesn't matter which value we choose, just so
1207 long as we canonicalize on one value. */
1208 if (is_gimple_min_invariant (y))
1210 else if (is_gimple_min_invariant (x))
1211 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1212 else if (prev_x && is_gimple_min_invariant (prev_x))
1213 x = y, y = prev_x, prev_x = prev_y;
1214 else if (prev_y)
1215 y = prev_y;
1217 /* After the swapping, we must have one SSA_NAME. */
1218 if (TREE_CODE (x) != SSA_NAME)
1219 return;
1221 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1222 variable compared against zero. If we're honoring signed zeros,
1223 then we cannot record this value unless we know that the value is
1224 nonzero. */
1225 if (HONOR_SIGNED_ZEROS (x)
1226 && (TREE_CODE (y) != REAL_CST
1227 || real_equal (&dconst0, &TREE_REAL_CST (y))))
1228 return;
1230 const_and_copies->record_const_or_copy (x, y, prev_x);
1233 /* Returns true when STMT is a simple iv increment. It detects the
1234 following situation:
1236 i_1 = phi (..., i_2)
1237 i_2 = i_1 +/- ... */
1239 bool
1240 simple_iv_increment_p (gimple *stmt)
1242 enum tree_code code;
1243 tree lhs, preinc;
1244 gimple *phi;
1245 size_t i;
1247 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1248 return false;
1250 lhs = gimple_assign_lhs (stmt);
1251 if (TREE_CODE (lhs) != SSA_NAME)
1252 return false;
1254 code = gimple_assign_rhs_code (stmt);
1255 if (code != PLUS_EXPR
1256 && code != MINUS_EXPR
1257 && code != POINTER_PLUS_EXPR)
1258 return false;
1260 preinc = gimple_assign_rhs1 (stmt);
1261 if (TREE_CODE (preinc) != SSA_NAME)
1262 return false;
1264 phi = SSA_NAME_DEF_STMT (preinc);
1265 if (gimple_code (phi) != GIMPLE_PHI)
1266 return false;
1268 for (i = 0; i < gimple_phi_num_args (phi); i++)
1269 if (gimple_phi_arg_def (phi, i) == lhs)
1270 return true;
1272 return false;
1275 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1276 successors of BB. */
1278 static void
1279 cprop_into_successor_phis (basic_block bb,
1280 class const_and_copies *const_and_copies)
1282 edge e;
1283 edge_iterator ei;
1285 FOR_EACH_EDGE (e, ei, bb->succs)
1287 int indx;
1288 gphi_iterator gsi;
1290 /* If this is an abnormal edge, then we do not want to copy propagate
1291 into the PHI alternative associated with this edge. */
1292 if (e->flags & EDGE_ABNORMAL)
1293 continue;
1295 gsi = gsi_start_phis (e->dest);
1296 if (gsi_end_p (gsi))
1297 continue;
1299 /* We may have an equivalence associated with this edge. While
1300 we can not propagate it into non-dominated blocks, we can
1301 propagate them into PHIs in non-dominated blocks. */
1303 /* Push the unwind marker so we can reset the const and copies
1304 table back to its original state after processing this edge. */
1305 const_and_copies->push_marker ();
1307 /* Extract and record any simple NAME = VALUE equivalences.
1309 Don't bother with [01] = COND equivalences, they're not useful
1310 here. */
1311 struct edge_info *edge_info = (struct edge_info *) e->aux;
1312 if (edge_info)
1314 tree lhs = edge_info->lhs;
1315 tree rhs = edge_info->rhs;
1317 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1318 const_and_copies->record_const_or_copy (lhs, rhs);
1321 indx = e->dest_idx;
1322 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1324 tree new_val;
1325 use_operand_p orig_p;
1326 tree orig_val;
1327 gphi *phi = gsi.phi ();
1329 /* The alternative may be associated with a constant, so verify
1330 it is an SSA_NAME before doing anything with it. */
1331 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1332 orig_val = get_use_from_ptr (orig_p);
1333 if (TREE_CODE (orig_val) != SSA_NAME)
1334 continue;
1336 /* If we have *ORIG_P in our constant/copy table, then replace
1337 ORIG_P with its value in our constant/copy table. */
1338 new_val = SSA_NAME_VALUE (orig_val);
1339 if (new_val
1340 && new_val != orig_val
1341 && may_propagate_copy (orig_val, new_val))
1342 propagate_value (orig_p, new_val);
1345 const_and_copies->pop_to_marker ();
1349 edge
1350 dom_opt_dom_walker::before_dom_children (basic_block bb)
1352 gimple_stmt_iterator gsi;
1354 if (dump_file && (dump_flags & TDF_DETAILS))
1355 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
1357 /* Push a marker on the stacks of local information so that we know how
1358 far to unwind when we finalize this block. */
1359 m_avail_exprs_stack->push_marker ();
1360 m_const_and_copies->push_marker ();
1362 record_equivalences_from_incoming_edge (bb, m_const_and_copies,
1363 m_avail_exprs_stack);
1365 /* PHI nodes can create equivalences too. */
1366 record_equivalences_from_phis (bb);
1368 /* Create equivalences from redundant PHIs. PHIs are only truly
1369 redundant when they exist in the same block, so push another
1370 marker and unwind right afterwards. */
1371 m_avail_exprs_stack->push_marker ();
1372 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1373 eliminate_redundant_computations (&gsi, m_const_and_copies,
1374 m_avail_exprs_stack);
1375 m_avail_exprs_stack->pop_to_marker ();
1377 edge taken_edge = NULL;
1378 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1379 taken_edge
1380 = optimize_stmt (bb, gsi, m_const_and_copies, m_avail_exprs_stack);
1382 /* Now prepare to process dominated blocks. */
1383 record_edge_info (bb);
1384 cprop_into_successor_phis (bb, m_const_and_copies);
1385 if (taken_edge && !dbg_cnt (dom_unreachable_edges))
1386 return NULL;
1388 return taken_edge;
1391 /* We have finished processing the dominator children of BB, perform
1392 any finalization actions in preparation for leaving this node in
1393 the dominator tree. */
1395 void
1396 dom_opt_dom_walker::after_dom_children (basic_block bb)
1398 gimple *last;
1400 /* If we have an outgoing edge to a block with multiple incoming and
1401 outgoing edges, then we may be able to thread the edge, i.e., we
1402 may be able to statically determine which of the outgoing edges
1403 will be traversed when the incoming edge from BB is traversed. */
1404 if (single_succ_p (bb)
1405 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
1406 && potentially_threadable_block (single_succ (bb)))
1408 thread_across_edge (single_succ_edge (bb));
1410 else if ((last = last_stmt (bb))
1411 && gimple_code (last) == GIMPLE_COND
1412 && EDGE_COUNT (bb->succs) == 2
1413 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
1414 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
1416 edge true_edge, false_edge;
1418 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1420 /* Only try to thread the edge if it reaches a target block with
1421 more than one predecessor and more than one successor. */
1422 if (potentially_threadable_block (true_edge->dest))
1423 thread_across_edge (true_edge);
1425 /* Similarly for the ELSE arm. */
1426 if (potentially_threadable_block (false_edge->dest))
1427 thread_across_edge (false_edge);
1431 /* These remove expressions local to BB from the tables. */
1432 m_avail_exprs_stack->pop_to_marker ();
1433 m_const_and_copies->pop_to_marker ();
1436 /* Search for redundant computations in STMT. If any are found, then
1437 replace them with the variable holding the result of the computation.
1439 If safe, record this expression into AVAIL_EXPRS_STACK and
1440 CONST_AND_COPIES. */
1442 static void
1443 eliminate_redundant_computations (gimple_stmt_iterator* gsi,
1444 class const_and_copies *const_and_copies,
1445 class avail_exprs_stack *avail_exprs_stack)
1447 tree expr_type;
1448 tree cached_lhs;
1449 tree def;
1450 bool insert = true;
1451 bool assigns_var_p = false;
1453 gimple *stmt = gsi_stmt (*gsi);
1455 if (gimple_code (stmt) == GIMPLE_PHI)
1456 def = gimple_phi_result (stmt);
1457 else
1458 def = gimple_get_lhs (stmt);
1460 /* Certain expressions on the RHS can be optimized away, but can not
1461 themselves be entered into the hash tables. */
1462 if (! def
1463 || TREE_CODE (def) != SSA_NAME
1464 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1465 || gimple_vdef (stmt)
1466 /* Do not record equivalences for increments of ivs. This would create
1467 overlapping live ranges for a very questionable gain. */
1468 || simple_iv_increment_p (stmt))
1469 insert = false;
1471 /* Check if the expression has been computed before. */
1472 cached_lhs = lookup_avail_expr (stmt, insert, avail_exprs_stack);
1474 opt_stats.num_exprs_considered++;
1476 /* Get the type of the expression we are trying to optimize. */
1477 if (is_gimple_assign (stmt))
1479 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1480 assigns_var_p = true;
1482 else if (gimple_code (stmt) == GIMPLE_COND)
1483 expr_type = boolean_type_node;
1484 else if (is_gimple_call (stmt))
1486 gcc_assert (gimple_call_lhs (stmt));
1487 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1488 assigns_var_p = true;
1490 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1491 expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt));
1492 else if (gimple_code (stmt) == GIMPLE_PHI)
1493 /* We can't propagate into a phi, so the logic below doesn't apply.
1494 Instead record an equivalence between the cached LHS and the
1495 PHI result of this statement, provided they are in the same block.
1496 This should be sufficient to kill the redundant phi. */
1498 if (def && cached_lhs)
1499 const_and_copies->record_const_or_copy (def, cached_lhs);
1500 return;
1502 else
1503 gcc_unreachable ();
1505 if (!cached_lhs)
1506 return;
1508 /* It is safe to ignore types here since we have already done
1509 type checking in the hashing and equality routines. In fact
1510 type checking here merely gets in the way of constant
1511 propagation. Also, make sure that it is safe to propagate
1512 CACHED_LHS into the expression in STMT. */
1513 if ((TREE_CODE (cached_lhs) != SSA_NAME
1514 && (assigns_var_p
1515 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1516 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1518 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
1519 || is_gimple_min_invariant (cached_lhs));
1521 if (dump_file && (dump_flags & TDF_DETAILS))
1523 fprintf (dump_file, " Replaced redundant expr '");
1524 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1525 fprintf (dump_file, "' with '");
1526 print_generic_expr (dump_file, cached_lhs, dump_flags);
1527 fprintf (dump_file, "'\n");
1530 opt_stats.num_re++;
1532 if (assigns_var_p
1533 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1534 cached_lhs = fold_convert (expr_type, cached_lhs);
1536 propagate_tree_value_into_stmt (gsi, cached_lhs);
1538 /* Since it is always necessary to mark the result as modified,
1539 perhaps we should move this into propagate_tree_value_into_stmt
1540 itself. */
1541 gimple_set_modified (gsi_stmt (*gsi), true);
1545 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1546 the available expressions table or the const_and_copies table.
1547 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1549 We handle only very simple copy equivalences here. The heavy
1550 lifing is done by eliminate_redundant_computations. */
1552 static void
1553 record_equivalences_from_stmt (gimple *stmt, int may_optimize_p,
1554 class avail_exprs_stack *avail_exprs_stack)
1556 tree lhs;
1557 enum tree_code lhs_code;
1559 gcc_assert (is_gimple_assign (stmt));
1561 lhs = gimple_assign_lhs (stmt);
1562 lhs_code = TREE_CODE (lhs);
1564 if (lhs_code == SSA_NAME
1565 && gimple_assign_single_p (stmt))
1567 tree rhs = gimple_assign_rhs1 (stmt);
1569 /* If the RHS of the assignment is a constant or another variable that
1570 may be propagated, register it in the CONST_AND_COPIES table. We
1571 do not need to record unwind data for this, since this is a true
1572 assignment and not an equivalence inferred from a comparison. All
1573 uses of this ssa name are dominated by this assignment, so unwinding
1574 just costs time and space. */
1575 if (may_optimize_p
1576 && (TREE_CODE (rhs) == SSA_NAME
1577 || is_gimple_min_invariant (rhs)))
1579 rhs = dom_valueize (rhs);
1581 if (dump_file && (dump_flags & TDF_DETAILS))
1583 fprintf (dump_file, "==== ASGN ");
1584 print_generic_expr (dump_file, lhs, 0);
1585 fprintf (dump_file, " = ");
1586 print_generic_expr (dump_file, rhs, 0);
1587 fprintf (dump_file, "\n");
1590 set_ssa_name_value (lhs, rhs);
1594 /* Make sure we can propagate &x + CST. */
1595 if (lhs_code == SSA_NAME
1596 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
1597 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR
1598 && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
1600 tree op0 = gimple_assign_rhs1 (stmt);
1601 tree op1 = gimple_assign_rhs2 (stmt);
1602 tree new_rhs
1603 = build_fold_addr_expr (fold_build2 (MEM_REF,
1604 TREE_TYPE (TREE_TYPE (op0)),
1605 unshare_expr (op0),
1606 fold_convert (ptr_type_node,
1607 op1)));
1608 if (dump_file && (dump_flags & TDF_DETAILS))
1610 fprintf (dump_file, "==== ASGN ");
1611 print_generic_expr (dump_file, lhs, 0);
1612 fprintf (dump_file, " = ");
1613 print_generic_expr (dump_file, new_rhs, 0);
1614 fprintf (dump_file, "\n");
1617 set_ssa_name_value (lhs, new_rhs);
1620 /* A memory store, even an aliased store, creates a useful
1621 equivalence. By exchanging the LHS and RHS, creating suitable
1622 vops and recording the result in the available expression table,
1623 we may be able to expose more redundant loads. */
1624 if (!gimple_has_volatile_ops (stmt)
1625 && gimple_references_memory_p (stmt)
1626 && gimple_assign_single_p (stmt)
1627 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1628 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1629 && !is_gimple_reg (lhs))
1631 tree rhs = gimple_assign_rhs1 (stmt);
1632 gassign *new_stmt;
1634 /* Build a new statement with the RHS and LHS exchanged. */
1635 if (TREE_CODE (rhs) == SSA_NAME)
1637 /* NOTE tuples. The call to gimple_build_assign below replaced
1638 a call to build_gimple_modify_stmt, which did not set the
1639 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1640 may cause an SSA validation failure, as the LHS may be a
1641 default-initialized name and should have no definition. I'm
1642 a bit dubious of this, as the artificial statement that we
1643 generate here may in fact be ill-formed, but it is simply
1644 used as an internal device in this pass, and never becomes
1645 part of the CFG. */
1646 gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
1647 new_stmt = gimple_build_assign (rhs, lhs);
1648 SSA_NAME_DEF_STMT (rhs) = defstmt;
1650 else
1651 new_stmt = gimple_build_assign (rhs, lhs);
1653 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1655 /* Finally enter the statement into the available expression
1656 table. */
1657 lookup_avail_expr (new_stmt, true, avail_exprs_stack);
1661 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1662 CONST_AND_COPIES. */
1664 static void
1665 cprop_operand (gimple *stmt, use_operand_p op_p)
1667 tree val;
1668 tree op = USE_FROM_PTR (op_p);
1670 /* If the operand has a known constant value or it is known to be a
1671 copy of some other variable, use the value or copy stored in
1672 CONST_AND_COPIES. */
1673 val = SSA_NAME_VALUE (op);
1674 if (val && val != op)
1676 /* Do not replace hard register operands in asm statements. */
1677 if (gimple_code (stmt) == GIMPLE_ASM
1678 && !may_propagate_copy_into_asm (op))
1679 return;
1681 /* Certain operands are not allowed to be copy propagated due
1682 to their interaction with exception handling and some GCC
1683 extensions. */
1684 if (!may_propagate_copy (op, val))
1685 return;
1687 /* Do not propagate copies into BIVs.
1688 See PR23821 and PR62217 for how this can disturb IV and
1689 number of iteration analysis. */
1690 if (TREE_CODE (val) != INTEGER_CST)
1692 gimple *def = SSA_NAME_DEF_STMT (op);
1693 if (gimple_code (def) == GIMPLE_PHI
1694 && gimple_bb (def)->loop_father->header == gimple_bb (def))
1695 return;
1698 /* Dump details. */
1699 if (dump_file && (dump_flags & TDF_DETAILS))
1701 fprintf (dump_file, " Replaced '");
1702 print_generic_expr (dump_file, op, dump_flags);
1703 fprintf (dump_file, "' with %s '",
1704 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
1705 print_generic_expr (dump_file, val, dump_flags);
1706 fprintf (dump_file, "'\n");
1709 if (TREE_CODE (val) != SSA_NAME)
1710 opt_stats.num_const_prop++;
1711 else
1712 opt_stats.num_copy_prop++;
1714 propagate_value (op_p, val);
1716 /* And note that we modified this statement. This is now
1717 safe, even if we changed virtual operands since we will
1718 rescan the statement and rewrite its operands again. */
1719 gimple_set_modified (stmt, true);
1723 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1724 known value for that SSA_NAME (or NULL if no value is known).
1726 Propagate values from CONST_AND_COPIES into the uses, vuses and
1727 vdef_ops of STMT. */
1729 static void
1730 cprop_into_stmt (gimple *stmt)
1732 use_operand_p op_p;
1733 ssa_op_iter iter;
1735 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
1736 cprop_operand (stmt, op_p);
1739 /* Optimize the statement in block BB pointed to by iterator SI
1740 using equivalences from CONST_AND_COPIES and AVAIL_EXPRS_STACK.
1742 We try to perform some simplistic global redundancy elimination and
1743 constant propagation:
1745 1- To detect global redundancy, we keep track of expressions that have
1746 been computed in this block and its dominators. If we find that the
1747 same expression is computed more than once, we eliminate repeated
1748 computations by using the target of the first one.
1750 2- Constant values and copy assignments. This is used to do very
1751 simplistic constant and copy propagation. When a constant or copy
1752 assignment is found, we map the value on the RHS of the assignment to
1753 the variable in the LHS in the CONST_AND_COPIES table. */
1755 static edge
1756 optimize_stmt (basic_block bb, gimple_stmt_iterator si,
1757 class const_and_copies *const_and_copies,
1758 class avail_exprs_stack *avail_exprs_stack)
1760 gimple *stmt, *old_stmt;
1761 bool may_optimize_p;
1762 bool modified_p = false;
1763 bool was_noreturn;
1764 edge retval = NULL;
1766 old_stmt = stmt = gsi_stmt (si);
1767 was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
1769 if (dump_file && (dump_flags & TDF_DETAILS))
1771 fprintf (dump_file, "Optimizing statement ");
1772 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1775 if (gimple_code (stmt) == GIMPLE_COND)
1776 canonicalize_comparison (as_a <gcond *> (stmt));
1778 update_stmt_if_modified (stmt);
1779 opt_stats.num_stmts++;
1781 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1782 cprop_into_stmt (stmt);
1784 /* If the statement has been modified with constant replacements,
1785 fold its RHS before checking for redundant computations. */
1786 if (gimple_modified_p (stmt))
1788 tree rhs = NULL;
1790 /* Try to fold the statement making sure that STMT is kept
1791 up to date. */
1792 if (fold_stmt (&si))
1794 stmt = gsi_stmt (si);
1795 gimple_set_modified (stmt, true);
1797 if (dump_file && (dump_flags & TDF_DETAILS))
1799 fprintf (dump_file, " Folded to: ");
1800 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1804 /* We only need to consider cases that can yield a gimple operand. */
1805 if (gimple_assign_single_p (stmt))
1806 rhs = gimple_assign_rhs1 (stmt);
1807 else if (gimple_code (stmt) == GIMPLE_GOTO)
1808 rhs = gimple_goto_dest (stmt);
1809 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1810 /* This should never be an ADDR_EXPR. */
1811 rhs = gimple_switch_index (swtch_stmt);
1813 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
1814 recompute_tree_invariant_for_addr_expr (rhs);
1816 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1817 even if fold_stmt updated the stmt already and thus cleared
1818 gimple_modified_p flag on it. */
1819 modified_p = true;
1822 /* Check for redundant computations. Do this optimization only
1823 for assignments that have no volatile ops and conditionals. */
1824 may_optimize_p = (!gimple_has_side_effects (stmt)
1825 && (is_gimple_assign (stmt)
1826 || (is_gimple_call (stmt)
1827 && gimple_call_lhs (stmt) != NULL_TREE)
1828 || gimple_code (stmt) == GIMPLE_COND
1829 || gimple_code (stmt) == GIMPLE_SWITCH));
1831 if (may_optimize_p)
1833 if (gimple_code (stmt) == GIMPLE_CALL)
1835 /* Resolve __builtin_constant_p. If it hasn't been
1836 folded to integer_one_node by now, it's fairly
1837 certain that the value simply isn't constant. */
1838 tree callee = gimple_call_fndecl (stmt);
1839 if (callee
1840 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
1841 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P)
1843 propagate_tree_value_into_stmt (&si, integer_zero_node);
1844 stmt = gsi_stmt (si);
1848 if (gimple_code (stmt) == GIMPLE_COND)
1850 tree lhs = gimple_cond_lhs (stmt);
1851 tree rhs = gimple_cond_rhs (stmt);
1853 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
1854 then this conditional is computable at compile time. We can just
1855 shove either 0 or 1 into the LHS, mark the statement as modified
1856 and all the right things will just happen below.
1858 Note this would apply to any case where LHS has a range
1859 narrower than its type implies and RHS is outside that
1860 narrower range. Future work. */
1861 if (TREE_CODE (lhs) == SSA_NAME
1862 && ssa_name_has_boolean_range (lhs)
1863 && TREE_CODE (rhs) == INTEGER_CST
1864 && ! (integer_zerop (rhs) || integer_onep (rhs)))
1866 gimple_cond_set_lhs (as_a <gcond *> (stmt),
1867 fold_convert (TREE_TYPE (lhs),
1868 integer_zero_node));
1869 gimple_set_modified (stmt, true);
1873 update_stmt_if_modified (stmt);
1874 eliminate_redundant_computations (&si, const_and_copies,
1875 avail_exprs_stack);
1876 stmt = gsi_stmt (si);
1878 /* Perform simple redundant store elimination. */
1879 if (gimple_assign_single_p (stmt)
1880 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
1882 tree lhs = gimple_assign_lhs (stmt);
1883 tree rhs = gimple_assign_rhs1 (stmt);
1884 tree cached_lhs;
1885 gassign *new_stmt;
1886 rhs = dom_valueize (rhs);
1887 /* Build a new statement with the RHS and LHS exchanged. */
1888 if (TREE_CODE (rhs) == SSA_NAME)
1890 gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
1891 new_stmt = gimple_build_assign (rhs, lhs);
1892 SSA_NAME_DEF_STMT (rhs) = defstmt;
1894 else
1895 new_stmt = gimple_build_assign (rhs, lhs);
1896 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
1897 cached_lhs = lookup_avail_expr (new_stmt, false, avail_exprs_stack,
1898 false);
1899 if (cached_lhs
1900 && rhs == cached_lhs)
1902 basic_block bb = gimple_bb (stmt);
1903 unlink_stmt_vdef (stmt);
1904 if (gsi_remove (&si, true))
1906 bitmap_set_bit (need_eh_cleanup, bb->index);
1907 if (dump_file && (dump_flags & TDF_DETAILS))
1908 fprintf (dump_file, " Flagged to clear EH edges.\n");
1910 release_defs (stmt);
1911 return retval;
1916 /* Record any additional equivalences created by this statement. */
1917 if (is_gimple_assign (stmt))
1918 record_equivalences_from_stmt (stmt, may_optimize_p, avail_exprs_stack);
1920 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
1921 know where it goes. */
1922 if (gimple_modified_p (stmt) || modified_p)
1924 tree val = NULL;
1926 update_stmt_if_modified (stmt);
1928 if (gimple_code (stmt) == GIMPLE_COND)
1929 val = fold_binary_loc (gimple_location (stmt),
1930 gimple_cond_code (stmt), boolean_type_node,
1931 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
1932 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1933 val = gimple_switch_index (swtch_stmt);
1935 if (val && TREE_CODE (val) == INTEGER_CST)
1937 retval = find_taken_edge (bb, val);
1938 if (retval)
1940 /* Fix the condition to be either true or false. */
1941 if (gimple_code (stmt) == GIMPLE_COND)
1943 if (integer_zerop (val))
1944 gimple_cond_make_false (as_a <gcond *> (stmt));
1945 else if (integer_onep (val))
1946 gimple_cond_make_true (as_a <gcond *> (stmt));
1947 else
1948 gcc_unreachable ();
1951 /* Further simplifications may be possible. */
1952 cfg_altered = true;
1956 /* If we simplified a statement in such a way as to be shown that it
1957 cannot trap, update the eh information and the cfg to match. */
1958 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1960 bitmap_set_bit (need_eh_cleanup, bb->index);
1961 if (dump_file && (dump_flags & TDF_DETAILS))
1962 fprintf (dump_file, " Flagged to clear EH edges.\n");
1965 if (!was_noreturn
1966 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
1967 need_noreturn_fixup.safe_push (stmt);
1969 return retval;
1972 /* Helper for walk_non_aliased_vuses. Determine if we arrived at
1973 the desired memory state. */
1975 static void *
1976 vuse_eq (ao_ref *, tree vuse1, unsigned int cnt, void *data)
1978 tree vuse2 = (tree) data;
1979 if (vuse1 == vuse2)
1980 return data;
1982 /* This bounds the stmt walks we perform on reference lookups
1983 to O(1) instead of O(N) where N is the number of dominating
1984 stores leading to a candidate. We re-use the SCCVN param
1985 for this as it is basically the same complexity. */
1986 if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
1987 return (void *)-1;
1989 return NULL;
1992 /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
1993 If found, return its LHS. Otherwise insert STMT in the table and
1994 return NULL_TREE.
1996 Also, when an expression is first inserted in the table, it is also
1997 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
1998 we finish processing this block and its children. */
2000 static tree
2001 lookup_avail_expr (gimple *stmt, bool insert,
2002 class avail_exprs_stack *avail_exprs_stack, bool tbaa_p)
2004 expr_hash_elt **slot;
2005 tree lhs;
2007 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
2008 if (gimple_code (stmt) == GIMPLE_PHI)
2009 lhs = gimple_phi_result (stmt);
2010 else
2011 lhs = gimple_get_lhs (stmt);
2013 class expr_hash_elt element (stmt, lhs);
2015 if (dump_file && (dump_flags & TDF_DETAILS))
2017 fprintf (dump_file, "LKUP ");
2018 element.print (dump_file);
2021 /* Don't bother remembering constant assignments and copy operations.
2022 Constants and copy operations are handled by the constant/copy propagator
2023 in optimize_stmt. */
2024 if (element.expr()->kind == EXPR_SINGLE
2025 && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME
2026 || is_gimple_min_invariant (element.expr()->ops.single.rhs)))
2027 return NULL_TREE;
2029 /* Finally try to find the expression in the main expression hash table. */
2030 hash_table<expr_elt_hasher> *avail_exprs = avail_exprs_stack->avail_exprs ();
2031 slot = avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
2032 if (slot == NULL)
2034 return NULL_TREE;
2036 else if (*slot == NULL)
2038 class expr_hash_elt *element2 = new expr_hash_elt (element);
2039 *slot = element2;
2041 avail_exprs_stack->record_expr (element2, NULL, '2');
2042 return NULL_TREE;
2045 /* If we found a redundant memory operation do an alias walk to
2046 check if we can re-use it. */
2047 if (gimple_vuse (stmt) != (*slot)->vop ())
2049 tree vuse1 = (*slot)->vop ();
2050 tree vuse2 = gimple_vuse (stmt);
2051 /* If we have a load of a register and a candidate in the
2052 hash with vuse1 then try to reach its stmt by walking
2053 up the virtual use-def chain using walk_non_aliased_vuses.
2054 But don't do this when removing expressions from the hash. */
2055 ao_ref ref;
2056 if (!(vuse1 && vuse2
2057 && gimple_assign_single_p (stmt)
2058 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
2059 && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)),
2060 ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true)
2061 && walk_non_aliased_vuses (&ref, vuse2,
2062 vuse_eq, NULL, NULL, vuse1) != NULL))
2064 if (insert)
2066 class expr_hash_elt *element2 = new expr_hash_elt (element);
2068 /* Insert the expr into the hash by replacing the current
2069 entry and recording the value to restore in the
2070 avail_exprs_stack. */
2071 avail_exprs_stack->record_expr (element2, *slot, '2');
2072 *slot = element2;
2074 return NULL_TREE;
2078 /* Extract the LHS of the assignment so that it can be used as the current
2079 definition of another variable. */
2080 lhs = (*slot)->lhs ();
2082 lhs = dom_valueize (lhs);
2084 if (dump_file && (dump_flags & TDF_DETAILS))
2086 fprintf (dump_file, "FIND: ");
2087 print_generic_expr (dump_file, lhs, 0);
2088 fprintf (dump_file, "\n");
2091 return lhs;