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