1/* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
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 "tree-inline.h"
36#include "gimple-iterator.h"
37#include "tree-cfg.h"
38#include "tree-into-ssa.h"
39#include "domwalk.h"
40#include "tree-ssa-propagate.h"
41#include "tree-ssa-threadupdate.h"
42#include "params.h"
43#include "tree-ssa-scopedtables.h"
44#include "tree-ssa-threadedge.h"
45#include "tree-ssa-dom.h"
46#include "gimplify.h"
47#include "tree-cfgcleanup.h"
48#include "dbgcnt.h"
49#include "alloc-pool.h"
50#include "tree-vrp.h"
51#include "vr-values.h"
52#include "gimple-ssa-evrp-analyze.h"
53
54/* This file implements optimizations on the dominator tree. */
55
56/* Structure for recording edge equivalences.
57
58 Computing and storing the edge equivalences instead of creating
59 them on-demand can save significant amounts of time, particularly
60 for pathological cases involving switch statements.
61
62 These structures live for a single iteration of the dominator
63 optimizer in the edge's AUX field. At the end of an iteration we
64 free each of these structures. */
65class edge_info
66{
67 public:
68 typedef std::pair <tree, tree> equiv_pair;
69 edge_info (edge);
70 ~edge_info ();
71
72 /* Record a simple LHS = RHS equivalence. This may trigger
73 calls to derive_equivalences. */
74 void record_simple_equiv (tree, tree);
75
76 /* If traversing this edge creates simple equivalences, we store
77 them as LHS/RHS pairs within this vector. */
78 vec<equiv_pair> simple_equivalences;
79
80 /* Traversing an edge may also indicate one or more particular conditions
81 are true or false. */
82 vec<cond_equivalence> cond_equivalences;
83
84 private:
85 /* Derive equivalences by walking the use-def chains. */
86 void derive_equivalences (tree, tree, int);
87};
88
89/* Track whether or not we have changed the control flow graph. */
90static bool cfg_altered;
91
92/* Bitmap of blocks that have had EH statements cleaned. We should
93 remove their dead edges eventually. */
94static bitmap need_eh_cleanup;
95static vec<gimple *> need_noreturn_fixup;
96
97/* Statistics for dominator optimizations. */
98struct opt_stats_d
99{
100 long num_stmts;
101 long num_exprs_considered;
102 long num_re;
103 long num_const_prop;
104 long num_copy_prop;
105};
106
107static struct opt_stats_d opt_stats;
108
109/* Local functions. */
110static void record_equality (tree, tree, class const_and_copies *);
111static void record_equivalences_from_phis (basic_block);
112static void record_equivalences_from_incoming_edge (basic_block,
113 class const_and_copies *,
114 class avail_exprs_stack *);
115static void eliminate_redundant_computations (gimple_stmt_iterator *,
116 class const_and_copies *,
117 class avail_exprs_stack *);
118static void record_equivalences_from_stmt (gimple *, int,
119 class avail_exprs_stack *);
120static void dump_dominator_optimization_stats (FILE *file,
121 hash_table<expr_elt_hasher> *);
122
123/* Constructor for EDGE_INFO. An EDGE_INFO instance is always
124 associated with an edge E. */
125
126edge_info::edge_info (edge e)
127{
128 /* Free the old one associated with E, if it exists and
129 associate our new object with E. */
130 free_dom_edge_info (e);
131 e->aux = this;
132
133 /* And initialize the embedded vectors. */
134 simple_equivalences = vNULL;
135 cond_equivalences = vNULL;
136}
137
138/* Destructor just needs to release the vectors. */
139
140edge_info::~edge_info (void)
141{
142 this->cond_equivalences.release ();
143 this->simple_equivalences.release ();
144}
145
146/* NAME is known to have the value VALUE, which must be a constant.
147
148 Walk through its use-def chain to see if there are other equivalences
149 we might be able to derive.
150
151 RECURSION_LIMIT controls how far back we recurse through the use-def
152 chains. */
153
154void
155edge_info::derive_equivalences (tree name, tree value, int recursion_limit)
156{
157 if (TREE_CODE (name) != SSA_NAME || TREE_CODE (value) != INTEGER_CST)
158 return;
159
160 /* This records the equivalence for the toplevel object. Do
161 this before checking the recursion limit. */
162 simple_equivalences.safe_push (equiv_pair (name, value));
163
164 /* Limit how far up the use-def chains we are willing to walk. */
165 if (recursion_limit == 0)
166 return;
167
168 /* We can walk up the use-def chains to potentially find more
169 equivalences. */
170 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
171 if (is_gimple_assign (def_stmt))
172 {
173 /* We know the result of DEF_STMT was zero. See if that allows
174 us to deduce anything about the SSA_NAMEs used on the RHS. */
175 enum tree_code code = gimple_assign_rhs_code (def_stmt);
176 switch (code)
177 {
178 case BIT_IOR_EXPR:
179 if (integer_zerop (value))
180 {
181 tree rhs1 = gimple_assign_rhs1 (def_stmt);
182 tree rhs2 = gimple_assign_rhs2 (def_stmt);
183
184 value = build_zero_cst (TREE_TYPE (rhs1));
185 derive_equivalences (rhs1, value, recursion_limit - 1);
186 value = build_zero_cst (TREE_TYPE (rhs2));
187 derive_equivalences (rhs2, value, recursion_limit - 1);
188 }
189 break;
190
191 /* We know the result of DEF_STMT was one. See if that allows
192 us to deduce anything about the SSA_NAMEs used on the RHS. */
193 case BIT_AND_EXPR:
194 if (!integer_zerop (value))
195 {
196 tree rhs1 = gimple_assign_rhs1 (def_stmt);
197 tree rhs2 = gimple_assign_rhs2 (def_stmt);
198
199 /* If either operand has a boolean range, then we
200 know its value must be one, otherwise we just know it
201 is nonzero. The former is clearly useful, I haven't
202 seen cases where the latter is helpful yet. */
203 if (TREE_CODE (rhs1) == SSA_NAME)
204 {
205 if (ssa_name_has_boolean_range (rhs1))
206 {
207 value = build_one_cst (TREE_TYPE (rhs1));
208 derive_equivalences (rhs1, value, recursion_limit - 1);
209 }
210 }
211 if (TREE_CODE (rhs2) == SSA_NAME)
212 {
213 if (ssa_name_has_boolean_range (rhs2))
214 {
215 value = build_one_cst (TREE_TYPE (rhs2));
216 derive_equivalences (rhs2, value, recursion_limit - 1);
217 }
218 }
219 }
220 break;
221
222 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
223 set via a widening type conversion, then we may be able to record
224 additional equivalences. */
225 case NOP_EXPR:
226 case CONVERT_EXPR:
227 {
228 tree rhs = gimple_assign_rhs1 (def_stmt);
229 tree rhs_type = TREE_TYPE (rhs);
230 if (INTEGRAL_TYPE_P (rhs_type)
231 && (TYPE_PRECISION (TREE_TYPE (name))
232 >= TYPE_PRECISION (rhs_type))
233 && int_fits_type_p (value, rhs_type))
234 derive_equivalences (rhs,
235 fold_convert (rhs_type, value),
236 recursion_limit - 1);
237 break;
238 }
239
240 /* We can invert the operation of these codes trivially if
241 one of the RHS operands is a constant to produce a known
242 value for the other RHS operand. */
243 case POINTER_PLUS_EXPR:
244 case PLUS_EXPR:
245 {
246 tree rhs1 = gimple_assign_rhs1 (def_stmt);
247 tree rhs2 = gimple_assign_rhs2 (def_stmt);
248
249 /* If either argument is a constant, then we can compute
250 a constant value for the nonconstant argument. */
251 if (TREE_CODE (rhs1) == INTEGER_CST
252 && TREE_CODE (rhs2) == SSA_NAME)
253 derive_equivalences (rhs2,
254 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
255 value, rhs1),
256 recursion_limit - 1);
257 else if (TREE_CODE (rhs2) == INTEGER_CST
258 && TREE_CODE (rhs1) == SSA_NAME)
259 derive_equivalences (rhs1,
260 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
261 value, rhs2),
262 recursion_limit - 1);
263 break;
264 }
265
266 /* If one of the operands is a constant, then we can compute
267 the value of the other operand. If both operands are
268 SSA_NAMEs, then they must be equal if the result is zero. */
269 case MINUS_EXPR:
270 {
271 tree rhs1 = gimple_assign_rhs1 (def_stmt);
272 tree rhs2 = gimple_assign_rhs2 (def_stmt);
273
274 /* If either argument is a constant, then we can compute
275 a constant value for the nonconstant argument. */
276 if (TREE_CODE (rhs1) == INTEGER_CST
277 && TREE_CODE (rhs2) == SSA_NAME)
278 derive_equivalences (rhs2,
279 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
280 rhs1, value),
281 recursion_limit - 1);
282 else if (TREE_CODE (rhs2) == INTEGER_CST
283 && TREE_CODE (rhs1) == SSA_NAME)
284 derive_equivalences (rhs1,
285 fold_binary (PLUS_EXPR, TREE_TYPE (rhs1),
286 value, rhs2),
287 recursion_limit - 1);
288 else if (integer_zerop (value))
289 {
290 tree cond = build2 (EQ_EXPR, boolean_type_node,
291 gimple_assign_rhs1 (def_stmt),
292 gimple_assign_rhs2 (def_stmt));
293 tree inverted = invert_truthvalue (cond);
294 record_conditions (&this->cond_equivalences, cond, inverted);
295 }
296 break;
297 }
298
299
300 case EQ_EXPR:
301 case NE_EXPR:
302 {
303 if ((code == EQ_EXPR && integer_onep (value))
304 || (code == NE_EXPR && integer_zerop (value)))
305 {
306 tree rhs1 = gimple_assign_rhs1 (def_stmt);
307 tree rhs2 = gimple_assign_rhs2 (def_stmt);
308
309 /* If either argument is a constant, then record the
310 other argument as being the same as that constant.
311
312 If neither operand is a constant, then we have a
313 conditional name == name equivalence. */
314 if (TREE_CODE (rhs1) == INTEGER_CST)
315 derive_equivalences (rhs2, rhs1, recursion_limit - 1);
316 else if (TREE_CODE (rhs2) == INTEGER_CST)
317 derive_equivalences (rhs1, rhs2, recursion_limit - 1);
318 }
319 else
320 {
321 tree cond = build2 (code, boolean_type_node,
322 gimple_assign_rhs1 (def_stmt),
323 gimple_assign_rhs2 (def_stmt));
324 tree inverted = invert_truthvalue (cond);
325 if (integer_zerop (value))
326 std::swap (cond, inverted);
327 record_conditions (&this->cond_equivalences, cond, inverted);
328 }
329 break;
330 }
331
332 /* For BIT_NOT and NEGATE, we can just apply the operation to the
333 VALUE to get the new equivalence. It will always be a constant
334 so we can recurse. */
335 case BIT_NOT_EXPR:
336 case NEGATE_EXPR:
337 {
338 tree rhs = gimple_assign_rhs1 (def_stmt);
339 tree res = fold_build1 (code, TREE_TYPE (rhs), value);
340 derive_equivalences (rhs, res, recursion_limit - 1);
341 break;
342 }
343
344 default:
345 {
346 if (TREE_CODE_CLASS (code) == tcc_comparison)
347 {
348 tree cond = build2 (code, boolean_type_node,
349 gimple_assign_rhs1 (def_stmt),
350 gimple_assign_rhs2 (def_stmt));
351 tree inverted = invert_truthvalue (cond);
352 if (integer_zerop (value))
353 std::swap (cond, inverted);
354 record_conditions (&this->cond_equivalences, cond, inverted);
355 break;
356 }
357 break;
358 }
359 }
360 }
361}
362
363void
364edge_info::record_simple_equiv (tree lhs, tree rhs)
365{
366 /* If the RHS is a constant, then we may be able to derive
367 further equivalences. Else just record the name = name
368 equivalence. */
369 if (TREE_CODE (rhs) == INTEGER_CST)
370 derive_equivalences (lhs, rhs, 4);
371 else
372 simple_equivalences.safe_push (equiv_pair (lhs, rhs));
373}
374
375/* Free the edge_info data attached to E, if it exists. */
376
377void
378free_dom_edge_info (edge e)
379{
380 class edge_info *edge_info = (struct edge_info *)e->aux;
381
382 if (edge_info)
383 delete edge_info;
384}
385
386/* Free all EDGE_INFO structures associated with edges in the CFG.
387 If a particular edge can be threaded, copy the redirection
388 target from the EDGE_INFO structure into the edge's AUX field
389 as required by code to update the CFG and SSA graph for
390 jump threading. */
391
392static void
393free_all_edge_infos (void)
394{
395 basic_block bb;
396 edge_iterator ei;
397 edge e;
398
399 FOR_EACH_BB_FN (bb, cfun)
400 {
401 FOR_EACH_EDGE (e, ei, bb->preds)
402 {
403 free_dom_edge_info (e);
404 e->aux = NULL;
405 }
406 }
407}
408
409/* We have finished optimizing BB, record any information implied by
410 taking a specific outgoing edge from BB. */
411
412static void
413record_edge_info (basic_block bb)
414{
415 gimple_stmt_iterator gsi = gsi_last_bb (bb);
416 class edge_info *edge_info;
417
418 if (! gsi_end_p (gsi))
419 {
420 gimple *stmt = gsi_stmt (gsi);
421 location_t loc = gimple_location (stmt);
422
423 if (gimple_code (stmt) == GIMPLE_SWITCH)
424 {
425 gswitch *switch_stmt = as_a <gswitch *> (stmt);
426 tree index = gimple_switch_index (switch_stmt);
427
428 if (TREE_CODE (index) == SSA_NAME)
429 {
430 int i;
431 int n_labels = gimple_switch_num_labels (switch_stmt);
432 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
433 edge e;
434 edge_iterator ei;
435
436 for (i = 0; i < n_labels; i++)
437 {
438 tree label = gimple_switch_label (switch_stmt, i);
439 basic_block target_bb = label_to_block (CASE_LABEL (label));
440 if (CASE_HIGH (label)
441 || !CASE_LOW (label)
442 || info[target_bb->index])
443 info[target_bb->index] = error_mark_node;
444 else
445 info[target_bb->index] = label;
446 }
447
448 FOR_EACH_EDGE (e, ei, bb->succs)
449 {
450 basic_block target_bb = e->dest;
451 tree label = info[target_bb->index];
452
453 if (label != NULL && label != error_mark_node)
454 {
455 tree x = fold_convert_loc (loc, TREE_TYPE (index),
456 CASE_LOW (label));
457 edge_info = new class edge_info (e);
458 edge_info->record_simple_equiv (index, x);
459 }
460 }
461 free (info);
462 }
463 }
464
465 /* A COND_EXPR may create equivalences too. */
466 if (gimple_code (stmt) == GIMPLE_COND)
467 {
468 edge true_edge;
469 edge false_edge;
470
471 tree op0 = gimple_cond_lhs (stmt);
472 tree op1 = gimple_cond_rhs (stmt);
473 enum tree_code code = gimple_cond_code (stmt);
474
475 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
476
477 /* Special case comparing booleans against a constant as we
478 know the value of OP0 on both arms of the branch. i.e., we
479 can record an equivalence for OP0 rather than COND.
480
481 However, don't do this if the constant isn't zero or one.
482 Such conditionals will get optimized more thoroughly during
483 the domwalk. */
484 if ((code == EQ_EXPR || code == NE_EXPR)
485 && TREE_CODE (op0) == SSA_NAME
486 && ssa_name_has_boolean_range (op0)
487 && is_gimple_min_invariant (op1)
488 && (integer_zerop (op1) || integer_onep (op1)))
489 {
490 tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
491 tree false_val = constant_boolean_node (false, TREE_TYPE (op0));
492
493 if (code == EQ_EXPR)
494 {
495 edge_info = new class edge_info (true_edge);
496 edge_info->record_simple_equiv (op0,
497 (integer_zerop (op1)
498 ? false_val : true_val));
499 edge_info = new class edge_info (false_edge);
500 edge_info->record_simple_equiv (op0,
501 (integer_zerop (op1)
502 ? true_val : false_val));
503 }
504 else
505 {
506 edge_info = new class edge_info (true_edge);
507 edge_info->record_simple_equiv (op0,
508 (integer_zerop (op1)
509 ? true_val : false_val));
510 edge_info = new class edge_info (false_edge);
511 edge_info->record_simple_equiv (op0,
512 (integer_zerop (op1)
513 ? false_val : true_val));
514 }
515 }
516 /* This can show up in the IL as a result of copy propagation
517 it will eventually be canonicalized, but we have to cope
518 with this case within the pass. */
519 else if (is_gimple_min_invariant (op0)
520 && TREE_CODE (op1) == SSA_NAME)
521 {
522 tree cond = build2 (code, boolean_type_node, op0, op1);
523 tree inverted = invert_truthvalue_loc (loc, cond);
524 bool can_infer_simple_equiv
525 = !(HONOR_SIGNED_ZEROS (op0)
526 && real_zerop (op0));
527 struct edge_info *edge_info;
528
529 edge_info = new class edge_info (true_edge);
530 record_conditions (&edge_info->cond_equivalences, cond, inverted);
531
532 if (can_infer_simple_equiv && code == EQ_EXPR)
533 edge_info->record_simple_equiv (op1, op0);
534
535 edge_info = new class edge_info (false_edge);
536 record_conditions (&edge_info->cond_equivalences, inverted, cond);
537
538 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
539 edge_info->record_simple_equiv (op1, op0);
540 }
541
542 else if (TREE_CODE (op0) == SSA_NAME
543 && (TREE_CODE (op1) == SSA_NAME
544 || is_gimple_min_invariant (op1)))
545 {
546 tree cond = build2 (code, boolean_type_node, op0, op1);
547 tree inverted = invert_truthvalue_loc (loc, cond);
548 bool can_infer_simple_equiv
549 = !(HONOR_SIGNED_ZEROS (op1)
550 && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
551 struct edge_info *edge_info;
552
553 edge_info = new class edge_info (true_edge);
554 record_conditions (&edge_info->cond_equivalences, cond, inverted);
555
556 if (can_infer_simple_equiv && code == EQ_EXPR)
557 edge_info->record_simple_equiv (op0, op1);
558
559 edge_info = new class edge_info (false_edge);
560 record_conditions (&edge_info->cond_equivalences, inverted, cond);
561
562 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
563 edge_info->record_simple_equiv (op0, op1);
564 }
565 }
566 }
567}
568
569
570class dom_opt_dom_walker : public dom_walker
571{
572public:
573 dom_opt_dom_walker (cdi_direction direction,
574 class const_and_copies *const_and_copies,
575 class avail_exprs_stack *avail_exprs_stack,
576 gcond *dummy_cond)
577 : dom_walker (direction, true),
578 m_const_and_copies (const_and_copies),
579 m_avail_exprs_stack (avail_exprs_stack),
580 m_dummy_cond (dummy_cond) { }
581
582 virtual edge before_dom_children (basic_block);
583 virtual void after_dom_children (basic_block);
584
585private:
586
587 /* Unwindable equivalences, both const/copy and expression varieties. */
588 class const_and_copies *m_const_and_copies;
589 class avail_exprs_stack *m_avail_exprs_stack;
590
591 /* VRP data. */
592 class evrp_range_analyzer evrp_range_analyzer;
593
594 /* Dummy condition to avoid creating lots of throw away statements. */
595 gcond *m_dummy_cond;
596
597 /* Optimize a single statement within a basic block using the
598 various tables mantained by DOM. Returns the taken edge if
599 the statement is a conditional with a statically determined
600 value. */
601 edge optimize_stmt (basic_block, gimple_stmt_iterator);
602};
603
604/* Jump threading, redundancy elimination and const/copy propagation.
605
606 This pass may expose new symbols that need to be renamed into SSA. For
607 every new symbol exposed, its corresponding bit will be set in
608 VARS_TO_RENAME. */
609
610namespace {
611
612const pass_data pass_data_dominator =
613{
614 GIMPLE_PASS, /* type */
615 "dom", /* name */
616 OPTGROUP_NONE, /* optinfo_flags */
617 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
618 ( PROP_cfg | PROP_ssa ), /* properties_required */
619 0, /* properties_provided */
620 0, /* properties_destroyed */
621 0, /* todo_flags_start */
622 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
623};
624
625class pass_dominator : public gimple_opt_pass
626{
627public:
628 pass_dominator (gcc::context *ctxt)
629 : gimple_opt_pass (pass_data_dominator, ctxt),
630 may_peel_loop_headers_p (false)
631 {}
632
633 /* opt_pass methods: */
634 opt_pass * clone () { return new pass_dominator (m_ctxt); }
635 void set_pass_param (unsigned int n, bool param)
636 {
637 gcc_assert (n == 0);
638 may_peel_loop_headers_p = param;
639 }
640 virtual bool gate (function *) { return flag_tree_dom != 0; }
641 virtual unsigned int execute (function *);
642
643 private:
644 /* This flag is used to prevent loops from being peeled repeatedly in jump
645 threading; it will be removed once we preserve loop structures throughout
646 the compilation -- we will be able to mark the affected loops directly in
647 jump threading, and avoid peeling them next time. */
648 bool may_peel_loop_headers_p;
649}; // class pass_dominator
650
651unsigned int
652pass_dominator::execute (function *fun)
653{
654 memset (&opt_stats, 0, sizeof (opt_stats));
655
656 /* Create our hash tables. */
657 hash_table<expr_elt_hasher> *avail_exprs
658 = new hash_table<expr_elt_hasher> (1024);
659 class avail_exprs_stack *avail_exprs_stack
660 = new class avail_exprs_stack (avail_exprs);
661 class const_and_copies *const_and_copies = new class const_and_copies ();
662 need_eh_cleanup = BITMAP_ALLOC (NULL);
663 need_noreturn_fixup.create (0);
664
665 calculate_dominance_info (CDI_DOMINATORS);
666 cfg_altered = false;
667
668 /* We need to know loop structures in order to avoid destroying them
669 in jump threading. Note that we still can e.g. thread through loop
670 headers to an exit edge, or through loop header to the loop body, assuming
671 that we update the loop info.
672
673 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
674 to several overly conservative bail-outs in jump threading, case
675 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
676 missing. We should improve jump threading in future then
677 LOOPS_HAVE_PREHEADERS won't be needed here. */
678 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
679
680 /* Initialize the value-handle array. */
681 threadedge_initialize_values ();
682
683 /* We need accurate information regarding back edges in the CFG
684 for jump threading; this may include back edges that are not part of
685 a single loop. */
686 mark_dfs_back_edges ();
687
688 /* We want to create the edge info structures before the dominator walk
689 so that they'll be in place for the jump threader, particularly when
690 threading through a join block.
691
692 The conditions will be lazily updated with global equivalences as
693 we reach them during the dominator walk. */
694 basic_block bb;
695 FOR_EACH_BB_FN (bb, fun)
696 record_edge_info (bb);
697
698 gcond *dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
699 integer_zero_node, NULL, NULL);
700
701 /* Recursively walk the dominator tree optimizing statements. */
702 dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies,
703 avail_exprs_stack, dummy_cond);
704 walker.walk (fun->cfg->x_entry_block_ptr);
705
706 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
707 edge. When found, remove jump threads which contain any outgoing
708 edge from the affected block. */
709 if (cfg_altered)
710 {
711 FOR_EACH_BB_FN (bb, fun)
712 {
713 edge_iterator ei;
714 edge e;
715
716 /* First see if there are any edges without EDGE_EXECUTABLE
717 set. */
718 bool found = false;
719 FOR_EACH_EDGE (e, ei, bb->succs)
720 {
721 if ((e->flags & EDGE_EXECUTABLE) == 0)
722 {
723 found = true;
724 break;
725 }
726 }
727
728 /* If there were any such edges found, then remove jump threads
729 containing any edge leaving BB. */
730 if (found)
731 FOR_EACH_EDGE (e, ei, bb->succs)
732 remove_jump_threads_including (e);
733 }
734 }
735
736 {
737 gimple_stmt_iterator gsi;
738 basic_block bb;
739 FOR_EACH_BB_FN (bb, fun)
740 {
741 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
742 update_stmt_if_modified (gsi_stmt (gsi));
743 }
744 }
745
746 /* If we exposed any new variables, go ahead and put them into
747 SSA form now, before we handle jump threading. This simplifies
748 interactions between rewriting of _DECL nodes into SSA form
749 and rewriting SSA_NAME nodes into SSA form after block
750 duplication and CFG manipulation. */
751 update_ssa (TODO_update_ssa);
752
753 free_all_edge_infos ();
754
755 /* Thread jumps, creating duplicate blocks as needed. */
756 cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p);
757
758 if (cfg_altered)
759 free_dominance_info (CDI_DOMINATORS);
760
761 /* Removal of statements may make some EH edges dead. Purge
762 such edges from the CFG as needed. */
763 if (!bitmap_empty_p (need_eh_cleanup))
764 {
765 unsigned i;
766 bitmap_iterator bi;
767
768 /* Jump threading may have created forwarder blocks from blocks
769 needing EH cleanup; the new successor of these blocks, which
770 has inherited from the original block, needs the cleanup.
771 Don't clear bits in the bitmap, as that can break the bitmap
772 iterator. */
773 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
774 {
775 basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
776 if (bb == NULL)
777 continue;
778 while (single_succ_p (bb)
779 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
780 bb = single_succ (bb);
781 if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
782 continue;
783 if ((unsigned) bb->index != i)
784 bitmap_set_bit (need_eh_cleanup, bb->index);
785 }
786
787 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
788 bitmap_clear (need_eh_cleanup);
789 }
790
791 /* Fixup stmts that became noreturn calls. This may require splitting
792 blocks and thus isn't possible during the dominator walk or before
793 jump threading finished. Do this in reverse order so we don't
794 inadvertedly remove a stmt we want to fixup by visiting a dominating
795 now noreturn call first. */
796 while (!need_noreturn_fixup.is_empty ())
797 {
798 gimple *stmt = need_noreturn_fixup.pop ();
799 if (dump_file && dump_flags & TDF_DETAILS)
800 {
801 fprintf (dump_file, "Fixing up noreturn call ");
802 print_gimple_stmt (dump_file, stmt, 0);
803 fprintf (dump_file, "\n");
804 }
805 fixup_noreturn_call (stmt);
806 }
807
808 statistics_counter_event (fun, "Redundant expressions eliminated",
809 opt_stats.num_re);
810 statistics_counter_event (fun, "Constants propagated",
811 opt_stats.num_const_prop);
812 statistics_counter_event (fun, "Copies propagated",
813 opt_stats.num_copy_prop);
814
815 /* Debugging dumps. */
816 if (dump_file && (dump_flags & TDF_STATS))
817 dump_dominator_optimization_stats (dump_file, avail_exprs);
818
819 loop_optimizer_finalize ();
820
821 /* Delete our main hashtable. */
822 delete avail_exprs;
823 avail_exprs = NULL;
824
825 /* Free asserted bitmaps and stacks. */
826 BITMAP_FREE (need_eh_cleanup);
827 need_noreturn_fixup.release ();
828 delete avail_exprs_stack;
829 delete const_and_copies;
830
831 /* Free the value-handle array. */
832 threadedge_finalize_values ();
833
834 return 0;
835}
836
837} // anon namespace
838
839gimple_opt_pass *
840make_pass_dominator (gcc::context *ctxt)
841{
842 return new pass_dominator (ctxt);
843}
844
845/* A hack until we remove threading from tree-vrp.c and bring the
846 simplification routine into the dom_opt_dom_walker class. */
847static class vr_values *x_vr_values;
848
849/* A trivial wrapper so that we can present the generic jump
850 threading code with a simple API for simplifying statements. */
851static tree
852simplify_stmt_for_jump_threading (gimple *stmt,
853 gimple *within_stmt ATTRIBUTE_UNUSED,
854 class avail_exprs_stack *avail_exprs_stack,
855 basic_block bb ATTRIBUTE_UNUSED)
856{
857 /* First query our hash table to see if the the expression is available
858 there. A non-NULL return value will be either a constant or another
859 SSA_NAME. */
860 tree cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, false, true);
861 if (cached_lhs)
862 return cached_lhs;
863
864 /* If the hash table query failed, query VRP information. This is
865 essentially the same as tree-vrp's simplification routine. The
866 copy in tree-vrp is scheduled for removal in gcc-9. */
867 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
868 {
869 cached_lhs
870 = x_vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
871 gimple_cond_lhs (cond_stmt),
872 gimple_cond_rhs (cond_stmt),
873 within_stmt);
874 return cached_lhs;
875 }
876
877 if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
878 {
879 tree op = gimple_switch_index (switch_stmt);
880 if (TREE_CODE (op) != SSA_NAME)
881 return NULL_TREE;
882
883 value_range *vr = x_vr_values->get_value_range (op);
884 if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
885 || symbolic_range_p (vr))
886 return NULL_TREE;
887
888 if (vr->type == VR_RANGE)
889 {
890 size_t i, j;
891
892 find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
893
894 if (i == j)
895 {
896 tree label = gimple_switch_label (switch_stmt, i);
897
898 if (CASE_HIGH (label) != NULL_TREE
899 ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
900 && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0)
901 : (tree_int_cst_equal (CASE_LOW (label), vr->min)
902 && tree_int_cst_equal (vr->min, vr->max)))
903 return label;
904
905 if (i > j)
906 return gimple_switch_label (switch_stmt, 0);
907 }
908 }
909
910 if (vr->type == VR_ANTI_RANGE)
911 {
912 unsigned n = gimple_switch_num_labels (switch_stmt);
913 tree min_label = gimple_switch_label (switch_stmt, 1);
914 tree max_label = gimple_switch_label (switch_stmt, n - 1);
915
916 /* The default label will be taken only if the anti-range of the
917 operand is entirely outside the bounds of all the (non-default)
918 case labels. */
919 if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
920 && (CASE_HIGH (max_label) != NULL_TREE
921 ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
922 : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >= 0))
923 return gimple_switch_label (switch_stmt, 0);
924 }
925 return NULL_TREE;
926 }
927
928 if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
929 {
930 tree lhs = gimple_assign_lhs (assign_stmt);
931 if (TREE_CODE (lhs) == SSA_NAME
932 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
933 || POINTER_TYPE_P (TREE_TYPE (lhs)))
934 && stmt_interesting_for_vrp (stmt))
935 {
936 edge dummy_e;
937 tree dummy_tree;
938 value_range new_vr = VR_INITIALIZER;
939 x_vr_values->extract_range_from_stmt (stmt, &dummy_e,
940 &dummy_tree, &new_vr);
941 if (range_int_cst_singleton_p (&new_vr))
942 return new_vr.min;
943 }
944 }
945 return NULL;
946}
947
948/* Valueize hook for gimple_fold_stmt_to_constant_1. */
949
950static tree
951dom_valueize (tree t)
952{
953 if (TREE_CODE (t) == SSA_NAME)
954 {
955 tree tem = SSA_NAME_VALUE (t);
956 if (tem)
957 return tem;
958 }
959 return t;
960}
961
962/* We have just found an equivalence for LHS on an edge E.
963 Look backwards to other uses of LHS and see if we can derive
964 additional equivalences that are valid on edge E. */
965static void
966back_propagate_equivalences (tree lhs, edge e,
967 class const_and_copies *const_and_copies)
968{
969 use_operand_p use_p;
970 imm_use_iterator iter;
971 bitmap domby = NULL;
972 basic_block dest = e->dest;
973
974 /* Iterate over the uses of LHS to see if any dominate E->dest.
975 If so, they may create useful equivalences too.
976
977 ??? If the code gets re-organized to a worklist to catch more
978 indirect opportunities and it is made to handle PHIs then this
979 should only consider use_stmts in basic-blocks we have already visited. */
980 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
981 {
982 gimple *use_stmt = USE_STMT (use_p);
983
984 /* Often the use is in DEST, which we trivially know we can't use.
985 This is cheaper than the dominator set tests below. */
986 if (dest == gimple_bb (use_stmt))
987 continue;
988
989 /* Filter out statements that can never produce a useful
990 equivalence. */
991 tree lhs2 = gimple_get_lhs (use_stmt);
992 if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME)
993 continue;
994
995 /* Profiling has shown the domination tests here can be fairly
996 expensive. We get significant improvements by building the
997 set of blocks that dominate BB. We can then just test
998 for set membership below.
999
1000 We also initialize the set lazily since often the only uses
1001 are going to be in the same block as DEST. */
1002 if (!domby)
1003 {
1004 domby = BITMAP_ALLOC (NULL);
1005 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest);
1006 while (bb)
1007 {
1008 bitmap_set_bit (domby, bb->index);
1009 bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1010 }
1011 }
1012
1013 /* This tests if USE_STMT does not dominate DEST. */
1014 if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index))
1015 continue;
1016
1017 /* At this point USE_STMT dominates DEST and may result in a
1018 useful equivalence. Try to simplify its RHS to a constant
1019 or SSA_NAME. */
1020 tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize,
1021 no_follow_ssa_edges);
1022 if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res)))
1023 record_equality (lhs2, res, const_and_copies);
1024 }
1025
1026 if (domby)
1027 BITMAP_FREE (domby);
1028}
1029
1030/* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
1031 by traversing edge E (which are cached in E->aux).
1032
1033 Callers are responsible for managing the unwinding markers. */
1034void
1035record_temporary_equivalences (edge e,
1036 class const_and_copies *const_and_copies,
1037 class avail_exprs_stack *avail_exprs_stack)
1038{
1039 int i;
1040 class edge_info *edge_info = (class edge_info *) e->aux;
1041
1042 /* If we have info associated with this edge, record it into
1043 our equivalence tables. */
1044 if (edge_info)
1045 {
1046 cond_equivalence *eq;
1047 /* If we have 0 = COND or 1 = COND equivalences, record them
1048 into our expression hash tables. */
1049 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
1050 avail_exprs_stack->record_cond (eq);
1051
1052 edge_info::equiv_pair *seq;
1053 for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i)
1054 {
1055 tree lhs = seq->first;
1056 if (!lhs || TREE_CODE (lhs) != SSA_NAME)
1057 continue;
1058
1059 /* Record the simple NAME = VALUE equivalence. */
1060 tree rhs = seq->second;
1061
1062 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
1063 cheaper to compute than the other, then set up the equivalence
1064 such that we replace the expensive one with the cheap one.
1065
1066 If they are the same cost to compute, then do not record
1067 anything. */
1068 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
1069 {
1070 gimple *rhs_def = SSA_NAME_DEF_STMT (rhs);
1071 int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights);
1072
1073 gimple *lhs_def = SSA_NAME_DEF_STMT (lhs);
1074 int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights);
1075
1076 if (rhs_cost > lhs_cost)
1077 record_equality (rhs, lhs, const_and_copies);
1078 else if (rhs_cost < lhs_cost)
1079 record_equality (lhs, rhs, const_and_copies);
1080 }
1081 else
1082 record_equality (lhs, rhs, const_and_copies);
1083
1084
1085 /* Any equivalence found for LHS may result in additional
1086 equivalences for other uses of LHS that we have already
1087 processed. */
1088 back_propagate_equivalences (lhs, e, const_and_copies);
1089 }
1090 }
1091}
1092
1093/* PHI nodes can create equivalences too.
1094
1095 Ignoring any alternatives which are the same as the result, if
1096 all the alternatives are equal, then the PHI node creates an
1097 equivalence. */
1098
1099static void
1100record_equivalences_from_phis (basic_block bb)
1101{
1102 gphi_iterator gsi;
1103
1104 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1105 {
1106 gphi *phi = gsi.phi ();
1107
1108 tree lhs = gimple_phi_result (phi);
1109 tree rhs = NULL;
1110 size_t i;
1111
1112 bool ignored_phi_arg = false;
1113 for (i = 0; i < gimple_phi_num_args (phi); i++)
1114 {
1115 tree t = gimple_phi_arg_def (phi, i);
1116
1117 /* Ignore alternatives which are the same as our LHS. Since
1118 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1119 can simply compare pointers. */
1120 if (lhs == t)
1121 continue;
1122
1123 /* We want to track if we ignored any PHI arguments because
1124 their associated edges were not executable. This impacts
1125 whether or not we can use any equivalence we might discover. */
1126 if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0)
1127 {
1128 ignored_phi_arg = true;
1129 continue;
1130 }
1131
1132 t = dom_valueize (t);
1133
1134 /* If we have not processed an alternative yet, then set
1135 RHS to this alternative. */
1136 if (rhs == NULL)
1137 rhs = t;
1138 /* If we have processed an alternative (stored in RHS), then
1139 see if it is equal to this one. If it isn't, then stop
1140 the search. */
1141 else if (! operand_equal_for_phi_arg_p (rhs, t))
1142 break;
1143 }
1144
1145 /* If we had no interesting alternatives, then all the RHS alternatives
1146 must have been the same as LHS. */
1147 if (!rhs)
1148 rhs = lhs;
1149
1150 /* If we managed to iterate through each PHI alternative without
1151 breaking out of the loop, then we have a PHI which may create
1152 a useful equivalence. We do not need to record unwind data for
1153 this, since this is a true assignment and not an equivalence
1154 inferred from a comparison. All uses of this ssa name are dominated
1155 by this assignment, so unwinding just costs time and space.
1156
1157 Note that if we ignored a PHI argument and the resulting equivalence
1158 is SSA_NAME = SSA_NAME. Then we can not use the equivalence as the
1159 uses of the LHS SSA_NAME are not necessarily dominated by the
1160 assignment of the RHS SSA_NAME. */
1161 if (i == gimple_phi_num_args (phi)
1162 && may_propagate_copy (lhs, rhs)
1163 && (!ignored_phi_arg || TREE_CODE (rhs) != SSA_NAME))
1164 set_ssa_name_value (lhs, rhs);
1165 }
1166}
1167
1168/* Record any equivalences created by the incoming edge to BB into
1169 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one
1170 incoming edge, then no equivalence is created. */
1171
1172static void
1173record_equivalences_from_incoming_edge (basic_block bb,
1174 class const_and_copies *const_and_copies,
1175 class avail_exprs_stack *avail_exprs_stack)
1176{
1177 edge e;
1178 basic_block parent;
1179
1180 /* If our parent block ended with a control statement, then we may be
1181 able to record some equivalences based on which outgoing edge from
1182 the parent was followed. */
1183 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1184
1185 e = single_pred_edge_ignoring_loop_edges (bb, true);
1186
1187 /* If we had a single incoming edge from our parent block, then enter
1188 any data associated with the edge into our tables. */
1189 if (e && e->src == parent)
1190 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
1191}
1192
1193/* Dump statistics for the hash table HTAB. */
1194
1195static void
1196htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab)
1197{
1198 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1199 (long) htab.size (),
1200 (long) htab.elements (),
1201 htab.collisions ());
1202}
1203
1204/* Dump SSA statistics on FILE. */
1205
1206static void
1207dump_dominator_optimization_stats (FILE *file,
1208 hash_table<expr_elt_hasher> *avail_exprs)
1209{
1210 fprintf (file, "Total number of statements: %6ld\n\n",
1211 opt_stats.num_stmts);
1212 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1213 opt_stats.num_exprs_considered);
1214
1215 fprintf (file, "\nHash table statistics:\n");
1216
1217 fprintf (file, " avail_exprs: ");
1218 htab_statistics (file, *avail_exprs);
1219}
1220
1221
1222/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1223 This constrains the cases in which we may treat this as assignment. */
1224
1225static void
1226record_equality (tree x, tree y, class const_and_copies *const_and_copies)
1227{
1228 tree prev_x = NULL, prev_y = NULL;
1229
1230 if (tree_swap_operands_p (x, y))
1231 std::swap (x, y);
1232
1233 /* Most of the time tree_swap_operands_p does what we want. But there
1234 are cases where we know one operand is better for copy propagation than
1235 the other. Given no other code cares about ordering of equality
1236 comparison operators for that purpose, we just handle the special cases
1237 here. */
1238 if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME)
1239 {
1240 /* If one operand is a single use operand, then make it
1241 X. This will preserve its single use properly and if this
1242 conditional is eliminated, the computation of X can be
1243 eliminated as well. */
1244 if (has_single_use (y) && ! has_single_use (x))
1245 std::swap (x, y);
1246 }
1247 if (TREE_CODE (x) == SSA_NAME)
1248 prev_x = SSA_NAME_VALUE (x);
1249 if (TREE_CODE (y) == SSA_NAME)
1250 prev_y = SSA_NAME_VALUE (y);
1251
1252 /* If one of the previous values is invariant, or invariant in more loops
1253 (by depth), then use that.
1254 Otherwise it doesn't matter which value we choose, just so
1255 long as we canonicalize on one value. */
1256 if (is_gimple_min_invariant (y))
1257 ;
1258 else if (is_gimple_min_invariant (x))
1259 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1260 else if (prev_x && is_gimple_min_invariant (prev_x))
1261 x = y, y = prev_x, prev_x = prev_y;
1262 else if (prev_y)
1263 y = prev_y;
1264
1265 /* After the swapping, we must have one SSA_NAME. */
1266 if (TREE_CODE (x) != SSA_NAME)
1267 return;
1268
1269 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1270 variable compared against zero. If we're honoring signed zeros,
1271 then we cannot record this value unless we know that the value is
1272 nonzero. */
1273 if (HONOR_SIGNED_ZEROS (x)
1274 && (TREE_CODE (y) != REAL_CST
1275 || real_equal (&dconst0, &TREE_REAL_CST (y))))
1276 return;
1277
1278 const_and_copies->record_const_or_copy (x, y, prev_x);
1279}
1280
1281/* Returns true when STMT is a simple iv increment. It detects the
1282 following situation:
1283
1284 i_1 = phi (..., i_2)
1285 i_2 = i_1 +/- ... */
1286
1287bool
1288simple_iv_increment_p (gimple *stmt)
1289{
1290 enum tree_code code;
1291 tree lhs, preinc;
1292 gimple *phi;
1293 size_t i;
1294
1295 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1296 return false;
1297
1298 lhs = gimple_assign_lhs (stmt);
1299 if (TREE_CODE (lhs) != SSA_NAME)
1300 return false;
1301
1302 code = gimple_assign_rhs_code (stmt);
1303 if (code != PLUS_EXPR
1304 && code != MINUS_EXPR
1305 && code != POINTER_PLUS_EXPR)
1306 return false;
1307
1308 preinc = gimple_assign_rhs1 (stmt);
1309 if (TREE_CODE (preinc) != SSA_NAME)
1310 return false;
1311
1312 phi = SSA_NAME_DEF_STMT (preinc);
1313 if (gimple_code (phi) != GIMPLE_PHI)
1314 return false;
1315
1316 for (i = 0; i < gimple_phi_num_args (phi); i++)
1317 if (gimple_phi_arg_def (phi, i) == lhs)
1318 return true;
1319
1320 return false;
1321}
1322
1323/* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
1324 successors of BB. */
1325
1326static void
1327cprop_into_successor_phis (basic_block bb,
1328 class const_and_copies *const_and_copies)
1329{
1330 edge e;
1331 edge_iterator ei;
1332
1333 FOR_EACH_EDGE (e, ei, bb->succs)
1334 {
1335 int indx;
1336 gphi_iterator gsi;
1337
1338 /* If this is an abnormal edge, then we do not want to copy propagate
1339 into the PHI alternative associated with this edge. */
1340 if (e->flags & EDGE_ABNORMAL)
1341 continue;
1342
1343 gsi = gsi_start_phis (e->dest);
1344 if (gsi_end_p (gsi))
1345 continue;
1346
1347 /* We may have an equivalence associated with this edge. While
1348 we can not propagate it into non-dominated blocks, we can
1349 propagate them into PHIs in non-dominated blocks. */
1350
1351 /* Push the unwind marker so we can reset the const and copies
1352 table back to its original state after processing this edge. */
1353 const_and_copies->push_marker ();
1354
1355 /* Extract and record any simple NAME = VALUE equivalences.
1356
1357 Don't bother with [01] = COND equivalences, they're not useful
1358 here. */
1359 class edge_info *edge_info = (class edge_info *) e->aux;
1360
1361 if (edge_info)
1362 {
1363 edge_info::equiv_pair *seq;
1364 for (int i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i)
1365 {
1366 tree lhs = seq->first;
1367 tree rhs = seq->second;
1368
1369 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1370 const_and_copies->record_const_or_copy (lhs, rhs);
1371 }
1372
1373 }
1374
1375 indx = e->dest_idx;
1376 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1377 {
1378 tree new_val;
1379 use_operand_p orig_p;
1380 tree orig_val;
1381 gphi *phi = gsi.phi ();
1382
1383 /* The alternative may be associated with a constant, so verify
1384 it is an SSA_NAME before doing anything with it. */
1385 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1386 orig_val = get_use_from_ptr (orig_p);
1387 if (TREE_CODE (orig_val) != SSA_NAME)
1388 continue;
1389
1390 /* If we have *ORIG_P in our constant/copy table, then replace
1391 ORIG_P with its value in our constant/copy table. */
1392 new_val = SSA_NAME_VALUE (orig_val);
1393 if (new_val
1394 && new_val != orig_val
1395 && may_propagate_copy (orig_val, new_val))
1396 propagate_value (orig_p, new_val);
1397 }
1398
1399 const_and_copies->pop_to_marker ();
1400 }
1401}
1402
1403edge
1404dom_opt_dom_walker::before_dom_children (basic_block bb)
1405{
1406 gimple_stmt_iterator gsi;
1407
1408 if (dump_file && (dump_flags & TDF_DETAILS))
1409 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
1410
1411 evrp_range_analyzer.enter (bb);
1412
1413 /* Push a marker on the stacks of local information so that we know how
1414 far to unwind when we finalize this block. */
1415 m_avail_exprs_stack->push_marker ();
1416 m_const_and_copies->push_marker ();
1417
1418 record_equivalences_from_incoming_edge (bb, m_const_and_copies,
1419 m_avail_exprs_stack);
1420
1421 /* PHI nodes can create equivalences too. */
1422 record_equivalences_from_phis (bb);
1423
1424 /* Create equivalences from redundant PHIs. PHIs are only truly
1425 redundant when they exist in the same block, so push another
1426 marker and unwind right afterwards. */
1427 m_avail_exprs_stack->push_marker ();
1428 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1429 eliminate_redundant_computations (&gsi, m_const_and_copies,
1430 m_avail_exprs_stack);
1431 m_avail_exprs_stack->pop_to_marker ();
1432
1433 edge taken_edge = NULL;
1434 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1435 {
1436 evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
1437 taken_edge = this->optimize_stmt (bb, gsi);
1438 }
1439
1440 /* Now prepare to process dominated blocks. */
1441 record_edge_info (bb);
1442 cprop_into_successor_phis (bb, m_const_and_copies);
1443 if (taken_edge && !dbg_cnt (dom_unreachable_edges))
1444 return NULL;
1445
1446 return taken_edge;
1447}
1448
1449/* We have finished processing the dominator children of BB, perform
1450 any finalization actions in preparation for leaving this node in
1451 the dominator tree. */
1452
1453void
1454dom_opt_dom_walker::after_dom_children (basic_block bb)
1455{
1456 x_vr_values = evrp_range_analyzer.get_vr_values ();
1457 thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
1458 m_avail_exprs_stack,
1459 &evrp_range_analyzer,
1460 simplify_stmt_for_jump_threading);
1461 x_vr_values = NULL;
1462
1463 /* These remove expressions local to BB from the tables. */
1464 m_avail_exprs_stack->pop_to_marker ();
1465 m_const_and_copies->pop_to_marker ();
1466 evrp_range_analyzer.leave (bb);
1467}
1468
1469/* Search for redundant computations in STMT. If any are found, then
1470 replace them with the variable holding the result of the computation.
1471
1472 If safe, record this expression into AVAIL_EXPRS_STACK and
1473 CONST_AND_COPIES. */
1474
1475static void
1476eliminate_redundant_computations (gimple_stmt_iterator* gsi,
1477 class const_and_copies *const_and_copies,
1478 class avail_exprs_stack *avail_exprs_stack)
1479{
1480 tree expr_type;
1481 tree cached_lhs;
1482 tree def;
1483 bool insert = true;
1484 bool assigns_var_p = false;
1485
1486 gimple *stmt = gsi_stmt (*gsi);
1487
1488 if (gimple_code (stmt) == GIMPLE_PHI)
1489 def = gimple_phi_result (stmt);
1490 else
1491 def = gimple_get_lhs (stmt);
1492
1493 /* Certain expressions on the RHS can be optimized away, but can not
1494 themselves be entered into the hash tables. */
1495 if (! def
1496 || TREE_CODE (def) != SSA_NAME
1497 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1498 || gimple_vdef (stmt)
1499 /* Do not record equivalences for increments of ivs. This would create
1500 overlapping live ranges for a very questionable gain. */
1501 || simple_iv_increment_p (stmt))
1502 insert = false;
1503
1504 /* Check if the expression has been computed before. */
1505 cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, insert, true);
1506
1507 opt_stats.num_exprs_considered++;
1508
1509 /* Get the type of the expression we are trying to optimize. */
1510 if (is_gimple_assign (stmt))
1511 {
1512 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1513 assigns_var_p = true;
1514 }
1515 else if (gimple_code (stmt) == GIMPLE_COND)
1516 expr_type = boolean_type_node;
1517 else if (is_gimple_call (stmt))
1518 {
1519 gcc_assert (gimple_call_lhs (stmt));
1520 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1521 assigns_var_p = true;
1522 }
1523 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1524 expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt));
1525 else if (gimple_code (stmt) == GIMPLE_PHI)
1526 /* We can't propagate into a phi, so the logic below doesn't apply.
1527 Instead record an equivalence between the cached LHS and the
1528 PHI result of this statement, provided they are in the same block.
1529 This should be sufficient to kill the redundant phi. */
1530 {
1531 if (def && cached_lhs)
1532 const_and_copies->record_const_or_copy (def, cached_lhs);
1533 return;
1534 }
1535 else
1536 gcc_unreachable ();
1537
1538 if (!cached_lhs)
1539 return;
1540
1541 /* It is safe to ignore types here since we have already done
1542 type checking in the hashing and equality routines. In fact
1543 type checking here merely gets in the way of constant
1544 propagation. Also, make sure that it is safe to propagate
1545 CACHED_LHS into the expression in STMT. */
1546 if ((TREE_CODE (cached_lhs) != SSA_NAME
1547 && (assigns_var_p
1548 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1549 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1550 {
1551 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
1552 || is_gimple_min_invariant (cached_lhs));
1553
1554 if (dump_file && (dump_flags & TDF_DETAILS))
1555 {
1556 fprintf (dump_file, " Replaced redundant expr '");
1557 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1558 fprintf (dump_file, "' with '");
1559 print_generic_expr (dump_file, cached_lhs, dump_flags);
1560 fprintf (dump_file, "'\n");
1561 }
1562
1563 opt_stats.num_re++;
1564
1565 if (assigns_var_p
1566 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1567 cached_lhs = fold_convert (expr_type, cached_lhs);
1568
1569 propagate_tree_value_into_stmt (gsi, cached_lhs);
1570
1571 /* Since it is always necessary to mark the result as modified,
1572 perhaps we should move this into propagate_tree_value_into_stmt
1573 itself. */
1574 gimple_set_modified (gsi_stmt (*gsi), true);
1575 }
1576}
1577
1578/* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1579 the available expressions table or the const_and_copies table.
1580 Detect and record those equivalences into AVAIL_EXPRS_STACK.
1581
1582 We handle only very simple copy equivalences here. The heavy
1583 lifing is done by eliminate_redundant_computations. */
1584
1585static void
1586record_equivalences_from_stmt (gimple *stmt, int may_optimize_p,
1587 class avail_exprs_stack *avail_exprs_stack)
1588{
1589 tree lhs;
1590 enum tree_code lhs_code;
1591
1592 gcc_assert (is_gimple_assign (stmt));
1593
1594 lhs = gimple_assign_lhs (stmt);
1595 lhs_code = TREE_CODE (lhs);
1596
1597 if (lhs_code == SSA_NAME
1598 && gimple_assign_single_p (stmt))
1599 {
1600 tree rhs = gimple_assign_rhs1 (stmt);
1601
1602 /* If the RHS of the assignment is a constant or another variable that
1603 may be propagated, register it in the CONST_AND_COPIES table. We
1604 do not need to record unwind data for this, since this is a true
1605 assignment and not an equivalence inferred from a comparison. All
1606 uses of this ssa name are dominated by this assignment, so unwinding
1607 just costs time and space. */
1608 if (may_optimize_p
1609 && (TREE_CODE (rhs) == SSA_NAME
1610 || is_gimple_min_invariant (rhs)))
1611 {
1612 rhs = dom_valueize (rhs);
1613
1614 if (dump_file && (dump_flags & TDF_DETAILS))
1615 {
1616 fprintf (dump_file, "==== ASGN ");
1617 print_generic_expr (dump_file, lhs);
1618 fprintf (dump_file, " = ");
1619 print_generic_expr (dump_file, rhs);
1620 fprintf (dump_file, "\n");
1621 }
1622
1623 set_ssa_name_value (lhs, rhs);
1624 }
1625 }
1626
1627 /* Make sure we can propagate &x + CST. */
1628 if (lhs_code == SSA_NAME
1629 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
1630 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR
1631 && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
1632 {
1633 tree op0 = gimple_assign_rhs1 (stmt);
1634 tree op1 = gimple_assign_rhs2 (stmt);
1635 tree new_rhs
1636 = build_fold_addr_expr (fold_build2 (MEM_REF,
1637 TREE_TYPE (TREE_TYPE (op0)),
1638 unshare_expr (op0),
1639 fold_convert (ptr_type_node,
1640 op1)));
1641 if (dump_file && (dump_flags & TDF_DETAILS))
1642 {
1643 fprintf (dump_file, "==== ASGN ");
1644 print_generic_expr (dump_file, lhs);
1645 fprintf (dump_file, " = ");
1646 print_generic_expr (dump_file, new_rhs);
1647 fprintf (dump_file, "\n");
1648 }
1649
1650 set_ssa_name_value (lhs, new_rhs);
1651 }
1652
1653 /* A memory store, even an aliased store, creates a useful
1654 equivalence. By exchanging the LHS and RHS, creating suitable
1655 vops and recording the result in the available expression table,
1656 we may be able to expose more redundant loads. */
1657 if (!gimple_has_volatile_ops (stmt)
1658 && gimple_references_memory_p (stmt)
1659 && gimple_assign_single_p (stmt)
1660 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1661 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1662 && !is_gimple_reg (lhs))
1663 {
1664 tree rhs = gimple_assign_rhs1 (stmt);
1665 gassign *new_stmt;
1666
1667 /* Build a new statement with the RHS and LHS exchanged. */
1668 if (TREE_CODE (rhs) == SSA_NAME)
1669 {
1670 /* NOTE tuples. The call to gimple_build_assign below replaced
1671 a call to build_gimple_modify_stmt, which did not set the
1672 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1673 may cause an SSA validation failure, as the LHS may be a
1674 default-initialized name and should have no definition. I'm
1675 a bit dubious of this, as the artificial statement that we
1676 generate here may in fact be ill-formed, but it is simply
1677 used as an internal device in this pass, and never becomes
1678 part of the CFG. */
1679 gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
1680 new_stmt = gimple_build_assign (rhs, lhs);
1681 SSA_NAME_DEF_STMT (rhs) = defstmt;
1682 }
1683 else
1684 new_stmt = gimple_build_assign (rhs, lhs);
1685
1686 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1687
1688 /* Finally enter the statement into the available expression
1689 table. */
1690 avail_exprs_stack->lookup_avail_expr (new_stmt, true, true);
1691 }
1692}
1693
1694/* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1695 CONST_AND_COPIES. */
1696
1697static void
1698cprop_operand (gimple *stmt, use_operand_p op_p)
1699{
1700 tree val;
1701 tree op = USE_FROM_PTR (op_p);
1702
1703 /* If the operand has a known constant value or it is known to be a
1704 copy of some other variable, use the value or copy stored in
1705 CONST_AND_COPIES. */
1706 val = SSA_NAME_VALUE (op);
1707 if (val && val != op)
1708 {
1709 /* Do not replace hard register operands in asm statements. */
1710 if (gimple_code (stmt) == GIMPLE_ASM
1711 && !may_propagate_copy_into_asm (op))
1712 return;
1713
1714 /* Certain operands are not allowed to be copy propagated due
1715 to their interaction with exception handling and some GCC
1716 extensions. */
1717 if (!may_propagate_copy (op, val))
1718 return;
1719
1720 /* Do not propagate copies into BIVs.
1721 See PR23821 and PR62217 for how this can disturb IV and
1722 number of iteration analysis. */
1723 if (TREE_CODE (val) != INTEGER_CST)
1724 {
1725 gimple *def = SSA_NAME_DEF_STMT (op);
1726 if (gimple_code (def) == GIMPLE_PHI
1727 && gimple_bb (def)->loop_father->header == gimple_bb (def))
1728 return;
1729 }
1730
1731 /* Dump details. */
1732 if (dump_file && (dump_flags & TDF_DETAILS))
1733 {
1734 fprintf (dump_file, " Replaced '");
1735 print_generic_expr (dump_file, op, dump_flags);
1736 fprintf (dump_file, "' with %s '",
1737 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
1738 print_generic_expr (dump_file, val, dump_flags);
1739 fprintf (dump_file, "'\n");
1740 }
1741
1742 if (TREE_CODE (val) != SSA_NAME)
1743 opt_stats.num_const_prop++;
1744 else
1745 opt_stats.num_copy_prop++;
1746
1747 propagate_value (op_p, val);
1748
1749 /* And note that we modified this statement. This is now
1750 safe, even if we changed virtual operands since we will
1751 rescan the statement and rewrite its operands again. */
1752 gimple_set_modified (stmt, true);
1753 }
1754}
1755
1756/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1757 known value for that SSA_NAME (or NULL if no value is known).
1758
1759 Propagate values from CONST_AND_COPIES into the uses, vuses and
1760 vdef_ops of STMT. */
1761
1762static void
1763cprop_into_stmt (gimple *stmt)
1764{
1765 use_operand_p op_p;
1766 ssa_op_iter iter;
1767 tree last_copy_propagated_op = NULL;
1768
1769 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
1770 {
1771 tree old_op = USE_FROM_PTR (op_p);
1772
1773 /* If we have A = B and B = A in the copy propagation tables
1774 (due to an equality comparison), avoid substituting B for A
1775 then A for B in the trivially discovered cases. This allows
1776 optimization of statements were A and B appear as input
1777 operands. */
1778 if (old_op != last_copy_propagated_op)
1779 {
1780 cprop_operand (stmt, op_p);
1781
1782 tree new_op = USE_FROM_PTR (op_p);
1783 if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME)
1784 last_copy_propagated_op = new_op;
1785 }
1786 }
1787}
1788
1789/* If STMT contains a relational test, try to convert it into an
1790 equality test if there is only a single value which can ever
1791 make the test true.
1792
1793 For example, if the expression hash table contains:
1794
1795 TRUE = (i <= 1)
1796
1797 And we have a test within statement of i >= 1, then we can safely
1798 rewrite the test as i == 1 since there only a single value where
1799 the test is true.
1800
1801 This is similar to code in VRP. */
1802
1803static void
1804test_for_singularity (gimple *stmt, gcond *dummy_cond,
1805 avail_exprs_stack *avail_exprs_stack)
1806{
1807 /* We want to support gimple conditionals as well as assignments
1808 where the RHS contains a conditional. */
1809 if (is_gimple_assign (stmt) || gimple_code (stmt) == GIMPLE_COND)
1810 {
1811 enum tree_code code = ERROR_MARK;
1812 tree lhs, rhs;
1813
1814 /* Extract the condition of interest from both forms we support. */
1815 if (is_gimple_assign (stmt))
1816 {
1817 code = gimple_assign_rhs_code (stmt);
1818 lhs = gimple_assign_rhs1 (stmt);
1819 rhs = gimple_assign_rhs2 (stmt);
1820 }
1821 else if (gimple_code (stmt) == GIMPLE_COND)
1822 {
1823 code = gimple_cond_code (as_a <gcond *> (stmt));
1824 lhs = gimple_cond_lhs (as_a <gcond *> (stmt));
1825 rhs = gimple_cond_rhs (as_a <gcond *> (stmt));
1826 }
1827
1828 /* We're looking for a relational test using LE/GE. Also note we can
1829 canonicalize LT/GT tests against constants into LE/GT tests. */
1830 if (code == LE_EXPR || code == GE_EXPR
1831 || ((code == LT_EXPR || code == GT_EXPR)
1832 && TREE_CODE (rhs) == INTEGER_CST))
1833 {
1834 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */
1835 if (code == LT_EXPR)
1836 rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs),
1837 rhs, build_int_cst (TREE_TYPE (rhs), 1));
1838
1839 if (code == GT_EXPR)
1840 rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs),
1841 rhs, build_int_cst (TREE_TYPE (rhs), 1));
1842
1843 /* Determine the code we want to check for in the hash table. */
1844 enum tree_code test_code;
1845 if (code == GE_EXPR || code == GT_EXPR)
1846 test_code = LE_EXPR;
1847 else
1848 test_code = GE_EXPR;
1849
1850 /* Update the dummy statement so we can query the hash tables. */
1851 gimple_cond_set_code (dummy_cond, test_code);
1852 gimple_cond_set_lhs (dummy_cond, lhs);
1853 gimple_cond_set_rhs (dummy_cond, rhs);
1854 tree cached_lhs
1855 = avail_exprs_stack->lookup_avail_expr (dummy_cond, false, false);
1856
1857 /* If the lookup returned 1 (true), then the expression we
1858 queried was in the hash table. As a result there is only
1859 one value that makes the original conditional true. Update
1860 STMT accordingly. */
1861 if (cached_lhs && integer_onep (cached_lhs))
1862 {
1863 if (is_gimple_assign (stmt))
1864 {
1865 gimple_assign_set_rhs_code (stmt, EQ_EXPR);
1866 gimple_assign_set_rhs2 (stmt, rhs);
1867 gimple_set_modified (stmt, true);
1868 }
1869 else
1870 {
1871 gimple_set_modified (stmt, true);
1872 gimple_cond_set_code (as_a <gcond *> (stmt), EQ_EXPR);
1873 gimple_cond_set_rhs (as_a <gcond *> (stmt), rhs);
1874 gimple_set_modified (stmt, true);
1875 }
1876 }
1877 }
1878 }
1879}
1880
1881/* Optimize the statement in block BB pointed to by iterator SI.
1882
1883 We try to perform some simplistic global redundancy elimination and
1884 constant propagation:
1885
1886 1- To detect global redundancy, we keep track of expressions that have
1887 been computed in this block and its dominators. If we find that the
1888 same expression is computed more than once, we eliminate repeated
1889 computations by using the target of the first one.
1890
1891 2- Constant values and copy assignments. This is used to do very
1892 simplistic constant and copy propagation. When a constant or copy
1893 assignment is found, we map the value on the RHS of the assignment to
1894 the variable in the LHS in the CONST_AND_COPIES table.
1895
1896 3- Very simple redundant store elimination is performed.
1897
1898 4- We can simpify a condition to a constant or from a relational
1899 condition to an equality condition. */
1900
1901edge
1902dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator si)
1903{
1904 gimple *stmt, *old_stmt;
1905 bool may_optimize_p;
1906 bool modified_p = false;
1907 bool was_noreturn;
1908 edge retval = NULL;
1909
1910 old_stmt = stmt = gsi_stmt (si);
1911 was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
1912
1913 if (dump_file && (dump_flags & TDF_DETAILS))
1914 {
1915 fprintf (dump_file, "Optimizing statement ");
1916 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1917 }
1918
1919 update_stmt_if_modified (stmt);
1920 opt_stats.num_stmts++;
1921
1922 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1923 cprop_into_stmt (stmt);
1924
1925 /* If the statement has been modified with constant replacements,
1926 fold its RHS before checking for redundant computations. */
1927 if (gimple_modified_p (stmt))
1928 {
1929 tree rhs = NULL;
1930
1931 /* Try to fold the statement making sure that STMT is kept
1932 up to date. */
1933 if (fold_stmt (&si))
1934 {
1935 stmt = gsi_stmt (si);
1936 gimple_set_modified (stmt, true);
1937
1938 if (dump_file && (dump_flags & TDF_DETAILS))
1939 {
1940 fprintf (dump_file, " Folded to: ");
1941 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1942 }
1943 }
1944
1945 /* We only need to consider cases that can yield a gimple operand. */
1946 if (gimple_assign_single_p (stmt))
1947 rhs = gimple_assign_rhs1 (stmt);
1948 else if (gimple_code (stmt) == GIMPLE_GOTO)
1949 rhs = gimple_goto_dest (stmt);
1950 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
1951 /* This should never be an ADDR_EXPR. */
1952 rhs = gimple_switch_index (swtch_stmt);
1953
1954 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
1955 recompute_tree_invariant_for_addr_expr (rhs);
1956
1957 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
1958 even if fold_stmt updated the stmt already and thus cleared
1959 gimple_modified_p flag on it. */
1960 modified_p = true;
1961 }
1962
1963 /* Check for redundant computations. Do this optimization only
1964 for assignments that have no volatile ops and conditionals. */
1965 may_optimize_p = (!gimple_has_side_effects (stmt)
1966 && (is_gimple_assign (stmt)
1967 || (is_gimple_call (stmt)
1968 && gimple_call_lhs (stmt) != NULL_TREE)
1969 || gimple_code (stmt) == GIMPLE_COND
1970 || gimple_code (stmt) == GIMPLE_SWITCH));
1971
1972 if (may_optimize_p)
1973 {
1974 if (gimple_code (stmt) == GIMPLE_CALL)
1975 {
1976 /* Resolve __builtin_constant_p. If it hasn't been
1977 folded to integer_one_node by now, it's fairly
1978 certain that the value simply isn't constant. */
1979 tree callee = gimple_call_fndecl (stmt);
1980 if (callee
1981 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
1982 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P)
1983 {
1984 propagate_tree_value_into_stmt (&si, integer_zero_node);
1985 stmt = gsi_stmt (si);
1986 }
1987 }
1988
1989 if (gimple_code (stmt) == GIMPLE_COND)
1990 {
1991 tree lhs = gimple_cond_lhs (stmt);
1992 tree rhs = gimple_cond_rhs (stmt);
1993
1994 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
1995 then this conditional is computable at compile time. We can just
1996 shove either 0 or 1 into the LHS, mark the statement as modified
1997 and all the right things will just happen below.
1998
1999 Note this would apply to any case where LHS has a range
2000 narrower than its type implies and RHS is outside that
2001 narrower range. Future work. */
2002 if (TREE_CODE (lhs) == SSA_NAME
2003 && ssa_name_has_boolean_range (lhs)
2004 && TREE_CODE (rhs) == INTEGER_CST
2005 && ! (integer_zerop (rhs) || integer_onep (rhs)))
2006 {
2007 gimple_cond_set_lhs (as_a <gcond *> (stmt),
2008 fold_convert (TREE_TYPE (lhs),
2009 integer_zero_node));
2010 gimple_set_modified (stmt, true);
2011 }
2012 else if (TREE_CODE (lhs) == SSA_NAME)
2013 {
2014 /* Exploiting EVRP data is not yet fully integrated into DOM
2015 but we need to do something for this case to avoid regressing
2016 udr4.f90 and new1.C which have unexecutable blocks with
2017 undefined behavior that get diagnosed if they're left in the
2018 IL because we've attached range information to new
2019 SSA_NAMES. */
2020 edge taken_edge = NULL;
2021 evrp_range_analyzer.vrp_visit_cond_stmt (as_a <gcond *> (stmt),
2022 &taken_edge);
2023 if (taken_edge)
2024 {
2025 if (taken_edge->flags & EDGE_TRUE_VALUE)
2026 gimple_cond_make_true (as_a <gcond *> (stmt));
2027 else if (taken_edge->flags & EDGE_FALSE_VALUE)
2028 gimple_cond_make_false (as_a <gcond *> (stmt));
2029 else
2030 gcc_unreachable ();
2031 gimple_set_modified (stmt, true);
2032 update_stmt (stmt);
2033 cfg_altered = true;
2034 return taken_edge;
2035 }
2036 }
2037 }
2038
2039 update_stmt_if_modified (stmt);
2040 eliminate_redundant_computations (&si, m_const_and_copies,
2041 m_avail_exprs_stack);
2042 stmt = gsi_stmt (si);
2043
2044 /* Perform simple redundant store elimination. */
2045 if (gimple_assign_single_p (stmt)
2046 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2047 {
2048 tree lhs = gimple_assign_lhs (stmt);
2049 tree rhs = gimple_assign_rhs1 (stmt);
2050 tree cached_lhs;
2051 gassign *new_stmt;
2052 rhs = dom_valueize (rhs);
2053 /* Build a new statement with the RHS and LHS exchanged. */
2054 if (TREE_CODE (rhs) == SSA_NAME)
2055 {
2056 gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
2057 new_stmt = gimple_build_assign (rhs, lhs);
2058 SSA_NAME_DEF_STMT (rhs) = defstmt;
2059 }
2060 else
2061 new_stmt = gimple_build_assign (rhs, lhs);
2062 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2063 cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false,
2064 false);
2065 if (cached_lhs && operand_equal_p (rhs, cached_lhs, 0))
2066 {
2067 basic_block bb = gimple_bb (stmt);
2068 unlink_stmt_vdef (stmt);
2069 if (gsi_remove (&si, true))
2070 {
2071 bitmap_set_bit (need_eh_cleanup, bb->index);
2072 if (dump_file && (dump_flags & TDF_DETAILS))
2073 fprintf (dump_file, " Flagged to clear EH edges.\n");
2074 }
2075 release_defs (stmt);
2076 return retval;
2077 }
2078 }
2079
2080 /* If this statement was not redundant, we may still be able to simplify
2081 it, which may in turn allow other part of DOM or other passes to do
2082 a better job. */
2083 test_for_singularity (stmt, m_dummy_cond, m_avail_exprs_stack);
2084 }
2085
2086 /* Record any additional equivalences created by this statement. */
2087 if (is_gimple_assign (stmt))
2088 record_equivalences_from_stmt (stmt, may_optimize_p, m_avail_exprs_stack);
2089
2090 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
2091 know where it goes. */
2092 if (gimple_modified_p (stmt) || modified_p)
2093 {
2094 tree val = NULL;
2095
2096 if (gimple_code (stmt) == GIMPLE_COND)
2097 val = fold_binary_loc (gimple_location (stmt),
2098 gimple_cond_code (stmt), boolean_type_node,
2099 gimple_cond_lhs (stmt),
2100 gimple_cond_rhs (stmt));
2101 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
2102 val = gimple_switch_index (swtch_stmt);
2103
2104 if (val && TREE_CODE (val) == INTEGER_CST)
2105 {
2106 retval = find_taken_edge (bb, val);
2107 if (retval)
2108 {
2109 /* Fix the condition to be either true or false. */
2110 if (gimple_code (stmt) == GIMPLE_COND)
2111 {
2112 if (integer_zerop (val))
2113 gimple_cond_make_false (as_a <gcond *> (stmt));
2114 else if (integer_onep (val))
2115 gimple_cond_make_true (as_a <gcond *> (stmt));
2116 else
2117 gcc_unreachable ();
2118
2119 gimple_set_modified (stmt, true);
2120 }
2121
2122 /* Further simplifications may be possible. */
2123 cfg_altered = true;
2124 }
2125 }
2126
2127 update_stmt_if_modified (stmt);
2128
2129 /* If we simplified a statement in such a way as to be shown that it
2130 cannot trap, update the eh information and the cfg to match. */
2131 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2132 {
2133 bitmap_set_bit (need_eh_cleanup, bb->index);
2134 if (dump_file && (dump_flags & TDF_DETAILS))
2135 fprintf (dump_file, " Flagged to clear EH edges.\n");
2136 }
2137
2138 if (!was_noreturn
2139 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
2140 need_noreturn_fixup.safe_push (stmt);
2141 }
2142 return retval;
2143}
2144